分布式应用中的一致性协议

在一个分布式系统中，需要一个规定来保证数据的一致性、各节点服务的容错性等等，这个规定就是一致性协议。常见的分布式协议有2PC、3PC、Paxos和raft等。

2PC

即Two-Phase Commit，二阶段提交。目前大多数的关系型数据库都是采用2PC协议来完成分布式事务处理的。

执行过程

2PC中包含两个角色协调者和参与者，其分为两个阶段：

阶段一，提交事务请求，也称投票阶段。

• 事务询问。协调者会向所有的参与者发送事务，询问是否可以执行事务提交操作，并开始等待各参与者的响应。
• 执行事务。各参与者执行事务操作，并将undo和redo信息记入事务日志中。
• 各参与者向协调者反馈事务询问的响应。如果参与者成功执行一事务操作， 反馈给协调者yes响应，表示事务可以执行；如果没有成功执行事务，就反馈no给协调者，表示事务不可执行。

阶段二，执行事务提交。

​ 在阶段二，协调者会根据各参与者的反馈情况决定最终是否可以进行事务提交操作。

• 发送提交请求。协调者会一一向参与者发送commit请求。
• 事务提交请求。当参与者收到commit请求后，会执行事务提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源。
• 反馈事务提交结果。参与者在完成事务提交之后，向协调者发送ack消息。
• 完成事务。协调者收到所有参与者反馈的ack消息后，完成事务。

中断事务，当参与者向协调者反馈了no响应，或者协调者在等待参与者反馈消息的过程中超时了，就会触发中断事务。

• 发送回滚请求。协调者向所有参与者发出rollback请求。
• 事务回滚。参与者收到rollback请求后，会复用在阶段一中记录的undo信息来执行回滚操作，并在完成回滚之后释放在整个事务执行期间占用的资源。
• 反馈事务回滚结果。参与者完成事务回滚之后，向协调者发送ack消息。
• 中断完成。协调者接收到所有参与者反馈的ack消息后，完成事务中断。

优缺点

优点：原理简单，实现方便。

缺点：同步阻塞、单点问题、数据不一致和没有完善的容错机制。

• 同步阻塞。在二阶段提交的执行过程中，所有参与该事务操作的逻辑都处于阻塞状态，即各个参与者在等待其他参与者响应的过程中，无法再进行其它操作。
• 单点问题。一旦协调者出现问题，整个二阶段的提交流程就无法正常地进行；并且其它参与者会一直处于锁定事务资源的状态中，无法继续完成事务操作。
• 数据不一致。在阶段二中，当协调者向所有参与者发送commit请求后，如果发生了局部的网络异常或者是协调者在尚未发送完commit请求之前自己崩溃了，导致最终只有部分参与者收到了commit。最终，只有收到commit请求的参与者才会进行事务的提交，整个分布式系统就会出现数据不一致的情况。
• 没有完善的容错机制。协调者在询问参与者事务提交的过程中，如果参与者由于种种原因没有返回消息，导致协调者不能获取 所有参与者的响应消息，协调者只能通过超时的机制来判断是否需要中断事务。2PC没有设计较为完善的容错机制 ，任意一个节点的失败都会导致整个事务的失败。

3PC

3PC即 Three-Phase Commit，是2PC的改进版，同样有两个角色协调者和参与者，不同的是将2PC的阶段一分成两步，所以它包含了三个阶段CanCommit、PreCommit和DoCommit。

CanCommit

• 事务询问。协调者向所有的参与者发送CanCommit请求，询问是否可以执行事务操作，然后等待参与者的响应。
• 参与者响应。参与者在收到协调者的CanCommit请求后，如果没有什么问题，就反馈yes，否则反馈no。

PreCommit

如果CanCommit正常进行，那么进入执行事务提交。

• 发送提交请求。协调者向所有参与者发送PreCommit请求，进入了Prepared阶段。
• 事务预提交。参与者接到PreCommit 请求后，会执行事务操作，并将undo和redo信息记录到事务日志中去。
• 参与者把事务执行的结果反馈给协调者。如果各参与者成功执行了事务操作，就反回ack响应，然后等待最终后Commit或abort的请求

如果第一步中有参与者返回了no，或者发生了超时，协调者就会中断事务

