Amazon's Dynamo - All Things Distributed

28 Dec 09

David Rodriguez

amazon database

22 Jul 09

fulvius longhi

no data loss event has occurred to date.

12 Jul 09

Stian Danenbarger

The Amazon.com platform, which provides services for many web sites worldwide, is implemented on top of an infrastructure of tens of thousands of servers and network components located in many datacenters around the world. At this scale, small and large components fail continuously and the 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 services use to provide an “always-on” experience. To achieve this level of availability, Dynamo sacrifices consistency under certain failure scenarios. It makes extensive use of object versioning and application-assisted conflict resolution in a manner that provides a novel interface for developers to use.

amazon dynamo distributed storage architecture data database

15 May 09

Kumar Raman

dynamo

Amazon's Dynamo

18 Apr 09

infrared

"Dynamo is internal technology developed at Amazon to address the need for an incrementally scalable, highly-available key-value storage system. The technology is designed to give its users the ability to trade-off cost, consistency, durability and perfor

amazon performance research distributed

06 Apr 09

sven duzont

amazon dynamo scalability architecture distributed

23 Feb 09

Carol Whittington

amazon dynamo storage cloud

17 Feb 09

Ernesto Krsulovic

programming development database amazon design performance scaling storage

08 Feb 09

Clifford Ilkay

amazon dynamo AWS scalability distributed systems high availability blogs tech blogs

21 Jan 09

Yong Zhang

Dynamo is not directly exposed externally as a web service; however, Dynamo and similar Amazon technologies are used to power parts of our Amazon Web Services, such as S3.

We submitted the technology for publication in SOSP because many of the techniques used in Dynamo originate in the operating systems and distributed systems research of the past years; DHTs, consistent hashing, versioning, vector clocks, quorum, anti-entropy based recovery, etc. As far as I know Dynamo is the first production system to use the synthesis of all these techniques, and there are quite a few lessons learned from doing so. The paper is mainly about these lessons.
- Yong Zhang on 2009-01-21
  
  The foundation of HaaS. The future of operating system, back to multi-users, time-sharing computing?

13 Jan 09

zhen ma

amazon distributed architecture dynamo

Dynamo employs
a gossip based distributed failure detection and membership protocol.

29 Dec 08

Jean-Lou Dupont

A
Merkle tree is a hash tree where leaves are hashes of the values of individual
keys.
Merkle trees minimize
the amount of data that needs to be transferred for synchronization and reduce the
number of disk reads performed during the anti-entropy process.
8 more annotations...
- Seeds are nodes that are discovered via an external mechanism and are
  known to all nodes.
- In Dynamo, each storage node has three main software
  components: request coordination, membership and failure detection, and a local
  persistence engine. All these components are implemented in Java.
- To counter this, any of the top N nodes in the
  preference list is allowed to coordinate the writes.
- Since Dynamo is run on standard commodity hardware
  components that have far less I/O throughput than high-end enterprise servers,
- To reduce the durability
  risk, the write operation is refined to have the coordinator choose one out of
  the N replicas to perform a “durable write”.
- The fundamental issue with this strategy is that the schemes
  for data partitioning and data placement are intertwined.
- Experience shows that the increase in the number of
  divergent versions is contributed not by failures but due to the increase in
  number of concurrent writers.
- Any
  Dynamo node can act as a coordinator for a read request. Write requests on the
  other hand will be coordinated by a node in the key’s current preference list.
  This restriction is due to the fact that these preferred nodes have the added
  responsibility of creating a new version stamp that causally subsumes the
  version that has been updated by the write request. Note that if Dynamo’s
  versioning scheme is based on physical timestamps, any node can coordinate a
  write request.

24 Nov 08

Jerry Wong

Amaozn的技术架构

Amazon Dynamo architecture

18 Oct 08

Mike Chelen

p2p distribute file system

it was imperative for us to avoid routing
requests through multiple nodes (which is the typical design adopted by several
distributed hash table systems such as Chord and Pastry)
Dynamo can be characterized as a zero-hop DHT, where
each node maintains enough routing information locally to route a request to
the appropriate node directly.
48 more annotations...
- 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 in the
  storage system and returns a single object or a list of objects with
  conflicting versions along with a context.
- The put(key, context,
  object) operation determines where the replicas of the object should
  be placed based on the associated key, and writes the replicas to
  disk.
- The context encodes system metadata about the object that is
  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 the
  system can verify the validity of the context object supplied in the put
  request.
- Dynamo’s
  partitioning scheme relies on consistent hashing to distribute the load across
  multiple storage hosts.
- In consistent hashing [10], the output
  range of a hash function is treated as a fixed circular space or “ring” (i.e.
  the largest hash value wraps around to the smallest hash value).
- The principle advantage
  of consistent hashing is that departure or arrival of a node only affects its
  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 nodes. To
  address these issues, Dynamo uses a variant of consistent hashing (similar to
  the one used in [10, 20]): instead of mapping a node to a single point in the
  circle, each node gets assigned to multiple points in the ring. To this end,
  Dynamo uses the concept of “virtual nodes”. A virtual node looks like a single
  node in the system, but each node can be responsible for more than one virtual
  node. Effectively, when a new node is added to the system, it is assigned
  multiple positions (henceforth, “tokens”) in the ring.
- 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 across
  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 equivalent
  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 physical
  infrastructure.
- Each data item is replicated at N hosts,
  where N is a parameter configured “per-instance”.
- Each key, k,
  is assigned to a coordinator node (described in the previous section). The
  coordinator is in charge of the replication of the data items that fall within
  its range. In addition to locally storing each key within its range, the
  coordinator replicates these keys at the N-1 clockwise successor nodes in the
  ring.
