共识算法系列：Paxos/Multi-Paxos算法关键点综述、优缺点总结

本文参考：

The Part-Time Parliament
Paxos Made Simple
Fast Paxos
Github Tencent/phxpaxos Wiki
Paxos之Multi-Paxos
分布式系列文章——Paxos算法原理与推导

---

其实对于所有的共识算法，无论是支持BFT容错（Byzantine fault tolerance允许有作恶/故障节点）的Pow、DPos、 PBFT等，还是仅仅支持CFT（Crash fault tolerant，只允许宕机）的Paxos、Raft等算法，我认为本质上就是一个投票选举的过程，都是为了选取“大多数”的决定，只是对于不同的共识算法，大家走的流程，要求大家做的事情不同而已。

Paxos是一种基于消息传递且具有高度容错特性的一致性算法，是Lamport老爷子的杰作。Paxos在分布式系统中非常常见的，但是，Paxos的论文读起来很抽象，以至于每次读起来都感觉是第一次读。所以我想在这篇文章中梳理记录一下Paxos的各种资料并尝试总结一下Paxos的一些特性。

直奔主题：

假设有多台服务器，他们的存储的数据决定了他们所处的状态，我们可以称之为状态机（只要初始状态一致，输入一致，那么引出的最终状态也是一致的），Paxos的目的就是通过一个协议让这多个服务器能达到一致的状态（复制状态机）。并且，Paxos允许在一定数量服务器不能工作时，整个多服务器系统还是能达到一致的状态。简单点来说：Paxos就是一个在异步通信环境，并容忍在只有多数派机器存活的情况下，仍然能完成一个一致性写入的协议。（多个副本确定同一个值，大家记录下来同一个值，那么就达到了一致性）。

如果我们能让这个系统确定有序的多个值（日志），那就可以像LevelDB的AppendLog一样有序的记录不同的操作，让这个系统提供分布式存储服务肯定也不是问题，Paxos就能做到。

对于网上各种Paxos的资料，目前来说，我觉得解释的最清楚的是微信团队PhxPaxos项目的Wiki，里面解释了Paxos协议的核心目的，并从整体框架的角度说明白了Paxos的协议逻辑，还有朴素Paxos的一致性证明，甚至还包括Multi-Paxos的优化原理，Leader和Master的作用和关系，动态成员变更等。

Wiki中有五篇相关文章，为了保证Wiki中原文的完整性和本文的简明性，我按照顺序介绍文章并贴出链接，并对我认为的关键点加以总结。

第一篇：微信自研生产级paxos类库PhxPaxos实现原理介绍(点我看原文)

这是一篇无需任何分布式以及paxos算法基础的人可以看懂的。它首先介绍了Paxos的目标——“确定一个值”、“确定多个值”、“有序的确定多个值”。此文还介绍的Paxos协议当中出现的几个角色：Acceptor、Proposer、Learner、State machine，并从框架的角度，说明了这些角色的作用，和耦合方式。在深入Paxos的核心算法之前可以读一下这篇文章，毕竟先明确目标和背景，再去理解算法/协议会更方便和直观一些。

第二篇：Paxos理论介绍(1): 朴素Paxos算法理论推导与证明(点我看原文)

重头戏来啦，这篇文章为我们介绍了朴素Paxos算法理论以及推导过程，这篇文章直接推导出了Paxos中 Prepare、Promise、Accepte这三个流程的原理。里面最重要的概念就是MaxVote的约束和原理，仔细跟着推导走一遍就不难理解，其实MaxVote也运用了类似Quorum机制中的鸽巢原理。

假设你已经读完原文，原文中用反证法来证明约束投票的一致性：当出现一轮投票B获得多数派通过后，那么不可能再出现新一轮投票B‘，使得B’bal > Bbal， 而B‘dec != Bdec。

这个其实从正面也很好推：因为B获得多数派通过，那么说明“大多数1”已经投过票，所以在之后计算MaxVote的时候，根据MaxVote的定义：取多轮投票里面这些成员（大多数2）小于这个编号的所有投票当中，最大编号的那个投票。而根据鸽巢原理，“大多数1”的成员和“大多数2”的成员必定存在一个非空的交集，所以MaxVote计算出来的B‘dec必定等于Bdec。

