前言
春节在家闲着没事看了几篇论文，把一致性协议的几篇论文都过了一遍。在看这些论文之前，我一直有一些疑惑，比如同样是有Leader和两阶段提交，Zookeeper的ZAB协议和Raft有什么不同，Paxos协议到底要怎样才能用在实际工程中，这些问题我都在这些论文中找到了答案。接下来，我将尝试以自己的语言给大家讲讲这些协议，使大家能够理解这些算法。同时，我自己也有些疑问，我会在我的阐述中提出，也欢迎大家一起讨论。水平有限，文中难免会有一些纰漏门也欢迎大家指出。
逻辑时钟
逻辑时钟其实算不上是一个一致性协议，它是Lamport大神在1987年就提出来的一个想法，用来解决分布式系统中，不同的机器时钟不一致可能带来的问题。在单机系统中，我们用机器的时间来标识事件，就可以非常清晰地知道两个不同事件的发生次序。但是在分布式系统中，由于每台机器的时间可能存在误差，无法通过物理时钟来准确分辨两个事件发生的先后顺序。但实际上，在分布式系统中，只有两个发生关联的事件，我们才会去关心两者的先来后到关系。比如说两个事务，一个修改了rowa，一个修改了rowb，他们两个谁先发生，谁后发生，其实我们并不关心。那所谓逻辑时钟，就是用来定义两个关联事件的发生次序，即‘happens before’。而对于不关联的事件，逻辑时钟并不能决定其先后，所以说这种‘happens before’的关系，是一种偏序关系。
图和例子来自于这篇博客
此图中，箭头表示进程间通讯，ABC分别代表分布式系统中的三个进程。
逻辑时钟的算法其实很简单：每个事件对应一个Lamport时间戳，初始值为0
如果事件在节点内发生，时间戳加1
如果事件属于发送事件，时间戳加1并在消息中带上该时间戳
如果事件属于接收事件，时间戳 = Max(本地时间戳，消息中的时间戳) + 1
这样，所有关联的发送接收事件，我们都能保证发送事件的时间戳小于接收事件。如果两个事件之间没有关联，比如说A3和B5，他们的逻辑时间一样。正是由于他们没有关系，我们可以随意约定他们之间的发生顺序。比如说我们规定，当Lamport时间戳一样时，A进程的事件发生早于B进程早于C进程，这样我们可以得出A3 ‘happens before’ B5。而实际在物理世界中，明显B5是要早于A3发生的，但这都没有关系。
逻辑时钟貌似目前并没有被广泛的应用，除了DynamoDB使用了vector clock来解决多版本的先后问题（如果有其他实际应用的话请指出，可能是我孤陋寡闻了），Google的Spanner 也是采用物理的原子时钟来解决时钟问题。但是从Larmport大师的逻辑时钟算法上，已经可以看到一些一致性协议的影子。
Replicated State Machine
说到一致性协议，我们通常就会讲到复制状态机。因为通常我们会用复制状态机加上一致性协议算法来解决分布式系统中的高可用和容错。许多分布式系统，都是采用复制状态机来进行副本之间的数据同步，比如HDFS，Chubby和Zookeeper。
所谓复制状态机，就是在分布式系统的每一个实例副本中，都维持一个持久化的日志，然后用一定的一致性协议算法，保证每个实例的这个log都完全保持一致，这样，实例内部的状态机按照日志的顺序回放日志中的每一条命令，这样客户端来读时，在每个副本上都能读到一样的数据。复制状态机的核心就是图中 的Consensus模块，即今天我们要讨论的Paxos，ZAB，Raft等一致性协议算法。
Paxos
Paxos是Lamport大神在90年代提出的一致性协议算法，大家一直都觉得难懂，所以Lamport在2001又发表了一篇新的论文《Paxos made simple》，在文中他自己说Paxos是世界上最简单的一致性算法，非常容易懂……但是业界还是一致认为Paxos比较难以理解。在我看过Lamport大神的论文后，我觉得，除去复杂的正确性论证过程，Paxos协议本身还是比较好理解的。但是，Paxos协议还是过于理论，离具体的工程实践还有太远的距离。我一开始看Paxos协议的时候也是一头雾水，看来看去发现Paxos协议只是为了单次事件答成一致，而且答成一致后的值无法再被修改，怎么用Paxos去实现复制状态机呢？另外，Paxos协议答成一致的值只有Propose和部分follower知道，这协议到底怎么用……但是，如果你只是把Paxos协议当做一个理论去看，而不是考虑实际工程上会遇到什么问题的话，会容易理解的多。Lamport的论文中对StateMachine的应用只有一个大概的想法，并没有具体的实现逻辑，想要直接把Paxos放到复制状态机里使用是不可能的，得在Paxos上补充很多的东西。这些是为什么Paxos有这么多的变种。
Basic-Paxos
Basic-Paxos即Lamport最初提出的Paxos算法，其实很简单，用三言两语就可以讲完，下面我尝试着用我自己的语言描述下Paxos协议，然后会举出一个例子。要理解Paxos，只要记住一点就好了，Paxos只能为一个值形成共识，一旦Propose被确定，之后值永远不会变，也就是说整个Paxos Group只会接受一个提案（或者说接受多个提案，但这些提案的值都一样）。至于怎么才能接受多个值来形成复制状态机，大家可以看下一节Multi-Paxos.
Paxos协议中是没有Leader这个概念的，除去Learner（只是学习Propose的结果，我们可以不去讨论这个角色），只有Proposer和Acceptor。Paxos并且允许多个Proposer同时提案。Proposer要提出一个值让所有Acceptor答成一个共识。首先是Prepare阶段，Proposer会给出一个ProposeID n（注意，此阶段Proposer不会把值传给Acceptor）给每个Acceptor，如果某个Acceptor发现自己从来没有接收过大于等于n的Proposer，则会回复Proposer，同时承诺不再接收ProposeID小于等于n的提议的Prepare。如果这个Acceptor已经承诺过比n更大的propose，则不会回复Proposer。如果Acceptor之前已经Accept了（完成了第二个阶段）一个小于n的Propose，则会把这个Propose的值返回给Propose，否则会返回一个null值。当Proposer收到大于半数的Acceptor的回复后，就可以开始第二阶段accept阶段。但是这个阶段Propose能够提出的值是受限的，只有它收到的回复中不含有之前Propose的值，他才能*提出一个新的value，否则只能是用回复中Propose最大的值做为提议的值。Proposer用这个值和ProposeID n对每个Acceptor发起Accept请求。也就是说就算Proposer之前已经得到过acceptor的承诺，但是在accept发起之前，Acceptor可能给了proposeID更高的Propose承诺，导致accept失败。也就是说由于有多个Proposer的存在，虽然第一阶段成功，第二阶段仍然可能会被拒绝掉。
下面我举一个例子，这个例子来源于这篇博客
假设有Server1，Server2， Server3三个服务器，他们都想通过Paxos协议，让所有人答成一致他们是leader，这些Server都是Proposer角色，他们的提案的值就是他们自己server的名字。他们要获取Acceptor1~3这三个成员同意。首先Server2发起一个提案【1】,也就是说ProposeID为1，接下来Server1发起来一个提案【2】,Server3发起一个提案【3】.
首先是Prepare阶段：
假设这时Server1发送的消息先到达acceptor1和acceptor2，它们都没有接收过请求，所以接收该请求并返回【2，null】给Server1，同时承诺不再接受编号小于2的请求；
紧接着，Server2的消息到达acceptor2和acceptor3，acceptor3没有接受过请求，所以返回proposer2 【1，null】，并承诺不再接受编号小于1的消息。而acceptor2已经接受Server1的请求并承诺不再接收编号小于2的请求，所以acceptor2拒绝Server2的请求；
最后，Server3的消息到达acceptor2和acceptor3，它们都接受过提议，但编号3的消息大于acceptor2已接受的2和acceptor3已接受的1，所以他们都接受该提议，并返回Server3 【3，null】；
此时，Server2没有收到过半的回复，所以重新取得编号4，并发送给acceptor2和acceptor3，此时编号4大于它们已接受的提案编号3，所以接受该提案，并返回Server2 【4，null】。
接下来进入Accept阶段，
Server3收到半数以上（2个）的回复，并且返回的value为null，所以，Server3提交了【3，server3】的提案。
Server1在Prepare阶段也收到过半回复，返回的value为null，所以Server1提交了【2，server1】的提案。
Server2也收到过半回复，返回的value为null，所以Server2提交了【4，server2】的提案。
Acceptor1和acceptor2接收到Server1的提案【2，server1】，acceptor1通过该请求，acceptor2承诺不再接受编号小于4的提案，所以拒绝；
Acceptor2和acceptor3接收到Server2的提案【4，server2】，都通过该提案；
Acceptor2和acceptor3接收到Server3的提案【3，server3】，它们都承诺不再接受编号小于4的提案，所以都拒绝。
此时，过半的acceptor（acceptor2和acceptor3）都接受了提案【4，server2】，learner感知到提案的通过，learner开始学习提案，所以server2成为最终的leader。
Multi-Paxos
刚才我讲了，Paxos还过于理论，无法直接用到复制状态机中，总的来说，有以下几个原因
- Paxos只能确定一个值，无法用做Log的连续复制
- 由于有多个Proposer，可能会出现活锁，如我在上面举的例子中，Server2的一共提了两次Propose才最终让提案通过，极端情况下，次数可能会更多
- 提案的最终结果可能只有部分Acceptor知晓，没法达到复制状态机每个instance都必须有完全一致log的需求。
那么其实Multi-Paxos，其实就是为了解决上述三个问题，使Paxos协议能够实际使用在状态机中。解决第一个问题其实很简单。为Log Entry每个index的值都是用一个独立的Paxos instance。解决第二个问题也很简答，让一个Paxos group中不要有多个Proposer，在写入时先用Paxos协议选出一个leader（如我上面的例子），然后之后只由这个leader做写入，就可以避免活锁问题。并且，有了单一的leader之后，我们还可以省略掉大部分的prepare过程。只需要在leader当选后做一次prepare，所有Acceptor都没有接受过其他Leader的prepare请求，那每次写入，都可以直接进行Accept，除非有Acceptor拒绝，这说明有新的leader在写入。为了解决第三个问题，Multi-Paxos给每个Server引入了一个firstUnchosenIndex，让leader能够向向每个Acceptor同步被选中的值。解决这些问题之后Paxos就可以用于实际工程了。
Paxos到目前已经有了很多的补充和变种，实际上，之后我要讨论的ZAB也好，Raft也好，都可以看做是对Paxos的修改和变种，另外还有一句流传甚广的话，“世上只有一种一致性算法，那就是Paxos”。
ZAB
ZAB即Zookeeper Atomic BoardCast，是Zookeeper中使用的一致性协议。ZAB是Zookeeper的专用协议，与Zookeeper强绑定，并没有抽离成独立的库，因此它的应用也不是很广泛，仅限于Zookeeper。但ZAB协议的论文中对ZAB协议进行了详细的证明，证明ZAB协议是能够严格满足一致性要求的。
ZAB随着Zookeeper诞生于2007年，此时Raft协议还没有发明，根据ZAB的论文，之所以Zookeeper没有直接使用Paxos而是自己造*，是因为他们认为Paxos并不能满足他们的要求。比如Paxos允许多个proposer，可能会造成客户端提交的多个命令没法按照FIFO次序执行。同时在恢复过程中，有一些follower的数据不全。这些断论都是基于最原始的Paxos协议的，实际上后来一些Paxos的变种，比如Multi-Paxos已经解决了这些问题。当然我们只能站在历史的角度去看待这个问题，由于当时的Paxos并不能很好的解决这些问题，因此Zookeeper的开发者创造了一个新的一致性协议ZAB。
ZAB其实和后来的Raft非常像，有选主过程，有恢复过程，写入也是两阶段提交，先从leader发起一轮投票，获得超过半数同意后，再发起一次commit。ZAB中每个主的epoch number其实就相当于我接下来要讲的Raft中的term。只不过ZAB中把这个epoch number和transition number组成了一个zxid存在了每个entry中。
ZAB在做log复制时，两阶段提交时，一个阶段是投票阶段，只要收到过半数的同意票就可以，这个阶段并不会真正把数据传输给follower，实际作用是保证当时有超过半数的机器是没有挂掉，或者在同一个网络分区里的。第二个阶段commit，才会把数据传输给每个follower，每个follower（包括leader）再把数据追加到log里，这次写操作就算完成。如果第一个阶段投票成功，第二个阶段有follower挂掉，也没有关系，重启后leader也会保证follower数据和leader对其。如果commit阶段leader挂掉，如果这次写操作已经在至少一个follower上commit了，那这个follower一定会被选为leader，因为他的zxid是最大的，那么他选为leader后，会让所有follower都commit这条消息。如果leader挂时没有follower commit这条消息，那么这个写入就当做没写完。
由于只有在commit的时候才需要追加写日志，因此ZAB的log，只需要append-only的能力，就可以了。
另外，ZAB支持在从replica里做stale read，如果要做强一致的读，可以用sync read，原理也是先发起一次虚拟的写操作，到不做任何写入，等这个操作完成后，本地也commit了这次sync操作，再在本地replica上读，能够保证读到sync这个时间点前所有的正确数据，而Raft所有的读和写都是经过主节点的
Raft
Raft是斯坦福大学在2014年提出的一种新的一致性协议。作者表示之所以要设计一种全新的一致性协议，是因为Paxos实在太难理解，而且Paxos只是一个理论，离实际的工程实现还有很远的路。因此作者狠狠地吐槽了Paxos一把：
- Paxos协议中，是不需要Leader的，每个Proposer都可以提出一个propose。相比Raft这种一开始设计时就把选主和协议达成一致分开相比，Paxos等于是把选主和propose阶段杂糅在了一起，造成Paxos比较难以理解。
- 最原始的Paxos协议只是对单一的一次事件答成一致，一旦这个值被确定，就无法被更改，而在我们的现实生活中，包括我们数据库的一致性，都需要连续地对log entry的值答成一致，所以单单理解Paxos协议本身是不够的，我们还需要对Paxos协议进行改进和补充，才能真正把Paxos协议应用到工程中。而对Paxos协议的补充本身又非常复杂，而且虽然Paxos协议被Lamport证明过，而添加了这些补充后，这些基于Paxos的改进算法，如Multi-Paxos，又是未经证明的。
- 第三个槽点是Paxos协议只提供了一个非常粗略的描述，导致后续每一个对Paxos的改进，以及使用Paxos的工程，如Google的Chubby，都是自己实现了一套工程来解决Paxos中的一些具体问题。而像Chubby的实现细节其实并没有公开。也就是说要想在自己的工程中使用Paxos，基本上每个人都需要自己定制和实现一套适合自己的Paxos协议。
因此，Raft的作者在设计Raft的时候，有一个非常明确的目标，就是让这个协议能够更好的理解，在设计Raft的过程中，如果遇到有多种方案可以选择的，就选择更加容易理解的那个。作者举了一个例子。在Raft的选主阶段，本来可以给每个server附上一个id,大家都去投id最大的那个server做leader，会更快地达成一致（类似ZAB协议），但这个方案又增加了一个serverid的概念，同时在高id的server挂掉时，低id的server要想成为主必须有一个等待时间，影响可用性。因此Raft的选主使用了一个非常简单的方案：每个server都随机sleep一段时间，最早醒过来的server来发起一次投票，获取了大多数投票即可为主。在通常的网络环境下，最早发起投票的server也会最早收到其他server的赞成票，因此基本上只需要一轮投票就可以决出leader。整个选主过程非常简单明了。
除了选主，整个Raft协议的设计都非常简单。leader和follower之间的交互（如果不考虑snapshot和改变成员数量）一共只有2个RPC call。其中一个还是选主时才需要的RequestVote。也就是说所有的数据交互，都只由AppendEntries 这一个RPC完成。
理解Raft算法，首先要理解Term这个概念。每个leader都有自己的Term，而且这个term会带到log的每个entry中去，来代表这个entry是哪个leader term时期写入的。另外Term相当于一个lease。如果在规定的时间内leader没有发送心跳（心跳也是AppendEntries这个RPC call）,Follower就会认为leader已经挂掉，会把自己收到过的最高的Term加上1做为新的term去发起一轮选举。如果参选人的term还没自己的高的话，follower会投反对票，保证选出来的新leader的term是最高的。如果在time out周期内没人获得足够的选票（这是有可能的），则follower会在term上再加上1去做新的投票请求，直到选出leader为止。最初的raft是用c语言实现的，这个timeout时间可以设置的非常短，通常在几十ms，因此在raft协议中，leader挂掉之后基本在几十ms就能够被检测发现，故障恢复时间可以做到非常短。而像用Java实现的Raft库，如Ratis，考虑到GC时间，我估计这个超时时间没法设置这么短。
在Leader做写入时也是一个两阶段提交的过程。首先leader会把在自己的log中找到第一个空位index写入，并通过AppendEntries这个RPC把这个entry的值发给每个follower，如果收到半数以上的follower（包括自己）回复true，则再下一个AppendEntries中，leader会把committedIndex加1，代表写入的这个entry已经被提交。如在下图中，leader将x=4写入index=8的这个entry中，并把他发送给了所有follower，在收到第一台（自己），第三台，第五台（图中没有画index=8的entry，但因为这台服务器之前所有的entry都和leader保持了一致，因此它一定会投同意），那么leader就获得了多数票，再下一个rpc中，会将Committed index往前挪一位，代表index<=8的所有entry都已经提交。至于第二台和第四台服务器，log内容已经明显落后，这要么是因为前几次rpc没有成功。leader会无限重试直到这些follower和leader的日志追平。另外一个可能是这两台服务器重启过，处于恢复状态。那么这两台服务器在收到写入index=8的RPC时，follower也会把上一个entry的term和index发给他们。也就是说prevLogIndex=7，prevLogTerm=3这个信息会发给第二台服务器，那么对于第二台服务器，index=7的entry是空的，也就是log和leader不一致，他会返回一个false给leader，leader会不停地从后往前遍历，直到找到一个entry与第二台服务器一致的，从这个点开始重新把leader的log内容发送给该follower，即可完成恢复。raft协议保证了所有成员的replicated log中每个index位置，如果他们的term一致，内容也一定一致。如果不一致，leader一定会把这个index的内容改写成和leader一致。
其实经过刚才我的一些描述，基本上就已经把Raft的选主，写入流程和恢复基本上都讲完了。从这里，我们可以看出Raft一些非常有意思的地方。
第一个有意思的地方是Raft的log的entry是可能被修改的，比如一个follower接收了一个leader的prepare请求，把值写入了一个index，而这个leader挂掉，新选出的leader可能会重新使用这个index，那么这个follower的相应index的内容，会被改写成新的内容。这样就造成了两个问题，首先第一个，raft的log无法在append-only的文件或者文件系统上去实现，而像ZAB，Paxos协议，log只会追加，只要求文件系统有append的能力即可，不需要随机访问修改能力。
第二个有意思的地方是，为了简单，Raft中只维护了一个Committed index，也就是任何小于等于这个committedIndex的entry，都是被认为是commit过的。这样就会造成在写入过程中，在leader获得大多数选票之前挂掉（或者leader在写完自己的log之后还没来得及通知到任何follower就挂掉），重启后如果这个server继续被选为leader，这个值仍然会被commit永久生效。因为leader的log中有这个值，leader一定会保证所有的follower的log都和自己保持一致。而后续的写入在增长committedIndex后，这个值也默认被commit了。
举例来说，现在有5台服务器，其中S1为leader，但是当他在为index=1的entry执行写入时，先写到了自己的log中，还没来得及通知其他server append entry就宕机了。
当S1重启后，任然有可能被重新当选leader，当S1重新当选leader后，仍然会把index=1的这个entry复制给每台服务器（但是不会往前移动Committed index）
此时S1又发生一次写入，这次写入完成后，会把Committed index移动到2的位置，因此index=1的entry也被认为已经commit了。
这个行为有点奇怪，因为这样等于raft会让一个没有获得大多数人同意的值最终commit。这个行为取决于leader，如果上面的例子中S1重启后没有被选为leader，index=1的entry内容会被新leader的内容覆盖，从而不会提交未经过表决的内容。
虽然说这个行为是有点奇怪，但是不会造成任何问题，因为leader和follower还是会保持一致，而且在写入过程中leader挂掉，对客户端来说是本来就是一个未决语义，raft论文中也指出，如果用户想要exactly once的语义，可以在写入的时候加入一个类似uuid的东西，在写入之前leader查下这个uuid是否已经写入。那么在一定程度上，可以保证exactly once的语义。
Raft的论文中也比较了ZAB的算法，文中说ZAB协议的一个缺点是在恢复阶段需要leader和follower来回交换数据，这里我没太明白，据我理解，ZAB在重新选主的过程中，会选择Zxid最大的那个从成为主，而其他follower会从leader这里补全数据，并不会出现leader从follower节点补数据这一说。
后话
目前，经过改进的Paxos协议已经用在了许多分布式产品中，比如说Chubby，PaxosStore，阿里云的X-DB，以及蚂蚁的OceanBase，都选用了Paxos协议，但他们都多多少少做了一些补充和改进。而像Raft协议，普遍认为Raft协议只能顺序commit entry，性能没有Paxos好，但是TiKV中使用了Raft，其公开的文章宣传对Raft做了非常多的优化，使Raft的性能变的非常可观。阿里的另外一个数据库PolarDB，也是使用了改进版的Parallel-Raft，使Raft实现了并行提交的能力。相信未来会有更多的基于Paxos/Raft的产品会面世，同时也对Raft/Paxos也会有更多的改进。
参考文献
- 《Time, clocks, and the ordering of events in a distributed system》
- 《Implementing fault-tolerant services using the state machine approach- A tutorial》
- 《Paxos Made Simple》
- 《Paxos made live- An engineering perspective》
- 《Multi-Paxos》（Standford大学的一个ppt）
- 《Zab- High-performance broadcast for primary-backup systems》
- 《In search of an understandable consensus algorithm》（raft）