FIFO Cache — मुख्य अवधारणाएँ, कतार एल्गोरिदम और यह कैसे काम करता है

FIFO Cache क्या है?

FIFO Cache (First In First Out Cache) एक निश्चित आकार का कैश है जो तत्वों को प्रबंधित करने के लिए कतार का उपयोग करता है। पहला जोड़ा गया तत्व कतार के सिर पर रखा जाता है और अतिप्रवाह होने पर सबसे पहले हटाया जाएगा। नए तत्व हमेशा पूंछ में जोड़े जाते हैं, यह सुनिश्चित करते हुए कि हटाने का क्रम जोड़ने के क्रम से मेल खाता है।

LRU के विपरीत, जो प्रत्येक एक्सेस पर तत्वों को पुनर्क्रमित करता है, FIFO get अनुरोधों पर मौजूदा तत्वों की स्थिति नहीं बदलता है। यह एल्गोरिदम को पूरी तरह से निर्धारणात्मक बनाता है: जोड़ने के क्रम को जानकर, कोई सटीक भविष्यवाणी कर सकता है कि आगे कौन सा तत्व हटाया जाएगा। यह पूर्वानुमेयता रियल-टाइम सिस्टम के लिए महत्वपूर्ण है जहाँ डेटा को आगमन के क्रम में संसाधित किया जाना चाहिए।

FIFO Cache का कार्यान्वयन कई डेटा संरचनाओं पर बनाया जा सकता है: अधिकतम प्रदर्शन के लिए सर्कुलर बफर, लचीलेपन के लिए लिंक्ड लिस्ट, या बिना अंतर्निहित कतार वाली भाषाओं के लिए दो स्टैक (टू-स्टैक कतार)। सर्कुलर बफर सबसे अच्छी कैश लोकैलिटी और न्यूनतम ओवरहेड प्रदान करता है, लेकिन maxSize के लिए मेमोरी के पूर्व-आवंटन की आवश्यकता होती है।

FIFO Cache के मूल संचालन

enqueue(value) संचालन कतार की पूंछ में एक तत्व जोड़ता है। यदि आकार maxSize तक पहुँचता है, तो जोड़ने से पहले सिर का तत्व हटा दिया जाता है। dequeue() संचालन सिर के तत्व को हटाता है और लौटाता है — सबसे पुराने तत्व के强制 निष्कर्षण के लिए। peek() संचालन बिना हटाए सिर का तत्व लौटाता है — कतार को संशोधित किए बिना सबसे पुराना तत्व देखने के लिए।

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

FIFO एल्गोरिदम सामान्य कतार के व्यवहार की नकल करता है: पहले आने वाले को पहले सेवा दी जाती है। कैशिंग के संदर्भ में, इसका मतलब है कि जो तत्व कैश में सबसे लंबे समय तक रहा है, उसे स्थान की आवश्यकता होने पर हटा दिया जाएगा — भले ही वह कितना भी लोकप्रिय क्यों न हो। FIFO की हटाने की नीति एक्सेस आवृत्ति को अनदेखा करती है, जो एल्गोरिदम की ताकत और कमजोरी दोनों है।

जब सर्कुलर बफर के माध्यम से कार्यान्वित किया जाता है, तो दो पॉइंटर्स का उपयोग किया जाता है: head (कतार के सिर का सूचकांक) और tail (पूंछ का सूचकांक)। enqueue पर, तत्व tail सूचकांक पर लिखा जाता है, और tail बढ़ा दिया जाता है। यदि tail बफर आकार तक पहुँचता है, तो यह ऐरे की शुरुआत में लपेट जाता है। यदि tail, head को पकड़ लेता है, तो कतार भर गई है, और head स्थानांतरित हो जाता है (हटाना)। सर्कुलर बफर को गतिशील मेमोरी आवंटन की आवश्यकता नहीं होती है और यह विखंडन से बचाता है।

FIFO Cache विशिष्ट कार्यभार के लिए 40% से 60% तक hit-ratio प्रदर्शित करता है, जो LIFO से अधिक है लेकिन LRU से कम है। हालाँकि, उन परिदृश्यों के लिए जहाँ डेटा एक्सेस एकसमान है और कोई हॉट स्पॉट नहीं हैं, FIFO काफी कम कार्यान्वयन जटिलता के साथ LRU के तुलनीय परिणाम दिखा सकता है। मेमोरी का कुशलतापूर्वक उपयोग किया जाता है: तत्व पुनर्क्रमण के लिए अतिरिक्त पॉइंटर्स की आवश्यकता नहीं होती है।

