Paxos算法概述与推导

原 作者 李兆龙 | 发表于 | 分类于 2018级

文章目录

引言

Paxos是一个经典的分布式共识算法,可以说在很长一段时间内都是分布式共识算法的代名词.在介绍Paxos算法之前我不得不介绍下它的作者,Leslie Lamport,此人是一个神牛,他的成果实在是数不胜数:lamport时间戳,描述了拜占庭问题的解决方法,Paxos算法的提出等等.并在2013年获得了图灵奖,为现代计算机科学领域做出了杰出的奉献.也不说值得学习了,这样的神人实在学习不来.

Lamport大师提出的Paxos算法自问世以来就垄断了分布式共识算法(Raft问世以前),它有一个特点,就是难,不但理论难以理解,实现更是这样.这也就是大师对于Paxos算法的研究论文"The Part-Time Paeliament"在1990年以"故事"的方式提出以后因为没有人能正确的理解而没有接收这篇论文,直到九年以后才由另一位大神修改后才被正式接收,这也意味着Paxos算法正式开始发挥它的价值.这篇晦涩难懂的论文我认为还是不适合我们这些智商普通的一般人去阅读的,还好Lamport在2001年使用通俗易懂的语言重新描述了Paxos算法,并发表了名为"Paxos Made Simple"的论文,这也是一个深入学习Paxos算法的好途径.当然随着互联网的发展,这也并不是唯一途径.

本文试图能够结合参考中的链接使读者大致理解Paxos与multi-Paxos的大部分,开始吧!

问题描述

首先Paxos建立在非拜占庭错误的基础上,也就是只接收节点自身宕机或者由于网络异常而引发的错误.在这样的情况下保证在全局节点为2f+1时容忍f个节点的错误.以此为基础使得整个分布式系统对于某个数据的值达成一致.其实也就是我们所说的共识算法,它的应用非常广泛,比如全局原子操作,实现全局唯一性约束,分布式锁等等.

算法描述

假设有一组可以提出提案的进程,对于问题的细致描述如下:

  1. 所有的提案中只有一个会被最终选定.
  2. 没有提案提出就不会有被选定的提案.
  3. 当一个提案被选定以后,所有进程可以获取被选定的提案.

这里的提案按照上面分布式锁的例子来说就是某些Node请求获取锁,在一次算法的过程中只有一个Node可以获取值.

在Paxos算法中节点有三种状态,且一个节点可以拥有不同的状态,分别为:

  1. Accpeter: 负责接收Proposer的提案,当一半以上Accpeter接收一个提案的时候其为此次算法过程中确定的值.
  2. Proposer: 向Accpeter发送提案.
  3. Learner: 当确定一个提案以后所有的Learner学习此提案,算法结束.

显然算法要求在结束后所有的节点都认可同一个值.

在Paxos中不精确定义活性,只需要确保最终会有一个提案被选定,且所有的节点都能获取到这个节点.(关于活性与安全性,DDIA:p290. 从Paxos到ZooKeeper:p28)我们定义的安全性如下:

  1. 只有被提出的value才能被选定.
  2. 只有一个value被选定.
  3. 如果某个进程认为某个value被选定了,那么这个value必须是真的被选定的那个.

算法推导

要选定唯一一个提案最简单的方案就是只使用一个Accpeter,这样的话只选择它接收到的第一个值就可以保证全局一致了,但是这也带来了单点的局限性,如果唯一的Accpeter宕机,整个系统就会对外界停止服务.所以我们选择使用多个Accpeter,当一半以上Accpeter同意某个提案的时候视为成功,为什么是一半以上呢?因为在任意两个包含大多数的Accpeter集合中必有交集.

首先我们希望即使只有一个提案被提出,仍旧可以选出一个提案,也就是满足以下约束:

P1: 一个Acceptor必须批准它收到的第一个提案.

但是有可能出现一种情况,即每一个Accpeter都批准它收到的第一个提案,但是没有Accpeter得到多数提案,如下图所示:
在这里插入图片描述
(这里要提一下这里的图是我在另一个博主那里拿的,我们的推导过程看起来应该都是基于从Paxos到ZooKeeper这本书和论文Paxos Made Simple的,参考链接我已经放在文末,侵删.)

这样只是一种极端的情况还可能出现两个Proposer,五个Accpeter,其中Peoposer1一个提交给三个Accpeter,Peoposer2提交给两个Accpeter,但是Peoposer1对应的一个Accpeter宕机,这在此轮中仍旧没有找到一个value.

这也就意味着在P1的基础上加上一条需求,即:一个提案被选定需要被半数以上的Acceptor批准.这其实也意味着一个Accpeter能够批准不同的提案,这个时候我们需要把提案这个概念改一改,即提案 == [ 全局唯一递增编号+Value ],此时我们需要清楚一个前提,就是我们虽然允许多个提案被批准,但是它们必须有相同的Value,否则的话会出现全局不一致的情况,也就是说有如下约束:

