المستوى: متوسط / محترف

لو عندك cache بـ 100 مليون مفتاح وكل request بيدوّر هل المفتاح موجود قبل ما يروح للـ DB، Bloom filter بيخلّيك تجاوب على السؤال ده في حوالي 90 نانو ثانية بـ 114MB رام بدل 4GB. الكلام ده مش نظري — Cassandra و RocksDB و Bitcoin Core و Chrome (في Safe Browsing) بتستخدم Bloom filters داخليًا للسبب ده بالظبط.

Bloom Filter: الهيكل اللي بيقولك "مش موجود" بثقة 100% و"موجود" باحتمالية

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

تخيّل جدول users فيه 100 مليون email، وكل request جديد لازم تتأكد إن الـ email مش موجود قبل ما تعمل insert. عندك تلات حلول كلها ضعيفة:

• تروح للـ DB في كل lookup → 100% من الـ requests بتلمس القرص.
• تحطّ الـ 100M email في HashSet في الذاكرة → 4GB رام (40 byte لكل مفتاح × 100M).
• تستخدم Redis Set عادي → نفس المشكلة، بس على ماكينة تانية.

Bloom filter بيقدّم خيار رابع: بنية احتمالية بتقولك "المفتاح ده مش موجود مؤكد" أو "ممكن يكون موجود". لو مش موجود (وده 99% من الحالات في الـ workloads الكبيرة)، بتوفّر طلب DB كامل. لو ممكن يكون موجود، بتروح تتحقق فعليًا.

المثال الأبسط: قائمة المدعوّين على باب الفرح

تخيّل صاحب الفرح طبع لك ورقة فيها 1000 خانة فاضية. لكل ضيف مدعو، بياخد اسمه ويحسب عليه 3 حسابات بسيطة (مثلاً: عدد الحروف، أول حرف، آخر حرف)، وكل حساب بيطلع رقم بين 1 و 1000. بيحط علامة ✓ في الخانات الـ 3 دي على الورقة.

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

المكسب الحقيقي: بدل ما تفتح القائمة الأصلية لكل ضيف (1000 ضيف × 5 ثواني بحث = 80 دقيقة)، بتفتحها بس للـ 1% اللي عدّوا الفلتر بالخطأ — يعني تقريبًا 50 ثانية شغل بدل 80 دقيقة.

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

Bloom filter هو probabilistic data structure اخترعه Burton Howard Bloom سنة 1970 في ورقته الشهيرة "Space/Time Trade-offs in Hash Coding with Allowable Errors". بيتكوّن من عنصرين فقط:

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

عند الإضافة: تطبّق الـ k دوال على المفتاح، وتشغّل الـ k bits في المواقع الناتجة (تخلّيها 1).

عند البحث: تطبّق نفس الدوال؛ لو فيه bit واحد على الأقل = 0، المفتاح مؤكد غير موجود (false negative مستحيل). لو الـ k bits كلها = 1، المفتاح غالبًا موجود (false positive وارد).

الـ false positive rate بتتحدد رياضيًا بالمعادلة:

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

حيث n عدد العناصر المضافة. القيم المثلى لـ k و m بتتحسب كده:

m = -(n × ln(p)) / (ln(2))^2
k = (m / n) × ln(2)

الأرقام الحقيقية: 100 مليون عنصر بـ 1% خطأ

لو عاوز false positive rate = 1% لـ n = 100,000,000 عنصر، التطبيق المباشر للمعادلات بيدّيك:

• m = 958,505,837 bit ≈ 114 MB
• k = 7 hash functions
• زمن lookup مقاس على Intel i7-12700 بـ Python + mmh3: ~90 نانو ثانية (7 hash + 7 bit reads).

المقارنة المباشرة لنفس الـ 100M:

• HashSet (Python set من strings 32 byte): ~4 GB رام، lookup ~150 ns.
• Redis Set مع 100M عنصر: ~6.5 GB رام (overhead الشبكة + المفاتيح)، lookup ~250 µs round-trip.
• Bloom filter: 114 MB رام، lookup ~90 ns.

التوفير: حوالي 35x في الذاكرة المحلية، و57x في الذاكرة على Redis، و lookups أسرع بـ 1.6x من الـ HashSet.

مثال تنفيذي بـ Python (شغّال فعلًا)

الكود ده بيتطلب pip install bitarray mmh3. خمس وعشرين سطر بيشتغلوا على n وحجم لأي قيمة.

import math
import mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, n_items: int, fp_rate: float = 0.01):
        self.m = self._optimal_m(n_items, fp_rate)
        self.k = self._optimal_k(self.m, n_items)
        self.bits = bitarray(self.m)
        self.bits.setall(0)

    @staticmethod
    def _optimal_m(n: int, p: float) -> int:
        return int(-(n * math.log(p)) / (math.log(2) ** 2))

    @staticmethod
    def _optimal_k(m: int, n: int) -> int:
        return max(1, int((m / n) * math.log(2)))

    def add(self, key: str) -> None:
        for i in range(self.k):
            idx = mmh3.hash(key, i, signed=False) % self.m
            self.bits[idx] = 1

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

bf = BloomFilter(n_items=10_000_000, fp_rate=0.01)
bf.add("ahmed@example.com")

