Der Key-Eviction-Sampling-Algorithmus: wie Redis bei maxmemory wirklich auswählt

1. Warum Redis keine exakte LRU-Liste führt

Eine klassische, exakte LRU-Implementierung braucht eine doppelt verkettete Liste, in der jeder Zugriff auf einen Eintrag diesen an das Listenende verschiebt, und eine Hash-Map für den schnellen Zugriff auf die jeweilige Listenposition. Diese Struktur liefert exakte Ergebnisse, kostet aber pro Zugriff zusätzlichen Speicher für die Verkettung sowie zusätzliche Rechenzeit für das ständige Umsortieren, selbst bei einfachen Lesezugriffen, die mit dem eigentlichen Eviction-Vorgang gar nichts zu tun haben.

Redis verzichtet bewusst auf diese exakte Struktur, weil der Speicher-Overhead bei Millionen von Keys erheblich wäre, gerade in einer Software, deren zentrales Verkaufsargument ein möglichst geringer Speicherverbrauch pro gespeichertem Wert ist. Stattdessen speichert Redis pro Key nur ein kompaktes Zugriffs-Metadatum, entweder einen Zeitstempel für LRU-Näherung oder einen Zähler für LFU-Näherung, direkt im ohnehin vorhandenen Objekt-Header, ohne jede zusätzliche Listenstruktur.

2. Wie der Sampling-Algorithmus konkret arbeitet

Muss Redis unter maxmemory-Druck einen Key entfernen, wählt es zufällig eine konfigurierbare Anzahl von Keys aus der Datenbank aus, standardmäßig fünf. Aus dieser kleinen Stichprobe wird derjenige Key ermittelt, der gemäß der aktiven Eviction-Policy am besten zur Entfernung geeignet ist: bei einer LRU-Policy der Key mit dem ältesten gespeicherten Zugriffs-Zeitstempel, bei einer LFU-Policy der Key mit dem niedrigsten Zugriffszähler. Genau dieser eine Key wird dann tatsächlich entfernt.

Reicht ein einzelner entfernter Key nicht aus, um wieder unter das konfigurierte Speicherlimit zu kommen, wiederholt Redis den gesamten Vorgang: eine neue Stichprobe ziehen, den schlechtesten Kandidaten ermitteln, entfernen, und prüfen, ob genug Speicher freigeworden ist. Dieser Zyklus läuft so lange, bis der Speicherverbrauch wieder unter maxmemory liegt, was bei starkem Schreibdruck durchaus mehrfach pro eingehendem Write-Command geschehen kann.

# Vereinfachte Skizze des Sampling-Algorithmus (Pseudocode)
def evict_one_key(db, policy, sample_size):
    kandidaten = db.zufalls_stichprobe(sample_size)
    if policy == "lru":
        schlechtester = min(kandidaten, key=lambda k: k.letzter_zugriff)
    elif policy == "lfu":
        schlechtester = min(kandidaten, key=lambda k: k.zugriffszähler)
    db.entferne(schlechtester)
    return schlechtester

3. Warum eine Approximation für den Anwendungsfall ausreicht

Auf den ersten Blick wirkt eine zufällige Stichprobe wie eine grobe Näherung, die häufig den falschen Key trifft. In der Praxis zeigt sich aber, dass die statistische Qualität der Approximation bereits bei kleinen Stichprobengrößen überraschend gut ist, weil Eviction kein einmaliges Ereignis ist, sondern ein wiederholter Prozess: Selbst wenn eine einzelne Stichprobe zufällig nicht den global ältesten Key enthält, wird über viele aufeinanderfolgende Eviction-Zyklen hinweg statistisch trotzdem bevorzugt eher ältere als neuere Keys entfernt.

Der entscheidende Punkt ist, dass das Eviction-Ziel selten eine perfekte Rangfolge braucht, sondern lediglich eine Tendenz: Selten genutzte Daten sollen mit höherer Wahrscheinlichkeit weichen als häufig genutzte. Für Cache-Workloads, bei denen es um ein gutes Verhältnis von Trefferquote zu Speicherverbrauch geht, nicht um eine mathematisch exakte Reihenfolge, liefert das approximierte Sampling-Verfahren in der Praxis fast identische Ergebnisse wie eine exakte Implementierung, bei einem Bruchteil des Speicher- und Rechenaufwands.

