Design a Distributed Key-Value Store
Design a distributed key-value store: put, get, delete, and optionally scan(prefix) over sorted keys. Open by listing the non-functional requirements you need before choosing anything — read/write ratio, key and value sizes, latency target, durability, whether stale reads are acceptable, whether range scans are needed — and let them drive the design.
Cover partitioning, replication and the consistency it implies, the storage engine on each node, and how replicas are repaired. Then take the large-value variant: values of many megabytes live on disk, and a writer holding a key's lock while writing to disk makes every reader and writer of that key wait. Fix the contention and be ready to write the acquire-and-release pseudocode.
Hints
Hint 1
Each layer is a two-option decision with a rule for choosing: consistent hashing versus range partitions (ranges are required for prefix scans), Raft per shard versus leaderless quorums (the consistency-versus-availability call), LSM versus B-tree (write-heavy versus read-heavy), read repair versus anti-entropy (use both).
Hint 2
For large values, separate keys from values: the index maps a key to (file, offset, length) and values go to an append-only log. Write the blob with no lock held, then take the key's lock only to swap the pointer.
Hint 3
Readers copy the pointer under a shared lock, release it, then read the blob; old blobs stay valid until garbage collection, so a reader never blocks on a writer's I/O.
Asked at
Sign in to talk to the interviewer — ask what's in scope, what scale to design for, or for a nudge when you're stuck. Conversations save to your account.