05 | Paxos算法（一）：如何在多个节点间确定某变量的值？

Feb 21, 2020

05 | Paxos算法（一）：如何在多个节点间确定某变量的值？-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

05 | Paxos算法（一）：如何在多个节点间确定某变量的值？

2020-02-21 韩健来自北京

《分布式协议与算法实战》

课程介绍



讲述：于航

时长13:07大小10.51M



你好，我是韩健。
提到分布式算法，就不得不提 Paxos 算法，在过去几十年里，它基本上是分布式共识的代名词，因为当前最常用的一批共识算法都是基于它改进的。比如，Fast Paxos 算法、Cheap Paxos 算法、Raft 算法等等。而很多同学都会在准确和系统理解 Paxos 算法上踩坑，比如，只知道它可以用来达成共识，但不知道它是如何达成共识的。
这其实侧面说明了 Paxos 算法有一定的难度，可分布式算法本身就很复杂，Paxos 算法自然也不会例外，当然了，除了这一点，还跟兰伯特有关。
兰伯特提出的 Paxos 算法包含 2 个部分：
一个是 Basic Paxos 算法，描述的是多节点之间如何就某个值（提案 Value）达成共识；
另一个是 Multi-Paxos 思想，描述的是执行多个 Basic Paxos 实例，就一系列值达成共识。
可因为兰伯特提到的 Multi-Paxos 思想，缺少代码实现的必要细节（比如怎么选举领导者），所以在理解上比较难。
为了让你理解 Paxos 算法，接下来我会用 2 节课的时间，分别以 Basic Paxos 和 Multi-Paxos 为核心，带你了解 Basic Paxos 如何达成共识，以及针对 Basic Paxos 的局限性 Multi-Paxos 又是如何改进的。今天咱们先来聊聊 Basic Paxos。
在我看来，Basic Paxos 是 Multi-Paxos 思想的核心，说白了，Multi-Paxos 就是多执行几次 Basic Paxos。所以掌握它之后，你能更好地理解后几讲基于 Multi-Paxos 思想的共识算法（比如 Raft 算法），还能掌握分布式共识算法的最核心内容，当现在的算法不能满足业务需求，进行权衡折中，设计自己的算法。
来看一道思考题。
假设我们要实现一个分布式集群，这个集群是由节点 A、B、C 组成，提供只读 KV 存储服务。你应该知道，创建只读变量的时候，必须要对它进行赋值，而且这个值后续没办法修改。因此一个节点创建只读变量后就不能再修改它了，所以所有节点必须要先对只读变量的值达成共识，然后所有节点再一起创建这个只读变量。
那么，当有多个客户端（比如客户端 1、2）访问这个系统，试图创建同一个只读变量（比如 X），客户端 1 试图创建值为 3 的 X，客户端 2 试图创建值为 7 的 X，这样要如何达成共识，实现各节点上 X 值的一致呢？带着这个问题，我们进入今天的学习。
图1
在一些经典的算法中，你会看到一些既形象又独有的概念（比如二阶段提交协议中的协调者），Basic Paxos 算法也不例外。为了帮助人们更好地理解 Basic Paxos 算法，兰伯特在讲解时，也使用了一些独有而且比较重要的概念，提案、准备（Prepare）请求、接受（Accept）请求、角色等等，其中最重要的就是“角色”。因为角色是对 Basic Paxos 中最核心的三个功能的抽象，比如，由接受者（Acceptor）对提议的值进行投票，并存储接受的值。
你需要了解的三种角色在 Basic Paxos 中，有提议者（Proposer）、接受者（Acceptor）、学习者（Learner）三种角色，他们之间的关系如下：
图2
看着是不是有些复杂，其实并不难理解：
提议者（Proposer）：提议一个值，用于投票表决。为了方便演示，你可以把图 1 中的客户端 1 和 2 看作是提议者。但在绝大多数场景中，集群中收到客户端请求的节点，才是提议者（图 1 这个架构，是为了方便演示算法原理）。这样做的好处是，对业务代码没有入侵性，也就是说，我们不需要在业务代码中实现算法逻辑，就可以像使用数据库一样访问后端的数据。
接受者（Acceptor）：对每个提议的值进行投票，并存储接受的值，比如 A、B、C 三个节点。 一般来说，集群中的所有节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。
讲到这儿，你可能会有疑惑：前面不是说接收客户端请求的节点是提议者吗？这里怎么又是接受者呢？这是因为一个节点（或进程）可以身兼多个角色。想象一下，一个 3 节点的集群，1 个节点收到了请求，那么该节点将作为提议者发起二阶段提交，然后这个节点和另外 2 个节点一起作为接受者进行共识协商，就像下图的样子：
图3
学习者（Learner）：被告知投票的结果，接受达成共识的值，存储保存，不参与投票的过程。一般来说，学习者是数据备份节点，比如“Master-Slave”模型中的 Slave，被动地接受数据，容灾备份。
其实，这三种角色，在本质上代表的是三种功能：
提议者代表的是接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商；
接受者代表投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存；
学习者代表存储数据，不参与共识协商，只接受达成共识的值，存储保存。
因为一个完整的算法过程是由这三种角色对应的功能组成的，所以理解这三种角色，是你理解 Basic Paxos 如何就提议的值达成共识的基础。那么接下来，咱们看看如何使用 Basic Paxos 达成共识，解决开篇提到的那道思考题。
如何达成共识？想象这样一个场景，现在疫情这么严重，每个村的路都封得差不多了，就你的村委会不作为，迟迟没有什么防疫的措施。你决定给村委会提交个提案，提一些防疫的建议，除了建议之外，为了和其他村民的提案做区分，你的提案还得包含一个提案编号，来起到唯一标识的作用。
与你的做法类似，在 Basic Paxos 中，兰伯特也使用提案代表一个提议。不过在提案中，除了提案编号，还包含了提议值。为了方便演示，我使用[n, v]表示一个提案，其中 n 为提案编号，v 为提议值。
我想强调一下，整个共识协商是分 2 个阶段进行的（也就是我在 03 讲提到的二阶段提交）。那么具体要如何协商呢？
我们假设客户端 1 的提案编号为 1，客户端 2 的提案编号为 5，并假设节点 A、B 先收到来自客户端 1 的准备请求，节点 C 先收到来自客户端 2 的准备请求。
准备（Prepare）阶段先来看第一个阶段，首先客户端 1、2 作为提议者，分别向所有接受者发送包含提案编号的准备请求：
图4
你要注意，在准备请求中是不需要指定提议的值的，只需要携带提案编号就可以了，这是很多同学容易产生误解的地方。
接着，当节点 A、B 收到提案编号为 1 的准备请求，节点 C 收到提案编号为 5 的准备请求后，将进行这样的处理：
图5
由于之前没有通过任何提案，所以节点 A、B 将返回一个 “尚无提案”的响应。也就是说节点 A 和 B 在告诉提议者，我之前没有通过任何提案呢，并承诺以后不再响应提案编号小于等于 1 的准备请求，不会通过编号小于 1 的提案。
节点 C 也是如此，它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。
另外，当节点 A、B 收到提案编号为 5 的准备请求，和节点 C 收到提案编号为 1 的准备请求的时候，将进行这样的处理过程：
图6
当节点 A、B 收到提案编号为 5 的准备请求的时候，因为提案编号 5 大于它们之前响应的准备请求的提案编号 1，而且两个节点都没有通过任何提案，所以它将返回一个 “尚无提案”的响应，并承诺以后不再响应提案编号小于等于 5 的准备请求，不会通过编号小于 5 的提案。
当节点 C 收到提案编号为 1 的准备请求的时候，由于提案编号 1 小于它之前响应的准备请求的提案编号 5，所以丢弃该准备请求，不做响应。
接受（Accept）阶段第二个阶段也就是接受阶段，首先客户端 1、2 在收到大多数节点的准备响应之后，会分别发送接受请求：
图7
当客户端 1 收到大多数的接受者（节点 A、B）的准备响应后，根据响应中提案编号最大的提案的值，设置接受请求中的值。因为该值在来自节点 A、B 的准备响应中都为空（也就是图 5 中的“尚无提案”），所以就把自己的提议值 3 作为提案的值，发送接受请求[1, 3]。
当客户端 2 收到大多数的接受者的准备响应后（节点 A、B 和节点 C），根据响应中提案编号最大的提案的值，来设置接受请求中的值。因为该值在来自节点 A、B、C 的准备响应中都为空（也就是图 5 和图 6 中的“尚无提案”），所以就把自己的提议值 7 作为提案的值，发送接受请求[5, 7]。
当三个节点收到 2 个客户端的接受请求时，会进行这样的处理：
图8
当节点 A、B、C 收到接受请求[1, 3]的时候，由于提案的提案编号 1 小于三个节点承诺能通过的提案的最小提案编号 5，所以提案[1, 3]将被拒绝。
当节点 A、B、C 收到接受请求[5, 7]的时候，由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5，所以就通过提案[5, 7]，也就是接受了值 7，三个节点就 X 值为 7 达成了共识。
讲到这儿我想补充一下，如果集群中有学习者，当接受者通过了一个提案时，就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案，那么它也通过该提案，接受该提案的值。
通过上面的演示过程，你可以看到，最终各节点就 X 的值达成了共识。那么在这里我还想强调一下，Basic Paxos 的容错能力，源自“大多数”的约定，你可以这么理解：当少于一半的节点出现故障的时候，共识协商仍然在正常工作。
内容小结本节课我主要带你了解了 Basic Paxos 的原理和一些特点，我希望你明确这样几个重点。
你可以看到，Basic Paxos 是通过二阶段提交的方式来达成共识的。二阶段提交是达成共识的常用方式，如果你需要设计新的共识算法的时候，也可以考虑这个方式。
除了共识，Basic Paxos 还实现了容错，在少于一半的节点出现故障时，集群也能工作。它不像分布式事务算法那样，必须要所有节点都同意后才提交操作，因为“所有节点都同意”这个原则，在出现节点故障的时候会导致整个集群不可用。也就是说，“大多数节点都同意”的原则，赋予了 Basic Paxos 容错的能力，让它能够容忍少于一半的节点的故障。
本质上而言，提案编号的大小代表着优先级，你可以这么理解，根据提案编号的大小，接受者保证三个承诺，具体来说：如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求；如果接受请求中的提案的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息。
课堂思考在示例中，如果节点 A、B 已经通过了提案[5, 7]，节点 C 未通过任何提案，那么当客户端 3 提案编号为 9 时，通过 Basic Paxos 执行“SET X = 6”，最终三个节点上 X 值是多少呢？为什么呢？欢迎在留言区分享你的看法，与我一同讨论。
最后，感谢你的阅读，如果这篇文章让你有所收获，也欢迎你将它分享给更多的朋友。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

