Распределённые системы
Paxos
Цели урока
- Понимать задачу консенсуса и четыре свойства (validity, agreement, termination, fault tolerance)
- Разбираться в двух фазах Basic Paxos: Prepare/Promise и Accept/Accepted
- Знать проблему livelock и как Multi-Paxos её решает через leader election
- Ориентироваться в production-применениях: Chubby, Spanner, ZooKeeper, Raft
Предварительные знания
- Понимание distributed systems: частичные отказы, network partitions
- CAP-теорема и CP vs AP компромисс
- Базовое знание репликации (leader/follower)
Google Chubby координирует GFS, Bigtable и Spanner - тысячи серверов, петабайты данных - через алгоритм, придуманный как притча про греческий парламент и отвергнутый академическими журналами дважды.
- **Google Chubby (1998, Mike Burrows)** - Multi-Paxos в production за 3 года до публикации статьи Lamport. Используется для distributed locks GFS и Bigtable
- **Google Spanner** - Paxos groups на уровне каждого shard. Глобальная strong consistency через атомные часы + Paxos
- **Apache ZooKeeper** - Zab протокол (вариант Paxos) координирует Kafka, HBase, Hadoop
- **AWS DynamoDB** - Paxos для metadata consensus в routing layer при сотнях тысяч операций в секунду
- **etcd (Kubernetes)** - Raft (алгоритм-преемник Paxos) хранит всё состояние кластера Kubernetes
Притча о парламенте острова Паксос
Лэмпорт описал алгоритм как историю про законодательный парламент острова Паксос (Греция), где депутаты голосовали за законы даже если часть из них уходила на перерыв. Статью отвергали дважды - TOCS в 1990 и 1996. Опубликована в 1998 по прямой просьбе Butler Lampson (Turing Award 1992). К тому моменту Butler Lampson лично рассказывал коллегам о Paxos на конференциях - алгоритм распространялся устно. Turing Award Лэмпорту дали в 2013, в том числе за Paxos и за логические часы.
Проблема консенсуса
**1989 год. Лесли Лэмпорт пишет статью про парламент острова Паксос (Греция) - притчу о том, как голосуют депутаты когда часть из них спит или уходит.** Академия её отвергла. В 1998 снова отправил - снова отвергли. Опубликовал в 2001. К тому моменту алгоритм уже три года работал в production в Google Chubby - распределённом сервисе блокировок для Bigtable, GFS и Spanner. Лэмпорт получил Turing Award в 2013 - в том числе за Paxos.
Задача консенсуса: N узлов должны договориться об одном значении, причём при отказе части узлов. Четыре свойства, которые нужно выполнить одновременно:
| Свойство | Что означает |
|---|---|
| **Validity** | Выбранное значение - одно из предложенных, не выдуманное |
| **Agreement** | Все живые узлы выбирают одинаковое значение |
| **Termination** | Алгоритм завершается за конечное время |
| **Fault tolerance** | Работает при отказе меньшинства узлов (менее N/2) |
**Кворум:** Paxos требует большинства - N/2 + 1. При 5 узлах нужно 3 голоса. Это позволяет пережить отказ 2 узлов и гарантирует, что любые два кворума пересекаются хотя бы в одном узле - ключевое свойство алгоритма.
Почему это сложно: допустим, два узла одновременно предлагают разные значения. Третий узел получает оба предложения в разном порядке (сеть недетерминирована). Нужен механизм, который гарантирует - в конце все видят одно и то же значение, даже если несколько узлов отвалились посередине.
Консенсус - просто голосование: кто больше проголосовал, тот и победил
Консенсус требует сохранения уже принятых решений между раундами, иначе два разных значения могут быть 'выбраны' в разных раундах
В простом голосовании нет памяти. В Paxos acceptor обещает (PROMISE) не принимать предложения с меньшим номером - и сообщает о последнем принятом значении. Без этого механизма второй proposer мог бы 'победить' с другим значением в следующем раунде.
Почему Paxos требует кворума N/2 + 1, а не просто большинства (например, 2 из 5)?
Протокол Basic Paxos
В Paxos три роли: **Proposer** (предлагает значения), **Acceptor** (голосует), **Learner** (узнаёт результат). Один узел может играть все три роли. Алгоритм состоит из двух фаз.
Phase 1: Prepare / Promise
Phase 2: Accept / Accepted
Пример: P1 предлагает X, P2 опаздывает
P1 отправляет PREPARE(1) - все три acceptor отвечают PROMISE(1, null). P1 отправляет ACCEPT(1, "X") на A1 и A2 - оба отвечают ACCEPTED. Кворум собран, "X" выбрано. P2 опаздывает с PREPARE(2) - A1 и A2 отвечают PROMISE(2, "X", 1). P2 видит уже принятое "X" и ОБЯЗАН предложить именно его. Итог: все узлы согласились на "X" даже при конкуренции двух proposer'ов.
**Ключевой инвариант:** если proposer видит в PROMISE уже принятое значение - он обязан его использовать. Это гарантирует agreement: два кворума пересекаются в минимум одном узле, который сообщит о принятом значении.
Proposer получил PROMISE от 3 из 5 acceptors. Один из PROMISE содержит принятое значение 'Y' (accepted_N=5). Что должен сделать proposer?
Multi-Paxos и livelock
Basic Paxos решает одиночный консенсус - договориться об одном значении. Реальные системы (реплицированные логи, distributed databases) требуют консенсуса для последовательности команд. Плюс у Basic Paxos есть теоретическая проблема - livelock.
Livelock: два proposer'а блокируют друг друга
Решение - **Multi-Paxos**: выбрать одного стабильного лидера. Лидер - единственный proposer, поэтому конкуренции нет. После первого успешного раунда Paxos (Phase 1) лидер может пропускать Phase 1 для всех последующих значений.
| Режим | Round-trips на значение | 100 значений |
|---|---|---|
| Basic Paxos | 2 RTT (Prepare + Accept) | 200 RTT |
| Multi-Paxos (установленный лидер) | 1 RTT (только Accept) | 2 + 99 = 101 RTT |
| Multi-Paxos (смена лидера) | 2 RTT на первое значение | пересчитывается с нового лидера |
**FLP Impossibility (Fischer, Lynch, Paterson, 1985):** в асинхронной системе с возможным отказом даже одного узла невозможно гарантировать консенсус за конечное время. Paxos обходит это не гарантируя termination в худшем случае (livelock теоретически возможен) - но на практике randomized leader election и timeouts решают проблему.
Livelock в Paxos - критическая проблема, из-за которой алгоритм непригоден на практике
Livelock теоретически возможен при одновременных competing proposers, но на практике решается выбором одного лидера
Multi-Paxos с leader election используется в Google Chubby и Spanner с 1998 года. При стабильном лидере livelock невозможен. Leader failure обрабатывается через timeout + новые выборы - это занимает секунды, а не бесконечность.
Почему Multi-Paxos при установленном лидере требует только 1 RTT вместо 2?
Paxos на практике
Paxos редко используется в виде 'vanilla' алгоритма - каждая система адаптирует его под свои нужды. Google Chubby (2006) стал первым широко описанным production-применением и вдохновил ZooKeeper.
| Система | Вариант Paxos | Применение |
|---|---|---|
| Google Chubby | Multi-Paxos | Distributed lock service - координация GFS, Bigtable, Spanner |
| Google Spanner | Paxos groups | Per-shard consensus для globally consistent DB |
| Apache ZooKeeper | Zab (Zookeeper Atomic Broadcast) | Похож на Paxos, оптимизирован для leader-driven replication |
| AWS DynamoDB | Paxos | Metadata consensus для routing layer |
| CockroachDB | Raft | Выбрали Raft как более понятный для реализации Paxos-подобный алгоритм |
Paxos vs Raft: выбор на практике
- Paxos — Теоретически оптимален, гибкий (много вариантов оптимизаций), проверен с 1989. Минус: сложен для понимания и реализации, recovery при leader failure требует аккуратной инженерии.
- Raft (2014) — Спроектирован специально для понятности. Strong leader упрощает логику, много качественных open-source реализаций (etcd, TiKV). Минус: менее гибкий, leader может быть bottleneck.
**Практический совет:** для новых проектов - Raft (etcd, HashiCorp Raft library, TiKV). Paxos выбирают когда нужна специфическая оптимизация или уже есть expertise в команде. Google использует Paxos потому что начали в 1998 году, до появления Raft.
Apache ZooKeeper использует Zab вместо vanilla Paxos. В чём главное отличие Zab?
Вопросы для размышления
- Raft спроектирован специально для понятности и обогнал Paxos по популярности в новых проектах. Что это говорит о роли инженерной читаемости алгоритма - насколько теоретическая оптимальность важна по сравнению с простотой реализации и отладки?
Связанные уроки
- ds-03-consensus — Paxos is the canonical consensus algorithm
- ds-06-leader-election — Paxos includes leader-like proposer selection
- dist-07-2pc — 2PC is a special-case precursor to Paxos
- dist-09-raft — Raft is a more understandable alternative to Paxos
- dist-10-byzantine — BFT Paxos variants handle Byzantine failures
- alg-12-bfs