Paxos Made Simple论文

原文
Paxos Made Simple

背景

大神 Leslie Lamport 最初的 PAXOS 论文发表于1998年，不过晦涩难懂
于是大神又在2001又写了一版，也就是这篇论文
这篇论文用尽量简洁的语言，描述复杂的共识算法

共识算法

问题描述

假设一系列进程可以提议一个值，一个共识算法可以确保：只有一个被提议的value能被选择
如果没有提议值，那么就没有值被选择
如果一个value已经被选择，那么进程就可以学习这个被选择的值
一个安全的共识需要确保：

只有被提议的value才能被选择
只能选出一个值
只有当一个value被真实的选择了，进程才会学习这个值

这里没有指定活性要求，但是这个目标确保了如果一些提议最终被选择了，那么进程最终可以学习到这些值
假设agent可以跟其他agent通讯，使用异步方式，且非拜占庭模式

agent 的以任意的速率执行，可以会停止或者重启，由于agent会在选择一个value后重启或失败，那么只能让这个agent记录这个value
消息被传递的时间是任意长的，并可能重复、丢失、但不会出现错误

选择一个value

一个最简单的方式是：只有一个接受者
一个提议者发出一个提议后，接受者选择它接收到的第一个提议值，尽管很简单但有问题，因为一旦接受者挂了就没法接收提议了

改进：

使用多个 接受者
一个提议者发送一个提议给一系列的接受者，一个接受者可以接收这个提议的值
只有当足够多的接受者已经接收了这个值之后，这个值才能被选择
足够多是多少呢？为确保只有一个值被选择，可以让足够大的集合包含大多数agent
因为任何两个多数派，都至少有一个共同的接受者
如果一个接受者最多可以接收一个值，那么这个方式就是有效的
对于多数派论证，在论文【3】中有描述
面对偶然的失败和消息丢失，我们希望即使只有一个提议者提出了一个值，也能被选择

P1

一个接受者必须接受它收到的第一个提议
这种方式有问题，如果不同的提议者同时提出了多个值，然后每个接受者都接收了一个value
但是没有一个value是被多数派接收
即使只有两个提议的value也是如此，如果每个value都被正好一半的接受者接收了，一个接受者如果突然挂了，这会导致不知道哪个value被接收了
P1 和需求说明了，只有多数派的接受者接收了这个值之后，它才能被选择；这也就是暗示了，一个接受者可以接收多个提议

现在，我们给每个提议分配一个自然数字，这样接受者就可以跟踪不同的提议了，所以提议是由：提议数、value 组成
为了防止冲突，我们需要确保不同的提议由不同的数
不过论文中并没有提到如何实现，因为者以来具体的实现细节，论文只是假设这里已经实现了

当单个提议被多数派接受者接收后，这个value就被选择了；在这种情况下，我们就说这个提议被选择了
我们也允许多个提议被选择，但必须保证所有被选择的提案有相同的value，通过对提案编号做归纳，就可以充分的保证

P2-a

如果一个有v的提案被选择了，那么被任何接受者接受的更高编号的议案都有v值
P1 确保了一些提案会被选择，因为通讯是异步的，一个提案可能被一个特殊的接受者选择，而这个接受者甚至没有接受过任何提案
假设一个新的提议者被唤醒，并发送一个更高编号的提案，此提案带有一个不同的值
P1 则要求 c 接受这个提案，但是违反为 P2-a
同时维持 P1和P2-a，需要加强P2-a

P2-b

如果选择了带有v值的提案，则任何提议者发出的更高编号提案都有v值
因为一个提案被任何接受者接受之前，都必须由一个提议者发起
所以 P2-b 意味着 P2-a，也就意味着 P2

为了发现如何才能满足 P2-b，让我们先考虑如何证明它是成立的

我们假设选了编号为 m，值是 v 的提案，并且任何编号 n > m 的提案也具有值 v
我们可以证明提案号 n 有值 v，另外假设每个提案编号在 m … (n - 1)有值 v，其中 i … j 表示从 i 到 j 的数字集合

如果要选择编号为 m 的提案，必须有一个集合 C，由大多数的接受者组成，集合中的每个接受者都接受了它
把这个和归纳假设结合起来，选择 m 的假设就意味着： C 中的每个接受者都接受了一个 m …(n - 1)的提案，并且任何接受者接受的每个 m …(n - 1)的提案值都是 v
因为任何集合 S 包含了大多数的接受者，它至少包含了C中的一个成员，我们可以得出结论，编号为 n 的提议的值为 v，通过确保保持以下不变式成立

