Содержание

среда, 1 февраля 2012 г.

Java LRU cache

Недавно мне вместо одного простенького кэша в виде хешмапы потребовалось использовать LRU кэш. Т.е. я хотел, чтобы при достижении кэшом какого-то размера, из него начинали выкидываться старые значения, которые давно не использовались. Каково же было мое удивление, что для этого во всем приложении пришлось добавить всего три строчки и не потребовалось подключения какой-либо библиотеки. Но это прокатило только для самого простейшего случая. Если вы хотите использовать LRU кэш, за доступ к которому будет нехилая конкуренция со стороны нескольких потоков, то для того, чтобы это работало эффективно, придется напрячься побольше. Но, давайте, обо всем по порядку.
LRU средствами JDK
Оказывается, если повнимательнее почитать javadoc к классу java.uril.LinkedHashMap, то сразу становиться ясно как создать LRU кэш:
final int MAX_CAPACITY = 1000;
Map<K, V> lruCache = new LinkedHashMap<K, V>(MAX_CAPACITY, 0.75f, true){
 @Override
 protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
  return size() > MAX_CAPACITY; 
    }
};
Данный метод вызывается на каждой вставке, и если он возвращает true, то элемент находящийся в хвосте связанной мапы удаляется. А так как мы передали третьим параметром в конструктор true, то при каждом доступе к данной мапе, зачитываемый элемент будет перемещен в голову коллекции. Таким образом, мы получаем простейший LRU кэш. Описанная логика его работы представлена на рисунке ниже.


LRU в многопоточной среде
Конечно, мы можем поступить топорно, и обернуть уже имеющийся LRU кэш synchronized оберткой.
Map<K, V> threadSafeLRUCache = Collections.synchronizedMap(lruCache);
Однако, как вы сами понимаете, при большом контеншене такой подход будет абсолютно не масштабируемым.

Если вы ярый противник втыкания в ваш девственно чистый код сторонних библиотек, то можно опять же попробовать соорудить что-нибудь на коленке. Как-то взять стандартную имплементацию связанной мапы из concurrency пакета (java.util.concurrent.ConcurrentSkipListMap) и сделать похожий финт, который реализован в java.uril.LinkedHashMap. Там метод removeEldestEntry не реализован, но, думаю, сделать это не составит особого труда. Однако надо помнить, что в мапе на основе скип-листов доступ к элментам будет O(lgN).

Однако я бы вам настоятельно рекомендовал взглянуть на ConcurrentLinkedHashMap, написанную инженером гугл. Он декорировал хорошо зарекомендавшую себя java.util.concurrent.ConcurrentHashMap из JDK, и вынес построения списка связей из рабочего потока в фоновый, введя буфер, как это изображено на картинке ниже.


Создать простейший LRU кэш на основе упомянутой библиотеки можно следующим способом:
ConcurrentMap<K, V> cache = new ConcurrentLinkedHashMap.Builder<K, V>()
    .maximumWeightedCapacity(1000)
    .build();
Согласно бенчмарку автора (размер: 5000, количество потоков: 250, количество ядер: 4), его кэш уступает стандартной java.util.concurrent.ConcurrentHashMap меньше 5% на чтение и меньше 30% на запись.

Так же при желании вы можете с помощью цпециального параметра заменить внутреннее представление, отказавшись от ConcurrentHashMap в пользу не без известной NonBlockingHashMap, что может вам дать большой выигрыш на больших многопроцессорных боксах.

Если вы скептически относитесь к еще нераскрученным решениям, то можете взять CacheBuilder или MapMaker из гугловской библиотеки guava. На сколько я понял код из описанной выше ConcurrentLinkedHashMap уже туда портирован. В MapMaker функционал LRU уже deprecated, так как он перенесен в специально созданный для этого новый класс CacheBuilder, который, правда, в текущей версии еще помечен аннотацией @Beta.
LIRS (Low Interreference Recency Set Replacement)
LRU кэш славиться простотой реализации, но на некоторых паттернах работы он становиться абсолютно беспомощным. Например, если вы будете пробегаться по длинному списку через ваш кэш, размер которого, хотябы немного меньше вашего списка, то такая операция опустошит весь ваш прогретый кэш. А если вы по такому списку буду бегать в цикле, то эффекта кэша вы вообще не заметите. Так же LRU кэш очень плохо работает в ситуации, когда вместимость кэша сильно меньше множества всех элементов, а элементы которые часто используются составляют лишь малую часть всего множества. С политикой LRU они могут постоянно вытесняться редкоиспользуемыми элементами, если их значительно больше. Как пример можно привести кэширование обращений к B-дереву, где хотелось бы закэшировать промежуточные ноды, но листы их постоянно вытесняют.

Со временем было придумано много довольно сложных алгоритмов основанных на распознавании паттерна использования и автоматического переключения политик выталкивания элементов из кэша. Однако существует и алгоритм с довольно простой реализацией, который позволяет эффективно работать в описанных выше ситуациях. Я сейчас говорю о LIRS, идея которого заключается в том, чтобы выталкивать из кэша элементы с наибольшим интервалом между последними двумя использываниями элемента. Реализовать его все же сложнее чем LRU, зато ведет он себя намного адекватнее.

Сейчас ведется его внедрение в уже описанной библиотеке ConcurrentLinkedHashMap, где он появиться, начиная со во второй версии. Будет очень интересно его заценить в действии.
Ссылки