FIFO Cache — Schlüsselkonzepte, Warteschlangenalgorithmus und Funktionsweise

Was ist FIFO Cache?

FIFO Cache (First In First Out Cache) ist ein Cache fester Größe, der eine Warteschlange zur Verwaltung von Elementen verwendet. Das erste hinzugefügte Element wird an den Kopf der Warteschlange gesetzt und bei Überlauf zuerst entfernt. Neue Elemente werden immer am Ende hinzugefügt, sodass die Entfernungsreihenfolge der Additionsreihenfolge entspricht.

Im Gegensatz zu LRU, das Elemente bei jedem Zugriff neu anordnet, ändert FIFO die Position vorhandener Elemente bei Get-Anfragen nicht. Dies macht den Algorithmus vollständig deterministisch: Kennt man die Additionsreihenfolge, kann man genau vorhersagen, welches Element als Nächstes entfernt wird. Diese Vorhersagbarkeit ist für Echtzeitsysteme entscheidend, in denen Daten in der Reihenfolge ihres Eintreffens verarbeitet werden müssen.

Eine FIFO-Cache-Implementierung kann auf mehreren Datenstrukturen aufbauen: einem Ringpuffer für maximale Leistung, einer verketteten Liste für Flexibilität oder zwei Stapeln (Two-Stack-Queue) für Sprachen ohne integrierte Warteschlange. Der Ringpuffer bietet die beste Cache-Lokalität und den geringsten Overhead, erfordert jedoch eine Vorabzuweisung von Speicher für maxSize.

Grundlegende FIFO-Cache-Operationen

Die Operation enqueue(value) fügt ein Element am Ende der Warteschlange hinzu. Wenn die Größe maxSize erreicht, wird das Element am Kopf vor dem Hinzufügen entfernt. Die Operation dequeue() entfernt und gibt das Element am Kopf zurück — zur erzwungenen Extraktion des ältesten Elements. Die Operation peek() gibt das Kopfelement ohne Entfernung zurück — zur Ansicht des ältesten Elements ohne Änderung der Warteschlange.

Wie FIFO Cache funktioniert

Der FIFO-Algorithmus ahmt das Verhalten einer normalen Warteschlange nach: Wer zuerst kommt, mahlt zuerst. Im Kontext des Cachings bedeutet dies, dass das Element, das am längsten im Cache war, entfernt wird, wenn Platz benötigt wird — unabhängig davon, wie beliebt es ist. Die Verdrängungsstrategie von FIFO ignoriert die Zugriffshäufigkeit, was sowohl eine Stärke als auch eine Schwäche des Algorithmus ist.

Bei der Implementierung über einen Ringpuffer werden zwei Zeiger verwendet: head (Index des Warteschlangenkopfes) und tail (Index des Endes). Bei enqueue wird das Element am tail-Index geschrieben und tail erhöht. Wenn tail die Puffergröße erreicht, wird es zum Anfang des Arrays zurückgesetzt. Wenn tail head einholt, ist die Warteschlange voll und head wird verschoben (Verdrängung). Der Ringpuffer erfordert keine dynamische Speicherzuweisung und vermeidet Fragmentierung.

FIFO Cache zeigt eine Trefferquote von 40% bis 60% für typische Arbeitslasten, was höher ist als bei LIFO, aber niedriger als bei LRU. Für Szenarien mit gleichmäßigem Datenzugriff ohne Hot Spots kann FIFO jedoch bei deutlich geringerer Implementierungskomplexität mit LRU vergleichbare Ergebnisse liefern. Der Speicher wird effizient genutzt: Es werden keine zusätzlichen Zeiger für die Neuordnung von Elementen benötigt.

Das Problem der Cache-Verschmutzung

Der Hauptnachteil von FIFO ist die Anfälligkeit für Cache-Verschmutzung. Wenn eine große Menge an Daten, die nie wieder benötigt werden, in den Cache aufgenommen wird, verdrängt sie nach und nach alle nützlichen Elemente, und die Trefferquote sinkt drastisch. LRU löst dieses Problem teilweise, da häufig genutzte Elemente durch Verschieben an den Kopf ständig aufgefrischt werden, während einmalige Daten schneller verdrängt werden. Bei FIFO verbleiben einmalige Daten so lange im Cache, bis sie auf natürliche Weise durch die Warteschlangenreihenfolge verdrängt werden.

Vergleich von FIFO, LRU und LIFO

Die Wahl zwischen FIFO, LRU und LIFO hängt vom Datenzugriffsmuster und den Anforderungen an die Verhaltensvorhersagbarkeit ab. LRU ist für die meisten Szenarien optimal, FIFO für Streamingdaten mit gleichmäßigem Zugriff und LIFO für Stapelstrukturen.

FIFO ist ideal für Szenarien, in denen die Verarbeitungsreihenfolge der Eingangsreihenfolge entsprechen muss: Datenpufferung, Protokollierung, Ereignisverarbeitung. LRU ist besser für Caching mit ungleichmäßigem Zugriff (Benutzerdaten). LIFO ist nur für Stapel und Rückgängig-Funktionen anwendbar. Für die meisten mobilen Anwendungen bleibt LRU die Standardwahl, aber FIFO kann bei strengen Speicherbeschränkungen oder Vorhersagbarkeitsanforderungen vorzuziehen sein.

Wo FIFO Cache verwendet wird

