मशीन लर्निंग-ऑप्टिमाइझ्ड ब्लूम फिल्टर्सच्या मदतीने Roblox स्पार्क जॉइन क्वेरी खर्च कसा कमी करते

सारांश

दररोज Roblox वर, 70 दशलक्ष वापरकर्ते लाखो अनुभवांमध्ये गुंततात, ज्यामुळे तिमाही एकूण 16 अब्ज तास होतात. ही परस्परसंवाद एक पेटाबाइट-स्तरीय डेटा लेक निर्माण करते, जी विश्लेषण आणि मशीन लर्निंग (ML) साठी समृद्ध केली जाते. आमच्या डेटा लेकमध्ये fact आणि dimension टेबल्स जोडणे संसाधन-गहन आहे, त्यामुळे या प्रक्रियेचे अनुकूलन करण्यासाठी आणि डेटा हलवण्याचे प्रमाण कमी करण्यासाठी, आम्ही Learned Bloom Filters [1]—ML वापरून तयार केलेली स्मार्ट डेटा संरचना—आपणली. उपस्थितीचा अंदाज लावून, हे फिल्टर्स जोडणीसाठी आवश्यक डेटा लक्षणीयरीत्या कमी करतात, ज्यामुळे कार्यक्षमता वाढते आणि खर्च कमी होतो. या प्रक्रियेत, आम्ही आमच्या मॉडेल आर्किटेक्चरमध्ये सुधारणा केल्या आणि प्रक्रिया करण्यासाठी आवश्यक मेमरी व CPU तास कमी करण्याबरोबरच ऑपरेशनल स्थिरता वाढविण्यात त्यांचे महत्त्वपूर्ण फायदे दाखविले.

परिचय

आमच्या डेटा लेकमध्ये कार्यक्षम प्रवेशासाठी तथ्य तक्त्यांना आणि डेटा क्यूब्सना कालांतराने विभागले जाते, तर परिमाण तक्त्यांमध्ये असे विभाग नसतात, आणि अद्यतनांदरम्यान त्यांना तथ्य तक्त्यांसोबत जोडणे संसाधन-गहन असते. जोडाचे मुख्य क्षेत्र जोडल्या जाणाऱ्या तथ्य तक्त्याच्या कालांतराने विभाजनाद्वारे चालवले जाते. त्या कालांतरातील विभाजनात उपस्थित असलेल्या परिमाणांच्या घटकांचा संपूर्ण परिमाण डेटासेटमध्ये उपस्थित असलेल्या घटकांचा एक लहान उपसमूह असतो. परिणामी, या जोडण्यांमध्ये शफल केलेला बहुसंख्य परिमाण डेटा शेवटी नाकारला जातो. या प्रक्रियेचे अनुकूलन करण्यासाठी आणि अनावश्यक शफलिंग कमी करण्यासाठी, आम्ही वेगळ्या जॉइन कींवर ब्लूम फिल्टर्स वापरण्याचा विचार केला, परंतु फिल्टरचा आकार आणि मेमरी फूटप्रिंटच्या समस्यांचा सामना करावा लागला.

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

लर्नड ब्लूम फिल्टर्ससह जॉइन कार्यक्षमतेत सुधारणा

तथ्य आणि परिमाण तक्त्यांमधील जॉइनचे अनुकूलन करण्यासाठी, आम्ही Learned Bloom Filter अंमलबजावणी स्वीकारली. आम्ही तथ्य तक्त्यातील उपस्थित कीजवरून एक निर्देशांक तयार केला आणि नंतर जॉइन ऑपरेशनपूर्वी परिमाण डेटा पूर्व-छाननी करण्यासाठी हा निर्देशांक तैनात केला. 

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

