Формат ARC

ARC (от англ. _Adaptable Replacement Cache_ — адаптируемый замещающий кэш) — это алгоритм кэширования, предназначенный для управления памятью в операционных системах, базах данных и файловых системах. Разработан в 2003 году исследователями Нимродом Мегиддо и Дхармой Моди из IBM Almaden Research Center. ARC обеспечивает динамическое балансирование между частотой и давностью обращений к данным, что позволяет достигать высокой эффективности при различных рабочих нагрузках без необходимости ручной настройки параметров.

История и предпосылки создания

До появления ARC в системах кэширования доминировали алгоритмы LRU (Least Recently Used) и LFU (Least Frequently Used). LRU вытесняет данные, к которым дольше всего не было обращений, что хорошо работает при равномерных запросах, но плохо справляется со скачкообразными нагрузками. LFU, напротив, учитывает частоту обращений, но требует значительных вычислительных ресурсов для подсчёта и подвержен «загрязнению» кэша устаревшими, но ранее популярными данными.

В начале 2000-х годов рост объёмов оперативной памяти и усложнение рабочих нагрузок (веб-серверы, базы данных, научные вычисления) выявили потребность в алгоритме, который мог бы адаптироваться к меняющимся паттернам доступа без вмешательства администратора. ARC стал ответом на эту потребность, предложив комбинированный подход, автоматически переключающийся между стратегиями LRU и LFU.

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

ARC использует четыре списка (или очереди) для отслеживания страниц памяти: два для недавно использованных данных (LRU-часть) и два для часто используемых (LFU-часть). Ключевая особенность — динамическая настройка размера этих частей в зависимости от характера запросов.

Структура очередей

1. T1 — очередь для недавно использованных страниц (LRU-подобная). Содержит данные, к которым обращались один или несколько раз за короткий промежуток времени.
2. T2 — очередь для часто используемых страниц (LFU-подобная). Содержит данные, к которым обращались многократно, что указывает на их высокую популярность.
3. B1 — очередь «призраков» (ghost entries) для страниц, недавно вытесненных из T1. Хранит только метаданные (например, идентификатор страницы), но не сами данные.
4. B2 — очередь «призраков» для страниц, недавно вытесненных из T2.

Размеры T1 и T2 динамически регулируются параметром p (target size for T1), который изменяется в диапазоне от 0 до общего размера кэша (c). Изначально p = c/2, то есть обе части равны.

Алгоритм замещения

При обращении к странице:

• Если страница находится в T1 или T2 (попадание в кэш), она перемещается в «голову» T2 (как в LFU).
• Если страница не в кэше (промах), она загружается. При этом проверяется, есть ли её идентификатор в B1 или B2:
• Если в B1 — это означает, что страницу ранее вытеснили из T1, и алгоритм увеличивает p (сдвиг в сторону LRU-стратегии).
• Если в B2 — уменьшает p (сдвиг в сторону LFU-стратегии).
• Если ни в B1, ни в B2 — p остаётся без изменений.

После загрузки новая страница помещается в «голову» T1. Если кэш переполнен, алгоритм вытесняет страницу из «хвоста» T1 или T2 в зависимости от текущего значения p. Вытесненная страница перемещается в соответствующую очередь «призраков» (B1 или B2), а её данные удаляются из памяти.

Адаптация

Механизм «призраков» позволяет ARC «помнить» о недавно вытесненных страницах без хранения их содержимого. Если к странице из B1 снова обращаются, это сигнал, что алгоритм слишком агрессивно вытеснял недавние данные, и долю T1 следует увеличить. Аналогично для B2. Таким образом, ARC автоматически подстраивается под текущую рабочую нагрузку: при преобладании краткосрочных запросов (например, последовательное чтение) растёт T1, при долгосрочных (например, часто используемые индексы базы данных) — T2.

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

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

• Автоматическая адаптация. Не требует ручной настройки параметров, что упрощает эксплуатацию.
• Устойчивость к изменениям нагрузки. Эффективно работает как при скачкообразных запросах (например, временные пики трафика), так и при стабильных паттернах доступа.
• Низкие накладные расходы. Алгоритм использует только операции сравнения и сдвига указателей, без сложных вычислений частоты.
• Высокая эффективность. По данным авторов, ARC в среднем на 10–30% превосходит LRU и LFU по коэффициенту попаданий (hit ratio) при типичных нагрузках.

Недостатки

• Повышенное потребление памяти. Хранение очередей «призраков» (B1 и B2) требует дополнительной памяти для метаданных. В системах с ограниченной памятью это может быть критично.
• Сложность реализации. По сравнению с LRU, ARC требует более сложной логики управления очередями и динамической настройки.
• Чувствительность к размеру кэша. При очень малых размерах кэша (менее 100 страниц) эффективность ARC может снижаться из-за недостаточности статистики для адаптации.

Применение

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

• Операционные системы. Реализован в ядре FreeBSD (с версии 7.0) для управления кэшем файловой системы ZFS. В Linux используется модифицированная версия ARC в подсистеме управления памятью.
• Базы данных. Применяется в СУБД PostgreSQL (в модуле кэширования), а также в некоторых NoSQL-решениях (например, Redis — частично).
• Файловые системы. ZFS активно использует ARC для кэширования блоков данных и метаданных. Это одна из ключевых причин высокой производительности ZFS при смешанных нагрузках.
• Веб-серверы. Алгоритм может быть адаптирован для кэширования HTTP-запросов, например, в прокси-серверах (Squid, Varnish) или CDN.

Модификации и альтернативы

На основе ARC были разработаны улучшенные версии:

• LARC (Lazy ARC) — модификация, снижающая накладные расходы за счёт отложенной обработки «призраков».
• CAR (Clock with Adaptive Replacement) — гибрид ARC и алгоритма Clock, более эффективный для многопроцессорных систем.
• 2Q (Two Queue) — упрощённая версия ARC, предложенная ранее (1994), использующая две очереди (A1in, A1out, Am) вместо четырёх.

Среди альтернативных алгоритмов можно выделить LFU-DA (LFU with Dynamic Aging) и LRU-K, которые также пытаются комбинировать частоту и давность, но без динамической адаптации размера очередей.

Критика и ограничения

Несмотря на успешное применение, ARC не лишён критики:

• Проблема «загрязнения» кэша. При внезапном появлении большого количества уникальных запросов (например, сканирование всей базы данных) ARC может временно вытеснить часто используемые данные, снижая производительность.
• Сложность отладки. Из-за динамической природы алгоритма трудно предсказать его поведение в конкретной системе без моделирования.
• Патентные ограничения. Изначально ARC был запатентован IBM (патент US 20040215886A1), что ограничивало его использование в коммерческом ПО. Однако срок действия патента истёк, и сейчас алгоритм доступен для свободного применения.

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

• ARC стал основой для алгоритма кэширования в ZFS, который считается одной из самых производительных файловых систем для хранения больших объёмов данных.
• Название «Adaptable Replacement Cache» было выбрано авторами, чтобы подчеркнуть отличие от «Adaptive Replacement Cache» — термина, который ранее использовался в других контекстах.
• В 2004 году ARC получил награду IBM Research Division Award за вклад в развитие систем хранения данных.

Источники

• 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.
• Smith A. J. Cache Memories // ACM Computing Surveys. — 1982. — Vol. 14, No. 3.
• Документация по ZFS: ARC (Adaptive Replacement Cache) — OpenZFS Project.
• Патент US 20040215886A1: Adaptive Replacement Cache. — IBM Corporation, 2003.