Distributed cache — partitioning, replication, hot key আর বহু-স্তরের cache

১ · একটি cache সার্ভার কখন যথেষ্ট নয় — memory, throughput আর availability

পর্ব ২৮-এ দেখেছেন cache-এ পড়া-লেখার নিয়ম (Caching কৌশল), পর্ব ২৯-এ কখন কী মুছবেন (Eviction আর invalidation) — দুটোতেই cache ছিল একটি বাক্স। এবার বাক্সটিকে একটি মেশিনের বাইরে নিতে হবে। শুরুতে একটি Redis বা Memcached সার্ভারই যথেষ্ট; একদিন তিনটি দেয়ালের কোনো একটিতে ধাক্কা লাগে:

• Memory: বারবার লাগা ডেটা — working set — আর এক মেশিনের RAM-এ আঁটে না। ফলে eviction বাড়ে, hit ratio নামে, database-এর চাপ বাড়ে।
• Throughput: একটি সার্ভার সেকেন্ডে নির্দিষ্ট সংখ্যক অনুরোধই সামলায় — CPU-র সীমা (Redis-এ command মূলত একটি thread-এ চলে), আর network card-এর bandwidth.
• Availability: সার্ভারটি বন্ধ হলে প্রতিটি hit মুহূর্তে miss, পুরো চাপ database-এ। Cache তখন একটি single point of failure, আর database সাধারণত সেই চাপের জন্য বানানোই হয়নি।

আকারের হিসাব — working set × overhead থেকে node-এর সংখ্যা

পর্ব ৩ — Back-of-the-envelope হিসাব-এর মতোই, তবে তিনটি আলাদা সীমা দেখতে হয়, আর সবচেয়ে কড়াটিই উত্তর:

• Overhead: প্রতিটি item-এর সাথে store নিজের হিসাব রাখে — hash table-এর ঘর, মেয়াদ, LRU-র pointer, allocator-এর গোল করা মাপ; মোটামুটি কয়েক দশক byte, engine আর সংস্করণভেদে আলাদা। অনুমান না করে নমুনা ভরে মাপুন (Redis-এ MEMORY USAGE command).
• ব্যবহারযোগ্য memory: পুরো RAM নয়। Fragmentation, client-এর buffer, persistence-এর fork আর OS-এর জন্য ২০–৩০% headroom রাখা একটি প্রচলিত সতর্কতা।
• কপি: প্রতিটি shard-এ একটি replica থাকলে memory দ্বিগুণ (অংশ ৩); throughput-এ সাধারণত শুধু primary ধরা হয়, কারণ ডিফল্টে পড়া যায় primary-তে।

নিচের হিসাবযন্ত্রে সব সংখ্যা ধরে নেওয়া। দ্বিতীয় অংশটি এই পর্বের সবচেয়ে গুরুত্বপূর্ণ সংখ্যা দেয়: replica ছাড়া একটি shard মরলে database-এ কত চাপ যায়, N = ৩, ৬ আর ১২-তে।

// Cache-cluster sizing from assumed inputs, then: what one dead shard does to the DB.
const items = 200e6;                    // cached items in the working set (assumed)
const keyB = 40, valB = 900, ovhB = 60; // bytes per item: key, value, engine overhead (varies)
const copies = 2;                       // each shard = 1 primary + 1 replica
const ramGB = 64, usable = 0.75;        // keep 25% for fragmentation, buffers, fork, OS
const peak = 600000, perShard = 100000; // peak reads/s; safe reads/s per primary (assumed)
const hit = 0.95;                       // cache hit ratio at peak

const perCopyGB = items * (keyB + valB + ovhB) / 1e9;
const byMem = Math.ceil(perCopyGB / (ramGB * usable));
const byOps = Math.ceil(peak / perShard);
const shards = Math.max(byMem, byOps);
console.log("one copy of the data: " + perCopyGB.toFixed(0) + " GB, usable per node: " +
  (ramGB * usable) + " GB");
console.log("shards for memory: " + byMem + ", for throughput: " + byOps + " -> " + shards +
  " shards x " + copies + " copies = " + shards * copies + " nodes");
console.log("network per shard at peak: " +
  (peak / shards * (keyB + valB) * 8 / 1e9).toFixed(2) + " Gbit/s");

console.log("\nshards  DB normal  DB after 1 dies  x normal  formula 1+h/(N(1-h))");
const dbNormal = Math.round(peak * (1 - hit));
for (const N of [3, 6, 12]) {
  const after = dbNormal + peak * hit / N;      // the dead shard's hits all become misses
  console.log(String(N).padStart(6) + String(dbNormal).padStart(11) +
    String(Math.round(after)).padStart(17) + (after / dbNormal).toFixed(2).padStart(10) +
    (1 + hit / (N * (1 - hit))).toFixed(2).padStart(10));
}

