Eviction-Strategien im Detail: LRU, LFU, Random

1. Warum Redis approximiert statt exakt verdrängt

Eine exakte Eviction-Strategie würde bedeuten, dass Redis für jeden einzelnen Schlüssel eine sortierte Datenstruktur pflegt, die stets den am längsten nicht genutzten oder am seltensten genutzten Kandidaten an oberster Stelle hält. Bei Millionen Schlüsseln würde eine solche Struktur, etwa eine doppelt verkettete Liste mit Zeiger pro Schlüssel, erhebliche zusätzliche Speicherkosten verursachen und bei jedem Zugriff eine teure Umsortierung erzwingen. Redis verzichtet deshalb bewusst auf Exaktheit und implementiert jede Eviction-Strategie als statistische Annäherung.

Zum Vergleich: Eine exakte LRU-Liste würde pro Schlüssel mindestens zwei zusätzliche Zeiger benötigen, üblicherweise 16 Byte auf 64-Bit-Systemen. Bei hundert Millionen Schlüsseln summiert sich das auf 1,6 Gigabyte reinen Verwaltungs-Overhead, nur um die Reihenfolge der Zugriffe exakt nachzuhalten, Speicher, der stattdessen für tatsächliche Nutzdaten zur Verfügung stehen könnte.

Diese Designentscheidung ist kein Kompromiss aus Bequemlichkeit, sondern eine bewusste Abwägung zwischen Speicher-Overhead, CPU-Kosten und praktischer Trefferqualität. Studien und interne Benchmarks der Redis-Entwickler zeigen, dass eine gut konfigurierte approximierte Eviction-Strategie bei realistischen Zugriffsmustern nur geringfügig schlechter abschneidet als eine exakte Implementierung, dabei aber einen Bruchteil des Speichers benötigt. Wer die Mechanik hinter dieser Approximation versteht, kann die Parameter gezielt auf das eigene Zugriffsmuster abstimmen, statt sich auf Standardwerte zu verlassen.

Die drei in Redis verfügbaren Eviction-Strategie-Familien, LRU, LFU und Random, unterscheiden sich fundamental darin, welche Metadaten pro Schlüssel gepflegt werden und wie diese Metadaten bei der Auswahl genutzt werden. Die folgenden Abschnitte gehen jede dieser drei Mechaniken bis auf die Implementierungsebene durch, weil erst dieses Verständnis erklärt, warum eine Eviction-Strategie in einem Workload gut funktioniert und im nächsten enttäuscht.

Ein weiterer Grund für die bewusste Approximation liegt in der Architektur des Event-Loops: Redis verarbeitet Befehle grundsätzlich single-threaded, sodass jede zusätzliche Rechenzeit für eine komplexere Eviction-Strategie direkt die Latenz aller anderen wartenden Clients erhöht. Eine Strategie, die theoretisch optimal, aber praktisch zu teuer ist, verschlechtert die Gesamt-Performance mehr, als sie durch bessere Verdrängungsentscheidungen einspart.

2. Der LRU-Sampling-Algorithmus im Detail

Die approximierte LRU-Eviction-Strategie arbeitet mit einem Kandidaten-Pool fester Größe, gesteuert über maxmemory-samples. Bei jedem Verdrängungsvorgang zieht Redis zufällig so viele Schlüssel wie in maxmemory-samples konfiguriert, vergleicht deren Idle-Zeit und entfernt den Kandidaten mit der längsten Inaktivität aus diesem kleinen Sample. Seit Redis 3.0 wird zusätzlich ein persistenter Pool über mehrere Verdrängungsrunden gepflegt: Statt bei jeder Runde bei null zu beginnen, werden gute Kandidaten aus vorherigen Samples im Pool behalten und mit neuen Stichproben verglichen. Das verbessert die Annäherung an echtes LRU erheblich, ohne die Sample-Größe erhöhen zu müssen.

Der Pool-Mechanismus funktioniert wie folgt: Bei jeder Verdrängung werden neue Zufallsschlüssel gezogen und mit den bereits im Pool befindlichen, nach Idle-Zeit sortierten Kandidaten verglichen. Die schlechtesten Kandidaten fallen aus dem Pool, die besten bleiben für die nächste Runde erhalten. Diese Eviction-Strategie konvergiert dadurch über mehrere Verdrängungszyklen hinweg gegen echtes LRU-Verhalten, obwohl pro einzelner Runde nur eine kleine Stichprobe betrachtet wird. Bei einem Sample von 5 erreicht Redis so laut eigenen Benchmarks eine Trefferqualität, die nur wenige Prozentpunkte unter exaktem LRU liegt.

