Don haka, bari mu yi tunanin. Akwai karaye guda 5 da aka kulle a cikin dakin, kuma domin su tashi su tadda mai shi, dukkansu suna bukatar a amince da wannan a tsakaninsu, domin kawai za su iya bude kofar da biyar daga cikinsu sun jingina da ita. Idan daya daga cikin kuliyoyi shine cat Schrödinger, kuma sauran kuliyoyi ba su san game da shawararsa ba, tambayar ta taso: "Ta yaya za su yi?"
A cikin wannan labarin, zan gaya muku a cikin sauƙi game da ka'idodin ka'idar duniyar tsarin rarraba da ka'idodin aikin su. Zan kuma yi nazarin ainihin ra'ayin da ke ƙarƙashin Paxos.
Lokacin da masu haɓakawa ke amfani da abubuwan samar da girgije, bayanan bayanai daban-daban, kuma suna aiki a cikin gungu na ɗimbin nodes, suna da tabbacin cewa bayanan za su kasance cikakke, amintattu, kuma koyaushe suna samuwa. Amma ina garantin?
Ainihin, garantin da muke da shi shine garantin mai bayarwa. An kwatanta su a cikin takaddun kamar haka: "Wannan sabis ɗin yana da aminci sosai, yana da SLA da aka bayar, kada ku damu, komai zai yi aiki a rarraba kamar yadda kuke tsammani."
Mun yi imani da mafi kyau, saboda mutane masu hankali daga manyan kamfanoni sun tabbatar mana cewa komai zai yi kyau. Ba mu tambayi tambaya: me yasa, a gaskiya, wannan zai iya aiki kwata-kwata? Shin akwai wani dalili na gaskiya don daidaitaccen aiki na irin waɗannan tsarin?
Na tafi kwanan nan kuma wannan batu ya burge shi sosai. Laccoci a makaranta sun kasance kamar azuzuwan lissafi fiye da wani abu mai alaƙa da tsarin kwamfuta. Amma wannan shine ainihin yadda mafi mahimmancin algorithms da muke amfani da su a kowace rana, ba tare da sanin su ba, an tabbatar da su a lokaci guda.
Yawancin tsarin rarrabawar zamani suna amfani da Paxos consensus algorithm da gyare-gyare daban-daban. Mafi kyawun abu shine cewa inganci kuma, bisa ka'ida, ainihin yiwuwar wanzuwar wannan algorithm ana iya tabbatar da shi kawai tare da alkalami da takarda. A aikace, ana amfani da algorithm a cikin manyan tsarin da ke gudana akan adadi mai yawa na nodes a cikin gajimare.
Misali mai haske na abin da za a tattauna a gaba: aikin janar guda biyuBari mu duba don dumi-up .
Muna da runduna biyu - ja da fari. Dakarun farar fata na da sansani a birnin da aka yiwa kawanya. Sojojin jajayen karkashin jagorancin janar-janar A1 da A2 suna bangarorin biyu na birnin. Aikin masu jajayen jajayen shine su kai hari ga fararen fata su yi nasara. Duk da haka, sojojin kowane jajayen janar a daidaikunsu ba su kai na farar sojojin ba.
Sharuɗɗan nasara ga masu ja: dole ne duka janar ɗin su kai hari a lokaci guda don samun fa'ida ta lambobi akan fararen fata. Don yin wannan, janar-janar A1 da A2 suna buƙatar yin yarjejeniya da juna. Idan kowa ya kai hari daban, jajayen za su yi asara.
Don cimma yarjejeniya, janar-janar A1 da A2 na iya aika manzanni ga juna ta cikin yankin farar fata. Manzo na iya samun nasarar isa ga wani janar na kawance ko kuma abokan gaba su kama shi. Tambaya: Shin akwai irin wannan tsarin sadarwa tsakanin manyan jajayen jajayen (sauyin aika manzanni daga A1 zuwa A2 da akasin haka daga A2 zuwa A1), inda aka ba su tabbacin amincewa da harin da aka kai a sa’a X. Anan. garantin yana nufin cewa duka janar ɗin za su sami tabbataccen tabbaci cewa abokin tarayya (wani janar) tabbas zai kai hari a lokacin da aka ayyana X.
A ce A1 ya aika manzo zuwa A2 da saƙon: “Bari mu kai hari yau da tsakar dare!” Janar A1 ba zai iya kai hari ba tare da tabbatarwa daga Janar A2 ba. Idan manzo daga A1 ya zo, sai Janar A2 ya aika da tabbaci tare da saƙon: "Ee, bari mu kashe fata a yau." Amma a yanzu Janar A2 bai san ko manzonsa ya zo ba ko a'a, ba shi da tabbacin ko za a kai harin a lokaci guda. Yanzu Janar A2 kuma yana buƙatar tabbaci.
Idan muka ci gaba da bayyana hanyoyin sadarwarsu, za a fahimci cewa komai yawan zagayowar sakonnin da ake yi, babu yadda za a iya tabbatar da cewa dukkanin manyan hafsoshin biyu sun karbi sakwannin nasu (a zaton ko ko wanne manzo za a iya kama shi).
Matsalar Janar Biyu babban misali ne na tsarin rarrabawa mai sauƙi inda akwai kuɗaɗe biyu tare da sadarwa mara inganci. Wannan yana nufin ba mu da garantin 100% cewa an daidaita su. Irin waɗannan matsalolin ana tattauna su ne kawai akan sikelin mafi girma daga baya a cikin labarin.
Muna gabatar da manufar tsarin rarraba
Tsarin da aka rarraba shine rukuni na kwamfutoci (nan gaba za mu kira su nodes) waɗanda ke iya musayar saƙonni. Kowane kumburi ɗaya wani nau'in mahalli ne mai cin gashin kansa. Kumburi na iya aiwatar da ayyuka da kansa, amma don sadarwa tare da sauran nodes, yana buƙatar aikawa da karɓar saƙonni.
Yadda ake aiwatar da saƙonni daidai, waɗanne ka'idoji ake amfani da su - wannan ba ya da sha'awar mu a cikin wannan mahallin. Yana da mahimmanci cewa nodes na tsarin da aka rarraba zasu iya musayar bayanai tare da juna ta hanyar aika saƙonni.
Ma'anar kanta ba ta yi kama da rikitarwa ba, amma dole ne mu yi la'akari da cewa tsarin da aka rarraba yana da yawan halayen da za su kasance masu mahimmanci a gare mu.
Halayen tsarin rarrabawa
- Tabbatarwa - yuwuwar abubuwan da ke faruwa a lokaci ɗaya ko na lokaci ɗaya a cikin tsarin. Bugu da ƙari, za mu yi la'akari da abubuwan da ke faruwa a kan kusoshi biyu daban-daban da za su iya kasancewa tare da juna muddin ba mu da takamaiman tsari na faruwar waɗannan abubuwan. Amma, a matsayin mai mulkin, ba mu da shi.
- Babu agogon duniya. Ba mu da cikakken tsari na abubuwan da suka faru saboda rashin agogon duniya. A cikin duniyar yau da kullun na mutane, mun saba da gaskiyar cewa muna da agogo da lokaci kwata-kwata. Komai yana canzawa idan yazo da tsarin rarrabawa. Ko da madaidaicin agogon atomic sun yi nisa, kuma za a iya samun yanayi da ba za mu iya sanin wannen al'amura biyu ne suka fara faruwa ba. Saboda haka, mu ma ba za mu iya dogaro da lokaci ba.
- Rashin cin gashin kansa na nodes na tsarin. Akwai wata matsala kuma: wani abu na iya faruwa ba daidai ba saboda nodes ɗinmu ba su dawwama har abada. Hard ɗin na iya gazawa, injin kama-da-wane da ke cikin gajimare na iya sake yin aiki, hanyar sadarwar na iya ƙiftawa kuma saƙonni za su ɓace. Bugu da ƙari, ana iya samun yanayi inda nodes ke aiki, amma a lokaci guda suna aiki da tsarin. Ajin ƙarshe na matsalolin har ma sun sami suna daban: matsala . Mafi shahararren misali na tsarin da aka rarraba tare da wannan matsala shine Blockchain. Amma a yau ba za mu yi la'akari da wannan musamman ajin matsaloli. Za mu yi sha'awar yanayin da ɗaya ko fiye da nodes na iya gazawa.
- Samfuran sadarwa (samfurin saƙo) tsakanin nodes. Mun riga mun tabbatar da cewa nodes suna sadarwa ta hanyar musayar saƙonni. Akwai sanannun samfuran saƙo guda biyu: aiki tare da asynchronous.
Samfuran sadarwa tsakanin nodes a cikin tsarin rarrabawa
Samfurin aiki tare - mun san tabbas akwai iyakataccen sanannen lokaci wanda aka ba da tabbacin isar da saƙo daga wannan kumburi zuwa wancan. Idan wannan lokaci ya wuce kuma sakon bai isa ba, za mu iya cewa kullin ya gaza. A cikin wannan samfurin muna da lokutan jira masu iya tsinkaya.
Samfurin Asynchronous - a cikin asynchronous model mun yi la'akari da cewa jiran lokaci ne iyaka, amma babu irin wannan delta lokaci bayan da za mu iya tabbatar da cewa kumburi ya kasa. Wadancan. Lokacin jiran saƙo daga kumburi na iya zama tsayi ba bisa ka'ida ba. Wannan ma'ana ce mai mahimmanci, kuma za mu ƙara yin magana game da shi.
Manufar yarjejeniya a cikin tsarin rarrabawa
Kafin mu fayyace ma’anar ijma’i a zahiri, bari mu yi la’akari da misalin yanayin da muke buqata, wato – Kwafin Injin Jiha.
Muna da wani log ɗin da aka rarraba. Muna son ya kasance daidai kuma ya ƙunshi bayanai iri ɗaya akan duk nodes na tsarin da aka rarraba. Lokacin da ɗaya daga cikin nodes ya koyi sabon ƙima da zai rubuta zuwa log ɗin, aikinsa ya zama bayar da wannan ƙimar ga duk sauran nodes don sabunta log ɗin akan duk nodes kuma tsarin ya motsa zuwa sabon daidaitaccen yanayi. A wannan yanayin, yana da mahimmanci cewa nodes sun yarda da juna: duk nodes sun yarda cewa sabon ƙimar da aka tsara daidai ne, duk nodes sun yarda da wannan darajar, kuma kawai a cikin wannan yanayin kowa zai iya rubuta sabon darajar zuwa log.
A wasu kalmomi: babu ɗayan nodes ɗin da ya ƙi cewa yana da ƙarin bayanan da suka dace, kuma ƙimar da aka tsara ba daidai ba ne. Yarjejeniya tsakanin nodes da yarjejeniya akan ƙimar karɓa daidai guda ɗaya yarjejeniya ce a cikin tsarin da aka rarraba. Na gaba, za mu yi magana game da algorithms waɗanda ke ba da damar tsarin da aka rarraba don a ba da garanti don cimma yarjejeniya.
Ƙarin ƙa'ida, za mu iya ayyana algorithm yarjejeniya (ko kawai algorithm yarjejeniya) a matsayin wani aiki wanda ke canja wurin tsarin da aka rarraba daga jihar A zuwa jihar B. Bugu da ƙari, wannan jihar yana karɓar duk nodes, kuma duk nodes na iya tabbatar da shi. Kamar yadda ya bayyana, wannan aikin ba shi da mahimmanci kamar yadda ake gani a farkon kallo.
Abubuwan Algorithm na Ijma'i
Algorithm na yarjejeniya dole ne ya sami kaddarori guda uku domin tsarin ya ci gaba da wanzuwa kuma ya sami ɗan ci gaba a ƙaura daga jiha zuwa jiha:
- Yarjejeniyar - duk nodes masu aiki daidai dole ne su ɗauki ƙima ɗaya (a cikin labaran kuma ana kiran wannan kadarar azaman kayan tsaro). Duk nodes ɗin da ke aiki a halin yanzu (ba su gaza ko rasa hulɗa da sauran ba) dole ne su zo kan yarjejeniya kuma su karɓi ƙimar gama gari ta ƙarshe.
Yana da mahimmanci a fahimci a nan cewa nodes a cikin tsarin rarraba da muke la'akari suna son yarda. Wato yanzu muna magana ne game da tsarin da wani abu zai iya yin kasawa kawai (misali, wasu kundila sun kasa), amma a cikin wannan tsarin babu shakka babu nodes da suka yi aiki da wasu da gangan (aikin manyan sojojin Byzantine). Saboda wannan kadara, tsarin ya kasance mai daidaituwa.
- mutunci - idan duk nodes masu aiki daidai suna ba da ƙimar iri ɗaya v, wanda ke nufin kowane kumburi aiki daidai dole ne ya karɓi wannan ƙimar v.
- ƙarshe - duk nodes masu aiki daidai za su ɗauki wani ƙima (dukiyar rayuwa), wanda ke ba da damar algorithm don samun ci gaba a cikin tsarin. Kowane mutum da kullin aiki daidai dole ne ba dade ko ba dade ya karɓi ƙimar ƙarshe kuma ya tabbatar da ita: "A gare ni, wannan ƙimar gaskiya ce, Na yarda da tsarin gaba ɗaya."
Misali na yadda algorithm yarjejeniya ke aiki
Duk da yake kaddarorin algorithm na iya zama ba su bayyana gaba ɗaya ba. Saboda haka, za mu misalta da wani misali abin da matakai mafi sauki yarjejeniya algorithm ke tafiya a cikin wani tsarin da synchronous saƙon model, a cikin abin da duk nodes aiki kamar yadda aka sa ran, saƙonni ba a rasa kuma babu abin karya (shin da gaske wannan ya faru?).
- Duk yana farawa da neman aure (Propose). Bari mu ɗauka cewa abokin ciniki ya haɗa da kumburi da ake kira "Node 1" kuma ya fara ciniki, yana ƙaddamar da sabon darajar zuwa kumburi - O. Daga yanzu, za mu kira "Node 1" don ba da shawara. A matsayin mai ba da shawara, "Node 1" dole ne a yanzu sanar da dukkan tsarin cewa yana da sabbin bayanai, kuma yana aika saƙonni zuwa duk sauran nodes: "Duba! Ma'anar "O" ta zo gare ni kuma ina so in rubuta shi! Da fatan za a tabbatar da cewa za ku kuma yi rikodin "O" a cikin log ɗin ku.
- Mataki na gaba shine zaɓen ƙimar da aka tsara (Voting). Menene don me? Yana iya faruwa cewa wasu nodes sun sami ƙarin bayanan kwanan nan, kuma suna da bayanai akan ma'amala ɗaya.
Lokacin da kumburi "Node 1" ya aika da shawararsa, sauran nodes suna duba rajistan ayyukan su don bayanai akan wannan taron. Idan babu sabani, nodes suna sanar da: "Ee, ba ni da wani bayanan wannan taron. Ƙimar "O" ita ce sabuwar bayanin da muka cancanci."A kowane hali, nodes na iya amsawa zuwa "Node 1": "Saurara! Ina da ƙarin bayanan kwanan nan akan wannan ma'amala. Ba 'O' ba, amma wani abu mafi kyau."
A matakin jefa kuri'a, nodes suna zuwa yanke shawara: ko dai duk sun yarda da ƙimar ɗaya, ko ɗayansu ya ƙi, yana nuna cewa yana da ƙarin bayanan kwanan nan.
- Idan zagayen zaɓen ya yi nasara kuma kowa ya yarda, to tsarin ya motsa zuwa wani sabon mataki - karɓar darajar (Karɓa). "Node 1" yana tattara duk martani daga wasu nodes da rahotanni: "Kowa ya amince da darajar "O"! Yanzu na ayyana a hukumance cewa “O” sabuwar ma’anarmu ce, iri ɗaya ce ga kowa! Rubuta shi a cikin ƙaramin littafinku, kar ku manta. Rubuta shi a cikin log ɗinku!”
- Sauran nodes suna aika tabbatarwa (An karɓa) cewa sun rubuta ƙimar "O"; babu wani sabon abu da ya zo a wannan lokacin (wani nau'i na nau'i biyu). Bayan wannan muhimmin taron, muna la'akari da cewa ma'amalar da aka rarraba ta ƙare.
Don haka, algorithm yarjejeniya a cikin yanayi mai sauƙi ya ƙunshi matakai guda huɗu: ba da shawara, jefa kuri'a (zaɓe), karɓa (karɓa), tabbatar da karɓa (karɓa).
Idan a wani mataki ba mu sami damar cimma yarjejeniya ba, to algorithm yana sake farawa, la'akari da bayanan da nodes suka bayar waɗanda suka ƙi tabbatar da ƙimar da aka tsara.
Algorithm na yarjejeniya a cikin tsarin asynchronous
Kafin wannan, komai ya kasance santsi, saboda muna magana ne game da ƙirar saƙon aiki tare. Amma mun san cewa a wannan zamani mun saba yin komai ba tare da an daidaita shi ba. Ta yaya irin wannan algorithm ke aiki a cikin tsarin tare da samfurin saƙon asynchronous, inda muka yi imani cewa lokacin jira don amsawa daga kumburi na iya zama tsayi ba bisa ƙa'ida ba (ta hanyar, gazawar kumburi kuma ana iya la'akari da shi azaman misali lokacin da aka yi la'akari da gazawar kumburi. kumburi na iya amsawa na dogon lokaci ba bisa ka'ida ba).
Yanzu da muka san yadda algorithm yarjejeniya ke aiki bisa ka'ida, tambaya ga waɗanda masu karatu masu bincike waɗanda suka yi hakan zuwa yanzu: nodes nawa a cikin tsarin nodes na N tare da ƙirar saƙon asynchronous na iya kasawa don har yanzu tsarin zai iya cimma yarjejeniya?
Amsa daidai da hujja suna bayan mai ɓarna.Amsa daidai: 0. Idan koda kumburi ɗaya a cikin tsarin asynchronous ya gaza, tsarin ba zai iya cimma yarjejeniya ba. An tabbatar da wannan bayanin a cikin ka'idar FLP, sananne a cikin wasu da'irori (1985, Fischer, Lynch, Paterson, haɗi zuwa asali a ƙarshen labarin): "Rashin yiwuwar cimma yarjejeniya da aka rarraba idan aƙalla kumburi ɗaya ya gaza. .”
Jama'a, to muna da matsala, mun saba da duk abin da yake asynchronous. Kuma ga shi. Yadda za a ci gaba da rayuwa?
Muna magana ne kan ka'ida, game da lissafi. Menene ma'anar "ba za a iya cimma yarjejeniya ba", fassara daga harshen lissafi zuwa namu - injiniyanci? Wannan yana nufin cewa "ba za a iya cimma ko da yaushe", watau. Akwai yanayin da ba za a iya cimma yarjejeniya ba. Wannan wace irin harka ce?
Wannan shi ne ainihin cin zarafin dukiyar rayuwa da aka kwatanta a sama. Ba mu da yarjejeniya guda ɗaya, kuma tsarin ba zai iya samun ci gaba ba (ba zai iya kammalawa a cikin ƙayyadadden lokaci ba) a cikin yanayin da ba mu da amsa daga duk nodes. Domin a cikin tsarin asynchronous ba mu da lokacin amsawa mai iya tsinkaya kuma ba za mu iya sanin ko kumburin ya fado ko yana ɗaukar lokaci mai tsawo don amsawa ba.
Amma a aikace muna iya samun mafita. Bari mu algorithm iya aiki na dogon lokaci idan akwai kasawa (yiwuwar zai iya aiki har abada). Amma a mafi yawan yanayi, lokacin da yawancin nodes ke aiki daidai, za mu sami ci gaba a cikin tsarin.
A aikace, muna mu'amala da nau'ikan sadarwar da ke aiki tare. Ana fahimtar sashe na haɗin gwiwa kamar haka: a cikin yanayin gabaɗaya, muna da ƙirar asynchronous, amma an gabatar da takamaiman manufar “lokacin daidaitawar duniya” na wani lokaci a kan lokaci.
Wannan lokacin a cikin lokaci bazai zo na kowane tsawon lokaci ba, amma dole ne ya zo wata rana. Agogon ƙararrawa na kama-da-wane zai yi ringi, kuma daga wannan lokacin muna iya hasashen lokacin da saƙon zai zo. Daga wannan lokacin, tsarin yana juyawa daga asynchronous zuwa aiki tare. A aikace, muna magance daidai irin waɗannan tsarin.
Algorithm na Paxos yana warware matsalolin yarjejeniya
Iyali ne na algorithms waɗanda ke magance matsalar yarjejeniya don tsarin aiki tare da ɗan lokaci, bisa yuwuwar wasu nodes na iya gazawa. Marubucin Paxos shine . Ya ba da shawara na yau da kullun na wanzuwa da daidaiton algorithm a cikin 1989.
Amma hujjar ta zama mai nisa daga ƙaramin abu. An fito da bugu na farko a cikin 1998 (shafukan 33) wanda ke kwatanta algorithm. Kamar yadda ya fito, yana da wuyar fahimta sosai, kuma a shekara ta 2001 an buga bayanin labarin, wanda ya ɗauki shafuka 14. An ba da ƙarar wallafe-wallafen don nuna cewa a gaskiya matsalar haɗin kai ba ta da sauƙi, kuma a bayan irin waɗannan algorithms yana da babban adadin aiki ta hanyar mutane mafi wayo.
Yana da ban sha'awa cewa Leslie Lamport da kansa ya lura a cikin karatunsa cewa a cikin kasida ta biyu na bayani akwai magana ɗaya, layi ɗaya (bai bayyana wanne ba), wanda za'a iya fassara ta hanyoyi daban-daban. Kuma saboda wannan, babban adadin aiwatar da Paxos na zamani ba sa aiki daidai.
Cikakken bincike na aikin Paxos zai ɗauki labarin fiye da ɗaya, don haka zan yi ƙoƙarin isar da babban ra'ayin a taƙaice. A cikin hanyoyin haɗin gwiwa a ƙarshen labarina za ku sami kayan da za a ci gaba da nutsewa cikin wannan batu.
Matsayi a Paxos
Algorithm na Paxos yana da ra'ayi na matsayin. Bari mu yi la'akari da manyan guda uku (akwai gyare-gyare tare da ƙarin ayyuka):
- Masu ba da shawara (ana kuma iya amfani da kalmomin: shugabanni ko masu gudanarwa). Waɗannan su ne mutanen da suka koyi game da wasu sababbin ƙima daga mai amfani kuma suka ɗauki matsayin jagora. Ayyukan su shine ƙaddamar da zagaye na shawarwari don sabon ƙima da daidaita ƙarin ayyuka na nodes. Bugu da ƙari, Paxos yana ba da damar kasancewar shugabanni da yawa a wasu yanayi.
- Masu karɓa (Masu jefa ƙuri'a). Waɗannan kuɗaɗe ne waɗanda ke jefa ƙuri'a don karɓa ko ƙi ƙima ta musamman. Matsayin su yana da mahimmanci, saboda yanke shawara ya dogara da su: menene tsarin tsarin zai (ko ba zai) zuwa bayan mataki na gaba na algorithm yarjejeniya.
- Masu koyo. Nodes waɗanda kawai ke karɓa da rubuta sabuwar ƙimar karɓa lokacin da yanayin tsarin ya canza. Ba sa yanke shawara, kawai suna karɓar bayanan kuma suna iya ba da shi ga mai amfani na ƙarshe.
Kumburi ɗaya na iya haɗa ayyuka da yawa a yanayi daban-daban.
Ma'anar qurum
Muna ɗauka cewa muna da tsarin N nodes Kuma daga cikinsu mafi girma F nodes na iya kasawa. Idan F nodes sun kasa, to dole ne mu sami aƙalla 2F+1 nodes masu karɓa.
Wannan ya zama dole domin koyaushe muna da rinjaye, ko da a cikin mafi munin yanayi, na nodes "mai kyau" waɗanda ke aiki daidai. Wato F+1 "mai kyau" nodes waɗanda suka yarda, kuma za a karɓi ƙimar ƙarshe. In ba haka ba, za a iya samun wani yanayi da ƙungiyoyin gida daban-daban suka ɗauki ma'anoni daban-daban kuma ba za su iya yarda da juna ba. Don haka, muna buƙatar cikakken rinjaye don samun nasarar jefa ƙuri'a.
Babban ra'ayin yadda Paxos yarjejeniya algorithm ke aiki
Algorithm na Paxos ya ƙunshi manyan matakai guda biyu, waɗanda kuma aka raba su zuwa matakai biyu kowanne:
- Mataki na 1a: Shirya. A lokacin shirye-shiryen, jagora (mai ba da shawara) ya sanar da duk nodes: "Muna fara sabon tsarin jefa kuri'a. Muna da sabon zagaye. Adadin wannan zagayen shine n. Yanzu za mu fara kada kuri'a." A yanzu, kawai yana ba da rahoton farkon sabon zagayowar, amma baya bayar da rahoton sabon ƙima. Aikin wannan mataki shine fara sabon zagaye da sanar da kowa lambar sa na musamman. Lambar zagaye yana da mahimmanci, dole ne ya zama darajar da ta fi duk lambobin zaɓe da suka gabata daga duk shugabannin da suka gabata. Domin godiya ga lambar zagaye cewa sauran nodes a cikin tsarin zasu fahimci yadda kwanan nan bayanan jagoran yake. Da alama sauran kujerun sun riga sun sami sakamakon jefa ƙuri'a daga zagaye na gaba kuma za su gaya wa shugaban cewa yana bayan lokutan.
- Mataki na 1b: Alkawari. Lokacin da nodes masu karɓa suka karɓi adadin sabon matakin jefa ƙuri'a, sakamako biyu yana yiwuwa:
- Lambar n na sabon ƙuri'ar ya fi yawan kowace ƙuri'ar da ta gabata wadda mai karɓa ya shiga. Sannan mai karba ya aika wa shugaba alkawari cewa ba za ta kara shiga cikin kuri'u da lamba kasa da n. Idan mai karba ya riga ya zave wani abu (wato ya riga ya karɓi wasu ƙima a cikin kashi na biyu), to sai ya jingina ƙimar karɓa da adadin ƙuri'ar da ya shiga cikin wa'adinsa.
- In ba haka ba, idan mai karɓa ya rigaya ya san game da mafi girman kuri'a, zai iya yin watsi da matakin shirye-shiryen kawai kuma ba ya amsa wa jagora.
- Mataki na 2a: Karɓa. Jagora yana buƙatar jiran amsa daga ƙungiyar ƙididdiga (mafi yawan nodes a cikin tsarin) kuma, idan an karɓi adadin da ake buƙata na martani, to yana da zaɓi biyu don haɓaka abubuwan da suka faru:
- Wasu daga cikin masu karɓar sun aika da ƙima waɗanda suka rigaya suka zaɓa. A wannan yanayin, jagora yana zaɓar ƙimar daga ƙuri'a tare da matsakaicin lamba. Bari mu kira wannan darajar x, kuma tana aika da sako zuwa ga dukkan nodes kamar: "Karɓi (n, x)", inda darajar farko ita ce lambar zaɓe daga mataki na Propose, na biyu kuma shine abin da kowa ya tattara. i.e darajar da a zahiri muke zabe.
- Idan babu daya daga cikin masu karban da ya aiko da wata kima, amma kawai ya yi alkawarin kada kuri'a a wannan zagaye, shugaba na iya gayyatar su don kada kuri'ar kimarsa, darajar da ya zama jagora a farko. Mu kira shi y. Yana aika saƙo zuwa ga duk nodes kamar: "Karɓa (n, y)", kama da sakamakon baya.
- Mataki na 2b: An karɓa. Bugu da ari, masu karɓa na karɓa, bayan karɓar saƙon "Karɓa (...)" daga jagorar, sun yarda da shi (aika da tabbaci ga duk nodes cewa sun yarda da sabon darajar) kawai idan ba su yi alkawarin wasu (wasu) ba). shugaba don shiga zabe tare da zagaye lamba ba > n, in ba haka ba sun yi watsi da buƙatar tabbatarwa.
Idan yawancin nodes sun amsa wa jagora, kuma dukansu sun tabbatar da sabon darajar, to ana ɗaukar sabon darajar. Hooray! Idan yawancin ba a kai ba ko kuma akwai nodes waɗanda suka ƙi karɓar sabon ƙimar, to komai yana farawa.
Wannan shine yadda Paxos algorithm ke aiki. Kowane ɗayan waɗannan matakan yana da dabaru da yawa, a zahiri ba mu yi la'akari da nau'ikan gazawa daban-daban ba, matsalolin shugabannin da yawa da ƙari mai yawa, amma manufar wannan labarin shine kawai don gabatar da mai karatu ga duniyar ƙididdigar rarrabawa a babban matakin.
Har ila yau, ya kamata a lura cewa Paxos ba shine kawai nau'insa ba, akwai wasu algorithms, misali, , amma wannan batu ne don wani labarin.
Hanyoyin haɗi zuwa kayan aiki don ƙarin nazari
Matakin farko:
- , Preethi Kasireddy, labarin blog akan Matsakaici
- , Adi Kancherla, labarin blog akan Matsakaici
- , Itai Ibrahim, blog
- , Itai Ibrahim, labarin blog
Leslie Lamport matakin:
- , Fischer, Lynch da Paterson, takarda bincike, 1985
- , Leslie Lamport, takarda bincike, 1998
- , Leslie Lamport, takarda bincike, 2001
source: www.habr.com