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 е приложим само за стекове и операции за Отмяна. За повечето мобилни приложения 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() при изтласкване премахва най-стария елемент (първия добавен). Този подход не изисква предварително заделяне на памет, но може да създаде допълнително натоварване на събирача на отпадъци при чести обръщания на стека. За мобилни приложения с ограничена памет цикличният буфер остава за предпочитане.