Paxos Made Simple

我对Paxos的理解一直不够深刻，说句实在的，是没有理解。没有理解的地方在于：

1. Paxos made simple里面讲解的是一次 paxos 实例还是多次paxos 实例？
2. gap 的填充具体逻辑是什么？具体的流程是什么？
3. learner 是怎么运作的？
4. leader 为什么一开始是一个learner？
5. leader 如何把 pending 的 paxos instance 确定下来？

看起来整个Paxos Made Simple讲的是一个paxos 实例中value是怎么被选定的过程。
先继续分析，最后再下结论。

在没有失败和消息丢失的情况下，如果我们希望即使在只有一个提案被提出的情况下，仍然可以选出一个提案来，即暗示了如下的需求：

P1. 一个Acceptor必须通过(Accept)它收到的第一个提案。

我们允许多个提案被选定，但是我们必须要保证所有被选定的提案都具有相同的value值。

P2. 如果具有value值的v的提案被选定(chosen)了，那么所有比它编号更高的被选定的提案的value也必须是v。

被选定的提案，首先必须被至少一个Acceptor通过，因此我们可以通过满足如下条件来满足P2:

P2a. 如果具有value值v的提案被选定(chosen)了，那么所有比它编号更高的被Acceptor通过的提案的value值也必须是v。

我们仍然需要P1来保证提案会被选定。但因为通信是异步的，一个提案可能会在某个Acceptr c还未收到任何提案时就被选定了。假设一个新的Proposer苏醒了，然后产生了一个具有另一个value值的更高编号的提案，根据 P1 ，就需要 c 通过这个提案，但是这与 P2a 矛盾。因此如果要同时满足 P1 和 P2a，需要对 P2a 进行强化。

P2b. 如果具有value值 v 的提案被选定，那么所有比它编号更高的被Proposer提出的提案的value值也必须是v。

一个提案被Acceptor通过之前，肯定要由某个Proposer提出，因此 P2b 就隐含了 P2a，进而隐含了 P2 。

为了发现如何保证 P2b,我们来看看如何证明它成立。我们假设某个具有编号m和value的值v的提案被选定了，需要证明具有编号n(n>m)的提案都具有value值v.我们可以通过对n使用归纳法来简化证明，这样我们就可以在额外的假设下 -- 即编号在 m .. (n-1)之间的提案具有value值v,来证明编号为n的提案具有value值v.因为编号为m的提案已经被选定了，这意味着肯定存在一个由半数以上的Acceptor组成的集合C,C中的每个Acceptor都通过了这个提案。再结合归纳假设，m被选定意味着：

C 中的每个Acceptor都通过了一个编号在 m .. n-1 之间的提案，每个编号在 m .. (n-1)之间的被Acceptor通过的提案都具有value值v。

因为任何包含半数以上的Acceptor的集合S都至少包含C中的一个成员，我们可以通过维护以下的不变性就可以保证编号为n的提案具有value v：

P2c. 对于任意的n和v,如果编号为n和value值为v的提案被提出，那么肯定存在一个由半数以上的Acceptor组成的集合S,可以满足条件 a) 或者 b) 中的一个：

a) S 中不存在任何的Acceptor通过过编号小于n的提案
b) v 是 S 中所有Acceptor通过的编号小于n的具有最大编号的提案的value值。

通过维护 P2c 我们就可以保证 P2b 了。

为了维护P2c的不变性，一个Proposer在产生编号为n的提案时，必须要知道某一个将要或者已经被半数以上Acceptor通过的编号小于n的最大编号的提案。获取那些已经被通过的提案很简单，但是预测未来哪些提案会被通过却很困难。在这里，为了避免让Proposer去预测未来，我们通过限定不会有那样的通过情况来控制它。换句话说，Proposer会请求Acceptors不要再通过任何编号小于n的提案。(这里即为了保证小于n的提案没有达成共识的机会。现在应该关注n及n以上的提案了。如果Acceptors还对小于n的提案做出响应就有可能达成共识，这样就违背了Proposer在产生编号为n的提案时必须要知道某一个将要或已经被半数以上Acceptors通过的编号小于n的最大编号的提案这个前提了！！这里就是为了不预测未来哪个提案会通过，索性直接把所有小于当前提案号的提案直接忽略掉，从而保证P2b和P2c。)这样就导致了如下的提案生成算法：

• Proposer 选择一个新的提案号n,然后向某个Acceptors集合的成员发送请求，要求Acceptor做出如下回应：

  1. 保证不再通过任何编号小于n的提案
  2. 返回当前它已经通过的编号小于n的最大编号的提案，如果存在的话。

我们把这样的一个请求称为编号为n的prepare请求。

• 如果Proposer收到来自半数以上的Acceptor的响应结果，那么它就可以产生编号为n,value值为v的提案，这里v是所有响应中编号最大的提案的value值，如果响应中不包含任何提案，那么这个值就可以由Proposer任意选择。
  xk
  Proposer通过向某个Acceptors集合发送需要被通过的提案请求来产生一个提案（此时的Acceptors集合不一定是响应前一请求的那个Acceptors集合）。我们称此请求为accept请求。

目前已经描述了Proposer的算法，Acceptor可能会收到来自Proposer的两种请求，prepare和accept请求。Acceptor可以忽略任何请求而不用担心破坏其算法的安全性。因此只需要说明它在什么情况下可以对一个请求做出响应。

它可以在任何时候响应一个prepare请求，对于一个accept请求，只要在它未违反现有承诺的情况下，才能响应一个accept请求，也就是：

P1a. 一个Acceptor可以接受一个编号为n的提案，只要它还未响应任何编号大于n的prepare请求。

可以看出 P1a 包含了 P1。

我们现在就获得了一个满足安全性需求的提案选定算法，假设编号为唯一的情况下。再做一些小的优化就得到了最终的算法。

假设一个Acceptor收到了一个编号为n的prepare请求，但是它已经对编号大于n的prepare请求做出了响应，因此它肯定不会再通过任何新的编号为n的提案，那么它就没有必要对这个请求做出响应，因为它肯定不会通过编号为n的提案，因此我们会让Acceptor忽略这样的prepare请求。我们也会让它忽略那些它已经通过的提案的prepare请求。
Paxos Made Simple

我对Paxos的理解一直不够深刻，说句实在的，是没有理解。没有理解的地方在于：

1. Paxos made simple里面讲解的是一次 paxos 实例还是多次paxos 实例？
2. gap 的填充具体逻辑是什么？具体的流程是什么？
3. learner 是怎么运作的？
4. leader 为什么一开始是一个learner？
5. leader 如何把 pending 的 paxos instance 确定下来？

看起来整个Paxos Made Simple讲的是一个paxos 实例中value是怎么被选定的过程。
先继续分析，最后再下结论。

在没有失败和消息丢失的情况下，如果我们希望即使在只有一个提案被提出的情况下，仍然可以选出一个提案来，即暗示了如下的需求：

P1. 一个Acceptor必须通过(Accept)它收到的第一个提案。

我们允许多个提案被选定，但是我们必须要保证所有被选定的提案都具有相同的value值。

P2. 如果具有value值的v的提案被选定(chosen)了，那么所有比它编号更高的被选定的提案的value也必须是v。

被选定的提案，首先必须被至少一个Acceptor通过，因此我们可以通过满足如下条件来满足P2:

P2a. 如果具有value值v的提案被选定(chosen)了，那么所有比它编号更高的被Acceptor通过的提案的value值也必须是v。

我们仍然需要P1来保证提案会被选定。但因为通信是异步的，一个提案可能会在某个Acceptr c还未收到任何提案时就被选定了。假设一个新的Proposer苏醒了，然后产生了一个具有另一个value值的更高编号的提案，根据 P1 ，就需要 c 通过这个提案，但是这与 P2a 矛盾。因此如果要同时满足 P1 和 P2a，需要对 P2a 进行强化。

P2b. 如果具有value值 v 的提案被选定，那么所有比它编号更高的被Proposer提出的提案的value值也必须是v。

一个提案被Acceptor通过之前，肯定要由某个Proposer提出，因此 P2b 就隐含了 P2a，进而隐含了 P2 。

