FIFO Cache — মূল ধারণা, কিউ অ্যালগরিদম এবং এটি কীভাবে কাজ করে

FIFO Cache কী?

FIFO Cache (First In First Out Cache) একটি নির্দিষ্ট আকারের ক্যাশ যা উপাদান পরিচালনার জন্য কিউ ব্যবহার করে। প্রথম যোগ করা উপাদানটি কিউয়ের মাথায় রাখা হয় এবং ওভারফ্লো হলে প্রথমে সরানো হবে। নতুন উপাদান সর্বদা লেজে যোগ করা হয়, নিশ্চিত করে যে অপসারণের ক্রম যোগ করার ক্রমের সাথে মেলে।

LRU-এর বিপরীতে, যা প্রতিটি অ্যাক্সেসে উপাদান পুনর্বিন্যাস করে, FIFO get অনুরোধে বিদ্যমান উপাদানের অবস্থান পরিবর্তন করে না। এটি অ্যালগরিদমকে সম্পূর্ণ নিয়ন্ত্রণাত্মক করে তোলে: যোগ করার ক্রম জানলে, পরবর্তী কোন উপাদানটি সরানো হবে তা সঠিকভাবে ভবিষ্যদ্বাণী করা যায়। এই পূর্বানুমেয়তা রিয়েল-টাইম সিস্টেমের জন্য গুরুত্বপূর্ণ যেখানে ডেটা আগমনের ক্রমে প্রক্রিয়াকরণ করা আবশ্যক।

FIFO Cache-এর বাস্তবায়ন বিভিন্ন ডেটা স্ট্রাকচারে নির্মিত হতে পারে: সর্বোচ্চ কর্মক্ষমতার জন্য সার্কুলার বাফার, নমনীয়তার জন্য লিঙ্কড লিস্ট, বা অন্তর্নির্মিত কিউ ছাড়া ভাষার জন্য two stacks (টু-স্ট্যাক কিউ)। সার্কুলার বাফার সর্বোত্তম ক্যাশ লোকালিটি এবং ন্যূনতম ওভারহেড প্রদান করে, কিন্তু 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() সবচেয়ে পুরনো উপাদান (প্রথম যোগ করা) সরিয়ে ফেলে। এই পদ্ধতিতে মেমোরির পূর্ব-বণ্টনের প্রয়োজন নেই কিন্তু ঘন ঘন স্ট্যাক উল্টানোর সময় আবর্জনা সংগ্রহে অতিরিক্ত চাপ সৃষ্টি করতে পারে। সীমিত মেমোরি সহ মোবাইল অ্যাপের জন্য, সার্কুলার বাফার বেশি পছন্দনীয় থাকে।