one copy of the data: 200 GB, usable per node: 48 GB
shards for memory: 5, for throughput: 6 -> 6 shards x 2 copies = 12 nodes
network per shard at peak: 0.75 Gbit/s

shards  DB normal  DB after 1 dies  x normal  formula 1+h/(N(1-h))
     3      30000           220000      7.33      7.33
     6      30000           125000      4.17      4.17
    12      30000            77500      2.58      2.58

নিচের ছবিটি এই পর্বের মানচিত্র: প্রতিটি app server-এর ভেতরে একটি ছোট local cache (L1), সবার ভাগের distributed cache cluster (L2), আর পেছনে database.

২ · Key কোন node-এ — client-side hashing, hash slot-এর cluster আর proxy

কয়েকটি cache node হলো; এখন প্রতিটি key-এর একটি ঠিকানা লাগবে, আর সব app server-কে একই ঠিকানা মানতে হবে। নিয়মের গণিত — ring, virtual node, rendezvous — আছে পর্ব ১৬ — Consistent hashing-এ। এখানে প্রশ্ন: সিদ্ধান্তটা কে নেয়? তিনটি প্রচলিত নকশা:

Hash slot-এর cluster ভেতর থেকে

Redis Cluster-এর অফিসিয়াল documentation অনুযায়ী (লেখার সময়ে) key-জগৎ ঠিক ১৬,৩৮৪টি hash slot-এ ভাগ: slot = CRC16(key) mod 16384. প্রতিটি primary কিছু slot-এর মালিক, আর node-রা একটি আলাদা cluster bus-এ heartbeat আর gossip দিয়ে মালিকানার খবর ছড়ায় — membership-এর তত্ত্ব পর্ব ৪৪ — Membership আর failure detection — heartbeat, gossip আর SWIM-এ। Slot থেকে node-এর table-টিই এখানে partition map, পর্ব ২৩ — Partitioning আর sharding-এর fixed partition-এর চিন্তা হুবহু। Redis-এর data type আর command আছে DBMS কোর্সের Redis পর্বে; এখানে দেখি একটি অনুরোধ ঠিক node কীভাবে খুঁজে পায় — resharding-এর মাঝপথেও।

client → C:  GET user:42:cart
C → client:  -ASK 12984 10.0.0.4:6379
client → D:  ASKING
client → D:  GET user:42:cart
D → client:  value      (slot map বদলাল না)

client → C:  GET user:42:cart
C → client:  -MOVED 12984 10.0.0.4:6379
client:      map-এ লিখল 12984 → D (বা পুরো map আবার আনল)
client → D:  GET user:42:cart
D → client:  value

MGET user:42:cart user:42:profile
-CROSSSLOT Keys in request don't hash to the same slot
CLUSTER KEYSLOT {user:42}:cart      →  15880
CLUSTER KEYSLOT {user:42}:profile   →  15880   (একই slot, একই node)

দুটি redirect-এর পার্থক্য মনে রাখুন: MOVED মানে “slot স্থায়ীভাবে সরেছে, map হালনাগাদ করুন”; ASK মানে “শুধু এবারের জন্য ওদিকে যান, map বদলাবেন না”। আরেকটি লুকানো খরচ: একটি পাতা একসাথে ১০০টি key চাইলে (multi-get) অনুরোধ যায় প্রায় সব shard-এ, আর উত্তরের সময় ঠিক করে সবচেয়ে ধীর shard — পর্ব ৪ — Latency, throughput আর percentile-এর fan-out. তাই একসাথে লাগা key-কে hash tag-এ এক জায়গায়, বা পাতার জন্য একটি মিলিত key রাখা প্রায়ই ভালো।

৩ · Cache-এর replication — primary-replica, হারানো লেখা আর “সত্যের উৎস”-এর ভুল

Cluster-এ প্রতিটি shard সাধারণত একটি primary আর এক বা একাধিক replica — আলাদা মেশিনে, ভালো হলে আলাদা availability zone-এ। লক্ষ্য durability নয়, availability: primary বিকল হলে replica উঠে আসে (failover), আর shard-এর key ঠান্ডা হয় না। পর্ব ২২ — Replication-এর leader-follower এখানে হুবহু, তবে প্রায় সব cache-এ replication asynchronous: primary নিজের memory-তে লিখেই client-কে OK বলে, কপি যায় পরে।

Failover-এ কী হারায় — আর কোন হারানো বেশি বিপজ্জনক

শেষ কয়েক millisecond-এর লেখা replica-তে পৌঁছানোর আগে primary মরলে নতুন primary সেগুলো জানে না। Cache-এ দুই রকম লেখা হারাতে পারে:

• হারানো SET: নতুন একটি মান লেখা হয়েছিল, হারাল। পরের পড়া miss পায় বা পুরোনো মান পায়, তারপর database থেকে নতুন করে আসে — ক্ষতি সামান্য।
• হারানো DEL (invalidation): database বদলানোর পর অ্যাপ key মুছেছিল (cache-aside, পর্ব ২৮), মোছাটাই হারাল। Replica-তে পুরোনো মান রয়ে গেল, আর নতুন primary সেটি দিতে থাকবে TTL শেষ না হওয়া পর্যন্ত। তাই প্রতিটি cache entry-তে একটি TTL রাখা নিরাপত্তা-জাল — invalidation হারালেও staleness-এর একটি সীমা থাকে।

Network ভাগ হলেও লেখা হারায়। Redis Cluster-এর documentation নিজেই বলে এটি strong consistency দেয় না: সংখ্যালঘু দিকে আটকে পড়া primary একটি timeout পর্যন্ত লেখা নিতে পারে, আর ওপাশে তার replica primary হলে সেই লেখাগুলো হারায় — split-brain-এর একটি রূপ। WAIT command কয়েকটি replica-র স্বীকৃতির অপেক্ষা করায়, তবু documentation অনুযায়ী তাতে Redis strongly consistent হয় না। Consistency-র অর্থ পর্ব ৪০ — CAP, PACELC আর consistency model-এ; আর এখানকার failover-এর ভোট পূর্ণ consensus নয় — সেই তত্ত্ব পর্ব ৪২-এ।

Cache-এর কি durability লাগে?

সাধারণ উত্তর: না। সত্যের উৎস database; cache হারালে আবার বানানো যায়। তবু persistence বা replica রাখার একটি কারণ আছে — উষ্ণতা: ২০০ GB-এর ঠান্ডা cache ভরতে database-কে সব পড়া নতুন করে দিতে হয়, যা অংশ ১-এর টেবিলের চেয়েও বড় ধাক্কা। তাই replica থাকে availability-র জন্য, আর নিয়মিত snapshot থাকলে restart-এর পর cache উষ্ণ ফেরে; প্রতিটি লেখার log (AOF) বিশুদ্ধ cache-এ সাধারণত লাগে না। খুঁটিনাটি DBMS কোর্সের Redis পর্বে।

Replica থেকে পড়া: পড়ার চাপ ভাগ করতে replica থেকেও পড়া যায় (Redis Cluster-এ replica-র connection-এ READONLY দিয়ে); দাম replication lag-এর সময়টুকু পুরোনো মান — প্রায়ই চলে, কিন্তু নিজের সদ্য লেখা দেখার পাতায় নয়।

৪ · একটি node মারা গেলে — database-এর ধাক্কা, gutter pool আর rehash storm

অংশ ১-এর সূত্রটি মনে করুন: ৬টি shard, peak-এ সেকেন্ডে ৬ লাখ পড়া, hit ৯৫% — database স্বাভাবিকভাবে পায় ৩০,০০০, একটি shard মরলে ১,২৫,০০০. ধরা যাক database নিরাপদে নিতে পারে ৫০,০০০. তাহলে cache-এর একটি node-এর বিভ্রাট মানেই পুরো সিস্টেমের বিভ্রাট। নিচের stepper-এ তিনটি প্রতিক্রিয়া — একটি ভুল, দুটি কাজের।

Gutter pool-এর ধারণাটি জনপ্রিয় হয় Facebook-এর memcache paper (Nishtala ও সহকর্মীরা, NSDI ২০১৩) থেকে। Paper অনুযায়ী একটি cluster-এর memcached সার্ভারের মোটামুটি ১% gutter হিসেবে রাখা হতো, আর বাকি সার্ভারে rehash না করার কারণ: একটি hot key পাশের সার্ভারে গিয়ে সেটিকেও ডোবাতে পারে।

Rehash storm কেন বিপজ্জনক

Client-side hashing-এ মৃত node-কে তালিকা থেকে বাদ দিলেই তার key-গুলো ring-এ পাশের node-এ যায় — মোটামুটি ১/N ভাগ (পর্ব ১৬)। শুনতে নিরাপদ, কিন্তু এই rehash storm-এর তিনটি সমস্যা: পাশের node-এ key-গুলো ঠান্ডা, তাই database-এর ধাক্কা একই; মৃত node-এর একটি hot key পাশের node-কেও ডোবাতে পারে, তারপর পরেরটিকে — cascading failure; আর node ফিরলে key-ও ফেরে, কিন্তু তার কপি বিভ্রাটের আগের, মাঝের invalidation গেছে পাশের node-এ — পুরোনো মান। বারবার ওঠানামা করা (flapping) node-এ এটি বারবার।

