分布式协议及Zookeeper实现(Paxos、2PC、3PC)(一)

约定不等于承诺〃 2022-02-15 18:43 242阅读 0赞

CAP 理论，即对于一个分布式系统而言，它是无法同时满足 **Consistency**(一致性)、**Availability**(可用性) 和 **Partition** **tolerance**(分区容错性) 这三个条件，最多只能满足其中两个。由于网络环境是不可信的，所以分区容忍性几乎是必不可选的，设计者基本就是在一致性和可用性之间做选择，当然大部分情况下，大家都会选择牺牲一部分的一致性来保证可用性（可用性较差的系统非常影响用户体验的，但是对另一些场景，比如支付场景，强一致性是必须要满足）。但是分布式系统又无法彻底放弃一致性（Consistency），如果真的放弃一致性，那么就说明这个系统中的数据根本不可信，数据也就没有意义，那么这个系统也就没有任何价值可言。

# CAP 理论 #

CAP 理论三个特性的详细含义如下：

1.  一致性（Consistency）： 在分布式环境中，一致性是指数据在多个副本之间是否能够保持一致的特性。
2.  可用性（Availability）：可用性是指系统提供的服务必须一直处于可用的状态，对于用户的每一个操作请求总是能够在有限的时间内返回结果。
    
    **         “有限的时间内”是指对于用户的一个操作请求，系统必须能够在指定的时间（即响应时间）内返回对应的处理结果，如果超过了这个时间范围，那么系统就被认为是不可用的。**
    
             **“返回结果”是可用性的另一个非常重要的指标，它要求系统在完成对用户请求的处理后，返回一个正常的响应结果。正常的响应结果通常能够明确的反映出对请求的处理结果，即成功或失败，而不是一个让用户感到困惑的返回结果。**
3.  分区容错性（Partition tolerance）：分布式系统在遇到任何网络分区故障的时候，仍然需要能够保证对外提供满足一致性和可用性的服务，除非是整个网络环境都发生了故障。

**  注：网络分区是指在分布式系统中，不同的节点分布在不同的子网络（机房或异地网络等）中，由于一些特殊的原因导致这些子网络之间出现网络不连通的状况，但各个子网络的内部网络是正常的，从而导致整个系统的网络环境被切分成了若干个孤立的区域。 **

<table> 
 <tbody> 
  <tr> 
   <td style="vertical-align:top;width:160px;"> <p>放弃CAP定理内容</p> </td> 
   <td style="vertical-align:top;width:688px;"> <p>说明</p> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:160px;"> <p>放弃P</p> </td> 
   <td style="vertical-align:top;width:688px;"> <p>放弃P，就是将所有的数据（或者是跟事物相关）都放在一个分布式节点上。这意味着系统不再是一个分布式系统了。也意味着放弃了系统的扩展性。</p> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:160px;"> <p>放弃A</p> </td> 
   <td style="vertical-align:top;width:688px;"> <p>一旦系统遇到网络分区或其它故障时，那么受到影响的服务需要等待一定的时间，在此期间系统无法对外提供正常的服务，即不可用。</p> </td> 
  </tr> 
  <tr> 
   <td style="vertical-align:top;width:160px;"> <p>放弃C</p> </td> 
   <td style="vertical-align:top;width:688px;"> <p>放弃C，指的是放弃数据的强一致性（实时一致性），而保留数据的最终一致性。这就引入了一个时间窗口的概念，具体多久能够达到数据一致取决于系统的设计，主要包括主副本在不同节点之间的复制时间长短。</p> </td> 
  </tr> 
 </tbody> 
</table>

# BASE理论 #

*   * BASE是BasicallyAvailable(基本可用)、Soft state(软状态)和Eventually consistent(最终一致性)三个短语的简写。*BASE理论是对CAP理论的延伸，核心思想是即使无法做到强一致性（Strong Consistency，CAP的一致性就是强一致性），但应用可以采用适合的方式达到最终一致性（Eventual Consitency）*

## 基本可用 ##

基本可用是指分布式系统在出现不可预知故障的时候，允许损失部分可用性。（因为网络问题，响应的延迟。请求过多的服务降级等）

