Кэширование: уровни, инвалидация, cache stampede, hit rate

В предыдущей статье мы заставляли базу отвечать быстро. Кэш — соседняя стратегия: не ускорить работу, а не делать её вовсе. Это самый мощный инструмент в наборе инженера по производительности и одновременно самый коварный: он не ускоряет систему, он меняет её на другую систему — со своими режимами отказа, своим классом багов и своей стоимостью владения.

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

Главный принцип трека здесь работает буквально. «Добавим кэш» — самая частая гипотеза, которую принимают без измерения. Люди ставят кэш перед запросом, который занимает 3% времени ответа; кэшируют то, что и так лежит в буферном пуле базы; радуются hit rate 98%, не заметив, что оставшиеся 2% дают весь p99.

Арифметика ставки: считайте промахи, а не попадания

Средняя стоимость обращения через кэш:

$$\bar{T} = h \cdot T_{\text{hit}} + (1-h) \cdot (T_{\text{miss}} + T_{\text{fill}})$$

где $h$ — доля попаданий, $T_{\text{hit}}$ — стоимость попадания, $T_{\text{miss}}$ — поход к источнику, $T_{\text{fill}}$ — запись в кэш (сериализация, сеть, вытеснение чужой записи). Последнее слагаемое почти всегда забывают, и именно оно объясняет, почему кэш с низким hit rate делает систему медленнее оригинала: вы платите за промах плюс за укладку, ничего не получая взамен. Точка безубыточности:

$$h_{\text{break-even}} = \frac{T_{\text{fill}}}{T_{\text{miss}} - T_{\text{hit}} + T_{\text{fill}}}$$

Если поход к источнику — 2 мс, попадание — 0.3 мс, укладка — 0.4 мс, кэш окупается примерно с $h > 0.19$. Если источник — функция на 20 мкс, а попадание в Redis стоит 300 мкс, кэш вреден при любом hit rate: дешёвое вычисление заменили дорогим сетевым запросом. Это происходит чаще, чем кажется.

Теперь ключевая интуиция. Ускорение относительно варианта без кэша при $T_{\text{hit}} \to 0$ равно $1/(1-h) = 1/m$, где $m$ — доля промахов. Полезная величина — не hit rate, а miss rate, и мыслить о ней надо в разах, а не в процентных пунктах.

Разница между 90% и 95% — это половина нагрузки на базу. Разница между 60% и 65% — почти ничего. Поэтому «мы подняли hit rate на 5 пунктов» бессмысленно без указания, откуда и куда, и поэтому графики надо строить по miss rate в логарифмической шкале: там улучшение видно как падение, а деградация — как всплеск, тогда как на графике hit rate падение с 99.5% до 99% выглядит незаметным дрожанием у потолка.

Тот же счёт применим к нагрузке: $\text{QPS}_{\text{источник}} = \text{QPS} \cdot (1-h)$. Кэш с 99% попаданий держит базу на одном проценте трафика — и это же означает, что падение hit rate с 99% до 90% даёт базе десятикратный всплеск. Отсюда растёт весь раздел про метастабильные отказы ниже.

Для латентности картина ещё жёстче. Кэш почти не двигает медиану, зато определяет форму хвоста: p99 при $h = 0.99$ — это ровно стоимость промаха. Разговор о перцентилях был в статье про измерение, и здесь он критичен: кэш маскирует медиану и оставляет хвост нетронутым, а хвост — это то, что чувствует пользователь.

Почему кэш вообще работает

Кэш опирается на два эмпирических свойства реальных нагрузок. Временная локальность: обращение к объекту предсказывает следующее обращение к нему же — то же свойство, на котором стоят кэши процессора, см. «Кэши и локальность». И перекошенная популярность: частоты обычно близки к закону Ципфа, $p(i) \propto i^{-\alpha}$ при $\alpha$ около единицы, то есть крошечная доля ключей собирает большую часть трафика.

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

Уровни: где именно вы кэшируете

Слово «кэш» обозначает не одну вещь, а восемь разных, лежащих на пути одного запроса. Прежде чем добавлять девятую, стоит понять, какие уже работают и почему их не хватает.

Правило дистанции. Чем ближе кэш к потребителю, тем дешевле попадание и тем труднее инвалидация. Кэш браузера отозвать нельзя вообще — единственный механизм это версия в имени файла (app.a91f2c.js). Поэтому вечный Cache-Control: max-age=31536000, immutable ставят только на контент с хешем в URL, а на остальное — короткий TTL или валидацию по ETag.

