Ya mere, ka anyị were ya. Enwere nwamba 5 akpọchiri n'ime ụlọ ahụ, ma ka ha wee kpọte onye nwe ya, ha niile kwesịrị ikwekọrịta na nke a n'etiti onwe ha, n'ihi na ha nwere ike imeghe ọnụ ụzọ na ise n'ime ha dabere na ya. Ọ bụrụ na otu nwamba ahụ bụ pusi Schrödinger, ma nwamba ndị ọzọ amaghị banyere mkpebi ya, ajụjụ na-ebilite: "Olee otú ha ga-esi mee ya?"
N'isiokwu a, m ga-agwa gị n'ụzọ dị mfe banyere akụkụ usoro ihe omimi nke ụwa nke usoro nkesa na ụkpụrụ nke ọrụ ha. M ga-enyochakwa isi echiche nke dị n'okpuru Paxos.
Mgbe ndị mmepe na-eji akụrụngwa igwe ojii, ọdụ data dị iche iche, ma na-arụ ọrụ na ụyọkọ nke ọnụ ọgụgụ buru ibu, ha na-enwe obi ike na data ahụ ga-ezu oke, nchekwa, na mgbe niile. Ma olee ebe nkwa ndị ahụ dị?
N'ezie, nkwa anyị nwere bụ nkwa ndị na-ebubata ihe. A kọwara ha n'akwụkwọ ahụ dị ka ndị a: "Ọrụ a bụ ihe a pụrụ ịdabere na ya, o nwere SLA, echegbula, ihe niile ga-arụ ọrụ na-ekesa dịka ị tụrụ anya."
Anyị na-ekwenyekarị na ihe kacha mma, n'ihi na ndị nwere ọgụgụ isi sitere na nnukwu ụlọ ọrụ mesiri anyị obi ike na ihe niile ga-adị mma. Anyị anaghị ajụ ajụjụ a: gịnị kpatara, n'ezie, nke a nwere ike ịrụ ọrụ ma ọlị? Ọ nwere ihe ezi uche dị na ya maka ịrụ ọrụ nke ọma nke sistemu ndị dị otú ahụ?
M gara nso nso a isiokwu a nwekwara mmụọ nsọ nke ukwuu. Nkuzi nkuzi n'ụlọ akwụkwọ dị ka klaasị karịa ihe metụtara usoro kọmputa. Ma nke a bụ kpọmkwem otu algọridim kachasị mkpa nke anyị na-eji kwa ụbọchị, n'amaghịdị ya, gosipụtara n'otu oge.
Ọtụtụ sistemụ kesara ọgbara ọhụrụ na-eji Paxos consensus algọridim na mgbanwe ya dị iche iche. Ihe kacha mma bụ na ịdị irè na, n'ụkpụrụ, enwere ike igosipụta ịdị adị nke algọridim a naanị site na mkpịsị akwụkwọ na akwụkwọ. Na omume, a na-eji algọridim na nnukwu usoro na-agba ọsọ na ọnụ ọgụgụ dị ukwuu nke ọnụ na ígwé ojii.
Ihe atụ dị mfe nke ihe a ga-atụle na-esote: ọrụ nke ndị ọchịagha abụọKa anyị lee anya maka ikpo ọkụ .
Anyị nwere ndị agha abụọ - uhie na ọcha. Ndị agha ọcha nọ n'obodo ahụ a nọchibidoro. Ndị agha uhie nke ndị ọchịagha A1 na A2 nọ n'akụkụ abụọ nke obodo ahụ. Ọrụ ndị redheads bụ ịwakpo obodo ọcha wee merie. Otú ọ dị, ndị agha nke onye ọ bụla na-acha uhie uhie n'ozuzu n'otu n'otu dị obere karịa ndị agha ọcha.
Ọnọdụ mmeri maka ndị na-acha uhie uhie: ndị isi abụọ ahụ aghaghị ịwakpo n'otu oge ka ha wee nwee uru ọnụọgụ karịa ndị ọcha. Iji mee nke a, ọ dị mkpa ka ndị isi A1 na A2 kwekọrịtara na ibe ha. Ọ bụrụ na onye ọ bụla na-awakpo iche iche, redheads ga-efunahụ.
Iji nweta nkwekọrịta, ndị isi A1 na A2 nwere ike iziga ndị ozi na ibe ha site na mpaghara obodo ọcha. Onye ozi ahụ nwere ike ịgakwuru ndị ọchịagha jikọrọ aka ma ọ bụ nwee ike ijide ya n'aka ndị iro. Ajụjụ: enwere usoro nkwukọrịta dị otú ahụ n'etiti ndị isi ndị isi na-acha uhie uhie (usoro nke izipu ndị ozi site na A1 ruo A2 na nke ọzọ site na A2 ruo A1), nke ekwere na ha ga-ekwenye na mbuso agha na elekere X. Ebe a, Nkwenye pụtara na ndị isi abụọ ahụ ga-enwe nkwenye doro anya na ndị mmekọ (ọha ọzọ) ga-alụ ọgụ n'oge a kara aka X.
Ka e were ya na A1 zigara onye ozi na A2 ozi: “Ka anyị wakpoo taa n’etiti abalị!” General A1 enweghị ike ịwakpo na-enweghị nkwenye sitere na General A2. Ọ bụrụ na onye ozi sitere na A1 bịarutere, General A2 na-eziga nkwenye na ozi ahụ: "Ee, ka anyị gbuo ndị ọcha taa." Mana ugbu a General A2 amaghị ma onye ozi ya abatala ma ọ bụ na ọ bụghị, ọ nweghị nkwa ma ọgụ ahụ ga-abụ n'otu oge. Ugbu a General A2 chọrọ nkwenye ọzọ.
N'ịkọwa nzikọrịta ozi ha gara n'ihu na-ekpughe ihe ndị a: n'agbanyeghị usoro okirikiri ozi dị, ọ nweghị ụzọ a ga-esi kwenye na e meela ka ndị isi abụọ ahụ mara na enwetala ozi ha (na-eche na enwere ike igbochi onye ozi ọ bụla).
Nsogbu Generals abụọ bụ nnukwu ihe atụ nke usoro kesara dị mfe ebe enwere ọnụ ụzọ abụọ nwere nkwurịta okwu na-enweghị ntụkwasị obi. Nke a pụtara na anyị enweghị nkwa 100% na emekọrịtara ha. A na-atụle nsogbu ndị yiri ya naanị n'ọ̀tụ̀tụ̀ buru ibu ma emechaa n'isiokwu ahụ.
Anyị na-ewebata echiche nke usoro kesara
Usoro kesara bụ otu kọmputa (nke a ga-akpọ ha ọnụ) nke nwere ike ịgbanwe ozi. Ọnụ onye ọ bụla bụ ụdị ụlọ ọrụ kwụụrụ onwe ya. Otu ọnụ nwere ike hazie ọrụ n'onwe ya, mana ka ọ na-ekwurịta okwu na ọnụ ndị ọzọ, ọ kwesịrị izipu ma nata ozi.
Otu esi emejuputa ozi kpọmkwem, kedu usoro a na-eji - nke a adịghị amasị anyị na nke a. Ọ dị mkpa na ọnụ nke usoro kesara nwere ike ịgbanwe data na ibe ya site na izipu ozi.
Nkọwa n'onwe ya adịghị ka mgbagwoju anya, ma anyị ga-eburu n'uche na usoro nkesa nwere ọtụtụ àgwà ndị ga-abara anyị uru.
Àgwà nke sistemu ekesa
- Mmechi - ohere nke ime n'otu oge ma ọ bụ ihe na-eme n'otu oge na-eme na usoro. Ọzọkwa, anyị ga-atụle ihe omume ndị na-eme n'ọnụ ụzọ abụọ dị iche iche nwere ike ịdị n'otu oge ma ọ bụrụhaala na anyị enweghị usoro doro anya nke ihe omume ndị a. Ma, dịka iwu, anyị enweghị ya.
- Enweghị elekere zuru ụwa ọnụ. Anyị enweghị usoro doro anya nke ihe omume n'ihi enweghị elekere zuru ụwa ọnụ. Na ụwa nkịtị nke ndị mmadụ, anyị na-agba nkịtị na eziokwu na anyị nwere clocks na oge kpamkpam. Ihe niile na-agbanwe ma a bịa na sistemụ kesara. Ọbụna elekere atọm nke dabara nke ọma na-akpagharị, a pụkwara inwe ọnọdụ ndị anyị na-apụghị ịkọ nke mbụ n'ime ihe abụọ merenụ. Ya mere, anyị enweghị ike ịdabere na oge.
- Ọdịda nke onwe nke ọnụ sistemu. Enwere nsogbu ọzọ: ihe nwere ike ịgahie naanị n'ihi na ọnụ anyị anaghị adịru mgbe ebighị ebi. Mbanye ike nwere ike ịda, igwe mebere na igwe ojii nwere ike ịmalitegharị, netwọk nwere ike ịnya isi na ozi ga-efunahụ ya. Ọzọkwa, enwere ike ịnwe ọnọdụ ebe ọnụ na-arụ ọrụ, ma n'otu oge ahụ na-arụ ọrụ megide usoro ahụ. Klas ikpeazụ nke nsogbu ọbụna natara aha dị iche: nsogbu . Ihe atụ kachasị ewu ewu nke sistemụ kesara nwere nsogbu a bụ Blockchain. Ma taa, anyị agaghị atụle ụdị nsogbu a pụrụ iche. Anyị ga-enwe mmasị n'ọnọdụ ebe nanị otu ọnụ ma ọ bụ karịa nwere ike ịda.
- Ụdị nzikọrịta ozi (ụdị izi ozi) n'etiti ọnụ. Anyị emebelarị na ọnụ ọnụ na-akpakọrịta site n'ịgbanwe ozi. Enwere ụdị izi ozi abụọ ama ama: synchronous na asynchronous.
Ụdị nkwurịta okwu n'etiti ọnụ na sistemụ kesara
Ụdị mmekọrịta - anyị maara n'ezie na e nwere njedebe mara delta nke oge nke ozi na-ekwe nkwa na ọ ga-esi n'otu ọnụ gaa na nke ọzọ. Ọ bụrụ na oge a agafeela ma ozi ahụ eruteghị, anyị nwere ike ikwu n'enweghị nsogbu na ọnụ ahụ adaala. N'ihe nlereanya a, anyị nwere oge nchere nke a na-atụghị anya ya.
Ihe nlereanya asynchronous - na ụdị asynchronous anyị na-atụle na oge nchere bụ njedebe, ma ọ dịghị ụdị delta nke oge mgbe nke ahụ gasịrị anyị nwere ike ikwe nkwa na ọnụ ahụ adawo. Ndị ahụ. Oge nchere maka ozi sitere na ọnụ nwere ike ịdị ogologo aka ike. Nke a bụ nkọwa dị mkpa, anyị ga-ekwukwa banyere ya ọzọ.
Echiche nke nkwenye na usoro kesara
Tupu anyị akọwapụta echiche nke nkwekọrịta, ka anyị tụlee ihe atụ nke ọnọdụ ebe anyị chọrọ ya, ya bụ - Ntugharị igwe steeti.
Anyị nwere ụfọdụ log na-ekesa. Anyị ga-achọ ka ọ na-agbanwe agbanwe ma nwee data yiri ya na ọnụ niile nke sistemu ekesa. Mgbe otu n'ime ọnụ ụzọ ahụ mụtara uru ọhụrụ ọ ga-ede na ndekọ ahụ, ọrụ ya na-aghọ ịnye uru a na ọnụ ọgụgụ ndị ọzọ niile ka e wee na-emelite log ahụ na oghere niile na usoro ahụ na-aga na ọnọdụ ọhụrụ na-agbanwe agbanwe. N'okwu a, ọ dị mkpa ka ọnụ ọgụgụ ahụ kwekọrịta n'etiti onwe ha: ọnụ ọgụgụ niile na-ekweta na uru ọhụrụ a chọrọ bụ nke ziri ezi, ọnụ ọgụgụ niile na-anabata uru a, na naanị na nke a onye ọ bụla nwere ike dee uru ọhụrụ na log.
N'ikwu ya n'ụzọ ọzọ: ọ dịghị nke ọ bụla n'ime oghere ahụ jụrụ na o nwere ozi ndị ọzọ dị mkpa, na uru a tụrụ aro ezighi ezi. Nkwekọrịta n'etiti ọnụ na nkwekọrịta na otu uru anabatara nke ọma bụ nkwenye n'ime usoro ekesa. Ọzọ, anyị ga-ekwu maka algọridim nke na-ekwe ka usoro nkesa na-ekwe nkwa iji nweta nkwenye.
N'ụzọ doro anya, anyị nwere ike ịkọwapụta algorithm nkwenye (ma ọ bụ nanị nkwekọrịta nkwekọrịta) dị ka ọrụ ụfọdụ nke na-enyefe usoro nkesa site na steeti A ruo na steeti B. Ọzọkwa, a na-anabata steeti a site na ọnụ ọgụgụ niile, na ọnụ niile nwere ike kwado ya. Dị ka ọ na-apụta, ọrụ a abụghị ihe dị ntakịrị ka ọ dị na nlele mbụ.
Njirimara Algorithm Consensus
Algọridim nkwekọrịta nkwekọrịta ga-enwerịrị ihe atọ ka sistemụ ahụ wee dịgide ma nwee ọganihu na ịkwaga site na steeti gaa na steeti:
- Nkwekọrịta - ọnụ ụzọ niile na-arụ ọrụ nke ọma ga-enwerịrị otu uru (n'isiokwu a na-akpọkwa ihe onwunwe a dị ka ihe nchekwa). Ọnụ niile na-arụ ọrụ ugbu a (anaghị ada ma ọ bụ furu efu na kọntaktị na ndị ọzọ) ga-abịarịrị na nkwekọrịta wee nabata ụfọdụ uru nkịtị.
Ọ dị mkpa ịghọta ebe a na ọnụ ọgụgụ dị na usoro nkesa anyị na-atụle chọrọ ikwenye. Nke ahụ bụ, anyị na-ekwu ugbu a banyere usoro nke ihe nwere ike ịda ada (dịka ọmụmaatụ, ụfọdụ ọnụ na-ada), ma na usoro a, ọ dịghị ọnụ na-ama ụma na-arụ ọrụ megide ndị ọzọ (ọrụ nke Byzantine general). N'ihi ihe onwunwe a, usoro ahụ na-anọgide na-agbanwe agbanwe.
- Ike n'Ezi - ọ bụrụ na ọnụ ụzọ niile na-arụ ọrụ nke ọma na-enye otu uru v, nke pụtara ọnụ ụzọ ọ bụla na-arụ ọrụ nke ọma ga-anabata uru a v.
- Nkwụsị - ọnụ ụzọ niile na-arụ ọrụ nke ọma ga-emecha nweta uru ụfọdụ (ihe onwunwe ndụ), nke na-enye ohere ka algọridim nwee ọganihu na usoro. Onye ọ bụla na-arụ ọrụ n'ụzọ ziri ezi ga-emesịa ma ọ bụ emechaa nabata uru ikpeazụ wee kwado ya: "Nye m, uru a bụ eziokwu, ekwenyere m na usoro dum."
Ihe atụ nke otu nkwekọrịta nkwekọrịta algorithm si arụ ọrụ
Ọ bụ ezie na njirimara nke algọridim nwere ike ọ gaghị adịcha mma. Ya mere, anyị ga-eji ihe atụ mee ihe nkebi ndị kasị mfe nkwenye algọridim na-aga site na a usoro na synchronous ozi nlereanya, nke niile ọnụ na-arụ ọrụ dị ka a tụrụ anya, ozi na-adịghị efu na ọ dịghị ihe na-agbaji (nke a ọ na-eme n'ezie?).
- Ihe niile na-amalite na atụmatụ alụmdi na nwunye (Propose). Ka anyị chee na onye ahịa jikọtara ọnụ nke a na-akpọ "Node 1" wee malite azụmahịa, na-agafe uru ọhụrụ na ọnụ ọnụ - O. Site ugbu a gaa n'ihu, anyị ga-akpọ "Node 1" ịtụ aro. Dị ka onye na-atụ aro, "Node 1" ga-agwa sistemụ ahụ niile na o nwere data ọhụrụ, ma ọ na-eziga ozi na ọnụ ndị ọzọ niile: "Lee! Ihe pụtara "O" bịakwutere m ma achọrọ m ide ya! Biko gosi na ị ga-edekọkwa "O" na ndekọ gị.
- Oge na-esote bụ ịtụ vootu maka uru achọrọ (Voting). Kedu ihe ọ bụ? Ọ nwere ike ime na ọnụ ụzọ ndị ọzọ anatawo ozi na nso nso a, ma ha nwere data na otu azụmahịa ahụ.
Mgbe ọnụ "Node 1" na-eziga atụmatụ ya, ọnụ ụzọ ndị ọzọ na-elele ndekọ ha maka data na mmemme a. Ọ bụrụ na enweghị esemokwu, ọnụ ụzọ na-ekwupụta: “Ee, enweghị m data ọzọ maka mmemme a. Uru "O" bụ ozi kachasị ọhụrụ anyị kwesịrị."N'ọnọdụ ọ bụla ọzọ, ọnụ nwere ike ịzaghachi na "Node 1": "Ntị! Enwere m data ọhụrụ na azụmahịa a. Ọ bụghị 'O', mana ihe ka mma."
N'oge ntuli aka, ọnụ na-abịa na mkpebi: ma ha niile na-anabata otu uru, ma ọ bụ otu n'ime ha na-emegide, na-egosi na o nwere data na-adịbeghị anya.
- Ọ bụrụ na ntuli aka ntuli aka ahụ gara nke ọma na onye ọ bụla na-akwado ya, mgbe ahụ, usoro ahụ na-aga na ọkwa ọhụrụ - ịnakwere uru (Nabata). "Node 1" na-anakọta nzaghachi niile site na ọnụ ụzọ ndị ọzọ na akụkọ: "Onye ọ bụla kwetara na uru "O"! Ugbu a, m na-ekwupụta n'ihu ọha na "O" bụ ihe ọhụrụ anyị pụtara, otu maka onye ọ bụla! Dee ya na obere akwụkwọ gị, echefula. Dee ya n'akwụkwọ ndekọ aha gị!"
- Ọnụ ụzọ ndị fọdụrụ na-eziga nkwenye (Nabata) na ha edewo uru "O"; ọ dịghị ihe ọhụrụ bịarutere n'oge a (ụdị ntinye nke abụọ). Mgbe ihe omume a dị ịrịba ama, anyị na-atụle na azụmahịa nke kesara agwụla.
Ya mere, nkwekọrịta nkwekọrịta n'okwu dị mfe nwere usoro anọ: atụpụta, votu (votu), ịnakwere (nabata), kwadoro nnabata (anabatara).
Ọ bụrụ na n'oge ụfọdụ anyị enweghị ike ịmekọrịta nkwekọrịta, mgbe ahụ, algọridim na-amalite ọzọ, na-eburu n'uche ozi nke ọnụ ọgụgụ ndị na-anabataghị iji kwado uru a chọrọ.
Nkwenye algọridim na usoro asynchronous
Tupu nke a, ihe niile dị mma, n'ihi na anyị na-ekwu maka ụdị izi ozi mmekọrịta. Ma anyị maara na n'ụwa nke oge a anyị na-eji na-eme ihe ọ bụla asynchronously. Kedu ka algọridim yiri ya si arụ ọrụ na sistemụ nwere ụdị izi ozi asynchronous, ebe anyị kwenyere na oge echere maka nzaghachi sitere na ọnụ nwere ike ịdị ogologo oge (n'agbanyeghị, ọdịda nke ọnụ nwekwara ike ịtụle dị ka ihe atụ mgbe. ọnụ nwere ike ịzaghachi ruo ogologo oge aka ike).
Ugbu a na anyị maara otú nkwekọrịta nkwekọrịta algọridim na-arụ ọrụ n'ụkpụrụ, ajụjụ maka ndị na-ajụ ajụjụ na-agụ ndị mere ya ruo ugbu a: ole ọnụ na a usoro nke N ọnụ na ihe asynchronous ozi nlereanya nwere ike ịda nke mere na usoro ka nwere ike iru nkwenye?
Azịza ziri ezi na izi ezi dị n'azụ onye na-emebi ihe.Azịza ziri ezi bụ: 0. Ọ bụrụ na ọbụlagodi otu ọnụ na sistemụ asynchronous daa, sistemụ ahụ agaghị enwe ike iru nkwekọrịta. E gosipụtara nkwupụta a na usoro FLP, nke a maara nke ọma na mpaghara ụfọdụ (1985, Fischer, Lynch, Paterson, njikọ na nke mbụ na njedebe nke isiokwu): "
Ụmụ okorobịa, mgbe ahụ anyị nwere nsogbu, anyị na-eji ihe niile na-asynchronous. Ma ebe a ka ọ dị. Kedu ka esi aga n'ihu na-adị ndụ?
Anyị na-ekwu naanị maka tiori, gbasara mgbakọ na mwepụ. Kedu ihe "enweghị ike nweta nkwenye" pụtara, na-atụgharị site na asụsụ mgbakọ na mwepụ gaa na nke anyị - engineering? Nke a pụtara na "enweghị ike imezu mgbe niile", ya bụ. Enwere ikpe nke nkwenye na-agaghị ekwe omume. Kedu ụdị ikpe nke a bụ?
Nke a bụ mmebi nke ihe onwunwe nke akọwara n'elu. Anyị enweghị nkwekọrịta ọnụ, na usoro enweghị ike inwe ọganihu (enweghị ike imezu ya na oge njedebe) n'ọnọdụ ebe anyị na-enweghị nzaghachi site na ọnụ ọgụgụ niile. N'ihi na n'ime sistemu asynchronous anyị enweghị oge nzaghachi a ga-ebu amụma ma anyị enweghị ike ịma ma ọnụ ọ daala ma ọ bụ na-ewe ogologo oge iji zaghachi.
Ma na omume anyị nwere ike ịchọta ngwọta. Ka algọridim anyị nwee ike ịrụ ọrụ ogologo oge ma ọ bụrụ na ọ dara (nwere ike ịrụ ọrụ ruo mgbe ebighị ebi). Ma n'ọtụtụ ọnọdụ, mgbe ọtụtụ ọnụ na-arụ ọrụ nke ọma, anyị ga-enwe ọganihu na usoro.
Na omume, anyị na-emeso ụdị nzikọrịta ozi na-emekọrịta ihe. A na-aghọta synchrony akụkụ dị ka nke a: n'ozuzu, anyị nwere ihe nlereanya asynchronous, ma a na-ewebata ụfọdụ echiche nke "oge nkwụsi ike zuru ụwa ọnụ" nke oge ụfọdụ.
Oge a n'oge nwere ike ọ gaghị abịa maka ogologo oge ọ bụla, mana ọ ga-abịarịrị otu ụbọchị. Elekere mkpuchi mebere ga-ada, ma site na oge ahụ anyị nwere ike ibu amụma oge delta nke ozi ga-abịarute. Site ugbu a gaa n'ihu, sistemụ na-atụgharị site na asynchronous gaa na synchronous. Na omume, anyị na-emeso usoro ndị dị otú ahụ kpọmkwem.
Paxos algọridim na-edozi nsogbu nkwenye
bụ ezinụlọ nke algọridim na-edozi nsogbu nkwenye maka sistemu na-emekọrịta ihe, dabere na ohere ụfọdụ ọnụ nwere ike daa. Onye edemede nke Paxos bụ . Ọ tụpụtara ihe akaebe na-egosi ịdị adị na izi ezi nke algọridim na 1989.
Ma ihe akaebe ahụ mechara bụrụ ihe na-enweghị isi. E wepụtara mbipụta mbụ naanị na 1998 (peeji 33) na-akọwa algọridim. Dị ka o si pụta, o siri nnọọ ike nghọta, na 2001, e bipụtara nkọwa nke isiokwu ahụ, nke were peeji 14. A na-enye mpịakọta akwụkwọ iji gosi na n'ezie nsogbu nke nkwekọrịta adịghị mfe ma ọlị, na n'azụ algọridim dị otú ahụ bụ nnukwu ọrụ nke ndị kasị mara ihe.
Ọ bụ ihe na-adọrọ mmasị na Leslie Lamport n'onwe ya kwuru na nkuzi ya na n'akwụkwọ nkọwa nke abụọ e nwere otu nkwupụta, otu ahịrị (ọ kwupụtaghị nke), nke a pụrụ ịkọwa n'ụzọ dị iche iche. Ma n'ihi nke a, ọnụ ọgụgụ buru ibu nke Paxos nke oge a na-arụ ọrụ adịghị arụ ọrụ nke ọma.
Nyocha zuru ezu nke ọrụ Paxos ga-ewe ihe karịrị otu isiokwu, yabụ m ga-agbalị ịkọwapụta echiche dị nkenke nke algorithm. Na njikọ ndị dị na njedebe nke akụkọ m, ị ga-ahụ ihe maka ịbanye n'ihu n'ime isiokwu a.
Ọrụ na Paxos
Paxos algọridim nwere echiche nke ọrụ. Ka anyị tụlee isi atọ (enwere mgbanwe nwere ọrụ ndị ọzọ):
- Ndị na-atụ aro (enwere ike iji okwu ndị a: ndị isi ma ọ bụ ndị nhazi). Ndị a bụ ụmụ okorobịa na-amụta banyere ụfọdụ uru ọhụrụ site n'aka onye ọrụ ma na-ewere ọrụ nke onye ndu. Ọrụ ha bụ ịmalite atụmatụ atụmatụ maka uru ọhụrụ na ịhazi ihe omume ndị ọzọ nke ọnụ. Ọzọkwa, Paxos na-enye ohere maka ọnụnọ nke ọtụtụ ndị isi na ọnọdụ ụfọdụ.
- Ndị nnabata (Ndị ntuli aka). Ndị a bụ ọnụ ọnụ na-eme ntuli aka ịnabata ma ọ bụ jụ otu uru. Ọrụ ha dị ezigbo mkpa, n'ihi na mkpebi ahụ dabere na ha: kedu ala usoro ahụ ga-aga (ma ọ bụ na ọ gaghị) na-aga mgbe usoro ọzọ nke nkwekọrịta nkwekọrịta algorithm gasịrị.
- Ndị na-amụ ihe. Ọnụ ụzọ na-anabata ma dee uru anabatara ọhụrụ mgbe ọnọdụ nke sistemu agbanweela. Ha anaghị eme mkpebi, ha na-enweta naanị data ma nwee ike inye ya onye ọrụ njedebe.
Otu ọnụ nwere ike ijikọta ọtụtụ ọrụ na ọnọdụ dị iche iche.
Echiche nke quorum
Anyị na-eche na anyị nwere usoro N ọnụ Na n'ime ha kacha F ọnụ nwere ike ịda. Ọ bụrụ na ọnụ F na-ada, mgbe ahụ anyị ga-enwerịrị opekata mpe 2F+1 ọnụ nnabata.
Nke a dị mkpa ka anyị na-enwekarị ọtụtụ, ọbụlagodi n'ọnọdụ kachasị njọ, nke ọnụ "ezigbo" na-arụ ọrụ nke ọma. Ya bụ F+1 "ezigbo" ọnụ nke kwetara, na uru ikpeazụ ga-anabata. Ma ọ bụghị ya, enwere ike ịnwe ọnọdụ ebe ndị dị iche iche dị n'ime obodo anyị na-ewere ihe dị iche iche na-enweghị ike ikwekọrịta n'etiti onwe ha. Ya mere, anyị chọrọ ọnụ ọgụgụ zuru oke iji nweta votu.
Echiche izugbe nke otu Paxos consensus algọridim si arụ ọrụ
Paxos algọridim na-agụnye akụkụ abụọ buru ibu, nke n'aka nke ya kewara ụzọ abụọ nke ọ bụla:
- Nkeji 1a: Kwadebe. N'oge usoro nkwadebe, onye ndu (onye na-atụ aro) na-agwa ọnụ ụzọ niile: "Anyị na-amalite usoro ịtụ vootu ọhụrụ. Anyị nwere agba ọhụrụ. Ọnụọgụ nke okirikiri a bụ n. Ugbu a, anyị ga-amalite ịtụ vootu." Maka ugbu a, ọ na-akọ naanị mmalite nke okirikiri ọhụrụ, mana anaghị akọpụta uru ọhụrụ. Ọrụ nke ogbo a bụ ibido okirikiri ọhụrụ wee gwa onye ọ bụla ọnụọgụ ya pụrụ iche. Nọmba okirikiri dị mkpa, ọ ga-abụrịrị uru karịa ọnụọgụ ntuli aka niile gara aga sitere na ndị isi niile gara aga. N'ihi na ọ bụ ekele maka ọnụ ọgụgụ gburugburu na ọnụ ọgụgụ ndị ọzọ na usoro ahụ ga-aghọta otú data onye ndu si dị nso. O yikarịrị ka ọnụ ụzọ ndị ọzọ enweelarị nsonaazụ ntuli aka site na agba ndị ọzọ ga-emecha gwa onye ndu na ọ nọ n'azụ oge.
- Nkeji 1b: Nkwa. Mgbe ọnụ ndị nnabata natara ọnụọgụ nke ọkwa ntuli aka ọhụrụ, nsonaazụ abụọ ga-ekwe omume:
- Ọnụọgụ n nke votu ọhụrụ karịrị ọnụ ọgụgụ nke votu ọ bụla gara aga nke onye na-anabata ya sonyeere. Mgbe ahụ, onye na-anabata ya na-ezigara onye ndu nkwa na ọ gaghị etinye aka na votu ọzọ na ọnụ ọgụgụ dị ala karịa n. Ọ bụrụ na onye na-anabata ya ahọrọlarị ihe (ya bụ, ọ nabatalarị ụfọdụ uru na akụkụ nke abụọ), mgbe ahụ ọ na-ejikọta uru a nabatara na ọnụ ọgụgụ nke votu nke ọ sonyere na nkwa ya.
- Ma ọ bụghị ya, ọ bụrụ na onye na-anabata ya amaralarị maka votu dị elu, ọ nwere ike ileghara usoro nkwadebe anya ma ghara ịza onye ndu.
- Nkeji 2a: Nabata. Onye ndu kwesịrị ichere maka nzaghachi site na quorum (ọtụtụ ọnụ na sistemụ) na, ọ bụrụ na enwetara ọnụọgụ nzaghachi achọrọ, mgbe ahụ ọ nwere nhọrọ abụọ maka mmepe nke ihe omume:
- Ụfọdụ n'ime ndị nabatara ezigara ụkpụrụ nke ha ahọrọlarị maka ya. N'okwu a, onye ndu na-ahọrọ uru site na votu na ọnụ ọgụgụ kachasị elu. Ka anyị kpọọ uru a x, ọ na-ezipụ ozi na ọnụ ụzọ niile dị ka: "Nabata (n, x)", ebe uru mbụ bụ nọmba ntuli aka site na nke ya Propose step, na uru nke abụọ bụ ihe onye ọ bụla gbakọtara maka. ya bụ. uru nke anyị n'ezie votu.
- Ọ bụrụ na onye ọ bụla n'ime ndị nabatara ezigara ụkpụrụ ọ bụla, mana ha kwere nkwa ịtụ vootu na gburugburu a, onye ndu nwere ike ịkpọ ha ka ha votu maka uru ha bara, uru nke ọ ghọrọ onye ndu na mbụ. Ka anyị kpọọ ya y. Ọ na-eziga ozi n'ọnụ ụzọ niile dị ka: "Nabata (n, y)", yiri nsonaazụ gara aga.
- Nkeji 2b: Anabata. Ọzọkwa, ndị na-anabata ọnụ, mgbe ha natara ozi "Nabata (...)" n'aka onye ndu, kwenye na ya (ziga nkwenye na ọnụ ọgụgụ niile na ha kwenyere na uru ọhụrụ) naanị ma ọ bụrụ na ha ekwebeghị ụfọdụ (ndị ọzọ) ) ) onye ndu isonye na ntuli aka na onu ogugu na > n, ma ọ bụghị ha na-eleghara arịrịọ nkwenye ahụ anya.
Ọ bụrụ na ihe ka ọtụtụ n'ọnụ zara onye ndú, na ha niile kwadoro uru ọhụrụ ahụ, mgbe ahụ, a na-ewere uru ọhụrụ a nabatara. Hooray! Ọ bụrụ na erughị ọtụtụ ma ọ bụ enwere ọnụ ndị jụrụ ịnakwere uru ọhụrụ ahụ, ihe niile na-amalite.
Nke a bụ otú Paxos algọridim si arụ ọrụ. Nke ọ bụla n'ime usoro ndị a nwere ọtụtụ ụzọ aghụghọ, anyị anaghị atụle ụdị ọdịda dị iche iche, nsogbu nke ọtụtụ ndị isi na ọtụtụ ihe ndị ọzọ, mana ebumnuche nke isiokwu a bụ naanị ịmebata onye na-agụ ya n'ụwa nke ịgbakọ kesara na ọkwa dị elu.
Ọ dịkwa mma ịmara na Paxos abụghị naanị ụdị ya, enwere algọridim ndị ọzọ, dịka ọmụmaatụ, , mana nke a bụ isiokwu maka edemede ọzọ.
Njikọ na ihe maka ọmụmụ ihe ọzọ
Ọkwa mmalite:
- , Preethi Kasireddy, akụkọ blọgụ na Ọkara
- , Adi Kancherla, isiokwu blọgụ na Ọkara
- , Itai Abraham, blọọgụ
- , Itai Abraham, blọgụ edemede
Ọkwa Leslie Lamport:
- , Fischer, Lynch na Paterson, akwụkwọ nyocha, 1985
- , Leslie Lamport, akwụkwọ nyocha, 1998
- , Leslie Lamport, akwụkwọ nyocha, 2001
isi: www.habr.com