LRU Cache — bu nədir, sıxışdırma alqoritmi və necə işləyir

LRU Cache nədir?

LRU Cache (Least Recently Used Cache) — sabit ölçülü məlumat strukturu olub, məhdud sayda elementi saxlayır və ən az müraciət edilənləri avtomatik silir. Tətbiq element tələb etdikdə, o keşin “təzə” hissəsinə köçürülür, uzun müddət istifadə olunmayan elementlər isə sona sürüşərək limit çatdıqda silinir.

“Least Recently Used” adı sıxışdırma siyasətini təsvir edir: saxlanılanlar arasında ən uzun müddət istifadə olunmayan element silinir. Bu, müraciət lokalizasiyası (locality of reference) fərziyyəsinə əsaslanır — yaxın vaxtda tələb edilmiş məlumatların təkrardan ehtiyac olma ehtimalı yüksəkdir. Məhz buna görə LRU əksər tətbiqlər üçün ən effektiv keşləmə strategiyalarından biri hesab olunur.

Klassik LRU Cache implementasiyası iki məlumat strukturu tələb edir: açara görə istənilən elementə O(1) çıxış üçün hash cədvəli və istifadə sırasını izləmək üçün ikiqat əlaqəli siyahı. Hash cədvəli siyahının düyünlərinə istinadlar saxlayır, siyahı isə ən yeni elementdən (baş) ən kökə (quyruq) qədər sıranı qoruyur.

LRU Cache-in əsas əməliyyatları

get(key) əməliyyatı hash cədvəlində açarın mövcudluğunu yoxlayır. Element tapılarsa, siyahının başına köçürülür (ən yeni olur) və dəyəri qaytarılır. Tapılmazsa — null qaytarılır veya istisna atılır. put(key, value) əməliyyatı yeni element daxil edir: açar artıq mövcuddursa — dəyər yenilənir və element başa köçürülür. Keş doludursa, daxil etmədən əvvəl siyahının quyruq elementi silinir. Bütün əməliyyatlar sabit O(1) vaxtında yerinə yetirilir.

LRU Cache necə işləyir

LRU Cache alqoritmi iki prinsipə əsaslanır: zamana görə müraciət sayğacı və daşma zamanı sıxışdırma mexanikası. Hər element ikiqat əlaqəli siyahının düyünündə saxlanılır, bu düyünlərə göstəricilər isə hash cədvəlindədir. Elementə hər müraciətdə o cari mövqeyindən ayrılaraq siyahının əvvəlinə daxil edilir.

Keşin ölçüsü maksimum dəyərə (maxSize) çatdıqda və yeni element daxil etmək sorğusu gəldikdə, alqoritm ikiqat əlaqəli siyahının quyruq elementini silir — bu ən uzun müddət istifadə olunmayan elementdir. Silindikdən sonra yeni element üçün yer boşalır və o siyahının başına daxil edilir. Hash cədvəli də yenilənir: köhnə açar silinir, yenisi əlavə olunur.

LRU-nun xüsusiyyəti — tsiklik təkrarlanan giriş nümunələrinə həssas olmamasıdır. Tətbiq keş ölçüsündən böyük məlumat dəstinə dövri olaraq müraciət edirsə, LRU thrashingdən — hər yeni sorğunun əvvəlkini sıxışdırdığı tez-tez dəyişmədən əziyyət çəkə bilər. Belə ssenarilərdə LFU (Least Frequently Used) və ya adaptiv alqoritmlər daha effektiv ola bilər.

Keş ölçüsü və metrikalar

LRU Cache ölçüsünün seçimi yaddaş istehlakı ilə hit-ratio (uğurlu müraciətlərin faizi) arasında kompromisdir. Mobil tətbiqlər üçün tipik dəyərlər: şəkil keşi üçün mövcud yaddaşın 10–20%-i və şəbəkə cavab keşi üçün 50–200 giriş. Hit-ratio 80–95% yaxşı göstərici hesab olunur, bu zaman keş yaddaş xərclərini əsaslandırır. Monitorinq üçün Android-də LruCache implementasiyasında mövcud olan hitCount və missCount sayğaclarından istifadə olunur.

LRU Cache-in implementasiyası: HashMap + Doubly Linked List

