"There are only two hard things in Computer Science: cache invalidation and naming things." — Phil Karlton

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

В этой главе мы разберём все ключевые аспекты кэширования — от базовых стратегий чтения и записи до распределённых кэш-кластеров, CDN и решения классических проблем вроде thundering herd.

---

1 Зачем нужно кэширование

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

Где кэширование встречается в реальных системах

Кэширование работает на всех уровнях стека:

Для контекста: чтение из PostgreSQL по индексу — порядка 1–5 ms, полный scan таблицы — сотни миллисекунд, запрос к внешнему API — 50–500 ms. Кэш в Redis отдаёт результат за ~1 ms, in-process кэш — за наносекунды.

Когда кэширование оправдано

Кэширование эффективно при выполнении нескольких условий:

1. Высокое соотношение чтений к записям (read-heavy workload). Если данные меняются каждую секунду, кэш придётся постоянно инвалидировать — выигрыш будет минимальным.

2. Дорогая генерация ответа. Если формирование результата требует сложных вычислений, JOIN-ов нескольких таблиц или обращений к внешним сервисам — это кандидат для кэширования.

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

4. Предсказуемые паттерны доступа. Если распределение запросов следует закону Парето (20% данных генерируют 80% трафика), кэш будет эффективен. Если каждый запрос уникален — кэш бесполезен.

---

2 Стратегии кэширования

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

2.1 Cache-Aside (Lazy Loading)

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

Чтение:
1. Приложение → GET key из кэша
2. Если cache hit → вернуть данные
3. Если cache miss → SELECT из БД → SET в кэш → вернуть данные

Запись:
1. Приложение → UPDATE/INSERT в БД
2. Приложение → DELETE key из кэша (или SET новое значение)

def get_user(user_id: str) -> dict:
    # 1. Проверяем кэш
    cached = redis.get(f"user:{user_id}")
    if cached:
        return json.loads(cached)

    # 2. Cache miss — читаем из БД
    user = db.query("SELECT * FROM users WHERE id = %s", user_id)

    # 3. Записываем в кэш с TTL
    redis.setex(f"user:{user_id}", ttl=3600, value=json.dumps(user))

    return user

def update_user(user_id: str, data: dict):
    # 1. Обновляем БД
    db.execute("UPDATE users SET ... WHERE id = %s", user_id)

    # 2. Инвалидируем кэш
    redis.delete(f"user:{user_id}")

Преимущества:

• Приложение имеет полный контроль над тем, что и когда кэшируется
• Кэш заполняется только реально запрашиваемыми данными (no cold data bloat)
• Кэш может быть недоступен — система продолжит работать (деградируя по скорости)

Недостатки:

• Cache miss приводит к тройной задержке: обращение к кэшу + обращение к БД + запись в кэш
• При первом запуске или после сброса кэш холодный — все запросы идут в БД
• Данные в кэше могут устареть (stale data), если другой сервис обновил БД напрямую

Когда использовать: Подходит для большинства случаев. Это стратегия по умолчанию. Используют Netflix (для каталога контента), GitHub (для данных репозиториев), Twitter (для профилей пользователей).

2.2 Read-Through

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

Чтение:
1. Приложение → GET key из кэша
2. Если cache hit → кэш возвращает данные
3. Если cache miss → кэш сам читает из БД → сохраняет у себя → возвращает

Отличие от cache-aside: логика загрузки данных при промахе находится в кэширующем слое, а не в приложении. Приложение не знает, откуда пришли данные — из кэша или из БД.

class ReadThroughCache:
    def __init__(self, redis_client, db, ttl=3600):
        self.redis = redis_client
        self.db = db
        self.ttl = ttl

    def get(self, key: str, loader: Callable) -> dict:
        cached = self.redis.get(key)
        if cached:
            return json.loads(cached)

        # Кэш сам загружает данные
        value = loader()
        self.redis.setex(key, self.ttl, json.dumps(value))
        return value

# Использование — приложение не знает о БД
cache = ReadThroughCache(redis, db)
user = cache.get(f"user:{user_id}", lambda: db.get_user(user_id))

Преимущества:

• Код приложения проще — нет логики взаимодействия с БД при cache miss
• Единообразный интерфейс — приложение всегда работает только с кэшем

Недостатки:

• Кэш становится критической зависимостью — при его падении приложение не может читать данные
• Сложнее в реализации — нужна библиотека или кэширующий proxy с поддержкой custom loaders

Когда использовать: Когда нужно минимизировать связность приложения с хранилищем. Применяется в ORM-фреймворках (Hibernate L2 cache), в AWS DAX (DynamoDB Accelerator).

2.3 Write-Through