赞 30

提建议

04 | BASE理论：CAP的碱，追求可用性

06 | Paxos算法（二）：Multi-Paxos不是一个算法，而是统称

 写留言

精选留言(107)

小晏子
2020-02-21
如果节点 A、B 已经通过了提案[5, 7]，节点 C 未通过任何提案，那么当客户端 3 提案编号为 9 ，通过 Basic Paxos 执行“SET X = 6”, 最终节点值应该是[9,7], 过程如下： 1. 在准备阶段，节点C收到客户端3的准备请求[9,6], 因为节点C未收到任何提案，所以返回“尚无提案”的相应。这时如果节点C收到了之前客户端的准备请求[5, 7], 根据提案编号5小于它之前响应的准备请求的提案编号9，会丢弃该准备请求。 2. 客户端3发送准备请求[9,6]给节点A，B，这时因为节点A，B已经通过了提案[5,7], 根据“如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息”，节点A，B会返回[5,7]给客户端3. 3. 客户端3发送会接受请求[9,7]给节点A，B，C（注意这里使用的是准备阶段的最大提议编号和已经被通过的值），因为此时请求编号9不小于之前的请求编号，所以所有节点接受该请求[9,7]. 4, 所有学习者会接受该提案，学习该值。
展开
作者回复: 加一颗星:)
共 34 条评论
111
EidLeung
2020-02-23
“作者回复: 大多数节点就某个值，达成共识后，值就不再变了，哪怕有新的提案，这个值，也能保证不再变了。”这个最后的值肯定是7，至于编号嘛，取最大的🤪。
作者回复: 加一颗星:)
共 5 条评论
55
LiuHu
2020-06-03
推荐一个 youtube 上的视频讲解 https://www.youtube.com/watch?v=UUQ8xYWR4do 。推荐理由是，视频中通过类似于时序图的方式讲解了如下3个场景：如何处理首个提案、如何解决冲突提案并达成共识、达成共识后如何处理新提案。并且在讲解这3个场景时，也详细描述了 Proposer、Acceptor、Learner 在集群中会产生哪些消息，如何处理这些消息。总之看了之后，对 Basic Paxos 算法的理解更加通透了。
展开
共 5 条评论
43
Jialin
2020-02-21
如果节点 A、B 已经通过了提案[5, 7]，节点 C 未通过任何提案，那么当客户端 3 提案编号为 9 时，通过 Basic Paxos 执行“SET X = 6”时准备阶段：当节点 A、B 收到提案编号为 9 的准备请求的时候，因为提案编号 9 大于它们之前响应的准备请求的提案编号 5，但这两个节点之前通过了提案[5, 7]，接受者A、B会在准备请求的响应中，包含已经通过的最大编号的提案信息[5, 7]，并承诺以后不再响应提案编号小于等于 9 的准备请求，不会通过编号小于 9 的提案；由于之前没有通过任何提案，所以节点 C 将返回一个 “尚无提案”的响应。并承诺以后不再响应提案编号小于等于 9 的准备请求，不会通过编号小于 9 的提案。接受阶段：当客户端 3 收到大多数的接受者的准备响应后（节点 A、B 和节点 C），根据响应中提案编号最大的提案的值，来设置接受请求中的值。因为来自节点 A、B 的准备响应中为[5, 7]和C的准确响应为空，所以就把节点 A、B的响应值 7 作为提案的值，发送接受请求[9, 7]。当节点 A、B、C 收到接受请求[9, 7]的时候，由于提案的提案编号 9 不小于三个节点承诺能通过的提案的最小提案编号 9，所以就通过提案[9, 7]，也就是接受了值 7，三个节点就 X 值为 7 达成了共识
展开
作者回复: 加一颗星:)
共 5 条评论
28
竹马彦四郎的好朋友影...
2020-05-01
这里总结一下韩老师讲解的为什么需要Basic paxos算法，或者说Basic Paxos 算法到底解决了个什么问题 Basic Paxos 算法解决的问题是一个分布式系统如何就某个值X（决议）达成一致。一个典型的场景是，在一个分布式数据库存储中，如果各节点的初始状态一致，每个节点执行相同的操作序列（例如上面是每个节点都要执行SET(X, 3)操作和SET(X, 7)操作，其中SET(X, 3)指令是客户端1向每个节点发出，SET(X, 7)指令是客户端2向每个节点发出），那么他们最后肯定能达到一个一致的状态。例如A、B、C三个节点执行的指令按照顺序都是 SET(X,3)-->SET(X, 7)的话，则A、B、C三个节点最终X的值都是7. 但是网络的不可靠性导致实际上最后每个节点执行的指令顺序并不一样，如果A节点、B节点执行顺序是SET(X,3)-->SET(X,7)，则A、B节点上最后的值就是X=7，而C节点上可能因为网络原因执行的顺序是 SET(X,7)-->SET(X,3), 结果最后C节点上的X值就是3了. 这种情况可能导致客户端发送相同执行指令，但是最终节点上的值不完全相同. 我们当然不希望看到这种情况的发生. 于是 Basic paxos算法横空出世. basic paxos算法需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。
展开
作者回复: 加一颗星:)
共 3 条评论
23
vi
2020-02-28
看了评论的推导，理解了结果是[9,7]，还有另外一个问题，对于接收阶段的值是如何确定的呢？如果问题改为，只有一个节点A通过提案[5, 7]，另外两个节点 B,C 未通过任何提案，这个时候客户端发起[9,6]的请求时，三个结点的最终值还会是[9,7]么？
作者回复: 最终的值，可能是6，也可能是7，取决于节点A的准备响应，是否是“大多数”中的一个。
共 12 条评论
14
NICK
2020-02-29
对思考题有个疑问，这个x的值是不是只要大多数节点通过后就不能被update了？即只要过半数的节点通过后，无论后面的新的请求的提案编号多高，这个值都不会被更新了？这个感觉哪里不对啊！
作者回复: 加一颗星：是这样的:)，通过提案是不会改的的，如果有节点上不存在通过的提案，不管后来的提议者，如何提交提案，值都不变的，也就是节点C上的X值是7，3个节点上的X值，都是7。通过这个思考题，希望大家注意到这么2点，首先在Basic Paxos的准备阶段，是会发现之前通过的提案的值；另外，Basic Paxos是一个共识算法，就一个值达成共识后，共识的这个值，就不会再变了。
共 3 条评论
13
Dovelol
2020-02-22
老师好，今天题目开始说到是一个只读的kv存储，那是不是只要最后所有节点数据一样就算成功了？如果某个节点挂了，重启了该怎么获取到最新值呢？如果是可读写的节点，该怎么取更新某个值呢？
作者回复: 大多数节点就某个值，达成共识后，值就不再变了，哪怕有新的提案，这个值，也能保证不再变了。节点挂了，属于系统实现层面，如何同步数据的问题，如果要处理的话，比如，可以这么做，实现数据同步机制或重新执行Basic Paxos。如果更新某个值，这是需要Multi-Paxos和状态机，我19、20讲，我会具体说说。咱们要注意的一点，Basic Paxos只能就单值达成共识，属于一个基础算法，Multi-Paxos，才能在实际场景中落地。
共 2 条评论
11
88591
2020-03-31
准备阶段： 1、 client3 [9,]—>A 、A 已提案通过，承诺编码为>=9、被返回 [5,7] 2、client3 [9,]—>B 、B 已提案通过,承诺编码为>=9、被返回 [5,7] 3、client3 [9,]—>C 、C 无提案通过,承诺编码为>=9、被返回尚无提案 C 收到的提议 [5,7]或者[9,6],不管是先收到5，还是9，都会承诺9. 接受阶段 client3 ：依据A,B 返回的信息为[5,7]，多数提议为【5，7】，只更新自己的编码不更新值 1、client3 [9,7]—> A ,A 提案通过。 2、client3 [9,7]—>B , B 提案通过, 3、client3 [9,7]—>C ,C 提案通过 4、学习者学习改提案值
展开
作者回复: 加一颗星:)
共 2 条评论
9
byrne
2020-05-20
老师，我下面的例子是我哪里理解错了，望百忙中抽空回答下，谢谢！假设有ABC三个节点，客户端甲发起一次提案编号1将X的值设为1，假设AB两个节点都收到客户端甲这次提案，客户端甲得到AB两个节点的应答之后开始进入第二阶段（三个节点中的两个，所以已经是大部分节点给了应答），假设此时客户端乙又发起一次提案编号2将X的值设为2，假设B和C两个节点收到客户端乙的提案，B发现编号2大于原先的编号1，因此给客户端乙回了没有提案，C由于从来没收到提案，因此也给客户端乙回了没有提案，此时客户端乙也进入了第二阶段，这样客户端甲将A节点的X设定为1，客户端乙将B和C节点的X设为2，这样两边就不一致了。
展开
作者回复: 加一颗星:)，这种情况属于一个异常情况，与实现有关，也是Basic Paxos没有约定的，在实现中，客户端重试就可以了。其实，异常情况（比如网络连接失败）虽然会肯定发生，但概率低，持续时间很短，“失败 - 缓存 - 重试”是一种很好的解决办法。
共 11 条评论
7
piboye
2020-04-27
怎么保障提案号不重复呢？
作者回复: 加一颗星:)，可以通过独立单调递增、随机超时，来避免重复冲突，比如，可以参考Hashicorp Raft对CurrentTerm的实现。
共 2 条评论
7
沉淀的梦想
2020-02-21
Basic Paxos 是只能用来解决这种只有一个 Key 的并且一次性赋值的只读 KV 存储的一致性问题吗？如果有多个 Key，或者要反复修改，就要用 Multi Paxos？
作者回复: Basic Paxos解决的单值的共识的问题，如果需要就一系列值达成共识，就多执行几次Basic Paxos，也就是Multi Paxos。如果，多个key，需要反复修改时，之前的共识是不能修改的，可以在之前的共识的基础之上，实现新的指令，在提交给状态机后，就可以修改value了。
共 3 条评论
7
X中倪
2020-03-08
有个小问题。延伸一下，这里的提案编号就好比达成共识协商的优先级别。就拿文章上述说的1，5提案编号对应的提案值是3，7。假设来了一个很好的提案的值这个值就是 6 ，但是提案编号是4 。自然都舍去了提案号为4的提案。系统该怎么才能接受这个提案编号为4 的提案值呢。对映上述疫情，优先级越大那么接受的可能就越大。假设 A B的提案编号是 200，500 。这时来了一个C 他的提案是最完美的，他的提案编号是100 ，怎么才能不被舍弃。
展开
作者回复: 加一颗星:)，其实Basic Paxos不关心这个问题，Basic Paxos解决的是如何就单值达成共识，并保证达成共识后的值，就不再变了。在这个延伸中，探讨的是如何接受最适合的值，既然我们知道它最适合了，就可以直接赋值了，不使用共识算法。正如，我们在文中常说的，技术用来解决问题，需要根据场景特点，选择适合的技术。
共 2 条评论
6
神垂死
2021-09-05
可以看下这个文章，讲得非常清楚：https://www.cnblogs.com/linbingdong/p/6253479.html
共 2 条评论
4
烽火戏诸侯
2020-03-22
每个客服端的提案号如何生成的
作者回复: 加一颗星:)，如何实现提案编号？论文提到了思路，独立、递增、存储在可靠性设备中。具体细节实现，可以参考Hashicorp Raft的CurrentTerm的实现（Raft.setCurrentTerm()、raftState.getCurrentTerm()、raftState.setCurrentTerm()），原子、递增、持久存储。
共 2 条评论
4
kylexy_0817
2020-03-21
韩老师好，想问下有没达到数据共识后，还需要发生改变的情况呢？该算法是达到共识后，就不能改变了，所以不能用来处理这种情况了吧？
作者回复: 在实际场景中，需要改变的不是达成共识的值，而是最终数据的值，比如KV存储系统。对于共识算法而言，达成了共识后，值就不会再变了，但如果我们想改变数据的值，可以实现状态机，和提议新的指令。
共 3 条评论
4
Geek_b1b6b1
2020-12-10
为什么达成共识之后还需要去处理请求。直接拒绝不可以吗？反正都不能修改
共 1 条评论
3
竹马彦四郎的好朋友影...
2020-04-28
感觉paxos这个大多数是个本质核心啊~ 它能保证一旦达成共识，后面除了提案编号变大之外，提案的值不变，而且2pc的第一阶段就能感知到已经通过的提案的信息，很神奇的算法！
作者回复: 加一颗星:)，很经典。
共 2 条评论
3
ID171
2020-02-21
因为节点C没有通过提案，可能是在接受阶段没有接收到来自客户端2的信息。当客户端3提出提案9，提议阶段节点A, B将会把已经通过的值7返回给C，在接受阶段，客户端3会通知节点C设置[9, 7] （这里有个问题，还需要同步信息给A, B吗，需要把提案编号9保存在A, B, C节点上吗？），然后三个节点 A, B ,C 的X值均为7
作者回复: 加一颗星:)，从代码实现的角度，是需要的。
共 3 条评论
3
LWD
2021-10-17
有一篇文章是这样总结的： Our full Paxos protocol now looks like this: Phase 1a: Proposer (PREPARE) A proposer initiates a PREPARE message, picking a unique, ever-incrementing value. ID = cnt++; send PREPARE(ID) Phase 1b: Acceptor (PROMISE) An acceptor receives a PREPARE(ID) message: if (ID <= max_id) do not respond (or respond with a "fail" message) else max_id = ID // save highest ID we've seen so far if (proposal_accepted == true) // was a proposal already accepted? respond: PROMISE(ID, accepted_ID, accepted_VALUE) else respond: PROMISE(ID) Phase 2a: Proposer (PROPOSE) The proposer now checks to see if it can use its proposal or if it has to use the highest-numbered one it received from among all responses: did I receive PROMISE responses from a majority of acceptors? if yes do any responses contain accepted values (from other proposals)? if yes val = accepted_VALUE // value from PROMISE message with the highest accepted ID if no val = VALUE // we can use our proposed value send PROPOSE(ID, val) to at least a majority of acceptors Phase 2b: Acceptor (ACCEPT) Each acceptor receives a PROPOSE(ID, VALUE) message from a proposer. If the ID is the highest number it has processed then accept the proposal and propagate the value to the proposer and to all the learners. if (ID == max_id) // is the ID the largest I have seen so far? proposal_accepted = true // note that we accepted a proposal accepted_ID = ID // save the accepted proposal number accepted_VALUE = VALUE // save the accepted proposal data respond: ACCEPTED(ID, VALUE) to the proposer and all learners else do not respond (or respond with a "fail" message) If a majority of acceptors accept ID, value then consensus is reached. Consensus is on the value, not necessarily the ID.
展开
共 1 条评论
2

