原文
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

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

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

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

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

  1. 一个提案者 选择了一个新的提案编号 n,然后发送一个请求给 某集合中的每个接受者,要求响应如下:
  • 保证不再接受小于 n 的提案编号
  • 对于已经接受的请求的最大编号(如果有的话) 要小于 n
  • 将上述这样的请求成为:编号为 n 的准备请求
  1. 如果提案者收到了多数派的响应,就发布编号 n 值为 v 的提案
  • 这个 v 就是所有响应中编号最高的提案值
  • 如果响应中没有任何提案,那么也会选择这个值
  • 提案者向一组接受方发送提案 被接受的请求,以此来发布提案
  • 提案者初始请求的接收者,和第二次发布的接受者,不一定是同一批
  • 对于第二次交互,称为 接受请求

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

  • 准备请求,prepare requests
  • 接受请求,accept requests

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

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

优化后

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

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

  1. 阶段1
  • 一个提案者 选一个提案编号n,并发送一个编号为n准备请求到多数派接受者
  • 如果一个接受者 接受了一个编号n的准备请求,而这个编号大于它已经响应过的任何 准备请求的编号
  • 接受者响应这个请求,保证不再接受任何小于n的提案,并接受最高的提案编号(如果有的话)
  1. 阶段2
  • 如果提案者收到多数派接受者对于 准备请求的响应,那么它就发送一个接受请求给每个接受者,同时携带n和值v
  • v 是响应中的最高提案编号值,如果响应报告中没有提案则可以接受任何值
  • 如果接受者 收到一个编号为n的 接受请求,除非它已响应了一个大于n的准备请求,否则就接受这个提案

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

学习一个value

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

  1. master学习者
  • 这里假设没有 拜占庭式的错误,这样一个学习者可以从其他学习者那里获取接受的值
  • 可以让接受者只请求一个固定的 master学习者,然后master学习者再转发给其他的学习者
  • 这个方案的可靠性 可能不够好,但是性能会有大幅度提升
  1. 多个master学习者
  • 接受者 转发给一群master学习者,再由master学习者转发给所有学习者
  • 提高了可靠性,但通讯的复杂度也提高了

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

进展

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

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

在分布式环境中,为了保证可以正常执行,需要选择一个master提案者来发布提案

实现

状态机

参考

  • [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.