Bloom filter: অল্প memory-তে সদস্যপদ যাচাই

Bloom filter একটি ছোট data structure, যা একটিই প্রশ্নের উত্তর দেয়: এই item কি সেটে আছে? উত্তর দুই রকম:

• "নিশ্চিত নেই": সবসময় সঠিক।
• "সম্ভবত আছে": সাধারণত ঠিক, মাঝেমধ্যে false positive।

এটি কখনো false negative দেয় না, আর item নিজে রাখার চেয়ে অনেক কম memory লাগে।

কীভাবে কাজ করে

m টি bit-এর array দিয়ে শুরু, সব ০, আর k টি আলাদা hash function।

• Item যোগ: k টি hash চালান, সেই k টি bit-কে ১ করুন।
• Item যাচাই: একই k টি hash চালান। যেকোনো bit ০ হলে item কখনো যোগ হয়নি। সব ১ হলে সম্ভবত যোগ হয়েছে (ওই bit অন্য item-ও সেট করে থাকতে পারে)।

Tuning

প্রতি item-এ বেশি bit ও সঠিক সংখ্যক hash false-positive হার কমায়। মোটামুটি, প্রতি item-এ প্রায় ১০ bit ও ৭টি hash-এ প্রায় ১% false positive হয়। Filter-এর আকার ঠিক করার সময়ই গ্রহণযোগ্য হার বেছে নেবেন।

সীমা

• Bit শেয়ার হয় বলে item মোছা যায় না। Counting Bloom filter bit-এর বদলে ছোট counter রেখে মোছার সুযোগ দেয়।
• এটি item রাখে না, তাই তালিকা করা যায় না।
• পরিকল্পনার চেয়ে অনেক বেশি item যোগ করলে false positive বাড়ে।

কোথায় ব্যবহার হয়

• Cache penetration: কোনো key-র জন্য database ডাকার আগে filter দেখুন। "নিশ্চিত নেই" বললে query বাদ দিন। যে item-ই নেই তার request থেকে database বাঁচে।
• Database (Cassandra, RocksDB-র মতো LSM-tree store): যে disk ফাইলে key থাকতেই পারে না তা পড়া এড়ায়।
• Crawler: "এই URL কি আগেই দেখা হয়েছে?"
• Spam ও ক্ষতিকর URL-এর আগাম যাচাই, এবং বড় stream-এ ডুপ্লিকেট ধরা।

উদাহরণ

Signup ফর্ম দেখে "এই username কি নেওয়া?" সব username-এর একটি Bloom filter বেশিরভাগ নতুন নামের জন্য "নিশ্চিত নেওয়া হয়নি" বলে, তাই database এড়ানো যায়। "হয়তো" বললে আসল যাচাই করুন।

মূল কথা: Bloom filter সস্তা প্রথম যাচাই হিসেবে ব্যবহার করুন যা নিশ্চিতভাবে "না" বলতে পারে, আর "হয়তো"-কে সবসময় আসল উৎসে যাচাই করুন।

---

System Design সিরিজ, পর্ব ২ (building block): 8 নম্বর (মোট 14)। আগের লেখা: gRPC বনাম REST: কোন API স্টাইল বাছবেন.