Bloom Filters للمتوسط: افحص وجود مليون عنصر في 1.2MB ذاكرة

FP_rate ≈ (1 - e^(-kn/m))^k

n = عدد العناصر المُضافة
m = حجم bit array بالبتات
k = عدد hash functions

الافتراض الخفي: الـ hash functions موزّعة بشكل متساوٍ (uniform) ومستقلة. لو استخدمت hash function ضعيفة زي MD5 truncated، الـ FP الفعلي بيطلع أعلى من المعادلة. استخدم MurmurHash3 أو xxHash.

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

التشغيل بيرجّع:

قارن: set بايثون لمليون string بياخد ~73MB. Bloom Filter بياخد 1.14MB — توفير 64x، مع latency أسرع لأن الـ 1.14MB بتقعد في L2/L3 cache بالكامل، فالـ CPU ما بيلمسش RAM أصلًا في معظم الـ lookups.

السيناريو الواقعي: API بـ 12K req/s

على API لخدمة محتوى عربي بـ 12,000 طلب/ثانية، فيه قائمة 8 مليون رابط محظور بسبب DMCA + روابط phishing معروفة. القياسات الفعلية بعد التحويل من Redis SET لـ Bloom Filter (in-process):

الـ false positive rate الموصى بيه: 0.1%. يعني 12 طلب من كل 12,000 هيسأل الـ DB للتأكد بعد ما الـ filter قال "محتمل محظور". الـ DB بيتحمّل الرقم ده من غير ضغط، ومحدش بياخد قرار blocking نهائي قبل الفحص الثانوي.

الـ Trade-offs الحقيقية — اقرأهم قبل ما تستخدم

1. مبتقدرش تحذف عنصر. bit واحد ممكن يكون مشترك بين أكتر من عنصر. لو محتاج delete، استخدم Counting Bloom Filter (4-bit counters بدل 1-bit، بياكل 4x ذاكرة)، أو Cuckoo Filter.
2. الحجم لازم يتحدد مقدمًا. لو أضفت 10x من العدد المتوقع، الـ FP rate بينهار من 1% لـ 60% فعليًا. الحل: Scalable Bloom Filter (Almeida et al. 2007) اللي بيضيف layers جديدة لما الأولى تتشبع.
3. مبتقدرش تطلع العناصر اللي ضفتها. الـ structure ما بيخزّنش الـ keys نفسها — بيخزّن "بصمة" بس. لو محتاج enumerate، خد HashSet عادي أو HyperLogLog حسب الحالة.
4. الـ False Positive مش غلط — هو ميزة محسوبة. لازم يكون عندك فحص ثانوي (DB أو cache طبقة تانية) للحالات اللي الـ filter قال "محتمل موجود". لو مفيش فحص ثانوي، Bloom Filter غلط في حالتك.

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

تجنّبه في 4 حالات صريحة:

• عندك أقل من 10,000 عنصر — HashSet أبسط وأسرع وما فيش false positives أصلًا.
• محتاج تحذف عناصر بانتظام — Counting variant بيضيع الـ memory advantage الأصلي.
• لازم تستخرج العناصر نفسها لاحقًا (مش بس فحص الوجود) — استخدم Trie أو HashSet.
• الـ false positive ممكن يكلّفك فلوس مباشرة. مثلًا: "هل العميل ده دفع؟" — هنا 1% خطأ كارثة مالية وقانونية. استخدم authoritative DB lookup مباشرة.

أمثلة من الإنتاج الحقيقي

مش مجرد feature أكاديمي. الـ structure ده شغّال في systems بتاكل ترليون طلب يوميًا:

• Apache Cassandra — كل SSTable عندها Bloom Filter لتسريع الـ read path قبل ما يلمس القرص (موجود في توثيق Cassandra الرسمي تحت storage_engine).
• Google Bigtable — لتقليل قراءات GFS العشوائية (Chang et al. 2008، OSDI Paper).
• Redis — module RedisBloom رسمي من Redis Labs، شائع في deduplication و session caching.
• Chrome Safe Browsing — استخدم Bloom Filter قبل لتصفية URLs الخبيثة محليًا قبل ما يسأل Google API.
• Bitcoin SPV wallets — بتستخدم Bloom Filter لطلب transactions مرتبطة بـ addresses معينة من غير ما تكشف الـ wallet كله للـ peers.

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

افتح الـ codebase بتاعك ودوّر على أي query بتسأل "هل العنصر ده موجود في القائمة الكبيرة دي؟" وبتتنفّذ أكتر من 1,000 مرة في الدقيقة. لو لقيت واحد:

1. ركّب pybloom-live في Python أو bloom-filters في Node.js.
2. قس الـ FP rate الفعلي على عينة 100,000 طلب من logs الإنتاج.
3. لو الرقم اتطابق مع التوقع النظري، حوّل الـ hot path لـ Bloom Filter وخلّي الـ DB يتنفّس.

المصادر

• Bloom, B. H. (1970). "Space/time trade-offs in hash coding with allowable errors". Communications of the ACM, 13(7), 422–426.
• Almeida, P. S., Baquero, C., Preguiça, N., & Hutchison, D. (2007). "Scalable Bloom Filters". Information Processing Letters, 101(6), 255–261.
• Chang, F. et al. (2008). "Bigtable: A Distributed Storage System for Structured Data". OSDI '06 / ACM TOCS 26(2).
• Fan, B. et al. (2014). "Cuckoo Filter: Practically Better Than Bloom". CoNEXT '14.
• RedisBloom Documentation — redis.io/docs/data-types/probabilistic/bloom-filter
• Apache Cassandra Storage Engine — cassandra.apache.org/architecture/storage_engine
• MurmurHash3 (Austin Appleby) — github.com/aappleby/smhasher