共识算法Paxos

共识算法Paxos,第1张

1. 背景

  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 Made Simple》 翻文《共识算法论文——Paxos Made Simple》
2. 学习心得

  第一次学习paxos算法是在《极客时间——分布式协议与算法实战》专栏,反复看了多遍专栏中paxos算法,里面介绍的案例推算过程已经明了。当回过头再看paxos算法的时候,发现很多问题从专栏中介绍的案例中都无法解答,甚至对专栏中介绍的例子需要解决的问题产生了疑问——到底需要解决什么问题。剩下的问题还有:1.怎样容错;2.服务各种故障之后怎样保证算法的正确性等等。
  之后在网上查看了多篇介绍Paxos算法的博客,大多都是通过例子来说明,没有得到我需要的答案。后面找到了Lamport的论文《Paxos Made Simple》然后回过头再看专栏,专栏中的Paxos算法例子需要解决的问题是——在集群中给个各节点创建达成共识的只读变量。容错问题作者在文中有指明但没有展开说明其中关键词是“大多数”。
  专栏中作者是围绕一个案例来介绍,例子不难理解,但不容易理解这样做的深层次的原理。如果之前没有看过这个专栏或者共识算法介绍,直接看Lamport的论文《Paxos Made Simple》,也是很难理解的。比较好的方法是,先看专栏再看论文,看完论文之后再回过来分析专栏中的示例。接下来介绍专栏中作者的例子。

  关于前面学习了多遍专栏,对专栏中示例需要解决的问题产生疑问的思考。1.阅读一遍和阅读多遍,认知上是不一样的;2.有先入为主的因素,纠正先入为主的观念也是这次一个收获。

3 Paxos Made Simple 概念回顾

  在一些经典的算法中,你会看到一些既形象又独有的概念(比如二阶段提交协议中的协调者),Basic Paxos 算法也不例外。在《共识算法论文——Paxos Made Simple》中有介绍兰伯特提出的概念:

  • value:提案值,是一个抽象的概念,这里不能把它简单的理解为数值。而应该理解为对某一数据或数据库某一行的某一列的一系列 *** 作。
  • number:提案编号,全局唯一,单调递增。
  • proposal:集群需要达成共识的提案,拥有 number 和 value。

proposal 中的 value 就是在 Paxos 算法完成之后需要达成共识的值。

Paxos 算法中有三个核心角色:

  • Proposer:生成提案编号 n 和 value v,然后向 Acceptors 广播该提案,接收 Acceptors 的回复,如果有超过半数的 Acceptors 同意该提案,则选定该提案,否则放弃此次提案并生成更新的提案重新发起流程,提案被选定之后则通知所有 Learners 获取该最终选定的提案值(也可以由 Acceptor 来通知,看具体实现)。Basic Paxos 中允许有多个 Proposers。
  • Acceptor:接收 Proposer 的提案并参与提案的表决过程,把各自的决定回复给 Proposer 进行统计。Acceptor 可以接受来自多个 Proposers 的多个提案。
  • Learner:不参与决策过程,只获取最终选定的提案 value。
4. 思考题 4.1 问题

  在一个分布式集群中有A、B、C三个节点,提供只读KV存储服务,只读服务要求是创建之后就无法修改,所以所有节点必须要先对只读变量的值达成共识,然后所有节点再一起创建这个只读变量。需要怎样实现这个集群?

说明:达成的值是多少我们并不关心,需要的是三个节点值是一致的。

4.2 问题示例分析

  当有多个客户端(比如客户端 1、2)访问这个系统,客户端1创建只读X=3,客户端2创建只读X=7,怎样保证保证节点上创建的数据是一致的?

(图一)

4.3 三种角色

(图二)
  • 提议者(Proposer):提议一个值,用于投票表决。可以把图 1 中的客户端 1 和 2 看作是提议者。但在绝大多数场景中,集群中收到客户端请求的节点,才是提议者(图 1 这个架构,是为了方便演示算法原理)。这样做的好处是,对业务代码没有入侵性。
  • 接受者(Acceptor):对每个提议的值进行投票,并存储接受的值,比如 A、B、C 三个节点。

可能的疑惑:前面说接收客户端请求的节点是提议者,这里怎么又是接受者呢?

  1. 在《Paxos Made Simple——2.1 The Problem》 兰伯特也提到,只是不是论文所关心的实现问题。
  2. 这是因为一个节点(或进程)可以身兼多个角色。想象一下,一个 3 节点的集群,1 个节点收到了请求,那么该节点将作为提议者发起二阶段提交,然后这个节点和另外 2 个节点一起作为接受者进行共识协商,就像下图的样子:

(图三)
  • 学习者(Learner):被告知投票的结果,接受达成共识的值,存储保存,不参与投票的过程。一般来说,学习者是数据备份节点,比如“Master-Slave”模型中的 Slave,被动地接受数据,容灾备份。

