Paxos算法

如何达成共识

想象这样一个场景，某地出现突发事件，当地村委会、负责人等在积极研究和搜集解决该事件的解决方案，你也决定参与其中，提交提案，建议一些解决方法。为了和其他村民的提案做区分，你的提案还得包含一个提案编号，以起到唯一标识的作用。与你的做法类似，在Basic Paxos中，兰伯特也使用提案代表一个提议。不过提案中除了包含提案编号，还包含提议值。为了方便表示，使用[n,v]表示一个提案，其中n为提案编号，v为提议值。

强调一下，整个共识协商是分为两个阶段进行的(也就是前面提到的二阶段提交:准备阶段、接受阶段)，那么具体要如何协商呢?
我们假设客户端1的提案编号为1，客户端2的提案编号为5，并假设节点A、B先收到来自客户端1的准备请求，节点C先收到客户端2
的准备请求

1.准备节点

先来看第一个阶段，首先，客户端1、2作为提议者，分别向所有接受者发送包含提案编号的准备请求，如图所示。

需要注意的是，准备请求中不需要指定提案的值，只需要携带提案编号就可以了，这也是很多人容易产生误解的地方。接着，节点A、B收到提案编号为1的准备请求，节点C收到提案编号为5的准备请求后，将进行如图所示的处理。由于之前没有通过任何提案，所以，节点A、B将返回一个"尚无提案"的响应，也就是说，节点A和B在告诉提议者，我之前没有通过任何提案，并承诺以后不再响应提案编号小于或等于1的准备请求，也不会通过编号小于1的提案。节点C也是如此，它将返回一个"尚无提案"的响应，并承诺以后不再响应提案编号小于等于5的准备请求，也不会通过编号小于5的提案。另外，节点A、B收到提案编号为5的准备请求，节点C收到提案编号为1的准备请求后将进行如图所示的处理过程。当节点A、B收到提案编号为5的准备请求时，因为提案编号5大于它们之前响应的主备请求的提案编号1，而且两个节点都没有通过任何提案，所以，节点A、B.将返回一个"尚无提案"的响应，并承诺以后不再响应提案编号小于等于5的准备请求，也不会通过编号小于5的提案。当节点C收到提案编号为1的准备请求时，由于提案编号1小于它之前响应的准备请求的提案编号5，所以节点C将丢弃该准备请求，不做响应

注意

本质上而言，提案编号的大小代表着优先级，你可以这么理解，根据提案编号的大小，接受者保证3个承诺，具体来说:

• 1.如果准备请求的提案编号小于或等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求；
• 2.如果接受请求中的提案编号小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；
• 3.如果接受者之前有通过提案，那么接受者将承诺准备请求的响应中会包含已经通过的最大编号的提案信息

2.接受阶段

第二个阶段也就是接受阶段，首先，客户端1、2在收到大多数节点的准备请求之后，会分别发送接受请求，如图所示.

客户端1收到大多数的接受者(节点A、B)的准备响应后，会根据响应中的提案编号最大的提案的值设置接受请求中的值。因为该值在来自节点A和B的准备响应都为空(“尚无提案”)，所以就把自己的提议值3作为提案的值，发送接受请求[1,3].客户端2收到大多数的接受者(节点Ahe 节点B)的准备响应后，会根据响应中提案编号最大的提案的值设置接受请求中的值，因为该值在来自节点A、B的准备响应中都为空，所以就把自己的提议值7作为提案的值，发送接受请求[5,7].

当3个节点收到两个客户端的接受请求时，会进行如图所示的处理.
当节点A、B、C收到接受请求[1,3]的时候，由于提案的提案编号1小于3个节点承诺能通过的最小提案编号5，所以提案[1,3]将被拒绝。当节点A、B、C收到的接受请求[5,7]的时候，由于提案的提案编号5不小于3个节点承诺能通过的提案的最小编号5，所以提案[5,7]通过，也就是接受了提议值7,3个节点就X值达成共识。如果集群中有学习者，接受者通过了一个提案后就会通知所有的学习者，当学习者发现大多数的接受者都通过了某个提案，那么它也会通过该提案，并接受该提案的值。通过上面的示例过程可以看到，最终就X的值达成了共识。Basic Paxos的容错能力源自"大多数"的约定，可以这么理解，当少于一半的节点出现故障时，共识协商仍然可以正常工作

Multi-Paxos:Multi-Paxos不是一个算法，而是一个统称

通过前面的了解，你应该知道，Basic Paxos只能就单个值达成共识，一旦遇到要实现一系列值得共识的情况时，它就不管用了。虽然兰伯特
提到可以通过多次执行Basic Paxos示例(比如每接到一个值，就执行以此Basic Paxos算法)实现一系列值得共识。但是，很多人读完论文后，
还是两眼抹黑，虽然能读懂每个英文单词，但是不理解兰伯特提到得Multi-Paxos到底时什么意思。为什么Multi-Paxos这么难理解呢？
在我看来，兰伯特并没有把Multi-Paxos讲清除，只是介绍了大概的思想，缺少算法过程的细节和编程所必需的细节(比如缺少选举领导者的细节)，
导致每个人实现的Multi-Paxos都不一样。不过从本质上看，大家都是在兰伯特特岛的Mutli-Paxos思想上补充细节，设计自己的Multi-Paxos算法,
然后实现它(比如Chubby的MultiPaxos实现、Raft算法等)。
所以在这里，补充一下:兰伯特提到的Multi-Paxos是一种思想，不是算法。而Multi-Paxos算法是一个统称，它是指基于Multi-Paxos思想，通过
多个Basic Paxos实例实现一系列值的共识算法。这一点由器需要注意

兰伯特关于Multi-Paxos的思考

熟悉Basic Paxos的读者可能还记得，Basic Paxos是通过二阶段提交来达成共识的。在第一阶段，也就是准备阶段，只有接收到大多数准备响应的提议者才能发起接受请求进入第二阶段(也就是接受阶段),如图所示 。

但是，如果我们之解通过多次执行Basic Paxos实例来实现一系列值得共识，就会存在这样几个问题:

• 1.如果多个提议者同时提交提案，可能出现因为提案编号冲突，在准备阶段没有提议者接收到大多数准备响应，导致协商失败，需要重新协商。你想象一下，一个5节点的集群，如果其中3个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应(比如1个提议者接收到1个准备响应，另外两个提议者分别接收到两个2准备响应)而准备失败，需要重新协商。还有可能只有提案编号最大的那个提议者的值能获得大多数的响应，前面的值则无响应，这显然也不符合Multi-Paxos的思想。
• 2.两轮RPC通信(准备阶段和接受阶段)往返消息多、耗性能、延迟大。你要知道，分布式系统的运行是建立在RPC通信的基础之上的。因此，延迟一直是分布式系统的通电，是需要我们在开发分布式系统时认真考虑和优化的那么如何解决上面的两个问题呢？可以通过引入领导者和优化Basic Paxos执行过程来解决