Hycz's Blog

Life is a game. Why so serious?

Tag Archives: Paxos

[转]PaxosLease

原文转自:http://www.cnblogs.com/chen77716/archive/2011/03/21/2130800.html

世上有很多选举算法,但最完美的莫过于Paxos,但把paxos用于master选举与用于value的选举有用众多不同之处,主要一点是二者执 行频率不同。value选举需要频繁、高密度地执行paxos算法,每instance选举一个value。因此,原生的paxos算法无法满足高性能的 要求;另一个问题是,paxos理论上存在活锁,lamprot推荐大家通过选举Leader避免这个问题。

所有的实现都指向一个Leader/Master,但Master的选举又该如何实现?如果继续采用paxos那性能和活锁又该如何解决?这个似乎 是个递归问题,用paxos解决paxos遇到的问题。能实现吗?能,Keyspace的PaxosLease算法给出了答案。

1. Lease

Master选举的过程是这样的:从众多的Node中选择一个作为Master,如果该Master一致alive则无需选举,如果master crash,则其他的node进行选举下一个master。选择正确性的保证是:任何时刻最多只能有一个master。

逻辑上Master更像一把无形的锁,任何一个节点拿到这个锁,都可成为master,所以本质上Master选举是个分布式锁的问题,但完全靠锁 来解决选举问题也是有风险的:如果一个Node拿到了锁,之后crash,那锁会导致无法释放,即死锁。一种可行的方案是给锁加个时间(Lease),拿 到锁的Master只能在Lease有效期内访问锁定的资源,在Lease timeout后,其他Node可以继续竞争锁,这就从根本上避免了死锁。

Master在拿到锁后,如果一直alive,可以向其他node”续租“锁,从而避免频繁的选举活动。关于Lease更多的请参考:http://research.microsoft.com/en-us/um/people/blampson/58-consensus/webpage.html

2. Master选举

Master选举与value选举存在几个不同的地方:

  • 执行频率低(正常情况下,Node失败概率不会太高)
  • 无Paxos的持久化,重启后状态丢失

为了保证选举正确性,还要保证:

  • 保证算法纯正性,不依赖与其他算法

3. PaxosLease

PaxosLease是Kespace开发的基于Paxos、Lease的Master选举算法,算法的角色与Paxos一样,也分Proposer、Acceptor、Learn,各角色的行为也与paxos基本一致,但除下面两个重要的区别:

  • 不要求acceptor持久化数据
  • 不存在Leader

PaxosLease把Paxos的accept阶段重新命名为propose,因此存在prepare、propose2个阶段。

再引入几个符号:

  • T:每个Master的Lease时间(秒)
  • M:全局Lease时间,要确保 M > T
  • ballot number:每次发送的proposal编号

算法过程

  1. proposer启动定时器Timer1,等待T秒便超时
  2. proposer向acceptor发送(ballot number,proposer id,T)
  3. acceptor接收到prepare消息后,判断:
    • 如果msg.ballot_number < local.promisedBallotNumber,则发送拒绝消息
    • 否则,发送accept,包含的内容已经promise的最大编号和T
  4. proposer接收acceptor的response
    • 如果多数派accept,则进入promise阶段
    • 否则,随机等待一段时间,提高编号重启prepare过程
  5. proposer执行promise阶段
    • 如果prepare阶段接收的value不为空,则终止promise
    • 否则,发送(ballot number,proposer id ,T)
  6. acceptor接收到promise请求
    • 如果msg.ballot_number < local.promisedBallotNumber,则回应拒绝消息
    • 否则,启动定时器Timer2,等待T秒超时
  7. proposer接收acceptor的response
    • 如果接收到多数派的回应
      • 删除Timer1
      • 启动extend Timer3,等待时间T1 < T
      • 发送Learn消息,转入8
    • 否则,重启prepare过程
  8.  Learn接收到proposer的learn消息
    • 停止Timer1
    • 重新启动Timer1

因为proposer、acceptor、learn三位一体,所以上述提到的Timer1、Timer2、Timer3其实位于同一Node,同一进程。

  • Timer1:等待时间T,超时便发起prepare请求
  • Timer2:等待时间T,超时便清空本次paxos instance状态,继续下一次
  • Timer3:等待时间T1 < T,超时便执行prepare

Timer1运行于所有的Node,任何一个Node的Timer1超时便发起prepare请求

Timer2仅运行与参与选举过程的Node,如果超期则清空本次选举状态

Timer3仅运行于获得lease的节点,目的是在lease超期之前续租

4. Paxos

移除lease相关部分,上述过程其实就是一次paxos instance,但第5步与原始paxos算法稍有不同:

  • 原始的paxos规定,如果接收的value v不为空,则使用v继续accept阶段,以保证每次选举仅选出一个决议;
  • PaxosLease选举的目的是使其他node接受自己作为master,当接收的value不为空时,自己应该退出选举,而不是继续提交其他Node的value。也就是说,只要当前node知道其他Node可能会优先自己成为master,则退出选举,成就他人。

因为每个节点都始终运行着Timer1,只要超时便开始prepare,因此paxosleas不存在静态死锁问题,但动态死该怎么解决?之前关于 paxos算法的介绍得知,在paxos中存在活锁,也即动态死锁,表现为在prepare阶段2个proposer会转而提出更高编号的 proposal,PaxosLease提供的解决办法就是在失败重新提交proposal时随机等待一段时间,因为各Node等待时间的不一致,只要运 行足够长的时间,活锁总能避免。

传统的Paxos是否可以采取这样的方法避免活锁?答案是否定的,之前说过,value选举的频率高、延迟低,不能容忍提交proposal时等待几秒。而Master选举因为频率低,却可以容忍上述方法带来的性能损失。

因为运行PaxosLease的所有节点都没有持久化,当Node重启时所有的状态都会丢失,这样重新加入的节点可能会扰乱前面的paxos过程, 因此强制Node在重新加入前必须等待M秒,因为M > T,所以只要等待M秒便可以越过本次paxos选举。其实即使等待M秒,也不能从理论上完全保证PaxosLease能正确执行,要搞清楚这个我问题,我 们必须知道新加入的Node是如何扰乱了paxos过程:

假如存在三个Acceptor A、B、C,已经promised的最高编号分别为A =(1),B =(1),C =(1);存在两个proposer P1,P2

  1. 初始状态A=(1)、B=(1)、C=N/A# P1 提交编号(3,v3)到A、B成功完成了prepare、accept阶段,编号3,v1被选为最终决议
  2. B宕机重启,状态丢失回到初始状态、A宕机、C重启,则A=N/A、B =(1)、C=(1)# P2提交编号(2,v2)到B、C也可成功完成preapare、accept阶段,编号2,v2被选为最终决议

存在v2、v3两个最终决议,违反了paxos的安全属性。如果B重启能记住之前的状态B=(3,v3),P2则不会提交成功,从而能保证paxos的安全属性。这个错误发生要几个条件:

  • 节点重启前作为多数派回应了prepaer、accept消息
  • 其他节点也重启,并与当前节点构成最少多数派
  • 之前的instance未结束,又回答了其他proposer的prepare、accept消息

反观M秒的设定,其实等待多少秒并不重要,重要的是重加入后不能立即参加paxos过程。在实际中因为选举的过程非常快,节点重加入的过程也可监控,这些理论上的错误是很难发生的。

Catch Up机制是否适用于PaxosLease?


在讨论paxos的实现时,曾提到如果节点磁盘失败,当重新加入时需要使用catch up,节点参与paxos过程,但不做任何回应,直至一次paxos过程完成。

但这个并不适合于PaxosLease,因为master选举的频率很低,如果等待一次paxos过程完成,节点要等很长的时间才能重新加入。

5. 正确性证明

PaxosLease是由3个精妙配合的Timer来工作的,Paxos算法的正确性是显然的,PaxosLease会不会在引入Timer之后改变其安全假设?请看下面简短证明:

首先引入几个符合:

  • b:ballot number
  • tstart :proposer启动Timer1的时间
  • tnow :proposer在prepare阶段接收到多数派响应空value的时间
  • tacquire :proposer在propose阶段接收到多数派的accept时间
  • A1:在prepare阶段回应proposer的多数派
  • A2:在propose阶段回应proposer的多数派

假如proposer p已经获得了lease,则在tend =tstart +T之内,其他proposer不会获得多数派acceptor响应空value,也即其他proposer不会获得lease。

Part1:不存在任何proposer q,编号b1<b,在[tacquire ,tend ]之间获得lease


假如q也在此期间获得了lease,则存在多数派A4在propose阶段回应了q,令a是A2和A4的公共成员,因为b1<b,a必定先接 受了q的proposal,然后发送回应给p,因为p在propose阶段接收到了空value,说明q的Timer2已经超时,因此q的timer也肯 定超时(b1<b,q的timer启动的更早),因此p、q的lease并无重叠

Part2:不存在任何propose q,编号b1>b,在[tacquire ,tend ]之间获得lease


证明与上类似。

6. 结论

其实PaxosLease的正确性是有Paxos算法保证的,PaxosLease只是在Paxos的基础上限定了一个时间。在时间T之内,任何Node都不能申请lease,因此master宕机后重新选择master的最大时间为T,也即服务不可用的最大时间为T。

T设的过小会减少服务不可用的时间,但会产生更多的内部消息;设的过大内部消息减少,但会导致更长的宕机时间。

PaxosLease是一个节点之间不存在依赖的简洁的选举算法,就像其论文所说每个节点都有两个状态:

  • 我不是master,也不知道谁是master
  • 我是master

正因为如此,PaxosLease的缺点就是无法做到负载均衡,无法按权重选择master。

[转]Paxos算法3-实现探讨

原文转自:http://www.cnblogs.com/chen77716/archive/2011/02/04/2130802.html

