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

169

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.

Hank Gay
źródło
O(1)wymagana wersja: stackoverflow.com/questions/23772102/…
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
Bardzo podobne pytanie również tutaj
Mifeet

Odpowiedzi:

102

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));
Hank Gay
źródło
15
Chciałbym jednak użyć tutaj hermetyzacji zamiast dziedziczenia. Tego nauczyłem się z Effective Java.
Kapil D
10
@KapilD Minęło trochę czasu, ale jestem prawie pewien, że JavaDocs LinkedHashMapwyraźnie popiera tę metodę tworzenia implementacji LRU.
Hank Gay
7
@HankGay Java's LinkedHashMap (z trzecim parametrem = true) nie jest pamięcią podręczną LRU. Dzieje się tak, ponieważ ponowne umieszczenie wpisu nie wpływa na kolejność wpisów (prawdziwa pamięć podręczna LRU umieści ostatnio wstawiony wpis z tyłu kolejności iteracji, niezależnie od tego, czy ten wpis początkowo istnieje w pamięci podręcznej)
Pacerier
2
@Pacerier W ogóle nie widzę tego zachowania. Przy włączonej mapie accessOrder wszystkie akcje tworzą wpis jako ostatnio używany (najświeższy): wstępne wstawienie, aktualizacja wartości i pobranie wartości. Czy coś mi brakuje?
Esailija
3
@Pacerier „ponowne wstawienie wpisu nie wpływa na kolejność wpisów”, to jest niepoprawne. Jeśli spojrzysz na implementację LinkedHashMap, metoda "put" dziedziczy implementację z HashMap. A Javadoc HashMap mówi: „Jeśli mapa zawierała wcześniej mapowanie klucza, stara wartość jest zastępowana”. A jeśli sprawdzisz jego kod źródłowy, podmieniając starą wartość, wywoła metodę recordAccess, aw metodzie recordAccess LinkedHashMap wygląda to tak: if (lm.accessOrder) {lm.modCount ++; usunąć(); addBefore (lm.header);}
nybon
18

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

Hank Gay
źródło
10

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.

RickHigh
źródło
9

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)

jiaweizhang
źródło
8

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/

Ron
źródło
2
Rozwiązanie Solr nie jest w rzeczywistości LRU, ale ConcurrentLinkedHashMapjest interesujące. Twierdzi, że został wtoczony MapMakerz guawy, ale nie zauważyłem tego w dokumentach. Masz jakiś pomysł, co się dzieje z tym wysiłkiem?
Hank Gay
3
Zintegrowano wersję uproszczoną, ale testy nie zostały zakończone, więc nie jest jeszcze publiczna. Miałem wiele problemów z głębszą integracją, ale mam nadzieję, że ją zakończę, ponieważ jest kilka fajnych właściwości algorytmicznych. Dodano możliwość odsłuchiwania eksmisji (pojemność, wygaśnięcie, GC) i jest ona oparta na podejściu CLHM (kolejka nasłuchiwania). Chciałbym również przedstawić ideę „wartości ważonych”, ponieważ jest to przydatne podczas buforowania kolekcji. Niestety z powodu innych zobowiązań byłem zbyt zalany, aby poświęcić czas, na jaki Guava zasługuje (i to obiecałem Kevinowi / Charlesowi).
Ben Manes
3
Aktualizacja: Integracja została zakończona i publiczna w Guava r08. To poprzez ustawienie #maximumSize ().
Ben Manes,
7

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.
}
Steve McLeod
źródło
nie masz na myśli, że musi być niezmienny?
shsteimer
2
zwróć uwagę, że jeśli spróbujesz wykonać wersję Priorityblockingqueue, o której wspomniał steve mcleod, powinieneś uczynić element niezmiennym, ponieważ modyfikowanie elementu w kolejce nie będzie miało żadnego wpływu, będziesz musiał usunąć element i dodać go ponownie, aby ponownie ustal priorytety.
james
James poniżej wskazuje na błąd, który popełniłem. Które podaję jako dowód na to, jak trudno jest pisać niezawodne, solidne skrytki.
Steve McLeod
6

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);
}
}
murasing
źródło
1
Niezły przykład! Czy mógłbyś skomentować, dlaczego trzeba ustawić pojemność maxSize * 4/3?
Akvel
1
@Akvel nazywa się to początkową pojemnością, może być dowolną wartością całkowitą, podczas gdy 0,75f jest domyślnym współczynnikiem obciążenia, mam nadzieję, że ten link pomoże: ashishsharma.me/2011/09/custom-lru-cache-java.html
murasing
5

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

}
sanjanab
źródło
To nie jest bezpieczne dla wątków. Na przykład możesz łatwo przekroczyć maksymalny rozmiar LRU, dzwoniąc jednocześnie put.
dpeacock
Proszę popraw to. Przede wszystkim nie kompiluje się on na linii map.containsKey (klucz). Po drugie, w get () powinieneś sprawdzić, czy klucz został rzeczywiście usunięty, w przeciwnym razie mapowanie i kolejka stracą synchronizację, a "queue.size ()> = size" stanie się zawsze prawdziwe. Opublikuję moją wersję po naprawieniu tego, ponieważ spodobał mi się twój pomysł wykorzystania tych dwóch kolekcji.
Aleksander Lech
3

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;
    }
}
Deepak Singhvi
źródło
2

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

}

