NoSQL数据库的分布式算法

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

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

• 数据一致性。NoSQL需要在分布式系统的一致性，容错性和性能，低延迟及高可用之间作出权衡，一般来说，数据一致性是一个必选项，所以这一节主要是关于数据复制和数据恢复。
• 数据放置。一个数据库产品应该能够应对不同的数据分布，集群拓扑和硬件配置。在这一节我们将讨论如何分布以及调整数据分布才能够能够及时解决故障，提供持久化保证，高效查询和保证集群中的资源（如内存和硬盘空间）得到均衡使用。
• 对等系统。像?leader election?这样的的技术已经被用于多个数据库产品以实现容错和数据强一致性。然而，即使是分散的的数据库（无中心）也要跟踪它们的全局状态，检测故障和拓扑变化。这一节将介绍几种使系统保持一致状态的技术。

数据一致性

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

• 可用性。在网络隔离的情况下剩余部分仍然可以应对读写请求。
• 读写延迟。读写请求能够在短时间内处理。
• 读写延展性。读写的压力可由多个节点均衡分担。
• 容错性。对于读写请求的处理不依赖于任何一个特定节点。
• 数据持久性。特定条件下的节点故障不会造成数据丢失。
• 一致性。一致性比前面几个特性都要复杂得多，我们需要详细讨论一下几种不同的观点。 但是我们不会涉及过多的一致性理论和并发模型，因为这已经超出了本文的范畴，我只会使用一些简单特点构成的精简体系。
  • 读写一致性。从读写的观点来看，数据库的基本目标是使副本趋同的时间尽可能短（即更新传递到所有副本的时间），保证最终一致性。除了这个较弱的保证，还有一些更强的一致性特点：
    • 写后读一致性。在数据项X上写操作的效果总是能够被后续的X上的读操作看见。
    • 读后读一致性。在一次对数据项X的读操作之后，后续对X的读操作应该返回与第一次的返回值相同或是更加新的值。
  • 写一致性。分区的数据库经常会发生写冲突。数据库应当能处理这种冲突并保证多个写请求不会被不同的分区所处理。这方面数据库提供了几种不同的一致性模型：
    • 原子写。假如数据库提供了API，一次写操作只能是一个单独的原子性的赋值，避免写冲突的办法是找出每个数据的“最新版本”。这使得所有的节点都 能够在更新结束时获得同一版本，而与更新的顺序无关，网络故障和延迟经常造成各节点更新顺序不一致。 数据版本可以用时间戳或是用户指定的值来表示。Cassandra用的就是这种方法。
    • 原子化的读-改-写。应用有时候需要进行 读-改-写 序列操作而非单独的原子写操作。假如有两个客户端读取了同一版本的数据，修改并且把修改后的数据写回，按照原子写模型，时间上比较靠后的那一次更新将会覆 盖前一次。这种行为在某些情况下是不正确的（例如，两个客户端往同一个列表值中添加新值）。数据库提供了至少两种解决方法：
      • 冲突预防。 读-改-写 可以被认为是一种特殊情况下的事务，所以分布式锁或是 PAXOS [20, 21] 这样的一致协议都可以解决这种问题。这种技术支持原子读改写语义和任意隔离级别的事务。另一种方法是避免分布式的并发写操作，将对特定数据项的所有写操作 路由到单个节点上（可以是全局主节点或者分区主节点）。为了避免冲突，数据库必须牺牲网络隔离情况下的可用性。这种方法常用于许多提供强一致性保证的系统 （例如大多数关系数据库，HBase，MongoDB）。
      • 冲突检测。数据库跟踪并发更新的冲突，并选择回滚其中之一或是维持两个版本交由客户端解决。并发更新通常用向量时钟 [19] （这是一种乐观锁）来跟踪，或者维护一个完整的版本历史。这个方法用于 Riak, Voldemort, CouchDB.

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

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

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

• （A, 反熵） 一致性最弱，基于策略如下。写操作的时候选择任意一个节点更新，在读的时候如果新数据还没有通过后台的反熵协议传递到读的那个节点，那么读到的仍然是旧数据。（下一节会详细介绍反熵协议）。这种方法的主要特点是：
  • 过高的传播延迟使它在数据同步方面不太好用，所以比较典型的用法是只作为辅助性的功能来检测和修复计划外的不一致。Cassandra就使用了反熵算法来在各节点之间传递数据库拓扑和其他一些元数据信息。
  • 一致性保证较弱：即使在没有发生故障的情况下，也会出现写冲突与读写不一致。
  • 在网络隔离下的高可用和健壮性。用异步的批处理替代了逐个更新，这使得性能表现优异。
  • 持久性保障较弱因为新的数据最初只有单个副本。
• （B） 对上面模式的一个改进是在任意一个节点收到更新数据请求的同时异步的发送更新给所有可用节点。这也被认为是定向的反熵。
  • 与纯粹的反熵相比，这种做法只用一点小小的性能牺牲就极大地提高了一致性。然而，正式一致性和持久性保持不变。
  • 假如某些节点因为网络故障或是节点失效在当时是不可用的，更新最终也会通过反熵传播过程来传递到该节点。
