🥇Il gatto di Schrödinger senza scatola: il problema del consenso nei sistemi distribuiti

Immagina. In una stanza ci sono 5 gatti rinchiusi, e per andare a svegliare il padrone devono prima accordarsi tutti insieme, poiché possono aprire la porta solo in cinque spingendosi contro di essa. Se uno dei gatti è il gatto di Schrödinger e gli altri non sono a conoscenza della sua decisione, sorge la domanda: "Come possono farlo?"

In questo articolo spiegherò in modo semplice la parte teorica del mondo dei sistemi distribuiti e i principi del loro funzionamento. Inoltre, esaminerò superficialmente l'idea principale alla base del Paxos.

Quando gli sviluppatori utilizzano infrastrutture cloud, diverse basi di dati e lavorano in cluster di numerosi nodi, sono certi che i dati saranno interi, sicuri e sempre accessibili. Ma da dove provengono le garanzie?

Di fatto, le garanzie che abbiamo sono quelle fornite dal fornitore. Vengono descritte nella documentazione all'incirca in questo modo: "Questo servizio è sufficientemente affidabile, ha un SLA definito, non preoccuparti, tutto funzionerà distribuito come ti aspetti".

Tendiamo a credere nel meglio, poiché i grandi esperti delle grandi aziende ci hanno assicurato che tutto andrà per il verso giusto. Non ci poniamo la domanda: perché, per l'appunto, questo dovrebbe funzionare? C'è una qualche giustificazione formale per la correttezza del funzionamento di tali sistemi?

Recentemente sono stato a una scuola di calcolo distribuito e sono stato molto ispirato da questo argomento. Le lezioni nella scuola assomigliavano più a corsi di analisi matematica piuttosto che a qualcosa legato a sistemi computerizzati. Ma è esattamente così che un tempo venivano dimostrati i più importanti algoritmi che utilizziamo ogni giorno, senza neanche rendercene conto.

Nella maggior parte dei moderni sistemi distribuiti viene utilizzato l'algoritmo di consenso Paxos e le sue varie modifiche. La cosa più interessante è che la validità e, in linea di principio, la possibilità stessa di esistenza di questo algoritmo possono essere dimostrate semplicemente con una penna e della carta. Nel pratico, però, l'algoritmo è applicato in grandi sistemi che operano su un numero elevato di nodi nelle nuvole.

Un'illustrazione leggera di ciò di cui si parlerà in seguito: il problema dei due generaliPer riscaldarci, analizziamo il problema dei due generali.

Ci sono due eserciti: uno rosso e uno bianco. Le forze bianche sono basate nella città assediata. Le forze rosse, comandate dai generali A1 e A2, si trovano ai due lati della città. L'obiettivo dei rossi è attaccare la città bianca e vincere. Tuttavia, l'esercito di ciascun generale rosso è più piccolo rispetto a quello dei bianchi.

Le condizioni per la vittoria dei rossi: entrambi i generali devono attaccare simultaneamente per avere un vantaggio numerico sui bianchi. Per questo, i generali A1 e A2 devono mettersi d'accordo tra di loro. Se ciascuno attacca separatamente, i rossi perderanno.