প্রতিকার: একবারের ব্যর্থ health check-এ node বাদ নয় — পরপর কয়েকবার, আর ফেরার আলাদা শর্ত (hysteresis); বাদ দেওয়ার সিদ্ধান্ত একটি কেন্দ্রীয় ব্যবস্থার, প্রতিটি client-এর নিজের নয়; ফিরে আসা node-কে খালি করে তবেই traffic দেওয়া; আর database-এ fallback সীমিত — concurrency limit আর request coalescing.

৫ · Hot key — চেনা, L1 cache, কপি ছড়ানো আর coalescing

Consistent hashing আর hash slot key-এর সংখ্যা সমান করে, traffic নয়। একটি কাল্পনিক খবরের সাইটে ক্রিকেট ফাইনালের দিন live score-এর key score:live-এ হঠাৎ মোট পড়ার বড় অংশ এলে সেই একটি shard ডোবে, বাকিরা অলস। Shard বাড়িয়েও লাভ নেই — key তো একটাই, থাকে একটি node-এ। এই একটি hot key-ই সমস্যা।

চেনা — কোন key গরম?

প্রথম লক্ষণ shard-এর metric: একটি shard-এর CPU বা network বাকিদের চেয়ে অনেক উঁচু, অথচ key-সংখ্যা সমান। তারপর key ধরে গোনা — client প্রতি ১০০টি অনুরোধে একটির key গুনে কয়েক সেকেন্ডে top-k পায়; key খুব বেশি হলে কম memory-র আনুমানিক গণনা count-min sketch, যার বিস্তারিত পর্ব ৪৫-এ। Store-এরও নিজের সুবিধা আছে, যেমন redis-cli --hotkeys (LFU-ধাঁচের eviction নিয়মে, সংস্করণভেদে)। পাওয়া তালিকা মেয়াদসহ সব app server-এ যায়।

সামলানো — চারটি উপায়

L1 — প্রতিটি app server-এর memory-তে অল্প TTL-এর কপি; কপি ছড়ানো — score:live#0 … #3 আলাদা shard-এ, পড়া এলোমেলো একটি থেকে, লেখা সবগুলোতে; coalescing — একসাথে আসা miss মিলিয়ে একটি অনুরোধ (পর্ব ২৯); আর replica থেকে পড়া, অংশ ৩-এর lag মেনে। কপি ছড়ানো পর্ব ২৩-এর salting-এর উল্টো: সেখানে লেখা ভাগ হয় আর পড়ায় সব লেজ লাগে, এখানে পড়া ভাগ হয় আর লেখায় সব কপি; লেখা-ভারী গরম গণনার পথ sharded counter. নকশাই বদলানোর উদাহরণ — বিখ্যাত অ্যাকাউন্টের পোস্ট পড়ার সময় আনা — পর্ব ৫৬ — Case study: news feed-এ। নিচে একটি live score-এ চারটির তিনটি একে একে:

এবার একই প্রশ্ন একটি simulation-এ: ৮টি shard, সেকেন্ডে ১,০০,০০০ অনুরোধ, ১০,০০০টি key-এ Zipf-ধাঁচের traffic, আর তার ওপরে একটি celebrity key — score:live — যে একাই ৩০% অনুরোধ পায়। তিনটি অবস্থা: কোনো প্রতিকার নেই; ৪০টি app server-এ L1 (TTL ১ সেকেন্ড); আর চারটি কপি। Hash FNV-1a, random সংখ্যা নির্দিষ্ট seed থেকে।

// 8 shards; Zipf traffic over 10,000 keys plus one celebrity key. Load per shard (req/s).
function h32(s) {                // FNV-1a 32-bit, then MurmurHash3's fmix32 to mix bits
  let h = 0x811c9dc5;
  for (let i = 0; i < s.length; i++) { h ^= s.charCodeAt(i); h = Math.imul(h, 0x01000193); }
  h ^= h >>> 16; h = Math.imul(h, 0x85ebca6b); h ^= h >>> 13; h = Math.imul(h, 0xc2b2ae35);
  return (h ^ (h >>> 16)) >>> 0;
}
let seed = 30; function rand() { // mulberry32: small seeded PRNG
  seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
}
const S = 8, SEC = 10, RPS = 100000, APPS = 40, HOT = "score:live", SHARE = 0.3, L1TTL = 1;
const cum = []; let tot = 0; for (let k = 1; k <= 10000; k++) { tot += 1 / k; cum.push(tot); }
function zipf() { const x = rand() * tot; let lo = 0, hi = cum.length - 1;
  while (lo < hi) { const m = (lo + hi) >> 1; if (cum[m] < x) lo = m + 1; else hi = m; } return lo + 1; }
