LRU Cache — ce este, algoritmul de eliminare și cum funcționează

Ce este LRU Cache?

LRU Cache (Least Recently Used Cache) — este o structură de date de dimensiune fixă care stochează un număr limitat de elemente și șterge automat pe cele la care s-a accesat cel mai rar. Când aplicația solicită un element, acesta este mutat în partea „proaspătă” a cache-ului, iar elementele neutilizate de mult timp se deplasează spre sfârșit și sunt șterse la atingerea limitei.

Denumirea „Least Recently Used” descrie politica de eliminare: se șterge elementul care nu a fost utilizat de cel mai mult timp dintre toate elementele stocate. Aceasta se bazează pe presupunerea localității referințelor (locality of reference) — datele solicitate recent au o probabilitate mare de a fi necesare din nou. De aceea LRU este considerată una dintre cele mai eficiente strategii de cache pentru majoritatea aplicațiilor.

Implementarea clasică a LRU Cache necesită două structuri de date: un tabel hash pentru acces O(1) la orice element după cheie și o listă dublu înlănțuită pentru urmărirea ordinii de utilizare. Tabelul hash stochează referințe la nodurile listei, iar lista menține ordinea de la cel mai nou element (cap) la cel mai vechi (coadă).

Operațiile de bază ale LRU Cache

Operația get(key) verifică prezența cheii în tabelul hash. Dacă elementul este găsit, este mutat la începutul listei (devine cel mai nou) și se returnează valoarea sa. Dacă nu este găsit — se returnează null sau se aruncă o excepție. Operația put(key, value) inserează un element nou: dacă cheia există deja — valoarea este actualizată și elementul este mutat la început. Dacă cache-ul este plin, înainte de inserare se șterge elementul de la coada listei. Toate operațiile se execută în timp constant O(1).

Cum funcționează LRU Cache

Algoritmul LRU Cache se bazează pe două principii: un contor de accesări în ordinea timpului și mecanica de eliminare la depășire. Fiecare element este stocat într-un nod al listei dublu înlănțuite, iar pointerii către aceste noduri — în tabelul hash. La fiecare acces la element, acesta este deconectat de la poziția curentă și inserat la începutul listei.

Când dimensiunea cache-ului atinge valoarea maximă (maxSize) și apare o solicitare de inserare a unui element nou, algoritmul șterge elementul de la coada listei dublu înlănțuite — acesta este elementul cel mai puțin recent utilizat. După ștergere, se eliberează spațiu pentru elementul nou, care este inserat la începutul listei. Tabelul hash este actualizat: cheia veche este ștearsă, cea nouă este adăugată.

Particularitatea LRU — insensibilitatea la modelele de acces cu repetare ciclică. Dacă aplicația accesează periodic un set de date mai mare decât dimensiunea cache-ului, LRU poate suferi de thrashing — înlocuirea frecventă a elementelor, când fiecare solicitare nouă o elimină pe precedenta. În astfel de scenarii, LFU (Least Frequently Used) sau algoritmii adaptivi pot fi mai eficienți.

Dimensiunea cache-ului și metrice

Alegerea dimensiunii LRU Cache este un compromis între consumul de memorie și hit-ratio (procentul de accesări reușite). Valorile tipice pentru aplicațiile mobile: 10–20% din memoria disponibilă pentru cache-ul de imagini și 50–200 de intrări pentru cache-ul de răspunsuri de rețea. Hit-ratio de 80–95% este considerat un indicator bun, la care cache-ul justifică costul de memorie. Pentru monitorizare se folosesc contoarele hitCount și missCount, disponibile în implementarea LruCache din Android.

Implementarea LRU Cache: HashMap + Doubly Linked List

Implementarea canonică a LRU Cache folosește combinația dintre un tabel hash și o listă dublu înlănțuită. Tabelul hash oferă acces la orice nod după cheie în O(1), iar lista dublu înlănțuită — mutarea nodului la început și ștergerea de la sfârșit în O(1). Este important ca lista să fie exact dublu înlănțuită: aceasta permite deconectarea nodului din mijlocul listei fără a parcurge toate elementele.

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

În implementare, fiecare nod (Node) stochează valoarea și referințe la nodul anterior și următor. Nodurile santinelă head și tail simplifică cazurile limită — nu este nevoie de verificări null la inserare și ștergere. Metoda get mută nodul găsit la început, iar put la depășire șterge elementul de la coadă. O metodă separată removeKeyByValue găsește cheia în tabelul hash după referința la nod și o șterge.

Implementarea încorporată LruCache în Android

Android SDK oferă clasa gata făcută LruCache în pachetul android.util, care implementează algoritmul LRU folosind LinkedHashMap în modul access-order. Clasa este thread-safe, suportă numărarea hit/miss și oferă callback-ul entryRemoved pentru eliberarea resurselor la eliminarea unui element. Dimensiunea cache-ului se setează în unități arbitrare (octeți, număr de elemente) — este suficient să suprascrieți metoda sizeOf.

LRU Cache vs FIFO și LIFO

Toți cei trei algoritmi — LRU, FIFO și LIFO — rezolvă aceeași problemă: limitarea consumului de memorie prin eliminarea elementelor la depășire. Cu toate acestea, ei folosesc criterii fundamental diferite pentru alegerea victimei, ceea ce determină eficiența lor în diferite scenarii.

FIFO elimină cel mai vechi element după timpul de adăugare, indiferent de cât de des a fost accesat. Acest lucru poate fi ineficient dacă elementul vechi este încă relevant. LRU evită acest dezavantaj, ținând cont de modelul de acces. LIFO elimină elementul proaspăt adăugat — util pentru scenariile de undo, dar nepotrivit pentru cache, deoarece datele noi sunt adesea mai necesare decât cele vechi. LRU este considerat echilibrul optim între complexitatea implementării și hit-ratio pentru majoritatea aplicațiilor.

Exemple de cod LRU Cache

Să analizăm utilizarea clasei încorporate LruCache din Android SDK pentru cache-ul imaginilor încărcate. Exemplul arată inițializarea cache-ului cu 1/8 din memoria disponibilă a aplicației, ceea ce este recomandarea standard Google pentru cache-ul de imagini.

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

Metoda sizeOf returnează dimensiunea elementului în aceleași unități în care a fost setat cacheSize. Aici se folosește dimensiunea Bitmap în kiloocteți (rowBytes × height / 1024). Când suma sizeOf a tuturor elementelor depășește cacheSize, LruCache elimină automat Bitmap-urile cel mai puțin recent utilizate. Callback-ul entryRemoved poate fi folosit pentru a apela bitmap.recycle() — eliberarea memoriei înainte de eliminare.

Implementarea LRU Cache în Swift

iOS nu are o clasă LRU Cache încorporată, dar poate fi ușor implementată prin NSCache (care folosește o politică de eliminare similară, dar nedocumentată) sau printr-o implementare proprie pe bază de Dictionary + Doubly Linked List, așa cum se arată mai jos.

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

În această implementare Swift, Node este o clasă internă cu câmpurile value, next și prev. Metoda moveToHead deconectează nodul de la poziția curentă și îl inserează la începutul listei. La depășire, se șterge tail — elementul cel mai puțin recent utilizat. Pentru versiunea de producție, se recomandă adăugarea siguranței firelor prin NSLock sau o coadă DispatchQueue.