Comment implémenteriez-vous un cache LRU en Java?

Veuillez ne pas dire EHCache ou OSCache, etc. Supposons pour les besoins de cette question que je souhaite implémenter le mien en utilisant uniquement le SDK (apprentissage par l'action). Étant donné que le cache sera utilisé dans un environnement multithread, quelles structures de données utiliseriez-vous? J'en ai déjà implémenté un en utilisant LinkedHashMap et Collections # synchronizedMap , mais je suis curieux de savoir si l'une des nouvelles collections simultanées serait de meilleurs candidats.

MISE À JOUR: Je lisais juste le dernier de Yegge quand j'ai trouvé cette pépite:

Si vous avez besoin d'un accès à temps constant et que vous souhaitez maintenir l'ordre d'insertion, vous ne pouvez pas faire mieux qu'un LinkedHashMap, une structure de données vraiment merveilleuse. La seule façon dont cela pourrait être plus merveilleux est s'il y avait une version simultanée. Mais hélas.

Je pensais presque exactement la même chose avant de partir avec le LinkedHashMap+Collections#synchronizedMap implémentation j'ai mentionnée ci-dessus. Ravi de savoir que je n'avais pas simplement oublié quelque chose.

Sur la base des réponses jusqu'à présent, il semble que mon meilleur pari pour un LRU hautement concurrentiel serait d'étendre ConcurrentHashMap en utilisant une partie de la même logique que celle utilisée LinkedHashMap.

J'aime beaucoup de ces suggestions, mais pour l'instant je pense que je vais m'en tenir à LinkedHashMap+ Collections.synchronizedMap. Si je revisite à l'avenir, je vais probablement travailler sur l' extension ConcurrentHashMapde la même manière LinkedHashMaps'étend HashMap.

METTRE À JOUR:

Sur demande, voici l'essentiel de ma mise en œuvre actuelle.

private class LruCache<A, B> extends LinkedHashMap<A, B> {
    private final int maxEntries;

    public LruCache(final int maxEntries) {
        super(maxEntries + 1, 1.0f, true);
        this.maxEntries = maxEntries;
    }

    /**
     * Returns <tt>true</tt> if this <code>LruCache</code> has more entries than the maximum specified when it was
     * created.
     *
     * <p>
     * This method <em>does not</em> modify the underlying <code>Map</code>; it relies on the implementation of
     * <code>LinkedHashMap</code> to do that, but that behavior is documented in the JavaDoc for
     * <code>LinkedHashMap</code>.
     * </p>
     *
     * @param eldest
     *            the <code>Entry</code> in question; this implementation doesn't care what it is, since the
     *            implementation is only dependent on the size of the cache
     * @return <tt>true</tt> if the oldest
     * @see java.util.LinkedHashMap#removeEldestEntry(Map.Entry)
     */
    @Override
    protected boolean removeEldestEntry(final Map.Entry<A, B> eldest) {
        return super.size() > maxEntries;
    }
}

Map<String, String> example = Collections.synchronizedMap(new LruCache<String, String>(CACHE_SIZE));

Si je faisais cela à partir de zéro aujourd'hui, j'utiliserais Guava CacheBuilder.

C'est le deuxième tour.

Le premier tour était ce que j'ai proposé puis j'ai relu les commentaires avec le domaine un peu plus enraciné dans ma tête.

Voici donc la version la plus simple avec un test unitaire qui montre qu'elle fonctionne sur la base d'autres versions.

D'abord la version non simultanée:

import java.util.LinkedHashMap;
import java.util.Map;

public class LruSimpleCache<K, V> implements LruCache <K, V>{

    Map<K, V> map = new LinkedHashMap (  );


    public LruSimpleCache (final int limit) {
           map = new LinkedHashMap <K, V> (16, 0.75f, true) {
               @Override
               protected boolean removeEldestEntry(final Map.Entry<K, V> eldest) {
                   return super.size() > limit;
               }
           };
    }
    @Override
    public void put ( K key, V value ) {
        map.put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map.get(key);
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        V value =  map.get ( key );
        if (value!=null) {
            map.remove ( key );
            map.put(key, value);
        }
        return value;
    }

    @Override
    public void remove ( K key ) {
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }


}

Le vrai drapeau suivra l'accès des get et des put. Voir JavaDocs. Le removeEdelstEntry sans l'indicateur true pour le constructeur implémenterait simplement un cache FIFO (voir les notes ci-dessous sur FIFO et removeEldestEntry).

Voici le test qui prouve qu'il fonctionne comme un cache LRU:

public class LruSimpleTest {

    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleCache<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        if ( !ok ) die ();

    }

Maintenant pour la version simultanée ...

package org.boon.cache;

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.concurrent.locks.ReadWriteLock;
import java.util.concurrent.locks.ReentrantReadWriteLock;

public class LruSimpleConcurrentCache<K, V> implements LruCache<K, V> {

    final CacheMap<K, V>[] cacheRegions;


    private static class CacheMap<K, V> extends LinkedHashMap<K, V> {
        private final ReadWriteLock readWriteLock;
        private final int limit;

        CacheMap ( final int limit, boolean fair ) {
            super ( 16, 0.75f, true );
            this.limit = limit;
            readWriteLock = new ReentrantReadWriteLock ( fair );

        }

        protected boolean removeEldestEntry ( final Map.Entry<K, V> eldest ) {
            return super.size () > limit;
        }


        @Override
        public V put ( K key, V value ) {
            readWriteLock.writeLock ().lock ();

            V old;
            try {

                old = super.put ( key, value );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return old;

        }


        @Override
        public V get ( Object key ) {
            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.get ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;
        }

        @Override
        public V remove ( Object key ) {

            readWriteLock.writeLock ().lock ();
            V value;

            try {

                value = super.remove ( key );
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public V getSilent ( K key ) {
            readWriteLock.writeLock ().lock ();

            V value;

            try {

                value = this.get ( key );
                if ( value != null ) {
                    this.remove ( key );
                    this.put ( key, value );
                }
            } finally {
                readWriteLock.writeLock ().unlock ();
            }
            return value;

        }

        public int size () {
            readWriteLock.readLock ().lock ();
            int size = -1;
            try {
                size = super.size ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return size;
        }

        public String toString () {
            readWriteLock.readLock ().lock ();
            String str;
            try {
                str = super.toString ();
            } finally {
                readWriteLock.readLock ().unlock ();
            }
            return str;
        }


    }

    public LruSimpleConcurrentCache ( final int limit, boolean fair ) {
        int cores = Runtime.getRuntime ().availableProcessors ();
        int stripeSize = cores < 2 ? 4 : cores * 2;
        cacheRegions = new CacheMap[ stripeSize ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    public LruSimpleConcurrentCache ( final int concurrency, final int limit, boolean fair ) {

        cacheRegions = new CacheMap[ concurrency ];
        for ( int index = 0; index < cacheRegions.length; index++ ) {
            cacheRegions[ index ] = new CacheMap<> ( limit / cacheRegions.length, fair );
        }
    }

    private int stripeIndex ( K key ) {
        int hashCode = key.hashCode () * 31;
        return hashCode % ( cacheRegions.length );
    }

    private CacheMap<K, V> map ( K key ) {
        return cacheRegions[ stripeIndex ( key ) ];
    }

    @Override
    public void put ( K key, V value ) {

        map ( key ).put ( key, value );
    }

    @Override
    public V get ( K key ) {
        return map ( key ).get ( key );
    }

    //For testing only
    @Override
    public V getSilent ( K key ) {
        return map ( key ).getSilent ( key );

    }

    @Override
    public void remove ( K key ) {
        map ( key ).remove ( key );
    }

    @Override
    public int size () {
        int size = 0;
        for ( CacheMap<K, V> cache : cacheRegions ) {
            size += cache.size ();
        }
        return size;
    }

    public String toString () {

        StringBuilder builder = new StringBuilder ();
        for ( CacheMap<K, V> cache : cacheRegions ) {
            builder.append ( cache.toString () ).append ( '\n' );
        }

        return builder.toString ();
    }


}

Vous pouvez voir pourquoi je couvre d'abord la version non simultanée. Les tentatives ci-dessus de créer des bandes pour réduire les conflits de verrouillage. Nous hachons donc la clé, puis recherchons ce hachage pour trouver le cache réel. Cela rend la taille limite plus une suggestion / estimation approximative avec une bonne quantité d'erreur en fonction de la répartition de votre algorithme de hachage de clés.

Voici le test pour montrer que la version simultanée fonctionne probablement. :) (Tester sous le feu serait le vrai moyen).

public class SimpleConcurrentLRUCache {


    @Test
    public void test () {
        LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 1, 4, false );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );

        puts (cache);
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();


        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();

        cache.put ( 8, 8 );
        cache.put ( 9, 9 );

        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();


        puts (cache);


        if ( !ok ) die ();

    }


    @Test
    public void test2 () {
        LruCache <Integer, Integer> cache = new LruSimpleConcurrentCache<> ( 400, false );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        for (int index =0 ; index < 5_000; index++) {
            cache.get(0);
            cache.get ( 1 );
            cache.put ( 2, index  );
            cache.put ( 3, index );
            cache.put(index, index);
        }

        boolean ok = cache.getSilent ( 0 ) == 0 || die ();
        ok |= cache.getSilent ( 1 ) == 1 || die ();
        ok |= cache.getSilent ( 2 ) != null || die ();
        ok |= cache.getSilent ( 3 ) != null || die ();

        ok |= cache.size () < 600 || die();
        if ( !ok ) die ();



    }

}

Ceci est le dernier message .. Le premier message que j'ai supprimé car c'était un LFU pas un cache LRU.

J'ai pensé que je donnerais une autre chance. J'essayais de trouver la version la plus simple d'un cache LRU en utilisant le JDK standard sans trop d'implémentation.

Voici ce que j'ai trouvé. Ma première tentative a été un peu un désastre car j'ai implémenté un LFU au lieu de et LRU, puis j'ai ajouté le support FIFO et LRU ... et puis j'ai réalisé que cela devenait un monstre. Puis j'ai commencé à parler à mon copain John qui était à peine intéressé, puis j'ai décrit en détail comment j'avais implémenté un LFU, un LRU et un FIFO et comment vous pouviez le changer avec un simple argument ENUM, puis j'ai réalisé que tout ce que je voulais vraiment était un simple LRU. Alors ignorez le message précédent de moi et faites-moi savoir si vous voulez voir un cache LRU / LFU / FIFO qui est commutable via une énumération ... non? Ok .. il y va.

Le LRU le plus simple possible en utilisant uniquement le JDK. J'ai implémenté à la fois une version simultanée et une version non simultanée.

J'ai créé une interface commune (c'est du minimalisme, il manque donc probablement quelques fonctionnalités que vous aimeriez mais cela fonctionne pour mes cas d'utilisation, mais laissez-moi savoir si vous souhaitez voir la fonctionnalité XYZ ... Je vis pour écrire du code.) .

public interface LruCache<KEY, VALUE> {
    void put ( KEY key, VALUE value );

    VALUE get ( KEY key );

    VALUE getSilent ( KEY key );

    void remove ( KEY key );

    int size ();
}

Vous vous demandez peut-être ce que getSilent . J'utilise ceci pour tester. getSilent ne modifie pas le score LRU d'un élément.

D'abord le non-concurrent ...

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

public class LruCacheNormal<KEY, VALUE> implements LruCache<KEY,VALUE> {

    Map<KEY, VALUE> map = new HashMap<> ();
    Deque<KEY> queue = new LinkedList<> ();
    final int limit;


    public LruCacheNormal ( int limit ) {
        this.limit = limit;
    }

    public void put ( KEY key, VALUE value ) {
        VALUE oldValue = map.put ( key, value );

        /*If there was already an object under this key,
         then remove it before adding to queue
         Frequently used keys will be at the top so the search could be fast.
         */
        if ( oldValue != null ) {
            queue.removeFirstOccurrence ( key );
        }
        queue.addFirst ( key );

        if ( map.size () > limit ) {
            final KEY removedKey = queue.removeLast ();
            map.remove ( removedKey );
        }

    }


    public VALUE get ( KEY key ) {

        /* Frequently used keys will be at the top so the search could be fast.*/
        queue.removeFirstOccurrence ( key );
        queue.addFirst ( key );
        return map.get ( key );
    }


    public VALUE getSilent ( KEY key ) {

        return map.get ( key );
    }

    public void remove ( KEY key ) {

        /* Frequently used keys will be at the top so the search could be fast.*/
        queue.removeFirstOccurrence ( key );
        map.remove ( key );
    }

    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }
}

La queue.removeFirstOccurrence est une opération potentiellement coûteuse si vous disposez d'un grand cache. On pourrait prendre LinkedList comme exemple et ajouter une carte de hachage de recherche inversée d'élément en nœud pour rendre les opérations de suppression BEAUCOUP PLUS RAPIDES et plus cohérentes. J'ai commencé aussi, mais j'ai réalisé que je n'en avais pas besoin. Mais peut-être...

Lorsque put est appelé, la clé est ajoutée à la file d'attente. Quand obtenir est appelé, la clé est supprimée et ajoutée à nouveau en haut de la file d'attente.

Si votre cache est petit et que la construction d'un objet coûte cher, cela devrait être un bon cache. Si votre cache est vraiment volumineux, la recherche linéaire pourrait être un goulot d'étranglement, surtout si vous n'avez pas de zones de cache chaudes. Plus les points chauds sont intenses, plus la recherche linéaire est rapide, car les éléments chauds sont toujours en haut de la recherche linéaire. Quoi qu'il en soit ... ce qui est nécessaire pour que cela aille plus vite, c'est d'écrire une autre LinkedList qui a une opération de suppression qui a une recherche inversée d'élément à nœud pour supprimer, puis la suppression serait à peu près aussi rapide que la suppression d'une clé d'une carte de hachage.

Si vous avez un cache de moins de 1000 éléments, cela devrait fonctionner correctement.

Voici un test simple pour montrer ses opérations en action.

public class LruCacheTest {

    @Test
    public void test () {
        LruCache<Integer, Integer> cache = new LruCacheNormal<> ( 4 );


        cache.put ( 0, 0 );
        cache.put ( 1, 1 );

        cache.put ( 2, 2 );
        cache.put ( 3, 3 );


        boolean ok = cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 0 ) == 0 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();


        cache.put ( 4, 4 );
        cache.put ( 5, 5 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 0 ) == null || die ();
        ok |= cache.getSilent ( 1 ) == null || die ();
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == 4 || die ();
        ok |= cache.getSilent ( 5 ) == 5 || die ();

        if ( !ok ) die ();

    }
}

Le dernier cache LRU était à thread unique, et veuillez ne pas l'envelopper dans un élément synchronisé ....

Voici un essai sur une version concurrente.

import java.util.Deque;
import java.util.LinkedList;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.locks.ReentrantLock;

public class ConcurrentLruCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    private final ReentrantLock lock = new ReentrantLock ();


    private final Map<KEY, VALUE> map = new ConcurrentHashMap<> ();
    private final Deque<KEY> queue = new LinkedList<> ();
    private final int limit;


    public ConcurrentLruCache ( int limit ) {
        this.limit = limit;
    }

    @Override
    public void put ( KEY key, VALUE value ) {
        VALUE oldValue = map.put ( key, value );
        if ( oldValue != null ) {
            removeThenAddKey ( key );
        } else {
            addKey ( key );
        }
        if (map.size () > limit) {
            map.remove ( removeLast() );
        }
    }


    @Override
    public VALUE get ( KEY key ) {
        removeThenAddKey ( key );
        return map.get ( key );
    }


    private void addKey(KEY key) {
        lock.lock ();
        try {
            queue.addFirst ( key );
        } finally {
            lock.unlock ();
        }


    }

    private KEY removeLast( ) {
        lock.lock ();
        try {
            final KEY removedKey = queue.removeLast ();
            return removedKey;
        } finally {
            lock.unlock ();
        }
    }

    private void removeThenAddKey(KEY key) {
        lock.lock ();
        try {
            queue.removeFirstOccurrence ( key );
            queue.addFirst ( key );
        } finally {
            lock.unlock ();
        }

    }

    private void removeFirstOccurrence(KEY key) {
        lock.lock ();
        try {
            queue.removeFirstOccurrence ( key );
        } finally {
            lock.unlock ();
        }

    }


    @Override
    public VALUE getSilent ( KEY key ) {
        return map.get ( key );
    }

    @Override
    public void remove ( KEY key ) {
        removeFirstOccurrence ( key );
        map.remove ( key );
    }

    @Override
    public int size () {
        return map.size ();
    }

    public String toString () {
        return map.toString ();
    }
}

Les principales différences sont l'utilisation du ConcurrentHashMap au lieu de HashMap, et l'utilisation du Lock (j'aurais pu m'en tirer avec synchronisé, mais ...).

Je ne l'ai pas testé sous le feu, mais cela ressemble à un simple cache LRU qui pourrait fonctionner dans 80% des cas d'utilisation où vous avez besoin d'une simple carte LRU.

J'apprécie les commentaires, sauf pourquoi n'utilisez-vous pas la bibliothèque a, b ou c. La raison pour laquelle je n'utilise pas toujours une bibliothèque est que je ne veux pas toujours que chaque fichier de guerre fasse 80 Mo, et j'écris des bibliothèques, donc j'ai tendance à rendre les bibliothèques enfichables avec une solution assez bonne en place et quelqu'un peut brancher -dans un autre fournisseur de cache s'ils le souhaitent. :) Je ne sais jamais quand quelqu'un pourrait avoir besoin de Guava ou d'ehcache ou de quelque chose d'autre, je ne veux pas les inclure, mais si je rend la mise en cache plugable, je ne les exclurai pas non plus.

La réduction des dépendances a sa propre récompense. J'adore avoir des commentaires sur la façon de rendre cela encore plus simple ou plus rapide ou les deux.

Aussi, si quelqu'un connaît un prêt à partir ...

Ok .. Je sais ce que vous pensez ... Pourquoi n'utilise-t-il pas simplement removeEldest entrée de LinkedHashMap, et bien je devrais mais ... mais ... mais ... Ce serait un FIFO pas un LRU et nous étions essayer de mettre en œuvre un LRU.

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };

Ce test échoue pour le code ci-dessus ...

        cache.get ( 2 );
        cache.get ( 3 );
        cache.put ( 6, 6 );
        cache.put ( 7, 7 );
        ok |= cache.size () == 4 || die ( "size" + cache.size () );
        ok |= cache.getSilent ( 2 ) == 2 || die ();
        ok |= cache.getSilent ( 3 ) == 3 || die ();
        ok |= cache.getSilent ( 4 ) == null || die ();
        ok |= cache.getSilent ( 5 ) == null || die ();

Voici donc un cache FIFO rapide et sale utilisant removeEldestEntry.

import java.util.*;

public class FifoCache<KEY, VALUE> implements LruCache<KEY,VALUE> {

    final int limit;

    Map<KEY, VALUE> map = new LinkedHashMap<KEY, VALUE> () {

        @Override
        protected boolean removeEldestEntry ( Map.Entry<KEY, VALUE> eldest ) {
            return this.size () > limit;
        }
    };


    public LruCacheNormal ( int limit ) {
        this.limit = limit;
    }

    public void put ( KEY key, VALUE value ) {
         map.put ( key, value );


    }


    public VALUE get ( KEY key ) {

        return map.get ( key );
    }


    public VALUE getSilent ( KEY key ) {

        return map.get ( key );
    }

