Reliability at massive scale is one of the biggest
challenges we face at Amazon.com, one of the largest e-commerce
the world; even the slightest outage has significant financial
impacts customer trust. The Amazon.com platform, which provides services
many web sites worldwide, is implemented on top of an infrastructure of
thousands of servers and network components located in many datacenters
the world. At this scale, small and large components fail continuously
way persistent state is managed in the face of these failures drives the
reliability and scalability of the software systems.
This paper presents the design and implementation of Dynamo,
a highly available key-value storage system that some of Amazon’s core
use to provide an “always-on” experience. To achieve this level of
availability, Dynamo sacrifices consistency under certain failure
makes extensive use of object versioning and application-assisted
resolution in a manner that provides a novel interface for developers to
Amazon runs a world-wide e-commerce platform that serves
tens of millions customers at peak times using tens of thousands of
located in many data centers around the world. There are strict
requirements on Amazon’s platform in terms of performance, reliability
efficiency, and to support continuous growth the platform needs to be
scalable. Reliability is one of the most important requirements because
the slightest outage has significant financial consequences and impacts
customer trust. In addition, to support continuous growth, the platform
to be highly scalable.
One of the lessons our organization has learned from
operating Amazon’s platform is that the reliability and scalability of a
is dependent on how its application state is managed. Amazon uses a
decentralized, loosely coupled, service oriented architecture consisting
of services. In this environment there is a particular need for storage
technologies that are always available. For example, customers should be
to view and add items to their shopping cart even if disks are failing,
routes are flapping, or data centers are being destroyed by tornados.
Therefore, the service responsible for managing shopping carts requires
can always write to and read from its data store, and that its data
needs to be
available across multiple data centers.
Dealing with failures in an infrastructure comprised of
millions of components is our standard mode of operation; there are
small but significant number of server and network components that are
at any given time. As such Amazon’s software systems need to be
a manner that treats failure handling as the normal case without
availability or performance.
To meet the reliability and scaling needs, Amazon has
developed a number of storage technologies, of which the Amazon Simple
Service (also available outside of Amazon and known as Amazon S3), is
the best known. This paper presents the design and implementation of
another highly available and scalable distributed data store built for
platform. Dynamo is used to manage the state of services that have very
reliability requirements and need tight control over the tradeoffs
availability, consistency, cost-effectiveness and performance. Amazon’s
platform has a very diverse set of applications with different storage
requirements. A select set of applications requires a storage technology
is flexible enough to let application designers configure their data
appropriately based on these tradeoffs to achieve high availability and
guaranteed performance in the most cost effective manner.
There are many services on Amazon’s platform that only need
access to a data store. For many services, such as those that provide
lists, shopping carts, customer preferences, session management, sales
product catalog, the common pattern of using a relational database would
to inefficiencies and limit scale and availability. Dynamo provides a
primary-key only interface to meet the requirements of these
Dynamo uses a synthesis of well known techniques to achieve
scalability and availability: Data is partitioned and replicated using
consistent hashing , and consistency is facilitated by object
The consistency among replicas during updates is maintained by a
technique and a decentralized replica synchronization protocol. Dynamo
a gossip based distributed failure detection and membership protocol.
a completely decentralized system with minimal need for manual
Storage nodes can be added and removed from Dynamo without requiring any
partitioning or redistribution.
In the past year, Dynamo has been the underlying storage
technology for a number of the core services in Amazon’s e-commerce
It was able to scale to extreme peak loads efficiently without any
during the busy holiday shopping season. For example, the service that
maintains shopping cart (Shopping Cart Service) served tens of millions
requests that resulted in well over 3 million checkouts in a single day
service that manages session state handled hundreds of thousands of
concurrently active sessions.
The main contribution of this work for the research
community is the evaluation of how different techniques can be combined
provide a single highly-available system. It demonstrates that an
storage system can be used in production with demanding applications. It
provides insight into the tuning of these techniques to meet the
of production systems with very strict performance demands.
The paper is structured as follows. Section 2 presents the
background and Section 3 presents the related work. Section 4 presents
system design and Section 5 describes the implementation. Section 6
experiences and insights gained by running Dynamo in production and
concludes the paper. There are a number of places in this paper where
additional information may have been appropriate but where protecting
business interests require us to reduce some level of detail. For this
the intra- and inter-datacenter latencies in section 6, the absolute
rates in section 6.2 and outage lengths and workloads in section 6.3 are
provided through aggregate measures instead of absolute details.
Amazon’s e-commerce platform is composed of hundreds of
services that work in concert to deliver functionality ranging from
recommendations to order fulfillment to fraud detection. Each service is
exposed through a well defined interface and is accessible over the
These services are hosted in an infrastructure that consists of tens of
of servers located across many data centers world-wide. Some of these
are stateless (i.e., services which aggregate responses from other
and some are stateful (i.e., a service that generates its response by
business logic on its state stored in persistent store).
Traditionally production systems store their state in
relational databases. For many of the more common usage patterns of
persistence, however, a relational database is a solution that is far
ideal. Most of these services only store and retrieve data by primary
do not require the complex querying and management functionality offered
by an RDBMS.
This excess functionality requires expensive hardware and highly skilled
personnel for its operation, making it a very inefficient solution. In
addition, the available replication technologies are limited and
choose consistency over availability. Although many advances have been
the recent years, it is still not easy to scale-out databases or use
partitioning schemes for load balancing.
This paper describes Dynamo, a highly available data storage
technology that addresses the needs of these important classes of
Dynamo has a simple key/value interface, is highly available with a
defined consistency window, is efficient in its resource usage, and has a
simple scale out scheme to address growth in data set size or request
service that uses Dynamo runs its own Dynamo instances.
2.1 System Assumptions and Requirements
The storage system for this class of services has the
Query Model: simple read and write operations to a
data item that is uniquely identified by a key. State is stored as
objects (i.e., blobs) identified by unique keys. No operations span
data items and there is no need for relational schema. This requirement
based on the observation that a significant portion of Amazon’s services
work with this simple query model and do not need any relational schema.
targets applications that need to store objects that are relatively
(usually less than 1 MB).
ACID Properties: ACID (Atomicity, Consistency,
Isolation, Durability) is a set of properties that guarantee that
transactions are processed reliably. In the context of databases, a
logical operation on the data is called a transaction. Experience at
shown that data stores that provide ACID guarantees tend to have poor
availability. This has been widely acknowledged by both the industry and
academia . Dynamo targets applications that operate with weaker
(the “C” in ACID) if this results in high availability. Dynamo does not
any isolation guarantees and permits only single key updates.
Efficiency: The system needs to function on a
commodity hardware infrastructure. In Amazon’s platform, services have
stringent latency requirements which are in general measured at the
percentile of the distribution. Given that state access plays a crucial
service operation the storage system must be capable of meeting such
SLAs (see Section 2.2 below). Services must be able to configure Dynamo
that they consistently achieve their latency and throughput
tradeoffs are in performance, cost efficiency, availability, and
Other Assumptions: Dynamo is used only by Amazon’s internal
services. Its operation environment is assumed to be non-hostile and
no security related requirements such as authentication and
Moreover, since each service uses its distinct instance of Dynamo, its
design targets a scale of up to hundreds of storage hosts. We will
scalability limitations of Dynamo and possible scalability related
2.2 Service Level Agreements (SLA)
To guarantee that the application can deliver its
functionality in a bounded time, each and every dependency in the
needs to deliver its functionality with even tighter bounds. Clients and
services engage in a Service Level Agreement (SLA), a formally
contract where a client and a service agree on several system-related
characteristics, which most prominently include the client’s expected
rate distribution for a particular API and the expected service latency
those conditions. An example of a simple SLA is a service guaranteeing
will provide a response within 300ms for 99.9% of its requests for a
load of 500 requests per second.
In Amazon’s decentralized service oriented infrastructure, SLAs play
role. For example a page request to one of the e-commerce sites
the rendering engine to construct its response by sending requests to
services. These services often have multiple dependencies, which
other services, and as such it is not uncommon for the call graph of an
application to have more than one level. To ensure that the page
engine can maintain a clear bound on page delivery each service within
chain must obey its performance contract.
Figure 1 shows an abstract view of the architecture of
Amazon’s platform, where dynamic web content is generated by page
components which in turn query many other services. A service can use
data stores to manage its state and these data stores are only
within its service boundaries. Some services act as aggregators by using
several other services to produce a composite response. Typically, the
aggregator services are stateless, although they use extensive caching.
Figure 1: Service-oriented architecture of Amazon’s platform.
A common approach in the industry for forming a performance
oriented SLA is to describe it using average, median and expected
Amazon we have found that these metrics are not good enough if the goal
build a system where all customers have a good experience, rather
the majority. For example if extensive personalization techniques are
used then customers with longer histories require more processing which
performance at the high-end of the distribution. An SLA stated in terms
or median response times will not address the performance of this
customer segment. To address this issue, at Amazon, SLAs are expressed
measured at the 99.9th percentile of the distribution. The choice
for 99.9% over an even higher percentile has been made based on a
analysis which demonstrated a significant increase in cost to improve
performance that much. Experiences with Amazon’s production systems have
that this approach provides a better overall experience compared to
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
on performance from the perspective of the customers’ experience. Many
report on averages, so these are included where it makes sense for
purposes. Nevertheless, Amazon’s engineering and optimization efforts
are not focused
on averages. Several techniques, such as the load balanced selection of
coordinators, are purely targeted at controlling performance at the
Storage systems often play an important role in establishing
a service’s SLA, especially if the business logic is relatively
is the case for many Amazon services. State management then becomes the
component of a service’s SLA. One of the main design considerations for
to give services control over their system properties, such as
consistency, and to let services make their own tradeoffs between
functionality, performance and cost-effectiveness.
2.3 Design Considerations
Data replication algorithms used in commercial
systems traditionally perform synchronous replica coordination in order
provide a strongly consistent data access interface. To achieve this
consistency, these algorithms are forced to tradeoff the availability of
data under certain failure scenarios. For instance, rather than dealing
the uncertainty of the correctness of an answer, the data is made
until it is absolutely certain that it is correct. From the very early
replicated database works, it is well known that when dealing with the
possibility of network failures, strong consistency and high data
cannot be achieved simultaneously [2, 11]. As such systems and
need to be aware which properties can be achieved under which
For systems prone to server and network
failures, availability can be increased by using optimistic replication
techniques, where changes are allowed to propagate to replicas in the
background, and concurrent, disconnected work is tolerated. The
this approach is that it can lead to conflicting changes which must be
and resolved. This process of conflict resolution introduces two
when to resolve them and who resolves them. Dynamo is designed to be an
consistent data store; that is all updates reach all replicas
An important design consideration is to decide when
to perform the process of resolving update conflicts, i.e., whether
should be resolved during reads or writes. Many traditional data
stores execute conflict resolution during writes and keep the read
simple . In such systems, writes may be rejected if the data store
reach all (or a majority of) the replicas at a given time. On the other
Dynamo targets the design space of an “always writeable” data store
data store that is highly available for writes). For a number of Amazon
rejecting customer updates could result in a poor customer experience.
instance, the shopping cart service must allow customers to add and
items from their shopping cart even amidst network and server failures.
requirement forces us to push the complexity of conflict resolution to
reads in order to ensure that writes are never rejected.
The next design choice is who
performs the process of conflict resolution. This can be done by the
data store or the application. If conflict resolution is done by the
store, its choices are rather limited. In such cases, the data store can
use simple policies, such as “last write wins” , to resolve
updates. On the other hand, since the application is aware of the data
can decide on the conflict resolution method that is best suited for its
experience. For instance, the application that maintains customer
can choose to “merge” the conflicting versions and return a single
shopping cart. Despite this flexibility, some application developers may
want to write their own conflict resolution mechanisms and choose to
push it down to the data store, which in turn chooses a simple policy
“last write wins”.
Other key principles embraced in the design
Incremental scalability: Dynamo
should be able to scale out one storage host (henceforth, referred to as
“node”) at a time, with minimal impact on both
operators of the system and
the system itself.
Symmetry: Every node in Dynamo should
have the same set of responsibilities as its peers; there should be no
distinguished node or nodes that take special roles or extra set of
responsibilities. In our experience, symmetry simplifies the process of
provisioning and maintenance.
Decentralization: An extension of
symmetry, the design should favor decentralized peer-to-peer techniques
centralized control. In the past, centralized control has resulted in
and the goal is to avoid it as much as possible. This leads to a
scalable, and more available system.
Heterogeneity: The system needs to be able to
exploit heterogeneity in the infrastructure it runs on. e.g. the work
distribution must be proportional to the capabilities of the individual
servers. This is essential in adding new nodes with higher capacity
having to upgrade all hosts at once.
3. Related Work
3.1 Peer to Peer Systems
There are several peer-to-peer (P2P) systems that have
looked at the problem of data storage and distribution. The first
P2P systems, such as Freenet
and Gnutella, were predominantly
used as file sharing systems. These were examples of unstructured P2P
where the overlay links between peers were established arbitrarily. In
networks, a search query is usually flooded through the network to find
peers as possible that share the data. P2P systems evolved to the next
into what is widely known as structured P2P networks. These networks
globally consistent protocol to ensure that any node can efficiently
search query to some peer that has the desired data. Systems like Pastry
Chord  use routing mechanisms to ensure that queries can be answered
a bounded number of hops. To reduce the additional latency introduced by
multi-hop routing, some P2P systems (e.g., ) employ O(1) routing
peer maintains enough routing information locally so that it can route
(to access a data item) to the appropriate peer within a constant number
Various storage systems, such as Oceanstore  and PAST 
were built on top of these routing overlays. Oceanstore provides a
transactional, persistent storage service that supports serialized
widely replicated data. To allow for concurrent updates while avoiding
the problems inherent with wide-area locking, it uses an update model
conflict resolution. Conflict resolution was introduced in  to
number of transaction aborts. Oceanstore resolves conflicts by
series of updates, choosing a total order among them, and then applying
atomically in that order. It is built for an environment where the data
replicated on an untrusted infrastructure. By comparison, PAST provides a
simple abstraction layer on top of Pastry for persistent and immutable
It assumes that the application can build the necessary storage
as mutable files) on top of it.
3.2 Distributed File Systems and Databases
Distributing data for performance, availability and
durability has been widely studied in the file system and database
community. Compared to P2P storage systems that only support flat
distributed file systems typically support hierarchical namespaces.
like Ficus  and Coda  replicate files for high availability at
expense of consistency. Update conflicts are typically managed using
specialized conflict resolution procedures. The Farsite system  is a
distributed file system that does not use any centralized server like
Farsite achieves high availability and scalability using replication.
Google File System  is another distributed file system built for
state of Google’s internal applications. GFS uses a simple design with a
master server for hosting the entire metadata and where the data is
chunks and stored in chunkservers. Bayou is a distributed relational
system that allows disconnected operations and provides eventual data
Among these systems, Bayou,
Coda and Ficus allow disconnected operations and are resilient to issues
as network partitions and outages. These systems differ on their
resolution procedures. For instance, Coda and Ficus perform system level
conflict resolution and Bayou allows application level resolution. All
however, guarantee eventual consistency. Similar to these systems,
allows read and write operations to continue even during network
resolves updated conflicts using different conflict resolution
block storage systems like FAB  split large size objects into
and stores each block in a highly available manner. In comparison to
systems, a key-value store is more suitable in this case because: (a) it
intended to store relatively small objects (size < 1M) and (b)
stores are easier to configure on a per-application basis. Antiquity is a
wide-area distributed storage system designed to handle multiple server
failures . It uses a secure log to preserve data integrity,
log on multiple servers for durability, and uses Byzantine fault
protocols to ensure data consistency. In contrast to Antiquity, Dynamo
focus on the problem of data integrity and security and is built for a
environment. Bigtable is a distributed storage system for managing
data. It maintains a sparse, multi-dimensional sorted map and allows
applications to access their data using multiple attributes .
Bigtable, Dynamo targets applications that require only key/value access
primary focus on high availability where updates are not rejected even
wake of network partitions or server failures.
Traditional replicated relational database systems focus on
the problem of guaranteeing strong consistency to replicated data.
strong consistency provides the application writer a convenient
model, these systems are limited in scalability and availability .
systems are not capable of handling network partitions because they
strong consistency guarantees.
Dynamo differs from the aforementioned decentralized storage
systems in terms of its target requirements. First, Dynamo is targeted
at applications that need an “always writeable” data store where no
rejected due to failures or concurrent writes. This is a crucial
for many Amazon applications. Second, as noted earlier, Dynamo is built
infrastructure within a single administrative domain where all nodes are
assumed to be trusted. Third, applications that use Dynamo do not
support for hierarchical namespaces (a norm in many file systems) or
relational schema (supported by traditional databases). Fourth, Dynamo
for latency sensitive applications that require at least 99.9% of read
write operations to be performed within a few hundred milliseconds. To
these stringent latency requirements, it was imperative for us to avoid
requests through multiple nodes (which is the typical design adopted by
distributed hash table systems such as Chord and Pastry). This is
routing increases variability in response times, thereby increasing the
at higher percentiles. Dynamo can be characterized as a zero-hop DHT,
each node maintains enough routing information locally to route a
the appropriate node directly.
The architecture of a storage system that needs to operate
in a production setting is complex. In addition to the actual data
the system needs to have scalable and robust solutions for load
membership and failure detection, failure recovery, replica
overload handling, state transfer, concurrency and job scheduling,
request routing, system monitoring and alarming, and configuration
Describing the details of each of the solutions is not possible, so this
focuses on the core distributed systems techniques used in Dynamo:
partitioning, replication, versioning, membership, failure handling and
Table 1 presents a summary of the list of techniques Dynamo uses and
Table 1: Summary of techniques used in Dynamo and
High Availability for writes
Vector clocks with reconciliation during reads
Version size is decoupled from update rates.
Handling temporary failures
Sloppy Quorum and hinted handoff
Provides high availability and durability guarantee
when some of the replicas are not available.
Recovering from permanent failures
Anti-entropy using Merkle trees
Synchronizes divergent replicas in the background.
Membership and failure detection
Gossip-based membership protocol and failure
Preserves symmetry and avoids having a centralized
registry for storing membership and node liveness information.
4.1 System Interface
Dynamo stores objects associated with a key through a simple
interface; it exposes two operations: get() and put(). The get(key)
operation locates the object replicas associated with the key
storage system and returns a single object or a list of objects
conflicting versions along with a context. The put(key,
object) operation determines where the replicas of the object should
placed based on the associated key, and writes the replicas to
disk. The context encodes system metadata about the object that
opaque to the caller and includes information such as the version of the
object. The context information is stored along with the object so that
system can verify the validity of the context object supplied in the put
Dynamo treats both the key and the object supplied by the
caller as an opaque array of bytes. It applies a MD5 hash on the key to
a 128-bit identifier, which is used to determine the storage nodes that
responsible for serving the key.
4.2 Partitioning Algorithm
One of the key design requirements for Dynamo
is that it must scale incrementally. This requires a mechanism to
partition the data over the set of nodes (i.e., storage hosts) in the
partitioning scheme relies on consistent hashing to distribute the load
multiple storage hosts. In consistent hashing , the output
range of a hash function is treated as a fixed circular space or “ring”
the largest hash value wraps around to the smallest hash value). Each
the system is assigned a random value within this space which represents
“position” on the ring. Each data item identified by a key is assigned
node by hashing the data item’s key to yield its position on the ring,
walking the ring clockwise to find the first node with a position larger
the item’s position. Thus, each node becomes responsible for the region
ring between it and its predecessor node on the ring. The principle
of consistent hashing is that departure or arrival of a node only
immediate neighbors and other nodes remain unaffected.
The basic consistent hashing algorithm presents some
challenges. First, the random position assignment of each node on
the ring leads to non-uniform data and load distribution. Second, the
basic algorithm is oblivious to the heterogeneity in the performance of
address these issues, Dynamo uses a variant of consistent hashing
the one used in [10, 20]): instead of mapping a node to a single point
circle, each node gets assigned to multiple points in the ring. To this
Dynamo uses the concept of “virtual nodes”. A virtual node looks like a
node in the system, but each node can be responsible for more than one
node. Effectively, when a new node is added to the system, it is
multiple positions (henceforth, “tokens”) in the ring. The process of
fine-tuning Dynamo’s partitioning scheme is discussed in Section 6.
Using virtual nodes has the following advantages:
If a node becomes unavailable (due to failures or
routine maintenance), the load handled by this node is evenly dispersed
the remaining available nodes.
When a node becomes available again, or a new node
is added to the system, the newly available node accepts a roughly
amount of load from each of the other available nodes.
The number of virtual nodes that a node is responsible
can decided based on its capacity, accounting for heterogeneity in the
To achieve high availability and durability, Dynamo
replicates its data on multiple hosts. Each data item is replicated at N
where N is a parameter configured “per-instance”. Each key, k,
is assigned to a coordinator node (described in the previous section).
coordinator is in charge of the replication of the data items that fall
its range. In addition to locally storing each key within its range, the
coordinator replicates these keys at the N-1 clockwise successor nodes
ring. This results in a system where each node is responsible for the
the ring between it and its Nth predecessor. In Figure 2, node B
the key k at nodes C and D in addition to storing it locally.
will store the keys that fall in the ranges (A, B], (B, C], and (C, D].
Figure 2: Partitioning and replication of keys in Dynamo ring.
The list of nodes that is responsible for storing a
particular key is called the preference list. The system is
as will be explained in Section 4.8, so that every node in the system
determine which nodes should be in this list for any particular key. To
account for node failures, preference list contains more than N nodes.
that with the use of virtual nodes, it is possible that the first
N successor positions for a particular key may be owned by less than N
physical nodes (i.e. a node may hold more than one of the first N
To address this, the preference list for a key is constructed by
positions in the ring to ensure that the list contains only distinct
4.4 Data Versioning
Dynamo provides eventual consistency, which allows for
updates to be propagated to all replicas asynchronously. A put() call
to its caller before the update has been applied at all the replicas,
result in scenarios where a subsequent get() operation may return an
that does not have the latest updates.. If there are no failures then
a bound on the update propagation times. However, under certain failure
scenarios (e.g., server outages or network partitions), updates may not
at all replicas for an extended period of time.
There is a category of applications in Amazon’s
platform that can tolerate such inconsistencies and can be constructed
operate under these conditions. For example, the shopping cart
that an “Add to Cart” operation can never be
forgotten or rejected. If the most recent state of the cart is
a user makes changes to an older version of the cart, that change is
meaningful and should be preserved. But at the same time it shouldn’t
the currently unavailable state of the cart, which itself may contain
that should be preserved. Note that both “add to cart” and “delete
from cart” operations are translated into put requests to Dynamo.
a customer wants to add an item to (or remove from) a shopping cart and
latest version is not available, the item is added to (or removed from)
version and the divergent versions are reconciled later.
In order to provide this kind of guarantee, Dynamo treats
the result of each modification as a new and immutable version of the
allows for multiple versions of an object to be present in the system at
same time. Most of the time, new versions subsume the previous
the system itself can determine the authoritative version (syntactic
reconciliation). However, version branching may happen, in the presence
failures combined with concurrent updates, resulting in conflicting
an object. In these cases, the system cannot reconcile the multiple
the same object and the client must perform the reconciliation in order
multiple branches of data evolution back into one (semantic
typical example of a collapse operation is “merging” different versions
customer’s shopping cart. Using this reconciliation mechanism, an “add
operation is never lost. However, deleted items can resurface.
It is important to understand that certain failure modes can
potentially result in the system having not just two but several
the same data. Updates in the presence of network partitions and node
can potentially result in an object having distinct version
which the system will need to reconcile in the future. This requires us
design applications that explicitly acknowledge the possibility of
versions of the same data (in order to never lose any updates).
Dynamo uses vector clocks  in order to capture causality
between different versions of the same object. A vector clock is
list of (node, counter) pairs. One vector clock is associated with every
of every object. One can determine whether two versions of an object are
parallel branches or have a causal ordering, by examine their vector
clocks. If the counters on the first object’s clock are
less-than-or-equal to all
of the nodes in the second clock, then the first is an
ancestor of the second and can be forgotten. Otherwise, the two changes
considered to be in conflict and require reconciliation.
In Dynamo, when a client wishes to update an object, it must
specify which version it is updating. This is done by passing the
obtained from an earlier read operation, which contains the vector clock
information. Upon processing a read request, if Dynamo has access to
branches that cannot be syntactically reconciled, it will return all the
objects at the leaves, with the corresponding version information in the
context. An update using this context is considered to have reconciled
divergent versions and the branches are collapsed into a single new
Figure 3: Version evolution of an object over time.
To illustrate the use of vector clocks, let us consider the
example shown in Figure 3. A client writes a new object. The node (say
that handles the write for this key increases its sequence number and
to create the data's vector clock. The system now has the object D1 and
associated clock [(Sx, 1)]. The client updates the object. Assume the
handles this request as well. The system now also has object D2 and its
associated clock [(Sx, 2)]. D2 descends from D1 and therefore
over-writes D1, however there may be replicas of D1 lingering at nodes
have not yet seen D2. Let us assume that the same client updates the
again and a different server (say Sy) handles the request. The system
data D3 and its associated clock [(Sx, 2), (Sy, 1)].
Next assume a different client reads D2 and then tries to
update it, and another node (say Sz) does the write. The system now has
(descendant of D2) whose version clock is [(Sx, 2), (Sz, 1)]. A node
aware of D1 or D2 could determine, upon receiving D4 and its clock, that
D2 are overwritten by the new data and can be garbage collected. A node
aware of D3 and receives D4 will find that there is no causal relation
them. In other words, there are changes in D3 and D4 that are not
reflected in each
other. Both versions of the data must be kept and presented to a client
read) for semantic reconciliation.
Now assume some client reads both D3 and D4 (the context
will reflect that both values were found by the read). The read's
context is a
summary of the clocks of D3 and D4, namely [(Sx, 2), (Sy, 1), (Sz, 1)].
client performs the reconciliation and node Sx coordinates the write, Sx
update its sequence number in the clock. The new data D5 will have the
following clock: [(Sx, 3), (Sy, 1), (Sz, 1)].
A possible issue with vector clocks is that the size of
vector clocks may grow if many servers coordinate the writes to an
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
server failures, write requests may be handled by nodes that are not in
N nodes in the preference list causing the size of vector clock to grow.
these scenarios, it is desirable to limit the size of vector clock. To
end, Dynamo employs the following clock truncation scheme: Along with
(node, counter) pair, Dynamo stores a timestamp that indicates the last
the node updated the data item. When the number of (node, counter) pairs
vector clock reaches a threshold (say 10), the oldest pair is removed
clock. Clearly, this truncation scheme can lead to inefficiencies in
reconciliation as the descendant relationships cannot be derived
However, this problem has not surfaced in production and therefore this
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
operations are performed in a failure-free environment and in the
section we describe how read and write operations are executed during
Both get and put operations are invoked using Amazon’s
infrastructure-specific request processing framework over HTTP. There
strategies that a client can use to select a node: (1) route its request
through a generic load balancer that will select a node based on load
information, or (2) use a partition-aware client library that routes
directly to the appropriate coordinator nodes. The advantage of the
approach is that the client does not have to link any code specific to
in its application, whereas the second strategy can achieve lower
it skips a potential forwarding step.
A node handling a read or write operation is
known as the coordinator. Typically, this is the
first among the top N nodes in the preference list. If the requests are
received through a load balancer, requests to access a key may be routed
random node in the ring. In this scenario, the node that receives the
not coordinate it if the node is not in the top N of the requested key’s
list. Instead, that node will forward the request to the first among the
nodes in the preference list.
Read and write operations involve the first N
healthy nodes in the preference list, skipping over those that are down
inaccessible. When all nodes are healthy, the top N nodes in a key’s
list are accessed. When there are node failures or network partitions,
that are lower ranked in the preference list are accessed.
To maintain consistency among its replicas,
Dynamo uses a consistency protocol similar to those used in quorum
This protocol has two key configurable values: R and W. R is the minimum
of nodes that must participate in a successful read operation. W is the
number of nodes that must participate in a successful write operation.
R and W such that R + W > N yields a quorum-like system. In this
latency of a get (or put) operation is dictated by the slowest of the R
(or W) replicas.
For this reason, R and W are usually configured to be less than N, to
Upon receiving a put() request for a key, the
coordinator generates the vector clock for the new version and writes
version locally. The coordinator then sends the new version (along with
vector clock) to the N highest-ranked reachable nodes. If at least W-1
respond then the write is considered successful.
Similarly, for a get() request, the
coordinator requests all existing versions of data for that key from the
highest-ranked reachable nodes in the preference list for that key, and
waits for R responses before returning the result to the client.
If the coordinator ends up gathering multiple
versions of the data, it returns all the versions it deems to be
unrelated. The divergent versions are then reconciled and the reconciled
version superseding the current versions is written back.
4.6 Handling Failures: Hinted Handoff
If Dynamo used a traditional quorum approach
it would be unavailable during server failures and network partitions,
would have reduced durability even under the simplest of failure
remedy this it does not enforce strict quorum membership and instead it
“sloppy quorum”; all read and write operations are performed on the
first N healthy
nodes from the preference list, which may not always be the first N
nodes encountered while walking the consistent hashing ring.
Consider the example of Dynamo configuration given in Figure
2 with N=3. In this example, if node A is temporarily down or
during a write operation then a replica that would normally have lived
will now be sent to node D. This is done to maintain the desired
and durability guarantees. The replica sent to D will have a hint in its
metadata that suggests which node was the intended recipient of the
this case A). Nodes that receive hinted replicas will keep them in a
database that is scanned periodically. Upon detecting that A has
recovered, D will
attempt to deliver the replica to A. Once the transfer succeeds, D may
object from its local store without decreasing the total number of
Using hinted handoff, Dynamo ensures that the
read and write operations are not failed due to temporary node or
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 single node in
system has durably written the key it to its local store. Thus, the
request is only rejected if all nodes in the system are unavailable.
in practice, most Amazon services in production set a higher W to meet
desired level of durability. A more detailed discussion of configuring
N, R and
W follows in section 6.
It is imperative that a highly available storage system be
capable of handling the failure of an entire data center(s). Data center
failures happen due to power outages, cooling failures, network
natural disasters. Dynamo is configured such that each object is
across multiple data centers. In essence, the preference list of a key
constructed such that the storage nodes are spread across multiple data
centers. These datacenters are connected through high speed network
scheme of replicating across multiple datacenters allows us to handle
data center failures without a data outage.
4.7 Handling permanent failures: Replica synchronization
Hinted handoff works best if the system membership churn is
low and node failures are transient. There are scenarios under which
replicas become unavailable before they can be returned to the original
node. To handle this and other threats to durability, Dynamo implements
anti-entropy (replica synchronization) protocol to keep the replicas
To detect the inconsistencies between replicas faster and to
minimize the amount of transferred data, Dynamo uses Merkle trees . A
Merkle tree is a hash tree where leaves are hashes of the values of
keys. Parent nodes higher in the tree are hashes of their respective
The principal advantage of Merkle tree is that each branch of the tree
checked independently without requiring nodes to download the entire
tree or the
entire data set. Moreover, Merkle trees help in reducing the amount of
that needs to be transferred while checking for inconsistencies among
For instance, if the hash values of the root of two trees are equal,
values of the leaf nodes in the tree are equal and the nodes require no
synchronization. If not, it implies that the values of some replicas are
different. In such cases, the nodes may exchange the hash values of
the process continues until it reaches the leaves of the trees, at which
the hosts can identify the keys that are “out of sync”. Merkle trees
the amount of data that needs to be transferred for synchronization and
number of disk reads performed during the anti-entropy process.
Dynamo uses Merkle trees for anti-entropy as follows: Each node
maintains a separate Merkle tree for each key range (the set of keys
a virtual node) it hosts. This allows nodes to compare whether the keys
a key range are up-to-date. In this scheme, two nodes exchange the root
of the Merkle
tree corresponding to the key ranges that they host in common.
using the tree traversal scheme described above the nodes determine if
have any differences and perform the appropriate synchronization action.
disadvantage with this scheme is that many key ranges change when a node
or leaves the system thereby requiring the tree(s) to be recalculated.
issue is addressed, however, by the refined partitioning scheme
4.8 Membership and Failure Detection
4.8.1 Ring Membership
In Amazon’s environment node
outages (due to failures and maintenance tasks) are often transient but
last for extended intervals. A node outage rarely signifies a permanent
departure and therefore should not result in rebalancing of the
assignment or repair of the unreachable replicas. Similarly, manual
could result in the unintentional startup of new Dynamo nodes. For
reasons, it was deemed appropriate to use an explicit mechanism to
addition and removal of nodes from a Dynamo ring. An administrator uses a
command line tool or a browser to connect to a Dynamo node and issue a
membership change to join a node to a ring or remove a node from a ring.
node that serves the request writes the membership change and its time
to persistent store. The membership changes form a history because nodes
removed and added back multiple times. A gossip-based protocol
membership changes and maintains an eventually consistent view of
node contacts a peer chosen at random every second and the two nodes
reconcile their persisted membership change histories.
When a node starts for the first
time, it chooses its set of tokens (virtual nodes in the consistent hash
and maps nodes to their respective token sets. The mapping is persisted
and initially contains only the local node and token set. The mappings
at different Dynamo nodes are reconciled during the same communication
that reconciles the membership change histories. Therefore, partitioning
placement information also propagates via the gossip-based protocol and
storage node is aware of the token ranges handled by its peers. This
each node to forward a key’s read/write operations to the right set of
4.8.2 External Discovery
The mechanism described above
could temporarily result in a logically partitioned Dynamo ring. For
the administrator could contact node A to join A to the ring, then
B to join B to the ring. In this scenario, nodes A and B would each
itself a member of the ring, yet neither would be immediately aware of
other. To prevent logical partitions, some Dynamo nodes play the role
seeds. Seeds are nodes that are discovered via an external mechanism
known to all nodes. Because all nodes eventually reconcile their
with a seed, logical partitions are highly unlikely. Seeds can be
either from static configuration or from a configuration service.
seeds are fully functional nodes in the Dynamo ring.
4.8.3 Failure Detection
Failure detection in Dynamo is
used to avoid attempts to communicate with unreachable peers during
put() operations and when transferring partitions and hinted replicas.
purpose of avoiding failed attempts at communication, a purely local
failure detection is entirely sufficient: node A may consider node B
node B does not respond to node A’s messages (even if B is responsive to
C's messages). In the presence of a steady rate of client requests
inter-node communication in the Dynamo ring, a node A quickly discovers
node B is unresponsive when B fails to respond to a message; Node A then
alternate nodes to service requests that map to B's partitions; A
retries B to check for the latter's recovery. In the absence of client
requests to drive traffic between two nodes, neither node really needs
whether the other is reachable and responsive.
Decentralized failure detection
protocols use a simple gossip-style protocol that enable each node in
system to learn about the arrival (or departure) of other nodes. For
on decentralized failure detectors and the parameters affecting their
the interested reader is referred to . Early designs of Dynamo used a
failure detector to maintain a globally consistent view of failure
it was determined that the explicit node join and leave methods obviates
need for a global view of failure state. This is because nodes are
permanent node additions and removals by the explicit node join and
methods and temporary node failures are detected by the individual nodes
they fail to communicate with others (while forwarding requests).
4.9 Adding/Removing Storage Nodes
When a new node (say X) is
added into the system, it gets assigned a number of tokens that are
scattered on the ring. For every key range that is assigned to node X,
be a number of nodes (less than or equal to N) that are currently in
handling keys that fall within its token range. Due to the allocation of
ranges to X, some existing nodes no longer have to some of their keys
nodes transfer those keys to X. Let us consider a simple bootstrapping
where node X is added to the ring shown in Figure 2 between A and B.
When X is
added to the system, it is in charge of storing keys in the ranges (F,
G], (G, A]
and (A, X]. As a consequence, nodes B, C and D no longer have to store
in these respective ranges. Therefore, nodes B, C, and D will offer to
confirmation from X transfer the appropriate set of keys. When a node
removed from the system, the reallocation of keys happens in a reverse
Operational experience has shown that this approach distributes
the load of key distribution uniformly across the storage nodes, which
important to meet the latency requirements and to ensure fast
Finally, by adding a confirmation round between the source and the
it is made sure that the destination node does not receive any duplicate
transfers for a given key range.
In Dynamo, each storage node has three main software
components: request coordination, membership and failure detection, and a
persistence engine. All these components are implemented in Java.
Dynamo’s local persistence component allows for different
storage engines to be plugged in. Engines that are in use are Berkeley
(BDB) Transactional Data Store, BDB Java Edition, MySQL, and an
in-memory buffer with persistent backing store. The main reason for
pluggable persistence component is to choose the storage engine best
an application’s access patterns. For instance, BDB can handle objects
typically in the order of tens of kilobytes whereas MySQL can handle
larger sizes. Applications choose Dynamo’s local persistence engine
based on their
object size distribution. The majority of Dynamo’s production instances
Transactional Data Store.
The request coordination component is built on top of an
event-driven messaging substrate where the message processing pipeline
into multiple stages similar to the SEDA architecture . All
are implemented using Java NIO channels. The coordinator executes the
write requests on behalf of clients by collecting data from one or more
(in the case of reads) or storing data at one or more nodes (for
client request results in the creation of a state machine on the node
received the client request. The state machine contains all the logic
identifying the nodes responsible for a key, sending the requests,
responses, potentially doing retries, processing the replies and
response to the client. Each state machine instance handles exactly one
request. For instance, a read operation implements the following state
(i) send read requests to the nodes, (ii) wait for minimum number of
responses, (iii) if too few replies were received within a given time
fail the request, (iv) otherwise gather all the data versions and
ones to be returned and (v) if versioning is enabled, perform syntactic
reconciliation and generate an opaque write context that contains the
clock that subsumes all the remaining versions. For the sake of brevity
failure handling and retry states are left out.
After the read response has been returned to the caller the state
machine waits for a small period of time to receive any outstanding
stale versions were returned in any of the responses, the coordinator
those nodes with the latest version. This process is called read
because it repairs replicas that have missed a recent update at an
opportunistic time and relieves the anti-entropy protocol from having to
As noted earlier, write requests are coordinated by one of
the top N nodes in the preference list. Although it is desirable always
the first node among the top N to coordinate the writes thereby
writes at a single location, this approach has led to uneven load
resulting in SLA violations. This is because the request load is not
distributed across objects. To counter this, any of the top N nodes in
preference list is allowed to coordinate the writes. In particular,
write usually follows a read operation, the coordinator for a write is
to be the node that replied fastest to the previous read operation which
stored in the context information of the request. This optimization
to pick the node that has the data that was read by the preceding read
thereby increasing the chances of getting “read-your-writes”
also reduces variability in the performance of the request handling
improves the performance at the 99.9 percentile.
6. Experiences & Lessons Learned
Dynamo is used by several services with different configurations.
These instances differ by their version reconciliation logic, and
quorum characteristics. The following are the main patterns in which
Business logic specific reconciliation: This is a
popular use case for Dynamo. Each data object is replicated across
nodes. In case of divergent versions, the client application performs
reconciliation logic. The shopping cart service discussed earlier is a
example of this category. Its business logic reconciles objects by
different versions of a customer’s shopping cart.
Timestamp based reconciliation: This case differs from
the previous one only in the reconciliation mechanism. In case of
versions, Dynamo performs simple timestamp based reconciliation logic of
write wins”; i.e., the object with the largest physical timestamp value
chosen as the correct version. The service that maintains customer’s
information is a good example of a service that uses this mode.
High performance read engine: While Dynamo is built to
be an “always writeable” data store, a few services are tuning its
characteristics and using it as a high performance read engine.
these services have a high read request rate and only a small number of
updates. In this configuration, typically R is set to be 1 and W to be
these services, Dynamo provides the ability to partition and replicate
data across multiple nodes thereby offering incremental scalability.
these instances function as the authoritative persistence cache for data
in more heavy weight backing stores. Services that maintain product
promotional items fit in this category.
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
performance, availability and durability. For instance, the value of N
determines the durability of each object. A typical value of N used by
users is 3.
The values of W and R impact object availability, durability
and consistency. For instance, if W is set to 1, then the system will
reject a write request as long as there is at least one node in the
can successfully process a write request. However, low values of W and R
increase the risk of inconsistency as write requests are deemed
returned to the clients even if they are not processed by a majority of
replicas. This also introduces a vulnerability window for durability
write request is successfully returned to the client even though it has
persisted at only a small number of nodes.
Traditional wisdom holds that durability and availability go
hand-in-hand. However, this is not necessarily true here. For instance,
vulnerability window for durability can be decreased by increasing W.
increase the probability of rejecting requests (thereby decreasing
availability) because more storage hosts need to be alive to process a
The common (N,R,W) configuration used by several instances
of Dynamo is (3,2,2). These values are chosen to meet the necessary
performance, durability, consistency, and availability SLAs.
All the measurements presented in this section were taken on
a live system operating with a configuration of (3,2,2) and running a
nodes with homogenous hardware configurations. As mentioned earlier,
instance of Dynamo contains nodes that are located in multiple
These datacenters are typically connected through high speed network
that to generate a successful get (or put) response R (or W) nodes need
to the coordinator. Clearly, the network latencies between datacenters
the response time and the nodes (and their datacenter locations) are
that the applications target SLAs are met.
6.1 Balancing Performance and Durability
While Dynamo’s principle design goal is to build a highly
available data store, performance is an equally important criterion in
platform. As noted earlier, to provide a consistent customer experience,
services set their performance targets at higher percentiles (such as
or 99.99th percentiles). A typical SLA required of services that use
Dynamo is that 99.9% of the read and write requests execute within
Since Dynamo is run on standard commodity hardware
components that have far less I/O throughput than high-end enterprise
providing consistently high performance for read and write operations is
task. The involvement of multiple storage nodes in read and write
makes it even more challenging, since the performance of these
operations is limited
by the slowest of the R or W replicas. Figure 4 shows the average and
percentile latencies of Dynamo’s read and write operations during a
30 days. As seen in the figure, the latencies exhibit a clear diurnal
which is a result of the diurnal pattern in the incoming request rate
there is a significant difference in request rate between the daytime
night). Moreover, the write latencies are higher than read latencies
write operations always results in disk access. Also, the 99.9th
percentile latencies are around 200 ms and are an order of magnitude
than the averages. This is because the 99.9th percentile latencies
are affected by several factors such as variability in request load,
sizes, and locality patterns.
Figure 4: Average and 99.9 percentiles of latencies for
read and write requests during our peak request season of December 2006.
intervals between consecutive ticks in the x-axis correspond to 12
follow a diurnal pattern similar to the request rate and 99.9 percentile
latencies are an order of magnitude higher than averages.
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
durability guarantees for performance. In the optimization each storage
maintains an object buffer in its main memory. Each write operation is
in the buffer and gets periodically written to storage by a writer
In this scheme, read operations first check if the requested key is
the buffer. If so, the object is read from the buffer instead of the
This optimization has resulted in lowering the 99.9th
percentile latency by a factor of 5 during peak traffic even for a very
buffer of a thousand objects (see Figure 5). Also, as seen in the
buffering smoothes out higher percentile latencies. Obviously, this
trades durability for performance. In this scheme, a server crash can
missing writes that were queued up in the buffer. To reduce the
risk, the write operation is refined to have the coordinator choose one
the N replicas to perform a “durable write”. Since the coordinator waits
for W responses, the performance of the write operation is not affected
performance of the durable write operation performed by a single
Figure 5: Comparison
of performance of 99.9th percentile latencies for buffered vs.
writes over a period of 24 hours. The intervals between consecutive
the x-axis correspond to one hour.
6.2 Ensuring Uniform Load distribution
Dynamo uses consistent hashing to partition its key space
across its replicas and to ensure uniform load distribution. A uniform
distribution can help us achieve uniform load distribution assuming the
of keys is not highly skewed. In particular, Dynamo’s design assumes
where there is a significant skew in the access distribution there are
keys in the popular end of the distribution so that the load of handling
keys can be spread across the nodes uniformly through partitioning. This
section discusses the load imbalance seen in Dynamo and the impact of
partitioning strategies on load distribution.
To study the load imbalance and its correlation with request
load, the total number of requests received by each node was measured
period of 24 hours - broken down into intervals of 30 minutes. In a
window, a node is considered to be “in-balance”, if the node’s request
deviates from the average load by a value a less than a certain
15%). Otherwise the node was deemed “out-of-balance”. Figure 6 presents
fraction of nodes that are “out-of-balance” (henceforth, “imbalance
during this time period. For reference, the corresponding request load
by the entire system during this time period is also plotted. As seen in
figure, the imbalance ratio decreases with increasing load. For
during low loads the imbalance ratio is as high as 20% and during high
is close to 10%. Intuitively, this can be explained by the fact that
loads, a large number of popular keys are accessed and due to uniform
distribution of keys the load is evenly distributed. However, during low
(where load is 1/8th of the measured peak load), fewer popular keys are
accessed, resulting in a higher load imbalance.
Figure 6: Fraction of nodes that are out-of-balance
(i.e., nodes whose request load is above a certain threshold from the
system load) and their corresponding request load. The interval between
in x-axis corresponds to a time period of 30 minutes.
This section discusses how Dynamo’s partitioning scheme has
evolved over time and its implications on load distribution.
Strategy 1: T random tokens per node and partition by
token value: This was the initial strategy deployed in
described in Section 4.2). In this scheme, each node is assigned T
(chosen uniformly at random from the hash space). The tokens of all
nodes are ordered
according to their values in the hash space. Every two consecutive
define a range. The last token and the first token form a range that
"wraps" around from the highest value to the lowest value in the hash
space. Because the tokens are chosen randomly, the ranges vary in size.
join and leave the system, the token set changes and consequently the
change. Note that the space needed to maintain the membership at each
increases linearly with the number of nodes in the system.
While using this strategy, the following problems were
encountered. First, when a new node joins the system, it needs to
“steal” its key
ranges from other nodes. However, the nodes handing the key ranges off
new node have to scan their local persistence store to retrieve the
set of data items. Note that performing such a scan operation on a
is tricky as scans are highly resource intensive operations and they
need to be
executed in the background without affecting the customer performance.
requires us to run the bootstrapping task at the lowest priority.
significantly slows the bootstrapping process and during busy shopping
when the nodes are handling millions of requests a day, the
taken almost a day to complete. Second, when a node joins/leaves the
the key ranges handled by many nodes change and the Merkle trees for the
ranges need to be recalculated, which is a non-trivial operation to
a production system. Finally, there was no easy way to take a snapshot
entire key space due to the randomness in key ranges, and this made the
of archival complicated. In this scheme, archiving the entire key space
requires us to retrieve the keys from each node separately, which is
The fundamental issue with this strategy is that the schemes
for data partitioning and data placement are intertwined. For instance,
cases, it is preferred to add more nodes to the system in order to
increase in request load. However, in this scenario, it is not possible
nodes without affecting data partitioning. Ideally, it is desirable to
independent schemes for partitioning and placement. To this end,
strategies were evaluated:
Strategy 2: T random tokens per node and equal sized
partitions: In this strategy, the hash space is divided into Q
sized partitions/ranges and each node is assigned T random tokens. Q is
set such that Q >> N and Q >> S*T, where S is the number of
in the system. In this strategy, the tokens are only used to build the
that maps values in the hash space to the ordered lists of nodes and not
decide the partitioning. A partition is placed on the first N unique
are encountered while walking the consistent hashing ring clockwise from
end of the partition. Figure 7 illustrates this strategy for N=3. In
example, nodes A, B, C are encountered while walking the ring from the
the partition that contains key k1. The primary advantages of this
are: (i) decoupling of partitioning and partition placement, and (ii)
the possibility of changing the placement scheme at runtime.
Figure 7: Partitioning and placement of keys in the three
strategies. A, B, and C depict the three unique nodes that form the
list for the key k1 on the consistent hashing ring (N=3). The shaded
indicates the key range for which nodes A, B, and C form the preference
Dark arrows indicate the token locations for various nodes.
Strategy 3: Q/S tokens per node, equal-sized
partitions: Similar to strategy 2, this strategy
divides the hash
space into Q equally sized partitions and the placement of partition is
decoupled from the partitioning scheme. Moreover, each node is assigned
tokens where S is the number of nodes in the system. When a node leaves
system, its tokens are randomly distributed to the remaining nodes such
these properties are preserved. Similarly, when a node joins the system
"steals" tokens from nodes in the system in a way that preserves
The efficiency of these three strategies is evaluated for a
system with S=30 and N=3. However, comparing these different strategies
fair manner is hard as different strategies have different
tune their efficiency. For instance, the load distribution property of
1 depends on the number of tokens (i.e., T) while strategy 3 depends on
number of partitions (i.e., Q). One fair way to compare these strategies
evaluate the skew in their load distribution while all strategies use
amount of space to maintain their membership information. For instance,
strategy 1 each node needs to maintain the token positions of all the
the ring and in strategy 3 each node needs to maintain the information
regarding the partitions assigned to each node.
In our next experiment, these strategies were evaluated by
varying the relevant parameters (T and Q). The load balancing efficiency
each strategy was measured for different sizes of membership information
needs to be maintained at each node, where Load balancing efficiency
defined as the ratio of average number of requests served by each node
maximum number of requests served by the hottest node.
The results are given in Figure 8. As seen in the figure,
strategy 3 achieves the best load balancing efficiency and strategy 2
worst load balancing efficiency. For a brief time, Strategy 2 served as
interim setup during the process of migrating Dynamo instances from
1 to Strategy 3. Compared to Strategy 1, Strategy 3 achieves better
and reduces the size of membership information maintained at each node
orders of magnitude. While storage is not a major issue the nodes gossip
membership information periodically and as such it is desirable to keep
information as compact as possible. In addition to this, strategy 3 is
advantageous and simpler to deploy for the following reasons: (i) Faster
bootstrapping/recovery: Since partition ranges are fixed, they can
stored in separate files, meaning a partition can be relocated as a unit
simply transferring the file (avoiding random accesses needed to locate
specific items). This simplifies the process of bootstrapping and
(ii) Ease of archival: Periodical archiving of the dataset is a
mandatory requirement for most of Amazon storage services. Archiving the
dataset stored by Dynamo is simpler in strategy 3 because the partition
can be archived separately. By contrast, in Strategy 1, the tokens are
randomly and, archiving the data stored in Dynamo requires retrieving
from individual nodes separately and is usually inefficient and slow.
disadvantage of strategy 3 is that changing the node membership requires
coordination in order to preserve the properties required of the
Figure 8: Comparison of the load distribution efficiency
of different strategies for system with 30 nodes and N=3 with equal
metadata maintained at each node. The values of the system size and
replicas are based on the typical configuration deployed for majority of
6.3 Divergent Versions: When and How Many?
As noted earlier, Dynamo is designed to tradeoff consistency
for availability. To understand the precise impact of different failures
consistency, detailed data is required on multiple factors: outage
of failure, component reliability, workload etc. Presenting these
detail is outside of the scope of this paper. However, this section
good summary metric: the number of divergent versions seen by the
in a live production environment.
Divergent versions of a data item arise in two scenarios.
The first is when the system is facing failure scenarios such as node
data center failures, and network partitions. The second is when the
handling a large number of concurrent writers to a single data item and
multiple nodes end up coordinating the updates concurrently. From both a
usability and efficiency perspective, it is preferred to keep the number
divergent versions at any given time as low as possible. If the versions
be syntactically reconciled based on vector clocks alone, they have to
passed to the business logic for semantic reconciliation. Semantic
reconciliation introduces additional load on services, so it is
minimize the need for it.
In our next experiment, the number of versions returned to
the shopping cart service was profiled for a period of 24 hours. During
period, 99.94% of requests saw exactly one version; 0.00057% of requests
versions; 0.00047% of requests saw 3 versions and 0.00009% of requests
versions. This shows that divergent versions are created rarely.
Experience shows that the increase in the number of
divergent versions is contributed not by failures but due to the
number of concurrent writers. The increase in the number of concurrent
usually triggered by busy robots (automated client programs) and rarely
humans. This issue is not discussed in detail due to the sensitive
6.4 Client-driven or Server-driven Coordination
As mentioned in Section 5, Dynamo has a request coordination
component that uses a state machine to handle incoming requests. Client
requests are uniformly assigned to nodes in the ring by a load balancer.
Dynamo node can act as a coordinator for a read request. Write requests
other hand will be coordinated by a node in the key’s current preference
This restriction is due to the fact that these preferred nodes have the
responsibility of creating a new version stamp that causally subsumes
version that has been updated by the write request. Note that if
versioning scheme is based on physical timestamps, any node can
An alternative approach to request coordination is to move
the state machine to the client nodes. In this scheme client
applications use a
library to perform request coordination locally. A client periodically
random Dynamo node and downloads its current view of Dynamo membership
Using this information the client can determine which set of nodes form
preference list for any given key. Read requests can be coordinated at
client node thereby avoiding the extra network hop that is incurred if
request were assigned to a random Dynamo node by the load balancer.
either be forwarded to a node in the key’s preference list or can be
coordinated locally if Dynamo is using timestamps based versioning.
An important advantage of the client-driven coordination
approach is that a load balancer is no longer required to uniformly
client load. Fair load distribution is implicitly guaranteed by the near
uniform assignment of keys to the storage nodes. Obviously, the
this scheme is dependent on how fresh the membership information is at
client. Currently clients poll a random Dynamo node every 10 seconds for
membership updates. A pull based approach was chosen over a push based
the former scales better with large number of clients and requires very
state to be maintained at servers regarding clients. However, in the
the client can be exposed to stale membership for duration of 10
case, if the client detects its membership table is stale (for instance,
members are unreachable), it will immediately refresh its membership
Table 2 shows the latency improvements at the 99.9th
percentile and averages that were observed for a period of 24 hours
client-driven coordination compared to the server-driven approach. As
the table, the client-driven coordination approach reduces the latencies
least 30 milliseconds for 99.9th percentile latencies and decreases
the average by 3 to 4 milliseconds. The latency improvement is because
client-driven approach eliminates the overhead of the load balancer and
extra network hop that may be incurred when a request is assigned to a
node. As seen in the table, average latencies tend to be significantly
than latencies at the 99.9th percentile. This is because Dynamo’s
engine caches and write buffer have good hit ratios. Moreover, since the
balancers and network introduce additional variability to the response
the gain in response time is higher for the 99.9th percentile than
Table 2: Performance of client-driven and
99.9th percentile read latency (ms)
99.9th percentile write latency (ms)
Average read latency (ms)
Average write latency (ms)
6.5 Balancing background vs. foreground tasks
Each node performs different kinds of background tasks for
replica synchronization and data handoff (either due to hinting or
adding/removing nodes) in addition to its normal foreground put/get
In early production settings, these background tasks triggered the
resource contention and affected the performance of the regular put and
operations. Hence, it became necessary to ensure that background tasks
when the regular critical operations are not affected significantly. To
end, the background tasks were integrated with an admission control
Each of the background tasks uses this controller to reserve runtime
the resource (e.g. database), shared across all background tasks. A
mechanism based on the monitored performance of the foreground tasks is
employed to change the number of slices that are available to the
The admission controller constantly monitors the behavior of
resource accesses while executing a "foreground" put/get operation.
Monitored aspects include latencies for disk operations, failed database
accesses due to lock-contention and transaction timeouts, and request
wait times. This information is used to check whether the percentiles of
latencies (or failures) in a given trailing time window are close to a
threshold. For example, the background controller checks to see how
99th percentile database read latency (over the last 60 seconds) is
to a preset threshold (say 50ms). The controller uses such comparisons
assess the resource availability for the foreground operations.
it decides on how many time slices will be available to background
thereby using the feedback loop to limit the intrusiveness of the
activities. Note that a similar problem of managing background tasks
studied in .
This section summarizes some of the experiences gained
during the process of implementation and maintenance of Dynamo. Many
internal services have used Dynamo for the past two years and it has
significant levels of availability to its applications. In particular,
applications have received successful responses (without timing out) for
99.9995% of its requests and no data loss event has occurred to date.
Moreover, the primary advantage of Dynamo is that it
provides the necessary knobs using the three parameters of (N,R,W) to
their instance based on their needs.. Unlike popular commercial data
Dynamo exposes data consistency and reconciliation logic issues to the
developers. At the outset, one may expect the application logic to
complex. However, historically, Amazon’s platform is built for high
availability and many applications are designed to handle different
modes and inconsistencies that may arise. Hence, porting such
use Dynamo was a relatively simple task. For new applications that want
Dynamo, some analysis is required during the initial stages of the
to pick the right conflict resolution mechanisms that meet the business
appropriately. Finally, Dynamo adopts a full membership model where each
is aware of the data hosted by its peers. To do this, each node actively
gossips the full routing table with other nodes in the system. This
well for a system that contains couple of hundreds of nodes. However,
a design to run with tens of thousands of nodes is not trivial because
overhead in maintaining the routing table increases with the system
limitation might be overcome by introducing hierarchical extensions to
note that this problem is actively addressed by O(1) DHT systems(e.g.,
This paper described Dynamo, a highly available and scalable
data store, used for storing state of a number of core services of
e-commerce platform. Dynamo has provided the desired levels of
performance and has been successful in handling server failures, data
failures and network partitions. Dynamo is incrementally scalable and
service owners to scale up and down based on their current request load.
allows service owners to customize their storage system to meet their
performance, durability and consistency SLAs by allowing them to tune
parameters N, R, and W.
The production use of Dynamo for the past year demonstrates
that decentralized techniques can be combined to provide a single
highly-available system. Its success in one of the most challenging
environments shows that an eventual-consistent storage system can be a
block for highly-available applications.
The authors would like to thank Pat Helland for his contribution
to the initial design of Dynamo. We would also like to thank Marvin
Robert van Renesse for their comments. Finally, we would like to thank
shepherd, Jeff Mogul, for his detailed comments and inputs while
camera ready version that vastly improved the quality of the paper.
Adya, A., Bolosky, W. J., Castro, M., Cermak, G., Chaiken, R., Douceur,
J. R., Howell, J., Lorch, J. R., Theimer, M., and Wattenhofer, R. P.
Farsite: federated, available, and reliable storage for an incompletely
environment. SIGOPS Oper. Syst. Rev. 36, SI (Dec. 2002), 1-14.
Bernstein, P.A., and Goodman, N. An algorithm for concurrency control
and recovery in replicated distributed databases. ACM Trans. on Database
9(4):596-615, December 1984
Chang, F., Dean, J., Ghemawat, S., Hsieh, W. C., Wallach, D. A.,
Burrows, M., Chandra, T., Fikes, A., and Gruber, R. E. 2006. Bigtable: a
distributed storage system for structured data. In Proceedings of the
Conference on USENIX Symposium on Operating Systems Design and
Volume 7 (Seattle, WA, November 06 - 08, 2006). USENIX Association,
Berkeley, CA, 15-15.
Douceur, J. R. and Bolosky, W. J. 2000. Process-based regulation of
low-importance processes. SIGOPS Oper. Syst. Rev. 34, 2 (Apr.
Fox, A., Gribble, S. D., Chawathe, Y., Brewer, E. A., and Gauthier, P.
1997. Cluster-based scalable network services. In Proceedings of the
Sixteenth ACM Symposium on Operating Systems Principles (Saint Malo,
France, October 05 - 08, 1997). W. M. Waite, Ed. SOSP '97. ACM Press,
Ghemawat, S., Gobioff, H., and Leung, S. 2003. The Google file system.
In Proceedings of the Nineteenth ACM Symposium on Operating Systems
Principles (Bolton Landing, NY, USA, October 19 - 22, 2003). SOSP
Press, New York, NY, 29-43.
Gray, J., Helland, P., O'Neil, P., and Shasha, D. 1996. The dangers of
replication and a solution. In Proceedings of the 1996 ACM SIGMOD
international Conference on Management of Data (Montreal, Quebec,
June 04 - 06, 1996). J. Widom, Ed. SIGMOD '96. ACM Press, New York, NY,
Gupta, I., Chandra, T. D., and Goldszmidt, G. S. 2001. On scalable and
efficient distributed failure detectors. In Proceedings of the
Annual ACM Symposium on Principles of Distributed Computing
Island, United States). PODC '01. ACM Press, New York, NY, 170-179.
Kubiatowicz, J., Bindel, D., Chen, Y., Czerwinski, S., Eaton, P., Geels,
D., Gummadi, R., Rhea, S., Weatherspoon, H., Wells, C., and Zhao, B.
OceanStore: an architecture for global-scale persistent storage. SIGARCH
Archit. News 28, 5 (Dec. 2000), 190-201.
D., Lehman, E., Leighton, T., Panigrahy, R., Levine, M., and Lewin, D.
Consistent hashing and random trees: distributed caching protocols for
relieving hot spots on the World Wide Web. In Proceedings of the
Twenty-Ninth Annual ACM Symposium on theory of Computing (El Paso,
United States, May 04 - 06, 1997). STOC '97. ACM Press, New York, NY,
B.G., et. al., “Notes on Distributed Databases”, Research Report
RJ2571(33471), IBM Research, July 1979
L. Time, clocks, and the ordering of events in a distributed system. ACM
Communications, 21(7), pp. 558-565, 1978.
R. A digital signature based on a conventional encryption function.
of CRYPTO, pages 369–378. Springer-Verlag, 1988.
V., and Sirer, E. G. Beehive: O(1)lookup performance for power-law
distributions in peer-to-peer overlays. In Proceedings of the 1st
on Symposium on Networked Systems Design and Implementation, San
CA, March 29 - 31, 2004.
P., Heidemann, J., Ratner, D., Skinner, G., and Popek, G. 1994.
conflicts in the Ficus file system. In Proceedings of the USENIX
Technical Conference on USENIX Summer 1994 Technical Conference - Volume
(Boston, Massachusetts, June 06 - 10, 1994). USENIX Association,
A., and Druschel, P. Pastry: Scalable, decentralized object location and
routing for large-scale peer-to-peer systems.Proceedings of Middleware,
pages 329-350, November, 2001.
A., and Druschel, P. Storage management and caching in PAST, a
persistent peer-to-peer storage utility. Proceedings of Symposium on
Systems Principles, October 2001.
Y., Frølund, S., Veitch, A., Merchant, A., and Spence, S. 2004. FAB:
distributed enterprise disk arrays from commodity components. SIGOPS
Syst. Rev. 38, 5 (Dec. 2004), 48-58.
M., Kistler, J.J., Siegel, E.H. Coda: A Resilient Distributed File
Workshop on Workstation Operating Systems, Nov. 1987.
I., Morris, R., Karger, D., Kaashoek, M. F., and Balakrishnan, H. 2001.
A scalable peer-to-peer lookup service for internet applications. In Proceedings
the 2001 Conference on Applications, Technologies, Architectures, and
Protocols For Computer Communications (San Diego, California, United
States). SIGCOMM '01. ACM Press, New York, NY, 149-160.
D. B., Theimer, M. M., Petersen, K., Demers, A. J., Spreitzer, M. J.,
Hauser, C. H. 1995. Managing update conflicts in Bayou, a weakly
replicated storage system. In Proceedings of the Fifteenth ACM
Operating Systems Principles (Copper Mountain, Colorado, United
December 03 - 06, 1995). M. B. Jones, Ed. SOSP '95. ACM Press, New York,
R. H. A majority consensus approach to concurrency control for multiple
databases. ACM Transactions on Database Systems 4 (2): 180-209, 1979.
H., Eaton, P., Chun, B., and Kubiatowicz, J. 2007. Antiquity: exploiting
secure log for wide-area distributed storage. SIGOPS Oper. Syst. Rev.
41, 3 (Jun. 2007), 371-384.
M., Culler, D., and Brewer, E. 2001. SEDA: an architecture for
well-conditioned, scalable internet services. In Proceedings of the
Eighteenth ACM Symposium on Operating Systems Principles (Banff,
Canada, October 21 - 24, 2001). SOSP '01. ACM Press, New York, NY,