Правило дублирования. Прежде чем кэшировать результат запроса к базе, проверьте, не лежит ли он уже в буферном пуле. Запрос, делающий Index Scan по разогретому индексу и возвращающий одну строку за 200 мкс, ничего не выиграет от Redis с RTT 300 мкс. Кэшировать надо агрегаты и результаты дорогих соединений, а не точечные выборки по первичному ключу.

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

Правый верхний угол — очевидные кандидаты. Правый нижний (дорого, но редко) — ловушка: hit rate будет низким, кэш заполнится мусором, вытеснение убьёт полезное. Для таких случаев нужен не кэш, а асинхронный пересчёт с материализацией.

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

Все проблемы кэша выглядят снаружи одинаково — «стало медленно». Ниже — что смотреть на каждом уровне.

Redis и memcached

$ redis-cli INFO stats | grep -E 'keyspace|expired|evicted'
keyspace_hits:184203911
keyspace_misses:9417720
expired_keys:2210443
evicted_keys:1183742
$ redis-cli INFO memory | grep -E 'used_memory_human|maxmemory_human|policy'
used_memory_human:11.84G
maxmemory_human:12.00G
maxmemory_policy:allkeys-lru

Считаем: $h = 184203911 / (184203911 + 9417720) = 0.951$. Красиво? Нет, и вот три причины.

Счётчики кумулятивные с момента старта процесса. Они дают среднее за недели аптайма и полностью размывают вчерашний инцидент, когда hit rate падал до 40% на два часа. Снимайте их в мониторинг и считайте производную — в PromQL это rate(redis_keyspace_hits_total[5m]) / (rate(redis_keyspace_hits_total[5m]) + rate(redis_keyspace_misses_total[5m])).

evicted_keys при used_memory вплотную к maxmemory — это диагноз. Здоровый кэш выбрасывает записи по TTL (expired_keys), больной — под давлением памяти (evicted_keys), то есть вытесняет живые горячие ключи. Прямой путь к обвалу hit rate.

95% — среднее по всем ключам инстанса. Внутри может быть префикс с 99.9% и другой с 30%: парадокс Симпсона в чистом виде. Разбивка по классам ключей нужна всегда.

# Что лежит в кэше: распределение по префиксам, без блокировки инстанса
$ redis-cli --scan --count 1000 | awk -F: '{print $1":"$2}' | sort | uniq -c | sort -rn | head
 412883 session:v3
  91204 product:v7
   8842 report:daily

$ redis-cli --hotkeys           # требуется maxmemory-policy allkeys-lfu
[00.00%] Hot key 'product:v7:8842' found so far with counter 254
[12.44%] Hot key 'feed:user:1' found so far with counter 1102

$ redis-cli --bigkeys           # крупные значения тормозят сериализацию и сеть
[00.00%] Biggest string found so far 'report:daily:2026-07-15' with 4194304 bytes

Метрики hit/miss на уровне приложения, помеченные классом ключа, важнее серверных счётчиков: только приложение знает, что product:v7:* и report:daily:* — разные сценарии с разной ценой промаха. Для memcached аналогично: stats даёт cmd_get, get_hits, get_misses, evictions, а stats slabs показывает slab calcification, когда память застряла в мелких слабах и недоступна крупным значениям.

Буферный пул базы

Уровень, про который забывают чаще всего. В PostgreSQL он виден прямо в плане:

EXPLAIN (ANALYZE, BUFFERS)
SELECT o.id, sum(i.price) FROM orders o JOIN order_items i ON i.order_id = o.id
WHERE o.created_at >= now() - interval '1 day' GROUP BY o.id;

 HashAggregate  (cost=48120.11..48330.44 rows=21033 width=12)
                (actual time=182.441..191.008 rows=20817 loops=1)
   Buffers: shared hit=13844 read=2189 dirtied=12
   ->  Hash Join  (actual time=12.004..151.882 rows=98422 loops=1)
         Buffers: shared hit=13844 read=2189
 Execution Time: 193.884 ms

shared hit=13844 read=2189 — попадания и промахи буферного пула, локальный hit rate 86%. Если read велик, а Execution Time скачет от прогона к прогону, вы упёрлись не в CPU, а в подъём страниц с диска — и правильный ответ, возможно, не Redis сверху, а shared_buffers побольше. Разбор планов — в «Производительности БД» и в «Индексах и планах запросов».

Агрегат по базе даёт SELECT blks_hit, blks_read FROM pg_stat_database WHERE datname = current_database() — с той же оговоркой про кумулятивность. И с дополнительной: «99% попаданий» здесь ничего не гарантирует, потому что промах страницы, попавшей в page cache ядра, стоит микросекунды, а промах до диска — сотни микросекунд, и pg_stat_database их не различает.

HTTP и CDN

