FIFO Cache — concepte cheie, algoritmul cozii și cum funcționează

Ce este FIFO Cache?

FIFO Cache (First In First Out Cache) — este un cache de dimensiune fixă care utilizează o coadă pentru gestionarea elementelor. Primul element adăugat se află în capul cozii și va fi șters primul la depășire. Elementele noi sunt întotdeauna adăugate la coadă, garantând că ordinea eliminării coincide cu ordinea adăugării.

Spre deosebire de LRU, care reordonează elementele la fiecare acces, FIFO nu schimbă poziția elementelor existente la operațiile get. Acest lucru face algoritmul complet determinist: cunoscând ordinea adăugării, se poate prezice exact ce element va fi eliminat următorul. O astfel de predictibilitate este critică pentru sistemele de timp real, unde trebuie garantată procesarea datelor în ordinea sosirii.

Implementarea FIFO Cache poate fi construită pe mai multe structuri de date: buffer circular (circular buffer) pentru performanță maximă, listă înlănțuită pentru flexibilitate sau două stive (Two-Stack Queue) pentru limbile fără coadă încorporată. Bufferul circular asigură cea mai bună localitate a cache-ului și o supraîncărcare minimă, dar necesită alocarea prealabilă a memoriei pentru maxSize.

Operații de bază FIFO Cache

Operația enqueue(value) adaugă un element la sfârșitul cozii. Dacă dimensiunea a atins maxSize, înainte de adăugare se elimină elementul din cap. Operația dequeue() elimină și returnează elementul din cap — pentru extragerea forțată a celui mai vechi element. Operația peek() returnează elementul din cap fără eliminare — pentru vizualizarea celui mai vechi element fără a modifica coada.

Cum funcționează FIFO Cache

Algoritmul FIFO imită comportamentul unei cozi obișnuite: primul sosit, primul servit. În contextul cache-ului, aceasta înseamnă că elementul care a stat cel mai mult în cache va fi eliminat la lipsa de spațiu — indiferent de cât de solicitat este. Politica de eliminare FIFO ignoră frecvența accesărilor, ceea ce este atât un punct tare, cât și unul slab al algoritmului.

În implementarea prin buffer circular se utilizează doi pointeri: head (indicele capului cozii) și tail (indicele cozii). La enqueue, elementul este scris la indicele tail, iar tail se incrementează. Dacă tail atinge dimensiunea bufferului, acesta se întoarce la începutul array-ului. Dacă tail ajunge din urmă head — coada este plină și head se deplasează (eliminare). Bufferul circular nu necesită alocare dinamică de memorie și evită fragmentarea.

FIFO Cache demonstrează un hit-ratio de 40% până la 60% pentru sarcini tipice, ceea ce este mai mare decât LIFO, dar mai mic decât LRU. Cu toate acestea, pentru scenariile unde accesul la date este uniform și nu există puncte fierbinți, FIFO poate arăta rezultate comparabile cu LRU la o complexitate de implementare semnificativ mai mică. Memoria este utilizată eficient: nu sunt necesari pointeri suplimentari pentru rearanjarea elementelor.

Problema poluării cache-ului

Principalul dezavantaj al FIFO — susceptibilitatea la poluarea cache-ului (cache pollution). Dacă în cache se adaugă un volum mare de date care nu vor mai fi necesare niciodată, ele vor elimina treptat toate elementele utile, iar hit-ratio va scădea brusc. LRU rezolvă parțial această problemă, deoarece elementele frecvent utilizate se reîmprospătează constant prin mutarea în cap, iar cele unice sunt eliminate mai repede. În FIFO, datele unice rămân în cache până când sunt eliminate în ordinea naturală a cozii.

Comparație între FIFO, LRU și LIFO

Alegerea între FIFO, LRU și LIFO depinde de modelul de acces la date și de cerințele de predictibilitate. LRU este optim pentru majoritatea scenariilor, FIFO — pentru date în flux cu acces uniform, LIFO — pentru structuri de stivă.

