这篇文章主要记录自己对Paxos/Raft的一点不成体系的理解,不是写给别人看的,所以不会有专门的图表。起因是学习它们的过程比较痛苦,啃过论文也看了不少别人的理解,但问题始终没有解决:1. 想编程实现它们”似乎”比较简单;2. 想知道它们为什么正确却很困难;3. 第2点导致了第1点”实际”并不简单。网上的文章大部分是基于”抢锁”或者”选主”这类角度来剖析的,虽然方便鸟瞰其大致过程,但是不利于理解其正确性。

Basic Paxos

先说Basic Paxos,它的第一阶段(Prepare)如果理解成”抢锁”或者”选主”,那么你会发现实际上同时可能存在多个提案者抢到了锁或者当上了领导。既然可能同时存在多个,那这个”锁”或者”主”的抽象意义其实也就没那么大。从上帝视角来看确实最多只有一个提案者”真正”抢到了锁或者当上了领导,其他的只是由于消息滞后自以为是。但是即使这样我们依然很难往后走,推导出算法为什么是正确的。

举一个浅显的例子:A以提案ID p1 抢到了”锁”,旋即执行第二阶段(Accept)将值决议成了 v1;此时B以提案ID p2 抢到了锁,旋即执行第二阶段(Accept)将值重新决议成了 v2。如果只从”锁”的角度看这个过程似乎没有问题,但实际上并不会发生这种情况,最关键的地方其实正是这句”但实际上并不会发生这种情况”。

其实Lamport在《Paxos Made Simple》里面的证明思路反而是更好理解的,但我需要换种方式来陈述:

  1. 如果一系列交互过程中曾经产生过共识(不管是一次还是多次),那么这些共识里面肯定存在一个最小的提案ID和对应的提案值,不妨记为(A, V),也称这次提案为提案A;
  2. 我们怎么能保证共识不变呢,一个最直观的想法就是考虑所有参与了第二阶段(Accept)的提案,找出提案ID恰好比A大的那一个,不妨记为B,同时也称这次提案为提案B。如果算法能保证提案B选用的提案值也是V,那么根据归纳法,1推2、2推3……就能一直推下去了;
  3. 因此如果我们把第二阶段(Accept)理解为”写”的话,在”写”之前还需要一次”读”,需要让提案B”读”到提案A的提案值V(注意提案B”读”到它的时候有可能还并没有形成决议,但这不影响最终结论);
  4. 根据反证法可以知道第3点是必然的:假如提案B”读”不到提案A的提案值V,意味着有超过半数的接受者本身还没接受提案A,而且承诺不再接受提案ID小于B的提案,那最后提案A的提案值V一定不会形成决议,和假设矛盾。需要强调一点是这里不要用分类讨论,甲情况乙情况什么的,就是B一定能”读”到提案A的提案值V。

整个思路并不是完全严格的,但是循着这个方向走把边角补齐,就会是一个完整的证明。所以回到最开始的问题,用什么角度来看待第一阶段(Prepare)?我个人觉得用”先读后写”的思路来同时看待第一阶段(Prepare)和第二阶段(Accept)更合理一些。先”读”已经形成的决议值,再用它来”写”。理解这个思路以后其实就会知道并不一定需要像论文里面说的”超过一半”。假设”写”需要的数量是W,它确实需要过半,即 W > N / 2,但是”读”需要的数量R其实并不一定得过半,只需要保证 R + W > N 即可。

Raft

以Basic Paxos的视角来看Raft,就会发现真的没有太大不同,区别只在于Basic Paxos需要决议的是一个单值,所以”读”到决议值以后必需”写”相同的决议值。而Raft呢,只是把这个单值拓展到了日志序列。在这种情况下,我们就把”决议不变”的含义从”数值相等”拓展为”只能追加”,剩下的事情就完全顺理成章了。

Raft的选主实际上就是Basic Paxos的第一阶段(Prepare),所以选主的目的也是相同的:拿到之前已经形成的决议值。还记得Basic Paxos里面是怎么拿到这个值的不,是从所有的Prepare Response里面挑出最大的提案ID对应的提案值。但现在提案值是日志序列了,再全量拷贝必然存在性能问题,所以Raft取巧的地方在于缩小候选范围,只让拥有决议值的节点当选,从而避免了拷贝问题。

同时Raft的日志同步,对应的就是Basic Paxos的第二阶段(Accept),当然这里也需要用拓展的观点来看待,就是Raft里面的Accept实际上是可以一次又一次地追加的,而并不是只能调用一次。

Multi Paxos

想想之前Raft里面比较取巧的点:缩小候选范围,只让拥有决议值的节点当选。这方面Multi Paxos没有取巧,而是选择了直接硬刚:每个节点都有机会当选。但是由于当选的节点可能并不包含完整的决议值(即单机上并不包含全部已经决议好的日志序列),所以它有一个反复调用Basic Paxos的过程来将日志空洞”补齐”。你可以认为,在”补齐”的那一刻,它自己拥有了完整的决议值,它当选了。

最后说说选举

一般讲到Raft和Multi Paxos的资料里面都会提到选举这个概念,但其实这两者都不需要一个真正意义上的”领导”,”领导”只是为了性能而搞出来的工程优化。我生物学忘得差不多了,似乎记得第一颗精子跑去和卵细胞结合以后,会设置屏障尽力阻止后面的精子继续进去。同样在Raft和Multi Paxos里面当一个节点得知自己当选以后,也会通过类似心跳的方式去阻止其他节点获得写入权,然而这只是为了效率,并不是正确性所必须。