Walkthrough 5 — Design a Distributed Cache (Redis-style)

# Design a Distributed Cache (Redis-style) ## The brief Design a distributed in-memory cache supporting GET, SET, DELETE. Must scale horizontally to handle millions of ops/sec across many nodes. ## Step 1: Requirements - GET/SET/DELETE key-value. - TTL per key. - Scale: 100M keys, 1M QPS. - Latency: < 1ms per op. - High availability: tolerate node failures. - Eviction when memory full (LRU). ## Step 2: Single-node cache Before distributed, design single-node first: - Hash table for O(1) lookups. - Doubly-linked list for LRU order. - TTL: separate priority queue OR lazy expiration on GET. - Memory cap: when full, evict tail of LRU list. ```python class Cache: def __init__(self, capacity): self.capacity = capacity self.data = {} # key -> (value, expires_at, lru_node) self.lru = DoublyLinkedList() def get(self, key): if key not in self.data: return None value, expires_at, node = self.data[key] if expires_at and time.time() > expires_at: self._evict(key); return None self.lru.move_to_front(node) return value def set(self, key, value, ttl=None): if key in self.data: _, _, node = self.data[key] self.lru.remove(node) if len(self.data) >= self.capacity: self._evict_lru() expires_at = time.time() + ttl if ttl else None node = self.lru.add_to_front(key) self.data[key] = (value, expires_at, node) ``` This is essentially Memcached / Redis single-node. ## Step 3: Going distributed Single node has limits: memory, throughput, availability. Distribute by: ### Sharding (partitioning) - N nodes; each holds 1/N of keys. - Client (or proxy) computes `shard = hash(key) % N` and routes. Problem with naive modulo: adding/removing nodes shuffles ALL keys (cache invalidation storm). ### Consistent hashing - Place nodes on a hash ring (each node has multiple "virtual nodes" for balance). - Key → hash → nearest clockwise virtual node. - Adding/removing a node only affects keys near that node on the ring. ``` node1 / \ key_a node2 | | node3 - key_b \ / node4 ``` When node3 leaves, only its keys redistribute to neighbors. Minimal disruption. ## Step 4: Replication For high availability, each shard has replicas: - Primary + 2 replicas = 3-way replication. - Async replication (fast writes; eventual consistency). - On primary failure, promote a replica. Trade-off: async replication can lose recent writes; sync replication is slower but consistent. For cache (where freshness matters less than uptime): async is usually fine. ## Step 5: Client / Proxy Two options for routing: - **Smart client**: client knows the ring; computes shard locally; calls right node. (Memcached pattern.) - **Proxy**: client calls a proxy; proxy routes. (Twemproxy, Envoy, Redis Cluster has both.) Trade-offs: - Smart client: faster (no extra hop); harder to update ring info. - Proxy: simpler client; extra hop (~1ms); easier to deploy. Most production stacks use a proxy or library that abstracts this (Lettuce for Redis, etc.). ## Step 6: Coordination Who tracks node membership? - **Static config**: simple; ops-heavy when nodes added. - **Gossip protocol**: nodes share state with each other (Redis Cluster uses this). - **ZooKeeper / etcd**: centralized coordination; nodes watch for changes. Redis Cluster uses gossip; this is decentralized and resilient. ## Step 7: Operations to handle ### Reads - Client hashes key → routes to shard → calls primary (or replica for read scaling). - Replica reads: lower latency in some setups; risk of stale data. ### Writes - Client hashes key → routes to primary. - Primary acknowledges; async-replicates to replicas. ### Failover - Detect failure via heartbeat. - Promote replica to primary. - Update gossip / coordination layer. - New requests routed to new primary. ### Reshard (add/remove nodes) - Update ring (add/remove virtual nodes). - Migrate affected keys from old → new owners. - During migration: redirect to new owner; client retries. ## Step 8: Eviction policy Redis options: - `allkeys-lru`: evict LRU across all keys. - `volatile-lru`: evict LRU among keys with TTL. - `allkeys-lfu`: evict least-frequently-used. - `noeviction`: error when full (safer in some cases). LRU is the default; LFU better for workloads with stable hot keys. ## Step 9: TTL handling Two strategies: - **Lazy**: check on GET; expire if past. - **Active**: background thread scans samples; expires. Redis does both: lazy is fast; active prevents memory bloat from cold expired keys. ## Step 10: Persistence (optional for cache) If cache is purely volatile (rebuild from source on restart): no persistence needed. If used as primary store (Redis often is): persistence to disk: - **AOF (Append-Only File)**: log every write; replay on restart. Durable; slow recovery. - **RDB (snapshots)**: periodic