Bloom Filter بـ 8 ميجا رام: ازاي Chrome بيفلتر مليار رابط ضارّ في ميكروثانية

الهيكل ده ما يدعمش الحذف (إلا في النسخة 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 سطر)

الكود ده بيستخدم 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.