День 2379. #ЗаметкиНаПолях
Алгоритмы Выбора Главного Узла в Распределённых БД. Начало
Распределённые системы БД нуждаются в координации для корректной работы. Когда несколько узлов реплицируют данные и обрабатывают запросы между регионами или зонами, определённый узел должен взять на себя управление операциями записи. Этот узел обычно называется лидером: единый узел, отвечающий за упорядочивание обновлений, фиксацию изменений и обеспечение согласованности системы даже в случае сбоя.

Выбор лидера существует для ответа на простой, но важный вопрос: какой узел в данный момент отвечает за управление? Процесс выбора должен выдерживать реальные нагрузки, включая сбои процессов, задержки в сети, разделы, перезапуски и непредсказуемую потерю сообщений. В случае сбоя главного узла система должна обнаружить его, согласовать замену и продолжить работу, не повреждая данные и не обрабатывая один и тот же запрос дважды. Это проблема отказоустойчивости и консенсуса, лежащая в основе проектирования распределённых БД.

Рассмотрим основные подходы к выбору лидера, каждый со своими предположениями, сильными сторонами и компромиссами.

1. Алгоритм забияки (Bully)
Основан на базовом правиле: узел с наивысшим идентификатором становится лидером. Если узел замечает, что текущий лидер не отвечает, он пытается взять на себя управление.

Каждому узлу присваивается уникальный числовой идентификатор. Чем он выше, тем выше «ранг» узла. Все узлы заранее знают идентификаторы друг друга, что важно для работы алгоритма.

Предположим, имеются узлы с идентификаторами от 1 до 5. Узел 5 в настоящее время является лидером.
Если №5 выходит из строя, и №3 замечает это (например, перестаёт получать сигналы), №3 инициирует выборы.

Вот как может работать такой процесс (см. диаграмму ниже):
A) №3 обнаруживает, что ведущий узел №5 вышел из строя.
№3 отправляет сообщения о выборах узлам 4 и 5.
B) №4 активен и отвечает «OK».
№3 отступает, увидев ответ от узла с более высоким идентификатором.
C) №4 отправляет сообщения о выборах №5.
D) Если №5 вышел из строя, №4 не получает ответа.
E) №4 становится ведущим и рассылает сообщение координатора всем узлам.

Процесс останавливается, когда все узнают, кто новый лидер.

Если узел с более низким ID инициирует выборы, а несколько узлов с более высоким ID активны, все они могут ответить сообщениями «OK» или «Я активен». Однако эти ответы не объявляют лидерство. Они лишь указывают: «Мой ID выше вашего. Вы не подходите для роли лидера. Я возьму на себя процесс выборов».

После отправки сообщения «OK» каждый из этих узлов с более высоким ID начинает выборы, отправляя сообщения о выборах узлам с ещё более высокими ID. Этот процесс каскадируется вверх по цепочке.

Предположения
- Все узлы знают идентификаторы друг друга.
- Узлы взаимодействуют по надёжным каналам связи.
- Отказ лидера может быть точно обнаружен.

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

Продолжение следует…

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