• （C） 在前一个模式中，使用提示移交技术 [8] 可以更好地处理某个节点的操作失败。对于失效节点的预期更新被记录在额外的代理节点上，并且标明一旦特定节点可用就要将更新传递给该节点。这样做提高了一致性，降低了复制收敛时间。
• （D, 一次性读写）因为提示移交的责任节点也有可能在将更新传递出去之前就已经失效，在这种情况下就有必要通过所谓的读修复来保证一致性。每个读操作都会启动一 个异步过程，向存储这条数据的所有节点请求一份数据摘要（像签名或者hash），如果发现各节点返回的摘要不一致则统一各节点上的数据版本。我们用一次性 读写来命名组合了A、B、C、D的技术- 他们都没有提供严格的一致性保证，但是作为一个自备的方法已经可以用于实践了。
• （E, 读若干写若干） 上面的策略是降低了复制收敛时间的启发式增强。为了保证更强的一致性，必须牺牲可用性来保证一定的读写重叠。 通常的做法是同时写入W个副本而不是一个，读的时候也要读R个副本。
  • 首先，可以配置写副本数W>1。
  • 其次，因为R+W>N，写入的节点和读取的节点之间必然会有重叠，所以读取的多个数据副本里至少会有一个是比较新的数据（上面的图中 W=2, R=3, N=4 ）。这样在读写请求依序进行的时候（写执行完再读）能够保证一致性（对于单个用户的读写一致性），但是不能保障全局的读一致性。用下面图示里的例子来 看，R=2，W=2，N=3，因为写操作对于两个副本的更新是非事务的，在更新没有完成的时候读就可能读到两个都是旧值或者一新一旧：

• 对于某种读延迟的要求，设置R和W的不同值可以调整写延迟与持久性，反之亦然。
• 如果W<=N/2，并发的多个写入会写到不同的若干节点（如，写操作A写前N/2个，B写后N/2个）。 设置 W>N/2 可以保证在符合回滚模型的原子读改写时及时检测到冲突。
  • 严格来讲，这种模式虽然可以容忍个别节点的失效， 但是对于网络隔离的容错性并不好。在实践中，常使用”近似数量通过“这样的方法，通过牺牲一致性来提高某些情景下的可用性。
• （F, 读全部写若干）读一致性问题可以通过在读数据的时候访问所有副本（读数据或者检查摘要）来减轻。这确保了只要有至少一个节点上的数据更新新的数据就能被读取者看到。但是在网络隔离的情况下这种保证就不能起到作用了。
• （G, 主从） 这种技术常被用来提供原子写或者 冲突检测持久级别的读改写。为了实现冲突预防级别，必须要用一种集中管理方式或者是锁。最简单的策略是用主从异步复制。对于特定数据项的写操作全部被路由 到一个中心节点，并在上面顺序执行。这种情况下主节点会成为瓶颈，所以必须要将数据划分成一个个独立的片区（不同片有不同的master），这样才能提供 扩展性。
• （H, Transactional Read Quorum Write Quorum and Read One Write All）? 更新多个副本的方法可以通过使用事务控制技术来避免写冲突。 众所周知的方法是使用两阶段提交协议。但两阶段提交并不是完全可靠的，因为协调者失效可能会造成资源阻塞。 PAXOS提交协议 [20, 21] 是更可靠的选择，但会损失一点性能。 在这个基础上再向前一小步就是读一个副本写所有副本，这种方法把所有副本的更新放在一个事务中，它提供了强容错一致性但会损失掉一些性能和可用性。

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

• 一致性与可用性。严密的权衡已经由CAP理论给出了。在网络隔离的情况下，数据库要么将数据集中，要么既要接受数据丢失的风险。
• 一致性与扩展性。看得出即使读写一致性保证降低了副本集的扩展性，只有在原子写模型中才可以以一种相对可扩展 的方式处理写冲突。原子读改写模型通过给数据加上临时性的全局锁来避免冲突。这表明， 数据或操作之间的依赖，即使是很小范围内或很短时间的，也会损害扩展性。所以精心设计数据模型，将数据分片分开存放对于扩展性非常重要。
• 一致性与延迟。如上所述，当数据库需要提供强一致性或者持久性的时候应该偏向于读写所有副本技术。但是很明显一致性与请求延迟成反比，所以使用若干副本技术会是比较中允的办法。
• 故障转移与一致性/扩展性/延迟。有趣的是容错性与一致性、扩展性、延迟的取舍冲突并不剧烈。通过合理的放弃 一些性能与一致性，集群可以容忍多达 up to 的节点失效。这种折中在两阶段提交与 PAXOS 协议的区别里体现得很明显。这种折中的另一个例子是增加特定的一致性保障，比如使用严格会话进程的“读己所写”，但这又增加了故障转移的复杂性 [22]。

反熵协议， 谣言传播算法

让我们从以下场景开始：

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

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

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

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

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

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

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

