分布式系统原理Day09-Paxos协议

「爱情、让人受尽委屈。」 2023-03-02 14:55 14阅读 0赞

### Paxos协议 ###

*  基本概念
 *  角色
 *  流程
 *   *   *  Proposer处理流程
         *  Acceptor流程
 *  Paxos协议示例

# 基本概念 #

*  **Paxos**协议是少数在工程实践中证实的强一致性,高可用的去中心化分布式协议
 *  **Paxos**协议的流程较为复杂,但是基本思想类似投票过程
 *  **Paxos**协议中有一组完全对等的参与节点 **:acceptor**
    
     *  这组节点各自就某一件事做出决议,如果某个决议获得了超过半数节点的同意则生效
 *  **Paxos**协议中只要有超过一半的节点正常,就可以工作,就能很好对抗宕机,网络分化等异常情况

# 角色 #

*  **Proposer:** 提案者
    
     *  **Proposer**可以有多个
     *  **Proposor**提出议案**value:**
        
         *  **value:** 指在工程实践中的任何操作:
            
             *  比如修改某个变量为某个值
             *  设置当前**primary**为某个节点等等
         *  Paxos协议中统一将这些操作抽象为**value**
     *  不同的**Proposer**可以提出不同甚至矛盾的**value:**
        
         *  比如某个**Proposer**提议“将变量X设置为1”
         *  另一个**Proposer**提议“将变量X设置为2”
     *  但是对于同一轮**Paxos**过程,最多只有一个**value**被批准
 *  **Acceptor:** 批准者
    
     *  **Acceptor**可以有多个
     *  **Proposer**提出的**value**必须获得超过半数的**Acceptor**批准后才能通过
     *  **Acceptor**之间完全对等独立
 *  **Learner:** 学习者
    
     *  **Learner**学习被批准的**value:**
        
         *  就是通过读取各个**Proposer**对**value**的选择结果
         *  如果某个**value**被超过半数**Acceptor**通过,那么**Learner**就学习到了这个**value**
 *  类似**Quorum**机制,某个**value**需要获得 N 2 + 1 \\frac\{N\}\{2\}+1 2N\+1的**Acceptor**批准,学习者**Learner**需要至少读取 N 2 + 1 \\frac\{N\}\{2\}+1 2N\+1个**Acceptor,** 至多读取**N**个**Acceptor**的结果后,才能学习到一个通过的**value**
 *  这三类角色只是逻辑上的划分,工程实践中一个节点可以同时充当这三类角色

# 流程 #

*  **Paxos**协议一轮一轮进行,每轮都有一个编号.每轮**Paxos**协议可能会批准一个**value.** 如果某一轮**Paxos**协议批准了某个**value,** 那么以后各轮**Paxos**协议只能批准这个**value**
 *  各轮协议流程组成一个**Paxos**协议实例: 一次**Paxos**协议实例只能批准一个**value.** 这也是Paxos协议强一致性的重要体现
 *  每轮**Paxos**协议分为两个阶段:
    
     *  **准备阶段**
     *  **批准阶段**
     *  这两个阶段**Proposer**和**Acceptor**有各自的处理流程

### Proposer处理流程 ###

*  向所有的**Acceptor**发送消息 **“Prepare(b)”,** 这里的**b**是**Paxos**的轮数,每轮递增
 *  如果收到任何一个**Acceptor**发送的消息 **“Reject(B)”,** 对于这个**Proposer**而言,本轮**Paxos**失败,将轮数**b**设置为**B+1**后重新进行上一个步骤
    
     *  在批准阶段,会根据收到的**Acceptor**的消息作出不同选择
 *  如果接收到的**Acceptor**的 **“Promise(b, v\_i)”** 消息达到 N 2 + 1 \\frac\{N\}\{2\}+1 2N\+1个 **. N**为**Acceptor**总数,除法取整 **,v-i**表示**Acceptor**最近一次在**i**轮批准过的**value**
    
     *  如果收到的 **“Promise(b, v)消息”** 中 **,v**都为空 **,Promise**会选择一个**value**作为**v,** 向所有**Acceptor**广播消息**Accept(b, v)**
     *  否则,在所有接收的 **“Promise(b, v\_i)消息”** 中,选择**i**最大的**value**作为**v,** 向所有**Acceptor**广播消息 **“Accept(b, v)”**
 *  如果接收到**Nack(B),** 将轮数**b**设置为**B+1**后重新进行第一步步骤

### Acceptor流程 ###

*  接收某个**Proposer**的消息**Prepare(b).** 参数**B**是该**Acceptor**收到的最大**Paxos**轮数编号 **,V**是**Acceptor**批准的**value,** 可以为空
    
     *  如果**b > B,** 回复**Promise(b, V\_B),** 设置**B = b.** 表示不再接受编号小于**b**提案
     *  否则,回复 **“Reject(B)消息”**
 *  接受**Accept(b, v):**
    
     *  如果**b < B,** 回复**Nack(B),** 表示**Proposer**有一个更大编号的提案被这个**Acceptor**接收了
     *  否则设置**V=v.** 表示这个**Acceptor**批准的**Value**是**v.** 广播 **“Accepted消息”**

# Paxos协议示例 #

*  有**5**个**Acceptor,1**个**Proposer,** 不存在任何网络,宕机异常
 *  着重考察各个**Acceptor**上变量**B**和变量**V**的变化以及**Proposer**上变量**B**的变化
 *  **初始状态:**  
    ![在这里插入图片描述][20200730120210661.png]
 *  **Proposer向所有Acceptor发送“Prepare(1)”. 所有Acceptor正确处理,并回复Promise(1, NULL) :**  
    ![在这里插入图片描述][20200730120449620.png]
 *  **Proposer收到5个Promise(1,NULL),满足多余半数的Promise的value为空,此时发送Accept(1, v1),其中v1是Proposer选择的value :**  
    ![在这里插入图片描述][20200730120759445.png]
 *  **此时,v1被超过半数的Acceptor批准,v1即是本次Paxos协议实例批准的value. 如果Learner学习value,学习到的只能是v1**
 *  **Paxos**协议的核心 **: 批准的value无法改变.** 这也是整个协议正确性的基础
    
     *  在同一个**Paxos**实例中, 批准的**value**是无法改变的,即使后续**Proposer**以更高的序号发起**Paxos**协议也无法改变**value**
 *  **Paxos**协议是被人为设计出来的,设计过程也是协议的推导过程:
    
     *  **Paxos**协议利用了**Quorum**机制,选择的 W = R = N 2 + 1 W=R=\\frac\{N\}\{2\}+1 W=R=2N\+1
     *  协议就是**Proposer**更新**Acceptor**的过程,一旦某个**Proposer**成功更新了超过半数的**Acceptor,** 那么就更新成功
     *  **Learner**按照**Quorum**机制去读取**Acceptor,** 一旦某个**value**在超过半数的**Proposer**上被成功读取,则说明这是一个被批准的**value**
     *  协议通过引入轮次,使得高轮次的提议抢占低轮次的提议来避免死锁
 *  **协议设计的关键点:**
    
     *  如何满足 **“在一次Paxos算法实例过程中只批准一个value”** 这一约束条件

[20200730120210661.png]: /images/20230208/d9e226a5157e42269331b7372dbd525b.png
[20200730120449620.png]: /images/20230208/ad8faedfca0b4d47acc6e1f8bb09d1c1.png
[20200730120759445.png]: /images/20230208/119d34b3d956444d978defeda15ec9a1.png