Проблема зависимостей в кэшировании

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

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

И тут на выручку приходит тегирование кэша, т.е. прошивание кэша метками. Например, кэш главной страницы может быть прошит тегом product.id:635. А все посты пользователя могут быть прошиты меткой user.id:10. Коллекции можно кэшировать составным тегом, состоящим из критериев выборки, например type.id:1;category.id:15;region.id:239.

Теперь достаточно инвалидировать метку, чтобы все зависимые кэши автоматически инвалидировались. Эта технология не нова, и активно используется в других языках программирования. Одно время ее даже пытались внедрить в memcached, см. memcached-tag.

Также смотрите:

Накладные расходы при чтении кэша или его создании?

Возникает вопрос реализации инвалидации зависимых от метки кэшей. Возможны два варианта:

1. При инвалидации метки физически уничтожать все зависимые кэши. Для реализации такого подхода потребуются накладные расходы при создании кэша, чтобы добавить информацию о нем в список (точнее, множество) зависимостей каждой метки (например, используя SADD). Недостаток заключается в том, что инвалидация большого количества зависимых кэшей требует определенного времени.

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

Я выбрал второй вариант.

Многоуровневое кэширование и тегирование

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

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

Проблема репликации

При инвалидации кэша параллельный поток может успеть воссоздать кэш с устаревшими данными, прочитанными из slave в перид времени после инвалидации кэша, но до момента обновления slave.

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

В своей практике мне приходилось встречать такой подход как регенерация кэша вместо его удаления/инвалидации. Такой подход влечет за собой не совсем эффективное использование памяти кэша (работающего по LRU принципу). К тому же, он не решает проблему сложности инвалидации, и, в данном вопросе, мало чем отличается от обычного удаления кэша по его ключу, возлагая всю сложность на само приложение. Также он таит множество потенциальных баг. Например, он чувствителен к качеству ORM, и если ORM не приводит все атрибуты инстанции модели к нужному типу при сохранении, то в кэш записываются неверные типы данных. Мне приходилось видеть случай, когда атрибут даты записывался к кэш в формате строки, в таком же виде, в каком он пришел от клиента. Хотя он и записывался в БД корректно, но модель не делала приведение типов без дополнительных манипуляций при сохранении (семантическое сопряжение).

Updated on Nov 10, 2016

Добавлено описание реализации блокировки меток.

Реализация блокировки меток

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

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

Почему не была использована пессимистическая блокировка меток (Pessimistic Offline Lock), или Mutual Exclusion? Вопрос резонный, ведь закэшированная логика может быть достаточно ресурсоемкой. При такой реализации параллельные потоки ожидали бы освобождения заблокированной метки.

Конструктивное препятствие реализации пессимистической блокировки

Библиотека предназначена, прежде всего, для управления инвалидацией кэша.

Предположим, поток П1 начал транзакцию с уровнем изоляции Repeatable read.

Следом за ним, поток П2 начал транзакцию, изменил данные в БД, и вызвал инвалидацию метки М1, что наложило блокировку на метку М1 до момента фиксации транзакции.

Поток П1 пытается прочитать кэш К1, который прошит меткой М1, и является невалидным. Не сумев прочитать невалидный кэш К1, поток П1 получает данные из БД, которые уже утратили актуальность (напомню, уровень изоляции - Repeatable read). Затем он пытается создать кэш К1, и встает в ожидание, так как на метку К1 наложена пессимистическая блокировка.

Во время фиксации транзакции, поток П2 освобождает метку М1. Затем поток П1 записывает в кэш устаревшие данные. Смысла от такой блокировки нет.

Но что если мы будем проверять статус метки не во время создания кэша, а во время чтения кэша? Изменило бы это хоть что-то?

Изменило бы. Во-первых, добавило бы оверхед на логику чтения. Во-вторых, изменило бы результат, если бы уровень изоляции транзакции не превышал Read committed. Для уровня изоляции Repeatable read (который выбран по умолчанию для ряда БД, и является минимально необходимым для корректной работы паттерна Identity Map) и выше, - ничего не изменило бы. Для этого пришлось бы блокировать поток еще до начала транзакции.

Таким образом, данное решение было бы половинчатым, не универсальным, и содержало бы неконтролируемую зависимость. Для 2-х из 4-х уровней изоляции транзакций работать не будет.

Сопутствующие препятствия реализации пессимистической блокировки

Кроме конструктивного препятствия есть еще и другие.

Библиотека ориентирована главным образом на веб-приложения. Ожидание параллельных потоков до момента окончания транзакции, или до момента обновления slave, который в некоторых случаях может длиться 8 секунд и более, практически не реализуемо в веб-приложениях.

Основных причин здесь три:

  • Для веб-приложения важна быстрота отклика, так как клиент может просто не дождаться ответа.
  • Нет смысла ожидать создание кэша более, чем требуется времени на само создание кэша.
  • Рост количества ожидающих потоков может привести к перерасходу памяти, или доступных воркеров сервера, или исчерпанию максимально допустимого числа коннектов к БД или других ресурсов.

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

  • Во-первых, для блокировки метки нужно использовать метод cache.add() вместо cache.set_many(), чтобы гарантировать атомарность проверки существования и создания кэша.
  • Во-вторых, каждую метку нужно блокировать отдельным запросом, что увеличило бы накладные расходы.
  • В-третьих, поодиночное блокирование чревато взаимной блокировкой (Deadlock), вероятность которой можно заметно сократить с помощью топологической сортировки.

