Jak zaimplementowałbyś pamięć podręczną LRU w Javie?

Proszę nie mówić o EHCache lub OSCache, itp. Załóżmy na potrzeby tego pytania, że ​​chcę zaimplementować własny używając tylko SDK (ucząc się przez działanie). Biorąc pod uwagę, że pamięć podręczna będzie używana w środowisku wielowątkowym, jakich struktur danych użyjesz? Zaimplementowałem już jeden przy użyciu LinkedHashMap i Collections # synchronizedMap , ale jestem ciekawy, czy któraś z nowych współbieżnych kolekcji byłaby lepszymi kandydatami.

AKTUALIZACJA: Właśnie czytałem najnowszą wersję Yegge, kiedy znalazłem ten samorodek:

Jeśli potrzebujesz stałego dostępu i chcesz utrzymać kolejność reklam, nie możesz zrobić nic lepszego niż LinkedHashMap, naprawdę wspaniała struktura danych. Jedynym sposobem, w jaki mogłoby być wspanialsze, jest istnienie równoległej wersji. Ale niestety.

Myślałam prawie dokładnie to samo, zanim poszłam z LinkedHashMap+ Collections#synchronizedMapwdrażania wspomniałem powyżej. Miło wiedzieć, że czegoś nie przeoczyłem.

Opierając się na dotychczasowych odpowiedziach, wydaje się, że najlepszym rozwiązaniem dla wysoce współbieżnego LRU byłoby rozszerzenie ConcurrentHashMap przy użyciu tej samej logiki, której LinkedHashMapużywa.

Podoba mi się wiele z tych sugestii, ale na razie myślę, że zostanę przy LinkedHashMap+ Collections.synchronizedMap. Jeśli wrócę do tego w przyszłości, prawdopodobnie popracuję nad rozszerzeniem ConcurrentHashMapw ten sam sposób LinkedHashMaprozszerzeń HashMap.

AKTUALIZACJA:

Na życzenie przedstawiam sedno mojej obecnej realizacji.

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));

Gdybym robił to dzisiaj od zera, użyłbym guawy CacheBuilder.

To jest runda druga.

Pierwsza runda była tym, co wymyśliłem, a potem ponownie przeczytałem komentarze z domeną nieco bardziej zakorzenioną w mojej głowie.

Oto najprostsza wersja z testem jednostkowym, który pokazuje, że działa w oparciu o inne wersje.

Najpierw wersja niewspółbieżna:

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 ();
    }


}

Prawdziwa flaga będzie śledzić dostęp do pobierania i wysyłania. Zobacz JavaDocs. RemoveEdelstEntry bez flagi true dla konstruktora po prostu zaimplementowałoby pamięć podręczną FIFO (zobacz uwagi poniżej na temat FIFO i removeEldestEntry).

Oto test, który dowodzi, że działa jako pamięć podręczna 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 ();

    }

Teraz dla wersji równoległej ...

pakiet 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 ();
    }


}

Możesz zobaczyć, dlaczego najpierw omawiam wersję, która nie jest współbieżna. Powyższe próby stworzenia pewnych pasków, aby zmniejszyć rywalizację o blokady. Więc haszuje klucz, a następnie wyszukuje ten skrót, aby znaleźć rzeczywistą pamięć podręczną. To sprawia, że ​​rozmiar limitu jest bardziej sugestią / zgadywaniem z dużą ilością błędu, w zależności od tego, jak dobrze rozłożony jest algorytm skrótu kluczy.

Oto test pokazujący, że wersja równoległa prawdopodobnie działa. :) (Test pod ostrzałem byłby prawdziwym sposobem).

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 ();



    }

}

To jest ostatni post .. Pierwszy post, który usunąłem, ponieważ był to LFU, a nie pamięć podręczna LRU.

Pomyślałem, że spróbuję jeszcze raz. Próbowałem wymyślić najprostszą wersję pamięci podręcznej LRU przy użyciu standardowego JDK bez zbyt wielu implementacji.

