LRU Cache — यह क्या है, निष्कासन एल्गोरिदम और यह कैसे काम करता है

LRU Cache क्या है?

LRU Cache (Least Recently Used Cache) एक निश्चित आकार की डेटा संरचना है जो सीमित संख्या में तत्वों को संग्रहीत करती है और स्वचालित रूप से उन तत्वों को हटा देती है जिन्हें सबसे कम एक्सेस किया गया है। जब कोई एप्लिकेशन किसी तत्व का अनुरोध करता है, तो वह कैश के “ताज़ा” भाग में चला जाता है, जबकि लंबे समय से अप्रयुक्त तत्व अंत की ओर खिसक जाते हैं और सीमा पहुँचने पर हटा दिए जाते हैं।

नाम “Least Recently Used” निष्कासन नीति का वर्णन करता है: वह तत्व हटा दिया जाता है जो सभी संग्रहीत तत्वों में से सबसे लंबे समय से उपयोग नहीं किया गया है। यह संदर्भ की स्थानीयता (locality of reference) की धारणा पर आधारित है — हाल ही में अनुरोधित डेटा के फिर से आवश्यक होने की अत्यधिक संभावना होती है। यही कारण है कि LRU को अधिकांश अनुप्रयोगों के लिए सबसे प्रभावी कैशिंग रणनीतियों में से एक माना जाता है।

शास्त्रीय LRU Cache कार्यान्वयन के लिए दो डेटा संरचनाओं की आवश्यकता होती है: कुंजी द्वारा किसी भी तत्व तक O(1) पहुँच के लिए हैश तालिका और उपयोग क्रम को ट्रैक करने के लिए दोगुनी लिंक्ड सूची। हैश तालिका सूची नोड्स के संदर्भ संग्रहीत करती है, और सूची नवीनतम तत्व (सिर) से सबसे पुराने (पूंछ) तक क्रम बनाए रखती है।

LRU Cache की मूल संक्रियाएँ

get(key) संक्रिया जाँचती है कि कुंजी हैश तालिका में मौजूद है या नहीं। यदि तत्व मिल जाता है, तो वह सूची के सिर पर चला जाता है (सबसे नया बन जाता है) और उसका मान लौटाया जाता है। यदि नहीं मिलता है, तो null लौटाया जाता है या अपवाद फेंका जाता है। put(key, value) संक्रिया एक नया तत्व सम्मिलित करती है: यदि कुंजी पहले से मौजूद है, तो मान अद्यतन होता है और तत्व सिर पर चला जाता है। यदि कैश भरा हुआ है, तो सम्मिलन से पहले पूंछ का तत्व हटा दिया जाता है। सभी संक्रियाएँ स्थिर समय O(1) में निष्पादित होती हैं।

LRU Cache कैसे काम करता है

LRU Cache एल्गोरिदम दो सिद्धांतों पर आधारित है: समय-क्रमित पहुँच गणना और ओवरफ़्लो पर निष्कासन तंत्र। प्रत्येक तत्व दोगुनी लिंक्ड सूची नोड में संग्रहीत होता है, और इन नोड्स के संकेत हैश तालिका में रखे जाते हैं। प्रत्येक पहुँच पर, तत्व अपनी वर्तमान स्थिति से अलग हो जाता है और सूची के सिर पर सम्मिलित हो जाता है।

जब कैश का आकार अपने अधिकतम मान (maxSize) तक पहुँचता है और एक नया तत्व सम्मिलित करने का अनुरोध आता है, तो एल्गोरिदम दोगुनी लिंक्ड सूची के पूंछ तत्व को हटा देता है — यह सबसे कम हाल ही में उपयोग किया गया तत्व है। हटाने के बाद, नए तत्व के लिए स्थान खाली हो जाता है, जो सूची के सिर पर सम्मिलित होता है। हैश तालिका तदनुसार अद्यतन होती है: पुरानी कुंजी हटा दी जाती है, नई जोड़ दी जाती है।

LRU की एक विशेषता चक्रीय पुनरावृत्ति वाले पहुँच पैटर्न के प्रति इसकी संवेदनशीलता है। यदि एप्लिकेशन समय-समय पर कैश आकार से बड़े डेटा सेट तक पहुँचता है, तो LRU thrashing से पीड़ित हो सकता है — बार-बार तत्व प्रतिस्थापन जहाँ प्रत्येक नया अनुरोध पिछले को हटा देता है। ऐसे परिदृश्यों में, LFU (Least Frequently Used) या अनुकूली एल्गोरिदम अधिक प्रभावी हो सकते हैं।

कैश आकार और मीट्रिक्स

LRU Cache आकार चुनना मेमोरी खपत और हिट-अनुपात (सफल पहुँच का प्रतिशत) के बीच एक समझौता है। मोबाइल अनुप्रयोगों के लिए विशिष्ट मान: छवि कैश के लिए उपलब्ध मेमोरी का 10–20% और नेटवर्क प्रतिक्रिया कैश के लिए 50–200 प्रविष्टियाँ। हिट-अनुपात 80–95% अच्छा माना जाता है, जहाँ कैश मेमोरी लागत को उचित ठहराता है। निगरानी के लिए, hitCount और missCount काउंटर का उपयोग किया जाता है, जो Android में LruCache कार्यान्वयन में उपलब्ध हैं।

LRU Cache का कार्यान्वयन: HashMap + Doubly Linked List

