Eviction আর invalidation — LRU, LFU, TTL আর cache stampede

১ · তিনটি আলাদা সমস্যা — eviction, expiration আর invalidation

Cache মানে ধীর উৎসের দরকারি অংশের একটি দ্রুত কপি। কিন্তু কপি রাখলেই তিনটি প্রশ্ন আসে, আর তিনটির উত্তর আলাদা জায়গায় লুকিয়ে থাকে। Cache কোথায় বসবে আর কে কখন তা ভরবে — cache-aside, read-through, write-through, write-back — সেই কৌশলগুলো পর্ব ২৮-এ। এই পর্বের প্রশ্ন তার পরের: কপি কখন আর কীভাবে সরবে।

নিচের ছবিতে তিনটিই: বাঁয়ে পড়ার পথ, ডানে লেখার পথ, মাঝে cache-এর ভেতর।

২ · LRU-র ভেতরে — hash map আর doubly linked list, প্রতিটি কাজ O(1)

সবচেয়ে পরিচিত eviction policy LRU (least recently used): জায়গা লাগলে সেই entry সরবে, যাকে সবচেয়ে বেশি সময় কেউ ছোঁয়নি — যা এইমাত্র লাগল, তা শিগগির আবার লাগার সম্ভাবনা বেশি। Hardware আর OS-এ একই নিয়ম: CA-র replacement policy আর OS-এর LRU. সেখানে কয়েকটি way বা frame; এখানে লাখ লাখ key, আর প্রতিটি সিদ্ধান্ত মাইক্রোসেকেন্ডে।

দুটি কাজ দ্রুত লাগবে: key দিয়ে মান খোঁজা, আর “কে সবচেয়ে পুরোনো” জানা ও ক্রম বদলানো। Hash table খোঁজে O(1)-এ, কিন্তু ক্রম জানে না; সময়-চিহ্নের heap ক্রম জানে, কিন্তু প্রতিটি hit-এ O(log n). উত্তর হলো জোড়া: hash map বলে node কোথায়, আর doubly linked list রাখে ক্রম — মাথায় সবচেয়ে সাম্প্রতিক বা MRU, লেজে সবচেয়ে পুরোনো বা LRU. Node-এর ঠিকানা জানা থাকলে তাকে খুলে নেওয়া মাত্র দুটি pointer বদল; আগের node-এর ঠিকানা লাগে বলেই list দ্বিমুখী। মৌলিক গঠন DSA-র hash table আর linked list পর্বে।

এবার একই গঠন কোডে। Hash map হিসেবে JavaScript-এর Map, আর list নিজে হাতে, দুই প্রান্তে দুটি পাহারাদার node (sentinel) দিয়ে — যাতে প্রথম বা শেষ node-এর জন্য আলাদা শর্ত না লাগে:

// O(1) LRU cache: a hash map (key -> node) plus a doubly linked list (head = MRU, tail = LRU).
class LRUCache {
  constructor(cap) {
    this.cap = cap; this.map = new Map();
    this.head = { key: "HEAD" }; this.tail = { key: "TAIL" };     // sentinels: no null checks
    this.head.next = this.tail; this.tail.prev = this.head;
  }
  unlink(n) { n.prev.next = n.next; n.next.prev = n.prev; }        // O(1): two pointer changes
  pushFront(n) { n.next = this.head.next; n.prev = this.head; this.head.next.prev = n; this.head.next = n; }
  get(key) {
    const n = this.map.get(key); if (!n) return undefined;          // O(1) lookup
    this.unlink(n); this.pushFront(n);                               // a hit makes it most recent
    return n.value;
  }
  put(key, value) {
    let n = this.map.get(key), evicted = "";
    if (n) { n.value = value; this.unlink(n); }
    else {
      if (this.map.size === this.cap) {                              // full: drop the tail (LRU)
        const lru = this.tail.prev; this.unlink(lru); this.map.delete(lru.key); evicted = lru.key;
      }
      n = { key, value }; this.map.set(key, n);
    }
    this.pushFront(n);
    return evicted;
  }
  order() { const k = []; for (let n = this.head.next; n !== this.tail; n = n.next) k.push(n.key); return k.join(" <-> "); }
}
const db = { A: "a1", B: "b1", C: "c1", D: "d1" }, cache = new LRUCache(3);
console.log("op     result               list (MRU ... LRU)");
for (const [op, k] of [["put", "A"], ["put", "B"], ["put", "C"], ["get", "A"], ["put", "D"], ["get", "B"], ["get", "A"]]) {
  let note = op === "get" && cache.get(k) !== undefined ? "hit" : op === "get" ? "miss, load" : "stored";
  if (note !== "hit") { const e = cache.put(k, db[k]); if (e) note += ", evict " + e; }
  console.log(`${op} ${k}`.padEnd(7) + note.padEnd(21) + cache.order());
}

op     result               list (MRU ... LRU)
put A  stored               A
put B  stored               B <-> A
put C  stored               C <-> B <-> A
get A  hit                  A <-> C <-> B
put D  stored, evict B      D <-> A <-> C
get B  miss, load, evict C  B <-> D <-> A
get A  hit                  A <-> B <-> D

৩ · LRU-র বাইরে — LFU, FIFO, random আর নমুনা-ভিত্তিক LRU

