• 术语&约定
• 算法
• 一些要点
• 正确性证明
• 正确性证明（另一条思路）
• 算法的其他特性
• 实例
  • 实例1：未达成一致状态下可以accept任何具有不同的value的proposal
  • 实例2：过半数acceptor都accept了同一value并不意味着达成一致
• 问题
• 其他note
• Multi-Paxos
• 参考

术语&约定

• 系统有多个进程，进程可能失效然后重启，进程间只能靠发送消息进行通信。消息发送速率任意，消息可以重复，也有可能被网络丢弃，但不能是corrupted（即系统中没有拜占庭失效）。
• 每个进程可以扮演如下三个角色中的一个或多个：
• proposer：负责提出proposal
• acceptor：负责接受（accept）和否决proposal，是最关键角色。
• learner：负责学习最终选定（chosen）的proposal
• 要求所有acceptor组成的进程集合不变；如果一个acceptor进程失效，必须能够重启并重新拥有跟原来进程相同的标识。设acceptor的个数为N。
• proposal是一个二元组<proposal_id, value>。其中proposal_id是一个整数值，由提出该proposal的proposer选定。要求不同的proposal具有不同的proposal_id（不管是不是同一个proposer提出的），因此不同的proposer用于产生proposal_id的整数集必须不相交。
• 一个proposal被chosen的精确定义是：超过半数的acceptor accept了该proposal（注意包括proposal_id）。accept是对于单个acceptor来说的应用于某个proposal上的动作。而chosen则是所有acceptor的accept动作达到的系统宏观上的一种状态。
• 下文中使用符号X(n:v,m)表示acceptor X accept了编号为n值为v的proposal，而m是X回复过的编号最大的prepare request

算法

• Phase 1.
  • (a) A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
  • (b) If an acceptor receives a prepare request with number n greater than that of any prepare request to which it has already responded, then it responds to the request with:
    • a promise not to accept any more proposals numbered less than n
    • the highest-numbered proposal (if any) that it has accepted.

    Otherwise do nothing. <==这句是我加的:)

