FIFO Cache — concetti chiave, algoritmo di coda e come funziona

Cos'è FIFO Cache?

FIFO Cache (First In First Out Cache) è una cache di dimensione fissa che utilizza una coda per gestire gli elementi. Il primo elemento aggiunto viene posto in testa alla coda e sarà il primo ad essere rimosso in caso di overflow. I nuovi elementi vengono sempre aggiunti in coda, garantendo che l'ordine di rimozione corrisponda all'ordine di aggiunta.

A differenza di LRU, che riordina gli elementi ad ogni accesso, FIFO non modifica la posizione degli elementi esistenti nelle richieste get. Questo rende l'algoritmo completamente deterministico: conoscendo l'ordine di aggiunta, si può prevedere con precisione quale elemento sarà rimosso successivamente. Questa prevedibilità è fondamentale per i sistemi in tempo reale dove i dati devono essere elaborati nell'ordine di arrivo.

Un'implementazione di FIFO Cache può essere costruita su diverse strutture dati: un buffer circolare per le massime prestazioni, una lista collegata per la flessibilità, o due pile (coda a due pile) per linguaggi senza coda integrata. Il buffer circolare offre la migliore località di cache e un overhead minimo, ma richiede la pre-allocazione della memoria per maxSize.

Operazioni di base di FIFO Cache

L'operazione enqueue(value) aggiunge un elemento in coda. Se la dimensione raggiunge maxSize, l'elemento in testa viene rimosso prima dell'aggiunta. L'operazione dequeue() rimuove e restituisce l'elemento in testa “per l'estrazione forzata dell'elemento più vecchio. L'operazione peek() restituisce l'elemento in testa senza rimuoverlo “per visualizzare l'elemento più vecchio senza modificare la coda”.

Come funziona FIFO Cache

L'algoritmo FIFO imita il comportamento di una coda normale: primo arrivato, primo servito. Nel contesto del caching, ciò significa che l'elemento che è rimasto più a lungo nella cache verrà rimosso quando sarà necessario spazio “indipendentemente dalla sua popolarità. La politica di rimozione di FIFO ignora la frequenza di accesso, il che è sia un punto di forza che una debolezza dell'algoritmo.

Quando implementato tramite un buffer circolare, vengono utilizzati due puntatori: head (indice della testa della coda) e tail (indice della coda). Durante enqueue, l'elemento viene scritto all'indice tail e tail viene incrementato. Se tail raggiunge la dimensione del buffer, torna all'inizio dell'array. Se tail raggiunge head, la coda è piena e head viene spostato (rimozione). Il buffer circolare non richiede allocazione dinamica della memoria ed evita la frammentazione.

FIFO Cache mostra un hit-ratio dal 40% al 60% per carichi di lavoro tipici, che è superiore a LIFO ma inferiore a LRU. Tuttavia, per scenari in cui l'accesso ai dati è uniforme e non ci sono punti caldi, FIFO può mostrare risultati paragonabili a LRU con una complessità di implementazione significativamente inferiore. La memoria viene utilizzata in modo efficiente: non sono necessari puntatori aggiuntivi per il riordino degli elementi.

Il problema dell'inquinamento della cache

Il principale svantaggio di FIFO è la suscettibilità all'inquinamento della cache. Se una grande quantità di dati che non saranno mai più necessari viene aggiunta alla cache, questi rimuoveranno gradualmente tutti gli elementi utili e l'hit-ratio crollerà. LRU risolve parzialmente questo problema perché gli elementi usati frequentemente vengono costantemente rinfrescati spostandoli in testa, mentre i dati monouso vengono rimossi più rapidamente. In FIFO, i dati monouso rimangono nella cache fino a quando non vengono rimossi naturalmente dall'ordine della coda.

Confronto tra FIFO, LRU e LIFO

La scelta tra FIFO, LRU e LIFO dipende dal pattern di accesso ai dati e dai requisiti di prevedibilità del comportamento. LRU è ottimale per la maggior parte degli scenari, FIFO per i dati in streaming con accesso uniforme e LIFO per le strutture a pila.

