译者注：网上太多文章解释Paxos算法了，但大多并不完整。本文是早期笔者学习Paxos过程中看到的一篇教程，写的很清晰，遂翻译好给大家阅读。原文：http://lamport.azurewebsites.net/pubs/paxos-simple.pdf
1 介绍
Paxos算法是被设计用于构造一个容错性分布式系统的，但很多人觉得它很难懂，也许是因为它的原版是希腊文[5]。实际上，它是所有分布式算法中最简单和浅显的一类算法了。它的核心是共识算法——一种教会决议算法[5]。下一节会根据大家习惯的问题解决思路来向大家彻底揭开Paxos的面纱。最后一节会将向大家展示整个完整的算法——它甚至可以直接被拿来使用，用以实现分布式系统中的状态机方案——这个著名的叫法在文献[4]中被提出，这篇文献应该是分布式系统理论中被引用最多的文章了。
2 共识算法
2.1 共识问题
假设有一群可以各自提交自己提案（其实就是一个值）的程序组成了一个分布式系统，那么所谓的“共识算法”就是要保证只有一个程序的提案被整个系统所接受。如果没有任何提案被提出，那么没有任何值将会被选择。如果一个提案被选择了，那么整个系统的程序节点都应该可以学习这个被接受的提案。共识所需要的安全要素有以下这些：
- 只有一个提案可能被选中。
- 只有一个提案被实际选中。（译者注：这是一句有意义的废话）
- 一个节点永远不会学习一个被选中的旧提案，意味着只会学习一个被选中的最新提案。 我们并不想精确的描述所有要素。说白了，共识的目标就是保证某个提案最终被系统选择，并且所有节点都能最终学习到这个提案。 我们将PAXOS算法中的3个角色表达为3种不同作用的执行人：提案者（proposer）、接收者（acceptor）和学习者（learner）。在算法实现中，一个独立的程序实际上可以同时拥有多个执行人角色，但本文中把他们分开以更好的解释算法，记住这和算法实现里单节点多角色并不冲突。 假设这些执行人互相之间可以通过发送消息来通信。我们用传统异步、非拜占庭模型来做演示这个算法，在这个模型里：
- 每个执行人的处理速度都不一样，有些可能会宕机或者重启。由于每个执行人都可能在提案被选出来之后宕机（但最终会重启），所以任何解决方案都要求节点宕机时可以保留已知的数据。
- 消息在执行人之间传递的速度也是任意的，有可能会重发，也有可能丢失，但绝对不会损坏。
译者注：CRC算法可以保证数据正确性，识别消息损坏的算法已经非常成熟。
2.2 选择一个提案
选择提案最简单的方式是只有一个接收者。任何一个提案者把提案发送给这个接收者，它将选择第一个收到的提案作为最终值。可惜这种简单的方案并不实用，因为一旦这仅有的接收者宕机或出现异常，系统就无法继续工作了。
注：这就是单点问题
所以我们得换一个思路——用多个接收者来替换单个接收者——一个提案者把自己的提案发送给一系列接收者。每一个接收者都可以选择接受这个提案，而最终只有当足够多的接收者都接受这个提案时，它才算真正被整个系统接受。那么问题来了，”足够多“是多少？为了保证只有一个提案值被接受，我们将这个数字设定为(N/2)+1，其中N是所有接收者的数量。由于每个接收者能且只能接受一个提案值，所以某个提案一旦被”半数+1“的接收者所接受，那就不会出现另一个被多数节点接受的提案[3]。
注：一个集体中只可能存在一种不重复的多数——这是一个常识。
考虑到接收者可能会宕机、信息可能会丢失，哪怕只有一个提案者发起了一个提案，我们依然希望有一个提案能被接受。这就要求：
条件1: 每个接收者必须接受它收到的第一个提案
这个条件会带来一个新的问题。多个提案者有可能会在同一个时刻发出提案，从而可能出现没有一个提案会被半数以上的接收者所接受。即便只有2个提案者，也可能出现一人一半——多出来的那个节点刚好宕机了。
这里有个基本假设——初始接收者集合数量为奇数
条件1和前文谈到的“至少有一个提案被半数以上的接受者接受”这两个条件想要被满足，接收者就必须被设计成可以接受多个提案，而不是只能接受一个。我们通过为每个提案添加一个递增的数字编号来跟踪不同的提案，这样一个提案就由两部分组成了：数字编号和提案值，记作(n,v)。为了避免冲突，不同的提案的编号也必须不相同。如何保证这些编号不相同取决于实现方法，目前我们不探讨如何实现，假设它已经实现了。
统一递增ID生成方法有很多。
一旦某个提案被大多数节点接受了，那么它也就是整个系统所选择的提案。我们允许多个提案被同时接受，只要他们的提案值是一样的。通过引入提案编号，我们足以保证：
条件2：如果一个提案(n,v)被选中了，那么其他被选中的带有更高编号的提案的值也是v。
由于提案编号是递增的，条件2保证了有且只会一个提案值被系统接受。要想被系统接受，任何一个提案必须至少被一个接收者接受，所以只要以下条件被满足，条件2就肯定满足：
条件2-1：如果一个提案(n,v)被接受了，那么任意一个接受者接受的带有更高编号的提案的值就是v。
我们仍然要求满足条件1来确保某个提案会被选中。因为执行人之间的通信是异步的，即便有些接受者由于宕机或者网络问题收不到任何提案，我们也得保证至少有一个提案被整个系统接受。假设这个宕机的接受者节点为c，它重启后立即有一个新的提案者发布了一个带有更高编号和不同提案值的提案，那么条件1就要求接收者c接受这个新提案——因为这是它活过来之后收到的第一个提案，而这违反了条件2-1。要想同时满足条件1和条件2-1，我们必须满足以下条件：
条件2-2：如果一个提案(n,v)被接受了，那么任何提案者发出的带有更高编号的提案的值必须是v。
由于一个提案先得被提交才可能会被接受，条件2-2也就成为了条件2-1的充分条件，当然也是条件2的充分条件。
为了满足条件2-2，我们可以想想如何找到它的充分条件。假设提案(m,v)被选中，并且任何的其他提案（编号>m)的值都是v。为了更好的证明，我们将问题描述为：如果编号为m+1,m+2,…n-1的提案对应的值是v的化那么提案n的值也是v。(m,v)被系统选中意味着存在一个接收者集合C，它的集合数量占整个接收者集合的半数以上。
假设1：集合C中的每个接受者接受到的提案编号范围为[m, n-1]，并且这些提案的值均为v。
由于任何一种多数接受者集合都至少含有一个集合C中的元素，只要下面的条件成立，提案n的值也一定是v。
条件2-3：对于提案(n,v)来说，只要它被发布了，则会存在一个多数接受者组成的集合S，要么S中没有任何节点接受了编号小于n的提案，要么S中接受者收到的编号<n的提案中最大编号提案的值一定是v。
我们只要保证条件2-3是永远成立的，条件2-2也就成立了。
为了让2-3成立，任何一个想要发布编号为n的提案的提案者必须已经知道了所有编号小于n中最大编号的提案——也就是知道了编号为n-1的提案（如果有的话）。如果有小于n的提案，那么这些编号小于n的提案中编号最大的提案已经或者即将会被多数接受者所接受。学习哪些提案已经被接受了是很简单的，预测哪些提案会被接受则是非常困难的。与其预测未来，提案者不如去向接受者要一个承诺——他们不会再接受编号小于n的其他提案。
这段的意思其实很简单：当提案者A准备把提案(n,v)发出去后接受者准备返回请求时，可能也有其他的提案(ni<n,vi)正在发送的路途上，这些在途的编号小于n的提案可能存在比提案者A上已知的<n的提案编号更大的提案，但只要接受者返回时保证自己后面不再接受比n更小的提案了，也就无所谓有<n的更大编号的提案了。为了更好的理解，举个例子来说明： 有2个提案者A、B、C，以及一个接受者D。 A 发送提案编号(5,nil) 给D B 发送提案编号(4,nil) 给D C 发送提案编号(3,nil) 给D 假设CD、AD的网速很快，BD之间的网速比较慢，具体的过程如下：
- 提案(3,nil)先达到D，D回复C：我收到了提案(3,nil)，并且我不再接受比3小的提案了。
- 提案(5,nil)到达了D，D发现5>3可以接受，D回复A：我收到了提案(5,nil)，并且我不再接受比5小的提案了，你放心吧。
- 提案(4,nil)到达了D，D发现4<5，直接丢弃，回复B：你的提案被我扔了，我这最新的提案编号是5。
这样的过程发生在“准备阶段”，这也是为什么paxos算法为什么会有准备阶段的原因。
到此为止我们可以得出以下提案者的提案发布算法：
-
一个提案者选择一个新的提案编号n，将其发送给接受者集合中的每个接受者，并要求这些接受者响应以下内容：
(a) 承诺它不再接受编号小于n的提案。
(b) 如果有编号小于n的提案被接受，那么也要在返回中附上。
我们把这样的一个发送编号n的请求叫做”准备型请求“。
-
如果提案者收到了来自多数接受者节点的响应，它就可以发布自己的提案详情了（也就是提案编号+提案值），最终发出的提案值有两种可能：
(a) 如果所有响应里没有发现已经被接受的编号小于n的提案，那么当前提案者发出自己的提案值。
(b) 否则，在所有响应中找到编号最大的（但小于n）的提案，把它的值作为当前提案者最终发出的提案值。
一个提案者将真正的提案内容（编号+值）发送给一群接受者(这群接受者不一定要和准备阶段的接受者集合一样)，我们把这个请求称之为”采纳型请求“。
“采纳型请求”代表这个请求的作用是让接受者采纳请求中的提案。
以上阐述了一个提案者所使用的提案算法，那么接受者呢？它将接受2种类型的请求：“准备型请求”和“采纳型请求”。接受者可以在不破坏安全性的前提下忽略任何请求。言下之意是接受者只有在被允许的情况下才能相应某个请求：对于“准备型请求”来说，接受者被始终允许响应这些请求；而对于“采纳型请求”来说，当且仅当它没有承诺过不接受的情况下才可以响应这些请求。换句话说：
条件1-1 一个接受者可以接受编号为n的提案的前提是——它没有响应过任何一个编号大于n的“准备型请求“。
注意条件1-1包含了条件1——每个接收者必须接受它收到的第一个提案。
译者注：这句话的意思是“每个接受者必须接受它收到的第一个提案”这个情形是条件1-1的一个特殊例子——因为是第一个，所以肯定没有响应过编号大于第一个编号的“准备型请求”。
到目前为止，我们已经有了一个完整的提案选择算法来满足系统的安全性——本质是使用了全局唯一的提案编号。最终版算法还需要在这个算法上做一点小的优化。
假设一个接受者收到了一个编号为n的“准备型请求”，而在这之前它已经响应了另一个编号大于n（假设为p）的准备型请求并承诺不再接受任何编号为n（小于p）的提案。这种情况下，接受者没有理由响应这个新收到的“准备型请求”——意味着它将不会接受编号为n的提案。因而我们需要接受者放弃这个“准备型请求”。当然了当某个提案被接受者所接受后，该提案对应的“准备型请求”也应该被丢弃——提案都接受了，这个准备阶段的请求自然也没用了。
有了这样的优化之后，一个接受者只需要记住它曾收到的最高编号的提案和它曾响应的最大编号“准备型请求”对应的编号。因为条件2-3必须被满足，而任何接受者都可能会死机，所以接受者需要持久化这些信息以便重启后进行加载。反观提案者则总是可以丢弃一个提案并且不持久化任何信息——因为它发布的提案对应的编号永远不会重复。
把提案者和接受者的行为总结在一起看，我们将会发现算法可以分为以下2个阶段：
阶段1：(a) 某个提案者选择一个提案号n，并且发送一个“准备型请求”给到系统中的大部分接受者节点。 (b) 如果一个接受者收到了一个这个编号为n的“准备型请求”，并且n大于所有它已经响应过的“准备型请求”的编号，那么它将响应这个“准备型请求”，具体的响应内容包含：承诺不再接受编号小于n的“提案”，以及它本地已经接受的编号最大的提案。
阶段2：(a) 如果一个提案者收到了来自大多数接受者节点的准备阶段的响应，然后它将把这个包含提案(n,v)的“接受型请求”发送给所有这些接受者们。它意味着这个提案是所有响应中编号最大的，或者是提案者自己组装的一个提案——来自接受者的响应中没有包含任何提案。 (b) 如果一个接受者收到了一个编号是n的“接受型请求”，除非它收到了编号大于n的“接受型请求”，否则它必须接受这个编号为n的提案。
一个提案者可以发部多种提议，只要每种提议都按照上述算法一个个的进行操作即可。提案者可以在协议运转中的任何一个时刻丢弃提议。（正确性是需要坚持的，尽管请求和/或响应会在提案被丢弃很长一段时间后到达目的地）。当整个系统中有人发出更高编号的提案时，那些发出低编号提案的提案者就该丢弃这些低编号提按。因此在接受者已经接收到更高编号“准备型请求”的前提下，当它又收到了低编号的“准备型请求”或者“接受型请求”，它应当丢弃这些请求并通知发出这些请求的提案者告诉它们目前系统中比他们发出的更高的编号，这些提案者收到后则可以放心的丢弃自己的提案。
2.3 学习一个提案
为了让整个系统中的节点学习被系统所选择的那个提案，一个学习者（learner）必须找出那个大多数节点所接受的提案。一个明显的方法是——无论何时任何接受者在接受某个提案后都需要广播给所有的学习者这个提案。这可以让学习者尽可能快的知道被选中的那个提案，但是它需要每个接受者将提案告知每个学习者——这个数字是接受者数量和学习者数量的乘积。
由于我们采用了非拜占庭错误模型，也就是假设系统中没有伪造信息的情况，所以一个学习者从另一个学习者那里学习哪个值被接受了是很简单的。我们可以让接受者把他们接受的提案发给一个指定的学习者，然后这个学习者在通知其他的学习者。这种方法需要额外的一轮通信来让所有学习者学习被选择的提案。而且这种方法也不太可靠，因为这个指定的学习者可能会宕机（单点问题）。不过这种方法有个好处是整个网络中的响应数量只是接受者和学习者节点的数量之和。