{"id":37335,"date":"2019-10-31T22:17:01","date_gmt":"2019-10-31T19:17:01","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah\/"},"modified":"2019-10-31T22:17:01","modified_gmt":"2019-10-31T19:17:01","slug":"kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","status":"publish","type":"post","link":"https:\/\/prohoster.info\/ro\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Pisica lui Schr\u00f6dinger f\u0103r\u0103 cutie: problema consensului \u00een sistemele distribuite","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

S\u0103 ne imagin\u0103m. \u00centr-o camer\u0103 sunt bloca\u021bi 5 pisici, \u0219i pentru a merge s\u0103-\u0219i trezeasc\u0103 st\u0103p\u00e2nul, trebuie s\u0103 se \u00een\u021beleag\u0103 \u00eentre ele, deoarece usa poate fi deschis\u0103 doar dac\u0103 se apas\u0103 cinci pe ea. Dac\u0103 una dintre pisici este pisica lui Schr\u00f6dinger, iar celelalte nu \u0219tiu despre decizia lui, se pune \u00eentrebarea: \u201eCum pot ei face asta?\u201d <\/p>\n

\u00cen acest articol, v\u0103 voi explica pe \u00een\u021belesul tuturor componenta teoretic\u0103 a lumii sistemelor distribuite \u0219i principiile lor de func\u021bionare. De asemenea, voi examina pe scurt ideea principal\u0103 care st\u0103 la baza algoritmului Paxos. <\/p>\n

\"Pisica
\n<\/a><\/noindex>
\nAtunci c\u00e2nd dezvoltatorii folosesc infrastructuri cloud, diverse baze de date \u0219i lucreaz\u0103 \u00een clustere cu un num\u0103r mare de noduri, ei sunt \u00eencrez\u0103tori c\u0103 datele vor fi integrale, securizate \u0219i mereu disponibile. Dar de unde vin aceste garan\u021bii?<\/p>\n

Practic, garan\u021biile pe care le avem sunt garan\u021biile furnizorului. Acestea sunt descrise \u00een documenta\u021bie cam a\u0219a: \u201eAcest serviciu este destul de fiabil, are un SLA specificat, nu v\u0103 face\u021bi griji, totul va func\u021biona distribuit, a\u0219a cum v\u0103 a\u0219tepta\u021bi.\u201d <\/p>\n

Suntem predispu\u0219i s\u0103 credem \u00een bine, deoarece unii b\u0103ie\u021bi de\u0219tep\u021bi din companii mari ne-au asigurat c\u0103 totul va fi bine. Nu ne punem \u00eentrebarea: de ce, de fapt, ar putea func\u021biona asta? Exist\u0103 vreo justificare formal\u0103 pentru corectitudinea func\u021bion\u0103rii acestor sisteme?<\/p>\n

Recent am fost la o \u0219coal\u0103 de calcul distribuit<\/a><\/noindex> \u0219i m-am sim\u021bit foarte inspirat de acest subiect. Lec\u021biile din \u0219coal\u0103 sem\u0103nau mai mult cu cursuri de analiz\u0103 matematic\u0103 dec\u00e2t cu ceva legat de sisteme informatice. Dar tocmai a\u0219a au fost demonstrate, la vremea respectiv\u0103, cele mai importante algoritmi pe care \u00eei folosim \u00een fiecare zi, f\u0103r\u0103 s\u0103 ne d\u0103m seama. <\/p>\n

\u00cen majoritatea sistemelor distribuite moderne se folose\u0219te algoritmul de consens Paxos \u0219i diversele sale modific\u0103ri. Cea mai tare parte este c\u0103 fundamentarea \u0219i posibilitatea existen\u021bei acestui algoritm pot fi dovedite simplu cu un pix \u0219i o foaie de h\u00e2rtie. \u00cen acela\u0219i timp, \u00een practic\u0103, algoritmul este aplicat \u00een sisteme mari, care func\u021bioneaz\u0103 pe un num\u0103r enorm de noduri \u00een cloud. <\/p>\n

O ilustra\u021bie simpl\u0103 a subiectului care va fi discutat \u00een continuare: problema celor doi generali.<\/b>Hai s\u0103 analiz\u0103m pentru \u00eenceput problema celor doi generali.<\/a><\/noindex>. <\/p>\n