FIFO è ideale per scenari in cui l'ordine di elaborazione deve corrispondere all'ordine di arrivo: bufferizzazione dei dati, registrazione, elaborazione di eventi. LRU è migliore per il caching con accesso non uniforme (dati utente). LIFO è applicabile solo per pile e Annulla. Per la maggior parte delle applicazioni mobili, LRU rimane la scelta predefinita, ma FIFO può essere preferibile sotto rigidi vincoli di memoria o requisiti di prevedibilità.

Dove viene utilizzato FIFO Cache

FIFO Cache trova applicazione in scenari in cui la prevedibilità della rimozione o l'ordine di elaborazione dei dati sono importanti. Esaminiamo i principali casi d'uso.

Bufferizzazione di dati in streaming

Durante la riproduzione audio e video, i dati arrivano in un flusso continuo e vengono temporaneamente memorizzati in un buffer. FIFO Cache garantisce che i primi frammenti ricevuti siano i primi ad essere inviati per la decodifica “che garantisce una riproduzione fluida senza ritardi. La dimensione del buffer viene scelta in base al bitrate del flusso e al ritardo accettabile: tipicamente 2–5 secondi per l'audio, 10–30 secondi per il video. FIFO è ideale per tali scenari poiché il riordino dei dati (come in LRU) non ha senso.

Code di richieste di rete

Quando si limita il numero di richieste di rete simultanee, FIFO Cache può essere utilizzato per memorizzare le richieste in attesa. La prima richiesta aggiunta verrà eseguita per prima, garantendo una distribuzione equa delle risorse di rete tra i diversi componenti dell'applicazione. Questo approccio viene utilizzato in OkHttp Dispatcher e librerie simili per la gestione del pool di connessioni.

Caching di risposte HTTP

Le cache semplici di risposte HTTP sui dispositivi mobili utilizzano spesso FIFO. Le risposte alle richieste vengono memorizzate nell'ordine di arrivo e, quando viene raggiunto il limite, quelle più vecchie vengono rimosse. Sebbene LRU fornirebbe un hit-ratio migliore per gli scenari utente, FIFO è più semplice da implementare e non richiede la memorizzazione del momento dell'ultimo accesso per ogni risposta. Per le API con carico uniforme, la differenza di hit-ratio tra FIFO e LRU è minima.

Elaborazione di eventi tattili

Nelle applicazioni mobili, gli eventi tattili vengono bufferizzati in una coda FIFO prima dell'elaborazione dei gesti. Ogni evento deve essere elaborato nell'ordine in cui si è verificato, altrimenti il gesto verrà riconosciuto in modo errato. Un FIFO Cache con limite di dimensione previene l'overflow del buffer durante gli swipe rapidi, scartando gli eventi più vecchi se l'applicazione non riesce a stare al passo.

Esempi di codice FIFO Cache

Esaminiamo un'implementazione di FIFO Cache in Kotlin utilizzando un buffer circolare “l'approccio più performante per i dispositivi mobili.

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) {
            // rimuovere l'elemento più vecchio
            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]
    }
}

Il buffer circolare utilizza indici head e tail che si incrementano ciclicamente modulo maxSize. Quando size == maxSize, enqueue rimuove prima l'elemento in head (il più vecchio), sposta head e poi scrive il nuovo elemento in tail. L'aritmetica modulare riporta automaticamente i puntatori all'inizio dell'array, eliminando la copia manuale dei dati.

Implementazione in Swift tramite due pile

In Swift, un'alternativa conveniente è una coda FIFO basata su due pile (coda a due pile). Tutte le operazioni enqueue vanno nella prima pila (push) e durante dequeue, gli elementi vengono trasferiti nella seconda pila in ordine inverso “rendendo dequeue O(1) in media.

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

Due pile forniscono complessità ammortizzata O(1) per enqueue e dequeue. outStack.removeLast() durante la rimozione elimina l'elemento più vecchio (il primo aggiunto). Questo approccio non richiede pre-allocazione di memoria ma può creare un carico aggiuntivo sul garbage collector durante frequenti inversioni di pila. Per applicazioni mobili con memoria limitata, il buffer circolare rimane più preferibile.