分布式 Paxos和Fast Paxos算法

待我称王封你为后i 2022-06-03 03:40 311阅读 0赞

## 一. Paxos ##

算法中的参与者主要分为三个角色，同时每个参与者又可兼领多个角色

*  Client：产生议题者 –> 交付Proposer提出
 *  Proposer：提议者 –> 提出提案（提案编号和提议的value）
 *  Acceptor：决策者 –> 收到提案后可以决定是否accept
 *  Learner：最终决策学习者 –> 只能学习被批准的提案

![这里写图片描述][18123808-b860c61793e247919ee3787ead3430ef.png]

Acceptor必须最少大于等于3个，并且必须是奇数个(保证一定产生多数胜出)

保证一致性的方法

*  value只有在被Proposer提出之后才可被批准
 *  在一次Paxos算法执行实例中，只会选择一个value
 *  Learner只可获得被批准的value

四个约束

*  P1： 一个Acceptor必须accept第一次收到的提案;
 *  P2a：一旦一个具有value v的提案被choose，那么之后任何Acceptor再次accept的提案必须具有value v;
 *  P2b：一旦一个具有value v的提案被choose，那么之后任何 Proposer 提出的提案必须具有value v;
 *  P2c：如果一个编号为n的提案具有value v，那么存在一个多数派，要么他们中所有人都没有accept编号小于n的任何提案，要么他们已经accpet的所有编号小于n的提案中编号最大的那个提案具有value v;

### Basic Paxos ###

分为两个阶段

**prepare阶段：**

1.  当Porposer希望提出方案V1，首先发出prepare请求至大多数Acceptor。Prepare请求内容为序列号`<SN1>`;
2.  当Acceptor接收到prepare请求`<SN1>`时，检查自身上次回复过的prepare请求`<SN2>`
3.  如果SN2>SN1，则忽略此请求，直接结束本次批准过程
4.  否则检查上次批准的accept请求（SNx，Vx），并且回复（SNx，Vx）；如果之前没有进行过批准，则简单回复OK

**accept批准阶段：**

1a. 经过一段时间，收到一些Acceptor回复，回复可分为以下几种:

1) 回复数量满足多数派，并且所有的回复都是`<OK>`，则Porposer发出accept请求，请求内容为议案（SN1，V1）;  
2) 回复数量满足多数派，但有的回复为：（SN2，V2），（SN3，V3）……则Porposer找到所有回复中超过半数的那个，假设为（SNx，Vx），则发出accept请求，请求内容为议案（SN1，Vx）  
3) 回复数量不满足多数派，Proposer尝试增加序列号为SN1+，转1继续执行;

1b. 经过一段时间，收到一些Acceptor回复，回复可分为以下几种:

1) 回复数量满足多数派，则确认V1被接受;  
2) 回复数量不满足多数派，V1未被接受，Proposer增加序列号为SN1+，转1继续执行

2.在不违背自己向其他Proposer的承诺的前提下，Acceptor收到accept 请求后即接受并回复这个请求。

**Fast Paxos**

Lamport在40多页的论文中不仅提出了Fast Paxos算法，并且还从工程实践的角度重新描述了Paxos，使其更贴近应用场景。从一般的Client/Server来考虑，Client其实承担了Proposer和Learner的作用，而Server则扮演Acceptor的角色，因此下面重新描述了Paxos算法中的几个角色：

*  Client/Prosposer/Learnder：负责提案并执行提案
 *  Coordinator：：Proposer协调者，可为多个，Client通过Coordinator进行提案
 *  Leader：在众多的Coordinator中指定一个作为Leader
 *  Acceptor：负责对Proposal进行投票表决

就是Client的提案由Coordinator进行，Coordinator存在多个，但只能通过其中被选定Leader进行；提案由Leader交由Server进行表决，之后Client作为Learner学习决议的结果。

这种方式更多地考虑了Client/Server这种通用架构，更清楚地注意到了Client既作为Proposer又作为Learner这一事实。同样要注意到的是，如果Leader宕机了，为了保证算法的正确性需要一个**Leader的选举算法**，但与之前一样，Lamport并不关心这个Leader选举算法，他认为可以简单地通过随机或超时机制实现。

另外在Basic Paxos中，从每次Proposer提案到决议被学习，需要三个通信步骤：

Proposer-----Leader-----Acceptor-----Learner

从直观上来说，Proposer其实更“知道”提交那个Value，如果能让Proposer直接提交value到Acceptor，则可以把通信步骤减少到2个。Fast Paxos便是基于此而产生。

回顾一下Basic Paxos的几个阶段：

