Bloom Filters للمتوسط: وفّر 99% من استعلامات DB غير المفيدة بـ 16KB

from pybloom_live import BloomFilter
import psycopg2

bloom = BloomFilter(capacity=100_000, error_rate=0.01)

# تحميل أولي من DB مرة واحدة عند الـ start
conn = psycopg2.connect("dbname=app user=app")
with conn.cursor() as cur:
    cur.execute("SELECT username FROM users")
    for (username,) in cur:
        bloom.add(username)

def user_might_exist(username: str) -> bool:
    return username in bloom

def login(username: str, password: str):
    if not user_might_exist(username):
        # ما لمسناش DB أصلاً
        return {"error": "invalid credentials"}, 401
    return verify_against_db(username, password)

# لما تسجّل user جديد
def register(username: str, password: str):
    insert_into_db(username, password)
    bloom.add(username)  # حافظ على الاتساق

الفكرة الأساسية: 99% من المحاولات الخاطئة بتترفض في حدود 8 ميكروثانية بدون استشارة DB. الـ 1% الباقي false positives بتعدّي عادي للـ DB وبتترفض هناك زي ما كانت بتترفض قبل.

الأرقام الفعلية: قبل وبعد

قياس على service بـ 4,500 RPS، PostgreSQL 16 على db.r6g.large، 100,000 مستخدم، 84% من المحاولات بأسماء غير موجودة:

• قبل: P50 = 14ms، P99 = 38ms، استهلاك CPU على DB = 71%.
• بعد: P50 = 0.4ms للمحاولات المرفوضة، P99 = 22ms، استهلاك CPU على DB = 9%.
• الذاكرة المستهلكة: 119KB في الـ application process لكل instance.
• تكلفة DB instance: نزّلنا الـ instance من r6g.large لـ r6g.medium، وفّرنا 88$ شهرياً.

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

1. False positives ممكنة، false negatives مستحيلة. ده شرط أساسي، مش رفاهية. لو حد قال لك "Bloom Filter اللي عمله ممكن يقول مش موجود وهو موجود"، ده مش Bloom Filter — ده شخص فاهم غلط.
2. مش بتقدر تحذف عنصر. الـ classic Bloom ما فيهوش delete، لإن نفس الـ bit ممكن يكون متشغّل من عناصر تانية. محتاج delete؟ استخدم Counting Bloom Filter بتاكل ذاكرة 4x، أو Cuckoo Filter كبديل أحدث.
3. المحافظة على الاتساق. لو ضفت user في DB ونسيت تضيفه في الـ Bloom، هيرجّع false negative وهيرفض user حقيقي. الحل: ضيف في نفس الـ transaction، أو اعمل rebuild يومي من DB.
4. التحميل الأولي. 10 مليون user بياخدوا 12 ثانية تحميل عند الـ start. الحل: persist الـ filter على ملف أو Redis، حمّله من هناك بدل ما تعيد بناءه.

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

تجاهل الموضوع ده تماماً لو:

• الـ DB query بيرجع نتيجة غير صفر في معظم الحالات. الـ Bloom طبقة فلترة للسؤال السلبي، مش حل عام.
• عدد العناصر أقل من 10K — الـ overhead أكبر من الفائدة، استخدم set عادي في الذاكرة.
• محتاج counts بدل boolean exists — استخدم HyperLogLog مش Bloom.
• الـ DB عندها index سريع جداً والـ query أصلاً بيرجع في 0.5ms — مفيش مشكلة تحلّها.
• متطلب legal أو compliance بيمنع false positives في الـ pipeline أصلاً.

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

ابدأ بأسرع نقطة ROI: شيّك الـ login endpoint بتاعك. لو 60% أو أكتر من المحاولات بترجع "user not found"، ركّب pybloom-live ولفّ الـ query في الـ helper اللي فوق. لو الفرق في P99 أكتر من 30%، انقل الـ filter لـ Redis Bloom عشان كل instances الـ app تستفيد من نفس النسخة. بعد كده فكّر في الـ endpoints التانية: GET /api/v1/posts/:slug، SELECT على email، أي endpoint بيعدّي قيمة جاية من المستخدم على DB.

المصادر

• Burton H. Bloom (1970), "Space/Time Trade-offs in Hash Coding with Allowable Errors," Communications of the ACM, Vol. 13, No. 7, pp. 422–426.
• Andrei Broder, Michael Mitzenmacher (2004), "Network Applications of Bloom Filters: A Survey," Internet Mathematics, Vol. 1, No. 4.
• RedisBloom Module Documentation — redis.io/docs/data-types/probabilistic/bloom-filter.
• PostgreSQL 16 Documentation, "bloom — bloom filter index access method" — postgresql.org/docs/16/bloom.html.
• Apache Cassandra Documentation, "How is data read?" — استخدام Bloom Filters في طبقة الـ SSTable.
• pybloom-live على PyPI — توثيق capacity و error_rate.