FIFO Cache — кључни појмови, алгоритам реда и како ради

Шта је FIFO Cache?

FIFO Cache (First In First Out Cache) — кеш фиксне величине који користи ред за управљање елементима. Први додани елемент налази се на почетку реда и биће први уклоњен при препуњавању. Нови елементи се увијек додају на крај, гарантујући да се редослијед избацивања поклапа са редослиједом додавања.

За разлику од LRU, који преуређује елементе при сваком приступу, FIFO не мијења положај постојећих елемената при get операцијама. То чини алгоритам потпуно детерминистичким: знајући редослијед додавања, може се тачно предвидјети који елемент ће бити сљедећи избачен. Таква предвидљивост је кључна за системе реалног времена, гдје треба гарантовати обраду података по редослиједу пристизања.

Имплементација FIFO Cache може бити изграђена на неколико структура података: кружни бафер (circular buffer) за максималне перформансе, повезана листа за флексибилност или два стека (Two-Stack Queue) за језике без уграђеног реда. Кружни бафер обезбјеђује најбољу кеш-локалност и минимално додатно оптерећење, али захтијева претходно додјељивање меморије за maxSize.

Основне операције FIFO Cache

Операција enqueue(value) додаје елемент на крај реда. Ако је величина достигла maxSize, прије додавања уклања се елемент са почетка. Операција dequeue() уклања и враћа елемент са почетка — за присилно извлачење најстаријег елемента. Операција peek() враћа елемент са почетка без уклањања — за преглед најстаријег елемента без мијењања реда.

Како ради FIFO Cache

Алгоритам FIFO опонаша понашање обичног реда: први ушао први се услужује. У контексту кеширања то значи да ће елемент који је најдуже остао у кешу бити уклоњен при недостатку простора — без обзира на то колико је тражен. Политика избацивања FIFO игнорише учесталост приступа, што је истовремено јака и слаба страна алгоритма.

При имплементацији преко кружног бафера користе се два показивача: head (индекс почетка реда) и tail (индекс краја). При enqueue елемент се уписује под индексом tail, а tail се повећава. Ако tail достигне величину бафера, он се враћа на почетак низа. Ако tail сустигне head — ред је пун и head се помјера (избацивање). Кружни бафер не захтијева динамичку додјелу меморије и избјегава фрагментацију.

FIFO Cache показује hit-ratio од 40% до 60% за типична оптерећења, што је више од LIFO, али мање од LRU. Међутим, за сценарије гдје је приступ подацима равномјеран и нема врућих тачака, FIFO може показати резултате упоредиве са LRU уз знатно мању сложеност имплементације. Меморија се користи ефикасно: нису потребни додатни показивачи за премјештање елемената.

Проблем загађења кеша

Главни недостатак FIFO — подложност загађењу кеша (cache pollution). Ако се у кеш дода велика количина података који више никада неће бити потребни, они ће постепено избацити све корисне елементе и hit-ratio ће нагло опасти. LRU дјелимично рјешава овај проблем, јер ће се често коришћени елементи стално освјежавати премјештањем на почетак, а једнократни брже избацивати. У FIFO, једнократни подаци остају у кешу док се не избаце природним редослиједом реда.

Поређење FIFO, LRU и LIFO

Избор између FIFO, LRU и LIFO зависи од обрасца приступа подацима и захтјева за предвидљивошћу понашања. LRU је оптималан за већину сценарија, FIFO — за токовне податке са равномјерним приступом, LIFO — за структуре стека.

FIFO је идеалан за сценарије гдје редослијед обраде треба да се поклапа са редослиједом пристизања: баферизација података, логирање, обрада догађаја. LRU је бољи за кеширање са неравномјерним приступом (кориснички подаци). LIFO се примјењује само за стекове и Undo операције. За већину мобилних апликација LRU остаје подразумијевани избор, али FIFO може бити пожељнији при строгим ограничењима меморије или захтјевима за предвидљивост.

Гдје се примјењује FIFO Cache

FIFO Cache налази примјену у сценаријима гдје је важна предвидљивост избацивања или редослијед обраде података. Размотримо главне случајеве употребе.

Баферизација токовних података

При репродукцији аудија и видеа, подаци пристижу у непрекидном току и привремено се чувају у баферу. FIFO Cache обезбјеђује да ће први примљени фрагменти бити први послати на декодирање — то гарантује глатку репродукцију без кашњења. Величина бафера се бира на основу битрејта тока и дозвољеног кашњења: за аудио типично 2–5 секунди, за видео — 10–30 секунди. FIFO је идеалан за такве сценарије, јер преуређивање података (као у LRU) нема смисла.

Редови мрежних захтјева

При ограничавању броја истовремених мрежних захтјева, FIFO Cache се може користити за чување захтјева на чекању. Први додани захтјев ће бити извршен први, што обезбјеђује праведну расподјелу мрежних ресурса између различитих компоненти апликације. Овај приступ се користи у OkHttp Dispatcher-у и сличним библиотекама за управљање pool-ом веза.

Кеширање HTTP одговора

Једноставни кешеви HTTP одговора на мобилним уређајима често користе FIFO. Одговори на захтјеве се чувају по редослиједу пристизања, а при достизању лимита бришу се најстарији. Иако би LRU дао бољи hit-ratio за корисничке сценарије, FIFO је једноставнији за имплементацију и не захтијева чување времена последњег приступа за сваки одговор. За API са равномјерним оптерећењем, разлика у hit-ratio између FIFO и LRU је минимална.

Обрада додирних догађаја

У мобилним апликацијама, додирни догађаји (touch events) се баферишу у FIFO реду прије препознавања гестикулација. Сваки догађај мора бити обрађен по редослиједу настанка, иначе ће гест бити погрешно препознат. FIFO Cache са ограничењем величине спречава препуњавање бафера при брзим превлачењима, одбацујући најстарије догађаје ако апликација не стиже да их обради.

Примјери кода FIFO Cache

Размотримо имплементацију FIFO Cache у Kotlin-у коришћењем кружног бафера — најефикаснијег приступа за мобилне уређаје.

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) {
            // уклони најстарији елемент
            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]
    }
}

Кружни бафер користи индексе head и tail, који се циклички повећавају по модулу maxSize. Када size == maxSize, enqueue прво уклања елемент под head (најстарији), помјера head, а затим уписује нови елемент под tail. Модуларна аритметика аутоматски враћа показиваче на почетак низа, искључујући ручно копирање података.

Имплементација у Swift-у кроз два стека

У Swift-у згодна алтернатива — FIFO ред на бази два стека (Two-Stack Queue). Све enqueue операције се извршавају у први стек (push), а при dequeue елементи се преносе у други стек обрнутим редом — тако dequeue операција постаје 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()
    }
}

Два стека обезбјеђују амортизовану сложеност O(1) за enqueue и dequeue. outStack.removeLast() при избацивању уклања најстарији елемент (први додани). Овај приступ не захтијева претходно додјељивање меморије, али може стварати додатно оптерећење на сакупљач отпада при честим обртањима стека. За мобилне апликације са ограниченом меморијом, кружни бафер остаје пожељнији.