FIFO Cache — mga pangunahing konsepto, algorithm ng pila at kung paano ito gumagana

Ano ang FIFO Cache?

FIFO Cache (First In First Out Cache) — cache na may nakapirming laki na gumagamit ng pila para pamahalaan ang mga elemento. Ang unang idinagdag na elemento ay nasa unahan ng pila at unang tatanggalin kapag umapaw. Ang mga bagong elemento ay palaging idinaragdag sa dulo, na tinitiyak na ang pagkakasunod-sunod ng pag-alis ay tumutugma sa pagkakasunod-sunod ng pagdaragdag.

Hindi tulad ng LRU, na muling nag-aayos ng mga elemento sa bawat pag-access, hindi binabago ng FIFO ang posisyon ng mga umiiral na elemento sa mga operasyong get. Ginagawa nitong ganap na deterministic ang algorithm: alam ang pagkakasunod-sunod ng pagdaragdag, maaaring tumpak na mahulaan kung aling elemento ang susunod na aalisin. Ang ganitong predictability ay kritikal para sa mga real-time system kung saan kailangang garantisado ang pagproseso ng data sa pagkakasunod-sunod ng pagdating.

Ang implementasyon ng FIFO Cache ay maaaring itayo sa ilang mga istruktura ng data: circular buffer para sa maximum na pagganap, naka-link na listahan para sa flexibility, o dalawang stack (Two-Stack Queue) para sa mga wikang walang built-in na pila. Ang circular buffer ay nagbibigay ng pinakamahusay na cache-locality at minimal na overhead, ngunit nangangailangan ng paunang paglalaan ng memorya para sa maxSize.

Mga pangunahing operasyon ng FIFO Cache

Ang operasyong enqueue(value) ay nagdaragdag ng elemento sa dulo ng pila. Kung ang laki ay umabot na sa maxSize, bago idagdag, ang elemento mula sa unahan ay tinatanggal. Ang operasyong dequeue() ay nag-aalis at nagbabalik ng elemento mula sa unahan — para sa sapilitang pagkuha ng pinakalumang elemento. Ang operasyong peek() ay nagbabalik ng elemento sa unahan nang hindi ito inaalis — para tingnan ang pinakalumang elemento nang hindi binabago ang pila.

Paano gumagana ang FIFO Cache

Ang algorithm na FIFO ay ginagaya ang pag-uugali ng isang ordinaryong pila: unang pumasok, unang pinaglilingkuran. Sa konteksto ng caching, nangangahulugan ito na ang elementong pinakamatagal na nasa cache ay tatanggalin kapag kulang ang espasyo — anuman ang kung gaano ito kailangan. Ang patakaran sa pag-alis ng FIFO ay hindi pinapansin ang dalas ng pag-access, na parehong lakas at kahinaan ng algorithm.

Sa implementasyon sa pamamagitan ng circular buffer, dalawang pointer ang ginagamit: head (index ng unahan ng pila) at tail (index ng dulo). Sa enqueue, ang elemento ay isinusulat sa index ng tail, at ang tail ay dinadagdagan. Kung ang tail ay umabot sa laki ng buffer, ito ay bumabalik sa simula ng array. Kung ang tail ay humabol sa head — puno na ang pila at ang head ay inililipat (pag-alis). Ang circular buffer ay hindi nangangailangan ng dynamic na paglalaan ng memorya at umiiwas sa fragmentation.

Ang FIFO Cache ay nagpapakita ng hit-ratio na 40% hanggang 60% para sa mga tipikal na karga, na mas mataas kaysa sa LIFO ngunit mas mababa kaysa sa LRU. Gayunpaman, para sa mga senaryo kung saan ang pag-access sa data ay pantay at walang mga mainit na punto, ang FIFO ay maaaring magpakita ng mga resulta na maihahambing sa LRU na may mas mababang kompleksidad ng implementasyon. Ang memorya ay ginagamit nang mahusay: hindi kailangan ng mga karagdagang pointer para sa muling pag-aayos ng mga elemento.

Problema ng polusyon sa cache

Ang pangunahing kahinaan ng FIFO — ang pagiging madaling kapitan sa polusyon ng cache (cache pollution). Kung ang isang malaking dami ng datos na hindi na kakailanganin ay idinagdag sa cache, unti-unti nilang aalisin ang lahat ng kapaki-pakinabang na elemento at ang hit-ratio ay babagsak nang husto. Ang LRU ay bahagyang nilulutas ang problemang ito, dahil ang mga madalas gamitin na elemento ay patuloy na nire-refresh sa pamamagitan ng paglipat sa unahan, habang ang mga isang-beses na elemento ay mas mabilis na inaalis. Sa FIFO, ang isang-beses na datos ay nananatili sa cache hanggang sa sila ay alisin sa natural na pagkakasunod-sunod ng pila.

Paghahambing ng FIFO, LRU at LIFO

Ang pagpili sa pagitan ng FIFO, LRU at LIFO ay depende sa pattern ng pag-access sa data at mga kinakailangan para sa predictability ng pag-uugali. Ang LRU ay optimal para sa karamihan ng mga senaryo, FIFO — para sa stream na datos na may pantay na pag-access, LIFO — para sa mga istruktura ng stack.