P2: 如果`编号为M0,Value的值为V0,即提案[M0,V0]被选定了,那么所有编号大于M0,且被选定的提案的Value必须等于V0.

因为序号是全序的,那么P2保证了只会有一个Value值这样的安全性保证,而且当一个提案被选定之前它必须先得被一个Accpeter批准,也就是说由P2衍生出如下约束:

P2a: 如果编号为M0,Value的值为V0,即提案[M0,V0]被选定了,那么所有编号大于M0,且被Accpeter批准的提案的Value必须等于V0.

但是此时还是可能出现问题,就是一个提案在某个Accpeter还未收到任何提案的时候有提案已经被选定了,此时就与P2a约束矛盾,如下图:

在这里插入图片描述
这样的话我们需要对P2a约束再做一些强化.即:

P2b: 如果一个提案[M0,V0]被选定以后,之后任何Proposer所产生编号更高的提案Value都是V0.

因为一个提案只有配Proposer提出以后才有可能被Accpeter批准,所以P2b实际上是包含P2a的,所以只要我们使得P2b成立即可,此时提出以下约束:

p2c: 对于任意的Mn和Vn,如果提案[Mn, Vn]被提出,那么肯定存在一个半数以上的Acceptor组成的集合S,满足以下两个条件中的任意一个:

  • S 中不存在任何批准过编号小于Mn的提案的Accpeter.
  • 选取 S 中所有的编号小于Mn的提案,其中编号最大的Value等于Vn.

这两个条件为什么能够满足p2b呢?因为此时编号M0的提案已经被选定了,也就是说存在一个半数以上的集合A,这个集合内每一个Accpeter都批准了[M0,V0]这个提案,也就是A中每一个Accpeter都批准了一个编号在[M0,Mn-1],Value为V0提案.所以半数以上的集合S必然包含一个集合A中的元素.所以只要满足p2c,就可以满足p2b.

到了这里我们其实可以看到P2c其实就是定义了一个提案生成算法,也就是说如果我们的提案可以满足p2c,就可以满足我们的全部假设.由此我们引入一个提案生成算法.

Proposer生成提案

我们的提案生成过程要遵循p2c,所以Proposer在产生一个序号为Mn的提案的时候要首先要知道一个将要或者已经被半数以上Accpeter批准的编号小于Mn的最大编号的提案.这就是算法的第一阶段.

  1. Proposer选择一个新的提案的编号Mn,然后向某个Accpeter集合的成员发送请求,并要求做出以下回应:
    (a) 保证不批准任何编号小于Mn的的提案.
    (b) 如果Accpeter已经批准过提案,就向Proposer返回该Accpeter已经批准的编号小于中编号最大的那个提案的Value.
  2. 如果Proposer收到了半数以上的Accpeter响应结果,此时Proposer可以生成一个[Mn, Vn]的提案,Vn为所有响应中编号最大的提案的Value.还有一种情况就是返回的响应中没有任何的提案,也就是说此时没有批准任何提案,这个时候Value值就可以自定义了.

这样的提案生成可以使得每次提交提案满足p2c约束,从而满足p2b,也就是说在任何情况都可以保证全局一致了.

在Accpeter接收到一个编号Mn的Prepare请求时,如果Mn小于这个Accpeter批准过的最大的序号,那么就没必要响应了,因为就算响应了在算法的第二阶段也不会批准这个编号为Mn的请求.

收到可能少于Proposer请求集合数回复的原因是可能这些Accpeter已经承诺了不接收序号为Mn的提案,而这个Proposer提案为Mn,也就是说同时有另一个Proposer也在提交提案,算法保证它们最后达成一致.

Accpeter接收提案

我们可以明确在Accpeter可能收到两种请求,分别如下:

  1. Prepare请求: Accpeter可以在任何时候响应一个Prepare请求.
  2. Accept请求: 在不违背现有的所有约束下可以响应任意请求(因为Value都相同).

所以有以下约束:

一个Acceptor只要尚未响应过任何编号大于Mn的Prepare请求,那么他就可以接受这个编号为Mn的提案.

活锁

basic paxos算法可能造成活锁.
在这里插入图片描述
上面我们可以看到每次在一个Proposer得到半数响应准备提交的时候都因为Accpeter承诺不接受编号小于这个Proposer的编号而使得提交失败.这个过程周而复始,从而陷入活锁.不仅如此,Paxos效率并不高,因为每一个值的确定需要3次网络交互,2次本地持久化,这个消耗就比较可观了.
三次请求:

  1. 广播prepare.
  2. 广播Accpet.
  3. 传递消息给Learner.

两次持久化:

  1. Accpeter记录最大序号.
  2. Proposer记录发送的Value.

multi-Paxos

好的解决方法就是multi-Paxos.就是选举一个Leader(前面因为允许多个值提交所以叫Proposer嘛),一般不使用Leader每次提交就是需要两个RTT+两次磁盘操作,如果选举出来Leader以后就只需要一个RTT+一次磁盘操作了.Multi-Paxos通过改变Prepare阶段的作用范围至后面Leader提交的所有实例,从而使得Leader的连续提交只需要执行一次Prepare阶段,后续只需要执行Accept阶段.且
Multi-Paxos允许有多个自认为是Leader的节点并发提交Proposal而不影响其安全性,因为其中总有一个因为编号小于另一个而无法收到一半以上的回复.那么如何选择Leader呢?由上面我们知道有两种方法,一种是强制只有一个Leader,另一个允许出现多个Leader,但效率偏低,因为一个Leader的提议可能会失效.下面是允许多个leader的算法:
在这里插入图片描述
显然可能因为网络的原因出现多个Leader,但是算法保证不会出错,只是增加冲突的机会,使得一些Leader的请求无效.

multi-Paxos与Raft

能看到这里说明你真的是一个很有毅力的人.而在看到multi-Paxos你是否有一种感觉,这玩意怎么和Raft这么像?要搞清这个问题我们首先需要清楚一个问题,就是Paxos实际上是对一个值的的共识,意味着一套复杂的操作后只能确定一个值.然而日常中的所有问题基本上都是对一系列值的共识,从这个角度来看multi-Paxos/Raft和Paxos实际上解决的并不是一个问题.前两个算法都是简化了Paxos的第一个阶段,使得共识的过程只需要一个阶段,这样来看它们确实是类似的.那么区别在哪里呢?问题的答案就是日志与选主:

  1. Raft仅允许日志最新最全的节点当选为leader,而multi-paxos则允许任意节点当选leader(因为multi-paxos日志空缺,不存在一个最新最全的节点).
  2. Raft不允许日志空缺,这也是为了比较容易同步follower的日志,而multi-paxos则允许日志出现空洞,而multi-paxos的leader节点也会异步的查询其他节点来填补自身日志空洞.

所以这样看来.multi-paxos和Raft只是对于Paxos简化的约束不一样,Raft 让用户的log 必须是有序, 选主必须是有日志最全的节点, 而multi-paxos没有这些限制,因此raft的实现会更简单.从这个角度来看,Diego Ongaro实现Raft的初衷应该是达到了,即让我们更好的理解Paxos算法,可能把Raft改名为simple-multi-Paxos我们就不会觉得奇怪了.这也就是Raft论文的第一段就有如下文字:

It produces a result equivalent to (multi-)Paxos, and it is as efficient as Paxos, but its structure is different from Paxos.
Raft提供了与multi-Paxos相同的结果,但是其算法结构不同于Paxos,而且更有效率.

还有一点值得一提就是正如参考中《谈谈paxos, multi-paxos, raft》这篇文章写的那样,Paxos的appendlog的过程是并发的,因为它不要求日志连续(允许出现空洞),而Raft的过程是顺序的,因为日志必须是连续的,所以需要在leader和follower之间同步日志,Raft的论文中也有如下文字:

如果跟随者崩溃或者运行缓慢，再或者网络丢包，领导人会不断的重复尝试附加日志条目 RPCs （尽管已经回复了客户端）直到所有的跟随者都最终存储了所有的日志条目。

且Raft的日志满足以下约束:

  • 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们存储了相同的指令。
  • 如果在不同的日志中的两个条目拥有相同的索引和任期号，那么他们之前的所有日志条目也全部相同。

从这个角度看来Paxos好像拥有更强的并发性(appendlog方面),不强制要求日志连续,Raft就在这点上有着更为强制的要求,这也使得Raft的复杂性减小了,但是研究表明Raft与Paxos的性能差别并不大.

Paxos当然也需要同步日志,在任何基于领导人的一致性算法中,领导人都必须存储所有已经提交的日志条目,Raft论文中有如下文字:

在某些一致性算法中，例如 Viewstamped Replication，一个人可以被选举为领导人即使他一开始并没有包含所有已经提交的日志条目。这种算法包含一些额外的机制来识别丢失的日志条目并把他们传送给新的领导人，要么是在选举阶段要么在之后很快进行。不幸的是，这种方法会导致相当大的额外的机制和复杂性。Raft 使用了一种更加简单的方法，它可以保证所有之前的任期号中已经提交的日志条目在选举的时候都会出现在新的领导人中，不需要传送这些日志条目给领导人。这意味着日志条目的传送是单向的，只从领导人传给跟随者，并且领导人从不会覆盖本地日志中已经存在的条目。

这也是我们上面所说的两个算法之间的差异所在.

如果你想了解的更多可以查看参考中的链接.

总结

我们要清楚的知道Paxos算法其实只是一个确定一个值的共识算法,这其实并不常用,所以只是存在于理论研究当中.更为实用的当属multi-Paxos/Raft算法,它们提供了更优的效率和更强大的功能,但这些也不能掩盖住Paxos算法的耀眼光芒.还有一点就是这样看来自己实现一个共识算法并不是一个容易的事情,按照DDIA上的一句话来说就是"这可能并不明智",因为实在是很少有机构成功,我们在需要的时候可以去使用一些组件以实现相同的功能,例如Zookeeper等.

参考: