Així doncs, imaginem-nos. Hi ha 5 gats tancats a l'habitació, i per anar a despertar el propietari cal que tots es posen d'acord, perquè només poden obrir la porta amb cinc d'ells recolzats. Si un dels gats és el gat de Schrödinger i els altres gats no saben de la seva decisió, sorgeix la pregunta: "Com ho poden fer?"
En aquest article us explicaré en termes senzills el component teòric del món dels sistemes distribuïts i els principis del seu funcionament. També examinaré superficialment la idea principal subjacent a Paxos.
Quan els desenvolupadors utilitzen infraestructures al núvol, diverses bases de dades i treballen en clústers d'un gran nombre de nodes, confien que les dades estaran completes, segures i sempre disponibles. Però on són les garanties?
Bàsicament, les garanties que tenim són garanties de proveïdors. Es descriuen a la documentació de la següent manera: "Aquest servei és bastant fiable, té un SLA determinat, no us preocupeu, tot funcionarà de manera distribuïda com espereu".
Tenim tendència a creure en el millor, perquè els intel·ligents de les grans empreses ens van assegurar que tot anirà bé. No ens fem la pregunta: per què, de fet, això pot funcionar? Hi ha alguna justificació formal per al correcte funcionament d'aquests sistemes?
Fa poc vaig anar a i estava molt inspirat amb aquest tema. Les conferències a l'escola s'assemblaven més a classes de càlcul que a alguna cosa relacionada amb els sistemes informàtics. Però això és exactament com es van demostrar en un moment els algorismes més importants que fem servir cada dia, sense ni saber-ho.
La majoria dels sistemes distribuïts moderns utilitzen l'algoritme de consens de Paxos i les seves diverses modificacions. El més genial és que la validesa i, en principi, la mateixa possibilitat de l'existència d'aquest algorisme es pot demostrar simplement amb un llapis i un paper. A la pràctica, l'algorisme s'utilitza en sistemes grans que s'executen en un gran nombre de nodes als núvols.
Una lleugera il·lustració del que es parlarà a continuació: la tasca de dos generalsFem una ullada per fer un escalfament .
Tenim dos exèrcits: vermell i blanc. Les tropes blanques es basen a la ciutat assetjada. Les tropes vermelles dirigides pels generals A1 i A2 es troben a dos costats de la ciutat. La tasca dels pèl-rojos és atacar la ciutat blanca i guanyar. Tanmateix, l'exèrcit de cada general vermell individualment és més petit que l'exèrcit blanc.
Condicions de victòria per als vermells: ambdues generals han d'atacar alhora per tenir un avantatge numèric sobre els blancs. Per fer-ho, els generals A1 i A2 han d'arribar a un acord entre ells. Si tothom ataca per separat, els pèl-rojos perdran.
Per arribar a un acord, els generals A1 i A2 poden enviar missatgers entre ells pel territori de la ciutat blanca. El missatger pot arribar amb èxit a un general aliat o pot ser interceptat per l'enemic. Pregunta: hi ha tal seqüència de comunicacions entre els generals pèl-rojos (la seqüència d'enviament de missatgers d'A1 a A2 i viceversa d'A2 a A1), en què es garanteix que es posaran d'acord en un atac a l'hora X. Aquí, Les garanties signifiquen que ambdós generals tindran una confirmació inequívoca que un aliat (un altre general) atacarà definitivament a l'hora assenyalada X.
Suposem que A1 envia un missatger a A2 amb el missatge: "Ataquem avui a mitjanit!" El general A1 no pot atacar sense la confirmació del general A2. Si ha arribat el missatger de l'A1, el general A2 envia una confirmació amb el missatge: "Sí, matem els blancs avui". Però ara el general A2 no sap si el seu missatger ha arribat o no, no té cap garantia si l'atac serà simultani. Ara el General A2 torna a necessitar confirmació.
Si descrivim més la seva comunicació, queda clar que no importa quants cicles d'intercanvi de missatges hi hagi, no hi ha manera de garantir que ambdós generals hagin rebut els seus missatges (suposant que qualsevol missatger pot ser interceptat).
El problema dels dos generals és una gran il·lustració d'un sistema distribuït molt senzill on hi ha dos nodes amb una comunicació poc fiable. Això vol dir que no tenim una garantia del 100% que estiguin sincronitzats. Problemes similars només es discuteixen a una escala més gran més endavant en l'article.
Introduïm el concepte de sistemes distribuïts
Un sistema distribuït és un grup d'ordinadors (d'ara endavant els anomenarem nodes) que poden intercanviar missatges. Cada node individual és una mena d'entitat autònoma. Un node pot processar tasques per si mateix, però per comunicar-se amb altres nodes, ha d'enviar i rebre missatges.
Com s'implementen exactament els missatges, quins protocols s'utilitzen, això no ens interessa en aquest context. És important que els nodes d'un sistema distribuït puguin intercanviar dades entre ells enviant missatges.
La definició en si no sembla gaire complicada, però hem de tenir en compte que un sistema distribuït té una sèrie d'atributs que seran importants per a nosaltres.
Atributs dels sistemes distribuïts
- Concurrència – la possibilitat que es produeixin esdeveniments simultanis o concurrents al sistema. A més, considerarem que els esdeveniments que es produeixen en dos nodes diferents són potencialment concurrents sempre que no tinguem un ordre clar d'ocurrència d'aquests esdeveniments. Però, per regla general, no en tenim.
- Sense rellotge global. No tenim un ordre clar dels esdeveniments a causa de la manca d'un rellotge global. En el món normal de la gent, estem acostumats a tenir rellotges i temps absolutament. Tot canvia quan es tracta de sistemes distribuïts. Fins i tot els rellotges atòmics ultraprecisos tenen una deriva, i pot haver-hi situacions en què no podem dir quin dels dos esdeveniments va passar primer. Per tant, tampoc podem confiar en el temps.
- Falla independent dels nodes del sistema. Hi ha un altre problema: alguna cosa pot anar malament simplement perquè els nostres nodes no duren per sempre. El disc dur pot fallar, la màquina virtual al núvol es pot reiniciar, la xarxa pot parpellejar i es perdran missatges. A més, pot haver-hi situacions en què els nodes funcionin, però al mateix temps funcionin contra el sistema. L'última classe de problemes fins i tot va rebre un nom separat: problema . L'exemple més popular d'un sistema distribuït amb aquest problema és Blockchain. Però avui no considerarem aquesta classe especial de problemes. Ens interessarà situacions en què simplement un o més nodes poden fallar.
- Models de comunicació (models de missatgeria) entre nodes. Ja hem establert que els nodes es comuniquen intercanviant missatges. Hi ha dos models de missatgeria coneguts: síncron i asíncron.
Models de comunicació entre nodes en sistemes distribuïts
Model sincrònic – sabem del cert que hi ha un delta de temps finit conegut durant el qual es garanteix que un missatge arriba d'un node a un altre. Si ha passat aquest temps i el missatge no ha arribat, podem dir amb seguretat que el node ha fallat. En aquest model tenim temps d'espera previsibles.
Model asíncron – en els models asíncrons considerem que el temps d'espera és finit, però no hi ha aquest delta de temps després del qual podem garantir que el node ha fallat. Aquells. El temps d'espera per a un missatge d'un node pot ser arbitràriament llarg. Aquesta és una definició important, i en parlarem més endavant.
El concepte de consens en sistemes distribuïts
Abans de definir formalment el concepte de consens, considerem un exemple d'una situació on ho necessitem, és a dir: Replicació de la màquina d'estat.
Tenim un registre distribuït. Ens agradaria que fos coherent i contingués dades idèntiques a tots els nodes del sistema distribuït. Quan un dels nodes aprèn un valor nou que escriurà al registre, la seva tasca és oferir aquest valor a tots els altres nodes de manera que el registre s'actualitzi a tots els nodes i el sistema passi a un nou estat coherent. En aquest cas, és important que els nodes estiguin d'acord entre ells: tots els nodes estan d'acord que el nou valor proposat és correcte, tots els nodes accepten aquest valor i només en aquest cas tothom pot escriure el nou valor al registre.
Dit d'una altra manera: cap dels nodes es va oposar que tenia informació més rellevant i el valor proposat era incorrecte. L'acord entre nodes i l'acord sobre un únic valor acceptat correcte és consens en un sistema distribuït. A continuació, parlarem d'algorismes que permeten garantir un sistema distribuït per arribar al consens.
Més formalment, podem definir un algorisme de consens (o simplement un algorisme de consens) com una funció determinada que transfereix un sistema distribuït de l'estat A a l'estat B. A més, aquest estat és acceptat per tots els nodes, i tots els nodes ho poden confirmar. Com a resultat, aquesta tasca no és gens tan trivial com sembla a primera vista.
Propietats de l'algoritme de consens
L'algoritme de consens ha de tenir tres propietats perquè el sistema continuï existint i tingui algun progrés en el moviment d'estat a estat:
- Acord – tots els nodes que funcionen correctament han de tenir el mateix valor (en els articles aquesta propietat també es coneix com a propietat de seguretat). Tots els nodes que funcionen actualment (no han fallat ni han perdut el contacte amb els altres) han d'arribar a un acord i acceptar algun valor comú final.
És important entendre aquí que els nodes del sistema distribuït que estem considerant volen estar d'acord. És a dir, ara estem parlant de sistemes en què alguna cosa simplement pot fallar (per exemple, algun node falla), però en aquest sistema definitivament no hi ha nodes que funcionin deliberadament contra altres (la tasca dels generals bizantins). A causa d'aquesta propietat, el sistema es manté coherent.
- integritat — si tots els nodes que funcionen correctament ofereixen el mateix valor v, el que significa que tots els nodes que funcionen correctament han d'acceptar aquest valor v.
- Terminació – tots els nodes que funcionen correctament adquiriran finalment un cert valor (propietat de vivacitat), que permet que l'algoritme avanci en el sistema. Cada node que funcioni correctament ha d'acceptar tard o d'hora el valor final i confirmar-lo: "Per a mi, aquest valor és cert, estic d'acord amb tot el sistema".
Un exemple de com funciona l'algoritme de consens
Tot i que les propietats de l'algorisme poden no estar del tot clares. Per tant, il·lustrarem amb un exemple per quines etapes passa l'algoritme de consens més senzill en un sistema amb un model de missatgeria síncrona, en què tots els nodes funcionen com s'esperava, no es perden missatges i no es trenca res (això realment passa?).
- Tot comença amb una proposta de matrimoni (Proposar). Suposem que un client es va connectar a un node anomenat "Node 1" i va iniciar una transacció, passant un nou valor al node - O. A partir d'ara, anomenarem "Node 1" oferta. Com a proposant, el "Node 1" ara ha de notificar a tot el sistema que té dades noves i envia missatges a tots els altres nodes: "Mira! El significat "O" em va venir i vull escriure-ho! Si us plau, confirmeu que també enregistrareu "O" al vostre registre".
- La següent etapa és votar el valor proposat (Votació). Per a què serveix? Pot passar que altres nodes hagin rebut informació més recent i tinguin dades sobre la mateixa transacció.
Quan el node "Node 1" envia la seva proposta, els altres nodes comproven els seus registres per trobar dades sobre aquest esdeveniment. Si no hi ha contradiccions, els nodes anuncien: “Sí, no tinc altres dades d'aquest esdeveniment. El valor "O" és la informació més recent que ens mereixem".En qualsevol altre cas, els nodes poden respondre al "Node 1": "Escolta! Tinc dades més recents sobre aquesta transacció. No "O", sinó alguna cosa millor".
En l'etapa de votació, els nodes prenen una decisió: o accepten tots el mateix valor, o un d'ells vota en contra, indicant que té dades més recents.
- Si la votació va tenir èxit i tothom estava a favor, el sistema passa a una nova etapa: acceptar el valor. "Node 1" recull totes les respostes d'altres nodes i informa: "Tothom estava d'acord en el valor "O"! Ara declaro oficialment que "O" és el nostre nou significat, el mateix per a tothom! Escriu-ho al teu llibret, no t'oblidis. Anoteu-ho al vostre registre!"
- Els nodes restants envien confirmació (Acceptat) que han escrit el valor "O"; no ha arribat res de nou durant aquest temps (una mena de commit en dues fases). Després d'aquest fet significatiu, considerem que l'operació distribuïda ha finalitzat.
Així, l'algorisme de consens en un cas senzill consta de quatre passos: proposar, votar (votar), acceptar (acceptar), confirmar l'acceptació (acceptar).
Si en algun pas no hem pogut arribar a un acord, l'algorisme torna a començar, tenint en compte la informació proporcionada pels nodes que es van negar a confirmar el valor proposat.
Algorisme de consens en un sistema asíncron
Abans, tot anava bé, perquè estàvem parlant d'un model de missatgeria síncrona. Però sabem que al món modern estem acostumats a fer-ho tot de manera asíncrona. Com funciona un algorisme similar en un sistema amb un model de missatgeria asíncrona, on creiem que el temps d'espera per a una resposta d'un node pot ser arbitràriament llarg (per cert, la fallada d'un node també es pot considerar com a exemple quan un node pot respondre durant un temps arbitràriament llarg).
Ara que sabem com funciona en principi l'algoritme de consens, una pregunta per a aquells lectors curiosos que han arribat fins aquí: quants nodes en un sistema de N nodes amb un model de missatge asíncron poden fallar perquè el sistema encara pugui arribar al consens?
La resposta correcta i la justificació estan darrere del spoiler.La resposta correcta és: 0. Si fins i tot un node d'un sistema asíncron falla, el sistema no podrà arribar a un consens. Aquesta afirmació queda demostrada en el teorema FLP, conegut en certs cercles (1985, Fischer, Lynch, Paterson, enllaç a l'original al final de l'article): “La impossibilitat d'aconseguir un consens distribuït si falla almenys un node. .”
Nois, llavors tenim un problema, estem acostumats a que tot sigui asíncron. I aquí està. Com seguir vivint?
Només estàvem parlant de teoria, de matemàtiques. Què vol dir "no es pot aconseguir el consens", traduint del llenguatge matemàtic al nostre: l'enginyeria? Això vol dir que "no sempre es pot aconseguir", és a dir. Hi ha un cas en què el consens no és possible. Quin tipus de cas és aquest?
Aquesta és exactament la violació de la propietat de vida descrita anteriorment. No tenim un acord comú, i el sistema no pot tenir progrés (no es pot completar en un temps finit) en el cas que no tinguem una resposta de tots els nodes. Perquè en un sistema asíncron no tenim un temps de resposta previsible i no podem saber si un node s'ha bloquejat o només triga molt a respondre.
Però a la pràctica podem trobar una solució. Que el nostre algorisme pugui funcionar durant molt de temps en cas de fallades (potencialment pot funcionar indefinidament). Però en la majoria de situacions, quan la majoria dels nodes funcionen correctament, tindrem progrés en el sistema.
A la pràctica, tractem models de comunicació parcialment sincrònics. La sincronia parcial s'entén de la següent manera: en el cas general, tenim un model asíncron, però s'introdueix formalment un cert concepte de "temps d'estabilització global" d'un moment determinat.
Aquest moment pot no arribar durant molt de temps, però ha d'arribar un dia. Sonarà el despertador virtual, i a partir d'aquest moment podem predir el delta horari per al qual arribaran els missatges. A partir d'aquest moment, el sistema passa d'asíncron a síncron. A la pràctica, tractem precisament aquests sistemes.
L'algorisme de Paxos resol problemes de consens
és una família d'algorismes que resolen el problema del consens per a sistemes parcialment sincrònics, subjecte a la possibilitat que alguns nodes puguin fallar. L'autor de Paxos és . Va proposar una prova formal de l'existència i la correcció de l'algorisme el 1989.
Però la prova va resultar estar lluny de ser trivial. La primera publicació es va publicar només el 1998 (33 pàgines) on es descriu l'algorisme. Com va resultar, va ser extremadament difícil d'entendre i l'any 2001 es va publicar una explicació de l'article, que va tenir 14 pàgines. El volum de publicacions es dóna per demostrar que, de fet, el problema del consens no és gens senzill, i darrere d'aquests algorismes s'amaga una gran quantitat de treball de les persones més intel·ligents.
És interessant que el mateix Leslie Lamport va assenyalar a la seva conferència que en el segon article explicatiu hi ha una afirmació, una línia (no va especificar quina), que es pot interpretar de diferents maneres. I per això, un gran nombre d'implementacions modernes de Paxos no funcionen del tot correctament.
Una anàlisi detallada del treball de Paxos necessitaria més d'un article, així que intentaré transmetre molt breument la idea principal de l'algorisme. Als enllaços al final del meu article trobareu materials per aprofundir en aquest tema.
Funcions a Paxos
L'algoritme de Paxos té un concepte de rols. Considerem-ne tres principals (hi ha modificacions amb rols addicionals):
- Proposents (també es poden utilitzar els termes: líders o coordinadors). Aquests són els nois que aprenen sobre algun valor nou de l'usuari i assumeixen el paper de líder. La seva tasca és llançar una ronda de propostes per a un nou valor i coordinar més accions dels nodes. A més, Paxos permet la presència de diversos líders en determinades situacions.
- Acceptants (votants). Són nodes que voten per acceptar o rebutjar un valor determinat. El seu paper és molt important, perquè d'ells depèn la decisió: a quin estat anirà (o no) el sistema després de la següent etapa de l'algorisme de consens.
- Aprenents. Nodes que simplement accepten i escriuen el nou valor acceptat quan l'estat del sistema ha canviat. No prenen decisions, només reben les dades i les poden donar a l'usuari final.
Un node pot combinar diversos rols en diferents situacions.
El concepte de quòrum
Suposem que tenim un sistema de N nodes I d'ells el màxim F els nodes poden fallar. Si fallen els nodes F, hem de tenir almenys 2F+1 nodes acceptors.
Això és necessari perquè tinguem sempre la majoria, fins i tot en la pitjor situació, de nodes “bons” que funcionen correctament. Això és F+1 nodes "bons" que s'acordin, i s'acceptarà el valor final. En cas contrari, pot haver-hi una situació en què els nostres diferents grups locals prenguin significats diferents i no es puguin posar d'acord entre ells. Per tant, necessitem la majoria absoluta per guanyar la votació.
La idea general de com funciona l'algoritme de consens de Paxos
L'algorisme de Paxos implica dues grans fases, que al seu torn es divideixen en dos passos cadascuna:
- Fase 1a: Preparació. Durant la fase de preparació, el líder (proposent) informa a tots els nodes: “Comencem una nova fase de votació. Tenim una nova ronda. El número d'aquesta ronda és n. Ara començarem a votar". De moment, simplement informa de l'inici d'un nou cicle, però no informa d'un nou valor. La tasca d'aquesta etapa és iniciar una nova ronda i informar a tothom del seu número únic. El número rodó és important, ha de ser un valor superior a tots els números de votació anteriors de tots els líders anteriors. Perquè és gràcies al número rodó que altres nodes del sistema entendran com de recents són les dades del líder. És probable que altres nodes ja tinguin resultats de votació de rondes molt posteriors i simplement diguin al líder que està endarrerit amb els temps.
- Fase 1b: Promesa. Quan els nodes acceptors reben el número de la nova etapa de votació, són possibles dos resultats:
- El número n del nou vot és superior al nombre de qualsevol vot anterior en el qual hagi participat l'acceptant. Aleshores, l'acceptant envia una promesa al líder que no participarà en més votacions amb un nombre inferior a n. Si l'acceptant ja ha votat alguna cosa (és a dir, ja ha acceptat algun valor en la segona fase), aleshores adjunta a la seva promesa el valor acceptat i el número del vot en què ha participat.
- En cas contrari, si l'acceptant ja coneix el vot de nombre més alt, simplement pot ignorar el pas de preparació i no respondre al líder.
- Fase 2a: Acceptar. El líder ha d'esperar una resposta del quòrum (la majoria dels nodes del sistema) i, si es rep el nombre requerit de respostes, té dues opcions per al desenvolupament d'esdeveniments:
- Alguns dels acceptants van enviar valors que ja havien votat. En aquest cas, el líder selecciona el valor de la votació amb el nombre màxim. Anomenem aquest valor x i envia un missatge a tots els nodes com: "Accepta (n, x)", on el primer valor és el número de votació del seu propi pas Proposa, i el segon valor és el que tothom va reunir, és a dir el valor pel qual votem realment.
- Si cap dels acceptants va enviar cap valor, però simplement es va comprometre a votar en aquesta ronda, el líder pot convidar-los a votar pel seu valor, el valor pel qual es va convertir en líder en primer lloc. Diguem-ne y. Envia un missatge a tots els nodes com: "Accepta (n, y)", similar al resultat anterior.
- Fase 2b: Acceptada. A més, els nodes acceptors, en rebre el missatge "Accepta (...)" del líder, estan d'acord amb ell (envien confirmació a tots els nodes que estan d'acord amb el nou valor) només si no han promès algun (un altre) ) líder per participar en la votació amb número de ronda n' > n, en cas contrari, ignoraran la sol·licitud de confirmació.
Si la majoria dels nodes van respondre al líder i tots van confirmar el nou valor, llavors el nou valor es considera acceptat. Hura! Si no s'arriba a la majoria o hi ha nodes que es van negar a acceptar el nou valor, tot torna a començar.
Així és com funciona l'algorisme de Paxos. Cadascuna d'aquestes etapes té moltes subtileses, pràcticament no hem considerat diversos tipus de fallades, problemes de múltiples líders i molt més, però l'objectiu d'aquest article és només introduir el lector al món de la informàtica distribuïda a un alt nivell.
També val la pena assenyalar que Paxos no és l'únic d'aquest tipus, hi ha altres algorismes, per exemple, , però aquest és un tema per a un altre article.
Enllaços a materials per a un estudi posterior
Nivell principiant:
- , Preethi Kasireddy, article del bloc sobre Medium
- , Adi Kancherla, article del blog sobre Medium
- , Ittai Abraham, bloc
- , Ittai Abraham, article del blog
Nivell de Leslie Lampport:
- , Fischer, Lynch i Paterson, document de recerca, 1985
- , Leslie Lampport, document de recerca, 1998
- , Leslie Lampport, document de recerca, 2001
Font: www.habr.com