2017年饿了么在做异地多活的时候，我的团队承接了多活的改造-在Zookeeper的不同地方活跃。在这段时间里，我听到了关于Zookeeper一致性的两种不同的说法：Zookeeper由于有多个副本而最终是一致的，以及保证大多数成功的Zab协议，当一个客户端进程写入一个新值时，另一个客户端进程无法保证它会立即读取它，但它可以保证它最终会读取到值。Zookeeper的Zab协议类似于Paxos协议，提供强一致性。每当我听到这两个说法，我都想纠正它们。Zookeeper是顺序一致性（SequentialConsistency），但是解释起来比较复杂。让我和你谈谈我的看法。什么是顺序一致性？我们从Zookeeper的文档中可以看到，明确说明了它的一致性是SequentialConsistency。那么，什么是顺序一致性？SequentialConsistency最早由Lamport于1979年提出。如论文中所定义，SequentialConsistency定义为满足以下条件：任何执行的结果都相同，就好像所有处理器的操作都按某种顺序执行，每个处理器的操作按照其程序指定的顺序出现在这个序列中。这个英文定义很晦涩，是Lamport一贯的风格，严谨但晦涩难懂，Paxos协议也是如此。当我第一次看到它时，我就像：“这到底是什么东西？”为什么我知道每个英文单词，但我就是不知道他在说什么？我们先来看一个在本文标题和定义中出现的关键词，用来说明SequentialConsistency的适用范围。论文的标题和定义中包含“多处理器”一词，意思是多核处理器。从这个关键字开始，SequentialConsistency是一种用来定义多核处理器和运行在多核处理器上的程序的特性。Lamport的论文标题可以翻译为：“如何让多核处理器的计算机正确执行多进程程序”。也就是说，如果一个多核处理器具有顺序一致性的特性，那么该多核处理器就可以正确运行。后面我会解释这个正确的操作是什么意思（也就是本文后面提到的SequentialConsistency的作用）。从这个标题我们也可以看出SequentialConsistency应该是ConcurrentProgramming领域的一个概念。但是现在我们在分布式系统领域经常讨论SequentialConsistency，比如本文主要讨论的Zookeeper（Zookeeper显然是分布式系统）的一致性。事实上，运行在一个多核处理器上的多个程序其实就是一个分布式系统（Lamport在他的开创性著作Time,Clocks,andtheOrderingofEventsinaDistributedSystem分布式系统中也阐述了这一观点）。所以SequentialConsistency虽然最早是在并发编程中提出来的，但是在分布式系统中是可以应用的，比如本文讨论的分布式存储系统Zookeeper。另一个重要的特性Linearizability（线性一致性）最早是在并发编程中提出的，目前广泛应用于分布式系统领域。接下来，让我们尝试翻译上面晦涩的定义。做这个翻译让我找到了在学校做阅读理解的感觉。我就不直接翻译了，因为就算我翻译成中文，估计很多人还是会有这样的感觉“为什么每个汉字我都看懂了，但还是不知道在说什么”关于”。首先，让我解释一下单个单词。首先，“任意执行”是什么意思？你有多个程序（Program）运行在一个多核处理器上，比如你有两个程序。第一个程序叫做P1，它的代码如下：P1_write(x);P1_read(y);第二个程序叫做P2，代码如下：P2_write(u);P2_read(v);理论上，两个独立处理器内核上运行的程序有多少种执行可能性？我列举其中的几个作为例子。第一种：P1---write(x)--------read(y)--------P2------------write(u)-------read(v)-第二种：P1------------write(x)-read(y)--------P2--write(u)----------------read(v)-第三种：P1---read(y)------------write(x)----P2------------write(u)------------read(v)-我们有24种可能的执行顺序，也就是这四种操作的任意排列组合，即4!=24。第一种和第二种可能性是众所周知的。为什么会有第三种这样的可能实现呢？那是因为即使在同一个程序中，由于多级缓存和处理器中一致性的存在，虽然你的程序是先写后读，但在内存中真正生效的顺序可能是先写后读。其实会有类似下面的执行，在两个处理器上同时执行两个操作。P1--write(x)-read(y)--------P2--write(u)--------read(v)-如果加上同时运行的情况时间，那么就有更多的可能。我的算术不太好，这里就不继续数了，因为有多少并不重要，重要的是知道有多少种可能。那么定义中的“任意执行”指的是任意一种可能的执行，也可以理解为定义中所有这些可能的执行。那么再解释一下另一个词——“顺序”。什么是顺序？翻翻英文词典吧（感觉更像是做阅读理解）。顺序的：连续的；顺序的；顺序顺序：顺序；其实sequential就是一个接一个的意思。在处理器的上下文中，sequential是指操作（operations）一个接一个地执行，即顺序执行，没有重叠。秩序是指事物经过一定的调整，按照一定的规则变得井然有序。比如算法中的排序算法就是排序，就是让数组按照从大到小或者从小到大的规则有序排列。那么sequentialorder就是按照这样的规则依次进行操作，没有重叠。回到上面的例子，如果我们将四个操作一一排列，可以得到4！排列结合了可能的排列（顺序），同样，有多少并不重要。例如：P1_write(x);P1_read(y);P2_write(u);P2_read(v);P1_read(y);P1_write(x);P2_write(u);P2:read(v);P2_write(u);P2_read(v);P1_read(y);P1:write(x);我这里只列出三个，其他的你可以自行安排。重点来了，其实sequentialorder就是让这四个操作一个一个执行，不重叠。请注意，这种安排不是真正的执行。真正的执行是任意执行。这里说的是一个逻辑假设，这就是为什么在定义中有一个asif。做了这么多伏笔，我们开始翻译定义中的第一句话：任何可能的执行效果，都等同于某个操作在所有按顺序排列的处理器上的执行效果。注意这里的some是指“某一种”，不是some，因为order是单数的（真的是做阅读理解）。这句话的意思是，如果一个处理器要满足这个条件，它只能允许那些满足这个条件的可能执行存在，其他不满足这个条件的可能执行不会出现。从第一句我们可以看出，如果多核处理器要满足顺序一致性，那么多个程序运行在多个核上的效果就“等同于”在一个核上顺序执行所有操作的效果。.如果真是这样的话，其实多核的威力基本就消失了。所以无论是从1979年Lamport写这篇论文的时候，还是现在，都没有真正的多核处理器实现过SequentialConsistency。那么，为什么兰波特会提出这样一个不切实际的概念呢？（需要说明的是，Lamport在写这篇论文时，并没有将其扩展到分布式系统领域，而是针对多核处理器和并发编程领域提出的。）我们稍后再讨论。这里还有一点要注意，我在翻译中使用了“effect”这个词，但实际上英文原文中使用了“result”这个词。效果和结果有区别吗？下面解释一下执行结果是什么。不管是什么真正的执行，或者排序后的某种假想执行，程序都会产生一定的结果，比如print(result)的结果。事实上，定义说结果是一样的。如果定义中使用了“效果”，那么这个定义只是定性定义，如果使用了“结果”，那么这个定义就是定量定义。定量的，即数学上可证明的。从这一点就可以看出大神们的不同，任何理论都可以通过数学来证明是正确的。本文后面会提到证明，这里先保密。到这里，定义的第一句比较准确的翻译是：任何可能执行的结果，都与某种操作在所有处理器上按顺序执行的结果相同。这里我们还需要注意一点。同样的结果意味着如果有人真的要实现一个SequentialConsistency的多核处理器，因为结果肯定是一样的，他有一定的优化空间，而不是完全顺序执行的效果。但估计这种优化也很有限。好了，最难的第一句终于解释完了，大家可以松一口气了，第二句很简单。我们先来解释一下出现在第二句中的一个词——“sequence”。刚才解释的顺序就是顺序排序（也就是一个一个的排序）。其实这是一个动作，一个动作产生一个结果，它的结果产生一个操作队列。第二句出现的sequence指的就是这个操作的队列。那么，第二句的翻译就是：并且每个独立处理器的操作都会按照程序指定的顺序出现在操作队列中。也就是说，如果程序先write(x);然后阅读（y）；那么只有满足这个顺序的操作队列才有资格。这样一来，我们刚才说的很多可能的实现就少了很多，这里不计算少了多少。还是那句话，多少不重要，反正有的，少的也多。那么第二句话是什么意思呢？就是说，如果一个多核处理器实现了SequentialConsistency，那么这种多核处理器基本上就告别了自（cache）跑（存）车。这里我又要继续玩花样了，连缓存的优化这种提升处理器性能最有效的方法都没有了。为什么大师会提出这个概念呢？好吧，这里我们可以把两个翻译放在一起，完整的看一下：任何可能执行的结果，都是按照一定顺序在所有处理器上执行操作的结果，而每个独立处理器的操作都会出现按照程序指定的顺序在操作队列中。从这个定义中，我们可以看出这个概念的核心是顺序顺序，这也是Lamport先生将这个一致性模型称为SequentialConsistency的原因。可以说，这个命名是非常恰当的。我不知道以英语为母语的人是否更能理解这种贴切。应该没有什么“秩序的秩序到底是什么”。如果你看完这篇文章觉得sequential很合适，说明我已经说清楚了。下面举个具体的例子来说明一下：executionAP0writex=1------------------------------------P1------writex=2--------------------P2----------------readx==1--readx==2P3----------------readx==1--readx==2顺序：P0_writex=1,P3_readx==1,P4_readx==1、P1_writex=2,P3_readx==2,P4_readx==2executionBP0write=1--------------------------------P1-------writex=2--------------------P2----------------readx==2--readx==1P3----------------readx==2--readx==1序列顺序：P1_writex=2,P3_readx==2,P4_readx==2,P0_writex=1,P3_readx==1,P4_readx==1executionCP0write=1--------------------------------P1-------writex=2--------------------P2----------------readx==1--readx==2P3----------------readx==2--readx==1sequetialorder:找不到满足2个条件的顺序定义。sequentialorder：找不到满足定义中两个条件的顺序。所以如果一个多核处理器只允许出现执行A和B，而不允许出现C，那么这个多核处理器就是SequentialConsistency；如果允许C出现，那么就不是SequentialConsistency。至此，我们已经完全解释了什么是顺序一致性。不过，细心的朋友可能会问，如果你的程序是多线程程序呢？然后让我们解释一下定义中最大的细节之一：程序这个词。程序是可以直接在处理器上运行的一系列指令。这不是对程序的严格定义，但我想指出的是，这个程序是一个在没有操作系统存在的古代就存在的概念。在上面的定义中，prgram指的是那个时代的节目。该程序中没有进程或线程的概念。这些概念是在操作系统建立之后才出现的。因为没有操作系统，所以没有内存空间的概念。和我们现在说的程序不同，不同的程序有自己独立的内存地址空间。在这里，内存为不同的程序共享。另外需要注意的是program可以用来描述各种程序，不管你是操作系统内核还是应用程序，都是适用的。顺序一致性是分布式领域的一个概念。刚才我们说了SequentialConsistency虽然是针对并发编程领域提出来的，但实际上是分布式领域，尤其是分布式存储系统中的一个概念。在Distributedsystem:PrinciplesandParadigms(byAndrewS.Tanenbaum,MaartenVanSteen)中，作者稍微修改了Lamport的定义，使其更接近于分布式领域的概念。让我们看看作者是如何改变它的：任何执行的结果都是一样的，就好像所有进程对数据存储的（读和写）操作都是按某种顺序执行的，并且每个进程的操作出现in此序列按其程序指定的顺序排列。作者将processor换成了process，并添加了对datastore的限制。Lamport的定义中没有这样的限制。其实默认指的是内存（memory）。过程指的是过程。以Zookeeper为例，指访问Zookeeper的应用进程。程序并不是这么低级的概念，它也是基于操作系统的应用程序。SequentialConsistency的作用不错，是时候揭晓我上面卖的两个重点了。Lamport的论文中给出了一个小例子如下：process1a:=1;ifb=0thencriticalsection:a:=0else...fiprocess2b:=1;ifa=0thencriticalsection:b:=0else...fiLamport在论文中是说如果一个多核处理满足顺序一致性的条件，那么最多只有一个程序可以进入临界区。在论文中，Lamport先生没有解释为什么最多只有一个程序可以进入临界区。而是把这个证明留给论文的读者，就像我们常见课本中的课后习题一样。Lamport先生应该是觉得这个证明太简单了，没必要费笔墨去证明。SequentialConsistencypaper不到两张A4纸，是我见过最短的paper。这是兰波特一贯的做事风格。在他的Paxos论文中，一笔带过很多细节，留给读者无尽的遐想（盲目想象）。假设我们现在已经证明这是正确的（虽然我没有证明，论文给出了两个参考文献来证明），这个例子说明了什么？你可能已经注意到这个例子没有使用任何锁，但是它实现了一个临界区，这是一个多线程同步机制。如果多核处理器是SequentialConsistency，那么你写的并发程序“天生就正确”。但是，为了追求性能，处理器的设计者将保证程序正确性的任务留给了程序开发者。硬件层面只提供了fence、cas等部分指令。基于这些指令，内核和语言库实现了各种同步机制，以保证操作系统的正确性和应用程序的正确性。程序员一定要小心使用线程和这些同步机制，否则会出现各种意想不到的问题。如果你没有调试过一个多线程的bug，连续两天加班，那你就是高手了。这些指令具有更高的一致性级别，即线性化性。虽然一致性级别很高，但仅针对个别指令。处理器作为一个整体只能达到比顺序一致性低得多的一致性级别。从而大大降低了实施难度。Lamport先生的SequentialConsistency概念虽然在ConcurrentProgramming领域没有什么实际意义，但是却给我们指出了程序员的天堂在哪里。在程序员的天堂里，没有多条火车线路（进站）（进站）（前进）（返回），只要写好程序即可。面试的时候，没有人会问你多线程编程，或者各种锁。在分布式领域，SequentialConsistency更为实用。Zookeeper实现了顺序一致性。同理，这也应该是可证明的，但是在Zookeeper社区中还没有找到可以证明这一点的论文。如果你已经理解了上面解释的定义，你就可以清楚地认为Zookeeper是顺序一致性的。欢迎一起讨论。Zookeeper为什么要实现SequentialConsistency其实Zookeeper的一致性是比较复杂的。Zookeeper的读操作是SequentialConsistency，Zookeeper的写操作是linearizability。关于这个说法，Zookeeper的官方文档并没有写出来，但是在社区邮件群里面有详细的讨论。另外这个观点在ModularCompositionofCoordinationServices中关于Zookeeper的论文中也有提到（这篇论文不是Zookeeper的主流论文，但是综合分析了Zookeeper的特点，以及跨机房的解决方案Zookeeper的多活改造也参考了本文的一些观点）。我们可以这样理解Zookeeper。从整体上（读操作+写操作）是SequentialConsistency，写操作实现了线性化。通过简单的推理，我们可以得出结论，Lamport论文中的小例子在Zookeeper中也是如此。我们可以这样实现分布式锁。但是Zookeeper官方推荐的分布式实现方式并没有采用这种方式，而是利用Zookeeper的线性化特性来实现分布式锁。Zookeeper为什么要实现顺序一致性？Zookeeper的核心功能是作为一个协调服务，即分布式锁服务。在分布式环境下，Zookeeper本身如何“天生正确”？没有其他的同步机制可以保证Zookeeper是正确的，所以Zookeeper只要实现SequentialConsistency，就可以自己保证正确性，从而对外提供锁服务。作者：陈东明简介：饿了么北京技术中心架构组组长，负责饿了么产品线架构设计和基础设施开发。前百度架构师，负责百度即时通讯产品的架构设计。具有丰富的大型系统建设和基础设施研发经验，擅长复杂业务需求下的大规模并发和分布式系统设计和持续优化。
