Paxos 实现日志复制同步

本篇文章以 John Ousterhout（斯坦福大学教授）和 Diego Ongaro（斯坦福大学获得博士学位，Raft算法发明人）在 Youtube 上的讲解视频及 ppt 为蓝本，深入分析 Paxos 的内部机制，并以日志复制同步（Replicated Logs）为背景，详细介绍使用 Paxos 协议实现日志复制同步。

Paxos 是在十九世纪80年代末由 Leslie Lamport 发明的，从那开始 Paxos 几乎就成为了分布式系统共识性的同义词。当大学教授分布式系统共识性的时候，几乎总是使用 Paxos 作为算法。Paxos 或许是在所有分布式系统算法中唯一重要的算法。

下面会以日志复制同步为背景介绍 Paxos，并用日志拷贝创建副本状态机（replicated state machine），当说到状态机时，这里指的是一个接收一些输入和生成一些输出，并保留一些内部状态的程序或应用，可以将几乎所有的程序都看成一个状态机。这里的想法是让一个状态机高度可靠，可以通过在多个不同的服务器上并行地运行多个状态机来达到此目的。如果每个状态机都以相同的顺序接收到同样的命令集合，那么它们应该表现出一致的行为并输出相同的结果。所以在理想状态下，如果有些状态机宕掉了，其他的还能继续提供服务。

目标：日志复制同步

实现日志复制同步的目的是让状态机以相同的顺序来处理命令，首先将命令存入日志并保证所有的日志具有相同顺序的相同命令。

系统是这样运行的：

如果一个客户端想要执行状态机里的一条命令，它先会将命令传给其中一个服务器，假设这里的命令是 X ，服务器会记录这条命令，并将它传递给其他的服务器，其他的服务器都会各自记录这条命令，一旦命令在所有的日志中都保存有副本，那么它就可以传递给状态机供执行，我们有时会使用词语 “应用（apply）” 代表命令真实执行的情况，一旦其中一台状态机执行了命令，那么它的结果就会被返回到客户端，可以发现在状态机上只要日志是相同的，处理日志中命令的顺序也是一致的，那么所有状态机所表现的行为也是一样的，这也就是共识模块要保证的 — 日志的副本是正确的。这也就是使用 Paxos 协议的目的。

一个共识模块最关键的特性是：对于一个系统来说，只要有大多数的服务器是可用的，那么它就可以提供所有的服务。所以如果我们有一个 5 台服务器的集群，那么它可以在仅有 3 台服务器可用的情况下，仍然能正常提供服务。所以我们可以容忍 5 台其中的 2 台宕掉。通常情况下，集群的大小会是一个奇数，如 3、5 或 7 。

Paxos 的失败模型是一个非拜占庭的模型，也就是说服务器会宕掉，或者它们会停掉和重启，不过一旦它们运行，它们的行为总是正确的，它们不会有不好的行为（即拜占庭将军问题）。我们也会假设网络会丢失消息，或者会存在消息延迟，也就是说可能会存在到达顺序会和发送顺序不一样的情况。当网络发生短暂隔断时，隔断也可以被修复，并让通信可以再次允许通信。当消息传递时只要系统在工作，就能保证正确。

Paxos 方法

要分解这个问题有多种方式，首先以最简单让人容易想象的共识问题开始 — 基础 Paxos（Basic Paxos） 或单度 Paxos。在这个问题下，我们有一组服务器，其中有些服务器会提议（propose）特定的值。基础 Paxos 的目的是挑选这些值中唯一的一个，这个被选中的值称为（chosen）。所有系统做的就是一次只挑选一个唯一值，它不会挑选第二个值，也不会更改它的选择。这是我们可以想象得到的最简单的共识性算法。当人们用到短语共识性算法的时候，通常就是指的这种最简单的模式。通常我们谈论的 Paxos 也是这个简单版本的 Paxos 。一旦我们有这种非常简单的方式来选择值，我们可以创建日志，为多条日志记录创建多个实例，这就是 多 Paxos（Multi-Paxos） 。我们会先解释 基础 Paxos ，然后介绍如何根据它来构建 多 Paxos。

基本 Paxos 的需求

在介绍 基础 Paxos 之前，我们先来了解一下需求。总体上讲有两个需求，针对于算法的安全性（Safety）和可用性（Liveness）。安全性（Safety）从总体上讲，指的是算法在任何时候都不能做不好的事情，在 基础 Paxos 的语境下，也就是说最多只能选择单个值，不可以选择第二个值取代第一个值。安全性的第二点是说，如果服务器认为一个值被选中，那么它必须真的被服务器选定，不能再改变。可用性（Liveness）指的是我们希望系统最终能做对的事情，仅仅不做不好的事情是不够的。可用性有两个属性，第一个是最终一定会选择某个提议的值，第二点是服务器最终会知道值已经被选中。这个可用性的前提是大多数的服务器是活着的并能进行合理的通讯。

基本 Paxos 的组件

基础 Paxos 有两个主要的组件， 提议者（Proposers） 和 接受者（Acceptors） ， 提议者（Proposers） 是活动元素，它们会主动做一些事情，通常它们会接收来自客户端的请求，获得特定的选定值，然后它会传递这个值，并让集群里的其他服务器也达成一致选择这个值。 接受者（Acceptors） 是被动元素，它们简单地接收来自于 提议者（Proposers） 的请求并做出响应，可以把这种响应当成 “投票” ， 提议者（Proposers） 会尝试获得 接受者（Acceptors） 所投的多数票， 接受者（Acceptors） 会存储多个状态，比如可能被选定或未被选定的值，以及响应的 “投票” 结果。最终它还是会想要知道具体被选定的值是哪个。不过正如我们所见，开始的时候，只有 提议者（Proposers） 知道这个值，但是最终 接受者（Acceptors） 还是需要知道这个值，这样才能将它传递给状态机。在 Lamport 对于这个问题定义的传统公式下，还定了另外一个元素，称为 监听者（Listeners） 。这些元素想要知道被选定的值，在这个例子中， 监听者（Listeners） 是处于 接受者（Acceptors） 内的。不仅如此，在我们介绍的这个例子中，每个服务器都包含一个 提议者（Proposers） 和 接受者（Acceptors） 。想要通过独立的 提议者（Proposers） 和 接受者（Acceptors） 来构建 Paxos 协议也是可能的，但对于这里的例子，我们做以上的前提假设。

