谈谈对分布式一致性的一点理解

引言

这是一个很大的主题。我相信每一个初学分布式的人开始时都像我一样深深的思考过这个问题，但是却仍然是一头雾水，然后每经历一次“顿悟”，又会因为某个新的问题再次陷入沉思，所幸在经历过几个这样的来回以后算是对这个问题在脑子里有了一个简单且算是全面的印象，遂记录这一篇博客以帮助更多的人能够对这个问题有着更为深入的理解。事实上我在一个月以前就想写下这篇文章了，可是当时因为一个问题始终没办法理解就半途而废了，当然这并不是全部原因，还有一部分原因是因为害怕写出来的东西是千篇一律，没有什么营养，直到前几天理解了那个问题以后才又鼓起勇气动笔，这篇文章的主要目的就是能让读者对于分布式一致性这个话题有一个初步的全面理解。

一致性的分类

其实开始是对于一致性的分类只有两种，就是强一致性与弱一致性，后来出现了最终一致性（Eventually consistent）这种说法，这个词最早由Douglas Terry提出，后来经由 Werner Volgels 在ACM上的一篇文章而普及，还好有前辈已经翻译了这篇经典的文章[1]，着实是不小的贡献。这篇文章上第一次出现了从两个角度来看一致性的观点，事实证明这种观点是非常正确且经典的，也是本篇文章重点讨论的一个问题。

首先要说的是这两个角度的叫法非常的不统一，目前我看到的有讨论这个问题的文章的叫法都不一样[1]，[3]，[5]，本文中采用[1]中的叫法，说这个的目的是让大家不要因为这个小事情感到疑惑。

1. Client-side Consistency：用户所实际看到的数据的状态所体现的一致性。
2. Server-side Consistency：物理上数据实际的一致性，举个例子，在一个三个副本的主从复制模型中，如果一次写入复制到全部的副本才返回这就是数据角度的强一致性。

对于这个看法我相信你还是有一些疑惑，我们举一个Zookeeper的例子来说明这个问题，我们知道Zookeeper在一致性协议上选择了独创的ZAB（ZooKeeper Atomic Broadcast）算法，这种算法在向副本复制的时候仍是遵从quorum，在大多数节点同意时就向调用者返回写入成功，而因为zk是一个读多写少的系统，所以允许直接从slave读取数据，且zk是一个CP的系统，是否觉得很奇怪呢？因为这样看起来从Server-side Consistency角度来看我们没办法保证slave看到的数据是最新的，因为在提交时还有最多f个节点没有接受到数据（2f + 1 >= N）,那么为什么zk还是一个CP的系统呢？原因就是zk使用了一些“黑魔法”保证了客户看到的数据一定是最新的，这种方法就是给事务加上一个zxid，具体可参考[7]。

然后我们就可以对开始提到的一致性分类做一个总结了：

1. 强一致性：我们一般也称强一致性为线性一致性（Linearizability），至于为什么叫线性，原因可能是把全局的这些事件一起构成的集合，在数学上可以称为具有“全序关系”的集合，而“全序”也称为“线性序”。这是分布式中可以达到的最强的一致性，它意味着全局发生的所有事件都是有先后顺序的，这显然很难在兼顾可用性的情况下办到，但不是不可以。
2. 最终一致性：在A节点（leader）写入数据后，BC节点（slave）可能在一段事件内无法读到最新数据，但是在某个时间窗口后保证最终可以读到，但也像前面zk那个例子，我们可以使用某些方法使得这种一致性可以变成客户角度的强一致性。
3. 弱一致性：也可以说弱于最终一致性，即写入数据 A 成功后，在数据副本上可能读出来，也可能读不出来，不能保证多长时间之后每个副本的数据一定是一致的。

因为最终一致性的特殊定义，有很多衍生的最终一致性模型。我们挑选几个常见的模型进行讨论，并希望能给出每一种模型的简单实现思路，至少我现在所看的文章中都缺乏此方面的描述，为我想对于一个初学者来说显然例子是更为直观的，我想这也算是我对社区的一点点绵薄的贡献。

就我现在看过的论文来说，很多架构都选择了最终一致性加上一些巧妙的方法让客户认为是强一致性，比如zk，GFS，但也有很多使用了真正的强一致性，比如Spanner，Chubby，所以一致性对于分布式系统的设计非常重要。

客户角度的一致性

线性一致性

这是最强的一致性约束，意味着全局的事件满足全序关系，这显然是一个非常难以实现的一点，因为我们很难把所有的事件记录在一条时间线上，上面的zk提到的解决方法是一种。还有一种就是参考Spanner，谷歌实现了一个新的API，即TrueTime，这可以精确的给出当前时间的一个区间，且区间范围在14ms之内，Spanner的事务会把涉及的所有节点的safet（执行下一个事务的安全起始时间）向后移动一个相同的值，这样可以确保全局的事务是一个全序，具体可参考[8]。

当然对一个分布式数据库来说，我们肯定是希望拥有这个级别的一致性的。

