请选择 进入手机版 | 继续访问电脑版

[分布式系统] 分布式系统非拜占庭错误故障错误算法paxos 算法

计算机科学 计算机科学 1738 人阅读 | 0 人回复

拜占庭将军问题中,提出分为两种解决问题的方向

https://www.crazybytex.com/thread-239-1-1.html

一种是非拜占庭错误,一种是拜占庭错误。

把出现故障( crash 或 fail-stop,即不响应)但不会伪造信息的情况称为“非拜占庭错误”( non-byzantine fault)或“故障错误”( Crash Fault);

Paxos就是一种非拜占庭错误解决算法。

The part-time parliament

https://dl.acm.org/doi/10.1145/279227.279229

中文版 https://www.crazybytex.com/thread-243-1-1.html

最近在Paxos岛上的考古发现表明,尽管兼职的立法者到处流动,但议会仍在运作。

尽管议员们经常突然闯入参加会议,而且他们的信使也很健忘,但议员们仍然保持着议会记录的一致副本。

Paxon议会的协议提供了一种实现分布式系统设计的状态机的新方法。

类比到分布式系统中:

议员->节点

议员游走流动/闯入参会->节点的上线/下线

信使靠谱/健忘->网络的联通/失效

议会记录一致->分布式系统达成共识

关于这段论文发表的历史比较有趣,lamport在下面的网址中有描述

http://lamport.azurewebsites.net/pubs/pubs.html#lamport-paxos

为了进一步展示形象,我以印第安纳-琼斯式考古学家的身份做了几次讲座,戴着斯泰森帽子和臀部烧瓶。

我试图在这个主题中插入一些幽默,但失败了。参加我讲座的人记得印第安纳琼斯,但不记得算法。

1990年向TOCS提交了这篇论文。三位审稿人都说这篇论文有点有趣,虽然不是很重要,但所有Paxos的东西都必须删除。我对在这个领域工作的每个人似乎都很不幽默感到非常恼火,所以我没有对论文做任何事情。

This paper won an ACM SIGOPS Hall of Fame Award in 2012.

另外lamport 在下面网址中说道:

http://lamport.azurewebsites.net/pubs/pubs.html#paxos-simple

在2001年的PODC会议上,我厌倦了每个人都说理解Paxos算法是多么困难,发表于[123]。尽管人们对伪希腊语的名字非常着迷,可他们认为论文很难理解,但算法本身非常简单。

所以,我在会议上逮到几个人,口头向他们解释了算法,没有论文。回到家后,我把解释写成了一张简短的纸条,后来我根据弗雷德·施耐德和巴特勒·兰普森的评论对其进行了修改。当前版本长达13页,其中没有比n1>n2更复杂的公式。

2015年,亚马逊的Michael Deardeuff告诉我,这篇论文中的一句话是模棱两可的,错误的解释理解会导致错误的算法。

Deardeuff发现Github上的许多Paxos实现实现了这种不正确的算法。

显然,实现者没有费心阅读[123]中算法的精确描述。我不会消除这种歧义,也不会揭示它在哪里。散文不是精确描述算法的方法。不要试图实现本文中的算法。改用[123]。

[123] 指的就是The part-time parliament

paxos-made-simple

https://www.microsoft.com/en-us/research/publication/paxos-made-simple/?from=https://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf&type=exact

简单说大神觉得这个事情很简单,你们怎么这么笨?

于是出了一个解释性的文档,当然,他提出还是需要The part-time parliament按照来实现算法,而不是这篇simple。

image.png

这大概也就是为什么这一篇的Abstract为什么只有一句话的原因吧

paxos made simple 翻译 中文版 https://www.crazybytex.com/thread-242-1-1.html

关于paxos发展历史,详见转载的一篇文章:https://www.crazybytex.com/thread-241-1-1.html

paxos made simple 是对The part-time parliament的解释说明,他们并不是两回事,相对来说simple更加容易理解一些,尽管仍旧是不太容易理解

Raft作者讲解Paxos:《Implementing Replicated Logs with Paxos》

ppt内容地址:

https://gitee.com/crazybytex/some-documents/blob/master/implementing%20replicated%20logs%20with%20paxos.pdf

在线讲解:

https://www.youtube.com/watch?v=JEpsBg0AO6o&t=41s

https://www.bilibili.com/video/av36556594/?vd_source=7741be735669cf4a8d044c6942e6c0e3

Fast Paxos

在到后面,lamport提出了改进的算法,提出了fast paxos ,之前的paxos就被称之为classic paxos

这个算法就是字面意思,改进了的,更快速的paxos

https://www.microsoft.com/en-us/research/publication/fast-paxos/

image.png

下面介绍的是经典的paxos

Paxos算法

以上是一些背景说明、文献指引记录,下面开始简单分析算法。

论文提出的算法可以认为是包含两个部分:

Basic Paxos 算法,描述的是多节点之间如何就某个值(提案 Value)达成共识;

Multi-Paxos 思想,描述的是执行多个 Basic Paxos 实例,就一系列值达成共识。

Basic Paxos 是 Multi-Paxos 思想的核心,本文先介绍Basic Paxos。

Basic Paxos

需求

  1. Only a value that has been proposed may be chosen,
  2. Only a single value is chosen, and
  3. A process never learns that a value has been chosen unless it actually has been.

以上是paxos made simple中关于达成共识的要求。

为了达成这几个目标,定义了几个角色,配合来执行

角色

在 Basic Paxos 中,有提议者(Proposer)、接受者(Acceptor)、学习者(Learner)三种角色

提议者(Proposer):提议一个值(Proposal),用于投票表决,Proposal信息包括提案编号 (Proposal ID) 和提议的值 (Value)。

接受者(Acceptor):对每个被提议的值进行投票(accept),并保存接受的值,也就是参与决策,回应Proposers的提案。收到Proposal后可以接受提案,若Proposal获得多数Acceptors的接受,则称该Proposal被批准。

学习者(Learner):被告知投票的结果,接受达成共识的值,存储保存,不参与投票的过程,也就是不参与决策,从Proposers/Acceptors学习最新达成一致的提案(Value)

image.png

这是一种比较严格、明确的划分,但是在实际的分布式系统中,通常每一个节点都将是提案者、接受者、学习者,因为他们都有可能接收来自外部用户客户端的请求,此时他就是提案者,然后他也需要参与接受者的过程,最终达成一致后,每个人也都是学习者,都要知悉最终的结论,并且存储这些数据。

单个接受者

核心目标是达成共识,那么最简单的无脑处理方法就是简化为只有一个接受者

这个唯一的接受者,根据他自己的处理逻辑,比如选择收到的第一个请求,作为最终一致的一个值,也是可以实现核心目标的。

image.png

但是很显然,如果只有一个接受者Acceptor ,一旦这个唯一单机,将会使系统不可用,对于分布式系统来说是灾难性的。

解决方法就必须是多接受者,Multiple acceptors

这样只要大多数接受者可以达成一致,最终一个值被选择出来(chosen),单节点的宕机就不会影响整个系统。

必须接受收到的第一个值

假设可以不接受第一个值,那么如果只有一个Proposer时,这个唯一的proposal如果可以不接受,那么后面将不再有任何Proposer进行提议,那么永远无法达成共识,为了满足这种场景下可以继续达成共识,必须接受第一个值。

都必须可以接受多个值

基于“必须接受收到的第一个值”,假设每个acceptor仅仅接受他收到的第一个值,如果有三个proposer,分别提出了三个提议,发给了三个acceptor,那么因为他们仅仅接受收到的第一个值,不接受别的值,无法达成一致,所以,每个acceptor都还可以接受多个值,就是选你也可以,选他也可以。

【编号+值】对提议进行编号

如果根据到达acceptor的先后顺序做处理:先到的被接受,后面的都丢弃,那此时acceptor只能接受一个提议; 如果后到的都被接受,那么当某value被选定后,其他proposer提出新value,选定的value就会被覆盖,导致由选定进入不选定状态,甚至进入下个value的选定状态,违反了一致性。

如果根据value的大小做处理:由于acceptor要能接受多个提案,提案可能存在被覆盖的情况,因此要保证可能被选定的value在被其他提案覆盖的情况下,仍旧能够记录保留 另外假设经历多轮选举,对于同一个proposor发送的多个提案,如何区分他的轮次?

因此有了提案=全局唯一编号+value的设计,通过编号的偏序关系定义acceptor处理提案的方式。

简单说一个有序的不重复的自然数序列作为编号对值进行标记,可以解决很多麻烦。

所有被选择的具有相同的值

Only a single value is chosen(只有一个值被选择),而且每个acceptor都可以接受多个值。

那么必须要保证所有的被选择的proposals 是同样的值(we must guarantee that all chosen proposals have the same value),如果大家选择的五花八门,就没有办法保证最终能够达成一致。

By induction on the proposal number, it suffices to guarantee: P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

通过归纳法,如果一个proposal 值v被选择,那么每一个更高序号的被选择的proposal 他的值也是v,就可以保障“所有被选择的具有相同的值”。

又因为被选择的,肯定是要被接受的,被接受的肯定是要被提出来的

所以:

P2b. If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

也就是如果一个proposal 值v被选择,那么每一个,被任意proposer提出的,一个更高编号的proposal的值是v。

图解

上面的一个简单的推导过程图解如下,右键新标签查看大图

image.png

如何满足?

关于P2b如何满足?

也就是上图的最下面的这个要求

数学归纳法

image.png

证明

命题:假设某个提议{m, v}被选择,任何编号n>m的提议的值都是v。

