Как устроен LRU и почему один большой отчёт вымывает весь кеш для остальных

MAATRIX

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

Что такое LRU и зачем кешу вообще нужна политика вытеснения

Кеш всегда меньше, чем множество данных, которые в теории могли бы в нём оказаться. Оперативная память на сервере с Redis или Memcached измеряется гигабайтами, а строк в базе, объектов в S3 или ответов API — обычно на порядки больше. Значит, в какой-то момент кеш заполняется, и любая новая запись требует освободить место под старую.

Здесь и появляется политика вытеснения (eviction policy) — правило, по которому кеш выбирает жертву. Вариантов несколько:

• FIFO — выкидывать то, что попало в кеш раньше всего, независимо от того, обращались к этому недавно или нет. Дёшево считать, но плохо работает на практике: старый, но популярный элемент вылетит так же легко, как и старый ненужный.
• Random — выбрать жертву случайно. Звучит грубо, но иногда работает не сильно хуже LRU и почти ничего не стоит по накладным расходам — поэтому в Redis есть режимы allkeys-random и volatile-random.
• LRU (Least Recently Used) — выкидывать то, к чему дольше всего не было обращений. Идея в том, что данные, которые были нужны недавно, скорее всего понадобятся снова в ближайшее время (это называется temporal locality, локальность по времени, и в реальных нагрузках она действительно часто подтверждается).
• LFU (Least Frequently Used) — выкидывать то, к чему обращались реже всего, независимо от того, когда был последний раз. Об этом подробнее — дальше в статье.

LRU стал стандартом по умолчанию почти везде — от кеша процессора до Redis, Memcached, буферных пулов баз данных и HTTP-кешей в браузере — не потому что он идеален, а потому что он дёшев в реализации и в среднем даёт неплохой результат на типичной нагрузке. Проблема начинается там, где нагрузка нетипичная.

Как LRU устроен технически: от связного списка до approximate LRU

Классическая, «учебная» реализация LRU — это связка из хеш-таблицы и двусвязного списка:

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

Обе операции — доступ и вытеснение — работают за O(1), что и сделало LRU практичным выбором: он не требует пересчёта статистики по всему кешу при каждой операции, в отличие от многих более «умных» схем.

На практике точная реализация с честным списком используется не везде. У неё есть накладные расходы: на каждую операцию чтения нужно менять указатели списка, а под конкурентным доступом из многих потоков это означает блокировки или атомарные операции на горячем пути. Поэтому многие системы используют приближённый (approximate) LRU.

Например, Redis по умолчанию не ведёт честный список для всех ключей. У каждого объекта есть поле с меткой времени последнего доступа (LRU clock, 24-битное значение с точностью примерно до секунд). Когда нужно освободить память, Redis не сканирует всё пространство ключей, а берёт случайную выборку — по умолчанию 5 ключей (параметр maxmemory-samples), сравнивает их метки и выкидывает самый старый из выборки. Это не точный LRU, а его статистическое приближение: чем больше maxmemory-samples, тем точнее поведение приближается к честному LRU, но тем дороже каждая операция вытеснения. Посмотреть метку доступа конкретного ключа можно так:

OBJECT IDLETIME key_name

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

Сценарий cache pollution: как один запрос вымывает всё

Теперь к сути проблемы. Представим типичный веб-сервис: тысячи пользователей каждую минуту читают одни и те же карточки товаров, профили, ленты — небольшой набор «горячих» ключей, который живёт в кеше и обслуживает основную массу трафика. Кеш рассчитан примерно на этот рабочий набор (working set) и при нормальной нагрузке держит hit rate высоким.

А теперь ночью или в конце месяца запускается один тяжёлый job: аналитический отчёт, выгрузка для бухгалтерии, полный обход каталога для переиндексации поиска. Такой запрос читает огромный объём данных — часто весь набор строк таблицы или все объекты определённого типа — но делает это буквально один раз. Сами по себе эти данные почти никогда не запрашиваются повторно: отчёт посчитан, выгрузка сохранена, обход завершён.

Проблема в том, что с точки зрения LRU разницы между «горячим» ключом обычного пользователя и «холодным» ключом из отчёта нет вообще. LRU смотрит только на один факт: обращались к ключу недавно или нет. Отчёт читает миллион строк — каждая из них при обращении отмечается как «только что использованная» и уходит в голову списка (или получает свежую метку времени в approximate-варианте). Если кеш вмещает условно 200 тысяч записей, а отчёт за проход коснулся 500 тысяч уникальных ключей, то к концу выгрузки в кеше физически не остаётся места для старых горячих данных — они вытеснены, потому что формально оказались «давно не используемыми» по сравнению с только что прочитанными строками отчёта.

Итог предсказуем: как только отчёт завершается, обычные пользователи начинают получать промахи кеша (cache miss) там, где секунду назад всё работало быстро. База данных или бэкенд получают резкий всплеск нагрузки — не потому что выросло число пользователей, а потому что кеш пришлось прогревать заново с нуля. Именно поэтому одна фоновая задача способна на несколько минут просадить отклик всего сервиса, хотя формально не нарушила ни один лимит и не сделала ничего «неправильного» — просто прочитала данные, которые ей были нужны.

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

Почему LRU в этом случае прав по правилам, но неверен по сути

Важно понимать: LRU не сломался и не «сглючил». Он сделал ровно то, что должен: выкинул то, что дольше всего не было в использовании, и оставил то, что использовалось недавно. Проблема не в реализации, а в самой гипотезе, на которой основан алгоритм.

