Un Cache en 2008

Un cache. Nous savons tous à quoi sert un cache d’objet. Réduire les temps d’accès à un tiers plus lent en conservant une copie temporaire dans un endroit indexé. La taille d’un cache doit être limitée afin de ne pas utiliser trop de mémoire. La recherche dans un cache doit être très rapide. Idéalement, un cache ne doit conserver que les données les plus souvent accédées. Il faut donc mettre en place un algorithme de tri afin que les données qui sont peu utilisées soient effacées.
Curieusement, à chaque fois que je change de boulot j’ai l’occasion d’implémenter un Cache. Je vous propose de passer en revue ici rapidement quelques implémentations simples de cache en Java.

Le cache pour les Nuls
Forcément, mon premier cache qui remonte à 2000 était à l’époque un peu limité. Le besoin était de stocker des objets Java représentant des données géographiques. A l’époque j’avais implémenté cela avec une HashMap toute simple.

Je vous laisse profiter du paysage :

/*
 * Copyright(c) 2008 Nicolas Martignole – Le Touilleur Express
 * http://touilleur-express.fr
 * Distributed under Creative Commons License 2.0
 * See http://creativecommons.org/licenses/by-sa/2.0/fr/deed.fr
 */

/**
 * A very simple cache that drop the oldest Entry.
 * http://touilleur-express.fr
 * @author Nicolas Martignole
 */
public class FIFOCache {
    private HashMap cache;
    private LinkedList indexes;
    private final int cacheSize;

    public FIFOCache(int cacheSize){
        this.cacheSize=cacheSize;
        cache=new HashMap(cacheSize); // initialCapacity
        indexes=new LinkedList();
    }

    public synchronized void cache(String key, Object o){
        if(cache.size() >= cacheSize){
            // remove the oldest element
            String keyToRemove=(String)indexes.removeLast();
            cache.remove(keyToRemove);
        }
        indexes.addFirst(key);
        cache.put(key,o);
    }

    public synchronized Object get(Object o){
        return cache.get(o);
    }
}

Cette implémentation est ultra simpliste : lorsque le cache est plein, on se contente d’effacer l’entrée la plus ancienne. Pour cela on stocke dans une liste chaînée la clé. L’avantage ? Pour un cache utilisé en lecture, c’est efficace. Notez que nous aurions même dû utiliser une Queue, tout simplement. Mais bon, c’était à l’époque.

Cache II, le retour
Un peu plus tard, chez Reuters, je crois avoir ensuite écrit un cache avec cette fois-ci un algorithme de LRU, Least Recently Used. L’idée est de n’effacer que l’entrée la moins accédée dans le cache. Pour que cela fonctionne, il faut donc réordonner la liste chaînée. Lorsqu’un élément existe dans le cache, avant de le retourner nous déplaçons sa clé au début de la liste chaînée.
Les entrées les moins accédées se trouvent à la fin de la liste, alors que les entrées les plus accédées sont au début de la liste. Lorsque le cache est plein, on efface la dernière entrée de la liste pour pouvoir insérer à nouveau une entrée.

Voici le bout de code, à peu de chose prêt :

/*
 * Copyright(c) 2008 Nicolas Martignole – Le Touilleur Express
 * http://touilleur-express.fr
 * Distributed under Creative Commons License 2.0
 * See http://creativecommons.org/licenses/by-sa/2.0/fr/deed.fr
 */

/**
 * A cache that implements the Least Recently Used algorithm, using a LinkedList.
 *
 * http://touilleur-express.fr
 * @author Nicolas Martignole
 */
public class LRUSimpleCache {
    private HashMap cache;
    private LinkedList indexes;
    private final int cacheSize;

    public LRUSimpleCache(int cacheSize) {
        this.cacheSize = cacheSize;
        cache = new HashMap(cacheSize); // initialCapacity
        indexes = new LinkedList();
    }

    public synchronized void cache(String key, Object o) {
        if (cache.size() >= cacheSize) {
            // remove the oldest element
            String keyToRemove = (String) indexes.removeLast();
            cache.remove(keyToRemove);
        }
        indexes.addFirst(key);
        cache.put(key, o);
    }

