تقنية وتكنولوجيا

تصميم النظام: مرشح بلوم. تحويل جدول التجزئة بذكاء إلى … | بواسطة فياتشيسلاف افيموف


تحويل جدول التجزئة بذكاء إلى بنية بيانات احتمالية لتداول الدقة لتحقيق مكاسب كبيرة في الذاكرة

نحو علم البيانات

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

العيب الرئيسي لجدول التجزئة هو الاصطدامات المحتملة. لتجنبها، تتضمن إحدى الطرق القياسية زيادة حجم جدول التجزئة. على الرغم من أن هذا الأسلوب يعمل بشكل جيد في معظم الحالات، إلا أننا في بعض الأحيان لا نزال محدودين في استخدام مساحة الذاكرة الكبيرة.

من الضروري أن نتذكر أن جدول التجزئة يوفر دائمًا إجابة صحيحة لأي استفسار. قد تمر بالاصطدامات وتكون بطيئة في بعض الأحيان ولكنها كذلك دائماً يضمن الإجابات الصحيحة بنسبة 100٪. اتضح أنه في بعض الأنظمة، لا نحتاج دائمًا إلى تلقي المعلومات الصحيحة للاستعلامات. يمكن استخدام هذا الانخفاض في الدقة للتركيز على تحسين جوانب أخرى من النظام.

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

يتم تنظيم مرشح Bloom على شكل مصفوفة منطقية بحجم m. في البداية تم وضع علامة على كافة عناصره على أنها 0 (خطأ). وبصرف النظر عن ذلك، فمن الضروري اختيار وظائف التجزئة k التي تأخذ الكائنات كمدخلات وتعيينها إلى النطاق [0, m — 1]. ستتوافق كل قيمة مخرجات لاحقًا مع عنصر صفيف في هذا الفهرس.

للحصول على نتائج أفضل، يوصى بأن تقوم دالات التجزئة بإخراج قيم توزيعها قريب من التجانس.

في مثالنا، سنستخدم مرشح Bloom بالحجم m = 13 مع وظائف التجزئة k = 3. تقوم كل من هذه الوظائف بتعيين كائن إدخال إلى النطاق [0, 12].

إدراج

عندما يلزم إضافة كائن جديد، يتم تمريره عبر وظائف التجزئة المحددة مسبقًا k. بالنسبة لكل قيمة تجزئة مخرجات، يصبح العنصر المقابل في هذا الفهرس 1 (صحيح).

تتم إضافة كائن “الموزة” إلى مرشح Bloom. قيم مخرجات وظائف التجزئة هي 6 و2 و9. وتتغير عناصر المصفوفة في تلك الفهارس إلى 1.

إذا كان عنصر المصفوفة الذي تم إخراج فهرسه من دالة التجزئة قد تم تعيينه بالفعل على 1، فسيظل ببساطة 1.

تتم إضافة كائن “apple” إلى مرشح Bloom. يتم تعيين عناصر المصفوفة في الفهارس 10 و9 و4 إلى 1. على الرغم من أن العنصر التاسع من المصفوفة قد تم تعيينه بالفعل إلى 1، إلا أن قيمته لا تتغير هنا.

في الأساس، وجود 1 في أي عنصر من عناصر المصفوفة يعمل كدليل جزئي على أن العنصر المجزأ إلى فهرس المصفوفة المعني موجود بالفعل في مرشح Bloom.

يبحث

للتحقق من وجود كائن، يتم حساب قيم التجزئة k الخاصة به. يمكن أن يكون هناك سيناريوهين محتملين:

إذا كان هذا هو مرة على الأقل قيمة التجزئة التي يساوي فيها عنصر الصفيف المعني 0، وهذا يعني أن الكائن غير موجود.

أثناء الإدراج، يصبح الكائن مرتبطًا بالعديد من عناصر المصفوفة التي تم وضع علامة عليها كـ 1. إذا كان الكائن موجودًا بالفعل في المرشح، فإن جميع وظائف التجزئة ستنتج بشكل حتمي نفس التسلسل من الفهارس التي تشير إلى 1. ومع ذلك، الإشارة إلى مصفوفة يشير العنصر الذي يحتوي على 0 بوضوح إلى أن الكائن الحالي غير موجود في بنية البيانات.

التحقق من وجود الكائن “البرتقالي” في مرشح Bloom. نظرًا لوجود دالة تجزئة واحدة على الأقل (اثنتان على وجه التحديد في حالتنا) تُخرج فهرسًا (7 و12) للمصفوفة التي يساوي عنصرها 0، فهذا يعني أن “البرتقالي” غير موجود في الفلتر.

