मशीन लर्निंग से अनुकूलित ब्लूम फ़िल्टर्स के साथ स्पार्क जॉइन क्वेरी लागत को कैसे कम करता है

सार

रॉब्लॉक्स पर हर दिन, 70 मिलियन उपयोगकर्ता लाखों अनुभवों के साथ जुड़ते हैं, जो त्रैमासिक रूप से कुल 16 बिलियन घंटे होते हैं। यह इंटरैक्शन एक पेटाबाइट-स्केल डेटा लेक उत्पन्न करता है, जिसे एनालिटिक्स और मशीन लर्निंग (एमएल) उद्देश्यों के लिए समृद्ध किया जाता है। हमारे डेटा लेक में फैक्ट और डायमेंशन टेबल्स को जोड़ना संसाधन-गहन है, इसलिए इसे अनुकूलित करने और डेटा शफलिंग को कम करने के लिए, हमने लर्नड ब्लूम फिल्टर्स [1] को अपनाया—एमएल का उपयोग करने वाले स्मार्ट डेटा संरचनाएं। उपस्थिति की भविष्यवाणी करके, ये फ़िल्टर ज्वाइन डेटा को काफी कम कर देते हैं, जिससे दक्षता बढ़ती है और लागत कम होती है। इसके साथ ही, हमने अपने मॉडल आर्किटेक्चर में भी सुधार किया और यह प्रदर्शित किया कि वे प्रोसेसिंग के लिए मेमोरी और सीपीयू समय को कम करने के साथ-साथ परिचालन स्थिरता को बढ़ाने में भी महत्वपूर्ण लाभ प्रदान करते हैं।

परिचय

हमारे डेटा लेक में, कुशल पहुँच के लिए फैक्ट टेबल और डेटा क्यूब्स को कालानुक्रमिक रूप से विभाजित किया जाता है, जबकि डायमेंशन टेबलों में इस तरह के विभाजन नहीं होते हैं, और अपडेट के दौरान उन्हें फैक्ट टेबलों के साथ जोड़ना संसाधन-गहन होता है। जॉइन की मुख्य सीमा उस फैक्ट टेबल के कालानुक्रमिक विभाजन द्वारा निर्धारित होती है जिसे जोड़ा जा रहा है। उस अस्थायी विभाजन में मौजूद आयाम इकाइयां, पूरे आयाम डेटासेट में मौजूद इकाइयों का एक छोटा उपसमूह होती हैं। परिणामस्वरूप, इन जॉइन्स में अधिकांश शफल किया गया आयाम डेटा अंततः त्याग दिया जाता है। इस प्रक्रिया को अनुकूलित करने और अनावश्यक शफलिंग को कम करने के लिए, हमने अलग-अलग जॉइन कीज़ पर ब्लूम फ़िल्टर का उपयोग करने पर विचार किया, लेकिन हमें फ़िल्टर के आकार और मेमोरी फ़ुटप्रिंट की समस्याओं का सामना करना पड़ा।

उन्हें संबोधित करने के लिए, हमने लर्नड ब्लूम फ़िल्टर्स (Learned Bloom Filters) का अन्वेषण किया, जो एक एमएल-आधारित समाधान है जो कम फ़ॉल्स पॉज़िटिव दरों को बनाए रखते हुए ब्लूम फ़िल्टर के आकार को कम करता है। यह नवाचार संगणकीय लागतों को कम करके और सिस्टम की स्थिरता में सुधार करके जॉइन ऑपरेशंस की दक्षता को बढ़ाता है। निम्नलिखित आरेख हमारे वितरित कंप्यूटिंग वातावरण में पारंपरिक और अनुकूलित जॉइन प्रक्रियाओं को दर्शाता है।

सीखा हुआ ब्लूम फ़िल्टर के साथ जॉइन दक्षता में सुधार

