FIFO Cache — Key Concepts, Queue Algorithm and How It Works

What is FIFO Cache?

FIFO Cache (First In First Out Cache) is a fixed-size cache that uses a queue to manage elements. The first added element is placed at the head of the queue and will be the first to be removed when overflow occurs. New elements are always added to the tail, ensuring that the eviction order matches the addition order.

Unlike LRU, which reorders elements on every access, FIFO does not change the position of existing elements on get requests. This makes the algorithm completely deterministic: knowing the addition order, one can accurately predict which element will be evicted next. This predictability is critical for real-time systems where data must be processed in order of arrival.

A FIFO Cache implementation can be built on several data structures: a circular buffer for maximum performance, a linked list for flexibility, or two stacks (Two-Stack Queue) for languages without a built-in queue. The circular buffer provides the best cache locality and minimal overhead but requires pre-allocation of memory for maxSize.

Basic FIFO Cache Operations

The enqueue(value) operation adds an element to the tail of the queue. If the size reaches maxSize, the element at the head is removed before addition. The dequeue() operation removes and returns the element at the head — for forced extraction of the oldest element. The peek() operation returns the head element without removal — for viewing the oldest element without modifying the queue.

How FIFO Cache Works

The FIFO algorithm mimics the behavior of a regular queue: first in, first served. In the context of caching, this means that the element that has been in the cache the longest will be removed when space is needed — regardless of how popular it is. The eviction policy of FIFO ignores access frequency, which is both a strength and a weakness of the algorithm.

When implemented via a circular buffer, two pointers are used: head (index of the queue head) and tail (index of the tail). On enqueue, the element is written at the tail index, and tail is incremented. If tail reaches the buffer size, it wraps around to the beginning of the array. If tail catches up to head, the queue is full, and head is shifted (eviction). The circular buffer does not require dynamic memory allocation and avoids fragmentation.

FIFO Cache demonstrates a hit-ratio of 40% to 60% for typical workloads, which is higher than LIFO but lower than LRU. However, for scenarios where data access is uniform and has no hot spots, FIFO can show results comparable to LRU with significantly lower implementation complexity. Memory is used efficiently: no additional pointers for element reordering are needed.

The Cache Pollution Problem

The main drawback of FIFO is susceptibility to cache pollution. If a large amount of data that will never be needed again is added to the cache, it will gradually evict all useful elements, and the hit-ratio will drop sharply. LRU partially solves this problem because frequently used elements are constantly refreshed by being moved to the head, while one-time data is evicted faster. In FIFO, one-time data remains in the cache until it is evicted naturally by the queue order.

Comparison of FIFO, LRU and LIFO

The choice between FIFO, LRU and LIFO depends on the data access pattern and requirements for behavioral predictability. LRU is optimal for most scenarios, FIFO for streaming data with uniform access, and LIFO for stack structures.

FIFO is ideal for scenarios where processing order must match arrival order: data buffering, logging, event processing. LRU is better for caching with uneven access (user data). LIFO is only applicable for stacks and Undo. For most mobile applications, LRU remains the default choice, but FIFO may be preferable under strict memory constraints or predictability requirements.

Where FIFO Cache is Used

FIFO Cache finds application in scenarios where eviction predictability or data processing order matters. Let us examine the main use cases.

Streaming Data Buffering

When playing audio and video, data arrives in a continuous stream and is temporarily stored in a buffer. FIFO Cache ensures that the first received fragments are the first sent for decoding — this guarantees smooth playback without delays. The buffer size is chosen based on the stream bitrate and acceptable delay: typically 2–5 seconds for audio, 10–30 seconds for video. FIFO is ideal for such scenarios since data reordering (as in LRU) is meaningless.

Network Request Queues

When limiting the number of simultaneous network requests, FIFO Cache can be used to store pending requests. The first added request will be executed first, ensuring fair distribution of network resources among different application components. This approach is used in OkHttp Dispatcher and similar libraries for connection pool management.

HTTP Response Caching

Simple HTTP response caches on mobile devices often use FIFO. Responses to requests are stored in order of arrival, and when the limit is reached, the oldest ones are removed. Although LRU would give a better hit-ratio for user scenarios, FIFO is simpler to implement and does not require storing the last access time for each response. For APIs with uniform load, the difference in hit-ratio between FIFO and LRU is minimal.

Touch Event Processing

In mobile applications, touch events are buffered in a FIFO queue before gesture processing. Each event must be processed in the order it occurred, otherwise the gesture will be recognized incorrectly. A FIFO Cache with size limit prevents buffer overflow during fast swipes by discarding the oldest events if the application cannot keep up.

FIFO Cache Code Examples

Let us look at a FIFO Cache implementation in Kotlin using a circular buffer — the most performant approach for mobile devices.

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]
    }
}

The circular buffer uses head and tail indices that cyclically increment by modulo maxSize. When size == maxSize, enqueue first removes the element at head (the oldest), shifts head, and then writes the new element at tail. Modular arithmetic automatically wraps the pointers to the beginning of the array, eliminating manual data copying.

Swift Implementation via Two Stacks

In Swift, a convenient alternative is a FIFO queue based on two stacks (Two-Stack Queue). All enqueue operations go to the first stack (push), and during dequeue, elements are transferred to the second stack in reverse order — making dequeue O(1) on average.

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

Two stacks provide amortized O(1) complexity for enqueue and dequeue. outStack.removeLast() during eviction removes the oldest element (the first added). This approach does not require pre-allocation of memory but may create additional garbage collection overhead during frequent stack reversals. For mobile applications with limited memory, the circular buffer remains more preferable.