Bloom Filter للمستوى المتوسط: امنع تسجيل إيميل مكرر في 50 ميكروثانية بدون DB lookup
المستوى المطلوب: متوسط. المقال ده بيفترض إنك فاهم hash functions، arrays، وbitwise operations في أي لغة. مش لازم خلفية رياضية متقدمة، بس هتشوف معادلتين بسيطتين هنشرحهم خطوة بخطوة. وقت القراءة المتوقع: 9 إلى 11 دقيقة.
لو عندك جدول users فيه 10 مليون صف، وكل تسجيل جديد بيعمل SELECT 1 FROM users WHERE email = ? علشان يتأكد إن الإيميل مش متسجّل قبل كده، الـ DB بياكل 6 إلى 12 مللي ثانية في كل request حتى مع B-tree index موجود. Bloom Filter بينزّل ده لـ 50 ميكروثانية في الذاكرة بدون أي lookup للـ DB، بشرط تتقبل false positive معدّله 1% — يعني ممكن يقولك "موجود" وهو في الحقيقة مش موجود (بس عمره ما هيقولك "مش موجود" وهو موجود).
المشكلة باختصار
endpoint التسجيل بيتنده 500 مرة في الثانية على workload متوسط. لو كل nde بياخد 8 مللي ثانية في الـ DB، يبقى 4 ثواني من كل ثانية بيضيعوا في checks فاضية. وأكتر من 95% من الإيميلات اللي بتتفحص جديدة ومش مكررة، يعني الـ DB بترجع "مش موجود" في معظم الوقت — وده شغل الـ B-tree بيدفع تكلفته كاملة بدون فايدة.
الافتراض: الـ workload بتاعك أغلبه قراءات بنتيجة "مش موجود". لو معظم الـ checks بترجع "موجود"، Bloom Filter مش هيوفّرلك حاجة، لأنك هتروح للـ DB بعده على أي حال.
المثال البسيط — قبل التعريف العلمي
تخيّل عندك دفتر ولاد المدرسة، وكل ولد ليه 5 خانات في الدفتر بتتحدد بحسبة معينة من اسمه. أول ما الولد يتسجّل، بتحط علامة ✓ في الـ 5 خانات بتاعته. لما حد يسأل "أحمد عندنا في المدرسة؟"، بتبص في الـ 5 خانات الخاصة بأحمد. لو واحدة فيهم فاضية، أكيد أحمد مش موجود — مفيش طريقة الخانة دي تكون فاضية لو أحمد سُجّل قبل كده. لو الـ 5 كلهم فيهم علامة، أحمد على الأرجح موجود، بس مش 100%، لأن ممكن ولاد تانيين شاركوه نفس الخانات الـ 5.
ده بالظبط Bloom Filter. الدفتر = bit array. الخانات الـ 5 = نتائج 5 hash functions مختلفة. العلامة = 1 بدل 0.
التعريف العلمي الدقيق
Bloom Filter هو probabilistic data structure اخترعه Burton Howard Bloom سنة 1970 في ورقة "Space/Time Trade-offs in Hash Coding with Allowable Errors" (Communications of the ACM). الهيكل بيتكوّن من عنصرين بس:
- Bit array بحجم
mbits، كلهم 0 في البداية. - k hash functions مستقلة، كل واحدة بتاخد العنصر وترجّع رقم في المدى
[0, m-1].
عند الإضافة (insert): شغّل الـ k hash functions على العنصر، وحط 1 في الـ k bits اللي رجعت.
عند البحث (query): شغّل نفس الـ k hash functions على العنصر، اقرا الـ k bits.
- لو bit واحد فيهم = 0 → العنصر أكيد مش موجود (مفيش false negative أبدًا).
- لو الـ k bits كلهم = 1 → العنصر على الأرجح موجود (في احتمال false positive محسوب).