这三种角色,在本质上代表的是三种功能:

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

一个完整的共识算法过程是由这三种角色对应的功能组成的,理解这三种角色,是理解 Basic Paxos 如何就提议的值达成共识的基础。

4.4 如何达成共识

  在 Paxos算法 中,兰伯特使用提案代表一个提议。在提案中,除了提案编号,还包含了提议值。为了方便演示,使用[n, v]表示一个提案,其中 n 为提案编号,v 为提议值。整个共识协商是分 2 个阶段进行的。

《Paxos Made Simple》两阶段提交介绍:

阶段 1:准备阶段
(a) Proposer 选择一个 proposal 编号 n,向 “大多数” Acceptor 发送一个带有编号 n的 prepare 请求;
(b) 如果 Acceptor 收到一个编号为 n 的 prepare 请求,且 n 比它已经响应过的任何一个 prepare请求的编号都大,则它会向这个请求回复响应,内容包括:一个不再接受任何编号小于 n 的 proposal 的承诺,以及它已经接受过的最大编号的 proposal(假如有的话)。

阶段 2:接受阶段
(a) 如果 Proposer 从"大多数" Acceptor 收到了对它前面发出的 prepare 请求的响应,它就会接着给这些 Acceptor 发送一个编号为 n 且 value 为 v 的 proposal 的 accept请求,而 v 就是它所收到的响应中最大编号的 proposal 的 value,或者是它在所有响应都表明没有接受过任何 proposal 的前提下自由选择的 value v;
(b) 如果 Acceptor 收到了一个编号为 n 的 proposal 的 accept 请求,它就会接受这个请求,除非它之前已经响应过编号大于 n 的 request 请求。

  我们假设客户端 1 的提案编号为 1,客户端 2 的提案编号为 5,并假设节点 A、B 先收到来自客户端 1 的准备请求,节点 C 先收到来自客户端 2 的准备请求。

4.4.1 准备(Prepare)阶段
  1. 客户端 1、2 作为提议者,分别向所有接受者发送包含提案编号的准备请求:
(图四)

注意,在准备请求中是不需要指定提议的值的,只需要携带提案编号就可以了。

  1. 当节点 A、B 收到提案编号为 1 的准备请求,节点 C 收到提案编号为 5 的准备请求后,将进行这样的处理:
(图五)
  • 由于之前没有通过任何提案,所以节点 A、B 将返回一个 “尚无提案”的响应。也就是说节点 A 和 B 在告诉提议者,我之前没有通过任何提案呢,并承诺以后不再响应提案编号小于等于 1 的准备请求,不会通过编号小于 1 的提案。
  • 节点 C 也是如此,它将返回一个 “尚无提案”的响应,并承诺以后不再响应提案编号小于等于 5 的准备请求,不会通过编号小于 5 的提案。
  1. 当节点 A、B 收到提案编号为 5 的准备请求,和节点 C 收到提案编号为 1 的准备请求的时候,将进行这样的处理过程:
(图六)
  • 当节点 A、B 收到提案编号为 5 的准备请求的时候,因为提案编号 5 大于它们之前响应的准备请求的提案编号 1,而且两个节点都没有通过任何提案,所以它将返回一个 “尚无提案”的响应,并承诺以后不再响应提案编号小于等于 5 的准备请求,不会通过编号小于 5 的提案。
  • 当节点 C 收到提案编号为 1 的准备请求的时候,由于提案编号 1 小于它之前响应的准备请求的提案编号 5,所以丢弃该准备请求,不做响应。
4.5.2 接受(Accept)阶段

  第二个阶段也就是接受阶。

  1. 首先客户端 1、2 在收到大多数节点的准备响应之后,会分别发送接受请求:
(图七)
  • 当客户端 1 收到大多数的接受者(节点 A、B)的准备响应后,根据响应中提案编号最大的提案的值,设置接受请求中的值。因为该值在来自节点 A、B 的准备响应中都为空(也就是图 5 中的“尚无提案”),所以就把自己的提议值 3 作为提案的值,发送接受请求[1, 3]。
  • 当客户端 2 收到大多数的接受者的准备响应后(节点 A、B 和节点 C),根据响应中提案编号最大的提案的值,来设置接受请求中的值。因为该值在来自节点 A、B、C 的准备响应中都为空(也就是图 5 和图 6 中的“尚无提案”),所以就把自己的提议值 7 作为提案的值,发送接受请求[5, 7]。
  1. 当三个节点收到 2 个客户端的接受请求时,会进行这样的处理:
