فلتر بلوم: تعرف إن العنصر "أكيد مش موجود" في خانة واحدة

مستوى المقال: محترف. يفترض أنك تعرف دوال الهاش، تحليل التعقيد Big-O، وأساسيات قراءة قواعد البيانات من القرص.

فلتر بلوم: تعرف إن العنصر "أكيد مش موجود" قبل ما تلمس قاعدة البيانات

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

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

عندك 50 مليون اسم مستخدم. مع كل تسجيل جديد لازم تتأكد إن الاسم مش متسجّل قبل كده. لو خزّنت الأسماء كلها في set في الذاكرة، ده حوالي 1 جيجابايت (بمتوسط 20 بايت للاسم مع overhead البنية). ولو رحت للقرص في كل طلب، كل استعلام بياخد ملّي ثانية أو اتنين على الأقل. المشكلة الحقيقية: أغلب الأسماء الجديدة فعلًا مش موجودة، فإنت بتصرف أغلى مواردك على إجابة سلبية متكررة.

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

تخيّل حارس على باب نادي معاه دفتر فيه 10 خانات صغيرة فاضية، مش أسماء. أول ما عضو يدخل، الحارس بيحسب من اسمه 3 أرقام ثابتة (مثلًا 1 و4 و7) ويعلّم الخانات دي. بعدين ييجي حد يسأل: "فلان دخل؟" الحارس بيحسب نفس الـ 3 أرقام من الاسم؛ لو لقى أي خانة منهم فاضية، يبقى الشخص ده أكيد ما دخلش. لو الثلاثة كلهم متعلّمين، يقول "غالبًا دخل" ويروح يراجع كشف الحضور الحقيقي عشان يتأكد.

علميًا: فلتر بلوم بنية بيانات احتمالية اخترعها Burton H. Bloom سنة 1970. هو مصفوفة من m بت كلها أصفار في البداية، مع k دوال هاش مستقلة. عملية الإضافة add(x): احسب k مواضع من x وحوّل البتات في المواضع دي لـ 1. عملية الفحص contains(x): احسب نفس الـ k مواضع؛ لو كلها 1 رجّع "ربما موجود"، ولو أي واحدة 0 رجّع "أكيد غير موجود". الخاصية المفتاحية: مفيش false negative إطلاقًا (اللي دخل مستحيل يظهر إنه مش موجود)، لكن ممكن يحصل false positive.

إزاي بيشتغل بالظبط — كود شغّال

ده تنفيذ مختصر بالـ Python باستخدام bytearray و hashlib. ركّز إن التخزين بتات فعلية على مستوى البايت، مش set بيخزّن العناصر:

import hashlib, math