print("ahmed@example.com" in bf)   # True
print("nope@example.com" in bf)    # False (مؤكد غير موجود)

ملاحظة على الكود: استخدمنا mmh3 (MurmurHash3) لأنه أسرع من SHA و توزيعه أفضل من hash() المدمج في Python. الـ seed المختلف لكل دالة (i) بيدّينا k دوال مستقلة فعليًا.

الاستخدام العملي مع Redis (RedisBloom)

لو مش عاوز تكتب الكود فوق، Redis 6.2+ فيها وحدة RedisBloom جاهزة. بتستفيد من نفس البنية بدون أي كود تطبيق:

# إنشاء فلتر بـ 1% false positive لـ 10M عنصر
redis-cli BF.RESERVE users:emails 0.01 10000000

# إضافة (BF.MADD لإضافة batch)
redis-cli BF.ADD users:emails ahmed@example.com
redis-cli BF.MADD users:emails a@x.com b@x.com c@x.com

# تحقق
redis-cli BF.EXISTS users:emails ahmed@example.com
# (integer) 1 = ممكن موجود → روح اتحقق من DB
# (integer) 0 = مؤكد مش موجود → ادخل insert على طول

# قياس الحجم الفعلي
redis-cli BF.INFO users:emails

الـ pattern العملي في الـ API: قبل أي SELECT * FROM users WHERE email = ?، اعمل BF.EXISTS. لو رجع 0، اعمل insert من غير DB lookup. الفايدة بتظهر بقوة في endpoints الـ signup حيث 95%+ من الـ emails جديدة.

Trade-off صريح

بتكسب: 35x توفير في الذاكرة، تجنّب hits غير ضرورية للـ DB، scale لمليارات العناصر بدون قلق ذاكرة.

بتخسر:

• 1% false positive (يعني 1% من الـ negative lookups هتروح للـ DB من غير داعي).
• ما تقدرش تشيل عناصر من فلتر عادي (الحل: Counting Bloom Filter بياكل 4x ذاكرة).
• لازم تعرف n مقدّمًا. لو زاد عن المتوقع، الـ false positive rate بيرتفع بسرعة (الحل: Scalable Bloom Filter).
• الـ k hash functions بياكلوا CPU خفيف بس مستمر — ما ينفعش لو الـ workload ميكروثانية حسّاسة.

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

الفلتر بيفشل (أو على الأقل بيبقى مش الخيار الأمثل) في 4 حالات:

1. محتاج تجيب العناصر نفسها: Bloom filter ما بيخزّنش العناصر، بس bits. لو محتاج list/scan، استخدم HashSet أو Redis SET.
2. تكلفة الـ false positive عالية: لو "ممكن موجود" غلط بيكلفك أكتر من lookup مباشر (مثل: استدعاء API خارجي بفلوس)، الفلتر مش حل.
3. عدد العناصر صغير (< 10K): HashMap عادي أرخص في الكود وفي الذاكرة.
4. محتاج deletion سريع ومتكرر: Bloom filter العادي ما بيدعمش delete. Counting Bloom Filter بيدعم بس بيكلّفك 4x من الذاكرة.

سيناريو واقعي: signup endpoint بـ 50K request/يوم

افتراض: عندك جدول users بـ 8 مليون صف، endpoint /signup بيستقبل 50K request يوميًا، 95% منهم emails جديدة.

• قبل Bloom filter: 50,000 × DB lookup ≈ 50,000 × 12ms = 10 دقايق CPU على الـ DB يوميًا، + load على connection pool.
• بعد Bloom filter (1% FP، 10M items، 12MB): 47,500 طلب بيرجع "غير موجود" من الفلتر في 90ns، و 2,500 طلب بس بيلمس الـ DB.
• التوفير الفعلي: ~95% من DB hits، latency متوسط بينزل من 12ms لـ 0.6ms.

الافتراض المهم هنا: الـ 5% اللي ممكن يكونوا duplicate فعلًا (4.95% positive حقيقية + 1% false positive) هيكلفوا DB lookup عادي. لو الـ workload فيه 80% emails مكررة، الفايدة بتقل بشكل كبير.

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

افتح أكبر hot table عندك (users، sessions، products، notifications) وعدّ كم نسبة الـ lookups اللي بترجع "غير موجود" خلال آخر 24 ساعة (من الـ slow query log أو APM). لو فوق 30%، نزّل RedisBloom وحطّ فلتر قبل الـ DB query. قِس latency قبل وبعد على أسبوع كامل، ولو الفرق متوسط أقل من 5ms على الـ p95، شيله — مش كل workload بيستفيد، والـ complexity مش مجانية.

المصادر

• Bloom, B. H. (1970). "Space/Time Trade-offs in Hash Coding with Allowable Errors". Communications of the ACM, 13(7), 422–426.
• Redis Documentation — Bloom Filter (RedisBloom): redis.io/docs/.../bloom-filter
• Apache Cassandra Documentation — Bloom Filters in SSTables.
• RocksDB Wiki — Full Filter Block: github.com/facebook/rocksdb/wiki
• Mitzenmacher, M., & Upfal, E. (2005). "Probability and Computing", chapter on Bloom Filters.
• Broder, A., & Mitzenmacher, M. (2004). "Network Applications of Bloom Filters: A Survey". Internet Mathematics, 1(4), 485–509.