LRU Cache — bu nima, siqib chiqarish algoritmi va qanday ishlaydi

LRU Cache nima?

LRU Cache (Least Recently Used Cache) — bu o'lchami cheklangan ma'lumotlar tuzilmasi bo'lib, cheklangan miqdordagi elementlarni saqlaydi va eng kam murojaat qilinganlarni avtomatik ravishda o'chiradi. Ilova elementni so'raganda, u keshning “yangi” qismiga ko'chiriladi, uzoq vaqt ishlatilmagan elementlar esa oxirga surilib, chegara erishilganda o'chiriladi.

“Least Recently Used” nomi siqib chiqarish siyosatini tavsiflaydi: saqlanganlar orasida eng uzoq vaqt ishlatilmagan element o'chiriladi. Bu murojaat lokalizatsiyasi (locality of reference) faraziga asoslanadi — yaqinda so'ralgan ma'lumotlar qayta kerak bo'lish ehtimoli yuqori. Aynan shuning uchun LRU ko'pgina ilovalar uchun eng samarali keshlash strategiyalaridan biri hisoblanadi.

Klassik LRU Cache implementatsiyasi ikkita ma'lumotlar tuzilmasini talab qiladi: kalit bo'yicha istalgan elementga O(1) kirish uchun hash jadvali va foydalanish tartibini kuzatish uchun ikki tomonlama bog'langan ro'yxat. Hash jadvali ro'yxat tugunlariga havolalarni saqlaydi, ro'yxat esa eng yangi elementdan (bosh) eng eskisiga (quyruq) qadar tartibni saqlaydi.

LRU Cache ning asosiy operatsiyalari

get(key) operatsiyasi hash jadvalida kalit mavjudligini tekshiradi. Agar element topilsa, u ro'yxatning boshiga ko'chiriladi (eng yangi bo'ladi) va uning qiymati qaytariladi. Agar topilmasa — null qaytariladi yoki istisno tashlanadi. put(key, value) operatsiyasi yangi elementni kiritadi: agar kalit allaqachon mavjud bo'lsa — qiymat yangilanadi va element boshga ko'chiriladi. Agar kesh to'la bo'lsa, kiritishdan oldin ro'yxatning quyruq elementi o'chiriladi. Barcha operatsiyalar doimiy O(1) vaqtida bajariladi.

LRU Cache qanday ishlaydi

LRU Cache algoritmi ikki tamoyilga asoslanadi: vaqt bo'yicha murojaat hisoblagichi va to'lib ketishda siqib chiqarish mexanikasi. Har bir element ikki tomonlama bog'langan ro'yxatning tugunida saqlanadi va bu tugunlarga ko'rsatkichlar hash jadvalida joylashgan. Elementga har bir murojaatda u joriy pozitsiyasidan ajratilib, ro'yxatning boshiga kiritiladi.

Kesh hajmi maksimal qiymatga (maxSize) yetganda va yangi elementni kiritish so'rovi kelganda, algoritm ikki tomonlama bog'langan ro'yxatning quyruq elementini o'chiradi — bu eng uzoq vaqt ishlatilmagan elementdir. O'chirilgandan so'ng yangi element uchun joy bo'shaydi va u ro'yxatning boshiga kiritiladi. Hash jadvali ham yangilanadi: eski kalit o'chiriladi, yangisi qo'shiladi.

LRU ning xususiyati — tsiklik takrorlanadigan kirish naqshlariga sezgir emasligi. Ilova vaqti-vaqti bilan kesh hajmidan katta ma'lumotlar to'plamiga murojaat qilsa, LRU thrashingdan — har bir yangi so'rov oldingisini siqib chiqaradigan tez-tez almashishdan aziyat chekishi mumkin. Bunday stsenariylarda LFU (Least Frequently Used) yoki adaptiv algoritmlar samaraliroq bo'lishi mumkin.

Kesh hajmi va metriklar

LRU Cache hajmini tanlash xotira iste'moli va hit-ratio (muvaffaqiyatli murojaatlar foizi) o'rtasidagi kelishuvdir. Mobil ilovalar uchun odatdagi qiymatlar: rasm keshi uchun mavjud xotiraning 10–20% i va tarmoq javoblari keshi uchun 50–200 ta yozuv. Hit-ratio 80–95% yaxshi ko'rsatkich hisoblanadi, bunda kesh xotira xarajatlarini oqlaydi. Monitoring uchun Androiddagi LruCache implementatsiyasida mavjud bo'lgan hitCount va missCount hisoblagichlaridan foydalaniladi.

LRU Cache implementatsiyasi: HashMap + Doubly Linked List

Kanonik LRU Cache implementatsiyasi hash jadvali va ikki tomonlama bog'langan ro'yxat kombinatsiyasidan foydalanadi. Hash jadvali kalit bo'yicha istalgan tugunga O(1) kirishni ta'minlaydi, ikki tomonlama bog'langan ro'yxat esa tugunni boshga ko'chirish va oxirdan o'chirishni O(1) da amalga oshiradi. Ro'yxatning aynan ikki tomonlama bog'langan bo'lishi muhim: bu barcha elementlarni aylanib o'tmasdan tugunni ro'yxatning o'rtasidan ajratish imkonini beradi.

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)
    }
}

