تصميم النظام: مرشح بلوم. تحويل جدول التجزئة بذكاء إلى … | بواسطة فياتشيسلاف افيموف
النشرة الإخبارية
Sed ut perspiciatis unde.
تحويل جدول التجزئة بذكاء إلى بنية بيانات احتمالية لتداول الدقة لتحقيق مكاسب كبيرة في الذاكرة
حطاولة الرماد هي واحدة من هياكل البيانات الأكثر شهرة واستخدامًا. من خلال الاختيار الحكيم لوظيفة التجزئة، يمكن أن ينتج جدول التجزئة أداءً مثاليًا لاستعلامات الإدراج والبحث والحذف في وقت ثابت.
العيب الرئيسي لجدول التجزئة هو الاصطدامات المحتملة. لتجنبها، تتضمن إحدى الطرق القياسية زيادة حجم جدول التجزئة. على الرغم من أن هذا الأسلوب يعمل بشكل جيد في معظم الحالات، إلا أننا في بعض الأحيان لا نزال محدودين في استخدام مساحة الذاكرة الكبيرة.
من الضروري أن نتذكر أن جدول التجزئة يوفر دائمًا إجابة صحيحة لأي استفسار. قد تمر بالاصطدامات وتكون بطيئة في بعض الأحيان ولكنها كذلك دائماً يضمن الإجابات الصحيحة بنسبة 100٪. اتضح أنه في بعض الأنظمة، لا نحتاج دائمًا إلى تلقي المعلومات الصحيحة للاستعلامات. يمكن استخدام هذا الانخفاض في الدقة للتركيز على تحسين جوانب أخرى من النظام.
في هذه المقالة، سوف نكتشف بنية بيانات مبتكرة تسمى أ مرشح بلوم. بكلمات بسيطة، إنها نسخة معدلة من جدول التجزئة القياسي الذي يستبدل انخفاضًا طفيفًا في الدقة لتحقيق مكاسب في مساحة الذاكرة.
يتم تنظيم مرشح Bloom على شكل مصفوفة منطقية بحجم m. في البداية تم وضع علامة على كافة عناصره على أنها 0 (خطأ). وبصرف النظر عن ذلك، فمن الضروري اختيار وظائف التجزئة k التي تأخذ الكائنات كمدخلات وتعيينها إلى النطاق [0, m — 1]. ستتوافق كل قيمة مخرجات لاحقًا مع عنصر صفيف في هذا الفهرس.
للحصول على نتائج أفضل، يوصى بأن تقوم دالات التجزئة بإخراج قيم توزيعها قريب من التجانس.
إدراج
عندما يلزم إضافة كائن جديد، يتم تمريره عبر وظائف التجزئة المحددة مسبقًا k. بالنسبة لكل قيمة تجزئة مخرجات، يصبح العنصر المقابل في هذا الفهرس 1 (صحيح).
إذا كان عنصر المصفوفة الذي تم إخراج فهرسه من دالة التجزئة قد تم تعيينه بالفعل على 1، فسيظل ببساطة 1.
في الأساس، وجود 1 في أي عنصر من عناصر المصفوفة يعمل كدليل جزئي على أن العنصر المجزأ إلى فهرس المصفوفة المعني موجود بالفعل في مرشح Bloom.
يبحث
للتحقق من وجود كائن، يتم حساب قيم التجزئة k الخاصة به. يمكن أن يكون هناك سيناريوهين محتملين:
إذا كان هذا هو مرة على الأقل قيمة التجزئة التي يساوي فيها عنصر الصفيف المعني 0، وهذا يعني أن الكائن غير موجود.
أثناء الإدراج، يصبح الكائن مرتبطًا بالعديد من عناصر المصفوفة التي تم وضع علامة عليها كـ 1. إذا كان الكائن موجودًا بالفعل في المرشح، فإن جميع وظائف التجزئة ستنتج بشكل حتمي نفس التسلسل من الفهارس التي تشير إلى 1. ومع ذلك، الإشارة إلى مصفوفة يشير العنصر الذي يحتوي على 0 بوضوح إلى أن الكائن الحالي غير موجود في بنية البيانات.
إذا ل جميع قيم التجزئة، عناصر المصفوفة المعنية تساوي 1، وهذا يعني أن هدف ربما موجود (ليس 100%).
هذا البيان هو بالضبط ما يجعل مرشح Bloom عبارة عن بنية بيانات احتمالية. إذا تمت إضافة كائن من قبل، أثناء البحث، يضمن مرشح Bloom أن قيم التجزئة ستكون هي نفسها بالنسبة له، وبالتالي سيتم العثور على الكائن.
ومع ذلك، يمكن لمرشح بلوم أن ينتج استجابة إيجابية كاذبة عندما لا يكون الكائن موجودًا بالفعل ولكن مرشح بلوم يدعي خلاف ذلك. يحدث هذا عندما تقوم جميع وظائف التجزئة للكائن بإرجاع قيم التجزئة 1 المقابلة للكائنات الأخرى المدرجة بالفعل في عامل التصفية.
تميل الإجابات الإيجابية الكاذبة إلى الحدوث عندما يصبح عدد الكائنات المدرجة مرتفعًا نسبيًا مقارنة بحجم مصفوفة مرشح بلوم.
تقدير الأخطاء الإيجابية الكاذبة
من الممكن تقدير احتمالية الحصول على خطأ إيجابي كاذب، بالنظر إلى بنية مرشح بلوم.
يمكن العثور على الدليل الكامل لهذه الصيغة على ويكيبيديا. بناءً على هذا التعبير، يمكننا تقديم بعض الملاحظات المثيرة للاهتمام:
- يتناقص احتمال FP مع زيادة عدد وظائف التجزئة k، وزيادة حجم المصفوفة m، وانخفاض عدد الكائنات المدرجة n.
- قبل إدراج كائنات في مرشح Bloom، يمكننا العثور على العدد الأمثل لوظائف التجزئة المطلوبة k والتي ستقلل من احتمالية FP إذا عرفنا حجم المصفوفة m ويمكننا تقدير عدد الكائنات n التي سيتم إدراجها في المستقبل.
هناك خيار آخر لتقليل احتمالية FP وهو الجمع (والاقتران) بين العديد من مرشحات Bloom المستقلة. يعتبر العنصر في النهاية موجودًا في بنية البيانات فقط إذا كان موجودًا في جميع مرشحات Bloom.
قيود
- على عكس جداول التجزئة، فإن التنفيذ القياسي لمرشح Bloom لا يدعم الحذف.
- لا يمكن تغيير العدد المختار من وظائف التجزئة k وحجم المصفوفة m في البداية لاحقًا. إذا كانت هناك حاجة لذلك، فإن الطريقة الوحيدة للقيام بذلك هي إنشاء مرشح Bloom آخر بإعدادات جديدة عن طريق إدراج جميع الكائنات المخزنة مسبقًا.
وفقًا للصفحة من ويكيبيديا، يُستخدم مرشح بلوم على نطاق واسع في الأنظمة الكبيرة:
- قواعد البيانات مثل أباتشي إتش بيس, أباتشي كاساندرا و PostgreSQL استخدم مرشح Bloom للتحقق من الصفوف أو الأعمدة غير الموجودة. يعد هذا الأسلوب أسرع بكثير من استخدام عمليات البحث على القرص.
- واسطة يستخدم مرشح Bloom لتصفية الصفحات التي تمت التوصية بها بالفعل للمستخدم.
- جوجل كروم استخدمت مرشح Bloom في الماضي لتحديد عناوين URL الضارة. يعتبر عنوان URL آمنًا إذا أعاد مرشح Bloom استجابة سلبية. وبخلاف ذلك، تم إجراء الفحص الكامل.
في هذه المقالة، قمنا بتغطية طريقة بديلة لإنشاء جداول التجزئة. عندما يمكن التنازل عن انخفاض بسيط في الدقة من أجل استخدام أكثر كفاءة للذاكرة، يصبح مرشح Bloom حلاً قويًا في العديد من الأنظمة الموزعة.
إن تغيير عدد وظائف التجزئة مع حجم مرشح Bloom يسمح لنا بإيجاد التوازن الأنسب بين الدقة ومتطلبات الأداء.
جميع الصور ما لم يذكر خلاف ذلك هي من قبل المؤلف.
اكتشاف المزيد من موقع علم
اشترك للحصول على أحدث التدوينات المرسلة إلى بريدك الإلكتروني.