    public void remove ( KEY key ) {
        map.remove ( key );
    }

    public int size () {
        return map.size ();
    }

    public String toString() {
        return map.toString ();
    }
}

Les FIFO sont rapides. Pas de recherche. Vous pourriez faire face à un FIFO devant un LRU et cela gérerait assez bien la plupart des entrées chaudes. Un meilleur LRU aura besoin de cet élément inversé en fonction de nœud.

Quoi qu'il en soit ... maintenant que j'ai écrit du code, laissez-moi parcourir les autres réponses et voir ce que j'ai manqué ... la première fois que je les ai scannées.

LinkedHashMapest O (1), mais nécessite une synchronisation. Pas besoin de réinventer la roue là-bas.

2 options pour augmenter la concurrence:

1. Créez multiples LinkedHashMapet hachage en eux: par exemple: LinkedHashMap[4], index 0, 1, 2, 3. Sur la touche faire key%4 (ou binary ORsur [key, 3]) pour choisir quelle carte faire un put / get / remove.

2. Vous pouvez faire un LRU «presque» en étendant ConcurrentHashMapet en ayant une carte de hachage liée comme une structure dans chacune des régions à l'intérieur. Le verrouillage se produirait de manière plus granulaire qu'un LinkedHashMapqui est synchronisé. Sur un putou putIfAbsentseulement un verrou sur la tête et la queue de la liste est nécessaire (par région). Lors d'un retrait ou d'une récupération, toute la région doit être verrouillée. Je suis curieux de savoir si des listes liées Atomic pourraient aider ici - probablement pour la tête de la liste. Peut-être pour plus.

