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.**