为了发现如何保证 P2b,我们来看看如何证明它成立。我们假设某个具有编号m和value的值v的提案被选定了，需要证明具有编号n(n>m)的提案都具有value值v.我们可以通过对n使用归纳法来简化证明，这样我们就可以在额外的假设下 -- 即编号在 m .. (n-1)之间的提案具有value值v,来证明编号为n的提案具有value值v.因为编号为m的提案已经被选定了，这意味着肯定存在一个由半数以上的Acceptor组成的集合C,C中的每个Acceptor都通过了这个提案。再结合归纳假设，m被选定意味着：

C 中的每个Acceptor都通过了一个编号在 m .. n-1 之间的提案，每个编号在 m .. (n-1)之间的被Acceptor通过的提案都具有value值v。

因为任何包含半数以上的Acceptor的集合S都至少包含C中的一个成员，我们可以通过维护以下的不变性就可以保证编号为n的提案具有value v：

P2c. 对于任意的n和v,如果编号为n和value值为v的提案被提出，那么肯定存在一个由半数以上的Acceptor组成的集合S,可以满足条件 a) 或者 b) 中的一个：

a) S 中不存在任何的Acceptor通过过编号小于n的提案
b) v 是 S 中所有Acceptor通过的编号小于n的具有最大编号的提案的value值。

通过维护 P2c 我们就可以保证 P2b 了。

为了维护P2c的不变性，一个Proposer在产生编号为n的提案时，必须要知道某一个将要或者已经被半数以上Acceptor通过的编号小于n的最大编号的提案。获取那些已经被通过的提案很简单，但是预测未来哪些提案会被通过却很困难。在这里，为了避免让Proposer去预测未来，我们通过限定不会有那样的通过情况来控制它。换句话说，Proposer会请求Acceptors不要再通过任何编号小于n的提案。(这里即为了保证小于n的提案没有达成共识的机会。现在应该关注n及n以上的提案了。如果Acceptors还对小于n的提案做出响应就有可能达成共识，这样就违背了Proposer在产生编号为n的提案时必须要知道某一个将要或已经被半数以上Acceptors通过的编号小于n的最大编号的提案这个前提了！！这里就是为了不预测未来哪个提案会通过，索性直接把所有小于当前提案号的提案直接忽略掉，从而保证P2b和P2c。)这样就导致了如下的提案生成算法：

• Proposer 选择一个新的提案号n,然后向某个Acceptors集合的成员发送请求，要求Acceptor做出如下回应：

  1. 保证不再通过任何编号小于n的提案
  2. 返回当前它已经通过的编号小于n的最大编号的提案，如果存在的话。

我们把这样的一个请求称为编号为n的prepare请求。

• 如果Proposer收到来自半数以上的Acceptor的响应结果，那么它就可以产生编号为n,value值为v的提案，这里v是所有响应中编号最大的提案的value值，如果响应中不包含任何提案，那么这个值就可以由Proposer任意选择。
  xk
  Proposer通过向某个Acceptors集合发送需要被通过的提案请求来产生一个提案（此时的Acceptors集合不一定是响应前一请求的那个Acceptors集合）。我们称此请求为accept请求。

目前已经描述了Proposer的算法，Acceptor可能会收到来自Proposer的两种请求，prepare和accept请求。Acceptor可以忽略任何请求而不用担心破坏其算法的安全性。因此只需要说明它在什么情况下可以对一个请求做出响应。

它可以在任何时候响应一个prepare请求，对于一个accept请求，只要在它未违反现有承诺的情况下，才能响应一个accept请求，也就是：

P1a. 一个Acceptor可以接受一个编号为n的提案，只要它还未响应任何编号大于n的prepare请求。

可以看出 P1a 包含了 P1。

我们现在就获得了一个满足安全性需求的提案选定算法，假设编号为唯一的情况下。再做一些小的优化就得到了最终的算法。

假设一个Acceptor收到了一个编号为n的prepare请求，但是它已经对编号大于n的prepare请求做出了响应，因此它肯定不会再通过任何新的编号为n的提案，那么它就没有必要对这个请求做出响应，因为它肯定不会通过编号为n的提案，因此我们会让Acceptor忽略这样的prepare请求。我们也会让它忽略那些它已经通过的提案的prepare请求。

通过这个优化，Acceptor只需要记住它已经通过的最大编号的提案和value以及它已经做出prepare请求响应的最大编号的提案的编号。因为必须要保证 P1c的不变性，即使在出错或这重启的情况下，Acceptor必须记住这些信息。Proposer总是可以丢弃提案以及它所有的信息，只要它自己保证不会产生相同编号的提案（或者回退）即可。

将Proposer和Acceptor放在一块，可以得到算法的如下两阶段执行过程：

Phase 1：

• Proposer选择一个提案编号n,然后向Acceptors的某个majority集合的成员发送编号为n的prepare请求。
• 如果一个Acceptor受到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号，那么它就会保证不会在通过(accept)任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在的话）作为响应。

Phase 2：

• 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n,value值为v的提案的accept请求给Acceptors,在这里v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。
• 如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未对编号大于n的prepare请求做出响应，它就可以通过这个提案。

一个Proposer可能产生多个提案，只要它遵循如上的算法即可。它可以在任意时刻丢弃某个提案。如果一个Proposer已经在试图产生编号更大的提案，那么丢弃未尝不是一个好的选择。因此如果一个Acceptor因为已经收到更大编号的prepare请求而忽略某个prepare或者accept请求时，那么它也应当通知它的Proposer,然后该Proposer应该丢弃该提案。这只是一个不影响正确性的优化。

获取被选定的提案值（Learning a choosen value）

为了获取被选定的值，一个Learner必须确定一个提案已经被半数以上的Acceptor通过。最明显的算法是，让每个Acceptor,只要它通过了一个提案就通知所有的Learners,将它通过的提案告知它们。这可以让Learners尽快找出被选定的值，但是它需要每个Acceptor都要与所有的Learners通信，所需的通信次数是二者数量的乘积。

在非拜占庭错误情况下，一个Learner可以很容易通过另一个learner了解到一个值已经被选定。我们可以让所有的Acceptor将它们的通过的提案发送给一个特定的Learner.当一个value被选定的时候，再由它通知其它的Learners。这种方法，需要多一个步骤才能通知到所有的Learners。而且也是不可靠的，因为那个特定的Learner可能挂掉。但是这种情况下的通信次数，只是Acceptors和Learners的个数的和。

更一般的，Acceptors可以将它们的通过信息发送给一个特定的Learners集合，它们中的每个都可以在一个value被选定之后，通知所有的Learners。这个集合中的Learners个数越多，可靠性就越好，但是通信复杂度就越高。

由于消息的丢失，一个value被选定后，可能没有Learners会发现。Learners可以询问Acceptors它们通过了哪些提案，但是一个Acceptor出错，都有可能导致无法判断出是否已经有半数以上的Acceptors通过的提案。Learner可以通过发起一次prepare来得到是否已经有value被选定。（这里可能有一个恰巧，即，实际Accept的Acceptor的大多数集合S和Learner发起提案对应响应的Acceptor的大多数集合S'，可能正好是两个最大不相同集合，此时交集的Acceptor可能正好挂掉。此时Learner就无法获取到选定的value，不过这不影响正确性，Learner得等待。比如等待超时，再发起一次prepare直到选定）

（从这里可以看到，只有Learner有完整的提案集合。那么选择leader当然只能从Learner集合中选择出来。）

进展（Progress）
很容易构造出一种情况，两个Proposer不断提出propose，并且每个Proposer的Phase 1都被超过一半的Acceptors通过，这样不断被新的Phase 1即prepare互相通过，导致都不能进入到Phase 2，即accept。

为了保证进度，必须选择一个特定的Proposer来作为一个唯一的提案提出者。如果这个Proposer可以同半数以上的Acceptors通信，同时，可以使用一个xk比现有的编号都大的编号来发起提案，那么它就可以成功的产生一个可以被通过的提案。再有，当它知道某些更高的编号的请求时，舍弃当前的提案并重做，这个Proposer最终一定会产生一个足够大的提案编号。（这里必须这样处理，保证安全性，因为有可能有两个Proposer认为自己是Leader，使用更高的编号）。

