छाया कैश बनाने के लिए हमने मेटा (फेसबुक) के साथ कैसे सहयोग किया

मेटा (फेसबुक), प्रिंसटन यूनिवर्सिटी और ऑलक्सियो के बीच सहयोग के साथ, हमने "शैडो कैश" विकसित किया है - काम करने वाले सेट आकार और अनंत कैश हिट अनुपात को ट्रैक करने के लिए एक हल्का Alluxio घटक। शैडो कैश गतिशील रूप से पिछली विंडो पर काम कर रहे सेट आकार का ट्रैक रख सकता है और ब्लूम फिल्टर की एक श्रृंखला द्वारा कार्यान्वित किया जाता है। मेटा (फेसबुक) प्रेस्टो में शैडो कैश तैनात किया गया है और सिस्टम की अड़चन को समझने और रूटिंग डिजाइन निर्णयों में मदद करने के लिए इसका लाभ उठाया जा रहा है।

प्रेरणा और पृष्ठभूमि

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

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

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

प्रेस्टो की ओर से दो प्रमुख प्रश्नों को संबोधित करने की आवश्यकता है:

1. प्रत्येक टैनेंट के लिए कैशे को कैसे आकार दें?

2. संभावित कैश हिट अनुपात में सुधार क्या है?

हम "शैडो कैश" का प्रस्ताव करते हैं, जो काम करने वाले सेट आकार और कैश हिट दर पर नज़र रखने के लिए एक हल्का Alluxio घटक है।

पहले प्रश्न का उत्तर देने के लिए, शैडो कैश भविष्य की कैश मांग का अनुमान लगाने के लिए व्यवस्थापक को बताएगा कि पिछले 24 घंटों में कैश को कितने गैर-डुप्लिकेट बाइट्स मिले हैं। दूसरे प्रश्न के लिए, शैडो कैश व्यवस्थापक को बताएगा कि यदि कैश पिछले 24 घंटों में सभी अनुरोधों को रख सकता है, तो कितने अनुरोध कैश को हिट करते हैं, अर्थात, अनहिट वे हैं जो कभी नहीं आए, इसलिए अधिकतम हिट दर कैश की गणना की जा सकती है।

यह हल्का Alluxio घटक, शैडो कैश, कैश वर्किंग सेट पर अंतर्दृष्टि प्रदान कर सकता है और कैश हिट रेट कैसा दिखेगा यदि अनंत कैश स्पेस हो। क्लस्टर की कैश स्थिति की निगरानी के लिए, हम निम्नलिखित प्रमुख मैट्रिक्स को परिभाषित करते हैं।

• C1: एक निश्चित समय पर वास्तविक कैश का उपयोग
• C2: एक टाइम विंडो में शैडो कैश वर्किंग सेट (1 दिन / 1 सप्ताह)
• H1: वास्तविक कैश हिट-दर
• H2: शैडो कैश हिट-दर

चुनौती

जबकि हमने Alluxio के कैशे के लिए उपरोक्त मेट्रिक्स प्रदान करने का प्रयास किया है, हमें कई चुनौतियों का सामना करना पड़ा है।

कम मेमोरी और सीपीयू ओवरहेड

शैडो कैश एक हल्का घटक है जो कैश्ड वर्किंग सेट के आकार का ट्रैक रखता है। सीमित स्मृति के साथ "अनंत" कार्यशील सेट का ट्रैक रखना मुश्किल है। शैडो कैश का CPU ओवरहेड भी कम होना चाहिए क्योंकि यह प्रत्येक क्वेरी को संसाधित करते समय डेटा को कैश करता है। अन्यथा, उपयोगकर्ता अनुरोध लंबे समय तक अवरुद्ध रहेंगे।

शुद्धता

शैडो कैश को भी सटीकता की गारंटी देनी चाहिए। प्रेस्टो में, शैडो कैश क्लस्टर की कैश स्थिति को मापता है, और यदि अनुमानित सीमा कैश हिट दर बहुत कम है, तो प्रेस्टो गलत तरीके से यह निर्धारित कर सकता है कि यह कार्य कैश-अमित्र है। इसके विपरीत, यदि अनुमानित सीमा कैश हिट दर बहुत अधिक है, तो प्रेस्टो यह मान सकता है कि इस बिंदु पर क्लस्टर के कैश का विस्तार करने से समग्र प्रदर्शन में उल्लेखनीय सुधार होगा।

गतिशील अद्यतन

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

समाधान

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

ब्लूम फिल्टर: ओवरहेड और एक्यूरेसी चुनौतियों का समाधान

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

ब्लूम फ़िल्टर में k हैश फ़ंक्शन होते हैं। एक तत्व जोड़ने के लिए, प्रत्येक हैश फ़ंक्शन को लागू करें और बिट को 1 पर सेट करें। किसी तत्व को क्वेरी करने के लिए, प्रत्येक हैश फ़ंक्शन और बिट्स को लागू करें। जब k पोजीशन पर सभी बिट्स 1 होते हैं, तो आइटम को अस्तित्व में माना जाता है। अन्यथा, आइटम मौजूद नहीं माना जाता है।