FIFO ay ideal para sa mga senaryo kung saan ang pagkakasunod-sunod ng pagproseso ay dapat tumugma sa pagkakasunod-sunod ng pagdating: buffering ng datos, pag-log, pagproseso ng mga kaganapan. LRU ay mas mahusay para sa caching na may hindi pantay na pag-access (datos ng gumagamit). LIFO ay naaangkop lamang para sa mga stack at operasyon ng Undo. Para sa karamihan ng mga mobile application, ang LRU ay nananatiling default na pagpipilian, ngunit ang FIFO ay maaaring mas gusto kapag may mahigpit na limitasyon sa memorya o mga kinakailangan sa predictability.

Saan ginagamit ang FIFO Cache

Ang FIFO Cache ay ginagamit sa mga senaryo kung saan mahalaga ang predictability ng pag-alis o ang pagkakasunod-sunod ng pagproseso ng datos. Tingnan natin ang mga pangunahing kaso ng paggamit.

Buffering ng stream na datos

Sa pag-playback ng audio at video, ang datos ay dumarating sa isang tuluy-tuloy na stream at pansamantalang iniimbak sa isang buffer. Tinitiyak ng FIFO Cache na ang mga unang fragment na natanggap ay unang ipapadala sa decoder — ito ay ginagarantiyahan ang maayos na playback nang walang pagkaantala. Ang laki ng buffer ay pinipili batay sa bitrate ng stream at pinapayagang pagkaantala: para sa audio karaniwang 2–5 segundo, para sa video — 10–30 segundo. Ang FIFO ay ideal para sa mga ganitong senaryo, dahil ang muling pag-aayos ng datos (tulad ng sa LRU) ay walang saysay.

Mga pila ng network request

Kapag nililimitahan ang bilang ng sabay-sabay na network request, ang FIFO Cache ay maaaring gamitin para sa pag-iimbak ng mga naghihintay na request. Ang unang idinagdag na request ay unang isasagawa, na tinitiyak ang patas na pamamahagi ng mga mapagkukunan ng network sa pagitan ng iba't ibang bahagi ng application. Ang pamamaraang ito ay ginagamit sa OkHttp Dispatcher at mga katulad na library para sa pamamahala ng pool ng koneksyon.

Caching ng mga tugon sa HTTP

Ang mga simpleng cache ng tugon sa HTTP sa mga mobile device ay kadalasang gumagamit ng FIFO. Ang mga tugon sa mga request ay iniimbak sa pagkakasunod-sunod ng pagdating, at kapag naabot ang limitasyon, ang mga pinakaluma ay tinatanggal. Kahit na ang LRU ay magbibigay ng mas mahusay na hit-ratio para sa mga senaryo ng gumagamit, ang FIFO ay mas simple na ipatupad at hindi nangangailangan ng pag-iimbak ng oras ng huling pag-access para sa bawat tugon. Para sa API na may pantay na karga, ang pagkakaiba sa hit-ratio sa pagitan ng FIFO at LRU ay minimal.

Pagproseso ng mga touch event

Sa mga mobile application, ang mga touch event ay naba-buffer sa isang FIFO na pila bago ang pagkilala ng kilos. Ang bawat kaganapan ay dapat iproseso sa pagkakasunod-sunod ng pangyayari, kung hindi, ang kilos ay makikilala nang mali. Ang FIFO Cache na may limitasyon sa laki ay pumipigil sa pag-apaw ng buffer sa mabilis na pag-swipe, itinatapon ang mga pinakalumang kaganapan kung ang application ay hindi makaproseso sa kanila.

Mga halimbawa ng code ng FIFO Cache

Tingnan natin ang implementasyon ng FIFO Cache sa Kotlin gamit ang circular buffer — ang pinakamahusay na pagganap na diskarte para sa mga mobile device.

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) {
            // tanggalin ang pinakalumang elemento
            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]
    }
}

Ang circular buffer ay gumagamit ng mga index na head at tail, na paikot na dinadagdagan modulo maxSize. Kapag size == maxSize, ang enqueue ay unang nag-aalis ng elemento sa head (pinakaluma), inililipat ang head, pagkatapos ay isinusulat ang bagong elemento sa tail. Ang modular arithmetic ay awtomatikong bumabalot ng mga pointer pabalik sa simula ng array, na inaalis ang manu-manong pagkopya ng datos.

Implementasyon sa Swift sa pamamagitan ng dalawang stack

Sa Swift, isang maginhawang alternatibo — FIFO na pila batay sa dalawang stack (Two-Stack Queue). Lahat ng enqueue ay ginagawa sa unang stack (push), at sa dequeue, ang mga elemento ay inililipat sa pangalawang stack sa baligtad na pagkakasunod-sunod — kaya ang operasyong dequeue ay nagiging O(1) sa karaniwan.

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

Dalawang stack ay nagbibigay ng amortized na kompleksidad na O(1) para sa enqueue at dequeue. outStack.removeLast() sa pag-alis ay tinatanggal ang pinakalumang elemento (unang idinagdag). Ang diskarteng ito ay hindi nangangailangan ng paunang paglalaan ng memorya, ngunit maaaring lumikha ng karagdagang karga sa garbage collector sa madalas na pagbabaligtad ng stack. Para sa mga mobile application na may limitadong memorya, ang circular buffer ay nananatiling mas gusto.