台州网站建设公司哪家好,wordpress 3.2,网站公众平台建设方案,网站建设 完成目录 Paxos算法Basic Paxos算法三种角色如何达成共识#xff08;协商过程#xff09;小结#xff1a; Multi-Paxos算法关于 Multi-Paxos 的思考领导者优化Basic PaxosChubby 的 Multi-Paxos 实现小结 参考 Paxos算法 Paxos论文 Paxos Made Simple 、author#xff1a;Lesli… 目录 Paxos算法Basic Paxos算法三种角色如何达成共识协商过程小结 Multi-Paxos算法关于 Multi-Paxos 的思考领导者优化Basic PaxosChubby 的 Multi-Paxos 实现小结 参考 Paxos算法 Paxos论文 Paxos Made Simple 、authorLeslie Lamport兰伯特 Paxos算法是一种共识算法一些常用的共识算法都是基于它改进的如Fast Paxos算法、Cheep Paxos算法、Raft算法等。Paxos算法包含2个部分
Basic Paxos算法描述的是多节点之间如何就某个值提案 value达成共识。Multi-Paxos算法描述的是执行多个Basic Paxos实例就一系列值达成共识。
Basic Paxos算法
实现一个分布式集群这个集群由多个组成。现有多个客户端客户端1、客户端2访问这个集群试图创建同一个只读变量如X客户端1试图创建值为3的X客户端2试图创建值为7的X。那如何达成共识实现各节点上X值的一致呢使用Paxos算法。
Paxos算法中有一些独有而且比较重要的概念提案、准备请求、接受请求、角色等。其中角色是对Basix Paxos中最核心三个功能的抽象。
三种角色
在Basic Paxos中有提议者Proposer、接受者Acceptor、学习者Learner三种角色。
提议者提议一个值用于投票表决。在绝大多数场景下集群中收到客户端的请求的节点是提议者而不是客户端作为提议者这样做的好处是对业务代码没有入侵性不需要在业务代码中实现算法逻辑。接受者对每个提议的值进行投票、并存储接受的值。一般来说集群中所有节点都在扮演接受者的角色参与共识协商并接受和存储数据。学习者被告知投票的结果接受达成共识的值存储保存不参与投票的过程。一般来说学习者是数据备份的节点被动地接受数据容灾备份。 一个节点可以身兼多种角色。例如一个3节点的集群1个节点收到了客户端的请求那么该节点将作为提议者发起二阶段提交然后这个节点和另外两个节点一起作为接受者进行共识协商。 这三种角色本质上代表的是三种功能
提议者代表的是接入和协调功能收到客户端请求后发起二阶段提交进行共识协商。接受者代表投票协商和存储数据对提议的值进行投票并接受达成共识的值存储保存。学习者代表存储数据不参与共识协商只接受达成共识的值存储保存。
如何达成共识协商过程
在Basic Paxos中使用提案代表一个提议。在提案中除了提案编号还包含了提议值。如[n,v]表示一个提案其中n为提案编号v为提议值。
假设客户端1的提案编号为1客户端2的提案编号为5节点A、B先收到来自客户端1的准备请求节点C先收到来自客户端2的准备请求。 提议者 一般由收到客户端请求的节点担任这里为了便于理解将客户端作为了提议者。你可以这样理解每个客户端对应一个节点其所对应的节点即担任提议者又担任接受者。所以下述的客户端1、2可以看成节点A、C。 准备Prepare阶段
第一个阶段是准备阶段。首先客户端1、2作为提议者分别向所有接受者发送包含提案编号的准备请求。 在准备请求的时候不需要指定提议的值只需要携带提案编号。 随后节点A、B收到提案编号为1的准备请求节点C收到提案编号为5的准备请求进行以下处理。
由于之前没有通过任何提案所以节点 A、B 将返回一个 “尚无提案”的响应。也就是说节点 A 和 B 在告诉提议者我之前没有通过任何提案呢并承诺以后不再响应提案编号小于等于 1 的准备请求不会通过编号小于 1 的提案。节点 C 也是如此它将返回一个 “尚无提案”的响应并承诺以后不再响应提案编号小于等于 5 的准备请求不会通过编号小于 5 的提案。
随后当节点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 的准备响应中都为空也就是图 5 和图 6 中的“尚无提案”所以就把自己的提议值 7 作为提案的值发送接受请求[5, 7]。
当节点 A、B、C 收到接受请求[1, 3]的时候由于提案的提案编号 1 小于三个节点承诺能通过的提案的最小提案编号 5所以提案[1, 3]将被拒绝。
当节点 A、B、C 收到接受请求[5, 7]的时候由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5所以就通过提案[5, 7]也就是接受了值 7三个节点就 X 值为 7 达成了共识。 如果节点的准备响应中包含了提案信息而不是“尚无提案”那么提议者会将响应的提案编号最大的提案所对应的值作为接受请求中的值而不是将自己的提议值作为提案值。这样就保证了大多数节点就某个值达成共识后这个值就不会改变了哪怕有新的提案这个值也不会改变了。 如果集群中有学习者当接受者通过一个提案时就通知给所有学习者。当学习者发现大多数的接受者都通过了提案那么它也通过该提案接受该提案的值。
除了共识之外Basic Paxos还实现了容错这个容错能力源自**“大多数”**的约定大多数接受者准备响应。可以理解为当少于一半的节点出现故障的时候共识协商仍能正常工作。 如果节点 A、B 已经通过了提案[5, 7]节点 C 未通过任何提案那么当客户端 3 提案编号为 9 时通过 Basic Paxos 执行“SET X 6”最终三个节点上 X 值是多少呢 准备阶段 当节点A、B收到提案编号为9的准备请求的时候因为提案编号9大于之前响应的准备请求的提案编号5并且这两个节点已经通过了之前的提案[5,7]接受者A、B会在准备请求的响应中包含已经通过的最大编号的提案信息[5,7]并承诺以后不再响应提案编号小于9不会通过编号小于9的提案由于节点C之前没有通过任何提案所以节点C将返回一个“尚无提案”的响应并承诺以后不再响应议案编号小于等于9的准备请求不会通过编号小于9的提案。 接受阶段 当客户端3收到大多数的接受者的准备请求后节点A、B和C根据响应中提案编号最大的提案的值来设置请求的值即来自A、B节点的准备响应的提案[5,7]。因此就把A、B响应值7作为提案的值发送接受请求[9,7]。当节点A、B、C收到接受请求[9,7]后由于提案的提案编号不小于三个节点承诺的能通过的提案的最小提案编号9所以就通过提案[9,7]。三个节点就达成了共识。最后的值为7。 大多是值就某个节点达成共识了值就不变了。哪怕有新的提案这个值也能保证不再变了。
小结
Basic Paxos 是通过二阶段提交的方式来达成共识的。二阶段提交是达成共识的常用方式。除了共识Basic Paxos 还实现了容错在少于一半的节点出现故障时集群也能工作。它不像分布式事务算法那样必须要所有节点都同意后才提交操作因为“所有节点都同意”这个原则在出现节点故障的时候会导致整个集群不可用。本质上而言提案编号的大小代表着优先级你可以这么理解根据提案编号的大小接受者保证三个承诺具体来说 如果准备请求的提案编号小于等于接受者已经响应的准备请求的提案编号那么接受者将承诺不响应这个准备请求如果接受请求中的提案的提案编号小于接受者已经响应的准备请求的提案编号那么接受者将承诺不通过这个提案如果接受者之前有通过提案那么接受者将承诺会在准备请求的响应中包含已经通过的最大编号的提案信息。
Multi-Paxos算法
Basic Paxos 只能就单个值Value达成共识一旦遇到为一系列的值实现共识的时候它就不管用了。可以通过多次执行 Basic Paxos 实例比如每接收到一个值时就执行一次 Basic Paxos 算法实现一系列值的共识。
Multi-Paxos 是一种思想不是算法。而 Multi-Paxos 算法是一个统称它是指基于 Multi-Paxos 思想通过多个 Basic Paxos 实例实现一系列值的共识的算法比如 Chubby 的 Multi-Paxos 实现、Raft 算法等。
关于 Multi-Paxos 的思考
Basic Paxos 是通过二阶段提交来达成共识的。在第一阶段也就是准备阶段接收到大多数准备响应的提议者才能发起接受请求进入第二阶段也就是接受阶段
如果我们直接通过多次执行 Basic Paxos 实例来实现一系列值的共识就会存在这样几个问题
如果多个提议者同时提交提案可能出现因为提案编号冲突在准备阶段没有提议者接收到大多数准备响应协商失败需要重新协商。2 轮 RPC 通讯准备阶段和接受阶段往返消息多、耗性能、延迟大。
可以通过引入领导者和优化 Basic Paxos 执行来解决上面的两个问题。
领导者
领导者节点作为唯一提议者这样就不存在多个提议者同时提交提案的情况也就不存在提案冲突的情况了。
在论文中并没有说如何选举领导者需要我们在实现 Multi-Paxos 算法的时候自己实现如在 Chubby 中领导者节是通过执行 Basic Paxos 算法进行投票选举产生的。
优化Basic Paxos
可以采用**“当领导者处于稳定状态时省掉准备阶段直接进入接受阶段”**这个优化机制优化 Basic Paxos 执行。也就是说领导者节点上序列中的命令是最新的不再需要通过准备请求来发现之前被大多数节点通过的提案领导者可以独立指定提案中的值。这时领导者在提交命令时可以省掉准备阶段直接进入到接受阶段 和重复执行 Basic Paxos 相比Multi-Paxos 引入领导者节点之后因为只有领导者节点一个提议者只有它说了算所以就不存在提案冲突。另外当主节点处于稳定状态时就省掉准备阶段直接进入接受阶段所以在很大程度上减少了往返的消息数提升了性能降低了延迟。 感觉Multi-Paxos 的实现需要执行多轮的 Basic Paxos但Multi-Paxos 对每一轮 Basic Paxos进行了上述优化。 Chubby 的 Multi-Paxos 实现
通过引入主节点实现了论文中提到的领导者Leader节点的特性。也就是说主节点作为唯一提议者这样就不存在多个提议者同时提交提案的情况也就不存在提案冲突的情况了。主节点是通过执行 Basic Paxos 算法进行投票选举产生的并且在运行过程中主节点会通过不断续租的方式来延长租期Lease。Chubby 中实现了论文提到的“当领导者处于稳定状态时省掉准备阶段直接进入接受阶段”这个优化机制。在 Chubby 中实现了成员变更Group membership以此保证节点变更的时候集群的平稳运行。在 Chubby 中为了实现了强一致性读操作也只能在主节点上执行。 也就是说只要数据写入成功之后所有的客户端读到的数据都是一致的。所有的读请求和写请求都由主节点来处理 读写请求都在主节点上了主节点的压力就很大了呀 小结
兰伯特提到的 Multi-Paxos 是一种思想不是算法而且还缺少算法过程的细节和编程所必须的细节比如如何选举领导者等这也就导致了每个人实现的 Multi-Paxos 都不一样。而 Multi-Paxos 算法是一个统称它是指基于 Multi-Paxos 思想通过多个 Basic Paxos 实例实现一系列数据的共识的算法比如 Chubby 的 Multi-Paxos 实现、Raft 算法等。Chubby 实现了主节点也就是兰伯特提到的领导者也实现了兰伯特提到的 “当领导者处于稳定状态时省掉准备阶段直接进入接受阶段” 这个优化机制省掉 Basic Paxos 的准备阶段提升了数据的提交效率但是所有写请求都在主节点处理限制了集群处理写请求的并发能力约等于单机。在 Chubby 的 Multi-Paxos 实现中也约定了“大多数原则”也就是说只要大多数节点正常运行时集群就能正常工作所以 Chubby 能容错n - 1/2 个节点的故障。本质上而言“当领导者处于稳定状态时省掉准备阶段直接进入接受阶段”这个优化机制是通过减少非必须的协商步骤来提升性能的。这种方法非常常用也很有效。比如Google 设计的 QUIC 协议是通过减少 TCP、TLS 的协商步骤优化 HTTPS 性能。
参考
分布式协议与算法实战 学习笔记
