FIFO Cache — konsep kunci, algoritme antrean dan cara kerjanya

Apa itu FIFO Cache?

FIFO Cache (First In First Out Cache) — cache berukuran tetap yang menggunakan antrean untuk mengelola elemen. Elemen pertama yang ditambahkan berada di kepala antrean dan akan dihapus pertama saat terjadi overflow. Elemen baru selalu ditambahkan ke ekor, memastikan bahwa urutan penghapusan sesuai dengan urutan penambahan.

Tidak seperti LRU yang mengurutkan ulang elemen pada setiap akses, FIFO tidak mengubah posisi elemen yang ada pada operasi get. Ini membuat algoritme sepenuhnya deterministik: mengetahui urutan penambahan, dapat diprediksi secara tepat elemen mana yang akan dihapus berikutnya. Prediktabilitas semacam ini sangat penting untuk sistem real-time di mana pemrosesan data harus dijamin dalam urutan kedatangan.

Implementasi FIFO Cache dapat dibangun di atas beberapa struktur data: buffer melingkar (circular buffer) untuk kinerja maksimal, linked list untuk fleksibilitas, atau dua stack (Two-Stack Queue) untuk bahasa tanpa antrean bawaan. Buffer melingkar memberikan cache-lokalitas terbaik dan overhead minimal, tetapi memerlukan alokasi memori awal untuk maxSize.

Operasi dasar FIFO Cache

Operasi enqueue(value) menambahkan elemen ke ekor antrean. Jika ukuran telah mencapai maxSize, sebelum penambahan, elemen dari kepala dihapus. Operasi dequeue() menghapus dan mengembalikan elemen dari kepala — untuk pengambilan paksa elemen tertua. Operasi peek() mengembalikan elemen kepala tanpa penghapusan — untuk melihat elemen tertua tanpa mengubah antrean.

Bagaimana FIFO Cache bekerja

Algoritme FIFO meniru perilaku antrean biasa: pertama masuk, pertama dilayani. Dalam konteks caching, ini berarti elemen yang paling lama berada di cache akan dihapus saat kekurangan tempat — terlepas dari seberapa dibutuhkannya. Kebijakan penghapusan FIFO mengabaikan frekuensi akses, yang merupakan kekuatan sekaligus kelemahan algoritme.

Dalam implementasi dengan buffer melingkar, dua pointer digunakan: head (indeks kepala antrean) dan tail (indeks ekor). Saat enqueue, elemen ditulis pada indeks tail, dan tail ditingkatkan. Jika tail mencapai ukuran buffer, ia kembali ke awal array. Jika tail menyusul head — antrean penuh dan head digeser (penghapusan). Buffer melingkar tidak memerlukan alokasi memori dinamis dan menghindari fragmentasi.

FIFO Cache menunjukkan hit-ratio 40% hingga 60% untuk beban tipikal, lebih tinggi dari LIFO tetapi lebih rendah dari LRU. Namun, untuk skenario di mana akses ke data seragam dan tidak ada titik panas, FIFO dapat menunjukkan hasil yang sebanding dengan LRU dengan kompleksitas implementasi yang jauh lebih rendah. Memori digunakan secara efisien: tidak diperlukan pointer tambahan untuk mengatur ulang elemen.

Masalah polusi cache

Kekurangan utama FIFO — kerentanan terhadap polusi cache (cache pollution). Jika sejumlah besar data yang tidak akan pernah diperlukan lagi ditambahkan ke cache, mereka secara bertahap akan menghapus semua elemen yang berguna dan hit-ratio akan turun drastis. LRU sebagian memecahkan masalah ini, karena elemen yang sering digunakan akan terus disegarkan dengan dipindahkan ke kepala, sementara elemen sekali pakai akan dihapus lebih cepat. Dalam FIFO, data sekali pakai tetap berada di cache sampai dihapus dalam urutan alami antrean.

Perbandingan FIFO, LRU dan LIFO

Pilihan antara FIFO, LRU dan LIFO tergantung pada pola akses data dan persyaratan prediktabilitas perilaku. LRU optimal untuk sebagian besar skenario, FIFO — untuk data aliran dengan akses seragam, LIFO — untuk struktur stack.

