ProHoster > Blogs > Administrācija > Šrēdingera kaķis bez kastes: vienprātības problēma sadalītajās sistēmās

Šrēdingera kaķis bez kastes: vienprātības problēma sadalītajās sistēmās

Tātad, iedomāsimies. Istabā ir aizslēgti 5 kaÄ·i, un, lai aizietu pamodināt saimnieku, viņiem visiem par to jāvienojas savā starpā, jo durvis var atvērt tikai pieci no tām atspieduÅ”ies. Ja viens no kaÄ·iem ir Å rēdingera kaÄ·is, bet pārējie kaÄ·i nezina par viņa lēmumu, rodas jautājums: "Kā viņi to var izdarÄ«t?"

Å ajā rakstā es jums vienkārÅ”i pastāstÄ«Å”u par sadalÄ«to sistēmu pasaules teorētisko sastāvdaļu un to darbÄ«bas principiem. Es arÄ« virspusēji apskatÄ«Å”u galveno Paxos ideju.

Šrēdingera kaķis bez kastes: vienprātības problēma sadalītajās sistēmās

Kad izstrādātāji izmanto mākoņa infrastruktÅ«ras, dažādas datu bāzes un strādā klasteros ar lielu skaitu mezglu, viņi ir pārliecināti, ka dati bÅ«s pilnÄ«gi, droÅ”i un vienmēr pieejami. Bet kur garantijas?

Būtībā mūsu garantijas ir piegādātāju garantijas. Tie dokumentācijā aprakstīti Ŕādi: "Šis pakalpojums ir diezgan uzticams, tam ir noteikts SLA, neuztraucieties, viss darbosies sadalīti, kā jūs gaidāt."

Mums ir tendence ticēt labākajam, jo ā€‹ā€‹gudri puiÅ”i no lielajiem uzņēmumiem mums apliecināja, ka viss bÅ«s labi. Mēs neuzdodam jautājumu: kāpēc patiesÄ«bā tas vispār var darboties? Vai ir kāds formāls pamatojums Ŕādu sistēmu pareizai darbÄ«bai?

Es nesen devos uz Izkliedētās skaitļoÅ”anas skola un mani ļoti iedvesmoja Ŕī tēma. Lekcijas skolā bija vairāk kā skaitļoÅ”anas nodarbÄ«bas, nevis kaut kas saistÄ«ts ar datorsistēmām. Bet tieÅ”i Ŕādi savulaik tika pierādÄ«ti svarÄ«gākie algoritmi, kurus lietojam ikdienā, pat nezinot.

Lielākā daļa mÅ«sdienu sadalÄ«to sistēmu izmanto Paxos konsensa algoritmu un tā dažādās modifikācijas. Pats forŔākais ir tas, ka Ŕī algoritma pamatotÄ«bu un principā arÄ« paÅ”u iespējamÄ«bu var pierādÄ«t vienkārÅ”i ar pildspalvu un papÄ«ru. Praksē algoritms tiek izmantots lielās sistēmās, kas darbojas ar lielu skaitu mezglu mākoņos.

Viegla ilustrācija tam, kas tiks apspriests tālāk: divu ģenerāļu uzdevumsApskatīsim iesildīŔanos divu ģenerāļu uzdevums.

Mums ir divas armijas ā€“ sarkanā un baltā. Baltais karaspēks bāzējas aplenktajā pilsētā. Abās pilsētas pusēs atrodas sarkanās vienÄ«bas Ä£enerāļu A1 un A2 vadÄ«bā. Sarkanmates uzdevums ir uzbrukt baltajai pilsētai un uzvarēt. Tomēr katra sarkanā Ä£enerāļa armija atseviŔķi ir mazāka par balto armiju.

Šrēdingera kaķis bez kastes: vienprātības problēma sadalītajās sistēmās

Uzvaras nosacÄ«jumi sarkanajiem: abiem Ä£enerāļiem jāuzbrukumā vienlaicÄ«gi, lai bÅ«tu skaitliskais pārsvars pār baltajiem. Lai to izdarÄ«tu, Ä£enerāļiem A1 un A2 ir jāvienojas savā starpā. Ja visi uzbruks atseviŔķi, sarkanmates zaudēs.

