LRU

К словарю | К разделу Fundamentals

LRU (Least Recently Used) — стратегия вытеснения данных из ограниченного
хранилища, при которой первым удаляется элемент, к которому дольше всего не
обращались.

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

Как работает LRU-кеш

LRU-кеш хранит элементы и порядок их последнего использования.

Операции:

• get(key) — возвращает значение и помечает элемент как недавно
  использованный;
• put(key, value) — добавляет или обновляет элемент и тоже помечает его как
  недавно использованный;
• если после добавления превышен лимит, удаляется least recently used элемент.

Пример для кеша ёмкостью 3:

1. Добавили A, B, C.
2. Обратились к A, теперь он считается недавно использованным.
3. Добавили D.
4. Вытесняется B, потому что к нему обращались раньше, чем к C и A.

Типичная реализация

Классическая реализация LRU-кеша использует две структуры данных:

• hash map для доступа к элементу по ключу за O(1);
• двусвязный список для хранения порядка использования и перемещения
  элемента в начало за O(1).

Обычно начало списка означает самые недавно использованные элементы, а конец —
кандидатов на вытеснение.

При get элемент находится в hash map и переносится в начало списка. При put
новый элемент добавляется в начало, а при превышении лимита удаляется хвост
списка и соответствующая запись из hash map.

Где применяется

LRU подходит, когда есть временная локальность доступа: если объект недавно
использовался, есть высокая вероятность, что он понадобится снова.

Примеры:

• in-memory кеши в приложениях;
• page cache и буферы операционной системы;
• кеширование результатов дорогих вычислений;
• кеши ORM, HTTP-клиентов и API gateway;
• ограничение размера локального кеша в мобильных или desktop-приложениях.

Преимущества

• простая и понятная модель вытеснения;
• хорошо работает для многих реальных workload с временной локальностью;
• операции можно реализовать за O(1);
• легко объяснять и отлаживать на собеседовании.

Ограничения

LRU не всегда оптимален.

Проблемные случаи:

• последовательное сканирование большого набора данных может вытеснить
  полезные горячие элементы;
• редкий, но массовый всплеск обращений может испортить состояние кеша;
• стратегия учитывает только факт последнего доступа, но не частоту,
  стоимость пересчёта или размер объекта;
• в распределённых системах порядок использования может быть локальным для
  конкретного узла и не отражать глобальную картину.

Если важна частота обращений, рассматривают LFU. Если данные имеют разный
размер или разную стоимость восстановления, применяют более сложные политики
вытеснения.

Что важно сказать на собеседовании

LRU — это не просто «удаляем старое». Важны две детали:

• элемент становится недавно использованным и при чтении, и при записи;
• эффективная реализация требует связки hash map и двусвязного списка, иначе
  операции обновления порядка могут стать дорогими.

Хороший ответ также должен упомянуть, что LRU является эвристикой. Она полезна
при временной локальности, но может плохо работать на workload с большими
последовательными проходами по данным.