[转]NoSQL数据库的分布式算法

[转]NoSQL数据库的分布式算法 转载一篇很不错的NoSQL数据库分布式算法，内容如下： 本文英文原文发表于知名技术博客《Highly Scalable Blog》，对NoSQL数据库中的 分布式 算法和思想进行了详细的讲解。文章很长，由@juliashine进行翻译投稿。感谢译者的共享

[转]NoSQL数据库的分布式算法

转载一篇很不错的NoSQL数据库分布式算法，内容如下： 

本文英文原文发表于知名技术博客《Highly Scalable Blog》，对NoSQL数据库中的分布式算法和思想进行了详细的讲解。文章很长，由@juliashine 进行翻译投稿。感谢译者的共享精神！

译者介绍：Juliashine是多年抓娃工程师，现工作方向是海量数据处理与分析，关注Hadoop与NoSQL生态体系。

英文原文：《Distributed Algorithms in NoSQL Databases》

译文地址：《NoSQL数据库的分布式算法》

系统的可扩展性是推动NoSQL运动发展的的主要理由，包含了分布式系统协调，故障转移，资源管理和许多其他特性。这么讲使得NoSQL听起来像是一个大筐，什么都能塞进去。尽管NoSQL运动并没有给分布式数据处理带来根本性的技术变革，但是依然引发了铺天盖地的关于各种协议和算法的研究以及实践。正是通过这些尝试逐渐总结出了一些行之有效的数据库构建方法。在这篇文章里，香港服务器租用，我将针对NoSQL数据库的分布式特点进行一些系统化的描述。

接下来我们将研究一些分布式策略，比如故障检测中的复制，这些策略用黑体字标出，被分为三段：

数据一致性

众所周知，分布式系统经常会遇到网络隔离或是延迟的情况，在这种情况下隔离的部分是不可用的，因此要保持高可用性而不牺牲一致性是不可能的。这一事实通常被称作“CAP理论”。然而，一致性在分布式系统中是一个非常昂贵的东西，所以经常需要在这上面做一些让步，不只是针对可用性，还有多种权衡。为了研究这些权衡，我们注意到分布式系统的一致性问题是由数据隔离和复制引起的，免备案空间，所以我们将从研究复制的特点开始：

现在让我们仔细看看常用的复制技术，并按照描述的特点给他们分一下类。第一幅图描绘了不同技术之间的逻辑关系和不同技术在系统的一致性、扩展性、可用性、延迟性之间的权衡坐标。 第二张图详细描绘了每个技术。

复本因子是4。读写协调者可以是一个外部客户端或是一个内部代理节点。

我们会依据一致性从弱到强把所有的技术过一遍：

上面分析中的一些权衡有必要再强调一下：

反熵协议， 谣言传播算法

让我们从以下场景开始：

有许多节点，每条数据会在其中的若干的节点上面存有副本。每个节点都可以单独处理更新请求，每个节点定期和其他节点同步状态，如此一段时间之后所有的副本都会趋向一致。同步过程是怎样进行的？同步何时开始？怎样选择同步的对象？怎么交换数据？我们假定两个节点总是用较新版本的数据覆盖旧的数据或者两个版本都保留以待应用层处理。

这个问题常见于数据一致性维护和集群状态同步（如集群成员信息传播）等场景。虽然引入一个监控数据库并制定同步计划的协调者可以解决这个问题，但是去中心化的数据库能够提供更好的容错性。去中心化的主要做法是利用精心设计的传染协议[7]，这种协议相对简单，但是提供了很好的收敛时间，而且能够容忍任何节点的失效和网络隔离。尽管有许多类型的传染算法，虚拟主机，我们只关注反熵协议，因为NoSQL数据库都在使用它。

反熵协议假定同步会按照一个固定进度表执行，每个节点定期随机或是按照某种规则选择另外一个节点交换数据，消除差异。有三种反风格的反熵协议：推，拉和混合。推协议的原理是简单选取一个随机节点然后把数据状态发送过去。在真实应用中将全部数据都推送出去显然是愚蠢的，所以节点一般按照下图所示的方式工作。

节点A作为同步发起者准备好一份数据摘要，里面包含了A上数据的指纹。节点B接收到摘要之后将摘要中的数据与本地数据进行比较，并将数据差异做成一份摘要返回给A。最后，A发送一个更新给B，B再更新数据。拉方式和混合方式的协议与此类似，就如上图所示的。

反熵协议提供了足够好的收敛时间和扩展性。下图展示了一个在100个节点的集群中传播一个更新的模拟结果。在每次迭代中，每个节点只与一个随机选取的对等节点发生联系。

可以看到，拉方式的收敛性比推方式更好，这可以从理论上得到证明[7]。而且推方式还存在一个“收敛尾巴”的问题。在多次迭代之后，尽管几乎遍历到了所有的节点，但还是有很少的一部分没受到影响。与单纯的推和拉方式相比， 混合方式的效率更高，所以实际应用中通常使用这种方式。反熵是可扩展的，因为平均转换时间以集群规模的对数函数形式增长。

尽管这些技术看起来很简单，仍然有许多研究关注于不同约束条件下反熵协议的性能表现。其中之一通过一种更有效的结构使用网络拓扑来取代随机选取 [10] 。在网络带宽有限的条件下调整传输率或使用先进的规则来选取要同步的数据 [9]。摘要计算也面临挑战，数据库会维护一份最近更新的日志以有助于摘要计算。

最终一致数据类型Eventually Consistent Data Types

在上一节我们假定两个节点总是合并他们的数据版本。但要解决更新冲突并不容易，让所有副本都最终达到一个语义上正确的值出乎意料的难。一个众所周知的例子是Amazon Dynamo数据库[8]中已经删除的条目可以重现。

我们假设一个例子来说明这个问题：数据库维护一个逻辑上的全局计数器，每个节点可以增加或者减少计数。虽然每个节点可以在本地维护一个自己的值，但这些本地计数却不能通过简单的加减来合并。假设这样一个例子：有三个节点A、B和C，每个节点执行了一次加操作。如果A从B获得一个值，并且加到本地副本上，然后C从B获得值，然后C再从A获得值，那么C最后的值是4，而这是错误的。解决这个问题的方法是用一个类似于向量时钟[19]的数据结构为每个节点维护一对计数器[1]：

class Counter { int[] plus int[] minus int NODE_ID increment() { plus[NODE_ID]++ } decrement() { minus[NODE_ID]++ } get() { return sum(plus) – sum(minus) } merge(Counter other) { for i in 1..MAX_ID { plus[i] = max(plus[i], other.plus[i]) minus[i] = max(minus[i], other.minus[i]) } } }

Cassandra用类似的方法计数[11]。利用基于状态的或是基于操作的复制理论也可以设计出更复杂的最终一致的数据结构。例如，[1]中就提及了一系列这样的数据结构，包括：

最终一致数据类型的功能通常是有限的，还会带来额外的性能开销。

数据放置

这部分主要关注控制在分布式数据库中放置数据的算法。这些算法负责把数据项映射到合适的物理节点上，在节点间迁移数据以及像内存这样的资源的全局调配。

均衡数据