Key-Value Stores & the Dynamo Model
Two operations, get and put, and a design built around scaling that simplicity to enormous throughput.
Intermediate
TopNotchNote
Notes that matter
the simplest possible database interface
A key-value store exposes just two operations —
get(key) and put(key, value) — and treats the value as an opaque blob it doesn't need to understand. No joins, no schema, no query language. That simplicity is the whole point: it's what lets a key-value store scale to a scenario like storing an active session for every one of PlateRoute's currently-online users, where the access pattern is always "fetch by exact ID" and never "find all sessions where...".requirements that shape the design
| Requirement | What it demands |
|---|---|
| Configurable consistency | Different applications tolerate different staleness — the store should let each caller choose, rather than forcing one fixed guarantee on everyone. |
| Always writable | Per the CAP theorem, favoring availability (A) over consistency (C) means a write should nearly always succeed, even mid-partition, accepting that conflicting versions may need to be reconciled later. |
| Hardware heterogeneity | New servers, possibly with more capacity than old ones, should join the cluster without a special migration step. |
| Incremental scalability | Adding or removing a server should cause minimal data movement — this is exactly what consistent hashing is for. |
the Dynamo model
Amazon's Dynamo paper is the most influential design in this space, and its ideas (or close variants) show up in DynamoDB, Cassandra, and Riak. Two pieces make it work:
Consistent hashing with virtual nodes places both keys and servers on a ring, so scaling the cluster up or down moves only a small fraction of keys (see Consistent Hashing for the full mechanism).
Quorum-based reads and writes tune the consistency/availability trade-off per-deployment. With
n replicas of each key, a write must be acknowledged by w of them and a read must query r of them; choosing w + r > n guarantees every read overlaps with at least one replica that has the latest write.
n = 3, w = 1, r = 1 -> fastest, most available, weakest consistency (w+r=2, no overlap guarantee)
n = 3, w = 2, r = 2 -> balanced: w+r=4 > n=3, strong overlap guarantee, moderate latency
n = 3, w = 3, r = 1 -> slow writes, fast strongly-consistent-ish reads
data versioning: what happens when replicas disagree
A store that favors availability over consistency will occasionally have replicas that briefly disagree about a key's value — two concurrent writes during a network partition, for instance. Simply keeping "whichever write has the latest timestamp" is unreliable in a distributed system, because clocks on different machines aren't perfectly synchronized (see Unique ID Generation at Scale for more on why time is tricky here).
The more robust technique is a vector clock: each value carries a small record of which node(s) have contributed to it and how many times. Comparing two versions' vector clocks can determine whether one is a strict successor of the other (safe to discard the older one) or whether they're genuinely concurrent, conflicting writes that need explicit reconciliation — either by a fixed rule (last-write-wins) or by handing both versions back to the application to merge.
when to reach for a key-value store
Good fits: session storage, shopping carts, feature flags, caching layers, and anything else that's naturally "one ID, one blob, read and write by that ID." A poor fit: anything that needs to query by an attribute other than the key ("find all orders over $50") — that's a job for a database with real indexing, like a document or relational store (see SQL vs. NoSQL).