जरी पारंपारिक ब्लूम फिल्टर कार्यक्षम असला, तरी आमच्या अपेक्षित फॉल्स पॉझिटिव्ह दराला गाठण्यासाठी त्याला लोड करणाऱ्या प्रत्येक वर्कर नोडवर तो 15-25% अतिरिक्त मेमरी जोडतो. परंतु लर्नड ब्लूम फिल्टर्सचा वापर करून, आम्ही त्याच फॉल्स पॉझिटिव्ह दरावर लक्षणीयरीत्या कमी इंडेक्स आकार साध्य केला. हे ब्लूम फिल्टरचे बायनरी वर्गीकरण समस्येत रूपांतर झाल्यामुळे शक्य झाले आहे. पॉझिटिव्ह लेबल इंडेक्समध्ये मूल्यांच्या उपस्थितीचे सूचक असतात, तर नकारात्मक लेबल त्यांच्या अनुपस्थितीचे सूचक असतात.

एमएल मॉडेलच्या परिचयामुळे मूल्यांची प्रारंभिक तपासणी सुलभ होते, त्यानंतर खोटे नकारात्मक निकाल काढून टाकण्यासाठी बॅकअप ब्लूम फिल्टरचा वापर होतो. मॉडेलच्या संकुचित प्रतिनिधित्वामुळे आणि बॅकअप ब्लूम फिल्टरसाठी आवश्यक कीज (keys) च्या संख्येत घट झाल्यामुळे आकार कमी होतो. हे पारंपारिक ब्लूम फिल्टर पद्धतीपेक्षा वेगळे आहे. 

या कामाचा एक भाग म्हणून, आम्ही आमच्या लर्नड ब्लूम फिल्टर पद्धतीचे मूल्यांकन करण्यासाठी दोन मेट्रिक्स निश्चित केले: इंडेक्सचा अंतिम सीरियलाइज्ड ऑब्जेक्ट आकार आणि जॉइन क्वेरीजच्या अंमलबजावणी दरम्यानचा CPU वापर. 

अंमलबजावणीतील आव्हानांवर मात करणे

आमच्यासमोरचे पहिले आव्हान म्हणजे फॅक्ट टेबलमध्ये काहीच डायमेंशन टेबल कीज असलेल्या अत्यंत पक्षपाती ट्रेनिंग डेटासेटवर काम करणे. असे करताना, आम्हाला टेबलमधील सुमारे तीन पैकी एका कीजमध्ये ओव्हरलॅप आढळला. यावर मात करण्यासाठी, आम्ही सँडविच लर्नड ब्लूम फिल्टर पद्धतीचा [2] वापर केला. ही पद्धत फॅक्ट टेबलमधून गहाळ असलेल्या बहुसंख्य कीज काढून टाकून डेटासेटचे वितरण पुनर्संतुलित करण्यासाठी सुरुवातीच्या पारंपारिक ब्लूम फिल्टरचा समावेश करते, ज्यामुळे डेटासेटमधील नकारात्मक नमुने प्रभावीपणे काढून टाकले जातात. यानंतर, फक्त प्रारंभिक ब्लूम फिल्टरमध्ये समाविष्ट कीज आणि चुकीचे सकारात्मक (false positives) ML मॉडेलकडे पाठवण्यात आले, ज्याला अनेकदा "लर्न्ड ओरेकल" असे संबोधले जाते. या पद्धतीमुळे लर्न्ड ओरेकलसाठी एक संतुलित प्रशिक्षण डेटासेट तयार झाला आणि पक्षपाताची समस्या प्रभावीपणे दूर झाली.

