亚马逊高度可用的关键值存储

1 . Dynamo: Amazon’s Highly Available Key-value Store Giuseppe DeCandia, Deniz Hastorun, Madan Jampani, Gunavardhan Kakulapati, Avinash Lakshman, Alex Pilchin, Swaminathan Sivasubramanian, Peter Vosshall and Werner Vogels Amazon.com One of the lessons our organization has learned from operating ABSTRACT Amazon’s platform is that the reliability and scalability of a Reliability at massive scale is one of the biggest challenges we system is dependent on how its application state is managed. face at Amazon.com, one of the largest e-commerce operations in Amazon uses a highly decentralized, loosely coupled, service the world; even the slightest outage has significant financial oriented architecture consisting of hundreds of services. In this consequences and impacts customer trust. The Amazon.com environment there is a particular need for storage technologies platform, which provides services for many web sites worldwide, that are always available. For example, customers should be able is implemented on top of an infrastructure of tens of thousands of to view and add items to their shopping cart even if disks are servers and network components located in many datacenters failing, network routes are flapping, or data centers are being around the world. At this scale, small and large components fail destroyed by tornados. Therefore, the service responsible for continuously and the way persistent state is managed in the face managing shopping carts requires that it can always write to and of these failures drives the reliability and scalability of the read from its data store, and that its data needs to be available software systems. across multiple data centers. This paper presents the design and implementation of Dynamo, a Dealing with failures in an infrastructure comprised of millions of highly available key-value storage system that some of Amazon’s components is our standard mode of operation; there are always a core services use to provide an “always-on” experience. To small but significant number of server and network components achieve this level of availability, Dynamo sacrifices consistency that are failing at any given time. As such Amazon’s software under certain failure scenarios. It makes extensive use of object systems need to be constructed in a manner that treats failure versioning and application-assisted conflict resolution in a manner handling as the normal case without impacting availability or that provides a novel interface for developers to use. performance. Categories and Subject Descriptors To meet the reliability and scaling needs, Amazon has developed D.4.2 [Operating Systems]: Storage Management; D.4.5 a number of storage technologies, of which the Amazon Simple [Operating Systems]: Reliability; D.4.2 [Operating Systems]: Storage Service (also available outside of Amazon and known as Performance; Amazon S3), is probably the best known. This paper presents the design and implementation of Dynamo, another highly available General Terms and scalable distributed data store built for Amazon’s platform. Algorithms, Management, Measurement, Performance, Design, Dynamo is used to manage the state of services that have very Reliability. high reliability requirements and need tight control over the tradeoffs between availability, consistency, cost-effectiveness and 1. INTRODUCTION performance. Amazon’s platform has a very diverse set of Amazon runs a world-wide e-commerce platform that serves tens applications with different storage requirements. A select set of of millions customers at peak times using tens of thousands of applications requires a storage technology that is flexible enough servers located in many data centers around the world. There are to let application designers configure their data store appropriately strict operational requirements on Amazon’s platform in terms of based on these tradeoffs to achieve high availability and performance, reliability and efficiency, and to support continuous guaranteed performance in the most cost effective manner. growth the platform needs to be highly scalable. Reliability is one of the most important requirements because even the slightest There are many services on Amazon’s platform that only need outage has significant financial consequences and impacts primary-key access to a data store. For many services, such as customer trust. In addition, to support continuous growth, the those that provide best seller lists, shopping carts, customer platform needs to be highly scalable. preferences, session management, sales rank, and product catalog, the common pattern of using a relational database would lead to inefficiencies and limit scale and availability. Dynamo provides a simple primary-key only interface to meet the requirements of these applications. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are Dynamo uses a synthesis of well known techniques to achieve not made or distributed for profit or commercial advantage and that scalability and availability: Data is partitioned and replicated copies bear this notice and the full citation on the first page. To copy using consistent hashing [10], and consistency is facilitated by otherwise, or republish, to post on servers or to redistribute to lists, object versioning [12]. The consistency among replicas during requires prior specific permission and/or a fee. SOSP’07, October 14–17, 2007, Stevenson, Washington, USA. updates is maintained by a quorum-like technique and a Copyright 2007 ACM 978-1-59593-591-5/07/0010...$5.00. decentralized replica synchronization protocol. Dynamo employs 205 195 

2 .a gossip based distributed failure detection and membership This paper describes Dynamo, a highly available data storage protocol. Dynamo is a completely decentralized system with technology that addresses the needs of these important classes of minimal need for manual administration. Storage nodes can be services. Dynamo has a simple key/value interface, is highly added and removed from Dynamo without requiring any manual available with a clearly defined consistency window, is efficient partitioning or redistribution. in its resource usage, and has a simple scale out scheme to address growth in data set size or request rates. Each service that uses In the past year, Dynamo has been the underlying storage Dynamo runs its own Dynamo instances. technology for a number of the core services in Amazon’s e- commerce platform. It was able to scale to extreme peak loads 2.1 System Assumptions and Requirements efficiently without any downtime during the busy holiday The storage system for this class of services has the following shopping season. For example, the service that maintains requirements: shopping cart (Shopping Cart Service) served tens of millions requests that resulted in well over 3 million checkouts in a single Query Model: simple read and write operations to a data item that day and the service that manages session state handled hundreds is uniquely identified by a key. State is stored as binary objects of thousands of concurrently active sessions. (i.e., blobs) identified by unique keys. No operations span multiple data items and there is no need for relational schema. The main contribution of this work for the research community is This requirement is based on the observation that a significant the evaluation of how different techniques can be combined to portion of Amazon’s services can work with this simple query provide a single highly-available system. It demonstrates that an model and do not need any relational schema. Dynamo targets eventually-consistent storage system can be used in production applications that need to store objects that are relatively small with demanding applications. It also provides insight into the (usually less than 1 MB). tuning of these techniques to meet the requirements of production systems with very strict performance demands. ACID Properties: ACID (Atomicity, Consistency, Isolation, Durability) is a set of properties that guarantee that database The paper is structured as follows. Section 2 presents the transactions are processed reliably. In the context of databases, a background and Section 3 presents the related work. Section 4 single logical operation on the data is called a transaction. presents the system design and Section 5 describes the Experience at Amazon has shown that data stores that provide implementation. Section 6 details the experiences and insights ACID guarantees tend to have poor availability. This has been gained by running Dynamo in production and Section 7 concludes widely acknowledged by both the industry and academia [5]. the paper. There are a number of places in this paper where Dynamo targets applications that operate with weaker consistency additional information may have been appropriate but where (the “C” in ACID) if this results in high availability. Dynamo protecting Amazon’s business interests require us to reduce some does not provide any isolation guarantees and permits only single level of detail. For this reason, the intra- and inter-datacenter key updates. latencies in section 6, the absolute request rates in section 6.2 and outage lengths and workloads in section 6.3 are provided through Efficiency: The system needs to function on a commodity aggregate measures instead of absolute details. hardware infrastructure. In Amazon’s platform, services have stringent latency requirements which are in general measured at 2. BACKGROUND the 99.9th percentile of the distribution. Given that state access Amazon’s e-commerce platform is composed of hundreds of plays a crucial role in service operation the storage system must services that work in concert to deliver functionality ranging from be capable of meeting such stringent SLAs (see Section 2.2 recommendations to order fulfillment to fraud detection. Each below). Services must be able to configure Dynamo such that they service is exposed through a well defined interface and is consistently achieve their latency and throughput requirements. accessible over the network. These services are hosted in an The tradeoffs are in performance, cost efficiency, availability, and infrastructure that consists of tens of thousands of servers located durability guarantees. across many data centers world-wide. Some of these services are stateless (i.e., services which aggregate responses from other Other Assumptions: Dynamo is used only by Amazon’s internal services) and some are stateful (i.e., a service that generates its services. Its operation environment is assumed to be non-hostile response by executing business logic on its state stored in and there are no security related requirements such as persistent store). authentication and authorization. Moreover, since each service uses its distinct instance of Dynamo, its initial design targets a Traditionally production systems store their state in relational scale of up to hundreds of storage hosts. We will discuss the databases. For many of the more common usage patterns of state scalability limitations of Dynamo and possible scalability related persistence, however, a relational database is a solution that is far extensions in later sections. from ideal. Most of these services only store and retrieve data by primary key and do not require the complex querying and 2.2 Service Level Agreements (SLA) management functionality offered by an RDBMS. This excess To guarantee that the application can deliver its functionality in a functionality requires expensive hardware and highly skilled bounded time, each and every dependency in the platform needs personnel for its operation, making it a very inefficient solution. to deliver its functionality with even tighter bounds. Clients and In addition, the available replication technologies are limited and services engage in a Service Level Agreement (SLA), a formally typically choose consistency over availability. Although many negotiated contract where a client and a service agree on several advances have been made in the recent years, it is still not easy to system-related characteristics, which most prominently include scale-out databases or use smart partitioning schemes for load the client’s expected request rate distribution for a particular API balancing. and the expected service latency under those conditions. An example of a simple SLA is a service guaranteeing that it will 206 196 

