Paxos算法

问题和假设

分布式系统中的节点通信存在两种模型：共享内存（Shared memory）和消息传递（Messages passing）。基于消息传递通信模型的分布式系统，不可避免的会发生以下错误：进程可能会慢、被杀死或者重启，消息可能会延迟、丢失、重复，在基础Paxos 场景中，先不考虑可能出现消息篡改即拜占庭错误的情况。Paxos 算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。因此从20世纪80年代起对于一致性算法的研究就没有停止过。
为描述Paxos算法，Lamport虚拟了一个叫做Paxos的希腊城邦，这个岛按照议会民主制的政治模式制订法律，但是没有人愿意将自己的全部时间和精力放在这种事情上。所以无论是议员，议长或者传递纸条的服务员都不能承诺别人需要时一定会出现，也无法承诺批准决议或者传递消息的时间。但是这里假设没有拜占庭将军问题（Byzantine failure，即虽然有可能一个消息被传递了两次，但是绝对不会出现错误的消息）；只要等待足够的时间，消息就会被传到。另外，Paxos岛上的议员是不会反对其他议员提出的决议的。
对应于分布式系统，议员对应于各个节点，制定的法律对应于系统的状态。各个节点需要进入一个一致的状态，例如在独立Cache的对称多处理器系统中，各个处理器读内存的某个字节时，必须读到同样的一个值，否则系统就违背了一致性的要求。一致性要求对应于法律条文只能有一个版本。议员和服务员的不确定性对应于节点和消息传递通道的不可靠性。

算法的内容

要满足P2c的约束，proposer提出一个提案前，首先要和足以形成多数派的acceptors进行通信，获得他们进行的最近一次接受（accept）的提案（prepare过程），之后根据回收的信息决定这次提案的value，形成提案开始投票。当获得多数acceptors接受（accept）后，提案获得批准（chosen），由acceptor将这个消息告知learner。这个简略的过程经过进一步细化后就形成了Paxos算法。
在一个paxos实例中，每个提案需要有不同的编号，且编号间要存在全序关系。可以用多种方法实现这一点，例如将序数和proposer的名字拼接起来。如何做到这一点不在Paxos算法讨论的范围之内。
如果一个没有chosen过任何proposer提案的acceptor在prepare过程中回答了一个proposer针对提案n的问题，但是在开始对n进行投票前，又接受（accept）了编号小于n的另一个提案（例如n-1），如果n-1和n具有不同的value，这个投票就会违背P2c。因此在prepare过程中，acceptor进行的回答同时也应包含承诺：不会再接受（accept）编号小于n的提案。这是对P1的加强：
P1a：当且仅当acceptor没有回应过编号大于n的prepare请求时，acceptor接受（accept）编号为n的提案。
现在已经可以提出完整的算法了。

实例

用实际的例子来更清晰地描述上述过程：
有A1, A2, A3, A4, A5 5位议员，就税率问题进行决议。议员A1决定将税率定为10%,因此它向所有人发出一个草案。这个草案的内容是：
现有的税率是什么?如果没有决定，则建议将其定为10%.时间：本届议会第3年3月15日;提案者：A1
在最简单的情况下，没有人与其竞争;信息能及时顺利地传达到其它议员处。
于是, A2-A5回应：
我已收到你的提案，等待最终批准
而A1在收到2份回复后就发布最终决议：
税率已定为10%,新的提案不得再讨论本问题。
这实际上退化为二阶段提交协议。
现在我们假设在A1提出提案的同时, A5决定将税率定为20%:
现有的税率是什么?如果没有决定，则建议将其定为20%.时间：本届议会第3年3月15日;提案者：A5
草案要通过侍从送到其它议员的案头. A1的草案将由4位侍从送到A2-A5那里。现在，负责A2和A3的侍从将草案顺利送达，负责A4和A5的侍从则不上班. A5的草案则顺利的送至A4和A3手中。
现在, A1, A2, A3收到了A1的提案; A4, A3, A5收到了A5的提案。按照协议, A1, A2, A4, A5将接受他们收到的提案，侍从将拿着
我已收到你的提案，等待最终批准
的回复回到提案者那里。
而A3的行为将决定批准哪一个。

情况一