## 弱状态（或软状态） ##

和硬状态相对，是指允许系统中的数据存在中间状态，并认为该中间状态的存在不会影响系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步的过程存在延时。

## 最终一致性 ##

最终一致性强调的是系统中所有的数据副本，在经过一段时间的同步后，最终能够达到一个一致的状态。因此最终一致性的本质是需要系统保证最终数据能够达到一致，而不需要实时保证系统数据的强一致性。

在没有发生故障的情况下，数据达到一致状态的时间延迟，取决于网络延迟、系统负载和数据复制方案设计等因素。

在实际工程中，最终一致性有五类变种:

*  因果一致性：如果进程A在更新完某个数据项后通知了进程B，那么进程B之后对该数据项的访问都应该能够获得进程A更新后的最新值。
 *  读己所写一致性：进程A更新了一个数据项之后，它自己总能是能够访问到数据更新过的最新值。而不会看到旧值。
 *  会话一致性：对系统数据的访问过程框定到了一个会话中：系统能够保证在同一个会话中更新数据后始终能获取到该数据项的最新值。
 *  单调读一致性：一个进程从系统中读取一个数据项的某个值后，那么系统对于该进程后续的任何数据访问都不应该返回更旧的值。
 *  单调写一致性：一个系统能够保证来自同一个进程的写操作被顺序执行。

# 一致性协议 #

**为了解决分布式的一致性问题，在长期的研究探索过程中，涌现出了一大批经典的一致性协议和算法，其中比较著名的有二阶段提交协议，三阶段提交协议和Paxos算法。**

## 2PC与3PC ##

**在分布式系统中，每一个机器节点虽然都能明确的知道自己执行的事务是成功还是失败，但是却无法知道其他分布式节点的事务执行情况。因此，当一个事务要跨越多个分布式节点的时候，为了保证该事务可以满足ACID，就要引入一个协调者（Cooradinator）。其他的节点被称为参与者（Participant）。协调者负责调度参与者的行为，并最终决定这些参与者是否要把事务进行提交。基于这个思想，衍生出了二阶段提交和三阶段提交两种协议。**

### 2PC ###

**    2PC，二阶段提交协议，即将事务的提交过程分为两个阶段来进行处理：准备阶段和提交阶段。事务的发起者称协调者，事务的执行者称参与者。**

**第一阶段：提交事务阶段(投票阶段)**

1.  事务询问：协调者会询问所有的参与者结点，是否可以执行提交操作，并等待响应。
2.  执行事务：各个参与者执行事务操作，并将Undo和Redo信息记入事务日志中。
3.  参与者向协调者反馈事务询问的响应：如果参与者成功执行了事务操作，反馈给协调者Yes响应，否则No响应表示事物不可执行。

**第二阶段：执行事务提交(执行阶段)**  
    协调者根据各个参与者的反馈情况来决定是否可以进行事物的提交操作，因此有两种可能：

**执行：**

1.  发送提交请求：协调者向参与者发送Commit请求。
2.  事务提交：参与者接受到Commit请求后，会正式执行事务提交操作，并在完成提交之后释放执行期间占用的事务资源。
3.  反馈事务提交结果：参与者在完成事务提交之后，向协调者发送Ack消息。
4.  完成事务：协调者接受到所有参与者反馈的Ack消息后，完成事务。

**中断：**

1.  发送回滚请求：协调者向所有参与者发送Rollback请求。
2.  事务回滚：参与者接受到Rollback请求后，利用Undo信息来执行事务回滚，并释放事务资源。
3.  反馈事务回滚结果：参与者在完成事务回滚之后，向协调者发送Ack消息。
4.  中断事务：协调者接收到所有参与者反馈的Ack消息之后，完成中断事务。

**二阶段提交优点：原理简单，实现方便**

**二阶段提交缺点：同步阻塞、单点问题、脑裂、太过保守**

**1、同步阻塞**

**   ** 二阶段提交过程中，所有参与该事物操作的逻辑都处于阻塞状态。各参与者等待其他参与者响应的过程中。将无法进行其他操作。这会很影响分布式系统的性能。  
**2、单点问题**