La structure ne conserverait pas l'ordre total, mais uniquement l'ordre par région. Tant que le nombre d'entrées est beaucoup plus grand que le nombre de régions, cela suffit pour la plupart des caches. Chaque région devra avoir son propre décompte d'entrées, celui-ci serait utilisé plutôt que le décompte global pour le déclencheur d'expulsion. Le nombre par défaut de régions dans a ConcurrentHashMapest de 16, ce qui est suffisant pour la plupart des serveurs aujourd'hui.

1. serait plus facile à écrire et plus rapide avec une concurrence modérée.

2. serait plus difficile à écrire mais évoluerait beaucoup mieux avec une concurrence très élevée. Ce serait plus lent pour un accès normal (tout comme ConcurrentHashMapc'est plus lent que HashMaplà où il n'y a pas de concurrence)

Il existe deux implémentations open source.

Apache Solr a ConcurrentLRUCache: https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html

Il existe un projet open source pour un ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/

J'envisagerais d'utiliser J'envisagerais d' java.util.concurrent.PriorityBlockingQueue , avec une priorité déterminée par un compteur "numberOfUses" dans chaque élément. Je serais très, très prudent pour que toute ma synchronisation soit correcte, car le compteur "numberOfUses" implique que l'élément ne peut pas être immuable.