- In Figure 2, node B replicates
  the key k at nodes C and D in addition to storing it locally. Node D
  will store the keys that fall in the ranges (A, B], (B, C], and (C, D].
- The list of nodes that is responsible for storing a
  particular key is called the preference list.
- every node in the system can
  determine which nodes should be in this list for any particular key
- it is possible that the first
  N successor positions for a particular key may be owned by less than N distinct
  physical nodes
- To address this, the preference list for a key is constructed by skipping
  positions in the ring to ensure that the list contains only distinct physical
  nodes.
- Dynamo provides eventual consistency, which allows for
  updates to be propagated to all replicas asynchronously.
- A put() call may return
  to its caller before the update has been applied at all the replicas, which can
  result in scenarios where a subsequent get() operation may return an object
  that does not have the latest updates.
- If there are no failures then there is
  a bound on the update propagation times.
- However, under certain failure
  scenarios (e.g., server outages or network partitions), updates may not arrive
  at all replicas for an extended period of time.
- For example, the shopping cart application requires
  that an “Add to Cart” operation can never be
  forgotten or rejected.
- If the most recent state of the cart is unavailable, and
  a user makes changes to an older version of the cart, that change is still
  meaningful and should be preserved. But at the same time it shouldn’t supersede
  the currently unavailable state of the cart, which itself may contain changes
  that should be preserved.
- both “add to cart” and “delete
  item from cart” operations are translated into put requests to Dynamo
- When
  a customer wants to 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) the older
  version and the divergent versions are reconciled later.
- Dynamo treats
  the result of each modification as a new and immutable version of the data
- Most of the time, new versions subsume the previous version(s), and
  the system itself can determine the authoritative version (syntactic
  reconciliation).
- However, version branching may happen, in the presence of
  failures combined with concurrent updates, resulting in conflicting versions of
  an object
- In these cases, the system cannot reconcile the multiple versions of
  the same object and the client must perform the reconciliation in order to collapse
  multiple branches of data evolution back into one (semantic reconciliation).
- A
  typical example of a collapse operation is “merging” different versions of a
  customer’s shopping cart.
- Using this reconciliation mechanism, an “add to cart”
  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 versions of
  the same data.
- Updates in the presence of network partitions and node failures
  can potentially result in an object having distinct version sub-histories,
  which the system will need to reconcile in the future.
- This requires us to
  design applications that explicitly acknowledge the possibility of multiple
  versions of the same data (in order to never lose any updates).
- Dynamo uses vector clocks [12] in order to capture causality
  between different versions of the same object.
- A vector clock is effectively a
  list of (node, counter) pairs.
- One vector clock is associated with every version
  of every object. One can determine whether two versions of an object are on
  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 are
  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 context it
  obtained from an earlier read operation, which contains the vector clock
  information.
- Upon processing a read request, if Dynamo has access to multiple
  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 the
  divergent versions and the branches are collapsed into a single new version.
- 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 Sx)
  that handles the write for this key increases its sequence number and uses it
  to create the data's vector clock. The system now has the object D1 and its
  associated clock [(Sx, 1)]. The client updates the object. Assume the same node
  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 that
  have not yet seen D2. Let us assume that the same client updates the object
  again and a different server (say Sy) handles the request. The system now has
  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 D4
  (descendant of D2) whose version clock is [(Sx, 2), (Sz, 1)]. A node that is
  aware of D1 or D2 could determine, upon receiving D4 and its clock, that D1 and
  D2 are overwritten by the new data and can be garbage collected. A node that is
  aware of D3 and receives D4 will find that there is no causal relation between
  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 (upon a
  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)]. If the
  client performs the reconciliation and node Sx coordinates the write, Sx will
  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 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.

18 Sep 08

mik rub

General

06 Aug 08

Frank Colcord

Wiki Ruby

26 Jun 08

Harjeet Singh

Amazon's Dynamo

architecture mapreduce

Dynamo is internal technology developed at Amazon to address the need for an incrementally scalable, highly-available key-value storage system. The technology is designed to give its users the ability to trade-off cost, consistency, durability and performance, while maintaining high-availability.
A pdf version is available here. You can also read the full online version.

07 Jun 08

Tong Luo

amazon infrastructure architecture

08 May 08

Ken Wei

Amazon dynamo

25 Mar 08

H I

distributed research storage

21 Mar 08

M R

Architektura DoSprawdzenia Skalowalność amazon dataBase dynamo

jaimini joshi

readinglist

20 Mar 08

Arrix Z

amazon cache distributed dynamo hashing performance scalability

19 Jan 08

Sander van Zoest

Highly Available Key-value Store

ddb algorithm amazon papers s3 scalability dynamo store high availability database

04 Dec 07

Jan Kujawa

17 Nov 07

Alex Kapranoff

amazon api database storage performance data

16 Nov 07

David Brown

amazon AWS databases Grid s3 EC2 technology

15 Nov 07

M G

06 Nov 07

hg ye

amazon scalability architecture distributed

03 Nov 07

François Charoy

amazon architecture performance webservices scalability research for:momo54 data

31 Oct 07

Gordon Haff

amazon storage

15 Oct 07

Jacob Share

e-commerce

11 Oct 07

Olifante *

"Dynamo is internal technology developed at Amazon to address the need for an incrementally scalable, highly-available key-value storage system [...] designed to give its users the ability to trade-off cost, consistency, durability and performance"

Dynamo Amazon HA consistency durability performance availability DHT consistent_hashing versioning vector_clocks quorum anti-entropy recovery