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

المستوى المطلوب: متوسط. الشرح بيفترض إنك مرتاح مع HashSet أو Dict في أي لغة، وتعرف الفرق بين O(1) و O(n) من غير ما نفسّرها من الصفر. لو لسه مبتدئ في الـ data structures، خد جولة في الـ HashSet الأول وارجع.

لو بتفحص "هل الـ user ده زار الصفحة قبل كده؟" على 80 مليون سجل في DB، أنت بتدفع 12ms لكل query. Bloom Filter بيرد على نفس السؤال في 0.4 microsecond، بـ 1.2MB ذاكرة بدل 6.4GB، بشرط واحد بسيط هتفهمه دلوقتي.

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

عندك سيرفر بيستقبل 12,000 طلب/ثانية، كل طلب لازم يتأكد إن user ID موجود في قائمة "المحظورين" (4 مليون ID). الحل المباشر: query على PostgreSQL. النتيجة: 12ms × 12,000 = استهلاك CPU 144 ثانية/ثانية. السيرفر بيختنق وانت لسه ما بدأتش الشغل الفعلي.

تحط القائمة كلها في Redis SET؟ يعمل، بس بياخد 320MB RAM. لو القائمة كبرت لـ 80 مليون، تبقى 6.4GB، وكل query بياخد قفزة شبكة (network hop) إضافية. Bloom Filter بيحل المشكلة دي بـ 1.2MB ثابتة في process memory نفسه، صفر شبكة، صفر I/O.

المثال البسيط للمبتدئ: بوّاب الحفلة

تخيّل بوّاب حفلة عنده ورقة فيها 4,000 اسم. كل ضيف بيوصل، البوّاب لازم يتأكد إن اسمه على القائمة. لو هيبحث خطّي اسم باسم، الضيف رقم 3,999 بياخد 4 ثواني والطابور بيقف.

الحل الذكي: البوّاب يحسب لكل اسم 3 أرقام (مجموع حروف، طول الاسم، كود حرف أول × 7). الـ 3 أرقام دي بتأشّر على 3 خانات في جدول 1,000 خانة. أول ما اسمك يدخل القائمة، الـ 3 خانات بتاعتك بتتعلّم عليها علامة.

لما ضيف جديد يوصل، البوّاب يحسب نفس الـ 3 أرقام، يبص للـ 3 خانات. لو واحدة منهم فاضية → الاسم مستحيل يكون على القائمة. لو الـ 3 كلها معلّمة → فيه احتمال كبير الاسم موجود، مع نسبة "إنذار كاذب" صغيرة محسوبة سلفًا.

ده Bloom Filter بالظبط: bit array + hash functions متعددة + ضمان رياضي إن "مش موجود" دائمًا صح.

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

Bloom Filter اخترعه Burton Howard Bloom سنة 1970 في ورقة منشورة في Communications of the ACM. هو data structure احتمالي مكوّن من:

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

عند الإضافة (insert): تحسب الـ k hashes للعنصر، تخلّي الـ k bits المقابلة = 1.

عند الفحص (query): تحسب الـ k hashes، تشوف الـ k bits. لو واحدة منهم 0 → العنصر قطعًا غير موجود. لو كلهم 1 → العنصر محتمل موجود (ممكن يكون false positive).

الميزة اللي محتاج تركّز فيها: false negatives مستحيلة رياضيًا. لو الـ filter قال "مش موجود" يبقى مش موجود حتمًا. الـ false positives بس هي اللي ممكنة، واحتمالها محسوب بالمعادلة دي:

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 سطر

import mmh3
from bitarray import bitarray
import math

class BloomFilter:
    def __init__(self, expected_items: int, fp_rate: float = 0.01):
        self.m = -int(expected_items * math.log(fp_rate) / (math.log(2) ** 2))
        self.k = max(1, int((self.m / expected_items) * math.log(2)))
        self.bits = bitarray(self.m)
        self.bits.setall(0)
        self.n = 0

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

    def __contains__(self, item: str) -> bool:
        for seed in range(self.k):
            idx = mmh3.hash(item, seed) % self.m
            if not self.bits[idx]:
                return False
        return True

# اختبار: مليون عنصر بـ FP rate = 1%
bf = BloomFilter(expected_items=1_000_000, fp_rate=0.01)
for i in range(1_000_000):
    bf.add(f"user_{i}")

print(f"حجم الذاكرة: {bf.m / 8 / 1024 / 1024:.2f} MB")
print(f"عدد hash functions (k): {bf.k}")
print(f"user_42 موجود؟ {'user_42' in bf}")
print(f"user_99999999 موجود؟ {'user_99999999' in bf}")

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

حجم الذاكرة: 1.14 MB
عدد hash functions (k): 7
user_42 موجود؟ True
user_99999999 موجود؟ False

قارن: 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