कैश प्रदूषण की समस्या

FIFO का मुख्य दोष कैश प्रदूषण के प्रति संवेदनशीलता है। यदि कैश में बड़ी मात्रा में ऐसा डेटा जोड़ा जाता है जिसकी फिर कभी आवश्यकता नहीं होगी, तो वह धीरे-धीरे सभी उपयोगी तत्वों को हटा देगा, और hit-ratio तेजी से गिर जाएगा। LRU इस समस्या को आंशिक रूप से हल करता है क्योंकि बार-बार उपयोग किए जाने वाले तत्व सिर पर ले जाकर लगातार ताज़ा किए जाते हैं, जबकि एक बार उपयोग किया गया डेटा तेजी से हटा दिया जाता है। FIFO में, एक बार उपयोग किया गया डेटा तब तक कैश में रहता है जब तक कि वह कतार क्रम द्वारा स्वाभाविक रूप से हटा नहीं दिया जाता।

FIFO, LRU और LIFO की तुलना

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

FIFO उन परिदृश्यों के लिए आदर्श है जहाँ प्रसंस्करण क्रम आगमन क्रम से मेल खाना चाहिए: डेटा बफरिंग, लॉगिंग, ईवेंट प्रसंस्करण। LRU असमान एक्सेस (उपयोगकर्ता डेटा) वाले कैशिंग के लिए बेहतर है। LIFO केवल स्टैक और पूर्ववत करने के लिए लागू है। अधिकांश मोबाइल ऐप्स के लिए, LRU डिफ़ॉल्ट विकल्प बना हुआ है, लेकिन सख्त मेमोरी बाधाओं या पूर्वानुमेयता आवश्यकताओं के तहत FIFO बेहतर हो सकता है।

FIFO Cache कहाँ उपयोग किया जाता है

FIFO Cache उन परिदृश्यों में उपयोग पाता है जहाँ हटाने की पूर्वानुमेयता या डेटा प्रसंस्करण क्रम मायने रखता है। आइए मुख्य उपयोग मामलों की जाँच करें।

स्ट्रीमिंग डेटा बफरिंग

ऑडियो और वीडियो चलाते समय, डेटा एक सतत धारा में आता है और अस्थायी रूप से बफर में संग्रहीत होता है। FIFO Cache सुनिश्चित करता है कि प्राप्त पहले खंड डिकोडिंग के लिए पहले भेजे जाएँ — यह बिना देरी के सुचारू प्लेबैक की गारंटी देता है। बफर आकार स्ट्रीम बिटरेट और स्वीकार्य देरी के आधार पर चुना जाता है: ऑडियो के लिए आमतौर पर 2–5 सेकंड, वीडियो के लिए 10–30 सेकंड। FIFO ऐसे परिदृश्यों के लिए आदर्श है क्योंकि डेटा पुनर्क्रमण (जैसा कि LRU में) का कोई अर्थ नहीं है।

नेटवर्क अनुरोध कतारें

एक साथ नेटवर्क अनुरोधों की संख्या को सीमित करते समय, FIFO Cache का उपयोग लंबित अनुरोधों को संग्रहीत करने के लिए किया जा सकता है। पहला जोड़ा गया अनुरोध पहले निष्पादित किया जाएगा, जो ऐप के विभिन्न घटकों के बीच नेटवर्क संसाधनों का निष्पक्ष वितरण सुनिश्चित करता है। यह दृष्टिकोण OkHttp Dispatcher और कनेक्शन पूल प्रबंधन के लिए समान पुस्तकालयों में उपयोग किया जाता है।

HTTP प्रतिक्रिया कैशिंग

मोबाइल उपकरणों पर सरल HTTP प्रतिक्रिया कैश अक्सर FIFO का उपयोग करते हैं। अनुरोधों की प्रतिक्रियाएँ आगमन के क्रम में संग्रहीत की जाती हैं, और जब सीमा पहुँच जाती है, तो सबसे पुरानी हटा दी जाती हैं। हालाँकि LRU उपयोगकर्ता परिदृश्यों के लिए बेहतर hit-ratio देगा, FIFO कार्यान्वित करने में सरल है और प्रत्येक प्रतिक्रिया के लिए अंतिम एक्सेस समय संग्रहीत करने की आवश्यकता नहीं है। एकसमान लोड वाले API के लिए, FIFO और LRU के बीच hit-ratio में अंतर न्यूनतम है।