P2-c

对于任何v和n，如果一个提案具体有值 v 和编号 n，一个集合 S 包含了多数派的接受者，那么下面条件只能有一个满足：

S中没有接受者接受任何小于编号 n 的提案
v是：集合 S 中被接受者接受的小于n 的所有提案中编号最高的提议值

因此，可以通过维持 P2-c 的不变性来满足 P2-b
为了保持 P2-c 的不变性，要发布编号为 n 的提案，提案者必须知道小于 n 的最大提案编号
如果有这种提案的话，那么它已经、或者将被多数派中的每个分接受者接受了

学习已经接受的提案是很简单的；而预测未来的接受情况则很难
并非直接预测未来，提案者是通过控制一个承诺来实现的，这个承诺就是不会有任何的接受
提案者请求接受者不再接受任何小于 n 的提案编号，这是导致了以下关于发布提案的算法：

一个提案者选择了一个新的提案编号 n，然后发送一个请求给某集合中的每个接受者，要求响应如下：

保证不再接受小于 n 的提案编号
对于已经接受的请求的最大编号(如果有的话) 要小于 n
将上述这样的请求成为：编号为 n 的准备请求

如果提案者收到了多数派的响应，就发布编号 n 值为 v 的提案

这个 v 就是所有响应中编号最高的提案值
如果响应中没有任何提案，那么也会选择这个值
提案者向一组接受方发送提案被接受的请求，以此来发布提案
提案者初始请求的接收者，和第二次发布的接受者，不一定是同一批
对于第二次交互，称为 接受请求

接受者可以接受两种类型的请求：

准备请求，prepare requests
接受请求，accept requests

接受者可以忽略任意请求，不会出现安全问题
它总是可以响应 准备请求，如果没有对应的承诺，它可以响应 接受请求，并接受提案
也就是说

p1-a. 如果一个接受者没有响应过一个大于n的准备请求，则它可以接受编号为 n 的提案
注意，P1-a 包含了 P1
现在，我们有了一个完整的算法，可以选择一个满足所有安全属性的值，这里假设提案编号是唯一的
通过一个小的优化，得到了最终的算法
假设一个接受者接受了一个编号为 n 的准备请求，但是它已经响应过大于n的准备请求了，那么按照之前的承诺，它就不会再接受任何新的编号为 n 的提案了
这样，接受者就没有任何理响应新的准备请求，因此它不再接受提案者发布的编号为n的提案
因此，让接受者忽略这样的准备请求，我们也会忽略已经接受的提案的准备请求

优化后

接受者只需要记住它曾经响应过的最高的提案编号，以及它已经响应过的编号最高的准备请求
因为要维持 p2-c 的不变性，不管当前是否失败，或者机器重启，接受者都必须记住这些信息
注意，提案者总是可以放弃一个提案并忘记它，只要它不再试图发送另一个相同编号的提案

将 接受者 和 提案者的操作放在一起，我们就可以看到算法在如下两个阶段的执过程：

阶段1

一个提案者选一个提案编号n，并发送一个编号为n的准备请求到多数派接受者
如果一个接受者接受了一个编号n的准备请求，而这个编号大于它已经响应过的任何准备请求的编号
接受者响应这个请求，保证不再接受任何小于n的提案，并接受最高的提案编号(如果有的话)

阶段2

如果提案者收到多数派接受者对于准备请求的响应，那么它就发送一个接受请求给每个接受者，同时携带n和值v
v 是响应中的最高提案编号值，如果响应报告中没有提案则可以接受任何值
如果接受者收到一个编号为n的接受请求，除非它已响应了一个大于n的准备请求，否则就接受这个提案

一个提案者可以发送多个提案，只要它遵循算法的每个步骤即可
提案者可以在执行过程中的任意时刻放弃提案(为保持正确性，即使提案请求/响应可能在提案被放弃很久之后才到达目的地)
如果一些提案者已经发送了一个更高编号的提案，那么放弃这个提案可能是更好的方式
如果接受者忽略了一个准备请求、或接受请求，是因为他们已经接受了一个更高编号的准备请求
接受者可以给提案者发送一个响应告知他们放弃了这个请求，这是一个可选的优化，有没有都不影响正确性

学习一个value

为了学习一个被选中的值，一个学习者必须找到被多数派接受的提案
一个简单的算法是，当一个接受者接受了一个提案后，就发送给所有的学习者
这可以使学习者即可得到最新的选择值，但是时间复杂度也很高，响应数量：接受者数量 * 学习者数量
优化：

master学习者