接下来会介绍一些我们想要实现共识性所需要解决的问题。

问题

稻草人: 单接受者 (Single Acceptor)

比方说这里有一个例子，但不幸的是它是不正确的。假设我们只选择了一个 接受者（Acceptors） 并让这个 接受者（Acceptors） 选择所有的值，所以在这种情况下，每个 提议者（Proposers） 都会给 接受者（Acceptors） 发送它的值， 接受者（Acceptors） 会挑选其中的一个，然后将其作为选定值。尽管这中实现方式很简单，但是无法解决 接受者（Acceptors） 可能会崩溃问题，如果 接受者（Acceptors） 在选择之后马上就崩溃了，我们就无法知道选定的值是什么，这样就必须进行重启。记住算法的目的是只要大多数节点是可用的，系统就必须能完全正常工作。

这个办法行不通。为了能处理节点失败的情况，我们就必须使用某些仲裁（quorum）的方法，我们需要有一组 接受者（Acceptors） ，通常是一个奇数，如 3 、5 或 7 。如果一个值被大多数 接受者（Acceptors） 选定，那么我们认为这个值被认为是选定的。这样即使在少数服务器崩溃的情况下，还有多数服务器存留可以接受值。甚至在接受后崩溃的情况下，还是可以确定被选定的值。仲裁（quorum）方法可以让我们在某些服务器崩溃后，仍然能保证集群能正常工作。

问题: 分票

不过让仲裁（quorum）能正常工作需要注意一些问题。

例如，我们假设每个 接受者（Acceptors） 都接收它第一次收到的值，然后让多数票的值获胜，如上图我们可以看到，也存在没有任何值是大多数的情况。服务器 S1 和 S2 接受的值是 red ，服务器 S3 和 S4 接受的值是 blue ，服务器 S5 接受的值是 green 。没有任何值在五个服务器中的三个达成一致的。这也就意味着 接受者（Acceptors） 有时需要改变他们的想法，在某些情况下，它们接受了一个值后需要接受另外一个不同的值。也就是说，几乎无法在一轮投票下就能达成一致，往往需要进行几轮的投票才能达到一致。这里接受（accepted）并不代表被选定（chosen），一个值只有在集群大多数节点接受之后才被认为是选定的。

问题: 选择冲突

现在来看另外一个问题，当 接受者（Acceptors） 在更混乱的情况下，它们会接受任何值，但这会带来两个问题，我会在本页和下页中分别讨论这两个问题。

第一个问题是我们可能会最终选择多个值。

例如，服务器 S1 会提议一个值 red ，让其他的服务器接受，这样服务器 S1、S2、S3 接受了这个值，那么现在被选定的值是 red ，因为它已经被多数服务器（3/5）选择。不过随后服务器 S5 来了，提议了一个不同的值 blue ，然后让 接受者（Acceptors） 接受这个值，因为它们会接受任何传递给它们的值，那么此时服务器 S3 接受的值是 blue ，尽管它之前接受的值是 red 。所以现在我们选择的值是 blue 。这样就违背了我们所定义的基础的安全属性的要求 — 我们只能选定一个值。

这个问题的解决办法是，如果第二个 提议者（Proposers） 有新的提议，这里是服务器 S5 ，此时如果已经有选定的值，那么它就必须放弃它自己的值，并提议当前已经选定的值，所以在这种规约下，在服务器 S5 向其他服务器发出请求要求接受它的值之前，它就需要查看集群里的其他服务器，看是否有其他值的存在，如果已经有其他选定的值，服务器 S5 就需要放弃它自己的值，然后使用 red 来代替，这样最终就可以使 red 成为选定的值，我们以第二次选择为终结点，但是最终选择的值是第一次选定的那个值（red）。这也就说，我们需要使用一个两段协议（two-phase protocol）。

不幸的是，只有两段协议（two-phase protocol）本身是不够的。上图说明了这个问题。

例如，服务器 S1 提议了一个值 red 。它首先检查其他的服务器，其他的服务器还没有接受任何值，所以它开始向其他服务器发起请求，希望它们能接受自己的值 red 。不过同时，在其他服务器真正应答之前，另外一个服务器 S5 又提议了另一个值 blue 。这时它也发现还没有其他服务器确定了选定值，那么它就开始发送消息，希望其他服务器能选择 blue 。然后，如果这个请求先结束，服务器 S3、S4、S5 接受并选定 blue ，但与此同时，red 值的服务器仍然处于运行中，因为 接受者（Acceptors） 会接受多个值，所以最终可以看到，会发生仲裁，最终 red 值会被选定，这样就违背了基本安全的属性要求。

这个问题的解决办法是，一旦我们已经选定了值，任何其他的竞争性提议必须被放弃。在上面的例子中，我们就需要服务器 S3 在已经接受了值 blue 后，拒绝对 red 值的接受请求。要想这么做，我们会给提议安排顺序，新的提议优先于所有提议。也就是说 blue 的请求更晚，它会截断 red 请求，这样请求就不会以选择竞争值为结束。

所以总结如下：我们需要一个两段协议（two-phase protocol）。在发起请求前先进行检查，然后我们需要请求有序，这样就能消除老的请求。