• 发送中断请求。协调者向所有参与者发送abort请求。
• 中断事务。对参与者而言，不管是收到abort请求还是在等待协调者的过程中发生了超时，其都会中断事务。

DoCommit

这一阶段才开始真正的事务提交。

执行提交。

• 发送提交请求。如果协调者收到了所有参与者ack 响应，就会向所有的参与者再次发送DoCommit请求。
• 事务提交。当参与者收到协调者的DoCommit请求后，开始正式执行事务的提交操作，并在完成提交之后释放在整个事务执行期间占用的事务资源。
• 反馈事务提交结果。参与者在完成事务提交之后 ，向协调者发送ack消息。
• 完成事务。协调者接收到所有参与者反馈的ack消息后，完成事务。

假如协调者在等待参与者的过程中发生了超时，或者有参与者返回了no的响应，那么协调者会中断事务。

• 发送中断请求。协调者向所有参与者发送abort请求。
• 事务回滚。参与者在收到abort请求后，会利用上一步在日志中记录的undo 信息来进行事务回滚操作，并释放在执行整个事务过程中占用的资源。
• 反馈事务回滚结果。 参与者在完成事务的回滚之后，向协调者发送ack响应。
• 中断事务。协调者收到所有的ack消息后，中断事务。

优缺点

3PC 相比2PC降低了参与者阻塞的范围，并能能够在出现故障后继续达到一致。

不过也引入了新的问题，在阶段二，如果发生局部网络的故障，协调者与个别参与者无法进行正常的通信，仍然会造成数据不一致的现象。

Paxos

2PC和3PC 都没有这样或那样的问题，Paxos的出现很好地解决了这一问题，是目前公认的解决分布式一致性问题最有效的算法之一。

Paxos中有3个参与者Proposer、Acceptor和Leaner，Proposer是发起提案的人，Acceptor是接受提案的人，Learner是信使在Proposer和Acceptor之间传送议案。在Paxos中有一些条件限制：

• 一个Acceptor必须批准他收到的第一个提案。
• 每个提案会有一个编号M，这个编号是全局递增的;同样每个提案本身也有一个值 Value。如果编号为M1的Value为V1的提案即[M1，V1]被选定了，那么所有比编号M1更高的，且被选定的提案，其值必须为V1。
  • 如果[M1，V1]被选定了，那么所以比M1更高的，那么所有比编号M1更高的，且被Acceptor选定的提案，其值必须为V1。
  • 如果[M1，V1]被选定了，往下产生的编号更高的提案，其Value都为V1。
  • 对如果[M1，V1]， 如果其被提出，肯定存在一个由半数以上的Acceptor组成的集合S,满足以下条件：S中不存在任何批准过编号大于M1的Acceptor；S中批准的所以编号小于M1的提案中，编号最大的那个的Value值也是V1。

执行过程

Paxos的执行相当于一次投票的选举过程，分为两个阶段。

阶段一

• Proper选择一个提案的编号M1,然后向Acceptor发送提案。
• 如果一个Acceptor收到提案M1，并且这个提案的编号大于自己之前处理过的所有的提案，那么它就会把它已经批准过的编号最大的提案返回给Proposer，同时该Proposer承诺不会再批准任何编号小于M1的提案。

阶段二

• 如果Proposer的提案受到半数以上的Acceptor的批准，那么他就会发送提案[M1, V1]的accept请求。V1是Proposer收到的响应中编号最大的提案的值，如果没有，则V1可以为任意值 。
• 当Acceptor收到提案时，如果他没有批准过大于其编号M1的提案，那么就可以批准M1。

当提案被半数Acceptror批准后，就会把这个提案发送给Learner，由Learner最后将提案传递下去，这样一个提案才算完成。

这篇文章 www.cnblogs.com/endsock/p/3… 中通过一个例子形象地描述了Paxos算法，在一定程度上有助于理解Paxos算法的原理。

但是这里也没有提到一个问题，就是当一个Acceptor接收到一个Proposer的提案时并响应时，有另外一个Proposer提了一个编号更高的提案，然后在Accetpor响应后又有另外一个Proposer提出编号更高的提案…这样会造成一个死循环。解决这个问题的方法就是建立一个主Proposer，在一个Proposer集合中只有一个Proposer能发出提案的请求给Acceptor。

优缺点

