Algoritmi de consens

1) Ce este consensul și de ce este necesar

Consens - Negociați aceeași valoare/secvență de valori între mai multe noduri pentru eșecuri și întârzieri. În mod tradițional, problema replicării de stat (Stat Machine Replication, SMR) este rezolvată: există o mașină de stare deterministă și o ordine generală a operațiunilor.

• Consens (SMR): o singură ordine totală de comenzi → stocare/registru liniarizabil, metadate de cluster, coordonatori tranzacționali.
• Operațiuni de cvorum fără ordine totală (Dynamo-like, CRDT): permite divergența și fuziunea ulterioară; nu înlocuiți consensul în cazul în care este necesară serializarea globală.

2) Modelul de timp și eșec

2. 1 Model de timp

Rețea asincronă: întârzierile sunt nelimitate; teorema FLP ⇒ este imposibil să se garanteze atât siguranța cât și viața fără ipoteze suplimentare.
Parțial sincron (adesea în practică): după un T necunoscut, sistemul „se comportă” sincron - majoritatea algoritmilor (Raft, Paxos) se bazează pe acest lucru.
Sincron: limite de timp stricte pentru canale (rareori în vânzări, cu excepția rețelelor speciale/PRT).

2. 2 Eșec model

Crash-fault tolerant (CFT): Nodurile pot cădea/atârna, dar nu se comportă malițios.
Bizantin-fault tolerant (BFT): Nodurile pot minți/mesaje false. Necesită 3f + 1 noduri pentru toleranță la f bizantin.

3) Proprietățile consensului

Siguranță: consistență (două noduri corecte nu vor rezolva valori diferite).
Liveness: Dacă rețeaua este „sănătoasă”, se obține o soluție.
Liniarizabilitate (liniaritate): operațiile sunt „văzute” ca atomice într-o singură ordine.
Durabilitate: deciziile luate nu sunt laminate înapoi (protecție jurnal/cvorum).

4) Cvorumuri, majorități și intersecții

În lumea CFT, clasicul: cvorum> N/2. Înregistrările și alegerile liderilor utilizează trecerea cvorumului, astfel încât cele două operațiuni „valide” nu intră în conflict.
În lumea BFT: cvorumurile 2f + 1 din 3f + 1 oferă o intersecție de cel puțin f + 1 noduri oneste.

Regula de trecere: Orice două cvorum trebuie să aibă ≥1 nod comun echitabil (CFT) sau ≥f+1 (BFT).

5) Replicarea de stat (log + cerere)

• Instantanee (o felie din starea după care înregistrările timpurii pot fi șterse/compilate).
• Compactarea jurnalului și triemul jurnalului.
• Verificări determinism (aceeași versiune cod/config).

6) Scheme de conducere și non-conducere

Leadership (Raft, Multi-Paxos, ZAB): un lider serializează înregistrări → mai ușor mental și operațional, latență mai bună pe un lider stabil.
Leaderless/multi-leader (EPaxos, Caesar): mai mult paralelism și toleranță pentru lider, dar o implementare mai dificilă și o soluție de conflict; profitul este vizibil cu mici conflicte de echipe.

7) Algoritmi CFT clasici

7. 1 Paxos/Multi-Paxos (și practici)

Ideea: două faze (pregătire/propunere), promisiuni de acceptori, cvorumuri majoritare. Multi-Paxos lasă un „lider stabil” și transformă operațiunile într-o singură rundă (pentru intrări noi) după „încălzire”.

• Model flexibil, dar dificil de implementat.
• Re-configurări prin intrări speciale (consens comun).
• În practică, biblioteci/motoare (generație Chubby/Spanner).

7. 2 Plută

Descompus pentru învățare: selecție lider, replicare jurnal, re-configurare.

Alegeri: termene aleatorii, vot la termen; un lider pe termen.
AppendEntries: liderul înregistrează fluxuri, monitorizează meciul prefixului (index/termen), se angajează la fixarea majorității.
Citește-cale: leasing-reads (cu un lider puternic) sau read-index pentru citiri liniare.
Reconfig: „comun” - nodurile votează în două clustere înainte de comutare.

Pro: mai ușor de dezvoltat/depanat, invarianți de ordine puternici. Contra: Liderul este un punct de presiune.

7. 3 ZAB (ZooKeeper Atomic Broadcast )/Replicarea ștampilată (VRR)

ZAB: lider difuzează tranzacții, faza de recuperare, zxid (epoch + index).
VRR: „vederi” cu un replicant primar, similar cu Multi-Paxos în spirit.

8) CFT-uri non-lider/multi-lider

8. 1 EPaxos

Nu există un lider permanent: orice nod poate iniția o comandă.
Echipele de conflict primesc ordine parțială; fără conflicte - se angajează la 1-2 RTT la nivel local.
Câștig în geo-distribuție cu conflicte reduse, dar coduri complexe de dependență/grafic.

8. 2 Cezar, Mencius

Variații care optimizează latența/echilibrarea și funcționarea WAN.

9) algoritmi BFT și familia PoS

9. 1 PBFT (Practic BFT)

Trei faze (pre-pregăti/pregăti/comite), necesită 3f + 1 noduri.
Latență scăzută în rețelele locale, drumuri multi-pas și mesaje O (N ²).

9. 2 Tendermint (stil BFT-PoS)

Runde cu propunere și două voturi (prevenire/precommit).
Determinist validator-proposer, timeout-uri, sincronicitate parțială.
Bun pentru rețelele permise/PoS cu zeci/sute de validatoare.

9. 3 HotStuff (și derivați)

Schema trifazată este unificată în „pachete” cu certificate de cvorum (QC).
Complexitatea liniară a comunicațiilor, suportul pentru ambalare și pipelining paralel, este convenabilă pentru implementările în blockchains (de exemplu, ecosistemul Diem/Move).
Cu semnături prag, traficul este redus.

9. 4 PoW/consens cumulat (pe scurt)

Nu BFT în sens strict, ci convergența probabilistică (lanțul cu cele mai multe lucrări). Avantaje: simplitate/deschidere; dezavantaje: energie, ~ secunde-minute până la finalitate.

10) Citește: liniar, secvențial, și cache

Citește liniar: lider cu leasing activ sau prin read-index (Raft) → confirmarea prin cvorum.
Secvențial: poate fi citit din orice nod, dar fără garanții de prospețime.
Adept citește: permise în conformitate cu cerințele slabe; pentru cache-uri - ok.

11) Re-configurare (schimbarea compoziției clusterului)

Necesită două configurații suprapuse (consens comun): orice comite cvorumuri de trecere ale ambelor configurații → fără „găuri”.
Adăugați/eliminați pe rând, observați dimensiunea cvorumului.
Transferul de leadership reduce pauzele.

12) Performanță și tuning

12. 1 Întârzieri

Algoritmi de conducere: 1 RTT per scriere (cu un lider stabil) + replicare.
Distribuție geografică: WAN RTT domină → utilizează regiuni locale + replicare transregională sau abordări EPaxos/HotStuff.

12. 2 Debit

Batching (gruparea comenzilor), AppendEntries paralel, memoria cache a paginii jurnal, aplicație paralelă (atunci când operațiile sunt comutate).
Discuri: NVMe/Log pe un dispozitiv separat, 'O _ DIRECT '/AIO, interval mare' fsync' cu restricții SLA (compromis de durabilitate/latență).

12. 3 cozi p99

Evitați nodurile fierbinți (există întotdeauna un lider): rotație periodică sau citire-descărcare pe adepți.
Monitor GC pauze (JVM/Go), CPU ace, NUMA.

13) Geografie și topologii

1 regiune, 3 zone: cluster clasic CFT (N = 3/5).
2 regiuni: evitați - fără cvorum fiabil la 1-1 împărțit.
3 + regiuni: lider în algoritmi „de mijloc” sau leaderless; sunt posibile proxy-uri regionale/fronturi locale cu jurnal asincron.

14) Probleme practice de funcționare

14. 1 Instantanee și recuperare

Prag după mărimea jurnalului/numărul de tranzacții.
Transferul unui instantaneu la noduri noi; Verificarea sumelor de control.

14. 2 Monitorizare

Leadership: cine este liderul, câți termeni (termen/epocă) s-au schimbat.
Лаги: 'append _ latency', 'commit _ index - applied_index'.

Sănătatea cvorumului: „sunt majoritatea în viață/2f + 1?”

Dimensiunea jurnalului/viteza de compresie, coada de instantanee.

Pentru BFT: cota de vot, semnatarii dump, întârzieri QC

