FIFO Cache — klíčové pojmy, algoritmus fronty a jak funguje

Co je FIFO Cache?

FIFO Cache (First In First Out Cache) — je mezipaměť pevné velikosti, která používá frontu pro správu prvků. První přidaný prvek je v čele fronty a bude odstraněn jako první při přetečení. Nové prvky jsou vždy přidávány na konec, což zaručuje, že pořadí odstraňování odpovídá pořadí přidávání.

Na rozdíl od LRU, které přeuspořádává prvky při každém přístupu, FIFO nemění pozici existujících prvků při operacích get. To činí algoritmus plně deterministickým: se znalostí pořadí přidávání lze přesně předpovědět, který prvek bude odstraněn jako další. Taková předvídatelnost je kritická pro systémy reálného času, kde je třeba garantovat zpracování dat v pořadí příchodu.

Implementace FIFO Cache může být postavena na několika datových strukturách: kruhový buffer (circular buffer) pro maximální výkon, spojový seznam pro flexibilitu nebo dva zásobníky (Two-Stack Queue) pro jazyky bez vestavěné fronty. Kruhový buffer poskytuje nejlepší lokalitu mezipaměti a minimální režii, ale vyžaduje předběžné přidělení paměti pro maxSize.

Základní operace FIFO Cache

Operace enqueue(value) přidá prvek na konec fronty. Pokud velikost dosáhla maxSize, před přidáním je odstraněn prvek z čela. Operace dequeue() odstraní a vrátí prvek z čela — pro vynucené získání nejstaršího prvku. Operace peek() vrátí prvek z čela bez odstranění — pro zobrazení nejstaršího prvku bez změny fronty.

Jak funguje FIFO Cache

Algoritmus FIFO napodobuje chování běžné fronty: první dovnitř, první ven. V kontextu ukládání do mezipaměti to znamená, že prvek, který byl v mezipaměti nejdéle, bude odstraněn při nedostatku místa — bez ohledu na to, jak je žádaný. Politika odstraňování FIFO ignoruje frekvenci přístupů, což je současně silnou i slabou stránkou algoritmu.

Při implementaci pomocí kruhového bufferu se používají dva ukazatele: head (index čela fronty) a tail (index konce). Při enqueue je prvek zapsán na index tail a tail se zvyšuje. Pokud tail dosáhne velikosti bufferu, je zatočen zpět na začátek pole. Pokud tail dohoní head — fronta je plná a head se posune (odstranění). Kruhový buffer nevyžaduje dynamické přidělování paměti a zabraňuje fragmentaci.

FIFO Cache vykazuje hit-ratio 40% až 60% pro typická zatížení, což je více než LIFO, ale méně než LRU. Nicméně pro scénáře, kde je přístup k datům rovnoměrný a neexistují horká místa, může FIFO ukázat výsledky srovnatelné s LRU při výrazně nižší složitosti implementace. Paměť je využívána efektivně: nejsou potřeba další ukazatele pro přeskupování prvků.

Problém znečištění mezipaměti

Hlavní nevýhoda FIFO — náchylnost ke znečištění mezipaměti (cache pollution). Pokud je do mezipaměti přidáno velké množství dat, která už nikdy nebudou potřeba, postupně odstraní všechny užitečné prvky a hit-ratio prudce klesne. LRU tento problém částečně řeší, protože často používané prvky jsou neustále obnovovány přesunem na začátek, zatímco jednorázové jsou odstraňovány rychleji. V FIFO zůstávají jednorázová data v mezipaměti, dokud nejsou odstraněna v přirozeném pořadí fronty.

Srovnání FIFO, LRU a LIFO

Výběr mezi FIFO, LRU a LIFO závisí na vzoru přístupu k datům a požadavcích na předvídatelnost chování. LRU je optimální pro většinu scénářů, FIFO — pro datové toky s rovnoměrným přístupem, LIFO — pro zásobníkové struktury.

