侧边栏壁纸
  • 累计撰写 793 篇文章
  • 累计创建 1 个标签
  • 累计收到 1 条评论
标签搜索

目 录CONTENT

文章目录

分布式一致性问题

Dettan
2021-04-10 / 0 评论 / 0 点赞 / 180 阅读 / 5,836 字
温馨提示:
本文最后更新于 2022-07-23,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。
应用场景
https://zhuanlan.zhihu.com/p/31727291

https://zhuanlan.zhihu.com/p/31780743

Paxos、Raft 分布式一致性算法应用场景一文讲述了分布式一致性问题与分布式一致性算法的典型应用场景。作为分布式一致性代名词的 Paxos 算法号称是最难理解的算法。本文试图用通俗易懂的语言讲述 Paxos 算法。一、Paxos 算法背景Paxos 算法是 Lamport 宗师提出的一种基于消息传递的分布式一致性算法,使其获得 2013 年图灵奖。Paxos 由 Lamport 于 1998 年在《The Part-Time Parliament》论文中首次公开,最初的描述使用希腊的一个小岛 Paxos 作为比喻,描述了 Paxos 小岛中通过决议的流程,并以此命名这个算法,但是这个描述理解起来比较有挑战性。后来在 2001 年,Lamport 觉得同行不能理解他的幽默感,于是重新发表了朴实的算法描述版本《Paxos Made Simple》。自 Paxos 问世以来就持续垄断了分布式一致性算法,Paxos 这个名词几乎等同于分布式一致性。Google 的很多大型分布式系统都采用了 Paxos 算法来解决分布式一致性问题,如 Chubby、Megastore 以及 Spanner 等。开源的 ZooKeeper,以及 MySQL 5.7 推出的用来取代传统的主从复制的 MySQL Group Replication 等纷纷采用 Paxos 算法解决分布式一致性问题。然而,Paxos 的最大特点就是难,不仅难以理解,更难以实现。二、Paxos 算法流程Paxos 算法解决的问题正是分布式一致性问题,即一个分布式系统中的各个进程如何就某个值(决议)达成一致。Paxos 算法运行在允许宕机故障的异步系统中,不要求可靠的消息传递,可容忍消息丢失、延迟、乱序以及重复。它利用大多数 (Majority) 机制保证了 2F+1 的容错能力,即 2F+1 个节点的系统最多允许 F 个节点同时出现故障。一个或多个提议进程 (Proposer) 可以发起提案 (Proposal),Paxos 算法使所有提案中的某一个提案,在所有进程中达成一致。系统中的多数派同时认可该提案,即达成了一致。最多只针对一个确定的提案达成一致。Paxos 将系统中的角色分为提议者 (Proposer),决策者 (Acceptor),和最终决策学习者 (Learner):Proposer: 提出提案 (Proposal)。Proposal 信息包括提案编号 (Proposal ID) 和提议的值 (Value)。Acceptor:参与决策,回应 Proposers 的提案。收到 Proposal 后可以接受提案,若 Proposal 获得多数 Acceptors 的接受,则称该 Proposal 被批准。Learner:不参与决策,从 Proposers/Acceptors 学习最新达成一致的提案(Value)。在多副本状态机中,每个副本同时具有 Proposer、Acceptor、Learner 三种角色。Paxos 算法中的角色Paxos 算法通过一个决议分为两个阶段(Learn 阶段之前决议已经形成):第一阶段:Prepare 阶段。Proposer 向 Acceptors 发出 Prepare 请求,Acceptors 针对收到的 Prepare 请求进行 Promise 承诺。第二阶段:Accept 阶段。Proposer 收到多数 Acceptors 承诺的 Promise 后,向 Acceptors 发出 Propose 请求,Acceptors 针对收到的 Propose 请求进行 Accept 处理。第三阶段:Learn 阶段。Proposer 在收到多数 Acceptors 的 Accept 之后,标志着本次 Accept 成功,决议形成,将形成的决议发送给所有 Learners。Paxos 算法流程Paxos 算法流程中的每条消息描述如下:Prepare: Proposer 生成全局唯一且递增的 Proposal ID (可使用时间戳加 Server ID),向所有 Acceptors 发送 Prepare 请求,这里无需携带提案内容,只携带 Proposal ID 即可。Promise: Acceptors 收到 Prepare 请求后,做出 “两个承诺,一个应答”。两个承诺:1. 不再接受 Proposal ID 小于等于(注意:这里是 <= )当前请求的 Prepare 请求。2. 不再接受 Proposal ID 小于(注意:这里是 < )当前请求的 Propose 请求。一个应答:不违背以前作出的承诺下,回复已经 Accept 过的提案中 Proposal ID 最大的那个提案的 Value 和 Proposal ID,没有则返回空值。Propose: Proposer 收到多数 Acceptors 的 Promise 应答后,从应答中选择 Proposal ID 最大的提案的 Value,作为本次要发起的提案。如果所有应答的提案 Value 均为空值,则可以自己随意决定提案 Value。然后携带当前 Proposal ID,向所有 Acceptors 发送 Propose 请求。Accept: Acceptor 收到 Propose 请求后,在不违背自己之前作出的承诺下,接受并持久化当前 Proposal ID 和提案 Value。Learn: Proposer 收到多数 Acceptors 的 Accept 后,决议形成,将形成的决议发送给所有 Learners。Paxos 算法伪代码描述如下:Paxos 算法伪代码获取一个 Proposal ID n,为了保证 Proposal ID 唯一,可采用时间戳 + Server ID 生成;Proposer 向所有 Acceptors 广播 Prepare(n) 请求;Acceptor 比较 n 和 minProposal,如果 n>minProposal,minProposal=n,并且将 acceptedProposal 和 acceptedValue 返回;Proposer 接收到过半数回复后,如果发现有 acceptedValue 返回,将所有回复中 acceptedProposal 最大的 acceptedValue 作为本次提案的 value,否则可以任意决定本次提案的 value;到这里可以进入第二阶段,广播 Accept (n,value) 到所有节点;Acceptor 比较 n 和 minProposal,如果 n>=minProposal,则 acceptedProposal=minProposal=n,acceptedValue=value,本地持久化后,返回;否则,返回 minProposal。提议者接收到过半数请求后,如果发现有返回值 result >n,表示有更新的提议,跳转到 1;否则 value 达成一致。下面举几个例子,实例 1 如下图:Paxos 算法实例 1图中 P 代表 Prepare 阶段,A 代表 Accept 阶段。3.1 代表 Proposal ID 为 3.1,其中 3 为时间戳,1 为 Server ID。X 和 Y 代表提议 Value。实例 1 中 P 3.1 达成多数派,其 Value(X) 被 Accept,然后 P 4.5 学习到 Value(X),并 Accept。Paxos 算法实例 2实例 2 中 P 3.1 没有被多数派 Accept(只有 S3 Accept),但是被 P 4.5 学习到,P 4.5 将自己的 Value 由 Y 替换为 X,Accept(X)。Paxos 算法实例 3实例 3 中 P 3.1 没有被多数派 Accept(只有 S1 Accept),同时也没有被 P 4.5 学习到。由于 P 4.5 Propose 的所有应答,均未返回 Value,则 P 4.5 可以 Accept 自己的 Value (Y)。后续 P 3.1 的 Accept (X) 会失败,已经 Accept 的 S1,会被覆盖。Paxos 算法可能形成活锁而永远不会结束,如下图实例所示:Paxos 算法形成活锁回顾两个承诺之一,Acceptor 不再应答 Proposal ID 小于等于当前请求的 Prepare 请求。意味着需要应答 Proposal ID 大于当前请求的 Prepare 请求。两个 Proposers 交替 Prepare 成功,而 Accept 失败,形成活锁(Livelock)。三、Multi-Paxos 算法原始的 Paxos 算法(Basic Paxos)只能对一个值形成决议,决议的形成至少需要两次网络来回,在高并发情况下可能需要更多的网络来回,极端情况下甚至可能形成活锁。如果想连续确定多个值,Basic Paxos 搞不定了。因此 Basic Paxos 几乎只是用来做理论研究,并不直接应用在实际工程中。实际应用中几乎都需要连续确定多个值,而且希望能有更高的效率。Multi-Paxos 正是为解决此问题而提出。Multi-Paxos 基于 Basic Paxos 做了两点改进:针对每一个要确定的值,运行一次 Paxos 算法实例(Instance),形成决议。每一个 Paxos 实例使用唯一的 Instance ID 标识。在所有 Proposers 中选举一个 Leader,由 Leader 唯一地提交 Proposal 给 Acceptors 进行表决。这样没有 Proposer 竞争,解决了活锁问题。在系统中仅有一个 Leader 进行 Value 提交的情况下,Prepare 阶段就可以跳过,从而将两阶段变为一阶段,提高效率。Multi-Paxos 流程Multi-Paxos 首先需要选举 Leader,Leader 的确定也是一次决议的形成,所以可执行一次 Basic Paxos 实例来选举出一个 Leader。选出 Leader 之后只能由 Leader 提交 Proposal,在 Leader 宕机之后服务临时不可用,需要重新选举 Leader 继续服务。在系统中仅有一个 Leader 进行 Proposal 提交的情况下,Prepare 阶段可以跳过。Multi-Paxos 通过改变 Prepare 阶段的作用范围至后面 Leader 提交的所有实例,从而使得 Leader 的连续提交只需要执行一次 Prepare 阶段,后续只需要执行 Accept 阶段,将两阶段变为一阶段,提高了效率。为了区分连续提交的多个实例,每个实例使用一个 Instance ID 标识,Instance ID 由 Leader 本地递增生成即可。Multi-Paxos 允许有多个自认为是 Leader 的节点并发提交 Proposal 而不影响其安全性,这样的场景即退化为 Basic Paxos。Chubby 和 Boxwood 均使用 Multi-Paxos。ZooKeeper 使用的 Zab 也是 Multi-Paxos 的变形。附 Paxos 算法推导过程Paxos 算法的设计过程就是从正确性开始的,对于分布式一致性问题,很多进程提出(Propose)不同的值,共识算法保证最终只有其中一个值被选定,Safety 表述如下:只有被提出(Propose)的值才可能被最终选定(Chosen)。只有一个值会被选定(Chosen)。进程只会获知到已经确认被选定(Chosen)的值。Paxos 以这几条约束作为出发点进行设计,只要算法最终满足这几点,正确性就不需要证明了。Paxos 算法中共分为三种参与者:Proposer、Acceptor 以及 Learner,通常实现中每个进程都同时扮演这三个角色。Proposers 向 Acceptors 提出 Proposal,为了保证最多只有一个值被选定(Chosen),Proposal 必须被超过一半的 Acceptors 所接受(Accept),且每个 Acceptor 只能接受一个值。为了保证正常运行(必须有值被接受),所以 Paxos 算法中:P1:Acceptor 必须接受(Accept)它所收到的第一个 Proposal。先来先服务,合情合理。但这样产生一个问题,如果多个 Proposers 同时提出 Proposal,很可能会导致无法达成一致,因为没有 Propopal 被超过一半 Acceptors 的接受,因此,Acceptor 必须能够接受多个 Proposal,不同的 Proposal 由不同的编号进行区分,当某个 Proposal 被超过一半的 Acceptors 接受后,这个 Proposal 就被选定了。既然允许 Acceptors 接受多个 Proposal 就有可能出现多个不同值都被最终选定的情况,这违背了 Safety 要求,为了保证 Safety 要求,Paxos 进一步提出:P2:如果值为 v 的 Proposal 被选定(Chosen),则任何被选定(Chosen)的具有更高编号的 Proposal 值也一定为 v。只要算法同时满足 P1 和 P2,就保证了 Safety。P2 是一个比较宽泛的约定,完全没有算法细节,我们对其进一步延伸:P2a:如果值为 v 的 Proposal 被选定(Chosen),则对所有的 Acceptors,它们接受(Accept)的任何具有更高编号的 Proposal 值也一定为 v。如果满足 P2a 则一定满足 P2,显然,因为只有首先被接受才有可能被最终选定。但是 P2a 依然难以实现,因为 acceptor 很有可能并不知道之前被选定的 Proposal(恰好不在接受它的多数派中),因此进一步延伸:P2b:如果值为 v 的 Proposal 被选定(Chosen),则对所有的 Proposer,它们提出的的任何具有更高编号的 Proposal 值也一定为 v。更进一步的:P2c:为了提出值为 v 且编号为 n 的 Proposal,必须存在一个包含超过一半 Acceptors 的集合 S,满足 (1) 没有任何 S 中的 Acceptors 曾经接受(Accept)过编号比 n 小的 Proposal,或者(2) v 和 S 中的 Acceptors 所接受过(Accept) 的编号最大且小于 n 的 Proposal 值一致。满足 P2c 即满足 P2b 即满足 P2a 即满足 P2。至此 Paxos 提出了 Proposer 的执行流程,以满足 P2c:Proposer 选择一个新的编号 n,向超过一半的 Acceptors 发送请求消息,Acceptor 回复: (a)承诺不会接受编号比 n 小的 proposal,以及 (b) 它所接受过的编号比 n 小的最大 Proposal(如果有)。该请求称为 Prepare 请求。如果 Proposer 收到超过一半 Acceptors 的回复,它就可以提出 Proposal,Proposal 的值为收到回复中编号最大的 Proposal 的值,如果没有这样的值,则可以自由提出任何值。向收到回复的 Acceptors 发送 Accept 请求,请求对方接受提出的 Proposal。仔细品味 Proposer 的执行流程,其完全吻合 P2c 中的要求,但你可能也发现了,当多个 Proposer 同时运行时,有可能出现没有任何 Proposal 可以成功被接受的情况(编号递增的交替完成第一步),这就是 Paxos 算法的 Liveness 问题,或者叫 “活锁”,论文中建议通过对 Proposers 引入选主算法选出 Distinguished Proposer 来全权负责提出 Proposal 来解决这个问题,但是即使在出现多个 Proposers 同时提出 Proposal 的情况时,Paxos 算法也可以保证 Safety。接下来看看 Acceptors 的执行过程,和我们对 P2 做的事情一样,我们对 P1 进行延伸:P1a:Acceptor 可以接受(Accept)编号为 n 的 Proposal 当且仅当它没有回复过一个具有更大编号的 Prepare 消息。易见,P1a 包含了 P1,对于 Acceptors:当收到 Prepare 请求时,如果其编号 n 大于之前所收到的 Prepare 消息,则回复。当收到 Accept 请求时,仅当它没有回复过一个具有更大编号的 Prepare 消息,接受该 Proposal 并回复。以上涵盖了满足 P1a 和 P2b 的一套完整一致性算法。注:文中部分图片来自互联网。写下你的评论... 不再接受 Proposal ID 小于等于(注意:这里是 <= )当前请求的 Prepare 请求按照时间戳 + Server ID 生成的 Proposal ID,这里相等的情况不会出现吧?如果每次都获取到递增的时间戳,确实不会出现,但如果本地时间作了调整,或者两次获取时间戳的间隔小于时钟精度,则可能出现相等的情况实例 2 中 3.1A 不会被 accept,因为此时做出了 promise4 了对的,Acceptor 节点不再会对 3.1 做出任何应答了。A3.1x 还是会 accept,因为前两个结点并没有收到 p4.5 的 prepare你好祥光,multi-paxos 的 leader 选举需要使用 basic-paxos,但是 basic-paxos 存在活锁问题,那么工程中对此有没有什么办法呢?你好,活锁问题与 Raft 的 leader 选举的选票分裂问题类似,工程上可采用 Raft 的 leader 选举的随机化方法,超时后随机等待一段时间后再发起选举嗯,确实,随机等待一段时间,这本身就是解决死锁,活锁的一种方法。谢谢哈!想问下如果 2 个 Proposer,3 个 acceptor,Proposer1 申请 acceptor1 和 acceptor2 的 prepare 且成功了之后, 因为第一次所以返回 null 值, 所以可以提交自己的值假如是 v1, 然后提交给 acceptor1 成功了, 因为 acceptor1 没有接受收到其他 prepare 所以接成功了, 但是此时 Proposer2 提交了自己的 v2, 给 acc2 和 acc3, 并且成功了, 确定了 v2, 那么就导致了 acc1 确认的是 v1,acc2 和 acc3 确认的是 v2对的,这样形成的决议的值是 v2,因为 v2 已经被大多数 acceptor 确认博主,那 acceptor1 中的 v1 不是和 acceptor2、acceptor3 中的值不一样了吗,acceptor1 通过什么机制把自己的值,替换为 v2?我有一个问题,如果 proposal ID 不是严格递增的,会有问题么?我觉得大致递增应该就能解决问题了吧。proposal ID 不严格递增当然没问题,只是较小的 proposal ID 会没有提议的机会如果给每台机器手动分配一个固定的 id,每次都用这个 id 其实也能达到这种效果吧。相当于 id 最大的胜出,除非 id 最大的挂了,第二大的胜出。mutli paxos 下请问多个 proposer 自认为 leader 情况下,系统如何退化为 basic paxos?哦,我懂了,原来是 Acceptor 返回给 proposer 的值没有超过 majority,那么 proposer 判断为没有被完全接受这个值,这时候就会出现失败,proposer 执行重试或者返回 client 失败。在多个 proposer 自认为 leader 的情况下,一定需要人工介入才能够解决问题吗?虽然在 Basic Paxos 选主的情况下,不可能出现多个 leader 的情况。如果出现多个 leader 证明系统有人入侵或者 bug,这也就是 multi paxos 能够解决拜占庭问题的原因?拜占庭问题不在 paxos 解决问题的范畴,paxos 默认信息传递是可靠的,basic paxos 的 prepare 也不是为了解决活锁,活锁的解决方案博主在其他评论下面有回复。multi paxos 中,proposer 提交的内容其实就是 basic paxos 中的 propose 阶段,因为只有一个 leader 的情况下直接就可以 propose 了。如果在 basic paxos 中,直接执行 propose 阶段,就会导致冲突很大,prepare 阶段就是为了减少冲突,尽力避免活锁的情况。感觉 basic paxos 中的 prepare 阶段其实可去掉,如果只是为了选一个 value,那么谁先被大多数接受,谁提的 value 就被接受则可以我提出 basic paxos 可以去除 prepare 阶段的一个支撑是,multi paxos 可以解决多个 proposer 自认为 leader 的情况请问一下为什么论文中提到需要全局唯一的 proposalId,prepare 阶段不是可以拒绝 <=minProposalId 的 proposal 吗?假如 n 个相同 proposalId 的 proposal 同时发起预提议(prepare),可能出现没有任何一个 proposal 获得 majority 的回复的情况,每个 proposal 都会误以为已经出现了更大的 proposalId,于是每个 proposal 不会尝试进入下一阶段(accept),这是不是 deadlock 了(大雾为啥你这个和何登成做的 ppt 是一样的内容,是他抄的你的么?我和何都是参考的国外一个大学老师的 PPT不是挑刺哦,时间戳 + Server ID 不能生成全局唯一且递增的 ID不要求严格递增两个承诺中有错误。 不知道作者是参考了什么写出来的,建议给出参考文档原闻其详之前迷糊了是因为:prepare 请求和 Propose 请求,这两个词。后来又看了一下原论文,原 PPT 和你的文章,只是你这里称呼与其他中不同。个人觉得还是以论文中称呼为准比较好,分别是:prepare 请求和 accept 请求。(建议全文中其他地方这些术语也应该以论文为准。)有个疑问,为什么可以说 Paxos 算法是强一致性的?看「Paxos 实例算法 3」,不同的服务器还是有不同的值。因为从系统外部的访问者来看,Paxos 可以做到强一致性,尽管从系统内部看 Paxos 并不保证强一致性从提出议案开始,到所有存活节点都学习到议案。系统是否处于不可用状态propose 和 proposal 有什么区别?一个名词一个动词推荐看这篇https://www.cnblogs.com/linbingdong/p/6253479.html描述得非常清晰。本文可能是作者翻译过来的,一些细节确实讲得不够精准;我是看了半天不得要领,找到了上面那篇。Prepare: Proposer 生成全局唯一且递增的 Proposal ID (可使用时间戳加 Server ID),向所有 Acceptors 发送 Prepare 请求,这里无需携带提案内容,只携带 Proposal ID 即可。文章里面说 Prepare 请求不带内容,那么承诺的 value 是怎么来的呢prepare 阶段有两个作用,一是尝试获取提议权,二是学习已经提议过的 value,都不需要携带自己的 value> 否则可以任意决定本次提案的 value任意这个词非常具有误导性,因为这个词等于随机,现实中不可能是随机的,而是外界(用户)的若干请求(明确集合)中选定的一个值。是从明确的候选列表中,采用明确的规则选取出的特定的值。不可能任意选取,也不可能用随机数据来代替,也不可能针对同样条件选取多次的结果不一样。所以,不存在所谓的 “任意”。不考虑应用背景,单纯在 paxos 算法看来,就是任意的
0

评论区