LRU Cache — co to jest, algorytm wypierania i jak działa

Co to jest LRU Cache?

LRU Cache (Least Recently Used Cache) — to struktura danych o stałym rozmiarze, która przechowuje ograniczoną liczbę elementów i automatycznie usuwa te, do których odwoływano się najrzadziej. Gdy aplikacja żąda elementu, jest on przenoszony do „świeżej” części pamięci podręcznej, a dawno nieużywane elementy przesuwają się na koniec i są usuwane po osiągnięciu limitu.

Nazwa „Least Recently Used” opisuje politykę wypierania: usuwany jest element, który nie był używany najdłużej spośród wszystkich przechowywanych. Opiera się to na założeniu o lokalności odwołań (locality of reference) — niedawno żądane dane z dużym prawdopodobieństwem będą potrzebne ponownie. Dlatego LRU jest uważany za jedną z najskuteczniejszych strategii buforowania dla większości aplikacji.

Klasyczna implementacja LRU Cache wymaga dwóch struktur danych: tablicy mieszającej dla dostępu O(1) do dowolnego elementu po kluczu i listy dwukierunkowej do śledzenia kolejności użycia. Tablica mieszająca przechowuje referencje do węzłów listy, a lista utrzymuje porządek od najnowszego elementu (głowa) do najstarszego (ogon).

Podstawowe operacje LRU Cache

Operacja get(key) sprawdza obecność klucza w tablicy mieszającej. Jeśli element zostanie znaleziony, jest przenoszony na początek listy (staje się najnowszym) i zwracana jest jego wartość. Jeśli nie zostanie znaleziony — zwracane jest null lub zgłaszany wyjątek. Operacja put(key, value) wstawia nowy element: jeśli klucz już istnieje — aktualizowana jest wartość i element przenoszony na początek. Jeśli pamięć podręczna jest pełna, przed wstawieniem usuwany jest element ogonowy listy. Wszystkie operacje wykonywane są w stałym czasie O(1).

Jak działa LRU Cache

Algorytm LRU Cache opiera się na dwóch zasadach: liczniku odwołań w porządku czasowym i mechanice wypierania przy przepełnieniu. Każdy element jest przechowywany w węźle listy dwukierunkowej, a wskaźniki do tych węzłów — w tablicy mieszającej. Przy każdym dostępie do elementu jest on odłączany od bieżącej pozycji i wstawiany na początek listy.

Gdy rozmiar pamięci podręcznej osiąga maksymalną wartość (maxSize) i pojawia się żądanie wstawienia nowego elementu, algorytm usuwa element ogonowy listy dwukierunkowej — jest to właśnie najdłużej nieużywany element. Po usunięciu zwalniane jest miejsce dla nowego elementu, który jest wstawiany na początek listy. Tablica mieszająca jest przy tym aktualizowana: stary klucz jest usuwany, nowy dodawany.

Cechą LRU jest niewrażliwość na wzorce dostępu z cyklicznym powtarzaniem. Jeśli aplikacja okresowo odwołuje się do większego zestawu danych niż rozmiar pamięci podręcznej, LRU może cierpieć na thrashing — częstą wymianę elementów, gdy każde nowe żądanie wypiera poprzednie. W takich scenariuszach bardziej efektywne mogą okazać się LFU (Least Frequently Used) lub algorytmy adaptacyjne.

Rozmiar pamięci podręcznej i metryki

Wybór rozmiaru LRU Cache to kompromis między zużyciem pamięci a hit-ratio (procentem udanych odwołań). Typowe wartości dla aplikacji mobilnych: 10–20% dostępnej pamięci dla pamięci podręcznej obrazów i 50–200 wpisów dla pamięci podręcznej odpowiedzi sieciowych. Hit-ratio 80–95% uważa się za dobry wskaźnik, przy którym pamięć podręczna uzasadnia nakład pamięci. Do monitorowania używa się liczników hitCount i missCount, dostępnych w implementacji LruCache w Android.