При каждой записи данные синхронно записываются и в кэш, и в БД. Кэш всегда содержит актуальную версию данных.

Запись:
1. Приложение → записать данные в кэш
2. Кэш → синхронно записывает в БД
3. Подтверждение записи возвращается приложению

Чтение:
1. Приложение → GET из кэша (всегда cache hit для ранее записанных данных)

class WriteThroughCache:
    def set(self, key: str, value: dict):
        # Записываем в БД синхронно
        self.db.upsert(key, value)
        # Записываем в кэш
        self.redis.setex(key, self.ttl, json.dumps(value))

    def get(self, key: str) -> dict:
        cached = self.redis.get(key)
        if cached:
            return json.loads(cached)
        # Fallback на БД при промахе (например, после рестарта кэша)
        value = self.db.get(key)
        if value:
            self.redis.setex(key, self.ttl, json.dumps(value))
        return value

Преимущества:

• Данные в кэше всегда актуальны — нет stale data
• Чтение после записи (read-your-writes) гарантировано

Недостатки:

• Повышенная латенси записи — каждая запись проходит через два хранилища последовательно
• Кэш заполняется данными, которые могут никогда не быть прочитаны (write waste)
• Если кэш недоступен, запись блокируется

Когда использовать: Когда критична согласованность между кэшем и БД, а объём записей невелик. Применяется в DynamoDB DAX, в банковских системах для кэширования справочников.

2.4 Write-Behind (Write-Back)

Данные записываются только в кэш, а кэш асинхронно (с задержкой) сбрасывает изменения в БД. Это зеркальное отражение read-through.

Запись:
1. Приложение → записать данные в кэш
2. Кэш подтверждает запись (мгновенно)
3. Кэш асинхронно (через буфер/очередь) записывает в БД

Чтение:
1. Приложение → GET из кэша (всегда актуально)

class WriteBehindCache:
    def __init__(self):
        self.write_buffer = deque()  # Буфер отложенных записей

    def set(self, key: str, value: dict):
        # Записываем в кэш мгновенно
        self.redis.set(key, json.dumps(value))
        # Добавляем в буфер для асинхронной записи в БД
        self.write_buffer.append((key, value, time.time()))

    async def flush_to_db(self):
        """Фоновый процесс, записывающий буфер в БД"""
        while True:
            batch = []
            while self.write_buffer and len(batch) < 100:
                batch.append(self.write_buffer.popleft())

            if batch:
                # Пакетная запись в БД
                self.db.bulk_upsert(batch)

            await asyncio.sleep(1)  # Flush каждую секунду

Преимущества:

• Минимальная латенси записи — приложение не ждёт БД
• Возможность батчить записи — вместо 1000 отдельных INSERT можно сделать один bulk INSERT
• Снижение нагрузки на БД

Недостатки:

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

Когда использовать: Когда допустима потеря данных (аналитика, счётчики просмотров) или когда есть механизм восстановления. Facebook использует write-behind для обновления счётчиков лайков — точное число не критично, а батчинг записей экономит тысячи IOPS.

Сравнительная таблица стратегий

На практике стратегии часто комбинируются. Типичная комбинация — cache-aside для чтения + write-through для записи — даёт хороший баланс производительности и консистентности.

---

3 Политики вытеснения (Eviction Policies)

Кэш имеет ограниченный объём памяти. Когда он заполняется, нужно решить, какие данные удалить, чтобы освободить место для новых. Политика вытеснения (eviction policy) определяет этот выбор.

3.1 LRU (Least Recently Used)

Вытесняет элемент, к которому дольше всего не обращались. Основана на предположении, что недавно запрошенные данные будут запрошены снова (temporal locality).

Реализация: Комбинация HashMap (для O(1) поиска) и двусвязного списка (для O(1) перемещения элементов).

from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: str):
        if key not in self.cache:
            return None
        # Перемещаем в конец (most recently used)
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: str, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            # Удаляем первый элемент (least recently used)
            self.cache.popitem(last=False)

Сложность: O(1) для get и put.

Где используется: Redis (по умолчанию allkeys-lru), Memcached, кэш браузера, CPU cache.

Слабость: Уязвим к scan-атаке — однократный проход по большому набору данных (например, массовый экспорт) вытеснит все «горячие» данные. Одно сканирование таблицы может убить весь кэш.

3.2 LFU (Least Frequently Used)

Вытесняет элемент, к которому обращались наименьшее число раз. Учитывает частоту обращений, а не давность.

from collections import defaultdict

class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}           # key -> value
        self.freq = {}            # key -> frequency
        self.freq_to_keys = defaultdict(OrderedDict)  # freq -> {keys}
        self.min_freq = 0

    def get(self, key: str):
        if key not in self.cache:
            return None
        self._increment_freq(key)
        return self.cache[key]

    def put(self, key: str, value):
        if self.capacity <= 0:
            return

        if key in self.cache:
            self.cache[key] = value
            self._increment_freq(key)
            return

        if len(self.cache) >= self.capacity:
            # Удаляем элемент с минимальной частотой (LRU среди них)
            evict_key, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
            del self.cache[evict_key]
            del self.freq[evict_key]

        self.cache[key] = value
        self.freq[key] = 1
        self.freq_to_keys[1][key] = None
        self.min_freq = 1

    def _increment_freq(self, key: str):
        f = self.freq[key]
        self.freq[key] = f + 1
        del self.freq_to_keys[f][key]
        if not self.freq_to_keys[f]:
            del self.freq_to_keys[f]
            if self.min_freq == f:
                self.min_freq = f + 1
        self.freq_to_keys[f + 1][key] = None

Где используется: Redis (политика allkeys-lfu), кэш DNS-серверов.

Слабость: «Исторически популярные» данные накапливают высокий счётчик и могут занимать кэш, даже если перестали быть актуальными. Чтобы бороться с этим, используют decay — периодическое уменьшение счётчиков (Redis делит счётчик пополам каждые N минут).

3.3 FIFO (First In, First Out)

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

Реализация: Обычная очередь (deque).

Где используется: Простые встроенные кэши, кэш конфигурации (данные обновляются редко и равномерно).

Слабость: Не учитывает ни давность, ни частоту обращений. Может вытеснить самый популярный элемент, если он был добавлен давно.

3.4 Другие политики

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

Redis поддерживает 8 политик, которые настраиваются параметром maxmemory-policy:

noeviction        — ошибка при заполнении (по умолчанию)
allkeys-lru       — LRU среди всех ключей
volatile-lru      — LRU среди ключей с TTL
allkeys-lfu       — LFU среди всех ключей
volatile-lfu      — LFU среди ключей с TTL
allkeys-random    — случайный среди всех ключей
volatile-random   — случайный среди ключей с TTL
volatile-ttl      — ключ с наименьшим оставшимся TTL

Практическая рекомендация: Для большинства use cases allkeys-lru — оптимальный выбор. allkeys-lfu лучше, когда есть ярко выраженные «горячие» ключи (например, профили популярных пользователей). volatile-ttl подходит для session store, где каждый ключ имеет TTL.

---

4 Распределённый кэш: Redis Cluster и Memcached

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

4.1 Redis

Redis — это in-memory data store, поддерживающий структуры данных (строки, хэши, списки, множества, sorted sets, streams, HyperLogLog и др.), репликацию, персистентность и кластеризацию.

Архитектура Redis Cluster:

┌──────────────────────────────────────────────┐
│                   Клиент                     │
│         (Smart client / Redis proxy)         │
└───────┬───────────────┬──────────────┬───────┘
        │               │              │
        ▼               ▼              ▼
┌──────────────┐┌──────────────┐┌──────────────┐
│   Master #1  ││   Master #2  ││   Master #3  │
│ Slots 0-5460 ││ Slots 5461-  ││ Slots 10923- │
│              ││    10922     ││    16383     │
│  ┌────────┐  ││  ┌────────┐  ││  ┌────────┐  │
│  │Replica │  ││  │Replica │  ││  │Replica │  │
│  │   1a   │  ││  │   2a   │  ││  │   3a   │  │
│  └────────┘  ││  └────────┘  ││  └────────┘  │
└──────────────┘└──────────────┘└──────────────┘

Redis Cluster делит пространство ключей на 16384 слота (hash slots). Каждый ключ отображается в слот через CRC16: slot = CRC16(key) % 16384. Каждый master-узел отвечает за подмножество слотов.

Ключевые свойства Redis Cluster:

• Автоматическое шардирование — данные распределяются по узлам
• Репликация — каждый master имеет одну или несколько реплик для failover
• Автоматический failover — при падении master реплика автоматически повышается
• Нет multi-key операций между шардами (кроме hash tags: {user:123}:profile и {user:123}:settings попадут в один слот)

Redis Sentinel — альтернатива для случаев, когда не нужно шардирование, но нужен automatic failover:

┌─────────────────────────────────────┐
│        Sentinel #1, #2, #3          │
│   (мониторинг + failover решения)   │
└─────────┬────────────────┬──────────┘
          │                │
          ▼                ▼
    ┌──────────┐      ┌──────────┐
    │  Master  │─────▶│ Replica  │
    └──────────┘      └──────────┘

Персистентность Redis:

• RDB (snapshotting): Периодические снимки всей БД на диск. Быстрый старт, но можно потерять данные между снимками.
• AOF (Append-Only File): Логирование каждой операции записи. Более надёжен, но медленнее при восстановлении.
• Комбинация RDB + AOF: Redis рекомендует использовать оба механизма.

4.2 Memcached

Memcached — простой, высокопроизводительный распределённый кэш типа key-value. В отличие от Redis, Memcached не поддерживает структуры данных, персистентность и репликацию «из коробки».

Архитектура Memcached:

┌──────────────────────────────────────────┐
│                  Клиент                  │
│   (consistent hashing для выбора узла)   │
└───────┬─────────────┬────────────┬───────┘
        │             │            │
        ▼             ▼            ▼
  ┌──────────┐  ┌──────────┐  ┌──────────┐
  │Memcached │  │Memcached │  │Memcached │
  │  Node 1  │  │  Node 2  │  │  Node 3  │
  └──────────┘  └──────────┘  └──────────┘
 (независимые, ничего не знают друг о друге)

Memcached не имеет встроенной кластеризации — узлы полностью независимы. Клиент определяет, на какой узел отправить запрос, используя consistent hashing.

Slab allocator: Memcached использует slab allocator для управления памятью, что минимизирует фрагментацию. Память делится на slab classes разного размера (64B, 128B, 256B...). Элемент попадает в ближайший подходящий slab.

4.3 Redis vs Memcached

Когда выбирать Memcached:

• Простое кэширование string/blob (HTML-фрагменты, сериализованные объекты)
• Многопоточная среда с упором на максимальный throughput простых GET/SET
• Не нужна персистентность или структуры данных

Когда выбирать Redis:

• Нужны структуры данных (sorted set для leaderboard, HLL для unique counts)
• Нужна персистентность или репликация
• Нужен Pub/Sub, Lua scripts или транзакции
• Нужен автоматический failover

На практике Redis доминирует. Facebook — один из немногих, кто по-прежнему масштабно использует Memcached (TAO, кэш social graph), потому что их системы строились до появления Redis Cluster, а переписывать инфраструктуру для сотен миллиардов запросов в день — задача соответствующего масштаба.

---

5 CDN как уровень кэширования

Content Delivery Network (CDN) — это географически распределённая сеть серверов (edge-серверов), которые кэшируют контент ближе к конечным пользователям.

Как работает CDN

Пользователь в Токио                    Origin Server в Вирджинии
        │                                         │
        │  1. DNS → CDN edge (Токио)              │
        ▼                                         │
  ┌──────────────┐                                │
  │   CDN Edge   │  2a. Cache HIT → ответ         │
  │   (Токио)    │──────────────────────────────▶ Пользователь
  │              │                                │
  │              │  2b. Cache MISS                │
  │              │───────────────────────────────▶│
  │              │  3. Origin отвечает            │
  │              │◀───────────────────────────────│
  │              │  4. CDN кэширует + отвечает    │
  │              │──────────────────────────────▶ Пользователь
  └──────────────┘

Типы контента для CDN

Push vs Pull CDN

Pull CDN (origin pull): Edge-сервер запрашивает контент с origin-сервера при первом обращении и кэширует его. Последующие запросы обслуживаются из кэша.

Настройка:
1. DNS CNAME: static.example.com → d123.cloudfront.net
2. Origin: origin.example.com
3. TTL: Cache-Control: public, max-age=86400

Преимущества: простая настройка, нет необходимости заранее загружать контент. Недостаток: первый запрос к каждому edge медленный (cache miss).

Push CDN: Контент загружается на edge-серверы заранее, до первого запроса пользователя.

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

Когда что использовать:

• Pull: большинство случаев (статика сайтов, API-ответы)
• Push: крупные медиафайлы (видео Netflix, обновления игр), контент, где недопустим cold start (прямые трансляции, запуск продуктов)

HTTP-заголовки кэширования

CDN и браузеры используют HTTP-заголовки для управления кэшированием:

# Кэшировать на 1 день на CDN и в браузере
Cache-Control: public, max-age=86400

# Кэшировать на CDN 1 час, в браузере не кэшировать
Cache-Control: s-maxage=3600, max-age=0

# Не кэшировать нигде
Cache-Control: no-store

# Кэшировать, но проверять валидность перед использованием
Cache-Control: no-cache
# (или)
Cache-Control: max-age=0, must-revalidate

# Условная валидация
ETag: "abc123"
Last-Modified: Wed, 21 Oct 2024 07:28:00 GMT

# Immutable — файл никогда не изменится (для версионированных ресурсов)
Cache-Control: public, max-age=31536000, immutable

Стратегия версионирования статики: Файлы с хэшем в имени (app.a1b2c3.js) получают max-age=31536000, immutable. HTML, ссылающийся на них, получает no-cache или короткий TTL. При деплое меняется хэш в имени файла — старый кэшируется вечно, новый подгружается автоматически.