前两篇Paxos算法的讨论,让我们对paxos算法的理论形成过程有了大概的了解,但距离其成为一个可执行的算法程序还有很长的路要走,原因是很多的细节和错误未被考虑。Google Chubby的作者说,paxos算法实现起来远没有看起来简单,原因是paxos的容错仅限于server crash这一种情况,但在实际工程实现时要考虑磁盘损坏、文件损坏、Leader身份丢失等诸多的错误。

1. Paxos各角色的职能

在paxos算法中存在Client、Proposer、Proposer Leaer、Acceptor、Learn五种角色,可精简为三种主要角色:proposer、acceptor、learn。角色只是逻辑上存在的,在实际实现中,节点可以身兼多职。

在我们的讨论中,我们先假定没有Proposer Leader这一角色,在不考虑活锁的情况下,如果算法过程正确,那有Leader角色的算法过程肯定也正确。

除了五种角色,还有三个重要的概念:instance、proposal、value,分别代表:每次paxos选举过程、提案、提案的value

当然,还有4个关键过程:

  • (Phase1):prepare
  • (Phase1):prepare ack
  • (Phase2):accept
  • (Phase2):accept ack

对acceptor来说,还蕴含是着promise、accept、reject三个动作。

先上一幅图,更直观地对几种角色的职能加以了解(各角色的具体职能参考Lamport的论文就足够了):

Paxos各角色职责

上图不是非常严格,仅为表现各角色之间的关系。

2. Proposer

