अनुकूली प्रतिस्थापन कैश
अनुकूली प्रतिस्थापन कैश (एआरसी) एलआरयू (कम से कम वर्तमान में उपयोग किए गए) की तुलना में श्रेष्ठ प्रदर्शन[1] के साथ एक पृष्ठ प्रतिस्थापन एल्गोरिथ्म है। यह अधिकांश उपयोग किए जाने वाले और वर्तमान में उपयोग किए गए पृष्ठों के साथ-साथ दोनों के लिए वर्तमान में निष्कासन इतिहास का ट्रैक रखने के द्वारा पूरा किया जाता है। एल्गोरिथम[2] आईबीएम अल्माडेन रिसर्च सेंटर में विकसित किया गया था। 2006 में आईबीएम को अनुकूली प्रतिस्थापन कैश नीति के लिए पेटेंट प्रदान किया गया था।
सारांश
बेसिक एलआरयू कैश में संसाधन प्रविष्टियों की एक आदेशित सूची (कैश निर्देशिका) रखता है, जिसमें सबसे नवीनतम पहुंच के समय के आधार पर क्रमबद्ध क्रम होता है। नीचे की प्रविष्टि को निष्कासित करने के बाद सूची के शीर्ष पर नई प्रविष्टियाँ जोड़ी जाती हैं। कैशे हिट अन्य सभी प्रविष्टियों को नीचे धकेलते हुए शीर्ष पर चले जाते हैं।
एआरसी वर्तमान में और अधिकांश संदर्भित प्रविष्टियों के लिए कैश निर्देशिका को दो सूचियों, T1 और T2 में विभाजित करके मूलभूत एलआरयू रणनीति में सुधार करता है। बदले में, इनमें से प्रत्येक को घोस्ट सूची (B1 या B2) के साथ विस्तारित किया जाता है, जो दो सूचियों के नीचे से जुड़ी होती है। ये घोस्ट सूचियां वर्तमान में निकाले गए कैश प्रविष्टियों के इतिहास का ट्रैक रखकर स्कोरकार्ड के रूप में कार्य करती हैं, और एल्गोरिदम संसाधन उपयोग में नवीनतम परिवर्तन के अनुकूल होने के लिए घोस्ट हिट का उपयोग करता है। ध्यान दें कि घोस्ट सूचियों में केवल मेटाडेटा (प्रविष्टियों के लिए कुंजियाँ) होते हैं और स्वयं संसाधन डेटा नहीं होते हैं, अर्थात् किसी प्रविष्टि को घोस्ट सूची में निष्कासित कर दिया जाता है, इसके डेटा को छोड़ दिया जाता है। संयुक्त कैश निर्देशिका को चार एलआरयू सूचियों में व्यवस्थित किया गया है:
- T1, वर्तमान की कैश प्रविष्टियों के लिए।
- T2, निरंतर प्रविष्टियों के लिए, कम से कम दो बार संदर्भित।
- B1, वर्तमान में T1 कैश से निष्कासित की गई घोस्ट प्रविष्टियां, किन्तु अभी भी ट्रैक की जाती हैं।
- B2, समान घोस्ट प्रविष्टियों, किन्तु T2 से निष्कासित।
T1 और B1 को एक साथ L1 के रूप में संदर्भित किया जाता है, जो वर्तमान के एकल संदर्भों का संयुक्त इतिहास हैं। इसी प्रकार, L2 T2 और B2 का संयोजन है।
संपूर्ण कैश निर्देशिका को पंक्ति में देखा जा सकता है:
. . . [ B1 <-[ T1 <-!-> T2 ]-> B2 ] . .
[ . . . . [ . . . . . . ! . .^. . . . ] . . . . ]
[ fixed cache size (c) ]
आंतरिक '[' ']' कोष्ठक वास्तविक कैश को निरुपित करता है, जो आकार में निश्चित होने के अतिरिक्त 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".