const copies = [];                     // 4 copies of the hot key, on 4 different shards
for (let i = 0; copies.length < 4; i++) { const s = h32(HOT + "#" + i) % S; if (!copies.includes(s)) copies.push(s); }
const none = Array(S).fill(0), l1 = Array(S).fill(0), rep = Array(S).fill(0);
const l1Until = Array(APPS).fill(-1);  // per app server: until when its L1 copy is fresh
for (let i = 0; i < SEC * RPS; i++) {
  const t = i / RPS, app = Math.floor(rand() * APPS), hot = rand() < SHARE;
  const home = h32(hot ? HOT : "item:" + zipf()) % S, pick = copies[Math.floor(rand() * 4)];
  none[home]++;
  if (!hot) l1[home]++; else if (t >= l1Until[app]) { l1[home]++; l1Until[app] = t + L1TTL; }
  rep[hot ? pick : home]++;
}
const rows = { "none": none, "L1 1s": l1, "copies x4": rep };
console.log("hot key on shard " + h32(HOT) % S + ", copies on shards " + copies.join(","));
console.log("shard     " + [0, 1, 2, 3, 4, 5, 6, 7].map((x) => String(x).padStart(6)).join("") + "   max/avg");
for (const [name, c] of Object.entries(rows)) {
  const r = c.map((x) => Math.round(x / SEC)), sum = r.reduce((a, b) => a + b);
  console.log(name.padEnd(10) + r.map((x) => String(x).padStart(6)).join("") +
    (Math.max(...r) / (sum / S)).toFixed(2).padStart(10) + "   total " + sum);
}

hot key on shard 2, copies on shards 7,5,6,2
shard          0     1     2     3     4     5     6     7   max/avg
none       15966  6109 36697  8008 12616  6395  6313  7896      2.94   total 100000
L1 1s      15966  6109  6712  8008 12616  6395  6313  7896      1.82   total 70015
copies x4  15966  6109 14210  8008 12616 13876 13813 15402      1.28   total 100000

৬ · Big key — বিশাল value আর collection-এর দাম

Hot key-এর আত্মীয় big key: একটি key-এর value কয়েক MB — একটি পুরো পাতার HTML, বিশাল JSON — বা একটি hash, list বা sorted set-এ লাখো সদস্য। তিনটি দাম:

• Network: ৫ MB-এর একটি value 1 Gbit/s-এ পাঠাতে শুধু তারেই প্রায় ৪০ ms; 10 Gbit/s-এর card-ও সেকেন্ডে ২৫০ বার এটি পড়লেই ভরে যায় — সেই node-এর বাকি সব key-এর অনুরোধ পেছনে আটকে থাকে।
• এক thread-এর CPU: Redis-এ command মূলত একটি thread-এ পরপর চলে। লাখো সদস্যের একটি collection পুরো পড়া (HGETALL) বা মোছা (DEL) যতক্ষণ চলে, ততক্ষণ সেই node-এর বাকি সব client অপেক্ষায় — tail latency লাফায়। মোছার কাজ পেছনের thread-এ পাঠাতে Redis 4.0 থেকে UNLINK আছে (সংস্করণভেদে)।
• সরানো আর কপি: resharding-এ বিশাল key একবারে সরাতে হয়, সেই মুহূর্তে দুই node-ই ধীর।

প্রতিকার: বড় value ভেঙে কয়েকটি key-তে রাখা; compression; collection পাতায় পাতায় পড়া (HSCAN, বা ZRANGE key 0 99-এর মতো ছোট পরিসর); ছবি বা বড় ফাইল object storage বা CDN-এ রেখে cache-এ শুধু ঠিকানা (পর্ব ২৬ — Object storage); আর নিয়মিত খোঁজা — redis-cli --bigkeys বা --memkeys (সংস্করণভেদে)। Memcached-এ একটি item-এর ডিফল্ট সীমা ১ MB (বাড়ানো যায়), Redis-এ একটি string সর্বোচ্চ ৫১২ MB — কিন্তু সীমার কাছে যাওয়াই নকশার ভুলের লক্ষণ।

৭ · বহু-স্তরের cache — browser থেকে buffer pool, আর স্তরে স্তরে staleness

একটি পড়ার অনুরোধ database-এ পৌঁছানোর আগে কয়েকটি স্তরের cache পেরোয় — একে বলে tiered caching. ওপরের স্তর ব্যবহারকারীর কাছে আর দ্রুত, কিন্তু ছোট আর কম নিয়ন্ত্রিত। Latency-গুলো মোটামুটি মাত্রা মাত্র:

ধারণাটি CPU-র L1, L2, L3-এর মতো — Computer Architecture কোর্সের multi-level cache দেখুন — তবে একটি বড় পার্থক্য আছে: CPU-র cache-গুলোকে hardware নিজেই coherent রাখে, আর আমাদের স্তরগুলোকে মেলাতে হয় নিজেদেরই। CDN-এর স্তর আছে পর্ব ১৭ — CDN আর edge-এ, gateway-র কথা পর্ব ১১ — Reverse proxy, API gateway আর BFF-এ।

সবচেয়ে খারাপ staleness = TTL-এর যোগফল