提醒：有一点需要明确，Paxos的本质是确定值，而不是确定一个“正确”的值，什么意思？Paxos协议只是一个工具，它并不在意值的“正确性“，只在意“一致性”也就是所谓的“共识”。假设一个分布式数据库用Paxos系统来保证一致性，它收到很多个proposals，有些proposals要求a写入“1+1=2”，而有的是要求a写入“1+1=3”，那么Paxos也只能用来保证其系统内的状态机写入了同一个proposal，从而使得让所有节点状态一致（无论写入的是1+1=2”还是“1+1=3”）。

所以，Prepare阶段的核心作用并不是让大多数节点“认可”这个数据，Prepare只是用来保证有大多数节点能响应，并且保证提案顺序的合法性而已（这是为了适应异步系统），为之后让“大多数”的Accepte打基础罢了。而MaxVote才是让proposals收敛的最重要约束。

第三篇：Paxos理论介绍(2): Multi-Paxos与Leader(点我看原文)

这篇文章说的非常清楚，Multi-Paxos通过改变Promised的生效范围至全局的Instance，来优化性能。这里值得注意的一点是，Multi-Paxos是一种优化措施，Leader可以看作是基于“Multi-Paxos这种优化措施”的优化措施。Multi-Paxos也可以没有Leader，它一样可以让所有节点对一个instance并行提交，只是这样Multi-Paxos的效率会退化成朴素Paxos罢了。无论是Multi-Paxos还是Leader，都不会影响系统的一致性，只是会让性能有些许不同。

关于Leader和Master的关系，在这里也可重点说一下，Leader的产生不需要选举：

• 如果一个节点向其他节点发送Accept请求，之后收到来自其他节点的Accept确认，则他会认为自己是Leader，并进行一段时间的拒绝其他节点的Prepare提交请求。

• 如果一个节点收到来自其它节点发送的Accept请求，那么他会认为请求方是Leader。并承诺一段时间内不会发起Prepare

双方的这种“默契”就构成，Leader的存在，所以Leader并不需要选举。这和Raft协议里面的选举算法原理本质上是相同的。而Master是必须得通过强一致性算法才能选举出来的。在PhxPaxos项目中他们没有使用类似Raft的Leader，而是直接使用了一致性更强的Master。

第四篇：Paxos理论介绍(3): Master选举(点我看原文)

假设我们已经完成了Paxos的算法，所以在完成Paxos工程上API设计后，我们可以直接使用Paxos算法本身用于选举，所以很好理解。作者在文中提了一个问题：

下图里面，为何Master任期的起始时间是从BeMaster算起，而不能是从BeMaster success算起？

本质上是为了达到这样一个目的：Master的单点性通过租约算法保证。由于恒定T(BeMaster) < T(Know other as master)，那么Master的过期时间肯定要比非Master节点认为Master过期的时间早，从而保证Master任期内，肯定不会出现其他节点尝试来抢占Master。

假设NodeA发起了BeMaster时为T1，NodeC收到A的BeMaster提议的时间为T2，NodeA想要确定自己是不是Master需要等待大家的回应，假设NodeA收到所有回应时为T3。根据paxos分布式算法的原理：在时间轴上T3 > T2 > T1，所以NodeA这个提议者未必能最早获得最终结果。所以，为了保证Master的过期时间比非Master节点认为Master过期的时间早，NodeA需要从发起BeMaster时开始计算任期。

第五篇：Paxos理论介绍(4): 动态成员变更(点我看原文)

这篇文章介绍了Paxos的动态成员变更，为了保证Bqrm的约束，我们同样使用Paxos算法本身去保证更换成员后的一致性。我们通过Paxos算法来决议一个成员变更操作，在理论上达到了原子变更的要求。但是如果系统本身支持多个instance基于窗口滑动并行提交，那么需要设置一个delay来保证窗口内的instance没有使用旧的成员节点。

总结

特征/优点:

• 高效，通信之间无须验证身份签名。

• Paxos算法有严格的数学证明，系统设计精妙。

• 容错性能: 允许半数以内的Acceptor失效、任意数量的Proposer失效，都能运行。 ⼀旦value值被确定，即使 半数以内的Acceptor失效，此值也可以被获取，并不会再修改。

缺点:

• 工程实践比较难，需要不同程度的工程优化，而有时工程设计的偏差会造成整个系统的不可用

• 只适用于permissioned systems(私有链)，只能容纳故障节点(fault)，不容纳作恶节点(corrupt)。(Crash Fault Tolerant), 不支持拜占庭容错(Byzantine Fault Tolerance)。

总结完毕，如文中出现错误或歧义，欢迎指正！如有不全面的地方也欢迎补充！