Les algorithmes d'éviction de cache déterminent quelles données supprimer lorsque la mémoire cache est pleine, en fonction de critères d'accès. Ils sont cruciaux pour optimiser les performances des systèmes de cache. Voici une analyse de plusieurs algorithmes courants, avec leurs principes, implémentations et compromis.

1. LRU (Least Recently Used)

1.1. Principe

L'algorithme LRU élimine les données les moins récemment utilisées. Sa logique repose sur l'idée que les données accédées récemment ont plus de chances d'être réutilisées.

1.2. Implémentation

Une méthode classique consiste à utiliser une liste chaînée pour gérer les données en cache :

• Les nouevlles données sont insérées en tête de liste.
• Lorsqu'une donnée est accédée (hit), elle est déplacée en tête de liste.
• Si la liste est pleine, la donnée en fin de liste est supprimée.

1.3. Analyse

Taux de réussite : Efficace pour les données chaudes, mais sensible aux accès sporadiques ou périodiques par lots, ce qui peut entraîner une pollution du cache et réduire le taux de réussite.

Complexité : Implémentation simple.

Coût : En cas de hit, il faut parcourir la liste pour localiser la donnée, puis la déplacer en tête.

2. LRU-K

2.1. Principe

Dans LRU-K, K représente le nombre d'accès récents. LRU classique correspond à K=1. LRU-K vise à réduire la pollution du cache en exigeant qu'une donnée soit accédée K fois avant d'être mise en cache. L'élimination se base sur la date du K-ième accès.

2.2. Implémentation

LRU-K maintient une file d'historique pour les accès. Les données ne sont transférées en cache que lorsqu'elles atteignent K accès. La file d'historique peut suivre une politique FIFO ou LRU pour l'élimination préliminaire. Une fois en cache, les données sont triées par date d'accès.

2.3. Analyse

Taux de réussite : Supérieur à LRU grâce à la réduction de la pollution.

Complexité : Élevée en raison de la gestion d'une file de priorité.

Coût : Consommation mémoire accrue pour l'historique des accès, et charge CPU plus importante due au tri par date.

En pratique, LRU-2 offre un bon compromis, tandis que des valeurs de K plus élevées améliorent le taux de réussite mais nécessitent plus de données pour nettoyer l'historique.

3. Two Queues (2Q)

3.1. Principe

L'algorithme 2Q est similaire à LRU-2, mais utilise deux files : une file FIFO pour les premiers accès et une file LRU pour les données accédées plus d'une fois.

3.2. Implémentation

Lors d'un premier accès, la donnée est placée dans la file FIFO. Si elle est réaccédée, elle est déplacée dans la file LRU. Chaque file applique sa propre politique d'élimination : FIFO pour la première, LRU pour la seconde.

3.3. Analyse

Taux de réussite : Meilleur que LRU.

Complexité : Modérée avec deux files simples.

Coût : Somme des coûts des deux politiques. Par rapport à LRU-2, 2Q peut réduire les lectures depuis le stockage d'origine.

4. Multi Queue (MQ)

4.1. Principe

MQ classe les données dans plusieurs files LRU basées sur la fréquence d'accès, avec des niveaux de priorité. L'idée est de favoriser les données fréquemment utilisées.

4.2. Implémentation

Les files Q0, Q1, ..., Qk représentent différents niveaux de priorité. Les nouvelles données entrent dans Q0. Lorsque le nombre d'accès augmente, les données sont promues vers une file de priorité supérieure. Si une donnée n'est pas accédée pendant un certain temps, elle est rétrogradée. L'élimination se fait depuis la file de priorité la plus basse, avec un historique Q-history pour les données éliminées.

4.3. Analyse

Taux de réussite : Élevé grâce à la gestion par fréquence.

Complexité : Supérieure à LRU due à la maintenance de plusieurs files et des horodatages.

Coût : Nécessite des scans périodiques des files, mais la taille totale des files est limitée par la capacité du cache.

5. Comparaison des algorithmes de type LRU

La comparaison ci-dessous est qualitative et théorique, car les performances varient selon les modèles d'accès.

En pratique, le choix dépend des besoins métier. Par exemple, LRU est souvent préféré pour sa simplicité et son faible coût, malgré un taux de réussite potentiellement plus bas.

