Paxos Made Simple (Paxos让事情变简单)
博客专区 > hyssop 的博客 > 博客详情
Paxos Made Simple (Paxos让事情变简单)
hyssop 发表于9个月前
Paxos Made Simple (Paxos让事情变简单)
  • 发表于 9个月前
  • 阅读 15
  • 收藏 0
  • 点赞 0
  • 评论 0
摘要: 译文

原文链接:http://lamport.azurewebsites.net/pubs/paxos-simple.pdf

#摘要: 用通俗英文表述Proxos算法是如此的简单。

1介绍

Paxos算法作为一个容错分布式系统实现一直以来被认为是难以理解的。可能是因为原文的表述对于大多数读者来说有些晦涩<sup>[5]</sup>。实际上,他是分布式算法中最简单,最浅显的。它的核心是一致性算法-“synod”算法<sup>[5]</sup>。下一部分将阐述该一致性算法,基本上我们不可避免的让它满足一些属性。最后一部分将通过应用一致性算法去创建分布式系统状态机的方式来解释Paxos算法的完整过程。这种方法很有名,因为它是分布式系统理论文章的主题<sup>[4]</sup>。

##2 一致性算法 ###2.1 问题 假设一组提议值的节点。一致性算法保证所提议值的一个被选中。如果没有值被提议,那么没有值被选中。如果一个值被选中,节点应该能够学习这个被选中的值。一致性的安全性需求是:

>仅有一个被提议的值可能会被选中,

>仅有单个值被选中,并且

>节点永远不会学习到一个没有被选中的值,除非他已经被选中。

我们不会尝试硬性满足上述需求。但是,最终的目标一定是确保一些被提议的是值最终被选中,并且如果一个值被选中,那么会有最终学习到该值的过程。

我们定义一致性算法的三个角色由以下三种代理类扮演:决策者、代理者、学习者。在实现过程中,单个节点可能扮演超过一种角色,但是节点和角色之间的映射不在本文讨论的范围。

我们假设各个角色之间可以通过发送消息互相沟通。我们使用常规的异步、非拜占庭模型。其中, 代理以任意速度操作,在出错时候停止,并且会重新启动。所有的代理都有可能在值被选中之后停止,并且重新启动,这种情况的时候需要该代理记住一些信息才能避免出错。

消息能通过任意长的时间被传递,复制或者消失,但是他们不会奔溃。

##2.2 选中一个值 选中一个值的最简单方法是拥有单个接受者代理(acceptor)。一个提议者发送提议给这个接受者,他选中第一个获得的值。虽然简单,该解决方案是不令人满意的,因为接收者的错误会使得接下来的处理变得无从下手。

所以,我们尝试另一种方式选中该值。我们用多个接收者代理取代单个接收者。提议者发送一个提议值给接收者集合,接收者可能获得该被提议的值。如果该值被大多数的接收者接收,则该值就被选中。那大多数接收者到底有多少?为了确保有一个单值被选中,我们让足够大的集合包含大多数的代理。因为在一个接收者至多接收一个值的前提下,任意两个大多数都会有一个公共节点。抛开错误和信息丢失,我们想一个值被单个提议者提议之后也被选举出来需要满足:

P1.接收者必须接受它接受的第一个提议值。

但是这种要求产生了一个问题。一些值被不同的提议者同时被提出,导致每个接收者都接收了一个值,没有单个值被大多数接收。即使只有两个提议值,如果每一个提议值都被大概一半的接收者所接收,单个接收者的接收错误都会导致无法辨识哪个值被选中。

条件P1和一个值被大多数接收者接收才能够被选举的条件预示着接收者必须允许接收多余一个的提议值。 我们给不同的提议者一个自然值,那么一个提议包含一个提议标号和一个值。为了避免混淆,我们需要给不同的提议一个不同的数值。如何完成要针对实现,我们现在只做假设。当一个提议被大多数接收者获得的时候,该值就被选中。我们能允许多个提议被选中,但是我们必须保证所有被选中的提议都包含相同的值。归纳下这个提议号,需要满足以下需求:

P2.如果一次选举中值v被拣选了出来,那么每一个高于该提议号的被拣选出来的提议必须有值v。

