Zenghui Bao's World

about life, programming, misc thoughts.

Paxos协议 学习小结

一直对Paxos协议比较感兴趣,之前对这个算法 有耳闻 但只是了解皮毛,最近在学Zookeeper,趁着这股新鲜劲,就花时间研究了下Zookeeper的选举算法实现,再重新学习了Paxos算法,这篇文章算是我的学习总结吧。

Basic Paxos 协议

Paxos 协议是一个解决分布式系统中 多个节点之间就某个值(提案value)达成一致(决议)的通信协议,也就是说,每个节点 提出的提案 会 对 同一个 提案内容 达成一致(知悉 且 要commit成功)。下面简称提案IDProposalID提案内容value

算法(提案的提出与批准)主要分为两个阶段:

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

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

  • 如果是,则:
    (1) 在本地持久化 ProposalID,可记为Max_ProposalID
    (2) 回复请求,并带上 已Accept的提案中 ProposalID 最大的 value(若此时还没有已Accept的提案,则返回value为空)。
    (3) 做出承诺:不会Accept 任何 小于 Max_ProposalID的提案。
  • 如果否:不回复。

第二阶段 Accept
P2a:Proposer 发送 Accept
经过一段时间后,Proposer 收集到一些 Prepare 回复,有下列几种情况:
(1) 回复数量 > 一半的Acceptor数量,且 所有的回复的 value 都为空,则 Porposer发出accept请求,并带上 自己指定的value
(2) 回复数量 > 一半的Acceptor数量,且 有的回复 value 不为空,则 Porposer发出accept请求,并带上 回复中 ProposalID最大 的value(作为自己的提案内容)。
(3) 回复数量 <= 一半的Acceptor数量,则 尝试 更新生成更大的 ProposalID,再转 P1a 执行。

P2b:Acceptor 应答 Accept
Accpetor 收到 Accpet请求 后,判断:
(1) 收到的ProposalID >= Max_ProposalID (一般情况下是 等于),则 回复 提交成功,并 持久化 ProposalID 和value。
(2) 收到的ProposalID < Max_ProposalID,则 不回复 或者 回复 提交失败

P2c: Proposer 统计投票
经过一段时间后,Proposer 收集到一些 Accept 回复提交成功,有几种情况:
(1) 回复数量 > 一半的Acceptor数量,则表示 提交value成功。此时,可以发一个广播给所有Proposer、Learner,通知它们 已commit的value。
(2) 回复数量 <= 一半的Acceptor数量,则 尝试 更新生成更大的 ProposalID,再转 P1a 执行。
(3) 收到 一条提交失败的回复,则 尝试 更新生成更大的 ProposalID,再转 P1a 执行。

最后,经过多轮投票后,达到的结果是:
(1) 所有Proposer都 提交提案成功了,且提交的value是同一个value。
(2) 过半数的 Acceptor都提交成功了,且提交的是 同一个value。

Paxos 协议 的几个约束:

  • P1: 一个Acceptor必须接受(accept)第一次收到的提案;
  • P2a: 一旦一个具有value v的提案被批准(chosen),那么之后任何Acceptor 再次接受(accept)的提案必须具有value v;
  • P2b: 一旦一个具有value v的提案被批准(chosen),那么以后任何 Proposer 提出的提案必须具有value v;
  • P2c: 如果一个编号为n的提案具有value v,那么存在一个多数派,要么他们中所有人都没有接受(accept)编号小于n的任何提案,要么他们已经接受(accpet)的所有编号小于n的提案中编号最大的那个提案具有value v;

常见的疑问、及异常处理:

  1. Paxos算法的核心思想是什么?
    (1) 引入了 多个Acceptor,避免 单个Acceptor成为单点。
    Proposer用 更大ProposalID 来抢占 临时的访问权,避免 其中一个 Proposer崩溃宕机 导致 死锁。
    (2) 保证一个ProposalID,只有一个Proposer能进行到第二阶段运行,Proposer按照ProposalID递增的顺序依次运行。
    (3) 新ProposalID 的 proposer 采用 后者认同前者的思路运行。
    • 在肯定 旧ProposalID 还没有生成确定的value (Acceptor 提交成功一个value)时,新ProposalID 会提交自己的value,不会冲突。
    • 一旦 旧ProposalID 生成了确定的value,新ProposalID 肯定可以获取到此值,并且认同此值。

    容错要求:
    (1) 半数以内的Acceptor失效、任意数量的Proposer 失效,都能运行。
    (2) 一旦value值被确定,即使 半数以内的Acceptor失效,此值也可以被获取,并不再修改。

  2. 工程实践中 ProposalID 怎么定?
    在《Paxos made simple》中提到,推荐Proposer从不相交的数据集合中进行选择,例如系统有5个Proposer,则可为每一个Proposer分配一个标识j(0~4),则每一个proposer每次提出决议的编号可以为5*i + j(i可以用来表示提出议案的次数)。
    在实践过程中,可以用 时间戳 + 提出提案的次数 + 机器 IP/机器ID 来保证唯一性和递增性。

  3. 如何保证 更大的ProposalID的Proposer 不会破坏 已经达成的确定性取值value?
    在P2a阶段中,Proposer会以 所有回复中ProposalID最大 的value 作为自己的提案内容。
    其中,prepare阶段的目的有两个: 1) 检查是否有被批准的值,如果有,就改用批准的值。2) 如果之前的提案还没有被批准,则阻塞掉他们以便不让他们和我们发生竞争,当然最终由ProposalID 的大小决定。

  4. Paxos协议的活锁问题
    新轮次的抢占会使旧轮次停止运行,如果每一轮在第二阶段执行成功之前 都 被 新一轮抢占,则导致活锁。怎么解决?
    这个问题在实际应用会发生地比较少,一般可通过 随机改变 ProposalID的增长幅度 或者 增加Proposer发送新一轮提案的间隔 来解决。

  5. Paxos 运行过程中,半数以内的Acceptor失效,都能运行。为什么?
    (1) 如果 半数以内的Acceptor失效时 还没确定最终的value,此时,所有Proposer会竞争 提案的权限,最终会有一个提案会 成功提交。之后,会有半过数的Acceptor以这个value提交成功。
    (2) 如果 半数以内的Acceptor失效时 已确定最终的value,此时,所有Proposer提交前 必须以 最终的value 提交,因为,一个Proposer要拿到过半数的accept响应,必须同一个已提交的Acceptor存在交集,故会在P2a阶段中会继续沿用该value。

  6. 若两个Proposer以不同的ProposalID,在进行到P2a阶段,收到的prepare回复的value值都为空,则两个proposer都以自己的值作为value(提案内容),向Acceptor提交请求,最后,两个proposer都会认为自己提交成功了吗?
    不会,因为Acceptor会根据ProposalID,批准执行最大的ProposalID的value,另一个会回复 执行失败。当proposer收到执行失败的回复时,就知道:当前 具有更大的ProposalID的提案提交成功了。

  7. 由于大ProposalID 可以 抢占 小ProposalID 的提交权限,如果 此时 Acceptor还没有一个确定性取值,有一个具有最大ProposalID的proposer进行到P2a阶段了,但这时 这个proposer挂了,会造成一种死锁状态(小ProposalID的会提交失败,但是 具有最大ProposalID的proposer却不能提交accept请求),如何解决这种死锁状态?
    不会产生这种死锁状态,acceptor回复提交失败后,proposer再生成 更大的ProposalID,下一轮可以用自己value提交成功。