तथ्य और आयाम तालिकाओं के बीच जॉइन को अनुकूलित करने के लिए, हमने लर्नड ब्लूम फ़िल्टर कार्यान्वयन को अपनाया। हमने तथ्य तालिका में मौजूद कुंजियों से एक अनुक्रमणिका बनाई और बाद में जॉइन ऑपरेशन से पहले आयाम डेटा को पूर्व-फ़िल्टर करने के लिए इस अनुक्रमणिका को तैनात किया। 

पारंपरिक ब्लूम फ़िल्टर से लर्नड ब्लूम फ़िल्टर तक का विकास

हालाँकि एक पारंपरिक ब्लूम फ़िल्टर कुशल है, यह हमारे वांछित फ़ॉल्स पॉज़िटिव दर को प्राप्त करने के लिए इसे लोड करने वाले प्रत्येक वर्कर नोड पर 15-25% अतिरिक्त मेमोरी जोड़ता है। लेकिन लर्नड ब्लूम फ़िल्टर्स का उपयोग करके, हमने उसी फ़ॉल्स पॉज़िटिव दर को बनाए रखते हुए, काफी कम इंडेक्स आकार प्राप्त किया। ऐसा ब्लूम फ़िल्टर के एक बाइनरी क्लासिफ़िकेशन समस्या में रूपांतरण के कारण है। पॉज़िटिव लेबल इंडेक्स में मानों की उपस्थिति को इंगित करते हैं, जबकि नेगेटिव लेबल का मतलब है कि वे अनुपस्थित हैं।

एक एमएल मॉडल का परिचय मानों के लिए प्रारंभिक जाँच को सुगम बनाता है, जिसके बाद गलत नकारात्मक परिणामों को खत्म करने के लिए एक बैकअप ब्लूम फ़िल्टर का उपयोग होता है। इसका आकार मॉडल के संपीड़ित प्रतिनिधित्व और बैकअप ब्लूम फ़िल्टर द्वारा आवश्यक कुंजियों की कम संख्या के कारण कम होता है। यह इसे पारंपरिक ब्लूम फ़िल्टर दृष्टिकोण से अलग करता है। 

इस कार्य के हिस्से के रूप में, हमने अपनी लर्नड ब्लूम फ़िल्टर (Learned Bloom Filter) पद्धति का मूल्यांकन करने के लिए दो मेट्रिक्स स्थापित किए: इंडेक्स का अंतिम सीरियलाइज़्ड ऑब्जेक्ट आकार और जॉइन क्वेरीज़ के निष्पादन के दौरान सीपीयू खपत। 

अमलीकरण की चुनौतियों से निपटना

हमारी शुरुआती चुनौती फैक्ट टेबल में कुछ ही डायमेंशन टेबल कीज़ वाले एक अत्यधिक पक्षपाती प्रशिक्षण डेटासेट को संबोधित करना था। ऐसा करते हुए, हमने टेबलों के बीच लगभग हर तीन में से एक कीज़ का ओवरलैप देखा। इसे हल करने के लिए, हमने सैंडविच लर्नड ब्लूम फिल्टर दृष्टिकोण [2] का लाभ उठाया। यह फैक्ट टेबल से अनुपस्थित अधिकांश कीज़ को हटाकर डेटासेट वितरण को पुनर्संतुलित करने के लिए एक प्रारंभिक पारंपरिक ब्लूम फिल्टर को एकीकृत करता है, जिससे डेटासेट से नकारात्मक नमूनों को प्रभावी ढंग से समाप्त किया जाता है। इसके बाद, केवल प्रारंभिक ब्लूम फ़िल्टर में शामिल कुंजियाँ, साथ ही फ़ॉल्स पॉज़िटिव, एमएल मॉडल को भेजी गईं, जिसे अक्सर "लर्नड ओरेकल" कहा जाता है। इस दृष्टिकोण के परिणामस्वरूप लर्नड ओरेकल के लिए एक अच्छी तरह से संतुलित प्रशिक्षण डेटासेट तैयार हुआ, जिससे पक्षपात की समस्या प्रभावी ढंग से दूर हो गई।

