LRU Cache — was es ist, Verdrängungsalgorithmus und wie es funktioniert

Was ist LRU Cache?

LRU Cache (Least Recently Used Cache) ist eine Datenstruktur fester Größe, die eine begrenzte Anzahl von Elementen speichert und automatisch diejenigen entfernt, auf die am seltensten zugegriffen wurde. Wenn eine Anwendung ein Element anfordert, wird es in den „frischen“ Teil des Caches verschoben, während lange ungenutzte Elemente zum Ende hin verschoben und bei Erreichen des Limits entfernt werden.

Der Name „Least Recently Used“ beschreibt die Verdrängungsstrategie: Das Element, das von allen gespeicherten Elementen am längsten nicht verwendet wurde, wird entfernt. Dies basiert auf der Annahme der Lokalität von Referenzen (locality of reference) — kürzlich angeforderte Daten werden mit hoher Wahrscheinlichkeit wieder benötigt. Deshalb gilt LRU als eine der effektivsten Caching-Strategien für die meisten Anwendungen.

Die klassische LRU Cache-Implementierung erfordert zwei Datenstrukturen: eine Hashtabelle für O(1)-Zugriff auf jedes Element per Schlüssel und eine doppelt verkettete Liste zur Verfolgung der Nutzungsreihenfolge. Die Hashtabelle speichert Verweise auf die Listenelemente, und die Liste behält die Reihenfolge vom neuesten Element (Kopf) bis zum ältesten (Schwanz) bei.

Grundlegende LRU Cache-Operationen

Die get(key)-Operation prüft, ob der Schlüssel in der Hashtabelle vorhanden ist. Wenn das Element gefunden wird, wird es an den Kopf der Liste verschoben (wird zum neuesten) und sein Wert wird zurückgegeben. Wenn nicht gefunden, wird null zurückgegeben oder eine Ausnahme ausgelöst. Die put(key, value)-Operation fügt ein neues Element ein: Wenn der Schlüssel bereits existiert, wird der Wert aktualisiert und das Element an den Kopf verschoben. Wenn der Cache voll ist, wird das Schwanz-Element vor dem Einfügen entfernt. Alle Operationen werden in konstanter Zeit O(1) ausgeführt.

Wie LRU Cache funktioniert

Der LRU Cache-Algorithmus basiert auf zwei Prinzipien: zeitlich geordnete Zugriffszählung und der Verdrängungsmechanismus bei Überlauf. Jedes Element wird in einem Knoten der doppelt verketteten Liste gespeichert, und Zeiger auf diese Knoten werden in der Hashtabelle gehalten. Bei jedem Zugriff wird das Element von seiner aktuellen Position getrennt und an den Anfang der Liste eingefügt.

Wenn die Cache-Größe ihren Maximalwert (maxSize) erreicht und eine Anfrage zum Einfügen eines neuen Elements eingeht, entfernt der Algorithmus das Schwanz-Element der doppelt verketteten Liste — dies ist das am längsten nicht verwendete Element. Nach der Entfernung wird Platz für das neue Element frei, das an den Kopf der Liste eingefügt wird. Die Hashtabelle wird entsprechend aktualisiert: Der alte Schlüssel wird entfernt, ein neuer hinzugefügt.

Eine Eigenschaft von LRU ist seine Empfindlichkeit gegenüber Zugriffsmustern mit zyklischer Wiederholung. Wenn die Anwendung periodisch auf einen Datensatz zugreift, der größer als die Cache-Größe ist, kann LRU unter Thrashing leiden — häufiger Elementaustausch, bei dem jede neue Anfrage die vorherige verdrängt. In solchen Szenarien können LFU (Least Frequently Used) oder adaptive Algorithmen effektiver sein.

Cache-Größe und Metriken

Die Wahl der LRU Cache-Größe ist ein Kompromiss zwischen Speicherverbrauch und Hit-Ratio (Prozentsatz erfolgreicher Zugriffe). Typische Werte für mobile Anwendungen: 10–20% des verfügbaren Arbeitsspeichers für Bildercache und 50–200 Einträge für Netzwerkantwort-Cache. Eine Hit-Ratio von 80–95% gilt als gut, bei der der Cache die Speicherkosten rechtfertigt. Zur Überwachung werden hitCount- und missCount-Zähler verwendet, die in der LruCache-Implementierung in Android verfügbar sind.

LRU Cache Implementierung: HashMap + Doubly Linked List

