Bloom Filter: وفّر 97% من ذاكرة فحص العضوية مقابل خطأ 1%

مستوى المقال: متوسط. المقال مناسب لو انت مرتاح مع الـ hashing و الـ set و كتابة كلاس في Python، وعايز تفهم هيكل بيانات احتمالي بتستخدمه قواعد بيانات حقيقية زي Cassandra و Bigtable.

لو بتخزّن مليون إيميل في set عشان تتأكد إن الإيميل اتسجّل قبل كده، انت بتاكل عشرات الميجابايتات على سؤال إجابته "أه" أو "لأ". الـ Bloom Filter بيجاوب نفس السؤال في حوالي 1.2 ميجا. الثمن الوحيد: أحيانًا بيقول "ربما موجود" وهو مش موجود، بنسبة تظبطها انت.

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

كتير من الأنظمة محتاجة تسأل سؤال واحد بسرعة: "هل العنصر ده شفته قبل كده؟". أمثلة: هل الـ URL ده في قايمة المواقع الخبيثة؟ هل الـ user ده اتبعتله الإشعار ده؟ هل المفتاح ده موجود في ملف على الديسك قبل ما أقرأه؟

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

الفكرة بمثال بسيط الأول

تخيّل حارس على باب حفلة. بدل ما يحفظ أسماء الألف مدعو كاملة، عنده ورقة فيها 100 خانة فاضية. كل ما حد يتسجّل، الحارس بياخد اسمه ويطبّق عليه 3 قواعد بسيطة بتحوّل الاسم لـ 3 أرقام خانات، وبيعلّم عليهم بعلامة.

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

دلوقتي بالتفصيل العلمي: الـ Bloom Filter هو مصفوفة من m بِت كلها أصفار في البداية، مع k دوال هاش مستقلة. عشان تضيف عنصر، بتمرّره على الـ k دوال، كل دالة بتطلّع رقم خانة بين 0 و m-1، وبتضبط الخانات دي على 1. عشان تسأل عن عنصر، بتحسب نفس الـ k خانات: لو واحدة منهم 0، فالعنصر أكيد مش موجود. لو كلهم 1، فالعنصر ربما موجود.

النتيجة المهمة هنا: الـ Bloom Filter ما بيعملش false negative أبدًا. لو قال "مش موجود"، ده يقين. هو بس بيعمل false positive أحيانًا. ده اللي بيخليه مفيد كـ "فلتر" قبل عملية غالية: لو قال "مش موجود"، وفّرت العملية الغالية تمامًا.

الكود: Bloom Filter شغّال في Python بدون مكتبات

الكود ده بيبني الكلاس بالكامل بـ hashlib فقط. بنستخدم حيلة الـ double hashing (Kirsch–Mitzenmacher): بنولّد هاشين بس وبنركّبهم خطيًا عشان نطلّع k خانات، بدل ما نشغّل k دوال منفصلة.

import math
import hashlib

