Do ni imagu. 5 katoj estas ŝlositaj en la ĉambro, kaj por iri veki la posedanton, ili devas ĉiuj interkonsenti pri tio, ĉar ili povas malfermi la pordon nur apogante sin sur ĝi kun kvin el ili. Se unu el la katoj estas la kato de Schrödinger kaj la aliaj katoj ne konscias pri lia decido, leviĝas la demando: "Kiel ili povas fari ĉi tion?"
En ĉi tiu artikolo, mi rakontos al vi en simplaj terminoj pri la teoria komponanto de la mondo de distribuitaj sistemoj kaj la principoj de ilia laboro. Kaj ankaŭ supraĵe konsideru la ĉefideon subesta Paxos'a.
Kiam programistoj uzas nubajn infrastrukturojn, diversajn datumbazojn, laboras en aretoj de granda nombro da nodoj, ili certas, ke la datumoj estos konsekvencaj, sekuraj kaj ĉiam disponeblaj. Sed kie estas la garantioj?
Fakte, la garantioj, kiujn ni havas, estas provizantaj garantioj. Ili estas priskribitaj en la dokumentado jene: "Ĉi tiu servo estas sufiĉe fidinda, ĝi havas donitan SLA, ne maltrankviliĝu, ĉio funkcios distribuita kiel vi atendas."
Ni emas kredi je la plej bona, ĉar inteligentaj onkloj de grandaj kompanioj certigis al ni, ke ĉio estos en ordo. Ni ne faras la demandon: kial, fakte, ĉi tio povas funkcii? Ĉu estas iu formala pravigo por la ĝusta funkciado de tiaj sistemoj?
Mi ĵus iris al kaj estis tre inspirita de ĉi tiu temo. Prelegoj en la lernejo estis pli kiel klasoj en matematika analizo ol io ajn rilata al komputilsistemoj. Sed ĝuste tiel la plej gravaj algoritmoj, kiujn ni uzas ĉiutage, sen suspekti ĝin, estis pruvitaj samtempe.
La plej multaj modernaj distribuitaj sistemoj uzas la Paxos-interkonsentalgoritmon kaj ĝiajn diversajn modifojn. La plej bonega afero estas, ke la valideco kaj, principe, la ebleco mem de la ekzisto de ĉi tiu algoritmo povas esti pruvitaj simple per plumo kaj papero. Samtempe, praktike, la algoritmo estas uzata en grandaj sistemoj funkciigantaj sur grandega nombro da nodoj en la nuboj.
Malpeza ilustraĵo de tio, kio estos diskutita poste: la problemo de du generalojNi rigardu la varmigon .
Ni havas du armeojn - ruĝan kaj blankan. Blankaj trupoj baziĝas en la sieĝita urbo. Ruĝaj trupoj gviditaj fare de generaloj A1 kaj A2 situas sur du flankoj de la grandurbo. La tasko de la ruĝharuloj estas ataki la blankan urbon kaj venki. Tamen, la armeo de ĉiu ruĝa generalo individue estas pli malgranda ol la armeo de blankuloj.
Venkkondiĉoj por la ruĝharuloj: ambaŭ generaloj devas samtempe ataki por havi nombran avantaĝon super la blankuloj. Por fari tion, generaloj A1 kaj A2 devas konsenti unu kun la alia. Se ĉiuj atakas aparte, la ruĝharuloj perdos.
Por intertrakti, generaloj A1 kaj A2 povas sendi mesaĝistojn unu al la alia tra la teritorio de la blanka urbo. La mesaĝisto povas sukcese atingi aliancan generalon, aŭ povas esti kaptita fare de la malamiko. Demando: ĉu ekzistas tia sinsekvo de komunikadoj inter la ruĝharaj generaloj (la sinsekvo de sendado de mesaĝistoj de A1 al A2 kaj inverse de A2 al A1), en kiu ili estas garantiite konsenti pri atako je la X-a horo. Jen, per garantioj oni komprenas, ke ambaŭ generaloj havos senduban konfirmon, ke aliancano (alia generalo) atakos ĝuste en la difinita tempo X.
Supozu, ke A1 sendas mesaĝiston al A2 kun la mesaĝo: "Ni ataku hodiaŭ noktomeze!". Generalo A1 ne povas ataki sen konfirmo de Generalo A2. Se la mesaĝisto de A1 atingis, tiam generalo A2 sendas konfirmon kun la mesaĝo: "Jes, ni plenigu la blankulojn hodiaŭ." Sed nun Generalo A2 ne scias ĉu lia mesaĝisto atingis aŭ ne, li ne havas garantiojn ĉu la atako estos samtempa. Nun Generalo A2 denove bezonas konfirmon.
Se ni priskribas ilian komunikadon plu, rezultas jene: kiom ajn da mesaĝ-interŝanĝaj cikloj estas, ne estas maniero garantii ambaŭ generalojn, ke iliaj mesaĝoj estas ricevitaj (supoze ke iu el la mesaĝistoj povas esti kaptita).
La du ĝeneralaj problemo estas bonega ilustraĵo de tre simpla distribuita sistemo kie estas du nodoj kun nefidinda komunikado. Do ni ne havas 100% garantion ke ili estas sinkronigitaj. Pri similaj problemoj nur pligrandskale poste en la artikolo.
Enkonduko de la koncepto de distribuitaj sistemoj
Distribuita sistemo estas grupo de komputiloj (ĉi-poste nomataj nodoj), kiuj povas interŝanĝi mesaĝojn. Ĉiu individua nodo estas iu aŭtonoma ento. Nodo povas prilabori taskojn memstare, sed por komuniki kun aliaj nodoj, ĝi bezonas sendi kaj ricevi mesaĝojn.
Kiel mesaĝoj estas specife efektivigitaj, kiaj protokoloj estas uzataj - ĉi tio ne interesas nin en ĉi tiu kunteksto. Gravas, ke la nodoj de distribuita sistemo povas interŝanĝi datumojn inter si sendante mesaĝojn.
La difino mem ne aspektas tre komplika, sed memoru, ke distribuita sistemo havas kelkajn atributojn, kiuj estos gravaj por ni.
Atributoj de distribuitaj sistemoj
- Concurrency – la ebleco de okazo de samtempaj aŭ konkurencivaj eventoj en la sistemo. Plie, ni konsideros, ke eventoj okazintaj sur du malsamaj nodoj estas eble samtempaj ĝis ni havas klaran ordon en kiu ĉi tiuj eventoj okazas. Kaj kutime ni ne faras.
- Neniu tutmonda horloĝo. Ni ne havas klaran ordon de eventoj pro la manko de tutmonda horloĝo. En la ordinara mondo de homoj, ni kutimas al tio, ke ni havas horojn kaj tempon absolute. Ĉio ŝanĝiĝas kiam temas pri distribuitaj sistemoj. Eĉ ultraprecizaj atomhorloĝoj havas drivon, kaj estas situacioj kie ni ne povas diri kiu el du eventoj okazis unue. Tial ni ankaŭ ne povas fidi pri tempo.
- Sendependa fiasko de sistemaj nodoj. Estas alia problemo: io povas misfunkcii simple ĉar niaj nodoj ne estas eternaj. La malmola disko povas malsukcesi, la virtuala maŝino en la nubo povas rekomenci, la reto povas palpebrumi kaj mesaĝoj estos perditaj. Plie, estas situacioj, kiam la nodoj funkcias, sed samtempe ili funkcias kontraŭ la sistemo. La lasta klaso de problemoj eĉ ricevis apartan nomon: la problemo . La plej populara ekzemplo de distribuita sistemo kun tia problemo estas Blockchain. Sed hodiaŭ ni ne konsideros ĉi tiun specialan klason de problemoj. Ni interesiĝos pri situacioj, en kiuj nur unu aŭ pluraj nodoj povas malsukcesi.
- Komunikaj modeloj (mesaĝaj modeloj) inter nodoj. Ni jam eksciis, ke nodoj komunikas per interŝanĝado de mesaĝoj. Estas du konataj mesaĝaj modeloj: sinkrona kaj nesinkrona.
Modeloj de komunikado inter nodoj en distribuitaj sistemoj
Sinkrona modelo - ni scias certe, ke ekzistas finia konata delto de tempo por kiu la mesaĝo estas garantiita atingi de unu nodo al alia. Se ĉi tiu tempo finiĝas kaj la mesaĝo ne alvenis, ni povas sekure diri, ke la nodo malsukcesis. En tia modelo, ni havas antaŭvideblan atendan tempon.
Nesinkrona modelo – en nesinkronaj modeloj, ni supozas ke la atendotempo estas finhava, sed ne ekzistas tempodelto post kiu oni povas garantii ke la nodo malsukcesis. Tiuj. la atendotempo por mesaĝo de nodo povas esti arbitre longa. Ĉi tio estas grava difino, kaj pri ĝi ni parolos plu.
La koncepto de konsento en distribuitaj sistemoj
Antaŭ formale difini la koncepton de konsento, konsideru ekzemplon de situacio kie ni bezonas ĝin, nome − Ŝtata Maŝina Reproduktado.
Ni havas kelkajn distribuitajn protokolojn. Ni ŝatus, ke ĝi estu konsekvenca kaj enhavu identajn datumojn pri ĉiuj nodoj de distribuita sistemo. Kiam unu el la nodoj lernas novan valoron, kiun ĝi skribos al la protokolo, ĝia tasko estas oferti ĉi tiun valoron al ĉiuj aliaj nodoj tiel ke la protokolo estas ĝisdatigita sur ĉiuj nodoj, kaj la sistemo ŝanĝas al nova konsekvenca stato. Samtempe gravas, ke la nodoj konsentas inter si: ĉiuj nodoj konsentas, ke la proponita nova valoro estas ĝusta, ĉiuj nodoj akceptas ĉi tiun valoron, kaj nur ĉi-kaze ĉiuj povas registri novan valoron.
Alivorte: neniu el la nodoj kontraŭis, ke ili havas pli ĝisdatigitajn informojn, kaj la proponita valoro estis malĝusta. Interkonsento inter nodoj kaj interkonsento pri ununura ĝusta akceptita valoro estas la interkonsento en distribuita sistemo. Tuj poste, ni parolos pri algoritmoj, kiuj permesas distribuitan sistemon atingi konsenton kun garantiita.
Pli formale, ni povas difini konsentan algoritmon (aŭ simple konsentan algoritmon) kiel iun funkcion, kiu prenas distribuitan sistemon de ŝtato A al ŝtato B. Plie, ĉi tiu stato estas akceptita de ĉiuj nodoj, kaj ĉiuj nodoj povas konfirmi ĝin. Kiel rezultas, ĉi tiu tasko tute ne estas tiel bagatela kiel ŝajnas unuavide.
Propraĵoj de la konsenta algoritmo
La interkonsentalgoritmo devas havi tri trajtojn por ke la sistemo daŭre ekzistu kaj havu iom da progreso en la transiro de ŝtato al ŝtato:
- interkonsento – ĉiuj ĝuste laborantaj nodoj devas preni la saman valoron (en artikoloj ĉi tiu posedaĵo troviĝas ankaŭ kiel sekureca posedaĵo). Ĉiuj nodoj, kiuj nun funkcias (ne malorde kaj ne perdis kontakton kun la ceteraj) devas interkonsenti kaj akcepti iun finan komunan valoron.
Estas grave kompreni ĉi tie, ke la nodoj en la distribuita sistemo, kiun ni pripensas, volas konsenti. Tio estas, ni nun parolas pri sistemoj, en kiuj io povas simple malsukcesi (ekzemple, iu nodo malsukcesas), sed en ĉi tiu sistemo certe ne ekzistas nodoj, kiuj intence funkcias kontraŭ aliaj (tasko de la bizancaj generaloj). Pro ĉi tiu posedaĵo, la sistemo restas konsekvenca.
- integreco - se ĉiuj ĝuste laborantaj nodoj ofertas la saman valoron v, do ĉiu ĝuste funkcianta nodo devas akcepti ĉi tiun valoron v.
- finaĵo - ĉiuj ĝuste laborantaj nodoj eventuale alprenos iom da valoro (viveca posedaĵo), kio permesas al la algoritmo havi progreson en la sistemo. Ĉiu individua nodo, kiu funkcias ĝuste, pli aŭ malpli frue devas akcepti la finan valoron kaj konfirmi ĝin: "Por mi, ĉi tiu valoro estas vera, mi konsentas kun la tuta sistemo."
Ekzemplo de kiel funkcias la konsenta algoritmo
Dum la propraĵoj de la algoritmo eble ne estas tute klaraj. Tial ni ilustros per ekzemplo, kiajn stadiojn trairas la plej simpla konsenta algoritmo en sistemo kun sinkrona mesaĝa modelo, en kiu ĉiuj nodoj funkcias kiel atendite, mesaĝoj ne perdiĝas kaj nenio rompas (ĉu tio vere okazas?).
- Ĉio komenciĝas per edziĝpropono (Proponi). Supozu kliento konektas al nodo nomita "Nodo 1" kaj komencas transakcion, pasante novan valoron al la nodo - O. De nun, ni nomos "Nodo 1" proponi. Ĉar la proponanto "Nodo 1" nun devas sciigi al la tuta sistemo, ke li havas freŝajn datumojn, kaj li sendas mesaĝojn al ĉiuj aliaj nodoj: "Rigardu! Mi ricevis la valoron "O", kaj mi volas skribi ĝin! Bonvolu konfirmi, ke vi ankaŭ registros "O" en via protokolo."
- La sekva etapo estas voĉdonado por la proponita valoro (Voĉdonado). Por kio ĝi estas? Povas okazi, ke aliaj nodoj ricevis pli freŝajn informojn, kaj ili havas datumojn pri la sama transakcio.
Kiam la nodo "Nodo 1" sendas sian proponon, la aliaj nodoj kontrolas siajn protokolojn por datumoj pri ĉi tiu evento. Se ne ekzistas konflikto, la nodoj anoncas: "Jes, mi ne havas aliajn datumojn por ĉi tiu evento. La "O" valoro estas la plej ĝisdata informo kiun ni meritas."En ajna alia kazo, la nodoj povas respondi al "Nodo 1": "Aŭskultu! Mi havas pli freŝajn datumojn pri ĉi tiu transakcio. Ne "Ho", sed io pli bona."
En la voĉdonadstadio, la nodoj venas al decido: aŭ ili ĉiuj akceptas la saman valoron, aŭ unu el ili voĉdonas kontraŭ, indikante ke li havas pli freŝajn datumojn.
- Se la voĉdonada rondo sukcesis, kaj ĉiuj estis favoraj, tiam la sistemo moviĝas al nova etapo - akcepto de la valoro (Akceptu). "Nodo 1" kolektas ĉiujn respondojn de aliaj nodoj kaj raportas: "Ĉiuj konsentis pri la valoro 'O'! Nun mi oficiale deklaras, ke "O" estas nia nova signifo, la sama por ĉiuj! Skribu ĝin en vian kajeron, ne forgesu. Skribu al via protokolo!"
- La ceteraj nodoj sendas konfirmon (Akceptitaj), ke ili notis la valoron "O" por si, nenio nova estis ricevita dum ĉi tiu tempo (ia dufaza kommit). Post ĉi tiu grava evento, ni konsideras, ke la distribuita transakcio finiĝis.
Tiel, la konsenta algoritmo en simpla kazo konsistas el kvar paŝoj: proponi, voĉdoni (voĉdonado), akcepto (akcepti), konfirmo de akcepto (akceptita).
Se en iu paŝo ni ne povis atingi interkonsenton, tiam la algoritmo estas rekomencita, konsiderante la informojn provizitajn de la nodoj, kiuj rifuzis konfirmi la proponitan valoron.
Interkonsenta algoritmo en nesinkrona sistemo
Antaŭ tio ĉio estis glata, ĉar temis pri la sinkrona mesaĝa modelo. Sed ni scias, ke en la moderna mondo ni kutimas fari ĉion nesinkrone. Kiel funkcias simila algoritmo en sistemo kun nesinkrona mesaĝmodelo, kie ni kredas, ke la atendotempo de respondo de nodo povas esti arbitre longa (cetere, noda fiasko ankaŭ povas esti konsiderata kiel ekzemplo kiam nodo povas respondi arbitre longe).
Nun kiam ni scias kiel principe funkcias la konsenta algoritmo, la demando estas por tiuj scivolaj legantoj, kiuj atingis ĉi tiun punkton: kiom da nodoj en sistemo de N nodoj kun nesinkrona mesaĝmodelo povas malsupreniri tiel ke la sistemo ankoraŭ povas atingi konsenton. ?
La ĝusta respondo kaj raciaĵo malantaŭ la spoiler.La ĝusta respondo estas: 0. Se eĉ unu nodo en nesinkrona sistemo malaltiĝas, la sistemo ne povos atingi konsenton. Ĉi tiu deklaro estas pruvita en la konata FLP-teoremo (1985, Fischer, Lynch, Paterson, ligo al la originalo ĉe la fino de la artikolo): "La malebleco atingi distribuitan konsenton se almenaŭ unu nodo malsukcesas."
Uloj, tiam ni havas problemon, ni kutimas, ke ĉio estas nesinkrona kun ni. Kaj jen ĝi. Kiel daŭre vivi?
Ni ĵus parolis pri teorio, pri matematiko. Kion signifas "konsento ne atingebla", tradukante el matematika lingvo en la nian - inĝenieristikon? Tio signifas ke "ne ĉiam povas esti atingita", t.e. estas kazo en kiu konsento ne estas realigebla. Kaj kio estas ĉi tiu kazo?
Ĉi tio estas ĝuste la malobservo de la viveca posedaĵo priskribita supre. Ni ne havas komunan interkonsenton, kaj la sistemo ne povas progresi (ne povas finiĝi en finia tempo) en la kazo kie ni ne havas respondon de ĉiuj nodoj. Ĉar en nesinkrona sistemo ni ne havas antaŭvideblan respondtempon kaj ni ne povas scii ĉu nodo malfunkcias aŭ nur bezonas longan tempon por respondi.
Sed en la praktiko, ni povas trovi solvon. Nia algoritmo povu funkcii dum longa tempo en kazo de malsukcesoj (ĝi eble povas funkcii senfine). Sed en la plej multaj situacioj, kiam la plej multaj el la nodoj funkcias ĝuste, ni havos progreson en la sistemo.
En la praktiko, ni traktas parte sinkronajn komunikadmodelojn. Parta sinkronismo estas komprenata jene: en la ĝenerala kazo, ni havas nesinkronan modelon, sed certa koncepto de "tutmonda stabiligtempo" de certa tempopunkto estas formale enkondukita.
Ĉi tiu momento eble ne venos por arbitre longa tempo, sed iam ĝi devas veni. La virtuala vekhorloĝo sonoros, kaj ekde tiu momento ni povas antaŭdiri la tempodelton, en kiu atingos la mesaĝoj. De ĉi tiu punkto, la sistemo turnas de nesinkrona al sinkrona. En la praktiko, ni traktas tiajn sistemojn.
Paxos-algoritmo solvas konsentajn problemojn
estas familio de algoritmoj kiuj solvas la interkonsentproblemon por parte sinkronaj sistemoj, kondiĉe ke kelkaj nodoj povas malsukcesi. La aŭtoro de Paxos estas . Li proponis formalan pruvon de la ekzisto kaj ĝusteco de la algoritmo en 1989.
Sed la pruvo montriĝis tute ne bagatela. La unua eldonaĵo estis publikigita nur en 1998 (33 paĝoj) priskribante la algoritmon. Kiel montriĝis, ĝi estis ege malfacile komprenebla, kaj en 2001 estis publikigita klarigo por la artikolo, kiu daŭris 14 paĝojn. La volumoj de publikaĵoj estas donitaj por montri, ke fakte la problemo de konsento tute ne estas simpla, kaj malantaŭ tiaj algoritmoj estas grandega laboro de la plej inteligentaj homoj.
Estas interese, ke Leslie Lampor mem en sia prelego notis, ke en la dua artikol-klarigo estas unu eldiro, unu linio (li ne precizigis kiun), kiuj estas diversmaniere interpreteblaj. Kaj pro tio, granda nombro da modernaj Paxos-efektivigoj ne funkcias tute ĝuste.
Detala analizo de la laboro de Paxos prenos pli ol unu artikolon, do mi provos transdoni la ĉefan ideon de la algoritmo tre mallonge. En la ligiloj ĉe la fino de mia artikolo vi trovos materialojn por plua plonĝi en ĉi tiun temon.
Roloj ĉe Paxos
La Paxos-algoritmo havas koncepton de roloj. Konsideru tri ĉefajn (estas modifoj kun pliaj roloj):
- Proponantoj (povas ekzisti ankaŭ terminoj: gvidantoj aŭ kunordigantoj). Ĉi tiuj estas la uloj kiuj lernas pri iu nova signifo de la uzanto kaj prenas la rolon de gvidanto. Ilia tasko estas lanĉi rondon de proponoj por nova valoro kaj kunordigi pliajn agojn de la nodoj. Krome, Paxos permesas la ĉeeston de pluraj gvidantoj en certaj situacioj.
- Akceptantoj (balotantoj). Ĉi tiuj estas la nodoj, kiuj voĉdonas por akcepti aŭ malakcepti apartan valoron. Ilia rolo estas tre grava, ĉar la decido dependas de ili: al kia stato la sistemo iros (aŭ ne iros) post la sekva etapo de la konsenta algoritmo.
- Lernantoj. Nodoj kiuj simple akceptas kaj skribas la novan ricevitan valoron kiam la stato de la sistemo ŝanĝiĝis. Ili ne faras decidojn, ili nur ricevas datumojn kaj povas doni ĝin al la fina uzanto.
Unu nodo povas kombini plurajn rolojn en malsamaj situacioj.
La koncepto de kvorumo
Ni supozas, ke ni havas sistemon de N nodoj. Kaj la plimulto el ili F nodoj povas malsukcesi. Se F-nodoj malsukcesas, tiam ni devus havi almenaŭ 2F+1 akceptantaj nodoj.
Ĉi tio estas necesa por ke ni ĉiam, eĉ en la plej malbona situacio, "bonaj", ĝuste laborantaj nodoj havu plimulton. Tio estas f+1 "bonaj" nodoj kiuj konsentis, kaj la fina valoro estos akceptita. Alie, povas esti situacio, kie malsamaj lokaj grupoj alprenos malsamajn signifojn kaj ne povos interkonsenti inter si. Do ni bezonas absolutan plimulton por gajni la voĉdonon.
Ĝenerala ideo de la algoritmo de konsento de Paxos
La Paxos-algoritmo supozas du grandajn fazojn, kiuj siavice estas dividitaj en du ŝtupojn ĉiu:
- Fazo 1a: Preparu. Dum la prepara etapo, la gvidanto (proponanto) informas ĉiujn nodojn: “Ni komencas novan voĉdonan etapon. Ni havas novan rondon. La nombro de ĉi tiu rondo estas n. Ni komencos voĉdoni nun." Ĝis nun ĝi nur raportas la komencon de nova ciklo, sed ne raportas la novan valoron. La tasko de ĉi tiu etapo estas komenci novan rondon kaj informi ĉiun pri ĝia unika nombro. La ronda nombro estas grava, ĝi devas esti pli granda ol ĉiuj antaŭaj balotaj nombroj de ĉiuj antaŭaj gvidantoj. Ĉar danke al la ronda nombro, aliaj nodoj en la sistemo komprenos kiom freŝaj estas la datumoj de la gvidanto. Verŝajne aliaj nodoj jam havas balotrezultojn de multe pli postaj ĉirkaŭvojoj kaj simple diros al la gvidanto, ke li estas malantaŭ la tempoj.
- Fazo 1b: Promeso. Kiam la akceptantaj nodoj ricevis la nombron de la nova voĉdonadstadio, du rezultoj estas eblaj:
- La nombro n de la nova voĉdono estas pli granda ol la nombro de iu ajn el la antaŭaj voĉoj, en kiuj la akceptanto partoprenis. Tiam la akceptanto sendas promeson al la gvidanto, ke ĝi ne plu partoprenos en ajnaj voĉoj kun nombro malpli ol n. Se la akceptanto jam voĉdonis por io (tio estas, ĝi jam akceptis ian valoron en la dua fazo), tiam ĝi aldonas al sia promeso la akceptitan valoron kaj la nombron de la voĉdono, en kiu ĝi partoprenis.
- Alie, se la akceptanto jam scias pri la alt-nombra voĉdono, ĝi povas simple ignori la preparpaŝon kaj ne respondi al la gvidanto.
- Fazo 2a: Akceptu. La gvidanto devas atendi respondon de la kvorumo (la plej multaj el la nodoj en la sistemo) kaj, se la bezonata nombro da respondoj estas ricevita, tiam li havas du eblojn por la disvolviĝo de eventoj:
- Iuj el la akceptantoj sendis valorojn, por kiuj ili jam voĉdonis. En ĉi tiu kazo, la gvidanto elektas la valoron el la voĉdono kun la plej alta nombro. Ni nomu ĉi tiun valoron x, kaj sendu mesaĝon kiel ĉi tion al ĉiuj nodoj: "Akceptu (n, x)", kie la unua valoro estas la voĉdona nombro de sia propra Proponi paŝo, kaj la dua valoro estas tio, por kio ĉiuj kolektis, t.e. valoro por kiu, fakte, ni voĉdonas.
- Se neniu el la akceptantoj sendis iujn ajn valorojn, sed ili simple promesis voĉdoni en ĉi tiu rondo, la gvidanto povas inviti ilin voĉdoni por ilia valoro, la valoro por kiu li entute fariĝis gvidanto. Ni nomu ĝin y. Ĝi sendas al ĉiuj nodoj mesaĝon kiel: "Akceptu (n, y)", analoge kun la antaŭa rezulto.
- Fazo 2b: Akceptita. Plue, la akceptantaj nodoj, ricevinte la mesaĝon "Akceptu (...)", de la gvidanto konsentas kun ĝi (sendu konfirmon al ĉiuj nodoj, ke ili konsentas kun la nova valoro) nur se ili ne promesis al iu (alia ) la gvidanto por partopreni en voĉdonado kun la nombro de la rondo n' > nalie ili ignoras la konfirmon.
Se la plimulto de nodoj respondis al la gvidanto, kaj ili ĉiuj konfirmis la novan valoron, tiam la nova valoro estas konsiderata akceptita. Hura! Se la plimulto ne estas tajpita aŭ estas nodoj, kiuj rifuzis akcepti la novan valoron, tiam ĉio rekomencas.
Tiel funkcias la algoritmo de Paxos. Ĉiu el ĉi tiuj etapoj havas multajn subtilecojn, ni praktike ne konsideris diversajn specojn de fiaskoj, problemojn de multoblaj gvidantoj kaj multe pli, sed la celo de ĉi tiu artikolo estas nur prezenti la leganton al la mondo de distribuita komputado ĉe la plej alta nivelo.
Estas ankaŭ notinde, ke Paxos ne estas la sola tia, ekzistas aliaj algoritmoj, ekzemple, , sed ĉi tio estas temo por alia artikolo.
Ligiloj al materialoj por plua studo
Novnivelo:
- , Preethi Kasireddy, blogartikolo pri Medium
- , Adi Kancherla, blogartikolo pri Medium
- Ittai Abraham blogo
- , Ittai Abraham, blogartikolo
Leslie Lampport Nivelo:
- Fischer, Lynch kaj Paterson, esplorartikolo, 1985
- Leslie Lampport, esplorartikolo, 1998
- Leslie Lampport, esplorartikolo, 2001
fonto: www.habr.com