Paxos分布式系统共识算法？我愿称其为点歌算法…

古城微笑少年丶 2024-03-30 09:01 75阅读 0赞

分布式系统共识算法Paxos相信大家都不陌生，它被称为最难理解的算法不是没有道理的，首先，它的发表之路就充满了坎坷。

1990年，莱斯利·兰伯特大佬写了一篇论文，举了一个城邦选举的例子来介绍Paxos算法，然而大佬的幽默感并未得到审稿人的认可，论文未发表成功…

1998年，兰伯特重新发表论文《The Part-Time Parliament》描述算法，然而众多学者并不买账，直呼看不懂…

2001年，兰伯特对算法的描述进行简化，再次发表 《Paxos Made Simple》，这次Paxos成为了世界公认最优秀的分布式系统共识算法…

![6f8c512d5adb42eed49d4ebd1a95f608.jpeg][]

其实说白了，Paxos算法要解决的问题是一个分布式系统如何就某个值决议达成一致。比如说，一组进程现在正在提议某个数据的值，需要通过消息传递的方式使这个值达成一致，也就是最终仅能有一个值被选定。

但毕竟是大佬写出来的东西，且不说逻辑推理部分，就算单拎出来论文中对两个核心阶段的描述来说，我等凡人理解起来也还是有些困难。

不信？那就让英语六级的我先来简单地翻译一下。

![6bbed360655e1ce9c99fb50ec92c4936.jpeg][]

#### 阶段1 ####

a、提案者选择一个提案号`n`，发送一个提案号为`n`的`prepare`请求给大多数接受者。

b、如果一个接受者收到的编号为`n`的`prepare`请求，并且编号比它已经响应过的任何`prepare`请求的编号都大，那它就回应这个请求，承诺不再接受任何编号小于`n`的提案，并回复它已经接受的编号最大的提案（如果存在的话）。

#### 阶段2 ####

a、如果提案者收到大多数接受者关于它编号为`n`的`prepare`请求的回应，它就给这些接受者发送一个编号为`n`，值为`v`的`accept`请求，`v`是收到的回应中编号最大的提案值。如果之前不存在任何一个提案的回复时，那么`v`可以是任意值，也就是可以由自己指定。

b、接受者收到编号为`n`的`accept`请求时，只要它还没有响应编号比`n`更高的`prepare`请求，那么它将接受该提案。

![ce0f30253cd226058ec9a856880d6278.jpeg][]

是不是还看不懂？那就对了，下面我们通过一个简单的例子来描述这个过程。

记得小时候，有不少广播电台可以通过电话点歌，打电话给话务员告诉她你要点的歌，接下来就会播放。当然了，这个过程不是免费的，肯定有不少小伙伴在月末父母交话费的时候，惨遭过社会的毒打。

既然是电台热线，那么肯定不只有一个话务员了，我们假定这个电台同时存在3个话务员，并且她们之间是相互没有交流的，那么当短时间内打进来很多电话时，要怎么决定放哪首歌呢？

![c1385bfe5a3bd9694fb0e8cffd8e1303.png][]

首先，话务员之间遵从少数服从多数，那么为了获得更多话务员的支持，你可以不断给更多的话务员打电话。

其次，前面我们说过，这个过程是收费的，假定存在一条潜规则，电台会更偏向于接受出价高的人的点歌请求，那么也就好办了，你可以使了劲地加钱。

在这种环境下，听众想要点歌成功的话，就得靠上面两个办法。

这时，第一个听众打进来电话了，在第一个阶段听众只能进行报价，还不能提出自己想要听什么歌，这个报价就可以理解为算法中的编号`n`。

![9ba43c6aec695b56d0129a6812a9a30b.png][]

因为听众1是第一个打进热线电话的，在他之前还不存在任何报价，所以这里话务员们会无条件地先接受第一个听众的报价并记录下来，然后返回给听众1一个回复信息。

在回复的信息中，话务员不但需要告诉听众他的报价目前最高，已经被认可了，还要说明之前没有接受过其他任何听众的点歌请求。

![8368ebc7f9daae43ee639798f8f1a346.png][]