这里假设没有拜占庭式的错误，这样一个学习者可以从其他学习者那里获取接受的值
可以让接受者只请求一个固定的 master学习者，然后master学习者再转发给其他的学习者
这个方案的可靠性可能不够好，但是性能会有大幅度提升

多个master学习者

接受者转发给一群master学习者，再由master学习者转发给所有学习者
提高了可靠性，但通讯的复杂度也提高了

因为消息的丢失，即使一个值被选中了，可能也不会有学习者发现
学习者可以向接受者询问他们接受了哪些提案，但接受者的失败可能导致不知道是否大多数人接收了一个某个提案
在这种情况下，只有当一个新的提案被选择了，学习者才能发现
如果一个学习想知道是否一个值被选中了，它可以让提案者使用上述算法来发布一个提案

进展

假设有这么一个场景：
两个提案者各自不断发布一系列递增的提案号，目前还没有一个被选择
执行过程：

阶段1，p发送了一个编号为 n1的提案，q发布了一个编号为n2的提案
阶段2，p的接受请求被忽略，由于 n2 > n1，所以接受者忽略了n1，并保证不再响应小于n2的编号
提案者p回到阶段1，新发了一个编号n3(n3>n2)，这会导致q的阶段2 的接收请求被忽略
以此类推

为了保证能正常运行，必须要选择一个master提案者来发布提案
如果master提案者跟多数派接受者通讯成功，并且它使用的提案编号大于任务已接受的编号，那么这个提案就被成功的接受了
通过放弃和重试，它就会知道某些请求有着更高的提案编号，那么master提案者最终会选择了一足够高的提案编号
如果系统资源足够(提案者、接受者之间的网络工作正常)，可以一个单个的提案者可以满足活性
相关著作暗示了，选举提案者的可靠算法必须使用随机性、实时性，比如使用超时的方式
当然，不管选举成功或失败，安全性都可以保证

实现

Paxos算法假设有一组网络进程，在其共识算法中，每个进程代表提案者、接受者、学习者这些角色
这个算法会选择一个 leader，这相当于 master提案者以及master学习者
Paxos共识算法，就是前面描述的那样，请求和响应的消息都是普通消息，响应消息被标记了对应的提案编号以防止混淆
为方式接受者宕机，消息需要被持久化保存，接受者在实际发送响应之前，需要先持久化保存

剩下要做的事情是描述一种机制，保证没有两个提案会发布相同的编号
不同的提案者从不相交的数字集合中选择他们的编号，所以两个不同的提案者绝不会发布相同的编号
每个提案者试图发布的最高提案编号，会持久化保存
之后在阶段一(也就是前面描述的)选择一个比曾使用过的更高的提案编号来发布

状态机

实现一个分布式系统的简单方式是，一个客户端集合，可以向一个中央服务发送命令
服务端可以描述为以某种顺序执行客户端命令的状态机
状态机有一个当前状态；通过输入命令并产生输出和新状态，来执行步骤

比如，分布式系统行的客户端可能是出纳员，状态机的状态由所有用户的账户余额组成
减少余额的操作通过状态机的命令来执行，当且仅当状态余额大于提取金额时，减少账户金额，并输出新的、旧的余额
如果只用单台机器则这种实现会有问题，我们使用一组机器，每个机器独立的实现状态机
因为状态机是确定性的，如果所有的机器都执行相同的命令序列，则他们会产生相同的状态序列和输出
发出命令的客户端可以使用任何服务器为其生成的输出

为保证所有的服务器执行相同的状态机命令序列，我们实现一系列Paxos共识算法的独立实例
第i个实例选择的值是序列中第i个状态机命令每个服务在算法的每个实例中都扮演所有角色(提案者、接受者、学习者)
现在，假设服务器的数量是固定的，那么所有的共识算法实例都使用相同的代理集

正常情况下，只有一个服务器会被选择为leader，也就是算法中的master提案者，它是唯一能发出提案的机器
客户端向leader发送命令，leader决定每个命令在序列中的哪个位置出现
如果leader决定某个客户端的命令是第135个命令，它就让这个命令被选为共识算法第135个实例的值
可能会因为宕机而失败，或者另一个服务器认为自己也是leader，并对第135个命令有不同想法
但共识算法，确保最多只能选择一条命令作为第135条命令

