3.1 一致性

3.1.1 CAP理论

     在2000年的ACM PODC研讨会上主题为“走向鲁棒的分布式系统”的演示文稿中，Eric Brewer提出了所谓的CAP理论（[ Bre00 ]），它目前在大型网络公司（如Amazon，参见[ Vog07 ]、[ Vog08 ]）以及NoSQL社区中广泛采纳。缩写CAP代表（Gray在[ Gra09 ]中总结）：

     一致性（Consistency）  意思是在一个操作的执行后系统是否和如何保持一个一致的状态。如果经过某个写者的一个更新操作后，所有读者通过某些共享数据源看到该写者的更新，则认为该分布式系统是一致的。（然而有几个对这个严格概念的变通，我们将在下面看到。）

     可用性（Availability）  尤其是高可用性意味着，一个系统以某种方式被设计和实现为允许它继续操作（即允许读写操作）当例如集群中的节点崩溃或一些硬件或软件部件由于升级而关闭。

     分区容错性（Partition Tolerance）  被理解为存在网络分区时系统能继续运作的能力。这发生在两个或更多的网络节点“孤岛”出现（暂时的或永久的）且无法彼此连接。有些人也把分区容错性理解为系统应付动态添加和删除节点的能力（如维修的目的；在这个概念中删除后再添加的节点被认为是一个自己的网络分区；[ Ipp09 ]）。

     现在Brewer称，在一个“共享数据系统”中最多只能选择这三个特性中的两个（参见[ Bre00，幻灯片14 ]）。在他的谈话中，他提到了ACID和BASE系统（见下一节）之间的权衡，并作为选择一个或另一个独立用例的决定标准：如果一个系统或系统的一部分必须是一致的和分区容错的，ACID特性是必需的；如果可用性和分区容错性比一致性更重要，由此产生的系统可以BASE属性来设计特征。后者是Amazon Dynamo的情况（[ DHJ+07 ]），其可用且分区容错，但不严格一致，即一个客户端的写在提交到所有读者后不能被立即看见。Google的Bigtable既不选择ACID也不选择BASE，而是第三种CAP选择即一个一致和可用的系统，因此存在网络分区时不能完全操作。在他的演示文稿中，Brewer指出三种可根据其CAP理论做出的选择的特征和例子（见表3.1）。

表3.1:CAP理论——选择，特征，例子（[ Bre00，幻灯片14-16 ]）

     关于数据库，Brewer认为当前“数据库的一致性比可用性更好”和“广域数据库无法两者兼有”（[ Bre00，幻灯片17 ]）——一个在NoSQL社区广泛采用的概念，且已经影响了非关系型数据存储的设计。

3.1.2 ACID vs. BASE

     互联网以及其维基、博客、社交网络等，创造了一个巨大的和不断增长的需要处理、分析和传输的数据量。提供这一领域的应用或服务的公司、组织和个人，必须确定其特有的性能、可靠性、可用性、一致性和持久性的需求（[ Gra09 ]）。正如上面所讨论的，CAP理论认为在一致性、可用性和分区容错性中只能选择两个。对越来越多的应用和用例来说（包括网络应用，特别是在大和超大型规模网络，甚至在电子商务领域，见[ Vog07 ]、[ Vog08 ]），可用性和分区容错性比严格的一致性更重要。这些应用需要时可靠的，涉及到可用性和冗余（因此在两个或多个节点之间分布是必要的，因为许多系统运行在“廉价的、商品化的和不可靠的”机器上[ Ho09a ]，同时也提供了可扩展性）。这些性质很难用ACID属性实现，因此像BASE这样的方法得以应用（[ Ipp09 ]）。

     根据Brewer，BASE方法牺牲ACID特性中的一致性和隔离性，换取“可用性、优美的退化、和性能”（[ Bre00，幻灯片12 ]）。缩写词BASE由以下特征组成：

     Brewer将ACID与BASE对比如表3.2所示，不过将这两个概念视为一个族谱而不是相互排斥的。Ippolito如下总结BASE的特性：一个应用程序基本上所有的时间工作（基本可用），不必永远一致（软状态），但最终会处于一些已知状态的状态（最终的一致性，参见[ Ipp09 ]）。