如果系统中有足够的组件（Proposer,Acceptors及通信网络）工作良好，通过选择一个特定的Proposer作为Leader就可以满足活性。著名的FLP结论指出，一个可靠的Proposer选举算法要么利用随机性，要么利用实时性来实现--比如使用超时机制（随即超时机制避免活锁）。不过无论选举是否成功，安全性都可以保证。

实现
Paxos算法假设了一组进程网络。在它的一致性算法中，每个进程扮演着Proposer,Acceptor及Learner的角色，该算法选定了一个Leader来扮演那个特定的Proposer和Learner.Paxos一致性算法就是上面描述的那个，请求和响应都是以普通的消息的方式发送（响应消息通过对应的提案编号来标识防止混淆）。使用可靠性的存储设备来存储Acceptor需要记住的信息来防止出错。Acceptor在真正送出响应之前，会将它记录在可靠性存储设备中。

如何保证编号唯一性？不同的Proposers可以使用等差数列，步长相同，不过不同的Proposer的起始值不同，就能保证任何的Proposer发出的提案均不相同。
每个Proposer需要将它目前生成的最大编号的提案记录在可靠性存储设备中，然后用一个比已经使用的所有编号都大的提案开始Phase 1。

实现状态机模型
实现分布式系统的一种简单方式就是，使用一组客户端集合然后向一个中央服务器发送命令。服务器可以看成是一个以某种顺序执行客户端命令的确定性状态机。该状态机有一个当前状态，通过输入一个命令来产生一个输出以及一个新的状态。比如一个分布式银行系统的客户端可能是一些出纳员，状态机状态由所有用户的账户余额组成。一个取款操作，通过执行一个减少账户余额的状态机命令（当且仅当余额大于等于取款数目时）实现，将新旧余额作为输出。

使用中央服务器的系统在该服务器失败的情况下，整个系统就失败了。因此，我们使用一组服务器来代替它，每个服务器独立实现了该状态机。因为状态机是确定性的，如果它们都按照相同的命令顺序执行，那么就会产生相同的状态机状态和输出。一个产生命令的客户端，就可以使用任意的服务器为它产生输出。

为了保证所有的服务器都执行相同的状态机命令序列，我们需要实现一系列独立的Paxos一致性算法实例，第i个实例选定的值作为序列中的第i个状态机命令。在算法的每个实例中，每个服务器担任所有的角色（Proposer、Acceptor和Learner）。现在，我们假设服务器集合是固定的，这样所有的一致性算法实例都具有相同的参与者合集。

在正常执行中，一个服务器会被选为Leader,它会在所有的一致性算法实例中被选作特定的Proposer（唯一的提案提出者）。客户端向该Leader发送命令，它来决定每个命令被安排在序列中的何处。如果Leader决定某个客户端命令应该是第135个命令，它会尝试让该命令xk成为第135个一致性算法实例选定的value值。通常这都会成功，但是由于出错或者另一个服务器认为自己是leader,而它对第135个命令持有异议。但是一致性算法可以保证，最多只有一个命令会被选定为第135个命令。

这种策略的关键在于，在Paxos一致性算法中，被提出的value只有在phase 2才会被选定。回忆一下，在Proposer的Phase 1完成时，要么提案的value已经确定了，要么Proposer可以自由地提出一个值。

现在我们已经知道在正常运行Phase 1：

• Proposer选择一个提案编号n,然后向Acceptors的某个majority集合的成员发送编号为n的prepare请求。
• 如果一个Acceptor受到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号，那么它就会保证不会在通过(accept)任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在的话）作为响应。

Phase 2：

• 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n,value值为v的提案的accept请求给Acceptors,在这里v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。
• 如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未对编号大于n的prepare请求做出响应，它就可以通过这个提案。时，paxos状态机实现是如何工作的。下面看出错的情况，看之前的leader失败以及新leader被选定后会发生什么？（系统启动是一种特殊情况，此时还没有命令被提出）

新的Leader被选出来，首先要成为所有一致性算法执行实例的Learner,需要知道目前已经想定的大部分命令。假设它知道命令1-134,138及139,也就是一致性算法实例1-134,138及139选定的值。（注意，这里只是说知道选定的值，还没有应用到状态机，需要把缺口的实例选定的值先确定下来，才能依次应用到状态机）让后它需要执行135-137以及所有其它大于139的算法执行实例的phase 1（这里有个优化，下面说）。假设执行结果表明，实例135和140中提出的提案值已经确定了。但是其它执行实例的提案值是没有限定的。那么现在该Leader就可以为135和140执行Phase 2,进而选定第135和140号命令。

Leader以及其它所有已经获取该Leader的已知命令的服务器，现在可以执行命令1-135，但还不能执行138-140,因为136和137还未选定。Leader可以将下两个到来的客户端请求命令作为命令136和137。但我们也可以提起一个特殊的noop命令作为136和137命令来尽快填补空缺（通过执行一致性算法实例136和137的Phase 2来完成）。一旦该noop命令被选定，命令138-140就可以执行了。（注意这里，如果不使用noop来填充，而是让后续到来的请求复用这两个instance，可能会造成状态机不满足顺序一致性，因为最新的命令使用了老的instance id。不过paxos仅仅保证了单个instance的安全性和正确性，保证其达成共识，并未保证上层应用的状态机的顺序一致性（可以理解为两套系统，互相不感知），不过这里填noop恰好能够满足上层应用状态机的顺序一致性）。

命令1-140目前已被选定了。Leader也已经完成了所有大于140的一致性算法实例的Phase 1（这里是一个优化，使用同时个编号来应用之后大于140的实例的phase 1，即大于140的提案的编号都复用同样的值，这样可以省去为每个instance执行一遍phase 1，前提是Leader是稳定的情况下，提案的编号相同，但是instance的值不同，直接可以将两个值携带到消息体中，这样只需要phase 2来达成共识即可。因为如果大于140的有已经通过的value时候，Acceptor会返回的，这样才能放心将某个范围的编号的phase 1省略）而且在这些实例中，它可以自由地提出任何值。它将下一个客户端的请求命令作为第141个命令，并且在Phase2中将它作为一致性算法的第141个实例的value值。它会将下一个客户端的请求命令作为命令142，如此 ...

Leader 可以在它提出的命令141被选定前提出命令142，。它发送的关于命令141的消息有可能全部丢失，因此在所有其他服务器在获知Leader选定了谁作为命令141之前，命令142就可能已被选定。当Leader无法收到实例141的Phase 2的期望响应之后，它会重传这些信息，当时重传这些信息，但是仍然可能会失败，这样就在被选定的命令序列中出现了缺口。假设一个Leader可以他们确定a个命令，这意味着在i被选定之后，它就可以提出命令 i + 1到 i + a的命令了。这样就可能形成一个长达 a - 1的命令缺口。

一个新选择的Leader需要为无数个一致性算法实例执行Phase 1（为了确定那些还未知的instance是否选定了值）--在上面的情景中，就是135-137以及所有大于139的实例。只要向其他的服务器发送一个合适的消息内容，就可以让所有的执行实例使用同一个提案编号（大于之前所有的）。（注：这里是一个优化，使用一个更大的提案编号来作为这个优化消息的编号，消息内容是所有需要确定的instance的范围，一并发送给了Acceptor）。在Phase 1,只要一个Acceptor以及收到来自某个Proposer的phase 2消息，那么它就可以为不止一个的执行实例作出承诺。（在上面的场景中，就是针对135和140的情况）因此一个服务器（作为Acceptor角色时）通过选择一个适当的短消息就可以对所有的实例作出响应，那么执行这样无限多个实例的Phase 1也就不会有问题。（注：此时Acceptor需要根据收到的需要确定是否选定value的的instance范围Paxos Made Simple

我对Paxos的理解一直不够深刻，说句实在的，是没有理解。没有理解的地方在于：

1. Paxos made simple里面讲解的是一次 paxos 实例还是多次paxos 实例？
2. gap 的填充具体逻辑是什么？具体的流程是什么？
3. learner 是怎么运作的？
4. leader 为什么一开始是一个learner？
5. leader 如何把 pending 的 paxos instance 确定下来？

