ЯдроКодаподготовка к экзаменам
Подготавливаем текст, источники и редакционные примечания без изменения разметки страницы.
Пошаговый разбор single-decree Paxos: роли, prepare/accept, пересечение кворумов, различие safety и liveness и требования к реализации.
Paxos решает задачу консенсуса: несколько процессов должны выбрать одно значение, несмотря на потерю, задержку и повтор сообщений, а также остановку части узлов. Алгоритм известен сложной репутацией, но его ядро строится вокруг одной идеи: любые два большинства пересекаются, а новая попытка обязана сохранить уже принятое значение, о котором узнаёт в этом пересечении.
Safety означает, что два разных значения не будут выбраны. Это свойство Paxos сохраняет при произвольных задержках и перестановках сообщений в принятой модели crash faults. Liveness означает, что значение когда-нибудь будет выбрано. Для прогресса нужны дополнительные условия: достаточно доступных acceptor, доставка сообщений и период, когда конкурирующие proposer перестают постоянно перебивать друг друга.
Фраза «Paxos работает при сетевом сбое» без этого разделения вводит в заблуждение. Во время длительного разделения сеть может не собрать кворум и остановить запись, сохранив безопасность. Алгоритм не обещает одновременно ответить всем изолированным сторонам.
В объяснении Lamport есть proposer, acceptor и learner. Один физический процесс может выполнять несколько ролей.
Single-decree Paxos выбирает одно значение. Реплицированный журнал требует последовательности экземпляров и практического протокола вроде Multi-Paxos, где стабильный лидер повторно использует подготовленное лидерство для многих позиций.
Proposer выбирает уникальный, больший прежних ballot n и отправляет prepare(n). Acceptor отвечает promise, если ещё не обещал ballot больше n. Вместе с обещанием он сообщает последнее принятое предложение, если оно есть.
Proposer ждёт ответы кворума. Если хотя бы один acceptor уже принимал значение, proposer обязан выбрать значение с максимальным ballot среди полученных accepted-состояний. Если никто ничего не принимал, можно предложить собственное значение.
Именно это правило переносит выбранное значение в будущие раунды. Новый лидер не «побеждает старое большинство» произвольным payload: пересечение кворумов сообщает ему достаточно истории.
После успешной подготовки proposer отправляет accept(n, value). Acceptor принимает запрос, если не обещал ballot больше n. Значение считается выбранным, когда его приняли acceptor из кворума. Learner может узнать это из подтверждений либо через отдельный канал распространения.
Три acceptor выдерживают остановку одного: кворум равен двум. Для устойчивости к f crash failures обычно требуется 2f+1 acceptor и кворум f+1. Это не защита от византийского поведения: узел, который лжёт или нарушает протокол, выходит за модель классического Paxos.
Минимальную проверку можно сделать перебором. Для пяти acceptor любой кворум из трёх пересекается с любым другим:
from itertools import combinations
acceptors = set(range(5))
quorums = [set(group) for group in combinations(acceptors, 3)]
for left in quorums:
for right in quorums:
assert left & right, (left, right)
print(f"Проверено пар кворумов: {len(quorums) ** 2}")Пересечение само по себе недостаточно: acceptor должен хранить обещание и принятое значение на стабильном носителе, если после рестарта считается тем же участником. Потеря этой памяти может нарушить предпосылки доказательства.
Представим A с ballot 10 и значением X, затем B с ballot 11 и значением Y. A успевает получить acceptance от двух из трёх узлов — X выбран. B начинает prepare(11) и собирает любое большинство. Оно обязательно включает хотя бы одного acceptor, принявшего X. Поэтому B увидит accepted(10, X) и обязан во второй фазе предложить X, хотя изначально хотел Y.
Если A получил только один acceptance, X ещё не выбран. B всё равно может унаследовать X, если этот ответ входит в его phase-1 quorum и имеет максимальный ballot. Это консервативное правило защищает случаи, когда proposer не знает, успело ли значение стать выбранным.
Чтобы реплицировать state machine, команды помещают в одинаковые позиции журнала. Все реплики применяют одну последовательность детерминированно. Нужны идентификаторы клиентов, дедупликация повторных запросов, снапшоты, восстановление журнала и безопасная смена конфигурации.
Paxos не определяет API сервиса, сериализацию, авторизацию и семантику повторов. Он также не решает, какая команда бизнес-правильно отменяет другую. Консенсус согласует порядок; смысл операций остаётся ответственностью приложения.
При чтении реализации найдите точное состояние acceptor: promised ballot, accepted ballot и accepted value. Проверьте, что оно переживает рестарт до отправки подтверждения. Затем найдите правило выбора значения после phase 1, размер кворума, генерацию уникального ballot и условия смены membership.
Для fault-injection теста задерживайте и дублируйте сообщения, останавливайте proposer после каждой записи, перезапускайте acceptor и создавайте конкурирующие ballot. Инвариант теста прост: в одном экземпляре не могут быть выбраны разные значения. Производительность измеряется отдельно после доказанной безопасности.
Paxos полезен не как набор названий сообщений, а как дисциплина сохранения знания между пересекающимися кворумами. Если реализация не показывает, где хранится это знание и почему новый раунд его наследует, одно упоминание Paxos не делает систему безопасной.
Самостоятельный редакционный разбор ЯдроКода по The Part-Time Parliament и Paxos Made Simple Leslie Lamport. Идеи атрибутированы первоисточникам, изложение и примеры созданы редакцией.
Пример кода и схемы сообщений создаются редакцией; оригинальные рисунки и текст публикаций Lamport не воспроизводятся.