L'objet élément serait un wrapper pour les objets dans le cache:

class CacheElement {
    private final Object obj;
    private int numberOfUsers = 0;

    CacheElement(Object obj) {
        this.obj = obj;
    }

    ... etc.
}

J'espère que cela t'aides .

import java.util.*;
public class Lru {

public static <K,V> Map<K,V> lruCache(final int maxSize) {
    return new LinkedHashMap<K, V>(maxSize*4/3, 0.75f, true) {

        private static final long serialVersionUID = -3588047435434569014L;

        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > maxSize;
        }
    };
 }
 public static void main(String[] args ) {
    Map<Object, Object> lru = Lru.lruCache(2);      
    lru.put("1", "1");
    lru.put("2", "2");
    lru.put("3", "3");
    System.out.println(lru);
}
}

Le cache LRU peut être implémenté à l'aide d'un ConcurrentLinkedQueue et d'un ConcurrentHashMap qui peuvent également être utilisés dans un scénario multithreading. La tête de la file d'attente est l'élément qui se trouve dans la file d'attente le plus longtemps. La queue de la file d'attente est l'élément qui a été dans la file d'attente le plus court temps. Lorsqu'un élément existe dans la carte, nous pouvons le supprimer de LinkedQueue et l'insérer à la fin.

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

public class LRUCache<K,V> {
  private ConcurrentHashMap<K,V> map;
  private ConcurrentLinkedQueue<K> queue;
  private final int size; 

  public LRUCache(int size) {
    this.size = size;
    map = new ConcurrentHashMap<K,V>(size);
    queue = new ConcurrentLinkedQueue<K>();
  }

  public V get(K key) {
    //Recently accessed, hence move it to the tail
    queue.remove(key);
    queue.add(key);
    return map.get(key);
  }

