المستوى: متوسط — يفترض إنك مرتاح مع Python و HashMap وعندك فكرة عن big-O.
لو الـ web crawler بتاعك بيعمل query على Postgres 3 مرات لكل URL جديد علشان يتأكد إنه ما اتزارش قبل كده، انت بتدفع 4ms كحد أدنى لكل link قبل أي شغل حقيقي. على crawler بيشتغل 4,000 link/ثانية ده معناه إن الـ DB لوحدها بتاكل 16 ثانية CPU في كل ثانية حقيقية. Bloom Filter بيخلّي نفس الفحص يحصل في 0.4 ميكروثانية، على 50 مليون URL محفوظين في 57MB RAM، بنسبة كذب 0.93% فقط.
Bloom Filters: هيكل بيانات احتمالي يوفّر 99% من زمن الفحص
المشكلة باختصار
أي نظام محتاج يجاوب على سؤال "هل العنصر ده شفته قبل كده؟" بيقع في نفس الفخ. عندك ثلاث خيارات تقليدية، وكل واحد بيدفع ضريبة:
- HashSet في الذاكرة: زمن lookup ثابت (O(1))، لكن بيخزّن الـ key كامل. لـ 50 مليون URL بطول متوسط 80 حرف، الذاكرة بتطلع 18.6GB.
- Database lookup: بيوفّر الذاكرة، لكن بيدفع 1–10ms في كل lookup، وعلى loop بـ 4,000 query/ثانية بيخنق الـ connection pool.
- Redis SET: حل وسط، لكن بياخد 3–4GB لنفس الـ 50 مليون مفتاح، و RTT بـ 0.3ms على الـ network.
Bloom Filter هو هيكل بيانات احتمالي (probabilistic) بيرد على نفس السؤال في زمن ثابت ومساحة ثابتة، مقابل إنه ساعات بيكدب — بيقول "موجود" وهو مش موجود — لكنه أبداً ما بيقول "مش موجود" وهو موجود. ده الـ trade-off الأساسي، ومن غير ما تستوعبه ما تستخدمش الـ filter.
المثال البسيط: حارس النادي اللي بيحفظ بالعلامات
تخيل حارس نادي عنده قائمة بـ 100 ألف شخص ممنوع دخولهم. حفظ الأسماء كلها مستحيل بشرياً. بدل كده، الحارس بيستخدم 7 ملامح بسيطة لكل شخص في القائمة: لون الشعر، شكل الحاجب، طول الأنف، صوت الكحة، طريقة المشي، نوع الحذاء، لون العين. كل ملامح بتترجم لـ "نقطة" واحدة في دفتر ضخم فيه 480 مليون مربع فارغ، وكل نقطة بيتم تظليلها بمجرد تسجيل الاسم.
لما حد جديد ييجي على الباب، الحارس بيشيك على الـ 7 ملامح في دفتره. لو الـ 7 كلهم مظللين → بيعتبره مشتبه به ويبعتله للمدير علشان يتأكد بقاعدة البيانات الكاملة. لو واحدة على الأقل مش مظللة → الشخص ده مؤكد مش في القائمة، اسمحله بالدخول فوراً بدون تأخير.
الحارس ده ممكن يرفض شخص بريء عَرَضاً لأنه صدفة فيه نفس الـ 7 ملامح (de هو الـ false positive)، لكن مستحيل يدخّل شخص ممنوع. وده بالظبط سلوك Bloom Filter.
التعريف العلمي والرياضي
Bloom Filter (اخترعه Burton Howard Bloom سنة 1970) عبارة عن:
- Bit array طوله m (مثلاً 480 مليون bit = 60MB).
- k دوال hash مستقلة (3–7 عادة). كل دالة بترجّع رقم بين 0 و m-1.
لإضافة عنصر x: مرّره على الـ k دوال، ولكل ناتج اضبط الـ bit المقابل في الـ array لـ 1.
للسؤال "هل x موجود؟": مرّره على نفس الـ k دوال. لو الـ k bits كلهم = 1 → غالباً موجود. لو واحد على الأقل = 0 → مؤكد مش موجود.
نسبة الـ false positive بتُحسب من المعادلة المعتمدة:
