Как бы вы реализовали LRU-кеш в Java?

169

Пожалуйста, не говорите EHCache или OSCache и т. Д. Предположим, что для целей этого вопроса я хочу реализовать свой собственный, используя только SDK (обучение на практике). Учитывая, что кеш будет использоваться в многопоточной среде, какие структуры данных вы бы использовали? Я уже реализовал один, используя LinkedHashMap и Коллекции # synchronizedMap , но мне любопытно, будут ли какие-либо из новых параллельных коллекций более подходящими кандидатами.

ОБНОВЛЕНИЕ: я только что прочитал последние Йегге, когда я нашел этот самородок:

Если вам нужен постоянный доступ и вы хотите поддерживать порядок вставки, вы не можете сделать лучше, чем LinkedHashMap, действительно замечательная структура данных. Единственный способ, которым это могло бы быть более чудесным, - это наличие параллельной версии. Но увы.

Я думал почти то же самое, прежде чем я пошел с LinkedHashMap+Collections#synchronizedMap реализации я упоминал выше. Приятно осознавать, что я что-то не заметил.

Исходя из полученных ответов, мне кажется, что лучшим вариантом для LRU с высокой степенью параллелизма было бы расширение ConcurrentHashMap с использованием той же логики, которая LinkedHashMapиспользуется.

Хэнк Гей
источник
O(1)требуемая версия: stackoverflow.com/questions/23772102/…
Сиро Сантилли 法轮功 冠状 病 六四 事件 法轮功
Очень похожий вопрос также здесь
Mifeet

Ответы:

102

Мне нравятся многие из этих предложений, но сейчас я думаю, что буду придерживаться LinkedHashMap+ Collections.synchronizedMap. Если я еще вернусь к этому в будущем, я, вероятно, буду работать над расширением ConcurrentHashMapтаким же образом, как LinkedHashMapрасширяет HashMap.

ОБНОВИТЬ:

По запросу, вот суть моей текущей реализации.

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));
Хэнк Гей
источник
15
Однако я хотел бы использовать здесь инкапсуляцию вместо наследования. Это то, что я узнал из эффективной Java.
Kapil D
10
@KapilD Это было давно, но я почти уверен, что JavaDocs LinkedHashMapявно одобрил этот метод для создания реализации LRU.
Хэнк Гей
7
@HankGay Java LinkedHashMap (с третьим параметром = true) не является кэшем LRU. Это связано с тем, что повторное размещение записи не влияет на порядок записей (реальный кэш LRU поместит последнюю вставленную запись в
конец
2
@Pacerier Я вообще не вижу такого поведения. С картой доступа, включенной accessOrder, все действия делают запись самой последней использованной (самой свежей): начальная вставка, обновление значения и извлечение значения. Я что-то упускаю?
Esailija
3
@Pacerier "повторное размещение записи не влияет на порядок записей", это неверно. Если вы посмотрите на реализацию LinkedHashMap, для метода «put» он наследует реализацию от HashMap. А Javadoc в HashMap говорит: «Если карта ранее содержала отображение для ключа, старое значение заменяется». И если вы извлекаете его исходный код, то при замене старого значения он вызывает метод recordAccess, а в методе recordAccess LinkedHashMap он выглядит следующим образом: if (lm.accessOrder) {lm.modCount ++; удалять(); addBefore (lm.header);}
nybon
18

Если бы я делал это снова с нуля сегодня, я бы использовал Guava CacheBuilder.

Хэнк Гей
источник
10

Это второй раунд.

Первый раунд был то, что я придумал, затем я перечитал комментарии с доменом, немного более укоренившимся в моей голове.

Итак, вот самая простая версия с модульным тестом, которая показывает, что она работает на основе некоторых других версий.

Сначала не параллельная версия:

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


}

Истинный флаг будет отслеживать доступ получает и кладет. Смотрите JavaDocs. RemoveEdelstEntry без флага true для конструктора просто реализует кеш FIFO (см. Примечания ниже по FIFO и removeEldestEntry).

Вот тест, который доказывает, что он работает как кэш 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 ();

    }

