Design a Key-Value Store

Consistent hashing maps both keys and nodes to positions on a virtual ring. Each key is assigned to the nearest node clockwise on the ring. When a node is added or removed, only keys in its range need to be remapped — unlike simple hash partitioning where nearly all keys must move. This minimizes disruption during cluster scaling.

Replicate each key to N nodes (e.g., 3). Use a quorum-based protocol: writes succeed if W of N replicas acknowledge, reads succeed if R of N respond, where W + R > N ensures consistency. Failed nodes are detected via heartbeats and replaced via hinted handoff or anti-entropy repair.

It depends on the use case. Strong consistency (linearizability) is easiest to reason about but adds latency. Eventual consistency offers better availability and performance but requires conflict resolution. Many systems offer tunable consistency — letting clients choose per-request based on their needs (e.g., Cassandra’s consistency levels).

Hot keys (keys accessed far more than others) can overload a single partition. Solutions include read replicas for hot keys, client-side caching, key splitting (appending a random suffix to spread load across partitions), and dedicated caching layers. Monitoring access patterns helps detect hot keys early.