Стратегии кэширования: cache-aside, write-through, write-behind и защита от stampede

Коротко

Реализацию вытеснения здесь не разбираем: она есть в статьях про LRU-кэш и LFU-кэш. Эта статья о том, что происходит вокруг кэша в системе.

Сначала считаем

Пусть $h$ — доля попаданий (hit ratio), $R$ — запросов в секунду на чтение. На базу доходит только то, что промахнулось:

$R_{db} = R \cdot (1 - h)$

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

$t = t_{cache} + (1 - h) \cdot t_{db}$

Возьмём 50 000 чтений в секунду, кэш за 1 мс, база за 20 мс:

Падение с 99% до 95% выглядит безобидно: задержка выросла на 0,8 мс. Но нагрузка на базу выросла в пять раз. Если база держит 2 000 запросов в секунду, такое падение её положит.

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

Стенд для примеров

Код ниже запускается без Redis, блоки идут подряд и опираются на импорты предыдущих. Cache — словарь с TTL, Db считает обращения, чтобы эффект было видно в цифрах. Исключение одно: блокировка написана под API клиента Redis.

import threading
import time


class Cache:
    def __init__(self):
        self.store = {}

    def get(self, key):
        item = self.store.get(key)
        if item is None:
            return None
        value, expires_at = item
        if expires_at <= time.monotonic():
            self.store.pop(key, None)
            return None
        return value

    def set(self, key, value, ttl):
        self.store[key] = (value, time.monotonic() + ttl)

    def delete(self, key):
        self.store.pop(key, None)


class Db:
    def __init__(self, rows=None, read_delay=0):
        self.rows = dict(rows or {})
        self.read_delay = read_delay
        self.reads = self.writes = 0
        self.lock = threading.Lock()

    def read(self, key):
        with self.lock:
            self.reads += 1
        time.sleep(self.read_delay)
        return self.rows.get(key)

    def write(self, key, value):
        self.writes += 1
        self.rows[key] = value

Четыре стратегии

Полезно разделить два независимых решения. Как читаем: cache-aside или read-through. Как пишем: удаляем ключ, write-through или write-behind. Обычно их называют одним списком, но комбинировать можно по-разному: read-through с write-through встречается часто, cache-aside с удалением ключа ещё чаще.

Cache-aside

Приложение само управляет кэшем. Промах — идём в базу и кладём результат. Запись — обновляем базу и удаляем ключ.

cache, db = Cache(), Db({"user:1": "Аня"})


def get_user(key):
    value = cache.get(key)
    if value is not None:
        return value
    value = db.read(key)
    if value is not None:
        cache.set(key, value, ttl=300)
    return value


def update_user(key, value):
    db.write(key, value)
    cache.delete(key)


get_user("user:1")
get_user("user:1")
update_user("user:1", "Анна")
print(get_user("user:1"), db.reads)  # Анна 2

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

Две детали, о которых спрашивают.

Почему удаляем, а не обновляем. Два писателя могут записать в базу в порядке A, B, а в кэш в порядке B, A. В базе останется B, в кэше A, и так до конца TTL. Удаление от порядка не зависит: следующий читатель возьмёт актуальное значение.

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

Read-through

На чтении то же самое, но промах обрабатывает сам кэш. Приложение видит только cache.get(key), а загрузчик настроен один раз.

Redis сам в базу ходить не умеет, поэтому read-through чаще живёт в библиотеках или прокси: LoadingCache в Caffeine, proxy_cache в nginx, DAX перед DynamoDB. Плюс не только в чистоте кода. Такой слой знает обо всех промахах сразу и может склеить одновременные загрузки одного ключа: в nginx это включается через proxy_cache_lock.

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

Write-through

Запись идёт через кэш, и он синхронно обновляет базу. Ответ клиент получает, когда обновлено и то и другое.

class ThroughCache:
    def __init__(self, db, ttl):
        self.cache, self.db, self.ttl = Cache(), db, ttl

    def get(self, key):  # read-through
        value = self.cache.get(key)
        if value is None:
            value = self.db.read(key)
            if value is not None:
                self.cache.set(key, value, self.ttl)
        return value

    def put(self, key, value):  # write-through
        self.db.write(key, value)  # база упала — кэш не тронут
        self.cache.set(key, value, self.ttl)


db = Db({"item:7": 100})
store = ThroughCache(db, ttl=300)
store.put("item:7", 120)
print(store.get("item:7"), db.reads)  # 120 0

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