这个方式的关键有效性在于，Paxos共识算法，它的值是直到第二阶段才被选择的
在完成共识算法的第一阶段之后，要么确定提案的值，要么提案者可以自由提议任何值
现在来讨论一下Paxos的正常流程，稍后讨论异常的情况；比如一个leader突然挂了，然后一个新的leader被选举；对于系统启动是一种特殊的情况，此时没有命令被提议
新的leader，在共识算法的所有实例中，新的leader一开始都是学习者；它需要知道大多数已被选择的命令
假设它知道命令 1-134、138、139，也就是共识算法的实例1-134、138、139被选择的值
稍后，我们会看到命令序列中，这种缺口是如何出现的
之后，它会执行 135-137，以及所有大于139实例的阶段一
假设这些执行结果，决定了在实例135、140中提议的值；但是所有实例中余下的提案值都是未约束的
leader之后执行了实例 135、140的阶段二，于是选择了命令135、140

leader，以及所有其他学习了leader所知道的命令的服务器，现在可以执行 1 - 135了
但是不能执行138-140，因为136和137还没被选择
leader 可以将客户端后面的两个请求命令变成 136、137，然后立刻填补上136、137的提案空缺
特殊的no-op命令不会改变状态(通过执行共识算法实例的136、137的第二阶段来实现这一点)
一旦no-op命令chosen，136、137就被执行了

命令 1 - 140现在都被选择了，leader现在已经完成了所有共识算法实例 > 140的阶段一，并可以在第二阶段对这些实例提议任何值
客户端传递的命令会被分配为141 编号，这就是下一个命令，并在共识算法实例141的阶段二提案一个值
而再下一个接受的命令就是142，以此类推

在leader知道了已提案的141命令已经被chosen后，就可以提案142命令了
而在提案141命令的过程中，可能所有的消息都会丢失；但在142命令被chosen前，其他任何机器都会学习到，leader提案的141命令是什么
当leader 在收到141命令的阶段二响应时失败了，它会继续重试，如果一切都正常，那么这个提案的命令就被chosen
但是，leader可能在收到阶段二的响应之前就挂了，这就会给 chosen的命令序列留下一个方空洞
通常来说，leader可以提前得到一个a指令，在1到i被chosen后，它就可以提案命令i+1到i+a了
而i - a命令就可能会留下一个空洞

新的leader可以在阶段一执行共识算法的无限多的实例，也就是上面场景的13-137实例，以及所有大于139的实例
对于所有的实例使用相同的提案编号，可以回复一个简短的消息
假设，一个acceptor在阶段二接受过一个提案，那么在阶段一就可以简短的回复一个消息(如135、137实例)
因此，acceptor可以用一个短消息回复所有的实例，在阶段一执行无限多的实例是没有问题的

因为leader宕机，以及选举新leader，一般来说都是很少发生的，那么执行一个状态机命令的开销
也就是达成命令/值的共识，是共识算法第二阶段执行的开销
相比于任何存在失败可能情况下的，并且又要达成一致的算法来说，在Paxos共识算法的阶段二，是最小可能的开销
因此，Paxos算法实际上是最优的

我们上面讨论的情况是，假设总是只有一个leader，除了短暂的leader失败，以及选举一个新leader
在非正常场景下，leader选举会失败，那么没有机器当选为leader，也就没有新的命令被提案
而如果多个机器都当选为leader，那么他们会在相同的实例上提议不同的提案，共识算法会保证不会有任何值被chosen
安全属性也会保护，两个不同的机器，对于第i 个状态机命令的值，永远不会产生分歧
而选举单个leader才能确保算法的活性

如果服务器的集合数量可以更改，那么必须有某种方式来确定，哪些服务器实现了共识算法的哪些实例
最简答的方式是通过状态机本身来实现
当前服务器集合可以作为状态的一部分，可以像普通命令那样被改变
我们可以让一组服务器实例，提案获取a个命令，这些服务器是通过执行共识算法的i+a来得到状态的
而这一切要在i状态机命令先执行
这允许任意复杂的重配置算法，用一个简单的方式来实现

参考

[1] Michael J. Fischer, Nancy Lynch, and Michael S. Paterson. Impossibility of distributed consensus with one faulty process. Journal of the ACM, 32(2):374–382, April 1985.
[2] Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus when there are no faults—a tutorial. TechnicalReport MIT-LCS-TR-821, Laboratory for Computer Science, Massachusetts Institute Technology, Cambridge, MA, 02139, May 2001. also published in SIGACT News 32(2) (June 2001).
[3] Leslie Lamport. The implementation of reliable distributed multiprocess systems. Computer Networks, 2:95–114, 1978.
[4] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 21(7):558–565, July 1978.
[5] Leslie Lamport. The part-time parliament. ACM Transactions on Computer Systems, 16(2):133–169, May 1998.

背景