Algorytmy konsensusu

1) Jaki jest konsensus i dlaczego jest potrzebny

Konsensus - Negocjuj tę samą wartość/sekwencję wartości między wieloma węzłami w przypadku awarii i opóźnień. Tradycyjnie rozwiązany jest problem replikacji stanu (State Machine Replication, SMR): istnieje deterministyczna maszyna stanu i ogólny porządek operacji.

• Konsensus (SMR): pojedyncza całkowita kolejność poleceń → linearyzable storage/registry, cluster metadata, koordynatorzy transakcji.
• Operacje kworum bez całkowitego zamówienia (Dynamo-like, CRDT): umożliwiają rozbieżność i późniejsze połączenie; nie zastępują konsensusu tam, gdzie potrzebna jest globalna serializacja.

2) Model czasu i awarii

2. 1 Model czasu

Sieć asynchroniczna: opóźnienia są nieograniczone; FLP twierdzi, że bez dodatkowych założeń niemożliwe jest zagwarantowanie zarówno bezpieczeństwa, jak i lęku.
Częściowo synchroniczny (często w praktyce): po nieznanym T system „zachowuje się” synchronicznie - na tym polegają większość algorytmów (tratwa, Paxos).
Synchroniczne: ścisłe limity czasowe dla kanałów (rzadko w sprzedaży, z wyjątkiem sieci specjalnych/PRT).

2. 2 Model awarii

Tolerancja awarii (CFT): Węzły mogą padać/wisieć, ale nie zachowują się złośliwie.
Tolerancja błędów bizantyjskich (BFT): Węzły mogą kłamać/łamać wiadomości. Wymaga 3f + 1 węzłów dla tolerancji na f bizantyjski.

3) Właściwości konsensusu

Bezpieczeństwo: spójność (dwa prawidłowe węzły nie rozwiążą różnych wartości).
Aktywność: Jeśli sieć jest „zdrowa”, uzyskuje się rozwiązanie.
Linearyzacja (liniowość): operacje są „postrzegane” jako atomowe w jednym porządku.
Trwałość: podejmowane decyzje nie są zwijane z powrotem (ochrona dziennika/kworum).

4) Kworum, wysokość i skrzyżowanie

W świecie CFT klasyczny: kworum> N/2. Rekordy i wybory liderów używają przeprawy kworum, więc dwie „ważne” operacje nie kolidują.
W świecie BFT: kworums 2f + 1 3f + 1 zapewniają przecięcie co najmniej f + 1 węzłów uczciwych.

Zasada przekraczania: Każde dwa kworum musi mieć ≥ 1 wspólny węzeł sprawiedliwy (CFT) lub ≥ f + 1 (BFT).

5) Replikacja stanu (dziennik + aplikacja)

• Migawki (kawałek stanu, po którym można usunąć/skompilować wczesne rekordy).
• Zagęszczenie dziennika i logarytm triem.
• Kontrole determinizmu (ta sama wersja kodu/konfiguracji).

6) Systemy przywództwa i niezwiązane z przywództwem

Przywództwo (Tratwa, Multi-Paxos, ا): jeden lider serializuje rekordy → łatwiejsze psychicznie i operacyjnie, lepsze opóźnienia na stabilnym liderze.
Leaderless/multi-leader (EPaxos, Cezar): więcej równoległości i tolerancji dla lidera, ale trudniejsze wdrożenie i rozwiązanie konfliktu; zysk jest widoczny z małymi konfliktami zespołów.

7) Klasyczne algorytmy CFT

7. 1 Paxos/Multi-Paxos (i praktyki)

Pomysł: dwa etapy (przygotować/zaproponować), obietnice akceptantów, kworum większości. Multi-Paxos pozostawia „stabilnego lidera” i zamienia operacje w jedną rundę (dla nowych wpisów) po „rozgrzaniu”.

• Elastyczny, ale trudny do wdrożenia model.
• Ponowne konfiguracje poprzez specjalne wpisy (wspólny konsensus).
• W praktyce biblioteki/silniki (generacja Chubby/Spanner).

7. 2 Tratwa

Rozkładany do nauki: wybór lidera, replikacja dziennika, ponowna konfiguracja.

Wybory: losowe terminy, głosowanie kadencyjne; jeden lider na kadencję.
AppendEntries: lider strumieni rekordów, monitoruje dopasowanie przedrostka (indeks/termin), zobowiązuje się do utrwalenia większości.
Ścieżka odczytu: lease-reads (z silnym liderem) lub read-index dla odczytów liniowych.
Reconfig: „joint” - węzły głosują w dwóch klastrach przed przełączeniem.

Plusy: łatwiejsze do opracowania/debugowania, niezmienne silne porządki. Lider jest punktem nacisku.

7. 3 • (ZooKeeper Atomic Broadcast )/Oglądane replikacje (VRR)

NA: lider transmituje transakcje, faza odzyskiwania, zxid (epoch + index).
VRR: „widoki” z podstawowym replikatorem, podobnym do Multi-Paxos w duchu.

8) CFT Non-Leader/Multi-Leader

8. 1 EPaxos

Nie ma stałego lidera: każdy węzeł może zainicjować polecenie.
Zespoły konfliktowe otrzymują częściowe zamówienie; free-conflict - commit to 1-2 RTT lokalnie.
Zyski w geo-dystrybucji z niskim konfliktem, ale złożone kody zależności/wykresu.

8. 2 Cezar, Mencjusz

Warianty optymalizujące operację latencji/równoważenia i WAN.

9) algorytmy BFT i rodzina PoS

9. 1 PBFT (praktyczne BFT)

Trzy fazy (pre-prepare/prepare/commit), wymaga węzłów 3f + 1.
Niskie opóźnienia w sieciach lokalnych, wielostopniowych drogach i komunikatach O (N ²).

9. 2 Tendermint (styl BFT-PoS)

Rundy z wnioskiem i dwoma głosami (zapobieganie/precommit).
Deterministyczny walidator, timeouts, częściowa synchroniczność.
Dobre dla dozwolonych/sieci PoS z dziesiątkami/setkami walidatorów.

9. 3 HotStuff (i instrumenty pochodne)

Trójfazowy system jest ujednolicony w „pakiety” z certyfikatami kworum (QC).
Liniowa złożoność komunikacji, wsparcie dla pakowania i rurociągów równoległych, jest wygodna dla implementacji w łańcuchach blokujących (na przykład ekosystem Diem/Move).
Przy sygnaturach progowych ruch jest zmniejszony.

9. 4 PoW/konsensus łączny (w skrócie)

Nie BFT w ścisłym znaczeniu, ale konwergencja probabilistyczna (łańcuch z największą pracą). Zalety: prostota/otwartość; wady: energia, ~ sekundy-minuty do finału.

10) Odczyt: liniowy, sekwencyjny i buforowany

Odczyt liniowy: lider z aktywną dzierżawą lub za pośrednictwem odczytu-indeksu (tratwa) → potwierdzenie przez kworum.
Sekwencyjny: można odczytać z dowolnego węzła, ale bez gwarancji świeżości.
Następca brzmi: dopuszczalne w słabych wymaganiach; dla pamięci podręcznej - ok.

11) Ponowna konfiguracja (zmiana składu klastra)

Wymaga dwóch nakładających się konfiguracji (konsensus): każdy commits pass kworums obu konfiguracji → bez „otworów”.
Dodaj/usuń jeden na raz, obserwuj rozmiar kworum.
Transfer przywództwa zmniejsza pauzy.

12) Wydajność i dostrajanie

12. 1 Opóźnienia

Algorytmy przywództwa: 1 RTT na pismo (ze stabilnym liderem) + replikacja.
Dystrybucja geograficzna: Dominuje WAN RTT → wykorzystaj regiony lokalne + replikacje międzyregionalne lub podejścia EPaxos/HotStuff.

12. 2 Przepustowość

Dozowanie (grupowanie poleceń), równoległe aplikacje AppendEntries, pamięć podręczna strony dziennika, aplikacja równoległa (podczas przełączania operacji).
Dyski: NVMe/Log na osobnym urządzeniu, 'O _ DIRECT '/AIO, duży odstęp' fsync' z ograniczeniami SLA (kompromis trwałości/opóźnienia).

12. 3 ogony p99

Unikaj węzłów gorących (zawsze jest jeden lider): okresowy obrót lub odczyt na naśladowcach.
Monitoruj zatrzymania GC (JVM/Go), piny procesora, NUMA.

13) Geografia i topologie

1 region, 3 strefy: klasyczny klaster CFT (N = 3/5).
2 regiony: unikać - brak wiarygodnego kworum przy 1-1 podziale.
3 + regiony: lider w „środkowym” lub bezołowiowym algorytmie; możliwe są regionalne proxy/fronty lokalne z dziennikiem asynchronicznym.

14) Praktyczne kwestie funkcjonowania

14. 1 Migawki i odzyskiwanie

Próg według wielkości dziennika/liczby transakcji.
Przeniesienie migawki do nowych węzłów; Sprawdź listy kontrolne.

14. 2 Monitorowanie

Przywództwo: kto jest liderem, ile terminów (termin/epoka) się zmieniło.
Лава: 'append _ latency', 'commit _ index - applied_index'.

Zdrowie kworum: „czy większość żyje/2f + 1?”

Rozmiar dziennika/prędkość kompresji, kolejka migawek.

W przypadku BFT: udział w głosowaniu, sygnatariusze wysypisk, opóźnienia QC