假设A1的提案先送到A3处，而A5的侍从决定放假一段时间。于是A3接受并派出了侍从. A1等到了两位侍从，加上它自己已经构成一个多数派，于是税率10%将成为决议. A1派出侍从将决议送到所有议员处：
税率已定为10%,新的提案不得再讨论本问题。
A3在很久以后收到了来自A5的提案。由于税率问题已经讨论完毕，他决定不再理会。但是他要抱怨一句：
税率已在之前的投票中定为10%,你不要再来烦我!
这个回复对A5可能有帮助，因为A5可能因为某种原因很久无法与与外界联系了。当然更可能对A5没有任何作用，因为A5可能已经从A1处获得了刚才的决议。

情况二

依然假设A1的提案先送到A3处，但是这次A5的侍从不是放假了，只是中途耽搁了一会。这次, A3依然会将"接受"回复给A1.但是在决议成型之前它又收到了A5的提案。这时协议有两种处理方式：
1.如果A5的提案更早，按照传统应该由较早的提案者主持投票。现在看来两份提案的时间一样（本届议会第3年3月15日）。但是A1是个惹不起的大人物。于是A3回复：
我已收到您的提案，等待最终批准，但是您之前有人提出将税率定为10%,请明察。
于是, A1和A5都收到了足够的回复。这时关于税率问题就有两个提案在同时进行。但是A5知道之前有人提出税率为10%.于是A1和A5都会向全体议员广播：
 税率已定为10%,新的提案不得再讨论本问题。
一致性得到了保证。
2. A5是个无足轻重的小人物。这时A3不再理会他, A1不久后就会广播税率定为10%.

情况三

在这个情况中，我们将看见，根据提案的时间及提案者的权势决定是否应答是有意义的。在这里，时间和提案者的权势就构成了给提案编号的依据。这样的编号符合"任何两个提案之间构成偏序"的要求。
A1和A5同样提出上述提案，这时A1可以正常联系A2和A3; A5也可以正常联系这两个人。这次A2先收到A1的提案; A3则先收到A5的提案. A5更有权势。
在这种情况下，已经回答A1的A2发现有比A1更有权势的A5提出了税率20%的新提案，于是回复A5说：
我已收到您的提案，等待最终批准。
而回复了A5的A3发现新的提案者A1是个小人物，不予理会。
A1没有达到多数，A5达到了，于是A5将主持投票，决议的内容是A5提出的税率20%.
如果A3决定平等地对待每一位议员，对A1做出"你之前有人提出将税率定为20%"的回复，则将造成混乱。这种情况下A1和A5都将试图主持投票，但是这次两份提案的内容不同。
这种情况下, A3若对A1进行回复，只能说：
有更大的人物关注此事，请等待他做出决定。
另外，在这种情况下, A4与外界失去了联系。等到他恢复联系，并需要得知税率情况时，他（在最简单的协议中）将提出一个提案：
现有的税率是什么?如果没有决定，则建议将其定为15%.时间：本届议会第3年4月1日;提案者：A4
这时，（在最简单的协议中）其他议员将会回复：
税率已在之前的投票中定为20%,你不要再来烦我!

决议的发布

一个显而易见的方法是当acceptors批准一个value时，将这个消息发送给所有learners。但是这个方法会导致消息量过大。
由于假设没有Byzantine failures，learners可以通过别的learners获取已经通过的决议。因此acceptors只需将批准的消息发送给指定的某一个learner，其他learners向它询问已经通过的决议。这个方法降低了消息量，但是指定learner失效将引起系统失效。
因此acceptors需要将accept消息发送给learners的一个子集，然后由这些learners去通知所有learners。
但是由于消息传递的不确定性，可能会没有任何learner获得了决议批准的消息。当learners需要了解决议通过情况时，可以让一个proposer重新进行一次提案。注意一个learner可能兼任proposer。

Progress的保证

根据上述过程当一个proposer发现存在编号更大的提案时将终止提案。这意味着提出一个编号更大的提案会终止之前的提案过程。如果两个proposer在这种情况下都转而提出一个编号更大的提案，就可能陷入活锁，违背了Progress的要求。一般活锁可以通过随机睡眠-重试 的方法解决。这种情况下的解决方案是选举出一个leader，仅允许leader提出提案。但是由于消息传递的不确定性，可能有多个proposer自认为自己已经成为leader。Lamport在The Part-Time Parliament一文中描述并解决了这个问题。

