Probabilistic data structure — Bloom filter, count-min sketch আর HyperLogLog

১ · নির্ভুলতার বদলে memory — কেন আনুমানিক উত্তর

বইমেলার একটি গেটের কথা ভাবুন। আয়োজকেরা জানতে চান, আজ কতজন আলাদা মানুষ এলেন — কেউ তিনবার ঢুকলেও একবার গোনা। নিখুঁত উপায় একটিই: প্রত্যেকের পরিচয় খাতায় লেখা, আর নতুন কেউ এলে পুরো খাতায় খোঁজা। এখন খাতাটিকে একটি সার্ভারের memory ভাবুন, আর মানুষগুলোকে একটি অ্যাপের কোটি কোটি ব্যবহারকারী — প্রতিটি পাতা আর প্রতিটি দিনের জন্য আলাদা খাতা।

বড় সিস্টেমে তিন ধরনের প্রশ্ন বারবার আসে, আর তিনটিরই নিখুঁত উত্তরে প্রতিটি আলাদা জিনিস মনে রাখতে হয়:

একটি হিসাব করে দেখুন (পর্ব ৩-এর মতো)। ধরা যাক একটি কাল্পনিক ভিডিও অ্যাপে এক মাসে প্রায় ১০০ কোটি আলাদা device id, প্রতিটি 64-bit বা ৮ byte — শুধু id-গুলোই ৮ GB, hash set-এর pointer, খালি ঘর আর metadata মিলিয়ে মোটামুটি ২০ GB-এর ঘরে। এটি একটি প্রশ্নের জন্য; “প্রতিটি ভিডিওর প্রতিদিনের আলাদা দর্শক” চাইলে লাখো ভিডিও × ৩০ দিন — অসম্ভব। অথচ dashboard-এ “৪৮.৩ লাখ” আর “৪৮.৭ লাখ”-এর ফারাক কারও সিদ্ধান্ত বদলায় না। HyperLogLog প্রতিটি গণনায় প্রায় ১২ KB নেয়, ভুল সাধারণত এক শতাংশের নিচে।

এই পর্বের কাঠামোগুলোকে বলে probabilistic data structure; ছোট সারাংশ রাখে বলে অনেকে বলেন sketch. তিনটি বৈশিষ্ট্য এদের আলাদা করে:

• Memory আগে থেকে ঠিক করা: আকার ঠিক হয় কত ভুল মেনে নেবেন তা দিয়ে, কত key আসবে তা দিয়ে নয়।
• ভুলের ধরন আর মাত্রা জানা: “কখনো ভুল ‘নেই’ বলবে না”, “কখনো কম দেখাবে না” — গণিতে প্রমাণিত প্রতিশ্রুতি।
• মেলানো যায় (mergeable): প্রতিটি সার্ভার বা partition নিজের sketch রাখে, পরে মিলিয়ে পুরো ডেটার sketch.

এই কাঠামোগুলো আগে কয়েকবার এসেছে: LSM-tree-এর প্রতিটি SSTable-এর সাথে Bloom filter (পর্ব ১৯), অস্তিত্বহীন key-এর ঢল ঠেকাতে Bloom filter (পর্ব ২৮, পর্ব ২৯), W-TinyLFU-এর ভেতরের count-min sketch (পর্ব ২৯), hot key খোঁজা (পর্ব ৩০), আর stream-এ আলাদা ব্যবহারকারী গোনা (পর্ব ৩৬)। এবার ভেতরটা খোলা যাক।

২ · ভিত্তি hashing — ভালো hash, seed আর double hashing

তিনটি কাঠামোর প্রাণ একটিই: hash function. Hash table-এর মূল কথা — hash কী, collision কেন অনিবার্য, birthday paradox — DSA কোর্সের Hash table পর্বে বিস্তারিত আছে; সেখানে Bloom filter-এর সংক্ষিপ্ত পরিচয়ও আছে। এখানে শুধু সেই শর্তগুলো, যা sketch-এর গণিতকে সত্য রাখে:

• Deterministic: একই ইনপুটে সবসময় একই ফল — অন্য সার্ভারে, অন্য সংস্করণেও। এই কারণেই HyperLogLog একই id দুবার গোনে না।
• Uniform: প্রমাণে ধরা হয় প্রতিটি ঘর পড়ার সম্ভাবনা 1/m; hash বাঁকা হলে প্রমাণ খাটে না।
• প্রায় স্বাধীন: Bloom filter-এর k টি hash বা count-min-এর d টি সারি সম্পর্কহীন হতে হবে; নইলে k টি hash আসলে একটি।
• দ্রুত, ক্রিপ্টোগ্রাফিক নয়: প্রতি ঘটনায় কয়েকবার hash হয়, তাই MurmurHash বা xxHash-এর মতো দ্রুত hash চলে।

