论文

Patrick Hunt and Mahadev Konar Yahoo! Grid {phunt,mahadev}@yahoo-inc.com Flavio P. Junqueira and Benjamin Reed Yahoo! Research {fpj,breed}@yahoo-inc.com 摘要 在本文中，我们描述了Zookeeper，一种用于协调分布式应用程序进程的服务。由于Zookeeper是关键基础设施的一部分，它旨在为客户端构建更复杂的协调原语提供一个简单且高性能的核心。它在一个复制的集中式服务中结合了组消息传递、共享寄存器和分布式锁服务的元素。Zookeeper提供的接口具有共享寄存器的无等待特性，并带有一个类似于分布式文件系统中缓存失效的事件驱动机制，从而提供一个简单而强大的协调服务。 Zookeeper的接口支持高性能服务实现。除了无等待特性外，Zookeeper还为客户机提供了请求的先进先出（FIFO）执行保证，并对所有改变Zookeeper状态的请求提供线性一致性。这些设计决策使得实现高性能处理流水线成为可能，读请求可以由本地服务器满足。我们展示了针对目标工作负载（读写比例为2:1到100:1），Zookeeper每秒能够处理数万到数十万次事务。这种性能允许客户端应用程序广泛使用Zookeeper。 1 引言 大规模分布式应用程序需要不同形式的协调。配置是最基本的协调形式之一。在其最简单的形式中，配置只是系统进程的操作参数列表，而更复杂的系统则具有动态配置参数。组成员关系和领导者选举在分布式系统中也很常见：通常进程需要知道其他哪些进程是活跃的以及这些进程负责什么。锁是一种强大的协调原语，用于实现对关键资源的互斥访问。 一种协调的方法是为每种不同的协调需求开发特定的服务。例如，Amazon Simple Queue Service 1 专门针对队列设计。其他服务则专门为领导者选举 2 和配置 3 开发。实现更强大原语的服务可以用来实现功能较弱的原语。例如，Chubby 4 是一个具有强同步保证的锁定服务。然后可以使用锁来实现领导者选举、组成员关系等。 在设计我们的协调服务时，我们没有选择在服务器端实现特定的原语，而是选择公开一个API，使应用程序开发人员能够实现自己的原语。这种选择导致了协调内核（coordination kernel）的实现，使得无需更改服务核心即可启用新的原语。这种方法允许根据应用的需求适应多种协调形式，而不是限制开发者使用固定的一组原语。 在设计Zookeeper的API时，我们避开了锁等阻塞原语。协调服务中的阻塞原语可能会导致诸如慢速或故障客户端对更快客户端性能产生负面影响等问题。如果请求处理依赖于其他客户端的响应和故障检测，服务本身的实现也会变得更加复杂。因此，我们的系统Zookeeper实现了一个操作简单无等待（wait-free）数据对象的API，这些数据对象以类似于文件系统的方式进行层次化组织。实际上，Zookeeper的API与其他文件系统的API相似，仅从API签名来看，Zookeeper似乎就是没有锁方法、打开和关闭功能的Chubby。然而，实现无等待数据对象使Zookeeper与基于锁等阻塞原语的系统有显著区别。 尽管无等待特性对性能和容错至关重要，但对于协调来说，这还不够。我们还需要为操作提供顺序保证。特别是，我们发现保证所有操作的先进先出（FIFO）客户机顺序和写操作的线性一致性，能够实现服务的高效实施，并且足以实现对我们应用程序感兴趣的协调原语。实际上，我们可以使用我们的API为任意数量的进程实现共识，根据Herlihy的层次结构，Zookeeper实现了通用对象5。 Zookeeper服务由一组使用复制技术以实现高可用性和性能的服务器组成。其高性能使得包含大量进程的应用程序能够使用这种协调内核来管理所有方面的协调。我们能够使用一种简单的流水线架构实现Zookeeper，这种架构允许我们在仍有低延迟的情况下处理数百或数千个未完成的请求。这样的流水线自然支持单个客户端操作按FIFO顺序执行。保证FIFO客户机顺序使客户机可以异步提交操作。通过异步操作，客户机能够同时拥有多个未完成的操作。例如，当一个新的客户机成为领导者并且需要相应地操作和更新元数据时，这一特性是理想的。如果没有多未完成操作的可能性，初始化时间可能会达到数秒而不是亚秒级。 为了保证更新操作满足线性一致性，我们实现了一个基于领导者的原子广播协议6，称为Zab7。然而，一个典型的Zookeeper应用程序工作负载主要由读操作主导，因此需要扩展读吞吐量。在Zookeeper中，服务器本地处理读操作，并且不使用Zab对它们进行全局排序。 客户端侧缓存数据是提高读性能的重要技术。例如，对于一个进程来说，缓存当前领导者的标识符比每次需要知道领导者信息时都查询Zookeeper要高效得多。Zookeeper使用观察机制使客户端能够在不直接管理客户端缓存的情况下缓存数据。通过这种机制，客户端可以监视给定数据对象的更新，并在发生更新时收到通知。Chubby直接管理客户端缓存，它阻止更新以使所有缓存了正在更改数据的客户端的缓存失效。在这种设计下，如果这些客户端中有任何一个缓慢或出现故障，更新将会被延迟。Chubby使用租约防止故障客户端无限期地阻塞系统。然而，租约仅限制了缓慢或故障客户端的影响，而Zookeeper的观察机制则完全避免了这一问题。 在本文中，我们讨论 ZooKeeper 的设计和实现。借助 ZooKeeper，我们能够实现应用程序所需的所有协调原语，即使只有写入是可线性化的。为了验证我们的方法，我们展示了如何使用 ZooKeeper 实现一些协调原语。 总之，本文的主要贡献如下： 协调内核：我们提出了一种具有宽松一致性保证的无等待协调服务，用于分布式系统中。特别是，我们描述了协调内核的设计与实现，该内核已在许多关键应用中用于实现各种协调技术。 协调方案：我们展示了如何使用Zookeeper构建更高级别的协调原语，甚至是阻塞和强一致性的原语，这些原语在分布式应用中经常被使用。 协调经验：我们分享了一些使用Zookeeper的方式，并评估了其性能。通过这些实际应用和性能评估，我们可以更好地理解Zookeeper在真实环境中的表现及其对分布式应用的支持能力。 2 ZooKeeper 服务 客户通过使用Zookeeper客户端库的客户端API向Zookeeper提交请求。除了通过客户端API暴露Zookeeper服务接口外，客户端库还管理客户端与Zookeeper服务器之间的网络连接。在本节中，我们首先提供Zookeeper服务的高层视图。然后讨论客户端用于与Zookeeper交互的API。 术语。在本文中，我们使用客户端（client）表示ZooKeeper服务的用户，服务器（server）表示提供ZooKeeper服务的进程，znode表示ZooKeeper数据中的内存数据节点，这些节点在一个分层命名空间中组织，称为数据树（data tree）。我们还使用术语更新和写入来指代任何修改数据树状态的操作。客户端在连接到ZooKeeper并获取会话句柄通过其发出请求时建立会话（session）。 2.1 服务总览 ZooKeeper为其客户端提供了一组按照分层命名空间组织的数据节点（znodes）的抽象。这个层次结构中的znodes是客户端通过ZooKeeper API进行操作的数据对象。分层命名空间常见于文件系统中，这是一种理想的组织数据对象的方式，因为用户对此抽象非常熟悉，并且它能够更好地组织应用程序元数据。为了引用一个特定的znode，我们使用标准的UNIX文件系统路径表示法。例如，我们使用/A/B/C来表示znode C的路径，其中C的父节点是B，而B的父节点是A。所有znodes都存储数据，并且除了临时znodes外，所有znodes都可以有子节点。 客户端可以创建两种类型的 znode： 常规znodes（regular）：客户端通过显式地创建和删除来操作常规znodes。 临时znodes（ephemeral）：客户端创建此类znodes，它们要么由客户端显式删除，要么在创建它们的会话终止（无论是故意终止还是由于故障）时由系统自动移除。 此外，当创建一个新的znode时，客户端可以设置一个顺序（sequential）标志。设置了顺序标志的节点会在其名称后附加一个单调递增计数器的值。如果$n$是新的znode，$p$是父znode，则$n$的序列值永远不会小于在$p$下创建的任何其他顺序znode名称中的值。 ZooKeeper实现了监视（watches）机制，允许客户端在不进行轮询的情况下及时接收变化的通知。当客户端发出带有监视标志的读操作时，操作会正常完成，但服务器承诺在返回的信息发生变化时通知客户端。监视是一次性触发器，与一个会话相关联；一旦触发或会话关闭，它们就会被注销。监视仅指示发生了变化，但不会提供具体的变化内容。例如，如果客户端在“/foo”被更改两次之前发出getData(''/foo'', true)，客户端将收到一个监视事件，告知“/foo”的数据已更改。会话事件，如连接丢失事件，也会发送到监视回调中，以便客户端知道监视事件可能会延迟。...

