Кэширование в информатике¶

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

¶Принцип работы

Кэширование строится на трёх базовых операциях: чтение (lookup), запись (write) и инвалидация (eviction/invalidation). При обращении к данным система сначала проверяет, присутствует ли запрошенный объект в кэше. При совпадении (hit) данные возвращаются из кэша без обращения к источнику — медленному носителю, удалённому серверу или вычислительному ядру. При отсутствии (miss) выполняется обращение к источнику, после чего результат сохраняется в кэше для последующих запросов.

Ключевые характеристики кэша:

• Размер — объём хранимых данных, определяемый аппаратными или программными ограничениями.
• Политика вытеснения — алгоритм выбора объекта, который удаляется при заполнении кэша (LRU, LFU, FIFO, Random).
• Время жизни (TTL) — период, после которого запись считается устаревшей и подлежит обновлению.
• Коэффициент попаданий (hit rate) — доля запросов, обслуженных из кэша, — основной показатель эффективности.

¶Уровни кэширования

Кэши организуются на разных уровнях вычислительной системы, от аппаратных регистров до распределённых сетевых систем:

Чем выше уровень, тем меньше задержка, но и тем меньше объём доступного кэша.

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

При заполнении кэша необходимо решать, какой объект удалить. Основные политики:

• LRU (Least Recently Used) — вытесняется объект, к которому дольше всего не обращались. Наиболее распространённая политика, хорошо работает при временной локальности.
• LFU (Least Frequently Used) — вытесняется объект с наименьшей частотой обращений. Требует подсчёта счётчиков использования.
• FIFO (First In First Out) — вытесняется самый старый объект, независимо от частоты обращений.
• ARC, LIRS, 2Q — адаптивные и гибридные политики, сочетающие преимущества LRU и LFU.

¶Кэширование в процессорах

Современные процессоры используют многоуровневый кэш (L1, L2, L3). L1-кэш разделён на инструкционный (L1i) и данных (L1d), работает на частоте ядра и имеет ёмкость 32–80 КБ на ядро. L2 объединяет оба типа и достигает нескольких МБ. L3 (LLC — Last Level Cache) общий для всех ядер и может достигать десятков МБ. При промахе в L3 процессор обращается к оперативной памяти, что увеличивает задержку в десятки раз. Ключевые проблемы кэширования на этом уровне — когерентность кэшей в многопроцессорных системах (протоколы MESI, MOESI) и ложные промахи, вызванные конфликтами адресов.

¶Кэширование в вебе и сетях

В веб-архитектуре кэширование реализуется на уровне HTTP: заголовки Cache-Control, ETag, Last-Modified, Expires определяют, как долго и при каких условиях ресурс может храниться в кэше браузера, промежуточного прокси или CDN. Различают:

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

Для динамического контента применяется кэширование страниц (page caching) и фрагментов (fragment caching) в веб-фреймворках.

¶Кэширование в базах данных

СУБД используют буферный пул для хранения прочитанных страниц. Дополнительно применяются результаты запросов (query cache), материализованные представления и индексные структуры. Главная проблема — согласованность кэша с источником данных. Решается инвалидацией по событию (event-driven invalidation), вытеснением по времени (TTL) или стратегиями write-through и write-back, определяющими, когда изменения записываются в основное хранилище.

¶Недостатки

Кэширование вносит дополнительную сложность в систему. Возникают проблемы когерентности, когда кэш содержит устаревшие данные, «громадные промахи» (thundering herd), когда множество клиентов одновременно запрашивают отсутствующий объект, и увеличение потребления памяти. Некорректная инвалидация приводит к рассинхронизации, поэтому в распределённых системах применяются стратегии cache-aside, read-through, write-through и write-behind.

¶Применение

Кэширование применяется повсеместно: в браузерах (кэш ресурсов), в DNS (кэш разрешения имён), в операционных системах (кэш файловой системы), в СУБД, в веб-серверах, в распределённых системах (Redis, Memcached, Hazelcast), в аппаратных процессорах. Правильно настроенное кэширование снижает нагрузку на источники данных и уменьшает время отклика в разы и более.

Источники:

• Таненбаум Э., Бос Х. Современные операционные системы
• Стоунбрейкер М. и др. Database Systems
• RFC 9111 — HTTP Caching
• Hennessy Дж., Паттерсон Д. Архитектура компьютера