এই পর্বের simulator-গুলোর hash সরল ও পরিচিত: FNV-1a 32-bit (পর্ব ১৬), তারপর MurmurHash3-এর শেষ ধাপ fmix32 — কারণ শুধু FNV-1a-তে প্রায় একই রকম string-এর (user:1, user:2…) ওপরের bit যথেষ্ট মেশে না, আর HyperLogLog ঠিক ওপরের bit-ই দেখে। একটি seed বদলালে একই function থেকে নতুন একটি “স্বাধীন” hash পাওয়া যায়।

Double hashing — দুটি hash থেকে k টি

৭টি বা ১০টি আলাদা hash প্রতিবার হিসাব করা ব্যয়বহুল। Adam Kirsch ও Michael Mitzenmacher ২০০৬ সালে (ESA সম্মেলনে, “Less Hashing, Same Performance”) দেখান, মাত্র দুটি hash থেকে বানানো অবস্থানগুলোও যথেষ্ট:

তাঁদের বিশ্লেষণ অনুযায়ী, বড় m-এ এভাবে double hashing করলে Bloom filter-এর false-positive হার প্রায় k টি সত্যিকারের স্বাধীন hash-এর সমান থাকে। বাস্তবে অনেক লাইব্রেরি একটি 64-bit বা 128-bit hash বানিয়ে তার দুই অর্ধেককে h₁ আর h₂ হিসেবে নেয়। একটি ছোট সতর্কতা: h₂ শূন্য হলে k টি অবস্থানই এক হয়ে যায়, তাই কোডে h₂-কে বিজোড় করা হয়েছে।

৩ · Bloom filter — bit array, k টি hash আর “নিশ্চিত নেই”

১৯৭০ সালে Burton H. Bloom Communications of the ACM-এ এই কাঠামোটি প্রকাশ করেন। Bloom filter-এর উপকরণ দুটি: m টি ঘরের একটি bit array, শুরুতে সব 0; আর k টি hash, প্রতিটি একটি key থেকে 0 থেকে m − 1-এর একটি ঘর দেয়।

• Insert(x): k টি hash-এর প্রতিটি ঘরে bit 1 করা। আগে থেকে 1 থাকলে 1-ই থাকে।
• Lookup(x): k টি ঘর দেখা। কোনো একটি 0 হলে উত্তর “নিশ্চিত নেই”; সবগুলো 1 হলে “হয়তো আছে”।

কেন “নিশ্চিত নেই” সবসময় সত্য? x ঢোকানোর সময় তার k টি ঘর 1 হয়েছিল, আর কোনো কাজ কখনো bit-কে 0 করে না — তাই false negative অসম্ভব। কিন্তু না-ঢোকানো একটি key-এর k টি ঘর অন্যরা মিলে ভরিয়ে ফেলতে পারে — সেটিই false positive, যেমন নিচের ছবিতে:

এবার একই ঘটনা ধাপে ধাপে দেখুন — দুটি insert, তারপর তিন রকম lookup:

তিনটি জিনিস Bloom filter পারে না। Delete: রাজশাহীকে ঢুকিয়ে আবার মুছতে ঘর ১, ৩, ১০ শূন্য করলে ঢাকা আর খুলনার ঘরও মোছে — তারা false negative পায়। তালিকা: ভেতরে কোন key আছে, বলা যায় না। Range: bit-গুলো এলোমেলো ঘরে, তাই “১০০ থেকে ২০০-এর মধ্যে কেউ আছে?”-র উত্তর নেই।

একটি সুবিধাও আছে: একই m, k আর hash-এর দুটি filter-এর bit-OR নিলে ঠিক দুই set-এর মিলিত filter পাওয়া যায় — Bloom filter-ও মেলানো যায়।

৪ · Bloom filter-এর গণিত — false-positive হার, সেরা k আর প্রতি key-এ কত bit

পরীক্ষা আর ইন্টারভিউতে প্রমাণটি প্রায়ই চাওয়া হয়। ধরে নিন hash-গুলো uniform আর স্বাধীন; n টি key ঢোকানো হয়েছে, m টি bit, k টি hash.

1. একটি নির্দিষ্ট bit একটি hash-এ 1 না হওয়ার সম্ভাবনা 1 − 1/m.
2. মোট kn বার hash হয়েছে। সববার সেই bit বাদ পড়ার সম্ভাবনা (1 − 1/m)^kn ≈ e^−kn/m, কারণ বড় m-এ (1 − 1/m)^m ≈ 1/e.
3. তাই যেকোনো bit 1 হওয়ার সম্ভাবনা, অর্থাৎ ভরা ঘরের অনুপাত, প্রায় 1 − e^−kn/m.
4. একটি না-ঢোকানো key-এর k টি ঘরের সবগুলো 1 হলে তবেই false positive. ঘরগুলোকে প্রায় স্বাধীন ধরলে:

