LFU и ARC

В статье о LRU-кэше был один день веб-сервера Космического центра Кеннеди — 13 июля 1995 года, день старта «Дискавери». Здесь вся неделя, с понедельника 10-го по воскресенье 16-го: 538 838 запросов к 4258 страницам и картинкам. Сравним три правила вытеснения: LRU выселяет то, к чему дольше всех не обращались, LFU — то, к чему обращались реже всех, а ARC сам решает, чему верить больше.

Переключите на «13 июля». За один день LFU обходит LRU: на сотне мест 79,99 % попаданий против 77,37 %, а на 25 местах — 59,5 % против 48,6 %. На неделе картина обратная: LRU ловит 68,65 % запросов, LFU — 61,89 %, и отстаёт он уже со вторника. На сотне мест ARC лучше обоих и на неделе (73,13 %), и на дне (80,53 %); только на дне с 25 местами LFU чуть впереди — 59,48 % против 59,32 %. Пунктир — правило Белади, которое знает будущее: 81,87 % на неделе. Ближе всех к нему подходит ARC.

Идея

У кэша два признака того, что страница понадобится снова: её спрашивали недавно и её спрашивали часто. LRU смотрит только на первый, LFU — только на второй, и каждый проигрывает там, где важен другой. ARC держит обе группы — страницы, которые спросили один раз, и спрошенные хотя бы дважды, — и помнит номера недавно выселенных из каждой группы. Если снова спросили выселенную «свежую», группе свежих мало места; если выселенную «частую» — частым. Граница между группами сдвигается сама.

Почему частота вообще помогает? В журнале веб-сервера есть страницы, которые спрашивают всегда: логотип, главная, часы обратного отсчёта. Их стоит держать в кэше, даже если последний запрос был минуту назад, а за эту минуту прошло много разовых запросов к старым архивам. LRU отдаёт место каждому разовому запросу и выселяет ради него логотип; LFU не выселит логотип никогда. Но у «никогда» есть цена, и неделя её показывает.

LFU за O(1)

У каждой страницы в кэше счётчик — сколько раз её спросили с тех пор, как она туда попала. Выселяется страница с наименьшим счётчиком, при равных — та, к которой дольше всех не обращались. Найти наименьшее можно кучей за O(log c), но есть способ быстрее: корзины. В корзине f лежат страницы со счётчиком f, упорядоченные по последнему обращению. Попадание переносит страницу из корзины f в конец корзины f + 1, выселяется первая страница самой маленькой корзины. Номер этой корзины не нужно искать: новая страница приходит со счётчиком 1, так что после промаха наименьший счётчик — 1, а после попадания он сдвигается, только если опустела корзина-минимум, и тогда становится на единицу больше. Каждая операция — O(1); так это и описали Кетан Шах, Анирбан Митра и Дхрув Матани в 2010 году.

Теперь о цене. Посмотрите, что происходит у LFU в середине недели.

У LFU почти все места заняты страницами со счётчиками в сотни и тысячи. За одно оставшееся место толкаются все новые страницы: новичок приходит со счётчиком 1, и следующий новичок выселяет его, не дав набрать второй запрос. Листинг считает: в воскресенье вечером у LFU из ста мест только одно занято страницей со счётом меньше четырёх. Среди старожилов — картинка обратного отсчёта /shuttle/countdown/count.gif со счётом 296: в воскресенье, через три дня после старта, её не спросил никто. Это застывание: счётчики помнят прошлое, и кэш перестаёт успевать за тем, что спрашивают сейчас.

Лечат его двумя способами. Первый — старение: время от времени делить все счётчики пополам, чтобы вчерашние заслуги таяли. Так делает Redis в политике allkeys-lfu: у ключа приближённый счётчик в несколько бит, который растёт всё медленнее, и он уменьшается, если ключ давно не трогали. Второй — не давать частоте решать всё: держать для новичков отдельное окно, где они могут набрать счёт. Сколько мест отдать окну — вопрос, на который нет одного ответа для всех журналов. ARC отвечает на него сам.

ARC: две половины и призраки

ARC держит в кэше два списка LRU. В T1 — страницы, которые спросили один раз с тех пор, как они попали в кэш; в T2 — спрошенные хотя бы дважды. Второе попадание переводит страницу из T1 в T2. Вместе T1 и T2 занимают не больше c мест, а граница между ними задана целевым размером T1 — числом p.