Oto co wymyśliłem. Moja pierwsza próba była trochę katastrofą, ponieważ zaimplementowałem LFU zamiast i LRU, a potem dodałem do niego FIFO i obsługę LRU ... i zdałem sobie sprawę, że staje się potworem. Potem zacząłem rozmawiać z moim kumplem Johnem, który był ledwo zainteresowany, a potem szczegółowo opisałem, jak zaimplementowałem LFU, LRU i FIFO i jak można to zmienić za pomocą prostego argumentu ENUM, a potem zdałem sobie sprawę, że wszystko, czego naprawdę chcę był prostym LRU. Więc zignoruj ​​wcześniejszy post ode mnie i daj mi znać, jeśli chcesz zobaczyć pamięć podręczną LRU / LFU / FIFO, którą można przełączać za pomocą wyliczenia ... nie? Ok .. oto on.

Najprostszy możliwy LRU wykorzystujący tylko JDK. Zaimplementowałem zarówno wersję współbieżną, jak i inną.

Stworzyłem wspólny interfejs (to minimalizm, więc prawdopodobnie brakuje kilku funkcji, które byś chciał, ale działa w moich przypadkach użycia, ale pozwól, jeśli chcesz zobaczyć funkcję XYZ, daj mi znać ... żyję, aby pisać kod.) .

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 ();
}

Możesz się zastanawiać, czym jest getSilent . Używam tego do testów. getSilent nie zmienia wyniku LRU elementu.

Najpierw nierównoczesny ....

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 ();
    }
}

Queue.removeFirstOccurrence jest potencjalnie kosztowna operacja, jeśli masz dużą pamięć podręczną. Można wziąć jako przykład LinkedList i dodać mapę skrótów wyszukiwania wstecznego od elementu do węzła, aby operacje usuwania były DUŻO SZYBSZE i bardziej spójne. Ja też zacząłem, ale potem zdałem sobie sprawę, że tego nie potrzebuję. Ale może...

Po wywołaniu put klucz zostanie dodany do kolejki. Po wywołaniu get klucz jest usuwany i ponownie dodawany na początek kolejki.

Jeśli twoja skrzynka jest mała, a budowanie przedmiotu jest drogie, powinna to być dobra skrzynka. Jeśli twoja pamięć podręczna jest naprawdę duża, wyszukiwanie liniowe może być szyjką butelki, zwłaszcza jeśli nie masz gorących obszarów pamięci podręcznej. Im bardziej intensywne są gorące punkty, tym szybsze jest wyszukiwanie liniowe, ponieważ gorące elementy zawsze znajdują się na szczycie wyszukiwania liniowego. W każdym razie ... aby to działało szybciej, jest napisanie innej LinkedList, która ma operację usuwania, która ma odwrotne wyszukiwanie elementu do węzła w celu usunięcia, a następnie usuwanie byłoby tak szybkie, jak usunięcie klucza z mapy skrótów.

Jeśli masz pamięć podręczną poniżej 1000 elementów, powinno to działać dobrze.

Oto prosty test pokazujący jego działanie w akcji.

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 ();

    }
}

Ostatnia pamięć podręczna LRU była jednowątkowa i proszę nie pakować jej w nic zsynchronizowanego ....

Oto próba równoległej wersji.

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 ();
    }
}

Główne różnice to użycie ConcurrentHashMap zamiast HashMap oraz użycie Lock (mogłem uciec z synchronizacją, ale ...).

Nie testowałem go pod ostrzałem, ale wygląda na to, że jest to prosta pamięć podręczna LRU, która może się sprawdzić w 80% przypadków użycia, w których potrzebujesz prostej mapy LRU.

Czekam na opinie, z wyjątkiem tego, dlaczego nie używasz biblioteki a, b lub c. Powodem, dla którego nie zawsze używam biblioteki, jest to, że nie zawsze chcę, aby każdy plik wojenny miał 80 MB i piszę biblioteki, więc staram się tworzyć wtyczki bibliotek z wystarczająco dobrym rozwiązaniem i ktoś może podłączyć - u innego dostawcy pamięci podręcznej, jeśli chcą. :) Nigdy nie wiem, kiedy ktoś może potrzebować guawy, ehcache lub czegoś innego, czego nie chcę dołączać, ale jeśli stworzę wtyczkę do buforowania, też ich nie wykluczę.

Zmniejszenie zależności ma swoją nagrodę. Uwielbiam otrzymywać opinie na temat tego, jak to uprościć lub przyspieszyć, lub jedno i drugie.

Również jeśli ktoś wie, że jest gotowy do pracy ....

Ok .. Wiem, o czym myślisz ... Dlaczego po prostu nie użyje wpisu removeEldest z LinkedHashMap i cóż, powinienem, ale .... ale .. ale .. To byłoby FIFO, a nie LRU i byliśmy próbując wdrożyć LRU.

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

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

