Paxos 实现日志复制同步
本篇文章以 John Ousterhout（斯坦福大学教授） 和 Diego Ongaro（斯坦福大学获得博士学位，Raft算法发明人） 在 Youtube 上的讲解视频及 ppt 为蓝本，深入分析 Paxos 的内部机制，并以日志拷贝（Replicated Logs）为背景，详细介绍使用 Paxos 协议实现日志副本。
用 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）。但是首先
（1）需要选择一个提议序号，原因在前面已经解释过，需要提供一个唯一的，之前没有使用过的数。然后就会进入准备阶段（prepare phase），在这个过程中，
（2） 提议者（Proposers） 会向集群的所有 接受者（Acceptor） 发起远程过程调用（remote procedure call），每条消息都包含提议序号（Prepare(n)），
（3）当 接受者（Acceptor） 收到 Prepare(n) 请求，它会做两件事情：首先，它需要保证永远不会接受一个提议序号更低的请求，可以通过保存内部变量（minProposal）的方式来达到目的，随着时间的推移，这个值会自动增长，如果当前的请求就是具有最高序号的提议，那么就会更新当前的 minProposal；第二步，就是需要响应并返回接受后的值，如果它之前已接受了某个提议，它会同时记录接受的值及其序号，并返回它当前接受的、具有最高序号的提议值。
（4） 提议者（Proposers） 会等待大多数 接受者（Acceptor） 的响应，一旦它接收到响应，它会检查看是否有返回，以及接受的提议值是什么，这样它会从所有的响应中挑选最高的提议序号，并用这个具有最高提议序号的值作为接受值，以替代它所提议的初始值，并用这个值继续后面的计算。如果没有 接受者（Acceptor） 返回已接受的提议值，那么它会使用自己的初始值继续后面的计算。这里就完成了协议的第一阶段。
（5）这里 提议者（Proposers） 会发送接受请求（Accept(n, value)）到集群的所有服务器，包括一个提议序号 n ，这个值必须与准备阶段的序号值保持一致，以及一个值。这个值可以是 提议者（Proposers） 所提议的初始值，也可以是从 接受者（Acceptor） 返回的接受值。这条消息会广播到集群的所有服务器。
（6）当集群服务器接收到这条消息后，它会将接受请求的提议序号与自己保存的提议序号作比较，如果接受到的提议序号没有保存的序号高，那么就会拒绝这个接受请求，但如果更高，那么就会接受这个提议，并记下这个接受请求的提议序号，以及它的值，并更新当前的提议序号，保证它是最大的。无论接受还是拒绝这个请求， 接受者（Acceptor） 都会返回它当前的提议值。这样 提议者（Proposers） 就可以使用这个返回值来判断请求是否被接受了。
（7） 提议者（Proposers） 会等待直到它接收到多数响应。一旦收到这些响应，它就会检查是否有请求被拒绝，它可以通过返回值和提议序号来进行比较，如果请求被拒绝了，那么这次提议需要回到第（1）步，重新开始。幸运的是它可以通过提议序号判断，那么下一轮就可以选取一个更高的提议序号和值，这样就更有机会在竞争中取胜。大多数情况下，更好的状态是 接受者（Acceptor） 都接受了请求，此时提议值被选定，协议结束执行。
为了保证这个协议能工作正常，集群必须保证三个值的稳定，minProposal、acceptedProposal 以及 acceptedValue ，它们需要保存在稳定的媒介，如磁盘或闪存中。
基础 Paxos 示例
接下来用一些例子来说明提议竞争的状态，以及关键点在于第二次提议的准备阶段。
总共有三种可能。
一、已经选定了之前的值
我们假设有两个提议，值分别是 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）
二、前值没有被选定，但对新提议可见
有可能前一次的提议正在处于接受值的过程中，第二次提议恰好见到了其中的接受值。如上图所示，服务器 S3 已经接受了第一个提议（P3.1 - A3.1 X），第二个提议者正好看见了这个接受值 X ，因为第二个提议者的准备阶段处于前一个提议者接受阶段之后（A3.1 X - P4.5）。所以在这种情况下第二个提议会使用当前已有的值 X ，并放弃 Y 值，并使用来自于 S3 的 X 值作为选定值。
这与前一种情况一样。前后两次提议请求都成功，而且最终都接受选定了相同的值 X 。
当第二次提议看到 X 值的时候，它并不知道这个值是否真的被选定了，因为它只与大多数服务器发生了对话，所以也有可能 S1、S2 已经完成了 X 的接受，而服务器 S5 并不知道。所以，一旦第二次提议看到前序接受的 X 值，它就必须要假设这个值已经被接受选定，并用这个值作为它自己的提议值。
三、前值没有被选定，对新提议也不可见
第三个场景是在第二次提议的准备阶段到来之前，接受值还没有确定，并对第二次提议的准备请求不可见的情况。它可能在别的某个服务器上被接受（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） 无法知道它保存的值是否以及被选中。如果其他的服务器想要知道被选定的值，它就必须自己执行协议。
参考
参考来源:
2013 Paxos lecture, Diego Ongaro
Wiki: Byzantine fault tolerance