لو بتعمل lookup على جدول فيه 100 مليون صف لكل request علشان تتأكد إن الـ user ده شاف الإعلان قبل كده، أنت بتدفع 200 ميكروثانية و 8GB RAM في كل instance. Bloom Filter بيرفض 99.9% من الطلبات قبل ما توصل للـ DB أصلاً، بـ 11 ميجابايت ذاكرة بس. في المقال ده هتبني واحد من الصفر وتفهم ليه Cassandra و Bitcoin و Chrome بيستخدموه.

Bloom Filter: التركيبة اللي بتقولك "أكيد لأ" أو "غالباً آه"

المشكلة باختصار

عندك قائمة ضخمة من العناصر (URLs زرتها قبل كده، usernames محجوزة، transaction hashes متشاف). كل request جديد لازم يتحقق: هل العنصر ده موجود في القائمة دي؟

الحل التقليدي: HashSet في الذاكرة. لكن لو القائمة 100 مليون string متوسط 40 حرف، الـ HashSet بياكل 6–8 جيجابايت. تحطها على DB؟ كل lookup بيكلفك round-trip شبكة، يعني 1–5 ميلي ثانية. على 10K request في الثانية، DB بتختنق.

Bloom Filter بيحل المشكلة بمقايضة ذكية: بدل ما يجاوبك "موجود" أو "مش موجود"، بيجاوبك "أكيد مش موجود" أو "غالباً موجود". الإجابة الأولى دقيقة 100%، التانية فيها نسبة خطأ صغيرة بتتحكم فيها أنت.

مثال للمبتدئ: حارس باب الحفلة

تخيّل حفلة فيها 1000 مدعو. الحارس مش حافظ كل الأسماء، لكن عنده ورقة فيها 8000 خانة، كلها فاضية في الأول. كل ما اسم يتسجل، الحارس بياخد الاسم ويمرّره على 3 طرق مختلفة لتحديد 3 خانات في الورقة، ويعلّم عليهم.

لمّا حد ييجي يدخل، الحارس بيكرر نفس العملية. لو لقى أي خانة من التلاتة فاضية → "أكيد مش مدعو، روح من هنا". لو الـ 3 كلهم معلّمين → "غالباً مدعو، اتفضل". الكلمة "غالباً" مهمة: ممكن تكون التلات خانات اتعلّموا بسبب أسامي تانية صدفة. ده بالظبط الـ false positive في Bloom Filter.

التعريف العلمي

Bloom Filter هو probabilistic data structure اخترعه Burton Howard Bloom سنة 1970. مكوّن من حاجتين:

• Bit array بحجم m بت، كلهم أصفار في البداية.
• k دالة hash مستقلة بترجّع كل واحدة رقم بين 0 و m-1.

للإضافة (insert): مرّر العنصر على الـ k دوال، اضبط البتات في الأماكن دي على 1.

للبحث (lookup): مرّر العنصر على نفس الـ k دوال. لو أي بت من الـ k بصفر → العنصر أكيد غير موجود. لو الـ k كلهم 1 → العنصر غالباً موجود.

ملحوظة مهمة: الحذف (delete) مش مدعوم في الـ Bloom Filter الكلاسيكي. لو محتاج حذف، استخدم Counting Bloom Filter (variant فيه عدّاد بدل بت).

الرياضيات اللي بتحدد الحجم

عندك n عنصر متوقع، وبتقبل false positive rate تساوي p. الحجم الأمثل m بالـ bits، وعدد دوال الـ hash الأمثل k:

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 لهذا الاستخدام).

import math
import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, n: int, p: float):
        self.m = int(-(n * math.log(p)) / (math.log(2) ** 2))
        self.k = int((self.m / n) * math.log(2))
        self.bits = bitarray(self.m)
        self.bits.setall(False)

    def _positions(self, item: str):
        for seed in range(self.k):
            yield mmh3.hash(item, seed) % self.m

    def add(self, item: str):
        for pos in self._positions(item):
            self.bits[pos] = True

    def __contains__(self, item: str) -> bool:
        return all(self.bits[pos] for pos in self._positions(item))

bf = BloomFilter(n=1_000_000, p=0.01)
bf.add("ahmed@example.com")
print("ahmed@example.com" in bf)   # True (موجود فعلاً)
print("xyz@example.com" in bf)     # False غالبًا (1% احتمال يطلع True بالغلط)

الكود ده لمليون عنصر بـ 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).