接下来我们看看如何使请求有序。

请求序号

采用的方式是为每个请求分配一个唯一的请求序号，使用一个从未被之前请求使用的序号，也就是高的序号要比低序号有更高的优先级，所以当服务器开始执行这个协议， 提议者（Proposers） 必须选择一个新的请求序号，它必须是唯一的，而且比其他序号更高。一种实现方式是将两个值进行拼接，以服务器 ID 为开始，为每个服务器分配一个唯一值，并将其置于请求序号（proposal number）的低位，其他的服务器都不会生成这个请求。在请求序号高位，我们放置一个自增循环数，在集群下所有服务内共享，最近的序号要比之前生成的要高。要想这么做，所有服务器都必须保存这个最大值，并根据它生成每个序号，这个值被称为 maxRound 。这个值必须被持久化到磁盘或其他稳定的媒介，以确保可以在系统崩溃后能够恢复，这样就能保证在系统崩溃恢复以后，请求序号不会重复。

基础 Paxos

本节会对基础 Paxos 做一个小结，详细的内容会在后续介绍。

在之前提到过，我们需要用一个两段协议（two-phase approach），在第一阶段， 提议者（Proposers） 会尝试让一个值被选定，它会向所有服务器发送 RPC 请求，我们将这个请求称为准备（Prepare）。这个请求有两个目的：首先，它会尝试找到其他可能被选定的值，这样就可以保证使用被选定的值，而不是自己的值；其次，如果有其他存在的但未被选中的请求值，它会阻止老的请求，这样就可以避免发生竞争。在第二阶段，会发起另外一个 RPC 请求以及一个选择好的值，如果这个阶段大多数都达成一致，我们就认为这个值已经被选定。

基础 Paxos 协议

上图显示了完整的基础 Paxos 协议，让我们来看看一个完整的请求过程，正如之前所提到的，整个过程是由 提议者（Proposers） 驱动的。 提议者（Proposers） 会由某个它希望选定的值为开始，然后会经历两轮广播消息：准备阶段（prepare phase）和接受阶段（accept phase）。但是首先

需要选择一个提议序号，原因在前面已经解释过，需要提供一个唯一的，之前没有使用过的数。然后就会进入准备阶段（prepare phase），在这个过程中，
提议者（Proposers） 会向集群的所有 接受者（Acceptor） 发起远程过程调用（remote procedure call），每条消息都包含提议序号（Prepare(n)），
当 接受者（Acceptor） 收到 Prepare(n) 请求，它会做两件事情：首先，它需要保证永远不会接受一个提议序号更低的请求，可以通过保存内部变量（minProposal）的方式来达到目的，随着时间的推移，这个值会自动增长，如果当前的请求就是具有最高序号的提议，那么就会更新当前的 minProposal；第二步，就是需要响应并返回接受后的值，如果它之前已接受了某个提议，它会同时记录接受的值及其序号，并返回它当前接受的、具有最高序号的提议值。
提议者（Proposers） 会等待大多数 接受者（Acceptor） 的响应，一旦它接收到响应，它会检查看是否有返回，以及接受的提议值是什么，这样它会从所有的响应中挑选最高的提议序号，并用这个具有最高提议序号的值作为接受值，以替代它所提议的初始值，并用这个值继续后面的计算。如果没有 接受者（Acceptor） 返回已接受的提议值，那么它会使用自己的初始值继续后面的计算。这里就完成了协议的第一阶段。
这里 提议者（Proposers） 会发送接受请求（Accept(n, value)）到集群的所有服务器，包括一个提议序号 n ，这个值必须与准备阶段的序号值保持一致，以及一个值。这个值可以是 提议者（Proposers） 所提议的初始值，也可以是从 接受者（Acceptor） 返回的接受值。这条消息会广播到集群的所有服务器。
当集群服务器接收到这条消息后，它会将接受请求的提议序号与自己保存的提议序号作比较，如果接受到的提议序号没有保存的序号高，那么就会拒绝这个接受请求，但如果更高，那么就会接受这个提议，并记下这个接受请求的提议序号，以及它的值，并更新当前的提议序号，保证它是最大的。无论接受还是拒绝这个请求， 接受者（Acceptor） 都会返回它当前的提议值。这样 提议者（Proposers） 就可以使用这个返回值来判断请求是否被接受了。
提议者（Proposers） 会等待直到它接收到多数响应。一旦收到这些响应，它就会检查是否有请求被拒绝，它可以通过返回值和提议序号来进行比较，如果请求被拒绝了，那么这次提议需要回到第（1）步，重新开始。幸运的是它可以通过提议序号判断，那么下一轮就可以选取一个更高的提议序号和值，这样就更有机会在竞争中取胜。大多数情况下，更好的状态是 接受者（Acceptor） 都接受了请求，此时提议值被选定，协议结束执行。

为了保证这个协议能工作正常，集群必须保证三个值的稳定，minProposal、acceptedProposal 以及 acceptedValue ，它们需要保存在稳定的媒介，如磁盘或闪存中。

基础 Paxos 示例

接下来用一些例子来说明提议竞争的状态，以及关键点在于第二次提议的准备阶段。

总共有三种可能。

1. 已经选定了之前的值