এখানে একটি টানাপোড়েন আছে। k বাড়ালে প্রতিটি lookup বেশি ঘর পরীক্ষা করে — একটি 0 পাওয়ার সুযোগ বাড়ে, ভালো। কিন্তু প্রতিটি insert-ও বেশি ঘর ভরায় — filter দ্রুত 1-এ ভরে, খারাপ। মাঝখানে একটি সেরা k আছে। p-কে k-এর সাপেক্ষে ন্যূনতম করলে (ln p-এর অবকলন শূন্য ধরে, প্রতিসাম্য থেকে) পাওয়া যায়:

সুন্দর একটি ফল: সেরা অবস্থায় ঠিক অর্ধেক bit 1 — প্রতিটি bit সর্বোচ্চ তথ্য বহন করে, যেমন একটি ন্যায্য মুদ্রার টস। এবার উল্টো দিক থেকে — লক্ষ্য p দেওয়া থাকলে কত memory লাগবে? k_opt বসিয়ে সমাধান করলে:

মনে রাখার নিয়ম: ভুল ১০ গুণ কমাতে প্রতি key-এ প্রায় ৪.৮ bit বেশি, আর key-এর আকার ভূমিকা রাখে না — ১০ byte-এর id আর ২০০ byte-এর URL, দুটোরই ৯.৬ bit. এবার মেপে দেখুন: নিচের simulator ১০,০০০টি key ঢোকায় (m = ১,০০,০০০, প্রতি key-এ ১০ bit), তারপর ১,০০,০০০টি কখনো-না-ঢোকানো key দিয়ে false positive গোনে, ছয়টি k-এর জন্য — আর প্রতিবার ঢোকানো সব key আবার যাচাই করে, false negative শূন্য কি না।

// Bloom filter: measured false-positive rate vs the formula (1 - e^(-kn/m))^k.
function rng(seed) {                                    // mulberry32: seeded, repeatable
  return () => { 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; };
}
function hash32(s, seed) {                              // FNV-1a 32-bit + murmur3 fmix32 finaliser
  let h = (0x811c9dc5 ^ seed) >>> 0;
  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;
}
const n = 10000, m = 100000, rand = rng(45);            // 10 bits per element
const members = [], strangers = [];
for (let i = 0; i < n; i++) members.push("user:" + Math.floor(rand() * 1e9));
for (let i = 0; i < 100000; i++) strangers.push("guest:" + i);   // never inserted
const hh = (s) => [hash32(s, 1), (hash32(s, 2) | 1) >>> 0];  // two hashes -> k positions (double hashing)
const H = members.map(hh), G = strangers.map(hh);
console.log(" k   measured FP   formula   members missed");
for (const k of [1, 2, 4, 7, 10, 14]) {
  const bits = new Uint8Array(m);
  for (const [a, b] of H) for (let i = 0; i < k; i++) bits[(a + i * b) % m] = 1;
  let missed = 0, fp = 0;
  for (const [a, b] of H) for (let i = 0; i < k; i++) if (!bits[(a + i * b) % m]) { missed++; break; }
  for (const [a, b] of G) { let all = true;
    for (let i = 0; i < k && all; i++) all = bits[(a + i * b) % m] === 1;
    if (all) fp++; }
  const f = (1 - Math.exp(-k * n / m)) ** k;
  console.log(String(k).padStart(2) + (fp / G.length * 100).toFixed(3).padStart(12) + "%" +
    (f * 100).toFixed(3).padStart(9) + "%" + String(missed).padStart(10));
}
console.log(`\nm/n = ${m / n}: optimal k = (m/n) ln 2 = ${(m / n * Math.LN2).toFixed(2)}`);
for (const p of [0.01, 0.001]) {
  const bpe = -Math.log(p) / Math.LN2 ** 2;
  console.log(`target ${p * 100}%: ${bpe.toFixed(2)} bits per element, k = ${(bpe * Math.LN2).toFixed(2)} -> use ${Math.round(bpe * Math.LN2)}`);
}

 k   measured FP   formula   members missed
 1       9.521%    9.516%         0
 2       3.370%    3.286%         0
 4       1.203%    1.181%         0
 7       0.853%    0.819%         0
10       1.054%    1.019%         0
14       1.851%    1.898%         0

m/n = 10: optimal k = (m/n) ln 2 = 6.93
target 1%: 9.59 bits per element, k = 6.64 -> use 7
target 0.1%: 14.38 bits per element, k = 9.97 -> use 10

৫ · রূপভেদ আর বাস্তব ব্যবহার — counting, cuckoo আর কোথায় বসে

Delete লাগলে — counting Bloom filter আর cuckoo filter

Counting Bloom filter-এ প্রতিটি ঘরে bit-এর বদলে ছোট counter — insert-এ k টি counter বাড়ে, delete-এ কমে। ধারণাটি জনপ্রিয় হয় Fan, Cao, Almeida ও Broder-এর “Summary Cache” গবেষণায় (১৯৯৮ সালে সম্মেলনে, ২০০০ সালে জার্নালে), যেখানে web proxy-গুলো একে অপরের cache-এর সারাংশ বিনিময় করত; ৪-bit counter প্রায় সবসময় যথেষ্ট ছিল — তাতেই memory চার গুণ। ফাঁদ: কখনো না-ঢোকানো কিছু “delete” করলে অন্যের counter কমে, false negative ফিরে আসে।

