Алгоритм LRU

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

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

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

Основные операции:

• Поиск (access): при обращении к элементу его временная метка обновляется на текущее время. Если элемент отсутствует в кэше, происходит кэш-промах и страница загружается из основного хранилища (например, из оперативной памяти в случае кэша процессора или с диска в случае кэша файловой системы).
• Замещение (eviction): когда кэш заполнен и требуется освободить место для нового элемента, выполняется поиск элемента с наименьшим значением временной метки. Этот элемент удаляется, а на его место помещается новый.

LRU является детерминированным: порядок вытеснения строго определён историей обращений. В идеальной реализации для каждого элемента должно храниться либо временное значение (счётчик или глобальный тик), либо порядок в списке.

Разновидности и реализации

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

Аппаратные и программные реализации

• На основе счётчика (counter-based): каждому элементу присваивается глобальный счётчик обращений (или значение времени), который увеличивается с каждым доступом. При вытеснении выбирается элемент с наименьшим счётчиком. Недостаток: счётчик может переполниться. Требует O(n) времени для поиска минимума при каждом вытеснении.
• Связанный список (linked list): элементы хранятся в двусвязном списке. При обращении элемент перемещается в конец или начало списка (в зависимости от реализации). Для вытеснения удаляется элемент из противоположного конца. Вставка и удаление в двусвязном списке выполняются за O(1), но требуется поиск элемента при обращении, что при хэш-таблице даёт амортизированное O(1). Эта реализация называется «LRU с помощью связного списка и хэш-таблицы».
• Стек или массив со сдвигом: более простая аппаратная реализация, при которой элементы сдвигаются при каждом обращении, что может быть дорого для больших кэшей.

Псевдо-LRU (PLRU)

Из-за сложности точного LRU в аппаратуре (особенно в кэшах процессоров) часто применяются приближённые варианты — pseudo-LRU (PLRU). Он хранит не полную историю доступа, а лишь некоторую информацию о том, какой набор элементов использовался недавно. Распространённый вариант — дерево битов доступа (tree-based PLRU), где каждый узел бинарного дерева хранит бит, указывающий, с какой ветви был последним доступ. При вытеснении обход начинается по указаниям битов, что позволяет выбрать кандидата за O(log n) операций. PLRU обеспечивает поведение, близкое к LRU, но с меньшими аппаратными затратами.

Применение

Операционные системы

В подсистеме управления памятью (MMU) операционных систем LRU используется для замещения страниц виртуальной памяти при нехватке физической памяти (подкачка). Например, ядро Linux использует алгоритм, напоминающий LRU, но с двухуровневой структурой страничных списков (активный и неактивный списки), который реализует приближение LRU. Реализация точного LRU для страниц памяти была бы слишком затратной, так как требуется обрабатывать каждую страницу при каждом доступе (что нарушило бы производительность).

Кэш-память процессоров

Алгоритмы замещения в кэш-памяти (L1, L2, L3) обычно реализуют PLRU или более простые политики (случайное, FIFO) из-за требований по скорости и площади на кристалле. Однако в некоторых современных процессорах (например, Intel Core) используются варианты LRU или PLRU с древовидным битом для каждого набора (set). В процессорах архитектуры x86-64 часто применяется алгоритм «NRU» (Not Recently Used) — упрощённая версия, где каждый элемент имеет флаг «использован», сбрасываемый периодически.

Базы данных

В СУБД (например, PostgreSQL, MySQL) буферный кэш страниц (буферный пул) часто использует политику LRU или его модификации. Это необходимо, чтобы уменьшить количество операций ввода-вывода с диском, сохраняя в памяти наиболее часто используемые страницы. В PostgreSQL используется алгоритм «часы» (clock sweep) — вариант LRU, реализованный с помощью кольцевого буфера и флага «использован» (аналог «дополнительный бит»). Позволяет избежать перемещения элементов в списке при каждом доступе, что снижает накладные расходы.

Веб-браузеры

Браузеры (Google Chrome, Mozilla Firefox, Safari) используют LRU для управления кэшем веб-страниц и изображений. Когда достигнут лимит кэша (например, 1 ГБ на диске), удаляются самые старые по последнему использованию файлы. Однако браузеры также применяют смешанные стратегии: например, приоритизация ресурсов с учётом размера файла и времени загрузки.

Системы управления содержимым (CMS)

Кэширование результатов запросов к базе данных часто реализуется через LRU, чтобы наиболее популярные страницы загружались быстрее. Пример: кэш WordPress (Object Cache) использует LRU для хранения объектов данных.

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

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

• Локальность доступа: LRU хорошо работает, если рабочее множество (working set) программы умещается в кэше: оно вытесняет давно не используемые страницы, сохраняя активные.
• Относительная простота реализации: при программном воплощении с хэш-таблицей и двусвязным списком поддерживается O(1) время на запрос.
• Детерминированность: в отличие от случайного вытеснения, поведение предсказуемо и воспроизводимо.

Недостатки

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

Альтернативы и усовершенствования

• LFU (Least Frequently Used — наименее часто используемый): вытесняет элементы с наименьшей частотой использования. Может быть эффективнее для паттернов доступа с повторяющимися запросами, но страдает от «загрязнения» популярными, но устаревшими элементами.
• ARC (Adaptive Replacement Cache): комбинирует LRU и LFU, адаптируясь к паттерну доступа. Используется в файловых системах ZFS и некоторых СУБД.
• 2Q (Two Queue): два списка — «частый» (FIFO) и «обычный» (LRU). Делает допуск в кэш после наблюдения повторного доступа, защищая от «сдвига» при однократных обращениях.
• Clock (часы): приближение LRU с помощью кольцевого буфера, где каждый элемент имеет бит «использован». При сканировании указателя сбрасываются биты и вытесняется первый с нулевым битом. Используется в Linux для страничного кэша.
• MRU (Most Recently Used): вытесняет самый недавно использованный элемент — используется в случаях, когда последний доступ редко повторяется (например, в некоторых СУБД).

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

• Алгоритм LRU был впервые описан в 1960-х годах в контексте управления виртуальной памятью в операционной системе Multics.
• В современных веб-браузерах кэш LRU может быть реализован как комбинация дискового и оперативного кэша, где в оперативной памяти хранится более быстрая версия LRU.
• Существуют реализации LRU с использованием СУБД в оперативной памяти — например, Redis имеет встроенную политику вытеснения allkeys-lru, которая удаляет ключи по принципу LRU при достижении лимита памяти.

Источники

• Tanenbaum A. S., Bos H. «Современные операционные системы» (4-е изд.).
• Denning P. J. «The working set model for program behavior».
• Silberschatz A., Galvin P. B., Gagne G. «Operating System Concepts» (10-е изд.).
• Документация ядра Linux — описание управления памятью и алгоритмов замещения страниц.
• Hennessy J. L., Patterson D. A. «Computer Architecture: A Quantitative Approach» (6-е изд.).
• Документация PostgreSQL — «The Buffer Manager».
• Документация Redis — «Политики вытеснения».