Lai panāktu vienoÅ”anos, Ä£enerāļi A1 un A2 var nosÅ«tÄ«t viens pie otra sÅ«tņus caur baltās pilsētas teritoriju. Ziņnesis var veiksmÄ«gi sasniegt sabiedroto Ä£enerāli vai arÄ« to var pārtvert ienaidnieks. Jautājums: vai starp sarkanmatainajiem Ä£enerāļiem ir tāda saziņas secÄ«ba (sÅ«tÄ«jumu nosÅ«tÄ«Å”anas secÄ«ba no A1 uz A2 un otrādi no A2 uz A1), kurā viņiem tiek garantēta vienoÅ”anās par uzbrukumu stundā X. LÅ«k, garantijas nozÄ«mē, ka abiem Ä£enerāļiem bÅ«s nepārprotams apstiprinājums, ka sabiedrotais (cits Ä£enerālis) noteikti uzbruks noteiktajā laikā X.

Pieņemsim, ka A1 nosÅ«ta vēstuli uz A2 ar ziņojumu: ā€œUzbruksim Å”odien pusnaktÄ«!ā€ Ä¢enerālis A1 nevar uzbrukt bez Ä£enerāļa A2 apstiprinājuma. Ja ir ieradies sÅ«tnis no A1, tad Ä£enerālis A2 nosÅ«ta apstiprinājumu ar ziņojumu: "Jā, Å”odien nogalināsim baltos." Bet tagad Ä£enerālis A2 nezina, vai viņa sÅ«tnis ir ieradies vai nav, viņam nav garantijas, vai uzbrukums bÅ«s vienlaikus. Tagad General A2 atkal ir nepiecieÅ”ams apstiprinājums.

Ja mēs sÄ«kāk aprakstam viņu saziņu, kļūst skaidrs, ka neatkarÄ«gi no tā, cik daudz ziņojumu apmaiņas ciklu ir, nevar garantēt, ka abi Ä£enerāļi ir saņēmuÅ”i savus ziņojumus (pieņemot, ka kādu no sÅ«tņiem var pārtvert).

Divu Ä£enerāļu problēma ir lielisks piemērs ļoti vienkārÅ”ai sadalÄ«tai sistēmai, kurā ir divi mezgli ar neuzticamu saziņu. Tas nozÄ«mē, ka mums nav 100% garantijas, ka tie ir sinhronizēti. LÄ«dzÄ«gas problēmas plaŔākā mērogā aplÅ«kotas vēlāk rakstā.

Iepazīstinām ar sadalīto sistēmu jēdzienu

Izkliedētā sistēma ir datoru grupa (turpmāk tos sauksim par mezgliem), kas var apmainÄ«ties ar ziņojumiem. Katrs atseviŔķais mezgls ir sava veida autonoma vienÄ«ba. Mezgls var pats apstrādāt uzdevumus, taču, lai sazinātos ar citiem mezgliem, tam ir jānosÅ«ta un jāsaņem ziņojumi.

Kā tieÅ”i tiek Ä«stenoti ziņojumi, kādi protokoli tiek izmantoti - Å”ajā kontekstā tas mÅ«s neinteresē. Ir svarÄ«gi, lai sadalÄ«tas sistēmas mezgli varētu apmainÄ«ties ar datiem savā starpā, nosÅ«tot ziņojumus.

Pati definÄ«cija neizskatās Ä«paÅ”i sarežģīta, taču jāņem vērā, ka izplatÄ«tajai sistēmai ir vairāki atribÅ«ti, kas mums bÅ«s svarÄ«gi.

Sadalīto sistēmu atribūti

  1. VienlaicÄ«ba ā€“ vienlaicÄ«gu vai vienlaicÄ«gu notikumu iespējamÄ«ba sistēmā notikt. Turklāt mēs uzskatÄ«sim, ka notikumi, kas notiek divos dažādos mezglos, ir potenciāli vienlaicÄ«gi, ja vien mums nav skaidras Å”o notikumu raÅ”anās secÄ«bas. Bet, kā likums, mums tā nav.
  2. Nav globālā pulksteņa. Mums nav skaidras notikumu secÄ«bas globālā pulksteņa trÅ«kuma dēļ. Parastajā cilvēku pasaulē mēs esam pieraduÅ”i pie tā, ka mums ir absolÅ«ti pulksteņi un laiks. Viss mainās, kad runa ir par sadalÄ«tām sistēmām. Pat Ä«paÅ”i precÄ«ziem atompulksteņiem ir novirze, un var bÅ«t situācijas, kad mēs nevaram pateikt, kurÅ” no diviem notikumiem notika pirmais. Tāpēc arÄ« uz laiku nevaram paļauties.
  3. Sistēmas mezglu neatkarÄ«ga kļūme. Ir vēl viena problēma: kaut kas var noiet greizi tikai tāpēc, ka mÅ«su mezgli nav mūžīgi. Cietais disks var neizdoties, virtuālā maŔīna mākonÄ« var atsāknēties, tÄ«kls var mirgot un ziņojumi tiks zaudēti. Turklāt var bÅ«t situācijas, kad mezgli darbojas, bet tajā paŔā laikā darbojas pret sistēmu. Pēdējā problēmu klase pat saņēma atseviŔķu nosaukumu: problēma Bizantijas Ä£enerāļi. Populārākais izplatÄ«tās sistēmas piemērs ar Å”o problēmu ir Blockchain. Bet Å”odien mēs neapskatÄ«sim Å”o Ä«paÅ”o problēmu klasi. MÅ«s interesēs situācijas, kurās var neizdoties vienkārÅ”i viens vai vairāki mezgli.
  4. Komunikācijas modeļi (ziņojumapmaiņas modeļi) starp mezgliem. Mēs jau esam noskaidrojuÅ”i, ka mezgli sazinās, apmainoties ar ziņojumiem. Ir divi labi zināmi ziņojumapmaiņas modeļi: sinhronais un asinhronais.

Komunikācijas modeļi starp mezgliem sadalītajās sistēmās

Sinhronais modelis ā€“ mēs noteikti zinām, ka ir zināms ierobežots laika delta, kura laikā ziņojums tiek garantēts no viena mezgla uz otru. Ja Å”is laiks ir pagājis un ziņa nav pienākusi, varam droÅ”i teikt, ka mezgls ir neizdevies. Å ajā modelÄ« mums ir paredzami gaidÄ«Å”anas laiki.

Asinhronais modelis ā€“ asinhronajos modeļos mēs uzskatām, ka gaidÄ«Å”anas laiks ir ierobežots, bet nav tāda laika delta, pēc kuras mēs varētu garantēt, ka mezgls ir atteicies. Tie. Ziņojuma gaidÄ«Å”anas laiks no mezgla var bÅ«t patvaļīgi garÅ”. Å Ä« ir svarÄ«ga definÄ«cija, un mēs par to runāsim tālāk.

Vienprātības jēdziens sadalītās sistēmās

Pirms formāli definējam konsensa jēdzienu, aplÅ«kosim piemēru situācijai, kurā mums tas ir nepiecieÅ”ams, proti - Stāvokļa maŔīnas replikācija.

Mums ir izplatÄ«ts žurnāls. Mēs vēlamies, lai tas bÅ«tu konsekvents un satur identiskus datus par visiem sadalÄ«tās sistēmas mezgliem. Kad viens no mezgliem uzzina jaunu vērtÄ«bu, ko tas ierakstÄ«s žurnālā, tā uzdevums ir piedāvāt Å”o vērtÄ«bu visiem pārējiem mezgliem, lai žurnāls tiktu atjaunināts visos mezglos un sistēma pārietu uz jaunu konsekventu stāvokli. Å ajā gadÄ«jumā ir svarÄ«gi, lai mezgli savā starpā vienotos: visi mezgli piekrÄ«t, ka piedāvātā jaunā vērtÄ«ba ir pareiza, visi mezgli pieņem Å”o vērtÄ«bu, un tikai Å”ajā gadÄ«jumā visi var ierakstÄ«t jauno vērtÄ«bu žurnālā.

