FIFO Cache — alapfogalmak, a sor algoritmusa és működése

Mi az a FIFO Cache?

FIFO Cache (First In First Out Cache) — fix méretű gyorsítótár, amely egy sort használ az elemek kezelésére. Az első hozzáadott elem a sor elején található, és túlcsorduláskor elsőként törlődik. Az új elemek mindig a sor végére kerülnek, biztosítva, hogy az eltávolítás sorrendje megegyezzen a hozzáadás sorrendjével.

Az LRU-val ellentétben, amely minden hivatkozáskor átrendezi az elemeket, a FIFO nem változtatja meg a meglévő elemek pozícióját get műveleteknél. Ez teszi az algoritmust teljesen determinisztikussá: a hozzáadás sorrendjének ismeretében pontosan megjósolható, hogy melyik elem lesz a következőként eltávolítva. Ez a kiszámíthatóság kritikus a valós idejű rendszerekben, ahol garantálni kell az adatok feldolgozását a beérkezés sorrendjében.

A FIFO Cache implementációja több adatstruktúrára épülhet: körkörös puffer (circular buffer) a maximális teljesítményért, láncolt lista a rugalmasságért, vagy két verem (Two-Stack Queue) a beépített sor nélküli nyelvekhez. A körkörös puffer biztosítja a legjobb gyorsítótár-lokalitást és minimális többletterhelést, de előzetes memóriafoglalást igényel a maxSize számára.

A FIFO Cache alapműveletei

Az enqueue(value) művelet hozzáad egy elemet a sor végéhez. Ha a méret elérte a maxSize értéket, a hozzáadás előtt a sor elejéről törlődik egy elem. A dequeue() művelet eltávolítja és visszaadja a sor elején lévő elemet — a legrégebbi elem kényszerített kivételéhez. A peek() művelet visszaadja a sor elején lévő elemet anélkül, hogy eltávolítaná — a legrégebbi elem megtekintéséhez a sor módosítása nélkül.

Hogyan működik a FIFO Cache

A FIFO algoritmus egy hétköznapi sor viselkedését utánozza: elsőként érkezett, elsőként kiszolgált. A gyorsítótárazás kontextusában ez azt jelenti, hogy a gyorsítótárban legtovább tartózkodó elem kerül eltávolításra helyhiány esetén — függetlenül attól, hogy mennyire keresett. Az eltávolítási politika FIFO esetén figyelmen kívül hagyja a hivatkozások gyakoriságát, ami az algoritmus egyszerre erőssége és gyengesége.

A körkörös pufferrel történő implementációban két mutatót használnak: head (a sor elejének indexe) és tail (a sor végének indexe). Enqueue esetén az elem a tail index alá íródik, és a tail növekszik. Ha a tail eléri a puffer méretét, visszatekeredik a tömb elejére. Ha a tail utoléri a head-et — a sor megtelt, és a head elmozdul (eltávolítás). A körkörös puffer nem igényel dinamikus memóriafoglalást és elkerüli a töredezettséget.

A FIFO Cache hit-ratio értéke 40% és 60% között mozog tipikus terheléseknél, ami magasabb, mint a LIFO-é, de alacsonyabb, mint az LRU-é. Azonban azokban a forgatókönyvekben, ahol az adatelérés egyenletes és nincsenek forró pontok, a FIFO az LRU-val összehasonlítható eredményeket mutathat lényegesen alacsonyabb implementációs komplexitás mellett. A memória hatékonyan kerül felhasználásra: nincs szükség további mutatókra az elemek átrendezéséhez.

A gyorsítótár szennyeződésének problémája

A FIFO fő hátránya — a gyorsítótár szennyeződésének (cache pollution) való kitettség. Ha nagy mennyiségű, soha többé nem szükséges adat kerül a gyorsítótárba, azok fokozatosan eltávolítják az összes hasznos elemet, és a hit-ratio drasztikusan leesik. Az LRU részben megoldja ezt a problémát, mivel a gyakran használt elemek folyamatosan frissülnek az elejére mozgatással, míg az egyszer használtak gyorsabban eltávolításra kerülnek. FIFO esetén az egyszer használt adatok a sor természetes sorrendjében történő eltávolításig maradnak a gyorsítótárban.

FIFO, LRU és LIFO összehasonlítása

A FIFO, LRU és LIFO közötti választás az adatelérési mintázattól és a viselkedés kiszámíthatóságára vonatkozó követelményektől függ. Az LRU a legtöbb forgatókönyvhöz optimális, a FIFO — az egyenletes hozzáférésű adatfolyamokhoz, a LIFO — a veremstruktúrákhoz.