ब्लूम फ़िल्टर श्रृंखला: गतिशील अद्यतन का समाधान

ब्लूम फ़िल्टर कम ओवरहेड और उच्च सटीकता दोनों प्रदान कर सकते हैं, तो क्या हम उन्हें सीधे शैडो कैश पर लागू कर सकते हैं?

हमारे सामने पहली समस्या यह है कि ब्लूम फ़िल्टर विलोपन का समर्थन नहीं करते हैं। ऐसा इसलिए है क्योंकि हम समय के साथ केवल उपयोगकर्ता के एप्लिकेशन के कामकाजी सेट के आकार की परवाह करते हैं, और ऐसा करने के लिए शैडो कैश की आवश्यकता होती है। शैडो कैश एक ब्लूम फ़िल्टर श्रृंखला बनाने के लिए कई फ़िल्टर को एक साथ जोड़कर ऐसा करता है।

यहां बताया गया है कि ब्लूम फ़िल्टर श्रृंखला का उपयोग वास्तविक समय में कार्यशील सेट के लोड आकार को अद्यतन करने के लिए कैसे किया जा सकता है।

प्रश्न: जैसा कि ऊपर दिखाया गया है, शैडो कैश कई ब्लूम फिल्टर से बनी एक श्रृंखला है। पिछले 24 घंटों में किसी उपयोगकर्ता के कार्य सेट के आकार को ट्रैक करते समय, हम 24 घंटों को चार अवधियों में विभाजित कर सकते हैं। ब्लूम फ़िल्टर शैडो कैश में प्रत्येक अवधि को ट्रैक करता है, और प्रत्येक ब्लूम फ़िल्टर एक अवधि को ट्रैक करता है। शैडो कैश सभी मौजूदा ब्लूम फ़िल्टर का उपयोग करता है या क्वेरी के लिए एक नया ब्लूम फ़िल्टर बनाता है, जैसा कि निम्न आकृति में दिखाया गया है।

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

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

जहाँ n* फ़िल्टर में मदों की संख्या का एक अनुमान है, m फ़िल्टर की लंबाई (आकार) है, k हैश फ़ंक्शन की संख्या है, और X एक पर सेट बिट्स की संख्या है।

अनंत आकार हिट अनुपात: कार्यशील सेट आकार मीट्रिक प्रदान करने के बाद, छाया कैश को अनंत आकार हिट अनुपात भी प्रदान करने की आवश्यकता होती है। हम ब्लूम फिल्टर का उपयोग अनंत स्थान के साथ कैश के रूप में कर सकते हैं क्योंकि वे कम मेमोरी उपयोग के साथ बड़ी मात्रा में डेटा को ट्रैक कर सकते हैं। ब्लूम फ़िल्टर को हिट करने वाले उपयोगकर्ता अनुरोधों की संख्या एक अनंत कैश में हिट की संख्या के बराबर होती है, जिसे हिट के रूप में दर्शाया जाता है। "उपयोगकर्ता अनुरोधों" की कुल संख्या को queryNum के रूप में दर्शाया गया है। QueryNum "उपयोगकर्ता अनुरोधों" की कुल संख्या है, इसलिए हिट दर हिट/क्वेरीनम के बराबर है।

प्रेस्टो क्लस्टर कैश स्थिति निर्धारित करने के लिए शैडो कैश का उपयोग करना

ब्लूम फ़िल्टर श्रृंखला को पूरा करने के बाद, हम पहले से परिभाषित मेट्रिक्स H1, H2, C1, C2 को जल्दी से सीख सकते हैं। अगले चरण में, प्रेस्टो उनके बीच आकार संबंध की तुलना करके क्लस्टर की कैश स्थिति का निर्धारण कर सकता है, जैसा कि निम्नलिखित आकृति में दिखाया गया है।

जब H2 कम होता है, तो यह इंगित करता है कि इस क्लस्टर में एप्लिकेशन की कैश हिट दर असीमित कैश स्पेस के साथ भी नहीं पहुंचा जा सकता है। इसका तात्पर्य है कि यह एप्लिकेशन कैश-फ्रेंडली नहीं है। जब H2 अधिक होता है और H1 कम होता है और C2> C1 होता है, तो यह इंगित करता है कि क्लस्टर कम-आवंटित कैश स्थान है और यदि कैश क्षमता का विस्तार किया जाता है तो हिट दर में और सुधार किया जा सकता है। जब H2 अधिक होता है और H1 अधिक होता है और C2 <C1, क्लस्टर कैश अधिक आवंटित होता है और संसाधन बर्बाद हो जाते हैं। यदि H2 > H1 और C2 > C1 और C2 > C1 एक क्लस्टर अच्छी स्थिति में है, जिसका अर्थ है कि कैश को स्केल करने की आवश्यकता नहीं है।

कार्यान्वयन

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

नीचे विन्यास हैं।

#कार्यशील सेट को परिभाषित करने के लिए पिछली विंडो

alluxio.user.client.cache.shadow.window=**24h**

#ट्रैकिंग के लिए उपयोग किए जाने वाले ब्लूम फिल्टर के लिए कुल मेमोरी ओवरहेड

alluxio.user.client.cache.shadow.memory.overhead=**125MB**

# ट्रैकिंग के लिए उपयोग किए जाने वाले ब्लूम फ़िल्टर की संख्या। प्रत्येक विंडो के एक खंड को ट्रैक करता है

alluxio.user.client.cache.shadow.bloomfilter.num=**4**

परीक्षा के परिणाम

हमने शैडो कैश का परीक्षण किया और पाया कि केवल 125MB स्थान के साथ, शैडो कैश केवल 3% की त्रुटि दर के साथ 27TB कार्यशील सेटों को ट्रैक कर सकता है। इसके अलावा, HyperLogLog का उपयोग करके त्रुटि दर को और कम किया जा सकता है, लेकिन यदि HyperLogLog का उपयोग किया जाता है, तो अनंत आकार हिट अनुपात अनुमान समर्थित नहीं होगा।

प्रेस्टो रूटिंग ऑप्टिमाइज़ेशन

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

प्रेस्टो रूटिंग

प्रेस्टो अलग-अलग समूहों में अलग-अलग तालिकाओं को संग्रहीत करता है, कैश को तालिका के नाम से क्लस्टर में साझा करता है। इसलिए, एक ही तालिका तक पहुँचने वाली क्वेरी हमेशा अपने कैश को अधिकतम करने के लिए एक ही लक्ष्य क्लस्टर में जाएगी। यदि ऐसा नहीं किया गया तो क्लस्टर कैश विभिन्न अलग-अलग तालिकाओं से भर जाएगा। नीचे रूटिंग एल्गोरिथम का एक आरेख है।

जैसा कि ऊपर की आकृति में दिखाया गया है, तालिका 1 से तालिका 4 में अलग-अलग तालिका नाम हैं और इसलिए उन्हें अलग-अलग समूहों को सौंपा गया है। तालिका 1 से डेटा का अनुरोध करते समय, रूटिंग एल्गोरिथ्म क्लस्टर 1 को अनुरोध भेजेगा, और तालिका 3 से डेटा का अनुरोध करते समय, रूटिंग एल्गोरिथ्म क्लस्टर 3 को अनुरोध भेजेगा।

रूटिंग ऑप्टिमाइज़ेशन विकल्प

क्लस्टर अनुरोध का प्रतिक्रिया समय यह निर्धारित करने का एक आसान तरीका है कि क्लस्टर काम कर रहा है या नहीं। जब क्लस्टर प्रतिक्रिया देने में धीमा होता है या प्रतिक्रिया देने में बहुत अधिक समय लेता है, तो हम मानते हैं कि क्लस्टर में कोई समस्या है। शैडो कैश के साथ, जैसा कि ऊपर उल्लेख किया गया है, H1, H2, C1, C2 के साथ संयुक्त, हम जल्दी से यह निर्धारित कर सकते हैं कि कैश तनाव के कारण क्लस्टर प्रदर्शन में गिरावट का अनुभव कर रहा है या नहीं।

प्रेस्टो ऐसे खराब प्रदर्शन वाले क्लस्टर के लिए निम्नलिखित तीन रूटिंग ऑप्टिमाइज़ेशन विकल्पों का प्रस्ताव करता है। बेशक, प्रत्येक विकल्प का अपना ट्रेडऑफ़ होता है।

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

सारांश

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

कुल मिलाकर, शैडो कैश प्रेस्टो को चार सुविधाजनक मेट्रिक्स प्रदान करता है: एच 1, एच 2, सी 1, सी 2, जहां एच 1 और सी 1 क्रमशः वास्तविक कैश हिट दर और उपयोग का प्रतिनिधित्व करते हैं, जबकि एच 2 और सी 2 कैश की सीमा हिट दर और आकार का प्रतिनिधित्व करते हैं। समय की अवधि में उपयोगकर्ता का कार्य सेट। प्रेस्टो कैश क्षमता और एप्लिकेशन प्रदर्शन के बीच संबंध को जल्दी से निर्धारित कर सकता है और उपरोक्त चार मेट्रिक्स के आधार पर बेहतर संतुलन और दक्षता के लिए रूटिंग एल्गोरिदम को अनुकूलित कर सकता है।

लिंक

• कोड मर्ज किया गया
• इस लेख का चीनी संस्करण

लेखक के बारे में

के वांग मेटा (फेसबुक) में एक सॉफ्टवेयर इंजीनियर हैं, जो प्रेस्टो टीम में कम विलंबता प्रश्नों पर ध्यान केंद्रित करते हैं।

झेन्यू सॉन्ग एक पीएच.डी. प्रिंसटन विश्वविद्यालय में कंप्यूटर विज्ञान विभाग में उम्मीदवार, सीडीएन में कैशिंग दक्षता में सुधार के लिए मशीन लर्निंग पर शोध कर रहे हैं।