LRU দেখে একটিই সংকেত — সাম্প্রতিকতা। অন্যরা অন্য সংকেত দেখে, বা সস্তা হতে কম দেখে।

• FIFO: যে আগে ঢুকেছে সে আগে যায়; hit-এ কিছুই বদলায় না, তাই পড়া lock ছাড়াই চলে। দুর্বলতা: সবচেয়ে জনপ্রিয় key-ও পালা এলে বেরিয়ে যায়, তারপর miss করে আবার ঢোকে। OS-এ FIFO-র Belady anomaly এখানে।
• Random: এলোমেলো একটি entry সরানো, বাড়তি তথ্য শূন্য। বড় cache-এ ফল FIFO-র কাছাকাছি, আর চক্রাকার ব্যবহারে LRU-র চেয়েও ভালো — যেখানে LRU ঠিক পরের দরকারিটিকেই সরায় (CA-র LRU-র ফাঁদ)।
• LFU: প্রতিটি entry-র ব্যবহারের counter; সবচেয়ে কম ব্যবহৃত সরে। স্থির জনপ্রিয়তায় — পণ্যের ক্যাটালগ, সাইটের config — LRU-র চেয়ে ভালো। দুটি ফাঁদ: গতকালের জনপ্রিয়তা — গতকাল ভাইরাল ভিডিওর বড় counter তাকে আজও আটকে রাখে; আর নতুনের দুর্ভোগ — নতুন key counter ১ নিয়ে ঢুকে প্রথম সুযোগেই সরে। প্রতিকার aging: নিয়মিত সব counter অর্ধেক করা।
• নমুনা-ভিত্তিক LRU: list নয়, প্রতিটি key-এ শুধু শেষ ব্যবহারের সময়; জায়গা লাগলে কয়েকটি key এলোমেলোভাবে তুলে তাদের সবচেয়ে পুরোনোটিকে সরানো। Redis এভাবেই কাজ করে — allkeys-lru নীতিতে ডিফল্টে প্রতিবার ৫টি নমুনা (maxmemory-samples), আর সংস্করণ ৩.০ থেকে প্রার্থীদের একটি ছোট pool রেখে আন্দাজ আরও ভালো (documentation-এর বর্ণনা অনুযায়ী)।

নমুনা কতটা ভালো? k-টি key সমান সম্ভাবনায় তোলা হলে তাদের সবচেয়ে পুরোনোটির গড় শতাংশ-অবস্থান k/(k + ১) — k-টি সমবণ্টিত সংখ্যার সর্বোচ্চটির গড়। তাই k = ৫-এ victim গড়ে বাকি প্রায় ৮৩% key-এর চেয়ে পুরোনো, k = ১০-এ প্রায় ৯১%; নিখুঁত LRU-তে ১০০%. দশটি নমুনায় বেশিরভাগ লাভ আসে, আর key-প্রতি দুটি pointer-এর memory বাঁচে — কোটি key-তে বড় অঙ্ক।

# memory-র সীমা; এর ওপরে গেলে eviction শুরু
maxmemory 4gb
# লেখার সময়ে প্রচলিত নাম: noeviction (অনেক সংস্করণে ডিফল্ট), allkeys-lru, allkeys-lfu,
# allkeys-random, volatile-lru, volatile-lfu, volatile-random, volatile-ttl
# volatile-* শুধু TTL-ওয়ালা key থেকে বাছে; allkeys-* সব key থেকে
maxmemory-policy allkeys-lfu
# নমুনার আকার: বড় হলে LRU/LFU-র আন্দাজ ভালো, CPU বেশি
maxmemory-samples 10
# LFU counter-এর ক্ষয় (মিনিটে) আর বৃদ্ধির হার
lfu-decay-time 1
lfu-log-factor 10

খেয়াল করুন: ডিফল্ট প্রায়ই noeviction — memory ভরলে নতুন লেখা error দেয়, তাই cache হিসেবে চালালে policy নিজে বেছে নিতে হয়; আর volatile-* নীতিতে TTL-বিহীন key কখনো সরে না। Redis-এর LFU (সংস্করণ ৪.০ থেকে) key-প্রতি একটি ছোট logarithmic counter রাখে, যা সময়ের সাথে ক্ষয় হয় — aging-এর বাস্তব রূপ।

৪ · Scan, বদলাতে থাকা জনপ্রিয়তা আর আধুনিক policy — SLRU, 2Q, ARC, W-TinyLFU আর Belady-র সীমা

রাত ২টায় একটি report job সব পণ্য একবার করে পড়ল, বা একটি crawler পুরোনো সব পাতা ঘুরল। প্রতিটি key একবারই লাগবে, কিন্তু LRU-র চোখে প্রত্যেকে “এইমাত্র ব্যবহৃত” — তারা মাথায় বসে, আর সারাদিনের জনপ্রিয় key-গুলো লেজ দিয়ে বেরিয়ে যায়। এর নাম cache pollution; যে policy এটি সহ্য করে, তার গুণ scan resistance.

চারটি কৌশল, একটিই চিন্তা: একবার দেখাকে বিশ্বাস নয়

