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) {
            // evict oldest 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]
    }
}

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