分布式系统非拜占庭错误故障错误算法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算法是多么困难，发表于。尽管人们对伪希腊语的名字非常着迷，可他们认为论文很难理解，但算法本身非常简单。
所以，我在会议上逮到几个人，口头向他们解释了算法，没有论文。回到家后，我把解释写成了一张简短的纸条，后来我根据弗雷德·施耐德和巴特勒·兰普森的评论对其进行了修改。当前版本长达13页，其中没有比n1>n2更复杂的公式。
2015年，亚马逊的Michael Deardeuff告诉我，这篇论文中的一句话是模棱两可的，错误的解释理解会导致错误的算法。
Deardeuff发现Github上的许多Paxos实现实现了这种不正确的算法。
显然，实现者没有费心阅读中算法的精确描述。我不会消除这种歧义，也不会揭示它在哪里。散文不是精确描述算法的方法。不要试图实现本文中的算法。改用。
指的就是**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。
!(data/attachment/forum/202212/02/110826blkc59czh51cbwbl.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "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 Logswith 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/`
!(data/attachment/forum/202212/06/145255ggknrinorzn4nktn.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "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 actuallyhas 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）
!(data/attachment/forum/202212/03/150713e3tscb1uggngn15s.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
这是一种比较严格、明确的划分，但是在实际的分布式系统中，通常每一个节点都将是提案者、接受者、学习者，因为他们都有可能接收来自外部用户客户端的请求，此时他就是提案者，然后他也需要参与接受者的过程，最终达成一致后，每个人也都是学习者，都要知悉最终的结论，并且存储这些数据。
### 单个接受者
核心目标是达成共识，那么最简单的无脑处理方法就是简化为只有一个接受者
这个唯一的接受者，根据他自己的处理逻辑，比如选择收到的第一个请求，作为最终一致的一个值，也是可以实现核心目标的。
!(data/attachment/forum/202212/03/162653cpssbhgoyofojh3o.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "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 proposalnumber, 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。
### 图解
上面的一个简单的推导过程图解如下，**右键新标签查看大图**
!(data/attachment/forum/202212/06/153605sod0mgevoos4wsu4.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
### 如何满足？
关于P2b如何满足？
也就是上图的最下面的这个要求
#### 数学归纳法
!(data/attachment/forum/202212/06/152140icumbyac5m5ag0y6.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "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 。
### 两阶段提交
两阶段提交-通过两个阶段来完成一次提交动作。
直白的说就是开始干活之前，有一个确认的过程，先问一下是否准备妥当，大家都准备好了之后，就进行下一步；否则直接失败
!(data/attachment/forum/202212/03/155057ka1aovbxm9vyzbm9.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "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的算法处理逻辑。
!(data/attachment/forum/202212/06/154016gi5azz694jdzi4id.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "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请求的数量。
最终归结为两个阶段：
!(data/attachment/forum/202212/06/170046dedy2c88p6rar6yv.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
下图来自John Ousterhunt的ppt，一个更形象的描述。
`https://gitee.com/crazybytex/some-documents/blob/master/implementing%20replicated%20logs%20with%20paxos.pdf`
!(data/attachment/forum/202212/06/163437ke7o44kb7kkb4lik.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
比如这样一个场景
!(data/attachment/forum/202212/06/174834hmptqss7tgujstj7.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
**首先是prepare阶段**
初始时，P1、P2 进行广播发送（初始时是没有值的，这个值是选出来或者最后自己定的）
横向的是时间轴，靠右表示时间的推移
!(data/attachment/forum/202212/06/174738e5db7tuxe507te6d.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
在每个节点第一次收到消息的时候，会接受消息，并且会返回当前没有选择的提议
A1、A2 第一次收到消息来自于P1，A3 第一次收到消息来自于P2
!(data/attachment/forum/202212/06/175022jyosl45i22yui555.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
对于非第一次收到prepare消息，也就是A1、A2 收到P2，A3 收到P1 的时候
因为A1，A2 目前也都还没有通过任何提议，而且，编号7 大于编号3，所以她给P2 也会返回未接受任何提议的响应；
但是对于A3 收到P1的请求时，之前已经响应过A2的编号为5的prepare请求了，就不会响应这个P1的编号为3的请求了
!(data/attachment/forum/202212/06/175328tczssboiybbrcuqf.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
**接来来是accept阶段**
此时，针对于P1，他已经收到了A1，A2（大多数）的未接受任何提议的响应了，所以他准备发送accept
针对于P2，他也收到了A1，A2，A3（大多数）的未接受任何提议的响应了，所以他准备发送accept
因为之前的节点都没有返回给P1和P2 他们有接受的提议，所以没有值，这个值就由P1，P2各自定
注意
虽然下图时间轴画的比较靠前，但是已经是对比prepare阶段往后推移过了的，可以认为开始的地方就比前面的最后晚。
!(data/attachment/forum/202212/06/175713mtb5x1bpp65ieq1p.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
因为A1、A2、A3已经承诺过不接受编号小于5的请求了，所以就不会对P1进行响应
只会对P2进行响应，所以都会对P2 响应对应的值9，所以就达成了一致性了
!(data/attachment/forum/202212/06/175939ubrbqabifwhwwed6.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "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进行唯一提议者，也就不存在冲突了
!(data/attachment/forum/202212/06/203308s552jk5ivsj5i5if.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "image.png")
论文中没有表明如何选出Leader，chubby是通过一轮Basic Paxos进行选举的。
本身prepare阶段就是发现选出被大多数通过的提议值，但是通过Leader，就不存在选举冲突，也就不存在多个值，都是Leader说了算，prepare就不再有意义，所以可以省略掉prepare阶段。也就是所谓的，领导者处于稳定状态时，省略掉准备阶段。
大大减少了消息的交互，退化为相当于单纯的主从节点数据通信交互。
Leader的本质就是我不要你们不断地商量，我只需要指定一个即可。毕竟很多场景下，比如选主，是谁都不重要，选出来最重要。
也就是不关心具体的值，只关心尽快达成一致。
!(data/attachment/forum/202206/16/141330jha7st9soow8772i.png?imageMogr2/auto-orient/strip%7CimageView2/2/w/300 "common_log.png")
`转载务必注明出处：程序员潇然，疯狂的字节X，https://crazybytex.com/thread-240-1-1.html `
页:
[1]