Zoltan Boda
źródło
1
@zoltan boda .... nie poradziłeś sobie z jedną sytuacją ... a co, jeśli ten sam obiekt zostanie użyty wiele razy? w tym przypadku nie powinniśmy dodawać wielu wpisów dla tego samego obiektu ... zamiast tego jego klucz powinien być
5
Ostrzeżenie: to nie jest pamięć podręczna LRU. W pamięci podręcznej LRU wyrzucasz elementy, do których ostatnio uzyskano dostęp. Ten wyrzuca pozycje ostatnio napisane. Jest to również skanowanie liniowe w celu wykonania operacji queue.remove (klucz).
Dave L.
Również ConcurrentLinkedQueue # size () nie jest operacją o stałym czasie.
NateS
3
Twoja metoda put nie wygląda na bezpieczną - zawiera kilka instrukcji check-then-act, które zrywają z wieloma wątkami.
asylias
2

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

}
broc.seib
źródło
2

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.

Łukasz
źródło
Dzięki za poziom szczegółowości, ale gdzie to daje przewagę nad wdrożeniem LinkedHashMap+ Collections.synchronizedMap()?
Hank Gay
Wydajność, nie wiem na pewno, ale nie sądzę, że LinkedHashMap ma wstawienie O (1) (prawdopodobnie jest to O (log (n))), właściwie można dodać kilka metod, aby uzupełnić interfejs mapy w mojej implementacji a następnie użyj Collections.synchronizedMap, aby dodać współbieżność.
Łukasz
W klasie LinkedList powyżej w metodzie add znajduje się kod w bloku else, tj. If (tail.prev == null) {tail.prev = head; head.next = tail; } Kiedy ten kod zostanie wykonany? Przeprowadziłem kilka prób i myślę, że to nigdy nie zostanie wykonane i powinno zostać usunięte.
Dipesh
1

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.

madlep
źródło
Zapewniłoby to ConcurrentSkipListMapjakąś korzyść w zakresie łatwości wdrożenia ConcurrentHashMap, czy jest to po prostu przypadek uniknięcia patologicznych przypadków?
Hank Gay
Ułatwiłoby to sprawę, ponieważ ConcurrentSkipListMap porządkuje elementy, co pozwoliłoby Ci zarządzać kolejnością, w jakiej zostały użyte. ConcurrentHashMap tego nie robi, więc w zasadzie trzeba by iterować całą zawartość pamięci podręcznej, aby zaktualizować ostatni element used counter 'or cokolwiek
madlep
Tak więc z ConcurrentSkipListMapimplementacją utworzyłbym nową implementację Mapinterfejsu, który deleguje ConcurrentSkipListMapi wykonuje pewnego rodzaju zawijanie, tak aby arbitralne typy kluczy były opakowane w typ, który można łatwo sortować na podstawie ostatniego dostępu?
Hank Gay
1

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);
}
}
Zoltan Boda
źródło
1
To nie jest pamięć podręczna LRU, tylko pamięć podręczna FIFO.
lslab
1

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/

Daimon
źródło
1

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

}

Dhirendra Gautam
źródło
0

Szukam lepszej pamięci podręcznej LRU przy użyciu kodu Java. Czy jest możliwe udostępnianie kodu pamięci podręcznej Java LRU przy użyciu LinkedHashMapi Collections#synchronizedMap? Obecnie używam LRUMap implements Mapi kod działa dobrze, ale przechodzę ArrayIndexOutofBoundExceptiondo testów obciążenia przy użyciu 500 użytkowników według poniższej metody. Metoda przenosi ostatni obiekt na początek kolejki.

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

get(Object key)a put(Object key, Object value)metoda wywołuje powyższą moveToFrontmetodę.

Raj Pandian
źródło
0

Chciałem dodać komentarz do odpowiedzi udzielonej przez Hanka ale trochę jak nie jestem w stanie - potraktuj to jako komentarz

LinkedHashMap utrzymuje również kolejność dostępu w oparciu o parametr przekazany w jego konstruktorze. Zachowuje podwójną listę w celu utrzymania porządku (patrz LinkedHashMap.Entry)