3 . production systems have shown that this approach provides a better overall experience compared to those systems that meet SLAs defined based on the mean or median. In this paper there are many references to this 99.9th percentile of distributions, which reflects Amazon engineers’ relentless focus on performance from the perspective of the customers’ experience. Many papers report on averages, so these are included where it makes sense for comparison purposes. Nevertheless, Amazon’s engineering and optimization efforts are not focused on averages. Several techniques, such as the load balanced selection of write coordinators, are purely targeted at controlling performance at the 99.9th percentile. Storage systems often play an important role in establishing a service’s SLA, especially if the business logic is relatively lightweight, as is the case for many Amazon services. State management then becomes the main component of a service’s SLA. One of the main design considerations for Dynamo is to give services control over their system properties, such as durability and consistency, and to let services make their own tradeoffs between functionality, performance and cost- effectiveness. Figure 1: Service-oriented architecture of Amazon’s 2.3 Design Considerations platform Data replication algorithms used in commercial systems traditionally perform synchronous replica coordination in order to provide a response within 300ms for 99.9% of its requests for a provide a strongly consistent data access interface. To achieve this peak client load of 500 requests per second. level of consistency, these algorithms are forced to tradeoff the In Amazon’s decentralized service oriented infrastructure, SLAs availability of the data under certain failure scenarios. For play an important role. For example a page request to one of the instance, rather than dealing with the uncertainty of the e-commerce sites typically requires the rendering engine to correctness of an answer, the data is made unavailable until it is construct its response by sending requests to over 150 services. absolutely certain that it is correct. From the very early replicated These services often have multiple dependencies, which database works, it is well known that when dealing with the frequently are other services, and as such it is not uncommon for possibility of network failures, strong consistency and high data the call graph of an application to have more than one level. To availability cannot be achieved simultaneously [2, 11]. As such ensure that the page rendering engine can maintain a clear bound systems and applications need to be aware which properties can on page delivery each service within the call chain must obey its be achieved under which conditions. performance contract. For systems prone to server and network failures, availability can Figure 1 shows an abstract view of the architecture of Amazon’s be increased by using optimistic replication techniques, where platform, where dynamic web content is generated by page changes are allowed to propagate to replicas in the background, rendering components which in turn query many other services. A and concurrent, disconnected work is tolerated. The challenge service can use different data stores to manage its state and these with this approach is that it can lead to conflicting changes which data stores are only accessible within its service boundaries. Some must be detected and resolved. This process of conflict resolution services act as aggregators by using several other services to introduces two problems: when to resolve them and who resolves produce a composite response. Typically, the aggregator services them. Dynamo is designed to be an eventually consistent data are stateless, although they use extensive caching. store; that is all updates reach all replicas eventually. A common approach in the industry for forming a performance An important design consideration is to decide when to perform oriented SLA is to describe it using average, median and expected the process of resolving update conflicts, i.e., whether conflicts variance. At Amazon we have found that these metrics are not should be resolved during reads or writes. Many traditional data good enough if the goal is to build a system where all customers stores execute conflict resolution during writes and keep the read have a good experience, rather than just the majority. For complexity simple [7]. In such systems, writes may be rejected if example if extensive personalization techniques are used then the data store cannot reach all (or a majority of) the replicas at a customers with longer histories require more processing which given time. On the other hand, Dynamo targets the design space impacts performance at the high-end of the distribution. An SLA of an “always writeable” data store (i.e., a data store that is highly stated in terms of mean or median response times will not address available for writes). For a number of Amazon services, rejecting the performance of this important customer segment. To address customer updates could result in a poor customer experience. For this issue, at Amazon, SLAs are expressed and measured at the instance, the shopping cart service must allow customers to add 99.9th percentile of the distribution. The choice for 99.9% over an and remove items from their shopping cart even amidst network even higher percentile has been made based on a cost-benefit and server failures. This requirement forces us to push the analysis which demonstrated a significant increase in cost to complexity of conflict resolution to the reads in order to ensure improve performance that much. Experiences with Amazon’s that writes are never rejected. 207 197 

4 .The next design choice is who performs the process of conflict Various storage systems, such as Oceanstore [9] and PAST [17] resolution. This can be done by the data store or the application. If were built on top of these routing overlays. Oceanstore provides a conflict resolution is done by the data store, its choices are rather global, transactional, persistent storage service that supports limited. In such cases, the data store can only use simple policies, serialized updates on widely replicated data. To allow for such as “last write wins” [22], to resolve conflicting updates. On concurrent updates while avoiding many of the problems inherent the other hand, since the application is aware of the data schema it with wide-area locking, it uses an update model based on conflict can decide on the conflict resolution method that is best suited for resolution. Conflict resolution was introduced in [21] to reduce its client’s experience. For instance, the application that maintains the number of transaction aborts. Oceanstore resolves conflicts by customer shopping carts can choose to “merge” the conflicting processing a series of updates, choosing a total order among them, versions and return a single unified shopping cart. Despite this and then applying them atomically in that order. It is built for an flexibility, some application developers may not want to write environment where the data is replicated on an untrusted their own conflict resolution mechanisms and choose to push it infrastructure. By comparison, PAST provides a simple down to the data store, which in turn chooses a simple policy such abstraction layer on top of Pastry for persistent and immutable as “last write wins”. objects. It assumes that the application can build the necessary storage semantics (such as mutable files) on top of it. Other key principles embraced in the design are: Incremental scalability: Dynamo should be able to scale out one 3.2 Distributed File Systems and Databases storage host (henceforth, referred to as “node”) at a time, with Distributing data for performance, availability and durability has minimal impact on both operators of the system and the system been widely studied in the file system and database systems itself. community. Compared to P2P storage systems that only support flat namespaces, distributed file systems typically support Symmetry: Every node in Dynamo should have the same set of hierarchical namespaces. Systems like Ficus [15] and Coda [19] responsibilities as its peers; there should be no distinguished node replicate files for high availability at the expense of consistency. or nodes that take special roles or extra set of responsibilities. In Update conflicts are typically managed using specialized conflict our experience, symmetry simplifies the process of system resolution procedures. The Farsite system [1] is a distributed file provisioning and maintenance. system that does not use any centralized server like NFS. Farsite Decentralization: An extension of symmetry, the design should achieves high availability and scalability using replication. The favor decentralized peer-to-peer techniques over centralized Google File System [6] is another distributed file system built for control. In the past, centralized control has resulted in outages and hosting the state of Google’s internal applications. GFS uses a the goal is to avoid it as much as possible. This leads to a simpler, simple design with a single master server for hosting the entire more scalable, and more available system. metadata and where the data is split into chunks and stored in chunkservers. Bayou is a distributed relational database system Heterogeneity: The system needs to be able to exploit that allows disconnected operations and provides eventual data heterogeneity in the infrastructure it runs on. e.g. the work consistency [21]. distribution must be proportional to the capabilities of the individual servers. This is essential in adding new nodes with Among these systems, Bayou, Coda and Ficus allow disconnected higher capacity without having to upgrade all hosts at once. operations and are resilient to issues such as network partitions and outages. These systems differ on their conflict resolution 3. RELATED WORK procedures. For instance, Coda and Ficus perform system level conflict resolution and Bayou allows application level resolution. 3.1 Peer to Peer Systems All of them, however, guarantee eventual consistency. Similar to There are several peer-to-peer (P2P) systems that have looked at these systems, Dynamo allows read and write operations to the problem of data storage and distribution. The first generation continue even during network partitions and resolves updated of P2P systems, such as Freenet and Gnutella1, were conflicts using different conflict resolution mechanisms. predominantly used as file sharing systems. These were examples Distributed block storage systems like FAB [18] split large size of unstructured P2P networks where the overlay links between objects into smaller blocks and stores each block in a highly peers were established arbitrarily. In these networks, a search available manner. In comparison to these systems, a key-value query is usually flooded through the network to find as many store is more suitable in this case because: (a) it is intended to peers as possible that share the data. P2P systems evolved to the store relatively small objects (size < 1M) and (b) key-value stores next generation into what is widely known as structured P2P are easier to configure on a per-application basis. Antiquity is a networks. These networks employ a globally consistent protocol wide-area distributed storage system designed to handle multiple to ensure that any node can efficiently route a search query to server failures [23]. It uses a secure log to preserve data integrity, some peer that has the desired data. Systems like Pastry [16] and replicates each log on multiple servers for durability, and uses Chord [20] use routing mechanisms to ensure that queries can be Byzantine fault tolerance protocols to ensure data consistency. In answered within a bounded number of hops. To reduce the contrast to Antiquity, Dynamo does not focus on the problem of additional latency introduced by multi-hop routing, some P2P data integrity and security and is built for a trusted environment. systems (e.g., [14]) employ O(1) routing where each peer Bigtable is a distributed storage system for managing structured maintains enough routing information locally so that it can route data. It maintains a sparse, multi-dimensional sorted map and requests (to access a data item) to the appropriate peer within a allows applications to access their data using multiple attributes constant number of hops. [2]. Compared to Bigtable, Dynamo targets applications that require only key/value access with primary focus on high 1 http://freenetproject.org/, http://www.gnutella.org availability where updates are not rejected even in the wake of network partitions or server failures. 208 198 