Хороший реальный пример — DAX: его документация описывает именно write-through и честно предупреждает о ловушке. Если другой клиент пишет в DynamoDB мимо DAX, значения расходятся до истечения TTL. Write-through работает, только пока все записи идут через кэш. Для массовой загрузки там же советуют обратное: писать мимо кэша (write-around), чтобы редко читаемые данные не вытесняли полезные.

Write-behind

Он же write-back. Запись подтверждается сразу после обновления кэша, в базу данные уходят позже, пачкой.

class WriteBehind:
    def __init__(self, db):
        self.db = db
        self.data = {}
        self.dirty = set()

    def put(self, key, value):
        self.data[key] = value
        self.dirty.add(key)

    def flush(self):
        for key in self.dirty:
            self.db.write(key, self.data[key])
        self.dirty.clear()


db = Db()
counters = WriteBehind(db)
for views in range(1, 1001):
    counters.put("views:42", views)
counters.put("views:7", 1)
print(db.writes)  # 0

counters.flush()
print(db.writes, db.rows["views:42"])  # 2 1000

1001 подтверждённая запись превратилась в две записи в базу. Но до flush в базе пусто, и падение узла кэша заберёт всё, что клиент считал сохранённым.

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

Есть и менее очевидная проблема: базу теперь могут обновлять только через этот кэш. Прямой UPDATE будет перезаписан следующим сбросом.

Таблица компромиссов

Инвалидация и TTL

Гонка, которую TTL не отменяет

Cache-aside с удалением ключа тоже может закэшировать устаревшее значение. Вот сценарий по шагам:

cache, db = Cache(), Db({"price": 100})

stale = db.read("price")  # читатель получил промах, прочитал и завис

db.write("price", 120)  # писатель обновил базу
cache.delete("price")  # и удалил ключ, которого ещё нет

cache.set("price", stale, ttl=300)  # читатель проснулся

print(cache.get("price"), db.rows["price"])  # 100 120

Окно узкое: чтение должно начаться до записи, а закончиться после удаления. На большой нагрузке оно всё равно случается, и пять минут пользователи видят старую цену.

Facebook решал это арендой (lease), она описана в Scaling Memcache at Facebook. При промахе клиент получает токен, удаление ключа токен отзывает, а записать значение можно только с действующим токеном. Опоздавший читатель из примера выше получил бы отказ.

В Redis аренды из коробки нет. Её можно собрать Lua-скриптом, но чаще держат короткий TTL и мирятся с редкой гонкой. На собеседовании достаточно назвать гонку, оценить её последствия и сказать, чем она закрывается.

Как именно инвалидировать

В той же статье про Memcache демоны mcsqueal читают закоммиченные SQL-запросы и рассылают удаления по кластерам. В обычном проекте аналог — Debezium и очередь.

Отдельный случай — ключи, производные от данных: «топ-10 товаров категории», «лента пользователя». Одно изменение затрагивает неизвестно сколько таких ключей, точечно их не удалить. Здесь спасает только короткий TTL или версия в ключе.

Как выбирать TTL

TTL — страховка на случай, если инвалидация не сработала, и верхняя граница устаревания. Выбирать его стоит от вопроса «сколько бизнес готов показывать старое», а не от желания поднять hit ratio.

Ориентиры условные, но помогают начать разговор: курс валют и остатки на складе — секунды, карточка товара — минуты, справочник городов — часы и дольше, статика с хешем в имени файла — год.

Ещё один нюанс. Если ключи загрузить разом с одинаковым TTL, разом они и истекут. Это случается после прогрева или рестарта, а проявляется через час, когда о рестарте уже забыли. Лечится случайной добавкой к TTL (jitter):

import random
from collections import Counter


def peak_expirations(keys, ttl, jitter):
    moments = Counter(
        int(ttl * random.uniform(1 - jitter, 1 + jitter)) for _ in range(keys)
    )
    return max(moments.values())


random.seed(1)
print(peak_expirations(100_000, 3600, 0))  # 100000
print(peak_expirations(100_000, 3600, 0.1))  # 177

Разброс в 10% снижает пик истечений со 100 000 ключей в секунду примерно до 180.

TTL и вытеснение — разные вещи

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

Как устроены LRU и LFU, разобрано в статье про LRU и статье про LFU. Для интервью хватит трёх фактов о Redis: LRU и LFU там приближённые, на основе случайной выборки ключей; allkeys-lru документация называет хорошим вариантом по умолчанию; а при noeviction запись упрётся в ошибку, как только память кончится.

Thundering herd и cache stampede

Термины часто используют как синонимы. Thundering herd — толпа клиентов, разбуженная одним событием. Cache stampede — её частный случай: популярный ключ истёк, и все запросы одновременно пошли его пересчитывать. Facebook называет thundering herd ещё и ситуацию, когда ключ читают и часто пишут, так что каждая запись снова вызывает волну промахов.

Вот как это выглядит. 100 одновременных запросов, база отвечает за 50 мс:

from concurrent.futures import ThreadPoolExecutor

cache, db = Cache(), Db({"top": "товары"}, read_delay=0.05)


def naive(key):
    value = cache.get(key)
    if value is None:
        value = db.read(key)
        cache.set(key, value, ttl=60)
    return value


def hammer(fn, requests=100):
    with ThreadPoolExecutor(requests) as pool:
        list(pool.map(fn, ["top"] * requests))


hammer(naive)
print(db.reads)  # 100

Сто запросов к базе за один ключ. А если запрос тяжёлый, база замедляется, запросов накапливается ещё больше, и система может не выйти из этого состояния сама.

Защита 1. Single-flight в процессе

В каждом процессе к базе идёт только один поток на ключ, остальные ждут его результат:

cache, db = Cache(), Db({"top": "товары"}, read_delay=0.05)
LOCKS = [threading.Lock() for _ in range(256)]


def single_flight(key):
    value = cache.get(key)
    if value is not None:
        return value
    with LOCKS[hash(key) % len(LOCKS)]:
        value = cache.get(key)  # пока ждали, ключ мог появиться
        if value is None:
            value = db.read(key)
            cache.set(key, value, ttl=60)
    return value


hammer(single_flight)
print(db.reads)  # 1

Было 100, стало 1. Фиксированный массив блокировок не течёт по памяти, в отличие от словаря «ключ → блокировка». Вторая проверка кэша под блокировкой обязательна, без неё следующие потоки просто встанут в очередь к базе.

В Go для этого есть golang.org/x/sync/singleflight. Ограничение одно: это защита внутри процесса. При 50 инстансах в базу придёт до 50 запросов, и для многих систем этого уже достаточно.

Защита 2. Распределённая блокировка

Если даже 50 запросов дорого, блокировку выносят в Redis:

import json
import uuid

RELEASE = """
if redis.call('get', KEYS[1]) == ARGV[1] then
    return redis.call('del', KEYS[1])
end
return 0
"""


def get_with_lock(r, key, load, ttl=300, lock_ttl=5, wait=0.05, attempts=100):
    lock_key, token = f"lock:{key}", uuid.uuid4().hex
    for _ in range(attempts):
        cached = r.get(key)
        if cached is not None:
            return json.loads(cached)
        if r.set(lock_key, token, nx=True, ex=lock_ttl):
            try:
                cached = r.get(key)
                if cached is not None:
                    return json.loads(cached)
                value = load()
                r.set(key, json.dumps(value), ex=ttl)
                return value
            finally:
                r.eval(RELEASE, 1, lock_key, token)
        time.sleep(wait)
    raise TimeoutError(f"не дождались загрузки {key}")

В эмуляции Redis (fakeredis) с 50 потоками load вызвался один раз. Детали, которые стоит проговорить:

• lock_ttl обязателен: упавший держатель не должен блокировать ключ навсегда.
• Освобождаем только свою блокировку, скриптом со сравнением токена. Простой DEL снял бы чужую, если наша уже истекла.
• Документация Redis не рекомендует этот паттерн для настоящих блокировок и советует Redlock. Но у нас блокировка нужна для экономии, а не для корректности: если она сорвётся, база получит два одинаковых запроса, и ничего не сломается. Redlock здесь избыточен.
• При таймауте нельзя молча идти в базу: при большой нагрузке это тот же stampede. Лучше вернуть устаревшее значение или ошибку.

Защита 3. Вероятностное раннее обновление

Блокировки срабатывают, когда ключ уже пропал. Можно обновить его заранее: каждый запрос сам с небольшой вероятностью решает пересчитать значение, и вероятность растёт к моменту истечения. Это XFetch из работы Vattani, Chierichetti, Lowenstein, VLDB 2015. Для него нужно хранить рядом со значением delta, время последнего пересчёта.

import math


def should_refresh(now, expiry, delta, beta=1.0):
    # 1 - random() лежит в (0, 1], поэтому логарифм определён
    return now - delta * beta * math.log(1 - random.random()) >= expiry


def simulate(ttl=60.0, delta=0.5, rps=200):
    """За сколько секунд до истечения начнётся пересчёт и сколько их будет."""
    first, refreshes = None, 0
    for i in range(int(ttl * rps)):
        now = i / rps
        if first is not None and now >= first + delta:
            break
        if should_refresh(now, ttl, delta):
            first = now if first is None else first
            refreshes += 1
    return ttl - first, refreshes