看起来整个Paxos Made Simple讲的是一个paxos 实例中value是怎么被选定的过程。
先继续分析，最后再下结论。

在没有失败和消息丢失的情况下，如果我们希望即使在只有一个提案被提出的情况下，仍然可以选出一个提案来，即暗示了如下的需求：

P1. 一个Acceptor必须通过(Accept)它收到的第一个提案。

我们允许多个提案被选定，但是我们必须要保证所有被选定的提案都具有相同的value值。

P2. 如果具有value值的v的提案被选定(chosen)了，那么所有比它编号更高的被选定的提案的value也必须是v。

被选定的提案，首先必须被至少一个Acceptor通过，因此我们可以通过满足如下条件来满足P2:

P2a. 如果具有value值v的提案被选定(chosen)了，那么所有比它编号更高的被Acceptor通过的提案的value值也必须是v。

我们仍然需要P1来保证提案会被选定。但因为通信是异步的，一个提案可能会在某个Acceptr c还未收到任何提案时就被选定了。假设一个新的Proposer苏醒了，然后产生了一个具有另一个value值的更高编号的提案，根据 P1 ，就需要 c 通过这个提案，但是这与 P2a 矛盾。因此如果要同时满足 P1 和 P2a，需要对 P2a 进行强化。

P2b. 如果具有value值 v 的提案被选定，那么所有比它编号更高的被Proposer提出的提案的value值也必须是v。

一个提案被Acceptor通过之前，肯定要由某个Proposer提出，因此 P2b 就隐含了 P2a，进而隐含了 P2 。

为了发现如何保证 P2b,我们来看看如何证明它成立。我们假设某个具有编号m和value的值v的提案被选定了，需要证明具有编号n(n>m)的提案都具有value值v.我们可以通过对n使用归纳法来简化证明，这样我们就可以在额外的假设下 -- 即编号在 m .. (n-1)之间的提案具有value值v,来证明编号为n的提案具有value值v.因为编号为m的提案已经被选定了，这意味着肯定存在一个由半数以上的Acceptor组成的集合C,C中的每个Acceptor都通过了这个提案。再结合归纳假设，m被选定意味着：

C 中的每个Acceptor都通过了一个编号在 m .. n-1 之间的提案，每个编号在 m .. (n-1)之间的被Acceptor通过的提案都具有value值v。

因为任何包含半数以上的Acceptor的集合S都至少包含C中的一个成员，我们可以通过维护以下的不变性就可以保证编号为n的提案具有value v：

P2c. 对于任意的n和v,如果编号为n和value值为v的提案被提出，那么肯定存在一个由半数以上的Acceptor组成的集合S,可以满足条件 a) 或者 b) 中的一个：

a) S 中不存在任何的Acceptor通过过编号小于n的提案
b) v 是 S 中所有Acceptor通过的编号小于n的具有最大编号的提案的value值。

通过维护 P2c 我们就可以保证 P2b 了。

为了维护P2c的不变性，一个Proposer在产生编号为n的提案时，必须要知道某一个将要或者已经被半数以上Acceptor通过的编号小于n的最大编号的提案。获取那些已经被通过的提案很简单，但是预测未来哪些提案会被通过却很困难。在这里，为了避免让Proposer去预测未来，我们通过限定不会有那样的通过情况来控制它。换句话说，Proposer会请求Acceptors不要再通过任何编号小于n的提案。(这里即为了保证小于n的提案没有达成共识的机会。现在应该关注n及n以上的提案了。如果Acceptors还对小于n的提案做出响应就有可能达成共识，这样就违背了Proposer在产生编号为n的提案时必须要知道某一个将要或已经被半数以上Acceptors通过的编号小于n的最大编号的提案这个前提了！！这里就是为了不预测未来哪个提案会通过，索性直接把所有小于当前提案号的提案直接忽略掉，从而保证P2b和P2c。)这样就导致了如下的提案生成算法：

• Proposer 选择一个新的提案号n,然后向某个Acceptors集合的成员发送请求，要求Acceptor做出如下回应：

  1. 保证不再通过任何编号小于n的提案
  2. 返回当前它已经通过的编号小于n的最大编号的提案，如果存在的话。

我们把这样的一个请求称为编号为n的prepare请求。

• 如果Proposer收到来自半数以上的Acceptor的响应结果，那么它就可以产生编号为n,value值为v的提案，这里v是所有响应中编号最大的提案的value值，如果响应中不包含任何提案，那么这个值就可以由Proposer任意选择。
  xk
  Proposer通过向某个Acceptors集合发送需要被通过的提案请求来产生一个提案（此时的Acceptors集合不一定是响应前一请求的那个Acceptors集合）。我们称此请求为accept请求。

目前已经描述了Proposer的算法，Acceptor可能会收到来自Proposer的两种请求，prepare和accept请求。Acceptor可以忽略任何请求而不用担心破坏其算法的安全性。因此只需要说明它在什么情况下可以对一个请求做出响应。

它可以在任何时候响应一个prepare请求，对于一个accept请求，只要在它未违反现有承诺的情况下，才能响应一个accept请求，也就是：

P1a. 一个Acceptor可以接受一个编号为n的提案，只要它还未响应任何编号大于n的prepare请求。

可以看出 P1a 包含了 P1。

我们现在就获得了一个满足安全性需求的提案选定算法，假设编号为唯一的情况下。再做一些小的优化就得到了最终的算法。

假设一个Acceptor收到了一个编号为n的prepare请求，但是它已经对编号大于n的prepare请求做出了响应，因此它肯定不会再通过任何新的编号为n的提案，那么它就没有必要对这个请求做出响应，因为它肯定不会通过编号为n的提案，因此我们会让Acceptor忽略这样的prepare请求。我们也会让它忽略那些它已经通过的提案的prepare请求。

通过这个优化，Acceptor只需要记住它已经通过的最大编号的提案和value以及它已经做出prepare请求响应的最大编号的提案的编号。因为必须要保证 P1c的不变性，即使在出错或这重启的情况下，Acceptor必须记住这些信息。Proposer总是可以丢弃提案以及它所有的信息，只要它自己保证不会产生相同编号的提案（或者回退）即可。

将Proposer和Acceptor放在一块，可以得到算法的如下两阶段执行过程：

Phase 1：

• Proposer选择一个提案编号n,然后向Acceptors的某个majority集合的成员发送编号为n的prepare请求。
• 如果一个Acceptor受到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号，那么它就会保证不会在通过(accept)任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在的话）作为响应。

Phase 2：

• 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n,value值为v的提案的accept请求给Acceptors,在这里v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。
• 如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未对编号大于n的prepare请求做出响应，它就可以通过这个提案。

一个Proposer可能产生多个提案，只要它遵循如上的算法即可。它可以在任意时刻丢弃某个提案。如果一个Proposer已经在试图产生编号更大的提案，那么丢弃未尝不是一个好的选择。因此如果一个Acceptor因为已经收到更大编号的prepare请求而忽略某个prepare或者accept请求时，那么它也应当通知它的Proposer,然后该Proposer应该丢弃该提案。这只是一个不影响正确性的优化。

获取被选定的提案值（Learning a choosen value）

为了获取被选定的值，一个Learner必须确定一个提案已经被半数以上的Acceptor通过。最明显的算法是，让每个Acceptor,只要它通过了一个提案就通知所有的Learners,将它通过的提案告知它们。这可以让Learners尽快找出被选定的值，但是它需要每个Acceptor都要与所有的Learners通信，所需的通信次数是二者数量的乘积。

在非拜占庭错误情况下，一个Learner可以很容易通过另一个learner了解到一个值已经被选定。我们可以让所有的Acceptor将它们的通过的提案发送给一个特定的Learner.当一个value被选定的时候，再由它通知其它的Learners。这种方法，需要多一个步骤才能通知到所有的Learners。而且也是不可靠的，因为那个特定的Learner可能挂掉。但是这种情况下的通信次数，只是Acceptors和Learners的个数的和。

更一般的，Acceptors可以将它们的通过信息发送给一个特定的Learners集合，它们中的每个都可以在一个value被选定之后，通知所有的Learners。这个集合中的Learners个数越多，可靠性就越好，但是通信复杂度就越高。