Теперь для параллельной версии ...

пакет 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 ();
    }


}

Вы можете понять, почему я сначала расскажу о несовместимой версии. Вышеприведенное пытается создать несколько полос для уменьшения конкуренции за блокировку. Таким образом, мы хэшируем ключ и затем ищем этот хеш, чтобы найти фактический кеш. Это делает предельный размер скорее предположением / грубым предположением при значительном количестве ошибок, в зависимости от того, насколько хорошо распределен ваш алгоритм хеширования ключей.

Вот тест, чтобы показать, что параллельная версия, вероятно, работает. :) (Испытание под огнем было бы реальным способом).

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



    }

}

Это последний пост. Первый пост, который я удалил, так как это был LFU, а не LRU-кеш.

Я думал, что я сделаю это еще раз. Я пытался найти простейшую версию LRU-кеша, используя стандартную JDK без слишком большой реализации.

Вот что я придумал. Моя первая попытка была немного неудачной, так как я внедрил LFU вместо LRU, а затем я добавил FIFO и поддержку LRU ... и затем я понял, что он становится монстром. Затем я начал разговаривать со своим приятелем Джоном, который едва интересовался, а затем я подробно описал, как я реализовал LFU, LRU и FIFO и как вы можете переключать его с помощью простого аргумента ENUM, и затем я понял, что все, чего я действительно хотел был простой LRU. Так что проигнорируйте мой предыдущий пост и дайте мне знать, если вы хотите увидеть кэш LRU / LFU / FIFO, который можно переключать с помощью enum ... нет? Хорошо .. вот и он.

Простейший из возможных LRU, использующий только JDK. Я реализовал как параллельную версию, так и не параллельную версию.

Я создал общий интерфейс (это минимализм, поэтому, скорее всего, отсутствуют некоторые функции, которые вы хотели бы, но он работает для моих случаев использования, но позвольте, если вы хотите увидеть функцию XYZ, дайте мне знать ... Я живу, чтобы писать код.) ,

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

Вы можете спросить, что такое getSilent . Я использую это для тестирования. getSilent не изменяет оценку LRU элемента.

Сначала не совпадающий ....

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 является потенциально дорогостоящей операцией , если у вас есть большой кэш. Можно взять LinkedList в качестве примера и добавить хэш-карту обратного просмотра от элемента к узлу, чтобы сделать операции удаления ОЧЕНЬ БЫСТРЕЕ и более согласованными. Я тоже начал, но потом понял, что мне это не нужно. Но возможно...

Когда вызывается метод put , ключ добавляется в очередь. Когда получить вызывается , ключ удаляется и снова добавляется в начало очереди.

Если у вас маленький кеш, а создание предмета стоит дорого, то это должен быть хороший кеш. Если ваш кеш очень большой, то линейный поиск может быть узким местом, особенно если у вас нет горячих областей кеша. Чем интенсивнее горячие точки, тем быстрее линейный поиск, поскольку горячие объекты всегда находятся на вершине линейного поиска. В любом случае ... для ускорения процесса необходимо написать еще один LinkedList, в котором есть операция удаления, которая имеет обратный элемент для поиска узлов для удаления, тогда удаление будет примерно таким же быстрым, как удаление ключа из хэш-карты.

Если у вас есть кеш менее 1000 элементов, это должно работать нормально.

Вот простой тест, чтобы показать его действия в действии.

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

    }
}

Последний LRU-кэш был однопоточным, и, пожалуйста, не включайте его в синхронизированный файл ...

Вот удар по параллельной версии.

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

Основными отличиями являются использование ConcurrentHashMap вместо HashMap и использование блокировки (я мог бы обойтись без синхронизации, но ...).

Я не тестировал его под огнем, но он выглядит как простой кэш LRU, который может сработать в 80% случаев, когда вам нужна простая карта LRU.