ধরুন invalidation নেই, শুধু TTL: L2-এর T₂, L1-এর T₁, CDN-এর T_c. মুহূর্ত t₀-তে database বদলাল। সবচেয়ে খারাপ ক্রম: L2 পুরোনো মানটি t₀-এর ঠিক আগে এনেছিল, তাই রাখবে t₀ + T₂ পর্যন্ত; একটি app server L2-এর মেয়াদ ফুরানোর ঠিক আগে সেটি L1-এ নিল — t₀ + T₂ + T₁ পর্যন্ত; CDN সেই app server-এর উত্তর ঠিক তখনই নিল — t₀ + T₂ + T₁ + T_c পর্যন্ত। প্রতিটি স্তর নিচের স্তরের প্রায় মেয়াদোত্তীর্ণ কপিকে নিজের পুরো TTL দেয়, তাই:

এটি ঊর্ধ্বসীমা — বাস্তবে প্রায়ই কম — কিন্তু প্রতিশ্রুতি দিতে হলে এটাই হিসাব। প্রতিটি ধরনের ডেটার জন্য আগে ঠিক করুন কতটা staleness চলে, তারপর স্তর আর TTL এমনভাবে বাছুন যাতে যোগফল সেই বাজেটে থাকে।

L1-কে মেলানো — pub/sub invalidation আর ছোট TTL একসাথে

লেখার পথ: database-এ commit → L2-এর key মোছা বা হালনাগাদ → একটি channel-এ “key X বদলেছে” বার্তা (pub/sub) → প্রতিটি app server-এর subscriber নিজের L1 থেকে X মোছে। বার্তা কয়েক ms-এ পৌঁছায়, তাই staleness নামে ms-এ। কিন্তু Redis-এর pub/sub-এর মতো অনেক ব্যবস্থা বার্তা জমিয়ে রাখে না: সেই মুহূর্তে সংযুক্ত নেই এমন subscriber (restart, network-এর ঝাঁকুনি) বার্তাটি হারায় — তত্ত্ব পর্ব ৩২ — Pub/sub আর event-driven architecture আর পর্ব ৩৪ — Delivery semantics-এ। তাই দুটোই লাগে: invalidation দ্রুততার জন্য, ছোট TTL নিরাপত্তা-জাল হিসেবে। Redis 6 থেকে server-এর সাহায্যে client-side caching-ও আছে (CLIENT TRACKING) — কোন client কোন key পড়েছে মনে রেখে বদলালে জানায় (সংস্করণভেদে)।

নিচের simulation-এ ১০টি app server, প্রতিটিতে ১০০টি key-এর L1 (LRU, TTL ২ সেকেন্ড), সবার ভাগের ৫,০০০টি key-এর L2, আর ২০,০০০টি key-এ Zipf traffic, সেকেন্ডে ১,০০০ অনুরোধ, ১২০ সেকেন্ড। ৬০ সেকেন্ডে সবচেয়ে জনপ্রিয় key বদলায়, database আর L2 সঙ্গে সঙ্গে হালনাগাদ। তিনটি অবস্থা: শুধু TTL; pub/sub (বার্তা ১ থেকে ৩১ ms পরে পৌঁছায়); আর pub/sub, কিন্তু সার্ভার ৭ তখন reconnect করছিল বলে বার্তা পায়নি।

