Design a key-value store

Do the numbers before the boxes

An interviewer gives a rate and a data size. Two numbers follow before any box is drawn: the mix of reads and writes, and the growth.

A 45-minute version of this answer is at the end.

We assume one AWS Region, us-east-1. Every count on this page is our estimate unless sourced.

The peak is 60,000 client operations a second. A client operation is one read or one write of one value.

40% are writes: 0.4 x 60,000 = 24,000 writes, and 60,000 - 24,000 = 36,000 reads a second.

A value is 1 KiB. The data is 18 TiB of values, 18 x 1,024 = 18,432 GiB, before any copies.

That is 18,432 GiB / 1 KiB = 18,432 x 1,048,576 values, about 19.3 billion.

Writes update existing keys, so the data stays near 18 TiB.

If every write were a new key, 24,000 x 1 KiB x 86,400 s would add 2,073,600,000 KiB, about 1.93 TiB a day.

A ring sized for 18 TiB would then fill within days, so an interviewer checks this first.

The callers are our own services in the VPC, so no answer crosses the internet.

Check in: Close the page and derive the reads, the writes, and the growth if every write were a new key.

One copy, by hash mod 15

Stage 1 is the first answer: 15 nodes, one copy of every value, and each key placed by hash mod 15.

The nodes run in 3 availability zones: separate data centres in one Region. That is 5 nodes a zone.

Each node is an EC2 i8g.4xlarge, one of AWS's virtual servers. It has 16 vCPUs, virtual processors, on Graviton, AWS's ARM processor.

It holds one 3,750 GB NVMe drive, fast flash storage in the host. That drive is instance store: its data is lost when the instance stops.

Drives are sold in decimal GB, and this page counts binary GiB: 3,750 x 10^9 / 2^30 = 3,492.46 GiB.

Hash mod n puts a key on node number hash(key) mod 15. Any client can compute it, with no directory to ask.

Bytes: 18,432 GiB / 15 = 1,228.8 GiB a node. That is 1,228.8 / 3,492.46 = 35.2% of the drive.

The card also counts replica operations: one copy of one value read or written on one node. With one copy, a client operation is one.

The card rates a node at 46,000 replica operations a second, from a vendor's test of Cassandra (Aerospike, a competitor).

That is the low end of our conversion; a beat after Stage 2 derives it. So a node takes 60,000 / 15 = 4,000 a second, 8.7%.

Four tiles go with each canvas: the load in client operations a second (req/sec), the latency, the cost a month, and what saturates first.

The card's percentage is the larger of the two shares: 35.2%. Nothing saturates, and the last tile notes "Busiest: Key-value ring at 35%".

The latency tile shows 0ms; Stage 2 says why. The cost tile shows $15k/mo: 15 x 720 hours x $1.3728 = $14,826.24.

Hash mod n works until the node count changes. A key keeps its node only if its hash gives the same remainder for 15 and 16.

One key in 16 does, so a 16th node moves 15/16 of the keys: 93.8%.

Each moved key must be copied to its new node while clients still read it.

And one copy means one lost drive loses its keys for good.

On the canvas there are no load buttons. The lesson here is bytes, and the bytes stay at 35.2% at any load.

The trade-off:

Hash mod n needs no directory. In exchange, a change in node count moves nearly every key, and one copy survives nothing.

Stage 1: One copy, by hash mod 15

• Load: 60,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $15k/mo

Check in: Why is hash mod 15 with one copy not interview ready?

Why a ring, and when a range directory wins

Hash mod n moves nearly every key when a node joins. An interviewer expects consistent hashing, and a reason to choose it.

A consistent-hash ring puts keys and nodes on one circle of hash values. A key belongs to the next node point after it, going round.

Each node takes 16 points on the circle, called virtual nodes, which is Cassandra's default since 4.0.

Add a 16th node to 15, and it takes a slice from many nodes. At one copy, 1/16 of the keys move, 6.3%.

At 3 copies, about 3/16 of the keys get a changed replica set, and the new node takes 1/16 of the bytes.

Virtual nodes also spread a node's work. When a node is replaced, many peers stream its data at once; Stage 4 shows it.

