5 алгоритмов выбора лидера базы данных
(продолжение предыдущего поста)

Лидер базы данных (leader, master, primary) — это основной узел в кластере баз данных при репликации на основе лидера (leader‑based replication, «главный – подчинённый»).
Алгоритм выбора лидера — это процесс в системе распределённых вычислений, который назначает один процесс организатором некоторой задачи, распределённой на несколько компьютеров (узлов).

1. Bully Algorithm (Алгоритм «хулигана»)
- Принцип работы: использует уникальные числовые ID узлов. Узлом-лидером становится узел с наибольшим ID.
- Механизм:
- координаторы обмениваются информацией;
- если один из узлов выходит из строя (Node Down), остальные координаторы продолжают процесс выбора;
- узел с наибольшим ID автоматически становится лидером.
- Особенности: простота реализации, но возможна задержка в выборе лидера при сбоях узлов.

2. Ring Algorithm (Кольцевой алгоритм)
- Принцип работы: узлы организованы в логическое кольцо, где они передают свои ID по кругу. Лидером становится узел с наибольшим ID в кольце.
- Механизм:
- узлы циркулируют свои ID по кольцу;
- каждый узел сравнивает полученный ID с собственным;
- если полученный ID больше — он передаётся дальше;
- узел, у которого ID оказался наибольшим, становится лидером (INITIATOR NODE).
- Особенности: упорядоченность процесса, но время выбора лидера зависит от размера кольца и скорости передачи данных.

3. Paxos Algorithm (Алгоритм Paxos)
- Принцип работы: кворум-основанный консенсусный алгоритм для выбора лидера. Требует согласия большинства узлов для принятия решения.
- Механизм:
- Proposer (Предложение): выдвигает кандидатуру на роль лидера;
- Acceptor (Принявший): рассматривает предложения и голосует;
- Learner (Ученик): получает итоговое решение после выбора лидера.
- Особенности: высокая надёжность и устойчивость к сбоям, но сложность реализации и высокая нагрузка на сеть из-за множества обменов сообщениями.

4. Raft Algorithm (Алгоритм Raft)
- Принцип работы: кандидаты запрашивают голоса у других узлов, и первый кандидат, получивший большинство голосов, становится лидером.
- Механизм:
- Follower (Последователь): пассивный узел, который может стать кандидатом;
- Candidate (Кандидат): инициирует выборы, отправляя запросы на голосование;
- Leader (Лидер): выбранный узел, который управляет кластером.
- Процесс включает этапы: старт, тайм-аут (инициирует новые выборы), получение большинства голосов (продвижение к роли лидера), потеря выборов (возврат к статусу последователя).
- Особенности: простота понимания и реализации по сравнению с Paxos, хорошая масштабируемость, устойчивость к сетевым задержкам.

5. Zookeeper Atomic Broadcast (Атомарная трансляция Zookeeper)
- Принцип работы: выбор лидера осуществляется с использованием эфемерных последовательных znodes (узлов Zookeeper).
- Механизм:
- узлы обмениваются сообщениями (Propose, ACK, Commit);
- один из узлов становится лидером и координирует работу остальных;
- последователи (FOLLOWER) подтверждают получение команд от лидера (ACK);
- после подтверждения лидер фиксирует изменения (Commit).
- Особенности: высокая надёжность благодаря использованию Zookeeper, атомарность трансляции сообщений, подходит для распределённых систем с высокой доступностью.