LRU Cache — mi ez, kiszorítási algoritmus és hogyan működik

Mi az LRU Cache?

LRU Cache (Least Recently Used Cache) — egy fix méretű adatstruktúra, amely korlátozott számú elemet tárol, és automatikusan eltávolítja azokat, amelyekhez a legritkábban fértek hozzá. Amikor egy alkalmazás lekér egy elemet, az a gyorsítótár „friss” részébe kerül, a régen nem használt elemek pedig a vége felé tolódnak, és a határ elérésekor törlődnek.

A „Least Recently Used” elnevezés a kiszorítási politikát írja le: a tárolt elemek közül a legrégebben nem használt kerül eltávolításra. Ez a lokalitási elven (locality of reference) alapul — a közelmúltban lekért adatok nagy valószínűséggel újra szükségesek lesznek. Ezért tekintik az LRU-t a legtöbb alkalmazás számára az egyik leghatékonyabb gyorsítótárazási stratégiának.

A klasszikus LRU Cache implementáció két adatstruktúrát igényel: egy hash táblát az O(1) hozzáféréshez bármely elemhez kulcs alapján, és egy duplán láncolt listát a használati sorrend nyomon követéséhez. A hash tábla referenciákat tárol a lista csomópontjaira, a lista pedig a legújabb elemtől (fej) a legrégebbiig (farok) tartja a sorrendet.

Az LRU Cache alapműveletei

A get(key) művelet ellenőrzi a kulcs jelenlétét a hash táblában. Ha az elem megtalálható, a lista elejére kerül (a legújabb lesz), és az értéke visszaadásra kerül. Ha nem található — null visszaadása vagy kivétel dobása történik. A put(key, value) művelet új elemet szúr be: ha a kulcs már létezik — az érték frissül és az elem a fejre kerül. Ha a gyorsítótár tele van, a beszúrás előtt a lista farok eleme törlődik. Minden művelet konstans O(1) időben hajtódik végre.

Hogyan működik az LRU Cache

Az LRU Cache algoritmus két elven alapul: egy időrendi hozzáférés-számláló és a túlcsorduláskori kiszorítás mechanikája. Minden elem a duplán láncolt lista egy csomópontjában tárolódik, a mutatók ezekre a csomópontokra — a hash táblában. Minden egyes elemhez való hozzáféréskor az leválasztásra kerül az aktuális pozícióról, és a lista elejére kerül.

Amikor a gyorsítótár mérete eléri a maximális értéket (maxSize), és új elem beszúrására irányuló kérés érkezik, az algoritmus eltávolítja a duplán láncolt lista farok elemét — ez a legrégebben nem használt elem. Az eltávolítás után hely szabadul fel az új elem számára, amely a lista fejére kerül. A hash tábla frissül: a régi kulcs törlődik, az új hozzáadódik.

Az LRU jellemzője — érzéketlenség a ciklikusan ismétlődő hozzáférési mintákra. Ha egy alkalmazás időszakosan a gyorsítótár méreténél nagyobb adathalmazhoz fér hozzá, az LRU thrashing-től szenvedhet — az elemek gyakori cseréjétől, amikor minden új kérés kiszorítja az előzőt. Ilyen forgatókönyvekben az LFU (Least Frequently Used) vagy az adaptív algoritmusok hatékonyabbak lehetnek.

Gyorsítótár mérete és metrikák

Az LRU Cache méretének megválasztása kompromisszum a memóriafogyasztás és a hit-ratio (sikeres hozzáférések százaléka) között. Tipikus értékek mobilalkalmazásokhoz: a rendelkezésre álló memória 10–20%-a képgyorsítótárhoz és 50–200 bejegyzés hálózati válaszgyorsítótárhoz. A hit-ratio 80–95% jó mutatónak számít, amelynél a gyorsítótár indokolja a memóriaköltséget. A monitorozáshoz a hitCount és missCount számlálók használhatók, amelyek elérhetők az Android LruCache implementációjában.

LRU Cache implementáció: HashMap + Doubly Linked List

