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 та аналогічних бібліотеках для керування пулом з'єднань.

Кешування 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() при витісненні видаляє найстаріший елемент (перший доданий). Цей підхід не вимагає попереднього виділення пам'яті, але може створювати додаткове навантаження на збирач сміття при частих реверсах стеку. Для мобільних додатків з обмеженою пам'яттю кільцевий буфер залишається більш кращим.