协调者一旦出现问题，整个二阶段提交过程都无法进行。如果协调者是在阶段二中出现问题，那么参与者将会一直处于锁定事务资源的状态中，而无法完成事务操作。  
**3、脑裂（数据不一致）**

**   ** 当协调者向所有参与者commit请求后，发生局部网络异常或者协调者尚未发送完commit请求之前自身发送崩溃。导致只有部分参与者收到commi请求。这部分收到请求的参与者就会进行事务提交，而没收到commit请求的参与者无法事务提交。因此造成了整个分布式系统数据不一致。  
**4、太过保守**

如果协调者指示参与者进行事务提交询问的过程中，参与者出现故障而导致协调者始终无法获取到所有参与者的响应信息。协调者只能依靠自身的超时机制来判断是否需要中断事务，这样做有些保守。因为二阶段提交没有设计完善的容错机制，任何一个节点的失败都会导致整个事物的失败。

### 3PC ###

**3PC，三阶段提交协议，是2PC的改进版本，即将事务的提交过程分为CanCommit、PreCommit、doCommit三个阶段来进行处理。**

**阶段1：CanCommit**

1.  事物询问：协调者向所有参与者发出包含事务内容的CanCommit请求，询问是否可以提交事务，并等待所有参与者响应。
2.  各参与者向协调者反馈事物询问的响应：参与者收到CanCommit请求后，如果认为可以执行事务操作，则反馈YES并进入预备状态，否则反馈NO。

**阶段2：PreCommit**  
    协调者根据参与者反馈来决定是否可以进行事物的PreCommit操作，有两种情况：

所有参与者均反馈YES，即执行事务预提交。  
　　**事务预提交：（所有参与者均反馈YES时）**

1.  发送预提交请求：协调者向所有参与者发出PreCommit请求，进入准备阶段。
2.  事物预提交：参与者收到PreCommit请求后，会执行事务操作，将Undo和Redo信息记入事务日志中（但不提交事务）。
3.  各参与者向协调者反馈事物执行的响应：如果参与者成功执行了事物操作，那就反馈给协调者Ack响应，同时等待最终的指令：提交或者终止。

任何一个参与者反馈NO，或者等待超时后协调者尚无法收到所有参与者的反馈，即中断事务。  
　　**中断事务：（任何一个参与者反馈NO，或者等待超时后协调者尚无法收到所有参与者的反馈时）**

1.  发送中断请求：协调者向所有参与者发出abort请求。
2.  中断事物：无论收到协调者发出的abort请求，或者在等待协调者请求过程中出现超时，参与者均会中断事务。

**阶段3：doCommit**  
   
　　**提交事务：（所有参与者均反馈Ack响应时）**

1.  发送提交请求：如果协调者处于工作状态，并且接受所有参与者的Ack响应，那么他会从预提交转换为提交状态，并向所有参与者发出do Commit请求。
2.  事物提交：参与者收到doCommit请求后，会正式执行事务提交操作，并完成提交之后释放整个事务期间占用的资源。
3.  反馈事物提交结果：各参与者完成事物提交之后，向协调者反馈Ack完成的消息。
4.  完成事务：协调者收到所有参与者反馈的Ack消息后，即完成事务提交。

**中断事务：（任何一个参与者反馈NO，或者等待超时后协调者尚无法收到所有参与者的反馈时）**  
发送中断请求：如果协调者处于工作状态，向所有参与者发出abort请求。

1.  事物回滚：参与者接收到abort请求后，会使用阶段二中记录的Undo信息执行回滚操作，并在完成回滚之后释放整个事务期间占用的资源。
2.  反馈事物回滚结果：参与者完成回滚后，各参与者向协调者反馈Ack消息。
3.  中断事物：协调者收到所有参与者反馈的Ack消息后，完成事务中断。

**三阶段提交协议的优点：相对于二阶段协议降低了阻塞范围，在等待超时后协调者或参与者会中断事务。避免了协调者单点故障，阶段3中协调者出现问题时，参与者会继续提交事务。  
   