由于选举号是完全有序的,条件P2保证了一个重要的安全属性:仅有一个值被选中。

为了参与选举,一次提议必须被至少一个接收者接收。所以,通过满足以下条件可以满足P2条件。

P2<sup>a</sup>:如果一个带有值v的提议被选中了,那么被任意接收者接收的每一个更高版本号的提议的值是v。

我们仍然保持P1,保证一些提议被拣选。因为沟通是异步的,一个本该某个接收者c获得的提议最终没有传播到c那里。假设一个新的提议“苏醒”了,并且发出一个带有更高版本号的新值提议。P1要求接收者c获得该提议,违反了P2<sup>a</sup>.保持P1和P2<sup>a</sup>需要增强P2<sup>a</sup>: P2<sup>b</sup>:如果一个带有值v的提议被选择了,那么任意提议者发起的每一个更高版本号的提议的值都是v。

因为一个提议在被接收者接收时必须由提议者提出,P2<sup>b</sup>证明了P2<sup>a</sup>,也就证明了P2。

为了发现如何满足P2<sup>b</sup>,让我们考虑如何证明它的结论。我们会假设一些版本号m和值v的提议被拣选,并且推导任何n>m的提议值都是v。为使得证明方便,我们在数字n上使用规约法。我们来证明任何带有版本号m在以下条件假设的时候有值为v:每一次提议的版本号在m...(n-1)之间的值一定是v,因为版本号为m的提议已经被拣选,所以一定有一个集合C包含大多数的接收者,这些接收者接收了该提议。结合该条件和规约假设。规约假设中版本号m的提议被拣选意味着:

每一个集合C里面的接收者已经接收的版本号为m..(n-1)之间的提议和每一个版本号为m..(n-1)被接收者接收的提议值都为v。

因为任何包含大多数接收者的集合S至少包含一个集合C。我们能获得结论:一个版本号为n的提议值为v的前提是维持以下变量:

P2<sup>c</sup>:对于任意的v和n,如果值为v、版本号为n的提议被拣选出来了,那么一定有一个包含大多数接收者的集合S。

(a)在集合S中没有接收者接收了小于版本号为n的提议

 (b) v是被集合S选中的版本号小于n的提议中版本号最大的值。

我们能通过满足P2<sup>c</sup>条件来满足P2<sup>b</sup>条件。

为了保持P2<sup>c</sup>的不变性。一个想要提议n的提议者必须学习小于版本号n的最大版本号对应的值。该值如果存在,该值已经或者将被大多数接收者集合中所接收。学习已经接收的值是容易的,预测未来接收信息是困难的。提议者要求接收者不要接收任何小于n的提议。这样就推导出以下的发布提议的算法。

1、一个选举者选择一个新的选举号n,并且发送一个请求给某个接收者集合,请求以下回复:

(a) 答应不接受任何提议号小于n的提议。并且

(b) 如果有,返回小于n的最高版本号对应的提议。

我将这个请求阶段叫做带有版本号n的预备请求阶段。

2、如果选举者获得大多数接收者的回复,那么选举者能够发布一个版本号为n值为v的请求。其中,v是获得回复中最高版本提议者的值。如果选举者没有获得任何回复者提供的值,那么选举者可以发布任何值作为请求。

选举者发布一个提议通过发送一个请求给某个接收者集合(这个接收集不需要和初始的请求集合一致)。我们称这个过程叫接受请求阶段。

下面描述提议者算法。一个接收者在请求发起后状态如何?它会从提议者们那里获得两种请求:预备请求和接收请求。在不牺牲安全性的前提下,接收者能够忽略掉任何请求。所以,我们必须知晓接收者在被允许应答的时候才做应答。接收者必须总是给准备请求阶段的请求做出应答。接收者在答应做应答的时候给接收请求阶段的请求做出应答,接收提议。换句话说:

P1<sup>a</sup> :在接收者没有给版本号高于n的准备请求做出回复的情况下,接收者才能够获得版本号为n的请求。

可以看出, P1<sup>a</sup> 包含 P1。

我们现在获得了一个满足安全属性需求的选择值的完整算法。假设提议号是不重复的,最终的算法可以通过小的优化获得。

假设一个接收者获得一个准备请求号为n,但是它已经回复了大于n的准备请求,答应不会给版本号为n的新提议任何回复。那么,没有任何理由让接收者对新的预备请求做回复,因为它将不会接受提议者发布的版本号为n的请求。所以,我们拥有了一个忽略预备请求的接收者。我们也知道它会忽略已经获得提议的新请求。

优化一下,接收者只需要记住他曾经接收到的的版本号最大的提议,和它已回复的预备请求中的最大版本号。因为P2<sup>c</sup>无论在何种失败情况下必须保持不变,即使在出错或者重启的情况下,接收者也必须记住这些信息。必须注意:只要不在相同版本号上继续发布另一个提议,提议者总是能够放弃一个提议,忘记所有关于这个提议的相关信息。

将提议者和接收者的行为放在一起,我们能够看到算法操作包括以下两个阶段:

阶段1.(a) 提议者选择请求号n发送一个预备请求给大多数的接收者。

(b) 如果接收者接收该请求号n的请求时,发现该请求的请求号大于任何一个它已获得的请求,那么它将回复这个请求,答应不再接收任何小于请求号n的请求,并在回复中将它选中的最高版本号的提议返回给接提议者。

阶段2:(a) 如果提议者从大多数的接收者中获得一个准备请求阶段的回复(请求号为n),那么要么他发送携带者请求号n和值v的一个接收请求给每一个接收者,v是回复中最高请求号携带的值,要么发送任何值给每一个接收者,这种情况是接收者获得的最大版本号没有携带一个明确的值。

(b) 如果接收者获得一个请求号为n的接收请求,除非接收者已经回复一个请求号大于n的预备请求。否则会接收这个新的请求。

只要遵循算法的每一步,一个提议者可以产生很多的请求。提议者可以在协议中间的任何时间放弃一个请求。(正确性可以被保证,即使提议者请求和/或相应在提议被放弃的很长一段时间以后到达目的接收者集合)。如果某个提议者已经开始尝试发布更高版本的提议时,放弃以前的提议也许是一个好主意。因此,如果一个接收者因为获得了更高请求号的预备请求而忽略了一个预备或接受请求,那么他hu应该获取通知这个提议者,以便提议者抛弃这个提议。这是一个不影响正确性的性能优化方案。

#2.3 学习挑选一个值

为了学习一个已被选中的值,学习者必须找到被大多数接收者接收的提议。一个明显的算法是对于每一个接收者,在接收一个请求的时候,反馈所有的学习者,将提议发送给每一个学习者。这样学习者能够很快的找到一个被选举出的值,但是它需要每一个接收者回复每一个学习者--回复数量是接收者数量乘以学习者数量。

非拜占庭假设使得一个学习者了解其他学习者获得的值的过程相对简单。当接收者选中一个值的时候,我们能够将接收者接收到的值告知一个特定的学习者,其他学习者轮流学习到该值。这种方法需要一个额外的循环使得所有的学习者学习到已被选举的值。该方法的可依赖性更差,因为特定学习者可能获得值的时候失败。但是该算法回复数量是接收者和学习者数量的和。

更通用的一种方法是,接收者可以从一个特定学习者集合中获得回复,该集合的每一个学习者在选中值出现时通知所有的学习者。使用的特定学习集合中学习者数量越多,稳定性越差,通信越复杂。在消息缺失的情况下,被选举的值不会被任何学习者知晓,学习者可以询问接收者们得知它们接受了哪些提议。在一个接收者选举失败的时候可能导致学习者无法知晓哪个值被选举,在这种情况下,学习者会在新的请求被选举出来以后知晓答案。如果一个学习者需要知道某个值是否被挑选出来,它需要一个提议者采用以上算法发布一个提议。

#2.4 过程

构建这样一个场景是很容易的,就是两个提议者使用递增的申请号持续发布一系列提议,这些提议没有一个被选举成功。提议者p使用请求号n1完成了阶段一的请求,另个一提议者q使用请求号n2完成了阶段1的请求,p的第二阶接收到了n1的第一阶段请求由于接收者都答应不接受任何小于版本号n2的请求而被忽略了的事实。所以,请求p开始以请求号为n3>n2的请求结束了阶段1的请求,导致提议者q的第二阶段得到了被拒绝的事实。这种情况可以反复出现。

