Redis Distributed Key-Value Store
Design a distributed key-value store: partitioning, replication, consistency, and fault tolerance.
What is a distributed key-value store?
A distributed key-value store saves a value under a unique key and spreads those records across multiple machines. Applications use simple operations such as PUT, GET, and DELETE; the store decides which partition owns the key, where copies live, and how many replicas must agree before an operation succeeds.
In plain language, it behaves like a very large dictionary that survives machine failures. The hard part is not looking up a key. It is preserving an honest consistency contract while partitions move, replicas lag, networks split, and demand grows.
The core invariant for this design is: every accepted operation satisfies the consistency level requested by the caller, or returns an explicit failure. This case study turns a 10-billion-key workload into capacity, partitioning, replication, failover, repair, and operating decisions.
Define what the store promises before choosing a database
A key-value API is intentionally small, but each operation still needs precise semantics. The design cannot choose quorums, retries, or conflict handling until callers state whether they need the newest acknowledged value, a highly available answer, or a conditional update.
Functional scope
PUT(key, value, consistency)creates or replaces an opaque value and returns its version.GET(key, consistency)returns the value and version, or a clear not-found result.DELETE(key, consistency)writes a versioned tombstone so an old replica cannot resurrect deleted data.- Conditional writes compare an expected version before replacing a value; they do not provide multi-key transactions.
Non-functional constraints
- Data: 10 billion records, keys up to 256 bytes, values up to 10 KB, and a planning average near 5 KB.
- Traffic: 10 million reads/s and 1 million writes/s at average load, with a two-times peak envelope.
- Latency: p99 below 10 ms for reads and below 20 ms for writes inside the serving region.
- Availability: at least 99.9% while one storage node is unavailable, with an explicit behavior for a network partition.
- Operations: add nodes, rebalance partitions, replace failed replicas, and repair divergence without stopping the whole service.
Deliberate exclusions
- No range scans, joins, secondary indexes, or arbitrary queries in the first version.
- No atomic transaction across unrelated keys.
- No promise of globally ordered writes across regions.
Consistency and durability answer different questions. Consistency determines which value a read may return; durability determines whether an acknowledged value survives failures. Replication helps both, but only when acknowledgement and repair rules are explicit.