Design a Distributed Cache (Redis / Memcached Architecture)

A Distributed In-Memory Cache stores frequently accessed key-value data in DRAM across a cluster of servers to achieve sub-millisecond read/write latencies and offload heavy database read IOPS.

Functional Requirements

1. Core Operations: Support GET(key), SET(key, value, ttl), and DEL(key) with sub-millisecond execution.
2. Eviction Policies: Support configurable eviction strategies when memory is full: LRU (Least Recently Used), LFU (Least Frequently Used), and FIFO.
3. Configurable TTL: Automatic expiration of keys after a defined Time-To-Live.
4. Data Structures: Basic string blobs, binary data, and optional collections (lists, sets, hashes).

Non-Functional Requirements

• Sub-Millisecond Latency: p99 read and write latency < 1 ms.
• Horizontal Elastic Scalability: Add or remove cache servers dynamically with minimal key remapping (< 1/N keys remapped).
• High Availability & Durability: 99.99\% uptime with automated master-replica failover.
• Cache Miss Protection: Prevent stampedes, penetration, and avalanche failures.

To achieve strictly constant O(1) time complexity for both key lookups and memory evictions on a single server, combine two data structures in RAM:

1. Hash Map (std::unordered_map / Java HashMap):
   • Maps key ➔ Pointer to Node in Doubly Linked List.
   • Provides instant O(1) key lookup.
2. Doubly Linked List:
   • Stores the cached key-value payload and maintains access recency order.
   • Head: Most recently accessed item.
   • Tail: Least recently used item (first candidate for eviction).
   • Node removal and insertion at Head execute in O(1) pointer adjustments without shifting arrays.

typescript
Copy
class Node {
  key: string;
  val: any;
  prev: Node | null = null;
  next: Node | null = null;
  constructor(key: string, val: any) {
    this.key = key;
    this.val = val;
  }
}

class LRUCache {
  private capacity: number;
  private map: Map<string, Node> = new Map();
  private head: Node = new Node("", null);
  private tail: Node = new Node("", null);

  constructor(capacity: number) {
    this.capacity = capacity;
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: string): any {
    const node = this.map.get(key);
    if (!node) return null;
    this.moveToHead(node);
    return node.val;
  }

  set(key: string, val: any): void {
    if (this.map.has(key)) {
      const node = this.map.get(key)!;
      node.val = val;
      this.moveToHead(node);
    } else {
      if (this.map.size >= this.capacity) {
        const lru = this.tail.prev!;
        this.removeNode(lru);
        this.map.delete(lru.key);
      }
      const newNode = new Node(key, val);
      this.addNode(newNode);
      this.map.set(key, newNode);
    }
  }

  private addNode(node: Node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  private removeNode(node: Node) {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private moveToHead(node: Node) {
    this.removeNode(node);
    this.addNode(node);
  }
}

A single server cannot hold hundreds of gigabytes of cache data. Naive modulo hashing (hash(key) % N) causes catastrophic total cache invalidation when adding or removing a node, because almost 100\% of keys remap to different servers, triggering a database-crushing stampede.

The Consistent Hashing Ring Solution:

• Map both physical servers and cache keys onto a continuous 360^\circ hash ring (0 to 2^{32}-1).
• A key is routed to the first server encountered clockwise on the ring.
• Node Addition/Removal Impact: When a node is added or removed, only 1/N fraction of keys are remapped.

Virtual Nodes (vNodes):

• Placing only 3 physical nodes on a ring causes non-uniform distribution (hot spots).
• Assign 100 to 200 Virtual Nodes (vNodes) per physical machine scattered uniformly across the ring.
• Result: Statistical standard deviation of key distribution drops to < 3\%, ensuring balanced memory utilization across all cluster nodes.

Understanding the concurrency architecture of the caching engine is critical for sizing and CPU core allocation:

1. Redis Model (Single-Threaded Event Loop)

• Uses non-blocking I/O multiplexing (epoll / kqueue / io_uring) on a single core for command execution.
• Why it is fast: Eliminates thread context switching, race conditions, and mutex lock contention. RAM access is so fast (100 ns) that CPU is rarely the bottleneck.
• I/O Threads (Redis 6.0+): Offloads network socket reading and writing to background worker threads while keeping core command execution strictly single-threaded.

2. Memcached Model (Multi-Threaded with Mutex Locks)

• Spawns multiple worker threads sharing a single memory address space.
• Employs fine-grained thread locking (LRU locks and Hash Table bucket locks).
• Utilizes multiple CPU cores effectively on large multi-socket server machines.

In production distributed caches, three distinct failure patterns can take down backend databases:

1. Cache Stampede / Thundering Herd

• Problem: A high-traffic key (e.g., home page product catalog with 50,000 QPS) expires. Thousands of simultaneous requests experience a cache miss at the exact same millisecond and all hammer the database at once.
• Mitigation:
  • Probabilistic Early Expiration (XFetch Algorithm): Recompute the cache in the background before it expires if \Delta - \beta × \ln(rand()) > TTL.
  • Mutex Lock (Single-Flight): The first cache-miss thread acquires a distributed lock to query the DB; all other threads wait or return stale cache data.

2. Cache Penetration

• Problem: Attackers query keys that do not exist in either the cache or the database (e.g., GET /users/invalid_id_-999). Every request bypasses the cache and hits the database.
• Mitigation:
  • In-Memory Bloom Filter: Place a Bloom filter in front of the cache to drop invalid IDs immediately.
  • Null Value Caching: Cache empty results ("user:-999" -> NULL) with a short TTL (e.g., 60 seconds).

3. Cache Avalanche

• Problem: Millions of keys are written with the identical TTL (e.g., 1 hour) and all expire simultaneously, flooding the database.
• Mitigation: Add random jitter to TTLs: TTL = base_ttl + random_between(0, 300) seconds.

Master-Replica Pairs with Sentinel / Raft

• Each cache partition consists of a Primary Master and 1-2 Read Replicas.
• Writes hit the Primary; reads can be routed to replicas for increased read throughput.
• Replication is asynchronous for speed, with optional semi-synchronous replication for high durability.
• If the Primary crashes, a consensus quorum (Redis Sentinel or Raft-based Redis Cluster) automatically promotes a replica to Primary in < 3 seconds.