Гипотеза LRU — «недавнее использование предсказывает будущее использование» — работает хорошо, когда доступ к данным более-менее равномерный и повторяющийся: одни и те же пользователи снова и снова смотрят одни и те же карточки. Она перестаёт работать, когда в трафик подмешивается последовательное сканирование большого объёма данных, которые не будут запрошены повторно. LRU не умеет отличать эти два паттерна доступа — он видит только временную метку, а не то, сколько раз к ключу обращались и вернутся ли к нему снова.

Это системная слабость, известная задолго до появления Redis — она разбиралась ещё применительно к буферным пулам баз данных и кешам файловых систем: буферный пул точно так же может быть вымыт одним полным сканированием таблицы, если СУБД не защищается от этого специальными механизмами. Ниже — какие механизмы для этого придумали.

LFU и учёт частоты: помним не только «когда», но и «сколько раз»

Самая прямая альтернатива — LFU, Least Frequently Used. Вместо метки времени последнего доступа каждый ключ хранит счётчик обращений, и вытесняется тот, у кого счётчик минимальный. Разовое чтение миллиона строк отчётом в этой схеме почти не опасно: каждая строка отчёта получает счётчик «1», а горячие ключи пользователей, к которым обращаются сотни раз в час, держат высокий счётчик и не вытесняются — даже если формально «давно» не читались в последние секунды.

У честного LFU есть свои минусы, поэтому в реальных системах его тоже приближают:

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

В Redis это реализовано как allkeys-lfu и volatile-lfu — политики, где вместо 24-битной метки времени у объекта хранится 8-битный логарифмический счётчик обращений с вероятностным увеличением (чем выше текущее значение, тем реже оно инкрементируется на следующее обращение) и настраиваемым затуханием во времени:

CONFIG SET maxmemory-policy allkeys-lfu
CONFIG SET lfu-log-factor 10
CONFIG SET lfu-decay-time 1

lfu-log-factor управляет тем, насколько медленно растёт счётчик на высоких значениях (выше — счётчик точнее различает очень горячие ключи между собой), lfu-decay-time — через сколько минут «неактивности» счётчик уменьшается на единицу. Точных значений для вашей нагрузки заранее никто не даст — это параметры, которые имеет смысл подбирать по факту на графике hit rate, а не копировать из чужого конфига.

Более продвинутая идея в том же направлении — TinyLFU (используется в библиотеке кеширования Caffeine для JVM): компактная приближённая структура на основе count-min sketch, которая перед добавлением нового элемента сравнивает его оценочную частоту с частотой кандидата на вытеснение и не пускает внутрь «одноразовые» ключи, если место уже занято более востребованным.

Сегментированные кеши: держим разовые запросы отдельно от рабочего набора

Второй путь — не пытаться угадать частоту одним счётчиком, а физически разделить кеш на зоны с разной судьбой.

Segmented LRU (SLRU) делит кеш на два сегмента: probationary (испытательный) и protected (защищённый). Новый ключ при первом обращении попадает в испытательный сегмент, а при повторном обращении переезжает в защищённый, который вытесняется в последнюю очередь. Разовое сканирование отчётом заполняет только испытательный сегмент и вытесняет из кеша только других «разовых» кандидатов, не трогая защищённые горячие данные. Похожий по смыслу подход — ARC (Adaptive Replacement Cache), применявшийся, например, в ZFS: он динамически балансирует между списком «использованных один раз» и «использованных многократно», подстраивая размеры под реальный трафик.

На практике эту же идею часто реализуют проще, на уровне архитектуры приложения, а не алгоритма кеша:

• Отдельный кеш или отдельная логическая база для отчётов и batch-задач. В Redis это может быть просто другой номер SELECT-базы или отдельный инстанс на другом порту с собственным maxmemory, который не делит память с кешем горячих пользовательских данных. Тяжёлый отчёт вымывает сам себя, но не трогает соседний кеш.
• CLIENT NO-TOUCH ON — команда, появившаяся в Redis 7.0, которая для текущего соединения отключает обновление LRU/LFU-метаданных при чтении. Клиент, который выполняет разовое массовое сканирование (например через SCAN + MGET), может явно сказать Redis «не считай это использованием» — и тогда прочитанные им ключи не получат свежую метку и не будут защищены от вытеснения как только что использованные, а заодно не вытеснят чужие горячие ключи вперёд себя.
• TTL и volatile-политики отдельно для batch-данных. Если отчёт всё же кладёт промежуточные результаты в тот же кеш, имеет смысл ставить им короткий явный TTL и использовать volatile-lru/volatile-lfu (вытеснять только ключи с TTL), оставляя постоянные горячие ключи без TTL защищёнными от этой политики вытеснения в принципе.
• Лимит на размер запроса или курсорное чтение вместо полного скана, когда это возможно — сама задача отчёта не обязана читать всё одним проходом через общий кеш; часто дешевле дать ей отдельный путь к данным (реплика для аналитики, прямой запрос в холодное хранилище) в обход горячего кеша целиком.

Ни один из этих подходов не бесплатен: LFU и сегментированные схемы точнее, но чуть дороже по накладным расходам на каждую операцию, а разделение на отдельные инстансы означает больше памяти и больше операционной сложности, чем один общий кеш. Выбор конкретной схемы — это компромисс между простотой honest LRU и точностью того, что предлагают LFU или SLRU, и правильный ответ зависит от того, насколько часто в вашей нагрузке реально случаются разовые массовые сканирования.

Частые вопросы