网站上传后,wordpress4.7.5下载,阳江市人才最新招聘网,怎样为网站设计关键词提到分布式算法#xff0c;就不得不提 Paxos 算法#xff0c;在过去几十年里#xff0c;它基本上是分布式共识的代名词#xff0c;因为当前一批常用的共识算法都是基于它改进的。比如#xff0c;Fast Paxos 算法、Cheap Paxos、Raft 算法等。 由莱斯利兰伯特#xff08;L… 提到分布式算法就不得不提 Paxos 算法在过去几十年里它基本上是分布式共识的代名词因为当前一批常用的共识算法都是基于它改进的。比如Fast Paxos 算法、Cheap Paxos、Raft 算法等。 由莱斯利·兰伯特Leslie Lamport于1990年首次提出并在后续文章中进一步阐述。Paxos 算法旨在解决在一个可能发生网络分区、节点失效或其他异常情况的分布式环境中如何让所有参与决策的节点对某个值达成一致同意的问题。 兰伯特提出的Paxos总共包含两部分
一个是 Basic Paxos 算法描述的是多节点之间如何就某个值(提案Value)达成共识另一个是 Multi-Paxos 思想描述的是执行多个 Basic Paxos 实例就一系列值达成共识
Basic Paxos 先来看一个例子 假设有一个分布式集群由三个节点 A、B、C 组成提供只读 KV 存储服务创建只读变量的时候必须要先写入数据而且这个数据后续不能被修改。因此一个节点写入只读变量后就不能再修改了所以所有节点必须要先对只读变量达成共识然后所有节点在一次创建这个只读变量。 当有多个客户端(如客户端1、2)访问这个系统试图创建同一个只读变量(如X)客户端1试图创建值为3的X客户端2试图创建值为7的X这样要如何达成共识实现各节点上X值一直呢 为了帮助人们更好的理解 Basic Paxos 算法兰伯特在讲解时也使用了一些独有而且比较重要的概念提案、准备(Prepare)请求、接受(Accept)请求、角色等等其中最重要的就是角色。因为角色是对 Basic Paxos 中最核心的三个功能的抽象比如由接受者(Acceptor)对提议者的值进行投票并存储接受的值。 角色划分 在 Basic Paxos 中由提议者(Proposer)、接受者(Acceotor)、学习者(Learner)三种角色如图 提议者(Proposer)提议一个值用于投票表决。为了方便演示可以把客户端1和2看做是提议者。但在绝大多数场景中集群中收到客户端请求的节点才是提议者。这样做的好处是对业务代码没有侵入性也就是说我们不需要在代码中实现算法逻辑就可以像使用数据库一样访问后端数据。接受者(Acceptor)对每个提议的值进行投票并存储接受的值比如 A、B、C 三个节点。一般来说集群中的所有节点都在扮演接受者的角色参与共识协商并接受和存储数据。 这里需要强调一下前面不是说接收客户端请求的节点是提议者吗这里怎么又是接受者呢这是因为一个节点或进程可以身兼多个角色。想象一下一个 3 节点的集群1 个节点收到了请求那么该节点将作为提议者发起二阶段提交然后这个节点和另外 2 个节点一起作为接受者进行共识协商就像下图的样子
学习者(Leaner)被告知投票的结果接受达成的共识值存储保存不参与投票的过程。一般来说学习者是备份节点比如“Master-Slave”模型中的Slave被动的接受数据容灾备份。 达成共识过程 有这样一个场景假如你所在的公司有一个新项目需要开发业务比较复杂你的领导给组内每个成员下发了任务要求每人写一个项目方案最终开会讨论采用哪套方案为了区分每套方案每个方案都有一个标识称为提案编号来唯一标识。 与你的做法类似在 Basic Paxos 中兰伯特也使用提案代表一个提议。不过在提案中除了提案编号还包含了提议值。使用 [n, v] 表示一个提案n 为提案编号v 为提议值。 整个共识协商是分两个阶段进行的。假设客户端 1 的提案编号为 1客户端 2 的提案编号为5并假设节点 A、B 先收到来自客户端1的准备请求节点 C 先收到来自客户端 2 的准备请求。 准备Prepare阶段 先来看第一阶段首先客户端 1、2 作为提议者分别向所有接受者发送包含提案编号的准备请求 在准备请求时不需要准备提议的值的只需要携带提案编号就可以了这是容易误解的地方。接着当A、B收到提案编号为 1 的准备请求节点 C 收到提案编号为 2 的准备请求后将进行这样的处理 由于之前没有通过任何提案所以节点 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所以丢弃该准备请求不做响应。 接受Acceptor阶段 第二个阶段也就是接受阶段首先客户端 1、2 在收到大多数节点的准备响应之后会分别发送接受请求 当客户端 1 收到大多数的接受者节点A、B的准备响应之后根据响应中提案编号最大的提案值设置接受请求中的值。因为该值在来自节点 A、B 的准备响应中都为空所以就把自己的提议值 3 作为提案的值发送接受请求 [1, 3]。当客户端2收到大多数的接受者的准备响应后节点A、B、C根据响应中提案编号最大的提案值来设置接受请求中的值。因为该值来自节点 A、B、C 准备响应都为空所以就把自己的提议值7作为提案的值发送接受请求 [5, 7]。 当三个节点接受到两个客户端的接受请求时会进行这样的处理 当节点 A、B、C 接受到请求 [1, 3] 的时候由于提案的提案编号 1 小于三个节点承诺能通过的提案的最小提案编号 5所以提案 [1, 3] 将被拒绝。当节点 A、B、C 接受到请求 [5, 7] 的时候由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5所以就通过提案 [5, 7]也就是接受了值 7三个节点就 X 值为 7 达成共识。 如果集群中有学习者当接受者通过了一个提案时就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案那么它也通过该提案接受该提案的值。
Multi-Paxos算法 Basic Paxos 只能就单个值Value达成共识一旦遇到为一系列的值实现共识的时候它就不管用了。虽然兰伯特提到可以通过多次执行 Basic Paxos 实例比如每接收到一个值时就执行一次 Basic Paxos 算法实现一系列值的共识。但是读完论文后虽然每个英文单词都能读懂但还是不理解兰伯特提到的 Multi-Paxos为什么 Multi-Paxos 这么难理解呢 兰伯特并没有把 Multi-Paxos 讲清楚只是介绍了大概的思想缺少算法过程的细节和编程所必须的细节。这就导致了每个人实现的 Multi-Paxos 都不一样。不过从本质上看大家都是在兰伯特提到的 Multi-Paxos 思想上补充细节设计自己的 Multi-Paxos 算法然后实现它比如 Chubby 的 Multi-Paxos 实现、Raft 算法等。 所以这里补充一下兰伯特提出的 Multi-Paxos 是一种思想不是算法。而 Multi-Paxos 是一种统称它是指基于 Multi-Paxos 思想通过多个 basic-Paxos 实现一系列值的共识算法。这一点尤为重要。 到这里 Paxos 共识算法就介绍完了。