Kanonik LRU Cache implementasiyası hash cədvəli və ikiqat əlaqəli siyahının kombinasiyasından istifadə edir. Hash cədvəli açara görə istənilən düyünə O(1) çıxış təmin edir, ikiqat əlaqəli siyahı isə düyünü başa köçürməyi və sondan silməyi O(1) ilə yerinə yetirir. Siyahının məhz ikiqat əlaqəli olması vacibdir: bu, bütün elementləri gəzmədən düyünü siyahının ortasından ayırmağa imkan verir.

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

Implementasiyada hər düyün (Node) dəyər və əvvəlki və növbəti düyünlərə istinadlar saxlayır. Baş və quyruq sentinel-düyünləri sərhəd hallarını sadələşdirir — daxil etmə və silmə zamanı null yoxlaması tələb olunmur. Get metodu tapılmış düyünü başa köçürür, put isə daşma zamanı quyruq elementini silir. Ayrıca removeKeyByValue metodu hash cədvəlində düyün istinadına görə açarı tapır və onu silir.

Android-də daxili LruCache implementasiyası

Android SDK android.util paketində hazır LruCache sinfi təqdim edir ki, o da access-order rejimində LinkedHashMap istifadə edərək LRU alqoritmini həyata keçirir. Sinif thread-safe-dir, hit/miss hesablamasını dəstəkləyir, həmçinin element sıxışdırıldıqda resursları azad etmək üçün entryRemoved callbackini təmin edir. Keş ölçüsü ixtiyari vahidlərdə (bayt, element sayı) təyin edilir — sizeOf metodunu override etmək kifayətdir.

LRU Cache vs FIFO və LIFO

Hər üç alqoritm — LRU, FIFO və LIFO — eyni məsələni həll edir: daşma zamanı elementləri sıxışdırmaqla yaddaş istehlakını məhdudlaşdırmaq. Lakin onlar qurban seçimi üçün prinsipial fərqli meyarlardan istifadə edir ki, bu da müxtəlif ssenarilərdə effektivliyini müəyyənləşdirir.

FIFO istifadə tezliyindən asılı olmayaraq ən köhnə elementi vaxtına görə sıxışdırır. Bu, köhnə element hələ də aktualdırsa, səmərəsiz ola bilər. LRU bu çatışmazlıqdan qaçır, müraciət nümunəsini nəzərə alır. LIFO təzə daxil edilmiş elementi sıxışdırır — undo ssenariləri üçün faydalıdır, lakin keşləmə üçün yararsızdır, çünki yeni məlumatlar çox vaxt köhnələrdən daha çox lazım olur. LRU əksər tətbiqlər üçün implementasiya mürəkkəbliyi ilə hit-ratio arasında optimal balans hesab olunur.

LRU Cache kod nümunələri

Yüklənmiş şəkillərin keşlənməsi üçün Android SDK-dan daxili LruCache sinfinin istifadəsini nəzərdən keçirək. Nümunə Google-un şəkil keşi üçün standart tövsiyəsi olan tətbiqin mövcud yaddaşının 1/8 hissəsində keşin inisializasiyasını göstərir.

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 metodu elementin ölçüsünü cacheSize ilə eyni vahidlərdə qaytarır. Burada Bitmap ölçüsü kilobaytlarla istifadə olunur (rowBytes × height / 1024). Bütün elementlərin sizeOf cəmi cacheSize-i keçdikdə, LruCache avtomatik olaraq ən az istifadə olunan Bitmap-ları sıxışdırır. entryRemoved callback-i bitmap.recycle() çağırmaq üçün istifadə oluna bilər — sıxışdırmadan əvvəl yaddaşı azad etmək.

Swift-də LRU Cache implementasiyası

iOS-da daxili LRU Cache sinfi yoxdur, lakin onu NSCache vasitəsilə (oxşar, lakin sənədləşdirilməmiş sıxışdırma siyasətindən istifadə edir) və ya Dictionary + Doubly Linked List əsasında öz implementasiyanızla asanlıqla həyata keçirmək olar, aşağıda göstərildiyi kimi.

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

Bu Swift implementasiyasında Node — value, next və prev sahələri olan daxili sinifdir. moveToHead metodu düyünü cari mövqeyindən ayıraraq siyahının başına daxil edir. Daşma zamanı ən az istifadə olunmuş element olan tail silinir. Production versiyası üçün NSLock və ya DispatchQueue növbəsi vasitəsilə thread təhlükəsizliyinin əlavə edilməsi tövsiyə olunur.