5 . Table 1: Summary of techniques used in Dynamo and Key K their advantages. A Problem Technique Advantage G Partitioning Consistent Hashing Incremental B Scalability Nodes B, C and D store High Availability Vector clocks with Version size is keys in for writes reconciliation during decoupled from F C range (A,B) reads update rates. including Handling temporary Sloppy Quorum and Provides high K. failures hinted handoff availability and E D durability guarantee when some of the replicas are not available. Figure 2: Partitioning and replication of keys in Dynamo Recovering from Anti-entropy using Synchronizes ring. permanent failures Merkle trees divergent replicas in the background. Traditional replicated relational database systems focus on the problem of guaranteeing strong consistency to replicated data. Membership and Gossip-based Preserves symmetry Although strong consistency provides the application writer a failure detection membership protocol and avoids having a and failure detection. centralized registry convenient programming model, these systems are limited in for storing scalability and availability [7]. These systems are not capable of membership and handling network partitions because they typically provide strong node liveness consistency guarantees. information. 3.3 Discussion Dynamo differs from the aforementioned decentralized storage Table 1 presents a summary of the list of techniques Dynamo uses systems in terms of its target requirements. First, Dynamo is and their respective advantages. targeted mainly at applications that need an “always writeable” data store where no updates are rejected due to failures or 4.1 System Interface concurrent writes. This is a crucial requirement for many Amazon Dynamo stores objects associated with a key through a simple applications. Second, as noted earlier, Dynamo is built for an interface; it exposes two operations: get() and put(). The get(key) infrastructure within a single administrative domain where all operation locates the object replicas associated with the key in the nodes are assumed to be trusted. Third, applications that use storage system and returns a single object or a list of objects with Dynamo do not require support for hierarchical namespaces (a conflicting versions along with a context. The put(key, context, norm in many file systems) or complex relational schema object) operation determines where the replicas of the object (supported by traditional databases). Fourth, Dynamo is built for should be placed based on the associated key, and writes the latency sensitive applications that require at least 99.9% of read replicas to disk. The context encodes system metadata about the and write operations to be performed within a few hundred object that is opaque to the caller and includes information such as milliseconds. To meet these stringent latency requirements, it was the version of the object. The context information is stored along imperative for us to avoid routing requests through multiple nodes with the object so that the system can verify the validity of the (which is the typical design adopted by several distributed hash context object supplied in the put request. table systems such as Chord and Pastry). This is because multi- Dynamo treats both the key and the object supplied by the caller hop routing increases variability in response times, thereby as an opaque array of bytes. It applies a MD5 hash on the key to increasing the latency at higher percentiles. Dynamo can be generate a 128-bit identifier, which is used to determine the characterized as a zero-hop DHT, where each node maintains storage nodes that are responsible for serving the key. enough routing information locally to route a request to the appropriate node directly. 4.2 Partitioning Algorithm One of the key design requirements for Dynamo is that it must 4. SYSTEM ARCHITECTURE scale incrementally. This requires a mechanism to dynamically The architecture of a storage system that needs to operate in a partition the data over the set of nodes (i.e., storage hosts) in the production setting is complex. In addition to the actual data system. Dynamo’s partitioning scheme relies on consistent persistence component, the system needs to have scalable and hashing to distribute the load across multiple storage hosts. In robust solutions for load balancing, membership and failure consistent hashing [10], the output range of a hash function is detection, failure recovery, replica synchronization, overload treated as a fixed circular space or “ring” (i.e. the largest hash handling, state transfer, concurrency and job scheduling, request value wraps around to the smallest hash value). Each node in the marshalling, request routing, system monitoring and alarming, system is assigned a random value within this space which and configuration management. Describing the details of each of represents its “position” on the ring. Each data item identified by the solutions is not possible, so this paper focuses on the core a key is assigned to a node by hashing the data item’s key to yield distributed systems techniques used in Dynamo: partitioning, its position on the ring, and then walking the ring clockwise to replication, versioning, membership, failure handling and scaling. find the first node with a position larger than the item’s position. 209 199 

6 .Thus, each node becomes responsible for the region in the ring return to its caller before the update has been applied at all the between it and its predecessor node on the ring. The principle replicas, which can result in scenarios where a subsequent get() advantage of consistent hashing is that departure or arrival of a operation may return an object that does not have the latest node only affects its immediate neighbors and other nodes remain updates.. If there are no failures then there is a bound on the unaffected. update propagation times. However, under certain failure scenarios (e.g., server outages or network partitions), updates may The basic consistent hashing algorithm presents some challenges. not arrive at all replicas for an extended period of time. First, the random position assignment of each node on the ring leads to non-uniform data and load distribution. Second, the basic There is a category of applications in Amazon’s platform that can algorithm is oblivious to the heterogeneity in the performance of tolerate such inconsistencies and can be constructed to operate nodes. To address these issues, Dynamo uses a variant of under these conditions. For example, the shopping cart application consistent hashing (similar to the one used in [10, 20]): instead of requires that an “Add to Cart” operation can never be forgotten or mapping a node to a single point in the circle, each node gets rejected. If the most recent state of the cart is unavailable, and a assigned to multiple points in the ring. To this end, Dynamo uses user makes changes to an older version of the cart, that change is the concept of “virtual nodes”. A virtual node looks like a single still meaningful and should be preserved. But at the same time it node in the system, but each node can be responsible for more shouldn’t supersede the currently unavailable state of the cart, than one virtual node. Effectively, when a new node is added to which itself may contain changes that should be preserved. Note the system, it is assigned multiple positions (henceforth, “tokens”) that both “add to cart” and “delete item from cart” operations are in the ring. The process of fine-tuning Dynamo’s partitioning translated into put requests to Dynamo. When a customer wants to scheme is discussed in Section 6. add an item to (or remove from) a shopping cart and the latest version is not available, the item is added to (or removed from) Using virtual nodes has the following advantages: the older version and the divergent versions are reconciled later. • If a node becomes unavailable (due to failures or routine In order to provide this kind of guarantee, Dynamo treats the maintenance), the load handled by this node is evenly result of each modification as a new and immutable version of the dispersed across the remaining available nodes. data. It allows for multiple versions of an object to be present in • When a node becomes available again, or a new node is the system at the same time. Most of the time, new versions added to the system, the newly available node accepts a subsume the previous version(s), and the system itself can roughly equivalent amount of load from each of the other determine the authoritative version (syntactic reconciliation). available nodes. However, version branching may happen, in the presence of failures combined with concurrent updates, resulting in • The number of virtual nodes that a node is responsible can conflicting versions of an object. In these cases, the system cannot decided based on its capacity, accounting for heterogeneity reconcile the multiple versions of the same object and the client in the physical infrastructure. must perform the reconciliation in order to collapse multiple branches of data evolution back into one (semantic 4.3 Replication reconciliation). A typical example of a collapse operation is To achieve high availability and durability, Dynamo replicates its “merging” different versions of a customer’s shopping cart. Using data on multiple hosts. Each data item is replicated at N hosts, this reconciliation mechanism, an “add to cart” operation is never where N is a parameter configured “per-instance”. Each key, k, is lost. However, deleted items can resurface. assigned to a coordinator node (described in the previous section). The coordinator is in charge of the replication of the data items It is important to understand that certain failure modes can that fall within its range. In addition to locally storing each key potentially result in the system having not just two but several within its range, the coordinator replicates these keys at the N-1 versions of the same data. Updates in the presence of network clockwise successor nodes in the ring. This results in a system partitions and node failures can potentially result in an object where each node is responsible for the region of the ring between having distinct version sub-histories, which the system will need it and its Nth predecessor. In Figure 2, node B replicates the key k to reconcile in the future. This requires us to design applications at nodes C and D in addition to storing it locally. Node D will that explicitly acknowledge the possibility of multiple versions of store the keys that fall in the ranges (A, B], (B, C], and (C, D]. the same data (in order to never lose any updates). The list of nodes that is responsible for storing a particular key is Dynamo uses vector clocks [12] in order to capture causality called the preference list. The system is designed, as will be between different versions of the same object. A vector clock is explained in Section 4.8, so that every node in the system can effectively a list of (node, counter) pairs. One vector clock is determine which nodes should be in this list for any particular associated with every version of every object. One can determine key. To account for node failures, preference list contains more whether two versions of an object are on parallel branches or have than N nodes. Note that with the use of virtual nodes, it is possible a causal ordering, by examine their vector clocks. If the counters that the first N successor positions for a particular key may be on the first object’s clock are less-than-or-equal to all of the nodes owned by less than N distinct physical nodes (i.e. a node may in the second clock, then the first is an ancestor of the second and hold more than one of the first N positions). To address this, the can be forgotten. Otherwise, the two changes are considered to be preference list for a key is constructed by skipping positions in the in conflict and require reconciliation. ring to ensure that the list contains only distinct physical nodes. In Dynamo, when a client wishes to update an object, it must specify which version it is updating. This is done by passing the 4.4 Data Versioning context it obtained from an earlier read operation, which contains Dynamo provides eventual consistency, which allows for updates the vector clock information. Upon processing a read request, if to be propagated to all replicas asynchronously. A put() call may 210 200 

