LRU-алгоритм

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

Принцип работы

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

Работу LRU можно описать следующей последовательностью шагов:

1. При запросе данных сначала проверяется, есть ли они в кэше (cache hit — попадание).
2. Если данные есть, они возвращаются, а их метка времени обновляется.
3. Если данных нет (cache miss — промах), они загружаются из основного хранилища.
4. Если в кэше есть свободное место, данные добавляются с текущей меткой времени.
5. Если свободного места нет, находится элемент с наименьшим значением метки времени (самый старый), он удаляется, и на его место помещается новый элемент.

Реализации

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

Простейшая реализация (связанный список + хеш-таблица)

Наиболее распространённая и эффективная реализация использует комбинацию двусвязного списка и хеш-таблицы (словаря). В двусвязном списке элементы хранятся в порядке от самого недавно использованного (в начале списка) до самого давнего (в конце). Хеш-таблица позволяет быстро находить элемент в списке по его ключу.

• Доступ к элементу: по ключу через хеш-таблицу находится узел списка. Если элемент найден, он перемещается в начало списка (удаляется с текущей позиции и вставляется в начало). Время операции — O(1).
• Вставка нового элемента: если кэш не заполнен, новый элемент добавляется в начало списка, а его ключ и ссылка на узел заносятся в хеш-таблицу. Если кэш заполнен, удаляется последний элемент списка (наименее недавно использованный), его запись удаляется из хеш-таблицы, после чего новый элемент добавляется в начало. Время операции — O(1).
• Удаление элемента: элемент удаляется из списка и из хеш-таблицы. Время операции — O(1).

Реализация на основе массива (счётчик)

В системах с ограниченными ресурсами или при небольшом размере кэша может использоваться массив с метками времени. Каждому элементу кэша присваивается счётчик обращений или метка времени. При каждом обращении счётчик текущего элемента сбрасывается, а счётчики остальных элементов увеличиваются. При вытеснении удаляется элемент с наибольшим значением счётчика. Недостаток — необходимость обновлять все счётчики при каждом обращении, что даёт сложность O(n) для операций доступа.

Реализация на основе стека

Стек, в котором при каждом обращении к элементу он перемещается на вершину, а при вытеснении удаляется элемент с дна. Требует O(n) операций для поиска и перемещения элемента в стеке.

Разновидности и модификации

LRU-K

Улучшенная версия, учитывающая не только последнее обращение, а историю последних K обращений. При вытеснении сравнивается время K-го по счёту последнего обращения. Позволяет точнее оценить частоту использования данных, но требует больше памяти для хранения истории.

Segmented LRU (SLRU)

Разделяет кэш на два сегмента: «пробный» (probationary) и «защищённый» (protected). Новые элементы сначала попадают в пробный сегмент. Если к элементу обращаются повторно, он перемещается в защищённый сегмент. Вытеснение происходит из пробного сегмента по LRU, а из защищённого — только при его переполнении, при этом элемент перемещается обратно в пробный. Используется, например, в кэше страниц операционной системы FreeBSD.

Clock (Second Chance)

Приближённая версия LRU, использующая бит доступа (reference bit) вместо точного времени. Элементы организованы в циклический буфер (кольцо). Алгоритм проходит по буферу, проверяя бит доступа: если бит установлен (к элементу обращались), он сбрасывается, и алгоритм переходит к следующему элементу; если бит не установлен, элемент удаляется. Этот алгоритм менее точен, чем LRU, но требует меньше ресурсов и широко применяется в ядрах операционных систем (например, в Linux).

Применение

LRU-алгоритм широко используется в различных областях компьютерных наук и информационных технологий:

• Кэширование страниц памяти в операционных системах (управление виртуальной памятью).
• Кэширование данных в базах данных (например, буферный кэш в PostgreSQL, InnoDB Buffer Pool в MySQL).
• Кэширование веб-контента в прокси-серверах и браузерах (например, кэш DNS, кэш HTTP-ответов).
• Кэширование файлов в файловых системах (например, dentry cache в Linux).
• Кэширование результатов запросов в веб-фреймворках и приложениях.
• Кэширование объектов в библиотеках и фреймворках (например, lru_cache в Python из модуля functools).

Преимущества и недостатки

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

• Простота реализации и понимания.
• Хорошая производительность при типичных паттернах доступа, особенно при наличии временной локальности (повторные обращения к недавно использованным данным).
• Гарантированное вытеснение наименее актуальных данных.

Недостатки

• Чувствительность к «сканированию» (scan resistance): если выполняется последовательный обход большого объёма данных, все элементы которого не помещаются в кэш, LRU может вытеснить все ранее кэшированные данные, заместив их одноразово используемыми элементами, что резко снижает эффективность кэширования.
• Потребление памяти: для хранения информации о порядке использования (например, указателей в двусвязном списке) требуется дополнительная память.
• Вычислительные накладные расходы: при каждом обращении необходимо обновлять структуру данных (перемещать элемент в начало списка), что может быть затратным при большом размере кэша и высокой частоте обращений.
• Не учитывает частоту обращений: элемент, к которому обращались часто, но давно, может быть вытеснен раньше, чем элемент, к которому обращались редко, но недавно.

Сравнение с другими алгоритмами

Интересные факты

• LRU-алгоритм был впервые описан в 1965 году в работе Ласло Белади (László Belády) «A Study of Replacement Algorithms for Virtual Storage Computers».
• В 1970-х годах было доказано, что LRU не является оптимальным алгоритмом вытеснения для всех паттернов доступа. Оптимальный алгоритм (Belady's algorithm) требует знания будущих обращений, что невозможно на практике.
• В современных процессорах для кэширования данных используется не LRU, а его приближённые версии (например, псевдо-LRU), поскольку реализация точного LRU в аппаратуре требует слишком много транзисторов и энергии.
• В Python декоратор @functools.lru_cache позволяет легко добавить кэширование с LRU-вытеснением к любой функции, что широко используется для оптимизации рекурсивных и вычислительно сложных функций.

Источники

• Belady, L. A. (1966). A Study of Replacement Algorithms for Virtual Storage Computers. IBM Systems Journal, 5(2), 78–101.
• Tanenbaum, A. S., & Bos, H. (2015). Modern Operating Systems (4th ed.). Pearson.
• Silberschatz, A., Galvin, P. B., & Gagne, G. (2018). Operating System Concepts (10th ed.). Wiley.
• Corbato, F. J. (1968). A Paging Experiment with the Multics System. MIT Project MAC Report.
• Документация Python: functools.lru_cache — Python 3.12.2 documentation.