// Two tiers: a small L1 (LRU + TTL) in each of 10 app servers, one shared L2 (LRU), then the DB.
// At t = 60 s the hottest key (key 1) changes in the DB and in L2. Who still sees the old v1?
const APPS = 10, KEYS = 20000, L1CAP = 100, L1TTL = 2, L2CAP = 5000, RPS = 1000, END = 120, TU = 60;
function sim(mode) {                      // mode: "TTL only" | "pub/sub" | "pub/sub, 1 missed"
  let seed = 7; const rand = () => {     // mulberry32, re-seeded so every mode sees the same traffic
    seed = (seed + 0x6D2B79F5) | 0; let t = Math.imul(seed ^ (seed >>> 15), 1 | seed);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
  const cum = []; let tot = 0; for (let k = 1; k <= KEYS; k++) { tot += 1 / k; cum.push(tot); }
  const zipf = () => { const x = rand() * tot; let lo = 0, hi = KEYS - 1;
    while (lo < hi) { const m = (lo + hi) >> 1; if (cum[m] < x) lo = m + 1; else hi = m; } return lo + 1; };
  const arrive = Array.from({ length: APPS }, () => TU + 0.001 + rand() * 0.03);  // 1-31 ms later
  if (mode === "pub/sub, 1 missed") arrive[7] = Infinity;      // server 7 was reconnecting
  const L1 = Array.from({ length: APPS }, () => new Map()), L2 = new Map();
  const touch = (m, k, v, cap) => {      // LRU: re-insert at the end, drop the oldest if full
    m.delete(k); m.set(k, v); if (m.size > cap) m.delete(m.keys().next().value); };
  let l1hit = 0, l2hit = 0, db = 0, stale = 0, last = 0, updated = false, got = Array(APPS).fill(false);
  for (let i = 0; i < RPS * END; i++) {
    const t = i / RPS, a = Math.floor(rand() * APPS), k = zipf();
    if (t >= TU && !updated) { updated = true; if (L2.has(1)) L2.set(1, 2); }   // the write
    if (mode !== "TTL only" && !got[a] && t >= arrive[a]) { L1[a].delete(1); got[a] = true; }
    let e = L1[a].get(k), v;
    if (e && e.exp > t) { l1hit++; v = e.v; touch(L1[a], k, e, L1CAP); }
    else {
      v = L2.get(k); if (v !== undefined) l2hit++; else { db++; v = (k === 1 && t >= TU) ? 2 : 1; }
      touch(L2, k, v, L2CAP); touch(L1[a], k, { v, exp: t + L1TTL }, L1CAP);
    }
    if (k === 1 && t >= TU && v === 1) { stale++; last = t - TU; }
  }
  const n = RPS * END, pct = (x) => (100 * x / n).toFixed(1).padStart(6) + "%";
  const col = (x, w) => String(Math.round(x)).padStart(w);
  console.log(mode.padEnd(18) + pct(l1hit) + pct(l1hit + l2hit) + col((n - l1hit) / END, 8) +
    col(db / END, 6) + col(stale, 7) + col(last * 1000, 8) + " ms");
}
console.log("mode                L1hit  total  L2 r/s  DB/s  stale  window");
["TTL only", "pub/sub", "pub/sub, 1 missed"].forEach(sim);

mode                L1hit  total  L2 r/s  DB/s  stale  window
TTL only            32.0%  79.9%     680   201    107    1426 ms
pub/sub             32.0%  79.9%     680   201      1      20 ms
pub/sub, 1 missed   32.0%  79.9%     680   201     15     893 ms

প্রতিটি স্তরের দাম

প্রতিটি নতুন স্তর memory নেয় (L1-এ একই ডেটা N গুণ), invalidation-এর আরেকটি পথ চায়, আর “কোন স্তর পুরোনো মানটি দিল?” প্রশ্নকে কঠিন করে — উত্তরে স্তরের নাম একটি header বা log-এ রাখুন। যোগ করার আগে মাপুন সেটি latency, network না database-এর চাপ কতটা কমাবে; মাপ ছাড়া স্তর প্রায়ই over-engineering.

৮ · একাধিক region — প্রতিটির নিজের cache, আর invalidation-এর ক্রম

ব্যবহারকারী কয়েকটি region-এ ছড়ানো হলে প্রতিটি region-এর নিজের cache cluster লাগে; অন্য region-এর cache পড়া মানে প্রতিবার কয়েক দশক থেকে শতাধিক ms-এর round trip. প্রচলিত নকশা: database-এর leader একটি region-এ, বাকিগুলোতে read replica, আর প্রতিটি region-এর cache ভরে কাছের replica থেকে। লেখা হলে সব region-এ invalidation পৌঁছাতে হবে — বিপদ লুকিয়ে আছে ক্রমে। নিচে region B-র replica ৩০০ ms পিছিয়ে, আর invalidation সরাসরি broadcast:

মোছা পৌঁছেছে ডেটার আগে, তাই cache আবার পুরোনো মানে ভরল। প্রতিকার: প্রতিটি region-এ invalidation চালাক সেই region-এর replication stream — replica পরিবর্তনটি প্রয়োগ করার পরেই একটি process সেই region-এর cache থেকে key মোছে (change data capture), ফলে মোছা কখনো ডেটার আগে পৌঁছায় না। Facebook-এর memcache paper অনুযায়ী তাঁরা MySQL-এর commit log পড়া একটি daemon (mcsqueal) দিয়ে প্রতিটি region-এ এভাবেই delete পাঠাতেন। আরও দুটি সহায়ক কৌশল: মানের সাথে version নম্বর রাখা আর পুরোনো version দিয়ে নতুনটিকে ঢাকতে না দেওয়া; আর লেখার ঠিক পরে ব্যবহারকারীর নিজের পড়া leader থেকে আনা (read-your-writes, পর্ব ২২)। পুরো region বিকল হলে অন্য region-এর cache-এ হঠাৎ দ্বিগুণ traffic, সেখানে ঠান্ডা key — traffic ধীরে সরানোর পরিকল্পনা পর্ব ৫১ — Failover আর disaster recovery — backup, RPO-RTO আর multi-region-এ।

৯ · Memcached বনাম Redis, আর চালানোর খুঁটিনাটি

দুটিই in-memory key-value store, কিন্তু distributed cache হিসেবে তাদের চরিত্র আলাদা। নিচের তুলনা লেখার সময়ের অবস্থা; সংস্করণ আর distribution-ভেদে বদলায়, তাই সিদ্ধান্তের আগে অফিসিয়াল documentation দেখুন। ২০২৪-এর লাইসেন্স বদল আর Valkey fork-এর কথা DBMS কোর্সের Redis পর্বে।

চালানোর পাঁচ অভ্যাস

• Connection pool: প্রতিটি app process প্রতিটি node-এর সাথে কয়েকটি স্থায়ী connection রাখে (connection pool), তাই প্রতিবার নতুন TCP বা TLS handshake লাগে না। হিসাব রাখুন: ২০০টি app process × প্রতি node-এ ৮টি = প্রতিটি node-এ ১,৬০০টি connection, ১২টি node-এ মোট ১৯,২০০; app দ্বিগুণ হলে connection-ও। Proxy বা multiplexing এই সংখ্যা কমায়।
• Timeout — ধীর cache মৃত cache-এর চেয়ে খারাপ: cache-এর p99 সাধারণত ১ ms-এর আশেপাশে। Client-এর timeout ১ সেকেন্ড হলে একটি অসুস্থ node প্রতিটি অনুরোধকে ১ সেকেন্ড আটকায়, thread ফুরিয়ে যায়; মরে গেলে অন্তত সঙ্গে সঙ্গে ত্রুটি আসত। তাই ছোট timeout (কয়েক থেকে কয়েক দশক ms), node-ভিত্তিক circuit breaker (পর্ব ৪৮ — Resilience pattern), আর database-এ fallback সীমিত হারে; সীমার বাইরের অনুরোধ fail fast বা পুরোনো মান পায় (পর্ব ১৮ — Overload সামলানো)।
• Eviction আর hit ratio-র নজর: সেকেন্ডে কত key evict হচ্ছে, hit ratio, ব্যবহৃত memory বনাম সীমা, প্রতি shard-এর অনুরোধ ও network. Eviction হঠাৎ বাড়া মানে working set বেড়েছে বা একটি big key ঢুকেছে; hit ratio এক ধাপ নামলেই database-এর চাপ লাফায়।
• Memory fragmentation: নানা মাপের value বারবার লেখা-মোছায় RAM-এ ছোট ছোট ফাঁক তৈরি হয়, তাই process ডেটার চেয়ে বেশি RAM ধরে রাখে — একে বলে memory fragmentation. Redis-এর INFO memory-তে mem_fragmentation_ratio দেখুন; বেশি হলে active defrag বা পরিকল্পিত restart. Memcached-এ ভিন্ন রূপ: পুরোনো traffic অনুযায়ী slab-এর ভাগ আটকে থাকা। কোন অনুপাত “বেশি”, তা সংস্করণ আর workload-ভেদে।
• নিরাপত্তা: cache কখনো ইন্টারনেটে খোলা নয় — private network, password বা ACL, দরকারে TLS.

# Illustrative only: a Redis node used purely as a cache. Check your version's docs.
maxmemory 44gb                  # leave headroom below the machine's RAM
maxmemory-policy allkeys-lfu    # evict any key, least frequently used first
save ""                         # no RDB snapshots: the database is the source of truth
appendonly no                   # no AOF either
lazyfree-lazy-eviction yes      # free evicted memory in a background thread
activedefrag yes                # background defragmentation (jemalloc builds)

১০ · AI-এর যুগে — distributed cache-এর নকশা যাচাই

“সাইট ধীর, কী করব?” — AI প্রায় সবসময় বলে, “Redis cluster বসান।” পরামর্শটি ভুল নয়, কিন্তু অসম্পূর্ণ; distributed cache-এ AI-এর ভুলগুলো বেশ নির্দিষ্ট:

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

• Item-সংখ্যা, overhead, headroom আর কপি ধরে memory-র হিসাব নিজে আবার করেছি; throughput আর network-ও দেখেছি
• একটি node বিকল হলে database-এর চাপ 1 + h/(N(1 − h)) দিয়ে হিসাব করে database-এর ক্ষমতার সাথে মিলিয়েছি
• Fallback-এর সীমা, timeout আর gutter বা replica-র পরিকল্পনা লেখা আছে — “ধীর cache” অবস্থাটিও ভেবেছি
• Hot key আর big key-এর detection ও প্রতিকার আছে; ছোট একটি simulation বা load test-এ যাচাই করেছি
• প্রতিটি ডেটার staleness-এর বাজেট আর স্তরগুলোর TTL-এর যোগফল মিলিয়েছি; invalidation হারালে কী হবে, ভেবেছি
• প্রতিটি product-এর সীমা ও ডিফল্ট অফিসিয়াল documentation-এ মিলিয়েছি