7 . object. In practice, this is not likely because the writes are usually handled by one of the top N nodes in the preference list. In case of network partitions or multiple server failures, write requests may be handled by nodes that are not in the top N nodes in the preference list causing the size of vector clock to grow. In these scenarios, it is desirable to limit the size of vector clock. To this end, Dynamo employs the following clock truncation scheme: Along with each (node, counter) pair, Dynamo stores a timestamp that indicates the last time the node updated the data item. When the number of (node, counter) pairs in the vector clock reaches a threshold (say 10), the oldest pair is removed from the clock. Clearly, this truncation scheme can lead to inefficiencies in reconciliation as the descendant relationships cannot be derived accurately. However, this problem has not surfaced in production and therefore this issue has not been thoroughly investigated. 4.5 Execution of get () and put () operations Any storage node in Dynamo is eligible to receive client get and put operations for any key. In this section, for sake of simplicity, we describe how these operations are performed in a failure-free Figure 3: Version evolution of an object over time. environment and in the subsequent section we describe how read and write operations are executed during failures. Dynamo has access to multiple branches that cannot be syntactically reconciled, it will return all the objects at the leaves, Both get and put operations are invoked using Amazon’s with the corresponding version information in the context. An infrastructure-specific request processing framework over HTTP. update using this context is considered to have reconciled the There are two strategies that a client can use to select a node: (1) divergent versions and the branches are collapsed into a single route its request through a generic load balancer that will select a new version. node based on load information, or (2) use a partition-aware client library that routes requests directly to the appropriate coordinator To illustrate the use of vector clocks, let us consider the example nodes. The advantage of the first approach is that the client does shown in Figure 3. A client writes a new object. The node (say not have to link any code specific to Dynamo in its application, Sx) that handles the write for this key increases its sequence whereas the second strategy can achieve lower latency because it number and uses it to create the data's vector clock. The system skips a potential forwarding step. now has the object D1 and its associated clock [(Sx, 1)]. The client updates the object. Assume the same node handles this A node handling a read or write operation is known as the request as well. The system now also has object D2 and its coordinator. Typically, this is the first among the top N nodes in associated clock [(Sx, 2)]. D2 descends from D1 and therefore the preference list. If the requests are received through a load over-writes D1, however there may be replicas of D1 lingering at balancer, requests to access a key may be routed to any random nodes that have not yet seen D2. Let us assume that the same node in the ring. In this scenario, the node that receives the client updates the object again and a different server (say Sy) request will not coordinate it if the node is not in the top N of the handles the request. The system now has data D3 and its requested key’s preference list. Instead, that node will forward the associated clock [(Sx, 2), (Sy, 1)]. request to the first among the top N nodes in the preference list. Next assume a different client reads D2 and then tries to update it, Read and write operations involve the first N healthy nodes in the and another node (say Sz) does the write. The system now has D4 preference list, skipping over those that are down or inaccessible. (descendant of D2) whose version clock is [(Sx, 2), (Sz, 1)]. A When all nodes are healthy, the top N nodes in a key’s preference node that is aware of D1 or D2 could determine, upon receiving list are accessed. When there are node failures or network D4 and its clock, that D1 and D2 are overwritten by the new data partitions, nodes that are lower ranked in the preference list are and can be garbage collected. A node that is aware of D3 and accessed. receives D4 will find that there is no causal relation between To maintain consistency among its replicas, Dynamo uses a them. In other words, there are changes in D3 and D4 that are not consistency protocol similar to those used in quorum systems. reflected in each other. Both versions of the data must be kept and This protocol has two key configurable values: R and W. R is the presented to a client (upon a read) for semantic reconciliation. minimum number of nodes that must participate in a successful Now assume some client reads both D3 and D4 (the context will read operation. W is the minimum number of nodes that must reflect that both values were found by the read). The read's participate in a successful write operation. Setting R and W such context is a summary of the clocks of D3 and D4, namely [(Sx, 2), that R + W > N yields a quorum-like system. In this model, the (Sy, 1), (Sz, 1)]. If the client performs the reconciliation and node latency of a get (or put) operation is dictated by the slowest of the Sx coordinates the write, Sx will update its sequence number in R (or W) replicas. For this reason, R and W are usually the clock. The new data D5 will have the following clock: [(Sx, configured to be less than N, to provide better latency. 3), (Sy, 1), (Sz, 1)]. Upon receiving a put() request for a key, the coordinator generates A possible issue with vector clocks is that the size of vector the vector clock for the new version and writes the new version clocks may grow if many servers coordinate the writes to an locally. The coordinator then sends the new version (along with 211 201 

8 .the new vector clock) to the N highest-ranked reachable nodes. If the original replica node. To handle this and other threats to at least W-1 nodes respond then the write is considered durability, Dynamo implements an anti-entropy (replica successful. synchronization) protocol to keep the replicas synchronized. Similarly, for a get() request, the coordinator requests all existing To detect the inconsistencies between replicas faster and to versions of data for that key from the N highest-ranked reachable minimize the amount of transferred data, Dynamo uses Merkle nodes in the preference list for that key, and then waits for R trees [13]. A Merkle tree is a hash tree where leaves are hashes of responses before returning the result to the client. If the the values of individual keys. Parent nodes higher in the tree are coordinator ends up gathering multiple versions of the data, it hashes of their respective children. The principal advantage of returns all the versions it deems to be causally unrelated. The Merkle tree is that each branch of the tree can be checked divergent versions are then reconciled and the reconciled version independently without requiring nodes to download the entire tree superseding the current versions is written back. or the entire data set. Moreover, Merkle trees help in reducing the amount of data that needs to be transferred while checking for 4.6 Handling Failures: Hinted Handoff inconsistencies among replicas. For instance, if the hash values of If Dynamo used a traditional quorum approach it would be the root of two trees are equal, then the values of the leaf nodes in unavailable during server failures and network partitions, and the tree are equal and the nodes require no synchronization. If not, would have reduced durability even under the simplest of failure it implies that the values of some replicas are different. In such conditions. To remedy this it does not enforce strict quorum cases, the nodes may exchange the hash values of children and the membership and instead it uses a “sloppy quorum”; all read and process continues until it reaches the leaves of the trees, at which write operations are performed on the first N healthy nodes from point the hosts can identify the keys that are “out of sync”. Merkle the preference list, which may not always be the first N nodes trees minimize the amount of data that needs to be transferred for encountered while walking the consistent hashing ring. synchronization and reduce the number of disk reads performed during the anti-entropy process. Consider the example of Dynamo configuration given in Figure 2 with N=3. In this example, if node A is temporarily down or Dynamo uses Merkle trees for anti-entropy as follows: Each node unreachable during a write operation then a replica that would maintains a separate Merkle tree for each key range (the set of normally have lived on A will now be sent to node D. This is done keys covered by a virtual node) it hosts. This allows nodes to to maintain the desired availability and durability guarantees. The compare whether the keys within a key range are up-to-date. In replica sent to D will have a hint in its metadata that suggests this scheme, two nodes exchange the root of the Merkle tree which node was the intended recipient of the replica (in this case corresponding to the key ranges that they host in common. A). Nodes that receive hinted replicas will keep them in a Subsequently, using the tree traversal scheme described above the separate local database that is scanned periodically. Upon nodes determine if they have any differences and perform the detecting that A has recovered, D will attempt to deliver the appropriate synchronization action. The disadvantage with this replica to A. Once the transfer succeeds, D may delete the object scheme is that many key ranges change when a node joins or from its local store without decreasing the total number of replicas leaves the system thereby requiring the tree(s) to be recalculated. in the system. This issue is addressed, however, by the refined partitioning scheme described in Section 6.2. Using hinted handoff, Dynamo ensures that the read and write operations are not failed due to temporary node or network 4.8 Membership and Failure Detection failures. Applications that need the highest level of availability can set W to 1, which ensures that a write is accepted as long as a 4.8.1 Ring Membership single node in the system has durably written the key it to its local In Amazon’s environment node outages (due to failures and store. Thus, the write request is only rejected if all nodes in the maintenance tasks) are often transient but may last for extended system are unavailable. However, in practice, most Amazon intervals. A node outage rarely signifies a permanent departure services in production set a higher W to meet the desired level of and therefore should not result in rebalancing of the partition durability. A more detailed discussion of configuring N, R and W assignment or repair of the unreachable replicas. Similarly, follows in section 6. manual error could result in the unintentional startup of new Dynamo nodes. For these reasons, it was deemed appropriate to It is imperative that a highly available storage system be capable use an explicit mechanism to initiate the addition and removal of of handling the failure of an entire data center(s). Data center nodes from a Dynamo ring. An administrator uses a command failures happen due to power outages, cooling failures, network line tool or a browser to connect to a Dynamo node and issue a failures, and natural disasters. Dynamo is configured such that membership change to join a node to a ring or remove a node each object is replicated across multiple data centers. In essence, from a ring. The node that serves the request writes the the preference list of a key is constructed such that the storage membership change and its time of issue to persistent store. The nodes are spread across multiple data centers. These datacenters membership changes form a history because nodes can be are connected through high speed network links. This scheme of removed and added back multiple times. A gossip-based protocol replicating across multiple datacenters allows us to handle entire propagates membership changes and maintains an eventually data center failures without a data outage. consistent view of membership. Each node contacts a peer chosen at random every second and the two nodes efficiently reconcile 4.7 Handling permanent failures: Replica their persisted membership change histories. synchronization Hinted handoff works best if the system membership churn is low When a node starts for the first time, it chooses its set of tokens and node failures are transient. There are scenarios under which (virtual nodes in the consistent hash space) and maps nodes to hinted replicas become unavailable before they can be returned to their respective token sets. The mapping is persisted on disk and 212 202 

