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

Однако реализация кэша сопряжена с рядом сложностей. Например, нужно решать, какие данные хранить, как долго их держать в кэше и когда удалять устаревшую информацию. Ошибки в управлении кэшем могут приводить к устаревшим / несогласованным данным, или даже к более долгому времени получения ответа, чем без применения кэша. Также важно учитывать ограничения памяти, ведь хранение слишком большого объема данных может привести к излишнему расходу ресурсов и снижению производительности.

Терминология

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

• cache miss - "промах кэша". Сценарий, когда запрошенный ключ не был найден в кэше

• cache hit - "попадание в кэш". Сценарий, когда запрошенный ключ был найден в кэше

• hit ratio - % попаданий запросов в кэш. Характеризует эффективность кэширования.

• горячий ключ - ключ, на который приходится бОльшая часть запросов

• прогрев кэша - процесс наполнения кэша данными. Зачастую кэш прогревается либо при запуске системы заранее известными наиболее часто запрашиваемыми данными, либо по мере запросов(при частых или даже при первом cache miss)

• инвалидация - удаление / обновление информации из кэша. Например, если в кэше находилось значение balance = 100$, а мы получили запрос на запись в базу balance = 400$, то очевидно что после успешной записи нам необходимо инвалидировать это значение в кэше

При необходимости и наличии нужных метрик, можно вычислить математически, будет ли эффективен кэш вовсе в вашем сценарии:

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

Разновидности кэша

Итак, какие же существуют разновидности кэша? Это зависит от критерия классификации.

По расположению в архитектуре систему кэши разделяют на 2 вида - внутренний и внешний кэш.

Внутренний кэш или in-memory cache находится в оперативной памяти нашего приложения. Внешний же кэш располагается как ни странно на стороннем сервере, представляющим собой такое же back-end приложение, либо более частый сценарий - одно из готовых решений по типу Redis, Tarantool и др.

Преимущества внутреннего кэша:

1. Высокая скорость записи / чтения данных (из-за отсутствия сетевых запросов)

2. Вытекает из п1 - отсутствие расходов на сериализацию / десериализацию данных

Недостатки внутреннего кэша:

1. Сложное, а иногда невозможное горизонтальное масштабирование

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

Преимущества внешнего кэша:

1. Простое горизонтальное масштабирование

2. Вытекает из п1 - возможно хранение большого объема данных

3. При падении нашего сервиса - данные кэша не теряются

4. Простой прогрев кэша и инвалидация данных

Недостатки внешнего кэша:

1. Скорость работы (из-за сетевых запросов)

Теперь предлагаю посмотреть на кэш немного под другим углом, и дифференцировать его не по размещению в нашей системе, а по способам взаимодействия с ним.

В данной парадигме мы можем вычленить 3 типа кэша - Cache Aside, Cache Through и Cache Ahead. Давайте о каждом по порядку:

1. Cache Aside (Кэш на стороне)

При данной стратегии наше приложение само координирует запросы в кэш и в БД.

2. Cache through (Сквозное кэширование)

Все запросы приложения проходят через кэш

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

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

3. Cache Ahead (Опережающее кэширование)

Данная стратегия кэширования предписывает, что все запросы на чтение всегда адресуются только в кэш, никогда не попадая в базу данных. Способы инвалидации варьируются, и выбираются уже основываясь на конкретном кейсе. Например, можно инвалидировать кэш при записи в БД. Либо же авто-подгружать данные самостоятельно раз в какой-то период времени.

Алгоритмы вытеснения

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

Так уж вышло, что безграничных ресурсов не существует, и проектируя какую-либо систему или отдельный компонент по типу кэша, мы всегда должны учитывать ресурсы, доступные нам в употребление. Сейчас не важен конкретный размер кэша, 10 или 1,000,000 записей, важно то, что он ограничен. То есть на длинном промежутке времени, при использовании нашего приложения, рано или поздно мы неизбежно столкнемся с ситуацией, где весь доступный кэш заполнен, и для записи новой информации в него, нужно удалить какую либо из существующих. Как же решить какая именно запись должна быть удалена? Именно на этот вопрос и дает нам ответ выбранный алгоритм вытеснения.

Для начала давайте взглянем на тривиальные алгоритмы вытеснения

Random

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

FIFO (First-In, First-Out)

Метод вытеснения FIFO работает по принципу «первым пришёл — первым ушёл». Это значит, что при заполнении кэша новая запись вытесняет самую старую, независимо от её актуальности. Такой подход хорошо подходит для простых сценариев, где важна предсказуемость работы кэша, а не оптимальная частота обращений к данным. Например, в малонагруженных системах или при кэшировании данных с естественным порядком устаревания, FIFO может стать отличным выбором благодаря своей очевидной и лёгкой реализации.

LIFO (Last In, First Out)

Метод вытеснения кэша LIFO основывается на принципе удаления самой последней добавленной записи, независимо от её востребованности. Это может показаться нелогичным, ведь свежие данные обычно более актуальны, но в сценариях с жестко ограниченной памятью или временными буферами такой подход может быть оправдан. Например, если кэш используется как стек для временного хранения промежуточных данных, то простота реализации и скорость работы LIFO могут перевесить его очевидные недостатки.

Но зачастую, данных алгоритмов не будет хватать, чтобы давать реальный профит на поле боя. Простота их разработки имеет обратную сторону - высокий cache miss. Чтобы лучше предсказывать какие записи стоит оставить, а какие можно удалить, существуют алгоритмы посложнее, которые проверены временем и заслужено стали незаменимой классикой, надстройки над которыми лежат в основе любого реального проекта.

Итак, 3 наших кита - LRU, MRU и LFU. Давайте по порядку:

LRU (Least Recently Used)

LRU — это алгоритм, удаляющий из кэша данные, которые не запрашивались дольше всего. Представь, что у тебя есть 5 последних вкладок в браузере, а ты открываешь шестую. Если места больше нет, то закроется та вкладка, которой ты пользовался давно, а не та, которую открыл минуту назад. Такой подход эффективен в ситуациях, когда данные, использованные недавно, с высокой вероятностью понадобятся снова, например, при кэшировании запросов в базе данных или изображений на сайте.

Применение LRU оправдано в системах, где старые данные теряют актуальность по мере времени. Например, в веб-сервере, хранящем в кэше страницы, которые чаще посещают, или в мобильных приложениях, где ресурсы ограничены, и нужно держать в памяти только самое важное.

MRU (Most Recently Used)

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

MRU полезен в системах, где частый доступ к одним и тем же данным маловероятен. Например, в потоковой обработке данных, где свежие записи постоянно заменяются новыми, или в мультимедиа-кэшах, где последний воспроизведенный файл можно удалить первым, так как он вряд ли будет проигрываться сразу снова. Такой подход особенно полезен в задачах с одноразовым доступом к данным.

LFU (Least Frequently Used)

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

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

Хочется упомянуть утопичный алгоритм Белади, который к сожалению нереализуем, но полезно о нем знать для общего развития:

Алгоритм Белади (Belady's Optimal Algorithm)

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

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

Advanced алгоритмы

Указанные выше 3 алгоритма довольно просты, и имеют также свои недостатки. В реальных проектах используются намного более сложные алгоритмы, которые являются многократными надстройками над данными китами. Их рассмотрение выходит за рамки данной статьи, но при желании, вы можете найти интересующую вас информацию по каждому из них. Вот наиболее известные алгоритмы: Second Chance, Clock, 2Q, SLRU(Segmented LRU), TLRU(Time aware LRU), LRU-K.