المستوى المطلوب: متوسط

وقت القراءة المتوقّع: 9 دقائق.

لو عندك جدول فيه مليار URL ضارّ، وعايز تتأكد قبل ما المتصفح يفتح أي رابط إنه مش في القائمة، ما تقدرش تحمّل المليار في ذاكرة العميل. Bloom Filter بيحلّ المشكلة دي في 8 ميجا رام تقريبًا، وبيرد على السؤال "هل الرابط ده موجود؟" في أقل من ميكروثانية، بمعدل خطأ تحت 1%. ده نفس الهيكل اللي Chrome بيستخدمه في خدمة Safe Browsing من 2012، واللي Cassandra بتعتمد عليه في كل SSTable عندها.

Bloom Filter: المرشّح الاحتمالي اللي بيفرق في القرارات الكبيرة

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

تخيّل إنك بتبني خدمة مكافحة تصيّد. عندك قاعدة بيانات بمليار رابط مشكوك فيه. كل مرة المستخدم بيكتب URL في المتصفح، لازم تتأكد إنه مش موجود في القائمة قبل ما يدوس Enter.

• لو بعت كل URL للسيرفر، هتاكل شبكة هائلة وهتأخّر التحميل.
• لو حمّلت القائمة كلها على العميل، هتاكل 30 جيجا رام (مليار رابط × 30 بايت متوسّط).
• لو حطيتها في DB في الذاكرة، الـ p95 latency في الاستعلام هيعدّي 5 مللي ثانية لكل ضربة كيبورد.

Bloom Filter بيدّيك إجابة سريعة، محلية، بحجم صغير جدًا، مقابل تنازل واحد بسيط: ممكن في 1% من الحالات يقول "ربما موجود" لرابط مش موجود فعلًا. والـ 1% دي بتتحقّق بسؤال السيرفر، فمحدّش بيتضرّر.

المثال البسيط أولًا: موظف باب الحفلة

تخيّل حفلة فيها 500 مدعوّ. على الباب موظف عنده ورقة بـ 1000 خانة فاضية. كل ضيف يدخل، الموظف بياخد اسمه ويعمل عليه ثلاث طرق تحويل مختلفة (يقلب الحروف، يجمع أرقام، يدخل اسم الأم) فيطلع له ثلاثة أرقام بين 1 و 1000. يحط علامة "صح" في الخانات الثلاثة.

لمّا يجي شخص جديد ويدّعي إنه مدعوّ، الموظف يعمل نفس الطرق التلاتة على اسمه. لو أيّ خانة من التلاتة فاضية → الشخص ده حتمًا مش مدعوّ، يتطرد. لو الخانات التلاتة عليها علامة → ربما مدعوّ، يدخل.

لاحظ حاجة مهمة: الموظف ما عندوش قائمة الأسماء أصلاً. عنده 1000 خانة بس. وممكن يحصل إن واحد دخيل صادف إن أرقامه التلاتة كلها مكتوبة قبل كده من ضيوف تانيين، فيدخل غلط (false positive). لكن مستحيل ضيف حقيقي يتطرد، لأن الخانات بتاعته اتلوّنت يوم ما دخل أول مرة.

ده بالظبط اللي Bloom Filter بيعمله: ممكن يقول "موجود" لحد مش موجود، لكن مستحيل يقول "مش موجود" لحد فعلًا موجود. صفر false negatives. هذه الخاصية هي اللي بتخلّيه مفيد جدًا كطبقة قبل الـ DB.

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

الـ Bloom Filter (اقترحه Burton Howard Bloom سنة 1970 في مجلة CACM) هيكل بيانات احتمالي مكوّن من جزئين:

• bit array طوله m بِت، كل البِتات مبدئيًا = 0.
• k دالة hash مستقلة، كل واحدة بتاخد العنصر وترجّع رقم بين 0 و m−1.

عند الإضافة (insert): بنحسب الـ k قيم hash للعنصر، ونحط 1 في كل المواضع الناتجة. عند الاستعلام (query): بنحسب نفس الـ k قيم. لو كل البِتات الـ k = 1 → "ربما موجود". لو واحد بس منهم 0 → "حتمًا غير موجود".

الهيكل ده ما يدعمش الحذف (إلا في النسخة Counting Bloom Filter)، ما يخزّنش العناصر نفسها، وما يقدرش يطلعها. هو مرشّح بـ false positive rate قابل للحساب الرياضي:

p ≈ (1 − e^−kn/m)^k

حيث n عدد العناصر المضافة. لقيمة معطاة من n وp، الـ m الأمثل = −n·ln(p) / (ln 2)²، والـ k الأمثل = (m/n)·ln(2). القاعدة العملية: 10 بِت لكل عنصر تدّيك خطأ ~1%.

كود Python شغّال (40 سطر)

# pip install mmh3 bitarray
import math
import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, n_items: int, fp_rate: float = 0.01):
        self.m = self._optimal_m(n_items, fp_rate)
        self.k = self._optimal_k(self.m, n_items)
        self.bits = bitarray(self.m)
        self.bits.setall(0)

    @staticmethod
    def _optimal_m(n: int, p: float) -> int:
        return int(-(n * math.log(p)) / (math.log(2) ** 2))

    @staticmethod
    def _optimal_k(m: int, n: int) -> int:
        return max(1, int((m / n) * math.log(2)))

    def add(self, item: str) -> None:
        for seed in range(self.k):
            idx = mmh3.hash(item, seed) % self.m
            self.bits[idx] = 1

    def __contains__(self, item: str) -> bool:
        return all(
            self.bits[mmh3.hash(item, seed) % self.m]
            for seed in range(self.k)
        )

# تجربة على مليون عنصر
bf = BloomFilter(n_items=1_000_000, fp_rate=0.01)
for i in range(1_000_000):
    bf.add(f"https://malicious-{i}.example")

print("https://malicious-42.example" in bf)   # True دائمًا
print("https://safe-site.example" in bf)      # False ~99% من الحالات
print(f"حجم الـ filter: {bf.m // 8 // 1024} KB")  # ~1170 KB

الكود ده بيستخدم MurmurHash3 (دالة hash سريعة وغير-تشفيرية، مثالية للموزّعات بدون متطلبات أمنية)، ومكتبة bitarray اللي بتخزّن بِت واحد لكل خانة بدل بايت كامل. النتيجة: مليون رابط في 1.17 ميجا، ومعدل خطأ 1% بالظبط.

أرقام واقعية من إنتاج فعلي

الـ Bloom Filter مش حاجة أكاديمية. هو شغّال في أكبر منظومات العالم:

• Chrome Safe Browsing: قاعدة الروابط الضارة بحوالي 3 مليون عنصر، الـ filter في الذاكرة ~2 ميجا، زمن استعلام ~600 نانو ثانية، false positive rate ~0.1% (وبعدها بيتحقق المتصفح من سيرفر Google فقط للروابط اللي رجعت "ربما موجود"، فاللي بيوصلوا للسيرفر أقل من 0.1% من الاستعلامات).
• Apache Cassandra: بتستخدم Bloom Filter لكل SSTable. لمّا تستعلم على key، السيستم بيسأل الـ Bloom Filter الأول. لو رد "غير موجود"، بيوفّر فتح الملف على القرص بالكامل. ده بيوفّر آلاف الـ disk reads في الثانية في الـ clusters الكبيرة.
• Bitcoin SPV nodes: بتستخدم Bloom Filter عشان تطلب من peers بس المعاملات اللي ليها علاقة بمحفظة المستخدم، بدون ما تكشف العناوين الكاملة.
• Medium: بتستخدم Bloom Filter عشان تتأكد إن الـ recommendation ما يكرّرش مقال شفته قبل كده، بدون ما تخزّن سجل قراءة كامل لكل مستخدم.

القياس البسيط: لـ 100 مليون عنصر بمعدل خطأ 1%، بتحتاج 117 ميجا فقط. لو نفس الـ 100 مليون رابط محفوظين كنصوص في hash set، هتاكل 3 جيجا على الأقل. الفرق 25 ضعف في الذاكرة.

الـ trade-offs الحقيقية

كل أداة ليها ثمن. الـ Bloom Filter بالظبط:

• المكسب 1: ذاكرة صغيرة جدًا — تقريبًا 10 بِت لكل عنصر لمعدل خطأ 1%، أو 14 بِت لمعدل 0.1%.
• المكسب 2: استعلام O(k) ثابت ومستقل عن n. لو ضفت مليار عنصر تاني، زمن الاستعلام ما يتغيّرش.
• المكسب 3: صفر false negatives. لو رد "غير موجود"، ده مضمون 100%.
• الخسارة 1: false positives موجودة بنسبة معروفة. لازم منظومتك تتعامل معاها (طبقة تحقّق بعدها).
• الخسارة 2: ما تقدرش تحذف عنصر. لو محتاج، استخدم Counting Bloom Filter (4 بت لكل خانة بدل 1) أو Cuckoo Filter.
• الخسارة 3: ما تقدرش تعدّ بدقة كم عنصر داخله ولا تطلع العناصر نفسها. هو one-way.
• الافتراض: دوال الـ hash بتوزّع uniform على المدى. لو غير ذلك (مثلًا hash ضعيف على أسماء مشابهة)، false positive rate الفعلي بيرتفع.

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

الأداة دي ممتازة في حالات معيّنة بالظبط، ومش مناسبة في حالات تانية. تجنّبها في:

• أي قرار لا يحتمل false positive: تحقق ملكية حساب بنكي، صلاحيات أمنية حساسة، أو تحديد هوية. استخدم hash set عادي أو DB query.
• الحاجات اللي بتتغيّر كتير بحذف: لو بتحذف عناصر بانتظام (cache invalidation، session expiry) — استخدم Cuckoo Filter أو Counting Bloom.
• مجموعات صغيرة (أقل من ~1000 عنصر): hash set عادي هيكون أصغر وأسرع. الـ Bloom بيكسب في المقاييس الكبيرة.
• لمّا محتاج تطلع العناصر نفسها: Bloom Filter مرشّح بس، مش مخزّن. استخدم structure تانية فوقه.
• لمّا الـ false positive rate الفعلي مش مقبول حتى مع الـ verify اللاحق: مثلًا لو verify على DB غالي جدًا، حتى 1% ممكن تكسرك.

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

افتح أقرب مشروع عندك فيه استعلام "هل ده موجود؟" على جدول كبير — emails مكرّرة، session IDs، URLs، product SKUs. ركّب Bloom Filter في الذاكرة قبل الـ DB، وقِس الـ p95 على 10 آلاف استعلام قبل وبعد. لو معظم استعلاماتك "غير موجود" (وده الشائع)، هتشوف الـ DB load بينزل بسهولة 90%، والـ latency بتنزل من ميلي ثوان لميكروثوان. ابعتلي الأرقام لو حصل تحسّن، أو لو لقيت الـ false positive rate الفعلي مختلف عن المتوقَّع نظريًا.

المصادر

• Burton H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, Vol 13, No 7, July 1970. dl.acm.org/doi/10.1145/362686.362692
• Google Safe Browsing technical overview — safebrowsing.google.com
• Apache Cassandra — Bloom Filters operating guide — cassandra.apache.org
• Bitcoin BIP 37 (Connection Bloom filtering) — github.com/bitcoin/bips
• Python mmh3 (MurmurHash3 binding) — pypi.org/project/mmh3
• Python bitarray library — pypi.org/project/bitarray
• Andrei Broder & Michael Mitzenmacher, "Network Applications of Bloom Filters: A Survey", Internet Mathematics 1(4), 2004.