Розподілений консенсус: Paxos і Raft простими словами

1. Проблема консенсусу

Формально консенсус вимагає, щоб набір процесів, кожен з яких пропонує значення, зрештою всі узгодили рівно одне з запропонованих значень. Мають виконуватися три властивості:

Узгодженість: жодні два коректні процеси не вирішують різні значення.
Валідність: вирішене значення було запропоноване якимось процесом (жодне значення не береться зі стелі).
Завершуваність: кожен коректний процес зрештою ухвалює рішення.

На практиці ми використовуємо реплікаційні скінченні автомати: кожен сервер зберігає журнал команд лише з дозаписом. Консенсус гарантує, що всі сервери виконують ті самі команди в тому самому порядку. Це є основою баз даних на кшталт CockroachDB, etcd (Kubernetes) і TiKV.

Чому це складно? Процеси падають будь-якої миті. Повідомлення затримуються, переупорядковуються або губляться. Ви не можете відрізнити мертву машину від дуже повільної (асинхронна модель мережі). Ви дізнаєтеся, що сервер упав, лише коли він перестає відповідати — а це потребує часу.

2. FLP і CAP — результати про неможливість

Неможливість FLP (1985)

Фішер, Лінч і Патерсон довели, що в суто асинхронній розподіленій системі навіть з одним процесом, здатним упасти, жоден детермінований алгоритм консенсусу не може завжди завершуватися — у поганих випадках він може працювати вічно. На практиці це означає, що нам потрібні тайм-аути та рандомізація (або припущення про синхронність), щоб просуватися вперед.

Теорема CAP

Теорема CAP Брюера стверджує, що розподілена система може гарантувати щонайбільше дві з трьох властивостей:

Узгодженість (C)

Кожне читання повертає найновіший запис або помилку. Усі вузли бачать ті самі дані одночасно.

Доступність (A)