Cuckoo filter (Fan, Andersen, Kaminsky ও Mitzenmacher, CoNEXT ২০১৪) প্রতিটি key-এর ছোট একটি fingerprint দুটি সম্ভাব্য bucket-এর একটিতে রাখে; জায়গা না থাকলে পুরোনো কাউকে তার বিকল্প bucket-এ সরায় — কোকিলের মতো, যে অন্যের বাসায় ডিম রাখে। Delete-ও চলে। প্রবন্ধের মাপ অনুযায়ী কম ভুলের হারে (মোটামুটি ৩%-এর নিচে) এটি প্রায়ই Bloom filter-এর চেয়ে কম জায়গা নেয়; দাম — প্রায় ভরা হলে insert ব্যর্থ হতে পারে, খুঁটিনাটি বাস্তবায়নভেদে আলাদা।

কোথায় বসে — চারটি প্রচলিত ব্যবহার

• LSM-tree-এ অকারণ disk-পড়া বাদ: প্রতিটি SSTable-এর সাথে একটি filter; অনুপস্থিত key-এর জন্য ১০টি SSTable-এ ১০টি disk-পড়ার বদলে ১% filter-এ গড়ে প্রায় ০.১টি। কাঠামো আর read amplification-এর হিসাব পর্ব ১৯-এ আছে; এখানে শুধু মনে রাখুন, সেই “প্রতি key-এ ১০ bit-এ প্রায় ০.৮%” ঠিক ওপরের simulator-এর k = 7-এর সারি।
• Cache-এ “one-hit wonder” ছাঁকা: বড় cache-এ অনেক object জীবনে একবারই চাওয়া হয়, আর প্রথমবারেই রাখলে তারা জনপ্রিয়দের বের করে দেয়। কৌশল: প্রথম অনুরোধে শুধু Bloom filter-এ লিখুন, দ্বিতীয়বার এলে তবেই cache-এ রাখুন; false positive মানে একটি object আগেভাগে ঢুকল — সামান্য ক্ষতি। একটি বড় CDN-এর প্রকাশিত গবেষণাপত্রে (Maggs ও Sitaraman, ২০১৫) এই কৌশলের বর্ণনা আছে। এটি একটি admission policy, W-TinyLFU-এর (পর্ব ২৯) আত্মীয়।
• Web crawler-এর “দেখা URL”: ১০০ কোটি URL-এর set, গড়ে ধরা যাক ১০০ byte করে, শুধু string-এই প্রায় ১০০ GB. ০.১%-এর Bloom filter-এ প্রায় ১.৮ GB, একটি মেশিনের RAM-এ আঁটে। False positive মানে একটি নতুন পাতা “আগে দেখেছি” ভেবে বাদ — হাজারে একটি পাতা হারানো সাধারণত মেনে নেওয়া যায়, প্রতিটি পাতা দুবার নামানো নয়। Crawler-এর পুরো নকশা আসবে পর্ব ৬৬-এর mock interview-তে।
• Device-এ স্থানীয় প্রাথমিক যাচাই: কিছু ব্রাউজারের ক্ষতিকর-সাইট সতর্কতার মতো ব্যবস্থায় device বিপজ্জনক URL-এর hash-অংশের একটি সংক্ষিপ্ত তালিকা রাখে, Bloom filter বা তার মতো কাঠামোয়। “নিশ্চিত নেই” হলে সাইট সঙ্গে সঙ্গে খোলে; “হয়তো আছে” হলে তবেই সার্ভারে পূর্ণ যাচাই। বেশিরভাগ পাতায় দেরি শূন্য, আর বেশিরভাগ URL device ছেড়ে যায় না — গোপনীয়তার দিক থেকেও ভালো।

একই ছাঁচ আরও জায়গায়: অস্তিত্বহীন id-এর ঢল (cache penetration) ঠেকানো (পর্ব ২৮); distributed join-এ এক পাশের key-এর filter অন্য পাশে পাঠিয়ে না-মেলা সারি আগেই বাদ (join-এর কৌশলগুলো পর্ব ৩৬-এ); URL shortener-এ নতুন short code-এর দ্রুত যাচাই (পর্ব ৫৪); news feed-এ “আগে দেখানো পোস্ট” (পর্ব ৫৬)।

৬ · Count-min sketch — কতবার এল, কম memory-তে

Graham Cormode ও S. Muthukrishnan ২০০৪ সালে (LATIN সম্মেলনে; পূর্ণ রূপ Journal of Algorithms, ২০০৫) count-min sketch প্রকাশ করেন। গঠন: d টি সারি, প্রতিটিতে w টি counter, আর প্রতিটি সারির নিজস্ব hash.