Ten test kończy się niepowodzeniem dla powyższego kodu ...

        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 ();

Oto szybka i brudna pamięć podręczna FIFO przy użyciu metody 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 ();
    }
}

FIFO są szybkie. Żadnego szukania. Możesz ustawić FIFO przed LRU, a to całkiem nieźle poradzi sobie z większością gorących wpisów. Lepszy LRU będzie potrzebował tego odwróconego elementu do funkcji Node.

W każdym razie ... teraz, gdy napisałem jakiś kod, przejdę przez inne odpowiedzi i zobaczę, co przegapiłem ... gdy zeskanowałem je po raz pierwszy.

LinkedHashMapjest O (1), ale wymaga synchronizacji. Nie ma potrzeby ponownego wynajdywania koła.

2 opcje zwiększania współbieżności:

1. Tworzenie wielu LinkedHashMapi mieszania do nich na przykład: LinkedHashMap[4], index 0, 1, 2, 3. Na klawiszu zrób key%4 (lub binary ORwłącz [key, 3]), aby wybrać mapę, którą chcesz umieścić / pobrać / usunąć.

2. Możesz zrobić „prawie” LRU, rozszerzając ConcurrentHashMapi mając połączoną strukturę przypominającą mapę skrótów w każdym z regionów wewnątrz niej. Blokowanie byłoby bardziej szczegółowe niż LinkedHashMapsynchronizacja. Na jednym putlub putIfAbsenttylko kłódce na początku i końcu listy jest potrzebny (na region). Podczas usuwania lub pobierania cały region musi zostać zablokowany. Jestem ciekawy, czy mogą tu pomóc jakieś powiązane listy Atomic - prawdopodobnie tak jest w przypadku głowy listy. Może po więcej.

Struktura nie zachowa całkowitego porządku, ale tylko porządek na region. Tak długo, jak liczba wpisów jest znacznie większa niż liczba regionów, jest to wystarczające dla większości skrytek. Każdy region będzie musiał mieć własną liczbę wjazdów, która będzie używana zamiast globalnej liczby wyzwalającej eksmisję. Domyślna liczba regionów w a ConcurrentHashMapto 16, co jest wystarczające dla większości dzisiejszych serwerów.

1. byłoby łatwiejsze do napisania i szybsze przy umiarkowanej współbieżności.

2. byłoby trudniejsze do napisania, ale znacznie lepsze skalowanie przy bardzo dużej współbieżności. Byłoby wolniejsze dla normalnego dostępu (tak samo, jak ConcurrentHashMapwolniejsze niż w HashMapprzypadku braku współbieżności)

Istnieją dwie implementacje open source.

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

Istnieje projekt typu open source dla ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/

Rozważałbym użycie java.util.concurrent.PriorityBlockingQueue , z priorytetem określanym przez licznik „numberOfUses” w każdym elemencie. Byłbym bardzo, bardzo ostrożny, aby uzyskać poprawną synchronizację, ponieważ licznik „numberOfUses” oznacza, że ​​element nie może być niezmienny.

Obiekt element byłby opakowaniem dla obiektów w pamięci podręcznej:

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

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

    ... etc.
}

Mam nadzieję że to pomoże .

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);
}
}

Pamięć podręczną LRU można zaimplementować za pomocą ConcurrentLinkedQueue i ConcurrentHashMap, które mogą być również używane w scenariuszu wielowątkowym. Głową kolejki jest ten element, który najdłużej znajdował się w kolejce. Ogon kolejki to ten element, który był w kolejce najkrócej. Kiedy element istnieje w Mapie, możemy go usunąć z LinkedQueue i wstawić na końcu.

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);
  }

}

Oto moja implementacja dla LRU. Użyłem PriorityQueue, który w zasadzie działa jako FIFO, a nie Threadafe. Użyty komparator oparty na czasie tworzenia strony i na podstawie kolejności stron według ostatniego używanego czasu.

Strony do rozważenia: 2, 1, 0, 2, 8, 2, 4