我们假设有两个提议，值分别是 X 和 Y 。一个客户端请求服务器 S1 让 X 被选定，另一个客户端请求服务器 S5 让 Y 被选定，上图的小方格表示特定服务器上的特定请求，所以在 S3 上的小方格 P3.1 表示提议序号 3.1，高位的 3 表示顺序数，地位的 5 表示服务器号，所以 P3.1 来自于 S1 。同样的在 S4 上的 A4.5 X 表示服务器 S4 接受了来自服务器 S5 的请求，以及值 X 。在第二个提议请求来之前，第一个提议请求已经选定了值，也就是说值 X 已经被集群的大多数服务器所接受。因为第二个提议请求也需要大多数服务器得到响应，所以一定可以保证会至少有一个准备（Prepare）请求会到达与前一个请求相同的服务器，这里是 S3 。所以服务器 S5 会发现已经接受的值 X ，当它响应准备请求（Prepare）时，它会放弃 Y 值，并为在所有接受（Accept）请求时使用 X 值。所以在这种情况下，服务器 S5 会成功，并且选定值为 S1 提议的 X 。

后面两种情况的前提是前值没有被选定的情况下，第二次请求进入了准备阶段（Prepare Phase）

2. 前值没有被选定，但对新提议可见

有可能前一次的提议正在处于接受值的过程中，第二次提议恰好见到了其中的接受值。如上图所示，服务器 S3 已经接受了第一个提议（P3.1 - A3.1 X），第二个提议者正好看见了这个接受值 X ，因为第二个提议者的准备阶段处于前一个提议者接受阶段之后（A3.1 X - P4.5）。所以在这种情况下第二个提议会使用当前已有的值 X ，并放弃 Y 值，并使用来自于 S3 的 X 值作为选定值。

这与前一种情况一样。前后两次提议请求都成功，而且最终都接受选定了相同的值 X 。

当第二次提议看到 X 值的时候，它并不知道这个值是否真的被选定了，因为它只与大多数服务器发生了对话，所以也有可能 S1、S2 已经完成了 X 的接受，而服务器 S5 并不知道。所以，一旦第二次提议看到前序接受的 X 值，它就必须要假设这个值已经被接受选定，并用这个值作为它自己的提议值。

3. 前值没有被选定，对新提议也不可见

第三个场景是在第二次提议的准备阶段到来之前，接受值还没有确定，并对第二次提议的准备请求不可见的情况。它可能在别的某个服务器上被接受（S1），但是在第二次提议（S5）的检查范围内，没有前序的值被接受。在这种情况下，服务器 S5 会使用它自己的值 Y 。最终选定的值也是 Y 。这里比较幸运的是 S5 成功阻止了 S1 ，S1 的提议至少会在一台服务器（这里是 S3）上与 S5 的提议相竞争，由于 P4.5 有更高的提议序号值，所以这里 S3 会拒绝接受 X 请求，所以这也会阻止 S1 接受 X ，S1 发起的提议需要重新开始，当再次开始时，会新发起一轮提议，这时它会至少在一台服务器上发现来自 S5 的提议 Y ，所以 S1 发起的提议最终会以 S5 的提议值 Y 作为它的接受值。也就是说，最终在集群内达成了一致，选定值 Y 。

这里的关键点在于这些竞争的提议必须在至少一台服务器上有重叠，这样可以通过它们与服务器通信的顺序来决定最终的结果。要么在前序提议值对后续请求可见的情况下，选定前序接受的值，要么在前序提议值对后续请求者不可见的情况下，会选定后续提议的接受值。任何一种方式都是安全的。

至此，足以说明 Paxos 协议在竞争状态下是安全的，无论如何竞争，最终都会选定某一值并达成一致。但是，这并不能说明基础 Paxos 协议是可用的（Live），可能会发生一组提议相互阻碍的情况，最终不会有任何选定值。下面会对此进行说明。

可用性 (Liveness)

竞争提议可能会导致死锁

假设服务器 S1 成功接收到请求，并处于准备阶段（P 3.1）。在接受值 X 之前（A 3.1 X），另外一个服务器 S5 正处于它的准备阶段（P 3.5），这会阻止前序值的接受（A 3.1 X）。然后 S1 会重新选择提议序号并再次开始提议过程（P 4.1），假设它正进入了第二轮的准备阶段，在接受值之前，服务器 S5 正试图完成接受值的选定 Y （A 3.5 Y），不过此时因为（P 4.1）的序号高于（A 3.5 Y），所以它阻止了（A 3.5 Y）的接受，这样 S5 的提议就失败了，然后 S5 又重新开始下一轮的提议，如此往复，这个过程会无限循环下去。

为了不发生死锁，Paxos 需要以某种补充机制来保证它可以正确运行。一个简单的方式是让服务器等待一会，如果发生接受失败的情况，必须返回重新开始。在重新开始之前等待一会，让提议能有机会完成。可以让集群下服务器随机的延迟，从而避免所有服务器都处于相同的等待时间下。在多 Paxos 协议（Multi-Paxos）下，会有些不同，我们会介绍另外一种被称为领导人选举（leader election）的机制。保证在同一时间下只有一个 提议者（Proposers） 在工作。

其他

基础 Paxos 协议也有它的缺陷。一旦值被选定之后，只有一台服务器（即发起提议的那台服务器）知道它选定的值是什么。 接受者（Acceptor） 无法知道它保存的值是否以及被选中。如果其他的服务器想要知道被选定的值，它就必须自己执行协议。

Multi-Paxos

Multi-Paxos 的目标是创建一个可复制的日志 (create a replicated log)。

一种实现方式是用一组基础 Paxos 实例，每条记录都有一个独立的 Paxos 实例，要想这么做只需要为每个 Prepare 和 Accept 请求增加一个小标索引（index），用来选择特定的记录，所有的服务器为日志里的每条记录都保有独立的状态。

上图展示了一个请求的完整周期。

从客户机开始，它向服务器发送所需执行的命令，它将命令发送至其中一台服务器的 Paxos 模块。
这台服务器运行 Paxos 协议，让该条命令（shl）被选择作为日志记录里的值。这需要它与其他服务器之间进行通信，让所有的服务器都达成一致。
服务器等待所有之前的日志被选定后，新的命令将被应用到状态机。
这时服务器将状态机里的结果返回给客户端。

