-
Yaroslav Dynnikov authoredfeat: raft peer discovery PoC chore: prevent C functions from being optimized out feat: improve peer discovery fix: fix tests after making instance_id arg mandatory Smart supevision with fork Make it work Under development IPC messages to supervisor One more little step: entrypoint enum Arrange IPC from child to supervisor Remove tarantool_main macro Persist snapshot Fix some fresh bugs Implement postjoin Discovery under refactoring Enhance discovery Working on discovery Fix all discovery bugs known so far Draft join algorithm Fail applying snapshot Joining a learner works Cleanup snapshot generation Reorganize traft code and call join automatically Change peer.commit_index type from option to u64 Implement autopromotion to voter Implement read_index Take read_index before self-romotion Cleanup excess logs Cleanup logs and code Deep refactoring in progress Finish refactoring db schema Embed entries applying inside traft node Refactor raft node communication Replace fiber channel with a mailbox, which is a `Vec<_>` + fiber cond. It allows to batch raft commands in a more predictable way and makes the code less error-prone. Remove commented code Simplify raft nodes interaction over net_box Eliminate `traft::Message` struct because its internals aren't used. Instead, serialize `raft::Message` using protobuf. Batch ConnectionPool requests 1. Send messages in batches. 2. Allow changing connection uri. 3. Close unused connections after `inactivity_timeout`. Enhance the raft node 1. Collect results from raft node 2. Fix initial bootstrap which used to fail due to fiber race. 3. Wrap raft storage operations in a transaction. Bump tarantool module Add documentation draft Cleanup warnings Try fixing tests Fix test_storage_log Fix test_traft_pool Fix luatest single and couple Start fixing threesome test Implement concurrent join requests handling
Yaroslav Dynnikov authoredfeat: raft peer discovery PoC chore: prevent C functions from being optimized out feat: improve peer discovery fix: fix tests after making instance_id arg mandatory Smart supevision with fork Make it work Under development IPC messages to supervisor One more little step: entrypoint enum Arrange IPC from child to supervisor Remove tarantool_main macro Persist snapshot Fix some fresh bugs Implement postjoin Discovery under refactoring Enhance discovery Working on discovery Fix all discovery bugs known so far Draft join algorithm Fail applying snapshot Joining a learner works Cleanup snapshot generation Reorganize traft code and call join automatically Change peer.commit_index type from option to u64 Implement autopromotion to voter Implement read_index Take read_index before self-romotion Cleanup excess logs Cleanup logs and code Deep refactoring in progress Finish refactoring db schema Embed entries applying inside traft node Refactor raft node communication Replace fiber channel with a mailbox, which is a `Vec<_>` + fiber cond. It allows to batch raft commands in a more predictable way and makes the code less error-prone. Remove commented code Simplify raft nodes interaction over net_box Eliminate `traft::Message` struct because its internals aren't used. Instead, serialize `raft::Message` using protobuf. Batch ConnectionPool requests 1. Send messages in batches. 2. Allow changing connection uri. 3. Close unused connections after `inactivity_timeout`. Enhance the raft node 1. Collect results from raft node 2. Fix initial bootstrap which used to fail due to fiber race. 3. Wrap raft storage operations in a transaction. Bump tarantool module Add documentation draft Cleanup warnings Try fixing tests Fix test_storage_log Fix test_traft_pool Fix luatest single and couple Start fixing threesome test Implement concurrent join requests handling
Discovery algorithm
Входные данные:
-
Nузлов, пока не связанных друг с другом по сети. Связать их предстоит алгоритму. - Тем не менее, каждый узел обладает на старте информацией о некоторых его соседях - массиве
initial_peers, содержащем сетевые адреса узлов (не менее одного).
Алгоритм налагает некоторые ограничение на входные данные, в противном случае результат работы алгоритма может оказаться некорректным. Чтобы обеспечить выполнение результата, у любой пары узлов должен существовать как минимум один общий элемент initial_peers.
Здесь стоит сказать пару слов о том, как именно мы будем моделировать сеть. Алгоритм специально составлен таким образом, чтобы его легко было адаптировать под конкретный транспортный протокол, хоть TCP, хоть UDP.
Чтобы не прослыть инфантильными, мы также сразу допускаем, что связность сети может спонтанно нарушаться. Любое сообщение может:
- быть доставлено получателю спустя неопределённое время,
- возможно бесконечно малое,
- а возможно и бесконечно никогда.
Мы хотим, чтобы алгоритм был полезен на практике. И такое предположение, несомненно, благоприятно скажется на способностях алгоритма не разбиться о суровую реальность, где сервера иногда простужаются перегреваются и выгорают целыми датацентрами.
В тоже время алгоритм совершенно не подготовлен к решению задачи о византийских генералах. Акцент в первую очередь делается на отказоустойчивости к ошибкам пользователя, а не злонамеренности генералов. Это призвано упростить процесс инициализации рафт группы (который в худшем случае можно и перезапустить на этапе подготовки к эксплуатации, в отличие от генералов). Византийская отказоустойчивость, если это необходимо, должна обеспечиваться другим протоколом.
Результат:
Результатом работы этого распределенного алгоритма является единственное булево значение i_am_bootstrap_leader. Мы ожидаем (и заверяем вас), что, пока входные параметры не нарушают наложенных ограничений, не более одного узла будущего кластера присвоят себе эту медальку. Я бы хотел, чтобы "не меньше" тоже было равно одному, но, увы, в условиях полной сетевой изоляции ответ будет ноль, и никакой онлайн-вечеринки не состоится.
И опять, в угоду пользовательского опыта, алгоритм не пытается заполучить больше информации о будущем кластере. В противном случае это потребовало бы делать дополнительные предположения о сетевой связности, и это могло негативно сказаться на удобстве эксплуатации решения. Данный алгоритм надеется на лучшее (один бутстрап лидер), оставаясь готовым к худшему (ноль бутстрап лидеров).
Собственно сам алгоритм
Шаг 0.1
Как уже упоминалось раньше, каждый узел i инициализирует массив известных адресов known_peers[i] = initial_peers[i] (со значениями, предоставленными пользователем).
Шаг 0.2
Каждый узел i генерирует случайный идентификатор (guid[i]), вероятность коллизии которых мы предполагаем равной нулю. Это требование совсем не сложно выполнить на практике.
Шаг 1
Каждый узел i проводит раунд запросов номер r - отправляет по всем известным адресам known_peers[i][m] сообщение ("discovery_req", m, known_peers[i]). Параметр m представляет собой всего лишь индекс адресата в массиве known_peers[i]. Единственная его роль в алгоритме - быть возвращённым в ответе, чтобы можно было сопоставить ответ с конкретным адресом. Впрочем, его можно вообще опустить, если эту функциональность предоставляет используемый транспортный протокол.
Меж двух шагов
Получив сообщение ("discovery_req", m, known_peers[i]), узел (j) проверяет своё состояние.
Если на данный момент лидер уже выбран и известен, то отправляет в ответ сообщение ("discovery_finished").
В противном случае обновляет свой массив known_peers[j] = known_peers[i] \/ known_peers[j]. Ответ содержит ("discovery_resp", m, known_peers[j], guid[j]).
Здесь делается ещё одно допущение о том, что используемый транспортный протокол обладает функцией "отправки ответа". Оба TCP и UDP такой функциональностью обладают.
Шаг 2 (Возвращаясь к узлу i - отправителю запроса)
Yaroslav Dynnikov, [08/04/2022 22:18]
Получив ответ ("discovery_finished") алгоритм завершает свою работу - задача выполнена. i_am_bootstrap_leader[i] = false.
Получив ответ ("discovery_resp", m, known_peers[j], guid[j]), узел (i), как и в случае обработки discovery_req, обновляет свой массив known_peers[i] = known_peers[i] \/ known_peers[j]. Далее полученный ответ сопоставляется с адресатом known_peers[i][m]. Если в массиве known_peers[i] остались ещё не ответившие адресаты, алгоритм приостанавливается до получения следующего сообщения.
Если ответ содержит ошибку протокола транспортного уровня, запрос повторяется с некоторым интервалом до тех пор, пока не будет получен внятный ответ.
Если к концу этого шага были обнаружены новые адресаты, алгоритм начинает новый раунд запросов r+1 и возвращается к шагу 1.
Шаг 3
Если вдруг лидер до сих пор не известен, то к этому моменту каждому узлу i становится известна полная карта known_peers[i][m] -> guid[m].
Если вдруг guid[i] == min(guid), то узел понимает, что i_am_bootstrap_leader[i] = true, и с этих пор перестаёт изменять внутреннее состояние, и отвечает на все запросы ("discovery_finished").
Если же, напротив, guid[i] != min(guid), то i_am_bootstrap_leader[i] = false.
Доказательство
Корректность алгоритма проще всего доказать от противного. Предположим, что в какой-то момент узел i решил, что i_am_bootstrap_leader[i] == true, в то время как уже существовал i_am_bootstrap_leader[j] == true (и при этом i != j).
Так как на третьем шаге оба узла вычисляют min(guid) идентичным оразом, то отличаться должны были сами таблицы guid.
При этом массив known_peers[j] заведомо не содержал адрес i в момент принятия решения, но содержал свой адрес j, иначе бы не выполнилось условие guid[j] == min(guid). Аналогично, known_peers[i] точно содержал i.
В то же время known_peers[i] не мог содержать j, иначе i не смог бы получить от j ответ ("discovery_resp") и не “выдать” себя.
Таким образом i и j не должны были в момент принятия решения ничего знать друг о друге.
Но так как у i и j по условию должен быть как минимум один общий "сосед", назовём его z, он также должен был обоим i и j дать ответы ("discovery_resp"). Противоречие заключается в том, что z пришлось бы одному из двух узлов в ответе ("discovery_resp") сообщить о существовании второго, покуда обработка запросов выполняется атомарно.
Возможные оптимизации
Основная часть алгоритма изложена так, чтобы быть максимально простой. Тем не менее, это не исключает наличия нескольких полезных оптимизаций, которые нисколько не влияют на результат, хотя позволяют сделать пользовательский опыт приятнее.
Начинать новый раунд на втором шаге не возбраняется сразу после обнаружения нового адресата. Не обязательно для этого дожидаться всех ожидаемых ответов.
После завершения работы алгоритма, с сообщениями ("discovery_finished") можно рассылать информацию об адресе лидера, о known_peers, или любую другую необходимую, которую хотелось бы синхронизировать. Так как единственность лидера доказана, остальные узлы могут ему верить, если конечно никто больше не возьмётся её модифицировать, а мы договорились не рассматривать византийские сценарии.