Bloom Filters
- ●Bloom filter একটা probabilistic data structure যা খুব কম জায়গায় বলে দেয় কোনো জিনিস সেটে আছে কি না।
- ●উত্তর দুই রকম — 'definitely no' (নিশ্চিত নেই) অথবা 'maybe yes' (থাকতেও পারে); false positive হয়, কিন্তু false negative কখনো হয় না।
- ●এটা একটা bit array আর কয়েকটা hash function দিয়ে কাজ করে; cache, ডেটাবেজ, ও crawler dedup-এ ব্যাপক ব্যবহৃত।
সমস্যাটা কী?
ভাবো তুমি একটা ওয়েব ক্রলার বানাচ্ছ যা প্রতিদিন কোটি কোটি URL ভিজিট করে। একটা নতুন URL পেলে তোমাকে আগে দেখতে হবে — "এই URL কি আগে ক্রল করেছি?" যদি করে থাকো, আবার করা মানে সময় ও ব্যান্ডউইথের অপচয়।
সহজ সমাধান — সব দেখা URL একটা HashSet-এ রাখো। কিন্তু ১০০ কোটি URL, প্রতিটা গড়ে ৭০ বাইট — মানে প্রায় ৭০ GB মেমোরি! এত RAM একটা মেশিনে রাখা ব্যয়বহুল ও কঠিন।
এখন একটু ভাবো — আমাদের কি আসলে পুরো URL-টা মনে রাখা দরকার? আমরা তো শুধু জানতে চাই "আগে দেখেছি কি না"। যদি একটা ব্যবস্থা থাকত যা ৯৯% নিশ্চয়তায়, মাত্র কয়েকশ MB-তে এই প্রশ্নের উত্তর দিত — তাহলেই হতো। ঠিক এই কাজটাই করে Bloom Filter।
মূল ধারণা
Bloom Filter হলো একটা space-efficient probabilistic data structure যা বলে দেয় কোনো উপাদান একটা সেটে আছে কি না — উত্তর হয় "নিশ্চিত নেই" অথবা "থাকতেও পারে"।
এর সবচেয়ে গুরুত্বপূর্ণ বৈশিষ্ট্য — এটা একটা Probabilistic Data Structure, মানে নিখুঁত নয়, কিছুটা অনিশ্চয়তা মেনে নিয়ে বিশাল জায়গা বাঁচায়। দুই রকম উত্তর:
- Definitely No — উপাদানটা সেটে নেই, এটা ১০০% নিশ্চিত।
- Maybe Yes — উপাদানটা থাকতে পারে, কিন্তু নিশ্চিত নয় (এটাই False Positive)।
মূল কথা — false negative কখনো হয় না, false positive হতে পারে। অর্থাৎ যা সত্যিই আছে তাকে কখনো "নেই" বলবে না, কিন্তু যা নেই তাকে মাঝে মাঝে "আছে" বলে ফেলতে পারে।
কীভাবে কাজ করে
এর দুটো উপকরণ — একটা bit array (শুরুতে সব ০) আর কয়েকটা ভিন্ন Hash Function।
Add করা
কোনো উপাদান (যেমন একটা URL) যোগ করতে:
- উপাদানটাকে k-টা hash function-এ পাঠাও।
- প্রতিটা hash একটা করে index দেয় (যেমন h1→2, h2→5, h3→9)।
- bit array-তে সেই সব position ১ করে দাও।
Check করা
কোনো উপাদান আছে কি না দেখতে:
- একই k-টা hash function চালাও, একই index গুলো পাও।
- দেখো সেই সব position কি ১?
- কোনো একটাও ০ হলে → definitely no (যোগ করা থাকলে সব position ১ হতোই)।
- সব ১ হলে → maybe yes (অন্য উপাদানও ওই bit গুলো ১ করে থাকতে পারে — তাই নিশ্চিত নয়)।
ছোট উদাহরণ (8-bit array, 3 hash)
| ধাপ | উপাদান | hash → index | bit array অবস্থা |
|---|---|---|---|
| শুরু | — | — | 0 0 0 0 0 0 0 0 |
| Add | "apple" | 1, 4, 6 | 0 1 0 0 1 0 1 0 |
| Add | "mango" | 0, 4, 7 | 1 1 0 0 1 0 1 1 |
| Check | "apple" | 1, 4, 6 → সব ১ | maybe yes (সঠিক) |
| Check | "grape" | 2, 5 → ০ আছে | definitely no |
Space-এর জাদু
লক্ষ করো, আমরা "apple" বা "mango" শব্দটা কোথাও জমা রাখিনি — শুধু কিছু bit set করেছি। তাই ১০০ কোটি উপাদানের জন্যও ~১% false positive rate-এ মাত্র কয়েকশ MB লাগে, ৭০ GB নয়। উপাদান বাড়লে false positive rate ধীরে ধীরে বাড়ে, যা bit array বড় বা hash সংখ্যা টিউন করে নিয়ন্ত্রণ করা যায়।
ভাবো একটা বিয়ের অনুষ্ঠানের গেটে দারোয়ান। সে প্রতিটা অতিথির পুরো নাম-ঠিকানা মনে রাখে না (তাতে অনেক জায়গা লাগত)। বদলে, প্রতিজন ঢোকার সময় সে তাদের হাতে কয়েকটা নির্দিষ্ট রঙের সিল মেরে দেয় (bit set করা)। কেউ আবার এলে দারোয়ান দেখে তার হাতে ওই রঙগুলো আছে কি না। কোনো রঙ না থাকলে — "তুমি নিশ্চিত আগে আসোনি" (definitely no)। সব রঙ থাকলে — "মনে হয় এসেছিলে" (maybe yes) — যদিও কাকতালীয়ভাবে নতুন কারো হাতেও একই রঙগুলো পড়ে যেতে পারে। সেটাই false positive।
প্রকারভেদ
মূল Bloom filter-এর কিছু সীমাবদ্ধতা আছে; তাই কয়েকটা ভ্যারিয়েন্ট তৈরি হয়েছে:
১. Standard (Classic) Bloom Filter
উপরে যা বর্ণনা করলাম। দ্রুত, সহজ, খুব কম জায়গা — কিন্তু delete করা যায় না (একটা bit একাধিক উপাদানের হতে পারে, তাই ০ করলে অন্যটার তথ্য নষ্ট হয়)।
২. Counting Bloom Filter
প্রতিটা bit-এর জায়গায় একটা ছোট counter রাখে। Add করলে counter বাড়ে, delete করলে কমে। এতে delete সম্ভব হয়, তবে কিছু বাড়তি জায়গা লাগে।
৩. Scalable Bloom Filter
উপাদান বাড়লে false positive rate ঠিক রাখতে এটি চলতে চলতে নিজের আকার বাড়িয়ে নেয় — যখন তুমি আগে থেকে মোট সংখ্যা জানো না, তখন কাজে লাগে।
কখন ব্যবহার করবে / করবে না
করবে:
- যখন নিখুঁত উত্তরের দরকার নেই, কিন্তু মেমোরি বাঁচানো জরুরি।
- যখন "নেই" উত্তরটা সস্তায় পেলে একটা ব্যয়বহুল কাজ (disk/network lookup) এড়ানো যায়।
করবে না:
- যখন false positive মোটেও মেনে নেওয়া যাবে না (যেমন নিরাপত্তা-সংবেদনশীল সিদ্ধান্ত)।
- যখন তোমার আসল উপাদানগুলো ফিরে পেতে হবে — Bloom filter ডেটা ফেরত দিতে পারে না, শুধু "আছে/নেই" বলে।
সবচেয়ে বড় ভুল — Bloom filter-এর "yes"-কে নিশ্চিত ধরে নেওয়া। "yes" মানে "maybe", তাই এটাকে সবসময় একটা দ্রুত pre-check হিসেবে ব্যবহার করো — "yes" পেলে তবেই আসল (ব্যয়বহুল) যাচাই চালাও। আর মনে রেখো, classic Bloom filter থেকে delete করা যায় না; delete দরকার হলে Counting Bloom Filter ব্যবহার করো।
বাস্তব উদাহরণ
Apache Cassandra ও Google Bigtable-এর মতো ডেটাবেজ Bloom filter দিয়ে disk read বাঁচায়। কোনো key খুঁজতে disk-এ যাওয়ার আগে তারা Bloom filter জিজ্ঞেস করে — "এই key কি এই SSTable ফাইলে থাকতে পারে?" উত্তর "definitely no" হলে disk-এ যাওয়ার দরকারই নেই (একটা ব্যয়বহুল ডিস্ক read এড়ানো গেল); "maybe yes" হলেই কেবল disk পড়ে।
আবার Google Chrome আগে ক্ষতিকর (malicious) URL চেক করতে Bloom filter-জাতীয় কৌশল ব্যবহার করত — URL টাইপ করার সাথে সাথে দ্রুত লোকালি দেখত "এটা কি বিপজ্জনক হতে পারে?", আর "maybe" হলে তবেই সার্ভারে নিশ্চিত যাচাই করত। Medium-ও ব্যবহারকারীকে আগে দেখা আর্টিকেল আবার সুপারিশ না করতে Bloom filter কাজে লাগায়।
ইন্টারভিউতে Bloom filter আনলে মূল লাইনটা মনে রেখো — "false negative নেই, false positive আছে।" এই একটা বাক্যেই তুমি বুঝিয়ে দাও কেন এটা pre-filter হিসেবে নিখুঁত — "no" নির্ভরযোগ্য বলে ব্যয়বহুল কাজ এড়ানো যায়, আর "yes"-এর ভুলটুকু পরে যাচাই করে শোধরানো যায়। space-এর ট্রেড-অফ আর Counting variant-এর কথা যোগ করলে উত্তর ঝকঝকে হবে।
মূল শব্দ (Key Terms)
মিনি কুইজ
1. Bloom filter কোন উত্তরটা নিশ্চিতভাবে দিতে পারে?
2. Bloom filter-এ false positive কেন হয়?
3. Bloom filter-এর মূল আকর্ষণ কী?