    public synchronized Object get(String key) {
        Object cached = cache.get(key);
        if (cached == null) return null;
        if (indexes.getFirst().equals(key)) {
            return cached;
        }
        indexes.remove(key);
        indexes.addFirst(key);
        return cached;
    }
}

L’idée est que lorsque l’entrée existe bien dans la Map, on déplace sa clé au début de notre table d’index. Vous allez me demander : pourquoi ne pas faire la recherche sur la liste chainée d’index au lieu de faire un map.get(key) ? Simplement parce que le temps de recherche dans une hashmap tend vers O(1) là où le temps de recherche dans une liste chaînée augmente de manière linéaire (O(n)).
C’est vrai en règle générale, la recherche dans une HashMap sera plus rapide que dans une LinkedList. C’est évidemment faux si vous avez 5 entrées dans votre cache.
Jusqu’ici, rien d’extraordinaire. Simplement, les accès coûtent chers lorsque le cache est plein.

FBI Fausse Bonne Idée
Ensuite j’ai pensé m’inspirer du Garbage Collector. L’idée est la suivante : on crée 2 Maps. Une Map destinée à recevoir les objets jeunes, une Map destinée à recevoir les objets qui ont été demandés de nombreuses fois. Lorsque le cache est plein, on détruit la Map « jeune » en déplaçant vers la Map ancienne les objets fréquemment demandés. Lorsque le cache est utilisé, on recherche d’abord dans la Map des « anciens » avant de chercher dans la Map des petits nouveaux. Le problème est de mettre en place une politique pour vider la Map ancienne. Pour cela on peut reprendre l’idée du FIFO ou même ajouter un peu de LRU… Bref c’est faisable mais un peu compliqué.

Cache III la revanche
Et puis ensuite, mission à la BNP. Même souci : un cache constitué de 2 Hashtables a un souci de synchronisation. Plutôt que de fixer le code, ce qui était possible, j’en ai profité pour regarder aujourd’hui comment je pourrai implémenter toujours le même cache le plus simplement du monde.

Tout d’abord le premier réflexe : consulter l’API de Java. Est-ce que cela vaut le coup de réinventer la roue ? Je me suis dis aussi : prenons une API opensource de cache et hop c’est réglé. Mais pour notre besoin, une seule classe est nécessaire.

Pour ma nouvelle implémentation je suis donc parti de la class LinkedHashMap. Cette class qui étend HashMap ajoute une liste ordonnée afin que l’ordre d’enregistrement des paires clés/valeurs soit prédictif. En clair : le même code que ce que je vous ai montré mais disponible dans l’API Java.

La classe LinkedHashMap fournit un temps constant d’accès comme toutes les HashMaps pour les méthodes add, contains et remove, ce qui en fait donc une classe parfaite pour le cache. Un constructeur spécial permet de créer une LinkedHashMap dont l’ordre d’itération correspond à l’ordre d’accès des entrées de la Map, de la donnée la plus accedée en premier à la donnée la moins accedée en dernier. Soit exactement l’algorithme LRU dont je vous parlais plus haut.
A chaque fois que vous allez utiliser la méthode get() de cette Map, l’entrée accédée est promue au début de la liste. Ainsi un hit cache entraîne un tri du cache. Petit à petit, les entrées du cache qui ne sont pas accédées se retrouvent à la fin de votre cache.

C’est là qu’intervient une méthode à surcharger afin de décider de la politique de nettoyage. La méthode removeEldestEntry(Map.Entry e) est appelée par l’API à chaque insertion. A vous d’implémenter un bout de code qui retourne true lorsque vous souhaitez effacer l’entrée la plus ancienne de la Map. Pour ma part je me contente de regarder si la taille de la LinkedHashMap est supérieure à ma taille configurée lors de la création de l’objet. Dans ce cas, l’API effectue le ménage et retire l’entrée la plus ancienne.

A cela j’ai ajouté l’utilisation des Generics. En effet, il est dommage en Java 5 de ne pas s’en servir, cela évite des typages à ajouter dans le code partout.