Die kanonische LRU Cache-Implementierung verwendet eine Kombination aus Hashtabelle und doppelt verketteter Liste. Die Hashtabelle bietet O(1)-Zugriff auf jeden Knoten per Schlüssel, während die doppelt verkettete Liste das Verschieben eines Knotens an den Kopf und das Entfernen vom Schwanz in O(1) ermöglicht. Wesentlich ist, dass die Liste doppelt verkettet ist: Dies ermöglicht das Trennen eines Knotens aus der Mitte der Liste, ohne alle Elemente durchlaufen zu müssen.

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

In der Implementierung speichert jeder Knoten (Node) einen Wert und Verweise auf den vorherigen und nächsten Knoten. Sentinel-Knoten head und tail vereinfachen Grenzfälle — bei Einfügen und Entfernen muss nicht auf null geprüft werden. Die get-Methode verschiebt den gefundenen Knoten an den Kopf, und put entfernt bei Überlauf das Schwanz-Element. Eine separate Methode removeKeyByValue findet den Schlüssel in der Hashtabelle über den Knotenverweis und entfernt ihn.

Integrierte LruCache-Implementierung in Android

Das Android SDK bietet eine fertige LruCache-Klasse im Paket android.util, die den LRU-Algorithmus mit LinkedHashMap im access-order-Modus implementiert. Die Klasse ist threadsicher, unterstützt hit/miss-Zählung und stellt den Callback entryRemoved zur Ressourcenbereinigung beim Verdrängen eines Elements bereit. Die Cache-Größe wird in beliebigen Einheiten (Bytes, Anzahl der Elemente) festgelegt — es genügt, die sizeOf-Methode zu überschreiben.

LRU Cache vs FIFO und LIFO

Alle drei Algorithmen — LRU, FIFO und LIFO — lösen dasselbe Problem: Begrenzung des Speicherverbrauchs durch Verdrängung von Elementen bei Überlauf. Sie verwenden jedoch grundlegend unterschiedliche Kriterien für die Auswahl des Opfers, was ihre Wirksamkeit in verschiedenen Szenarien bestimmt.

FIFO verdrängt das älteste Element nach Einfügezeit, unabhängig davon, wie oft darauf zugegriffen wurde. Dies kann ineffizient sein, wenn ein altes Element noch relevant ist. LRU vermeidet diesen Nachteil, indem es das Zugriffsmuster berücksichtigt. LIFO verdrängt das zuletzt hinzugefügte Element — nützlich für Rückgängig-Szenarien, aber ungeeignet für Caching, da neue Daten oft benötigter sind als alte. LRU gilt als optimaler Kompromiss zwischen Implementierungskomplexität und Hit-Ratio für die meisten Anwendungen.

LRU Cache Codebeispiele

Betrachten wir die Verwendung der integrierten LruCache-Klasse aus dem Android SDK zum Caching heruntergeladener Bilder. Das Beispiel zeigt die Initialisierung des Caches auf 1/8 des verfügbaren Anwendungsspeichers, was der Standardempfehlung von Google für Bild-Caching entspricht.

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

Die sizeOf-Methode gibt die Elementgröße in denselben Einheiten zurück, in denen cacheSize angegeben ist. Hier wird die Bitmap-Größe in Kilobyte verwendet (rowBytes × height / 1024). Wenn die Summe der sizeOf aller Elemente cacheSize übersteigt, verdrängt LruCache automatisch die am längsten nicht verwendeten Bitmaps. Der entryRemoved-Callback kann verwendet werden, um bitmap.recycle() aufzurufen — Speicherfreigabe vor der Verdrängung.

LRU Cache Implementierung in Swift

iOS verfügt nicht über eine integrierte LRU Cache-Klasse, aber sie lässt sich leicht mit NSCache (das eine ähnliche, aber undokumentierte Verdrängungsstrategie verwendet) oder durch eine benutzerdefinierte Implementierung mit Dictionary + doppelt verketteter Liste realisieren, wie unten gezeigt.

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

In dieser Swift-Implementierung ist Node eine interne Klasse mit value-, next- und prev-Feldern. Die Methode moveToHead trennt einen Knoten von seiner aktuellen Position und fügt ihn an den Kopf der Liste ein. Bei Überlauf wird der Schwanz — das am längsten nicht verwendete Element — entfernt. Für die Produktion wird empfohlen, Threadsicherheit über NSLock oder eine DispatchQueue hinzuzufügen.