• Segmented LRU (SLRU): নতুনরা ঢোকে পরীক্ষাধীন (probation) অংশে, আবার ব্যবহৃত হলে ওঠে সুরক্ষিত (protected) অংশে; eviction শুধু probation-এর লেজ থেকে। Scan-এর key দ্বিতীয়বার আসে না, তাই সুরক্ষিত অংশ ছুঁতেই পারে না। Memcached-এর নতুন সংস্করণের hot-warm-cold LRU এই পরিবারের (খুঁটিনাটি সংস্করণভেদে আলাদা)।
• 2Q (Johnson ও Shasha, VLDB ১৯৯৪): প্রথমবার-আসারা একটি ছোট FIFO-তে; সেখান থেকে সরানোদের শুধু key মনে রাখে একটি ghost list; সেই key আবার এলে তবেই মূল LRU-তে।
• ARC (IBM-এর Megiddo ও Modha, USENIX FAST ২০০৩): T1-এ একবার দেখা, T2-এ অন্তত দুবার দেখা, আর দুটির ghost list B1, B2. B1-এ থাকা key-তে miss মানে “সাম্প্রতিকদের তাড়াতাড়ি সরিয়েছি”, তাই T1-এর লক্ষ্য-আকার বাড়ে; B2-তে উল্টো। হাতে-বসানো parameter ছাড়াই সে workload-এর সাথে মানিয়ে নেয়। ZFS-এর ARC এর পরিবর্তিত রূপ।
• W-TinyLFU (Einziger, Friedman ও Manes, ACM Transactions on Storage ২০১৭): প্রশ্ন বদলায় — “কাকে বের করব” নয়, “নতুনকে ঢুকতে দেব কি না”; এটি একটি admission policy. নতুন key আর eviction-এর প্রার্থীর আনুমানিক চাহিদা তুলনা হয়, নতুনটি বেশি জনপ্রিয় হলে তবেই ঢোকে। গোনে মোট একটি ছোট count-min sketch (গঠন পর্ব ৪৫-এ), যার counter নির্দিষ্ট সংখ্যক ঘটনার পরে সব অর্ধেক হয় — aging. সামনে একটি ছোট LRU জানালা (গবেষণাপত্রের ডিফল্টে মোটামুটি ১%), যাতে হঠাৎ জনপ্রিয় নতুনরা সুযোগ পায়। Java-র Caffeine লাইব্রেরি এটি ব্যবহার করে বলে তার documentation জানায়।

কোন চাহিদায় কোনটি জেতে

সাম্প্রতিকতা যেখানে সংকেত — সংবাদ-সাইটের “এইমাত্র” খবর, চ্যাটের শেষ বার্তা, চালকের সর্বশেষ অবস্থান — সেখানে LRU, কারণ জনপ্রিয়তা দ্রুত বদলায়। স্থির জনপ্রিয়তা — পণ্যের ক্যাটালগ, শীর্ষ বিক্রির তালিকা — সেখানে frequency. মিশ্র, তার ওপর scan — বেশিরভাগ বাস্তব সিস্টেম — সেখানে SLRU, ARC বা W-TinyLFU. ঈদের আগে অনলাইন বাজারের flash sale-এ দুটোই ঘটে: পুরোনো জনপ্রিয় পণ্য থাকে, আর হঠাৎ নতুন অফারে ভিড়।

সীমা কোথায় — Belady-র OPT

১৯৬৬ সালে IBM-এর László Bélády যে নীতি বর্ণনা করেন: যে entry সবচেয়ে দেরিতে আবার লাগবে, তাকে সরানো — এর চেয়ে কম miss অসম্ভব (প্রমাণের রূপরেখা OS-এর OPT অংশে)। ভবিষ্যৎ জানতে হয় বলে চালানো যায় না, কিন্তু রেকর্ড করা trace-এ জানা যায় আর কতটা উন্নতি সম্ভব; cache-এ সে আর-কখনো-না-লাগা key ঢুকতেই দেয় না। এই Belady-র সীমা-সহ নিচে চারটি policy, তিনটি seeded trace-এ: ১০,০০০টি key, Zipf-ধাঁচের জনপ্রিয়তা (α = ০.৯), cache ৩০০টি key-এর। (খ)-তে অর্ধেক সময় একটি job প্রতিটি ব্যবহারকারী-অনুরোধের পাশে দুটি নতুন, একবার-পড়া key ছোঁয়; (গ)-তে প্রতি ২০,০০০ অনুরোধে জনপ্রিয়তা ৩,০০০ key সরে যায়। Hit গোনা শুধু ব্যবহারকারীর অনুরোধে। আকার বনাম hit-এর বক্ররেখা পর্ব ১৭-এর অংশ ৬-এ; এখানে আকার স্থির, policy বদলায়:

// Hit ratio of FIFO, random, LRU, LFU and Belady's OPT (offline bound) on three seeded traces.
const N = 10000, ALPHA = 0.9, CAP = 300, REQS = 60000, WARM = 10000;
function mulberry32(a) { return () => { 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 rnd = mulberry32(7), cdf = new Float64Array(N); let sum = 0;
for (let k = 1; k <= N; k++) { sum += Math.pow(k, -ALPHA); cdf[k - 1] = sum; }
function zipf() { let lo = 0, hi = N - 1; const x = rnd() * sum;
  while (lo < hi) { const m = (lo + hi) >> 1; if (cdf[m] < x) lo = m + 1; else hi = m; } return lo; }
const A = [], B = [], C = []; let once = N;      // keys >= N belong to a scan: read once, never again
for (let i = 0; i < REQS; i++) {
  const k = zipf(); A.push(k); B.push(k); C.push((k + 3000 * Math.floor(i / 20000)) % N);
  if (Math.floor(i / 5000) % 2) B.push(once++, once++);   // half the time a job scans 2 keys/request
}
function run(pol, tr) {
  const c = new Map(), next = new Int32Array(tr.length), seen = new Map(), rr = mulberry32(99);
  for (let i = tr.length - 1; i >= 0; i--) { next[i] = seen.get(tr[i]) ?? 1e9; seen.set(tr[i], i); }
  let z = 0, hits = 0;
  tr.forEach((k, i) => {
    const hit = c.has(k); if (k < N && ++z > WARM && hit) hits++;   // score user requests only
    if (hit) { if (pol === "LRU") { c.delete(k); c.set(k, 0); } else if (pol === "LFU") c.set(k, c.get(k) + 1);
      else if (pol === "OPT") c.set(k, next[i]); return; }
    if (pol !== "OPT" && c.size >= CAP) {                  // evict one key, then admit the new one
      let v = c.keys().next().value, m = Infinity, j = Math.floor(rr() * c.size);  // FIFO/LRU: oldest
      if (pol === "RANDOM") for (const x of c.keys()) if (j-- === 0) { v = x; break; }
      if (pol === "LFU") for (const [x, f] of c) if (f < m) { m = f; v = x; }      // ties: oldest
      c.delete(v);
    }
    c.set(k, pol === "OPT" ? next[i] : pol === "LFU" ? 1 : 0);
    if (pol === "OPT" && c.size > CAP) { let m = -1, v; for (const [x, n] of c) if (n > m) { m = n; v = x; } c.delete(v); }
  });
  return ((hits / (REQS - WARM) * 100).toFixed(1) + "%").padStart(10);
}
console.log(`keys ${N}, Zipf alpha ${ALPHA}, cache ${CAP} keys, ${REQS} user requests (first ${WARM} = warm-up)`);
console.log("policy     (a) Zipf  (b) + scan  (c) shift");
for (const p of ["FIFO", "RANDOM", "LRU", "LFU", "OPT"]) console.log(p.padEnd(8) + run(p, A) + run(p, B) + run(p, C));

keys 10000, Zipf alpha 0.9, cache 300 keys, 60000 user requests (first 10000 = warm-up)
policy     (a) Zipf  (b) + scan  (c) shift
FIFO         34.7%     27.7%     34.6%
RANDOM       34.7%     27.7%     34.5%
LRU          39.1%     31.9%     39.0%
LFU          48.7%     48.2%     22.2%
OPT          59.9%     59.9%     59.2%

৫ · TTL-এর নকশা — fixed বনাম sliding, jitter আর soft TTL

Expiration-এর দুই রূপ। Fixed (absolute) TTL: লেখার মুহূর্ত থেকে T সেকেন্ড, যতবারই পড়া হোক — invalidation না থাকলেও কোনো কপি T-এর বেশি পুরোনো নয়, তবে replica থেকে ভরা হলে সাথে যোগ হয় replication lag. Sliding TTL: প্রতিটি পড়ায় মেয়াদ নতুন করে শুরু, শুধু অলস key মরে। Session-এ এটি স্বাভাবিক, কিন্তু উৎস-বদলানো ডেটায় বিপজ্জনক: প্রতি সেকেন্ডে পড়া জনপ্রিয় key কখনোই মরে না, তার staleness-এর সীমা নেই — তাই সাথে একটি সর্বোচ্চ বয়স। Redis-ধাঁচের store-এ সাধারণ GET মেয়াদ বাড়ায় না; তার জন্য আলাদা কমান্ড (যেমন GETEX, Memcached-এ touch — সংস্করণভেদে আলাদা)।

খুঁটিনাটি: মেয়াদোত্তীর্ণ key সাধারণত সাথে সাথে মোছে না — lazy expiration-এ পড়ার সময় মেয়াদ দেখে মোছা হয়, আর পেছনের একটি কাজ নমুনা নিয়ে মরা key খোঁজে। তাই expiration থাকলেও eviction policy লাগে।

TTL কত? আগে ব্যবসার প্রশ্ন — কতক্ষণ পুরোনো চলে; তারপর অঙ্ক — পুরোনো উত্তরের ভাগ মোটামুটি T ÷ ২P (P = উৎস কত ঘন ঘন বদলায়), পুরো হিসাব পর্ব ১৭-এর অংশ ৭-এ। Invalidation থাকলেও TTL রাখুন — হারানো invalidation-এর ক্ষতির সীমা সেটিই।

একসাথে লেখা, একসাথে মরা — TTL jitter

Deploy-এর পরে একটি warm-up script ১ লাখ key একসাথে লিখল, সবার TTL ৩৬০০ s. এক ঘণ্টা পরে একই সেকেন্ডে ১ লাখ key মরবে, পরের অনুরোধগুলো একসাথে ডেটাবেসে ছুটবে, আর আবার লেখা হলে ঢেউ প্রতি ঘণ্টায় ফিরবে। প্রতিকার: মেয়াদে এলোমেলো অংশ — TTL × (১ + J·u), u −১ থেকে ১-এর মধ্যে সমবণ্টিত। N-টি key তখন ২·J·T সেকেন্ডের জানালায় ছড়ায়:

N = ১,০০,০০০, T = ৩৬০০, J = ০.১০ হলে জানালা ৭২০ s, গড় প্রায় ১৩৯; কিন্তু কোনো কোনো সেকেন্ডে বেশি পড়ে, আর ডেটাবেসের সাথে মেলাতে হয় সর্বোচ্চটি। Seeded simulator-এ, সাথে আবার লেখার পরের ঢেউ:

// 100,000 keys are written at the same moment (say, a warm-up script after a deploy), TTL 3600 s.
// Each key's TTL gets a random +-J share: TTL * (1 + J * u), u uniform in [-1, 1).
// Every key is written again right after it expires. Count expirations per one-second bucket.
const KEYS = 100000, TTL = 3600;
function mulberry32(a) { return () => { 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; }; }
function wave(J, round) {                       // round = which expiry of each key (1st, 2nd, 3rd ...)
  const rnd = mulberry32(5), perSec = new Map();
  for (let k = 0; k < KEYS; k++) {
    let t = 0;
    for (let r = 0; r < round; r++) t += TTL * (1 + J * (2 * rnd() - 1));
    const s = Math.floor(t); perSec.set(s, (perSec.get(s) || 0) + 1);
  }
  const secs = [...perSec.keys()], max = Math.max(...perSec.values());
  const span = Math.max(...secs) - Math.min(...secs) + 1;
  console.log(`+-${(J * 100).toFixed(0)}%`.padStart(6) + String(round).padStart(7) +
    String(span).padStart(10) + (KEYS / span).toFixed(1).padStart(12) + String(max).padStart(10));
}
console.log("jitter  round  span (s)  mean per s  max per s");
for (const J of [0, 0.01, 0.05, 0.1, 0.2]) wave(J, 1);
wave(0, 3);
for (const r of [2, 3]) wave(0.1, r);

jitter  round  span (s)  mean per s  max per s
  +-0%      1         1    100000.0    100000
  +-1%      1        72      1388.9      1479
  +-5%      1       360       277.8       325
 +-10%      1       720       138.9       180
 +-20%      1      1440        69.4        99
  +-0%      3         1    100000.0    100000
 +-10%      2      1436        69.6       169
 +-10%      3      2129        47.0       130

Soft TTL — মেয়াদ পেরোলেও কাউকে অপেক্ষা করতে হয় না

Soft TTL-এ দুটি সময়সীমা: soft মেয়াদের পরে মানটি “নবায়ন দরকার”, তবু দেওয়া চলে আর একজন পেছনে নবায়ন করে; hard মেয়াদের পরে আর নয়। Store-এর TTL hard মেয়াদে, soft মেয়াদ লেখা থাকে মানের ভেতরে। HTTP-তে একই ধারণা stale-while-revalidate (পর্ব ১৭); stampede ঠেকাতে এর ভূমিকা অংশ ৭-এ।

৬ · Invalidation-এর কৌশল — শুধু TTL থেকে event, versioned key আর tag

প্রকৌশলীদের প্রিয় উক্তি: “Computer science-এ কঠিন কাজ দুটি — cache invalidation আর নাম দেওয়া।” এটি প্রচলিতভাবে Netscape-এর প্রকৌশলী Phil Karlton-এর বলে ধরা হয়, যদিও লিখিত উৎস নিশ্চিত করা কঠিন। কঠিন কেন? Invalidation আসলে বার্তা পৌঁছানোর সমস্যা: লেখা এক জায়গায়, কপি অন্য জায়গায়, আর মাঝের বার্তা দেরিতে আসে, হারায় বা ক্রম উল্টে আসে। CDN-এর purge-এর দিক থেকে একই প্রশ্ন পর্ব ১৭-এর ভাবনার প্রশ্নে; এখানে application cache-এর পাঁচ কৌশল:

লেখার পরে মোছা — সবচেয়ে প্রচলিত, আর তার ফাঁক

Cache-aside নকশায় অ্যাপ লেখে ডেটাবেসে, তারপর cache থেকে key মোছে; পরের পড়া miss করে নতুন মান আনে। নতুন মান বসানোর বদলে মোছা কেন, আর পড়া-লেখার race কীভাবে পুরোনো মান ফেরায় — পর্ব ২৮-এ। এখানে দুটি কাঠামোগত ফাঁক: এক, commit সফল, তারপর মোছার আগেই সার্ভার বন্ধ — পুরোনো মান TTL পর্যন্ত; এটি dual write-এর সমস্যা, যার একটি উত্তর পর্ব ২৫-এর outbox pattern. দুই, ডেটা বদলায় অনেক পথে — অন্য সার্ভিস, রাতের batch job, হাতে চালানো SQL — আর তারা কেউ cache-এর কথা জানে না।

Event-চালিত invalidation — log শোনে, key মোছে

দ্বিতীয় ফাঁকের উত্তর: প্রতিটি commit-ই invalidation-এর উৎস। Change data capture (CDC) ডেটাবেসের replication log পড়ে প্রতিটি পরিবর্তনকে event বানায়, আর একটি ছোট কর্মী সংশ্লিষ্ট key মোছে — লেখা যে পথেই আসুক। বিকল্পে লেখক নিজে একটি pub/sub channel-এ “user:42 বদলেছে” প্রকাশ করে, আর প্রতিটি সার্ভার শুনে নিজের local cache-এর কপি মোছে। Pub/sub পর্ব ৩২-এ, log-ভিত্তিক stream পর্ব ৩৩-এ। চারটি ঝুঁকি:

• হারানো বার্তা: কিছু pub/sub বার্তা জমিয়ে রাখে না — Redis-এর Pub/Sub documentation অনুযায়ী at-most-once; সংযোগ-কাটা গ্রাহক বার্তা পায় না। উত্তর: টেকসই log (offset ধরে আবার পড়া), আর TTL নিরাপত্তা-জাল।
• দুবার আসা: at-least-once-এ একই বার্তা দুবার আসে; মোছা idempotent, তাই ক্ষতি নেই।
• ক্রম উল্টানো: মোছার বার্তায় ক্রম অপ্রাসঙ্গিক — দুটোই key সরায়। কিন্তু বার্তায় নতুন মান পাঠালে v7 শেষে বসে v8-কে মুছে দিতে পারে; তখন শুধু বড় version হলে লেখা, অর্থাৎ compare-and-set. তাই নিয়ম: event-এ মান নয়, invalidation পাঠানো।
• আগে এসে পড়া: event key মুছল, কিন্তু পরের miss পড়ল read replica থেকে, যেখানে বদল তখনো আসেনি — পুরোনো মান আবার পুরো TTL-এর জন্য বসল (পর্ব ২২)। উত্তর: miss-এ primary থেকে পড়া, lag পেরোনোর পরে দ্বিতীয়বার মোছা (“delayed double delete”), বা versioned key.

Versioned key আর দল ধরে অচল করা

সবচেয়ে শক্তিশালী কৌশল: ভুলে যাওয়ার দরকারই না রাখা — ডেটা বদলালে নামই বদলাবে। Versioned key-এ সারিতে একটি version column, আর cache key-এ সেই সংখ্যা। পুরোনো key ভুল হয় না, শুধু অব্যবহৃত — TTL বা eviction-এ সরে। নামে hash-ওয়ালা static ফাইল (cache busting) একই চিন্তা।

on update(user 42):
    DB:    UPDATE users SET name = ..., version = version + 1 WHERE id = 42   -- now version 8
    cache: SET user:42:ver 8              -- tiny pointer key (or keep the version in a parent object)

on read(user 42):
    v    = cache.GET user:42:ver          -- on a miss, read the version from the DB
    data = cache.GET "user:42:v" + v      -- user:42:v8
    if data is missing:
        data = DB.read(42); cache.SET "user:42:v" + v, data, EX 3600
    -- nobody asks for user:42:v7 again; TTL or eviction removes it

-- group (namespace) invalidation: every page of a product list carries the group version
key = "plist:ns" + cache.GET(plist:ns) + ":page:" + n     -- plist:ns5:page:3
INCR plist:ns                                            -- ns5 -> ns6: every page is now a miss

সমস্যা পুরো যায় না, ছোট হয়: এখন শুধু একটি ছোট version key ঠিক রাখতে হয়। দলের সংস্করণ বাড়ালে পুরো দল একসাথে miss — বড় দলে সেটি নিজেই ঢল, তাই soft TTL বা ধাপে ধাপে। CDN-এর tag-purge (surrogate key) এই দল-চিন্তারই রূপ, পর্ব ১৭-এ।

৭ · Cache stampede গভীরে — lock, XFetch, stale পরিবেশন আর pre-warming

জনপ্রিয় একটি key cache-এ না থাকলে বহু অনুরোধ একসাথে miss করে ডেটাবেসে ছোটে — cache stampede, বা dogpile; ভিড়ের সাধারণ রূপ thundering herd-এর প্রথম পরিচয় পর্ব ৬-এর deep dive-এ। কারণ চারটি: hot key-এর মেয়াদ শেষ; ঠান্ডা শুরু (cold start) — নতুন node বা restart; deploy-এ flush বা গণ-invalidation; আর memory-র চাপে hot key-এরই eviction. আকার: সেকেন্ডে λ অনুরোধ আর recompute-এ Δ সেকেন্ড হলে মেয়াদের দেয়ালে আটকায় প্রায় λ × Δ অনুরোধ — λ = ২,০০০, Δ = ০.০৫ s-এ ১০০টি একই query. চাপে ডেটাবেস ধীর হলে Δ বাড়ে, আর সংখ্যাটিও।

# 1) try to take the lock: only one caller gets OK; it expires by itself after 2000 ms
SET lock:product:42 9f3c1a NX PX 2000
# 2) OK -> read the database, then write the value with its TTL
SET product:42 "{...}" EX 600
# 3) release only if the lock is still ours (check and delete together, e.g. in a Lua script)
#    if redis.call("GET", KEYS[1]) == ARGV[1] then return redis.call("DEL", KEYS[1]) end
# nil in step 1 -> someone else is computing: wait a few ms and GET again, or serve the stale copy

তিনটি খুঁটিনাটি: lock-এর মেয়াদ recompute-এর চেয়ে বড়, নইলে কাজ শেষের আগেই আরেকজন lock পায়; ছাড়ার সময় token মেলানো, যাতে অন্যের lock ভুলে মুছে না যায়; আর lock-সেবা বিকল হলে নিয়ম কী, তা আগেই ঠিক করা। Distributed lock, lease আর fencing token পর্ব ৪৩-এ।

XFetch — মেয়াদের আগেই, সম্ভাবনার নিয়মে নবায়ন

Lock-এ সমন্বয় লাগে, আর দেয়ালে কেউ না কেউ অপেক্ষা করেই। বিকল্প: দেয়ালে পৌঁছানোর আগেই কাউকে দিয়ে নবায়ন — probabilistic early expiration. Vattani, Chierichetti ও Lowenstein-এর “Optimal Probabilistic Cache Stampede Prevention” (PVLDB, ২০১৫) গবেষণাপত্রের রূপটির নাম XFetch. প্রতিটি entry-র সাথে রাখা হয় Δ — শেষ recompute-এর সময়। প্রতিটি অনুরোধ কারও সাথে কথা না বলে সিদ্ধান্ত নেয়:

rand() ০ থেকে ১-এর মধ্যে, তাই −Δ·β·ln(rand()) একটি সূচকীয় (exponential) এলোমেলো দূরত্ব, গড় Δ·β — অনুরোধটি যেন নিজের ঘড়ি সেই দূরত্বে এগিয়ে দেখে। মেয়াদ যত কাছে, সম্ভাবনা তত বেশি। β = ১ ডিফল্ট; বাড়ালে আরও আগে নবায়ন, ডেটাবেসে কিছু বাড়তি কাজ। আর ধীর recompute-এ (বড় Δ) নবায়ন নিজে থেকেই আগে শুরু হয়।

function fetch(key, ttl, beta = 1):
    value, delta, expiry = cache.read(key)
    if value is missing or now() - delta * beta * ln(rand()) >= expiry:
        start = now()
        value = recompute_value()          -- the database or the slow service
        delta = now() - start              -- measured, stored with the value
        cache.write(key, (value, delta), ttl)
    return value

এবার চারটি নকশা একই seeded Poisson-ধাঁচের traffic-এ — সুরক্ষা নেই, single-flight lock, lock আর পুরোনো মান (soft TTL), আর XFetch; গোনা হচ্ছে recompute, দেয়ালে অপেক্ষা, পুরোনো মান, আর একসাথে সর্বোচ্চ query:

// One hot key, 2,000 req/s (seeded Poisson arrivals), TTL 10 s, 60 s of traffic.
// Recomputing the value from the database takes DELTA seconds. Four ways to handle expiry.
const RATE = 2000, DELTA = 0.05, TTL = 10, T = 60, BETA = 1;
function mulberry32(a) { return () => { 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; }; }
function sim(mode) {
  const rnd = mulberry32(2026);
  let t = 0, expiry = TTL, inflight = [], db = 0, waited = 0, stale = 0, peak = 0;
  const recompute = () => { inflight.push(t + DELTA); db++; peak = Math.max(peak, inflight.length); };
  for (;;) {
    t += -Math.log(1 - rnd()) / RATE; if (t >= T) break;
    inflight = inflight.filter((done) => (done <= t ? ((expiry = Math.max(expiry, done + TTL)), false) : true));
    if (t < expiry) {                                    // the cached value is still valid
      // XFetch: refresh early with probability exp(-(expiry - t) / (DELTA * BETA))
      if (mode === "xfetch" && t - DELTA * BETA * Math.log(1 - rnd()) >= expiry) recompute();
      continue;
    }
    if (mode === "none" || mode === "xfetch") { recompute(); waited++; }   // everyone goes to the DB
    else if (mode === "lock") { if (!inflight.length) recompute(); waited++; } // one goes, others wait
    else { if (!inflight.length) recompute(); stale++; } // "stale": one refreshes, others get old value
  }
  console.log(mode.padEnd(8) + String(db).padStart(13) + String(waited).padStart(9) +
    String(stale).padStart(8) + String(peak).padStart(10));
}
console.log(`recompute ${DELTA * 1000} ms, TTL ${TTL} s, ${RATE} req/s for ${T} s`);
console.log("mode     DB recomputes   waited  served  peak DB");
console.log("                      at expiry   stale  parallel");
["none", "lock", "stale", "xfetch"].forEach(sim);

recompute 50 ms, TTL 10 s, 2000 req/s for 60 s
mode     DB recomputes   waited  served  peak DB
                      at expiry   stale  parallel
none              503      503       0       117
lock                5      475       0         1
stale               5        0     475         1
xfetch             12        0       0         3

শেষ অস্ত্রটি সবচেয়ে পুরোনো: pre-warming — জানা ভিড়ের আগে (ফল প্রকাশ, flash sale, নতুন node) cache ভরে রাখা, আর নতুন node-এ traffic ধাপে ধাপে বাড়ানো। অজানা মুহূর্তে lock, soft TTL আর XFetch; জানা মুহূর্তে প্রস্তুতি।

৮ · Penetration আর avalanche — অস্তিত্বহীন key আর গণ-miss

Stampede একটি key-এর গল্প। আরও দুটি পরিচিত বিপদ আছে; অনেক ইন্টারভিউ-সংকলনে তিনটিকে একসাথে penetration, breakdown আর avalanche নামে ডাকা হয় — এখানে breakdown মানে একটি hot key-এর মেয়াদ শেষ, অর্থাৎ stampede. নাম উৎসভেদে আলাদা, ধারণা এক।

Cache penetration — যা নেই, তার জন্য বারবার

কেউ এমন id চাইছে যা ডেটাবেসেও নেই — একটি bug-এর ভুল id, পুরোনো লিংক, বা এলোমেলো id দিয়ে খোঁজা কোনো স্বয়ংক্রিয় client. উৎসেই নেই বলে cache-এ কখনো বসবে না, আর প্রতিটি অনুরোধ ডেটাবেস পর্যন্ত যায়। প্রতিরক্ষা তিন স্তরে:

• Negative caching: “নেই” উত্তরও ছোট TTL-এ (ধরা যাক ৩০–৬০ s) cache করা — একই id বারবার এলে কাজ করে। শর্ত: id-টি পরে তৈরি হলে সেই “নেই” মুছতে হবে।
• Bloom filter: প্রতিবার নতুন এলোমেলো id এলে negative cache কাজে আসে না। তখন সামনে সব বৈধ id-এর Bloom filter: “অবশ্যই নেই” বললে ডেটাবেসে না গিয়েই ফেরত। সেকেন্ডে ৫,০০০টি অস্তিত্বহীন id আর ১% ভুল-ইতিবাচক হারে ডেটাবেসে পৌঁছায় প্রায় ৫০টি; এক কোটি id-এর জন্য লাগে প্রায় ১২ MB আর ৭টি hash — সূত্র পর্ব ৪৫-এ।
• ইনপুট যাচাই আর সীমা: ভুল ধরনের id প্রথমেই প্রত্যাখ্যান, আর client-প্রতি অনুরোধের হারে সীমা — পর্ব ৪৯-এর rate limiter দিয়ে।

Cache avalanche — একসাথে বিপুল miss

দুই উৎস: সমলয়ে মেয়াদ (অংশ ৫-এর ঢেউ, প্রতিকার jitter) আর একটি cache node বিকল — তার ভাগের সব key একসাথে miss. হিসাব: সেকেন্ডে ১,০০,০০০ পড়া, ১০টি node-এ সমান ভাগ, hit ratio ৯৫%. স্বাভাবিকে ডেটাবেস পায় ১,০০,০০০ × ০.০৫ = ৫,০০০. একটি node পড়লে তার ১০,০০০-এর পুরোটাই ডেটাবেসে, বাকি ৯টি থেকে ৯ × ৫০০ = ৪,৫০০ — মোট ১৪,৫০০, প্রায় ২.৯ গুণ। ডেটাবেসের নিরাপদ সীমা ধরা যাক ৮,০০০ হলে এক node-এর বিভ্রাটই সেবা ফেলে দিতে পারে; সব key একসাথে মরলে চাপ ২০ গুণ।

• Cache-এর redundancy: node-এর replica বা দুটি cluster; consistent hashing (পর্ব ১৬), যাতে node বদলে শুধু তার ভাগটুকু সরে; replication আর বহু-স্তরের cache পর্ব ৩০-এ।
• বিকল্প পথ: অ্যাপ সার্ভারের ছোট local cache, ডেটাবেসমুখী query-র সীমা, circuit breaker (পর্ব ৪৮), আর বাড়তি অনুরোধ নম্রভাবে ফেরানো — load shedding (পর্ব ১৮)।
• পুরোনো দেখানো, বন্ধ নয়: soft TTL-এর পুরোনো মান বা সরল ডিফল্ট — graceful degradation.
• ফিরে আসার নিয়ম: ঠান্ডা node-এ traffic ধাপে ধাপে, আগে ভরে নিয়ে; নইলে ভাবনার প্রশ্ন ৫-এর ফাঁদ।

৯ · AI-এর যুগে — eviction আর invalidation-এর পরামর্শ যাচাই

“অ্যাপ ধীর” বললে AI প্রায়ই লেখে: “Redis বসান, LRU দিন, TTL এক ঘণ্টা, invalidation-এর জন্য Kafka.” কিছুটা হয়তো ঠিক, কিন্তু cache-এর ভুল নিঃশব্দ — পুরোনো দাম, ভুল স্টক, মেয়াদের মুহূর্তে ডেটাবেসের ধস — আর demo-তে ধরা পড়ে না। চেনা ভুলগুলো:

AI-এর cache-পরিকল্পনা হাতে পেলে — যাচাইয়ের চেকলিস্ট

• প্রতিটি ডেটার “কতক্ষণ পুরোনো চলে” সংখ্যায় লেখা; যেখানে শূন্য, সেই পড়া cache থেকে নয়
• Eviction policy নিজের trace-এ মেপেছি — scan আর জনপ্রিয়তার বদলসহ, OPT-এর পাশে রেখে
• TTL-এ jitter আছে, আর N ÷ ২JT ও সর্বোচ্চ সেকেন্ড নিজে হিসাব করেছি
• Invalidation হারালে, দুবার এলে, উল্টো ক্রমে এলে বা replica পিছিয়ে থাকলে কী হয় — ভেবেছি; TTL নিরাপত্তা-জাল আছে
• Hot key-এ λ × Δ হিসাব করে stampede-এর প্রতিকার বেছেছি; lock-এর মেয়াদ recompute-এর চেয়ে বড়
• Setting documentation আর CONFIG GET-এ মিলিয়েছি; ছোট load test বা simulation চালিয়েছি
• Failure-mode review: cache node বিকল, সব key ঠান্ডা, invalidation বন্ধ — প্রতিটিতে ডেটাবেসের চাপ কত