①设(m,v) 是被选中的,提议的值是v ②假设编号从m到n-1的每个提议值都是v(i..j 表示从i到j的所有整数的集合),如果可以由此推得,m=n时,提议的值是v,那么命题成立。

过程:

对于已被选择(chosen)的编号为m的提议,必定存在某集合C,由接受了这个提议的acceptor多数派组成。 也就是说C中的每一个acceptor 都接受了编号为m..(n-1)中的一个提议(因为是C就是由接受了v的多数acceptor组成的),又依据假设②,被任意一个acceptor接受的编号为m..(n-1)的提议,他们的值都是v。

而且,任何一个多数派集合S,都必然包含一个元素属于C,因为任意两个多数派集合必然有交集,否则两个多数派并集就超出了原有集合了, 如果能够满足下面的条件,就可以保障编号n的提议,他的值也是v

对于任何值v 和n ,如果一个 proposal具有编号n 和值v ,那么由多数派 acceptor组成的集合S满足以下其中一个条件

  • S 中的 acceptor不会接受任何编号小于 n 的proposal。
  • 所有编号小于n并被S集合中的所有acceptor接受的提议中,v是编号最大的提议的值,也就是S中 acceptor接受的最大编号的 proposal的值为 v 。

两阶段提交

两阶段提交-通过两个阶段来完成一次提交动作。

直白的说就是开始干活之前,有一个确认的过程,先问一下是否准备妥当,大家都准备好了之后,就进行下一步;否则直接失败

image.png

类比到paxos算法,协调者就是提议者proposer,参与者就是接收者acceptor

解决过程

对于任何值v 和n ,如果一个 proposal具有编号n 和值v ,那么由多数派 acceptor组成的集合S满足以下其中一个条件

  • S 中的 acceptor不会接受任何编号小于 n 的proposal。
  • 所有编号小于n并被S集合中的所有acceptor接受的提议中,v是编号最大的提议的值,也就是S中 acceptor接受的最大编号的 proposal的值为 v 。

关于这个条件,也就是论文中的P2 <sub>c</sub>

如何保证?

一个proposer想要提出一个编号为n的proposal,就必须要知道目前所有的编号小于n的最高编号的proposal,这是很容易的,但是接下来的未来是很难预测的,所以无法预测,就直接拒绝,也就是不接受任何编号小于n的proposal

所以可以提出如下推导逻辑,这个就是proposer的算法处理逻辑。

image.png

prepare

一个 proposer选择一个新的编号为n 的 proposal,并发送请求到 acceptor的集合,并要求得到以下其中一个回应:

一个不会接受编号值小于n 的 proposal的承诺。 如果 acceptor已经接受过 proposal,则响应已接受的小于编号n 的最大编号的 proposal(如果有的话)。 将该请求称为编号为n 的prepare请求。

accept

如果proposer接受到了大多数的acceptor响应的请求,然后他就可以提出来一个proposal,编号为n,并且选择这些响应中编号最大的proposal中的值v,作为值v,如果没有人响应值,他就可以自己选一个其他的值。然后将这一次提议发送给acceptor集合,这就是accept请求。

上面是proposer的处理逻辑,对于acceptor,acceptor可以从 proposer接收两种类型的请求:

prepare和 accept请求。

acceptor如果不响应任何请求,并不会带来安全性的问题(最开始提出来的需要解决的问题,只有一个可以被选中那三条)

所以只需要说明,需要响应的时候的场景。

对于prepare请求,他总是可以响应的。

他也可以响应accept请求,接受这个提议,如果他没有承诺不接受(他是承诺不会接受编号值小于n 的 proposal),换句话说:

acceptor没有响应过编号大于n 的 prepare请求的话,那么可以接收一个编号为n 的 proposal。

假设 acceptor收到编号为n 的 prepare请求,但是已经响应过一个编号值大于n 的 prepare请求。

因此承诺不会接受任何编号为n 的新的 proposal请求。(不接受编号更小的)

这样,acceptor就没有理由响应新的 prepare请求,因为它不会接受 proposer想要发出的编号为n 的 proposal。

因此,我们让 acceptor忽略这样的 prepare请求。

我们也可以忽略它已经接受的 proposal的 prepare请求。 通过这种优化

接受者只需要记住它曾经接受的编号最高的 proposal以及它已响应的编号最高的 prepare请求的数量。

最终归结为两个阶段:

image.png

下图来自John Ousterhunt的ppt,一个更形象的描述。

https://gitee.com/crazybytex/some-documents/blob/master/implementing%20replicated%20logs%20with%20paxos.pdf

image.png

比如这样一个场景

image.png

首先是prepare阶段

初始时,P1、P2 进行广播发送(初始时是没有值的,这个值是选出来或者最后自己定的)

横向的是时间轴,靠右表示时间的推移

image.png