Implementacja LRU Cache: HashMap + Doubly Linked List

Kanoniczna implementacja LRU Cache używa kombinacji tablicy mieszającej i listy dwukierunkowej. Tablica mieszająca zapewnia dostęp do dowolnego węzła po kluczu w O(1), a lista dwukierunkowa — przenoszenie węzła na początek i usuwanie z końca w O(1). Ważne, że lista jest właśnie dwukierunkowa: umożliwia to odłączenie węzła ze środka listy bez przeglądania wszystkich elementów.

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

W implementacji każdy węzeł (Node) przechowuje wartość oraz referencje do poprzedniego i następnego węzła. Węzły wartownicze head i tail upraszczają przypadki brzegowe — nie trzeba sprawdzać null przy wstawianiu i usuwaniu. Metoda get przenosi znaleziony węzeł na początek, a put przy przepełnieniu usuwa element ogonowy. Osobna metoda removeKeyByValue znajduje klucz w tablicy mieszającej po referencji do węzła i usuwa go.

Wbudowana implementacja LruCache w Android

Android SDK udostępnia gotową klasę LruCache w pakiecie android.util, która implementuje algorytm LRU z użyciem LinkedHashMap w trybie access-order. Klasa jest thread-safe, obsługuje zliczanie hit/miss, a także udostępnia callback entryRemoved do zwalniania zasobów przy wypieraniu elementu. Rozmiar pamięci podręcznej ustawia się w dowolnych jednostkach (bajty, liczba elementów) — wystarczy nadpisać metodę sizeOf.

LRU Cache vs FIFO i LIFO

Wszystkie trzy algorytmy — LRU, FIFO i LIFO — rozwiązują jedno zadanie: ograniczenie zużycia pamięci poprzez wypieranie elementów przy przepełnieniu. Używają jednak zasadniczo różnych kryteriów wyboru ofiary, co decyduje o ich efektywności w różnych scenariuszach.

FIFO wypiera najstarszy element według czasu dodania, niezależnie od tego, jak często był używany. Może to być nieefektywne, jeśli stary element jest nadal aktualny. LRU unika tej wady, uwzględniając wzorzec odwołań. LIFO wypiera świeżo dodany element — przydatne w scenariuszach undo, ale nieodpowiednie do buforowania, ponieważ nowe dane są często bardziej potrzebne niż stare. LRU uważany jest za optymalny balans między złożonością implementacji a hit-ratio dla większości aplikacji.

Przykłady kodu LRU Cache

Przyjrzyjmy się użyciu wbudowanej klasy LruCache z Android SDK do buforowania załadowanych obrazów. Przykład pokazuje inicjalizację pamięci podręcznej na 1/8 dostępnej pamięci aplikacji, co jest standardowym zaleceniem Google dla pamięci podręcznej obrazów.

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 zwraca rozmiar elementu w tych samych jednostkach, w których ustawiono cacheSize. Użyto tutaj rozmiaru Bitmap w kilobajtach (rowBytes × height / 1024). Gdy suma sizeOf wszystkich elementów przekroczy cacheSize, LruCache automatycznie wypiera najdłużej nieużywane Bitmapy. Callback entryRemoved można wykorzystać do wywołania bitmap.recycle() — zwolnienia pamięci przed wypchnięciem.

Implementacja LRU Cache w Swift

iOS nie ma wbudowanej klasy LRU Cache, ale można ją łatwo zaimplementować przez NSCache (który używa podobnej, ale nieudokumentowanej polityki wypierania) lub przez własną implementację na Dictionary + Doubly Linked List, jak pokazano poniżej.

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

W tej implementacji w Swift Node to wewnętrzna klasa z polami value, next i prev. Metoda moveToHead odłącza węzeł od bieżącej pozycji i wstawia na początek listy. Przy przepełnieniu usuwany jest tail — najdłużej nieużywany element. W wersji produkcyjnej zaleca się również dodanie bezpieczeństwa wątkowego przez NSLock lub kolejkę DispatchQueue.