LRU

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

История

Идея вытеснения на основе давности последнего обращения восходит к ранним работам по управлению памятью в 1960-х годах. В 1965 году Ласло Белади (László Belády) опубликовал статью «A Study of Replacement Algorithms for a Virtual-Storage Computer», в которой сравнил несколько политик замещения, включая LRU и оптимальный алгоритм (OPT). Белади показал, что LRU близок к оптимальному по числу кэш-промахов при типичных паттернах доступа, хотя и не достигает его. В последующие десятилетия LRU стал стандартом де-факто в операционных системах (например, в ядре Linux для управления страницами памяти) и в аппаратных кэшах процессоров. С развитием веб-технологий LRU начал применяться в прокси-серверах и CDN для кэширования HTTP-ответов.

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

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

Формально алгоритм можно описать так:

1. При запросе элемента X:

• Если X уже в кэше: переместить X в начало очереди (или обновить временную метку).
• Если X нет в кэше: если кэш заполнен, удалить элемент из конца очереди; затем добавить X в начало.

1. При вытеснении: удаляется элемент с минимальным значением времени последнего доступа.

В реализации LRU требуется структура данных, позволяющая быстро (за O(1)) выполнять операции вставки, удаления и перемещения. Обычно используется двусвязный список (Doubly Linked List) в паре с хеш-таблицей: хеш-таблица хранит указатели на узлы списка для доступа за константное время, а список поддерживает порядок по давности.

Реализации

Аппаратная реализация

В процессорных кэшах (например, L1, L2, L3) LRU реализуется на уровне транзисторов с использованием матриц доступа (access matrix) или счётчиков времени. В кэшах с небольшим числом строк (например, 4-канальный ассоциативный кэш) часто применяется псевдо-LRU (pLRU) — приближение LRU, требующее меньше аппаратных ресурсов. pLRU использует битовые деревья (tree-based PLRU), где каждый бит указывает, какая половина набора использовалась недавно.

Программная реализация

В программах LRU реализуется через:

• Двусвязный список + хеш-таблица — классический подход, обеспечивающий O(1) для всех операций.
• Связный список с временными метками — менее эффективен, но проще в реализации (O(n) для поиска).
• Битовые массивы — используются в ядрах ОС для управления страницами памяти (например, в Linux — алгоритм clock, приближающий LRU).

Пример на псевдокоде (Python-подобный): ```python class LRUCache: def __init__(self, capacity): self.capacity = capacity self.cache = {} self.order = DoublyLinkedList()

def get(self, key): if key in self.cache: node = self.cache[key] self.order.move_to_front(node) return node.value return -1

def put(self, key, value): if key in self.cache: node = self.cache[key] node.value = value self.order.move_to_front(node) else: if len(self.cache) >= self.capacity: lru_node = self.order.remove_last() del self.cache[lru_node.key] new_node = self.order.add_to_front(key, value) self.cache[key] = new_node ```

Варианты и модификации

Псевдо-LRU (pLRU)

Используется в аппаратных кэшах для экономии площади на кристалле. Вместо полного упорядочивания хранится битовое дерево, которое приблизительно указывает на наименее используемый элемент. Точность ниже, чем у полного LRU, но производительность достаточна для большинства сценариев.

LRU-K

Модификация, учитывающая K последних обращений к элементу. Элемент вытесняется на основе времени его K-го по счёту последнего доступа. LRU-2 (K=2) часто используется в системах управления базами данных (например, в буферном менеджере PostgreSQL) для защиты от «загрязнения» кэша однократными запросами.

ARC (Adaptive Replacement Cache)

Алгоритм, динамически переключающийся между LRU и LFU (Least Frequently Used) в зависимости от паттерна доступа. Разработан в IBM Almaden Research Center (2003). ARC часто превосходит LRU по hit rate на реальных трассах.

Clock (Second Chance)

Приближение LRU, используемое в ядре Linux для управления страницами памяти. Страницы организованы в циклический список с битом доступа. При вытеснении алгоритм просматривает страницы по кругу: если бит доступа установлен, он сбрасывается и страница получает «второй шанс»; если сброшен — страница вытесняется. Это снижает накладные расходы по сравнению с полным LRU.

Применение

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

Виртуальная память использует LRU (или его приближения) для вытеснения страниц из физической памяти на диск. В ядре Linux применяется алгоритм Clock (активный с версии 2.6.28), который эмулирует LRU с меньшими накладными расходами. В Windows NT используется модифицированный LRU с разделением на рабочие наборы процессов.

Процессорные кэши

В современных процессорах (Intel Core, AMD Zen) кэши L1, L2 и L3 частично используют pLRU. Например, в Intel Skylake L2-кэш использует 8-канальный ассоциативный кэш с pLRU на основе битовых деревьев.

Базы данных

Буферные менеджеры (например, в PostgreSQL, MySQL InnoDB) применяют LRU с модификациями. InnoDB использует LRU с разделением на «молодую» и «старую» части (LRU with midpoint insertion) для защиты от сканирований, которые могут вытеснить часто используемые страницы.

Веб-кэширование

Прокси-серверы (Squid, Varnish) и CDN (Cloudflare, Akamai) используют LRU для вытеснения устаревших HTTP-ответов. Однако в веб-среде LRU может быть неоптимален из-за неравномерного распределения популярности контента (закон Ципфа), поэтому часто применяются гибридные алгоритмы (например, GDSF — Greedy Dual Size Frequency).

Кэширование данных в приложениях

Библиотеки и фреймворки (например, lru_cache в Python, LRUCache в Java Guava) реализуют LRU для кэширования результатов функций, запросов к API или вычислений.

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

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

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

Недостатки

• Неэффективен при циклических сканированиях (scan resistance): если каждый элемент запрашивается ровно один раз, LRU вытесняет все предыдущие, что приводит к нулевому hit rate.
• Чувствителен к «загрязнению» кэша однократными запросами (например, при полном сканировании таблицы в БД).
• Требует дополнительной памяти для хранения порядка (в программной реализации — двусвязный список).
• В аппаратной реализации полный LRU дорог для кэшей с большой ассоциативностью (более 8-16 каналов).

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

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

• Алгоритм LRU иногда называют «алгоритмом Белади» в честь Ласло Белади, хотя сам Белади описал его как частный случай более общего семейства.
• В 1970 году Белади открыл аномалию, названную его именем: для некоторых алгоритмов (включая FIFO) увеличение размера кэша может парадоксально увеличить число кэш-промахов. LRU такой аномалии не подвержен.
• В процессорах ARM Cortex-A серии используется pLRU с битовыми деревьями для кэша L2.
• В языке Python декоратор @functools.lru_cache (до версии 3.9) реализован на основе двусвязного списка; начиная с Python 3.9, он заменён на более эффективную реализацию на основе словаря с упорядочиванием (OrderedDict).

Источники

• Belády, L. A. (1966). «A Study of Replacement Algorithms for a Virtual-Storage Computer». IBM Systems Journal.
• Tanenbaum, A. S., & Bos, H. (2015). «Modern Operating Systems» (4th ed.). Pearson.
• Hennessy, J. L., & Patterson, D. A. (2019). «Computer Architecture: A Quantitative Approach» (6th ed.). Morgan Kaufmann.
• Megiddo, N., & Modha, D. S. (2003). «ARC: A Self-Tuning, Low Overhead Replacement Cache». Proceedings of the 2nd USENIX Conference on File and Storage Technologies.
• Документация ядра Linux: «Page Replacement Policies» (Documentation/vm/).