Avem dou\u0103 armate \u2013 ro\u0219ie \u0219i alb\u0103. Trupele albe sunt bazate \u00een ora\u0219ul asediat. Trupele ro\u0219ii, conduse de generalii A1 \u0219i A2, se afl\u0103 de ambele p\u0103r\u021bi ale ora\u0219ului. Sarcina ro\u0219ilor este s\u0103 atace ora\u0219ul alb \u0219i s\u0103 \u00eenving\u0103. Totu\u0219i, fiecare armat\u0103 a fiec\u0103rui general ro\u0219u este mai mic\u0103 dec\u00e2t armata alb\u0103.<\/p>\n

\"Pisica
\n
\nCondi\u021biile de victorie pentru ro\u0219ii: ambii generali trebuie s\u0103 atace simultan pentru a avea un avantaj numeric asupra albilor. Pentru aceasta, generalii A1 \u0219i A2 trebuie s\u0103 ajung\u0103 la un acord \u00eentre ei. Dac\u0103 fiecare atac\u0103 separat, ro\u0219ii vor pierde. <\/p>\n

Pentru a ajunge la un consens, generalii A1 \u0219i A2 pot trimite mesageri unii altora prin teritoriul ora\u0219ului alb. Mesagerul poate ajunge cu succes la generalul aliat sau poate fi interceptat de inamic. \u00centrebarea este: exist\u0103 o astfel de secven\u021b\u0103 de comunica\u021bie \u00eentre generalii ro\u0219ii (secven\u021ba de trimitere a mesagerilor de la A1 la A2 \u0219i invers de la A2 la A1), prin care se garanteaz\u0103 c\u0103 vor ajunge s\u0103 se \u00een\u021beleag\u0103 asupra atacului la ora X. Aici, prin garan\u021bii se \u00een\u021belege c\u0103 ambii generali vor avea o confirmare clar\u0103 c\u0103 aliatul (cel\u0103lalt general) va ataca cu siguran\u021b\u0103 la timpul stabilit X.<\/p>\n

S\u0103 presupunem c\u0103 A1 trimite un mesager c\u0103tre A2 cu mesajul: \u201eS\u0103 atac\u0103m azi la miezul nop\u021bii!\u201d. Generalul A1 nu poate ataca f\u0103r\u0103 confirmarea generalului A2. Dac\u0103 mesagerul de la A1 a ajuns, atunci generalul A2 trimite o confirmare cu mesajul: \u201eDa, hai s\u0103 \u00eei ducem pe albi\u201d. Dar acum generalul A2 nu \u0219tie dac\u0103 mesagerul s\u0103u a ajuns sau nu, nu are garan\u021bii c\u0103 atacul va fi simultan. Acum, generalul A2 are nevoie din nou de o confirmare.<\/p>\n

Dac\u0103 continu\u0103m s\u0103 detaliem comunica\u021bia lor, se va dovedi urm\u0103toarele: indiferent c\u00e2te cicluri de schimb de mesaje ar fi, nu exist\u0103 o modalitate de a informa cu certitudine am\u00e2ndoi generalii c\u0103 mesajele lor au fost primite (cu condi\u021bia ca oricare dintre mesageri s\u0103 fie interceptat).<\/p>\n

Problema celor doi generali este o ilustra\u021bie excelent\u0103 a unui sistem distribuit foarte simplu, \u00een care exist\u0103 dou\u0103 noduri cu comunica\u021bie nesigur\u0103. Asta \u00eenseamn\u0103 c\u0103 nu avem o garan\u021bie de 100% c\u0103 se vor sincroniza. Despre astfel de probleme, dar la o scar\u0103 mai mare, vom discuta mai departe \u00een articol.<\/p>\n

Introducem conceptul de sisteme distribuite<\/h2>\n

\nUn sistem distribuit este un grup de computere (pe care le vom numi noduri) care pot schimba mesaje. Fiecare nod este o entitate autonom\u0103. Un nod poate procesa sarcini \u00een mod independent, dar pentru a interac\u021biona cu alte noduri, trebuie s\u0103 trimit\u0103 \u0219i s\u0103 primeasc\u0103 mesaje. <\/p>\n

Cum sunt implementate concret mesajele, ce protocoale sunt utilizate - nu ne intereseaz\u0103 \u00een acest context. Este important c\u0103 nodurile sistemului distribuit pot face schimb de date \u00eentre ele prin trimiterea de mesaje.<\/p>\n