random.seed(7)
runs = [simulate() for _ in range(2000)]
print(round(min(lead for lead, _ in runs), 1))  # 1.0
print(round(sum(lead for lead, _ in runs) / len(runs), 1))  # 2.6
print(round(sum(count for _, count in runs) / len(runs), 1))  # 2.7

При 200 запросах в секунду и пересчёте за 0,5 с первый пересчёт стартует в среднем за 2,6 с до истечения и даже в худшем прогоне успевает закончиться вовремя. К базе за это время уходит около 2,7 запроса, а не 100, и без всякой координации. beta больше 1 сдвигает пересчёт ещё раньше. Цена: ровно один пересчёт не гарантирован, а редко читаемому ключу метод не поможет.

Защита 4. Отдавать старое, пока идёт обновление

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

Пользователь никогда не ждёт базу, и это самое приятное свойство варианта. В HTTP тот же приём описан в RFC 5861:

Cache-Control: max-age=600, stale-while-revalidate=30, stale-if-error=1200

Значение свежее 600 секунд, ещё 30 секунд его можно отдавать, обновляя в фоне, а если источник отвечает ошибками, то ещё 1200 секунд. В nginx похожее поведение даёт proxy_cache_use_stale updating. Для цены в момент оплаты способ, разумеется, не годится.

Какую защиту выбрать

Для масштаба: в статье Facebook аренда с выдачей токена не чаще раза в 10 секунд на ключ снизила пик запросов к базе на проблемных ключах с 17 тысяч до 1,3 тысячи в секунду.

Запросы несуществующих ключей

Родственная проблема — cache penetration. Запрашивают то, чего нет в базе, поэтому кэш никогда не срабатывает, и каждый запрос идёт в базу. Иногда это бот, перебирающий id.

Два средства. Кэшировать отсутствие значения коротким TTL (negative caching, так делает и DAX). Если пространство ключей огромное, перед кэшем ставят фильтр Блума: он дешёво отвечает «такого ключа точно нет».

Горячие ключи

Шардирование размазывает ключи, а не запросы. Если один ключ собирает 200 000 чтений в секунду, все они приходят на один шард, и добавление шардов не поможет. Вирусный пост, распродажа, громкая новость — типичные причины.

Рядом стоит большой ключ, и вместе они особенно опасны: значение на 100 КБ при 20 000 чтений в секунду — это 2 ГБ/с, то есть около 16 Гбит/с трафика на один узел. Сеть закончится раньше процессора.

Как найти. В Redis есть redis-cli --hotkeys, но он работает только с LFU-политикой вытеснения, а частоты у неё приближённые. Надёжнее считать частоты в клиенте по выборке запросов и выгружать топ в метрики.

Локальный кэш. Самое сильное средство. В каждом инстансе приложения держим значение на 1–5 секунд. При 50 инстансах и TTL 1 секунда на ключ в Redis придёт порядка 50 запросов в секунду, а не 200 000. Платим небольшим отставанием и тем, что разные инстансы могут ответить по-разному.

Копии ключа. Значение хранится под несколькими именами, читаем случайную копию, пишем во все:

import hashlib

SHARDS, COPIES = 8, 8


def shard_of(key):
    return int(hashlib.md5(key.encode()).hexdigest(), 16) % SHARDS


def read_key(key):
    return f"{key}#{random.randrange(COPIES)}"


def write_keys(key):
    return [f"{key}#{copy}" for copy in range(COPIES)]


random.seed(1)
requests = 100_000
split = Counter(shard_of(read_key("post:42")) for _ in range(requests))
print(max(split.values()) / requests, len(split))  # 0.37318 5

Здесь вместо 100% самый нагруженный шард получил 37% потока: восемь копий случайно легли на пять шардов из восьми. Важная ловушка: в Redis Cluster нельзя писать копии как {post:42}#1, фигурные скобки задают hash tag и все копии окажутся в одном слоте. Запись теперь стоит COPIES операций, поэтому способ подходит только для ключей, которые редко меняются.

Реплики чтения. Работают, если приложение согласно на их отставание. Масштабируют шард целиком, а не один ключ.

Прогрев. Трафик на старт распродажи известен заранее. Такие ключи заполняют до начала, а не на первом запросе.

Уровни кэша

Цифры дают только порядок и зависят от инфраструктуры.