Citiem vārdiem sakot: neviens no mezgliem neiebilda, ka tam ir atbilstoŔāka informācija, un piedāvātā vērtÄ«ba bija nepareiza. VienoÅ”anās starp mezgliem un vienoÅ”anās par vienu pareizu pieņemto vērtÄ«bu ir vienprātÄ«ba sadalÄ«tā sistēmā. Tālāk mēs runāsim par algoritmiem, kas ļauj sadalÄ«tai sistēmai garantēt vienprātÄ«bu.
Šrēdingera kaķis bez kastes: vienprātības problēma sadalītajās sistēmās
Formālāk mēs varam definēt konsensa algoritmu (vai vienkārÅ”i konsensa algoritmu) kā noteiktu funkciju, kas pārsÅ«ta sadalÄ«to sistēmu no stāvokļa A uz stāvokli B. Turklāt Å”o stāvokli pieņem visi mezgli, un visi mezgli to var apstiprināt. Kā izrādās, Å”is uzdevums nemaz nav tik triviāls, kā Ŕķiet no pirmā acu uzmetiena.

Konsensa algoritma īpaŔības

Konsensa algoritmam ir jābÅ«t trim Ä«paŔībām, lai sistēma turpinātu pastāvēt un panāktu zināmu progresu, pārejot no stāvokļa uz stāvokli:

  1. VienoÅ”anās ā€“ visiem pareizi strādājoÅ”iem mezgliem jābÅ«t vienādiem (rakstos Ŕī Ä«paŔība tiek saukta arÄ« par droŔības Ä«paŔību). Visiem mezgliem, kas paÅ”laik darbojas (nav izgāzuÅ”ies vai zaudējuÅ”i kontaktu ar citiem), ir jāvienojas un jāpieņem kāda galÄ«gā kopÄ«gā vērtÄ«ba.

    Å eit ir svarÄ«gi saprast, ka sadalÄ«tās sistēmas mezgli, kurus mēs apsveram, vēlas vienoties. Tas ir, mēs tagad runājam par sistēmām, kurās kaut kas var vienkārÅ”i neizdoties (piemēram, kāds mezgls neizdodas), bet Å”ajā sistēmā noteikti nav mezglu, kas apzināti darbojas pret citiem (Bizantijas Ä£enerāļu uzdevums). Pateicoties Å”ai Ä«paŔībai, sistēma paliek konsekventa.

  2. GodÄ«gums ā€” ja visi pareizi strādājoÅ”ie mezgli piedāvā vienādu vērtÄ«bu v, kas nozÄ«mē, ka katram pareizi strādājoÅ”am mezglam ir jāpieņem Ŕī vērtÄ«ba v.
  3. IzbeigÅ”ana ā€“ visi pareizi strādājoÅ”ie mezgli ar laiku iegÅ«s noteiktu vērtÄ«bu (dzÄ«vÄ«bas Ä«paŔību), kas ļauj algoritmam progresēt sistēmā. Katram atseviŔķam pareizi strādājoÅ”am mezglam agrāk vai vēlāk ir jāpieņem galÄ«gā vērtÄ«ba un tā jāapstiprina: "Man Ŕī vērtÄ«ba ir patiesa, es piekrÄ«tu visai sistēmai."

Piemērs tam, kā darbojas konsensa algoritms

