Ngakho, ake sicabange. Kunamakati awu 5 akhiyelwe ekamelweni, ukuze ayovusa umnikazi wawo, kumele avumelane ngawodwana ngalokhu, ngoba angavula umnyango kuphela amahlanu ancike kuwo. Uma elinye lamakati liyikati likaSchrödinger, kanti amanye amakati awazi ngesinqumo sakhe, kuphakama umbuzo: "Bangakwenza kanjani?"
Kulesi sihloko, ngizokutshela ngamagama alula mayelana nengxenye yethiyori yomhlaba wezinhlelo ezisabalalisiwe kanye nezimiso zokusebenza kwazo. Ngizophinde ngihlole ngokukha phezulu umqondo oyinhloko ongaphansi kwe-Paxos.
Uma abathuthukisi besebenzisa izingqalasizinda zamafu, isizindalwazi esihlukahlukene, futhi besebenza ngamaqoqo enani elikhulu lamanodi, bayaqiniseka ukuthi idatha izobe iphelele, ivikelekile, futhi itholakala njalo. Kodwa ziphi iziqinisekiso?
Empeleni, iziqinisekiso esinazo ziyiziqinisekiso zabahlinzeki. Bachazwe emibhalweni ngale ndlela: "Le nsizakalo ithembekile impela, ine-SLA enikeziwe, ungakhathazeki, konke kuzosebenza ngokusatshalaliswa njengoba ulindele."
Sivame ukukholelwa kokungcono kakhulu, ngoba abafana abahlakaniphile abavela ezinkampanini ezinkulu basiqinisekisa ukuthi konke kuzolunga. Asibuzi umbuzo: kungani, empeleni, lokhu kungasebenza nhlobo? Ingabe kukhona ukuthethelelwa okusemthethweni kokusebenza kahle kwalezo zinhlelo?
Ngisanda kuya futhi wagqugquzelwa kakhulu ngalesi sihloko. Izifundo esikoleni zazifana namakilasi okubala kunokuthile okuhlobene nezinhlelo zamakhompiyutha. Kodwa yiyo kanye indlela ama-algorithms abaluleke kakhulu esiwasebenzisa nsuku zonke, ngaphandle kokwazi, afakazelwa ngayo ngesikhathi esisodwa.
Amasistimu amaningi esimanje asabalalisiwe asebenzisa i-algorithm yokuvumelana ye-Paxos kanye nokuguqulwa kwayo okuhlukahlukene. Into ebanda kunazo zonke ukuthi ubuqiniso futhi, ngokomthetho, ukuthi kungenzeka khona le algorithm kungafakazelwa kalula ngepeni nephepha. Empeleni, i-algorithm isetshenziswa ezinhlelweni ezinkulu ezisebenza ngenani elikhulu lama-node emafini.
Umfanekiso olula walokho okuzoxoxwa ngakho ngokulandelayo: umsebenzi wojenene ababiliAke sibheke ukuzifudumeza .
Sinamabutho amabili - obomvu nokumhlophe. Amasosha amhlophe azinze edolobheni elivinjezelwe. Amasosha abomvu aholwa ojenene u-A1 no-A2 atholakala ezinhlangothini ezimbili zedolobha. Umsebenzi we-redheads ukuhlasela idolobha elimhlophe futhi linqobe. Nokho, ibutho likajenene ngamunye obomvu lincane kunebutho elimhlophe.
Izimo zokunqoba ezibomvu: bobabili ojenene kufanele bahlasele ngesikhathi esifanayo ukuze babe nenani elizuzisayo ngaphezu kwabamhlophe. Ukwenza lokhu, ojenene u-A1 no-A2 badinga ukuvumelana omunye nomunye. Uma wonke umuntu ehlasela ngokwehlukana, ama-redheads azolahlekelwa.
Ukuze kufinyelelwe esivumelwaneni, ojenene u-A1 no-A2 bangathumela izithunywa komunye nomunye endaweni yedolobha elimhlophe. Isithunywa singase sifinyelele ujenene ongumlingani ngempumelelo noma sibanjwe yisitha. Umbuzo: ingabe kukhona ukulandelana okunjalo kokuxhumana phakathi kojenene abanezinwele ezibomvu (ukulandelana kokuthumela izithunywa zisuka ku-A1 ziye ku-A2 futhi ngokuphambene nalokho zisuka ku-A2 ziye ku-A1), lapho ziqinisekiswa khona ukuthi zizovumelana ngokuhlaselwa ngehora X. Lapha, iziqinisekiso zisho ukuthi bobabili ojenene bazoba nesiqiniseko esicacile sokuthi umlingani (omunye ujenene) uzohlasela nakanjani ngesikhathi esimisiwe X.
Ake sithi i-A1 ithumela isithunywa ku-A2 nomlayezo othi: “Asihlasele namuhla phakathi kwamabili!” I-General A1 ayikwazi ukuhlasela ngaphandle kwesiqinisekiso esivela ku-General A2. Uma isithunywa esivela kwa-A1 sesifikile, khona-ke uGeneral A2 uthumela isiqinisekiso ngomlayezo: "Yebo, asibulale abamhlophe namuhla." Kodwa manje uGeneral A2 akazi ukuthi isithunywa sakhe sesifikile noma cha, akanaso isiqiniseko sokuthi ukuhlasela kuzokwenziwa kanyekanye. Manje i-General A2 iphinde idinga ukuqinisekiswa.
Uma siqhubeka sichaza ukuxhumana kwabo, kuyacaca ukuthi kungakhathaliseki ukuthi mingaki imijikelezo yokushintshisana ngemiyalezo, ayikho indlela yokuqinisekisa ukuthi ojenene bobabili bayitholile imilayezo yabo (kucatshangwa ukuthi noma yisiphi isithunywa singabanjwa).
Inkinga YamaGeneral Amabili ingumfanekiso omuhle kakhulu wesistimu esabalalisiwe elula lapho kunamanodi amabili anokuxhumana okungathembekile. Lokhu kusho ukuthi asinaso isiqinisekiso esingu-100% sokuthi avumelanisiwe. Izinkinga ezifanayo kuxoxwa ngazo kuphela ngezinga elikhulu kamuva esihlokweni.
Sethula umqondo wamasistimu asabalalisiwe
Uhlelo olusabalalisiwe yiqembu lamakhompyutha (ngemuva kwalokhu sizowabiza ngokuthi ama-node) angashintshana ngemiyalezo. Inodi ngayinye iwuhlobo oluthile lwebhizinisi elizimele. I-node ingakwazi ukucubungula imisebenzi ngokwayo, kodwa ukuze uxhumane namanye ama-node, idinga ukuthumela nokwamukela imilayezo.
Ukuthi imilayezo isetshenziswa kanjani ngempela, yiziphi izivumelwano ezisetshenziswayo - lokhu akusithakazelisi kulo mongo. Kubalulekile ukuthi ama-node wesistimu esabalalisiwe akwazi ukushintshanisa idatha nomunye nomunye ngokuthumela imilayezo.
Incazelo ngokwayo ayibukeki iyinkimbinkimbi kakhulu, kodwa kufanele sicabangele ukuthi uhlelo olusabalalisiwe lunenombolo yezimfanelo ezizobaluleka kithi.
Izimfanelo zamasistimu asabalalisiwe
- I-Concurrency - amathuba okuba kwenzeke izigameko ngesikhathi esisodwa noma ngesikhathi esisodwa ohlelweni. Ngaphezu kwalokho, sizocubungula izehlakalo ezenzeka kuma-node amabili ahlukene njengezingahle zifane inqobo nje uma singenalo uhlelo olucacile lokwenzeka kwalezi zenzakalo. Kodwa, njengomthetho, asinakho.
- Alikho iwashi lomhlaba jikelele. Asinakho ukuhleleka okucacile kwezenzakalo ngenxa yokuntuleka kwewashi lomhlaba wonke. Ezweni elivamile labantu, sijwayele iqiniso lokuthi sinamawashi nesikhathi ngokuphelele. Konke kuyashintsha uma kukhulunywa ngezinhlelo ezisabalalisiwe. Ngisho namawashi e-athomu anembe kakhulu ayakwazi ukukhukhuleka, futhi kungase kube nezimo lapho singeke sazi ukuthi yisiphi isenzakalo kwezimbili esenzeka kuqala. Ngakho-ke, nathi ngeke sithembele esikhathini.
- Ukwehluleka okuzimele kwamanodi esistimu. Kukhona enye inkinga: kukhona okungahamba kahle ngenxa yokuthi amanodi ethu awahlali unomphela. I-hard drive ingase yehluleke, umshini we-virtual osefwini ungase uqalise kabusha, inethiwekhi ingase icwayize futhi imilayezo izolahleka. Ngaphezu kwalokho, kungase kube nezimo lapho ama-node asebenza khona, kodwa ngesikhathi esifanayo asebenze ngokumelene nesistimu. Ikilasi lokugcina lezinkinga laze lathola igama elihlukile: inkinga . Isibonelo esidume kakhulu sesistimu esabalalisiwe nale nkinga yiBlockchain. Kodwa namuhla ngeke sicabangele lesi sigaba esikhethekile sezinkinga. Siyoba nesithakazelo ezimweni lapho i-nodi eyodwa noma ngaphezulu ingase yehluleke.
- Amamodeli okuxhumana (amamodeli wokuthumela imiyalezo) phakathi kwamanodi. Sesikutholile kakade ukuthi ama-node ayaxhumana ngokushintshana imiyalezo. Kunamamodeli amabili emiyalezo aziwayo: evumelanayo ne-asynchronous.
Amamodeli okuxhumana phakathi kwama-node kumasistimu asabalalisiwe
Imodeli yokuvumelanisa - siyazi ngokuqinisekile ukuthi kune-delta yesikhathi esinqunyelwe lapho umlayezo uqinisekiswa ukuthi uzofika usuka kwenye indawo uye kwenye. Uma lesi sikhathi sesidlulile futhi umlayezo ungakafiki, singasho ngokuphepha ukuthi i-node ihlulekile. Kulo modeli sinezikhathi zokulinda ezingabikezelwa.
Imodeli ye-Asynchronous - kumamodeli asynchronous sibheka ukuthi isikhathi sokulinda siphelile, kodwa ayikho i-delta enjalo yesikhathi ngemva kwalokho singaqinisekisa ukuthi i-node ihlulekile. Labo. Isikhathi sokulinda somlayezo ovela endaweni singaba yinde ngokunganaki. Lena incazelo ebalulekile, futhi sizokhuluma ngayo ngokuqhubekayo.
Umqondo wokuvumelana ezinhlelweni ezisabalalisiwe
Ngaphambi kokuchaza ngokusemthethweni umqondo wokuvumelana, ake sicabangele isibonelo sesimo lapho sisidinga khona, okungukuthi - I-State Machine Replication.
Sinelogi ethile esabalalisiwe. Singathanda ukuthi ingaguquki futhi iqukathe idatha efanayo kuwo wonke ama-node wesistimu esabalalisiwe. Lapho enye yama-node ifunda inani elisha elizolibhala kulogi, umsebenzi wayo uba ukunikeza leli nani kuwo wonke amanye ama-node ukuze ilogi ibuyekezwe kuwo wonke ama-node futhi uhlelo luqhubekele esimweni esisha esingaguquki. Kulesi simo, kubalulekile ukuthi ama-node avumelane phakathi kwawo: wonke ama-node avuma ukuthi inani elisha elihlongozwayo lilungile, wonke ama-node ayamukela leli nani, futhi kuphela kulokhu wonke umuntu angabhala inani elisha kulogi.
Ngamanye amazwi: awekho amanodi aphikisayo ngokuthi anolwazi olufanele, futhi inani elihlongozwayo lalingalungile. Isivumelwano phakathi kwama-node nesivumelwano senani elilodwa elilungile elamukelekayo siwukuvumelana ohlelweni olusabalalisiwe. Okulandelayo, sizokhuluma ngama-algorithms avumela isistimu esabalalisiwe ukuthi iqinisekiswe ukuze ifinyelele ukuvumelana.
Ngokusemthethweni, singachaza i-algorithm yokuvumelana (noma i-algorithm yokuvumelana) njengomsebenzi othile odlulisa uhlelo olusabalalisiwe ukusuka kusimo A ukuya ku-B. Ngaphezu kwalokho, lesi simo samukelwa yiwo wonke ama-node, futhi wonke ama-node angasiqinisekisa. Njengoba kuvela, lo msebenzi awuwona neze umncane njengoba ubonakala ekuqaleni.
Izakhiwo ze-Consensus Algorithm
I-algorithm yokuvumelana kufanele ibe nezakhiwo ezintathu ukuze isistimu iqhubeke nokuba khona futhi ibe nenqubekelaphambili ethile ekuhambeni ukusuka kwesinye isimo kuye kwesinye:
- Isivumelwano - wonke ama-node asebenzayo kufanele athathe inani elifanayo (ezindabeni le ndawo ibizwa nangokuthi impahla yokuphepha). Wonke ama-node asebenzayo njengamanje (akehlulekanga noma alahlekelwe ukuxhumana nabanye) kufanele afinyelele esivumelwaneni futhi amukele inani lokugcina elivamile.
Kubalulekile ukuqonda lapha ukuthi ama-node ohlelweni olusabalalisiwe esicabanga ukuthi afuna ukuvumelana. Okusho ukuthi, manje sikhuluma ngezinhlelo lapho into ethile ingahluleka khona (isibonelo, enye i-node ihluleka), kodwa kulesi simiso awekho nakanjani ama-node asebenza ngamabomu ngokumelene nabanye (umsebenzi wojenene baseByzantine). Ngenxa yalesi sici, isistimu ihlala ingashintshi.
- Ubuqotho - uma wonke amanodi asebenza kahle enikeza inani elifanayo v, okusho ukuthi yonke indawo esebenza kahle kufanele yamukele leli nani v.
- Ukuqedwa - wonke ama-node okusebenza ngendlela efanele azogcina ethatha inani elithile (impahla ye-liveness), evumela i-algorithm ukuthi iqhubekele phambili ohlelweni. Inodi ngayinye esebenza kahle kufanele ngokushesha noma kamuva amukele inani lokugcina futhi aliqinisekise: “Kimi, leli nani liyiqiniso, ngivumelana nalo lonke uhlelo.”
Isibonelo sokuthi i-algorithm yokuvumelana isebenza kanjani
Ngenkathi izici ze-algorithm zingase zingacaci ngokuphelele. Ngakho-ke, sizofanekisa ngesibonelo ukuthi yiziphi izigaba i-algorithm yokuvumelana elula ehamba kuzo ohlelweni olunemodeli yokuthumela imiyalezo, lapho wonke ama-node asebenza njengoba kulindelekile, imilayezo ayilahleki futhi akukho lutho oluphukayo (ingabe lokhu kuyenzeka ngempela?).
- Konke kuqala ngesiphakamiso somshado (Phakamisa). Ake sicabange ukuthi iklayenti elixhunywe ku-node ebizwa ngokuthi "Node 1" futhi laqala ukuthengiselana, lidlulisela inani elisha ku-node - O. Kusukela manje kuqhubeke, sizobiza "I-Node 1" ukuphakamisa. Njengomhlongozi, "I-Node 1" manje kufanele yazise lonke uhlelo ukuthi inedatha entsha, futhi ithumela imilayezo kuwo wonke amanye ama-node: "Bheka! Incazelo ethi “O” yeza kimi futhi ngifuna ukuyibhala phansi! Sicela uqinisekise ukuthi uzophinda urekhode u-“O” kulogi yakho.”
- Isigaba esilandelayo sivotela inani elihlongozwayo (Ukuvota). Kwenzelweni? Kungenzeka ukuthi amanye ama-node athole ulwazi lwakamuva, futhi anedatha yokwenziwayo okufanayo.
Lapho i-node ethi “Node 1” ithumela isiphakamiso sayo, amanye amanodi ahlola amalogi awo ukuze athole idatha yalo mcimbi. Uma kungekho ukuphikisana, amanodi amemezela: “Yebo, anginayo enye idatha yalo mcimbi. Inani elithi “O” liwulwazi lwakamuva olusifanele.”Kunoma isiphi esinye isimo, ama-node angaphendula ku-“Node 1”: “Lalela! Nginedatha yakamuva kakhulu kulokhu okwenziwayo. Hhayi 'O', kodwa okuthile okungcono."
Esigabeni sokuvota, ama-node afika esinqumweni: noma wonke amukela inani elifanayo, noma oyedwa wabo ivota ngokumelene, okubonisa ukuthi unedatha yakamuva.
- Uma umjikelezo wokuvota ube yimpumelelo futhi wonke umuntu evuna, uhlelo luzodlulela esigabeni esisha - Ukwamukela inani. "I-Node 1" iqoqa zonke izimpendulo ezivela kwamanye ama-node futhi ibike: "Wonke umuntu uvumelene nenani elithi "O"! Manje ngimemezela ngokusemthethweni ukuthi “O” incazelo yethu entsha, efanayo kuwo wonke umuntu! Kubhale phansi encwadini yakho encane, ungakhohlwa. Kubhale phansi ohlwini lwakho!”
- Amanodi asele athumela isiqinisekiso (Samukelwe) sokuthi abhale phansi inani elithi “O”; akukho okusha okufikile ngalesi sikhathi (uhlobo lokuzibophezela kwezigaba ezimbili). Ngemuva kwalesi sehlakalo esibalulekile, sicabanga ukuthi umsebenzi osabalalisiwe usuphelile.
Ngakho, i-algorithm yokuvumelana esimweni esilula iqukethe izinyathelo ezine: phakamisa, ivota (ukuvota), yamukela (yamukele), qinisekisa ukwamukelwa (kwamukelwe).
Uma ngesinyathelo esithile asikwazanga ukufinyelela esivumelwaneni, i-algorithm iqala futhi, kucatshangelwa ulwazi olunikezwe ama-node anqabe ukuqinisekisa inani elihlongozwayo.
I-algorithm ye-Consensus kusistimu ye-asynchronous
Ngaphambi kwalokhu, yonke into yayibushelelezi, ngoba sasikhuluma ngemodeli yemiyalezo evumelanisiwe. Kodwa siyazi ukuthi emhlabeni wanamuhla sijwayele ukwenza yonke into ngokungahambisani. I-algorithm efanayo isebenza kanjani ohlelweni olunemodeli yemiyalezo engavumelaniyo, lapho sikholelwa ukuthi isikhathi sokulinda impendulo evela ku-node singaba yinde ngokungafanele (ngendlela, ukwehluleka kwe-node kungabuye kubhekwe njengesibonelo uma i-node ingaphendula isikhathi eside ngokunganaki).
Manje njengoba sesiyazi ukuthi i-algorithm yokuvumelana isebenza kanjani ngokomthetho, umbuzo walabo bafundi abanolwazi abenze kuze kube manje: mangaki ama-node ohlelweni lwama-N node anemodeli yomlayezo we-asynchronous angahluleka ukuze uhlelo lusakwazi ukufinyelela ukuvumelana?
Impendulo efanele kanye nokuthethelelwa kungemuva kwe-spoiler.Impendulo efanele yilena: 0. Uma ngisho ne-node eyodwa ohlelweni lwe-asynchronous ihluleka, uhlelo ngeke lukwazi ukufinyelela ukuvumelana. Lesi sitatimende sifakazelwa kuyi-theorem ye-FLP, eyaziwa kakhulu emibuthanweni ethile (1985, Fischer, Lynch, Paterson, ixhumanisa neyokuqala ekugcineni kwesihloko): “Ukungenzeki kokufinyelela ukuvumelana okusabalalisiwe uma okungenani indawo eyodwa yehluleka. .”
Bafo ke sinenkinga, sesijwayele ukuthi yonke into ibe asynchronous. Futhi nakhu. Ungaqhubeka kanjani nokuphila?
Besikhuluma nje ngethiyori, ngezibalo. Kusho ukuthini ukuthi “ukuvumelana akuzuzuzwa”, ukuhumusha kusuka olimini lwezibalo kuya kolwethu - ubunjiniyela? Lokhu kusho ukuthi "akunakwenzeka njalo", i.e. Kunesimo lapho ukuvumelana kungafezeki. Icala elinjani leli?
Lokhu kungukuphulwa kwempahla ye-liveness echazwe ngenhla. Asinaso isivumelwano esifanayo, futhi isistimu ayikwazi ukuba nenqubekelaphambili (ayikwazi ukuqeda ngesikhathi esinqunyelwe) esimweni lapho singenayo impendulo evela kuwo wonke ama-node. Ngoba ohlelweni lwe-asynchronous asinaso isikhathi sokuphendula esingabikezelwa futhi asikwazi ukuthi i-node iphahlazekile noma ithatha isikhathi eside ukuphendula.
Kodwa ngokwenza singathola isixazululo. Vumela i-algorithm yethu ikwazi ukusebenza isikhathi eside uma kwenzeka ukwehluleka (okungenzeka ukuthi ingasebenza unomphela). Kodwa ezimweni eziningi, lapho amanodi amaningi esebenza kahle, sizoba nenqubekelaphambili ohlelweni.
Empeleni, sisebenzisana namamodeli okuxhumana avumelana kancane. I-synchrony eyingxenye iqondwa ngale ndlela elandelayo: esimweni esivamile, sinemodeli ye-asynchronous, kodwa umqondo othile "wesikhathi sokuzinza komhlaba wonke" wephuzu elithile ngesikhathi wethulwa ngokusemthethweni.
Lo mzuzu ngesikhathi ungase ungafiki nganoma yisiphi isikhathi eside, kodwa kufanele ufike usuku olulodwa. Iwashi le-alamu elibonakalayo lizokhala, futhi kusukela ngaleso sikhathi singabikezela i-delta yesikhathi imilayezo ezofika ngayo. Kusukela kulo mzuzu kuqhubeke, isistimu iphenduka isuka ku-asynchronous iye ku-synchronous. Empeleni, sibhekana ngqo nezinhlelo ezinjalo.
I-algorithm ye-Paxos ixazulula izinkinga zokuvumelana
iwumndeni wama-algorithms axazulula inkinga yokuvumelana kumasistimu ahambisana kancane, kuncike ekutheni kungenzeka ukuthi amanye amanodi angahluleka. Umbhali wePaxos ngu . Uphakamise ubufakazi obusemthethweni bokuba khona kanye nokunemba kwe-algorithm ngo-1989.
Kodwa ubufakazi babonakala buyinto encane. Incwadi yokuqala yakhululwa kuphela ngo-1998 (amakhasi angu-33) echaza i-algorithm. Njengoba kwenzeka, kwakunzima kakhulu ukukuqonda, futhi ngo-2001 kwanyatheliswa incazelo yalesi sihloko, eyathatha amakhasi angu-14. Umthamo wokushicilelwa unikezwa ukuze kuboniswe ukuthi empeleni inkinga yokuvumelana ayilula neze, futhi ngemuva kwama-algorithms anjalo kukhona inani elikhulu lomsebenzi wabantu abahlakaniphe kakhulu.
Kuyathakazelisa ukuthi u-Leslie Lamport ngokwakhe waphawula enkulumweni yakhe ukuthi esihlokweni sesibili esichazayo kukhona isitatimende esisodwa, umugqa owodwa (akazange acacise ukuthi iyiphi), engahunyushwa ngezindlela ezahlukene. Futhi ngenxa yalokhu, inani elikhulu lokuqaliswa kwe-Paxos yesimanje alisebenzi ngokuphelele ngendlela efanele.
Ukuhlaziywa okuningiliziwe komsebenzi kaPaxos kungathatha indatshana engaphezu kweyodwa, ngakho-ke ngizozama ukudlulisa kafushane umqondo oyinhloko we-algorithm. Kuzixhumanisi ezisekupheleni kwe-athikili yami uzothola izinto zokungena emanzini kulesi sihloko.
Izindima ku-Paxos
I-algorithm ye-Paxos inomqondo wezindima. Ake sicabangele ezintathu eziyinhloko (kukhona ukuguqulwa ngezindima ezengeziwe):
- Abaphakamisi (amagama angasetshenziswa: abaholi noma abaxhumanisi). Laba abafana abafunda mayelana nevelu entsha kumsebenzisi futhi bathathe indima yokuba umholi. Umsebenzi wabo ukwethula umjikelezo weziphakamiso zevelu entsha kanye nokuxhumanisa ezinye izenzo zama-node. Ngaphezu kwalokho, i-Paxos ivumela ukuba khona kwabaholi abambalwa ezimweni ezithile.
- Abamukeli (Abavoti). Lawa ama-node avotela ukwamukela noma ukwenqaba inani elithile. Indima yabo ibaluleke kakhulu, ngoba isinqumo sincike kubo: yisiphi isimo uhlelo (noma olungeke) ukuya kulo ngemuva kwesigaba esilandelayo se-algorithm yokuvumelana.
- Bafundi. Amanodi avele amukele futhi abhale inani elisha elamukelwayo lapho isimo sesistimu sesishintshile. Abenzi izinqumo, bavele bathole idatha futhi bangayinikeza umsebenzisi wokugcina.
I-node eyodwa ingahlanganisa izindima eziningana ezimweni ezahlukene.
Umqondo wekhoramu
Sicabanga ukuthi sinohlelo lwe N ama-node Futhi kubo esiphezulu F amanodi angase ahluleke. Uma ama-F node ehluleka, kufanele sibe nawo okungenani 2F+1 amanodi owamukelayo.
Lokhu kuyadingeka ukuze sihlale sineningi, ngisho nasesimweni esibi kakhulu, samanodi “okuhle” asebenza ngendlela efanele. Leyo F+1 "amahle" amanodi avumile, futhi inani lokugcina lizokwamukelwa. Kungenjalo, kungase kube nesimo lapho amaqembu ethu ahlukene endawo ethatha izincazelo ezahlukene futhi engakwazi ukuvumelana phakathi kwawo. Ngakho-ke, sidinga iningi eliphelele ukuze siwine ivoti.
Umbono ojwayelekile wokuthi i-algorithm ye-Paxos yokuvumelana isebenza kanjani
I-algorithm ye-Paxos ibandakanya izigaba ezimbili ezinkulu, nazo ezihlukaniswe ngezinyathelo ezimbili ngasinye:
- Isigaba 1a: Lungiselela. Phakathi nesigaba sokulungiselela, umholi (umphakamisi) wazisa wonke ama-node: “Siqala isigaba esisha sokuvota. Sinomzuliswano omusha. Inombolo yalo mzuliswano ngu-n. Manje sesizoqala ukuvota." Okwamanje, ivele ibike ukuqala komjikelezo omusha, kodwa ayibiki ivelu entsha. Umsebenzi walesi sigaba ukuqala umzuliswano omusha nokwazisa wonke umuntu ngenombolo yawo eyingqayizivele. Inombolo eyindingilizi ibalulekile, kufanele ibe yinani elikhulu kunawo wonke amanani okuvota adlule avela kubo bonke abaholi bangaphambilini. Ngoba kungenxa yenombolo eyindilinga ukuthi amanye ama-node ohlelweni azoqonda ukuthi idatha yomholi yakamuva kangakanani. Kungenzeka ukuthi amanye ama-node asenayo imiphumela yokuvota evela emizuliswaneni yakamuva futhi azovele atshele umholi ukuthi usemuva kwezikhathi.
- Isigaba 1b: Isethembiso. Lapho amanodi abamukelayo ethola inombolo yesiteji esisha sokuvota, imiphumela emibili ingenzeka:
- Inombolo n yevoti elisha inkulu kunenombolo yanoma yiliphi ivoti langaphambilini lapho owamukelayo ahlanganyele khona. Bese kuthi owamukelayo athumele isethembiso kumholi sokuthi ngeke abambe iqhaza kwamanye amavoti anenombolo engaphansi kuka-n. Uma owamukelayo esevotele okuthile (okungukuthi, useyamukele kakade inani elithile esigabeni sesibili), khona-ke unamathisela inani elamukelekayo kanye nenombolo yevoti ahlanganyele kulo esithembisweni sakhe.
- Uma kungenjalo, uma owamukelayo eseyazi kakade ngevoti elinenombolo ephezulu, angamane ashaye indiva isinyathelo sokulungiselela futhi angaphenduli kumholi.
- Isigaba 2a: Yamukela. Umholi udinga ukulinda impendulo evela kwikhoramu (iningi lamanodi ohlelweni) futhi, uma inani elidingekayo lezimpendulo litholwa, khona-ke unezinketho ezimbili zokuthuthukiswa kwemicimbi:
- Abanye babamukeli bathumele amanani asebevele bewavotele. Kulokhu, umholi ukhetha inani levoti elinenombolo enkulu. Masibize leli nani ngokuthi x, futhi lithumela umlayezo kuwo wonke amanodi afana nokuthi: “Yamukela (n, x)”, lapho inani lokuqala kuyinombolo yokuvota esinyathelweni salo esithi Phakamisa, futhi inani lesibili yilokho wonke umuntu akuqoqele kona, i.e. inani esilivotela ngempela.
- Uma kungekho noyedwa wabamukeli othumele noma yiziphi izimiso, kodwa bamane bathembisa ukuvota kulo mzuliswano, umholi angabamema ukuthi bavotele inani labo, inani abe ngumholi walo kwasekuqaleni. Masiyibize ngokuthi y. Ithumela umlayezo kuwo wonke ama-node afana nokuthi: “Yamukela (n, y)”, efana nomphumela wangaphambilini.
- Isigaba 2b: Samukelwe. Ngaphezu kwalokho, amanodi owamukelayo, lapho ethola umlayezo othi “Yamukela(...)” ovela kumholi, uyavumelana nawo (thumela isiqinisekiso kuwo wonke ama-node ukuthi avumelana nenani elisha) kuphela uma bengathembisanga okunye (okunye) ) umholi ukubamba iqhaza ekuvoteni ngenombolo eyindilinga n > n, ngaphandle kwalokho abaziba isicelo sokuqinisekisa.
Uma iningi lamanodi liphendule umholi, futhi wonke aqinisekisa inani elisha, inani elisha libhekwa njengelamukelwe. Hooray! Uma iningi lingafinyelelwanga noma kukhona ama-node anqabile ukwamukela inani elisha, khona-ke yonke into iqala kabusha.
Le yindlela i-algorithm ye-Paxos esebenza ngayo. Ngasinye salezi zigaba sinobuqili obuningi, empeleni asizange sicabangele izinhlobo ezahlukene zokwehluleka, izinkinga zabaholi abaningi nokunye okuningi, kodwa inhloso yalesi sihloko iwukwethula kuphela umfundi emhlabeni wekhompiyutha esabalalisiwe ezingeni eliphezulu.
Kuyaqapheleka futhi ukuthi i-Paxos akuyona yodwa yohlobo lwayo, kukhona amanye ama-algorithms, ngokwesibonelo, , kodwa lesi isihloko sesinye isihloko.
Izixhumanisi zezinto zokufunda ngokuqhubekayo
Ileveli yabaqalayo:
- , Preethi Kasireddy, isihloko sebhulogi ku-Medium
- , Adi Kancherla, isihloko sebhulogi ku-Medium
- , Itai Abraham, ibhulogi
- , Itai Abraham, isihloko sebhulogi
Izinga le-Leslie Lamport:
- , uFischer, uLynch noPaterson, iphepha lokucwaninga, 1985
- , Leslie Lamport, iphepha lokucwaninga, 1998
- , Leslie Lamport, iphepha lokucwaninga, 2001
Source: www.habr.com