FIFO Cache findet Anwendung in Szenarien, in denen die Vorhersagbarkeit der Verdrängung oder die Reihenfolge der Datenverarbeitung wichtig ist. Betrachten wir die wichtigsten Anwendungsfälle.

Pufferung von Streamingdaten

Bei der Audio- und Videowiedergabe treffen Daten in einem kontinuierlichen Strom ein und werden vorübergehend in einem Puffer gespeichert. FIFO Cache stellt sicher, dass die ersten empfangenen Fragmente als erste zur Dekodierung gesendet werden — dies gewährleistet eine reibungslose Wiedergabe ohne Verzögerungen. Die Puffergröße wird basierend auf der Bitrate des Streams und der akzeptablen Verzögerung gewählt: typischerweise 2–5 Sekunden für Audio, 10–30 Sekunden für Video. FIFO ist ideal für solche Szenarien, da eine Datenumordnung (wie bei LRU) sinnlos ist.

Netzwerkanfragewarteschlangen

Bei der Begrenzung der Anzahl gleichzeitiger Netzwerkanfragen kann FIFO Cache zum Speichern ausstehender Anfragen verwendet werden. Die erste hinzugefügte Anfrage wird zuerst ausgeführt, was eine faire Verteilung der Netzwerkressourcen zwischen verschiedenen Anwendungskomponenten gewährleistet. Dieser Ansatz wird in OkHttp Dispatcher und ähnlichen Bibliotheken zur Verwaltung von Verbindungspools verwendet.

Zwischenspeicherung von HTTP-Antworten

Einfache HTTP-Antwort-Caches auf mobilen Geräten verwenden häufig FIFO. Antworten auf Anfragen werden in der Reihenfolge ihres Eintreffens gespeichert, und bei Erreichen des Limits werden die ältesten entfernt. Obwohl LRU eine bessere Trefferquote für Benutzerszenarien liefern würde, ist FIFO einfacher zu implementieren und erfordert keine Speicherung des letzten Zugriffszeitpunkts für jede Antwort. Bei APIs mit gleichmäßiger Auslastung ist der Unterschied in der Trefferquote zwischen FIFO und LRU minimal.

Verarbeitung von Berührungsereignissen

In mobilen Anwendungen werden Berührungsereignisse vor der Gestenerkennung in einer FIFO-Warteschlange gepuffert. Jedes Ereignis muss in der Reihenfolge seines Auftretens verarbeitet werden, sonst wird die Geste falsch erkannt. Ein FIFO Cache mit Größenbegrenzung verhindert Pufferüberläufe bei schnellen Wischbewegungen, indem die ältesten Ereignisse verworfen werden, wenn die Anwendung nicht mithalten kann.

FIFO Cache Codebeispiele

Betrachten wir eine FIFO-Cache-Implementierung in Kotlin unter Verwendung eines Ringpuffers — des leistungsfähigsten Ansatzes für mobile Geräte.

class FifoCache<V>(
    private val maxSize: Int
) {
    private val buffer = arrayOfNulls<V>(maxSize)
    private var head = 0
    private var tail = 0
    private var size = 0

    fun enqueue(value: V) {
        if (size == maxSize) {
            // ältestes Element entfernen
            buffer[head] = null
            head = (head + 1) % maxSize
            size--
        }
        buffer[tail] = value
        tail = (tail + 1) % maxSize
        size++
    }

    fun dequeue(): V? {
        if (size == 0) return null
        val result = buffer[head]
        buffer[head] = null
        head = (head + 1) % maxSize
        size--
        return result
    }

    fun peek(): V? {
        return buffer[head]
    }
}

Der Ringpuffer verwendet head- und tail-Indizes, die zyklisch um maxSize modulo erhöht werden. Wenn size == maxSize, entfernt enqueue zuerst das Element an head (das älteste), verschiebt head und schreibt dann das neue Element an tail. Die modulare Arithmetik wickelt die Zeiger automatisch zum Anfang des Arrays zurück und macht manuelles Datenkopieren überflüssig.

Swift-Implementierung über zwei Stapel

In Swift ist eine praktische Alternative eine FIFO-Warteschlange auf Basis von zwei Stapeln (Two-Stack-Queue). Alle enqueue-Operationen gehen in den ersten Stapel (push), und bei dequeue werden die Elemente in umgekehrter Reihenfolge in den zweiten Stapel übertragen — was dequeue im Durchschnitt zu O(1) macht.

struct FifoCache<Value> {
    private let maxSize: Int
    private var inStack = [Value]()
    private var outStack = [Value]()

    mutating func enqueue(value: Value) {
        if inStack.count + outStack.count >= maxSize {
            if outStack.isEmpty {
                outStack = inStack.reversed()
                inStack.removeAll()
            }
            outStack.removeLast()
        }
        inStack.append(value)
    }

    mutating func dequeue() -> Value? {
        if outStack.isEmpty {
            outStack = inStack.reversed()
            inStack.removeAll()
        }
        return outStack.popLast()
    }
}

Zwei Stapel bieten eine amortisierte O(1)-Komplexität für enqueue und dequeue. outStack.removeLast() entfernt bei der Verdrängung das älteste Element (das zuerst hinzugefügte). Dieser Ansatz erfordert keine Vorabzuweisung von Speicher, kann aber bei häufigen Stapelumkehrungen eine zusätzliche Belastung für die Speicherbereinigung darstellen. Für mobile Anwendungen mit begrenztem Speicher bleibt der Ringpuffer vorzuziehen.