Dynamo — Amazon's Highly Available Key-Value Store

What you'll learn

• Introduction

  This document unpacks the original Amazon Dynamo described in the 2007 paper "Dynamo: Amazon's Highly Available Key-value Store" by DeCandia et al. This is NOT AWS DynamoDB—DynamoDB is a managed service that was influenced by Dynamo but…

• 1. Why Dynamo — The Amazon Shopping-Cart Problem

  Amazon's business metrics drove a clear engineering observation: every 100ms of additional latency cost them 1% in sales. More critically, if a customer couldn't add an item to their cart because the system was unavailable, that was an i…

• The Business Case for AP

  Traditional databases (RDBMS) offered strong consistency but required coordination—locks, master election, quorum writes that block if nodes are unreachable. In Amazon's highly distributed infrastructure spanning multiple datacenters, ne…

• The CAP Choice

  Dynamo explicitly chose AP over CP: - CP systems (like Google's BigTable or Megastore): guarantee consistency by refusing writes during partitions or coordination failures - AP systems (like Dynamo): accept all writes, store multiple con…

• 2. Design Goals (from the paper)

  The Dynamo paper explicitly lists these design principles:

• Always Writeable

  The primary goal. Even if nodes fail, even during network partitions, writes must succeed. This led to "sloppy quorums" (explained later) where writes are accepted by any reachable node, not just the "correct" ones.

• Decentralized, Symmetric Architecture

  No master node. No distinguished coordinator. Every node has the same responsibilities. This eliminates single points of failure and simplifies operations—any node can answer any request.

• Incremental Scalability

  Add nodes one at a time without downtime or system-wide coordination. The consistent hashing ring (below) makes this possible—new nodes claim a portion of the keyspace automatically.

• Heterogeneity Awareness

  Nodes have different hardware capabilities (CPU, disk, network). Virtual nodes (tokens) allow a more powerful machine to claim more of the ring, balancing load proportionally to capacity.

• Tunable Consistency

  Amazon didn't want one-size-fits-all. Different use cases tolerate different consistency/latency tradeoffs. The N/R/W knobs (replication factor, read quorum, write quorum) let operators dial consistency up or down per deployment.

• Eventual Consistency

  Replicas will converge to the same value eventually, but they may diverge temporarily. Anti-entropy mechanisms (Merkle trees) ensure convergence happens automatically in the background. ---

• 3. Data Model

  Dynamo's data model is brutally simple: - Key: opaque byte array, typically a string. Hashed to determine placement on the ring. - Value: opaque blob, typically Each key is hashed: position = MD5(key) mod 2^128. The key is stored on the…

• Physical vs Virtual Nodes

  Naive consistent hashing assigns each physical node one position on the ring. Problem: uneven load. If you have 10 nodes, random hash placement doesn't guarantee each node gets 10% of the keys. Solution: Virtual nodes (tokens). Each phys…

• Why Virtual Nodes?

  1. Uniform load distribution: Statistical averaging makes load imbalance unlikely 2. Heterogeneous hardware: A machine with 2x capacity can claim 2x tokens 3. Graceful node addition/removal: When a node leaves, its tokens are distributed…

• Coordinator Node

  For a given key, the coordinator is the first node encountered clockwise from hash(key) on the ring. The coordinator handles client requests for that key (reads and writes). ---

• 5. Replication — Preference Lists

  Each key is replicated on N nodes (typically N=3). The replicas are the next N distinct physical nodes clockwise from the coordinator.

• Preference List Construction

  1. Start at position = hash(key) 2. Walk clockwise on the ring 3. Collect the first N distinct physical nodes (skip virtual nodes from the same physical node) This list is called the preference list for the key.

• Why Distinct Physical Nodes?

  If you replicate to three virtual nodes on the same physical machine, a single hardware failure loses all replicas. Requiring distinct physical nodes ensures fault tolerance. Amazon's deployments often spanned multiple availability zones…

• 6. Quorum Reads & Writes (N, R, W tunable)

  Dynamo uses quorum-based replication with three tunable parameters: - N: replication factor (number of replicas) - R: read quorum (must read from R replicas) - W: write quorum (must write to W replicas)

• Write Path

  When a client writes put(key, context, value): 1. Request arrives at coordinator (or any node, which forwards to coordinator) 2. Coordinator sends write to all N nodes in the preference list 3. Coordinator waits for W nodes to acknowledg…

• Read Path

  When a client reads get(key): 1. Request arrives at coordinator 2. Coordinator sends read to all N nodes in preference list 3. Coordinator waits for R nodes to respond 4. Coordinator reconciles versions (vector clocks) from R replicas 5.…

• Consistency Tradeoffs

  The magic is in the inequality R + W > N: - If R + W > N, read and write quorums overlap—at least one node in the read quorum saw the write - This guarantees read-your-writes consistency (you'll see your own write immediately) - If R + W…

• Consistency Guarantees Table

  | Property | N=3, R=2, W=2 | N=3, R=1, W=1 | N=5, R=3, W=3 | |----------|---------------|---------------|---------------| | Read-your-writes | ✅ (R+W>N) | ❌ (R+W≤N) | ✅ (R+W>N) | | Monotonic reads | ❌ (depends on routing) | ❌ | ❌ | | Mon…

• 7. Hinted Handoff

  Quorum replication assumes you can reach W nodes in the preference list. But what if one is down? Sloppy quorum: if a node in the preference list is unreachable, accept the write at another node with a hint indicating the intended recipi…

• How It Works

  Write to key with preference list [A, B, C]: 1. Coordinator tries to write to A, B, C 2. Node B is down (network partition or crash) 3. Coordinator picks another node D (next on the ring, or any reachable node) 4. Coordinator writes to A…

• Why Hinted Handoff?

  Availability: Without hinted handoff, if one replica is down, W=2 might fail (only 2 of 3 reachable → not enough). With hints, you can accept writes as long as any W reachable nodes exist, not just W in the preference list. Eventual cons…

• Tradeoffs

  - Hinted handoff reduces durability temporarily: if node D crashes before handing off to B, the write is lost (unless A or C still have it) - It complicates failure reasoning: a write may succeed but not be on the "right" nodes yet Amazo…

• 8. Vector Clocks for Version Reconciliation

  Dynamo tracks causality using vector clocks to detect concurrent writes and preserve all conflicting versions (siblings).

• What is a Vector Clock?

  A vector clock is a list of (node, counter) pairs: Each node that handles a write increments its own counter. The vector clock captures the causal history: "this version descends from A's 1st write, B's 2nd write, and C's 1st write."

• Write Algorithm

  When node X coordinates a write: 1. Client provides context (vector clock from previous read, or empty if first write) 2. Node X increments context[X] 3. New version is stored with the updated vector clock

• Descendant vs Concurrent

  Given two vector clocks V1 and V2: - V2 descends from V1 if V2[node] >= V1[node] for all nodes - V1 and V2 are concurrent if neither descends from the other

• Sibling Detection

  On read, coordinator fetches R replicas and reconciles their versions: 1. Collect all versions (each tagged with a vector clock) 2. Remove any version dominated by another (descendent relationship) 3. Return all remaining versions (sibli…

• Worked Example

• Code: Vector Clock Comparison

• Vector Clock Pruning

  Problem: vector clocks grow unbounded as more nodes touch a key. Amazon's solution: limit vector clock size (e.g., 10 entries) and drop the oldest entry when full. This can cause false concurrency (siblings created unnecessarily), but in…

• 9. Anti-Entropy — Merkle Trees

  Quorum replication and hinted handoff handle most consistency needs, but failures can still cause replicas to diverge (missed hints, long-duration partitions). Anti-entropy is the background process that ensures replicas eventually conve…

• Naive Approach: Compare Every Key

  Replicas could periodically exchange all key-value pairs and synchronize. Problem: inefficient. A node with millions of keys can't afford to scan and compare them all regularly.

• Merkle Trees

  A Merkle tree (hash tree) compactly represents the state of a key range. Each leaf is hash(key + value + version), and each internal node is hash(leftchild | rightchild). If two replicas have the same root hash, their entire key range is…

• Anti-Entropy Protocol

  1. Replica A and B (for a shared key range) exchange root hashes 2. If roots match → done (no divergence) 3. If roots differ → exchange level-2 hashes 4. Recursively descend until leaf divergence is found 5. Synchronize only the divergen…

• Merkle Tree Maintenance

  Each node maintains one Merkle tree per virtual token (key range). When a key is written/updated, the leaf and path to the root are recomputed (log N updates). Amazon's Dynamo maintained separate trees per key range to parallelize synchr…

• Tradeoffs

  - Pros: Dramatically reduces network cost (only divergent keys are exchanged) - Cons: Memory overhead (storing trees), rebuild cost if key range splits/merges But for Amazon's scale, Merkle trees were essential—scanning millions of keys…

• 10. Membership & Failure Detection

  Dynamo is fully decentralized—no master to manage membership. Instead, nodes use gossip to propagate membership changes and local failure detection to mark peers as down.

• Gossip-Based Membership

  Each node maintains a local membership view: the set of nodes in the ring and their token assignments. Periodically (e.g., every second): 1. Node A picks a random peer B 2. A sends its membership view to B 3. B merges A's view with its o…

• Adding a Node

  When a new node joins: 1. New node contacts a seed node (bootstrap list, manually configured) 2. Seed returns current membership list 3. New node picks tokens (random positions on the ring) 4. New node gossips its tokens to the cluster 5…

• Removing a Node

  Two cases: Graceful leave: Node gossips "I'm leaving" with a high timestamp. Other nodes remove it from their membership view and redistribute its tokens. Failure: Other nodes detect the failure (timeout-based, below) and eventually goss…

• Failure Detection

  Each node independently monitors its peers: - Periodic heartbeat (e.g., every 1 second) - If no response after N attempts, mark peer as "suspected" - If suspected for > threshold (e.g., 10 seconds), mark as "down" Crucially: failure dete…

• Seed Nodes

  Every node is configured with a static list of seed nodes (e.g., 3-5 well-known nodes). Seeds serve only to bootstrap membership—new nodes contact seeds to join. Once a node has the membership list, it no longer relies on seeds (gossip k…

• Deeper Look — Seed Nodes and Logical Partitions

  Gossip alone can create a subtle problem: if an administrator adds node A and then separately adds node B, both nodes consider themselves part of the ring, but neither immediately knows about the other. This creates a logical partition w…

• 10.5. Request Routing — Client Strategies

  Dynamo clients can route requests in two ways, each with different tradeoffs for latency and complexity.

• Strategy 1: Client Routes Through a Load Balancer

  The client sends requests to a generic load balancer, which forwards to any node in the cluster. That node acts as the coordinator (or forwards to the correct coordinator if it's not in the preference list). Pros: - Client is unaware of…

• Strategy 2: Partition-Aware Client (Zero-Hop DHT)

  The client maintains a copy of the ring (token assignments) and directly contacts a node in the preference list for the key. Pros: - Lower latency (no intermediate hop) - Direct path to the right coordinator - Called "zero-hop DHT" becau…

• Coordinator Selection for Writes

  Writes are coordinated by one of the top N nodes in the preference list. Although it's natural to always use the first node (for serialization), this creates uneven load when request patterns aren't uniform. Dynamo optimizes by choosing…

• 11. Failure Handling End-to-End

  Let's walk through a complete failure scenario to see how Dynamo's mechanisms compose.

• Scenario: Node B Fails Permanently

• Key Observations

  1. Availability maintained: Every write succeeded, even with B permanently down. 2. Hinted handoff bridged the gap: Node D temporarily held writes intended for B. 3. Gossip adapted membership: B was removed from the ring after a grace pe…

• 11.5. Read Repair — Background Consistency

  After a read coordinator returns the reconciled data to the client, it doesn't immediately discard the responses from replicas. Instead, it waits for a short period (typically a few hundred milliseconds) to collect any outstanding respon…

• How Read Repair Works

• Why Read Repair Matters

  Without Read Repair, stale replicas would only get fixed via anti-entropy (Merkle tree background sync), which runs much less frequently (every few hours). Read Repair catches most divergence quickly because: - Hot keys get read frequent…

• 11.6. Request Handling State Machine

  Each client request (get or put) creates a state machine instance on the coordinator node. The state machine encapsulates all the logic for handling the request: - Identifying the preference list nodes - Sending requests to replicas - Wa…

• Read Operation State Machine

• Write Operation State Machine

  The state machine approach simplifies concurrency: each request is independent, and the coordinator doesn't need to maintain complex shared state. If the coordinator fails mid-request, the client retries, and a different coordinator hand…

• 12. Sloppy Quorum vs Strict Quorum

  Dynamo's quorum is "sloppy" rather than "strict." Understanding the difference is critical.

• Strict Quorum (Traditional)

  In a strict quorum, R and W must overlap within the N nodes of the preference list: - Write must succeed on W nodes from the preference list - Read must succeed on R nodes from the preference list - If R + W > N, quorums overlap (read-yo…

• Sloppy Quorum (Dynamo)

  Dynamo relaxes this: R and W can be satisfied by any N healthy nodes, not necessarily from the preference list. If a preference list node is down, the write goes to a "hint holder" (next available node). How it works: - Write to key with…

• 13. What Dynamo Got Wrong (in retrospect)

  Dynamo's design was groundbreaking, but production use revealed challenges:

• 1. Application-Side Conflict Resolution is Hard

  The paper presents the shopping cart merge (union of items) as straightforward. In practice, most application developers struggled with sibling reconciliation: - What if the conflict is on user profile data? (Two updates to "email" field…

• 2. Vector Clock Complexity

  Vector clocks grew large for hot keys touched by many nodes. The pruning strategy (drop oldest entry) caused false siblings. Developers found vector clocks opaque and hard to debug. Later systems (Riak, Voldemort) exposed vector clocks b…

• 3. Operational Complexity of Tunable Consistency

  N/R/W knobs are powerful but confusing. Operators often misconfigured them (e.g., R=1, W=1 with N=3, expecting read-your-writes but not getting it). There's no "right" answer—each use case needs different settings.

• 4. Eventual Consistency is User-Facing

  In theory, siblings are rare (only under concurrent writes). In practice, due to failures, partitions, and hinted handoff delays, siblings appeared more often than expected. Users saw stale data or unexpected merge results. Amazon's shop…

• 5. Lack of Strong Consistency Option

  Some use cases (e.g., inventory counts, financial transactions) genuinely need strong consistency. Dynamo offered no way to achieve it—you had to use a different system. Later databases (DynamoDB, Cassandra with lightweight transactions)…

• 13.5. Criticism & Limitations

  Dynamo's design was influential, but it also had recognized limitations. Some were acknowledged in the original paper, others emerged from production use.

• 1. Routing Table Scalability

  Every Dynamo node maintains a full copy of the ring (all nodes and their token assignments). This routing table grows as nodes are added. For a cluster with thousands of nodes and hundreds of tokens per node, the routing table can become…

• 2. Seed Nodes Violate Symmetry

  Dynamo claims to be fully symmetric—every node has the same responsibilities. But seed nodes are a special class: they're externally discoverable and used to bootstrap membership. Why it's a problem: - Seeds are configured statically (in…

• 3. Security and DHT Attacks

  Dynamo was built for Amazon's internal trusted network. No authentication, no encryption, no protection against malicious nodes. DHT-specific vulnerabilities: - Sybil attack: A malicious actor adds many nodes with chosen token positions,…

• 4. Leaky Abstraction — Client-Side Conflict Resolution

  Dynamo exposes siblings (conflicting versions) to the client and expects the application to merge them. This is a "leaky abstraction"—the client must understand distributed systems concepts (vector clocks, concurrency, merge semantics) t…

• 5. No Strong Consistency Option

  Dynamo's design prioritizes availability over consistency. There's no way to get linearizable reads or serializable writes—even if you set R=W=N, you can still see stale data due to sloppy quorum and hinted handoff. When this is a proble…

• 6. High Load Causes Imbalance

  Under very high load, Dynamo's load balancing can degrade. The problem: if one node becomes slow (e.g., GC pause, disk contention), clients avoid it (because it times out or responds slowly). But that node still owns its token ranges, so…

• 14. Dynamo vs DynamoDB — Not the Same Thing

  This is critical: Amazon Dynamo (2007 paper) and AWS DynamoDB (2012 launch) are different systems.

• Original Dynamo (2007)

  - Deployed: Internal Amazon infrastructure (shopping cart, session state) - Consistency: AP (eventual consistency), vector clocks, siblings returned to client - Replication: Peer-to-peer, sloppy quorum with hinted handoff - Membership: G…

• AWS DynamoDB (2012–present)

  - Deployment: Fully managed AWS service - Consistency: Tunable per-request: eventual or strong consistency (linearizable reads available) - Replication: Uses Paxos-based replication (not sloppy quorum), writes go to a leader - Membership…

• Why the Differences?

  AWS productized Dynamo's ideas but made pragmatic changes: 1. Strong consistency option: Customers demanded it. DynamoDB uses Paxos to provide linearizable reads (at the cost of latency and availability during leader failures). 2. Simpli…

• What Stayed the Same?

  - Consistent hashing with virtual nodes (for partitioning) - Replication across 3 availability zones - Emphasis on availability (though not as absolute as original Dynamo) - Key-value access pattern (no joins, no SQL) Bottom line: Origin…

• 14.5. Datastores Built on Dynamo Principles

  Dynamo was never open-sourced. Two major NoSQL databases adopted its ideas: Apache Cassandra and Riak. Each made different choices about which Dynamo techniques to adopt.

• Adoption Comparison

  | Technique | Apache Cassandra | Riak | |-----------|------------------|------| | Consistent Hashing with Virtual Nodes | ✅ Yes (tokens) | ✅ Yes (vnodes) | | Hinted Handoff | ✅ Yes | ✅ Yes | | Anti-Entropy with Merkle Trees | ⚠️ Manual r…

• Apache Cassandra

  Cassandra started at Facebook in 2008, combining Dynamo's partitioning and replication with BigTable's storage model (SSTables, memtables). From Dynamo: - Consistent hashing with tokens (virtual nodes) - Tunable N/R/W quorums - Gossip-ba…

• Riak

  Basho built Riak in 2009 as a near-clone of Dynamo, staying closer to the original design. From Dynamo: - All core techniques: consistent hashing, vector clocks, sloppy quorum, hinted handoff, Merkle tree anti-entropy, gossip Enhancement…

• Project Voldemort

  LinkedIn built Voldemort in 2009, also heavily inspired by Dynamo. Similar to Riak: vector clocks, tunable consistency, pluggable storage. Voldemort was eventually replaced at LinkedIn by other systems (Espresso, Kafka ecosystem) but rem…

• 15. What Dynamo Influenced

  Dynamo's 2007 paper became one of the most influential distributed systems papers of its era. Here's its legacy:

• Apache Cassandra (2008)

  Facebook (later open-sourced) combined Dynamo's partitioning and replication with BigTable's storage model (SSTables, memtables). Result: a wide-column store with tunable consistency. From Dynamo: - Consistent hashing + virtual nodes (Ca…

• Riak (2009)

  Basho built Riak as a near-clone of Dynamo: - Vector clocks (exposed to clients, with configurable auto-merge strategies) - Pluggable conflict resolution (app can provide merge functions) - Sloppy quorum, hinted handoff - Merkle tree ant…

• Project Voldemort (2009)

  LinkedIn's open-source key-value store, heavily inspired by Dynamo: - Consistent hashing, replication - Vector clocks - Pluggable storage backends (BerkeleyDB, MySQL, in-memory) - Tunable consistency Voldemort was eventually replaced at…

• The "AP Database" Category

  Before Dynamo, most databases were CP or strived for strong consistency. Dynamo legitimized the AP (available, partition-tolerant) category, spawning a generation of NoSQL databases: - Couchbase (eventual consistency mode) - Aerospike (c…

• Academic Impact

  Dynamo popularized: - Tunable consistency as a first-class design axis - Conflict-free replicated data types (CRDTs) (later research formalized what Dynamo's merge semantics hinted at) - Eventual consistency as a viable model (not just a…

• 15.5. Responsibilities of a Dynamo Node

  Because Dynamo is fully decentralized, every node performs three functions:

• 1. Request Coordination

  A node may act as the coordinator for any key. When a client request arrives (get or put), the node: - Determines the preference list for the key - Sends the request to N replicas - Waits for R (read) or W (write) responses - Reconciles…

• 2. Membership and Failure Detection

  Every node tracks: - The full ring (all nodes and their token assignments) - Which nodes are currently reachable (via heartbeats) - Membership changes (nodes joining or leaving) Nodes use gossip protocol to keep this information up-to-da…

• 3. Local Storage

  Each node is responsible for being either the primary or replica store for keys that hash to its token ranges. The node stores (key, value, vector clock) tuples using a pluggable storage engine: - BerkeleyDB Transactional Data Store: For…

• Why This Matters

  The symmetry—every node does everything—eliminates single points of failure. If a node crashes, any other node can immediately take over its coordinator role (via consistent hashing). Clients don't need to know which nodes are up; they j…

• 16. Interview Takeaways

  If you're discussing Dynamo in an interview (system design or distributed systems deep-dive), emphasize these points:

• 1. Why Virtual Nodes?

  Answer: Load balancing. With one token per physical node, the keyspace distribution is uneven (hash randomness). Virtual nodes (100–500 tokens per node) average out to uniform load. Bonus: heterogeneous hardware (stronger nodes claim mor…

• 2. Why Sloppy Quorum?

  Answer: Availability. If a replica is down and you use strict quorum (must write to preference list nodes), writes fail. Sloppy quorum says "write to any W reachable nodes, with hints for the correct ones." The intended replica catches u…

• 3. Why Are Vector Clocks Hard?

  Answer: Application burden. Detecting concurrency is elegant in theory, but reconciling siblings (merge logic) is application-specific and error-prone. Developers often default to "last write wins" (defeating the purpose). Later systems…

• 4. When to Pick AP Over CP?

  Answer: When availability beats consistency for your use case: - Shopping cart: losing the add-to-cart button (downtime) is worse than a rare duplicate item (eventual consistency) - Session state: stale session data is annoying, lost ses…

• 5. How Does Dynamo Handle Partitions?

  Answer: Stays available on both sides. During a network partition, nodes on each side form their own quorum (sloppy if needed) and accept writes. Both sides produce conflicting versions (siblings). When the partition heals, gossip re-mer…

• Worked Example: Hash Ring and Preference List

  Let's walk through a concrete example with a small cluster.

• Setup

  - Cluster: 4 physical nodes (A, B, C, D) - Virtual nodes per physical node: 2 (for simplicity; real systems use 100+) - Hash space: 0–255 (instead of 2^128, for readability)

• Token Assignments

• Ring Visualization (sorted by position)

• Key Placement

  Key: "user-session-42" Hash: MD5("user-session-42") mod 256 = 73 Position 73 falls between 60 (Node B) and 90 (Node C). First token clockwise from 73 is 90 (Node C) → Coordinator = Node C.

• Preference List (N=3)

  Walk clockwise from position 73, collect first 3 distinct physical nodes: 1. Position 90 → Node C (coordinator) 2. Position 120 → Node D 3. Position 180 → Node A 4. ~~Position 210 → Node B~~ (stop, we have 3 distinct) Preference list = […

• Write Path (W=2)

  Client writes put("user-session-42", context, "sessiondata"): 1. Request routed to coordinator Node C 2. C sends write to [C, D, A] 3. C waits for W=2 acknowledgments: - C (local) → ack 1 - D → ack 2 - A → (may or may not respond; doesn'…

• Read Path (R=2)

  Client reads get("user-session-42"): 1. Request routed to coordinator Node C (or any node, which forwards to C) 2. C sends read to [C, D, A] 3. C waits for R=2 responses: - C: version [(C, 5)] - D: version [(C, 5)] 4. C reconciles: both…

• Failure Scenario: Node D Down

  Client writes put("user-session-42", context, "newsessiondata"): 1. Coordinator C tries to write to [C, D, A] 2. D is unreachable 3. Hinted handoff: C picks next node clockwise after A → position 210 → Node B 4. C writes to: - C (local)…

• Conclusion

  Dynamo was a watershed moment in distributed systems. It proved that: - AP is not just a theoretical curiosity—it's a pragmatic choice for real, revenue-critical systems - Decentralized, symmetric architectures can scale—no master, no si…

• References

  - Original paper: DeCandia et al., "Dynamo: Amazon's Highly Available Key-value Store," SOSP 2007. - Cassandra: Lakshman & Malik, "Cassandra: A Decentralized Structured Storage System," 2010. - Vector clocks: Lamport, "Time, Clocks, and…

• Appendix: Glossary

  - AP: Available and Partition-tolerant (CAP theorem). Prioritizes availability over consistency. - CP: Consistent and Partition-tolerant. Prioritizes consistency over availability. - Coordinator: The node responsible for routing requests…