$ curl -sSI https://example.com/assets/app.a91f2c.js | grep -iE 'cache|age|etag|vary'
cache-control: public, max-age=31536000, immutable
age: 84213
etag: "a91f2c-8f21"
x-cache: HIT
vary: Accept-Encoding

age показывает, сколько ответ уже лежит на edge (близко к max-age — значит, скоро протухнет и придёт волна к origin); x-cache: HIT/MISS — попадание конкретного узла; vary — по каким заголовкам размножается ключ. Каждое значение в Vary умножает число вариантов ответа и делит hit rate. Vary: User-Agent — верный способ обнулить кэш CDN: уникальных User-Agent в дикой природе десятки тысяч.

В браузере то же видно в DevTools → Network: колонка Size показывает (disk cache) или (memory cache) вместо размера, а Time при этом нулевое. Фильтр larger-than:100k плюс сортировка по Time быстро находит ресурсы, которые качаются заново на каждой навигации; подробнее — в «Веб-производительности».

Что снимать помимо hit rate

• Латентность попадания и промаха раздельно. Смешанная гистограмма бимодальна, её перцентили не значат ничего. Нужны два таймера с метками result="hit" и result="miss".
• Время заполнения ($T_{\text{fill}}$): если оно сравнимо со стоимостью промаха, кэш почти бесполезен.
• Возраст отданных значений — гистограмма now - created_at. Показывает фактическую свежесть, а не задуманную в TTL. Доля ответов из устаревших значений при stale-while-revalidate — отдельный SLI.
• Вытеснения и распределение TTL. Массовая одновременная экспирация видна как гребёнка на графике expired_keys.
• Размер значений. p99 в 4 МБ означает, что вы гоняете по сети мегабайты и держите кэш занятым на сериализации.

Кривая промахов: сколько памяти нужно на самом деле

«Сколько дать кэшу памяти» почти всегда решают на глаз. Правильный ответ даёт miss ratio curve — зависимость доли промахов от размера кэша, построенная по трассе реальных обращений.

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

Классический способ построения — алгоритм Мэттсона: для стеково-упорядоченных политик (LRU в их числе) одна прогонка трассы даёт результат сразу для всех размеров кэша. Нужна дистанция повторного использования — сколько различных ключей встретилось между двумя обращениями к одному ключу. Обращение попадает в кэш размера $C$ тогда и только тогда, когда эта дистанция меньше $C$. Наивная реализация — $O(n \cdot u)$; практичная, через дерево Фенвика, — $O(n \log n)$. Чтобы это работало на трассах в миллиарды обращений, применяют SHARDS (Waldspurger et al., FAST 2015): пространственное семплирование по хешу. Ключ либо всегда в выборке, либо всегда нет, поэтому дистанции внутри выборки пропорциональны настоящим, и кривая по 1% ключей воспроизводит настоящую с погрешностью порядка процентного пункта при постоянном расходе памяти.

MRC(трасса, доля выборки R):
    fenwick ← пустое дерево над позициями;  last ← {};  hist ← {};  cold ← 0;  t ← 0
    для каждого key из трассы:
        если hash(key) / MAX_HASH ≥ R: продолжить      # ключ вне выборки навсегда
        если key ∈ last:
            d ← число живых меток в fenwick на (last[key], t)   # дистанция
            hist[d] += 1;  fenwick.add(last[key], −1)
        иначе: cold += 1                                # обязательный промах
        fenwick.add(t, +1);  last[key] ← t;  t += 1
    доля промахов для размера S = (cold + Σ hist[d] при d ≥ S·R) / всего

import hashlib

class Fenwick:
    """Дерево Фенвика: префиксная сумма и точечное обновление за O(log n)."""
    def __init__(self, n): self.n, self.t = n, [0] * (n + 1)

    def add(self, i, v):
        i += 1
        while i <= self.n: self.t[i] += v; i += i & -i

    def prefix(self, i):                       # сумма на полуинтервале [0, i)
        s = 0
        while i > 0: s += self.t[i]; i -= i & -i
        return s


def miss_ratio_curve(trace, sizes, rate=0.01):
    """Доля промахов LRU для набора размеров кэша, метод SHARDS.

    trace — ключи из реального лога, sizes — размеры кэша в записях,
    rate — доля семплируемых ключей.
    Время O(n log n), память O(u * rate), где u — число уникальных ключей.
    """
    threshold, keys = int(rate * (1 << 32)), list(trace)
    fen, last, hist = Fenwick(len(keys) + 1), {}, {}
    cold = t = 0
    for key in keys:
        digest = hashlib.blake2b(key.encode(), digest_size=4).digest()
        if int.from_bytes(digest, "big") >= threshold:
            continue                           # не в выборке — и никогда не будет
        if key in last:
            d = fen.prefix(t) - fen.prefix(last[key] + 1)  # различных ключей с прошлого раза
            hist[d] = hist.get(d, 0) + 1
            fen.add(last[key], -1)             # снимаем старую метку
        else:
            cold += 1                          # обязательный промах: ключ виден впервые
        fen.add(t, 1); last[key] = t; t += 1
    total = cold + sum(hist.values())
    return [(s, (cold + sum(c for d, c in hist.items() if d >= s * rate)) / total)
            for s in sizes]

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

