المستوى المطلوب: متوسط — يفترض إنك بتشتغل على PostgreSQL أو MySQL، عندك خبرة Python أساسية، وفاهم يعني إيه hash function ولو على المستوى السطحي. لو لسه مبتدئ، فيه قسم في النص بيشرح الفكرة بمثال بوّاب الفندق قبل ما ندخل في الرياضيات.

Bloom Filters: ازاي توفّر 99% من استعلامات قاعدة بياناتك بـ 16 كيلوبايت ذاكرة بس

لو الـ login endpoint بتاعك بيستقبل 4,500 محاولة دخول في الدقيقة، و 3,800 منهم بأسماء مستخدمين مش موجودة أصلاً، انت بتضيع 84% من طاقة قاعدة البيانات على بحث بيرجع صفر. Bloom Filter في 50 سطر Python بيرفض المحاولات دي قبل ما توصل لـ DB، باستهلاك 119 كيلوبايت ذاكرة لـ 100 ألف مستخدم.

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

قاعدة البيانات بتشتغل بكفاءة لما السؤال له إجابة. الكارثة بتبدأ لما السؤال إجابته "غير موجود". في الحالة دي، حتى مع index كويس، الـ planner لازم يفتح صفحات الـ B-tree ويتأكد، ويرجّعلك صفر. لو ده بيحصل آلاف المرات في الثانية، الـ DB بتشتغل 100% CPU في حاجة عديمة الفائدة، والمستخدم اللي عنده اسم صحيح بيدفع التمن في زمن استجابة عالي.

المفهوم بمثال بسيط جداً

تخيّل بوّاب فندق عنده دفتر فيه أسماء النزلاء. كل ما حد ييجي الباب يقوله اسمه. لو الاسم مش في الدفتر، البوّاب لازم يقفل الكتاب ويفتح صفحة صفحة عشان يتأكد. ده بياخد وقت.

دلوقتي خلّي البوّاب عنده ورقة صغيرة فيها 1000 خانة فاضية. كل ما يدخل نزيل جديد، البوّاب بياخد اسمه ويحطّ علامة في 3 خانات محسوبة من الاسم — مش الاسم نفسه، بصمة منه. لما حد ييجي يدّعي إنه نزيل، البوّاب بيشوف الـ 3 خانات بتاعت اسمه. لو خانة واحدة فيهم فاضية، يبقى أكيد مش نزيل، ومش محتاج يفتح الدفتر أصلاً. لو الـ 3 ممتلين، يبقى يمكن نزيل، يفتح الدفتر يتأكد. الورقة الصغيرة دي اسمها Bloom Filter.

التعريف العلمي بالظبط

Bloom Filter هو bit array بطول m بت مع k دوال hash مستقلة. لما تضيف عنصر، بتمرّر العنصر على الـ k دوال، وبتشغّل الـ k bits اللي بترجعهم (set to 1). لما تستعلم عن وجود عنصر، بتعيد نفس العملية؛ لو أي bit منهم = 0، يبقى العنصر مش موجود قطعاً. لو كلهم = 1، يبقى غالباً موجود مع احتمال false positive.

الورقة الأصلية كتبها Burton Howard Bloom سنة 1970 في Communications of the ACM. النتيجة الرياضية الأهم: عشان تضمن نسبة false positive قدرها p على n عنصر، محتاج m = -n · ln(p) / (ln 2)² بت، وعدد دوال hash المثالي k = (m/n) · ln 2. للقيم الشائعة 1% FPR و 100K عنصر تطلع تقريباً 958,506 بت ≈ 117 كيلوبايت، و 7 hash functions. الرقم 16KB في العنوان بيناسب 10K عنصر بنفس النسبة.

كود Python شغّال

هتحتاج pybloom-live لو الـ filter محلي داخل الـ application، أو redis 7+ مع وحدة RedisBloom لو عايز كل الـ instances تستفيد من نفس الـ filter:

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.