原论文：Paxos Made Live - An Engineering Perspective
领域内描述Paxos算法的资料其实有不少，这里选择的论文是从工程角度阐述依靠Paxos搭建Chubby的经验，而不是像Raft论文那样的理论文章。这篇文章讨论的内容包括Paxos原理、对Paxos做的改进以及工程方面对可测试性、可维护性等做出的额外付出，这篇blog聚焦在Paxos的部分。
我们首先回顾一下一致性共识算法要解决的问题：
硬件设备，尤其是廉价硬件设备的可靠性难以保证。一个构建在这些设备上的分布式系统希望具备容忍各类故障的能力，如网络波动、硬盘故障、系统崩溃等。要实现这一点，思路之一是将分布式系统的状态复制到各个节点中，这样就算出现了部分成员异常，整个系统也能维持正常运转，发生异常的成员后续也能重新接入。
一致性共识算法处理的就是状态复制问题。简单来说，它们将一系列的操作指令分配到每台主机上形成日志，如果出现主机崩溃，其他主机也保留了集群状态。崩溃的主机重新加入集群时，也可以通过接收日志，并重放操作的方式来保持自身状态和集群状态一致。
这里不再介绍Chubby（详见之前的blog），简言之，它是一个分布式锁服务。每个Chubby cell包含5个副本，而Chubby存储的对象（锁、小文件等）都存在底层的数据库里，这个数据库由Paxos复制。
如图，Chubby的底层数据库包含快照和日志两部分。当有数据库操作被提交到该数据库时，该操作会作用于数据库，并记录到日志。而Paxos算法保证所有副本的日志相同。Chubby客户端会同某个单独的Chubby结点通信，并在数据库中更新Chubby集群状态。
论文将Paxos、数据库和Chubby做了分层处理，这是一种工程设计方面的考量，毕竟这种可复制的日志功能完全可以复用到别的系统中。
上图描述了日志层的API，其操作包括submit和callback。前者向日志提交一条操作记录，提交成功后，通过Paxos传播该日志，并触发callback。
Paxos基础
一轮Paxos的过程可以分为如下三个阶段：
- 一个成员被选举为
coordinator（注意，Paxos的coordinator和master是两个概念）； coordinator选择一个值（或者说，操作记录），通过accept消息广播到集群，其他成员可以接受或者拒绝该消息；- 一旦大多数成员接受该消息，集群就达成了一致，
coordinator再广播一条commit消息告知其他成员这一点。（原理上就像是两阶段提交）
在现实场景中Paxos可以被并发执行，这也就是说，集群中同时可能有多个成员变成coordinator，这些coordinator可能选择不同的值进行广播。
为了确保集群能对一个值达成一致，Paxos引入了如下限制机制：
- 给后继
coordinator分配顺序； - 限制每个
coordinator对广播值的选择范围。
给coordinator标定顺序，意味着集群成员能够分辨coordinator的“新旧”，于是便可以拒绝旧的coordinator的accept消息。为了实现这一点，每个coordinator会被分配一个递增的序列号，而每个集群成员都会记录它所见过的最大的序列号。当它想变成coordinator，它就将序列号加一，向集群发送propose消息。集群成员会从propose消息中拿出序列号，并和自己本地记录的序列号做对比。如果大多数成员都认可（propose消息中的序列号更大，此时它回复promise消息，表明它将拒绝更小序列号coordinator的accept消息），则消息的发送者成为coordinator。
一旦集群就某个值达成了一致，后续的coordinator就必须选择同样的值广播，以免破坏一致。为此，promise消息中带有集群成员最近接受的值以及广播这个值的coordinator序列号。新的coordinator必须选择最新的值进行广播，当然，如果所有的promise消息中都没有这类内容，它就可以自由的选择一个前面submit给日志的值。 综合来看，新的coordinator必然会拿到已经达成一致的值的信息（因为该信息被集群大多数认可，它一定存在于至少一个回复promise消息的成员中）。
为就一系列值达成一致，最简单的做法是重复地执行Paxos算法。在论文中，每一次单独执行被视为Paxos的一个实例（instance）。每当给日志submit一个值，就是启动了一个Paxos实例。
在这种Multi-Paxos的场景下，一些成员可能因为各种原因运行缓慢，没有参与到最近的Paxos实例中，状态落后其他成员太多。此时，这些成员可以利用日志来快速跟进状态（catch-up）。每当一个成员要发送消息时，它必须先将自身状态记入日志持久化，意味着一次Paxos实例中必然包含多次磁盘写操作。显然，这里有值得优化的地方：如果消息发送越少，那么磁盘写的次数就越少，算法运行也就越快。如果多个Paxos实例中没有发生coordinator变化（多次Paxos执行都由同一个coordinator发起），我们就可以省略前述Paxos过程第一步的选举过程，即省略一次propose消息的发送和响应。论文把这种优化后的coordinator称为master。更进一步，在一次Paxos实例中，master可以打包广播多个值。
算法优化
磁盘崩溃
当一个成员的磁盘崩溃后，它就失去了它的持久化状态，进而破坏Paxos通信。从表现上看，磁盘崩溃分两种：1）文件内容发生变化；2）文件不再可用。对于前者，论文在每个文件中保存了校验和，方便识别。对于后者，有必要区分磁盘本身为空和磁盘崩溃后信息丢失两种场景。论文依靠第三方GFS进行鉴别：每个成员启动后都会在GFS中做标记。一旦成员重启后磁盘为空，但在GFS中发现标记，那就说明这块磁盘之前崩溃过。
一个磁盘发生崩溃的成员将不会进行投票，其首要任务是恢复自身状态。它将利用catch-up机制快速跟进，但不会发送任何promise或ack消息，直至它观察到了自它重启后执行的一次完整的Paxos实例。
master心跳
论文令master周期性向集群提交心跳值，以通知其他成员自己正常运行，这样它们就不会试图变成coordinator提交值。反之，一旦master失联，集群就会选出带有更大序列号的新master。之前的master仍然会提交值，如果它仍然能和某些成员发生联系，就会得到当前更大的序列号。当它和全部集群成员恢复联系，它就可能用更大的序列号来发起propose，导致整个集群的序列号暴涨。
论文设置master心跳机制的原因是为了确保master正常运行时，其他成员不能向集群提交值，如此一来，master存储的集群状态必然是最新的。对于这类一致性算法，读操作同样也要被记入日志，这样做能够确保读到的就是最近的状态，否则client可能会同落后的master（这里说coordinator更稳妥）进行交互，拿到不那么新的状态。
epoch变量
master在接收到请求到集群达成一致的过程中，有可能失去其master地位，此时，这条请求就应该被丢弃。为了检查这种情况，论文引入epoch概念进行优化。epoch是集群的一个全局状态变量，被存放在底层数据库中。如果master在前述时间段内不发生变化，epoch就不会改变，由此可以判断是否需要丢弃某条请求。
快照机制
同Raft一样，快照是为了控制空间占用和成员恢复时的日志重放时间。本论文中的Paxos框架允许上层应用在任意时间点进行快照操作，此时Paxos会截断当前时间点前的日志，将集群状态保存为快照。一旦有成员崩溃，它在恢复过程中会安装最近的快照，并重放在那之后的日志。快照并不会被同步，每个成员自己决定快照时机。
对Paxos来说，快照机制的引入带来了显而易见的复杂性：
- 快照必须和日志保持逻辑上的相互一致性。每个快照都需要记录它相对于日志的内容信息，论文使用快照句柄（
snapshot handle）实现。句柄里包括与Paxos相关的数据，在创建快照时，句柄会被交给上层应用保存，应用需要将其提交给Paxos，以协调快照和日志。 - 取快照是耗时操作。论文中将取快照分为三个阶段：1）应用请求一个快照句柄；2）取快照；3）操作完成后，应用将快照句柄提交给Paxos，后者据此裁剪日志。
- 取快照操作可能失败。论文的框架里，只有在获取快照句柄后，Paxos才会裁剪日志。在合理的逻辑里，应用会识别第二步中快照的完整性，如果失败，就不会提交句柄。
catch-up时，Paxos成员可能需要重放已经被裁剪的日志，此时它将从其他成员获取快照安装，并根据句柄信息获取还需要的日志。注意，在这个过程中，领先的成员可能还在创建更新的快照，此时catch-up阶段的成员就只能再重复这一过程，请求更新的快照。又及，领先成员在发送完快照后可能会崩溃，此时本成员就得向另一个领先成员建立通信。- 快照的查询机制。快照既可以被设计成通过领先成员传递，也可以设计成通过第三方服务，比如GFS，来传递。论文对这里的设计持开放态度，允许应用程序告知Paxos框架快照的位置信息。