Политики вытеснения

Когда память кончилась, кто-то должен уйти. Теоретический предел известен: алгоритм Белади (1966) выбрасывает запись, к которой обратятся позже всех. Он неосуществим — требует знания будущего, — но полезен как верхняя граница: если ваша политика даёт 90%, а Белади на той же трассе 91%, менять политику бессмысленно, надо менять размер или ключи.

Redis не реализует настоящий LRU. Он семплирует maxmemory-samples случайных ключей (по умолчанию 5) и выбрасывает худший. Качество приближения документировано в руководстве по вытеснению: при maxmemory-samples 10 результат почти совпадает с точным LRU при заметно меньших накладных расходах. Если вы упираетесь в вытеснение, это первый параметр, который стоит поднять. И помните: volatile-lru вытесняет только ключи с TTL, поэтому забытый TTL при заполнении памяти означает не вытеснение, а ошибки OOM.

Большинство однократных объектов не заслуживают места. На этом построены W-TinyLFU (TinyLFU: A Highly Efficient Cache Admission Policy) и S3-FIFO (FIFO queues are all you need for cache eviction, SOSP 2023): важна не только политика вытеснения, но и политика допуска — стоит ли класть в кэш объект, который видят впервые. В типичных веб-трассах от половины до 80% объектов запрашиваются ровно один раз, и их допуск вытесняет действительно горячее. Пишете кэш в процессе — берите Caffeine на JVM или Ristretto на Go, а не наивный LRU на связном списке.

Сложность всех перечисленных политик — $O(1)$ амортизированно на операцию (LRU: хеш-таблица плюс двусвязный список; W-TinyLFU добавляет скетч фиксированного размера). Память — $O(C)$ плюс накладные расходы на запись, в Redis порядка 50–100 байт на ключ; при миллионах мелких ключей это становится основной статьёй расхода.

Стратегии чтения и записи

Cache-aside (lazy loading) — рабочая лошадка, 90% случаев. Приложение само проверяет кэш, при промахе читает источник и кладёт результат. Кэш может упасть, и система продолжит работать медленнее; в кэше только реально спрашиваемое. Минусы: каждый холодный ключ стоит промаха, логика размазана по коду, есть гонка при записи. Read-through — то же самое, но внутри кэш-библиотеки (cache.get(key, loader)): логика в одном месте, и большинство таких библиотек уже включают защиту от stampede.

Write-through держит кэш согласованным ценой удвоенной стоимости записи и заполнения данными, которые могут не понадобиться. Разумен при очень высоком отношении чтений к записям. Write-behind даёт огромный выигрыш на записи и батчинг, но при падении узла теряет подтверждённые данные — только там, где потеря допустима: счётчики просмотров, «последний раз онлайн». Refresh-ahead обновляет популярные записи до истечения TTL; по сути это ручная версия вероятностного упреждающего обновления, о котором ниже.

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

Инвалидация: две трудные задачи

TTL — не механизм согласованности, а бюджет рассогласования. Ставя ttl=60, вы декларируете: система имеет право показывать данные до минуты устаревшими. Это продуктовое решение, и его надо проговаривать вслух. Для цен минута может стоить денег, для счётчика лайков — ничего.

Версионирование ключей вместо удаления. Вместо DEL product:8842 пишем ключ как product:v7:8842, где v7 — версия схемы или поколение сущности. Инкремент версии мгновенно делает все старые ключи недостижимыми, а вытеснение уберёт их само. Единственный способ атомарно «инвалидировать» миллион ключей и единственный безопасный способ при выкатке нового формата сериализации.

Теги и surrogate keys. На CDN ответы помечают тегами и делают purge по тегу — изменение одного товара сбрасывает все страницы, где он показывался. Внутри приложения тот же паттерн реализуется обратным индексом «тег → множество ключей», но за размером этих множеств надо следить.

Гонка cache-aside, о которой все узнают на проде

def get_product(pid: int) -> dict:
    key = f"product:v7:{pid}"
    raw = redis.get(key)
    if raw is not None:
        return json.loads(raw)
    row = db.fetch_product(pid)              # (1) прочитали из БД
    redis.set(key, json.dumps(row), ex=300)  # (2) положили в кэш
    return row

