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

    Инвалидация кеша, возможно, одна из самых запутанных вещей в программировании. Тонкость вопроса состоит в компромиссе между полнотой, избыточностью и сложностью этой процедуры. Так о чём же эта статья? Хотелось бы не привязываясь к какой-либо платформе, языку или фреймворку, подумать о том как следует реализовывать систему инвалидации. Ну а чтобы не писать обо всём и ни о чём, сконцентрируемся на кешировании результатов 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 запроса.

    Реализация

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

    Подробнее
    Реклама
    Комментарии 15
    • –5
      эх, глядя на название думал что будет описана структура и особенности кэша процессора.
      • +7
        Погадаю на сабжах топиков. Очищу карму тролля. Предскажу рейтинг комментария.

        Потомственная хабрагадалка
      • 0
        К примеру у нас есть таблица posts
        и по этой таблице строится N сущностей, «в порядке добавления», «не прочитанное», «популярное», «отклоненное», «Новое», «отмодеренное»…

        Получается что у нас есть N коллекций (возможно) одних и тех самых данных и при изменении/удалении/добавлении данных из таблицы posts нам необходимо вызвать инвалидатор у каждой из этих сущностей?
        Причем если это апдейт — то вызовов будет N*2

        Как то не очень эффективно, как мне кажеться. Возможно я вас просто не правильно понял.

        • 0
          Видимо, неправильно, потому как не надо. Напишите свой пример в терминах sql и я напишу как он будет инвалидироваться.
          • +1
            1. select * from posts order by time_added
            2. select post.* left join post_readed where user_id=1 and post_readed.post_id=posts.id from posts where post_readed.id is null
            3. select posts.* inner join post_rating where post_rating.post_id=posts.id from posts order by post_rating.rating desc
            4. select * from posts where status=«rejected»
            5. select * from posts where status=«new»
            6. select * from posts where status=«accepted»

            и тут происходит апдейт:
            update posts set title=«new title», status=«accepted», time_added=time() where id=105

            Прощу прощение если где-то опечатался в названиях таблиц или полей. Суть я думаю будет ясна.

            Спасибо.
            • 0
              Для краткости буду обозначать запросы q1,...,q6.

              Очевидно, q1 должен инвалидироваться при любом изменении в таблице, ему будет соответствовать инвалидатор с пустой схемой (схема — список полей). q2 и q3 содержат join-ы, как их обрабатывать я в статье не упоминал. Можно огрод городить, но на данный момент я просто игнорирую условия на приджойненные таблицы, т.е. такие запросы могут инвалидироваться чаще, чем необходимо. q4,q5,q6 — запросы с простым условием равенства поля, как раз то, с чем описанная система справляется лучше всего.

              Вот набор инвалидаторов, который формируется после выполнения q1-q6:
              ""-- (пустая схема)
                  q1, q3
              user_id = ?:
                  1: q2
              status = ?:
                  "rejected": q4
                  "new": q5
                  "accepted": q6

              Теперь происходит обновление строки, при обновлении важны все колонки, а не только те, которые меняются, причём необходимо знать и старое и новое состояния объекта/ряда. Приходиться перед update-ом и delete-ом выбирать ряд, за всё приходится платить (впрочем ORM может делать это и так, чтобы удалять/обновлять зависимые объекты, например).

              Итак мы выбираем объект
              {id: 105, user_id: 2, title: "old title", status: "new", time_added: "..."}
              и обновляем его до
              {id: 105, user_id: 2, title: "new title", status: "accepted", time_added: "..."}

              Подставляем старый объект в схемы, получаем "", user_id=2, status="new", подставляем новый, получаем "", user_id=2, status="accepted". Собирая всё вместе, видим что надо сбросить q1,q3,q5 и q6.
            • 0
              Извиняюсь что не написал это в предыдущем посте.
              Также интересует в каком виде вы храните данные в кеше? В виде массива с данными чтото типа {id: 42, a: 1, b: 10}?
              И как быть с большими наборами данных, а также с постраничным кешерованием (я подразумеваю что хранится данные должны блоками с определенным количеством элементов, и если оно будет хранится блоками то и инвалидировать нужно все эти блоки)?
              Ибо выходит что бы поднять, например, 20 первых записей нужно подымать кеш и десиарелизировать 100000 элементов, а то и больше…

              Спасибо.
              • 0
                Данные выдаются из кеша в том же виде, что выдаёт ORM в том случае если кеш не используется, таким образом кеширование прозрачно для пользователя ORM-а, ему собственно всё равно откуда пришли данные из кеши или из базы. Обычно это модели или списки моделей, но могут быть и словари/хеши/просто списки.

                Кешируется то, что запрашивается, т.е. если вы пользователь ORM-а запрашивает всё сразу, то и в кеш ляжет 100000 записей, если постранично, то будет ложиться отдельными блоками с одними и теми же инвалидаторами, ну и в случае чего сброшены будут все вместе.
          • 0
            Гугл что-то не показывает толковых ссылок на тему, объясняющую что такое, собственно «инвалидатор».
            • 0
              инвалидация — процесс удаления кеша, когда он «протухает». можно, как и написано, удалять его по истечении какого-то времени, либо при каких-то событиях.

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

              — если страница тяжелая, то каждый первый человек после инвалидации будет натыкаться на страницу без кеша. можно ведь как-нибудь при инвалидации перед сжиганием кеша делать новый и подменять, чтобы всегда и все попадали на кеш?
              • 0
                1. С количеством комментариев возможно много вариантов:
                — счётчик денормализуется и храниться в посте, минус — новые посты будут часто менятся и стираться из кеша.
                — счётчик будет получаться для каждого поста на странице отдельным запросом
                select count(*from comment where post_id = <post_id>;
                такие запросы будут инвалидироваться только тогда когда надо, сами посты будут инвалидироваться независимо, т.е. значительно реже, чем в первом случае. Минус много запросов, но если они, как правило, будут браться из кеша, то это нормально.
                — вариация на тему, считать комментарии сразу для всех постов на странице:
                select post_id, count(*from comment 
                where post_id in (<post_id1><post_id2>, ...) group by 1;
                Минусы — такие запросы будут чаще инвалидироваться, чем в предыдущем варианте, более сложная реализация и промахи при изменении списка постов на странице.

                2. Если сбросить весь кеш, то первый человек получит лаг, ничего не поделаешь. Но кеш обычно весь не сбрасывается, тяжёлая страница делает много запросов, которые инвалидируются по разным условиям.
              • 0
                Грубо говоря, инвалидатор — что-то, что инвалидирует, или помогает инвалидировать.

                Я инвалидаторами называю структуры {условие на модель} -> {список ключей, которые нужно сбросить при выполнении условия}, описанные в статье.
              • 0
                самая быстрая инвалидация кэша =)

                net/ipv4/route.c:823

                /*
                * Perturbation of rt_genid by a small quantity [1..256]
                * Using 8 bits of shuffling ensure we can call rt_cache_invalidate()
                * many times (2^24) without giving recent rt_genid.
                * Jenkins hash is strong enough that litle changes of rt_genid are OK.
                */
                static void rt_cache_invalidate(struct net *net)
                {
                unsigned char shuffle;

                get_random_bytes(&shuffle, sizeof(shuffle));
                atomic_add(shuffle + 1U, &net->ipv4.rt_genid);
                }
                • +1
                  Пока не совсем понятно что к чему, жду продолжения и примеров реализации! Интересно.
                  • 0
                    Вы меня извините, но я не могу понять:
                    1. Абстрагируемся от конкретной реализации движка СУБД и ее языка.
                    2. При этом, можем утверждать, что при «category_id=? and published=?» «не требуется последовательная проверка условий».

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

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.