FIFO Cache — temel kavramlar, kuyruk algoritması ve nasıl çalıştığı

FIFO Cache Nedir?

FIFO Cache (First In First Out Cache), öğeleri yönetmek için bir kuyruk kullanan sabit boyutlu bir önbellektir. İlk eklenen öğe kuyruğun başına yerleştirilir ve taşma olduğunda ilk kaldırılan olacaktır. Yeni öğeler her zaman kuyruğa eklenir ve kaldırma sırasının ekleme sırasıyla eşleşmesi sağlanır.

Her erişimde öğeleri yeniden sıralayan LRU'nun aksine, FIFO get isteklerinde mevcut öğelerin konumunu değiştirmez. Bu, algoritmayı tamamen deterministik yapar: ekleme sırası bilindiğinde, bir sonraki hangi öğenin kaldırılacağı doğru bir şekilde tahmin edilebilir. Bu öngörülebilirlik, verilerin varış sırasına göre işlenmesi gereken gerçek zamanlı sistemler için kritiktir.

FIFO Cache uygulaması birkaç veri yapısı üzerine inşa edilebilir: maksimum performans için dairesel tampon, esneklik için bağlantılı liste veya yerleşik kuyruğu olmayan diller için iki yığın (İki Yığınlı Kuyruk). Dairesel tampon en iyi önbellek yerelliğini ve minimum ek yükü sağlar, ancak maxSize için önceden bellek ayrılması gerektirir.

FIFO Cache Temel İşlemleri

enqueue(value) işlemi kuyruğa bir öğe ekler. Boyut maxSize'a ulaşırsa, eklemeden önce baştaki öğe kaldırılır. dequeue() işlemi baştaki öğeyi kaldırır ve döndürür — en eski öğenin zorla çıkarılması için. peek() işlemi kaldırmadan baştaki öğeyi döndürür — kuyruğu değiştirmeden en eski öğeyi görüntülemek için.

FIFO Cache Nasıl Çalışır

FIFO algoritması normal bir kuyruğun davranışını taklit eder: ilk gelen ilk hizmet alır. Önbellekleme bağlamında bu, önbellekte en uzun süre kalan öğenin, popülerliğine bakılmaksızın, alan gerektiğinde kaldırılacağı anlamına gelir. FIFO'nun çıkarma politikası erişim sıklığını yok sayar, bu algoritmanın hem gücü hem de zayıflığıdır.

Dairesel tampon ile uygulandığında, iki işaretçi kullanılır: head (kuyruk başı dizini) ve tail (kuyruk sonu dizini). enqueue sırasında, öğe tail dizinine yazılır ve tail artırılır. Tail tampon boyutuna ulaşırsa, dizinin başına sarılır. Tail head'i yakalarsa, kuyruk doludur ve head kaydırılır (çıkarma). Dairesel tampon dinamik bellek ayırma gerektirmez ve parçalanmayı önler.

FIFO Cache, tipik iş yükleri için %40 ile %60 arasında bir hit-ratio gösterir; bu LIFO'dan yüksek ancak LRU'dan düşüktür. Bununla birlikte, veri erişiminin tekdüze olduğu ve sıcak noktaların bulunmadığı senaryolarda FIFO, önemli ölçüde daha düşük uygulama karmaşıklığı ile LRU'ya benzer sonuçlar gösterebilir. Bellek verimli kullanılır: öğelerin yeniden sıralanması için ek işaretçilere gerek yoktur.

Önbellek Kirliliği Sorunu

FIFO'nun ana dezavantajı, önbellek kirliliğine yatkınlığıdır. Bir daha asla ihtiyaç duyulmayacak büyük miktarda veri önbelleğe eklenirse, kademeli olarak tüm yararlı öğeleri çıkarır ve hit-ratio keskin bir şekilde düşer. LRU bu sorunu kısmen çözer çünkü sık kullanılan öğeler başa taşınarak sürekli tazelenirken, tek kullanımlık veriler daha hızlı çıkarılır. FIFO'da tek kullanımlık veriler, kuyruk sırasına göre doğal olarak çıkarılana kadar önbellekte kalır.

FIFO, LRU ve LIFO Karşılaştırması

FIFO, LRU ve LIFO arasındaki seçim, veri erişim modeline ve davranışsal öngörülebilirlik gereksinimlerine bağlıdır. LRU çoğu senaryo için en uygunudur, FIFO tekdüze erişimli akış verileri için ve LIFO yığın yapıları için uygundur.

FIFO, işleme sırasının varış sırasıyla eşleşmesi gereken senaryolar için idealdir: veri tamponlama, günlükleme, olay işleme. LRU, düzensiz erişimli (kullanıcı verileri) önbellekleme için daha iyidir. LIFO yalnızca yığınlar ve Geri Al için uygulanabilir. Çoğu mobil uygulama için LRU varsayılan seçim olmaya devam eder, ancak sıkı bellek kısıtlamaları veya öngörülebilirlik gereksinimleri altında FIFO tercih edilebilir.

FIFO Cache Nerelerde Kullanılır

FIFO Cache, çıkarma öngörülebilirliğinin veya veri işleme sırasının önemli olduğu senaryolarda uygulama bulur. Ana kullanım durumlarını inceleyelim.

Akış Verisi Tamponlama

Ses ve video oynatırken, veriler sürekli bir akış halinde gelir ve geçici olarak bir tamponda depolanır. FIFO Cache, ilk alınan parçaların kod çözme için ilk gönderilenler olmasını sağlar — bu gecikmesiz kesintisiz oynatmayı garanti eder. Tampon boyutu akış bit hızına ve kabul edilebilir gecikmeye göre seçilir: ses için tipik olarak 2–5 saniye, video için 10–30 saniye. FIFO bu tür senaryolar için idealdir çünkü veri yeniden sıralamanın (LRU'daki gibi) bir anlamı yoktur.

Ağ İstek Kuyrukları

Eşzamanlı ağ isteklerinin sayısını sınırlarken, FIFO Cache bekleyen istekleri depolamak için kullanılabilir. İlk eklenen istek ilk yürütülür ve uygulamanın farklı bileşenleri arasında ağ kaynaklarının adil dağıtımını sağlar. Bu yaklaşım, bağlantı havuzu yönetimi için OkHttp Dispatcher ve benzer kitaplıklarda kullanılır.

HTTP Yanıt Önbellekleme

Mobil cihazlardaki basit HTTP yanıt önbellekleri genellikle FIFO kullanır. İsteklere verilen yanıtlar varış sırasına göre depolanır ve sınıra ulaşıldığında en eskileri kaldırılır. LRU kullanıcı senaryoları için daha iyi bir hit-ratio sağlasa da, FIFO uygulaması daha basittir ve her yanıt için son erişim zamanını depolamayı gerektirmez. Tekdüze yüke sahip API'ler için FIFO ve LRU arasındaki hit-ratio farkı minimumdur.

Dokunmatik Olay İşleme

Mobil uygulamalarda, dokunmatik olaylar jest işlemeden önce bir FIFO kuyruğunda tamponlanır. Her olay meydana geldiği sırayla işlenmelidir, aksi takdirde jest yanlış tanınır. Boyut sınırı olan bir FIFO Cache, hızlı kaydırmalar sırasında tampon taşmasını önler ve uygulama yetişemezse en eski olayları atar.

FIFO Cache Kod Örnekleri

Mobil cihazlar için en verimli yaklaşım olan dairesel tampon kullanarak Kotlin'de bir FIFO Cache uygulamasına bakalım.

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) {
            // en eski öğeyi kaldır
            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]
    }
}

Dairesel tampon, maxSize modülüne göre döngüsel olarak artan head ve tail indekslerini kullanır. size == maxSize olduğunda, enqueue önce head'deki öğeyi (en eski) kaldırır, head'i kaydırır ve ardından tail'e yeni öğeyi yazar. Modüler aritmetik, işaretçileri otomatik olarak dizinin başına sarar ve manuel veri kopyalamayı ortadan kaldırır.

İki Yığın ile Swift Uygulaması

Swift'te kullanışlı bir alternatif, iki yığına dayalı bir FIFO kuyruğudur (İki Yığınlı Kuyruk). Tüm enqueue işlemleri ilk yığına (push) gider ve dequeue sırasında öğeler ters sırada ikinci yığına aktarılır — bu dequeue'yi ortalama olarak O(1) yapar.

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

İki yığın, enqueue ve dequeue için amortize edilmiş O(1) karmaşıklığı sağlar. Çıkarma sırasında outStack.removeLast() en eski öğeyi (ilk eklenen) kaldırır. Bu yaklaşım önceden bellek ayırmayı gerektirmez ancak sık yığın ters çevirmeleri sırasında çöp toplayıcıda ek yük oluşturabilir. Sınırlı belleğe sahip mobil uygulamalar için dairesel tampon daha tercih edilir olmaya devam eder.