FIFO Cache — conceptos clave, algoritmo de cola y cómo funciona

¿Qué es FIFO Cache?

FIFO Cache (First In First Out Cache) es una caché de tamaño fijo que utiliza una cola para gestionar los elementos. El primer elemento añadido se coloca al principio de la cola y será el primero en eliminarse cuando se produzca un desbordamiento. Los nuevos elementos siempre se añaden al final, lo que garantiza que el orden de eliminación coincida con el orden de adición.

A diferencia de LRU, que reordena los elementos en cada acceso, FIFO no cambia la posición de los elementos existentes en las solicitudes get. Esto hace que el algoritmo sea completamente determinista: conociendo el orden de adición, se puede predecir con precisión qué elemento será el próximo en eliminarse. Esta previsibilidad es crítica para los sistemas de tiempo real donde los datos deben procesarse en orden de llegada.

Una implementación de FIFO Cache puede construirse sobre varias estructuras de datos: un búfer circular para máximo rendimiento, una lista enlazada para flexibilidad, o dos pilas (cola de dos pilas) para lenguajes sin cola incorporada. El búfer circular proporciona la mejor localidad de caché y una sobrecarga mínima, pero requiere preasignación de memoria para maxSize.

Operaciones básicas de FIFO Cache

La operación enqueue(value) añade un elemento al final de la cola. Si el tamaño alcanza maxSize, el elemento de la cabeza se elimina antes de la adición. La operación dequeue() elimina y devuelve el elemento de la cabeza — para la extracción forzada del elemento más antiguo. La operación peek() devuelve el elemento de la cabeza sin eliminarlo — para ver el elemento más antiguo sin modificar la cola.

Cómo funciona FIFO Cache

El algoritmo FIFO imita el comportamiento de una cola normal: primero en entrar, primero en ser atendido. En el contexto del almacenamiento en caché, esto significa que el elemento que ha estado más tiempo en la caché será eliminado cuando se necesite espacio, independientemente de su popularidad. La política de eliminación de FIFO ignora la frecuencia de acceso, lo que es tanto una fortaleza como una debilidad del algoritmo.

Cuando se implementa mediante un búfer circular, se utilizan dos punteros: head (índice de la cabeza de la cola) y tail (índice de la cola). Al hacer enqueue, el elemento se escribe en el índice tail y tail se incrementa. Si tail alcanza el tamaño del búfer, se envuelve al principio del array. Si tail alcanza a head, la cola está llena y head se desplaza (eliminación). El búfer circular no requiere asignación dinámica de memoria y evita la fragmentación.

FIFO Cache demuestra un hit-ratio del 40% al 60% para cargas de trabajo típicas, que es más alto que LIFO pero más bajo que LRU. Sin embargo, para escenarios donde el acceso a los datos es uniforme y no tiene puntos calientes, FIFO puede mostrar resultados comparables a LRU con una complejidad de implementación significativamente menor. La memoria se utiliza de manera eficiente: no se necesitan punteros adicionales para la reordenación de elementos.

El problema de la contaminación de la caché

El principal inconveniente de FIFO es la susceptibilidad a la contaminación de la caché. Si se añade a la caché una gran cantidad de datos que nunca más se necesitarán, irán eliminando gradualmente todos los elementos útiles y el hit-ratio caerá drásticamente. LRU resuelve parcialmente este problema porque los elementos utilizados con frecuencia se refrescan constantemente al moverse a la cabeza, mientras que los datos de un solo uso se eliminan más rápido. En FIFO, los datos de un solo uso permanecen en la caché hasta que se eliminan de forma natural por el orden de la cola.

Comparación de FIFO, LRU y LIFO

La elección entre FIFO, LRU y LIFO depende del patrón de acceso a los datos y de los requisitos de previsibilidad del comportamiento. LRU es óptimo para la mayoría de los escenarios, FIFO para datos en flujo con acceso uniforme y LIFO para estructuras de pila.

