В чем преимущество передовых алгоритмов главных выборов перед алгоритмом хулиганов?

Я читал, как современные алгоритмы выбора мастера, такие как Raft, Paxos или Zab, выбирают мастера в кластере, и не мог понять, почему они используют сложные алгоритмы вместо простого алгоритма хулигана.

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

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

Может кто-нибудь уточнить это?


cluster-computing distributed-computing apache-zookeeper raft paxos
person Boyolame    schedule 19.12.2014    source источник
comment
Если у вас есть временное разделение в вашей сети, которое позже закрывается, узлы могут не соглашаться, кто самый старший, верно?   -  person Christopher Creutzig    schedule 20.12.2014

Ответы (1)


arrow_upward
7
arrow_downward

С теоретической точки зрения Raft, Paxos и Zab не являются алгоритмами выбора лидера. Они решают другую проблему, называемую консенсусом.

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

Следствие таково. Если безопасность системы зависит от присутствия единственного лидера, у вас могут возникнуть проблемы, полагаясь только на его выборы. Рассмотрим пример. Узлы получают сообщения от многоадресной рассылки UDP и делают A, если отправитель является лидером, но делают B, если отправитель не является лидером. Если два узла проверят наличие самого старого узла в кластере в несколько разные моменты времени, они могут увидеть разных лидеров. Эти два узла могут затем получить многоадресное сообщение и обработать его разными способами, возможно, нарушив какое-то свойство безопасности системы, которое вы хотите сохранить (например, все узлы либо выполняют A, либо B, но ни один из них не выполняет A, а другой - Б).

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

Здесь две заметки. Во-первых, алгоритм хулигана определен для синхронных систем. Если вы действительно реализуете его, как описано в статье Гарсиа-Молина, я считаю, что вы можете столкнуться с проблемами в вашей частично синхронной системе. Во-вторых, алгоритм Zab основан на своего рода алгоритме хулигана для асинхронных систем. Лидер выбирается путем сравнения длины их историй (что сводит к минимуму время восстановления системы). Как только лидер выбран, он пытается запустить протокол Zab, который, в свою очередь, блокирует эпоху для лидера.

person danyhow    schedule 20.12.2014