Multi-Paxos

Paxos的典型部署需要一组连续的被接受的值（value），作为应用到一个分布式状态机的一组命令。如果每个命令都通过一个Basic Paxos算法实例来达到一致，会产生大量开销。
如果Leader是相对稳定不变的，第1阶段就变得不必要。 这样，系统可以在接下来的Paxos算法实例中，跳过的第1阶段，直接使用同样的Leader。
为了实现这一目的，在同一个Leader执行每轮Paxos算法时，提案编号I 每次递增一个值，并与每个值一起发送。Multi-Paxos在没有故障发生时，将消息延迟(从propose阶段到learn阶段)从4次延迟降低为2次延迟。

Multi-Paxos 没有失败的情况

在下面的图中，只显示了基本Paxos协议的一个实例(或“执行”)和一个初始Leader(Proposer)。注意，Multi-Paxos使用几个Basic Paxos的实例。
Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |<---------X--X--X------>|->|  Accepted(N,I,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |
式中V = (Va, Vb, Vc) 中最新的一个。

跳过阶段1时的Multi-Paxos

在这种情况下，Basic Paxos的后续实例(由I+1表示)使用相同的Leader，因此，包含在Prepare和Promise的阶段1(Basic Paxos协议的这些后续实例)将被跳过。注意，这里要求Leader应该是稳定的，即它不应该崩溃或改变。
Client   Proposer       Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Accepted(N,I+1,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

Fast-Paxos

Fast-Paxos将Basic-Paxos进行了推广，以减少端到端消息延迟。在Basic-Paxos中，从客户端发起请求开始，到Learn阶段结束的消息延迟是3个消息延迟。而Fast-Paxos允许2个消息延迟，但要求：
(1)系统由3f+ 1个Acceptor组成，以容忍最多f个错误(而不是Basic-Paxos的2f+1)；
(2)客户端需要直接将请求发送到多个目标。
直观上，如果Leader没有提议任何value，那么客户可以直接发送Accept消息到向接收方发。Acceptor会像Basic-Paxos一样运行，向Leader和每个Learner发送Accepted的消息，从而实现从客户端到Learner的两消息延迟。
如果Leader检测到冲突，它通过发起新一轮投票，并发送Accept消息来解决冲突，通常是一个Accepted消息。这种有协调者参与的冲突恢复机制需要4个从客户端到Learner的消息延迟。
如果Leader提前指定了一种冲突恢复机制，就可以实现另一种优化，它允许Acceptors自己执行冲突恢复。因此，无协调的冲突恢复可能实现三个消息延迟(如果所有的Learner都是接收者，那么只有两个消息延迟)。

消息流: Fast-Paxos，无冲突

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)
   |         |          |  |  |  |       |  |

消息流:Fast-Paxos，冲突的建议

有协调这参与的冲突恢复。注意:协议没有指定如何处理被丢弃的客户端请求。
Client   Leader      Acceptor     Learner
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |
 |  |      |        |  |  |  |      |  |  !! 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------->|->|->|->|      |  |  Accept!(N+1,I,W)
 |  |      |<-------X--X--X--X----->|->|  Accepted(N+1,I,W)
 |<---------------------------------X--X  Response(W)
 |  |      |        |  |  |  |      |  |
无协调者参与的相冲突恢复：
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)
 |  |      |        |  |  |  |      |  |

消息流:无协调者的冲突恢复、角色崩溃的Fast-Paxos

(合并的Acceptor/Learner)
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  Accepted(N+1,I,W)
 |<-----------X--X--X--X  Response(W)
 |  |         |  |  |  |

应用 

微软公司为简化的Paxos算法申请了专利。但专利中公开的技术和本文所描述的不尽相同。
谷歌公司（Google公司）在其分布式锁服务中应用了Multi-Paxos算法。Chubby lock应用于大表（Bigtable），后者在谷歌公司所提供的各项服务中得到了广泛的应用。
谷歌公司（Google公司）在其分布式数据库spanner中使用Multi-Paxos作为分布式一致性保证的基础组件
Apache ZooKeeper 使用一个类Multi-Paxos的一致性算法作为底层存储协同的机制。