这是个基本机制，后面会作详细介绍。

Multi-Paxos 的问题

本页介绍了要让 Multi-Paxos 在实际中得以正确运行，所需解决的一些基本问题。

对于一个请求，如何决定该使用哪条日志记录？
第二个问题关于性能。如果用之前的基础 Paxos 中描述的方式，运行会很慢。所以引入了 领导者（leader） 来降低 提议者（proposer） 之间的冲突。还可以消除几乎绝大多数的 准备阶段（Prepare） 的请求，只需要处理一轮 RPC 请求。
第三个问题关于完整复制。如何保证所有的服务器最终都有每天记录，每个服务器都知道被选定的日志记录是什么。
客户端协议。会介绍客户端在服务器崩溃时，如何还能正常工作。
最后一个问题就是配置的变更。如何安全地给 Multi-Paxos 集群增加或移除服务器。

这里需要注意的是，基础 Paxos 已经有非常完整地描述，而且分析也证明它是正确的。非常易于理解。但是 Multi-Paxos 确不是这样，它的描述很抽象，有很多选择处理方式，没有一个是很具体的描述。而且，Multi-Paxos 并没有为我们详细的描述它是如何解决这些问题的。

这篇文章以一种易于理解的方式来解释 Multi-Paxos 的机制。现在我们还没有实现它，也还没有证明它的正确性，所以后续解释可能会有 bug 。但希望这些内容可以对解决问题、构建可用的 Multi-Paxos 协议有所帮助。

选择日志记录

第一个问题是当接收到客户端请求时如何选择日志槽，我们以上图中的例子来阐述如何做到这点。假设我们的集群里有三台服务器，所以 “大多数” 指的是 2 。这里展示了当客户端发送命令（jmp）时，每台服务器上日志的状态，客户端希望这个请求值能在日志中被记录下来，并被状态机执行。

当接收到请求时，服务器 S1 上的记录可能处于不同的状态，服务器知道有些记录已经被选定（1-mov，2-add，6-ret），在后面我会介绍服务器是如何知道这些记录已经被选定的。服务器上也有一些其他的记录（3-cmp），但此时它还不知道这条记录已经被选定。在这个例子中，我们可以看到，实际上记录（3-cmp）已经被选定了，因为在服务器 S3 上也有相同的记录，只是 S1 和 S3 还不知道。还有空白记录（4-，5-）没有接受任何值，不过其他服务器上相应的记录可能已经有值了。

现在来看看发生些什么：

当 jmp 请求到达 S1 后，它会找到第一个没有被选定的记录（3-cmp），然后它会试图让 jmp 作为该记录的选定值。为了让这个例子更具体一些，我们假设服务器 S3 已经下线。所以 Paxos 协议在服务器 S1 和 S2 上运行，服务器 S1 会尝试让记录 3 接受 jmp 值，它正好发现记录 3 内已经有值（3-cmp），这时它会结束选择并进行比较，S1 会向 S2 发送接受（3-cmp）的请求，S2 会接受 S1 上已经接受的 3-cmp 并完成选定。这时（3-cmp）变成粗体，不过还没能完成客户端的请求，所以我们返回到第一步，重新进行选择。找到当前还没有被选定的记录（这次是记录 4-），这时 S1 会发现 S2 相应记录上已经存在接受值（4-sub），所以它会再次放弃 jmp ，并将 sub 值作为它 4- 记录的选定值。所以此时 S1 会再次返回到第一步，重新进行选择，当前未被选定的记录是 5- ，这次它会成功的选定 5-jmp ，因为 S1 没有发现其他服务器上有接受值。

当下一次接收到客户端请求时，首先被查看的记录会是 7- 。

在这种方式下，单个服务器可以同时处理多个客户端请求，也就是说前一个客户端请求会找到记录 3- ，下一个客户端请求就会找到记录 4- ，只要我们为不同的请求使用不同的记录，它们都能以并行的方式独立运行。不过，当进入到状态机后，就必须以一定的顺序来执行命令，命令必须与它们在日志内的顺序一致，也就是说只有当记录 3- 完成执行后，才能执行记录 4- 。

提高效率

下一个需要解决的就是效率问题。在之前描述过的内容中存在两个问题：

第一个问题就是当有多个 提议者（proposer） 同时工作时，仍然会有可能存在竞争冲突的情况，有些请求会被要求重新开始，可能大家还会记得在 基础 Paxos 里介绍过的死锁情况。同样的状况也可以在这里发生，当集群压力过大时，这个问题会非常明显，如果有很多客户端并发的请求集群，所有的服务器都试图在同一条记录上进行值的选定，就可能会出现系统失效或系统超负荷的情况。

第二个问题就是每次客户端的请求都要求两轮的远程调用，第一轮是提议的准备（Prepare）请求阶段，第二轮是提议的接受（Accept）请求阶段。

为了让事情更有效率，这里会做两处调整。首先，我们会安排单个服务器作为活动的 提议者（proposer） ，所有的提议请求都会通过这个服务器来发起。我们称这个服务器为 领导者（leader） 。其次，我们有可能可以消除几乎所有的准备（Prepare）请求，为了达到目的，我们可以为 领导者（leader） 使用一轮提议准备（Prepare），但是准备的对象是完整的日志，而不是单条记录。一旦完成了准备（Prepare），它就可以通过使用接受（Accept）请求，同时创建多条记录。这样就不需要多次使用准备（Prepare）阶段。这样就能减少一半的 RPC 请求。

领导者选举

选举领导者的方式有很多，这里只介绍一种由 Leslie Lamport 建议的简单方式。这个方式的想法是，因为服务器都有它们自己的 ID ，让有最高 ID 的服务器作为领导者。可以通过每个服务器定期（每 T ms）向其他服务器发送心跳消息的方式来实现。这些消息包含发送服务器的 ID ，当然同时所有的服务器都会监控它们从其他服务器处收到的心跳检测，如果它们没有能收到某一具有高 ID 的服务器的心跳消息，这个间隔（通常是 2T ms）需要设置的足够长，让消息有足够的通信传递时间。所以，如果这些服务器没有能接收到高 ID 的服务器消息，然后它们会自己选举成为领导者。也就是说，首先它会从客户端接受到请求，其次在 Paxos 协议中，它会同时扮演 提议者（proposer） 和 接受者（acceptor） 两种角色。如果机器能够接收到来自高 ID 的服务器的心跳消息，它就不会作为领导者，如果它接收到客户端的请求，那么它会拒绝这个请求，并告知客户端与 领导者（leader） 进行通信。另外一件事是，非 领导者（leader） 服务器不会作为 提议者（proposer） ，只会作为 接受者（acceptor） 。这个机制的优势在于，它不太可能出现两个 领导者（leader） 同时工作的情况，即使这样，如果出现了两个 领导者（leader） ，Paxos 协议还是能正常工作，只是不是那么高效而已。

应该注意的是，实际上大多数系统都不会采用这种选举方式，它们会采用基于租约的方式（lease based approach），这比上述介绍的机制要复杂的多，不过也有其优势。

减少准备 (Prepare) 的 RPC 请求

另一个提高效率的方式就是减少准备请求的 RPC 调用次数，我们几乎可以摆脱所有的准备（Prepare）请求。为了理解它的工作方式，让我们先来回忆一下为什么我们需要准确请求（Prepare）。首先，我们需要使用提议序号来阻止老的提议，其次，我们使用准备阶段来检查可能已经被接受的值，这样就可以使用这些值来替代原本自己希望接受的值。

第一个问题是阻止所有的提议，我们可以通过改变提议序号的含义来解决这个问题，我们将提议序号全局化，代表完整的日志，而不是为每个日志记录都保留独立的提议序号。当然我们知道，这么做会让我们在完成一轮准备请求后锁住整个日志，所以后续的日志记录不需要其他的准备请求。

第二个问题有点讨巧。因为在不同接受者的不同日志记录里有很多接受值，为了处理这些值，我们扩展了准备请求的返回信息。和之前一样，准备请求仍然返回 接受者（acceptor） 所接受的最高 ID 的提议，它只对当前记录这么做，不过除了这个， 接受者（acceptor） 会查看当前请求的后续日志记录，如果后续的日志里没有接受值，它还会返回这些记录的标志位 noMoreAccepted 。

最终如果我们使用了这种领导者选举的机制，领导者会达到一个状态，每个 接受者（acceptor） 都返回 noMoreAccepted ，领导者知道所有它已接受的记录。所以一旦达到这个状态，对于单个 接受者（acceptor） 我们不需要再向这些 接受者（acceptor） 发送准备请求，因为它们已经知道了日志的状态。

不仅如此，一旦从集群大多数 接受者（acceptor） 那获得 noMoreAccepted 返回值，我们就不需要发送准备的 RPC 请求。也就是说， 领导者（leader） 可以简单地发送接受（Accept）请求，只需要一轮的 RPC 请求。这个过程会一直执行下去，唯一能改变的就是有其他的服务器被选举成了 领导者（leader） ，当前 领导者（leader） 的接受（Accept）请求会被拒绝，整个过程会重新开始。

复制完整性

这个问题的目的是让所有的 接受者（acceptor） 都能完全接受到日志的最新信息。现在算法并没有提供完整的信息。例如，日志记录可能没有在所有的服务器上被完整复制，所选择的值只是在大多数服务器上被接受。但我们要保证的就是每条日志记录在每台服务器上都被完全复制。第二个问题是，现在只有 提议者（proposer） 知道某个已被选定的特定值，知道的方式是通过收到大多数 接受者（acceptor） 的响应，但其他的服务器并不知道记录是否已被选定。例如， 接受者（acceptor） 不知道它们存储的记录已被选定，所以我们还想通知所有的服务器，让它们知道已被选定的记录。提供这种完整信息的一个原因在于，它要让所有的服务器都可以将命令传至它们的状态机，然后通过这个状态机执行这些命令。所以这些状态机可以和领导者服务器上的状态机保持一致。如果我没有这么做，他们就没有日志记录也不知道哪个日志记录是被选定的，也就无法在状态机中执行这些命令。

下面会通过四步来解释这个过程：