Я приветствую обратную связь, за исключением того, почему вы не используете библиотеку a, b или c. Причина, по которой я не всегда использую библиотеку, заключается в том, что я не всегда хочу, чтобы каждый war-файл занимал 80 МБ, и я пишу библиотеки, поэтому я стремлюсь сделать библиотеки подключаемыми с достаточно хорошим решением, и кто-то может подключить -в другом провайдере кэша, если им нравится. :) Я никогда не знаю, когда кому-то может понадобиться Guava или ehcache или что-то еще, я не хочу их включать, но если я сделаю кэширование подключаемым, я тоже не буду исключать их.

Сокращение зависимостей имеет свою награду. Мне нравится получать отзывы о том, как сделать это еще проще, быстрее или и то, и другое.

Также, если кто-нибудь знает о готовом к работе ....

Хорошо ... Я знаю, о чем вы думаете ... Почему он просто не использует запись removeEldest из LinkedHashMap, и хорошо, но я должен, но .... но ... но .. Это было бы FIFO, а не LRU, и мы были пытаясь реализовать LRU.

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

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

Этот тест не проходит для приведенного выше кода ...

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

Итак, вот быстрый и грязный FIFO-кеш с использованием 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 быстрые. Нет поиска вокруг. Вы могли бы выставить FIFO перед LRU, и это очень хорошо обработало бы самые горячие записи. Лучшему LRU понадобится этот обратный элемент для функции Node.

Во всяком случае ... теперь, когда я написал некоторый код, позвольте мне пройтись по другим ответам и посмотреть, что я пропустил ... при первом сканировании.

RickHigh
источник
9

LinkedHashMapявляется O (1), но требует синхронизации. Не нужно изобретать велосипед там.

2 варианта увеличения параллелизма:

1. Создайте несколько LinkedHashMap, и хэш в них: пример: LinkedHashMap[4], index 0, 1, 2, 3. На клавише do key%4 (или binary ORon [key, 3]) выберите карту для установки / получения / удаления.

2. Вы могли бы создать «почти» LRU, расширив его ConcurrentHashMapи добавив структуру хеш-карты, подобную структуре, в каждой из областей внутри него. Блокировка будет происходить более детально, чем LinkedHashMapсинхронизация. На putили putIfAbsentтолько блокировка головы и хвоста списка необходима (для региона). При удалении или получении весь регион должен быть заблокирован. Мне любопытно, могут ли здесь помочь какие-то списки связанных списков Atomic, вероятно, для главы списка. Возможно для большего.

Структура будет хранить не общий заказ, а только заказ на регион. Пока количество записей намного больше, чем количество регионов, этого достаточно для большинства кэшей. Каждый регион должен иметь свой собственный счетчик записей, который будет использоваться вместо глобального счета для триггера выселения. Число областей по умолчанию в a ConcurrentHashMapравно 16, что достаточно для большинства серверов сегодня.

  1. было бы легче написать и быстрее при умеренном параллелизме.

  2. было бы сложнее написать, но масштабировать намного лучше при очень высоком параллелизме. Это было бы медленнее для нормального доступа (так же, как ConcurrentHashMapмедленнее, чем HashMapпри отсутствии параллелизма)

jiaweizhang
источник
8

Есть две реализации с открытым исходным кодом.

Apache Solr имеет ConcurrentLRUCache: https://lucene.apache.org/solr/3_6_1/org/apache/solr/util/ConcurrentLRUCache.html

Существует проект с открытым исходным кодом для ConcurrentLinkedHashMap: http://code.google.com/p/concurrentlinkedhashmap/

Рон
источник
2
Решение Solr на самом деле не LRU, но ConcurrentLinkedHashMapэто интересно. Он утверждает, что был свернут вMapMaker из Гуавы, но я не нашел его в документах. Есть идеи, что происходит с этими усилиями?
Хэнк Гей
3
Упрощенная версия была интегрирована, но тесты еще не завершены, поэтому она еще не опубликована. У меня было много проблем с более глубокой интеграцией, но я надеюсь завершить ее, поскольку есть некоторые хорошие алгоритмические свойства. Возможность прослушивания выселения (емкость, истечение срока действия, сборщик мусора) была добавлена ​​и основана на подходе CLHM (очередь слушателей). Я также хотел бы внести идею «взвешенных значений», поскольку это полезно при кэшировании коллекций. К сожалению, из-за других обязательств я был слишком занят, чтобы посвятить время, которое заслуживает Гуава (и то, что я обещал Кевину / Чарльзу).
Бен Мейн
3
Обновление: Интеграция была завершена и опубликована в Guava r08. Это через параметр #maximumSize ().
Бен Мейн
7

