FIFO Cache — nyckelbegrepp, köalgoritmen och hur den fungerar

Vad är FIFO Cache?

FIFO Cache (First In First Out Cache) — en cache med fast storlek som använder en kö för att hantera element. Det första tillagda elementet finns i kön huvudet och kommer att tas bort först vid överflöd. Nya element läggs alltid till i svansen, vilket garanterar att borttagningsordningen överensstämmer med tilläggsordningen.

Till skillnad från LRU, som omordnar element vid varje åtkomst, ändrar FIFO inte positionen för befintliga element vid get-operationer. Detta gör algoritmen helt deterministisk: genom att känna till tilläggsordningen kan man exakt förutsäga vilket element som kommer att tas bort härnäst. En sådan förutsägbarhet är kritisk för realtidssystem där databehandling måste garanteras i ankomstordning.

Implementeringen av FIFO Cache kan byggas på flera datastrukturer: cirkulär buffert (circular buffer) för maximal prestanda, länkad lista för flexibilitet eller två stackar (Two-Stack Queue) för språk utan inbyggd kö. Den cirkulära bufferten ger bäst cache-lokalitet och minimal överhead, men kräver förhandsallokering av minne för maxSize.

Grundläggande operationer för FIFO Cache

Operationen enqueue(value) lägger till ett element i slutet av kön. Om storleken har nått maxSize tas elementet från huvudet bort före tilläggning. Operationen dequeue() tar bort och returnerar elementet från huvudet — för tvungen hämtning av det äldsta elementet. Operationen peek() returnerar elementet från huvudet utan borttagning — för att visa det äldsta elementet utan att ändra kön.

Hur FIFO Cache fungerar

FIFO-algoritmen efterliknar beteendet hos en vanlig kö: först in, först ut. I cachelagringssammanhang innebär detta att elementet som varit längst i cachen tas bort vid platsbrist — oavsett hur efterfrågat det är. Borttagningspolicyn för FIFO ignorerar åtkomstfrekvensen, vilket är både en styrka och en svaghet hos algoritmen.

Vid implementering via cirkulär buffert används två pekare: head (index för kön huvud) och tail (index för kön svans). Vid enqueue skrivs elementet på tail-index och tail ökas. Om tail når buffertens storlek lindas den tillbaka till början av arrayen. Om tail kommer ikapp head — är kön full och head flyttas (borttagning). Den cirkulära bufferten kräver inte dynamisk minnesallokering och undviker fragmentering.

FIFO Cache uppvisar en träfffrekvens på 40% till 60% för typiska belastningar, vilket är högre än LIFO men lägre än LRU. För scenarier där dataåtkomsten är enhetlig och det inte finns några heta punkter kan FIFO dock visa resultat jämförbara med LRU med betydligt lägre implementeringskomplexitet. Minnet används effektivt: inga extra pekare behövs för omordning av element.

Problemet med cache-förorening

Den största nackdelen med FIFO — mottaglighet för cache-förorening (cache pollution). Om en stor mängd data som aldrig kommer att behövas igen läggs till i cachen kommer de gradvis att ta bort alla användbara element och träfffrekvensen sjunker dramatiskt. LRU löser delvis detta problem eftersom ofta använda element ständigt uppdateras genom att flyttas till huvudet, medan engångselement tas bort snabbare. I FIFO förblir engångsdata i cachen tills de tas bort i köns naturliga ordning.

Jämförelse av FIFO, LRU och LIFO

Valet mellan FIFO, LRU och LIFO beror på dataåtkomstmönstret och kraven på beteendeförutsägbarhet. LRU är optimalt för de flesta scenarier, FIFO — för strömmande data med enhetlig åtkomst, LIFO — för stackstrukturer.

FIFO är idealiskt för scenarier där bearbetningsordningen måste överensstämma med ankomstordningen: databuffring, loggning, händelsebearbetning. LRU är bättre för cachelagring med ojämn åtkomst (användardata). LIFO är endast tillämpligt för stackar och Ångra-operationer. För de flesta mobilapplikationer förblir LRU standardvalet, men FIFO kan vara att föredra vid strikta minnesbegränsningar eller krav på förutsägbarhet.

Var används FIFO Cache

FIFO Cache används i scenarier där förutsägbarhet vid borttagning eller databehandlingsordning är viktig. Låt oss titta på de viktigaste användningsfallen.

Buffring av strömmande data

Vid uppspelning av ljud och video kommer data i en kontinuerlig ström och lagras tillfälligt i en buffert. FIFO Cache säkerställer att de första mottagna fragmenten skickas först till avkodning — detta garanterar smidig uppspelning utan fördröjning. Buffertstorleken väljs baserat på strömmens bithastighet och tillåten fördröjning: för ljud typiskt 2–5 sekunder, för video — 10–30 sekunder. FIFO är idealiskt för sådana scenarier eftersom omordning av data (som i LRU) inte är meningsfull.

Köer av nätverksförfrågningar

Vid begränsning av antalet samtidiga nätverksförfrågningar kan FIFO Cache användas för att lagra väntande förfrågningar. Den första tillagda förfrågan kommer att utföras först, vilket säkerställer rättvis fördelning av nätverksresurser mellan olika komponenter i applikationen. Denna metod används i OkHttp Dispatcher och liknande bibliotek för hantering av anslutningspooler.

Cachelagring av HTTP-svar

Enkla cacheminnen för HTTP-svar på mobila enheter använder ofta FIFO. Svar på förfrågningar lagras i ankomstordning och när gränsen nås tas de äldsta bort. Även om LRU skulle ge bättre träfffrekvens för användarscenarier är FIFO enklare att implementera och kräver inte lagring av tid för senaste åtkomst för varje svar. För API med enhetlig belastning är skillnaden i träfffrekvens mellan FIFO och LRU minimal.

Bearbetning av beröringshändelser

I mobilapplikationer buffras beröringshändelser (touch events) i en FIFO-kö före gestigenkänning. Varje händelse måste bearbetas i händelseordning, annars kommer gesten att kännas igen felaktigt. FIFO Cache med storleksbegränsning förhindrar buffertspill vid snabba svepningar genom att kassera de äldsta händelserna om applikationen inte hinner bearbeta dem.

Kodexempel för FIFO Cache

Låt oss titta på implementeringen av FIFO Cache i Kotlin med cirkulär buffert — den mest prestandaeffektiva metoden för mobila enheter.

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) {
            // ta bort äldsta elementet
            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]
    }
}

Den cirkulära bufferten använder indexen head och tail, som cykliskt ökas modulo maxSize. När size == maxSize tar enqueue först bort elementet vid head (äldst), flyttar head och skriver sedan det nya elementet vid tail. Modulär aritmetik lindar automatiskt pekarna tillbaka till början av arrayen, vilket eliminerar manuell kopiering av data.

Implementering i Swift via två stackar

I Swift är ett bekvämt alternativ — FIFO-kö baserad på två stackar (Two-Stack Queue). Alla enqueue utförs i den första stacken (push), och vid dequeue överförs elementen till den andra stacken i omvänd ordning — så dequeue-operationen blir i genomsnitt 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()
    }
}

Två stackar ger amorterad komplexitet O(1) för enqueue och dequeue. outStack.removeLast() vid borttagning tar bort det äldsta elementet (först tillagt). Denna metod kräver inte förhandsallokering av minne men kan skapa extra belastning på sophämtaren vid frekventa stackomkastningar. För mobila applikationer med begränsat minne är den cirkulära bufferten fortfarande att föredra.