Implémentation Java de LRU

Une implémentation simple utilise la classe LinkedHashMap de Java en surchargeant la méthode removeEldestEntry.

Voici une version adaptée avec synchronisation :

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

public class CacheLRU<K, V> extends LinkedHashMap<K, V> {
    private final int capaciteMax;
    private static final float FACTEUR_CHARGE = 0.75f;
    private final Lock verrou = new ReentrantLock();

    public CacheLRU(int capaciteMax) {
        super(capaciteMax, FACTEUR_CHARGE, true);
        this.capaciteMax = capaciteMax;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> plusAncien) {
        return size() > capaciteMax;
    }

    @Override
    public boolean containsKey(Object cle) {
        verrou.lock();
        try {
            return super.containsKey(cle);
        } finally {
            verrou.unlock();
        }
    }

    @Override
    public V get(Object cle) {
        verrou.lock();
        try {
            return super.get(cle);
        } finally {
            verrou.unlock();
        }
    }

    @Override
    public V put(K cle, V valeur) {
        verrou.lock();
        try {
            return super.put(cle, valeur);
        } finally {
            verrou.unlock();
        }
    }

    @Override
    public int size() {
        verrou.lock();
        try {
            return super.size();
        } finally {
            verrou.unlock();
        }
    }

    @Override
    public void clear() {
        verrou.lock();
        try {
            super.clear();
        } finally {
            verrou.unlock();
        }
    }
}

Une autre approche utilise une liste doublement chaînée pour une gestion explicite :

import java.util.Hashtable;

public class CacheLRUPersonnalise {
    class Noeud {
        Noeud precedent;
        Noeud suivant;
        Object valeur;
        Object cle;
    }

    private int tailleCache;
    private Hashtable<Object, Noeud> conteneur;
    private int tailleActuelle;
    private Noeud tete;
    private Noeud queue;

    public CacheLRUPersonnalise(int taille) {
        tailleActuelle = 0;
        tailleCache = taille;
        conteneur = new Hashtable<>(taille);
    }

    public Object obtenir(Object cle) {
        Noeud noeud = conteneur.get(cle);
        if (noeud != null) {
            deplacerEnTete(noeud);
            return noeud.valeur;
        }
        return null;
    }

    public void mettre(Object cle, Object valeur) {
        Noeud noeud = conteneur.get(cle);
        if (noeud == null) {
            if (tailleActuelle >= tailleCache) {
                if (queue != null) {
                    conteneur.remove(queue.cle);
                    supprimerQueue();
                }
            } else {
                tailleActuelle++;
            }
            noeud = new Noeud();
        }
        noeud.valeur = valeur;
        noeud.cle = cle;
        deplacerEnTete(noeud);
        conteneur.put(cle, noeud);
    }

    public Object supprimer(Object cle) {
        Noeud noeud = conteneur.get(cle);
        if (noeud != null) {
            if (noeud.precedent != null) {
                noeud.precedent.suivant = noeud.suivant;
            }
            if (noeud.suivant != null) {
                noeud.suivant.precedent = noeud.precedent;
            }
            if (queue == noeud) {
                queue = noeud.precedent;
            }
            if (tete == noeud) {
                tete = noeud.suivant;
            }
        }
        return noeud;
    }

    public void vider() {
        tete = null;
        queue = null;
    }

    private void supprimerQueue() {
        if (queue != null) {
            if (queue.precedent != null) {
                queue.precedent.suivant = null;
            } else {
                tete = null;
            }
            queue = queue.precedent;
        }
    }

    private void deplacerEnTete(Noeud noeud) {
        if (noeud == tete) {
            return;
        }
        if (noeud.precedent != null) {
            noeud.precedent.suivant = noeud.suivant;
        }
        if (noeud.suivant != null) {
            noeud.suivant.precedent = noeud.precedent;
        }
        if (queue == noeud) {
            queue = noeud.precedent;
        }
        if (tete != null) {
            noeud.suivant = tete;
            tete.precedent = noeud;
        }
        tete = noeud;
        noeud.precedent = null;
        if (queue == null) {
            queue = tete;
        }
    }
}