FIFO este ideal pentru scenarii unde ordinea procesării trebuie să coincidă cu ordinea sosirii: bufferizarea datelor, logare, procesarea evenimentelor. LRU este mai bun pentru cache cu acces neuniform (date utilizator). LIFO se aplică doar pentru stive și operații Undo. Pentru majoritatea aplicațiilor mobile, LRU rămâne alegerea implicită, dar FIFO poate fi preferat la constrângeri stricte de memorie sau cerințe de predictibilitate.

Unde se aplică FIFO Cache

FIFO Cache își găsește aplicarea în scenarii unde predictibilitatea eliminării sau ordinea procesării datelor contează. Să examinăm principalele cazuri de utilizare.

Bufferizarea datelor în flux

La redarea audio și video, datele sosesc într-un flux continuu și sunt stocate temporar într-un buffer. FIFO Cache asigură că primele fragmente primite vor fi primele trimise la decodare — aceasta garantează redarea fluentă fără întârzieri. Dimensiunea bufferului se alege în funcție de bitrate-ul fluxului și întârzierea admisibilă: pentru audio tipic 2–5 secunde, pentru video — 10–30 secunde. FIFO este ideal pentru astfel de scenarii, deoarece reordonarea datelor (ca în LRU) nu are sens.

Cozile de cereri de rețea

La limitarea numărului de cereri de rețea simultane, FIFO Cache poate fi utilizat pentru stocarea cererilor în așteptare. Prima cerere adăugată va fi executată prima, ceea ce asigură distribuirea echitabilă a resurselor de rețea între diferite componente ale aplicației. Această abordare este utilizată în OkHttp Dispatcher și biblioteci similare pentru gestionarea pool-ului de conexiuni.

Cache pentru răspunsuri HTTP

Cache-urile simple de răspunsuri HTTP pe dispozitivele mobile folosesc adesea FIFO. Răspunsurile la cereri sunt salvate în ordinea sosirii, iar la atingerea limitei sunt șterse cele mai vechi. Deși LRU ar oferi un hit-ratio mai bun pentru scenariile utilizatorilor, FIFO este mai simplu de implementat și nu necesită stocarea timpului ultimului acces pentru fiecare răspuns. Pentru API-uri cu încărcare uniformă, diferența de hit-ratio între FIFO și LRU este minimă.

Procesarea evenimentelor tactile

În aplicațiile mobile, evenimentele tactile (touch events) sunt bufferizate într-o coadă FIFO înainte de recunoașterea gesturilor. Fiecare eveniment trebuie procesat în ordinea apariției, altfel gestul va fi recunoscut incorect. FIFO Cache cu limitare de dimensiune previne depășirea bufferului la swipe-uri rapide, eliminând cele mai vechi evenimente dacă aplicația nu reușește să le proceseze.

Exemple de cod FIFO Cache

Să examinăm implementarea FIFO Cache în Kotlin folosind bufferul circular — cea mai performantă abordare pentru dispozitive mobile.

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) {
            // elimină cel mai vechi element
            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]
    }
}

Bufferul circular utilizează indicii head și tail, care sunt incrementați ciclic modulo maxSize. Când size == maxSize, enqueue mai întâi elimină elementul de la head (cel mai vechi), deplasează head, apoi scrie noul element la tail. Aritmetica modulară întoarce automat pointerii la începutul array-ului, eliminând copierea manuală a datelor.

Implementare în Swift prin două stive

În Swift, o alternativă convenabilă — coada FIFO bazată pe două stive (Two-Stack Queue). Toate enqueue sunt efectuate în prima stivă (push), iar la dequeue elementele sunt transferate în a doua stivă în ordine inversă — astfel operația dequeue devine O(1) în medie.

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

Două stive asigură o complexitate amortizată O(1) pentru enqueue și dequeue. outStack.removeLast() la eliminare șterge cel mai vechi element (primul adăugat). Această abordare nu necesită alocare prealabilă de memorie, dar poate crea o sarcină suplimentară asupra garbage collector-ului la inversări frecvente ale stivei. Pentru aplicațiile mobile cu memorie limitată, bufferul circular rămâne mai preferabil.