*  Phase 1a： Leader提交proposal到Acceptor
 *  Phase 2b：Acceptor回应已经参与投票的最大Proposer编号和选择的Value
 *  Phase 2a：Leader收集Acceptor的返回值  
    
    
     *  Phase 2a.1：如果Acceptor无返回值，则自由决定一个
     *  Phase 2a.2： 如果有返回值，则选择Proposer编号最大的一个
 *  Phase 2b：Acceptor把表决结果发送到Learner

很明显，在Phase2a.1中，如果Leader可以自由决定一个Value，则可以让Proposer提交这个Value，自己则退出通信过程。只要之后的过程运行正常，Leader始终不参与通信，一直有Proposer直接提交Value到Acceptor，从而把Basic Paxos的三阶段通信减少为两阶段，这便是Fast Paxos的由来。因此，我们形式化下Fast Paxos的几个阶段：

*  Phase 1a：Leader提交proposal到Acceptor
 *  Phase 1b：Acceptor回应已经参与投票的最大Proposer编号和选择的Value
 *  Phase 2a：Leader收集Acceptor的返回值  
    
    
     *  Phase 2a.1：如果Acceptor无返回值，则发送一个Any消息给Acceptor，之后Acceptor便等待Proposer提交Value
     *  Phase 2a.2：如果有返回值，则根据规则选取一个
 *  Phase2b：Acceptor把表决结果发送到Learner（包括Leader）

算法主要变化在Phase2a阶段，即：

若Leader可以自由决定一个Value，则发送一条Any消息，Acceptor便等待Proposer提交Value,若Acceptor有返回值，则Acceptor需选择某个Value

先不考虑实现，从形式上消息仅需在

Proposer-----Acceptor-----Learner

之间传递即可，也即仅需2个通信步骤。下面我们详细说明算法过程：

**Quorum**

在Basic Paxos中一直通过多数派（Majority）来保证算法的正确性，对多数派再进一步抽象化，称为“Quorum”，要求任意两个Quorum之间有交集（从而间接表达了majority的含义）

**Round**

在Basic Paxos中，Proposer每次提案都用一个全序的编号表示，如果执行顺利，该编号的Proposal在经历Phase1，Phase2后最终会执行成功。

在Fast Paxos称这个带编号的Proposal的执行过程为“Round”

**i-Quorum**

在Basic Paxos执行过程中，一般不会明确区分每次Round执行的Quorum，虽然也可以为每个Round指定一个Quorum。在Fast Paxos中会通过i-Quorum明确指定Round i需要的Quorum

**Basic Round**

执行Basic Paxos的Round称为Basic Round

**Fast Round**

如果Leader发送了Any消息，则认为后续通信是一个Fast Round；若Leader未发送Any消息，还是跟之前一样通信，则后续行为仍然是Basic Round。

根据Lamport描述，Basic Round和Fast Round可通过Round Number进行加以区分。

**Any消息**

在正常情况下，Leader若可以自由决定一个Value，应该发生一条Phase2a消息，其中包含了选择的Value，但此时却发送了一条无Value的Any消息。Acceptor在接收到Any消息后可做一些开始Fast Round的初始化工作，等待Proposer提交真正的Value。Any消息的意思是Acceptor可以做任意的处理。

因此，一个Fast Round包括两个阶段：由Any消息开始的阶段和由Proposer提交Value的结束阶段，而Leader只是起到一个初始化过程的作用，如果没有错误发生，Leader将退出之后的通信中过程。

下面是Basic Paxos交互图：

![这里写图片描述][SouthEast]

下面是Fast Paxos的交互图：

![这里写图片描述][SouthEast 1]

**总结**

Fast Paxos基本是本着乐观锁的思路：如果存在冲突，则进行补偿。其中Leader起到一个初始化Progress和解决冲突的作用，如果Progress一直执行良好，则Leader将始终不参与一致性过程。因此Fast Paxos理论上只需要2个通信步骤，而Classic Paxos需要3个，但Fast Paxos在解决冲突时有至少需要1个通信步骤，在高并发的场景下，冲突的概率会非常高，冲突解决的成本也会很大。另外，Fast Paxos把Client深度引入算法中，致使其架构远没Classic Paxos那么清晰，也没Classic Paxos容易扩展。  
还有一点要注意的是，Fast Quorum的大小比Classic的要大，一般Fast Quorum至少需要4个节点(3E+1)，而Classic Paxos需要3个(2F+1)

[18123808-b860c61793e247919ee3787ead3430ef.png]: /images/20220603/bbf6028f4c0e4c32b92604be14430e3b.png
[SouthEast]: /images/20220603/f0c86ab080824b7595ec5e6e22431fcc.png
[SouthEast 1]: /images/20220603/c278e0530df54667808ed0ee327d6c75.png