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

الـ Bloom Filter: تشيك على وجود عنصر في مجموعة ضخمة بذاكرة أقل 83 مرة

لو محتاج تعرف "هل الرابط ده اتخزّن قبل كده؟" على مليون عنصر، الـ set العادي هياكل حوالي 100 ميجابايت. الـ Bloom Filter بيعمل نفس الفحص في ~1.2 ميجابايت، مقابل ثمن واحد: 1% إجابات "ممكن موجود" وهي مش موجودة. هنا هتعرف إزاي يشتغل، وإمتى يستحق الثمن ده.

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

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

الفكرة بمثال قبل التعريف

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

علميًا: الـ Bloom Filter هو مصفوفة بتات (bit array) طولها m، مع عدد k من دوال التجزئة (hash functions). لإضافة عنصر، بنمرّره على الـ k دوال، وكل دالة بتطلّع رقم خانة نضبطها على 1. للفحص، بنعمل نفس الشيء: لو أي خانة من الـ k بتساوي 0، العنصر مضمون إنه مش موجود. لو كلهم 1، العنصر "ربما موجود". عشان كده الـ Bloom Filter بيدّي 0% سلبيات كاذبة (مش بيقول "مش موجود" لعنصر موجود) لكن نسبة إيجابيات كاذبة أكبر من صفر.

الحساب والكود

الحجم مش تخمين، فيه معادلة. لعدد عناصر n ونسبة إيجابية كاذبة مستهدفة p: عدد البتات m = -n.ln(p) / (ln2)^2، وعدد الدوال المثالي k = (m/n).ln2. لمليون عنصر و p = 1%: تطلع m ~ 9,585,059 بت (~1.2 ميجابايت) و k = 7 دوال.

import math, mmh3
from bitarray import bitarray

class BloomFilter:
    def __init__(self, n, p):
        self.m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))
        self.k = math.ceil((self.m / n) * math.log(2))
        self.bits = bitarray(self.m); self.bits.setall(0)

    def add(self, item):
        for i in range(self.k):
            self.bits[mmh3.hash(item, i) % self.m] = 1

    def __contains__(self, item):
        return all(self.bits[mmh3.hash(item, i) % self.m] for i in range(self.k))

bf = BloomFilter(n=1_000_000, p=0.01)
for i in range(1_000_000):
    bf.add(f"user_{i}")

print(bf.m, bf.k)          # ~9585059 bit | 7 hashes = ~1.2 MB
print("user_5" in bf)      # True
print("ghost_5" in bf)     # False غالبا، وأحيانا True (ايجابية كاذبة)

الكود ده شغّال فعلًا (محتاج pip install mmh3 bitarray). لو عدّيت عليه 100 ألف عنصر مش مضاف، هتلاقي عدد الـ True القريب من 1000 عنصر، أي 1% بالظبط زي المستهدف.

سيناريو واقعي

ده مش تمرين نظري. Apache Cassandra و RocksDB و HBase بيحطّوا Bloom Filter على كل ملف SSTable عشان يتجنّبوا قراءة قرص لمفتاح مش موجود، وده بيوفّر ملايين القراءات العشوائية. متصفّح Chrome استخدم بنية شبيهة لفحص الروابط الخبيثة محليًا قبل ما يسأل السيرفر. وشبكات الـ CDN بتستخدمها في مشكلة "one-hit-wonder": ما تكاشّش object غير لما يتطلب مرتين، فتوفّر مساحة كاش كبيرة.

الـ trade-offs بوضوح

بتكسب: ذاكرة أقل حوالي 83 مرة، واستعلام بزمن ثابت O(k) مش متعلق بحجم المجموعة. بتخسر حاجتين. الأولى: نسبة إيجابيات كاذبة (اضبطها بـ p، لكن كل ما صغّرتها كل ما كبّرت الذاكرة). التانية والأهم: ماتقدرش تحذف عنصر، لأن البت الواحد ممكن يكون مشترك بين أكتر من عنصر، فلو صفّرته هتكسر عناصر تانية. لو محتاج حذف، استخدم Counting Bloom Filter (بيخزّن عدّاد بدل بت) بتكلفة ذاكرة تقريبًا 4 أضعاف.

الافتراض اللي الكلام ده مبني عليه: إنك تقدر تتحمّل 1% "غالبًا موجود" غلط، وإن أهم حاجة عندك هي إن جواب "مش موجود" يكون مضمون 100%. لو ده مش وضعك، الـ Bloom Filter مش الأداة.

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

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

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

ثبّت mmh3 و bitarray، اضبط n و p على أرقام بياناتك الحقيقية، وشغّل الكود فوق على عيّنة من عناصر مش مضافة عشان تقيس نسبة الإيجابيات الكاذبة الفعلية. لو طلعت أعلى بكتير من p، غالبًا الـ k عندك غلط أو دالة الهاش ضعيفة، فراجعهم قبل ما تعتمد عليه في الإنتاج.

المصادر

• Bloom, B. H. (1970). "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM 13(7). المرجع الأصلي للبنية.
• Kirsch, A. and Mitzenmacher, M. (2008). "Less Hashing, Same Performance: Building a Better Bloom Filter". أساس تقنية الـ double hashing المستخدمة في التطبيقات العملية.
• توثيق Apache Cassandra، قسم Bloom filters (cassandra.apache.org).
• توثيق RedisBloom / Redis Stack، probabilistic data structures (redis.io).
• معادلات الحجم ونسبة الخطأ: مقالة Bloom filter على Wikipedia، قسم "Probability of false positives".