@Pacerier to prawda, że ​​LinkedHashMap zachowuje tę samą kolejność podczas iteracji, jeśli element jest dodawany ponownie, ale to tylko w przypadku trybu zamówienia wstawiania.

to właśnie znalazłem w dokumentach java obiektu LinkedHashMap.Entry

    /**
     * This method is invoked by the superclass whenever the value
     * of a pre-existing entry is read by Map.get or modified by Map.set.
     * If the enclosing Map is access-ordered, it moves the entry
     * to the end of the list; otherwise, it does nothing.
     */
    void recordAccess(HashMap<K,V> m) {
        LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
        if (lm.accessOrder) {
            lm.modCount++;
            remove();
            addBefore(lm.header);
        }
    }

ta metoda dba o przeniesienie ostatnio otwieranego elementu na koniec listy. Podsumowując, LinkedHashMap to najlepsza struktura danych do implementacji LRUCache.

Abhishek Gayakwad
źródło
0

Kolejna myśl, a nawet prosta implementacja z wykorzystaniem kolekcji Java LinkedHashMap.

LinkedHashMap udostępnił metodę removeEldestEntry, którą można przesłonić w sposób opisany w przykładzie. Domyślnie implementacja tej struktury kolekcji jest fałszywa. Jeśli jej prawda i rozmiar tej struktury przekracza początkową pojemność, najstarsze lub starsze elementy zostaną usunięte.

Możemy mieć pageno i zawartość strony w moim przypadku pageno to liczba całkowita, a zawartość strony zachowałem ciąg wartości numeru strony.

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

/**
 * @author Deepak Singhvi
 *
 */
public class LRUCacheUsingLinkedHashMap {


     private static int CACHE_SIZE = 3;
     public static void main(String[] args) {
        System.out.println(" Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99");
        System.out.println("----------------------------------------------\n");


// accessOrder is true, so whenever any page gets changed or accessed,    // its order will change in the map, 
              LinkedHashMap<Integer,String> lruCache = new              
                 LinkedHashMap<Integer,String>(CACHE_SIZE, .75F, true) {

           private static final long serialVersionUID = 1L;

           protected boolean removeEldestEntry(Map.Entry<Integer,String>                           

                     eldest) {
                          return size() > CACHE_SIZE;
                     }

                };

  lruCache.put(2, "2");
  lruCache.put(1, "1");
  lruCache.put(0, "0");
  System.out.println(lruCache + "  , After first 3 pages in cache");
  lruCache.put(2, "2");
  System.out.println(lruCache + "  , Page 2 became the latest page in the cache");
  lruCache.put(8, "8");
  System.out.println(lruCache + "  , Adding page 8, which removes eldest element 2 ");
  lruCache.put(2, "2");
  System.out.println(lruCache+ "  , Page 2 became the latest page in the cache");
  lruCache.put(4, "4");
  System.out.println(lruCache+ "  , Adding page 4, which removes eldest element 1 ");
  lruCache.put(99, "99");
  System.out.println(lruCache + " , Adding page 99, which removes eldest element 8 ");

     }

}

Wynik wykonania powyższego kodu jest następujący:

 Pages for consideration : 2, 1, 0, 2, 8, 2, 4,99
--------------------------------------------------
    {2=2, 1=1, 0=0}  , After first 3 pages in cache
    {2=2, 1=1, 0=0}  , Page 2 became the latest page in the cache
    {1=1, 0=0, 8=8}  , Adding page 8, which removes eldest element 2 
    {0=0, 8=8, 2=2}  , Page 2 became the latest page in the cache
    {8=8, 2=2, 4=4}  , Adding page 4, which removes eldest element 1 
    {2=2, 4=4, 99=99} , Adding page 99, which removes eldest element 8 
Deepak Singhvi
źródło
To jest FIFO. Poprosił o LRU.
RickHigh
Test nie powiódł się ... 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 ();
RickHigh
0

Zgodnie z koncepcją @sanjanab (ale po poprawkach) wykonałem swoją wersję LRUCache, zapewniając również Konsumenta, który w razie potrzeby pozwala zrobić coś z usuniętymi elementami.

public class LRUCache<K, V> {

    private ConcurrentHashMap<K, V> map;
    private final Consumer<V> onRemove;
    private ConcurrentLinkedQueue<K> queue;
    private final int size;

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

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

    public void put(K key, V value) {
        //ConcurrentHashMap doesn't allow null key or values
        if (key == null || value == null) throw new IllegalArgumentException("key and value cannot be null!");

        V existing = map.get(key);
        if (existing != null) {
            queue.remove(key);
            onRemove.accept(existing);
        }

        if (map.size() >= size) {
            K lruKey = queue.poll();
            if (lruKey != null) {
                V removed = map.remove(lruKey);
                onRemove.accept(removed);
            }
        }
        queue.add(key);
        map.put(key, value);
    }
}
Aleksander Lech
źródło