CDN-провайдеры

---

6 Cache Invalidation: проблемы и решения

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

6.1 Способы инвалидации

TTL (Time-To-Live): Самый простой способ. Данные автоматически удаляются из кэша через заданное время.

redis.setex("user:123", 3600, user_data)  # Истекает через 1 час

Плюсы: простота, гарантия, что stale data не живёт вечно. Минусы: данные могут быть устаревшими до истечения TTL; после истечения — cache miss и нагрузка на БД.

Выбор TTL: Это всегда компромисс.

• Короткий TTL (секунды) → актуальные данные, но низкий cache hit ratio
• Длинный TTL (часы/дни) → высокий hit ratio, но stale data

Практическое правило: TTL должен быть достаточно коротким, чтобы stale data не вызывала бизнес-проблем, и достаточно длинным, чтобы кэш был эффективен.

Явное удаление (explicit invalidation):

def update_user(user_id, data):
    db.update_user(user_id, data)
    redis.delete(f"user:{user_id}")  # Инвалидация

Плюсы: данные актуализируются сразу после изменения. Минусы: нужно знать все ключи, связанные с изменёнными данными. Обновление одной записи может потребовать инвалидации десятков кэш-ключей (пользователь, его профиль, лента друзей, поисковый индекс...).

Event-driven инвалидация:

БД (binlog/WAL) → CDC (Debezium) → Kafka → Cache Invalidator → Redis DELETE

Приложение не занимается инвалидацией — отдельный сервис слушает изменения в БД (через Change Data Capture) и автоматически удаляет соответствующие ключи из кэша.

Плюсы: приложение не знает о кэше при записи; работает даже если данные изменены другими сервисами или напрямую в БД. Минусы: задержка (eventual consistency), сложность инфраструктуры.

6.2 Проблема: Delete vs Update

При инвалидации кэша встаёт вопрос: удалять ключ или обновлять его новым значением?

Delete (рекомендуемый подход):

db.update(user_id, new_data)
redis.delete(f"user:{user_id}")

Следующее чтение вызовет cache miss, загрузит свежие данные из БД и положит их в кэш.

Update:

db.update(user_id, new_data)
redis.set(f"user:{user_id}", serialize(new_data))

Почему delete предпочтительнее: при update возникает race condition. Два параллельных запроса могут обновить БД в порядке A→B, но записать в кэш в порядке B→A — и в кэше окажется устаревшее значение.

Время →
Thread 1: DB.update(v=1) ─────────────────── Cache.set(v=1)
Thread 2: ──────── DB.update(v=2) ─ Cache.set(v=2)

Результат в БД: v=2 (правильно)
Результат в кэше: v=1 (STALE! — Thread 1 записал позже)

При delete в кэш не записывается потенциально устаревшее значение. Следующее чтение гарантированно возьмёт актуальные данные из БД.

6.3 Проблема: порядок операций

Даже с delete возможны проблемы с порядком операций.

Вариант 1: Сначала удалить кэш, потом обновить БД (плохо):

Thread 1: Cache.delete ──────────── DB.update(v=2)
Thread 2: ────── Cache.get(MISS) → DB.read(v=1) → Cache.set(v=1)

Результат: БД содержит v=2, кэш содержит v=1 (STALE)

Thread 2 попадает в окно между удалением кэша и обновлением БД, читает старое значение и кладёт его в кэш.

Вариант 2: Сначала обновить БД, потом удалить кэш (лучше):

Thread 1: DB.update(v=2) ──────── Cache.delete
Thread 2: ────── Cache.get(v=1) → ответ v=1

Результат: Thread 2 получил stale ответ, но после delete
           следующие чтения получат v=2 (корректно)

Здесь race condition тоже возможен, но окно очень маленькое и после delete кэш корректен. Это стандартный подход.

Вариант 3: Delayed double delete (для параноидальных случаев):

def update_user(user_id, data):
    redis.delete(f"user:{user_id}")        # 1. Первый delete
    db.update_user(user_id, data)           # 2. Обновляем БД
    time.sleep(0.5)                         # 3. Ждём
    redis.delete(f"user:{user_id}")         # 4. Второй delete

Второй delete через небольшую задержку «подчищает» stale значение, которое мог записать параллельный read. На практике это избыточно для большинства систем — достаточно варианта 2 с TTL как подстраховкой.

6.4 Инвалидация связанных данных

Одно из самых сложных мест. Обновление пользователя может потребовать инвалидации:

• user:123 — профиль
• user:123:posts — список постов пользователя
• feed:456 — лента друга, в которой есть посты пользователя
• search:users:john — результат поиска, содержащий этого пользователя

