LFU

LFU (Least Frequently Used, «наименее часто используемый») — это алгоритм кэширования, который вытесняет из кэша элемент, имеющий наименьшую частоту обращений за определённый период. LFU относится к классу политик замещения страниц и блоков данных, используемых в операционных системах, базах данных, веб-серверах, процессорах и других системах, где ограниченный объём памяти требует эффективного управления хранимыми данными. Основная цель LFU — минимизировать количество промахов кэша (cache misses) путём сохранения наиболее востребованных данных, при этом жертвуя редко запрашиваемыми.

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

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

Пример

Допустим, кэш вмещает 3 элемента. Последовательность обращений: A, B, C, A, B, D.

• После обращений к A, B, C — все три в кэше, счётчики: A=1, B=1, C=1.
• При обращении к A счётчик A становится 2.
• При обращении к B счётчик B становится 2.
• При запросе D кэш полон. Счётчики: A=2, B=2, C=1. Вытесняется C (наименьшая частота). D добавляется со счётчиком 1.

История

Идея учёта частоты обращений для управления памятью восходит к ранним работам по операционным системам и виртуальной памяти в 1960-х годах. Алгоритм LFU в явном виде был описан в 1970-х годах в контексте замещения страниц в ОС Multics. В 1980-х годах LFU начал применяться в базах данных для кэширования блоков данных. С развитием веб-технологий в 1990-х годах LFU стал использоваться в прокси-серверах и кэшах браузеров, однако его практическая реализация столкнулась с проблемами производительности и точности. В 2000-х годах были предложены модификации, такие как LFU с экспоненциальным затуханием (LFU with decay) и адаптивный LFU (Adaptive LFU), которые улучшили поведение алгоритма в реальных сценариях.

Классификация

LFU относится к семейству политик замещения, основанных на частоте (frequency-based policies). Внутри этого семейства выделяют:

• Чистый LFU (Pure LFU) — счётчики не сбрасываются и не уменьшаются со временем. Недостаток: «застарелые» данные с высокими счётчиками могут оставаться в кэше, даже если перестали быть востребованными.
• LFU с затуханием (LFU with decay) — счётчики периодически уменьшаются (например, делением на 2) или сбрасываются для старых записей, чтобы алгоритм реагировал на изменения паттернов доступа.
• LFU с окном (Windowed LFU) — учитываются обращения только за последние N запросов или за определённый временной интервал.
• Адаптивный LFU (Adaptive LFU) — динамически меняет параметры (например, размер окна или коэффициент затухания) в зависимости от наблюдаемой нагрузки.
• LFU с приоритетом по давности (LFU with LRU tie-breaker) — при равной частоте используется правило Least Recently Used (LRU) — вытесняется элемент, к которому дольше всего не обращались.

Устройство и реализация

Структуры данных

Прямая реализация LFU требует хранения счётчика для каждого элемента кэша. Для эффективного поиска элемента с минимальной частотой используются:

• Двусвязный список с хеш-таблицей — каждый элемент хранится в узле списка, упорядоченного по частоте. Хеш-таблица позволяет быстро находить элемент по ключу. При увеличении частоты элемент перемещается в нужную позицию. Сложность операций: O(1) в среднем для поиска и вставки, O(n) в худшем случае для перемещения.
• Минимальная куча (min-heap) — элементы хранятся в куче, где ключом является частота. Поиск минимума — O(1), вставка и удаление — O(log n). Недостаток: при каждом обращении требуется обновление кучи, что может быть затратно.
• Список частотных блоков (frequency list) — каждый блок содержит все элементы с одинаковой частотой. Блоки упорядочены по возрастанию частоты. При обращении элемент перемещается из одного блока в другой. Эта структура обеспечивает O(1) для всех операций при условии, что количество частотных блоков невелико.

Проблемы реализации

• Переполнение счётчиков — при большом количестве обращений счётчики могут достичь максимального значения и переполниться. Решение: использование счётчиков с плавающей точкой или периодический сброс.
• Затраты памяти — хранение счётчика для каждого элемента увеличивает накладные расходы, особенно при большом размере кэша.
• Нечувствительность к временным паттернам — чистый LFU не учитывает, что данные, популярные в прошлом, могут больше не запрашиваться. Это приводит к эффекту «загрязнения кэша» (cache pollution).

Применение

LFU используется в различных областях, где требуется кэширование с учётом частоты доступа:

• Операционные системы — замещение страниц виртуальной памяти (например, в некоторых версиях ОС Multics, а также в экспериментальных ядрах).
• Базы данных — кэширование блоков данных (буферный пул) в СУБД (например, в PostgreSQL поддерживается политика LFU как опция для буферного кэша).
• Веб-серверы и прокси-серверы — кэширование HTTP-ответов, изображений, скриптов. Например, в Squid (прокси-сервер) используется алгоритм LFU с некоторыми модификациями.
• Процессоры — кэширование инструкций и данных в процессорах архитектуры x86 и ARM (часто в комбинации с LRU).
• Системы управления контентом (CDN) — кэширование на граничных узлах, где частота обращений к контенту может сильно варьироваться.
• Рекомендательные системы — кэширование результатов вычислений для часто запрашиваемых пользователей или товаров.

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

В целом, LFU превосходит LRU в сценариях, где популярность данных стабильна и не меняется быстро, но уступает в условиях резких изменений паттернов доступа.

Критика

Основная критика LFU связана с его неспособностью адаптироваться к изменениям востребованности данных. В реальных системах, таких как веб-кэши, популярность контента может резко падать (например, после окончания акции или выхода новой версии страницы). Чистый LFU будет долго удерживать устаревшие данные, что снижает эффективность кэша. Кроме того, реализация LFU требует дополнительных затрат памяти и процессорного времени на поддержание счётчиков, что может быть критично для систем с жёсткими ограничениями по ресурсам.

Для преодоления этих недостатков были разработаны гибридные алгоритмы, такие как ARC (Adaptive Replacement Cache) и LIRS (Low Inter-reference Recency Set), которые комбинируют элементы LFU и LRU. Также в современных системах часто используется LFU с затуханием или оконный LFU, которые частично решают проблему «загрязнения» кэша.

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

• Алгоритм LFU часто применяется в кэшах процессоров в паре с LRU: например, в кэше данных L2 некоторых процессоров Intel используется политика, близкая к LFU, для долгоживущих данных.
• В системах управления базами данных, таких как Oracle, используется алгоритм, похожий на LFU, под названием «LRU with touch count» — счётчики обращений обновляются при каждом доступе, а вытеснение происходит по наименьшему значению.
• В 2010-х годах компания Google предложила модификацию LFU для кэширования в распределённых системах, где частота обращений усредняется по множеству узлов.

Источники

• Таненбаум Э., Бос Х. «Современные операционные системы». — 4-е изд. — СПб.: Питер, 2015. — 1120 с.
• Сильбершац А., Корф Г., Сударшан С. «Системы баз данных: полный курс». — М.: Вильямс, 2003. — 1088 с.
• O'Neil E. J., O'Neil P. E., Weikum G. «The LRU-K page replacement algorithm for database disk buffering» // Proceedings of the 1993 ACM SIGMOD International Conference on Management of Data. — 1993. — P. 297–306.
• Megiddo N., Modha D. S. «ARC: A Self-Tuning, Low Overhead Replacement Cache» // Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST '03). — 2003. — P. 115–130.
• Jiang S., Zhang X. «LIRS: An Efficient Low Inter-reference Recency Set Replacement Policy to Improve Buffer Cache Performance» // Proceedings of the 2002 ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. — 2002. — P. 31–42.