مرشحات بلوم (Bloom Filters): كيف تتأكد من عدم تكرار اسم مستخدم من بين الملايين بجزء من الذاكرة؟

يا هلا بيكم يا جماعة الخير، معكم أخوكم أبو عمر.

خلوني أحكيلكم قصة صارت معي قبل كم سنة. كنا فريق صغير من المبرمجين الفلسطينيين، شغالين بحماس على تطبيق اجتماعي جديد، وكنا شايفين فيه مستقبل كبير. بعد شهور من السهر والتعب، أطلقنا التطبيق وعملنا حملة تسويقية بسيطة. في أول يوم، الأمور كانت “عال العال”، والمستخدمين الجداد بفوتوا شوي شوي. لكن فجأة، وبدون سابق إنذار، الخادم (السيرفر) الرئيسي بلّش ينهار! الاتصالات بالداتابيس (قاعدة البيانات) صارت بطيئة جداً، والتطبيق علّق عند الكل.

بعد تحليل سريع للمشكلة، اكتشفنا إنو سبب الكارثة كان شغلة بسيطة جداً: التحقق من اسم المستخدم عند التسجيل. مع كل مستخدم جديد بحاول يسجل، كنا نبعت استعلام (query) لقاعدة البيانات لنتأكد إذا كان اسم المستخدم “مأخوذ” أو لأ. مع آلاف المستخدمين اللي بحاولوا يسجلوا بنفس الوقت، قاعدة البيانات المسكينة ما قدرت تتحمل كل هالضغط. قعدنا نضرب أخماس بأسداس، كيف بدنا نحل هالمشكلة بدون ما نشتري سيرفرات جديدة تكلفنا “اللي فوقنا واللي تحتنا”؟

وهون، لمعت في بالي فكرة قديمة كنت قرأت عنها في كتاب خوارزميات: الـ Bloom Filters أو “مرشحات بلوم”. كانت زي طوق النجاة اللي أنقذ مشروعنا. اليوم، بدي أشارككم سحر هذه الأداة وكيف ممكن تغير طريقة تفكيركم في حل مشاكل الأداء.

ما هي المشكلة بالضبط؟

قبل ما نغوص في الحل، خلينا نفصّل المشكلة أكثر. تخيل عندك قاعدة بيانات فيها 100 مليون اسم مستخدم. لما يجي مستخدم جديد بده يسجل باسم “khalid123″، شو بتعمل؟

1. بتروح على قاعدة البيانات وبتسألها: “يا قاعدة البيانات، هل الاسم ‘khalid123’ موجود عندك؟”
2. قاعدة البيانات بتبحث في الـ 100 مليون سجل.
3. بترجعلك جواب: “نعم، موجود” أو “لا، غير موجود”.

هذه العملية، حتى لو كانت سريعة نسبياً بفضل الفهرسة (Indexing)، إلا إنها تستهلك موارد. لما يكون عندك 10,000 مستخدم بيعملوا هاي العملية بنفس الثانية، قاعدة البيانات ببساطة بتصير “مخنوقة”.

الحلول التقليدية وعيوبها

• الاستعلام المباشر (Direct Query): كما ذكرنا، بطيء ومكلف تحت الضغط العالي.
• التخزين في الذاكرة (In-memory Set): ممكن تفكر تحط كل أسماء المستخدمين في ذاكرة الوصول العشوائي (RAM) داخل هيكل بيانات سريع مثل Hash Set. هذا بيخلي عملية البحث سريعة جداً. لكن المشكلة هي حجم الذاكرة! 100 مليون اسم مستخدم ممكن يحتاجوا جيجابايتات من الذاكرة، وهذا مكلف جداً وغير عملي.

إذن، شو الحل؟ بدنا إشي يكون سريع زي الحل الثاني، ورخيص وما بستهلك ذاكرة زي الحل الأول. معادلة صعبة، صح؟ لا مش مع مرشحات بلوم!

مرحباً بعالم مرشحات بلوم (Bloom Filters)

مرشح بلوم هو هيكل بيانات احتمالي (Probabilistic Data Structure)، وركزوا لي على كلمة “احتمالي” هاي. هو مصمم ليخبرك بسرعة فائقة وبمساحة ذاكرة قليلة جداً إذا كان عنصر ما (مثل اسم المستخدم) قد يكون موجوداً في مجموعة، أو بالتأكيد غير موجود.