FIFO es ideal para escenarios donde el orden de procesamiento debe coincidir con el orden de llegada: almacenamiento en búfer de datos, registro, procesamiento de eventos. LRU es mejor para el almacenamiento en caché con acceso desigual (datos de usuario). LIFO solo es aplicable para pilas y Deshacer. Para la mayoría de las aplicaciones móviles, LRU sigue siendo la opción por defecto, pero FIFO puede ser preferible bajo restricciones estrictas de memoria o requisitos de previsibilidad.

Dónde se utiliza FIFO Cache

FIFO Cache encuentra aplicación en escenarios donde la previsibilidad de la eliminación o el orden de procesamiento de los datos son importantes. Examinemos los principales casos de uso.

Almacenamiento en búfer de datos en flujo

Al reproducir audio y vídeo, los datos llegan en un flujo continuo y se almacenan temporalmente en un búfer. FIFO Cache garantiza que los primeros fragmentos recibidos sean los primeros en enviarse para su decodificación — esto garantiza una reproducción fluida sin retrasos. El tamaño del búfer se elige en función de la tasa de bits del flujo y el retardo aceptable: normalmente de 2 a 5 segundos para audio, de 10 a 30 segundos para vídeo. FIFO es ideal para tales escenarios, ya que la reordenación de datos (como en LRU) no tiene sentido.

Colas de solicitudes de red

Al limitar el número de solicitudes de red simultáneas, FIFO Cache puede utilizarse para almacenar las solicitudes pendientes. La primera solicitud añadida se ejecutará primero, lo que garantiza una distribución justa de los recursos de red entre los diferentes componentes de la aplicación. Este enfoque se utiliza en OkHttp Dispatcher y bibliotecas similares para la gestión del grupo de conexiones.

Almacenamiento en caché de respuestas HTTP

Las cachés simples de respuestas HTTP en dispositivos móviles suelen utilizar FIFO. Las respuestas a las solicitudes se almacenan en orden de llegada y, cuando se alcanza el límite, se eliminan las más antiguas. Aunque LRU daría un mejor hit-ratio para los escenarios de usuario, FIFO es más simple de implementar y no requiere almacenar la hora del último acceso para cada respuesta. Para las API con carga uniforme, la diferencia en hit-ratio entre FIFO y LRU es mínima.

Procesamiento de eventos táctiles

En las aplicaciones móviles, los eventos táctiles se almacenan en un búfer FIFO antes del procesamiento de gestos. Cada evento debe procesarse en el orden en que ocurrió, de lo contrario el gesto se reconocerá incorrectamente. Una caché FIFO con límite de tamaño evita el desbordamiento del búfer durante los deslizamientos rápidos, descartando los eventos más antiguos si la aplicación no puede seguir el ritmo.

Ejemplos de código FIFO Cache

Veamos una implementación de FIFO Cache en Kotlin utilizando un búfer circular — el enfoque más eficiente para dispositivos móviles.

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) {
            // eliminar el elemento más antiguo
            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]
    }
}

El búfer circular utiliza índices head y tail que se incrementan cíclicamente por módulo maxSize. Cuando size == maxSize, enqueue primero elimina el elemento en head (el más antiguo), desplaza head y luego escribe el nuevo elemento en tail. La aritmética modular envuelve automáticamente los punteros al principio del array, eliminando la copia manual de datos.

Implementación en Swift mediante dos pilas

En Swift, una alternativa conveniente es una cola FIFO basada en dos pilas (cola de dos pilas). Todas las operaciones enqueue van a la primera pila (push), y durante dequeue, los elementos se transfieren a la segunda pila en orden inverso — lo que hace que dequeue sea O(1) en promedio.

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

Dos pilas proporcionan una complejidad amortizada O(1) para enqueue y dequeue. outStack.removeLast() durante la eliminación retira el elemento más antiguo (el primero añadido). Este enfoque no requiere preasignación de memoria, pero puede crear una sobrecarga adicional del recolector de basura durante las inversiones frecuentes de la pila. Para aplicaciones móviles con memoria limitada, el búfer circular sigue siendo más preferible.