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

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

هذا يعني أن طلبًا من عنوان IP الذي تم حله 192.0.2.1 تم تسجيله في مركز بيانات Cloudflare رقم 107. جاءت هذه البيانات من مصادر عديدة ، بما في ذلك عيناتنا النشطة والسلبية ، وسجلات بعض المجالات التي نمتلكها (على سبيل المثال ،cloudflare.com) ، المصادر المفتوحة (على سبيل المثال ، جداول BGP) ، إلخ. عادة ما يتكرر نفس السطر في عدة ملفات.

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

ويكفي أن نقول أن خطوط عدم تكرار مع أوامر العادية من نوع sortفي تشكيلات مختلفة (انظر --parallel، --buffer-sizeو --unique) لم يكن الأفضل لمثل هذه مجموعة كبيرة من البيانات.

مرشحات بلوم

رسم توضيحي لديفيد إبشتاين في المجال العام

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

هذا مثالي لمرشحات بلوم!

أثناء قراءةويكيبيديا على فلاتر بلوم، هذه هي الطريقة التي أنظر بها إلى هيكل البيانات هذا.

كيف ستطبقالتعددية؟ بالنظر إلى وظيفة التجزئة المثالية والذاكرة اللامتناهية ، يمكننا ببساطة إنشاء صورة نقطية غير محدودة وتعيين رقم بت لكل عنصرhash(item). وهذا يوفر بنية البيانات المثالية لـ "التعدد". حق؟ بشكل تافه. لسوء الحظ ، تتصادم وظائف التجزئة ، ولا توجد ذاكرة لا حصر لها ، لذلك في واقعنا يجب أن نتنازل. ولكن يمكننا حساب احتمال الاصطدامات وإدارة هذه القيمة. على سبيل المثال ، لدينا وظيفة تجزئة جيدة وذاكرة 128 جيجابايت. يمكننا حساب أن احتمال الاصطدام لكل عنصر جديد هو 1 في 1099511627776. عند إضافة المزيد من العناصر ، يزداد الاحتمال مع امتلاء الصورة النقطية.

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

n - عدد العناصر المدرجة (العدد الأساسي)
m - الذاكرة المستخدمة من قبل الصورة النقطية
k - عدد وظائف التجزئة المحسوبة لكل إدخال
p - احتمال مصادفة موجبة كاذبة

بالنظر إلى الرقم الأساسي nوالاحتمال المطلوب للنتائج الإيجابية الخاطئة p، يُرجع عامل تصفية بلوم الذاكرة mالمطلوبة والعدد المطلوب من وظائف التجزئة k.

تحقق من هذا التصور الممتاز لتوماس هيرست لكيفية تأثير المعلمات على بعضها البعض.

mmuniq-bloom

استرشدت بالحدس ، أضفت الأداة الاحتمالية mmuniq-bloom إلى ترسانتي ، والتي تأخذ مدخلات STDIN وترجع فقط خطوط فريدة في STDOUT. يجب أن يكون أسرع بكثير من مزيج من sort+ uniq!

ها هو:

mmuniq-bloom.c

من أجل البساطة والسرعة ، قمت في البداية بتعيين بعض المعلمات. أولاً ، ما لم يذكر خلاف ذلك ، يستخدم mmuniq-bloom ثماني وظائف تجزئة k = 8. يبدو أن هذا قريب من الرقم الأمثل لحجم البيانات لدينا ، ويمكن أن تنتج وظيفة التجزئة بسرعة ثمانية تجزئة لائقة. ثم نقوم بمحاذاة الذاكرة mفي الصورة النقطية مع قوة اثنين لتجنب عملية باهظة الثمن %modulo، والتي تنخفض في المجمع إلى بطيئة div. إذا كان الصفيف يساوي قوة اثنين ، فيمكننا فقط استخدام أحادي المعامل AND (للمتعة اقرأ كيف يحسن المترجمون بعض عمليات القسمة بالضرب في ثابت سحري ).

الآن يمكننا تشغيله على نفس ملف البيانات الذي استخدمناه من قبل:

أوه ، هذا أفضل بكثير! 12 ثانية بدلاً من دقيقتين. يستخدم البرنامج بنية بيانات محسنة ، وكمية محدودة نسبيًا من الذاكرة ، وتحليل خطي محسن وتخزين جيد للإخراج ... ومع كل هذا ، تبدو 12 ثانية وكأنها أبدية مقارنة بالأداة wc -l:

ما الذي يحدث؟ أتفهم أن حساب السلاسل wcأسهل من حساب السلاسل الفريدة ، ولكن هل فرق 26 مرة له ما يبرره حقًا؟ ماذا تأخذ وحدة المعالجة المركزية mmuniq-bloom؟

