كيف تقلل Roblox تكاليف استعلامات Spark Join باستخدام مرشحات Bloom المُحسّنة بالتعلم الآلي

ملخص

كل يوم على Roblox، يتفاعل 70 مليون مستخدم مع ملايين التجارب، بإجمالي 16 مليار ساعة كل ثلاثة أشهر. ينتج عن هذا التفاعل بحيرة بيانات بحجم بيتابايت، يتم إثرائها لأغراض التحليلات والتعلم الآلي (ML). إن ربط جداول الحقائق والأبعاد في بحيرة البيانات لدينا يستهلك موارد كثيرة، لذا من أجل تحسين ذلك وتقليل إعادة ترتيب البيانات، اعتمدنا مرشحات بلوم المُتعلمة [1] — وهي هياكل بيانات ذكية تستخدم التعلم الآلي. من خلال توقع التواجد، تعمل هذه المرشحات على تقليص بيانات الدمج بشكل كبير، مما يعزز الكفاءة ويقلل التكاليف. وفي أثناء ذلك، قمنا أيضًا بتحسين بنى نماذجنا وأثبتنا الفوائد الجوهرية التي تقدمها لتقليل استهلاك الذاكرة وساعات وحدة المعالجة المركزية (CPU) للمعالجة، فضلاً عن زيادة الاستقرار التشغيلي.

مقدمة

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

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

تعزيز كفاءة عملية الدمج باستخدام مرشحات بلوم المُدرّبة

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

التطور من مرشحات بلوم التقليدية إلى مرشحات بلوم المُتعلمة

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

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

كجزء من هذا العمل، وضعنا مقياسين لتقييم نهج مرشح بلوم المُتعلم: الحجم النهائي للكائن المتسلسل للفهرس واستهلاك وحدة المعالجة المركزية (CPU) أثناء تنفيذ استعلامات الانضمام. 

التغلب على تحديات التنفيذ

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

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

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

يظهر أدناه استعلام الانضمام المحدث باستخدام مرشحات بلوم المُتعلمة:

النتائج

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

مقارنة حجم مرشح بلوم المُتعلم

كما هو موضح أدناه، عند النظر إلى معدل إيجابي كاذب معين، يعمل النوعان من مرشحات بلوم المُتعلمة على تحسين الحجم الإجمالي للكائنات بنسبة تتراوح بين 17 و42% مقارنةً بمرشحات بلوم التقليدية.

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

نتائج استخدام مرشح بلوم المكتسب 

في هذا القسم، نقارن أداء عمليات الدمج المستندة إلى مرشح بلوم بأداء عمليات الدمج العادية عبر عدة مقاييس. 

يقارن الجدول أدناه أداء أحمال العمل مع استخدام مرشحات بلوم المُتعلمة وبدونها. تُظهر مرشحة بلوم المُتعلمة ذات احتمال إيجابي كاذب إجمالي بنسبة 1% المقارنة أدناه مع الحفاظ على نفس تكوين المجموعة لكلا نوعي عمليات الربط. 

أولاً، وجدنا أن تطبيق مرشح بلوم (Bloom Filter) تفوق على عملية الدمج العادية بنسبة تصل إلى 60٪ في ساعات استخدام وحدة المعالجة المركزية (CPU). لاحظنا زيادة في استخدام وحدة المعالجة المركزية (CPU) في خطوة المسح بالنسبة لنهج مرشح بلوم المُتعلم (Learned Bloom Filter) بسبب الحساب الإضافي الذي تم إنفاقه في تقييم مرشح بلوم. ومع ذلك، فإن التصفية المسبقة التي تمت في هذه الخطوة قللت من حجم البيانات التي يتم خلطها، مما ساعد في تقليل استخدام وحدة المعالجة المركزية (CPU) في الخطوات اللاحقة، وبالتالي تقليل إجمالي ساعات استخدام وحدة المعالجة المركزية (CPU).

ثانيًا، تقل حجم البيانات الإجمالي لـ Learned Bloom Filters بنحو 80٪، كما تقل بايتات التبديل الإجمالية المكتوبة بنحو 80٪ مقارنة بالربط العادي. وهذا يؤدي إلى أداء ربط أكثر استقرارًا كما هو موضح أدناه. 

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

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

المراجع

[1] T. Kraska، A. Beutel، E. H. Chi، J. Dean، و N. Polyzotis. The Case for Learned Index Structures. https://arxiv.org/abs/1712.01208، 2017.

[2] M. Mitzenmacher. تحسين مرشحات بلوم المكتسبة عن طريق التداخل. 

https://arxiv.org/abs/1803.01474، 2018.

¹اعتبارًا من الربع المنتهي في 30 يونيو 2023

²اعتبارًا من الـ 3 أشهر المنتهية في 30 يونيو 2023