Как правило, статьи о кешировании начинаются за здравие, а заканчиваются LRU кешем. Попробуем переломить эту тенденцию? Начнем с того, чем LRU плох, а закончим за здравие. Я надеюсь.
Вне зависимости от того, строите ли вы хайлоад сервис для миллионов посетителей или проектируете мобильное приложение, пишите операционную систему или СУБД — ключевое звено, влияющее на конечную стоимость системы и на отзывчивость интерфейса/сервиса — это кеш.
Спрашивая на собеседованиях какие алгоритмы кеширования вы знаете — как правило слышишь в ответ, ммм… LRU Cache… Зато если спросить про алгоритмы сортировки, вероятность услышать что-то помимо «Пузырек» — значительно выше. Человек готов потратить несколько дней на поиск оптимальной библиотеки ресайза изображений или веб фреймворка, не понимая, что реализовав эффективный кеш, он может взять в принципе любую библиотеку со схожими характеристиками, так как кеш — минимизирует обращения к ней, сгладив разницу в быстродействии.
Для Relap.io, как для хайлоад сервиса, кеширование особенно важно. Например, вчера мы показали рекомендации на различных сайтах 789301033 раз. Поэтому у нас густо обмазано кешем все: рекомендации, картинки, реклама и так далее.
Не все кеши одинаково полезны
Хороший пример LRU Cache.
На конкурсы алгоритмов его обычно не берут. Никто не хочет иметь ничего общего с неудачником. Сложно придумать более неэффективный алгоритм. Единственный алгоритм, у которого LRU Cache выигрывает по эффективности — это, наверно, просто очередь, например, FIFO. Тем не менее, LRU встроен везде и всюду как дефолтный и, к сожалению, часто единственный алгоритм, так как он прост в реализации.
Вам хотелось бы пользоваться сайтом, приложением или операционной системой, которая тормозит, неэффективна и жрет ресурсы как не в себя, но зато она написана на простом в реализации языке, например, условном бейсике? Если нет — добро пожаловать под кат.
Я люблю правило Парето. На стат значимой выборке его можно применять абсолютно ко всему.
Давайте попробуем:
- 20% усилий приносят 80% результата,
- 20% товаров приносят 80% прибыли,
- на 20% урлов приходится 80% просмотров,
- 20% кода реализуют 80% функционала.
Это довольно интересная закономерность справедливая для больших массивов данных. Казалось бы, причем тут Парето?
<Лирическое отступление>
Несколько лет назад мы писали приложение под андроид для Surfingbird. Мы перешли на RX Java. Асинхронизировали все что можно. Сгладили все переходы анимацией, тем не менее осталась одна нерешенная проблема, это постоянные перезагрузки картинок. И ваше приложение буквально кишит картинками, и они постоянно ротируются меняются и вам не хватает памяти для их размещения.
Признаюсь, я поначалу думал что все дело в имаджлоадере. Достаточно выбрать эффективный и вуаля. Я пересмотрел все. Пикассо, Фейсбуковский fresco, UIL не помню уже все названия. Но проблема оставалась. Картинки грузились где то чуть быстрее, где то чуть плавнее, но они грузились. Тогда я сел, и написал свой. Простой. Чистый. Легкий. И это не помогло. Глупые имаджлоадеры продолжали постоянно теребить картинки нервируя пользователя и никак не могли отделить зерна от плевел. Тогда я вспомнил о правиле Парето.
</Лирическое отступление>
Если предположить, что 20% картинок — показываются 80% раз — все встает на свои места. Единственное что осталось понять — какие именно картинки надо хранить.
Как работает LRU cache?
Давайте рассмотрим сферическое приложение в вакууме. Пусть это будет мессенджер, его проще всего представить.
скриншот_из_телеграмм.jpg
Если внимательно посмотреть на скриншот, то можно увидеть, что сообщения пользователей сопровождаются аватарками, а в теле сообщений — встречаются картинки. Перед вами стоит задача — сделать максимально плавный интерфейс. Давайте еще раз взглянем на скриншот выше. Мы видим 2 повторяющиеся автарки в диалоге, и затем юзер 1 прислал большую картинку.
- Пришла аватарка 1 — 100 на 100 пикселей, мы записали в кеш 100*100*4 байт.
- Пришла аватарка 2 — 100 на 100 пикселей, мы записали в кеш 100*100*4 байт.
- Пришла аватарка 1 — мы подняли ее в очереди наверх.
Пока все идет неплохо.
Пришла картинка 1024 на 768 пикселей, мы записали в кеш 1024*768*4 байт — и БАМ! Наши прекрасные аватарки выбило напрочь из кеша. Теперь там торжественно валяется картинка, которую нужно было показать один раз и не нужно было кешировать.
Как победить?
Если посмотреть, например, на библиотеку AQuery, то разработчик предлагает разделить кеш на несколько кучек. Отдельная кучка для маленьких аватарок, отдельная кучка для больших картинок. Уже хлеб кстати, но это решение не универсально, требует программирования и внимания, а хочется всего и сразу. Так как все интересное уже было придумано до нас — самое время взглянуть на то, какие еще существуют алгоритмы кеширования.
Статья в вики
Простите, что я тут чуть чуть сжухлю, и опишу очень коротко прописные истины.
LRU — не использованный дольше всех вылетает из кеша.
MRU — последний использованный вылетает из кеша (специфичный кейс, бережем старье).
LFU — реже всего использованный вылетает из кеша.
Это база. Вас может испугать что затраты на вычисления растут с ростом сложности алгоритмов, но не критично. Попробуйте сравнить время лукапов по ключам в памяти со временем рендеринга картинки 1024 на 768. А именно это произойдет если алгоритм «промахнулся».
SNLRU (сегментированный LRU) — заводим несколько «коробочек» с LRU. Сперва кладем в первую коробочку, при повтороном запросе перекладываем во вторую из второй — в третью.
Если назвать коробочки — будет понятнее:
- Cold — первая коробочка,
- Warm — вторая,
- Hot — третья.
Это уже неплохой алгоритм, он используется в недрах freebsd, если не ошибаюсь. По крайней мере я сталкивался с ним в данном контексте.
Mid point LRU — сегментированный LRU в котором всего две коробочки.
MQ — сегментированный LRU в котором запоминаем. Запоминается позиция с которой элемент вылетел — и при повторном запросе — возвращается туда, где был, если не вылетел из очереди запомненных позиций. По сути кеш быстрее прогревается в случае циклической ротации элементов (какашечки могут стать популярными). Выглядит как довольно странный юзкейс.
ARC, GCLOCK — и прочие более сложные алгоритмы придется на время вынести за скобки. Не то чтобы они плохие или неинтересные, тот же ARC используется (точнее, наверное, использовался, судя по данной преисполненной боли статье: www.varlena.com/GeneralBits/96.php) в postgreSQL. Не удержусь от небольшой цитаты:
Database systems often use LRU algorithms but many are switching to other algorithms to better handle a variety of behaviors not handled well by LRU. For example, one one-time very large sequential scan might flood the cache with pages that are not expected to be used again any time soon. The cache then is not helpful until it is re-populated with more commonly used pages.
2Q — или две очереди, примечателен тем, что сохраняя простоту реализации, он прекрасно адаптируется. Кеш разделяется на три части, как в сегментированном LRU, но с более сложной стратегией:
- Первая часть In — FIFO входящий кеш в который помещаются новые элементы.
- Вторая часть Out — FIFO исходящий кеш, в который перемещаются элементы, вытесненные из коробочки In.
- Третья часть Hot LRU кеш для элементов, запрошенных из Out.
Стратегия вытеснения из кеша:
- элементы запрошенные из In никуда не двигаются. Вытесненные из In элементы — перемещаются в Out.
- элементы запрошенные из Out — попадают в рай, в коробочку Main. Вытесненные же из Out (не использованные) — попадают сразу в ад (null).
Ссылка на каноническое описание.
Во первых — это красиво. Коробочку Main — делаем, например, 20% (помните о Парето?) именно тут скопятся наши аватарки. А вот Out — надо сделать побольше, процентов 60. Так как это «отстойник».
В чем прелесть In — новые элементы спокойно спускаются по FIFO трубе из In в Out, не подпрыгивая и никуда не перемещаясь по мере запросов. А вот если опять запросили (например пользователь подскролил вверх) и, картинка успела перейти из In в Out — вот она картинка победительница. Кеш на уровне архитектуры корректирует некие типичные корреляции, присутствующие в обычной жизни. И после внедрения исчезли постоянные перезагрузки в условиях ограниченного размера памяти. Парето сработал. Но мы еще не раз вернемся к Парето.
Во первых, перейдем к нюансам. Когда читаешь про три коробочки, есть невольный соблазн прямо так тупо и сделать три связанных списка и гонять по ним элементы. Но это неэффективный путь, и как-то не по-джедайски. На самом деле, нам нужно знать только, в какой коробочке лежит ключ, а сами значения могут валяться в это время в некой безобразной куче. Перейдем же скорее к программированию.
package com.squareup.picasso;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
/**
* 2Q: A Low Overhead High Performance Buffer Management Replacement Algorith
* Based on description: http://www.vldb.org/conf/1994/P439.PDF
* Created by recoilme on 22/08/15.
* email: vadim-kulibaba@yandex.ru
*/
public class TwoQCache<K, V> {
/**
* Primary container
*/
final HashMap<K, V> map;
/**
* Sets for 2Q algorithm
*/
private final LinkedHashSet<K> mapIn, mapOut, mapHot;
protected float quarter = .25f;
/**
* Size of this cache in units. Not necessarily the number of elements.
*/
//private int size;
private int sizeIn;
private int sizeOut;
private int sizeHot;
private int maxSizeIn;
private int maxSizeOut;
private int maxSizeHot;
private int putCount;
private int createCount;
private int evictionCount;
private int hitCount;
private int missCount;
/**
* Two queues cache
*
* @param maxSize for caches that do not override {@link #sizeOf}, this is
* this is the maximum sum of the sizes of the entries in this cache.
*/
public TwoQCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
calcMaxSizes(maxSize);
map = new HashMap<K, V>(0, 0.75f);
mapIn = new LinkedHashSet<K>();
mapOut = new LinkedHashSet<K>();
mapHot = new LinkedHashSet<K>();
}
/**
* Sets sizes:
* mapIn ~ 25% // 1st lvl - store for input keys, FIFO
* mapOut ~ 50% // 2nd lvl - store for keys goes from input to output, FIFO
* mapHot ~ 25% // hot lvl - store for keys goes from output to hot, LRU
*
* @param maxSize if mapIn/mapOut sizes == 0, works like LRU for mapHot
*/
private void calcMaxSizes(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
synchronized (this) {
//sizes
maxSizeIn = (int) (maxSize * quarter);
maxSizeOut = maxSizeIn * 2;
maxSizeHot = maxSize - maxSizeOut - maxSizeIn;
}
}
/**
* Sets the size of the cache.
*
* @param maxSize The new maximum size.
*/
public void resize(int maxSize) {
calcMaxSizes(maxSize);
synchronized (this) {
HashMap<K, V> copy = new HashMap<K, V>(map);
evictAll();
Iterator<K> it = copy.keySet().iterator();
while (it.hasNext()) {
K key = it.next();
put(key, copy.get(key));
}
}
}
/**
* Returns the value for {@code key} if it exists in the cache or can be
* created by {@code #create}. If a value was returned, it is moved to the
* head of the queue. This returns null if a value is not cached and cannot
* be created.
*/
public V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
if (mapHot.contains(key)) {
// add & trim (LRU)
mapHot.remove(key);
mapHot.add(key);
} else {
if (mapOut.contains(key)) {
mapHot.add(key);
sizeHot += safeSizeOf(key, mapValue);
trimMapHot();
sizeOut -= safeSizeOf(key, mapValue);
mapOut.remove(key);
}
}
return mapValue;
}
missCount++;
}
/*
* Attempt to create a value. This may take a long time, and the map
* may be different when create() returns. If a conflicting value was
* added to the map while create() was working, we leave that value in
* the map and release the created value.
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
synchronized (this) {
createCount++;
if (!map.containsKey(key)) {
// There was no conflict, create
return put(key, createdValue);
} else {
return map.get(key);
}
}
}
/**
* Caches {@code value} for {@code key}.
*
* @return the previous value mapped by {@code key}.
*/
public V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
if (map.containsKey(key)) {
// if already have - replace it.
// Cache size may be overheaded at this moment
synchronized (this) {
V oldValue = map.get(key);
if (mapIn.contains(key)) {
sizeIn -= safeSizeOf(key, oldValue);
sizeIn += safeSizeOf(key, value);
}
if (mapOut.contains(key)) {
sizeOut -= safeSizeOf(key, oldValue);
sizeOut += safeSizeOf(key, value);
}
if (mapHot.contains(key)) {
sizeHot -= safeSizeOf(key, oldValue);
sizeHot += safeSizeOf(key, value);
}
}
return map.put(key, value);
}
V result;
synchronized (this) {
putCount++;
final int sizeOfValue = safeSizeOf(key, value);
//if there are free page slots then put value into a free page slot
boolean hasFreeSlot = add2slot(key, safeSizeOf(key, value));
if (hasFreeSlot) {
// add 2 free slot & exit
map.put(key, value);
result = value;
} else {
// no free slot, go to trim mapIn/mapOut
if (trimMapIn(sizeOfValue)) {
//put X into the reclaimed page slot
map.put(key, value);
result = value;
} else {
map.put(key, value);
mapHot.add(key);
sizeHot += safeSizeOf(key, value);
trimMapHot();
result = value;
}
}
}
return result;
}
/**
* Remove items by LRU from mapHot
*/
public void trimMapHot() {
while (true) {
K key;
V value;
synchronized (this) {
if (sizeHot < 0 || (mapHot.isEmpty() && sizeHot != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
if (sizeHot <= maxSizeHot || mapHot.isEmpty()) {
break;
}
// we add new item before, so next return first (LRU) item
key = mapHot.iterator().next();
mapHot.remove(key);
value = map.get(key);
sizeHot -= safeSizeOf(key, value);
map.remove(key);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
/**
* Remove items by FIFO from mapIn & mapOut
*
* @param sizeOfValue size of
* @return boolean is trim
*/
private boolean trimMapIn(final int sizeOfValue) {
boolean result = false;
if (maxSizeIn < sizeOfValue) {
return result;
} else {
while (mapIn.iterator().hasNext()) {
K keyIn;
V valueIn;
if (!mapIn.iterator().hasNext()) {
System.out.print("err");
}
keyIn = mapIn.iterator().next();
valueIn = map.get(keyIn);
if ((sizeIn + sizeOfValue) <= maxSizeIn || mapIn.isEmpty()) {
//put X into the reclaimed page slot
if (keyIn == null) {
System.out.print("err");
}
mapIn.add(keyIn);
sizeIn += sizeOfValue;
result = true;
break;
}
//page out the tail of mapIn, call it Y
mapIn.remove(keyIn);
final int removedItemSize = safeSizeOf(keyIn, valueIn);
sizeIn -= removedItemSize;
// add identifier of Y to the head of mapOut
while (mapOut.iterator().hasNext()) {
K keyOut;
V valueOut;
if ((sizeOut + removedItemSize) <= maxSizeOut || mapOut.isEmpty()) {
// put Y into the reclaimed page slot
mapOut.add(keyIn);
sizeOut += removedItemSize;
break;
}
//remove identifier of Z from the tail of mapOut
keyOut = mapOut.iterator().next();
mapOut.remove(keyOut);
valueOut = map.get(keyOut);
sizeOut -= safeSizeOf(keyOut, valueOut);
}
}
}
return result;
}
/**
* Check for free slot in any container and add if exists
*
* @param key key
* @param sizeOfValue size
* @return true if key added
*/
private boolean add2slot(final K key, final int sizeOfValue) {
boolean hasFreeSlot = false;
if (!hasFreeSlot && maxSizeIn >= sizeIn + sizeOfValue) {
mapIn.add(key);
sizeIn += sizeOfValue;
hasFreeSlot = true;
}
if (!hasFreeSlot && maxSizeOut >= sizeOut + sizeOfValue) {
mapOut.add(key);
sizeOut += sizeOfValue;
hasFreeSlot = true;
}
if (!hasFreeSlot && maxSizeHot >= sizeHot + sizeOfValue) {
mapHot.add(key);
sizeHot += sizeOfValue;
hasFreeSlot = true;
}
return hasFreeSlot;
}
/**
* Removes the entry for {@code key} if it exists.
*
* @return the previous value mapped by {@code key}.
*/
public V remove(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V previous;
synchronized (this) {
previous = map.remove(key);
if (previous != null) {
if (mapIn.contains(key)) {
sizeIn -= safeSizeOf(key, previous);
mapIn.remove(key);
}
if (mapOut.contains(key)) {
sizeOut -= safeSizeOf(key, previous);
mapOut.remove(key);
}
if (mapHot.contains(key)) {
sizeHot -= safeSizeOf(key, previous);
mapHot.remove(key);
}
}
}
if (previous != null) {
entryRemoved(false, key, previous, null);
}
return previous;
}
/**
* Called for entries that have been evicted or removed. This method is
* invoked when a value is evicted to make space, removed by a call to
* {@link #remove}, or replaced by a call to {@link #put}. The default
* implementation does nothing.
* <p>
* <p>The method is called without synchronization: other threads may
* access the cache while this method is executing.
*
* @param evicted true if the entry is being removed to make space, false
* if the removal was caused by a {@link #put} or {@link #remove}.
* @param newValue the new value for {@code key}, if it exists. If non-null,
* this removal was caused by a {@link #put}. Otherwise it was caused by
* an eviction or a {@link #remove}.
*/
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {
}
/**
* Called after a cache miss to compute a value for the corresponding key.
* Returns the computed value or null if no value can be computed. The
* default implementation returns null.
* <p>
* <p>The method is called without synchronization: other threads may
* access the cache while this method is executing.
* <p>
* <p>If a value for {@code key} exists in the cache when this method
* returns, the created value will be released with {@link #entryRemoved}
* and discarded. This can occur when multiple threads request the same key
* at the same time (causing multiple values to be created), or when one
* thread calls {@link #put} while another is creating a value for the same
* key.
*/
protected V create(K key) {
return null;
}
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
/**
* Returns the size of the entry for {@code key} and {@code value} in
* user-defined units. The default implementation returns 1 so that size
* is the number of entries and max size is the maximum number of entries.
* <p>
* <p>An entry's size must not change while it is in the cache.
*/
protected int sizeOf(K key, V value) {
return 1;
}
/**
* Clear the cache, calling {@link #entryRemoved} on each removed entry.
*/
public synchronized final void evictAll() {
Iterator<K> it = map.keySet().iterator();
while (it.hasNext()) {
K key = it.next();
it.remove();
remove(key);
}
mapIn.clear();
mapOut.clear();
mapHot.clear();
sizeIn = 0;
sizeOut = 0;
sizeHot = 0;
}
/**
* For caches that do not override {@link #sizeOf}, this returns the number
* of entries in the cache. For all other caches, this returns the sum of
* the sizes of the entries in this cache.
*/
public synchronized final int size() {
return sizeIn + sizeOut + sizeHot;
}
/**
* For caches that do not override {@link #sizeOf}, this returns the maximum
* number of entries in the cache. For all other caches, this returns the
* maximum sum of the sizes of the entries in this cache.
*/
public synchronized final int maxSize() {
return maxSizeIn + maxSizeOut + maxSizeHot;
}
/**
* Returns the number of times {@link #get} returned a value that was
* already present in the cache.
*/
public synchronized final int hitCount() {
return hitCount;
}
/**
* Returns the number of times {@link #get} returned null or required a new
* value to be created.
*/
public synchronized final int missCount() {
return missCount;
}
/**
* Returns the number of times {@link #create(Object)} returned a value.
*/
public synchronized final int createCount() {
return createCount;
}
/**
* Returns the number of times {@link #put} was called.
*/
public synchronized final int putCount() {
return putCount;
}
/**
* Returns the number of values that have been evicted.
*/
public synchronized final int evictionCount() {
return evictionCount;
}
/**
* Returns a copy of the current contents of the cache, ordered from least
* recently accessed to most recently accessed.
*/
public synchronized final Map<K, V> snapshot() {
return new HashMap<K, V>(map);
}
@Override
public synchronized final String toString() {
int accesses = hitCount + missCount;
int hitPercent = accesses != 0 ? (100 * hitCount / accesses) : 0;
return String.format("Cache[size=%d,maxSize=%d,hits=%d,misses=%d,hitRate=%d%%," +
"]",
size(), maxSize(), hitCount, missCount, hitPercent)
+ "\n map:" + map.toString();
}
public List<Object> getMapHotSnapshot() {
List<Object> result = new ArrayList<Object>();
Iterator<K> it = mapHot.iterator();
while (it.hasNext()) {
K key = it.next();
result.add(key);
result.add(map.get(key));
}
return result;
}
}
Обратите внимание на контейнеры:
/** Primary container */
private final HashMap<K,V> map;
/** Sets for 2Q algorithm */
private final LinkedHashSet<K> mapIn, mapOut, mapHot;
Управление «кучками» реализовано на супербыстрых и экономичных по памяти LinkedHashSet, нам не важно значение, важно лишь в какой «кучке» какой ключ находится в данный момент. Это ключ к быстродействию.
Больше практики. Допустим мы хотим прикрутить его к имадж лоадеру — пул реквест к пикассо: github.com/square/picasso/pull/1134
Но вообще это не обязательно. Нормальные либы — позволяют подключить произвольный алгоритм кеширования — достаточно скопипастить класс и переопределить кеш (glide вроде умел, picasso, начиная с какой то версии)
Я уже не помню точных цифр по хитрейту в своем случае. Помню только что у LRU — хитрейт был более 70% но менее 80. У 2Q — чуть более 80%. Но чудо произошло. Потому что все, что нам надо — это закешировать 20% инфы, которая составит 80% трафика. Чудо еще кстати состояло в том, что по скорости 2Q был быстрее LRU.
У нас в Relap.io, несколько реализаций кешей, например моя — github.com/recoilme/2qcache (вообще я не перл программист, это моя первая и надеюсь единственная программа на этом языке, единственный ее плюс — она простая).
Поэтому рекомендую посмотреть на реализацию 2Q на перле от нашего ведущего разработчика:
Реализация на перле, бам: github.com/grinya007/2q
Итак, не важно, что вы пишете: сайт, хайлоад-сервис, мобильное приложение или операционную систему, реализовав единожды умный алгоритм кеширования, вы можете использовать его повсеместно, экономя ресурсы и нервы пользователя.
Комментарии (50)
orthanner
30.07.2016 07:30JDK 4? если более новый, то лучше, наверное, посмотреть в сторону java.util.concurrent с подпакетами вместо synchronized. Синхронизированные методы блокируют все доступы к объекту.
Beanut
30.07.2016 08:46-1Мне кажется этот код — вообще не рабочий. Например: это что, заглушка какая то?
protected int sizeOf(K key, V value) { return 1; }
recompileme
30.07.2016 09:30+1Я написал подробные комментарии к каждому методу:
/** * Returns the size of the entry for {@code key} and {@code value} in * user-defined units. The default implementation returns 1 so that size * is the number of entries and max size is the maximum number of entries. * * <p>An entry's size must not change while it is in the cache. */ protected int sizeOf(K key, V value) { return 1; }
Необходимо перекрыть данный метод Если размер элемента отличен от 1, например так:
@Override protected int sizeOf(String key, Bitmap value) { final int bitmapSize = Utils.getBitmapBytes(value) / 1024; return bitmapSize == 0 ? 1 : bitmapSize; }
Когда кажется — крестятся, а когда хотят проверить код пишут тест
Извините, немного раздражают подобные утверждения
G-M-A-X
30.07.2016 09:35Если большая картинка вытесняла маленькие в LRU, то поему она не вытеснит их в Вашем варианте?
Может большие картинки в кеш не ложить и все? :)
kowack
30.07.2016 22:16Если большая картинка вытиснила маленькие в первом случае из-за нехватки памяти, согласно статье, то никакой алгоритм тут не спасёт. И автор статьи использует НЕ классический 2Q. Достаточно перейти по ссылке в статье http://www.vldb.org/conf/1994/P439.PDF.
А вот 2Q решает эту проблему тем, что OUT хранит исключительно ключи, а не значения, и не обязан быть большим по памяти.
В свою очередь MAIN защищает данные от «вымывания».
А IN защищает от попадания в MAIN временно частых запросов.
2Q — это не убер-алгоритм, но он идеально подходит для кэширования данных генерируемых поведением пользователя.
Всегда пожалуйста)recompileme
01.08.2016 11:34Спасибо за доходчивое объяснение, но не совсем согласен. Размер имеет значение. Прочитайте боль разработчиков постгри:
Database systems often use LRU algorithms but many are switching to other algorithms to better handle a variety of behaviors not handled well by LRU. For example, one one-time very large sequential scan might flood the cache with pages that are not expected to be used again any time soon. The cache then is not helpful until it is re-populated with more commonly used pages.
Учитывание размера значений хранящихся в кеше — позволит более гибко их обрабатывать. Допустим размер кеша 10 мегабайт, Вы поделили на 3 области, например
in — 2.5
out — 5
main — 2.5
Приходит 5 ключей по 0.5 Mb — они ложатся в in
Приходит ключ 3 Mb — в in места нет, он ложится в out
Приходят 10 ключей по 0.5 Mb из которых 5- старые
Старые ключи ложатся в out (так как они уже были в in) — большой ключ на 3 мегабайта вылетает в ад (места нет и он не был запрошен из out)
Новые 5 ключей ложатся в in
При третьем запросе ключей из out — они уходят в защищенную область main
Когда размер контейнера задается не в виде размера памяти, а в виде количества хранящихся значений — разницы нет. Размер out/main/in — лучше подбирать индивидуально, согласен. By default размер задан таким, каким его видят авторы алгоритм но в RL у нас другие размеры контейнеров (мы задираем main)
G-M-A-X
01.08.2016 16:49Я не понимаю, почему заминусовали?
Типа я повторил то, что писали другие выше 100500 раз?
Пост долго был на премодерации.andybelo
02.08.2016 09:20-2Подонки минусуют, что бы рот заткнуть. я вот убедился, что все социальные сети сделаны, что бы ограничить общение. ну не нравиться, не читай мои коменты. Или возрази. А так молча неизвестно кто насрал и смылся. Тактика известного персонажа.
andybelo
30.07.2016 10:26-2Для улучшения отзывчивости нужно параллелить узкие места, а не кешировать.
iChaos
30.07.2016 11:44Вы странные…
Как можно судить об эффективности алгоритмов, без учета характеристик используемых данных и характера их использования?!
Имхо, выбор (или создание) эффективного алгоритма кэширования, напрямую проистекает из того, как именно, и какие данные используются в каждом конкретном случае. Без учета этой информации, построение эффективного алгоритма кэширования значительно затрудняется…recompileme
30.07.2016 11:48Вы абсолютно правы, мы всегда тестируем прежде чем выбрать
Вот некоторые результаты
check out its efficiency git clone https://github.com/grinya007/2q.git cd 2q zcat ids.gz | ./test.pl with max size of 2000 entries it does: worked out 1000000 keys hit rate: 72.689 % memory: 2.828 Mb time: 2.767 s Cache::LRU with everything else being equal does: worked out 1000000 keys hit rate: 64.762 % memory: 3.547 Mb time: 2.998 s Cache::Ref::CAR with everything else being equal does: worked out 1000000 keys hit rate: 69.292 % memory: 3.465 Mb time: 12.961 s
alno
30.07.2016 13:43+1Спасибо за отличную статью! Можете пояснить вот этот кусочек кода в get?
if (mapHot.contains(key)) { // add & trim (LRU) mapHot.add(key); sizeHot += safeSizeOf(key, mapValue); trimMapHot(); }
Насколько я понимаю, в случае если ключ находится в hot вы добавляете его туда опять чтобы поменять позицию в LinkedHashSet?
Но если это так, то оно не будет работать как запланировано — из документации к LinkedHashSet:
Note that insertion order is not affected if an element is re-inserted into the set. (An element e is reinserted into a set s if s.add(e) is invoked when s.contains(e) would return true immediately prior to the invocation.)
Ну и можно проверить:
LinkedHashSet<Integer> lhs = new LinkedHashSet<Integer>(); lhs.add(1); lhs.add(2); lhs.add(3); lhs.add(1); // Add again, try to change position for (Integer v: lhs) System.out.println(v); => 1 2 3
И почему вы увеличиваете sizeHot, хотя элемент же уже был в множестве, ведь размер не поменялся?recompileme
01.08.2016 10:38Спасибо! В пулл реквесте в этом месте пара remove/add Заведем репозиторий под это дело чтоб не путаться
bitec
30.07.2016 17:10+1Думал, будет упоминание про LIRS, весьма любопытный алгоритм по своей идее, в MySql и Infinispan судя по всему используется
recompileme
01.08.2016 12:24Немножко смотрел. Пишут, что он проще в разработке по сравнению с 2Q, а к минусам — то что он прожорливее по памяти. Проще понять наверно по реализации чем по описанию. Надо сравнивать(
pansa
31.07.2016 02:04А только мне кажется странным, что LRU объявлен неудачником и полным УГ на основании примера с большой картинкой? Ведь в алгоритме LRU никак не учавствует размер элемента. Взят довольно вырожденный случай, когда алгоритм поведет себя плохо. Но таким образом оценивать эффективность это же абсурд?
recompileme
01.08.2016 11:00Не совсем так. LRU ведет себя хуже всех на всех тестах, вне зависимости от реализации с учетом размера элементов или нет, на сайте или в приложении, для урлов или для картинок, для хитов или для рекомендаций, наверное даже банальный рандом возьмите — LRU всегда проигрывает всем. Статья вобщем то не о том какой 2Q прекрасный, статья о том, что LRU это худщий алгоритм из всех существующих.
— Не учитывается частота использования элементов (100 раз запросили или 1 — LRU все равно)
— Очень длинный период вытеснения редко используемых элементов
— Нет защищенных областей
— Не эффективно используется память
Единственный его плюс — его очень легко понять.
dkosolobov
02.08.2016 14:14Вы совсем как-то заклеймили LRU. Верю, что, вероятно, на многих реальных паттернах использования кэша LRU проигрывает некоторым другим кэшам. Но есть у LRU одна особенность: в худшем случае его поведение в некотором смысле наилучшее по отношению к «ясновидящему» оптимальному алгоритму. Это доказано Слейтором и Тарьяном в статье Amortized efficiency of list update and paging rules (раздел 4). Немного огрублённо их результат можно сформулировать так:
Для любой константы c>1 и для любой последовательности s обращений к кэшируемым элементам (кэшируемые элементы имеют одинаковый размер) выполняется F_LRU(s) <= c F_OPT(s), где F_LRU(s) и F_OPT(s) — это число непопаданий в кэш на последовательности s для, соответственно, алгоритма LRU с размером кэша n и ясновидящего алгоритма OPT с размером кэша (1 — 1/c)n.
И обратно: для любого алгоритма кэширования A найдётся сколь угодно длинная последовательность s обращений к кэшируемым элементам, такая что F_A(s) >= c F_OPT(s), где F_A(s) — это число непопаданий в кэш на последовательности s для алгоритма A с размером кэша n, а у OPT опять размер кэша (1 — 1/c)n.
kemsky
31.07.2016 05:27+1Куда более интересно было бы изучить статистику, выбрать оптимальную стратегию кэширования для снижения нагрузки на сервер, изучить поведение пользователей в приложении, попробовать предсказать поведение пользователя и на его стороне адаптивно кэшировать.
tridemax
31.07.2016 14:32Я решил обновить публичную имплементацию алгоритма CART до v0.2:
https://github.com/tridemax/CART
Интересно было бы сравнить эффективность. =)recompileme
01.08.2016 10:48Нет ли случайно планов перенести реализацию на ванильный C? Чтоб встроить в тот же Nginx, и по хардкору развлекаться?
tridemax
01.08.2016 14:36А что, в Nginx нельзя закомпиленный C++ модуль вкрутить? Пусть даже и с внешним С-шным интерфейсом?
recompileme
01.08.2016 15:16Вкрутить вроде вкручивают… Там еще некий tbb… У нас вроде никто на C++ не пишет, даже спросить некого
tridemax
01.08.2016 21:47TBB очень легко подключается к проектам. Проблем вообще не должно быть. Гугл полон пошаговых инструкций. :)
G-M-A-X
31.07.2016 20:12Кстати, в memcached вроде LRU, но там блоки разных размеров хранятся отдельно.
То есть, большие и маленькие не пересекаются.recompileme
01.08.2016 09:41Судя по сорцам — в memcached SNLRU + возможность задания «протухания ключа» по времени. Только в SNLRU разные блоки — не для разных размеров, они по частоте обращений делятся на cold,warm,hot
farewell
02.08.2016 10:13Применительно к Android, можно использовать https://github.com/candrews/HttpResponseCache.
zuborg
03.08.2016 19:21+1LRU конечно плох, но и все эти зонные алгоритмы не сказать что идеальны.
Как по мне, надо просто для каждого объекта считать частоту запросов с експоненциальным затуханием (т.е. через T времени накопленная частота снизится в E раз), и просто вытеснять из кеша объекты с самой маленькой частотой.
Частоту запросов можно описать такой структурой { LastAccess uint32, Rate float32 }
И при каждом хите обновлять её:
Rate = 1 + Rate / exp((Now() — LastAccess) * DAMPING_FACTOR)
LastAccess = Now()
При таком подходе в кеше асимптотика заполнения кеша будет стремиться к идеальной — в нем будут самые часто запрашиваемые объекты.recompileme
03.08.2016 19:49+1Очень интересная идея. За основу можно взять hacker news rank кстати
Score = (P-1) / (T+2)^G
where,
P = points of an item (and -1 is to negate submitters vote)
T = time since submission (in hours)
G = Gravity, defaults to 1.8
Должно получится своеобразное предсказание (шаг на пути к идеальному алгоритму:))
recompileme
Сняли небольшое видео о том, как устроен 2Q, но звук/качество получилось к сожалению не очень, вставлять постеснялись, а выкидывать жалко( Вот оно:
Beanut
Как то странная логика у вас. Для LRU кэша большая картинка вытесняет маленькие потому что для маленьких нет места в кэше. Однако для 2Q кэша вы просто делаете в 3 раза больший размер кэша и все у вас помещается. Хотелось бы сравнения в равных условиях.
Да и в целом описание 2Q не понятно — откуда брать картинки? Из In? Из Out? Из Hot?
recompileme
Условия идентичны конечно. Выделенная под кеш память в одном случае не делится, а в другом — режется на три области. Про откуда брать картинки — вопрос настолько странный что я даже не знаю как ответить.
gurinderu
А я не совсем понял, почему в LRU большая картинка, должна выкинуть все маленькие? У вас есть какое-то ограничение по памяти? Если да, то в вашей реализации на основе Map я его не вижу. В вашем случае можно всегда модифицировать очередь приоритетов для LRU и раставлять его чуть ли не руками. Ну и выходит что условия не идентичны.
recompileme
Конечно есть ограничения по памяти
И конечно условия идентичные.
Друзья, наверно я сложно и запутанно объяснил: вот ссылка на каноническое описание от авторов 2Q
http://www.vldb.org/conf/1994/P439.PDF
Так понятней?
motakuji
У вас size любых объектов равен 1. Так что ограничений по памяти у вас нет! Только по количеству элементов.
recompileme
В случае если размер отличен от 1 — этот метод перекрывается:
Пример
То же самое, перекрытие метода и задание размера — необходимо сделать если вы используете библиотеку LRU от Google из фреймворка андроид
gurinderu
Ок, если вы его завераидили, то все понятно. Но чисто в теории при прокрутке туда сюда, большая картинка может попасть в hot и выкинуть оттуда ваши аватарочки. +Ваш код довольно не оптимален, когда с кэшем будет работать много потоков.
Beanut
Хорошо, предположим что сумма размеров одинакова:
https://habrastorage.org/files/249/aca/dd8/249acadd8e8640b8a0b4a488a9160c66.png
Объясните — куда поместится большая картинка в вашем случае?
Если же сделать так, чтобы большая картинка помещалась в ваш контейнер, то его придется увеличить, а если размеры равны, то придется увеличить и LRU контейнер и вот уже маленькие картинки перестанут вытесняться.
recompileme
В случае изображенном на Вашем скриншоте (размер значения превышает размер контейнера) — большая картинка отправится сразу в ад (не будет помещена в кеш), сохранив место в кеше для более мелких элементов.
motakuji
В первом случае (LRU) выделяется фиксированная память, а во втором (2Q) — она никак не ограничена. Так что тест у вас не корректный.
recompileme
LruCache lruCache = new LruCache(1024 * 1024 * 10);
TwoQCacheImpl twoQueues = new TwoQCacheImpl(1024 * 1024 * 10);
motakuji
Смотрите мой ответ выше. Из текста вашего поста следует, что LRU ограничен по помяти, т.к. большая картинка вытесняет маленькие. А TwoQCacheImpl может хранить 1024*1024*10 элементов без ограничения по памяти. Складывается такое впечатление, что либо не вы писали эту реализацию, либо не понимаете как она работает.
recompileme
1024*1024*10 — это максимальный размер кеша, это и есть ограничение. Эту реализацию писал я, она великолепно работает и я прекрасно понимаю как, только Вам объяснить не могу)
Используйте готовые библиотеки если не можете понять. Это нормально. Так делают 80% программистов
motakuji
Ну если у вас элементы по 1 байту, то да :) Прогоните код. Получается, что все комментаторы ламеры, а вы Д’Артаньян :)
bizon2000
Очевидно, что размер кэша таков, что он может вместить не одну большую картинку, а несколько. Вопрос в том, что будет вытеснено, когда после одной большой картинки придет очередная большая картинка, а места в кэше нет. В алгоритме LRU она вытеснит маленькие картинки, т.к. они дольше не использовались, а в алгоритме 2Q маленькие картинки не удалятся, т.к., они уже в Main. А большая картинка вытеснится, когда придет ее очередь, т.к. она использовалась лишь однократно
we1
При переходе и Out в Hot элемент из списка Out сразу удялается буд-то он внизу оказался, или остается? Это отличие должно довольно сильно повлять на ситуацию, когда элемент будет выкинут из Hot.