Enfin comme je suis ami avec la mémoire, j’ai décidé de décorer les valeurs cachées d’une SoftReference. L’idée est la suivante : lorsque dans la JVM la mémoire vient à manquer, autant faire le ménage dans le cache et donc, effacer toutes les entrées afin de laisser respirer l’application. Pour faire cela, le mieux est donc de simplement décorer les valeurs enregistrées dans la LinkedHashMap avec une SoftReference, ce qui n’est pas trop agressif et permet de conserver les données en cache. Une WeakReference sera trop faible et dès l’activation du GarbageCollector, votre cache sera vidé. Une SoftReference d’après mes tests, ne sera détruite que si tout d’abord la donnée pointée n’est plus disponible ou en cours d’utilisation, et lorsque le GC se réveille pour faire un gros nettoyage.

Pour tester cela, j’ai fait un test unitaire avec une petite boucle infinie. Sans SoftReference, une exception OutOfMemory est levée au bout de 50 objets stockés. Avec une SoftReference, le test tourne sans fin. Un test avec YourKit montre l’activité du GarbageCollector, et que donc le cache se nettoie bien tout seul.
Voilà j’espère que ce code fonctionnera correctement et longtemps, et que donc à mon prochain job je n’aurai pas à nouveau besoin d’écrire un cache.

/**
 * Copyright(c) 2008 Nicolas Martignole – Le Touilleur Express
 * http://touilleur-express.fr
 * Distributed under Creative Commons License 2.0
 * See http://creativecommons.org/licenses/by-sa/2.0/fr/deed.fr
*/

/**
 * New LRU Cache constructed with a LinkedHashMap, a Map with a predictable iteration order that
 * stores a key/value pair, the value is decorated with a SoftReference so that we can release
 * memory when the system is overloaded.
 * I also use a special constructor from LinkedHashMap so that I can have an order in this map
 * provided by access
 *
 * @author Nicolas Martignole
 * @version created Sep 16, 2008
 */
public class NewLRUCache<K, V> {
    private LinkedHashMap<K, SoftReference<V>> cache;
    private int cacheSize;
    private int numberOfElements = 0;

    /**
     * Creates a cache with a fixed size of 1000.
     */
    public NewLRUCache() {
        this(1000);
    }

    /**
     * Create a new LRU Cache with a LinkedHashMap, override the removeEldestEntry
     * so that we can inject the current cacheSize.
     *
     * @param cacheSize is a positive integer.
     */
    public NewLRUCache(int cacheSize) {
        this.cacheSize = (cacheSize < 1) ? 1000 : cacheSize;
        int initialCapacity = (int) (cacheSize * 0.75);
        cache = new LinkedHashMap<K, SoftReference<V>>(initialCapacity, 0.75f, true) {
            @Override
            /**
             * Returns true if the current map size is greater than NewLRUCache, wich means
             * that the cache is full and we should drop the oldest entry.
             */
            protected boolean removeEldestEntry(Map.Entry<K, SoftReference<V>> eldest) {
                return size() > NewLRUCache.this.cacheSize;
            }
        };
    }

    /**
     * Returns the cache size.
     *
     * @return the cache size.
     */
    public final int getSize() {
        return cacheSize;
    }

    /**
     * Returns the number of elements currently stored into the cache.
     *
     * @return a number of elements.
     */
    public final int getCurrentUsage() {
        return numberOfElements;
    }

    /**
     * Stores into the cache the specified entry, remove the less recently used entry
     * if the cache is full.
     *
     * @param key   is the new unique key to store.
     * @param entry is the object to put into the cache.
     */
    public void cacheEntry(K key, V entry) {
        if (key == null) return;
        if (entry == null) return;
        synchronized (this) {
            cache.put(key, new SoftReference<V>(entry));
            numberOfElements++;
        }
    }

    /**
     * Lookup for the specified key, update the list of less recently used items.
     *
     * @param key is the key to lookup
     * @return the associated object or null if it was not found.
     */
    public V getEntry(K key) {
        if (key == null) {
            return null;
        }
        SoftReference<V> ref;
        synchronized (this) {
            ref = cache.get(key);
            if (ref == null) {
                // The value has been garbage collected so we must delete the key
                cache.remove(key);
                numberOfElements--;
                return null;
            }
        }
        return ref.get();
    }

}

Références :
Javadoc de LinkedHashMap
Javadoc de SoftReference

Articles similaires:

Une histoire de cache Devoxx 2008 c’est parti Prédictions pour 2008 Synchronisation avec Vector,Hashtable,HashMap et ArrayList