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

Question

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

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

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

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

Answer 1

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

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

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

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

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