Я верно что понял HTTP Pipelining отключен, например в хроме, фаерфоксе и ее не рекомендуют использовать?
https://www.chromium.org/developers/design-documents/network-stack/http-pipelining
http://kb.mozillazine.org/Network.http.pipelining
В связи с этим — интересно было бы увидеть более приближенные к реальности результаты тестов, без Pipelining.
На хабре неплохо с технологиями. Но это не значит, что нельзя лучше. Есть довольно много нюансов. Взять, например, рекомендации к данной статье. Я прочел все три эти статьи несколько лет назад. Очевидно что в Вашем алгоритме это не учтено. Не хочется быть голословным, давайте сделаем A/B тест рекомендации relap vs рекомендации habr с аудитом через гугл аналитикс?
Немножко смотрел. Пишут, что он проще в разработке по сравнению с 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)
В случае изображенном на Вашем скриншоте (размер значения превышает размер контейнера) — большая картинка отправится сразу в ад (не будет помещена в кеш), сохранив место в кеше для более мелких элементов.
Не совсем так. LRU ведет себя хуже всех на всех тестах, вне зависимости от реализации с учетом размера элементов или нет, на сайте или в приложении, для урлов или для картинок, для хитов или для рекомендаций, наверное даже банальный рандом возьмите — LRU всегдапроигрываетвсем. Статья вобщем то не о том какой 2Q прекрасный, статья о том, что LRU это худщий алгоритм из всех существующих.
— Не учитывается частота использования элементов (100 раз запросили или 1 — LRU все равно)
— Очень длинный период вытеснения редко используемых элементов
— Нет защищенных областей
— Не эффективно используется память
Единственный его плюс — его очень легко понять.
Судя по сорцам — в memcached SNLRU + возможность задания «протухания ключа» по времени. Только в SNLRU разные блоки — не для разных размеров, они по частоте обращений делятся на cold,warm,hot
Вы абсолютно правы, мы всегда тестируем прежде чем выбрать
Вот некоторые результаты
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
1024*1024*10 — это максимальный размер кеша, это и есть ограничение. Эту реализацию писал я, она великолепно работает и я прекрасно понимаю как, только Вам объяснить не могу)
Используйте готовые библиотеки если не можете понять. Это нормально. Так делают 80% программистов
/**
* 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
/**
* 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;
}
Когда кажется — крестятся, а когда хотят проверить код пишут тест
Извините, немного раздражают подобные утверждения
Условия идентичны конечно. Выделенная под кеш память в одном случае не делится, а в другом — режется на три области. Про откуда брать картинки — вопрос настолько странный что я даже не знаю как ответить.
https://www.chromium.org/developers/design-documents/network-stack/http-pipelining
http://kb.mozillazine.org/Network.http.pipelining
В связи с этим — интересно было бы увидеть более приближенные к реальности результаты тестов, без Pipelining.
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
Должно получится своеобразное предсказание (шаг на пути к идеальному алгоритму:))
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)
— Не учитывается частота использования элементов (100 раз запросили или 1 — LRU все равно)
— Очень длинный период вытеснения редко используемых элементов
— Нет защищенных областей
— Не эффективно используется память
Единственный его плюс — его очень легко понять.
Вот некоторые результаты
Используйте готовые библиотеки если не можете понять. Это нормально. Так делают 80% программистов
Пример
То же самое, перекрытие метода и задание размера — необходимо сделать если вы используете библиотеку LRU от Google из фреймворка андроид
И конечно условия идентичные.
Друзья, наверно я сложно и запутанно объяснил: вот ссылка на каноническое описание от авторов 2Q
http://www.vldb.org/conf/1994/P439.PDF
Так понятней?
TwoQCacheImpl twoQueues = new TwoQCacheImpl(1024 * 1024 * 10);
Необходимо перекрыть данный метод Если размер элемента отличен от 1, например так:
Когда кажется — крестятся, а когда хотят проверить код пишут тест
Извините, немного раздражают подобные утверждения