К вопросу об инвалидации кеша

Suor 2 июня 2011 в 18:23 13,2k
Инвалидация кеша, возможно, одна из самых запутанных вещей в программировании. Тонкость вопроса состоит в компромиссе между полнотой, избыточностью и сложностью этой процедуры. Так о чём же эта статья? Хотелось бы не привязываясь к какой-либо платформе, языку или фреймворку, подумать о том как следует реализовывать систему инвалидации. Ну а чтобы не писать обо всём и ни о чём, сконцентрируемся на кешировании результатов SQL-запросов построенных с помощью ORM, которые в наше время встречаются нередко.

Полнота и избыточность

Начнём всё же с общих соображений не специфичных ни для 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,3and b=10:
        in_sql
    a>1 and b=10
        gt_sql
и т.д.
В реальности в инвалидаторах удобнее хранить списки ключей кеша, а не тексты запросов, тексты здесь для наглядности.

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

Очевидно, нужно как-то группировать и отсеивать инвалидаторы без их полной проверки. Заметим, что картина когда условия различаются только значениями. Например, инвалидаторы в модели post все имеют вид category_id=? and published=?.. Сгруппируем инвалидаторы из примера по схемам:
post:
    category_id=? and published=?:
        2true:
            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
        3true:
            select * from post where category_id=3 and published limit 20 offset 20
        3false:
            select count(*from post where category_id=3 and not published 
foo:
    a=? or b=?:
        110:
            or_sql
    a in ? and b=?:
        (2,3), 10:
            in_sql
    a > ? and b=?:
        110:
            gt_sql

Обратим внимание на условие category_id=? and published=?, зная значения полей добавляемого поста, мы можем однозначно заполнить метки "?". Если объект:
{id: 42, title: "…", content: "…", category_id: 2, published: true}
, то единственный подходящий инвалидатор из семейства будет category_id=2 and published=true и, следовательно нужно стереть соответствующие ему 3 ключа кеша. Т.е. не требуется последовательная проверка условий мы сразу получаем нужный инвалидатор по схеме и данным объекта.

Однако, что делать с более сложными условиями? В отдельных случаях кое-что можно сделать: or разложить на два инвалидатора, in развернуть в or. В остальных случаях либо придётся всё усложнить, либо сделать инвалидацию избыточной, отбросив такие условия. Приведём то, какими будут инвалидаторы для foo после таких преобразований:
foo:
    a = ?:
        1: or_sql
    b = ?:
        10: or_sql, gt_sql
    a = ? and b = ?:
        210: in_sql
        310: 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 запроса.

Реализация

Я старался по-возможности абстрагироваться от языка и платформы, однако, рабочая и работающая в довольно нагруженном проекте система тоже существует. Подробнее о ней и о хитростях реализации вообще в следующей статье.
Проголосовать:
+25
Сохранить: