CART कैशिंग एल्गोरिथ्म का बहु-थ्रेडेड कार्यान्वयन

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

मैंने बाहरी अनुप्रयोगों का उपयोग करने के विचार को अस्वीकार कर दिया जैसे कि तुरंत ठीक किया गया - यह ग्राफ़ के किनारे पर प्रत्येक संक्रमण में एक अपरिहार्य अतिरिक्त अंतराल का परिचय देगा। आवेदन के भीतर कार्यान्वयन के बारे में एक सवाल था।

प्रलेखन ने मदद की है कि मेरे टीबीबी पुस्तकालय में एक LRU कैश कार्यान्वयन है। दुर्भाग्य से, उस समय यह कार्यान्वयन एक पूर्वावलोकन स्थिति में था (जहां यह अभी भी है)।

मेरे पास एक विकल्प था - अपर्याप्त परीक्षण किए गए कार्यान्वयन पर भरोसा करना, जहां किसी भी बग को ठीक करना एक महान साहसिक कार्य होगा, या अपना खुद का लिखना होगा। इसके अलावा, कैशिंग एल्गोरिदम के उपलब्ध प्रकाशनों पर एक त्वरित नज़र ने मुझे यह सोचने के लिए प्रेरित किया कि शायद LRU सबसे कुशल योजना नहीं है। भारी भरकम अनुप्रयोगों के लिए, यहां तक ​​कि कुछ प्रतिशत अतिरिक्त दक्षता ही रोटी है। मैंने जो कुछ भी पाया उससे गुजरने के बाद, मैं कार्ट एल्गोरिथ्म पर बस गया।

यह योजना कई उपयोगी लाभों को जोड़ती है:

1. स्कैन सुरक्षा। यदि आप एक बार पूरे डेटाबेस से गुजरते हैं, तो यह कैश की प्रभावशीलता को प्रभावित नहीं करेगा। उदाहरण के लिए, विश्लेषणात्मक उपकरणों का उपयोग करते समय ऐसी स्थिति उत्पन्न हो सकती है।
2. दोहरे उपचार के खिलाफ संरक्षण। अक्सर ऐसा होता है कि अनुरोधों के बीच समान अंतराल के साथ एक ही डेटाबेस आइटम का दो बार अनुरोध किया जाता है, और फिर इसे एक्सेस नहीं किया जाता है। इससे सर्किट की दक्षता में महत्वपूर्ण कमी हो सकती है, जिसमें इस तरह के व्यवहार के खिलाफ सुरक्षा नहीं होती है, क्योंकि किसी भी तत्व का अनुरोध सर्किट में प्राथमिकता प्राप्त करेगा।
3. कैश में प्रत्येक हिट को आंतरिक संरचनाओं के किसी भी महत्वपूर्ण संचालन या रखरखाव की आवश्यकता नहीं है (जो LRU का एक महत्वपूर्ण दोष है)। यह बहु-थ्रेडेड कार्यान्वयन के लिए बहुत महत्वपूर्ण है, क्योंकि इसमें प्रत्येक उपचार के साथ अवरोध की आवश्यकता नहीं होती है।

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

सबसे पहले, हम तीन कैश आकार (100, 500 और 1000) के लिए संख्याओं के एक यादृच्छिक रूप से उत्पन्न क्रम (0 ... 10000) पर दोनों योजनाओं की प्रभावशीलता का परीक्षण करते हैं:

कम बेहतर है।
रैंडम नंबर, कैश साइज 100
कार्ट परिणाम: 0.99, 994950/1005000 छूटे
LRU परिणाम: 0.990057, 995007/1005000 से चूक गए
यादृच्छिक संख्या, कैश आकार 500
कार्ट परिणाम: 0.949862, 954611/1005000 छूटे
LRU परिणाम: 0.95016, 954911/1005000 से चूक गए
यादृच्छिक संख्या, कैश आकार 1000
कार्ट परिणाम: 0.90002, 904520/1005000 याद किया
LRU परिणाम: 0.900309, 904811/1005000 से चूक गए

CART दक्षता में LRU से थोड़ा आगे है, लेकिन, स्पष्ट रूप से, पूरी तरह से यादृच्छिक अभिगम एक अच्छी परीक्षा नहीं है। इसके अलावा, इस प्रकार की पहुंच के साथ एक वास्तविक एप्लिकेशन में, किसी भी कैश की प्रभावशीलता कम होगी।

इसलिए, मैंने एक व्यावहारिक अनुप्रयोग की तरह दूसरा परीक्षण किया। यहां संख्याओं को 6 टोकरियों से लिया गया है, जिनमें से प्रत्येक में तत्वों की बढ़ती संख्या है, जो किसी विशेष संख्या को चुनने की संभावना को कम करता है। इस प्रकार, कुल संख्या में 0 से 150 तक की संख्या 5000 से 10000 तक की संख्या के रूप में चयनित होने की समान संभावना है। यह रणनीति एक नमूना पैटर्न के समान है, उदाहरण के लिए, उपयोगकर्ता डेटाबेस से, जहां अक्सर आने वाले उपयोगकर्ता अक्सर डेटाबेस को खींचते हैं।

डिब्बे ड्रा, कैश का आकार 100
कार्ट परिणाम: 0.920258, 924859/1005000 छूटे
LRU परिणाम: 0.965795, 970624/1005000 याद किया
डिब्बे ड्रा, कैश का आकार 500
कार्ट परिणाम: 0.721484, 725091/1005000 छूटे
LRU परिणाम: 0.84106, 845265/1005000 से चूक गया
डिब्बे ड्रा, कैश आकार 1000
कार्ट परिणाम: 0.581132, 584038/1005000 छूटे
LRU परिणाम: 0.71412, 717691/1005000 से चूक गया

इस मामले में, CART पहले से ही LRU की तुलना में काफी बेहतर परिणाम दिखा रहा है। जो, वास्तव में, हम हासिल करना चाहते थे। रुचि रखने वाले सभी के लिए, मैं एक उदाहरण डाउनलोड करने और इसे स्वयं लॉन्च करने का सुझाव देता हूं।

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

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

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

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