本文是工程实践的一篇总结，上图为达成共识。

在分布式系统中，由于机器可能宕机，网络可能短连等许多问题，所以如何保证多个副本之间的一致性成为了最重要的问题之一，而Paxos算法就是解决这个问题的算法。

Basic-Paxos

Basic Paxos就是Lamport在Paxos Made Simple中提出的最初的Paxos算法。

Basic Paxos允许多个Proposer和多个Acceptor，同时允许一个节点兼任两个角色。

这个算法包含两个部分：一个是Prepare阶段，二是Acceptor阶段。

在Prepare阶段，多个Proposer可能提出多个提案，算法会选择具有最大id的提案，并且将该id记录在本地。这里，我们可以认为Prepare阶段的作用是选出“最新”的提案，并且在Acceptor阶段尝试提交这个提案。

当提案的Proposer收到Quorum个确认之后，Proposer就会进入Accept阶段。

在Accept阶段，Acceptor会根据本地记录的提案的最大id来判断是否接受该提案，这一步会拒绝非“最新”的提案。当Proposer在Acceptor阶段收到Quorum个确认之后，就认为共识已经达成了。

Basic Paxos最明显的优点是解决了分布式系统中的共识问题。

Basic Paxos的缺点则是每次Paxos算法的运行需要经历两个阶段，这中间需要多次网络IO，而且每次算法只能确定一个值。这两个问题使得Basic Paxos算法的效率很低。所以就催生了Multi-Paxos。

Multi-Paxos

Multi-Paxos的基本想法是：Prepare阶段的作用是选出“最新”的提案，而在实际的环境中，针对一个值或者一条命令，并不会在同一时间出现两种提案，也就是说不会在Prepare阶段中相互争抢。那么就可以使用一台机器作为Leader去接受客户端的请求，同时将该请求作为提案，直接进入Accept阶段。

然而，Leader的引入也造成了一个问题：在Basic Paxos中，由于有2f+1个Proposer，所以能容忍f个机器宕机。但是在Multi-Paxos中，由于只有一个Leader，那么必须要考虑怎么处理Leader宕机的情况。

这里就需要Leader Election的机制，当检测到Leader宕机以后，就会发起这个流程，Leader Election其实也是一个共识问题，所以使用的算法仍然是Basic Paxos。当Leader Election结束以后，会有新的Leader代替旧的Leader继续运行。

几乎所有的工业级软件使用的共识性算法都是Multi-Paxos，但是另一方面，因为Multi-Paxos只是一个模糊的概念，所以没有一个统一的规范，所以，我认为只要是实现了Paxos算法并且使用了Leader机制的实现都可以称为Multi-Paxos。

Multi-Paxos使用Leader机制取代了Prepare阶段，将网络IO减少了一半，同时实现了能够连续地确定值，大大提高的Basic Paxos的效率。

但是，就像我们上面提到的，Multi-Paxos只是模糊的概念，各有各的实现，而彼此之间的实现细节差异也很大。

Raft

Raft是由Diego Ongaro提出的共识性算法，虽然有很多人认为它和Paxos是两种不同的算法，但我更倾向于认为它是Paxos的一种实现，更准确地说，Raft就是一种Multi-Paxos。但是Raft更加地清晰易懂，只要按照论文中的Figure 2要求，完全能够实现达到基本要求的Raft算法。

Raft中还引入了一些概念：

• 复制状态机：如果两台机器以同样的状态开始，并且按照同样的顺序执行相同的命令，那么在执行完同样数量的命令以后，两台机器的状态当前的状态也是相同的。
• Ack：Follower将命令写入本地后回复的确认
• Commit：当某个Log收到Quorum个Ack后，它的状态就是Commit的
• Apply：当某个Log状态为Commit，那么就可以被Apply到状态机中

Raft要求在正常运行的状态下，所有Follower（即之前的Acceptor）的Log都和Leader保持一致。为了实现这个目标，所有的Log在Ack时要保证之前的Log已经Ack了，所有的Log在Commit时要保证之前的Log已经Commit了，所有的Log在Apply时要保证之前的Log已经Apply了。

简单地说，就是要按序Ack，按序Commit，按序Apply。

另外，如果有Follower中的Log和Leader的Log不一致，就要删除该Log和其以后的所有Log，并把Leader的对应Log复制到Follower的对应位置上。

Raft还明确提出了检测Leader宕机的机制。Leader必须定期向Follower发送心跳信息，一旦在规定的时间内Follower没有收到信息，就认为和Leader断开连接（有可能是网络故障，也可能是Leader宕机），这时候Follower就会发起Leader Election，尝试选出新的Leader。

Raft的优点是给出了一套完全可行的实现共识的算法，同时考虑了使用状态机实现副本的数据一致。

Raft最为人诟病的是它按序Ack，Commit，Apply的要求。这样一来，虽然Raft使用Leader减少了一半的网络IO，但是Multi-Paxos是可以乱序Ack和Commit的，也就是说Raft不能是并行的。而这在广泛使用并行提高效率的网络中几乎是不可接受的。

ParallelRaft - PolarFS

在PolarFs的论文中，他们提出了ParallelRaft，但是要指出的是这种算法只适用于PolarFS。

ParallelRaft允许Log乱序Ack，Commit，Apply，但是，允许乱序Ack和Commit的后果就是Log的记录中会出现“洞”，那么在Apply时就会出现问题。这里，他们给出的方案是使用Look Aside Buffer作为”桥“跨越”洞“，“桥”中记录了之前N个文件块的修改情况，而且这个“桥”是全局的。

