LRU-кэш

13 июля 1995 года в 9:41 утра по местному времени из Космического центра Кеннеди стартовал шаттл «Дискавери». Веб-сервер центра в этот день принял больше запросов, чем в любой другой день сохранившегося журнала за июль: 134 тысячи, вдвое больше, чем в обычный день. В журнале за этот день 128 932 успешных запроса к 2230 разным страницам и картинкам: часы обратного отсчёта, страница старта, логотип NASA. Если держать в памяти сотню последних нужных файлов и выбрасывать тот, к которому дольше всех не обращались, — сколько запросов обойдутся без чтения с диска?

Кэш на сотню страниц — меньше двадцатой части всего, что спрашивали в тот день, — ловит 77,37 % запросов. Правило FIFO, которое выбрасывает того, кто раньше всех пришёл, на той же сотне ловит 71,20 %, а правило Белади, которое знает будущее и выбрасывает страницу, нужную позже всех, — 86,96 %. Выше пунктира не поднимется никто: 2230 первых запросов к каждой странице — промахи при любом размере, и потолок — 98,27 %. Переключите на «Войну и мир»: слова романа как поток обращений повторяются реже, и кривая поднимается медленнее.

Идея

Кэш хранит до k элементов и на каждое обращение отвечает «есть» или «нет». Когда места нет, а пришёл новый, выселяется тот, к которому дольше всех не обращались. Чтобы это стоило O(1), нужны две структуры сразу: словарь «ключ → узел» находит элемент за один шаг, а двусвязный список держит элементы в порядке последнего обращения — свежий в начале, давний в конце. Попадание вынимает узел из середины списка и ставит в начало; промах при полном кэше снимает узел с конца. И то и другое — несколько указателей.

Это правило называют LRU, least recently used. Почему именно оно — подсказывает журнал: если к странице только что обращались, скорее всего, к ней обратятся снова. Скрипт часов обратного отсчёта в тот день запросили 6199 раз, маленький логотип NASA — 12 066 раз: он стоял почти на каждой странице. О том, откуда берётся эта близость во времени и как её используют процессорные кэши, рассказывает глава курса о кэшах, а о вытеснении страниц памяти — глава о виртуальной памяти. Здесь — как LRU устроить, насколько он хорош и где ломается.

Словарь и список

Одного словаря мало: он найдёт страницу, но не скажет, какая из них самая давняя, — пришлось бы хранить время обращения и при каждом выселении искать минимум, O(k). Одного списка тоже мало: он знает порядок, но чтобы найти в нём страницу, его нужно пройти, опять O(k). Вместе они закрывают слабости друг друга: словарь хранит не саму страницу, а ссылку на её узел в списке. Ниже — тридцать запросов подряд из середины того дня.

Список двусвязный не случайно: чтобы вынуть узел из середины, нужно сомкнуть его соседей, а для этого узел должен знать обоих. В односвязном списке пришлось бы искать предыдущий узел проходом. Удобно завести узел-сторож, который замыкает список в кольцо: тогда «первый» — это сосед сторожа справа, «последний» — слева, и у вставки и удаления нет особых случаев для пустого списка и для краёв.

На этих четырёх местах из тридцати запросов попаданий 17. Поменяйте ёмкость: с тремя местами часы обратного отсчёта, cdt_clock.pl и cdt_main.pl, вытесняют друг друга чаще. В Python готовый кэш — декоратор functools.lru_cache. В CPython он написан на C, а в запасной версии на Python, которая лежит рядом, хорошо видно устройство: словарь и кольцевой двусвязный список со сторожем. Его родственник collections.OrderedDict умеет move_to_end и popitem(last=False) — это и есть два действия LRU. В Go в стандартной библиотеке кэша нет, но есть container/list, и кэш собирается из него и обычной карты.

Насколько он хуже идеала

Правило Белади — выселять страницу, которая понадобится позже всех, — лучшее из возможных, но для него нужно знать будущее. На записанном журнале будущее известно, и правило Белади служит линейкой: на сотне страниц LRU промахивается в 22,63 % запросов, Белади — в 13,04 %. Это не случайный разрыв, а гарантия.

При h = k отношение — k: гарантия слабая, и на специально подобранных запросах — например, круговом обходе страниц чуть больше кэша — LRU и правда промахивается каждый раз. Но если дать LRU вдвое больше места, чем линейке, отношение не превышает двух. На журнале NASA LRU с двумястами страницами промахнулся 19 249 раз, а Белади со ста — 16 813: в 1,14 раза чаще при гарантии 1,98. Слитор и Тарьян показали, что то же верно и для FIFO, и это объясняет, почему все разумные правила вытеснения на практике близки: теорема меряет худший случай, а настоящие журналы до него не доходят.

Все размеры за один проход

Кривая LRU в первой сцене посчитана для всех 2230 размеров сразу, а не 2230 симуляциями. Это возможно благодаря свойству, которое доказано в главе курса о виртуальной памяти: содержимое LRU-кэша на k мест всегда входит в содержимое кэша на k + 1 место. Значит, можно хранить один «стек» всех страниц в порядке последнего обращения, и кэш на k мест — это всегда его верхние k страниц.

Номер страницы в этом стеке перед обращением к ней — её стековое расстояние: сколько разных страниц спросили с прошлого раза. Кэш на k мест попадает ровно тогда, когда расстояние меньше k. Один проход по журналу собирает гистограмму расстояний, а её накопленные суммы — это доля попаданий для каждого размера. Метод описали Р. Маттсон, Я. Гечей, Д. Слуц и И. Трейгер из IBM в 1970 году: по одной записи обращений программы за один проход они получали поведение памяти любого размера.

На журнале NASA половина всех попаданий приходится на расстояния меньше 26 — поэтому кривая так круто взлетает слева. Простой проход по стеку стоит в среднем 101,8 шага на повторное обращение. Если страниц миллионы, стек проходят иначе: расстояние — это число страниц, последнее обращение к которым случилось между двумя обращениями к нашей, и его считает дерево Фенвика по моментам времени за O(log n). Так посчитана кривая в сцене; так же нужно решить вторую задачу статьи.

Код

Кэш LRU на словаре и кольцевом списке со сторожем в Python и на карте и container/list в Go — и рядом FIFO и правило Белади на том же дне журнала. Правило Белади написано на куче моментов следующего обращения с ленивым удалением устаревших записей.

Второй листинг — метод Маттсона: стек в порядке обращений, гистограмма расстояний, доля попаданий для всех размеров и проверка прямой симуляцией.

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

Память — словарь и k узлов, у каждого два указателя. «В среднем» — от словаря: хеш-таблица отвечает за O(1) в среднем. Замер — кэш на k мест на случайных запросах к 2k ключам, примерно половина попаданий. Две серии: LRU на одном списке в порядке обращений — найти ключ, вынуть, дописать в конец — и словарь со списком.

На десяти местах один список держится: на Go срез из десяти чисел впятеро быстрее карты со списком, на Python медленнее лишь вдвое. Дальше линейная работа берёт своё: на ста тысячах мест список медленнее в 1300 раз на Python и в 200 раз на Go. Для кэша на десяток записей хватит чего угодно; кэш на сотни тысяч записей без словаря невозможен.

Где LRU ошибается

Круг чуть больше кэша. Программа, которая ходит по кругу по k + 1 страницам, промахивается у LRU каждый раз: нужная страница всегда та, которую только что выселили. Это слабое место видно в виджете главы о кэшах, и именно его эксплуатирует худший случай теоремы.

Однократный просмотр. Большой последовательный проход — резервное копирование, обход сайта поисковым роботом, полное чтение таблицы — заполняет кэш страницами, которые больше не понадобятся, и выталкивает всё полезное. После прохода кэш наполняется заново. PostgreSQL от этого защищается так: большой последовательный просмотр получает маленькое кольцо буферов — для чтения таблицы 256 КБ — и крутится в нём, не трогая остальной кэш.

Частота против свежести. LRU помнит только последнее обращение: страница, которую спрашивали тысячу раз в день, проигрывает той, которую спросили один раз минуту назад. Правила, которые учитывают и частоту — LFU, 2Q, ARC, — разобраны в статье LFU и ARC.

Цена точности. Переставлять узел при каждом обращении дорого, когда обращений миллиарды в секунду или когда на элемент жалко двух указателей. Поэтому в системах чаще работают приближения. Многие операционные системы и PostgreSQL используют «часы»: один бит или маленький счётчик на страницу и стрелку по кругу (как они устроены — в главе о виртуальной памяти); на первой сцене видно, что часы идут почти вровень с LRU. Redis в режиме allkeys-lru не хранит порядок вовсе: при нехватке памяти он берёт несколько случайных ключей — по умолчанию пять — и выселяет самый давний из них, с версии 3.0 ещё и держит пул хороших кандидатов; документация объясняет выбор тем, что точный LRU стоит больше памяти. В ядре Linux страницы долго жили в двух списках, активном и неактивном, а с версии 6.1 появился многопоколенный LRU, разработанный в Google.

История

В 1966 году Ласло Белади из IBM опубликовал большое сравнение правил вытеснения страниц для машины с виртуальной памятью и описал недостижимое лучшее правило — выселять то, что понадобится позже всех (подробнее — в главе курса). В 1970 году Маттсон, Гечей, Слуц и Трейгер в IBM Systems Journal ввели стековые алгоритмы, к которым относятся и LRU, и правило Белади, и показали, как одним проходом по записи обращений получить поведение памяти любого размера. В 1985 году Дэниел Слитор и Роберт Тарьян в Communications of the ACM доказали, что LRU и FIFO уступают правилу Белади не больше чем в k/(k − h + 1) раз, и что лучше гарантировать нельзя. С этого сравнения алгоритма, не знающего будущего, с алгоритмом, который его знает, начался конкурентный анализ онлайн-алгоритмов; само название появилось в 1988 году.

Журнал, на котором работают сцены и листинги, собрал Джим Дюмулен из Космического центра Кеннеди, а Мартин Арлитт и Кэри Уильямсон выложили его в открытый архив Internet Traffic Archive: это один из шести журналов, на которых они искали общие закономерности нагрузки веб-серверов для статьи 1996 года. Адреса клиентов в журнале сохранены, но архив просит не анализировать ничего, кроме общей картины трафика; здесь адресов нет вовсе, а поисковые запросы и имена пользователей в путях заменены номерами.

Задачи

В первой нужно написать кэш на O(1) и прогнать через него тот же день сервера NASA и большие журналы, где медленный кэш не успеет. Во второй нужно для каждого размера кэша сказать, сколько запросов он поймает, — за один проход, как Маттсон, но быстрее, чем проходом по стеку.