توی سیستم‌های High-Load، یکی از چالش‌های همیشگی اینه که خیلی سریع بفهمیم یک دیتای خاص وجود داره یا نه. اگر بخوایم برای هر چک کردن ساده به‌طور مستقیم سراغ دیتابیس بریم یا حتی به صورت کامل روی Cache حساب کنیم، هم منابع زیادی درگیر می‌شه و هم Latency بالا میره.

یکی از رویکردهای بهینه و جذاب برای حل این مسئله، استفاده از Bloom Filter هست.
بلوم فیلتر یک Data Structure احتمالاتی 🥴 هست که با کمترین میزان مصرف مموری و سرعت خیره‌کننده، بهمون میگه یک آیتم وجود داره یا نه.

سناریوی واقعی: انتخاب یوزرنیم در تلگرام
تلگرام صدها میلیون کاربر داره. وقتی شما موقع ثبت‌نام داری یوزرنیم تایپ می‌کنی، به ازای هر کاراکتری که می‌زنی باید چک بشه که این یوزرنیم آزاد هست یا نه. اگر تلگرام بخواد برای هر تایپ شما یک کوئری به دیتابیس اصلیش بزنه، دیتابیس در عرض چند ثانیه از حجم درخواست‌ها نابود می‌شه!
راه‌حل چیه؟ تلگرام تمام یوزرنیم‌های ثبت‌شده رو میده به یک Bloom Filter که توی رم قرار داره. وقتی شما یوزرنیم جدید رو تایپ می‌کنی، بلوم فیلتر در کسری از میلی‌ثانیه چک می‌کنه. اگر بگه «این یوزرنیم به‌طور قطع وجود نداره»، تلگرام همون لحظه تیک سبز رو بهت نشون میده و دیگه کاری به دیتابیس نداره (صرفه‌جویی عظیم در منابع). اما اگر بلوم فیلتر بگه «ممکن هست وجود داشته باشه»، تلگرام تازه اونجا میره از دیتابیس می‌پرسه که "مطمئنی این یوزرنیم پر شده؟" تا وضعیت دقیق رو بهت بگه. (که البته تلگرام چنین کاری نمی‌کنه و مثال بود=))

حالا این بلوم فیلتر چطور کار می‌کنه؟
پشت صحنه، Bloom Filter در واقع فقط یک آرایه طولانی از Bitهاست که اول کار همه‌شون صفر هستن. در کنارش، چند تا تابع Hash مستقل و سریع هم داریم.
وقتی می‌خوایم یک دیتای جدید رو به سیستم اضافه کنیم، این دیتا رو به توابع Hash می‌دیم. خروجی این توابع، ایندکس‌هایی از همون آرایه بیت‌هاست. بعد میریم اون ایندکس‌ها رو برابر با ۱ قرار می‌دیم.

موقع جستجو دوباره همون دیتای ورودی رو هش می‌کنیم و ایندکس‌ها رو چک می‌کنیم:
۱. اگر حتی یکی از اون بیت‌ها صفر باشه، سیستم با قطعیت ۱۰۰٪ میگه این دیتا «به‌طور قطع وجود نداره».
۲. اگر همه بیت‌ها ۱ باشن، سیستم میگه این دیتا «احتمالا وجود داره».

چرا می‌گیم احتمالا؟ چون ممکنه اون بیت‌ها قبلا به‌خاطر هش شدنِ دیتای دیگه‌ای ۱ شده باشن (همون پدیده Hash Collision). یعنی ما توی Bloom Filter خطای False Positive داریم، اما False Negative اصلا نداریم.

البته که این ساختار محدودیت‌های خودش رو هم داره؛ به‌طور مثال حذف کردن یک آیتم از بلوم فیلتر در پیاده‌سازی‌های استانداردش یه‌جورایی غیرممکنه؛ چون با صفر کردن یک بیت، ممکن هست دیتای دیگه‌ای که از همون بیت استفاده می‌کرده رو هم خراب کنیم.

در نهایت، در ازای پذیرش اون احتمال کمِ False Positive، سیستمی به دست میاد که می‌تونه وجود میلیون‌ها رکورد رو فقط با چند مگابایت RAM در لایه Application چک کنه و زیرساخت دیتابیس شما رو از شر درخواست‌های بیهوده نجات بده.