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
