System Design · Lesson 10 of 18
Key-Value Store and Pastebin
Quorums, versioning, LSM trees, bloom filters and a Pastebin built on top.
- Advanced
- 70 min read
- 6 objectives
Before this lessonLesson 9: Rate Limiter
What you will learn
- Partition keys with consistent hashing and virtual nodes
- Tune N, R and W and know what quorum overlap does and does not guarantee
- Detect and resolve conflicts with vector clocks
- Repair replicas with hinted handoff, read repair and Merkle trees
- Explain the LSM write and read paths, bloom filters and compaction
- Design Pastebin: metadata vs object storage, key generation and expiry
Your Progress
0 of 18 lessons 0%
- Lessons0 / 18
- Completed0
- Est. time left~ 16 hours
Progress is saved in this browser. No account needed.
Tip: pressing Next marks this lesson complete automatically.
A distributed key-value store is the engine under half the systems in this course: session stores, shopping carts, feature flags, the short-code table of the URL shortener, the counters behind the rate limiter. Amazon's Dynamo paper, and the systems it inspired (Cassandra, Riak, Voldemort, and the design ideas inside DynamoDB), are the reference design, and "design a key-value store" is really "reinvent Dynamo and explain every trade-off you made on the way".
This lesson has two parts, because interviewers ask them together or separately:
- Part A — the key-value store itself. Partitioning with consistent hashing, replication and quorums, conflict resolution with vector clocks, surviving temporary and permanent failures, gossip membership, and the LSM storage engine on each node. This is the hard, deep half.
- Part B — Pastebin, built on top. A read-heavy product with a public URL per blob of text. Its interesting parts are splitting metadata from content, generating unguessable keys, and expiry — and it is a nice demonstration that once you have a good KV store and object storage, the product layer is thin.
Part A — A Dynamo-style key-value store
Step 1 — Clarify the requirements
A key-value store sounds trivially simple — it is a hash map. The whole interview is about what happens when the hash map is spread over two hundred machines that fail independently. So the requirements you pin down are mostly non-functional.
Functional, in scope
put(key, value),get(key),delete(key). Keys are opaque bytes up to 256 B; values are opaque bytes up to 1 MB. The store never interprets either.- Optional per-key TTL, because sessions, carts and caches all want it and it is cheap to implement inside the storage engine.
- A version context returned by
getand passed back onput, so the store can tell an update from a concurrent overwrite (this matters in Step 8). - A per-request consistency level, so each caller chooses its own point between fast and fresh.
Explicitly out of scope
Range scans and secondary indexes (they break the "hash the key, find the node" model — that is a wide-column or ordered store), multi-key transactions, SQL, and values above 1 MB (those go to object storage with a pointer in the KV — exactly what Pastebin will do in Part B). Say these out loud; each one is a different system.
Non-functional, with numbers
- Scale: 10 billion live keys, average value 1 KB. 2 million reads/s and 500k writes/s at peak across the fleet.
- Latency: p99
getunder 10 ms and p99putunder 20 ms, measured at the coordinator, inside one region. The tail matters more than the mean: one page render can fan out to dozens of keys, and the slowest one sets the page time. - Availability: 99.99%, and specifically always writeable. A shopping cart that rejects "add to cart" because two replicas are unreachable costs money; a cart that briefly shows a stale item does not. This one requirement drives most of the design toward AP.
- Durability: an acknowledged write survives the loss of any single machine, and of any single availability zone.
- Incremental scalability: add one node at a time, with only a proportional slice of data moving.
- Symmetry and decentralisation: no master node, no special coordinator, no single point of failure. Every node runs the same code and can serve any request.
- Heterogeneity: a new box with twice the disk should take twice the data without manual placement.
Step 2 — Back-of-the-envelope estimation
# KV store sizing: a shared store behind sessions, carts, feature flags, pastes
keys = 10_000_000_000 # 10 B live keys
avg_key_bytes = 40
avg_value_bytes = 1_000 # 1 KB typical, 1 MB hard cap
N = 3 # replicas per key
peak_reads = 2_000_000 # ops/s across the fleet
peak_writes = 500_000
raw_tb = keys * (avg_key_bytes + avg_value_bytes) / 1e12
replicated_tb = raw_tb * N
on_disk_tb = replicated_tb * 1.5 # LSM space amplification + headroom
print(f"raw {raw_tb:.1f} TB, x{N} replicas {replicated_tb:.1f} TB, on disk ~{on_disk_tb:.0f} TB")
disk_per_node_tb = 4 # keep nodes small: faster rebuilds
ops_per_node = 40_000 # conservative, SSD, mixed read/write
nodes_for_storage = on_disk_tb / disk_per_node_tb
# every client write becomes N replica writes; a quorum read touches R=2 replicas
replica_ops = peak_writes * N + peak_reads * 2
nodes_for_ops = replica_ops / ops_per_node
print(f"nodes for storage: {nodes_for_storage:.0f} nodes for throughput: {nodes_for_ops:.0f}")
nodes = max(nodes_for_storage, nodes_for_ops) * 1.3 # 30% headroom for failures
print(f"provision ~{nodes:.0f} nodes")
per_node_gb = on_disk_tb * 1e3 / nodes
print(f"data per node: {per_node_gb:.0f} GB -> fits the OS page cache on a 384 GB box")
# how long does re-replicating one dead node take?
rebuild_gbps = 2.0 # streamed from many peers in parallel, throttled
minutes = per_node_gb * 8 / rebuild_gbps / 60
print(f"re-replicate one dead node at {rebuild_gbps} Gbit/s: {minutes:.0f} min")raw 10.4 TB, x3 replicas 31.2 TB, on disk ~47 TB nodes for storage: 12 nodes for throughput: 138 provision ~179 nodes data per node: 262 GB -> fits the OS page cache on a 384 GB box re-replicate one dead node at 2.0 Gbit/s: 17 min
What the numbers actually decide
- The fleet is throughput-bound, not storage-bound. 47 TB fits on a dozen nodes, but 5.5 million replica operations per second (1.5 M replica writes plus 4 M quorum replica reads) needs well over a hundred. That tells you each node holds a few hundred GB — small enough to sit mostly in the OS page cache — which is how p99 reads under 10 ms become realistic.
- Small nodes are a feature. A dead node with 262 GB re-replicates in minutes, streamed in parallel from dozens of peers (thanks to virtual nodes, Step 6). A dead 40 TB node at the same rate takes almost two days, during which a second failure can lose data.
- Every write costs N disk writes. 500k client writes become 1.5 M replica writes. That is why the storage engine must turn random writes into sequential ones (the LSM tree in Step 12). A B-tree doing in-place random updates would need far more hardware.
- 180 nodes means a few failures a week are normal. At that size something is always broken, restarting or slow. Failure handling is not an edge case; it is the main code path.
Step 3 — API design
The client-facing API is tiny. Almost everything interesting lives in the parameters and the error codes.
## Client API (gRPC or HTTP; shown as HTTP for readability)
GET /v1/kv/{key}?consistency=QUORUM
-> 200 { value: <bytes>, context: "<opaque version token>" }
-> 300 { siblings: [{ value, context }, ...] } # concurrent versions: client merges
-> 404 # not found, or tombstoned
-> 503 UNAVAILABLE { needed: 2, alive: 1 } # could not reach R replicas
PUT /v1/kv/{key}?consistency=QUORUM
Headers: X-Context: <token from the last GET> # omit only for blind writes
X-TTL-Seconds: 3600 # optional
Body: <bytes, max 1 MB>
-> 200 { context } # new version token
-> 413 VALUE_TOO_LARGE
-> 503 UNAVAILABLE { needed: 2, acked: 1 } # write MAY exist on 1 replica
DELETE /v1/kv/{key}?consistency=QUORUM
Headers: X-Context: <token>
-> 204 # writes a tombstone, see Step 12
PUT /v1/kv/{key}?if_absent=true # conditional create (Pastebin needs it)
-> 201 | 409 KEY_EXISTS # runs as a Paxos/LWT round, slower
## Consistency levels (per request)
ONE | TWO | QUORUM | LOCAL_QUORUM | EACH_QUORUM | ALL
## Internal node-to-node RPCs (never exposed)
replicate(key, value, clock, hint_for?) read(key) / read_digest(key)
merkle_range(token_range, depth) stream_range(token_range)
gossip(heartbeat_table) deliver_hint(key, value, clock)Four API decisions worth defending
- The version context is opaque. Clients pass back what they received and never construct it. That lets the server change its versioning scheme (vector clock, dotted version vector, timestamp) without breaking clients.
- A 503 on write does not mean "not written". If one replica acked and the quorum failed, that replica holds the value and anti-entropy will eventually spread it. The client must treat the outcome as unknown and retry idempotently. Candidates who say "the write failed, so it's gone" have missed how leaderless replication works.
- Siblings are a first-class response. Returning two values is ugly, but the only alternative is the store silently choosing one and discarding a customer's write.
- Conditional create is a separate, slower path. Put-if-absent needs agreement among replicas (a Paxos round, as Cassandra's lightweight transactions do), roughly four round trips instead of one. Offer it, but do not make every write pay for it.
Step 4 — Data model on each node
The store has no schema, but every record carries metadata, and each node keeps a handful of files per partition. Knowing what is on disk is what lets you reason about reads, repair and deletes later.
-- One stored record (a "cell") --------------------------------------------
key bytes -- opaque, <= 256 B; its hash picks the ring position
value bytes -- opaque, <= 1 MB; empty for a tombstone
clock map -- vector clock {node_id: counter}, e.g. {X:2, Y:1}
write_ts int64 -- coordinator wall clock (micros): used only for LWW mode,
-- tombstone expiry and TTL, never for causality
ttl_expiry int64 NULL -- absolute expiry; expired cells are dropped at compaction
tombstone bool -- a delete is a WRITE of this marker, not an erase
-- On disk, per token range owned by this node ---------------------------------
commitlog/segment-000123.log -- append-only, fsync'd in batches (every 10 ms);
-- replayed on crash to rebuild the memtable
data/range-17/sst-000481-Data.db -- sorted key -> cell blocks, compressed 64 KB blocks
data/range-17/sst-000481-Index.db -- key -> block offset (sparse: every 128th key)
data/range-17/sst-000481-Filter.db -- bloom filter over every key in the file
data/range-17/sst-000481-Summary.db -- sample of the index, held in RAM
hints/node-B/*.hint -- writes held for a dead replica (Step 9)
merkle/range-17.tree -- hash tree for anti-entropy (Step 10)
-- In memory ----------------------------------------------------------------------
memtable -- sorted map (skip list) of recent writes, flushed at ~128 MB
ring view -- token -> node map, versioned, learned by gossip (Step 11)
key cache / row cache -- hot keys' block offsets / whole valuesThree modelling decisions to explain
- Deletes are writes. In a leaderless replicated system, erasing a key on two replicas while the third is down means the third will later "repair" the others and bring the key back to life. The tombstone is what tells repair "this was deleted on purpose". It must live longer than the longest outage you tolerate (commonly 10 days, called
gc_grace), then compaction removes it. - The wall-clock timestamp is metadata, not truth. Clocks across 180 machines drift by milliseconds and occasionally by seconds. Use them for TTLs and for last-write-wins mode where the application accepts the loss; never to decide which of two concurrent writes "happened first".
- Files are per token range. When a range moves to a new node, the old owner can stream whole files rather than scanning and filtering every key — which is what makes adding a node take minutes instead of hours.
Step 5 — High-level design
fan-out, quorum wait, read repair] PART[Partitioner
consistent hash ring + vnodes] REP[Replication manager
preference list, sloppy quorum] HH[Hinted handoff store] MEM[Membership + gossip
failure detector] AE[Anti-entropy
Merkle trees] SE[Storage engine
commit log, memtable, SSTables] CO --> PART CO --> REP REP --> HH CO --> SE MEM --> PART AE --> SE end CO -->|replicate / read| P1[Peer replica 1] CO -->|replicate / read| P2[Peer replica 2] MEM <-->|gossip every 1 s| P1 AE <-->|compare trees| P2
No master. Any node can coordinate any request; the client driver usually picks a node that owns the key to save a hop. Gossip keeps every node's ring view in step, and background anti-entropy repairs whatever the foreground path missed.
What each module owns
- Request coordinator — receives a client request, looks up the key's replicas, sends to all N in parallel, waits for W acks or R replies, reconciles versions, triggers read repair, applies the client timeout.
- Partitioner — the ring: key → token → ordered list of physical nodes. Pure function of the ring view.
- Replication manager — builds the preference list (skipping duplicate physical boxes and, ideally, duplicate racks and AZs), substitutes stand-ins when an owner is down.
- Hinted handoff store — durable queue of writes held for unreachable replicas, replayed when they return.
- Membership and failure detection — gossip protocol, heartbeat table, suspicion levels, seed nodes. Decides who is up, never who owns what (ownership changes are explicit admin operations).
- Anti-entropy — periodically builds Merkle trees per token range and exchanges them with other replicas, streaming only the differing ranges.
- Storage engine — the single-node database: commit log, memtable, SSTables, bloom filters, compaction, TTL expiry. Pluggable (Dynamo itself supported several engines).
The most common wrong answer at this point is "a master node holds the key-to-server map, and clients ask it first". That master is the single point of failure and the throughput bottleneck the requirements forbid. The ring is small enough (a few hundred nodes × 256 tokens) for every node and every client to hold a full copy.
Step 6 — Partitioning with consistent hashing
Why not hash(key) % N
Modulo hashing spreads keys evenly and is one line of code, but the moment N changes almost every key maps somewhere else. Going from 4 servers to 5 moves about 80% of the data — for our store, 37 TB of network traffic to add one box, while every cached location is wrong. The same happens when a server dies and N shrinks.
The ring
Hash both keys and nodes onto the same large circular space (say 0 to 264−1). A key belongs to the first node found walking clockwise from its position. Add a node and it takes over only the arc between itself and its predecessor; every other key stays put. Remove one and only its arc moves, to its successor. On average only K / N keys move.
Why a plain ring is not enough: virtual nodes
With one position per node, arcs are wildly uneven (random points on a circle clump), one node can end up owning three times its share, and when a node dies its entire load lands on a single successor, which may then fall over too. The fix is to give every physical node many positions — virtual nodes or tokens, typically 128 to 256 each. Now each node owns many small arcs scattered around the ring, so:
- load evens out statistically (the more tokens, the tighter the spread);
- when a node dies, its arcs are inherited by many different successors, so the extra load and the re-replication traffic are spread across the cluster;
- a bigger box simply gets more tokens — heterogeneity handled by one weight;
- a new node takes a little from everyone rather than a lot from one neighbour.
Here is a ring with virtual nodes, run against 50,000 keys. It measures three things: how much data moves on a resize (modulo vs ring), where the moved keys come from, and how the number of virtual nodes affects balance.
import bisect, hashlib
from collections import Counter
def h(s: str) -> int:
"""64-bit position on the ring. md5 is fine here: we need spread, not secrecy."""
return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")
class Ring:
def __init__(self, vnodes: int = 128):
self.vnodes = vnodes
self.tokens: list[int] = [] # sorted ring positions
self.owner: dict[int, str] = {} # position -> physical node
def add(self, node: str, weight: float = 1.0):
for i in range(int(self.vnodes * weight)): # bigger box = more tokens
t = h(f"{node}#{i}")
bisect.insort(self.tokens, t)
self.owner[t] = node
def remove(self, node: str):
self.tokens = [t for t in self.tokens if self.owner[t] != node]
self.owner = {t: n for t, n in self.owner.items() if n != node}
def preference_list(self, key: str, n: int = 3) -> list[str]:
"""Walk clockwise from hash(key); collect the first n DISTINCT physical nodes."""
i = bisect.bisect_right(self.tokens, h(key)) % len(self.tokens)
out = []
while len(out) < n:
node = self.owner[self.tokens[i]]
if node not in out: # skip vnodes of a box we already have
out.append(node)
i = (i + 1) % len(self.tokens)
return out
keys = [f"user:{i}" for i in range(50_000)]
# --- 1. naive modulo: add a 5th server and see what moves ---
before = {k: h(k) % 4 for k in keys}
after = {k: h(k) % 5 for k in keys}
moved = sum(before[k] != after[k] for k in keys)
print(f"mod-N 4 -> 5 servers: {moved/len(keys):.1%} of keys move")
# --- 2. ring: same change ---
ring = Ring(vnodes=128)
for n in "ABCD":
ring.add(n)
before = {k: ring.preference_list(k, 1)[0] for k in keys}
ring.add("E")
after = {k: ring.preference_list(k, 1)[0] for k in keys}
moves = Counter((before[k], after[k]) for k in keys if before[k] != after[k])
print(f"ring 4 -> 5 servers: {sum(moves.values())/len(keys):.1%} of keys move")
print(" every move goes TO the new node:", all(dst == "E" for _, dst in moves))
print(" taken from:", dict(sorted((src, c) for (src, _), c in moves.items())))
# --- 3. why virtual nodes: load spread with 1 token vs 128 per box ---
for v in (1, 16, 128):
r = Ring(vnodes=v)
for n in "ABCDE":
r.add(n)
load = Counter(r.preference_list(k, 1)[0] for k in keys)
share = [load[n] / len(keys) for n in "ABCDE"]
print(f"vnodes={v:>3}: busiest {max(share):.1%} idlest {min(share):.1%}")
print("replicas for user:42 ->", ring.preference_list("user:42", 3))mod-N 4 -> 5 servers: 80.0% of keys move
ring 4 -> 5 servers: 18.9% of keys move
every move goes TO the new node: True
taken from: {'A': 3146, 'B': 1374, 'C': 2432, 'D': 2495}
vnodes= 1: busiest 40.0% idlest 1.3%
vnodes= 16: busiest 27.8% idlest 14.7%
vnodes=128: busiest 22.6% idlest 16.4%
replicas for user:42 -> ['D', 'E', 'B']
Reading the output
- 80% vs 19%. The ring moves close to the theoretical minimum (1/5 = 20%) and every moved key goes to the new node — no key is shuffled between old nodes. With modulo, keys shuffle between servers that did not change at all.
- The new node takes from all four old ones. That is the virtual-node effect: node E's 128 tokens are scattered, so the streaming load is shared. With one token each, E would take everything from a single neighbour.
- Balance improves with more tokens. One token per node gives a 40% / 1% split — useless. 128 tokens gets within a few points of the ideal 20%. Beyond ~256 the gain is small and the ring metadata and repair bookkeeping grow, which is why real systems settle in that range (and newer ones use smarter token allocation rather than more random tokens).
- The preference list skips duplicates. Walking clockwise from a key, consecutive tokens can belong to the same box; the replica list must contain N distinct physical nodes, and in production also distinct racks or availability zones, or one power failure takes out all three copies.
node D"] --> T2["token 0x3f9c
node D again - skip"] T2 --> T3["token 0x4102
node E"] T3 --> T4["token 0x44e0
node B"] end T1 -.-> R1[Replica 1: D] T3 -.-> R2[Replica 2: E] T4 -.-> R3[Replica 3: B]
The preference list for a key is the first N distinct physical nodes clockwise from its hash. A second token belonging to D is skipped; with rack awareness, a node in the same rack as D would be skipped too.
Wrong answers to avoid: "range partitioning by key" (lexicographic ranges create hot spots — every key starting with user: lands together, and time-ordered keys all hit the last range); "a lookup table from key to node" (billions of entries, and it needs a master); and "consistent hashing solves hot keys" (it balances the key space, not the traffic — one celebrity key still lands on one set of three replicas; see Step 16).
Step 7 — Replication and quorums (N, R, W)
Each key is stored on the N nodes of its preference list (N = 3 is the usual default: survives one failure with room to spare, and fits one replica per AZ). The coordinator sends every write to all N replicas in parallel and reports success after W of them acknowledge. A read asks replicas and returns after R reply, choosing the newest version among them.
W + R > Nmeans every read set overlaps every successful write set in at least one node, so (in the absence of the complications below) a read that starts after a write is acknowledged will see it. With N = 3 the classic choice is W = 2, R = 2.W + R ≤ Ntrades that guarantee for speed and availability: the read may hit only replicas the write has not reached yet.- W is the durability-vs-write-latency dial; R is the freshness-vs-read-latency dial. Both are also availability dials: a request fails if fewer than W (or R) replicas are reachable.
Rather than argue in the abstract, simulate it. Each trial writes a key to three replicas whose apply latencies are random (mean 4 ms), then reads the key immediately. Each replica is down with probability 5%. The coordinator acks the write at the W-th fastest replica and answers the read from the R fastest replies.
import random
def trial(rng, N, W, R, p_down, mean_ms=4.0):
"""One write followed immediately by one read of the same key.
Returns (write_ok, write_ms, read_ok, read_ms, stale)."""
up = [rng.random() > p_down for _ in range(N)]
# time at which each replica has APPLIED the write (inf if it is down)
applied = [rng.expovariate(1 / mean_ms) if u else float("inf") for u in up]
acks = sorted(a for a in applied if a != float("inf"))
if len(acks) < W:
return False, None, False, None, False # coordinator returns an error
t_ack = acks[W - 1] # client hears "OK" at the W-th ack
# the client reads right away; each live replica answers after its own delay
replies = []
for i in range(N):
if not up[i]:
continue
rtt = rng.expovariate(1 / mean_ms)
arrives = t_ack + rtt / 2 # when the read hits replica i
has_new = applied[i] <= arrives
replies.append((rtt, has_new))
replies.sort()
if len(replies) < R:
return True, t_ack, False, None, False
first_r = replies[:R] # coordinator waits for R replies
stale = not any(new for _, new in first_r) # newest version among R wins
return True, t_ack, True, first_r[-1][0], stale
def p99(xs):
xs = sorted(xs)
return xs[int(len(xs) * 0.99)]
N, TRIALS = 3, 50_000
print(" W R W+R>N write p99 read p99 stale write fails read fails")
for W, R in [(1, 1), (1, 2), (2, 1), (2, 2), (3, 1), (1, 3)]:
rng = random.Random(7) # same failures for every config
res = [trial(rng, N, W, R, p_down=0.05) for _ in range(TRIALS)]
wl = [r[1] for r in res if r[0]]
rl = [r[3] for r in res if r[2]]
stale = sum(r[4] for r in res) / sum(r[2] for r in res)
wfail = sum(not r[0] for r in res) / TRIALS
rfail = sum(r[0] and not r[2] for r in res) / TRIALS
print(f" {W} {R} {str(W + R > N):5} {p99(wl):6.1f} ms {p99(rl):5.1f} ms"
f" {stale:6.1%} {wfail:10.2%} {rfail:9.2%}")W R W+R>N write p99 read p99 stale write fails read fails 1 1 False 7.0 ms 6.9 ms 54.5% 0.02% 0.00% 1 2 False 7.0 ms 13.9 ms 17.5% 0.02% 0.68% 2 1 False 14.4 ms 6.8 ms 24.2% 0.72% 0.00% 2 2 True 14.4 ms 14.1 ms 0.0% 0.72% 0.00% 3 1 True 23.1 ms 6.2 ms 0.0% 13.89% 0.00% 1 3 True 7.0 ms 22.6 ms 0.0% 0.02% 14.01%
What the simulation shows
- Every configuration with
W + R > Nhas zero stale reads; every configuration without it has plenty. The rule is real, not folklore. - The stale rates without overlap are brutal here (54% for 1/1) because the read is fired the instant the write returns, while two replicas are still applying it. Real traffic spaces reads out more, so stale reads are rarer — but "read my own write straight after saving" is exactly the case users notice.
- Latency follows the slowest replica you wait for. Waiting for 1 of 3 gives the p99 of the fastest; waiting for all 3 gives the p99 of the slowest — more than 3x worse. Quorum configurations sit in between.
W = 3orR = 3destroys availability. With a 5% per-replica failure rate, requiring all three fails about 14% of requests. Requiring 2 of 3 fails well under 1%. This is why "ALL" is almost never the right answer.- The shapes to remember:
W=2, R=2balanced default;W=1, R=3for write-heavy logs you rarely read;W=3, R=1for read-mostly config that must be fresh (and can tolerate failed writes);W=1, R=1for caches and metrics where stale is fine.
Step 8 — Versioning and conflict resolution
Because any node can coordinate a write and replicas can be partitioned from each other, two clients can update the same key at the same time through different coordinators, and both writes succeed. The store now has two versions. There are two schools of thought on what to do.
Option 1: last-write-wins (LWW)
Attach a timestamp; the highest one wins everywhere. Simple, no sibling handling in the client, and the default in Cassandra. The cost: one of two concurrent writes is silently discarded, and with clock skew the "later" write can be the one that actually happened first. Fine for "set the user's last-seen time", wrong for a shopping cart where both adds must survive.
Option 2: vector clocks and siblings
A vector clock is a map of {node: counter} attached to each version. The coordinator that handles a write increments its own entry. Version A descends version B if every counter in A is at least the one in B — then A has seen B and B can be thrown away. If neither descends the other, the writes were concurrent: both are kept as siblings and returned to the next reader, who merges them and writes the merged value back with a clock that dominates both.
from dataclasses import dataclass
Clock = dict[str, int] # node id -> counter
def descends(a: Clock, b: Clock) -> bool:
"""True if a has seen everything b has seen (a >= b on every entry)."""
return all(a.get(n, 0) >= c for n, c in b.items())
def compare(a: Clock, b: Clock) -> str:
if a == b:
return "equal"
if descends(a, b):
return "a newer"
if descends(b, a):
return "b newer"
return "CONCURRENT" # neither saw the other: a real conflict
def bump(clock: Clock, node: str) -> Clock:
c = dict(clock)
c[node] = c.get(node, 0) + 1
return c
@dataclass
class Version:
value: object
clock: Clock
def reconcile(versions: list[Version]) -> list[Version]:
"""Drop every version that some other version descends from.
Whatever survives are siblings the client must merge."""
keep = []
for v in versions:
dominated = any(o is not v and descends(o.clock, v.clock) and o.clock != v.clock
for o in versions)
if not dominated and all(k.clock != v.clock for k in keep):
keep.append(v)
return keep
# A shopping cart. Coordinator X handles the first write.
v1 = Version({"milk"}, bump({}, "X")) # {X:1}
v2 = Version(v1.value | {"eggs"}, bump(v1.clock, "X")) # {X:2}, descends v1
print("v2 vs v1:", compare(v2.clock, v1.clock))
# A partition. Two clients both read v2, then write through different coordinators.
v3 = Version(v2.value | {"bread"}, bump(v2.clock, "Y")) # {X:2, Y:1}
v4 = Version(v2.value - {"milk"}, bump(v2.clock, "Z")) # {X:2, Z:1}
print("v3 vs v4:", compare(v3.clock, v4.clock))
siblings = reconcile([v1, v2, v3, v4])
for s in siblings:
print(" sibling", sorted(s.value), s.clock)
# The client (or application merge function) resolves and writes back.
merged_clock = {n: max(s.clock.get(n, 0) for s in siblings)
for s in siblings for n in s.clock}
merged = Version(v3.value | v4.value, bump(merged_clock, "X")) # union: the Dynamo cart rule
print("merged:", sorted(merged.value), merged.clock)
print("merged vs v3:", compare(merged.clock, v3.clock),
"| merged vs v4:", compare(merged.clock, v4.clock))
print("note: union resurrected", sorted(v2.value - v4.value), "- deletes need tombstones")
# Last-write-wins on wall clocks, for contrast: one version is silently discarded.
lww = max([(1_700_000_000_120, v3), (1_700_000_000_118, v4)], key=lambda t: t[0])[1]
print("LWW keeps:", sorted(lww.value), "and drops the other write with no error")v2 vs v1: a newer
v3 vs v4: CONCURRENT
sibling ['bread', 'eggs', 'milk'] {'X': 2, 'Y': 1}
sibling ['eggs'] {'X': 2, 'Z': 1}
merged: ['bread', 'eggs', 'milk'] {'X': 3, 'Y': 1, 'Z': 1}
merged vs v3: a newer | merged vs v4: a newer
note: union resurrected ['milk'] - deletes need tombstones
LWW keeps: ['bread', 'eggs', 'milk'] and drops the other write with no error
What to take from the example
- The store detects conflicts; the application resolves them. Only the application knows that two carts should be unioned, two counters summed, or two profile edits merged field by field.
- Union-merge has a known flaw: the removed "milk" came back, because the merge cannot tell "never added" from "deleted". Real carts track removals explicitly (a set of added items and a set of removed items), which is the idea behind an OR-Set CRDT. CRDTs — counters, sets and maps with a merge that is mathematically guaranteed to converge — are the modern answer when you want conflicts without a human-written merge function (Riak ships them as data types).
- Clocks grow. Every coordinator that ever touched a key adds an entry. Implementations cap the size (Dynamo truncated the oldest entries past about ten), accepting that truncation occasionally makes a descendant look concurrent — a spurious sibling, never lost data. Dotted version vectors, used by Riak, fix the related "sibling explosion" problem when many clients write through the same node.
- LWW is still a legitimate choice — state it as a per-table option. Immutable data (write once, never update, like a paste) cannot conflict at all, so it pays nothing for LWW.
Step 9 — Temporary failures: sloppy quorum and hinted handoff
A strict quorum only counts acks from the key's N home replicas. If two of the three are unreachable, a W = 2 write fails — the store refuses writes during precisely the kind of partial outage "always writeable" was meant to survive.
A sloppy quorum instead takes the first N healthy nodes walking the ring. If replica B is down, the write goes to the next node, D, tagged with a hint: "this belongs to B". D keeps hinted writes in a separate local store. When gossip reports B alive again, D replays the hints to B and deletes its copy. This is hinted handoff.
from collections import defaultdict
RING = ["A", "B", "C", "D", "E"] # clockwise order for this key's range
N, W = 3, 2
up = {n: True for n in RING}
store = defaultdict(dict) # node -> {key: value}
hints = defaultdict(list) # holder -> [(intended_owner, key, value)]
def write(key, value):
owners = RING[:N] # the key's real preference list: A, B, C
targets, acks = [], 0
spare = iter(n for n in RING[N:] if up[n]) # next healthy nodes on the ring
for owner in owners:
if up[owner]:
store[owner][key] = value; acks += 1
else:
stand_in = next(spare, None) # sloppy quorum: borrow a neighbour
if stand_in:
store[stand_in][key] = value
hints[stand_in].append((owner, key, value)); acks += 1
targets.append(f"{stand_in}(hint for {owner})")
continue
targets.append(owner)
return acks >= W, targets
def recover(node):
up[node] = True
for holder in list(hints):
keep = []
for owner, k, v in hints[holder]:
if owner == node: # hand the write back, then forget it
store[owner][k] = v
store[holder].pop(k, None)
else:
keep.append((owner, k, v))
hints[holder] = keep
up["B"] = False
ok, where = write("cart:9", ["milk", "eggs"])
print("B down -> write ok:", ok, "| stored on:", where)
print("B has cart:9?", "cart:9" in store["B"], "| D holds hints:", hints["D"])
recover("B")
print("B back -> B has cart:9?", "cart:9" in store["B"],
"| D hints left:", hints["D"], "| D copy dropped:", "cart:9" not in store["D"])
up["B"] = up["C"] = up["D"] = up["E"] = False
print("4 of 5 down -> write ok:", write("cart:10", ["tea"])[0], "(only A acked; W=2 not met)")B down -> write ok: True | stored on: ['A', 'D(hint for B)', 'C']
B has cart:9? False | D holds hints: [('B', 'cart:9', ['milk', 'eggs'])]
B back -> B has cart:9? True | D hints left: [] | D copy dropped: True
4 of 5 down -> write ok: False (only A acked; W=2 not met)
The caveats an interviewer expects you to know
- Sloppy quorums break the overlap argument. A W = 2 write that landed on A and D, followed by an R = 2 read from B and C once B is back but before the hint is delivered, returns stale data even though W + R > N. Availability was bought with consistency — say so.
- Hints are bounded. Stand-ins keep hints for a window (Cassandra's default is three hours). A node down longer than that will not be caught up by hints and needs a full anti-entropy repair (Step 10) when it returns.
- A write can still fail. If fewer than W nodes in the whole ring neighbourhood are healthy, even the sloppy quorum fails — the last line of the output. Sloppy means "flexible about which nodes", not "accepts one ack".
- Hinted handoff is a latency hedge, not a durability guarantee. If the stand-in dies while holding hints, those copies are lost; the other acked replicas still have the value, and anti-entropy restores the third.
Step 10 — Permanent failures: read repair and Merkle-tree anti-entropy
Hints cover short outages. Longer outages, lost hints, disk corruption and dropped messages leave replicas quietly disagreeing, and the store needs two repair mechanisms:
- Read repair (foreground, opportunistic). When a coordinator gathers R replies and sees that one replica returned an older version, it sends that replica the newest one. Cheap, but it only fixes keys that are read — cold keys can stay divergent forever.
- Anti-entropy (background, exhaustive). Replicas periodically compare everything they hold for a shared token range and fix differences. The naive way — send every key — means shipping hundreds of GB to find three bad rows. The trick is a Merkle tree.
Split each token range into many slices. Hash the contents of each slice to make the leaves; hash pairs of children to make each parent, up to a single root. Two replicas exchange roots: equal roots mean the whole range is identical, and they are done after comparing one hash. Otherwise they compare the two children, and descend only into the halves that differ.
import hashlib
def H(b: bytes) -> bytes:
return hashlib.sha256(b).digest()
BUCKETS = 1024 # leaves: the key range split into 1024 slices
def bucket_of(key: str) -> int:
return int.from_bytes(H(key.encode())[:4], "big") % BUCKETS
def build(data: dict[str, str]) -> list[list[bytes]]:
"""Level 0 = leaves (hash of every key/value in that slice), last level = root."""
slices = [[] for _ in range(BUCKETS)]
for k in sorted(data):
slices[bucket_of(k)].append(f"{k}={data[k]}".encode())
level = [H(b"|".join(s)) for s in slices]
tree = [level]
while len(level) > 1:
level = [H(level[i] + level[i + 1]) for i in range(0, len(level), 2)]
tree.append(level)
return tree
def diff(a, b):
"""Walk down from the root, descending only into children whose hashes differ.
Returns (differing leaf buckets, number of hashes exchanged)."""
top = len(a) - 1
frontier, exchanged = [0], 1
for lvl in range(top, 0, -1):
nxt = []
for i in frontier:
for c in (2 * i, 2 * i + 1):
exchanged += 1
if a[lvl - 1][c] != b[lvl - 1][c]:
nxt.append(c)
frontier = nxt
return frontier, exchanged
replica_a = {f"k{i}": f"v{i}" for i in range(100_000)}
replica_b = dict(replica_a)
replica_b["k1234"] = "STALE" # missed an update
del replica_b["k99999"] # missed a write entirely
replica_b["k75000"] = "v75000-old"
ta, tb = build(replica_a), build(replica_b)
print("roots equal?", ta[-1][0] == tb[-1][0], " tree depth:", len(ta) - 1)
buckets, exchanged = diff(ta, tb)
print("differing buckets:", buckets)
print(f"hashes compared: {exchanged} of {sum(len(l) for l in ta)}")
keys_to_sync = [k for k in replica_a if bucket_of(k) in buckets]
print(f"keys streamed: {len(keys_to_sync)} instead of {len(replica_a):,}")
fix = sorted(k for k in keys_to_sync if replica_a.get(k) != replica_b.get(k))
print("actually different:", fix)roots equal? False tree depth: 10 differing buckets: [47, 62, 1001] hashes compared: 47 of 2047 keys streamed: 287 instead of 100,000 actually different: ['k1234', 'k75000', 'k99999']
Why this is the right tool
- Cost scales with the difference, not the data. Three bad keys out of 100,000 were found by comparing 47 hashes (out of 2,047 in the tree) and streaming 287 keys — the three slices that contained them. With identical replicas, the cost is one hash.
- Leaf count is a knob. More leaves means fewer keys streamed per mismatch but a bigger tree to build and keep. Trees are built per token range so a range's tree can be rebuilt independently.
- Building the tree is the expensive part — it reads every key in the range. That is why repair runs as a scheduled, throttled background job (for example, each range once a week, well inside
gc_graceso tombstones reach every replica before they are purged). - Range changes invalidate trees. When a node joins and ranges shift, affected trees must be rebuilt — another reason to add capacity gradually.
Step 11 — Membership and failure detection with gossip
With no master, how does every node learn that node 17 died, or that node 181 joined? A central registry would be the single point of failure again, and all-to-all heartbeats cost N2 messages per second (32,000 per second for 180 nodes, growing fast).
Instead, every node runs a gossip protocol: once a second it picks a random peer and the two exchange their membership tables — for every node, a heartbeat counter and the last time it was seen increasing. Each node bumps its own counter every round. News spreads like an epidemic: the number of informed nodes roughly doubles each round, so it reaches everyone in about log2(N) rounds, with each node sending just one message per round.
import math, random
def gossip_rounds(n: int, seed: int = 1) -> int:
"""Push-pull gossip: every round, every node swaps state with one random peer.
Returns rounds until all n nodes know that 'node 17 is DOWN'."""
rng = random.Random(seed)
knows = [False] * n
knows[0] = True # the node that first suspected it
rounds = 0
while not all(knows):
rounds += 1
snapshot = knows[:] # exchanges within a round are simultaneous
for a in range(n):
b = rng.randrange(n)
if snapshot[a] or snapshot[b]:
knows[a] = knows[b] = True
return rounds
for n in (10, 100, 1_000, 10_000):
r = gossip_rounds(n)
print(f"{n:>6} nodes: {r:2d} rounds (log2 n = {math.log2(n):4.1f})")
# Heartbeat-based failure detection on top of gossip
T_FAIL, T_CLEANUP = 10, 60 # seconds without a heartbeat bump
def status(last_bump_age_s: float) -> str:
if last_bump_age_s < T_FAIL:
return "ALIVE"
return "SUSPECT" if last_bump_age_s < T_CLEANUP else "REMOVED from ring view"
for age in (2, 12, 75):
print(f"heartbeat counter unchanged for {age:>2}s -> {status(age)}")10 nodes: 3 rounds (log2 n = 3.3) 100 nodes: 6 rounds (log2 n = 6.6) 1000 nodes: 9 rounds (log2 n = 10.0) 10000 nodes: 12 rounds (log2 n = 13.3) heartbeat counter unchanged for 2s -> ALIVE heartbeat counter unchanged for 12s -> SUSPECT heartbeat counter unchanged for 75s -> REMOVED from ring view
Details that make gossip work in production
- Seed nodes. A few well-known nodes that everyone gossips with occasionally. A new node contacts a seed to join; seeds also prevent the cluster from splitting into two groups that each think the other is dead. Seeds are not masters — they hold no special data.
- Suspicion, not verdicts. Fixed timeouts are brittle: a long GC pause looks like death. Cassandra uses a phi accrual detector, which learns each peer's normal heartbeat interval and outputs a suspicion level that rises continuously the longer a heartbeat is overdue. The coordinator simply stops sending to highly suspected nodes; nothing is moved.
- Transient failure is not membership change. Dynamo's key insight: a node being unreachable is handled by sloppy quorum and hints, not by reassigning its ranges. Permanently adding or removing a node is an explicit operator action, gossiped as a new ring version. Otherwise a flapping network would trigger terabytes of pointless data movement.
- Local view. Node A may consider C down while B considers it up — failure detection is per observer. That is acceptable because the only consequence is where A routes its own requests.
Step 12 — The storage engine: LSM trees
Each replica is its own single-node database. From Step 2, it must absorb heavy random writes, which a B-tree handles poorly: every update is a read-modify-write of a random page. A log-structured merge tree turns every write into sequential I/O.
The write path inside one node
- Append to the commit log (write-ahead log). Sequential, and fsync'd in small batches (every few ms) so one disk flush covers hundreds of writes. This is the durability point: after a crash the log is replayed.
- Insert into the memtable, an in-memory sorted structure (a skip list). The write is now complete and the replica acks. No disk seek has happened.
- Flush: when the memtable reaches its size limit (say 128 MB), it is frozen, a new one takes writes, and the frozen one is written out as an immutable, sorted SSTable in one sequential pass. The matching commit log segments can then be deleted.
- Compact: in the background, SSTables are merged. Newer versions of a key replace older ones, expired TTL cells and old-enough tombstones are dropped, and the number of files a read must check is kept small.
The read path inside one node
- Check the memtable (freshest data).
- Then SSTables from newest to oldest. For each, ask its bloom filter first: "definitely not here" skips the file with zero I/O; "maybe here" costs one index lookup and one block read.
- Stop at the first hit — it is the newest version. A tombstone means "deleted": return not-found and stop, because older files may still contain the deleted value.
A bloom filter is a bit array plus k hash functions. Adding a key sets k bits; checking tests them. If any bit is 0 the key was never added — certain. If all are 1 it probably was — with a tunable false-positive rate (about 10 bits per key gives 1%). It can never give a false negative, which is exactly the property a "should I bother reading this file?" check needs.
import bisect, hashlib, math
class Bloom:
"""m bits, k hash functions. 'No' is certain; 'maybe' can be wrong."""
def __init__(self, n_items: int, fp_rate: float = 0.01):
self.m = max(8, int(-n_items * math.log(fp_rate) / math.log(2) ** 2))
self.k = max(1, round(self.m / n_items * math.log(2)))
self.bits = 0
def _idx(self, key: str):
d = hashlib.sha256(key.encode()).digest()
h1, h2 = int.from_bytes(d[:8], "big"), int.from_bytes(d[8:16], "big")
return [(h1 + i * h2) % self.m for i in range(self.k)] # double hashing
def add(self, key):
for i in self._idx(key):
self.bits |= 1 << i
def might_contain(self, key):
return all(self.bits >> i & 1 for i in self._idx(key))
TOMBSTONE = object() # a delete is a write of "nothing"
class SSTable:
"""Immutable, sorted, on 'disk'. Built once from a memtable, never edited."""
def __init__(self, items: dict):
self.keys = sorted(items)
self.vals = [items[k] for k in self.keys]
self.bloom = Bloom(len(self.keys))
for k in self.keys:
self.bloom.add(k)
def get(self, key):
i = bisect.bisect_left(self.keys, key) # a sparse index + one block read
if i < len(self.keys) and self.keys[i] == key:
return True, self.vals[i]
return False, None
class LSM:
def __init__(self, memtable_limit=1000):
self.wal: list[tuple] = [] # append-only commit log (fsync'd in real life)
self.mem: dict = {} # memtable (a skip list / red-black tree for real)
self.tables: list[SSTable] = [] # newest first
self.limit = memtable_limit
self.disk_reads = 0
def put(self, key, value):
self.wal.append((key, value)) # 1. durable first: sequential append
self.mem[key] = value # 2. then the in-memory sorted structure
if len(self.mem) >= self.limit:
self.flush()
def delete(self, key):
self.put(key, TOMBSTONE)
def flush(self):
self.tables.insert(0, SSTable(self.mem)) # one sequential write
self.mem, self.wal = {}, [] # log can be truncated now
def get(self, key):
if key in self.mem: # newest data first
v = self.mem[key]
return None if v is TOMBSTONE else v
for t in self.tables: # then newest table to oldest
if not t.bloom.might_contain(key):
continue # skipped with zero I/O
self.disk_reads += 1
found, v = t.get(key)
if found:
return None if v is TOMBSTONE else v
return None
def compact(self):
"""Merge all tables, newest version wins, tombstones dropped at the bottom."""
merged = {}
for t in reversed(self.tables): # oldest first, newer overwrite
merged.update(zip(t.keys, t.vals))
live = {k: v for k, v in merged.items() if v is not TOMBSTONE}
self.tables = [SSTable(live)] if live else []
return len(merged) - len(live)
db = LSM(memtable_limit=1000)
for i in range(10_000):
db.put(f"user:{i:05d}", {"v": 1})
for i in range(0, 10_000, 10):
db.put(f"user:{i:05d}", {"v": 2}) # overwrites land in NEW tables
for i in range(0, 10_000, 100):
db.delete(f"user:{i:05d}")
print("sstables before compaction:", len(db.tables), "| memtable:", len(db.mem))
db.disk_reads = 0
print("get user:00010 ->", db.get("user:00010"), "| disk reads:", db.disk_reads)
db.disk_reads = 0
print("get user:00100 ->", db.get("user:00100"), "(deleted) | disk reads:", db.disk_reads)
db.disk_reads = 0
for i in range(2_000):
db.get(f"nope:{i}")
print(f"2000 lookups of absent keys: {db.disk_reads} disk reads "
f"(without blooms: {2_000 * len(db.tables):,})")
db.flush()
dropped = db.compact()
print("after compaction:", len(db.tables), "table,", len(db.tables[0].keys),
"live keys, purged", dropped, "tombstones")
b = db.tables[0].bloom
print(f"bloom for {len(db.tables[0].keys)} keys: {b.m:,} bits ({b.m/8/1024:.1f} KiB), k={b.k}")sstables before compaction: 11 | memtable: 100
get user:00010 -> {'v': 2} | disk reads: 1
get user:00100 -> None (deleted) | disk reads: 0
2000 lookups of absent keys: 209 disk reads (without blooms: 22,000)
after compaction: 1 table, 9900 live keys, purged 100 tombstones
bloom for 9900 keys: 94,892 bits (11.6 KiB), k=7
Reading the output
- Eleven SSTables after 11,100 writes with a 1,000-entry memtable: overwrites and deletes did not modify old files, they created new ones. That is the LSM bargain — write amplification is deferred to compaction.
- The overwritten key cost one disk read: the newest table containing it answered first, and the blooms of the newer tables that did not hold it were skipped for free.
- 2,000 absent-key lookups cost 209 disk reads instead of 22,000. 209 across 11 tables × 2,000 probes is a 0.95% false-positive rate — exactly the 1% the filter was sized for. Absent-key lookups are common in a KV store (existence checks, cache misses, conditional creates), so this matters enormously.
- Compaction collapsed everything to one table and purged tombstones. A real engine only drops a tombstone once it is older than
gc_graceand it is compacting every file that could still hold the deleted key — dropping it earlier risks resurrection.
Compaction strategies and their amplification
| Strategy | How it merges | Good for | Cost |
|---|---|---|---|
| Size-tiered | Merge a few similarly sized tables into one bigger one | Write-heavy workloads | Reads may check many tables; needs up to 2x free disk during a big merge |
| Leveled | Levels of non-overlapping tables, each level ~10x the last; a key lives in at most one table per level | Read-heavy, update-heavy | Roughly 10x more write amplification — the same bytes are rewritten at each level |
| Time-window | Group tables by write time; whole old windows expire at once | TTL'd time-series, logs, sessions | Poor if old data is ever updated |
The three amplifications to name: write amplification (bytes written to disk per byte written by the client), read amplification (files touched per lookup) and space amplification (disk used per byte of live data). You can minimise any two; the strategy picks which. Mention that compaction competes with foreground traffic for disk bandwidth and must be throttled — unthrottled compaction is a classic cause of p99 spikes.
sequential append)] W --> MT[Memtable
sorted, in RAM] MT -->|flush at 128 MB| S0[(SSTable newest)] S0 --> CMP{{Compaction}} S1[(Older SSTables)] --> CMP CMP --> S2[(Merged SSTable)] RD[Read] --> MT RD --> BF{Bloom filter
maybe here?} BF -->|no: skip, zero I/O| NX[Next table] BF -->|maybe| IDX[Index lookup + one block read]
Writes are sequential appends plus an in-memory insert. Reads check the memtable and then each SSTable newest-first, with bloom filters eliminating nearly every file that does not hold the key.
Step 13 — Walk one put end to end
The coordinator answers as soon as W replicas have made the write durable in their commit logs. The slow or substituted replicas finish in the background, and hinted handoff completes the third copy once B returns.
The order of operations, and why
- The client driver routes to an owner. A ring-aware driver hashes the key itself and sends to a replica, saving the extra hop through a random node. If it sends to a non-owner, that node coordinates anyway — any node can.
- The coordinator builds the version before fan-out. The new clock descends the context the client read, so replicas can tell this is an update, not a concurrent write.
- Send to all N at once, wait for W. Sending to all rather than just W is what lets the third replica catch up without repair. Waiting for only W is what cuts the tail: one slow disk does not slow the request.
- Each replica acks after the commit log append, not after flushing to an SSTable. The log is the durability point; that is why a replica write takes well under a millisecond locally.
- Late acks still count toward convergence. The coordinator does not cancel outstanding replication when it returns to the client.
- If W is not reached before the timeout, return 503 and let the client retry with the same context. Replicas that did apply the write keep it; the retry produces a version that descends it.
Step 14 — Walk one get end to end
The coordinator returns as soon as R replies are in and reconciled. Replica B was behind, so the coordinator repairs it after answering, and the next read of this key will find all three replicas agreeing.
The order of operations, and why
- Prefer a coordinator that is itself a replica. One of the R replies is then a local read with no network hop.
- Ask for one full value and digests from the rest. A digest (a hash of the value plus its clock) is a few bytes; only if digests disagree does the coordinator fetch full values. For 1 MB values this saves most of the read bandwidth.
- Reconcile with vector clocks, not timestamps. Versions that are descended from others are discarded; if truly concurrent versions remain, return them all as siblings (HTTP 300) with a merged context, so the client's next write resolves them.
- Answer first, repair after. Read repair is asynchronous so it never adds latency. Some systems only perform it on a sample of reads (say 10%) to cap the extra write load.
- Speculative retry for the tail. If one replica has not answered by the p95 latency, send the same read to the third replica too and take whichever answers first. This single trick often halves p99 read latency, at the cost of a few percent more read traffic.
Step 15 — Tunable consistency and where this sits in CAP
Consistency is a per-request parameter, which is the "tunable" in tunable consistency. Here are the levels a Cassandra-style store offers, with N = 3 per data centre:
| Level | Waits for | Guarantee | Use it for |
|---|---|---|---|
| ONE | 1 replica | Fastest, may be stale | Metrics, caches, activity logs |
| QUORUM | 2 of 3 (globally, across DCs) | Read-your-writes when both sides use it | Single-region default |
| LOCAL_QUORUM | 2 of 3 in the local DC | Fresh within the DC, no cross-region latency | Multi-region default |
| EACH_QUORUM | A quorum in every DC | Fresh everywhere, slow, fails if any DC is cut off | Rare: global config writes |
| ALL | Every replica | Freshest; one dead node fails the request | Almost never |
| SERIAL (Paxos) | Consensus round | Linearizable compare-and-set on one key | Put-if-absent, uniqueness claims |
CAP placement
During a network partition you must choose between answering (and risking inconsistency) or refusing (and staying consistent). This design is AP: sloppy quorums, hinted handoff and siblings are all mechanisms for staying available through a partition and reconciling afterwards. The more useful framing is PACELC: under a Partition choose A or C; Else, in normal operation, choose Latency or Consistency. Dynamo-style stores are PA/EL — they also give up consistency for latency when nothing is broken, by acking at W < N.
Contrast with the CP family — etcd, ZooKeeper, Spanner, and per-range Raft stores like TiKV or CockroachDB's storage layer: every key range has a leader, writes go through consensus, reads are linearizable, and a minority partition refuses writes. They are the right answer for metadata, locks and money; they are the wrong answer for an "always writeable" shopping cart. A strong answer names both, and notes that many real products (DynamoDB's optional strongly consistent reads, Cassandra's LWT) offer a CP path for the few operations that need it.
Step 16 — Scaling, hot keys and multiple regions
- Adding a node. The operator assigns tokens; the new node streams its ranges from current replicas (from many peers at once, thanks to virtual nodes), throttled so foreground latency does not suffer. It serves reads for a range only once it has finished streaming it. Going from 180 to 200 nodes moves about 10% of the data.
- Hot keys. Consistent hashing balances keys, not requests. One viral key at 200k reads/s saturates its three replicas. Fixes, in order: a client-side or proxy cache with a short TTL (1–5 s); reading from all N replicas at ONE rather than a quorum; and for write-hot keys (counters), splitting the key into
key#0..key#15and summing on read. - Large values and wide keys. A 1 MB cap exists because a single huge value blocks a replica's network queue and makes compaction lumpy. Anything larger belongs in object storage with the KV holding the pointer — Part B's design.
- Multiple regions. Place replicas per data centre (for example 3 in each of two regions) and use LOCAL_QUORUM so requests never wait on a cross-ocean round trip. Replication between regions is asynchronous, and conflicts across regions are resolved by the same vector clocks or LWW.
- Throttling and admission control. Each node bounds its request queue and rejects early (503 with retry-after) when overloaded; a store that queues unboundedly turns a spike into a cluster-wide timeout storm.
Step 17 — Failure modes
| What fails | What the client sees | Mechanism |
|---|---|---|
| One replica down for 5 minutes | Nothing | Quorum met by the other two; stand-in holds hints; replay on return |
| One replica down for 2 days | Nothing | Hints expire after 3 h; full Merkle repair when it returns, or replace the node |
| Disk dies, node replaced | Slightly higher latency on its ranges | New node streams its ranges from the surviving replicas, from many peers in parallel |
| A whole availability zone lost | Nothing, if replicas are AZ-aware | Rack/AZ-aware preference lists keep one replica per AZ; 2 of 3 remain |
| Network partition splits the cluster | Both sides keep accepting writes (sloppy quorum) | Divergent versions become siblings, merged on read after the partition heals |
| Long GC pause on one node | A p99 blip | Phi accrual detector raises suspicion; speculative retry reads from another replica |
| Clock jumps forward 30 s on one node | With LWW: later writes from other nodes lose | NTP monitoring, reject writes from badly skewed nodes, vector clocks where it matters |
| Delete lost on one replica, repaired back | Deleted key reappears (zombie) | Tombstones kept for gc_grace longer than the repair interval |
| Compaction falls behind | Rising read latency, disk filling | Alert on pending compactions; throttle writes; add nodes before disks pass 50–60% |
| Hot key | Timeouts on one key only | Caching, read at ONE from any replica, key splitting |
Step 18 — Observability
- Per-operation latency at p50/p99/p999, split by consistency level and by coordinator vs replica time — the difference is network and queueing.
- Repair health: hints pending per node and their age, read-repair rate (a rising rate means replicas are diverging), time since the last full anti-entropy pass per range (must stay under
gc_grace). - Storage engine: SSTables per read (read amplification), pending compactions, bloom filter false-positive rate, memtable flush rate, disk usage vs the 50–60% ceiling compaction needs.
- Ring and membership: nodes up, suspected and down from each node's view — disagreement between views is an early sign of a network problem.
- Business-level SLI: the fraction of requests that met their requested consistency level within the latency SLO. That is the number your users experience.
The Part A trade-off summary
- Leaderless replication, not a primary per shard. Any replica accepts writes, so a node failure never causes a failover pause. We pay with conflicts, and with vector clocks and repair to handle them.
- Consistent hashing with virtual nodes, not modulo or range partitioning. Adding a node moves about 1/N of the data from many peers at once. We pay with ring metadata and some remaining imbalance.
- N = 3, W = 2, R = 2 by default, tunable per request. Read-your-writes in the common case, one node can fail with no impact. Callers who need speed over freshness can ask for ONE.
- Sloppy quorum plus hinted handoff. Writes survive the loss of home replicas. We knowingly give up the strict quorum overlap during failures.
- Merkle-tree anti-entropy plus read repair. Replicas converge even for keys nobody reads, and repair cost scales with how much is different.
- Gossip and phi accrual, not a coordinator service. No single point of failure; failure knowledge spreads in about log N seconds.
- LSM storage. Sequential writes for a write-heavy replicated workload; bloom filters and compaction keep reads fast.
- AP, PA/EL in PACELC, with a Paxos path for the rare compare-and-set. The store says exactly which guarantee each operation gets.
Part B — Pastebin, built on the store
Pastebin (and gists, and every "share this log" service) lets a user paste text and get back a short URL anyone with the link can open. It is a cousin of the URL shortener — a short key mapping to something — except the "something" is a blob of kilobytes to megabytes, which changes where it is stored, how it is cached and what expiry costs.
Step 19 — Clarify the requirements
Functional, in scope
- Create a paste of plain text and receive a unique URL. Optional title and syntax-highlighting language.
- Expiry: the user picks 10 minutes, 1 hour, 1 day, 1 week, 1 month or never; the default is 1 month for anonymous users. Expired pastes become unreachable automatically.
- Custom alias (optional):
paste.example/deploy-notes. 4–32 characters from[a-z0-9-], case-insensitive, with a reserved-word list (api,login,raw...). - Visibility: public (listed, indexable), unlisted (anyone with the link) or private (owner only, signed-in users).
- View rendered or raw; delete by the owner (or by anyone holding the delete token returned at creation, for anonymous pastes).
- A public REST API with API keys for tools and CI systems that post logs.
Explicitly out of scope
Editing pastes (each edit is a new paste — immutability makes caching trivial), images and binary files, comments, forks and revision history, full-text search over all pastes. Analytics (view counts) is an extension, handled asynchronously.
Non-functional
- Size limit: 10 MB per paste. Large enough for a big log file; small enough to stop the service becoming free file hosting. Enforced at the edge, before the body is read into an app server.
- Durability: a paste that returned 201 is never lost before its expiry.
- Availability: 99.95% for reads; links are shared in chats and tickets, and a dead link is the product failing.
- Latency: reads p99 < 200 ms for a typical paste; creates p99 < 500 ms.
- Unguessable URLs. An unlisted paste is protected only by its key. Sequential or predictable keys let anyone enumerate other people's pastes — this is a security requirement, not a nicety.
- Read-heavy: about 10 reads per write.
Step 20 — Back-of-the-envelope estimation
# Pastebin: back-of-the-envelope
SECONDS_PER_DAY = 86_400
new_pastes_day = 2_000_000
read_ratio = 10 # reads per write; pastes are shared links
avg_paste_kb = 12 # logs and snippets; median is ~2 KB, the tail drags it up
meta_bytes = 300 # key, owner, sizes, timestamps, flags, content pointer
keep_years = 5
w = new_pastes_day / SECONDS_PER_DAY
r = w * read_ratio
print(f"writes: {w:.0f}/s avg, {w*5:.0f}/s peak reads: {r:.0f}/s avg, {r*5:,.0f}/s peak")
content_tb = new_pastes_day * 365 * keep_years * avg_paste_kb * 1e3 / 1e12
meta_gb = new_pastes_day * 365 * keep_years * meta_bytes / 1e9
print(f"content over {keep_years}y: {content_tb:.1f} TB (x3 replication inside S3 is not our bill line)")
print(f"metadata over {keep_years}y: {meta_gb:,.0f} GB rows: {new_pastes_day*365*keep_years/1e9:.2f} B")
# how long must the key be?
total_keys = new_pastes_day * 365 * keep_years
for length in (6, 7, 8):
space = 62 ** length
print(f"base62 len {length}: {space:.2e} keys, {total_keys/space:.4%} used after {keep_years}y")
egress = r * avg_paste_kb * 1e3 * 8 / 1e6
print(f"read egress: {egress:.0f} Mbit/s avg")
# cache: hot 20% of a day's distinct reads
daily_reads = new_pastes_day * read_ratio
cache_gb = 0.2 * daily_reads * avg_paste_kb * 1e3 / 1e9
print(f"cache for the hot 20% of a day's reads: {cache_gb:.0f} GB (upper bound, repeats dedupe)")writes: 23/s avg, 116/s peak reads: 231/s avg, 1,157/s peak content over 5y: 43.8 TB (x3 replication inside S3 is not our bill line) metadata over 5y: 1,095 GB rows: 3.65 B base62 len 6: 5.68e+10 keys, 6.4260% used after 5y base62 len 7: 3.52e+12 keys, 0.1036% used after 5y base62 len 8: 2.18e+14 keys, 0.0017% used after 5y read egress: 22 Mbit/s avg cache for the hot 20% of a day's reads: 48 GB (upper bound, repeats dedupe)
What the numbers decide
- Traffic is small. A thousand reads per second at peak is modest — this is not a throughput problem, it is a storage-layout and correctness problem. Say so; do not design a 200-node cluster for it.
- 44 TB of content vs ~1 TB of metadata is a 40:1 ratio. They belong in different stores: content in cheap, durable object storage, metadata in a fast KV store. Putting 10 MB blobs into the KV store would hit its 1 MB value limit and ruin its compaction.
- Seven base62 characters, not six. After five years six characters would be 6.4% full — random key creation would collide on one in sixteen attempts, and an attacker probing random six-character URLs would hit a real paste 64,000 times per million guesses. Seven characters costs one byte and cuts both by 62x.
- The cache is tiny. Under 50 GB covers the hot set — two or three cache nodes. And because pastes are immutable, cached copies never need invalidating, only expiring.
Step 21 — API design
POST /api/v1/pastes
Headers: Authorization: Bearer <api key or session> (optional: anonymous allowed)
Idempotency-Key: <uuid> (retries return the same paste)
{ content: "...", title?: "build log", language?: "python",
expires_in?: "1d" | "never" | ..., visibility?: "unlisted",
custom_alias?: "deploy-notes", burn_after_read?: false }
-> 201 { key: "q7Bx2Pk", url: "https://paste.example/q7Bx2Pk",
raw_url: "https://paste.example/raw/q7Bx2Pk",
expires_at: "2026-10-23T10:00:00Z",
delete_token: "dt_9f..." } # shown once, never again
400 INVALID_ALIAS | 409 ALIAS_TAKEN | 413 PASTE_TOO_LARGE (10 MB)
422 CONTENT_REJECTED (abuse scan) | 429 + Retry-After (rate limit)
GET /{key} -> 200 HTML page (rendered, highlighted)
GET /raw/{key} -> 200 text/plain; charset=utf-8
Cache-Control: public, max-age=300 (public pastes only)
Content-Security-Policy: sandbox (never execute content)
404 NOT_FOUND | 410 GONE (expired or burned) | 403 (private, not the owner)
GET /api/v1/pastes/{key} -> 200 { key, title, language, size_bytes, created_at,
expires_at, visibility, views? }
DELETE /api/v1/pastes/{key}
Headers: Authorization (owner) or X-Delete-Token: dt_9f...
-> 204 | 403 | 404
GET /api/v1/users/me/pastes?cursor=<opaque> -> 200 { pastes: [...], next_cursor }Decisions worth defending
- 410 Gone vs 404. Distinguishing "expired" from "never existed" helps users ("this link has expired") and costs nothing — the metadata row is kept briefly past expiry as a tombstone. Omit it for private pastes to avoid revealing existence.
- Raw content is served as
text/plainwith a sandbox CSP, ideally from a separate domain (pasteusercontent.example). Pastes are attacker-controlled; if the main origin ever served them as HTML, a paste becomes a stored XSS on your login cookies. - The delete token is returned once and stored only as a hash — like a password. Anonymous users can still delete what they created.
- Idempotency-Key on create, because CI systems retry on timeout and would otherwise create duplicate pastes.
Step 22 — Data model: metadata store vs object storage
-- METADATA (the Part A key-value store, or DynamoDB / Cassandra) ---------------
table pastes -- partition key: paste_key (hash -> spreads evenly)
paste_key text PK -- "q7Bx2Pk" or a lowercased custom alias
content_ref text -- "s3://pastes-2026-09/q7Bx2Pk/4c1e..." or INLINE
inline_body bytes NULL -- pastes under 4 KB (~60% of them) live right here
size_bytes int
sha256 text -- integrity check + abuse blocklist matching
owner_id bigint NULL -- NULL for anonymous
visibility tinyint -- 0 public, 1 unlisted, 2 private
language text, title text
created_at timestamp
expires_at timestamp NULL -- also set as the row TTL (+1 day grace for 410s)
delete_token_hash text
burn_after_read boolean
-- ~300 bytes per row; point lookups only; no joins, no scans
table pastes_by_owner -- the one secondary access path, kept by the app
owner_id bigint PK -- partition key
created_at timestamp CK DESC -- clustering key: newest first, cursor = last ts
paste_key text, title text, size_bytes int, expires_at timestamp
table users (a small relational DB is fine: tens of millions of rows, rarely written)
user_id bigint PK, email text UNIQUE, api_key_hash text, plan tinyint, created_at
-- CONTENT (object storage: S3 / GCS / Azure Blob) ----------------------------------
bucket pastes-2026-09 / q7Bx2Pk / <random 16 bytes hex>
-- body gzip'd (logs compress 5-10x); Content-Type text/plain
-- one bucket (or prefix) per creation month -> lifecycle rules delete whole months
-- random suffix: content URL cannot be derived from the public paste key
-- CACHE (Redis / Memcached) --------------------------------------------------------
meta:q7Bx2Pk -> metadata row, TTL min(1 h, expires_at - now)
body:q7Bx2Pk -> body if < 1 MB, TTL min(1 h, expires_at - now)Why split metadata from content
- Different shapes. Metadata is small, hot, point-looked-up and sometimes queried by owner. Content is large, immutable, and read whole. No single store is good at both.
- Different economics. Object storage costs a fraction of replicated SSD per GB, grows without capacity planning, and is built for eleven-nines durability. The KV store stays at ~1 TB — a small cluster that fits in memory.
- Independent scaling. Traffic growth scales the KV and cache; retention growth scales only the bucket.
- Inline small pastes. Most pastes are a few KB. Storing bodies under 4 KB directly in the metadata row saves an object-store round trip (typically 20–50 ms) on the majority of reads, and saves per-object request costs. This is an optimisation worth naming; it is how you meet the 200 ms p99 cheaply.
Wrong answers: "a relational table with a TEXT column for content" (works at 1,000 pastes, but 44 TB in an OLTP database means huge backups, slow replicas and expensive storage); and "content-addressed storage keyed by the hash of the text, so duplicates share one object" (tempting for deduplication, but deleting one paste must not delete another user's identical paste, and a public URL derived from the content hash lets anyone test whether a given text has been pasted — a privacy leak).
Step 23 — Key generation
The key must be short, unique and unguessable. Four approaches, and why most fail one of those three:
- Auto-increment or Snowflake id in base62 — unique and short, but sequential:
q7Bx2Pktells youq7Bx2Plexists. That breaks the unguessability requirement for unlisted pastes. (It is the right choice for the internal id in the unique ID lesson; it is the wrong choice for a public capability URL, unless you encrypt it with a keyed permutation first.) - Hash of the content (MD5/SHA, truncated) — identical pastes collide by design, truncation to 7 characters adds accidental collisions, and it leaks existence as described above.
- Random key plus a conditional insert — generate 7 random base62 characters from a cryptographic source and write with put-if-absent. Collisions are rare (0.1% when the space is 5 years full) and simply retried. Simple, stateless, no extra service.
- A key generation service (KGS) — a standalone service pre-generates random keys into a key database with an unused and a used table, and hands app servers batches of, say, 1,000 keys at a time, marking them used as they are handed out. App servers never collide and never retry. Costs: another service to run and replicate (a standby takes over if the primary dies, otherwise it is a single point of failure), and keys held by a server that crashes are lost — acceptable, since there are 3.5 trillion.
import secrets, string
ALPHABET = string.digits + string.ascii_letters # base62: URL-safe, no escaping
def random_key(length: int = 7) -> str:
# secrets, not random: keys must be unguessable, and random's Mersenne
# Twister output can be predicted after observing enough values
return "".join(secrets.choice(ALPHABET) for _ in range(length))
class PasteStore:
"""Stand-in for the KV store's conditional put (put-if-absent)."""
def __init__(self):
self.rows = {}
def put_if_absent(self, key, row) -> bool:
if key in self.rows:
return False
self.rows[key] = row
return True
def create(store, row, custom_alias=None, max_attempts=5):
if custom_alias is not None: # the user chose: never retry
return custom_alias if store.put_if_absent(custom_alias, row) else None
for _ in range(max_attempts):
key = random_key()
if store.put_if_absent(key, row): # atomic: no read-then-write race
return key
raise RuntimeError("key space too full - lengthen keys")
s = PasteStore()
k = create(s, {"size": 812})
print("random key length:", len(k), "| all base62:", all(c in ALPHABET for c in k))
print("custom 'deploy-notes':", create(s, {}, "deploy-notes"))
print("same alias again :", create(s, {}, "deploy-notes"), "-> 409 ALIAS_TAKEN")
# Expected attempts per create as the key space fills (random keys, retry on clash)
for length, used in ((6, 3.65e9), (7, 3.65e9)):
fill = used / 62 ** length
print(f"len {length} with {used/1e9:.2f} B keys used: fill {fill:.4%}, "
f"expected attempts {1 / (1 - fill):.4f}, "
f"guess hits per 1M random probes {fill * 1e6:,.0f}")random key length: 7 | all base62: True custom 'deploy-notes': deploy-notes same alias again : None -> 409 ALIAS_TAKEN len 6 with 3.65 B keys used: fill 6.4260%, expected attempts 1.0687, guess hits per 1M random probes 64,260 len 7 with 3.65 B keys used: fill 0.1036%, expected attempts 1.0010, guess hits per 1M random probes 1,036
Choose random keys with a conditional insert and state why: at 116 writes per second peak, a retry at 0.1% probability is one extra round trip every nine seconds. KGS solves a collision problem this system does not have, at the price of a stateful service. Mention KGS as the answer when writes reach tens of thousands per second, or when the conditional-insert path of the store is expensive (it is a Paxos round in Cassandra; in that case, a KGS lets you use plain writes). Custom aliases always use the conditional insert and never retry — the user chose that name, so a clash is a 409 they must see.
Step 24 — High-level design
public raw pastes, static assets] CDN --> LB[Load balancer + WAF
10 MB body limit, TLS] LB --> RL[Rate limiter] RL --> W[Write API service] RL --> R[Read service] W --> SCAN[Abuse scanner
secrets, malware, blocklist] W --> OS[(Object storage
content, gzip)] W --> KV[(Metadata KV store
pastes, pastes_by_owner)] R --> CACHE[(Redis
hot metadata + bodies)] R --> KV R --> OS W --> Q[[Event queue]] R --> Q Q --> AN[Analytics: view counts] Q --> SW[Expiry sweeper + CDN purge] SW --> OS
Reads and writes are separate services because they scale and fail differently. The KV store holds metadata and small bodies; object storage holds everything else. Analytics and cleanup hang off a queue so they can never slow a request.
What each component owns
- CDN — caches public raw pastes (immutable, so safe to cache until expiry) and absorbs a viral paste's traffic. Never caches private or unlisted pastes at shared edges — unlisted links leak into logs and referrers, and an edge cache would widen the exposure.
- Load balancer and WAF — TLS, the 10 MB body limit (rejecting oversized uploads before an app server buffers them), obvious bot blocking.
- Rate limiter — per IP and per API key, much tighter for anonymous creates (say 10/min), because spam and malware hosting are the dominant abuse. See the rate limiter lesson.
- Write API — validation, alias rules, abuse scan, key generation, the two writes (content then metadata).
- Read service — cache, then metadata, then content; visibility and expiry checks; burn-after-read.
- Expiry sweeper — deletes content objects the lifecycle rules do not cover and purges CDN entries.
Step 25 — Walk a create and a read end to end
Content is written before metadata so a paste is never visible without its body. The read path is cache, metadata, object store — and after the first read, cache only.
The order of operations, and why
- Content first, metadata second. If the service crashes between the two writes, the worst outcome is an orphaned object with no metadata pointing at it — invisible to users and cleaned up by the sweeper (or a lifecycle rule). The opposite order could publish a URL that returns an error.
- The metadata put-if-absent is the commit point. A key clash here means retry with a new key; the orphaned object from the first attempt is harmless.
- Reads at consistency ONE. Pastes are immutable, so there is nothing to be stale about except the brief window right after creation. If a read misses at ONE within a few seconds of creation, retry at QUORUM before returning 404 — that covers "I just created it and it 404'd" without paying quorum cost on every read.
- Check expiry on read, not just by deletion. The sweeper and TTLs run on their own schedule; the read path must refuse an expired paste the instant
expires_atpasses. - Cache TTL never outlives the paste.
min(1 h, expires_at − now)means a 10-minute paste cannot be served from cache after it expires.
Step 26 — Expiry, cleanup and burn-after-read
- Metadata: the KV row's native TTL (expiry plus a day, so 410 can be returned briefly). Expired cells disappear at compaction, with zero sweeper work.
- Content: one bucket or prefix per creation month plus object-store lifecycle rules. For fixed-expiry classes, rules delete objects by age at no request cost. For "never" and mixed expiries, a sweeper consumes expiry events from the queue (or scans an expiry index by day) and deletes objects in batches.
- CDN: public raw pastes are served with
max-ageno longer than the remaining lifetime, so edges expire them on their own; explicit purges are only needed for owner deletes and abuse takedowns. - Burn after read: the read service performs a conditional delete (compare-and-set on the row) before returning the body, so two simultaneous readers cannot both see it. The body is never cached or sent to the CDN.
- Deletion is also cost control. Without the sweeper, "never looked at again" pastes cost storage forever; with a month default for anonymous pastes, steady-state storage is bounded.
Step 27 — Scaling, security and failure modes
Scaling
- Viral paste: a link on a front page means 50k reads/s on one key. The CDN takes it for public pastes; for unlisted ones, the Redis cache plus a small in-process cache (a few seconds) in each read server keeps it off the KV store.
- Metadata partitioning: hash of
paste_key— keys are random, so the load spreads perfectly.pastes_by_owneris partitioned by owner; a heavy CI account with millions of pastes gets a time bucket in its partition key (owner_id, month) so no partition grows unbounded. - Writes are small: 116/s peak. A handful of stateless write servers; the object store absorbs throughput.
Security and abuse
- Serve user content from a separate cookieless domain, as
text/plain, withnosniffand a sandbox CSP. - Scan for leaked credentials (API keys, private keys) on create and warn or block; pastes are a common way secrets leak.
- Rate-limit anonymous creates hard; block known-malware hashes; a takedown path that deletes content, metadata and CDN copies together.
- Private pastes: authorisation on every read, never cached at the CDN, and 404 (not 403) for non-owners so existence is not revealed.
| What fails | What users see | Mechanism |
|---|---|---|
| Object storage slow or down | Small pastes still work; large ones error | Inline bodies under 4 KB; cached bodies; retries with backoff and a circuit breaker |
| Redis down | Slightly slower reads | Fall through to KV and object store — the traffic is small enough to absorb |
| KV replica down | Nothing | Reads at ONE, writes at QUORUM, hinted handoff (Part A) |
| Crash between content and metadata write | Nothing (client retries, gets a new or same paste) | Orphan object swept; Idempotency-Key returns the original result |
| Read right after create returns 404 | Nothing | Retry at QUORUM before answering 404 |
| Spam wave from a botnet | Legit users unaffected | Per-IP and per-ASN rate limits, CAPTCHA on anonymous create, scanner |
The Part B trade-off summary
- Metadata in a KV store, content in object storage. Each store does what it is good at; the KV stays small and fast. We pay with two writes per create and an orphan sweeper.
- Small bodies inline in the metadata row. Most reads are one lookup. We pay with a size-based branch in the code.
- Random 7-character keys with put-if-absent, not a KGS. Unguessable, stateless, rare retries. Revisit at much higher write rates.
- Immutable pastes. Caches never need invalidation, only expiry, and conflicts cannot happen — which is why reads at ONE are safe.
- Expiry by TTL, lifecycle rules and a sweeper, checked again on read. Correct at the instant of expiry, and cheap in bulk.
- Separate content domain and strict content types. User text is never executable on our origin.
// Write your solution here
// Write your solution here
// Write your solution here
// Write your solution here
Finished reading? Mark this lesson complete to track your progress.