दुसरे आव्हान मॉडेलची रचना आणि प्रशिक्षण वैशिष्ट्यांवर केंद्रित होते. फिशिंग URL [1] या पारंपारिक समस्येपेक्षा वेगळे, आमच्या जॉइन कीज (ज्या बहुतेक प्रकरणांमध्ये वापरकर्ते/अनुभवांसाठी अद्वितीय ओळख क्रमांक असतात) स्वतःच माहितीपूर्ण नव्हत्या. यामुळे आम्हाला डायमेंशन अॅट्रिब्यूट्सना संभाव्य मॉडेल वैशिष्ट्ये म्हणून तपासण्यास प्रवृत्त केले, जे डायमेंशन एंटिटी फॅक्ट टेबलमध्ये उपस्थित आहे की नाही हे भाकीत करण्यात मदत करू शकतात. उदाहरणार्थ, समजा एखाद्या तथ्य तक्त्यात विशिष्ट भाषेतील अनुभवांसाठी वापरकर्त्याच्या सत्र माहितीचा समावेश आहे. वापरकर्ता परिमाणातील भौगोलिक स्थान किंवा भाषा प्राधान्य गुणधर्म हे एखादा विशिष्ट वापरकर्ता तथ्य तक्त्यात उपस्थित आहे की नाही हे ओळखण्याचे चांगले निर्देशक ठरू शकतात.

तिसरी आव्हान—निष्कर्षातील विलंब—अशी मॉडेल्स आवश्यक होती ज्यांनी खोटे नकारात्मक निकाल कमीतकमी ठेवले आणि जलद प्रतिसाद दिला. या मुख्य मेट्रिक्ससाठी ग्रेडियंट-बूस्टेड ट्री मॉडेल सर्वोत्तम निवड ठरला, आणि आम्ही अचूकता व गती यात संतुलन साधण्यासाठी त्याचे वैशिष्ट्य संच छाटले.

शिकवलेल्या ब्लूम फिल्टर्सचा वापर करून आमची अद्ययावत जॉइन क्वेरी खालीलप्रमाणे आहे:

परिणाम

येथे आमच्या डेटा लेकमध्ये Learned Bloom फिल्टर्ससह केलेल्या प्रयोगांचे निकाल आहेत. आम्ही त्यांना पाच उत्पादन कार्यभारांमध्ये समाकलित केले, ज्यापैकी प्रत्येकाची डेटा वैशिष्ट्ये वेगवेगळी होती. या कार्यभारांचा सर्वात जास्त गणनात्मक खर्च fact table आणि dimension table यांच्यातील join मध्ये होतो. फॅक्ट टेबलचे की स्पेस डायमेंशन टेबलच्या सुमारे 30% इतके आहे. प्रथम, आम्ही पारंपारिक ब्लूम फिल्टर्सच्या तुलनेत लर्नड ब्लूम फिल्टरने अंतिम सिरियलाइज्ड ऑब्जेक्टच्या आकारात कसे उत्कृष्ट प्रदर्शन केले ते पाहतो. नंतर, आमच्या वर्कलोड प्रोसेसिंग पाइपलाइन्समध्ये लर्नड ब्लूम फिल्टर्स समाकलित करून आम्ही पाहिलेल्या कामगिरी सुधारणा दाखवतो.

लर्न्ड ब्लूम फिल्टर आकार तुलना

जसे खाली दाखवले आहे, दिलेल्या खोट्या सकारात्मक दरावर पाहता, पारंपारिक ब्लूम फिल्टरच्या तुलनेत शिकवलेल्या ब्लूम फिल्टरच्या दोन आवृत्त्या एकूण ऑब्जेक्ट आकारात 17-42% ने सुधारणा करतात.

याव्यतिरिक्त, आमच्या ग्रेडियंट बूस्टेड ट्री-आधारित मॉडेलमध्ये वैशिष्ट्यांच्या लहान उपसमूहाचा वापर करून, आम्ही इन्फरन्स जलद करताना फक्त थोड्या टक्केवारीने ऑप्टिमायझेशन गमावले.

शिकलेल्या ब्लूम फिल्टर वापराचे निकाल 

या विभागात, आम्ही ब्लूम फिल्टर-आधारित जॉइन्सचे कार्यप्रदर्शन विविध मेट्रिक्सवर नियमित जॉइन्सच्या कार्यप्रदर्शनाशी तुलना करतो. 