A kanonikus LRU Cache implementáció egy hash tábla és egy duplán láncolt lista kombinációját használja. A hash tábla O(1) hozzáférést biztosít bármely csomóponthoz kulcs alapján, a duplán láncolt lista pedig — a csomópont fejre helyezését és a farokról való törlését O(1) időben. Fontos, hogy a lista pontosan duplán láncolt legyen: ez lehetővé teszi egy csomópont leválasztását a lista közepéről az összes elem bejárása nélkül.

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

Az implementációban minden csomópont (Node) tárolja az értéket és a referenciákat az előző és következő csomópontra. Az őrszem csomópontok (head és tail) leegyszerűsítik a határeseteket — nincs szükség null ellenőrzésre beszúráskor és törléskor. A get metódus a megtalált csomópontot a fejre helyezi, a put pedig túlcsorduláskor törli a farok elemet. Egy külön removeKeyByValue metódus megkeresi a kulcsot a hash táblában a csomópont referenciája alapján, és eltávolítja azt.

Beépített LruCache implementáció Androidban

Az Android SDK kész LruCache osztályt biztosít az android.util csomagban, amely az LRU algoritmust implementálja LinkedHashMap használatával access-order módban. Az osztály thread-safe, támogatja a hit/miss számlálást, valamint entryRemoved callback-et biztosít az erőforrások felszabadításához elem kiszorításakor. A gyorsítótár mérete tetszőleges egységekben állítható be (bájt, elemek száma) — elegendő felülírni a sizeOf metódust.

LRU Cache vs FIFO és LIFO

Mindhárom algoritmus — LRU, FIFO és LIFO — ugyanazt a feladatot oldja meg: a memóriafogyasztás korlátozását elemek kiszorításával túlcsorduláskor. Azonban alapvetően különböző kritériumokat használnak az áldozat kiválasztásához, ami meghatározza hatékonyságukat különböző forgatókönyvekben.

FIFO a legrégebbi elemet szorítja ki a hozzáadás ideje alapján, függetlenül attól, hogy milyen gyakran fértek hozzá. Ez hatástalan lehet, ha a régi elem még mindig releváns. Az LRU elkerüli ezt a hátrányt a hozzáférési minta figyelembevételével. LIFO a frissen hozzáadott elemet szorítja ki — hasznos az undo forgatókönyvekhez, de nem alkalmas gyorsítótárazásra, mivel az új adatok gyakran szükségesebbek a régebbieknél. Az LRU optimális egyensúlynak tekinthető az implementáció komplexitása és a hit-ratio között a legtöbb alkalmazás számára.

LRU Cache kódpéldák

Vizsgáljuk meg a beépített LruCache osztály használatát az Android SDK-ból betöltött képek gyorsítótárazásához. A példa a gyorsítótár inicializálását mutatja az alkalmazás rendelkezésre álló memóriájának 1/8-án, ami a Google szabványos ajánlása a képek gyorsítótárazásához.

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

A sizeOf metódus az elem méretét adja vissza ugyanabban a mértékegységben, mint a cacheSize. Itt a Bitmap mérete kilobájtban van használva (rowBytes × height / 1024). Amikor az összes elem sizeOf-jának összege meghaladja a cacheSize-t, az LruCache automatikusan kiszorítja a legrégebben nem használt Bitmap-eket. Az entryRemoved callback használható a bitmap.recycle() meghívásához — memória felszabadítása a kiszorítás előtt.

LRU Cache implementáció Swift-ben

Az iOS nem rendelkezik beépített LRU Cache osztállyal, de könnyen implementálható NSCache segítségével (amely hasonló, de nem dokumentált kiszorítási politikát használ) vagy saját implementációval Dictionary + Doubly Linked List alapokon, ahogy az alábbiakban látható.

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

Ebben a Swift implementációban a Node egy belső osztály value, next és prev mezőkkel. A moveToHead metódus leválasztja a csomópontot az aktuális pozícióról, és a lista elejére szúrja be. Túlcsorduláskor a tail — a legrégebben nem használt elem — törlődik. Gyártási verzióhoz ajánlott a szálbiztonság hozzáadása NSLock vagy DispatchQueue segítségével.