11-06 12:06 阅读 250

关注

Paxos协议和流程详解！细说分布式系统中的去中心化的分布式协议

基本概念

• Paxos协议是少数在工程实践中证实的强一致性,高可用的去中心化分布式协议

• Paxos协议的流程较为复杂,但是基本思想类似投票过程

• Paxos协议中有一组完全对等的参与节点 :acceptor

• 这组节点各自就某一件事做出决议,如果某个决议获得了超过半数节点的同意则生效

• Paxos协议中只要有超过一半的节点正常,就可以工作,就能很好对抗宕机,网络分化等异常情况

角色

• Proposer: 提案者

• 比如某个Proposer提议“将变量X设置为1”

• 另一个Proposer提议“将变量X设置为2”

• value: 指在工程实践中的任何操作:

• Paxos协议中统一将这些操作抽象为value

• 比如修改某个变量为某个值

• 设置当前primary为某个节点等等

• Proposer可以有多个

• Proposor提出议案value:

• 不同的Proposer可以提出不同甚至矛盾的value:

• 但是对于同一轮Paxos过程,最多只有一个value被批准

• Acceptor: 批准者

• Acceptor可以有多个

• Proposer提出的value必须获得超过半数的Acceptor批准后才能通过

• Acceptor之间完全对等独立

• Learner: 学习者

• 就是通过读取各个Proposer对value的选择结果

• 如果某个value被超过半数Acceptor通过,那么Learner就学习到了这个value

• Learner学习被批准的value:

• 类似Quorum机制,某个value需要获得$\frac{N}{2}+1$的Acceptor批准,学习者Learner需要至少读取$\frac{N}{2}+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)” 消息达到$\frac{N}{2}+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的变化

• 初始状态:

• Proposer向所有Acceptor发送“Prepare(1)”. 所有Acceptor正确处理,并回复Promise(1, NULL) :

• Proposer收到5个Promise(1,NULL),满足多余半数的Promise的value为空,此时发送Accept(1, v1),其中v1是Proposer选择的value :

• 此时,v1被超过半数的Acceptor批准,v1即是本次Paxos协议实例批准的value. 如果Learner学习value,学习到的只能是v1

• Paxos协议的核心 : 批准的value无法改变. 这也是整个协议正确性的基础

• 在同一个Paxos实例中, 批准的value是无法改变的,即使后续Proposer以更高的序号发起Paxos协议也无法改变value

• Paxos协议是被人为设计出来的,设计过程也是协议的推导过程:

• Paxos协议利用了Quorum机制,选择的$W=R=\frac{N}{2}+1$

• 协议就是Proposer更新Acceptor的过程,一旦某个Proposer成功更新了超过半数的Acceptor, 那么就更新成功

• Learner按照Quorum机制去读取Acceptor, 一旦某个value在超过半数的Proposer上被成功读取,则说明这是一个被批准的value

• 协议通过引入轮次,使得高轮次的提议抢占低轮次的提议来避免死锁

• 协议设计的关键点:

• 如何满足 “在一次Paxos算法实例过程中只批准一个value” 这一约束条件

作者：攻城狮Chova
链接：https://juejin.cn/post/7027098708097368100