paxos协议落地-一个工程视角
概要
我们描述了我们在构建一个容错数据库时使用Paxos共识算法的经验。尽管该领域已经有文献，事实表明构建这样的数据库并非易事。我们描述了被选择的算法和工程问题，和我们找到的对应解决方案。我们的测量表明我们构建了一个有竞争力的系统。
介绍
我们知道通用硬件的容错可以通过复制达到。一个公共的方法是使用共识算法以确保复制相互之间一致。通过反复应用这些算法在输入值序列上，可以在在每个副本上构建相同的日志。如果值是对某个数据结构的操作，所有副本上相同的应用可用于在所有副本上获得相互一致的数据结构。例如，如果日志包含了数据操作序列，并且如果相同的操作序列被应用到每个数据库的本地副本，最终所有的副本将会称为相同数据库内容（前提是，所有的开始都是相同的数据库状态）。
这种通用的方法可以实现各种各样的容错原语，其中的容错数据库只是一个例子。因此，共识问题在过去20年中得到了广泛的研究。有几个知名的共识算法，能在各种环境下操作，并且容忍各种故障。PAxos一致性算法已经在理论上被讨论过了，应用在社区已经有十年了。
我们使用Paxos算法作为基本的实现容错日志的框架。我们然后依赖该框架来构建一个容错数据库。虽然在这个主题上已经存在文献，由于各种原因，构建生成系统被证明是一项不平凡的任务。
- paxos可以用一页伪代码来描述，我们完成的实现包含了几千行C++代码。这不仅仅是因为我们使用了C++而不是伪代码，也不是因为我们的代码风格过于冗长。将代码转化为实际的，生产就绪的系统设计许多特性和优化- 一些发表在文献中，一些没有。
- 容错算法社区习惯于提供短的算法（一页伪代码）的准确性。这种方法不适用于包含数千行代码的系统。为了得到对于真实系统正确性的信心，必须使用不同的方法。
- 容错算法只能容忍有限的精心挑选的错误。然而，真实世界的软件有各种各样的故障模式，包括算法中的错误，实现中的bug，操作员错误。我们必须设计软件并设计操作程序，并且设计操作程序以健壮的处理这些广泛的故障模式。
- 一个真实的系统很少被精确的指定。甚至更遭，规范可能在实现时被修改。因此一个实现需要是可延展的。最后，一个系统可能由于在特殊阶段发生的误会导致故障
这篇论文讨论了算法的选择和工程上的挑战，我们在移动paxos从理论到现实时遇到的。这需要更多的研发努力超过了简单的翻译C++伪代码的建议实现。
这篇论文的剩余部分是安排如下。下面俩个章节展示了这个项目的动机，描述构建系统的一般环境。然后我们提供了对paxos的快速复习。我们将我们的经验分为三类并且以此讨论：文献中算法的差距，软件工程挑战，不可预期的故障。最后我们对系统进行测量，一些对于我们领域最先进计数的一些观察。
2 背景
Chubby是一个谷歌的容错系统，他提供分布式锁机制并且存储小文件。通常每个数据中心一个Chubby事例或者cell。几个谷歌的系统-比如谷歌文件系统和Bigtbable使用Chubby作为分布式协调和存储少量的元数据。
Chubby通过复制实现了容错，一个典型的Chubby cell包含五个副本，运行相同的代码，每个运行在专用的机器上。每个Chubby镀锡（即Chubby lock或者文件）作为一条数据库记录被存储。复制的就是这个数据库。在任意时间，一个副本被叫做master。
Chubby客户端（比如GFS和Bigtable）为它们的服务进行构建。主副本服务于所有Chubby请求。如果Chubby客户端包含了不是master的一个副本，副本将使用master的地址进行回复。Chubby客户端仍然可以联系master。如果master故障了，新的master自动被选出，他将会继续基于它本地被复制的数据库副本及允许服务于流量。因此，被复制的数据库确保了Chubby状态在master失效时的连续性。
第一个版本的Chubby是基于商业的，第三方的，容错的数据库；在本文的其余部分我们把这个数据库成为3DB。该数据库具有复制相关的错误历史记录。事实上，据我们所知，复制机制不是基于经过验证的复制算法，并且我们不知道他是否是正确的。鉴于该产品历史问题以及Chubby的重要性，我们最终确定使用paxos基于自己的方案来取代3DB。
3 架构轮廓
图1展示了单个Chubby副本的架构。基于paxos算法位于协议栈的底部容错的复制日志。每个副本维护一个本地的日志副本。paxos算法根据需要重复运行以确保，所有副本在本地日志中有相同的条目序列。副本之间彼此沟通通过特定的paxos协议。
下一个层是容错复制数据库，它包括了每个副本数据库的本地拷贝。数据库由本地快照和数据库操作的重放日志组成。新的数据库操作被提交到复制的日志。当数据库操操作出现在副本上时，它用于该副本的本地数据库副本。
最后，Chubby使用容错数据库来存储它的状态。Chubby客户端通过Chubby特定的协议和单个Chubby副本进行沟通。
我们致力于设计干净的接口与paxos框架，数据库和Chubby进行分离。我们在开发这个系统时，这样做的原因部分是为了清晰，而且还打算在其他应用程序中重用复制的日志层。我们预计未来在谷歌的系统将通过复制寻求容错。
我们的容错日志API在图2中进行描述，它包含了向新日志提交的调用。一旦提交的值进入容错日志，我们的系统在每个副本上执行客户端应用程序的回调并且通过提交值。
我们的系统是多线程的，并且多个值可以在在不同的线程同时被提交。复制日志不创建自己的线程，但是可以通过任意线程的数量同时执行。这种线程处理方法有助于测试系统，我们在本文后面会详细介绍。
4 paxos之上
在这一章节，我们给出了paxos算法的非正式概述，以及概述如何将它们多个执行链接在一起。我们建议读者参考文献以更正确的描述和准确的协议。已经熟悉paxos的读者可以跳过这一章节。
4.1 基础paxos
paxos是一个一致性算法通过一组程序执行，由一组成为副本的进程执行，以便在故障时就单个值达成一致。副本可能会崩溃并随后恢复。网络可能漏掉复制之间的数据。副本可以访问持久存储，在崩溃时也能存活。一些副本可能提交值以进行共识，如果最终大多数副本运行足够长的时间没有崩溃且没有失败，保证所有正在运行的副本都同意提交的值之一。在我们的系统中，要商定的值是（复制）日志中的下一个条目。
算法包含了三个阶段，它可以被重复（由于故障）
- 选举副本作为协调者
- 协调器选择一个值，并在称为accept消息的消息中将其广播给所有副本。其他副本要么acknowledge要么rejec它。
- 一旦大部分的副本acknowledge这个协调，共识被达成，并且协调器广播提交信息以通知副本。
为了提供算法是如何工作的直觉，考虑在只有一个协调器，并且没有故障的情况。一旦大多数副本接收到来自协调器的accept信息并acknowledge它，共识就被达到了。之后如果任何少数的副本故障，我们仍然保持只少一个副本是活的，并且收到了共识。
相关的协调器可能故障。paxos不需要一次只有一个副本充当协调器。多个副本可能决定成为协调器，并且在任何时候执行算法。通常系统的设计是为了限制协调器更替，因为它会影响达成共识。paxos确保可以对单个值达成共识（它可以来自任何协调及诶单），这是通过额外的机制引入的：1 为后续的协调者进行排序 2限制每个协调者在选择值是的选择。
排序协调器允许在每个副本区分当前的协调器和之前的协调器。在这个方法中，副本可以拒绝来自老的协调器的消息并且维护在共识达成后破坏共识。Paxos通过协调器分配一个递增的序列号来排序它们。每个副本都会跟踪到目前为止看到最新的序列号。当一个副本想要成为协调者，它要生成一个唯一的序列号比任何它见过的都要高，并且以提议消息的形式广播给所有的副本。如果大多数副本恢复那么代表它们没有看到过更高的序列号然后副本作为协调器。这些回复被称为承诺消息，因为副本承诺从此以后拒绝来自旧协调器的消息。这个提议、承诺消息构成了上述的第一步。
一旦在值上达成共识paxos必须强制未来的协调器选择相同的值，以确保继续协议。为了保证这一点，来自副本的承诺消息包括它们听到的最近的值（如果有的话），以及从其听到该值的协调器的序列号。新的协调器从最新的协调器中选择值，如果所有的承诺消息都不包含值，协调器可以自由的选择提交的值。
这种做法行得通的原因和微妙，但大致如下。新的协调器需要响应大多数副提案的消息。因此，如果前任的协调员达成了协商一致，新的协调器被保证从最少一个节点能够听到确定的值。通过归纳，该值将具有接受到响应中的最高序列号，因此将由心的协调者选出。
4.2 Multi-Paxos
现实中的系统使用paxos构建块以在连续的值上达成共识，比如在复制日志中。一个简单实现它的方法是定期执行paxos算法。我们每次执行称为paxos的实例。我们指向的是paxos提交一个值（或者相同的到日志）表示一个paxos的执行实例同时提交那个值。
在multi-paxos中一些缓慢（滞后）的副本可能没有参与最近的paxos实例。我们使用catch-up机制来确保落后的副本能够跟上主副本。
每个副本维护一个本地的持久化日志来记录所有的paxos动作。当副本崩溃并随后恢复时，它重放持久日志以重建崩溃前的状态。副本在帮助落后副本赶上时也使用此日志。到目前为止所描述的paxos算法要求所有消息发送方在发送消息之前的记录状态-因此算法需要五次的写入序列（对于每个提议，承诺，接收，确认和提交消息）到其关键路径上的磁盘。注意，所有写操作必须立即刷新到磁盘，然后系统才能继续进行。在系统中副本是网络接近的，磁盘刷新时间可以支配实现的总体延迟时间。
有一种众所周知的优化，将多个paxos实例链接在一起来减少所涉及的消息数量。如果协调器表示在实例之间没有更改，则可以省略提议消息。这不会干扰paxos的属性，因为任何副本在任何的时间可以通过广播更高序列号的信息尝试称为协调者，Multi-paxos可以被用来长时间周期的选择一个协调者，尝试不让协调者改变。我们把这个协调器称为master。通过这种优化，Paxos算法只需要对每个副本上的每个Paxos实例进行一次磁盘写操作，并彼此并行执行。主机在发送其接受消息后立即写入磁盘，而其他副本在发送确认消息之前写入磁盘。
为了在并发系统中获得额外的吞吐量，可以将不同应用程序线程提交的一组值批处理到单个Paxos实例中。
5 算法挑战
虽然核心的paxos算法已经被描述的很好了，基于它实现容错日志是一个不容易的努力。有些复杂性是因为现实中的不完美（如磁盘故障和有限的资源），有些是因为额外的需求（实例，master租约）。许多挑战都有算法解决方案，这与核心的paxos算法相关。下面介绍我们引入的一些机制。
5.1 处理磁盘损坏
副本不时见证磁盘损坏。由于介质故障或者操作错误（操作员可能会意外的擦除关键数据），磁盘可能会损坏。当副本的磁盘损坏时，它丢失持久化的状态，它可能会违背对其他副本做出的承诺。这违反了paxos中的一个关键假设。我们使用以下机制来解决这个问题。
磁盘损坏有俩中表现形式。要么文件内容被改变了要么文件会变得不可访问。为了探测前者我们存储文件中每个文件的校验和。后者可能与具有空磁盘的新副本无法区分-我们通过在启动后让新副本在GFS中留下标记来检测这种情况。如果这个副本以空磁盘再次启动，如果发现GFS标记那么代表着它的磁盘故障。
一个故障磁盘的副本用以下方式重建它的状态。它作为没有投票权的成员后加入paxos；意味着它使用catch-up机制来追赶，但是不响应承诺或者确认消息。它一直保持这种状态，直到它观察到一个完整的paxos实例，该实例是在副本重建其状态后启动的。通过等待额外的paxos实例，通过等待额外的paxos实例，我们确认了这个副本不会违约它早期的承诺。
这个机制允许以下的操作以降低系统中的延迟。因为系统现在可以处理偶然的磁盘故障，在这样的环境下，不立即将内容刷新到磁盘是可以接受的。虽然我们考虑过利用这一观察结果的方案，但我们目前没有实现它。
5.2 master 租约
当basic paxos算法被用来实现重复的数据结构，读取数据结构需要执行paxos实例。这将读取与更新序列化以确保当前的读取状态。事实上，读取操作不能从数据结构的主副本提供，因为可能其他副本已经选择了另一个主并且在没有通知旧主的情况修改了数据结构。在这种情况下，读取主服务器的操作有返回旧数据的风险。由于读取操作通常占有很大一部分，通过串行读取是昂贵的。
解决方法是实现master租约使用以下的语义：只要master持有了租约，它保证其他副本抱你成功的提交值到paxos。因此有租约的master有本地数据结构中最新的信息，这可以被用来服务完全本地的读取操作。通过让master尝试在租约到期之前更新它，我们可以确认master可以在大部分时间持有租约。在我们的系统中，masters承担维护租约几天。
在我们的视线中，所有副本都隐式的授予前一个paxos实例的主节点，并在租约期间拒绝处理从其他副本到达的paxos信息。master为租约维护的超时时间比副本要短- 这防止了时钟偏移。主服务器定期向paxos提交一个虚拟的心跳来刷新租约。
当出现间歇性网络中断时，Multi-paxos优化表现出以下的稳定性问题。当master暂时断开连接，paxos将会选举新的master，新的master将在paxos实例之间维护一个固定的序列号。在此期间，当断开连接的旧主机试图允许paxos算法时，如果它成功连接另一个副本，它可能会增强它的序列号。当它重新连接时，它可能有比新主更高的序列好，并且能够替换掉新主。稍后它可能会再次断开，并且这样的循环可能会重复。
这种行为是不可取的，因为Chubby master的更改可能会对某些用户产生负面的影响。此外，在连通性差的网络中，这种行为可能会退化为快速的主更改。
在我们的实现中，通过运行整一轮的paxos算法，master定期增加它的序列号，包括发送提议信息。在大多数情况下，以适当的频率增加可以避免这种类型的错乱。
请注意，租约的概念可以扩展到所有副本。这允许任何有租约的副本从本地磁盘数据结构中服务读取请求。当读取流量明显的超过写入流量时，这个机制很有用。我们已经研究了副本租约的算法，但是还没有实现它。
5.3 epoch 号
请求（Chubby客户端）提交到Chubby cell是直接到当前的Chubby master副本的。从主副本接收到请求开始算起，请求导致底层数据库的更新，副本可能已经失去其主状态。它甚至可能在丢失master状态后又重新获得了它。如果主的身份在处理请求期间失去或者重新获得，Chubby需要组织到来的请求。我们需要一种机制来可靠的探测主切换，在必要时终止操作。
我们通过引入全局epoch号来解决这个问题，它有以下的语义。如果在两个请求之间的时间间隔内该副本连续为主副本，则对主副本的epoch号的两个请求接收相同的值。epoch号座位一个条目存储在数据库中，所有的数据库操作都以epoch号的值为条件。
5.4 组成员
现实中的系统必须能够处理副本集的改变。这在文献中被称为组成员问题。一些paxos论文指出，paxos算法自身可以被用来实现组成员。虽然核心paxos算法的组成员关系很简单，当我们引入Multi-Paxos，磁盘损坏等时，确切的细节是非平凡的。不行的是文献中并没有说明这一点，它也不包含使用paxos组成员关系的正确性证明。我们必须填补这些空白，使组成员制在我们的系统中发挥作用。细节——尽管相对次要——是微妙的，超出了本文的范围。