LRU Cache — co to je, algoritmus vytěsňování a jak funguje

Co je LRU Cache?

LRU Cache (Least Recently Used Cache) — datová struktura pevné velikosti, která ukládá omezený počet prvků a automaticky odstraňuje ty, ke kterým se přistupovalo nejméně často. Když aplikace požaduje prvek, je přesunut do „čerstvé” části mezipaměti a dlouho nepoužívané prvky se posouvají ke konci a po dosažení limitu jsou odstraněny.

Název „Least Recently Used” popisuje politiku vytěsňování: odstraní se prvek, který nebyl použit nejdéle ze všech uložených. To je založeno na předpokladu lokality referencí (locality of reference) — nedávno požadovaná data budou s vysokou pravděpodobností potřeba znovu. Proto je LRU považován za jednu z nejúčinnějších strategií ukládání do mezipaměti pro většinu aplikací.

Klasická implementace LRU Cache vyžaduje dvě datové struktury: hashovací tabulku pro přístup O(1) k libovolnému prvku podle klíče a obousměrně vázaný seznam pro sledování pořadí použití. Hashovací tabulka ukládá reference na uzly seznamu a seznam udržuje pořadí od nejnovějšího prvku (hlava) po nejstarší (ocas).

Základní operace LRU Cache

Operace get(key) kontroluje přítomnost klíče v hashovací tabulce. Pokud je prvek nalezen, je přesunut na začátek seznamu (stává se nejnovějším) a je vrácena jeho hodnota. Pokud není nalezen — je vráceno null nebo je vyvolána výjimka. Operace put(key, value) vkládá nový prvek: pokud klíč již existuje — hodnota je aktualizována a prvek je přesunut na začátek. Pokud je mezipaměť plná, před vložením je odstraněn ocasní prvek seznamu. Všechny operace jsou prováděny v konstantním čase O(1).

Jak funguje LRU Cache

Algoritmus LRU Cache je založen na dvou principech: čítači přístupů v časovém pořadí a mechanice vytěsňování při přetečení. Každý prvek je uložen v uzlu obousměrně vázaného seznamu a ukazatele na tyto uzly — v hashovací tabulce. Při každém přístupu k prvku je odpojen od aktuální pozice a vložen na začátek seznamu.

Když velikost mezipaměti dosáhne maximální hodnoty (maxSize) a přijde požadavek na vložení nového prvku, algoritmus odstraní ocasní prvek obousměrně vázaného seznamu — to je nejdéle nepoužitý prvek. Po odstranění se uvolní místo pro nový prvek, který je vložen na začátek seznamu. Hashovací tabulka je aktualizována: starý klíč je odstraněn, nový je přidán.

Vlastností LRU je necitlivost na vzory přístupu s cyklickým opakováním. Pokud aplikace periodicky přistupuje k větší datové sadě, než je velikost mezipaměti, může LRU trpět thrashingem — častým nahrazováním prvků, kdy každý nový požadavek vytěsňuje předchozí. V takových scénářích mohou být účinnější LFU (Least Frequently Used) nebo adaptivní algoritmy.

Velikost mezipaměti a metriky

Výběr velikosti LRU Cache je kompromisem mezi spotřebou paměti a hit-ratio (procentem úspěšných přístupů). Typické hodnoty pro mobilní aplikace: 10–20 % dostupné paměti pro mezipaměť obrázků a 50–200 záznamů pro mezipaměť síťových odpovědí. Hit-ratio 80–95 % je považováno za dobrý ukazatel, při kterém mezipaměť ospravedlňuje náklady na paměť. Pro monitorování se používají čítače hitCount a missCount, dostupné v implementaci LruCache v Androidu.

Implementace LRU Cache: HashMap + Doubly Linked List

Kanonická implementace LRU Cache používá kombinaci hashovací tabulky a obousměrně vázaného seznamu. Hashovací tabulka poskytuje přístup k libovolnému uzlu podle klíče v O(1) a obousměrně vázaný seznam — přesun uzlu na začátek a odstranění z konce v O(1). Je důležité, že seznam je právě obousměrně vázaný: to umožňuje odpojení uzlu z prostředka seznamu bez procházení všech prvků.

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

V implementaci každý uzel (Node) ukládá hodnotu a reference na předchozí a následující uzel. Strážní uzly head a tail zjednodušují okrajové případy — není třeba kontrolovat null při vkládání a odebírání. Metoda get přesune nalezený uzel na začátek a put při přetečení odstraní ocasní prvek. Samostatná metoda removeKeyByValue najde klíč v hashovací tabulce podle reference na uzel a odstraní ho.

Vestavěná implementace LruCache v Androidu

Android SDK poskytuje hotovou třídu LruCache v balíčku android.util, která implementuje algoritmus LRU pomocí LinkedHashMap v režimu access-order. Třída je thread-safe, podporuje počítání hit/miss a poskytuje callback entryRemoved pro uvolnění zdrojů při vytěsnění prvku. Velikost mezipaměti se nastavuje v libovolných jednotkách (bajty, počet prvků) — stačí přepsat metodu sizeOf.

LRU Cache vs FIFO a LIFO

Všechny tři algoritmy — LRU, FIFO a LIFO — řeší stejný úkol: omezení spotřeby paměti vytěsňováním prvků při přetečení. Používají však zásadně odlišná kritéria pro výběr oběti, což určuje jejich účinnost v různých scénářích.

FIFO vytěsňuje nejstarší prvek podle času přidání, bez ohledu na to, jak často byl používán. To může být neefektivní, pokud je starý prvek stále relevantní. LRU se tomuto nedostatku vyhýbá tím, že bere v úvahu vzor přístupu. LIFO vytěsňuje čerstvě přidaný prvek — užitečné pro scénáře undo, ale nevhodné pro ukládání do mezipaměti, protože nová data jsou často potřebnější než stará. LRU je považován za optimální rovnováhu mezi složitostí implementace a hit-ratio pro většinu aplikací.

Příklady kódu LRU Cache

Podívejme se na použití vestavěné třídy LruCache z Android SDK pro ukládání načtených obrázků do mezipaměti. Příklad ukazuje inicializaci mezipaměti na 1/8 dostupné paměti aplikace, což je standardní doporučení Google pro mezipaměť obrázků.

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 vrací velikost prvku ve stejných jednotkách, v jakých je nastaven cacheSize. Zde se používá velikost Bitmap v kilobajtech (rowBytes × height / 1024). Když součet sizeOf všech prvků překročí cacheSize, LruCache automaticky vytěsní nejdéle nepoužité Bitmapy. Callback entryRemoved lze použít k volání bitmap.recycle() — uvolnění paměti před vytěsněním.

Implementace LRU Cache ve Swiftu

iOS nemá vestavěnou třídu LRU Cache, ale lze ji snadno implementovat pomocí NSCache (který používá podobnou, ale nedokumentovanou politiku vytěsňování) nebo pomocí vlastní implementace na Dictionary + Doubly Linked List, jak je ukázáno níže.

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

V této Swift implementaci je Node vnitřní třída s poli value, next a prev. Metoda moveToHead odpojí uzel od aktuální pozice a vloží jej na začátek seznamu. Při přetečení je tail — nejdéle nepoužitý prvek — odstraněn. Pro produkční verzi se doporučuje přidání bezpečnosti vláken pomocí NSLock nebo fronty DispatchQueue.