Я хотел бы рассмотреть возможность использования java.util.concurrent.PriorityBlockingQueue с приоритетом, определяемым счетчиком «numberOfUses» в каждом элементе. Я был бы очень, очень осторожен, чтобы все мои синхронизации были правильными, поскольку счетчик «numberOfUses» подразумевает, что элемент не может быть неизменным.

Элемент object будет оболочкой для объектов в кеше:

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

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

    ... etc.
}
Стив Маклеод
источник
Разве вы не имеете в виду, должен быть неизменным?
Штеймер
2
обратите внимание, что если вы попытаетесь сделать версию priorityblockingqueue, упомянутую steve mcleod, вы должны сделать элемент неизменяемым, потому что изменение элемента в очереди не окажет никакого влияния, вам нужно будет удалить элемент и повторно добавить его, чтобы переориентировать это.
Джеймс
Джеймс ниже указывает на ошибку, которую я сделал. Который я предлагаю в качестве доказательства того, насколько трудно кровоточить, чтобы писать надежные и надежные кеши.
Стив Маклеод
6

Надеюсь это поможет .

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
источник
1
Хороший пример! Не могли бы вы прокомментировать, почему нужно установить емкость maxSize * 4/3?
Аквел
1
@Akvel, он называется начальной емкостью, может быть любым [целочисленным] значением, тогда как 0,75f является коэффициентом загрузки по умолчанию, надеюсь, эта ссылка поможет: ashishsharma.me/2011/09/custom-lru-cache-java.html
murasing
5

Кэш LRU может быть реализован с использованием ConcurrentLinkedQueue и ConcurrentHashMap, которые также могут использоваться в сценарии многопоточности. Голова очереди - это тот элемент, который находился в очереди дольше всего. Хвост очереди - это тот элемент, который находился в очереди кратчайшее время. Когда элемент существует на карте, мы можем удалить его из LinkedQueue и вставить его в хвост.

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
источник
Это не потокобезопасно. Например, вы можете легко превысить максимальный размер LRU, одновременно вызывая put.
dpeacock
Пожалуйста, исправьте это. Прежде всего, он не компилируется в строку map.containsKey (ключ). Во-вторых, в get () вы должны проверить, действительно ли был удален ключ, иначе map и queue не синхронизированы, а queue.size ()> = size всегда становится true. Я опубликую свою версию, исправив ее, так как мне понравилась ваша идея использовать эти две коллекции.
Александр Лех
3

Вот моя реализация для LRU. Я использовал PriorityQueue, который в основном работает как FIFO, а не как потокобезопасный. Используемый компаратор на основе создания времени страницы и на основе выполняет упорядочивание страниц за наименее использованное время.

Страницы для рассмотрения: 2, 1, 0, 2, 8, 2, 4

Страница добавлена ​​в кеш: 2
Страница добавлена ​​в кеш: 1
Страница добавлена ​​в кеш: 0
Страница: 2 уже существует в кеше. Время последнего доступа обновлено.
Ошибка страницы, PAGE: 1, заменена на PAGE: 8
Страница, добавленная в кэш: 8
Страница: 2 уже существует в кеше. Время последнего обращения к обновленной
странице Ошибка, PAGE: 0, заменено на PAGE: 4
Страница, добавленная в кеш: 4

ВЫВОД

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

введите код сюда

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;
    }
}
Дипак Сингхви
источник
2

Вот моя проверенная наиболее эффективная параллельная реализация кэша LRU без какого-либо синхронизированного блока:

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

}

