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 + দ্বি-লিঙ্কযুক্ত তালিকার উপর ভিত্তি করে কাস্টম বাস্তবায়নের মাধ্যমে এটি সহজেই বাস্তবায়ন করা যায়, যেমন নীচে দেখানো হয়েছে।

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 ক্যুর মাধ্যমে থ্রেড নিরাপত্তা যোগ করার সুপারিশ করা হয়।