第一步，在我们达成仲裁之前不会停止接受（Accept）请求的 RPC 。也就是说如果我们知道大多数服务器已经选定了日志记录，那么就可以继续在本地状态机中执行命令，并返回给客户端。但是在后台会不断重试这些 Accept RPC 直到获得所有服务器的应答，由于这是后台运行的，所以不会使系统变慢。这样就能保证在本服务器上创建的记录能同步到其他服务器上，这样也就提供了完整的复制。但这并没有解决所有问题，因为也可能有其他更早的日志记录在服务器崩溃前只有部分已复制，没有被完整复制。
第二步，每台服务器需要跟踪每个已知被选中的记录，需要做到两点：首先，如果服务器发现一条记录被选定，它会为这条记录设置 acceptedProposal 值为无穷大 ∞ 。这个标志表示当前的提议已被选定，这个无穷大 ∞ 的意义在于，永远不会再覆盖掉这个已接受的提议，除非获得了另外一个有更高 ID 的提议，所以使用无穷大 ∞ 可以知道，这个提议不再会被覆盖掉。除此之外，每台服务器还会保持一个 firstUnchosenIndex 值：这个值是表示未被标识选定的最小下标位置。这个也是已接受提议值不为无穷大 ∞ 的最低日志记录。
第三步， 提议者（proposer） 为 接受者（acceptor） 提供已知被选定的记录信息，它以捎带的方式在接受请求中提供相关的信息。每条由 提议者（proposer） 发送给 接受者（acceptor） 的请求都包括首个未被选定值的下标索引位置 firstUnchosenIndex ，换句话说 接受者（acceptor） 现在知道所有记录的提议序号低于这个值的都已经被选定，它可以用这个来更新自己。为了解释这个问题，我们用例子来进行说明，假设我们有一个 接受者（acceptor） 里的日志如上图所示，日志中为方便只展示提议序号。在它接收到接受请求之前，日志的信息可知记录 1、2、3、5 已经被标记为了选定，记录 4、6 有其他提议序号，所以它们还没有被认定是已选定的。现在假设接收到接受请求
```
  Accept(proposal=3.4, index=8, value=v, firstUnchosenIndex=7)
```
它的提议序号是 3.4 ，firstUnchosenIndex 的值为 7 ，这也意味着在 提议者（proposer） 看来，所有 1 至 6 位的记录都已经被选定， 接受者（acceptor） 会比较这个提议序号与日志中所有 index < firstfirstUnchosenIndex 的日志的提议序号，如果存在任意记录具有相同的提议序号且没被选定，那么就会标记为已选定。在这个例子中，日志记录 6 有匹配的提议序号 3.4 ，所以 接受者（acceptor） 会标记这条记录为已选定。之所以能这样，是因为 接受者（acceptor） 知道相关信息：首先，因为 接受者（acceptor） 知道当前这个日志记录来自于发送接受消息的同一 提议者（proposer） 且该已经被 提议者（proposer） 选定；而且我们还知道， 提议者（proposer） 没有比这个日志里更新的值，因为在日志记录里已接受的提议序号值与 提议者（proposer） 发送的接受消息中的提议序号值相同 (也就是说没有更加新的 提议者（proposer）)；所以我们知道这条记录在选定范围以内，还是我们所能知道的 提议者（proposer） 里可能的最新值，所以它一定是一个选定的值。所以 接受者（acceptor） 可以将这条记录标记为已选定的。因为同时我们还接收到关于新记录 8 的请求，所以在接收到接受消息之后，记录 8 处提议序号值为 3.4 。

这个机制无法解决所有的问题。问题在于 接受者（acceptor） 可能会接收到来自于不同 提议者（proposer） 的某些日志记录，这里记录 4 可能来自于之前轮次的服务器 S5 ，不幸的是这种情况下， 接受者（acceptor） 是无法知道该记录是否已被选定，它也可能是一个已失效过时的值。它也有可能已经被 提议者（proposer） 选定，但是一个更新的值。所以还需要多做一步。
第四步， 接受者（acceptor） 接收的处理日志记录来自于旧领导者（leader），所以它不确定记录的值是否已被选定。当 接受者（acceptor） 响应接受请求时，它会返回自己的第一个未选定值的下标 firstUnchosenIndex ，当 提议者（proposer） 接收到响应时，会将自己的 firstUnchosenIndex 与响应里的 firstUnchosenIndex 作比较，如果 提议者（proposer） 的下标位置更大，这就表明 接受者（acceptor） 的某些状态是不确定的，这时 提议者（proposer） 会将准确的内容发送给 接受者（acceptor） ，这都可以通过一个新的 RPC 调用来完成。这是 Multi-Paxos 使用的第三种 RPC 调用，这个调用包括两个参数，日志记录的下标位置及该位置的值。这条消息可以让某一特定位置的某一特定值被选定，不会再存在未知的情况，所以接受者只要将这个信息从消息中提取并更新它自己的日志记录即可，然后返回它更新的 firstUnchosenIndex ，因为可能存在有多个未知状态的情况，所以 提议者（proposer） 会发送多个 RPC 请求，直到最后 接受者（acceptor） 与 提议者（proposer） 的日志状态达成一致。

这一系列机制可以保证最终，所有的服务器里的日志记录都可以被选定，而且它们知道已被选定。在通常情况下，是不会有额外开销的，额外的开销仅存在与领导者被切换的情况，这个时间也非常短暂。

客户端协议

Multi-Paxos 第五个问题是客户端如何与系统进行交互的。如果客户端想要发送一条命令，它将命令发送给当前集群的 领导者（leader） 。如果客户端正好刚启动，它并不知道哪个服务器是 领导者（leader），此时它会向任一服务器发送命令，如果服务器不是 领导者（leader） 它会返回一些信息，让客户端重试并向真正的 领导者（leader） 发送命令。一旦 领导者（leader） 收到消息， 领导者（leader） 会为命令确定选定值所处位置，在确定之后，就会将这个命令传递给它自己的状态机，一旦状态机执行命令后，它就会将结果返回给客户端。客户端会一直向某一 领导者（leader） 发送命令，直到它无法找到这个 领导者（leader） 为止，例如， 领导者（leader） 可能会崩溃，此时客户端的请求会发送超时，在此种情况下，客户端会随便选择任意随机选取一台服务器，并对命令进行重试，最终集群会选择一个新的 领导者（leader） 并重试请求，最终请求会成功得到应答。

但是这个重试机制存在问题。