Per mettersi d'accordo, i generali A1 e A2 possono inviare messaggeri l'uno all'altro attraverso il territorio della città bianca. Un messaggero può arrivare con successo al generale alleato o può essere intercettato dal nemico. La domanda è: esiste una sequenza di comunicazioni tra i generali rossi (sequenza di invio dei messaggeri da A1 a A2 e viceversa da A2 a A1), in cui possano garantire di concordare l'attacco all'ora X. Qui, per garanzie si intende che entrambi i generali abbiano una conferma inequivocabile che l'alleato (l'altro generale) attaccherà sicuramente all'ora X.

Supponiamo che A1 invii un messaggero a A2 con il seguente messaggio: «Attacchiamo oggi a mezzanotte!». Il generale A1 non può attaccare senza la conferma del generale A2. Se il messaggero di A1 è arrivato, il generale A2 invia una conferma con il messaggio: «Sì, attacchiamo oggi, abbattiamo i bianchi». Ma ora il generale A2 non sa se il suo messaggero sia arrivato o meno, non ha garanzie che l'attacco avverrà simultaneamente. Ora il generale A2 ha bisogno nuovamente di una conferma.

Se approfondiamo ulteriormente la loro comunicazione, scopriremo che, per quanti cicli di scambio messaggi ci siano, non c'è modo di garantire che entrambi i generali siano stati informati della ricezione dei loro messaggi (a condizione che uno qualsiasi dei messaggeri possa essere intercettato).

Il problema dei due generali è un'ottima illustrazione di un sistema distribuito molto semplice, dove ci sono due nodi con comunicazione inaffidabile. Quindi non abbiamo la garanzia del 100% che essi si sincronizzino. Si parlerà di problemi simili su una scala molto più ampia più avanti nell'articolo.

Introduciamo il concetto di sistemi distribuiti

Un sistema distribuito è un insieme di computer (da ora in poi chiamati nodi) che possono scambiarsi messaggi. Ogni nodo è un'entità autonoma. Un nodo può elaborare compiti in modo indipendente, ma per interagire con altri nodi deve inviare e ricevere messaggi.

Come vengono implementati i messaggi e quali protocolli vengono utilizzati non ci interessa in questo contesto. È importante che i nodi di un sistema distribuito possano scambiarsi dati inviando messaggi.

La definizione stessa non sembra molto complessa, ma bisogna considerare che un sistema distribuito ha una serie di attributi che saranno importanti per noi.

Attributi dei sistemi distribuiti

Concorrenza – la possibilità che si verifichino eventi simultanei o concorrenti nel sistema. Inoltre, considereremo che gli eventi che si verificano su due nodi diversi sono potenzialmente concorrenti fino a quando non abbiamo un ordine definitivo di insorgenza di questi eventi. E, come regola, di solito non abbiamo tale ordine.
Assenza di orologi globali. Non abbiamo un ordine preciso degli eventi a causa dell'assenza di orologi globali. Nel mondo normale degli esseri umani, siamo abituati a avere orologi e tempo definito. Tutto cambia quando si parla di sistemi distribuiti. Anche gli orologi atomici più precisi presentano un drift, e ci possono essere situazioni in cui non possiamo dire quale dei due eventi sia avvenuto per primo. Pertanto, non possiamo nemmeno fare affidamento sul tempo.
Guasto indipendente dei nodi del sistema. C'è un altro problema: qualcosa può andare storto semplicemente perché i nostri nodi non sono eterni. Un disco rigido può guastarsi, una macchina virtuale nel cloud può riavviarsi, la rete può lampeggiare e i messaggi possono andare persi. Inoltre, possono verificarsi situazioni in cui i nodi funzionano, ma lavorano contro il sistema. L'ultimo classe di problemi ha persino ricevuto un nome specifico: problema dei generali bizantini. Il più popolare esempio di un sistema distribuito con tale problema è il Blockchain. Ma oggi non esamineremo questa particolare classe di problemi. Ci interesseranno situazioni in cui uno o più nodi possono semplicemente guastarsi.
Modelli di comunicazione (modelli di scambio di messaggi) tra nodi. Abbiamo già stabilito che i nodi comunicano tramite scambi di messaggi. Ci sono due modelli di scambio di messaggi ben noti: sincrono e asincrono.

Modelli di comunicazione tra nodi in sistemi distribuiti

Modello sincrono – sappiamo con certezza che esiste una delta di tempo finita, entro la quale il messaggio arriva garantito da un nodo all'altro. Se questo tempo scade e il messaggio non è arrivato, possiamo affermare con certezza che il nodo è fuori uso. In questo modello abbiamo un tempo di attesa prevedibile.

Modello asincrono – nei modelli asincroni consideriamo che il tempo di attesa sia finito, ma non esiste una delta di tempo dopo la quale possiamo garantire che il nodo sia fuori uso. Cioè, il tempo di attesa per un messaggio da un nodo può essere arbitrariamente lungo. Questa è una definizione importante, e ne parleremo in seguito.

Il concetto di consenso nei sistemi distribuiti

Prima di definire formalmente il concetto di consenso, consideriamo un esempio di situazione in cui è necessario, ovvero – Replica di macchine di stato.

Abbiamo un certo registro distribuito. Vorremmo che fosse coerente e contenesse dati identici su tutti i nodi del sistema distribuito. Quando uno dei nodi apprende un nuovo valore che intende registrare nel registro, il suo compito è proporre questo valore a tutti gli altri nodi, affinché il registro venga aggiornato su tutti i nodi e il sistema passi a un nuovo stato coerente. È importante che i nodi raggiungano un accordo tra loro: tutti i nodi devono concordare che il nuovo valore proposto sia corretto, tutti i nodi devono accettare tale valore, e solo allora tutti possono registrare il nuovo valore nel registro.

In altre parole: nessuno dei nodi ha obiettato di avere informazioni più aggiornate e che il valore proposto fosse errato. L'accordo tra i nodi e il consenso su un unico valore corretto accettato è ciò che costituisce il consenso in un sistema distribuito. Successivamente parleremo degli algoritmi che consentono a un sistema distribuito di raggiungere il consenso in modo garantito.

In modo più formale, possiamo definire un algoritmo di consenso (o semplicemente algoritmo di consenso) come una funzione che trasforma un sistema distribuito da uno stato A a uno stato B. Questo stato deve essere accettato da tutti i nodi, e tutti i nodi devono poterlo convalidare. A quanto pare, questo compito non è affatto triviale come potrebbe sembrare a prima vista.

Proprietà dell'algoritmo di consenso

L'algoritmo di consenso deve possedere tre proprietà affinché il sistema continui a esistere e faccia progressi nel passaggio da uno stato a un altro:

Accordo – tutti i nodi funzionanti correttamente devono accettare lo stesso valore (in letteratura, questa proprietà è anche nota come safety property). Tutti i nodi attualmente operativi (che non sono guasti e non hanno perso la connessione con gli altri) devono raggiungere un accordo e accettare un valore comune finale.
È importante comprendere che i nodi nel sistema distribuito che stiamo considerando desiderano accordarsi. Stiamo parlando di sistemi in cui qualcosa può semplicemente fallire (ad esempio, un nodo può smettere di funzionare), ma in questo sistema non ci sono nodi che lavorano intenzionalmente contro gli altri (il problema dei generali bizantini). Grazie a questa proprietà, il sistema rimane consistente.
Integrità — se tutti i nodi funzionanti correttamente offrono lo stesso valore v, significa che ogni nodo funzionante correttamente deve accettare questo valore v.
Terminazione – tutti i nodi funzionanti correttamente alla fine accetteranno un certo valore (proprietà di vitalità), permettendo all'algoritmo di fare progressi nel sistema. Ogni singolo nodo funzionante correttamente deve, prima o poi, accettare il valore finale e confermarlo: "Per me, questo valore è vero, sono d'accordo con l'intero sistema".

Esempio di funzionamento dell'algoritmo di consenso

Al momento le proprietà dell'algoritmo potrebbero non essere del tutto chiare. Pertanto, illustriamo con un esempio quali fasi attraversa il più semplice algoritmo di consenso in un sistema con un modello di scambio messaggi sincrono, dove tutti i nodi funzionano correttamente, i messaggi non vanno persi e non ci sono guasti (può davvero succedere?).

Tutto inizia con una proposta (Propose). Supponiamo che un cliente si sia connesso al nodo chiamato "Nodo 1" e abbia avviato una transazione, inviando al nodo un nuovo valore – 0. Da questo momento in poi, il "Nodo 1" sarà chiamato proposer. Come proposer, il "Nodo 1" deve ora informare l'intero sistema che ha nuovi dati, e invia a tutti gli altri nodi un messaggio: "Guardate! Ho ricevuto il valore '0' e voglio memorizzarlo! Vi prego di confermare che anche voi memorizzerete '0' nel vostro registro."
La fase successiva è il voto sul valore proposto (Voting). A cosa serve? Può accadere che ad altri nodi sia arrivata un'informazione più recente e che abbiano dati su questa stessa transazione.

Quando il nodo "Nodo 1" invia la sua proposta, gli altri nodi controllano nei loro registri i dati relativi a questo evento. Se non ci sono contraddizioni, i nodi dichiarano: "Sì, non ho altri dati su questo evento. Il valore 'O' è l'informazione più recente che abbiamo ottenuto."
In qualsiasi altro caso, i nodi possono rispondere a "Nodo 1": "Ascolta! Ho dati più aggiornati su questa transazione. Non 'O', ma qualcosa di meglio."
Nella fase di voto, i nodi arrivano a una decisione: o tutti accettano un valore unico, oppure qualcuno di loro vota contro, indicando di avere dati più aggiornati.
Se il turno di voto ha avuto successo e tutti hanno votato 'sì', il sistema passa a una nuova fase: l'accettazione del valore (Accept). "Nodo 1" raccoglie tutte le risposte degli altri nodi e annuncia: "Tutti hanno concordato sul valore 'O'! Ora dichiaro ufficialmente che 'O' è il nostro nuovo valore, unico per tutti! Annotatelo, non dimenticatelo. Scrivetelo nel vostro registro!"
Gli altri nodi inviano una conferma (Accepted) che hanno registrato il valore "O"; nel frattempo non sono arrivate nuove informazioni (una sorta di commit a due fasi). Dopo questo significativo evento, consideriamo che la transazione distribuita sia stata completata.

Pertanto, l'algoritmo di consenso, in un caso semplice, consiste in quattro passaggi: propose, voting, accept, accepted.

Se in qualche fase non siamo riusciti a raggiungere un consenso, l'algoritmo riparte da capo, tenendo conto delle informazioni fornite dai nodi che si sono rifiutati di confermare il valore proposto.

L'algoritmo di consenso in un sistema asincrono

Fino a questo punto, tutto è andato liscio, poiché si trattava di un modello di scambio messaggi sincrono. Ma sappiamo che nel mondo moderno siamo abituati a fare tutto in modo asincrono. Come funziona quindi un algoritmo simile in un sistema con un modello di scambio messaggi asincrono, dove riteniamo che il tempo di attesa per una risposta da un nodo possa essere indefinito (tra l'altro, il guasto di un nodo può essere vista anche come un esempio, in cui un nodo può rispondere dopo un tempo indefinito).

Ora che sappiamo come funziona, in linea di principio, l'algoritmo di consenso, la domanda per quei lettori curiosi che sono arrivati fino a questo punto è: quanti nodi in un sistema di N nodi con un modello di messaggistica asincrona possono guastarsi affinché il sistema possa comunque raggiungere il consenso?

La risposta corretta e la motivazione sono nel seguito.La risposta corretta: 0. Se almeno un nodo in un sistema asincrono si guasta, il sistema non sarà in grado di raggiungere il consenso. Questa affermazione è dimostrata nel noto teorema FLP (1985, Fischer, Lynch, Paterson, riferimento originale alla fine dell'articolo): «L'impossibilità di raggiungere un consenso distribuito in caso di guasto di almeno un nodo».

Ragazzi, allora abbiamo un problema, siamo abituati a pensare che tutto sia asincrono. E ora ci troviamo in questa situazione. Come possiamo procedere?

Abbiamo appena parlato di teoria, di matematica. Cosa significa «il consenso non può essere raggiunto» traducendo dal linguaggio matematico al nostro - ingegneristico? Significa che «non sempre può essere raggiunto», ossia esiste un caso in cui il consenso non è raggiungibile. Ma qual è questo caso?

Questo rappresenta proprio una violazione della proprietà di liveness descritta sopra. Non abbiamo un consenso comune e il sistema non può fare progressi (non può terminare in un tempo finito) quando non riceviamo risposta da tutti i nodi. Poiché in un sistema asincrono non abbiamo un tempo di risposta prevedibile, non possiamo sapere se un nodo è guasto o sta semplicemente rispondendo lentamente.

Ma nella pratica possiamo trovare una soluzione. Diciamo che il nostro algoritmo può funzionare a lungo in caso di guasti (potenzialmente può operare all'infinito). Tuttavia, nella maggior parte delle situazioni, quando la maggior parte dei nodi funziona correttamente, avremo dei progressi nel sistema.

Nella pratica, affrontiamo modelli di comunicazione parzialmente sincroni. La parziale sincronia si intende nel senso che, in generale, abbiamo un modello asincrono, ma viene formalmente introdotto un concetto di "tempo di stabilizzazione globale" in un certo momento.

Questo momento potrebbe non arrivare per lungo tempo, ma un giorno dovrà arrivare. Suonerà la sveglia virtuale, e da quel momento saremo in grado di prevedere la delta di tempo che intercorre affinché i messaggi arrivino. Da quel momento il sistema passa da asincrono a sincrono. Nella pratica, ci confrontiamo proprio con questi sistemi.

L'algoritmo Paxos risolve problemi di consenso

Paxos è una famiglia di algoritmi che risolvono il problema del consenso per sistemi parzialmente sincroni, a condizione che alcuni nodi possano andare offline. L'autore del Paxos è Leslie Lamport. Ha proposto una dimostrazione formale dell'esistenza e correttezza dell'algoritmo nel 1989.

Ma la dimostrazione si rivelò tutt’altro che banale. La prima pubblicazione è stata rilasciata solo nel 1998 (33 pagine) con la descrizione dell'algoritmo. Si è rivelata estremamente complessa da comprendere, e nel 2001 è stata pubblicata una spiegazione dell'articolo che ha occupato 14 pagine. I volumi delle pubblicazioni sono forniti per dimostrare che in realtà il problema del consenso è tutt'altro che semplice, e dietro a questi algoritmi ci sono enormi fatiche delle menti più brillanti.

È interessante notare che lo stesso Leslie Lamport nella sua lezione ha osservato che nel secondo articolo esplicativo c'è un'affermazione, una riga (non specificata quale), che può essere interpretata in vari modi. A causa di ciò, un gran numero di implementazioni moderne di Paxos non funzionano in modo del tutto corretto.

Un'analisi dettagliata del funzionamento del Paxos richiederebbe più di un articolo, quindi cercherò di trasmettere molto brevemente l'idea principale dell'algoritmo. Nei link alla fine del mio articolo troverete materiale per un ulteriore approfondimento su questo argomento.

Ruoli in Paxos

Nell'algoritmo Paxos esiste il concetto di ruoli. Consideriamo i tre principali (esistono modifiche con ruoli aggiuntivi):

Proposers (possono essere utilizzati anche i termini: leader o coordinatori). Sono i ragazzi che apprendono un nuovo valore dall'utente e assumono il ruolo di leader. Il loro compito è avviare un round di proposta di un nuovo valore e coordinare le ulteriori azioni dei nodi. Paxos consente la presenza di più leader in alcune situazioni.
Acceptors (Voters). Sono nodi che votano per l'accettazione o il rifiuto di un determinato valore. Il loro ruolo è molto importante, poiché da loro dipende la decisione: in quale stato passerà (o non passerà) il sistema dopo ogni fase dell'algoritmo di consenso.
Apprendenti. Nodi che semplicemente accettano e registrano il nuovo valore accettato quando lo stato del sistema cambia. Non prendono decisioni, ricevono solo dati e possono restituirli all'utente finale.

Un nodo può assumere più ruoli in diverse situazioni.

Il concetto di quoro

Supponiamo di avere un sistema di N nodi. E di questi un massimo di F nodi può guastarsi. Se F nodi si guastano, significa che nel cluster devono esserci almeno 2F + 1 nodi acceptor.

Questo è necessario affinché anche nella peggiore situazione i nodi "buoni", che funzionano correttamente, abbiano la maggioranza. Cioè, F + 1 “buoni” nodi che hanno acconsentito, e il valore finale sarà accettato. Altrimenti, potrebbe verificarsi una situazione in cui i nostri diversi gruppi locali accettano valori diversi e non riescono a mettersi d'accordo. Pertanto, abbiamo bisogno di una maggioranza assoluta per vincere la votazione.

L'idea generale del funzionamento dell'algoritmo di consenso Paxos

L'algoritmo Paxos prevede due fasi principali, che a loro volta sono suddivise in due passaggi ciascuna:

Fase 1a: Prepare. Durante la fase di preparazione, il leader (proposer) comunica a tutti i nodi: «Iniziamo una nuova fase di votazione. Abbiamo un nuovo turno. Il numero di questo turno è n. Ora iniziamo a votare». In questo momento, sta solo annunciando l'inizio di un nuovo ciclo, ma non sta rivelando un nuovo valore. L'obiettivo di questa fase è avviare un nuovo turno e comunicare a tutti il suo numero unico. Il numero del turno è importante, deve essere un valore superiore a tutti i numeri di votazione precedenti provenienti da tutti i leader passati. Infatti, grazie al numero del turno, gli altri nodi nel sistema capiranno quanto siano recenti i dati del leader. Probabilmente, gli altri nodi hanno già risultati di votazione di turni molto più recenti e informeranno semplicemente il leader che è rimasto indietro.
Fase 1b: Promessa. Quando i nodi-acceptor hanno ricevuto il numero del nuovo round di votazione, ci sono due possibili esiti:
- Il numero n della nuova votazione è maggiore di quello di qualsiasi votazione precedente a cui ha partecipato l'accettore. In tal caso, l'accettore invia al leader una promessa di non partecipare più a votazioni con numeri inferiori a n. Se l'accettore ha già votato per qualcosa (ossia è già nella seconda fase e ha accettato un certo valore), aggiunge alla sua promessa il valore accettato e il numero della votazione a cui ha partecipato.
- In caso contrario, se l'accettore è già a conoscenza di una votazione con un numero maggiore, può semplicemente ignorare la fase di preparazione e non rispondere al leader.
Fase 2a: Accettare. Il leader deve attendere una risposta da parte del quorum (maggioranza dei nodi nel sistema) e, se riceve il numero necessario di risposte, ha due possibili sviluppi:
- Alcuni degli acceptor hanno inviato valori per cui hanno già votato. In questo caso, il leader sceglie un valore dalla votazione con il numero massimo. Chiamiamo questo valore x e invia a tutti i nodi un messaggio del tipo: «Accept (n, x)», dove il primo valore è il numero di votazione dal suo stesso passo Propose, e il secondo valore è ciò per cui ci si è riuniti, cioè il valore su cui stiamo votando.
- Se nessuno degli acceptor ha inviato valori, ma hanno solo promesso di votare in questo round, il leader può proporre loro di votare per il proprio valore, quello per cui è diventato leader. Chiamiamolo y. Invia a tutti i nodi un messaggio del tipo: «Accept (n, y)», in analogia con il precedente esito.
Fase 2b: Accettato. Successivamente, i nodi-acceptor, al ricevimento del messaggio «Accept(…)» dal leader, concordano con lui (inviando a tutti i nodi una conferma che sono d'accordo con il nuovo valore) solo se non hanno promesso a un (altro) leader di partecipare alle votazioni con il numero di round n' > n, altrimenti ignorano la richiesta di conferma.
Se la maggioranza dei nodi risponde al leader e tutti confermano il nuovo valore, allora il nuovo valore è considerato accettato. Hurra! Se invece non si raggiunge la maggioranza o ci sono nodi che rifiutano di accettare il nuovo valore, tutto ricomincia da capo.

Ecco come funziona l'algoritmo Paxos. Ciascuna di queste fasi presenta molte sfumature; non abbiamo praticamente considerato i vari tipi di guasti, i problemi con più leader e molto altro, ma l'obiettivo di questo articolo è solo quello di dare al lettore un'introduzione a livello alto al mondo del calcolo distribuito.

È anche importante notare che Paxos non è l'unico del suo genere; ci sono altri algoritmi, per esempio, Raft, ma questo è già un argomento per un altro articolo.