Design a Distributed Key-Value Store
Design a distributed, highly available key-value store similar to DynamoDB or Cassandra. The system must support put(key, value) and get(key) across multiple storage nodes with configurable consistency, automatic data partitioning, and failure recovery.
Requirements
- ✓put(key, value): store or update key-value pair.
- ✓get(key): retrieve value associated with key.
- ✓High availability and fault tolerance: survive node failures without data loss.
- ✓Horizontal scalability: scale storage and throughput by adding nodes.
- ✓Tunable consistency: support configurable R (read quorum) and W (write quorum).
Constraints & Scale
- —Key size: up to 256 bytes; value size: up to 1 MB.
- —Low latency: p99 read and write under 10 ms within same datacenter.
- —Handle network partitions (CAP theorem AP system with eventual consistency).
Understand
Guided mode
What makes a distributed KV store fundamentally different from a single Redis instance? How do consistent hashing, replication, and quorum consistency work together?
Context & Constraints — Human Reviewed
Distributed KV stores partition data across nodes using Consistent Hashing, replicate each key across N nodes, and use quorum voting (R + W > N) for strong consistency or eventual consistency.
Trade-offs
- ⚖Consistent Hashing vs Range Partitioning: Consistent hashing distributes write load evenly without hotspots; range partitioning enables efficient range scans but causes write hotspots on sequential keys.
- ⚖Sloppy Quorum + Hinted Handoff vs Strict Quorum: Sloppy quorum maintains write availability during network partition, but risks stale reads until hinted handoff reconciles.
Concepts used in this stage