स्पर्श ईवेंट प्रसंस्करण

मोबाइल ऐप्स में, स्पर्श ईवेंट जेस्चर प्रसंस्करण से पहले FIFO कतार में बफर किए जाते हैं। प्रत्येक ईवेंट को उसके घटित होने के क्रम में संसाधित किया जाना चाहिए, अन्यथा जेस्चर गलत तरीके से पहचाना जाएगा। आकार सीमा वाला FIFO Cache तेज़ स्वाइप के दौरान बफर अतिप्रवाह को रोकता है, यदि ऐप प्रसंस्करण नहीं कर पाता तो सबसे पुराने ईवेंट को त्याग देता है।

FIFO Cache कोड उदाहरण

आइए सर्कुलर बफर का उपयोग करके Kotlin में FIFO Cache के कार्यान्वयन को देखें — मोबाइल उपकरणों के लिए सबसे प्रभावी दृष्टिकोण।

class FifoCache<V>(
    private val maxSize: Int
) {
    private val buffer = arrayOfNulls<V>(maxSize)
    private var head = 0
    private var tail = 0
    private var size = 0

    fun enqueue(value: V) {
        if (size == maxSize) {
            // सबसे पुराना तत्व हटाएँ
            buffer[head] = null
            head = (head + 1) % maxSize
            size--
        }
        buffer[tail] = value
        tail = (tail + 1) % maxSize
        size++
    }

    fun dequeue(): V? {
        if (size == 0) return null
        val result = buffer[head]
        buffer[head] = null
        head = (head + 1) % maxSize
        size--
        return result
    }

    fun peek(): V? {
        return buffer[head]
    }
}

सर्कुलर बफर head और tail सूचकांकों का उपयोग करता है जो maxSize मॉड्यूलो द्वारा चक्रीय रूप से बढ़ते हैं। जब size == maxSize होता है, enqueue पहले head पर तत्व (सबसे पुराना) हटाता है, head को स्थानांतरित करता है, और फिर tail पर नया तत्व लिखता है। मॉड्यूलर अंकगणित स्वचालित रूप से पॉइंटर्स को ऐरे की शुरुआत में लपेटता है, मैन्युअल डेटा कॉपीिंग को समाप्त करता है।

दो स्टैक के माध्यम से Swift कार्यान्वयन

Swift में, एक सुविधाजनक विकल्प दो स्टैक (टू-स्टैक कतार) पर आधारित FIFO कतार है। सभी enqueue संचालन पहले स्टैक (push) में जाते हैं, और dequeue के दौरान, तत्व उल्टे क्रम में दूसरे स्टैक में स्थानांतरित हो जाते हैं — जिससे dequeue औसतन O(1) हो जाता है।

struct FifoCache<Value> {
    private let maxSize: Int
    private var inStack = [Value]()
    private var outStack = [Value]()

    mutating func enqueue(value: Value) {
        if inStack.count + outStack.count >= maxSize {
            if outStack.isEmpty {
                outStack = inStack.reversed()
                inStack.removeAll()
            }
            outStack.removeLast()
        }
        inStack.append(value)
    }

    mutating func dequeue() -> Value? {
        if outStack.isEmpty {
            outStack = inStack.reversed()
            inStack.removeAll()
        }
        return outStack.popLast()
    }
}

दो स्टैक enqueue और dequeue के लिए परिशोधित O(1) जटिलता प्रदान करते हैं। हटाने के दौरान outStack.removeLast() सबसे पुराने तत्व (पहले जोड़ा गया) को हटाता है। यह दृष्टिकोण मेमोरी के पूर्व-आवंटन की आवश्यकता नहीं है, लेकिन बार-बार स्टैक उलटने के दौरान कचरा संग्रहण पर अतिरिक्त भार पैदा कर सकता है। सीमित मेमोरी वाले मोबाइल ऐप्स के लिए, सर्कुलर बफर अधिक बेहतर बना हुआ है।