• Update(x, c): প্রতিটি সারি i-তে ঘর h_i(x)-এর counter c বাড়ানো (সাধারণত c = 1).
• Query(x): d টি ঘরের counter-এর সর্বনিম্ন।

প্রতিটি ঘরে x-এর নিজের গণনা, সাথে collision-এ পড়া অন্যদের; শুধু যোগ হয়, তাই প্রতিটি ঘর ≥ আসল, সর্বনিম্নটিও — কখনো কম দেখায় না। N মোট ঘটনা হলে:

প্রমাণের ছক: একটি সারিতে x-এর ঘরে অন্য প্রতিটি key পড়ার সম্ভাবনা 1/w (pairwise স্বাধীন hash ধরে), তাই বাড়তির প্রত্যাশিত মান ≤ N/w = ε·N/e. Markov-এর অসমতায় বাড়তি ε·N ছাড়ানোর সম্ভাবনা ≤ 1/e; সর্বনিম্নটি খারাপ হবে শুধু d টি সারিই খারাপ হলে: ≤ (1/e)^d = δ. যেমন ε = ০.০০১, δ = ০.০১-এ w = ২,৭১৯, d = ৫ — ১৩,৫৯৫টি counter, ৪ byte করে প্রায় ৫৪ KB, আলাদা key যতই আসুক।

নিচের stepper-এ ছোট একটি sketch (d = 3, w = 6) চারটি ঘটনা আর দুটি query নেয়; সাথে একটি heap সেরা ২টি key ধরে রাখে (ব্যাখ্যা পরে)।

এবার বড় পরিসরে: একটি কাল্পনিক গানের অ্যাপের ২,০০,০০০টি play, জনপ্রিয়তা Zipf-ধাঁচের (r-তম গানের ওজন 1/r, ৫০,০০০টি গান থেকে), ε = ০.০০১, δ = ০.০১. কয়েকটি গানের আসল আর আনুমানিক গণনা, তারপর সবচেয়ে বেশি ভুল বনাম ε·N:

// Count-min sketch over a Zipf-like stream: true vs estimated counts, and the eps*N bound.
function rng(seed) {                                    // mulberry32: seeded, repeatable
  return () => { 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; };
}
function hash32(s, seed) {                              // FNV-1a 32-bit + murmur3 fmix32 finaliser
  let h = (0x811c9dc5 ^ seed) >>> 0;
  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;
}
const K = 50000, N = 200000, eps = 0.001, delta = 0.01, rand = rng(45);
const w = Math.ceil(Math.E / eps), d = Math.ceil(Math.log(1 / delta));
const cdf = []; let acc = 0;                            // Zipf: rank r chosen with weight 1/r
for (let r = 1; r <= K; r++) { acc += 1 / r; cdf.push(acc); }
const table = Array.from({ length: d }, () => new Uint32Array(w)), truth = new Map();
for (let e = 0; e < N; e++) {
  const x = rand() * acc; let lo = 0, hi = K - 1;
  while (lo < hi) { const mid = (lo + hi) >> 1; if (cdf[mid] < x) lo = mid + 1; else hi = mid; }
  const key = "song:" + (lo + 1);
  truth.set(key, (truth.get(key) || 0) + 1);
  for (let i = 0; i < d; i++) table[i][hash32(key, i + 1) % w]++;   // update: +1 in every row
}
const est = (key) => Math.min(...table.map((row, i) => row[hash32(key, i + 1) % w]));  // query: min
console.log(`w = ${w}, d = ${d}, counters = ${w * d}, distinct keys seen = ${truth.size}`);
console.log("key          true   estimate");
for (const r of [1, 2, 3, 10, 100, 1000]) {
  const key = "song:" + r;
  console.log(key.padEnd(11) + String(truth.get(key) || 0).padStart(6) + String(est(key)).padStart(10));
}
let worst = 0, over = 0, exact = 0;
for (const [key, c] of truth) { const err = est(key) - c;
  worst = Math.max(worst, err); if (err > eps * N) over++; if (err === 0) exact++; }
console.log(`\nbound eps*N = ${eps * N}; worst overestimate = ${worst}; keys above bound = ${over} of ${truth.size}`);
console.log(`keys estimated exactly = ${exact}; never an underestimate (min over rows)`);

w = 2719, d = 5, counters = 13595, distinct keys seen = 28633
key          true   estimate
song:1      17527     17549
song:2       8842      8863
song:3       5822      5844
song:10      1774      1803
song:100      183       193
song:1000      29        41

bound eps*N = 200; worst overestimate = 71; keys above bound = 0 of 28633
keys estimated exactly = 4; never an underestimate (min over rows)

Heavy hitters আর top-k — sketch-এর সাথে একটি heap

