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

5. Zookeeper и Zab
ZooKeeper не является БД. Он не хранит записи пользователей, индексы запросов и не реплицирует записи журнала. Вместо этого он играет важнейшую роль в распределённой экосистеме: координирует работу. Когда системам требуется выбрать брокера, управлять отказоустойчивостью лидера или синхронизировать конфигурацию, ZooKeeper — незаменимый сервис.

Внутренне ZooKeeper использует протокол Zab (ZooKeeper Atomic Broadcast). Zab обрабатывает как выбор лидера, так и репликацию состояния, гарантируя безопасность, согласованность и отказоустойчивость даже метаданных координации (см. диаграмму ниже).

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

Каждая транзакция в ZooKeeper помечается zxid (идентификатором транзакции ZooKeeper), который объединяет эпоху лидера и индекс журнала. Это позволяет узлам определять, кто имеет наиболее актуальную картину мира.

Во время выборов лидера в Zab:
- Предпочтение отдаётся кандидату с наиболее актуальным ZXID.
- Новый лидер должен пройти фазу синхронизации состояния с кворумом, прежде чем сможет фиксировать новые транзакции.
- Если синхронизация не удаётся, выборы завершаются неудачей, и повторяются.

Итого
Каждый алгоритм выборов лидера решает одну и ту же фундаментальную задачу: выбор одного надёжного лидера в распределённой системе. Но они подходят к этому с разными допущениями, компромиссами и эксплуатационными характеристиками.

- Алгоритмы Забияки и Кольцевой используют детерминированные правила, основанные на идентификаторах узлов. Paxos, Raft и Zab используют принятие решений на основе кворума.
- Для обеспечения отказоустойчивости алгоритм Забияки предполагает надёжные соединения и точное обнаружение сбоев. Узел, ложно помеченный как мёртвый, может привести к появлению нескольких лидеров или частым перевыборам. Кольцевой алгоритм останавливается, если любой узел в кольце выходит из строя без предупреждения. В отличие от этого, Paxos, Raft и Zab допускают частичные сбои и продолжают принимать безопасные решения.
- С точки зрения производительности, Raft и ZooKeeper/Zab предсказуемо справляются с перевыборами. Алгоритмы Забияки и Кольцевой неэффективны в средах с высокой текучестью. Paxos, особенно в базовой версии, может испытывать трудности при наличии нескольких предлагающих узлов и нечётком лидерстве, если не использовать такие усовершенствования, как Multi-Paxos.
- Алгоритмы Забияки и Кольцевой просты в реализации. Raft требует больше усилий. Paxos довольно сложно настроить правильно. ZooKeeper/Zab скрывает сложность за API, но лежащие в его основе механизмы нетривиальны.

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