Paxos

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

Это первый придуманный практический алгоритм консенсуса такого вида. Он быстро работает и не приходит к согласию в очень редких случаях, на практике такого не случается.

Описан много где разными словами. Обычно используется для хранения самых-самых важных данных.

Тут довольно много деталей опущено, так что реализовать это на практике довольно сложно.

Алгоритм

Роли

Мы хотим достичь согласованного консенсуса. У нас есть несколько процессов, у каждого есть некоторое подмножество ролей:

• Предлагающий (proposer) — может выдвинуть предложение
• Принимающий (acceptor) — принимают консенсус
• Узнающий (learner) — тот, кто узнаёт про принятый консенсус

Дальше алгоритм говорит исключительно про роли, а не процессы. Обычно в каждом процессе совмещаются все три роли.

У алгоритма статическая конфигурация: в базовой версии мы не можем добавлять новые роли в процессе работы. Переконфигурация — отдельная интересная инженерная задача.

Лидер

Если у нас только один принимающий процесс, то всё просто, но нет защиты от отказов. По этому должно быть несколько принимающих процессов. Алгоритм Paxos требует, чтобы решение принималось кворумом процессов. Обычно берут кворум простого большинства и 3-5 процессов, выбирают из соображений надёжности: процесс может уйти в swap и это нестрашно (система-то асинхронная), а может полностью отказать (тогда его надо физически заменить).

На самом деле мы не пытаемся сразу принять консенсус, а сначала выбираем лидера, что эквивалентно консенсусу, но зато потом можно очень быстро работать, если никто не падает. Лидера выбираем из предлагающих процессов (судя по статье на Хабре, а в лекции говорилось, что из принимающих).

Лидера можно просто и быстро выбрать, если нет отказов. А если есть — можно просто и быстро выбрать (предположив синхронность системы), но, возможно, будет несколько лидеров. Тем не менее, Paxos всё ещё будет гарантировать согласие и в этом случае. Возможно, будет работать бесконечно долго, но согласие будет.

А на практике для получения нескольких лидеров надо, чтобы что-то пошло не так ровно в момент выборов лидера, а это очень быстрый процесс. Так что на практике лидер почти всегда один и всё работает.

Алгоритм

К консенсусу мы приходим за несколько голосований. Каждое голосование инициирует лидер (возможно, несколько лидеров параллельно, если нам не повезло).

У каждого голосования есть уникальный номер $k$: нам требуется, чтобы они в голосованиях были уникальны и возрастали. Этого можно достичь, если номер — это пара из логических часов и фиксированного уникального номера процесса. Можно не гонять логические часы на вообще все сообщения, а строить их только на известных процессу номерах голосований, тоже пойдёт.

Примерная схема: на фазе 1 лидер добивается от кворума принимающих обещание, что они за него, а на фазе 2 выбирает какое-то предложение и рассылает его своим принимающим. У принимающего есть две независимых компоненты состояния: кому он что-нибудь пообещал (только лидер и номер голосования) и какое предложение он принял (от какого лидера, номер голосования, какое значение).

Фаза 1a (подготовка): лидер посылает сообщение $(1a, k)$ всем принимающим (и ждёт ответа от кворума на второй фазе). Пока никаких предложений нет.

Фаза 1b (обещание): каждый принимающий начинает выбирать предложение с максимальным номером:

1. Если пришло предложение больше, чем все предыдущие, то принимающий обещает лидеру не принимать предложения с меньшим номером, отвечает $(1b, k, ack, 0, 0)$.

Но если какое-то предложение с меньшим номером $k'$ уже было принято со значением $v'$ (это происходит на фазе 2), то отвечает $(1b, k, ack, k', v')$, чтобы лидер был в курсе.

1. Если пришло предложение меньше, чем имеющийся максимум $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_1 > k$."

Модификации

Переконфигурация — отдельная задача.

Multi paxos

Если нам нужно прийти к нескольким консенсусам, то можно вместо запуска нескольких копий Paxos выполнить выбор лидера и первую фазу один раз для всех копий сразу. Тогда в них будут одинаковые голосования, но они всё ещё будут работать. Зато сильно сокращается задержка.

Dynamic Paxos

Можно добавить отдельную операцию "изменение конфигурации" в RSM.

Cheap Paxos

Если мы хотим пережить много отказов и нам нужно много процессов, то базовый Paxos посылает сообщение всем и ждёт кворума. Работает быстро, но шлёт много сообщений. Можно сначала слать только какому-то конкретному элементу кворума, а остальных игнорировать. И подключать остальных только если кворум долго не отвечает.

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