在论文中，他们指出桥的长度为2，简单来说，当执行到第i个Log时，如果之前i-1和i-2个Log缺失了，但是“桥”中记录表明，这两个Log涉及的文件块和第i个Log无关，那么可以直接执行第i个Log，中间的两个Log可以等到补全时再执行。

但是，这种方案过于激进，而且只适用于PolarFS。因为PolarFS有特别的组件PolarCtrl来监测这些信息，恰恰是因为这是一个文件系统，记录的信息没有那么多，而且写文件块也不算频繁才能使用这一方案。

如果想要用在数据库中，仅仅考虑对某一行的插入和更新两个操作就很难使用这个算法实现。

TiKV

在TiKV中，PingCAP给出了一种相对保守合理的优化。

在原始的Raft中，必须要完整地Ack，Commit，Apply完一个Log才能继续处理下一个Log。而TiKV则并行地发送AppendEntries请求，并不等到上一个Log被Apply结束，其他的要求和原始的Raft相同。虽然这是一个简单的优化，单个请求花费的时间也没有减少，但是由于是并行地处理请求，整个流程是流水线的，系统的吞吐量大大提高了。

另外，TiKV还提出了三种读数据的方案。

第一种方案类似于原生的Raft读。传统的读需要像写一样经历整个Raft流程，然后从Leader处读取数据。这里TiKV只要求发送Heartbeats确认自己是Leader就可以返回数据。

第二种方案使用了Lease机制。Leader和Follower达成一个共识：在Lease规定的时间内，不会发起Leader Election。由于Raft所有的写都经过Leader，所以只要不重新选举Leader，就可以保证Leader的数据是系统中最新的，那么在这段时间内，Leader可以直接响应写请求。

第三种方案类似于Zookeeper的sync()请求。Follower也能接受读请求，但是在响应前必须发送请求给Leader确认自己是否拥有最新的数据。如果是，那么就可以直接回应请求，如果没有，就必须等到Apply到和Leader一样的位置。

TIKV给出的写方案是我认为相对合理优秀的。另外，他的读的策略也有值得借鉴的地方。

共识算法优化的思考

杨新泰同学转达了Terrillma老师对目前算法的局限性的观察。这里，我阐述一下我的对这两个问题的思考。

对于Lease的思考

Lease机制的工作流程是这样的：Master将Lease颁发给某一台机器，这台机器会持有一段时间Lease，在这个时间段内，这台机器就是Leader。为了减少Leader的变更，在这段时间里，Leader每执行完一次命令就会更新Lease的时间。

简单地说，Lease机制主要有两个作用：一是代替Leader Election，由Master挑选一个Leader；二是实现Failure Detection。当一台机器不再持有Lease时，有两种可能，一是在他的任期内没有执行命令，二是这台机器宕机了。其中，前者的可能相当地小，所以可以认为如果Lease过期，大概率是因为宕机。

很直观地，Failure Detection的最大延迟就是Lease的持有时间。假设当一台机器在收到Lease后立刻宕机了，那么Master必须等到Lease时间结束才能检测到这个情况。

同样的，在使用Heartbeats检测宕机的解决方案中，最大的延迟是设定的超时时间。但是，由于这个时间是在Follower中的，所以和Leader的任期时间无关，可以设置得相对短一些。

所以，如果想要加快Leader的替换时间就必须减少宕机检测的时间。由于Lease设置的时间是针对Leader的，而Heartbeats是针对Follower的，所以可以使用Heartbeats来替换Lease。

但是，如果单纯使用Raft中的Heartbeats，就需要花费额外的时间进行Leader Election。

所以，我的初步的想法是：使用Master用较短的时间和Leader进行Heartbeats，但是Master又额外维护每个副本的最大Log Index。这里的信息由每个副本在写入WAL后，发送给Master。那么当Master发现Leader不可达时，就将拥有最大Index的设置为Leader，继续服务。

这里存在相当多的问题，比如一台机器在写入第i个Log后宕机了，没有给Master发送信息，而另一台机器只有i-1条Log，但是却被选为Leader，那么Leader的数据就不是最新的。诸如此类，我还没有深入地思考过。这仅仅是一个相当初步的想法。

对于并发写的思考

在重新读了Megastore以后，我认为它的写逻辑和原生的Raft类似。两者都是通过类似NextIndex确定下一个写入位置，从而保证了强一致性。但是因为必须等到nextIndex更新才能执行下一条命令，所以是非并发的。

这里，我想可以使用TiKV的优化方案，实现流水线式的并发写。

我们从复制状态机的角度重新考虑这个问题。状态机的状态取决于Apply的顺序和Apply了多少命令，而和Ack和Commit是无关的。所以从状态机的角度来说，它并不关心Log是否按序Ack和Commit。也就是说，两台机器的数据一致性只取决于Apply而不是Ack和Commit。

另外，由于Leader的完备性等性质，可以确定当前Term的Leader的数据是最正确最完整的。AppendEntries的失败有多重可能，总结起来就是两种，发出AppendEntries请求的Leader是过时的，或者，Follower的Log出现错误。也就是说只要是当前的Leader发出的AppendEntries，在大多数情况下是会最终成功的（除非Leader宕机了）。

所以，我们完全可以实现Log的乱序Ack和乱选Commit，而只要求Apply是按序的。这样，能够实现并发地处理网络请求，写WAL。理论上能大幅提高系统的吞吐量。

总结

以上的两个方案是相当粗糙的，没有深入思考过的方案。希望大家能够多多讨论可能出现的问题。我个人对Paxos的理解可能也有偏颇之处，希望大家能够多多指正。