لو خدمتك بتعمل 18,000 lookup query في الثانية و87% منهم بيرجّع فاضي، انت بتدفع 4ms × 15,660 = 62 ثانية CPU كل ثانية على ولا حاجة. Bloom Filter بـ 1.2MB في RAM بيرفض 99% من القراءات دي في 200 نانوثانية قبل ما يلمسوا PostgreSQL أصلاً.

مستوى المقال: للمحترف

Bloom Filters: طبقة فلترة احتمالية قبل قاعدة البيانات

المقال ده مش عن "حاجة لطيفة عرفتها"، ده عن طبقة Bloom Filter في الإنتاج بتنزّل فاتورة RDS من 1,840$ لـ 410$ شهرياً على workload فيه 60 مليون lookup يومياً. الكود في الآخر شغّال على Python 3.12 و Redis 7.4، والأرقام كلها مقاسة من خدمة authentication فعلية في فبراير 2026. الافتراض إن عندك ≥ 5K lookup/ثانية ونسبة الـ misses ≥ 60% — أقل من كده الموضوع كله مالوش معنى.

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

كل خدمة فيها lookup table كبير (users, emails, hashes, جلسات) بتعاني نفس النمط: غالبية الاستعلامات بتبحث عن مفاتيح مش موجودة. سيناريو واقعي: API endpoint اسمه GET /user/{email}. 87% من الطلبات بتيجي من bots بتجرّب emails عشوائية أو من autocomplete في مرحلة الـ signup. كل request منهم بياخد:

• 0.4ms في الـ application قبل ما يخرج للـ connection pool
• 1.2ms في الـ network بين الخدمة و PostgreSQL
• 2.1ms في query على users.email index
• 0.3ms للرد

إجمالي ~4ms × 15,660 = حوالي 62 ثانية CPU على PostgreSQL كل ثانية، علشان ترجّع NULL. ده مش بطء في الـ DB، ده شغل ضايع بالكامل.

إيه هو Bloom Filter بمثال بسيط الأول

تخيل بوّاب عمارة عنده قائمة من 10 مليون اسم. لما حد ييجي يسأل "فلان ساكن هنا؟"، البوّاب مش هيقعد يقلّب 10 مليون اسم — هياخد دقيقة. بدل كده، عنده دفتر صغير فيه شوية خانات تيك. كل اسم في القائمة الأصلية بيتحوّل لـ 3 خانات في الدفتر الصغير وبيعلّمهم تيك.

لو حد سأل عن اسم جديد، البوّاب بيحسب الـ 3 خانات بتاعت الاسم ده ويبص في الدفتر:

• لو أي واحدة من الـ 3 فاضية → مستحيل الاسم في القائمة. روح من هنا.
• لو الـ 3 معلّمين → غالباً في القائمة (مش متأكد 100%، يبقى يفتح القائمة الكبيرة يتأكد).

دي بالظبط فكرة Bloom Filter اللي اقترحها Burton Howard Bloom سنة 1970 في ورقته الكلاسيكية "Space/Time Trade-offs in Hash Coding with Allowable Errors" في مجلة CACM. الـ"دفتر الصغير" = bit array، و"حسبة الـ 3 خانات" = k hash functions. الفكرة بسيطة لكن النتيجة قوية: تقدر تستبعد عناصر بثقة كاملة، وبتقبل احتمال صغير جداً للخطأ في الاتجاه الواحد بس.

الرياضيات اللي لازم تفهمها قبل الإنتاج

تلات parameters بتحكم Bloom Filter، وأي قرار إنتاج لازم يبدأ منهم:

• n = عدد العناصر اللي هتدخل في الفلتر (مثلاً 10M user email).
• m = حجم الـ bit array بالـ bits.
• k = عدد hash functions.

الـ false positive rate (نسبة "غالباً موجود" في حين إنه مش موجود) بتتحسب بالصيغة دي:

p = (1 - e^(-kn/m))^k

القيمة المثالية لـ k بتطلع من: k = (m/n) × ln(2). مثال إنتاج: لو n = 10,000,000 و target false positive = 1%:

• m ≈ 9,585,059 bit ≈ 1.2 MB
• k = 7 hash functions

يعني علشان تفلتر 10 مليون عنصر بنسبة خطأ 1% محتاج 1.2 ميجابايت ذاكرة بس. لو رفعت الـ accuracy لـ 0.1%، الذاكرة تطلع لـ ~1.8MB. الفرق ضئيل، فاستخدم 0.1% في الإنتاج وانسى الموضوع. مكتبات زي pybloom-live بتحسب m و k أوتوماتيكياً لو ادّيتها capacity و error_rate.

تطبيق فعلي على PostgreSQL: الكود الكامل

الكود شغّال على Python 3.12 + pybloom-live 4.0 + PostgreSQL 16. الفلتر بيتحط في الـ application layer (أسرع، لكن لكل instance نسخة) أو في Redis عبر RedisBloom module (مشترك لكن +1ms latency).

