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

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

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

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

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

Для реализации этого метода нам понадобятся две структуры данных:
Хеш-таблица hashTable, которая будет хранить непосредственно закэшированные значения.
Очередь с приоритетами 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;
}

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

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

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

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

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

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

Update (Спасибо ToSHiC22 за комментарий) Для интересующихся ссылка на чуть более продвинутую реализацию 2Q

Ссылки по теме

• Каталог программ средств разработки ПО
• Купить программное обеспечение компании Microsoft