06 | Paxos算法（二）：Multi-Paxos不是一个算法，而是统称

Feb 24, 2020

06 | Paxos算法（二）：Multi-Paxos不是一个算法，而是统称-极客时间



下载APP





关闭

讲堂部落提薪训练营云原生训练营架构实战营企业版极客商城兑换中心 App下载浏览器插件

渠道合作

推荐作者

06 | Paxos算法（二）：Multi-Paxos不是一个算法，而是统称

2020-02-24 韩健来自北京

《分布式协议与算法实战》

课程介绍



讲述：于航

时长10:08大小8.12M



你好，我是韩健。
经过上节课的学习，你应该知道，Basic Paxos 只能就单个值（Value）达成共识，一旦遇到为一系列的值实现共识的时候，它就不管用了。虽然兰伯特提到可以通过多次执行 Basic Paxos 实例（比如每接收到一个值时，就执行一次 Basic Paxos 算法）实现一系列值的共识。但是，很多同学读完论文后，应该还是两眼摸黑，虽然每个英文单词都能读懂，但还是不理解兰伯特提到的 Multi-Paxos，为什么 Multi-Paxos 这么难理解呢？
在我看来，兰伯特并没有把 Multi-Paxos 讲清楚，只是介绍了大概的思想，缺少算法过程的细节和编程所必须的细节（比如缺少选举领导者的细节）。这也就导致每个人实现的 Multi-Paxos 都不一样。不过从本质上看，大家都是在兰伯特提到的 Multi-Paxos 思想上补充细节，设计自己的 Multi-Paxos 算法，然后实现它（比如 Chubby 的 Multi-Paxos 实现、Raft 算法等）。
所以在这里，我补充一下：兰伯特提到的 Multi-Paxos 是一种思想，不是算法。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列值的共识的算法（比如 Chubby 的 Multi-Paxos 实现、Raft 算法等）。 这一点尤其需要你注意。
为了帮你掌握 Multi-Paxos 思想，我会先带你了解，对于 Multi-Paxos 兰伯特是如何思考的，也就是说，如何解决 Basic Paxos 的痛点问题；然后我再以 Chubby 的 Multi-Paxos 实现为例，具体讲解一下。为啥选它呢？因为 Chubby 的 Multi-Paxos 实现，代表了 Multi-Paxos 思想在生产环境中的真正落地，它将一种思想变成了代码实现。
兰伯特关于 Multi-Paxos 的思考熟悉 Basic Paxos 的同学（可以回顾一下05 讲）可能还记得，Basic Paxos 是通过二阶段提交来达成共识的。在第一阶段，也就是准备阶段，接收到大多数准备响应的提议者，才能发起接受请求进入第二阶段（也就是接受阶段）：
而如果我们直接通过多次执行 Basic Paxos 实例，来实现一系列值的共识，就会存在这样几个问题：
如果多个提议者同时提交提案，可能出现因为提案编号冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商。你想象一下，一个 5 节点的集群，如果 3 个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应（比如 1 个提议者接收到 1 个准备响应，另外 2 个提议者分别接收到 2 个准备响应）而准备失败，需要重新协商。
2 轮 RPC 通讯（准备阶段和接受阶段）往返消息多、耗性能、延迟大。你要知道，分布式系统的运行是建立在 RPC 通讯的基础之上的，因此，延迟一直是分布式系统的痛点，是需要我们在开发分布式系统时认真考虑和优化的。
那么如何解决上面的 2 个问题呢？可以通过引入领导者和优化 Basic Paxos 执行来解决，咱们首先聊一聊领导者。
领导者（Leader）我们可以通过引入领导者节点，也就是说，领导者节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了：
在这里，我补充一点：在论文中，兰伯特没有说如何选举领导者，需要我们在实现 Multi-Paxos 算法的时候自己实现。 比如在 Chubby 中，主节点（也就是领导者节点）是通过执行 Basic Paxos 算法，进行投票选举产生的。
那么，如何解决第二个问题，也就是如何优化 Basic Paxos 执行呢？
优化 Basic Paxos 执行我们可以采用“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，优化 Basic Paxos 执行。也就是说，领导者节点上，序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。这时，领导者在提交命令时，可以省掉准备阶段，直接进入到接受阶段：
你看，和重复执行 Basic Paxos 相比，Multi-Paxos 引入领导者节点之后，因为只有领导者节点一个提议者，只有它说了算，所以就不存在提案冲突。另外，当主节点处于稳定状态时，就省掉准备阶段，直接进入接受阶段，所以在很大程度上减少了往返的消息数，提升了性能，降低了延迟。
讲到这儿，你可能会问了：在实际系统中，该如何实现 Multi-Paxos 呢？接下来，我以 Chubby 的 Multi-Paxos 实现为例，具体讲解一下。
Chubby 的 Multi-Paxos 实现既然兰伯特只是大概的介绍了 Multi-Paxos 思想，那么 Chubby 是如何补充细节，实现 Multi-Paxos 算法的呢？
首先，它通过引入主节点，实现了兰伯特提到的领导者（Leader）节点的特性。也就是说，主节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了。
另外，在 Chubby 中，主节点是通过执行 Basic Paxos 算法，进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期（Lease）。比如在实际场景中，几天内都是同一个节点作为主节点。如果主节点故障了，那么其他的节点又会投票选举出新的主节点，也就是说主节点是一直存在的，而且是唯一的。
其次，在 Chubby 中实现了兰伯特提到的，“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制。
最后，在 Chubby 中，实现了成员变更（Group membership），以此保证节点变更的时候集群的平稳运行。
最后，我想补充一点：在 Chubby 中，为了实现了强一致性，读操作也只能在主节点上执行。 也就是说，只要数据写入成功，之后所有的客户端读到的数据都是一致的。具体的过程，就是下面的样子。
所有的读请求和写请求都由主节点来处理。当主节点从客户端接收到写请求后，作为提议者，执行 Basic Paxos 实例，将数据发送给所有的节点，并且在大多数的服务器接受了这个写请求之后，再响应给客户端成功：
当主节点接收到读请求后，处理就比较简单了，主节点只需要查询本地数据，然后返回给客户端就可以了：
Chubby 的 Multi-Paxos 实现，尽管是一个闭源的实现，但这是 Multi-Paxos 思想在实际场景中的真正落地，Chubby 团队不仅编程实现了理论，还探索了如何补充细节。其中的思考和设计非常具有参考价值，不仅能帮助我们理解 Multi-Paxos 思想，还能帮助我们理解其他的 Multi-Paxos 算法（比如 Raft 算法）。
内容小结本节课我主要带你了解了 Basic Paxos 的局限，以及 Chubby 的 Multi-Paxos 实现。我希望你明确的重点如下：
兰伯特提到的 Multi-Paxos 是一种思想，不是算法，而且还缺少算法过程的细节和编程所必须的细节，比如如何选举领导者等，这也就导致了每个人实现的 Multi-Paxos 都不一样。而 Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos 实例实现一系列数据的共识的算法（比如 Chubby 的 Multi-Paxos 实现、Raft 算法等）。
Chubby 实现了主节点（也就是兰伯特提到的领导者），也实现了兰伯特提到的 “当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段” 这个优化机制，省掉 Basic Paxos 的准备阶段，提升了数据的提交效率，但是所有写请求都在主节点处理，限制了集群处理写请求的并发能力，约等于单机。
因为在 Chubby 的 Multi-Paxos 实现中，也约定了“大多数原则”，也就是说，只要大多数节点正常运行时，集群就能正常工作，所以 Chubby 能容错（n - 1）/2 个节点的故障。
本质上而言，“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制，是通过减少非必须的协商步骤来提升性能的。这种方法非常常用，也很有效。比如，Google 设计的 QUIC 协议，是通过减少 TCP、TLS 的协商步骤，优化 HTTPS 性能。我希望你能掌握这种性能优化思路，后续在需要时，可以通过减少非必须的步骤，优化系统性能。
最后，我想说的是，我个人比较喜欢 Paxos 算法（兰伯特的 Basic Paxos 和 Multi-Paxos），虽然 Multi-Paxos 缺失算法细节，但这反而给我们提供了思考空间，让我们可以反复思考和考据缺失的细节，比如在 Multi-Paxos 中到底需不需要选举领导者，再比如如何实现提案编号等等。
但我想强调，Basic Paxos 是经过证明的，而 Multi-Paxos 是一种思想，缺失实现算法的必须编程细节，这就导致，Multi-Paxos 的最终算法实现，是建立在一个未经证明的基础之上的，正确性是个问号。
与此同时，实现 Multi-Paxos 算法，最大的挑战是如何证明它是正确的。 比如 Chubby 的作者做了大量的测试，和运行一致性检测脚本，验证和观察系统的健壮性。在实际使用时，我不推荐你设计和实现新的 Multi-Paxos 算法，而是建议优先考虑 Raft 算法，因为 Raft 的正确性是经过证明的。当 Raft 算法不能满足需求时，你再考虑实现和优化 Multi-Paxos 算法。
课堂思考既然，我提了 Chubby 只能在主节点上执行读操作，那么在最后，我给你留了一个思考题，这个设计有什么局限呢？欢迎在留言区分享你的看法，与我一同讨论。
最后，感谢你的阅读，如果这篇文章让你有所收获，也欢迎你将它分享给更多的朋友。

分享给需要的人，Ta购买本课程，你将得18元

生成海报并分享

赞 20

提建议

05 | Paxos算法（一）：如何在多个节点间确定某变量的值？

07 | Raft算法（一）：如何选举领导者？

 写留言

精选留言(68)

HuaMax
置顶
2020-02-24
“当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段”这个优化机制。请问，什么样是稳定状态？为什么稳定状态可以省掉准备阶段？
作者回复: 如何理解领导者处于稳定状态？领导者节点上，序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。我来具体说说，准备阶段的意义，是发现接受者节点上，已经通过的提案的值。如果在所有接受者节点上，都没有已经通过的提案了，这时，领导者就可以自己指定提案的值了，那么，准备阶段就没有意义了，也就是可以省掉了。
共 6 条评论
36
每天晒白牙
置顶
2020-02-24
只能在主节点进行读操作，效果相当于单机，对吞吐量和性能有所影响写也是在主节点进行，性能也有问题
作者回复: 加一颗星:)
共 9 条评论
20
Geek_MYMSwen
2020-02-24
Chubby的局限可能在于高读的系统中，如果读请求过大，会导致系统的不可用。另外在系统中如何能够将主节点更替的信息向用户传播也是需要考虑的问题。还有有一种情况我没有想清楚，请各位指点：一个分布式系统中有5个节点，3个在一个机房A(机器编号A1，A2，A3)，2个在另一个机房B（机器编号B1，B2）。 1）如果节点A1的机架网络发生故障，导致A1与其他节点通信受阻，那么A1节点将会执行什么操作呢？通讯恢复以后A1节点如何进行数据同步呢？同样在A1无法通讯后出现集群有偶数节点，选举时会出现怎样的情况？ 2）如果主节点为B1，A机房与B机房间通讯产生故障，A机房和B机房的节点将分别执行怎样的操作呢？
展开
作者回复: 加一颗星:) 1. A1节点，可以联系其他节点，联系领导者，获取最新的集群节点状态信息和领导者信息，拒绝写操作的执行。 2. 如果，同步数据，需要在代码实现设计实现，比如，可以请求领导者节点，把新通过的提案，都同步过来，更具体的实现，可以参考Raft的日志复制。 3. 偶数节点不是问题，只要有大多数节点在稳定运行，就可以了。 4. 节点B1，在leader leasing过后，要主动退位，并拒绝执行写操作，A机房的3个节点，将选举出新的领导者。
共 6 条评论
18
小石头
2020-03-22
如果多个提议者同时提交提案，可能出现因为提案冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商。你想象一下，一个 5 节点的集群，如果 3 个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应（比如 1 个提议者接收到 1 个准备响应，另外 2 个提议者分别接收到 2 个准备响应）而准备失败，需要重新协商。这第一个问题理解不了，按上篇讲的，最大提议号的提议者不是会收到所有的准备响应么？
展开
作者回复: 加一颗星:)，这里指的是提案编号相同、选票瓜分的情况。
共 5 条评论
9
zjm_tmac
2020-02-25
leader怎么确定acceptor的总数呢？集群是允许扩容的吗
作者回复: 怎么确定acceptor总数，涉及代码实现和成员变更；扩容涉及到成员变更。首先，使用什么数据结构来保存acceptor总数，这属于编程实现，不属于算法了，绝大多数算法都不会约定的这么细的。其次，Multi-Paxos，只是一种思想，缺少算法细节和编程所必须的细节，比如，成员变更，在Multi-Paxos中，提了下，可以把服务器配置作为指令，通过状态机提交，等等。但是，如果学习了09讲后，你就会发现，真正实现起来，比这个要复杂很多，比如Raft设计了2种成员变更方法，一种难以实现，一种容易实现，但在16年时，爆出了一个算法bug，虽然很快就修复了，但也反映了成员变更比较复杂，不是三言两语能讲清楚的。另外，其实，学习Multi-Paxos的最好的方式，是先理解Raft，再回过头来，学习Multi-Paxos。如果在学习Multi-Paxos中遇到不理解的，可以在学习完Raft后，再回头来研究学习。
7
snakorse
2020-03-21
找到一篇微信后台团队对PhxPasox的讲解，感觉是对multi-paxos非常好的补充，推荐一下https://mp.weixin.qq.com/s?__biz=MzI4NDMyNTU2Mw==&mid=2247483695&idx=1&sn=91ea422913fc62579e020e941d1d059e&chksm=ebfc62fbdc8bebed551c2a041bb37bcaab836c4b2ca8e575d418f1e24459459c1c16faf70d06
作者回复: Paxos是共识算法，不是一致性协议，consensus不等于consistency。
共 5 条评论
6
eason2017
2020-04-01
集群，分布式的意义是提供更大的吞吐量，和并发，这样的操作无疑是掩耳盗铃
作者回复: 有些场景需要的是强一致性、故障容错等，场景决定系统的形态。
共 2 条评论
5
阿卡牛
2020-03-24
主节点只一个？那存在单点故障的问题
作者回复: 有节点故障容错能力的，当主节点故障时，会选举出新的主节点，保证集群服务的可用。
5
陈
2020-02-28
只能在主节点读取，存在单机性能和容错问题。
作者回复: 加一颗星:)，性能瓶颈是痛点，共识算法具有容错能力，领导者模型的共识算法，在故障、选举期间，无法执行写操作。
5
约书亚
2020-02-24
本来想问个问题，看到思考题提到了。从raft和zab的实现来看，一致性读操作的处理和写操作是类似的，不从本地读，而是也要发请求到所有节点，得到大多数节点的响应才行。我了解到的有的实现是领导者发送一个空操作给所有节点。这样做的原因不光是考虑吞吐量的问题，而是读本地是满足不了强一致性的，因为自以为的leader未必是真的leader，此时可能另外的节点已经自己组成一个小团队，选出一个新leader，这个变量也可能都更新好几次了。只有和大多数节点交互一次才能知道自己当前还是不是leader。有个问题，兰伯特提到的 “当领导者处于稳定状态时...”这个稳定状态是什么意思呢？在领导者是谁这个问题上，达成大多数节点的一致?
展开
作者回复: 领导者节点上，序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，领导者可以独立指定提案中的值。我来具体说说，准备阶段的意义，是发现接受者节点上，已经通过的提案的值。如果在所有接受者节点上，都没有已经通过的提案了，这时，领导者就可以自己指定提案的值了，那么，准备阶段就没有意义了，也就是可以省掉了。
5
W.G.Ma
2020-03-26
如果多个提议者同时提交提案，可能出现因为提案冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商——————为什么？三个提议者最大编号的的总能收到准备提议的回复
作者回复: 加一颗星:)，这里指的是提案编号相同、“选票”被瓜分的情况。另外，编号最大的提议者，虽然能收到大多数准备响应，但也可能因为各提议者不断递增提案编号和重试，出现始终没有提案被选定的情况。
共 5 条评论
4
cp★钊
2020-03-10
咨询下，对于写请求，主节会发接受请求发给其余节点，只有其余节点过半操作成功才能返回成功给客户端。这里有个问题是，如果操作没有过半成功，比如6台机器只有两个写成功了，那主节点返回失败给客户端后，是不是还得考虑怎么让那两个写成功的回滚操作？大概可以怎么实现
作者回复: 加一颗星:)，不需要回滚，只有2个节点写成功了，这时就会有空洞日志，如何处理，与工程实现有关，最终，指令被覆盖，或者指令提交成功，并因客户端重试，导致指令重复提交，那么，因为有状态机，只要实现操作的冥等性，就可以了。
共 2 条评论
4
笑若海
2020-02-28
Chubby是如何解决单机leader的性能的：Chubby的角色定位是提供分布式锁服务，帮助其他应用达成分布式共识，内部存储的都是其他服务如GFS、MapReduce运行所需的元数据信息，数据结构采用类似linux文件系统的结构，每一级目录代表一定级别的锁。按照论文里面测试结果，97%（也可能是99%，记不太清了）以上的服务请求数据大小不超过1k，同时锁是有租约的，租约到期前不需要再发请求可以一直使用，快到期时发请求续租。论文中特别强调不要在Chubby上存储太大数据，有应用因存储1M大小的元数据而性能极差。建议大家有空看看Chubby的论文。另外论文提到了状态机，对状态机的有啥用，为了解决什么问题一直没想明白。
展开
作者回复: 加一颗星:)，可以这么理解，状态机是一个功能模块，用来处理一系列请求，最大的特点就是确定性，也就是说，对于相同的输入，不管重复运行多少次，最终的内部状态和输出都是相同的。基于状态机，我们可以通过提议新的指令，比如“SET X = 7”，来实现修改X的值的目的。
4
sai
2020-02-24
您好，假设有3台节点 A, B, C. leader 最开始是A, 依次执行写入操作[set x=1, set y=2, set z=3], 假设B和C都有可能超时，根据paxos只需要大多数写入成功就算执行成功的原则，当前状态可能为A:[x:1, y:2, z:3], B:[x:1, z:3], C: [y2, z3]。如果这个时候主节点A宕机，如何重新选择主节点并恢复数据呢？
作者回复: 加一颗星:)，如何选举领导者，需要我们自己实现，比如，我们可以通过执行Basic Paxos来选举个新的领导者，比如节点B。当节点B当选领导者后，需要先作为学习者，了解目前已被选定的值，这时它执行 Basic Paxos 的准备阶段，就会发现之前选定的值（比如 [y:2]）。
4
Sam
2020-03-05
老师，能介绍一些关于这方面的书单吗？
作者回复: 没有看到特别合适的书，多读论文，多研究源码，多实战吧。学习中遇到问题，欢迎留言，咱们一起讨论:)
3
Dovelol
2020-02-24
老师好，想问下，如果只有领导者可以发起提案，那么这是不是就退化为串行操作了，这样的话性能怎么保证呢，实际应用中是怎么解决的？我觉得最后问题， Chubby只能在主节点上执行读操作，在读请求量非常大的情况下，也是会遇到瓶颈的，还有就是单点问题，主节点挂了，在选出主节点之前就不能提供服务了对吧，该如果解决这类问题呢？
作者回复: 加一颗星:)，问题1，可以通过其他方式来提升性能，比如升级硬件、分集群；问题2：一般而言，领导者选举是很快的，客户端支持失败重试，就可以了。
共 4 条评论
3
侧耳倾听
2020-04-14
原文：一个 5 节点的集群，如果 3 个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应（比如 1 个提议者接收到 1 个准备响应，另外 2 个提议者分别接收到 2 个准备响应）而准备失败，需要重新协商。问题：对于接受准备响应的数量不太理解。前一章老师说过，提议者也是接受者。那么当三个节点中的一个提议者提案时，其他两个提议者是当作当前提议者的接受者来看待吗？这样四个接受者的前提下，对于同一个KV的提案，我考虑了几种情况都能得到最大提案编号达成共识的结果。不知道我理解的有无问题，麻烦老师指点。如果上述方案正确的前提下，不需要引入领导者增加了系统可用性，但是内部请求数依然比较大
展开
作者回复: 加一颗星:)，提案编号相同，在这种情况下，会出现选票被瓜分的情况。另外，当提案编号不同时，也可能因为多个提议者不断尝试和递增编号，而始终无法提交新提案的情况。当然除了领导者，还有办法能解决这些问题，毕竟解决一个问题，有多种办法。在我看来，领导者能极大简化算法设计，这个理念很常用，比如，在早期设计HA cluster时，我们也设计了领导者选举。
共 2 条评论
2
密码123456
2020-03-12
还以为会比上一节理解起来难。原来就处理2问题。一个是没有提议者没有大多数响应，还有一个是通信过多。我这里理解有一个问题。如果对领导节点选择，使用了base paxos算法。假设有5个机器。3个提议者，没出现大多数怎么办？
作者回复: 加一颗星:)，需要重新选举，可以通过引入随机超时时间等机制，来减少出现多个提议者、没有“大多数”的情况。
2
波波
2020-03-06
老师我有个疑问，如果主节点在发送接收请求给其他节点时，刚好第一个节点接受并返回了，主节点想发送给其他节点时挂掉了，这时会重新选举leader，但是之后怎么保证其他节点数据的一致性啊？
作者回复: 加一颗星:)，发生领导者切换时，未达成共识的数据，可能会丢失，也可能最终被提交；达成共识的数据，是肯定不会变的。具体的推导，我后面以图例的形式补充下吧。
2
小晏子
2020-02-24
Chubby 只能在主节点上执行读写操作, 那么这个主节点就是热点，所有的请求都要经过它，显而易见它就是系统的瓶颈，影响系统的并发度，而且在并发时，写请求会block读请求，影响整个系统的QPS。
作者回复: 加一颗星:)
2