दूसरी चुनौती मॉडल आर्किटेक्चर और प्रशिक्षण सुविधाओं पर केंद्रित थी। फ़िशिंग URL [1] की क्लासिक समस्या के विपरीत, हमारी जॉइन कीज़ (जो अधिकांश मामलों में उपयोगकर्ताओं/अनुभवों के लिए अद्वितीय पहचानकर्ता होती हैं) स्वाभाविक रूप से सूचनाप्रद नहीं थीं। इसने हमें डायमेंशन विशेषताओं को संभावित मॉडल सुविधाओं के रूप में तलाशने के लिए प्रेरित किया जो यह अनुमान लगाने में मदद कर सकती हैं कि कोई डायमेंशन इकाई फैक्ट टेबल में मौजूद है या नहीं। उदाहरण के लिए, एक ऐसी फैक्ट टेबल की कल्पना करें जिसमें किसी विशेष भाषा में अनुभवों के लिए उपयोगकर्ता सत्र की जानकारी हो। उपयोगकर्ता डायमेंशन का भौगोलिक स्थान या भाषा वरीयता एट्रिब्यूट इस बात के अच्छे संकेतक होंगे कि कोई व्यक्तिगत उपयोगकर्ता फैक्ट टेबल में मौजूद है या नहीं।

तीसरी चुनौती—निष्कर्ष विलंब—ऐसे मॉडल की आवश्यकता थी जो झूठे नकारात्मक परिणामों को कम से कम करें और तेज़ प्रतिक्रियाएं प्रदान करें। इन प्रमुख मेट्रिक्स के लिए एक ग्रेडिएंट-बूस्टेड ट्री मॉडल सबसे उपयुक्त विकल्प था, और हमने सटीकता और गति के बीच संतुलन बनाने के लिए इसके फ़ीचर सेट को छाँटा।

हमारा अपडेटेड जॉइन क्वेरी, सीखे हुए ब्लूम फ़िल्टर का उपयोग करके, नीचे दिखाए अनुसार है:

परिणाम

यहाँ हमारे डेटा लेक में लर्नड ब्लूम फ़िल्टर्स के साथ हमारे प्रयोगों के परिणाम दिए गए हैं। हमने उन्हें पाँच प्रोडक्शन वर्कलोड में एकीकृत किया, जिनमें से प्रत्येक में अलग-अलग डेटा विशेषताएँ थीं। इन वर्कलोड का सबसे अधिक गणनात्मक रूप से महँगा हिस्सा एक फ़ैक्ट टेबल और एक डायमेंशन टेबल के बीच जॉइन है। फैक्ट टेबल्स का की स्पेस डायमेंशन टेबल का लगभग 30% है। सबसे पहले, हम चर्चा करते हैं कि कैसे लर्नड ब्लूम फ़िल्टर ने अंतिम सीरियलाइज़्ड ऑब्जेक्ट साइज़ के मामले में पारंपरिक ब्लूम फ़िल्टर्स से बेहतर प्रदर्शन किया। इसके बाद, हम अपने वर्कलोड प्रोसेसिंग पाइपलाइन्स में लर्नड ब्लूम फ़िल्टर्स को एकीकृत करके देखी गई प्रदर्शन सुधारें दिखाते हैं।

सीखा हुआ ब्लूम फ़िल्टर आकार की तुलना

जैसा कि नीचे दिखाया गया है, जब एक दिए गए फाल्से पॉजिटिव रेट को देखा जाता है, तो लर्नड ब्लूम फ़िल्टर के दो वेरिएंट पारंपरिक ब्लूम फ़िल्टर की तुलना में कुल ऑब्जेक्ट साइज़ में 17-42% तक सुधार करते हैं।

इसके अतिरिक्त, हमारे ग्रेडिएंट बूस्टेड ट्री-आधारित मॉडल में फ़ीचर्स के एक छोटे उपसमूह का उपयोग करके, हमने इंफरेंस को तेज़ बनाने के साथ-साथ ऑप्टिमाइज़ेशन का केवल एक छोटा प्रतिशत ही खोया।

सीखे गए ब्लूम फ़िल्टर उपयोग के परिणाम 

