Алгоритм Paxos в контексте транзакции распределенной базы данных

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

Первое, на что следует обратить внимание, это то, что здесь речь идет о двух «ценностях». Во-первых, это значение базы данных, изменяемые данные уровня приложения. Во-вторых, это решение «зафиксировать» / «прервать». Для транзакций на основе Paxos консенсусной «ценностью» является решение «зафиксировать» / «прервать».

Важный момент, о котором следует помнить о транзакциях базы данных в отношении консенсуса Paxos, заключается в том, что Paxos не гарантирует, что все партнеры, участвующие в транзакции, действительно увидят консенсусное решение. Когда это необходимо, как это обычно бывает с базами данных, приложение должно гарантировать, что это произойдет. Это означает, что состояние, сохраняемое некоторыми одноранговыми узлами, может отставать от других, и любому приложению базы данных, построенному на основе Paxos, потребуется какой-то механизм для обработки этого. Это может быть очень сложно и все зависит от приложения, поэтому я собираюсь полностью игнорировать все это и сосредоточиться на обеспечении того, чтобы простое большинство всех реплик базы данных согласовывалось со значением версии 2 ключа базы данных FOO, что, конечно же, изначально установлен на BAR.

Первый шаг - отправить новое значение для FOO, скажем, BAZ, и это ожидаемая текущая ревизия, 1, вместе с сообщением Paxos Prepare. Когда реплики базы данных получают это сообщение, они сначала ищут свою локальную копию FOO и проверяют, соответствует ли текущая ревизия ожидаемой ревизии, включенной вместе с сообщением Подготовить. Если они совпадают, реплика базы данных объединит флаг «Vote Commit» вместе с сообщением Promise, отправленным в ответ на Prepare. Если они не совпадают, вместо этого будет отправлено сообщение «Отмена голосования» (проверка исправлений защищает от случая, когда значение было изменено с момента последнего чтения приложением. Разрешение перезаписи в этом случае может привести к повреждению состояния приложения).

Как только драйвер транзакции получает кворум сообщений Promise вместе со связанными с ними значениями «Vote Commit» / «Vote Abort», он должен выбрать либо «Commit», либо «Abort». Первым шагом при выборе этого значения является выполнение требования Paxos по проверке сообщений Prepare, чтобы увидеть, принял ли какой-либо репликант базы данных (Acceptor в терминах Paxos) уже сообщение " Принять решение "/" Отменить ". Если какой-либо из них имеет, то драйвер транзакции должен выбрать значение «Фиксация» / «Прервать», связанное с наивысшим ранее принятым идентификатором предложения. Если у них нет, он должен решить сам. Это можно сделать, просмотрев значения «Подтверждение голосования» / «Прерывание голосования», связанные с обещаниями. Если присутствует кворум «Голосование Commmit», драйвер транзакции может предложить «Commit», в противном случае он должен предложить «Abort».

С этого момента происходит обмен стандартными сообщениями Paxos, пока не будет достигнут консенсус по решению «Применить» / «Прервать». Предполагая, что выбрано «Commit», репликанты базы данных обновят значение и ревизию, связанные с FOO, до BAZ и 2, соответственно.

В простой бумаге Paxos made simple используются разные виды paxos. Один - Паксос (простой Паксос, Паксос одной степени, синод), другой - Мульти-Паксос. С точки зрения инженера, первый - это распределенный регистр однократной записи, а второй - распределенный журнал только с добавлением записи.

Ответы:

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

   В контексте Multi-Paxos фактическое значение - это последнее значение, добавленное в журнал.

2. С Multi-Paxos мы просто добавляем новое значение в журнал. Чтобы прочитать текущее значение, мы читаем журнал и возвращаем последнюю версию. На нижнем уровне Multi-Paxos представляет собой массив регистров Paxos. Чтобы записать новое значение, мы помещаем его вместе с текущим значением в свободный регистр, а затем заполняем предыдущие свободные регистры нерабочими. Когда два регистра содержат два разных следующих значения для одного и того же предыдущего значения, мы выбираем регистр с самой низкой позицией в массиве.

3. С Multi-Paxos это возможно и тривиально: мы просто начинаем новый раунд Paxos через бесплатную регистрацию. Хотя простой Paxos не покрывает его, мы можем расширить его и превратить в распределенную переменную вместо dist. регистр. Я описал эту идею и доказательство в памятке о том, как работает Paxos сообщение.

Я написал длинный блог со ссылками на исходный код по теме репликации журнала транзакций с помощью paxos, как описано в Бумага Paxos Made Simple. Здесь я дам краткие ответы на ваши вопросы. Сообщение в блоге и исходный код показывают полную картину.

С одной стороны, я понимаю, что это делается для сохранения консенсуса. Но с другой стороны, у меня возникла путаница по поводу того, что на самом деле представляет собой значение - какой смысл в том, чтобы «отправлять принимающим значение, которое было принято ранее»?

Значение - это команда, которую клиент пытается запустить в кластере. Во время простоя значение клиента, переданное всем узлам последним лидером, могло достигнуть только одного узла из оставшегося большинства. Новый лидер может не быть этим узлом. Новый лидер обнаруживает значение клиента по крайней мере от одного уцелевшего узла и затем передает его всем узлам в оставшемся большинстве. Таким образом, новый лидер сотрудничает с мертвым лидером, чтобы завершить любую работу с клиентом, которую он, возможно, выполнял.

Что делать, если в контексте транзакций базы данных требуется зафиксировать новое значение? Нужно ли запускать новый экземпляр Paxos?

Он не может выбирать какие-либо новые команды от клиентов, пока он не перестроит историю выбранных значений, выбранных последним лидером. В сообщении блога об этом говорится как о «фазе смены лидера», когда после отказа старого лидера новый лидер пытается полностью обновить все узлы.

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

Если ответ на поставленный выше вопрос «Да», то как акцептанты сбрасывают состояние?

Они этого не делают. Существует разрыв между выбранным значением и любым узлом, узнавшим, что это значение было выбрано. В контексте базы данных вы не можете «зафиксировать» значение (применить его к хранилищу данных), пока не «изучите» выбранное значение. Paxos гарантирует, что выбранное значение никогда не будет отменено. Так что не фиксируйте значение, пока не узнаете, что значение было выбрано. Сообщение в блоге дает более подробную информацию об этом.

Это из моего опыта реализации рафта и чтения статьи ZAB. Какие два наиболее распространенных воплощения PAXOS. Я не особо разбирался в простых paxos или multipaxos.

Когда клиент отправляет фиксацию на любой узел в кластере, он перенаправляет эту фиксацию лидеру, затем лидер отправляет сообщение фиксации каждому узлу в кворуме, когда все узлы подтверждают фиксацию, которую он зафиксирует в собственном журнале .