这时候听众1一看，自己已经获得了超过半数以上的话务员的认可了，那么进入阶段2，告诉话务员自己想要听什么歌曲。当然，在这个过程中，还得顺带着告诉话务员自己在上一阶段中的报价是多少。

于是，听众1再次打进热线，先单独向话务员2发起了选歌提议。

![74ab385bef6ef50ce7faed897acca8b1.png][]

在收到听众1的点歌请求后，话务员2看到听众1在请求中携带的之前报价是1块，满足大于等于自己记录的最大报价这一条件，于是果断接受听众1的点歌请求。

在接受点歌请求后，话务员2要记录的东西又要增加了，她不但要记住已接受的请求的报价金额，还要记住已接受请求的点播歌曲。然后给听众1一个回复，表示我已经接受了你的点歌请求。

![8c8e569320a22803ba470d0396cf06fe.png][]

当然了，在听众1努力点歌的时候，其他听众也不会闲着对不对？

听众2虽然打进电话晚了点，但是直接发动钞能力，把自己的报价提升到了两块，来和话务员们进行通话。

![48f4fc6c56493965e79aa33bcfb7b351.png][]

由于两块钱的报价高于本地记录的最高报价，所以话务员1和话务员2都会认可这个报价，所以她们会先把本地的最高报价值更新为两块。

但是接下来，由于本地记录的信息有所不同，所以她们将会给出不同的答复。

![3ba73c743fee9c6e7e732cac19260ea1.png][]

如果这时候，再来一个听众3打进电话，并且尝试以两块或以下的价格进行报价给前两个话务员的话，那么他的报价不会得到话务员的认可。

这是因为我们前面说过了，话务员们都遵循拜金主义这一潜规则，所以她们不会接受比已记录的最高报价还要低的报价。

![ccbdaa0ba9fd5a4e20447315f24a953a.png][]

在拒绝了听众3之后，我们再回到前面的两位听众这边。

接下来，我们根据听众1和2谁先打进电话，把时间线划分为两个平行宇宙。

### 平行宇宙1 ###

在平行宇宙1这条时间线里，我们假设听众1先打进电话。

这时，仍然只有话务员2接受了听众1的点歌请求，于是听众1继续向其他话务员拨打电话，告诉她们自己要听的歌。

![ba216d1cb95747eaeadce4cd6303dd6b.png][]

在话务员3这里，她记录的最高报价还是听众1之前的1块，所以没有意外，话务员3会接受听众1的点歌请求，并更新本地的记录信息。

但是话务员1这就不一样了，她所认可的报价已经涨到了2，所以旧的1块钱报价已经不能在她这里点歌了，因此话务员1会拒绝听众1的点歌请求。

![527af21ccf7b7a9e80aae2f0379aac54.png][]

尽管请求没有得到话务员1的接受，但是前面我们说了，话务员之间要遵循少数服从多数的原则，听众1的点歌请求已经被半数以上话务员接受，那么听众1确认自己点的这首《东风破》已被选定。

### 平行宇宙2 ###

让我们回到平行宇宙的分叉点，先回顾一下前情，这时听众2已经向话务员1和话务员2发出过报价，并从话务员2那里得知她已经以1块钱的报价接受了《东风破》这首歌的提案。

那么在这条时间线中，我们让听众2先打给1、2号话务员。

听众2这时心里会想，我们杰迷们都是有素质的人，尽管我之前想听的是《简单爱》，但听一下《东风破》貌似也挺不错，那么我干脆支持听众1的选择吧。

于是，报价已被认可的他再次拿起电话打给两位话务员，发起点歌请求。

![13b6c720e67cfd323d0be7072eab7df2.png][]

话务员1和话务员2再次比较听众2这次携带的之前报价，均大于等于本地记录的最高报价，所以接受他的点歌请求。在更新本地记录的信息后，回复信息给听众2。

![0e2eee7ff78713d146165c8b51b28c6e.png][]

于是，听众2的点歌请求也获得了半数以上话务员的承认，那么听众2确认自己点的歌被选定。

看到这里，是不是似乎感觉世界线产生了收束，难道之后的每一种结果都是《东风破》将被选定？

