Алгоритми консенсусу

1) Що таке консенсус і навіщо він потрібен

Консенсус - узгодження одного і того ж значення/послідовності значень між декількома вузлами при збоях і затримках. Традиційно вирішується задача реплікації стану (State Machine Replication, SMR): є детермінована машина станів і загальний порядок операцій.

• Консенсус (SMR): єдиний тотальний порядок команд → лінійзоване сховище/реєстр, метадані кластера, транзакційні координатори.
• Кворумні операції без тотального порядку (Dynamo-подібні, CRDT): допускають дивергенцію і подальше злиття; не замінюють консенсус там, де потрібна глобальна серіалізація.

2) Модель часу і відмов

2. 1 Модель часу

Асинхронна мережа: затримки необмежені; теорема FLP ⇒ неможливо гарантувати і safety, і liveness без додаткових припущень.
Частково-синхронна (часто на практиці): після невідомого T система «поводиться» синхронно - більшість алгоритмів (Raft, Paxos) покладаються саме на це.
Синхронна: жорсткі тайм-ліміти на канали (рідко в проді, крім спеціальних мереж/ПТП).

2. 2 Модель відмов

Crash-fault tolerant (CFT): вузли можуть падати/виснути, але не поводяться зловмисно.
Byzantine-fault tolerant (BFT): вузли можуть брехати/підробляти повідомлення. Потрібно 3f + 1 вузлів для толерантності до f візантійським.

3) Властивості консенсусу

Safety (безпека): несуперечливість (два коректних вузли не вирішать різні значення).
Liveness (живучість): якщо мережа «здорова», рішення досягається.
Лінеаризованість (лінійність): операції «бачаться» як атомарні в єдиному порядку.
Довговічність: прийняті рішення не відкочуються (захист журналом/кворумом).

4) Кворуми, більшість і перетину

У CFT-світі класика: кворум> N/2. Записи і вибори лідера використовують перетин кворумів, тому дві «валідні» операції не конфліктують.
У BFT-світі: кворуми 2f + 1 з 3f + 1 забезпечують перетин мінімум в f + 1 чесних вузлів.

Правило перетинів: будь-який два кворуми повинні мати ≥1 загальний чесний вузол (CFT) або ≥f+1 (BFT).

5) Реплікація стану (журнал + застосування)

• Снапшоти (зріз стану, після якого ранні записи можна видалити/скомпактувати).
• Компакцію журналу і лог-тріїм.
• Перевірки детермінізму (однакова версія коду/конфігів).

6) Лідерські та нелідерські схеми

Лідерські (Raft, Multi-Paxos, ZAB): один лідер серіалізує записи → простіше ментально і операційно, краще latency на стабільному лідері.
Безлідерні/мультилідерні (EPaxos, Caesar): більше паралелізму і толерантність до лідера, але складніше реалізація і конфлікт-рішення; прибуток видно при малих конфліктностях команд.

7) Класичні CFT-алгоритми

7. 1 Paxos/Multi-Paxos (і практики)

Ідея: два фази (prepare/propose), обіцянки акцепторів, мажоритарні кворуми. Multi-Paxos залишає «стабільного лідера» і перетворює операції в однораундові (для нових записів) після «прогріву».

• Гнучка, але складна для реалізації модель.
• Реконфігурації через особливі записи (joint consensus).
• На практиці - бібліотеки/рушії (Chubby/Spanner-покоління).

7. 2 Raft

Декомпозований для навчання: вибір лідера, реплікація логів, ре-конфігурація.

Election: випадкові таймаути, голосування по термах; один лідер на термін.
AppendEntries: лідер стримить записи, стежить за збігом префікса (індекс/терм), коміт по мажоритарній фіксації.
Read-path: lease-reads (при сильному лідері) або read-index для лінійних читань.
Reconfig: «спільна конфігурація» (joint) - вузли голосують у двох кластерах до переходу.

Плюси: простіше для розробки/дебага, сильні інваріанти порядку. Мінуси: лідер - точка тиску.

7. 3 ZAB (ZooKeeper Atomic Broadcast) / Viewstamped Replication (VRR)