14. 3 Codul de securitate/consecvență

Versionarea protocolului pe sârmă, migrații cu compatibilitate jurnal.
Scrima token-uri pe efecte externe (a se vedea „Încuietori distribuite”): timp de plumb (termen) pentru a transfera la CRON/locuri de muncă.

15) Anti-modele

Pune consens „de dragul modei” în cazul în care un DBMS sau cvorum citește fără serializare sunt suficiente.
Se amestecă CP și AP fără limite clare (CAP) → UX imprevizibil.
Supraestimați PoW/PoS pentru sarcini de întreprindere cu zeci de noduri (dificile/scumpe).
Ignorați re-configurarea și „intersectarea cvorumurilor” atunci când compoziția se schimbă.
Lipsa barierei de citire (leasing/read-index) → a citirilor murdare.
Executați clustere cu 2 noduri (fără majoritate).
Subestimarea discurilor și fsync: „totul zboară în memorie” - până la prima repornire.

16) Lista de verificare a selecției

1. Model de eșec: CFT (accidente) sau BFT (rău intenționat)?
2. Geografie: o regiune/trei zone sau WAN? RTT decide.
3. Semantica de lectură: sunt necesare citiri liniare? Leasing/read-index/follow-up.
4. Încărcare: așteptări de p50/p99, debit; dacă este nevoie de multi-leadership.
5. Complexitate operațională: bibliotecă/motor off-the-raft (etcd/ZK/Consul/Raft-Lifs) vs implementare nativă.
6. Reconfigurarea: frecventă? Avem nevoie de consens comun și de instrumente de migrație.
7. Integrări: efecte secundare externe - există garduri pe epocă/termen?
8. Securitate: autentificarea gazdei, criptarea canalului, controlul versiunii protocolului.
9. Playbook-uri de testare: partiție, GC-stop, kill leader, lent disk, ceas înclinare.
10. Observabilitate: sunt configurate măsurătorile Leader/Lags/Journal și Alert.

17) Mini-ghid: când să ia ceea ce

etcd/Raft cluster pentru configurații/încuietori/coordonare în DC.
ZooKeeper/ZAB pentru servicii deja legate de ZK (stive vechi, cozi, conducere).
Multi-Paxos printr-un serviciu gata/bibliotecă în sisteme foarte specializate.
EPaxos pentru geo-distribuție și conflict de comandă scăzut.
Tendermint/HotStuff pentru rețele permise/PoS-layer cu zeci până la sute de validatoare și cerințe de finalitate.
Dynamo-like/CRDT atunci când nu este nevoie de consens, dar accesibilitatea/scara cu fuziunea ulterioară este importantă.

18) Exemple de interfețe (pseudo)

18. 1 Comite înregistrări (stil 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 Indicele de citire pentru citirea liniară (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 Configurație comună

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

18. 4 BFT (HotStuff aproximativ)

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

19) ÎNTREBĂRI FRECVENTE

Î: De ce nu folosiți două noduri și un întrerupător de cravată?
R: Două noduri fără un al treilea arbitru nu dau cvorum în împărțire. Aveți nevoie de ≥3 (CFT) sau 3f + 1 (BFT).

Î: Ce este Raft' mai simplu "Paxos?
R: Descompunere clară, invarianți ușor de înțeles ai jurnalului și configurației; mai ușor de implementat și întreținut.

Î: Cum citiți rapid fără a încărca liderul?
R: Follower-reads (consecutiv) pentru non-critice, sau lease-reads/read-index pentru liniar; cache.

Î: Ce ucide p99?
R: WAN-RTT, disc fsync, GC-stops, lider supraîncălzit, instantanee mari la ora de vârf.

Î: Are cache-ul/catalogul nevoie de consens?
R: Dacă este suficientă o eventuală consecvență - nu. Dacă sunt necesare invariante tranzacționale, da.

20) Totaluri

Consensul este un instrument pentru o coerență strictă și ordonare. Alegeți un algoritm bazat pe modelul de eșec și geografie; oferă treceri de cvorum, re-configurare corectă, citiri liniare în cazul în care critice, și observabilitate. Nu uitați de garduri pentru efecte externe, instantanee și disciplina revistă. Apoi replicarea de stat va fi previzibilă, iar incidentele vor fi rare și ușor de înțeles.