Design a Key-Value Store, From the Single-Node Storage Engine to Replication

Design a key-value store: clients store a value under a key, read the value for a key, and delete keys. The round reported only the topic, so settle with the interviewer whether this is a single-machine store, a distributed one, or one that grows from the first into the second, and which guarantees it must give. ```hint Before you say "OK" Decide what must be on disk before a put is acknowledged, and how the store rebuilds its state after a crash without losing acknowledged writes. ``` ```hint Moving keys between machines When a node is added or removed, consider how many keys your placement scheme forces to move, and what a reader sees while they are moving. ``` ### Constraints and Clarifications - Not given: data size, key and value sizes, read and write rates, latency targets, consistency requirements, and whether range scans are needed. Ask, or state your assumptions. ### Clarifying Questions - Does the data fit in memory on one machine, and must it survive restarts? - What are typical key and value sizes, the total data size, and the read and write rates? - After a successful put, must every later get return the new value, or is eventual consistency acceptable? - Are range scans over ordered keys needed, or only point lookups? - Are expiry times, compare-and-set, or multi-key transactions needed? - During a network partition, should the store refuse some requests or accept writes on both sides? ### What a Strong Answer Covers - Requirements settled first: API, sizes, consistency, durability, scans - A single-node storage engine with a durable write path, an efficient read path, and a plan for deletes and space reclamation - Partitioning that spreads keys evenly and limits data movement when the cluster changes - Replication with an explicit consistency model and the quorum or consensus mechanism that delivers it - Failure handling (node loss, leader failover, recovery, rebalancing) and observability ### Follow-up Questions - One key receives a large fraction of all reads. What do you do? - A client writes a key and immediately reads it through another replica. How do you guarantee it sees its own write? - Range scans become a requirement. What has to change? - A network partition splits the replicas of a shard two to one. What do clients on each side see?