FIFO Cache — kluczowe pojęcia, algorytm kolejki i jak działa

Czym jest FIFO Cache?

FIFO Cache (First In First Out Cache) — to bufor o stałym rozmiarze wykorzystujący kolejkę do zarządzania elementami. Pierwszy dodany element znajduje się na początku kolejki i zostanie usunięty jako pierwszy w przypadku przepełnienia. Nowe elementy są zawsze dodawane na końcu, co gwarantuje, że kolejność usuwania jest zgodna z kolejnością dodawania.

W przeciwieństwie do LRU, który zmienia kolejność elementów przy każdym dostępie, FIFO nie zmienia pozycji istniejących elementów przy operacjach get. To czyni algorytm w pełni deterministycznym: znając kolejność dodawania, można dokładnie przewidzieć, który element zostanie usunięty jako następny. Taka przewidywalność jest kluczowa dla systemów czasu rzeczywistego, gdzie trzeba zagwarantować przetwarzanie danych w kolejności napływania.

Implementacja FIFO Cache może być zbudowana na kilku strukturach danych: buforze cyklicznym (circular buffer) dla maksymalnej wydajności, liście połączonej dla elastyczności lub dwóch stosach (Two-Stack Queue) dla języków bez wbudowanej kolejki. Bufor cykliczny zapewnia najlepszą lokalność pamięci podręcznej i minimalny narzut, ale wymaga wcześniejszego przydzielenia pamięci dla maxSize.

Podstawowe operacje FIFO Cache

Operacja enqueue(value) dodaje element na koniec kolejki. Jeśli rozmiar osiągnął maxSize, przed dodaniem usuwany jest element z początku. Operacja dequeue() usuwa i zwraca element z początku — do wymuszonego pobrania najstarszego elementu. Operacja peek() zwraca element z początku bez usuwania — do podglądu najstarszego elementu bez zmiany kolejki.

Jak działa FIFO Cache

Algorytm FIFO naśladuje zachowanie zwykłej kolejki: pierwszy w kolejce jest obsługiwany jako pierwszy. W kontekście buforowania oznacza to, że element znajdujący się w buforze najdłużej zostanie usunięty w przypadku braku miejsca — niezależnie od tego, jak bardzo jest potrzebny. Polityka usuwania FIFO ignoruje częstotliwość użycia, co jest jednocześnie mocną i słabą stroną algorytmu.

W implementacji przez bufor cykliczny używane są dwa wskaźniki: head (indeks początku kolejki) i tail (indeks końca). Przy enqueue element zapisywany jest pod indeksem tail, a tail jest zwiększany. Jeśli tail osiągnie rozmiar bufora, jest zawijany na początek tablicy. Jeśli tail dogoni head — kolejka jest pełna, a head przesuwany (usunięcie). Bufor cykliczny nie wymaga dynamicznego przydzielania pamięci i zapobiega fragmentacji.

FIFO Cache osiąga współczynnik trafień od 40% do 60% dla typowych obciążeń, co jest wyższe niż LIFO, ale niższe niż LRU. Jednak w scenariuszach, gdzie dostęp do danych jest równomierny i nie występują „gorące” punkty, FIFO może osiągać wyniki porównywalne z LRU przy znacznie mniejszej złożoności implementacji. Pamięć jest wykorzystywana efektywnie: nie są potrzebne dodatkowe wskaźniki do przestawiania elementów.

Problem zanieczyszczenia bufora

Główną wadą FIFO jest podatność na zanieczyszczenie bufora (cache pollution). Jeśli do bufora dodana zostanie duża ilość danych, które nigdy więcej nie będą potrzebne, stopniowo usuną one wszystkie użyteczne elementy, a współczynnik trafień gwałtownie spadnie. LRU częściowo rozwiązuje ten problem, ponieważ często używane elementy będą stale „odświeżane” poprzez przenoszenie na początek, a jednorazowe będą usuwane szybciej. W FIFO jednorazowe dane pozostają w buforze aż do naturalnego usunięcia w kolejności kolejki.

Porównanie FIFO, LRU i LIFO

Wybór między FIFO, LRU i LIFO zależy od wzorca dostępu do danych i wymagań dotyczących przewidywalności zachowania. LRU jest optymalny dla większości scenariuszy, FIFO — dla danych strumieniowych z równomiernym dostępem, LIFO — dla struktur stosowych.

