الـ Bloom Filter: تتأكد إن العنصر مش موجود بذاكرة صغيرة جدًا

مستوى المقال: محترف — بيفترض إنك متعامل قبل كده مع الهاش والداتابيز، وعايز توفّر ذاكرة واستعلامات في نظام كبير.

لو عندك مليون إيميل مسجّل وعايز تتأكد بسرعة إن إيميل جديد مش موجود، من غير ما تضرب الداتابيز في كل مرة، الـ Bloom Filter بيعمل ده بذاكرة حوالي 1.1 ميجا بدل عشرات الميجات. المقال ده هيوريك إزاي، بمثال، بكود شغّال، وبالأرقام.

الـ Bloom Filter: تتأكد إن العنصر مش موجود بذاكرة صغيرة جدًا

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

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

الفكرة: البواب اللي بيقولك "أكيد لأ" بس مش بيأكدلك "أيوه"

تخيّل بواب عند باب حفلة، ومعاه ورقة فيها علامات صغيرة بدل أسماء المدعوين كاملة. لما حد ييجي، البواب بيبص على شوية خانات مرتبطة باسمه. لو واحدة منهم فاضية، يبقى الشخص ده أكيد مش مدعو، وبيرفضه فورًا من غير ما يفتح كشف الأسماء الطويل. لكن لو كل الخانات معلّمة، البواب بيقول "غالبًا مدعو" وبيروح يتأكد من الكشف الحقيقي. ساعات بيحصل تشابه في العلامات فيوقّف حد مش مدعو للمراجعة، بس عمره ما هيرفض مدعو حقيقي بالغلط.

علميًا: الـ Bloom Filter عبارة عن مصفوفة بتات (m bit) كلها أصفار في البداية، ومعاها عدد k من دوال الهاش. عند الإضافة، بنمرّر العنصر على الـ k دوال، وكل واحدة بتطلع رقم خانة، وبنخلّي البت بتاعها = 1. عند السؤال، بنحسب نفس الخانات: لو أي بت منهم = 0 يبقى العنصر مؤكد غير موجود؛ لو كلهم = 1 يبقى غالبًا موجود (مع احتمال إيجابية خاطئة). النتيجة السلبية دايمًا يقينية 100%، والإيجابية هي بس اللي فيها احتمال خطأ.

الحل بالكود: تنفيذ شغّال في 20 سطر

الكود ده بيشتغل على بايثون من غير أي مكتبة خارجية. بيستخدم تقنية الهاش المزدوج (Kirsch-Mitzenmacher) عشان يولّد k دوال من هاشين بس:

import math, hashlib

class BloomFilter:
    def __init__(self, n, p):
        # m: حجم المصفوفة بالبت، k: عدد دوال الهاش المثالي
        self.m = math.ceil(-(n * math.log(p)) / (math.log(2) ** 2))
        self.k = max(1, round((self.m / n) * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _positions(self, item):
        data = item.encode("utf-8")
        h1 = int.from_bytes(hashlib.sha256(data).digest()[:8], "big")
        h2 = int.from_bytes(hashlib.md5(data).digest()[:8], "big")
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        for pos in self._positions(item):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def __contains__(self, item):
        return all(self.bits[pos >> 3] & (1 << (pos & 7))
                   for pos in self._positions(item))

# تجربة: مليون مستخدم، ومعدل خطأ مستهدف 1%
bf = BloomFilter(n=1_000_000, p=0.01)
for i in range(1_000_000):
    bf.add(f"user{i}@mail.com")

print(bf.m // 8 // 1024, "كيلوبايت")   # ~1170
print("k =", bf.k)                      # 7
print("user7@mail.com" in bf)           # True  (موجود)
print("ghost@mail.com" in bf)           # False (غير موجود بيقين)

الأرقام: ليه ده مكسب حقيقي

لمليون عنصر ومعدل خطأ 1%، المعادلة m = -n·ln(p) / (ln2)² بتطلع حوالي 9.585 مليون بت، يعني ≈ 1.14 ميجابايت، بمعدل 9.6 بت لكل عنصر بس. عدد دوال الهاش المثالي k = (m/n)·ln2 ≈ 7. قارن ده بتخزين مليون إيميل كنص في set بايثون: بيوصل بسهولة لـ 90–120 ميجابايت مع overhead الكائنات. يعني وفّرت أكتر من 98% من الذاكرة. والبحث بياخد زمن ثابت O(k) مهما كبر عدد العناصر.

الفايدة العملية الأكبر: لو 95% من الإيميلات الجديدة غير موجودة، الـ Bloom Filter بيرد عليها بـ "لأ" فورًا من الرام، فبتوفّر حوالي 95% من استعلامات الداتابيز على مسار التحقق ده.

الـ trade-offs اللي لازم تعرفها

• إيجابية خاطئة موجودة: لما الفلتر يقول "غالبًا موجود"، لازم تعمل تحقق حقيقي من الداتابيز. بتكسب توفير على الـ "لأ"، وبتخسر إنك محتاج طبقة تأكيد على الـ "أيوه".
• مفيش حذف: النسخة القياسية ما بتدعمش delete، لأن تصفير بت ممكن يكسر عناصر تانية بتشاركه. لو محتاج حذف، استخدم Counting Bloom Filter مقابل ذاكرة أكبر.
• مش بتقدر تسترجع العناصر: الفلتر بيرد بـ نعم/لا بس، مبيخزّنش القيم نفسها.
• الدقة مرتبطة بالحجم مقدمًا: لو زوّدت العناصر عن اللي خطّطتله، معدل الخطأ بيرتفع. الافتراض إنك عارف n تقريبي.

متى لا تستخدم هذه الطريقة

لو الداتا صغيرة وبتترتّب على إندكس عادي في الداتابيز، مش محتاج تعقيد زيادة، استخدم unique index وخلاص. ولو الإيجابية الخاطئة غير مقبولة نهائيًا ومفيش عندك طبقة تحقق تانية (مثلًا قرار أمني نهائي بدون مراجعة)، الـ Bloom Filter مش أداتك. وكمان لو محتاج حذف متكرر أو استرجاع العناصر، ابعد عن النسخة القياسية.

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

حط RedisBloom قدّام استعلام "هل الإيميل مسجّل" باستخدام BF.RESERVE myfilter 0.01 1000000 ثم BF.ADD وBF.EXISTS. شغّله لمدة يوم، وقيس نسبة الاستعلامات اللي اترفضت من الرام قبل ما توصل للداتابيز. لو النسبة قريبة من نسبة الإيميلات الجديدة عندك، يبقى الفلتر شغّال صح.

المصادر

• الورقة الأصلية: Burton H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, 1970.
• معادلات الحجم وعدد الدوال المثالي: Wikipedia — Bloom filter (قسم Optimal number of hash functions).
• تقنية الهاش المزدوج: Kirsch & Mitzenmacher, "Less Hashing, Same Performance", 2006.
• الاستخدام العملي: RedisBloom Documentation (أوامر BF.RESERVE / BF.ADD / BF.EXISTS).
• أمثلة إنتاجية: Apache Cassandra Docs — Bloom filters لتقليل قراءات القرص من ملفات SSTable.