Lai gan algoritma Ä«paŔības var nebÅ«t pilnÄ«gi skaidras. Tāpēc ar piemēru ilustrēsim, kādus posmus sistēmā ar sinhronās ziņojumapmaiņas modeli iziet vienkārŔākais konsensa algoritms, kurā visi mezgli funkcionē kā paredzēts, ziņojumi netiek zaudēti un nekas nelÅ«zt (vai tieŔām tā notiek?).

  1. Viss sākas ar laulÄ«bas piedāvājumu (Propose). Pieņemsim, ka klients pieslēdzās mezglam ar nosaukumu "Node 1" un sāka darÄ«jumu, nododot mezglam jaunu vērtÄ«bu - O. Turpmāk mēs izsauksim "Node 1" piedāvājums. Kā ierosinātājs, ā€œNode 1ā€ tagad ir jāpaziņo visai sistēmai, ka tajā ir svaigi dati, un tas nosÅ«ta ziņojumus visiem pārējiem mezgliem: ā€œPaskatieties! NozÄ«me ā€œOā€ man atnāca, un es gribu to pierakstÄ«t! LÅ«dzu, apstipriniet, ka savā žurnālā ierakstÄ«siet arÄ« ā€œOā€.

    Šrēdingera kaķis bez kastes: vienprātības problēma sadalītajās sistēmās

  2. Nākamais posms ir balsoÅ”ana par piedāvāto vērtÄ«bu (BalsoÅ”ana). Kam tas paredzēts? Var gadÄ«ties, ka citi mezgli ir saņēmuÅ”i jaunāku informāciju, un tiem ir dati par to paÅ”u darÄ«jumu.

    Šrēdingera kaķis bez kastes: vienprātības problēma sadalītajās sistēmās

    Kad mezgls ā€œNode 1ā€ nosÅ«ta savu priekÅ”likumu, pārējie mezgli pārbauda savos žurnālos datus par Å”o notikumu. Ja nav pretrunu, mezgli paziņo: ā€œJā, man nav citu datu par Å”o notikumu. ā€œOā€ vērtÄ«ba ir jaunākā informācija, ko esam pelnÄ«juÅ”i.

    Jebkurā citā gadÄ«jumā mezgli var atbildēt uz ā€œNode 1ā€: ā€œKlausieties! Man ir jaunāki dati par Å”o darÄ«jumu. Nevis "O", bet kaut kas labāks."

    BalsoÅ”anas posmā mezgli pieņem lēmumu: vai nu viņi visi pieņem vienu un to paÅ”u vērtÄ«bu, vai arÄ« viens no tiem balso pret, norādot, ka viņam ir jaunāki dati.

  3. Ja balsoÅ”anas kārta bija veiksmÄ«ga un visi bija par, tad sistēma pāriet uz jaunu posmu - VērtÄ«bas pieņemÅ”ana. ā€œNode 1ā€ apkopo visas atbildes no citiem mezgliem un ziņo: ā€œVisi vienojās par vērtÄ«bu ā€œOā€! Tagad es oficiāli paziņoju, ka ā€œOā€ ir mÅ«su jaunā nozÄ«me, visiem vienāda! Pierakstiet to savā mazajā grāmatiņā, neaizmirstiet. Pierakstiet to savā žurnālā!ā€

    Šrēdingera kaķis bez kastes: vienprātības problēma sadalītajās sistēmās

  4. AtlikuÅ”ie mezgli nosÅ«ta apstiprinājumu (pieņemts), ka ir pierakstÄ«juÅ”i vērtÄ«bu ā€œOā€; Å”ajā laikā nekas jauns nav nācis (sava ā€‹ā€‹veida divu fāžu apņemÅ”anās). Pēc Ŕī nozÄ«mÄ«gā notikuma uzskatām, ka izplatÄ«tais darÄ«jums ir pabeigts.
    Šrēdingera kaķis bez kastes: vienprātības problēma sadalītajās sistēmās

Tādējādi vienprātÄ«bas algoritms vienkārŔā gadÄ«jumā sastāv no četriem soļiem: ierosināt, balsot (balsot), pieņemt (akceptēt), apstiprināt pieņemÅ”anu (akceptēts).

Ja kādā solÄ« nevarējām panākt vienoÅ”anos, tad algoritms sākas no jauna, ņemot vērā to mezglu sniegto informāciju, kuri atteicās apstiprināt piedāvāto vērtÄ«bu.

Konsensa algoritms asinhronā sistēmā

Pirms tam viss bija gludi, jo mēs runājām par sinhronās ziņojumapmaiņas modeli. Taču mēs zinām, ka mÅ«sdienu pasaulē esam pieraduÅ”i visu darÄ«t asinhroni. Kā lÄ«dzÄ«gs algoritms darbojas sistēmā ar asinhrono ziņojumapmaiņas modeli, kur mēs uzskatām, ka atbildes gaidÄ«Å”anas laiks no mezgla var bÅ«t patvaļīgi garÅ” (starp citu, mezgla atteici var uzskatÄ«t arÄ« par piemēru, kad mezgls var reaģēt patvaļīgi ilgu laiku).

Tagad, kad mēs zinām, kā principā darbojas konsensa algoritms, jautājums tiem zinātkārajiem lasÄ«tājiem, kuri ir tikuÅ”i lÄ«dz Å”im: cik mezglu N mezglu sistēmā ar asinhrono ziņojuma modeli var neizdoties, lai sistēma joprojām varētu panākt vienprātÄ«bu?

