Design a distributed in-memory key-value cache similar to Redis or Memcached. The cache must support GET, SET, and DELETE with TTL. It should scale horizontally and handle node failures gracefully.
Client
│
├── Cache Client Library (consistent hashing router)
│ │
│ Consistent hash ring → selects cache node for each key
│
├── Cache Node 1 [10 GB in-memory HashMap + LRU]
├── Cache Node 2
├── Cache Node 3
└── Cache Node N
[Coordination Service (ZooKeeper / etcd)]
→ tracks live nodes
→ notifies clients of topology changes
Consistent Hashing: keys are mapped to a virtual ring. Each node owns a range of the ring. Adding/removing a node only remaps keys from the adjacent node — not the entire keyspace.
// Client SDK (not HTTP — internal TCP binary protocol)
cache.get("user:123") → String | null
cache.set("user:123", json, 3600) → OK
cache.delete("user:123") → OK
cache.mget(["k1", "k2", "k3"]) → Map<String, String>
Why not HTTP? HTTP overhead (~200 bytes per request) is significant at 1M QPS. Redis uses a custom binary protocol (RESP) over raw TCP — ~4× lower latency.
HashMap (O(1) GET/SET/DELETE):
HashMap<String, CacheEntry> store;
class CacheEntry {
byte[] value;
long expiresAt; // epoch millis, -1 = no TTL
LRUNode lruNode; // pointer into doubly-linked LRU list
}
LRU via Doubly Linked List + HashMap:
TTL expiration — two strategies:
Each primary cache node has 1 replica:
Primary Node → (async) → Replica Node
On primary failure: replica promoted. Client updated via ZooKeeper watch.