FIFO ideal untuk skenario di mana urutan pemrosesan harus sesuai dengan urutan kedatangan: buffering data, pencatatan log, pemrosesan peristiwa. LRU lebih baik untuk caching dengan akses tidak merata (data pengguna). LIFO hanya berlaku untuk stack dan operasi Undo. Untuk sebagian besar aplikasi seluler, LRU tetap menjadi pilihan standar, tetapi FIFO mungkin lebih disukai saat ada batasan memori yang ketat atau persyaratan prediktabilitas.

Di mana FIFO Cache digunakan

FIFO Cache diterapkan dalam skenario di mana prediktabilitas penghapusan atau urutan pemrosesan data penting. Mari kita lihat kasus penggunaan utama.

Buffering data aliran

Saat memutar audio dan video, data datang dalam aliran berkelanjutan dan disimpan sementara di buffer. FIFO Cache memastikan bahwa fragmen pertama yang diterima akan menjadi yang pertama dikirim ke decoder — ini menjamin pemutaran yang lancar tanpa penundaan. Ukuran buffer dipilih berdasarkan bitrate aliran dan penundaan yang diizinkan: untuk audio biasanya 2–5 detik, untuk video — 10–30 detik. FIFO ideal untuk skenario seperti itu, karena pengurutan ulang data (seperti di LRU) tidak masuk akal.

Antrean permintaan jaringan

Saat membatasi jumlah permintaan jaringan bersamaan, FIFO Cache dapat digunakan untuk menyimpan permintaan yang menunggu. Permintaan pertama yang ditambahkan akan dieksekusi pertama, memastikan distribusi yang adil dari sumber daya jaringan antara berbagai komponen aplikasi. Pendekatan ini digunakan di OkHttp Dispatcher dan pustaka serupa untuk mengelola kumpulan koneksi.

Caching respons HTTP

Cache respons HTTP sederhana pada perangkat seluler sering menggunakan FIFO. Respons terhadap permintaan disimpan dalam urutan kedatangan, dan saat mencapai batas, yang tertua dihapus. Meskipun LRU akan memberikan hit-ratio yang lebih baik untuk skenario pengguna, FIFO lebih sederhana untuk diimplementasikan dan tidak memerlukan penyimpanan waktu akses terakhir untuk setiap respons. Untuk API dengan beban seragam, perbedaan hit-ratio antara FIFO dan LRU minimal.

Pemrosesan peristiwa sentuh

Dalam aplikasi seluler, peristiwa sentuh (touch events) di-buffer dalam antrean FIFO sebelum pengenalan gerakan. Setiap peristiwa harus diproses dalam urutan kejadiannya, jika tidak, gerakan akan dikenali secara salah. FIFO Cache dengan batasan ukuran mencegah overflow buffer pada gesekan cepat, membuang peristiwa tertua jika aplikasi tidak dapat memprosesnya.

Contoh kode FIFO Cache

Mari kita lihat implementasi FIFO Cache di Kotlin menggunakan buffer melingkar — pendekatan paling berkinerja untuk perangkat seluler.

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) {
            // hapus elemen tertua
            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]
    }
}

Buffer melingkar menggunakan indeks head dan tail, yang ditingkatkan secara siklik modulo maxSize. Ketika size == maxSize, enqueue terlebih dahulu menghapus elemen di head (tertua), menggeser head, kemudian menulis elemen baru di tail. Aritmetika modular secara otomatis membungkus pointer kembali ke awal array, menghilangkan penyalinan data manual.

Implementasi di Swift melalui dua stack

Di Swift, alternatif yang nyaman — antrean FIFO berbasis dua stack (Two-Stack Queue). Semua enqueue dilakukan di stack pertama (push), dan saat dequeue, elemen dipindahkan ke stack kedua dalam urutan terbalik — sehingga operasi dequeue menjadi O(1) rata-rata.

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

Dua stack memberikan kompleksitas amortisasi O(1) untuk enqueue dan dequeue. outStack.removeLast() saat penghapusan menghapus elemen tertua (pertama ditambahkan). Pendekatan ini tidak memerlukan alokasi memori awal, tetapi dapat menciptakan beban tambahan pada garbage collector saat pembalikan stack yang sering. Untuk aplikasi seluler dengan memori terbatas, buffer melingkar tetap lebih disukai.