إذا ل جميع قيم التجزئة، عناصر المصفوفة المعنية تساوي 1، وهذا يعني أن هدف ربما موجود (ليس 100%).

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

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

ومع ذلك، يمكن لمرشح بلوم أن ينتج استجابة إيجابية كاذبة عندما لا يكون الكائن موجودًا بالفعل ولكن مرشح بلوم يدعي خلاف ذلك. يحدث هذا عندما تقوم جميع وظائف التجزئة للكائن بإرجاع قيم التجزئة 1 المقابلة للكائنات الأخرى المدرجة بالفعل في عامل التصفية.

مثال على استجابة إيجابية كاذبة. على الرغم من أن “الكرز” لم تتم إضافته من قبل، إلا أن المرشح يعتقد أنه موجود لأن جميع قيم تجزئة الإخراج لـ “الكرز” تشير إلى عناصر المصفوفة ذات القيم 1.

تميل الإجابات الإيجابية الكاذبة إلى الحدوث عندما يصبح عدد الكائنات المدرجة مرتفعًا نسبيًا مقارنة بحجم مصفوفة مرشح بلوم.

تقدير الأخطاء الإيجابية الكاذبة

من الممكن تقدير احتمالية الحصول على خطأ إيجابي كاذب، بالنظر إلى بنية مرشح بلوم.

الصورة المعتمدة من قبل المؤلف. المصدر: مرشح بلوم | ويكيبيديا

يمكن العثور على الدليل الكامل لهذه الصيغة على ويكيبيديا. بناءً على هذا التعبير، يمكننا تقديم بعض الملاحظات المثيرة للاهتمام:

  • يتناقص احتمال FP مع زيادة عدد وظائف التجزئة k، وزيادة حجم المصفوفة m، وانخفاض عدد الكائنات المدرجة n.
تؤدي الزيادة في k أو الزيادة في m أو النقصان في n إلى انخفاض معدل FP
  • قبل إدراج كائنات في مرشح Bloom، يمكننا العثور على العدد الأمثل لوظائف التجزئة المطلوبة k والتي ستقلل من احتمالية FP إذا عرفنا حجم المصفوفة m ويمكننا تقدير عدد الكائنات n التي سيتم إدراجها في المستقبل.
العدد الأمثل لوظائف التجزئة k التي تقلل من احتمالية FP

هناك خيار آخر لتقليل احتمالية FP وهو الجمع (والاقتران) بين العديد من مرشحات Bloom المستقلة. يعتبر العنصر في النهاية موجودًا في بنية البيانات فقط إذا كان موجودًا في جميع مرشحات Bloom.

قيود

  • على عكس جداول التجزئة، فإن التنفيذ القياسي لمرشح Bloom لا يدعم الحذف.
  • لا يمكن تغيير العدد المختار من وظائف التجزئة k وحجم المصفوفة m في البداية لاحقًا. إذا كانت هناك حاجة لذلك، فإن الطريقة الوحيدة للقيام بذلك هي إنشاء مرشح Bloom آخر بإعدادات جديدة عن طريق إدراج جميع الكائنات المخزنة مسبقًا.

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

  • قواعد البيانات مثل أباتشي إتش بيس, أباتشي كاساندرا و PostgreSQL استخدم مرشح Bloom للتحقق من الصفوف أو الأعمدة غير الموجودة. يعد هذا الأسلوب أسرع بكثير من استخدام عمليات البحث على القرص.
  • واسطة يستخدم مرشح Bloom لتصفية الصفحات التي تمت التوصية بها بالفعل للمستخدم.
  • جوجل كروم استخدمت مرشح Bloom في الماضي لتحديد عناوين URL الضارة. يعتبر عنوان URL آمنًا إذا أعاد مرشح Bloom استجابة سلبية. وبخلاف ذلك، تم إجراء الفحص الكامل.
خوارزمية Google التي تم استخدامها للتحقق من عناوين URL الضارة. سمح استخدام مرشح بلوم بتقليل عدد عمليات الفحص الكاملة الثقيلة من الناحية الحسابية والتي كانت ستكون مطلوبة لولا ذلك لجزء كبير من الروابط الآمنة.

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

إن تغيير عدد وظائف التجزئة مع حجم مرشح Bloom يسمح لنا بإيجاد التوازن الأنسب بين الدقة ومتطلبات الأداء.

جميع الصور ما لم يذكر خلاف ذلك هي من قبل المؤلف.

اترك تعليقاً

لن يتم نشر عنوان بريدك الإلكتروني. الحقول الإلزامية مشار إليها بـ *

زر الذهاب إلى الأعلى