“আজ সবচেয়ে বেশি চালানো ১০টি গান”, “কোন key একটি cache shard-কে গরম করছে” — এগুলো heavy hitters সমস্যা। Count-min sketch key-এর নাম মনে রাখে না, তাই সাথে রাখা হয় k আকারের একটি min-heap (গঠন DSA কোর্সের Heap পর্বে): প্রতিটি ঘটনায় sketch হালনাগাদ, তারপর সেই key-এর অনুমান; key heap-এ থাকলে মান হালনাগাদ, না থাকলে অনুমান heap-এর মাথার (সবচেয়ে ছোট) চেয়ে বড় হলে মাথাটি সরিয়ে নতুনটি। খরচ প্রতি ঘটনায় O(d + log k). এভাবে পাওয়া top-k তালিকা hot key সামলানো (পর্ব ৩০, পর্ব ২৩) আর trending শব্দের (পর্ব ২৭) ভিত্তি।

দুটি উন্নতি প্রচলিত। Conservative update (Estan ও Varghese, ২০০২): শুধু সেই counter-গুলো বাড়ানো, যেগুলো নতুন অনুমানের চেয়ে ছোট — বাড়তি গণনা অনেক কমে, তবে বিয়োগ আর চলে না। আর পুরোনো জনপ্রিয়তা ভোলাতে মাঝে মাঝে সব counter অর্ধেক করা — W-TinyLFU-এর aging (পর্ব ২৯)। মেলানোও সহজ: একই d, w আর hash-এর দুটি sketch ঘর ধরে যোগ করলেই মিলিত ধারার sketch.

৭ · HyperLogLog — কতজন আলাদা, ১২ KB-তে

একটি ভালো hash-এর প্রতিটি bit যেন একটি ন্যায্য টস। একটি hash ঠিক r টি শূন্য দিয়ে শুরু হওয়ার সম্ভাবনা 2^−(r+1), আর অন্তত r টি শূন্যের সম্ভাবনা 2^−r. তাই n টি আলাদা key-এর hash দেখলে শুরুর শূন্যের সর্বোচ্চ সংখ্যা মোটামুটি log₂ n-এর কাছে থাকে। আর একই key আবার এলে hash একই, শূন্যও একই — সর্বোচ্চ বদলায় না। Duplicate আপনাআপনি বাদ পড়ে, তাই কাঠামোটি গোনে শুধু আলাদা key.

একটি সর্বোচ্চ দিয়ে আন্দাজ খুব নড়বড়ে — একটি ভাগ্যবান hash ফল দ্বিগুণ করে দেয়। সমাধান: hash-এর প্রথম p টি bit দিয়ে key-গুলোকে m = 2^p টি দলে ভাগ; প্রতিটি দলের একটি register মনে রাখে বাকি bit-এ সর্বোচ্চ ρ (শুরুর শূন্য + ১)। শেষে register-গুলো মেলানো হয় harmonic mean দিয়ে, যা ব্যতিক্রমী বড় মানে কম টলে:

ইতিহাস ধাপে ধাপে: Flajolet ও Martin-এর probabilistic counting (১৯৮৫), Durand ও Flajolet-এর LogLog (২০০৩, register-এর সাধারণ গড়), আর ২০০৭ সালে Flajolet, Fusy, Gandouet ও Meunier-এর HyperLogLog — harmonic mean, ভুল প্রায় 1.04/√m. Google-এর Heule, Nunkesser ও Hall ২০১৩ সালে HyperLogLog++ প্রকাশ করেন: 64-bit hash, ছোট গণনায় ভুলের বাঁক (bias) সংশোধন, আর অল্প key-এ sparse রূপ।

নিচের stepper-এ p = 4 (১৬টি register) নিয়ে একটি key-এর register হালনাগাদ দেখুন। Hash-এর bit-গুলো এই পর্বের simulator-এর hash থেকে সত্যিকারের হিসাব করা।

ছোট আর বড় গণনার সংশোধন

অল্প key-এ অনেক register শূন্য থাকে আর মূল সূত্র বাঁকা ফল দেয়; তাই E ≤ 2.5m হলে আর শূন্য register থাকলে linear counting: E = m · ln(m ÷ V), V = শূন্য register-এর সংখ্যা। খুব বড় গণনায় 32-bit hash-এর নিজের collision-এর জন্য মূল প্রবন্ধে আলাদা সংশোধন আছে; 64-bit hash নিলে সমস্যাটি কার্যত চলে যায়।

Memory আর নির্ভুলতা

64-bit hash-এ ρ সর্বোচ্চ ৬৪-এর কাছে, তাই প্রতি register-এ ৬ bit যথেষ্ট:

নিয়ম: memory ৪ গুণ করলে ভুল অর্ধেক (√m-এর কারণে)। আর memory গণনার আকারের ওপর প্রায় নির্ভর করে না — ১০ হাজার আর ১০০ কোটি, দুটোর জন্যই একই ১২ KB. Standard error মানে সর্বোচ্চ ভুল নয়: ভুলের বণ্টন মোটামুটি normal ধরলে প্রায় ৬৮% ক্ষেত্রে ভুল ±১ standard error-এর মধ্যে, প্রায় ৯৫% ক্ষেত্রে ±২-এর মধ্যে।