खालील तक्त्यात लर्नड ब्लूम फिल्टर वापरल्यास आणि न वापरल्यास होणाऱ्या वर्कलोड्सच्या कामगिरीची तुलना केली आहे. दोन्ही जॉइन प्रकारांसाठी समान क्लस्टर कॉन्फिगरेशन राखून, एकूण 1% खोटे सकारात्मक शक्यता असलेला लर्नड ब्लूम फिल्टर खालील तुलना दर्शवितो. 

प्रथम, आम्हाला आढळले की ब्लूम फिल्टरची अंमलबजावणी नियमित जॉइनच्या तुलनेत CPU तासांमध्ये सुमारे 60% ने जास्त कार्यक्षम आहे. ब्लूम फिल्टरचे मूल्यांकन करण्यासाठी लागणाऱ्या अतिरिक्त गणनेमुळे Learned Bloom Filter पद्धतीच्या स्कॅन टप्प्यातील CPU वापरात वाढ झाली. तथापि, या टप्प्यात केलेल्या प्रीफिल्टरिंगमुळे शफल होणाऱ्या डेटाचा आकार कमी झाला, ज्यामुळे पुढील टप्प्यांसाठी वापरला जाणारा CPU कमी झाला आणि एकूण CPU तास कमी झाले.

दुसरे म्हणजे, Learned Bloom Filters ची एकूण डेटा आकारमान आणि एकूण शफल बाइट्स लिहिलेले हे नियमित जॉइनच्या तुलनेत सुमारे 80% कमी असते. यामुळे खाली चर्चा केल्याप्रमाणे जॉइनची कामगिरी अधिक स्थिर होते. 

प्रयोगादरम्यान आमच्या इतर उत्पादन कार्यभारांमध्येही संसाधनांचा वापर कमी झालेला आम्ही पाहिला. सर्व पाच कार्यभारांवर दोन आठवड्यांच्या कालावधीत, लर्नड ब्लूम फिल्टर पद्धतीने सरासरी दररोज 25% खर्च बचत केली, ज्यात मॉडेल प्रशिक्षण आणि निर्देशांक निर्मितीचा देखील समावेश आहे.

जॉइन करताना शफल होणाऱ्या डेटाच्या प्रमाणात कपात झाल्यामुळे, आम्ही आमच्या अ‍ॅनालिटिक्स पाइपलाइनचा ऑपरेशनल खर्च लक्षणीयरीत्या कमी करू शकलो आणि त्यासोबतच ती अधिक स्थिर बनवली. खालील चार्टमध्ये आम्ही प्रयोग केलेल्या पाच वर्कलोडसाठी दोन आठवड्यांच्या कालावधीत नियमित जॉइन वर्कलोड आणि लर्नड ब्लूम फिल्टर-आधारित वर्कलोडसाठी रनच्या कालावधीत (वॉल क्लॉक टाइम) होणाऱ्या बदलत्या प्रमाणाचे (वariatioN coefficient वापरून) दर्शविले आहे. लर्नड ब्लूम फिल्टर वापरून केलेल्या रन अधिक स्थिर—कालावधीत अधिक सुसंगत—होते, ज्यामुळे त्यांना स्वस्त, तात्पुरत्या आणि अविश्वसनीय संगणकीय संसाधनांवर हलवण्याची शक्यता निर्माण होते. 

संदर्भ

[1] टी. क्रस्का, ए. ब्यूटल, ई. एच. ची, जे. डीन, आणि एन. पॉलिझोटीस. शिकलेल्या निर्देशांक संरचनांसाठी युक्तिवाद. https://arxiv.org/abs/1712.01208, 2017.

[2] M. Mitzenmacher. सँडविचिंगद्वारे शिकलेल्या ब्लूम फिल्टर्सचे अनुकूलन. 

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

¹30 जून 2023 रोजी संपलेल्या 3 महिन्यांपर्यंत

²30 जून 2023 रोजी संपलेल्या 3 महिन्यांपर्यंत