Bloom Filter بالعربي: قلّل أسئلة قاعدة البيانات قبل ما تبدأ

هتطلع من المقال ده بفكرة عملية: إزاي تستخدم Bloom Filter كبوابة رخيصة قبل قاعدة البيانات، فتقلل استعلامات ملهاش لازمة بدون ما تمنع نتيجة موجودة فعلاً.

مستوى القارئ: متوسط

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

افترض إن عندك API بيتأكد هل الإيميل موجود قبل إنشاء حساب جديد. كل طلب بيعمل query على PostgreSQL. لو عندك 100,000 محاولة يوميًا، و80% منها لإيميلات غير موجودة، فأنت بتدفع تكلفة DB على أسئلة أغلبها إجابته "لا".

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

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

ركز في المثال ده. عندك موظف أمن على باب أرشيف كبير. بدل ما يدخل الأرشيف كل مرة يبحث عن اسم، معاه ورقة صغيرة عليها علامات. لو العلامة مش موجودة، يقول لك فورًا: الاسم مش في الأرشيف. لو العلامة موجودة، هو مش متأكد 100%، فيدخل الأرشيف ويتأكد.

Bloom Filter بيعمل نفس الفكرة. هو structure في الذاكرة بيقول لك إجابتين فقط: "مش موجود أكيد" أو "ممكن يكون موجود". لا يقول "موجود أكيد". ودي أهم نقطة. هو يضمن عدم وجود false negatives، لكنه يقبل false positives بنسبة تختارها.

علميًا، Bloom Filter عبارة عن bit array وعدة hash functions. عند إضافة عنصر، كل hash function يحدد مكان bit ويتحول إلى 1. عند الفحص، لو أي bit من المطلوب يساوي 0، العنصر غير موجود أكيد. لو كل الـ bits تساوي 1، العنصر ممكن يكون موجود، وساعتها تسأل قاعدة البيانات.

الحل العملي في Python

الافتراض إن عندك قائمة إيميلات موجودة بالفعل، وعايز تقلل checks الفارغة قبل ما تروح لـ DB. الكود التالي تعليمي ومناسب لفهم الفكرة. في الإنتاج، استخدم RedisBloom أو مكتبة جاهزة لو عندك أكثر من instance.

from hashlib import blake2b

class BloomFilter:
    def __init__(self, size=1_000_000, hashes=7):
        self.size = size
        self.hashes = hashes
        self.bits = bytearray(size)

    def _positions(self, value):
        raw = value.encode("utf-8")
        for seed in range(self.hashes):
            digest = blake2b(raw, digest_size=8, person=f"bf{seed}".encode()).digest()
            yield int.from_bytes(digest, "big") % self.size

    def add(self, value):
        for pos in self._positions(value):
            self.bits[pos] = 1

    def might_contain(self, value):
        return all(self.bits[pos] for pos in self._positions(value))

bf = BloomFilter()
for email in ["a@example.com", "b@example.com"]:
    bf.add(email)

if not bf.might_contain("new@example.com"):
    print("skip database query")
else:
    print("ask database to confirm")

الكود بيستخدم hashlib.blake2b لأن Python بيوفره في المكتبة القياسية، وبيسمح بتغيير person لإنتاج مسارات hash مختلفة لنفس القيمة. ده مناسب للمثال. في أنظمة حقيقية، اختبر التوزيع والحجم بدل ما تنقل القيم كما هي.

الأرقام المتوقعة قبل وبعد

لو عندك 100,000 check يوميًا، و20,000 فقط لإيميلات موجودة، فالسيناريو المباشر يعمل 100,000 query. مع Bloom Filter مضبوط على false positive حوالي 1%، المتوقع إن كل الـ 80,000 غير الموجودين يتوقفوا تقريبًا، ما عدا حوالي 800 سؤال ممكن يعدي بالغلط. يعني بدل 100,000 query، هتعمل تقريبًا 20,800 query.

الرقم ده تقديري، لكنه مفيد لاتخاذ القرار. المكسب واضح: ضغط أقل على DB، latency أقل للطلبات الفارغة، وCPU أقل في طبقة التخزين. الـ trade-off هنا إنك بتضيف ذاكرة وتعقيد مزامنة. لو الـ filter قديم أو ناقص، لازم تفضل قاعدة البيانات هي مصدر الحقيقة.

RedisBloom بدل الكود اليدوي

لو التطبيق عندك أكتر من instance، الكود المحلي هيعمل مشكلة. كل instance هيبقى عنده filter مختلف. أفضل طريقة هنا تستخدم RedisBloom. تضيف الإيميل عند إنشائه، وتسأل Redis قبل query التأكيد.

# إضافة قيمة للفلتر
BF.ADD users:emails a@example.com

# فحص قيمة قبل سؤال PostgreSQL
BF.EXISTS users:emails new@example.com

حسب توثيق Redis، BF.ADD يضيف عنصرًا إلى Bloom filter، وBF.EXISTS يرجع إن العنصر قد يكون موجودًا أو غير موجود. ركز: عند "may exist" لا تثق في Redis وحده. اسأل PostgreSQL للتأكيد. Redis هنا بوابة، مش مصدر الحقيقة.

ما الذي تكسبه وما الذي تخسره

• تكسب: تقليل queries الفارغة. في مثالنا من 100,000 إلى حوالي 20,800 query يوميًا.
• تكسب: رد أسرع للطلبات التي تسأل عن قيم غير موجودة.
• تخسر: ذاكرة إضافية حسب عدد العناصر ونسبة الخطأ المستهدفة.
• تخسر: مسار تحديث جديد. أي insert لازم يحدّث قاعدة البيانات والفلتر.

الطريقة دي بتفشل لو استخدمتها كبديل للـ unique constraint. Bloom Filter لا يمنع التكرار وحده. لو قال "ممكن موجود"، ده ليس حكمًا نهائيًا. ولو قال "غير موجود"، تقدر تتجنب query قراءة، لكن عند الكتابة لازم قاعدة البيانات تفضل صاحبة القرار.

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

لا تستخدم Bloom Filter لو عدد الطلبات قليل، مثل 5,000 check يوميًا. التعقيد مش هيستاهل. لا تستخدمه لو كل القيم تقريبًا موجودة، لأنك هتسأل DB في أغلب الحالات. ولا تستخدمه لو الخطأ الإيجابي البسيط غير مقبول في تجربة المستخدم، مثل قرارات مالية أو أمنية نهائية.

استخدمه لما يكون عندك نسبة كبيرة من الأسئلة على عناصر غير موجودة: إيميلات، SKUs، slugs، أو IDs خارجية. ولو عايزها تدعم حذف العناصر بكفاءة، ابحث عن Counting Bloom Filter بدل Bloom Filter العادي، لأن الفلتر العادي لا يعرف يمسح عنصرًا بدون مخاطرة على عناصر أخرى.

المصادر

• Python hashlib documentation: توثيق BLAKE2 ودعم digest_size وperson.
• Redis BF.ADD command: إضافة عنصر إلى Bloom Filter.
• Redis BF.EXISTS command: فحص هل العنصر قد يكون موجودًا.

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

اختَر endpoint واحد عندك بيعمل checks كثيرة على قيم غالبًا غير موجودة. قِس عدد queries الحالي لمدة يوم، ثم جرّب Bloom Filter بنسبة خطأ 1% خلف feature flag، وقارن عدد queries قبل وبعد.