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) میں نوڈ کو سر پر منتقل کرنے اور دم سے ہٹانے کی اجازت دیتی ہے۔ اہم بات یہ ہے کہ فہرست دوہری منسلک ہے: یہ تمام عناصر پر iterate کیے بغیر فہرست کے بیچ سے نوڈ کو الگ کرنے کی اجازت دیتی ہے۔

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 متعین کیا گیا ہے۔ یہاں، Kilobytes میں Bitmap کا سائز استعمال کیا گیا ہے (rowBytes × height / 1024)۔ جب تمام عناصر کے sizeOf کا مجموعہ cacheSize سے تجاوز کر جاتا ہے، LruCache خود بخود سب سے کم حالیہ استعمال شدہ Bitmap کو خارج کر دیتا ہے۔ 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 کے ذریعے تھریڈ سیفٹی شامل کرنے کی سفارش کی جاتی ہے۔