distributed key value store
Distributed Key-Value Stores are systems that partition a key-value dataset across multiple nodes, providing scalable storage and retrieval with tunable consistency, availability, and partition tolerance guarantees — forming the backbone of modern web services, caching layers, and distributed state management.
The fundamental challenge is distributing data across N nodes while supporting: fast lookups (O(1) per key), even load distribution, fault tolerance (node failures don't lose data), and dynamic scaling (adding/removing nodes without full redistribution).
Consistent Hashing: The core data distribution mechanism. Keys and nodes are mapped to positions on a hash ring (0 to 2^m-1). Each key is assigned to the first node clockwise from its position. When a node joins/leaves, only keys in adjacent ring segments are redistributed (O(K/N) keys instead of O(K)). Virtual nodes (each physical node maps to V positions on the ring) improve load balance from O(log N) variance to near-uniform distribution.
Replication Strategies:
| Strategy | Consistency | Availability | Use Case |
|---|---|---|---|
| Single copy | Strong (trivial) | Low | Cache only |
| Chain replication | Strong (linearizable) | Medium | Metadata stores |
| Quorum (W+R>N) | Tunable | Tunable | General purpose |
| Leaderless (Dynamo) | Eventual | High | Shopping carts, sessions |
| Raft/Paxos per shard | Strong | Medium-high | Coordination services |
Quorum Systems: With N replicas, write quorum W and read quorum R, if W+R>N then reads always see the latest write (strong consistency). Tuning W and R trades consistency for latency: W=1, R=N gives fastest writes; W=N, R=1 gives fastest reads; W=R=(N+1)/2 balances both.
Conflict Resolution: Under eventual consistency, concurrent writes to the same key create conflicts. Resolution approaches: last-writer-wins (LWW) using vector clocks or timestamps (simple but loses writes), application-level merge (client resolves conflicts using semantic knowledge), CRDTs (conflict-free replicated data types — data structures that mathematically guarantee convergence), and read-repair (detect stale replicas during reads and update them).
Production Systems:
| System | Consistency | Partitioning | Special Feature |
|---|---|---|---|
| Redis Cluster | Async replication | Hash slots (16384) | In-memory, sub-ms latency |
| DynamoDB | Tunable | Consistent hashing | Serverless, auto-scaling |
| Cassandra | Tunable quorum | Token ring | Wide-column, multi-DC |
| etcd | Strong (Raft) | None (small data) | Kubernetes coordination |
| TiKV | Strong (Raft) | Range-based | Distributed transactions |
Performance Considerations: Tail latency — P99 latency is critical for user-facing services; hedged requests (send to multiple replicas, use first response) reduce tail latency at cost of extra load. Hot keys — popular keys create load imbalance; mitigation via key splitting, local caching, or read replicas. Data locality — co-locating related keys on the same partition enables multi-key operations.
Distributed key-value stores embody the CAP theorem tradeoffs in practice — every design decision balances consistency, availability, and partition tolerance, making them both the simplest and most instructive examples of distributed systems engineering.