表3.2:ACID vs. BASE（[ Bre00，幻灯片13 ]）

     在他的谈话“分布式非关系型数据库的设计模式”中，Todd Lipcon比较了严格与最终一致性。他定义说一个一致性模型——例如严格或最终一致性——“为更新的可见性和表象顺序确定规则”。Lipcon和Brewer一样，将一致性看作“带权衡的连续性”，并如下描述严格和最终一致性（[ Lip09，幻灯片14-16）：

     严格一致性  根据Lipcon这意味着“所有的读操作必须从最新完成的写操作返回数据，不管操作去了哪个副本”。这意味着对于一个给定的数据集，读或写操作必须在同一节点执行，或由分布式事务协议（如两阶段提交或Paxos）保证的严格一致性。正如我们所看到的，根据CAP理论，这样的严格一致性无法与可用性和分区容错性同时达到。

     最终一致性  意味着随着时间的推移读者会看到写：“在一个稳定的状态，系统最终将返回最后写的值”。因此，更新正在进行中时客户可能面临数据不一致的状态。例如，在一个有副本的数据库中，更新操作可能会先在一个有最新版本副本的节点发生，然后到其它含有被修改数据集其它副本的节点，因此各副本节点最终将有最新版本。

     Lipcon和Ho指出，最终一致性的系统可以对其客户提供更多差异化的、额外的保证（参见[ Lip09，幻灯片16 ]，[ Ho09a ]）：

     读自身写（RYOW）一致性  表示一个客户端在他的更新发布和完成后立即看到，哪怕他写到一个服务器，但接下去从不同的服务器读。其他客户端的更新不是立即可见的。

     Session一致性  意味着被限制在一个session范围内的读自身写一致性（通常是绑定到一个服务器），因此一个客户端立即看到他的更新，仅当更新发布后的读请求位于同一个session的范围内。

     临时一致性  表示，如果一个客户端读取版本x并随后写入版本y，任何客户读版本y也会看到版本x。

     单调读一致性  提供时间单调性的保证，客户端只会在未来的请求中看到数据的被更新更多次的版本。

     Ho评论，如果对同分区数据的并发更新是不可能的，且如果客户端不立即依赖于读取自身或其它客户发布的更新，则最终一致性是有用的（ [Ho09a] ）。他进一步说，为系统（或系统的一部分）选择的一致性模型，关系到客户端的请求如何被分派到副本上，以及副本如何传递和应用更新。

3.1.3 分布式场景下的数据集版本控制

     如果数据集在节点间分布，他们可以在每个节点上被读取和改变，且没有由分布式事务协议确保的严格一致性，问题出现了，“并发的”修改和版本是如何处理的，且数据集最终将收敛到何值。有几个选项处理这些问题：

     时间戳  对制定一个按时间排列的顺序而言似乎是一个明显的解决方案。然而，时间戳“依赖于时钟同步且不捕获因果关系”，Lipcon指出（[ Lip09，幻灯片17 ]；一个更根本的、彻底的对这些问题的讨论见[ Mat89 ]）。

     乐观锁  意味着为每个数据保存一个唯一的计数器或时钟值。当一个客户端尝试更新一个数据集，它必须提供它想要更新的计数器/时钟值的修订（[ K+10b ]）。作为这个过程的一个缺点，Project Voldemort的开发团队注意到它在分布的和动态的场景下工作得不好，这种场景服务器经常启动和关闭且不事先通知。为允许版本上的因果推理（如更新提交的节点上哪个修订被认为是最近的），大量历史信息必须被保存、保持和处理，因为乐观锁方案需要一个版本号的总的顺序以使因果推理成为可能。在分布式和动态的节点设置下这样的总顺序很容易被破坏，Project Voldemort团队认为。

     向量锁  是一种捕获顺序的替代方法，并允许在分布式系统内的更新之间推理。他们在下面更详细地解释。

     多版本存储  意为为每个表单元格存储一个时间戳。这些时间戳“不一定需要与现实生活相关“，而可以是一些有特定顺序的人工值。对于一个给定的行，多个版本可以同时存在。除了最近的版本，读者也可以请求“T前最新”的版本。这提供了“带时间戳上的比较和交换操作的乐观并发控制”，也允许为数据集获取快照（[ Lip09，幻灯片20 ]）。

向量锁

     一个向量时钟定义为一个来自每个节点的时钟值的元组V[0]，V[1]，…，V[n]（[ Lip09，幻灯片18）。在一个分布式场景节下，节点i维护这样一个时钟值的元组，代表该节点在一个特定时间感知到的自身和其他（副本）节点的状态（第节点的时钟值为Vi[0]，第二个节点的时钟值为Vi[1]，……，自己为Vi[i]，最后一个节点的时钟值为Vi[n]）。时钟值可能是来自一个节点的本地时钟的真实的时间戳、版本/修订数字或其他可排序的值。

     作为例子，2号节点的向量时钟可能接收到如下的值：

     V2[0]=45, V2[1]=3, V2[2]=55

图3.1:向量时钟（来自[ Ho09a ]）

     这反映了从2号节点的角度来看，以下更新发生于数据集，此时向量时钟指：1号节点上的更新产生修订3，0号节点的更新产生修订45，最新的更新发生在2号节点本身，产生修订55。

     向量时钟的更新通过如下规则定义（[ Ho09a ]、[ K+10b ]）：

          Vi=max(Vi, Vmessage)

          为比较两个向量时钟Vi和Vj以得到部分排序，以下规则被应用：

          Vi>Vj, if  ∀k Vi[k]>Vj[k]

          如果Vi>Vj或Vi<Vj都不成立，则因并发更新导致的冲突发生，需要由如客户端程序解决。

     可见，向量时钟可被利用“解决写多个副本之间的一致性”（ [ Lip09，幻灯片18 ]），因为它们允许更新之间的因果推理。副本节点通常不维护客户端的 向量时钟，但客户端以如下的方式参与到向量时钟方案中： 他们维护了他们 最后 联络过 的副本节点的向量时钟 ，并以客户端一致性模型需要的方式使用这个向量时钟； 例如单调读一致性，客户端将接收到的最后的向量时钟附加在请求上 ，与其接触的副本节点确保响应的向量时钟 大于客户端提交的向量时钟。这意味着 可以肯定 客户端 只看到较新版本的数据（与它已经看到的版本相比“较新”  [ Ho09a ]）。

     相比上述其余方法（时间戳、带修订数字的乐观锁、多版本存储），向量时钟的优点是：

向量时钟用于通过Gossip协议传播状态

     博主Ricky Ho给出了一个关于向量时钟如何用于处理一致性、冲突版本和分区数据库中副本间转移状态的概述（会在下一节中讨论）。他描述了客户端和数据库节点间以及后者相互之间传输向量时钟是通过Gossip协议，其可作用于一个状态或一个操作传输模型来处理读和更新操作、以及在数据库节点间复制操作（[ Ho09a ]）。对于通过Gossip协议的节点间传播，Todd Lipcon指出该方法提供了可扩展性并避免了单点故障（SPOF）。然而，因为一个n节点的集群中状态信息需要O(log n)轮传播，只有最终一致性可以达到（[ Lip09，幻灯片34）。

     状态传输模型  在状态传输模型中数据或数据的变化量在客户端和服务器以及服务器之间交换。在这个模型中，数据库服务器节点为他们的数据维护向量时钟，也为冲突的版本（即对应的向量时钟不能满足Va＜Vb或Va＞Vb关系的版本）维护状态版本树；客户端也为他们已请求或更新的数据维护向量时钟。这些以如下的方式交流和处理：

     查询处理  当一个客户端查询数据时，它将请求数据的向量时钟和请求一起发送。数据库服务器节点用先于客户端请求上附带的向量时钟的那些数据的部分状态树（以保证单调读一致性）和服务器的向量时钟来作为响应。接下来，客户端增加其向量时钟，通过合并自身的向量时钟和服务器响应上附带的向量时钟。对于这一步，客户端还必须解决潜在的版本冲突；Ho指出这是必要的，因为如果客户在读时并没有解决冲突，可能会导致他对一个过时的数据修订（与接触的副本节点上维护的数据修订相比）操作或提交更新。

     更新处理  类似读取请求的情况，客户端还必在更新请求须附上被更新数据的向量时钟。接触的副本服务器然后检查，如果根据所发送的向量时钟客户端的状态先于当前服务器状态，则忽略更新请求（因为客户已获取了最新版本，并在读时解决了版本冲突——如前一段所述）；如果客户端传输的向量时钟比服务器自己的更大，则服务器执行更新请求。

     节点间Gossiping  副本负责相同分区的数据在后台交换他们的向量时钟和版本树，并尝试合并它们以保持同步。

     图3.2描述了在状态传输模型中通过Gossip协议的消息交换，以及它们是如何被接收方处理的，如刚才描述的。

图3.2：向量时钟——在状态传输模型中使用Gossip协议交换（来自[ Ho09a ]）

     操作传输模型  与上述讨论的状态传输模型相反，在操作传输模型中，可用于本地维护数据的操作在节点间通信。此过程一个明显的优点是，与交换实际数据或数据的变化量相比，交换操作消耗的带宽较小。在操作传输模型里，特别重要的是以正确的顺序将操作应用在每个节点上。因此，副本节点在将它们应用到数据之前，首先要确定一个临时的操作间关系（通过向量时钟比较）。其次，它必须将操作的应用推迟到所有先前的操作已被执行之后；这意味着维护一个需要与其它副本交换和合并的递延操作的队列（如我们将在下面看到）。在这个模型中，一个副本节点维护以下向量时钟（[ Ho09a ]）：

     在操作传输模型中，以如下方式交换和处理读消息、更新消息、节点间消息的向量时钟：

     查询处理  在一个读请求中，一个客户端再次附上他的向量时钟。接触的副本节点确定客户端请求中是否具有一个和已提交视图因果跟随的视图。它以状态的最新视图进行响应，即或者是客户端附带的向量时钟所对应的状态，或者是该节点自身因果后续的向量时钟所对应的状态。

     更新处理  当一个客户端提交一个更新请求时，所接触的副本节点缓存该更新操作直到它可以应用到它的本地状态，考虑到他维护的三个向量时钟（见上面）和已缓存操作的队列。缓存的更新操作被两个向量时钟标记：Vclient代表提交更新时的客户视图，和Vreceived代表收到更新时的副本节点视图（即上面提到的向量时钟Vi）。当所有在因果上先于已收到的更新操作的其他操作都到达并被应用后，客户端所请求的更新可以执行。

     节点间Gossiping  在操作传输模型中，副本节点交换他们的等待操作队列并更新彼此的向量时钟。当节点交换了他们的操作队列后，他们决定在这些队列中的特定操作是否可以被应用（因所有相关的操作已经收到）。如果一次可执行多个操作，该副本节点将这些操作排列为正确的（因果的）顺序，其由这些请求携带的向量时钟确定，并将操作应用到该节点数据的本地状态。在不同副本上的并发更新的情况下——导致同一时间有多个操作队列——必须有一个下列情况间的区别：

     1、并发更新是可交换的，所以它们应用的顺序不重要。

     2、并发更新是不可交换的。在这种情况下，由比较向量时钟推出的部分排序是不足够的，必须确定一个总的顺序。为实现这个，Ho提出从中央计数器得到的全局序列号的引入：“第一个更新者首先获得一个单调的序列号，后来者跟随这一序列”（[ Ho09a ]）。

     当一个操作被应用到副本的本地时，仅当所有其他副本节点被通知该更新的执行后，它们可从节点的操作队列中移除。

     图3.3显示了在操作传输模型中通过Gossip协议的消息交换和处理，以查询、更新和节点间的通信为例。

图3.3:向量时钟——在操作传输模型中使用Gossip协议交换（来自[ Ho09a ]）

3.2 分区

     假设在大型系统中的数据超过一台机器的容量，也应该被复制以确保可靠性和允许缩放措施如负载均衡，这样一个系统中数据分区的方式必须考虑。根据系统的大小和其他因素如动态性（例如，存储节点可能的加入和离开有多频繁和动态），对该问题有不同的方法：

     内存缓存  类似memcached（[ F+10A ]、[ F+10b ]）可以被看作是分区的——虽然短暂——内存数据库，因为它们将最经常被请求的部分数据库复制到主内存，快速提供这些数据给客户端，因此显著为数据库服务器减负。在memcached的情况下，内存缓存由分配了一定量内存的一个进程队列组成，其可在网络的数台机器上被运行并通过配置使其对应用程序可见。memcached协议（[ F+10c ]）的实现在不同的编程语言是可用的（[ F+09 ]），可用于在客户端应用程序中提供一个简单的键/值存储API。它存储以一个键放入缓存的对象，通过将键哈希到配置的memcached实例上。如果一个memcached进程不回应，多数API的实现忽略非应答节点并使用响应节点替代，这将导致缓存对象的隐式重哈希，即缓存未命中后他们的一部分被哈希到不同的memcached服务器；当原非应答节点再次加入memcached服务器阵列，缓存未命中后一部分数据的键再次被哈希到这个实例上，且当该节点挂掉时，现在只属于该节点的对象将隐式地离开他们被哈希到的其它memcached服务器的内存（因为memcached对缓存清除应用LRU策略而且允许对缓存的对象指定超时）。其他内存缓存的实现也可用，例如应用服务器像JBoss等（[ Jbo10b ]）。

     集群  数据库服务器的集群是另一种对数据分区的方法，该方法力求对客户透明，客户不应该注意到一个数据库服务器集群而是单个服务器。虽然这种方法有助于一定程度上扩展一个系统的持久层，很多人批评集群特性只被添加到了原本不是为分布式设计的DBMS的上层（参阅Stonebraker等人的评论，2.1.2节）。

     读写分离  意为指定一个或多个专用服务器（主），所有或部分数据的写操作路由到其上，以及大量副本服务器（从）用鱼满足读操作。如果主异步地复制到它的客户端则没有写延迟，但如果在完成复制到至少一个客户端的操作过程中主节点崩溃，则写操作丢失；如果主同步地复制到它的客户端则写更新不会丢失，但如果要求严格一致性则读请求不能发到任一从节点，且写延迟无法避免（参见[ Ho09a ]以及StudiVz的Dennis Bemmann关于写延迟的评论[ Bem10 ]）。在后者的情况下，如果主崩溃，有最新版本的数据的从节点可以被选为新的主。如果读/写比高，主/从模型的工作效果良好。数据的复制可以通过状态传输（即拷贝最近版本的数据或与前一版本之间的变化量），或操作传输，其将被应用到从节点的状态上并以正确的顺序到达（[ Ho09a ]）。

     分片  意为如下分区数据，典型地数据的请求和更新一起发生在同一节点上，且服务器间的负载和存储量大致平均分布（与它们的存储容量和处理能力有关；如Bemmann关于德国一家大型社交网络的经验[ Bem10 ]）。数据分片也可能因可靠性和负载均衡的原因被复制，它可能被允许写到一个专用的副本上或所有副本维护一个分区的数据。为允许这样一个分片的场景，需要有数据分区（片）和负责这些片的存储节点之间的映射。这个映射可以是静态的或动态的，由客户端应用确定

，由一些专门的“映射服务/组件”或由一些客户端应用和存储节点间的网络基础设施组成。分片方案的缺点是，数据片之间的连接是不可能的，因此客户端应用程序或数据库内部或外部的代理层必须发出一些请求和用结果的后置处理（如过滤、聚合）来替代。因此Lipcon评论，有了分片后“你会失去所有使一个RDBMS有用的功能”且分片是“操作上讨厌的”（[ Lip09 ]）。这种评估依据的是分片原来并不是设计在当前的RDBMS内而是其上的补充的事实。相比之下许多NoSQL数据库已经植入分片作为一个重要特征，有些甚至提供了自动分区和节点间的数据平衡，例如MongoDB版本1.6（[ MHC+10b ]，[ Mon10 ]）。

     在一个分区场景下，知道如何将数据库对象映射到服务器是关键。一个明显的方法是以如下方式，对数据库对象主键和可用的数据库节点做简单哈希：

     partition=hash(o) mod n    o=哈希的对象, n=节点数

     正如上面提到的这一过程的缺点是，当节点离开和加入时至少一部分数据必须重新分布。在内存缓存场景中，数据重新分布可能隐式发生在观察到缓存未命中、再次从数据库或后端系统中读取数据、对其和目前可用的缓存服务器进行哈希、以及让陈旧的缓存数据被从缓存服务器清除的策略如LRU。但对于持久性的数据存储这种隐式重分布过程是不可接受的，因为不在可用的节点上的数据不能被重建（[ Ho09a ]、[ Whi07 ]）。因此，一个节点可能在运行时加入和离开的环境下（例如由于节点崩溃、临时不可达、维护工作），不同的方法如一致性哈希方法必须被发现，这将在此后讨论。

3.2.1 一致性哈希

     一致性哈希的主意是由David Karger等人1997年（[ KLL+97 ]）在一篇关于“一族分布式网络的缓存协议，可用于减少或消除网络中出现的热点问题”的论文中提出的。这个缓存协议族基于一致性哈希，其从1997以来已在除缓存网络协议外的其他领域采用，例如，Chord的分布式哈希表实现（[ Par09 ]），一些memcached客户端，以及NoSQL的场景，如它已经被集成到数据库如Amazon的Dynamo和Project Voldemort。

     “一致性哈希算法背后的基本思想是对对象和缓存使用相同的哈希函数”，博主Tom White指出。不仅哈希对象，机器也能利用其优点，即机器得到哈希函数的范围的一个区间，相邻的机器可以接管其邻居的一部分区间如果其邻居离开，也可以抛弃他们自己的一部分区间如果新节点加入且映射到相邻的区间。一致性哈希方法进一步的优点是，客户端应用程序可以计算出联系哪个节点以请求或写一块数据，且不必须有元数据服务器，如谷歌文件系统（GFS）有这样一个中心化的（虽然是集群）元数据服务器，它包含存储服务器和数据分区（在GFS中称为chunk；见[ GL03，页2 ]）之间的映射关系。

     图3.4和3.5说明了一致性哈希方法背后的思想。在图3.4中有三个红色的节点A、B、C，和四个蓝色的对象1-4分别映射到一个哈希函数的值域，其被想象并画为一个环。哪个对象映射到哪个节点通过顺时针绕环移动决定。因此，对象4和1被映射到节点A，对象2到节点B，对象3到节点C。当一个节点离开系统时，缓存对象将映射到它们的相邻节点（顺时针方向）；当一个节点进入系统，它会哈希到环上并获取对象。图3.5中所示的一个例子，与图3.4比较，节点C离开且节点D进入了系统，所以现在对象3和4将被映射到节点D。这表明，通过改变节点编号，并非所有的对象都需要被映射到新的节点集合，而是只有一部分的对象需要。

图3.4：一致性哈希——初始状态（来自[ Whi07 ]）

图3.5：一致性哈希——节点加入或离开后的状态（来自[ Whi07 ]）

     在此过程中仍有问题：首先，环上的节点分布其实是随机的，因为它们的位置由一个哈希函数确定且节点之间的间隔可能是“不平衡”的，这反过来又导致在这些节点上的缓存对象的不平衡分布（如图3.5中可见，节点D需要以一个比节点A甚至节点B更大的间隔来获取缓存对象）。解决这个问题的一个方法是哈希一些代表/副本——也称为虚拟节点——为环上的每个物理节点（参见[ Whi07 ]，作为一个例子可见图3.6）。一个物理节点的虚拟节点数目可以单独根据它的硬件容量（CPU、内存、磁盘容量）来定义，不必对所有物理节点都相同。通过添加如副本计数器到节点的id，然后计算哈希，这些虚拟节点将使代表该物理节点的点在整个环上分布。

     在他的一致性哈希的博文中，Tom White模拟了添加虚拟节点的影响，他将10000个对象分布在10个物理节点上。结果是，对象分布的标准差可以从没有虚拟节点的100%下降到每个物理节点2-5个虚拟节点的50%，每个物理节点500个虚拟节点的5–10%（[ Whi07 ]）。

     当应用于持久性存储，进一步的问题是：如果一个节点已经离开现场，存储在该节点的数据变得不可用，除非它之前已被复制到其他节点；在相反的情况下新节点接入，相邻节点不再负责一些他们仍储存但不会再被请求的数据，因为对请求客户而言相应的对象不再被哈希到这些节点上。为了解决这个问题，一个复本因子（r）被引入。这样做，不仅下一个节点，而是下r个顺时针方向的（物理！）节点负责某个对象（[ K+10b ]、[ Ho09a ]）。图3.7描述了这样一个带副本数据的场景：大写字母再次代表存储节点——根据虚拟节点的思想——将被多次映射到环上，带箭头的圆表示映射到该环上图示位置的数据对象。在这个例子中，副本因子是3，所以对每个数据对象有3个物理节点（图中方括号中列出的）负责它。副本的引入关系到数据分区的读写操作，将在下一个小节中考虑。上述造成成员变化的问题在此后讨论。

图3.6：一致性哈希——虚拟节点的例子（来自[ Lip09，幻灯片12 ]）

图3.7：一致性哈希——虚拟节点和副本数据的例子（来自[ K+10b ]）

3.2.2 分区数据上的读写操作

     在分区方案里引入副本后——除了可靠性的好处——也使得它可以传播读请求的工作负载，可以去任何一个负责被请求数据的物理节点。在资格上，应说明的是，负载均衡读取操作的可能性不适用于这类场景：客户端必须在一个数据集的多个版本中做决定，因此必须从一个法定数量的服务器中读，这反过来又降低了负载均衡的读请求的能力。Project Voldemort小组指出，关于读或写操作三个参数是特别重要的（[ K+10b ]）：

     N  需要读取或写入的数据或数据块的副本数量。

     R  读操作中通信的机器数量。

     W  必须在写操作中被阻塞的机器的数量。

     为了提供如读自己写一致性模型，以上参数间的以下关系是必须的：

          R+W>N

     关于写操作，客户端必须清楚，这些既不是立即一致的，也不是独立的（[ K+10b ]）：

3.2.3 成员变化

     在一个分区的数据库中，节点可以在任何时间加入和离开系统而不影响其操作，所有节点间必须相互通信，特别是当成员变化时。

     当一个新的节点加入系统，以下行动必须发生（[ Ho09a ]）：

     1、新到达的节点通过广播宣布它的存在和它的标识符到相邻的节点或所有节点。

     2、新节点的邻居调整对象和副本归属。

     3、新节点从它的邻居拷贝它现在负责的数据集。这可以批量和异步地执行。

     4、如果在步骤1中，成员变化没有被广播到所有节点，新节点现在宣布它的到达。

     在图3.8中，这个过程被说明。节点X加入一个系统，其配置的副本因子为3。它被哈希到A和B之间，因此节点H、A和B传输数据到新节点X，之后节点B、C和D可以丢弃节点X现在作为第三副本负责的那部分数据（除了节点H、A和B）。

图3.8：成员变化——节点X加入系统（来自[ Ho09a ]）

     Ho指出，当数据传输和范围调整发生在步骤2和3，新节点的相邻节点可能仍然被请求，此时可以将它们转发到新节点。如果新节点已经收到了请求的数据块，或可以将向量时钟发送给客户端，让它们在接触多个副本后确定最新版本的数据集，就是这种情况。

     当一个节点离开系统，以下行动必须发生（[ Ho09a ]）：

     1、系统中的节点需要检测一个节点是否已经离开，因为它可能已经崩溃且不能把它的离开通知其他节点。这在许多系统中也是常见的，当节点离开时没有通知被交换。如果系统的节点定期通信如通过Gossip协议，他们能够检测到一个节点的离开，因为它不再回应。

     2、如果节点的离开被检测到，节点的邻居必须反应，通过互相交换数据以及调整对象和副本归属。

     图3.9显示当节点B——因为崩溃——离开系统时应做的操作。节点C、D和E开始负责新的一段间隔的散列对象，因此需要从逆时针方向的节点复制数据，并重新调整其间隔的内部表示，因为RangeAB和RangeBC现在已经合并为RangeAC。

图3.9：成员变化——节点B离开系统（来自[ Ho09a ]）

3.3 存储布局

     在他的非关系型数据库设计模式的谈话中，Todd Lipcon给出了一个存储布局的概述，其决定磁盘是如何访问的且因此直接影响性能。此外，存储布局定义了哪些数据（例如整行、整列、列的子集）可以以块的方式读取（参见[ Lip09，幻灯片21–31 ]）。

     基于行的存储布局  意味着一个关系模型的表被以行的方式追加和刷新到磁盘来序列化（见图3.10a）。这种存储布局的优点是，首先整个数据集可以在一个单一的IO操作中被读写，其次具有 “不同列上的好的访问（在磁盘上或内存中）本地性”。缺点是，列的操作是昂贵的，因为大量数据（在幼稚的实现中可能是全部数据）需要被读取。

     列式存储布局  通过对列追加和刷新到磁盘的方式来序列化表（见图3.10b）。因此，在列上的操作是快速和廉价的，而行的操作是昂贵的，且可能导致查找很多或所有的列。这种存储布局类型的典型应用领域是分析，该领域内为统计目的在列上做高效检查非常重要。

     带本地性组的列式存储布局  类似于基于列的存储，但增加了定义所谓本地性组的特性，其是一组预期将在一起被客户访问的列。这样的一组列可能因此被存储在一起，与其他的列和列组从物理上分离（见图3.10c）。本地性组的思想在Google的Bigtable论文中被引入。首先，它对语义上仿射或相关的列描述了列族的逻辑模型（[ CDG+06，2节]），其次提出了本地性组的思想作为一种完善，其列族可为物理存储而被聚合或分离（[ CDG+06，6节 ]）。

图3.10：存储布局——基于行，列式不带/带有本地性组（来自[ Lip09，幻灯片22-24 ]）

     日志结构归并树（LSM树）  与之前描述的存储布局相反，日志结构归并树不描述如何序列化逻辑数据结构（如表、文档等），而是如何有效地使用内存和磁盘存储以高效、高性能、安全地满足读写请求。该想法由O'Neil等人1996年提出（[ OCGO96 ]），是将数据成块保存在内存中（在所谓的Memtables），为这些内存数据结构维护盘上提交日志，以及不时地将Memtables刷写到磁盘中所谓的SSTables（见图3.11a和3.11e）。这些SSTables是不可改变的，并且随着时间的推移压缩，当保留原始的SSTables时复制被压缩的SSTables到磁盘的另一个区域，并在压缩进程发生后移除较早的数据（参见图3.11f）。压缩是必要的因为在SSTable中存储的数据可能已经被客户改变或删除。这些数据修改首先体现在Memtable内，之后被作为一个整体刷写到磁盘中的SSTable，其可能连同已在磁盘上的其他SSTables一起被压缩。读请求带着请求的数据去Memtable和SSTables中，并返回一个合并的视图（见图3.11b）。为优化读取请求相关的SSTables布隆过滤器可被使用（见图3.11c）。写请求去Memtable中并同步地写一个盘上的提交日志（见图3.11d）。

图3.11：存储布局—— 日志结构归并树（来自[ Lip09，幻灯片26-31 ]）

     日志结构归并树的优点是，可以利用内存来快速的满足读请求，且磁盘I/O加快因为SSTables可以顺序读取数据因其数据不是随机分布在磁盘上的。LSM树也容忍机器故障，因为写操作不仅去内存，而是也（同步地）进入提交日志，因此机器可以从崩溃中恢复。日志结构归并树在如Google的Bigtable中实现（[ CDG+06，节4，5.3，5.4，6 ]），如博主Ricky Ho用图3.12总结的。

图3.12：存储布局—— Bigtable中的Memtables和SSTables（来自[ Ho09a ]）

     考虑盘上或内存中存储或两者组合（如在LSM树）的讨论，博主Nati Shalom指出它“主要归结为数据的每GB成本和读/写性能”。他引用斯坦福大学的分析（题为“RAMCloud的案例”，参见[ OAE+10 ]）得出的结论是“成本也是一个性能的函数”。他引用了这一分析“如果一个应用程序需要存储大量的数据，并且具有较低的访问率，RAMCloud不是最好的解决方案”，但“对高吞吐量需求的系统需要，RAMCloud可以提供的不仅是高性能更是节能”（[ Sha09a ]）。

     博主Ricky Ho在上述存储布局的分类上补充，一些NoSQL数据库将存储实现留作开放式的，允许插入不同类型的插件——如Project Voldemort允许使用如关系数据库、键/值数据库BerkleyDB、文件系统或内存哈希表来作为存储实现。相反，大多数NoSQL数据库实现了针对其具体特点进行了优化的存储系统。

     除了这些一般的存储布局，以及可插拔的和专有的存储实现之间的区别，大多数数据库根据其特定的数据模型、查询处理手段、索引结构等进行优化。

     作为一个例子，文档数据库CouchDB提供一种修改时复制的语义与一个为存放数据库内容的只追加文件的组合（[ Apa10b，节“ACID属性”]）。修改时复制语义指为用户发出的对数据和索引（CouchDB中为B树）的修改请求保存一份私有拷贝；这允许CouchDB为发起者提供读自身写的一致性，而修改只是最终被其他客户端看到。这个私有拷贝传播到副本节点——因为CouchDB还支持多版本并发控制（MVCC）——也许客户端必须合并冲突的版本在新版本变为对所有客户端有效前（这是由交换存储元数据（以B树方式组织）的根指针实现的，如图3.13所示）。CouchDB同步地将所有更新以只追加方式持久化到硬盘。垃圾收集不时地压缩持久化的数据，通过复制压缩文件的内容到一个新的文件而不touch旧文件，直到新文件被正确写入。这种方式允许垃圾回收执行时系统连续操作。

     Ho描绘了CouchDB索引和文件被更新时的影响，如图3.13所示。

图3.13:存储布局—— CouchDB中的修改时复制（来自[ Ho09a ]）

3.4 查询模型

     如博主Nati Shalom指出，不同NoSQL数据存储提供的查询能力有本质的不同（[ Sha09a ]）：鉴于键/值存储的设计往往只提供了通过主键或id字段的查找，缺乏查询其他字段的能力，其他数据存储如文档数据库CouchDB和MongoDB允许复杂的查询——至少是在数据库节点上预定义的静态查询（如CouchDB）。这并不奇怪，因为在很多NoSQL数据库的设计中，丰富的动态查询功能为性能和可扩展性而被省略了。另一方面，当使用NoSQL数据库时，有这样的用例至少需要非主键属性上的一些查询功能。在他的博客“NoSQL数据库的查询处理”中，博主Ricky Ho阐述了这个问题，并提出了几种实现NoSQL数据范畴中查询功能的方法：

     同伴SQL数据库  是一种将可搜索的属性复制到SQL或文本数据库的方法。该数据库的查询功能是用来检索匹配的数据集的主键，通过这些主键NoSQL数据库随后将被访问（见图3.14）。

图3.14：查询模型——同伴SQL数据库（来自[ Ho09b ]）

     分散/聚集本地搜索  可被使用如果NoSQL存储允许数据库服务器节点内的查询和索引。如果是这样的话，查询处理器可以向数据库节点发送查询，查询在节点本地执行。从所有数据库服务器返回的结果被发送回查询处理器做后续处理，如做一些聚集并将结果返回给发出查询的客户端（见图3.15）。

图3.15：查询模型——分散/聚集本地搜索（来自[ Ho09b ]）

     分布式B+树  另一种实现查询功能的选择（参见图3.16）。基本思想是哈希可搜索属性来定位一个分布式B+树的根节点（进一步的关于可扩展的、分布式的B+树的信息，可以在一个微软、惠普和多伦多大学的论文中找到，参见[ AGS08 ]）。这个根节点的“值”包含B+树上一个子节点的id，使其可以被再次查找。这个过程被重复直到到达一个叶节点，其包含匹配搜索条件的NoSQL数据库的主键或id。Ho注意到，分布式B+树中的节点更新（由于拆分和合并）必须谨慎处理，且应该用原子方式来处理。

图3.16：查询模型——分布式B+树（来自[ Ho09b ]）

     前缀哈希表（也叫分布式Trie树）  是一个树的数据结构，其中每一个从根节点到叶节点的路径包含键的前缀，且每一个Trie树上的节点包含键是以其为前缀的所有数据（详情参见关于此数据结构的伯克利论文[ RRHS04 ]）。除了插图（见图3.17），Ho在他的博客中提供一些代码片段描述了如何操作前缀哈希表/分布式Trie树，以及如何使用它们来达到查询的目的（[ Ho09b ]）。

图3.17：查询模型——前缀哈希表/分布式Trie树（来自[ Ho09b ]）

     Ho进一步指出，在涉及分布式的查询方法中（分散/聚集本地搜索，分布式B+树），搜索条件里的连接必须明确地解说：

     OR连接  很简单，因为来自不同数据库节点的搜索结果可以通过union操作放在一起。

     AND连接  更困难，因为独立匹配条件的交集被期望，因此，需要有效的方式对潜在的大集合求交。幼稚的实现可能将所有匹配的对象发送到执行集合求交的服务器上（例如初始化分布式查询的处理器，如图3.14 - 3.16）。然而，这涉及到大的带宽消耗，如果一些或所有的数据集很大。一些更有效的方法在Reynolds和Vahdat的一篇论文中描述（[ RV03 ]）：

3.5 通过MapReduce的分布式数据处理

     上一节通过集中考察动态查询机制来关注分布式环境下如何进行操作。虽然没有缺乏查询与维护功能的替代方案（如Brian Aker正确且幽默地在“你的NoSQL引导”文中评论的），但某种程度上相关的方案是用一种MapReduce方式来操作分布式数据库节点。这种方法，由谷歌员工2004年提出（[ DG04 ]），将一个任务分为两个阶段，由函数map和reduce描述。在第一阶段，一个协调者指定需要处理的数据分片，一些节点执行一个给定的map函数并产生中间输出。下一步，中间输出被一些执行给定的reduce函数的机器处理，其目的是从中间结果创建最终的输出，例如通过某些聚合。Map和reduce函数都必须以一个真正的函数性的方式被理解，所以他们不依赖于执行机器上的一些状态， 因此在每个执行环境中，给定相同的输入数据，总产生相同的输出。原始数据的分区以及中间数据的分配是由协调者完成的，根据谷歌的原始论文。

     图3.18展示和总结了处理分布式数据的MapReduce方式。

图3.18：MapReduce——执行概览（来自[ DG04，页3 ]）

     MapReduce范式已经被许多编程语言（如Python）、框架（如Apache Hadoop）、甚至JavaScript工具包（如Dojo）和NoSQL数据库（如CouchDB）所采用。 这是因为它适合分布式处理，如博主Ricky Ho指出的（[ Ho09a ]），特别是对分析目的或预计算任务（例如CouchDB生成的数据视图，参见[ Apa10b ]）。当应用到数据库，MapReduce意为处理一组键，通过提交处理逻辑（map和reduce函数代码）到存储节点，在存储节点本地对他们拥有且应被处理的键执行map操作。中间结果可以像正常数据一样进行一致性哈希，并被顺时针方向的后续节点处理，即在中间结果上应用reduce函数并产生最终结果。应指出的是，通过中间结果的一致性哈希，使得无需协调者来告诉处理节点在哪里找到他们。

     在分布式数据存储上应用MapReduce的概念如图3.19所示。

图3.19：MapReduce——在分布式存储节点上执行（来自[ Ho09a ]）