Implementatsiyada har bir tugun (Node) qiymat va oldingi hamda keyingi tugunlarga havolalarni saqlaydi. Boshlang'ich va quyruq sentinel-tugunlari chegaraviy holatlarni soddalashtiradi — kiritish va o'chirishda null tekshiruvi talab qilinmaydi. Get metodi topilgan tugunni boshga ko'chiradi, put esa to'lib ketishda quyruq elementini o'chiradi. Alohida removeKeyByValue metodi hash jadvalida tugun havolasiga ko'ra kalitni topadi va uni o'chiradi.

Androiddagi o'rnatilgan LruCache implementatsiyasi

Android SDK android.util paketida tayyor LruCache klassini taqdim etadi, u access-order rejimida LinkedHashMap dan foydalangan holda LRU algoritmini amalga oshiradi. Klass thread-safe, hit/miss hisoblashni qo'llab-quvvatlaydi, shuningdek element siqib chiqarilganda resurslarni bo'shatish uchun entryRemoved callbackini ta'minlaydi. Kesh hajmi ixtiyoriy birliklarda (bayt, elementlar soni) o'rnatiladi — sizeOf metodini override qilish kifoya.

LRU Cache vs FIFO va LIFO

Har uchala algoritm — LRU, FIFO va LIFO — bitta vazifani hal qiladi: elementlarni to'lib ketishda siqib chiqarish orqali xotira iste'molini cheklash. Biroq ular qurbonni tanlash uchun tubdan farqli mezonlardan foydalanadi, bu esa ularning turli stsenariylarda samaradorligini belgilaydi.

FIFO eng eski elementni qo'shilish vaqtiga ko'ra siqib chiqaradi, undan qanchalik tez-tez foydalanilganidan qat'iy nazar. Bu eski element hali ham dolzarb bo'lsa, samarasiz bo'lishi mumkin. LRU bu kamchilikdan murojaat naqshini hisobga olgan holda qochadi. LIFO yangi kiritilgan elementni siqib chiqaradi — undo stsenariylari uchun foydali, ammo keshlash uchun yaroqsiz, chunki yangi ma'lumotlar ko'pincha eskilaridan ko'ra ko'proq kerak bo'ladi. LRU ko'pgina ilovalar uchun implementatsiya murakkabligi va hit-ratio o'rtasidagi optimal muvozanat hisoblanadi.

LRU Cache kod namunalari

Yuklangan rasmlarni keshlash uchun Android SDK dan o'rnatilgan LruCache klassidan foydalanishni ko'rib chiqamiz. Misol Google-ning rasm keshi uchun standart tavsiyasi bo'lgan ilovaning mavjud xotirasining 1/8 qismida keshni ishga tushirishni ko'rsatadi.

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 metodi element hajmini cacheSize bilan bir xil birliklarda qaytaradi. Bu yerda Bitmap hajmi kilobaytlarda ishlatilgan (rowBytes × height / 1024). Barcha elementlarning sizeOf yig'indisi cacheSize dan oshganda, LruCache avtomatik ravishda eng kam ishlatilgan Bitmap-larni siqib chiqaradi. entryRemoved callbacki bitmap.recycle() ni chaqirish uchun ishlatilishi mumkin — siqib chiqarishdan oldin xotirani bo'shatish.

Swift da LRU Cache implementatsiyasi

iOS da o'rnatilgan LRU Cache klassi yo'q, lekin uni NSCache orqali (o'xshash, ammo hujjatlashtirilmagan siqib chiqarish siyosatidan foydalanadi) yoki Dictionary + Doubly Linked List asosidagi o'z implementatsiyangiz orqali osongina amalga oshirish mumkin, quyida ko'rsatilganidek.

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)
    }
}

Ushbu Swift implementatsiyasida Node — value, next va prev maydonlariga ega ichki klass. moveToHead metodi tugunni joriy pozitsiyasidan ajratib, ro'yxatning boshiga kiritadi. To'lib ketishda eng kam ishlatilgan element bo'lgan tail o'chiriladi. Production versiyasi uchun NSLock yoki DispatchQueue navbati orqali ip xavfsizligini qo'shish tavsiya etiladi.