def update_product(pid: int, price: int) -> None:
    db.update_price(pid, price)              # (3) записали в БД
    redis.delete(f"product:v7:{pid}")        # (4) убрали из кэша

Выглядит корректно. Но порядок может оказаться таким: читатель выполняет (1) и получает старую цену; писатель выполняет (3) и (4); читатель просыпается и выполняет (2), записывая в кэш значение, прочитанное до обновления. Устаревшая цена лежит в кэше следующие 300 секунд, база права, кэш врёт, и воспроизвести это в тесте почти невозможно.

Что с этим делают:

1. Короткий TTL — не решение, а ограничение ущерба. Обязателен всегда как страховка.
2. Запись с проверкой версии. Храните рядом со значением версию строки (xmin, updated_at, номер ревизии) и обновляйте по принципу «побеждает больший».
3. Аренда (lease), как в memcached у Facebook. При промахе кэш выдаёт читателю токен; запись принимается только с валидным токеном, а инвалидация токен обнуляет. Механизм описан в Scaling Memcache at Facebook (NSDI 2013) — обязательное чтение, если строите кэш всерьёз. Он же решает и stampede.
4. Инвалидация из журнала репликации. Ключ удаляет не приложение, а потребитель CDC-потока: он видит коммит и только после этого сбрасывает кэш, что убирает класс гонок «удалили до коммита». Meta описала похожую систему и её верификацию в Cache made consistent.
5. Отложенное двойное удаление: удалить, записать в базу, удалить снова через задержку больше типичного времени чтения. Костыль, но рабочий, если остальное недоступно.

Вывод: безусловно корректной инвалидации в распределённой системе не бывает — есть только выбор бюджета рассогласования и его измерение. Формальный разбор возможных гарантий — в моделях согласованности.

Cache stampede: как один промах кладёт базу

Stampede (он же dogpile, thundering herd) — ситуация, когда популярный ключ пропадает из кэша и все ждавшие его запросы одновременно идут к источнику.

Арифметика беспощадна. Ключ с частотой 5000 запросов в секунду, пересчёт 200 мс. За время пересчёта промахнутся $5000 \cdot 0.2 = 1000$ запросов, и все они пойдут в базу делать одну и ту же работу. База, рассчитанная на 50 одновременных запросов, ложится; пересчёт замедляется; промахивается ещё больше. Система вошла в положительную обратную связь и не выйдет из неё после устранения исходной причины — это метастабильный отказ, описанный в Metastable Failures in Distributed Systems (HotOS 2021).

Три разных сценария прячутся под одним именем. Одновременное истечение: тысяча ключей записана в один момент (прогрев, деплой, ночной джоб) с одинаковым TTL и протухает тоже одновременно — лечится джиттером, ttl = base + random(0, 0.1 * base). Истечение горячего ключа: один ключ, но очень популярный, джиттер не помогает, нужна координация. Холодный старт: кэш пуст целиком после перезапуска Redis или смены формата ключей — самый опасный случай, бьёт по всем ключам сразу.

Механизм 1: схлопывание запросов

Из всех промахнувшихся к источнику идёт один, остальные ждут его результат. В Go это singleflight:

func (s *Service) Top(ctx context.Context, key string) ([]Item, error) {
    if v, ok := s.cache.Get(ctx, key); ok {
        return v, nil // попадание: быстрый путь без блокировок
    }
    // Все горутины с одинаковым key разделят один вызов fn.
    v, err, _ := s.sf.Do(key, func() (any, error) {
        items, err := s.db.LoadTop(ctx, key)
        if err != nil {
            s.sf.Forget(key) // не залипаем на ошибке: следующая волна попробует снова
            return nil, err
        }
        s.cache.Set(ctx, key, items, jitteredTTL(5*time.Minute))
        return items, nil
    })
    if err != nil {
        return nil, err
    }
    return v.([]Item), nil
}

Тонкости, которые часто упускают. singleflight схлопывает запросы внутри одного процесса: при 40 подах вы получите 40 обращений к базе вместо 1000 — обычно достаточно, но если нет, нужна распределённая блокировка (SET lock:key token NX PX 10000 с освобождением по токену через Lua) либо аренда из подхода Facebook. Ошибка тоже разделяется: упадут все ожидающие. И ожидающие наследуют латентность лидера — если пересчёт занял 4 секунды, все ждали 4 секунды, поэтому у ожидания должен быть собственный таймаут, короче клиентского.

Механизм 2: вероятностное упреждающее обновление

