vlambda博客
学习文章列表

理解 Paxos(含伪代码)

Google Chubby 的作者 Mike Burrows 说过:There is only one consensus protocol, and that's Paxos.

引言

我们已经详细的阐述了共识问题并介绍了一些共识算法,其中 Paxos 算法是 Leslie Lamport 于 1990 年提出的共识算法,不幸的是采用希腊民主议会的比喻很明显失败了,Lamport 像写小说一样,把一个复杂的数学问题弄成了一篇带有考古色彩的历史小说。根据 Lamport 自己的描述[1],三个审稿者都认为该论文尽管并不重要但还有些意思,只是应该把其中所有 Paxos 相关的故事背景删掉。Lamport 对这些缺乏幽默感的人感到生气,所以他不打算对论文做任何修改。

多年后,两个在 SRC(Systems Research Center,DEC 于 1984 年创立,Lamport 也曾在此工作过)工作的人需要为他们正在构建的分布式系统寻找一些合适算法,而 Paxos 恰恰提供了他们想要的。Lamport 就将论文发给他们,他们也没觉得该论文有什么问题。

因此,Lamport 觉得论文重新发表的时间到了,"The Part-Time Parliament[2]" 最终在 1998 年公开发表。

可是很多人抱怨这篇论文根本看不懂啊,人们只记住了那个奇怪的故事,而不是 Paxos 算法。Lamport 走到哪都要被人抱怨一通。于是他忍无可忍,2001 年重新发表了一篇关于 Paxos 的论文——"Paxos Made Simple[3]",这次论文中一个公式也没有,摘要也只有一句话:

The Paxos algorithm, when presented in plain English, is very simple.

满满的都是嘲讽!

然而,可能是表述顺序的原因,这篇论文还是非常难以理解,于是人们写了一系列文章来解释这篇论文(重复造论文),以及在工程上如何实现它。

其中,个人认为讲解 Paxos 最好的视频[4]来自于 Raft 算法作者 Diego Ongaro,本文采用 Diego 讲义中的图片来理解 Paxos 算法,也纠正了一个个人认为 Diego 笔误的地方。

术语

基本概念

Proposal Value:提案的值;Proposal Number:提案编号;Proposal:提案 = 提案编号 + 提案的值;Chosen:批准,也叫选定。一旦某个值被 Chosen,后续 Paxos 都必须用该值进行交互。

注:Proposal 有人叫“提议”有人叫“提案”,此处和维基百科里的翻译保持一致,叫“提案”。

角色

Proposer:提案发起者;Acceptor:提案接收者;Learner:提案学习者;

问题描述

为了高可用性,一种常见的设计是用一个 master 节点来写,然后复制到各个 slave 节点。这种解决方法的问题在于,一旦 master 节点故障,整个服务将不可用或者数据不一致。

为了克服单点写入问题,于是有了多数派(Quorum)写,思路就是写入一半以上的节点。即,如果集群中有 N 个节点,客户端需要写入 W >= N/2 + 1 个节点。不需要主节点。这种方法可以容忍最多 (N-1)/2 个节点故障。

但是问题依然存在:每个接收者该如何决定是否接受这次请求的值呢?

如果我们接受第一次收到的值,那么当出现以下情况(Split Votes),则没有出现多数派,没有一个值被 Chosen,算法无法终止,这违反了活性(liveness)。



为了解决 Split Votes 问题,我们允许接受多个不同的值,收到的每一个(every)请求都接受,这时候新的问题出现了,如下,可能不止一个值被 Chosen,这违反了安全性(safety)。


理解 Paxos(含伪代码)


注意,Paxos 强调:

Once a value has been chosen, future proposals must propose the same value.

也就是说,我们讨论的 Basic-Paxos 只会 Chosen 一个值。基于此,就需要一个两阶段(2-phase)协议,对于已经 Chosen 的值,后面的提案也要使用相同的值。

如下图这种情况,S3 直接拒绝 red 值,因为 blue 已经 Chosen,这样就可以保证成功。


理解 Paxos(含伪代码)


这种方式我们需要对提案进行排序。如果你熟悉分布式系统,应该能想到 "Time, Clocks and the Ordering of Events in a Distributed System[5]" 这篇论文,我们不能用时间来判断提案的先后顺序。

Proposal Number

一种简单的方式就是每个请求一个唯一的编号,例如:<seq_id, server_id>,为了排序 seq_id 是自增的;同时为了避免崩溃重启,必须能在本地持久化存储。

Paxos

现在我们终于可以开始描述 Paxos 算法了。

如上所述,Paxos 是一个两阶段算法。我们把第一个阶段叫做准备(Prepare)阶段,第二个阶段叫做接受(Accept)阶段。分别对应两轮 RPC。

第一轮 Prepare RPCs:

请求(也叫 Prepare 阶段):

Proposer 选择一个提案编号 n,向所有的 Acceptor 广播 Prepare(n) 请求。

这里 Prepare(n)不包含提案的值。

伪代码:

send PREPARE(++n)

响应(也叫 PROMISE 阶段):

Acceptor 接收到 Prepare(n) 请求,此时有两种情况:

如果 n 大于之前接受到的所有 Prepare 请求的编号,则返回 Promise() 响应,并承诺将不会接收编号小于 n 的提案。如果有提案被 Chosen 的话,Promise() 响应还应包含前一次提案编号和对应的值。否则(即 n 小于等于 Acceptor 之前收到的最大编号)忽略,但常常会回复一个拒绝响应。

