Jouons à cache-cache avec Java (première partie)

Mettre en cache un objet signifie qu'on espère le réutiliser à court ou moyen terme en s'épargnant le coût de sa reconstruction. Nous allons voir dans cet article une solution au demeurant louable visant à élaborer une stratégie d'éviction qui s'avère désastreuse : surtout, ne l'utilisez pas en production !

Principe et stratégie

Utiliser un cache est monnaie courante dans une application. Un cache permet de stocker en mémoire un objet susceptible d'être réutilisé, ce qui apporte son lot d'inconvénients : si on veut un cache efficace, il faut stocker suffisamment d'objets, mais si on stocke trop d'objets, on risque de saturer la mémoire. Le gain escompté doit être à la hauteur des sacrifices consentis en terme de volume de mémoire alloué mais aussi en terme de gestion du cache (l'objet mis en cache n'est-il pas périmé ? quelle clé utiliser pour le retrouver ? etc).
Toute la question réside dans l'adoption d'une sorte de compromis entre la taille du cache, la durée de rétention des objets, et dans l'application d'une politique d'éviction.

Parmi les stratégies les plus conventionnelles, on peut fixer une durée de rétention sur les objets, ou fixer un nombre maximum d'objets, ou de taille des objets à stocker, en supprimant les plus anciens une fois le quota atteint. Simple mais très souvent efficace. Google Guava est une librairie Java assez complète qui offre ce type de fonctionnalités, et permet également d'être notifié des entrées supprimées du cache.

Cache-sexe utilisé jadis dans l'île de Java
- Peut contenir un nombre limité d'objets -

Les données du problème

Une autre stratégie plus risquée, est de se délester de la préoccupation de gestion du cache en la confiant à un composant plus primitif qui s'en charge : la référence faible. La JVM se charge alors de libérer les objets non utilisés si la mémoire venait à manquer en supprimant les plus anciens qui n'ont plus de référence forte. Un objet conservant au moins une référence forte est bien entendu conservé tant que le programme en a besoin, mais une fois non atteignable, il devient éligible pour le ramasse miette.

On l'aura compris, une fois qu'un objet est en train d'être collecté par le ramasse miette, l'entrée correspondante est supprimée du cache, mais alors, que devient la notification ? Et bien le composant qui reçoit la notification ne peut plus réaliser de post-traitement sur l'objet, car il n'existe déjà plus. Peut-on alors faire en sorte d'être notifié de la suppression prochaine de l'objet avant qu'elle n'opère ? Non, pas avec des références faibles, à moins que...

L'énoncé du problème

Donc on veut un cache qui retienne ses objets jusqu'à ce qu'on leur dise qu'ils peuvent être éventuellement évincés du cache. Tentons de créer un cache avec les spécifications suivantes :

• on ne veut pas de politique d'éviction particulière, on veut simplement qu'en cas de manque de mémoire, les entrées les plus anciennes qui ont été déclarées "éligibles" pour le ramasse miette soient supprimées du cache
• on veut pouvoir réaliser un post-traitement de ces objets avant qu'ils ne soient réclamés par le ramasse-miette, c'est à dire être notifié de leur suppression du cache mais avec une référence forte que l'on puisse exploiter.

Une solution théoriquement viable...

On va étendre Google Guava pour faire tout ça. Traduit en Java, cela donne une simple interface qui contient deux méthodes :

• la première indiquant qu'on ne retient plus l'objet, qui devient donc candidat à l'éviction
• la seconde qui reçoit la notification de la suppression, mais avec l'instance active bien que retirée du cache.

import com.google.common.cache.Cache;

public interface RetainCache<K, V> extends Cache<K, V> {

 public void release(K key);

 public void discarded(K key, V value);

}

Ensuite, l'implémentation qui doit mettre tout cela en musique. Allons-y progressivement.