4. maxmemory-samples: Genauigkeit gegen CPU-Kosten abwägen

Die Konfigurationsoption maxmemory-samples legt fest, wie viele Keys pro Eviction-Zyklus als Kandidaten gezogen werden. Der Standardwert von fünf stellt einen bewussten Kompromiss dar, der für die meisten Workloads ein gutes Verhältnis zwischen Trefferqualität und Rechenaufwand bietet. Eine größere Stichprobe erhöht die Wahrscheinlichkeit, dass der tatsächlich am längsten ungenutzte Key gefunden wird, kostet aber pro Eviction-Zyklus mehr CPU-Zeit, weil mehr Kandidaten geprüft und verglichen werden müssen.

Bei sehr hoher Schreiblast nahe am maxmemory-Limit kann diese zusätzliche CPU-Last durch eine große Sample-Größe spürbar werden, weil Eviction-Zyklen dann sehr häufig ausgelöst werden. Eine zu klein gewählte Sample-Größe spart zwar CPU-Zeit, erhöht aber das Risiko, dass häufig genutzte Keys fälschlich entfernt werden, weil die Stichprobe zufällig nur relativ junge Kandidaten enthält und der tatsächlich älteste Key im Datenbestand gar nicht erst gezogen wird.

# Aktuellen Wert prüfen
redis-cli CONFIG GET maxmemory-samples
# maxmemory-samples: 5

# Für höhere Genauigkeit erhöhen (kostet mehr CPU pro Eviction)
redis-cli CONFIG SET maxmemory-samples 10

# In redis.conf dauerhaft setzen
maxmemory-samples 10

5. Sampling bei LRU-Policies im Vergleich zu LFU-Policies

Bei den LRU-basierten Policies volatile-lru und allkeys-lru basiert das Sampling auf einem 24-Bit-Zeitstempel, der bei jedem Zugriff auf den Key aktualisiert wird. Aufgrund der begrenzten Bitbreite handelt es sich technisch bereits um eine Näherung der tatsächlichen Zugriffszeit, die zusätzlich zur Stichproben-Näherung besteht, in der Praxis aber für Eviction-Entscheidungen völlig ausreichend genau ist, da es nur auf die relative Reihenfolge innerhalb einer Stichprobe ankommt, nicht auf die exakte absolute Zeit.

Bei den LFU-basierten Policies volatile-lfu und allkeys-lfu wird statt eines Zeitstempels ein 8-Bit-Zugriffszähler geführt, der mit einem probabilistischen Inkrement-Algorithmus wachsen und mit der Zeit auch wieder abklingen kann, gesteuert über die Parameter lfu-log-factor und lfu-decay-time. Das Sampling-Prinzip selbst bleibt identisch zu LRU: Aus der Stichprobe wird der Key mit dem niedrigsten Zählerwert entfernt, nur die Metrik hinter der Bewertung unterscheidet sich, Häufigkeit statt Aktualität des Zugriffs.

6. Sampling-Umfang: volatile- versus allkeys-Policies

Ein weiterer, oft übersehener Aspekt betrifft den Pool, aus dem die Stichprobe überhaupt gezogen wird. Bei den volatile-Varianten der Policies wie volatile-lru oder volatile-lfu zieht Redis die Zufalls-Stichprobe ausschließlich aus jenen Keys, für die überhaupt eine TTL gesetzt ist. Keys ohne Ablaufzeit bleiben in diesem Modus von der Eviction grundsätzlich verschont, selbst wenn sie seit Ewigkeiten nicht mehr genutzt wurden.

Bei den allkeys-Varianten hingegen umfasst der Stichproben-Pool sämtliche Keys der Datenbank, unabhängig davon, ob eine TTL gesetzt ist oder nicht. Diese Unterscheidung hat direkte praktische Konsequenzen für die Sample-Qualität: In einer Datenbank, in der nur ein kleiner Teil der Keys eine TTL besitzt, ist der effektive Auswahlpool bei volatile-Policies entsprechend kleiner, was die Wahrscheinlichkeit erhöht, dass wiederholt ähnliche Keys in der Stichprobe landen, verglichen mit einer allkeys-Policy auf derselben Datenbank.

