अनुकूली प्रतिस्थापन कैश
एडेप्टिव रिप्लेसमेंट कैश (एआरसी) एक पृष्ठ प्रतिस्थापन एल्गोरिथ्म है बेहतर प्रदर्शन[1] कैश एल्गोरिदम की तुलना में (कम से कम हाल ही में उपयोग किया गया)। यह अक्सर उपयोग किए जाने वाले और हाल ही में उपयोग किए गए पृष्ठों के साथ-साथ दोनों के लिए हाल ही में निष्कासन इतिहास का ट्रैक रखने के द्वारा पूरा किया जाता है। एल्गोरिदम विकसित किया गया था[2] आईबीएम अल्माडेन रिसर्च सेंटर में। 2006 में, IBM को अनुकूली प्रतिस्थापन कैश नीति के लिए पेटेंट दिया गया था।
सारांश
बेसिक एलआरयू कैश में संसाधन प्रविष्टियों की एक आदेशित सूची (कैश निर्देशिका) रखता है, जिसमें सबसे हालिया पहुंच के समय के आधार पर क्रमबद्ध क्रम होता है। नीचे की प्रविष्टि को बेदखल करने के बाद सूची के शीर्ष पर नई प्रविष्टियाँ जोड़ी जाती हैं। कैशे हिट अन्य सभी प्रविष्टियों को नीचे धकेलते हुए शीर्ष पर चले जाते हैं।
एआरसी हाल ही में और अक्सर संदर्भित प्रविष्टियों के लिए कैश निर्देशिका को दो सूचियों, टी 1 और टी 2 में विभाजित करके बुनियादी एलआरयू रणनीति में सुधार करता है। बदले में, इनमें से प्रत्येक को एक भूत सूची (बी1 या बी2) के साथ विस्तारित किया जाता है, जो दो सूचियों के नीचे से जुड़ी होती है। ये भूत सूचियां हाल ही में निकाले गए कैश प्रविष्टियों के इतिहास का ट्रैक रखकर स्कोरकार्ड के रूप में कार्य करती हैं, और एल्गोरिदम संसाधन उपयोग में हालिया परिवर्तन के अनुकूल होने के लिए घोस्ट हिट का उपयोग करता है। ध्यान दें कि घोस्ट सूचियों में केवल मेटाडेटा (प्रविष्टियों के लिए कुंजियाँ) होते हैं और स्वयं संसाधन डेटा नहीं होते हैं, यानी किसी प्रविष्टि को घोस्ट सूची में बेदखल कर दिया जाता है, इसके डेटा को छोड़ दिया जाता है। संयुक्त कैश निर्देशिका को चार LRU सूचियों में व्यवस्थित किया गया है:
- T1, हाल की कैश प्रविष्टियों के लिए।
- T2, लगातार प्रविष्टियों के लिए, कम से कम दो बार संदर्भित।
- बी 1, हाल ही में टी 1 कैश से बेदखल की गई भूत प्रविष्टियां, लेकिन अभी भी ट्रैक की जाती हैं।
- बी2, समान घोस्ट एंट्री, लेकिन टी2 से बेदखल।
T1 और B1 को एक साथ L1 के रूप में संदर्भित किया जाता है, हाल ही के एकल संदर्भों का एक संयुक्त इतिहास। इसी तरह, L2 T2 और B2 का संयोजन है।
संपूर्ण कैश निर्देशिका को एक पंक्ति में देखा जा सकता है:
. . . '[' B1 <-'[' T1 <-'!'-> T2 ']'-> B2 ']' । .
'['। . . . '['। . . . . . '!' . '^'। . . . ']'। . . . ']'
'[' निश्चित कैश आकार (सी) ']'
आंतरिक '[' ']' कोष्ठक वास्तविक कैश को इंगित करता है, जो हालांकि आकार में तय है, B1 और B2 इतिहास में स्वतंत्र रूप से स्थानांतरित हो सकता है।
L1 अब दाएँ से बाएँ प्रदर्शित होता है, शीर्ष से प्रारंभ होकर, '!' द्वारा दर्शाया जाता है मार्कर। '^' T1 के लिए लक्षित आकार को इंगित करता है, और वास्तविक आकार के बराबर, उससे छोटा या बड़ा हो सकता है (जैसा कि '!' द्वारा इंगित किया गया है)।
- नई प्रविष्टियाँ '!' के बाईं ओर T1 में प्रवेश करती हैं, और धीरे-धीरे बाईं ओर धकेल दी जाती हैं, अंततः T1 से B1 में निकाल दी जाती हैं, और अंत में पूरी तरह से बाहर हो जाती हैं।
- L1 में कोई भी प्रविष्टि जो एक बार फिर से संदर्भित हो जाती है, उसे एक और मौका मिलता है, और L2 में प्रवेश करती है, ठीक केंद्रीय '!' मार्कर। वहां से, इसे फिर से बाहर की ओर धकेला जाता है, T2 से B2 में। L2 में प्रविष्टियां जो एक और हिट प्राप्त करती हैं, इसे अनिश्चित काल तक दोहरा सकती हैं, जब तक कि वे अंत में B2 के दूर दाईं ओर से बाहर नहीं निकल जातीं।
प्रतिस्थापन
कैश (T1, T2) में प्रवेश करने वाली प्रविष्टियाँ (पुनः-) कारण होंगी ! लक्ष्य मार्कर ^ की ओर बढ़ने के लिए। यदि संचय में कोई रिक्त स्थान मौजूद नहीं है, तो यह चिह्नक यह भी निर्धारित करता है कि क्या T1 या T2 में से कोई एक प्रविष्टि निकालेगा।
- B1 में हिट करने से T1 का आकार बढ़ जाएगा, ^ को दाईं ओर धकेल दिया जाएगा। T2 में अंतिम प्रविष्टि B2 में बेदखल है।
- B2 में हिट ^ को वापस बाईं ओर धकेलते हुए T1 को सिकोड़ देगा। T1 में अंतिम प्रविष्टि अब B1 में बेदखल कर दी गई है।
- एक कैश मिस ^ को प्रभावित नहीं करेगा, लेकिन ! सीमा ^ के करीब जाएगी।
परिनियोजन
ARC वर्तमान में IBM के DS6000/IBM DS8000 भंडारण नियंत्रकों में परिनियोजित है।
सन माइक्रोसिस्टम्स का स्केलेबल फ़ाइल सिस्टम ZFS एक संस्करण का उपयोग करता है[3] वर्चुअल मेमोरी में पारंपरिक सोलारिस (ऑपरेटिंग सिस्टम) फाइल सिस्टम पेज कैश के विकल्प के रूप में एआरसी का। इसे लॉक किए गए पृष्ठों की अनुमति देने के लिए संशोधित किया गया है जो वर्तमान में उपयोग में हैं और खाली नहीं किए जा सकते हैं।
PostgreSQL ने थोड़े समय के लिए अपने बफर मैनेजर में ARC का उपयोग किया (संस्करण 8.0.0), लेकिन जल्दी से इसे दूसरे एल्गोरिथम से बदल दिया, एआरसी पर आईबीएम पेटेंट पर चिंताओं का हवाला देते हुए।[4] VMware का vSAN (पूर्व में वर्चुअल SAN) VMware द्वारा विकसित एक हाइपर-कन्वर्ज्ड, सॉफ़्टवेयर-डिफ़ाइंड स्टोरेज (SDS) उत्पाद है। यह अपने कैशिंग एल्गोरिदम में एआरसी के एक प्रकार का उपयोग करता है। [5] OpenZFS रीड कैश के रूप में बहु-स्तरीय कैश में ARC और L2ARC का उपयोग करने का समर्थन करता है। OpenZFS में, डिस्क रीड अक्सर ARC का उपयोग करके RAM में प्रथम स्तर के डिस्क कैश को हिट करता है। यदि दूसरे स्तर के डिस्क कैश को स्टोर करने के लिए एक SSD स्थापित किया गया है, तो इसे L2ARC कहा जाता है। L2ARC समान ARC एल्गोरिद्म का उपयोग करता है, लेकिन कैश्ड डेटा को RAM में संग्रहीत करने के बजाय, L2ARC कैश्ड डेटा को तेज़ SSD में संग्रहीत करता है।[6][7][8][9][10][11]
यह भी देखें
संदर्भ
- ↑ One Up on LRU, Usenix :login; August 2003
- ↑ Nimrod Megiddo and Dharmendra Modha, 2010-03-09 archive of the ARC home page, with pointers to several articles
- ↑ comments in Solaris ZFS arc.c source file explains differences with original work
- ↑ Article in Postgresql General Bits, "The Saga of the ARC Algorithm and Patent", published 6 February 2005
- ↑ Reference document, "VMware vSAN Caching Algorithms"[permanent dead link]
- ↑ "ZFS Caching".
- ↑ "ZFS Primer".
- ↑ Jim Salter. "Persistent L2ARC might be coming to ZFS on Linux". 2020.
- ↑ "Cache: L2ARC accesses".
- ↑ Brendan Gregg. "ZFS L2ARC".
- ↑ Ranvir Singh. "Adaptive Replacement Cache (ARC) and L2ARC".