Pareizā atbilde un pamatojums ir aiz spoilera.Pareizā atbilde ir: 0. Ja pat viens mezgls asinhronā sistēmā neizdodas, sistēma nevarēs panākt vienprātÄ«bu. Å is apgalvojums ir pierādÄ«ts FLP teorēmā, kas ir labi zināma noteiktās aprindās (1985, Fischer, Lynch, Paterson, saite uz oriÄ£inālu raksta beigās): ā€œNeiespējamÄ«ba panākt sadalÄ«tu vienprātÄ«bu, ja vismaz viens mezgls neizdodas. ā€.
Šrēdingera kaķis bez kastes: vienprātības problēma sadalītajās sistēmās
PuiÅ”i, tad mums ir problēma, esam pieraduÅ”i, ka viss ir asinhroni. Un Å”eit tas ir. Kā turpināt dzÄ«vot?

Mēs tikai runājām par teoriju, par matemātiku. Ko nozÄ«mē ā€œvienprātÄ«bu nevar panāktā€, tulkojot no matemātikas valodas mÅ«sējā - inženierzinātnēs? Tas nozÄ«mē, ka ā€œne vienmēr var sasniegtā€, t.i. Ir gadÄ«jums, kad vienprātÄ«ba nav panākama. Kas tas par lietu?

Tas ir tieÅ”i iepriekÅ” aprakstÄ«tais dzÄ«vÄ«guma Ä«paŔību pārkāpums. Mums nav kopÄ«gas vienoÅ”anās, un sistēma nevar progresēt (nevar pabeigt ierobežotā laikā), ja mums nav atbildes no visiem mezgliem. Tā kā asinhronā sistēmā mums nav paredzama reakcijas laika, un mēs nevaram zināt, vai mezgls ir avarējis vai vienkārÅ”i prasa ilgu laiku, lai reaģētu.

Bet praksē mēs varam atrast risinājumu. Ļaujiet mūsu algoritmam darboties ilgu laiku kļūmju gadījumā (iespējams, tas var darboties bezgalīgi). Bet vairumā gadījumu, kad vairums mezglu darbojas pareizi, sistēma progresēs.

Praksē mēs nodarbojamies ar daļēji sinhroniem komunikācijas modeļiem. Daļējā sinhronija tiek saprasta Ŕādi: vispārÄ«gā gadÄ«jumā mums ir asinhrons modelis, bet formāli tiek ieviests noteikta laika momenta ā€œglobālās stabilizācijas laikaā€ jēdziens.

Å is laika brÄ«dis var nepienākt ilgi, bet kādu dienu tam ir jāpienāk. Skanēs virtuālais modinātājs, un no Ŕī brīža mēs varam paredzēt laika delta, par kuru ziņojumi tiks saņemti. No Ŕī brīža sistēma pārvērÅ”as no asinhronas uz sinhronu. Praksē mēs strādājam tieÅ”i ar Ŕādām sistēmām.

Paxos algoritms atrisina vienprātības problēmas

paxos ir algoritmu saime, kas atrisina vienprātÄ«bas problēmu daļēji sinhronām sistēmām, ņemot vērā iespēju, ka daži mezgli var neizdoties. Paxos autors ir Leslija Lamporta. ViņŔ 1989. gadā ierosināja formālu pierādÄ«jumu par algoritma esamÄ«bu un pareizÄ«bu.

Taču pierādÄ«jumi izrādÄ«jās nebÅ«t ne triviāli. Pirmā publikācija tika izdota tikai 1998. gadā (33 lappuses), kurā aprakstÄ«ts algoritms. Kā izrādÄ«jās, to bija ārkārtÄ«gi grÅ«ti saprast, un 2001. gadā tika publicēts raksta skaidrojums, kas aizņēma 14 lappuses. Publikāciju apjoms dots, lai parādÄ«tu, ka patiesÄ«bā vienprātÄ«bas problēma nebÅ«t nav vienkārÅ”a un aiz Ŕādiem algoritmiem slēpjas milzÄ«gs gudrāko cilvēku darbs.

Interesanti, ka pats Leslijs Lamports savā lekcijā atzÄ«mēja, ka otrajā skaidrojoÅ”ajā rakstā ir viens apgalvojums, viena rindiņa (viņŔ neprecizēja, kura), ko var dažādi interpretēt. Un Ŕī iemesla dēļ liela daļa mÅ«sdienu Paxos implementāciju nedarbojas pilnÄ«gi pareizi.