在Proposer、Acceptor、Learn中均涉及到proposal的编号,该编号应该有proposer作出改变,对其他的角色是只读的,这就保证了只有一个数据源。当多个proposer同时提交proposal时,必须保证各proposer的编号唯一、且可比较,具体做法之前已经提到。这里还要强调一点的是,仅每个proposer按自己的规则提高编号是不够的,还必须了解“外面”的最大编号是多少,例如,P1、P2、P3(请参考:Paxos算法2#再论编号问题:编号唯一性 )

  • P3的当前编号为初始编号2
  • 当P3提交proposal时发现已经有更大的编号16(16是P2提出的,按规则:5*3+1)
  • P3发起新编号时必须保证new no >16,按照前面的规则必须选择:5*3+2 = 17,而不能仅按自己的规则选择:1*3+2=5

这要求acceptor要在reject消息中给出当前的最大编号,proposer可能出现宕机,重启后继续服务,reject消息会帮助它迅速找到下一个正确编号。但是当多个acceptor回复各自不一的reject消息时,事情就变得复杂起来。

当proposer发送proposal给一个acceptor时,会有三种结果:

  • timeout:超时,未接收到aceptor的response
  • reject:编号不够大,拒绝。并附有当前最大编号
  • promise:接受,并确保不会批准小于此编号的proposal。并附有当前最大编号及对应的value

在判断是否可以进行Phase2时的一个充分条例就是:必须有acceptor的多数派promise了当前的proposal 。

下面分别从Phase1和Phase2讨论proposer的行为:

Phase1-prepare:发送prepare到acceptor


Proposer在本地选择proposal编号,发送给acceptor,会收到几种情况的response:

(a). 没有收到多数派的回应

消息丢失、Server宕机导致没有多数派响应,在可靠消息传输(TCP)下,应该报告宕机导致剩余的Server无法继续提供服务,在实际中一个多数派同时宕机的可能性非常小。

(b). 收到多数派的reject

Acceptor可能会发生任意的错误,比如消息丢失、宕机重启等,会导致每个acceptor看到的最大编号不一致,因而在reject消息中response给proposer的最大编号也不一致,这种情况proposer应该取其最大作为比较对象,重新计算编号后继续Phase1的prepare阶段。

(c). 收到多数派的promise

根据包含的value不同,这些promise又分三种情况:

  • 多数派的value是相同的,说明之前已经达成了最终决议
  • value互不相同,之前并没有达成最终决议
  • 返回的value全部为null

全部为null的情况比较好处理,只要proposer自由决定value即可;多数派达成一致的情况也好处理,选择已经达成决议的value提交即可,value互不相同的情况有两种处理方式:

  • 方案1:自由确定一个value。原因:反正之前没有达成决议,本次提交哪个value应该是没有限制的。
  • 方案2:选择promise编号最大的value。原因:本次选举(instance)已经有提案了,虽未获通过,但以后的提案应该继续之前的,Lamport在paxos simple的论文中选择这种方式。

其实问题的本质是:在一个instance内,一个acceptor是否能accept多个value?约束P2只是要求,如果某个value v已被选出,那之后选出的还应该是v;反过来说,如果value v还没有被多数派accept,也没有限制acceptor只accept一个value。

感觉两种处理方式都可以,只要选择一个value,能在paxos之后的过程中达成一致即可。其实不然,有可能value v已经成为了最终决议,但acceptor不知道,如果这时不选择value v而选其他value,会导致在一次instance内达成两个决议。

会不会存在这样一种情况:A、B、C、D为多数派的promise,A、B、C的proposal编号,value为(1,1),D的为(2,2)?就是说,编号互不一致,但小编号的已经达成了最终决议,而大编号的没有?

设:小编号的proposal为P1,value为v1;大编号的proposal为P2,value为v2

  • 如果P1选出最终决议,那么肯定是完成了phase1、phase2。存在一个acceptor的多数派C1,P1为其最大编号,并且每个acceptor都accept了v1;
  • 当P2执行phase1时,存在多数派C2回应了promise,则C1与C2存在一个公共成员,其最大编号为P1,并且accept了v1
  • 根据规则,P2只能选择v1继续phase2,也就是说v1=v2,无论phase2是否能成功,绝不会在acceptor中遗留下类似(2,2)这样的value

也就是说,只要按照【方案2】选择value就能保证结果的正确性。之所以能有这样的结果,关键还是那个神秘的多数派,这个多数派起了两个至关重要的作用:

  • 在phase1拒绝小编号的proposal
  • 在phase2强迫proposal选择指定的value

而多数派能起作用的原因就是,任何两个多数派至少有一个公共成员,而这个公共成员对后续proposal的行为起着决定性的影响,如果这个多数派拒绝了后续的proposal,这些proposal就会因为无法形成新的多数派而进行不下去。这也是paxos算法的精髓所在吧。

Phase2-accept:发送accept给acceptor


如果一切正常,proposer会选择一个value发送给acceptor,这个过程比较简单

accept也会收到2种回应:


(a). acceptor多数派accept了value

一旦多数派accept了value,那最终决议就已达成,剩下的工作就是交由learn学习并关闭本次选举(instance)。

(b). acceptor多数派reject了value或超时

说明acceptor不可用或提交的编号不够大,继续Phase1的处理。

proposer的处理大概如此,但实际编程时还有几个问题要考虑:

  • 来自acceptor的重复消息
  • 本来超时的消息又突然到了
  • 消息持久化

其他2个问题比较简单,持久化的问题有必要讨论下。

持久化的目的是在proposer server宕机“苏醒”时,可以继续参与paxos过程。

从前面分析可看出,proposer工作的正确性是靠编号的正确性来保证的,编号的正确性是由proposer对编号的初始化写及acceptor的reject一起保证的,所以只要acceptor能正常工作,proposer就无须持久化当前编号。

3. acceptor

acceptor的行为相对简单,就是根据提案的编号决定是否接受proposal,判断编号依赖promise和accept两种消息,因此acceptor必须对接收到的消息做持久化处理。根据之前的讨论也知道,acceptor的持久化也会影响着proposer的正确性。

在acceptor对proposal进行决策的时候,还有个重要的概念没有被详细讨论,即instance。任何对proposal的判断都是基于某个instance,即某次paxos过程,当本次instance宣布结束(选出了最终决议)时,paxos过程就转移到下一个instance。这样会衍生出几个问题:

  1. instance何时被关闭?被谁关闭?
  2. acceptor的行为是否依赖instance的关闭与否?
  3. acceptor的多数派会不会在同一个instance内对两个不同的value同时达成一致?

根据1中对各角色职能的讨论,决议是否被选出是由learn来决定的,当learn得知某个value v已经被多数派accept时,就认为决议被选出,并宣布关闭当前的instance。与2中提到的一样,因为网络原因acceptor可能不会得知instance已被关闭,而会继续对proposer回答关于该instance的问题。也就是说,无论如何acceptor都无法准确得知instance是否关闭,acceptor程序的正确性也就不能依赖instance是否关闭。但acceptor在已经知道instance已被关闭的情况下,在拒绝proposer时能提供更多的信息,比如,可以使proposer选择一个更高的instance重新提交请求。

当然,只要proposer根据2中提到的方式进行提案,就不会发生同一instance中产生两个决议的情况。

4. learn

learn的主要职责是学习决议,但决议必须一个一个按顺序学,不能跳号,比如learn已经知道了100,102号决议,必须同时知道101时才能一起学习。只是简单的等待101号决议的到来显然不是一个好办法,learn还要去主动向acceptor询问101号决议的情况,acceptor会对消息做持久化,做到这一点显然不难。

learn还要周期性地check所接收到的value,一旦意识到决议已经达成,必须关闭对应的instance,并通知acceptor、proposer等(根据需要可以通知任意多的对象)。

learn还存在一个问题是,是选择一个server做learn还是选多个,假如有N个acceptor,M个learn,则会产生N*M的通信量,如果M很大则通信量会非常大,如果M=1,通信量小但会形成单点。折中方案是选择规模相对较小的M,使这些learn通知其他learn。

paxos中的learn相对比较抽象,好理解但难以想象能做什么,原因在于对paxos的应用场景不清晰。一般说来有两种使用paxos的场景:

  • paxos作为单独的服务,比如google的chubby,hadoop的zookeeper
  • paxos作为应用的一部分,比如Keyspace、BerkeleyDB

如果把paxos作为单独的服务,那learn的作用就是达成决议后通知客户端;如果是应用的一部分,learn则会直接执行业务逻辑,比如开始数据复制。

持久化:

learn所依赖的所有信息就是value和instance,这些信息都已在acceptor中进行了持久化,所有learn不需要在对消息做持久化,当learn新加入或重启时要做到的就是能把这些信息通过acceptor再取回来。

错误处理:

learn可能会重启或新加入后会对“之前发生的事情”不清楚,解决办法是:使learn继续监听消息,直至某个instance对应的value达成一致时,learn再向acceptor请求之前所有的instance。

至此,我们进一步讨论了paxos个角色的职责和可能的实现分析,离我们把paxos算法变为一个可执行程序的目标又进了一步,使我们对paxos的实现方式大致心里有底,但还有诸多的问题需要进一步讨论,比如错误处理。虽然文中也提到了一些错误及处理方式,但还没有系统地考虑到所有的错误。

接下来的讨论将重点围绕着分布式环境下的错误处理。

[转]Paxos算法2-算法过程

原文转自:http://www.cnblogs.com/chen77716/archive/2011/01/30/2130803.html

1.编号处理

根据P2c ,proposer在提案前会先咨询acceptor查看其批准的最大的编号和value,再决定提交哪个value。之前我们一直强调更高编号的proposal,而没有说明低编号的proposal该怎么处理。

|——–低编号(L<N)——–|——–当前编号(N)——–|——–高编号(H>N)——–|

P2c 的正确性是由当前编号N而产生了一些更高编号H来保证的,更低编号L在之前某个时刻,可能也是符合P2c 的,但因为网络通信的不可靠,导致L被延迟到与H同时提交,L与H有可能有不同的value,这显然违背了P2c ,解决办法是acceptor不接受任何编号已过期的proposal,更精确的描述为:

P1a : An acceptor can accept a proposal numbered n iff it has not responded to a prepare request having a number greater than n.

显然,acceptor接收到的第一个proposal符合这个条件,也就是说P1a 蕴含了P1。

关于编号问题进一步的讨论请参考下节的【再论编号问题:唯一编号 】。

2. Paxos算法形成

重新整理P2c 和P1a 可以提出Paxos算法,算法分2个阶段:

Phase1:prepare

(a)proposer选择一个proposal编号n,发送给acceptor中的一个多数派

(b)如果acceptor发现n是它已回复的请求中编号最大的,它会回复它已accept的最大的proposal和对应的value(如果有);同时还附有一种承诺:不会批准编号小于n的proposal

Phase2:accept

(a)如果proposer接收到了多数派的回应,它发送一个accept消息到(编号为n,value v的proposal)到acceptor的多数派(可以与prepare的多数派不同)

关键是这个value v是什么,如果acceptor回应中包含了value,则取其编号最大的那个,作为v;如果回应中不包含任何value,则有proposer随意选择一个

(b)acceptor接收到accept消息后check,如果没有比n大的回应比n大的proposal,则accept对应的value;否则拒绝或不回应

感觉算法过程异常地简单,而理解算法是怎么形成却非常困难。再仔细考虑下,这个算法又会产生更多的疑问:

再论编号问题:唯一编号


保证paxos正确运行的一个重要因素就是proposal编号,编号之间要能比较大小/先后,如果是一个proposer很容易做到,如果是多个proposer同时提案,该如何处理?Lamport不关心这个问题,只是要求编号必须是全序的,但我们必须关心。这个问题看似简单,实际还稍微有点棘手,因为这本质上是也是一个分布式的问题。

在Google的Chubby论文中给出了这样一种方法:

假设有n个proposer,每个编号为ir (0<=ir <n),proposol编号的任何值s都应该大于它已知的最大值,并且满足:s %n = ir => s = m*n + ir

proposer已知的最大值来自两部分:proposer自己对编号自增后的值和接收到acceptor的reject后所得到的值

以3个proposer P1、P2、P3为例,开始m=0,编号分别为0,1,2

P1提交的时候发现了P2已经提交,P2编号为1 > P1的0,因此P1重新计算编号:new P1 = 1*3+0 = 4

P3以编号2提交,发现小于P1的4,因此P3重新编号:new P3 = 1*3+2 = 5

整个paxos算法基本上就是围绕着proposal编号在进行:proposer忙于选择更大的编号提交proposal,acceptor则比较提交的proposal的编号是否已是最大,只要编号确定了,所对应的value也就确定了。所以说,在paxos算法中没有什么比proposal的编号更重要。

活锁


当一proposer提交的poposal被拒绝时,可能是因为acceptor promise了更大编号的proposal,因此proposer提高编号继续提交。 如果2个proposer都发现自己的编号过低转而提出更高编号的proposal,会导致死循环,也称为活锁。

Leader选举


活锁的问题在理论上的确存在,Lamport给出的解决办法是选举出一个proposer作leader,所有的proposal都通过leader来提交,当Leader宕机时马上再选举其他的Leader。

Leader之所以能解决这个问题,是因为其可以控制提交的进度,比如果之前的proposal没有结果,之后的proposal就等一等,不着急提高编号再次提交,相当于把一个分布式问题转化为一个单点问题,而单点的健壮性是靠选举机制保证。

问题貌似越来越复杂,因为又需要一个Leader选举算法,但Lamport在fast paxos中认为该问题比较简单,因为Leader选举失败不会对系统造成什么影响,因此这个问题他不想讨论。但是后来他又说,Fischer, Lynch, and Patterson的研究结果表明一个可靠的选举算法必须使用随机或超时(租赁)。

Paxos本来就是选举算法,能否用paxos来选举Leader呢?选举Leader是选举proposal的一部分,在选举leader时再用paxos是不是已经在递归使用paxos?存在称之为PaxosLease的paxos算法简化版可以完成leader的选举,像Keyspace、Libpaxos、Zookeeper、goole chubby等实现中都采用了该算法。关于PaxosLease,之后我们将会详细讨论。

虽然Lamport提到了随机和超时机制,但我个人认为更健壮和优雅的做法还是PaxosLease。

Leader带来的困惑


Leader解决了活锁问题,但引入了一个疑问:

既然有了Leader,那只要在Leader上设置一个Queue,所有的proposal便可以被全局编号,除了Leader是可以选举的,与Paxos算法1 提到的单点MQ非常相似。

那是不是说,只要从多个MQ中选举出一个作为Master就等于实现了paxos算法?现在的MQ本身就支持Master-Master模式,难道饶了一圈,paxos就是双Master模式?

仅从编号来看,的确如此,只要选举出单个Master接收所有proposal,编号问题迎刃而解,实在无须再走acceptor的流程。但paxos算法要求无论发生什么错误,都能保证在每次选举中能选定一个value,并能被learn学习。比如leader、acceptor,learn都可能宕机,之后,还可能“苏醒”,这些过程都要保证算法的正确性。

如果仅有一个Master,宕机时选举的结果根本就无法被learn学习, 也就是说,Leader选举机制更多的是保证异常情况下算法的正确性,虚惊一场,paxos原来不是Master-Master。

在此,我们第一次提到了”learn”这个角色,在value被选择后,learn的工作就是去学习最终决议,学习也是算法的一部分,同样要在任何情况下保证正确性,后续的主要工作将围绕“learn”展开。

Paxos与二段提交


Google的人曾说,其他分布式算法都是paxos的简化形式。

假如leader只提交一个proposal给acceptor的简单情况:

  • 发送prepared给多数派acceptor
  • 接收多数派的响应
  • 发送accept给多数派使其批准对应的value

其实就是一个二段提交问题,整个paxos算法可以看作是多个交叉执行而又相互影响的二段提交算法。

如何选出多个Value


Paxos算法描述的过程是发生在“一次选举”的过程中,这个在前面也提到过,实际Paxos算法执行是一轮接一轮,每轮还有个专有称呼:instance(翻译成中文有点怪),每instance都选出一个唯一的value。

在每instanc中,一个proposal可能会被提交多次才能获得acceptor的批准,一般做法是,如果acceptor没有接受,那proposer就提高编号继续提交。如果acceptor还没有选择(多数派批准)一个value,proposer可以任意提交value,否则就必须提交意见选择的,这个在P2c 中已经说明过。

Paxos中还有一个要提一下的问题是,在prepare阶段提交的是proposal的编号,之后再决定提交哪个value,就是value与编号是分开提交的,这与我们的思维有点不一样。

3. 学习决议

在决议被最终选出后,最重要的事情就是让learn学习决议,学习决议就是决定如何处理决议。

在学习的过程中,遇到的第一个问题就是learn如何知道决议已被选出,简单的做法就是每个批准proposal的acceptor都告诉每个需要学习的learn,但这样的通信量非常大。简单的优化方式就是只告诉一个learn,让这个唯一learn通知其他learn,这样做的好是减少了通信量,但坏处同样明显,会形成单点;当然折中方案是告诉一小部分learn,复杂性是learn之间又会有分布式的问题。

无论如何,有一点是肯定的,就是每个acceptor都要向learn发送批准的消息,如果不是这样的话,learn就无法知道这个value是否是最终决议,因此优化的问题缩减为一个还是多个learn的问题。

能否像proposer的Leader一样为learn也选个Leader?因为每个acceptor都有持久存储,这样做是可以的,但会把系统搞的越来越复杂,之后我们还会详细讨论这个问题。

Learn学习决议时,还有一个重要的问题就是要按顺序学习,之前的选举算法花费很多精力就是为了给所有的proposal全局编号,目的是能被按顺序使用。但learn收到的决议的顺序可能不不一致,有可能先收到10号决议,但9号还未到,这时必须等9号到达,或主动向acceptor去请求9号决议,之后才能学习9号、10号决议。

4. 异常情况、持久存储

在算法执行的过程中会产生很多的异常情况,比如proposer宕机、acceptor在接收proposal后宕机,proposer接收消息后宕机,acceptor在accept后宕机,learn宕机等,甚至还有存储失败等诸多错误。

但无论何种错误必须保证paxos算法的正确性,这就需要proposer、aceptor、learn都做能持久存储,以做到server”醒来“后仍能正确参与paxos处理。

  • propose该存储已提交的最大proposal编号、决议编号(instance id)
  • acceptor储已promise的最大编号;已accept的最大编号和value、决议编号
  • learn存储已学习过的决议和编号

以上就是paxos算法的大概介绍,目的是对paxos算法有粗略了解,知道算法解决什么问题、算法的角色及怎么产生的,还有就是算法执行的过程、核心所在及对容错处理的要求。

但仅根据上面的描述还很难翻译成一个可执行的算法程序,因为还有无限多的问题需要解决:

  • Leader选举算法
  • Leader宕机,但新的Leader还未选出,对系统会有什么影响
  • 更多交叉在一起的错误发生,还能否保证算法的正确性
  • learn到达该怎么学习决议
  • instance no、proposal no是该维护在哪里?
  • 性能

众多问题如雪片般飞来,待这些都逐一解决后才能讨论实现的问题。当然还有一个最重要的问题,paxos算法被证明是正确的,但程序如何能被证明是正确的?

更多的请参考后面的章节。

[转]Paxos算法1-算法形成理论

原文转自http://www.cnblogs.com/chen77716/archive/2011/01/27/2130804.html

Paxos算法的难理解与算法的知名度一样令人敬仰,从我个人的经历而言,难理解的原因并不是该算法高深到大家智商不够,而在于Lamport在表达该算法时过于晦涩且缺乏一个完整的应用场景。如果大师能换种思路表达该算法,大家可能会更容易接受:

  • 首先提出算法适用的场景,给出一个多数读者能理解的案例
  • 其次描述Paxos算法如何解决这个问题
  • 再次给出算法的起源(就是那些希腊城邦的比喻和算法过程)

Lamport首先提出算法的起源,在没有任何辅助场景下,已经让很多人陷于泥潭,在满脑子疑问的前提下,根本无法继续接触算法的具体内容,更无从体会算法的精华。本文将换种表达方法对Paxos算法进行重新描述。

我们所有的描述都假设读者已经熟读了Lamport的paxos-simple一文,因此对各种概念不再解释。

除了Lamport的几篇论文,对Paxos算法描述比较简洁的中文文章是:http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95,该文翻译的比较到位,但在关键细节上还是存在一些歧义和一些对原文不正确的理解,可能会导致读者对Paxos算法更迷茫,但阅读该文可以快速地对Paxos算法有个大概的了解。

1.应用场景

(1)分布式中的一致性

Paxos算法主要是解决一致性问题,关于“一致性”,在不同的场景有不同的解释:

  • NoSQL领域:一致性更强调“能读到新写入的”,就是读写一致性
  • 数据库领域:一致性强调“所有的数据状态一致”,经过一个事务后,如果事务成功,所有的表数据都按照事务中的SQL进行了操作,该修改的修改,该增加的增加,该删除的删除,不能该修改的修改了,该删除的没删掉;如果事务失败,所有的数据还是在初始状态;
  • 状态机:在状态机中的一致性更强调在每个初始状态一致的状态机上执行一串命令后状态都必须相互一致,也就是顺序一致性。Paxos算法中的一致性指的就是这种情况,接下来我们会对这种场景进一步讨论。

(2)MQ

假如所有系统的Log信息都写入一个MQ Server,然后通过MQ把每条Log指令发异步送到多个Log Server写入文件(写入多个Log Server的原因是对Log文件做备份以防数据丢失),则所有Log Server上的数据肯定是一致的(Log内容及顺序完全相同),因为MQ本身就有排序功能,只要进了Q数据也就有了序,相当于编了全局唯一的号,无论把这些数据写入多少个文件,只要按编号,各文件的内容必定是一致的,但一个MQ Server显然是一个单点,如果宕了会影响整个系统的可用性。

(3)多MQ

要解决MQ单点问题,首选方案是采用多个MQ Server,即使用一个MQ Cluster,客户端可以访问任意MQ Server,不同的客户端可能访问不同MQ Server,不同MQ Server上的数据内容、顺序可能不一致,如果不解决这个问题,每个MQ Server写入Log Server的内容就不一致,这显然不是我们期望的结果。

(4)NoSQL中的数据更新

一般的NoSQL都会通过数据复制的形式保证其可用性,但客户端对多数据进行操作时,可能会有很多对同一数据的操作发送的某一台或几台Server,有可能执行:Insert、Update A、Update B….Update N,就一次Insert连续多次Update,最终复制Server上也必须执行这一的更新操作,如果因为线程池、网络、Server资源等原因导致各复制Server接收到的更新顺序不一致,那边这样的复制数据就失去了意义,如果在金融领域甚至会造成严重的后果。

上面这些不一致问题性正是Paxos算法要解决的,当然这些问题也不是只有Paxos能解决,在没有Paxos之前这些问题也得到了解决,比如通过使用双Master模式的MQ解决MQ单点问题;通过使用Master Server解决NoSQL的复制问题,但这些解决方法都存在一些缺陷,要么难水平扩展,要么影响可用性。当然除了Paxos算法还有其他一些算法也试图解决这类问题,比如:Viewstamped Replication算法。

上面描述的这些场景的共性是希望多Server之间状态一致,也就是一致性,再看中文Wiki开篇提到的:

在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致

大家或许会对该描述有更深的理解。

2.Paxos如何解决这类问题

Paxos对这类问题的解决就是试图对各Server上的状态进行全局编号,如果能编号成功,那么所有操作都按照编号顺序执行,一致性就不言而喻。当Cluster中的Server都接收了一些数据,如何进行编号?就是表决,让所有的Server进行表决,看哪个Server上的哪个数据应该排第一,哪个排第二…,只要多数Server同意某个数据该排第几,那就排第几。

很显然,为了给每个数据唯一编号,每次表决只能产生一个数据,否则表决就没有任何意义。Paxos的算法的所有精力都放在如何在一次表决只产生一个数据。再进一步,我们称表决的数据叫Value,Paxos算法的核心和精华就是确保每次表决只产生一个Value。

3.Paxos算法

我们对原文的概念加以补充:

  • promise:Acceptor对proposer承诺,如果没有更大编号的proposal会accept它提交的proposal
  • accept:Acceptor没有发现有比之前的proposal更大编号的proposal,就批准了该proposal
  • chosen:当Acceptor的多数派都accept一个proposal时,该proposal就被最终选择,也称为决议

也就是说,Acceptor对proposer有两个动作:promise和accept

下面的解释也主要围绕着”Only a single value is chosen, “, 再看下条件P1,

P1:An acceptor must accept the first proposal that it receives.

乍一看,这个条件是显然的,因为之前没有任何value,acceptor理所当然地应该accept第一个proposal,但仔细想想,感觉P1这个条件很不严格,到底是一个对问题的简单描述还是一个数学上严格的必要条件?这些疑问归结为2个问题:

(1)这个条件本质上在保证什么?

(2)第二个proposal怎么办?

在后续的算法中看到一个Acceptor是否批准一个Value与它是否是第一个没有任何关系,而与这个Proposal的编号有关。那岂不说明P1没有得到保证?开始我也百思不得其解,后来经过跟朋友交流发现,P1中的”accept”其实是指acceptor对proposer的”promise”,就是语言描述跟算法的步骤描述之间存在歧义,因此我认为对算法问题还是应该采用数学语法而非文字语言。

所以,P1是强调了第一个proposal要被promise,但第二个还未提到,这也是疑问之一。

也很显然的是,单靠P1是无法保证Paxos算法的,因可能无法形成多数派,那接下来的讨论应该是考虑如何弥补P1的缺点,使其可以保证Paxos算法,就是我们希望未来的条件应该说明:

  • 如何解决P1中无法形成多数派的问题
  • 第二个proposal如何选择

于是约束P2出现了:
P2:If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

P2的出现让人大跌眼镜,P2并没沿着P1的路向下走,也没有解决P1的上述2个不完备,而是从另一个侧面讨论如何保证只能选出一个Value。P1讨论的是该如何选择,P2讨论的是一旦被选出来,之后的选择应该不变,就是P1还在讨论选的问题,P2已经选出来了,中间有个断层,怎么选的没有讨论。

其实从后面Lamport不断对P2增强可以看出,P2里面蕴含着P1(通过proposal编号,第一次之前没有编号,所以选择),P2才真正给出了怎么选择的具体过程,从事后分析看,P1给出了第一个该怎么选,P2给出了所有的该怎么选,条件有点重复。所以,把P1和P2看作是两个独立条件的做法是不准确的,因而中文wiki中提到“如果 P1 和 P2 都能够保证,那么约束2就能够保证 ”,对细微理解有一定的影响。

也不是说P1就没有用,反过来看,P2是个未知问题,而P1是这个未知问题的已知部分,从契约的角度来看,P1就是个不变式,任何对P2的增强都不能过了头以至于无法满足P1这个不变式,也就是说,P1是P2增强的底线。

那还有没有其他的不变式需要遵守?是否在对P2增强的过程中已破坏了这些未知的不变式?这些高难度的问题牵扯到Paxos算法正确性,要看MIT的严格的数学证明,已超出了本文。

另外,中文Wiki对P2的描述是:“P2:一旦一个 value 被批准(chosen),那么之后批准(chosen)的 value 必须和这个 value 一样 。”,原文采用higher-numbered 更能描述未来对proposal进行编号这个事实, 而中文采用“之后,已经完全失去这个意义。

我们暂时按下P1不表,近距离观察一下P2,为了保证每次选出一个value,P2规定在一个Value已经被选出的情况下,如果还有其他的proposer提交value,那之后批准的value应该跟前一个一致,就是在事实上已经选定一个value时,之后的proposer不能提交不同的value把之前的结果打乱。这是一个泛泛的描述,但如果这个描述能得到实现,paxos算法就能得到保证,因此P2也称”safety property”。

接下来的讨论都时基于“If a proposal with value v is chosen”,如何保证“then every higher-numbered proposal that is chosen has value v ”,具体怎么做到“a proposal with value v is chosen”暂且不谈。

P2更多是从思想层面上提出来该如何解决这个问题,但具体的落实工作需要很多细化的步骤,Lamport是通过逐步增强条件的方式进行落实P2,主要从下面几个方面进行:

  • 对整个结果提出要求(P2)
  • 对Acceptor提出要求(P2a
  • 对Proposer提出要求(P2b
  • 对Acceptor与Proposer同时提出要求(P2c

Lamport为什么能把过程划分的如此清楚已经不得而知,但从Lamport发表的文章来看,他对分布式有很深的造诣,也持续了很长的时间,能有如此的结果,与他对分布式的基础与背后的巨大努力有很大关系。但对我们而言,不知过程只知个结果,总感觉知其然不知其所以然。

我们沿着上面的思路继续:

P2a :If a proposal with value v is chosen, then every higher-numbered proposal accepted by any acceptor has value v.

这个条件是在限制acceptor,很显然,如果P2a 得到了满足,满足P2是肯定的,但P2a 的增强破坏了P1不变式的底线,具体参考原文,所以P2a本身没啥意义,转而从proposer端进行增强。

P2b :If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

这个条件是在限制proposer,如果能限制住proposer,对acceptor的限制当然能被满足的。同时,因为限制proposer必须提交value v,也就顺便保证了P1(第一个肯定是value v)

但P2b 是难以实现的,难实现的原因是多个proposer可以提交任意value的proposal,无法限制proposer不能提交某个value,因此需要寻找P2b的等价条件:

P2c :For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that either

(a) no acceptor in S has accepted any proposal numbered less than n, or

(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S.

根据原文,P2c 里面蕴含了P2b ,但由P2c 推导P2b是最难理解的部分。

首先要清楚P2c 要做什么,因为P2b 很难直接实现,P2c 要做的就是解决的P2b问题,也就是要解决“如果value v被选择了,更高编号的提案已经具有value v”,也就是说:

  • R:“For any v and n, if a proposal with value v and number n is issued”是结果,而
  • C:“ then there is a set S consisting… ”是条件

就是要证明如果C成立,那么结果R成立,而原文的表达是“如果R成立,那么存在一个条件R”,容易让人搞混因果关系,再次感叹如果使用数学符号表达这样的歧义肯定会减少很多。

P2c 解决问题的思路是:不是直接尝试去满足P2b ,而是寻找能满足P2b 的一个充分条件,如果能满足这个充分条件,那P2b 的满足是显然的。还要强调一点的是proposer可以提交任意的value,你怎么能限制我提交的必须是value v呢?其实原文中的“For any v and n, if a proposal with value v and number n is issued ”是指“如果一个编号为n的proposal提交value v,并且value v能被acceptor所接受”,要想被接受就不能随便提交一个value,就必须是一个受限制的value,这里讨论的前提是value v是要被接受的。然后我们再看下,是否满足了条件C,结果R就成立。

(a) no acceptor in S has accepted any proposal numbered less than n

如果这个条件成立,那么n是S中第一个proposal,根据P1,必须接受,所以结果R成立

(b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S

这个证明先假设编号为n的proposal具有value X被选择,肯定存在一个结合C,其中的每个acceptor都接受了value X,而集合S中的每个Acceptor都接受了value v,因为S、C都是多数派,所以存在一个公共成员u,既接受了X,又接受了v,为了保证选择的唯一性,必须X=v.

大家可能会发觉该证明有点不太严格,“小于n的最大编号”与n之间还有很多proposal,那些proposal也有一些value,那些value会不会不是v?

这个就会用到原文中的数学归纳法,就是任意的编号m的proposal具有了value v,那么n=m+1是,根据上面也是具有value v的,那么向后递推,任意的n >m都具有value v。中文wiki中的那个归纳证明不需要对m…n-1正推,而对n反证,通过数学归纳正推完全可以得出最终结果。

也就是说,P2c 是P2b 的一个加强,满足P2c 就能满足P2b

我们再近距离观察下P2c ,发现只要在proposer提交提案前,咨询一下acceptor,看他们的最高编号是啥,他们是否选择了某个value v,再根据acceptor的回答进行选择新的编号、value提交,就可以满足P2c。通过编号,可以把(a)和(b)两个条件统一在一起。

其实P2c要表达的思想非常简单:如果前面有value v选出了,那以后就提交这个value v;否则proposer决定提交哪个value,具体做法就是事前咨询,事中决定,事后提交,也就是说可以通过消息传递模型实现。Lamport通过条件、集合、归纳证明等形式表达该问题,而没提这样做的目的,会导致理解很困难。大家可能会比较疑惑,难道自始至终只能选出一个value?其实这里的选出,是指一次选举,而不是整个选举周期,可以多次运行paxos,每次都只选出一个value。

满足P2c从侧面也反映出要想提交一个正确的value v,要对proposer、acceptor同时进行限制,仅限制一方问题是无法解决的。

再回顾下条件之间的递推关系P2c =>P2b =>P2a =>P2,就是说P2c 最终保证了P2,也就是解决了如何做到一个value v被选择之后,被选择的编号更大的proposal都具有value v,P2c不仅保证P2的结果,更提出了“如何选”的问题,就是上面分阶段进行,这就填补了P1与P2之间缺少如何选的断层,还有P1的2个不完备问题从直观上感觉会得到解决,具体的要看算法过程章节。

P1的不完备问题:

P2c也顺便解决了P1的不完备问题,因为proposer提交的value是受acceptor限制的,就不会在一次选举中提交两个不同的value,即使能提交也会因为proposal编号问题有一个会被拒绝,从而能保证能形成多数派。

另一个关于第二个该怎么选的不完备问题,也是显然的了。

再次证明了,P2里面蕴含了P1,P1只是未知问题P2的不变式。

Paxos学习笔记——overall

一、一些废话

第一次听说Paxos算法,是在2011年的春节期间,与刘君吃饭时听到他提起的。后来,我渐渐了解到,Paxos乃是Google产品的重要基础,最初的使用是在Chubby中,后来似乎在Megastore中再次使用。

6月之后,既然GRE败了,那么还是先把开题的任务搞定。我觉得我开题其实是个巨大的坑,同组的其他人要么开了可以忽悠的题目,要么是别人已经做好了,但是boss不知道的题目。我开的题则是在我某天包夜,喝咖啡喝的恍惚的时候想到的,但是现在想一想,也不是怎么靠谱,甚至有可能毫无意义。无论如何,都要从Paxos算法的实现做起,刘君说,这个算法很难实现,确实如此。可笑的是,算法的实现已经很困难了,而且别人早已有了很多成功的Paxos实现,但是我却妄图在这些成功的方法上加上一些愚蠢的改动,完全是自虐。整个毕业设计的工作计划争取在放假结束前写完,这是后话

Paxos的文章很多,最为重要的自然是Lamport所写的那些文章http://research.microsoft.com/en-us/um/people/lamport/pubs/pubs.html),所以一开始我打算先把他的论文看完,但是,看了几天,我就发现这是一个极为困难的任务,首先,他的文章很多,其次,他的文章确实不太好懂。所以我退而求其次,转向了Paxos的wikihttp://en.wikipedia.org/wiki/Paxos_(computer_science)),wiki比较浅显易懂,而且涵盖了更多的内容,当我完成了这部分的工作之后,再去相应的论文中寻找更多的细节与证明。所以下面的内容大量参考wiki上的内容,许多渣翻译。

二、名字的由来与故事

来自Lamport虚构的希腊的Paxos岛群中所使用的立法一致系统(legislative consensus system)。

具体的故事是这样的(摘自中文Paxos wiki(http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95)):

为描述 Paxos 算法,Lamport 虚拟了一个叫做 Paxos 的希腊城邦,这个岛按照议会民主制的政治模式制订法律,但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员,议长或者传递纸条的服务员都不能承诺别人需要时一定会出现,也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题(Byzantine failure,即虽然有可能一个消息被传递了两次,但是绝对不会出现错误的消息);只要等待足够的时间,消息就会被传到。另外,Paxos 岛上的议员是不会反对其他议员提出的决议的。

三、Safety and liveness properties,安全性和活性?好吧,我也不知道怎么翻

Paxos中定义了三条安全性质,并且保证在没出错时一直保证之:

  • 非平凡性——Non-triviality
    只有提议(propose)的值(value,下同,具体含义的理解在本节最后)才能被获知(learn)。
  • 一致性——Consistency
    只有一个值能被获知。这意味着两个不同的获知者不会得到不同的值。我的理解是一次Paxos执行中
  • 活性——Liveness(C,L)
    如果值C被提议了,那么最终获知者L将会得到某些值(如果足够多的处理者保持没有出错的话)。

看到这里,恐怕还是云里雾里,不知道这三条性质具体是指什么。这里先讲讲关于value的我的理解,value在这里是一个很抽象的概念,既可以是一个数字,也可以是一套方案,一系列操作,所以value的具体含义在于开发者针对什么问题使用了Paxos算法,此时,value的含义就是这个问题中需要保持一致的对象

这三条性质保证了一致性的需要,所以Paxos算法其实就是围绕这如何保持这三条性质展开的。关于为何满足这三条性质就能保证一致状态,Lamport也给出了证明。

四、假设与定义

1、假设

Paxos的假设分为两方面,一方面是关于处理者的,一方面是关于网络的。我认为,这是由于假设中的限制非常少,才使得满足了这些假设的算法意义非凡。

关于处理者,processors,是指故事中的议员,或是真正的实现中的处理程序,节点。相关的假设如下:

  • 处理者以任意速度进行处理
  • 处理者会失效,无法工作
  • 拥有稳定存储的处理者可以在失效之后再次加入Paxos
  • 处理者不会勾结欺骗,即无拜占庭错误

关于网络,networks,是指故事中的消息传递机制,或是真正的实现中的网络系统,事实上,也就是互联网。相关假设如下:

  • 处理者可以发送消息给其他的处理者
  • 消息被异步地发送,并且花费任意长的时间才能收到
  • 消息会丢失,顺序错误,重复
  • 消息不会出现欺骗,即无拜占庭错误

2、处理者数量

一般来说,一个一致性算法的运行使用2F+1个处理者,并且可以容忍同时F个处理者的失效,即容忍少于一半的失效。然而,经过配置的话,这个协议也可以容忍更多的失效,只要失效不会产生地过快。

所谓不会失效地过快,是指不会同时一起失效,而是一个接一个地失效。这里提到的方法是使用备用处理者代替失效处理者。举例来说,5台服务器,原本可以容忍2台失效,现在使用如下,将3台作为活跃机使用,2台作为备用机使用,当活跃机失效时,就重新配置,让备用机代替活跃机工作,当然,前提是失效只会在重新配置完成后才发生,这样最终可以容忍3台失效。我认为,这样的方法实际上降低了服务器的可用性,意义不太大。

3、角色

终于到了一个很关键的地方,上面提到的处理者有不同的角色,不同角色的处理者作不同的处理动作,他们是:client, acceptor, proposer, learner, and leader。在实现时,往往一个处理者要同时扮演几个角色,这并不会影响协议的正确性,而且这也很平常,因为合并角色可以减少延迟,或者减少消息数量。

  • 客户,Client
    客户会向分布式系统发送请求,然后等待回应。例如,发往分布式文件服务器的写请求。
  • 决议者,Acceptor
    决议者是协议中的容错记忆体。一定数量的决议者被归为一组,称为额定数(Quorum)。任何发往决议者的消息都必须发往额定数量的决议者,任何来自决议者的消息都应该 由额定数量的决议者分别发出同个消息的拷贝,否则将会被忽略。简单来说,消息必须有Quorum份。
  • 提议者,Proposer
    提议者提议各异客户请求,尝试让决议者同意它,并且在发生冲突时作为协调者(Coordinator)推动协议继续进行。
  • 获知者,Learner
    获知者作为协议的副本因子,一旦一个客户请求被决议者所同意,那么获知者将会采取相应的行动,例如,执行请求并回应给客户。额外的获知者可以提供更高的可用性
  • 领导者,Leader
    Paxos需要一个高阶的提议者(成为领导者)来推动协议的进行。有可能很多处理者都会认为自己是领导者,但是协议保证最终仅有一个会被选为领导者。如果两个处理者认为他们都是领导者,将会不停地提出冲突的更新请求,那么会拖延整个协议。安全性无论如何将会被保证。

4、额定数(Quorum

额定数表示了Paxos的安全性,说明至少有一些存活的处理者知道结果。

额定数被定义为决议者集合中的一系列子集,并且这一系列子集中的任意两个子集的交集都不为空。典型的额定数是决议者的多数。比如,有决议者集合{A,B,C,D},一个多数额定可以是其中任意的三个决议者:: {A,B,C}, {A,C,D}, {A,B,D}, {B,C,D}。更一般化的情况是,可以给决议者赋予任意的正权值,此时,额定数就被定义为了子集总权值大于全集总权值的一半的那些子集。

5、提议编号与同意值(Proposal Number & Agreed Value

每次尝试定义一个大家都同意的值,都是通过提议的形式来完成的。一个指定的提议者的每个提议都有一个唯一的提议编号。

五、典型实现方案

在大多数的Paxos实现方案中,只有三种角色:Proposer, Acceptor and Learner。这能显著降低消息复杂度,在不牺牲正确性的前提下。

通过合并角色,整个协议缩减成了一个有效的客户-主人-副本(client-master-replica)风格的部署,这是数据库社区的典型部署。使用Paxos系列方法的好处是安全性的保证。

一个典型实现的数据流将在Typical Multi-Paxos deployment中提到。

六、Paxos的系列算法

1990,Paxos算法就已经被Lamport所创立,但是直到1998年关于Paxos的论文才发表。之后有许多的工作围绕着Paxos展开,但是这都是围绕着Paxos的核心而做的修修补补,或者结合不同的情景与需求所做的改动,最为核心的仍然是Lamport最开始描述的Paxos,因为这个核心才是保证一致性的关键。

1、Basic Paxos

这个协议是Paxos系列中最基础的一个。每个Basic Paxos协议的实例都会决定一个输出值。协议可以进行很多轮(round),每轮有2个阶段(Phase)。当提议者无法与额定数量的决议者通讯时,提议者不应该启动Paxos。

描述如下(名称不翻了,不然感觉怪怪的):

Phase 1a: Prepare
一个提议者(即领导者)创建一个提议,这个提议用一个数字N进行标识。这个数字必须比这个提议者曾使用过的提议编号都大。然后,它发送一个准备(prepare)消息(消息中包括了这个提议)给额定数量的决议者。

Phase 1b: Promise
如果决议者收到的提议编号N比任何之前收到的(来自任何提议者的)提议编号都大的话,那么决议者必须返回一个保证(promise),保证忽略之后收到的任何提议编号小于N的提议。如果一个决议者在之前已经同意了某个值,那么它在回应提议者的时候,必须附加上最新同意的提议编号以及相应的值。
否则,决议者可以忽略收到的提议。甚至可以不用回应它。然后,为了优化的目的,发送回一个拒绝(Nack)回应可以告诉提议者可以停止尝试在提议N上达到一致。

Phase 2a: Accept Request
如果一个提议者从决议者处收到了足够多的保证(额定数个),那么这个提议者需要给它的提议设定一个值(value)。如果某个决议者之前已经同意了某个提议的话,那么它已经将它同意的值发送给了提议者,这时,提议者必须将值设为已经收到的值中(在promise中一起返回的,都是各决议者已经同意的值)编号最大的提议的值。否则,它可以直接设定自己的独立的值。
然后,提议者发送一个请求接受(Accept Request)消息给额定数量的决议者,这个消息中,包含了提议中选择的值。

Phase 2b: Accepted
如果一个决议者(Acceptor)收到了提议N的接受请求消息,它必须接受它,当且仅当它还没有向一个编号大于N的提议进行保证时。这种情况下,它应该注册这个相应的值v,然后发送一个已接受(Accepted)消息给提议者和每个获知者。否则,它可以忽略这个接受请求。

每轮过程会在下面两种情况下失败:多个提议者发送了冲突的准备消息;或者是提议者没有收到额定数目的回应(保证已接受)。在这些情况下,需要开始新的一轮,并使用新的更高的提议编号。

注意到当决议者接受一个请求时,他们也会告知提议者的领导。因此,Paxos也可以用于在一个集群的节点中选择一个领导者(Leader)

下面是 Basic Paxos协议 的图示。注意在保证消息(Va,Vb,Vc)中返回的值在第一轮实例中通常是null,下面写出来是为了完整性。

Message flow: Basic Paxos

(one instance, one successful round)

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Basic Paxos中的出错情况

最简单的出错情况是冗余获知者的失效,或者一个决议者的失效,但此时仍有额定数量的决议者存活。这种情况下,不需要恢复操作,也不需要额外的几轮过程或几轮消息。如下所示:

Message flow: Basic Paxos, failure of Acceptor

(Quorum size = 2 Acceptors)

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |          |  |  !       |  |  !! FAIL !!
   |         |<---------X--X          |  |  Promise(N,{Va,Vb})
   |         X--------->|->|          |  |  Accept!(N,Vn)
   |         |<---------X--X--------->|->|  Accepted(N,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |          |  |

 Message flow: Basic Paxos, failure of redundant Learner

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N,Vn)
   |         |          |  |  |       |  !  !! FAIL !!
   |<---------------------------------X     Response
   |         |          |  |  |       |

下一个出错情况是当提议者在提议了一个值之后,但是在达到共识前的时候失效了。忽略选择领导者的问题,例子如下:

Message flow: Basic Paxos, failure of Proposer

(re-election not shown, one instance, two rounds)

Client  Leader         Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(N)
   |      |<------------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |      |             |  |  |       |  |
   |      |             |  |  |       |  |  !! Leader fails during broadcast !!
   |      X------------>|  |  |       |  |  Accept!(N,Vn)
   |      !             |  |  |       |  |
   |         |          |  |  |       |  |  !! NEW LEADER !!
   |         X--------->|->|->|       |  |  Prepare(N+1)
   |         |<---------X--X--X       |  |  Promise(N+1,{Vn})
   |         X--------->|->|->|       |  |  Accept!(N+1,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N+1,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

最为复杂的情况是多个提议者相信自己是领导者。举例来说,当前的领导者失效了,并且在之后恢复了,但是其他的提议者已经重新选举了一个新的领导者。这个恢复了的领导者并不知道这件事,然后尝试开始新的一轮过程,但是这与当前的领导者冲突了。

Message flow: Basic Paxos, dueling Proposers

(one instance, four unsuccessful rounds)

Client   Proposer      Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(N)
   |      |<------------X--X--X       |  |  Promise(N,{Va,Vb,Vc})
   |      !             |  |  |       |  |  !! LEADER FAILS
   |         |          |  |  |       |  |  !! NEW LEADER (knows N)
   |         X--------->|->|->|       |  |  Prepare(N+1)
   |         |<---------X--X--X       |  |  Promise(N+1,{Va,Vb,Vc})
   |      |  |          |  |  |       |  |  !! OLD LEADER recovers
   |      |  |          |  |  |       |  |  !! OLD LEADER tries N+1, denied
   |      X------------>|->|->|       |  |  Prepare(N+1)
   |      |<------------X--X--X       |  |  Nack(N+1)
   |      |  |          |  |  |       |  |  !! OLD LEADER tries N+2
   |      X------------>|->|->|       |  |  Prepare(N+2)
   |      |<------------X--X--X       |  |  Promise(N+2,{Va,Vb,Vc})
   |      |  |          |  |  |       |  |  !! NEW LEADER proposes, denied
   |      |  X--------->|->|->|       |  |  Accept!(N+1,Vn)
   |      |  |<---------X--X--X       |  |  Nack(N+2)
   |      |  |          |  |  |       |  |  !! NEW LEADER tries N+3
   |      |  X--------->|->|->|       |  |  Prepare(N+3)
   |      |  |<---------X--X--X       |  |  Promise(N+3,{Va,Vb,Vc})
   |      |  |          |  |  |       |  |  !! OLD LEADER proposes, denied
   |      X------------>|->|->|       |  |  Accept!(N+2,Vn)
   |      |<------------X--X--X       |  |  Nack(N+3)
   |      |  |          |  |  |       |  |  ... and so on ...

2、Multi-Paxos

典型的Paxos实现需要一个关于同意值(agreed value)的持续流(continuous stream),这些同意值用作分布式状态机的命令。如果每个命令都是一个Basic Paxos的实例的结果,那么这将意味着很大量的开销。

如果领导者相对稳定的话,phase 1就变得不再必要。因此,如果之后的实例都使用相同的领导者,那么phase 1就可以跳过。

为了达到这种方式,实例编号I要被包含在每个值(value)中。Multi-Paxos在保证容错的同时,将消息延迟(从提议到被他人得知)从4步延迟降到了2步延迟。

Message flow: Multi-Paxos, start

(first instance with new leader)

 Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,Vn)
   |         |<---------X--X--X------>|->|  Accepted(N,I,Vn)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Message flow: Multi-Paxos, steady-state

(subsequent instances with same leader)

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N+1,I,W)
   |         |<---------X--X--X------>|->|  Accepted(N+1,I,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

典型Multi-Paxos实现

Paxos系列最常见的实现就是Multi-Paxos,特别是参加Paxos的处理者分别是提议者(Proposers),决议者(Acceptors)和获知者(Learners)。于是消息流可以被优化如下:

Message flow: Collapsed Multi-Paxos, start

(first instance with new leader)

 Client      Servers
   |         |  |  | --- First Request ---
   X-------->|  |  |  Request
   |         X->|->|  Prepare(N)
   |         |<-X--X  Promise(N,I,{Va,Vb,Vc})
   |         X->|->|  Accept!(N,I,Vn)
   |         |<-X--X  Accepted(N,I)
   |<--------X  |  |  Response
   |         |  |  |

Message flow: Collapsed Multi-Paxos, steady state

(subsequent instances with same leader)

 Client      Servers
   X-------->|  |  |  Request
   |         X->|->|  Accept!(N+1,I,W)
   |         |<-X--X  Accepted(N+1,I)
   |<--------X  |  |  Response
   |         |  |  |

3、优化

很多的优化降低了消息的复杂度和大小。这些优化总结如下:

“可以以 额外的一个消息延迟 的代价获得消息数量的减少,方式是使用一个特别的获知者,当它发现一个值被选择之后,由它来通知其他的获知者。然后决议者只发送已接受(Accepted)消息给这个特别的获知者。在大多数的应用中,领导者和特别的获知者的角色通常是由相同的处理者所担当的。

“领导者可以只发送准备(Prepare)消息和请求接受(Accept!)消息给额定数量的决议者(而不是全部)。只要额定数中的所有决议者都能正常工作,并且可以和领导者和获知者通信,那么就没有必要让额定数之外的决议者做任何事。

“决议者不在乎被选择的是哪个值。他们仅仅对准备(Prepare)消息和请求接受(Accept!)消息做出回应,并在没有发生失效时保证只有一个值会被选择。然而,如果一个决议者确实获知了是哪个值被选择了之后,那么它可以把值储存在可靠稳定的存储器上,然后擦除它保存在那的任何其他信息。在这之后如果决议者又接到了准备消息或者请求接受消息,就可以略过Phase 1b和Phase 2b,而直接通知领导者它选择的值。

“领导者可以在其请求接受消息中发送值v的哈希(hash of v)给一些决议者,而不是发送整个值v。获知者将会或者哪个值被选择了,如果它从额定数量的决议者处收到了关于值v或者它的哈希的已接受(Accepted)消息,并且这些消息中至少有一条包含了v,而不是它的hash。然而,领导者可能会只接受了包含v的hash的保证(Promise)消息,而不是v的确切值,但是在它的Phase 2a中必须要使用v值。如果这种情况发生的话,领导者就不能执行Phase 2a,直到它与一些知道v的处理者通信并取得v值。

“提议者只可以发送提议给领导者,而不是所有的协调者(Coordinator)。然而,这需要把领导者选择算法的结果广播给所有的提议者,这是昂贵的开销。因此,更好的方案是发送提议给所有的协调者,在这种情况下,只有协调者内部需要知道领导者是谁。

“取代每个决议者发送已接受(Accepted)消息给每个获知者的方案,决议者可以发送已接受消息给领导者,然后领导者可以在一个值被选择时通知获知者。然而,这会增加一个额外的消息延迟。

“最后,观察到Phase 1对于第一轮(Round 1)是不必要的,第一轮的领导者可以从发送请求接受(Accept!)消息开始,请求接受消息中包含提议值(proposed value)。”

4、Cheap Paxos

Cheap Paxos继承了Basic Paxos,使用F+1个主处理者和F个辅处理者,能在每次失效发生后动态重新配置,能够容忍F个失效。

需要的处理者数量的减少,是以活力的损失为代价的;如果太多主处理者在短时间内失效,整个系统就需要暂停,直到辅处理者重新配置系统。在稳定的期间,辅处理者不参加协议的执行。

“只有两个处理者p和q,那么一个处理者不能辨别另一个处理者的失效是真的失效还是由于通信介质的失效。于是需要第三个处理者。然而,第三个处理者并不必加入到选择命令序列的任务中。它需要做的,是当p或者q失效时,它能够启动,当p或者q能够继续操作系统时,它又可以休息了。因此第三个处理者可以是小的/慢的/便宜的(small/slow/cheap)那个处理者,或者是一个主要投入到其他工作中去的处理者。”

Message flow: Cheap Multi-Paxos

3 main Acceptors, 1 Auxiliary Acceptor, Quorum size = 3, showing failure of one main processor and subsequent reconfiguration

            {  Acceptors   }
Proposer     Main       Aux    Learner
|            |  |  |     |       |  -- Phase 2 --
X----------->|->|->|     |       |  Accept!(N,I,V)
|            |  |  !     |       |  --- FAIL! ---
|<-----------X--X--------------->|  Accepted(N,I,V)
|            |  |        |       |  -- Failure detected (only 2 accepted) --
X----------->|->|------->|       |  Accept!(N,I,V)  (re-transmit, include Aux)
|<-----------X--X--------X------>|  Accepted(N,I,V)
|            |  |        |       |  -- Reconfigure : Quorum = 2 --
X----------->|->|        |       |  Accept!(N,I+1,W) (Aux not participating)
|<-----------X--X--------------->|  Accepted(N,I+1,W)
|            |  |        |       |

5、Fast Paxos

Fast Paxos推广了Basic Paxos,降低了端到端消息延迟。在Basic Paxos中,从客户端请求到获知结果的消息延迟是3个消息延迟。Fast Paxos只要2个消息延迟,但是需要客户端发送请求到多个目标处。

直觉地,如果领导者没有用来提交的值,那么客户端可以直接发送一个请求接受(Accepted!)消息给决议者。决议者如同在Basic Paxos中一样进行回应,发送已接受(Accepted)消息给领导者,这里从客户端到获知者只要2个消息延迟。

如果领导者检测到了一个冲突,它会用以下的方法来解决冲突,它在新的一轮中发送请求接受(Accepted!)消息,在新的一轮中,可以正常接受(Accepted)。这个协调恢复方法(coordinated recovery technique)从客户端到获知者需要4个消息延迟。

当领导者发现恢复方法正在启动时,可以进行最后的优化,允许决议者自身进行冲突恢复。因此,非协调冲突恢复需要3个消息延迟(如果所有的获知者都是决议者的话,只需要2个消息延迟)。

Message flow: Fast Paxos, non-conflicting

Client    Leader         Acceptor      Learner
   |         |          |  |  |  |       |  |
   |         X--------->|->|->|->|       |  |  Any(N,I,Recovery)
   |         |          |  |  |  |       |  |
   X------------------->|->|->|->|       |  |  Accept!(N,I,W)
   |         |<---------X--X--X--X------>|->|  Accepted(N,I,W)
   |<------------------------------------X--X  Response(W)
   |         |          |  |  |  |       |  |

Message flow: Fast Paxos, conflicting proposals

Conflicting proposals with uncoordinated recovery. Note: the protocol does not specify how to handle the dropped client request.

Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      X------->|->|->|->|      |  |  Any(N,I,Recovery)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Concurrent conflicting proposals
 |  |      |        |  |  |  |      |  |  !!   received in different order
 |  |      |        |  |  |  |      |  |  !!   by the Acceptors
 |  X--------------?|-?|-?|-?|      |  |  Accept!(N,I,V)
 X-----------------?|-?|-?|-?|      |  |  Accept!(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Acceptors disagree on value
 |  |      |<-------X--X->|->|----->|->|  Accepted(N,I,V)
 |  |      |<-------|<-|<-X--X----->|->|  Accepted(N,I,W)
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! Detect collision & recover
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |

Message flow: Fast Paxos, collapsed roles

(merged Acceptor/Learner roles)

Client         Servers
 |  |         |  |  |  |
 |  |         X->|->|->|  Any(N,I,Recovery)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Concurrent conflicting proposals
 |  |         |  |  |  |  !!   received in different order
 |  |         |  |  |  |  !!   by the Servers
 |  X--------?|-?|-?|-?|  Accept!(N,I,V)
 X-----------?|-?|-?|-?|  Accept!(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Servers disagree on value
 |  |         X--X->|->|  Accepted(N,I,V)
 |  |         |<-|<-X--X  Accepted(N,I,W)
 |  |         |  |  |  |
 |  |         |  |  |  |  !! Detect collision & recover
 |<-----------X--X--X--X  Response(W)
 |  |         |  |  |  |

6、Generalized Paxos

推广的一致性(generalized consensus)探讨了分布式状态机(distributed state machine)的操作和用来处理状态机一致性的一致性协议(consensus protocol)之间的关系。主要的研究当冲突的提议可以以任意顺序被状态机接受时,是一致性协议的优化。例如,由冲突的提议所提议的操作是状态机中的可交换操作。

在这种情况下,冲突的操作可以都被接受,并且避免了解决冲突和重新提议被拒绝的操作所花费的延迟。

这个概念被进一步推广到可交换操作的持续增长集 上,某些这样的持续增长集被认为是稳定的(stable)(因此可以被执行这个协议)。协议追踪这些操作集,确保在允许任何不可交换操作变稳定(stable)前,一个集合中的所有提交的可交换操作都是稳定的。(这段没太懂。。。原文如下:This concept is further generalized into ever-growing sets of commutative operations, some of which are known to be stable (and thus may be executed). The protocol tracks these sets of operations, ensuring that all proposed commutative operations of one set are stabilized before allowing any non-commuting operation to become stable. 关键在于这个stable的理解上,关于stable的词出现了2个,一个是形容词stable,一个是动词stabilize,那么stabilize这个词的意思是将所谓的operation执行,然后把执行的结果输出到稳定的存储中去么,然后stable就是指执行结果已被输出到稳定存储的状态。)

举例

为了阐明Generalized Paxos,这个例子由以下部分进行表示:两个并行执行的客户端间的消息流,以及一个在2个相互独立的注册地址(A和B)处执行read/write注册操作的状态机。
可交换性表(Commutativity Table);做标记的地方表示有干扰:
                 Read(A) Write(A) Read(B) Write(B)
        Read(A) |       |    X   |       |        |
        Write(A)|   X   |    X   |       |        |
        Read(B) |       |        |       |    X   |
        Write(B)|       |        |   X   |    X   |
操作的提交序列(全局顺序):
        1:Read(A)
        2:Read(B)
        3:Write(B)
        4:Read(B)
        5:Read(A)
        6:Write(A)
        7:Read(A)
通过交换之后,一个可能的排列:
        { 1:Read(A),  2:Read(B), 5:Read(A) }
        { 3:Write(B), 6:Write(A) }
        { 4:Read(B),  7:Read(A)  }
观察结果:
  • 5:Read(A) 可以交换到3:Write(B)/4:Read(B) pair之前.
  • 4:Read(B) 可以交换到 the 3:Write(B)/6:Write(A) pair之后.
  • 实际上,交换只会发生在操作是同时提交的情况下.

Message flow: Generalized Paxos (example)

Responses not shown. Note: message abbreviations differ from previous message flows due to specifics of the protocol, see(Generalized Consensus and Paxos)for a full discussion.

           {    Acceptors   }
Client      Leader  Acceptor     Learner
 |  |         |      |  |  |         |  |  !! New Leader Begins Round
 |  |         X----->|->|->|         |  |  Prepare(N)
 |  |         |<-----X--X--X         |  |  Promise(N,null)
 |  |         X----->|->|->|         |  |  Phase2Start(N,null)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Concurrent commuting proposals
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadA)
 X-----------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         X------X-------------->|->|  Accepted(N,<ReadA,ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! No Conflict, both accepted
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Concurrent conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(<WriteB,ReadA>)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadB)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N,<WriteB,ReadA> . <ReadB>)
 |  |         |<--------X--X-------->|->|  Accepted(N,<ReadB> . <WriteB,ReadA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  | !! Conflict detected, leader chooses
 |  |         |      |  |  |         |  |    commutative order:
 |  |         |      |  |  |         |  |    V = <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         X----->|->|->|         |  |  Phase2Start(N+1,V)
 |  |         |<-----X--X--X-------->|->|  Accepted(N+1,V)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB>
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! More conflicting proposals
 X-----------?|-----?|-?|-?|         |  |  Propose(WriteA)
 |  X--------?|-----?|-?|-?|         |  |  Propose(ReadA)
 |  |         |      |  |  |         |  |
 |  |         X------X-------------->|->|  Accepted(N+2,<WriteA> . <ReadA>)
 |  |         |<--------X--X-------->|->|  Accepted(N+2,<ReadA> . <WriteA>)
 |  |         |      |  |  |         |  |
 |  |         |      |  |  |         |  |  !! Leader chooses order W
 |  |         X----->|->|->|         |  |  Phase2Start(N+2,W)
 |  |         |<-----X--X--X-------->|->|  Accepted(N+2,W)
 |  |         |      |  |  |         |  |  Stable = <ReadA, ReadB> .
 |  |         |      |  |  |         |  |           <ReadA, WriteB, ReadB> .
 |  |         |      |  |  |         |  |           <WriteA, ReadA>
 |  |         |      |  |  |         |  |

Generalized Paxos vs. Fast Multi-Paxos

上面的数据流显示了Generalized Paxos在10个消息延迟中执行了关于7个值的协议。对相同的提议值序列,Fast Multi-Paxos则需要15-17个延迟(3个需要不协调恢复的并发提议,每个需要3个延迟,加上至少2个延迟给最终需要重新提交的3个被拒绝的提议,并发的重提议可能还要加上2个额外的延迟)。 

7、Byzantine Paxos

Paxos可以被扩充以支持参加者会发生的任意错误,包括撒谎(lying),消息伪造(fabrication of  messages),与其他参加者同谋(collusion with other participants),选择性不参与(selective non-participation),等等。这些类型的错误被称为拜占庭错误(Byzantine failures),Lamport给出了结局方案。

Byzantine Paxos增加了额外的一个消息(verify),用来分发已知信息,以及核实其他处理者的动作。

Message flow: Byzantine Multi-Paxos, steady state

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |          X<>X<>X       |  |  Verify(N,I,V) - BROADCAST
   |         |<---------X--X--X------>|->|  Accepted(N,V)
   |<---------------------------------X--X  Response(V)
   |         |          |  |  |       |  |

Fast Byzantine Paxos溢出了这个额外的延迟,因为客户端可以直接发送命令给决议者。

注意到在Fast Byzantine Paxos中的已接受(Accepted)消息被发送给所有的决议者和获知者,而Fast Paxos仅将此消息发送给获知者。

Message flow: Fast Byzantine Multi-Paxos, steady state

Client    Acceptor     Learner
   |      |  |  |       |  |
   X----->|->|->|       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  |       |  |

这个失效场景与两个与两个协议相同;每个获知者等待F+1个从不同决议者处发出的同样的消息。如果这没有发生,那么决议者本身也会知道(因为他们在广播轮(broadcast round)中交换各自的消息),并且正常的决议者会再次广播这个同意值:

Message flow: Fast Byzantine Multi-Paxos, failure

Client    Acceptor     Learner
   |      |  |  !       |  |  !! One Acceptor is faulty
   X----->|->|->!       |  |  Accept!(N,I,V)
   |      X<>X<>X------>|->|  Accepted(N,I,{V,W}) - BROADCAST
   |      |  |  !       |  |  !! Learners receive 2 different commands
   |      |  |  !       |  |  !! Correct Acceptors notice error and choose
   |      X<>X<>X------>|->|  Accepted(N,I,V) - BROADCAST
   |<-------------------X--X  Response(V)
   |      |  |  !       |  |

 Virtually Synchronous Paxos(虚拟同步Paxos)

虽然虚拟同步模型与Paxos对于创建状态机副本服务和简单应用来说,有时看起来是相反方向的选择,但是近来的工作(“Virtually Synchronous Methodology for Dynamic Service Replication”)证明了合并两种模型到一个统一方案的可能性。这个方法使用虚拟同步来支持执行时期(execution epochs),在执行时期内,成员(membership)被一致性协议决定并被是稳定的(stable)。于是,容错协议就被定义在了每个时期的基础上。这个方法相比于其他方法,加强了虚拟同步模型,使其在动态Paxos服务成员(making the membership of a Paxos service dynamic)的方面,提供了更好的性能。

七、最后的吐槽

首先是我的效率太低了!这篇日志从7月底一直写到了8月中旬,虽然中间经过了开年会,放假等等,前前后后有20多天,但是,主要还是我磨磨蹭蹭的原因,如果拼命写,估计7月底就写完了。。。

嘛,也不能说是写完了,应该是翻译完了,开头还想写点自己的话,后来写到具体的算法介绍时就开始照着wiki翻译了,然后强迫症让我硬生生翻译完了。。。

最后,英转中总是这么蛋疼,讲话思维是反的,于是我的渣翻译就跟机翻一样,感觉还是完全不能看啊!