Paxos Made Live - 《Apaas平台》

我们从Google的团队那里得到消息，他们以Chubby为核心实现了Paxos。

这篇论文让人想起了下面的约吉·贝拉的一句话：“理论和实践没有区别。在实践中是这样的：“尽管有关于这个主题的现有文献，但由于各种原因，构建一个生产Paxos系统是一项非常重要的任务…

虽然PaxOS可以用伪代码页来描述，但我们的完整实现包含了几千行C++代码。爆炸不是因为我们使用C++而不是伪符号，也不是因为我们的代码风格可能是冗长的。将该算法转换为一个实用的、生产就绪的系统涉及到实现许多特性和优化——有些在文献中发表，有些没有。

这是一本很好的读物，有助于在你开始创建自己的共识算法实现之前，缓和过度的热情。作者将他们的经验分为三类：文献中的算法缺陷、软件工程挑战和意外失败。它们还包括对Paxos和多Paxos的简要概述。考虑到我们在过去两天里一直在研究该协议，我们将跳过这些内容，但您可能会发现阅读这部分文章很有帮助，因为这些想法是用稍微不同的术语解释的，通过另一个镜头看到它们可以帮助各部分按入到位。

算法挑战
虽然核心Paxos算法描述得很好，但基于它实现容错日志是一项非常重要的工作。

磁盘损坏
**团队必须处理的第一个问题是磁盘损坏的可能性（它发生了，而且还会再次发生！）。“当复制副本的磁盘损坏并失去其持久状态时，它可能会违背过去对其他复制副本所做的承诺。这违反了Paxos算法中的一个关键假设。“校验和被引入来检测更改的文件内容，而‘标记文件’被用于谷歌的分布式文件系统GFS中，以便能够区分副本的磁盘由于故障而变得完全空的和全新的副本。

磁盘损坏的复制副本按如下方式重建其状态。它以无投票权成员的身份参与Paxos；这意味着它使用追赶机制来追赶，但不响应承诺或确认消息。它将保持此状态，直到它观察到一个完整的Paxos实例，该实例是在复制副本开始重建其状态后启动的。通过等待Paxos的额外实例，我们确保此副本不会违背先前的承诺。

主机租约
当使用基本的Paxos算法实现复制数据结构时，读取数据结构需要执行Paxos实例。这将序列化与更新相关的读取，并确保读取当前状态。尤其是，无法从数据结构的主副本中执行读取操作，因为其他副本可能选择了另一个主副本并在不通知旧主副本的情况下修改了数据结构。在这种情况下，主机上的读取操作有返回过时数据的风险。由于读操作通常占所有操作的很大一部分，因此通过Paxos对读操作进行序列化非常昂贵。

为了解决这个问题，引入了一种租用机制，这样当主服务器有一个租用时，就可以保证其他副本不能成功提交给Paxos。这意味着它可以提供本地读取。

该团队还引入了一种定期增加主序列号的机制，以避免频繁的主交换和间歇性的网络中断。

Epoch数
在Google的应用程序中，Chubby需要知道在处理请求的过程中领导力（精通）何时丢失和/或重新获得。因此，他们引入了一个全球纪元数字，领导层的变化划定了纪元。

集团成员
Paxos简单地指出，Paxos本身可以用来协调组更改。

虽然核心Paxos算法的组成员关系很简单，但是当我们引入多Paxos、磁盘损坏等时，确切的细节是不重要的。不幸的是，文献并没有阐明这一点，也没有包含与使用Paxos的组成员关系更改相关的算法的正确性证明。我们必须填补这些空白，使小组成员在我们的系统中发挥作用。

团队通过创建状态机DSL和编译器来将DSL翻译成C++来解决这个问题。“语言设计得很简洁，这样就可以在一个屏幕上呈现完整的算法。”

还引入了广泛的运行时自检机制，包括校验和数据库日志比较。

测试线束会使系统经历一系列长时间的故障，并验证它是否仍按预期工作。

我们的测试从安全模式开始，并向系统注入随机故障。在运行一段预定的时间后，我们停止注入故障，并给系统充分恢复的时间。然后我们将测试切换到活动模式。活性测试的目的是验证系统在一系列失败之后不会死锁。

即使使用状态机DSL和大量的运行时检查，测试工具仍然发现错误：

这个测试在发现各种细微的协议错误（包括组成员身份实现中的错误）和处理损坏磁盘的修改时被证明是有用的。为了测试测试的强度，我们在系统中留下了一些在代码和设计评审期间发现的协议错误，并验证了我们的测试系统检测到了这些错误。经过多次错误修复，测试变得非常稳定。为了提高它的bug产量，我们开始在一个有几百台Google机器的农场上运行这个测试。我们发现了额外的bug，其中一些bug需要数周的模拟执行时间（以极高的失败率）才能找到。

所有这些都显示了为了创建一个完全强化的共识实现所需准备的长度。

快照
为了避免日志不断增长的问题，引入了周期性快照，它能够在失败后从快照中恢复，然后从快照中重放其余的日志。

这种机制一开始看起来很简单，在文献中也有简要介绍。但是，它给系统带来了相当大的复杂性：复制副本的持久状态现在包括一个日志和一个快照，必须一致地维护它们。日志完全由框架控制，而快照格式是特定于应用程序的。

快照的一些细微问题包括协调快照和日志、在复制副本的日志仍在向前移动时拍摄快照、失败的快照以及在恢复期间发生的快照。

软件工程挑战
众所周知，容错算法很难正确表达，即使是伪代码。当这样一个算法的代码与构建一个完整系统所需的所有其他代码混合时，这个问题就更糟了。很难看到核心算法，也很难对其进行推理，或者在出现错误时对其进行调试。这也使得根据需求的变化改变核心算法变得困难。

总结
Paxos算法的描述与实际系统的需求之间存在显著的差距。为了构建一个真实的系统，一个专家需要使用大量分散在文献中的思想，并进行几个相对较小的协议扩展。累积的努力将是巨大的，最终的系统将基于一个未经验证的协议。

对于任何试图实现它的人来说，Paxos绝不是一个简单的协议，尽管它基于相对简单的不变量。本文提供了完整Paxos（或多Paxos）协议的命令式伪代码，而不回避讨论各种实现细节。