В этой статье я опишу один способ, помогающий определить, когда инвалидировать записи кэша. В качестве примера я приведу специфическую конфигурацию, которая, тем не менее, должна получиться достаточно универсальной, а в заключении поста расскажу, как обобщить ее еще сильнее.
Итак, «решается» ли в этом посте какая-либо задача, либо является ли предложенное «решение» в какой-то степени инновационным? Нет. Цель, с которой я написал этот пост – представить кэш как распределенную систему (как он того заслуживает). Работает ли представленное здесь решение для инвалидации кэша по некоторому протоколу (в том смысле, можно ли его доказать при помощи TLA+)? Да. Я буду рад написать для него спецификацию в формате TLA+, если читатели заинтересуются. Дайте мне знать.
В первой половине этого поста описано потенциальное решение для конкретных задач, связанных с инвалидацией кэша. Во второй половине поста приведены компромиссы, на которые приходится идти при попытке обобщить это решение. Так или иначе, кэш все равно можно инвалидировать, но иногда цена этого слишком высока (неограниченное усиление записи, гигантские вычислительные издержки, т.д.). В данном случае речь не идет о принципиальной невозможности инвалидировать кэш, но в некоторых случаях делать инвалидацию, возможно, и не стоит – в зависимости от ситуации, рабочей нагрузки и требований. Так что, вы можете сами определиться с тем, когда и как инвалидировать кэши (при условии, что в рамках этой задачи считаете кэш распределенной системой), но есть разнообразные причины, по которым вы просто не пойдете на инвалидацию кэша.
Пример
Допустим, в системе есть следующие компоненты (на самом деле, это конфигурация самого типичного веб-приложения):
- Множество клиентов, не сохраняющих состояние (веб-серверы).
- Один кэш-сервер (скажем, Memcache).
- Одна база данных (скажем, Postgres).
В базе данных мы храним таблицу (набор отношений) под названием friends. А ее схема выглядит примерно так:
Теперь мы хотим сохранить в кэше набор отношений friends-of-friends, так как у нас в приложении есть код вида getFriendsofFriends($bob). Вполне обычно/естественно кэшировать список friends-of-friends так, чтобы в качестве ключей выступали user-id, и делать это в таких сервисах как Redis или Memcache. Допустим, ключом в Memcache является пользовательский id (напр., user id Боба), а значением – список id тех пользователей, которые дружат с друзьями Боба. Вот и все.
Определение
- Здесь я определю «кэш» как любое материальное представление информации, содержащееся в источнике истины к этому посту, и подразумеваю такое определение везде в рамках этого поста, если не указано иное.
- Под «инвалидацией» я понимаю операцию обновления/отбрасывания действующих записей кэша, когда источник истины меняется. Поэтому никакие устаревшие данные не будут храниться в кэше неопределенно долго.
Требования
Используя кэш, вы по определению работаете с распределенной системой – есть кэш, а есть источник истины. Поскольку вы имеете дело с распределенной системой, мы должны ясно представлять себе ожидаемое распределение состояния и знаний. Слишком много таких систем, в которых к кэшу подходят ситуативно, распределенность системы при этом не осознается. Именно поэтому становится невероятно сложно определиться с тем, когда именно инвалидировать кэш. Если вы выполняете запрос в базе Postgres и сохраняете данные локально в ее клиентском кэше, то очевидно, что, не зная об устройстве базы данных, инвалидировать кэш правильно удается не всегда. Например, может прийти другой клиент и втихую изменить Postgres, а первый клиент об этом знать не будет. Postgres не знает о том, что первый клиент успел кэшировать какие-либо данные в своем более раннем запросе, т.д.
Чтобы можно было корректно обращаться с распределенной системой, кэш и база данных должны быть осведомлены друг о друге. Это означает, что база данных должна знать: некоторые запросы кэшируются. А кэш должен знать, откуда поступают данные (и, в особенности, в каком порядке идут операции изменения – если в распределенных системах и есть единственное важнейшее слово, то это слово «порядок»).
Точнее, схема данных кэша должна быть сообщена всей системе данных (а не только о самом кэше, отдельно взятом процессе, который где-то работает). Очевидно, что без этих требований вообще невозможно провести надежную инвалидацию кэша (но для конкретного практического случая можно предложить какое-нибудь импровизированное решение).
ВВЕДЕНИЕ
Например, кто-нибудь вставит (INSERT) новое отношение дружбы, связывающее Боба и Алису:
BEGIN;
INSERT INTO friends (user_id, friend_id)
VALUES
($bob, $alice), ($alice, $bob);
COMMIT;Наша цель здесь – обрисовать, когда и как инвалидировать записи кэша (друзья-друзей) и сделать это надежно. В Postgres есть возможность, поддерживающая возврат данных из измененных строк. В данном случае это удобно, поскольку мы хотим знать id тех пользователей, список отношений «друзья друзей» для которых могли бы измениться. Теперь транзакция записи могла бы выглядеть так:
BEGIN;
INSERT INTO friends (user_id, friend_id)
VALUES
($bob, $alice), ($alice, $bob) RETURNING user_id;
COMMIT;В данном простом примере очень легко выявить те пользовательские user_id, которые изменяются (того же самого можно добиться, имея SELECT после INSERT). Но в более сложных запросах возможность RETURNING из базы данных Postgres становится очень удобна.
Теперь, когда клиент базы данных выполнит эту транзакцию, он получит список тех user_id, чьи дружеские связи изменились. Теперь в кэше необходимо обновить списки «друзей друзей» не только для Алисы и Боба, но и для друзей Алисы и друзей Боба. После этого, имея список user_id, необходимо выполнить запрос select, чтобы получить всех пользователей, на которых повлияли данные изменения:
SELECT friend_id
FROM friends
WHERE user_id in $user_ids;Итак, теперь у нас есть полный список тех пользовательских id, которые нужно инвалидировать.
Операции пойдут в таком порядке:
- Клиент начинает транзакцию.
- Клиент выполняет все необходимые изменения.
- Клиент собирает те user_id, чьи записи в кэше необходимо инвалидировать.
- Список user_id надолго сохраняется в отдельной таблице или в бинлоге (напр., MySQL) – все это должно делаться в рамках одной и той же транзакции базы данных DB.
- Клиент фиксирует транзакцию.
- Инвалидируется кэш для выбранных user_id.
В данном случае, даже если после фиксации базы данных работа клиента аварийно завершится, можно применить отсекатель, который делит лог инвалидации на части, после чего асинхронно и надежно применяет инвалидацию кэша. Для инвалидации требуется лишь семантика «как минимум однократной» доставки.
Максимально упрощенная реализация отсекателя может выглядеть так:
- Читать таблицу to-be-invalidated.
- Отправлять требование об инвалидации кэша.
- По получении подтверждения отсекать таблицу to-be-invalidated (вплоть до записи, которая завершает список, отправленный на инвалидацию кэша).
Возможны случаи, в которых одни и те же записи кэша будут инвалидироваться многократно; и это нормально, коль скоро информация об инвалидациях кэша отправляется после фиксаций базы данных.
Такой механизм работает, когда у нас всего одна база данных (один шард, один ведущий диск).
В данном случае особенно приятно, что шаги «сбор пользовательских id» и «инвалидация кэша» могут быть инкапсулированы в клиенте базы данных, и не придется беспокоиться о том, не забыл ли кто-нибудь инвалидировать кэш. Вы заметите, что клиент базы данных здесь осведомлен о схеме кэша (поэтому знает, что нужно собирать user_ids, т.д.). Здесь и начинает действовать упомянутое ранее требование:
Схема данных кэша должна быть сообщена всей системе данных.На практике именно тот, кто добавляет новую схему кэша, также должен обновить клиент базы данных, так, чтобы он мог обрабатывать инвалидацию кэша. Как можно отметить, оператор RETURNING должен прикрепляться к каждой операции изменения, и возникает вопрос о том, насколько универсален и практичен такой подход. Если вы знакомы с MySQL и RBR, примерьте их на этот случай. В сущности, здесь мы стремимся получить набор RBR-событий, которые происходили бы синхронно. Поэтому здесь действует единственное требование: оператор RETURNING должен обновлять строки для каждой таблицы (отношений). Это функция имеющихся таблиц вашей базы данных, от схем кэша она не зависит. Она очень универсальна.
Возможно, вы заметили, что здесь мы, в сущности, выполняем «транзакцию», захватывающую базу данных и кэш. Это не ACID-транзакция, но на стороне кэша это, по сути, постоянно фиксируемая (always-commit) транзакция. Причина, по которой эта операция может быть менее строгой, чем транзакция базы данных, захватывающая разные системы/шарды – в том, что кэш содержит чисто материальное представление именно той информации, что содержится в базе данных. Поэтому не может возникать конфликтов такого рода: база данных фиксирует операцию записи, а кэш отвечает, что существует конфликт, поэтому кэш инвалидировать нельзя (что может произойти при транзакциях баз данных, захватывающих x-систему/x-шард).
Обобщение
Теперь давайте обобщим вышеприведенную конфигурацию – единственный кэш, единственная база данных.
Что, если схема кэша достаточно сложна?
Допустим, у нас есть кэш, в котором хранятся записи по друзьям друзей, живущим в США. Итак, кроме таблицы friends у нас теперь есть таблица home, и в этой таблице записано, где живет каждый пользователь. Теперь на наш кэш могут повлиять обновления, вносимые как в friends, так и в home. Вспомните одно из ключевых требований, перечисленных нами выше: информация о схемах кэша предоставляется всей системе данных.
Теперь давайте сосредоточимся только на изменившихся строках, так как только изменившиеся отношения friends и/или изменившиеся отношения home могут повлиять на наш кэш. Если изменятся отношения friends, то все та же функция преобразования, о которой речь шла выше в этом посте, будет применяться в основном без изменений (за исключением того, что теперь здесь добавляется дополнительное объединение и фильтрация по таблице home). Нам просто нужно добавить логику сбора инвалидационных ключей на случай изменения отношений home. Она может иметь примерно такой вид:
BEGIN;
UPDATE home SET country = 'US' WHERE user_id = $bob RETURNING user_id;
COMMIT;Теперь при обновлениях отношения home мы получим в ответ список тех user_id, чьи страны пребывания изменились, а эти изменения могут затронуть наш кэш «друзья друзей, живущие в США». После этого запрос к коллекции может принять вид:
SELECT friends.user_id
FROM
(
SELECT friends.user_id as uid
FROM friends
WHERE friend_id in $user_ids -- обратите внимание, что здесь мы не фильтруем по стране, так как любое изменение страны (эмиграция из США или иммиграция в США) спровоцирует инвалидацию
) AS user_with_friends_who_moved
JOIN friends
ON friends.friend_id = user_with_friends_who_moved.uid;Итак, теперь у нас есть полный список ключей инвалидации – id тех пользователей, чьи «друзья друзей» переехали. Суть в том, что информация, сохраненная в кэше – это также просто набор отношений. При условии, что мы знаем схему, для нас абсолютно осуществимо вывести тот список ключей, которые должны быть обновлены в рамках той же транзакции базы данных. Сработает ли это? Да (если под «сработает» подразумевается «нам удастся надежно инвалидировать кэш»). Всегда ли это хорошая идея? Определенно, нет. Просто посмотрите на приведенный здесь запрос. У него неограниченный разброс веерной доставки (fanout), что замедлит вашу транзакцию. Инвалидировать кэш даром не получится.
Что, если у меня много реплик кэша, схем кэша и много данных?
Именно здесь применяется асинхронное усиление записи (в кэш). Если у вас много реплик кэша (так бывает нередко, поскольку кэши часто вводятся для масштабирования трафика при считывании), то усиление записи ужасно. Из-за него транзакция записи замедляется, а сам этот подход чреват возникновением ошибок (частота ошибок возрастает, как и время ожидания при транзакции, время ожидания при блокировке, т.д.). Это неудивительно, так как в кэше хранится денормализованное материализованное представление данных, которое сближается по характеристикам с табличными индексами на пути обновлений. Следовательно, совместное использование усиления записи также приводит к издержкам.
Один из вариантов сократить усиление записи – перенести больше вычислений на путь считывания. Например, здесь можно кэшировать список пользователь -> друзья и выполнить объединение на пути считывания. Мгновенный снимок в результате не получится (если только операции считывания, выполняемые вами в базе данных, не проводятся в строго определенные моменты).
А что если моя реплика базы данных предназначена только для чтения?
Берегитесь. После того, как кэш инвалидирован (после изменения базы данных), взгляните, есть ли у вас реплика базы данных (всегда находится за ведущим экземпляром базы данных). Если так, то всегда есть шанс, что кэш удастся заполнить данными из устаревшей реплики базы данных.
Конкретный пример выглядел бы так:
- В базе данных есть информация A.
- Клиент обновляет A -> B и инвалидирует кэш.
- В реплике базы данных по-прежнему есть информация A.
- Кэш заполняется данными из реплики базы данных и возвращает A на место.
- Реплика базы данных поспевает за происходящим и обновляет A -> B.
- Теперь данные A (устаревшие) будут находиться в кэше неопределенно долго.
Не буду вдаваться в детали, но есть несколько способов выпутаться из этой ситуации.
Например,
- Вместе с командой на инвалидацию кэша отправлять данные о версии.
- Отслеживать версию данных в кэше, чтобы более ранние данные никогда не актуализировались (напр., после того, как будет обработана инвалидация B, ни в коем случае не возвращаться обратно к A).
Что, если у меня есть множество шардов базы данных и есть кэш, материализующий данные из множества таких шардов?
Решение в основном тем же, и единственная проблема, которую нужно решить – опять же, упорядочивание (как вы помните, порядок – наиважнейшее ключевое слово при работе с распределенными системами). В зависимости от того, с какой системой вы работаете, вы, возможно, сможете пользоваться векторными часами, а если у вас есть еще и Spanner (везет же вам), то можно просто воспользоваться TrueTime для разрешения всех проблем с упорядочиванием, поэтому состояния кэша никогда не будут откатываться вспять.
Что, если я кэширую данные из множества источников, файлов, баз данных, ответов, т.д.?
При использовании кэша вы имеете дело с распределенной системой. Если вы кэшируете информацию из файлов, и баз данных, и ответов от других сервисов, то вам приходится судить обо всех них сразу как о распределенной системе. Если вы оказались в такой ситуации, и она требует инвалидации кэша, то вполне возможно, что придется рассуждать по обстоятельствам.
Здесь процитирую Марка Брукера:
Слишком много таких систем, в которых эта задача решается по ситуации. В результате возникает представление, будто инвалидация кэша крайне сложна… ситуативные суждения о распределенных вариантах дизайна часто приводят к провалу.
Что, если я не храню данные в Postgres?
При проектировании кэша нужно держать в уме, какие возможности поддерживает ваша база данных. Именно тут вступает в игру одно из вышеупомянутых требований:
Чтобы можно было корректно обращаться с распределенной системой, кэш и база данных должны быть осведомлены друг о друге.
Имея дело с кэшами, вы работаете с распределенной системой. Соответственно, считайте кэш распределенной системой. Если ваша база данных не поддерживает синхронного возвращения модифицированных данных, но поддерживает бинлог (как, например, MySQL), то можно:
- Обрезать бинлог при изменениях (и на данном этапе можно собирать измененные пользовательские id).
- Присылать инвалидацию от отсекателя.
Здесь снова засада. Необходимо выполнять логику выбора, например, находить ключи инвалидации, когда чей-то адрес меняется. Для этого требуется мгновенный снимок операции считывания, выполняемой строго по времени, в тот момент, когда происходит транзакция записи. Существует немало баз данных, в которых предоставляется такая возможность (она не слишком затратная, если базе данных требуется хранить историю в течение всего нескольких минут, в данном случае – пока нужны эти мгновенные снимки). Итак, если вы хотите изменить логику сбора инвалидационных ключей, так, чтобы эта операция происходила асинхронно (вне транзакций базы данных), то база данных вообще должна поддерживать мгновенные снимки операций считывания, выполняемые по времени. В зависимости от схемы кэша, имеющихся у вас примитивов версионирования и от конкретных случаев вполне возможно, что вы сможете держать ваши кэши в актуальном виде и без базы данных, которая поддерживала бы назначаемые по времени операции считывания.
Что насчет усиления записи?
Теперь, чтобы держать кэши в обновленном виде, нам, возможно, придется очень дорого платить за усиление записи (синхронное или асинхронное), причем, такое усиление может быть неограниченным. Например, если я подружусь с Алисой, а у нее уже миллион друзей, то понадобится обновить в кэше не менее миллиона записей.
Именно здесь придется идти на компромиссы, в зависимости от имеющихся рабочих нагрузок (на чтение и на запись). Иногда мощности можно сэкономить, применяя TTL – время жизни данных (таким образом можно полностью избавиться от инвалидации).
Что делать, если источник истины находится вне базы данных?
Допустим, данные хранятся в обычных файлах. Если данные неизменяемые, то никакой инвалидации производить не требуется. И хорошо. Если же данные в файлах поддаются изменению, а базу данных вы не используете, то вы должны предоставить подмножество возможностей базы данных, чтобы, как минимум, синхронизировать операции доступа. Далее «порядок» следования данных в мутационных потоков можно предзагрузить и затем упорядочивать события инвалидации кэша в рамках все той же общей последовательности.
Заключение
Если подходить к кэшированию как к задаче на работу с распределенными системами (а это и есть такая задача), то вся суть ее сводится к компромиссам. Вы идете на компромисс между согласованностью кэша и издержками на координацию кэша, взвешивая, какой вариант лучше всего подходит для ваших рабочих нагрузок и удовлетворяет вашим требованиям. При кэшировании в принципе важнее всего подобрать такой компромисс. Теперь, когда вы его сделали и реализовали самый лучший протокол инвалидации кэша (и корректность этого протокола доказуема на уровне TLA+), в кэшах все равно может возникать несогласованность, так как правильно обрабатывать инвалидацию кэша очень сложно. В этом посте подробно рассказано, почему настолько сложно реализовать инвалидацию кэша, и как справиться с этой сложностью.