Die Pool-Größe selbst ist intern auf 16 Einträge begrenzt und nicht über eine eigene Konfigurationsoption einstellbar, sie ist ein festes Implementierungsdetail der Eviction-Strategie. Das bedeutet, dass selbst bei sehr hohem maxmemory-samples-Wert nie mehr als 16 Kandidaten gleichzeitig im Pool gehalten werden, was den Speicher-Overhead dieser Optimierung unabhängig von der Sample-Größe konstant und vernachlässigbar klein hält.

# redis.conf: Sampling-Parameter der Eviction-Strategie
maxmemory-policy allkeys-lru
maxmemory-samples 5

# Höhere Sample-Größe erhöht Genauigkeit der Eviction-Strategie,
# kostet aber mehr CPU pro Verdrängungsentscheidung
redis-cli CONFIG SET maxmemory-samples 10

# Approximation vs. exaktes LRU (interne Redis-Benchmarks, Richtwerte):
# samples=3  → ca. 92% Übereinstimmung mit exaktem LRU
# samples=5  → ca. 96% Übereinstimmung (Standardwert)
# samples=10 → ca. 99% Übereinstimmung
#
# Faustregel: samples nur in kleinen Schritten erhöhen und
# jeweils mindestens eine repräsentative Lastperiode beobachten

3. Der Idle-Time-Zeitstempel: wie "zuletzt genutzt" gespeichert wird

Jeder Redis-Objektheader enthält ein 24-Bit-Feld, das entweder als LRU-Zeitstempel oder als LFU-Zähler interpretiert wird, je nach aktiver Eviction-Strategie. Im LRU-Modus speichert dieses Feld eine minutengenaue Uhrzeit relativ zu einem internen Referenzpunkt, der regelmäßig aktualisiert wird, um Bit-Überlauf zu vermeiden. Bei jedem Lese- oder Schreibzugriff auf einen Schlüssel aktualisiert Redis dieses Feld auf die aktuelle Zeit, was praktisch keine zusätzlichen Kosten verursacht, weil kein separater Datenstruktur-Zugriff nötig ist.

Der Befehl OBJECT IDLETIME macht diesen internen Zeitstempel für Diagnosezwecke sichtbar und gibt die Anzahl Sekunden seit dem letzten Zugriff zurück. Diese Metrik ist besonders wertvoll, um vor einer Umstellung der Eviction-Strategie zu prüfen, welche Schlüssel tatsächlich seit Langem inaktiv sind. Wichtig: OBJECT IDLETIME funktioniert nur, solange keine LFU-Policy aktiv ist, weil das Feld sonst als Frequenzzähler interpretiert wird und keine sinnvolle Zeitangabe mehr enthält.

Da die Auflösung minutengenau statt sekundengenau ist, eignet sich das Feld nicht für hochpräzise Latenzmessungen, sondern ausschließlich für die grobe Einordnung, ob ein Schlüssel seit Minuten, Stunden oder Tagen inaktiv ist. Für die Eviction-Strategie reicht diese Granularität vollkommen aus, weil die relative Reihenfolge der Kandidaten im Sample entscheidend ist, nicht die exakte Sekundendifferenz zwischen ihnen.

# Idle-Zeit einzelner Schlüssel vor einer Policy-Umstellung prüfen
redis-cli OBJECT IDLETIME session:user:8842
# (integer) 340

redis-cli OBJECT IDLETIME product:catalog:1123
# (integer) 4

# Nur gültig, solange keine LFU-Policy aktiv ist
redis-cli CONFIG GET maxmemory-policy

4. LFU-Zähler: probabilistisches Wachstum statt linearer Zählung

Für die LFU-Eviction-Strategie nutzt Redis dasselbe 24-Bit-Feld, interpretiert die oberen 8 Bit aber als probabilistischen Zähler nach dem Prinzip des Morris-Counters. Ein linearer Zähler mit nur 8 Bit würde bei 255 sättigen und könnte extrem populäre von moderat populären Schlüsseln nicht mehr unterscheiden. Der probabilistische Ansatz löst dieses Problem: Die Wahrscheinlichkeit, dass ein Zugriff den Zähler tatsächlich erhöht, sinkt mit steigendem aktuellem Zählerstand nach einer logarithmischen Formel, gesteuert über lfu-log-factor.