Strona dodana do cache to: 2
Strona dodana do cache to: 1
Strona dodana do cache to: 0
Strona: 2 już istnieje w cache. Czas ostatniego dostępu do aktualizacji
Błąd strony, STRONA: 1, Zastąpiona STRONA: 8
Strona dodana do pamięci podręcznej to: 8
Strona: 2 już istnieje w pamięci podręcznej. Czas ostatniego dostępu do aktualizacji
Usterka strony, STRONA: 0, Zastąpiona STRONA: 4
Strona dodana do pamięci podręcznej to: 4

WYNIK

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

Wprowadź kod tutaj

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;
    }
}

Oto moja przetestowana, najlepiej działająca, współbieżna implementacja pamięci podręcznej LRU bez żadnego zsynchronizowanego bloku:

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);
}

}

To jest pamięć podręczna LRU, której używam, która hermetyzuje LinkedHashMap i obsługuje współbieżność z prostą blokadą synchronizacji chroniącą soczyste miejsca. „Dotyka” elementów, gdy są używane, aby ponownie stały się „najświeższym” elementem, tak że jest to właściwie LRU. Miałem również wymóg, aby moje elementy miały minimalną żywotność, którą można również traktować jako dozwolony „maksymalny czas bezczynności”, wtedy jesteś gotowy do eksmisji.

Zgadzam się jednak z konkluzją Hanka i przyjąłem odpowiedź - gdybym zaczynał dzisiaj od nowa, sprawdziłbym guawy 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();
        }
    }

}

Cóż, jeśli chodzi o pamięć podręczną, generalnie będziesz wyszukiwać dane przez obiekt proxy (adres URL, ciąg ...), więc pod względem interfejsu będziesz potrzebować mapy. ale żeby pozbyć się rzeczy, potrzebujesz struktury takiej jak kolejka. Wewnętrznie utrzymywałbym dwie struktury danych, Priority-Queue i HashMap. Oto implementacja, która powinna być w stanie zrobić wszystko w czasie O (1).

Oto klasa, którą przygotowałem dość szybko:

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;
        }       
    }
}

Oto jak to działa. Klucze są przechowywane na połączonej liście, a najstarsze klucze znajdują się na początku listy (nowe klucze znajdują się z tyłu), więc kiedy chcesz coś `` wysunąć '', po prostu zdejmij to z przodu kolejki, a następnie użyj klucza, aby usuń wartość z mapy. Kiedy element zostaje przywołany, pobierasz ValueHolder z mapy, a następnie używasz zmiennej queuelocation, aby usunąć klucz z jego bieżącej lokalizacji w kolejce, a następnie umieszczasz go z tyłu kolejki (jest to teraz ostatnio używany). Dodawanie rzeczy przebiega prawie tak samo.

Jestem pewien, że jest tu mnóstwo błędów i nie zaimplementowałem żadnej synchronizacji. ale ta klasa zapewni O (1) dodawanie do pamięci podręcznej, O (1) usuwanie starych elementów i O (1) pobieranie elementów pamięci podręcznej. Nawet trywialna synchronizacja (po prostu zsynchronizuj każdą metodę publiczną) nadal będzie miała niewielką rywalizację o blokady ze względu na czas wykonywania. Jeśli ktoś ma sprytne sztuczki synchronizacyjne, byłbym bardzo zainteresowany. Jestem również pewien, że istnieją dodatkowe optymalizacje, które można zaimplementować za pomocą zmiennej maxsize w odniesieniu do mapy.

Spójrz na ConcurrentSkipListMap . Powinien dać ci log (n) czas na przetestowanie i usunięcie elementu, jeśli jest już zawarty w pamięci podręcznej, oraz stały czas na ponowne dodanie.

Potrzebowałbyś tylko licznika itp. I elementu opakowującego, aby wymusić zamówienie LRU i upewnić się, że ostatnie rzeczy zostaną odrzucone, gdy pamięć podręczna jest pełna.

Oto moja krótka realizacja, skrytykuj ją lub popraw!

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);
}
}

Oto moja własna implementacja tego problemu

simplelrucache zapewnia bezpieczne wątkowo, bardzo proste, nierozproszone buforowanie LRU z obsługą TTL. Zapewnia dwie implementacje:

• Współbieżne oparte na ConcurrentLinkedHashMap
• Zsynchronizowane w oparciu o LinkedHashMap

Możesz go znaleźć tutaj: http://code.google.com/p/simplelrucache/

Najlepszym sposobem na osiągnięcie tego jest użycie LinkedHashMap, który utrzymuje kolejność wstawiania elementów. Oto przykładowy kod:

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);
}