Design a distributed key-value store

01Choose the meaning of a successful operation

A key-value store maps a tenant’s key to value bytes whose contents it does not interpret. Offer exact-key GET, PUT and DELETE, with optional expected-version conditions. Exclude joins, arbitrary search, global range scans and multi-key transactions. Those operations require additional indexes or coordination and should not appear accidentally through an underspecified API.

Use cart-42 at version 7. Client A adds a pen while client B removes a book, both from version 7. The store cannot decide how the shopping application should merge those intentions. It can ensure only one conditional replacement succeeds; the other client rereads and decides what to do next.

Choose strong per-key operations in one home region: a read begun after a successful write returns that write or something newer. This is linearizability, a real-time ordering contract. An isolated replica cannot simply keep accepting conditional updates or serving old values as current. A separate stale-read option can exist, but must be named explicitly.

Assume 1 KiB average values, a 1 MiB maximum and a 20 ms normal-operation p95 target. Acknowledged mutations should survive one replica-node or zone failure, with replica placement chosen accordingly. Regional disaster recovery is a separate promise.

Clarify whether callers need strong current reads or may accept stale replicas, whether operations cover one key or several, and what failure must preserve an acknowledged write. This answer chooses exact-key linearizable operations in one home region with one-zone failure tolerance.

02Functional requirements

1. Read and mutate exact keys. Provide authenticated GET, PUT and DELETE for opaque value bytes under a tenant’s key.

2. Update conditionally. Accept an expected version so clients can reject a replacement based on an outdated value.

3. Recover mutation retries. Return the stored outcome for the same request identity and payload within the supported retry horizon, including after a lost response.

4. Distribute and recover data. Route keys to their current owner and support safe replica recovery and partition movement without changing the client’s key or operation meaning.

03Non-functional requirements

These are illustrative interview assumptions, not product facts or measured benchmarks. Confirm them before choosing components, then validate the completed design under the stated workload. Here p95 means the 95th-percentile latency: 95% of measured requests take no longer than that value. Report errors and rejected work alongside latency; a fast failure is not a successful outcome.

1. Capacity and size limits. Plan for ten billion live keys, 100,000 reads/s and 20,000 writes/s, with 1 KiB average values and a 1 MiB maximum. Budget three copies plus indexes, maintenance and retry history.

2. Latency. Target 20 ms p95 for admitted same-region exact-key operations under normal load. Benchmark durable writes, strong reads and ongoing compaction together; timeouts are misses, not fast successful operations.

3. Consistency. Provide linearizable per-key reads and mutations: a read started after a successful write sees it or something newer. Only one conditional replacement of the same current version may succeed.

4. Durability and failure boundary. Use three consensus replicas placed across zones so acknowledged mutations survive one replica or zone failure. Stop strong operations in a partition that lacks a safe majority; regional disaster survival is outside this promise.

5. Retry and tenant isolation. Retain mutation outcomes for the selected one-hour retry horizon. Authenticate tenant scope on every path, reject conflicting request-ID reuse and enforce byte as well as operation quotas.

04Begin with one durable storage owner

The baseline is one server using a tested local storage engine. The server authenticates the tenant, identifies the key and processes its changes in order. Before changing cart-42, the owner checks whether this request identity already has a saved result. If so, it returns that result after confirming the payload matches.

For a new conditional PUT:

1. Compare expected version 7 with the current value inside the same atomic operation that installs the replacement.

2. On success, write the new value, a fresh version and the saved request result together.

3. Make the operation durable before replying.

A crash after commit but before response can then recover both the value and what the caller should receive.

GET reads the current committed value. DELETE writes an ordered deletion marker rather than relying on an untracked physical erase. Recreating the key receives a new version so an old expected-version token cannot accidentally match a later incarnation.

This single-owner version is complete for local concurrency and process restart under the engine's guarantees. It cannot tolerate losing the only disk or serve while that machine is unavailable. Replication is the next change because of those specific limits, not because a dictionary automatically becomes distributed when copied.

05Separate stored data from rewritten bytes

Assume 100,000 reads/s and 20,000 writes/s. With 1,024-byte average values, value ingress is 20.48 MB/s, about 1.77 TB/day. That is write traffic, not necessarily new live storage: repeatedly replacing the same cart rewrites bytes without adding a new live cart each time.

Ten billion live keys at 1 KiB plus 100 bytes of key/version overhead require about 11.24 TB logically. Three copies require 33.72 TB before engine indexes, logs, temporary compaction files and failure reserve. If a tested node has 500 GB of usable live-data capacity, the ratio suggests about 68 node equivalents, not a final fleet layout. Placement, throughput and failure headroom still determine the actual topology.

Retaining one hour of results at 20,000 mutations/s means 72 million results. At an illustrative 100 bytes each, that adds 7.2 GB logically before replication and indexing; rejected conditions may also need saved outcomes.

Read payload is roughly 102.4 MB/s before overhead. A hot key can dominate one owner despite comfortable total bandwidth. Benchmark durable writes and steady-state storage maintenance, not only an in-memory map. Client retries increase attempted traffic during outages without increasing useful completed writes.

06Make versions and request identities distinct

Interfaces

Conditional replacement request

PUT /kv/cart-42

Request fields for client A’s update

expectedVersion: 7
requestId:       the stable identity reused for this attempted update
value:           replacement cart bytes containing A’s added pen

Conditional delete request

DELETE /kv/cart-42

Delete request fields

expectedVersion: the version being deleted
requestId:       the stable identity reused for this attempted deletion

Stored records

A version identifies the state being replaced. A request ID identifies the attempted operation. Reusing an ID with another value or condition must fail; otherwise a caller could accidentally retrieve the result of unrelated work. Tenant identity comes from authentication on every access path.

Specify a retry horizon, such as one hour, rather than retaining results forever by implication. Older uncertain operations require status recovery or an application-level decision after rereading; issuing a new unconditional write blindly can repeat the original change. Return distinct conflicts, size-limit errors, admission limits and unavailable outcomes. A network timeout alone cannot establish whether the mutation committed.

07Give each partition one agreed command history

Use a proven leader-based consensus implementation for each replica group, with three appropriately placed replicas in this exercise. The leader proposes commands to an ordered log. The protocol determines when a command is durably committed and ensures a valid replacement leader preserves committed history. Apply a committed command before acknowledging its application result.

Suppose two commands expect version 7. A's command is applied first, finds version 7 and creates version 8. B's command is applied next, sees version 8 and records a conflict. The comparison occurs while applying the agreed order, not in an earlier unprotected read. Two callers therefore cannot both successfully replace the same current version.

The local engine applies the value or deletion marker, saved result and applied-log position as one recoverable batch. After a crash, recovery knows which commands are installed and which must be replayed. An in-memory duplicate-request cache alone would lose the result when leadership changes.

Three copies are not sufficient without the protocol. If A acknowledges before another durable copy receives the update, losing A can lose a successful write. If a replacement leader can choose an obsolete history, waiting for extra copies still does not establish safe failover. Use the library's supported election and membership rules rather than inventing them during the interview.

08Explain why a strong read cannot trust an old leader

A client routes GET to the partition leader, but the process still needs to establish that its authority is current. Imagine A loses contact with B and C. They elect a new leader and commit version 8 while A's disk still contains version 7. A must not answer a later strong GET from its isolated local copy.

One supported approach uses the consensus protocol to confirm leadership with a quorum and obtain a safe read position. The leader waits until its local state has applied through that position, then returns the key. A correctly implemented lease can be an alternative, but it adds timing assumptions that the baseline need not introduce.

A storage-engine block cache speeds disk access without changing which committed state is read. An independent application value cache cannot silently serve this strong API unless it has an appropriate freshness-validation protocol. Followers may support explicitly stale reads for callers who accept them, with different documented semantics.

Not-found responses also matter: after a successful creation, an old replica saying “absent” violates the same promise as returning an old value. During majority loss, the affected partition becomes unavailable for strong operations even if its surviving node can still answer network requests.

09Partition independent keys and preserve ownership on moves

Hash the authenticated tenant and key into logical partitions. A routing directory maps each partition to its replica group. Many logical partitions may share physical nodes; choosing many manageable units allows capacity changes without moving an entire server's data at once. A cached directory reduces lookup work, while stale owners reject or redirect requests using a placement version.

Different partitions can process independent keys in parallel. A single hot cart still has one ordered mutation history. Moving that partition to a larger owner can help resource pressure, but adding hash partitions does not create parallel successful replacements of the same version. Splitting that value into subkeys would change which updates can commit together.

To move a partition, transfer a consistent snapshot, replay subsequent committed changes and verify the destination is caught up before activating its ownership. Include values, deletion markers, versions and request-result history. Copying only live values would lose retry safety and might resurrect deleted state.

Coordinate cutover through the replication system's supported configuration protocol and a current routing generation. The previous owner must lose write authority before an independent new owner accepts conflicting commands. Updating the directory before the copy is ready creates a missing or stale partition, not a completed migration.

10Explain storage maintenance without designing a new database

A log-structured merge storage engine keeps recent entries in an in-memory sorted structure backed by recovery data, then writes sorted immutable files. Background compaction combines files and discards obsolete versions when safe. This can support efficient sustained ingestion, but it consumes CPU, I/O and temporary disk space after the original write returns.

Reads may consult several structures. Bloom filters help skip files that definitely lack a key; a positive result only means the file may contain it. A block cache helps repeated reads. Neither feature changes the store's consistency contract or replaces the authoritative version decision.

A deletion marker suppresses older values still present in files or replicas. Remove it only when the supported repair, snapshot and retention rules ensure that old state cannot reappear. Physical removal from backups follows a separate retention policy. Immediate API deletion does not imply that every historical byte vanished immediately.

A B-tree engine is a valid alternative for another measured read/write mix. Explain which work the local engine performs, then discuss write amplification, read amplification and resources reserved for maintenance. A local engine such as RocksDB does not independently provide distributed routing, consensus or request deduplication; those belong to the system around it.

11Recover while protecting foreground capacity

Apply tenant quotas in bytes as well as operations: a 1 MiB write costs much more than an average 1 KiB write. Reserve bandwidth for foreground requests and throttle compaction, catch-up and migration when they compete for the same disks. Unlimited buffering converts a transient stall into memory exhaustion and extreme latency.

Monitor committed-operation tail latency, conflicts, unavailable partitions, leader changes, synchronization latency, compaction backlog and hot-key concentration. Distinguish attempts from proposals and successful mutations to see retry storms clearly. Test leader loss at commit boundaries, old-leader reads, deleted-key recreation and migration during retries. A successful backup job is insufficient until a restore produces a validated state.

12Check the design against its requirements

Use the numbered requirements to check the final design. FR refers to the functional list; NFR refers to the non-functional list. Performance rows specify tests still required, not achieved benchmark results.

13Rapid revision

Remember: Save the new value and request result together, so a retry can return the result of the original write.

Close with the cart-42 conflict and lost-response example. The deliberate cost is minority-side unavailability. If asked to accept writes in disconnected regions, discuss a different merge or conflict contract before changing the topology; the original immediate conditional-update guarantee cannot simply remain on both isolated sides.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.