مرشح بلوم لا يقول لك “نعم، هذا العنصر موجود”. بل يقول لك إما “مستحيل يكون موجود” أو “يمكن يكون موجود”.

وهون مربط الفرس! هاي الميزة هي سر قوته.

كيف بتشتغل هاي الشغلة؟

الفكرة بسيطة وعبقرية. مرشح بلوم يتكون من شغلتين أساسيتين:

1. مصفوفة بتات (Bit Array): تخيلها شريط طويل من الأصفار، مثلاً مليون صفر جنب بعض. حجم هذا الشريط بنرمزله بالرمز m.
2. عدة دوال هاش (Hash Functions): عدد معين من دوال الهاش، مثلاً 3 دوال. وظيفة دالة الهاش إنها تاخد أي مدخل (زي اسم المستخدم) وتحوله لرقم عشوائي ضمن نطاق معين. بنرمز لعدد الدوال بالرمز k.

إضافة عنصر جديد (مثلاً، تسجيل مستخدم “abu_omar”)

لما نضيف “abu_omar” للمرشح، بتصير الخطوات التالية:

1. بناخد اسم “abu_omar” وبنمرره على دوال الهاش الثلاثة (k=3).
2. كل دالة هاش بتعطينا رقم (أو مؤشر) مختلف. مثلاً:
   • hash1("abu_omar") بيعطينا الرقم 150.
   • hash2("abu_omar") بيعطينا الرقم 823.
   • hash3("abu_omar") بيعطينا الرقم 541.
3. ب نروح على مصفوفة البتات، وبنحول الخانات اللي أرقامها 150 و 823 و 541 من 0 إلى 1.

وهيك بنكون “سجلنا” وجود “abu_omar” في المرشح. بنكرر هاي العملية لكل أسماء المستخدمين الموجودة عنا في قاعدة البيانات.

التحقق من وجود عنصر (مثلاً، مستخدم جديد يحاول التسجيل باسم “sami”)

الآن، يجي “sami” ويسأل: هل الاسم متاح؟

1. بناخد اسم “sami” وبنمرره على نفس دوال الهاش الثلاثة.
2. بتعطينا نتائج جديدة، مثلاً: 210، 654، 901.
3. ب نروح على مصفوفة البتات وبنتحقق من الخانات بهاي الأرقام.
4. هنا يكمن الاحتمالان:
   • إذا كان واحد على الأقل من هاي الخانات (210، 654، 901) قيمته 0: هذا يعني 100% إنو اسم “sami” لم تتم إضافته من قبل. إذن، الاسم متاح بالتأكيد! (لا يوجد نتائج سلبية كاذبة – No False Negatives).
   • إذا كانت كل الخانات الثلاثة قيمتها 1: هذا يعني أن الاسم “sami” قد يكون موجوداً. ليش “قد يكون”؟ لأنه ممكن اسم ثاني أو مجموعة أسماء أخرى هي اللي حولت هاي الخانات إلى 1 بالصدفة. وهذا ما نسميه “الإيجابية الكاذبة” (False Positive).

مشكلة الإيجابيات الكاذبة (The False Positive Problem)

الإيجابية الكاذبة هي المقايضة (Trade-off) اللي بنعملها عشان نحصل على السرعة والذاكرة القليلة. المرشح ممكن يغلط ويقولك “يمكن الاسم موجود” وهو في الحقيقة مش موجود. لكنه مستحيل يغلط ويقولك “الاسم مش موجود” وهو موجود.

الخبر الحلو إنو بنقدر نتحكم في نسبة الخطأ هاي. كلما زاد حجم مصفوفة البتات (m) وقل عدد العناصر اللي بنخزنها (n)، كلما قلت نسبة الخطأ. اختيار عدد دوال الهاش (k) بشكل صحيح مهم أيضاً. هناك معادلات رياضية تساعدنا نختار أفضل القيم لتحقيق نسبة خطأ قليلة جداً (مثلاً 1%).

تطبيق عملي: العودة لقصة مدقق اسم المستخدم

هلقيت، كيف حل مرشح بلوم مشكلتنا في التطبيق؟

