Paxos & amp; Protocols de consens de la bassa

Paxos i Balsa són dos protocols de consens coneguts que existeixen des de fa molt de temps i que continuen sent vitals per entendre la replicació de màquines estatals en sistemes informàtics distribuïts. Paxos és en realitat una família de protocols que es basen en un grup de suposicions diferents segons el sistema, mentre que Raft és un consens alternatiu a Paxos dissenyat per ser més comprensible.

Comprendre tant Paxos com Raft és molt útil per afavorir el coneixement de com funcionen els protocols de consens distribuït en criptomonedes, com ara proves de treball i pràctica tolerància a fallades bizantines..

Paxos & amp; Protocols de consens de la bassa

Antecedents sobre Paxos i Raft

Paxos es va proposar inicialment el 1989 i es va distingir com un mètode particularment elegant per demostrar la seguretat del consens distribuït tolerant als errors. Malgrat la seva novetat inicial, sovint es considera que Paxos és un desafiament d’entendre per les seves àmplies suposicions i el seu comportament complex.

Raft es va desenvolupar com una alternativa més comprensible a Paxos, que bàsicament equival a Paxos en termes de rendiment i garanties tolerants a fallades. Hi ha amplis recursos disponibles tant a Paxos com a Raft, i actualment s’estudien i s’utilitzen en una gran varietat d’aplicacions i sistemes..

Alguns dels usos pràctics més coneguts de Paxos es troben a la base de dades NewSQL de Google Clau i la IBM SAN Volume Controller per a serveis de visualització d’emmagatzematge.

Raft té diversos programes de codi obert implementacions de referència en diversos idiomes, inclosos Go, Java, C ++ i Rust.

Què és Paxos?

El consens en un sistema distribuït tolerant a fallades està acordant un resultat entre un grup de participants poc fiables. Paxos és una família d’algoritmes de consens que fan diversos compromisos entre suposicions sobre els processadors, els participants i els missatges d’un sistema determinat. El protocol garanteix la seguretat i sovint s’utilitza quan es requereix la durabilitat de grans conjunts de dades.

Els protocols de consens asíncrons no poden garantir la seguretat i la vitalitat, de manera que tots vénen amb els seus propis compromisos inherents. Paxos va ser un dels primers protocols distribuïts de consens tolerants a fallades per garantir la seguretat i els intents de generar vitalitat, assegurant-se que el valor de la proposta sigui finalment seleccionat pel grup de participants en una ronda de consens..

Hi ha tres rols en el consens de Paxos, coneguts com a agents:

  1. Proponents
  2. Acceptadors
  3. Aprenents

L’objectiu del consens és que un grup de participants arribi a un acord sobre un valor únic per cada ronda. Una ronda de consens comença quan un proponent envia un valor proposat a un grup d’acceptants. Els acceptants poden acceptar el valor proposat per un determinant proponent i, un cop es compleixi un llindar determinat, aquest valor l’aprova la xarxa.

No obstant això, perquè el consens funcioni correctament, la primera condició de Paxos és:

“Els acceptants han d’acceptar el primer valor proposat que reben”.

Això comporta el problema que diversos proponents envien valors proposats que són acceptats pels acceptants, però tots no accepten cap valor majoritari ja que accepten el primer valor proposat. Paxos ho soluciona indexant de forma única cada valor proposat que rep un acceptant que els permet acceptar més d’una proposta.

Un número únic defineix cada proposta i la xarxa selecciona un valor un cop la majoria d’acceptants accepta un valor específic proposat, conegut com a escollit valor. Es poden triar diverses propostes, però cal validar la propietat de seguretat garantint que totes aquestes propostes tinguin el mateix valor. Segons la definició de Leslie Lamport de la segona condició necessària de Paxos que garanteixi la seguretat:

“Si es tria una proposta amb valor v, totes les propostes que tinguin un nombre més elevat tindran valor v”.

La comunicació a la xarxa és asíncrona, de manera que és possible que certs acceptants no hagin rebut el valor escollit, cosa que està bé sempre que no es infringeixin les condicions 1 i 2.

Els proponents utilitzen certes restriccions com a missatges a grups d’acceptants juntament amb els valors. Aquests es diuen preparar peticions i contenen 2 sol·licituds principals:

  1. Prometeu que mai no acceptareu una proposta inferior a n (n és el número de la nova proposta)
  2. Respon amb la proposta amb el nombre més baix de n que l’acceptant ha acceptat.

Segons Lamport:

“Si el proponent rep les respostes sol·licitades per la majoria dels acceptants, pot emetre una proposta amb el número n i el valor v, on v és el valor de la proposta més numerada entre les respostes o és qualsevol valor seleccionat pel proponent si els respondents no van informar de cap proposta ”.

Posteriorment, els proponents envien una sol·licitud d’acceptació que els acceptants reconeixen. A continuació, el proponent envia un missatge de confirmació als acceptants que poden ignorar (sense comprometre la seguretat) o indicar l’èxit de la confirmació de valor. Un cop determinat llindar d’acceptants ha compromès el valor, el protocol d’aquesta ronda de consens finalitza i externalitza el valor.

El complex disseny de Paxos és que pot acceptar valors quan la majoria de nodes estan d’acord malgrat que altres nodes ignoren o deneguen un valor proposat. Això difereix de les anteriors iteracions de consens que requerien que tots els nodes estiguessin d’acord i estiguessin subjectes a bloqueig del protocol per la fallada de nodes individuals.