Схлопывание убирает дублирующую работу, но не саму паузу: пока лидер считает, все стоят. Изящнее — не давать ключу протухнуть вовсе: пусть запросы до истечения TTL с растущей вероятностью решают обновить значение заранее. Метод описан в работе Vattani, Chierichetti, Lowenstein Optimal Probabilistic Cache Stampede Prevention (VLDB 2015) и доказуемо оптимален в своём классе. Обновляем, если

$$\text{now} - \delta \cdot \beta \cdot \ln(u) \ge \text{expiry}, \qquad u \sim U(0,1)$$

где $\delta$ — длительность прошлого пересчёта, $\beta$ — агрессивность (по умолчанию 1). Смысл: чем дороже пересчёт, тем раньше начинаются попытки; чем ближе к истечению, тем выше вероятность. Ключ обновляется одним случайным запросом заранее и никогда не бывает отсутствующим.

import math, random, time

def get_with_early_recompute(cache, key, recompute, ttl, beta=1.0):
    """Чтение с вероятностным упреждающим обновлением (XFetch).

    Рядом со значением хранятся delta — длительность прошлого пересчёта —
    и expiry, абсолютный момент логического истечения.
    O(1) дополнительных операций на чтение, +2 поля на запись.
    """
    entry = cache.get(key)
    now = time.monotonic()
    if entry is not None:
        value, delta, expiry = entry
        # log равномерной величины отрицателен, поэтому вычитание сдвигает
        # «текущее время» вперёд тем сильнее, чем дороже был пересчёт.
        if now - delta * beta * math.log(random.random()) < expiry:
            return value                       # рано обновлять — отдаём как есть
    start = time.monotonic()
    value = recompute()                        # сюда попадает один запрос из многих
    delta = time.monotonic() - start
    # Физический TTL длиннее логического: значение остаётся доступным как stale.
    cache.set(key, (value, delta, now + ttl), ttl=ttl * 2)
    return value

Жизненный цикл записи при таком подходе:

Правильная комбинация в проде — все три механизма сразу: джиттер TTL против синхронного истечения, схлопывание против дублирующей работы, упреждающее обновление против пауз. Плюс stale-if-error: если источник недоступен, лучше отдать данные пятиминутной давности, чем 500.

Остальные патологии

Cache penetration. Запросы к несуществующим ключам проходят кэш насквозь и бьют в базу — типично при переборе идентификаторов ботами. Лечится негативным кэшированием: кладите «ничего нет» с коротким TTL (5–30 секунд) как полноценное значение. Для больших пространств ключей добавьте фильтр Блума над множеством существующих: он даёт ложноположительные, но никогда ложноотрицательные, поэтому «нет в фильтре» — надёжный ответ без похода в базу.

Горячий ключ. Один ключ собирает столько трафика, что упирается в сетевую карту одного шарда. Признак — перекос загрузки узлов при равномерном распределении ключей. Решения: реплики значения под ключами key:0..key:N со случайным выбором; локальный кэш в процессе на 1–5 секунд поверх распределённого; вынос значения в конфиг, раздаваемый push-ом.

Крупные значения и загрязнение. Значение в 4 МБ означает 4 МБ по сети на каждое попадание и десятки миллисекунд на сериализацию — в этот момент кэш становится медленнее базы; меряйте p99 размера, крупные объекты держите в объектном хранилище, а в кэше — ссылку. Соседняя беда: ночной аналитический джоб проходит по всем данным, вытесняет горячее множество, и утро начинается с обвала hit rate. Лечится отдельным пулом соединений с флагом «не кэшировать» либо политикой допуска — W-TinyLFU отсеет однократные объекты сам.

Кэш как единая точка отказа. Если при недоступности Redis приложение не отвечает, вы не добавили кэш, а добавили обязательную зависимость. Правильное поведение: короткий таймаут на обращение к кэшу (десятки миллисекунд, не секунды), размыкатель цепи вокруг клиента, деградация в прямой поход к источнику — обязательно с ограничителем нагрузки, чтобы не убить базу. Про размыкатели и ограничители — в паттернах устойчивости.

Холодный старт. Система, живущая на 99% попаданий, после перезапуска кэша получает стократную нагрузку. Меры: раскатывать по одному инстансу с паузой, прогревать перед приёмом трафика, ограничивать конкурентность походов к источнику на время прогрева, для Redis — рассмотреть персистентность. И обязательно проведите учение: выключите кэш на стенде под продовым профилем нагрузки и посмотрите, что произойдёт. Если результат не нравится, у вас не кэш, а необъявленная зависимость.

Как врут бенчмарки кэша

Кэш — рекордсмен по числу способов получить красивое неправильное число. Общие механизмы разобраны в «Бенчмаркинге честно»; здесь — специфика.

