Algoritmi di consenso

1) Che cosa è il consenso e perché è necessario

Consenso: coerenza dello stesso valore/sequenza di valori tra più nodi in caso di guasti e ritardi. La replica di stato (State Machine Replication, SMR) è una soluzione tradizionale, con una macchina di stato determinata e un ordine generale delle operazioni.

• Consenso (SMR) - Un unico ordine totale dei comandi di storage/registro lineare, metadati del cluster, coordinatori transazionali.
• Operazioni quorum senza ordine totale (Dynamamo-simili, CRDT): consentono la divergenza e la successiva fusione; non sostituiscono il consenso quando c'è bisogno di una serializzazione globale.

2) Modello tempo e guasti

2. 1 Modello di tempo

Rete asincrona: i ritardi sono illimitati; il teorema FLP non può essere garantito sia da safety che da liveness senza ulteriori presupposti.
Parzialmente sincrona (spesso in pratica): dopo una T sconosciuta, il sistema si comporta in modo sincrono: la maggior parte degli algoritmi (Raft, Paxos) si basa su questo.
Sincrone: limiti di tempo rigidi per canale (raramente in vendita, tranne reti speciali/PTP).

2. 2 Modello di guasto

Crash-fault tolerant (CFT) - I nodi possono cadere/appendere, ma non comportarsi male.
Byzantine-fault tolerant (BFT) - I nodi possono mentire/falsificare messaggi. Sono necessari 3f + 1 nodi per tollerare f bizantini.

3) Proprietà consenso

Safety (protezione) - Coerenza (i due nodi corretti non risolvono valori diversi).
Liveness - Se la rete è sana, la soluzione viene raggiunta.
Linearità (linearità) - Le operazioni vengono viste come atomiche in un unico ordine.
Durata: le decisioni prese non vengono ritrattate (protezione registro/quorum).

4) Quorum, maggioranza e intersezioni

Nel mondo CFT il classico è quorum> N/2. Le registrazioni e l'elezione del leader utilizzano l'intersezione dei quorum, quindi le due operazioni «validi» non sono in conflitto.
Nel mondo BFT, i quorum 2f + 1 di 3f + 1 consentono l'intersezione di un minimo di f + 1 nodi onesti.

Regola di intersezione: tutti i due quorum devono avere un nodo comune equo (CFT) o un (BFT).

5) Replica dello stato (registro + applicazione)

• Snapshot (taglio di stato dopo il quale è possibile eliminare/compilare i record iniziali).
• Compagine del registro e login-triim.
• Controlli di determinismo (identica versione codice/configure).

6) Diagrammi di leadership e non ideali

Leader (Raft, Multi-Paxos, ZAB): Un leader serializza le registrazioni in modo più semplice mentalmente e operativamente, meglio latency su un leader stabile.
Illimitati/multi-ideali (APaxos, Caesar): più parallelismo e tolleranza verso il leader, ma più difficile da implementare e risolvere conflitti; il profitto è visibile nei piccoli conflitti dei comandi.

7) Algoritmi CFT classici

7. 1 Paxos/Multi-Paxos (e pratiche)

L'idea è di due fasi (predare/propose), promesse di accettatori, quorum maggioritari. Multi-Paxos lascia il «leader stabile» e trasforma le operazioni in un singolo round (per nuovi record) dopo «riscaldamento».

• Modello flessibile ma complesso da implementare.
• E-configurazioni tramite record speciali (joint consensus).
• In pratica, librerie/motori (Chubby/Spanner Generation).

7. 2 Raft

Decomposizione per l'apprendimento: scelta del leader, replica dei logi, configurazione della re.

Election: timeout casuale, voto per termini; Un leader per un mandato.
AppendEntries Il leader stravolge le registrazioni, controlla la corrispondenza del prefisso (indice/term), il commit di fissazione maggioritaria.
Read-path: lease-reads (con un forte leader) o read-index per le letture lineari.
Riconfig - Configurazione congiunta - I nodi votano in due cluster prima della transizione.

I vantaggi sono più semplici da sviluppare/debag, forti invarianti dell'ordine. Il leader è un punto di pressione.

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

ZAB: il leader trasmette transazioni, fasi di ripristino, zxid (era + indice).
VRR: «viste» (views) con replica primaria, simile a Multi-Paxos per spirito.

8) CFT non ideali/multi-ideali

8. 1 EPaxos

Nessun leader permanente: qualsiasi nodo può avviare un comando.
I comandi di conflitto ottengono un ordine parziale; senza conflitto - si colloca in 1-2 RTT locale.
Vincite in georassistenza con bassa conflittualità, ma complessi codici di dipendenze/grafici.

8. 2 Caesar, Mencius

Variazioni che ottimizzano i ritardi/bilanciamenti e il funzionamento in WAN.

9) algoritmi BFT e famiglia PoS

9. 1 PBFT (Practical BFT)

Tre fasi (pre-predare/predare/commit) richiedono 3f + 1 nodi.
Bassa latitanza su reti locali, strade multifunzione e O (N m2) messaggi.

9. 2 Tendermint (stile BFT-PoS)

Round con proposal e due voci (prevote/precommit).
Costruttore determinatore, timeout, sincronità parziale.
Buono per le reti permissioned/PoS con decine/centinaia di valigatori.

9. 3 HotStuff (e derivati)

Lo schema trifase è unificato in «pacchetti» con certificati quorum (QC).
La complessità lineare delle comunicazioni, il supporto per la batch e la piplinazione parallela, è facile da implementare in blockchain (ad esempio Diem/Move Ecosistema).
Con le firme di soglia (threshold signature), il traffico diminuisce.

9. 4 PoW/consenso di risparmio (in breve)

Non BFT in senso rigoroso, ma convergenza plausibile (la catena con il lavoro più alto). Virtù: semplicità/apertura; i difetti sono energia, secondi o secondi prima della finalità.

10) Letture lineari, sequenziali e memorizzate nella cache

Letture lineari: il leader con lease attiva o tramite read-index (Raft) → la conferma attraverso il quorum.
Sequenziali: potete leggere da qualsiasi nodo, ma senza garanzie di freschezza.
Follower reads: validi in caso di requisiti deboli Ok per la cache.

11) Configurazione re (modifica composizione cluster)

Richiede due configurazioni sovrapposte (joint consensus): tutte le committenti vengono sottoposte a quorum di entrambe le configurazioni senza «buchi».
Aggiungi/rimuovi uno alla volta, mantieni la dimensione del quorum.
La migrazione della leadership (leadership transfer) riduce le interruzioni.

12) Prestazioni e tuning

12. 1 Ritardi

Algoritmi di leadership: 1 RTT per scrittura (con leader stabile) + replica.
Georassistenza: WAN RTT domina, usa le regioni locali + ripliking crociato-regionale o approcci EPaxos/HotStuff.

12. 2 Larghezza di banda

Batching (raggruppamento dei comandi), AppendEntries paralleli, file-cash del registro, applicazioni parallele (quando le operazioni vengono commutate).
Unità: NVMe/Registro su periferica separata, 'O _ DIRECT '/AIO, grande' fsync '- interstatale con vincoli SLA (compromesso durability/latency).

12. 3 Code p99

Evitare i nodi caldi (leader sempre uno): rotazione periodica o read-offload sui followers.
Controllare le pause GC (JVM/Go), i pin CPU, NUMERA.

13) Geografia e topologia

1 regione, 3 zone: classico cluster CFT (N = 3/5).
2 regioni: evitare - non si ottiene un quorum affidabile quando si divide 1-1.
3 + regioni: leader nel «mezzo» o algoritmi illimitati; sono disponibili proxy/fronti locali regionali con registro asincrono.

14) Questioni pratiche di funzionamento

14. 1 Snapshot e ripristino

Soglia per dimensione di registro/numero di operazioni.
Trasferire il snapshot ai nuovi nodi; Controllo degli importi di controllo.

14. 2 Monitoraggio

Leadership: chi è il leader, quanti tempi (term/epoch) sono cambiati.
Лаги: `append_latency`, `commit_index - applied_index`.

Quorum health: «La maggior parte/2f + 1 è viva?»

Dimensione del registro/velocità di compressione, coda di snapshot.
Per la BFT, percentuale di voti, cancellazione dei firmatari, ritardi del QC.

14. 3 Sicurezza/coerenza del codice

Versione del protocollo sul cavo, migrazione con la compatibilità dei registri.
Token Fencing sugli effetti esterni (vedere Blocchi distribuiti): tempo di leadership (term) trasmesso a CRON/jobs.

15) Anti-pattern

Mettere il consenso per la moda dove c'è abbastanza database o letture quorum senza serializzazione.
Miscelare CAP e AP senza limiti netti (CAP) con un UX imprevedibile.
Sovrastima le attività aziendali con decine di nodi (complessi/costosi).
Ignora la configurazione e i quorum di intersezione quando la composizione viene modificata.
L'assenza di read-barrier (lease/read-index) è una lettura «sporca».
Avvia cluster a 2 nodi (nessuna maggioranza).
Sottovalutazione dei dischi e fsync: «Tutto vola nella memoria» - prima del primo riavvio.

16) Assegno-foglio di selezione

1. Modello di guasto: CFT (crash) o BFT (malavitosi)?
2. Geografia: una regione/tre zone o WAN? La RTT decide.
3. Semantica di lettura: sono necessarie letture lineari? Lease/read-index/followers rids.
4. Carico: attesa p50/p99, throughput; se c'è bisogno di una leadership multi.
5. Complessità operativa: libreria/motore pronto (etcd/ZK/Consul/Raft-Lips) vs propria implementazione.
6. La riconfigurazione è frequente? Serve un joint consensus e strumenti di migrazione.
7. Integrazioni: effetti collaterali esterni - ci sono fencing per epoch/term?
8. Protezione: autenticazione dei siti, crittografia del canale, controllo delle versioni del protocollo.
9. Playbook di prova: partition, GC-stop, leader kill, slow disk, clock skew.
10. Le metriche del leader/lag/registro e gli alert sono configurati.

17) Mini-guida: quando prendere cosa

etcd/Raft-cluster per configurazioni/blocchi/coordinazione all'interno della DC.
ZooKeeper/ZAB per servizi già collegati a ZK (vecchie pile, code, leadership).
Multi-Paxos attraverso un servizio/libreria finiti in sistemi altamente specializzati.
EPaxos per la distribuzione geografica e la ridotta conflittualità dei comandi.
Tendermint/HotStuff per le reti permissionate/PoS-Leier con decine-centinaia di validatori e requisiti di finalità.
Dynamamo-simili/CRDT quando il consenso non è necessario, ma importante per la disponibilità/scala e la fusione successiva.

18) Esempi di interfaccia (pseudo)

18. 1 Commit di scrittura (stile 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 per la lettura lineare (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 Configurazione congiunta

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

18. 4 BFT (HotStuff-approssimativamente)

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

19) FAQ

Q: Perché non usare due nodi e un tie breaker?
A: Due nodi senza un terzo arbitro non danno quorum durante la separazione. Deve essere ≥3 (CFT) o 3f + 1 (BFT).

Q: In che modo Raft «è più semplice» Paxos?
A: Decomposizione netta, comprensibili invarianti di loggia e configurazione più facile da realizzare e da accompagnare.

Come si legge velocemente senza caricare il leader?
A: Follower-reads (sequenziali) per non critici o lease-reads/read-index per lineari; nella cache.

Cosa uccide la p99?
A: WAN-RTT, dischi fsync, piedi GC, leader surriscaldato, grandi snapshot in «ora di punta».

Q: È necessario un consenso per la cache/catalogo?
A: Se c'è abbastanza eventual consistency, no. Se sono necessari invarianti transazionali, sì.

20) Riepilogo

Il consenso è uno strumento per la coerenza e l'ordinamento rigorosi. Selezionare un algoritmo in base al modello di errore e alla geografia; fornite intersezioni quorum, configurazione ra-lineare corretta, letture lineari dove è critico e osservabilità. Non dimenticare il fencing per effetti esterni, snapshot e disciplina dei registri. Allora la replica sarà prevedibile e gli incidenti rari e comprensibili.