يجب أن يكون لحسابات التجزئة. wcلا تنفق الأداة المعالج ، وتقوم بكل هذه الحسابات الغريبة لكل خط من 40 مليون خط. أستخدم وظيفة تجزئة غير تافهة إلى حد ما siphash24، بالتأكيد أنها تحرق المعالج ، أليس كذلك؟ دعنا نتحقق من خلال تشغيل وظيفة التجزئة فقط ، ولكن ليسعدم إجراء أي عمليات باستخدام مرشح Bloom:

هذا أمر غريب. يستغرق حساب دالة التجزئة حوالي ثانيتين فقط ، على الرغم من تنفيذ البرنامج بالكامل في التشغيل السابق لمدة 12 ثانية. هل يعمل مرشح بلوم لمدة 10 ثوان؟ كيف يكون هذا ممكنا؟ هذه بنية بيانات بسيطة ...

السلاح السري - المحلل

حان الوقت لتطبيق الأداة المناسبة لهذه المهمة - فلنشغل المحلل ونرى ما الذي يعمل عليه المعالج. أولاً ، دعنا نركض straceللتحقق من عدم وجود مكالمات نظام غير متوقعة:

كل شيء يبدو جيدًا. عشرة مكالمات إلى mmap4 مللي ثانية لكل (3971 μs) مثيرة للفضول ، لكن هذا جيد. نملأ الذاكرة مسبقًا MAP_POPULATE، لمنع الأخطاء لاحقًا بسبب نقص الصفحة.

ما هي الخطوة التالية؟ بالطبع هو كذلك perf!

ثم دعنا نرى النتيجة:

لذا ، نحرق 87.2٪ من الدورات في الكود الرئيسي. دعونا نرى أين بالضبط. يظهر الفريق على perf annotate process_line --sourceالفور شيئًا غير متوقع.

نرى أن 26.90٪ من المعالج أحترقmov، لكن هذا ليس كل شيء! يقوم المترجم بإدخال الوظيفة بشكل صحيح ويوسع الحلقة. اتضح أن معظم الدورات تذهب إلى هذا movأو إلى الخط uint64_t v = *p!

من الواضح أن الكمال خاطئ ، كيف يمكن لهذه السلسلة البسيطة أن تستهلك الكثير من الموارد؟ لكن تكرار الاختبار مع أي محلل آخر يظهر نفس المشكلة. على سبيل المثال ، أحب استخدام google-perftools مع kcachegrind بسبب الرسوم البيانية الملونة:

نتيجة التصور هي كما يلي:

دعني ألخص ما اكتشفناه حتى الآن.

تقوم الأداة المساعدة القياسية wcبمعالجة ملف 600 ميغا بايت لوقت معالج يبلغ 0.45 ثانية. تعمل أداتنا المُحسّنة mmuniq-bloom12 ثانية. يتم حرق المعالج بناءً على تعليمات واحدة mov، مما يؤدي إلى إلغاء الإشارة إلى الذاكرة ...

صورة خوسيه نيكداو ، CC BY / 2.0

Oh! كيف يمكنني ان انسى. الوصول العشوائي إلى الذاكرةبطيءحقا! بطيء جدا جدا جدا!

وفقًاللأرقام التي يجب أن يعرفها كل مبرمج، يستغرق الوصول الفردي إلى ذاكرة الوصول العشوائي حوالي 100 نانوثانية. دعونا نحسب: 40 مليون خط ، 8 تجزئات لكل منها. نظرًا لأن فلتر بلوم لدينا يحتوي على حجم 128 ميجابايت ،فإنه لا يصلح فيأجهزتنا القديمةفي ذاكرة التخزين المؤقت L3! يتم توزيع التجزئة بشكل متساوٍ على نطاق واسع من الذاكرة - ينتج عن كل منها خطأ في ذاكرة التخزين المؤقت. ضع كل شيء معًا ، واتضح ...

اتضح أن 32 ثانية تحترق فقط عند وصول الذاكرة. يتناسب البرنامج الحقيقي في 12 ثانية فقط ، لأن مرشح Bloom لا يزال يستفيد من التخزين المؤقت. من السهل رؤية ذلك مع perf stat -d:

نعم ، كان يجب أن يكون لدينا 320 مليون على الأقل من ذاكرة التخزين المؤقت (LLC-load-misses) ، ولكن حدث 280 مليون فقط: لا يزال هذا لا يفسر سبب عمل البرنامج في 12 ثانية فقط. لكن لا يهم. من المهم أن يكون عدد ذاكرة التخزين المؤقت المفقودة مشكلة حقيقية ، ولا يمكننا حلها إلا عن طريق تقليل عدد مرات الوصول إلى الذاكرة. دعنا نحاول تهيئة مرشح Bloom لاستخدام وظيفة التجزئة واحدة فقط:

