Algoritmi di Consenso a Confronto: Raft, Multi-Paxos, Viewstamped Replication ed EPaxos

Perché il Consenso È Difficile (Riepilogo Veloce)

Il problema fondamentale: N server devono concordare su una sequenza di operazioni, anche se fino a F di essi crashano (dove N >= 2F + 1). Questo accordo deve essere:

• Safe: Tutti i server non guasti concordano sulla stessa sequenza
• Live: Il sistema alla fine fa progressi (assumendo meno di F+1 crash e che la rete alla fine consegni i messaggi)

Il risultato di impossibilità FLP ci dice che non possiamo avere entrambi in una rete asincrona con anche un solo guasto per crash. Ogni algoritmo di consenso pratico aggira questo usando timeout come rilevatori di guasti — il che tecnicamente viola il modello asincrono, ma funziona in pratica perché le reti reali hanno ritardi limitati-ma-sconosciuti.

Raft: L'Algoritmo Che Si Spiega Da Solo

Raft è stato progettato per la comprensibilità, e mantiene quella promessa. L'algoritmo si decompone in tre sottoproblemi: elezione del leader, replicazione del log e safety. Mi concentro sulle parti che sono più difficili da implementare di quanto il paper suggerisca.

Elezione del Leader: Le Parti Sottili

Il meccanismo base è semplice: i candidati incrementano il loro term, votano per se stessi e richiedono voti agli altri. Ma i dettagli implementativi contano enormemente.

type RaftNode struct {
 mu sync.Mutex
 state NodeState
 currentTerm uint64
 votedFor *uint64
 log []LogEntry

 electionTimeout time.Duration
 heartbeatTimeout time.Duration
 lastHeartbeat time.Time

 // Protocollo pre-vote (Sezione 9.6 della dissertazione di Raft)
 preVoteEnabled bool
}

func (n *RaftNode) startElection() {
 n.mu.Lock()
 defer n.mu.Unlock()

 if n.preVoteEnabled {
 // Pre-vote: chiedere ai peer se voterebbero per noi SENZA incrementare il term
 // Questo previene le disruzioni da nodi partizionati
 n.runPreVote()
 return
 }

 n.currentTerm++
 n.state = Candidate
 n.votedFor = &n.id
 n.persistState() // DEVE essere durabile prima di inviare RequestVote

 lastLogIndex, lastLogTerm := n.lastLogInfo()

 for _, peer := range n.peers {
 go func(p PeerID) {
 reply, err := n.sendRequestVote(p, &RequestVoteArgs{
 Term: n.currentTerm,
 CandidateID: n.id,
 LastLogIndex: lastLogIndex,
 LastLogTerm: lastLogTerm,
 })
 if err != nil {
 return
 }
 n.handleVoteResponse(reply)
 }(peer)
 }
}

Il protocollo pre-vote è critico e spesso omesso dai tutorial. Senza di esso, un nodo che viene partizionato dal cluster continua a incrementare il suo term. Quando si riconnette, il suo term artificialmente alto forza una nuova elezione, disturbando il cluster sano. Pre-vote chiede "voteresti per me?" senza incrementare effettivamente il term. Se la risposta è no (perché il cluster ha già un leader sano), il nodo si ritira.

Log Compaction: Dove Vive il Dolore

La Sezione 7 del paper di Raft sulla log compaction è circa una pagina. La mia implementazione è di 2.000 righe. Ecco perché:

type SnapshotManager struct {
 stateMachine StateMachine
 raftLog *RaftLog
 snapshotDir string

 inProgress atomic.Bool
 lastIncluded struct {
 Index uint64
 Term uint64
 }
}

func (sm *SnapshotManager) TakeSnapshot() error {
 if !sm.inProgress.CompareAndSwap(false, true) {
 return ErrSnapshotInProgress
 }
 defer sm.inProgress.Store(false)

 snapshot, appliedIndex, appliedTerm := sm.stateMachine.Snapshot()

 tmpPath := filepath.Join(sm.snapshotDir, fmt.Sprintf("snap-%d.tmp", appliedIndex))
 finalPath := filepath.Join(sm.snapshotDir, fmt.Sprintf("snap-%d.dat", appliedIndex))

 f, err := os.Create(tmpPath)
 if err != nil {
 return err
 }

 header := SnapshotHeader{
 LastIncludedIndex: appliedIndex,
 LastIncludedTerm: appliedTerm,
 Size: uint64(len(snapshot)),
 Checksum: crc32.ChecksumIEEE(snapshot),
 }

 if err := binary.Write(f, binary.LittleEndian, header); err != nil {
 f.Close()
 os.Remove(tmpPath)
 return err
 }

 if _, err := f.Write(snapshot); err != nil {
 f.Close()
 os.Remove(tmpPath)
 return err
 }

 if err := f.Sync(); err != nil {
 f.Close()
 os.Remove(tmpPath)
 return err
 }
 f.Close()

 if err := os.Rename(tmpPath, finalPath); err != nil {
 return err
 }

 sm.raftLog.TruncateBefore(appliedIndex)
 sm.lastIncluded.Index = appliedIndex
 sm.lastIncluded.Term = appliedTerm

 return nil
}

