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 SIGOPS Symposium on Operating Systems Principles (SOSP '07), 41(6), 205-220.

Type

Conference paper

Intellectual base

Primary research

Year

2007

DOI

10.1145/1294261.1294281

Link

https://doi.org/10.1145/1294261.1294281

Cited from

computer_science, logistics_supply_chain, neuroscience

Cited by

7 citations across 7 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.

• 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).

• 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.

• Scalability
  • A common failure is sharding on a key that seemed balanced but turns out to be skewed in production (one customer accounts for 30% of traffic), leading to resource under-utilization on most shards and bottleneck contention on the hot shard
• Sharding
  • Distributed databases: Bigtable, MongoDB, Cassandra, DynamoDB hash or range a row key to assign rows to shards; a query on a key goes directly to the owning shard.

Domain-specific

• Distributed Data Store
  • Google's Bigtable demonstrates a structured store designed for petabytes across thousands of commodity servers. Amazon's Dynamo demonstrates a highly available key-value design with partitioning, replication, version reconciliation, and decentralized membership.

Verification

This reference passed the adversarial substantiation pipeline: it was checked to exist and to support the claim it is attached to. 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 ×1
• https://www.amazon.science/publications/dynamo-amazons-highly-available-key-value-store ×1

Registry ID ref:202ce5f4b8bd · see in the full table