Как работают алгоритмы выбора лидера в распределенных системах?

Question

[Катя Смирнова]

Здравствуйте, ради интереса решила поизучать тему распределенных, высоконагруженных систем, прочитала пару умных книг, в которых говорилось о репликации и алгоритмах выбора нового лидера (Leader Election) в случае отказа текущего. В частности я узнала об алгоритме Bully, Modified Bully и Ring алгоритмах.

Сразу появилась пара вопросов:

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

Comments

[Crash]

на девушке, задающей такие вопросы, я бы женился xD

Answer 1

[Saboteur]

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

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

Comments

[Катя Смирнова]

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

[Saboteur]

Ну вот в том-то и дело, что между тем как первый узел обнаружит и отправит, другой тоже обнаружить и отправить.
Вы обсуждаете алгоритм, а не конкретную реализацию в конкретном продукте. А во время конкретной реализации всплывает то, что не вся математика подходит под физику без компенсации.
Это как 1+1 всегда 2, а в физике 1 капля + 1 капля будет 1 капля побольше.

Answer 2

[Roman K]

https://raft.github.io/

Answer 3

[Dimonchik]

для капитанов военных кораблей есть такая штукенция типа арифмометра: при торпедной атаке повернуть на столько то градусов - градус штукенция и выбирает

чтобы капитаны не умничали против строгой математики уже за них просчитанной