К сожалению, в очередной раз заметил, что почти все мои коллеги не знают, что такое LRU, и как реализовать кэш определенного размера. Поэтому я решил написать небольшую статью, где расскажу как быстро реализовать метод LRU, и не вынуждать коллег вручную сбрасывать кэш там, где не требуется.
Мы будем под кэшированием понимать сохранение результатов вычислений в ответ на некоторые запросы. То есть, повторный результат запроса не всегда вычисляется заново, но иногда берется из таблицы, называемой кэшем. Сложно переоценить роль кеширования в современных системах. При этом часто возникает проблема, связанная с недостатком памяти. Действительно, что делать, если запросов много, а памяти хватает лишь для хранения ограниченного числа результатов? В этом случае, как правило, кеш стрится следующим образом. Фиксируется размер кэша, пусть будет N, и сохраняются результаты только для N самых «популярных» запросов.
То есть сохраняются результаты вычислений, которые скорее всего запросят заново.
Как определять эти «популярные» запросы? Наиболее известным способом является LRU, о котором я и расскажу в этой статье.
LRU (least recently used) — это алгоритм, при котором вытесняются значения, которые дольше всего не запрашивались. Соответственно, необходимо хранить время последнего запроса к значению. И как только число закэшированных значений превосходит N необходимо вытеснить из кеша значение, которое дольше всего не запрашивалось.
Для реализации этого метода нам понадобятся две структуры данных:
Предположим, что для исходных вычислений использовался метод calculate(x). Мы заменим метод calculate на новый calculateWithCache, который пополняет кеш, выталкивает устаревшие значения и запрашивает результат у calculate, если не найдет в кеше.
Так будет выглядеть алгоритм работы calculateWithCache:
Вот и все. Теперь вместо необходимости сбрасывать кэш пользователю необходимо задать размер кэша. При этом приветствуется задание разумного значения по-умолчанию.
Если воспользоваться эффективной реализацией очереди с приоритетами, то оверхед, который требует LRU — O(log N).
B стандартных библиотеках может быть реализована очередь с приоритетами, например, в C++. Но даже если не реализована, а читать лениво, то можно догадаться, как использовать сбалансированное дерево для реализации очереди с приоритетами с такой же сложностью, правда с чуть большим коэффициентом.
Вопрос для тех, кто хочет чуть подумать. Как добиться константного оверхеда, считая, что сложность операции с хеш-таблицей — константа?
Подсказка: нужно убрать очередь с приоритетами и использовать обычную очередь:)
Можно найти более сложные эвристики, учитывающие время вычисления calculate для данного ключа key, или объем результата, или что-то еще.
Но в большинстве задач LRU наиболее адекватно определяет самые «популярные» запросы.
Примечание 1: Можно ограничить объем памяти на кэш, а не количество хранимых значений. Алгоритм практически не изменится, только вместо длины будет занимаемая память + память для хранения нового значения.
Примечание 2: Специально избегал вопросов многопоточности, так как это не тема данной статьи.
Update (Спасибо ToSHiC22 за комментарий) Для интересующихся ссылка на чуть более продвинутую реализацию 2Q
Мы будем под кэшированием понимать сохранение результатов вычислений в ответ на некоторые запросы. То есть, повторный результат запроса не всегда вычисляется заново, но иногда берется из таблицы, называемой кэшем. Сложно переоценить роль кеширования в современных системах. При этом часто возникает проблема, связанная с недостатком памяти. Действительно, что делать, если запросов много, а памяти хватает лишь для хранения ограниченного числа результатов? В этом случае, как правило, кеш стрится следующим образом. Фиксируется размер кэша, пусть будет 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
