Paxos

简介

Paxos 协议是分布式系统中最著名的一致性协议，最早由 Lamport 在 1989 年发表，根据 Lamport 自己介绍，Paxos 名称来源与希腊的一个岛名。由于当时发表的 Paper 描述太过晦涩没有被人所注意，直到 1998 年在期刊上再次发表一篇论文 “The Part-Time Parliament” 才最终被业界所重视才流传开来。虽然如此，Paxos 还是不易理解，因此，后来 Lamport 又用白话文再写了一篇 “Paxos Made Simple” 的论文发表，人们才渐渐真正理解 Paxos 的原理。

我在美国念研究生的时候，专业核心方向便是分布式系统算法，那时候的课程几乎全是在学习这些大神的论文，课后的很多的 Projects 便是根据论文来实现他们论文中所描述的算法，这些基础性的论文大量来自于 Leslie Lamport 教授。

Paxos 协议

Paxos 协议其实真正理解起来不难，难的地方在我看来主要是很难与工程或者实践联系起来，造成了理解和体会上的分割。

这篇文章主要简单阐述 Paxos 的协议原理

Paxos 协议中一共有 3 中角色： Proposers, Acceptors, Learners

整个协议的过程分为两个阶段

第一阶段（Prepare Phase)：

（a）Proposer 选择一个 Number 和一个 Value，发送一个 Prepare Request 给大多数 Acceptors
（b）Acceptor 收到 Prepare Request 之后
如果当前 Number 小于已经 Promise 过的 Proposal 的 number，那么忽略请求（或者更好的处理是告知对方当前已经 Promise 过的 Number，以便对方下次可以提出一个更高的 Number 提高下次的通过概率）
如果当前 Number 大于已经 Promise 过的 Proposal 的 number，或者没有 Promise 过任何 Proposal，那么直接同意，Acceptor 做出 Promise，并且立刻告知对方。

总结，Prepare 有两个作用:

大的 proposal id 会 block 未完成的小的 proposal id 达成一致的过程，所以为了减少无效的 Prepare 请求，每次都选择比自己以往见过的 proposal id 更大的id。
一旦某个 value 达成一致，那么后续的 Prepare 都会找到这个 value 作为 accept 阶段的值可以看出，一次 Paxos 达成一致至少需要两次网络交互。

注意，Acceptor 需要记住两个值：
第一个是在 Prepare 阶段，需要记住 Promise 过的最高的 Number
第二个是在 Accept 阶段，需要记住已经 accept 过的最高的 Number，一旦有 accept request 过来的 number 小于之前已经 accept 过的最高 Number，就忽略或拒绝。

第二阶段（Accept Phase）

Propose 在提出 Prepare request 并收到大多数 acceptors 的 response 消息之后，就发送 accept request 给大多数的 Acceptors（这些 Acceptors 没必要都是上一阶段接收 prepare requests 的那些 Acceptors），并把所有收到的 resonse 中的 Number 值最大的对应的 Value 发送过去。
Acceptor 收到一个 accept request，如果该 number 的值大于等于之前回复过的 prepare request 中的 number 的值，就立刻接受，并且通知 Learners 去学习。

value 被大多数接受之前，每个Acceptor可以accept多个不同的值。但是，一旦一个value被majority accept(即value达成一致)，那么这个value就不会变了。因为Prepare阶段会将该value给找出来，随后Accept阶段会使用这个value，后续的所有的提案都会选择这个value。

最后还有个阶段，就是学习阶段，其流程非常简单：

一旦 accept 某个 proposal，就把该 proposal 告诉所有 learners，让他们学习这个 chosen value。
由于要告诉所有 learners，效率比较低，所以考虑一个专门（distinguished）的 learners group。

Paxos 的开源实现

https://github.com/cocagne/paxos

##### 参考： [paxos made simple][]