浅谈 CAP 和 Paxos 共识算法( 二 ) 作者：郑勰

PaxosPaxos 模型试图探讨分布式共识问题的一个更一般的形式。
Lesile Lamport ， Latex 的发明者，提出了 Paxos 算法。他虚拟了一个叫做 Paxos 的希腊城邦，这个岛按照议会民主制的政治模式制定法律，但是没有人愿意将自己的全部时间和精力放在这件事上。所以无论是议员、议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议后者传递消息的时间。由于 Paxos 让人太难以理解， Lamport 觉得同行不能理解他的幽默感，于是后来又重新发表了朴实的算法描述版本《Paxos Made Simple》（#891d9af87884442fbf2adaa36b9f9454）。
文章插图
该共识算法就整体来说，存在两个阶段，如图，第一个阶段是提议，第二个阶段是决定。
分布式系统要做到 fault tolorence ，就需要共识模型，而节点达成共识，不仅需要节点之间的算法，还会取决于 client 的行为。比如即使副本系统使用 multi-paxos 在所有副本服务器上同步了日志序号，但如果 Client 被允许从非 Leader 节点写入数据，则整个副本系统仍然不是强一致的。
下面，重头戏来了，详细介绍 Paxos 。
角色介绍：
Client：系统外部角色，请求发起者。如民众。
Proposer: 接受 Client 请求，向集群提出提议（propose）。并在冲突发生时，起到冲突调节的作用。如议员，替民众提出议案。
Accpetor: 提议投票和接收者，只有在形成法定人数（Quorum ，即 Majority 多数派）时，提议才会最终被接受。如国会。
Learner: 提议接受者， backup ，备份，对集群的一致性没影响。如记录员。
步骤、阶段：
文章插图
1.Phase1a: Prepare
proposer 提出一个议案，编号为 N ， N 一定大于这个 proposer 之前提出的提案编号，请求 acceptor 的 quorum（大多数）接受。
2.Phase1b: Promise
如果 N 大于此 acceptor 之前接受的任何提案编号则接受，否则拒绝。
3.Phase2a: Accept
如果达到了多数派， proposer 会发出 accept 请求，此请求包含上一步的提案编号和提案内容。
4.Phase2b: Accepted
如果此 acceptor 在此期间没有收到任何大于 N 的提案，则接受此提案内容，否则忽略。
还记得上文中我们提到过，同步编号是非常重要的问题，绿色框出来的实际上就是同步编号的过程。通过这个编号，就知道每条操作日志的先后顺序。简单说来，第一阶段，获取编号，第二阶段，写入日志。可以看出来， Paxos 通过两轮交互，牺牲时间和性能来达到弥补一致性的问题。
现在我们考虑部分节点 down 掉的情景。
文章插图
由于是多数派 accptor 达成了一致，第一阶段仍然成功获得了编号，所有最终还是成功的。
考虑 proposer down 掉的情景。
文章插图
没关系，虽然第一个 proposer 失败，但下一个 proposer 用更大的提案编号，所以下一次 proposer 最终还是成功了，仍然保证了可用性和一致性。
潜在问题：活锁
文章插图
Paxos 存在活锁问题。如图，当第一个 proposer 在第一阶段发出请求，还没来得及后续的第二阶段请求，紧接着第二个 proposer 在第一阶段也发出请求，如果这样无穷无尽， acceptor 始终停留在决定顺序号的过程上，那大家谁也成功不了，遇到这样的问题，其实很好解决，如果发现顺序号被新的 proposer 更新了，则引入一个随机的等待的超时时间，这样就避免了多个 proposer 发生冲突的问题。
Multi Paxos
由于 Paxos 存在的问题：难实现、效率低（2 轮 rpc）、活锁。
因此又引入了 Multi Paxos ， Multi Paxos 引入 Leader ，也就是唯一的 proposer ，所有的请求都需经过此 Leader 。
文章插图
因为只有一个节点维护提案编号，这样，就省略了第一轮讨论提议编号的过程。
然后进一步简化角色。
文章插图
Servers 中第左边的就是 Proposer ，另外两个和自身充当 acceptor ，这样就更像我们真实的系统了。 Raft 和 ZAB 协议其实基本上和这个一致，两者的差别很小，就是心跳的方向不一样。