理解 Paxos 算法

June 14th, 2020 by JasonLe's Tech Leave a reply »

Paxos 的节点角色

在 Paxos 协议中,有三类节点角色,分别是 Proposer、Acceptor 和 Learner,另外还有一个 Client,作为产生议题者。

上述三类角色只是逻辑上的划分,在工作实践中,一个节点可以同时充当这三类角色。

Proposer 提案者

Proposer 可以有多个,在流程开始时,Proposer 提出议案,也就是value,所谓 value,在工程中可以是任何操作,比如“修改某个变量的值为某个新值”,Paxos 协议中统一将这些操作抽象为 value。

不同的 Proposer 可以提出不同的甚至矛盾的 value,比如某个 Proposer 提议“将变量 X 设置为 1”,另一个 Proposer 提议“将变量 X 设置为 2”,但对同一轮 Paxos 过程,最多只有一个 value 被批准。

Acceptor 批准者

在集群中,Acceptor 有 N 个,Acceptor 之间完全对等独立,Proposer 提出的 value 必须获得超过半数(N/2+1)的 Acceptor 批准后才能通过。

Learner 学习者

Learner 不参与选举,而是学习被批准的 value,在Paxos中,Learner主要参与相关的状态机同步流程。

这里Leaner的流程就参考了Quorum 议会机制,某个 value 需要获得 W=N/2 + 1 的 Acceptor 批准,Learner 需要至少读取 N/2+1 个 Accpetor,最多读取 N 个 Acceptor 的结果后,才能学习到一个通过的 value。

Client 产生议题者

Client 角色,作为产生议题者,实际不参与选举过程,比如发起修改请求的来源等。

Proposer 与 Acceptor 之间的交互

Paxos 中, Proposer 和 Acceptor 是算法核心角色,Paxos 描述的就是在一个由多个 Proposer 和多个 Acceptor 构成的系统中,如何让多个 Acceptor 针对 Proposer 提出的多种提案达成一致的过程,而 Learner 只是“学习”最终被批准的提案。

Proposer 与 Acceptor 之间的交互主要有 4 类消息通信,如下图:

这 4 类消息对应于 Paxos 算法的两个阶段 4 个过程,下面在分析选举过程时会讲到。

Paxos 选举过程

选举过程可以分为两个部分,准备阶段和选举阶段,可以查看下面的时序图:

Phase 1 准备阶段

Proposer 生成全局唯一且递增的 ProposalID,向 Paxos 集群的所有机器发送 Prepare 请求,这里不携带 value,只携带 N 即 ProposalID。

Acceptor 收到 Prepare 请求后,判断收到的 ProposalID 是否比之前已响应的所有提案的 N 大,如果是,则:

在本地持久化 N,可记为 Max_N;

回复请求,并带上已经 Accept 的提案中 N 最大的 value,如果此时还没有已经 Accept 的提案,则返回 value 为空;

做出承诺,不会 Accept 任何小于 Max_N 的提案。

如果否,则不回复或者回复 Error。

Phase 2 选举阶段

为了方便描述,我们把 Phase 2 选举阶段继续拆分为 P2a、P2b 和 P2c。

P2a:Proposer 发送 Accept

经过一段时间后,Proposer 收集到一些 Prepare 回复,有下列几种情况:

若回复数量 > 一半的 Acceptor 数量,且所有回复的 value 都为空时,则 Porposer 发出 accept 请求,并带上自己指定的 value。

若回复数量 > 一半的 Acceptor 数量,且有的回复 value 不为空时,则 Porposer 发出 accept 请求,并带上回复中 ProposalID 最大的 value,作为自己的提案内容。

若回复数量 <= 一半的 Acceptor 数量时,则尝试更新生成更大的 ProposalID,再转到准备阶段执行。

P2b:Acceptor 应答 Accept

Accpetor 收到 Accpet 请求 后,判断:

若收到的 N >= Max_N(一般情况下是等于),则回复提交成功,并持久化 N 和 value;

若收到的 N < Max_N,则不回复或者回复提交失败。

P2c: Proposer 统计投票

经过一段时间后,Proposer 会收集到一些 Accept 回复提交成功的情况,比如:

当回复数量 > 一半的 Acceptor 数量时,则表示提交 value 成功,此时可以发一个广播给所有的 Proposer、Learner,通知它们已 commit 的 value;

当回复数量 <= 一半的 Acceptor 数量时,则尝试更新生成更大的 ProposalID,转到准备阶段执行。

当收到一条提交失败的回复时,则尝试更新生成更大的 ProposalID,也会转到准备阶段执行。

Paxos 常见的问题

关于Paxos协议,有几个常见的问题,简单介绍下。

1.如果半数以内的 Acceptor 失效,如何正常运行?

在Paxos流程中,如果出现半数以内的 Acceptor 失效,可以分为两种情况:

第一种,如果半数以内的 Acceptor 失效时还没确定最终的 value,此时所有的 Proposer 会重新竞争提案,最终有一个提案会成功提交。

第二种,如果半数以内的 Acceptor 失效时已确定最终的 value,此时所有的 Proposer 提交前必须以最终的 value 提交,也就是Value实际已经生效,此值可以被获取,并不再修改。

2. Acceptor需要接受更大的N,也就是ProposalID有什么意义?

这种机制可以防止其中一个Proposer崩溃宕机产生阻塞问题,允许其他Proposer用更大ProposalID来抢占临时的访问权。

3. 如何产生唯一的编号,也就是 ProposalID?

在《Paxos made simple》论文中提到,唯一编号是让所有的 Proposer 都从不相交的数据集合中进行选择,需要保证在不同Proposer之间不重复,比如系统有 5 个 Proposer,则可为每一个 Proposer 分配一个标识 j(0~4),那么每一个 Proposer 每次提出决议的编号可以为 5*i + j,i 可以用来表示提出议案的次数。

 

The PartTime Parliament

Paxos Made Simple

fast-paxos