Золтан Бода
источник
1
@zoltan boda .... вы не справились с одной ситуацией ... что если один и тот же объект используется несколько раз? в этом случае мы не должны добавлять несколько записей для одного и того же объекта ... вместо этого его ключ должен быть
5
Предупреждение: это не кэш LRU. В кеше LRU вы выбрасываете элементы, к которым недавно обращались. Этот выбрасывает предметы, написанные не так давно. Это также линейное сканирование для выполнения операции queue.remove (key).
Дейв Л.
Также ConcurrentLinkedQueue # size () не является операцией с постоянным временем.
NateS
3
Ваш метод put не выглядит безопасным - у него есть несколько операторов check-then-act, которые порвутся с несколькими потоками.
assylias
2

Это кеш LRU, который я использую, который инкапсулирует LinkedHashMap и обрабатывает параллелизм с помощью простой блокировки синхронизации, защищающей сочные участки. Он «касается» элементов по мере их использования, чтобы они снова стали «самыми свежими» элементами, так что это фактически LRU. У меня также было требование, чтобы у моих элементов была минимальная продолжительность жизни, которую вы также можете считать «максимальным временем простоя», тогда вы готовы к выселению.

Тем не менее, я согласен с выводом Хэнка и принятым ответом - если бы я начал это сегодня снова, я бы проверил мнение Гуавы 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
источник
2

Что касается кеша, вы, как правило, будете искать часть данных через прокси-объект (URL, String ....), поэтому для интерфейса вам понадобится карта. но чтобы выкинуть вещи, вам нужна очередь, такая как структура. Внутренне я бы поддерживал две структуры данных, Priority-Queue и HashMap. Вот реализация, которая должна быть в состоянии сделать все за O (1) времени.

Вот класс, который я довольно быстро взбил:

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

Вот как это работает. Ключи хранятся в связанном списке с самыми старыми ключами в начале списка (новые ключи идут назад), поэтому, когда вам нужно «извлечь» что-то, вы просто выталкиваете его из передней части очереди, а затем используете клавишу для удалить значение с карты. Когда на элемент ссылаются, вы берете ValueHolder с карты, а затем используете переменную queuelocation, чтобы удалить ключ из его текущего местоположения в очереди, а затем поместить его в конец очереди (теперь он используется самым последним). Добавление вещей - это почти то же самое.

Я уверен, что здесь куча ошибок, и я не реализовал никакой синхронизации. но этот класс обеспечит O (1) добавление в кеш, O (1) удаление старых элементов и O (1) извлечение элементов кеша. Даже обычная синхронизация (просто синхронизировать каждый публичный метод) все равно будет иметь небольшую конкуренцию за блокировку из-за времени выполнения. Если у кого-нибудь есть какие-нибудь хитрые приемы синхронизации, мне было бы очень интересно. Кроме того, я уверен, что есть некоторые дополнительные оптимизации, которые вы могли бы реализовать, используя переменную maxsize относительно карты.

Люк
источник
Спасибо за уровень детализации, но где это обеспечивает победу над реализацией LinkedHashMap+ Collections.synchronizedMap()?
Хэнк Гей
Производительность, я не знаю точно, но я не думаю, что LinkedHashMap имеет вставку O (1) (вероятно, это O (log (n))), на самом деле вы можете добавить несколько методов для завершения интерфейса карты в моей реализации а затем используйте Collections.synchronizedMap для добавления параллелизма.
Луки
В приведенном выше классе LinkedList в методе add есть код в блоке else, т.е. if (tail.prev == null) {tail.prev = head; head.next = tail; } Когда этот код будет выполнен? Я провел несколько пробных прогонов, и я думаю, что это никогда не будет выполнено и должно быть удалено.
Дипеш
1

Посмотрите на ConcurrentSkipListMap . Это должно дать вам log (n) время для тестирования и удаления элемента, если он уже содержится в кэше, и постоянное время для его повторного добавления.

Вам просто понадобится некоторый счетчик и т. Д. И элемент-обертка, чтобы принудительно упорядочить порядок LRU и убедиться, что последние данные отбрасываются, когда кэш заполнен.

