一致性 hash 环算法

　　一致性 hash 是一种被广泛应用的技术，其最早在一个叫 distributed hash tables(DHTs)的系统中进行使用。那些类 Dynamo 的应用，比如 Cassandra、Voldemort 和 Riak，基本上都使用了一致性 hash 环算法。

▲图1 一致性Hash环算法的hash函数

　　如图 1 所示，一致性 hash 环算法有一个 hash 函数H，所有存储数据的节点和数据本身都可以通过这个函数算出一个 hash 值，作为自己在下面环上的位置。然后每个节点会负责存储其 hash 值到下一个节点间的所有数据的存储。这样使得即使节点数变化了，大部分数据并不需要进行迁移。

　　连续范围分区

　　使用连续范围分区的方法进行数据分片，需要我们保存一份映射关系表，标明哪一段 Key 值对应存在哪台机器上。与一致性 hash 类似，连续范围分区会把 Key 值按连续的范围分段，每段数据会被指定保存在某个节点上，然后会被冗余备份到其他节点。

　　BigTable 的处理方式

　　Google BigTable 论文中描述了一种范围分区方式，它将数据切分成一个个的 tablet 数据块。每个 tablet 保存一定数量的键值对。然后存储在 Tablet 服务器上。tablet 块的大小会保持在一定范围，太大的块会分裂成两个，太小的块又会合并成一个。BigTable 通过一个叫 Chubby 的模块来实现节点状态检测。类似的在 Hadoop 中有一个叫 ZooKeeper 的工具实现此功能。

　　一致性

　　上面讲到了通过将数据冗余存储到不同的节点来保证数据安全和减轻负载，下面我们来看看这样做引发的一个问题：保证数据在多个节点间的一致性是非常困难的。在多个点间保持数据的一致性的问题，也就是本章的主题。下面我们首先来看一下在著名的 CAP 理论。

　　①一致性(C)：在分布式系统中的所有数据备份，在同一时刻是否同样的值。

　　②可用性(A)：在集群中一部分节点故障后，集群整体是否还能响应客户端的读写请求。

　　③分区容忍性(P)：集群中的某些节点在无法联系后，集群整体是否还能继续进行服务。

　　而 CAP 理论就是说在分布式存储系统中，最多只能实现上面的两点。再加之当前的网络硬件肯定会出现延迟丢包等问题，所以分区容忍性是我们必须需要实现的。结果就是我们只能在一致性和可用性之间进行权衡，没有 NoSQL 系统能同时保证这三点。

　　对一致性的保证，通常有强一致性和弱一致性的选择，而在弱一致性里，又以最终一致性的实现较为普遍。

　　如果我们采用 NRW 的设定，N为数据需要备份的份数，R为读操作需要读到的不同节点上的数据份数，W为写操作需要成功写到不同节点的数据份数，那么当R+W>N时，既是强一致性的保证，当R+W

　　写在最后的话

　　目前 NoSQL 系统来处在它的萌芽期，我们上面讨论到的很多 NoSQL 系统，它们的架构、设计和接口可能都会改变。本章的目的，不在于让你了解这些 NoSQL 系统目前是如何工作的，而在于让你理解这些系统之所以这样实现的原因。NoSQL 系统把更多的设计工作留给了应用开发工作者来做。理解上面这些组件的架构，不仅能让你写出下一个 NoSQL 系统，更让你对现有系统应用得更好。