class BloomFilter:
    def __init__(self, m_bits, k):
        self.m = m_bits
        self.k = k
        self.bits = bytearray(m_bits // 8 + 1)

    def _positions(self, item):
        h = hashlib.sha256(item.encode()).digest()
        h1 = int.from_bytes(h[:8], "big")
        h2 = int.from_bytes(h[8:16], "big")
        # double hashing: g_i = h1 + i*h2 (Kirsch-Mitzenmacher)
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, item):
        for p in self._positions(item):
            self.bits[p // 8] |= (1 << (p % 8))

    def contains(self, item):
        return all(self.bits[p // 8] & (1 << (p % 8))
                   for p in self._positions(item))

# 50 مليون عنصر, 10 بت لكل عنصر
n = 50_000_000
m = 10 * n                          # 500 مليون بت = ~62.5 ميجابايت
k = round((m / n) * math.log(2))    # ≈ 7
bf = BloomFilter(m, k)

bf.add("ahmed@haies.com")
print(bf.contains("ahmed@haies.com"))   # True  (مضمون)
print(bf.contains("random@nope.com"))   # False (غالبًا)

الأرقام في السطور دي مش عشوائية؛ هي ناتجة من معادلة نشرحها دلوقتي.

الأرقام: كام بت وكام دالة هاش

احتمال الـ false positive تقريبًا: p ≈ (1 − e^(−k·n/m))^k. وأفضل عدد دوال هاش هو k = (m/n)·ln2. لو خصّصت 10 بت لكل عنصر (m/n = 10)، أفضل k حوالي 7، والـ false positive بيطلع حوالي 1%. يعني في المتوسط طلب واحد من كل 100 هيروح يراجع قاعدة البيانات بدون داعٍ، والـ 99 الباقيين بيتحسموا من الذاكرة مباشرة.

المقارنة الملموسة: 50 مليون عنصر × 10 بت = ~62.5 ميجابايت في الرام، مقابل ~1 جيجابايت لو خزّنت الأسماء نفسها في set. يعني توفير حوالي 16 ضعف في الذاكرة، مقابل نسبة خطأ 1% إنت حاسبها ومتحكّم فيها سلفًا.

الـ trade-offs

• بتكسب: ذاكرة أقل بمراحل، وفحص بتعقيد O(k) ثابت من غير ما تلمس القرص. بتخسر: نسبة false positive ثابتة، ولازم تراجع المصدر الحقيقي في الحالات دي بس.
• مفيش حذف في فلتر بلوم الكلاسيكي؛ ما تقدرش تصفّر بت لأنه ممكن يكون مشترك مع عناصر تانية. لو محتاج حذف، محتاج Counting Bloom Filter (بيصرف ذاكرة أكتر)، أو تعيد بناء الفلتر دوريًا.
• الافتراض إن حجم البيانات n معروف تقريبًا وقت التصميم. لو n طلع أكبر بكتير من المتوقّع، نسبة الخطأ بتزيد بسرعة لأن أغلب البتات بتتملي بـ 1.

فين بتُستخدم فعليًا

Cassandra و RocksDB و LevelDB بيحطّوا فلتر بلوم على كل SSTable عشان يتخطّوا قراءة القرص للمفاتيح غير الموجودة، وده بيوفّر عمليات I/O كتير على قرص. متصفّح Chrome استخدم نسخة منه في Safe Browsing عشان يفحص الروابط محليًا قبل ما يسأل السيرفر. و RedisBloom بيوفّره كنوع بيانات جاهز تضيف وتفحص عليه بأوامر مباشرة.

متى لا تستخدم فلتر بلوم

ما تستخدموش لو محتاج إجابة قطعية بـ "موجود" (هو قطعي بس في "غير موجود")، أو لو محتاج تحذف عناصر بكثرة، أو لو البيانات صغيرة أصلًا وتقدر تحطها في set عادي من غير قلق على الذاكرة. كمان مش مناسب لو تكلفة الـ false positive عالية جدًا لدرجة إن أي مراجعة زيادة لقاعدة البيانات بتكسر الـ SLA بتاعك.

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

افتح أبطأ endpoint عندك بيعمل "فحص وجود" على قاعدة البيانات. لو أغلب النتائج بترجع "غير موجود"، حط قدّامه فلتر بلوم بـ 10 بت لكل عنصر و k = 7، وقِس نسبة الطلبات اللي وصلت فعلًا للـ DB قبل وبعد. المفروض تنزل بحوالي 99% لو بياناتك متفرّقة. لو ما نزلتش، يبقى أغلب طلباتك على عناصر موجودة فعلًا، وساعتها فلتر بلوم مش الأداة الصح.

مصادر

• Burton H. Bloom, "Space/Time Trade-offs in Hash Coding with Allowable Errors", Communications of the ACM, Vol. 13, 1970.
• Adam Kirsch, Michael Mitzenmacher, "Less Hashing, Same Performance: Building a Better Bloom Filter", 2006 (طريقة الـ double hashing المستخدمة في الكود).
• توثيق Apache Cassandra — Bloom filters (cassandra.apache.org).
• توثيق RocksDB — Bloom Filter (github.com/facebook/rocksdb/wiki).
• RedisBloom module documentation (redis.io/docs/data-types/probabilistic).
• معادلة احتمال الـ false positive: مقالة "Bloom filter" على Wikipedia، قسم Probability of false positives.