Подходы:

1. Tag-based invalidation. Каждый кэш-ключ помечается тегами. При изменении сущности инвалидируются все ключи с соответствующим тегом.

cache.set("feed:456", data, tags=["user:123", "user:789"])
cache.set("search:users:john", data, tags=["user:123"])

# При обновлении user:123
cache.invalidate_by_tag("user:123")
# → удалит feed:456 и search:users:john

2. Версионирование. Вместо инвалидации меняем версию ключа. Старые данные остаются, но не находятся.

version = redis.incr("user:123:version")  # 42 → 43
# Ключи строятся с версией: user:123:v43:posts
# Старый ключ user:123:v42:posts больше не запрашивается, удалится по TTL

3. Грубая инвалидация. Просто ставим короткий TTL и не инвалидируем вручную. Допустимо, если stale data в течение нескольких секунд/минут приемлемы.

---

7 Thundering Herd и другие проблемы кэширования

7.1 Thundering Herd (Cache Stampede)

Проблема: Популярный ключ истекает по TTL. Тысячи одновременных запросов обнаруживают cache miss и все идут в БД за одними и теми же данными. БД получает spike нагрузки, который может привести к каскадному отказу.

Время: T0              T1 (TTL expired)          T2
                        │
Запрос 1: ──────────────┤ MISS → DB query ─────→ cache.set()
Запрос 2: ──────────────┤ MISS → DB query ─────→ cache.set()
Запрос 3: ──────────────┤ MISS → DB query ─────→ cache.set()
...
Запрос 1000: ───────────┤ MISS → DB query ─────→ cache.set()

БД: 💥 1000 одинаковых запросов одновременно

Решения:

1. Distributed Lock (Mutex)

Только один запрос при cache miss идёт в БД, остальные ждут.

def get_with_lock(key: str) -> dict:
    value = redis.get(key)
    if value:
        return json.loads(value)

    # Пытаемся захватить lock
    lock_key = f"lock:{key}"
    acquired = redis.set(lock_key, "1", nx=True, ex=5)  # NX = only if not exists

    if acquired:
        try:
            # Мы получили lock — идём в БД
            value = db.query(key)
            redis.setex(key, 3600, json.dumps(value))
            return value
        finally:
            redis.delete(lock_key)
    else:
        # Кто-то другой уже пошёл в БД — ждём и повторяем
        time.sleep(0.05)
        return get_with_lock(key)  # retry

Плюсы: только один запрос к БД. Минусы: остальные запросы ждут (повышенная латенси), deadlock если процесс с lock упадёт (поэтому TTL на lock обязателен).

2. Probabilistic Early Expiration (Stampede Prevention)

Кэш обновляется заранее, до истечения TTL. Каждый запрос с некоторой вероятностью (растущей по мере приближения к TTL) инициирует фоновое обновление.

import math
import random

def get_with_early_recompute(key: str, ttl: int, beta: float = 1.0) -> dict:
    value, expiry = redis.get_with_ttl(key)

    if value is None:
        # Полный miss — обязательно обновляем
        return recompute_and_cache(key, ttl)

    remaining_ttl = expiry - time.time()

    # Вероятность раннего обновления растёт по мере приближения к TTL
    # XFetch алгоритм: delta * beta * log(random()) + expiry
    if remaining_ttl - beta * math.log(random.random()) * 60 <= 0:
        # Фоновое обновление (не блокирует текущий запрос)
        threading.Thread(target=recompute_and_cache, args=(key, ttl)).start()

    return json.loads(value)

Плюсы: нет блокировок, нет spike — обновление происходит плавно до истечения TTL. Минусы: иногда несколько запросов одновременно решат обновить кэш (но это гораздо лучше, чем тысяча).

3. Stale-While-Revalidate

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

def cache_set_with_stale(key: str, value, fresh_ttl: int, stale_ttl: int):
    data = {
        "value": value,
        "fresh_until": time.time() + fresh_ttl,
    }
    redis.setex(key, fresh_ttl + stale_ttl, json.dumps(data))

def cache_get_with_stale(key: str) -> dict:
    raw = redis.get(key)
    if raw is None:
        return None  # Полный miss

    data = json.loads(raw)

    if time.time() < data["fresh_until"]:
        return data["value"]  # Свежие данные

    # Данные stale — отдаём их, но обновляем в фоне
    trigger_background_refresh(key)
    return data["value"]  # Stale, но лучше, чем ждать

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

7.2 Cache Penetration

Проблема: Запросы к данным, которых нет ни в кэше, ни в БД (например, несуществующий user_id). Каждый такой запрос проходит насквозь в БД, потому что cache miss никогда не кэшируется.

