Mar sin, smaoinich sinn. Tha 5 cait glaiste san t-seòmar, agus gus an sealbhadair a dhùsgadh, feumaidh iad uile aontachadh air seo nam measg fhèin, oir chan urrainn dhaibh ach an doras fhosgladh le còignear dhiubh a 'lùbadh air. Mas e cat Schrödinger aon de na cait, agus nach eil fios aig na cait eile mun cho-dhùnadh aige, tha a’ cheist ag èirigh: “Ciamar as urrainn dhaibh a dhèanamh?”
San artaigil seo, innsidh mi dhut ann an teirmean sìmplidh mun phàirt teòiridheach de shaoghal nan siostaman sgaoilte agus prionnsapalan an obrachaidh. Nì mi sgrùdadh cuideachd air a’ phrìomh bheachd a tha mar bhunait air Paxos.
Nuair a bhios luchd-leasachaidh a’ cleachdadh bun-structaran sgòthan, diofar stòran-dàta, agus ag obair ann an cruinneachaidhean de àireamh mhòr de nodan, tha iad misneachail gum bi an dàta coileanta, tèarainte, agus an-còmhnaidh ri fhaighinn. Ach càit a bheil na barrantasan?
Gu bunaiteach, tha na barrantasan a th’ againn mar gheallaidhean solaraiche. Tha iad air am mìneachadh anns na sgrìobhainnean mar a leanas: “Tha an t-seirbheis seo gu math earbsach, tha SLA air a thoirt seachad, na gabh dragh, obraichidh a h-uile dad mar a bhiodh dùil agad."
Tha sinn buailteach a bhith a’ creidsinn anns an fheadhainn as fheàrr, oir thug daoine sgairteil bho chompanaidhean mòra cinnteach dhuinn gum bi a h-uile dad gu math. Chan eil sinn a 'faighneachd na ceiste: carson, gu dearbh, an urrainn seo obrachadh idir? A bheil fìreanachadh foirmeil ann airson obrachadh ceart nan siostaman sin?
Chaidh mi gu o chionn ghoirid agus bha e air a bhrosnachadh gu mòr leis a’ chuspair seo. Bha òraidean san sgoil nas coltaiche ri clasaichean calculus na rudeigin co-cheangailte ri siostaman coimpiutair. Ach is e seo dìreach mar a chaidh na h-algorithms as cudromaiche a bhios sinn a’ cleachdadh a h-uile latha, gun eadhon fios a bhith againn air, a dhearbhadh aig aon àm.
Bidh a’ mhòr-chuid de shiostaman sgaoilte ùr-nodha a’ cleachdadh algorithm co-aontachd Paxos agus na diofar atharrachaidhean aige. Is e an rud as fhuaire gu bheil èifeachd agus, ann am prionnsapal, comasachd gu bheil an algairim seo ann a bhith air a dhearbhadh dìreach le peann is pàipear. Ann an cleachdadh, tha an algairim air a chleachdadh ann an siostaman mòra a 'ruith air àireamh mhòr de nodan anns na sgòthan.
Dealbh aotrom de na thèid a dheasbad an ath rud: gnìomh dà sheanalairBheir sinn sùil airson blàthachadh .
Tha dà fheachd againn - dearg is geal. Tha saighdearan geala stèidhichte anns a’ bhaile fo shèist. Tha saighdearan dearga air an stiùireadh le seanalairean A1 agus A2 suidhichte air dà thaobh a’ bhaile. Is e obair nan Redheads ionnsaigh a thoirt air a’ bhaile gheal agus buannachadh. Ach, tha arm gach seanalair dearg leotha fhèin nas lugha na an arm geal.
Suidheachadh buaidh airson an fheadhainn dhearg: feumaidh an dà sheanalair ionnsaigh a thoirt aig an aon àm gus am bi buannachd àireamhach aca thairis air na daoine geala. Gus seo a dhèanamh, feumaidh seanalairean A1 agus A2 tighinn gu aonta le chèile. Ma bheir a h-uile duine ionnsaigh air leth, caillidh na cinn-dhearg.
Gus aonta a ruighinn, faodaidh seanalairean A1 agus A2 teachdairean a chuir gu chèile tro chrìochan a’ bhaile gheal. Faodaidh an teachdaire seanalair càirdeil a ruighinn gu soirbheachail no faodaidh an nàmhaid a bhith air a ghlacadh. Ceist: a bheil an leithid de chonaltradh ann eadar na seanailearan ruadh (an t-sreath de bhith a 'cur theachdairean bho A1 gu A2 agus a chaochladh bho A2 gu A1), anns a bheil iad cinnteach gun aontaich iad ionnsaigh aig uair X. An seo, tha geallaidhean a’ ciallachadh gum bi dearbhadh gun teagamh aig an dà sheanalair gun toir caidreachas (seanalair eile) ionnsaigh gu cinnteach aig an àm ainmichte X.
Osbarr bidh A1 a’ cur teachdaire gu A2 leis an teachdaireachd: “Thug sinn ionnsaigh an-diugh aig meadhan oidhche!” Chan urrainn dha Seanalair A1 ionnsaigh a thoirt gun dearbhadh bhon t-Seanalair A2. Ma tha an teachdaire bho A1 air ruighinn, an uairsin cuiridh an Seanalair A2 dearbhadh leis an teachdaireachd: “Tha, marbhamaid na daoine geala an-diugh.” Ach a-nis chan eil fios aig an t-Seanalair A2 a bheil an teachdaire aige air ruighinn no nach eil, chan eil gealltanas sam bith aige am bi an ionnsaigh aig an aon àm. A-nis feumaidh an Seanalair A2 dearbhadh a-rithist.
Ma bheir sinn tuilleadh cunntas air a’ chonaltradh aca, bidh e soilleir, ge bith cia mheud cearcall iomlaid teachdaireachd a th’ ann, nach eil dòigh ann gealltainn gu bheil an dà sheanalair air na teachdaireachdan aca fhaighinn (a’ gabhail ris gum faodar an dàrna cuid teachdaire a ghlacadh).
Tha an Problem Two Generals na dheagh eisimpleir de shiostam sgaoilte gu math sìmplidh far a bheil dà nod le conaltradh neo-earbsach. Tha seo a’ ciallachadh nach eil gealltanas 100% againn gu bheil iad air an sioncronachadh. Tha duilgheadasan coltach ris air an deasbad a-mhàin air sgèile nas motha nas fhaide air adhart san artaigil.
Bheir sinn a-steach bun-bheachd siostaman sgaoilte
Is e siostam sgaoilte buidheann de choimpiutairean (an seo às deidh sin canaidh sinn nodan riutha) as urrainn teachdaireachdan iomlaid. Tha gach nód fa leth na sheòrsa de bhuidheann neo-eisimeileach. Faodaidh nód gnìomhan a phròiseasadh leis fhèin, ach gus conaltradh le nodan eile, feumaidh e teachdaireachdan a chuir agus fhaighinn.
Dè cho dìreach ‘s a tha teachdaireachdan air an cur an gnìomh, dè na protocolaidhean a thathas a’ cleachdadh - chan eil seo inntinneach dhuinn sa cho-theacsa seo. Tha e cudromach gun urrainn do nodan siostam sgaoilte dàta iomlaid le bhith a’ cur teachdaireachdan.
Chan eil am mìneachadh fhèin a’ coimhead gu math toinnte, ach feumaidh sinn gabhail a-steach gu bheil grunn fheartan aig siostam sgaoilte a bhios cudromach dhuinn.
Feartan siostaman sgaoilte
- Co-chòrdadh - an comas air tachartasan aig an aon àm no aig an aon àm tachairt san t-siostam. A bharrachd air an sin, beachdaichidh sinn gum faodadh tachartasan a tha a’ tachairt air dà nod eadar-dhealaichte a bhith aig an aon àm fhad ‘s nach eil òrdugh soilleir againn mu na tachartasan sin. Ach, mar riaghailt, chan eil e againn.
- Gun ghleoc cruinne. Chan eil òrdugh thachartasan soilleir againn air sgàth dìth cloc cruinne. Ann an saoghal àbhaisteach dhaoine, tha sinn cleachdte ris gu bheil clocaichean agus ùine againn gu tur. Bidh a h-uile càil ag atharrachadh nuair a thig e gu siostaman sgaoilte. Tha eadhon gleocaichean atamach fìor mhionaideach air gluasad, agus dh’ fhaodadh gum bi suidheachaidhean ann far nach urrainn dhuinn innse dè an dà thachartas a thachair an toiseach. Mar sin, chan urrainn dhuinn a bhith an urra ri ùine nas motha.
- Fàilligeadh neo-eisimeileach de nodan siostam. Tha duilgheadas eile ann: faodaidh rudeigin a dhol ceàrr dìreach leis nach mair na nodan againn gu bràth. Dh’ fhaodadh gum fàillig an draibh cruaidh, faodaidh an inneal mas-fhìor san sgòth ath-thòiseachadh, faodaidh an lìonra priobadh agus thèid teachdaireachdan a chall. A bharrachd air an sin, dh'fhaodadh gum bi suidheachaidhean ann far a bheil nodan ag obair, ach aig an aon àm ag obair an aghaidh an t-siostaim. Fhuair an clas mu dheireadh de dhuilgheadasan eadhon ainm air leth: duilgheadas . Is e an eisimpleir as mòr-chòrdte de shiostam sgaoilte leis an duilgheadas seo Blockchain. Ach an-diugh cha bhith sinn a 'beachdachadh air a' chlas shònraichte seo de dhuilgheadasan. Bidh ùidh againn ann an suidheachaidhean far am faodadh dìreach aon nod no barrachd fàiligeadh.
- Modalan conaltraidh (modalan teachdaireachd) eadar nodan. Tha sinn mar-thà air dearbhadh gum bi nodan a’ conaltradh le bhith ag iomlaid theachdaireachdan. Tha dà mhodail teachdaireachd ainmeil ann: sioncronaich agus asyncronach.
Modalan conaltraidh eadar nodan ann an siostaman sgaoilte
Synchronous modail - tha fios againn le cinnt gu bheil ùine chuingealaichte aithnichte ann nuair a thathar a’ gealltainn gun ruig teachdaireachd bho aon nód gu nód eile. Ma tha an ùine seo air a dhol seachad agus nach eil an teachdaireachd air ruighinn, faodaidh sinn a ràdh gu sàbhailte gu bheil an nód air fàiligeadh. Anns a’ mhodail seo tha amannan feitheimh ris a bheil dùil againn.
Modail asyncronach - ann am modalan asyncronach tha sinn den bheachd gu bheil an ùine feitheimh crìochnaichte, ach chan eil leithid de ùine ann às deidh sin is urrainn dhuinn gealltainn gu bheil an nód air fàiligeadh. An fheadhainn sin. Faodaidh an ùine feitheimh airson teachdaireachd bho nód a bhith fada gu neo-riaghailteach. Is e mìneachadh cudromach a tha seo, agus bruidhnidh sinn mu dheidhinn nas fhaide.
Bun-bheachd co-aontachd ann an siostaman sgaoilte
Mus dèan sinn mìneachadh foirmeil air bun-bheachd co-aontachd, beachdaichidh sinn air eisimpleir de shuidheachadh far a bheil feum againn air, is e sin - Ath-riochdachadh inneal stàite.
Tha cuid de log sgaoilte againn. Bu mhath leinn gum biodh e cunbhalach agus gum biodh dàta co-ionann ann mu gach nod den t-siostam sgaoilte. Nuair a dh’ ionnsaicheas aon de na nodan luach ùr a tha e gu bhith a’ sgrìobhadh chun loga, bidh e na ghnìomh aige an luach seo a thabhann do gach nod eile gus am bi an log air ùrachadh air a h-uile nod agus an siostam a’ gluasad gu staid chunbhalach ùr. Anns a 'chùis seo, tha e cudromach gum bi na nodan ag aontachadh nam measg fhèin: tha na nodan uile ag aontachadh gu bheil an luach ùr a thathar a' moladh ceart, tha na nodan uile a 'gabhail ris an luach seo, agus a-mhàin anns a' chùis seo faodaidh a h-uile duine an luach ùr a sgrìobhadh chun log.
Ann am faclan eile: cha robh gin de na nodan a’ gearan gu robh fiosrachadh nas buntainniche aige, agus bha an luach a chaidh a mholadh ceàrr. Tha aonta eadar nodan agus aonta air aon luach ceart ris an deach gabhail mar cho-aontachd ann an siostam sgaoilte. An ath rud, bruidhnidh sinn mu algorithms a leigeas le siostam sgaoilte a bhith cinnteach gun ruig e co-aontachd.
Nas foirmeile, is urrainn dhuinn algorithm co-aontachd (no dìreach algairim co-aontachd) a mhìneachadh mar ghnìomh sònraichte a ghluaiseas siostam sgaoilte bho stàite A gu stàite B. A bharrachd air an sin, tha a h-uile nod a’ gabhail ris an stàit seo, agus faodaidh gach nod a dhearbhadh. Mar a thionndaidh e, chan eil an obair seo idir cho beag ‘s a tha e coltach aig a’ chiad sealladh.
Feartan an Algorithm Co-aontachd
Feumaidh trì feartan a bhith aig an algairim co-aontachd gus am bi an siostam fhathast ann agus beagan adhartais ann a bhith a’ gluasad bho stàite gu stàite:
- Aonta - feumaidh a h-uile nod obrachaidh ceart an aon luach a ghabhail (ann an artaigilean tha an togalach seo cuideachd air ainmeachadh mar sheilbh sàbhailteachd). Feumaidh a h-uile nodan a tha ag obair an-dràsta (nach do dh’ fhàilnich no air conaltradh a chall leis an fheadhainn eile) tighinn gu aonta agus gabhail ri luach coitcheann deireannach.
Tha e cudromach tuigsinn an seo gu bheil na nodan san t-siostam sgaoilte air a bheil sinn a’ beachdachadh ag iarraidh aontachadh. Is e sin, tha sinn a-nis a 'bruidhinn mu shiostaman anns am faod rudeigin fàiligeadh gu sìmplidh (mar eisimpleir, tha cuid de nód a' fàilligeadh), ach gu cinnteach chan eil nodan ann a tha ag obair a dh'aona ghnothaich an aghaidh feadhainn eile (gnìomh seanalairean Byzantine). Air sgàth an togalaich seo, tha an siostam fhathast cunbhalach.
- ionracas - ma tha na nodan a tha ag obair gu ceart a’ tabhann an aon luach v, a tha a’ ciallachadh gum feum a h-uile nód obrachaidh ceart gabhail ris an luach seo v.
- Crìochnachadh - gabhaidh a h-uile nod obrachaidh ceart mu dheireadh luach sònraichte (seilbh beòthalachd), a leigeas leis an algairim adhartas a dhèanamh san t-siostam. Feumaidh gach nòta a tha ag obair gu ceart gabhail ris an luach mu dheireadh nas luaithe no nas fhaide air adhart agus a dhearbhadh: “Dhòmhsa, tha an luach seo fìor, tha mi ag aontachadh leis an t-siostam gu lèir.”
Eisimpleir de mar a tha an algairim co-aontachd ag obair
Ged is dòcha nach eil feartan an algairim gu tur soilleir. Mar sin, seallaidh sinn le eisimpleir dè na h-ìrean a bhios an algairim co-aontachd as sìmplidh a’ dol troimhe ann an siostam le modal teachdaireachd sioncronaich, anns a bheil a h-uile nod ag obair mar a bhiodh dùil, nach eil teachdaireachdan air chall agus nach eil dad a’ briseadh (a bheil seo a’ tachairt dha-rìribh?).
- Bidh e uile a’ tòiseachadh le moladh pòsaidh (Moladh). Gabhamaid ris gu bheil neach-dèiligidh ceangailte ri nód ris an canar "Node 1" agus thòisich e air malairt, a 'dol seachad air luach ùr don nód - O. Bho seo a-mach, canaidh sinn "Node 1" tairgse. Mar thagraiche, feumaidh “Node 1” a-nis innse don t-siostam gu lèir gu bheil dàta ùr aige, agus bidh e a’ cur teachdaireachdan chun a h-uile nod eile: “Seall! Thàinig an ciall “O” thugam agus tha mi airson a sgrìobhadh sìos! Dèan cinnteach gun clàraich thu “O” nad loga cuideachd.”
- Is e an ath ìre bhòtadh airson an luach a thathar a’ moladh (Bhòt). Carson a tha e? Dh’ fhaodadh e tachairt gu bheil nodan eile air fiosrachadh nas ùire fhaighinn, agus gu bheil dàta aca air an aon ghnothach.
Nuair a chuireas nód “Node 1” a mholadh, bidh na nodan eile a’ sgrùdadh na logaichean aca airson dàta mun tachartas seo. Mura h-eil contrarrachdan ann, tha na nodan ag ainmeachadh: “Tha, chan eil dàta eile agam airson an tachartais seo. Is e luach “O” am fiosrachadh as ùire a tha sinn airidh air.”Ann an suidheachadh sam bith eile, faodaidh nodan freagairt a thoirt do “Node 1”: “Èist! Tha dàta nas ùire agam mun ghnothach seo. Chan e 'O', ach rudeigin nas fheàrr."
Aig an ìre bhòtaidh, thig na nodan gu co-dhùnadh: an dàrna cuid tha iad uile a’ gabhail ris an aon luach, no bidh aon dhiubh a’ bhòtadh na aghaidh, a’ nochdadh gu bheil dàta nas ùire aige.
- Ma bha a 'chuairt bhòtaidh soirbheachail agus bha a h-uile duine fàbharach, gluaisidh an siostam gu ìre ùr - A' gabhail ris an luach. Bidh “Node 1” a’ cruinneachadh a h-uile freagairt bho nodan agus aithisgean eile: “Dh’ aontaich a h-uile duine mun luach “O”! A-nis tha mi ag innse gu h-oifigeil gur e “O” an ciall ùr againn, an aon rud airson a h-uile duine! Sgrìobh sìos e anns an leabhar bheag agad, na dìochuimhnich. Sgrìobh sìos sa chlàr agad e!”
- Bidh na nodan a tha air fhàgail a’ cur dearbhadh (Gabhail ris) gu bheil iad air an luach “O” a sgrìobhadh sìos; chan eil dad ùr air ruighinn aig an àm seo (seòrsa de ghealladh dà-ìre). Às deidh an tachartas cudromach seo, tha sinn den bheachd gu bheil an gnothach sgaoilte air a chrìochnachadh.
Mar sin, tha an algairim co-aontachd ann an cùis shìmplidh air a dhèanamh suas de cheithir ceumannan: moladh, bhòt (bhòtadh), gabhail (gabhail ris), dearbhadh gabhail ris (gabhail ris).
Mura b’ urrainn dhuinn aig ìre air choreigin aonta a ruighinn, an uairsin tòisichidh an algairim a-rithist, a’ toirt aire don fhiosrachadh a thug na nodan seachad a dhiùlt an luach a chaidh a mholadh a dhearbhadh.
Algorithm co-aontachd ann an siostam asyncronach
Roimhe seo, bha a h-uile dad rèidh, oir bha sinn a ’bruidhinn mu mhodal teachdaireachdan sioncronaich. Ach tha fios againn anns an t-saoghal ùr-nodha gu bheil sinn cleachdte ri bhith a’ dèanamh a h-uile càil gu neo-chunbhalach. Mar a tha algorithm coltach ris ag obair ann an siostam le modal teachdaireachd asyncronach, far a bheil sinn den bheachd gum faod an ùine feitheimh airson freagairt bho nód a bhith fada gu neo-riaghailteach (co-dhiù, faodar beachdachadh air fàilligeadh nód mar eisimpleir nuair a faodaidh nód freagairt airson ùine gu neo-riaghailteach).
A-nis gu bheil fios againn mar a tha an algairim co-aontachd ag obair ann am prionnsapal, ceist dha na leughadairean fiosrachail sin a rinn e gu ruige seo: cia mheud nodan ann an siostam nodan N le modal teachdaireachd asyncronach a dh’ fhaodadh fàiligeadh gus an urrainn don t-siostam fhathast co-aontachd a ruighinn?
Tha am freagairt ceart agus an fhìreanachadh air cùl an spoiler.Is e am freagairt ceart: 0. Ma dh’ fhailicheas eadhon aon nód ann an siostam asyncronach, cha bhith e comasach don t-siostam co-aontachd a ruighinn. Tha an aithris seo air a dhearbhadh ann an teòirim FLP, a tha aithnichte ann an cearcallan sònraichte (1985, Fischer, Lynch, Paterson, ceangal ris an fhear thùsail aig deireadh na h-artaigil): “Tha e do-dhèanta co-aontachd sgaoilte a choileanadh ma dh’ fhailicheas co-dhiù aon nód. .”
Guys, an uairsin tha duilgheadas againn, tha sinn cleachdte ris a h-uile dad a bhith asyncronach. Agus seo e. Ciamar a leantainn air adhart a 'fuireach?
Bha sinn dìreach a’ bruidhinn air teòiridh, mu dheidhinn matamataig. Dè tha “chan urrainnear co-aontachd a choileanadh” a’ ciallachadh, ag eadar-theangachadh bho chànan matamataigeach gu ar cànan - innleadaireachd? Tha seo a’ ciallachadh “nach gabh a choileanadh an-còmhnaidh”, i.e. Tha cùis ann far nach gabh co-aontachd a choileanadh. Dè an seòrsa cùis a tha seo?
Is e seo dìreach a’ bhriseadh air an togalach beòthalachd a chaidh a mhìneachadh gu h-àrd. Chan eil aonta coitcheann againn, agus chan urrainn don t-siostam adhartas a dhèanamh (chan urrainn dha a chrìochnachadh ann an ùine chrìochnaichte) anns a’ chùis far nach eil freagairt againn bho gach nod. Leis nach eil ùine freagairt ro-innseach againn ann an siostam asyncronach agus chan eil fios againn a bheil nód air tuiteam no a bheil e dìreach a’ toirt ùine mhòr airson freagairt.
Ach ann an cleachdadh is urrainn dhuinn fuasgladh a lorg. Leig leis an algairim againn a bhith comasach air obrachadh airson ùine mhòr gun fhios nach bi fàilligidhean ann (is dòcha gun obraich e gun chrìoch). Ach anns a 'mhòr-chuid de shuidheachaidhean, nuair a bhios a' mhòr-chuid de nodan ag obair gu ceart, bidh adhartas againn san t-siostam.
Ann an cleachdadh, bidh sinn a 'dèiligeadh ri modalan conaltraidh pàirt-shioncronach. Thathas a’ tuigsinn gu bheil sioncronadh pàirteach mar a leanas: anns a’ chùis choitcheann, tha modail asyncronach againn, ach tha bun-bheachd sònraichte de “ùine seasmhachd cruinne” aig àm sònraichte air a thoirt a-steach gu foirmeil.
Is dòcha nach tig an t-àm seo airson ùine sam bith, ach feumaidh e tighinn aon latha. Bidh an gleoc rabhaidh brìgheil a ’glaodhadh, agus bhon mhionaid sin is urrainn dhuinn ro-innse dè an ùine delta airson an ruig na teachdaireachdan. Bhon mhionaid seo, bidh an siostam a’ tionndadh bho asyncronach gu sioncronaich. Ann an cleachdadh, bidh sinn a 'dèiligeadh gu mionaideach ri siostaman mar sin.
Bidh algorithm Paxos a’ fuasgladh dhuilgheadasan co-aontachd
na theaghlach de algorithms a dh’ fhuasglas an duilgheadas co-aontachd airson siostaman a tha gu ìre sioncronaich, le ùmhlachd do dh’ fhaodadh gum faodadh cuid de nodan fàiligeadh. Tha an t-ùghdar aig Paxos . Mhol e dearbhadh foirmeil air a bhith ann agus ceartachd an algairim ann an 1989.
Ach thionndaidh an dearbhadh a-mach gu bhith fada bho bhith beag. Chaidh a 'chiad fhoillseachadh fhoillseachadh a-mhàin ann an 1998 (33 duilleagan) a' toirt cunntas air an algairim. Mar a thionndaidh e a-mach, bha e uamhasach duilich a thuigsinn, agus ann an 2001 chaidh mìneachadh mun artaigil fhoillseachadh, a thug 14 duilleagan. Tha an àireamh de fhoillseachaidhean air a thoirt seachad gus sealltainn nach eil an duilgheadas co-aontachd idir sìmplidh idir, agus air cùl na h-algorithms sin tha tòrr obrach leis na daoine as sgiobalta.
Tha e inntinneach gun tug Leslie Lamport fhèin fa-near anns an òraid aige gu bheil aon aithris ann an dàrna artaigil mìneachaidh, aon loidhne (cha do shònraich e dè am fear), a dh'fhaodar a mhìneachadh ann an diofar dhòighean. Agus air sgàth seo, chan eil àireamh mhòr de bhuileachadh Paxos an latha an-diugh ag obair gu tur ceart.
Bheireadh mion-sgrùdadh mionaideach air obair Paxos barrachd air aon artaigil, agus mar sin feuchaidh mi ri mìneachadh goirid a dhèanamh air a’ phrìomh bheachd air an algairim. Anns na ceanglaichean aig deireadh an artaigil agam gheibh thu stuthan airson tuilleadh dàibheadh a-steach don chuspair seo.
Dreuchdan aig Paxos
Tha bun-bheachd de dhleastanasan aig algorithm Paxos. Beachdaichidh sinn air trì prìomh fheadhainn (tha atharrachaidhean ann le dreuchdan a bharrachd):
- Luchd-tairgse (faodar na teirmean a chleachdadh cuideachd: stiùirichean no co-òrdanaichean). Is iad sin na daoine a bhios ag ionnsachadh mu luach ùr bhon neach-cleachdaidh agus a’ gabhail os làimh dreuchd stiùiriche. Is e an obair aca cruinneachadh de mholaidhean a chuir air bhog airson luach ùr agus gnìomhan eile nan nodan a cho-òrdanachadh. A bharrachd air an sin, tha Paxos a 'ceadachadh grunn stiùirichean a bhith an làthair ann an suidheachaidhean sònraichte.
- Luchd-gabhail (Luchd-bhòtaidh). Is iad sin nodan a bhòtas airson gabhail ri no diùltadh luach sònraichte. Tha an dreuchd aca glè chudromach, oir tha an co-dhùnadh an urra riutha: dè an stàit a thèid (no nach bi) an siostam às deidh an ath ìre den algorithm co-aontachd.
- Luchd-ionnsachaidh. Nòtaichean a tha dìreach a’ gabhail ris agus a’ sgrìobhadh an luach ùr ris an deach gabhail nuair a tha staid an t-siostaim air atharrachadh. Cha bhith iad a’ dèanamh cho-dhùnaidhean, bidh iad dìreach a’ faighinn an dàta agus is urrainn dhaibh a thoirt don neach-cleachdaidh deireannach.
Faodaidh aon nód grunn dhreuchdan a chur còmhla ann an diofar shuidheachaidhean.
Bun-bheachd cuòram
Tha sinn a’ gabhail ris gu bheil siostam againn de N nodan Agus dhiubh an ìre as àirde F faodaidh nodan fàiligeadh. Ma dh’ fhailicheas nodan F, feumaidh sinn a bhith againn co-dhiù 2F+1 nodan glacadair.
Tha seo riatanach gus am bi a’ mhòr-chuid againn an-còmhnaidh, eadhon anns an t-suidheachadh as miosa, de nodan “math” a bhios ag obair gu ceart. S e sin F+1 nodan "math" a dh'aontaich, agus thèid gabhail ris an luach mu dheireadh. Rud eile, dh’ fhaodadh suidheachadh a bhith ann far am bi na diofar bhuidhnean ionadail againn a’ gabhail ri diofar bhrìgh agus nach urrainn dhaibh aontachadh eatorra fhèin. Mar sin, feumaidh sinn mòr-chuid iomlan airson a’ bhòt a bhuannachadh.
Am beachd coitcheann air mar a tha algorithm co-aontachd Paxos ag obair
Tha algorithm Paxos a’ toirt a-steach dà ìre mhòr, a tha an uair sin air an roinn ann an dà cheum gach fear:
- Ceum 1a: Dèan ullachadh. Rè na h-ìre ullachaidh, tha an stiùiriche (neach-tairgse) ag innse don h-uile nod: “Tha sinn a’ tòiseachadh air ìre bhòtaidh ùr. Tha cuairt ùr againn. Is e àireamh na cuairte seo n. A-nis tòisichidh sinn a’ bhòtadh. ” Airson a-nis, tha e dìreach ag aithris toiseach cearcall ùr, ach chan eil e ag aithris luach ùr. Is e obair na h-ìre seo cuairt ùr a thòiseachadh agus innse don h-uile duine mun àireamh shònraichte aige. Tha an àireamh cruinn cudromach, feumaidh e a bhith na luach nas motha na a h-uile àireamh bhòtaidh a bh’ ann roimhe bho na stiùirichean a bh’ ann roimhe. Leis gur ann mar thoradh air an àireamh chruinn a thuigeas nodan eile san t-siostam dè cho fada ‘s a tha dàta an stiùiriche. Tha e coltach gu bheil toraidhean bhòtaidh aig nodan eile mu thràth bho chuairtean fada nas fhaide air adhart agus gun innis iad don stiùiriche gu bheil e air cùl na h-amannan.
- Ceum 1b: Gealladh. Nuair a fhuair na nodan glacaidh àireamh na h-ìre bhòtaidh ùr, tha dà thoradh comasach:
- Tha an àireamh n den bhòt ùr nas àirde na an àireamh de bhòt sam bith roimhe anns an do ghabh an neach-gabhail pàirt. An uairsin cuiridh an neach-gabhail gealladh chun stiùiriche nach gabh e pàirt ann am barrachd bhòtaichean le àireamh nas ìsle na n. Ma tha an neach-gabhail mar-thà air bhòtadh airson rudeigin (is e sin, tha e mu thràth air gabhail ri beagan luach san dàrna ìre), bidh e a’ ceangal an luach ris an deach gabhail agus àireamh na bhòt anns an do ghabh e pàirt ris a ghealladh.
- Rud eile, ma tha fios aig an neach-gabhail mu thràth mun bhòt le àireamh nas àirde, faodaidh e dìreach an ceum ullachaidh a leigeil seachad agus gun a bhith a’ freagairt don stiùiriche.
- Ceum 2a: Gabh ris. Feumaidh an stiùiriche feitheamh ri freagairt bhon chuòram (a 'mhòr-chuid de nodan san t-siostam) agus, ma gheibhear an àireamh riatanach de fhreagairtean, tha dà roghainn aige airson leasachadh thachartasan:
- Chuir cuid den luchd-gabhail luachan air an robh iad air bhòtadh mu thràth. Anns a 'chùis seo, bidh an ceannard a' taghadh an luach bhon bhòt leis an àireamh as motha. Canaidh sinn an luach seo x, agus bidh e a’ cur teachdaireachd chun a h-uile nod mar: “Gabh (n, x)”, far a bheil a’ chiad luach mar an àireamh bhòtaidh bhon cheum Molaidh aige fhèin, agus is e an dàrna luach na chruinnich a h-uile duine, i.e. an luach dha-rìribh air a bheil sinn a’ bhòtadh.
- Mura do chuir gin den luchd-gabhail luachan sam bith, ach gun do gheall iad dìreach bhòtadh sa chuairt seo, faodaidh an stiùiriche cuireadh a thoirt dhaibh bhòtadh airson an luach, an luach air an robh e na stiùiriche sa chiad àite. Canaidh sinn e y. Bidh e a’ cur teachdaireachd chun a h-uile nod mar: “Gabh (n, y)”, coltach ris a’ bhuil roimhe.
- Ìre 2b: Air gabhail ris. Nas fhaide, bidh an neach-gabhail ag aontachadh, nuair a gheibh iad an teachdaireachd “Gabh (...)” bhon stiùiriche, ag aontachadh ris (cuir dearbhadh chun a h-uile nod gu bheil iad ag aontachadh leis an luach ùr) a-mhàin mura h-eil iad air cuid (eile) a ghealltainn. stiùiriche pàirt a ghabhail ann am bhòtadh le àireamh cruinn n> n, air dhòigh eile bidh iad a’ seachnadh an iarrtas dearbhaidh.
Ma fhreagair a 'mhòr-chuid de nodan an stiùiriche, agus gun do dhearbh iad uile an luach ùr, thathas a' meas gu bheilear a 'gabhail ris an luach ùr. Hooray! Mura ruigear a’ mhòr-chuid no ma tha nodan ann a dhiùlt gabhail ris an luach ùr, tòisichidh a h-uile càil.
Seo mar a tha algorithm Paxos ag obair. Tha mòran subtleties aig gach aon de na h-ìrean sin, cha mhòr nach do smaoinich sinn air diofar sheòrsaichean fàilligeadh, duilgheadasan ioma-stiùiriche agus mòran a bharrachd, ach is e adhbhar an artaigil seo dìreach an leughadair a thoirt a-steach do shaoghal coimpiutaireachd sgaoilte aig ìre àrd.
Is fhiach a bhith mothachail cuideachd nach e Paxos an aon fhear de sheòrsa, tha algorithms eile ann, mar eisimpleir, , ach seo cuspair airson artaigil eile.
Ceanglaichean gu stuthan airson tuilleadh ionnsachaidh
Ìre tòiseachaidh:
- , Preethi Kasireddy, artaigil blog air Meadhanach
- , Adi Kancherla, artaigil blog air Meadhanach
- , Ittai Abraham, blog
- , Ittai Abraham, artaigil blog
Ìre Leslie Lamport:
- , Fischer, Lynch agus Paterson, pàipear rannsachaidh, 1985
- , Leslie Lamport, pàipear rannsachaidh, 1998
- , Leslie Lamport, pàipear rannsachaidh, 2001
Source: www.habr.com