Detalizēta Paksosa darba analÄ«ze prasÄ«s vairāk nekā vienu rakstu, tāpēc mēģināŔu ļoti Ä«si izklāstÄ«t algoritma galveno ideju. Mana raksta beigās esoÅ”ajās saitēs jÅ«s atradÄ«sit materiālus turpmākai nirÅ”anai Å”ajā tēmā.

Lomas uzņēmumā Paxos

Paxos algoritmam ir lomu koncepcija. Apsvērsim trīs galvenās (ir modifikācijas ar papildu lomām):

  1. PriekÅ”likumu iesniedzēji (var lietot arÄ« terminus: vadÄ«tāji vai koordinatori). Tie ir puiÅ”i, kuri uzzina par kādu jaunu vērtÄ«bu no lietotāja un uzņemas lÄ«dera lomu. Viņu uzdevums ir uzsākt jaunu vērtÄ«bu priekÅ”likumu kārtu un koordinēt tālāko mezglu darbÄ«bu. Turklāt Paxos pieļauj vairāku lÄ«deru klātbÅ«tni noteiktās situācijās.
  2. Pieņēmēji (balsotāji). Tie ir mezgli, kas balso par noteiktas vērtÄ«bas pieņemÅ”anu vai noraidÄ«Å”anu. Viņu loma ir ļoti svarÄ«ga, jo no viņiem atkarÄ«gs lēmums: kādā stāvoklÄ« sistēma nonāks (vai nenonāks) pēc konsensa algoritma nākamā posma.
  3. izglÄ«tojamajiem. Mezgli, kas vienkārÅ”i pieņem un ieraksta jauno pieņemto vērtÄ«bu, kad sistēmas stāvoklis ir mainÄ«jies. Viņi nepieņem lēmumus, viņi tikai saņem datus un var tos nodot gala lietotājam.

Viens mezgls dažādās situācijās var apvienot vairākas lomas.

Kvoruma jēdziens

Mēs pieņemam, ka mums ir sistēma N mezgli Un no tiem maksimums F mezgli var neizdoties. Ja F mezgli neizdodas, tad mums ir jābūt vismaz 2F+1 akceptora mezgli.

Tas ir nepiecieÅ”ams, lai mums vienmēr bÅ«tu lielākā daļa "labo" mezglu, kas darbojas pareizi, pat vissliktākajā situācijā. Tas ir F+1 "labi" mezgli, kas vienojās, un tiks pieņemta galÄ«gā vērtÄ«ba. Pretējā gadÄ«jumā var rasties situācija, ka mÅ«su dažādās vietējās grupas iegÅ«st dažādas nozÄ«mes un nevar vienoties savā starpā. Tāpēc mums ir nepiecieÅ”ams absolÅ«tais vairākums, lai balsojumā uzvarētu.

Vispārēja ideja par to, kā darbojas Paxos konsensa algoritms