Главное — два «призрачных» списка, B1 и B2. В них не страницы, а только номера страниц, недавно выселенных из T1 и T2. Номер стоит несколько байт, страница — килобайты, поэтому помнить ещё c номеров почти бесплатно. Призраки — это память об ошибках. Если запрос пришёл к номеру из B1, значит, кэш недавно выселил страницу, которую спросили один раз, — а её спросили снова. Будь у T1 больше мест, это было бы попадание; поэтому p растёт. Запрос к номеру из B2 — зря выселили частую страницу, и p уменьшается. Шаг тем больше, чем меньше призрачный список, в который попал запрос: редкое попадание в маленький список — сильный довод.

Место освобождают так: если в T1 больше p страниц, самая давняя из T1 уходит в B1, иначе самая давняя из T2 — в B2. Есть тонкость для запроса из B2 при |T1| = p — место тогда тоже отдаёт T1; все правила целиком — во второй задаче статьи.

На неделе журнала NASA ARC держит p около семи: из ста мест семь — для страниц, которых спросили один раз, девяносто три — для повторных. Поток, как и показал LFU, любит частоту, но совсем без мест для новичков, как у LFU, кэш застывает. ARC нашёл это равновесие сам, без настройки, и на неделе он на 4,5 процентного пункта лучше LRU и на 11 — лучше LFU. В средней сцене это видно: оранжевые клетки T1 слева у ARC меняются постоянно, синие T2 — медленнее, а у LFU вспыхивает одно последнее место.

Отсюда и устойчивость к просмотру. Когда робот-индексатор один раз проходит по всем страницам сайта, каждая из них попадает в T1 и вытесняет только T1; страницы T2, которые спрашивают постоянно, не трогаются. У LRU такой проход выметает весь кэш.

Код

LRU на упорядоченном словаре, LFU на корзинах счётчиков, ARC с четырьмя списками и правило Белади — на дне 13 июля и на всей неделе, с долями попаданий по дням. В конце листинг заглядывает в кэш LFU в воскресенье вечером и печатает среднее p у ARC по дням.

Сколько это стоит

Все три работающих правила — O(1) на запрос, и разница между ними не в скорости, а в попаданиях. Четыре с половиной процентных пункта между ARC и LRU на этой неделе — это 24 тысячи запросов, которые не дошли до диска, а одиннадцать пунктов между ARC и LFU — около 60 тысяч. ARC платит памятью на призраков и тем, что каждая операция трогает два-три списка вместо одного.

Где работает

ZFS. Кэш файловой системы ZFS так и называется — ARC; исходник ссылается на статью Мегиддо и Модхи и перечисляет отличия: блоки там разного размера, от 512 байт до 128 КБ, и выселять приходится столько блоков, сколько нужно под новый.

PostgreSQL. В версии 8.0 буферный кэш работал по ARC. На алгоритм была подана заявка на патент IBM, и в 8.0.2 его заменили похожим и чуть более простым 2Q, который был опубликован раньше. В 8.1 буферный менеджер переписали на «часы» — одну стрелку, которая обходит буферы и уменьшает их счётчики использования. Такой схеме нужно меньше блокировок, чем ARC, а на многопроцессорных машинах это оказалось важнее.

Redis. Политика allkeys-lfu появилась в версии 4.0. Чтобы не хранить честный счётчик, Redis держит в каждом ключе приближённый счётчик Морриса, который растёт с вероятностью, падающей по мере роста, и уменьшает его со временем.

Caffeine. Кэш для Java построен на W-TinyLFU Гила Эйнцигера, Роя Фридмана и Бена Мейнса: маленькое окно LRU для новичков, а решение, впустить ли новичка на место кандидата на выселение, принимает приближённый счётчик частоты на основе Count-Min Sketch. Это то же лечение застывания, что и у ARC: у новичков есть своё место, а частота решает только, кому остаться надолго.

История

Мысль учитывать не только последнее обращение появилась в базах данных. В 1993 году Элизабет О'Нил, Патрик О'Нил и Герхард Вейкум предложили LRU-K — выселять страницу, у которой K-е с конца обращение было давнее всех. В 1994 году Теодор Джонсон и Деннис Шаша описали 2Q: новые страницы сначала живут в короткой очереди и переходят в основную, только если их спросят снова. Обоим правилам нужны параметры, подобранные под нагрузку. Нимрод Мегиддо и Дхармендра Модха в 2003 году на конференции FAST показали ARC, который подбирает свой параметр сам и работает за O(1). По их замерам он почти не уступает тому же правилу с лучшим постоянным p, подобранным задним числом под журнал, и заметно обходит LRU.

Задачи

Первая задача — LFU за O(1) и его очередь на выселение на настоящем журнале. Вторая — ARC по всем правилам, включая тонкие места, на которых легко ошибиться.