Кожен запит отримує відповідь (не обов'язково з найновішими даними). Система завжди працює.

Стійкість до розділення (P)

Система продовжує працювати попри довільні розділення мережі між вузлами.

На практиці

Мережі справді розділяються, тож P є обов'язковою. Системи обирають: CP (сильна узгодженість, може відхиляти запити) або AP (зрештою-узгодженість, завжди відповідає).

Raft і Paxos — це системи CP. Під час розділення сторона меншості відмовляє в запитах, щоб зберегти узгодженість.

3. Paxos: класичний алгоритм

Paxos описав Лемпорт у 1989 році (опубліковано 1998). Він працює у дві фази на кожен раунд консенсусу (екземпляр):

Фаза 1 — Prepare

Пропонувач обирає номер бюлетеня n (вищий за будь-який, що він бачив) і розсилає Prepare(n) більшості акцепторів. Акцептори відповідають:

Обіцянка: «Я не прийматиму бюлетені < n».
Найвище прийняте значення (якщо є): пропонувач мусить зберегти його.

Фаза 2 — Accept

Пропонувач обирає значення (своє або найвище раніше прийняте значення з фази 1) і надсилає Accept(n, v) акцепторам. Акцептори приймають його, якщо не пообіцяли вищий бюлетень. Щойно більшість приймає, значення вважається обраним.

Інваріант безпеки Paxos Якщо значення v обране на бюлетені n, то будь-яке значення, обране на бюлетені n' > n, також має бути v. Начерк доведення: перетини більшостей (кворумів) гарантують, що принаймні один акцептор у новому кворумі бачив старе прийняте значення.

Multi-Paxos: запускати один екземпляр Paxos на кожен запис журналу дорого. Multi-Paxos обирає стабільного лідера, який пропускає фазу 1 для наступних записів, зводячи звичайний випадок до одного оберту туди-назад (лише фаза 2).

4. Raft: зрозумілість понад усе

Raft розробили Онгаро та Аустергаут (2014) з явною метою: бути простішим для розуміння, ніж Paxos. Ключові проєктні рішення:

Сильний лідер: усі записи журналу проходять через єдиного лідера.
Рандомізовані тайм-аути: прості, імовірнісні вибори лідера.
Зміни складу: спільний консенсус для безпечної переконфігурації кластера.
Узгодження журналів: якщо два журнали мають однаковий запис за тим самим індексом, усі попередні записи ідентичні.

Raft розкладає консенсус на три незалежні підпроблеми: вибори лідера, реплікація журналу та безпека.

5. Вибори лідера

Кожен сервер перебуває в одному з трьох станів: Послідовник, Кандидат або Лідер. Час поділено на терміни (монотонно зростаючі цілі числа).

Послідовники чекають на серцебиття від лідера. Кожен послідовник має рандомізований тайм-аут виборів (150–300 мс).
Якщо тайм-аут спливає без серцебиття, послідовник стає Кандидатом і починає вибори на термін T+1.
Кандидат голосує за себе й надсилає RequestVote(term, lastLogIndex, lastLogTerm) усім одноранговим вузлам.
Сервер віддає свій голос, якщо: він ще не голосував у цьому терміні І журнал кандидата принаймні настільки ж актуальний, як його власний.
Кандидат, який отримує більшість голосів, стає лідером. Він негайно надсилає серцебиття, щоб зупинити інші вибори.

Розщеплення голосів: якщо два кандидати стартують одночасно, жоден може не набрати більшості. Обидва досягають тайм-ауту, збільшують термін і пробують знову. Рандомізовані тайм-аути роблять повторні розщеплення рідкісними — на практиці вибори завершуються за один раунд.

Умова надання голосу grant \leftarrow candidate.term \geq self.currentTerm AND self.votedFor \in {null, candidate.id} AND журнал candidate принаймні настільки ж актуальний, як self.log «Принаймні настільки ж актуальний»: candidate.lastLogTerm > self.lastLogTerm АБО (рівний термін І candidate.lastLogIndex \geq self.lastLogIndex)

6. Реплікація журналу

Клієнти надсилають усі команди лідеру. Лідер дописує команду до свого журналу (з поточним терміном), потім реплікує її паралельно всім послідовникам через RPC AppendEntries.

Індекс	Термін	Команда	Статус
1	1	SET x=5	Зафіксовано
2	1	SET y=3	Зафіксовано
3	2	DEL x	Зафіксовано
4	3	SET z=9	Очікує (ще немає більшості)

Запис вважається зафіксованим, щойно лідер реплікував його на більшість серверів. Тоді лідер застосовує команду до свого скінченного автомата й відповідає клієнту. Він повідомляє послідовників про індекс фіксації у наступних викликах AppendEntries.

Властивість узгодження журналів

Коли лідер надсилає AppendEntries(prevLogIndex, prevLogTerm, entries), послідовник перевіряє, що його запис за prevLogIndex має термін prevLogTerm. Якщо ні, він відхиляє його, і лідер повторює спробу з раніших індексів. Ця перевірка узгодженості гарантує, що журнали ніколи не розходяться непомітно.

7. Безпека та живучість

Безпека: жодних двох зафіксованих значень за тим самим індексом

Raft гарантує, що якщо запис за індексом i зафіксовано в терміні t, то інший запис за індексом i ніколи не буде зафіксовано в жодному терміні. Це випливає з того, що:

Фіксація потребує підтвердження від більшості.
Будь-який майбутній лідер мусив отримати голоси від більшості, тож принаймні один із тих, хто голосував, має зафіксований запис.
Обмеження на вибори (голосувати лише за актуальних кандидатів) гарантує, що журнал нового лідера містить усі зафіксовані записи.

Живучість: просування за часткових збоїв

Raft витримує до ⌊(n-1)/2⌋ збоїв серверів у кластері з n серверів (кластер із 5 вузлів переживає 2 збої). Доки більшість жива й підключена, вибори завершуються, а реплікація триває.

Візантійські збої: Raft і Paxos припускають збої типу crash-stop — сервери або працюють коректно, або зупиняються. Вони не обробляють візантійські збої (зловмисні/пошкоджені сервери). Для цього потрібні алгоритми BFT (PBFT, HotStuff), які вимагають 3f+1 реплік, щоб витримати f візантійських збоїв — значно дорожче.

8. Використання на практиці

Алгоритми консенсусу живлять шар координації багатьох критичних систем:

etcd (Raft) — сховище конфігурації для Kubernetes; кожне планування пода, запис виявлення сервісів і секрет проходять через нього.
CockroachDB, TiKV (Raft) — розподілений SQL; кожен діапазон (шард на 64 МіБ) має власну Raft-групу.
Chubby, Zookeeper (Paxos / ZAB) — розподілені служби блокувань Google/Yahoo; використовуються HDFS, HBase.
Apache Kafka — режим KRaft (Raft) замінює ZooKeeper для керування метаданими з 2022 року.
Consul (Raft) — консенсус сервісної сітки та перевірка справності.

Вибір розміру кластера — це компроміс: 3 вузли (витримка 1 збою) для бюджетних розгортань; 5 вузлів (2 збої) для високої доступності; 7+ вузлів дуже рідко (спадна віддача за затримкою запису проти відмовостійкості).

Показники продуктивності: добре налаштований Raft-кластер із 5 вузлів у локальній мережі досягає ~50 000 записів/с із медіанною затримкою <1 мс. Розгортання між дата-центрами додають RTT (30–150 мс) безпосередньо до затримки фіксації — це неминуче; це ціна довговічності між доменами відмов.