Эффективное кеширование. От теории к практике

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?

Давайте рассмотрим сферическое приложение в вакууме. Пусть это будет мессенджер, его проще всего представить.

скриншот_из_телеграмм.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 — вот она картинка победительница. Кеш на уровне архитектуры корректирует некие типичные корреляции, присутствующие в обычной жизни. И после внедрения исчезли постоянные перезагрузки в условиях ограниченного размера памяти. Парето сработал. Но мы еще не раз вернемся к Парето.

Во первых, перейдем к нюансам. Когда читаешь про три коробочки, есть невольный соблазн прямо так тупо и сделать три связанных списка и гонять по ним элементы. Но это неэффективный путь, и как-то не по-джедайски. На самом деле, нам нужно знать только, в какой коробочке лежит ключ, а сами значения могут валяться в это время в некой безобразной куче. Перейдем же скорее к программированию.

Реализация на 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 {
    /** Primary container */
    private final HashMap map;
    /** Sets for 2Q algorithm */
    private final LinkedHashSet 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(0,0.75f);

        mapIn = new LinkedHashSet();
        mapOut = new LinkedHashSet();
        mapHot = new LinkedHashSet();
    }

    /**
     * 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 copy = new HashMap(map);
            evictAll();
            Iterator 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
     * 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.
     *
     * 

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. * *

The method is called without synchronization: other threads may * access the cache while this method is executing. * *

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. * *

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 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 snapshot() { return new HashMap(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 map;
    /** Sets for 2Q algorithm */
    private final LinkedHashSet 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

Итак, не важно, что вы пишете: сайт, хайлоад-сервис, мобильное приложение или операционную систему, реализовав единожды умный алгоритм кеширования, вы можете использовать его повсеместно, экономя ресурсы и нервы пользователя.

Комментарии (1)

  • 29 июля 2016 в 19:24

    0

    Сняли небольшое видео о том, как устроен 2Q, но звук/качество получилось к сожалению не очень, вставлять постеснялись, а выкидывать жалко (Вот оно:

© Habrahabr.ru