ZAB: лідер широковещает транзакції, фаза відновлення, zxid (епоха + індекс).
VRR: «види» (views) з первинним реплікантом, схожий на Multi-Paxos за духом.

8) Нелідерські/мультилідерні CFT

8. 1 EPaxos

Немає постійного лідера: будь-який вузол може ініціювати команду.
Конфліктні команди отримують частковий порядок; безконфліктні - коммітяться в 1-2 RTT локально.
Виграш в георозподілі при низькій конфліктності, але складні коди залежностей/графів.

8. 2 Caesar, Mencius

Варіації, що оптимізують затримки/балансування і роботу в WAN.

9) BFT-алгоритми та PoS-сімейство

9. 1 PBFT (Practical BFT)

Три фази (pre-prepare/prepare/commit), вимагає 3f + 1 вузлів.
Низька латентність на локальних мережах, доріг багатошаговістю і O (N ²) повідомленнями.

9. 2 Tendermint (BFT-PoS стиль)

Раунди з proposal і двома голосуваннями (prevote/precommit).
Детермінований валідатор-запропонник, тайм-аути, часткова синхронність.
Хороший для permissioned/PoS-мереж з десятками/сотнями валідаторів.

9. 3 HotStuff (і похідні)

Уніфікована трифазна схема в «пакети» з кворумними сертифікатами (QC).
Лінійна складність комунікацій, підтримка пакетування і паралельної пайплайнізації, зручна для реалізацій в блокчейнах (наприклад, Diem/Move-екосистема).
З пороговими підписами (threshold signatures) зменшується трафік.

9. 4 PoW/накопичувальний консенсус (коротко)

Не BFT в строгому сенсі, а ймовірнісна конвергенція (ланцюжок з найбільшою роботою). Переваги: простота/відкритість; недоліки: енергія, ~ секунд-хвилини до фінальності.

10) Читання: лінійні, послідовні та кешовані

Лінійні читання: лідер з активним lease або через read-index (Raft) → підтвердження через кворум.
Послідовні: можна читати з будь-якого вузла, але без гарантій свіжості.
Follower reads: допустимі при слабких вимогах; для кешів - ok.

11) Ре-конфігурація (зміна складу кластера)

Вимагає двох конфігурацій, що перекриваються (joint consensus): будь-які коміти проходять кворуми обох конфігурацій → без «дірок».
Додавайте/видаляйте по одному, дотримуйтесь розміру кворуму.
Перенесення лідерства (leadership transfer) знижує паузи.

12) Продуктивність і тюнінг

12. 1 Затримки

Лідерські алгоритми: 1 RTT на запис (при стабільному лідері) + реплікація.
Георозподіл: WAN RTT домінує → використовуйте локальні регіони + крос-регіональну реplikацію або EPaxos/HotStuff-підходи.

12. 2 Пропускна

Batching (групування команд), паралельні AppendEntries, пейдж-кеш журналу, паралельне застосування (коли операції комутують).
Диски: NVMe/Журнал на окремому пристрої,'O _ DIRECT '/AIO, великий'fsync'-інтервал з обмеженнями SLA (компроміс durability/latency).

12. 3 Хвости p99

Уникайте гарячих вузлів (лідер постійно один): періодична ротація або read-offload на фоловерів.
Контролюйте GC-паузи (JVM/Go), піни CPU, NUMA.

13) Географія і топології

1 регіон, 3 зони: класичний CFT-кластер (N = 3/5).
2 регіони: уникайте - не виходить надійний кворум при поділі 1-1.
3 + регіонів: лідер в «середині» або безлідерні алгоритми; можливі регіональні проксі/локальні фронти з асинхронним журналом.

14) Практичні питання експлуатації

14. 1 Снапшоти і відновлення

Поріг за розміром журналу/кількістю операцій.
Передача снапшота новим вузлам; перевірка контрольних сум.

14. 2 Моніторинг

Лідерство: хто лідер, скільки термінів (term/epoch) змінилося.
Лаги: `append_latency`, `commit_index - applied_index`.

Кворум-здоров'я: «чи живі більшість/2f + 1?»

Розмір журналу/швидкість компакції, черга снапшотів.
Для BFT: частка голосів, відвал підписантів, затримки QC.

