Bloom Filters بالعربي: ازاي تتحقق من مليار عنصر بـ 11 ميجابايت بس

m = -(n * ln(p)) / (ln(2)^2)
k = (m / n) * ln(2)

لو n = 100,000,000 و p = 0.01 (1% خطأ مقبول)، يطلع m ≈ 958 مليون بت = 120 ميجابايت، و k ≈ 7. لو خفّضت p لـ 0.001 (0.1%)، الذاكرة هتبقى 180 ميجابايت تقريبًا. مقارنة بـ HashSet اللي بياكل 6–8 جيجابايت لنفس البيانات، الفرق 50× في صالحك.

كود Python شغّال — 30 سطر

هنا implementation مينيمالي بدون مكتبات خارجية باستثناء mmh3 (MurmurHash3، أسرع وأوزع من hashlib لهذا الاستخدام).

الكود ده لمليون عنصر بـ 1% خطأ بياكل 1.2 ميجابايت بس. جرّبه بنفسك: ضيف مليون بريد عشوائي، وقيس كم نسبة الـ false positives على عيّنة جديدة. هتلاقيها قريبة جدًا من 0.01 — الرياضيات مش بتكدب.

أرقام واقعية من production

دي مش أرقامي، دي مذكورة في وثائق المشاريع نفسها:

• Cassandra: كل SSTable معاه Bloom Filter. لما تبحث عن key، الـ filter بيقولك أي SSTable يستحق فتح فعلاً. النتيجة: تخفيض 95–99% من الـ disk reads العشوائية.
• Chrome Safe Browsing: قائمة المواقع الخبيثة فيها ملايين العناوين. Chrome بيخزّن Bloom Filter محلي بحجم بضع ميجابايت بدل قائمة كاملة بحجم جيجابايت، ولو الـ filter قال "مشبوه" بيتأكد من السيرفر.
• Bitcoin SPV wallets: المحفظة الخفيفة بترسل Bloom Filter للـ full node بدل عناوينها الحقيقية، فالـ node يرجّع المعاملات اللي تطابق الفلتر — privacy + bandwidth في حركة واحدة.
• PostgreSQL: من إصدار 9.6 فيه bloom extension للـ index على أعمدة كتيرة بـ filter موحّد بدل index لكل عمود.

سيناريو عملي: deduplication لإعلانات شُوهدت

افترض إن عندك platform إعلانات بتعرض 50 مليون impression يوميًا، وعايز ما تعرضش نفس الإعلان لنفس الـ user مرّتين في 24 ساعة. الحل التقليدي: Redis SET فيه (user_id, ad_id). على 50 مليون مدخل، Redis بياخد ~5 جيجابايت RAM و كل lookup بيدخل الشبكة.

الحل بـ Bloom Filter: filter في الذاكرة المحلية للـ application server بحجم 60 ميجابايت يخدم نفس الـ 50 مليون مدخل بـ 0.1% false positive. الـ trade-off: 50,000 إعلان في اليوم هيتمنعوا غلط (false positive). ده مقبول في إعلانات. مش مقبول في معاملات بنكية.

الـ trade-offs اللي لازم تكون عارفها

• بتكسب: ذاكرة أقل بـ 50–100×، وlookup ثابت O(k) بدون round-trip شبكة.
• بتخسر: نسبة false positives محدودة، ومستحيل تحذف عنصر، ومستحيل تستعرض المحتوى. الـ filter one-way.
• الافتراض: عدد العناصر n معروف مسبقًا. لو تجاوزته بكتير، نسبة الخطأ هتطلع فوق p بكتير. لو محتاج auto-resize استخدم Scalable Bloom Filter (Almeida et al., 2007).

متى لا تستخدم Bloom Filter

• لمّا الـ dataset أصلاً صغير (أقل من 10,000 عنصر) — HashSet أبسط وبيخلص الشغل بدون false positives.
• لمّا الـ false positive واحد ممكن يكلّفك فلوس أو ثقة. الدفع، تسجيل الدخول، التحقق من جواز السفر — كله out of scope.
• لمّا محتاج تحذف عناصر بانتظام — استخدم Counting Bloom Filter أو Cuckoo Filter.
• لمّا n مش معروف وبيكبر بشكل غير محدود — Bloom Filter ثابت الحجم. لو هيكبر استخدم Scalable variant.

الخطوة التالية

افتح أبطأ endpoint في تطبيقك اللي بيعمل lookup ضد جدول كبير لمجرد التحقق من وجود مفتاح. لو الإجابة "مش موجود" في 95% من الحالات، حط Bloom Filter قبل الـ DB. قِس latency قبل وبعد، وقِس نسبة الـ DB hits اللي اتشالت. لو الفرق أقل من 30% احتمال إن الـ access pattern مش مناسب — ابعتلي الأرقام نناقش.

المصادر

• Bloom, B. H. (1970). Space/time trade-offs in hash coding with allowable errors, Communications of the ACM, 13(7).
• Almeida, P. S. et al. (2007). Scalable Bloom Filters, Information Processing Letters.
• Apache Cassandra documentation — SSTable Bloom Filter (cassandra.apache.org).
• PostgreSQL Documentation — bloom extension (postgresql.org/docs/current/bloom.html).
• Bitcoin BIP-37 — Connection Bloom Filtering.
• Chrome Safe Browsing — Update API design (developers.google.com/safe-browsing).
• mmh3 — Python wrapper for MurmurHash3 (pypi.org/project/mmh3).