Diego Ongaro and John Ousterhout Stanford University 摘要 Raft 是一种用于管理复制日志的共识算法。它能够产生与(多)Paxos 相同的结果，并且效率与 Paxos 相当，但其结构与 Paxos 不同。这种结构上的差异使得 Raft 比 Paxos 更容易理解，同时也为构建实际系统提供了更好的基础。为了提升可理解性，Raft 将共识的关键要素进行了分离，如领导者选举、日志复制和安全性保证等，并且强化了一致性要求以减少需要考虑的状态数量。用户研究的结果表明，相比 Paxos，学生们更容易掌握 Raft。此外，Raft 还引入了一种新的集群成员变更机制，该机制通过使用重叠的多数派来保证安全性。 1 引言 共识算法使得一组机器能够作为一个连贯的整体工作，并且能够在部分成员发生故障时继续运行。正因如此，这类算法在构建可靠的大规模软件系统中发挥着关键作用。在过去的十年里，Paxos1 2主导了关于共识算法的讨论：大多数共识算法的实现要么基于 Paxos，要么受到它的影响，而且 Paxos 已经成为向学生教授共识知识的主要载体。 不幸的是，尽管已经有许多让它变得更容易理解的尝试，Paxos 仍然非常难以理解。此外，它的架构需要进行复杂的改动才能支持实际系统。因此，系统构建者和学生都在与 Paxos 作斗争。 在我们自己也经历过与 Paxos 搏斗之后，我们着手寻找一种新的共识算法，希望它能为系统构建和教育提供更好的基础。我们采用了一种不同寻常的方式，即将 可理解性（understandability） 作为首要目标：我们能否定义一个用于实际系统的共识算法，并以一种比 Paxos 容易得多的方式来描述它？此外，我们希望这个算法能够帮助系统构建者形成必要的直观认识。重要的不仅是算法能够工作，更重要的是能够清楚地理解为什么它能工作。 这项工作的成果就是一个称为 Raft 的共识算法。在设计 Raft 时，我们应用了特定的技术来提高可理解性，包括分解（Raft 将领导者选举、日志复制和安全性分开）和状态空间简化（相比 Paxos，Raft 减少了不确定性的程度以及服务器之间可能产生不一致的方式）。在两所大学进行的涉及 43 名学生的用户研究表明，Raft 比 Paxos 更容易理解:在学习了这两种算法之后，其中 33 名学生对 Raft 的相关问题回答得比 Paxos 的问题要好。 Raft 在许多方面与现有的共识算法相似（最值得注意的是 Oki 和 Liskov 的 Viewstamped Replication 3 4），但它有几个新颖的特点：...

