CFT-консенсус: Paxos и Raft

Начнём консенсус с лёгкого мира: узлы честны и умеют только падать, не врать. Это crash fault tolerance, и его решали задолго до блокчейна, в распределённых базах. Разберём репликацию состояния как машину, кворум большинства, и протокол Raft, который сделал консенсус понятным. Это фундамент: византийский консенсус из следующего урока надстраивается ровно над этими идеями.

Идея

Цель консенсуса звучит обманчиво просто: несколько узлов должны согласиться об одном значении, даже если часть из них упадёт. На практике это значит согласиться о последовательности команд, и тут появляется главная модель блока.

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

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

Кворум большинства

Как согласовать запись, не доверившись одному узлу? Через голосование, но не единогласное (один мёртвый узел заморозил бы всё), а большинством. Кворум большинства это ⌊N/2⌋+1 узлов.

Магия в пересечении. Два большинства в кластере из N узлов обязаны иметь хотя бы один общий узел: их суммарный размер больше N, в непересекающиеся они не помещаются. Этот общий узел и есть страж согласованности: он не одобрит два противоречащих решения, а значит две половины кластера не примут разное. Отсюда правило живучести: чтобы пережить f отказов, нужно N ≥ 2f + 1 узлов (трое переживают одного павшего, пятеро двоих).

Покрути кластер: меняй размер и число отказов и смотри, когда кворум есть, а когда система честно встаёт, лишь бы не расколоться.

узлов в кластере N: 5отказало f: 1

✕

●

●

●

●

кворум большинства: ⌊5/2⌋+1 = 3живых: 4переживает отказов: 2

Кворум есть: 4 живых из нужных 3. Кластер работает и не расколется, ведь два непересекающихся большинства в 5 узлах невозможны.

Правило N ≥ 2f + 1: чтобы пережить f отказов, нужно минимум 2f+1 узлов. Любые два большинства обязаны пересекаться хотя бы в одном узле, и этот общий узел не даёт двум половинам принять противоречащие решения. Поэтому кластеры делают нечётными: 4 узла переживают столько же отказов, сколько 3, но требуют большего кворума.

Кворум руками выглядит так:

/// Кворум большинства для кластера из n узлов.
fn quorum(n: usize) -> usize {
    n / 2 + 1
}

/// Голос принят, если за него хотя бы кворум.
fn decided(votes: usize, n: usize) -> bool {
    votes >= quorum(n)
}

fn main() {
    assert_eq!(quorum(5), 3); // в кластере из 5 нужно 3 голоса
    assert_eq!(quorum(4), 3); // из 4 тоже 3: чётность не помогает
    assert!(decided(3, 5)); // 3 из 5 это решение
    assert!(!decided(2, 5)); // 2 из 5 нет
    // Пять узлов переживают 2 отказа: 3 живых всё ещё дают кворум.
    let n = 5;
    let alive = n - 2;
    assert!(alive >= quorum(n));
}

Paxos: как принимается одно значение

Классический протокол консенсуса это Paxos Лесли Лэмпорта. Он решает минимальную задачу: узлы должны согласиться об одном значении, даже если предложений несколько и часть узлов падает. Роли три: proposer предлагает значение, acceptor голосует, learner узнаёт результат (на практике один узел совмещает все три).

Работает это в две фазы, и вся соль в номерах раундов. Каждый proposer выбирает свой уникальный возрастающий номер n (например, из счётчика, склеенного с id узла) и идёт по шагам:

1. Prepare. Proposer шлёт acceptor-ам prepare(n): собираюсь предлагать в раунде n.
2. Promise. Acceptor, увидевший n больше всех, что видел раньше, отвечает обещанием: с этого момента он игнорирует любые предложения с номерами меньше n. И ключевая деталь: если он уже принял какое-то значение в прошлом раунде, он сообщает его в ответе вместе с номером того раунда.
3. Accept. Собрав обещания от кворума большинства, proposer шлёт accept(n, v). Но v он выбирает не как хочет: если хоть один acceptor вернул уже принятое значение, proposer обязан взять значение из самого свежего такого ответа. Своё значение он предлагает, только если никто ничего не принимал.
4. Accepted. Acceptor принимает accept(n, v), если не давал обещания раунду старше n. Как только кворум acceptor-ов принял одно (n, v), значение выбрано навсегда.

Правило «бери уже принятое значение» и есть сердце безопасности. Если значение v набрало кворум, любой будущий proposer на фазе prepare соберёт обещания от большинства, а любое большинство пересекается с тем кворумом. Значит хотя бы один acceptor вернёт ему v, и proposer будет вынужден продвигать v дальше, а не своё. Переиграть выбранное значение невозможно, можно только повторить его с новым номером.

За это Paxos платит живостью: два proposer-а могут бесконечно перебивать друг друга растущими номерами (первый успел с prepare, второй перебил большим n, первый перебил ещё большим, и так далее), и решение не примется никогда. Это FLP из прошлого урока во плоти: safety железная, liveness не гарантирована. На практике лечат выбором одного координатора, и это уже полшага к лидеру Raft.