为了保证过程顺利进行,必须选择出一个独特的提议者让他单独发布提议。如果该提议者能够和大多数的接收者沟通,并且它使用的版本号大于已经被选举的版本号,那么他将成功发布一个被接收的提议。通过放弃一个请求,并使用已被接收者接受的更高版本号去重新请求,这个特定提议者最终以选择到足够高的请求号为结果。

如果系统(提议者、接收者和通信网络)都运行的足够好,系统的活跃度会因为选择独特的提议者的方案获得保证。 Fischer, Lynch, and Patterson<sup>[1]</sup>的著名结果显示选举提议者的一个可依赖的算法必须使用随机或者实时的方式,-比如通过超时。然而,不管选举的成功或者失败,系统的安全性必须被保证。

#2.5 实现

Paxos算法假定了一个网络处理环境。在一致性算法中,每一个处理过程都包含了提议者、接收者、学习者三种角色。算法选择了一个领袖,扮演着独特提议者和独特学习者的角色。Paxos一致性算法是正好是以上描述的样子,请求和回复都以普通报文的形式发送。回复信息会打上标签,将相应的请求号带回避免混乱。在失败时起保护作用,使用稳定的存储保存接收者必须记住的信息。接受者在真正发送回复之前必须将回复信息保存到稳定存储中。算法接下来的内容就是讲述如何保证两个提议者的版本号不重复。不同的提议者选择版本号从两个无交集的数据集中获取。每一个提议者在稳定存储器中记住已经被发布的最高版本,使用更高版本号发送第一阶段的请求。

#3、实现一个状态机 实现一个分布式系统的简单方法是做为一个客户端集合将发布命令发布给服务器中心。服务器可以被描述为一个确定性状态机,有序的执行客户端命令。状态机有一个现有状态,通过获取输入命令和生成一个输出的过程变为一个新的状态。比如某个一特定银行系统客户端集合相当于出纳员,状态机的状态相当于所有用户的账户余额。通过执行状态机命令发起提款请求,只有该账户的余额大于所要求提款的数额才允许执行命令,产生了一个老的和新的余额作为结果。

如果服务失败,那么单机服务器的实现也就失败了。我们因此通过使用一个服务器集合,每一个服务器单独实现状态机。由于状态机是确定性的,当执行相同一系列命令的时候,所有的服务器将产生某一系列的状态和输出。客户端发布一个命令时,能够使用任何服务器的输出作为结果。

为了保证所有的服务器都执行相同系列的状态机命令,我们分别实现了一系列Paxos一致性算法实例,i<sup>th</sup>实例选择的值作为系列中i<sup>th</sup>状态机的命令。算法中每一个节点的服务器都扮演了所有的角色(提议者、接收者和学习者)。目前,我们假设服务器集合数量固定,一致性算法的所有实例都使用相同的代理集合。

在正常操作的情况下,单个服务器被选中为领导者,在一致性算法的所有实例中该服务器扮演了一个独特的提议者(它唯一发布提议)。客户端发送命令给领导者,领导者决定命令系列应该出现在哪里。如果领导决定某个客户端的命令应该是第135个命令,那么它会将该命令选择为一致性算法中的第135个实例。这个过程通常会成功。在网络异常的情况会失败,或者由于另一个服务器也将自己当成了领导者,并且对第135个命令有另一种想法的情况也会失败。但是一致性算法保证只有一个第135个命令。

该方法的效率核心是,在Paxos一致性算法中,被选举的值是在第二阶段才被选中。回想一下,在请求算法的第一阶段完成后,要么被选中的值被定下来了,要么提议者可以任意选择一个值。我马上要描述Paxos状态机实现在正常操作的流程。然后,我将要讨论在错误流程时候状态机流程。我会考虑当前一个领导者刚刚失败,新的领导者被选举出来的时候会发生什么。系统启动是一个比较特殊的场景,没有命令已经被选举出来。