由于消息的丢失，一个value被选定后，可能没有Learners会发现。Learners可以询问Acceptors它们通过了哪些提案，但是一个Acceptor出错，都有可能导致无法判断出是否已经有半数以上的Acceptors通过的提案。Learner可以通过发起一次prepare来得到是否已经有value被选定。（这里可能有一个恰巧，即，实际Accept的Acceptor的大多数集合S和Learner发起提案对应响应的Acceptor的大多数集合S'，可能正好是两个最大不相同集合，此时交集的Acceptor可能正好挂掉。此时Learner就无法获取到选定的value，不过这不影响正确性，Learner得等待。比如等待超时，再发起一次prepare直到选定）

（从这里可以看到，只有Learner有完整的提案集合。那么选择leader当然只能从Learner集合中选择出来。）

进展（Progress）
很容易构造出一种情况，两个Proposer不断提出propose，并且每个Proposer的Phase 1都被超过一半的Acceptors通过，这样不断被新的Phase 1即prepare互相通过，导致都不能进入到Phase 2，即accept。

为了保证进度，必须选择一个特定的Proposer来作为一个唯一的提案提出者。如果这个Proposer可以同半数以上的Acceptors通信，同时，可以使用一个xk比现有的编号都大的编号来发起提案，那么它就可以成功的产生一个可以被通过的提案。再有，当它知道某些更高的编号的请求时，舍弃当前的提案并重做，这个Proposer最终一定会产生一个足够大的提案编号。（这里必须这样处理，保证安全性，因为有可能有两个Proposer认为自己是Leader，使用更高的编号）。

如果系统中有足够的组件（Proposer,Acceptors及通信网络）工作良好，通过选择一个特定的Proposer作为Leader就可以满足活性。著名的FLP结论指出，一个可靠的Proposer选举算法要么利用随机性，要么利用实时性来实现--比如使用超时机制（随即超时机制避免活锁）。不过无论选举是否成功，安全性都可以保证。

实现
Paxos算法假设了一组进程网络。在它的一致性算法中，每个进程扮演着Proposer,Acceptor及Learner的角色，该算法选定了一个Leader来扮演那个特定的Proposer和Learner.Paxos一致性算法就是上面描述的那个，请求和响应都是以普通的消息的方式发送（响应消息通过对应的提案编号来标识防止混淆）。使用可靠性的存储设备来存储Acceptor需要记住的信息来防止出错。Acceptor在真正送出响应之前，会将它记录在可靠性存储设备中。

如何保证编号唯一性？不同的Proposers可以使用等差数列，步长相同，不过不同的Proposer的起始值不同，就能保证任何的Proposer发出的提案均不相同。
每个Proposer需要将它目前生成的最大编号的提案记录在可靠性存储设备中，然后用一个比已经使用的所有编号都大的提案开始Phase 1。

实现状态机模型
实现分布式系统的一种简单方式就是，使用一组客户端集合然后向一个中央服务器发送命令。服务器可以看成是一个以某种顺序执行客户端命令的确定性状态机。该状态机有一个当前状态，通过输入一个命令来产生一个输出以及一个新的状态。比如一个分布式银行系统的客户端可能是一些出纳员，状态机状态由所有用户的账户余额组成。一个取款操作，通过执行一个减少账户余额的状态机命令（当且仅当余额大于等于取款数目时）实现，将新旧余额作为输出。

使用中央服务器的系统在该服务器失败的情况下，整个系统就失败了。因此，我们使用一组服务器来代替它，每个服务器独立实现了该状态机。因为状态机是确定性的，如果它们都按照相同的命令顺序执行，那么就会产生相同的状态机状态和输出。一个产生命令的客户端，就可以使用任意的服务器为它产生输出。

为了保证所有的服务器都执行相同的状态机命令序列，我们需要实现一系列独立的Paxos一致性算法实例，第i个实例选定的值作为序列中的第i个状态机命令。在算法的每个实例中，每个服务器担任所有的角色（Proposer、Acceptor和Learner）。现在，我们假设服务器集合是固定的，这样所有的一致性算法实例都具有相同的参与者合集。

在正常执行中，一个服务器会被选为Leader,它会在所有的一致性算法实例中被选作特定的Proposer（唯一的提案提出者）。客户端向该Leader发送命令，它来决定每个命令被安排在序列中的何处。如果Leader决定某个客户端命令应该是第135个命令，它会尝试让该命令xk成为第135个一致性算法实例选定的value值。通常这都会成功，但是由于出错或者另一个服务器认为自己是leader,而它对第135个命令持有异议。但是一致性算法可以保证，最多只有一个命令会被选定为第135个命令。

这种策略的关键在于，在Paxos一致性算法中，被提出的value只有在phase 2才会被选定。回忆一下，在Proposer的Phase 1完成时，要么提案的value已经确定了，要么Proposer可以自由地提出一个值。

现在我们已经知道在正常运行Phase 1：

• Proposer选择一个提案编号n,然后向Acceptors的某个majority集合的成员发送编号为n的prepare请求。
• 如果一个Acceptor受到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号，那么它就会保证不会在通过(accept)任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在的话）作为响应。

Phase 2：

• 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n,value值为v的提案的accept请求给Acceptors,在这里v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。
• 如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未对编号大于n的prepare请求做出响应，它就可以通过这个提案。时，paxos状态机实现是如何工作的。下面看出错的情况，看之前的leader失败以及新leader被选定后会发生什么？（系统启动是一种特殊情况，此时还没有命令被提出）

新的Leader被选出来，首先要成为所有一致性算法执行实例的Learner,需要知道目前已经想定的大部分命令。假设它知道命令1-134,138及139,也就是一致性算法实例1-134,138及139选定的值。（注意，这里只是说知道选定的值，还没有应用到状态机，需要把缺口的实例选定的值先确定下来，才能依次应用到状态机）让后它需要执行135-137以及所有其它大于139的算法执行实例的phase 1（这里有个优化，下面说）。假设执行结果表明，实例135和140中提出的提案值已经确定了。但是其它执行实例的提案值是没有限定的。那么现在该Leader就可以为135和140执行Phase 2,进而选定第135和140号命令。

Leader以及其它所有已经获取该Leader的已知命令的服务器，现在可以执行命令1-135，但还不能执行138-140,因为136和137还未选定。Leader可以将下两个到来的客户端请求命令作为命令136和137。但我们也可以提起一个特殊的noop命令作为136和137命令来尽快填补空缺（通过执行一致性算法实例136和137的Phase 2来完成）。一旦该noop命令被选定，命令138-140就可以执行了。（注意这里，如果不使用noop来填充，而是让后续到来的请求复用这两个instance，可能会造成状态机不满足顺序一致性，因为最新的命令使用了老的instance id。不过paxos仅仅保证了单个instance的安全性和正确性，保证其达成共识，并未保证上层应用的状态机的顺序一致性（可以理解为两套系统，互相不感知），不过这里填noop恰好能够满足上层应用状态机的顺序一致性）。

命令1-140目前已被选定了。Leader也已经完成了所有大于140的一致性算法实例的Phase 1（这里是一个优化，使用同时个编号来应用之后大于140的实例的phase 1，即大于140的提案的编号都复用同样的值，这样可以省去为每个instance执行一遍phase 1，前提是Leader是稳定的情况下，提案的编号相同，但是instance的值不同，直接可以将两个值携带到消息体中，这样只需要phase 2来达成共识即可。因为如果大于140的有已经通过的value时候，Acceptor会返回的，这样才能放心将某个范围的编号的phase 1省略）而且在这些实例中，它可以自由地提出任何值。它将下一个客户端的请求命令作为第141个命令，并且在Phase2中将它作为一致性算法的第141个实例的value值。它会将下一个客户端的请求命令作为命令142，如此 ...

Leader 可以在它提出的命令141被选定前提出命令142，。它发送的关于命令141的消息有可能全部丢失，因此在所有其他服务器在获知Leader选定了谁作为命令141之前，命令142就可能已被选定。当Leader无法收到实例141的Phase 2的期望响应之后，它会重传这些信息，当时重传这些信息，但是仍然可能会失败，这样就在被选定的命令序列中出现了缺口。假设一个Leader可以他们确定a个命令，这意味着在i被选定之后，它就可以提出命令 i + 1到 i + a的命令了。这样就可能形成一个长达 a - 1的命令缺口。

一个新选择的Leader需要为无数个一致性算法实例执行Phase 1（为了确定那些还未知的instance是否选定了值）--在上面的情景中，就是135-137以及所有大于139的实例。只要向其他的服务器发送一个合适的消息内容，就可以让所有的执行实例使用同一个提案编号（大于之前所有的）。（注：这里是一个优化，使用一个更大的提案编号来作为这个优化消息的编号，消息内容是所有需要确定的instance的范围，一并发送给了Acceptor）。在Phase 1,只要一个Acceptor以及收到来自某个Proposer的phase 2消息，那么它就可以为不止一个的执行实例作出承诺。（在上面的场景中，就是针对135和140的情况）因此一个服务器（作为Acceptor角色时）通过选择一个适当的短消息就可以对所有的实例作出响应，那么执行这样无限多个实例的Phase 1也就不会有问题。（注：此时Acceptor需要根据收到的需要确定是否选定value的的instance范围逐个检查并回复，这样避免了为每个instance单独执行一次phase 1的开销）。

因为Leader的失败和新Leader的选举都是很少见的情况，因此执行一个状态机命令--即在命令值上达成一致性的花费就是执行该一致性算法的Phase 2的花费。（注：因为此时Leader是一直都存在的，progress是一定保证的，不会存在提案编号冲突的情况，Proposer没有任何并行提出提案的情况，所以不需要变化提案号，也就不需要prepare的过程，其实此时就退化成了raft了）。

在该系统的正常执行下，我们假设总是只有一个Leader,只有在当前的Leader失效及选举新Leader的较短时间内才会违背这个假设。在特殊情况下，Leader选举可能失败。如果没有服务器担任Leader,那么就没有新命令被提出。如果同时有多个服务器认为自己是Leader，它们在一个一致性算法执行实例中可能提出不同的value，这可能会导致无法选出一个value，但是，安全性一直都可以保证--即不可能会同时有两个命令被选定为第i个状态机命令。Leader的选举只是为了保证progress。

如果服务器集合是变化的，那么必须有某种方式来决定哪些服务器来实现哪些实例。配置的变更最直接的方式是将配置本身作为状态的一部分。只需要确定从哪个instance开始使用新的配置。比如i之前使用旧的服务器集合，i之后使用新的服务器集合。配置的变更同样使用一次paxos instance的方式来决定。这就提供了一种支持任意负载的重配置算法的简单实现。

The End;

我对Paxos的理解一直不够深刻，说句实在的，是没有理解。没有理解的地方在于：

1. Paxos made simple里面讲解的是一次 paxos 实例还是多次paxos 实例？
2. gap 的填充具体逻辑是什么？具体的流程是什么？
3. learner 是怎么运作的？
4. leader 为什么一开始是一个learner？
5. leader 如何把 pending 的 paxos instance 确定下来？

看完后回答的，现在尝试再回答之前自己的疑问：

1. Paxos made simple里面讲解的是一次 paxos 实例还是多次paxos 实例？
   答：Paxos made simple 大部分都在讲一次paxos instance达成共识的过程。一步步推演，最终得到一个既保证了safety,又保证了liveness的算法，不过此时已经不是单纯的单个paxos instance过程，为了保证liveness，引入了multi-paxos即Leader的思想。而单个paxos instance的执行过程则分为两个阶段：
   Phase 1：

• Proposer选择一个提案编号n,然后向Acceptors的某个majority集合的成员发送编号为n的prepare请求。
• 如果一个Acceptor受到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号，那么它就会保证不会在通过(accept)任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在的话）作为响应。

Phase 2：

• 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n,value值为v的提案的accept请求给Acceptors,在这里v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。
• 如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未对编号大于n的prepare请求做出响应，它就可以通过这个提案。

2. gap 的填充具体逻辑是什么？具体的流程？
   答：gap 通过发起一次phase 1来向Acceptor探测哪些达成了共识，对达成共识的，执行phase 2，填充，可以随意值的，可以填noop，或者让后续的提案复用老的值。不过这里当心对于应用层的状态机顺序一致性的保证。

3. learner 是怎么运作的？
   答：learner 是通过Acceptor告诉它那些提案被选定了，learner通过统计如果大多数的Acceptor都accept了，其可以认为这个提案已经选定了。learner会作为leader的备选集合。

4. leader 为什么一开始是一个learner？
   答：因为只有learner才可能有接近完整的所有提案共识的结果，所有的Acceptor都将accept的结果直接发送给learner。

5. leader 如何把 pending 的 paxos instance 确定下来？
   答：这个问题和问题2很接近，leader通过对pending的paxos instance执行一次phase 1。然后选择要么phase 2给定值，要么给noop值，取决于Acceptor是否已经接受过。

逐个检查并回复，这样避免了为每个instance单独执行一次phase 1的开销）。

因为Leader的失败和新Leader的选举都是很少见的情况，因此执行一个状态机命令--即在命令值上达成一致性的花费就是执行该一致性算法的Phase 2的花费。（注：因为此时Leader是一直都存在的，progress是一定保证的，不会存在提案编号冲突的情况，Proposer没有任何并行提出提案的情况，所以不需要变化提案号，也就不需要prepare的过程，其实此时就退化成了raft了）。

在该系统的正常执行下，我们假设总是只有一个Leader,只有在当前的Leader失效及选举新Leader的较短时间内才会违背这个假设。在特殊情况下，Leader选举可能失败。如果没有服务器担任Leader,那么就没有新命令被提出。如果同时有多个服务器认为自己是Leader，它们在一个一致性算法执行实例中可能提出不同的value，这可能会导致无法选出一个value，但是，安全性一直都可以保证--即不可能会同时有两个命令被选定为第i个状态机命令。Leader的选举只是为了保证progress。

如果服务器集合是变化的，那么必须有某种方式来决定哪些服务器来实现哪些实例。配置的变更最直接的方式是将配置本身作为状态的一部分。只需要确定从哪个instance开始使用新的配置。比如i之前使用旧的服务器集合，i之后使用新的服务器集合。配置的变更同样使用一次paxos instance的方式来决定。这就提供了一种支持任意负载的重配置算法的简单实现。

The End;

我对Paxos的理解一直不够深刻，说句实在的，是没有理解。没有理解的地方在于：

1. Paxos made simple里面讲解的是一次 paxos 实例还是多次paxos 实例？
2. gap 的填充具体逻辑是什么？具体的流程是什么？
3. learner 是怎么运作的？
4. leader 为什么一开始是一个learner？
5. leader 如何把 pending 的 paxos instance 确定下来？

看完后回答的，现在尝试再回答之前自己的疑问：

1. Paxos made simple里面讲解的是一次 paxos 实例还是多次paxos 实例？
   答：Paxos made simple 大部分都在讲一次paxos instance达成共识的过程。一步步推演，最终得到一个既保证了safety,又保证了liveness的算法，不过此时已经不是单纯的单个paxos instance过程，为了保证liveness，引入了multi-paxos即Leader的思想。而单个paxos instance的执行过程则分为两个阶段：
   Phase 1：

• Proposer选择一个提案编号n,然后向Acceptors的某个majority集合的成员发送编号为n的prepare请求。
• 如果一个Acceptor受到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号，那么它就会保证不会在通过(accept)任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在的话）作为响应。

Phase 2：

• 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n,value值为v的提案的accept请求给Acceptors,在这里v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。
• 如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未对编号大于n的prepare请求做出响应，它就可以通过这个提案。

2. gap 的填充具体逻辑是什么？具体的流程？
   答：gap 通过发起一次phase 1来向Acceptor探测哪些达成了共识，对达成共识的，执行phase 2，填充，可以随意值的，可以填noop，或者让后续的提案复用老的值。不过这里当心对于应用层的状态机顺序一致性的保证。

3. learner 是怎么运作的？
   答：learner 是通过Acceptor告诉它那些提案被选定了，learner通过统计如果大多数的Acceptor都accept了，其可以认为这个提案已经选定了。learner会作为leader的备选集合。

