Paxos 算法Paxos 算法是 Leslie Lamport 于1990年提出的一种基于消息传递且具有高度容错特性的一致性算法。Paxos 算法目前在 Google 的 Chubby、MegaStore、Spanner 等系统中得到了应用，Hadoop 中的 ZooKeeper 也使用了 Paxos 算法。
在 Paxos 算法中，分为4种角色：
- Proposer ：提议者
- Acceptor：决策者
- Client：产生议题者
- Learner：最终决策学习者
算法可以分为两个阶段来执行：
阶段1- Proposer 选择一个议案编号 n，向 acceptor 的多数派发送编号也为 n 的 prepare 请求。
- Acceptor：如果接收到的 prepare 请求的编号 n 大于它已经回应的任何prepare 请求，它就回应已经批准的编号最高的议案（如果有的话），并承诺不再回应任何编号小于 n 的议案；
阶段2- Proposer：如果收到了多数 acceptor 对 prepare 请求（编号为 n）的回应，它就向这些 acceptor 发送议案{n, v}的 accept 请求，其中 v 是所有回应中编号最高的议案的决议，或者是 proposer 选择的值，如果回应说还没有议案。
- Acceptor：如果收到了议案{n, v}的 accept 请求，它就批准该议案，除非它已经回应了一个编号大于 n 的议案。
- Proposer 可以提出多个议案，只要它遵循上面的算法。它可以在任何时刻放弃一个议案。（这不会破坏正确性，即使在议案被放弃后，议案的请求或者回应消息才到达目标）如果其它的 proposer 已经开始提出更高编号的议案，那么最好能放弃当前的议案。因此，如果 acceptor 忽略一个 prepare 或者 accept 请求（因为已经收到了更高编号的 prepare 请求），它应该告知 proposer 放弃议案。这是一个性能优化，而不影响正确性。
|