三阶段提交协议的缺陷：脑裂问题依然存在，即在参与者收到PreCommit请求后等待最终指令，如果此时协调者无法与参与者正常通信，会导致参与者继续提交事务，造成数据不一致。 **

## Paxos算法 ##

**    Paxos 算法是分布式一致性算法用来解决一个分布式系统如何就某个值(决议)达成一致的问题。**

**paxos算法介绍**

Paxos保证以下三点：

1.  只有被提出提案才能被选定； 
2.  只有一个值被选定； 
3.  如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个。

该一致性算法中有三个角色，分别是：proposer，acceptor，learner。它们之间通过消息来通讯。

1.  Proposer：只要Proposer发的提案被Acceptor接受（刚开始先认为只需要一个Acceptor接受即可，在推导过程中会发现需要半数以上的Acceptor同意才行），Proposer就认为该提案里的value被选定了。
2.  Acceptor：只要Acceptor接受了某个提案，Acceptor就任务该提案里的value被选定了。
3.  Learner：Acceptor告诉Learner哪个value被选定，Learner就认为那个value被选定。

**Paxos的目标：保证最终有一个value会被选定，当value被选定后，进程最终也能获取到被选定的value。 **

### 提案的选举 ###

要选定一个唯一提案的最简单方式莫过于只允许一个Accpetor存在，这样的话，Proposer只能发送提案给该Accpetor，Acceptor会选择他接收到的第一个提案作为被选定的提案。

但是，如果这个唯一的Acceptor宕机了，那么整个系统就**无法工作**了！

因此，应该寻找一种更好的解决方式，例如可以使用多个Accpetor来避免Accpetor的单点问题。在存在多个Acceptor的情况下，如何进行提案的选取：Proposer向一个Acceptor集合发送提案，同样，集合中的每个Acceptor都可能会批准（Accept）该提案，当有足够多的Acceptor批准这个提案的时候，我们就可以认为该提案被选定了。我们假定足够多的Acceptor是整个Acceptor集合的一个子集，并且让这个集合大的可以包含Acceptor集合中的大多数成员，因为任意两个包含大多数Acceptor的子集至少有一个公共成员。另外我们再规定，每一个Acceptor最多只能批准一个提案，那么就能保证只有一个提案被选定了。

### 推导过程 ###

在没有失败和消息丢失的情况下，如果希望即使在只有一个提案被提出的情况下，仍然可以选出一个提案，这就按时了如下的需求。

> **P1：一个Acceptor必须批准他收到的第一个提案。**

上面这个需求就引出了另外一个问题：如果有多个提案被不同的Proposer同时提出，这可能会导致虽然每个Acceptor都批准了他收到的第一个提案，但是没有一个提案是由多数人都批准的。下图就是这样的场景。

> ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70][]

上图所示就是不同的Proposer分别提出了多个提案的场景，在这种场景下，是无法选定一个提案的。另外，即使只有两个提案被提出，如果每个提案都被差不多一般的Acceptor批准了，此时即使只有一个Acceptor出错，都有可能导致无法确定该选定哪个提案，下图所示就是这样的场景。

> ![20171124155731248][]

上图所示就是一个典型的在任意一个Acceptor出现问题的情况下，无法选定提案的情况。在这个例子中，共有5个Acceptor，其中2个批准了提案V1，另外3个批准了提案V2，此时如果批准V2的3个Acceptor中有一个（上图的第5个Acceptor）出错了，那么V1和V2的批准者都变成了2个，此时无法选定最终的提案了。

因此，在P1的基础上，再加上一个提案被选定需要由半数以上的Acceptor批准的需求按时着一个Acceptor必须能够批准不止一个提案。在这里，我们使用一个全局的编号（这种全局唯一编号的生成并不是Paxos算法需要关注的地方，就算法本身而言，其假设当前已经具备这样的外部组件能够生成一个全局唯一的编号）来唯一标识每一个被Acceptor批准的提案，当一个具有某Value值的提案被半数以上的Acceptor批准后，我们就认为该Value被选定了，此时我们也认为该提案被选定了。需要注意的是，此处讲到的提案已经和Value不是同一个概念了，提案变成了一个由编号和Value组成的组合体，因此我们以“\[编号 ,Value\]”来表示一个提案。