4. leader 为什么一开始是一个learner？
   答：因为只有learner才可能有接近完整的所有提案共识的结果，所有的Acceptor都将accept的结果直接发送给learner。

5. leader 如何把 pending 的 paxos instance 确定下来？
   答：这个问题和问题2很接近，leader通过对pending的paxos instance执行一次phase 1。然后选择要么phase 2给定值，要么给noop值，取决于Acceptor是否已经接受过。

通过这个优化，Acceptor只需要记住它已经通过的最大编号的提案和value以及它已经做出prepare请求响应的最大编号的提案的编号。因为必须要保证 P1c的不变性，即使在出错或这重启的情况下，Acceptor必须记住这些信息。Proposer总是可以丢弃提案以及它所有的信息，只要它自己保证不会产生相同编号的提案（或者回退）即可。

将Proposer和Acceptor放在一块，可以得到算法的如下两阶段执行过程：

Phase 1：

• Proposer选择一个提案编号n,然后向Acceptors的某个majority集合的成员发送编号为n的prepare请求。
• 如果一个Acceptor受到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号，那么它就会保证不会在通过(accept)任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在的话）作为响应。

Phase 2：

• 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n,value值为v的提案的accept请求给Acceptors,在这里v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。
• 如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未对编号大于n的prepare请求做出响应，它就可以通过这个提案。

一个Proposer可能产生多个提案，只要它遵循如上的算法即可。它可以在任意时刻丢弃某个提案。如果一个Proposer已经在试图产生编号更大的提案，那么丢弃未尝不是一个好的选择。因此如果一个Acceptor因为已经收到更大编号的prepare请求而忽略某个prepare或者accept请求时，那么它也应当通知它的Proposer,然后该Proposer应该丢弃该提案。这只是一个不影响正确性的优化。

获取被选定的提案值（Learning a choosen value）

为了获取被选定的值，一个Learner必须确定一个提案已经被半数以上的Acceptor通过。最明显的算法是，让每个Acceptor,只要它通过了一个提案就通知所有的Learners,将它通过的提案告知它们。这可以让Learners尽快找出被选定的值，但是它需要每个Acceptor都要与所有的Learners通信，所需的通信次数是二者数量的乘积。

在非拜占庭错误情况下，一个Learner可以很容易通过另一个learner了解到一个值已经被选定。我们可以让所有的Acceptor将它们的通过的提案发送给一个特定的Learner.当一个value被选定的时候，再由它通知其它的Learners。这种方法，需要多一个步骤才能通知到所有的Learners。而且也是不可靠的，因为那个特定的Learner可能挂掉。但是这种情况下的通信次数，只是Acceptors和Learners的个数的和。

更一般的，Acceptors可以将它们的通过信息发送给一个特定的Learners集合，它们中的每个都可以在一个value被选定之后，通知所有的Learners。这个集合中的Learners个数越多，可靠性就越好，但是通信复杂度就越高。

由于消息的丢失，一个value被选定后，可能没有Learners会发现。Learners可以询问Acceptors它们通过了哪些提案，但是一个Acceptor出错，都有可能导致无法判断出是否已经有半数以上的Acceptors通过的提案。Learner可以通过发起一次prepare来得到是否已经有value被选定。（这里可能有一个恰巧，即，实际Accept的Acceptor的大多数集合S和Learner发起提案对应响应的Acceptor的大多数集合S'，可能正好是两个最大不相同集合，此时交集的Acceptor可能正好挂掉。此时Learner就无法获取到选定的value，不过这不影响正确性，Learner得等待。比如等待超时，再发起一次prepare直到选定）

（从这里可以看到，只有Learner有完整的提案集合。那么选择leader当然只能从Learner集合中选择出来。）

进展（Progress）
很容易构造出一种情况，两个Proposer不断提出propose，并且每个Proposer的Phase 1都被超过一半的Acceptors通过，这样不断被新的Phase 1即prepare互相通过，导致都不能进入到Phase 2，即accept。

为了保证进度，必须选择一个特定的Proposer来作为一个唯一的提案提出者。如果这个Proposer可以同半数以上的Acceptors通信，同时，可以使用一个xk比现有的编号都大的编号来发起提案，那么它就可以成功的产生一个可以被通过的提案。再有，当它知道某些更高的编号的请求时，舍弃当前的提案并重做，这个Proposer最终一定会产生一个足够大的提案编号。（这里必须这样处理，保证安全性，因为有可能有两个Proposer认为自己是Leader，使用更高的编号）。

如果系统中有足够的组件（Proposer,Acceptors及通信网络）工作良好，通过选择一个特定的Proposer作为Leader就可以满足活性。著名的FLP结论指出，一个可靠的Proposer选举算法要么利用随机性，要么利用实时性来实现--比如使用超时机制（随即超时机制避免活锁）。不过无论选举是否成功，安全性都可以保证。

实现
Paxos算法假设了一组进程网络。在它的一致性算法中，每个进程扮演着Proposer,Acceptor及Learner的角色，该算法选定了一个Leader来扮演那个特定的Proposer和Learner.Paxos一致性算法就是上面描述的那个，请求和响应都是以普通的消息的方式发送（响应消息通过对应的提案编号来标识防止混淆）。使用可靠性的存储设备来存储Acceptor需要记住的信息来防止出错。Acceptor在真正送出响应之前，会将它记录在可靠性存储设备中。

如何保证编号唯一性？不同的Proposers可以使用等差数列，步长相同，不过不同的Proposer的起始值不同，就能保证任何的Proposer发出的提案均不相同。
每个Proposer需要将它目前生成的最大编号的提案记录在可靠性存储设备中，然后用一个比已经使用的所有编号都大的提案开始Phase 1。

实现状态机模型
实现分布式系统的一种简单方式就是，使用一组客户端集合然后向一个中央服务器发送命令。服务器可以看成是一个以某种顺序执行客户端命令的确定性状态机。该状态机有一个当前状态，通过输入一个命令来产生一个输出以及一个新的状态。比如一个分布式银行系统的客户端可能是一些出纳员，状态机状态由所有用户的账户余额组成。一个取款操作，通过执行一个减少账户余额的状态机命令（当且仅当余额大于等于取款数目时）实现，将新旧余额作为输出。

使用中央服务器的系统在该服务器失败的情况下，整个系统就失败了。因此，我们使用一组服务器来代替它，每个服务器独立实现了该状态机。因为状态机是确定性的，如果它们都按照相同的命令顺序执行，那么就会产生相同的状态机状态和输出。一个产生命令的客户端，就可以使用任意的服务器为它产生输出。

为了保证所有的服务器都执行相同的状态机命令序列，我们需要实现一系列独立的Paxos一致性算法实例，第i个实例选定的值作为序列中的第i个状态机命令。在算法的每个实例中，每个服务器担任所有的角色（Proposer、Acceptor和Learner）。现在，我们假设服务器集合是固定的，这样所有的一致性算法实例都具有相同的参与者合集。

在正常执行中，一个服务器会被选为Leader,它会在所有的一致性算法实例中被选作特定的Proposer（唯一的提案提出者）。客户端向该Leader发送命令，它来决定每个命令被安排在序列中的何处。如果Leader决定某个客户端命令应该是第135个命令，它会尝试让该命令xk成为第135个一致性算法实例选定的value值。通常这都会成功，但是由于出错或者另一个服务器认为自己是leader,而它对第135个命令持有异议。但是一致性算法可以保证，最多只有一个命令会被选定为第135个命令。

这种策略的关键在于，在Paxos一致性算法中，被提出的value只有在phase 2才会被选定。回忆一下，在Proposer的Phase 1完成时，要么提案的value已经确定了，要么Proposer可以自由地提出一个值。

现在我们已经知道在正常运行Phase 1：

• Proposer选择一个提案编号n,然后向Acceptors的某个majority集合的成员发送编号为n的prepare请求。
• 如果一个Acceptor受到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号，那么它就会保证不会在通过(accept)任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在的话）作为响应。

Phase 2：

