Детализированные стратегии кэширования динамических запросов

Сегодня я хотел бы поговорить о стратегиях кэширования для совокупных запросов к часто обновляемым данным, основанным на времени. На предыдущем месте работы я провел немало «мозговых циклов» и с удовольствием поделюсь некоторыми своими находками.

Пример данных и сценарий использования

Допустим, у нас есть таблица реляционной базы данных, содержащая финансовые операции:



Таблица имеет вторичный упорядоченный индекс по столбцу date таким образом, что можно быстро запросить фрагмент дат (т. е. ... WHERE date BETWEEN '2023-05-24' AND '2023-05-31'). Предположим, что таблица состоит из достаточного количества строк, так, что SELECT SUM(amount) FROM transactions работает медленно.

Требования к схеме доступа для этой таблицы следующие:

1. Мутации (т. е. вставки, обновления и удаления) могут происходить с любой из строк. То есть таблица предназначена не только для добавления данных.
2. Мутации происходят чаще, чем запросы.
3. Клиенты заинтересованы в суммировании подмножества транзакций с помощью пользовательских фильтров, динамически генерируемых из веб-интерфейса. Фильтровать можно по следующим параметрам:
   a) теги, суммы и описания.
   b) по диапазонам дат.
4. Клиенты ожидают, что последовательные запросы будут возвращаться быстро.

Реализация

Оказалось, что вышеупомянутое требование — удивительно трудно решаемая задача! Мне нравится немного упрощать инженерные задачи, чтобы понять, что на самом деле является сложным, поэтому давайте построим решение с нуля и при этом упростим некоторые моменты:

Неизменяемые данные

Пока предположим, что таблица неизменяема (т. е. мутации недопустимы). Так что же не так с простым построением запроса SELECT к неизменяемым данным? Оказывается, запрос к ним выполняется слишком медленно (требование 4). Классический способ решить эту проблему — добавить слой кэширования* перед базой данных. Мы используем SQL-запрос в качестве ключа кэша и возвращаем кэшированное значение, если оно существует — в противном случае выполняем дорогостоящий запрос к базе данных.

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

Встроенные мутации и отсутствие разбиения

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

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

Стоит отметить, что если бы транзакции были привязаны к userId, то, по крайней мере, мы могли бы инвалидировать ключи кэша лишь для конкретного пользователя. Некоторые кэши (посмотрите на Redis) поддерживают перебор ключей кэша, но большинство — нет. В любом случае это будет дорогостоящая операция. Обходной путь для этого — начать работать с хэшированием. Если мы введем новую таблицу cache_invalidation_token, сопоставляющую userId с некоторым случайным одноразовым номером (nonce), который обновляется каждый раз, когда мы изменяем финансовую транзакцию пользователя (в рамках одной и той же транзакции базы данных), мы сможем использовать HASH(sql) XOR NONCE(userId) в качестве ключа поиска в кэше. Обновляя nonce-номер при каждой записи, мы неявно инвалидируем все результаты SQL. Отлично!

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

Разбиение по дате

Проблема с вышеописанным подходом заключается в том, что каждая инвалидация кэша требует повторного прохода по всем данным пользователя. Можем ли мы сделать лучше? Обычно да, и здесь все становится интереснее. Мы можем сделать более тонкую процедуру инвалидации кэша по дате. Разделив наши кэшированные результаты SQL по дате, например, по месяцу, мы можем инвалидировать только определенные фрагменты наших данных. Позвольте мне объяснить:
Для простоты давайте просто проигнорируем поле userId и предположим, что мы всегда фильтруем по нему и учитываем его при выполнении поиска из кэша. Если вместо этого мы определим отображение cache_invalidation_tokens как (year, month) => nonce, то запрос

SELECT SUM(amount) FROM transactions WHERE description='Netflix' AND date BETWEEN '2023-01-01' AND '2023-06-01'

выполнит пять операций поиска в кэше и, возможно, пять SQL-запросов:

SELECT SUM(amount) FROM transactions WHERE description='Netflix' AND date BETWEEN '2023-01-01' AND '2023-02-01';
SELECT SUM(amount) FROM transactions WHERE description='Netflix' AND date BETWEEN '2023-02-01' AND '2023-03-01';
SELECT SUM(amount) FROM transactions WHERE description='Netflix' AND date BETWEEN '2023-03-01' AND '2023-04-01';
SELECT SUM(amount) FROM transactions WHERE description='Netflix' AND date BETWEEN '2023-04-01' AND '2023-05-01';
SELECT SUM(amount) FROM transactions WHERE description='Netflix' AND date BETWEEN '2023-05-01' AND '2023-06-01';

Каждый SQL-запрос сначала проверяет, существует ли ключ кэша HASH(sql) XOR NONCE(year, month). Затем следует дополнительный запрос к основной таблице на промах кэша. Наконец, все результаты суммируются до конечного значения SUM(amount). Далее, при каждой мутации необходимо обновить случайный одноразовый номер для (year, month) (как и раньше, либо в транзакции базы данных, либо в кэше).

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

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

Дополнительно: Предварительное заполнение горячего кэша

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

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

Дополнительно: 2-фазный поиск и иерархическое разбиение по датам

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

SELECT SUM(amount) FROM transactions WHERE date BETWEEN '2023-01-05' AND '2023-04-15'

То есть

SELECT SUM(amount) FROM transactions WHERE description='Netflix' AND date BETWEEN '2023-01-05' AND '2023-02-01';
SELECT SUM(amount) FROM transactions WHERE description='Netflix' AND date BETWEEN '2023-02-01' AND '2023-03-01';
SELECT SUM(amount) FROM transactions WHERE description='Netflix' AND date BETWEEN '2023-03-01' AND '2023-04-01';
SELECT SUM(amount) FROM transactions WHERE description='Netflix' AND date BETWEEN '2023-04-01' AND '2023-04-15';

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

Еще одной проблемой может стать запрос:

SELECT SUM(amount) FROM transactions WHERE date BETWEEN '2000-01-01' AND '2023-01-01'

Две описанные выше проблемы можно решить двумя разными подходами:

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

SELECT SUM(amount) FROM transactions WHERE (date BETWEEN '2000-01-01' AND '2015-01-01') OR (date BETWEEN '2017-01-01' AND '2023-01-01')

Это определенно уменьшит количество запросов к базе данных, но не к кэшу cache_invalidation_tokens!

Чтобы меньше тратить кэш, можно использовать иерархическое разбиение по датам, где несы вводятся для разных гранулярностей разбиения по датам. Например, NONCE(userId, year), NONCE(userId, month), и NONCE(userId, day). Мутация финансовой транзакции с датой 2013-08-03 для пользователя X приведет к аннулированию кэша для ключей (X, 2013), (X, 2013-08), и (X, 2013-08-03). Приведенная выше логика запросов усложнится, но по возможности лучше выполнять запросы в следующем порядке:

1. раздел года из кэша.
2. раздел месяца из кэша.
3. раздел дня из кэша.
4. SQL-запрос к реляционным первичным данным.

Иерархический подход позволяет сократить количество обращений к реляционной базе данных, но при этом увеличивает количество записей в cache_invalidation_tokens, а также объем хранилища, необходимого для этого.

Заключение

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

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

Дополнение I: О соотношении между чтением и записью а также о кэшировании

Обычно вычислительные системы классифицируют по соотношению чтения и записи: у них высокое или низкое соотношение чтения и записи. Соотношение высокое, если чтений больше, чем записей. Оно низкое, если записей больше, чем чтений.

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

Однажды я услышал, как кто-то сказал что-то вроде

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

Это действительно так! Если я правильно помню, эта цитата была приведена кем-то при рассказе о паттерне разделения ответственности на команды и запросы (CQRS). Это паттерн, при котором система явно подразделяется на две части. Одна часть отвечает за запись (валидация и обеспечение согласованности данных), а другая часть, отвечает за операции чтения.

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

Иерархический подход, основанный на датах, хорош тем, что позволяет гибко подходить к оптимизации чтения и записи, не превращаясь в решение «или-или».

Добавление II: Об общих упорядоченных данных

Эта статья была написана на основе записей таблицы с датами. Ничто не мешает использовать более общий подход к разбиению столбцов других типов!