GET user:999999999 → cache MISS → DB MISS → ничего не кэшируется
GET user:999999999 → cache MISS → DB MISS → ничего не кэшируется
... (бесконечно, каждый раз нагружая БД)

Это может быть как случайностью (ошибка клиента), так и атакой (перебор несуществующих ID).

Решения:

1. Кэширование «пустых» ответов:

def get_user(user_id: str) -> dict | None:
    cached = redis.get(f"user:{user_id}")
    if cached == "__NULL__":
        return None  # Кэшированный пустой результат
    if cached:
        return json.loads(cached)

    user = db.get_user(user_id)
    if user is None:
        redis.setex(f"user:{user_id}", 300, "__NULL__")  # Короткий TTL!
        return None

    redis.setex(f"user:{user_id}", 3600, json.dumps(user))
    return user

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

2. Bloom Filter:

Bloom filter — вероятностная структура данных, которая может сказать «точно нет» или «возможно да». Размещается перед кэшем и фильтрует заведомо несуществующие ключи.

# При создании пользователя
bloom_filter.add(user_id)

# При запросе
def get_user(user_id: str):
    if not bloom_filter.might_contain(user_id):
        return None  # Точно нет в БД — не запрашиваем ни кэш, ни БД

    # Стандартная логика cache-aside
    ...

Bloom filter на 1 миллиард элементов с false positive rate 1% занимает ~1.2 GB памяти. Это намного дешевле, чем пропускать миллионы бесполезных запросов в БД.

7.3 Cache Breakdown (Hot Key Problem)

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

Решения:

1. Репликация горячих ключей. Хранить копии ключа с суффиксами (hot_key:1, hot_key:2, ..., hot_key:N) и распределять читающие запросы между ними.

def get_hot_key(key: str, replicas: int = 10):
    replica_id = random.randint(0, replicas - 1)
    return redis.get(f"{key}:{replica_id}")

2. Local cache (L1 кэш). Кэширование горячих данных в памяти процесса приложения (Caffeine, Guava Cache), чтобы запросы вообще не доходили до Redis.

from cachetools import TTLCache

local_cache = TTLCache(maxsize=1000, ttl=10)  # 10 секунд

def get_user(user_id: str):
    # L1: in-process cache
    if user_id in local_cache:
        return local_cache[user_id]

    # L2: Redis
    cached = redis.get(f"user:{user_id}")
    if cached:
        user = json.loads(cached)
        local_cache[user_id] = user
        return user

    # L3: Database
    user = db.get_user(user_id)
    redis.setex(f"user:{user_id}", 3600, json.dumps(user))
    local_cache[user_id] = user
    return user

Внимание: Local cache создаёт проблему N копий (по одной на каждый инстанс приложения), которые могут рассинхронизироваться. Используйте очень короткий TTL (5–30 секунд).

7.4 Cache Avalanche

Проблема: Множество ключей истекают одновременно (например, все кэши были прогреты в одно время и имеют одинаковый TTL). Массовый cache miss вызывает волну запросов в БД.

Решения:

1. Jitter (случайное смещение TTL):

import random

base_ttl = 3600  # 1 час
jitter = random.randint(0, 600)  # ±10 минут
redis.setex(key, base_ttl + jitter, value)

2. Разнесение прогрева. При холодном старте не прогревать весь кэш одновременно, а делать это постепенно.

3. Fallback на degraded mode. При всплеске cache miss — ограничивать число одновременных запросов к БД (semaphore/rate limiter) и отдавать stale данные или default response.

---

8 Паттерны кэширования в реальных системах

Facebook: TAO и Memcached

Facebook обслуживает миллиарды запросов в секунду к social graph. Архитектура кэширования:

• Memcached — основной кэш-слой (трилионы запросов в день)
• TAO (The Associations and Objects) — кэширующий слой поверх MySQL для social graph
• Lease-based invalidation — при cache miss выдаётся «lease» (токен). Только владелец lease может записать в кэш, остальные ждут. Это решает thundering herd.
• Региональная репликация — кэш-кластеры в каждом дата-центре, инвалидация через McRouter (proxy для Memcached)

Netflix: EVCache

Netflix разработал EVCache (Ephemeral Volatile Cache) — распределённый кэш поверх Memcached:

• Данные реплицируются между availability zones
• Чтение идёт из локальной зоны (низкая латенси)
• Запись идёт во все зоны (консистентность)
• Используется для кэширования метаданных контента, данных пользователей, результатов рекомендательной системы

Twitter: Manhattan + Redis

Twitter использует комбинацию:

• Manhattan — собственное key-value хранилище для персистентных данных
• Redis — кэш для таймлайнов (fanout-on-write: при публикации твита он записывается в кэш таймлайна каждого подписчика)
• Twemproxy — прокси для шардирования Redis/Memcached

