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")