इस अनुभाग में, हम कई मेट्रिक्स पर ब्लूम फ़िल्टर-आधारित जॉइन्स के प्रदर्शन की तुलना नियमित जॉइन्स से करते हैं। 

नीचे दी गई तालिका लर्नड ब्लूम फ़िल्टर के उपयोग के साथ और उसके बिना वर्कलोड के प्रदर्शन की तुलना करती है। 1% कुल फाल्स पॉज़िटिव संभावना वाला एक लर्नड ब्लूम फ़िल्टर दोनों जॉइन प्रकारों के लिए समान क्लस्टर कॉन्फ़िगरेशन बनाए रखते हुए नीचे की तुलना प्रदर्शित करता है। 

सबसे पहले, हमने पाया कि ब्लूम फ़िल्टर कार्यान्वयन ने सीपीयू घंटों में नियमित जॉइन की तुलना में 60% तक बेहतर प्रदर्शन किया। हमने ब्लूम फ़िल्टर का मूल्यांकन करने में खर्च किए गए अतिरिक्त कंप्यूट के कारण लर्नड ब्लूम फ़िल्टर दृष्टिकोण के स्कैन चरण के लिए सीपीयू उपयोग में वृद्धि देखी। हालाँकि, इस चरण में की गई प्रीफ़िल्टरिंग ने शफल किए जा रहे डेटा के आकार को कम कर दिया, जिससे डाउनस्ट्रीम चरणों द्वारा उपयोग किए गए सीपीयू को कम करने में मदद मिली, जिससे कुल सीपीयू घंटे कम हो गए।

दूसरा, लर्नड ब्लूम फ़िल्टर का कुल डेटा आकार एक नियमित जॉइन की तुलना में लगभग 80% कम होता है और कुल शफल बाइट्स लिखे जाने की मात्रा भी लगभग 80% कम होती है। इससे जॉइन का प्रदर्शन अधिक स्थिर होता है, जैसा कि नीचे चर्चा की गई है। 

परीक्षण के दौरान हमारे अन्य प्रोडक्शन वर्कलोड में भी संसाधनों के उपयोग में कमी देखी गई। सभी पांच वर्कलोड पर दो सप्ताह की अवधि में, लर्नड ब्लूम फ़िल्टर दृष्टिकोण ने औसतन 25% की दैनिक लागत बचत उत्पन्न की, जिसमें मॉडल प्रशिक्षण और इंडेक्स निर्माण भी शामिल हैं।

जॉइन करते समय शफल किए गए डेटा की कम मात्रा के कारण, हम अपनी एनालिटिक्स पाइपलाइन के परिचालन लागत को काफी कम करने में सक्षम हुए, साथ ही इसे अधिक स्थिर भी बनाया। निम्न चार्ट, जिन पाँच वर्कलोड पर हमने प्रयोग किया, उनके लिए दो सप्ताह की अवधि में एक नियमित जॉइन वर्कलोड और एक लर्नड ब्लूम फिल्टर आधारित वर्कलोड के रन की अवधि (वॉल क्लॉक टाइम) में परिवर्तनशीलता (परिवर्तन गुणांक का उपयोग करके) को दर्शाता है। लर्नड ब्लूम फ़िल्टर का उपयोग करने वाले रन अधिक स्थिर थे—अवधि में अधिक सुसंगत थे—जो उन्हें सस्ते, अस्थायी और अविश्वसनीय कंप्यूट संसाधनों पर ले जाने की संभावना खोलता है। 

संदर्भ

[1] टी. क्रस्का, ए. ब्यूटल, ई. एच. ची, जे. डीन, और एन. पोलिज़ोतिस. द केस फॉर लर्नड इंडेक्स स्ट्रक्चर्स. https://arxiv.org/abs/1712.01208, 2017.

[2] एम. मिट्ज़ेनमाकर. सैंडविचिंग द्वारा सीखे गए ब्लूम फ़िल्टर का अनुकूलन। 

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

¹30 जून, 2023 को समाप्त हुई 3 महीनों की अवधि तक

²30 जून, 2023 को समाप्त हुई 3 महीनों की अवधि तक