Design Key-Value Store

Assume a multi-tenant regional service with 4 million operations a second at peak, 70% of them reads, 40 billion items averaging 1.5 KB, and three replicas of everything.

The data plane has two layers. Request routers are stateless servers that authenticate the caller, check the table's rate limits, hash the partition key, and look up which partition and which leader own that hash in a cached partition map. Storage nodes host many partition replicas each. Every partition has three replicas in three availability zones forming one Raft group, with one leader that serves strong reads and all writes.

The control plane owns the partition map and never sits on the request path. It stores tables, partitions, hash ranges and replica placement in a small replicated metadata store. A placement manager watches partition sizes, request heat and node health, and decides when to split a partition, move a replica or replace a dead node. Routers subscribe to map changes; if a router sends a request to the wrong node anyway, the node answers with a redirect and the current map version.

Each storage node runs an LSM engine per partition, or one shared engine with partition-prefixed keys. Committed writes also flow to a change stream so other systems can react, and log segments and SSTables are shipped to object storage for backups and point-in-time restore.

The router hashes the partition key to a 64-bit value. The table's hash space is cut into ranges, one per partition, and the map says which range holds that value and which replica currently leads. This is consistent hashing in spirit, since adding capacity only moves the keys in the ranges being split or moved, but with explicit, centrally managed ranges instead of a ring of random virtual nodes. Explicit ranges let the placement manager split a hot range at its median or move one replica without reshuffling anything else.

Sort keys do not affect placement. All items for customer#4410 live in one partition, ordered by sort key, which is what makes range queries cheap. It is also what makes a giant partition key a problem, which we deal with below.

The leader checks any condition against its current state, assigns the next version, and appends the write to its Raft log. It sends the entry to both followers in parallel. As soon as one follower has written it durably, two of three copies exist in two zones, and the entry is committed. The leader applies it to its in-memory table and replies. The slower follower catches up in the background.

Because a single leader orders every write to a partition, conditional writes and version numbers are trivial: the leader always has the latest value. Strong reads also go to the leader, which must be sure it is still the leader. Rather than run a round of consensus per read, the leader holds a time-bounded lease that followers promise not to undercut by electing someone else. As long as the lease is valid, local reads are linearizable. Eventual reads can go to any replica and may be a few milliseconds behind.

If the leader fails, followers stop hearing heartbeats, and after an election timeout of a second or two one of them, necessarily one with every committed entry, becomes leader. Writes to that partition pause for that window. Clients that timed out mid-write do not know whether it committed, so conditional writes with versions, or idempotency tokens stored with the item, let them retry safely.

A committed write lands in a sorted in-memory table, already protected by the Raft log, which doubles as the write-ahead log. When the memtable reaches about 64 MB, it is written to disk as an immutable sorted file, an SSTable, in one sequential pass. Disks are good at sequential writes, so write throughput stays high even with small random keys.

Reads check the memtable, then SSTables from newest to oldest. Each SSTable has a Bloom filter that answers "definitely not here" for almost every file, and a sparse index that points to the right block. With filters and a block cache, a point read usually costs at most one disk read.

Files accumulate, so a background compaction merges them, keeping only the newest version of each key and dropping tombstones that are old enough. Leveled compaction keeps read and space amplification low at the cost of rewriting data several times; size-tiered compaction writes less but leaves more files to search and needs more spare disk. A read-heavy multi-tenant service usually prefers leveled. Compaction must be rate limited so it never starves foreground requests of disk bandwidth.

When a partition passes about 10 GB or sustains more traffic than one leader should take, the placement manager splits it. The split point is the median of the hash range for size, or the observed traffic median for heat. Both halves stay on the same three replicas at first, so a split is a metadata change and nearly instant. Afterwards, the manager moves one half's replicas to less loaded nodes by adding a new replica, letting it catch up from a snapshot and the log, then removing an old one. At no point does the Raft group lose its majority.

Hashing spreads different keys well but cannot split one key. If one partition key receives 50,000 writes a second, no split helps. The system can absorb short bursts with per-partition burst credit and by placing hot leaders on lightly loaded nodes, but the real fix is in the data model: add a random suffix to hot keys and read across the suffixes, or put a cache in front for read-heavy keys.