Persistent Key-Value Store System Design Interview Guide

A key-value question arrives in two flavours, and the first thing you should do is ask which one is on the table. "Design a cache" (think Redis, Memcached) means speed is everything and durability is optional: a lost entry is a slower request, not lost data. "Design a persistent key-value store" (think DynamoDB, Cassandra, RocksDB) means the opposite. An acknowledged write that disappears is a bug, not a miss, and every other decision bends around that one commitment.

This guide designs the durable one. The shared distribution machinery, consistent hashing, replication topology, hot keys, capacity, is developed in the companion guide, designing a distributed cache; rather than repeat it here, this guide refers back to it and spends its space on what is genuinely different: what an acknowledgement costs, how an LSM-tree earns its write throughput, and how replicas that disagree are reconciled.

What makes the question deceptively hard is that the core operation, put(key, value) / get(key), is trivially solved with a single hash table and an fsync. The interview is really asking: what does "durable" mean when the machine holding your write dies before it answers? Which replicas have to agree before you say yes? And when two of them disagree, who wins, and how do you find out they disagreed at all?

Functional requirements

Note what is out of scope, and say so explicitly: no secondary indexes, no multi-key transactions, no joins. Each of those changes the storage engine rather than sitting on top of it, and offering them unprompted is how a 45-minute design becomes unfinishable.

Non-functional requirements

Working assumptions for this design: 10 TB of logical data, 250k writes/sec and 500k reads/sec at peak, replication factor N=3.

Rationale behind each NFR

A cache is sized by its working set: how much RAM buys how high a hit rate. A persistent store has no working set to speak of, it holds everything, so the sizing question is different and mostly about disk. Three numbers matter, and only one of them is the obvious one.

Bloom filter memory is worth a sentence because it is the one RAM cost that scales with the dataset rather than with traffic: at ~10 bits per key it is the stored record count that matters, not the logical one, so 20B keys at N=3 is ~75 GB of filters across the cluster and ~4.7 GB on each of 16 nodes. It is also the cost you least want to cut, because the filters are what keep a point read from touching every level.

The cache-sizing question, how much RAM buys how high a hit rate under a Zipf distribution, is a different calculation with a different shape; there is an interactive estimator for it in the cache guide.

The shape of this system is the thing most candidates get wrong, because they reach for the picture they have drawn before: a cache in front, a database behind. There is no such split here. Every node is a full participant, holding a token range of the keyspace and running a storage engine on its own local disk. A client's request is handled by whichever node it reaches, acting as coordinator for that one request, which fans it out to the N replicas that own the key and waits for W or R of them.

That is the structural difference worth stating plainly: the durable layer is not a tier behind the system, it is the system. There is no cache-aside path, no miss, no second hop to a database. Requests that a cache would have absorbed are served by the same nodes that store the data.

Coordinator is a role, not a machine. Any node can play it, which is what keeps the request path free of a single point of failure and of a global lookup. The coordinator hashes the key, finds the N nodes that own it on the ring (§5), sends the request to all of them, and applies the quorum rule to the responses it gets back.

Replicas each hold a full copy of their token ranges and run the same storage engine: a commit log for durability, a MemTable for the current writes, and immutable SSTables on disk (§7). Nothing about a replica is special, which is what makes losing one survivable and adding one mechanical.

Membership is tracked by gossip rather than an external coordinator. This is the opposite of the choice the cache guide makes, and deliberately so: a cache cluster wants fast, arbitrated failover to a new primary, while this design has no primary to elect. Every replica can serve, so what it needs is an eventually-consistent view of who is alive, which gossip provides without adding Zookeeper as a dependency on the write path.

Architectural rationale

The partitioning mechanism here is the standard one and it is not what distinguishes this design: both nodes and keys are placed on a circular hash ring, each key belongs to the first node clockwise from its position, and each physical node takes many virtual positions so the load spreads evenly. Adding a node moves roughly 1/N of the keyspace rather than reshuffling everything. That machinery, including why naive hash(key) % N remaps about 75% of keys when you add a fourth node, the role of virtual nodes, and rendezvous hashing as an alternative, is developed with diagrams in the cache guide. It is identical here.

What is not identical is what a token range contains. In a cache, a range holds a copy of something that exists elsewhere, so moving a range is a warm-up problem: the new node starts cold and fills as traffic arrives, and the worst case is a period of extra misses. In a persistent store the range is the data. Three consequences follow, and they are what an interviewer is looking for once you have said "consistent hashing".

What changes when the partition owns durable data

The surface area is intentionally small — get, put, delete — and almost all of the interesting design is in what the response tells the caller. A durable store has to expose three things a cache never does: which consistency level the operation ran at, what version of the value this is, and how the caller should behave when two versions come back. An API that hides those is an API that cannot honestly claim tunable consistency.

Core endpoints

GET /v1/keys/{key}

// Request — consistency is per-call, not per-cluster
GET /v1/keys/user:1234:profile?consistency=quorum HTTP/1.1

// Response
HTTP/1.1 200 OK
X-Consistency: quorum        // what actually ran: one | quorum | all
X-Replicas-Responded: 2/3
X-Read-Repair: triggered     // a stale replica was found and is being fixed
{
  "key": "user:1234:profile",
  "value": "{\"name\":\"Ada\",\"tier\":\"gold\"}",
  "version": "a1b2:7,c3d4:2",   // opaque causal token — see §8
  "updated_at": "2026-09-17T12:00:00Z"
}

// Response, key absent — or deleted and the tombstone has not yet been reaped
HTTP/1.1 404 Not Found
{ "error": "key_not_found" }

Two details are worth defending out loud. consistency is a request parameter because the same store serves a profile read that can tolerate a stale replica and a balance read that cannot, and forcing both to the strict setting is how you pay quorum latency for traffic that never needed it. And version is opaque — the client is expected to echo it back, never to parse or compare it. The moment clients start interpreting versions, the conflict-resolution strategy in §8 becomes a public contract you cannot change.

PUT /v1/keys/{key}

// Request
PUT /v1/keys/user:1234:profile HTTP/1.1
Content-Type: application/json
{
  "value": "{\"name\":\"Ada\",\"tier\":\"platinum\"}",
  "if_version": "a1b2:7,c3d4:2",  // the version this write is based on
  "consistency": "quorum",        // W: one | quorum | all
  "ttl_seconds": null              // optional expiry; null = keep forever
}

// Response — returned only after W replicas have it in an fsynced log
HTTP/1.1 200 OK
X-Consistency: quorum
X-Replicas-Durable: 2/3
{ "status": "ok", "version": "a1b2:8,c3d4:2" }

// Response — could not reach W replicas within the timeout
HTTP/1.1 503 Service Unavailable
{ "error": "insufficient_replicas", "required": 2, "durable": 1,
  "hint": "the write may still be applied — retry is safe only if idempotent" }

DELETE /v1/keys/{key}

DELETE /v1/keys/user:1234:profile?consistency=quorum HTTP/1.1

HTTP/1.1 204 No Content  // success — writes a tombstone, not a removal
HTTP/1.1 404 Not Found   // no live version found (idempotent, safe to repeat)

A delete in a replicated LSM store is a write: it appends a tombstone that shadows every older version of the key until compaction reclaims them (§7). It cannot be an in-place removal, because a replica that was down during the delete would otherwise resurrect the old value the moment it came back and anti-entropy compared it against a key that simply is not there. The tombstone is what lets a returning replica learn that the absence is intentional.

Optional endpoints by level

Conditional writes & compare-and-swap

The if_version field turns a blind overwrite into optimistic concurrency control. Two clients read the same key and both receive version a1b2:7. Both compute a new value and write. The first wins; the second is rejected with the current version and must re-read, re-apply its change, and retry. This is the standard answer to "how do you prevent lost updates without distributed transactions", and it is worth being precise about what it costs.

// Response on conflict
HTTP/1.1 409 Conflict
{ "error": "version_mismatch",
  "current_version": "a1b2:8,c3d4:2",
  "hint": "re-read and retry" }

The uncomfortable part is that on a leaderless store, a compare-and-swap is not free and not quite atomic. The coordinator can only compare against the versions it saw from the R replicas that answered; a partitioned replica may be holding a newer version it has not shown anyone. Two honest ways to close that gap, and interviewers at L6+ will push until you name one:

• Read and write at all for the keys that need CAS. Every replica is consulted and every replica is updated, so nothing can be hiding. You have traded availability for correctness on those keys specifically — which is the right trade for a balance and the wrong one for a profile.
• Run consensus for that one operation. Cassandra's lightweight transactions do exactly this: a Paxos round per conditional write, roughly four round-trips instead of one. DynamoDB exposes the same guarantee as a ConditionExpression, cheaply, because its partitions are leader-based underneath and the leader can decide alone.

The point to land is that conditional writes are where a leaderless design pays for the leader it does not have. Everything else in this system is cheaper without a leader; this one operation is dramatically more expensive.

Security & multi-tenancy

Three controls are non-negotiable at L6+, and the durability requirement changes what the third one means. First, namespace isolation: prefix every key with a tenant identifier and enforce it at the coordinator, so a cross-tenant read is not expressible rather than merely forbidden. Second, authentication and per-service credentials, with the storage nodes on a private subnet — the inter-node replication port is a far more attractive target than the client API, because it speaks for the cluster rather than for one user. Third, encryption at rest, which a cache can often skip and this system cannot: the data is on disk by design, and it stays there through compaction, snapshots and backups. Encrypt the SSTables and the commit log, and remember that a key rotation has to survive files written months apart.

Two more that come up at L7+: value size limits enforced at the API tier, because a multi-megabyte value is not just memory pressure but a partition that compaction can never rewrite cheaply; and per-tenant rate limiting at the coordinator, since one tenant's hot partition degrades every tenant that shares those replicas.

A cache's read path is a story about misses. This system has no misses: every key either exists or does not, and the nodes that own it are the only place it could be. The interesting question moves to the write path, and specifically to the moment the coordinator decides it has heard enough to say yes.

The write path

Read the sequence as four decisions rather than six steps:

1. Any node coordinates. The client did not have to find the right node, and there is no routing tier that could go down. The coordinator hashes the key, walks the ring to the N owners, and sends the write to all of them at once, not to W of them. Sending to all and waiting for W is what makes a slow replica cost nothing.
2. Each replica makes the write durable before answering. Append to the commit log, fsync, apply to the MemTable. An acknowledgement that skips the fsync is the single most common way a design that claims durability does not have it.
3. The coordinator answers at W, not at N. With W=2 the client waits for the second of three responses, so one slow or dead replica is invisible. This is also exactly why the p99 write budget is 10 ms rather than 5: waiting for the second of three is a worse tail than waiting for one.
4. The write that did not land is remembered, not lost. The coordinator keeps a hint for the replica it could not reach and replays it when that node comes back. Without hinted handoff, every node restart would leave a permanent hole that only anti-entropy (§8) eventually finds.

The read path

The read is the mirror image, with one addition. The coordinator sends the read to all N replicas, waits for R of them, and then has to do something a cache never does: decide which answer is right. Two replicas returning different values is not a fault. It is the expected result of a write that was acknowledged at W=2 while the third replica was down. The coordinator compares version metadata, returns the winner, and, if it saw a stale replica, writes the winning value back to it in the background. That last step is read repair, and it is the cheapest of the three mechanisms that keep replicas converging, because it costs nothing on the keys nobody reads.

A common follow-up is why you would ever read from more than one replica when they are all supposed to have the data. The answer is that "supposed to" is doing the work: at W=2 of N=3, one replica is allowed to be behind at any moment, so R=1 is a coin flip weighted by how recently that replica was down. R=2 makes the overlap argument work. How the winner is actually chosen, and why a plain timestamp is a trap, is §8.

Everything so far has treated a replica as a box that stores things. This is the section where you open the box, and it is the section that separates a distributed-systems answer from a storage answer. The requirement driving all of it was set in §2: a write must be durable before it is acknowledged, on a 10 ms p99 budget, on a device where a random write is expensive and a sequential write is not.

That single constraint rules out the obvious design. Updating a record in place means finding it first — a seek — and then writing a partial page, which on an SSD means the drive reads an erase block, merges your bytes in, and writes it back. The log-structured merge tree's answer is to never update anything: every write is an append, and the cost of keeping the data organised is paid later, in the background, in large sequential batches.

What is actually stored

Each record carries more than the value, and each field earns its place:

{
  "key":        "user:1234:profile",
  "value":      <opaque bytes>,
  "version":    "a1b2:8,c3d4:2",     // who wrote it, and after what — §8
  "timestamp":  1789564800123,        // tie-break of last resort
  "tombstone":  false,                // a delete is a write
  "ttl":        null
}

The tombstone flag is the one people forget, and it has a consequence that reaches the operations section: tombstones cannot be dropped the moment compaction sees them. If a replica has been down for longer than the tombstone lived, it will come back still holding the old value and anti-entropy will happily propagate it back. So a tombstone must survive at least gc_grace — long enough that a down replica is either repaired or declared dead. Compact too eagerly and deleted data returns from the dead, which is the failure mode most likely to end up in a postmortem.

Why the write is fast, precisely

Walk the budget from §2. The commit-log append is sequential, so the device does no seek. The fsync is the only synchronous disk operation on the path, roughly 1 ms on an enterprise NVMe drive with a power-loss-protected write cache. Applying to the MemTable is a skip-list insert, tens of nanoseconds. Nothing else touches disk. One sequential append and one fsync is the entire cost of a durable write — the SSTables, the sorting, the levels are all built later by a background thread that no client is waiting on.

Compaction, and the three amplifications

Compaction merges SSTables, discards shadowed versions, and drops expired tombstones. Compaction is not housekeeping — it is the mechanism that decides what the read path costs, and the strategy you choose is a direct trade between three quantities:

You cannot minimise all three. The two mainstream strategies sit at opposite ends:

For this design, levelled compaction is the right default, and the reasoning is the traffic mix rather than a preference: reads outnumber writes two to one, and a read that misses the cache has to touch every level it cannot rule out, so paying more on the write path to keep read amplification near one is trading the cheaper side for the more expensive one. The honest cost to state alongside it is that levelled compaction writes roughly 10–30 bytes for every byte the client sends, which is a real number on SSD endurance and a real amount of background IO competing with the foreground reads you just optimised.

§6 ended on an admission: at W = 2 of N = 3 the coordinator will sometimes read two different values for the same key and has to pick one. That is not a bug to be engineered away — it is the direct, intentional consequence of acknowledging before every replica has the write. This section is about what you do with it, and it is the part of the design most likely to be probed hardest, because the wrong answer here loses data silently.

Be precise about the two situations that look identical and are not. A replica that is simply behind has an older version of a write it will eventually receive; there is a right answer and the system just has to deliver it. Two clients that wrote concurrently, each without having seen the other, have produced two equally valid values; there is no right answer, and any mechanism that silently picks one is choosing to lose a write. Telling these apart is the entire job of version metadata.

Last-write-wins, and why the timestamp is a trap

The simplest resolution is to stamp every write with a wall-clock time and keep the larger one. It is O(1), needs no client cooperation, and it is what Cassandra does by default — so it is a defensible answer, provided you say the cost out loud rather than being told it.

The cost is that it cannot distinguish "older" from "concurrent", so every concurrent write becomes a silently discarded write, and it inherits every clock problem the fleet has. Tens of milliseconds of skew between two nodes is ordinary under healthy NTP; under a failed NTP daemon, seconds. A write that genuinely happened second but landed on the node with the slow clock loses — and nothing anywhere reports an error. The client got its 200 OK. This is the specific failure interviewers are listening for: LWW makes lost updates invisible.

It is the right choice when writes to a single key are rarely concurrent and the value is a whole-object overwrite — a user profile, a device setting. It is the wrong choice for anything accumulative: a counter, a cart, a set of tags.

Version vectors

The alternative is to track causality instead of time. Each key carries a small map of node → counter; the coordinating node bumps its own entry on every write. Version X descends from version Y if every counter in X is greater than or equal to Y's. If neither descends from the other, the writes were concurrent, and the system knows it.

// Ada and Ben both read the cart at version {A:1}
put  cart:42  ["book"]              → version {A:1}

// Ada adds a pen. Coordinated by node A, based on {A:1}
put  cart:42  ["book","pen"]        → version {A:2}

// Ben adds a mug at the same moment. Coordinated by node B, also based on {A:1}
put  cart:42  ["book","mug"]        → version {A:1, B:1}

// Neither descends from the other: A:2 > A:1, but B:1 > B:0.
// The read returns BOTH — these are siblings.
get  cart:42  → [ {["book","pen"], {A:2}},
                  {["book","mug"], {A:1,B:1}} ]

// The client merges (union, for a cart) and writes back a version
// that descends from both, which collapses the siblings.
put  cart:42  ["book","pen","mug"]  → version {A:3, B:1}

The famous illustration is Amazon's shopping cart, and the reason it is famous is the trade it makes: DynamoDB's predecessor chose that an item mistakenly reappearing in your cart is a better outcome than an item silently vanishing. Union-merging siblings can resurrect a deleted item; it can never lose an added one. That is a business decision expressed as a data structure, and naming it that way is worth more than reciting the algorithm.

Two honest costs. Version vectors grow with the number of nodes that have ever coordinated a write to the key, so implementations truncate the oldest entries — which can reintroduce false concurrency. And they push work onto the client: every reader must be able to receive several values and merge them. If you cannot change the clients, you cannot use this, and that constraint alone decides the question in many real systems.

The three repair mechanisms

Detecting divergence is not enough; replicas have to converge. Three mechanisms do it, at three different timescales, and a complete answer names all three because each covers what the others miss.

Read repair and hinted handoff are easy to describe. Anti-entropy is the one with an interesting data structure behind it, because the naive version — compare every key on every replica — would move the entire dataset across the network to discover that almost nothing differs.

Merkle trees

Tuning consistency per call

Because W and R are request parameters (§5b), one cluster can serve several consistency contracts at once. The rule is W + R > N for read-your-writes on a single key; below it, you are choosing eventual consistency deliberately.

Scaling this system is mostly uneventful, and that is the point of the choices made in §4 and §5: no leader to become a bottleneck, no routing tier to saturate, and a ring that spreads both data and traffic. What does not scale automatically is everything that involves moving bytes — adding a node, losing one, or crossing a region boundary — because those are bounded by disk and network rather than by request rate.

A cache's failure modes are mostly about latency: something misses, something falls through, something gets slow. This system's failure modes are about data, which is why they are worth more in an interview and why the answers have to be specific. The ones that matter most are the quiet ones — the failures where every request returns 200 OK and the data is wrong anyway.

Classic probes table

Every architectural decision in this article is downstream of about twenty numbers. Not one of them needs to be precise. What earns credit is knowing which number settles which argument: why the acknowledgement waits for two replicas and not three, why the cluster provisions 40 TB for 10 TB of data, why repair speed matters more than the replication factor.

The pattern to practise is a single move: name the number, then name the decision it closes. “A spinning-disk seek is 4–10 ms and the entire write budget is 10 ms, so the log goes on NVMe” is a complete argument in one breath. Reciting latency tables without attaching them to a choice is not.

Latency: the numbers that set the budget

Capacity and throughput: the numbers that decide how many boxes

These answer “how big is this cluster” — and the important ones are the multipliers, not the inputs. Quoting logical data and logical write rate is the most common way to arrive at a cluster three times too small.

Durability and repair: the numbers nobody quotes and everybody should

At L6 and above the strongest opening move on this question is often not a diagram. It is: "we almost certainly should not build this — here is what I would run instead, and here is the specific thing that would make me change my mind." Everything in this article is a description of systems that already exist and have absorbed a decade of operational scar tissue each. Rebuilding one is a multi-year commitment whose main deliverable is repair tooling.

So know the landscape well enough to pick from it. The four systems below all implement most of this design; they differ in the parts you now know are expensive.

When building it is the right answer

There are real cases, and they are narrower than people expect. Name a specific one rather than gesturing at scale:

• The managed option's pricing inverts at your scale. Per-request pricing that is trivial at 10 K QPS is a large line item at 500 K QPS sustained. This is the most common honest reason, and it is an arithmetic argument, not an engineering one.
• You need a merge the store must perform itself. If clients cannot be changed to resolve siblings, and the value is a type with a real CRDT merge, a store that converges internally is a capability none of the above offer in the form you need.
• Placement is a hard constraint. Data residency that requires specific keys to live in specific jurisdictions, enforced at the partitioner, is genuinely difficult to bolt on.
• You are the cloud provider. Somebody has to build it.

What is not a reason: "our workload is special", "we want full control", or "it would be faster". A candidate who says the first two unprompted and then argues past them is more convincing than one who never raises the question.

L6+ candidates are expected to own the system end to end, and this system has an unusual property that makes that harder than it sounds: its worst failures do not show up as errors. A cluster silently losing writes to clock skew, or quietly resurrecting deleted rows because repair has been failing for a fortnight, looks perfectly healthy on a latency dashboard. So the signals worth instrumenting are not the obvious ones.

Key metrics to monitor

Safe operations playbook