A range directory keeps keys sorted and split into ranges. A metadata service maps each range to a node.

Bigtable, HBase and FoundationDB work this way. They can scan a range of keys, which a hash ring cannot.

They also split a busy range by themselves: HBase by size by default, Bigtable by load too. The cost is a metadata service to run.

Neither design splits a single key. One hot key stays on its copies in both, and Stage 5 shows what that costs.

Choose the ring for point reads at scale, with no directory to run. Choose a directory when queries scan ranges.

Say it like this: "A consistent-hash ring with 16 virtual nodes a node. At one copy, a join moves 1/16 of the keys, not 15/16."

Step through the figure to compare the two.

The trade-off:

The ring gives up range scans and automatic splits. In exchange, no directory sits on the request path, and a join moves one share.

From hash mod n to a ring

1. Hash mod 15: a key goes to node hash(key) mod 15. Any client can compute it.
2. Add a 16th node: a key stays only if both remainders match. 15/16 of the keys move, 93.8%.
3. A ring: each node takes 16 points on one circle of hashes. A key goes to the next point.
4. Add a 16th node: it takes a slice from many nodes. At one copy, 1/16 of the keys move, 6.3%.

Check in: A 16th node joins 15. How many keys move under hash mod n, and how many on the ring?

Three copies on the same 15 nodes

The interviewer asks: A node will die. Keep three copies, and survive a zone.

Stage 2 keeps the 15 nodes on a ring and stores 3 copies of every value, one in each zone.

Each copy is a replica. Cassandra's NetworkTopologyStrategy walks the ring and skips a node in a zone it has already used.

So each zone holds one full copy, and node counts are a multiple of 3.

A write goes to all 3 copies and waits for 2 acks: N 3, W 2. A read asks 2 copies: R 2.

The bytes triple: 18,432 x 3 = 55,296 GiB. On 15 nodes that is 3,686.4 GiB a node.

A node's drive holds 3,492.46 GiB, and 3,686.4 / 3,492.46 = 1.0555, about 106%. The bytes do not fit.

The result names Key-value ring. Its warning says 106%: the bytes do not fit on the instance store.

A card turns red at 90%, and the ring card warns over 80% full. Past 100% a part is named, the card stops at 100%, and its warning gives the full figure.

Bytes do not queue. A node full on bytes is saturated at any load, and its latency does not rise.

This card counts no software time on NVMe, so the latency tile reads 0 ms. A read also waits for the slower of its two copies, in another zone: usually about a millisecond, and AWS says under 10. The card does not model that wait.

The operations grow too: a read costs 2 replica operations, and a write 3. In all, 36,000 x 2 + 24,000 x 3 = 144,000 a second.

That is 2.4 times the client load. Each node takes 144,000 / 15 = 9,600 a second: 20.9% of 46,000.

The CPU has room; the drives do not. Replication is capacity, and bytes run out first.

The cost tile shows $15k/mo, the same $14,826.24 as Stage 1: the same nodes, and the bytes do not fit on them.

On the canvas, the card applies the copies itself, so the edge carries client operations only.

There are no load buttons: the wall is bytes, and no load changes it.

Stage 3 fixes it with more nodes. Your turn, after the quiz, fixes it another way.

The trade-off:

Three copies survive a zone. In exchange, the ring needs three times the drive space and 2.4 times the operations.

Stage 2: Three copies on the same 15 nodes

• Load: 60,000 req/sec
• First to saturate: Key-value ring
• Estimated cost: $15k/mo

• Key-value ring: Stored 3,686 GiB a node (18,432 GiB x 3 copies over 15 nodes) against 3,492 GiB raw on i8g.4xlarge (1 x 3,750 GB): 106%. The bytes do not fit on the instance store.

Check in: At what load does Stage 2 stop being saturated?

Why a leaderless quorum, and when a leader wins

Stage 2's ring has no leader: any copy takes a write. An interviewer asks what that buys, and what it costs.

With N 3, W 2 and R 2, W + R = 4 is more than 3. So a read's 2 copies always include one that took the last acknowledged write.

This is a strict quorum. When a copy is down, the node handling the write stores a hint to replay later. A hint never counts as an ack.