其实，Paxos算法中最精彩的部分在于它更像是一场博弈，棋局中的每一步，都可能影响最终的结果。

### 平行宇宙β ###

让我们把分叉点上的时间，再往前多回溯一点，回到下面这个时间点的状态，这时话务员2刚接受了听众1的点歌请求，而听众2还没有开始打热线电话。

![7ee065e73f9a03450482c36a5fdc0260.png][]

这次，我们站在上帝视角，让听众2改变一下选择，既然话务员2已经被别人收买了，那么干脆避其锋芒，直接向话务员1、3报价。

![2c47a63f964f63dcb054a2d6b0b65ea2.png][]

可想而知，听众2的报价会被两位话务员都认可。

![6c11e2eb72eb0ffb330bb8e55e705043.png][]

在收到了半数以上话务员的报价认可后，听众2先向话务员1发起点歌请求。

![f4bf7832c07529290297cfca2bf7904b.png][]

话务员1比对一下报价，嗯，没有问题，更新本地的记录，接受他的点歌请求。

![f2f5d788c6f1eec446689e16611b790f.png][]

讲道理，现在的形势对听众2真的是一片大好，只要再打个电话给话务员3，就能够成功点歌了。

但是这个节骨眼上，听众2的室友喊他了，说：听歌多没意思，咱们一起来打一局刀塔吧。

听众2一想，没毛病，那我先不点歌了。

而这时，听众1回过神来了，他在之前报价阶段可是获得过半数以上的认可的，于是他带着之前被认可的报价打电话进来点歌。

![a0180407d2d695fcbb61443d3841375e.png][]

可是在两位话务员那里，记录的最高报价已经升到了两块了，于是听众1的点歌请求会被拒绝。

![4e1d3fb9f9079544e7593ca9ed128245.png][]

到这，我们梳理一下，听众1的点歌请求得到了1个接受、2个拒绝，也就是说他的提议没有被过半数以上的话务员接受。

无奈，听众1只能回到第一阶段，从报价开始再重头走一遍流程。并且这次，他把报价提升到了3块。

![8092322767a6efdc75011ba0227f27d6.png][]

三位话务员收到新的报价请求后，都会表示认可，并且返回自己本地记录的信息。

![0e54646aa86760faf4ce40ec8a28699c.png][]

听众1这一次收到的三条报价认可中，有两条携带了之前被接受的点歌信息。那么新问题来了，他应该选哪一首歌曲作为自己接下来要点播的歌曲呢？

在这里，听众要遵循的规则其实和话务员一致，他需要在这些返回的报价及歌曲信息中，选择最高报价的歌曲，作为自己的接下来选歌的依据，因此他最终会选择《简单爱》。

![5bbd6c6677cd8732ab4ffc8cee7c0895.png][]

最终，在没有其他听众中途打进电话干扰的情况下，三位话务员都会接受听众1的点歌请求。

最终，听众1的点歌请求收到超过半数话务员的接受，于是他确认《简单爱》这首歌会被选中。

### 最后 ###

前面提到过，Paxos算法中的选举过程就像是一场博弈，场上局势瞬息万变。

回顾一下上面3条不同的时间线，打进电话顺序的不同、选择的话务员不同，都可能导致最终产生不同的结果。

而Paxos算法本身，并不关注最终选择的是哪一个结果，它关注的是无论如何，在最后一定要能够达成一个共识。

当然了，也有可能遇到下面这种无法解决的情况…

![ea1c6a0928528d6ae27a0b1922e45985.png][]

![360acd7a66119ee87d7a1eec10956565.png][]

在这种情况下，可能会有两个听众交替报价成功，却提议歌曲失败，形成一个**活锁**的局面。如果这样下去，有可能一整天下来，一首歌曲都没有被最终选取成功。

所以在某些情况下，需要选取一个**主提案者**，只有主提案者才能和过半的接受者进行通信提出提案。

说白了，也就是我们常说的话事人。

![6159d0d6d5241ca988b594ad6f215b97.jpeg][]

那么，我们最后再做一个总结，其实在我看来，Paxos算法的关键，就在于后者要认同前者，来避免无休止的争端。

