Design a Distributed Cache (Redis / Memcached Cluster)

Distributed in-memory caches sit in front of primary databases to slash read latencies from milliseconds to microseconds and absorb massive traffic spikes.

1. Core Design Goals

1. Microsecond Latency: Read and write operations complete in $< 1\text{ms}$.
2. Horizontal Scalability: Add or remove cache nodes dynamically with minimal key movement via Consistent Hashing.
3. High Availability: Master-replica node pairs with automated failover via Raft or Gossip consensus.
4. Smart Eviction: Bound memory usage using Least Recently Used (LRU) or Least Frequently Used (LFU) algorithms.

2. Key Architecture Elements

Consistent Hashing Ring

• Keys and cache nodes are mapped onto a 32-bit or 64-bit integer hash ring.
• Keys are assigned to the first node encountered clockwise.
• Virtual Nodes: Each physical server is assigned 100–250 virtual points on the ring to prevent unbalanced "hot spots" and guarantee uniform key distribution.

Mitigating Cache Stampede (Thundering Herd)

When a hot key expires, thousands of concurrent requests miss the cache simultaneously, threatening to take down the underlying database.

• Probabilistic Early Expiration (XFetch):

$$\Delta - \beta \times \ln(\text{rand}()) > \text{TTL}$$ Clients randomly refresh the cache in the background slightly before official expiration.

• Mutex Locking: Only the first worker to miss the cache acquires a distributed lock to recompute the database value; all other threads sleep briefly and read the refreshed cache.

Key Architecture Trade-Offs & Decision Matrix