7. Praktische Konsequenz für die Wahl der Sample-Größe

Für die große Mehrheit produktiver Redis-Installationen ist der Standardwert von fünf ein sinnvoller Ausgangspunkt, der in unabhängigen Benchmarks bereits eine Trefferqualität nahe an einer exakten LRU-Implementierung erreicht. Eine Erhöhung auf zehn liefert eine messbar bessere Approximation bei moderat steigenden CPU-Kosten und eignet sich für Workloads, bei denen die Genauigkeit der Eviction-Entscheidung eine höhere Priorität hat als die letzte mögliche CPU-Ersparnis, etwa bei einem sehr wertvollen, teuer wiederherstellbaren Cache.

Eine Reduktion unter den Standardwert ist dagegen nur in seltenen Fällen sinnvoll, etwa bei extrem CPU-limitierten Umgebungen mit sehr hoher Eviction-Frequenz, bei denen jede eingesparte Millisekunde zählt und eine etwas ungenauere Eviction-Entscheidung akzeptabel ist. In einem Magento-Kontext, wo Redis häufig als Full-Page-Cache mit vielen unterschiedlich wertvollen Einträgen dient, ist eine moderate Erhöhung auf acht bis zehn oft ein guter Kompromiss, um besonders wertvolle, aufwendig neu zu berechnende Seiten seltener fälschlich zu entfernen.

# Trefferqualität grob abschätzen: Eviction-Zähler beobachten
redis-cli INFO stats | grep evicted_keys

# Nach Erhöhung von maxmemory-samples erneut vergleichen,
# ob sich das Verhältnis von Cache-Hits zu Neuberechnungen verbessert
redis-cli INFO stats | grep -E "keyspace_hits|keyspace_misses"

8. Grenzen des Sampling-Ansatzes

Der Sampling-Ansatz stößt an eine praktische Grenze, wenn die Datenbank sehr wenige Keys enthält, die überhaupt für Eviction infrage kommen, etwa bei volatile-Policies mit nur einer Handvoll Keys mit gesetzter TTL. In diesem Fall nähert sich die Stichprobe zwangsläufig der Gesamtmenge an, und die Näherung wird faktisch zu einer exakten Auswahl, weil kaum noch Zufallsvarianz übrig bleibt. Bei sehr großen Datenbanken mit Millionen infrage kommender Keys hingegen bleibt eine gewisse statistische Unschärfe bestehen, selbst bei erhöhter Sample-Größe.

Wichtig ist außerdem, dass eine höhere Sample-Größe die grundsätzliche Charakteristik des Verfahrens nicht ändert: Es bleibt eine Approximation, keine exakte Berechnung. Wer eine wirklich exakte LRU-Eviction benötigt, muss auf eine andere Architektur ausweichen, etwa eine eigene, anwendungsseitig geführte Zugriffsstruktur, da Redis selbst diese Garantie prinzipbedingt nicht anbietet, unabhängig davon, wie hoch maxmemory-samples gesetzt wird.

9. Praxis-Fazit: Sample-Größe als Stellschraube verstehen, nicht als Notlösung

Der Sampling-basierte Eviction-Algorithmus ist eine bewusste Designentscheidung, die Redis erlaubt, LRU- und LFU-ähnliches Verhalten mit minimalem Speicher-Overhead pro Key anzubieten, statt eine exakte, aber teure Datenstruktur zu pflegen. Für die allermeisten Cache-Workloads ist diese Näherung praktisch nicht von einer exakten Implementierung zu unterscheiden, solange die Sample-Größe nicht unnötig klein gewählt wird.

Wer die Sample-Größe anpasst, sollte das als bewusste Abwägung zwischen Trefferqualität und CPU-Kosten verstehen und die Wirkung über Metriken wie evicted_keys und die Verhältniszahl von keyspace_hits zu keyspace_misses beobachten, statt den Wert blind zu erhöhen. In den meisten Fällen bleibt der Standardwert von fünf die richtige Wahl, eine moderate Erhöhung auf acht bis zehn ist der naheliegende nächste Schritt, wenn die Trefferqualität tatsächlich messbar verbessert werden soll.

10. Zusammenfassung

11. FAQ: Eviction-Sampling