Caching

The browser can't be purged. Once a response is stored with Cache-Control: max-age=31536000, nothing you do on the server removes it from a user's disk before then. That's why static assets get a content hash in the file name (app.3f9a1c.js): a new version is a new URL, so the old copy simply stops being asked for. immutable (RFC 8246) tells the browser not even to revalidate such a file on reload. HTML, which must change when you deploy, gets a short max-age or no-cache (store it, but revalidate every time).

A shared cache must not see personal data. The CDN and gateway answer everyone who sends the same cache key. A response that depends on the cookie but is cached without the cookie in its key is served to the next visitor. Mark per-user responses Cache-Control: private (MDN: shared caches must not store it) and keep the public part of the page separate from the personal part.

The CDN only knows the request. Its cache key is the URL plus whatever headers or cookies you add to it, so every extra dimension multiplies the number of copies: varying on Accept-Language with 40 languages turns one cached page into 40, each with 1/40th of the traffic and so a far lower hit ratio. Normalise keys at the edge (drop utm_* tracking parameters, sort query parameters, collapse languages to the ones you actually serve) so equivalent requests share one copy.

An in-process cache multiplies by the number of servers. Fifty app servers mean fifty copies of every L1 entry, fifty misses to warm it, and fifty places to invalidate. Keep L1 for small, very hot, slow-changing things (feature flags, configuration, the hottest keys during a spike) with a TTL of seconds, and let the shared cache hold everything else.

The database cache isn't yours to tune key by key, but it explains a familiar effect: right after a restart the database is slow because its buffer pool is cold, which is the same warm-up problem as an empty Redis (see Distributed caches).

How long a CDN keeps an object is mostly up to your headers. On CloudFront, for example, s-maxage (or max-age) sets the edge TTL within the cache policy's minimum and maximum, and with no cache policy and no header the default TTL is 24 hours (AWS CloudFront docs, checked October 2026). CloudFront also honours stale-while-revalidate and stale-if-error (RFC 5861), which let the edge keep serving an expired copy while it refetches, or while the origin is down. Those two directives are the edge's built-in answer to the stampede and outage problems in Hot keys and cache stampedes.

A miss for something that doesn't exist goes to the database every time, because there's nothing to cache. A bot requesting random product IDs turns your cache into a pass-through. The fix is negative caching: store a small "not found" marker with a short TTL (say 30–60 seconds), so repeated lookups for the same missing ID stop at the cache. Keep the TTL short so a newly created item appears quickly, and delete the marker when the item is created. For huge ID spaces, a Bloom filter of existing IDs in front of the cache rejects most nonexistent IDs without storing a marker per ID.

Errors are different: don't cache a 500 as if it were the answer, or a one-second blip becomes a minute-long outage. Do the opposite: keep serving the last good copy while the origin is failing (stale-if-error at the edge, or a "serve stale on error" path in the app), so a downstream failure degrades freshness instead of availability.

Writes are where the patterns really differ. The next model runs a mixed workload against a cache too small to hold everything: 1,000 keys with Zipf popularity, an LRU cache of 300 entries, one operation per millisecond for 10 seconds, 80% reads and 20% writes. A database write costs 10 ms and a cache operation 1 ms. Write-behind flushes its dirty keys once a second (and flushes a dirty key early if LRU is about to evict it), and the model records how many unflushed writes a cache crash at 9.5 s would lose.

