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

程序员潇然

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

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。

这大概也就是为什么这一篇的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/

下面介绍的是经典的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）

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

单个接受者

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

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

但是很显然，如果只有一个接受者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。

图解

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

如何满足？

关于P2b如何满足？

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

数学归纳法

证明

命题：假设某个提议{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 。

两阶段提交

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

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

类比到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的算法处理逻辑。

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请求的数量。

最终归结为两个阶段：

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

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

比如这样一个场景

首先是prepare阶段

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

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

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

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

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

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

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

接来来是accept阶段

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

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

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

注意

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

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

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

小结

提议编号顺序简单的就可以理解为优先级，根据优先级（编号的大小），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进行唯一提议者，也就不存在冲突了

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

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

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

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

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

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