酷应用

谷歌大神Jeff Dean点赞网红博士论文：改进分布式共识机制 | 技术头条

百家作者：AI100 2019-04-18 14:04:50

作者 | Heidi Howard

编译 | 刘静

本文转载自公众号图灵TOPIA（ID:turingtopia）

本文作者Heidi Howard，是剑桥大学计算机科学与技术系系统研究小组的分布式系统研究员。

Heidi的研究领域一直围绕分布式系统中的一致性，容错性和性能并且专注于分布式一致性算法。她最广为人知的是Leslie Lamport用于解决共识的Paxos算法的泛化，称为Flexible Paxos。

4 月 16 日，Heidi的博士论文《改进分布式共识》公开，发在 Twitter 上之后 Google 大神 Jeff Dean 点了个赞。

在论文中，她对分布式共识的代表算法Paxos提出了质疑，并证明了当前分布式共识很多未解决的问题只是Paxos这个算法的问题，而不是因为分布式共识本身的问题。

共识机制是什么？

简单来讲，它并不是解决对网络里面的是非的判断，而是说当我在网络中发生了两个可能会产生冲突的交易时候，我去选择哪一个，或者再换一句话说，如果有两个事实都是可以成立的时候，去选择哪一个，这是一个决策的机制，而不是判断是非的机制。

分布式共识是目前大热的区块链的核心技术。

论文摘要

在日常生活中的各个方面，我们都依赖于分布式系统。分布式共识，即在面对故障和异步时达成协议的能力，是用不可靠组件构建可靠分布式系统的基础和强大原语。

20多年来，Paxos算法一直是分布式共识的代名词。Paxos被广泛应用于生产系统，但人们对它知之甚少，并且在实践中证明它是重量级的，不可扩展的和不可靠的。

因此，为了更好地理解该算法，优化其性能并减轻其局限性，Paxos一直是广泛研究的主题。在本文中，我们重新研究了Paxos如何解决分布式共识的基础。我们的假设是，这些限制并不是共识问题所固有的，而是Paxos方法特有的。

令人惊讶的是，我们的分析结果大大削弱了这一广泛研究的算法的要求。我们对分布式共识的修订理解使我们能够构建一个多样化的算法族来解决共识;涵盖了经典算法和新算法，以达到以前认为不可能的共识。我们将探讨这种新理解的广泛影响，从实用优化到生产系统，再到基本新颖的共识方法，从而在性能，可扩展性和可靠性方面实现新的权衡。

论文简介

我们在生活的各个方面都依赖计算机系统。我们希望系统能够快速响应，按预期运行，并在需要时可用。然而，构成这些系统的组件，例如计算机和连接它们的网络，是不可靠的。

分布式共识是指如何在面对故障和异步时可靠地达成一致的问题。这一长期挑战对于分布式系统至关重要，一旦解决了这个问题，我们就可以用不可靠的组件构建可靠的分布式系统。

20年来，Lamport的Paxos算法已经成为分布式共识的代名词。它在生产中得到了广泛的应用，优化、扩展和更好地理解该算法一直是广泛研究的课题。

尽管它很受欢迎，但Paxos在实践中表现不佳，它的方法不够灵活、特别重量级而且不可扩展，在面对异步和失败时可能无法使用。本文重新审视了分布式共识的问题及其解决方法。

首先，我们证明了Paxos实际上只是解决分布式共识的广泛方法的一个方面，这为新一代高性能，可扩展且具有弹性的共识算法打开了大门。然后，我们探索了这个结果可能产生的一些新算法;其中一些甚至能够在以前认为不可能的地方达成共识。

我们描述了在现代分布式系统中达成共识的实际方法。对于不熟悉该领域的读者，我们将概述本研究的历史背景，重点关注分布式共识问题的早期表述如何形成（并且可论证有限）今天如何解决。

接下来是我们对这种广泛采用的方法的批评，以及我们重新审视如何解决共识的动机。我们描述了我们为调查共识而选择的方法，并强调了对共识领域作出的惊人贡献。

现有技术

在各方之间达成协议的能力是现代社会的一项基本必要条件，无论是决定开会的时间还是由谁来治理国家。对于分布式计算机系统也是如此，其中主机需要协议以共享诸如寻址，资源分配，文件系统，主要选举，路由，锁定，排序和协调等重要功能的一致状态。

