инвалидация в программировании что это
Каскадная инвалидация кэша. Часть 1
Вот уже несколько лет, как почти каждая статья о передовых подходах к кэшированию рекомендует пользоваться в продакшне следующими методиками:
Все известные мне средства для сборки проектов поддерживают добавление к именам файлов хэша их содержимого. Делается это с помощью простого конфигурационного правила (наподобие того, что показано ниже):
Столь широкая поддержка этой технологии привела к тому, что подобная практика стала чрезвычайно распространённой.
Эксперты в сфере производительности веб-проектов, кроме того, рекомендуют пользоваться методиками разделения кода. Эти методики позволяют разбивать JavaScript-код на отдельные бандлы. Такие бандлы могут быть загружены браузером параллельно, или даже лишь тогда, когда в них возникнет необходимость, по запросу браузера.
Одним из многих преимуществ разделения кода, в частности, имеющих отношение к передовым методикам кэширования, называют то, что изменения, внесённые в отдельный файл с исходным кодом, не приводят к инвалидации кэша всего бандла. Другими словами, если для npm-пакета, созданного разработчиком «X», вышло обновление безопасности, и при этом содержимое node_modules разбито на фрагменты по разработчикам, то изменить придётся только фрагмент, содержащий пакеты, созданные «X».
Проблема тут заключается в том, что если всё это скомбинировать, то подобное редко приводит к повышению эффективности долговременного кэширования данных.
На практике изменения одного из файлов исходного кода почти всегда приводят к инвалидации более чем одного выходного файла системы сборки пакетов. И это происходит именно из-за того, что к именам файлов были добавлены хэши, отражающие версии содержимого этих файлов.
Проблема, касающаяся версионирования имён файлов
Представьте, что вы создали и развернули веб-сайт. Вы воспользовались разделением кода, в результате большая часть JavaScript-кода вашего сайта загружается по запросу.
Типичное дерево зависимостей JavaScript-модуля
И наконец, так как содержимое файла main изменилось, имя этого файла тоже должно будет измениться.
Вот как теперь будет выглядеть диаграмма зависимостей.
Модули в дереве зависимостей, на которые повлияло единственное изменение в коде одного из листовых узлов дерева
Из этого примера видно, как небольшое изменение кода, сделанное всего лишь в одном файле, привело к инвалидации кэша 80% фрагментов бандла.
Хотя и правда то, что не все изменения приводят к столь печальным последствиям (например, инвалидация кэша листового узла приводит к инвалидации кэша всех узлов вплоть до корневого, но инвалидация кэша корневого узла не вызывает каскадной инвалидации, доходящей до листовых улов), в идеальном мире нам не приходилось бы сталкиваться с любыми ненужными инвалидациями кэша.
Это приводит нас к следующему вопросу: «Можно ли получить преимущества, даваемые иммутабельными ресурсами и долговременным кэшированием, и при этом не страдать от каскадных инвалидаций кэша?».
Подходы к решению проблемы
Проблема, касающаяся хэшей содержимого файлов, находящихся в именах файлов, с технической точки зрения, заключается не в том, что хэши находятся в именах. Она заключается в том, что эти хэши появляются и внутри других файлов. В результате кэш этих файлов инвалидируется при изменении хэшей в именах файлов, от которых они зависят.
Как оказалось, существует несколько способов достижения этой цели:
Подход №1: карты импорта
Карты импорта — это простейшее решение проблемы каскадной инвалидации кэшей. Кроме того, этот механизм легче всего реализовать. Но он, к сожалению, поддерживается лишь в Chrome (эту возможность, к тому же, нужно явным образом включать).
Несмотря на это я хочу начать именно с рассказа о картах импорта, так как уверен в том, что это решение станет в будущем наиболее распространённым. Кроме того, описание работы с картами импорта поможет объяснить и особенности других подходов к решению нашей проблемы.
Использование карт импорта для предотвращения каскадной инвалидации кэша состоит из трёх шагов.
▍Шаг 1
Нужно настроить бандлер так, чтобы он, при сборке проекта, не включал бы хэши содержимого файлов в их имена.
Если собрать проект, модули которого показаны на диаграмме из предыдущего примера, не включая в имена файлов хэши их содержимого, то файлы в выходной директории проекта будут выглядеть так:
Команды импорта в соответствующих модулях тоже не будут включать в себя хэши:
▍Шаг 2
Нужно воспользоваться инструментом, наподобие rev-hash, и сгенерировать с его помощью копию каждого файла, к имени которого добавлен хэш, указывающий на версию его содержимого.
После того, как эта часть работы выполнена, содержимое выходной директории должно будет выглядеть примерно так, как показано ниже (обратите внимание на то, что там теперь присутствует по два варианта каждого файла):
▍Шаг 3
Нужно создать JSON-объект, хранящий сведения о соответствии каждого файла, в имени которого нет хэша, каждому файлу, в имени которого хэш есть. Этот объект нужно добавить в HTML-шаблоны.
Этот JSON-объект и является картой импорта. Вот как он может выглядеть:
После этого всякий раз, когда браузер увидит команду импорта файла, находящегося по адресу, соответствующему одному из ключей карты импорта, браузер импортирует тот файл, который соответствует значению ключа.
Это означает, что исходный код модулей может совершенно спокойно ссылаться на имена файлов модулей, не содержащих хэшей, а браузер всегда будет загружать файлы, имена которых содержат сведения о версиях их содержимого. А, так как хэшей нет в исходном коде модулей (они присутствуют лишь в карте импорта), то изменения этих хэшей не приведут к инвалидации модулей, отличных от тех, содержимое которых действительно изменилось.
Возможно, вы сейчас задаётесь вопросом о том, почему я создал копию каждого файла вместо того, чтобы просто файлы переименовать. Это нужно для поддержки браузеров, которые не могут работать с картами импорта. В предыдущем примере подобные браузеры увидят лишь файл /vendor.mjs и просто загрузят этот файл, поступив так, как обычно поступают, встречая подобные конструкции. В результате и оказывается, что на сервере должны существовать оба файла.
Если вы хотите увидеть карты импорта в действии, то вот — набор примеров, демонстрирующих все способы решения проблемы каскадной инвалидации кэша, показанные в этом материале. Кроме того, взгляните на конфигурацию сборки проекта, на тот случай, если вам интересно узнать о том, как я генерировал карту импорта и хэши версий для каждого файла.
Уважаемые читатели! Знакома ли вам проблема каскадной инвалидации кэша?
К вопросу об инвалидации кеша
Полнота и избыточность
Начнём всё же с общих соображений не специфичных ни для SQL-запросов, ни для ORM. Упомянутые полноту и избыточность я определяю следующим образом. Полнота инвалидации — это её характеристика, определяющая насколько часто и в каких случаях может/будет возникать ситуация когда в кеше будут содержаться грязные данные и как долго они там будут оставаться. Избыточностью, в свою очередь, назовём то как часто кеш будет инвалидироваться без необходимости.
Рассмотрим для примера распространённый способ инвалидации по времени. С одной стороны, он практически гарантирует, что сразу после изменения данных кеш грязен. С другой стороны, время которое кеш остаётся грязным, мы можем легко ограничить уменьшив время жизни (что в свою очередь сократит процент попаданий). Т.е. при сокращении времени жизни кеша полнота инвалидации улучшается, а избыточность ухудшается. В итоге, чтобы достигнуть идеальной полноты инвалидации (никаких грязных данных) мы должны выставить таймаут в 0, или, другими словами, отключить кеш. Во многих случаях временное устаревание данных в кеше допустимо. Например, как правило, не так уж и страшно если новость в блоке последних новостей появится там на несколько минут позже или общее количество пользователей вашей социальной сети будет указано с ошибкой в пару-тройку тысяч.
Инвалидация по событию
Способ с инвалидацией по времени хорош своей простотой, однако, не всегда применим. Что ж, можно сбрасывать кеш при изменении данных. Одной из проблем при таком подходе является то, что при добавлении нового запроса, который мы кешируем приходиться добавлять код для его инвалидации в при изменении данных. Если мы используем ORM, то данные изменяются (в хорошем случае) в одном месте — при сохранении модели. Наличие одного центрального кода изменения данных облегчает задачу, однако, при большом количестве разнообразных запросов приходиться всё время дописывать туда всё новые и новые строки сброса различных кусочков кеша. Таким образом, мы получаем на свою голову избыточную связность кода. Пора её ослабить.
Воспользуемся событиями — ORM при сохранении/удалении модели будет события генерировать, а мы при кешировании чего-либо будем тут же и вешать обработчик на соответствующее событие, удаляющий это что-либо из кеша. Всё отлично, однако, написание большого количества похожих обработчиков утомляет, плюс логика приложения зарастает логикой кеширования/инвалидации как свинья жиром.
Автоматическая инвалидация ORM-запросов
Вспомним, что у нас есть ORM, а для него каждый запрос представляет не просто текст, а определённую структуру — модели, дерево условий и прочее. Так что, по идее, ORM может и кешировать и вешать инвалидационные обработчики прямо при кешировании по мере надобности. Чертовски привлекательное решение для ленивых ребят, вроде меня.
Небольшой пример. Допустим мы выполняем запрос:
select * from post where category_id =2 and published
и т.д.
В реальности в инвалидаторах удобнее хранить списки ключей кеша, а не тексты запросов, тексты здесь для наглядности.
Посмотрим, что будет происходить при добавлении объекта. Мы должны пройти по всему списку инвалидаторов и стереть ключи кеша для условий, выполняющихся для добавленного объекта. Но инвалидаторов может быть много, и храниться они должны там же где сам кеш, т.е. скорее всего не в памяти процесса и загружать их все каждый раз не хотелось бы, да и последовательная проверка всех условий больно долга.
Очевидно, нужно как-то группировать и отсеивать инвалидаторы без их полной проверки. Заметим, что картина когда условия различаются только значениями. Например, инвалидаторы в модели post все имеют вид category_id=? and published=. Сгруппируем инвалидаторы из примера по схемам:
то единственный подходящий инвалидатор из семейства будет category_id=2 and published=true и, следовательно нужно стереть соответствующие ему 3 ключа кеша. Т.е. не требуется последовательная проверка условий мы сразу получаем нужный инвалидатор по схеме и данным объекта.
Однако, что делать с более сложными условиями? В отдельных случаях кое-что можно сделать: or разложить на два инвалидатора, in развернуть в or. В остальных случаях либо придётся всё усложнить, либо сделать инвалидацию избыточной, отбросив такие условия. Приведём то, какими будут инвалидаторы для foo после таких преобразований:
Таким образом, нам нужно для каждой модели только хранить схемы (просто списки полей), по которым при надобности мы строим инвалидаторы и запрашиваем списки ключей, которые следует стереть.
О проблемах инвалидации кэша. Тегирование кэша.¶
О моем опыте решения проблем инвалидации кэша, и о принципах работы библиотеки cache-dependencies.
Проблема зависимостей в кэшировании¶
Теперь достаточно инвалидировать метку, чтобы все зависимые кэши автоматически инвалидировались. Эта технология не нова, и активно используется в других языках программирования. Одно время ее даже пытались внедрить в memcached, см. memcached-tag.
Накладные расходы при чтении кэша или его создании?¶
Возникает вопрос реализации инвалидации зависимых от метки кэшей. Возможны два варианта:
1. При инвалидации метки физически уничтожать все зависимые кэши. Для реализации такого подхода потребуются накладные расходы при создании кэша, чтобы добавить информацию о нем в список (точнее, множество) зависимостей каждой метки (например, используя SADD). Недостаток заключается в том, что инвалидация большого количества зависимых кэшей требует определенного времени.
2. При инвалидации метки просто изменять версию этой метки. Для реализации потребуется добавлять в кэш информацию о версиях меток. При чтении кэша потребуются накладные расходы для сверки версии каждой его метки, и, если версия устарела, то кэш считается недействительным. Достоинство этого подхода заключается в мгновенной инвалидации метки и всех ее зависимых кэшей. Можно не бояться вытеснения из хранилища закэшированной информации о версии метки по LRU принципу, так как метки запрашиваются намного чаще самого кэша.
Я выбрал второй вариант.
Многоуровневое кэширование и тегирование¶
Поэтому система кэширования должна автоматически отслеживать связи между вложенными кэшами, и передавать метки от дочернего кэша к родительскому.
Проблема репликации¶
При инвалидации кэша параллельный поток может успеть воссоздать кэш с устаревшими данными, прочитанными из slave в перид времени после инвалидации кэша, но до момента обновления slave.
Лучшим решением было бы блокирование создания кэша до момента обновления slave. Но, во-первых, это сопряжено с определенными накладными расходами, а во-вторых, все потоки (в том числе и текущий) продолжают считывать устаревшие данные из slave (если не указано явное чтение из мастера). Поэтому, компромиссным решением может быть просто повторная инвалидация кэша через период времени гарантированного обновления slave.
В своей практике мне приходилось встречать такой подход как регенерация кэша вместо его удаления/инвалидации. Такой подход влечет за собой не совсем эффективное использование памяти кэша (работающего по LRU принципу). К тому же, он не решает проблему сложности инвалидации, и, в данном вопросе, мало чем отличается от обычного удаления кэша по его ключу, возлагая всю сложность на само приложение. Также он таит множество потенциальных баг. Например, он чувствителен к качеству ORM, и если ORM не приводит все атрибуты инстанции модели к нужному типу при сохранении, то в кэш записываются неверные типы данных. Мне приходилось видеть случай, когда атрибут даты записывался к кэш в формате строки, в таком же виде, в каком он пришел от клиента. Хотя он и записывался в БД корректно, но модель не делала приведение типов без дополнительных манипуляций при сохранении (семантическое сопряжение).
Updated on Nov 10, 2016
Добавлено описание реализации блокировки меток.
Реализация блокировки меток¶
Блокировка меток в библиотеке реализована в виде обхода параллельными потоками процедуры сохранения кэша, помеченного заблокированной меткой.
Конструктивное препятствие реализации пессимистической блокировки¶
Библиотека предназначена, прежде всего, для управления инвалидацией кэша.
Предположим, поток П1 начал транзакцию с уровнем изоляции Repeatable read.
Следом за ним, поток П2 начал транзакцию, изменил данные в БД, и вызвал инвалидацию метки М1, что наложило блокировку на метку М1 до момента фиксации транзакции.
Во время фиксации транзакции, поток П2 освобождает метку М1. Затем поток П1 записывает в кэш устаревшие данные. Смысла от такой блокировки нет.
Но что если мы будем проверять статус метки не во время создания кэша, а во время чтения кэша? Изменило бы это хоть что-то?
Таким образом, данное решение было бы половинчатым, не универсальным, и содержало бы неконтролируемую зависимость. Для 2-х из 4-х уровней изоляции транзакций работать не будет.
Сопутствующие препятствия реализации пессимистической блокировки¶
Кроме конструктивного препятствия есть еще и другие.
Библиотека ориентирована главным образом на веб-приложения. Ожидание параллельных потоков до момента окончания транзакции, или до момента обновления slave, который в некоторых случаях может длиться 8 секунд и более, практически не реализуемо в веб-приложениях.
Основных причин здесь три:
Также возникла бы проблема с реализацией, поскольку корректно заблокировать все метки одним запросом невозможно.
Отдельно стоит упомянуть возможность блокировки строк в БД при использовании выражения SELECT FOR UPDATE. Но это будет работать только в том случае, если обе транзакции используют выражение SELECT FOR UPDATE, в противном случае:
Однако, выборку для модификации не имеет смысла кэшировать (да и вообще, в веб-приложениях ее мало кто использует, так как этот вопрос перекрывается уже вопросом организации бизнес-транзакций), соответственно, ее блокировка мало чем может быть полезна в этом вопросе. К тому же она не решает проблему репликации.
Thundering herd¶
Но что делать, если закэшированная логика действительно очень ресурсоемка?
Dogpile известен также как Thundering Herd effect или cache stampede.
Блокировка должна охватывать весь фрагмент кода от чтения кэша до его создания. Она решает другую задачу, которая не связана с инвалидацией.
Существует ряд решений для реализации такой блокировки, вот только некоторые из них:
Проблема транзакций¶
Если Ваш проект имеет более-менее нормальную посещаемость, то с момента инвалидации кэша и до момента фиксации транзакции, параллельный поток может успеть воссоздать кэш с устаревшими данными. В отличии от проблемы репликации, здесь проявление проблемы сильно зависит от качества ORM, и вероятность проблемы снижается при использовании паттерна Unit of Work.
Рассмотрим проблему для каждого уровня изоляции транзакции по отдельности.
Read uncommitted¶
Тут все просто, и никакой проблемы не может быть в принципе. В случае использования репликации достаточно сделать отложенный повтор инвалидации через интервал времени гарантированного обновления slave.
Read committed¶
Тут уже проблема может присутствовать, особенно если Вы используете ActiveRecord. Использование паттерна DataMapper в сочетании с Unit of Work заметно снижает интервал времени между сохранением данных и фиксацией транзакции, но вероятность проблемы все равно остается.
В отличии от проблемы репликации, здесь предпочтительней было бы блокирование создания кэша до момента фиксации транзакции, так как текущий поток видит в БД не те данные, которые видят параллельные потоки. А поскольку нельзя гарантированно сказать какой именно поток, текущий или параллельный, создаст новый кэш, то создание кэша до фиксации транзакции было бы желательно избежать.
Тем не менее, этот уровень изоляции не является достаточно серьезным, и выбирается, как правило, для повышения степени параллелизма, т.е. с той же целью что и репликация. А в таком случае, эта проблема обычно поглощается проблемой репликации, ведь чтение делается все равно из slave.
Поэтому, дорогостоящая блокировка может быть компромисно заменена повторной инвалидацией в момент фиксации транзакции.
Repeatable read¶
Этот случай наиболее интересен. Здесь уже без блокировки создания кэша не обойтись, хотя бы потому, что нам нужно знать не только список меток, но и время фиксации транзакции, которая осуществила инвалидацию метки кэша.
Мало того, что мы должны заблокировать метку с момента инвалидации до момента фиксации транзакции, так мы еще и не можем создавать кэш в тех параллельных транзакциях, которые были открыты до момента фиксации текущей транзакции.
Хорошая новость заключается в том, что раз уж мы и вынуждены мириться с накладными расходами на блокировку меток, то можно блокировать их вплоть до обновления slave, и обойтись без компромисов.
Serializable¶
Поскольку несуществующие объекты обычно не кэшируются, то здесь достаточно ограничится той же проблематикой, что и для уровня Repeatable read.
Множественные соединения с БД¶
Но если Вы используете несколько соединений к одной и той же БД (что само по себе странно, но теоретически могут быть случаи когда нет возможности расшарить коннект для нескольких ORM в едином проекте), или же просто транзакции различных БД не синхронны, то Вы можете сконфигурировать внешний кэш так, чтобы иметь по одному экземпляру внешнего кэша на каждое соединение с БД для каждого экземпляра внутреннего кэша.
Динамические окна в кэше¶
Но более интересной мне показалась возможность использовать в качестве динамического окна обычный Python-код, и абстрагироваться от сторонних технологий.
Updated on Nov 06, 2016
Добавлен абстрактный менеджер зависимостей.
Абстрактный менеджер зависимостей¶
Долгое время мне не нравилось то, что о логике, ответственной за обработку тегов, были осведомлены сразу несколько различных классов с различными обязанностями.
Кроме того, у меня там был еще один метод со спутанными обязанностями для обеспечения возможности агрегации запросов в хранилище, что большого восторга не вызывало.
Но мысль инкапсулировать управление тегами в отдельном абстрактном классе, отвечающем за управления зависимостями, и получить возможность использовать для управления инвалидацией не только теги, но и любой иной принцип, включая компоновку различных принципов, мне нравилась.
Решение появилось с введение класса Deferred. Собственно это не Deferred в чистом виде, в каком его привыкли видеть в асинхронном программировании, иначе я просто использовал бы эту элегантную и легковесную библиотечку, любезно предоставленную ребятами из Canonical.
В моем же случае, требуется не только отложить выполнение задачи, но и накапливать их с целью агрегации однотипных задач, которые допускают возможность агрегации ( cache.get_many() является как раз таким случаем).
Возможно, название Queue или Aggregator здесь подошло бы лучше, но так как с точки зрения интерфейса мы всего лишь откладываем выполнение задачи, не вникая в детали ее реализации, то я предпочел оставить название Deferred.
Все это позволило выделить интерфейс абстрактного класса, ответственного за управление зависимостями, и теперь управление метками кэша стало всего лишь одной из его возможных реализаций в виде класса TagsDependency.
Это открывает перспективы создания других вариантов реализаций управления зависимостями, например, на основе наблюдения за изменением какого-либо файла, или SQL-запроса, или какого-то системного события.
Благодарности¶
Моя благодарность @akorn за содержательное обсуждение проблематики кэширования.
Control. Invalidate Метод
Определение
Некоторые сведения относятся к предварительной версии продукта, в которую до выпуска могут быть внесены существенные изменения. Майкрософт не предоставляет никаких гарантий, явных или подразумеваемых, относительно приведенных здесь сведений.
Делает недействительной конкретную область элемента управления и вызывает отправку сообщения рисования элементу управления.
Перегрузки
Делает недействительной указанную область элемента управления (добавляет ее к области обновления элемента, которая будет перерисована при следующей операции рисования) и вызывает отправку сообщения рисования элементу управления. При необходимости объявляет недействительными назначенные элементу управления дочерние элементы.
Делает недействительной указанную область элемента управления (добавляет ее к области обновления элемента, которая будет перерисована при следующей операции рисования) и вызывает отправку сообщения рисования элементу управления. При необходимости объявляет недействительными назначенные элементу управления дочерние элементы.
Делает недействительной указанную область элемента управления (добавляет ее к области обновления элемента, которая будет перерисована при следующей операции рисования) и вызывает отправку сообщения рисования элементу управления.
Делает недействительной указанную область элемента управления (добавляет ее к области обновления элемента, которая будет перерисована при следующей операции рисования) и вызывает отправку сообщения рисования элементу управления.
Делает недействительной конкретную область элемента управления и вызывает отправку сообщения рисования элементу управления. При необходимости объявляет недействительными назначенные элементу управления дочерние элементы.
Делает недействительной всю поверхность элемента управления и вызывает его перерисовку.
Invalidate(Region, Boolean)
Делает недействительной указанную область элемента управления (добавляет ее к области обновления элемента, которая будет перерисована при следующей операции рисования) и вызывает отправку сообщения рисования элементу управления. При необходимости объявляет недействительными назначенные элементу управления дочерние элементы.
Параметры
Объект Region, который делается недействительным.
Комментарии
Вызов Invalidate метода не приводит к принудительной синхронной прорисовке; чтобы принудительно выполнить синхронную заливку, вызовите Update метод после вызова Invalidate метода. При вызове этого метода без параметров вся клиентская область добавляется в область обновления.