Dynamo's sloppy quorum lets stand-in nodes count, which voids the overlap. This store does not use it.

Two things still break "read your last write". Each cell keeps the write with the latest timestamp, last write wins, so clock skew lets an older write win.

And Stage 6's client cache serves values up to 1 s old.

Under a network partition, a leaderless ring at QUORUM needs the same majority as a Raft group, a leader with followers.

Its gains are no pause while a new leader is chosen, and the freedom to ask a faster copy.

A compare-and-set is a write that applies only if the value is unchanged.

The ring has no cheap compare-and-set: each one is a Paxos round of about 4 round trips. A leader gives a cheap one.

A leader with a leader lease or ReadIndex also gives reads that always see the latest write. A deposed leader without one can serve a stale read.

Choose a leader when a key is often decremented, and must be decremented safely. The stock beat shows why.

DynamoDB is not built like this ring. It runs Multi-Paxos with a leader for each partition (USENIX ATC 2022).

Only that leader serves writes and strongly consistent reads.

Say it like this: "Leaderless, N 3, W 2, R 2, a strict quorum. No failover pause, but no cheap compare-and-set."

The trade-off:

No leader means no failover pause. In exchange, a compare-and-set costs a Paxos round, and last write wins on clocks.

Check in: Does W + R > N make this store strongly consistent?

Where 46,000 a node comes from

Skip on a first read; come back before the interview. Every operations percentage here divides by 46,000, and an interviewer will ask for its source.

Aerospike, which sells a competing database, tested Cassandra 5.0.3 on 6 i4g.4xlarge nodes, with 3 copies of each value.

Cassandra averaged 138,028 client operations a second, over a run that filled the cluster. That is 138,028 / 6, about 23,000 a node.

Half were writes, and a write reaches all 3 copies. A read touches 1 copy at the consistency level ONE, or 2 at QUORUM.

So a client operation was 0.5 x 1 + 0.5 x 3 = 2.0 replica operations at ONE. At QUORUM it was 0.5 x 2 + 0.5 x 3 = 2.5.

A node then did 23,000 x 2.0 = 46,000 to 23,000 x 2.5 = 57,500 replica operations a second.

AWS rates i8g's compute up to 60% better than i4g's. So an i8g.4xlarge may reach 57,500 x 1.6 = 92,000.

That 92,000 is the highest figure we derive from the source. The card takes 46,000, the low end of our conversion.

So a clean result holds across the band. A saturated result must be more than twice 46,000 to hold at 92,000 too.

The source's figure is an average while the cluster filled. Near the end of the run it may be about 12% lower.

No clean result on this page sits near enough to its line for that to matter.

A second source agrees. Instaclustr measured 32,894 client operations a second on a 3-node i4g.2xlarge cluster, at QUORUM.

That is about 10,965 a node, and 1,371 for each of its 8 vCPUs. Aerospike's is 23,000 / 16 = 1,438 a vCPU, within 5%.

Say it like this: "Aerospike's test of Cassandra, about 23,000 client operations a node, is 46,000 replica operations at the low end."

And: "It is a competitor's figure, so I size clean results on its low end."

The trade-off:

One figure from a competitor, converted by us. In exchange, every clean result holds across the whole band, from 46,000 to 92,000.

Check in: Why can a clean result rest on 46,000, while a saturated one needs more than twice it?

One write and one read, from client to disk

Walk one write and one read through their states. An interviewer probes each one.

Routed. Each client runs a token-aware driver: it hashes the key and sends the request to a node that holds a copy.

That node is the coordinator. A token-aware driver with a rack-aware policy, each zone set as a rack, picks a replica in its own zone.

Without that policy, two coordinators in three sit in another zone. No load balancer sits between: it would add a hop and pick a node by chance.

Written. The coordinator sends the write to all 3 copies and answers after 2 acks.

On each copy, the write is appended to the commit log and put in a memtable, a sorted table in memory.

Later the memtable is flushed to an SSTable, a sorted file that never changes. Compaction later merges SSTables into new ones.

Read. The coordinator reads its own copy in full, and asks one more copy for a digest, a hash of its value.

On a mismatch, it fetches the newer value and writes it to the stale copy. That is read repair.

