Distributed Data Primitives
Design a distributed key-value store
get(key) and put(key, value). Two operations, and yet Dynamo, Cassandra, and Riak were all born from this question. There is no SQL, no joins, no schema — and somehow it is the hardest design in this course, because every guarantee you want costs you another one.
Start stupid: one machine, one in-memory hash map from key to value. Reads and writes are O(1) and microseconds fast. But RAM is volatile, so every write is first appended to a commit log on disk — a plain append-only file. On restart you replay the log and rebuild the map. Two limits kill this version: the dataset must fit in one machine's RAM, and when that machine dies, everything is gone.
- Place nodes and keys on a hash ring: hash each node to a position, hash each key the same way, and walk clockwise to find its owner.
- Adding or removing a node only moves the keys of its immediate neighbor — about 1/N of the keyspace, not a full reshuffle like key % N would cause.
- Give each physical node several virtual nodes spread around the ring, so load spreads evenly and a big machine can hold more virtual nodes than a small one.
One copy per key still dies with its node, so store each key on N=3 successive nodes on the ring. Now choose W (nodes that must ack a write) and R (nodes that must answer a read). With W=2, R=2, you get W+R>N — the read set and the write set must overlap, so a read sees the latest write as long as no more than one replica is stale. Flip it to W=1, R=1 and both operations fly — but a write acknowledged by node A followed by a read answered by node B returns nothing. You bought speed with other people's data.
Strict quorum refuses a write when one of the N owners is down — availability lost. Sloppy quorum accepts it instead: the write goes to the first W healthy nodes on the ring, even stand-ins that do not own the key, tagged with a hint naming the real owner. When the real owner recovers, the stand-in pushes the write over and deletes its copy — hinted handoff. You stayed available through the failure, and in exchange you accepted that a read during the outage might miss data sitting on a stand-in.
Two clients write the same key at the same time on different replicas — which value wins? Vector clocks answer precisely: each version carries a (node, counter) list, so you can tell whether one version descends from the other or the two diverged, in which case you keep both and let the reader reconcile. Last-write-wins is the lazy default: compare wall-clock timestamps and drop the loser silently. It is one line of code and it deletes data — a slow consumer's cart update can erase a fast one's. Choose LWW only when losing a write is genuinely acceptable.
There is no master here, so nodes find failures by gossip: every second each node exchanges heartbeat and version metadata with a few random peers, and suspicion spreads through the cluster in O(log N) rounds without any central watcher. But gossip only covers liveness. Replicas also drift silently — a dropped handoff, a lost write. Anti-entropy repairs this with Merkle trees: each node hashes its keyspace into a tree, peers compare root hashes, and only when roots differ do they walk down to the differing branches and sync just those keys. You compare a whole partition with one hash instead of shipping every record.
A write lands in the commit log first — a sequential append, the fastest thing a disk does — then into a memtable, a sorted in-memory structure. When the memtable fills, it flushes to disk as an SSTable: an immutable, sorted file. Reads check the memtable, then the SSTables newest to oldest, with Bloom filters skipping files that cannot contain the key. Nothing is ever updated in place, so writes stay sequential I/O at memory speed while the disk only sees appends and periodic compactions that merge old SSTables and drop overwritten versions.
Notice what you never did: you never picked 'the best' configuration. N, W, R, sloppy versus strict, vector clocks versus LWW — each is a dial, and the right position depends on whether your product fears slow responses, stale reads, or lost writes. A distributed key-value store is not a data structure; it is a bundle of negotiated trade-offs.
With N=3, W=1, R=1, what can a client read immediately after its own write was acknowledged — and why? (Possibly the old value or nothing at all: W=1 means a single replica stored the write, and R=1 means the read may be served by a different replica that has not received it yet — W+R=2 is not greater than N=3, so the read and write sets are not guaranteed to overlap.)
The classic mistake is treating 'distributed' as a free upgrade — sprinkle nodes, get scale and reliability. Every guarantee in this lesson is a dial you pay for: strong-ish reads cost latency (waiting for W and R acks), availability during failures costs consistency (sloppy quorum), safe conflict handling costs complexity and payload size (vector clocks), and fast writes cost read amplification and compaction work. If a design claims all of them at once, it is hiding the bill.
You built it layer by layer: one node with a hash map and a commit log, consistent hashing to spread the keyspace, N=3 replicas with W=2 and R=2 for reads that see their writes, sloppy quorum and hinted handoff to survive outages, vector clocks to face concurrency honestly, gossip and Merkle trees to keep the cluster healthy, and an LSM-style write path that keeps writes sequential. That is Dynamo's skeleton — and now it is yours.
Take a datastore your team runs — Redis, Cassandra, even Postgres with replicas — and write down its actual N, W, R behavior: how many copies exist, when a write is acknowledged, and what a read can return during a node failure. Then find one place where you rely on last-write-wins and ask what data it could silently drop. Ten minutes, and you will know your system's real consistency contract for the first time.
Distributed Data Primitives