विहित LRU Cache कार्यान्वयन हैश तालिका और दोगुनी लिंक्ड सूची के संयोजन का उपयोग करता है। हैश तालिका कुंजी द्वारा किसी भी नोड तक O(1) पहुँच प्रदान करती है, जबकि दोगुनी लिंक्ड सूची नोड को सिर पर ले जाने और पूंछ से हटाने की O(1) अनुमति देती है। महत्वपूर्ण रूप से, सूची दोगुनी लिंक्ड है: यह सभी तत्वों पर पुनरावृत्ति किए बिना सूची के बीच से नोड को अलग करने की अनुमति देता है।

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

कार्यान्वयन में, प्रत्येक नोड (Node) एक मान और पिछले तथा अगले नोड्स के संदर्भ संग्रहीत करता है। सेंटिनल नोड्स head और tail सीमांत मामलों को सरल बनाते हैं — सम्मिलन और हटाने पर null जाँचने की आवश्यकता नहीं होती। get विधि मिले हुए नोड को सिर पर ले जाती है, और put ओवरफ़्लो पर पूंछ तत्व को हटा देती है। एक अलग विधि removeKeyByValue नोड संदर्भ द्वारा हैश तालिका में कुंजी ढूँढती है और उसे हटा देती है।

Android में अंतर्निहित LruCache कार्यान्वयन

Android SDK android.util पैकेज में एक तैयार LruCache वर्ग प्रदान करता है, जो access-order मोड में LinkedHashMap का उपयोग करके LRU एल्गोरिदम को कार्यान्वित करता है। वर्ग thread-safe है, hit/miss गणना का समर्थन करता है, और तत्व निष्कासन पर संसाधन सफाई के लिए entryRemoved कॉलबैक प्रदान करता है। कैश का आकार मनमानी इकाइयों (बाइट, तत्वों की संख्या) में सेट किया जाता है — बस sizeOf विधि को ओवरराइड करें।

LRU Cache बनाम FIFO और LIFO

तीनों एल्गोरिदम — LRU, FIFO और LIFO — एक ही समस्या हल करते हैं: ओवरफ़्लो पर तत्वों को हटाकर मेमोरी खपत को सीमित करना। हालाँकि, वे शिकार चुनने के लिए मौलिक रूप से भिन्न मानदंडों का उपयोग करते हैं, जो विभिन्न परिदृश्यों में उनकी प्रभावशीलता निर्धारित करता है।

FIFO सम्मिलन समय के अनुसार सबसे पुराने तत्व को हटाता है, भले ही उस तक कितनी बार पहुँचा गया हो। यह अप्रभावी हो सकता है यदि कोई पुराना तत्व अभी भी प्रासंगिक है। LRU पहुँच पैटर्न पर विचार करके इस कमी से बचता है। LIFO सबसे हाल ही में जोड़े गए तत्व को हटाता है — पूर्ववत परिदृश्यों के लिए उपयोगी, लेकिन कैशिंग के लिए अनुपयुक्त, क्योंकि नया डेटा अक्सर पुराने से अधिक आवश्यक होता है। LRU अधिकांश अनुप्रयोगों के लिए कार्यान्वयन जटिलता और हिट-अनुपात के बीच इष्टतम संतुलन माना जाता है।

LRU Cache कोड उदाहरण

आइए डाउनलोड की गई छवियों को कैश करने के लिए Android SDK से अंतर्निहित LruCache वर्ग के उपयोग पर विचार करें। उदाहरण एप्लिकेशन की उपलब्ध मेमोरी के 1/8 पर कैश आरंभीकरण दिखाता है, जो छवि कैशिंग के लिए Google की मानक अनुशंसा है।

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

sizeOf विधि तत्व का आकार उन्हीं इकाइयों में लौटाती है जिनमें cacheSize निर्दिष्ट है। यहाँ किलोबाइट में Bitmap आकार का उपयोग किया गया है (rowBytes × height / 1024)। जब सभी तत्वों के sizeOf का योग cacheSize से अधिक हो जाता है, तो LruCache स्वचालित रूप से सबसे कम हाल ही में उपयोग किए गए Bitmaps को हटा देता है। entryRemoved कॉलबैक का उपयोग bitmap.recycle() कॉल करने के लिए किया जा सकता है — निष्कासन से पहले मेमोरी मुक्त करना।

Swift में LRU Cache कार्यान्वयन

iOS में कोई अंतर्निहित LRU Cache वर्ग नहीं है, लेकिन इसे NSCache (जो समान लेकिन अप्रलेखित निष्कासन नीति का उपयोग करता है) या Dictionary + Doubly Linked List पर आधारित कस्टम कार्यान्वयन के माध्यम से आसानी से कार्यान्वित किया जा सकता है, जैसा कि नीचे दिखाया गया है।

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

इस Swift कार्यान्वयन में, Node value, next और prev फील्ड वाला एक आंतरिक वर्ग है। moveToHead विधि नोड को उसकी वर्तमान स्थिति से अलग करती है और सूची के सिर पर सम्मिलित करती है। ओवरफ़्लो होने पर, पूंछ — सबसे कम हाल ही में उपयोग किया गया तत्व — हटा दिया जाता है। उत्पादन के लिए, NSLock या DispatchQueue क्यू के माध्यम से थ्रेड सुरक्षा जोड़ने की अनुशंसा की जाती है।