এখন মেপে দেখুন: p = 10 আর p = 14-এর sketch-এ ১০ হাজার, ১ লাখ আর ১০ লাখ আলাদা id, তারপর merge — A-তে id ০ থেকে ৫,৯৯,৯৯৯, B-তে ৪,০০,০০০ থেকে ৯,৯৯,৯৯৯, মিলিত আলাদা id ঠিক ১০ লাখ। সরলতার জন্য কোডে প্রতি register-এ এক byte; বাস্তব ব্যবস্থা ৬ bit-এ ঠাসে।

// HyperLogLog: estimate distinct counts with 2^p registers, then merge two sketches.
function rng(seed) {                                    // mulberry32: seeded, repeatable
  return () => { 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; };
}
function hash32(s) {                                    // FNV-1a 32-bit + murmur3 fmix32 finaliser
  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;
}
const salt = Math.floor(rng(451)() * 1e9);               // seeded prefix: ids "salt:i" are all distinct
const sketch = (p) => ({ p, reg: new Uint8Array(1 << p) });
function add(S, h) { const idx = h >>> (32 - S.p);    // first p bits choose the register
  const rho = Math.min(Math.clz32((h << S.p) >>> 0), 32 - S.p) + 1;  // leading zeros of the rest + 1
  if (rho > S.reg[idx]) S.reg[idx] = rho;               // register keeps the maximum
}
function count(S) {
  const m = S.reg.length; let sum = 0, zeros = 0; for (const r of S.reg) { sum += 2 ** -r; if (r === 0) zeros++; }
  const E = (0.7213 / (1 + 1.079 / m)) * m * m / sum;   // alpha_m * m^2 / sum(2^-M[j]) (harmonic mean)
  return E <= 2.5 * m && zeros > 0 ? m * Math.log(m / zeros) : E;  // small-range: linear counting
}
const fill = (lo, hi, ...S) => { for (let i = lo; i < hi; i++) { const h = hash32(salt + ":" + i); for (const s of S) add(s, h); } };
const pct = (e, t) => ((e - t) / t * 100).toFixed(2).padStart(7) + "%";
console.log("distinct     p=10 (m=1024)          p=14 (m=16384)");
for (const N of [10000, 100000, 1000000]) {
  const a = sketch(10), b = sketch(14); fill(0, N, a, b);
  console.log(String(N).padStart(8) + String(Math.round(count(a))).padStart(10) + pct(count(a), N) +
    String(Math.round(count(b))).padStart(12) + pct(count(b), N));
}
console.log(`theory: 1.04/sqrt(m) = ${(104 / 32).toFixed(2)}% (p=10), ${(104 / 128).toFixed(2)}% (p=14)`);
const A = sketch(14), B = sketch(14); fill(0, 600000, A); fill(400000, 1000000, B);   // overlap 200k
const U = sketch(14); U.reg = A.reg.map((r, j) => Math.max(r, B.reg[j]));           // merge = max
console.log(`\nA ~ ${Math.round(count(A))} (true 600000), B ~ ${Math.round(count(B))} (true 600000)`);
console.log(`merged A u B ~ ${Math.round(count(U))} (true 1000000), error ${pct(count(U), 1e6).trim()}`);

distinct     p=10 (m=1024)          p=14 (m=16384)
   10000     10120   1.20%       10067   0.67%
  100000     96156  -3.84%       99248  -0.75%
 1000000   1041952   4.20%     1001281   0.13%
theory: 1.04/sqrt(m) = 3.25% (p=10), 0.81% (p=14)

A ~ 602261 (true 600000), B ~ 606201 (true 600000)
merged A u B ~ 1001281 (true 1000000), error 0.13%

Merge — distributed গণনার আসল শক্তি

এই মেলানোর ক্ষমতাই HyperLogLog-কে distributed সিস্টেমে অপরিহার্য করেছে। প্রতিটি সার্ভার, partition বা ঘণ্টা নিজের ১২ KB-র sketch রাখে; ২৪টি ঘণ্টার sketch মেলালে দিনের, ৩০টি দিনের মেলালে মাসের আলাদা ব্যবহারকারী — কাঁচা ডেটা আবার না পড়েই। দৈনিক গণনার যোগফল মাসিক আলাদা ব্যবহারকারী নয় (একই মানুষ ৩০ বার গোনা পড়বেন); register-এর max এই ভুল এড়ায়। Max নেওয়া commutative, associative আর idempotent — ক্রম যা-ই হোক, একই sketch দুবার মেলালেও ফল এক; তাই retry বা duplicate বার্তায় (পর্ব ৩৪) ভয় নেই, আর এই তিন গুণই পরের পর্বের CRDT-এর ভিত্তি (পর্ব ৪৬)। তবে intersection — “দুই দিনেই এসেছেন কতজন” — এত সহজ নয় (ভাবনার প্রশ্ন ৪)।