FIFO ideális azokhoz a forgatókönyvekhez, ahol a feldolgozási sorrendnek meg kell egyeznie a beérkezési sorrenddel: adatpufferelés, naplózás, eseményfeldolgozás. LRU jobb az egyenlőtlen hozzáférésű gyorsítótárazáshoz (felhasználói adatok). LIFO csak vermekhez és Visszavonás műveletekhez alkalmazható. A legtöbb mobilalkalmazás esetében az LRU marad az alapértelmezett választás, de a FIFO előnyösebb lehet szigorú memóriakorlátok vagy kiszámíthatósági követelmények esetén.

Hol alkalmazzák a FIFO Cache-t

A FIFO Cache olyan forgatókönyvekben talál alkalmazást, ahol az eltávolítás kiszámíthatósága vagy az adatfeldolgozás sorrendje számít. Tekintsük át a főbb használati eseteket.

Adatfolyamok pufferelése

Audio- és videolejátszás során az adatok folyamatos adatfolyamban érkeznek és ideiglenesen egy pufferben tárolódnak. A FIFO Cache biztosítja, hogy az elsőként kapott töredékek kerüljenek elsőként dekódolásra — ez garantálja a zökkenőmentes lejátszást késedelem nélkül. A puffer mérete az adatfolyam bitsebessége és a megengedett késleltetés alapján kerül kiválasztásra: audiónál tipikusan 2–5 másodperc, videónál — 10–30 másodperc. A FIFO ideális az ilyen forgatókönyvekhez, mivel az adatok átrendezésének (mint az LRU-nál) nincs értelme.

Hálózati kérések sorai

Az egyidejű hálózati kérések számának korlátozásakor a FIFO Cache használható a várakozó kérések tárolására. Az elsőként hozzáadott kérés kerül elsőként végrehajtásra, biztosítva a hálózati erőforrások igazságos elosztását az alkalmazás különböző összetevői között. Ezt a megközelítést használja az OkHttp Dispatcher és hasonló könyvtárak a kapcsolati pool kezelésére.

HTTP-válaszok gyorsítótárazása

A mobil eszközökön lévő egyszerű HTTP-válasz gyorsítótárak gyakran használnak FIFO-t. A kérésekre adott válaszok a beérkezés sorrendjében kerülnek tárolásra, a limit elérésekor pedig a legrégebbiek törlődnek. Bár az LRU jobb hit-ratio-t adna a felhasználói forgatókönyvekhez, a FIFO egyszerűbben implementálható és nem igényli az utolsó hozzáférés idejének tárolását minden válaszhoz. Az egyenletes terhelésű API-k esetében a hit-ratio különbség a FIFO és az LRU között minimális.

Érintési események feldolgozása

Mobilalkalmazásokban az érintési események (touch events) egy FIFO sorban pufferelődnek a gesztusfelismerés előtt. Minden eseményt a bekövetkezés sorrendjében kell feldolgozni, különben a gesztus hibásan kerül felismerésre. A FIFO Cache méretkorláttal megakadályozza a puffer túlcsordulását gyors húzásoknál, eldobva a legrégebbi eseményeket, ha az alkalmazás nem képes azokat feldolgozni.

FIFO Cache kódpéldák

Tekintsük meg a FIFO Cache implementációját Kotlinban körkörös puffer használatával — a mobil eszközök számára legteljesítményesebb megközelítéssel.

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) {
            // legrégebbi elem eltávolítása
            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]
    }
}

A körkörös puffer a head és tail indexeket használja, amelyek ciklikusan növekednek a maxSize modulója szerint. Amikor size == maxSize, az enqueue először eltávolítja a head alatti elemet (a legrégebbit), elmozdítja a head-et, majd az új elemet a tail alá írja. A moduláris aritmetika automatikusan visszatekeri a mutatókat a tömb elejére, kiküszöbölve az adatok kézi másolását.

Implementáció Swiftben két verem segítségével

A Swiftben egy kényelmes alternatíva — a két veremen alapuló FIFO sor (Two-Stack Queue). Az összes enqueue az első verembe (push) történik, míg dequeue esetén az elemek fordított sorrendben kerülnek át a második verembe — így a dequeue művelet átlagosan O(1) lesz.

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

Két verem amortizált O(1) komplexitást biztosít az enqueue és dequeue műveletekhez. Az outStack.removeLast() eltávolításkor a legrégebbi elemet (az elsőként hozzáadottat) távolítja el. Ez a megközelítés nem igényel előzetes memóriafoglalást, de további terhelést jelenthet a szemétgyűjtő számára gyakori veremfordítások esetén. Korlátozott memóriájú mobilalkalmazásokhoz a körkörös puffer továbbra is előnyösebb.