Каждый уровень снижает нагрузку на следующий, но устаревание складывается. Значение могло попасть в локальный кэш с TTL 5 секунд за миг до истечения в Redis с TTL 300 секунд. В худшем случае читатель увидит данные возрастом 305 секунд, а с CDN ещё больше. На вопрос «как быстро пользователь увидит изменение» нужно отвечать суммой, а не последним TTL.

Локальный кэш можно обновлять быстрее через pub/sub. В Redis начиная с версии 6 есть client-side caching: сервер запоминает, кто какой ключ читал, и сам присылает сообщение об инвалидации.

Когда кэш падает

Вернёмся к таблице в начале: при hit ratio 99% база видит 500 запросов в секунду. Кэш упал или перезапустился пустым, и она получает 50 000. Ни одна защита выше не спасает от этого сама по себе. Что помогает:

• Лимит на обращения к базе. Лишние запросы лучше сразу отклонить, чем дать им положить базу: тогда часть пользователей получит ошибку, а не все сразу.
• Постепенный возврат трафика и прогрев после рестарта. Пустой кэш под полным потоком — та же авария.
• Реплики кэша с автоматическим переключением, чтобы одна упавшая нода не обнуляла долю данных.
• Консистентное хеширование. При hash(key) % N смена числа нод перемешивает почти все ключи, а это массовый промах. При консистентном хешировании перемещается примерно $1/N$ ключей.
• Запасной пул. У Facebook это Gutter: около 1% серверов кластера, которые принимают запросы вместо упавших и хранят значения с коротким TTL.

Как обсуждать кэш на system design интервью

Общий порядок решения задачи разобран в статье про подходы к проектированию систем. Здесь только про кэш, по шагам.

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

2. Посчитайте. Нагрузка на базу при целевом hit ratio и размер кэша. Например: 20 млн товаров, горячие 20%, по 2 КБ на карточку, это 8 ГБ данных. С запасом на накладные расходы около 12 ГБ, с репликой вдвое больше. Цифра не обязана быть точной, важно, что она есть.

3. Назовите стратегию и причину выбора. Не «поставим Redis», а так:

Читаем через cache-aside, TTL 5 минут с 10% jitter. При обновлении цены удаляем ключ. Если удаление не дойдёт, цена в каталоге отстанет максимум на 5 минут, и для каталога это приемлемо. В корзине и при оплате цену берём из базы, мимо кэша.

Самое важное здесь — последнее предложение: видно, что кандидат понимает, где кэш недопустим.

4. Проговорите, что сломается, не дожидаясь вопроса. Устаревшие данные и гонка при заполнении, истечение популярного ключа, горячий ключ, падение кэша. На каждое — одно средство.

5. Добавьте метрики. Hit ratio по типам данных, число вытеснений, задержка, размер значений, нагрузка на базу. Средний hit ratio легко скрывает проблему: 99% по всей системе могут жить вместе с 40% на самом дорогом запросе.

Рассуждать вслух лучше по ходу, а не выдавать готовый итог: об этом есть отдельная статья.

Какие вопросы задают дальше

Логику работы с уточняющими вопросами мы разбирали в этой статье. Для кэша они обычно такие:

Частые ошибки

• Нет maxmemory. Redis будет расти, пока его не убьёт система. Этот лимит — первое, что задают в настройках кэша.
• Неполный ключ. Значение зависит от языка или роли, а ключ нет. В лучшем случае английский текст увидят русские пользователи, в худшем — чужие персональные данные.
• Кэшируется ошибка или таймаут. Сбой базы на секунду превращается в проблему на весь TTL.
• Нет версии формата. Новый код читает старый JSON и падает. Версия в ключе решает проблему при выкатке.
• Один Redis на всё. Кэш и данные, которые нельзя терять, делят память и вытеснение. Их стоит развести.
• Кэш вместо индекса. Сначала чинят медленный запрос, потом кэшируют.

Что запомнить

• Падение hit ratio с 99% до 95% увеличивает нагрузку на базу в пять раз: считайте её, а не среднюю задержку.
• Cache-aside и удаление ключа при записи — стартовый выбор. Write-through нужен для чтения сразу после записи, write-behind — там, где потеря допустима.
• TTL ограничивает устаревание, но не заменяет инвалидацию. Добавляйте к нему jitter.
• От stampede защищают single-flight, ранний пересчёт и отдача устаревшего значения. Блокировка в Redis здесь нужна для экономии, а не для корректности.
• Горячий ключ не лечится добавлением шардов. Лечится локальным кэшем на секунды и копиями ключа.
• Устаревание по уровням складывается, а падение кэша нужно заложить в дизайн заранее.