FIFO Cache — kernbegrippen, wachtrijalgoritme en hoe het werkt

Wat is FIFO Cache?

FIFO Cache (First In First Out Cache) — een cache met vaste grootte die een wachtrij gebruikt voor het beheren van elementen. Het eerste toegevoegde element staat aan de kop van de wachtrij en wordt als eerste verwijderd bij overloop. Nieuwe elementen worden altijd aan de staart toegevoegd, wat garandeert dat de verwijderingsvolgorde overeenkomt met de toevoegingsvolgorde.

In tegenstelling tot LRU, dat elementen herordent bij elke toegang, verandert FIFO de positie van bestaande elementen niet bij get-bewerkingen. Dit maakt het algoritme volledig deterministisch: als de toevoegingsvolgorde bekend is, kan exact worden voorspeld welk element als volgende wordt verwijderd. Deze voorspelbaarheid is cruciaal voor real-time systemen waar gegevensverwerking in volgorde van binnenkomst moet worden gegarandeerd.

De implementatie van FIFO Cache kan op verschillende gegevensstructuren worden gebouwd: circulaire buffer (circular buffer) voor maximale prestaties, gelinkte lijst voor flexibiliteit of twee stacks (Two-Stack Queue) voor talen zonder ingebouwde wachtrij. De circulaire buffer biedt de beste cache-lokaliteit en minimale overhead, maar vereist voorafgaande geheugentoewijzing voor maxSize.

Basisbewerkingen van FIFO Cache

De bewerking enqueue(value) voegt een element toe aan de staart van de wachtrij. Als de grootte maxSize heeft bereikt, wordt vóór het toevoegen het element uit de kop verwijderd. De bewerking dequeue() verwijdert en retourneert het element uit de kop — voor het geforceerd ophalen van het oudste element. De bewerking peek() retourneert het kopelement zonder verwijdering — voor het bekijken van het oudste element zonder de wachtrij te wijzigen.

Hoe werkt FIFO Cache

Het FIFO-algoritme bootst het gedrag van een gewone wachtrij na: wie het eerst komt, het eerst maalt. In de context van caching betekent dit dat het element dat het langst in de cache heeft gezeten, wordt verwijderd bij ruimtegebrek — ongeacht hoe gewild het is. Het verwijderingsbeleid van FIFO negeert de toegangsfrequentie, wat zowel een sterk als een zwak punt van het algoritme is.

Bij implementatie via een circulaire buffer worden twee pointers gebruikt: head (index van de kop van de wachtrij) en tail (index van de staart). Bij enqueue wordt het element geschreven op index tail en wordt tail verhoogd. Als tail de buffergrootte bereikt, wordt deze terug naar het begin van de array gewikkeld. Als tail head inhaalt — is de wachtrij vol en wordt head verschoven (verwijdering). De circulaire buffer vereist geen dynamische geheugentoewijzing en voorkomt fragmentatie.

FIFO Cache vertoont een hit-ratio van 40% tot 60% voor typische belastingen, wat hoger is dan LIFO maar lager dan LRU. Voor scenario's waar de toegang tot gegevens uniform is en er geen hete punten zijn, kan FIFO echter resultaten vergelijkbaar met LRU laten zien bij aanzienlijk lagere implementatiecomplexiteit. Geheugen wordt efficiënt gebruikt: er zijn geen extra pointers nodig voor het herschikken van elementen.

Het probleem van cache-vervuiling

Het belangrijkste nadeel van FIFO — de vatbaarheid voor cache-vervuiling (cache pollution). Als een grote hoeveelheid gegevens die nooit meer nodig zullen zijn aan de cache wordt toegevoegd, zullen ze geleidelijk alle nuttige elementen verwijderen en zal de hit-ratio sterk dalen. LRU lost dit probleem gedeeltelijk op, omdat veelgebruikte elementen constant worden ververst door ze naar de kop te verplaatsen, terwijl eenmalige elementen sneller worden verwijderd. In FIFO blijven eenmalige gegevens in de cache tot ze in de natuurlijke volgorde van de wachtrij worden verwijderd.

Vergelijking van FIFO, LRU en LIFO

De keuze tussen FIFO, LRU en LIFO hangt af van het toegangspatroon tot gegevens en de vereisten voor gedragsvoorspelbaarheid. LRU is optimaal voor de meeste scenario's, FIFO — voor streamgegevens met uniforme toegang, LIFO — voor stackstructuren.

