يا أهلاً وسهلاً فيكم. قبل ما ندخل في صلب الموضوع التقني، اسمحولي أشارككم قصة صارت معي ومع فريقي قبل كم سنة. كنا شغالين على منصة اجتماعية جديدة، وكان فيها ميزة تسجيل المستخدمين طبعاً. كل شيء كان ماشي تمام، التطبيق شغال زي الحلاوة، والمستخدمين مبسوطين.
بعد فترة، ومع زيادة عدد المستخدمين، بلّشنا نلاحظ بطء غريب في النظام، خصوصاً في عملية التسجيل. السيرفرات صايرة “تئن”، وقاعدة البيانات “بتشكي همها” من كثر الضغط. قعدنا أنا والشباب نحلل الوضع، وفتحنا سجلات الأداء (Performance Logs)، وهون كانت الصدمة. اكتشفنا إنه أكثر من 90% من الاستعلامات (Queries) اللي بتروح على جدول المستخدمين كانت من نوع: SELECT id FROM users WHERE username = 'some_new_username'. والمصيبة الأكبر، إنه معظم هاي الاستعلامات كانت بترجع بنتيجة فارغة! يعني اليوزر اللي بحاول يسجل، بختار اسم مستخدم، واحنا بنروح نسأل قاعدة البيانات: “يا داتا بيس، هاد الاسم موجود عندك؟”، وفي أغلب الأحيان، كان الجواب “لأ، مش موجود”.
فعلياً، كنا بنسأل قاعدة البيانات عن “أشباح”، عن بيانات مش موجودة أصلاً. كل استعلام من هدول، حتى لو كان سريع، إله تكلفته: اتصال بالداتا بيس، تنفيذ، بحث في الفهرس (Index)… ومع آلاف المستخدمين اللي بحاولوا يسجلوا بنفس الوقت، صار الموضوع كابوس. واحد من الشباب صاح فينا: “يا جماعة، الداتا بيس راح تنفجر! لازم نلاقي حل لهالاستعلامات الشبحية!”. وقتها، لمعت في بالي فكرة، خوارزمية كنت قرأت عنها زمان وبعتبرها من أجمل وأبسط الأفكار في عالم هياكل البيانات: فلتر بلوم.
كان الحل بسيطاً جداً لدرجة أننا شعرنا بالغباء لأننا لم نفكر فيه من البداية. كانت الفكرة هي أن نتوقف عن إزعاج قاعدة البيانات بأسئلة لا تملك إجابتها.
ما هو “فلتر بلوم” (Bloom Filter) يا أبو عمر؟
بكل بساطة، فلتر بلوم هو هيكل بيانات احتمالي (Probabilistic Data Structure)، ومصمم ليعطيك جواب سريع جداً على سؤال واحد فقط: “هل هذا العنصر محتمل أن يكون عضواً في هذه المجموعة؟”.
لاحظوا كلمة “محتمل”. هون السر كله. فلتر بلوم بيتميز بشغلتين رئيسيتين:
- كفاءة عالية في استخدام الذاكرة: صغير جداً مقارنة بتخزين كل البيانات الأصلية.
- لا يعطي نتائج سلبية خاطئة (No False Negatives): إذا قال لك الفلتر “هذا العنصر غير موجود بالتأكيد”، فهو صادق 100%. مستحيل يغلط ويقول لك عنصر موجود إنه مش موجود.
- قد يعطي نتائج إيجابية خاطئة (Can have False Positives): إذا قال لك الفلتر “هذا العنصر قد يكون موجوداً”، فهنا يوجد احتمال صغير إنه يكون غلطان.
تخيلوا معي إنه حارس أمن على باب بناية ضخمة. بدل ما يكون معه دفتر فيه أسماء كل السكان (وهذا بياخذ وقت وجهد للبحث)، معه ورقة صغيرة فيها “بصمات” مشفرة لأسماء السكان. لما يجي زائر ويسأل عن شخص، الحارس بياخذ بصمة اسم الشخص وبيقارنها بالورقة اللي معه. إذا البصمة مش موجودة، فهو متأكد 100% إنه هالشخص مش من سكان البناية. أما إذا البصمة موجودة، فبيقول للزائر “ممكن يكون موجود، تفضل اسأل الاستقبال للتأكيد”. ليش؟ لأنه ممكن بالصدفة بصمة اسم شخص آخر تكون مشابهة.
كيف بيشتغل هالحكي؟ (آلية العمل ببساطة)
آلية عمل فلتر بلوم بتعتمد على مكونين أساسيين: مصفوفة من البتات (Bit Array) ومجموعة من دوال التجزئة (Hash Functions).
مرحلة الإضافة (Adding an element)
لنفترض أن لدينا مصفوفة بتات بحجم 10 (كلها أصفار في البداية) و 3 دوال تجزئة (k=3).
Bit Array: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
عندما نريد إضافة عنصر، مثلاً اسم المستخدم “omar”، نقوم بالخطوات التالية:
- نمرر “omar” على دوال التجزئة الثلاثة.
- كل دالة تعطينا رقماً (موقعاً) في المصفوفة. لنفترض أن النتائج كانت: 2، 5، 9.
- نذهب إلى هذه المواقع في المصفوفة ونحول قيمتها من 0 إلى 1.
فتصبح المصفوفة بهذا الشكل:
Bit Array: [0, 0, 1, 0, 0, 1, 0, 0, 0, 1]
الآن، لنضف عنصراً آخر، مثلاً “ahmed”. لنفترض أن دوال التجزئة أعطتنا المواقع: 3، 5، 8. سنقوم بتحويل البتات في هذه المواقع إلى 1. لاحظوا أن الموقع 5 كان بالفعل 1، وهذا طبيعي جداً.
تصبح المصفوفة النهائية:
Bit Array: [0, 0, 1, 1, 0, 1, 0, 0, 1, 1]
مرحلة الفحص (Checking for an element)
هنا يظهر السحر الحقيقي. عندما نريد أن نتحقق من وجود عنصر ما، نقوم بنفس العملية:
- فحص “omar”: نمرره على دوال التجزئة، نحصل على 2، 5، 9. نتحقق من المصفوفة: هل البتات في المواقع 2، 5، 9 كلها تساوي 1؟ نعم. إذن، الجواب هو “محتمل أن يكون موجوداً”.
- فحص “khalid”: نمرره على دوال التجزئة، لنفترض أن النتائج كانت 1، 5، 7. نتحقق من المصفوفة: هل البتات في المواقع 1، 5، 7 كلها تساوي 1؟ ننظر إلى الموقع 1، فنجد أن قيمته 0. هنا نتوقف فوراً. بما أن أحد البتات المطلوبة يساوي 0، فهذا يعني أن “khalid” غير موجود بالتأكيد.
هذا هو المبدأ الذي أنقذنا. كنا نتجنب الذهاب لقاعدة البيانات في كل مرة يكون فيها الجواب “غير موجود بالتأكيد”.
العودة إلى أرض المعركة: كيف طبقنا الحل؟
الحل كان بسيطاً وأنيقاً. قمنا بإنشاء فلتر بلوم وخزّناه في ذاكرة سريعة (In-memory cache) مثل Redis.
- عند تسجيل مستخدم جديد: بعد أن يتم حفظ اسم المستخدم بنجاح في قاعدة البيانات، كنا نضيف اسم المستخدم هذا إلى فلتر بلوم الموجود في Redis.
- عند محاولة تسجيل مستخدم جديد: قبل إرسال أي استعلام لقاعدة البيانات، كنا نتحقق أولاً من اسم المستخدم المقترح في فلتر بلوم.
السيناريوهات الناتجة:
- إذا قال الفلتر “غير موجود بالتأكيد”: يا سلام! هذا يعني أن اسم المستخدم متاح بنسبة 100%. كنا نعطي الضوء الأخضر للمستخدم ونكمل عملية التسجيل دون إزعاج قاعدة البيانات. هذا السيناريو غطى أكثر من 90% من الحالات.
- إذا قال الفلتر “محتمل أن يكون موجوداً”: هنا فقط، وفي هذه الحالة فقط، كنا نذهب ونسأل قاعدة البيانات للتأكد. إما أن يكون الاسم محجوزاً فعلاً، أو أنها كانت حالة “إيجابية خاطئة” (False Positive) واسم المستخدم متاح. في كلتا الحالتين، عدد الاستعلامات التي تصل لقاعدة البيانات انخفض بشكل هائل.
شوية كود عشان الصورة توضح (مثال بايثون)
هذا مثال بسيط جداً باستخدام مكتبة pybloom_live في بايثون لتوضيح الفكرة:
# First, install the library
# pip install pybloom-live
from pybloom_live import BloomFilter
# Create a Bloom Filter
# capacity: number of elements we expect to store
# error_rate: our acceptable false positive probability
# For 1 million users with a 0.1% error rate
users_bloom = BloomFilter(capacity=1000000, error_rate=0.001)
# --- Simulating existing users being added to the filter ---
existing_users = ["omar", "ahmed", "sara", "fatima"]
for user in existing_users:
users_bloom.add(user)
print(f"Added '{user}' to the Bloom Filter.")
# --- Now, let's simulate new user registration checks ---
def check_username(username):
print(f"nChecking username: '{username}'...")
# 1. First, check the Bloom Filter
if username in users_bloom:
# It *might* be in the set.
print(f"Bloom Filter says: '{username}' *might* exist. Need to check DB.")
# 2. In a real app, you would query the database here.
# db_result = database.query("SELECT id FROM users WHERE username = ?", username)
# For simulation, we'll just check our original list
if username in existing_users:
print(f"DB Confirmation: '{username}' is already taken. (True Positive)")
else:
print(f"DB Confirmation: '{username}' is available! (False Positive from Bloom Filter)")
else:
# It is *definitely* not in the set.
print(f"Bloom Filter says: '{username}' is definitely available. No DB check needed!")
# --- Let's test it ---
check_username("omar") # A user that actually exists
check_username("khalid") # A user that definitely doesn't exist
check_username("random_user")# Another user that definitely doesn't exist
check_username("possible_fp")# This might trigger a false positive depending on the hash
نصائح من العبد لله (من خبرتي العملية)
اختيار الحجم ودوال الهاش (m و k)
أهم قرار عند استخدام فلتر بلوم هو تحديد حجم المصفوفة (m) وعدد دوال التجزئة (k). هذه القيم تعتمد على عدد العناصر التي تتوقع تخزينها (n) ونسبة الخطأ الإيجابي الخاطئ (p) التي يمكنك تحملها. لا تقلق، لست بحاجة لحسابها يدوياً. هناك الكثير من الآلات الحاسبة على الإنترنت (ابحث عن “Bloom Filter Calculator”) التي تعطيك القيم المثلى بمجرد إدخال توقعاتك.
لا يمكن الحذف!
تذكر جيداً: فلتر بلوم القياسي لا يدعم عملية الحذف. لماذا؟ لأنك إذا قمت بتحويل بت من 1 إلى 0 لحذف عنصر، قد تكون دمرت عن غير قصد عنصراً آخر يتشارك معك في نفس البت. هناك حلول بديلة مثل “فلتر بلوم العدّاد” (Counting Bloom Filter) الذي يسمح بالحذف، ولكنه يستهلك ذاكرة أكبر وهو أكثر تعقيداً.
متى تستخدمه ومتى لأ
- استخدمه: عندما تكون تكلفة الاستعلام الأصلي عالية (مثل استعلامات الشبكة أو الأقراص الصلبة)، ويمكنك تحمل نسبة صغيرة من الإيجابيات الخاطئة. ممتاز لـ:
- تصفية ذاكرة التخزين المؤقت (Cache filtering): “هل هذا العنور موجود في الكاش قبل أن أذهب إلى الداتا بيس؟”.
- التحقق من توفر أسماء المستخدمين أو العناوين (URLs).
- تجنب التوصية بمقالات قرأها المستخدم بالفعل.
- قوائم حظر (Blocklists) لعناوين IP أو المواقع الخبيثة.
- لا تستخدمه: عندما تحتاج إلى دقة 100% ولا يمكنك تحمل أي إيجابيات خاطئة على الإطلاق. إذا كان السؤال “هل هذا المريض لديه حساسية من البنسلين؟”، فاستخدام فلتر بلوم هنا سيكون كارثياً.
الخلاصة يا جماعة الخير
فلتر بلوم هو مثال رائع على كيف يمكن لفكرة بسيطة وذكية أن تحل مشاكل أداء معقدة. إنه ليس حلاً لكل شيء، ولكنه أداة قوية جداً في جعبة أي مطور برمجيات. من خلال التضحية بالقليل من الدقة (بشكل يمكن التحكم فيه)، نكسب سرعة هائلة وكفاءة في استخدام الموارد.
في المرة القادمة التي تجد فيها نظامك يلهث تحت وطأة استعلامات تبحث عن “أشباح”، تذكر قصة الحارس ذو الذاكرة الاحتمالية. أحياناً، جواب “ربما” هو كل ما تحتاجه لتجنب آلاف الإجابات البطيئة والمكلفة. 😉