  public void put(K key, V value) {
    //ConcurrentHashMap doesn't allow null key or values
    if(key == null || value == null) throw new NullPointerException();
    if(map.containsKey(key) {
      queue.remove(key);
    }
    if(queue.size() >= size) {
      K lruKey = queue.poll();
      if(lruKey != null) {
        map.remove(lruKey);
      }
    }
    queue.add(key);
    map.put(key,value);
  }

}

Voici mon implémentation pour LRU. J'ai utilisé PriorityQueue, qui fonctionne essentiellement comme FIFO et non threadsafe. Comparateur utilisé basé sur la création du temps de page et basé sur le exécute le classement des pages pour le temps le moins récemment utilisé.

Pages à considérer: 2, 1, 0, 2, 8, 2, 4

La page ajoutée au cache est: 2 La
page ajoutée au cache est: 1 La
page ajoutée au cache est: 0 La
page: 2 existe déjà dans le cache. Dernier accès mis à jour
Erreur de page, PAGE: 1, remplacée par PAGE: 8 La
page ajoutée au cache est: 8 La
page: 2 existe déjà dans le cache. Dernier accès mis à jour
Erreur de page, PAGE: 0, remplacée par PAGE: 4 La
page ajoutée au cache est: 4

PRODUCTION

LRUCache Pages
-------------
PageName: 8, PageCreationTime: 1365957019974
PageName: 2, PageCreationTime: 1365957020074
PageName: 4, PageCreationTime: 1365957020174

entrez le code ici

import java.util.Comparator;
import java.util.Iterator;
import java.util.PriorityQueue;


public class LRUForCache {
    private PriorityQueue<LRUPage> priorityQueue = new PriorityQueue<LRUPage>(3, new LRUPageComparator());
    public static void main(String[] args) throws InterruptedException {

        System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4");
        System.out.println("----------------------------------------------\n");

        LRUForCache cache = new LRUForCache();
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("1"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("0"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("8"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("2"));
        Thread.sleep(100);
        cache.addPageToQueue(new LRUPage("4"));
        Thread.sleep(100);

        System.out.println("\nLRUCache Pages");
        System.out.println("-------------");
        cache.displayPriorityQueue();
    }


    public synchronized void  addPageToQueue(LRUPage page){
        boolean pageExists = false;
        if(priorityQueue.size() == 3){
            Iterator<LRUPage> iterator = priorityQueue.iterator();

            while(iterator.hasNext()){
                LRUPage next = iterator.next();
                if(next.getPageName().equals(page.getPageName())){
                    /* wanted to just change the time, so that no need to poll and add again.
                       but elements ordering does not happen, it happens only at the time of adding
                       to the queue

                       In case somebody finds it, plz let me know.
                     */
                    //next.setPageCreationTime(page.getPageCreationTime()); 

                    priorityQueue.remove(next);
                    System.out.println("Page: " + page.getPageName() + " already exisit in cache. Last accessed time updated");
                    pageExists = true;
                    break;
                }
            }
            if(!pageExists){
                // enable it for printing the queue elemnts
                //System.out.println(priorityQueue);
                LRUPage poll = priorityQueue.poll();
                System.out.println("Page Fault, PAGE: " + poll.getPageName()+", Replaced with PAGE: "+page.getPageName());

            }
        }
        if(!pageExists){
            System.out.println("Page added into cache is : " + page.getPageName());
        }
        priorityQueue.add(page);

    }

    public void displayPriorityQueue(){
        Iterator<LRUPage> iterator = priorityQueue.iterator();
        while(iterator.hasNext()){
            LRUPage next = iterator.next();
            System.out.println(next);
        }
    }
}

class LRUPage{
    private String pageName;
    private long pageCreationTime;
    public LRUPage(String pagename){
        this.pageName = pagename;
        this.pageCreationTime = System.currentTimeMillis();
    }

    public String getPageName() {
        return pageName;
    }

    public long getPageCreationTime() {
        return pageCreationTime;
    }

    public void setPageCreationTime(long pageCreationTime) {
        this.pageCreationTime = pageCreationTime;
    }

    @Override
    public boolean equals(Object obj) {
        LRUPage page = (LRUPage)obj; 
        if(pageCreationTime == page.pageCreationTime){
            return true;
        }
        return false;
    }

    @Override
    public int hashCode() {
        return (int) (31 * pageCreationTime);
    }

    @Override
    public String toString() {
        return "PageName: " + pageName +", PageCreationTime: "+pageCreationTime;
    }
}


class LRUPageComparator implements Comparator<LRUPage>{

    @Override
    public int compare(LRUPage o1, LRUPage o2) {
        if(o1.getPageCreationTime() > o2.getPageCreationTime()){
            return 1;
        }
        if(o1.getPageCreationTime() < o2.getPageCreationTime()){
            return -1;
        }
        return 0;
    }
}

Voici mon implémentation de cache LRU simultanée la plus performante testée sans aucun bloc synchronisé:

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

/**
 * @param key - may not be null!
 * @param value - may not be null!
 */
public void put(final Key key, final Value value) {
    if (map.containsKey(key)) {
        queue.remove(key); // remove the key from the FIFO queue
    }

    while (queue.size() >= maxSize) {
        Key oldestKey = queue.poll();
        if (null != oldestKey) {
            map.remove(oldestKey);
        }
    }
    queue.add(key);
    map.put(key, value);
}

/**
 * @param key - may not be null!
 * @return the value associated to the given key or null
 */
public Value get(final Key key) {
    return map.get(key);
}

}

C'est le cache LRU que j'utilise, qui encapsule un LinkedHashMap et gère la concurrence avec un simple verrou de synchronisation gardant les zones juteuses. Il "touche" les éléments au fur et à mesure qu'ils sont utilisés pour qu'ils redeviennent l'élément le plus "frais", de sorte qu'il s'agit en fait de LRU. J'avais également l'exigence que mes éléments aient une durée de vie minimale, que vous pouvez également considérer comme un "temps d'inactivité maximal" autorisé, alors vous êtes prêt pour l'expulsion.

Cependant, je suis d'accord avec la conclusion de Hank et la réponse acceptée - si je recommençais aujourd'hui, je vérifierais celle de Guava CacheBuilder.

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;


public class MaxIdleLRUCache<KK, VV> {

    final static private int IDEAL_MAX_CACHE_ENTRIES = 128;

    public interface DeadElementCallback<KK, VV> {
        public void notify(KK key, VV element);
    }

    private Object lock = new Object();
    private long minAge;
    private HashMap<KK, Item<VV>> cache;


    public MaxIdleLRUCache(long minAgeMilliseconds) {
        this(minAgeMilliseconds, IDEAL_MAX_CACHE_ENTRIES);
    }

    public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries) {
        this(minAgeMilliseconds, idealMaxCacheEntries, null);
    }