Konkret bedeutet das: Bei niedrigem Zählerstand erhöht praktisch jeder Zugriff den Wert, bei hohem Zählerstand erhöht nur noch ein kleiner Bruchteil der Zugriffe den Wert weiter. Dadurch kann der 8-Bit-Zähler effektiv Zugriffszahlen im Millionenbereich repräsentieren, ohne zu überlaufen. Diese Eviction-Strategie ist damit speicherneutral gegenüber LRU, weil kein zusätzliches Byte pro Schlüssel benötigt wird, liefert aber ein qualitativ anderes Signal: Häufigkeit über die gesamte Lebensdauer des Schlüssels statt nur den letzten Zugriffszeitpunkt.

# redis.conf: LFU-Zähler-Verhalten feinjustieren
maxmemory-policy allkeys-lfu
lfu-log-factor 10    # höher = langsameres Zählerwachstum bei hohen Werten

# LFU-Zähler eines Schlüssels prüfen (0-255)
redis-cli OBJECT FREQ product:catalog:8842
# (integer) 189

# lfu-log-factor Referenztabelle (ungefähre Zugriffe bis Zähler=255):
# factor=0  → ca. 100.000 Zugriffe
# factor=10 → ca. 1.000.000.000 Zugriffe (Standardwert)
# factor=100 → mehrere Größenordnungen mehr, sehr grobe Auflösung unten

5. LFU-Decay: wie alte Popularität verblasst

Ohne Gegenmechanismus würde ein Schlüssel, der einmal extrem populär war, seinen hohen Zählerstand dauerhaft behalten, selbst wenn er längst nicht mehr angefragt wird. Genau dieses Problem löst der Decay-Mechanismus, der fester Bestandteil der LFU-Eviction-Strategie ist. Über den Parameter lfu-decay-time legt Redis fest, wie viele Minuten Inaktivität nötig sind, damit der Zähler eines Schlüssels beim nächsten Zugriff um einen Punkt reduziert wird, bevor die reguläre Zähler-Logik greift.

Der Decay wird lazy angewendet: Redis führt keinen Hintergrundprozess, der alle Zähler periodisch verringert, sondern berechnet beim nächsten Zugriff auf einen Schlüssel, wie viel Zeit seit dem letzten Zugriff vergangen ist, und reduziert den Zähler proportional dazu, bevor der eigentliche Zugriff gezählt wird. Ein lfu-decay-time von 1 (Standardwert) bedeutet, dass der Zähler pro Minute Inaktivität um einen Punkt sinkt. Ein Wert von 0 deaktiviert Decay vollständig, was für sehr stabile Zugriffsmuster ohne saisonale Schwankungen sinnvoll sein kann, in den meisten Fällen aber zu einer Eviction-Strategie führt, die alte Popularität überbewertet.

Für saisonale Workloads, etwa einen Shop mit ausgeprägtem Weihnachtsgeschäft, ist ein moderater Decay-Wert besonders wichtig, weil sonst im Januar noch dieselben Produktschlüssel als populär gelten, die im Dezember dominierten, obwohl sich das tatsächliche Zugriffsmuster längst verschoben hat. Ein zu aggressiver Decay-Wert hingegen lässt die Eviction-Strategie zu stark auf kurzfristige Schwankungen reagieren und nähert sich in der Wirkung wieder reinem LRU an.

6. Random Eviction: wann Gleichverteilung tatsächlich ausreicht

Random als Eviction-Strategie klingt nach dem Verzicht auf jede Intelligenz, ist aber in bestimmten, klar definierbaren Situationen die effizienteste Wahl. Wenn die Zugriffswahrscheinlichkeit über alle Schlüssel annähernd gleich verteilt ist, etwa bei einem großen Cache für gleichmäßig abgefragte Sensordaten oder bei zufällig verteilten Hashes ohne erkennbares Popularitätsmuster, liefert LRU oder LFU statistisch kein besseres Ergebnis als eine zufällige Auswahl. Der Grund: Beide Strategien versuchen, ein Muster in den Zugriffen zu erkennen und auszunutzen. Existiert kein Muster, gibt es nichts zu erkennen, und der zusätzliche Sampling-Aufwand von LRU oder LFU wird zu reiner Verschwendung.

In der Praxis lohnt sich Random als Eviction-Strategie vor allem bei sehr hohem Schreibdurchsatz, wenn selbst der geringe CPU-Overhead des LRU-Samplings spürbar zur Gesamtlast beiträgt. Ein Benchmark-Ansatz zur Entscheidungsfindung: redis-cli --intrinsic-latency vor und nach dem Wechsel der Policy laufen lassen und die Trefferrate über einen repräsentativen Zeitraum vergleichen. Zeigt sich kein messbarer Unterschied in der Trefferrate zwischen allkeys-lru und allkeys-random, sollte man zur einfacheren und günstigeren Eviction-Strategie wechseln.