Ay! انه حقا مؤلم! للحصول على احتمالية تصادم تبلغ 1 لكل 10000 سطر ، تطلب مرشح بلوم 64 جيجابايت من الذاكرة. انه شئ فظيع!

بالإضافة إلى ذلك ، لا يبدو أن السرعة زادت بشكل ملحوظ. استغرق نظام التشغيل 22 ثانية لتحضير الذاكرة لنا ، لكننا ما زلنا نقضي 11 ثانية في مساحة المستخدم. أعتقد أنه الآن يتم تعويض جميع مزايا الوصول النادر إلى الذاكرة من خلال احتمال أقل للدخول إلى ذاكرة التخزين المؤقت بسبب زيادة حجم الذاكرة بشكل حاد. في وقت سابق ، كان 128 ميجابايت كافيا لمرشح بلوم!

رفض مرشحات بلوم

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

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

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

رسم توضيحي لـ Vadims Podans

يجتمع التجزئة mmuniq

هنا هو الإصدار الجديد من mmuniq-bloom باستخدام جدول التجزئة:

mmuniq-hash.c

بدلاً من البتات لمرشح Bloom ، نقوم الآن بتخزين تجزئات 64 بت من وظيفة "siphash24" . وهذا يوفر حماية أفضل بكثير من تصادمات التجزئة: أفضل بكثير من واحد لكل 10000 سطر.

دعونا نحسب. إضافة عنصر جديد إلى جدول التجزئة ، على سبيل المثال مع 40 مليون إدخال ، يمنح فرصة تصادمات التجزئة 40 000 000/2^64. هذا هو حوالي 1 في 461 مليار - احتمال ضعيف إلى حد ما. لكننا لا نضيف عنصرًا واحدًا إلى المجموعة المعبأة مسبقًا! بدلاً من ذلك ، نضيف 40 مليون صف إلى المجموعة الفارغة في البداية. وفقًا لمفارقة عيد الميلاد ، فإن هذا يزيد بشكل كبير من احتمال الاصطدام. سيكون تقريب معقول تقدير '~n^2/2m، في حالتنا هو~(40M^2)/(2*(2^64)). تبين فرصة واحدة من أصل 23000. وبعبارة أخرى ، مع وظيفة التجزئة الجيدة ، نتوقع تصادمًا في واحدة من 23000 مجموعة عشوائية من 40 مليون عنصر. هذا احتمال غير صفري ، لكنه لا يزال أفضل من مرشح بلوم ، وهو مقبول تمامًا لحالة الاستخدام الخاصة بنا.

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

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

من المثال السابق ، نعلم أن دالة التجزئة لدينا تستغرق حوالي ثانيتين. نستنتج أن 40 مليون وصول للذاكرة يستغرق حوالي أربع ثوان.

الدروس المستفادة

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

هياكل البيانات المتقدمة مثيرة للاهتمام للغاية ، ولكن كن حذرا. تتطلب أجهزة الكمبيوتر الحديثة استخدام خوارزميات محسّنة لذاكرة التخزين المؤقت. عند العمل مع مجموعات بيانات كبيرة لا تتناسب مع L3 ، يُفضل التحسين على عدد النتائج ، بدلاً من التحسين على مقدار الذاكرة المستخدمة.

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

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

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

أخيرا ، لا تكرر خطأي. تحتاج دائمًا إلى تنفيذ ملف التعريف أولاًperf stat -dوإلقاء نظرة على عداد IPC (تعليمات لكل دورة). إذا كان أقل من واحد ، فهذا يعني عادة أن البرنامج عالق في انتظار الذاكرة. القيم المثلى فوق اثنين. هذا يعني أن عبء العمل يقع بشكل رئيسي على وحدة المعالجة المركزية. لسوء الحظ ، في مهامي ، IPC لا يزال منخفضًا ...

mmuniq متفوقة

بمساعدة زملائي ، كتبت نسخة محسنة من أداة mmuniq على أساس جدول تجزئة. هذا هو الرمز:

mmuniq.c

يمكنه تغيير حجم جدول التجزئة ديناميكيًا ، ويدعم الإدخال برقم أساسي تعسفي. ثم يعالج البيانات في الحزم ، ويستخدم بشكل فعال التلميح prefetchفي وحدة المعالجة المركزية ، مما يسرع البرنامج بنسبة 35-40 ٪. كن حذرًا ، prefetchنادرًا ما يؤدي الاستخدام بكثرة في الشفرة إلى التأثير. لاستخدام هذه الوظيفة ، قمت بإعادة ترتيب الخوارزميات بشكل خاص. مع كل التحسينات ، تم تقليل وقت التنفيذ إلى 2.1 ثانية:

النهاية

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

عندما لا يصلح مرشح الإزهار