Jeffrey Dean and Sanjay Ghemawat jeff@google.com, sanjay@google.com Google, Inc. 摘要 MapReduce 是一种用于处理和生成大型数据集的编程模型和相关实现。用户指定一个 map 函数来处理键/值对，生成一组中间键/值对，并指定一个 reduce 函数来合并与同一中间键相关的所有中间值。如本文所示，许多现实世界中的任务都可以用这个模型来表达。 以这种函数式风格编写的程序会自动并行化，并在大型商用机器集群上执行。运行时系统会处理分割输入数据、调度程序在一组机器上的执行、处理机器故障以及管理所需的机器间通信等细节。这样，没有任何并行和分布式系统经验的程序员也能轻松利用大型分布式系统的资源。 我们的 MapReduce 实现运行在大型商用机器集群上，并且具有高度可扩展性：典型的 MapReduce 计算在数千台机器上处理数 TB 的数据。程序员发现该系统易于使用：数百个 MapReduce 程序已经实现，并且每天在 Google 集群上执行超过一千个 MapReduce 作业。 1 引言 在过去五年中，本文作者和 Google 的许多其他人已经实现了数百种特殊用途的计算，这些计算处理大量原始数据（例如抓取的文档、Web 请求日志等），以计算各种派生数据（例如倒排索引、Web 文档图形结构的各种表示、每个主机抓取的页面数量摘要、给定一天中最频繁的查询集等）。大多数此类计算在概念上都很简单。但是，输入数据通常很大，并且计算必须分布在数百或数千台机器上才能在合理的时间内完成。如何并行化计算、分发数据和处理故障的问题共同掩盖了原始的简单计算，并使用大量复杂的代码来处理这些问题。 为了应对这种复杂性，我们设计了一种新的抽象，它允许我们表达我们试图执行的简单计算，但隐藏了库中的并行化、容错、数据分布和负载平衡的复杂细节。我们的抽象受到 Lisp 和许多其他函数式语言中存在的 map 和 Reduce 原语的启发。我们意识到，我们的大多数计算都涉及将 map 操作应用于输入中的每个逻辑“记录”，以计算一组中间键/值对，然后对共享相同键的所有值应用 Reduce 操作，以便适当地组合派生数据。我们使用具有用户指定的 map 和 Reduce 操作的函数模型，使我们能够轻松地并行化大型计算，并使用重新执行作为容错的主要机制。 这项工作的主要贡献在于提供了一个简单而功能强大的接口，可实现大规模计算的自动并行化和分布式处理，同时还实现了该接口在大型商用 PC 集群上的高性能。 第 2 节描述了基本编程模型并给出了几个示例。第 3 节描述了针对我们基于集群的计算环境定制的 MapReduce 接口实现。第 4 节描述了我们发现有用的编程模型的几个改进。第 5 节对我们的实现进行了各种任务的性能测量。第 6 节探讨了 MapReduce 在 Google 中的使用情况，包括我们使用它作为重写生产索引系统的基础的经验。第 7 节讨论了相关工作和未来工作。...