Open-source Redis-এ HyperLogLog একটি data type: PFADD যোগ, PFCOUNT গণনা, PFMERGE মেলানো। Redis-এর documentation অনুযায়ী (লেখার সময়ে) প্রতিটি key সর্বোচ্চ প্রায় ১২ KB নেয়, standard error ০.৮১% — অর্থাৎ p = 14; অল্প উপাদানে sparse রূপে আরও কম। খুঁটিনাটি সংস্করণভেদে আলাদা হতে পারে।

# daily unique users, then a weekly merge (illustrative only)
PFADD uv:2026-10-27 user:31 user:52 user:7
PFADD uv:2026-10-28 user:31 user:99
PFCOUNT uv:2026-10-28                          # about 2
PFMERGE uv:week:44 uv:2026-10-27 uv:2026-10-28
PFCOUNT uv:week:44                             # about 4 (user:31 counted once)

৮ · অন্যান্য sketch, বাছাই আর ইন্টারভিউতে আকার ঠিক করা

আরও দুটি পরিবার নাম জানার মতো। Quantile sketch: শত সার্ভারের latency-র p99 চাই, কিন্তু সার্ভারগুলোর p99-এর গড় মিলিত p99 নয় (পর্ব ৪); Ted Dunning-এর t-digest (আর KLL, DDSketch-এর মতো কয়েকটি) মেলানো যায় এমন সংক্ষিপ্ত সারাংশ থেকে percentile আন্দাজ করে। Similarity sketch: Andrei Broder-এর ১৯৯৭ সালের MinHash প্রতিটি set-এর কয়েকশো hash-এর সর্বনিম্ন মান রাখে; দুই set-এর কত ভাগ সর্বনিম্ন মিলল, সেটিই তাদের মিলের (Jaccard similarity) আনুমানিক মান — প্রায়-একই web পাতা খোঁজার জন্য তৈরি।

নিচের ছবিতে দুটি সাধারণ জায়গা পাশাপাশি — অনুরোধের পথে সামনে বসা Bloom filter, আর analytics-এর পথে প্রতিটি partition-এ sketch, শেষে merge:

ইন্টারভিউতে আকার ঠিক করার পাঁচ ধাপ

1. প্রশ্নটি চিনুন: আছে কি না, কতবার, কতজন আলাদা, নাকি percentile?
2. পরিমাণ বলুন: n বা N, আর কতগুলো sketch — প্রতি পাতা, প্রতি দিন।
3. ভুলের মাত্রা আর দিক: কত শতাংশ, আর কোন দিকের ভুলে কার ক্ষতি।
4. সূত্রে বসান: Bloom-এ m = 1.44·n·log₂(1/p), count-min-এ ⌈e/ε⌉ × ⌈ln(1/δ)⌉, HyperLogLog-এ 2^p × 6 bit — তারপর sketch-সংখ্যা দিয়ে গুণ।
5. জীবনচক্র: কোথায় থাকে, কীভাবে মেলে, restart-এ হারায় কি না, পুরোনোটা কখন বাদ, আর n সীমা পেরোলে কী।

পাঁচ ধাপের একটি পূর্ণ হিসাব — crawler-এর filter, count-min আর লাখো HyperLogLog — অনুশীলন ১-এ আছে।

৯ · AI-এর যুগে sketch-নকশা যাচাই

“আলাদা ব্যবহারকারী আর trending গান কীভাবে গুনব?” — AI সাধারণত বলে “Redis-এর HyperLogLog আর একটি Bloom filter ব্যবহার করুন।” নাম ঠিক, কিন্তু কত ভুল, কোন দিকে, কত memory, কীভাবে মেলাবেন — এগুলো প্রায়ই বাদ পড়ে। সাধারণ ভুলগুলো:

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

• নিখুঁত উপায়ের memory নিজে হিসাব করেছি — hash set বা bitmap কি যথেষ্ট ছিল?
• প্রতিটি সূত্র নিজে বসিয়ে আবার হিসাব করেছি — bit থেকে byte-এ ৮ দিয়ে ভাগ, sketch-সংখ্যা দিয়ে গুণ
• প্রতিটি ব্যবহারে ভুলের দিক আর তার দাম লিখেছি; যেখানে দাম আছে, সেখানে “হয়তো আছে”-র পরে আসল উৎসে যাচাই রেখেছি
• Merge-এর নিয়ম (max, যোগ, OR), একই hash আর seed, আর restart-এ sketch হারালে কী হবে — মিলিয়ে দেখেছি
• একটি ছোট simulation বা load test-এ ভুলের হার মেপেছি, আর product-এর সীমা official documentation-এ মিলিয়েছি