Инвалидация кеша, возможно, одна из самых запутанных вещей в программировании. Тонкость вопроса состоит в компромиссе между полнотой, избыточностью и сложностью этой процедуры. Так о чём же эта статья? Хотелось бы не привязываясь к какой-либо платформе, языку или фреймворку, подумать о том как следует реализовывать систему инвалидации. Ну а чтобы не писать обо всём и ни о чём, сконцентрируемся на кешировании результатов SQL-запросов построенных с помощью ORM, которые в наше время встречаются нередко.
Начнём всё же с общих соображений не специфичных ни для SQL-запросов, ни для ORM. Упомянутые полноту и избыточность я определяю следующим образом. Полнота инвалидации — это её характеристика, определяющая насколько часто и в каких случаях может/будет возникать ситуация когда в кеше будут содержаться грязные данные и как долго они там будут оставаться. Избыточностью, в свою очередь, назовём то как часто кеш будет инвалидироваться без необходимости.
Рассмотрим для примера распространённый способ инвалидации по времени. С одной стороны, он практически гарантирует, что сразу после изменения данных кеш грязен. С другой стороны, время которое кеш остаётся грязным, мы можем легко ограничить уменьшив время жизни (что в свою очередь сократит процент попаданий). Т.е. при сокращении времени жизни кеша полнота инвалидации улучшается, а избыточность ухудшается. В итоге, чтобы достигнуть идеальной полноты инвалидации (никаких грязных данных) мы должны выставить таймаут в 0, или, другими словами, отключить кеш. Во многих случаях временное устаревание данных в кеше допустимо. Например, как правило, не так уж и страшно если новость в блоке последних новостей появится там на несколько минут позже или общее количество пользователей вашей социальной сети будет указано с ошибкой в пару-тройку тысяч.
Способ с инвалидацией по времени хорош своей простотой, однако, не всегда применим. Что ж, можно сбрасывать кеш при изменении данных. Одной из проблем при таком подходе является то, что при добавлении нового запроса, который мы кешируем приходиться добавлять код для его инвалидации в при изменении данных. Если мы используем ORM, то данные изменяются (в хорошем случае) в одном месте — при сохранении модели. Наличие одного центрального кода изменения данных облегчает задачу, однако, при большом количестве разнообразных запросов приходиться всё время дописывать туда всё новые и новые строки сброса различных кусочков кеша. Таким образом, мы получаем на свою голову избыточную связность кода. Пора её ослабить.
Воспользуемся событиями — ORM при сохранении/удалении модели будет события генерировать, а мы при кешировании чего-либо будем тут же и вешать обработчик на соответствующее событие, удаляющий это что-либо из кеша. Всё отлично, однако, написание большого количества похожих обработчиков утомляет, плюс логика приложения зарастает логикой кеширования/инвалидации как свинья жиром.
Вспомним, что у нас есть ORM, а для него каждый запрос представляет не просто текст, а определённую структуру — модели, дерево условий и прочее. Так что, по идее, ORM может и кешировать и вешать инвалидационные обработчики прямо при кешировании по мере надобности. Чертовски привлекательное решение для ленивых ребят, вроде меня.
Небольшой пример. Допустим мы выполняем запрос:
В реальности в инвалидаторах удобнее хранить списки ключей кеша, а не тексты запросов, тексты здесь для наглядности.
Посмотрим, что будет происходить при добавлении объекта. Мы должны пройти по всему списку инвалидаторов и стереть ключи кеша для условий, выполняющихся для добавленного объекта. Но инвалидаторов может быть много, и храниться они должны там же где сам кеш, т.е. скорее всего не в памяти процесса и загружать их все каждый раз не хотелось бы, да и последовательная проверка всех условий больно долга.
Очевидно, нужно как-то группировать и отсеивать инвалидаторы без их полной проверки. Заметим, что картина когда условия различаются только значениями. Например, инвалидаторы в модели post все имеют вид category_id=? and published=?.. Сгруппируем инвалидаторы из примера по схемам:
Обратим внимание на условие category_id=? and published=?, зная значения полей добавляемого поста, мы можем однозначно заполнить метки "?". Если объект:
Однако, что делать с более сложными условиями? В отдельных случаях кое-что можно сделать: or разложить на два инвалидатора, in развернуть в or. В остальных случаях либо придётся всё усложнить, либо сделать инвалидацию избыточной, отбросив такие условия. Приведём то, какими будут инвалидаторы для foo после таких преобразований:
Таким образом, нам нужно для каждой модели только хранить схемы (просто списки полей), по которым при надобности мы строим инвалидаторы и запрашиваем списки ключей, которые следует стереть.
Приведу пример процедуры инвалидации для foo. Пусть мы запросили из базы объект
Я старался по-возможности абстрагироваться от языка и платформы, однако, рабочая и работающая в довольно нагруженном проекте система тоже существует. Подробнее о ней и о хитростях реализации вообще в следующей статье.
Полнота и избыточность
Начнём всё же с общих соображений не специфичных ни для SQL-запросов, ни для ORM. Упомянутые полноту и избыточность я определяю следующим образом. Полнота инвалидации — это её характеристика, определяющая насколько часто и в каких случаях может/будет возникать ситуация когда в кеше будут содержаться грязные данные и как долго они там будут оставаться. Избыточностью, в свою очередь, назовём то как часто кеш будет инвалидироваться без необходимости.
Рассмотрим для примера распространённый способ инвалидации по времени. С одной стороны, он практически гарантирует, что сразу после изменения данных кеш грязен. С другой стороны, время которое кеш остаётся грязным, мы можем легко ограничить уменьшив время жизни (что в свою очередь сократит процент попаданий). Т.е. при сокращении времени жизни кеша полнота инвалидации улучшается, а избыточность ухудшается. В итоге, чтобы достигнуть идеальной полноты инвалидации (никаких грязных данных) мы должны выставить таймаут в 0, или, другими словами, отключить кеш. Во многих случаях временное устаревание данных в кеше допустимо. Например, как правило, не так уж и страшно если новость в блоке последних новостей появится там на несколько минут позже или общее количество пользователей вашей социальной сети будет указано с ошибкой в пару-тройку тысяч.
Инвалидация по событию
Способ с инвалидацией по времени хорош своей простотой, однако, не всегда применим. Что ж, можно сбрасывать кеш при изменении данных. Одной из проблем при таком подходе является то, что при добавлении нового запроса, который мы кешируем приходиться добавлять код для его инвалидации в при изменении данных. Если мы используем ORM, то данные изменяются (в хорошем случае) в одном месте — при сохранении модели. Наличие одного центрального кода изменения данных облегчает задачу, однако, при большом количестве разнообразных запросов приходиться всё время дописывать туда всё новые и новые строки сброса различных кусочков кеша. Таким образом, мы получаем на свою голову избыточную связность кода. Пора её ослабить.
Воспользуемся событиями — ORM при сохранении/удалении модели будет события генерировать, а мы при кешировании чего-либо будем тут же и вешать обработчик на соответствующее событие, удаляющий это что-либо из кеша. Всё отлично, однако, написание большого количества похожих обработчиков утомляет, плюс логика приложения зарастает логикой кеширования/инвалидации как свинья жиром.
Автоматическая инвалидация ORM-запросов
Вспомним, что у нас есть ORM, а для него каждый запрос представляет не просто текст, а определённую структуру — модели, дерево условий и прочее. Так что, по идее, ORM может и кешировать и вешать инвалидационные обработчики прямо при кешировании по мере надобности. Чертовски привлекательное решение для ленивых ребят, вроде меня.
Небольшой пример. Допустим мы выполняем запрос:
select * from post where category_id=2 and published
category_id=2 and published=true. Через некоторое время для каждой модели образуются списки инвалидаторов, каждый из которых хранит список запросов, которые должен сбрасывать:post:
category_id=2 and published=true:
select * from post where category_id=2 and published
select count(*) from post where category_id=2 and published
select * from post where category_id=2 and published limit 20
category_id=3 and published=true:
select * from post where category_id=3 and published limit 20 offset 20
category_id=3 and published=false:
select count(*) from post where category_id=3 and not published
foo:
a=1 or b=10:
or_sql
a in (2,3) and b=10:
in_sql
a>1 and b=10:
gt_sql
В реальности в инвалидаторах удобнее хранить списки ключей кеша, а не тексты запросов, тексты здесь для наглядности.
Посмотрим, что будет происходить при добавлении объекта. Мы должны пройти по всему списку инвалидаторов и стереть ключи кеша для условий, выполняющихся для добавленного объекта. Но инвалидаторов может быть много, и храниться они должны там же где сам кеш, т.е. скорее всего не в памяти процесса и загружать их все каждый раз не хотелось бы, да и последовательная проверка всех условий больно долга.
Очевидно, нужно как-то группировать и отсеивать инвалидаторы без их полной проверки. Заметим, что картина когда условия различаются только значениями. Например, инвалидаторы в модели post все имеют вид category_id=? and published=?.. Сгруппируем инвалидаторы из примера по схемам:
post:
category_id=? and published=?:
2, true:
select * from post where category_id=2 and published
select count(*) from post where category_id=2 and published
select * from post where category_id=2 and published limit 20
3, true:
select * from post where category_id=3 and published limit 20 offset 20
3, false:
select count(*) from post where category_id=3 and not published
foo:
a=? or b=?:
1, 10:
or_sql
a in ? and b=?:
(2,3), 10:
in_sql
a > ? and b=?:
1, 10:
gt_sql
Обратим внимание на условие category_id=? and published=?, зная значения полей добавляемого поста, мы можем однозначно заполнить метки "?". Если объект:
{id: 42, title: "…", content: "…", category_id: 2, published: true}
Однако, что делать с более сложными условиями? В отдельных случаях кое-что можно сделать: or разложить на два инвалидатора, in развернуть в or. В остальных случаях либо придётся всё усложнить, либо сделать инвалидацию избыточной, отбросив такие условия. Приведём то, какими будут инвалидаторы для foo после таких преобразований:
foo:
a = ?:
1: or_sql
b = ?:
10: or_sql, gt_sql
a = ? and b = ?:
2, 10: in_sql
3, 10: in_sql
Таким образом, нам нужно для каждой модели только хранить схемы (просто списки полей), по которым при надобности мы строим инвалидаторы и запрашиваем списки ключей, которые следует стереть.
Приведу пример процедуры инвалидации для foo. Пусть мы запросили из базы объект
{id: 42, a: 1, b: 10}
сменили значение a на 2 и записали обратно. При обновлении процедуру инвалидации следует прогонять и для старого, и для нового состояния объекта. Итак, инвалидаторы для старого состояния: a=1, b=10, a=1 and b=10, соответствующие ключи or_sql и gt_sql (последний инвалидатор отсутсвует, можно считать пустым). Для нового состояния получаем инвалидаторы a=2, b=10, a=2 and b=10, что добавляет ключ in_sql. В итоге стираются все 3 запроса.Реализация
Я старался по-возможности абстрагироваться от языка и платформы, однако, рабочая и работающая в довольно нагруженном проекте система тоже существует. Подробнее о ней и о хитростях реализации вообще в следующей статье.