День 2382. #ЗаметкиНаПолях
Алгоритмы Выбора Главного Узла в Распределённых БД. Продолжение
1. Алгоритм Забияки
2. Кольцевой Алгоритм
3. Алгоритм Paxos

4. Алгоритм Raft
Raft существует, потому что Paxos, несмотря на свою мощь, сложен в реализации и ещё сложнее в понимании. Raft предоставляет те же гарантии безопасности, что и Paxos, например, отсутствие двух лидеров одновременно, согласование журнала и отслеживание прогресса при наличии кворума. Однако архитектуру проще отслеживать, отлаживать и развёртывать.

Каждый узел Raft находится в одном из трёх состояний:
- Ведомый (Follower) - пассивный узел, слушает лидера и отвечает на запросы.
- Кандидат (Candidate) - пытается стать лидером при отсутствии тактовых импульсов.
- Лидер (Leader) - активный узел, который обрабатывает все клиентские запросы и репликацию.

Узлы начинают работу как ведомые. Если они слишком долго не получают ответ от лидера (по тактовым импульсам), они считают лидера мёртвым и запускают выборы (см. диаграмму ниже).

Raft предотвращает конфликты выборов, используя рандомизированные таймауты. Каждый ведомый начинает обратный отсчёт со случайным значением, например, от 150 до 300 миллисекунд. Если до истечения таймера он не получает ответа от лидера, он становится кандидатом и начинает выборы.

Кандидат:
- Увеличивает свой срок полномочий (своего рода счётчик эпох).
- Голосует за себя.
- Отправляет RPC-запросы «RequestVote» всем остальным узлам.
- Другие узлы будут голосовать за кандидата только в том случае, если:
они не голосовали в текущем сроке полномочий и журнал кандидата как минимум не менее актуален, чем их собственный.
- Если кандидат получает голоса большинства, он становится новым лидером и начинает отправлять тактовые импульсы для поддержания своего статуса. Если ни один из кандидатов не побеждает (например, голоса разделились), все ждут и повторяют попытки с новыми таймаутами. Такой рандомизированный подход гарантирует, что один из узлов в итоге опередит остальных.

Raft использует сроки полномочий (term) для отслеживания эпох лидерства. Каждая запись в журнале привязана к сроку полномочий, в котором она была создана. Это позволяет легко обнаруживать и отклонять устаревших или конфликтующих лидеров. Перед голосованием узлы сравнивают журналы. Кандидат с устаревшим журналом будет отклонён, даже если его запрос первым достигнет других узлов. Это гарантирует, что лидером может стать только узел с самой актуальной версией журнала. Затем лидеры реплицируют новые записи журнала на ведомых с помощью RPC-вызовов «AppendEntries». После того, как кворум подтвердил запись, она считается подтверждённой.

Raft решает проблему разделения власти, применяя правила кворума:
- Лидер должен иметь поддержку большинства узлов.
- Два лидера не могут быть активны в одном и том же сроке.
- Ведомый принимает запросы только от лидера текущего срока.
- Если устаревший лидер пытается действовать после разделения сети, он немедленно отклоняется ведомыми с более новым сроком.

Эта чёткая структура позволяет избежать неоднозначности, характерной для таких протоколов, как базовый Paxos, где одновременное выдвижение предложений может замедлять работу узлов или приводить системы в состояние неопределённости.

Окончание следует…

Источник: https://blog.bytebytego.com/p/top-leader-election-algorithms-in