1. مرحلة الإعداد: قمنا بإنشاء مرشح بلوم. قرأنا كل أسماء المستخدمين من قاعدة البيانات (مرة واحدة) وأضفناهم للمرشح. هذا المرشح، الذي يمثل 100 مليون اسم مستخدم، أخذ مساحة صغيرة جداً في الذاكرة (ميجابايتات قليلة بدلاً من جيجابايتات).
2. مرحلة التحقق الفوري: لما يجي مستخدم جديد ويدخل اسم، التطبيق ما بروح على قاعدة البيانات فوراً. بل:
   1. يتحقق من الاسم في مرشح بلوم الموجود في الذاكرة (عملية سريعة جداً).
   2. إذا قال المرشح “غير موجود بالتأكيد”: نعرض للمستخدم علامة صح خضراء فوراً ونقول له الاسم متاح. هذا يحدث في 99% من الحالات (لأن معظم المحاولات تكون لأسماء فريدة). وبهيك، خففنا الضغط على قاعدة البيانات بنسبة 99%!
   3. إذا قال المرشح “قد يكون موجوداً” (حالة الـ 1%): فقط في هذه الحالة، نقوم بالخطوة المكلفة ونرسل استعلاماً لقاعدة البيانات للتأكد 100%. إذا قالت قاعدة البيانات إنه غير موجود، فهذا كان “إيجابية كاذبة” والاسم متاح. وإذا قالت إنه موجود، فالاسم فعلاً محجوز.

النتيجة؟ الخادم رجع يتنفس، والتطبيق صار سريع جداً، والمستخدمون سعداء، وإحنا كفريق 개발者… رُفعت معنوياتنا للسما! 😎

يلّا نشوف شوية كود

عشان الصورة تكون أوضح، هي مثال بسيط جداً بلغة بايثون يوضح فكرة مرشح بلوم. رح نستخدم مكتبة hashlib الموجودة في بايثون لعمل دوال الهاش.

import hashlib
import math

class BloomFilter:
    def __init__(self, num_items, false_positive_prob):
        # حساب حجم مصفوفة البتات (m)
        self.size = int(-(num_items * math.log(false_positive_prob)) / (math.log(2) ** 2))
        # حساب العدد الأمثل لدوال الهاش (k)
        self.hash_count = int((self.size / num_items) * math.log(2))
        
        self.bit_array = [0] * self.size
        print(f"تم إنشاء مرشح بلوم بحجم: {self.size} بت, وعدد دوال هاش: {self.hash_count}")

    def _get_hashes(self, item):
        """يرجع قائمة بالهاشات للعنصر"""
        hashes = []
        # نستخدم دالتين هاش أساسيتين (sha256, md5) ونولد منهما k من الهاشات
        # هذه طريقة بسيطة لتوليد دوال هاش متعددة، في التطبيقات الحقيقية يفضل استخدام دوال مستقلة
        h1 = int(hashlib.sha256(item.encode()).hexdigest(), 16)
        h2 = int(hashlib.md5(item.encode()).hexdigest(), 16)
        for i in range(self.hash_count):
            # (h1 + i * h2) % self.size هي خدعة لتوليد k من الهاشات
            hashes.append((h1 + i * h2) % self.size)
        return hashes

    def add(self, item):
        """إضافة عنصر إلى المرشح"""
        for h in self._get_hashes(item):
            self.bit_array[h] = 1
        # print(f"تمت إضافة '{item}'")

    def check(self, item):
        """التحقق من وجود عنصر"""
        for h in self._get_hashes(item):
            if self.bit_array[h] == 0:
                # إذا وجدنا 0 واحد، فهو بالتأكيد غير موجود
                return False
        # إذا كانت كل البتات 1، فهو قد يكون موجوداً
        return True

# --- مثال عملي ---
# عدد المستخدمين الحاليين
num_users = 1000000
# نسبة الخطأ (الإيجابيات الكاذبة) التي نقبلها، مثلا 1%
fp_prob = 0.01

# إنشاء مرشح بلوم
bloom = BloomFilter(num_users, fp_prob)

# إضافة المستخدمين الحاليين للمرشح (هنا سنضيف أمثلة قليلة للتوضيح)
existing_users = ["abu_omar", "ahmad_ali", "fatima_z", "user12345"]
for user in existing_users:
    bloom.add(user)

print("n--- مرحلة التحقق ---")

