paxos.js·5 scenarios
Paxos consensus algorithm — concept page for /concepts/paxos. Visualizes proposer/acceptor/learner roles, two-phase prepare/accept protocol, majority quorum, Multi-Paxos optimization with stable leader, and the duelling-proposers livelock problem. 5 acceptors + 2 proposers + 2 learners. Five scenarios: basic-happy (single decree 2 RTT), conflict-prior-wins (safety preservation), livelock-duelling-proposers (with showError + flashError + Multi-Paxos fix), multi-paxos-stable-leader (1 RTT per slot), greek-mess-why-hard (Paxos Made Live war stories). Two ADRs: full algorithm description, and Paxos vs Raft comparison.
Paxos — первый практический consensus algorithm (Lamport 1990). На нём построены Google Chubby, Spanner, Megastore, Cassandra LWT. Понимать его обязательно по трём причинам: (1) все современные алгоритмы консенсуса (Raft, Zab, Viewstamped Replication) — это переупаковки Paxos с лучшей презентацией; (2) самые критичные production deployments в мире до сих пор работают на нём; (3) это theoretical foundation для всего, что вообще называется «consensus».
Базовая задача: N узлов должны договориться об одном значении (либо последовательности значений — это Multi-Paxos), несмотря на падения узлов, потерянные сообщения и переупорядочивание. Без single point of failure. Без блокировки навсегда при сбое любого меньшинства.
Контекст: см. [CONCEPT]consensus-overview для обзора всех алгоритмов, [CONCEPT]raft — современная альтернатива с лучшей понятностью, [CONCEPT]zab — близкий кузен в ZooKeeper.
«Никто не владеет системой. Любая нода может быть Proposer. Acceptors голосуют двухфазно: prepare, потом accept. Consensus достигается через монотонные proposal numbers и обещания не голосовать за более старые номера.»
Три роли:
В практике один процесс играет несколько ролей. В Multi-Paxos обычно есть distinguished leader (как в Raft).
Главное прозрение: proposal numbers globally unique и monotonic. Обычно это пара (round, proposer_id). Это одновременно ID, приоритет и причина, по которой «старые» сообщения не могут сломать систему. Если acceptor пообещал не голосовать за номера < n, он не нарушит обещание, даже если задержанный пакет с n-1 прилетит через 10 секунд.
Два phase:
Правило safety, которое делает всё это работающим: если в Phase 1 proposer узнал, что кто-то уже принял prior value — он ОБЯЗАН в Phase 2 предложить именно его (с самым высоким prior n). Не своё. Иначе уже chosen value может потеряться.
5 acceptors (a1–a5, quorum = 3/5), 2 proposers (p1, p2), 2 learners (l1, l2). Каждый proposer связан со всеми acceptors физическими TCP-edges — это каналы для prepare и accept (и обратных ответов через reverse animation). Acceptors связаны с learners для broadcast'а chosen values.
Классический Basic Paxos в один декрет. P1 шлёт PREPARE(n=10) всем пяти acceptors, получает promise от трёх (quorum), видит что никто не accept'ил prior value — свободен использовать «apple». Шлёт ACCEPT(10, "apple") майоритету, получает ack от трёх — value chosen, learners получают уведомление. Латентность: 2 RTT (Phase 1 + Phase 2).
Ключевой сценарий safety. P1 успевает дозвониться только до двух acceptors (a3 unreachable), отправляет ACCEPT только a1, тот persists ("apple", n=1), а P1 умирает не получив majority. Через какое-то время P2 хочет propose "banana" с n=2. PREPARE(2) проходит к майоритету; a1 в promise возвращает prior=("apple", 1). По правилу safety P2 обязан забыть про «banana» и предложить "apple" в Phase 2. Финальное chosen value = "apple". Даже несмотря на то, что P1 не дождался majority acks, его частично принятое значение «защитилось» через promise от a1.
Почему Basic Paxos нельзя использовать в production без leader. P1 шлёт PREPARE(1), все обещают. До того как P1 успевает ACCEPT, прилетает PREPARE(2) от P2. Acceptors теперь обещают n≥2 — ACCEPT от P1 с n=1 отвергнут. P1 retry с n=3 — теперь ACCEPT от P2 с n=2 отвергнут. P2 retry с n=4. И так бесконечно. Никто не достигает Phase 2, прогресса нет. Lamport показал что это теоретически возможно навсегда (FLP impossibility).
Fix 1: randomized exponential backoff между retries. Fix 2 (production): Multi-Paxos с stable distinguished leader. Fix 3 (architectural): именно поэтому в Raft leader mandatory, не optional.
Production-режим. P1 elected leader для term, шлёт PREPARE(100) один раз — он distinct и для всех будущих slot'ов одновременно. Получает majority promise. После этого для каждой клиентской команды нужен только Phase 2: ACCEPT(slot=1, "set x=5") к майоритету, majority ack — chosen. Slot=2, slot=3 — все идут на 1 RTT. Phase 1 нужен снова только если leader упал и проводится новая «election» с term bump.
Латентность amortized = 1 RTT per command. Это та же стоимость, что и у Raft (потому что Raft — это и есть упорядоченное переоткрытие Multi-Paxos).
Лекция о том, почему Paxos исторически считают сложным. Lamport написал оригинал в 1990 в виде истории о древнегреческом парламенте — paper отклонили, никто не понял. В 2001 переписал как «Paxos Made Simple» — стало понятнее, но всё равно реализовать с нуля корректно почти невозможно. В 2007 Chandra et al. (Google) опубликовали «Paxos Made Live» — описание реальной реализации в Chubby с цитатой: «significant gaps between the description of the Paxos algorithm and the needs of a real-world system». Их инженерам понадобились месяцы PhD-уровня работы на: disk corruption recovery, master leases, joint consensus для membership changes, snapshotting, batching, pipelining, out-of-order ack handling, Jepsen-style fault injection testing. Именно эта статья мотивировала Ousterhout создать Raft как «consensus algorithm designed for understandability».
Вместо одной таблицы — два разреза.
ADR-001: Paxos vs не-консенсус (eventual consistency).
ADR-002: Paxos vs Raft.
| Аспект | Paxos | Raft |
|---|---|---|
| Понятность | Низкая (нужен PhD) | Высокая (стандарт для teaching) |
| Гибкость | Multi / Fast / Generalized / EPaxos | Один canonical protocol |
| Leadership | Optional (но обычно есть) | Mandatory |
| Bug-free implementations | Меньше | Больше |
| Production maturity | Decades (Chubby с 2006) | Decade+ (etcd с 2014) |
| Variants для optimization | Богатый choice | В основном vanilla |
| Учебники / визуализации | Скудны | thesecretlivesofdata.com и пр. |
Формально Paxos и Raft эквивалентны по safety/liveness. На практике Raft вытеснил Paxos почти везде. Paxos остаётся там, где есть expertise (Google) и нужны специфические optimization (per-shard groups в Spanner, leaderless EPaxos для geo-distributed). Все остальные пишут Raft.
ADR-003: Basic vs Multi-Paxos в production.
IF NOT EXISTS, conditional updates). 4 RTTs на одно решение — поэтому в разы медленнее обычных writes. Использовать только когда linearizability реально нужна.