LRU Cache — ce que c'est, algorithme d'éviction et comment ça fonctionne

Qu'est-ce que LRU Cache ?

LRU Cache (Least Recently Used Cache) est une structure de données de taille fixe qui stocke un nombre limité d'éléments et supprime automatiquement ceux qui ont été le moins fréquemment accédés. Lorsqu'une application demande un élément, celui-ci se déplace vers la partie « fraîche » du cache, tandis que les éléments inutilisés depuis longtemps se déplacent vers la fin et sont supprimés lorsque la limite est atteinte.

Le nom « Least Recently Used » décrit la politique d'éviction : l'élément qui n'a pas été utilisé depuis le plus longtemps parmi tous les éléments stockés est supprimé. Ceci repose sur l'hypothèse de localité de référence (locality of reference) — les données récemment demandées ont une forte probabilité d'être à nouveau nécessaires. C'est pourquoi LRU est considéré comme l'une des stratégies de mise en cache les plus efficaces pour la plupart des applications.

L'implémentation classique de LRU Cache nécessite deux structures de données : une table de hachage pour un accès O(1) à tout élément par clé et une liste doublement chaînée pour suivre l'ordre d'utilisation. La table de hachage stocke des références vers les nœuds de la liste, et la liste maintient l'ordre de l'élément le plus récent (tête) au plus ancien (queue).

Opérations de base de LRU Cache

L'opération get(key) vérifie si la clé existe dans la table de hachage. Si l'élément est trouvé, il se déplace en tête de liste (devient le plus récent) et sa valeur est retournée. S'il n'est pas trouvé, null est retourné ou une exception est levée. L'opération put(key, value) insère un nouvel élément : si la clé existe déjà, la valeur est mise à jour et l'élément se déplace en tête. Si le cache est plein, l'élément de queue est supprimé avant l'insertion. Toutes les opérations s'exécutent en temps constant O(1).

Comment fonctionne LRU Cache

L'algorithme LRU Cache repose sur deux principes : comptage d'accès ordonné dans le temps et le mécanisme d'éviction par débordement. Chaque élément est stocké dans un nœud de la liste doublement chaînée, et les pointeurs vers ces nœuds sont conservés dans la table de hachage. À chaque accès, l'élément est détaché de sa position actuelle et inséré en tête de liste.

Lorsque la taille du cache atteint sa valeur maximale (maxSize) et qu'une demande d'insertion d'un nouvel élément arrive, l'algorithme supprime l'élément de queue de la liste doublement chaînée — c'est l'élément le moins récemment utilisé. Après la suppression, de l'espace est libéré pour le nouvel élément, qui est inséré en tête de liste. La table de hachage est mise à jour en conséquence : l'ancienne clé est supprimée, une nouvelle est ajoutée.

Une caractéristique de LRU est sa sensibilité aux schémas d'accès à répétition cyclique. Si l'application accède périodiquement à un ensemble de données plus grand que la taille du cache, LRU peut souffrir de thrashing — remplacement fréquent d'éléments où chaque nouvelle requête évince la précédente. Dans de tels scénarios, LFU (Least Frequently Used) ou les algorithmes adaptatifs peuvent être plus efficaces.

Taille du cache et métriques

Choisir la taille du LRU Cache est un compromis entre la consommation mémoire et le hit-ratio (pourcentage d'accès réussis). Valeurs typiques pour les applications mobiles : 10–20% de la mémoire disponible pour le cache d'images et 50–200 entrées pour le cache de réponses réseau. Un hit-ratio de 80–95% est considéré comme bon, où le cache justifie les coûts mémoire. Pour la surveillance, les compteurs hitCount et missCount sont utilisés, disponibles dans l'implémentation LruCache dans Android.

Implémentation de LRU Cache : HashMap + Doubly Linked List

L'implémentation canonique de LRU Cache utilise une combinaison d'une table de hachage et d'une liste doublement chaînée. La table de hachage fournit un accès O(1) à tout nœud par clé, tandis que la liste doublement chaînée permet de déplacer un nœud en tête et de le supprimer de la queue en O(1). Il est crucial que la liste soit doublement chaînée : cela permet de détacher un nœud du milieu de la liste sans itérer sur tous les éléments.

class LruCache<K, V>(
    private val maxSize: Int
) {
    private val map = mutableMapOf<K, Node<V>>()
    private val head = Node<V>(null)
    private val tail = Node<V>(null)

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: K): V? {
        val node = map[key] ?: return null
        removeNode(node)
        addToHead(node)
        return node.value
    }

    fun put(key: K, value: V) {
        map[key]?.let { node ->
            removeNode(node)
            node.value = value
            addToHead(node)
            return
        }
        if (map.size >= maxSize) {
            tail.prev?.let { toRemove ->
                removeNode(toRemove)
                removeKeyByValue(toRemove)
            }
        }
        val newNode = Node(value)
        addToHead(newNode)
    }
}