Unavailable. With fewer than 2 copies up, the coordinator refuses at once with an UnavailableException. Nothing was written: a clean failure.

Timed out. Too few acks came back in time, but the copies that took the write keep it. The result is unknown, not failed.

Read repair can then spread it. So retry with the same value and a timestamp set by the client: the retry is idempotent.

A repeat then changes nothing: the same cell gets the same value at the same timestamp.

Lost. The commit log syncs to disk every 10 s by default. If 2 copies lose power in that window, an acknowledged write is gone.

Step through the figure to follow both.

The trade-off:

An answer after 2 acks of 3 keeps writes fast. In exchange, a timeout leaves the result unknown, so retries must be idempotent.

One write and one read, from client to disk

1. Routed: a token-aware, rack-aware driver sends the request to a copy in its own zone, the coordinator.
2. Written: the coordinator sends the write to all 3 copies and answers after 2 acks.
3. On each copy: the commit log, then the memtable. Later a flush to an SSTable, and compaction.
4. Read: its own copy in full, and a digest from one more. A mismatch starts read repair.
5. Unavailable: fewer than 2 copies up. Nothing was written.
6. Timed out: too few acks in time. The copies that took it keep it, so the result is unknown.

Check in: A write returned a timeout. Is the value stored?

Size the ring for three copies

Stage 2 cannot hold its copies. Stage 3 sizes the ring by its bytes, and counts by zone.

Each zone holds one full copy: 18,432 GiB. So size one zone, then multiply by 3.

Fill each drive to 70% at most. The other 30% is for compaction's working space, growth, and streaming a replacement node.

Compaction needs free space. Leveled compaction (LCS), which this page assumes, needs about 10% free. Size-tiered compaction (STCS) needs up to 50%.

A drive at 70% holds 0.7 x 3,492.46 = 2,444.72 GiB. A zone then needs 18,432 / 2,444.72 = 7.54 nodes, so 8.

That is 8 a zone, 24 nodes, and 18,432 x 3 / 24 = 2,304 GiB a node: 66.0% of the drive.

Nothing saturates; the note reads "Busiest: Key-value ring at 66%".

Why not 23 nodes? They split 8, 8 and 7, and the 7 hold 18,432 / 7 = 2,633 GiB each: 75.4%, past the 70% line.

Operations: 144,000 / 24 = 6,000 a node, 13.0%. The operations alone fit on 144,000 / (0.7 x 46,000) = 4.47, so 6 nodes, 2 a zone.

That holds even at the low end of our conversion; a higher figure leaves them more room.

A ring is sized by bytes before operations.

With STCS at 50% free, a zone needs 18,432 / (0.5 x 3,492.46) = 10.56, so 11 a zone, 33 nodes.

The latency tile shows 0ms. The cost tile shows $24k/mo: 24 x 720 hours x $1.3728 = $23,721.98.

Say it like this: "Each zone holds a full copy, 18 TiB. At 70% fill that is 8 nodes a zone, 24 in all."

The buttons count client operations a second. Press 120,000 and 240,000, two and four times the peak.

Operations rise to 120,000 x 2.4 / 24 = 12,000 a node, 26.1%, then 24,000, 52.2%. The card stays at 66.0% on bytes.

So the note still reads "Busiest: Key-value ring at 66%": bytes bind, not operations.

At the low end, operations saturate only past 24 x 46,000 / 2.4 = 460,000 client operations a second.

Step through the figure to see why the count is a multiple of 3.

The trade-off:

A ring sized for its bytes runs its operations at 13%. In exchange, the drives keep room for compaction, growth and a replacement.

One full copy in each zone

1. Three zones, and each holds one full copy: 18,432 GiB.
2. 8 nodes a zone, 24 in all: 2,304 GiB a node, 66.0% of the drive.
3. 23 nodes split 8, 8 and 7. The 7-node zone holds 2,633 GiB a node, 75.4%.

Stage 3: Size the ring for three copies

• Load: 60,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $24k/mo

Check in: On average, 23 nodes hold 18,432 x 3 / 23 = 2,404 GiB each. Why is 23 still worse than it looks?

How many times a byte reaches the drive

A 1 KiB write reaches the drive many times. An interviewer asks how many, and what happens when the drive cannot keep up.

Once in the commit log, once at the flush to an SSTable, and again at every compaction.

LCS keeps SSTables in levels. Moving one SSTable into a level rewrites about 11 times its size (ScyllaDB).

A full node has 4 or 5 levels, so each byte is rewritten 10 to 50 times, about 40 likely.

ScyllaDB measured 13 times on a small set, and warns of 50.

On Stage 3, a node takes 24,000 x 3 / 24 = 3,000 replica writes a second. That is 3,000 KiB/s, 2.93 MiB/s of new data.

At 40 times, compaction writes 2.93 x 40 = 117 MiB/s. Cassandra throttles compaction to 64 MiB/s a node by default.

The default binds past 64 / 2.93 = 21.8, about 22 times. So at 40 times it binds.

Then compaction falls behind while the CPU looks idle. Reads touch more SSTables and slow down.

So the design raises compaction_throughput, the throttle setting. The drive has room: the card puts its writes at about 9% of their rated rate.

The drive is rated at 600,000 reads and 330,000 writes a second, of 4 KiB each.

The card takes a write amplification of 10, and counts each rewrite as one 4 KiB disk write. At 1 KiB values, that is about the bytes of 40.

On Stage 3: reads 3,000 / 600,000 = 0.5%, writes 3,000 x 10 / 330,000 = 9.1%. About 9.6% in all.

Say it like this: "LCS rewrites each byte 10 to 50 times, about 40. That passes the 64 MiB/s default throttle, so I raise it and watch pending compactions."

The trade-off:

LCS keeps reads to few SSTables and needs little free space. In exchange, it rewrites each byte many times, and the default throttle binds.

Check in: Stage 3's operations are at 13%. How can its reads still slow down?

A node is down, and a replacement streams

The interviewer asks: A node dies at the peak.

Stage 4 is Stage 3 with one node of 24 down, and its instance store gone with it.

The ring does not copy a dead node's ranges again by itself. An operator chooses: replace the node, or remove it.

Stage 4 draws a replacement. 23 nodes serve while the new node streams 2,304 GiB back from the other two zones.

Cassandra streams at 24 MiB/s a sender by default. With virtual nodes, up to 16 peers in those zones send at once.

From 16 peers: 2,304 x 1,024 MiB / (16 x 24 MiB/s) = 6,144 s, about 1.7 hours.

Meanwhile 23 nodes hold 23/24 of the copies, 17,664 GiB of values x 3. Each survivor still holds 2,304 GiB, 66.0%.

Reads move. The rack-aware driver coordinates in its own zone, and for the dead node's ranges that copy is gone.

So both reads go to the copies in the other two zones. The same 16 nodes that stream each take about 1/16 more.

The card spreads the load over all 23: 144,000 / 23 = 6,261 a node, 13.6%. QUORUM still works: 2 of 3 copies remain.

Writes meant for the dead node leave hints, for at most 3 hours. A longer outage needs a full repair.

Remove the node instead, and its copy stays in its zone. Only its 7 zone-mates take its data: 2,304 x 8 / 7 = 2,633 GiB, 75.4%.

Aerospike's test, the source of 46,000, also ran with a node down.

The same source saw Cassandra unstable at 100K ops/s with a node down. Plan headroom for a node loss, and for the streaming and hints that come with it.

The latency tile shows 0ms. The cost tile shows $23k/mo: 23 x 720 hours x $1.3728 = $22,733.57.

The replacement node is not drawn, so it is not on this bill. On AWS it bills from its launch.

On the canvas, the extra 1/16 on the other two zones does not show. There are no load buttons: the bytes stay at 66.0% at any load.

Step through the figure to compare a replacement with a removal.

The trade-off:

A replacement keeps every node at 66.0%. In exchange, two zones carry extra reads and the streaming for about 1.7 hours, and hints pile up.

A node is lost: replace it or remove it

1. One node of 24 is down. The ring does not copy its ranges again by itself.
2. Replace: the new node streams 2,304 GiB back from up to 16 peers in the other two zones, about 1.7 hours.
3. Meanwhile the same 16 nodes take its reads, about 1/16 more each. Every node stays at 66.0% on bytes.
4. Remove: its copy stays in its zone. Its 7 zone-mates take its data: 2,633 GiB each, 75.4%.

Stage 4: A node is down, and a replacement streams

• Load: 60,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $23k/mo

Check in: A dead node at 8 a zone is removed. Why do some nodes reach 75.4%, and not 68.8%?

A flash sale on one product record

The interviewer asks: A flash sale: one product's page gets 300,000 reads a second.

Stage 5 is Stage 3's 24 nodes at the normal 60,000, plus 300,000 reads a second of one product's page record.

The record holds the title, price and images, and is read far more than written. Stock is not in it: the stock beat explains.

The entry is 60,000 + 300,000 = 360,000 client operations a second.

A key lives on its 3 copies, one a zone. A ring of 24 nodes or 240 gives it the same 3.

The card spreads its load evenly over its nodes, so the record's 3 nodes are drawn on their own card.

The ring card holds the other 21 nodes and 21/24 of the data, 16,128 GiB of values.

Each read asks 2 copies: 300,000 x 2 / 3 = 200,000 replica reads a node. That is 434.8% of 46,000.

The result names "The hot record's 3 nodes", and its warning gives 435%.

Against the band's high end, 200,000 / 92,000 = 2.2 times. The result holds for any figure in the band.

Reads of the product record wait in line. Its three nodes get at least twice the highest figure we derive from the source, so the tile's time is a floor.

The latency tile shows "≥ 0ms". The ≥ marks a floor: the record's reads queue, so the true time is higher than any figure shown.

The record's nodes also carry their share of normal traffic, about 6,000 each, which the card omits. So 434.8% errs low.

The other 21 nodes take 60,000 x 2.4 / 21 = 6,857 a second, 14.9%. Their card reads 66% on bytes.

The cost tile shows $24k/mo: 21 + 3 = 24 nodes, the same $23,721.98 as Stage 3.

More nodes do not help. The record stays on 3 of them however large the ring grows.

On the canvas, the two edges split the entry: 0.167 to the ring, 0.833 to the record. Those shares hold only during the sale, so there are no load buttons.

Step through the figure to follow the record's reads.

The trade-off:

Three copies carry any one key. In exchange, a hot key gets exactly 3 nodes, whatever the ring costs.

One hot record on its 3 copies

1. One record, 3 copies, one a zone. 300,000 reads x 2 copies / 3 = 200,000 replica reads a node.
2. A ring of 24 nodes or 240: the record still lives on the same 3.
3. A 1 s cache in each of 500 client tasks: 500 reads reach the ring, 333 a node.

Stage 5: A flash sale on one product record

• Load: 360,000 req/sec
• First to saturate: The hot record's 3 nodes
• Estimated cost: $24k/mo

• Latency past saturation is a lower bound, not an estimate. The hot record's 3 nodes is saturated on the critical path, where the queueing model stops tracking a real queue - the true figure is higher by an amount this model cannot know. Relieve the bottleneck to get a latency number worth reading.
• The hot record's 3 nodes: Node serves 200,000 replica ops/s against the measured 46,000 (435%).

Check in: The ring grows from 24 nodes to 48. What happens to the record's 3 nodes?

Clients cache the record for one second

Stage 6 keeps the sale. The record's reads must stop at their callers.

About 500 client tasks call the ring (our estimate). Each task keeps the record in memory for 1 second.

Reads in a task that miss together share one fetch. So each task reads the record once a second.

That is 500 reads a second, not 300,000. Each asks 2 copies: 500 x 2 / 3 = 333 replica reads a node.

The record's nodes run 0.7% of the software figure. Their card shows 66.0% on bytes, like the ring card.

Nothing saturates, and the busiest note names one of the two cards at 66%.

The price: a shopper can see a page up to 1 s old. These cached reads lose the quorum guarantee.

Checkout reads the price again at QUORUM. Stock goes through the inventory service's conditional write.

The latency tile shows 0ms. The cost tile shows $24k/mo, the same $23,721.98: the cache is memory in each client task.

Say it like this: "Fix a hot read key in its callers. A 1 s cache in 500 tasks turns 300,000 reads into 500."

On the canvas, the record's edge carries 0.00139 of the entry, 500 of 360,000. That share is typed for 500 tasks, so there are no load buttons.

The trade-off:

A page up to 1 s old, and a cache in every caller. In exchange, the hot record costs the ring 500 reads a second.

Stage 6: Clients cache the record for one second

• Load: 360,000 req/sec
• First to saturate: Nothing at this load
• Estimated cost: $24k/mo

Check in: What does the 1 s client cache give up?

Why a client cache, and when another fix wins

A hot key has other fixes, on the ring or between it and the callers. An interviewer asks why the callers, and when another fix wins.

A row cache on the copies keeps the record in memory. Each request still pays its CPU and network on those 3 nodes.

A coalescing service sits between callers and the store, and merges identical reads into one. It wins when callers are many or cannot be changed.

Discord moved 177 Cassandra nodes to 72 ScyllaDB nodes; its data services coalesce reads, which fixed its hot partitions.

Reading the page at ONE, 1 copy, halves the load first: 300,000 x 1 / 3 = 100,000 a node. That is still past 92,000.

A split key stores the record under k suffixes, so k sets of copies share it. It wins when a key is hot on writes, which a cache cannot absorb.

The client cache wins here because the callers are our own services, and the page accepts 1 s of staleness.

It removes the load where it starts, at no cost on the bill.

Say it like this: "Cache in the callers when you own them. A coalescing tier when you do not, and a split key for hot writes."

The trade-off:

A client cache needs every caller to adopt it. In exchange, it removes the reads before they leave the caller.

Check in: The hot key is a counter, incremented 300,000 times a second. Does the client cache help?

Selling the last item

The sale also sells stock. Why is stock not in the cached record, and not a plain write on this ring?

A read at QUORUM, then a write, races. Two buyers read 1, both write 0, and last write wins: two sales, one item.

A QUORUM read does not stop it. Only a compare-and-set does, and there are three honest ways to get one.

A lightweight transaction: set stock to 0 only if it is still 1. Cassandra runs it as Paxos, about 4 round trips.

It runs one at a time on one partition. So a hot item takes a few hundred to a few thousand a second (our estimate, not measured).

A store with a leader for each key and a conditional write: a DynamoDB condition expression, or a Raft group.

Or stock split into k buckets, each decremented by compare-and-set, with a sold-out flag once all are empty.

So stock lives in an inventory service, and the hot record holds only the title, price and images.

Say it like this: "The ring is last write wins, so stock needs a compare-and-set: a lightweight transaction, a leader, or buckets."

The trade-off:

A compare-and-set costs round trips and runs one at a time on one key. In exchange, the store never sells an item twice.

Check in: Why does a QUORUM read before the write not stop an oversell?

Deletes, repair, the tail and the zone bill

Four questions usually follow. None changes a canvas, so we reason by hand.

Deletes: a delete writes a tombstone, a marker that the value is gone. Copies drop it after gc_grace_seconds, 10 days by default.

A copy that missed the delete must be repaired within those 10 days. Otherwise the tombstone goes, and the old value comes back.

Repair: each copy builds a Merkle tree, a tree of hashes over a range. Copies compare trees and stream only the ranges that differ.

Building a tree reads every SSTable in a range, so plan repair in the drive budget. Incremental repair re-reads only data not yet repaired.

Conflicts: this ring keeps last write wins per cell. Dynamo keeps divergent versions and merges them with vector clocks. Riak calls them siblings.

A merged cart can bring back a deleted item.

The tail: a read waits for the 2nd of 2 answers, a write for the 2nd of 3. With one copy a zone, the 2nd is always in another zone.

So the slower copies set the p99, not the average one. W 1 and R 1 buy latency and give up the overlap.

The zone bill: data between zones is not on the canvas. Each write sends 2 copies to other zones.

That is 24,000 x 2 x 1 KiB = 46.875 MiB/s. Over 2,592,000 s, 118,652 GiB a month.

AWS charges $0.01 a GB in each direction: 118,652 x $0.02 = $2,373 a month, 10% of Stage 3's ring.

We count a billed GB as 2^30 bytes; in decimal GB it is $2,548.

Reads add little: the remote copy sends a digest. A driver that is not zone-aware would add client hops across zones.

The trade-off:

Repair, hints and tombstones are the price of a leaderless store. In exchange, any copy takes a write, and no leader fails over.

Check in: Why must repair finish within 10 days?

The ring chain on one screen

Skip on a first read; come back before the interview. Every number on Stages 1 to 6 comes from the ones before it.

Units: drives are sold in decimal GB, and this page counts binary KiB, MiB and GiB. 18 TiB is 18,432 GiB.

Drive: 3,750 x 10^9 / 2^30 = 3,492.46 GiB.

Client operations: 0.6 x 60,000 = 36,000 reads, and 0.4 x 60,000 = 24,000 writes.

Replica operations: 36,000 x 2 + 24,000 x 3 = 144,000 a second, 2.4 a client operation.

Bytes a node: Stage 1, 18,432 / 15 = 1,228.8 GiB, 35.2%. Stage 2, 18,432 x 3 / 15 = 3,686.4 GiB, about 106%.

Stage 3: 18,432 x 3 / 24 = 2,304 GiB, 66.0%. Stage 4: 17,664 x 3 / 23 = 2,304 GiB.

Stages 5 and 6: 16,128 x 3 / 21 and 2,304 x 3 / 3, both 2,304 GiB.

Operations a node against 46,000: Stage 1, 4,000, 8.7%. Stage 2, 9,600, 20.9%. Stage 3, 6,000, 13.0%.

Stage 4: 6,261, 13.6%. Stage 5: the ring 6,857, 14.9%, and the record 300,000 x 2 / 3 = 200,000, 434.8%.

Stage 6: the record 500 x 2 / 3 = 333, 0.7%.

Sizing at 70%: 18,432 / (0.7 x 3,492.46) = 7.54, so 8 a zone. STCS at 50%: 10.56, so 11 a zone.

Streaming: 2,304 x 1,024 / (16 x 24) = 6,144 s, about 1.7 hours.

Price: i8g.4xlarge at $1.3728 an hour, for 720 hours a month.

Stages 1 and 2: 15 x 720 x $1.3728 = $14,826.24. Stages 3, 5 and 6: 24 nodes, $23,721.98. Stage 4: 23 nodes, $22,733.57.

Check in: Close the page and rebuild Stage 3's node count from the data size.

Say this in 45 minutes

The interviewer asks: What fails in this design, and what does a caller see?

A design that works on a good day is half an answer. The interviewer asks what fails, who notices, and what it costs.

A node dies: QUORUM holds on 2 of 3 copies. A replacement streams its data back in about 1.7 hours.

A zone is lost: every key keeps a copy in each of the other two zones, so QUORUM holds.

A write times out: the result is unknown. The client retries with the same value and timestamp.

A clock runs fast: its writes win under last write wins. So the fleet alarms on clock offset.

One key gets hot: its 3 copies carry it at any ring size. Cache it in the callers.

Compaction falls behind: reads slow while the CPU looks idle. Raise the compaction throttle, and watch pending compactions.

A deleted value comes back: repair missed gc_grace_seconds. Repair every range within 10 days.

Say it out loud: "A leaderless ring on instance store, 3 copies, one a zone, a strict quorum at W 2 and R 2."

And: "Sized by bytes first: 24 nodes hold 3 copies of 18 TiB at 66%. A hot key is fixed in its callers."

Minutes 0 to 5: requirements. Get and put, 60,000 a second, 18 TiB, a zone lost.

Minutes 5 to 12: Stage 1, hash mod n, then the ring and virtual nodes.

Minutes 12 to 22: Stages 2 and 3. Copies and the quorum, one request's states, sizing by bytes.

Minutes 22 to 30: compaction, then Stage 4, a node lost.

Minutes 30 to 38: Stages 5 and 6. A hot record, the client cache, and stock.

Minutes 38 to 45: repair and deletes, the quorum tail, and the zone bill.

The trade-off:

Each answer has a price. Copies cost drive space, a quorum costs a round trip between zones, and a cache costs freshness.

Check in: Set a timer for 45 minutes. Give the whole answer out loud, and check it against the pacing plan.