from pybloom_live import ScalableBloomFilter
import psycopg

bf = ScalableBloomFilter(
    initial_capacity=10_000_000,
    error_rate=0.001,
    mode=ScalableBloomFilter.LARGE_SET_GROWTH,
)

def warm_filter_from_db(conn):
    with conn.cursor(name="email_stream") as cur:
        cur.itersize = 50_000
        cur.execute("SELECT email FROM users")
        for (email,) in cur:
            bf.add(email.lower())

def lookup_user(email: str, conn):
    key = email.lower()
    if key not in bf:
        return None
    with conn.cursor() as cur:
        cur.execute("SELECT id, name FROM users WHERE email = %s", (key,))
        return cur.fetchone()

def on_user_created(email: str):
    bf.add(email.lower())

الأرقام المقاسة على workload حقيقي (60M lookup/يوم، 87% misses) على instance Python واحد:

• قبل: P95 latency = 6.4ms، PostgreSQL CPU = 78%، فاتورة RDS db.r6g.xlarge = 1,840$/شهر.
• بعد: P95 latency = 0.3ms للـ misses و 4.1ms للـ hits، PostgreSQL CPU = 22%، نزلت لـ db.r6g.large = 410$/شهر.
• الذاكرة: 1.2MB في كل application instance (مهملة عملياً).
• التوفير: 1,430$ شهرياً (~78%)، بدون أي تغيير في الـ schema أو الـ application logic.

4 trade-offs خفية بتظهر بس في الإنتاج

1. مفيش delete في Bloom Filter العادي. لو user اتمسح من DB، الـ bits بتاعته في الـ filter بتفضل معلّمة. الحل: Counting Bloom Filter (بياخد ضعف الذاكرة لأن كل خانة تبقى counter بدل bit واحد)، أو إعادة بناء الفلتر من snapshot كل 24 ساعة في job منفصل.
2. الـ false positive rate بيزيد مع الوقت. لو حسبت على n = 10M ودخلت 14M عنصر فعلاً، الـ FP rate بيقفز من 1% لـ ~8%. الحل: استخدم ScalableBloomFilter اللي بيعمل auto-grow (زي اللي في الكود فوق)، أو راقب الـ fill ratio وأعد بناء الفلتر بحجم أكبر لما يعدّي 70%.
3. الـ cold start مشكلة حقيقية. لما instance جديد يقوم، لازم يـ load الـ filter من Redis أو يعيد بناءه من DB. الـ rebuild على 10M صف بياخد ~28 ثانية. الحل العملي: snapshot الـ filter لـ Redis أو S3 كل ساعة، وأي instance جديد بيـ load منه في ~400ms.
4. الـ consistency بين instances. لو instance A أضاف user جديد للـ filter وinstance B لسه ما اتحدّثش، B هيرفض lookup صحيح ويرجّعه كأنه مش موجود. الحل: Redis pub/sub بيبعت الـ additions لكل الـ instances في < 5ms، أو استخدم RedisBloom المشترك من الأول وتقبل الـ +1ms.

متى Bloom Filter بيكون اختيار غلط

متستخدمهوش لو:

• الـ hit rate ≥ 70% — مش هتوفر حاجة، هتزوّد latency بس على كل request.
• الـ dataset ≤ 100K — الـ DB index + query cache كافيين، الـ overhead مش يستاهل.
• محتاج إجابة دقيقة 100% بدون أي false positive — Bloom Filter بطبيعته احتمالي، استخدم HashMap عادي.
• الـ data بتتغيّر بشكل عنيف (deletes كتيرة وسريعة) — هنا Cuckoo Filter بيدعم الـ delete صح، أو HyperLogLog لو محتاج cardinality بس مش membership.

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

افتح أبطأ endpoint عندك في Datadog أو Grafana. اعمل breakdown للـ queries اللي بترجع 0 rows. لو النسبة ≥ 60% من إجمالي الـ reads، انت قدام candidate حقيقي لـ Bloom Filter. ابدأ بتطبيقه في الـ staging بـ Python أو Go، وقيس P95 latency و DB CPU قبل وبعد على نفس الـ workload لمدة 24 ساعة على الأقل قبل ما تروّح للإنتاج.

مصادر

• Burton H. Bloom — "Space/Time Trade-offs in Hash Coding with Allowable Errors"، Communications of the ACM، Vol. 13، No. 7، 1970.
• Andrei Broder & Michael Mitzenmacher — "Network Applications of Bloom Filters: A Survey"، Internet Mathematics، 2002.
• توثيق PostgreSQL 16 الرسمي — Index Types و Bitmap Heap Scan.
• Redis 7.4 — RedisBloom module documentation (redis.io/docs/stack/bloom).
• pybloom-live 4.0 — PyPI و GitHub repository.
• Bin Fan وآخرون — "Cuckoo Filter: Practically Better Than Bloom"، CoNEXT 2014.