最终一致数据类型

在上一节我们假定两个节点总是合并他们的数据版本。但要解决更新冲突并不容易，让所有副本都最终达到一个语义上正确的值出乎意料的难。一个众所周知的例子是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]中就提及了一系列这样的数据结构，包括：

• 计数器（加减操作）
• 集合（添加和移除操作）
• 图（增加边或顶点，移除边或顶点）
• 列表（插入某位置或者移除某位置）

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

数据放置

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

均衡数据

我们还是从一个简单的协议开始，它可以提供集群节点间无缝的数据迁移。这常发生于像集群扩容（加入新节点），故障转移（一些节点宕机）或是均衡数据 （数据在节点间的分布不均衡）这样的场景。如下图A中所描绘的场景 – 有三个节点，数据随便分布在三个节点上（假设数据都是key-value型）。

如果数据库不支持数据内部均衡，就要在每个节点上发布数据库实例，如上面图B所示。这需要手动进行集群扩展，停掉要迁移的数据库实例，把它转移到新 节点上，再在新节点上启动，如图C所示。尽管数据库能够监控到每一条记录，包括MongoDB, Oracle Coherence, 和还在开发中的 Redis Cluster 在内的许多系统仍然使用的是自动均衡技术。也即，将数据分片并把每个数据分片作为迁移的最小单位，这是基于效率的考虑。很明显分片数会比节点数多，数据分 片可以在各节点间平均分布。按照一种简单的协议即可实现无缝数据迁移，这个协议可以在迁移数据分片的时候重定向客户的数据迁出节点和迁入节点。下图描绘了 一个Redis Cluster中实现的get（key）逻辑的状态机。

假定每个节点都知道集群拓扑，能够把任意key映射到相应的数据分片，把数据分片映射到节点。如果节点判断被请求的key属于本地分片，就会在本地 查找（上图中上面的方框）。假如节点判断请求的key属于另一个节点X，他会发送一个永久重定向命令给客户端（上图中下方的方框）。永久重定向意味着客户 端可以缓存分片和节点间的映射关系。如果分片迁移正在进行，迁出节点和迁入节点会标记相应的分片并且将分片的数据加锁逐条加锁然后开始移动。迁出节点首先 会在本地查找key，如果没有找到，重定向客户端到迁入节点，假如key已经迁移完毕的话。这种重定向是一次性的，并且不能被缓存。迁入节点在本地处理重 定向，但定期查询在迁移还没完成前被永久重定向。

动态环境中的数据分片和复制

我们关注的另一个问题是怎么把记录映射到物理节点。比较直接的方法是用一张表来记录每个范围的key与节点的映射关系，一个范围的key对应到一个 节点，或者用key的hash值与节点数取模得到的值作为节点ID。但是hash取模的方法在集群发生更改的情况下就不是很好用，因为增加或者减少节点都 会引起集群内的数据彻底重排。导致很难进行复制和故障恢复。

有许多方法在复制和故障恢复的角度进行了增强。最著名的就是一致性hash。网上已经有很多关于一致性hash的介绍了，所以在这里我只提供一个基本介绍，仅仅为了文章内容的完整性。下图描绘了一致性hash的基本原理：

一致性hash从根本上来讲是一个键值映射结构 – 它把键（通常是hash过的）映射到物理节点。键经过hash之后的取值空间是一个有序的定长二进制字符串，很显然每个在此范围内的键都会被映射到图A中 A、B、C三个节点中的某一个。为了副本复制，将取值空间闭合成一个环，沿环顺时针前行直到所有副本都被映射到合适的节点上，如图B所示。换句话说，Y将 被定位在节点B上，因为它在B的范围内，第一个副本应该放置在C，第二个副本放置在A，以此类推。

这种结构的好处体现在增加或减少一个节点的时候，因为它只会引起临接区域的数据重新均衡。如图C所示，节点D的加入只会对数据项X产生影响而对Y无 影响。同样，移除节点B（或者B失效）只会影响Y和X的副本，而不会对X自身造成影响。但是，正如参考资料[8]中所提到的，这种做法在带来好处的同时也 有弱点，那就是重新均衡的负担都由邻节点承受了，它们将移动大量的数据。通过将每个节点映射到多个范围而不是一个范围可以一定程度上减轻这个问题带来的不 利影响，如图D所示。这是一个折中，它避免了重新均衡数据时负载过于集中，但是与基于模块的映射相比，保持了总均衡数量适当降低。

给大规模的集群维护一个完整连贯的hash环很不容易。对于相对小一点的数据库集群就不会有问题，研究如何在对等网络中将数据放置与网络路由结合起 来很有意思。一个比较好的例子是Chord算法，它使环的完整性让步于单个节点的查找效率。Chord算法也使用了环映射键到节点的理念，在这方面和一致 性hash很相似。不同的是，一个特定节点维护一个短列表，列表中的节点在环上的逻辑位置是指数增长的（如下图）。这使得可以使用二分搜索只需要几次网络 跳跃就可以定位一个键。

?