前缀一致性

很多文章都提到了这个，所以我直接拿一个其他博主的图（侵删）来说明这个级别的一致性：

小明和小红分别把数据发送给了不同的节点，即N1和N2，小刚从N3读取数据（向物理上离自己最近的数据中心读取数据），因为网络的原因，可能小刚先看到答案才看到提问，这显然就违反前缀一致性。

那么我们如何可以解决这个问题呢？

其实在这个问题中关键在于如何判断操作是有因果关系（happens-before）还是它们完全并发，其实我们可以这样理解，即：一个操作发生的时候如果已经看到了上一个操作，那么这两个操作就是有因果关系的，反之说它们之间是并发的。也可以说两个任意操作A，B之间只有三种关系，A发生在B之前，B发生在A之前和AB并发。DDIA[6]5.4的happens-before小节中描述了一种称为版本矢量的方法可以解决这个问题，限于篇幅不详细描述。

单调读一致性

我们先举一个不保证单调读一致性会出现意料之外情况的例子：

小明先发送了一条空间动态，这条动态在T1时刻被复制到R1，小红首次刷新时看到了这条说说，过了一会刷新第二次，这发生在T2之前，奇怪的事情发生了，刚刚看到的消息不见了，这是什么回事，原因是第二次查看的副本是R2，而数据还没有被同步到R2，所以发生了这样的事情。

也就是说单调读一致性的定义就是：用户一旦读到某个值就不会读到比这条消息更旧的值。

我们该如何做呢？这其实做法相比于前两中就简单了很多，比如让一个账号在数据确定被同步到所有节点前始终只访问一个数据中心，或者像zk一样给每一个操作分配一个zxid，读操作附带一个前一个看到的操作的zxid，这样访问的数据中心最新数据如果还没到的话就阻塞，知道数据到达再回复，这样也可以做到单调读。

读己之写

小明把数据发送到R1，T1时刻返回，并且希望自己可以看到的自己刚刚的写入，我们可以看出其实这和单调读，前缀一致读都非常类似，可以说是一个级别的一致性。

我们只需要保证复制到全部节点前在同一个节点就可以，当然是用zxid也可以。

服务器角度的一致性

我在文章开头提到有问题没有理解，其实就是服务器角度的一致性，并且当时不能理解[1]关于此部分的为什么这么描写，现在才知道当时想多了，所谓服务器的一致性就是数据的实际分布，也就是在所有副本中规定的quorum数量。

对于这个问题我想引用[1]中对这个问题的描述：

N：存储数据冗余副本的节点数
W：在更新结束前，需要发出更新到达信号的冗余副本数
R：一个数据对象进行读操作需要建立的冗余副本的数量

强一致性

也就是说我们希望每一个读操作都能看到读操作发生前所有的写操作，那么我们可以把上述参数配置为W + R > N，这样可以保证读写总会有交集，这样也就保证了强一致性。

当然有时可能需要我们优化写操作，那么我们可以配置W为1，然后使用诸如gossip协议去实现一个最终一致。有时我们则需要优化读操作，此时就可以把R配置成1，如果我们想要在优化读的情况下还实现强一致，要么配置W == N，要么像zk一样给每一个事物分配唯一递增ID，在未读到最新数据时阻塞。

顺序一致性

定义为：所有的进程以相同的顺序看到所有的修改。读操作未必能及时得到此前其他进程对同一数据的写更新，但是每个进程读到的该数据的不同值的顺序是一致的。

你可能会说这真的会发生吗？当然，且有两种发生的情况，一种是单主节点，一种是多主节点。但是不必担心这些情况，因为我们都可以很好的解决。

单主节点

假设我们有ABCDE五个副本，在一个Term中A为leader，其余节点为slave，我们假设这个集群中不会出现两个主节点同时工作的情况。首先我们向A执行写操作1，操作1得到ABC三个节点的ACK，成功写入；我们再向A执行写操作2，得到ACD三个节点的同意，成功写入，我们发现此时仅有AC节点的顺序是一致的，BD仅有一个数据，而E则没有数据，随着时间的推移，D的数据和AC顺序就不一样，E则可能一样，也可能不一样。

我们几乎在任何情况下都不需要这样的数据，细心的朋友可能发现了上面描述的问题就是分布式共识算法所解决的问题，我们看看对于上面问题Raft算法如何解决，首先我们来看一个奇怪的日志条目，来源于Raft论文的图7：

当一个 leader 成功当选时（最上面那条日志），follower 可能是（a-f）中的任何情况。每一个项表示一个日志条目；里面的数字表示任期号。Follower 可能会缺少一些日志条目（a-b），可能会有一些未被提交的日志条目（c-d），或者两种情况都存在（e-f）。例如，场景 f 可能这样发生，f 对应的服务器在任期 2 的时候是 leader ，追加了一些日志条目到自己的日志中，一条都还没提交（commit）就崩溃了；该服务器很快重启，在任期 3 重新被选为 leader，又追加了一些日志条目到自己的日志中；在这些任期 2 和任期 3 中的日志都还没被提交之前，该服务器又宕机了，并且在接下来的几个任期里一直处于宕机状态。

