前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Paxos协议学习小结

Paxos协议学习小结

作者头像
用户1263954
发布2018-01-30 11:39:48
1.2K0
发布2018-01-30 11:39:48
举报
文章被收录于专栏:IT技术精选文摘

一直对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 采用 后者认同前者的思路运行。 容错要求: (1) 半数以内的Acceptor失效、任意数量的Proposer 失效,都能运行。 (2) 一旦value值被确定,即使 半数以内的Acceptor失效,此值也可以被获取,并不再修改。
    • 在肯定 旧ProposalID 还没有生成确定的value (Acceptor 提交成功一个value)时,新ProposalID 会提交自己的value,不会冲突。
    • 一旦 旧ProposalID 生成了确定的value,新ProposalID 肯定可以获取到此值,并且认同此值。
  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的数据分布设计(二)

出处:https://baozh.github.io/2016-03/paxos-learning/

版权申明:内容来源网络,版权归原创者所有。除非无法确认,我们都会标明作者及出处,如有侵权烦请告知,我们会立即删除并表示歉意。谢谢。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2017-06-29,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 IT技术精选文摘 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Basic Paxos 协议
    • 算法(提案的提出与批准)主要分为两个阶段:
      • Paxos 协议 的几个约束:
        • 常见的疑问、及异常处理:
          • Zookeeper做的调整及优化:
          • Multi Paxos 协议
          • 解决单点问题的几种思路
          • 参考:
          领券
          问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档