Le parti difficili:

1. Fare lo snapshot non deve bloccare l'applicazione del log. Se la tua state machine è un B-tree, hai bisogno di semantica copy-on-write o un meccanismo di snapshot isolation. BoltDB te lo dà gratis; una mappa in memoria naive no.

2. L'RPC InstallSnapshot è chunked. Quando un follower è così indietro che il leader ha già compattato il suo log, il leader invia il suo snapshot. Per state machine multi-GB, questo deve essere chunked e resumable. Il paper lo menziona in una frase.

3. Il crash recovery intercala snapshot e log. Al riavvio, carichi l'ultimo snapshot, poi replichi le entry del log dopo l'ultimo indice incluso nello snapshot. Se sei crashato tra prendere uno snapshot e truncare il log, potresti avere entry sovrapposte. La tua logica di recovery deve gestire questo.

Multi-Paxos: Un Protocollo Senza Specifica Canonica

Ecco il segreto sporco di Multi-Paxos: non esiste un paper canonico di Multi-Paxos. L'originale "The Part-Time Parliament" di Lamport descrive Paxos a singolo decreto. L'estensione a multi-decreto (una sequenza di istanze di consenso) è descritta informalmente, e ogni implementazione fa scelte diverse.

L'ottimizzazione core di Multi-Paxos rispetto al Paxos base: una volta stabilito un leader, può saltare la fase Prepare per le entry di log successive, andando direttamente all'Accept. Questo significa che le operazioni a regime richiedono solo un round-trip invece di due.

func (n *MultiPaxosNode) Propose(value []byte) (uint64, error) {
 if !n.proposerState.isLeader {
 return 0, ErrNotLeader
 }

 slot := atomic.AddUint64(&n.proposerState.maxSlot, 1)

 acceptMsg := &AcceptMessage{
 Ballot: n.proposerState.ballotNum,
 Slot: slot,
 Value: value,
 }

 ackCount := 1
 quorum := (len(n.peers) / 2) + 1

 for _, peer := range n.peers {
 go func(p PeerID) {
 reply, err := n.sendAccept(p, acceptMsg)
 if err != nil {
 return
 }

 if reply.Ballot > n.proposerState.ballotNum {
 n.stepDown(reply.Ballot)
 return
 }

 if atomic.AddInt32(&ackCount, 1) >= int32(quorum) {
 n.markChosen(slot, value)
 }
 }(peer)
 }

 return slot, nil
}

Il Problema dei Gap negli Slot

In Multi-Paxos, gli slot possono essere scelti fuori ordine. La richiesta del Cliente A potrebbe ottenere lo slot 5, e quella del Cliente B lo slot 7, mentre lo slot 6 è ancora pendente. Quando consegni comandi alla state machine, devi consegnarli in ordine. Questo significa che hai bisogno di un meccanismo per riempire i gap — sia con no-op che riproponendo valori per slot vuoti.

Questa logica di gap-filling è dove la maggior parte delle implementazioni Multi-Paxos ha bug. L'interazione tra gap-filling, cambi di leader e la fase accept è sottile. Se un nuovo leader inizia a riempire gap in modo concorrente con gli accept del vecchio leader ancora in volo, puoi finire con uno slot scelto con due valori diversi a meno che il meccanismo di ballot number sia correttamente implementato.

Viewstamped Replication: Il Figlio di Mezzo Dimenticato

VR precede Paxos nella pubblicazione ed è notevolmente simile a Raft nella struttura — ha un primary (leader), view (term) e un log. Le differenze chiave sono nel protocollo di view change e nel meccanismo di riconfigurazione.

Operazione Normale (semplificata):
1. Client → Primary: REQUEST(op, client-id, request-num)
2. Primary: Assegnare op-number, aggiungere al log
3. Primary → Backup: PREPARE(view, op-number, op, commit-number)
4. Backup: Aggiungere al log, rispondere PREPARE-OK
5. Primary: Dopo f+1 PREPARE-OK, commit
6. Primary → Client: REPLY(view, request-num, result)

La cosa interessante di VR è il suo protocollo di view change, che è più strutturato dell'elezione di Raft. Quando un backup sospetta che il primary sia guasto:

1. Invia messaggi START-VIEW-CHANGE
2. Dopo aver ricevuto f tali messaggi, un nodo invia DO-VIEW-CHANGE al nuovo primary (determinato da round-robin)
3. Il nuovo primary raccoglie f+1 messaggi DO-VIEW-CHANGE, seleziona il log con i dati più recenti e avvia la nuova view

