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

3. Алгоритм Paxos
Позволяет любому узлу попытаться предложить значение, а затем использует кворумное голосование для определения того, какое предложение будет принято. Лидерство переходит к узлу, который последовательно добивается успеха в этой игре.

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

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

Paxos разделяет процесс на два этапа:
- Подготовка/Обещание
- Предложение/Принятие
Каждый узел играет одну или несколько ролей: предлагающего, принимающего и иногда обучающегося (см. диаграмму ниже).

1. Подготовка и обещание
Любой узел может выступать в роли предлагающего. Для начала он генерирует номер предложения, который представляет собой монотонно возрастающий идентификатор.

- Предлагающий отправляет сообщение «Prepare(n)» большинству принимающих, прося их пообещать не принимать предложения с номерами меньше n.
- Когда принимающий получает сообщение «Prepare(n)», он отвечает «Promise(n)», если он ещё не обещал что-то более высокое. Вместе с обещанием он включает предложение с уже принятым им значением (если оно есть).
Этот шаг помогает подавить конфликтующие или устаревшие предложения, гарантируя, что будущие предложения будут либо более новыми, либо основаны на ранее принятых.

Вот пример:
- Предлагающий A отправляет Prepare(100)
- Принимающие 1, 2 и 3 получают его и отвечают:
№1: Promise(100), ранее принятого значения нет
№2: Promise(100), ранее принятое значение (лидер = №4)
№3: Promise(100), ранее принятого значения нет

Теперь узел A знает, что он должен сохранить «№4» в качестве кандидата на лидера, даже если изначально он его не предлагал.

2. Предложение и принятие
Предлагающий выбирает значение:
- Если какой-либо принимающий ответил ранее принятым значением, он должен повторно предложить это значение.
- Если ранее ни одно из них не было принято, он может выбрать своё собственное (например, «выбрать A лидером»).

Он отправляет сообщение «Accept(n, значение)» тому же большинству. Если принимающие за это время не обещали ничего более высокого, они отвечают «Accepted(n, значение)». Как только кворум принимает значение, оно выбирается.

Multi-Paxos
В базовом протоколе Paxos каждое значение требует нового раунда шагов Prepare/Promise и Accept/Accepted. Это затратно и неэффективно, если значения предлагаются часто.

Multi-Paxos оптимизирует этот процесс:
- Выбирается определённый предлагающий, который будет выступать в качестве стабильного лидера.
- Лидеру предоставляется возможность пропускать фазу 1 для последующих значений, повторно используя лидерство до тех пор, пока его никто не оспорит.
Это создаёт форму стабильного лидерства. Лидер не избирается посредством отдельного механизма, а становится единственным узлом, постоянно успешно предлагающим значения.

Почему Paxos сложен?
- Номера предложений должны быть уникальными и упорядоченными глобально.
- Узлы должны сохранять состояние (обещания, принятые значения) при перезапусках.
- Восстановление после частичных сбоев или передачи управления требует тщательной координации.

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

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