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

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

Автор надеется помочь читателям глубже понять протокол Raft и применить его в инженерной практике, и в то же время интерпретировать ключевые моменты, которые нелегко понять или неправильно понять. Серия начинается сПринцип, исходный код, практикаТри части объясняют принципы и алгоритмы Raft:

Основная частьВ сочетании с документом Raft, чтобы объяснить принцип алгоритма Raft, следуйте модульной идее Raft, соответственно объясните выбор лидера, репликацию журнала, безопасность, изменение членства в кластере, уплотнение журнала и т. д.
исходный кодПроанализируйте hashicorp/raft, чтобы изучить промышленную реализацию Raft (hashicorp/raft — низкоуровневая зависимость от Consul).
Практическая частьРеализуйте простое распределенное хранилище kv на основе hashcorp/raft в качестве последнего штриха.

Ссылки на серию исторических статей:

Боевая серия протокола Raft (1) - основные понятия
Боевая серия протокола Raft (2) - основная подборка
Боевая серия протокола Raft (3) - репликация журнала
Протокол боевой серии Raft (4) - безопасность

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

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

В этой статье мы объясним эти два метода отдельно.

1. Смена члена кластера

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

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

1.1 Непосредственное переключение конфигурации члена кластера

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

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

Чтобы понять сделанные выше выводы, давайте рассмотрим реальный сценарий проблемы, который показан на рисунке 1.

*Рисунок 1

этап а.В кластере три узла S1 ~ S3.Конфигурацию участника обозначим как C-old, зеленый цвет указывает на то, что текущее представление (конфигурация участника) узла является C-old, а S3 на красной стороне является лидером.

этап б.В кластер добавляются два новых узла, S4 и S5. Изменение записывается с лидера. Обозначим пятиузловую конфигурацию нового члена S1 ~ S5 как C-new, а синий цвет означает, что текущий вид узла C-новый.

этап в.Предположим, что кратковременный сбой S3 инициирует тайм-аут S1 и S5 для выбора ведущего.

стадия д.S1 запрашивает голоса от S2 и S3, а S5 запрашивает голоса от всех остальных четырех узлов. Поскольку журнал S2 не новее журнала S1, S2 может голосовать за S1, а S1 избирается двумя голосами (поскольку S1 считает, что кластер имеет только три узла). И S5 точно получит голоса S3 и S4, потому что S1 не может воспринимать S4, не отправляет ему RPC RequestVote, и лог S1 отстает от S3, S3 точно не проголосует за S1, а S5 избирается тремя голосами . В конце концов в кластере произошла фатальная ошибка с несколькими главными узлами, также известная как «расщепленный мозг».

*фигура 2

Рисунок 2 взят из статьи и представляет ту же проблему, что и рисунок 1, но в другой форме. Значение цвета соответствует рисунку 1, вproblem: two disjoint majoritiesНа данный момент в кластере может быть два лидера.

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

Источник: «Подробное объяснение протокола плота» Зная Бога.

zhuanlan.zhihu.com/p/27207160

*изображение 3

Этот гипотетический сценарий аналогичен этапу d на рисунке 1, а процесс моделирования выглядит следующим образом:

S1 является исходным лидером кластера, а в кластер добавлены S4 и S5.Эта конфигурация была передана на S3, но S2 еще не получила ее.
В это время S1 отключается на короткое время, а S2 и S3 запускают выборы мастера соответственно.
В итоге S2 получил S1 и свои голоса, S3 — S4, S5 и свои голоса, и в кластере появились два лидера.

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

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

Каждый кандидат должен иметь последнюю версию (термин, индекс) своего локального журнала в RPC RequestVote.Если ведомый обнаружит, что в журнале кандидата нет собственного нового журнала, он откажется голосовать за кандидата.

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

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

1.2 Конфигурация элемента кластера двухфазной коммутации

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

первый этап

Клиент отправляет C-new лидеру, а лидер забирает C-old и C-newсоюзи применимы сразу, обозначим какC-old,new.
Лидер оборачивает C-старые, новые по мере синхронизации логов с другими узлами.
Последователь применяется сразу после получения C-old, new, когда большинство узлов **C-old, new (то есть большинство узлов C-old и большинство узлов C-new)** переключается, лидер будет фиксировать журнал.

второй этап

Затем Leader оборачивает C-new как синхронизацию журнала с другими узлами.
Подписчики подают заявку сразу после получения C-new.Если они обнаружат, что в это время их нет в списке C-new, они будут активно выходить из кластера.
Лидер подтверждаетБольшинство узлов C-newПосле успешного переключения отправьте клиенту ответ об успешном выполнении.

*Рисунок 4

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

Почему эта схема гарантирует отсутствие нескольких лидеров? Разберем процесс пошагово.

Этап 1. C-старый, новый еще не зафиксирован

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

Если взять в качестве примера сценарий на рис. 1, то S5 вообще не имеет шансов стать лидером на этапе d, потому что за него проголосовала только S3 на C-old, что не удовлетворяет большинство.

Этап 2. C-старый, новый зафиксирован, C-новый не выдан

На этом этапе C-old,new был зафиксирован, что может гарантировать, что большинство узлов, которые были C-old,new (Опять же: большинство узлов для C-старых и большинство узлов для C-новых)копировать.

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

Этап 3. C-new выпущен, но еще не зафиксирован

На данном этапе в кластере может быть три типа узлов C-old, C-old, new и C-new, но так как этап 2 уже пройден, узел C-old уже не может стать лидером. Будь то C-старые, новые или C-новые узлы для инициирования выборов, требуется согласие большинства C-новых узлов, поэтому невозможно иметь двух лидеров.

Стадия 4. C-new зафиксирован

На этом этапе C-new зафиксирован, поэтому только C-new узел может получить большинство голосов, чтобы стать лидером. На данный момент кластер благополучно завершил этот раунд изменений и может продолжить запуск следующего раунда изменений.

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

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

2. Сжатие журнала

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

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

снимок(Snapshot) — это распространенный и простой метод сжатия журналов, который используется такими системами, как ZooKeeper и Chubby. Проще говоря, это дамп состояния системы в определенный момент и сохранение его на земле, чтобы все логи до этого момента можно было отбросить. Так что не поймите неправильно слово «сжатие», у нас нет способа «распаковать» моментальный снимок конечного автомата обратно в последовательность журнала.

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

*Рисунок 5

На рисунке 5 показан журнал замены узла (term1, index1) ~ (term3, index5) снимками.

Снимки обычно содержат следующее:

журнал метаданных: последний термин журнала и индекс, примененный к моментальному снимку.
Государственный аппарат: Состояние машины окончательно получено после применения всех предыдущих логов

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

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

Синхронизированные моментальные снимки используют новый метод RPC, называемыйInstallSnapshot RPC.

До сих пор мы в основном объясняли содержание статьи Raft.«В поисках понятного алгоритма консенсуса (расширенная версия)»В конце концов, это всего лишь 18 страниц, и в нем основное внимание уделяется теоретическому описанию, а не инженерной практике. Если вы хотите подробно изучить Raft или написать надежную реализацию Raft самостоятельно,Консенсус: соединение теории и практикиЭто лучший выбор для вашей справки.

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