14. 3 Безпека/узгодженість коду

Версійність протоколу на проводі, міграції з сумісністю журналів.
Fencing-токени на зовнішніх ефектах (див. розділ «Розподілені блокування»): лідерський термін (term) передавати в CRON/джоби.

15) Анти-патерни

Ставити консенсус «заради моди» там, де вистачає однієї СУБД або кворумних читань без серіалізації.
Змішувати CP і AP без чітких меж (CAP) → непередбачуваний UX.
Переоцінювати PoW/PoS для корпоративних завдань з десятками вузлів (складно/дорого).
Ігнорувати ре-конфігурацію і «перетинаються кворуми» при зміні складу.
Відсутність read-barrier (lease/read-index) → «брудні» читання.
Запускати 2-вузлові кластери (немає більшості).
Недооцінка дисків і fsync: «у пам'яті все літає» - до першого перезавантаження.

16) Чек-лист вибору

1. Модель відмов: CFT (фарби) або BFT (зловмисні)?
2. Географія: один регіон/три зони або WAN? RTT вирішує.
3. Семантика читань: чи потрібні лінійні читання? Lease/read-index/фоловер-ріди.
4. Навантаження: очікування по p50/p99, throughput; чи потрібна мульти-лідерність.
5. Операційна складність: бібліотека/готовий рушій (etcd/ZK/Consul/Raft-ліби) vs власна реалізація.
6. Реконфігурація: часта? Потрібен joint consensus та інструменти міграцій.
7. Інтеграції: зовнішні побічні ефекти - чи є fencing по epoch/term?
8. Безпека: аутентифікація вузлів, шифрування каналу, контроль версій протоколу.
9. Тест-плейбуки: partition, GC-стоп, лідера kill, slow disk, clock skew.
10. Спостережуваність: метрики лідера/лагів/журналу та алерти налаштовані.

17) Міні-довідник: коли що брати

etcd/Raft-кластер для конфігурацій/блокувань/координації всередині DC.
ZooKeeper/ZAB для сервісів, вже зав'язаних на ZK (старі стеки, черги, лідерство).
Multi-Paxos через готовий сервіс/бібліотеку у вузькоспеціалізованих системах.
EPaxos при георозподілі і низькій конфліктності команд.
Tendermint/HotStuff для permissioned мереж/PoS-лейєра з десятками-сотнями валідаторів і вимогами до фінальності.
Dynamo-подібні/CRDT коли консенсус не потрібен, а важлива доступність/масштаб з подальшим злиттям.

18) Приклади інтерфейсів (псевдо)

18. 1 Коміт запису (Raft-стиль)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18. 2 Read-index для лінійного читання (Raft)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18. 3 Спільна конфігурація

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18. 4 BFT (HotStuff-наближено)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) FAQ

Q: Чому б не використовувати два вузли і тай-брейкер?
A: Два вузли без третього арбітра не дають кворуму при поділі. Потрібно ≥3 (CFT) або 3f + 1 (BFT).

Q: Чим Raft «простіше» Paxos?
A: Чітка декомпозиція, зрозумілі інваріанти логу та конфігурації; легше реалізувати і супроводжувати.

Q: Як читати швидко, не навантажуючи лідера?
A: Follower-reads (послідовні) для некритичних, або lease-reads/read-index для лінійних; кешуйте.

Q: Що вбиває p99?
A: WAN-RTT, дискові fsync, GC-стопи, перегрітий лідер, великі снапшоти в «годину пік».

Q: Чи потрібен консенсус для кешу/каталогу?
A: Якщо достатньо eventual consistency - ні. Якщо потрібні транзакційні інваріанти - так.

20) Підсумки

Консенсус - інструмент для суворої узгодженості та впорядкування. Вибирайте алгоритм, виходячи з моделі відмов і географії; забезпечте кворумні перетини, коректну реконфігурацію, лінійні читання там, де це критично, і спостережуваність. Не забувайте про fencing для зовнішніх ефектів, снапшоти і дисципліну журналів. Тоді реплікація стану буде передбачуваною, а інциденти - рідкісними і зрозумілими.