Всем привет, меня зовут Сергей Петренко, я программист в Tarantool. Сегодня мы посмотрим, с какими трудностями сталкивается клиент, когда вместо того чтобы общаться с системой, расположенной на одном инстансе, начинает общаться с распределенной системой. И разумеется, поговорим о том, как эти трудности преодолеть. Я расскажу, что такое линеаризуемость, как мы ее реализуем в Tarantool и как это делают другие СУБД. В завершение мы поговорим о накладных расходах от линеаризуемости.
Эта статья написана по моему одноименному докладу на SmartData 2023. Его можно посмотреть в записи.
Проблемы масштабирования
Один мой знакомый сказал: «К сожалению, число пользователей прибавляется». В результате приложение, хранящее данные на одном сервере БД, рано или поздно упирается в производительность и живучесть этого сервера. Репликация помогает преодолеть эти ограничения. Допустим, вдобавок к основному экземпляру БД, мастеру, мы подняли ещё несколько его копий — реплик. Теперь мы можем снять нагрузку на чтение с мастера и распределить её между всеми репликами. К тому же теперь в случае падения мастера одна из реплик становится новым мастером и принимает на себя всю нагрузку на запись.
Асинхронная репликация
Самый очевидный подход к репликации — это асинхронная репликация. Давайте просто запустим на мастере фоновый поток, который будет пересылать данные с него на реплику.
Это, конечно, избавляет нас от единой точки отказа в лице мастера и решает проблему с перегруженностью мастера. Однако появляются аномалии, которые при доступе к одному лишь мастеру пользователь наблюдать не мог.
Чтение старых данных
Вот клиент. Он пока не знает, что ему предстоит, поэтому улыбается. Он обращается к мастеру и просит записать значение «foo», которое мастер подтверждает. После этого клиент звонит по телефону своему другу, говорит, что он все записал, и друг идет это читать. Но его чтение попадает на реплику, и оказывается, что на реплике ещё нет записи. Ничего удивительного в этом нет, потому что сам процесс репликации асинхронный. Если друг попробует еще раз прочитать это значение, он его уже, скорее всего, увидит.
Потеря данных
А вот другая ситуация: пользователь записывает значение «foo». Мастер подтверждает запись, а затем падает, не выполнив репликацию «foo». Теперь запись была подтверждена, но пользователи её не увидят до тех пор, пока мастер не восстановится и не возобновит репликацию.
Конфликты
А ещё с асинхронной репликацией возможны конфликты. Пользователь пытается записать «foo = 1» на мастере. Мастер применяет запись и падает, не успев ответить пользователю и реплицировать запись. В такой ситуации ни пользователь, ни какая-либо из реплик кластера не знает, была выполнена запись или нет. Пользователь предполагает, что запись не выполнена, и пытается выполнить запись на новом мастере, например «foo = 2». Новый мастер подтверждает запись. После этого поднимается старый мастер. В случае, если репликация настроена «от всех ко всем», запись «foo = 1» со старого мастера попадает на все узлы кластера и перезаписывает «foo = 2». В результате любое последующее чтение вернёт неподтверждённую запись «foo = 2», а запись «foo = 1», для которой ответ вообще не был получен. К слову, старый мастер, наоборот, будет отвечать, что «foo = 2».
Синхронная репликация
От части описанных проблем помогает синхронная репликация: пусть мастер подтверждает запись клиенту только после того, как эта запись будет реплицирована на некоторое число реплик, называемое кворумом.
Нет потери данных
Теперь, если клиенту подтвердили какую-то запись, это значит, что эта запись попала не только на мастера, но и хотя бы на одну реплику. И если после подтверждения записи мастер упадет, клиент спокойно может читать подтвержденные данные с реплики.
Нет конфликтов
При правильной настройке кворума (кворум — большинство узлов в кластере, N / 2 + 1) синхронная репликация защищает и от конфликтов. Клиент пытается записать «foo = 1» на мастере, но мастер падает, не успев подтвердить запись клиенту. Клиент предполагает, что мастер ничего не записал, и выполняет запись на новом мастере. Новый мастер, прежде чем подтвердить запись, распространяет запись на кворум реплик. Когда вернётся старый мастер, он снова попытается реплицировать запись «foo = 1», но её никто не примет, потому что из двух конфликтующих записей только одна может оказаться на большинстве узлов и только эта запись («foo = 2») считается применённой. А старая запись будет отменена. Более того, старый мастер со временем получит «foo = 2» по репликации, и данные в кластере станут консистентными.
Чтение старых данных
К сожалению, справиться с чтением старых данных синхронная репликация не помогает: несмотря на то, что мастер отвечает клиенту после применения записи на кворуме узлов, даже после полученного подтверждения новый запрос на чтение может прийти на узел вне кворума, который ещё не получил новую запись.
Конечно, чтения старых данных бы удалось избежать при кворуме N, то есть при записи на все узлы в кластере перед подтверждением записи клиенту. Но при кворуме N на запись падение любого узла в кластере приводит к тому, что кластер становится недоступен на запись. К тому же «без дополнительных предосторожностей» чтение устаревших данных возможно и с кворумом N. Я буду говорить про это подробнее ниже.
Итак, с частью проблем при переходе от хранения данных на одном узле к репликации мы справились, но основная аномалия — чтение старых данных — всё ещё остаётся.
Линеаризуемость
В идеале нам бы хотелось сохранить преимущества репликации — распределение нагрузки на чтения и увеличенную доступность, — сохраняя при этом для пользователя иллюзию, будто он общается с единственным экземпляром БД. Это свойство называется линеаризуемостью. Давайте сначала посмотрим на ее определение. Линеаризуемость — это свойство одного объекта и операций чтения и записи в него. Какой это объект, решает имплементация. То есть это может быть строка в таблице, это может быть вся таблица целиком или вы можете обеспечивать линеаризуемость сразу для всей базы. Чуть позже мы увидим, что большая часть реализаций обеспечивает «честную» линеаризуемость — сразу для всей базы.
Объект называется линеаризуемым, если любая операция над ним выполняется атомарно в какой-то момент времени между получением системой запроса и отправкой ответа клиенту. И более того, любое чтение возвращает результат всех выполненных на момент его прихода записей.
Давайте посмотрим на примере, что линеаризуемая система нам может вернуть в ответ, а что не может:
Здесь у нас нарисованы три клиента. Цветными овалами отмечены моменты времени, когда они ждали ответа на запрос от базы. То есть когда овал начинается, клиент отправил запрос в базу. База для нас здесь какой-то черный ящик, мы не говорим, на какой сервер клиент отправил запрос. Овал кончается, когда база ответила клиенту.
Заметьте, что чтение происходит строго после того, как пришёл ответ на первую запись, и одновременно с выполнением второй записи. То есть ответ на запрос на чтение приходит между отправкой второго запроса на запись и получением на него ответа. Линеаризуемость устанавливает порядок только между первой записью и чтением. Вторая запись и чтение могут быть выполнены в любом порядке.
Возможен и такой вариант:
Если с точки зрения клиента история исполнения операций будет выглядеть так, то эта система не линеаризуемая. То есть клиент получил в ответ на чтение «foo» пустое значение. Это чтение старых данных в классическом виде, потому что чтение было отправлено строго после того, как была завершена запись «foo = 1», и, значит, оно было должно вернуть хотя бы «foo = 1».
Вот другой пример:
Чтение вернуло устаревшие данные, да еще и записи поменялись местами. Я вам рассказывал, как это может произойти, в примере с конфликтами в асинхронной репликации. На картинке это не показано, но последующие чтения вернут «foo = 1» вместо «foo = 2». Это тоже нарушит линеаризуемость, потому что запись «foo = 2» была отправлена уже после того, как была подтверждена запись «foo = 1». Записи обязаны применяться в том же порядке.
А линеаризуемая история исполнения может выглядеть так:
То есть чтение вернуло «foo = 1».
Или может так:
Чтение здесь вернуло «foo = 2». Линеаризуемость не запрещает прочитать данные, которые были записаны позже.
Достижение линеаризуемости
Давайте теперь поговорим, как получить линеаризуемость в реальной системе. И начнем с игрушечного примера, когда у нас вообще нет проблем и в кластере всего один узел. Понятное дело, что один узел всегда обеспечивает линеаризуемость. Он просто выполняет все приходящие операции в порядке их получения.
Теперь узлов резко стало пять. На самом деле вся идея линеаризуемости заключается в том, чтобы найти в кластере один узел, который видел все операции — и чтения, и записи. А потом расположить операции в истории исполнения в том же порядке, в каком их расположил этот узел.
Чтобы один узел видел все операции, нужно, чтобы кворумы на чтение и на запись для любых двух операций пересекались. Например, когда у вас пять узлов, вы можете и писать с кворумом 3, и читать с кворумом 3. Это необходимое условие линеаризуемости. Тогда любой кворум на чтение (3) пересечётся с кворумом каждой из уже подтверждённых записей хотя бы по одному узлу. Так чтение будет знать о том, какие записи уже были подтверждены на момент его прихода. Можно сказать, что операции чтения и записи исполняются в том порядке, в котором их наблюдают узлы из пересечения кворумов.
Итак, если у нас N узлов в кластере и мы читаем с кворумом R и пишем с кворумом W, то для линеаризуемости необходимо, чтобы R + W было больше, чем N. Впервые мы столкнулись с этим ещё на примере с синхронной репликацией, когда я говорил, что кворум на запись N избавил бы нас от чтения устаревших данных. Действительно, если взять W = N и R = 1, W + R > N, линеаризуемость достигается. Но, как я уже говорил, любой вариант с экстремальным кворумом (W = N или R = N) негативно влияет на доступность операций чтения или записи. Для нечётных N оптимальными кворумами будут пары R, W = N / 2 + 1, например N = 3, R = W = 2, а для чётных N — W, R = N / 2 + 1, N / 2 (или наоборот) — например, имея всего два узла, можно писать с кворумом 2 и читать без кворума (с «кворумом» 1). Имея четыре узла, можно писать с кворумом 3 и читать с кворумом 2.
Важно помнить, что линеаризуемое чтение с «кворумом» 1 — это не обычное чтение. Узел, выполняющий чтение, не должен дополнительно опрашивать кворум, но всё равно должен дождаться момента, когда лидер подтвердит все записи, находящиеся на узле, прежде чем читать.
Линеаризуемость в Raft
Подход, описанный выше, реализует алгоритм Raft. Про Raft я уже писал в предыдущих статьях (раз, два), а сейчас нам достаточно знать, что Raft автоматически выбирает лидера и кворум на запись в Raft — W = N / 2 + 1. С кворумом на чтение всё сложнее, мы поговорим об этом дальше.
В Raft лидера выбирают большинством голосов — то есть кворумом N / 2 + 1. Можно сказать, что это кворум на чтение, потому что голосующие отдают голос за кандидата, только если он обладает более актуальными данными, чем они. Для того чтобы узнать это, нужно прочитать его состояние.
Благодаря этим кворумам каждый вновь избранный лидер гарантированно имеет у себя в журнале все подтвержденные на момент его избрания записи. Дальше уже новоиспеченный лидер делает так, чтобы журналы всех реплик совпадали с его журналом. В результате Raft гарантирует, что подтверждённые записи расположены в журналах всех узлов кластера в одном и том же порядке. Это линеаризуемость для записей, но у нас по-прежнему нет линеаризуемости для чтения. Давайте ей займемся.
Наивная идея выглядит так: давайте просто читать с лидера. Раз уж он знает, какие записи он уже подтвердил, он легко может отвечать на любые чтения. Делать для чтения видимыми подтверждённые записи и не показывать ещё не подтверждённые. Это работает ровно до тех пор, пока кто-нибудь не сместит лидера. Чтобы сместить лидера, совсем не обязательно его об этом уведомлять, всё голосование, в процессе которого большинство узлов договорится о новом лидере, может пройти вообще незамеченным для старого лидера. Новый лидер даже может успеть подтвердить новые записи до того, как старый лидер узнает, что его сместили.
Старый лидер, конечно, уже не сможет подтвердить ни одну новую запись (вспоминаем линеаризуемость для записей), но он по-прежнему может обрабатывать чтения и возвращать устаревшие результаты. Подход с чтением на лидере не работает. Нужно, чтобы лидер был «не уверен в себе» и перед каждым чтением опрашивал кворум, чтобы убедиться, что его не сместили.
Так в Raft и предлагают сделать. То есть если лидер выполняет линеаризуемое чтение, он запоминает номер последней подтверждённой записи, выпускает хартбиты ко всем своим фолловерам, дожидается ответа от большинства. Если он всё еще лидер, то он просто выполняет чтение.
Если выяснилось, что на момент, когда ему вернулись ответы, он уже не лидер, он возвращает ошибку, не выполняя чтение. Он поймет это, если один из ответов содержал больший терм, чем тот, в котором узел является лидером.
Этот подход предлагает автор Raft, Диего Онгаро, в своей диссертации. Этой же идеей пользуется реализация etcd/raft и, соответственно, все, кто ей пользуется: etcd, CockroachDB, TiDB. В их реализации есть только одно отличие. Они заметили следующее: вообще-то, лидер не должен быть настолько не уверен в себе, потому что после того, как он пообщался с кворумом, он знает, что еще какое-то время его никто не сместит.
Новые выборы начинаются, только если большинство не получало сообщений от действующего лидера в течение определённого тайм-аута начала новых выборов. Если лидер только что получил ответы на heartbeat от большинства, он может быть уверен не только в том, что на момент отправки им heartbeat в кластере не начинались выборы, но и в том, что они не начинались ещё некоторое время после отправки. Соответственно, все запросы на чтение, пришедшие в течение этого промежутка времени (предположим, лидер его знает), можно обрабатывать, не консультируясь с кворумом. Соответственно, не нужно отправлять раунд хартбитов на каждое чтение, достаточно полагаться на хартбиты, которыми и так время от времени перебрасываются лидер и реплики. Линеаризуемое чтение будет ждать ответа от большинства, только если последний обмен хартбитами был слишком давно.
На самом деле лидер никогда не знает точно промежуток времени, в течение которого выборы не начинались. Каждый раз «точный» промежуток зависит от того, насколько по-разному идут часы на узлах. Поэтому этот промежуток задаётся программно, например, как какая-то доля тайм-аута начала новых выборов. Вместе с ним задаётся максимально допустимое расхождение часов узлов, при котором алгоритм может работать (в реальных системах это что-то около сотен миллисекунд).
И вроде бы все хорошо — мы почти никогда не платим повышенной задержкой за чтение. Но есть нюанс: мы можем читать только на лидере. А ведь изначально нашей целью было снять нагрузку на чтение с лидера. Поэтому мы в Tarantool мы пошли своим путём и сделали так, чтобы линеаризуемые чтения не нагружали лидера.
Линеаризуемость в Tarantool
В Tarantool линеаризуемые чтения может выполнять не только лидер, но и любая из реплик.
Алгоритм действий при линеаризуемом чтении на реплике следующий:
- Опросить кворум, найти среди ответивших узел с наибольшим количеством выполненных записей.
- Дождаться, пока реплика выполнит столько же операций записи.
- Дождаться, пока все операции в журнале до этого места будут либо подтверждены, либо откачены новым лидером.
- Выполнить чтение.
Почему это не нарушает линеаризуемость? Реплика, в отличие от лидера, конечно, не знает, какая запись была подтверждена последней, но знает следующее: если лидер подтвердил какую-то запись, то она точно есть в журналах большинства реплик. Во время опроса кворума реплика обязательно встретит хотя бы один узел, выполнивший последнюю подтверждённую на лидере запись (если, конечно, кворумы на чтение и запись пересекаются). Когда узел дождется получения всех записей, о которых он узнал от кворума, он получит и эту запись. Когда он дождется, пока все записи в его журнале будут выполнены, он дождется, пока эта запись будет выполнена, и может выполнять чтение.
Да, этот подход, возможно, заставит его подождать чуть больше. Может, он даже прочитает что-нибудь лишнее, потому что мы не знаем наверняка, какая запись была последней подтвержденной. Но мы точно прочитаем последнюю подтвержденную запись и не вернём устаревшие данные.
Давайте разберёмся на примере. Теперь у нас лидер сделал две записи, обе подтвердил, но одна из реплик не успела получить вторую запись. Что будет, если эта реплика станет выполнять чтение? Реплика общается с кворумом, то есть с другой репликой (лидер в этом процессе может не участвовать, если кворум набран без него), и узнаёт, сколько записей она успела сделать. Другая реплика отвечает, что две. Значит, наша реплика должна подождать, пока не выполнит две записи. Дождавшись этого момента, а затем и момента, когда все, что есть в её журнале, будет подтверждено, реплика выполняет чтение и читает «foo = 2». Линеаризуемость не нарушена.
Теперь сравним подход к линеаризуемости в etcd, в каноническом Raft и у нас. Etcd и прочие читают только на лидере. Мы вообще не нагружаем лидера чтениями. У нас фолловеры могут, не спрашивая лидера, между собой договориться и найти, что можно прочитать, а что нельзя. Но благодаря тому, что etcd читает на лидере, они могут полагаться на хартбиты, которые лидер и так время от времени рассылает.
Мы же вынуждены на фолловере, который никакие хартбиты по Raft не посылает, эти хартбиты посылать дополнительно (в ответ на хартбит приходит информация о количестве сделанных записей): мы копим небольшую пачку чтений на фолловере и для них всех разом выпускаем раунд хартбитов. Но в любом случае у нас есть поток хартбитов между фолловерами, выполняющими линеаризуемые чтения, и эти хартбиты рассылаются гораздо чаще, чем того требует Raft.
При этом в случае etcd и чтения с лидера Latency для линеаризуемых чтений почти всегда такая же, как и для обычных чтений: там, кроме редких случаев, можно просто прочитать состояние лидера, не спрашивая кворум. А у нас Latency всегда возрастает на RTT от реплики до самого дальнего узла в кворуме, потому что реплика сама по себе никогда не знает, какая операция была последней подтвержденной. Чтобы это узнать, ей нужно опросить кворум.
Цена линеаризуемости
С разными подходами к линеаризуемости разобрались. Давайте теперь посмотрим, чего же это стоит для пользователя — сделать свою систему линеаризуемой.
Сильно снижает устойчивость к сбоям. В то время как некворумная система у нас будет работоспособна до тех пор, пока работает хотя бы один узел, линеаризуемая система способна обрабатывать записи до тех пор, пока доступно большинство узлов, а чтения — пока доступно большинство, или, при чётных N, половина узлов.
Проблемы с двумя дата-центрами. Если ваша база расположена всего в двух дата-центрах, потеря связи между ними или какие-то проблемы в одном из дата-центров сразу же вас лишают кворума и вы уже не можете писать. Читать, скорее всего, можете, потому что при чётном N кворум для чтения чуть меньше, N / 2. Но если у вас три дата-центра, таких проблем нет.
Страдает задержка и на запись, и на чтение. Некворумная система получает запрос от клиента, обрабатывает его локально на сервере, на котором он пришел, и возвращает ответ. Линеаризуемая система перед обработкой запроса общается с кворумом, и в результате Latency увеличивается на RTT от узла, выполняющего операцию, до самого далёкого узла кворума.
Когда без линеаризуемости не обойтись
Ради чего же все это тогда, если от линеаризуемости столько минусов? Ради простоты написания приложений. Все-таки очень заманчиво общаться с базой данных, вообще не думая о том, распределенная она или нет. Хочется записать что-нибудь, дождаться ответа, что всё записано, и больше ни о чем не думать. Это насколько заманчиво, что в документации к Google Spanner так и написано: «Включайте линеаризуемость всегда и не включайте, только если вы хорошо всё прикинули и поняли, что с ней производительности вам хватать не будет».
Дополнительное чтение
- Документация Tarantool — как включать линеаризуемые чтения.
- Блог CockroachDB. Это ребята, которые взяли библиотеку etcd/raft. Они очень хорошо в своем блоге сравнивают себя с Google Spanner и в целом про линеаризуемость хорошо пишут, со множеством подробностей. Рекомендую.
- Aphyr, автор Джепсен, хорошо рассказывает, какие вообще бывают уровни консистентности. По ссылке будет пирамидка из уровней консистентности, и линеаризуемость там вторая сверху. Есть еще кое-что посильнее, не расскажу что — зайдите по ссылке и узнаете. Каждый уровень в пирамидке кликабельный.
- Снова Aphyr. Очень хорошая статья про то, что вообще такое консистентность и почему мы определяем её именно так.
Питер Бейлис, исследователь распределенных систем, сравнивает линеаризуемость и сериализуемость, объясняет, что это совсем не одно и то же.