• Phase 2.
  • (a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.
  • (b) If an acceptor receives an accept request for a proposal numbered n, it accepts the proposal unless it has already responded to a prepare request having a number greater than n.

一些要点

• 对任意acceptor来说，如果它已经accept了一个proposal (n1, v1)，它之后仍然可以accept其他proposal如(n2, v2)。算法保证，如果在accept (n2, v2)前有一个proposal (n, v)被chosen，则v2==v且n2>=n。反之，如果在accept (n2, v2)前没有任何proposal被chosen，则有n2>n1而v2可以不等于v1。
• Phase 2 (a)中让proposer向每个给它发response的acceptor发出proposal，这是必须的。如果是发给任意超过半数的acceptors，将可能出现一个acceptor accept一个比自己之前accept过的proposal的编号还小的proposal的情况，导致算法失效。见算法的其他特性特性3。
• 不可能存在这种情况：
  • 超过半数的acceptor accept了(n1, v1)
  • 其中一个acceptor（可以是那些accept了(n1, v1)的acceptor或其他acceptor）accept了(n2, v2)
  • n2>n1且v2!=v1 这可以从下面的证明过程得到。也可以从直观上来理解：在(n2, v2)被某个acceptor accept之前，必须得到过半数的acceptor保证不会accept小于n2的proposal。如果这些保证发生在(n1, v1)被chosen之后，v2必然会等于v1（证明中对n2=n1+1, n1+2, …进行归纳假设）；如果之前，则(n1, v1)不可能被过半数的acceptor chosen。
• 再强调一下：在Phase 2 (b)中accepts the proposal指的是该proposal作为一个整体（包括其proposal_id）被accepted。如果是具有相同value但不同proposal_id的proposals分别地被一些acceptor accept且这些acceptor个数加起来超过半数，这不能也不意味着到达chosen状态。下文的实例会举出这样的例子。
• 上文Phase 1 (b)中的acceptor也可以这么干：
  • 不respond且不更新自己记录的收到的prepare请求中最大的proposal_id，这相当于该prepare消息被网络丢弃。
  • 不respond但更新自己记录的收到的prepare请求中最大的proposal_id，这相当于respond了但是该response被网络丢弃。
  • 但绝不能：respond却不更新。
• learner如何学习到结果：每个acceptor无论在任何时候accept了一个proposal就要给learner发消息（需要通过重传或其他机制保证该消息最终会被learner收到）。尽管消息可能是乱序到达的，但每个proposal都有一个proposal_id，而且任何acceptor只会按照proposal_id的递增顺序accept不同的proposal，因此learner仍然可以在收到消息后对同一个acceptor accept的proposal进行排序，找出一个被超过半数acceptor accept的proposal即为结果，如果找不到说明还没达成一致。

正确性证明

求证：Paxos将保证

• i 只有被proposed的value才会被chosen
• ii 如果有一个value被chosen，则只会有一个value被chosen
• iii 一个learner绝不会学到一个value，除非该value被chosen

证明：由算法的过程可知i和iii是显然的。现在证明ii。由算法的Phase 2 (a)可知如下结论P2c成立：

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.

现在来证明P2b：

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

采用反证法。假设proposal (n, v)被chosen，而proposal (n1, v1)是被issued的满足n1>n且v1!=v且proposal_id（即n1）最小的proposal。为了满足P2c，必须使P2c (a)或P2c (b)成立。而：

1. (n1, v1)要被issued，首先要得到任意一个由过半数acceptor组成的集合S1中每个acceptor的保证，说之后再也不accept任何proposal_id<n1的proposal；而(n, v)被chosen，说明有一个由过半数的acceptor组成的集合S2中的所有acceptor都accept了它。S1和S2的交集S1∩S2中的每个acceptor都保证既不accept任何proposal_id<n1的proposal，又accept了proposal_id<n1的(n, v)；所以只能是先accept了(n, v)，再保证，故P2c (a)不成立。
2. 由上述分析可知，所有proposal_id>n且被issued的的proposal都是在(n, v)被chosen后被issued的，而所有满足n<proposal_id<n1的proposal都具有value v（归纳法）。设所有回复过proposal_id在[n, n1)中的prepare请求的acceptor的集合为S3（所以这是一个由过半acceptor组成的集合），则S1∩S3非空，要满足P2c (b)，则prepare n1请求的回复中最大的proposal_id由S1∩S3决定，因而v1=v，与假设矛盾。

因此P2b成立。

注：如何理解上述证明第2小节中的“后”：由于chosen是由S2中所有acceptor共同决定的，而时间是相对的，无法定义S2中哪个acceptor是“最后一个”accept了(n,v)的（同理，假如(n, v)没有被chosen，也无法定义到底是哪个acceptor的“不accept”即ignore动作最后决定了(n, v)不被chosen，这是题外话）。因此，这里说“在(n, v)被chosen后被issued”的精确定义是：S1∩S2中每个acceptor都是先accept了(n, v)，再发出保证说“再也不accept任何proposal_id<n1的proposal”，从而使(n1, v1)可以被issued。

而P2b蕴含P2a：

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

P2a又蕴含P2：

P2. If a proposal with value v is chosen, then every higher-numbered proposal that is chosen has value v.

P2保证了每个被chosen的higher-numbered的proposal有value v，而由于消息可能重复和延迟发送，一个acceptor在accept了那个被chosen的proposal之后可能会收到一个延迟的lower-numbered的proposal。我们必须保证该acceptor不会accept它，这将在下一节的特性2证明。因此，P2和特性2保证了ii。证毕。

论文中其他推论：

• P1a. 即算法步骤Phase 2 (b)。
• P1a蕴含了P1. An acceptor must accept the first proposal that it receives.

正确性证明（另一条思路）

我觉得这是更容易理解的思路（因为不用纠结全局时钟的问题），而且是Paxos的精髓所在。

• Paxos算法对所有proposal定义了一个序，用<<表示，其定义为：(n1, v1)<<(n2, v2)当且仅当n1<n2。为了明白这个序的特性，首先明确，proposal (n, v)之所以成为proposal，首先需要收到过半数acceptor在Phase 1 (b)发出的response。而acceptor要在Phase 1 (b)发response的条件是，它之前没有看到过编号大于或等于n的prepare request（注意那句Otherwise do nothing）。设在Phase 1 (b)回复过编号为n1的prepare request的acceptor组成的集合为Sn1，在Phase 1 (b)回复过编号为n2的prepare request的acceptor组成的集合为Sn2，则Sn1和Sn2均包含过半acceptor，因此它们的交集非空，而Sn1∩Sn2中的acceptor肯定是先回复了编号为n1的prepare request，再回复编号为n2的prepare request。如果我们用N条平行直线表示包括N个acceptor组成的系统，acceptor每次在Phase 1 (b)中回复一个prepare request我们就在对应的直线上画一个圈并标明该prepare request的编号，这样一条直线上不同的圈就反应了一个acceptor发出的不同回复的相对时间序。而<<序表明，对于任意不同的n1和n2，我们总可以找到一个割（cut），使得与n1关联的圈在该割的一边而与n2关联的圈在该割的另一边。由于<<对任何n1和n2都成立，所以<<是一个全序而不仅是一个偏序。
• 现在证明如果其中某个proposal被accept了，则所有编号更大的proposal都有相同的value（即P2b）。假设(n1, v1)被chosen了，而(n2, v2)是最“小”的使得(n1, v1)<<(n2, n2)成立的proposal（也即，不存在和n2不同的n3满足(n1, v1)<<(n3, v3)<<(n2, v2)）。设accept了(n1, v1)的acceptor组成的集合为Sn1’，则Sn1’是Sn1的一个子集。
  • 考虑Sn1’∩Sn2里面的acceptor，它们都按顺序做了这样的操作：
    • 回复编号为n1的prepare request
    • Did something X
    • accept了(n1, v1)
    • Did something Y
    • 回复编号为n2的prepare request

    X不能是回复任何编号不为n1的prepare request，更不能是accept任何其他的proposal。所以X是空操作。Y可以是回复任何编号大于n1但小于n2的prepare request，但不能是accept任何编号不为n1的proposal（因为一个proposal要成为proposal首先要被过半数的acceptor回复其prepare request，而(n2, v2)是(n1, v1)之后第一个proposal）。回复prepare request并不会改变之后回复prepare request时附上的曾经accept过的最大编号的proposal的信息，因此对所有Y中包括随后编号为n2的prepare request的response都具有值v1。

  • 对于Sn2-Sn1’中（即在Sn2中但不在Sn1’中）的acceptor来说，在回复编号为n2的prepare request之前它们不可能accept一个编号比n1更大的proposal（再一次，因为一个proposal要成为proposal首先要收到过半数acceptor回复其prepare request，而(n2, v2)是(n1, v1)之后第一个proposal），所以它们之前accept过的proposal的编号只能比n1更小。
  • 综合上述两种情况，Sn2中的acceptor回复编号为n2的prepare request附上的编号最大的proposal就是(n1, v1)，因此v2=v1。采用同样的方法可以归纳证明所有编号大于n1的proposal都具有相同的值v1。

算法的其他特性

• 特性1·设acceptor X在任意时刻的状态为X(n:v,m)，则n<=m。Phase 2 (a)保证了这点。
• 特性2·不可能出现一个acceptor accept一个比自己之前accept过的proposal的编号还小的proposal的情况，这是因为：根据Phase 2 (b)，一个acceptor X(n:v,m)只能accept编号大于等于m的request，而任何时刻都有n<=m（特性1）。
• 特性3·如果Phase 2 (a)中的proposer不是向每个给它发response的acceptor发accept request，而是向任意过半数的acceptor发，尽管P2仍然成立，但特性1和特性2不再成立：一个acceptor可能accept一个比自己之前accept过的proposal的编号还小的proposal，算法将失败。考虑三个acceptor ABC的例子，初始为重设状态：
  • P1给AB发prepare 1

  • AB均回复保证

    此时状态为：A(-:-,1) B(-:-,1) C(-:-,-)

  • P2给AB发prepare 100

  • AB均回复保证

    此时状态为：A(-:-,100) B(-:-,100) C(-:-,-)

  • P2收到保证并给BC发(100:b)

  • BC收到并accept

    此时状态为：A(-:-,100) B(100:b,100) C(100:b,-)

    注意(100:b)已经被chosen

  • P1收到保证并给BC发(1:a)

  • B不accept，而C收到并accept

    此时状态为：A(-:-,100) B(100:b,100) C(1:a,-)

    再一次变成没有任何proposal被chosen的状态，算法失败

• 特性4·如果维持特性3对Phase 2 (a)的修改，同时修改Phase 2 (b)使：禁止一个acceptor accept一个比自己之前accept过的proposal的编号还小的proposal，算法将成功，因为这不影响P2成立，而重新保证了特性2成立（尽管特性1不再满足）。
• 特性5·一旦一个proposal被chosen，即使挂掉少半数的acceptor，算法的正确性仍然能够得到保证，即即使不断有proposer提出不同的proposal也不会改变那个被chosen的proposal！因此acceptor的挂掉不会阻止learner学习到被chosen的value：learner可以充当proposer执行算法直到新的proposal（包含相同的被chosen的value）被chosen即可（注意：一定要等到新的proposal被chosen，而不能从已有的N-1个acceptor的当前状态推断出是否有旧的proposal被chosen，原因可以考虑实例2步骤13完成后B挂掉的情况）

实例

实例1：未达成一致状态下可以accept任何具有不同的value的proposal

假设共有5个acceptor分别标记为ABCDE，任意数量个proposer分别为P1，P2，P3…，设一开始系统为重设状态，算法开始：

1. P1给ABC发编号为1的prepare
2. ABC均返回response保证不接受编号小于1的proposal，但由于ABC均为初始状态故没有任何highest-numbered proposal被返回
3. P1选定值a并把(1:a)发给ABC

4. A收到P1的消息并accept了(1:a)

   此时状态为：A(1:a,1) B(-:-,1) C(-:-,1) D(-:-,-) E(-:-,-)

5. 在BC收到P1的消息前，P2向BCD发出了编号为2的prepare并被BCD收到
6. BCD均返回response保证不接受编号小于2的proposal，但由于BCD均为初始状态故没有返回任何highest-numbered proposal
7. P1发给BC的消息在到达BC后被ignored（另一种可能的情况是：P1发给BC的消息被网络丢弃了。下面用这种情况简化描述）
8. P2选定值b并把(2:b)发给BCD

9. B收到P2的消息并accept了(2:b)，P2发给CD的消息被网络丢弃

   此时状态为：A(1:a,1) B(2:b,2) C(-:-,2) D(-:-,2) E(-:-,-)

10. P3向CDE发出了编号为3的prepare并被CDE收到
11. CDE均返回response保证不接受编号小于3的proposal，CDE为初始状态故没有返回highest-numbered proposal
12. P3选定值c并把(3:c)发给CDE

13. C收到P3的消息并accept了(3:c)，P3发给DE的消息被网络丢弃

    此时状态为：A(1:a,1) B(2:b,2) C(3:c,3) D(-:-,3) E(-:-,3)

14. P4向DEA发出了编号为4的prepare并被DEA收到
15. DEA均返回response保证不接受编号小于4的proposal，DE为初始状态故没有返回highest-numbered proposal，而A返回(1:a)
16. P4在收到的highest-numbered proposal中选编号最大者的值a并把(4:a)发给DEA

17. D收到P4的消息并accept了(4:a)，P4发给EA的消息被网络丢弃

    此时状态为：A(1:a,4) B(2:b,2) C(3:c,3) D(4:a,4) E(-:-,4)

18. P5向EAB发出了编号为5的prepare并被EAB收到
19. EAB均返回response保证不接受编号小于5的proposal，E为初始状态故没有返回highest-numbered proposal，而A返回(1:a)，B返回(2:b)
20. P5在收到的highest-numbered proposal中选编号最大者的值b并把(5:b)发给EAB

21. E收到P5的消息并accept了(5:b)，P5发给AB的消息被网络丢弃

    此时状态为：A(1:a,5) B(2:b,5) C(3:c,3) D(4:a,4) E(5:b,5)

至此，每个acceptor都accept了一个proposal，但没有任何一个proposal被过半数的acceptor接受。因此此时的状态不是稳定状态，ABCDE都可以继续accept其他proposal，即使它们与自己之前accept过的proposal的value不一样。Paxos保证一旦有一个proposal被chosen（即被过半数acceptor接受）后系统就只会issued包含该proposal的value的proposal，因此chosen后的状态为稳定状态。继续重复类似上述的过程将得到如下状态序列：

• A(6:c,6) B(2:b,6) C(3:c,6) D(4:a,4) E(5:b,5)
• A(6:c,6) B(7:a,7) C(3:c,7) D(4:a,7) E(5:b,5)
• A(6:c,6) B(7:a,7) C(8:b,8) D(4:a,8) E(5:b,8)
• A(6:c,9) B(7:a,7) C(8:b,8) D(9:c,9) E(5:b,9)
• …

即系统无法取得progress达到一致状态，即使网络不丢包且消息也是顺序到达。但实际中发生这种情况的概率应该很小。

实例2：过半数acceptor都accept了同一value并不意味着达成一致

如果实例1中从第10步开始变为：

10. P3向ACD发出了编号为3的prepare并被ACD收到
11. ACD均返回response保证不接受编号小于3的proposal，CD为初始状态故没有返回highest-numbered proposal，而A返回(1:a)
12. P3在收到的highest-numbered proposal中选编号最大者的值a并把(3:a)发给ACD

13. CD收到P3的消息并accept了(3:a)，P3发给A的消息被网络丢弃

    此时状态为：A(1:a,3) B(2:b,2) C(3:a,3) D(3:a,3) E(-:-,-)

    此时ACD构成过半数acceptor且都accept value a，但是这并不表示a被chosen了！Paxos要求的是一个proposal作为一个整体被过半数acceptor accept，因此现在的状态不是一个chosen状态，系统并未达到一致且可能issue value不为a的proposal。考虑：

14. P4向EAB发出了编号为4的prepare并被EAB收到
15. EAB均返回response保证不接受编号小于4的proposal，E为初始状态故没有返回highest-numbered proposal，而A返回(1:a)，B返回(2:b)
16. P4在收到的highest-numbered proposal中选编号最大者的值b并把(4:b)发给EAB

17. EAB收到P4的消息并accept了(4:b)，到达一致状态

    此时状态为：A(4:b,4) B(4:b,4) C(3:a,3) D(3:a,3) E(4:b,4)

    此后系统再也不可能产生value不为b的proposal。

问题

• acceptor的个数是否可以为偶数？答：可以。证明过程对于N为任意正整数都成立。
• 2PC是否是Paxos的变种(@Mike Burrows)？答：
• 根据FLP结论如何构造出“单个进程失效使得Paxos无法达成一致”的例子？答：
• 在一次算法的运行中被至少一个acceptor accept过的不同的v值只有向上取整n/2个？答：

其他note

• 一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。这即论文中所述的“分布式状态机”。
• 一个分布式算法，有两个最重要的属性：safety 和livness，简单来说safety就是指那些需要保证永远都不会发生的事情，livness是指那些最终一定会发生的事情

Multi-Paxos

[from dsdoc.net]

如何理解“因为Leader的失败和新Leader的选举都是很少见的情况，因此执行一个状态机命令—即在命令值上达成一致性的花费就是执行该一致性算法的Phase 2的花费”：大部分时间里Leader正常；Leader正常时，如果majority的proposer在Phase 1承诺了编号 n，由于所有执行实例用同一个的提案编号计数器，即所有实例的Phase 1都完成了，之后只提交Phase2消息即可。即：用一个Phase 1的message搞定了一堆Paxos实例的Phase 1的执行。

参考

• 英文wiki
• 各个版本的翻译和注解
  • 银河里的星星 - done
  • loop in the codes - done
  • sparkliang的专栏 - done
  • 中文wiki - done
  • 后端技术by Tim Yang - done
  • 小武哥的博客 - done
  • 阿里核心团队博客1 - done
  • 阿里核心团队博客2
  • 阿里核心团队博客3
  • paxos图解
  • Paxos算法详解
  • 壮族小伙
  • 理解这两点，也就理解了paxos协议的精髓
  • Distributed Systems-白话Paxos