1988 年,Brian M. Oki 和 Barbara H. Liskov 在论文《Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems》中首次提出了解决 Paxos 问题的算法。
Paxos 能保证在超过一半的节点正常工作时,系统总能以较大概率达成共识。读者可以试着自己设计一套非拜占庭容错下基于消息传递的异步共识方案,会发现在满足各种约束情况下,算法过程总会十分类似 Paxos 的过程。这也是为何 Google Chubby 的作者 Mike Burrows 说:“这个世界上只有一种一致性算法,那就是 Paxos(There is only one consensus protocol, and that's Paxos)”。
接受者 i 收到提案编号 n,检查回复过的提案的最大编号 M_i。如果 n > M_i,则向提案者返回准备接受(accept)提交的最大编号的提案 P_i(如果还未接受过任何提案,则为空),并不再接受小于 n 的提案,同时更新 M_i = n。这一步是让接受者筛选出它收到的最大编号的提案,接下来只接受其后续提交。
提交阶段:
某个提案者如果收到大多数接受者的回复(表示大部分人收到了 n),则准备发出带有 n 的提交消息。如果收到的回复中带有提案 P_i(说明自己看到的信息过期),则替换选编号最大的 P_i 的值为提案值;否则指定一个新提案值。如果没收到大多数回复,则再次发出请求;
接受者 i 收到序号为 n 的提交消息,如果发现 n >= P_i 的序号,则接受提案,并更新 P_i 序号为 n。
一旦多数接受者接受了共同的提案值,则形成决议,成为最终确认。之后可以开始新一轮的提交确认。
需要注意,Paxos 并不一定能保证每一轮都能提交提案。
Raft 算法
Paxos 算法虽然给出了共识设计,但并没有讨论太多实现细节,也并不重视工程上的优化,因此后来在学术界和工程界出现了一些改进工作,包括 Fast Paxos、Multi-Paxos,Zookeeper Atomic Broadcast(ZAB)和 Raft 等。这些算法重点在于改进执行效率和可实现性。
其中,Raft 算法由斯坦福大学的 Diego Ongaro 和 John Ousterhout 于 2014 年在论文《In Search of an Understandable Consensus Algorithm》中提出,基于 Multi-Paxos 算法进行重新简化设计和实现,提高了工程实践性。Raft 算法的主要设计思想与 ZAB 类似,通过先选出领导节点来简化流程和提高效率。实现上解耦了领导者选举、日志复制和安全方面的需求,并通过约束减少了不确定性的状态空间。