我对Paxos算法的理解(2)

a. Acceptor承诺不再批准任何编号小于n的草案。

b. 如果acceptor批准过小于编号n的草案，则将编号最大的草案响应给proposer。

我们称这个请求过程为草案n的prepare请求。

2. 如果proposer从某个组（涵盖半数以上的acceptor）中的acceptor方面得到响应，假如该proposer就可以出具值为v的草案n了。当然了，这儿的v要视响应消息而定。如果得到的号召是acceptor已经获批的编号小于n的的某些提案中的编号最大的草案，假如提案n的值v就是响应的草案的值；如果得到的号召消息是acceptor没有批准过任何编号小于n的草案，假如值v就可以是任意的了。得到prepare请求的号召之后，proposer再次向同一

acceptor发出批准该草案的请求。我们称其为accept请求。

下面的硬件是对proposer提出的。那对于acceptor方面有该怎么处理呢？在下面的过程中，acceptor会收到两种类型的请求：prepare和accept。

acceptor是可以忽视任何请求的，如果不用考虑能否能满足什么条件。 所以说，这儿我们说的是acceptor会对一个请求进行号召的现象。acceptor对于prepare 请求总是会积极响应。对于accept请求，或者他没有响应批准该草案，那它会响应一个批准该草案的传闻。也就是下面的条件

P1a：acceptor对于编号为n的草案的accept请求，或者之前没有对编号大于n的草案的prepare请求进行过响应，假如该acceptor会报批编号为n的草案。

原著中是如此描述的

P1a. An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

我们看，在P1a中是涵盖P1的。

到当前为止我们已然有了一个比较完整的硬件。现在我们将proposer和acceptor综合起来，看一下整个硬件的过程。

Phase1 （a）proposer选择一个编号为n的草案，如果发送一个带有编号n的prepare请求给一组包含半数以上的acceptor。

（b）一个acceptor接收到一个关于编号n的prepare请求，发现编号n比其先前接收到的一切的草案的编号都大，如果对于它们议案的prepare请求都已然进行了号召。那么acceptor会向n的prepare请求回应的传闻包含两部份：一是，不会再批准任何小于n的草案；二是，将早已获批的编号小于n的的某些提案中的编号最大的草案的值，一定这个草案要存在。如果不存在则仅仅响应第一条。

Phase2 （a）当proposer从包括半数以上的一组acceptor那里收到关于编号n的草案的prepare请求的号召信息，假如它将要向这组acceptor发送一个编号为n值为v的草案的accept请求。这个v的值按照proposer得到的号召信息来定：或者在响应信息中涵盖有草案信息，那这个v就是该草案的值；如果没有提案信息，则v可以是任意值，只要proposer愿意。

（b）或者acceptor收到一个关于n的草案的accept请求，假如acceptor已经向大于n的草案的prepare请求进行了号召，如果该acceptor是会报批编号为n的草案的。

一个proposer只要遵照下面的要点，他就可以生成多个草案。在下面的过程中，proposer可以在任意的时刻终止一个提案。对于acceptor来说，无论如何，或者acceptor由于之前已然向一个编号更大的草案的prepare请求进行了号召而要忽视当前提案的prepare或者accept请求的话，必须要能通知到proposer。由proposer来拒绝这个草案的提交。

下面就是关于proposer和acceptor的硬件。说到这里，对于proposer和acceptor要做的大事就已然清楚了。但是我们明白，在Paxos算法中是存在三种角色的。除了proposer和acceptor以外还有learner。既然我们的草案已经选出来了，那就需要learner来学习了。下面我们就来看一下learner是怎么学习一个已经被选中的草案的。

最简单的手段就是，learner必须获取被半数以上acceptor批准的草案。所以，必须使每位acceptor，不论何时只要它批准一个提案就会通知到一切的learner，并将批准的proposal发送给learner。因此，learner可以及时的获取一个被选中的草案。但是，这样手段的代价就是会有较多的通信。因为这样手段要求每位acceptor向每位learner都要发送消息。[方法一]

还有一个方式就是，指定一个特定的learner负责和acceptor进行通信。acceptor只负责将其批准的草案发送给这个特殊的learner，由这个learner再将其发送给这些的learner。[方法二]

方法二还是有效的减少、了通信的次数，反而这样手段却是不可信的。因为一旦那个特殊的learner出现故障，一切的learner都将获取不到提案。所以在手段二的基础上演变出来了手段三。不再指定一个特定的learner，而是指定多个learner负责和acceptor通信，然后再将资料发送给这些的learner。很明显，这样手段较方式二来说通信次数又增强了，反而较方式一，通信次数一直是削减的。而且这样手段是比较可信的。

考虑到，在实际画面中消息是会丢失的。一个被选中的草案估计不会被learner获取到。这时候它可以向acceptor询问一个其已然获批的草案，反而这个acceptor是没有办法知道这个草案是否被大多数的acceptor所获批。在这样现象下，learner可以求助于proposer。它可以让一个proposer按照之前描述的要点来填写一个提案。如果该草案被填写成功了，按照之前的P2c、P2b等条件可以明白该草案的值已经被选中；否则该值没有被选中。

硬件到这儿就已然完整了。对于开始说到的三个角色——proposer、acceptor和learner，各自要进行的姿势都已然明确了。下面来说一个比较独特的现象。

我们来假设这种的一个情景：有两个proposer——p和q，每一个都会提出一系列编号递增的草案。这些议案都没有别选中过。现在p完成了阶段1的编号为n1的草案。然后p完成了阶段1的编号为n2（n2 > n1）的草案。所以对于n1的阶段2的accept请求会被忽视，因为一切的acceptor都已然向n2的prepare响应了不会再批准任何编号小于n2的草案。因此，p开始提出n3（n3 > n2），如果完成了prepare的请求。同样，这时n2的accept请求也会被忽视。以此进行下去岂不是就成了一个死循环了。

为了解决这个难题，依照learner学习提案的手段二，指定一个特定的proposer，使其也是惟一的可以提出议案的proposer。

一切里面的硬件都有一个前提，就是任何两个proposer提出的草案的编号都不相近。

下面一堆堆的插图应该有些啰嗦，多数都是参照原文翻译过来的。有不确凿的地方还能够多多指教！

参考文献：《Paxos Made Simple》

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-119092-2.html