FIFO jest idealny do scenariuszy, gdzie kolejność przetwarzania musi być zgodna z kolejnością napływania: buforowanie danych, logowanie, przetwarzanie zdarzeń. LRU jest lepszy do buforowania z nierównomiernym dostępem (dane użytkowników). LIFO ma zastosowanie tylko dla stosów i operacji Cofnij. Dla większości aplikacji mobilnych LRU pozostaje domyślnym wyborem, ale FIFO może być preferowany przy ścisłych ograniczeniach pamięci lub wymaganiach dotyczących przewidywalności.

Gdzie stosuje się FIFO Cache

FIFO Cache znajduje zastosowanie w scenariuszach, gdzie ważna jest przewidywalność usuwania lub kolejność przetwarzania danych. Rozważmy główne przypadki użycia.

Buforowanie danych strumieniowych

Podczas odtwarzania audio i video dane docierają ciągłym strumieniem i są tymczasowo przechowywane w buforze. FIFO Cache zapewnia, że pierwsze otrzymane fragmenty zostaną wysłane jako pierwsze do dekodowania — gwarantuje to płynne odtwarzanie bez opóźnień. Rozmiar bufora jest dobierany na podstawie przepływności strumienia i dopuszczalnego opóźnienia: dla audio typowo 2–5 sekund, dla wideo — 10–30 sekund. FIFO jest idealny do takich scenariuszy, ponieważ zmiana kolejności danych (jak w LRU) nie ma sensu.

Kolejki zapytań sieciowych

Przy ograniczeniu liczby jednoczesnych zapytań sieciowych FIFO Cache może być używany do przechowywania oczekujących zapytań. Pierwsze dodane zapytanie zostanie wykonane jako pierwsze, co zapewnia uczciwy podział zasobów sieci między różnymi komponentami aplikacji. Takie podejście jest stosowane w OkHttp Dispatcher i podobnych bibliotekach do zarządzania pulą połączeń.

Buforowanie odpowiedzi HTTP

Proste bufory odpowiedzi HTTP na urządzeniach mobilnych często używają FIFO. Odpowiedzi na zapytania są zapisywane w kolejności napływania, a po osiągnięciu limitu usuwane są najstarsze. Chociaż LRU zapewniłby lepszy współczynnik trafień w scenariuszach użytkownika, FIFO jest prostszy w implementacji i nie wymaga przechowywania czasu ostatniego dostępu dla każdej odpowiedzi. Dla API z równomiernym obciążeniem różnica we współczynniku trafień między FIFO a LRU jest minimalna.

Przetwarzanie zdarzeń dotykowych

W aplikacjach mobilnych zdarzenia dotykowe (touch events) są buforowane w kolejce FIFO przed rozpoznaniem gestów. Każde zdarzenie musi być przetworzone w kolejności występowania, w przeciwnym razie gest zostanie rozpoznany nieprawidłowo. FIFO Cache z ograniczeniem rozmiaru zapobiega przepełnieniu bufora przy szybkich przesunięciach, odrzucając najstarsze zdarzenia, jeśli aplikacja nie nadąża z ich przetwarzaniem.

Przykłady kodu FIFO Cache

Rozważmy implementację FIFO Cache w Kotlin z wykorzystaniem bufora cyklicznego — najbardziej wydajnego podejścia dla urządzeń mobilnych.

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) {
            // usuń najstarszy element
            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]
    }
}

Bufor cykliczny używa indeksów head i tail, które są cyklicznie inkrementowane modulo maxSize. Gdy size == maxSize, enqueue najpierw usuwa element pod head (najstarszy), przesuwa head, a następnie zapisuje nowy element pod tail. Arytmetyka modularna automatycznie zawija wskaźniki na początek tablicy, eliminując ręczne kopiowanie danych.

Implementacja w Swift przez dwa stosy

W Swift wygodną alternatywą jest kolejka FIFO oparta na dwóch stosach (Two-Stack Queue). Wszystkie enqueue wykonują push do pierwszego stosu, a przy dequeue elementy są przenoszone do drugiego stosu w odwrotnej kolejności — dzięki temu operacja dequeue osiąga O(1) średnio.

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

Dwa stosy zapewniają amortyzowaną złożoność O(1) dla enqueue i dequeue. outStack.removeLast() przy usuwaniu usuwa najstarszy element (pierwszy dodany). To podejście nie wymaga wcześniejszego przydzielania pamięci, ale może powodować dodatkowe obciążenie garbage collectora przy częstych odwracaniach stosu. Dla aplikacji mobilnych z ograniczoną pamięcią bufor cykliczny pozostaje bardziej preferowany.