    public MaxIdleLRUCache(long minAgeMilliseconds, int idealMaxCacheEntries, final DeadElementCallback<KK, VV> callback) {
        this.minAge = minAgeMilliseconds;
        this.cache = new LinkedHashMap<KK, Item<VV>>(IDEAL_MAX_CACHE_ENTRIES + 1, .75F, true) {
            private static final long serialVersionUID = 1L;

            // This method is called just after a new entry has been added
            public boolean removeEldestEntry(Map.Entry<KK, Item<VV>> eldest) {
                // let's see if the oldest entry is old enough to be deleted. We don't actually care about the cache size.
                long age = System.currentTimeMillis() - eldest.getValue().birth;
                if (age > MaxIdleLRUCache.this.minAge) {
                    if ( callback != null ) {
                        callback.notify(eldest.getKey(), eldest.getValue().payload);
                    }
                    return true; // remove it
                }
                return false; // don't remove this element
            }
        };

    }

    public void put(KK key, VV value) {
        synchronized ( lock ) {
//          System.out.println("put->"+key+","+value);
            cache.put(key, new Item<VV>(value));
        }
    }

    public VV get(KK key) {
        synchronized ( lock ) {
//          System.out.println("get->"+key);
            Item<VV> item = getItem(key);
            return item == null ? null : item.payload;
        }
    }

    public VV remove(String key) {
        synchronized ( lock ) {
//          System.out.println("remove->"+key);
            Item<VV> item =  cache.remove(key);
            if ( item != null ) {
                return item.payload;
            } else {
                return null;
            }
        }
    }

    public int size() {
        synchronized ( lock ) {
            return cache.size();
        }
    }

    private Item<VV> getItem(KK key) {
        Item<VV> item = cache.get(key);
        if (item == null) {
            return null;
        }
        item.touch(); // idle the item to reset the timeout threshold
        return item;
    }

    private static class Item<T> {
        long birth;
        T payload;

        Item(T payload) {
            this.birth = System.currentTimeMillis();
            this.payload = payload;
        }

        public void touch() {
            this.birth = System.currentTimeMillis();
        }
    }

}

Eh bien, pour un cache, vous rechercherez généralement des données via un objet proxy, (une URL, une chaîne ...) donc au niveau de l'interface, vous voudrez une carte. mais pour expulser les choses, vous voulez une structure semblable à une file d'attente. En interne, je maintiendrais deux structures de données, une file d'attente prioritaire et un HashMap. Voici une implémentation qui devrait pouvoir tout faire en temps O (1).

Voici un cours que j'ai organisé assez rapidement:

import java.util.HashMap;
import java.util.Map;
public class LRUCache<K, V>
{
    int maxSize;
    int currentSize = 0;

    Map<K, ValueHolder<K, V>> map;
    LinkedList<K> queue;

    public LRUCache(int maxSize)
    {
        this.maxSize = maxSize;
        map = new HashMap<K, ValueHolder<K, V>>();
        queue = new LinkedList<K>();
    }

    private void freeSpace()
    {
        K k = queue.remove();
        map.remove(k);
        currentSize--;
    }

    public void put(K key, V val)
    {
        while(currentSize >= maxSize)
        {
            freeSpace();
        }
        if(map.containsKey(key))
        {//just heat up that item
            get(key);
            return;
        }
        ListNode<K> ln = queue.add(key);
        ValueHolder<K, V> rv = new ValueHolder<K, V>(val, ln);
        map.put(key, rv);       
        currentSize++;
    }

    public V get(K key)
    {
        ValueHolder<K, V> rv = map.get(key);
        if(rv == null) return null;
        queue.remove(rv.queueLocation);
        rv.queueLocation = queue.add(key);//this ensures that each item has only one copy of the key in the queue
        return rv.value;
    }
}

class ListNode<K>
{
    ListNode<K> prev;
    ListNode<K> next;
    K value;
    public ListNode(K v)
    {
        value = v;
        prev = null;
        next = null;
    }
}

class ValueHolder<K,V>
{
    V value;
    ListNode<K> queueLocation;
    public ValueHolder(V value, ListNode<K> ql)
    {
        this.value = value;
        this.queueLocation = ql;
    }
}

class LinkedList<K>
{
    ListNode<K> head = null;
    ListNode<K> tail = null;

    public ListNode<K> add(K v)
    {
        if(head == null)
        {
            assert(tail == null);
            head = tail = new ListNode<K>(v);
        }
        else
        {
            tail.next = new ListNode<K>(v);
            tail.next.prev = tail;
            tail = tail.next;
            if(tail.prev == null)
            {
                tail.prev = head;
                head.next = tail;
            }
        }
        return tail;
    }

    public K remove()
    {
        if(head == null)
            return null;
        K val = head.value;
        if(head.next == null)
        {
            head = null;
            tail = null;
        }
        else
        {
            head = head.next;
            head.prev = null;
        }
        return val;
    }

