llmdocsсправочник разработчика

Кэш (вычисления)

Материал из llmdocs — справочник разработчика
Портал: Основы CS
Кэш (вычисления)
Назначениеускорить повторный доступ к данным за счёт их копии в быстром хранилище
Метрикадоля попаданий (hit ratio)
Политики вытесненияLRU, LFU, FIFO, TTL, ARC, W-TinyLFU
Стратегии записиwrite-through, write-back, write-around
Уровнирегистры → L1/L2/L3 → ОЗУ → страничный кэш → диск → сеть
Прикладные кэшиRedis, Memcached, Varnish, CDN, HTTP-кэш браузера

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

Иерархия памяти

Кэширование работает потому, что программы обладают локальностью: недавно использованные данные скорее всего понадобятся снова (временная локальность), а соседние с ними — тоже (пространственная).[1] Порядки задержек сильно различаются:[7]

Уровень Типичная задержка
Кэш L1 процессора ~1 нс
Кэш L2 / L3 ~4 / ~40 нс
Оперативная память ~100 нс
Чтение с NVMe SSD ~20–100 мкс
Запрос в пределах дата-центра ~0,5 мс
Запрос через континент ~50–150 мс

Процессор читает память строками кэша по 64 байта, поэтому последовательный проход по массиву многократно быстрее «прыжков» по связному списку, хотя асимптотика обоих — O(n) (см. Алгоритм и O-нотация). Операционная система держит недавно прочитанные блоки файлов в страничном кэше — поэтому свободная память в Linux почти всегда «занята» под buff/cache, и это нормально.

Где кэшируют в приложениях

  • Мемоизация функций — запоминание результата для одинаковых аргументов:[4]
from functools import lru_cache

@lru_cache(maxsize=1024)
def get_rate(currency: str) -> float:
    return fetch_from_api(currency)      # медленный внешний вызов
  • Кэш перед базой данных — Redis или Memcached хранят результаты частых запросов, сессии, счётчики.
  • HTTP-кэш — браузер, обратный прокси и CDN сохраняют ответы по правилам заголовков Cache-Control, ETag, Last-Modified (RFC 9111).[2][3]
Cache-Control: public, max-age=31536000, immutable    # статика с хешем в имени
Cache-Control: no-cache                                # хранить, но проверять каждый раз
ETag: "33a64df5"                                       # клиент спросит If-None-Match → 304
  • Кэши сборки — слои Docker-образов, кэш зависимостей в CI/CD, __pycache__, кэш компилятора.
  • Кэш в LLM — KV-кэш внимания при генерации и кэширование промптов у API-провайдеров.

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

  • Cache-aside (ленивая загрузка) — самая распространённая: приложение ищет в кэше, при промахе читает из БД и кладёт результат в кэш с TTL.[6]
def get_user(uid):
    if (cached := redis.get(f"user:{uid}")) is not None:
        return json.loads(cached)
    user = db.fetch_user(uid)
    redis.set(f"user:{uid}", json.dumps(user), ex=300)   # TTL 5 минут
    return user
  • Write-through — запись идёт одновременно в кэш и в источник; данные согласованы, запись медленнее.
  • Write-back — запись сначала только в кэш, в источник позже; быстро, но при сбое данные могут потеряться (так работают кэши процессора и дисков).
  • Write-around — запись мимо кэша, он заполняется только при чтении.

Вытеснение

Кэш ограничен, поэтому при заполнении нужно решать, что выбросить:

  • LRU (least recently used) — дольше всего не использовавшийся элемент; классическая реализация — хеш-таблица плюс двусвязный список, обе операции за O(1);
  • LFU — используемый реже всего;
  • FIFO, случайное вытеснение;
  • TTL — элемент истекает по времени;
  • адаптивные алгоритмы — ARC, W-TinyLFU (библиотеки Caffeine, Ristretto).

В Redis политика задаётся параметром maxmemory-policy, например allkeys-lru или volatile-ttl.[5]

Инвалидация и типовые проблемы

Известная шутка Фила Карлтона: «В информатике есть только две сложные вещи — инвалидация кэша и придумывание имён». Главные трудности:

  • Устаревшие данные — источник изменился, а кэш отдаёт старое. Решения: короткий TTL, явное удаление ключа при изменении, версии в ключах (user:42:v7), хеш содержимого в имени файла для статики.
  • Лавина промахов (cache stampede) — популярный ключ истёк, и тысячи запросов одновременно идут в БД. Помогают блокировка на перестроение, ранний случайный перерасчёт и устаревшие ответы на время обновления (stale-while-revalidate).
  • Холодный старт — после перезапуска кэш пуст, нагрузка на источник резко растёт.
  • Кэширование персональных данных — ответ одного пользователя, ошибочно закэшированный общим кэшем, увидят другие; для таких ответов нужен Cache-Control: private или no-store.
  • Согласованность между несколькими кэшами и экземплярами приложения — требует распределённых механизмов инвалидации.

Кэш — оптимизация, а не источник истины: система должна работать корректно (пусть и медленнее), если кэш пуст или недоступен.

См. также

Источники

  1. Hennessy, Patterson — Computer Architecture: A Quantitative Approach (6th ed.), ch. 2 Memory Hierarchy
  2. RFC 9111 — HTTP Caching
  3. MDN — HTTP caching
  4. Python — functools.lru_cache and functools.cache
  5. Redis — Key eviction
  6. AWS — Caching best practices
  7. Peter Norvig — Latency numbers every programmer should know
Категории: