Design a Distributed Cache (Redis)

1Requirements

2Back-of-envelope estimation

3API design

4High-level design

Clients embed a smart library that owns routing: it hashes each key onto a consistent hash ring and talks directly to the owning node, so there is no central proxy to bottleneck. Each physical node is placed on the ring 100 to 200 times as virtual nodes, which smooths out load imbalance from an uneven hash distribution and lets heterogeneous machines take proportional shares.

Each node is a single-threaded (or sharded-per-core) event loop over an in-memory hash map, paired with a doubly linked list for LRU ordering. Every GET moves the entry to the head; when memory passes the cap, the tail is evicted. TTLs are enforced lazily on read plus a background sampler that scans a few random keys per tick, which is how Redis actually does it.

The dominant usage pattern is cache-aside: the application reads the cache, falls back to the database on a miss, then populates the cache with a TTL. Writes go to the database first and then delete (not update) the cache key, because delete-on-write avoids races where an older value overwrites a newer one. TTLs act as the safety net for any missed invalidation.

For availability, each shard gets an async replica. On primary failure, a sentinel process (or the cluster's gossip protocol) promotes the replica and clients refresh the ring. Because replication is async, a promoted replica may serve slightly stale data, which is acceptable for a cache where the database is the source of truth.

Two failure amplifiers get dedicated treatment: cache stampedes (thousands of concurrent misses on the same expired key all hitting the database) are handled with per-key mutex locks or probabilistic early refresh; hot keys (one celebrity key exceeding a single node's capacity) are handled with client-local caching and key duplication across nodes.

5Data model

6Deep dives

7Rapid implementation: build the MVP

Theory is table stakes. Here is how you would stand up a working version fast, on a budget, with the core algorithm in real code.

1. 01Build the LRU store class: Map for O(1) lookup, doubly linked list for recency order, maxBytes cap with tail eviction.
2. 02Wrap it in a tiny TCP or HTTP server exposing GET, SET with TTL, and DELETE; run two instances on ports 7001 and 7002.
3. 03Write the client library: build a ring of 128 virtual nodes per server using sha1(node + '#' + i), route each key with binary search over sorted ring points.
4. 04Implement cache-aside in a demo API route: check cache, on miss query Postgres, SET with a 300 second TTL plus 10% random jitter.
5. 05Add stampede protection: a per-key in-flight promise map in the client so concurrent misses for the same key share one database query.
6. 06Kill one cache process while load testing and verify requests fall through to Postgres and the ring reroutes after the config refresh.
7. 07Add a /stats endpoint per node (hits, misses, evictions) and confirm the hit ratio exceeds 90% under a zipfian load test.

interface Node { key: string; val: Buffer; expiresAt: number; prev: Node | null; next: Node | null; }

export class LRU {
  private map = new Map<string, Node>();
  private head: Node | null = null; // most recent
  private tail: Node | null = null; // least recent
  private used = 0;
  constructor(private maxBytes: number) {}

  get(key: string): Buffer | undefined {
    const n = this.map.get(key);
    if (!n) return undefined;
    if (n.expiresAt < Date.now()) { this.remove(n); return undefined; }
    this.remove(n); this.pushFront(n); // refresh recency
    return n.val;
  }
  set(key: string, val: Buffer, ttlMs: number) {
    const old = this.map.get(key);
    if (old) this.remove(old);
    const n: Node = { key, val, expiresAt: Date.now() + ttlMs, prev: null, next: null };
    this.pushFront(n);
    this.used += val.length + key.length;
    while (this.used > this.maxBytes && this.tail) this.remove(this.tail); // evict LRU
  }
  private pushFront(n: Node) {
    this.map.set(n.key, n);
    n.next = this.head; n.prev = null;
    if (this.head) this.head.prev = n;
    this.head = n;
    if (!this.tail) this.tail = n;
  }
  private remove(n: Node) {
    this.map.delete(n.key);
    this.used -= n.val.length + n.key.length;
    if (n.prev) n.prev.next = n.next; else this.head = n.next;
    if (n.next) n.next.prev = n.prev; else this.tail = n.prev;
  }
}

import { createHash } from "crypto";

function hash32(s: string): number {
  return createHash("sha1").update(s).digest().readUInt32BE(0);
}

export class Ring {
  private points: { h: number; node: string }[] = [];
  constructor(nodes: string[], vnodes = 128) {
    for (const node of nodes)
      for (let i = 0; i < vnodes; i++)
        this.points.push({ h: hash32(node + "#" + i), node });
    this.points.sort((a, b) => a.h - b.h);
  }
  lookup(key: string): string {
    const h = hash32(key);
    let lo = 0, hi = this.points.length - 1;
    while (lo < hi) { // first point with h >= key hash
      const mid = (lo + hi) >> 1;
      if (this.points[mid].h < h) lo = mid + 1; else hi = mid;
    }
    return this.points[this.points[lo].h >= h ? lo : 0].node; // wrap around
  }
}

const inflight = new Map<string, Promise<Buffer>>();

export async function getOrLoad(
  key: string,
  cacheGet: (k: string) => Promise<Buffer | undefined>,
  cacheSet: (k: string, v: Buffer, ttlMs: number) => Promise<void>,
  loadFromDb: (k: string) => Promise<Buffer>
): Promise<Buffer> {
  const hit = await cacheGet(key);
  if (hit) return hit;
  const pending = inflight.get(key);
  if (pending) return pending; // piggyback on the miss already in flight
  const p = (async () => {
    try {
      const val = await loadFromDb(key);
      const jitter = 1 + Math.random() * 0.1; // avoid synchronized expiry
      await cacheSet(key, val, Math.floor(300_000 * jitter));
      return val;
    } finally {
      inflight.delete(key);
    }
  })();
  inflight.set(key, p);
  return p;
}