How does caching improve system performance?

// How a cache changes latency and database load, and what each write policy costs.
// Simulated: an in-process LRU stands for Redis/Memcached, a Map stands for the database.
// Latencies are assumed costs (cache 1 ms, database 20 ms), not measurements.

let seed = 7;
function rand() { // Park-Miller generator, identical in every language
  seed = (seed * 48271) % 2147483647;
  return seed / 2147483647;
}

const KEYS = 10000;
const cdf = [];
let total = 0;
for (let k = 1; k <= KEYS; k++) { total += 1 / k; cdf.push(total); }
function pick() { // Zipf: key k is requested with weight 1/k
  const u = rand() * total;
  let lo = 0, hi = KEYS - 1;
  while (lo < hi) { const mid = (lo + hi) >> 1; if (cdf[mid] < u) lo = mid + 1; else hi = mid; }
  return lo;
}

class LRU {
  constructor(cap) { this.cap = cap; this.map = new Map(); }
  get(k) {
    if (!this.map.has(k)) return undefined;
    const v = this.map.get(k); this.map.delete(k); this.map.set(k, v); return v;
  }
  set(k, v) {
    let out = null;
    if (this.map.has(k)) this.map.delete(k);
    else if (this.map.size >= this.cap) {
      const old = this.map.keys().next().value;
      out = [old, this.map.get(old)]; this.map.delete(old);
    }
    this.map.set(k, v);
    return out;
  }
  delete(k) { this.map.delete(k); }
}

const CACHE_MS = 1, DB_MS = 20, N = 100000, RPS = 5000;

console.log(`Part 1: ${N} reads over ${KEYS} keys (Zipf), cache ${CACHE_MS} ms, database ${DB_MS} ms`);
console.log("  cache size   hit ratio   avg ms   p50 ms   p99 ms   db reads/s at " + RPS + " req/s");
for (const cap of [0, 100, 1000, 3000, 9000]) {
  seed = 7;
  const cache = new LRU(Math.max(cap, 1));
  const lat = [];
  let hits = 0;
  for (let i = 0; i < N; i++) {
    const k = pick();
    if (cap > 0 && cache.get(k) !== undefined) { hits++; lat.push(CACHE_MS); continue; }
    lat.push(cap > 0 ? CACHE_MS + DB_MS : DB_MS); // a miss pays for the cache lookup too
    if (cap > 0) cache.set(k, "row" + k);
  }
  lat.sort((a, b) => a - b);
  const sum = lat.reduce((a, b) => a + b, 0);
  const avg = (Math.round((sum * 10) / N) / 10).toFixed(1);
  const p50 = lat[Math.floor(N * 0.5)], p99 = lat[Math.floor(N * 0.99)];
  const dbPerSec = Math.round((RPS * (N - hits)) / N);
  console.log(`  ${String(cap).padStart(10)}   ${(Math.round((hits * 1000) / N) / 10).toFixed(1).padStart(8)}%   ${avg.padStart(6)}   ${String(p50).padStart(6)}   ${String(p99).padStart(6)}   ${String(dbPerSec).padStart(8)}`);
}

console.log("\nPart 2: 100000 operations, 10% writes, cache holds 1000 keys, TTL 2000 operations");
console.log("  policy                 db reads   db writes   stale reads   unsaved if cache dies");
for (const policy of ["cache-aside + TTL", "cache-aside + delete", "write-through", "write-back"]) {
  seed = 7;
  const db = new Map(), truth = new Map(), dirty = new Set();
  const cache = new LRU(1000);
  let dbReads = 0, dbWrites = 0, stale = 0;
  const put = (k, e) => { // write-back flushes a dirty entry only when it is evicted
    const out = cache.set(k, e);
    if (out && dirty.has(out[0])) { db.set(out[0], out[1].v); dbWrites++; dirty.delete(out[0]); }
  };
  for (let i = 0; i < N; i++) {
    const k = pick();
    if (rand() < 0.1) { // a write of value i to key k
      truth.set(k, i);
      if (policy === "write-back") { put(k, { v: i, at: i }); dirty.add(k); continue; }
      db.set(k, i); dbWrites++;
      if (policy === "cache-aside + delete") cache.delete(k);
      if (policy === "write-through") put(k, { v: i, at: i });
      continue;
    }
    let e = cache.get(k);
    if (e && policy === "cache-aside + TTL" && i - e.at > 2000) { cache.delete(k); e = undefined; }
    if (!e) { dbReads++; e = { v: db.has(k) ? db.get(k) : -1, at: i }; put(k, e); }
    if (e.v !== (truth.has(k) ? truth.get(k) : -1)) stale++;
  }
  console.log(`  ${policy.padEnd(22)} ${String(dbReads).padStart(8)}   ${String(dbWrites).padStart(9)}   ${String(stale).padStart(11)}   ${String(dirty.size).padStart(21)}`);
}