Requirements
- Store and retrieve values by key across many nodes.
- Survive node failures without data loss.
- Scale horizontally as data and traffic grow.
High level design
Keys are spread across nodes by consistent hashing, and each key is replicated to several nodes.
- Partitioning: consistent hashing places keys on a ring so adding or removing a node moves only a small slice of keys.
- Replication: each key is stored on the next few nodes clockwise, giving redundancy.
- Consistency: quorum reads and writes let you tune how many replicas must respond.
Bottlenecks
- Rebalancing: naive hashing reshuffles everything on resize, so consistent hashing with virtual nodes keeps movement small and balanced.
- Conflicts: concurrent writes to replicas diverge, so use version vectors and resolve on read.
- Tail latency: a slow replica drags quorum reads, so send to extra replicas and take the fastest responses.
A write coordinator returns success once enough replicas acknowledge, and read repair fixes stale copies in the background.
Key idea
A distributed key value store leans on consistent hashing for partitioning and quorum replication for durability, tuning consistency against latency.