如果 领导者（leader） 已经成功执行了命令，在响应前的最后一秒崩溃了？这时客户端会尝试在新 领导者（leader） 下重试命令，这样就可能会导致相同的命令被执行两次，这是不允许发生的，我们需要保证的是每个命令都仅执行一次。为了达到目的，客户端需要为每条命令提供一个唯一的 ID ，这个 ID 可以是客户端的 ID 以及一个序列号，这条记录包含客户端发送给服务器的信息，服务器会记录这个 ID 以及命令的值，同时，当状态机执行命令时，它会跟踪最近的命令的信息，即最高 ID 序号，在它执行新命令之前，它会检查命令是否已经被执行过，所以在 领导者（leader） 崩溃的情况下，客户端会以新的 领导者（leader） 来重试，新的 领导者（leader） 可以看到所有已执行过的命令，包括旧 领导者（leader） 崩溃之前已执行的命令，这样它就不会重复执行这条命令，只会返回首次执行的结果。

结果就是，只要客户端不崩溃，就能获得 exactly once 的保证，每个客户端命令仅被集群执行一次。如果客户端出现崩溃，就处于 at most once 的情况，也就是说客户端的命令可能执行，也可能没有执行。但是如果客户端是活着的，这些命令只会执行一次。

配置变更

最后的一个问题在配置变更的情况。

这里说的系统配置信息指的是参与共识性协议的服务器信息，通常也就是服务器的 ID ，服务器的网络地址。这些配置的重要性在于，它决定了仲裁过程，当前仲裁的大多数代表什么。如果我们改变服务器数量，那么结果也会发生变化。我们有对配置提出变更的需求，例如如果服务器失败了，我们可能需要切换并替代这台服务器，又或我们需要改变仲裁的规模，我们希望集群更加可靠（比如从 5 台服务器提升到 7 台）。

这些变更需要非常小心，因为它会改变仲裁的规模。

另外一点就是需要保证在任何时候都不能出现两个不重叠的多数派，这会导致同一日志记录选择不同值的情况。在变更过程中，我们仍要保持整个系统的安全特性（还记得我们在前面ppt里讲过的paxos的安全特性吗？安全特性要求：1.系统只能选定一个值；2.如果一台server根据算法得知一个值被选定了，那就是真的被选定了，永远不能改变）。假设我们将集群内服务器从 3 台提升到 5 台时，在某些情况下，有些服务器会相信旧的配置是有效的，有些服务器会认为新配置是有效的。这可能会导致最上图最左侧的两台服务器还以旧的配置信息进行仲裁，选择的值是（v1），而右侧的三台服务器认为新配置是有效的，所以 3 台服务器构成了大多数，这三台服务器会选择一个不同的值（v2）。这是我们不希望发生的。

Leslie Lamport 建议的 Paxos 配置变更方案是用日志来管理这些变更，当前的配置作为日志的一条记录存储，并与其他的日志记录一同被复制同步。所以上图中 1-C1、3-C2 表示两个配置信息，其他的用来存储普通的命令。这里有趣的是，每条记录所使用的配置是由它的更早的记录的配置所决定的。这里有一个系统参数 \(\alpha\) 来决定这个更早是多早，假设 \(\alpha\) 为 3，我们这里有两个配置相关的记录，C1 存于记录 1 中，C2 存于记录 3 中，这也意味着 C1 在 3 条记录内不会生效，也就是说，C1 从记录 4 开始才会生效。C2 从记录 6 开始才会生效。所以当我们选择记录 1、2、3 时，生效的配置会是 C1 之前的那条配置，这里我们将其标记为 C0 。这里的 \(\alpha\) 是在系统启动时配置好的参数，它的大小会限制我们在系统可以同时选定的 log 条数。在 \(i\) 这个位置的值被选定之前，我们不能选定 \(i+\alpha\) 这个位置的值，因为我们不知道中间是否有配置变更。所以如果 \(\alpha\) 值很小，假设就是1，那整个系统就只能是串行工作了，我们只能选定了上一个 log 的值，才能接着选定下一个 log 的值。如果 \(\alpha\) 值是 3，那意味着我们可以同时选定 3 个位置的值，因为我们知道即使有配置变更，在选定这三个位置的 value 时也是不生效的。但如果我们把 \(\alpha\) 值定得非常大，那事情就开始复杂了。例如我们把 \(\alpha\) 值定成 1000，那我们在配置变更后，要等好一阵子，一直到配置所在位置之后的 1000 条 log 都被确定后，我们的配置才会开始生效。为了迫使我们的配置更快的生效，我们可以产生一些 no-op 指令来填充 log，让 log 迅速达到需要的条数，而不用一直等着 client 的命令。

总结一下关于配置变更的处理方法，其实非常简单：我们把配置作为一条普通log一样存储和同步，然后我们就等待系统在一定的条数 log 后采用我们的新配置。

总结

这里重新列了下这次课的内容。让我们总结一下这次 paxos 的课都覆盖了哪些内容。

首先，我覆盖到了 basic paxos，这是你可能想象的最简单形式的一致性问题：多台 server 如何就一个值达成一致意见。记住，他使用了非常重要的两阶段方法：使用 Prepare 阶段来找出已经被选定的值，并且阻止了其他的提议；然后使用 Accept 阶段来完成整个过程。

然后，我描述了怎么让一组 basic paxos 实例一起配合工作来选定一系列的 log。我讲了怎么选定一个 log 位置。接着讲了两个可以提升 paxos 效率的方法：在实际系统中我们并不完全照搬选定单个值的 basic paxos，而是通过 leader 选举来减少这里的竞争；我们通过锁定整个 log 的方式来移除大部分 prepare 请求。我还讲到了怎么才能让所有的 server 都最终得到完整的信息。

我讲到了 client 应该怎么系统交互，这里的关键点在于，client 在发送请求时，带上一个唯一的 id，状态机在执行这些命令时，根据这些i d 来确保一条命令自己只执行一遍。

最后，我讲了如何处理配置变更。通过将配置记录到 log 里边，根据系统参数 \(\alpha\) ，系统在确定每个 log 的值时都知道应该使用什么配置。

感谢大家的参与，希望这个讲解可以让你对 paxos 多了解一点。