Ефективне кешування. Від теорії до практики

image

Як правило, статті про кешировании починаються за здравіє, а закінчуються 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?



Давайте розглянемо сферичне додаток в вакуумі. Нехай це буде месенджер, його найпростіше уявити.

скриншот_из_телеграмм.јрд

Якщо уважно подивитися на скріншот, то можна побачити, що повідомлення користувачів супроводжуються аватарками, а в тілі повідомлення — трапляються картинки. Перед вами стоїть завдання — зробити максимально плавний інтерфейс. Давайте ще раз поглянемо на скріншот вище. Ми бачимо 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 handle to better 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 any time again 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 — ось вона картинка переможниця. Кеш на рівні архітектури коригує якісь типові кореляції, присутні в звичайному житті. І після впровадження зникли постійні перезавантаження в умовах обмеженого розміру пам'яті. Парето спрацював. Але ми ще не раз повернемося до Парето.

По-перше, перейдемо до нюансів. Коли читаєш про три коробочки, є мимовільний спокуса прямо так тупо і зробити три пов'язаних списку і ганяти по ним елементи. Але це неефективний шлях, і якось не по-джедайски. Насправді, нам потрібно знати тільки, в який коробочці лежить ключ, а самі значення можуть валятися в цей час в якійсь потворної купи. Перейдемо ж швидше до програмування.

Реалізація на java, бам!
import java.util.*;

/**
* 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 TwoQueuesCache<K, V> {
/** Primary container */
private final HashMap<K,V> map;
/** Sets for 2Q algorithm */
private final LinkedHashSet<K> mapIn, mapOut, mapHot;

private final 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 TwoQueuesCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}

calcMaxSizes(maxSize);

map = new HashMap<K, V>(0,0.75 f);

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
*/
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 final 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.add(key);
sizeHot += safeSizeOf(key, mapValue);
trimMapHot();
}
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 final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}

if (safeSizeOf(key, value) > maxSizeIn) {
//throw new IllegalArgumentException("value size is too big for store");
System.out.println("Warning! TwoQueuesCache:"+"value size is too big for store in cache.\n" +
"MaxSizeIn: "+maxSizeIn+ "\nStored: "+safeSizeOf(key, value)+
"\nKey:"+key.toString()
);
}

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
* @return
*/
private boolean trimMapIn(final int sizeOfValue) {
boolean result = false;
if (maxSizeIn < sizeOfValue) {
return result;
}
else {
while (mapIn.iterator().hasNext()) {
K keyIn = null;
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
* @param sizeOfValue
* @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 final V remove(K key, V replace) {
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
* when invoked 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>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 повертає null.
*
* <p>The method is called without synchronization: other threads may
* access the cache while this method is executing.
*
* <p>If a value for {@code key} exists in the cache when this method
* returns, created the value will be released with {@link #entryRemoved}
* and discarded. This can occur when multiple threads request the same key
* at the same time (заподіяння 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>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 final void evictAll() {
Iterator<K> it = map.keySet().iterator();
while (it.hasNext()) {
K key = it.next();
it.remove();
remove(key, map.get(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();
}
}



Зверніть увагу на контейнери:
/** 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

Отже, не важливо, що ви пишете: сайт, хайлоад-сервіс, мобільний додаток або операційну систему, реалізувавши один раз розумний алгоритм кешування, ви можете використовувати його повсюдно, економлячи ресурси і нерви.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.