根据上面讲到的额内容，我们虽然允许多个提案被选定，但同时必须要保证所有被选定的提案都具有相同的Value值——这是一个关于提案Value的约定，结合提案的编号，该约定可以定义如下：

> **P2：如果编号为M0、Value值为V0的提案（即\[M0 , V0\]）被选定了，那么所有比编号M0更高的，且被选定的提案，其Value值必须也是V0。**

因为提案的编号是全序的，条件P2就保证了只有一个Value值被选定这一关键安全性属性。同时，一个提案要被选定，其首先必须被至少一个Acceptor批准，因此我们可以通过满足如下条件来满足P2。

> **P2a：如果编号为M0、Value值为V0的提案（即\[M0 , V0\]）被选定了，那么所有比编号M0更高的，且被Acceptor批准的提案，其Value值必须也是V0。**

至此，我们仍然需要P1来保证提案会被选定，但是因为通信是异步的，一个提案可能会在某个Acceptor还未受到任何提案时就被选定了。如下图所示。

> ![20171124161601052][]

如上图所示，在Acceptor I 没有收到任何提案的情况下，其他4个Acceptor已经批准了来自Proposer2的提案\[M0，V1\]，而此时，Proposer 1 产生了一个具有其他Value值的、编号更高的提案\[M1，V2\]，并发送给了Acceptor 1。根据P1，就需要Acceptor 1 批准该提案，但是这与P2a矛盾，因此如果要同时满足P1和P2a，需要对P2a进行如下强化：

> **P2b：如果一个提案\[M0 , V0\]被选定后，那么之后任何Proposer产生的编号更高的提案，其Value值都为V0。**

因为一个提案必须在被Proposer提出后才能被Acceptor批准，因此P2b包含了P2a，进而包含了P2。于是，接下去的重点就是论证P2b成立即可：

> **假设某个提案\[M0 , V0\]已经被选定了，证明任何编号Mn>M0的提案，其Value值都是V0。**

以上可用数学归纳法来进行证明。

### Proposer生成提案 ###

在P2c的基础上如何进行提案的生成。对于一个Proposer来说，获取那些已经被通过的提案远比预测未来可能会被通过的提案来的简单。因此，Proposer在产生一个编号为Mn的提案时，必须要知道当前某一个将要或已经被半数以上Acceptor批准的编号小于Mn但为最大编号的提案。并且，Proposer会要求所有的Acceptor都不要再批准任何编号小于Mn的提案——这就引出了如下的提案生成算法。

*  Proposer选择一个新的提案编号Mn，然后向某个Acceptor集合的成员发送请求，要求该集合中的Acceptor做出回应。
    
    1.  向Proposer承诺，保证不再批准任何编号小于Mn的提案。
    2.  如果Acceptor已经批准过任何提案，那么其就向Proposer反馈当前该Acceptor已经批准的编号小于Mn但为最大编号的那个提案的值。

> 我们将该请求称为编号为Mn的提案的Prepare请求。

*  如果Proposer收到了来自半数以上的Acceptor的响应结果，那么他就可以产生编号为Mn、Value值为Vn的提案，这里的Vn是所有响应中编号最大的提案的Value值。当然还存在另一种情况，就是半数以上的Acceptor都哦没有批准过任何提案，即响应中不包含任何的提案，那么此时Vn值就可以由Proposer任意选择。

在确定提案之后，Proposer就会将该提案再次发送给某个Acceptor集合，并期望获得他们的批准，我们称此请求为Accept请求。需要注意的一点事，此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合。任意两个半数以上的Acceptor集合，必定包含至少一个公共Acceptor。

### Acceptor批准提案 ###

在上文已经讲解了Paxos算法中Proposer的处理逻辑，下面我们来看看Acceptor是如何批准提案的。

根据上面的内容，一个Acceptor可能会收到来自Proposer的两种请求，分别是Prepare请求和Accept请求，对这两类请求做出响应的条件分别如下。

