Haddaba, aan qiyaasno. Qolka waxaa ku xiran 5 bisadood, si ay u kiciyaan milkiilaha, dhammaan waxay u baahan yihiin inay ku heshiiyaan arrintan dhexdooda, sababtoo ah waxay furi karaan oo keliya albaabka iyadoo shan ka mid ah ay ku tiirsan yihiin. Haddii mid ka mid ah bisadaha uu yahay bisadda Schrödinger, oo bisadaha kale aysan ogeyn go'aankiisa, su'aashu waxay soo baxaysaa: "Sidee u samayn karaan?"
Maqaalkan, waxaan kuu sheegi doonaa si fudud oo ku saabsan qaybta aragtida adduunka ee nidaamyada la qaybiyey iyo mabaadi'da hawlgalkooda. Waxaan sidoo kale si qotodheer u baari doonaa fikradda ugu weyn ee ku hoos jirta Paxos.
Marka horumariyayaashu isticmaalaan kaabayaasha daruuriga ah, xog ururin kala duwan, oo ay ka shaqeeyaan kooxo tiro badan oo nood ah, waxay ku kalsoon yihiin in xogtu noqon doonto mid dhamaystiran, sugan, oo had iyo jeer la heli karo. Laakiin aaway dammaanad qaadku?
Asal ahaan, dammaanadaha aan haysanno waa dammaanad-bixiye. Waxay ku qeexan yihiin dukumeentiga sida soo socota: "Adeeggani waa mid la isku halleyn karo, wuxuu leeyahay SLA, ha ka welwelin, wax walba waxay u shaqeyn doonaan si loo qaybiyo sida aad filayso."
Waxaan u muuqannaa inaan aaminsanahay sida ugu fiican, sababtoo ah ragga caqliga leh ee shirkadaha waaweyn waxay noo xaqiijiyeen in wax walba ay fiicnaan doonaan. Ma waydiino su'aasha: sababta, dhab ahaantii, tani ma shaqeyn karto gabi ahaanba? Ma jirtaa sabab rasmi ah oo ku saabsan hawlgalka saxda ah ee nidaamyadan?
Waxaan dhawaan tagay waxaana aad u dhiiri galiyay mawduucan. Casharrada dugsigu waxay ahaayeen kuwo la mid ah fasallada calculus marka loo eego shay la xidhiidha nidaamka kombayutarka. Laakiin tani waa sida saxda ah ee algorithms-yada ugu muhiimsan ee aan isticmaalno maalin kasta, iyada oo aan xitaa ogeyn, ayaa la xaqiijiyay hal mar.
Inta badan nidaamyada casriga ah ee la qaybiyey waxay adeegsadaan Paxos consensus algorithm iyo wax ka beddelkeeda kala duwan. Waxa ugu fiican ayaa ah in ansaxnimada iyo, mabda'a ahaan, suurtogalnimada jiritaanka algorithm kan si fudud loogu cadeyn karo qalin iyo warqad. Ficil ahaan, algorithm-ka waxaa loo isticmaalaa habab waaweyn oo ku socda tiro badan oo nood ah oo daruuraha ah.
Tilmaan fudud oo ku saabsan waxa laga wada hadli doono marka xigta: Hawsha laba JeneraalAynu eegno diirimaad .
Waxaan leenahay laba ciidan - casaan iyo caddaan. Ciidamada cadaanka ah ayaa ku sugan magaalada go’doonsan. Ciidamada cas oo ay hogaaminayaan jeneraal A1 iyo A2 ayaa ku sugan labada dhinac ee magaalada. Madaxda cas-cas shaqadoodu waa inay weeraraan magaalada cad oo ay guulaystaan. Si kastaba ha ahaatee, ciidanka Jeneraal kasta oo cas si gaar ah ayaa ka yar ciidanka cadaanka ah.
Shuruudaha guusha ee kuwa casaanka ah: labada jeneraal waa inay isku mar weeraraan si ay faa'iido tirooyin ah uga helaan caddaanka. Si taas loo sameeyo, jeneraalada A1 iyo A2 waxay u baahan yihiin inay heshiis wada gaadhaan. Haddii qof kastaa si gooni ah u weeraro, madax-guduudan ayaa lumin doona.
Si heshiis loo gaaro, jeneraalada A1 iyo A2 waxay isu diri karaan wargeeyayaal dhexmara dhulka magaalada cad. Rasuulku wuxuu si guul leh u gaari karaa jeneraal xulafo ah ama waxaa dhici karta in cadowgu soo dhexgalo. Su’aal: ma jiraan xiriiro isdaba joog ah oo ka dhexeeya jeneraalada timo-casaanka ah (isku xigxiga soo dirida fariimaha A1 ilaa A2 iyo ka soo dirida A2 ilaa A1), kaas oo loo ballan qaaday inay ku heshiiyaan weerar saacadda X. Halkan. dammaanad qaadyadu waxay ka dhigan tahay in labada janaraalba ay heli doonaan xaqiijin aan caddayn oo ah in xulafada (General kale) uu si xaqiiqo ah u weerari doono wakhtiga loo cayimay X.
Ka soo qaad in A1 uu farriin u soo diro A2 fariinta: "Aan weerarno maanta saqda dhexe!" General A1 ma weerari karo iyada oo aan la xaqiijin General A2. Haddii farriinta ka socota A1 uu yimaado, markaa General A2 wuxuu soo dirayaa xaqiijin fariinta: "Haa, aan dilno kuwa cadaanka ah maanta." Laakin hadda General A2 ma oga in uu rasuulkiisii yimid iyo in kale, ma hayo dammaanad qaadka in weerarku isku mar noqon doono. Hadda General A2 wuxuu mar kale u baahan yahay xaqiijin.
Haddaynu sii sharaxno xidhiidhkooda, waxa inoo soo baxaysa in si kasta oo ay tahay inta wareegtada fariimaha la is waydaarsado, aanay jirin dammaanad lagu dammaanad qaadi karo in labada janaraalba fariimahooda ay heleen (iyada oo loo malaynayo in mid ka mid ah Rasuulkuba la qaban karo).
Dhibaatada Labada Guud waa tusaale weyn oo ah nidaam aad u fudud oo la qaybiyey halkaas oo ay jiraan laba nood oo leh isgaarsiin aan la isku halleyn karin. Tani waxay ka dhigan tahay in aanaan haysanin 100% dammaanad ah in la isku daray. Dhibaatooyinka la midka ah waxaa looga hadlayaa oo kaliya miisaan weyn dambe ee maqaalka.
Waxaan soo bandhigeynaa fikradda nidaamyada la qaybiyey
Nidaamka la qaybiyay waa koox kombiyuutaro ah (hadda kadib waxaan ugu yeeri doonaa noodes) kuwaas oo is dhaafsan kara fariimaha. Node kasta oo gaar ah waa nooc ka mid ah hay'ad madaxbannaan. Noodku iskii buu u farsamayn karaa hawlaha, laakiin si loola xidhiidho qanjidhada kale, waxay u baahan tahay inay dirto oo hesho fariimaha.
Sida saxda ah ee farriimaha loo fuliyo, xeerar noocee ah ayaa la isticmaalaa - tani maaha mid noo daneynaysa macnaha guud. Waa muhiim in qanjidhada nidaamka qaybsan ay isku dhaafsan karaan xogta midba midka kale iyagoo diraya farriimaha.
Qeexitaanku laftiisu uma eka mid aad u adag, laakiin waa in aan xisaabta ku darnaa in nidaamka la qaybiyey uu leeyahay tiro sifooyin ah oo muhiim noo noqon doona.
Sifooyinka nidaamyada qaybsan
- Isku-tanaasul - suurtogalnimada dhacdooyin isku mar ah ama isku mid ah oo ka dhaca nidaamka. Waxaa intaa dheer, waxaan u tixgelin doonaa dhacdooyinka ka dhaca laba nuurad oo kala duwan inay yihiin kuwo isku mid ah ilaa inta aynaan haysanin nidaam cad oo dhacdooyinkan ah. Laakiin, sida caadiga ah, ma hayno.
- Ma jiro saacad caalami ah. Ma hayno nidaam cad oo dhacdooyin ah sababtoo ah saacad la'aanta caalamiga ah. Dunida caadiga ah ee dadka, waxaan la qabsanay xaqiiqda ah in aan haysanno saacado iyo waqti gabi ahaanba. Wax kastaa way isbeddelaan marka ay timaado nidaamyada qaybsan. Xataa saacadaha atomikada ee aadka u saxda ah ayaa leexleexan, waxaana laga yaabaa inay jiraan xaalado aynaan sheegi karin labada dhacdo midkood ee dhacay. Sidaa darteed, sidoo kale kuma tiirsanaan karno waqtiga.
- Fashil madax-banaan ee qanjidhada nidaamka. Dhibaato kale ayaa jirta: wax ayaa khaldami kara si fudud sababtoo ah qanjidhadayadu weligeed ma sii waaraan. Hard Drive-ku waxa laga yaabaa inuu fashilmo, mishiinkii farsamada ee daruuraha ku jiray ayaa laga yaabaa inuu dib u bilaabo, shabakadu way ilbidhici kartaa fariimahana way lumi doonaan. Waxaa intaa dheer, waxaa jiri kara xaalado ay noodhadhku shaqeeyaan, laakiin isla mar ahaantaana ka soo horjeeda nidaamka. Dhibaatooyinka fasalka ugu dambeeya xitaa waxay heleen magac gaar ah: dhibaato . Tusaalaha ugu caansan ee nidaamka qaybsan ee dhibaatadani waa Blockchain. Laakiin maanta ma tixgelin doono fasalkan gaarka ah ee dhibaatooyinka. Waxaan xiisayn doonaa xaaladaha kuwaas oo si fudud hal ama ka badan laga yaabo inay ku fashilmaan.
- Moodooyinka isgaadhsiinta (qaababka fariimaha) ee u dhexeeya qanjidhada. Waxaan horey u xaqiijinay in noodhadhku ay ku xiriiraan isdhaafsiga fariimaha. Waxaa jira laba nooc oo farimo ah oo si fiican loo yaqaan: synchronous iyo asynchronous.
Qaababka isgaadhsiinta ee ka dhexeeya qanjidhada ee nidaamyada qaybsan
Moodeelka isku midka ah - Waxaan si hubaal ah u ognahay in uu jiro waqti go'an oo la yaqaan oo dhambaalka ah inta lagu jiro dammaanad qaadida fariinta in ay ka soo gaarto mindhicir ilaa mid kale. Haddii wakhtigan la dhaafay oo farriintu aysan iman, waxaan si ammaan ah u dhihi karnaa in noodhka uu fashilmay. Qaabkan waxaan ku leenahay waqtiyo sugitaan la saadaalin karo.
Moodeelka Asynchronous - moodooyinka asynchronous waxaan u aragnaa in wakhtiga sugitaanku uu yahay mid xadidan, laakiin ma jiro waqti sidaas oo kale ah oo aan dammaanad qaadi karno in noodhka uu ku guuldareystay. Kuwaas. Wakhtiga sugitaanka fariinta ka imanaysa noodhka waxay noqon kartaa mid dheer oo aan sabab lahayn. Tani waa qeexid muhiim ah, oo aan ka sii hadli doono.
Fikradda la isku raacsan yahay ee nidaamyada qaybsan
Intaynaan si rasmi ah u qeexin fikradda la isku raacsan yahay, aan ka fiirsanno tusaale xaalad aan u baahanahay, oo ah - Ku celcelinta Mashiinka Gobolka.
Waxaan haynaa wax loo qaybiyey. Waxaan rabnaa in ay noqoto mid joogto ah oo ay ku jirto xog isku mid ah dhammaan qanjidhada nidaamka la qaybiyay. Marka mid ka mid ah qanjidhada uu barto qiimo cusub oo uu u qori doono log, hawshiisu waxay noqonaysaa inay bixiso qiimahan dhammaan noodyada kale si loggu u cusbooneysiiyo dhammaan noodyada iyo nidaamka u guuro xaalad cusub oo joogto ah. Xaaladdan oo kale, waxaa muhiim ah in qanjidhada ay ku heshiiyaan dhexdooda: dhammaan qanjidhada waxay ku heshiiyaan in qiimaha cusub ee la soo jeediyay uu sax yahay, dhammaan qanjidhada ayaa aqbalaya qiimahan, oo kaliya kiiskan qof kastaa wuxuu qori karaa qiimaha cusub ee log.
Si kale haddii loo dhigo: mid ka mid ah qanjidhada ayaa diiday in ay hayso macluumaad dheeraad ah oo la xidhiidha, qiimaha la soo jeediyayna waa khalad. Heshiiska u dhexeeya qanjidhada iyo heshiiska qiimaha saxda ah ee la aqbalay waa la isku raacsan yahay nidaamka qaybsan. Marka xigta, waxaan ka hadli doonaa algorithms kuwaas oo u oggolaanaya nidaamka la qaybiyey in la dammaanad qaado si loo gaaro is-afgarad.
Si rasmi ah, waxaan u qeexi karnaa algorithm la isku raacsan yahay (ama si fudud algorithm la isku raacsan yahay) sida hawl gaar ah oo ka wareejinaysa nidaamka qaybinta gobolka A ilaa gobolka B. Waxaa intaa dheer, gobolkan waxaa aqbalaya dhammaan qanjidhada, iyo dhammaan qanjidhada ayaa xaqiijin kara. Sida ay soo baxday, hawshani maaha mid aad u fudud sida ay u muuqato jaleecada hore.
Tilmaamaha Algorithm-ka Consensus
Algorithm-ka la isku raacsan yahay waa inuu lahaadaa saddex sifo oo nidaamku u sii jiro oo uu yeesho xoogaa horumar ah oo laga guurayo gobol ilaa gobol:
- Heshiiska - Dhammaan qanjidhada si sax ah u shaqeynaya waa inay qaataan qiime isku mid ah (maqaallada gurigan waxaa sidoo kale loo yaqaan hantida badbaadada). Dhammaan qanjidhada hadda shaqeeya (aanan ku guuldareysan ama lumin xiriirka kuwa kale) waa inay la yimaadaan heshiis oo ay aqbalaan qaar ka mid ah qiimaha guud ee kama dambaysta ah.
Waxaa muhiim ah in la fahmo halkan in qanjidhada nidaamka qaybinta ee aan tixgelineyno ay rabaan in ay ku heshiiyaan. Taasi waa, waxaan hadda ka hadlaynaa nidaamyada ay wax si fudud u fashilmi karaan (tusaale ahaan, qaar ka mid ah noodhka ayaa ku guuldareysta), laakiin nidaamkan waxaa hubaal ah ma jiraan nodes kuwaas oo si ula kac ah uga shaqeeya kuwa kale (hawsha guud ee Byzantine). Hantidan awgeed, nidaamku waa mid joogto ah.
- Integrity - haddii dhammaan qanjidhada si sax ah u shaqeeyaa ay bixiyaan qiime isku mid ah v, taas oo macnaheedu yahay noodh kasta oo si sax ah u shaqeeya waa inuu aqbalo qiimahan v.
- Joojinta - Dhammaan qanjidhada si sax ah u shaqeeya ayaa ugu dambeyntii qaadan doona qiimo gaar ah (hanti nololeed), taas oo u oggolaanaysa algorithm in uu horumar ka sameeyo nidaamka. Shakhsi kasta oo si sax ah u shaqeeya waa inuu si dhaqsa ama dambe u aqbalo qiimaha ugu dambeeya oo uu xaqiijiyaa: "Aniga ahaan, qiimahani waa run, waan ku raacsanahay nidaamka oo dhan."
Tusaale ahaan sida algorithm-ka la isku raacsan yahay u shaqeeyo
Halka sifooyinka algorithmamka laga yaabo inaysan si buuxda u caddayn. Sidaa darteed, waxaan ku tusin doonaa tusaale ahaan marxaladaha algorithm-ka ugu fudud ee la isku raacsan yahay ee ku dhex mara nidaam leh qaab fariin isku dhafan, kaas oo dhammaan noodyadu u shaqeeyaan sidii la filayay, farriimaha lama lumin oo waxba ma jabaan (tani dhab ahaantii ma dhacdaa?).
- Dhammaan waxay ka bilaabmaan hindisaha guurka (Propose). Aynu ka soo qaadno in macmiilku ku xidhan yahay noodhka loo yaqaan "Node 1" oo bilaabay macaamil ganacsi, isaga oo u gudbinaya qiime cusub qanjirka - O. Hadda wixii ka dambeeya, waxaan wici doonaa "Node 1" soo jeedin. Soo jeedin ahaan, "Node 1" waa inuu hadda ogeysiiyaa nidaamka oo dhan inuu haysto xog cusub, oo ay u dirto farriimaha dhammaan qanjidhada kale: "Fiiri! Macnaha "O" ayaa ii yimid oo waxaan rabaa inaan qoro! Fadlan xaqiiji inaad sidoo kale ku duubi doonto "O" logkaaga."
- Marxaladda xigta waa u codeynta qiimaha la soo jeediyay (Codeynta). maxaa loogu talagalay? Waxaa laga yaabaa inay dhacdo in qanjidhada kale ay heleen macluumaad dhow oo dheeraad ah, waxayna hayaan xog ku saabsan isla macaamil ganacsi.
Marka noodhka "Node 1" soo diro soo jeedintiisa, qanjidhada kale waxay hubinayaan diiwaankooda xogta dhacdadan. Haddii aysan jirin wax is burinaya, noodhadhku waxay ku dhawaaqayaan: "Haa, ma hayo xog kale oo dhacdadan ah. Qiimaha "O" waa macluumaadkii ugu dambeeyay ee aan u qalano."Xaalad kasta oo kale, noodhadhku waxay uga jawaabi karaan "Node 1": "Dhagayso! Waxaan hayaa xog badan oo cusub oo ku saabsan wax kala iibsiga. Ma aha 'O', laakiin wax ka fiican."
Marxaladda cod bixinta, noodhadhku waxay yimaadaan go'aan: dhammaantood waxay aqbalaan qiime isku mid ah, ama mid ka mid ah ayaa ka soo horjeeda, taas oo muujinaysa in uu haysto xog cusub.
- Haddii wareegga codbixinta uu ahaa mid guul leh oo qof kastaa uu taageeray, markaa nidaamku wuxuu u guuraa marxalad cusub - Ogolaanshaha qiimaha. "Node 1" waxay ka soo ururisaa dhammaan jawaabaha noodhka kale iyo warbixinnada: "Qof walba wuxuu ku heshiiyey qiimaha "O"! Hadda waxaan si rasmi ah u caddaynayaa in "O" uu yahay macneheena cusub, oo isku mid ah qof kasta! Ku qor buuggaaga yar, ha ilaawin. Ku qor loggaaga!”
- Nudaha soo haray waxay soo diraan xaqiijin (Waa la aqbalay) inay qoreen qiimaha "O", wax cusub oo waqtigan soo gaaray ma jiro (nooc laba waji ah oo ballanqaad ah). Dhacdadan muhiimka ah ka dib, waxaan tixgelineynaa in macaamilka la qaybiyay uu dhammaaday.
Haddaba, algorithm-ka la isku raacsan yahay ee kiis fudud wuxuu ka kooban yahay afar tillaabo: soo jeedin, codeyn (codbixin), aqbal (aqbal), xaqiiji aqbalaadda (la aqbalay).
Haddii tilaabo ka mid ah aynaan awoodin in aan heshiis gaarno, ka dibna algorithm-ku mar kale ayuu bilaabmaa, iyada oo la tixgelinayo macluumaadka ay bixiyeen qanjidhada oo diiday in la xaqiijiyo qiimaha la soo jeediyay.
Algorithm isku raacsanaanta nidaamka asynchronous
Taas ka hor, wax waliba way siman yihiin, sababtoo ah waxaan ka hadlaynay qaabka fariimaha isku midka ah. Laakiin waxaynu ognahay in dunida casriga ah aynu u barannay in aynu wax walba u samayno si isku mid ah. Sidee algorithm la mid ah u shaqeeyaa nidaamka leh qaabka fariinta asynchronous, halkaas oo aan aaminsanahay in waqtiga sugitaanka jawaabta qanjirada ay noqon karto mid dheer oo aan sabab lahayn (sida, fashilka qanjidhada ayaa sidoo kale loo tixgelin karaa tusaale ahaan marka Noodku wuxuu ka jawaabi karaa wakhti dheer oo aan sabab lahayn).
Hadda oo aan ognahay sida algorithm la isku raacsan yahay u shaqeeyo mabda'a, su'aal loogu talagalay akhristayaasha wax-is-weydiinta leh ee illaa hadda sameeyay: immisa qanjidhada N oo leh qaabka fariinta asynchronous ayaa ku fashilmi kara si nidaamku weli u gaaro heshiis?
Jawaabta saxda ah iyo garnaqsiga ayaa ka dambeeya qaswadayaasha.Jawaabta saxda ah waa: 0. Haddii xitaa hal noode ee nidaamka asynchronous uu ku guuldareysto, nidaamku ma awoodi doono inuu gaaro heshiis la isku raacsan yahay. Bayaankan waxaa lagu caddeeyey aragtida FLP, oo si fiican loo yaqaan goobo gaar ah (1985, Fischer, Lynch, Paterson, isku xirka asalka dhammaadka maqaalka): "Suruurtagalnimada ah in la gaaro heshiis la qaybiyey haddii ugu yaraan hal nood uu guuldareysto. .”
Nimanyahow, markaas dhibaato ayaa na haysata, wax kasta oo aan la qabsanay ayaannu la qabsannay. Waana kan. Sida loo sii noolaado?
Waxaan ka hadlaynay uun aragti, xisaab. Maxay la macno tahay "lagu heshiiyey lama gaari karo" micnaha, anagoo ka turjumaya luqadda xisaabta oo keenna - injineernimada? Tani waxay ka dhigan tahay in "mar walba aan la gaari karin", i.e. Waxaa jirta kiis aan la isku raacsanayn. Kani waa nooc noocee ah?
Tani waa dhab ahaan ku xadgudubka hantida nolosha ee kor lagu tilmaamay. Ma lihin heshiis guud, nidaamkuna horumar ma yeelan karo (ma dhammayn karo waqti xaddidan) haddii aynaan jawaab ka helin dhammaan noodaha. Sababtoo ah nidaamka asynchronous ma hayno wakhti jawaab celin la saadaalin karo mana ogaan karno in noodu burburtay ama ay wakhti dheer qaadanayso in laga jawaabo.
Laakiin ficil ahaan waxaan ku heli karnaa xal. U ogolow algoorithmsyadu inay awoodaan inay shaqeeyaan muddo dheer haddii ay dhacdo guuldarrooyin (waxaa suurtagal ah inay si aan xad lahayn u shaqeyn karto). Laakiin xaaladaha intooda badan, marka qanjidhada intooda badani ay si sax ah u shaqeeyaan, waxaanu horumar ka samayn doonaa nidaamka.
Ficil ahaan, waxaanu wax ka qabanaa moodooyinka isgaadhsiinta ee qayb ahaan isku xidhan. Isku-duubnida qayb ka mid ah waxa loo fahmayaa sidan soo socota: guud ahaan, waxaanu leenahay qaab asynchronous ah, laakiin fikrad gaar ah oo ah "waqtiga xasilinta caalamiga ah" ee waqti cayiman ayaa si rasmi ah loo soo bandhigay.
Wakhtigan wakhtigan ku jira ma iman karo wakhti kasta, laakiin waa inay timaadaa hal maalin. Saacada alaarmiga dalwaddu way soo wici doontaa, laga bilaabo wakhtigaas waxaan saadaalin karnaa wakhtiga delta ee ay fariimaha u iman doonaan. Laga bilaabo wakhtigan, nidaamku wuxuu ka noqdaa asynchronous wuxuuna noqdaa isku mid. Ficil ahaan, waxaan si sax ah ula macaamilnaa nidaamyada noocaas ah.
Algorithm-ka Paxos wuxuu xalliyaa dhibaatooyinka la isku raacsan yahay
waa qoys algorithms ah oo xaliya dhibaatada la isku raacsan yahay ee nidaamyada qayb ahaan isku xidhan, iyada oo ay ku xidhan tahay suurtogalnimada in qaar ka mid ah noodhka ay fashilmaan. Qoraaga Paxos waa . Waxa uu soo jeediyay caddayn rasmi ah oo ku saabsan jiritaanka iyo saxnaanta algorithm ee 1989.
Laakiin caddayntu waxay noqotay wax aan macno lahayn. Daabacaaddii ugu horreysay waxa la sii daayay kaliya 1998 (33 bog) oo qeexaya algorithm. Sida ay soo baxday, aad bay u adagtahay in la fahmo, 2001-dii waxaa la daabacay sharraxaadda maqaalka, kaas oo qaatay 14 bog. Mugga daabacaadda ayaa la bixiyaa si loo muujiyo in xaqiiqda ah dhibaatada la isku raacsan yahay ma aha mid fudud, oo ka dambeeya algorithms-yada noocan oo kale ah ayaa ku jira shaqo aad u badan oo ay qabtaan dadka ugu caqli badan.
Waxa xiiso leh in Leslie Lamport laftiisu uu muxaadaradiisa ku xusay in maqaalka labaad ee sharraxaadda uu ku jiro hal odhaah, hal sadar (ma aanu cayimin midka), kaas oo loo fasiran karo siyaabo kala duwan. Taas awgeed, tiro badan oo ka mid ah hirgelinta Paxos casriga ah si buuxda uma shaqeeyaan.
Falanqaynta faahfaahsan ee shaqada Paxos waxay qaadan doontaa in ka badan hal maqaal, markaa waxaan isku dayi doonaa inaan si kooban u gudbiyo fikradda ugu muhiimsan ee algorithm. Xidhiidhada ku yaal dhamaadka maqaalkayga waxaad ka heli doontaa agab aad u sii quusto mawduucan.
Doorarka Paxos
Algorithm-ka Paxos wuxuu leeyahay fikradda doorarka. Aynu tixgelinno saddex ka mid ah kuwa ugu waaweyn (waxaa jira isbeddello leh doorar dheeri ah):
- Soo-jeediyeyaal (ereyada sidoo kale waa la isticmaali karaa: hoggaamiyeyaasha ama isku-duwayaasha). Kuwani waa nimanka ka barta adeegsadaha wax ku saabsan qiime cusub oo qaata doorka hoggaamiyaha. Shaqadoodu waa in ay bilaabaan wareegyo soo jeedin ah oo loogu talagalay qiime cusub oo ay isku dubbaridaan ficillada dheeraadka ah ee qanjidhada. Waxaa intaa dheer, Paxos waxay u ogolaataa joogitaanka hoggaamiyeyaal dhowr ah xaaladaha qaarkood.
- Aqbalayaasha (Codbixiyayaasha). Kuwani waa noodhadhka u codeeya inay aqbalaan ama diidaan qiime gaar ah. Doorkoodu waa mid aad muhiim u ah, sababtoo ah go'aanku wuxuu ku xiran yahay iyaga: waa maxay gobolka nidaamku (ama uusan) tagi doonin ka dib marxaladda xigta ee algorithm-ka la isku raacsan yahay.
- Barteyaasha. Nodes si fudud u aqbala oo u qora qiimaha cusub ee la aqbalay marka xaalada nidaamku is bedesho. Ma sameeyaan go'aamo, kaliya waxay helayaan xogta waxayna siin karaan isticmaalaha ugu dambeeya.
Hal noodu waxay isku dari kartaa doorar dhowr ah xaalado kala duwan.
Fikradda Kooramka
Waxaan u qaadaneynaa inaan leenahay nidaam N noodhadhka Oo iyaga ka mid ah ugu badnaan F noodhadhku way fashilmi karaan. Haddii qanjidhada F ay ku guuldareystaan, markaa waa inaan haysanaa ugu yaraan 2F+1 qanjidhada aqbalaha.
Tani waa lagama maarmaan si aan had iyo jeer u helno aqlabiyadda, xitaa xaaladda ugu xun, ee noodhka "wanaagsan" ee si sax ah u shaqeeya. Taasi waa F+1 "wanaagsan" noodes ku heshiiyey, iyo qiimaha ugu dambeeya waa la aqbali doonaa. Haddii kale, waxaa dhici karta inay jirto xaalad ay kooxaheenna maxalliga ah ay qaataan macnayaal kala duwan oo ay ku heshiin waayaan dhexdooda. Sidaa darteed, waxaan u baahanahay aqlabiyad buuxda si aan ugu guuleysano codka.
Fikradda guud ee sida Paxos consensus algorithm u shaqeyso
Algorithm ee Paxos waxay ku lug leedahay laba weji oo waaweyn, kuwaas oo iyaguna loo qaybiyay laba tillaabo midkiiba:
- Wajiga 1a: Diyaari. Inta lagu jiro marxaladda diyaarinta, hogaamiyaha (proposor) wuxuu ku wargelinayaa dhammaan qanjidhada: "Waxaan bilaabaynaa weji cusub oo codbixineed. Waxaan leenahay wareeg cusub. Tirada wareegani waa n. Hadda waxaan bilaabi doonaa codeynta." Hadda, waxay si fudud u soo sheegaysaa bilawga wareegga cusub, laakiin ma soo sheegto qiime cusub. Hawsha marxaladani waa in la bilaabo wareeg cusub oo qof walba la ogeysiiyo lambarkiisa gaarka ah. Lambarka wareeggu waa muhiim, waa inuu ahaadaa qiimo ka weyn dhammaan tirooyinka codbixinta ee hore ee dhammaan hoggaamiyeyaashii hore. Sababtoo ah waxay ku mahadsan tahay lambarka wareega in qanjidhada kale ee nidaamka ay fahmi doonaan sida ugu dhow ee xogta hogaamiyaha. Waxay u badan tahay in noodhadhka kale ay horeba u heleen natiijooyin codbixineed wareegyo dambe oo si fudud u sheegi doona hoggaamiyaha inuu ka dambeeyaa wakhtiyada.
- Wajiga 1b: Ballanqaad. Marka qanjidhada aqbaleyuhu ay helaan tirada marxaladda codbixinta cusub, laba natiijo ayaa suurtagal ah:
- Tirada n ee codka cusub ayaa ka badan tiradii codbixintii hore ee uu ka qaybqaatay aqbaluhu. Dabadeed aqbaluhu waxa uu u diraa ballan qaad ah in aanu ka qayb galayn codad dambe oo nambar ka hooseeya n. Haddii qofka aqbalaya uu mar hore u codeeyay shay (taas oo ah, waxay hore u aqbashay qaar ka mid ah qiimaha wejiga labaad), ka dibna waxay ku dhejinaysaa qiimaha la aqbalay iyo tirada codadka uu ka qaybqaatay ballankeeda.
- Haddii kale, haddii aqbaluhu uu hore u yaqaanay codka tirada sare leh, waxay si fudud u diidi kartaa tallaabada diyaarinta oo aan u jawaabin hoggaamiyaha.
- Wajiga 2a: Aqbal. Hogaamiyuhu wuxuu u baahan yahay inuu sugo jawaabta kooramka (inta badan qanjidhada nidaamka) iyo, haddii tirada jawaabaha ee loo baahan yahay la helo, markaa wuxuu leeyahay laba ikhtiyaar oo horumarinta dhacdooyinka:
- Qaar ka mid ah aqbalayaasha waxay soo direen qiyamka ay hore ugu codeeyeen. Xaaladdan oo kale, hoggaamiyaha ayaa ka dooranaya qiimaha codka leh tirada ugu badan. Aan u yeerno qiimahan x, waxayna farriin u diraysaa dhammaan qanjidhada sida: "Aqbal (n, x)", halkaasoo qiimaha ugu horreeya uu yahay lambarka codeynta ee ka timaadda tillaabada u gaarka ah, qiimaha labaadna waa waxa qof kastaa ku soo ururay. i.e. qiimaha aan runtii u codeyno.
- Haddii mid ka mid ah kuwa aqbalaya uusan soo dirin wax qiyam ah, laakiin ay si fudud u ballanqaadeen inay u codeeyaan wareeggan, hoggaamiyaha ayaa ku martiqaadi kara inay u codeeyaan qiimahooda, qiimihii uu ku noqday hogaamiye markii hore. Aan u yeerno y. Waxay fariin u dirtaa dhammaan qanjidhada sida: "Aqbal (n, y)", oo la mid ah natiijadii hore.
- Wajiga 2b: Waa la aqbalay. Dheeraad ah, qanjidhada aqbalaha, markay helaan fariinta "Aqbal (...)" ee hogaamiyaha, waxay ku heshiiyaan (u dir xaqiijinta dhammaan noodhadhka inay ku raacsan yihiin qiimaha cusub) kaliya haddii aysan u ballan qaadin qaar (kale) ) hogaamiyaha si uu uga qayb qaato codaynta oo leh wareeg ah n > n, haddii kale way iska indhatiraan codsiga xaqiijinta.
Haddii inta badan qanjidhada ay u jawaabaan hogaamiyaha, oo dhammaantood ay xaqiijiyeen qiimaha cusub, ka dibna qiimaha cusub ayaa loo tixgeliyaa in la aqbalay. Hooray! Haddii aqlabiyadda aan la gaarin ama ay jiraan qanjidhada diidaya inay aqbalaan qiimaha cusub, markaa wax walbaa way bilaabmaan.
Tani waa sida Paxos algorithm u shaqeyso. Mid kasta oo ka mid ah marxaladahani waxay leedahay khiyaamo badan, ficil ahaan ma tixgelin noocyada kala duwan ee guul-darrada, dhibaatooyinka hoggaamiyeyaasha badan iyo wax badan oo kale, laakiin ujeedada maqaalkani waa kaliya in aan akhristaha u soo bandhigo adduunka xisaabinta la qaybiyey oo heer sare ah.
Waxaa sidoo kale xusid mudan in Paxos uusan ahayn midka kaliya ee noociisa ah, waxaa jira algorithms kale, tusaale ahaan, , laakiin tani waa mawduuc maqaal kale.
Xidhiidhada agabka waxbarasho ee dheeraadka ah
Heerka bilowga:
- , Preethi Kasireddy, maqaal blog ah oo ku saabsan Dhexdhexaad
- , Adi Kancherla, maqaal blog ah oo ku saabsan Dhexdhexaad
- , Itai Abraham, blog
- , Itai Abraham, maqaal blog
Heerka Leslie Lamport:
- , Fischer, Lynch iyo Paterson, warqad cilmi-baaris, 1985
- , Leslie Lamport, warqad cilmi baaris, 1998
- , Leslie Lamport, warqad cilmi baaris, 2001
Source: www.habr.com