FIFO Cache — concepts clés, algorithme de file d'attente et fonctionnement

Qu'est-ce que FIFO Cache ?

FIFO Cache (First In First Out Cache) est un cache de taille fixe qui utilise une file d'attente pour gérer les éléments. Le premier élément ajouté est placé en tête de file et sera le premier à être supprimé en cas de débordement. Les nouveaux éléments sont toujours ajoutés en queue, garantissant que l'ordre de suppression correspond à l'ordre d'ajout.

Contrairement à LRU, qui réorganise les éléments à chaque accès, FIFO ne change pas la position des éléments existants lors des requêtes get. Cela rend l'algorithme complètement déterministe : en connaissant l'ordre d'ajout, on peut prédire avec précision quel élément sera supprimé ensuite. Cette prévisibilité est cruciale pour les systèmes temps réel où les données doivent être traitées dans l'ordre d'arrivée.

Une implémentation de FIFO Cache peut être construite sur plusieurs structures de données : un tampon circulaire pour des performances maximales, une liste chaînée pour la flexibilité, ou deux piles (file à deux piles) pour les langages sans file intégrée. Le tampon circulaire offre la meilleure localité de cache et une surcharge minimale, mais nécessite une pré-allocation de mémoire pour maxSize.

Opérations de base de FIFO Cache

L'opération enqueue(value) ajoute un élément en queue de file. Si la taille atteint maxSize, l'élément en tête est supprimé avant l'ajout. L'opération dequeue() supprime et retourne l'élément en tête « pour l'extraction forcée de l'élément le plus ancien. L'opération peek() retourne l'élément en tête sans le supprimer « pour visualiser l'élément le plus ancien sans modifier la file ».

Comment fonctionne FIFO Cache

L'algorithme FIFO imite le comportement d'une file d'attente normale : premier arrivé, premier servi. Dans le contexte de la mise en cache, cela signifie que l'élément qui est dans le cache depuis le plus longtemps sera supprimé lorsque de l'espace sera nécessaire « indépendamment de sa popularité. La politique d'éviction de FIFO ignore la fréquence d'accès, ce qui est à la fois une force et une faiblesse de l'algorithme.

Lorsqu'il est implémenté via un tampon circulaire, deux pointeurs sont utilisés : head (index de la tête de file) et tail (index de la queue). Lors de enqueue, l'élément est écrit à l'index tail et tail est incrémenté. Si tail atteint la taille du tampon, il revient au début du tableau. Si tail rattrape head, la file est pleine et head est décalé (éviction). Le tampon circulaire ne nécessite pas d'allocation dynamique de mémoire et évite la fragmentation.

FIFO Cache démontre un hit-ratio de 40 % à 60 % pour des charges de travail typiques, ce qui est supérieur à LIFO mais inférieur à LRU. Cependant, pour les scénarios où l'accès aux données est uniforme et sans points chauds, FIFO peut montrer des résultats comparables à LRU avec une complexité d'implémentation significativement moindre. La mémoire est utilisée efficacement : aucun pointeur supplémentaire n'est nécessaire pour la réorganisation des éléments.

Le problème de la pollution du cache

Le principal inconvénient de FIFO est sa susceptibilité à la pollution du cache. Si une grande quantité de données qui ne seront plus jamais nécessaires est ajoutée au cache, elles évinceront progressivement tous les éléments utiles et le hit-ratio chutera fortement. LRU résout partiellement ce problème car les éléments fréquemment utilisés sont constamment rafraîchis en étant déplacés en tête, tandis que les données à usage unique sont évincées plus rapidement. Dans FIFO, les données à usage unique restent dans le cache jusqu'à ce qu'elles soient évincées naturellement par l'ordre de la file.

Comparaison de FIFO, LRU et LIFO

Le choix entre FIFO, LRU et LIFO dépend du modèle d'accès aux données et des exigences de prévisibilité du comportement. LRU est optimal pour la plupart des scénarios, FIFO pour les données en streaming avec accès uniforme et LIFO pour les structures de pile.