*  **Prepare请求：**Acceptor可以在任何时候响应一个Prepare请求。
 *  **Accept请求：**在不违背Accept现有承诺的前提下，可以任意响应Accept请求。

因此，对Acceptor逻辑处理的约束条件，大体可以定义如下。

> **P1a：一个Acceptor只要尚未响应过任何编号大于Mn的Prepare请求，那么他就可以接受这个编号为Mn的提案。**

从这个约束条件中，我们可以看出，P1a包含了P1。同时，值得一提的是，Paxos算法允许Acceptor忽略任何请求而不用担心破坏其算法的安全性。

### 算法优化 ###

在上面的内容中，我们分别从Proposer和Acceptor对提案的生成和批准两方面来讲解了Paxos算法在提案选定过程中的算法细节，同时也在提案的编号全局唯一的前提下，获得了一个满足安全性需求的提案选定算法，接下来我们再对这个初步算法做一个小优化。尽可能的忽略Prepare请求：

> 假设一个Acceptor收到了一个编号为Mn的Prepare请求，但此时该Acceptor已经对编号大于Mn的Prepare请求做出了响应，因此他肯定不会再批准任何新的编号为Mn的提案，那么很显然，Acceptor就没有必要对这个Prepare请求做出响应，于是Acceptor可以选择忽略这样的Prepare请求。同时，Acceptor也可以忽略掉那些他已经批准过的提案的Prepare请求。

通过这个优化，每个Acceptor只需要记住他已经批准的提案的最大编号以及他已经做出Prepare请求响应的提案的最大编号，以便在出现故障或节点重启的情况下，也能保证P2c的不变性。而对于Proposer来说，只要他可以保证不会产生具有相同编号的提案，那么就可以丢弃任意的提案以及他所有运行时状态信息。

### 算法陈述 ###

综合前面讲解的内容，结合Proposer和Acceptor对提案的处理逻辑，就可以得到如下类似于两阶段提交的算法执行过程。

**阶段一**

1.  Proposer选择一个提案编号Mn，然后向Acceptor的某个超过半数的子集成员发送编号为Mn的Prepare请求。
2.  如果一个Acceptor收到一个编号为Mn的Prepare请求，且编号Mn大于该Acceptor已经响应的所有Prepare请求的编号，那么他就会将它已经批准过的最大编号的提案作为响应反馈给Proposer，同时该Acceptor会承诺不会再批准任何编号小于Mn的提案。

*    举个例子来说，假定一个Acceptor已经响应过的所有Prepare请求对应的提案编号分别为1、2、...、5和7，那么该Acceptor在接收到一个编号为8的Prepare请求后，就会将编号为7的提案作为响应反馈给Proposer。 *

**阶段二**

1.  如果Proposer收到来自半数以上的Acceptor对于其发出的编号为Mn的Prepare请求的响应，那么他就会发送一个针对\[Mn , Vn\]提案的 Accept 请求给 Acceptor。注意，Vn的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么他就是任意值。
2.  如果Acceptor收到这个针对\[Mn , Vn\]提案的Accept请求，只要该Acceptor尚未对编号大于Mn的Prepare请求做出响应，他就可以通过这个提案。

在实际运行过程中，每一个Proposer都有可能会产生多个提案，但只要每个Proposer都遵循如上所述的算法运行，就一定能够保证算法执行的正确性。每个Proposer都可以在任意时刻丢弃一个提案，哪怕针对该提案的请求和响应在提案被丢弃后会到达，但根据Paxos算法的一系列规约，依然可以保证其在提案选定上的正确性。事实上，如果某个Proposer已经在试图生成编号更大的提案，那么丢弃一些旧的提案未尝不是一个好的选择。因此，如果一个Acceptor因为已经收到过更大编号的Prepare请求而忽略某个编号更小的Prepare或者Accept请求，那么他也应当通知其对应的Proposer，以便该Proposer也能够将该提案进行丢弃——这和上面“”算法优化“”部分中提到的提案丢弃是一致的。

### 提案的获取 ###

在上文中介绍了如何而来选定一个提案，下面再来看看如何让Learner获取提案，大体可以有以下几种方案。

**方案一**

>  
> 
> Learner获取一个已经被选定的提案的前提是，该提案已经被半数以上的Acceptor批准。因此，最简单的做法就是一旦Acceptor批准了一个提案，就将该提案发送给所有的Learner。
> 
> 很显然这种做法虽然可以让Learner尽快的获取被选定的提案，但是却需要让每个Acceptor与所有的Learner逐个进行一次通信，通信的次数至少为二者个数的乘积。

**方案二**

> 另一种可行的方案是，我们可以让所有的Acceptor将他们对提案的批准情况，统一发送给一个特定的Learner（下文中我们将这样的Learner称为“主Learner”），在不考虑拜占庭将军问题的前提下，我们假定Learner之间可以通过消息通信来互相感知提案的选定情况。基于这样的前提，当主Learner被通知一个提案已经被选定时，他会负责通知其他的Learner。
> 
> 在这种方案中，Acceptor首先会将得到批准的提案发送给主Learner，再由其同步给其他Learner，因此较方法一而言，方案二虽然需要多一个步骤才能将提案通知到所有的Learner，但其通信次数却大大减少了，通常只是Acceptor和Learner的个数总和。但同时，该方案引入了一个新的不稳定因素：主Learner随时可能出现故障。

**方案三**

> 在讲解方案二的时候，我们提到，方案二最大的问题在于主Learner存在单点问题，即主Learner随时可能出现故障。因此对方案二进行改进，可以将主Learner的范围扩大，即Acceptor可以将批准的提案发送给一个特定的Learner集合，该集合中的每个Learner都可以在一个提案被选定后通知所有其他的Learner。这个Learner集合中的Learner个数越多，可靠性就越好，但同时网路通信的复杂度也就越高。

### 通过选取主Proposer保证算法的活性 ###

根据前面的内容讲解，我们已经基本上了解了Paxos算法的核心逻辑，我们再来看看Paxos算法在实际运行过程中的一些细节。假设存在这样一种极端情况，有两个Proposer依次提出了一系列编号递增的议案，但是最终都无法被选定，具体流程如下：

Proposer P1 提出了一个编号为M1的提案，并完成了上述阶段一的流程。但与此同时，另外一个Proposer P2 提出了一个编号为M2（M2>M1）的提案，同样也完成了阶段一的流程，于是Acceptor已经承诺不再批准编号小于M2的提案了。因此，当P1进入阶段二的时候，其发出的Accept请求将被Acceptor忽略，于是P1再次进入阶段一并提出了一个编号为M3（M3>M2）的提案，而这又导致P2在第二阶段的Accept请求被忽略，以此类推，提案的选定过程将陷入死循环，如下图所示。

> ![20171124192603869][]

**为了保证Paxos算法流程的可持续性，以避免陷入上述提到的“死循环”，就必须选择一个主Proposer，并规定只有主Proposer才能提出议案。**这样一来，只要主Proposer和过半的Acceptor能够正常进行网络通信，那么但凡主Proposer提出一个编号更高的提案，该提案终将会被批准。如果Proposer发现当前算法流程中已经有一个编号更大的提案被提出或者正在接受批准。那么他会丢弃目前这个编号较小的提案，并最终选出一个编号足够大的提案。因此，如果系统中有足够多的组件（包括Proposer、Acceptor和其他网络通信组件）能够正常工作，那么通过选择一个主Proposer，整套Paxos算法流程就能够保持活性。

**参考书籍：《从Paxos到Zookeeper 分布式一致性原理与实践》（强烈推荐）**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3NTk4MDEx_size_16_color_FFFFFF_t_70]: /images/20220215/953fd85c1bf24ab49c1c95ec1f1ee1db.png
[20171124155731248]: /images/20220215/71818f1eb2c54bd5bf609f2ac9b71d3d.png
[20171124161601052]: /images/20220215/52f01a26c3b34302b56551950725440b.png
[20171124192603869]: /images/20220215/74d440b2825f4612a190c82e87279b67.png