所以,Acceptor 需要持久化存储 max_n、accepted_N 和 accepted_VALUE

伪代码:

if (n > max_n) max_n = n // save highest n we've seen so far if (proposal_accepted == true) // was a proposal already accepted? respond: PROMISE(n, accepted_N, accepted_VALUE) else respond: PROMISE(n)else do not respond (or respond with a "fail" message)

第二轮 Accept RPCs:

请求(也叫 PROPOSE 阶段):

当 Proposer 收到超过半数 Acceptor 的 Promise() 响应后,Proposer 向多数派的 Acceptor 发起 Accept(n, value) 请求并带上提案编号和值。(注:这里讲义的算法流程图是向所有的 Acceptor 发起 Accept() 请求,鄙人认为应该改为向多数派 Acceptor 发起。)

注意:Proposer 不一定是将 Accept() 请求发给有应答的多数派 Acceptors,可以再选另一个多数派 Acceptors 广播 Accept() 请求。

关于值 value 的选择:如果前面的 Promise 响应有返回 accepted_VALUE,那就使用这个值作为 value。如果没有返回 accepted_VALUE,那可以自由决定提案值 value。

伪代码:

did I receive PROMISE responses from a majority of acceptors?if yes do any responses contain accepted values (from other proposals)? if yes val = accepted_VALUE // value from PROMISE message with the highest accepted ID if no val = VALUE // we can use our proposed value send Accept(ID, val) to at least a majority of acceptors

响应(也叫 ACCEPT 阶段):

Acceptor 收到 Accept() 请求,在这期间如果 Acceptor 没有对比 n 更大的编号另行 Promise,则接受该提案。

伪代码:

if (n >= max_n) // is the n the largest I have seen so far? proposal_accepted = true // note that we accepted a proposal accepted_N = n // save the accepted proposal number accepted_VALUE = VALUE // save the accepted proposal data respond: Accepted(N, VALUE) to the proposer and all learnerselse do not respond (or respond with a "fail" message)

一些例子

情况 1:提案已 Chosen

理解 Paxos(含伪代码)


1.S1 收到客户端提案请求 X,于是 S1 向 S1-S3 发起 Prepare(3.1) 请求,PROMISE() 响应返回没有提案被 Chosen2.由于 S1-S3 没有任何提案被 Chosen,S1 继续向 S1-S3 发送 Accept(3.1, X) 请求,提案被成功 Chosen3.在提案被 Chosen 后,S5 收到客户端提案值为 Y 的请求,向 S3-S5 发送 Prepare(4.5) 请求,由于编号 4 > 3 会收到提案值为 X 已经被 Chosen 的 PROMISE() 响应4.于是 S5 将提案值 Y 替换成 X,向 S1-S3 发送 Accept(4.5, X) 请求,提案再次被 Chosen

情况 2:提案未 Chosen,Proposer 可见

理解 Paxos(含伪代码)


情况 2 和情况 1 类似,在 S3 Chosen 了提案后,S5 收到来自 S3 的 PROMISE() 响应包含了已经 Chosen 的提案值 X,所以同样会将提案值替换成 X,最终所有 Acceptor 对 X 达成共识。

注意上面的伪代码:do any responses contain accepted values,也就是说只要有一个 Acceptor 在 Promise() 响应中返回了提案值,就要用它来替换提案值。

情况 3:提案未提交,Proposer 不可见

理解 Paxos(含伪代码)


情况 3 中,提案只被 S1 Chosen,S3 还未 Chosen 该提案,S3-S5 的 Promise() 响应中没有任何提案信息,所以 S5 自行决定提案值为 Y,发送 Accept(4.5, Y) 请求。

由于此时 S3 承诺的提案编号 n 变为了 4 且 4 大于 3,所以 S3 不再接受 S1 后续的 Accept(3.1, X) 请求。提案值 X 被阻止,而提案值 Y 最终被 Chosen。

活锁


如图:当 Proposer 在第一轮 Prepare 发出请求,还没来得及后续的第二轮 Accept 请求,紧接着第二个 Proposer 在第一阶段也发出编号更大的请求。如果这样无穷无尽,Acceptor 始终停留在决定顺序号的过程上,那大家谁也成功不了。

解决活锁最简单的方式就是引入随机超时,这样可以让某个 Proposer 先进行提案,减少一直互相抢占的可能。

结语

Paxos 只从一个或多个值中选择一个值,如果需要重复运行 Paxos 来创建复制状态机,我们称之为 multi-Paxos,但如果每个命令都通过一个Basic Paxos算法实例来达到一致,会产生大量开销。对于 multi-Paxos 可以做一些优化,我们在下篇文章中讨论 Paxos 的变种。

References

[1] Lamport 自己的描述: http://lamport.azurewebsites.net/pubs/pubs.html#lamport-paxos
[2] The Part-Time Parliament: https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf
[3] Paxos Made Simple: https://lamport.azurewebsites.net/pubs/paxos-simple.pdf
[4] 视频: https://www.youtube.com/watch?v=JEpsBg0AO6o
[5] Time, Clocks and the Ordering of Events in a Distributed System: http://lamport.azurewebsites.net/pubs/time-clocks.pdf