System Design Problems
Design a Key-Value Store
A distributed key-value store provides a simple interface: put(key, value) and get(key). Systems like Redis, DynamoDB, and Memcached form the backbone of modern applications, enabling sub-millisecond data access at massive scale.
- Simple Interface β
put(key, value)andget(key)operations - Horizontal Scalability β Distribute data across thousands of nodes
- Tunable Consistency β Choose between strong and eventual consistency per operation
The elegance of a key-value store lies in its simplicityβbut achieving distributed consistency, availability, and performance requires sophisticated engineering.
Requirements
Functional Requirements
put(key, value): Insert or update a key-value pairget(key): Retrieve the value for a given keydelete(key): Remove a key-value pair- Support for different value types (strings, lists, sets, hashes)
- TTL (Time-to-Live) support for key expiration
Non-Functional Requirements
- Latency: Read/write in < 1ms (p99)
- Availability: 99.99% uptime
- Scalability: Billions of keys, millions of QPS
- Durability: Data must survive node failures
- Consistency: Tunable (strong or eventual)
Back-of-the-Envelope Estimation
Core Design Concepts
Data Partitioning
Replication
For durability and availability, each key is replicated across multiple nodes:
Conflict Resolution
When concurrent writes reach different replicas, conflicts arise:
| Strategy | Description | Use Case |
|---|---|---|
| Last-Write-Wins (LWW) | Timestamp determines winner | Simple, low storage |
| Vector Clocks | Track causal ordering | Complex, precise |
| CRDTs | Conflict-free data types | Counter, set operations |
| Application-level | Merge in application code | Custom logic needed |
Storage Engine
Each node uses a local storage engine:
Gossip Protocol
For cluster membership and failure detection, use a gossip protocol:
Practice Exercises
-
Design: How would you implement TTL-based key expiration? Compare lazy expiration vs active expiration approaches.
-
Trade-offs: Under what conditions would you choose W=1, R=1 (AP) over W=2, R=2 (CP) for a distributed KV store?
-
Scale: If the KV store needs to handle 10 million keys with 99.9% cache hit ratio, estimate the memory needed assuming 1 KB average value.
-
Consistency: Explain how vector clocks detect conflicts in a distributed KV store. What happens when two concurrent writes occur on different replicas?
What to Learn Next
-> Consistent Hashing Deep dive into hash rings, virtual nodes, and load distribution.
-> Databases SQL vs NoSQL, indexing strategies, and storage engines.
-> CAP Theorem Consistency, availability, and partition tolerance trade-offs.
-> Caching Strategies Cache-aside, write-through, and distributed caching patterns.
-> Data Replication Single-leader, multi-leader, and leaderless replication.
-> Design Distributed Cache Building Redis/Memcached at scale with consistent hashing.