这其实就是我们所说的违反顺序一致性，Raft选择所有节点无条件信任主节点（Raft只能应对非拜占庭错误），以主节点日志为主，Raft会为每一个slave维护一个nextIndex和matchIndex，分别代表对于每一个服务器，需要发送给他的下一个日志条目的索引值和对于每一个服务器，已经复制给他的日志的最高索引值，这样我们可以在副本察觉到当前日志不符合主服务器的信息的时候，会抛弃掉一部分自己的日志，并向主节点返回，几个来回以后直到完全匹配，主服务器把slave缺失的日志全部发送，这样就解决了这个问题，当然这里只是简单描述，有兴趣的朋友可参考[9]中的5.3。

多主节点

显然多主节点在某些情况下有自己的优势[10]，但是也看出现我们所说的顺序问题，试想在多个节点同时向一个用户写入数据，这就是一个并发的操作，如果使得多个数据中心间数据顺序一致呢？三种方法：

1. 避免冲突：我们可以在应用层是不同的用户始终访问地理上据他更近的同一个节点，这样就不会发生写冲突。这样对于用户来说就相当于是单节点主从复制，典型例子就是Redis的集群。当我们使用某个账号对应节点时确实是非常不错的，但是如果换到了另一个地方，此时距离原节点地理上就太远了。
2. 收敛于一致状态：多主节点不像单主节点那样写入有顺序性，多主节点互相都不知道对方此刻发了哪些消息，这些消息都是并发的，那么如何收敛于一致状态，保证全局数据一致呢？可以分配UUID，或者使用基于存储的哈希，比较大小，大的删除，此时这里的纪元应该是高于其他节点的，几轮心跳包以后就数据一致了。
3. 自定义冲突解决:最典型的就是git了吧，当我们有了两个分支以后把这些值混合在一起，用户自定义选择。

因果一致性

对于这个名词我目前看到的所有文章中所描述的都非常含糊，且界限也很模糊，比如在[5]中把它归于客户端一致性，而在[3]中归于服务器的一致性，我个人认为它也很像前缀一致性，在DDIA上就把前缀一致性中的关系称为因果关系，所以这是个让我很疑惑的名词。

在[11]中提到了其实这种情况往往发生在分区（也称为分片）的分布式数据库中。分区后，每个节点并不包含全部数据。不同的节点独立运行，因此不存在全局写入顺序。如果用户A提交一个问题，用户B提交了回答。问题写入了节点A，回答写入了节点B。因为同步延迟，发起查询的用户可能会先看到回答，再看到问题。所以此时我们需要如果一系列写入按某个逻辑顺序发生，那么任何人读取这些写入时，会看见它们以正确的逻辑顺序出现。这就是因果一致性。

总结

显然从上面的描述我们可以看出一个问题，就是分布式一致性模型中有两个要点，即读写策略和多副本状态，也就是说一个分布式系统的一致性实际与协议不完全相关，哪怕你使用Raft，但开放了slave读数据也没办法保证线性一致性；相反，哪怕因为协议无法保证slave读数据的线性一致性，你也可以从读写策略上下手，来保证线性一致性，例如Zookeeper。

对这个问题的讨论到这里就告一段落了，对于构建一个分布式系统来说，选择合适的一致性是所有任务中优先级最高的一个任务，因为一致性决定了整体的架构。而一个合理的一致性可以是我们完成需求的情况下仅可能高的提升效率和可用性。文中也只是很浅薄的讨论了这个问题，此方面的论文有不少，感兴趣的读者可以酌情阅读。但是还是切记纸上得来终觉浅，讨论毕竟只是讨论，看几个经过实际使用的系统的论文中对一致性的描述可以更好的体会不同的一致性对设计的影响，当然在了解理论以后看代码更能提高我们的水平，写代码当然又是更高的一个级别了，但是实现这样一个系统当然是不容易的，还记得实现一个强一致性的kvraft调bug就让我半周不想吃饭。。

笔者水平有限，文章有差错之处还请读者斧正

参考：

1. 博文《［译］最终一致性》
2. 博文《Base理论》
3. 博文《分布式下的一致性杂谈》
4. 博文《Azure Cosmos DB 中的一致性级别》
5. 博文《强一致性：那么多数据一致性模型，究竟有啥不一样？》
6. 书籍《Designing Data-Intensive Applications》
7. 博文《Zookeeper探究之一致性与应用》
8. 博文《谷歌技术探究之Spanner》
9. 论文《In Search of an Understandable Consensus Algorithm(Extended Version)》
10. 博文《节点间数据复制》
11. 博文《通俗易懂 强一致性、弱一致性、最终一致性、读写一致性、单调读、因果一致性 的区别与联系》
12. 《共识、线性一致性与顺序一致性》