Svo, við skulum ímynda okkur. Það eru 5 kettir læstir inni í herberginu og til þess að geta farið að vekja eigandann þurfa þeir allir að vera sammála um þetta sín á milli, því þeir mega bara opna hurðina með fimm þeirra sem halla sér að henni. Ef einn af köttunum er köttur Schrödinger og hinir kettirnir vita ekki um ákvörðun hans, vaknar spurningin: „Hvernig geta þeir gert það?
Í þessari grein mun ég segja þér á einfaldan hátt um fræðilegan þátt í heimi dreifðra kerfa og meginreglur um starfsemi þeirra. Ég mun einnig skoða yfirborðslega meginhugmyndina sem liggur að baki Paxos.
Þegar forritarar nota skýjainnviði, ýmsa gagnagrunna og vinna í þyrpingum af miklum fjölda hnúta eru þeir fullvissir um að gögnin verði fullbúin, örugg og alltaf tiltæk. En hvar eru ábyrgðirnar?
Í meginatriðum eru ábyrgðirnar sem við höfum birgjaábyrgðir. Þeim er lýst í skjölunum sem hér segir: „Þessi þjónusta er nokkuð áreiðanleg, hún hefur ákveðið SLA, ekki hafa áhyggjur, allt mun virka dreift eins og þú býst við.
Okkur hættir til að trúa á það besta, því klárir krakkar frá stórfyrirtækjum fullvissuðu okkur um að allt yrði í lagi. Við spyrjum ekki spurningarinnar: hvers vegna, í raun, getur þetta virkað yfirleitt? Er einhver formleg réttlæting fyrir réttri starfsemi slíkra kerfa?
Ég fór nýlega til og var mjög innblásin af þessu efni. Fyrirlestrar í skólanum voru meira eins og reikningstímar en eitthvað sem tengist tölvukerfum. En þetta er nákvæmlega hvernig mikilvægustu reikniritin sem við notum á hverjum degi, án þess þó að vita af því, reyndust í einu.
Flest nútíma dreifð kerfi nota Paxos samstöðu reiknirit og ýmsar breytingar á því. Það flottasta er að hægt er að sanna réttmæti og í grundvallaratriðum sjálfan möguleikann á tilvist þessa reiknirits einfaldlega með penna og pappír. Í reynd er reikniritið notað í stórum kerfum sem keyra á miklum fjölda hnúta í skýjunum.
Létt lýsing á því sem verður rætt næst: verkefni tveggja hershöfðingjaVið skulum kíkja á upphitun .
Við höfum tvo her - rauðan og hvítan. Hvítir hermenn hafa aðsetur í umsátri borginni. Rauðir hermenn undir forystu hershöfðingjanna A1 og A2 eru staðsettir beggja vegna borgarinnar. Verkefni rauðhærða er að ráðast á hvítu borgina og vinna. Hins vegar er her hvers rauðs hershöfðingja fyrir sig minni en hvíta hersins.
Sigurskilyrði fyrir þá rauðu: báðir hershöfðingjar verða að sækja á sama tíma til að hafa tölulegt forskot á hvíta. Til þess þurfa hershöfðingjar A1 og A2 að komast að samkomulagi sín á milli. Ef allir ráðast sérstaklega á þá tapa rauðhærðir.
Til að ná samkomulagi geta hershöfðingjar A1 og A2 sent sendiboða sín á milli um yfirráðasvæði hvítu borgarinnar. Sendiboðinn getur náð til bandamanns hershöfðingja eða verið stöðvaður af óvininum. Spurning: Er slík samskiptaröð milli rauðhærðu hershöfðingjanna (röðin að senda boðbera frá A1 til A2 og öfugt frá A2 til A1), þar sem tryggt er að þeir komist að samkomulagi um árás á klukkustund X. Hér, tryggingar þýða að báðir hershöfðingjar fá ótvíræða staðfestingu á því að bandamaður (annar hershöfðingi) muni örugglega gera árás á tilsettum tíma X.
Segjum sem svo að A1 sendi boðbera til A2 með skilaboðunum: „Við skulum ráðast á miðnætti í dag!“ Hershöfðingi A1 getur ekki gert árás án staðfestingar frá A2 hershöfðingja. Ef boðberinn frá A1 er kominn sendir A2 hershöfðingi staðfestingu með skilaboðunum: „Já, við skulum drepa hvíta í dag. En nú veit A2 hershöfðingi ekki hvort sendiboði hans er kominn eða ekki, hann hefur enga tryggingu fyrir því hvort árásin verði samtímis. Nú þarf A2 hershöfðingi aftur að fá staðfestingu.
Ef við lýsum frekar samskiptum þeirra verður ljóst að sama hversu margar skilaboðaskipti eru, þá er engin leið til að tryggja að báðir hershöfðingjarnir hafi fengið skilaboðin sín (að því gefnu að hægt sé að hlera annan hvorn boðberann).
The Two Generals Vandamálið er frábær lýsing á mjög einföldu dreifðu kerfi þar sem það eru tveir hnútar með óáreiðanleg samskipti. Þetta þýðir að við höfum ekki 100% tryggingu fyrir því að þær séu samstilltar. Svipuð vandamál eru aðeins rædd í stærri skala síðar í greininni.
Við kynnum hugtakið dreifð kerfi
Dreift kerfi er hópur tölva (hér eftir köllum við þær hnúta) sem geta skipt á skilaboðum. Hver einstakur hnútur er einhvers konar sjálfstæð eining. Hnútur getur unnið verkefni á eigin spýtur, en til þess að eiga samskipti við aðra hnúta þarf hann að senda og taka á móti skilaboðum.
Hvernig nákvæmlega skilaboð eru útfærð, hvaða samskiptareglur eru notaðar - þetta vekur ekki áhuga fyrir okkur í þessu samhengi. Mikilvægt er að hnútar dreifðs kerfis geti skipt gögnum sín á milli með því að senda skilaboð.
Skilgreiningin sjálf lítur ekki mjög flókin út, en við verðum að taka með í reikninginn að dreifð kerfi hefur fjölda eiginleika sem munu skipta okkur máli.
Eiginleikar dreifðra kerfa
- Concurrency - möguleiki á að atburðir eigi sér stað samtímis eða samtímis í kerfinu. Þar að auki munum við líta á atburði sem eiga sér stað á tveimur mismunandi hnútum sem hugsanlega samhliða svo framarlega sem við höfum ekki skýra röð þessara atburða. En að jafnaði höfum við það ekki.
- Engin heimsklukka. Við höfum ekki skýra röð atburða vegna skorts á heimsklukku. Í venjulegum heimi fólks erum við vön því að við höfum klukkur og tíma algjörlega. Allt breytist þegar kemur að dreifðum kerfum. Jafnvel ofurnákvæmar atómklukkur hafa rekið og það geta verið aðstæður þar sem við getum ekki sagt til um hvor af tveimur atburðum gerðist fyrst. Þess vegna getum við heldur ekki treyst á tíma.
- Óháð bilun í kerfishnútum. Það er annað vandamál: eitthvað getur farið úrskeiðis einfaldlega vegna þess að hnútar okkar endast ekki að eilífu. Harði diskurinn gæti bilað, sýndarvélin í skýinu gæti endurræst sig, netið gæti blikka og skilaboð glatast. Þar að auki geta komið upp aðstæður þar sem hnútar vinna, en vinna á sama tíma gegn kerfinu. Síðasti flokkur vandamála fékk meira að segja sérstakt nafn: vandamál . Vinsælasta dæmið um dreifð kerfi með þetta vandamál er Blockchain. En í dag munum við ekki íhuga þennan sérstaka flokk vandamála. Við munum hafa áhuga á aðstæðum þar sem einfaldlega einn eða fleiri hnútar geta bilað.
- Samskiptalíkön (skilaboðalíkön) milli hnúta. Við höfum þegar staðfest að hnútar eiga samskipti með því að skiptast á skilaboðum. Það eru tvær vel þekktar skilaboðagerðir: samstilltur og ósamstilltur.
Líkön af samskiptum milli hnúta í dreifðum kerfum
Samstillt líkan – við vitum með vissu að það er endanlegt þekkt þátttaka tíma þar sem boð er tryggt að ná frá einum hnút til annars. Ef þessi tími er liðinn og skilaboðin hafa ekki borist, getum við örugglega sagt að hnúturinn hafi bilað. Í þessu líkani höfum við fyrirsjáanlegan biðtíma.
Ósamstilltur líkan – í ósamstilltum líkönum teljum við að biðtíminn sé endanlegur, en það er ekkert slíkt tímadelta sem við getum ábyrgst að hnúturinn hafi bilað. Þeir. Biðtími eftir skilaboðum frá hnút getur verið geðþótta langur. Þetta er mikilvæg skilgreining og við munum tala um hana frekar.
Hugmyndin um samstöðu í dreifðum kerfum
Áður en við skilgreinum hugtakið samstaða formlega skulum við íhuga dæmi um aðstæður þar sem við þurfum á því að halda, þ.e. Afritun ríkisvéla.
Við erum með dreifðan dagbók. Við viljum að það sé samkvæmt og innihaldi eins gögn um alla hnúta dreifða kerfisins. Þegar einn af hnútunum lærir nýtt gildi sem hann ætlar að skrifa í reikninginn, þá verður verkefni hans að bjóða öllum öðrum hnútum þetta gildi þannig að annálinn er uppfærður á öllum hnútum og kerfið færist í nýtt stöðugt ástand. Í þessu tilviki er mikilvægt að hnútarnir séu sammála innbyrðis: allir hnútar eru sammála um að fyrirhugað nýja gildi sé rétt, allir hnútar samþykkja þetta gildi og aðeins í þessu tilfelli geta allir skrifað nýja gildið í loginn.
Með öðrum orðum: enginn af hnútunum mótmælti því að hann hefði meira viðeigandi upplýsingar og fyrirhugað gildi var rangt. Samkomulag milli hnúta og samkomulag um eitt rétt samþykkt gildi er samstaða í dreifðu kerfi. Næst munum við tala um reiknirit sem gera kleift að tryggja að dreift kerfi nái samstöðu.
Með formlegri hætti getum við skilgreint samhljóða reiknirit (eða einfaldlega samhljóða reiknirit) sem ákveðið fall sem flytur dreifð kerfi frá ástandi A til ástands B. Þar að auki er þetta ástand samþykkt af öllum hnútum og allir hnútar geta staðfest það. Eins og það kemur í ljós er þetta verkefni alls ekki eins léttvægt og það virðist við fyrstu sýn.
Eiginleikar Consensus Reikniritsins
Samkomulagsreikniritið verður að hafa þrjá eiginleika til þess að kerfið haldi áfram að vera til og nái einhverjum framförum í flutningi frá ríki til ríkis:
- Samningur - allir rétt starfandi hnútar verða að hafa sama gildi (í greinum er þessi eiginleiki einnig nefndur öryggiseign). Allir hnútar sem eru að virka núna (hafa ekki brugðist eða misst samband við hina) verða að komast að samkomulagi og samþykkja eitthvert endanlegt sameiginlegt gildi.
Það er mikilvægt að skilja hér að hnútarnir í dreifða kerfinu sem við erum að íhuga vilja vera sammála. Það er að segja, við erum núna að tala um kerfi þar sem eitthvað getur einfaldlega bilað (til dæmis einhver hnútur bilar), en í þessu kerfi eru örugglega engir hnútar sem vinna viljandi gegn öðrum (verkefni býsanska hershöfðingja). Vegna þessa eiginleika er kerfið stöðugt.
- heiðarleiki — ef allir rétt virka hnútar bjóða upp á sama gildi v, sem þýðir að sérhver rétt starfandi hnút verður að samþykkja þetta gildi v.
- Uppsögn – allir rétt starfandi hnútar munu á endanum taka á sig ákveðið gildi (lífeiginleika), sem gerir reikniritinu kleift að taka framförum í kerfinu. Hver einstakur rétt starfandi hnút verður fyrr eða síðar að samþykkja lokagildið og staðfesta það: "Fyrir mér er þetta gildi satt, ég er sammála öllu kerfinu."
Dæmi um hvernig samstöðu reikniritið virkar
Þó að eiginleikar reikniritsins séu kannski ekki alveg skýrir. Þess vegna munum við útskýra með dæmi hvaða stig einfaldasta samstöðualgrímið fer í gegnum í kerfi með samstilltu skilaboðalíkani, þar sem allir hnútar virka eins og búist er við, skilaboð glatast ekki og ekkert bilar (gerist þetta í alvöru?).
- Þetta byrjar allt með hjónabandstillögu (Propose). Gerum ráð fyrir að viðskiptavinur hafi tengt við hnút sem heitir "Node 1" og hafið færslu og sendi nýtt gildi til hnútinn - O. Héðan í frá munum við kalla "Node 1" Tilboðið. Sem tillögumaður verður „Node 1“ nú að tilkynna öllu kerfinu að það hafi ný gögn og það sendir skilaboð til allra annarra hnúta: „Sjáðu! Merkingin „O“ kom til mín og ég vil skrifa hana niður! Vinsamlega staðfestu að þú skráir einnig „O“ í skránni þinni.
- Næsti áfangi er atkvæðagreiðsla um fyrirhugað gildi (atkvæðagreiðsla). Til hvers er það? Það getur gerst að aðrir hnútar hafi fengið nýlegri upplýsingar og þeir hafa gögn um sömu viðskipti.
Þegar hnútur „Node 1“ sendir tillögu sína, athuga hinir hnútarnir í annálum sínum fyrir gögn um þennan atburð. Ef það eru engar mótsagnir tilkynna hnútarnir: „Já, ég hef engin önnur gögn um þennan atburð. „O“ gildið er nýjustu upplýsingarnar sem við eigum skilið.Í öllum öðrum tilvikum geta hnútar svarað „Node 1“: „Hlustaðu! Ég hef nýlegri gögn um þessi viðskipti. Ekki „O“ heldur eitthvað betra.“
Á atkvæðagreiðslustigi komast hnútarnir að ákvörðun: annað hvort samþykkja þeir allir sama gildi, eða einn þeirra greiðir atkvæði á móti, sem gefur til kynna að hann hafi nýlegri gögn.
- Ef atkvæðagreiðslan heppnaðist vel og allir voru hlynntir, þá færist kerfið á nýtt stig - Samþykkja gildið. „Hnútur 1“ safnar öllum svörum frá öðrum hnútum og segir: „Allir voru sammála um gildið „O“! Nú lýsi ég því formlega yfir að „O“ er nýja merkingin okkar, sú sama fyrir alla! Skrifaðu það niður í litlu bókina þína, ekki gleyma. Skrifaðu það niður í dagbókina þína!"
- Hinir hnútarnir sem eftir eru senda staðfestingu (Samþykkt) um að þeir hafi skrifað niður gildið „O“; ekkert nýtt hefur borist á þessum tíma (eins konar tveggja fasa commit). Eftir þennan mikilvæga atburð teljum við að dreifðu viðskiptunum sé lokið.
Þannig samanstendur samþykkisalgrímið í einföldu tilfelli af fjórum skrefum: leggja til, kjósa (atkvæða), samþykkja (samþykkja), staðfesta samþykki (samþykkt).
Ef á einhverju skrefi tókst okkur ekki að ná samkomulagi, þá byrjar reikniritið aftur, að teknu tilliti til upplýsinganna frá hnútunum sem neituðu að staðfesta fyrirhugað gildi.
Consensus algrím í ósamstilltu kerfi
Fyrir þetta var allt slétt, því við vorum að tala um samstillt skilaboðalíkan. En við vitum að í nútíma heimi erum við vön að gera allt ósamstillt. Hvernig virkar svipað reiknirit í kerfi með ósamstilltu skilaboðalíkani, þar sem við teljum að biðtími eftir svari frá hnút geti verið geðþótta langur (við the vegur, bilun í hnút má líka líta á sem dæmi þegar hnútur getur svarað í geðþótta langan tíma).
Nú þegar við vitum hvernig samstöðu reikniritið virkar í grundvallaratriðum, spurning fyrir þá fróðleiksfúsa lesendur sem hafa komist svona langt: hversu margir hnútar í kerfi N hnúta með ósamstilltu skilaboðalíkani geta bilað þannig að kerfið geti samt náð samstöðu?
Rétt svar og rökstuðningur eru á bak við spoilerinn.Rétt svarið er: 0. Ef jafnvel einn hnútur í ósamstilltu kerfi bilar mun kerfið ekki geta náð samstöðu. Þessi fullyrðing er sönnuð í FLP setningunni, sem er vel þekkt í ákveðnum hópum (1985, Fischer, Lynch, Paterson, hlekkur á frumritið í lok greinarinnar): „Það er ómögulegt að ná dreifðri samstöðu ef að minnsta kosti einn hnút bregst. .”
Krakkar, þá erum við með vandamál, við erum vön því að allt sé ósamstillt. Og hér er það. Hvernig á að halda áfram að lifa?
Við vorum bara að tala um fræði, um stærðfræði. Hvað þýðir „samstaða er ekki hægt að ná“, að þýða úr stærðfræðimáli yfir á okkar - verkfræði? Þetta þýðir að „ekki alltaf hægt að ná“, þ.e. Það er tilfelli þar sem samstaða er ekki hægt að ná. Hvers konar mál er þetta?
Þetta er einmitt brotið á lífeyriseigninni sem lýst er hér að ofan. Við höfum ekki sameiginlegt samkomulag og kerfið getur ekki náð framvindu (getur ekki lokið á endanlegum tíma) í því tilviki sem við höfum ekki svar frá öllum hnútum. Vegna þess að í ósamstilltu kerfi höfum við engan fyrirsjáanlegan viðbragðstíma og við getum ekki vitað hvort hnútur hafi hrunið eða tekur bara langan tíma að svara.
En í reynd getum við fundið lausn. Láttu reikniritið okkar geta virkað í langan tíma ef bilanir verða (hugsanlega getur það virkað endalaust). En í flestum tilfellum, þegar flestir hnútar virka rétt, munum við hafa framfarir í kerfinu.
Í reynd erum við að fást við samstillt samskiptalíkön að hluta. Hlutasamstilling er skilin sem hér segir: í almennu tilvikinu höfum við ósamstillt líkan, en ákveðið hugtak um „alheimsstöðugleikatíma“ á ákveðnum tímapunkti er formlega kynnt.
Þetta augnablik kemur kannski ekki í langan tíma, en það verður að koma einn daginn. Sýndarvekjaraklukkan mun hringja og frá því augnabliki getum við spáð fyrir um tímadeltuna sem skilaboðin munu berast. Frá þessari stundu breytist kerfið úr ósamstilltu í samstillt. Í reynd erum við einmitt að fást við slík kerfi.
Paxos reikniritið leysir samstöðuvandamál
er fjölskylda reiknirita sem leysa samstöðuvandamálið fyrir samstillt kerfi að hluta, með fyrirvara um að sumir hnútar geti bilað. Höfundur Paxos er . Hann lagði til formlega sönnun fyrir tilvist og réttmæti reikniritsins árið 1989.
En sönnunin reyndist langt frá því að vera léttvæg. Fyrsta ritið kom fyrst út árið 1998 (33 síður) þar sem reikniritið var lýst. Það kom í ljós að hún var afar erfitt að skilja og árið 2001 birtist skýring á greininni sem tók 14 blaðsíður. Ritamagnið er gefið upp til að sýna fram á að í raun er samstöðuvandinn alls ekki einfaldur og á bak við slík reiknirit liggur gríðarleg vinna af snjöllustu fólki.
Það er athyglisvert að Leslie Lamport tók sjálfur fram í fyrirlestri sínum að í annarri skýringargreininni er ein fullyrðing, ein lína (hann tilgreindi ekki hverja), sem má túlka á mismunandi vegu. Og vegna þessa virkar mikill fjöldi nútíma Paxos útfærslur ekki alveg rétt.
Ítarleg greining á verkum Paxos myndi taka fleiri en eina grein, svo ég mun reyna að koma mjög stuttlega á framfæri meginhugmynd reikniritsins. Í krækjunum í lok greinar minnar finnurðu efni til að kafa frekar inn í þetta efni.
Hlutverk hjá Paxos
Paxos reikniritið hefur hugmynd um hlutverk. Við skulum íhuga þrjár helstu (það eru breytingar með viðbótarhlutverkum):
- Tillögur (einnig má nota hugtökin: leiðtogar eða samræmingarstjórar). Þetta eru strákarnir sem læra um eitthvað nýtt gildi frá notandanum og taka að sér leiðtogahlutverkið. Verkefni þeirra er að hefja lotu af tillögum um nýtt gildi og samræma frekari aðgerðir hnútanna. Þar að auki gerir Paxos ráð fyrir viðveru nokkurra leiðtoga í ákveðnum aðstæðum.
- Samþykktir (kjósendur). Þetta eru hnútar sem greiða atkvæði um að samþykkja eða hafna tilteknu gildi. Hlutverk þeirra er mjög mikilvægt, vegna þess að ákvörðunin veltur á þeim: í hvaða ástandi kerfið mun (eða mun ekki) fara í eftir næsta stig samstöðu reikniritsins.
- Nemendur. Hnútar sem einfaldlega samþykkja og skrifa nýja samþykkta gildið þegar ástand kerfisins hefur breyst. Þeir taka ekki ákvarðanir, þeir taka bara við gögnunum og geta gefið þau til endanotandans.
Einn hnút getur sameinað mörg hlutverk við mismunandi aðstæður.
Hugtakið sveitarfélag
Við gerum ráð fyrir að við höfum kerfi af N hnúta Og af þeim hámarkið F hnútar gætu mistekist. Ef F hnútar mistakast, þá verðum við að hafa amk 2F+1 samþykkishnútar.
Þetta er nauðsynlegt svo að við höfum alltaf meirihluta, jafnvel í verstu aðstæðum, af „góðum“ hnútum sem virka rétt. Það er F+1 „góðir“ hnútar sem samþykktu og lokagildið verður samþykkt. Annars getur komið upp sú staða að ólíkir staðbundnir hópar okkar fá mismunandi merkingu og geta ekki komið sér saman um. Þess vegna þurfum við hreinan meirihluta til að ná atkvæðagreiðslunni.
Almenn hugmynd um hvernig Paxos samstöðu reiknirit virkar
Paxos reikniritið felur í sér tvo stóra fasa, sem aftur er skipt í tvö skref hvert:
- Áfangi 1a: Undirbúningur. Á undirbúningsstigi upplýsir leiðtogi (tillögugjafi) öllum hnútum: „Við erum að hefja nýjan atkvæðagreiðslufasa. Við erum með nýja umferð. Fjöldi þessarar umferðar er n. Nú byrjum við að kjósa." Í bili tilkynnir það einfaldlega upphaf nýrrar lotu, en tilkynnir ekki um nýtt gildi. Verkefni þessa áfanga er að hefja nýja umferð og upplýsa alla um sitt einstaka númer. Hringtalan er mikilvæg, hún verður að vera hærra gildi en allar fyrri kosningatölur allra fyrri leiðtoga. Vegna þess að það er hringlaga tölunni að þakka að aðrir hnútar í kerfinu munu skilja hversu nýleg gögn leiðtogans eru. Líklegt er að aðrir hnútar séu nú þegar með niðurstöður atkvæðagreiðslu úr miklu síðari umferðum og muni einfaldlega segja leiðtoganum að hann sé á eftir tímanum.
- Áfangi 1b: Loforð. Þegar viðtökuhnútar fengu númer nýja atkvæðagreiðslustigsins eru tvær niðurstöður mögulegar:
- Talan n nýja atkvæðisins er meiri en fjöldi fyrri atkvæða sem viðtakandinn tók þátt í. Þá sendir viðtakandi loforð til oddvita um að hann muni ekki taka þátt í fleiri atkvæðum með lægri tölu en n. Ef viðtakandinn hefur þegar greitt atkvæði með einhverju (þ.e. hann hefur þegar samþykkt eitthvað gildi í öðrum áfanga), þá bindur hann samþykkt gildi og númer atkvæða sem hann tók þátt í við loforð sitt.
- Annars, ef viðtakandi veit nú þegar um hærra atkvæði, getur hann einfaldlega hunsað undirbúningsskrefið og ekki svarað leiðtoganum.
- Áfangi 2a: Samþykkja. Leiðtoginn þarf að bíða eftir svari frá sveitinni (meirihluti hnúta í kerfinu) og ef tilskilinn fjöldi svara berst, þá hefur hann tvo möguleika til að þróa atburði:
- Sumir viðtakenda sendu gildi sem þeir höfðu þegar kosið um. Í þessu tilviki velur leiðtoginn gildið úr atkvæðagreiðslunni með hámarksfjölda. Við skulum kalla þetta gildi x, og það sendir út skilaboð til allra hnúta eins og: "Samþykkja (n, x)", þar sem fyrsta gildið er atkvæðatalan úr eigin tillöguþrepinu og annað gildið er það sem allir söfnuðust saman fyrir, þ.e. gildið sem við kjósum í raun um.
- Ef enginn viðtakenda sendi nein gildi, en þeir lofuðu einfaldlega að kjósa í þessari umferð, getur leiðtoginn boðið þeim að kjósa um gildi þeirra, gildið sem hann varð leiðtogi fyrir í fyrsta lagi. Við skulum kalla það y. Það sendir skilaboð til allra hnúta eins og: "Samþykkja (n, y)", svipað og fyrri útkoma.
- Áfangi 2b: Samþykkt. Ennfremur samþykkja hnútarnir, þegar þeir fá „Samþykkja(...)“ skilaboðin frá leiðtoganum, samþykkja það (senda staðfestingu til allra hnúta um að þeir séu sammála nýja gildinu) aðeins ef þeir hafa ekki lofað einhverju (annað) ) leiðtogi til að taka þátt í atkvæðagreiðslu með umferðarnúmeri n' > n, annars hunsa þeir staðfestingarbeiðnina.
Ef meirihluti hnúta svaraði leiðtoganum og allir staðfestu nýja gildið, þá er nýja gildið talið samþykkt. Húrra! Ef meirihlutinn næst ekki eða það eru hnútar sem neituðu að samþykkja nýja gildið, þá byrjar allt aftur.
Svona virkar Paxos reikniritið. Hvert þessara stiga hefur marga fínleika, við tókum nánast ekki tillit til ýmiss konar bilana, vandamála margra leiðtoga og margt fleira, en tilgangur þessarar greinar er aðeins að kynna lesandanum heim dreifðrar tölvunar á háu stigi.
Það er líka athyglisvert að Paxos er ekki sá eini sinnar tegundar, það eru önnur reiknirit, td. , en þetta er efni í aðra grein.
Tenglar á efni til frekara náms
Byrjendastig:
- , Preethi Kasireddy, blogggrein um Medium
- , Adi Kancherla, blogggrein um Medium
- , Ittai Abraham, blogg
- , Ittai Abraham, blogggrein
Leslie Lamport stig:
- , Fischer, Lynch og Paterson, rannsóknarritgerð, 1985
- , Leslie Lamport, rannsóknarritgerð, 1998
- , Leslie Lamport, rannsóknarritgerð, 2001
Heimild: www.habr.com