在每个节点第一次收到消息的时候,会接受消息,并且会返回当前没有选择的提议

A1、A2 第一次收到消息来自于P1,A3 第一次收到消息来自于P2

image.png

对于非第一次收到prepare消息,也就是A1、A2 收到P2,A3 收到P1 的时候

因为A1,A2 目前也都还没有通过任何提议,而且,编号7 大于编号3,所以她给P2 也会返回未接受任何提议的响应;

但是对于A3 收到P1的请求时,之前已经响应过A2的编号为5的prepare请求了,就不会响应这个P1的编号为3的请求了

image.png

接来来是accept阶段

此时,针对于P1,他已经收到了A1,A2(大多数)的未接受任何提议的响应了,所以他准备发送accept

针对于P2,他也收到了A1,A2,A3(大多数)的未接受任何提议的响应了,所以他准备发送accept

因为之前的节点都没有返回给P1和P2 他们有接受的提议,所以没有值,这个值就由P1,P2各自定

注意

虽然下图时间轴画的比较靠前,但是已经是对比prepare阶段往后推移过了的,可以认为开始的地方就比前面的最后晚。

image.png

因为A1、A2、A3已经承诺过不接受编号小于5的请求了,所以就不会对P1进行响应

只会对P2进行响应,所以都会对P2 响应对应的值9,所以就达成了一致性了

image.png

小结

提议编号顺序简单的就可以理解为优先级,根据优先级(编号的大小),acceptor有三个承诺:

如果prepare请求的编号,小于等于acceptor已经响应过得prepare编号,那么承诺不响应这个prepare请求。

如果accept请求的编号,小于acceptor已经响应的prepare请求的编号,那么acceptor承诺不通过这个提议。

如果acceptor之前有通过的提议,那么就会在prepare请求的响应消息里面,把通过的最大编号的提议信息发送过去。

Multi-Paxos

lamport描述了几种实现 multi-Paxos 的可行方法, 但缺失了细节。

也就是不是完备的、论证的算法。

后面大多都是基于multi-paxos算法进行的完善,但是很难证明。

所以也可以说:兰伯特提到的 Multi-Paxos 是一种思想,不是算法。

而 Multi-Paxos 算法是一个统称,它是指基于 Multi-Paxos 思想,通过多个 Basic Paxos 实例实现系列值的共识的算法(比如 Chubby 的 Multi-Paxos 实现、Raft 算法等)。

Chubby的 Multi-Paxos 实现,代表了Multi-Paxos思想在生产环境中的真正落地,它将一种思想变成了代码实现,其实也是因为Chubby的出现,让Paxos开始火了起来。

不过Chubby不是开源的。

这部分可以更多的参考原始论文The Part-Time Parliament

multi-Paxos如果直接多次执行basic-Paxos的话:

如果prepare阶段,没有协商成功,比如5个节点,有三个是proposer,必然不会有大多数进行响应,最多得到两个prepare的响应,准备阶段就失败了,也就是所谓的提议冲突

本身分布式系统基于rpc进行通讯,大量消息往返会消耗资源、时间,浪费性能。

可以通过引入Leader角色,通过Leader进行唯一提议者,也就不存在冲突了

image.png

论文中没有表明如何选出Leader,chubby是通过一轮Basic Paxos进行选举的。

本身prepare阶段就是发现选出被大多数通过的提议值,但是通过Leader,就不存在选举冲突,也就不存在多个值,都是Leader说了算,prepare就不再有意义,所以可以省略掉prepare阶段。也就是所谓的,领导者处于稳定状态时,省略掉准备阶段。

大大减少了消息的交互,退化为相当于单纯的主从节点数据通信交互。

Leader的本质就是我不要你们不断地商量,我只需要指定一个即可。毕竟很多场景下,比如选主,是谁都不重要,选出来最重要。

也就是不关心具体的值,只关心尽快达成一致。

common_log.png 转载务必注明出处:程序员潇然,疯狂的字节X,https://crazybytex.com/thread-240-1-1.html

关注下面的标签,发现更多相似文章

文章被以下专栏收录:

    黄小斜学Java

    疯狂的字节X

  • 目前专注于分享Java领域干货,公众号同步更新。原创以及收集整理,把最好的留下。
    包括但不限于JVM、计算机科学、算法、数据库、分布式、Spring全家桶、微服务、高并发、Docker容器、ELK、大数据等相关知识,一起进步,一起成长。
热门推荐
[若依]微服务springcloud版新建增添加一个
[md]若依框架是一个比较出名的后台管理系统,有多个不同版本。
[CXX1300] CMake '3.18.1' was not
[md][CXX1300] CMake '3.18.1' was not found in SDK, PATH, or
java 解析modbus 协议 Modbus4j应用 使用mo
[md]本文记录使用java开发modbus协议程序,与串口进行连接,使用