Cache Celebrity Problem: почему 100 Redis-нод не спасут вас от одного hot key — и что заложить в архитектуру до первого крупного клиента

Можно идеально разложить миллиард ключей по 100 Redis-нодам и всё равно получить деградацию из-за одного merchant:123. Если один клиент внезапно начинает генерировать 500 000 RPS, средняя загрузка кластера может выглядеть прекрасно ровно до того момента, когда один shard упрётся в CPU и сеть.

В распределённых системах мы привыкли лечить нагрузку горизонтальным масштабированием: добавили ноды, разбили данные на shard'ы, распределили ключи через hash или consistent hashing — живём дальше.

Проблема в том, что эта модель хорошо работает, пока нагрузка распределена более-менее равномерно.

В реальной системе она почти никогда не равномерна.

Один merchant проводит платежей на два порядка больше остальных. Один SKU внезапно становится вирусным. Один пост читают миллионы пользователей. Один tenant вырастает так, что начинает потреблять заметную долю всего кластера.

Так появляется Cache Celebrity Problem, она же частный случай hot key / hot partition problem.

Проще всего объяснить на социальной сети.

Допустим, последние посты пользователя лежат в кеше так:

У обычного пользователя этот ключ читают несколько раз в минуту.

Теперь Cristiano Ronaldo публикует пост. Миллионы пользователей начинают читать:

С точки зрения данных ничего особенного не произошло. Это по-прежнему один ключ.

С точки зрения нагрузки этот ключ отличается от остальных на несколько порядков.

Отсюда и название: небольшое количество «знаменитостей» получает непропорционально большую долю трафика.

Причём celebrity — это необязательно человек. В платёжной системе им легко становится крупный merchant или банковский BIN. В e-commerce — популярный SKU. В SaaS — жирный tenant. В инфраструктуре — конфигурационный ключ, который читает весь fleet.

Главное свойство одно:

То есть проблема не в объёме данных. Проблема в skew распределения нагрузки.

Представим Redis Cluster из 100 нод.

Есть миллиард ключей, которые отлично распределились по shard'ам:

На каждый shard приходится примерно одинаковый объём данных. Красиво.

Потом появляется:

И получает:

Hash всё равно отправляет ключ на одну ноду:

Получаем примерно это:

Остальные 99 shard'ов в этот момент могут быть загружены на 5%.

Средний CPU кластера будет выглядеть почти издевательски хорошо:

А система уже деградирует.

Это одна из самых неприятных частей Celebrity Problem: агрегированные метрики успокаивают ровно тогда, когда надо начинать нервничать.

Если смотреть только на average CPU, average latency и суммарный RPS, hotspot легко пропустить. Нужны метрики уровня конкретного shard'а и конкретной нагрузки:

Особенно полезны отношения вроде:

и:

Если средний shard держит 10k RPS, а максимальный уже 80k RPS, то skew factor = 8. Средняя температура по больнице здесь ничего не объясняет.

У consistent hashing другая работа.

Он хорошо распределяет разные ключи между нодами:

Но один ключ получает одно положение:

Если половина всего трафика системы приходит в этот ключ, половина трафика окажется на одном shard'е.

Отсюда принцип, который полезно держать в голове при любом шардировании:

балансировка данных != балансировка нагрузки

Архитектору куда важнее знать распределение RPS по ключам и tenant'ам, чем радоваться одинаковому количеству ключей на shard.

Поэтому и очевидные решения часто не работают.

«Redis перегружен — давайте добавим нод» лечит общую нагрузку. Если было 10 shard'ов, стало 100, hot key просто переедет с shard-7 на shard-73. Инфраструктура станет дороже в десять раз, а bottleneck останется на одной машине.

Можно поставить shard помощнее. Иногда это нормальная временная мера. Но 500k RPS -> one machine остаётся той же архитектурой. Завтра будет 1M RPS — и потолок вернётся.

Ещё хуже бывает с TTL. Интуитивно хочется уменьшить его ради свежести. Но если горячий ключ получает 100k RPS и протухает каждую секунду, один cache miss легко превращается в толпу одинаковых запросов к downstream.

Было:

Стало:

Это уже cache stampede / thundering herd.

Универсальной кнопки нет. Нормальная защита обычно строится слоями.

Если значение допускает хотя бы секунду stale-данных, локальный кеш внутри application instance может снять несколько порядков запросов с Redis.

Вместо:

получаем:

Например:

Есть 100 application instances и 100k RPS на один горячий объект.

Без L1 это до 100k Redis reads/sec.

С L1 при достаточно горячих данных мы можем получить порядок 100 Redis reads/sec: каждый instance обновляет локальную копию примерно раз в секунду.

Цена понятна: данные между instances некоторое время расходятся, а холодный старт fleet способен ударить вниз по стеку. Но если бизнес допускает секундную stale-версию, это очень дешёвый способ убрать сетевой трафик из самой горячей части path.

Если один ключ уже не помещается по RPS на одну машину, нет смысла продолжать хранить одну физическую копию.

Вместо:

делаем:

На чтении выбираем одну из реплик:

Разные physical keys попадут на разные shard'ы, и один logical key начнёт масштабироваться горизонтально.

Это, пожалуй, главный сдвиг мышления в Celebrity Problem:

если один logical key слишком горячий для одной машины, ему нужны несколько physical representations.

Мы больше не пытаемся масштабировать «кластер вообще». Мы масштабируем конкретную celebrity.

Репликация спасает steady-state чтения, но не cache miss.

Допустим, 10 000 запросов одновременно хотят объект, которого сейчас нет в кеше.

Плохой вариант:

Нормальный:

Первый запрос загружает данные. Остальные ждут его результат.

В Go на одном instance это может быть обычный:

Для distributed-варианта понадобится coordination между instances или request collapsing ниже по стеку.

Здесь важен сам принцип: popular cache miss опаснее popular cache hit. Пока значение есть в кеше, мы мучаем cache layer. Когда оно исчезло, celebrity способна мгновенно протащить весь свой RPS в базу.

Классическая модель TTL выглядит так:

Для hot key это довольно нервная схема.

Полезнее иметь промежуточное состояние:

Например:

Это stale-while-revalidate / lazy revalidation.

Тот же принцип хорошо работает во время проблем downstream. Иногда старые данные на пару минут дешевле, чем идеально свежий ответ ценой умершей базы.

Некоторые celebrity предсказуемы.

Пользователь с десятками миллионов подписчиков публикует пост. Большой merchant запускает распродажу. Популярный товар появляется в промо.

В таких случаях можно прогреть cache replicas заранее:

Для news feed это особенно хорошо ложится на гибридную схему. Обычных пользователей можно обслуживать через push/fan-out, а celebrity перевести на pull и держать отдельно закешированной.

Не надо пушить запись в десятки миллионов timelines. Достаточно заранее положить её в ограниченное число cache replicas.

В платёжных и SaaS-системах интереснее другой вариант.

Допустим, есть 100 000 клиентов. Большинство делает порядка 10 RPS.

Но несколько выглядят так:

А routing устроен классически:

В какой-то момент крупные merchants случайно оказываются вместе:

Остальные shard'ы получают около 10k RPS.

Это та же Celebrity Problem. Только celebrity теперь — жирный клиент.

И вот здесь hash(tenant_id) -> shard начинает мешать.

Пока система маленькая, жёсткая hash-схема очень удобна. Никакого metadata storage, routing map и control plane. Взяли tenantID, посчитали hash, нашли shard.

Проблема появляется в тот день, когда нужно сказать:

А hash-функция отвечает: «Нет».

Поэтому в крупной системе полезен слой indirection:

Для большинства tenants mapping всё ещё можно получать обычным hash:

Для исключений появляется override:

В коде реализауия примитивная:

Зато архитектурно меняется очень многое. Placement становится управляемым.

Если речь про cache, миграция относительно простая.

Сначала поднимаем target shard. Потом прогреваем на нём самые горячие ключи. Если переключить жирного клиента на пустой cache, migration сама создаст cache stampede.

После прогрева переключаем routing:

Mapping лучше версионировать и быстро распространять между application instances:

Старый cache я бы не удалял сразу. Пусть естественно умирает по TTL. Тогда rollback — это смена mapping обратно на 42 -> 7, пока старая копия ещё жива.

С persistent database shard всё заметно сложнее: backfill, CDC/replication, сверка состояния, при необходимости shadow reads, переключение routing, rollback window и только потом удаление старых данных.

Но главный вывод тот же:

routing не должен быть намертво зашит в hash-функцию.

Нужен control plane, который умеет перемещать конкретную нагрузку.

Иначе после появления первого действительно крупного клиента выяснится странная вещь: кластер масштабировать мы умеем, а одного клиента — нет.

Допустим, жирного merchant вынесли на отдельный shard.

Работает.

Через год он вырос ещё в десять раз и стал больше capacity одной машины.

Мы снова в исходной точке.

Тогда появляется следующий уровень:

То есть сначала система шардируется по клиентам. Потом конкретного клиента приходится шардировать уже внутри него самого:

Celebrity сначала перестаёт делить shard с соседями, а потом сама становится небольшим распределённым кластером.

И это нормальная эволюция. Плохой сценарий — когда архитектура считает, что любой tenant навсегда меньше одного shard.

Главная ошибка в таких системах — предполагать, что равномерное распределение данных автоматически даст равномерную нагрузку.

Не даст.

Один logical entity способен генерировать трафик, сопоставимый со всем остальным кластером. Поэтому система должна уметь обнаружить hotspot, изолировать его, размазать его нагрузку и при необходимости изменить placement.

Практические правила у меня здесь простые.

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

Именно эта разница обычно отделяет систему, которая отлично выглядит на архитектурной диаграмме, от системы, которая нормально переживает первого по-настоящему большого клиента.

Если вам интересны такие разборы про highload, distributed systems, Go и финтех — подписывайтесь на мой Telegram-канал.