    public void remove(ListNode<K> ln)
    {
        ListNode<K> prev = ln.prev;
        ListNode<K> next = ln.next;
        if(prev == null)
        {
            head = next;
        }
        else
        {
            prev.next = next;
        }
        if(next == null)
        {
            tail = prev;
        }
        else
        {
            next.prev = prev;
        }       
    }
}

Voici comment ça fonctionne. Les clés sont stockées dans une liste chaînée avec les clés les plus anciennes au début de la liste (les nouvelles clés vont à l'arrière), donc lorsque vous devez `` éjecter '' quelque chose, il vous suffit de le sortir de l'avant de la file d'attente, puis d'utiliser la clé pour supprimer la valeur de la carte. Lorsqu'un élément est référencé, vous récupérez le ValueHolder de la carte, puis utilisez la variable queueelocation pour supprimer la clé de son emplacement actuel dans la file d'attente, puis placez-la à l'arrière de la file d'attente (c'est maintenant le plus récemment utilisé). Ajouter des choses est à peu près la même chose.

Je suis sûr qu'il y a une tonne d'erreurs ici et je n'ai implémenté aucune synchronisation. mais cette classe fournira O (1) l'ajout au cache, O (1) la suppression des anciens éléments et O (1) la récupération des éléments du cache. Même une synchronisation triviale (synchroniser simplement chaque méthode publique) aurait encore peu de conflits de verrouillage en raison de la durée d'exécution. Si quelqu'un a des astuces de synchronisation intelligentes, je serais très intéressé. En outre, je suis sûr qu'il existe des optimisations supplémentaires que vous pouvez implémenter à l'aide de la variable maxsize par rapport à la carte.

Jetez un œil à ConcurrentSkipListMap . Cela devrait vous donner du temps à log (n) pour tester et supprimer un élément s'il est déjà contenu dans le cache, et un temps constant pour le rajouter.

Vous auriez juste besoin d'un compteur, etc. et d'un élément wrapper pour forcer l'ordre de l'ordre LRU et vous assurer que les éléments récents sont supprimés lorsque le cache est plein.

Voici ma courte mise en œuvre, veuillez la critiquer ou l'améliorer!

package util.collection;

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentLinkedQueue;

/**
 * Limited size concurrent cache map implementation.<br/>
 * LRU: Least Recently Used.<br/>
 * If you add a new key-value pair to this cache after the maximum size has been exceeded,
 * the oldest key-value pair will be removed before adding.
 */

public class ConcurrentLRUCache<Key, Value> {

private final int maxSize;
private int currentSize = 0;

private ConcurrentHashMap<Key, Value> map;
private ConcurrentLinkedQueue<Key> queue;

public ConcurrentLRUCache(final int maxSize) {
    this.maxSize = maxSize;
    map = new ConcurrentHashMap<Key, Value>(maxSize);
    queue = new ConcurrentLinkedQueue<Key>();
}

private synchronized void freeSpace() {
    Key key = queue.poll();
    if (null != key) {
        map.remove(key);
        currentSize = map.size();
    }
}

public void put(Key key, Value val) {
    if (map.containsKey(key)) {// just heat up that item
        put(key, val);
        return;
    }
    while (currentSize >= maxSize) {
        freeSpace();
    }
    synchronized(this) {
        queue.add(key);
        map.put(key, val);
        currentSize++;
    }
}

public Value get(Key key) {
    return map.get(key);
}
}

Voici ma propre implémentation à ce problème

simplelrucache fournit une mise en cache LRU sûre pour les threads, très simple et non distribuée avec prise en charge TTL. Il fournit deux implémentations:

• Concurrent basé sur ConcurrentLinkedHashMap
• Synchronisé basé sur LinkedHashMap

Vous pouvez le trouver ici: http://code.google.com/p/simplelrucache/

Le meilleur moyen d'y parvenir est d'utiliser un LinkedHashMap qui maintient l'ordre d'insertion des éléments. Voici un exemple de code:

public class Solution {

Map<Integer,Integer> cache;
int capacity;
public Solution(int capacity) {
    this.cache = new LinkedHashMap<Integer,Integer>(capacity); 
    this.capacity = capacity;

}

// This function returns false if key is not 
// present in cache. Else it moves the key to 
// front by first removing it and then adding 
// it, and returns true. 

public int get(int key) {
if (!cache.containsKey(key)) 
        return -1; 
    int value = cache.get(key);
    cache.remove(key); 
    cache.put(key,value); 
    return cache.get(key); 

}

public void set(int key, int value) {

    // If already present, then  
    // remove it first we are going to add later 
       if(cache.containsKey(key)){
        cache.remove(key);
    }
     // If cache size is full, remove the least 
    // recently used. 
    else if (cache.size() == capacity) { 
        Iterator<Integer> iterator = cache.keySet().iterator();
        cache.remove(iterator.next()); 
    }
        cache.put(key,value);
}

}

Je recherche un meilleur cache LRU utilisant du code Java. Est-il possible pour vous de partager votre code de cache Java LRU en utilisant LinkedHashMapet Collections#synchronizedMap? Actuellement, j'utilise LRUMap implements Mapet le code fonctionne bien, mais je suis en train ArrayIndexOutofBoundExceptionde tester la charge avec 500 utilisateurs sur la méthode ci-dessous. La méthode déplace l'objet récent au début de la file d'attente.

private void moveToFront(int index) {
        if (listHead != index) {
            int thisNext = nextElement[index];
            int thisPrev = prevElement[index];
            nextElement[thisPrev] = thisNext;
            if (thisNext >= 0) {
                prevElement[thisNext] = thisPrev;
            } else {
                listTail = thisPrev;
            }
            //old listHead and new listHead say new is 1 and old was 0 then prev[1]= 1 is the head now so no previ so -1
            // prev[0 old head] = new head right ; next[new head] = old head
            prevElement[index] = -1;
            nextElement[index] = listHead;
            prevElement[listHead] = index;
            listHead = index;
        }
    }