CUCKOO vs BLOOM filter ، من منظور Gopher

في هذه المقالة ، أحاول تنفيذ واختبار كفاءة مرشح الوقواق على مرشح إزهار. (اقرأ المنشور السابق على Chord DHT ، تنفيذ جدول التجزئة الموزع في Golang)

المقدمة

تعد هياكل البيانات الاحتمالية مفيدة للغاية ، خاصةً عند معالجة مجموعات البيانات الكبيرة. في معظم الأوقات ، أثناء العمل على جانب البيانات من الأشياء ، قد يرغب المرء في إجراء استعلام بسيط "هو العنصر غير موجود" أو "هل العنصر موجود بالفعل" أثناء معالجة بيانات الوقت الفعلي. لنفترض أنك تريد الإجابة على استفساراتك في الوقت الفعلي ، مثل عدد IPS الفريد ، الأكثر تكرارًا ، إذا كان قد تم تقديم إعلان بالفعل إلى مستخدم ما ، فإن استخدام هياكل البيانات الاحتمالية يوفر وسيلة فعالة للمساحة للإجابة على هذه الاستعلامات. تتمثل الطريقة المعتادة لمثل هذه الاستعلامات في استخدام إما HashMap أو HashTable ، أو تخزينها في ذاكرة تخزين مؤقت خارجية (مثل redis) ، ولكن المشكلة تتعلق بمجموعات البيانات الكبيرة ، ولا يمكن أن تتوافق هياكل البيانات البسيطة هذه مع الذاكرة. هذا هو المكان الذي تلعب فيه هياكل البيانات الاحتمالية دورها بسبب مساحتها وميزاتها الزمنية.

مثال حالات الاستخدام

  • يستخدم كل من Google Bigtable و Apache HBase و Apache Cassandra و Postgresql عوامل تصفية Bloom لتقليل عمليات البحث عن الأقراص للصفوف أو الأعمدة غير الموجودة. يؤدي تجنب عمليات البحث عن الأقراص المكلفة إلى زيادة كبيرة في أداء عملية استعلام قاعدة البيانات.
  • يستخدم متوسط ​​عوامل تصفية Bloom للتحقق مما إذا كان قد تم بالفعل التوصية بمقال للمستخدم
  • يستخدم Ethereum عوامل تصفية Bloom للعثور بسرعة على سجلات على blockchain Ethereum
  • يستخدم متصفح الويب Google Chrome لاستخدام مرشح Bloom لتحديد عناوين URL الضارة. تم التحقق أولاً من أي عنوان URL مقابل مرشح Bloom محلي ، وفقط في حالة إرجاع مرشح Bloom للنتيجة الإيجابية ، تم التحقق الكامل من عنوان URL الذي تم تنفيذه (وحذر المستخدم ، إذا كان ذلك قد أدى أيضًا إلى نتيجة إيجابية)

ما هو في "الوقواق"؟

لقد استخدمنا عوامل تصفية bloom في العديد من الأماكن للإجابة على مثل هذه الاستعلامات على منصة البيانات. لقد صادفت هذه الورقة مؤخرًا على مرشح الوقواق الذي لفت انتباهي. يقول العنوان نفسه ، "مرشح الوقواق: عمليًا أفضل من بلوم" ، لذلك قررت أن أتحقق منه.

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

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

خوارزمية

معلمات المرشح:
1. وظيفتان تجزئة: h1 و h2
2. مجموعة B مع دلاء ن. سيتم استدعاء دلو i-B B [i]

المدخلات: L ، قائمة العناصر التي سيتم إدراجها في مرشح الوقواق.

الخوارزمية:
بينما L ليست فارغة:
    اجعل x هو العنصر الأول في القائمة L. احذف x من القائمة.
    إذا كانت B [h1 (x)] فارغة:
        ضع x في B [h1 (x)]
    عدا ذلك ، إذا كانت B [h2 (x) فارغة]:
        ضع x في B [h2 (x)]
    آخر:
        ليكن y العنصر في B [h2 (x)].
        قم بإعداد y إلى L
        ضع x في B [h2 (x)]

التنفيذ

يبدو التنفيذ بسيطًا للغاية ، لذلك قررت أن أقوم به وأن أقارن مدى فعالية المساحة / الوقت مقارنةً بمرشح bloom. يتكون عامل تصفية Cuckoo من جدول تجزئة Cuckoo الذي يخزن "بصمات الأصابع" للعناصر المدرجة. بصمة العنصر عبارة عن سلسلة بت مشتقة من تجزئة ذلك العنصر. يتكون جدول تجزئة الوقواق من مجموعة من الجرافات حيث يتم تعيين عنصر لإدراجه على جرافتين محتملتين استنادًا إلى وظيفتي تجزئة. يمكن تكوين كل مجموعة لتخزين عدد متغير من بصمات الأصابع. بشكل عام ، يتم تحديد مرشح Cuckoo بواسطة بصمة حجم الجرافة. على سبيل المثال ، يقوم عامل تصفية Cuckoo (2.4) بتخزين بصمات أصابع بطول 2 بت ويمكن لكل مجموعة في جدول تجزئة Cuckoo تخزين ما يصل إلى 4 بصمات.

إدراج

الخوارزمية:

و = بصمة (س) ؛
i1 = hash (x)؛
i2 = i1 ⊕ hash (f) ؛
إذا كان الجرافة [i1] أو الجرافة [i2] بها إدخال فارغ بعد ذلك
   أضف f إلى ذلك الدلو ؛
   تم
// يجب نقل العناصر الموجودة ؛
أنا = عشوائيا اختيار i1 أو i2 ؛
ل n = 0 ؛ n 
// Hashtable يعتبر ممتلئ؛
عودة الفشل.

الشفرة:

بحث

الخوارزمية:

و = بصمة (س) ؛
i1 = hash (x)؛
i2 = i1 ⊕ hash (f) ؛
إذا كان الجرافة [i1] أو الجرافة [i2] بها f
    عودة صحيح
عودة كاذبة؛

الشفرة:

حذف

الخوارزمية:

و = بصمة (س) ؛
i1 = hash (x)؛
i2 = i1 ⊕ hash (f) ؛
إذا كان الجرافة [i1] أو الجرافة [i2] بها f
   إزالة نسخة من f من هذا الدلو ؛
   عودة صحيح
عودة كاذبة؛

الشفرة:

تجربة أداء

لقد استخدمت مكتبة Will Fitzgerald للاختبار على مرشح Bloom. الحصة FPP (الاحتمالات الإيجابية الخاطئة) المأخوذة لفلتر الوقواق هي 0.001

تعقيد الفضاء

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

تعقيد الوقت

في تجزئة الوقواق ، يبدو إدراج عنصر أسوأ بكثير من O (1) في أسوأ الحالات لأنه قد يكون هناك العديد من الحالات أثناء الاصطدام ، حيث يتعين علينا إزالة قيمة لإفساح المجال للقيمة الحالية. بالإضافة إلى ذلك ، إذا كانت هناك دورة ، فيجب إعادة صياغة الجدول بأكمله.

يؤدي إجراء تحليل زمني لكلتا المرشحات إلى النتائج التالية:

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

الإستنباط

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

الشفرة

المراجع

  • https://brilliant.org/wiki/cuckoo-filter/
  • https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf
  • https://en.wikipedia.org/wiki/Cuckoo_hashing
  • https://blog.fastforwardlabs.com/2016/11/23/probabilistic-data-structure-showdown-cuckoo.html

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