System Design Problems
Design a Distributed Cache
A distributed cache stores frequently accessed data in memory across a cluster of servers, providing sub-millisecond read latency. Redis Cluster and Memcached are the most widely used distributed caches, forming the performance backbone of nearly every large-scale system.
- Sub-millisecond Latency â Memory-based storage with no disk I/O
- Horizontal Scalability â Distribute data across thousands of nodes
- High Availability â Replication and automatic failover
The fundamental trade-off in caching is between cache hit ratio (accuracy) and memory cost. A 99% cache hit ratio means 99% of requests never touch the database.
Requirements
Functional Requirements
put(key, value, ttl): Store key-value pair with optional TTLget(key): Retrieve value by keydelete(key): Remove key from cache- Support for different data types (strings, hashes, lists, sets)
- Cache eviction policies (LRU, LFU, TTL-based)
- Cluster mode with automatic data distribution
Non-Functional Requirements
- Latency: Read/write in < 1ms (p99)
- Throughput: 1M operations/second per node
- Availability: 99.99% (cache failure should not crash the system)
- Scalability: 100 TB total cache size across cluster
- Durability: Optional persistence (RDB/AOF for Redis)
Back-of-the-Envelope Estimation
Data Distribution
Consistent Hashing
Replication
Cache Architecture
Redis Cluster Slot Management
Eviction Policies
When memory is full, evict keys based on policy:
| Policy | Description | Use Case |
|---|---|---|
| LRU | Evict least recently used | General purpose |
| LFU | Evict least frequently used | Access pattern varies |
| TTL | Evict expired keys | Time-sensitive data |
| Random | Evict random keys | Simple, no tracking |
| No-eviction | Return error when full | Critical data only |
Cache Patterns
Practice Exercises
-
Design: How would you handle cache stampede (thundering herd) when a popular key expires? Design a mechanism to prevent all requests from hitting the database simultaneously.
-
Scale: If the cluster has 100 nodes and 100 TB of data, estimate the memory overhead for consistent hashing metadata and replication information.
-
Consistency: Design a cache invalidation strategy that ensures eventual consistency between the cache and database. What happens during network partitions?
-
Recovery: When a failed node recovers, how do you synchronize its data with the current cluster state? Compare Merkle tree anti-entropy vs. full sync.
What to Learn Next
-> Caching Strategies Cache-aside, write-through, and cache invalidation.
-> Consistent Hashing Deep dive into hash rings and virtual nodes.
-> Design Key-Value Store Distributed KV store with replication and consistency.
-> Data Replication Leader-follower replication and conflict resolution.
-> Load Balancing Distributing cache requests across cluster nodes.
-> Databases Cache invalidation strategies for database-backed caches.