Согласие без центра: как решать вместе, не доверяя никому на слово

Почему координатор не решает проблему

Координатор удобен, пока система живёт в одном процессе на одной машине. Как только участники распределены, у него появляются три свойства, которые в продакшене обходятся дорого: он становится узким местом по пропускной способности, единой точкой отказа и единственным, кому все обязаны верить.

Третье свойство обычно недооценивают. Речь не о злом умысле. Достаточно программной ошибки, устаревшего состояния или частичной потери связи, чтобы координатор начал раздавать решения, которые противоречат тому, что видят остальные. И система их примет, потому что доверие встроено в архитектуру.

Что значит византийская модель отказов

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

Для сети автономных агентов такая постановка задачи точнее всего. Участник может работать на чужой машине и на другой версии кода, его часы могут разойтись с остальными, его могут взломать. Протокол должен оставаться корректным именно в таких условиях.

Как устроен один цикл согласия

1. Лидер раунда рассылает подписанное предложение: какое изменение общего состояния он предлагает зафиксировать.
2. Каждая реплика сама проверяет предложение (корректность перехода состояния, номер последовательности, подпись) и отвечает собственным подписанным голосом.
3. Лидер собирает кворум голосов от разных участников и рассылает сертификат фиксации.
4. Каждая реплика проверяет все подписи в сертификате, записывает его в журнал и только после этого применяет изменение.

Арифметика устойчивости

Для комитета из n участников число реплик, которые могут вести себя произвольно, и размер кворума в классической схеме считаются так:

f = floor((n - 1) / 3)
quorum = 2f + 1

На практике комитет из четырёх переживает одного отказавшего или злонамеренного участника, если остальные трое могут общаться. Из формулы следует и неприятная правда: устойчивость покупается числом участников. Чтобы пережить двоих, нужно семеро. Согласие стоит дорого, поэтому применять его стоит выборочно.

Кворум 2f + 1 верен, когда участников ровно 3f + 1: четыре, семь, десять. При другом размере комитета два кворума уже не обязаны пересекаться в честной реплике, и кворум нужно считать иначе. В текущей версии открытого рантайма кворум считается как 2f + 1 при любом размере комитета, и реплика не отказывается голосовать за второе, другое предложение с тем же номером. Поэтому мы называем его протоколом согласия в стиле PBFT для фиксированного набора узлов и гарантий отказоустойчивости ему не приписываем.

Что протокол обязан отвергать

• повторный голос одного участника в одном сертификате, иначе кворум набирается одним активным узлом;
• голоса тех, кто не входит в комитет;
• изменённые команды: подпись должна покрывать содержимое, а не только факт отправки;
• неверный номер последовательности или раунда, чтобы не применить устаревшее решение;
• подделанную подпись и повтор ранее перехваченного сообщения.

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

Смена лидера и догоняющая синхронизация

Лидер может исчезнуть или замолчать. Тогда участники голосуют за смену раунда, и лидерство переходит к следующему. Это штатная часть протокола, а не аварийная процедура: система должна продолжать работу без вмешательства человека.

Реплика, которая была недоступна, догоняет остальных по сертификатам. Она запрашивает все зафиксированные решения после своего последнего номера и применяет их, проверяя подписи. Верить тому, кто прислал историю, ей не нужно: каждый сертификат проверяется сам по себе.

Где это нужно агентной системе

Не везде. Согласие оправдано там, где решение общее и необратимое:

• изменение общего состояния, которое видят все участники;
• допуск нового участника в доверенный контур;
• операции с ресурсами, где двойная трата недопустима;
• структурные операции: объединение группы участников в одного и обратное разворачивание.

Всё остальное решают сами участники или пары по договорённости, согласие всей группы для этого не нужно. Если проводить через комитет каждое действие, живая система станет медленной: цену согласия придётся платить за каждое решение, а польза от него есть только там, где расхождение действительно опасно.