Design: Distributed Cache

Client → [Cache Cluster Proxy / Router]
            ↓ consistent hashing
  [Shard 0] [Shard 1] [Shard 2] ... [Shard N]
  (Leader + Follower)

// Route key to the correct shard
String shard = consistentHash.getNode(key);
redisClient(shard).get(key);

class LRUCache {
    private final int capacity;
    private final Map<String, Node> map = new HashMap<>();
    private final DoublyLinkedList list = new DoublyLinkedList();

    public String get(String key) {
        if (!map.containsKey(key)) return null;
        Node node = map.get(key);
        list.moveToFront(node); // recently used
        return node.value;
    }

    public void put(String key, String value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            list.moveToFront(node);
        } else {
            if (map.size() == capacity) {
                Node evicted = list.removeLast(); // evict LRU
                map.remove(evicted.key);
            }
            Node node = new Node(key, value);
            list.addToFront(node);
            map.put(key, node);
        }
    }
}

Each shard has a Leader + 1-2 Followers:
  Writes → Leader only
  Reads → Leader or Follower (consistency vs latency tradeoff)

On Leader failure:
  1. Sentinel/ZooKeeper detects via heartbeat
  2. Promotes Follower to Leader
  3. Clients re-route to new Leader

Lazy expiration: check TTL on access, delete if expired
Active expiration: background thread scans and deletes expired keys periodically

Redis approach: lazy + active (scan 20 random keys/sec per DB)

Gossip Protocol: nodes exchange cluster state periodically
→ Eventually consistent view of which nodes are alive
→ No central coordinator needed

Redis Cluster: 16384 hash slots, gossip protocol