Dynamo: Amazon's Highly Available Key-Value Store¶
DeCandia, G., Hastorun, D., Jampani, M., Kakulapati, G., Lakshman, A., Pilchin, A., Sivasubramanian, S., et al. (2007). Dynamo: Amazon's Highly Available Key-Value Store. Proceedings of the 21st ACM Symposium on Operating Systems Principles, 41(6), 205-220.
Cited by¶
16 citations across 16 artifacts.
Each citation links to the sentence it supports in the citing article.
Primes¶
- Bottleneck
This sourceACM. Biblio reference (distributed-systems cluster, never cited in body).
- Concurrency
- The coordinator's latency is a critical performance bottleneck: too strict (too much synchronization) and throughput suffers; too loose (too little coordination) and correctness fails
This sourceDescribes Dynamo's partitioning, replication, quorum tuning, and eventual consistency under massive concurrent request load. SUPPORTS marker 056 (cloud data-center request router; load balancing and per-client quota as coordination vs throughput trade-off). DOI verified.
- The coordinator's latency is a critical performance bottleneck: too strict (too much synchronization) and throughput suffers; too loose (too little coordination) and correctness fails
- Race Condition
- And in distributed data stores, write-write conflicts under weak consistency are resolved by after-the-fact reconciliation.
This sourceDescribes write-write conflicts under weak (eventual) consistency resolved by after-the-fact reconciliation (vector clocks, merge).
- And in distributed data stores, write-write conflicts under weak consistency are resolved by after-the-fact reconciliation.
- Receptive Field
- Key-range sharding maps onto the identical problem: the input space is the keyspace, each shard owns a bounded range of keys, a router sends each request to the shard whose field contains it, and the prime's gap-and-overlap predictions are exact — a key that falls outside every shard's range produces a lookup failure (silence), and an overlap produces double-ownership contention.
This sourceDescribes consistent-hash key-range partitioning of a keyspace across nodes and re-partitioning (re-sharding) under uneven (hot) load — receptive-field tiling and re-tiling in a distributed store.
- Key-range sharding maps onto the identical problem: the input space is the keyspace, each shard owns a bounded range of keys, a router sends each request to the shard whose field contains it, and the prime's gap-and-overlap predictions are exact — a key that falls outside every shard's range produces a lookup failure (silence), and an overlap produces double-ownership contention.
- Scalability
- Sharding
Domain-specific¶
- CAP Theorem
- Amazon's Dynamo (DeCandia et al., 2007), the system behind the shopping cart
This sourceDynamo's always-writeable design, motivated by Amazon's shopping-cart service. Vector-clock versioning of divergent replicas with later application-level reconciliation, including the cart merge in which deleted items can resurface.
SupportedVerified against the source
- Amazon's Dynamo (DeCandia et al., 2007), the system behind the shopping cart
- CAP Theorem (and variants)
- Rather than block, it reconciles: cart operations are structured so that merging two divergent versions takes their union, and the system tracks causality with vector clocks to detect conflicts
This sourceAmazon's Dynamo, the highly available key-value store built to keep persistent state reliable at massive scale despite continuous component failure.
Supported in partVerified against the publisher's abstract
“Reliability at massive scale is one of the biggest challenges we face at Amazon.com”
- Rather than block, it reconciles: cart operations are structured so that merging two divergent versions takes their union, and the system tracks causality with vector clocks to detect conflicts
- Distributed Data Store
Mechanisms¶
- Anti-Entropy Synchronization
- The classic misuse is treating anti-entropy as a substitute for a durable write path: leaning on it to "eventually" fix under-replicated writes while acking writes only one node ever saw, so a node loss before the next sync loses data outright.
This sourceAllows a Dynamo deployment to acknowledge a write when the write threshold W is configured as low as one replica.
- The classic misuse is treating anti-entropy as a substitute for a durable write path: leaning on it to "eventually" fix under-replicated writes while acking writes only one node ever saw, so a node loss before the next sync loses data outright.
- Delta Reconciliation Patch
- It is the standard way distributed stores heal after partitions — anti-entropy repair walks exactly this diff-and-patch path.
This sourceUses Merkle-tree comparison to identify out-of-sync keys and synchronize divergent replicas during anti-entropy repair.
- It is the standard way distributed stores heal after partitions — anti-entropy repair walks exactly this diff-and-patch path.
- Hinted-Handoff Buffer
- It is what lets a system accept writes at all during a partial outage.
This sourceShows that sloppy quorum with hinted handoff keeps writes available during temporary node and network failures.
- It is what lets a system accept writes at all during a partial outage.
- Merkle-Tree Divergence Scan
- A root-hash match only proves the two agree, even if they agree on the same wrong value, and deciding a winner needs version metadata the scan doesn't carry.
This sourceExplains that matching Merkle roots show replica agreement, while choosing among divergent values requires separate version metadata.
- A root-hash match only proves the two agree, even if they agree on the same wrong value, and deciding a winner needs version metadata the scan doesn't carry.
- Partitioning or Sharding
- A skewed key produces hot slices that saturate while others idle, so the average looks fine while a few keys carry all the pain
This sourceSkewed key-access distributions can produce load imbalance even in a hash-partitioned store.
- A skewed key produces hot slices that saturate while others idle, so the average looks fine while a few keys carry all the pain
- Read Repair
- Read repair only heals data that gets read — cold, rarely-accessed keys can stay silently divergent indefinitely, so a system that relies on it alone will rot in its long tail.
This sourceDocuments Read repair only heals data that gets read; cold, rarely-accessed keys can stay silently divergent indefinitely.
- Read repair only heals data that gets read — cold, rarely-accessed keys can stay silently divergent indefinitely, so a system that relies on it alone will rot in its long tail.
- Read Repair on Access
- Its strength is self-healing consistency for the data that matters most — whatever is actually being read — with no separate job to run, and it guards each individual read from returning a stale answer even mid-convergence, which is what makes reads feel monotonic.
This sourceDynamo read repair opportunistically updates replicas that return stale versions during reads, reducing reliance on a separate anti-entropy pass for those objects.
- Its strength is self-healing consistency for the data that matters most — whatever is actually being read — with no separate job to run, and it guards each individual read from returning a stale answer even mid-convergence, which is what makes reads feel monotonic.
Verification¶
Does it exist? Confirmed. This work's DOI resolves to a registered record, which fixes its identity. That is all it fixes.
Does it back the claim? Read against the text for 2 of 16 citations: 1 supported, 1 supported in part. Each verdict is shown under its citation below, with what in the work backs the sentence.
Support is checked per citation rather than per work — the same source can be cited soundly in one article and wrongly in another. Per-citation recording began recently, so a citation with no recorded check is a gap in the record rather than evidence it went unchecked.
See how references were verified.
Links previously used in the corpus¶
Before the registry existed this work was also linked 2 other ways.
- https://doi.org/10.1145/1323293.1294281 ×3
- https://www.amazon.science/publications/dynamo-amazons-highly-available-key-value-store ×2
Registry ID ref:202ce5f4b8bd · see in the full table