协议涵盖分布式系统中的广泛决策问题。分布式共识是一个这样的问题，其特征在于两个保证：首先，所有决策都是最终的，不需要假设可靠性或同步性（安全保证）；其次，最终将达成一个决策(进度保证)。如果不对同步性或可靠性做出假设，就无法保证进展。因此，解决共识的算法旨在保证在最弱的活跃度假设下的进展。

Paxos算法最初由Leslie Lamport于1998年提出，后来被改进，是我们今天如何实现分布式共识的核心。从广义上讲，其方法分两个阶段进行，每个阶段都需要大多数参与者的同意。第一阶段是将参与者之一确定为领导者，防止过去的领导者做出任何进一步的决定。

一旦大多数参与者同意谁将领导，领导者将进入第二阶段，通过获得大多数参与者的支持做出决策。领导者负责确保在算法的第一阶段学习到的所有过去的决策都被保留下来，并且只有在安全的情况下才会提出新的值。只要至少大多数参与者正在启动并同步通信，该算法就能保证做出决策。这种方法现在被广泛采用作为许多生产系统的基础。

研究动机

尽管Paxos已经成为分布式系统中达成共识的事实上的方法，但它也并非没有局限性。

首先，Paxos是出了名的难理解，导致了大量的后续工作，用更简单的术语解释算法并填补原始描述中的空白，这是构建实际实现所必需的。理论与系统社区之间的这种不一致最好用以下引语说明：

Paxos算法以简单的英语呈现，非常简单。[Paxos]是最简单，最明显的分布式算法之一。- Leslie Lamport

Paxos非常难以理解。完整的解释是出了名的不透明;很少有人能够成功地理解它，并且只有付出很大的努力。。。。在NSDI 2012的与会者的非正式调查中，我们发现很少有人对Paxos感到满意，即使是经验丰富的研究人员也是如此。

我们的结论是，Paxos没有为系统建设或教育提供良好的基础。- Diego Ongaro和John Ousterhout

其次，对多数协议的依赖意味着Paxos算法决策速度很慢，因为每个算法都需要往返于多个参与者之间。通过让大多数参与者参与每个决策，参与者和领导者之间的网络上设置了高负载。因此，系统的规模有限，通常只有三到五个参与者，因为每增加一名参与者，整体性能就会显著下降。

很明显，如果大多数参与者都失败了，那么Paxos就无法达成协议。但是，这只是整体情况的一部分，未能达成协议不仅会导致主机不可用，还会导致网络分区，主机速度慢，网络拥塞，持久存储等资源争用，时钟偏差，数据包丢失等无数问题。

这些问题在某些系统中很常见，它们通常相互关联并逐步升级。实际上，部署Paxos并不能保证可用性，因为算法的进度取决于满足当今系统无法保证的同步和活跃条件。

Paxos的共识方法是确定了一位参与者为领导者，并使该参与者对决策负责。这种集中式方法将简单性作为单一的序列化点提供，但它也使算法的性能与单个高度拥塞的参与者的性能相关。

由于领导者负责决策，所有决策请求必须转发给领导者并由领导者处理，这进一步增加了决策延迟。领导者在分布式系统中引入了单点故障。虽然Paxos能够在给定条件下从领导者故障中恢复，但是这种恢复可能是缓慢且麻烦的并且通常导致一段时间不可用。

这些限制众所周知，但在实践中很少使用Paxos的替代品。分布式共识中的大量学术文献通常侧重于通过优化，扩展和实用实现来减轻这些限制。鉴于我们迄今为止所讨论的局限性，亚马逊的Dynamo和Facebook的TAO 等生产系统选择牺牲强一致性保证以支持高可用性。

研究方法

自然会出现这样的问题：这些限制是否是共识问题所固有的，还是Paxos算法采用的方法所特有的？同样，Paxos算法是达成共识的最佳解决方案吗？这些问题将指导我们的研究。

我们的方法是重新审视分布式共识的问题，以及我们作为一个社区如何处理这个问题。与以前的工作相比，我们对如何在单一价值上达成共识进行了广泛的研究。由于Paxos的广泛采用以及我们对共识的基础理论的关注，我们的分析结果可能具有广泛的影响，这些影响与特定系统，硬件，工作负载或部署方案无关（因此不受限于范围）。

我们首先开发一个框架，用于证明共识算法的正确性，并将其应用于Paxos算法。该框架的目的是明确如何在正确性证明中使用算法的属性。这允许我们修改算法并验证正确性，而无需重新验证整个算法。

这种方法的令人惊讶的结果有两个方面：确性的证明没有充分利用所提供的属性的强度;其次，有许多方法满足相同的属性。这些观察结果构成了我们逐步推广Paxos算法的基础。在每个阶段，我们都能够通过建立在原始证明的基础上来验证正确性。

研究局限

拜占庭容错 - 我们假设算法被正确地实现和执行。参与者和他们之间的网络不能任意或恶意行动。不假设这种情况的共识算法称为拜占庭容错。PBFT [CL99]是这种算法的一个例子。

重新配置 - 我们假设一组固定且已知的参与者，每个参与者都有一个唯一的标识符。重构在文献中有广泛的讨论，是许多算法的组成部分。例子包括Stoppable Paxos，VRR ，Raft 。

弱化语义 - 我们不支持具有弱化语义的操作，例如过时读取或依赖于同步或有界时钟漂移的操作，例如主租约。

实现细节 - 我们假设无边界存储，任意值的表示，状态或消息没有损坏。参与者可以停止并重新启动。重新启动时，持久状态不变，重新初始化非持久状态，并从头开始再次执行算法。假设本文提供的伪代码由单个线程按顺序执行，并且每条线以原子方式执行。必须在继续之前完成对state的写入，包括写入持久存储。这可以通过诸如预写日志之类的技术来实现。从状态读取必须始终返回一个最新值。

偏序 - 我们的算法决定一个单一值（或决定一个完全有序的，无限的值序列）。我们不考虑就多个系列值，部分有序序列[Lam05b]或有限序列[MLZ08]达成一致。

实践进展 - 参与者可以以任意速度运作。消息最终被传递，但是通信信道传递消息的时间没有限制。消息可能无序或多次传递。然而，算法的进展取决于广泛的假设，包括同步和定时。我们在这些假设下证明了算法的进展，但它们并不是最小的。

特定系统 - 所有算法都是作为高级表示提供的，而不是具体的协议或实现。为了继续适用于一系列现有系统和其他系统，我们不会对特定系统或工作负载进行优化，因为这是广泛研究的主题。例如，Ring Paxos和Multi-Ring Paxos 针对提供IP多播的网络进行了优化。

论文大纲

本文共分为8章，通过逐步推广流行的Paxos算法，构建了解决分布式共识的新型广义算法。总的来说，我们做出了以下重要贡献：

第2章我们首先定义分布式共识的问题，并概述两个已知的解决方案，一个简单的稻草人算法和广泛使用的Paxos算法。我们证明两种算法都满足解决共识的必要要求。

第3章在知识章节的系统化中，我们概述了Paxos算法最常见的改进，将基础算法贡献与文献中使用的框架和术语的细节分开，这些文献中使用的框架和术语通常在不同的出版物中有很大的不同。

第4章我们通过弱化quorum交集要求来概括Paxos算法，允许算法的两个阶段中的每个阶段都有不相交的交集。然后，我们提出了进一步的一般化，通过弱化quorum交集要求，允许算法的第一阶段和随后的第二阶段之间不相交。

第5章我们证明了quorum交集是可传递的并且可以重复使用，允许在某些情况下使用较少的参与者来做出决策。

第6章我们通过利用算法第一阶段的知识来弱化价值选择规则来推广Paxos算法。这种一般化使参与者在选择建议值时具有更大的灵活性。

第7章我们进一步扩展我们的泛型，允许各种共享阶段的机制，以便最好地利用迄今为止的泛型。我们提出的算法可以提供新的进度保证，并可以在几个阶段做出决策。

本论文的结果是一系列实现分布式共识的方法，这些方法概括了最流行的现有算法，如Paxos和Fast Paxos 。我们的目标是进一步了解这个通常知之甚少的领域，并展示解决共识的可能正确方法的广度。