Quindi, immaginiamo. Ci sono 5 gatti chiusi nella stanza, e per poter svegliare il proprietario, devono accordarsi tutti tra loro, perché possono aprire la porta solo con cinque di loro appoggiati sopra. Se uno dei gatti è il gatto di Schrödinger e gli altri gatti non sanno della sua decisione, sorge la domanda: "Come possono farlo?"
In questo articolo ti parlerò in termini semplici della componente teorica del mondo dei sistemi distribuiti e dei principi del loro funzionamento. Esaminerò anche superficialmente l'idea principale che sta alla base di Paxos.
Quando gli sviluppatori utilizzano infrastrutture cloud, vari database e lavorano in cluster con un gran numero di nodi, hanno la certezza che i dati saranno completi, sicuri e sempre disponibili. Ma dove sono le garanzie?
Essenzialmente, le garanzie che abbiamo sono garanzie del fornitore. Sono descritti nella documentazione come segue: "Questo servizio è abbastanza affidabile, ha un determinato SLA, non preoccuparti, tutto funzionerà in modo distribuito come previsto."
Tendiamo a credere nel meglio, perché ragazzi intelligenti di grandi aziende ci hanno assicurato che andrà tutto bene. Non ci poniamo la domanda: perché, in effetti, tutto questo può funzionare? Esiste una giustificazione formale per il corretto funzionamento di tali sistemi?
Ci sono andato di recente ed è stato molto ispirato da questo argomento. Le lezioni a scuola erano più simili a lezioni di calcolo che a qualcosa legato ai sistemi informatici. Ma è proprio così che un tempo sono stati dimostrati gli algoritmi più importanti che utilizziamo ogni giorno, senza nemmeno saperlo.
La maggior parte dei moderni sistemi distribuiti utilizza l'algoritmo di consenso di Paxos e le sue varie modifiche. La cosa più bella è che la validità e, in linea di principio, la possibilità stessa dell'esistenza di questo algoritmo può essere dimostrata semplicemente con carta e penna. In pratica, l’algoritmo viene utilizzato in sistemi di grandi dimensioni che funzionano su un numero enorme di nodi nel cloud.
Una leggera illustrazione di ciò che verrà discusso in seguito: il compito di due generaliDiamo un'occhiata per un riscaldamento .
Abbiamo due eserciti: rosso e bianco. Le truppe bianche hanno sede nella città assediata. Le truppe rosse guidate dai generali A1 e A2 si trovano su due lati della città. Il compito dei rossoneri è attaccare la città bianca e vincere. Tuttavia, l'esercito di ciascun generale rosso individualmente è più piccolo dell'esercito bianco.
Condizioni di vittoria per i rossi: entrambi i generali devono attaccare contemporaneamente per avere un vantaggio numerico sui bianchi. Per fare ciò, i generali A1 e A2 devono mettersi d’accordo tra loro. Se tutti attaccassero separatamente, i rossoneri perderebbero.
Per raggiungere un accordo, i generali A1 e A2 possono scambiarsi messaggeri attraverso il territorio della città bianca. Il messaggero può raggiungere con successo un generale alleato o essere intercettato dal nemico. Domanda: esiste una tale sequenza di comunicazioni tra i generali dai capelli rossi (la sequenza di invio di messaggeri da A1 ad A2 e viceversa da A2 ad A1), in cui è garantito che si accordino per un attacco all'ora X. Ecco, garanzie significano che entrambi i generali avranno la conferma inequivocabile che un alleato (un altro generale) attaccherà sicuramente all'ora stabilita X.
Supponiamo che A1 invii un messaggero ad A2 con il 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 conferma con il messaggio: “Sì, uccidiamo i bianchi oggi”. Ma ora il Generale A2 non sa se il suo messaggero è arrivato oppure no, non ha alcuna garanzia che l'attacco sarà simultaneo. Ora il Generale A2 ha nuovamente bisogno di conferme.
Se descriviamo ulteriormente la loro comunicazione, diventa chiaro che, indipendentemente dal numero di cicli di scambio di messaggi, non c'è modo di garantire che entrambi i generali abbiano ricevuto i loro messaggi (assumendo che uno dei messaggeri possa essere intercettato).
Il problema dei due generali è un ottimo esempio di un sistema distribuito molto semplice in cui sono presenti due nodi con comunicazione inaffidabile. Ciò significa che non abbiamo una garanzia al 100% che siano sincronizzati. Problemi simili verranno discussi solo su scala più ampia più avanti nell'articolo.
Introduciamo il concetto di sistemi distribuiti
Un sistema distribuito è un gruppo di computer (di seguito li chiameremo nodi) che possono scambiarsi messaggi. Ogni singolo nodo è una sorta di entità autonoma. Un nodo può elaborare attività da solo, ma per comunicare con altri nodi deve inviare e ricevere messaggi.
Come vengono implementati esattamente i messaggi, quali protocolli vengono utilizzati: questo non ci interessa in questo contesto. È importante che i nodi di un sistema distribuito possano scambiarsi dati tra loro inviando messaggi.
La definizione in sé non sembra molto complicata, ma dobbiamo tenere presente 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 potenzialmente concorrenti gli eventi che si verificano su due nodi diversi finché non avremo un chiaro ordine in cui si verificano questi eventi. Ma, di regola, non ce l'abbiamo.
- Nessun orologio globale. Non abbiamo un ordine chiaro degli eventi a causa della mancanza di un orologio globale. Nel mondo ordinario delle persone, siamo abituati al fatto di avere orologi e tempo assolutamente. Tutto cambia quando si parla di sistemi distribuiti. Anche gli orologi atomici ultraprecisi hanno una deriva e potrebbero esserci situazioni in cui non possiamo dire quale dei due eventi sia accaduto 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 durano per sempre. Il disco rigido potrebbe guastarsi, la macchina virtuale nel cloud potrebbe riavviarsi, la rete potrebbe lampeggiare e i messaggi andranno persi. Inoltre, potrebbero esserci situazioni in cui i nodi funzionano, ma allo stesso tempo funzionano contro il sistema. L'ultima classe di problemi ha persino ricevuto un nome separato: problema . L’esempio più popolare di sistema distribuito con questo problema è Blockchain. Ma oggi non considereremo questa particolare classe di problemi. Saremo interessati a situazioni in cui semplicemente uno o più nodi potrebbero fallire.
- Modelli di comunicazione (modelli di messaggistica) tra nodi. Abbiamo già stabilito che i nodi comunicano scambiandosi messaggi. Esistono due modelli di messaggistica ben noti: sincrono e asincrono.
Modelli di comunicazione tra nodi in sistemi distribuiti
Modello sincrono – sappiamo per certo che esiste un delta di tempo noto e finito durante il quale è garantito che un messaggio raggiunga da un nodo all’altro. Se questo tempo è passato e il messaggio non è arrivato, possiamo tranquillamente dire che il nodo ha fallito. In questo modello abbiamo tempi di attesa prevedibili.
Modello asincrono – nei modelli asincroni consideriamo che il tempo di attesa è finito, ma non esiste un tale delta di tempo dopo il quale possiamo garantire che il nodo ha fallito. Quelli. Il tempo di attesa per un messaggio da un nodo può essere arbitrariamente lungo. Questa è una definizione importante e ne parleremo ulteriormente.
Il concetto di consenso nei sistemi distribuiti
Prima di definire formalmente il concetto di consenso, consideriamo un esempio di una situazione in cui ne abbiamo bisogno, vale a dire: Replica della macchina a stati.
Abbiamo qualche 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 scriverà nel log, il suo compito diventa offrire questo valore a tutti gli altri nodi in modo che il log venga aggiornato su tutti i nodi e il sistema passi a un nuovo stato coerente. In questo caso è importante che i nodi siano d'accordo tra loro: tutti i nodi concordano che il nuovo valore proposto è corretto, tutti i nodi accettano questo valore e solo in questo caso tutti possono scrivere il nuovo valore nel log.
In altre parole: nessuno dei nodi ha obiettato di avere informazioni più rilevanti e il valore proposto non era corretto. L'accordo tra i nodi e l'accordo su un unico valore corretto accettato è consenso in un sistema distribuito. Successivamente parleremo degli algoritmi che consentono ad un sistema distribuito di garantire il raggiungimento del consenso.
Più formalmente, possiamo definire un algoritmo di consenso (o semplicemente un algoritmo di consenso) come una certa funzione che trasferisce un sistema distribuito dallo stato A allo stato B. Inoltre, questo stato è accettato da tutti i nodi e tutti i nodi possono confermarlo. A quanto pare, questo compito non è così banale come sembra a prima vista.
Proprietà dell'algoritmo di consenso
L’algoritmo di consenso deve avere tre proprietà affinché il sistema continui ad esistere e abbia qualche progresso nel passaggio da uno stato all’altro:
- Accordo – tutti i nodi correttamente funzionanti devono assumere lo stesso valore (negli articoli questa proprietà è chiamata anche proprietà di sicurezza). Tutti i nodi attualmente funzionanti (che non hanno fallito o perso il contatto con gli altri) devono raggiungere un accordo e accettare un valore comune finale.
È importante capire qui che i nodi del sistema distribuito che stiamo considerando vogliono essere d'accordo. Cioè, ora stiamo parlando di sistemi in cui qualcosa può semplicemente fallire (ad esempio, qualche nodo fallisce), ma in questo sistema non ci sono sicuramente nodi che lavorano deliberatamente contro altri (il compito dei generali bizantini). Grazie a questa proprietà, il sistema rimane coerente.
- Integrità — se tutti i nodi che funzionano correttamente offrono lo stesso valore v, il che significa che ogni nodo che funziona correttamente deve accettare questo valore v.
- Terminazione – tutti i nodi che funzionano correttamente prima o poi assumeranno un certo valore (proprietà liveness), che consente all’algoritmo di fare progressi nel sistema. Ogni singolo nodo che opera correttamente deve prima o poi accettare il valore finale e confermarlo: “Per me questo valore è vero, sono d’accordo con l’intero sistema”.
Un esempio di come funziona l'algoritmo di consenso
Mentre le proprietà dell'algoritmo potrebbero non essere del tutto chiare. Pertanto, illustreremo con un esempio quali fasi attraversa l'algoritmo di consenso più semplice in un sistema con un modello di messaggistica sincrona, in cui tutti i nodi funzionano come previsto, i messaggi non vengono persi e nulla si rompe (succede davvero?).
- Tutto inizia con una proposta di matrimonio (Propose). Supponiamo che un client si sia connesso a un nodo chiamato "Nodo 1" e abbia avviato una transazione, passando un nuovo valore al nodo - O. D'ora in poi chiameremo "Nodo 1" proporre. In qualità di proponente, il “Nodo 1” deve ora notificare all’intero sistema che ha nuovi dati e inviare messaggi a tutti gli altri nodi: “Guarda! Mi è venuto in mente il significato “O” e voglio scriverlo! Conferma che registrerai anche "O" nel tuo registro. "
- La fase successiva è la votazione per il valore proposto (votazione). Cosa serve? Può succedere che altri nodi abbiano ricevuto informazioni più recenti e dispongano di dati sulla stessa transazione.
Quando il nodo "Nodo 1" invia la sua proposta, gli altri nodi controllano i loro registri per i dati su questo evento. Se non ci sono contraddizioni, i nodi annunciano: “Sì, non ho altri dati per questo evento. Il valore “O” è l’ultima informazione che meritiamo”.In ogni altro caso, i nodi possono rispondere al “Nodo 1”: “Ascolta! Ho dati più recenti su questa transazione. Non 'O', ma qualcosa di meglio."
Nella fase di votazione, i nodi prendono una decisione: o accettano tutti lo stesso valore, oppure uno di loro vota contro, indicando che ha dati più recenti.
- Se la votazione ha avuto successo e tutti erano favorevoli, il sistema passa a una nuova fase: accettazione del valore. Il “Nodo 1” raccoglie tutte le risposte degli altri nodi e riporta: “Tutti erano d'accordo sul valore “O”! Adesso dichiaro ufficialmente che “O” è il nostro nuovo significato, uguale per tutti! Scrivilo nel tuo libretto, non dimenticarlo. Scrivilo nel tuo diario!”
- I restanti nodi inviano conferma (Accepted) di aver annotato il valore “O”; durante questo tempo non è arrivato nulla di nuovo (una sorta di commit a due fasi). Dopo questo significativo evento, riteniamo che l'operazione distribuita sia completata.
Pertanto, l'algoritmo di consenso in un caso semplice consiste di quattro passaggi: proporre, votare (votare), accettare (accettare), confermare l'accettazione (accettato).
Se ad un certo punto non siamo riusciti a raggiungere un accordo, l'algoritmo ricomincia, tenendo conto delle informazioni fornite dai nodi che si sono rifiutati di confermare il valore proposto.
Algoritmo di consenso in un sistema asincrono
Prima tutto andava liscio, perché si parlava di un modello di messaggistica sincrona. Ma sappiamo che nel mondo moderno siamo abituati a fare tutto in modo asincrono. Come funziona un algoritmo simile in un sistema con un modello di messaggistica asincrono, dove riteniamo che il tempo di attesa per una risposta da un nodo possa essere arbitrariamente lungo (a proposito, il guasto di un nodo può anche essere considerato un esempio quando un nodo può rispondere per un tempo arbitrariamente lungo).
Ora che sappiamo come funziona in linea di principio l’algoritmo di consenso, una domanda per quei lettori curiosi che sono arrivati fin qui: quanti nodi in un sistema di N nodi con un modello di messaggio asincrono possono fallire affinché il sistema possa ancora raggiungere il consenso?
La risposta corretta e la giustificazione sono dietro lo spoiler.La risposta corretta è: 0. Se anche un solo nodo in un sistema asincrono fallisce, il sistema non sarà in grado di raggiungere il consenso. Questa affermazione è dimostrata nel teorema FLP, ben noto in certi ambienti (1985, Fischer, Lynch, Paterson, link all’originale alla fine dell’articolo): “L’impossibilità di raggiungere un consenso distribuito se almeno un nodo fallisce .”
Ragazzi, allora abbiamo un problema, siamo abituati a tutto in modo asincrono. Ed eccolo qui. Come continuare a vivere?
Stavamo solo parlando di teoria, di matematica. Cosa significa "il consenso non può essere raggiunto", traducendo dal linguaggio matematico al nostro: ingegneria? Ciò significa che “non è sempre possibile realizzarlo”, vale a dire C’è un caso in cui il consenso non è raggiungibile. Che razza di caso è questo?
Questa è esattamente la violazione della proprietà di vivacità descritta sopra. Non abbiamo un accordo comune e il sistema non può progredire (non può completarsi in un tempo finito) nel caso in cui non abbiamo una risposta da tutti i nodi. Perché in un sistema asincrono non abbiamo tempi di risposta prevedibili e non possiamo sapere se un nodo si è bloccato o se sta semplicemente impiegando molto tempo per rispondere.
Ma in pratica possiamo trovare una soluzione. Lascia che il nostro algoritmo possa funzionare a lungo in caso di guasti (potenzialmente può funzionare indefinitamente). Ma nella maggior parte delle situazioni, quando la maggior parte dei nodi funziona correttamente, avremo progressi nel sistema.
In pratica si tratta di modelli di comunicazione parzialmente sincroni. La sincronia parziale è intesa come segue: nel caso generale, abbiamo un modello asincrono, ma viene introdotto formalmente un certo concetto di “tempo di stabilizzazione globale” di un certo punto nel tempo.
Questo momento potrebbe non arrivare per molto tempo, ma un giorno arriverà. Suonerà la sveglia virtuale, e da quel momento potremo prevedere il delta temporale per il quale arriveranno i messaggi. Da questo momento in poi il sistema passa da asincrono a sincrono. In pratica si tratta proprio di sistemi di questo tipo.
L'algoritmo di Paxos risolve i problemi di consenso
è una famiglia di algoritmi che risolvono il problema del consenso per sistemi parzialmente sincroni, soggetti alla possibilità che alcuni nodi possano fallire. L'autore di Paxos lo è . Nel 1989 propose una prova formale dell'esistenza e della correttezza dell'algoritmo.
Ma la dimostrazione si è rivelata tutt’altro che banale. La prima pubblicazione è stata pubblicata solo nel 1998 (33 pagine) descrivendo l'algoritmo. Si è scoperto che era estremamente difficile da capire e nel 2001 è stata pubblicata una spiegazione dell'articolo, che occupava 14 pagine. Il volume delle pubblicazioni è dato per dimostrare che in realtà il problema del consenso non è affatto semplice e dietro tali algoritmi si nasconde un'enorme mole di lavoro delle persone più intelligenti.
È interessante notare che lo stesso Leslie Lamport ha notato nella sua conferenza che nel secondo articolo esplicativo c'è un'affermazione, una riga (non ha specificato quale), che può essere interpretata in modi diversi. E per questo motivo, un gran numero di moderne implementazioni di Paxos non funzionano del tutto correttamente.
Un’analisi dettagliata del lavoro di Paxos richiederebbe più di un articolo, quindi cercherò di trasmettere molto brevemente l’idea principale dell’algoritmo. Nei link alla fine del mio articolo troverai materiale per approfondire questo argomento.
Ruoli a Paxos
L'algoritmo di Paxos ha il concetto di ruoli. Consideriamone tre principali (ci sono modifiche con ruoli aggiuntivi):
- Proponenti (i termini possono essere utilizzati anche: leader o coordinatori). Questi sono i ragazzi che apprendono nuovi valori dall'utente e assumono il ruolo di leader. Il loro compito è lanciare una serie di proposte per un nuovo valore e coordinare ulteriori azioni dei nodi. Inoltre, Paxos consente la presenza di più leader in determinate situazioni.
- Accettatori (elettori). Questi sono i nodi che votano per accettare o rifiutare un particolare valore. Il loro ruolo è molto importante, perché da loro dipende la decisione: a quale stato andrà (o meno) il sistema dopo la fase successiva dell’algoritmo di consenso.
- Gli studenti. Nodi che semplicemente accettano e scrivono il nuovo valore accettato quando lo stato del sistema è cambiato. Non prendono decisioni, ricevono semplicemente i dati e possono trasmetterli all'utente finale.
Un nodo può combinare diversi ruoli in diverse situazioni.
Il concetto di quorum
Supponiamo di avere un sistema di N nodi E di loro il massimo F i nodi potrebbero fallire. Se i nodi F falliscono, allora dobbiamo avere almeno 2P+1 nodi accettori.
Ciò è necessario affinché abbiamo sempre la maggioranza, anche nella situazione peggiore, di nodi “buoni” che funzionino correttamente. Questo è FA + 1 nodi "buoni" che hanno accettato e il valore finale sarà accettato. Altrimenti, potrebbe verificarsi una situazione in cui i nostri diversi gruppi locali assumono significati diversi e non riescono ad accordarsi tra loro. Pertanto, per vincere il voto abbiamo bisogno della maggioranza assoluta.
L'idea generale di come funziona l'algoritmo di consenso di Paxos
L’algoritmo di Paxos prevede due grandi fasi, a loro volta suddivise in due step ciascuna:
- Fase 1a: preparazione. Durante la fase di preparazione, il leader (proponente) informa tutti i nodi: “Stiamo iniziando una nuova fase di votazione. Abbiamo un nuovo ciclo. Il numero di questo round è il n. Ora inizieremo a votare." Per ora segnala semplicemente l'inizio di un nuovo ciclo, ma non riporta un nuovo valore. Il compito di questa fase è avviare un nuovo round e informare tutti del proprio numero univoco. Il numero tondo è importante, deve essere un valore maggiore di tutti i numeri di votazione precedenti di tutti i leader precedenti. Perché è grazie al numero tondo che gli altri nodi del sistema capiranno quanto sono recenti i dati del leader. È probabile che altri nodi abbiano già i risultati delle votazioni di turni molto successivi e diranno semplicemente al leader che è in ritardo.
- Fase 1b: Promessa. Quando i nodi accettanti ricevono il numero della nuova fase di votazione, sono possibili due risultati:
- Il numero n del nuovo voto è maggiore del numero di qualsiasi voto precedente a cui ha partecipato l'accettante. Quindi l'accettante promette al leader che non parteciperà ad altri voti con un numero inferiore a n. Se l'accettante ha già votato per qualcosa (cioè ha già accettato un valore nella seconda fase), allora allega alla sua promessa il valore accettato e il numero del voto a cui ha partecipato.
- Altrimenti, se l'accettante è già a conoscenza del voto con il numero più alto, può semplicemente ignorare la fase di preparazione e non rispondere al leader.
- Fase 2a: Accetta. Il leader deve attendere una risposta dal quorum (la maggior parte dei nodi del sistema) e, se viene ricevuto il numero richiesto di risposte, ha due opzioni per lo sviluppo degli eventi:
- Alcuni accettanti hanno inviato valori per i quali avevano già votato. In questo caso, il leader seleziona dal voto il valore con il numero massimo. Chiamiamo questo valore x e invia un messaggio a tutti i nodi come: "Accetta (n, x)", dove il primo valore è il numero di voto dal proprio passaggio Proponi e il secondo valore è ciò per cui tutti si sono riuniti, cioè. il valore per il quale effettivamente votiamo.
- Se nessuno degli accettanti ha inviato valori, ma ha semplicemente promesso di votare in questo turno, il leader può invitarli a votare per il loro valore, il valore per il quale è diventato leader in primo luogo. Chiamiamolo y. Invia un messaggio a tutti i nodi come: “Accetta (n, y)”, simile al risultato precedente.
- Fase 2b: Accettata. Inoltre, i nodi accettanti, dopo aver ricevuto il messaggio “Accetta(...)” dal leader, sono d'accordo con esso (inviano conferma a tutti i nodi che sono d'accordo con il nuovo valore) solo se non ne hanno promesso alcuni (altri)) leader di partecipare alla votazione con il numero tondo n' > n, altrimenti ignorano la richiesta di conferma.
Se la maggior parte dei nodi ha risposto al leader e tutti hanno confermato il nuovo valore, il nuovo valore viene considerato accettato. Evviva! Se la maggioranza non viene raggiunta o ci sono nodi che rifiutano di accettare il nuovo valore, allora tutto ricomincia da capo.
Ecco come funziona l'algoritmo di Paxos. Ognuna di queste fasi ha molte sottigliezze, praticamente non abbiamo considerato vari tipi di guasti, problemi di più leader e molto altro, ma lo scopo di questo articolo è solo quello di introdurre il lettore al mondo del calcolo distribuito ad alto livello.
Vale anche la pena notare che Paxos non è l'unico nel suo genere, esistono altri algoritmi, ad esempio , ma questo è un argomento per un altro articolo.
Collegamenti a materiali per ulteriori approfondimenti
Livello principiante:
- , Preethi Kasireddy, articolo del blog su Medium
- , Adi Kancherla, articolo del blog su Medium
- , Ittai Abraham, blog
- , Ittai Abraham, articolo del blog
Livello di Leslie Lamport:
- , Fischer, Lynch e Paterson, documento di ricerca, 1985
- , Leslie Lamport, documento di ricerca, 1998
- , Leslie Lamport, documento di ricerca, 2001
Fonte: habr.com