Алгоритм ARC

Алгоритм ARC (Adaptive Replacement Cache, адаптивное замещение кэша) — это алгоритм управления кэшем, разработанный для повышения эффективности кэширования данных в системах хранения и базах данных. Он относится к классу алгоритмов вытеснения (eviction policies), которые определяют, какие данные следует удалить из кэша при нехватке места для новых записей. ARC сочетает в себе элементы алгоритмов LRU (Least Recently Used, наименее недавно использованный) и LFU (Least Frequently Used, наименее часто используемый), адаптивно подстраиваясь под изменяющиеся паттерны доступа к данным.

История

Алгоритм ARC был предложен в 2003 году исследователями Нимродом Мегиддо (Nimrod Megiddo) и Дхармендрой Моди (Dharmendra S. Modha) из исследовательского центра IBM Almaden. Первоначально он был разработан для систем кэширования в операционных системах и системах управления базами данных, где требуется высокая производительность при ограниченном объёме кэша. Публикация статьи «ARC: A Self-Tuning, Low Overhead Replacement Cache» в журнале ACM Transactions on Storage (2003) представила алгоритм как альтернативу классическому LRU, который плохо справляется с циклическими и сканирующими паттернами доступа.

В последующие годы ARC был реализован в ряде коммерческих продуктов, включая системы хранения данных IBM (например, IBM DS8000), а также в операционной системе FreeBSD (начиная с версии 7.0, 2008 год) и в некоторых версиях Linux (через модуль ZFS). Алгоритм также лёг в основу более поздних разработок, таких как CAR (Clock with Adaptive Replacement) и LIRS (Low Inter-reference Recency Set).

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

ARC использует четыре списка (или очереди) для отслеживания страниц кэша, разделяя их на два типа: недавно использованные (Recent) и часто используемые (Frequent). Каждый тип дополнительно делится на «живые» страницы (текущие в кэше) и «призрачные» страницы (вытесненные записи, но с сохранением метаданных). Это позволяет алгоритму «помнить» о недавно вытесненных данных и адаптироваться к изменениям рабочей нагрузки.

Основные компоненты

• LRU-список Recent (R): содержит страницы, которые были использованы недавно, но не обязательно часто. Размер этого списка динамически регулируется.
• LFU-список Frequent (F): содержит страницы, которые используются часто, даже если они не были запрошены недавно.
• Призрачные списки Ghost Recent (GR) и Ghost Frequent (GF): хранят метаданные (например, ключи) вытесненных страниц из соответствующих списков. Они не занимают место в кэше, но позволяют алгоритму определять, какие данные были вытеснены и как часто к ним обращаются.

Процесс вытеснения

Когда в кэш поступает новый запрос на страницу, алгоритм выполняет следующие шаги:

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

• Если страница есть в Ghost Recent, это указывает на то, что данные были недавно вытеснены, но к ним снова обратились. Алгоритм увеличивает размер списка Recent, добавляя страницу в кэш.
• Если страница есть в Ghost Frequent, это указывает на часто используемые данные, которые были вытеснены. Алгоритм увеличивает размер списка Frequent.
• Если страницы нет ни в одном призрачном списке, она добавляется в конец списка Recent.

1. Вытеснение (eviction): если кэш заполнен, алгоритм удаляет страницу из конца одного из списков (Recent или Frequent) в зависимости от текущего соотношения их размеров. Вытесненная страница перемещается в соответствующий призрачный список, а её данные освобождаются.

Адаптация

Ключевая особенность ARC — динамическая настройка пропорции между списками Recent и Frequent. Алгоритм использует параметр p (от 0 до 1), который определяет долю кэша, выделенную для списка Recent. Значение p корректируется на основе частоты попаданий в призрачные списки: если чаще происходят попадания в Ghost Recent, p увеличивается (больше места для недавних данных); если в Ghost Frequent — p уменьшается (больше места для частых данных). Это позволяет ARC адаптироваться к меняющимся паттернам доступа без ручной настройки.

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

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

• Адаптивность: ARC автоматически подстраивается под различные рабочие нагрузки, включая циклические, сканирующие и смешанные паттерны, без необходимости в предварительной настройке.
• Высокая эффективность: по сравнению с LRU, ARC снижает количество промахов кэша (cache miss rate) на 10–30% в типичных сценариях, особенно при наличии повторяющихся обращений к данным.
• Низкие накладные расходы: алгоритм требует лишь небольшого объёма дополнительной памяти для призрачных списков (обычно 1–2% от размера кэша) и выполняется за O(1) время на операцию.
• Устойчивость к сканированиям: в отличие от LRU, ARC не вытесняет все полезные данные при однократном последовательном сканировании, так как часто используемые данные защищены списком Frequent.

Недостатки

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

Применение

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

• Системы хранения данных: в контроллерах RAID и массивах хранения (например, IBM DS8000, NetApp) для кэширования блоков данных.
• Файловые системы: в ZFS (OpenZFS) для кэширования метаданных и данных (ARC является основным кэшем в ZFS, хотя в современных версиях используется модифицированная версия).
• Операционные системы: в FreeBSD и некоторых версиях Linux для кэширования страниц виртуальной памяти и файловых систем.
• Базы данных: в системах управления базами данных (например, PostgreSQL через расширение pg_buffercache) для кэширования страниц таблиц и индексов.
• Веб-кэширование: в прокси-серверах и CDN для кэширования контента, хотя здесь чаще используются специализированные алгоритмы (например, GDSF).

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

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

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

• Алгоритм ARC был запатентован IBM (патент US 6,996,676 B2, 2006 год), что ограничило его использование в некоторых открытых проектах. Однако реализация в FreeBSD и ZFS была выполнена на основе лицензионного соглашения.
• В 2008 году алгоритм ARC был включён в ядро FreeBSD 7.0 как альтернатива стандартному LRU для кэша буферов, что значительно повысило производительность файловых операций.
• Существует модификация алгоритма — ARC с адаптивной частотой (ARC-F), которая добавляет учёт частоты обращений для улучшения работы с очень длинными циклами.
• ARC лёг в основу алгоритма CAR (Clock with Adaptive Replacement), который использует структуру часов для уменьшения накладных расходов на обслуживание списков.

Источники

1. Megiddo, N., & Modha, D. S. (2003). ARC: A Self-Tuning, Low Overhead Replacement Cache. ACM Transactions on Storage, 2(1), 1-30.
2. Modha, D. S., & Megiddo, N. (2004). Outperforming LRU with an adaptive replacement cache algorithm. IEEE Computer, 37(4), 58-65.
3. FreeBSD Documentation Project. (2008). FreeBSD 7.0 Release Notes. FreeBSD Foundation.
4. OpenZFS Documentation. (2020). ARC — Adaptive Replacement Cache. OpenZFS Project.
5. Патент США № 6,996,676 B2. (2006). Adaptive replacement cache algorithm. IBM Corporation.