新的领导者,作为一致性算法实例中的一个学习者应该知道已经被选中的大多数命令。假设它知道1-134、138和139号命令-也就是对应一致性算法中1-134、138和139实例的值(接下来我们将要看到命令系列的这个间隔是如何产生的)。新的领导者将会在实例编号为135-137和所有大于139的实例中执行第一个阶段(下面我们将描述它是如何做到的)。假设这些执行结果决定选中实例135和140中获得的值,但是和其他实例的值有差异,领导者会在实例135和140中执行第二阶段,因此选择了135-140实例的命令。

除了其它学习者学习到了领导者知晓的命令,领导者现在能够执行命令1-135。然而,由于136和137的命令已经被选中,它也知道自己不能够执行138-140的命令。领导者能够接收客户端对136、137的命令。通过提议我们让它作为136、137的命令立刻填补了间隙,空操作让状态机状态不变(通过执行一致性实例136、137的第二阶段的方法)。一旦这些空操作被选举,138-140的命令就能够被执行。

现在,1-140的命令已经被选中。领导者也完成了所有大于140实例一致性算法的第一阶段,他可以提议任意值给实例的第二阶段。它分派命令号141给客户端的命令请求,提议它作为一致性算法的141实例第二阶段被选举的值。领导者提议它接收到的下一个客户端命令作为第142号命令,以此类推。

在领导者学习到第141号命令被选中之前,可以提议第142号命令。这种可能是在第141号命令所携带的所有信息丢失的情况下。并且,在其他服务器学习到领导者已提议141号命令之前选中了142号命令。当领导者没能在第二阶段获得141号命令的期望回复,他将重新发送这些信息。一切顺利的情况下,提议的命令会被选中。然而,它可能首先失败,离开被选择命令系列的间隙。通常情况下,假设领导者能够提前得到a命令,也就是说它在命令1到i命令被选中后,能够通过提议命令i+a命令提议i+1命令。大于a-1的命令间隙会随之产生。

新选举出来的领导者在阶段1可能执行一致性算法的无限多实例。比如在以上场景中,选举者可以在阶段1执行实例135-137和所有大于139的实例。可以通过发送单个合理的小信息给其它服务器的形式给所有实例相同的提议编号。阶段1,如果接收者从一些提议者的第二阶段获得了信息,那么提议者会发送大于1的简单回复ok(当前场景是135-140会出现这种情形)。因此,一个服务器(扮演一个接收者)会回复所有的实例一个简单的信息,执行这些无限多实例的第一阶段会毫无问题。

由于领导者失败,选择新的选举者情形比较罕见,执行状态机命令的实际成本是获得命令/值一致性的开销,也是只执行一致性算法第二阶段的开销。Paxos一致性算法的第二阶段已经在出现错误的情况下最小化可能得开销。因此Paxos算法本质上是优化的。

讨论中假设在系统的普通操作中总是只有一个领导者,没有讨论当现有领导者失败,新的领导者被选中的阶段。正常情况下,领导者选举会失败,如果没有服务器作为领导者,那么不会有新的命令被提议。如果多个服务器都相当领导者,那么在一致性算法中,它们都能够在相同节点中提议,这样就阻止了任何一个值被选中。然而,安全起见还是阻止两个领导者,如果有两个领导者状态机的i阶段不会同意任何值被选中。为确保过程一定选举出单个领导者。

如果一组服务器能够被改变,那么他们必须通过某种方式决定服务器扮演一致性算法的哪种实例。这件事最简单的实现就是通过状态机本身。目前的服务器集合可以作为状态机的一部分,并且能够通过普通的状态机命令被改变。通过以下的方式我们允许一个领导者提前获得命令a,在第i个状态机命令被执行之后,通过指定执行了一致性算法i+a命令的服务器集合。这允许了任意复杂可配置算法的简单实现。

##参考文献 [1] Michael J. Fischer, Nancy Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.

[2] Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus when there are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821, Laboratory for Computer Science, Massachusetts Institute Technology, Cambridge, MA, 02139, May 2001. also published in SIGACT News 32(2) (June 2001).

[3] Leslie Lamport. The implementation of reliable distributed multiprocess systems. Computer Networks, 2:95–114, 1978.

[4] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, July 1978.

[5] Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133–169, May 1998.- 这里是列表文本

共有 人打赏支持
粉丝 18
博文 84
码字总数 103453
×
hyssop
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: