The Store

Design a distributed key-value store that is strongly consistent and available under node failures.

What is the quorum overlap rule (W + R > N)? Give an example of how it guarantees you read the latest write.

How does DynamoDB handle write conflicts when two clients write the same key concurrently?

What is the difference between a key-value store and a distributed cache? Can you use Redis as a persistent store?

Describe the read-repair pattern in a distributed store. When does it happen and what problem does it solve?

Implementing get without a read quorum

Symptom: Stale reads: a client reads a value that has been overwritten by a concurrent write on another node.

Not handling concurrent writes with the same key

Symptom: Two concurrent puts result in different nodes holding different values; reads return different results depending on which node you ask.

Returning a success to the client before the write is durable

Symptom: Client sees a successful write but the value disappears after a node restart.

Not propagating deletes — only overwrites

Symptom: Deleted keys re-appear after anti-entropy sync with a node that missed the delete.

O(n) scan for every read instead of an index lookup

Symptom: Read latency grows linearly with the number of keys; the store becomes unusably slow with thousands of entries.

Storage Engines: B-Tree vs LSM-Tree

The storage engine determines how data is laid out on disk, which directly impacts read and write performance, space amplification, and compaction behaviour.