Разогрев работает в обе стороны. Прогон с прогретым кэшем измеряет производительность попадания, прогон без прогрева — производительность промаха плюс заполнения. Ни то, ни другое не есть производительность системы: она определяется смесью, а смесь задаётся вашим hit rate. Меряйте оба режима и указывайте, при каком hit rate получен итог.

Равномерные ключи — самая частая ложь. key = "item:" + random(1, 1_000_000) даёт распределение, которого в природе не бывает: при кэше на 100 тысяч записей hit rate составит около 10%, и вы «докажете», что кэш бесполезен. Обратная ошибка — генератор со ста ключами: hit rate 100%, «кэш решает всё». Правда посередине и определяется формой распределения вашего трафика. Берите ключи из настоящего лога либо генерируйте по Ципфу с показателем, оценённым по логу.

// k6: нагрузка с перекошенным по Ципфу распределением ключей.
import http from 'k6/http';
import { Trend, Rate } from 'k6/metrics';

const hitLat = new Trend('latency_hit', true);
const missLat = new Trend('latency_miss', true);
const hitRate = new Rate('cache_hit_rate');

const N = 100000, ALPHA = 1.0;
const cdf = (() => {                        // ключ i выбирается с вероятностью ~1/i^ALPHA
  const c = new Float64Array(N); let acc = 0;
  for (let i = 1; i <= N; i++) { acc += 1 / Math.pow(i, ALPHA); c[i - 1] = acc; }
  for (let i = 0; i < N; i++) c[i] /= acc;
  return c;
})();

function zipfKey() {                        // бинарный поиск по CDF, O(log N)
  const u = Math.random(); let lo = 0, hi = N - 1;
  while (lo < hi) { const m = (lo + hi) >> 1; if (cdf[m] < u) lo = m + 1; else hi = m; }
  return `product:v7:${lo + 1}`;
}

export const options = {
  // Постоянная скорость прибытия, а не постоянное число VU: иначе медленные
  // ответы сами снижают нагрузку и прячут stampede (coordinated omission).
  scenarios: { steady: { executor: 'constant-arrival-rate', rate: 2000,
    timeUnit: '1s', duration: '10m', preAllocatedVUs: 400, maxVUs: 2000 } },
  thresholds: { latency_miss: ['p(99)<800'], cache_hit_rate: ['rate>0.95'] },
};

export default function () {
  const res = http.get(`https://api.example.com/${zipfKey()}`);
  const hit = res.headers['X-Cache'] === 'HIT';
  hitRate.add(hit);
  (hit ? hitLat : missLat).add(res.timings.duration);
}

Ошибка выжившего в двух видах. Первый: вы смотрите на среднюю латентность, которая при hit rate 99% почти целиком состоит из попаданий, и не видите, что промах стоит 900 мс — всегда разделяйте гистограммы hit и miss. Второй, более коварный: запросы, отвалившиеся по таймауту во время stampede, не попадают в статистику успешных, и график латентности улучшается в момент инцидента, потому что выживают только быстрые. Считайте долю ошибок и таймаутов рядом с латентностью, иначе увидите ровно противоположную картину.

Coordinated omission. Нагрузчик с фиксированным числом виртуальных пользователей во время stampede просто перестаёт слать запросы, ожидая ответа, и не измеряет тех, кто в реальности стоял бы в очереди. Единственный корректный режим для проверки кэша — постоянная скорость прибытия (constant-arrival-rate в k6, wrk2 вместо wrk). Иначе вы не увидите стадо, стоя посреди него.

Микробенчмарк библиотеки кэша. «Наш LRU делает 40 миллионов операций в секунду» — одновременно правда и бесполезность. В проде операция сопровождается сериализацией, сетевым RTT и промахом кэша процессора при обходе структуры, а конкуренция за блокировку меняет картину на порядок. Меряйте под конкурентностью и с реальными значениями. И следите за окном: ночью hit rate выше (мало уникальных запросов), днём ниже — сравнивайте одинаковые интервалы суток.

Числа, которые полезно держать в голове

Ниже — типичные порядки величин с важной оговоркой. Знаменитый список «latency numbers every programmer should know» Джеффа Дина датируется примерно 2012 годом; с тех пор NVMe вытеснил SATA, сети стали быстрее, а межконтинентальные задержки не изменились вовсе, потому что упираются в скорость света. Интерактивная версия с поправкой на год — на странице Колина Скотта. Пользуйтесь такими таблицами как картой порядков величин, а не как источником констант: относительные соотношения устойчивы, абсолютные значения устаревают, и задержка до вашего Redis в вашей сети — единственное число, на которое можно опираться в решении.