madlep
источник
Может ли это ConcurrentSkipListMapдать преимущество в простоте реализации ConcurrentHashMapили это просто случай избежать патологических случаев?
Хэнк Гей
Это упростит задачу, так как ConcurrentSkipListMap упорядочивает элементы, что позволит вам управлять тем, в каком порядке использовались элементы. ConcurrentHashMap этого не делает, поэтому вам придется в основном перебирать все содержимое кэша, чтобы обновить последний элемент используется счетчик "или что-то еще
madlep
Так что с ConcurrentSkipListMapреализацией, я бы создал новую реализацию Mapинтерфейса, который делегирует ConcurrentSkipListMapи выполняет какое-то обертывание, чтобы произвольные типы ключей были обернуты в тип, который легко сортируется на основе последнего доступа?
Хэнк Гей
1

Вот моя короткая реализация, пожалуйста, критикуйте или улучшайте ее!

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);
}
}
Золтан Бода
источник
1
Это не LRU-кеш, просто FIFO-кеш.
lslab
1

Вот моя собственная реализация этой проблемы

simplelrucache обеспечивает потоковое, очень простое, нераспределенное LRU-кэширование с поддержкой TTL Он обеспечивает две реализации:

  • Параллельный на основе ConcurrentLinkedHashMap
  • Синхронизируется на основе LinkedHashMap

Вы можете найти его здесь: http://code.google.com/p/simplelrucache/

Даймон
источник
1

Лучший способ добиться этого - использовать LinkedHashMap, который поддерживает порядок вставки элементов. Ниже приведен пример кода:

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

}

Дирендра Гаутам
источник
0

Я ищу лучший кэш LRU с использованием кода Java. Можно ли поделиться кодом кеша Java LRU с помощью LinkedHashMapи Collections#synchronizedMap? В настоящее время я использую, LRUMap implements Mapи код работает нормально, но я ArrayIndexOutofBoundExceptionиспользую нагрузочное тестирование с использованием 500 пользователей по приведенному ниже методу. Метод перемещает последний объект в начало очереди.

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)и put(Object key, Object value)метод вызывает вышеуказанный moveToFrontметод.

Радж Пандиан
источник
0

Хотел добавить комментарий к ответу, данному Хэнком, но кое-что, как я не могу - пожалуйста, относитесь к нему как к комментарию

LinkedHashMap также поддерживает порядок доступа на основе параметра, переданного в его конструкторе. Он поддерживает двунаправленный список для поддержания порядка (см. LinkedHashMap.Entry).

@Pacerier это правильно, что LinkedHashMap сохраняет тот же порядок во время итерации, если элемент добавляется снова, но это только в случае режима порядка вставки.

это то, что я нашел в документации по Java объекта 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);
        }
    }

этот метод заботится о перемещении недавно использованного элемента в конец списка. В общем, LinkedHashMap - лучшая структура данных для реализации LRUCache.

Абхишек Гаяквад
источник
0

Еще одна мысль и даже простая реализация, использующая коллекцию Java LinkedHashMap.

LinkedHashMap предоставляет метод removeEldestEntry, который может быть переопределен способом, упомянутым в примере. По умолчанию реализация этой структуры коллекции ложна. Если его истинность и размер этой структуры выходят за пределы первоначальной емкости, то старые или более старые элементы будут удалены.

У нас может быть pageno и содержимое страницы, в моем случае pageno является целым числом и содержанием страницы. Я сохранил строку значений номера страницы.

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

     }

}

Результат выполнения вышеуказанного кода выглядит следующим образом:

 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 
Дипак Сингхви
источник
Это ФИФО. Он попросил LRU.
RickHigh
Не проходит этот тест ... 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 || умереть (); ok | = cache.getSilent (3) == 3 || умереть (); ok | = cache.getSilent (4) == null || умереть (); ok | = cache.getSilent (5) == null || умереть ();
RickHigh
0

Следуя концепции @sanjanab (но после исправлений), я сделал свою версию LRUCache, предоставив также Consumer, который позволяет делать что-то с удаленными элементами при необходимости.

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);
    }
}
Александр лех
источник