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

    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, бам!
    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

    Итак, не важно, что вы пишете: сайт, хайлоад-сервис, мобильное приложение или операционную систему, реализовав единожды умный алгоритм кеширования, вы можете использовать его повсеместно, экономя ресурсы и нервы пользователя.
    Surfingbird
    0.00
    Company
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 59

      +3
      Сняли небольшое видео о том, как устроен 2Q, но звук/качество получилось к сожалению не очень, вставлять постеснялись, а выкидывать жалко( Вот оно:
        +1
        Как то странная логика у вас. Для LRU кэша большая картинка вытесняет маленькие потому что для маленьких нет места в кэше. Однако для 2Q кэша вы просто делаете в 3 раза больший размер кэша и все у вас помещается. Хотелось бы сравнения в равных условиях.
        Да и в целом описание 2Q не понятно — откуда брать картинки? Из In? Из Out? Из Hot?
          0
          Условия идентичны конечно. Выделенная под кеш память в одном случае не делится, а в другом — режется на три области. Про откуда брать картинки — вопрос настолько странный что я даже не знаю как ответить.
            0
            А я не совсем понял, почему в LRU большая картинка, должна выкинуть все маленькие? У вас есть какое-то ограничение по памяти? Если да, то в вашей реализации на основе Map я его не вижу. В вашем случае можно всегда модифицировать очередь приоритетов для LRU и раставлять его чуть ли не руками. Ну и выходит что условия не идентичны.
              0
              Конечно есть ограничения по памяти
              /**
                   * 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
              Так понятней?
                +1
                У вас size любых объектов равен 1. Так что ограничений по памяти у вас нет! Только по количеству элементов.
                  0
                  В случае если размер отличен от 1 — этот метод перекрывается:
                  Пример

                  То же самое, перекрытие метода и задание размера — необходимо сделать если вы используете библиотеку LRU от Google из фреймворка андроид
                    0
                    Ок, если вы его завераидили, то все понятно. Но чисто в теории при прокрутке туда сюда, большая картинка может попасть в hot и выкинуть оттуда ваши аватарочки. +Ваш код довольно не оптимален, когда с кэшем будет работать много потоков.
              +3
              Хорошо, предположим что сумма размеров одинакова:
              https://habrastorage.org/files/249/aca/dd8/249acadd8e8640b8a0b4a488a9160c66.png
              Объясните — куда поместится большая картинка в вашем случае?
              Если же сделать так, чтобы большая картинка помещалась в ваш контейнер, то его придется увеличить, а если размеры равны, то придется увеличить и LRU контейнер и вот уже маленькие картинки перестанут вытесняться.
                0
                В случае изображенном на Вашем скриншоте (размер значения превышает размер контейнера) — большая картинка отправится сразу в ад (не будет помещена в кеш), сохранив место в кеше для более мелких элементов.
                0
                В первом случае (LRU) выделяется фиксированная память, а во втором (2Q) — она никак не ограничена. Так что тест у вас не корректный.
                  0
                  LruCache lruCache = new LruCache(1024 * 1024 * 10);
                  TwoQCacheImpl twoQueues = new TwoQCacheImpl(1024 * 1024 * 10);
                    0
                    Смотрите мой ответ выше. Из текста вашего поста следует, что LRU ограничен по помяти, т.к. большая картинка вытесняет маленькие. А TwoQCacheImpl может хранить 1024*1024*10 элементов без ограничения по памяти. Складывается такое впечатление, что либо не вы писали эту реализацию, либо не понимаете как она работает.
                      0
                      1024*1024*10 — это максимальный размер кеша, это и есть ограничение. Эту реализацию писал я, она великолепно работает и я прекрасно понимаю как, только Вам объяснить не могу)
                      Используйте готовые библиотеки если не можете понять. Это нормально. Так делают 80% программистов
                        0
                        Ну если у вас элементы по 1 байту, то да :) Прогоните код. Получается, что все комментаторы ламеры, а вы Д’Артаньян :)
                          0
                          Размер считается тут
                          Однако почему-то в килобайтах, а не в байтах. Так что сравнение и правда некорректное :)
                +1
                Очевидно, что размер кэша таков, что он может вместить не одну большую картинку, а несколько. Вопрос в том, что будет вытеснено, когда после одной большой картинки придет очередная большая картинка, а места в кэше нет. В алгоритме LRU она вытеснит маленькие картинки, т.к. они дольше не использовались, а в алгоритме 2Q маленькие картинки не удалятся, т.к., они уже в Main. А большая картинка вытеснится, когда придет ее очередь, т.к. она использовалась лишь однократно
                0
                При переходе и Out в Hot элемент из списка Out сразу удялается буд-то он внизу оказался, или остается? Это отличие должно довольно сильно повлять на ситуацию, когда элемент будет выкинут из Hot.
                0
                JDK 4? если более новый, то лучше, наверное, посмотреть в сторону java.util.concurrent с подпакетами вместо synchronized. Синхронизированные методы блокируют все доступы к объекту.
                  –1
                  Мне кажется этот код — вообще не рабочий. Например: это что, заглушка какая то?
                  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;
                       }
                    


                    Когда кажется — крестятся, а когда хотят проверить код пишут тест
                    Извините, немного раздражают подобные утверждения
                  0
                  Если большая картинка вытесняла маленькие в LRU, то поему она не вытеснит их в Вашем варианте?

                  Может большие картинки в кеш не ложить и все? :)
                    0
                      0
                      Если большая картинка вытиснила маленькие в первом случае из-за нехватки памяти, согласно статье, то никакой алгоритм тут не спасёт. И автор статьи использует НЕ классический 2Q. Достаточно перейти по ссылке в статье http://www.vldb.org/conf/1994/P439.PDF.

                      А вот 2Q решает эту проблему тем, что OUT хранит исключительно ключи, а не значения, и не обязан быть большим по памяти.
                      В свою очередь MAIN защищает данные от «вымывания».
                      А IN защищает от попадания в MAIN временно частых запросов.

                      2Q — это не убер-алгоритм, но он идеально подходит для кэширования данных генерируемых поведением пользователя.

                      Всегда пожалуйста)
                        0
                        Спасибо за доходчивое объяснение, но не совсем согласен. Размер имеет значение. Прочитайте боль разработчиков постгри:

                        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)
                          0
                          Я явно передавал в mysql SQL_NO_CACHE
                          А потом вообще кеш отключил
                          Все кеширует приложение
                          Зачем 2 кеша?
                            0
                            субд держит кеш в памяти своего процесса. так что обращение к кешу внутри субд явно быстрей чем обращение к внешнему кешу из приложения
                        0
                        Я не понимаю, почему заминусовали?
                        Типа я повторил то, что писали другие выше 100500 раз?

                        Пост долго был на премодерации.
                        • UFO just landed and posted this here
                      • UFO just landed and posted this here
                          0
                          Вы странные…
                          Как можно судить об эффективности алгоритмов, без учета характеристик используемых данных и характера их использования?!
                          Имхо, выбор (или создание) эффективного алгоритма кэширования, напрямую проистекает из того, как именно, и какие данные используются в каждом конкретном случае. Без учета этой информации, построение эффективного алгоритма кэширования значительно затрудняется…
                            0
                            Вы абсолютно правы, мы всегда тестируем прежде чем выбрать
                            Вот некоторые результаты
                            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
                            
                            +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, хотя элемент же уже был в множестве, ведь размер не поменялся?
                              0
                              Спасибо! В пулл реквесте в этом месте пара remove/add Заведем репозиторий под это дело чтоб не путаться
                              +1
                              Думал, будет упоминание про LIRS, весьма любопытный алгоритм по своей идее, в MySql и Infinispan судя по всему используется
                                0
                                Немножко смотрел. Пишут, что он проще в разработке по сравнению с 2Q, а к минусам — то что он прожорливее по памяти. Проще понять наверно по реализации чем по описанию. Надо сравнивать(
                                0
                                А только мне кажется странным, что LRU объявлен неудачником и полным УГ на основании примера с большой картинкой? Ведь в алгоритме LRU никак не учавствует размер элемента. Взят довольно вырожденный случай, когда алгоритм поведет себя плохо. Но таким образом оценивать эффективность это же абсурд?
                                  0
                                  Не совсем так. LRU ведет себя хуже всех на всех тестах, вне зависимости от реализации с учетом размера элементов или нет, на сайте или в приложении, для урлов или для картинок, для хитов или для рекомендаций, наверное даже банальный рандом возьмите — LRU всегда проигрывает всем. Статья вобщем то не о том какой 2Q прекрасный, статья о том, что LRU это худщий алгоритм из всех существующих.

                                  — Не учитывается частота использования элементов (100 раз запросили или 1 — LRU все равно)
                                  — Очень длинный период вытеснения редко используемых элементов
                                  — Нет защищенных областей
                                  — Не эффективно используется память
                                  Единственный его плюс — его очень легко понять.
                                    0
                                    Вы совсем как-то заклеймили 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.
                                  +1

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

                                    0
                                    Я решил обновить публичную имплементацию алгоритма CART до v0.2:
                                    https://github.com/tridemax/CART

                                    Интересно было бы сравнить эффективность. =)
                                      0
                                      Нет ли случайно планов перенести реализацию на ванильный C? Чтоб встроить в тот же Nginx, и по хардкору развлекаться?
                                        0
                                        А что, в Nginx нельзя закомпиленный C++ модуль вкрутить? Пусть даже и с внешним С-шным интерфейсом?
                                          0
                                          Вкрутить вроде вкручивают… Там еще некий tbb… У нас вроде никто на C++ не пишет, даже спросить некого
                                            0
                                            TBB очень легко подключается к проектам. Проблем вообще не должно быть. Гугл полон пошаговых инструкций. :)
                                      0
                                      Кстати, в memcached вроде LRU, но там блоки разных размеров хранятся отдельно.
                                      То есть, большие и маленькие не пересекаются.
                                        0
                                        Судя по сорцам — в memcached SNLRU + возможность задания «протухания ключа» по времени. Только в SNLRU разные блоки — не для разных размеров, они по частоте обращений делятся на cold,warm,hot
                                          0
                                          Нет, там slab-ы именно по размерам…
                                        0
                                        Применительно к Android, можно использовать https://github.com/candrews/HttpResponseCache.
                                          +1
                                          LRU конечно плох, но и все эти зонные алгоритмы не сказать что идеальны.
                                          Как по мне, надо просто для каждого объекта считать частоту запросов с експоненциальным затуханием (т.е. через T времени накопленная частота снизится в E раз), и просто вытеснять из кеша объекты с самой маленькой частотой.

                                          Частоту запросов можно описать такой структурой { LastAccess uint32, Rate float32 }
                                          И при каждом хите обновлять её:
                                          Rate = 1 + Rate / exp((Now() — LastAccess) * DAMPING_FACTOR)
                                          LastAccess = Now()

                                          При таком подходе в кеше асимптотика заполнения кеша будет стремиться к идеальной — в нем будут самые часто запрашиваемые объекты.
                                            +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

                                            Должно получится своеобразное предсказание (шаг на пути к идеальному алгоритму:))
                                              0
                                              По большому счёту, зонные алгоритмы — это грубое приближение экспоненциального затухания.

                                              Более тонкое приближение — мысленно отсортировать ключи по частоте-с-затуханием.
                                              И считать, что частота обратно пропорциональна индексу.

                                              Тогда обновление состоит в том, что если ключ был в ячейке с индексом z, надо его перенести его в ячейку x = z/DAMPING_FACTOR (сдвинув, разумеется, все элементы x..z вправо).
                                                0
                                                Конкретно в таком виде это не будет работать. Регулярно будет ситуация, когда в ячейку x будет помещаться режезапрашиваемый объект, чем в ячейке x+1, а значит «частота обратно пропорциональна индексу» очень быстро перестанет быть таковой.

                                                Но идея с перемещением елемента в индексе в целом продуктивна. Так как основная задача состоит в том, чтобы отделить редкозапрашиваемые объекты от частозапрашиваемых, то, видимо, будет достаточно при каждом хите перемещать объект ближе к голове списка на одну позицию (простой обмен с соседним элементом). Тогда частозапрашиваемые объекты сконцентрируются у головы списка, а редкозапрашиваемые — у хвоста, причем чем реже будут запрашиваться — тем ближе к хвосту.
                                                Новый объект вполне безопасно помещать в начало списка — если он популярный, то там и останется, если нет — его обгонят более популярные, а сам елемент уйдет в хвост и в итоге будет вытеснен.
                                              0
                                              Управление «кучками» реализовано на супербыстрых и экономичных по памяти LinkedHashSet, нам не важно значение, важно лишь в какой «кучке» какой ключ находится в данный момент. Это ключ к быстродействию.

                                              Хотелось бы подробностей, почему именно LinkedHashSet, а не обычный HashSet.
                                              LinkedHashSet используется тогда, когда важен порядок добавления, а вы пишете, что «важно лишь в какой «кучке» какой ключ находится в данный момент».
                                                +2
                                                Пассаж про LRU и его «неэффективность» весьма категоричен, поэтому неверен. Возможно его встраивают по-умолчанию не просто так, а потому что он естественным образом подходит для многих случаев?

                                                Вот тут хорошо про стратегии:


                                                Вкратце перескажу содержание: в 60х года прошлого века математики доказали что наиболее эффективным алгоритмом вытеснения (минимизирует cache-miss) будет алгоритм, который вытесняет тот элемент, запрос к которому будет произведен позже других элементов. Принцип очень прост, но, к сожалению, в будущее никто заглядывать не умеет — поэтому остается строить догадки, какой именно из элементов будет запрошен из кэша позже всего. Например, можно предположить, что если элемент запрашивали недавно, то его запросят скоро еще раз, поэтому выгоднее выталкивать элементы, которые уже долго никто не запрашивал (LRU). Однако предметная область у каждого разная, и алгоритм вытеснения подбирается под ситуацию: например, мы всеми силами можем стараться сохранить в кэше картинки с совушками, а вот картинки с Гитлером выталкивать при любом удобном случае.

                                                Другим интересным моментом оказывается то, что хоть мы и не можем смотреть в будущее, смотреть в прошлое нам никто не запрещает. Поэтому если взять логи запросов и логи вытеснения мы можем оценить насколько эффективно работает наш алгоритм вытеснения и не пора ли его поменять или оттюнить.

                                                Кроме эффективности самого алгоритма вытеснения существуют чисто технические проблемы эффективности: уменьшение contention при конкурентном доступе к кешу (например разделением на регионы или разделением кэшей по типам данных), оптимизация внутренних структур, баланс между идеальными показателями cache-miss и временем доступа.

                                                  0
                                                  Возможно его встраивают по-умолчанию не просто так, а потому что он естественным образом подходит для многих случаев?
                                                  Более логичным выглядит предположение, что популярность этого алгоритма вытекает из его простоты.

                                                  Эффективность LRU весьма невысока — если после запроса любого объекта будет запрошено N других разных объектов, где N > размер кеша, то исходный объект будет вытеснен, даже если он будет самым! частозапрашиваемым. Например, для вырожденного случая, когда у нас есть кеш размером N, и набор из M объектов (M > N), которые запрашиваются равномерно по кругу (1, 2,…, M-1, M, 1, 2 ..) — эффективность LRU кеша будет равна 0% — в кеше всегда будут последние N запрошенных объектов и ни одного из тех, который будет запрошен до того, как будет вытеснен из кеша.

                                                  При разработке стратегии кеширования предпочтительнее учитывать всю частоту (усредненную каким-либо образом) запрашивания объекта, а не одно лишь время, прошедшее с последнего запроса.
                                                    0
                                                    Я бы предложил употреблять более конкретные заявления — «эффективность при сценарии, который заключается в том, что ...». В большинстве случаев, когда кэширование действительно требуется мы можем наблюдать четкий сценарий использования и универсальные алгоритмы не нужны.

                                                    В данном случае у вас искусственный, специфичный сценарий использования. В то время как для большинства сервисов можно выделить «горячий» контент, который постоянно находится в ротации (обычно свежий) и «холодный» контент, который запрашивают очень редко. В таких случаях при правильном размере кэша LRU вытеснение горячего контента маловероятно и особого вреда в массе не приносит.

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

                                                      Скорее всего вы правы, но всё таки есть немало программистов, которые краем уха где-то слышали об оптимальности LRU при каких-то условиях, что частично оправдывает его использование (смотрите мой комментарий выше).

                                                  Only users with full accounts can post comments. Log in, please.