(图八)
  • 当节点 A、B、C 收到接受请求[1, 3]的时候,由于提案的提案编号 1 小于三个节点承诺能通过的提案的最小提案编号 5,所以提案[1, 3]将被拒绝。
  • 当节点 A、B、C 收到接受请求[5, 7]的时候,由于提案的提案编号 5 不小于三个节点承诺能通过的提案的最小提案编号 5,所以就通过提案[5, 7],也就是接受了值 7,三个节点就 X 值为 7 达成了共识。
4.5.3 学习者

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

4.5.4 结论

  通过上面的演示过程,最终各节点就 X 的值达成了共识。
  需要了解的是,Basic Paxos 的容错能力,源自“大多数”的约定,可以这么理解:当少于一半的节点出现故障的时候,共识协商仍然在正常工作。

4.6 小结
  • 可以看到,Basic Paxos 是通过二阶段提交的方式来达成共识的。二阶段提交是达成共识的常用方式,如果我们需要设计新的共识算法的时候,也可以考虑这个方式。
  • 除了共识,Basic Paxos 还实现了容错,在少于一半的节点出现故障时,集群也能工作。它不像分布式事务算法那样,必须要所有节点都同意后才提交 *** 作,因为“所有节点都同意”这个原则,在出现节点故障的时候会导致整个集群不可用。也就是说,“大多数节点都同意”的原则,赋予了 Basic Paxos 容错的能力,让它能够容忍少于一半的节点的故障。
  • 本质上而言,提案编号的大小代表着优先级,你可以这么理解,根据提案编号的大小,接受者保证三个承诺:
    1. 如果准备请求的提案编号,小于等于接受者已经响应的准备请求的提案编号,那么接受者将承诺不响应这个准备请求;
    1. 如果接受请求中的提案的提案编号,小于接受者已经响应的准备请求的提案编号,那么接受者将承诺不通过这个提案;
    1. 如果接受者之前有通过提案,那么接受者将承诺,会在准备请求的响应中,包含已经通过的最大编号的提案信息。
5. 论文中定义
  • P1. 接受者(acceptor)必须接受它收到的第一个提案。
  • P2. 如果一个 value 为 v 的 proposal 被选中,那么所有被选中的高编号(high-numbered)的 proposal 都包含 value v。
5.1 论文中定义分析 5.1.1 P1定义

P1. 接受者(acceptor)必须接受它收到的第一个提案。

推到原因:在没有失败或消息丢失的情况下,即使单个提议者只提出一个值,我们也希望选择这个值。

5.1.2 P2定义

P2. 如果一个 value 为 v 的 proposal 被选中,那么所有被选中的高编号(high-numbered)的 proposal 都包含 value v。

推到过程:见《共识算法论文——Paxos Made Simple》

P2(a). 如果一个 value 为 v 的 proposal 被选中,那么任何 Acceptor 接受的每个高编号的 proposal 都有 value v。
P2(b). 如果一个 value 为 v 的 proposal 被选中,那么之后每个 Proposer 提议的高编号的 proposal 都有 value v。

因为一个proposal 在被acceptor接受之前都要首先由proposer发出。因此满足P2b就满足了P2a,也就满足了P2。
在4.6小结中的三个承诺,是对这个定义的概括。

6. 思考题2

在上文示例中,如果节点 A、B 已经通过了提案[5, 7],节点 C 未通过任何提案,那么当客户端 3 提案编号为 9 时,通过 Basic Paxos 执行“SET X = 6”,最终三个节点上 X 值是多少呢?

6.2 答案

最终节点值应该是[9,7]。

  1. 在准备阶段,节点C收到客户端3的准备请求[9,6], 因为节点C未收到任何提案,所以返回“尚无提案”的响应。这时如果节点C收到了之前客户端的准备请求[5, 7], 根据提案编号5小于它之前响应的准备请求的提案编号9,会丢弃该准备请求【P1】。
  2. 客户端3发送准备请求[9,6]给节点A,B,这时因为节点A,B已经通过了提案[5,7], 根据“如果接受者之前有通过提案,那么接受者将承诺,会在准备请求的响应中,包含已经通过的最大编号的提案信息”,节点A,B会返回[5,7]给客户端3【承诺3】。
  3. 客户端3发送会接受请求[9,7]给节点A,B,C(注意这里使用的是准备阶段的最大提议编号和已经被通过的值),因为此时请求编号9不小于之前的请求编号,所以所有节点接受该请求[9,7]。
  4. 所有学习者会接受该提案,学习该值。
6.3 小结

  解决这个问题的关键是理解4.6中的三个承诺。这个三承诺,可以理解为是对兰伯特论文中P2定义的概括。(先这样理解吧,不一定完全准确)

参考:
《极客时间——分布式协议与算法实战》
《共识算法论文——Paxos Made Simple》

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/727636.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-26
下一篇 2022-04-26

发表评论

登录后才能评论

评论列表(0条)

保存