On va forcément utiliser des références faibles (Google Guava le fait aussi, mais ne permet pas d'être notifié des entrées qui ont été supprimées pour libérer de la mémoire : rappelez-vous c'est l'objectif que nous nous sommes fixé), alors on va l'appeler "SoftCache" :


(NOTE : le code complet non morcellé de la classe est dispo à la fin de l'article)

public abstract class SoftCache<K,V> implements RetainCache<K, V> {
    // notre code ici
}

Puis, l'entrée à stocker dans le cache. Le problème avec SoftReference, comme indiqué précédemment, est que l'objet ainsi référencé une fois purgé ne peut plus être utilisé pour la notification. L'astuce est simplement de ne pas référencer cet objet par une référence faible mais par une référence forte puisqu'on en aura encore besoin, et de lui adjoindre un objet compagnon factice, qui lui sera référencé par une référence faible :

class SoftEntry extends SoftReference<Object> {
    K key;
    V value;
    Object o;
    SoftEntry(K key, V value) {
        this(key, value, new Object());
    }
    SoftEntry(K key, V value, Object o) {
        // wrap a dummy object
        super(o, queue);
        this.key = key;
        this.value = value;
        this.o = o;
    }
    V getValue() {
        // before returning the value, we force
        // to restore a hard reference on the
        // dummy object, which cause the update
        // of the underlying timestamp.
        get();
        // we are able to supply the real value
        // even if the object has been reclaimed.
        return this.value;
    }
}

Dans cette classe, la référence faible est juste un déclencheur. Il est établi que la JVM tâchera de supprimer les entrées les moins récemment utilisées. Quand on récupère la valeur utile (méthode getValue()), on prend soin de solliciter l'objet factice afin d'actualiser son horloge biologique et lui donner une chance de survivre un peu plus longtemps. Il suffit de jeter un oeil sur le code de la classe SoftReference pour s'en assurer :

// class java.lang.ref.SoftReference

    public T get() {
        T o = super.get();
        if (o != null && this.timestamp != clock) 
            this.timestamp = clock;
        return o;
    }

Dans le constructeur de notre classe SoftEntry, on constate qu'une queue est utilisée :

        super(o, queue);

Cet objet reçoit simplement au fur et à mesure les SoftEntry correspondants aux objets compagnons supprimés. Il nous sert de support à la notification :

    ReferenceQueue<Object> queue = new ReferenceQueue<Object>();

    void startQueueObserver() {
        Thread queueObserver = new Thread() {
            @Override
            public void run() {
                while (true) {
                    try {
                        @SuppressWarnings("unchecked")
                        SoftEntry softEntry =
                                      (SoftEntry) queue.remove();
                        if (softEntry != null) {
                            SoftCache.this.cache.invalidate(
                                      softEntry.key);
                            // notify that the entry
                            // has been discarded
                            discarded(softEntry.key,
                                      softEntry.value);
                        }
                    } catch (InterruptedException ie) { // ignore
                    }
                }
            };
        };
        queueObserver.setDaemon(true);
        queueObserver.setPriority(Thread.MAX_PRIORITY);
        queueObserver.start();
    }

A chaque fois qu'un objet compagnon est supprimé, la SoftEntry correspondante est ajoutée à la fin de la queue (dont la photo plus haut en est une représentation métaphorique). Il suffit d'observer les SoftEntry qui y sont présents, de récupérer la clé et la valeur utile de l'entrée :

• la clé sert à supprimer l'entrée du cache
• et sert aussi avec la valeur à indiquer que l'entrée a été supprimée, mais cette fois, on n'a pas une valeur null mais bien notre objet sur lequel pourra s'opérer le post-traitement souhaité

On remarque que le thread a une priorité élevée, mais que la méthode ne va pas boucler inutilement : la méthode queue.remove() est bloquante et attendra sagement qu'une entrée devienne disponible.

Il ne reste plus qu'à relâcher l'objet compagnon pour rendre l'entrée candidate à la suppression :

    @Override
    public void release(K key) {
        SoftEntry entry = this.cache.getIfPresent(key);
        if (entry != null) {
            // remove the strong ref to the dummy object
            entry.o = null;
            // now, the dummy object has only a soft ref
        }
    };

Le reste du code ne sert qu'à enrober l'entrée dans une SoftEntry :

    public void put(K key, V value) {
        this.cache.put(key, new SoftEntry(key, value));
    }

    public V get(K key) throws ExecutionException {
        SoftEntry entry = this.cache.getIfPresent(key);
        if (entry == null) {
            return null;
        } else {
            return entry.getValue();
        }
    }

    public V getIfPresent(K key) {
        SoftEntry entry = this.cache.getIfPresent(key);
        if (entry == null) {
            return null;
        } else {
            return entry.getValue();
        }
    }

...et à déléguer le cache à Google Guava :

    Cache<K, SoftEntry> cache;

    public SoftCache() {
        this.cache = createCacheBuilder().build();
        startQueueObserver();
    }

    public long size() {
        return this.cache.size();
    }

    public CacheStats stats() {
        return this.cache.stats();
    }

    // etc

Voilà, il ne nous reste plus qu'à tester, à constater que "ça marchotte", mais que toutes les conditions de plantage sont réunies ! Ceux qui ont déjà deviné pourquoi peuvent m'envoyer leur réponses et peut-être gagner un an d'abonnement gratuit au blog "Semantic Mismatch" (croyez-moi, ça vaut le coup).

Nous verrons dans la seconde partie de cet article les raisons de cet échec, les variations de stratégies qui ne font guère mieux, puis quelle application concrète permet d'utiliser une version améliorée d'un tel cache, avec plus de réussite.

Semantic Mismatch
ERR-05 : IllegalArgumentException
CORDES is a bad argument for IL PLEUT
-- See log for details

Annexe : Code complet

• Interface RetainCache :

import com.google.common.cache.Cache;

/**
 * A cache that is able to retain some items until
 * they are explicitly released, whatever is the
 * eviction policy.
 *
 * A cache that implements this interface has its
 * eviction policy slightly changed to retain its
 * relevant items until they are explicitly release.
 *
 * @author Philippe Poulard
 */
public interface RetainCache<K, V> extends Cache<K, V> {

 /**
  * Release an entry, that becomes eligible; when
  * reclaimed (according to the eviction policy of
  * the cache), the {@link #discarded(Object, Object)}
  * method will be invoked.
  *
  * @param key The key of the entry to release.
  */
 public void release(K key);

 /**
  * This method is invoked when the entry has been removed
  * from the cache. This is the entry point for handling
  * the key and the value after removing the entry.
  *
  * @param key The key that was removed.
  * @param value The discarded value.
  */
 public void discarded(K key, V value);

}

• Classe SoftCache :

import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.util.concurrent.Callable;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.ExecutionException;

import com.google.common.cache.Cache;
import com.google.common.cache.CacheBuilder;
import com.google.common.cache.CacheLoader;
import com.google.common.cache.CacheStats;
import com.google.common.collect.ImmutableMap;

/**
 * A soft-cache that is able to handle its reclaimed items
 * before they are about to be removed (when memory leaks
 * happened).
 *
 * <h3>GC note</h3>
 *
 * <p>As mentioned in <a href="http://www.oracle.com/technetwork/java/javase/gc-tuning-6-140523.html#other_considerations">GC tuning</a>,
 * soft references may be kept alive approximately 1000 ms
 * per megabyte by default, which means that if the cache
 * (and the memory) is filled too quickly, an <tt>OutOfMemoryError</tt>
 * may be raised. A call to <tt>System.gc()</tt> may prevent
 * such issue but a normal functioning suppose a statistical
 * distribution in time of storing objects, which would avoid
 * flooding the cache.
 * Note that stressing the cache in a test benchmark may lead to
 * this not realistic case.</p>
 *
 * <h3>Warning</h3>
 *
 * <p>This cache is experimental, do not use in production
 * environment (risk of <tt>OutOfMemoryError</tt>).</p>
 *
 * @author Philippe Poulard
 */
public abstract class SoftCache<K,V> implements RetainCache<K, V> {

    /*
     * The idea of such soft entry, is to store
     * the data in a strong ref and create a soft ref
     * as a companion object. We can't wrap our data
     * in a soft ref because when it is retrieved in
     * the queue, it might have been reclaimed and all
     * the GC stuff might have already happened
     * (therefore we MUST NOT rely on it).
     *
     * In this class, the soft reference is just a
     * trigger; it is stated that the JVM should try
     * to discard the less recently used entries,
     * then if the soft ref is eligible, it means that
     * the value has to be discarded, because it is
     * old enough; since the memory is low, we also
     * discard the data, but after the notification.
     * Note that the VM may use the timestamp of the
     * field when selecting soft references to be
     * cleared, but it is not required to do so.
     */
    class SoftEntry extends SoftReference<Object> {
        K key;
        V value;
        Object o;
        SoftEntry(K key, V value) {
            this(key, value, new Object());
        }
        SoftEntry(K key, V value, Object o) {
            // wrap a dummy object
            super(o, queue);
            this.key = key;
            this.value = value;
            this.o = o;
        }
        V getValue() {
            // before returning the value, we force
            // to restore a hard reference on the
            // dummy object, which cause the update
            // of the underlying timestamp.
            get();
            // we are able to supply the real value
            // even if the object has been reclaimed.
            return this.value;
        }
    }

    Cache<K, SoftEntry> cache;
    ReferenceQueue<Object> queue = new ReferenceQueue<Object>();

    @SuppressWarnings("unchecked")
    public SoftCache(CacheLoader<K,V> cacheLoader) {
        CacheLoader<K,SoftEntry> softCacheLoader = getSoftCacheLoader(cacheLoader);
        this.cache = createCacheBuilder().build(softCacheLoader);
        startQueueObserver();
    }

    @SuppressWarnings("unchecked")
    public SoftCache() {
        this.cache = createCacheBuilder().build();
        startQueueObserver();
    }

    void startQueueObserver() {
        Thread queueObserver = new Thread() {
            @Override
            public void run() {
                while (true) {
                    try {
                        @SuppressWarnings("unchecked")
                        SoftEntry softEntry = (SoftEntry) queue.remove();
                        if (softEntry != null) {
                            SoftCache.this.cache.invalidate(softEntry.key);
                            // notify that the entry has been discarded
                            discarded(softEntry.key, softEntry.value);
                        }
                    } catch (InterruptedException ie) { // ignore
                    }
                }
            };
        };
        queueObserver.setDaemon(true);
        queueObserver.setPriority(Thread.MAX_PRIORITY);
        queueObserver.start();
    }

    /**
     * Create a default cache builder;
     * override this method to add features
     * to the builder.
     *
     * @return A default cache builder.
     */
    @SuppressWarnings("rawtypes")
    protected CacheBuilder createCacheBuilder() {
        return CacheBuilder.newBuilder();
    }

    // a wrapper of the cache loader that deals with soft entry
    CacheLoader<K,SoftEntry> getSoftCacheLoader(final CacheLoader<K,V> cacheLoader) {
        return new CacheLoader<K, SoftEntry>() {
            @Override
            public SoftEntry load(K key) throws Exception {
                return new SoftEntry(key, cacheLoader.load(key));
            }
        };
    }

    @Override
    public void release(K key) {
        SoftEntry entry = this.cache.getIfPresent(key);
        if (entry != null) {
            // remove the strong ref to the dummy object
            entry.o = null;
            // now, the dummy object has only a soft ref
        }
    };

    /**
     * This method is invoked when the entry has been removed
     * from the cache. This is the entry point for handling
     * the key and the value after removing the entry.
     *
     * <p>Since this method is called when a memory leak
     * occurred, the amount of memory used by this method
     * must be low, or provisioned apart (and synchronized).</p>
     *
     * @param key The key that was removed.
     * @param value The discarded value.
     */
    @Override
    public abstract void discarded(K key, V value);

    @Override
    public boolean equals(Object object) {
        return this.cache.equals(object);
    }

    @Override
    public V get(K key) throws ExecutionException {
        SoftEntry entry = this.cache.getIfPresent(key);
        if (entry == null) {
            return null;
        } else {
            return entry.getValue();
        }
    }

    @Override
    public V getIfPresent(K key) {
        SoftEntry entry = this.cache.getIfPresent(key);
        if (entry == null) {
            return null;
        } else {
            return entry.getValue();
        }
    }

    @Override
    public V get(final K key, final Callable<? extends V> valueLoader)
            throws ExecutionException {
        return this.cache.get(key, new Callable<SoftEntry>() {
            @Override
            public SoftEntry call() throws Exception {
                return new SoftEntry(key, valueLoader.call());
            }
        }).getValue();
    }

    /**
     * Irrelevant operation for such a cache
     * (always throws an exception).
     *
     * @throws UnsupportedOperationException
     */
    @Override
    public ImmutableMap<K, V> getAllPresent(Iterable<? extends K> keys) {
        throw new UnsupportedOperationException();
    }

    /**
     * Always throws an exception.
     *
     * @throws UnsupportedOperationException
     */
    @Override
    public V getUnchecked(K key) {
        throw new UnsupportedOperationException();
    }

    @Override
    public void put(K key, V value) {
        this.cache.put(key, new SoftEntry(key, value));
    }

    @Override
    public void invalidate(Object key) {
        this.cache.invalidate(key);
    }

    @Override
    public void invalidateAll(Iterable<?> keys) {
        this.cache.invalidateAll(keys);
    }

    @Override
    public void invalidateAll() {
        this.cache.invalidateAll();
    }

    @Override
    public long size() {
        return this.cache.size();
    }

    @Override
    public CacheStats stats() {
        return this.cache.stats();
    }

    @Override
    public void cleanUp() {
        this.cache.cleanUp();
    }

    /**
     * Irrelevant operation for such a cache
     * (always throws an exception).
     *
     * @throws UnsupportedOperationException
     */
    public ImmutableMap<K, V> getAll(Iterable<? extends K> keys)
            throws ExecutionException {
        throw new UnsupportedOperationException();
    }

    /**
     * Irrelevant operation for such a cache
     * (always throws an exception).
     *
     * @throws UnsupportedOperationException
     */
    @Override
    public V apply(K key) {
        throw new UnsupportedOperationException();
    }

    /**
     * Irrelevant operation for such a cache
     * (always throws an exception).
     *
     * @throws UnsupportedOperationException
     */
    @Override
    public ConcurrentMap<K, V> asMap() {
        throw new UnsupportedOperationException();
    }

}