Paxos很好地解决分布式系统中的阻塞和单点故障的问题，但是Paxos的复杂性增加了它在工程实践中应用的难度。

raft

Raft是斯坦福的Diego Ongaro、John Ousterhout两个人以易懂（Understandability）为目标设计的一致性算法，在2013年发布了论文：《In Search of an Understandable Consensus Algorithm》从2013年发布到现在不过只有两年，到现在已经有了十多种语言的Raft算法实现框架，较为出名的有etcd，Google的Kubernetes也是用了etcd作为他的服务发现框架；由此可见易懂性是多么的重要。

在了解Raft之前，我们先了解Consensus一致性这个概念，它是指多个服务器在状态达成一致，但是在一个分布式系统中，因为各种意外可能，有的服务器可能会崩溃或变得不可靠，它就不能和其他服务器达成一致状态。这样就需要一种Consensus协议，一致性协议是为了确保容错性，也就是即使系统中有一两个服务器当机，也不会影响其处理过程。

为了以容错方式达成一致，我们不可能要求所有服务器100%都达成一致状态，只要超过半数的大多数服务器达成一致就可以了，假设有N台服务器，N/2 +1 就超过半数，代表大多数了。

Paxos和Raft都是为了实现Consensus一致性这个目标，这个过程如同选举一样，参选者需要说服大多数选民(服务器)投票给他，一旦选定后就跟随其操作。Paxos和Raft的区别在于选举的具体过程不同。

在Raft中，任何时候一个服务器可以扮演下面角色之一：

• Leader: 处理所有客户端交互，日志复制等，一般一次只有一个Leader.
• Follower: 类似选民，完全被动
• Candidate候选人: 类似Proposer律师，可以被选为一个新的领导人。

执行过程

Raft阶段分为两个，首先是选举过程，然后在选举出来的领导人带领进行正常操作，比如日志复制等。下面用图示展示这个过程：

• 任何一个服务器都可以成为一个候选者Candidate，它向其他服务器Follower发出要求选举自己的请求：
• 其他服务器同意了，发出OK。注意如果在这个过程中，有一个Follower当机，没有收到请求选举的要求，因此候选者可以自己选自己，只要达到N/2 + 1 的大多数票，候选人还是可以成为Leader的。
• 这样这个候选者就成为了Leader领导人，它可以向选民也就是Follower们发出指令，比如进行日志复制。
• 以后通过心跳进行日志复制的通知。
• 如果一旦这个Leader当机崩溃了，那么Follower中有一个成为候选者，发出邀票选举。
• Follower同意后，其成为Leader，继续承担日志复制等指导工作：

Splite Vote是因为如果同时有两个候选人向大家邀票，这时通过类似加时赛来解决，两个候选者在一段timeout比如300ms互相不服气的等待以后，因为双方得到的票数是一样的，一半对一半，那么在300ms以后，再由这两个候选者发出邀票，这时同时的概率大大降低，那么首先发出邀票的的候选者得到了大多数同意，成为领导者Leader，而另外一个候选者后来发出邀票时，那些Follower选民已经投票给第一个候选者，不能再投票给它，它就成为落选者了，最后这个落选者也成为普通Follower一员了。

动画演示: thesecretlivesofdata.com/raft/

优缺点

熟悉或了解分布性系统的开发者都知道一致性算法的重要性，Paxos一致性算法从90年提出到现在已经有二十几年了，而Paxos流程太过于繁杂实现起来也比较复杂，可能也是以为过于复杂 现在我听说过比较出名使用到Paxos的也就只是Chubby、libpaxos，搜了下发现Keyspace、BerkeleyDB数据库中也使用了该算法作为数据的一致性同步，虽然现在很广泛使用的Zookeeper也是基于Paxos算法来实现，但是Zookeeper使用的ZAB（Zookeeper Atomic Broadcast）协议对Paxos进行了很多的改进与优化，算法复杂我想会是制约他发展的一个重要原因；说了这么多只是为了要引出本篇文章的主角Raft一致性算法，没错Raft就是在这个背景下诞生的，文章开头也说到了Paxos最大的问题就是复杂，Raft一致性算法就是比Paxos简单又能实现Paxos所解决的问题的一致性算法。

参考资料：

• 从Paxos到zookeeper分布式一致性原理与实践
• www.jdon.com/artichect/r…
• blog.csdn.net/xu__cg/arti…