• 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n,value值为v的提案的accept请求给Acceptors,在这里v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。
• 如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未对编号大于n的prepare请求做出响应，它就可以通过这个提案。时，paxos状态机实现是如何工作的。下面看出错的情况，看之前的leader失败以及新leader被选定后会发生什么？（系统启动是一种特殊情况，此时还没有命令被提出）

新的Leader被选出来，首先要成为所有一致性算法执行实例的Learner,需要知道目前已经想定的大部分命令。假设它知道命令1-134,138及139,也就是一致性算法实例1-134,138及139选定的值。（注意，这里只是说知道选定的值，还没有应用到状态机，需要把缺口的实例选定的值先确定下来，才能依次应用到状态机）让后它需要执行135-137以及所有其它大于139的算法执行实例的phase 1（这里有个优化，下面说）。假设执行结果表明，实例135和140中提出的提案值已经确定了。但是其它执行实例的提案值是没有限定的。那么现在该Leader就可以为135和140执行Phase 2,进而选定第135和140号命令。

Leader以及其它所有已经获取该Leader的已知命令的服务器，现在可以执行命令1-135，但还不能执行138-140,因为136和137还未选定。Leader可以将下两个到来的客户端请求命令作为命令136和137。但我们也可以提起一个特殊的noop命令作为136和137命令来尽快填补空缺（通过执行一致性算法实例136和137的Phase 2来完成）。一旦该noop命令被选定，命令138-140就可以执行了。（注意这里，如果不使用noop来填充，而是让后续到来的请求复用这两个instance，可能会造成状态机不满足顺序一致性，因为最新的命令使用了老的instance id。不过paxos仅仅保证了单个instance的安全性和正确性，保证其达成共识，并未保证上层应用的状态机的顺序一致性（可以理解为两套系统，互相不感知），不过这里填noop恰好能够满足上层应用状态机的顺序一致性）。

命令1-140目前已被选定了。Leader也已经完成了所有大于140的一致性算法实例的Phase 1（这里是一个优化，使用同时个编号来应用之后大于140的实例的phase 1，即大于140的提案的编号都复用同样的值，这样可以省去为每个instance执行一遍phase 1，前提是Leader是稳定的情况下，提案的编号相同，但是instance的值不同，直接可以将两个值携带到消息体中，这样只需要phase 2来达成共识即可。因为如果大于140的有已经通过的value时候，Acceptor会返回的，这样才能放心将某个范围的编号的phase 1省略）而且在这些实例中，它可以自由地提出任何值。它将下一个客户端的请求命令作为第141个命令，并且在Phase2中将它作为一致性算法的第141个实例的value值。它会将下一个客户端的请求命令作为命令142，如此 ...

Leader 可以在它提出的命令141被选定前提出命令142，。它发送的关于命令141的消息有可能全部丢失，因此在所有其他服务器在获知Leader选定了谁作为命令141之前，命令142就可能已被选定。当Leader无法收到实例141的Phase 2的期望响应之后，它会重传这些信息，当时重传这些信息，但是仍然可能会失败，这样就在被选定的命令序列中出现了缺口。假设一个Leader可以他们确定a个命令，这意味着在i被选定之后，它就可以提出命令 i + 1到 i + a的命令了。这样就可能形成一个长达 a - 1的命令缺口。

一个新选择的Leader需要为无数个一致性算法实例执行Phase 1（为了确定那些还未知的instance是否选定了值）--在上面的情景中，就是135-137以及所有大于139的实例。只要向其他的服务器发送一个合适的消息内容，就可以让所有的执行实例使用同一个提案编号（大于之前所有的）。（注：这里是一个优化，使用一个更大的提案编号来作为这个优化消息的编号，消息内容是所有需要确定的instance的范围，一并发送给了Acceptor）。在Phase 1,只要一个Acceptor以及收到来自某个Proposer的phase 2消息，那么它就可以为不止一个的执行实例作出承诺。（在上面的场景中，就是针对135和140的情况）因此一个服务器（作为Acceptor角色时）通过选择一个适当的短消息就可以对所有的实例作出响应，那么执行这样无限多个实例的Phase 1也就不会有问题。（注：此时Acceptor需要根据收到的需要确定是否选定value的的instance范围逐个检查并回复，这样避免了为每个instance单独执行一次phase 1的开销）。

因为Leader的失败和新Leader的选举都是很少见的情况，因此执行一个状态机命令--即在命令值上达成一致性的花费就是执行该一致性算法的Phase 2的花费。（注：因为此时Leader是一直都存在的，progress是一定保证的，不会存在提案编号冲突的情况，Proposer没有任何并行提出提案的情况，所以不需要变化提案号，也就不需要prepare的过程，其实此时就退化成了raft了）。

在该系统的正常执行下，我们假设总是只有一个Leader,只有在当前的Leader失效及选举新Leader的较短时间内才会违背这个假设。在特殊情况下，Leader选举可能失败。如果没有服务器担任Leader,那么就没有新命令被提出。如果同时有多个服务器认为自己是Leader，它们在一个一致性算法执行实例中可能提出不同的value，这可能会导致无法选出一个value，但是，安全性一直都可以保证--即不可能会同时有两个命令被选定为第i个状态机命令。Leader的选举只是为了保证progress。

如果服务器集合是变化的，那么必须有某种方式来决定哪些服务器来实现哪些实例。配置的变更最直接的方式是将配置本身作为状态的一部分。只需要确定从哪个instance开始使用新的配置。比如i之前使用旧的服务器集合，i之后使用新的服务器集合。配置的变更同样使用一次paxos instance的方式来决定。这就提供了一种支持任意负载的重配置算法的简单实现。

The End;

我对Paxos的理解一直不够深刻，说句实在的，是没有理解。没有理解的地方在于：

1. Paxos made simple里面讲解的是一次 paxos 实例还是多次paxos 实例？
2. gap 的填充具体逻辑是什么？具体的流程是什么？
3. learner 是怎么运作的？
4. leader 为什么一开始是一个learner？
5. leader 如何把 pending 的 paxos instance 确定下来？

看完后回答的，现在尝试再回答之前自己的疑问：

1. Paxos made simple里面讲解的是一次 paxos 实例还是多次paxos 实例？
   答：Paxos made simple 大部分都在讲一次paxos instance达成共识的过程。一步步推演，最终得到一个既保证了safety,又保证了liveness的算法，不过此时已经不是单纯的单个paxos instance过程，为了保证liveness，引入了multi-paxos即Leader的思想。而单个paxos instance的执行过程则分为两个阶段：
   Phase 1：

• Proposer选择一个提案编号n,然后向Acceptors的某个majority集合的成员发送编号为n的prepare请求。
• 如果一个Acceptor受到一个编号为n的prepare请求，且n大于它已经响应的所有prepare请求的编号，那么它就会保证不会在通过(accept)任何编号小于n的提案，同时将它已经通过的最大编号的提案（如果存在的话）作为响应。

Phase 2：

• 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求（编号为n）的响应，那么它就会发送一个针对编号为n,value值为v的提案的accept请求给Acceptors,在这里v是收到的响应中编号最大的提案的值，如果响应中不包含提案，那么它就是任意值。
• 如果Acceptor收到一个针对编号n的提案的accept请求，只要它还未对编号大于n的prepare请求做出响应，它就可以通过这个提案。

2. gap 的填充具体逻辑是什么？具体的流程？
   答：gap 通过发起一次phase 1来向Acceptor探测哪些达成了共识，对达成共识的，执行phase 2，填充，可以随意值的，可以填noop，或者让后续的提案复用老的值。不过这里当心对于应用层的状态机顺序一致性的保证。

3. learner 是怎么运作的？
   答：learner 是通过Acceptor告诉它那些提案被选定了，learner通过统计如果大多数的Acceptor都accept了，其可以认为这个提案已经选定了。learner会作为leader的备选集合。

4. leader 为什么一开始是一个learner？
   答：因为只有learner才可能有接近完整的所有提案共识的结果，所有的Acceptor都将accept的结果直接发送给learner。

5. leader 如何把 pending 的 paxos instance 确定下来？
   答：这个问题和问题2很接近，leader通过对pending的paxos instance执行一次phase 1。然后选择要么phase 2给定值，要么给noop值，取决于Acceptor是否已经接受过。