Ein weiteres Argument für Random ergibt sich bei sehr kleinen Objekten mit annähernd identischer Größe, etwa Zähler oder Flags, bei denen der Wert eines einzelnen Schlüssels ohnehin kaum von seinen Nachbarn abweicht. In solchen Fällen ist der potenzielle Trefferraten-Gewinn durch LRU oder LFU meist zu gering, um den zusätzlichen Sampling-Aufwand zu rechtfertigen, besonders wenn Tausende dieser Schlüssel pro Sekunde verdrängt werden müssen.

# Random Eviction aktivieren und mit LRU vergleichen
redis-cli CONFIG SET maxmemory-policy allkeys-random
redis-cli --intrinsic-latency 5

redis-cli CONFIG SET maxmemory-policy allkeys-lru
redis-cli --intrinsic-latency 5

# Trefferraten beider Varianten über INFO stats vergleichen
redis-cli INFO stats | grep -E "keyspace_hits|keyspace_misses"

7. Sampling-Pool-Größe: CPU-Kosten gegen Genauigkeit

Die Wahl von maxmemory-samples ist der zentrale Stellhebel, um die Genauigkeit der LRU- oder LFU-Eviction-Strategie gegen CPU-Verbrauch abzuwägen. Jede Erhöhung der Sample-Größe bedeutet mehr Zufallszugriffe auf die interne Hashtabelle pro Verdrängungsentscheidung, was bei hoher Verdrängungsrate spürbar zur CPU-Last beiträgt. Der Standardwert von 5 ist für die meisten Workloads ein guter Kompromiss, weil der persistente Pool-Mechanismus aus Abschnitt 2 bereits einen Großteil der Genauigkeitslücke zu exaktem LRU schließt.

Für Workloads mit besonders hohem Verdrängungsdruck, etwa Caches, die konstant an ihrer Speichergrenze operieren und pro Sekunde tausende Schlüssel verdrängen, kann eine niedrigere Sample-Größe die CPU-Last senken, ohne die Trefferrate spürbar zu verschlechtern, weil der Pool über viele Runden ohnehin konvergiert. Für Workloads mit seltenen, aber besonders folgenreichen Verdrängungsentscheidungen, etwa kleine, hochwertige Caches, lohnt sich eine höhere Sample-Größe, weil die CPU-Kosten insgesamt gering bleiben, während die Genauigkeit der Eviction-Strategie spürbar steigt.

Als Faustregel hat sich in der Praxis bewährt, den Wert schrittweise in kleinen Inkrementen zu erhöhen und nach jeder Änderung mindestens eine repräsentative Lastperiode abzuwarten, bevor die nächste Anpassung erfolgt. Sprunghafte Änderungen von beispielsweise 5 auf 50 erschweren die Zuordnung, welcher Effekt tatsächlich auf die geänderte Sample-Größe zurückzuführen ist und welcher auf natürliche Schwankungen im Zugriffsmuster.

8. Eviction-Strategie unter Cluster-Bedingungen

In einem Redis-Cluster wird die Eviction-Strategie pro Shard unabhängig ausgeführt. Jeder Knoten kennt nur seinen eigenen Speicherverbrauch und die Idle-Zeiten oder LFU-Zähler seiner eigenen Schlüssel, es gibt keine clusterweite Koordination der Verdrängung. Das hat eine wichtige praktische Konsequenz: Bei ungleichmäßiger Verteilung von Hot Keys über die Shards kann ein Knoten unter starkem Verdrängungsdruck stehen, während ein anderer Knoten desselben Clusters noch reichlich freien Speicher hat.

Diese Eigenheit macht Hash-Tag-basierte Schlüsselverteilung und regelmäßiges Monitoring der Pro-Shard-Speichernutzung zu einer Voraussetzung für eine funktionierende Eviction-Strategie im Cluster-Betrieb. Wird ein Shard konsequent stärker belastet als die anderen, hilft keine Anpassung von maxmemory-samples oder lfu-decay-time, sondern nur eine bessere Verteilung der Schlüssel oder ein Resharding. Cluster-Metriken sollten deshalb immer pro Knoten und nicht nur aggregiert über den gesamten Cluster ausgewertet werden.

Ein zusätzlicher Effekt im Cluster-Betrieb: Da jeder Knoten seine eigene Sampling-Population aus einem kleineren Schlüsselraum zieht als eine vergleichbare Standalone-Instanz mit demselben Gesamtdatenbestand, kann die statistische Genauigkeit der LRU-Approximation pro Shard leicht variieren. Bei sehr kleinen Shards mit wenigen tausend Schlüsseln lohnt es sich deshalb, maxmemory-samples testweise zu erhöhen, um die geringere Grundgesamtheit auszugleichen.