# التحقق من اسم مستخدم موجود بالفعل
test_user_1 = "abu_omar"
if bloom.check(test_user_1):
    print(f"التحقق من '{test_user_1}': قد يكون موجوداً (وهو كذلك بالفعل).")
else:
    print(f"التحقق من '{test_user_1}': غير موجود بالتأكيد.")

# التحقق من اسم مستخدم جديد وغير موجود بالتأكيد
test_user_2 = "sami_the_new_guy"
if bloom.check(test_user_2):
    print(f"التحقق من '{test_user_2}': قد يكون موجوداً (إيجابية كاذبة!).")
else:
    print(f"التحقق من '{test_user_2}': غير موجود بالتأكيد (وهو كذلك بالفعل).")

# التحقق من اسم قد يسبب إيجابية كاذبة (حسب الصدفة)
test_user_3 = "some_random_user"
if bloom.check(test_user_3):
    print(f"التحقق من '{test_user_3}': قد يكون موجوداً (احتمال أن تكون إيجابية كاذبة).")
else:
    print(f"التحقق من '{test_user_3}': غير موجود بالتأكيد.")

نصايح من أخوكم أبو عمر

بناءً على خبرتي في استخدام هذه الأداة في مشاريع مختلفة، اسمحولي أقدم لكم كم نصيحة عملية:

• لا تخترع العجلة: الكود اللي كتبناه فوق هو للتوضيح فقط. في المشاريع الحقيقية، استخدم مكتبات جاهزة وموثوقة مثل pybloom_live في بايثون أو Guava BloomFilter في جافا. هذه المكتبات محسّنة ومختبرة.
• اختيار دوال الهاش: سرعة مرشح بلوم تعتمد على سرعة دوال الهاش. تجنب استخدام دوال التشفير البطيئة مثل SHA-256 (استخدمتها في المثال للتبسيط فقط). استخدم دوال سريعة وغير تشفيرية مثل Murmur3 أو FNV.
• احسبها صح: قبل بناء المرشح، استخدم حاسبة مرشح بلوم (ابحث في جوجل عن “Bloom filter calculator”). أدخل عدد العناصر المتوقع (n) ونسبة الخطأ المقبولة (p)، وستعطيك الحجم الأمثل للمصفوفة (m) وعدد دوال الهاش (k).
• متى تستخدمها؟ مرشحات بلوم ممتازة في أي سيناريو تحتاج فيه إلى تصفية العناصر غير الموجودة بسرعة. بعض الأمثلة الأخرى:
  • أنظمة التوصية: لمنع عرض مقال أو فيديو شاهده المستخدم من قبل.
  • فحص الروابط الخبيثة: المتصفحات تستخدمها للتحقق بسرعة إذا كان الرابط في قائمة سوداء ضخمة.
  • قواعد البيانات الموزعة: مثل Apache Cassandra، تستخدمها لتقليل عمليات القراءة من القرص الصلب.
• تذكر: لا يمكن حذف عنصر! في مرشح بلوم التقليدي، لا يمكنك حذف عنصر بسهولة، لأنك لو حولت بت من 1 إلى 0، قد تكون أفسدت المعلومات الخاصة بعنصر آخر يشارك نفس البت. هناك أنواع متقدمة مثل Counting Bloom Filter تسمح بالحذف ولكنها أكثر تعقيداً وتستهلك ذاكرة أكبر.

الخلاصة يا جماعة الخير

مرشحات بلوم هي مثال رائع على عبقرية الخوارزميات وكيف يمكن لفكرة بسيطة أن تحل مشاكل معقدة. هي ليست حلاً سحرياً لكل شيء، ولكنها الأداة المثالية عندما تكون مستعداً للتضحية بنسبة ضئيلة جداً من الدقة مقابل توفير هائل في الموارد والسرعة. 👍

الدرس الأهم هنا هو أن تفكر دائماً “خارج الصندوق”. لا تحصر نفسك بالحلول التقليدية. عالم هياكل البيانات والخوارزميات مليء بالجواهر الخفية مثل مرشحات بلوم، التي تنتظر من يكتشفها ويستخدمها ليبني أنظمة أفضل وأكثر كفاءة.

أتمنى تكونوا استفدتوا، وبالتوفيق في مشاريعكم القادمة!