Paxos Consensus Algorithm

1. Paxos 算法
- 1.1. 问题描述
- 1.2. Paxos 算法描述
  - 1.2.1. 没有错误发生时 Paxos 的消息交换过程
  - 1.2.2. 有错误发生时 Paxos 达成一致的过程举例
2. Multi-Paxos

1. Paxos 算法

Paxos 算法是 Lamport 于 1990 年提出的基于消息交换的具有高度容错特性的分布式环境中的一致性算法。注：Paxos 这个名字来源于 Lamport 在论文中虚构的一个岛屿名称。Paxos 算法是一种“Crash Fault Tolerance（CFT）”算法，不是“Byzantine Fault Tolerance（BFT）算法，也就是说 Paxos 考虑的是系统中有故障，但没有恶意节点的情况。

1.1. 问题描述

在分布式 key-value 存储系统中， 多个 client 可能同时对不同节点上的 server 进程提交修改请求，如何让所有 server 上 key 所关联的 value 值达成一致？

1.2. Paxos 算法描述

Paxos 算法把参与者分为下面几个角色：Proposer（提议者）、Acceptor（决策者）、Learner（最终决策学习者）。除此外，还有 Client（产生议题者）。在具体实现中，往往每个 server 同时都是 Proposer/Acceptor/Learner。

Proposer 可以看作是 Client 的使者，Proposer 带着 Client 的议题向 Acceptor 提议，让 Acceptor 来决策。经过两个过程（后文将介绍）后，如果有多数派个 Acceptor 最终接受了某议题，那么这个议题就被批准了。Learner 学习被批准的议题。

Paxos 算法描述如下：
第一个阶段：Prepare 阶段。
(a) Proposer 为议题选择一个编号 $n$ （每个提议都有一个唯一的编号），去找 Acceptor，想要它们初步接受（大多数 Acceptor 初步接受即可）。
(b) Acceptor 收到议题后，检测编号 $n$ ，如果 $n$ 比当前 Acceptor 曾经“初步接受”过的议题的编号都要大，则“初步接受”这个编号为 $n$ 的议题；反之，如果当前 Acceptor 曾经“初步接受”过比 $n$ 大的议题，则拒绝这个编号为 $n$ 的议题。也就是说，Acceptor 能够保证，如果自己“初步接受”了编号为 $n$ 的议题，则不会再“初步接受”编号比 $n$ 小的议题。

第二个阶段：Accept 阶段。
(a) 如果在第一个阶段，Proposer 的议题得到了大多数 Acceptor 的初步接受。那么 Proposer 把这个议题的编号 $n$ 和内容（比如“设置 keyA 的值为 value1”）发送给 Acceptor，想要它们“最终批准”（大多数 Acceptor 最终批准即可）。
(b) Acceptor 收到 Proposer 发送的希望得到“最终批准”的编号为 $n$ 的议题后，一般情况都会“最终批准”它，除非 Acceptor 曾经在第一个阶段“初步接受”过编号比 $n$ 大的议题（比如它初步接受过编号为 $n + 1$ 的议题“设置 keyA 的值为 value2”，这种情况下 Acceptor 会拒绝“最终批准”这个编号为 $n$ 的议题“设置 keyA 的值为 value1”）。

在第二个阶段中，如果大多数 Acceptor 最终批准了议题（如“设置 keyA 的值为 value1”），则这个议题就被正式批准，可以被所有 Learner 学习。

用一句话简单描述就是：“Proposer 提出议题，先争取大多数 Acceptor 的支持，超过一半支持时，则发送议题结果给所有 Acceptor 进行确认。” 其过程类似于 Two-phase commit protocol 。图 1 （摘自 Implementing Replicated Logs with Paxos）对 Paxos 总结得比较好。

Figure 1: Basic Paxos

参考：
Paxos Made Simple: http://research.microsoft.com/users/lamport/pubs/paxos-simple.pdf
Paxos Made Live - An Engineering Perspective: https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf
一步一步理解Paxos算法
MIT 6.824 Lab 3: Paxos-based Key/Value Service: http://nil.csail.mit.edu/6.824/2015/labs/lab-3.html
Distributed Systems - Concepts and Design, 5th Edition, 15.5.3 The Byzantine generals problem in a synchronous system
Distributed Systems - Concepts and Design, 5th Edition, 21.5.2 Chubby
Paxos 算法细节详解(一)--通过现实世界描述算法：http://www.cnblogs.com/endsock/p/3480093.html
Distributed Systems: What is a simple explanation of the Paxos algorithm?: https://www.quora.com/Distributed-Systems-What-is-a-simple-explanation-of-the-Paxos-algorithm

1.2.1. 没有错误发生时 Paxos 的消息交换过程

没有错误发生时 Paxos 的消息交换过程如图 2 （摘自 Distributed Systems - Concepts and Design, 5th Edition, 21.5.2 Chubby）所示。

Figure 2: Message exchanges in Paxos (in absence of failures)

图 2 中 seq_number 就是提议的编号，Promise 表示“我承诺不会初步接受编号比 seq_number 小的议题”。

没有错误发生时 Paxos 的消息交换过程也可以表示为下面形式：

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

Vn = highest of (Va,Vb,Vc)

1.2.2. 有错误发生时 Paxos 达成一致的过程举例

下面内容摘自：Error cases in Basic Paxos (Wikipedia)
Message flow: Basic Paxos, failure of Acceptor

Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  |
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(1)
   |         |          |  |  !       |  |  !! FAIL !!
   |         |<---------X--X          |  |  Promise(1,{null,null})
   |         X--------->|->|          |  |  Accept!(1,V)
   |         |<---------X--X--------->|->|  Accepted(1,V)
   |<---------------------------------X--X  Response
   |         |          |  |          |  |

Message flow: Basic Paxos, failure of Proposer

Client  Proposer        Acceptor     Learner
   |      |             |  |  |       |  |
   X----->|             |  |  |       |  |  Request
   |      X------------>|->|->|       |  |  Prepare(1)
   |      |<------------X--X--X       |  |  Promise(1,{null, null, null})
   |      |             |  |  |       |  |
   |      |             |  |  |       |  |  !! Leader fails during broadcast !!
   |      X------------>|  |  |       |  |  Accept!(1,Va)
   |      !             |  |  |       |  |
   |         |          |  |  |       |  |  !! NEW LEADER !!
   |         X--------->|->|->|       |  |  Prepare(2)
   |         |<---------X--X--X       |  |  Promise(2,{null, null, null})
   |         X--------->|->|->|       |  |  Accept!(2,V)
   |         |<---------X--X--X------>|->|  Accepted(2,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

2. Multi-Paxos

使用 Paxos 可以对一个值达成一致（比如 keyA 的值），如果系统中有很多值（比如还有 keyB 的值，keyC 的值等等）需要达成一致，显然运行多个 Paxos 过程即可。不过，我们还可以使用 Multi-Paxos 对多个值达成一致。这里不介绍 Multi-Paxos。