292
правки
Изменения
→Алгоритм
== Алгоритм ==
=== Роли ===
Мы хотим достичь согласованного консенсуса.
У нас есть несколько процессов, у каждого есть некоторое подмножество ролей:
* Предлагающий (proposer) — может выдвинуть предложение
* Принимающий (acceptor) — принимают консенсус
* Узнающий (learner) — тот, кто узнаёт про принятый консенсус
Дальше алгоритм говорит исключительно про роли, а не процессы.
Обычно в каждом процессе совмещаются все три роли.
У алгоритма статическая конфигурация: в базовой версии мы не можем добавлять новые роли в процессе работы.
Переконфигурация — отдельная интересная инженерная задача.
=== Лидер ===
Если у нас только один принимающий процесс, то всё просто, но нет защиты от отказов.
По этому должно быть несколько принимающих процессов.
Алгоритм Paxos требует, чтобы решение принималось [[Кворум|кворумом]] процессов.
Обычно берут кворум простого большинства и 3-5 процессов, выбирают из соображений надёжности: процесс может уйти в swap и это нестрашно (система-то асинхронная), а может полностью отказать (тогда его надо физически заменить).
На самом деле мы не пытаемся сразу принять консенсус, а сначала [[Переформулировки консенсуса в распределённой системе#Выбор лидера|выбираем лидера]],
что эквивалентно консенсусу, но зато потом можно очень быстро работать, если никто не падает.
Лидера выбираем из предлагающих процессов (судя по статье на Хабре, а в лекции говорилось, что из принимающих).
Лидера можно просто и быстро выбрать, если нет отказов.
А если есть — можно просто и быстро выбрать (предположив синхронность системы), но, возможно, будет несколько лидеров.
Тем не менее, Paxos всё ещё будет гарантировать согласие и в этом случае.
Возможно, будет работать бесконечно долго, но согласие будет.
А на практике для получения нескольких лидеров надо, чтобы что-то пошло не так ровно в момент выборов лидера, а это очень быстрый процесс.
Так что на практике лидер почти всегда один и всё работает.
=== Алгоритм ===
К консенсусу мы приходим за несколько голосований.
Каждое голосование инициирует лидер (возможно, несколько лидеров параллельно, если нам не повезло).
У каждого голосования есть уникальный номер $k$: нам требуется, чтобы они в голосованиях были уникальны и возрастали.
Этого можно достичь, если номер — это пара из [[Логические часы Лампорта|логических часов]] и фиксированного уникального номера процесса.
Можно не гонять логические часы на вообще все сообщения, а строить их только на известных процессу номерах голосований, тоже пойдёт.
Примерная схема: на фазе 1 лидер добивается от кворума принимающих ''обещание'', что они за него, а на фазе 2 выбирает какое-то предложение и рассылает его своим принимающим.
У принимающего есть две независимых компоненты состояния: кому он что-нибудь ''пообещал'' (только лидер и номер голосования) и какое предложение он ''принял'' (от какого лидера, номер голосования, какое значение).
'''Фаза 1a (подготовка)''': лидер посылает сообщение $(1a, k)$ кворуму принимающих (или вообще всем, а ждёт ответа от кворума?). Пока никаких предложений нет.
'''Фаза 1b (обещание)''': каждый принимающий начинает выбирать предложение с максимальным номером:
# Если пришло предложение больше, чем все предыдущие, то принимающий ''обещает'' лидеру не принимать предложения с меньшим номером, отвечает $(1b, k, ack, 0, 0)$.
Но если какое-то предложение с меньшим номером $k'$ уже было ''принято'' со значением $v'$ (это происходит на фазе 2), то отвечает $(1b, k, ack, k', v')$, чтобы лидер был в курсе.
# Если пришло предложение меньше, чем имеющийся максимум $k''$, ничего не делаем. Ну, можем ответить $(1b, k', nack)$ для оптимизации.
Если лидер видит хотя бы один nack, то он понимает, что его обогнали, и начинает фазу 1 заново, подняв своё $k$ до присланного $k'+1$ (это просто оптимизация, чтобы не тормозить с перевыбором лидера).
Таким образом, если у нас несколько лидеров, они будут друг другу активно мешать.
То есть они в какой-то момент как-то должны догадаться, что их много (как?).
'''Фаза 2a (запрос)''': если лидеру удалось собрать кворум обещаний, то он должен попросить принимающих ''принять'' какое-то значение.
Если ему кто-то сказал, что уже принял значение $v_1$, $v_2$, ..., то выбираем значение с максимальным номером голосования.
А если никто ничего не принимал, то лидер вносит своё предложение.
После этого рассылает предложение принимающим, хотя бы кворуму: $(2a, k, v)$, где $v$ — выбранное лидером предложение.
'''Фаза 2b (подтверждение''': если принимающий получает запрос $(2a, k, v)$ и он ещё не дал обещание для $k' > k$, то он ''принимает'' предложение $(k, v)$ и посылает сообщение $(2b, k, v)$ всем узнающим.
После этого во всех следующих голосованиях всем существующим лидерам принимающий будет сообщать лидеру, что он уже принял какое-то предложение.
А лидер будет пытаться это мнение учитывать.
Узнающий принимает решение: если он получил одинаковое сообщение $(2b, k, v)$ от кворума принимающих, то алгоритм Paxos выбрал значение $v$.
==== Обработка отказов ====
Обычно делается таймаутами(?) и рандомом(?):
* Если лидеру не удалось собрать консенсус за какое-то время, он может забить и попробовать ещё раз.
* Если какой-то узел давно не слышал от лидера, он может инициировать перевыбора
* Если лидер увидел второго лидера, можно выбрать, кому жить (например, тому, у кого номер голосования меньше)
Все эти трюки на корректность не влияют(?) и в каком-то смысле вторичны по сравнению с ядром Paxos.
Но на практике работают хорошо, сбои-то у нас редкие.
==== Количество сообщений ====
На каждый консенсус у нас задержка хотя бы в четыре сообщения: 1a, 1b, 2a, 2b.
==== Наблюдения про корректность ====
Paxos гарантирует, что если было в конце было выбрано значение $v$, то никакое другое никогда больше не может быть выбрано.
В самом деле: если у нас получилось сообщение $(2b, k, v)$ от одного кворума принимающих и сообщение $(2b, k', v')$ от другого кворума принимающих, то эти кворумы пересекаются по принимающему $P$.
Не умаляя общности считаем, что $k < k'$.
Тогда получаем, что $P$ сначала в голосовании $k$ принял от лидера предложение $v$, а потом в голосовании $k' > k$ сообщил об этом лидеру, но тот всё равно выбрал не $v$, а $v'$.
Значит, $v'$ было получено от какого-то принимающего с комментарием "я принял его в голосовании $k'' > k$"
== Модификации ==