Sanjay Ghemawat, Howard Gobioff, and Shun-Tak Leung Google∗ 摘要 我们设计并实现了谷歌文件系统，这是一个可扩展的分布式文件系统，适用于大型分布式数据密集型应用。该系统可在廉价的商品硬件上运行，同时提供容错功能，并能为大量客户端提供高聚合性能。 我们的设计目标与之前的分布式文件系统有许多相同之处，但我们对应用工作负载和技术环境（包括当前和预期环境）的观察结果表明，我们的设计明显偏离了之前的一些文件系统假设。这促使我们重新审视传统的选择，探索完全不同的设计要点。 文件系统成功地满足了我们的存储需求。它在谷歌内部被广泛部署，作为生成和处理我们的服务所使用的数据以及需要大型数据集的研发工作的存储平台。迄今为止，最大的集群在一千多台机器上的数千个磁盘上提供了数百 TB 的存储空间，并被数百个客户端并发访问。 在本文中，我们介绍了为支持分布式应用而设计的文件系统接口扩展，讨论了我们设计的许多方面，并报告了微基准测试和实际使用的测量结果。 1. 引言 我们设计并实施了谷歌文件系统（GFS），以满足谷歌快速增长的数据处理需求。GFS 与以前的分布式文件系统有许多相同的目标，如性能、可扩展性、可靠性和可用性。但是，在设计 GFS 时，我们对当前和预期的应用工作负载和技术环境进行了重要观察，这反映出我们明显偏离了之前的一些文件系统设计假设。我们重新审视了传统的选择，并探索了设计空间中完全不同的点。 首先，组件故障是常态而非例外。文件系统由数百甚至数千台存储机组成，这些存储机都是用廉价的商品部件制造的，并被数量相当的客户机访问。这些组件的数量和质量几乎可以保证，在任何特定时间都会有一些组件无法正常工作，而且有些组件无法从当前故障中恢复。我们见过应用程序错误、操作系统错误、人为错误以及磁盘、内存、连接器、网络和电源故障造成的问题。因此，持续监控、错误检测、容错和自动恢复必须成为系统的组成部分。 其次，按照传统的标准，文件是巨大的。多 GB 的文件很常见。每个文件通常包含许多应用对象，如网络文档。当我们经常处理由数十亿个对象组成的多 TB 快速增长的数据集时，即使文件系统可以支持，要管理数十亿个约 KB 大小的文件也很不方便。因此，必须重新审视 I/O 操作和块大小等设计假设和参数。 第三，大多数文件都是通过添加新数据而不是覆盖现有数据来改变的。文件内的随机写入几乎不存在。文件一旦写入，就只能读取，而且通常只能按顺序读取。各种数据都具有这些特征。有些可能是数据分析程序扫描过的大型存储库。有些可能是运行中的应用程序持续生成的数据流。有些可能是档案数据。有些可能是在一台机器上生成并在另一台机器上处理的中间结果，无论是同时处理还是稍后处理。鉴于巨型文件的这种访问模式，追加成为性能优化和原子性保证的重点，而在客户端缓存数据块则失去了吸引力。 第四，共同设计应用程序和文件系统 API 可以提高我们的灵活性，从而使整个系统受益。例如，我们放宽了 GFS 的一致性模型，大大简化了文件系统，而不会给应用程序带来沉重负担。我们还引入了原子追加操作，使多个客户端可以同时追加文件，而无需额外的同步。本文稍后将详细讨论这些内容。 目前，为不同目的部署了多个 GFS 集群。最大的集群有超过 1000 个存储节点，超过 300 TB 的磁盘存储空间，数百个客户端在不同的机器上持续大量访问。 2. 设计概述 2.1 假设 在设计满足我们需求的文件系统时，我们遵循的假设既是挑战也是机遇。我们在前面提到了一些重要的观察结果，现在详细介绍一下我们的假设。 该系统由许多经常发生故障的廉价商品组件构成。系统必须不断进行自我监控，日常检测、容忍和及时恢复组件故障。 系统存储的大文件数量不多。我们预计会有几百万个文件，每个文件的大小通常为 100 MB 或更大。多 GB 文件是常见情况，应得到有效管理。我们必须支持小文件，但无需对其进行优化。 工作负载主要包括两种读取：大型流式读取和小型随机读取。在大数据流读取中，单个操作通常读取数百 KB，更常见的是 1 MB 或更多。来自同一客户端的连续操作通常会读取文件的连续区域。小型随机读取通常在某个任意偏移位置读取几个 KB 的数据。注重性能的应用程序通常会对小规模读取进行批处理和排序，以稳定地读取文件，而不是来回读取。 这些工作负载中还有许多向文件追加数据的大型连续写入操作。典型的操作大小与读取类似。文件一旦写入，就很少再修改。支持在文件任意位置进行小规模写入，但不一定要高效。 系统必须有效地实现多个客户端同时追加到同一文件的定义明确的语义。我们的文件通常用作生产者-消费者队列或多路合并。数以百计的生产者（每台机器运行一个）将同时追加到一个文件。同步开销最小的原子性至关重要。文件可能会在稍后被读取，或者消费者可能会同时读取文件。 高持续带宽比低延迟更重要。我们的大多数目标应用都非常重视高速批量处理数据，而很少有应用对单个读取或写入的响应时间有严格要求。 2.2 接口 GFS 提供了一个熟悉的文件系统接口，尽管它没有实现标准的 API（如 POSIX）。文件在目录中按层次组织，并用路径名标识。我们支持创建、删除、打开、关闭、读取和写入文件的常规操作。...