Storage and consistency

Name the consistency before you name the storage

Before any component, say one sentence of the form "a reader may see data up to N seconds old, and a duplicate costs X". That sentence picks the design. A like counter can be minutes stale and nobody notices. A cache can be seconds stale if a write invalidates it. An ID that is issued twice corrupts two records. A charge that runs twice is a refund, a support ticket and a lost customer.

Then say what happens when the network splits, because it will, and the interviewer is waiting for it. During a partition a node cut off from the rest has two choices: refuse the request (stay consistent, lose availability) or answer it from what it has (stay available, risk a stale read or a conflicting write that must be merged later). There is no third choice. Pick per operation, not per system.

Linearisable

Every read sees the latest acknowledged write, as if there were one copy. Needed for anything that must not happen twice: a payment, a lock, a balance. Costs a round trip to a majority on every write, and the minority side of a split stops accepting writes.

Read-your-writes

You see your own writes; other people may lag. Enough for a profile edit or a posted comment. Usually done by routing a user's reads to the leader for a few seconds after they write.

Eventual

Replicas agree if writes stop. Enough for caches, counters, feeds and rate limits. Both sides of a split keep working, and you must say how conflicting writes are merged (last-writer-wins, a counter that adds, or keep both and let the app decide).

Questions

Answer each one yourself before you open it.

1. 01Design a distributed key-value store: a billion keys, values around 1 KB, 200,000 operations a second at peak.

   The hinge is partitioning plus replication: spread keys over nodes with consistent hashing so adding a node moves only a slice of them, and keep 3 copies of each key. Then the real decision is per request: a quorum where reads plus writes overlap (R + W > N, say 2 and 2 of 3) gives you the latest value, while R = W = 1 is faster and can return stale data.

   These are interview assumptions; replace the operations rate first, since it sizes the cluster. Data: 1,000,000,000 keys × 1 KB = 1 TB, and × 3 replicas = 3 TB. Throughput: if one node serves about 20,000 ops/s, then 200,000 / 20,000 = 10 nodes, each holding 3 TB / 10 = 300 GB, which fits on one SSD. So throughput, not disk, sets the node count. Components: a client or coordinator that hashes the key onto the ring, storage nodes with an append-only log plus an LSM tree underneath, and a gossip or config service that tells everyone who owns which range.

   Follow-up The link between your two data centres drops. A client writes the same key on both sides. What happens?

   You chose that when you chose the quorum. With strict majorities, the side without a majority of replicas refuses the write and the key stays consistent. If you let both sides accept writes to stay available, you now hold two versions and must merge them when the link returns: last-writer-wins by timestamp silently drops one, while version vectors keep both and hand the conflict to the application.

   Learn more Splitting the ledger (sharding) · The ring (consistent hashing lab) · Replication

2. 02Design a distributed cache in front of a database that serves a million reads a second.

   The hinge is the hit rate, because the database only sees the misses: cache-aside with a TTL, keys spread over cache nodes by consistent hashing, and an explicit decision that readers may see a value up to one TTL old. Writes go to the database and then delete the cache key, rather than updating it, so two racing writes cannot leave the older value behind.

   Interview assumptions; replace the hit rate first, because it moves the database load by 10x. At 99% hits the database sees 1,000,000 × 0.01 = 10,000 reads/s. At 90% it sees 1,000,000 × 0.1 = 100,000 reads/s, ten times more, from a one-line change in hit rate. Memory: 20 million hot objects × 2 KB = 40 GB, which fits in a handful of nodes; at about 100,000 ops/s per node, 1,000,000 / 100,000 = 10 nodes, so again throughput sets the count. Why consistent hashing: growing from 10 to 11 nodes with hash % N remaps 1 - 1/11 ≈ 90% of keys (a near-empty cache and a stampede on the database), with a ring only about 1/11 ≈ 9%.

   Follow-up One key is so popular that its node melts, and when it expires a thousand requests hit the database at once. Fix it.

   For the stampede, let one request refill the key while the others wait on it (request coalescing, or a short lock on the key), and add jitter to TTLs so keys do not expire together. For the hot key, copy it to several nodes under suffixed keys (key#1 to key#8) and have readers pick one at random, or keep it in a small in-process cache on each app server for a second or two.

   Learn more The slate next to the stove (caching) · The Slate, Properly (caching to real depth) · The slate (cache lab)

3. 03Design a rate limiter for a public API: 100 requests a minute per user, 10 million users, 500,000 requests a second through the gateway.

   The hinge is that the limit does not need to be exact, so the counter can be cheap: a token bucket per user, stored in a shared in-memory store sharded by user id, checked and decremented in one atomic operation. If the store is unreachable, fail open and let the request through, because a limiter outage should not become an API outage.

   Interview assumptions; replace the request rate first, because it sets the shard count. State: a bucket is a token count and a last-refill timestamp, about 100 bytes with key overhead, so 10,000,000 × 100 B = 1 GB, which fits in one machine's memory. Throughput is the constraint: at about 100,000 atomic ops/s per store node, 500,000 / 100,000 = 5 shards, keyed by user id so one user always lands on one shard. Components: the check lives in the gateway, one network hop to the store (well under a millisecond in the same zone), and a 429 with a Retry-After header when the bucket is empty.

   Follow-up Now you run in two regions. How do you enforce one global limit per user?

   Do not check across regions on every request: that adds a cross-region round trip, tens of milliseconds, to every call. Either split the budget (each region gets 50 per minute) or count locally and sync totals every second or so, accepting that a user hitting both regions at once can overshoot briefly. Say the overshoot out loud; it is the price of not paying the round trip.

   Learn more The bouncer at the door (rate limiting) · The bouncer at the door (lab)

4. 04Design a service that hands out unique IDs: 64 bits, roughly sortable by time, 100,000 IDs a second across many machines.

   The hinge is avoiding coordination per ID: each ID is built from the current time, a machine number and a per-machine counter, so no two machines can ever produce the same one and no request waits on another machine. The only coordination is once at startup, to hand each machine its number.

   Interview assumptions; replace the per-machine peak first. This is the layout Twitter published as Snowflake in 2010: 41 bits of milliseconds, 10 bits of machine, 12 bits of sequence. 2^41 ms ≈ 70 years before the clock field runs out; 2^10 = 1,024 machines; 2^12 = 4,096 IDs per machine per millisecond, about 4 million per second each, so 100,000/s needs one machine and the rest are for availability. Why not just random 64-bit numbers: a year at 100,000/s is 100,000 × 86,400 × 365 ≈ 3 × 10^12 IDs, and the birthday bound gives about n² / 2^65 ≈ 300,000 expected collisions. A random 128-bit UUID fixes that (about 10^-14 expected) but doubles the index and is not time-sortable.

   Follow-up NTP moves a machine's clock back two seconds. What does your generator do?

   It must not issue IDs with a timestamp it has already used, or it can repeat one. Keep the last timestamp in memory; if the clock reads earlier, refuse (or wait) until it catches up, and alarm if the jump is large. On restart, do not trust memory: persist a high-water mark or wait out the maximum plausible skew before issuing again.

   Learn more The birthday collision (lab) · Who holds the pen (consensus & Raft)

5. 05Design a payment system that must never charge a customer twice, even when requests are retried.

   The hinge is an idempotency key: the client generates one per checkout, the server writes it with a unique constraint in the same transaction that records the payment as pending, and every retry with that key returns the first result instead of charging again. The same key is passed to the card processor, so the promise holds across the one call you cannot roll back.

   Interview assumptions; replace the timeout rate first, because it is the number of ambiguous payments you must resolve. At 1,000,000 payments a day, 1,000,000 / 86,400 ≈ 10 per second on average, perhaps 100 at a 10x peak, so scale is not the problem, correctness is. If 1% of calls time out and get retried, that is 1,000,000 × 0.01 = 10,000 payments a day where the client does not know whether it paid. Keeping keys for a day costs 1,000,000 × 200 B = 200 MB. Components: a payments service with a relational store (you want its transactions and unique constraints), an outbox so the "payment succeeded" event is published exactly when the row commits, and a nightly reconciliation against the processor's settlement file.

   Follow-up The call to the card processor times out. Did the customer pay?

   You do not know, and the one wrong move is retrying with a fresh key. Leave the payment pending, ask the processor for the status of that same idempotency key (or retry with it, which the processor deduplicates), and only then mark it succeeded or failed. Anything still unresolved is caught by reconciliation. Exactly-once is not a delivery guarantee you get; it is at-least-once delivery plus a handler that ignores the duplicates.

   Learn more Charged Twice (idempotency & exactly-once) · The Two Ledgers Must Agree (Distributed Transactions) · Charged twice (lab)