Le due lezioni precedenti hanno coperto i modelli di consistency (cosa possono vedere le letture) e il tempo (come ordinare gli eventi). Entrambe assumevano qualcosa che non abbiamo ancora giustificato: che il sistema sia in grado di prendere decisioni. Che un gruppo di repliche possa accordarsi su un valore, su un ordine, su un leader, su una configurazione. Senza quella capacità, il resto dello spettro crolla: non puoi offrire la linearizability senza un modo per accordarti su quale write sia arrivato per primo, non puoi offrire la replica leader-based senza un modo per accordarti sul leader, non puoi far evolvere la membership del cluster senza un modo per accordarti sulla nuova membership.
Il nome tecnico di questa capacità è consensus. Far accordare un gruppo di nodi su un singolo valore, anche quando alcuni sono lenti, mancanti, o stanno mentendo, è il problema difficile per antonomasia dei sistemi distribuiti. Esistono risultati di impossibilità ben noti (FLP, nel 1985, ha dimostrato che nessun protocollo asincrono può garantire sia safety che liveness anche con un solo nodo guasto) e soluzioni ben note che funzionano comunque in pratica (Paxos, Raft, e una piccola famiglia di cugini). Questa lezione copre i due protocolli che incontrerai davvero nei sistemi di produzione e i trade-off che hanno portato uno a rimpiazzare in larga parte l’altro.
Cos’è il consensus, e a cosa serve
Il problema del consensus, formalmente: un gruppo di N nodi propone ognuno un valore. Il protocollo deve terminare con ogni nodo non guasto che decide lo stesso valore, e quel valore deve essere uno di quelli proposti da qualcuno. Il protocollo deve soddisfare due proprietà:
- Safety. Tutti i nodi non guasti che decidono, decidono lo stesso valore. Il sistema non è mai in disaccordo con sé stesso, non commette mai due valori diversi per lo stesso slot.
- Liveness. Il protocollo prima o poi termina, e un valore viene deciso. Il sistema fa progressi.
Le due proprietà sono in tensione. Un protocollo che si ferma sempre al primo segno di guai è safe ma non live. Un protocollo che sceglie sempre qualcosa, anche quando è incerto, è live ma non safe. I protocolli di consensus del mondo reale garantiscono safety incondizionatamente e forniscono liveness “quando le condizioni sono abbastanza buone” (la rete sta in gran parte funzionando, una maggioranza di nodi è up, i leader non sono eletti e rieletti in loop). Questo è il compromesso pratico attorno al risultato di impossibilità FLP.
Perché vogliamo il consensus, in termini concreti:
- Leader election. Molti sistemi sono più semplici da ragionare quando un nodo è il leader per un dato ruolo. Scegliere quel leader, e ri-sceglierlo quando il leader corrente fallisce, richiede consensus.
- Log replicati. Un log basato su consensus è la fondazione delle replicated state machine: ogni replica applica la stessa sequenza di operazioni nello stesso ordine, e finisce nello stesso stato. Questo è il modo standard per costruire un database fault-tolerant.
- Lock e lease distribuiti. Quando due client corrono per lo stesso lock, qualcuno deve decidere chi l’ha preso. Quella decisione è consensus.
- Storage di configurazione. La membership del cluster, la topologia, i feature flag. Tutto ciò dove “ogni nodo deve accordarsi sulla risposta” vive in uno store basato su consensus.
Quasi ogni sistema distribuito affidabile che puoi nominare ha un protocollo di consensus al suo cuore, anche se il materiale di marketing non lo menziona. Kubernetes gira su etcd, che gira su Raft. Cloud Spanner gira Multi-Paxos sotto ogni tablet. Kafka, dalla rimozione di ZooKeeper, gira la sua variante di Raft chiamata KRaft. Il protocollo è il muro portante.
Paxos
Il primo algoritmo a risolvere correttamente il consensus in una rete asincrona con fallimenti crash-stop. Leslie Lamport lo ha descritto in un technical report del 1989 sotto un’elaborata metafora sui parlamenti greci, poi lo ha pubblicato formalmente nel 1998 come “The Part-Time Parliament.” La metafora doveva essere affascinante. È riuscita per lo più a rendere il paper difficile da seguire. Lamport stesso ha scritto una versione più semplice nel 2001 chiamata “Paxos Made Simple,” che a sua volta non è semplice.
Privato della metafora, il Paxos di base funziona così. Tre ruoli: proposer (che vogliono far scegliere un valore), acceptor (che formano un quorum e votano sui valori), e learner (che scoprono cosa è stato scelto). Un nodo di solito ricopre più ruoli. Un round di Paxos ha due fasi.
Fase 1 (Prepare). Un proposer sceglie un proposal number n unico e crescente e invia un messaggio “prepare” a una maggioranza di acceptor. Ogni acceptor che non ha promesso qualcosa con un numero più alto risponde con una promessa: “Non accetterò alcuna proposal con un numero inferiore a n.” Se l’acceptor ha già accettato un valore in un round precedente, include quel valore e il suo numero nella risposta.
Fase 2 (Accept). Se il proposer riceve promesse da una maggioranza, sceglie un valore da proporre. Se qualche acceptor ha riportato un valore precedentemente accettato, il proposer deve proporre quel valore (specificamente, quello con il numero accettato più alto). Altrimenti, il proposer è libero di proporre il proprio valore. Invia poi una richiesta “accept” con il valore scelto. Se una maggioranza di acceptor accetta, il valore è scelto.
Il protocollo garantisce che, una volta che un valore è scelto, nessun altro valore può essere scelto per lo stesso slot. La dimostrazione si appoggia sull’overlap della maggioranza: due maggioranze qualsiasi di N acceptor devono condividere almeno un acceptor, e le promesse e accettazioni di quell’acceptor sovrapposto fanno rispettare la proprietà di safety.
Per un sistema a singola decisione questo è sufficiente. I sistemi reali devono prendere una sequenza di decisioni: ogni entry nel log replicato è la propria istanza di consensus. Far girare Paxos di base per ogni entry è corretto ma costoso (due round-trip per decisione). L’ottimizzazione è Multi-Paxos: eleggere un leader stabile, lasciare che il leader salti la Fase 1 per i round successivi, e pagare un round-trip per decisione invece di due. Multi-Paxos è ciò che i sistemi di produzione fanno girare davvero.
Multi-Paxos ha una reputazione. È corretto, ben studiato, e provato su scala. È anche ampiamente considerato difficile da implementare, difficile da debuggare, e difficile da insegnare. Diversi team hanno pubblicato war story su come hanno sbagliato Paxos in modi sottili: race nella leader election, bug off-by-one nello schema dei proposal number, cambi di configurazione che hanno violato l’overlap del quorum.
Raft
Diego Ongaro e John Ousterhout, lavorando a Stanford, hanno scritto un paper nel 2014 intitolato “In Search of an Understandable Consensus Algorithm.” La loro tesi era semplice: Paxos è corretto, ma l’incapacità del campo di insegnarlo in modo consistente è essa stessa un bug. Hanno disegnato Raft da zero con la comprensibilità come obiettivo primario. Il paper offre le stesse garanzie di safety e liveness di Paxos ma le presenta in un modo che un ingegnere può leggere una volta e implementare.
Raft fa alcune scelte opinionate che semplificano il protocollo.
Strong leadership. Raft ha un leader in ogni momento (a meno che non sia in corso un’elezione). Tutte le richieste dei client passano attraverso il leader. Il leader è responsabile di appendere al log e replicarlo ai follower. Non c’è il concetto di “qualunque nodo può proporre”; il leader propone, i follower riconoscono.
Tre ruoli. Ogni nodo si trova in uno di tre stati alla volta: leader, follower, o candidate. Un follower riceve heartbeat dal leader e accetta le entry del log. Un candidate è un nodo che cerca di diventare leader. Un leader è il nodo attualmente al comando. Le transizioni di stato sono chiaramente definite: un follower diventa candidate quando smette di sentire il leader, un candidate diventa leader quando vince un’elezione, un leader si fa da parte quando vede evidenza di un term più recente.
Term number. Raft divide il tempo in term, ognuno che inizia con un’elezione. Un term è identificato da un intero monotonicamente crescente. Ogni messaggio porta un term number, e qualunque nodo veda un term più alto si fa subito da parte e diventa follower aggiornando il suo term. Questo singolo meccanismo rimpiazza lo schema dei proposal number di Paxos ed è molto più facile da ragionare.
Log matching. La log replication di Raft ha un’invariante forte: se due log concordano sulla entry all’indice i, concordano su tutte le entry fino a i. Il leader fa rispettare questo inviando le entry sia con l’indice che con il term dell’indice precedente, e i follower rifiutano qualunque entry che non corrisponda alla loro entry precedente. Questo rende le inconsistenze del log facili da rilevare e riparare.
Il costo: Raft è leggermente meno flessibile di Multi-Paxos in alcuni scenari avanzati. Multi-Paxos può in linea di principio committare entry del log fuori ordine, raggruppare decisioni in modi inusuali, e tollerare alcune configurazioni che Raft rifiuta. In pratica, quasi nessun sistema di produzione ha bisogno di quella flessibilità, e la semplicità di Raft ha dominato.
Una leader election Raft è l’esempio canonico di quanto sia pulito il protocollo. I follower fanno girare un election timeout (randomizzato tra 150 e 300 millisecondi, tipicamente). Se un follower va in timeout senza sentire il leader, incrementa il suo term, vota per sé stesso, e chiede a ogni altro nodo il loro voto. Un nodo vota per al massimo un candidate per term e solo se il log del candidate è almeno aggiornato quanto il suo. Se un candidate riceve una maggioranza di voti, diventa leader e inizia a inviare heartbeat. Se due candidate dividono il voto, entrambi vanno in timeout e ritentano con un nuovo term.
sequenceDiagram
participant F1 as Follower 1
participant F2 as Follower 2
participant C as Candidate
Note over C: election timeout
Note over C: term = term + 1, vote for self
C->>F1: RequestVote(term, log info)
C->>F2: RequestVote(term, log info)
F1-->>C: VoteGranted
F2-->>C: VoteGranted
Note over C: majority received
Note over C: become Leader
C->>F1: AppendEntries (heartbeat)
C->>F2: AppendEntries (heartbeat)Il diagramma cattura l’intera elezione in cinque scambi di messaggi. L’equivalente Paxos, disegnato onestamente, richiede una nota a piè pagina sui leader lease, sui ballot number, e su cosa succede quando due proposer corrono nella Fase 1.
Perché Raft ha in larga parte rimpiazzato Paxos
Lo spostamento nell’industria tra circa il 2014 e il 2020 riguarda quasi interamente il costo di onboarding. I nuovi sistemi distribuiti scelgono Raft perché:
- Un ingegnere può leggere il paper Raft in un pomeriggio e implementare una versione funzionante in una settimana. Paxos richiede molto più tempo, e la prima implementazione è di solito sottilmente sbagliata.
- Raft ha implementazioni di riferimento in ogni linguaggio principale (l’implementazione Go di etcd, hashicorp/raft, raft-rs in Rust di tikv). Sceglierne una dallo scaffale è un’opzione vera. Multi-Paxos ha meno librerie del genere, e quelle che esistono sono fortemente accoppiate ai loro sistemi parent.
- Debuggare Raft in produzione è più facile perché la state machine è piccola e le invarianti sono esplicite. Il debug di Paxos spesso si riduce a “quali proposal number erano in volo quando il leader è fallito.”
Il trade-off è abbastanza piccolo in pratica che l’industria ha votato con i piedi. Multi-Paxos rimane nei sistemi più vecchi perché riscrivere un’implementazione di consensus funzionante è rischioso e raramente vale la pena. I nuovi sistemi scelgono Raft.
Sistemi reali
Un breve tour.
Costruiti su Raft. etcd (il cervello di Kubernetes), Consul (il service catalog e config store di HashiCorp), CockroachDB (ogni range è il proprio gruppo Raft), TiDB (stesso modello), RethinkDB, Vault, Nomad, il protocollo di replica set election di MongoDB dalla versione 3.2 (una variante ispirata a Raft). Apache Kafka dalla transizione a KRaft.
Costruiti su Paxos o una variante di Paxos. Google Spanner (Multi-Paxos per tablet). Google Chubby (il lock service originale che ha ispirato ZooKeeper). Google Megastore. Apache ZooKeeper (che usa Zab, una variante di Paxos sintonizzata per i broadcast ordinati). Microsoft Azure Cosmos DB (Multi-Paxos sotto diversi dei suoi consistency level). Diversi sistemi interni di Amazon.
La lista racconta una storia generazionale. Google ha costruito su Paxos negli anni 2000 perché era l’algoritmo meglio compreso al tempo. La generazione successiva di sistemi open-source, scritta per lo più dopo il 2014, ha scelto Raft per le ragioni sopra.
Il costo in performance
Il consensus non è gratis. Ogni operazione committata richiede un round-trip a una maggioranza di nodi. In un cluster a cinque nodi, questo significa aspettare almeno tre acknowledgment. Il pavimento di latenza è fissato dal nodo più lento nel quorum, più il round-trip time della rete.
In un cluster single-datacenter, questo è attorno a 1, 2 millisecondi per commit. Tra region, può essere da 50 a 200 millisecondi. Ecco perché i sistemi di consensus ad alto throughput fanno batching aggressivamente: un leader che spedisce 1000 log entry in un singolo messaggio AppendEntries paga il costo di un round-trip per 1000 decisioni, non 1000 round-trip. Il batching è ciò che rende Raft viable su scala, ed è il primo posto dove guardare quando le performance del consensus sono cattive.
L’altra leva è la geografia. Un gruppo Raft con membri su tre continenti pagherà latenza scala-continentale su ogni write. Gli architetti che si preoccupano sia di availability che di latency di solito fanno girare più gruppi Raft, ognuno fissato a una singola region per le sue write, con la replica cross-region gestita fuori dal protocollo di consensus. Il “geo-partitioning” di CockroachDB e il piazzamento a livello di directory di Spanner sono entrambi versioni di questa idea.
Chiudendo il cerchio
Il consensus è la fondazione di ogni sistema distribuito affidabile. Senza, non puoi offrire consistency linearizable, non puoi eleggere leader in modo affidabile, non puoi far evolvere la configurazione del cluster in sicurezza. Con esso, puoi costruire sistemi che sopravvivono a guasti dei nodi, partition, ed errori degli operatori, al costo di un round-trip per decisione e della complessità operativa di far girare un quorum.
Le prossime due lezioni coprono cosa succede quando i team cercano di saltare il consensus e costruire sistemi distribuiti su fondazioni più deboli: i failure mode che ne risultano, e gli strumenti (gossip protocol, CRDT, replica leaderless) che esistono per i casi in cui il consensus sarebbe troppo costoso. Sapere quando non usare il consensus è importante quanto sapere come usarlo.