предисловие

Raftтакжеалгоритм консенсуса,иPaxosЦель та же. Но у него есть другое имя -Простой для понимания алгоритм консенсуса.PaxosиRaftвсе для достиженияпоследовательностьпроизведено. Этот процесс похож на выборы.Кандидатнужно убедитьбольшинство избирателей(Сервер) проголосуйте за него и следуйте его действиям после выбора.PaxosиRaftРазница в выборахКонкретный процессразные.

текст

Мелкий измельчитель

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

Вопрос: Два человека, А и Б, по очереди раскладывают на круглом столе черные и белые фигуры го, по одной, причем фигуры не должны перекрывать друг друга. Как мне сказать, чтобы выиграть?

Этот вопрос имеет два значения: во-первых, есть ли способ гарантировать победу? Во-вторых, если да, то как это доказать?

Приведенная выше картинка ответила на этот вопрос, то есть победит первая линия, здесь используйте три разных способа объяснения:

1. Предположим, что стол размером с шахматную фигуру.

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

3. Один круг можно нарисовать из нескольких маленьких кругов одинакового диаметра, касающихся друг друга.

Три разных способа мышления постепенно усложняют разборчивость.

1. Первыйминималистское мышление, но математическинесерьезноиз.

2. Второйограничить мышление, в сочетании с первымМатематическая индукция, что математическитщательныйиз.

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

Что такое Рафт-протокол

RaftСоглашение будетServerПроцессы делятся на три категории, а именноLeader,Candidate,Follower. ОдинServerПроцесс может быть только одним изтип, но это не исправлено. В разное время она может иметь разные виды,ServerКак изменится тип процесса, будет объяснено позже.

вRaftВ кластере, организованном по протоколу, есть три типа ролей:

• Лидер
• Последователь (масса)
• Кандидат

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

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

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

Процесс избрания лидера

При минималистском мышлении минимальнаяRaftПотребности демократического кластератри участника(Как показано ниже:A,B,C), так что возможно большинство голосов.

начальное состояниеABCобаFollower, а затем инициировать выборы. В это время естьтривозникает возможная ситуация. Первые два на следующем рисунке могут быть выбраныLeader, третий показывает, чтоЭтот раунд голосования недействителен(Split Votes). В третьем случае каждая партия проголосовала за себя, и ни одна из партий не получила большинства. послекаждый участникСделай перерыв(Election Timeout) повторно инициировать голосование до тех пор, пока одна из сторон не получит большинства. Тут главное случайностьtimeout, сначала изtimeoutПартия, возобновившая голосование вtimeoutдругие двазапросить голосование, то он может голосовать только за себя, что приводит к быстрому соглашению.

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

Влияние лидера на последовательность

Raftпротоколсильная зависимость LeaderузлаДоступность, чтобы гарантировать, что кластерсогласованность данных.поток данныхтолько отLeaderУзел вFollowerПеренос узла. Конкретный процесс выглядит следующим образом:

1. когдаClientк кластеруLeaderузелотправить данныеЗадний,Leaderузелполученные данныевнезафиксированный статус(Uncommitted).

2. тогдаLeaderузел будетодновременновсеFollowerузелскопировать данныеижду ответа.

3. по крайней мере в кластеребольше половиныузелПолучилаПолучив данные,LeaderсноваClientПодтвердить данныеПолучила.

4. однажды, чтобыClientотправить данные получитьAckПосле ответа указывает, что на этот разстатус данныхВходитьОтправлено(Committed),Leaderперенаправление узлаFollowerУзел отправляет уведомление, чтобы сообщитьСтатус данных отправлен.

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

1. Сценарий 1

Излишне говорить, что до того, как данные достигнут узла-лидера, лидер зависает на этом этапе, не влияя на согласованность.

2. Сценарий 2

Данные поступают на узел-лидер, но не реплицируются на узел-ведомый.

этот этапLeaderповесить трубку, данные принадлежатнезафиксированный статус,Clientне получитAckподумал бытайм-аут не удалсяБезопасно инициироватьПовторить попытку.

FollowerНа узле таких данных нет,переизбраниеЗаднийClientПовторить попыткуОтправить повторноможет быть успешным. оригинальныйLeaderузелвосстанавливатьсяпозже какFollowerПрисоединиться к кластеру, перезапустить стекущий срокновыйLeaderгдеСинхронные данные, вынуждены держать иLeader Данные согласованы.

3. Сценарий 3

Данные поступают на узел-лидер и успешно реплицируются на все узлы-последователи, но ведомый еще не ответил ведущему.

этот этапLeaderповесить трубку, хотя данные естьFollowerузел находится внезафиксированный статус(Uncommitted),нобыть последовательнымиз. переизбратьLeaderможно закончить позжепредставление данных.

В настоящее времяClientПоскольку вы не знаете, была ли отправка успешной или нет, вы можете повторить отправку. Ввиду этой ситуацииRaftТребоватьRPCвыполнение запросаидемпотентность, то есть добитьсяВнутренний механизм дедупликации.

4. Сценарий 4

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

этот этапLeaderповесить трубку, данные естьFollowerузел находится внезафиксированный статус(Uncommitted)инепоследовательный.

RaftПротокол требует, чтобы голоса могли быть поданы только за тех, ктоПоследние данныеузел. Таким образом, узел с последними данными будет выбран какLeader,после этогоПринудительно синхронизировать данныек другомуFollower,гарантироватьДанные не будут потеряныив конечном итоге последовательный.

5. Сценарий 5

Когда данные достигают узла-лидера, они успешно реплицируются на все или большинство узлов-последователей.Данные находятся в состоянии «Отправлено» на ведущем узле, но в состоянии «Не отправлено» на ведомом.

этот этапLeaderповесить трубку,переизбратьновыйLeaderПроцесс и этапы постобработки3Такой же.

6. Сценарий 6

Данные достигают узла-лидера и успешно реплицируются на все или большинство узлов-последователей Данные находятся в состоянии отправки на всех узлах, но еще не ответили клиенту.

этот этапLeaderЕсли он зависает, данные внутри кластера на самом деле ужепоследовательный,ClientПовторные попытки основаны на парах идемпотентных политик.Консистенция не влияет.

7. Сценарий 7

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

сетевой разделоригиналLeaderузел иFollowerузлы разделены,Followerне могу получитьLeaderизсердцебиениебудетсноваИнициировать выборы для создания новогоLeader, затем производитДвойной лидерФеномен.

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

восстановление сетипосле старогоLeaderнашел в кластереСрок обновления(Term)новыйLeader,ноАвтоматический переход на более раннюю версиюзаFollowerи возобновитьLeaderгдеСинхронные данныедостичь кластераДанные согласованы.

Результаты проверки

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

резюме

PaxosАлгоритмLeslie Lamportсуществует1990Он был публично опубликован на собственном веб-сайте в 2018 году. Когда мы узнали об этом? Когда будет полезная реализация? иRaftАлгоритм2013Опубликовано в году, на который все ссылаютсяБиблиотека реализации Raft с открытым исходным кодом, вы можете видеть, что есть многоБиблиотека реализации с открытым исходным кодом,Этопонятностьважность.

Ссылки по теме

1. Распределенная теория (1) - теорема CAP
2. Распределенная теория (2) - BASE Theory
3. Распределенная теория (3) - протокол 2PC
4. Распределенная теория (4) — протокол 3PC
5. Распределенная теория (5) - Алгоритм согласованности Paxos
6. Распределенная теория (6) — Плот протокола согласованности

---

Добро пожаловать в публичный аккаунт: Zero One Technology Stack

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