La selezione deterministica del primary (round-robin basato sul numero di view) significa che non c'è uno scenario di split-vote — non servono timeout randomizzati come Raft. Il tradeoff è meno flessibilità: non puoi preferire un nodo con hardware migliore o latenza inferiore ai client.

Dove VR Brilla

Il protocollo di riconfigurazione di VR (cambiare l'insieme delle repliche) è significativamente più semplice dell'approccio joint consensus di Raft. In VR, la riconfigurazione è semplicemente un'operazione speciale nel log. Quando viene committata, la nuova configurazione prende effetto in quel punto del log. Le vecchie repliche trasferiscono lo stato alle nuove, e la transizione è pulita.

Ho usato l'approccio di riconfigurazione di VR anche nella mia implementazione di Raft, perché il joint consensus di Raft (Sezione 6 del paper) è un incubo da implementare correttamente.

EPaxos: La Promessa Leaderless

EPaxos (Egalitarian Paxos) è il più intellettualmente ambizioso dei quattro. Invece di incanalare tutte le operazioni attraverso un leader, qualsiasi replica può proporre comandi. I comandi non conflittuali possono essere committati in un singolo round-trip (il fast path), e i conflitti vengono risolti attraverso un grafo di dipendenze.

Il Grafo delle Dipendenze

Qui è dove EPaxos si complica. Ogni comando porta un insieme di dipendenze — altri comandi dopo i quali deve essere eseguito:

func (r *EPaxosReplica) StartCommand(cmd []byte) {
 inst := &EPaxosInstance{
 Command: cmd,
 SeqNum: 0,
 Deps: make(map[InstanceID]uint64),
 Status: PreAccepted,
 }

 for id, other := range r.instances {
 if r.conflictsWithAny(cmd, other.Command) {
 inst.Deps[id] = other.SeqNum
 if other.SeqNum >= inst.SeqNum {
 inst.SeqNum = other.SeqNum + 1
 }
 }
 }

 superQuorum := (3*len(r.peers)/4) + 1
 replies := r.broadcastPreAccept(inst)

 if r.fastPathSucceeded(replies, inst, superQuorum) {
 inst.Status = Committed
 r.broadcastCommit(inst)
 } else {
 r.mergedDeps(inst, replies)
 inst.Status = Accepted
 r.broadcastAccept(inst)
 }
}

Il Problema dell'Esecuzione

Committare è facile. Eseguire è difficile. Poiché i comandi vengono committati da repliche diverse con insiemi di dipendenze diversi, serve un algoritmo deterministico per linearizzare il grafo delle dipendenze. Questo usa l'algoritmo delle componenti fortemente connesse di Tarjan:

1. Costruire il grafo delle dipendenze dalle istanze committate
2. Trovare tutte le componenti fortemente connesse (SCC)
3. Eseguire le SCC in ordine topologico inverso
4. All'interno di ogni SCC, eseguire i comandi in ordine di numero di sequenza

Confronto delle Performance

Ho benchmarkato tutti e quattro su un cluster di 5 nodi (AWS c6g.xlarge, stessa regione, 0.3ms RTT inter-nodo):

Algoritmo	Throughput (ops/s)	Latenza P50	Latenza P99	Note
Raft	42.000	0.8ms	2.1ms	BatchSize=64
Multi-Paxos	58.000	0.6ms	1.8ms	Accept pipelined
VR	41.000	0.9ms	2.3ms	Simile a Raft
EPaxos (no conflitti)	73.000	0.4ms	1.2ms	Fast path
EPaxos (50% conflitti)	31.000	1.4ms	8.7ms	Slow path + deps

EPaxos vince in modo convincente quando i comandi non conflittuano. Ma con il 50% di tasso di conflitto (comune nei workload key-value dove le chiavi seguono la distribuzione Zipf), è il peggior performer. L'overhead della risoluzione delle dipendenze domina.

Cosa Sceglierei Oggi

Per la maggior parte dei sistemi: Raft con le ottimizzazioni di etcd (pipelining, learner node, pre-vote, leader lease per le letture). L'ecosistema non ha paragoni — etcd, CockroachDB, TiKV e Consul usano tutti varianti di Raft, e le loro implementazioni battle-tested sono disponibili come librerie.

Per sistemi geo-distribuiti con operazioni prevalentemente non conflittuali: EPaxos, ma solo se hai le risorse ingegneristiche per gestire la complessità implementativa e l'incubo di debugging che è la risoluzione dei grafi di dipendenze.

Per imparare e costruire intuizione: implementa Raft prima, poi VR. Le somiglianze cristallizzeranno la tua comprensione, e le differenze nel view change vs. election ti insegneranno perché queste scelte di design contano.

Multi-Paxos è la risposta giusta se hai bisogno del massimo throughput su un singolo leader e sei disposto a investire in un'implementazione custom. Ma onestamente, a quel punto, dovresti probabilmente usare etcd o CockroachDB e concentrare il tuo sforzo ingegneristico sul tuo prodotto reale.