FIFO est idéal pour les scénarios où l'ordre de traitement doit correspondre à l'ordre d'arrivée : mise en tampon des données, journalisation, traitement d'événements. LRU est meilleur pour la mise en cache avec accès inégal (données utilisateur). LIFO n'est applicable que pour les piles et Annuler. Pour la plupart des applications mobiles, LRU reste le choix par défaut, mais FIFO peut être préférable sous des contraintes de mémoire strictes ou des exigences de prévisibilité.

Où FIFO Cache est utilisé

FIFO Cache trouve son application dans les scénarios où la prévisibilité de l'éviction ou l'ordre de traitement des données est important. Examinons les principaux cas d'utilisation.

Mise en tampon des données en streaming

Lors de la lecture audio et vidéo, les données arrivent en flux continu et sont temporairement stockées dans un tampon. FIFO Cache garantit que les premiers fragments reçus sont les premiers envoyés pour décodage « cela assure une lecture fluide sans délai. La taille du tampon est choisie en fonction du débit binaire du flux et du délai acceptable : typiquement 2 à 5 secondes pour l'audio, 10 à 30 secondes pour la vidéo. FIFO est idéal pour de tels scénarios car la réorganisation des données (comme dans LRU) n'a pas de sens.

Files de requêtes réseau

En limitant le nombre de requêtes réseau simultanées, FIFO Cache peut être utilisé pour stocker les requêtes en attente. La première requête ajoutée sera exécutée en premier, garantissant une distribution équitable des ressources réseau entre les différents composants de l'application. Cette approche est utilisée dans OkHttp Dispatcher et les bibliothèques similaires pour la gestion des pools de connexions.

Mise en cache des réponses HTTP

Les caches simples de réponses HTTP sur les appareils mobiles utilisent souvent FIFO. Les réponses aux requêtes sont stockées dans l'ordre d'arrivée et, lorsque la limite est atteinte, les plus anciennes sont supprimées. Bien que LRU donnerait un meilleur hit-ratio pour les scénarios utilisateur, FIFO est plus simple à implémenter et ne nécessite pas de stocker le moment du dernier accès pour chaque réponse. Pour les API avec charge uniforme, la différence de hit-ratio entre FIFO et LRU est minimale.

Traitement des événements tactiles

Dans les applications mobiles, les événements tactiles sont mis en tampon dans une file FIFO avant le traitement des gestes. Chaque événement doit être traité dans l'ordre où il s'est produit, sinon le geste sera reconnu incorrectement. Un FIFO Cache avec limite de taille empêche le débordement du tampon lors des balayages rapides, en supprimant les événements les plus anciens si l'application ne peut pas suivre.

Exemples de code FIFO Cache

Examinons une implémentation de FIFO Cache en Kotlin utilisant un tampon circulaire « l'approche la plus performante pour les appareils mobiles.

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) {
            // supprimer l'élément le plus ancien
            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]
    }
}

Le tampon circulaire utilise des indices head et tail qui s'incrémentent cycliquement modulo maxSize. Lorsque size == maxSize, enqueue supprime d'abord l'élément à head (le plus ancien), déplace head, puis écrit le nouvel élément à tail. L'arithmétique modulaire renvoie automatiquement les pointeurs au début du tableau, éliminant la copie manuelle des données.

Implémentation en Swift via deux piles

En Swift, une alternative pratique est une file FIFO basée sur deux piles (file à deux piles). Toutes les opérations enqueue vont dans la première pile (push), et lors de dequeue, les éléments sont transférés vers la deuxième pile dans l'ordre inverse « rendant dequeue O(1) en moyenne.

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

Deux piles offrent une complexité amortie O(1) pour enqueue et dequeue. outStack.removeLast() lors de l'éviction supprime l'élément le plus ancien (le premier ajouté). Cette approche ne nécessite pas de pré-allocation de mémoire mais peut créer une charge supplémentaire sur le ramasse-miettes lors des inversions fréquentes de pile. Pour les applications mobiles avec mémoire limitée, le tampon circulaire reste préférable.