本文也只是对决议部分的两阶段通过示例进行了说明，并忽略了算法中另一个角色**学习者**的内容，如果有兴趣的话，大家不妨去看看论文原文。

毕竟兰伯特大佬都说了：

![69ee3d81707d885c7ddaa097f21256ab.png][]

> 论文原文：
> 
> http://lamport.azurewebsites.net/pubs/paxos-simple.pdf

![2f9c2353d971132fc5be500b78cac8a8.jpeg][]

[6f8c512d5adb42eed49d4ebd1a95f608.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/dc723d20cd19492d94ef8317f5e0979b.jpeg
[6bbed360655e1ce9c99fb50ec92c4936.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/916b2296efe9415e929bccc189967ae0.jpeg
[ce0f30253cd226058ec9a856880d6278.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/97f2a50e47b94728a6b92264d1ec7de9.jpeg
[c1385bfe5a3bd9694fb0e8cffd8e1303.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/86e8cb5ec9ed4506b352a1b8a00b415e.png
[9ba43c6aec695b56d0129a6812a9a30b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2e279f0b7f804c788ed62ca2abd505c4.png
[8368ebc7f9daae43ee639798f8f1a346.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/71469c1d1e444597ae8d545c09a3bdac.png
[74ab385bef6ef50ce7faed897acca8b1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/107c68ee6420428f879ff52ac0279c8a.png
[8c8e569320a22803ba470d0396cf06fe.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/39005a17bcf444f2abf7e2301c48531b.png
[48f4fc6c56493965e79aa33bcfb7b351.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f98a29793c4442beb3a37bbe8d922fe2.png
[3ba73c743fee9c6e7e732cac19260ea1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0f1471d03d9b4af7ac0c75484a5456e2.png
[ccbdaa0ba9fd5a4e20447315f24a953a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/f5c683dafc7e43f39fe2073218db9a67.png
[ba216d1cb95747eaeadce4cd6303dd6b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/88263dad8c9b42cba90e080f72f66050.png
[527af21ccf7b7a9e80aae2f0379aac54.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2558a622244645159b6140b5b0f9d20c.png
[13b6c720e67cfd323d0be7072eab7df2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9be2b680c6744f8aaa7067e330d3a6dd.png
[0e2eee7ff78713d146165c8b51b28c6e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/2b559127199b45b38d760745ba19544e.png
[7ee065e73f9a03450482c36a5fdc0260.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/72714b38f330461aad2984e841d56f02.png
[2c47a63f964f63dcb054a2d6b0b65ea2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/575f6a02b1374b649593c7e226c919f2.png
[6c11e2eb72eb0ffb330bb8e55e705043.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/e51e0580895f448aaf7d778d69d1edc5.png
[f4bf7832c07529290297cfca2bf7904b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/b196172e75bb4637b3cbd03d70b013c2.png
[f2f5d788c6f1eec446689e16611b790f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a9c864c29bfd48ba89ff366e022f833a.png
[a0180407d2d695fcbb61443d3841375e.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/646a253fa30849d5b14fe9b28ca7c297.png
[4e1d3fb9f9079544e7593ca9ed128245.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/98fbcd59d32147b0bbb5921bee08fc18.png
[8092322767a6efdc75011ba0227f27d6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/30143364a6ea4ad7a105ea5f6e39c4f3.png
[0e54646aa86760faf4ce40ec8a28699c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/842dc266d4b046a481ca72a005204eb1.png
[5bbd6c6677cd8732ab4ffc8cee7c0895.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/474eeb8beb7849c9b330c343c469070b.png
[ea1c6a0928528d6ae27a0b1922e45985.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/a58db3e19d454caf93304b93b54a45fb.png
[360acd7a66119ee87d7a1eec10956565.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/403cc3e7b271466da8bc7695b94811f5.png
[6159d0d6d5241ca988b594ad6f215b97.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/9010082240f04244ba403498da5c4908.jpeg
[69ee3d81707d885c7ddaa097f21256ab.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/521f9914459d4accb4630c40475b33d7.png
[2f9c2353d971132fc5be500b78cac8a8.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/30/0c9bd9c34f074864948a132f616c1d53.jpeg