Raft

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

Синхронная репликация появилась в релизе 2.5.1, а в конце октября в релизе 2.6.1 появилась поддержка автоматических выборов лидера на основе Raft.

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

1. Репликация вообще

Прежде чем погрузиться в дебри алгоритма выборов лидера, зададимся вопросом: откуда вообще возникла необходимость в таких алгоритмах?

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

Со всеми же, кто остался, продолжим разговор о репликации. Она бывает двух видов.

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

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

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

Выглядит асинхронная репликация так:


Слева мастер. Он отвечает клиенту ок, как только запишет транзакцию в свой журнал.

или так =(


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

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

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

Выглядит синхронная репликация так:


Мастер слева. Прежде чем отвечать клиенту, он отправляет данные реплике и дожидается её ответа.

Что ни делай с синхронной репликацией, потери подтверждённых данных не произойдёт:


Пусть мастер и отказал, на реплике транзакция осталась.

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

2. Лидер и его выборы

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

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

Как же нам назначить единственного лидера? Есть два пути. Во-первых, все реплики после пропажи лидера могут ждать, пока внешнее средство не назначит среди них одного лидера. Это может быть, например, администратор, который перевёл один узел из режима read-only в read-write, либо же какой-то внешний инструмент, управляющий репликацией. В таком случае, конечно, удастся назначить единственного лидера, но потребуются лишние действия, и поэтому время простоя кластера будет заметным. Поясню, что я имею в виду: после пропажи лидера нельзя допустить, чтобы транзакций, применённых им, не было на новом лидере. Поскольку лидер у нас источник правды, отсутствие транзакций означало бы, что данные сначала были подтверждены, а затем исчезли. Это особенно важно для синхронной репликации. То есть лидером нельзя назначить абы какой узел. Выбрать нужно тот, который меньше других отстал от старого мастера. Следующим шагом нужно применить все синхронные транзакции, которые не успел применить старый лидер. Нужно ждать их репликации на кворум узлов, а затем рассылать подтверждения этих транзакций.

В общем, работы немало, и делать её руками не очень хочется.

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

К счастью, нам не пришлось изобретать велосипед. Широко известным и хорошо проверенным является алгоритм Raft, который мы и взялись реализовывать.

3. Алгоритм Raft

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

Обычно кластер выглядит так: один узел находится в состоянии leader и может писать в журнал, применять транзакции и так далее. Все остальные узлы находятся в состоянии follower и применяют всё, что получают от лидера. Если follower получит по каналу репликации какую-то транзакцию от не-лидера, он её проигнорирует.

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

Другая часть протокола, которую мы будем рассматривать в этой статье, касается выборов лидера.

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

Всё время существования кластера разделено на логические блоки, называемые термами (term). Они пронумерованы целыми числами начиная с 1, и каждый терм начинается с выборов нового лидера. После того как лидер выбран, он принимает запросы и сохраняет в журнал новые записи, которые рассылает остальным членам кластера.

Чтобы узел был выбран лидером, за него должны проголосовать более половины узлов в кластере. Это гарантирует, что в каждом терме будет выбран либо единственный лидер, либо никто. В некоторых термах выборы могут так и не закончиться назначением лидера. Такое может произойти, если все узлы проголосовали, но ни один из кандидатов не получил большинство голосов. В таком случае начнётся новый терм, а значит будут проведены новые выборы. Все узлы проголосуют заново. Таким образом, рано или поздно один из узлов станет лидером.

Согласно Raft каждый узел может быть в одном из трёх состояний follower, candidate, leader.

Follower состояние, в котором узел может только отвечать на запросы AppendEntries от лидера и RequestVote от кандидатов. Если follower давно не получал ничего от лидера (в течение так называемого Election Timeout), то он переходит в состояние candidate и начинает новый терм, а вместе с тем и новые выборы.

Candidate состояние узла, инициировавшего новые выборы. В этом случае узел голосует сам за себя, а затем рассылает всем членам кластера запросы RequestVote. Ответ на этот запрос поле VoteGranted, принимающее значение true, если узел проголосовал за кандидата. Сам кандидат никогда не отвечает на запросы RequestVote других кандидатов. Он уже проголосовал за себя и больше ни за кого не голосует. Кандидат ведёт подсчёт отданных за него голосов. Как только их становится больше, чем половина всех узлов в кластере, кандидат становится лидером, о чём сообщает всем рассылкой пустого запроса AppendEntries (своеобразный хартбит, который может послать только лидер).

Если с момента начала выборов прошёл Election Timeout, а нужное число голосов так и не собрано, это может означать, что при голосовании никто не получил достаточное количество голосов. В таком случае кандидат инициирует новые выборы, увеличив свой term и повторно разослав другим узлам запрос RequestVote. Чтобы избежать бесконечного цикла из перевыборов, Election Timeout слегка рандомизируется на каждом из узлов. Благодаря этому рано или поздно один из кандидатов первым инициирует новые выборы и соберёт необходимое количество голосов.

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

Если лидер или кандидат внезапно узнаёт от одного из узлов, что начался новый терм (больший, чем тот, в котором они находятся), он сразу же становится followerом. После этого election timeout начинает отсчёт сначала.

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

Состояние узла в журнал не попадает. После перезапуска узел всегда оказывается в состоянии follower.

4. Наша реализация синхронной репликации

Часть протокола Raft, отвечающая за репликацию журналов, была реализована как отдельная задача на три месяца раньше, чем началась работа над выборами лидера.

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

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

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

Особенность журнала Tarantool в том, что он хранит только redo-записи, а не undo. Это значит, что после перезапуска журнал можно проиграть только от начала до конца, повторив все применённые транзакции. Однако журнал нельзя развидеть, то есть отменить транзакцию, прочитанную из журнала. В нём просто нет необходимых для этого структур. Это позволяет сделать журнал компактнее. Структуры, которые нужны для отмены транзакции, хранятся в памяти, и в случае асинхронной репликации освобождаются сразу после успешной записи в журнал, а в случае синхронной либо после подтверждения транзакции кворумом узлов, либо после её отката по таймауту.

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

Из-за этого появилась нужда в новом типе записей в журнале ROLLBACK. Как только на мастере наступает таймаут на ожидание подтверждений от реплик, он вносит в журнал запись ROLLBACK с LSN (порядковым номером) отмененной транзакции. Эта запись, как и все остальные в журнале, пересылается на реплику. Получив такую запись, реплика отменяет неуспешную синхронную транзакцию и все транзакции с большим LSN. Сделать она это может благодаря хранящемуся в памяти undo log. То же самое делает и мастер.

Если же кворум реплик, получивших транзакцию, собран, то репликам нужно сообщить, что транзакция подтверждена. Во-первых, это позволит им освободить undo log. Во-вторых, при восстановлении из журнала им будет нужна информация о том, какие транзакции применены, а какие нет. Для этой цели была добавлена ещё одна служебная запись в журнал CONFIRM.

Поскольку репликация в Tarantool реализована как построчная пересылка записей из журнала мастера репликам, изобретение записей CONFIRM и ROLLBACK сыграло нам на руку: сообщения о подтверждении или откате синхронных транзакций реплики получали по обычному каналу репликации. Не пришлось придумывать, каким образом мастер будет отправлять им системные сообщения. Он просто считывает их из журнала и отправляет как обычные данные. Кроме того, реплики могут без изменений записывать полученные служебные сообщения в свои собственные журналы, что позволило им корректно восстанавливаться, игнорируя отменённые синхронные транзакции.

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

Итак, все транзакции, и синхронные, и асинхронные, первым делом попадают в WAL. После успешной записи асинхронные транзакции сразу коммитятся, а синхронные попадают в специальную очередь limbo, где они ждут своей репликации на кворум узлов. Когда кворум подтверждений собран, транзакция коммитится, а в журнал записывается CONFIRM. Если же произошёл таймаут ожидания подтверждений, в журнал пишется ROLLBACK, а транзакция откатывается вместе со всеми следующими за ней в очереди.

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

По умолчанию, пока транзакции находятся в очереди, их изменения будут видны другим транзакциям. Такой эффект называется грязные чтения, и чтобы с ним бороться, нужно включить менеджер транзакций. В Vinyl дисковом движке Tarantool менеджер транзакций был включен всегда, а в Memtx движке для хранения данных в памяти он появился в релизе 2.6 стараниями Александра Ляпунова, о чём тот расскажет в своей статье.

5. Адаптация Raft к нашему репликационному протоколу

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

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

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

Сам модуль Raft работает в потоке tx (этот поток занимается обработкой транзакций). Каждое изменение состояния (речь о персистентной части состояния, то есть терме и голосе) должно, согласно Raft, попадать в журнал. Как только новое состояние записано, его можно разослать репликам. Для этого tx отправляет всем потокам relay-сообщение, в которое включает и неперсистентную информацию: роль узла в Raft-кластере и, опционально, vclock этого узла. Далее каждый relay отсылает эту информацию подключённой к нему реплике, а реплика, в свою очередь, передаёт информацию в свой модуль Raft.

В Raft состояние журнала узла, то есть присутствующие на узле данные, можно обозначить одним числом: количеством записей в журнале, которое называется log index. В Tarantool его аналогом является LSN log sequence number, порядковый номер, который присвоен каждой транзакции.

Выделяется Tarantool тем, что состояние журнала обозначается не единственным числом, а массивом LSN, называемым vclock. Это наследие асинхронной репликации мастер-мастер, когда все узлы могут писать одновременно. Транзакции каждого узла при этом подписываются не только LSN, но и ID этого узла.

Все узлы кластера имеют свою собственную компоненту в vclock, и, записав транзакцию, пришедшую от другого узла, реплика присваивает его vclock-компоненте порядковый номер транзакции. В кластере из трёх узлов vclock одной из реплик может выглядеть, например, так: {1: 11, 2:13, 3:5}. Это означает, что на этом узле есть все транзакции с порядковым номером до 11 от узла номер 1, все транзакции с порядковым номером до 13 от узла номер 2, и (считаем, что смотрим на vclock узла 3), сам этот узел записал всего 5 транзакций.

Из-за vclock пришлось внести коррективы в нашу реализацию Raft. Во-первых, по умолчанию алгоритм всегда может определить, какой из узлов имеет более свежие данные, сравнив log index. У нас же нужно сравнивать vclock, которые могут быть несравнимыми, например, {1:3, 2:5} и {1:4, 2:1}. Проблемой это не стало, просто голосующие узлы отдают голос только за тех кандидатов, vclock которых строго больше или равен их собственному.

Как уже говорилось, в Tarantool журнал типа redo, а не undo, да ещё и append only. Это уже добавило трудностей. Дело в том, что хотя большинство узлов и отдало голос за кандидата, меньшинство может иметь более новые данные предыдущего лидера. Поскольку судьбой кластера теперь управляет новый лидер, это меньшинство больше не может работать. Нужно удалить данные таких узлов и заново подключить их к кластеру. Эта операция называется rejoin. А в алгоритме Raft такой трудности не возникало: меньшинство просто отрезало концы своих журналов так, чтобы соответствовать журналу лидера.

6. Конфигурация Raft

6.1. Режим работы узла

Чтобы узел участвовал в выборах лидера, в его конфигурации нужно указать опцию election_mode.

box.cfg{    election_mode = "off", -- значение по умолчанию}

election_mode можно выставить в одно из следующих значений:

• off Raft не работает. При этом узел будет получать и запоминать номер текущего терма. Нужно это для того, чтобы в момент включения Raft узел сразу включился в нормальную работу кластера.
• voter узел будет голосовать за других кандидатов, но сам никогда не будет начинать выборы и выдвигать свою кандидатуру. Такие узлы полезны для ограничения набора узлов, из которых может быть выбран лидер. Скажем, можно сделать кластер из трёх узлов: двух кандидатов и одного голосующего. Тогда при отказе лидера второй из кандидатов будет сразу же выигрывать выборы, набрав большинство голосов (2 из 3: свой собственный и голос голосующего узла).
  
  Кроме того, эта настройка полезна, если нужно заставить лидера сложить свои полномочия, не выключая при этом на нём Raft. Если текущего лидера переконфигурировать в voter, то он сразу же станет read-only и перестанет отправлять лидерские хартбиты followerам. По прошествии таймаута на отказ лидера (election timeout) followerы начнут новые выборы, и лидером будет выбран другой узел.
• candidate узел может начать выборы, как только обнаружит, что лидера нет. Также этот узел может голосовать за других кандидатов, но только если он сам ещё не проголосовал за себя в текущем терме.

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

Требование Raft к выборам лидера: кворум, равный N/2 + 1 голосу, вместе с запретом голосовать более одного раза за выборы. Это гарантирует, что победить в выборах может не более, чем один узел.


Состояния трёх узлов кластера в двух термах. В терме t1 лидером стал s1, поскольку он первым разослал запрос на голос. Когда s1 отказал, первым это заметил s2, он успел первым послать запрос на голос и стал лидером в терме t2. Когда s1 вернулся, он стал простым followerом.

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

Vclock векторные часы; структура, показывающая, какие данные на узле есть, а каких нет. Она представляет собой массив порядковых номеров транзакций, которые попали в журнал на этом узле. Все узлы кластера имеют свою собственную компоненту в vclock, и, записав транзакцию, пришедшую от другого узла, реплика присваивает его компоненте vclock порядковый номер транзакции. В кластере из трёх узлов vclock одного из узлов может выглядеть так: {1: 11, 2:13, 3:5}. Это означает, что на этом узле есть все транзакции с порядковым номером до 11 от узла номер 1, все транзакции с порядковым номером до 13 от узла номер 2, и (считаем, что смотрим на vclock узла 3), сам этот узел записал всего 5 транзакций.

В случае синхронной репликации, при условии, что кворум на подтверждение синхронных транзакций выставлен не меньше, чем N/2+1, голосующие выберут лидера, журнал которого точно содержит все подтверждённые синхронные транзакции. Действительно, раз для подтверждения транзакции она должна попасть хотя бы на N/2+1 узлов, и для выбора нового лидера нужно, чтобы он получил голоса хотя бы N/2 + 1 узлов, то эта транзакция будет в журнале хотя бы одного из проголосовавших. А значит она будет и в журнале нового лидера.

6.2. Таймаут на перевыборы

Важный элемент Raft перевыборы. Они позволяют бороться с ситуацией, когда ни один из кандидатов не набрал кворум голосов. Работает это так: кандидат собирает голоса за себя в течение election timeout. Если достаточное количество голосов так и не собрано, и лидер не заявил о себе, кандидат начинает новые выборы, увеличив номер терма. Election timeout зависит от опции конфигурации и рандомизируется в пределах 10 % от её значения.

Настраивается election timeout так:

 box.cfg{    election_timeout = 5, -- значение по умолчанию, в секундах}

6.3. Кворум голосов за кандидата

Количество голосов, которое должен получить узел перед тем, как стать лидером, конфигурируется только вместе с кворумом синхронной репликации.

box.cfg{    replication_synchro_quorum = 1, -- значение по умолчанию}

В случае синхронной репликации имеет смысл любое значение, кроме 1. Кворум узлов, применивших транзакцию, считается так: 1 за успешную запись транзакции в журнал на мастере + 1 за каждую реплику, применившую транзакцию.

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

Для выборов лидера значение кворума нельзя ставить меньше, чем N/2 + 1, где N количество голосующих узлов в кластере (не всех узлов, а именно голосующих, то есть тех, кто сконфигурирован в election_mode = candidate или election_mode = voter). В противном случае при первых же выборах может появиться несколько лидеров.

Соответственно, для того, чтобы корректно добавлять в кластер новые голосующие узлы, действовать нужно так:

1. Подключить к кластеру реплику с election_mode = off.
2. Дождаться, пока реплика инициализируется и начнёт нормально работать.
3. При необходимости увеличить replication_synchro_quorum так, чтобы он был не меньше, чем N/2 + 1 (N количество голосующих узлов + новая реплика).
4. Включить Raft на реплике, выставив election_mode=voter либо candidate.

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

Если нужно вывести голосующую реплику из кластера, то сперва необходимо её отключить и только после этого уменьшить кворум, но не ниже значения N/2 + 1.

6.4. Coming soon

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

box.cfg{replication_synchro_quorum = "N / 2 + 1", -- значение по умолчанию}

Кворум будет обновляться по формуле при каждой вставке и удалении из спейса _cluster, который хранит информацию обо всех зарегистрированных в кластере узлах. При этом в формулу будет подставляться параметр N, равный количеству записей в спейсе _cluster. Вычисление по формуле будет применяться и для кворума синхронной репликации, и для кворума на голоса в выборах.

Заметим, что отказ одного из узлов не повлечёт за собой изменение кворума. Чтобы понизить кворум, нужно будет удалить узел из спейса _cluster. Tarantool никогда не удаляет узлы из _cluster самостоятельно, это может сделать только администратор.

7. Мониторинг кластера Raft

Для мониторинга состояния Raft можно пользоваться таблицей box.info.election, выглядит она примерно так:

box.info.election---- state: leader  vote: 1  leader: 1  term: 2...

Здесь:

state состояние текущего узла, оно может быть follower, leader, candidate или none.

term номер текущего терма.

leader replica_id узла, который является лидером в этом терме.

vote replica_id узла, за который этот узел голосовал.

Vote и leader не обязаны совпадать. Может оказаться, что этот узел тоже был кандидатом и проголосовал сам за себя. Но потом какой-то другой кандидат его опередил и стал лидером первым.

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

Кроме того, все свои действия Raft подробно журналирует:

2020-11-27 14:41:35.711 [7658] main I> Raft: begin new election round2020-11-27 14:41:35.711 [7658] main I> Raft: bump term to 2, follow2020-11-27 14:41:35.711 [7658] main I> Raft: vote for 1, follow2020-11-27 14:41:35.712 [7658] main/116/Raft_worker I> Raft: persisted state {term: 2, vote: 1}2020-11-27 14:41:35.712 [7658] main/116/Raft_worker I> Raft: enter leader state with quorum 1

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

Кроме того, журналируется терм, в котором находится узел, и причины, по которым он не голосует за другие узлы, если вдруг получает от них запрос на голос. Среди таких причин несравнимые vclockи у голосующего и кандидата, или же то, что в текущем терме лидер уже известен.

8. Заключение

В Tarantool 2.6 появилась встроенная функциональность для автоматических выборов лидера на основе Raft. Теперь можно обходиться без внешних инструментов для смены мастера.

Это позволяет держать все настройки в одном месте файле конфигурации Tarantool. Как бонус: обновление кворума вскоре будет автоматизировано, что ещё больше повысит удобство использования.

Также достоинствами встроенной реализации являются большая надёжность и максимально быстрая реакция на происходящие события.

Кроме того, теперь встроенная функциональность Tarantool позволяет небольшими усилиями написать автоматический failover. Подробный пример на lua можно найти в нашем репозитории с примерами. Осмотритесь там. Помимо выборов лидера там есть много полезных образцов кода.

В качестве домашней работы рекомендую посмотреть запись вебинара, где я рассказал про выборы лидера в Tarantool 2.6 и показал ещё несколько примеров. Стоит также напомнить, что скачать Tarantool можно на официальном сайте, а получить помощь в Telegram-чате.

Tarantool это платформа для in-memory вычислений, где упор всегда делался на горизонтальную масштабируемость. То есть при нехватке мощности одного инстанса нужно добавить больше инстансов, а не больше ресурсов одному инстансу.

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

Задача реализации синхронной репликации стояла перед командой разработчиков Tarantool долгие годы, к ней было совершено несколько подходов. И вот теперь в релизе 2.6 Tarantool обзавёлся синхронной репликацией и выборами лидера на базе алгоритма Raft.

В статье описан долгий путь к схеме алгоритма и его реализации. Статья довольно длинная, но все её части важны и складываются в единую историю. Однако если нет времени на 60 000 знаков, то вот краткое содержание разделов. Можно пропустить те, которые уже точно знакомы.

1. Репликация. Введение в тему, закрепление всех важных моментов.
2. История разработки синхронной репликации в Tarantool. Прежде чем переходить к технической части, я расскажу о том, как до этой технической части дошли. Путь был длиной в 5 лет, много ошибок и уроков.
3. Raft: репликация и выборы лидера. Понять синхронную репликацию в Tarantool без знания этого протокола нельзя. Акцент сделан на репликации, выборы описаны кратко.
4. Асинхронная репликация. В Tarantool до недавнего времени была реализована только асинхронная репликация. Синхронная основана на ней, так что для полного погружения надо сначала разобраться с асинхронной.
5. Синхронная репликация. В этом разделе алгоритм и его реализация описаны применительно к жизненному циклу транзакции. Раскрываются отличия от алгоритма Raft. Демонстрируется интерфейс для работы с синхронной репликацией в Tarantool.

1. Репликация

Репликация в базах данных это технология, которая позволяет поддерживать актуальную копию базы данных на нескольких узлах. Группу таких узлов принято называть репликационная группа, или менее формально репликасет. Обычно в группе выделяется один главный узел, который занимается обновлением/удалением/вставкой данных, выполнением транзакций. Главный узел принято называть мастером. Остальные узлы зовутся репликами. Ещё бывает мастер-мастер репликация, когда все узлы репликасета способны изменять данные.


Репликация призвана решить сразу несколько задач. Одна из наиболее частых и очевидных наличие резервной копии данных. Она должна быть готова принимать клиентские запросы, если мастер откажет. Ещё одно из популярных применений распределение нагрузки. При наличии нескольких инстансов БД клиентские запросы между ними можно балансировать. Это нужно, если для одного узла нагрузка слишком велика, или на мастере хочется иметь наименьшую задержку на обновление/вставку/удаление записей (латенси, latency), а чтения не страшно распределить по репликам.

Типично выделяется два типа репликации асинхронная и синхронная.

Асинхронная репликация

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

Цикл жизни асинхронной транзакции сводится к следующим шагам:

• создать транзакцию;
• поменять какие-то данные;
• записать в журнал;
• ответить клиенту, что транзакция завершена.

Параллельно с этим после записи в журнал транзакция поедет на реплики и там проживёт тот же цикл.


Такой репликации хватает для большинства задач. Но здесь есть не всегда очевидная проблема, которая для некоторых областей разработки делает асинхронную репликацию либо вовсе не применимой, либо её нужно обкладывать костылями, чтобы получить желаемый результат. А именно: мастер-узел может отказать между шагами 3 и 5 на картинке. То есть после того, как клиент получил подтверждение применения транзакции, но до того, как эта транзакция заедет на реплики.

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

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

Решать эту проблему можно по-разному. Есть способы остаться на асинхронной репликации и действовать в зависимости от ситуации. В случае Tarantool можно написать логику своего приложения таким образом, чтобы после успешного коммита не торопиться отвечать клиенту, а подождать явно, пока реплики транзакцию подхватят. API Tarantool такое делать позволяет после определённых приседаний. Но подходит такое решение не всегда. Дело в том, что даже если запрос-автор транзакции будет ждать её репликации, остальные запросы к БД уже будут видеть изменения этой транзакции, и исходная проблема может повториться. Это называется грязные чтения (dirty reads).

            Client 1           |           Client 2-------------------------------+--------------------------------box.space.money:update(        v    {uid}, {{'+', 'sum', 50}}  |)                              v-------------------------------+--------------------------------                               v   -- Видит незакоммиченные                               |   -- данные!!!                               v   box.space.money:get({uid})-------------------------------+--------------------------------wait_replication(timeout)      |                               v

В примере два клиента работают с базой. Один клиент добавляет себе 50 денег и начинает ждать репликации. Второй клиент уже видит данные транзакции до её репликации и логического коммита. Этим вторым клиентом может быть сотрудник банка или автоматика, делающая зачисление на счёт. Теперь если транзакция первого клиента не реплицируется в течение таймаута и будет откачена, то второй клиент видел несуществующие данные и мог принять на их основании неверные решения.

Это означает, что ручное ожидание репликации довольно специфичный хак, который использовать трудно и не всегда возможно.

Синхронная репликация

Самое правильное при таких требованиях использовать синхронную репликацию. Тогда транзакция не завершится успехом, пока не будет реплицирована на некоторое количество реплик.


Стоит обратить внимание, что шаг коммит и ответ выполняется в конце, уже после репликации.

Количество реплик, нужное для коммита транзакции, называется кворум. Обычно это 50 % размера репликасета + 1. То есть в случае двух узлов синхронная транзакция должна попасть на два узла, в случае трёх тоже на два, в случае четырёх на 3 узла, 5 на 3, и так далее.

50 % + 1 берётся для того, чтобы кластер мог пережить потерю половины узлов и всё равно не потерять данные. Это просто хороший уровень надёжности. Ещё одна причина: обычно в алгоритмах синхронной репликации предусмотрены выборы лидера, в которых для успешных выборов за нового лидера должно проголосовать более половины узлов. Любой кворум из половины или меньше узлов мог бы привести к выборам более чем одного лидера. Отсюда и выходит 50 % + 1 как минимум. Один кворум на любые решения коммиты транзакций и выборы.

Почему просто не использовать синхронную репликацию всегда, раз она лучше асинхронной? Потому что за синхронность нужно платить.

1. Расплата будет в скорости. Синхронная репликация медленнее, так как существенно возрастает задержка от начала коммита до его конца. Это происходит из-за участия сети и журналов других узлов: транзакцию надо на них послать, там записать и ответ получить. Сам факт присутствия сети увеличивает задержку потенциально до порядка миллисекунд.
2. В синхронной репликации сложнее поддерживать доступность репликасета на запись. Ведь при асинхронной репликации правило простое: если мастер есть, то данные можно менять. Неважно, есть ли живые реплики и сколько их. При синхронной, даже если мастер доступен, он может быть не способен применять новые транзакции, если подключенных реплик слишком мало какие-то могли отказать. Тогда он не может собирать кворум на новые транзакции.
3. Синхронную репликацию сложнее конфигурировать и программировать. Нужно аккуратно подбирать значение кворума (если каноническое 50 % + 1 недостаточно), таймаут на коммит транзакции, готовить мониторинг. В коде приложения придётся быть готовым к различным ошибкам, связанным с сетью.
4. Синхронная репликация не предусматривает мастер-мастер репликацию. Это ограничение алгоритма, который используется в Tarantool в данный момент.

Но в обмен на эти сложности можно получить гораздо более высокие гарантии сохранности данных.

К счастью, придумывать алгоритм синхронной репликации с нуля не нужно. Есть уже созданные алгоритмы, принятые практически как стандарт. Сегодня самым популярным является Raft. Он обладает рядом особенностей, которые его популярность оправдывают:

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

Raft был реализован в Tarantool в двух частях синхронная репликация и выборы лидера. Обе чуть изменены, чтобы адаптироваться к существующим системам Tarantool (формат журнала, архитектура в целом). Про Raft и реализацию его синхронной репликации пойдёт речь в данной статье далее. Выборы лидера тема отдельной статьи.

2. История разработки синхронной репликации в Tarantool

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

Задача разработки синхронной репликации существует в Tarantool с 2015 года, сколько я помню себя работающим здесь. Синхронная репликация изначально не рассматривалась как что-то срочно необходимое. Всегда находились более важные задачи, или просто не хватало ресурсов. Хотя неизбежность её реализации была ясна.

С развитием Tarantool становилось всё более очевидно, что без синхронной репликации некоторые области применения для этой СУБД закрыты. Например, определённые задачи в банках. Необходимость обходить отсутствие синхронной репликации в коде приложения существенно повышает порог входа, увеличивает вероятность ошибки и стоимость разработки.

Сначала на задачу был поставлен один человек, сделать её сразу и с наскоку. Но сложность оказалась слишком высока, а разработчик в итоге покинул команду. Было решено разбить синхронную репликацию на несколько задач поменьше, которые можно делать параллельно:

Реализация SWIM протокола построения кластера и обнаружения отказов. Дело в том, что в Raft выделяются два компонента, друг от друга почти не зависящие синхронная репликация при известном лидере и выборы нового лидера. Чтобы выбрать нового лидера, нужен способ обнаружить отказ старого. Это можно выделить в третью часть Raft, которую мог бы отлично решить протокол SWIM.

Также он мог бы быть использован как транспорт сообщений Raft, например, для голосования за нового лидера. Ещё SWIM мог бы быть использован для автоматической сборки кластера, чтобы узлы сами друг друга обнаруживали и подключались каждый к каждому, как того требует Raft.

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

Ручные выборы лидера box.ctl.promote(). Это должна была быть такая функция, которую можно вызвать на инстансе и сделать его лидером, а остальных репликами. Предполагалось, что в выборах лидера самое сложное начать их, и что начать можно с того, чтобы запускать выборы вручную.

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

Всё это должно было закончиться вводом автоматических выборов лидера, логически завершая Raft.

Список задач был сформирован в 2015, и с тех пор на несколько лет был отложен в долгий ящик. Команда сильно отвлеклась на более приоритетные задачи, такие как дисковый движок vinyl, SQL, шардинг.

Ручные выборы

В 2018 году появились ресурсы, и синхронная репликация снова стала актуальна. В первую очередь попытались реализовать box.ctl.promote().

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

Получались выборы практически как в Raft, но автоматически голосование никто не начинает, даже если текущий лидер недоступен. В результате стало очевидно, что смысла делать box.ctl.promote() в его изначальной задумке нет. Это получалась чуть-чуть урезанная версия целого Raft.

Прокси

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

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

Должен ли это быть отдельный модуль, или надо встроить его в существующие интерфейсы? Должен ли он поставляться из коробки или скачиваться отдельно? Как должна или не должна работать авторизация? Должна ли она быть прозрачной, или у прокси-сервера должна быть своя авторизация, со своими пользователями, паролями?

Задача была отложена на неопределённое время, потому что таких вопросов было слишком много. Тем более, в том же году появился модуль vshard, который задачу проксирования успешно решал.

SWIM

Следующая попытка продолжить синхронную репликацию произошла в конце 2018 начале 2019. Тогда за год был реализован протокол SWIM. Реализация была выполнена в виде встроенного модуля, доступного для использования даже без репликации, для чего угодно, прямо из Lua. На одном инстансе можно было создавать много SWIM-узлов. Планировалось, что у Tarantool будет свой внутренний SWIM-узел специально для Raft-сообщений, обнаружений отказов и автопостроения кластера.

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

Оптимизации репликации

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

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

Человек, занимавшийся реализацией, покинул команду. Незадолго до него ушёл автор изначального разбиения задач и по совместительству CTO Tarantool. Почти одновременно с этим команду покинул ещё один сильный разработчик, соблазнившись оффером из Google. В итоге команда была обескровлена, а прогресс по синхронной репликации был отброшен практически к нулю.

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

Прогресс пошёл значительно быстрее. В 2020-м, менее чем за год была реализована синхронная репликация. За основу снова взяли протокол Raft. В качестве минимальной рабочей версии оказалось нужно сделать всего две вещи: синхронный журнал и выборы лидера. Вот так сразу, без годов подготовки, без бесчисленных подзадач и переработок существующих систем Tarantool. По крайней мере, для первой версии.

3. Raft: репликация и выборы лидера

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

Оригинальная статья с полным описанием Raft называется In Search of an Understandable Consensus Algorithm. Алгоритм делится на две независимые части: репликация и выборы лидера.

Под лидером подразумевается единственный узел, принимающий запросы. Можно сказать, что лидер в терминологии Raft это почти то же самое, что мастер в Tarantool.

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

Вторая часть Raft занимается обнаружением отказа лидера и выборами нового.

В классическом Raft все узлы репликасета имеют роль: лидер (leader), реплика (follower) или кандидат (candidate):

• Лидер это узел, который принимает все запросы на чтение и запись.
• Реплики получают транзакции от лидера и подтверждают их. Все запросы от клиентов реплики перенаправляют на лидера (даже чтения).
• Кандидатом становится реплика, когда видит, что мастер пропал и надо начать новые выборы.

При нормальной работе кластера (то есть почти всегда) в репликасете ровно один лидер, а все остальные реплики.

Выборы лидера

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

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


Другие узлы, получив запрос на голос, действуют исходя из своего состояния. Если их терм меньше или такой же, но в этом терме ещё не голосовали, то узел голосует за кандидата.

Кандидат собирает ответы на запрос голоса, и если собирает большинство, то становится лидером, о чём сразу рассылает уведомление. Если же никто большинство не собрал, то спустя случайное время узлы начнут перевыборы. Время рандомизируется на каждом участнике кластера по-своему. За счёт этого минимизируется вероятность того, что все начнут одновременно, проголосуют за себя и никто не выиграет. Если же лидер был успешно выбран, то он способен применять новые транзакции.

Синхронная репликация

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

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


На реплики, не попавшие в кворум сразу, транзакция и факт её коммита доставляются асинхронно.

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


Журнал в Raft устроен как последовательность записей вида key = value. Каждая запись содержит саму модификацию данных и метаданные индекс в журнале и терм, когда запись была создана на лидере.

В журнале лидера поддерживается два курсора: конец журнала и последняя закоммиченная транзакция. Журналы реплик же являются префиксами журнала лидера. Лидер по мере сборки подтверждений от реплик пишет коммиты в журнал и продвигает индекс последней завершённой транзакции.

В процессе работы Raft поддерживает два свойства:

• Если две записи в журналах двух узлов имеют одинаковые индекс и терм, то и команда в них одна и та же. Та, которая key = value.
• Если две записи в журналах двух узлов имеют одинаковые индекс и терм, то их журналы полностью идентичны во всём, вплоть до этой записи.

Первое следует из того, что в каждом терме новые изменения генерируются на единственном лидере. Они содержат одинаковые команды и термы, распространяемые на все реплики. Ещё индекс всегда возрастает, и записи в журнале никогда не переупорядочиваются.

Второе следует из проверки, встроенной в AppendEntries. Когда лидер этот запрос рассылает, он включает туда не только новые изменения, но и терм + индекс последней записи журнала лидера. Реплика, получив AppendEntries, проверяет, что если терм и индекс последней записи лидера такие же, как в её локальном журнале, то можно применять новые изменения. Они точно следуют друг за другом. Иначе реплика не синхронизирована не хватает куска журнала с лидера, и даже могут быть транзакции не с лидера! Не синхронизированные реплики, согласно Raft, должны отрезать у себя голову журнала такой длины, чтоб остаток журнала стал префиксом журнала лидера, и скачать с лидера правильную голову журнала.

Здесь стоит сделать лирическое отступление и отметить, что на практике отрезание головы журнала не всегда возможно. Ведь данные хранятся не только в журнале! Например, это может быть B-дерево в SQLite в отдельном файле, или LSM-дерево, как в Tarantool в движке vinyl. То есть только отрезание головы журнала не удалит данные, ждущие коммита от лидера, если они попадают в хранилище сразу. Для такого журнал, как минимум, должен быть undo. То есть из каждой записи журнала можно вычислить, как сделать обратную запись, откатив изменения. Undo-журнал может занимать много места. В Tarantool же используется redo-журнал, то есть можно его проигрывать с начала, но откатывать с конца нельзя.

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


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


На реплике журнал может быть длиннее и даже иметь термы новее, чем в журнале лидера. Хотя текущий терм лидера всё равно будет больше, даже если он ещё ничего не записал (иначе бы он не избрался). Такое может произойти, если реплика была лидером в терме 3 и успела записать две записи, но кворум на них не собрала. Потом был выбран новый лидер в терме 4, и он успел записать две другие записи. Но на них тоже кворум не собрал, а только реплицировал на лидера терма 3. А потом выбрался текущий лидер в терме 5.

В Raft истина всегда за лидером, а потому реплики с плохим журналом должны отрезать от него часть, чтобы стал префиксом лидера. Это полностью валидно и не ведёт к потере данных, так как такое может происходить только с изменениями, не собравшими кворум, а значит не закоммиченными и не отданными пользователю как успешные. Если изменение собрало кворум, то при выборах нового лидера будет выбран один из узлов этого кворума. Если более половины кластера живо. Но это уже отдельная задача для модуля выборов лидера.

Это краткое изложение сути Raft с упором на синхронную репликацию. Алгоритм достаточно несложный по сравнению с аналогами вроде Paxos. Для понимания данной статьи изложения выше хватит.

4. Асинхронная репликация

В Tarantool до недавнего времени была реализована только асинхронная репликация. Синхронная основана на ней, так что для полного понимания надо сначала разобраться с асинхронной.

В Tarantool есть три основных потока выполнения и по одному потоку на каждую подключенную реплику:

• транзакционный поток (TX);
• сетевой поток (IProto);
• журнальный поток (WAL);
• репликационный поток (Relay).

Транзакционный поток TX

Это главный поток Tarantool. TX transaction. В нём выполняются все пользовательские запросы. Поэтому Tarantool часто называют однопоточным.

Поток работает в режиме кооперативной многозадачности при помощи легковесных потоков корутин (coroutine), написанных на С и ассемблере. В Tarantool они называются файберами (fiber).

Файберов могут быть тысячи, а настоящий поток с точки зрения операционной системы один. Поэтому при наличии, в некотором смысле, параллельности здесь полностью отсутствуют мьютексы, условные переменные, спинлоки и все прочие примитивы синхронизации потоков. Остается больше времени на выполнение реальной работы с данными вместо скачек с блокировками. Ещё это очень сильно упрощает разработку. Как команде Tarantool, так и пользователям.

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

Сетевой поток IProto

Это поток, задачи которого чтение и запись данных в сеть и из сети, декодирование сообщений по протоколу Tarantool под названием IProto. Это значительно разгружает TX-поток от довольно тяжелой задачи ввода-вывода сети. Пользователю этот поток недоступен никак, но и делать ему в нём всё равно нечего.

Однако существует запрос от сообщества на возможность создавать свои потоки и запускать в них собственные серверы, например, по протоколу HTTPS. Забегая вперёд, скажу, что в эту сторону начались работы.

Журнальный поток WAL

Поток, задача которого запись транзакций в журнал WAL (Write Ahead Log). В такой журнал транзакции записываются до того, как они применяются к структурам базы данных и становятся видимыми всем пользователям. Поэтому Write Ahead пиши наперёд.

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

Журнал в Tarantool redo. Его можно проигрывать с начала и заново применять транзакции. Это и происходит при перезапуске узла. При этом проигрывание возможно только с начала до конца. Нельзя откатывать транзакции, проходя в обратную сторону. Для компактности транзакции в redo-журнале не содержат информации, необходимой для их отката.

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

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

Репликационный поток Relay

Помимо трёх главных потоков Tarantool создает потоки репликации. Они есть только при наличии репликации и называются relay-потоками.

По одному relay-потоку создаётся на каждую подключённую реплику. Relay-поток получает от реплики запрос на получение всех транзакций, начиная с определённого момента. Он исполняет этот запрос в течение жизни репликации, постоянно отслеживая новые транзакции, попавшие в журнал, и посылая их на реплику. Это репликация на другой узел.

Для репликации с другого узла, а не на другой узел, Tarantool создаёт в TX-потоке файбер под названием applier применяющий файбер. К этому файберу подключается relay на исходном инстансе. То есть relay и applier это два конца одного соединения, в котором данные плывут в одном направлении: от relay к applier. Метаданные (например, подтверждения получения) посылаются в обе стороны.

Например, есть узел 1 с конфигурацией box.cfg{listen = 3313, replication = {localhost:3314}}, и узел 2 с конфигурацией box.cfg{listen = 3314}. Тогда на обоих узлах будут TX-, WAL-, IProto-потоки. На узле 1 в TX-потоке будет жить applier-файбер, который скачивает транзакции с узла 2. На узле 2 будет relay-поток, который отправляет транзакции в applier узла 1.


Relay сделаны отдельными потоками, так как занимаются тяжёлой задачей: чтением диска и отправкой записей журнала в сеть. Чтение диска здесь самая долгая операция.

Идентификация транзакций

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

Идентификация записей в журнале происходит по двум числам: replica ID и LSN. Первое это уникальный ID узла, который создал транзакцию. Второе число LSN, Log Sequence Number, идентификатор записи. Это число постоянно возрастает внутри одного replica ID, и не имеет смысла при сравнении с LSN под другими replica ID.

Такая парная идентификация служит для поддержки мастер-мастер репликации, когда много инстансов могут генерировать транзакции. Для их различия они идентифицируются по ID узла-автора, а для упорядочивания по LSN. Разделение по replica ID позволяет не заботиться о генерировании уникальных и упорядоченных LSN на весь репликасет.

Всего реплик может быть 31, и ID нумеруются от 1 до 31. То есть журнал в Tarantool в общем случае это сериализованная версия 31-го журнала. Если собрать все транзакции со всеми replica ID на узле, то получается массив из максимум 31-го числа, где индекс это ID узла, а значение последний примененный LSN от этого узла. Такой массив называется vclock vector clock, векторные часы. Vclock это точный снимок состояния всего кластера. Обмениваясь vclock, инстансы сообщают друг другу, кто на сколько отстаёт, кому какие изменения надо дослать, и фильтруют дубликаты.

Есть ещё 32-я часть vclock под номером 0, которая отвечает за локальные транзакции и не связана с репликацией.

Реплицированные транзакции на репликах применяются ровно так же, как и на узле-авторе. С тем же replica ID и LSN. А потому продвигают ту же часть vclock реплики, что и на узле-авторе. Так автор транзакций может понять, надо ли посылать их ещё раз, если реплика переподключается, и сообщает свой полный vclock.

Далее следует пример обновления и обмена vclock на трёх узлах. Допустим, узлы имеют replica ID 1, 2 и 3 соответственно. Их LSN изначально равны 0.

Узел 1: [0, 0, 0]Узел 2: [0, 0, 0]Узел 3: [0, 0, 0]

Пусть узел 1 выполнил 5 транзакций и продвинул свой LSN на 5.

Узел 1: [5, 0, 0]Узел 2: [0, 0, 0]Узел 3: [0, 0, 0]

Теперь происходит репликация этих транзакций на узлы 2 и 3. Узел 1 будет посылать их через два relay-потока. Транзакции содержат в себе {replica ID = 1}, и потому будут применены к первой части vclock на других узлах.

Узел 1: [5, 0, 0]Узел 2: [5, 0, 0]Узел 3: [5, 0, 0]

Пусть теперь узел 2 сделал 6 транзакций, а узел 3 сделал 9 транзакций. Тогда до репликации vclock будут выглядеть так:

Узел 1: [5, 0, 0]Узел 2: [5, 6, 0]Узел 3: [5, 0, 9]

А после так:

Узел 1: [5, 6, 9]Узел 2: [5, 6, 9]Узел 3: [5, 6, 9]

Общая схема

Схема асинхронной репликации в такой архитектуре:

1. Транзакция создаётся в TX-потоке, пользователь начинает её коммит и его файбер засыпает.
2. Транзакция отправляется в WAL-поток для записи в журнал, записывается, в TX-поток уходит положительный ответ.
3. TX-поток будит файбер пользователя, пользователь видит успешный коммит.
4. Просыпается relay-поток, читает эту транзакцию из журнала и посылает её в сеть на реплику.
5. На реплике её принимает applier-файбер, коммитит её.
6. Транзакция отправляется в WAL-поток реплики, записывается в её журнал, в TX-поток уходит положительный ответ.
7. Applier-файбер посылает ответ со своим новым vclock, что всё нормально применилось.

Пользователь к последнему шагу уже давно ушёл. Если выключить Tarantool из розетки до того, как транзакция будет выслана на реплики (после конца шага 3, до конца шага 4) и больше не включать, то эта транзакция уже никуда не доедет и будет потеряна. Конечно, если узел включится снова, то он будет продолжать пытаться отправить транзакцию на реплики, но на сервере мог сгореть диск, и тогда уже ничего не поделать.

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

5. Синхронная репликация

Прежде чем приступать к реализации Raft, было решено зафиксировать несколько правил, которых было обязательно придерживаться в процессе разработки:

• Если синхронная репликация не используется, то протокол репликации и формат журнала не должны быть изменены никак, полная обратная совместимость. Это позволит обновить существующие кластеры на новый Tarantool и уже потом включить синхронность, по необходимости.
• Если синхронность используется, нельзя менять формат существующих записей журнала, снова из целей обратной совместимости. Можно только добавлять новые типы записей. Или добавлять новые опциональные поля в существующие типы записей. То же самое про сообщения в репликационных каналах.
• Нельзя существенно изменить архитектуру Tarantool. Иначе это приведет к изначальной проблеме, когда задача был раздута и растянута на годы. То есть надо оставить основные потоки Tarantool делать то, что они делали, и сохранить их связность в текущем виде. TX-поток должен управлять транзакциями, WAL должен остаться тривиальной системой записи на диск, IProto остается простейшим интерфейсом к клиентам из сети, и relay-потоки должны только читать журнал и посылать транзакции на реплики. Любые последующие оптимизации и перераспределения обязанностей систем должны быть выполнены отдельно, не являться блокировщиками.

Правила достаточно просты, но их явная формулировка была полезна. Это позволило отметать некоторые нереалистичные идеи.

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

• создание;
• начало коммита;
• ожидание подтверждений;
• сборка кворума;
• коммит или отмена транзакции.

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

Создание транзакции

Синхронность в Tarantool это свойство не всей БД. Это свойство каждой транзакции по отдельности. Это значит, что пользователи сами выбирают, для каких данных им синхронность нужна, а для каких не особо.

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

Синхронными являются те транзакции, которые затрагивают хотя бы один синхронный спейс. Спейс это аналог SQL-таблицы в Tarantool. При создании можно указать опцию is_sync, и все транзакции над этим спейсом будут синхронными. Даже если транзакция меняет обычные спейсы, но меняет ещё и хотя бы один синхронный спейс, она вся станет синхронной.

Как это выглядит в коде:

Включить синхронность на существующем спейсе:

box.space[name]:alter({is_sync = true})

Включить синхронность на новом спейсе:

box.schema.create_space(name, {is_sync = true})

Синхронная транзакция на одном спейсе:

sync = box.schema.create_space(   stest, {is_sync = true}):create_index(pk)-- Транзакция из одного выражения,-- синхронная.sync:replace{1}-- Транзакция из двух выражений, тоже-- синхронная.box.begin()sync:replace{2}sync:replace{3}box.commit()

Синхронная транзакция на двух спейсах, один из которых не синхронный:

async = box.schema.create_space(    atest, {is_sync = false}):create_index(pk)-- Транзакция над двумя спейсами, один-- из них  синхронный, а значит вся-- транзакция  синхронная.box.begin()sync:replace{5}async:replace{6}box.commit()

С момента создания и до начала коммита транзакция ведёт себя неотличимо от асинхронной.

Начало коммита транзакции

Транзакция, независимо от того, синхронная она или нет, в первую очередь должна попасть в журнал. В случае асинхронных успешная запись в журнал = коммит. Зачем делать это для синхронных, если ещё не собраны подтверждения от реплик?

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

Чтобы транзакция не была потеряна при перезапуске инстанса, но и не была завершена до отправки на нужное число реплик, коммит нужно делить на две части. Это запись в журнал самой транзакции с её данными, и отдельно запись в журнал специального маркера COMMIT после того, как кворум собран. Это очень напоминает алгоритм двухфазного коммита. Если репликация не сработала за разумное время, то по таймауту надо писать маркер ROLLBACK.

На самом деле Raft это и подразумевает. Просто он не декларирует, как именно это сохранять в журнал, в каком формате. Столкновение с этими деталями происходит уже в процессе проектирования применительно к конкретной БД.

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

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

Ожидание подтверждений от реплик

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

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

Лимб находится в TX-потоке, куда также стягиваются все подтверждения от реплик из relay-потоков. Такая организация позволяет практически никак не менять существующие подсистемы Tarantool. Всё ядро синхронной репликации, все её действия происходят в новой подсистеме лимб, который взаимодействует с другими подсистемами через их интерфейсы.


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

Сбор кворума

Пока транзакция находится в лимбе, relay-потоки читают её из журнала и высылают на реплики. Реплика получает транзакцию и делает всё тоже самое: пишет её в свой журнал и кладет в свой собственный лимб. Синхронная транзакция или нет, реплика понимает так же, как лидер смотря на синхронность измененных спейсов.

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

После записи в журнал реплика посылает лидеру подтверждение о записи. Подтверждения в Tarantool посылались всегда, для разных подсистем, для мониторинга. И их формат не изменен нисколько.

Подтверждение суть vclock реплики. Он меняется при каждой записи в журнал. Получив это сообщение с vclock реплики, лидер может посмотреть, какой его LSN реплика уже записала в журнал. Например, лидер посылает 3 транзакции на реплику, одной пачкой, {LSN = 1}, {LSN = 2}, {LSN = 3}. Реплика отвечает {LSN = 3} это значит, что все транзакции с LSN <= 3 попали в её журнал. То есть они подтверждены.

На лидере подтверждения от реплик читаются в relay-потоке, оттуда попадают в TX-поток и становятся видны в box.info.replication. Лимб эти уведомления отлавливает и следит, не собрался ли кворум для старейшей ждущей транзакции.

Для отслеживания кворума по мере прогрессирования репликации лимб на лидере строит картину того, какая реплика как далеко зашла. Он поддерживает у себя векторные часы, в которых записаны пары {replica ID, LSN}. Только это не совсем обычный vclock. Первое число идентификатор реплики, а второе последний LSN от лидера, применённый на этой реплике.

Получается, что лимб хранит множество версий LSN лидера, как он хранится на репликах. Обычный vclock хранит LSN разных инстансов, а тут разные LSN одного инстанса лидера.

Для любой синхронной транзакции по её LSN лимб может точно сказать, сколько реплик её применило, просто посчитав, сколько частей этих специальных векторных часов >= этого LSN. Это немного отличается от того, какой vclock пользователи могут видеть в box.info. Но суть очень похожа. В итоге, каждое подтверждение от реплики немного продвигает одну часть этих часов.

Далее следует пример, как обновляется vclock лимба на лидере в кластере из трех узлов. Узел 1 лидер.

Узел 1: [0, 0, 0], лимб: [0, 0, 0]Узел 2: [0, 0, 0]Узел 3: [0, 0, 0]

Пусть лидер начал коммитить 5 синхронных транзакций. Они попали в его журнал, но ещё не были отправлены на реплики. Тогда vclock будут выглядеть так:

Узел 1: [5, 0, 0], лимб: [5, 0, 0]Узел 2: [0, 0, 0]Узел 3: [0, 0, 0]

В vclock лимба продвинулась первая компонента, так как эти 5 транзакций были применены на узле с replica ID = 1, и совершенно не важно, лидер это или нет. Лидер тоже участник кворума.

Теперь предположим, что первые 3 транзакции были реплицированы на узел 2, а первые 4 на узел 3. То есть репликация ещё не завершена. Тогда vclock будут выглядеть следующим образом:

Узел 1: [5, 0, 0], лимб: [5, 3, 4]Узел 2: [3, 0, 0]Узел 3: [4, 0, 0]

Стоит обратить внимание, как обновился vclock лимба. Он фактически является столбиком в матрице vclock-ов. Так как узел 2 подтвердил LSN 3, в лимбе это отражено как LSN 3 во второй компоненте. Так как узел 3 подтвердил LSN 4, в лимбе это LSN 4 в третьей компоненте. Так, глядя на этот vclock, можно сказать, на какой LSN есть кворум.

Например, здесь на LSN 4 есть кворум два узла: 1 и 3, так как они этот LSN подтвердили. А на LSN 5 кворума ещё нет этот LSN есть только на узле 1. Под кворумом подразумевается 50 % + 1, то есть два узла.

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

Коммит транзакции

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

Транзакции упорядочены по LSN, поэтому в какой-то момент встретится транзакция, у которой кворума ещё нет, и 100 % у следующих транзакций его тоже нет. Либо лимб окажется пуст. Для последней собранной транзакции с максимальным LSN лимб пишет в журнал запись COMMIT. Это также автоматически подтвердит все предыдущие транзакции, поскольку репликация строго последовательна. То есть если транзакция с LSN L собрала кворум, то все транзакции с LSN < L тоже его собрали. Это экономит количество операций записи в журнал и место в нём.

После записи COMMIT все завершённые транзакции отвечаются пользователям как успешные и удаляются из памяти.

Рассмотрим пример, как лимб сворачивается. Пусть в кластере 5 узлов. Лидер третий. В лимбе накопились транзакции в ожидании кворума.


Коммитить пока ничего нельзя: самая старая транзакция имеет LSN 1, который подтверждён только лидером. Пусть часть реплик подтвердила несколько LSN-ов.


Теперь LSN 1 подтвержден узлами 1, 3, 4, 5 то есть это больше половины и кворум собран, можно коммитить. Следующий LSN 2, на него только два подтверждения, от узлов 3 и 4. Его коммитить пока нельзя, как и все последующие. Значит в журнал надо записать COMMIT LSN 1.


Спустя ещё время получены новые подтверждения от реплик.


Теперь кворум есть на LSN 5 его подтвердили все. Так как везде LSN >= 5. На LSN 6 кворума нет, он есть только на двух узлах (3-й и 5-й), а это меньше половины. Значит коммитить можно все LSN <= 5.


Стоит обратить внимание, как одна запись COMMIT завершает сразу 4 транзакции.

Так как COMMIT попадает в журнал, а журнал реплицируется, то эта запись автоматически уедет на реплики и отпустит завершённые транзакции в их лимбах. Ровно таким же образом, но только реплики не будут писать ещё один COMMIT. Они только запишут тот, что пришёл от лидера.

Отмена транзакции

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

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

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

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

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

Если будет потеряно большинство реплик (больше, чем кворум), то даже коммит транзакции не даёт гарантий.

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

К сожалению, в распределённых системах нет никаких 100 % гарантий ни на что. Можно лишь увеличивать шансы на успех, наращивать надёжность, но идеального решения физически невозможно создать.

Смена лидера

Бывает, что лидер становится недоступен по какой-либо причине. Тогда надо выбрать нового лидера. Делать это можно разными способами, включая вторую часть Raft, которая тоже реализована в Tarantool и делает смену автоматически. Можно каким-то другим способом.

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

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

Если выбрать лидером не тот узел, то можно потерять данные. Так как узел после становления лидером будет единственным источником правды. Если на нём есть не все закоммиченные данные, то они будут считаться несуществующими, и это состояние будет форсировано на весь кластер.

Рассмотрим пример. Есть 5 узлов. Один из них лидер, и он выполнил транзакцию по обновлению ключа A в значение 20 вместо старого 10. На эту транзакцию он собрал кворум из трёх узлов, закоммитил её, ответил клиенту.


Теперь лидер был уничтожен до того, как успел послать эту транзакцию на другие два узла.


Новым лидером может стать только один из узлов под синим контуром. Если лидером сделать один из узлов под красным контуром, то он форсирует на остальных состояние {a = 10}, что приведёт к потере транзакции. Несмотря на то, что на неё был собран кворум, произошел коммит и более половины кластера всё ещё цело.

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

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

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

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

Интерфейс

Функции для работы с синхронной репликацией в Tarantool делятся на две группы: для управления синхронностью и для выборов лидера. Для включения синхронности на спейсе нужно указать опцию is_sync со значением true при его создании или изменении.

Создание:

box.schema.create_space('test', {is_sync = true})

Изменение:

box.space[test]:alter({is_sync = true})

Теперь любая транзакция, меняющая синхронный спейс, становится синхронной. Для настройки параметров синхрона есть глобальные опции:

box.cfg{    replication_synchro_quorum = <count or expression>,    replication_synchro_timeout = <seconds>,    memtx_use_mvcc_engine = <boolean>}

Replication_synchro_quorum это количество узлов, которые должны подтвердить транзакцию для её коммита на лидере. Можно задать его как число, а можно как выражение над размером кластера. К примеру, каноническая форма box.cfg{replication_synchro_quorum = N/2 + 1}, которая означает кворум 50 % + 1. Tarantool вместо N подставляет количество узлов, известных лидеру. Кворум можно выбрать и больше канонического, если нужны более сильные гарантии. Но выбирать половину или меньше уже небезопасно.

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

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

Для выборов лидера можно пользоваться автоматикой, освещённой в отдельной статье. А можно выбирать вручную или своей собственной автоматикой через API Tarantool.

Для поиска нового лидера надо знать, у кого самый большой LSN от старого лидера. Чтобы его найти, следует воспользоваться box.info.vclock, где указан весь vclock узла, и в нём надо найти компоненту старого лидера. Ещё можно попытаться искать узел, где все части vclock больше или равны всех частей vclock на других узлах, но можно наткнуться на несравнимые vclock.

После нахождения кандидата следует позвать на нем box.ctl.clear_synchro_queue(). Пока эта функция не вернёт успех, лидер не может начать делать новые транзакции.

Отличия от Raft

Идентификация транзакций

Главное отличие от Raft идентификация транзакций. Происходит отличие из формата журнала. Дело в том, что в Raft журнал един. В нём нет векторности. Записи журнала Raft имеют формат вида {{key = value}, log_index, term}. В терминологии Tarantool это изменения транзакции и её LSN. Tarantool не хранит термы в каждой записи, и в нём нет единой последовательности log_index нужно хранить replica ID. В Tarantool расчёт LSN идёт индивидуально на каждом узле для транзакций его авторства.

Блокирующими проблемами это, на самом деле, не является. Потому как, во-первых, транзакции генерирует только один узел, а значит из всех компонент vclock меняется только один с ID = replica ID лидера. То есть журнал на самом деле линеен, пока лидер известен и работает. Во-вторых, хранить терм в каждой записи не нужно, и вообще может быть дорого. Достаточно фиксировать в журнале, когда терм был изменён, и в памяти держать текущее значение терма. Это делается модулем выборов лидера отдельно от синхронной репликации.

Сложность возникает, когда лидер меняется. Тогда нужно во всём кластере перевести отсчёт LSN на другую часть vclock, с отличным replica ID. Для этого новый лидер завершает все транзакции старого лидера, захватывает лимб транзакций и начинает генерировать свои собственные транзакции. На репликах произойдёт то же самое: они получат от нового лидера COMMIT и ROLLBACK на транзакции старого лидера, и потом новые транзакции с другим replica ID. Лимбы всего кластера переключаются автоматически, когда их опустошили, и начали давать новые транзакции с другим replica ID.

Это выглядит почти как если бы в кластере был 31 протокол Raft, работающий поочередно.

Нет отката журнала

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

В Tarantool отката журнала нет, так как он redo, а не undo. Кроме того, архитектурой не предусмотрен откат LSN. Если в кластере появляются такие реплики, то нет выбора кроме как их удалить и подключать как новые, скачать все данные с лидера заново. Это называется rejoin.

Однако в этом направлении ведутся работы, в результате которых откат будет работать без пересоздания реплики.

Заключение

Синхронная репликация в Tarantool доступна с версии 2.5, а автоматические выборы с версии 2.6. На данный момент эта функциональность находится в бета-версии, то есть ещё не обкатана в реальных системах, а интерфейсы и их поведение ещё могут измениться. И пока существующая реализация полируется, есть планы по её оптимизации и расширению. Оптимизации главным образом технические.

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

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

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

Транзакции в бинарном протоколе
С момента создания Tarantool в нём не было возможно делать долгие транзакции из более чем одного выражения прямо по сети, используя только удалённый коннектор к Tarantool. Для любой операции сложнее, чем один replace/delete/insert/update, требовалось написать код на Lua, который бы делал нужные операции в одной транзакции, и вызывать этот код как функцию.

В данный момент запланирована реализация транзакций прямо в протоколе. Со стороны клиента на Lua это будет выглядеть, например, так:

c = netbox.connect(host)c:begin()c.space.test1:replace{100}c.space.test2:delete({5})c:commit()

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

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

Запланировано расширение интерфейса коммита, чтобы файбер не блокировался. Выглядеть будет, например, вот так:

box.begin()box.space.test1:replace{100}box.commit({is_lazy = true})box.begin()box.space.test2:replace{200}box.space.test3:replace{300}box.commit({is_lazy = true})

Оба box.commit() вернут управление сразу, а транзакция попадёт в журнал и будет закоммичена в конце итерации цикла событий Tarantool (event loop). Такой подход не только может уменьшить задержку на ответ клиенту, но и лучше использовать ресурсы WAL-потока, так как больше транзакций сможет попасть в одну пачку записи на диск к концу итерации цикла событий.

Кроме того, касательно синхронных транзакций иногда может быть удобно сделать синхронным не целый спейс, а только определённые транзакции, даже над обычными спейсами. Для такого запланировано добавлении ещё одной опции в box.commit() is_sync. Выглядеть будет так: box.commit({is_sync = true}).

Мониторинг
В данный момент нет способа узнать, сколько синхронных транзакций ожидают коммита (находятся в лимбе). Ещё нет способа узнать, каково значение кворума, если пользователь использовал выражение в replication_synchro_quorum. Например, если было задано N/2 + 1, то в коде узнать фактическое значение кворума нельзя никаким вменяемым способом (но способ есть).

Для устранения этих неизвестностей будет выведена отдельная функция мониторинга box.info.synchro.