Dans l'implémentation, chaque nœud (Node) stocke une valeur et des références vers les nœuds précédent et suivant. Les nœuds sentinelles head et tail simplifient les cas limites — pas besoin de vérifier null lors de l'insertion et de la suppression. La méthode get déplace le nœud trouvé en tête, et put supprime l'élément de queue en cas de débordement. Une méthode séparée removeKeyByValue trouve la clé dans la table de hachage par référence au nœud et la supprime.

Implémentation intégrée de LruCache dans Android

Le SDK Android fournit une classe LruCache prête dans le paquet android.util, qui implémente l'algorithme LRU en utilisant LinkedHashMap en mode access-order. La classe est thread-safe, supporte le comptage hit/miss et fournit le callback entryRemoved pour le nettoyage des ressources lors de l'éviction d'un élément. La taille du cache est définie en unités arbitraires (octets, nombre d'éléments) — il suffit de surcharger la méthode sizeOf.

LRU Cache vs FIFO et LIFO

Les trois algorithmes — LRU, FIFO et LIFO — résolvent le même problème : limiter la consommation mémoire en évincant les éléments en cas de débordement. Cependant, ils utilisent des critères fondamentalement différents pour sélectionner la victime, ce qui détermine leur efficacité dans différents scénarios.

FIFO évince l'élément le plus ancien par temps d'insertion, indépendamment de la fréquence d'accès. Cela peut être inefficace si un élément ancien est toujours pertinent. LRU évite cet inconvénient en tenant compte du schéma d'accès. LIFO évince l'élément le plus récemment ajouté — utile pour les scénarios d'annulation, mais inadapté à la mise en cache, car les nouvelles données sont souvent plus nécessaires que les anciennes. LRU est considéré comme l'équilibre optimal entre complexité d'implémentation et hit-ratio pour la plupart des applications.

Exemples de code LRU Cache

Considérons l'utilisation de la classe intégrée LruCache du SDK Android pour mettre en cache les images téléchargées. L'exemple montre l'initialisation du cache à 1/8 de la mémoire disponible de l'application, ce qui est la recommandation standard de Google pour la mise en cache d'images.

import android.util.LruCache

class ImageCache(context: Context) {
    private val maxMemory = (Runtime.getRuntime().maxMemory() / 1024).toInt()
    private val cacheSize = maxMemory / 8

    private val lruCache = object : LruCache<String, Bitmap>(cacheSize) {
        override fun sizeOf(key: String, bitmap: Bitmap): Int {
            return bitmap.rowBytes * bitmap.height / 1024
        }
    }

    fun getBitmap(key: String): Bitmap? {
        return lruCache.get(key)
    }

    fun putBitmap(key: String, bitmap: Bitmap) {
        lruCache.put(key, bitmap)
    }
}

La méthode sizeOf retourne la taille de l'élément dans les mêmes unités que cacheSize. Ici, la taille du Bitmap en kilo-octets est utilisée (rowBytes × height / 1024). Lorsque la somme des sizeOf de tous les éléments dépasse cacheSize, LruCache évince automatiquement les Bitmaps les moins récemment utilisés. Le callback entryRemoved peut être utilisé pour appeler bitmap.recycle() — libérer la mémoire avant l'éviction.

Implémentation de LRU Cache en Swift

iOS n'a pas de classe LRU Cache intégrée, mais il est facile de l'implémenter en utilisant NSCache (qui utilise une politique d'éviction similaire mais non documentée) ou via une implémentation personnalisée utilisant Dictionary + liste doublement chaînée, comme montré ci-dessous.

class LRUCache<Key: Hashable, Value> {
    private let maxSize: Int
    private var dict = [Key: Node<Value>]()
    private var head: Node<Value>?
    private var tail: Node<Value>?

    init(maxSize: Int) {
        self.maxSize = maxSize
    }

    func get(key: Key) -> Value? {
        guard let node = dict[key] else { return nil }
        moveToHead(node)
        return node.value
    }

    func put(key: Key, value: Value) {
        if let node = dict[key] {
            node.value = value
            moveToHead(node)
            return
        }
        if dict.count >= maxSize {
            tail.map { removeNode($0) }
        }
        let node = Node(value: value)
        dict[key] = node
        addToHead(node)
    }
}

Dans cette implémentation Swift, Node est une classe interne avec les champs value, next et prev. La méthode moveToHead détache un nœud de sa position actuelle et l'insère en tête de liste. En cas de débordement, la queue — l'élément le moins récemment utilisé — est supprimée. Pour la production, il est recommandé d'ajouter la sécurité des threads via NSLock ou une file DispatchQueue.