Отдельно стоит упомянуть возможность блокировки строк в БД при использовании выражения SELECT FOR UPDATE. Но это будет работать только в том случае, если обе транзакции используют выражение SELECT FOR UPDATE, в противном случае:

When a transaction uses this isolation level, a SELECT query (without a FOR UPDATE/SHARE clause) sees only data committed before the query began; it never sees either uncommitted data or changes committed during query execution by concurrent transactions. In effect, a SELECT query sees a snapshot of the database as of the instant the query begins to run.

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

Thundering herd

Но что делать, если закэшированная логика действительно очень ресурсоемка?

Dogpile известен также как Thundering Herd effect или cache stampede.

Ответ прост, - пессимистическая блокировка. Только не меток кэша, а ключа кэша (или группы связанных ключей, см. Coarse-Grained Lock, особенно при использовании агрегирования запросов). Потому что при освобождении блокировки кэш должен быть гарантированно создан (а кэш и метки связаны отношением many to many).

Блокировка должна охватывать весь фрагмент кода от чтения кэша до его создания. Она решает другую задачу, которая не связана с инвалидацией.

Существует ряд решений для реализации такой блокировки, вот только некоторые из них:

Проблема транзакций

Если Ваш проект имеет более-менее нормальную посещаемость, то с момента инвалидации кэша и до момента фиксации транзакции, параллельный поток может успеть воссоздать кэш с устаревшими данными. В отличии от проблемы репликации, здесь проявление проблемы сильно зависит от качества ORM, и вероятность проблемы снижается при использовании паттерна Unit of Work.

Рассмотрим проблему для каждого уровня изоляции транзакции по отдельности.

Read uncommitted

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

Read committed

Тут уже проблема может присутствовать, особенно если Вы используете ActiveRecord. Использование паттерна DataMapper в сочетании с Unit of Work заметно снижает интервал времени между сохранением данных и фиксацией транзакции, но вероятность проблемы все равно остается.

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

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

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

Repeatable read

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

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

Хорошая новость заключается в том, что раз уж мы и вынуждены мириться с накладными расходами на блокировку меток, то можно блокировать их вплоть до обновления slave, и обойтись без компромисов.

Serializable

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

Множественные соединения с БД

Если Вы используете разные БД, и их транзакции синхронны, или просто используется репликация, Вы можете использовать по одному экземляру внешнего кэша (враппера) для каждого экземпляра внутреннего кэша (бэкенда). Транзакции кэша не обязаны строго соответствовать системным транзакциям каждой БД. Достаточно того, чтобы они выполняли свое предназначение, - не допускать подмену данных посредством кэша в параллельных потоках. Поэтому, они могут охватывать несколько системных транзакций БД.

Но если Вы используете несколько соединений к одной и той же БД (что само по себе странно, но теоретически могут быть случаи когда нет возможности расшарить коннект для нескольких ORM в едином проекте), или же просто транзакции различных БД не синхронны, то Вы можете сконфигурировать внешний кэш так, чтобы иметь по одному экземпляру внешнего кэша на каждое соединение с БД для каждого экземпляра внутреннего кэша.

Динамические окна в кэше

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

Один из вариантов решения этой проблемы - это использование технологии Server Side Includes.

Другой вариант - это использование двухфазной шаблонизации, например, используя библиотеку django-phased. Справедливости ради нужно отметить, что решение имеет немаленькое ресурсопотребление, и в некоторых случаях может нивелировать (если не усугублять) эффект от кэширования. Возможно, именно поэтому, оно не получило широкого распространения.

Популярный шаблонный движок Smarty на PHP имеет функцию {nocache}.

Но более интересной мне показалась возможность использовать в качестве динамического окна обычный Python-код, и абстрагироваться от сторонних технологий.

Updated on Nov 06, 2016

Добавлен абстрактный менеджер зависимостей.

Абстрактный менеджер зависимостей

Долгое время мне не нравилось то, что о логике, ответственной за обработку тегов, были осведомлены сразу несколько различных классов с различными обязанностями.

Было желание инкапсулировать эту обязанность в отдельном классе-стратегии, как это сделано, например, в TagDependency of YII framework, но не хотелось ради этого увеличивать накладные расходы в виде дополнительного запроса на каждый ключ кэша для сверки его меток, что означало бы лишение метода cache.get_many() своего смысла - агрегирования запросов. По моему мнению, накладные расходы не должны превышать одного запроса в совокупности на каждое действие, даже если это действие агрегированное, такое как cache.get_many().

Кроме того, у меня там был еще один метод со спутанными обязанностями для обеспечения возможности агрегации запросов в хранилище, что большого восторга не вызывало.

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

Решение появилось с введение класса Deferred. Собственно это не Deferred в чистом виде, в каком его привыкли видеть в асинхронном программировании, иначе я просто использовал бы эту элегантную и легковесную библиотечку, любезно предоставленную ребятами из Canonical.

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

Возможно, название Queue или Aggregator здесь подошло бы лучше, но так как с точки зрения интерфейса мы всего лишь откладываем выполнение задачи, не вникая в детали ее реализации, то я предпочел оставить название Deferred.

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

Это открывает перспективы создания других вариантов реализаций управления зависимостями, например, на основе наблюдения за изменением какого-либо файла, или SQL-запроса, или какого-то системного события.

Благодарности

Моя благодарность @akorn за содержательное обсуждение проблематики кэширования.

This article in English “About problems of cache invalidation. Cache tagging.”.

About problems of cache invalidation. Cache tagging.   Искусство воевать

Comments

comments powered by Disqus