Практический вывод: сетевой кэш стоит примерно как быстрый запрос к базе. Он окупается, только когда заменяет что-то заметно более дорогое — соединение нескольких таблиц, вычисление, обращение к внешнему API. Замена индексного поиска по первичному ключу на Redis — почти всегда ухудшение.

Чеклист перед добавлением кэша

1. Измерено, что этот путь значим в профиле, а не просто «выглядит тяжёлым».
2. Оценены $T_{\text{miss}}$, $T_{\text{hit}}$, $T_{\text{fill}}$ и точка безубыточности.
3. Ожидаемый hit rate оценён по реальному логу ключей, а не по интуиции.
4. Проверено, что данные не закэшированы уровнем ниже (буферный пул, page cache, CDN).
5. Назван бюджет рассогласования: сколько секунд можно показывать устаревшее и кто это согласовал.
6. Выбрана стратегия инвалидации, разобрана гонка «читатель записал устаревшее».
7. Есть защита от stampede: джиттер плюс схлопывание плюс упреждающее обновление.
8. Есть метрики: hit/miss по классам ключей, раздельные гистограммы латентности, вытеснения, возраст значений, доля stale.
9. Есть таймаут и размыкатель цепи вокруг клиента кэша, деградация проверена учением.
10. Есть план холодного старта: прогрев или ограничение конкурентности при выкатке.

Если не выполнены пункты 1–3, вы не оптимизируете, а гадаете. Если не выполнены 7–10, вы не добавили кэш, а отложили инцидент.

Мини-итог

• Кэш — ставка на повторяемость, и у ставки есть арифметика: точка безубыточности, ускорение $1/(1-h)$, нагрузка на источник $\text{QPS} \cdot (1-h)$. Думайте в промахах и в разах, а не в процентных пунктах попаданий.
• Средний hit rate по инстансу почти бесполезен: разбивайте по классам ключей и считайте по скользящему окну, а не с момента старта процесса. Кривая промахов по реальной трассе превращает спор о размере кэша в измерение.
• Не кэшируйте то, что уже лежит в буферном пуле, и то, что дешевле пересчитать, чем сходить по сети.
• Корректной инвалидации не бывает — бывает названный и измеренный бюджет рассогласования. При записи удаляйте, а не обновляйте.
• Stampede — не редкость, а свойство любого популярного ключа с TTL; джиттер, схлопывание и упреждающее обновление применяются вместе.
• Кэш меняет режимы отказа. Проведите учение с выключенным кэшем: если система не выживает, у вас не кэш, а необъявленная зависимость.
• Бенчмарки кэша врут особенно нагло — через равномерные ключи, разогрев, coordinated omission и ошибку выжившего в хвосте.

Источники

• Brendan Gregg. Systems Performance, 2nd ed., Addison-Wesley, 2020.
• Rajesh Nishtala et al. Scaling Memcache at Facebook, NSDI 2013 — аренда, stale-значения, схлопывание на масштабе.
• Meta Engineering. Cache made consistent, 2022 — измерение и верификация согласованности инвалидации.
• Vattani, Chierichetti, Lowenstein. Optimal Probabilistic Cache Stampede Prevention, VLDB 2015.
• Waldspurger et al. Efficient MRC Construction with SHARDS, FAST 2015.
• Einziger, Friedman, Manes. TinyLFU: A Highly Efficient Cache Admission Policy, 2015; реализация — Caffeine.
• Juncheng Yang et al. FIFO queues are all you need for cache eviction, SOSP 2023.
• Bronson, Aghayev, Charapko, Zhu. Metastable Failures in Distributed Systems, HotOS 2021.
• RFC 9111: HTTP Caching и RFC 5861: stale-while-revalidate, stale-if-error.
• Redis key eviction, Redis client-side caching, golang.org/x/sync/singleflight.
• Смежное на портале: https://courses.digitable.life/post/databases/11-redis/ про сам Redis, https://courses.digitable.life/post/architecture-patterns/08-caching-and-scaling/ про архитектурную сторону, https://courses.digitable.life/post/frontend/14-web-performance/ про кэш в браузере.

Что дальше

Кэш убирает работу, но не убирает дорогу. Даже стопроцентное попадание не спасёт, если до кэша идти через два TLS-рукопожатия и десять последовательных round trip. Следующая статья — про то, как измерять и сокращать саму дорогу: откуда берётся RTT, что даёт keep-alive и мультиплексирование, когда сжатие ускоряет, а когда замедляет, и почему батчинг часто выигрывает больше любой оптимизации кода.

Сетевая производительность: RTT, keep-alive, сжатие, батчинг