---

9 Практические рекомендации

Чек-лист при проектировании кэширования

1. Определите, что кэшировать. Не всё стоит кэшировать. Начните с самых «дорогих» и частых запросов. Профилируйте: какие запросы к БД самые медленные и частые?

2. Выберите стратегию. Для большинства случаев — cache-aside с TTL. Если нужна строгая консистентность — write-through.

3. Определите TTL. Начните с консервативного значения (минуты), мониторьте hit ratio, постепенно увеличивайте.

4. Добавьте jitter к TTL. Всегда. TTL = base_ttl + random(0, base_ttl * 0.1).

5. Защитите от thundering herd. Используйте lock или stale-while-revalidate для горячих ключей.

6. Защитите от cache penetration. Кэшируйте «пустые» ответы или используйте Bloom filter.

7. Планируйте мониторинг. Ключевые метрики:

   • Hit ratio — целевое значение > 90% (для прогретого кэша)
   • Latency (p50, p99) — Redis обычно < 1ms на p99
   • Eviction rate — если высокий, нужно больше памяти
   • Memory usage — для планирования capacity

8. Продумайте прогрев кэша. После деплоя или рестарта кэш холодный. Варианты: постепенный прогрев (lazy loading), предварительный прогрев из БД (batch load), канареечный деплой (новые инстансы получают малый трафик, пока кэш прогреется).

9. Используйте многоуровневый кэш. L1 (in-process, TTL=секунды) → L2 (Redis, TTL=минуты/часы) → L3 (CDN для статики).

---

10 Вопросы для самопроверки

1. Вы проектируете систему профилей пользователей с 50M DAU. 95% запросов — чтение профилей, 5% — обновление. Какую стратегию кэширования вы выберете и почему?

2. В Redis Cluster один из master-узлов получает в 10 раз больше запросов, чем остальные (hot key). Как вы решите эту проблему?

3. Объясните, почему при инвалидации кэша рекомендуется удалять ключ (delete), а не обновлять его (update). Приведите пример race condition.

4. Ваша система использует cache-aside с TTL=1 час. После деплоя новой версии нужно инвалидировать кэш 10 миллионов ключей. Какие подходы вы рассмотрите?

5. Чем отличается cache penetration от cache avalanche? Предложите решения для каждой проблемы.

6. Вы используете CDN для кэширования API-ответов. Один из ответов содержит персонализированные данные (имя пользователя). Как вы предотвратите кэширование персонализированного контента на CDN?

7. Сравните LRU и LFU. Приведите сценарий, в котором LRU работает лучше LFU, и наоборот.

8. Вашей команде нужно выбрать между Redis и Memcached для кэширования HTML-фрагментов (размер ~10KB). Нагрузка — 500K RPS. Какой выбор вы порекомендуете и почему?

9. Как реализовать кэширование с гарантией read-your-writes consistency?

10. Опишите архитектуру многоуровневого кэша (L1/L2/CDN) для e-commerce каталога. Какие trade-offs вы видите?

---

11 Дополнительные ресурсы

Papers

• Scaling Memcache at Facebook (Nishtala et al., 2013) — как Facebook обслуживает миллиарды запросов через Memcached. Подробно описывает lease-based invalidation, regional replication и thundering herd protection.
• An Analysis of Facebook Photo Caching (Huang et al., 2013) — паттерны кэширования фотографий и эффективность CDN.
• Dynamo: Amazon's Highly Available Key-value Store (DeCandia et al., 2007) — consistent hashing и реплицированное хранилище, на котором базируется DynamoDB.
• XFetch: A Lightweight Approach for Avoiding Thundering Herds — алгоритм probabilistic early expiration.

Блоги

• Redis Documentation (redis.io/docs) — исчерпывающая документация с примерами для каждой структуры данных и команды.
• Cloudflare Blog (blog.cloudflare.com) — регулярные статьи об оптимизации CDN, кэшировании на edge и борьбе с thundering herd.
• Netflix Tech Blog: EVCache — описание распределённого кэша Netflix.
• How Facebook Live-Streams to 800,000 Simultaneous Viewers — CDN и кэширование для live-video.

Talks

• "Scaling Redis at Twitter" (Yao Yu, Strange Loop) — практический опыт использования Redis для кэширования таймлайнов в Twitter.
• "Caching at Netflix: The Hidden Microservice" (Scott Mansfield, QCon) — архитектура EVCache и паттерны кэширования в Netflix.
• "TAO: Facebook's Distributed Data Store for the Social Graph" (Nathan Bronson, USENIX ATC) — архитектура кэширующего слоя Facebook.