9. Messen und Tunen: IDLETIME, FREQ und evicted_keys

Um die Wirksamkeit einer Eviction-Strategie objektiv zu bewerten, reicht ein einzelner Blick auf evicted_keys nicht aus. Sinnvoller ist die Kombination aus Verdrängungsrate, Trefferrate und einer stichprobenartigen Prüfung, ob tatsächlich die richtigen Schlüssel verdrängt werden. OBJECT IDLETIME und OBJECT FREQ erlauben genau diese stichprobenartige Prüfung: Werden regelmäßig Schlüssel mit niedriger Idle-Zeit oder hohem Frequenzzähler verdrängt, deutet das auf ein Problem mit der Sample-Größe oder der Policy-Wahl hin.

Ein praktischer Diagnose-Workflow: Vor einer Umstellung der Eviction-Strategie eine Stichprobe von 50 bis 100 Schlüsseln ziehen und deren IDLETIME oder FREQ protokollieren. Nach der Umstellung dieselbe Stichprobe erneut ziehen und die Verteilung vergleichen. Zusätzlich INFO stats vor und nach der Änderung sichern, um evicted_keys, keyspace_hits und keyspace_misses im direkten Vergleich zu haben. Diese Kombination aus Stichprobe und Aggregatmetrik liefert eine deutlich belastbarere Grundlage als reines Bauchgefühl.

Ein oft übersehener letzter Schritt: Die Stichprobe sollte nicht willkürlich, sondern gezielt über verschiedene Schlüssel-Präfixe hinweg gezogen werden, weil unterschiedliche Datenkategorien innerhalb derselben Instanz, etwa Produktdaten gegenüber Session-Daten, völlig unterschiedliche Zugriffsmuster aufweisen können. Eine einzelne aggregierte Trefferrate über die gesamte Instanz kann dabei gegensätzliche Effekte verschiedener Kategorien verdecken.

# Stichprobe zur Diagnose der aktiven Eviction-Strategie
redis-cli --scan --pattern "product:*" | head -50 | while read -r key; do
  echo "$key: $(redis-cli OBJECT FREQ "$key" 2>/dev/null || redis-cli OBJECT IDLETIME "$key")"
done

# Getrennte Stichproben je Schlüssel-Präfix für differenzierte Auswertung
for prefix in "product:" "session:" "cart:"; do
  echo "=== $prefix ==="
  redis-cli --scan --pattern "${prefix}*" | head -20 | while read -r key; do
    redis-cli OBJECT FREQ "$key" 2>/dev/null
  done
done

# Aggregierte Vergleichsmetriken sichern
redis-cli INFO stats > before.txt
redis-cli CONFIG SET maxmemory-policy allkeys-lfu
sleep 3600
redis-cli INFO stats > after.txt
diff before.txt after.txt | grep -E "evicted_keys|keyspace_"

10. Zusammenfassung

Jede Eviction-Strategie in Redis ist eine bewusst approximierte, keine exakte Implementierung, um Speicher-Overhead und CPU-Kosten in Grenzen zu halten. Approximiertes LRU nutzt einen persistenten Sampling-Pool, der über mehrere Runden gegen echtes LRU-Verhalten konvergiert. LFU nutzt einen probabilistischen 8-Bit-Zähler mit logarithmischem Wachstum und zeitbasiertem Decay, um Häufigkeit ohne Überlauf abzubilden. Random verzichtet vollständig auf Metadaten und ist dort im Vorteil, wo ohnehin kein Zugriffsmuster existiert, das sich ausnutzen ließe.

Die Parameter maxmemory-samples, lfu-log-factor und lfu-decay-time erlauben Feinabstimmung jeder Eviction-Strategie auf das eigene Zugriffsmuster, sollten aber datenbasiert und nicht nach Bauchgefühl gesetzt werden. OBJECT IDLETIME und OBJECT FREQ liefern die nötige Transparenz, um zu prüfen, ob die aktive Eviction-Strategie tatsächlich die richtigen Schlüssel verdrängt. Im Cluster-Betrieb muss diese Prüfung pro Shard erfolgen, weil Verdrängung nie clusterweit koordiniert wird.

Am Ende ist die Wahl der richtigen Eviction-Strategie keine einmalige Entscheidung, sondern ein fortlaufender Abgleich zwischen theoretischem Modell und tatsächlichem Zugriffsverhalten, das sich mit der Zeit verschieben kann. Regelmäßige Stichproben und ein festes Monitoring-Intervall verhindern, dass eine einst passende Konfiguration unbemerkt zur Fehlkonfiguration wird.

11. FAQ: Eviction-Strategien in Redis