14. 3 Bezpieczeństwo kodu/spójność

Wersioning protokołu na drucie, migracje z kompatybilnością dziennika.
Żetony ogrodzeniowe dotyczące efektów zewnętrznych (patrz „Blokady rozproszone”): czas realizacji (termin) przeniesienia do CRON/miejsc pracy.

15) Anty-wzory

Umieść konsensus „dla dobra mody”, gdzie jeden DBMS lub kworum czyta bez serializacji wystarczy.
Wymieszać CP i AP bez wyraźnych granic (CAP) → nieprzewidywalny UX.
Overestimate PoW/PoS dla zadań przedsiębiorstwa z dziesiątkami węzłów (trudne/drogie).
Ignoruj ponowną konfigurację i „przecinające się kworum”, gdy skład się zmienia.
Brak bariery odczytu (dzierżawa/czytanie-indeks) → brudne odczyty.
Uruchom klastry 2-węzłowe (bez większości).
Niedocenianie płyt i fsync: „wszystko leci w pamięci” - aż do pierwszego ponownego uruchomienia.

16) Lista kontrolna wyboru

1. Model awarii: CFT (awarie) lub BFT (złośliwe)?
2. Geografia: jeden region/trzy strefy lub WAN? RTT decyduje.
3. Semantyka czytania: czy odczyty liniowe są konieczne? Dzierżawa/czytanie/monitorowanie.
4. Obciążenie: oczekiwania przez p50/p99, przepustowość; czy potrzebne jest wielozadaniowe przywództwo.
5. Złożoność operacyjna: library/off-the-shelf engine (etcd/ZK/Consul/Raft-libs) vs native implementation.
6. Rekonfiguracja: Częste? Potrzebujemy wspólnego konsensusu i narzędzi migracyjnych.
7. Integracja: zewnętrzne skutki uboczne - czy jest ogrodzenie według epoki/terminu?
8. Bezpieczeństwo: uwierzytelnianie hosta, szyfrowanie kanału, kontrola wersji protokołu.
9. Test playbooks: partycja, GC-stop, kill leader, slow disk, skew zegara.
10. Obserwowalność: Lider/Lags/Journal i Alert Metrics są skonfigurowane.

17) Mini-przewodnik: kiedy wziąć co

Klaster etcd/tratwa dla konfiguracji/zamków/koordynacji w DC.
ZooKeeper dla usług już związanych z ZK (stare stosy, kolejki, przywództwo).
Multi-Paxos za pośrednictwem gotowej usługi/biblioteki w wysoko wyspecjalizowanych systemach.
EPaxos dla geo-dystrybucji i niskiego konfliktu dowodzenia.
Tendermint/HotStuff dla dozwolonych sieci/PoS-layer z dziesiątkami do setek walidatorów i wymagań dotyczących finalności.
Dynamopodobne/CRDT, gdy konsensus nie jest potrzebny, ale dostępność/skala z późniejszym połączeniem jest ważna.

18) Przykłady interfejsów (pseudo)

18. 1 Rekordy Commit (styl tratwy)

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 Czytelnik do odczytu liniowego (tratwa)

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 Konfiguracja wspólna

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

18. 4 BFT (HotStuff przybliżony)

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

19) FAQ

P: Dlaczego nie użyć dwóch węzłów i łącznika?
Odp.: Dwa węzły bez trzeciego arbitra nie dają kworum w podziale. Potrzebujesz ≥ 3 (CFT) lub 3f + 1 (BFT).

P: Co to jest tratwa „prostsze” Paxos?
Odp.: Wyraźny rozkład, zrozumiałe niezmienniki dziennika i konfiguracji; łatwiejsze do wdrożenia i utrzymania.

P: Jak czytasz szybko bez ładowania lidera?
Odp.: Odczyty naśladowców (kolejne) dla niekrytycznych lub leasingowych/odczytowych dla liniowych; pamięci podręcznej.

P: Co zabija p99?
Odp.: WAN-RTT, dysk fsync, przystanki GC, przegrzany lider, duże migawki w godzinie szczytu.

P: Czy pamięć podręczna/katalog wymaga konsensusu?
Odp.: Jeśli wystarczy ewentualnej spójności - nie. Jeśli wymagane są niezmienne transakcje, tak.

20) Kwoty całkowite

Konsensus jest narzędziem ścisłej spójności i zamawiania. Wybierz algorytm oparty na modelu awarii i geografii; zapewniają skrzyżowania kworum, prawidłową konfigurację, czytniki liniowe, gdzie krytyczne i obserwowalność. Nie zapomnij o ogrodzeniu dla efektów zewnętrznych, migawki i dyscypliny magazynu. Wtedy replikacja stanu będzie przewidywalna, a incydenty będą rzadkie i zrozumiałe.