分布式系统的一致性问题

发表于 更新于 分类于 阅读次数：

分布式系统中的数据如何保证一致性一直是设计分布式系统时比较棘手的问题，在过去的几十年里人们已经提出了很多与之相关的理论试图去完美地解决它。

为什么会出现一致性问题

以最常见的分布式系统–银行 ATM 为例，假设某人 A 的一个帐户内存有200块钱，某一时间点 A 和他的朋友 B 同时在两个不同的 ATM 机进行取款200块的操作，此时系统便出现了一致性问题，因为不管系统作出何种回应都会导致不一致的问题：

  1. 系统接受一方的取款请求，拒绝另一方的取款请求
    这会导致被拒绝的一方认为系统不可用，因为任何一方此时都认为帐户里应有200块的余额可用。
  2. 系统对于两个请求均接受
    银行帐户发生透支。
  3. 系统同时拒绝两个请求
    两方都认为系统不可用。

解决一致性问题的一些算法

上述问题出现的根本原因还是由于缺乏一个既定的规则，因而发生了冲突。下面简要介绍一些能够解决这一问题的算法。

Lamport 面包店算法

类似于去营业厅排号，每个请求先申请到一个独一无二的号码，然后按号码小者优先的规则进行办理。对应到上面的例子，A、B两人取钱前都获得了一个号码，假设 A 的号码是1， B 的是 2，那么系统将会接受 A 的请求而拒绝 B 的， B 发现失败后也能通过排号的纪录查到原因。
这个方法看似简单易行，但在分布式系统中难以实现，因为在分布式系统中要维护一个全局的排号系统并不容易，这往往需要较高的硬件环境，可以参考谷歌利用GPS和原子钟使数据库全球范围信息同步。

Vector Clocks

这个算法与上面的面包店算法算法都是 Lamport 提出的，可以说是上一个算法的改进版，去除了维护全局排号系统的负担。从字面大概也可以猜到，这个算法通过一系列的计数器来实现。还是对应到上面的例子，A、B所用的 ATM 机需要自己维护一个计数器序列，每次操作将这个序列里自己的计数器加一，当 ATM 发送请求到系统中时需要附带这个序列。假设刚开始时两台 ATM 的计数都为0，那么 A 操作后的 ATM 将发送 [{a, 1}, {b, 0}]， B 的将发送 [{a, 0}, {b, 1}]，可以看出 A 的序列中 b 比 B 的序列中 b 还小，说明有冲突，此时可以按照时间顺序谁先到处理谁，后来的拒绝，假如同时到达则按 ATM 机的字母排号选择，排号小的（这里就是 A ）操作被执行。注意 Vector Clocks 本身并不包含冲突的解决过程，它仅是发现冲突，但上述冲突解决方法已被大多数采用此算法的实际系统采用。
这个算法已有一些分布式系统采用，比如 Riak 和早期的 Cassandra、 Dynamo 。但此方法需要每次请求前先向其他节点获得对方计数器的最新版本，而且还要给 Vector Clocks 存储留一定的空间，造成性能和资源的消耗加剧，实际使用效果并不佳。

选举算法

既然解决冲突那么麻烦，于是有了一些尽量避开冲突的方法，选举算法就是其中之一。首先在系统中通过既定的规则选举出一个 Master ，其余节点都为 Slave ，外来请求都通过 Master 处理， Slave 节点只需把 Master 上的数据同步过来即可。以上面的例子来说， A 与 B 可以先定下规矩，在使用这个账号取钱时都要先打电话跟对方确认，这样就能够避免冲突。当 Master 节点失效时，系统其他节点再通过之前定好的规则选举新的 Master 。这里的选举规则比较常见的有 Paxos 和 Raft。
现在比较流行的分布式系统大多采用这一方法，比如 MongoDB、Redis 和 Dynamo 等，此外还可以使用 ZooKeeper 等支持选举算法的工具实现自己的分布式系统。这个方法的缺点是当 Master 失效后系统会短暂的处于不可用状态。

Quorum NRW

一种从客户端侧解决一致性问题的投票算法，它通过客户端同步操作多个实例来保证一致性，具体冲突解决由客户端自己实现，详细内容可参考这里。

Rev Tree

另外一种避开冲突的解决算法，类似于 Git 的版本树。对每次操作产生一个对应的 Rev Id ，将每次操作的 Rev Id 都放到上次操作之后形成主分支，当有一个拥有不一致的 Rev Tree 的数据想进行合并时冲突产生，此时便会产生一个新的分支，然后两个分支同时工作。默认会以最长分支为主分支，其他分支及其所有的数据会在一段时间后删除。还是以 ATM 的例子进行说明，在这种情况下 A、B 的取款请求都会被成功响应，而后假如 A 又通过 ATM 进行了一些操作而 B 没有，那么 A 的请求会被最终记录下来，而 B 的请求一段时间后会被删除，显然对于取款这样需要即时完成的操作，这种方法并不可取。
此算法在 CouchDB 中被使用。这个算法把冲突的解决交给了时间，活跃度最高的数据会被保存下来，类似于民主选举的理念，适用于没有权威决策要求的去中心化系统。

区块链

这是比特币网络中用于记录交易过程生成总账单的算法，类似于上面提到的 Rev Tree 算法，不过基于安全性的需要增加了非对称加密、计算能力验证等逻辑。具体内容可参考我之前的一篇博客–比特币背后的技术。

CRDT

力图从数据结构上避免冲突。 CRDT 就是指能够避免冲突的可复制的数据结构，而且这类数据结构的合并过程一般情况下都会满足 ACID 2.0：

  1. 结合律 f(a,f(b,c)) = f(f(a,b),c)
  2. 交换律 f(a,b) = f(b,a)
  3. 等冪性 f(f(x))=f(x)

目前已知的满足以上几点的数据结构有计数器（Counter）、寄存器（Register）、集合（Set）、图（Graph）等，详见这里。
更多的 CRDT 仍处于理论界的探讨证明中，目前仅有少数几个分布式系统使用了这一数据结构，比如 Riak 和 Project FiFo 。