Distributed Key Value Store
Distributed Key-Value Stores are systems that partition key-value data across multiple nodes using consistent hashing or range partitioning — providing horizontal scalability, fault tolerance through replication, and low-latency access (< 1ms) for billions of key-value pairs that cannot fit on a single machine, forming the backbone of caching layers, session stores, and real-time feature serving.
Core Architecture
1. Partitioning: Key space divided across N nodes so each node holds 1/N of the data.
2. Replication: Each partition replicated to R nodes for fault tolerance (typically R=3).
3. Routing: Client or proxy determines which node holds a given key.
4. Consistency: Configurable from eventual to strong consistency.
Consistent Hashing
- Nodes placed on a virtual ring (hash space 0 to 2³² - 1).
- Key hashed → walk clockwise on ring → first node encountered is the owner.
- Adding a node: Only keys in the new node's range are rehashed (1/N of total).
- Removing a node: Only that node's keys are redistributed.
- Virtual nodes: Each physical node gets V virtual positions on ring → better load balance.
Popular Systems
| System | Consistency | Use Case | Latency |
|---|---|---|---|
| Redis Cluster | Eventual (async replication) | Cache, session, real-time | < 0.5 ms |
| Memcached | None (cache only) | Pure cache layer | < 0.3 ms |
| Amazon DynamoDB | Eventual or Strong | Serverless NoSQL | < 5 ms |
| Apache Cassandra | Tunable (quorum) | Time-series, IoT, logs | 1-10 ms |
| etcd | Strong (Raft) | Config/service discovery | 1-10 ms |
| TiKV | Strong (Raft) | Distributed transactional | 1-5 ms |
CAP Theorem Tradeoff
- C (Consistency): All nodes see same data at same time.
- A (Availability): Every request gets a response.
- P (Partition tolerance): System works despite network partitions.
- Must choose 2 of 3: Redis chooses AP, etcd chooses CP.
Replication Strategies
- Leader-follower: Writes go to leader, replicated to followers.
- Leaderless (quorum): Write to W nodes, read from R nodes, W + R > N ensures freshness.
- Chain replication: Write propagates through chain of nodes — strong consistency with high throughput.
Performance Optimization
- Connection pooling: Reuse TCP connections to nodes.
- Pipelining: Send multiple requests without waiting for responses.
- Client-side caching: Cache frequently accessed keys locally.
- Hot key handling: Replicate hot keys to more nodes or use local caching.
Distributed key-value stores are the fundamental building block of scalable systems — from caching database query results to serving ML feature vectors in real time, they provide the low-latency, high-throughput data access layer that enables applications to serve millions of concurrent users.