(articolo redatto da Gaetano De Pascale)
In questo approfondimento parliamo degli algoritmi di consenso distribuito, sviluppati per risolvere il problema di avere più nodi in una rete, che cercano di raggiungere un accordo su una decisione comune.
Che cos’è un sistema distribuito
Un sistema distribuito è un insieme di componenti software autonomi che interagiscono tra loro attraverso una rete di comunicazione per raggiungere un obiettivo comune.
In un sistema distribuito, le risorse di elaborazione, memoria e dati sono distribuite tra più computer, anziché essere concentrate in un’unica macchina.
Questo sistema risulta completamente trasparente all’utente finale, che pensa di interagire con un’unica entità remota.
Esso consente di:
- gestire grandi quantità di dati ed elaborazioni complesse in modo più efficiente, grazie alla capacità di scalare orizzontalmente, aggiungendo nuovi nodi di elaborazione,
- garantire una maggiore affidabilità, in quanto un guasto su un nodo non compromette il funzionamento dell’intero sistema.
Alcuni esempi di sistemi distribuiti sono le reti peer-to-peer, i cluster di elaborazione, i servizi web e le applicazioni cloud.
Algoritmi di consenso distribuito
Gli algoritmi di consenso distribuito sono stati sviluppati per risolvere il problema di avere più nodi in una rete che cercano di raggiungere un accordo su una decisione comune.
L’obiettivo di questi algoritmi è di garantire che tutti i nodi nella rete raggiungano lo stesso consenso sulla decisione senza la necessità di un’autorità centrale.
La storia degli algoritmi di consenso distribuito risale almeno al 1982, quando Leslie Lamport ha proposto l’algoritmo di Paxos. Questo è stato uno dei primi algoritmi di consenso distribuito sviluppati e ha rappresentato un importante passo avanti nella ricerca sui sistemi distribuiti.
L’algoritmo di Paxos prevede che i nodi della rete inviino messaggi a un coordinatore, chiamato “proposer“, che a sua volta invia messaggi di proposta ai nodi della rete. Se la maggioranza dei nodi accetta la proposta, allora questa diventa il consenso della rete.
Un altro importante algoritmo di consenso distribuito è stato sviluppato nel 2008 da Satoshi Nakamoto, il creatore di Bitcoin. L’algoritmo di Nakamoto è stato utilizzato per creare la blockchain di Bitcoin e si basa su una rete di nodi, che condividono un registro contabile pubblico, chiamato “blockchain”.
Gli utenti di Bitcoin possono inviare transazioni alla rete, e i nodi della rete cercano di raggiungere un consenso sulla validità di queste transazioni. Una volta che una transazione è stata confermata dalla maggioranza dei nodi, viene aggiunta alla blockchain.
Negli anni successivi, sono stati sviluppati altri algoritmi di consenso distribuito, tra cui l’algoritmo di Raft, proposto nel 2014 da Diego Ongaro e John Ousterhout.
L’obiettivo di Raft, che è anche la grande novità, è proprio nel titolo del suo whitepaper: “In Search of an Understandable Consensus Algorithm” (rif. https://raft.github.io/raft.pdf). L’obiettivo di Ongaro e Ousterhout era quello di ideare un algoritmo comprensibile e molto più semplice da implementare e manutenere rispetto a Paxos.
Focus sull’algoritmo RAFT
Ci sono alcune caratteristiche chiave dell’algoritmo Raft che lo rendono più semplice da implementare e mantenere rispetto ad altri algoritmi di consenso distribuito.
In primo luogo, Raft utilizza un approccio leader-based, il che significa che solo il leader della rete invia messaggi di log ai nodi. Questo semplifica la logica dell’algoritmo, poiché ogni nodo deve solo interagire con il leader, anziché con tutti gli altri nodi della rete.
Inoltre, Raft utilizza un meccanismo di timeout basato su un orologio interno, il che significa che un nodo si considera non più attivo se non riceve messaggi da altri nodi entro un determinato intervallo di tempo. Ciò evita che un nodo rimanga attivo a lungo senza comunicare con gli altri nodi.
In sintesi, l’algoritmo Raft è un algoritmo di consenso distribuito semplice ed efficace.
Grazie alla sua architettura leader-based e al meccanismo di timeout basato su un orologio interno, Raft è stato utilizzato con successo in molte applicazioni distribuite, come i sistemi di gestione di database, i sistemi di archiviazione di file e le piattaforme di elaborazione distribuita dei dati.
Come funziona una rete basata su Raft
Proviamo a dare una spiegazione semplificata di come funziona nel dettaglio una rete basata su Raft.
Ogni nodo della rete può trovarsi in tre stati diversi: Candidate, Leader, Follower.
- Candidate: è un candidato che richiede agli altri nodi i voti per diventare leader.
- Leader: si occupa di ricevere gli stati dal “mondo esterno” e propagarli verso gli altri nodi. È l’unico nodo della rete che può comunicare con i client.
- Follower: nodo generico della rete che replica gli stati ricevuti dal leader. Ogni follower può candidarsi a diventare leader quando il leader attuale risulta irraggiungibile.
Fasi di funzionamento RAFT
Il funzionamento di Raft può essere suddiviso in tre fasi: elezione del leader, replicazione dei log e applicazione dei comandi.
Elezione del leader
In partenza tutti i nodi della rete si trovano nello stato Follower ed hanno impostato un timeout random tra 150 e 300 ms entro il quale sono in attesa di un ping dal Leader.
Allo scadere del timeout un follower che non ha ricevuto un segnale di vita dal Leader si erge a Candidate e richiede agli altri nodi un voto per diventare il nuovo leader della rete. Se nessun candidato raggiunge la maggioranza dei voti, viene avviato un nuovo round di elezione.
Uno degli elementi chiave di Raft è il concetto di Term. Un term è un progressivo numerico che identifica in maniera univoca il periodo di tempo durante il quale un leader rimane al “comando”.
Ad ogni nuova elezione parte un nuovo term ed il suo identificativo viene usato per identificare gli stati attuali e gli stati successivi della rete. Ogni nodo memorizza il term corrente associato al suo stato e lo aggiorna, quando riceve nuove modifiche con un term successivo.
Replicazione dei log
La seconda fase dell’algoritmo Raft è la replicazione dei log. Una volta che un leader è stato eletto, il leader invia messaggi di log ai nodi della rete. I log contengono una lista di comandi che devono essere eseguiti da tutti i nodi della rete. Quando un nodo riceve un messaggio di log dal leader, replica il log e invia una conferma al leader. Una volta che il leader riceve la conferma da tutti i nodi, sa che il log è stato replicato con successo.
Applicazione dei comandi
La terza fase dell’algoritmo Raft è l’applicazione dei comandi. Una volta che il log è stato replicato in tutti i nodi della rete, il leader può inviare i comandi ai nodi per eseguirli. I comandi vengono eseguiti in ordine, garantendo che tutti i nodi eseguano gli stessi comandi nello stesso ordine.
Cerchiamo di capire meglio con un esempio.
Nel term 1 viene eletto il nodo 1 come leader e vengono inviati dai client delle modifiche.
Dopo tre operazioni il nodo 1 va fuori rete e non è più raggiungibile dai suoi follower, quindi, viene battezzato un nuovo term (il 2) ed il nodo 2 si erge a candidate e viene eletto leader. Ora sarà lui ad inviare i log delle operazioni agli altri nodi. Dopo una serie di operazioni eseguite nel term 2 il nodo 1 torna online, si rende conto che sta ricevendo delle operazioni dal nodo 3 con un term che è successivo a quello che ha impostato in locale e diventa follower. E così via.
Principali differenze tra Raft e Paxos
Gli algoritmi per il calcolo della data della Pasqua sono un argomento interessante e importante per la Chiesa cristiana e per molte altre applicazioni. Meeus è il più preciso e performante, mentre Conway e Gauss sono forse più semplici da comprendere.
La scelta dell’algoritmo ovviamente dipende dalle esigenze applicative e dalle capacità del programmatore.
Per un approfondimento
Paxos vs Raft: Have we reached consensus on distributed consensus?
Vantaggi e svantaggi di un sistema basato su Raft
Evidenziamo quelli che a nostro modo di vedere possono essere alcuni dei vantaggi e degli svantaggi di usare un sistema basato su algoritmo Raft.
Vantaggi:
- Raft è facile da capire e implementare. La sua logica è divisa in sotto problemi indipendenti e ha una chiara definizione delle responsabilità tra i server.
- Raft garantisce la coerenza tra i server. Ogni server ha lo stesso stato della macchina a stati e le stesse voci del log.
- Raft è fault-tollerant. Dato N è il numero totale di server della rete, può tollerare fino a (N-1)/2 down.
Svantaggi:
- Raft richiede una maggior quantità di comunicazione tra i suoi nodi. Il leader deve inviare costantemente segnali di alive agli altri server per mantenere la sua autorità e replicare le nuove voci del log.
Raft può avere dei tempi di latenza in caso di cambio del leader. Se il leader è down o viene isolato, ci vuole un certo tempo prima che un nuovo leader sia eletto e sia possibile sincronizzare i log su tutti i nodi.
Curiosità finale: Perchè il nome RAFT?
In molti fin dalla sua pubblicazione si sono chiesti ma cosa vuol dire Raft? È un acronimo? Come è stato scelto il nome finale? Ecco una piccola curiosità scovata in rete!
Proprio Ongaro ci dà una risposta pubblica , allegando anche le foto delle lavagne con i possibili candidati, dicendo che:
- Non è un acronimo, anche se avevano pensato alle parole ‘reliable’, ‘replicated’, ‘redundant’, e ‘fault-tolerant’.
- Doveva essere un nome che facesse pensare ai registri ed al loro utilizzo.
- Doveva essere un qualcosa che facesse pensare ad un modo per “scappare dall’isola di Paxos”.
Da qui la scelta di Raft, una “zattera” per portare gli algoritmi di consenso verso nuovi orizzonti.
Se anche tu vuoi occuparti di progetti di sviluppo IT di ultima generazione
dai un’occhiata alle nostre opportunità di lavoro e conosciamoci subito!