Zookeeper做的调整及优化:

  1. 刚挂掉的leader 优先 争抢 leadership。
    在运行的过程中,如果leader节点崩溃,此时,所有slave节点需要sleep几秒后,才能争抢leadership,而刚挂掉的节点重启后,可以马上争抢leadership。
    这么做,是为了解决 leader节点由于负载过重 导致 假死,优先选择 原来的leader节点 可以减少 同步的数据量。

  2. ProposalID以 Zxid + 机器ID 来确定,其中 Zxid表示 本节点 最近Commit的事务ID。
    Zookeeper会优化 选择 拥有最新commit记录(Zxid最大)的机器作为leader,如果Zxid相等,则选择机器ID更大的那个。

  3. Zookeeper中的节点兼具Acceptor,Proposer,而且没有明确区分Prepare阶段和Accept阶段。
    提案的ProposalID和value,用的同一个结构体Vote,每轮投票直接发Vote,其它节点收到后,如果比自己的提案大,则将 自己的提案ProposalID和value 更新为 收到的Vote的值,且广播向其它节点发送新的提案。
    经过多轮投票后,会使 每个节点的提案 趋于最终的那个值。

Multi Paxos 协议

可以看出,一个Basic Paxos Instance运行完,要经过 每个Proposer的prepare阶段、accept阶段,还需要在过半数的节点上commit成功,流程太多,导致性能不高。一般在实践过程中用Multi Paxos协议。

Multi Paxos协议省去了Basic Paxos的prepare阶段,直接由一个leader节点提交提案,并通知其它Follower节点提交提案。在Leader租约内,只有Leader可以提出提案。如果leader节点崩溃宕机、或者租约到期后没有续约,则由 其它Follower 使用 Basix Paxos协议 竞争leadship。

在使用Multi Paxos 协议做多节点的复制时,有一些细节需要注意。详细可以参考这篇文章这篇文章

解决单点问题的几种思路

最近在项目中遇到一个需求,要解决一个中心节点(下称DC节点)的单点问题,我思考了下,解决方式有三种:

  1. vip + keepalived

    布署两台机器(一主一备),这两台用keepalive检测心跳,对外提供vip。每台机器都设置一个crontab脚本,每5分钟检查一下Dc进程在不在,如果不在,则拉起来。
    外部用vip访问这个节点。如果一台机器的Dc进程崩溃了,则crontab脚本会拉起来。如果整台机器都挂了,则vip会切换到另一台机器的ip上。

  2. 用Zookeeper选举一个leader来对外服务,当leader节点挂掉后,再选举另一个节点。外部通过Zookeeper来实时 获取Dc的真实ip。
    这种方法有个缺点:要布署一个zookeeper集群、且需要zookeeper先运行、其它节点后运行。

  3. 在Dc节点中内置Basic Paxos协议 来实现选举,对外提供接口获取Dc leader节点的ip


参考:

  1. 《Paxos made simple》论文

  2. 图解分布式一致性协议Paxos

  3. 图解zookeeper FastLeader选举算法

  4. 《从Paxos到Zookeeper–分布式一致性原理与实践》 第2、3、4、7.6章节

  5. 一步一步理解Paxos算法
    这篇文章讲得很浅显易懂,我就是通过这篇文章开悟的!

  6. [Paxos三部曲之一] 使用Basic-Paxos协议的日志同步与恢复
    讲解应用Basic-Paxos解决 多节点 复制日志的一致性问题。

  7. [Paxos三部曲之二] 使用Multi-Paxos协议的日志同步与恢复

  8. 架构师需要了解的Paxos原理、历程及实战

  9. 视频 paxos和分布式系统
    百度的高级工程师对Paxos协议的解决,很不错!

  10. Paxos在大型系统中常见的应用场景

  11. 多IDC的数据分布设计(一)

  12. 多IDC的数据分布设计(二)