FIFO Cache — conceitos-chave, algoritmo de fila e como funciona

O que é FIFO Cache?

FIFO Cache (First In First Out Cache) é um cache de tamanho fixo que utiliza uma fila para gerir elementos. O primeiro elemento adicionado é colocado na cabeça da fila e será o primeiro a ser removido quando ocorrer transbordo. Novos elementos são sempre adicionados no final, garantindo que a ordem de remoção corresponde à ordem de adição.

Ao contrário do LRU, que reordena elementos a cada acesso, o FIFO não altera a posição dos elementos existentes em requisições get. Isso torna o algoritmo completamente determinístico: conhecendo a ordem de adição, pode-se prever com precisão qual elemento será removido a seguir. Esta previsibilidade é crítica para sistemas de tempo real onde os dados devem ser processados na ordem de chegada.

Uma implementação de FIFO Cache pode ser construída em várias estruturas de dados: um buffer circular para máximo desempenho, uma lista ligada para flexibilidade, ou duas pilhas (fila de duas pilhas) para linguagens sem fila embutida. O buffer circular oferece a melhor localidade de cache e sobrecarga mínima, mas requer pré-alocação de memória para maxSize.

Operações básicas do FIFO Cache

A operação enqueue(value) adiciona um elemento ao final da fila. Se o tamanho atingir maxSize, o elemento da cabeça é removido antes da adição. A operação dequeue() remove e retorna o elemento da cabeça — para extração forçada do elemento mais antigo. A operação peek() retorna o elemento da cabeça sem removê-lo — para visualizar o elemento mais antigo sem modificar a fila.

Como funciona o FIFO Cache

O algoritmo FIFO imita o comportamento de uma fila normal: primeiro a entrar, primeiro a ser servido. No contexto de cache, isto significa que o elemento que está no cache há mais tempo será removido quando for necessário espaço — independentemente da sua popularidade. A política de remoção do FIFO ignora a frequência de acesso, o que é simultaneamente um ponto forte e uma fraqueza do algoritmo.

Quando implementado através de um buffer circular, são usados dois ponteiros: head (índice da cabeça da fila) e tail (índice do final). No enqueue, o elemento é escrito no índice tail e tail é incrementado. Se tail atingir o tamanho do buffer, ele volta ao início do array. Se tail alcançar head, a fila está cheia e head é deslocado (remoção). O buffer circular não requer alocação dinâmica de memória e evita fragmentação.

O FIFO Cache demonstra um hit-ratio de 40% a 60% para cargas de trabalho típicas, que é superior ao LIFO mas inferior ao LRU. No entanto, para cenários onde o acesso aos dados é uniforme e não tem pontos quentes, o FIFO pode apresentar resultados comparáveis ao LRU com complexidade de implementação significativamente menor. A memória é utilizada de forma eficiente: não são necessários ponteiros adicionais para reordenar elementos.

O problema da poluição do cache

A principal desvantagem do FIFO é a suscetibilidade à poluição do cache. Se uma grande quantidade de dados que nunca mais será necessária for adicionada ao cache, ela removerá gradualmente todos os elementos úteis e o hit-ratio cairá drasticamente. O LRU resolve parcialmente este problema porque os elementos usados com frequência são constantemente atualizados ao serem movidos para a cabeça, enquanto os dados de uso único são removidos mais rapidamente. No FIFO, os dados de uso único permanecem no cache até serem removidos naturalmente pela ordem da fila.

Comparação entre FIFO, LRU e LIFO

A escolha entre FIFO, LRU e LIFO depende do padrão de acesso aos dados e dos requisitos de previsibilidade de comportamento. O LRU é ideal para a maioria dos cenários, o FIFO para dados em stream com acesso uniforme e o LIFO para estruturas de pilha.

FIFO é ideal para cenários onde a ordem de processamento deve corresponder à ordem de chegada: buffering de dados, registo, processamento de eventos. LRU é melhor para cache com acesso desigual (dados do utilizador). LIFO é aplicável apenas para pilhas e Undo. Para a maioria das aplicações mobile, o LRU continua a ser a escolha padrão, mas o FIFO pode ser preferível sob restrições rigorosas de memória ou requisitos de previsibilidade.

Onde o FIFO Cache é usado

O FIFO Cache encontra aplicação em cenários onde a previsibilidade da remoção ou a ordem de processamento dos dados são importantes. Vamos examinar os principais casos de uso.

Buffering de dados em stream

Ao reproduzir áudio e vídeo, os dados chegam num fluxo contínuo e são armazenados temporariamente num buffer. O FIFO Cache garante que os primeiros fragmentos recebidos são os primeiros a ser enviados para descodificação — isto garante uma reprodução suave sem atrasos. O tamanho do buffer é escolhido com base na taxa de bits do fluxo e no atraso aceitável: tipicamente 2–5 segundos para áudio, 10–30 segundos para vídeo. O FIFO é ideal para tais cenários, pois a reordenação de dados (como no LRU) não faz sentido.

Filas de requisições de rede

Ao limitar o número de requisições de rede simultâneas, o FIFO Cache pode ser usado para armazenar requisições pendentes. A primeira requisição adicionada será executada primeiro, garantindo uma distribuição justa dos recursos de rede entre diferentes componentes da aplicação. Esta abordagem é usada no OkHttp Dispatcher e bibliotecas semelhantes para gestão de pool de conexões.

Cache de respostas HTTP

Caches simples de respostas HTTP em dispositivos móveis usam frequentemente FIFO. As respostas às requisições são armazenadas por ordem de chegada e, quando o limite é atingido, as mais antigas são removidas. Embora o LRU desse um melhor hit-ratio para cenários de utilizador, o FIFO é mais simples de implementar e não requer armazenar o momento do último acesso para cada resposta. Para APIs com carga uniforme, a diferença no hit-ratio entre FIFO e LRU é mínima.

Processamento de eventos tácteis

Em aplicações mobile, os eventos tácteis são armazenados num buffer FIFO antes do processamento de gestos. Cada evento deve ser processado na ordem em que ocorreu, caso contrário o gesto será reconhecido incorretamente. Um FIFO Cache com limite de tamanho evita o transbordo do buffer durante deslizes rápidos, descartando os eventos mais antigos se a aplicação não conseguir acompanhar.

Exemplos de código FIFO Cache

Vejamos uma implementação de FIFO Cache em Kotlin usando um buffer circular — a abordagem mais eficiente para dispositivos móveis.

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) {
            // remover elemento mais antigo
            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]
    }
}

O buffer circular utiliza índices head e tail que incrementam ciclicamente pelo módulo maxSize. Quando size == maxSize, o enqueue primeiro remove o elemento em head (o mais antigo), desloca head e depois escreve o novo elemento em tail. A aritmética modular envolve automaticamente os ponteiros para o início do array, eliminando a cópia manual de dados.

Implementação em Swift através de duas pilhas

Em Swift, uma alternativa conveniente é uma fila FIFO baseada em duas pilhas (fila de duas pilhas). Todas as operações enqueue vão para a primeira pilha (push), e durante o dequeue, os elementos são transferidos para a segunda pilha em ordem inversa — tornando o dequeue O(1) em média.

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

Duas pilhas fornecem complexidade amortizada O(1) para enqueue e dequeue. outStack.removeLast() durante a remoção retira o elemento mais antigo (o primeiro adicionado). Esta abordagem não requer pré-alocação de memória, mas pode criar sobrecarga adicional no coletor de lixo durante inversões frequentes da pilha. Para aplicações móveis com memória limitada, o buffer circular continua a ser mais preferível.