Key-Value Store
AdvancedOverview
A distributed key-value store (like DynamoDB, Cassandra, or Riak) provides a simple data model—storing and retrieving a blob of data by a unique key—across a cluster of machines. It prioritizes high availability, scalability, and partition tolerance over strict ACID transactions, making it foundational for modern web-scale infrastructure.
Functional Requirements
- Put(key, value): Insert or update a value associated with a key.
- Get(key): Retrieve the value associated with a key.
- The system should support configurable consistency levels (e.g., ONE, QUORUM, ALL).
Non-Functional Requirements
- High availability: The system must continue to function even if some nodes fail.
- High scalability: Adding or removing nodes must be seamless and not cause significant downtime or massive data movement.
- Low latency: Reads and writes should be in the single-digit milliseconds.
- Fault tolerance: The system must detect failures and automatically recover or reroute requests.
Capacity Estimation
Assume the system needs to store 10 billion key-value pairs and handle 100,000 QPS (reads and writes combined).
- Storage: Average key size = 100 bytes, average value size = 10 KB.
- Data per pair = ~10 KB.
- Total raw storage: 10 billion x 10 KB = 100 TB.
- With a replication factor of 3, total storage needed = 300 TB.
- Bandwidth:
- Assuming an even split (50k writes, 50k reads).
- Write ingress: 50,000 * 10 KB ~ 500 MB/s.
- Read egress: 50,000 * 10 KB ~ 500 MB/s.
This volume requires a partitioned, multi-node architecture, as no single machine can hold 300 TB or sustain 1 GB/s of constant throughput efficiently.
High-Level Architecture
The architecture relies on a decentralized, peer-to-peer design. Clients connect to any node (the Coordinator) which hashes the key to determine its position on a Hash Ring using Consistent Hashing. The Coordinator routes the request to the primary node and its replicas. Background processes like Hinted Handoff and Anti-Entropy (using Merkle Trees) ensure eventual consistency and fault tolerance without slowing down the hot path.
Data Model
| Entity | Fields / Schema | Storage Choice |
|---|---|---|
| kv_pair | key (PK), value, version_vector, timestamp | LSM-Tree based storage engine (like RocksDB or SSTables) on local node disks |
Detailed Design
Data Partitioning: Consistent Hashing
To distribute 300 TB of data across many servers, we use Consistent Hashing. The hash space is treated as a ring. Each node is assigned multiple positions on the ring using Virtual Nodes (VNodes). When a key is hashed, the system walks clockwise on the ring to find the first VNode, which dictates the primary physical node for that data. VNodes ensure that when a physical machine is added or removed, the data redistribution is balanced across all remaining nodes, preventing hot spots.
Data Replication
To ensure high availability, data is replicated to N nodes (e.g., N=3). The coordinator node walks the hash ring clockwise from the key's position and selects the first N distinct physical nodes to store the replicas.
Consistency and Quorum
The system uses a Quorum consensus protocol to balance latency and consistency. Let N be the replication factor, W be the write quorum, and R be the read quorum.
- For a write to be successful, it must be acknowledged by at least W nodes.
- For a read to be successful, it must receive responses from at least R nodes.
- If W + R > N, we guarantee strong consistency (a read will always see the latest write). Often, systems are configured with N=3, W=2, R=2.
Handling Temporary Failures: Hinted Handoff
If a replica node is temporarily down during a write, the coordinator writes the data to a healthy node with a "hint" indicating the true destination. When the downed node comes back online, the healthy node forwards the hinted data to it. This keeps writes highly available even during partial outages.
Handling Permanent Failures: Anti-Entropy
For long-term desynchronization or missed hinted handoffs, nodes use an anti-entropy protocol running in the background. They exchange Merkle Trees (hash trees) of their data ranges. Merkle trees allow nodes to quickly determine exactly which keys differ without transferring the actual data, minimizing network overhead during repair.
Bottlenecks & Solutions
Concurrent updates to the same key can cause version conflicts. Since the system is highly distributed, relying on wall-clock timestamps for conflict resolution (Last-Write-Wins) can lead to data loss due to clock skew. Instead, the system uses Vector Clocks (or Version Vectors) to track causality. If two updates are concurrent and cannot be automatically merged, the system keeps both versions (siblings) and returns them to the client on the next read, forcing the client to resolve the conflict.