9 .initially contains only the local node and token set. The mappings us consider a simple bootstrapping scenario where node X is stored at different Dynamo nodes are reconciled during the same added to the ring shown in Figure 2 between A and B. When X is communication exchange that reconciles the membership change added to the system, it is in charge of storing keys in the ranges histories. Therefore, partitioning and placement information also (F, G], (G, A] and (A, X]. As a consequence, nodes B, C and D no propagates via the gossip-based protocol and each storage node is longer have to store the keys in these respective ranges. aware of the token ranges handled by its peers. This allows each Therefore, nodes B, C, and D will offer to and upon confirmation node to forward a key’s read/write operations to the right set of from X transfer the appropriate set of keys. When a node is nodes directly. removed from the system, the reallocation of keys happens in a reverse process. 4.8.2 External Discovery The mechanism described above could temporarily result in a Operational experience has shown that this approach distributes logically partitioned Dynamo ring. For example, the the load of key distribution uniformly across the storage nodes, administrator could contact node A to join A to the ring, then which is important to meet the latency requirements and to ensure contact node B to join B to the ring. In this scenario, nodes A and fast bootstrapping. Finally, by adding a confirmation round B would each consider itself a member of the ring, yet neither between the source and the destination, it is made sure that the would be immediately aware of the other. To prevent logical destination node does not receive any duplicate transfers for a partitions, some Dynamo nodes play the role of seeds. Seeds are given key range. nodes that are discovered via an external mechanism and are known to all nodes. Because all nodes eventually reconcile their 5. IMPLEMENTATION membership with a seed, logical partitions are highly unlikely. In Dynamo, each storage node has three main software Seeds can be obtained either from static configuration or from a components: request coordination, membership and failure configuration service. Typically seeds are fully functional nodes detection, and a local persistence engine. All these components in the Dynamo ring. are implemented in Java. Dynamo’s local persistence component allows for different 4.8.3 Failure Detection storage engines to be plugged in. Engines that are in use are Failure detection in Dynamo is used to avoid attempts to Berkeley Database (BDB) Transactional Data Store2, BDB Java communicate with unreachable peers during get() and put() Edition, MySQL, and an in-memory buffer with persistent operations and when transferring partitions and hinted replicas. backing store. The main reason for designing a pluggable For the purpose of avoiding failed attempts at communication, a persistence component is to choose the storage engine best suited purely local notion of failure detection is entirely sufficient: node for an application’s access patterns. For instance, BDB can handle A may consider node B failed if node B does not respond to node objects typically in the order of tens of kilobytes whereas MySQL A’s messages (even if B is responsive to node C's messages). In can handle objects of larger sizes. Applications choose Dynamo’s the presence of a steady rate of client requests generating inter- local persistence engine based on their object size distribution. node communication in the Dynamo ring, a node A quickly The majority of Dynamo’s production instances use BDB discovers that a node B is unresponsive when B fails to respond to Transactional Data Store. a message; Node A then uses alternate nodes to service requests that map to B's partitions; A periodically retries B to check for the The request coordination component is built on top of an event- latter's recovery. In the absence of client requests to drive traffic driven messaging substrate where the message processing pipeline between two nodes, neither node really needs to know whether the is split into multiple stages similar to the SEDA architecture [24]. other is reachable and responsive. All communications are implemented using Java NIO channels. The coordinator executes the read and write requests on behalf of Decentralized failure detection protocols use a simple gossip-style clients by collecting data from one or more nodes (in the case of protocol that enable each node in the system to learn about the reads) or storing data at one or more nodes (for writes). Each arrival (or departure) of other nodes. For detailed information on client request results in the creation of a state machine on the node decentralized failure detectors and the parameters affecting their that received the client request. The state machine contains all the accuracy, the interested reader is referred to [8]. Early designs of logic for identifying the nodes responsible for a key, sending the Dynamo used a decentralized failure detector to maintain a requests, waiting for responses, potentially doing retries, globally consistent view of failure state. Later it was determined processing the replies and packaging the response to the client. that the explicit node join and leave methods obviates the need for Each state machine instance handles exactly one client request. a global view of failure state. This is because nodes are notified of For instance, a read operation implements the following state permanent node additions and removals by the explicit node join machine: (i) send read requests to the nodes, (ii) wait for and leave methods and temporary node failures are detected by minimum number of required responses, (iii) if too few replies the individual nodes when they fail to communicate with others were received within a given time bound, fail the request, (iv) (while forwarding requests). otherwise gather all the data versions and determine the ones to be 4.9 Adding/Removing Storage Nodes returned and (v) if versioning is enabled, perform syntactic reconciliation and generate an opaque write context that contains When a new node (say X) is added into the system, it gets the vector clock that subsumes all the remaining versions. For the assigned a number of tokens that are randomly scattered on the sake of brevity the failure handling and retry states are left out. ring. For every key range that is assigned to node X, there may be a number of nodes (less than or equal to N) that are currently in After the read response has been returned to the caller the state charge of handling keys that fall within its token range. Due to the 2 allocation of key ranges to X, some existing nodes no longer have http://www.oracle.com/database/berkeley-db.html to some of their keys and these nodes transfer those keys to X. Let 213 203 

10 .Figure 4: Average and 99.9 percentiles of latencies for read and Figure 5: Comparison of performance of 99.9th percentile write requests during our peak request season of December 2006. latencies for buffered vs. non-buffered writes over a period of The intervals between consecutive ticks in the x-axis correspond 24 hours. The intervals between consecutive ticks in the x-axis to 12 hours. Latencies follow a diurnal pattern similar to the correspond to one hour. request rate and 99.9 percentile latencies are an order of magnitude higher than averages machine waits for a small period of time to receive any • Timestamp based reconciliation: This case differs from the outstanding responses. If stale versions were returned in any of previous one only in the reconciliation mechanism. In case of the responses, the coordinator updates those nodes with the latest divergent versions, Dynamo performs simple timestamp version. This process is called read repair because it repairs based reconciliation logic of “last write wins”; i.e., the object replicas that have missed a recent update at an opportunistic time with the largest physical timestamp value is chosen as the and relieves the anti-entropy protocol from having to do it. correct version. The service that maintains customer’s session information is a good example of a service that uses As noted earlier, write requests are coordinated by one of the top this mode. N nodes in the preference list. Although it is desirable always to have the first node among the top N to coordinate the writes • High performance read engine: While Dynamo is built to be thereby serializing all writes at a single location, this approach has an “always writeable” data store, a few services are tuning its led to uneven load distribution resulting in SLA violations. This is quorum characteristics and using it as a high performance because the request load is not uniformly distributed across read engine. Typically, these services have a high read objects. To counter this, any of the top N nodes in the preference request rate and only a small number of updates. In this list is allowed to coordinate the writes. In particular, since each configuration, typically R is set to be 1 and W to be N. For write usually follows a read operation, the coordinator for a write these services, Dynamo provides the ability to partition and is chosen to be the node that replied fastest to the previous read replicate their data across multiple nodes thereby offering operation which is stored in the context information of the incremental scalability. Some of these instances function as request. This optimization enables us to pick the node that has the the authoritative persistence cache for data stored in more data that was read by the preceding read operation thereby heavy weight backing stores. Services that maintain product increasing the chances of getting “read-your-writes” consistency. catalog and promotional items fit in this category. It also reduces variability in the performance of the request handling which improves the performance at the 99.9 percentile. The main advantage of Dynamo is that its client applications can tune the values of N, R and W to achieve their desired levels of 6. EXPERIENCES & LESSONS LEARNED performance, availability and durability. For instance, the value of Dynamo is used by several services with different configurations. N determines the durability of each object. A typical value of N These instances differ by their version reconciliation logic, and used by Dynamo’s users is 3. read/write quorum characteristics. The following are the main The values of W and R impact object availability, durability and patterns in which Dynamo is used: consistency. For instance, if W is set to 1, then the system will • Business logic specific reconciliation: This is a popular use never reject a write request as long as there is at least one node in case for Dynamo. Each data object is replicated across the system that can successfully process a write request. However, multiple nodes. In case of divergent versions, the client low values of W and R can increase the risk of inconsistency as application performs its own reconciliation logic. The write requests are deemed successful and returned to the clients shopping cart service discussed earlier is a prime example of even if they are not processed by a majority of the replicas. This this category. Its business logic reconciles objects by also introduces a vulnerability window for durability when a write merging different versions of a customer’s shopping cart. request is successfully returned to the client even though it has been persisted at only a small number of nodes. 214 204 

11 . significant difference in request rate between the daytime and night). Moreover, the write latencies are higher than read latencies obviously because write operations always results in disk access. Also, the 99.9th percentile latencies are around 200 ms and are an order of magnitude higher than the averages. This is because the 99.9th percentile latencies are affected by several factors such as variability in request load, object sizes, and locality patterns. While this level of performance is acceptable for a number of services, a few customer-facing services required higher levels of performance. For these services, Dynamo provides the ability to trade-off durability guarantees for performance. In the optimization each storage node maintains an object buffer in its main memory. Each write operation is stored in the buffer and Figure 6: Fraction of nodes that are out-of-balance (i.e., nodes gets periodically written to storage by a writer thread. In this whose request load is above a certain threshold from the scheme, read operations first check if the requested key is present average system load) and their corresponding request load. in the buffer. If so, the object is read from the buffer instead of the The interval between ticks in x-axis corresponds to a time storage engine. period of 30 minutes. This optimization has resulted in lowering the 99.9th percentile latency by a factor of 5 during peak traffic even for a very small Traditional wisdom holds that durability and availability go hand- buffer of a thousand objects (see Figure 5). Also, as seen in the in-hand. However, this is not necessarily true here. For instance, figure, write buffering smoothes out higher percentile latencies. the vulnerability window for durability can be decreased by Obviously, this scheme trades durability for performance. In this increasing W. This may increase the probability of rejecting scheme, a server crash can result in missing writes that were requests (thereby decreasing availability) because more storage queued up in the buffer. To reduce the durability risk, the write hosts need to be alive to process a write request. operation is refined to have the coordinator choose one out of the The common (N,R,W) configuration used by several instances of N replicas to perform a “durable write”. Since the coordinator Dynamo is (3,2,2). These values are chosen to meet the necessary waits only for W responses, the performance of the write levels of performance, durability, consistency, and availability operation is not affected by the performance of the durable write SLAs. operation performed by a single replica. All the measurements presented in this section were taken on a 6.2 Ensuring Uniform Load distribution live system operating with a configuration of (3,2,2) and running Dynamo uses consistent hashing to partition its key space across a couple hundred nodes with homogenous hardware its replicas and to ensure uniform load distribution. A uniform key configurations. As mentioned earlier, each instance of Dynamo distribution can help us achieve uniform load distribution contains nodes that are located in multiple datacenters. These assuming the access distribution of keys is not highly skewed. In datacenters are typically connected through high speed network particular, Dynamo’s design assumes that even where there is a links. Recall that to generate a successful get (or put) response R significant skew in the access distribution there are enough keys (or W) nodes need to respond to the coordinator. Clearly, the in the popular end of the distribution so that the load of handling network latencies between datacenters affect the response time popular keys can be spread across the nodes uniformly through and the nodes (and their datacenter locations) are chosen such that partitioning. This section discusses the load imbalance seen in the applications target SLAs are met. Dynamo and the impact of different partitioning strategies on load distribution. 6.1 Balancing Performance and Durability While Dynamo’s principle design goal is to build a highly To study the load imbalance and its correlation with request load, available data store, performance is an equally important criterion the total number of requests received by each node was measured in Amazon’s platform. As noted earlier, to provide a consistent for a period of 24 hours - broken down into intervals of 30 customer experience, Amazon’s services set their performance minutes. In a given time window, a node is considered to be “in- targets at higher percentiles (such as the 99.9th or 99.99th balance”, if the node’s request load deviates from the average load percentiles). A typical SLA required of services that use Dynamo by a value a less than a certain threshold (here 15%). Otherwise is that 99.9% of the read and write requests execute within 300ms. the node was deemed “out-of-balance”. Figure 6 presents the fraction of nodes that are “out-of-balance” (henceforth, Since Dynamo is run on standard commodity hardware “imbalance ratio”) during this time period. For reference, the components that have far less I/O throughput than high-end corresponding request load received by the entire system during enterprise servers, providing consistently high performance for this time period is also plotted. As seen in the figure, the read and write operations is a non-trivial task. The involvement of imbalance ratio decreases with increasing load. For instance, multiple storage nodes in read and write operations makes it even during low loads the imbalance ratio is as high as 20% and during more challenging, since the performance of these operations is high loads it is close to 10%. Intuitively, this can be explained by limited by the slowest of the R or W replicas. Figure 4 shows the the fact that under high loads, a large number of popular keys are average and 99.9th percentile latencies of Dynamo’s read and accessed and due to uniform distribution of keys the load is write operations during a period of 30 days. As seen in the figure, evenly distributed. However, during low loads (where load is 1/8th the latencies exhibit a clear diurnal pattern which is a result of the diurnal pattern in the incoming request rate (i.e., there is a 215 205 

12 . Figure 7: Partitioning and placement of keys in the three strategies. A, B, and C depict the three unique nodes that form the preference list for the key k1 on the consistent hashing ring (N=3). The shaded area indicates the key range for which nodes A, B, and C form the preference list. Dark arrows indicate the token locations for various nodes. of the measured peak load), fewer popular keys are accessed, The fundamental issue with this strategy is that the schemes for resulting in a higher load imbalance. data partitioning and data placement are intertwined. For instance, in some cases, it is preferred to add more nodes to the system in This section discusses how Dynamo’s partitioning scheme has order to handle an increase in request load. However, in this evolved over time and its implications on load distribution. scenario, it is not possible to add nodes without affecting data Strategy 1: T random tokens per node and partition by token partitioning. Ideally, it is desirable to use independent schemes for value: This was the initial strategy deployed in production (and partitioning and placement. To this end, following strategies were described in Section 4.2). In this scheme, each node is assigned T evaluated: tokens (chosen uniformly at random from the hash space). The Strategy 2: T random tokens per node and equal sized partitions: tokens of all nodes are ordered according to their values in the In this strategy, the hash space is divided into Q equally sized hash space. Every two consecutive tokens define a range. The last partitions/ranges and each node is assigned T random tokens. Q is token and the first token form a range that "wraps" around from usually set such that Q >> N and Q >> S*T, where S is the the highest value to the lowest value in the hash space. Because number of nodes in the system. In this strategy, the tokens are the tokens are chosen randomly, the ranges vary in size. As nodes only used to build the function that maps values in the hash space join and leave the system, the token set changes and consequently to the ordered lists of nodes and not to decide the partitioning. A the ranges change. Note that the space needed to maintain the partition is placed on the first N unique nodes that are encountered membership at each node increases linearly with the number of while walking the consistent hashing ring clockwise from the end nodes in the system. of the partition. Figure 7 illustrates this strategy for N=3. In this While using this strategy, the following problems were example, nodes A, B, C are encountered while walking the ring encountered. First, when a new node joins the system, it needs to from the end of the partition that contains key k1. The primary “steal” its key ranges from other nodes. However, the nodes advantages of this strategy are: (i) decoupling of partitioning and handing the key ranges off to the new node have to scan their partition placement, and (ii) enabling the possibility of changing local persistence store to retrieve the appropriate set of data items. the placement scheme at runtime. Note that performing such a scan operation on a production node Strategy 3: Q/S tokens per node, equal-sized partitions: Similar to is tricky as scans are highly resource intensive operations and they strategy 2, this strategy divides the hash space into Q equally need to be executed in the background without affecting the sized partitions and the placement of partition is decoupled from customer performance. This requires us to run the bootstrapping the partitioning scheme. Moreover, each node is assigned Q/S task at the lowest priority. However, this significantly slows the tokens where S is the number of nodes in the system. When a bootstrapping process and during busy shopping season, when the node leaves the system, its tokens are randomly distributed to the nodes are handling millions of requests a day, the bootstrapping remaining nodes such that these properties are preserved. has taken almost a day to complete. Second, when a node Similarly, when a node joins the system it "steals" tokens from joins/leaves the system, the key ranges handled by many nodes nodes in the system in a way that preserves these properties. change and the Merkle trees for the new ranges need to be recalculated, which is a non-trivial operation to perform on a The efficiency of these three strategies is evaluated for a system production system. Finally, there was no easy way to take a with S=30 and N=3. However, comparing these different snapshot of the entire key space due to the randomness in key strategies in a fair manner is hard as different strategies have ranges, and this made the process of archival complicated. In this different configurations to tune their efficiency. For instance, the scheme, archiving the entire key space requires us to retrieve the load distribution property of strategy 1 depends on the number of keys from each node separately, which is highly inefficient. tokens (i.e., T) while strategy 3 depends on the number of partitions (i.e., Q). One fair way to compare these strategies is to 216 206 

13 . 1 6.3 Divergent Versions: When and 0.9 How Many? As noted earlier, Dynamo is designed to tradeoff consistency for Efficieny (mean load/max load) 0.8 availability. To understand the precise impact of different failures on consistency, detailed data is required on multiple factors: 0.7 outage length, type of failure, component reliability, workload etc. Presenting these numbers in detail is outside of the scope of this 0.6 paper. However, this section discusses a good summary metric: 0.5 Strategy 1 the number of divergent versions seen by the application in a live Strategy 2 production environment. Strategy 3 0.4 0 5000 10000 15000 20000 25000 30000 35000 Divergent versions of a data item arise in two scenarios. The first Size of me tadata maintained at each node (in abstract units) is when the system is facing failure scenarios such as node failures, data center failures, and network partitions. The second is when the system is handling a large number of concurrent writers Figure 8: Comparison of the load distribution efficiency of to a single data item and multiple nodes end up coordinating the different strategies for system with 30 nodes and N=3 with updates concurrently. From both a usability and efficiency equal amount of metadata maintained at each node. The perspective, it is preferred to keep the number of divergent values of the system size and number of replicas are based on versions at any given time as low as possible. If the versions the typical configuration deployed for majority of our cannot be syntactically reconciled based on vector clocks alone, services. they have to be passed to the business logic for semantic reconciliation. Semantic reconciliation introduces additional load evaluate the skew in their load distribution while all strategies use on services, so it is desirable to minimize the need for it. the same amount of space to maintain their membership information. For instance, in strategy 1 each node needs to In our next experiment, the number of versions returned to the maintain the token positions of all the nodes in the ring and in shopping cart service was profiled for a period of 24 hours. strategy 3 each node needs to maintain the information regarding During this period, 99.94% of requests saw exactly one version; the partitions assigned to each node. 0.00057% of requests saw 2 versions; 0.00047% of requests saw 3 versions and 0.00009% of requests saw 4 versions. This shows In our next experiment, these strategies were evaluated by varying that divergent versions are created rarely. the relevant parameters (T and Q). The load balancing efficiency of each strategy was measured for different sizes of membership Experience shows that the increase in the number of divergent information that needs to be maintained at each node, where Load versions is contributed not by failures but due to the increase in balancing efficiency is defined as the ratio of average number of number of concurrent writers. The increase in the number of requests served by each node to the maximum number of requests concurrent writes is usually triggered by busy robots (automated served by the hottest node. client programs) and rarely by humans. This issue is not discussed in detail due to the sensitive nature of the story. The results are given in Figure 8. As seen in the figure, strategy 3 achieves the best load balancing efficiency and strategy 2 has the 6.4 Client-driven or Server-driven worst load balancing efficiency. For a brief time, Strategy 2 served as an interim setup during the process of migrating Coordination As mentioned in Section 5, Dynamo has a request coordination Dynamo instances from using Strategy 1 to Strategy 3. Compared component that uses a state machine to handle incoming requests. to Strategy 1, Strategy 3 achieves better efficiency and reduces the Client requests are uniformly assigned to nodes in the ring by a size of membership information maintained at each node by three load balancer. Any Dynamo node can act as a coordinator for a orders of magnitude. While storage is not a major issue the nodes read request. Write requests on the other hand will be coordinated gossip the membership information periodically and as such it is by a node in the key’s current preference list. This restriction is desirable to keep this information as compact as possible. In due to the fact that these preferred nodes have the added addition to this, strategy 3 is advantageous and simpler to deploy responsibility of creating a new version stamp that causally for the following reasons: (i) Faster bootstrapping/recovery: subsumes the version that has been updated by the write request. Since partition ranges are fixed, they can be stored in separate Note that if Dynamo’s versioning scheme is based on physical files, meaning a partition can be relocated as a unit by simply timestamps, any node can coordinate a write request. transferring the file (avoiding random accesses needed to locate specific items). This simplifies the process of bootstrapping and An alternative approach to request coordination is to move the recovery. (ii) Ease of archival: Periodical archiving of the dataset state machine to the client nodes. In this scheme client is a mandatory requirement for most of Amazon storage services. applications use a library to perform request coordination locally. Archiving the entire dataset stored by Dynamo is simpler in A client periodically picks a random Dynamo node and strategy 3 because the partition files can be archived separately. downloads its current view of Dynamo membership state. Using By contrast, in Strategy 1, the tokens are chosen randomly and, this information the client can determine which set of nodes form archiving the data stored in Dynamo requires retrieving the keys the preference list for any given key. Read requests can be from individual nodes separately and is usually inefficient and coordinated at the client node thereby avoiding the extra network slow. The disadvantage of strategy 3 is that changing the node hop that is incurred if the request were assigned to a random membership requires coordination in order to preserve the Dynamo node by the load balancer. Writes will either be properties required of the assignment. forwarded to a node in the key’s preference list or can be 217 207 

14 .Table 2: Performance of client-driven and server-driven shared across all background tasks. A feedback mechanism based coordination approaches. on the monitored performance of the foreground tasks is employed to change the number of slices that are available to the 99.9th 99.9th background tasks. percentile percentile Average Average read write read write The admission controller constantly monitors the behavior of latency latency latency latency resource accesses while executing a "foreground" put/get (ms) (ms) (ms) (ms) operation. Monitored aspects include latencies for disk operations, Server- failed database accesses due to lock-contention and transaction driven 68.9 68.5 3.9 4.02 timeouts, and request queue wait times. This information is used Client- to check whether the percentiles of latencies (or failures) in a driven 30.4 30.4 1.55 1.9 given trailing time window are close to a desired threshold. For example, the background controller checks to see how close the 99th percentile database read latency (over the last 60 seconds) is coordinated locally if Dynamo is using timestamps based to a preset threshold (say 50ms). The controller uses such versioning. comparisons to assess the resource availability for the foreground An important advantage of the client-driven coordination operations. Subsequently, it decides on how many time slices will approach is that a load balancer is no longer required to uniformly be available to background tasks, thereby using the feedback loop distribute client load. Fair load distribution is implicitly to limit the intrusiveness of the background activities. Note that a guaranteed by the near uniform assignment of keys to the storage similar problem of managing background tasks has been studied nodes. Obviously, the efficiency of this scheme is dependent on in [4]. how fresh the membership information is at the client. Currently clients poll a random Dynamo node every 10 seconds for 6.6 Discussion This section summarizes some of the experiences gained during membership updates. A pull based approach was chosen over a the process of implementation and maintenance of Dynamo. push based one as the former scales better with large number of Many Amazon internal services have used Dynamo for the past clients and requires very little state to be maintained at servers two years and it has provided significant levels of availability to regarding clients. However, in the worst case the client can be its applications. In particular, applications have received exposed to stale membership for duration of 10 seconds. In case, successful responses (without timing out) for 99.9995% of its if the client detects its membership table is stale (for instance, requests and no data loss event has occurred to date. when some members are unreachable), it will immediately refresh its membership information. Moreover, the primary advantage of Dynamo is that it provides th the necessary knobs using the three parameters of (N,R,W) to tune Table 2 shows the latency improvements at the 99.9 percentile their instance based on their needs.. Unlike popular commercial and averages that were observed for a period of 24 hours using data stores, Dynamo exposes data consistency and reconciliation client-driven coordination compared to the server-driven logic issues to the developers. At the outset, one may expect the approach. As seen in the table, the client-driven coordination application logic to become more complex. However, historically, approach reduces the latencies by at least 30 milliseconds for Amazon’s platform is built for high availability and many 99.9th percentile latencies and decreases the average by 3 to 4 applications are designed to handle different failure modes and milliseconds. The latency improvement is because the client- inconsistencies that may arise. Hence, porting such applications to driven approach eliminates the overhead of the load balancer and use Dynamo was a relatively simple task. For new applications the extra network hop that may be incurred when a request is that want to use Dynamo, some analysis is required during the assigned to a random node. As seen in the table, average latencies initial stages of the development to pick the right conflict tend to be significantly lower than latencies at the 99.9th resolution mechanisms that meet the business case appropriately. percentile. This is because Dynamo’s storage engine caches and Finally, Dynamo adopts a full membership model where each write buffer have good hit ratios. Moreover, since the load node is aware of the data hosted by its peers. To do this, each balancers and network introduce additional variability to the node actively gossips the full routing table with other nodes in the response time, the gain in response time is higher for the 99.9th system. This model works well for a system that contains couple percentile than the average. of hundreds of nodes. However, scaling such a design to run with 6.5 Balancing background vs. foreground tens of thousands of nodes is not trivial because the overhead in maintaining the routing table increases with the system size. This tasks limitation might be overcome by introducing hierarchical Each node performs different kinds of background tasks for extensions to Dynamo. Also, note that this problem is actively replica synchronization and data handoff (either due to hinting or addressed by O(1) DHT systems(e.g., [14]). adding/removing nodes) in addition to its normal foreground put/get operations. In early production settings, these background 7. CONCLUSIONS tasks triggered the problem of resource contention and affected This paper described Dynamo, a highly available and scalable the performance of the regular put and get operations. Hence, it data store, used for storing state of a number of core services of became necessary to ensure that background tasks ran only when Amazon.com’s e-commerce platform. Dynamo has provided the the regular critical operations are not affected significantly. To desired levels of availability and performance and has been this end, the background tasks were integrated with an admission successful in handling server failures, data center failures and control mechanism. Each of the background tasks uses this network partitions. Dynamo is incrementally scalable and allows controller to reserve runtime slices of the resource (e.g. database), service owners to scale up and down based on their current 218 208 

15 .request load. Dynamo allows service owners to customize their Principles of Distributed Computing (Newport, Rhode storage system to meet their desired performance, durability and Island, United States). PODC '01. ACM Press, New York, consistency SLAs by allowing them to tune the parameters N, R, NY, 170-179. and W. [9] Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, The production use of Dynamo for the past year demonstrates that P., Geels, D., Gummadi, R., Rhea, S., Weatherspoon, H., decentralized techniques can be combined to provide a single Wells, C., and Zhao, B. 2000. OceanStore: an architecture highly-available system. Its success in one of the most for global-scale persistent storage. SIGARCH Comput. challenging application environments shows that an eventual- Archit. News 28, 5 (Dec. 2000), 190-201. consistent storage system can be a building block for highly- [10] Karger, D., Lehman, E., Leighton, T., Panigrahy, R., Levine, available applications. M., and Lewin, D. 1997. Consistent hashing and random trees: distributed caching protocols for relieving hot spots on ACKNOWLEDGEMENTS the World Wide Web. In Proceedings of the Twenty-Ninth The authors would like to thank Pat Helland for his contribution Annual ACM Symposium on theory of Computing (El Paso, to the initial design of Dynamo. We would also like to thank Texas, United States, May 04 - 06, 1997). STOC '97. ACM Marvin Theimer and Robert van Renesse for their comments. Press, New York, NY, 654-663. Finally, we would like to thank our shepherd, Jeff Mogul, for his detailed comments and inputs while preparing the camera ready [11] Lindsay, B.G., et. al., “Notes on Distributed Databases”, version that vastly improved the quality of the paper. Research Report RJ2571(33471), IBM Research, July 1979 [12] Lamport, L. Time, clocks, and the ordering of events in a REFERENCES distributed system. ACM Communications, 21(7), pp. 558- [1] Adya, A., Bolosky, W. J., Castro, M., Cermak, G., Chaiken, 565, 1978. R., Douceur, J. R., Howell, J., Lorch, J. R., Theimer, M., and [13] Merkle, R. A digital signature based on a conventional Wattenhofer, R. P. 2002. Farsite: federated, available, and encryption function. Proceedings of CRYPTO, pages 369– reliable storage for an incompletely trusted environment. 378. Springer-Verlag, 1988. SIGOPS Oper. Syst. Rev. 36, SI (Dec. 2002), 1-14. [14] Ramasubramanian, V., and Sirer, E. G. Beehive: O(1)lookup [2] Bernstein, P.A., and Goodman, N. An algorithm for performance for power-law query distributions in peer-to- concurrency control and recovery in replicated distributed peer overlays. In Proceedings of the 1st Conference on databases. ACM Trans. on Database Systems, 9(4):596-615, Symposium on Networked Systems Design and December 1984 Implementation, San Francisco, CA, March 29 - 31, 2004. [3] Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, [15] Reiher, P., Heidemann, J., Ratner, D., Skinner, G., and D. A., Burrows, M., Chandra, T., Fikes, A., and Gruber, R. Popek, G. 1994. Resolving file conflicts in the Ficus file E. 2006. Bigtable: a distributed storage system for structured system. In Proceedings of the USENIX Summer 1994 data. In Proceedings of the 7th Conference on USENIX Technical Conference on USENIX Summer 1994 Technical Symposium on Operating Systems Design and Conference - Volume 1 (Boston, Massachusetts, June 06 - 10, Implementation - Volume 7 (Seattle, WA, November 06 - 08, 1994). USENIX Association, Berkeley, CA, 12-12.. 2006). USENIX Association, Berkeley, CA, 15-15. [16] Rowstron, A., and Druschel, P. Pastry: Scalable, [4] Douceur, J. R. and Bolosky, W. J. 2000. Process-based decentralized object location and routing for large-scale peer- regulation of low-importance processes. SIGOPS Oper. Syst. to-peer systems. Proceedings of Middleware, pages 329-350, Rev. 34, 2 (Apr. 2000), 26-27. November, 2001. [5] Fox, A., Gribble, S. D., Chawathe, Y., Brewer, E. A., and [17] Rowstron, A., and Druschel, P. Storage management and Gauthier, P. 1997. Cluster-based scalable network services. caching in PAST, a large-scale, persistent peer-to-peer In Proceedings of the Sixteenth ACM Symposium on storage utility. Proceedings of Symposium on Operating Operating Systems Principles (Saint Malo, France, October Systems Principles, October 2001. 05 - 08, 1997). W. M. Waite, Ed. SOSP '97. ACM Press, New York, NY, 78-91. [18] Saito, Y., Frølund, S., Veitch, A., Merchant, A., and Spence, S. 2004. FAB: building distributed enterprise disk arrays [6] Ghemawat, S., Gobioff, H., and Leung, S. 2003. The Google from commodity components. SIGOPS Oper. Syst. Rev. 38, 5 file system. In Proceedings of the Nineteenth ACM (Dec. 2004), 48-58. Symposium on Operating Systems Principles (Bolton Landing, NY, USA, October 19 - 22, 2003). SOSP '03. ACM [19] Satyanarayanan, M., Kistler, J.J., Siegel, E.H. Coda: A Press, New York, NY, 29-43. Resilient Distributed File System. IEEE Workshop on Workstation Operating Systems, Nov. 1987. [7] Gray, J., Helland, P., O'Neil, P., and Shasha, D. 1996. The dangers of replication and a solution. In Proceedings of the [20] Stoica, I., Morris, R., Karger, D., Kaashoek, M. F., and 1996 ACM SIGMOD international Conference on Balakrishnan, H. 2001. Chord: A scalable peer-to-peer Management of Data (Montreal, Quebec, Canada, June 04 - lookup service for internet applications. In Proceedings of 06, 1996). J. Widom, Ed. SIGMOD '96. ACM Press, New the 2001 Conference on Applications, Technologies, York, NY, 173-182. Architectures, and Protocols For Computer Communications (San Diego, California, United States). SIGCOMM '01. [8] Gupta, I., Chandra, T. D., and Goldszmidt, G. S. 2001. On ACM Press, New York, NY, 149-160. scalable and efficient distributed failure detectors. In Proceedings of the Twentieth Annual ACM Symposium on 219 209 

16 .[21] Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., [23] Weatherspoon, H., Eaton, P., Chun, B., and Kubiatowicz, J. Spreitzer, M. J., and Hauser, C. H. 1995. Managing update 2007. Antiquity: exploiting a secure log for wide-area conflicts in Bayou, a weakly connected replicated storage distributed storage. SIGOPS Oper. Syst. Rev. 41, 3 (Jun. system. In Proceedings of the Fifteenth ACM Symposium on 2007), 371-384. Operating Systems Principles (Copper Mountain, Colorado, [24] Welsh, M., Culler, D., and Brewer, E. 2001. SEDA: an United States, December 03 - 06, 1995). M. B. Jones, Ed. architecture for well-conditioned, scalable internet services. SOSP '95. ACM Press, New York, NY, 172-182. In Proceedings of the Eighteenth ACM Symposium on [22] Thomas, R. H. A majority consensus approach to Operating Systems Principles (Banff, Alberta, Canada, concurrency control for multiple copy databases. ACM October 21 - 24, 2001). SOSP '01. ACM Press, New York, Transactions on Database Systems 4 (2): 180-209, 1979. NY, 230-243. 220 210