Paxos algoritms ietver divas lielas fāzes, kuras savukārt ir sadalītas divos posmos:

  1. 1.a fāze: sagatavojieties. SagatavoÅ”anas posmā vadÄ«tājs (priekÅ”likuma iesniedzējs) informē visus mezglus: ā€œSākam jaunu balsoÅ”anas posmu. Mums ir jauna kārta. Å Ä«s kārtas numurs ir n. Tagad mēs sāksim balsot." Pagaidām tas vienkārÅ”i ziņo par jauna cikla sākumu, bet neziņo par jaunu vērtÄ«bu. Å Ä« posma uzdevums ir uzsākt jaunu kārtu un informēt visus par tās unikālo numuru. Apaļais skaitlis ir svarÄ«gs, tam ir jābÅ«t lielākai par visiem iepriekŔējiem balsoÅ”anas cipariem no visiem iepriekŔējiem lÄ«deriem. Jo tieÅ”i pateicoties apaļajam skaitlim, citi sistēmas mezgli sapratÄ«s, cik jaunāki ir lÄ«dera dati. Visticamāk, ka citiem mezgliem jau ir balsoÅ”anas rezultāti no daudz vēlākām kārtām un viņi vienkārÅ”i pateiks lÄ«derim, ka viņŔ ir atpalicis no laika.
  2. 1.b fāze: solÄ«jums. Kad pieņemÅ”anas mezgli ir saņēmuÅ”i jaunā balsoÅ”anas posma numuru, ir iespējami divi rezultāti:
    • Jaunā balsojuma skaitlis n ir lielāks par jebkura iepriekŔējā balsojuma skaitu, kurā piedalÄ«jās akceptētājs. Tad akceptētājs nosÅ«ta vadÄ«tājam solÄ«jumu, ka vairs nepiedalÄ«sies balsojumos, kuru skaitlis ir mazāks par n. Ja akceptētājs par kaut ko jau ir nobalsojis (tas ir, jau ir pieņēmis kādu vērtÄ«bu otrajā fāzē), tad tas savam solÄ«jumam pievieno pieņemto vērtÄ«bu un balsojuma numuru, kurā piedalÄ«jās.
    • Pretējā gadÄ«jumā, ja akceptētājs jau zina par balsojumu ar augstāku numuru, tas var vienkārÅ”i ignorēt sagatavoÅ”anās soli un neatbildēt vadÄ«tājam.
  3. 2.a fāze: pieņem. LÄ«derim jāsagaida atbilde no kvoruma (lielākā daļa sistēmas mezglu) un, ja tiek saņemts nepiecieÅ”amais atbilžu skaits, viņam ir divas notikumu attÄ«stÄ«bas iespējas:
    • Daži no akceptētājiem nosÅ«tÄ«ja vērtÄ«bas, par kurām jau bija nobalsojuÅ”i. Å ajā gadÄ«jumā vadÄ«tājs izvēlas vērtÄ«bu no balsojuma ar maksimālo skaitu. Nosauksim Å”o vērtÄ«bu x, un tā nosÅ«ta ziņojumu visiem mezgliem, piemēram: ā€œPieņemt (n, x)ā€, kur pirmā vērtÄ«ba ir balsoÅ”anas numurs no paÅ”a Ierosināt soļa, bet otrā vērtÄ«ba ir tā, par ko visi pulcējās, t.i. vērtÄ«ba, par kuru mēs faktiski balsojam.
    • Ja neviens no akceptētājiem neatsÅ«tÄ«ja nekādas vērtÄ«bas, bet viņi vienkārÅ”i apsolÄ«ja balsot Å”ajā kārtā, vadÄ«tājs var aicināt viņus balsot par savu vērtÄ«bu, par kuru viņŔ vispirms kļuva par lÄ«deri. Sauksim to par y. Tas nosÅ«ta ziņojumu visiem mezgliem, piemēram: ā€œPieņemt (n, y)ā€, lÄ«dzÄ«gi kā iepriekŔējais rezultāts.
  4. 2.b posms: pieņemts. Turklāt akceptormezgli, saņemot no vadÄ«tāja ziņojumu ā€œPieņemt(...)ā€, tam piekrÄ«t (visiem mezgliem nosÅ«ta apstiprinājumu, ka viņi piekrÄ«t jaunajai vērtÄ«bai) tikai tad, ja nav apsolÄ«juÅ”i kādu (citu) ) lÄ«deris piedalÄ«ties balsoÅ”anā ar apaļu numuru n'> n, pretējā gadÄ«jumā viņi ignorē apstiprinājuma pieprasÄ«jumu.

    Ja lielākā daļa mezglu atbildēja līderim un visi apstiprināja jauno vērtību, tad jaunā vērtība tiek uzskatīta par pieņemtu. Urrā! Ja vairākums netiek sasniegts vai ir mezgli, kas atteicās pieņemt jauno vērtību, tad viss sākas no jauna.

Šādi darbojas Paxos algoritms. Katram no Å”iem posmiem ir daudz smalkumu, mēs praktiski neuzskatÄ«jām dažāda veida neveiksmes, vairāku vadÄ«tāju problēmas un daudz ko citu, taču Ŕī raksta mērÄ·is ir tikai iepazÄ«stināt lasÄ«tāju ar izplatÄ«tās skaitļoÅ”anas pasauli augstā lÄ«menÄ«.

Ir arÄ« vērts atzÄ«mēt, ka Paxos nav vienÄ«gais Ŕāda veida produkts, ir arÄ« citi algoritmi, piemēram, Plosts, bet Ŕī ir cita raksta tēma.

Saites uz materiāliem turpmākai izpētei

Iesācēja līmenis:

Leslijas Lamportas līmenis:

Avots: www.habr.com

Pievieno komentāru