dtcms 源码 网络服务器 EasyCVR url UIkit vue开发文档 nginx教程视频 jquery通过class获取元素 pr序列设置哪个好 plsql连接mysql mysql临时表 python迭代器 python课程 python中len函数 python正则表达式例子 python的random模块 python零基础 javaqueue javamysql java变量 java访问数据库 java学习教程 java在线课程 javapattern java的泛型 java多线程处理 java运行 心理学与生活txt xp画图工具 摩尔斯电码翻译器 路由器辐射大吗 win10计算器下载 主板芯片组天梯图 ad下载 卡巴斯基离线升级包 按键精灵脚本教程 系统工具箱 联发科mt6750 小米9截图 linux格式化硬盘
当前位置: 首页 > 学习教程  > 编程语言

分布式协议与算法实战——Paxos(笔记)

2020/7/24 11:26:32 文章标签: 测试文章如有侵权请发送至邮箱809451989@qq.com投诉后文章立即删除

在过去几十年里,Paxos算法基本上是分布式共识的代名词,因为当前最常用的一批共识算法都是基于它改进的。比如,Fast Paxos算法、Cheap Paxos 算法、Raft 算法、ZAB 协议等等。

兰伯特提出的 Paxos 算法包含 2 个部分:

  • Basic Paxos 算法:描述的是多节点之间如何就某个值(提案 Value)达成共识;
  • Multi-Paxos 思想:描述的是执行多个 Basic Paxos 实例,就一系列值达成共识。

Basic Paxos算法

三种角色

  • 提议者(Proposer):提议一个值,用于投票表决。在绝大多数场景中,集群中收到客户端请求的节点,才是提议者。这样做的好处是,对业务代码没有入侵性,也就是说,我们不需要在业务代码中实现算法逻辑,就可以像使用数据库一样访问后端的数据。
  • 接受者(Acceptor):每个提议的值进行投票,并存储接受的值。 一般来说,集群中的所有节点都在扮演接受者的角色,参与共识协商,并接受和存储数据。
  • 学习者(Learner):被告知投票的结果,接受达成共识的值存储保存不参与投票的过程。一般来说,学习者是数据备份节点,比如“Master-Slave”模型中的 Slave,被动地接受数据,容灾备份。
    在这里插入图片描述
    注:一个节点(或进程)可以身兼多个角色。

角色的本质

  • 提议者代表的是接入协调功能,收到客户端请求后,发起二阶段提交,进行共识协商;
  • 接受者代表投票协商存储数据,对提议的值进行投票,并接受达成共识的值,存储保存;
  • 学习者代表存储数据,不参与共识协商,只接受达成共识的值,存储保存。

达成共识的过程

在 Basic Paxos 中,兰伯特也使用提案代表一个提议。在提案中包括提案编号提议值。为了方便演示,使用[n, v]表示一个提案,其中 n 为提案编号,v 为提议值。

准备(Prepare)阶段

(1)客户端 1、2 作为提议者,分别向所有接受者发送包含提案编号的。在准备请求中是不需要指定提议的值,只需要携带提案编号。
准备请求:
在这里插入图片描述
(2)当节点 A、B 收到提案编号为 1 的准备请求,节点 C 收到提案编号为 5 的准备请求后,将进行这样的处理:
在这里插入图片描述
由于之前没有通过任何提案,所以节点 A、B 将返回一个 “尚无提案”的响应。也就是说节点 A 和 B 在告诉提议者,之前没有通过任何提案,并承诺以后不再响应提案编号小于等于 1 的准备请求,不会通过编号小于 1 的提案;节点 C 也将返回一个 “尚无提案”的响应,并承诺以后不再响应提案编号小于等于 5 的准备请求,不会通过编号小于 5 的提案。
(3)当节点 A、B 收到提案编号为 5 的准备请求,和节点 C 收到提案编号为 1 的准备请求的时候,将进行这样的处理过程:
在这里插入图片描述
当节点 A、B 收到提案编号为 5 的准备请求的时候,因为提案编号 5 大于它们之前响应的准备请求的提案编号 1,两个节点都没有通过任何提案,所以它将返回一个 “尚无提案”的响应,并承诺以后不再响应提案编号小于等于 5 的准备请求,不会通过编号小于 5 的提案。

当节点 C 收到提案编号为 1 的准备请求的时候,由于提案编号 1 小于之前响应的准备请求的提案编号 5,所以丢弃该准备请求,不做响应

接受(Accept)阶段

首先客户端 1、2 在收到大多数节点的准备响应之后,会分别发送接受请求:
在这里插入图片描述
当客户端 1 收到大多数的接受者(节点 A、B)的准备响应后,根据响应中提案编号最大的提案的值,设置接受请求中的值。因为该值在来自节点 A、B 的准备响应中都为空,所以就把自己的提议值 3 作为提案的值,发送接受请求[1, 3]。

当客户端 2 收到大多数的接受者的准备响应后(节点 A、B 和节点 C),根据响应中提案编号最大的提案的值,来设置接受请求中的值。因为该值在来自节点 A、B、C 的准备响应中都为空(,所以就把自己的提议值 7 作为提案的值,发送接受请求[5, 7]。

三个节点收到 2 个客户端的接受请求时,会进行这样的处理:
在这里插入图片描述
当节点 A、B、C 收到接受请求[1, 3]的时候,由于提案的提案编号 1 小于三个节点承诺能通过的提案的最小提案编号 5,所以提案[1, 3]将被拒绝。

当节点 A、B、C 收到接受请求[5, 7]的时候,由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5,所以就通过提案[5, 7],也就是接受了值 7,三个节点就 X 值为 7 达成了共识。

如果集群中有学习者,当接受者通过了一个提案时,就通知给所有的学习者。当学习者发现大多数接受者通过了某个提案,那么它也通过该提案,接受该提案的值。

总结

  • Basic Paxos 是通过二阶段提交的方式来达成共识的。
  • 除了共识,Basic Paxos 还实现了容错,在少于一半的节点出现故障时,集群也能工作。它不像分布式事务算法那样,必须要所有节点都同意后才提交操作,因为“所有节点都同意”这个原则,在出现节点故障的时候会导致整个集群不可用。也就是说,“大多数节点都同意”的原则,赋予了 Basic Paxos 容错的能力,让它能够容忍少于一半的节点的故障。
  • 提案编号的大小代表着优先级,根据提案编号的大小,接受者保证三个承诺,具体来说:如果准备请求的提案编号,小于等于接受者已经响应的准备请求的提案编号,那么接受者将承诺不响应这个准备请求;如果接受请求中的提案的提案编号,小于接受者已经响应的准备请求的提案编号,那么接受者将承诺不通过这个提案;如果接受者之前有通过提案,那么接受者将承诺,会在准备请求的响应中,包含已经通过的最大编号的提案信息。

本文链接: http://www.dtmao.cc/news_show_50420.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?