Ein LRU-Cache (Least Recently Used, „zuletzt am wenigsten genutzt“) verwirft bei vollem Speicher gezielt das Element, das am längsten nicht mehr angefordert wurde. Die Grundidee: Was lange nicht gebraucht wurde, wird vermutlich auch bald nicht gebraucht – das Lokalitätsprinzip, das auch beim Seitenersatz im Betriebssystem gilt.
So funktioniert es
Jeder Zugriff aktualisiert die Reihenfolge: Das angeforderte Element wandert an die Spitze, das am längsten unbenutzte steht hinten. Wird der Cache voll, entfernt er das hinterste Element. Als Datenstruktur kommt typisch eine Hash-Map plus doppelt verkettete Liste zum Einsatz – damit sind get und put in O(1) möglich: Die Map findet das Element, die Liste verschiebt es ohne Suche an den Kopf.
Einsatzgebiete
- CPU-Caches und Cache-Speicher-Hierarchien
- Betriebssysteme: Seitenersatz (als LRU oder Clock-Approximation)
- Datenbanken: Puffer-Pools (z. B. InnoDB Buffer Pool)
- Web-Caches, Redis, Browser-Caches – überall, wo begrenzter Speicher häufige Zugriffe beschleunigt
LRU vs. LFU vs. FIFO
FIFO verwirft das älteste Element unabhängig von der Nutzung, LFU das am seltensten genutzte (nach Zählern) und LRU das zuletzt am längsten unbenutzte. LRU reagiert gut auf kurzfristige Nutzungsmuster; LFU bevorzugt dauerhaft beliebte Elemente, kann aber auf einmal beliebte, dann nie wieder angeforderte Elemente festhalten. Eine gängige Näherung für große Caches ist Clock (Second-Chance), die mit einem Referenzbit pro Eintrag fast LRU-Verhalten erreicht.
Verwandte Grundlagen: Seitenersatz, Page Cache, Seitenfehler, Cache-Speicher.