0,0
рейтинг
22 января 2012 в 17:05

Разработка → LRU, метод вытеснения из кэша

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

Мы будем под кэшированием понимать сохранение результатов вычислений в ответ на некоторые запросы. То есть, повторный результат запроса не всегда вычисляется заново, но иногда берется из таблицы, называемой кэшем. Сложно переоценить роль кеширования в современных системах. При этом часто возникает проблема, связанная с недостатком памяти. Действительно, что делать, если запросов много, а памяти хватает лишь для хранения ограниченного числа результатов? В этом случае, как правило, кеш стрится следующим образом. Фиксируется размер кэша, пусть будет N, и сохраняются результаты только для N самых «популярных» запросов.

То есть сохраняются результаты вычислений, которые скорее всего запросят заново.
Как определять эти «популярные» запросы? Наиболее известным способом является LRU, о котором я и расскажу в этой статье.

LRU (least recently used) — это алгоритм, при котором вытесняются значения, которые дольше всего не запрашивались. Соответственно, необходимо хранить время последнего запроса к значению. И как только число закэшированных значений превосходит N необходимо вытеснить из кеша значение, которое дольше всего не запрашивалось.

Для реализации этого метода нам понадобятся две структуры данных:
  1. Хеш-таблица hashTable, которая будет хранить непосредственно закэшированные значения.
  2. Очередь с приоритетами timeQueue. Структура, которая поддерживает следующие операции:
    • Добавить пару значение и приоритет timeQueue.Add(val, priority).
    • Извлечь (удалить и вернуть) значение с наименьшим приоритетом timeQueue.extractMinValue().
Подробнее про очереди с приоритетами можно почитать здесь

Предположим, что для исходных вычислений использовался метод calculate(x). Мы заменим метод calculate на новый calculateWithCache, который пополняет кеш, выталкивает устаревшие значения и запрашивает результат у calculate, если не найдет в кеше.

Так будет выглядеть алгоритм работы calculateWithCache:

calculateWithCache(key) {
    curTime = getCurrentTime();
    // Если значение уже было в кэше вернем его
    if (key in hashTable) {
        // Сначала обновим время последнего запроса к key
        timeQueue.set(key, curTime);
        return hashTable[key];
    }
    // Иначе вычислим результат
    result = calculate(key);

    // Если в кэше уже N элементов, то вытесним самый старый
    if (hashTable.length == N) {
        minKey = timeQueue.extractMinValue();
        hashTable.remove(minKey);
    }
	
    // Добавим в таблицу, и в очередь
    hashTable.add(key, result);
    timeQueue.add(key, curTime);
	
    return result;
}


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

Если воспользоваться эффективной реализацией очереди с приоритетами, то оверхед, который требует LRUO(log N).

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

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

Можно найти более сложные эвристики, учитывающие время вычисления calculate для данного ключа key, или объем результата, или что-то еще.
Но в большинстве задач LRU наиболее адекватно определяет самые «популярные» запросы.

Примечание 1: Можно ограничить объем памяти на кэш, а не количество хранимых значений. Алгоритм практически не изменится, только вместо длины будет занимаемая память + память для хранения нового значения.
Примечание 2: Специально избегал вопросов многопоточности, так как это не тема данной статьи.

Update (Спасибо ToSHiC22 за комментарий) Для интересующихся ссылка на чуть более продвинутую реализацию 2Q
Алексеев Алексей @Pr0grammer
карма
34,0
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

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

  • +6
    А чем двусвязный список + hash не угодил, зачем хранить время?
    • 0
      Ну да это и есть ответ на вопрос, просто исходный LRU описывается именно с временами. Да и мне кажется, что проще понять.
      • 0
        По-моему, стопка листов, в которую новый кладем сверху, а самый старый забираем снизу, понятнее.
        • +1
          Не только. Если лист в середине и спрашивается опять, то он должен быть поднят наверх.
          Для этого нужен именно двусвязанный список и еще хеш-таблица, для отслеживания какой лист на каком месте. Как правильно сказали в самом первом комментарии.
  • +3
    Варианты с одной очередью не очень хороши — однократно запрошенные элементы будут вытеснять чуть менее популярные элементы, которые запрашивали много раз. В интернетах встречаются статьи про кэши 2Q, где эта проблема частично решена: хэш-таблица для поиска элементов и 2 очереди. Сначала элемент попадает в нижнюю очередь, а если его запросили второй раз и он всё ещё в кэше — то тогда в верхнюю. Когда верняя очередь заканчиваются — элементы из неё вытесняются в нижнюю, из нижней же элементы вытесняются совсем и удаляются из кэша. Получается константное время поиска записи и её добавления

    Кстати, в бусте есть контейнер, который отлично подходят для подобных схем — intrusive list. Ну и ещё intrusive hashmap, чтобы уж совсем минимально с памятью работать.
    • +1
      Спасибо, читал в процессе написания статьи, и решил не грузить. Добавил ссылку для интересующихся.
  • 0
    О том какие готовые решения предоставляет Java можно почитать в статье Java LRU Cache
  • 0
    А как решаем проблему консистентности?

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.