function mulberry32(a) {                                   // seeded PRNG: same numbers every run
  return () => {
    a |= 0; a = (a + 0x6d2b79f5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
const KEYS = 1000, CAPACITY = 300, DB_MS = 10, CACHE_MS = 1, FLUSH_EVERY = 1000;
const w = Array.from({ length: KEYS }, (_, i) => 1 / (i + 1));
const total = w.reduce((a, b) => a + b);
const pick = (r) => { let x = r() * total; for (let i = 0; i < KEYS; i++) if ((x -= w[i]) <= 0) return i; return KEYS - 1; };

function run(strategy) {
  const rand = mulberry32(7);
  const cache = new Map();                                 // insertion order = LRU order
  const dirty = new Set();                                 // write-behind: written to cache, not yet to the DB
  let dbWrites = 0, misses = 0, reads = 0, writeMs = 0, writes = 0, lostAtCrash = 0;
  const put = (k, v) => {
    cache.delete(k); cache.set(k, v);
    if (cache.size <= CAPACITY) return;
    const victim = cache.keys().next().value;              // least recently used
    cache.delete(victim);
    if (dirty.delete(victim)) dbWrites++;                  // write-behind must flush a dirty victim first
  };
  for (let now = 1; now <= 10_000; now++) {                // 10 s, one operation per ms
    const key = pick(rand);
    if (rand() < 0.8) {                                    // 80% reads
      reads++;
      if (cache.has(key)) put(key, cache.get(key));
      else { misses++; put(key, "row"); }                  // miss: load the row from the DB
    } else {
      writes++;
      if (strategy === "cache-aside") { dbWrites++; cache.delete(key); writeMs += DB_MS + CACHE_MS; }
      if (strategy === "write-through") { dbWrites++; put(key, "new"); writeMs += DB_MS + CACHE_MS; }
      if (strategy === "write-behind") { put(key, "new"); dirty.add(key); writeMs += CACHE_MS; }
    }
    if (strategy === "write-behind") {
      if (now === 9_500) lostAtCrash = dirty.size;         // what a crash at 9.5 s would lose
      if (now % FLUSH_EVERY === 0) { dbWrites += dirty.size; dirty.clear(); }  // one DB write per dirty key
    }
  }
  return `${strategy.padEnd(13)} writes ${writes}  db writes ${String(dbWrites).padStart(4)}  ` +
    `avg write ${(writeMs / writes).toFixed(1).padStart(4)} ms  read miss ${((misses / reads) * 100).toFixed(1)}%  ` +
    `lost if cache dies at 9.5 s: ${lostAtCrash}`;
}
for (const s of ["cache-aside", "write-through", "write-behind"]) console.log(run(s));

cache-aside   writes 1917  db writes 1917  avg write 11.0 ms  read miss 34.9%  lost if cache dies at 9.5 s: 0
write-through writes 1917  db writes 1917  avg write 11.0 ms  read miss 23.3%  lost if cache dies at 9.5 s: 0
write-behind  writes 1917  db writes 1052  avg write  1.0 ms  read miss 23.3%  lost if cache dies at 9.5 s: 64

Choosing in the interview

Start from the default: cache-aside with delete-on-write and a TTL. It's simple, the cache can be lost at any moment without losing data (it only holds copies), and the TTL bounds how wrong a copy can be. Then change it only for a reason you can name:

• The same user reads right after writing (edit profile, then the profile page reloads): write-through for those keys, or keep the delete and accept one miss. Both are fine; say which and why.
• Writes are far more frequent than reads and individually unimportant (view counts, likes, "last seen" timestamps, game scores): write-behind. Increment in Redis, flush aggregated deltas to the database every few seconds. Losing a few seconds of view counts in a crash is acceptable; losing a payment is not.
• A few keys are hot and expensive to compute (the home page's "trending" list, a leaderboard top 100): refresh-ahead from a scheduled job or on access, so the expensive recompute never happens on a user's request.
• Many services share the same loading logic: put it behind a read-through layer (a small cache service or a library with a loader) so coalescing, TTLs and metrics live in one place.

Which policy suits which workload, in the terms you'd use in a design discussion:

Production caches approximate these policies to save memory and CPU, and the details come up in interviews.

Redis samples instead of keeping a list. Its allkeys-lru doesn't maintain a linked list of every key. It picks a few keys at random (maxmemory-samples, default 5), evicts the oldest of the sample, and since Redis 3.0 keeps a small pool of good candidates; the docs say 10 samples is very close to true LRU. Its LFU (Redis 4.0+) uses a Morris counter, a probabilistic logarithmic counter that fits in 8 bits, with two knobs: lfu-log-factor (default 10: about a million hits saturate the counter) and lfu-decay-time (default 1: the counter is reduced every minute a key isn't touched). That decay is the same idea as LFU+decay in the model. (Redis eviction docs, checked October 2026.)

Redis's policy list in 2026 is noeviction (refuse writes when full), allkeys-lru, allkeys-lfu, allkeys-random, the volatile-* versions that only consider keys with a TTL, volatile-ttl (shortest remaining TTL first), and, new in Redis 8.6, allkeys-lrm and volatile-lrm (least recently modified: reads don't refresh the timestamp, only writes do). The docs' rule of thumb is allkeys-lru as the default when a subset of keys is much hotter than the rest.

Caffeine (the Java cache library) uses Window TinyLFU: new entries go into a small LRU "window" where they can prove themselves, and only enter the main segmented-LRU area if a compact frequency sketch (a 4-bit count-min sketch, about 8 bytes per entry) says they're used more often than the entry they'd replace. The window/main split adapts by hill climbing. Its wiki reports near-optimal hit rates on traces from Wikipedia, search and databases, competitive with ARC and LIRS. The idea to take into an interview: admission (should this new key get in at all?) matters as much as eviction (who leaves?), and it's what makes a cache scan-resistant.

Size matters, not just count. The model counts entries, but real caches are bounded in bytes, and one 900 KB value costs as much as nine thousand 100-byte values. Size-aware policies weigh the benefit of keeping an entry by its size. Memcached also caps item size: 1 MB by default, adjustable with -I up to 1 GB (memcached man page, 2026). Keep cached values small and split large ones.

A TTL should come from a staleness budget: how long can this copy be wrong before a user or the business notices? A product description can be wrong for an hour; a price for a minute; stock levels on a product page for 30 seconds, but never during checkout, which reads the database. Write that number down per key type in the design rather than using one global TTL.

Three rules of thumb:

• Short TTLs cost load, long TTLs cost staleness. Each halving of the TTL roughly doubles the reloads of hot keys. The next topic measures the trade.
• Use the TTL as the safety net, not the mechanism. If correctness matters, delete on write and keep the TTL as the bound for when an invalidation is lost.
• Add jitter. Keys written together (after a deploy or a cache restart) expire together. A random ±10% on each TTL spreads their reloads; Hot keys and cache stampedes measures the difference.

The textbook write is "update the database, then delete the key". It has one well-known race, which the Node.js and Databases courses reproduce against real Redis and MySQL. In outline:

1. Reader A misses the cache and reads the row (price 100) from the database.
2. Writer B updates the row to 80, commits, and deletes the cache key.
3. A, delayed for a few milliseconds by a GC pause or a slow network, now sets the cache to the 100 it read before.
4. The cache says 100 and the database says 80, and nothing will correct it until the TTL expires.

The window is small (A's read must start before B's commit and its set must land after B's delete), but at thousands of requests a second on hot keys it happens. The design-level fixes, from cheapest to strongest:

• Keep a TTL on every key. It doesn't prevent the race; it bounds the damage to one TTL.
• Delayed double delete: the writer deletes again a short time later (say a second, longer than a typical read takes). It narrows the window further but is a heuristic, not a guarantee.
• Leases (Facebook's memcache): on a miss, the cache hands the reader a 64-bit token bound to the key; a later delete invalidates the token, and the cache refuses a set with an invalidated token. A's stale set in step 3 is simply rejected. The same token rate-limits refills, which is the stampede fix in the next topic.
• Versioned writes: store a version (or the row's update timestamp) with the cached value and only accept a set if it's newer than what's there, atomically in the cache (a Lua script in Redis). The Databases course builds this.
• Change data capture (CDC): derive invalidations from the database's own commit log instead of from application code, as below.

And the order matters. Delete before writing is worse: between the delete and the commit, any reader refills the cache with the old value, and that's a much wider window than the race above. Update the cache instead of deleting is also worse with concurrent writers: two writers can commit in one order and update the cache in the other, leaving the older value cached. Facebook's paper gives the short reason they delete: deletes are idempotent, so they can be retried and repeated safely.

Asking every code path that writes to remember every affected key doesn't scale: someone adds a write path and forgets. The robust design is to tail the database's change log (MySQL binlog, PostgreSQL WAL logical replication, DynamoDB Streams) and turn each committed change into deletes of the keys it affects.

This is what Facebook described in "Scaling Memcache at Facebook" (NSDI 2013): a daemon called mcsqueal runs on every database, reads its MySQL commit log and broadcasts the deletes to every frontend memcache cluster in that region (other regions get the change through MySQL replication, and their own databases' mcsqueal invalidates their clusters), while the web server that made the change also deletes in its own cluster so the user sees their own write. Because the invalidations are derived from what the database committed and kept in its log, a misrouted or lost batch can be replayed, which was hard when web servers sent deletes directly. The paper also notes that only about 4% of deletes they issue actually remove a cached item, which tells you invalidation traffic is mostly wasted work, so it's batched. Today you'd build the same thing with Debezium (or a managed CDC stream) feeding a small consumer.

The price of CDC: one more pipeline to run and monitor, invalidations arrive with the pipeline's lag (typically well under a second, but it can grow), and the consumer must map a row change to every cache key derived from that row, which is easiest when keys are named after rows (product:42) rather than after queries.

With read replicas, "delete then the next read reloads" has a second race: the next read may go to a replica that hasn't applied the write yet, and it caches the old row with a fresh TTL. Fixes: read from the primary when refilling a key that was just invalidated, delay the invalidation until replicas have caught up (CDC from the replica's log does this naturally), or mark recently written keys so their refills go to the primary. Facebook calls the last one a remote marker: when a non-primary region writes, it sets a marker for the key, and a reader that sees the marker sends its refill query to the primary region.

Some invalidations would have to delete many keys at once: everything rendered for one user, every page of a category listing, every cached query for one tenant. A cache has no "delete by prefix" that's cheap; in Redis you'd have to SCAN the whole keyspace. Versioned keys turn that into a single write: keep a small version number per user (or tenant, or category), put it in every derived key's name, and bump it to invalidate them all.

// A fake shared cache that counts how many keys each operation has to touch.
const cache = new Map();
let touched = 0;
const get = (k) => { touched++; return cache.get(k); };
const set = (k, v) => { touched++; cache.set(k, v); };

// 100,000 cached fragments from 2,000 users; user 42 owns 50 of them.
for (let u = 0; u < 2_000; u++) for (let f = 0; f < 50; f++) cache.set(`u:${u}:v1:frag:${f}`, `html ${u}/${f}`);
for (let u = 0; u < 2_000; u++) cache.set(`u:${u}:ver`, 1);   // each user's current namespace version

// Option A: delete by pattern. The cache has no index by prefix, so you scan everything.
function deleteByPattern(prefix) {
  let deleted = 0;
  for (const k of [...cache.keys()]) { touched++; if (k.startsWith(prefix) && !k.endsWith(":ver")) { cache.delete(k); deleted++; } }
  return deleted;
}
// Option B: bump the user's version. Every key the app builds now has a new name.
const bump = (u) => set(`u:${u}:ver`, get(`u:${u}:ver`) + 1);
const keyFor = (u, f) => `u:${u}:v${get(`u:${u}:ver`)}:frag:${f}`;

touched = 0;
const deleted = deleteByPattern("u:42:");
console.log(`A  delete by pattern: removed ${deleted} keys, touched ${touched} keys`);

for (let f = 0; f < 50; f++) cache.set(`u:42:v1:frag:${f}`, `html 42/${f}`);   // put them back for option B
touched = 0;
bump(42);
console.log(`B  bump version:      touched ${touched} keys, version is now ${cache.get("u:42:ver")}`);
console.log(`   next read builds ${keyFor(42, 7)} -> ${cache.get(keyFor(42, 7)) ?? "miss, reload from DB"}`);
const orphans = [...cache.keys()].filter((k) => k.startsWith("u:42:v1:")).length;
console.log(`   ${orphans} old v1 keys are now unreachable; their TTL (or eviction) removes them`);

A  delete by pattern: removed 50 keys, touched 102000 keys
B  bump version:      touched 2 keys, version is now 2
   next read builds u:42:v2:frag:7 -> miss, reload from DB
   50 old v1 keys are now unreachable; their TTL (or eviction) removes them

Versioning by content is the same idea at the edge: app.3f9a1c.js is a versioned key. A deploy changes the hash, the HTML points at the new name, and the old file is never requested again, which is the only reliable way to "invalidate" a browser cache you can't reach.

The last strategy needs the cache entry to outlive its freshness, which is the soft TTL / hard TTL split: store the value with a long real expiry and, inside the value, a shorter "refresh after" time.

"Scaling Memcache at Facebook" (NSDI 2013) describes the lock-like defence built into the cache itself. On a miss, memcached gives the client a lease token, and it hands out a token for a given key at most once every 10 seconds by default. Anyone else who misses within those 10 seconds is told to wait a short time and retry; by then the lease holder has usually set the value within a few milliseconds. On a week of misses for keys prone to thundering herds, the paper reports the peak database query rate fell from 17K/s without leases to 1.3K/s with them, and since they provision databases for peak load, that's a direct hardware saving. Clients that can live with slightly old data can instead take a stale value that memcached keeps briefly after a delete, which is the "serve stale" row of the model.

Stampedes don't need one hot key. If many keys are written at the same moment (a cache restart, a deploy that warms the cache, a nightly job), they all get the same TTL and expire at the same moment, and because each is reloaded as soon as it expires, they get the same TTL again. The wave repeats every TTL period. The model below loads 100,000 keys in the first 10 seconds after a restart, gives each a 300 s TTL, and assumes every key is read constantly, so it's reloaded the second it expires. It counts database reloads per second over an hour, with and without random jitter on each TTL.

function mulberry32(a) {                                    // seeded PRNG: same numbers every run
  return () => {
    a |= 0; a = (a + 0x6d2b79f5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
// 100,000 keys are all loaded in the first 10 s after a cache restart, each with a 300 s TTL.
// Every key is read constantly, so it is reloaded from the database the second it expires.
const KEYS = 100_000, TTL = 300, HOURS = 1;

function run(jitter) {
  const rand = mulberry32(5);
  const reloadsPerSecond = new Array(HOURS * 3600).fill(0);
  for (let k = 0; k < KEYS; k++) {
    let t = Math.floor(rand() * 10);                          // first load during the warm-up burst
    while (t < reloadsPerSecond.length) {
      reloadsPerSecond[t]++;
      const ttl = TTL * (1 + jitter * (2 * rand() - 1));      // jitter = 0.1 means 270..330 s
      t += Math.max(1, Math.round(ttl));
    }
  }
  const peakIn = (from, to) => Math.max(...reloadsPerSecond.slice(from, to));
  const waves = [0, 1, 2, 5, 11].map((w) => String(peakIn(w * TTL, (w + 1) * TTL)).padStart(6));
  console.log(`jitter ±${String(jitter * 100).padStart(2)}%  peak DB reloads/s in TTL periods 1,2,3,6,12: ${waves.join(" ")}`);
}
console.log(`average if spread evenly: ${Math.round(KEYS / TTL)} reloads/s`);
for (const j of [0, 0.1, 0.25]) run(j);

average if spread evenly: 333 reloads/s
jitter ± 0%  peak DB reloads/s in TTL periods 1,2,3,6,12:  10167  10167  10167  10167  10167
jitter ±10%  peak DB reloads/s in TTL periods 1,2,3,6,12:  10125   1753   1611   1028    720
jitter ±25%  peak DB reloads/s in TTL periods 1,2,3,6,12:  10073    706    663    450    396

A hot key is a different problem: the value is in the cache, but one node has to serve all its traffic. Adding shards doesn't help, because a key lives on exactly one shard however many there are. The model puts 500,000 reads a second on a 16-shard cache: 80% follow a Zipf distribution over a million keys, and 20% are for one viral post. It reports the busiest shard's load and how far above the average shard it is, then tries two fixes.

const SHARDS = 16, KEYS = 1_000_000, RPS = 500_000, APP_SERVERS = 50;
const shardOf = (key) => {                                    // murmur3's fmix32 as a cheap, well-mixed hash
  let h = key ^ 0x9e3779b9;
  h = Math.imul(h ^ (h >>> 16), 0x85ebca6b); h = Math.imul(h ^ (h >>> 13), 0xc2b2ae35);
  return ((h ^ (h >>> 16)) >>> 0) % SHARDS;
};
let norm = 0;
for (let i = 1; i <= KEYS; i++) norm += 1 / i;                // Zipf, s = 1: key 0 is the most popular
const zipfRate = (key) => (RPS * 0.8) / (key + 1) / norm;     // 80% of traffic follows Zipf ...
const viral = RPS * 0.2;                                      // ... and 20% is one viral post, key 0

function report(label, loadOfKey) {
  const shards = new Array(SHARDS).fill(0);
  for (let k = 0; k < KEYS; k++) for (const [shard, rps] of loadOfKey(k)) shards[shard] += rps;
  const max = Math.max(...shards), mean = shards.reduce((a, b) => a + b) / SHARDS;
  const total = shards.reduce((a, b) => a + b);
  console.log(`${label.padEnd(30)} busiest shard ${String(Math.round(max)).padStart(6)}/s  ` +
    `${(max / mean).toFixed(2)}x the mean   cache traffic ${Math.round(total)}/s`);
}
const rate = (k) => zipfRate(k) + (k === 0 ? viral : 0);

report("no viral post", (k) => [[shardOf(k), zipfRate(k)]]);
report("viral post", (k) => [[shardOf(k), rate(k)]]);
// L1: every app server keeps the top 100 keys in memory for 1 s, so it asks the shard once a second per key.
report("viral + L1 for top 100 (1 s)", (k) => [[shardOf(k), k < 100 ? Math.min(rate(k), APP_SERVERS) : rate(k)]]);
// Split: the viral key is written to 8 copies, "post:0#0".."post:0#7"; each read picks one copy at random.
report("viral + split into 8 copies", (k) =>
  k === 0 ? Array.from({ length: 8 }, (_, i) => [shardOf(KEYS + i), rate(0) / 8]) : [[shardOf(k), rate(k)]]);

no viral post                  busiest shard  50774/s  2.03x the mean   cache traffic 400000/s
viral post                     busiest shard 150774/s  4.82x the mean   cache traffic 500000/s
viral + L1 for top 100 (1 s)   busiest shard  17131/s  1.05x the mean   cache traffic 260833/s
viral + split into 8 copies    busiest shard  68659/s  2.20x the mean   cache traffic 500000/s

Finding hot keys is half the job. Options: sample commands at the client and count keys (cheap, works on any cache); Redis's redis-cli --hotkeys, which needs an LFU eviction policy because it reads the LFU counters (on an LRU policy Redis 8.10 refuses with "ERR An LFU maxmemory policy is not selected, access frequency not tracked", checked in a local container); per-node CPU and network metrics, where one node far above the rest is the signature of a hot key; and, best of all, knowing your domain: a celebrity's post, the home page, the product in tonight's TV advert.

The ring isn't the only scheme with the "move only 1/N" property, and two others are simpler.

Rendezvous hashing (highest random weight, Thaler and Ravishankar, 1996): for each key, score every node with hash(node, key) and pick the highest score. When a node joins, it wins only the keys where its score beats the old winner's, about 1/(N + 1) of them; when one leaves, only its keys move, each to its runner-up. No ring, no virtual nodes, perfectly even load, but each lookup costs N hashes, which is fine for tens of nodes and poor for thousands.

Jump consistent hash (Lamping and Veach, Google, 2014) computes the bucket for a key from the key and the bucket count alone, in a few lines of arithmetic and no memory at all. Its catch: buckets must be numbered 0..n-1, so you can only add or remove the last bucket. That suits storage shards that are renamed and replicated behind the number, not caches whose arbitrary members come and go.

import { createHash } from "node:crypto";
const md5 = (s) => createHash("md5").update(s).digest();

// Rendezvous (highest random weight): score every node for this key, pick the highest.
const rendezvous = (key, nodes) => {
  let best, bestScore = -1;
  for (const n of nodes) { const s = md5(`${n}|${key}`).readUInt32BE(0); if (s > bestScore) [best, bestScore] = [n, s]; }
  return best;
};
// Jump consistent hash (Lamping and Veach, 2014): no table at all, buckets must be numbered 0..n-1.
const jump = (key, buckets) => {
  let k = md5(key).readBigUInt64BE(0), b = -1n, j = 0n;
  while (j < BigInt(buckets)) {
    b = j;
    k = (k * 2862933555777941757n + 1n) & 0xffffffffffffffffn;   // 64-bit linear congruential step
    j = BigInt(Math.floor(Number(b + 1n) * (2 ** 31 / Number((k >> 33n) + 1n))));
  }
  return Number(b);
};

const keys = Array.from({ length: 100_000 }, (_, i) => `user:${i}`);
const names = (n) => Array.from({ length: n }, (_, i) => `cache-${i}`);
for (const [label, place] of [
  ["rendezvous", (k, n) => rendezvous(k, names(n))],
  ["jump hash", (k, n) => jump(k, n)],
]) {
  let moved = 0;
  const load = new Map();
  for (const k of keys) {
    const a = place(k, 10);
    if (a !== place(k, 11)) moved++;
    load.set(a, (load.get(a) ?? 0) + 1);
  }
  const c = [...load.values()], mean = keys.length / 10;
  console.log(`${label.padEnd(10)} 10 -> 11 nodes: moved ${((moved / keys.length) * 100).toFixed(1)}%  ` +
    `busiest ${(Math.max(...c) / mean).toFixed(2)}x, emptiest ${(Math.min(...c) / mean).toFixed(2)}x the mean`);
}

rendezvous 10 -> 11 nodes: moved 9.1%  busiest 1.01x, emptiest 0.99x the mean
jump hash  10 -> 11 nodes: moved 9.3%  busiest 1.02x, emptiest 0.98x the mean

• Memcached clients use consistent hashing on the client side (the "ketama" ring is the classic implementation); the servers don't know about each other. Facebook's memcache paper says items are distributed across hundreds of servers in a cluster this way.
• Cassandra and Dynamo-style stores place nodes on a token ring with virtual nodes. Cassandra 5.0's default is num_tokens: 16 (its docs, checked October 2026); older versions defaulted to 256, and a newer token allocator chooses positions to keep load even with fewer tokens.
• Redis Cluster doesn't use a ring. It uses a fixed set of 16,384 hash slots, slot = CRC16(key) mod 16384, and an explicit table saying which node owns which slots. Adding a node means moving some slots to it, deliberately, with live migration. It's the same goal (only the moved slots' keys change owner) reached with a directory instead of a ring, and it lets an operator move exactly the slots they choose (see Distributed caches).

Fixed slots versus a ring is a real design choice. A ring needs no coordination (every client computes the same answer from the member list) but moves whatever arcs the hashes dictate. Slots need a shared slot table that every client must learn and refresh, but rebalancing is explicit, can be done slot by slot at a chosen pace, and lets you place hot slots on bigger machines.

Redis replicates asynchronously: the primary acknowledges a write and then sends it to replicas. The Redis Cluster specification is explicit that there are small windows where acknowledged writes can be lost: a write reaches a primary, the primary replies, and it fails before the replica receives the write; the promoted replica never had it. Failover takes the node timeout plus about one or two seconds for a replica to be elected. For a cache this is usually fine, because it holds copies and the worst case is a few stale or missing keys. It's not fine if you've used the cache as the only copy of something (write-behind, sessions, rate-limit counters), which is when you reach for WAIT (block until N replicas acknowledged), persistence, or a real database.

Reading from replicas (READONLY on a cluster connection) spreads read load but makes reads eventually consistent: a replica can serve a value the primary has already deleted, which reintroduces the invalidation races from earlier in a new place. It's a reasonable trade for hot read-mostly keys; for anything you just invalidated, read the primary.

In Redis Cluster every key maps to one of 16,384 slots, CRC16(key) mod 16384, and each primary owns ranges of slots. The spec suggests clusters on the order of 1,000 nodes at most. A command touching several keys (MGET, MSET, a transaction, a Lua script) works only if all its keys are in the same slot. You control that with a hash tag: if a key contains {...}, only the part inside the first braces is hashed, so user:{42}:profile and user:{42}:cart always share a slot. The model implements the slot function and checks it against the specification's CRC16 test value.

// Redis Cluster's key -> slot function: CRC16 (XMODEM variant) of the key, mod 16384.
function crc16(buf) {
  let crc = 0;
  for (const byte of buf) {
    crc ^= byte << 8;
    for (let i = 0; i < 8; i++) crc = crc & 0x8000 ? ((crc << 1) ^ 0x1021) & 0xffff : (crc << 1) & 0xffff;
  }
  return crc;
}
function slot(key) {
  const open = key.indexOf("{");                    // hash tag: only the part inside the first {...} is hashed
  if (open !== -1) {
    const close = key.indexOf("}", open + 1);
    if (close > open + 1) key = key.slice(open + 1, close);
  }
  return crc16(Buffer.from(key)) % 16384;
}
console.log("crc16('123456789') =", "0x" + crc16(Buffer.from("123456789")).toString(16), "(the spec's test value is 0x31c3)");
for (const k of ["somekey", "user:42:profile", "user:42:cart", "user:{42}:profile", "user:{42}:cart", "{}:empty-tag"])
  console.log(`${k.padEnd(18)} -> slot ${slot(k)}`);

// Three primaries split the slots evenly, like a fresh cluster created with 3 masters.
const owner = (s) => (s <= 5460 ? "A" : s <= 10922 ? "B" : "C");
console.log("user:{42}:profile and user:{42}:cart both live on primary", owner(slot("user:{42}:profile")));

crc16('123456789') = 0x31c3 (the spec's test value is 0x31c3)
somekey            -> slot 11058
user:42:profile    -> slot 9133
user:42:cart       -> slot 12984
user:{42}:profile  -> slot 8000
user:{42}:cart     -> slot 8000
{}:empty-tag       -> slot 15110
user:{42}:profile and user:{42}:cart both live on primary B

Size for both memory and throughput, and take the larger answer. The estimate below assumes a working set of 20 million keys of about 1 KB each, roughly 100 bytes of per-key overhead (key name, pointers, expiry; a rule of thumb, measure with MEMORY USAGE), 25% headroom for fragmentation and growth, nodes with 26 GB usable for data (a 32 GB machine leaving room for replication buffers and the OS), a peak of 400,000 operations a second, and about 100,000 operations a second per node (a rule of thumb for simple GETs and SETs; benchmark your own).

const keys = 20_000_000, valueBytes = 1_000, overheadBytes = 100, headroom = 1.25;
const usablePerNodeGB = 26, peakOps = 400_000, opsPerNode = 100_000, replicasPerShard = 1;

const dataGB = (keys * (valueBytes + overheadBytes) * headroom) / 1e9;
const shardsForMemory = Math.ceil(dataGB / usablePerNodeGB);
const shardsForOps = Math.ceil(peakOps / opsPerNode);
const shards = Math.max(shardsForMemory, shardsForOps);
console.log(`data with headroom: ${dataGB.toFixed(1)} GB -> ${shardsForMemory} shards for memory`);
console.log(`peak ${peakOps.toLocaleString("en")} ops/s -> ${shardsForOps} shards for throughput`);
console.log(`shards: ${shards}, nodes with ${replicasPerShard} replica each: ${shards * (1 + replicasPerShard)}`);
console.log(`losing one shard's primary drops ${(100 / shards).toFixed(0)}% of keys until its replica takes over`);

data with headroom: 27.5 GB -> 2 shards for memory
peak 400,000 ops/s -> 4 shards for throughput
shards: 4, nodes with 1 replica each: 8
losing one shard's primary drops 25% of keys until its replica takes over

Managed services set practical limits too: on Amazon ElastiCache, a cluster-mode Valkey or Redis OSS cluster has up to 90 nodes by default (from 90 shards with no replicas to 15 shards with 5 replicas each), raisable to 500 on Valkey 7.2+ or Redis OSS 5.0.6 to 7.1 (AWS docs, checked October 2026). Valkey is the open-source fork of Redis created after Redis's 2024 licence change; the Databases course covers the licensing story.