Comments 59
Сняли небольшое видео о том, как устроен 2Q, но звук/качество получилось к сожалению не очень, вставлять постеснялись, а выкидывать жалко( Вот оно:
Как то странная логика у вас. Для LRU кэша большая картинка вытесняет маленькие потому что для маленьких нет места в кэше. Однако для 2Q кэша вы просто делаете в 3 раза больший размер кэша и все у вас помещается. Хотелось бы сравнения в равных условиях.
Да и в целом описание 2Q не понятно — откуда брать картинки? Из In? Из Out? Из Hot?
Да и в целом описание 2Q не понятно — откуда брать картинки? Из In? Из Out? Из Hot?
Условия идентичны конечно. Выделенная под кеш память в одном случае не делится, а в другом — режется на три области. Про откуда брать картинки — вопрос настолько странный что я даже не знаю как ответить.
А я не совсем понял, почему в LRU большая картинка, должна выкинуть все маленькие? У вас есть какое-то ограничение по памяти? Если да, то в вашей реализации на основе Map я его не вижу. В вашем случае можно всегда модифицировать очередь приоритетов для LRU и раставлять его чуть ли не руками. Ну и выходит что условия не идентичны.
Конечно есть ограничения по памяти
И конечно условия идентичные.
Друзья, наверно я сложно и запутанно объяснил: вот ссылка на каноническое описание от авторов 2Q
http://www.vldb.org/conf/1994/P439.PDF
Так понятней?
/**
* 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 TwoQueuesCache(int maxSize) {
И конечно условия идентичные.
Друзья, наверно я сложно и запутанно объяснил: вот ссылка на каноническое описание от авторов 2Q
http://www.vldb.org/conf/1994/P439.PDF
Так понятней?
У вас size любых объектов равен 1. Так что ограничений по памяти у вас нет! Только по количеству элементов.
В случае если размер отличен от 1 — этот метод перекрывается:
Пример
То же самое, перекрытие метода и задание размера — необходимо сделать если вы используете библиотеку LRU от Google из фреймворка андроид
Пример
То же самое, перекрытие метода и задание размера — необходимо сделать если вы используете библиотеку LRU от Google из фреймворка андроид
Хорошо, предположим что сумма размеров одинакова:
https://habrastorage.org/files/249/aca/dd8/249acadd8e8640b8a0b4a488a9160c66.png
Объясните — куда поместится большая картинка в вашем случае?
Если же сделать так, чтобы большая картинка помещалась в ваш контейнер, то его придется увеличить, а если размеры равны, то придется увеличить и LRU контейнер и вот уже маленькие картинки перестанут вытесняться.
https://habrastorage.org/files/249/aca/dd8/249acadd8e8640b8a0b4a488a9160c66.png
Объясните — куда поместится большая картинка в вашем случае?
Если же сделать так, чтобы большая картинка помещалась в ваш контейнер, то его придется увеличить, а если размеры равны, то придется увеличить и LRU контейнер и вот уже маленькие картинки перестанут вытесняться.
В первом случае (LRU) выделяется фиксированная память, а во втором (2Q) — она никак не ограничена. Так что тест у вас не корректный.
LruCache lruCache = new LruCache(1024 * 1024 * 10);
TwoQCacheImpl twoQueues = new TwoQCacheImpl(1024 * 1024 * 10);
TwoQCacheImpl twoQueues = new TwoQCacheImpl(1024 * 1024 * 10);
Смотрите мой ответ выше. Из текста вашего поста следует, что LRU ограничен по помяти, т.к. большая картинка вытесняет маленькие. А TwoQCacheImpl может хранить 1024*1024*10 элементов без ограничения по памяти. Складывается такое впечатление, что либо не вы писали эту реализацию, либо не понимаете как она работает.
1024*1024*10 — это максимальный размер кеша, это и есть ограничение. Эту реализацию писал я, она великолепно работает и я прекрасно понимаю как, только Вам объяснить не могу)
Используйте готовые библиотеки если не можете понять. Это нормально. Так делают 80% программистов
Используйте готовые библиотеки если не можете понять. Это нормально. Так делают 80% программистов
Ну если у вас элементы по 1 байту, то да :) Прогоните код. Получается, что все комментаторы ламеры, а вы Д’Артаньян :)
Размер считается тут
Однако почему-то в килобайтах, а не в байтах. Так что сравнение и правда некорректное :)
Однако почему-то в килобайтах, а не в байтах. Так что сравнение и правда некорректное :)
Очевидно, что размер кэша таков, что он может вместить не одну большую картинку, а несколько. Вопрос в том, что будет вытеснено, когда после одной большой картинки придет очередная большая картинка, а места в кэше нет. В алгоритме LRU она вытеснит маленькие картинки, т.к. они дольше не использовались, а в алгоритме 2Q маленькие картинки не удалятся, т.к., они уже в Main. А большая картинка вытеснится, когда придет ее очередь, т.к. она использовалась лишь однократно
При переходе и Out в Hot элемент из списка Out сразу удялается буд-то он внизу оказался, или остается? Это отличие должно довольно сильно повлять на ситуацию, когда элемент будет выкинут из Hot.
JDK 4? если более новый, то лучше, наверное, посмотреть в сторону java.util.concurrent с подпакетами вместо synchronized. Синхронизированные методы блокируют все доступы к объекту.
Мне кажется этот код — вообще не рабочий. Например: это что, заглушка какая то?
protected int sizeOf(K key, V value) {
return 1;
}Я написал подробные комментарии к каждому методу:
Необходимо перекрыть данный метод Если размер элемента отличен от 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;
}
Когда кажется — крестятся, а когда хотят проверить код пишут тест
Извините, немного раздражают подобные утверждения
Если большая картинка вытесняла маленькие в LRU, то поему она не вытеснит их в Вашем варианте?
Может большие картинки в кеш не ложить и все? :)
Может большие картинки в кеш не ложить и все? :)
Если большая картинка вытиснила маленькие в первом случае из-за нехватки памяти, согласно статье, то никакой алгоритм тут не спасёт. И автор статьи использует НЕ классический 2Q. Достаточно перейти по ссылке в статье http://www.vldb.org/conf/1994/P439.PDF.
А вот 2Q решает эту проблему тем, что OUT хранит исключительно ключи, а не значения, и не обязан быть большим по памяти.
В свою очередь MAIN защищает данные от «вымывания».
А IN защищает от попадания в MAIN временно частых запросов.
2Q — это не убер-алгоритм, но он идеально подходит для кэширования данных генерируемых поведением пользователя.
Всегда пожалуйста)
А вот 2Q решает эту проблему тем, что OUT хранит исключительно ключи, а не значения, и не обязан быть большим по памяти.
В свою очередь MAIN защищает данные от «вымывания».
А IN защищает от попадания в MAIN временно частых запросов.
2Q — это не убер-алгоритм, но он идеально подходит для кэширования данных генерируемых поведением пользователя.
Всегда пожалуйста)
Спасибо за доходчивое объяснение, но не совсем согласен. Размер имеет значение. Прочитайте боль разработчиков постгри:
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)
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)
Я не понимаю, почему заминусовали?
Типа я повторил то, что писали другие выше 100500 раз?
Пост долго был на премодерации.
Типа я повторил то, что писали другие выше 100500 раз?
Пост долго был на премодерации.
UFO just landed and posted this here
Вы странные…
Как можно судить об эффективности алгоритмов, без учета характеристик используемых данных и характера их использования?!
Имхо, выбор (или создание) эффективного алгоритма кэширования, напрямую проистекает из того, как именно, и какие данные используются в каждом конкретном случае. Без учета этой информации, построение эффективного алгоритма кэширования значительно затрудняется…
Как можно судить об эффективности алгоритмов, без учета характеристик используемых данных и характера их использования?!
Имхо, выбор (или создание) эффективного алгоритма кэширования, напрямую проистекает из того, как именно, и какие данные используются в каждом конкретном случае. Без учета этой информации, построение эффективного алгоритма кэширования значительно затрудняется…
Вы абсолютно правы, мы всегда тестируем прежде чем выбрать
Вот некоторые результаты
Вот некоторые результаты
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
Спасибо за отличную статью! Можете пояснить вот этот кусочек кода в get?
Насколько я понимаю, в случае если ключ находится в hot вы добавляете его туда опять чтобы поменять позицию в LinkedHashSet?
Но если это так, то оно не будет работать как запланировано — из документации к LinkedHashSet:
Ну и можно проверить:
И почему вы увеличиваете sizeHot, хотя элемент же уже был в множестве, ведь размер не поменялся?
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, хотя элемент же уже был в множестве, ведь размер не поменялся?
Спасибо! В пулл реквесте в этом месте пара remove/add Заведем репозиторий под это дело чтоб не путаться
Думал, будет упоминание про LIRS, весьма любопытный алгоритм по своей идее, в MySql и Infinispan судя по всему используется
Немножко смотрел. Пишут, что он проще в разработке по сравнению с 2Q, а к минусам — то что он прожорливее по памяти. Проще понять наверно по реализации чем по описанию. Надо сравнивать(
А только мне кажется странным, что LRU объявлен неудачником и полным УГ на основании примера с большой картинкой? Ведь в алгоритме LRU никак не учавствует размер элемента. Взят довольно вырожденный случай, когда алгоритм поведет себя плохо. Но таким образом оценивать эффективность это же абсурд?
Не совсем так. LRU ведет себя хуже всех на всех тестах, вне зависимости от реализации с учетом размера элементов или нет, на сайте или в приложении, для урлов или для картинок, для хитов или для рекомендаций, наверное даже банальный рандом возьмите — LRU всегда проигрывает всем. Статья вобщем то не о том какой 2Q прекрасный, статья о том, что LRU это худщий алгоритм из всех существующих.
— Не учитывается частота использования элементов (100 раз запросили или 1 — LRU все равно)
— Очень длинный период вытеснения редко используемых элементов
— Нет защищенных областей
— Не эффективно используется память
Единственный его плюс — его очень легко понять.
— Не учитывается частота использования элементов (100 раз запросили или 1 — LRU все равно)
— Очень длинный период вытеснения редко используемых элементов
— Нет защищенных областей
— Не эффективно используется память
Единственный его плюс — его очень легко понять.
Вы совсем как-то заклеймили 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.
Для любой константы 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.
Куда более интересно было бы изучить статистику, выбрать оптимальную стратегию кэширования для снижения нагрузки на сервер, изучить поведение пользователей в приложении, попробовать предсказать поведение пользователя и на его стороне адаптивно кэшировать.
Я решил обновить публичную имплементацию алгоритма CART до v0.2:
https://github.com/tridemax/CART
Интересно было бы сравнить эффективность. =)
https://github.com/tridemax/CART
Интересно было бы сравнить эффективность. =)
Кстати, в memcached вроде LRU, но там блоки разных размеров хранятся отдельно.
То есть, большие и маленькие не пересекаются.
То есть, большие и маленькие не пересекаются.
Судя по сорцам — в memcached SNLRU + возможность задания «протухания ключа» по времени. Только в SNLRU разные блоки — не для разных размеров, они по частоте обращений делятся на cold,warm,hot
Применительно к Android, можно использовать https://github.com/candrews/HttpResponseCache.
LRU конечно плох, но и все эти зонные алгоритмы не сказать что идеальны.
Как по мне, надо просто для каждого объекта считать частоту запросов с експоненциальным затуханием (т.е. через T времени накопленная частота снизится в E раз), и просто вытеснять из кеша объекты с самой маленькой частотой.
Частоту запросов можно описать такой структурой { LastAccess uint32, Rate float32 }
И при каждом хите обновлять её:
Rate = 1 + Rate / exp((Now() — LastAccess) * DAMPING_FACTOR)
LastAccess = Now()
При таком подходе в кеше асимптотика заполнения кеша будет стремиться к идеальной — в нем будут самые часто запрашиваемые объекты.
Как по мне, надо просто для каждого объекта считать частоту запросов с експоненциальным затуханием (т.е. через T времени накопленная частота снизится в E раз), и просто вытеснять из кеша объекты с самой маленькой частотой.
Частоту запросов можно описать такой структурой { LastAccess uint32, Rate float32 }
И при каждом хите обновлять её:
Rate = 1 + Rate / exp((Now() — LastAccess) * DAMPING_FACTOR)
LastAccess = Now()
При таком подходе в кеше асимптотика заполнения кеша будет стремиться к идеальной — в нем будут самые часто запрашиваемые объекты.
Очень интересная идея. За основу можно взять 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
Должно получится своеобразное предсказание (шаг на пути к идеальному алгоритму:))
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
Должно получится своеобразное предсказание (шаг на пути к идеальному алгоритму:))
По большому счёту, зонные алгоритмы — это грубое приближение экспоненциального затухания.
Более тонкое приближение — мысленно отсортировать ключи по частоте-с-затуханием.
И считать, что частота обратно пропорциональна индексу.
Тогда обновление состоит в том, что если ключ был в ячейке с индексом z, надо его перенести его в ячейку x = z/DAMPING_FACTOR (сдвинув, разумеется, все элементы x..z вправо).
Более тонкое приближение — мысленно отсортировать ключи по частоте-с-затуханием.
И считать, что частота обратно пропорциональна индексу.
Тогда обновление состоит в том, что если ключ был в ячейке с индексом z, надо его перенести его в ячейку x = z/DAMPING_FACTOR (сдвинув, разумеется, все элементы x..z вправо).
Конкретно в таком виде это не будет работать. Регулярно будет ситуация, когда в ячейку x будет помещаться режезапрашиваемый объект, чем в ячейке x+1, а значит «частота обратно пропорциональна индексу» очень быстро перестанет быть таковой.
Но идея с перемещением елемента в индексе в целом продуктивна. Так как основная задача состоит в том, чтобы отделить редкозапрашиваемые объекты от частозапрашиваемых, то, видимо, будет достаточно при каждом хите перемещать объект ближе к голове списка на одну позицию (простой обмен с соседним элементом). Тогда частозапрашиваемые объекты сконцентрируются у головы списка, а редкозапрашиваемые — у хвоста, причем чем реже будут запрашиваться — тем ближе к хвосту.
Новый объект вполне безопасно помещать в начало списка — если он популярный, то там и останется, если нет — его обгонят более популярные, а сам елемент уйдет в хвост и в итоге будет вытеснен.
Но идея с перемещением елемента в индексе в целом продуктивна. Так как основная задача состоит в том, чтобы отделить редкозапрашиваемые объекты от частозапрашиваемых, то, видимо, будет достаточно при каждом хите перемещать объект ближе к голове списка на одну позицию (простой обмен с соседним элементом). Тогда частозапрашиваемые объекты сконцентрируются у головы списка, а редкозапрашиваемые — у хвоста, причем чем реже будут запрашиваться — тем ближе к хвосту.
Новый объект вполне безопасно помещать в начало списка — если он популярный, то там и останется, если нет — его обгонят более популярные, а сам елемент уйдет в хвост и в итоге будет вытеснен.
Управление «кучками» реализовано на супербыстрых и экономичных по памяти LinkedHashSet, нам не важно значение, важно лишь в какой «кучке» какой ключ находится в данный момент. Это ключ к быстродействию.
Хотелось бы подробностей, почему именно LinkedHashSet, а не обычный HashSet.
LinkedHashSet используется тогда, когда важен порядок добавления, а вы пишете, что «важно лишь в какой «кучке» какой ключ находится в данный момент».
Пассаж про LRU и его «неэффективность» весьма категоричен, поэтому неверен. Возможно его встраивают по-умолчанию не просто так, а потому что он естественным образом подходит для многих случаев?
Вот тут хорошо про стратегии:
Вкратце перескажу содержание: в 60х года прошлого века математики доказали что наиболее эффективным алгоритмом вытеснения (минимизирует cache-miss) будет алгоритм, который вытесняет тот элемент, запрос к которому будет произведен позже других элементов. Принцип очень прост, но, к сожалению, в будущее никто заглядывать не умеет — поэтому остается строить догадки, какой именно из элементов будет запрошен из кэша позже всего. Например, можно предположить, что если элемент запрашивали недавно, то его запросят скоро еще раз, поэтому выгоднее выталкивать элементы, которые уже долго никто не запрашивал (LRU). Однако предметная область у каждого разная, и алгоритм вытеснения подбирается под ситуацию: например, мы всеми силами можем стараться сохранить в кэше картинки с совушками, а вот картинки с Гитлером выталкивать при любом удобном случае.
Другим интересным моментом оказывается то, что хоть мы и не можем смотреть в будущее, смотреть в прошлое нам никто не запрещает. Поэтому если взять логи запросов и логи вытеснения мы можем оценить насколько эффективно работает наш алгоритм вытеснения и не пора ли его поменять или оттюнить.
Кроме эффективности самого алгоритма вытеснения существуют чисто технические проблемы эффективности: уменьшение contention при конкурентном доступе к кешу (например разделением на регионы или разделением кэшей по типам данных), оптимизация внутренних структур, баланс между идеальными показателями cache-miss и временем доступа.
Вот тут хорошо про стратегии:
Вкратце перескажу содержание: в 60х года прошлого века математики доказали что наиболее эффективным алгоритмом вытеснения (минимизирует cache-miss) будет алгоритм, который вытесняет тот элемент, запрос к которому будет произведен позже других элементов. Принцип очень прост, но, к сожалению, в будущее никто заглядывать не умеет — поэтому остается строить догадки, какой именно из элементов будет запрошен из кэша позже всего. Например, можно предположить, что если элемент запрашивали недавно, то его запросят скоро еще раз, поэтому выгоднее выталкивать элементы, которые уже долго никто не запрашивал (LRU). Однако предметная область у каждого разная, и алгоритм вытеснения подбирается под ситуацию: например, мы всеми силами можем стараться сохранить в кэше картинки с совушками, а вот картинки с Гитлером выталкивать при любом удобном случае.
Другим интересным моментом оказывается то, что хоть мы и не можем смотреть в будущее, смотреть в прошлое нам никто не запрещает. Поэтому если взять логи запросов и логи вытеснения мы можем оценить насколько эффективно работает наш алгоритм вытеснения и не пора ли его поменять или оттюнить.
Кроме эффективности самого алгоритма вытеснения существуют чисто технические проблемы эффективности: уменьшение contention при конкурентном доступе к кешу (например разделением на регионы или разделением кэшей по типам данных), оптимизация внутренних структур, баланс между идеальными показателями cache-miss и временем доступа.
Возможно его встраивают по-умолчанию не просто так, а потому что он естественным образом подходит для многих случаев?Более логичным выглядит предположение, что популярность этого алгоритма вытекает из его простоты.
Эффективность LRU весьма невысока — если после запроса любого объекта будет запрошено N других разных объектов, где N > размер кеша, то исходный объект будет вытеснен, даже если он будет самым! частозапрашиваемым. Например, для вырожденного случая, когда у нас есть кеш размером N, и набор из M объектов (M > N), которые запрашиваются равномерно по кругу (1, 2,…, M-1, M, 1, 2 ..) — эффективность LRU кеша будет равна 0% — в кеше всегда будут последние N запрошенных объектов и ни одного из тех, который будет запрошен до того, как будет вытеснен из кеша.
При разработке стратегии кеширования предпочтительнее учитывать всю частоту (усредненную каким-либо образом) запрашивания объекта, а не одно лишь время, прошедшее с последнего запроса.
Я бы предложил употреблять более конкретные заявления — «эффективность при сценарии, который заключается в том, что ...». В большинстве случаев, когда кэширование действительно требуется мы можем наблюдать четкий сценарий использования и универсальные алгоритмы не нужны.
В данном случае у вас искусственный, специфичный сценарий использования. В то время как для большинства сервисов можно выделить «горячий» контент, который постоянно находится в ротации (обычно свежий) и «холодный» контент, который запрашивают очень редко. В таких случаях при правильном размере кэша LRU вытеснение горячего контента маловероятно и особого вреда в массе не приносит.
Полагаю опять же, что вырожденный сценарий можно придумать для любой стратегии вытеснения. Да и чтобы усреднять запрашивание объектов нужен еще один кэш — теперь уже по всем объектам.
В данном случае у вас искусственный, специфичный сценарий использования. В то время как для большинства сервисов можно выделить «горячий» контент, который постоянно находится в ротации (обычно свежий) и «холодный» контент, который запрашивают очень редко. В таких случаях при правильном размере кэша LRU вытеснение горячего контента маловероятно и особого вреда в массе не приносит.
Полагаю опять же, что вырожденный сценарий можно придумать для любой стратегии вытеснения. Да и чтобы усреднять запрашивание объектов нужен еще один кэш — теперь уже по всем объектам.
Рассмотрим сервер с 1ТБ активного (и 10+ТБ общего, но нас интересует активный, который запрашивается хотя бы раз в сутки) контента и 128ГБ оперативки, с сетевой нагрузкой, скажем, 800Мбит/c (100МБайт/c)
Частотность запросов распределена по закону Ципфа (т.е. объект на 100-м месте в ранге частотности будет иметь в 2 раза меньшую частоту запрашивания, чем объект на 50-м месте).
Кстати, при такой скорости 1ГБ скачивается за 10 секунд, 1ТБ — за 10к секунд, ну а за сутки соотв скачивается всего 8.6ТБ (в сутках 86400 секунд)
Вполне рабочий сценарий, не так ли?
Какую частоту запросов должен иметь объект, чтобы входить в топ-100ГБ? Если последний объект из топ-1000ГБ запрашивается раз в сутки, то последний объект из топ-100ГБ запрашивается в 10 раз чаще, т.е. 10 раз в сутки (а чтобы попасть в топ-10ГБ — надо чтобы частота запросов составляла не менее 100 раз в сутки)
Сколько трафика сгенерят объекты не из топ-100ГБ (а из диапазона 100… 1000ГБ, т.е. объекты с частотой запросов от 10 в сутки и до 1 в сутки)? Считаем интеграл от 1/x (распределение Ципфа) в диапазоне от 100 до 1000 (и умножаем на 1000ГБ, чтобы частота менялась от 10 до 1 в сутки) — это дает нам (ln(1000)-ln(100)) * 1000ГБ = 2.3ТБ. Соответственно топ-100ГБ контента генерирует 6.3ТБ трафика, а кеш в 100ГБ (чтобы поместить этот топ-100ГБ контента) при идеальном заполнении обеспечивает 6.3/8.6 = 73% попаданий — весьма хороший hit-ratio, на самом деле.
А теперь смотрим дальше:
Пусть у нас в кеше лежит топ-100ГБ контента.
27МБ/c (27% от 800Мбит/c) незакешированных запросов при использовании LRU за 1000 секунд съедят до 27ГБ оперативки (на самом деле немного меньше, так как небольшая часть таких запросов будет повторятся). Ещё 1000 секунд — и вот кеш уже наполовину занят данными, которые не то что не входят в топ-100ГБ, а по большей части вообще плетутся в хвосте распределения. Теперь у нас кеш содержит не топ-100ГБ, как раньше, а уже топ-50ГБ (hit-ratio у которого, кстати, с 73% опускается до 65%).
Будет ли топ-50ГБ вымываться дальше? Будет, потому что минимальная частота у топ-50ГБ это 20 запросов в сутки (против 10 запросов у топ-100ГБ), т.е. раз в 4к секунд, а вымывался он до этого уровня всего 2к секунд. А т.к. hit-ratio понизился, то скорость вымывания соответственно выросла до 35МБ/c — за 2к секунд в кеш зайдет уже 70ГБ холодных данных, а останется топ-30ГБ (с соответствующим снижением hit-ratio до 60%).
В итоге процесс уравновесится где-то на уровне 20-25ГБ, фактически 3/4 кеша будут содержать холодные данные, а процент попаданий будет почти в полтора раза меньше от возможного. Называть ли такую стратегию кеширования эффективной — дело вкуса, но лично я так не считаю.
Частотность запросов распределена по закону Ципфа (т.е. объект на 100-м месте в ранге частотности будет иметь в 2 раза меньшую частоту запрашивания, чем объект на 50-м месте).
Кстати, при такой скорости 1ГБ скачивается за 10 секунд, 1ТБ — за 10к секунд, ну а за сутки соотв скачивается всего 8.6ТБ (в сутках 86400 секунд)
Вполне рабочий сценарий, не так ли?
Какую частоту запросов должен иметь объект, чтобы входить в топ-100ГБ? Если последний объект из топ-1000ГБ запрашивается раз в сутки, то последний объект из топ-100ГБ запрашивается в 10 раз чаще, т.е. 10 раз в сутки (а чтобы попасть в топ-10ГБ — надо чтобы частота запросов составляла не менее 100 раз в сутки)
Сколько трафика сгенерят объекты не из топ-100ГБ (а из диапазона 100… 1000ГБ, т.е. объекты с частотой запросов от 10 в сутки и до 1 в сутки)? Считаем интеграл от 1/x (распределение Ципфа) в диапазоне от 100 до 1000 (и умножаем на 1000ГБ, чтобы частота менялась от 10 до 1 в сутки) — это дает нам (ln(1000)-ln(100)) * 1000ГБ = 2.3ТБ. Соответственно топ-100ГБ контента генерирует 6.3ТБ трафика, а кеш в 100ГБ (чтобы поместить этот топ-100ГБ контента) при идеальном заполнении обеспечивает 6.3/8.6 = 73% попаданий — весьма хороший hit-ratio, на самом деле.
А теперь смотрим дальше:
Пусть у нас в кеше лежит топ-100ГБ контента.
27МБ/c (27% от 800Мбит/c) незакешированных запросов при использовании LRU за 1000 секунд съедят до 27ГБ оперативки (на самом деле немного меньше, так как небольшая часть таких запросов будет повторятся). Ещё 1000 секунд — и вот кеш уже наполовину занят данными, которые не то что не входят в топ-100ГБ, а по большей части вообще плетутся в хвосте распределения. Теперь у нас кеш содержит не топ-100ГБ, как раньше, а уже топ-50ГБ (hit-ratio у которого, кстати, с 73% опускается до 65%).
Будет ли топ-50ГБ вымываться дальше? Будет, потому что минимальная частота у топ-50ГБ это 20 запросов в сутки (против 10 запросов у топ-100ГБ), т.е. раз в 4к секунд, а вымывался он до этого уровня всего 2к секунд. А т.к. hit-ratio понизился, то скорость вымывания соответственно выросла до 35МБ/c — за 2к секунд в кеш зайдет уже 70ГБ холодных данных, а останется топ-30ГБ (с соответствующим снижением hit-ratio до 60%).
В итоге процесс уравновесится где-то на уровне 20-25ГБ, фактически 3/4 кеша будут содержать холодные данные, а процент попаданий будет почти в полтора раза меньше от возможного. Называть ли такую стратегию кеширования эффективной — дело вкуса, но лично я так не считаю.
Более логичным выглядит предположение, что популярность этого алгоритма вытекает из его простоты.
Скорее всего вы правы, но всё таки есть немало программистов, которые краем уха где-то слышали об оптимальности LRU при каких-то условиях, что частично оправдывает его использование (смотрите мой комментарий выше).
Sign up to leave a comment.
Эффективное кеширование. От теории к практике