logo资料库

Dynamo paper中文版.pdf

发布时间：2022-05-29 发布人：admin 分类：说明书 资料大小：0.65M 资料格式：pdf 举报 版权申诉
第1页 / 共16页
第2页 / 共16页
第3页 / 共16页
第4页 / 共16页
第5页 / 共16页
第6页 / 共16页
第7页 / 共16页
第8页 / 共16页
资料共16页，剩余部分请下载后查看
    Amazon's Dynamo 中文 翻译: quest.run 原著： Werner Vogels (翻译本文，旨在讨论 NoSQL 时会有一个共同的 Terminology，对于要实现 NoSQL 方案的同学，建议啃啃原文， 因为很多术语在翻译成中文后语义差异很大，如 quorum, replica/replication, read-repair, anti-entropy, partition/partitioning/networkpartition, hinting-handoff, reconcile/reconciliation, eventual- consistency, always-writeable,…文中用红色标记了相关的译注，包括一些不知道怎么下手的词汇) 在两个星期内，我们会将一个 Dynamo 技术相关的论文呈现给 SOSP，一个享有威望的一年两次的操作系统会议。Dynamo 是 在 Amazon 内部开发的技术用以解决一个增量扩展的，高可用性的键-值(key-value)存储系统的需求。该技术被设计旨在给其 用户能够权衡成本，一致性，耐用性和性能，但同时保持高可用性。 在它被误解之前，让我来强调一下其内部部分技术：Dynamo 不直接作为 Web 服务暴露给外部，但是，Dynamo 和其它类似 的 Amazon 技术是用于支撑我们 Amazon 的一部分 Web 服务，如 S3。 我们之所以提交这一技术给 SOSP，是因为 Dynamo 使用的许多技术都起源于过去几年的操作系统和分布式系统的研究;动态哈 希表(DHTs)，一致性哈希(consistent hashing)，版本(versioning)，矢量时钟(vector clocks)，仲裁(quorum)，基于反熵 的恢复(anti-entropy based recovery)等。据我所知 Dynamo 是最早的综合使用所有这些技术的生产系统，并且通过这样做 也得到了不少教训。本文主要关于这些经验教训。 我们非常幸运，本文能被 SOSP 选中发表，只有极少数真正的生产系统能够进入到会议中，因此这也是对这项工作的质量的认 可：即构建一个真正可增加扩展的存储系统，且其中最重要的属性都可以适当配置。 Dynamo 是我们在 Amazon 做的许多工作的一个代表；我们不断使用最近的研究开发尖端技术，并且在许多情况下，我们自己 做研究。在 Amazon 的大部分工程，无论是基础设施，分布式系统，工作流，前端页面渲染(rendering)，搜索， digital(??)，similarities(??)，供应链，货运或其他任何系统，都同样是非常先进的。 论文的官方参考： Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swami Sivasubramanian, Peter Vosshall and Werner Vogels, “Dynamo: Amazon's Highly Available Key- Value Store”, in the Proceedings of the 21st ACM Symposium on Operating Systems Principles, Stevenson, WA, October 2007. PDF 版本可在这里获得。你还可以阅读完整的在线版本。( ACM 拥有该文件的文本版权，因此适用于下列声明： © ACM, 2007. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in SOSP’07, October 14–17, 2007, Stevenson, Washington, USA, Copyright 2007 ACM 978-1-59593-591-5/07/0010 中文版在 Amazon's Dynamo 中文 ) Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Dynamo：Amazon 的高可用性的键-值存储系统 Pilchin, Swaminathan Sivasubramanian, Peter Vosshall and Werner Vogels Amazon.com 摘要 巨大规模系统的可靠性是我们在 Amazon.com，这个世界上最大的电子商务公司之一，面对最大的挑战之一，即使最轻微的系 统中断都有显着的经济后果并且影响到客户的信赖。Amazon.com 平台，它为全球许多网站服务，是实现在位于世界各地的许 多数据中心中的成千上万的服务器和网络基础设施之上。在这一规模中，各种大大小小的部件故障持续不断发生，管理持久化 状态的方法在面对这些故障时，驱使软件系统的可靠性和可扩展性。 本文介绍 Dynamo 的设计和实现，一个高度可用的 key-value 存储系统，一些 Amazon ”在线 的用户体验。为了达到这个级别的可用性，Dynamo 在某些故障的场景中将牺牲一致性。它大量使用对象版本和应用程 序协助的冲突协调方式以提供一个开发人员可以使用的新颖接口。 的核心服务使用它用以提供一个 永远 “ 分类和主题描述 D.4.2 [Operating Systems]: Storage Management; D.4.5 [Operating Systems]: Reliability; D.4.2 [Operating Systems]: Performance; General Terms Algorithms, Management, Measurement, Performance, Design, Reliability.(算法，管理，计量，性能，设计，可靠 性。) 1 简介 Amazon 运行一个全球性的电子商务服务平台，在繁忙时段使用位于世界各地的许多数据中心的数千台服务器为几千万的客户 服务。Amazon 平台有严格的性能，可靠性和效率方面操作要求，并支持持续增长，因此平台需要高度可扩展性。可靠性是最 重要的要求之一，因为即使最轻微的系统中断都有显著的经济后果和影响客户的信赖。此外，为了支持持续增长，平台需要高 度可扩展性。
    我们组织在运营 Amazon 平台时所获得的教训之一是，一个系统的可靠性和可扩展性依赖于它的应用状态如何管理。Amazon 采用一种高度去中心化(decentralized)，松散耦合，由数百个服务组成的面向服务架构。在这种环境中特别需要一个始终可用 存储技术。例如，即使磁盘故障，网络路线状态摇摆不定，或数据中心被龙卷风摧毁时，客户应该能够查看和添加物品到自己 的购物车。因此，负责管理购物车的服务，它可以随时写入和读取数据，并且数据需要跨越多个数据中心。 在一个由数百万个组件组成的基础设施中进行故障处理是我们的标准运作模式;在任何给定的时间段，总有一些小的但相当数量 的服务器和网络组件故障，因此 Amazon 的软件系统需要将错误处理当作正常情况下来建造，而不影响可用性或性能。 为了满足可靠性和可伸缩性的需要，Amazon 开发了许多存储技术，其中 Amazon 简单存储服务(一个 Amazon 之外也可获得 的服务，即广为人知的 AmazonS3–SimpleStorageService)大概是最为人熟知。本文介绍了 Dynamo 的设计和实现，另一 个为 Amazon 的平台上构建的高度可用和可扩展的分布式数据存储系统。Dynamo 被用来管理服务状态并且要求非常高的可靠 性，而且需要严格控制可用性，一致性，成本效益和性能的之间的权衡。Amazon 平台的不同应用对存储要求非常差异非常高。 一部分应用需要存储技术具有足够的灵活性，让应用程序设计人员配置适当的数据存储来达到一种平衡，以实现高可用性和最 具成本效益的方式保证性能。 Amazon 服务平台中的许多服务只需要主键访问数据存储。对于许多服务，如提供最畅销书排行榜，购物车，客户的偏好，会 话管理，销售等级，产品目录，常见的使用关系数据库的模式会导致效率低下，有限的可扩展性和可用性。Dynamo 提供了一 个简单的主键唯一的接口，以满足这些应用的要求。 Dynamo 综合了一些著名的技术来实现可伸缩性和可用性：数据划分(data partitioned)和使用一致性哈希的复制 (replicated)[10]，并通过对象版本(object versioning)提供一致性[12]。在更新时，副本之间的一致性是由仲裁般 (quorum-like)的技术和去中心化的副本同步协议来维持的。Dynamo 采用了基于 gossip(不知道怎样译过来好，流言蜚语?或 许保留成外来语为好)的分布式故障检测及成员(membership)协议(也即 token 环上的节点在响应节点加入(join)/离开 (leaving)/移除(removing)/消亡(dead)等所采取的动作以维持 DHT/Partitioning 的正确语义)。Dynamo 是一个只需要很少 的人工管理，去中心化的系统。存储节点可以添加和删除，而不需要任何手动划分(partitioning - partitioner controls how the data are distributed over the nodes)或重新分配(redistribution)。 在过去的一年，Dynamo 已经成为 Amazon 电子商务平台的核心服务的底层存储技术。它能够有效地扩展到极端高峰负载，在 繁忙的假日购物季节没有任何的停机时间。例如，维护购物车(购物车服务)的服务，在一天内承担数千万的请求，并因此导致超 过 300 万 checkouts(结算？)，以及管理十万计的并发活动会话的状态。 这项工作对研究社区的主要贡献是评估不同的技术如何能够结合在一起，并最终提供一个单一的高可用性的系统。它表明一个 最终一致(eventually-consistent)的存储系统可以在生产环境中被苛刻的应用程序所采用。它也对这些技术的调整的进行深入 的分析，以满足性能要求非常严格的生产系统的需求。 本文的结构如下：第 2 节背景知识，第 3 节阐述有关工作，第 4 节介绍了系统设计，第 5 描述了实现，第 6 条详述经验和在生 产运营 Dynamo 时取得的经理，第 7 节结束本文。在这其中，有些地方也许可以适当有更多的信息，但出于适当保护 Amazon 的商业利益，要求我们在文中降低详细程度。由于这个原因，第 6 节数据中心内和跨数据中心之间的延时，第 6.2 节 的相对请求速率，以及第 6.3 节系统中断(outage)的时长，系统负载，都只是总体测量而不是绝对的详细。 2 背景 Amazon 电子商务平台由数百个服务组成，它们协同工作，提供的功能包括建议，完成订单到欺诈检测。每个服务是通过一个 明确的公开接口，通过网络访问。这些服务运行在位于世界各地的许多数据中心的数万台服务器组成的基础设施之上。其中一 些服务是无状态(比如，一些服务只是收集(aggregate)其他服务的 response)，有些是有状态的(比如，通过使用持久性存储 区中的状态，，执行业务逻辑，进而生成 response)。 传统的生产系统将状态存储在关系数据库中。对于许多更通用的状态存储模式，关系数据库方案是远不够理想。因为这些服务 大多只通过数据的主键存储和检索数据，并且不需要 RDBMS 提供的复杂的查询和管理功能。这多余的功能，其运作需要昂贵 的硬件和高技能人才，使其成为一个非常低效的解决方案。此外，现有的复制(replication)技术是有限的，通常选择一致性是 以牺牲可用性为代价(typically choose consistency over availability)。虽然最近几年已经提出了许多进展，但数据库水平 扩展(scaleout)或使用负载平衡智能划分方案仍然不那么容易。 本文介绍了 Dynamo，一个高度可用的数据存储技术，能够满足这些重要类型的服务的需求。Dynamo 有一个简单的键/值接 口，它是高可用的并同时具有清晰定义的一致性滑动窗口，它在资源利用方面是高效的，并且在解决规模增长或请求率上升时 具有一个简单的水平扩展(scaleout)方案。每个使用 Dynamo 的服务运行它自己的 Dynamo 实例。 2.1 系统假设和要求 这种类型的服务的存储系统具有以下要求： 查询模型：对数据项简单的读，写是通过一个主键唯一性标识。状态存储为一个由唯一性键确定二进制对象(即 blob，呵呵， java 就是 ByteBuffer 啦)。没有横跨多个数据项的操作，也不需要关系方案(relational schema)。这项规定是基于观察，相 当一部分 Amazon 的服务可以使用这个简单的查询模型，并不需要任何关系模式。Dynamo 的目标应用程序需要存储的对象都 比较小(通常小于 1MB)。 ：系统需运作在 日用品 (commodity，非常喜欢这个词，因为可以在家做试验！)级的硬件基础设施上。Amazon 平台的 ACID 属性：ACID(原子性，一致性，隔离性，持久性)是一种保证数据库事务可靠地处理的属性。在数据库方面的，对数据的 单一的逻辑操作被称作所谓的交易。Amazon 的经验表明，在保证 ACID 的数据存储提往往有很差的可用性。这已被业界和学 术界所公认[5]。Dynamo 的目标应用程序是高可用性，弱一致性(ACID “中的 C”)。Dynamo 不提供任何数据隔离(Isolation) 保证，只允许单一的关键更新。 效率 服务都有着严格的延时要求，一般延时所需要度量到分布的 99.9 百分位。在服务操作中鉴于对状态的访问起着至关重要的作用， 存储系统必须能够满足那些严格的 SLA(见以下 2.2)，服务必须能够通过配置 Dynamo，使他们不断达到延时和吞吐量的要求。 因此，必须在成本效率，可用性和耐用性保证之间做权衡。 其他假设：Dynamo 仅被 Amazon 内部的服务使用。它的操作环境被假定为不怀恶意的(non-hostile)，没有任何安全相关的 身份验证和授权的要求。此外，由于每个服务使用其特定的 Dynamo 实例，它的最初设计目标的规模高达上百的存储主机。我 们将在后面的章节讨论 Dynamo 可扩展性的限制和相关可能的扩展性的延伸。 “ ”
    2.2 服务水平协议(SLA) 为了保证应用程序可以在限定的(bounded)时间内递送(deliver)其功能，一个平台内的任何一个依赖都在一个更加限定的时间 内递送其功能。客户端和服务端采用服务水平协议(SLA)，其为客户端和服务端在几个系统相关的特征上达成一致的一个正式协 商合约，其中，最突出的包括客户对特定的 API 的请求速率分布的预期要求，以及根据这些条件，服务的预期延时。一个简单 的例子是一个服务的 SLA 保证：在客户端每秒 500 个请求负载高峰时，99.9%的响应时间为 300 毫秒。 在 Amazon 的去中心化的面向服务的基础设施中，服务水平协议发挥了重要作用。例如，一个页面请求某个电子商务网站，通 常需要页面渲染(rendering)引擎通过发送请求到 150 多个服务来构造其响应。这些服务通常有多个依赖关系，这往往是其他 服务，因此，有一层以上调用路径的应用程序通常并不少见。为了确保该网页渲染引擎在递送页面时可以保持明确的时限，调 用链内的每个服务必须履行合约中的性能指标。 图 1 显示了 Amazon 平台的抽象架构，动态网页的内容是由页面呈现组件生成，该组件进而查询许多其他服务。一个服务可以 使用不同的数据存储来管理其状态，这些数据存储仅在其服务范围才能访问。有些服务作为聚合器使用其他一些服务，可产生 合成(composite)响应。通常情况下，聚合服务是无状态，虽然他们利用广泛的缓存。 图 1：面向服务的 Amazon 平台架构。 行业中，表示面向性能的 SLA 的共同做法是使用平均数(average)，中值(median)和预期变化(expected variance)。在 Amazon，我们发现，这些指标不够好，如果目标是建立一个对所有，而不是大多数客户都有着良好体验的系统。例如，如果 个性化(personalization)技术被广泛使用，那么有很长的历史的客户需要更多的处理，性能影响将表现在分布的高端。前面所 述的基于平均或中值响应时间的 SLA 不能解决这一重要客户段的性能问题。为了解决这个问题，在 Amazon，SLA 是基于分布 的 99.9 百分位来表达和测量的。选择百分位 99.9 的而不是更高是根据成本效益分析，其显示出在 99.9 之后，要继续提高性 能，成本将大幅增加。系统的经验与 Amazon 的生产表明，相比于那些基于平均或中值定义的 SLA 的系统，该方法提供了更好 的整体体验。 本文多次提到这种 99.9 百分位分布，这反映了 Amazon 工程师从客户体验角度对性能不懈追求。许多论文统计平均数，所以 在本论文的一些地方包括它可以用来作比较。然而，Amazon 的工程和优化没有侧重于平均数。几种技术，如作为写协调器 (coordinators)的负载均衡的选择，纯粹是针对控制性能在 99.9 百分位的。 存储系统在建立一个服务的 SLA 中通常扮演重要角色，特别是如果业务逻辑是比较轻量级时，正如许多 Amazon 的服务的情况。 状态管理就成为一个服务的 SLA 的主要组成部分。对 dynamo 的主要设计考虑的问题之一就是给各个服务控制权，通过系统属 性来控制其耐用性和一致性，并让服务自己在功能，性能和成本效益之间进行权衡。 2.3 设计考虑 在商业系统中，数据复制(Data replication)算法传统上执行同步的副本(replica)协调，以提供一个强一致性的数据访问接口。 为了达到这个水平的一致性，在某些故障情况下，这些算法被迫牺牲了数据可用性。例如，与其不能确定答案的正确性与否， 不如让该数据一直不可用直到它绝对正确时。从最早期的备份(replicated)数据库，众所周知，当网络故障时，强一致性和高可 用性不可能性同时实现[2，11]。因此，系统和应用程序需要知道在何种情况下可以达到哪些属性。 对于容易出现的服务器和网络故障的系统，可使用乐观复制技术来提高系统的可用性，其变化可以在后台传播到副本，同时， 并发和断开(disconnected)是可以容忍的。这种方法的挑战在于，它会导致更改冲突，而这些冲突必须检测并协调解决。这种
    “ ” “ ” “ ” 协调冲突的过程引入了两个问题：何时协调它们，谁协调它们。Dynamo 被设计成最终一致性(eventually consistent)的数 据存储，即所有的更新操作，最终达到所有副本。 一个重要的设计考虑的因素是决定何时去协调更新操作冲突，即是否应该在读或写过程中协调冲突。许多传统数据存储在写的 过程中执行协调冲突过程，从而保持读的复杂度相对简单[7]。在这种系统中，如果在给定的时间内数据存储不能达到所要求的 所有或大多数副本数，写入可能会被拒绝。另一方面，Dynamo 的目标是一个 永远可写 (always writable)的数据存储(即数 据存储的 写 是高可用)。对于 Amazon 许多服务来讲，拒绝客户的更新操作可能导致糟糕的客户体验。例如，即使服务器或网 络故障，购物车服务必须让客户仍然可向他们的购物车中添加和删除项。这项规定迫使我们将协调冲突的复杂性推给 读 ，以 确保 写 永远不会拒绝。 下一设计选择是谁执行协调冲突的过程。这可以通过数据存储或客户应用程序。如果冲突的协调是通过数据存储，它的选择是 相当有限的。在这种情况下，数据存储只可能使用简单的策略，如 最后一次写入获胜 (last write wins)[22]，以协调冲突的 更新操作。另一方面，客户应用程序，因为应用知道数据方案，因此它可以基于最适合的客户体验来决定协调冲突的方法。例 如，维护客户的购物车的应用程序，可以选择 合并 冲突的版本，并返回一个统一的购物车。尽管具有这种灵活性，某些应用 ” 程序开发人员可能不希望写自己的协调冲突的机制，并选择下压到数据存储，从而选择简单的策略，例如 最后一次写入获胜 。 设计中包含的其他重要的设计原则是： 增量的可扩展性：Dynamo 应能够一次水平扩展一台存储主机( 小。 对称性：每个 Dynamo 节点应该与它的对等节点(peers)有一样的责任;不应该存在有区别的节点或采取特殊的角色或额外的责 任的节。根据我们的经验，对称性(symmetry)简化了系统的配置和维护。 去中心化：是对对称性的延伸，设计应采用有利于去中心化而不是集中控制的技术。在过去，集中控制的设计造成系统中断 (outages)，而本目标是尽可能避免它。这最终造就一个更简单，更具扩展性，更可用的系统。 异质性：系统必须能够利用异质性的基础设施运行。例如，负载的分配必须与各个独立的服务器的能力成比例。这样就可以一 次只增加一个高处理能力的节点，而无需一次升级所有的主机。 “节点 )，而对系统操作者和系统本身的影响很 “ 以下，简称为 “ ” “ ” ” “ “ 3 相关工作 3.1 点对点系统 已经有几个点对点(P2P)系统研究过数据存储和分配的问题。如第一代 P2P 系统 Freenet 和 Gnutella，被主要用作文件共享系 统。这些都是由链路任意建立的非结构化 P2P 的网络的例子。在这些网络中，通常是充斥着通过网络的搜索查询以找到尽可能 多地共享数据的对等节点。P2P 系统演进到下一代是广泛被称为结构化 P2P。这些网络采用了全局一致的协议，以确保任何节 点都可以有效率地传送一个搜索查询到那些需要数据的节点。系统，如 Pastry[16]和 Chord[20]使用路由机制，以确保查询可 以在有限的跳数(hops)内得到回答。为了减少多跳路由引入的额外延时，有些 P2P 系统(例如，[14])采用 O(1)路由，每个节点 保持足够的路由信息，以便它可以在常数跳数下从本地路由请求(到要访问的数据项)到适当的节点。 其他的存储系统，如 Oceanstore[9]和 PAST[17]是建立在这些交错的路由基础之上的。Oceanstore 提供了一个全局性的， 事务性，持久性存储服务，支持对广阔的(widely)复制的数据进行序列化更新。为允许并发更新的同时避免与广域锁定(wide- area locking)固有的许多问题，它使用了一个协调冲突的更新模型。[21]介绍了在协调冲突，以减少交易中止数量。 Oceanstore 协调冲突的方式是：通过处理一系列的更新，为他们选择一个最终的顺序，然后利用这个顺序原子地进行更新。 它是为数据被复制到不受信任的环境的基础设施之上而建立。相比之下，PAST 提供了一个基于 Pastry 和不可改变的对象的简 单的抽象层。它假定应用程序可以在它之上建立必要的存储的语义(如可变文件)。 3.2 分布式文件系统和数据库 出于对性能，可用性和耐用性考虑，数据分发已被文件系统和数据库系统的社区广泛研究。对比于 P2P 存储系统的只支持平展 的命名空间，分布式文件系统通常支持分层的命名空间。系统象 Ficus[15]和 Coda[19]其文件复制是以牺牲一致性为代价而达 到高可用性。更新冲突管理通常使用专门的协调冲突程序。Farsite 系统[1]是一个分布式文件系统，不使用任何类似 NFS 的中 心服务器。Farsite 使用复制来实现高可用性和可扩展性。谷歌文件系统[6]是另一个分布式文件系统用来承载谷歌的内部应用 程序的状态。GFS 使用简单的设计并采用单一的中心(master)服务器管理整个元数据，并且将数据被分成块存储在 chunkservers 上。Bayou 是一个分布式关系数据库系统允许断开(disconnected)操作，并提供最终的数据一致性[21]。 在这些系统中，Bayou,Coda 和 Ficus 允许断开操作和有从如网络分裂和中断的问题中复原的弹性。这些系统的不同之处在于 协调冲突程序。例如，Coda 和 Ficus 执行系统级协调冲突方案，Bayou 允许应用程序级的解决方案。不过，所有这些都保证 最终一致性。类似这些系统，Dynamo 允许甚至在网络被分裂(partition - network partition, which is a break in the network that prevents one machine in one data center from interacting directly with another machine in other data center)的情况下继续进行读，写操作，以及使用不同的机制来协调有冲突的更新操作。分布式块存储系统，像 FAB[18] 将大对象分成较小的块，并以高度可用的方式存储。相对于这些系统中，一个 key-value 存储在这种情况下更合适，因为：(a) 它就是为了存放相对小的物体(大小<1M) 和 (b)key-value 存储是以每个应用更容易配置为基础的。Antiquity 是一个广域分布 式存储系统，专为处理多种服务器故障[23]。它使用一个安全的日志来保持数据的完整性，复制日志到多个服务器以达到耐久 性，并使用 Byzantine 容错协议来保证数据的一致性。相对于 antiquity，Dynamo 不太注重数据完整性和安全问题，并为一 个可信赖的环境而建立的。BigTable 是一个管理结构化数据的分布式存储系统。它保留着稀疏的,多维的有序映射，并允许应用 程序使用多个属性访问他们的数据[2]。相对于 Bigtable 中，Dynamo 的目标应用程序只需要 key/value 并主要关注高可用性， 甚至在网络分裂或服务器故障时，更新操作都不会被拒绝。 传统备份(replicated)关系数据库系统强调保证复制数据的一致性。虽然强一致性给应用编写者提供了一个更方便的应用程序编 程模型，但这些系统都只有有限的可伸缩性和可用性[7]。这些系统不能处理网络分裂(partition)，因为它们通常提供强的一致 性保证。 3.3 讨论 与上述去中心化的存储系统相比，Dynamo 有着不同的目标需求：首先，Dynamo 主要是针对应用程序需要一个 永远可写 数 据存储，不会由于故障或并发写入而导致更新操作被拒绝。这是许多 Amazon 应用的关键要求。其次，如前所述，Dynamo 是 建立在一个所有节点被认为是值得信赖的单个管理域的基础设施之上。第三，使用 Dynamo 的应用程序不需要支持分层命名空 间(许多文件系统采用的规范)或复杂的(由传统的数据库支持)关系模式的支持。第四，Dynamo 是为延时敏感应用程序设计的， 需要至少 99.9％的读取和写入操作必须在几百毫秒内完成。为了满足这些严格的延时要求，这促使我们必须避免通过多个节点 路由请求(这是被多个分布式哈希系统如 Chord 和 Pastry 采用典型的设计)。这是因为多跳路由将增加响应时间的可变性，从而 导致百分较高的延时的增加。Dynamo 可以被定性为零跳(zero-hop)的 DHT，每个节点维护足够的路由信息从而直接从本地 “ ”
    将请求路由到相应的节点。 4 系统架构 一个操作在生产环境里的存储系统的架构是复杂的。除了实际的数据持久化组件，系统需要有负载平衡，成员(membership) 和故障检测，故障恢复，副本同步，过载处理，状态转移，并发性和工作调度，请求 marshaling，请求路由，系统监控和报警， 以及配置管理等可扩展的且强大的解决方案。描述解决方案的每一个细节是不可能的，因此本文的重点是核心技术在分布式系 统中使用 Dynamo：划分(partitioning)，复制(replication)，版本(versioning)，会员(membership)，故障处理(failure handling)和伸缩性(scaling)。表 1 给出了简要的 Dynamo 使用的技术清单和各自的优势。 表 1：Dynamo 使用的技术概要和其优势。 问题 划分 技术 优势 一致性哈希 增量可伸缩性 写的高可用性 矢量时钟与读取过程中的协 调(reconciliation) 版本大小与更新操作速率脱钩。 暂时性的失败处理 草率仲裁(Sloppy Quorum？)，并暗示移交 (hinted handoff) 提供高可用性和耐用性的保证，即使一些副本不可用时。 永久故障恢复 使用 Merkle 树的反熵(Anti- entropy) 在后台同步不同的副本。 会员和故障检测 Gossip 的成员和故障检测协 议。 保持对称性并且避免了一个用于存储会员和节点活性信息的集中注册 服务节点。 4.1 系统接口 Dynamo 通过一个简单的接口将对象与 key 关联，它暴露了两个操作：get()和 put()。get(key)操作在存储系统中定位与 key 关联的对象副本，并返回一个对象或一个包含冲突的版本和对应的上下文对象列表。put(key,context,object)操作基于关联的 key 决定将对象的副本放在哪，并将副本写入到磁盘。该 context 包含对象的系统元数据并对于调用者是不透明的(opaque)， 并且包括如对象的版本信息。上下文信息是与对象一起存储，以便系统可以验证请求中提供的上下文的有效性。 Dynamo 将调用者提供的 key 和对象当成一个不透明的字节数组。它使用 MD5 对 key 进行 Hash 以产生一个 128 位的标识符， 它是用来确定负责(responsible for)那个 key 的存储节点。 4.2 划分算法 ” “ ” “ Dynamo 的关键设计要求之一是必须增量可扩展性。这就需要一个机制来将数据动态划分到系统中的节点(即存储主机)上去。 Dynamo 的分区方案依赖于一致哈希将负载分发到多个存储主机。在一致的哈希中[10]，一个哈希函数的输出范围被视为一个 固定的圆形空间或 环 (即最大的哈希值绕到(wrap)最小的哈希值)。系统中的每个节点被分配了这个空间中的一个随机值，它 代表着它的在环上的 位置 。每个由 key 标识的数据项通过计算数据项的 key 的 hash 值来产生其在环上的位置。然后沿顺时 针方向找到第一个其位置比计算的数据项的位置大的节点。因此，每个节点变成了环上的一个负责它自己与它的前身节点间的 区域(region)。一致性哈希的主要优点是节点的进进出出(departure or arrival)只影响其最直接的邻居，而对其他节点没影响。 这对基本的一致性哈希算法提出了一些挑战。首先，每个环上的任意位置的节点分配导致非均匀的数据和负荷分布。二，基本 算法无视于节点的性能的异质性。为了解决这些问题，Dynamo 采用了一致的哈希(类似于[10，20]中使用的)的变体：每个节 点被分配到环多点而不是映射到环上的一个单点。为此，Dynamo 使用了 虚拟节点 的概念。系统中一个虚拟节点看起来像单 个节点，但每个节点可对多个虚拟节点负责。实际上，当一个新的节点添加到系统中，它被分配环上的多个位置( 以下简称 标 ” 记 Token )。对 Dynamo 的划分方案进一步细化在第 6 部分讨论。 使用虚拟节点具有以下优点： • 如果一个节点不可用(由于故障或日常维护)，这个节点处理的负载将均匀地分散在剩余的可用节点。 • 当一个节点再次可用，或一个新的节点添加到系统中，新的可用节点接受来自其他可用的每个节点的负载量大致相当。 • 一个节点负责的虚拟节点的数目可以根据其处理能力来决定，顾及到物理基础设施的异质性。 “ “ ” 4.3 复制 为了实现高可用性和耐用性，Dynamo 将数据复制到多台主机上。每个数据项被复制到 N 台主机，其中 N “是 每实例 (“per- instance)的配置参数。每个键，K，被分配到一个协调器(coordinator)节点(在上一节所述)。协调器节点掌控其负责范围内的 复制数据项。除了在本地存储其范围内的每个 key 外，协调器节点复制这些 key 到环上顺时针方向的 N-1 后继节点。 这样的结果是，系统中每个节点负责环上的从其自己到第 N 个前继节点间的一段区域。在图 2 中，节点 B 除了在本地存 储键 K 外，在节点 C 和 D 处复制键 K。节点 D 将存储落在范围(A,B],(B,C]和(C,D]上的所有键。 ”
    图 2：Dynamo 的划分和键的复制。 一个负责存储一个特定的键的节点列表被称为首选列表(preference list)。该系统的设计，如将 4.8 节中解释，让系统中每一 个节点可以决定对于任意 key 哪些节点应该在这个清单中。出于对节点故障的考虑，首选清单可以包含起过 N 个节点。请注意， 因使用虚拟节点，对于一个特定的 key 的第一个 N 个后继位置可能属于少于 N 个物理所节点(即节点可以持有多个第一个 N 个 位置)。为了解决这个问题，一个 key 首选列表的构建将跳过环上的一些位置，以确保该列表只包含不同的物理节点。 4.4 版本化的数据 “ Dynamo 提供最终一致性，从而允许更新操作可以异步地传播到所有副本。put()调用可能在更新操作被所有的副本执行之前就 返回给调用者，这可能会导致一个场景：在随后的 get()操作可能会返回一个不是最新的对象。如果没有失败，那么更新操作的 传播时间将有一个上限。但是，在某些故障情况下(如服务器故障或网络 partitions)，更新操作可能在一个较长时间内无法到达 所有的副本。 在 Amazon 的平台，有一种类型的应用可以容忍这种不一致，并且可以建造并操作在这种条件下。例如，购物车应用程序要求 “一个 添加到购物车 动作从来没有被忘记或拒绝。如果购物车的最近的状态是不可用，并且用户对一个较旧版本的购物车做了 更改，这种变化仍然是有意义的并且应该保留。但同时它不应取代当前不可用的状态，而这不可用的状态本身可能含有的变化 也需要保留。请注意在 Dynamo “中 添加到购物车“ ”和 从购物车删除项目“这两个操作被转成 put 请求。当客户希望增加一个项 目到购物车(或从购物车删除)但最新的版本不可用时，该项目将被添加到旧版本(或从旧版本中删除)并且不同版本将在后来协调 (reconciled)。 为了提供这种保证，Dynamo 将每次数据修改的结果当作一个新的且不可改变的数据版本。它允许系统中同一时间出现多个版 本的对象。大多数情况，新版本包括（subsume）老的版本，且系统自己可以决定权威版本( reconciliation)。然而，版本分支可能发生在并发的更新操作与失败的同时出现的情况，由此产生冲突版本的对象。在这种情 况下，系统无法协调同一对象的多个版本，那么客户端必须执行协调，将多个分支演化后的数据崩塌(collapse)成一个合并的 版本(语义协调) 远不会丢失。但是， 重要的是要了解某些故障模式有可能导致系统中相同的数据不止两个，而是好几个版本。在网络分裂和节点故障的情况下，可 能会导致一个对象有不同的分历史，系统将需要在未来协调对象。这就要求我们在设计应用程序，明确意识到相同数据的多个 版本的可能性(以便从来不会失去任何更新操作)。 Dynamo 使用矢量时钟[12]来捕捉同一不同版本的对象的因果关系。矢量时钟实际上是一个(node,counter)对列表(即(节点， 计数器)列表)。矢量时钟是与每个对象的每个版本相关联。通过审查其向量时钟，我们可以判断一个对象的两个版本是平 行分枝或有因果顺序。如果第一个时钟对象上的计数器在第二个时钟对象上小于或等于其他所有节点的计数器，那么第一个是 第二个的祖先，可以被人忽略。否则，这两个变化被认为是冲突，并要求协调。 在 dynamo 中，当客户端更新一个对象，它必须指定它正要更新哪个版本。这是通过传递它从早期的读操作中获得的上下文对 象来指定的，它包含了向量时钟信息。当处理一个读请求，如果 Dynamo 访问到多个不能语法协调(syntactically reconciled)的分支，它将返回分支叶子处的所有对象，其包含与上下文相应的版本信息。使用这种上下文的更新操作被认为已 经协调了更新操作的不同版本并且分支都被倒塌到一个新的版本。 。一个典型的崩塌的例子是 合并 客户的不同版本的购物车。使用这种协调机制，一个 添加到购物车 操作是永 语法协调 syntactic 已删除的条目可能会 重新浮出水面 (resurface)。 ” “ ” “ ” ”
    图 3：对象的版本随时间演变。 为了说明使用矢量时钟，让我们考虑图 3 所示的例子。 1)客户端写入一个新的对象。节点(比如说 Sx)，它处理对这个 key 的写：序列号递增，并用它来创建数据的向量时钟。该系统 现在有对象 D1 和其相关的时钟[(Sx，1)]。 2)客户端更新该对象。假定也由同样的节点处理这个要求。现在该系统有对象 D2 和其相关的时钟[(Sx，2)]。D2 继承自 D1， 因此覆写 D1，但是节点中或许存在还没有看到 D2 的 D1 的副本。 3)让我们假设，同样的客户端更新这个对象但不同的服务器(比如 Sy)处理了该请求。目前该系统具有数据 D3 及其相关的时钟 [(Sx，2)，(Sy，1)]。 4)接下来假设不同的客户端读取 D2，然后尝试更新它，并且另一个服务器节点(如 Sz)进行写操作。该系统现在具有 D4(D2 的 子孙)，其版本时钟[(Sx，2)，(Sz，1)]。一个对 D1 或 D2 有所了解的节点可以决定，在收到 D4 和它的时钟时，新的数据将覆 盖 D1 和 D2，可以被垃圾收集。一个对 D3 有所了解的节点，在接收 D4 时将会发现，它们之间不存在因果关系。换句话说， D3 和 D4 都有更新操作，但都未在对方的变化中反映出来。这两个版本的数据都必须保持并提交给客户端(在读时)进行语 义协调。 5)现在假定一些客户端同时读取到 D3 和 D4(上下文将反映这两个值是由 read 操作发现的)。读的上下文包含有 D3 和 D4 时钟 的概要信息，即[(Sx，2)，(Sy，1)，(Sz，1)]的时钟总结。如果客户端执行协调，且由节点 Sx 来协调这个写操作，Sx 将更新 其时钟的序列号。D5 的新数据将有以下时钟：[(Sx，3)，(Sy，1)，(Sz，1)]。 关于向量时钟一个可能的问题是，如果许多服务器协调对一个对象的写，向量时钟的大小可能会增长。实际上，这是不太可能 的，因为写入通常是由首选列表中的前 N 个节点中的一个节点处理。在网络分裂或多个服务器故障时，写请求可能会被不是首 选列表中的前 N 个节点中的一个处理的，因此会导致矢量时钟的大小增长。在这种情况下，值得限制向量时钟的大小。为此， Dynamo 采用了以下时钟截断方案：伴随着每个(节点，计数器)对，Dynamo 存储一个时间戳表示最后一次更新的时间。当向 量时钟中(节点，计数器)对的数目达到一个阈值(如 10)，最早的一对将从时钟中删除。显然，这个截断方案会导至在协调时效 率低下，因为后代关系不能准确得到。不过，这个问题还没有出现在生产环境，因此这个问题没有得到彻底研究。 4.5 执行 get()和 put()操作 Dynamo 中的任何存储节点都有资格接收客户端的任何对 key 的 get 和 put 操作。在本节中，对简单起见，我们将描述如何在 一个从不失败的(failure-free)环境中执行这些操作，并在随后的章节中，我们描述了在故障的情况下读取和写入操作是如何执 行。 GET 和 PUT 操作都使用基于 Amazon 基础设施的特定要求，通过 HTTP 的处理框架来调用。一个客户端可以用有两种策略之 一来选择一个节点：(1)通过一个普通的负载平衡器路由请求，它将根据负载信息选择一个节点，或(2)使用一个分区(partition) 敏感的客户端库直接路由请求到适当的协调程序节点。第一个方法的优点是，客户端没有链接(link)任何 Dynamo 特定的代码 在到其应用中，而第二个策略，Dynamo 可以实现较低的延时，因为它跳过一个潜在的转发步骤。 处理读或写操作的节点被称为协调员。通常，这是首选列表中跻身前 N 个节点中的第一个。如果请求是通过负载平衡器收到， 访问 key 的请求可能被路由到环上任何随机节点。在这种情况下，如果接收到请求节点不是请求的 key 的首选列表中前 N 个节 点之一，它不会协调处理请求。相反，该节点将请求转发到首选列表中第一个跻身前 N 个节点。 读取和写入操作涉及到首选清单中的前 N 个健康节点，跳过那些瘫痪的(down)或者不可达(inaccessible)的节点。当所有节点 都健康，key 的首选清单中的前 N 个节点都将被访问。当有节点故障或网络分裂，首选列表中排名较低的节点将被访问。 为了保持副本的一致性，Dynamo 使用的一致性协议类似于仲裁(quorum)。该协议有两个关键配置值：R 和 W. R 是必须参 与一个成功的读取操作的最少数节点数目。W 是必须参加一个成功的写操作的最少节点数。设定 R 和 W，使得 R+W>N 产生类似仲裁的系统。在此模型中，一个 get(or out)操作延时是由最慢的 R(或 W)副本决定的。基于这个原因，R 和 W 通常配置为小于Ｎ，为客户提供更好的延时。 当收到对 key 的 put()请求时，协调员生成新版本向量时钟并在本地写入新版本。协调员然后将新版本(与新的向量时钟一起)发 送给首选列表中的排名前Ｎ个的可达节点。如果至少Ｗ-1 个节点返回了响应，那么这个写操作被认为是成功的。
    同样，对于一个 get()请求，协调员为 key 从首选列表中排名前Ｎ个可达节点处请求所有现有版本的数据，然后等待Ｒ个响应， 然后返回结果给客户端。如果最终协调员收集的数据的多个版本，它返回所有它认为没有因果关系的版本。不同版本将被协调， 并且取代当前的版本，最后写回。 4.6 故障处理：暗示移交(Hinted Handoff) ” “ Dynamo 如果使用传统的仲裁(quorum)方式,在服务器故障和网络分裂的情况下它将是不可用，即使在最简单的失效条件下也 将降低耐久性。为了弥补这一点，它不严格执行仲裁，即使用了 马虎仲裁 (“sloppy quorum”)，所有的读，写操作是由首选 列表上的前 N 个健康的节点执行的，它们可能不总是在散列环上遇到的那前Ｎ个节点。 考虑在图 2 例子中 Dynamo 的配置，给定 N=3。在这个例子中，如果写操作过程中节点 A 暂时 Down 或无法连接，然后通常 本来在 A 上的一个副本现在将发送到节点 D。这样做是为了保持期待的可用性和耐用性。发送到 D 的副本在其原数据中将有一 个暗示，表明哪个节点才是在副本预期的接收者(在这种情况下Ａ)。接收暗示副本的节点将数据保存在一个单独的本地存储 中，他们被定期扫描。在检测到了 A 已经复苏，D 会尝试发送副本到 A。一旦传送成功，D 可将数据从本地存储中删除而不会 降低系统中的副本总数。 使用暗示移交，Dynamo 确保读取和写入操作不会因为节点临时或网络故障而失败。需要最高级别的可用性的应用程序可以设 置 W 为 1，这确保了只要系统中有一个节点将 key 已经持久化到本地存储 ,　一个写是可以接受(即一个写操作完成即意味着 成功)。因此，只有系统中的所有节点都无法使用时写操作才会被拒绝。然而，在实践中，大多数 Amazon 生产服务设置了更 高的 W 来满足耐久性极别的要求。对 N, R 和 W 的更详细的配置讨论在后续的第 6 节。 一个高度可用的存储系统具备处理整个数据中心故障的能力是非常重要的。数据中心由于断电，冷却装置故障，网络故障和自 然灾害发生故障。Dynamo 可以配置成跨多个数据中心地对每个对象进行复制。从本质上讲，一个 key 的首选列表的构造是基 于跨多个数据中心的节点的。这些数据中心通过高速网络连接。这种跨多个数据中心的复制方案使我们能够处理整个数据中心 故障。 4.7 处理永久性故障：副本同步 Hinted Handoff 在系统成员流动性(churn)低，节点短暂的失效的情况下工作良好。有些情况下，在 hinted 副本移交回原来 的副本节点之前，暗示副本是不可用的。为了处理这样的以及其他威胁的耐久性问题，Dynamo 实现了反熵(anti-entropy， 或叫副本同步)协议来保持副本同步。 为了更快地检测副本之间的不一致性，并且减少传输的数据量，Dynamo 采用 MerkleTree[13]。MerkleTree 是一个哈希树 (Hash Tree)，其叶子是各个 key 的哈希值。树中较高的父节点均为其各自孩子节点的哈希。该 merkleTree 的主要优点是树 的每个分支可以独立地检查，而不需要下载整个树或整个数据集。此外，MerkleTree 有助于减少为检查副本间不一致而传输的 数据的大小。例如，如果两树的根哈希值相等，且树的叶节点值也相等，那么节点不需要同步。如果不相等，它意味着，一些 副本的值是不同的。在这种情况下，节点可以交换 children 的哈希值，处理直到它到达了树的叶子，此时主机可以识别出 不 ”同步 的 key。MerkleTree 减少为同步而需要转移的数据量，减少在反熵过程中磁盘执行读取的次数。 Dynamo 在反熵中这样使用 MerkleTree：每个节点为它承载的每个 key 范围( 由一个虚拟节点覆盖 key 集合)维护一个单独的 MerkleTree。这使得节点可以比较 key range 中的 key 是否是最新。在这个方案中，两个节点交换 MerkleTree 的根，对应 于它们承载的共同的键范围。其后，使用上面所述树遍历方法，节点确定他们是否有任何差异和执行适当的同步行动。方案的 缺点是，当节点加入或离开系统时有许多 key rangee 变化，从而需要重新对树进行计算。通过由 6.2 节所述的更精炼 partitioning 方案，这个问题得到解决。 “ 4.8 会员和故障检测 4.8.1 环会员(Ring Membership) Amazon 环境中，节点中断(由于故障和维护任务)常常是暂时的，但持续的时间间隔可能会延长。一个节点故障很少意味着一 个节点永久离开，因此应该不会导致对已分配的分区重新平衡(rebalancing)和修复无法访问的副本。同样，人工错误可能导致 意外启动新的 Dynamo 节点。基于这些原因，应当适当使用一个明确的机制来发起节点的增加和从环中移除节点。管理员使用 命令行工具或浏览器连接到一个节点，并发出成员改变(membership change)指令指示一个节点加入到一个环或从环中删除 一个节点。接收这一请求的节点写入成员变化以及适时写入持久性存储。该成员的变化形成了历史，因为节点可以被删除，重 新添加多次。一个基于 Gossip 的协议传播成员变动，并维持成员的最终一致性。每个节点每间隔一秒随机选择随机的对等节点， 两个节点有效地协调他们持久化的成员变动历史。 当一个节点第一次启动时，它选择它的 Token(在虚拟空间的一致哈希节点) 并将节点映射到各自的 Token 集(Token set)。该 映射被持久到磁盘上，最初只包含本地节点和 Token 集。在不同的节点中存储的映射（节点到 token set 的映射）将在协调成 员的变化历史的通信过程中一同被协调。因此，划分和布局信息也是基于 Gossip 协议传播的，因此每个存储节点都了解对等节 点所处理的标记范围。这使得每个节点可以直接转发一个 key 的读/写操作到正确的数据集节点。 4.8.2 外部发现 上述机制可能会暂时导致逻辑分裂的 Dynamo 环。例如，管理员可以将节点 A 加入到环，然后将节点 B 加入环。在这种情况 下，节点 A 和 B 各自都将认为自己是环的一员，但都不会立即了解到其他的节点(也就是Ａ不知道 B 的存在，B 也不知道 A 的存在，这叫逻辑分裂)。为了防止逻辑分裂，有些 Dynamo 节点扮演种子节点的角色。种子的发现(discovered)是通过外 部机制来实现的并且所有其他节点都知道(实现中可能直接在配置文件中指定 seed node 的 IP，或者实现一个动态配置服 务,seed register)。因为所有的节点，最终都会和种子节点协调成员关系，逻辑分裂是极不可能的。种子可从静态配置或配置 服务获得。通常情况下，种子在 Dynamo 环中是一个全功能节点。 4.8.3 故障检测 Dynamo 中，故障检测是用来避免在进行 get()和 put()操作时尝试联系无法访问节点，同样还用于分区转移(transferring partition)和暗示副本的移交。为了避免在通信失败的尝试，一个纯本地概念的失效检测完全足够了：如果节点 B 不对节点 A 的 信息进行响应(即使 B 响应节点 C 的消息)，节点 A 可能会认为节点 B 失败。在一个客户端请求速率相对稳定并产生节点间通信 的 Dynamo 环中，一个节点 A 可以快速发现另一个节点 B 不响应时，节点 A 则使用映射到 B 的分区的备用节点服务请求，并 定期检查节点 B 后来是否后来被复苏。在没有客户端请求推动两个节点之间流量的情况下，节点双方并不真正需要知道对方是 否可以访问或可以响应。 去中心化的故障检测协议使用一个简单的 Gossip 式的协议，使系统中的每个节点可以了解其他节点到达(或离开)。有关去中心 化的故障探测器和影响其准确性的参数的详细信息，感兴趣的读者可以参考[8]。早期 Dynamo 的设计使用去中心化的故障检 测器以维持一个失败状态的全局性的视图。后来认为，显式的节点加入和离开的方法排除了对一个失败状态的全局性视图的需
    分享到：
    赞 收藏

    相关推荐

    资料库

    开发技术

    共收录19306份资料，累计14个分类，关注成员有19位，主要包括：Actionscript,Javascript,PHP,VB,Perl,Delphi,Python,C#,C,Java,C++,Web开发,硬件开发,其它

    热门标签

    Actionscript Javascript PHP VB Perl Delphi Python C# C Java C++ Web开发 硬件开发 其它

    最新资料