Стратегия кэширования для URL-редиректов: L1 LRU и L2 Redis

Уровень редиректов в сокращателе URL — одна из немногих продакшн-систем, где стратегия кэширования и есть сама архитектура. На горячем пути (hot path) не происходит никакой другой значимой работы: каждый запрос разрешает ключ (короткий слаг), считывает URL назначения и выдает 301 или 302. Все остальное — это observability и учет данных. Именно кэш определяет, займет ли медианный запрос 800 микросекунд или 12 миллисекунд.

В этом посте документирована стратегия кэширования сервиса edge-redirect в Elido. Два уровня, политика вытеснения, выбранная для оптимизации хвостовой задержки (tail latency), а не коэффициента попаданий (hit rate), скучная, но надежная стратегия прогрева и разбор сбоев, которые мы видели за 18 месяцев работы в продакшене. Статья о p95 редиректа < 15 мс описывает общий бюджет задержки; это же — глубокое погружение именно в кэш.

Почему два уровня#

Самая простая архитектура кэша для сервиса редиректов — одноуровневая: кластер Redis между процессом редиректа и основной базой данных. Каждый запрос, который не попадает в базу, попадает в Redis; каждый запрос, который не попадает в Redis, попадает в базу. Прыжок в Redis добавляет около 1 мс, если Redis находится в том же регионе.

Двухъярусные кэши добавляют внутрипроцессный слой перед Redis. Первый уровень — назовем его L1 — живет внутри адресного пространства процесса редиректа. Попадание в L1 возвращает URL назначения за несколько сотен наносекунд, не требуя сетевого round-trip. Промах в L1 переходит в Redis (L2), который обслуживает запрос с задержкой менее миллисекунды. Промах в L2 переходит в gRPC-вызов к основной базе данных Postgres.

Выбор между одним или двумя уровнями — это, по сути, вопрос того, насколько «плоской» должна быть ваша хвостовая задержка. Redis быстрый, но не бесплатный. Задержка 1 мс p50 для Redis превращается в 4–6 мс p99 под нагрузкой, а p99.9 может превышать 20 мс при любых сетевых заторах. Для SLO, нацеленного на p95 < 15 мс, каждое попадание в Redis потребляет значительную часть бюджета. Для p99.9 < 50 мс хвост Redis становится доминирующим фактором.

LRU внутри процесса поглощает самые высокочастотные ключи — те, что обеспечивают более 80% трафика. При распределении трафика Elido на 1000 топовых коротких ссылок приходится более 70% запросов. Эти ключи легко обслуживать внутри процесса; длинный хвост может уходить в Redis без деградации p95.

L1: LRU на уровне процесса#

Кэш L1 использует Ristretto — тот же LRU с политикой допуска (admission-policy), который используют Caddy и Dgraph. Мы выбрали его по трем причинам:

Конкурентное чтение масштабируется линейно с ядрами CPU. Простой кэш на базе sync.Map упирается в потолок около 4 млн операций в секунду на типичной машине edge POP; Ristretto поддерживает более 30 млн в наших бенчмарках.
Политика допуска TinyLFU предотвращает вытеснение горячих ключей одноразовыми нагрузками сканирования. Обход бота, который по разу запрашивает 10 000 уникальных слагов, не вытесняет по-настоящему популярные ссылки из кэша.
Ограничение по памяти, а не по количеству ключей. Мы можем установить «использовать до 256 МБ» вместо «хранить до 100 000 записей», что критично для планирования мощностей.

Конфигурация, которую мы используем:

cache, err := ristretto.NewCache(&ristretto.Config{
    NumCounters: 10_000_000, // 10M counters → tracks ~1M items
    MaxCost:     256 << 20,   // 256MB
    BufferItems: 64,
    Metrics:     true,
})

NumCounters — это размер таблицы отслеживания частоты TinyLFU; эмпирическое правило из документации Ristretto — в 10 раз больше ожидаемого количества элементов. При бюджете 256 МБ и средней записи ссылки в 200 байт кэш вмещает около 1,3 млн записей при заполнении.

TTL для записей L1 составляет 60 секунд. Это намеренно короткий срок. Назначение редиректа может быть изменено в панели управления в любое время, а кэш L1 — самый медленный слой для инвалидации (Redis можно инвалидировать при публикации; L1 живет в каждом процессе и требует скоординированного пути инвалидации).

TTL в 60 секунд означает, что в худшем случае данные будут неактуальны в течение 60 секунд после обновления назначения. Для большинства сценариев это приемлемо; для случаев, когда это недопустимо (мгновенная смена назначения во время активной кампании), кнопка инвалидации в панели управления запускает fanout, который очищает все кэши L1 во всем флоте. Для fanout используется Redis pub/sub на канале, на который подписывается каждый edge-процесс при запуске.

L2: Кластер Redis с репликами для чтения#

L2 — это кластер Redis, развернутый в каждом регионе (Frankfurt, Ashburn, Singapore). Чтение идет из локальных реплик; запись — в основной узел региона и реплицируется в рамках стандартной асинхронной модели Redis.

Формат данных компактный. Запись редиректа в L2 выглядит так:

KEY:   redirect:f.elido.me:abc123
VALUE: {"d":"https://shop.example.com/spring","f":0,"v":12}

Три поля: URL назначения (destination), флаги (фильтрация ботов включена, требуется пароль и т. д., упакованные в uint16) и версия. Версия — это версия строки из Postgres; она позволяет обнаруживать устаревшие записи кэша при чтении.

TTL в L2 составляет 24 часа. Это гораздо дольше, чем в L1, потому что у L2 есть рабочий путь инвалидации: при создании или обновлении ссылки в основной базе данных API публикует сообщение Redis pub/sub в региональный канал инвалидации, и процессы edge-redirect вытесняют свои записи L1; запись L2 перезаписывается напрямую уровнем API.

Инвалидация через pub/sub имеет тонкую особенность: она может приводить к потере данных. Если процесс редиректа перезагружается в момент публикации сообщения об инвалидации, он не увидит сообщения, и его кэш L1 может отдавать устаревшее значение до 60 секунд. Мы допускаем это, так как TTL служит страховкой — время устаревания ограничено.

Размер кластера Redis в каждом POP невелик. Во Франкфурте работают три основных узла плюс три реплики; весь набор данных помещается примерно в 4 ГБ. При нашем коэффициенте попаданий (98% L1, 1,8% L2, 0,2% к источнику при нормальной нагрузке) требования к пропускной способности Redis умеренные — обычно 5–15 тыс. операций в секунду на пике на каждый POP, что вполне укладывается в возможности одного основного узла, если бы нам пришлось консолидироваться.

Выбор политики вытеснения#

Политика допуска TinyLFU в Ristretto — это выбор, который важнее всего для хвостовой задержки.

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

Нагрузки сканирования (Scan workloads). Краулер ботов, который быстро опрашивает 50 000 уникальных слагов, при наивном LRU вытеснит все горячие ключи и заменит их ключами краулера, к которым больше никогда не будет обращений. Коэффициент попаданий в кэш падает, основная база видит всплеск нагрузки, а p95 прыгает, так как большинство запросов теперь идут по длинному пути.
Взрывные горячие ключи (Bursty hot keys). Ссылка, которая обычно «холодная», но внезапно получает 100 тыс. запросов за 30 секунд (вирусный пост, реклама на ТВ), должна быть закэширована быстро. При наивном LRU она вытеснит один из существующих горячих ключей.

TinyLFU справляется с обоими случаями. Политика допуска отслеживает частоту ключей и допускает новый ключ в кэш только в том случае, если он встречается чаще, чем кандидат на вытеснение. Одноразовый обход бота не вытесняет горячие ключи, так как у ключей краулера частота равна 1. Взрывной горячий ключ попадает в кэш, но только после того, как его частота превысит частоту кандидата на вытеснение — что происходит в течение первых нескольких сотен запросов.

Цена заключается в том, что первые 100–500 запросов для новой популярной ссылки будут медленными (уйдут в L2 или базу), пока политика допуска не решит её закэшировать. Для большинства сценариев это оправданный компромисс; для кампаний, где мы заранее знаем о всплеске, у нас есть эндпоинт предварительного прогрева, описанный ниже.

Прогрев кэша#

Кэш L2 проходит «холодный старт», когда запускается новый кластер Redis. Мы не прогреваем его из снапшота; в первые 5 минут после перезапуска кластера наблюдается повышенный трафик к базе, пока кэш не заполнится естественным образом.

Кэш L1 проходит холодный старт при перезапуске процесса редиректа (деплой, OOM, масштабирование). Первые 30 секунд после перезапуска процесса большинство запросов уходят в L2; в следующие 60 секунд L1 заполняется рабочим набором горячих ключей. Суммарный вклад холодного старта в нагрузку на базу невелик (большинство edge-процессов перезапускаются гораздо реже, чем истекает TTL кэша).

Исключение: когда менеджер кампании заранее публикует ссылку, которая точно даст всплеск (URL из ТВ-рекламы, пресс-релиза, анонса запуска), панель управления предлагает переключатель «pre-warm». Его активация инициирует холостой запрос редиректа к сервису edge-redirect в каждом POP, что заранее заполняет L1. Это не самый изящный метод и он редко требуется; автоскейлер адекватно справляется с непредвиденными всплесками. Прогрев — это решение для ожидаемых пиков, когда задержка холодного кэша в первые 60 секунд была бы заметна.

Что происходит при заполнении L1#

Кэш L1 объемом 256 МБ заполняется менее чем за минуту на типичном edge POP. После заполнения для каждого нового ключа политика TinyLFU должна решить, стоит ли вытеснять существующий ключ.

Интересное наблюдение: при нашем распределении коэффициент попаданий L1 стабилизируется на уровне около 98% после прогрева. 2% промахов — это «длинный хвост» — примерно 30% ссылок, на которые приходится менее 30% трафика, и которые не проходят порог частоты TinyLFU. Эти запросы промахиваются в L1 и попадают в L2, где коэффициент попаданий составляет около 99%. Оставшиеся 0,2% всех запросов уходят в основную базу.

Мы измеряли это распределение при трех типах нагрузки — тяжелый трафик ботов, вирусный всплеск, стабильное состояние — и коэффициент попаданий L1 колебался между 95% и 99%. Коэффициент попаданий L2 более стабилен и составляет 98–99,5%. Таким образом, общая нагрузка на базу от уровня редиректов ограничена примерно 0,5% от входящего объема запросов — это именно та цифра, которая важна для планирования мощностей источника.

Подробно об инвалидации кэша#

Поток инвалидации — это часть архитектуры, которую чаще всего понимают неправильно. Детали:

Когда API получает PATCH /v1/links/{id}, изменяющий URL назначения, последовательно происходят три вещи:

Postgres фиксирует изменения с новой версией строки (UPDATE links SET destination = ?, version = version + 1 WHERE id = ?).
Запись в Redis напрямую с новым значением в каждом региональном кластере Redis. Запись рассылается от API в Redis каждого региона через уровень сквозной записи (write-through).
Публикация инвалидации через pub/sub в каждом региональном канале invalidate:redirect. Процессы edge-redirect подписываются на этот канал при запуске и вытесняют запись L1 для данного ключа.

Порядок имеет значение. Сначала Postgres гарантирует, что в каноническом хранилище есть новое значение. Запись в Redis перед публикацией гарантирует, что любой процесс, который пропустит публикацию, но обратится к Redis, увидит новое значение. Публикация — это оптимизация для синхронизации L1; TTL — страховка на случай пропуска публикации.

Известное состояние гонки (race condition): процесс редиректа читает из Redis (из-за промаха в L1) одновременно с публикацией инвалидации. Чтение может вернуть новое значение (публикация произошла чуть раньше) или старое (публикация чуть позже). Если будет возвращено старое значение и закэшировано в L1, этот процесс может отдавать старое значение в течение следующих 60 секунд. Это допустимо; альтернатива — синхронная блокировка вокруг гонки «чтение-публикация» — добавила бы задержку каждому запросу ради избежания граничного случая, который затрагивает менее 0,01% инвалидаций.

Для случаев, когда окно устаревания недопустимо (URL назначения удаляется по юридическим причинам или внезапно стал вредоносным), действие «purge cache» в панели управления запускает агрессивную инвалидацию: оно приостанавливает чтение из L1 на 100 мс во всем флоте, вытесняет ключ из каждого L1, а затем возобновляет работу. Это используется редко и ограничено лимитом запросов в секунду.

Сбои, с которыми мы столкнулись на практике#

Три сбоя за 18-месячную историю эксплуатации, которые стоит задокументировать, так как они сформировали текущую конфигурацию.

Failover основного узла Redis с устаревшими репликами. На 4-й месяц работы в кластере Франкфурта отказал основной узел. Реплика была повышена в течение 30 секунд (failover под управлением Sentinel). Реплики отставали от основного узла примерно на 200 мс в момент сбоя, что означало, что первые несколько сотен инвалидаций, опубликованных непосредственно перед сбоем, не достигли повышенной реплики. Результат: краткое окно, когда около 0,3% редиректов отдавали старые назначения. Решение: теперь мы запускаем реплики с min-replicas-to-write 1 и min-replicas-max-lag 10, что немного снижает доступность записи в пользу более жестких гарантий лага репликации.

Трэшинг (thrashing) кэша L1 во время сканирования мониторингом. На 9-й месяц сторонний сервис мониторинга был неправильно настроен: он проверял каждую короткую ссылку в воркспейсе клиента раз в минуту. У клиента было 18 000 ссылок. Паттерн проверки представлял собой полное сканирование каждые 60 секунд. Эффект: коэффициент попаданий L1 упал с 98% до 71% на трех edge POP, так как паттерн сканирования заносил каждый проверенный ключ в кэш. Решение: мы добавили фильтрацию на основе User-Agent перед уровнем допуска в кэш — известные User-Agent мониторинга обходят кэш L1 и обслуживаются напрямую из L2. Это был граничный случай TinyLFU: ключи сканирования выглядели достаточно частотными, чтобы вытеснить реально горячие ключи.

Разрыв соединения pub/sub во время длительного деплоя. На 13-й месяц деплой, занявший больше времени, чем ожидалось (около 4 минут), привел к тому, что несколько edge-процессов остались подключенными к старому каналу pub/sub после того, как основной узел Redis переключился. Инвалидации, опубликованные на новом основном узле, не достигли этих процессов; их кэши L1 отдавали устаревшие значения на протяжении всего деплоя. Решение: введение heartbeats для соединений pub/sub с автопереподключением при пропуске, а также очистка L1 во время деплоя в качестве меры предосторожности.

Что мы рассматривали и от чего отказались#

Несколько альтернатив, которые мы оценивали, но не выбрали:

Только внутрипроцессный кэш без Redis. Протестировано. Доля промахов в базу от одного процесса слишком высока без L2; основной базе данных потребовалось бы в 3–5 раз больше мощностей. Стоимость Redis невелика по сравнению с экономией ресурсов базы.

CDN вроде Cloudflare или Fastly для кэширования редиректов. Протестировано в staging. Задержка CDN в 1–2 мс на попадание в кэш примерно равна задержке Redis, но ситуация с инвалидацией значительно хуже (очистка CDN занимает минуты и стоит денег за каждый URL). CDN добавила сложности, не улучшив задержку или коэффициент попаданий.

Увеличение объема L1. Бюджет в 256 МБ соответствует лимитам памяти процесса; его удвоение не удваивает коэффициент попаданий, так как рабочий набор горячих ключей уже помещается в кэш. Закон убывающей отдачи вступает в силу примерно на 128 МБ при нашем распределении; 256 МБ дают запас для роста трафика.

Наблюдаемость (Observability)#

Метрики, которые мы отслеживаем для каждого edge-процесса:

cache_l1_hit_total, cache_l1_miss_total — расчетный hit rate на процесс.
cache_l2_hit_total, cache_l2_miss_total — расчетный hit rate на регион.
cache_origin_request_total — объем запросов к базе; цель SLO < 1% от всех запросов.
cache_invalidation_total{source="pubsub|ttl|purge"} — количество инвалидаций по механизмам.
cache_l1_memory_bytes — реальный объем памяти, используемый L1; оповещение при достижении 90% бюджета.

Все метрики собираются Prometheus и визуализируются в наборе дашбордов руководства по observability. Дашборды Grafana на региональном уровне показывают коэффициент попаданий в регионе со временем; дашборды уровня процесса (используемые при инцидентах) показывают hit rate L1 и использование памяти конкретным процессом.

Когда использовать эту стратегию, а когда нет#

Двухъярусный кэш оправдан, когда:

Нагрузка преимущественно на чтение с распределением ключей по принципу «длинного хвоста».
Рабочий набор горячих ключей помещается в память процесса (несколько сотен мегабайт).
Промахи кэша достаточно дороги, чтобы второй ярус существенно экономил ресурсы базы.
Требования к актуальности данных жестче, чем позволяет только TTL уровня L1.

Это не имеет смысла, если:

Рабочий набор горячих ключей не помещается в память процесса. В этом случае промахи L1 будут так часто уходить в L2, что вклад L1 станет ничтожным.
Запись происходит часто по сравнению с чтением. Стоимость инвалидации станет доминирующей.
Данные уникальны для каждого запроса (кэширование вообще не дает преимуществ).

Для нагрузки сокращателя URL верны все четыре условия «за», и описанная выше конфигурация успешно справляется с ростом продакшена в течение 18 месяцев. Для других типов нагрузки количество ярусов и политика вытеснения требуют повторной оценки.

Что еще почитать#

Достижение p95 < 15 мс для редиректов из FRA, ASH и SGP — ключевой материал инженерного кластера; этот пост является глубоким погружением именно в тему кэша.
Почему мы используем ClickHouse для аналитики кликов (а не Postgres) — смежное инженерное решение в той же архитектуре.
Сбор кликов по принципу «выстрелил и забыл» с Redpanda — конвейер событий кликов, который работает параллельно с кэшем редиректов.
Короткие ссылки как Terraform — операционное руководство по настройке уровня редиректов.
Архитектура Edge: /docs/architecture/edge-redirect.
Операционное руководство: /docs/guides/observability — упомянутый выше набор дашбордов.
Продуктовые решения: /solutions/developers и /solutions/analytics.
Внешние ресурсы: Статья о дизайне Ristretto и статья о TinyLFU с теорией политик допуска.