Defini\u021bia \u00een sine nu pare foarte complicat\u0103, dar trebuie s\u0103 lu\u0103m \u00een considerare c\u0103 un sistem distribuit are o serie de atribute care vor fi importante pentru noi.<\/p>\n

Atributele sistemelor distribuite<\/h4>\n

<\/p>\n

    \n
  1. Concuren\u021ba<\/b> \u2013 capacitatea de a apari simultane sau evenimente concurente \u00een sistem. Mai mult, vom considera c\u0103 evenimentele survenite pe dou\u0103 noduri diferite sunt poten\u021bial concurente p\u00e2n\u0103 c\u00e2nd nu avem un ordine clar definit\u0103 a apari\u021biei acestor evenimente. \u0218i, de obicei, nu avem a\u0219a ceva.<\/li>\n
  2. Lipsa ceasurilor globale<\/b>. Nu avem un ordonare clar\u0103 a evenimentelor din cauza lipsei ceasurilor globale. \u00cen lumea obi\u0219nuit\u0103 a oamenilor, ne-am obi\u0219nuit cu faptul c\u0103 avem ceasuri \u0219i un timp absolut. Totul se schimb\u0103 c\u00e2nd vine vorba de sistemele distribuite. Chiar \u0219i ceasurile atomice extrem de precise au un drift \u0219i sunt posibile situa\u021bii \u00een care nu putem spune care dintre cele dou\u0103 evenimente a avut loc prima. A\u0219adar, nu ne putem baza nici pe timp.<\/li>\n
  3. Defec\u021biunea independent\u0103 a nodurilor sistemului<\/b>. Mai exist\u0103 o problem\u0103: ceva poate merge prost pur \u0219i simplu pentru c\u0103 nodurile noastre nu sunt eterne. Poate c\u0103 un disc dur se defecteaz\u0103, o ma\u0219in\u0103 virtual\u0103 din cloud se reporne\u0219te, re\u021beaua poate s\u0103 clipeasc\u0103 \u0219i mesajele s\u0103 se piard\u0103. Mai mult, pot exista situa\u021bii \u00een care nodurile func\u021bioneaz\u0103, dar \u00een acela\u0219i timp opereaz\u0103 \u00eempotriva sistemului. Ultima clas\u0103 de probleme a primit chiar \u0219i un nume separat: problema generalilor bizantini<\/a><\/noindex>. Cel mai popular exemplu de sistem distribuit cu o astfel de problem\u0103 este Blockchain. Dar ast\u0103zi nu vom examina aceast\u0103 clas\u0103 special\u0103 de probleme. Ne vor interesa situa\u021biile \u00een care pur \u0219i simplu unul sau mai multe noduri pot c\u0103dea din func\u021biune.<\/li>\n
  4. Modele de comunica\u021bie (modele de schimb de mesaje) \u00eentre noduri<\/b>. Am stabilit c\u0103 nodurile comunic\u0103 prin schimb de mesaje. Exist\u0103 dou\u0103 modele cunoscute de schimb de mesaje: sincron \u0219i asincron.<\/li>\n<\/ol>\n

    <\/p>\n

    Modele de comunicare \u00eentre noduri \u00een sisteme distribuite<\/h4>\n

    \nModelul sincron<\/b> \u2013 \u0219tim cu siguran\u021b\u0103 c\u0103 exist\u0103 o delta de timp finit cunoscut, \u00een care mesajul ajunge garantat de la un nod la altul. Dac\u0103 acest timp a expirat \u0219i mesajul nu a sosit, putem spune cu certitudine c\u0103 nodul a e\u0219uat. \u00cen acest model, avem un timp de a\u0219teptare predictibil. <\/p>\n

    Modelul asincron<\/b> \u2013 \u00een modelele asincrone consider\u0103m c\u0103 timpul de a\u0219teptare este finit, dar nu exist\u0103 o delta de timp dup\u0103 care putem garanta c\u0103 nodul a e\u0219uat. Adic\u0103, timpul de a\u0219teptare pentru un mesaj de la un nod poate fi oric\u00e2t de lung. Aceasta este o defini\u021bie important\u0103, de care vom discuta mai departe. <\/p>\n

    Conceptul de consens \u00een sistemele distribuite<\/h2>\n

    \n\u00cenainte de a defini formal conceptul de consens, s\u0103 lu\u0103m \u00een considerare un exemplu de situa\u021bie \u00een care acesta este necesar, \u0219i anume \u2013 Replica ma\u0219inii de stare<\/b>. <\/p>\n

    Avem un anumit jurnal distribuit. Ne-ar pl\u0103cea s\u0103 fie consistent \u0219i s\u0103 con\u021bin\u0103 date identice pe toate nodurile sistemului distribuit. C\u00e2nd unul dintre noduri afl\u0103 o nou\u0103 valoare pe care inten\u021bioneaz\u0103 s\u0103 o \u00eenregistreze \u00een jurnal, sarcina sa devine s\u0103 propun\u0103 aceast\u0103 valoare celorlalte noduri, astfel \u00eenc\u00e2t jurnalul s\u0103 fie actualizat pe toate nodurile \u0219i sistemul s\u0103 ajung\u0103 \u00eentr-o nou\u0103 stare consistent\u0103. Este important ca nodurile s\u0103 ajung\u0103 la un acord: toate nodurile sunt de acord c\u0103 noua valoare propus\u0103 este corect\u0103, toate nodurile accept\u0103 aceast\u0103 valoare, \u0219i abia atunci pot toate s\u0103 scrie \u00een jurnal noua valoare. <\/p>\n

    Cu alte cuvinte: niciunul dintre noduri nu a contestat c\u0103 ar avea informa\u021bii mai actuale, iar valoarea propus\u0103 este gre\u0219it\u0103. Acordul \u00eentre noduri \u0219i consensul asupra unei valori corecte acceptate este consensul \u00eentr-un sistem distribuit. Mai departe, vom discuta despre algoritmii care permit sistemului distribuit s\u0103 ating\u0103 consens \u00een mod garantat.
    \n\"Pisica
    \nMai formal, putem defini un algoritm de consens (sau pur \u0219i simplu algoritmul de consens) ca o func\u021bie care transform\u0103 un sistem distribuit din starea A \u00een starea B. Aceast\u0103 stare este acceptat\u0103 de toate nodurile, iar toate nodurile o pot confirma. A\u0219a cum se dove\u0219te, aceast\u0103 sarcin\u0103 nu este deloc trivial\u0103, a\u0219a cum pare la prima vedere.<\/p>\n

    Propriet\u0103\u021bile algoritmului de consens<\/h4>\n

    \nAlgoritmul de consens trebuie s\u0103 aib\u0103 trei propriet\u0103\u021bi pentru ca sistemul s\u0103 continue s\u0103 existe \u0219i s\u0103 aib\u0103 progrese \u00een tranzi\u021bia dintr-o stare \u00een alta:<\/p>\n

      \n
    1. Acord <\/b> \u2013 toate nodurile care func\u021bioneaz\u0103 corect trebuie s\u0103 accepte aceea\u0219i valoare (\u00een articole, aceast\u0103 proprietate este de asemenea men\u021bionat\u0103 ca proprietate de siguran\u021b\u0103). Toate nodurile care func\u021bioneaz\u0103 acum (care nu au e\u0219uat \u0219i nu au pierdut conexiunea cu celelalte) trebuie s\u0103 ajung\u0103 la un acord \u0219i s\u0103 accepte o anumit\u0103 valoare comun\u0103 final\u0103.\n

      Aici este important s\u0103 \u00een\u021belegem c\u0103 nodurile din sistemul distribuit pe care \u00eel discut\u0103m doresc s\u0103 ajung\u0103 la un acord. Adic\u0103, vorbim acum despre sisteme \u00een care ceva poate e\u0219ua (de exemplu, un nod poate e\u0219ua), dar \u00een acest sistem cu siguran\u021b\u0103 nu exist\u0103 noduri care lucreaz\u0103 inten\u021bionat \u00eempotriva altora (sarcina generalilor bizantini). Datorit\u0103 acestei propriet\u0103\u021bi, sistemul r\u0103m\u00e2ne consistent.<\/li>\n

    2. Integritate <\/b> \u2013 dac\u0103 toate nodurile care func\u021bioneaz\u0103 corect propun aceea\u0219i valoare v<\/b>, atunci fiecare nod care func\u021bioneaz\u0103 corect trebuie s\u0103 accepte aceast\u0103 valoare v<\/b>. <\/li>\n
    3. Terminare <\/b>\u2013 toate nodurile care func\u021bioneaz\u0103 corect vor accepta \u00een cele din urm\u0103 o anumit\u0103 valoare (proprietate de activitate), ceea ce permite algoritmului s\u0103 aib\u0103 progres \u00een sistem. Fiecare nod corect func\u021bion\u00e2nd trebuie, mai devreme sau mai t\u00e2rziu, s\u0103 accepte valoarea final\u0103 \u0219i s\u0103 confirme acest lucru: \u201ePentru mine, aceast\u0103 valoare este adev\u0103rat\u0103, sunt de acord cu \u00eentregul sistem\u201d.<\/li>\n<\/ol>\n

      <\/p>\n

      Exemplu de func\u021bionare a algoritmului de consens<\/h4>\n

      \nDe\u0219i propriet\u0103\u021bile algoritmului pot s\u0103 nu fie complet clare, s\u0103 ilust\u0103m printr-un exemplu etapele prin care trece cel mai simplu algoritm de consens \u00eentr-un sistem cu un model sincronic de schimb de mesaje, \u00een care toate nodurile func\u021bioneaz\u0103 corect, mesajele nu se pierd \u0219i nimic nu se stric\u0103 (chiar se \u00eent\u00e2mpl\u0103 asta?).<\/p>\n

        \n
      1. Totul \u00eencepe cu o propunere de c\u0103s\u0103torie (Propose). S\u0103 presupunem c\u0103 un client s-a conectat la nodul numit \u201eNod 1\u201d \u0219i a \u00eenceput o tranzac\u021bie, transmit\u00e2nd nodului o nou\u0103 valoare \u2013 O. De acum \u00eenainte, vom numi \u201eNod 1\u201d proposer<\/b>. Ca proposer, \u201eNod 1\u201d trebuie acum s\u0103 informeze \u00eentreaga sistem\u0103 c\u0103 are date noi \u0219i trimite tuturor celorlalte noduri mesaje: \u201eUita\u021bi! Am primit valoarea \u201eO\u201d \u0219i vreau s\u0103 o \u00eenregistrez! V\u0103 rog s\u0103 confirma\u021bi c\u0103 \u0219i voi ve\u021bi \u00eenregistra \u201eO\u201d \u00een jurnalul vostru\u201d.\n

        \"Pisica<\/li>\n

      2. Urm\u0103toarea etap\u0103 este votarea pentru valoarea propus\u0103 (Voting). De ce este necesar\u0103 aceasta? Este posibil ca altor noduri s\u0103 le fi sosit informa\u021bii mai recente \u0219i acestea s\u0103 aib\u0103 date referitoare la aceea\u0219i tranzac\u021bie.\n

        \"Pisica
        \n
        \nC\u00e2nd nodul \u201eNod 1\u201d \u00ee\u0219i trimite propunerea, celelalte noduri verific\u0103 \u00een jurnalele lor datele referitoare la acest eveniment. Dac\u0103 nu exist\u0103 contradic\u021bii, nodurile declar\u0103: \u201eDa, nu am alte date referitoare la acest eveniment. Valoarea \u201eO\u201d este cea mai recent\u0103 informa\u021bie pe care o avem\u201d. <\/p>\n

        \u00cen orice alt caz, nodurile pot r\u0103spunde \u201eNodului 1\u201d: \u201eAscult\u0103! Am date mai recente referitoare la aceast\u0103 tranzac\u021bie. Nu \u201eO\u201d, ci ceva mai bun\u201d.<\/p>\n

        \u00cen etapa de votare, nodurile ajung la o decizie: fie to\u021bi accept\u0103 o singur\u0103 valoare, fie unul dintre ele voteaz\u0103 \u00eempotriv\u0103, indic\u00e2nd c\u0103 are date mai recente. <\/li>\n

      3. Dac\u0103 runda de votare a avut loc cu succes, iar to\u021bi au fost \u201epentru\u201d, sistemul trece la o nou\u0103 etap\u0103 \u2013 acceptarea valorii (Accept). \u201eNod 1\u201d adun\u0103 toate r\u0103spunsurile de la celelalte noduri \u0219i anun\u021b\u0103: \u201eTo\u021bi au fost de acord cu valoarea \u201eO\u201d! Acum declar oficial c\u0103 \u201eO\u201d este noua noastr\u0103 valoare, comun\u0103 tuturor! Nota\u021bi-v\u0103 \u00een carnet, nu uita\u021bi. \u00cenregistra\u021bi \u00een jurnalul vostru!\u201d\n

        \"Pisica<\/li>\n

      4. Celelalte noduri trimit confirmarea (Accepted) c\u0103 au \u00eenregistrat valoarea \u201eO\u201d, nimic nou neprimind \u00een acest timp (o form\u0103 de two-phase commit). Dup\u0103 acest eveniment semnificativ, consider\u0103m c\u0103 tranzac\u021bia distribuit\u0103 s-a finalizat.
        \n \"Pisica <\/li>\n<\/ol>\n

        \nAstfel, algoritmul de consens \u00een cazul simplu const\u0103 din patru pa\u0219i: propunere, votare (voting), acceptare (accept), confirmarea accept\u0103rii (accepted).<\/p>\n

        Dac\u0103 la vreun pas nu am reu\u0219it s\u0103 ajungem la un consens, algoritmul se reporne\u0219te, av\u00e2nd \u00een vedere informa\u021biile pe care le vor oferi nodurile care au refuzat s\u0103 confirme valoarea propus\u0103.<\/p>\n

        Algoritmul de consens \u00eentr-un sistem asincron<\/h2>\n

        \nP\u00e2n\u0103 acum, totul a fost bine, deoarece vorbeam despre un model sincron de schimb de mesaje. Dar \u0219tim c\u0103 \u00een lumea modern\u0103 ne-am obi\u0219nuit s\u0103 facem totul asincron. Cum func\u021bioneaz\u0103 un algoritm similar \u00eentr-un sistem cu un model asincron de schimb de mesaje, unde consider\u0103m c\u0103 timpul de a\u0219teptare pentru r\u0103spuns de la un nod poate fi, \u00een teorie, nesf\u00e2r\u0219it (de altfel, e\u0219ecul unui nod poate fi v\u0103zut ca un exemplu \u00een care un nod poate r\u0103spunde oric\u00e2t de mult)? <\/p>\n

        Acum c\u0103 \u0219tim, \u00een principiu, cum func\u021bioneaz\u0103 algoritmul de consens, o \u00eentrebare pentru acei cititori curio\u0219i care au ajuns p\u00e2n\u0103 aici: c\u00e2te noduri dintr-un sistem cu N noduri, av\u00e2nd un model de mesaje asincron, pot ie\u0219i din func\u021biune astfel \u00eenc\u00e2t sistemul s\u0103 poat\u0103 atinge consensul \u00een continuare?<\/p><\/blockquote>\n

        \nR\u0103spunsul corect \u0219i explica\u021bia se afl\u0103 sub spoiler.<\/b>R\u0103spunsul corect: 0<\/b>. Dac\u0103 m\u0103car un nod dintr-un sistem asincron iese din func\u021biune, sistemul nu va putea atinge consensul. Aceast\u0103 afirma\u021bie este demonstrat\u0103 \u00een teorema cunoscut\u0103 \u00een anumite cercuri FLP (1985, Fischer, Lynch, Paterson, link c\u0103tre sursa original\u0103 la finalul articolului): \u201eImposibilitatea de a atinge consens distribu\u021bional \u00een cazul e\u0219ecului m\u0103car a unui nod\u201d.
        \n\"Pisica
        \nB\u0103ie\u021bi, atunci avem o problem\u0103, ne-am obi\u0219nuit cu totul asincron. \u0218i acum se \u00eent\u00e2mpl\u0103 asta. Cum mai trebuie s\u0103 continu\u0103m? <\/p>\n

        Acum am discutat despre teorie, despre matematic\u0103. Ce \u00eenseamn\u0103 \u201econsensul nu poate fi atins\u201d, traduc\u00e2nd din limbajul matematic \u00een limbajul nostru \u2013 ingineresc? Aceasta \u00eenseamn\u0103 c\u0103 \u201enu poate fi atins tot timpul\u201d, adic\u0103 exist\u0103 un caz \u00een care consensul nu este realizabil. Dar care este acel caz? <\/p>\n

        Aceasta este o \u00eenc\u0103lcare a propriet\u0103\u021bii de liveness, descris\u0103 mai sus. Nu avem un consens comun, iar sistemul nu poate progresa (nu poate termina \u00eentr-un timp finit) \u00een cazul \u00een care nu avem r\u0103spuns din partea tuturor nodurilor. Deoarece \u00eentr-un sistem asincron nu avem un timp de r\u0103spuns previzibil, \u0219i nu putem \u0219ti dac\u0103 un nod a ie\u0219it din func\u021biune sau pur \u0219i simplu r\u0103spunde \u00eencet.<\/p>\n

        Dar \u00een practic\u0103, putem g\u0103si o solu\u021bie. S\u0103 presupunem c\u0103 algoritmul nostru poate func\u021biona mult timp \u00een cazuri de e\u0219ec (poate func\u021biona teoretic la nesf\u00e2r\u0219it). Dar \u00een cele mai multe situa\u021bii, c\u00e2nd majoritatea nodurilor func\u021bioneaz\u0103 corect, vom avea progres \u00een sistem. <\/p>\n

        \u00cen practic\u0103, ne ocup\u0103m cu modele de comunicare par\u021bial sincronizate. Par\u021biala sincronizare este \u00een\u021beleas\u0103 astfel: \u00een general, avem un model asincron, dar se introduce formal un anumit concept de \u00abtimp de stabilizare global\u0103\u00bb a unui moment dat. <\/p>\n

        Acest moment poate s\u0103 nu apar\u0103 o perioad\u0103 nelimitat\u0103, dar, odat\u0103, el trebuie s\u0103 se \u00eent\u00e2mple. Un ceas virtual va suna, iar de atunci putem prezice delta de timp \u00een care mesajele vor ajunge. De atunci, sistemul devine din asincron \u00een sincron. \u00cen practic\u0103, ne confrunt\u0103m exact cu astfel de sisteme. <\/p>\n

        Algoritmul Paxos rezolv\u0103 problemele de consens.<\/h2>\n

        \nPaxos <\/a><\/noindex> \u2013 este o familie de algoritmi care rezolv\u0103 problema consenului pentru sisteme par\u021bial sincronizate, \u00een condi\u021biile \u00een care unele noduri pot c\u0103dea. Autorul algoritmului Paxos este Leslie Lamport<\/a><\/noindex>. El a propus o dovad\u0103 formal\u0103 a existen\u021bei \u0219i corectitudinii algoritmului \u00een 1989. <\/p>\n

        \u00cens\u0103, dovada s-a dovedit a fi deloc trivial\u0103. Prima publica\u021bie a fost lansat\u0103 abia \u00een 1998 (33 de pagini) cu descrierea algoritmului. A\u0219a cum s-a dovedit, aceasta a fost extrem de dificil de \u00een\u021beles, iar \u00een 2001 a fost publicat\u0103 o explica\u021bie a articolului, care a ocupat 14 pagini. Volumele publica\u021biilor sunt men\u021bionate pentru a ar\u0103ta c\u0103, de fapt, problema consensului nu este deloc simpl\u0103 \u0219i c\u0103 \u00een spatele acestor algoritmi se afl\u0103 un efort imens al celor mai inteligen\u021bi oameni.<\/p>\n

        Este interesant c\u0103 Leslie Lamport \u00eensu\u0219i a observat \u00een cursul s\u0103u c\u0103 \u00een al doilea articol explicativ exist\u0103 o afirma\u021bie, o linie (nu a specificat care), care poate fi interpretat\u0103 diferit. Din aceast\u0103 cauz\u0103, un num\u0103r mare de implement\u0103ri moderne ale Paxos func\u021bioneaz\u0103 nu tocmai corect. <\/p><\/blockquote>\n

        \nO analiz\u0103 detaliat\u0103 a func\u021bion\u0103rii Paxos ar necesita mai multe articole, a\u0219a c\u0103 voi \u00eencerca s\u0103 transmit pe scurt ideea principal\u0103 a algoritmului. \u00cen linkurile de la sf\u00e2r\u0219itul articolului meu ve\u021bi g\u0103si materiale pentru o aprofundare a acestei teme.<\/p>\n

        Roluri \u00een Paxos<\/h4>\n

        \n\u00cen algoritmul Paxos exist\u0103 un concept de roluri. S\u0103 examin\u0103m cele trei principale (exist\u0103 \u0219i modific\u0103ri cu roluri adi\u021bionale):<\/p>\n

          \n
        1. Propozitori (pot fi \u00eent\u00e2lni\u021bi de asemenea termeni: lideri sau coordonatori)<\/b>. Ace\u0219tia sunt oamenii care afl\u0103 despre un nou tip de valoare de la utilizator \u0219i \u00ee\u0219i asum\u0103 rolul de lider. Sarcina lor este s\u0103 ini\u021bieze un ciclu de propunere a noii valori \u0219i s\u0103 coordoneze ac\u021biunile ulterioare ale nodurilor. \u00cen plus, Paxos permite existen\u021ba mai multor lideri \u00een anumite situa\u021bii.<\/li>\n
        2. Acceptori (Votanti)<\/b>. Acestea sunt nodurile care voteaz\u0103 pentru acceptarea sau respingerea unei anumite valori. Rolul lor este foarte important, deoarece decizia final\u0103 despre starea sistemului dup\u0103 fiecare etap\u0103 a algoritmului de consens depinde de ei.<\/li>\n
        3. \u00cenv\u0103\u021b\u0103cei<\/b>. Noduri care pur \u0219i simplu accept\u0103 \u0219i \u00eenregistreaz\u0103 noua valoare acceptat\u0103, atunci c\u00e2nd starea sistemului se schimb\u0103. Ace\u0219tia nu iau decizii, ci doar primesc datele \u0219i le pot transmite utilizatorului final. <\/li>\n<\/ol>\n

          \nUn nod poate \u00eendeplini mai multe roluri \u00een func\u021bie de situa\u021bie. <\/p>\n

          Conceptul de cv\u00f3rum<\/h4>\n

          \nPresupunem c\u0103 avem un sistem format din N<\/b> noduri. \u0218i din acestea, maximum F<\/b> noduri pot s\u0103 e\u0219ueze. Dac\u0103 F noduri e\u0219ueaz\u0103, atunci \u00een cluster trebuie s\u0103 avem, minimum 2F + 1<\/b> noduri acceptor. <\/p>\n

          Acest lucru este necesar pentru a ne asigura c\u0103, chiar \u0219i \u00een cea mai grav\u0103 situa\u021bie, nodurile \u201ebune\u201d care func\u021bioneaz\u0103 corect au o majoritate. Cu alte cuvinte, F + 1<\/b> noduri \u201ebune\u201d care au fost de acord, iar valoarea final\u0103 va fi acceptat\u0103. \u00cen caz contrar, ar putea ap\u0103rea situa\u021bii \u00een care grupuri locale diferite accept\u0103 valori diferite \u0219i nu pot ajunge la un consens. De aceea, avem nevoie de o majoritate absolut\u0103 pentru a c\u00e2\u0219tiga votul.<\/p>\n

          Ideea general\u0103 de func\u021bionare a algoritmului de consens Paxos<\/h4>\n

          \nAlgoritmul Paxos preconizeaz\u0103 dou\u0103 faze mari, care sunt \u00eemp\u0103r\u021bite fiecare \u00een dou\u0103 pa\u0219i:<\/p>\n

            \n
          1. Faza 1a: Preg\u0103tire<\/b>. \u00cen etapa de preg\u0103tire, liderul (proposer) comunic\u0103 tuturor nodurilor: \u201e\u00cencepem o nou\u0103 etap\u0103 de votare. Avem un nou tur. Num\u0103rul acestui tur este n. Acum vom \u00eencepe votarea\u201d. Deocamdat\u0103, el anun\u021b\u0103 doar \u00eenceputul unui nou ciclu, f\u0103r\u0103 a comunica o nou\u0103 valoare. Scopul acestei etape este de a ini\u021bia un nou tur \u0219i de a anun\u021ba tuturor num\u0103rul s\u0103u unic. Num\u0103rul turului este important, trebuie s\u0103 fie o valoare mai mare dec\u00e2t toate numerele voturilor anterioare ale tuturor liderilor anteriori. Datorit\u0103 num\u0103rului turului, celelalte noduri din sistem vor \u00een\u021belege c\u00e2t de recente sunt datele liderului. Probabil c\u0103 alte noduri au deja rezultatele vot\u0103rii din tururi mult mai recente \u0219i \u00eei vor spune liderului c\u0103 a r\u0103mas \u00een urm\u0103.<\/li>\n
          2. Faza 1b: Promisiune<\/b>. Atunci c\u00e2nd nodurile acceptor primesc num\u0103rul noii etape de votare, sunt posibile dou\u0103 rezultate: \n