FIFO je ideální pro scénáře, kde pořadí zpracování musí odpovídat pořadí příchodu: bufferování dat, logování, zpracování událostí. LRU je lepší pro ukládání do mezipaměti s nerovnoměrným přístupem (uživatelská data). LIFO je použitelné pouze pro zásobníky a operace Zpět. Pro většinu mobilních aplikací zůstává LRU výchozí volbou, ale FIFO může být preferováno při přísných omezeních paměti nebo požadavcích na předvídatelnost.

Kde se používá FIFO Cache

FIFO Cache nachází uplatnění ve scénářích, kde je důležitá předvídatelnost odstraňování nebo pořadí zpracování dat. Podívejme se na hlavní případy použití.

Bufferování datových toků

Při přehrávání audia a videa data přicházejí v nepřetržitém toku a jsou dočasně uložena v bufferu. FIFO Cache zajišťuje, že první přijaté fragmenty budou první odeslány k dekódování — to zaručuje plynulé přehrávání bez zpoždění. Velikost bufferu se volí na základě datového toku a povoleného zpoždění: pro audio typicky 2–5 sekund, pro video — 10–30 sekund. FIFO je pro takové scénáře ideální, protože přeskupování dat (jako v LRU) nedává smysl.

Fronty síťových požadavků

Při omezení počtu současných síťových požadavků lze FIFO Cache použít k ukládání čekajících požadavků. První přidaný požadavek bude proveden jako první, což zajišťuje spravedlivé rozdělení síťových zdrojů mezi různé součásti aplikace. Tento přístup se používá v OkHttp Dispatcher a podobných knihovnách pro správu fondu připojení.

Ukládání HTTP odpovědí do mezipaměti

Jednoduché mezipaměti HTTP odpovědí na mobilních zařízeních často používají FIFO. Odpovědi na požadavky jsou ukládány v pořadí příchodu a při dosažení limitu jsou nejstarší odstraněny. Ačkoli by LRU poskytlo lepší hit-ratio pro uživatelské scénáře, FIFO je jednodušší na implementaci a nevyžaduje ukládání času posledního přístupu pro každou odpověď. Pro API s rovnoměrným zatížením je rozdíl v hit-ratio mezi FIFO a LRU minimální.

Zpracování dotykových událostí

V mobilních aplikacích jsou dotykové události (touch events) bufferovány ve frontě FIFO před rozpoznáváním gest. Každá událost musí být zpracována v pořadí výskytu, jinak bude gesto rozpoznáno nesprávně. FIFO Cache s omezením velikosti zabraňuje přetečení bufferu při rychlých swipích, zahazováním nejstarších událostí, pokud je aplikace nestíhá zpracovat.

Příklady kódu FIFO Cache

Podívejme se na implementaci FIFO Cache v Kotlin pomocí kruhového bufferu — nejvýkonnějšího přístupu pro mobilní zařízení.

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) {
            // odstranit nejstarší prvek
            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]
    }
}

Kruhový buffer používá indexy head a tail, které jsou cyklicky zvyšovány modulo maxSize. Když size == maxSize, enqueue nejprve odstraní prvek na head (nejstarší), posune head a poté zapíše nový prvek na tail. Modulární aritmetika automaticky zatočí ukazatele zpět na začátek pole, čímž eliminuje ruční kopírování dat.

Implementace v Swift pomocí dvou zásobníků

V Swift je pohodlnou alternativou — FIFO fronta založená na dvou zásobnících (Two-Stack Queue). Všechny enqueue se provádějí do prvního zásobníku (push), a při dequeue jsou prvky přeneseny do druhého zásobníku v obráceném pořadí — tak se operace dequeue stává průměrně 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()
    }
}

Dva zásobníky poskytují amortizovanou složitost O(1) pro enqueue a dequeue. outStack.removeLast() při odstraňování odstraní nejstarší prvek (první přidaný). Tento přístup nevyžaduje předběžné přidělení paměti, ale může vytvářet dodatečné zatížení garbage collectoru při častých obraceních zásobníku. Pro mobilní aplikace s omezenou pamětí zůstává kruhový buffer preferovanější.