Mentre els números de la proposta siguin únics, Paxos pot seleccionar un valor que garanteixi la seguretat. És important tenir en compte que un acceptant només ha de recordar la proposta més numerada que ha acceptat. Per contra, un proponent sempre pot abandonar una proposta sempre que no reediti una proposta amb el mateix número únic.

Desglossar els rols del propositor i de l’acceptador en el protocol és el següent:

Proponent

  • Envia la proposta n als acceptants juntament amb preparar la sol·licitud, espereu que la majoria respongui.
  • Si la majoria dels acceptors respon que hi estan d’acord, respondran amb el valor acordat. Si la majoria rebutja, abandonar i reiniciar el procés.
  • Posteriorment, el proposador envia un missatge de confirmació amb n i valora si la majoria accepta.
  • Si la majoria dels acceptants accepten el missatge de confirmació, es completarà la ronda de protocol.

Acceptador

  • Rebeu la proposta i compareu-la amb la proposta més numerada ja acceptada.
  • Si n és més gran que acceptar la proposta, si n és inferior, rebutgeu la proposta.
  • Accepteu el missatge de confirmació posterior si el seu valor és el mateix que una proposta acceptada anteriorment i el seu número de seqüència és el nombre més alt acordat.

Les propostes poden fer diverses propostes, però han de seguir l’algoritme de cada proposta individualment.

Finalment, el paper del aprenents és descobrir que la majoria dels acceptants han acceptat una proposta dels proposants. Es selecciona un alumne distingit que propaga el valor escollit als altres estudiants de la xarxa. Es poden utilitzar variacions d’aquest procés quan tots els acceptants informen els aprenents corresponents de les seves decisions o bé els acceptants responen a un conjunt diferent d’aprenents que després propaguen el missatge a la resta d’aprenents.

Formalment, l’algorisme de Paxos distingeix un líder (proponent) per a cada ronda que es requereix per avançar. Els acceptadors poden reconèixer el lideratge d’un proposador que permet utilitzar Paxos per seleccionar un líder dins d’un grup de nodes. Tanmateix, Paxos es pot aturar si dos proponents competeixen per la posició de líder sense acord sobre quin és el líder. Però és poc probable que aquest estat de no terminació persisteixi.

Què és Raft?

Raft es va crear com una versió més comprensible de Paxos amb la mateixa tolerància a fallades i garanties de rendiment. Raft també millora la creació d’implementacions pràctiques de protocols. A causa de la complexitat de Paxos, no és útil per proporcionar una base sòlida a desenvolupar. Raft és similar a Paxos, de manera que comparar els dos requereix un breu desglossament de com Raft simplifica el procés de Paxos.

Raft empra un model de líder i seguidor basat en el supòsit que un grup de nodes només té un líder elegit. El líder gestiona la rèplica de registres a través dels nodes participants i se substitueix un cop falla o es desconnecta.

També es tria un líder quan comença l’algorisme. Per donar cert context a la selecció de líders, juga un paper vital en consens i es distingeix en algorismes específics. Per exemple, a la prova de treball de Nakamoto, la selecció de líders s’aconsegueix mitjançant un procés de mineria semblant a la loteria per a cada ronda, que és aproximadament cada 10 minuts. A la Tolerància a fallades bizantines pràctiques (pBFT), la selecció de líders es realitza mitjançant un format d’estil round-robin.

Què és el consens de Nakamoto

Llegiu: Què és el consens de Nakamoto?

Raft selecciona el líder mitjançant un procés iniciat per un node candidat. Si els candidats no reben comunicació durant una fase coneguda com a temps d’espera electoral, després voten per si mateixos després d’augmentar la seva comptador de termes i emetre’l als altres nodes. Els candidats es converteixen en seguidors d’altres candidats que tenen un nombre de termes com a mínim tan gran com el seu, i aquest efecte ondulat continua entre els nodes fins que un candidat rep la majoria de seguidors..

El líder controla la rèplica de registres entre els nodes on envia les ordres de sol·licitud del client als seus seguidors. Si la majoria dels seguidors confirmen la replicació, la sol·licitud es compromet. Els seguidors també apliquen els compromisos a les seves màquines estatals locals.

Raft conserva la tolerància a fallades dels nodes subjectes a fallades o fallades del líder en fer que un nou líder obligui els seus seguidors a duplicar els seus propis registres. Totes les entrades que no estiguin d’acord entre elles se suprimeixen, mantenint la coherència de la replicació del registre.

Els candidats líders han de tenir un registre més actualitzat que els registres de seguidors. Si el registre d’un candidat està menys actualitzat que un seguidor potencial (un votant en aquest context), el candidat es rebutjarà.

En general, Raft desconstrueix el consens en 3 subproblemes individuals:

  1. Elecció de líder
  2. Replicació de registres
  3. Seguretat

El protocol de consens utilitza a líder fort, el que significa que el node líder de Raft exerceix una influència substancial en el procés mentre es manté restringit pels límits del protocol. Com a resultat, Raft té un disseny més senzill que Paxos.

Conclusió

Paxos i Raft són protocols de consens importants que són components bàsics de l’ecosistema distribuït de tolerància a fallades més gran. Tot i que no s’utilitzen directament en criptomonedes, els protocols de consens utilitzats a les xarxes de criptomonedes deriven de molts dels seus supòsits característics del disseny de Paxos i Raft..

Mike Owergreen Administrator
Sorry! The Author has not filled his profile.
follow me