分布式学习手记03 - Paxos 算法

Paxos 算法是一种基于消息传递且具有高度容错性的一致性算法

Paxos 算法需要解决的问题是如何在一个随时可能发生机器宕机或网络异常等情况的分布式系统中，快速正确地在集群内部对某个数据值达成一致。

该算法的前提是消息的可靠性，即排除拜占庭将军问题。

拜占庭将军问题

结论：在存在消息丢失的不可靠信道上试图通过消息传递的方式达到一致性几乎不可能。

维基百科 - 拜占庭将军问题

分部署系统可以通过校验算法等多种手段，避免消息不完整或被篡改，所以可以假设不存在拜占庭将军问题。

Paxos

Paxos 算法的目的是要保证，在系统中最终有一个提案被选定，并且，进程最终也能获取到这个被选定的提案。

所以过程上包含两个阶段：提案选定、提案获取；

角色上分为： Proposer、Acceptor、Learner

提案选定

1- Proposer 发出 Prepare 请求，编号 M_n

Proposer 选择新的提案编号 M_n，然后向某个 Acceptor 集合成员请求如下回应：

• Acceptor 承诺不再批准编号小于 M_n 的提案；

• 若该 Acceptor 已批准某个提案，就向 Proposer 反馈当前已经批准的编号小于 M_n，但为最大编号的那个提案的值

2- 若 Proposer 收到半数以上 Acceptor 的响应，即可产生编号为 M_n，Value 值为 V_n 的提案，V_n 取值有两种情况：

• Proposer 收到 Acceptor 反馈的最大编号提案的 Value，则 V_n 就设为这个值；

• 半数以上的 Acceptor 尚未批准过任何提案，响应中无反馈值，则 V_n 由 Proposer 自行设定

3- Proposer 发送 Accept 请求，即 [M_n,V_n] 提案，等待批准；

4- 如果 Acceptor 收到这个针对 [M_n,V_n] 提案的 Accept 请求，只要该 Acceptor 尚未对编号大于 M_n 的 Prepare 请求做出响应，就可以通过此提案。

总结

• 一个 Acceptor 必须批准它收到的第一个提案；—— 保证只有一个提案时也能选出结果

• 如果编号为 M₀，Value 值为 V₀ 的提案被选定了，则所有比此编号 M₀ 更高的，且被选定的提案，其 Value 值必须也是 V₀

提案获取

方案一

Acceptor 将批准的提案发送给所有 Learner，复杂度为 m x n；

方案二

Acceptor 将批准的提案发送给一个主 Learner，再由主 Learner 通知其他 Learner，复杂度降为 n + 1，但主 Learner 存在单点问题；

方案三

将主 Learner 扩展成一个集合。