class BloomFilter:
    def __init__(self, n, fp_rate=0.01):
        # m: عدد البتات المثالي،  k: عدد دوال الهاش المثالي
        self.m = math.ceil(-(n * math.log(fp_rate)) / (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()
        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 // 8] |= 1 << (pos % 8)

    def __contains__(self, item):
        return all(
            self.bits[pos // 8] >> (pos % 8) & 1
            for pos in self._positions(item)
        )

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

print("ahmed@example.com" in bf)   # True  (موجود فعلاً)
print("nada@example.com" in bf)    # False (أكيد مش موجود)
print(f"m={bf.m} bit ≈ {bf.m/8/1024/1024:.2f} MB, k={bf.k}")
# m=9585059 bit ≈ 1.14 MB, k=7

المخرج بيقول إن مليون عنصر بنسبة خطأ 1% محتاجين حوالي 9.59 مليون بِت، يعني ~1.14 ميجا، و7 دوال هاش. لاحظ إن الرقم ده ثابت سواء كان العنصر إيميل قصير أو URL طويل 200 حرف.

سيناريو واقعي بالأرقام

قول عندك خدمة فيها مليون إيميل مسجّل، وعايز تمنع التسجيل المكرر. لو خزّنتهم في set في Python، كل إدخال بياخد مرجع للسترينج زائد overhead الـ set، فبتوصل بسهولة لـ 50–90 ميجا في الرام لمليون إيميل. الـ Bloom Filter بنفس المليون عند خطأ 1% بياخد ~1.14 ميجا. ده توفير في حدود 97%–98% من الذاكرة، والفحص بيفضل O(k) — سبع عمليات هاش ثابتة لكل سؤال.

ده مش مثال نظري. قواعد بيانات زي Apache Cassandra و Google Bigtable بتحط Bloom Filter في الرام لكل ملف SSTable على الديسك. قبل ما تعمل قراءة عشوائية غالية من الديسك (ممكن تكون من ~100 ميكروثانية على SSD لـ عدة ميلي ثانية على HDD)، بتسأل الفلتر الأول. لو قال "المفتاح ده مش هنا"، بتتجنّب القراءة بالكامل. متصفح Chrome كمان استخدم نفس الفكرة في Safe Browsing لفحص الروابط الخبيثة محليًا قبل ما يسأل السيرفر.

الـ trade-offs بوضوح

كل قرار هنا ليه ثمن. خلّيك صريح معاه:

• بتكسب: ذاكرة صغيرة جدًا (~9.6 بِت لكل عنصر عند خطأ 1%، أي ~1.2 بايت)، وفحص بزمن ثابت مهما كبر العنصر.
• بتخسر: إيجابيات كاذبة. لما الفلتر يقول "ربما"، لازم يبقى عندك مصدر حقيقي تتحقق منه (الداتابيز مثلاً). الفلتر بيقلّل القراءات، مش بيلغيها.
• الافتراض: انت عارف عدد العناصر التقريبي n مقدمًا عشان تظبط m و k. لو العناصر الفعلية عدّت اللي خطّطتله، نسبة الخطأ بترتفع بسرعة فوق الـ 1%.
• قيد مهم: النسخة الأساسية مفيهاش حذف. ما تقدرش تصفّر بِت لأنه ممكن يكون مشترك مع عنصر تاني. ولا تقدر تسترجع العناصر نفسها — الفلتر بيخزّن آثار، مش بيانات.

الصيغة اللي بتحكم الخطأ هي تقريبًا (1 - e^(-kn/m))^k. عشان تنزّل الخطأ من 1% لـ 0.1%، محتاج تزوّد البتات لكل عنصر من ~9.6 لـ ~14.4، يعني الذاكرة بتكبر بنسبة ~50% مقابل خطأ أقل 10 مرات.

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

• لو محتاج يقين 100% بوجود العنصر، ومعندكش مصدر تتحقق منه عند إجابة "ربما". الإيجابي الكاذب هيغُشّك.
• لو محتاج حذف متكرر للعناصر. ساعتها استخدم Counting Bloom Filter أو Cuckoo Filter اللي بيدعموا الحذف.
• لو عدد العناصر صغير (آلاف قليلة). الـ set العادي أبسط، أسرع في الكتابة، وفرق الذاكرة مش هيفرق معاك.
• لو محتاج تسترجع العناصر نفسها أو تعدّها. ده مش شغل الـ Bloom Filter من الأساس.

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

انسخ الكلاس فوق، حطّ فيه مليون سترينج عشوائي، وقيس استهلاك الذاكرة بـ sys.getsizeof(bf.bits) مقابل نفس البيانات في set. بعدين غيّر fp_rate من 0.01 لـ 0.001 وراقب m بيكبر إزاي. لو الـ false positive عندك عدّى الـ 1% بكتير، يبقى n الحقيقي أكبر من اللي خطّطتله — وده أول مكان تدوّر فيه.

المصادر

• Bloom, B. H. (1970). "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM.
• Kirsch, A. & Mitzenmacher, M. (2006). "Less Hashing, Same Performance: Building a Better Bloom Filter" — أصل حيلة الـ double hashing.
• Apache Cassandra Documentation — Bloom filters (operating/bloom_filters).
• Chang, F. et al. (2006). "Bigtable: A Distributed Storage System for Structured Data", OSDI — استخدام Bloom filters لتقليل قراءات الديسك.
• RedisBloom Documentation — Bloom filter module.
• Wikipedia: Bloom filter — للصيغ الرياضية وحساب m و k المثاليين.