FIFO is ideaal voor scenario's waar de verwerkingsvolgorde moet overeenkomen met de volgorde van binnenkomst: databuffering, loggen, gebeurtenisverwerking. LRU is beter voor caching met ongelijke toegang (gebruikersgegevens). LIFO is alleen toepasbaar voor stacks en Ongedaan maken-bewerkingen. Voor de meeste mobiele applicaties blijft LRU de standaardkeuze, maar FIFO kan de voorkeur hebben bij strikte geheugenbeperkingen of voorspelbaarheidsvereisten.

Waar wordt FIFO Cache toegepast

FIFO Cache vindt toepassing in scenario's waar voorspelbaarheid van verwijdering of de volgorde van gegevensverwerking belangrijk is. Laten we de belangrijkste gebruikssituaties bekijken.

Bufferen van streamgegevens

Bij het afspelen van audio en video komen gegevens in een continue stroom binnen en worden tijdelijk in een buffer opgeslagen. FIFO Cache zorgt ervoor dat de eerste ontvangen fragmenten als eerste naar de decoder worden gestuurd — dit garandeert vloeiend afspelen zonder vertragingen. De buffergrootte wordt gekozen op basis van de bitsnelheid van de stream en de toegestane vertraging: voor audio typisch 2–5 seconden, voor video — 10–30 seconden. FIFO is ideaal voor dergelijke scenario's, omdat het herordenen van gegevens (zoals in LRU) geen zin heeft.

Wachtrijen van netwerkverzoeken

Bij het beperken van het aantal gelijktijdige netwerkverzoeken kan FIFO Cache worden gebruikt voor het opslaan van wachtende verzoeken. Het eerst toegevoegde verzoek wordt als eerste uitgevoerd, wat zorgt voor een eerlijke verdeling van netwerkbronnen tussen verschillende componenten van de applicatie. Deze benadering wordt gebruikt in OkHttp Dispatcher en vergelijkbare bibliotheken voor het beheren van de verbindingspool.

Cachen van HTTP-antwoorden

Eenvoudige caches voor HTTP-antwoorden op mobiele apparaten gebruiken vaak FIFO. Antwoorden op verzoeken worden opgeslagen in volgorde van binnenkomst en bij het bereiken van de limiet worden de oudste verwijderd. Hoewel LRU een betere hit-ratio zou geven voor gebruikersscenario's, is FIFO eenvoudiger te implementeren en vereist het geen opslag van de tijd van laatste toegang voor elk antwoord. Voor API's met uniforme belasting is het verschil in hit-ratio tussen FIFO en LRU minimaal.

Verwerking van aanraakgebeurtenissen

In mobiele applicaties worden aanraakgebeurtenissen (touch events) gebufferd in een FIFO-wachtrij voordat gebaren worden herkend. Elke gebeurtenis moet worden verwerkt in de volgorde van optreden, anders wordt het gebaar onjuist herkend. FIFO Cache met groottebeperking voorkomt bufferoverloop bij snelle swipes door de oudste gebeurtenissen te verwijderen als de applicatie ze niet kan verwerken.

Voorbeelden van FIFO Cache code

Laten we de implementatie van FIFO Cache in Kotlin bekijken met behulp van een circulaire buffer — de meest performante benadering voor mobiele apparaten.

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) {
            // oudste element verwijderen
            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]
    }
}

De circulaire buffer gebruikt indices head en tail, die cyclisch worden verhoogd modulo maxSize. Wanneer size == maxSize, verwijdert enqueue eerst het element bij head (oudste), verschuift head en schrijft vervolgens het nieuwe element bij tail. Modulaire rekenkunde wikkelt de pointers automatisch terug naar het begin van de array, waardoor handmatig kopiëren van gegevens wordt geëlimineerd.

Implementatie in Swift via twee stacks

In Swift is een handig alternatief — een FIFO-wachtrij op basis van twee stacks (Two-Stack Queue). Alle enqueue-bewerkingen worden uitgevoerd in de eerste stack (push), en bij dequeue worden elementen in omgekeerde volgorde naar de tweede stack overgebracht — zo wordt de dequeue-bewerking gemiddeld O(1).

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

Twee stacks bieden een geamortiseerde complexiteit van O(1) voor enqueue en dequeue. outStack.removeLast() verwijdert bij verwijdering het oudste element (eerst toegevoegd). Deze benadering vereist geen voorafgaande geheugentoewijzing, maar kan extra belasting op de garbage collector veroorzaken bij frequente stack-omkeringen. Voor mobiele applicaties met beperkt geheugen blijft de circulaire buffer de voorkeur genieten.