背景介绍

对于一个分布式系统，虽然每一个机器节点都可以明确知道自己进行事务操作过程的结果是成功或失败，但是无法直接获取其他分布式节点的操作结果。因此，当一个事务操作需要跨越多个分布式节点的时候，为了保持事务处理的ACID特性：

• 原子性（atomicity）
• 一致性（consistency）
• 隔离性（isolation）
• 容错性（durablity）

，需要引入一个被称为协调者（Coordinator）的组件来统一调度所有分布式节点的执行逻辑，这些被调度的分布式节点叫做参与者（Participant）。总之，由协调者来负责调度参与者的行为，并最终决定这些参与者是否要真正提交事务。
为了以容错方式达成一致，不可能要求所有服务器都100%达到一致状态，只需要超过半数的服务器达成一致就行了。
Paxos算法就是谷歌提出的一种基于消息传递且具有高度容错特性、一致性的算法。

下面展开的Paxos算法和Raft算法一般应用于中心化的分布式系统，或者受限应用的私有区块链。

一、Paxos算法

在Paxos算法中，有3种角色：

• Proposer
• Acceptor
• Learners

在具体实现中，一个进程可能同时充当多个角色，甚至三者都兼任。

还有一个很重要的概念——提案（Proposal）。最终要达成一致的value就在提案例。

1.阶段一

1）Proposer 选择一个提案编号N，然后向半数以上的Acceptor发送编号为N的Prepare请求

2）如果一个Acceptor收到一个编号为N的Prepare请求，且N大于该Acceptor已经响应过的所有Prepare请求的编号，那么它就会将它已经接收过的编号最大的提案（如果有的话）作为响应反馈给Proposer，同时该Acceptor承诺不再接收任何编号小于N的提案

2.阶段二

1）如果Proposer收到半数以上Acceptor对其编号为N的Prepare请求的响应，那么它就会发送一个针对[N, V]提案的Accept请求给半数以上的Acceptor

2）如果Acceptor收到一个针对编号为N的提案的Accept请求，只要该Acceptor没有对编号大于N的Prepare请求做出过响应，它就接收该提案

3.总结

Paxos算法的特点是一致性>可用性，由于这个算法比较复杂且难以理解，也不容易实现，所以有下面的Raft算法。

二、Raft算法

Raft本质上跟Paxos类似，在Raft中，在任何时候一个服务进程都可以扮演下面角色之一：

• Leader：处理所有客户端交互、日志复制等，一般一次只有一个Leader
• Follower：类似选民
• Candidate：候选人，可以被选为一个新的Leader

Raft算法的大致过程可以总结为：首先是Leader选举过程，其次在选举出来的Leader的基础上完成正常操作，例如日志复制和记账等。

• 1.任何一个服务器都可以成为一个Candidate，它向其他服务器Follower发出要求选举自己的请求；

• 2.其他服务器同意了，发出OK；

• 3.Candidate就成为了Leader，它可以向选民也就是Follower发出指令，比如进行日志复制；

• 4.以后通过心跳进行日志复制的通知；

• 5.一旦这个Leader宕机崩溃了，那么Follower中有一个成为Candidate，发出邀票选举；

• 6.Follower同意后，其成为Leader，继续承担日志复制等指导工作。