🥇Il-Qattus ta' Schrödinger Mingħajr il-Kaxxa: Il-Problema tal-Kunsens f'Sistemi Distribwiti

Allura, ejja nimmaġinaw. Hemm 5 qtates msakkra fil-kamra, u sabiex iqumu lis-sid, jeħtieġ li lkoll jaqblu dwar dan bejniethom, għax jistgħu jiftħu biss il-bieb b'ħamsa minnhom mimli fuqha. Jekk wieħed mill-qtates huwa l-qattus ta 'Schrödinger, u l-qtates l-oħra ma jafux dwar id-deċiżjoni tiegħu, tqum il-mistoqsija: "Kif jistgħu jagħmlu dan?"

F'dan l-artikolu, ser ngħidlek f'termini sempliċi dwar il-komponent teoretiku tad-dinja tas-sistemi distribwiti u l-prinċipji tat-tħaddim tagħhom. Se nikkunsidra wkoll superfiċjalment l-idea prinċipali sottostanti Paxos.

Meta l-iżviluppaturi jużaw infrastrutturi tas-sħab, databases varji, u jaħdmu fi gruppi ta 'numru kbir ta' nodi, huma kunfidenti li d-dejta tkun kompluta, sigura u dejjem disponibbli. Imma fejn huma l-garanziji?

Essenzjalment, il-garanziji li għandna huma garanziji tal-fornitur. Huma deskritti fid-dokumentazzjoni kif ġej: "Dan is-servizz huwa pjuttost affidabbli, għandu SLA partikolari, tinkwetax, kollox se jaħdem b'mod distribwit kif tistenna."

Għandna t-tendenza li nemmnu fl-aħjar, għax guys intelliġenti minn kumpaniji kbar assigurawna li kollox se jkun tajjeb. Aħna ma nistaqsux il-mistoqsija: għaliex, fil-fatt, dan jista 'jaħdem għal kollox? Hemm xi ġustifikazzjoni formali għat-tħaddim korrett ta' sistemi bħal dawn?

Dan l-aħħar mort Skola tal-Kompjuter Imqassam u kien ispirat ħafna minn dan is-suġġett. Lectures fl-iskola kienu aktar bħal klassijiet tal-kalkulu milli xi ħaġa relatata mas-sistemi tal-kompjuter. Iżda dan huwa eżattament kif l-algoritmi l-aktar importanti li nużaw kuljum, mingħajr lanqas biss nafu, ġew ippruvati f'ħin wieħed.

Il-biċċa l-kbira tas-sistemi distribwiti moderni jużaw l-algoritmu tal-kunsens Paxos u l-modifiki varji tiegħu. L-iktar ħaġa sabiħa hija li l-validità u, fil-prinċipju, il-possibbiltà stess tal-eżistenza ta 'dan l-algoritmu jistgħu jiġu ppruvati sempliċement b'pinna u karta. Fil-prattika, l-algoritmu jintuża f'sistemi kbar li jaħdmu fuq numru kbir ta 'nodi fis-sħab.

Illustrazzjoni ħafifa ta 'dak li se jiġi diskuss li jmiss: il-kompitu ta' żewġ ġeneraliEjja nagħtu ħarsa għal warm-up kompitu ta’ żewġ ġenerali.

Għandna żewġ armati - aħmar u abjad. Truppi bojod huma bbażati fil-belt assedjata. Truppi ħomor immexxija mill-ġenerali A1 u A2 jinsabu fuq żewġ naħat tal-belt. Il-kompitu tar-redheads huwa li jattakkaw il-belt bajda u jirbħu. Madankollu, l-armata ta 'kull ġenerali aħmar individwalment hija iżgħar mill-armata bajda.

Kundizzjonijiet tar-rebħa għall-aħmar: iż-żewġ ġenerali jridu jattakkaw fl-istess ħin biex ikollhom vantaġġ numeriku fuq il-abjad. Biex tagħmel dan, il-ġenerali A1 u A2 jeħtieġ li jaslu għal ftehim bejniethom. Jekk kulħadd jattakka separatament, ir-redheads jitilfu.

Biex jintlaħaq ftehim, il-ġenerali A1 u A2 jistgħu jibagħtu messaġġiera lil xulxin permezz tat-territorju tal-belt bajda. Il-messaġġier jista 'jilħaq b'suċċess ġenerali alleat jew jista' jiġi interċettat mill-ghadu. Mistoqsi garanziji jfissru li ż-żewġ ġenerali se jkollhom konferma mhux ambigwa li alleat (ġenerali ieħor) definittivament se jattakka fil-ħin stabbilit X.

Ejja ngħidu li A1 jibgħat messaġġier lil A2 bil-messaġġ: "Ejja nattakkaw illum f'nofsillejl!" Il-Ġeneral A1 ma jistax jattakka mingħajr konferma mill-Ġeneral A2. Jekk il-messaġġier minn A1 ikun wasal, allura l-Ġeneral A2 jibgħat konferma bil-messaġġ: "Iva, ejja noqtlu l-abjad illum." Imma issa l-Ġeneral A2 ma jafx jekk il-messaġġier tiegħu wasalx jew le, m'għandux garanzija jekk l-attakk hux se jkun simultanju. Issa Ġenerali A2 għal darb'oħra jeħtieġ konferma.

Jekk niddeskrivu aktar il-komunikazzjoni tagħhom, isir ċar li ma jimpurtax kemm hemm ċikli ta 'skambju ta' messaġġi, m'hemm l-ebda mod kif niggarantixxu li ż-żewġ ġenerali jkunu rċevew il-messaġġi tagħhom (jekk wieħed jassumi li kwalunkwe messaġġier jista 'jiġi interċettat).

Il-Problema taż-Żewġ Ġenerali hija illustrazzjoni kbira ta 'sistema distribwita sempliċi ħafna fejn hemm żewġ nodi b'komunikazzjoni mhux affidabbli. Dan ifisser li m'għandniex garanzija ta' 100% li huma sinkronizzati. Problemi simili huma diskussi biss fuq skala akbar aktar tard fl-artiklu.

Aħna nintroduċu l-kunċett ta 'sistemi distribwiti

Sistema mqassma hija grupp ta 'kompjuters (minn hawn 'il quddiem se nsejħulhom nodi) li jistgħu jiskambjaw messaġġi. Kull nodu individwali huwa xi tip ta 'entità awtonoma. Nodu jista 'jipproċessa kompiti waħdu, iżda sabiex jikkomunika ma' nodi oħra, jeħtieġ li jibgħat u jirċievi messaġġi.

Kif eżattament jiġu implimentati l-messaġġi, liema protokolli jintużaw - dan mhuwiex ta 'interess għalina f'dan il-kuntest. Huwa importanti li n-nodi ta' sistema distribwita jkunu jistgħu jiskambjaw data ma' xulxin billi jibagħtu messaġġi.

Id-definizzjoni nnifisha ma tantx tidher ikkumplikata, iżda rridu nqisu li sistema mqassma għandha numru ta 'attributi li se jkunu importanti għalina.

Attributi ta' sistemi distribwiti

Fl-istess ħin – il-possibbiltà ta' avvenimenti simultanji jew konkorrenti li jseħħu fis-sistema. Barra minn hekk, aħna se nikkunsidraw avvenimenti li jseħħu fuq żewġ nodi differenti bħala potenzjalment konkorrenti sakemm ma jkollniex ordni ċara ta 'okkorrenza ta' dawn l-avvenimenti. Iżda, bħala regola, m'għandniex dan.
L-ebda arloġġ globali. M'għandniex ordni ċara ta 'avvenimenti minħabba n-nuqqas ta' arloġġ globali. Fid-dinja ordinarja tan-nies, aħna mdorrijin għall-fatt li għandna arloġġi u ħin assolutament. Kollox jinbidel meta niġu għal sistemi distribwiti. Anke arloġġi atomiċi ultra-preċiżi għandhom drift, u jista 'jkun hemm sitwazzjonijiet fejn ma nistgħux ngħidu liema minn żewġ avvenimenti ġara l-ewwel. Għalhekk, lanqas ma niddependu fuq il-ħin.
Falliment indipendenti tan-nodi tas-sistema. Hemm problema oħra: xi ħaġa tista' tmur ħażin sempliċement għax in-nodi tagħna ma jdumux għal dejjem. Il-hard drive jista 'jfalli, il-magna virtwali fis-sħaba tista' terġa 'tibda, in-netwerk jista' jteptep u l-messaġġi jintilfu. Barra minn hekk, jista 'jkun hemm sitwazzjonijiet fejn in-nodi jaħdmu, iżda fl-istess ħin jaħdmu kontra s-sistema. L-aħħar klassi ta 'problemi saħansitra rċeviet isem separat: problema Ġenerali Biżantini. L-aktar eżempju popolari ta 'sistema distribwita b'din il-problema huwa Blockchain. Imma llum mhux se nikkunsidraw din il-klassi speċjali ta 'problemi. Se nkunu interessati f'sitwazzjonijiet li fihom sempliċiment nodu wieħed jew aktar jistgħu jfallu.
Mudelli ta' komunikazzjoni (mudelli ta' messaġġi) bejn in-nodi. Diġà waqqafna li n-nodi jikkomunikaw billi jiskambjaw messaġġi. Hemm żewġ mudelli ta 'messaġġi magħrufa sew: sinkroniku u mhux sinkroniku.

Mudelli ta' komunikazzjoni bejn nodi f'sistemi distribwiti

Mudell sinkroniku – nafu żgur li hemm delta ta’ żmien magħrufa finit li matulu messaġġ huwa garantit li jasal minn nodu għal ieħor. Jekk dan iż-żmien għadda u l-messaġġ ma wasalx, nistgħu ngħidu b'mod sikur li n-node falla. F'dan il-mudell għandna ħinijiet ta' stennija prevedibbli.

Mudell mhux sinkroniku – f'mudelli asinkroniċi nikkunsidraw li l-ħin ta 'stennija huwa finit, iżda m'hemm l-ebda delta ta' żmien bħal dan li warajh nistgħu niggarantixxu li n-node jkun falla. Dawk. Il-ħin ta' stennija għal messaġġ minn nodu jista' jkun twil b'mod arbitrarju. Din hija definizzjoni importanti, u se nitkellmu aktar dwarha.

Il-kunċett ta' kunsens f'sistemi distribwiti

Qabel ma niddefinixxu formalment il-kunċett ta' kunsens, ejja nikkunsidraw eżempju ta' sitwazzjoni fejn għandna bżonnha, jiġifieri - Replikazzjoni tal-Magni tal-Istat.

Għandna xi log imqassam. Nixtiequ li jkun konsistenti u jkun fih data identika fuq in-nodi kollha tas-sistema distribwita. Meta wieħed min-nodi jitgħallem valur ġdid li se jikteb fil-log, il-kompitu tiegħu jsir li joffri dan il-valur lin-nodi l-oħra kollha sabiex il-log jiġi aġġornat fuq in-nodi kollha u s-sistema timxi għal stat konsistenti ġdid. F'dan il-każ, huwa importanti li n-nodi jaqblu bejniethom: in-nodi kollha jaqblu li l-valur il-ġdid propost huwa korrett, in-nodi kollha jaċċettaw dan il-valur, u f'dan il-każ biss kulħadd jista 'jikteb il-valur il-ġdid fil-log.

Fi kliem ieħor: l-ebda wieħed min-nodi ma oġġezzjona li kellu aktar informazzjoni rilevanti, u l-valur propost ma kienx korrett. Il-ftehim bejn in-nodi u l-qbil fuq valur wieħed aċċettat korrett huwa kunsens f'sistema distribwita. Sussegwentement, se nitkellmu dwar algoritmi li jippermettu li sistema distribwita tikseb kunsens garantit.

B'mod aktar formali, nistgħu niddefinixxu algoritmu ta 'kunsens (jew sempliċiment algoritmu ta' kunsens) bħala ċerta funzjoni li tittrasferixxi sistema distribwita minn stat A għal stat B. Barra minn hekk, dan l-istat huwa aċċettat min-nodi kollha, u n-nodi kollha jistgħu jikkonfermawh. Kif jirriżulta, dan il-kompitu mhu xejn daqshekk trivjali kif jidher mal-ewwel daqqa t'għajn.

Proprjetajiet tal-Algoritmu tal-Kunsens

L-algoritmu tal-kunsens għandu jkollu tliet proprjetajiet sabiex is-sistema tkompli teżisti u jkollha xi progress biex timxi minn stat għal stat:

Ftehim – in-nodi kollha li joperaw b'mod korrett għandhom jieħdu l-istess valur (f'artikoli din il-proprjetà tissejjaħ ukoll proprjetà ta' sikurezza). In-nodi kollha li bħalissa qed jaħdmu (ma fallewx jew tilfu l-kuntatt mal-oħrajn) iridu jaslu għal ftehim u jaċċettaw xi valur komuni finali.
Huwa importanti li nifhmu hawnhekk li n-nodi fis-sistema distribwita li qed nikkunsidraw iridu jaqblu. Jiġifieri, issa qed nitkellmu dwar sistemi li fihom xi ħaġa tista 'sempliċement tfalli (per eżempju, xi nodu jonqos), iżda f'din is-sistema definittivament m'hemm l-ebda nodi li jaħdmu apposta kontra oħrajn (il-kompitu tal-ġenerali Biżantini). Minħabba din il-proprjetà, is-sistema tibqa’ konsistenti.
integrità — jekk in-nodi kollha li jaħdmu sew joffru l-istess valur v, li jfisser li kull nodu li jopera b'mod korrett għandu jaċċetta dan il-valur v.
terminazzjoni – in-nodi kollha li joperaw b'mod korrett eventwalment se jieħdu ċertu valur (proprjetà tal-ħajja), li jippermetti li l-algoritmu jagħmel progress fis-sistema. Kull nodu li jopera b'mod korrett illum jew għada għandu jaċċetta l-valur finali u jikkonfermah: "Għalija, dan il-valur huwa minnu, naqbel mas-sistema kollha."

Eżempju ta' kif jaħdem l-algoritmu tal-kunsens

Filwaqt li l-proprjetajiet tal-algoritmu jistgħu ma jkunux kompletament ċari. Għalhekk, aħna se nuru b'eżempju minn liema stadji jgħaddi l-algoritmu ta' kunsens l-aktar sempliċi f'sistema b'mudell ta' messaġġi sinkroniċi, li fiha n-nodi kollha jiffunzjonaw kif mistenni, il-messaġġi ma jintilfux u xejn ma jinkiser (dan verament jiġri?).

Kollox jibda bi proposta taż-żwieġ (Proponi). Ejja nassumu li klijent konness ma 'node imsejjaħ "Node 1" u beda tranżazzjoni, jgħaddi valur ġdid lin-node - O. Minn issa 'l quddiem, se nsejħu "Node 1" biex tipproponi. Bħala proponent, "Node 1" issa għandu jinnotifika lis-sistema kollha li għandha data ġdida, u jibgħat messaġġi lin-nodi l-oħra kollha: "Ara! It-tifsira “O” waslet għandi u rrid niktebha! Jekk jogħġbok ikkonferma li se tirreġistra wkoll “O” fil-log tiegħek.”
L-istadju li jmiss huwa l-votazzjoni għall-valur propost (Votazzjoni). Għal xiex? Jista 'jiġri li nodi oħra rċevew informazzjoni aktar reċenti, u għandhom data dwar l-istess tranżazzjoni.

Meta n-node "Node 1" jibgħat il-proposta tiegħu, in-nodi l-oħra jiċċekkjaw ir-reġistri tagħhom għad-dejta dwar dan l-avveniment. Jekk ma jkunx hemm kontradizzjonijiet, in-nodi jħabbru: "Iva, m'għandi l-ebda data oħra għal dan l-avveniment. Il-valur "O" huwa l-aħħar informazzjoni li ħaqqna."
Fi kwalunkwe każ ieħor, in-nodi jistgħu jirrispondu għal “Node 1”: “Isma’! Għandi dejta aktar riċenti dwar din it-tranżazzjoni. Mhux 'O', imma xi ħaġa aħjar."
Fl-istadju tal-votazzjoni, in-nodi jaslu għal deċiżjoni: jew kollha jaċċettaw l-istess valur, jew wieħed minnhom jivvota kontra, li jindika li għandu data aktar reċenti.
Jekk ir-rawnd tal-votazzjoni kien suċċess u kulħadd kien favur, allura s-sistema timxi għal stadju ġdid - Taċċetta l-valur. "Node 1" jiġbor it-tweġibiet kollha minn nodi oħra u jirrapporta: "Kulħadd qabel dwar il-valur "O"! Issa niddikjara uffiċjalment li "O" hija t-tifsira l-ġdida tagħna, l-istess għal kulħadd! Iktebha fil-ktieb żgħir tiegħek, tinsiex. Iktebha fil-ġurnal tiegħek!”
In-nodi li fadal jibagħtu konferma (Aċċettati) li tniżżlu l-valur "O"; xejn ġdid ma wasal matul dan iż-żmien (tip ta 'commit f'żewġ fażijiet). Wara dan l-avveniment sinifikanti, aħna nikkunsidraw li t-tranżazzjoni mqassma tlestiet.

Għalhekk, l-algoritmu ta 'kunsens f'każ sempliċi jikkonsisti f'erba' passi: tipproponi, tivvota (votazzjoni), taċċetta (aċċetta), tikkonferma l-aċċettazzjoni (aċċettata).

Jekk f'xi pass ma stajniex nilħqu ftehim, allura l-algoritmu jerġa 'jibda, b'kont meħud tal-informazzjoni pprovduta min-nodi li rrifjutaw li jikkonfermaw il-valur propost.

Algoritmu ta' kunsens f'sistema asinkronika

Qabel dan, kollox kien bla xkiel, għax konna nitkellmu dwar mudell ta 'messaġġi sinkroniċi. Imma nafu li fid-dinja moderna mdorrijin nagħmlu kollox b’mod asinkroniku. Kif jaħdem algoritmu simili f'sistema b'mudell ta' messaġġi asinkronu, fejn nemmnu li l-ħin ta' stennija għal tweġiba minn node jista' jkun twil b'mod arbitrarju (mill-mod, il-falliment ta' nodu jista' jitqies ukoll bħala eżempju meta node jista' jirrispondi għal żmien twil b'mod arbitrarju).

Issa li nafu kif jaħdem l-algoritmu tal-kunsens fil-prinċipju, mistoqsija għal dawk il-qarrejja kurżittivi li għamluha s'issa: kemm nodi f'sistema ta 'N nodi b'mudell ta' messaġġ mhux sinkroniku jistgħu jonqsu sabiex is-sistema xorta tkun tista 'tilħaq kunsens?

It-tweġiba korretta u l-ġustifikazzjoni huma wara l-ispoiler.It-tweġiba korretta hija: 0. Jekk anki nodu wieħed f'sistema asinkronika jonqos, is-sistema ma tkunx tista' tilħaq kunsens. Din id-dikjarazzjoni hija ppruvata fit-teorema tal-FLP, magħrufa sew f’ċerti ċrieki (1985, Fischer, Lynch, Paterson, link għall-oriġinal fl-aħħar tal-artiklu): “L-impossibiltà li jinkiseb kunsens distribwit jekk mill-inqas nodu wieħed ifalli .”

Guys, allura għandna problema, aħna mdorrijin li kollox ikun asinkroniku. U hawn hu. Kif tkompli tgħix?

Konna biss nitkellmu dwar it-teorija, dwar il-matematika. Xi jfisser "ma jistax jintlaħaq kunsens", li jittraduċi minn lingwaġġ matematiku għal tagħna - inġinerija? Dan ifisser li "ma jistax dejjem jintlaħaq", i.e. Hemm każ li fih il-kunsens ma jistax jintlaħaq. X'tip ta' każ huwa dan?

Dan huwa eżattament il-ksur tal-proprjetà tal-ħajja deskritta hawn fuq. M'għandniex ftehim komuni, u s-sistema ma jistax ikollha progress (ma tistax titlesta fi żmien finit) fil-każ fejn ma jkollniex rispons min-nodi kollha. Għax f'sistema asinkronika m'għandna l-ebda ħin ta' rispons prevedibbli u ma nistgħux inkunu nafu jekk node ġġarrafx jew hux qed jieħu ħafna żmien biex jirrispondi.

Iżda fil-prattika nistgħu nsibu soluzzjoni. Ħalli l-algoritmu tagħna jkun jista 'jaħdem għal żmien twil f'każ ta' fallimenti (potenzjalment jista 'jaħdem b'mod indefinit). Iżda fil-biċċa l-kbira tas-sitwazzjonijiet, meta l-biċċa l-kbira tan-nodi qed jaħdmu b'mod korrett, ikollna progress fis-sistema.

Fil-prattika, nittrattaw mudelli ta 'komunikazzjoni parzjalment sinkroniċi. Is-sinkronija parzjali hija mifhuma kif ġej: fil-każ ġenerali, għandna mudell mhux sinkroniku, iżda ċertu kunċett ta '"ħin ta' stabbilizzazzjoni globali" ta 'ċertu punt fiż-żmien huwa introdott formalment.

Dan il-mument fiż-żmien jista’ ma jasal għal xi żmien, imma jrid jiġi jum wieħed. L-arloġġ ta 'l-allarm virtwali ser idur, u minn dak il-mument nistgħu nbassru d-delta tal-ħin li għalih se jaslu l-messaġġi. Minn dan il-mument 'il quddiem, is-sistema ddawwar minn asinkronu għal sinkroniku. Fil-prattika, nittrattaw preċiżament sistemi bħal dawn.

L-algoritmu Paxos isolvi problemi ta' kunsens

Paxos hija familja ta 'algoritmi li jsolvu l-problema ta' kunsens għal sistemi parzjalment sinkroniċi, soġġetti għall-possibbiltà li xi nodi jistgħu jfallu. L-awtur ta 'Paxos huwa Leslie Lampport. Huwa ppropona prova formali tal-eżistenza u l-korrettezza tal-algoritmu fl-1989.

Iżda l-prova rriżulta li kienet 'il bogħod milli trivjali. L-ewwel pubblikazzjoni ġiet rilaxxata biss fl-1998 (33 paġna) li tiddeskrivi l-algoritmu. Kif irriżulta, kien estremament diffiċli li wieħed jifhem, u fl-2001 ġiet ippubblikata spjegazzjoni tal-artiklu, li ħadet 14-il paġna. Il-volum tal-pubblikazzjonijiet jingħata sabiex juri li fil-fatt il-problema tal-kunsens mhi xejn sempliċi, u wara algoritmi bħal dawn hemm ammont kbir ta 'xogħol mill-aktar nies intelliġenti.

Huwa interessanti li Leslie Lamport stess innota fit-taħdita tiegħu li fit-tieni artiklu ta’ spjegazzjoni hemm stqarrija waħda, linja waħda (ma speċifikax liema waħda), li tista’ tiġi interpretata b’modi differenti. U minħabba dan, numru kbir ta 'implimentazzjonijiet moderni ta' Paxos ma jaħdmux kompletament b'mod korrett.

Analiżi dettaljata tax-xogħol ta 'Paxos tieħu aktar minn artiklu wieħed, għalhekk se nipprova nwassal fil-qosor ħafna l-idea ewlenija tal-algoritmu. Fil-links fl-aħħar tal-artiklu tiegħi se ssib materjali għal aktar għadis f'dan is-suġġett.

Rwoli f'Paxos

L-algoritmu Paxos għandu kunċett ta 'rwoli. Ejja nikkunsidraw tlieta ewlenin (hemm modifiki bi rwoli addizzjonali):

Proponenti (it-termini jistgħu jintużaw ukoll: mexxejja jew koordinaturi). Dawn huma l-guys li jitgħallmu dwar xi valur ġdid mill-utent u jieħdu r-rwol ta 'mexxej. Il-kompitu tagħhom huwa li jniedu sensiela ta' proposti għal valur ġdid u jikkoordinaw aktar azzjonijiet tan-nodi. Barra minn hekk, Paxos jippermetti l-preżenza ta 'diversi mexxejja f'ċerti sitwazzjonijiet.
Aċċettaturi (Votanti). Dawn huma nodi li jivvutaw biex jaċċettaw jew jirrifjutaw valur partikolari. Ir-rwol tagħhom huwa importanti ħafna, minħabba li d-deċiżjoni tiddependi minnhom: liema stat se tmur (jew le) is-sistema wara l-istadju li jmiss tal-algoritmu tal-kunsens.
Studenti. Nodi li sempliċement jaċċettaw u jiktbu l-valur il-ġdid aċċettat meta l-istat tas-sistema jkun inbidel. Huma ma jieħdux deċiżjonijiet, huma biss jirċievu d-dejta u jistgħu jagħtuha lill-utent aħħari.

Nodu wieħed jista 'jgħaqqad diversi rwoli f'sitwazzjonijiet differenti.

Il-kunċett ta' quorum

Nassumu li għandna sistema ta N nodi U minnhom il-massimu F nodi jistgħu jfallu. Jekk in-nodi F ifallu, allura jrid ikollna mill-inqas 2F+1 nodi li jaċċettaw.

Dan huwa meħtieġ sabiex dejjem ikollna l-maġġoranza, anke fl-agħar sitwazzjoni, ta 'nodi "tajbin" li jaħdmu b'mod korrett. Jiġifieri F+1 "tajba" nodi li qablu, u l-valur finali se jiġu aċċettati. Inkella, jista’ jkun hemm sitwazzjoni fejn il-gruppi lokali differenti tagħna jieħdu tifsiriet differenti u ma jistgħux jaqblu bejniethom. Għalhekk, għandna bżonn maġġoranza assoluta biex nirbħu l-vot.

L-idea ġenerali ta 'kif jaħdem l-algoritmu ta' kunsens Paxos

L-algoritmu Paxos jinvolvi żewġ fażijiet kbar, li min-naħa tagħhom huma maqsuma f'żewġ passi kull wieħed:

Fażi 1a: Ipprepara. Matul il-fażi ta’ preparazzjoni, il-mexxej (proponent) jinforma lin-nodi kollha: “Qed nibdew fażi ġdida ta’ votazzjoni. Għandna rawnd ġdid. In-numru ta' dan ir-rawnd huwa n. Issa se nibdew nivvutaw.” Għalissa, sempliċement tirrapporta l-bidu ta 'ċiklu ġdid, iżda ma tirrapportax valur ġdid. Il-kompitu ta 'dan l-istadju huwa li jinbeda rawnd ġdid u jinforma lil kulħadd bin-numru uniku tiegħu. In-numru tond huwa importanti, għandu jkun valur akbar min-numri kollha tal-votazzjoni preċedenti mill-mexxejja kollha preċedenti. Minħabba li huwa grazzi għan-numru tond li nodi oħra fis-sistema se jifhmu kemm hi riċenti d-dejta tal-mexxej. Huwa probabbli li nodi oħra diġà għandhom riżultati tal-votazzjoni minn rawnds ħafna aktar tard u sempliċement jgħidu lill-mexxej li huwa lura ż-żminijiet.
Fażi 1b: Wegħda. Meta n-nodi li jaċċettaw irċevew in-numru tal-istadju tal-votazzjoni l-ġdid, żewġ riżultati huma possibbli:
- In-numru n tal-vot il-ġdid huwa akbar min-numru ta' kwalunkwe vot preċedenti li fih ipparteċipa l-aċċettatur. Imbagħad l-aċċettatur jibgħat wegħda lill-mexxej li mhux se jipparteċipa f’aktar voti b’numru inqas minn n. Jekk l-aċċettatur diġà ivvota għal xi ħaġa (jiġifieri diġà aċċetta xi valur fit-tieni fażi), allura jehmeż il-valur aċċettat u n-numru tal-vot li fih ipparteċipa mal-wegħda tiegħu.
- Inkella, jekk l-aċċettatur diġà jaf dwar il-vot b'numru ogħla, jista 'sempliċement jinjora l-pass tal-preparazzjoni u ma jirrispondix lill-mexxej.
Fażi 2a: Aċċetta. Il-mexxej jeħtieġ li jistenna tweġiba mill-kworum (il-maġġoranza tan-nodi fis-sistema) u, jekk jasal in-numru meħtieġ ta 'tweġibiet, allura għandu żewġ għażliet għall-iżvilupp ta' avvenimenti:
- Uħud mill-aċċettaturi bagħtu valuri li kienu diġà vvutaw għalihom. F'dan il-każ, il-mexxej jagħżel il-valur mill-vot bin-numru massimu. Ejja nsejħu dan il-valur x, u jibgħat messaġġ lin-nodi kollha bħal: "Aċċetta (n, x)", fejn l-ewwel valur huwa n-numru tal-votazzjoni mill-pass Propponi tiegħu stess, u t-tieni valur huwa dak li kulħadd ġabar għalih, i.e. il-valur li fil-fatt nivvutaw għalih.
- Jekk ħadd mill-aċċettaturi ma bagħat xi valuri, iżda sempliċement wegħdu li jivvotaw f'dan ir-rawnd, il-mexxej jista 'jistedinhom jivvutaw għall-valur tagħhom, il-valur li għalih sar mexxej fl-ewwel post. Ejja nsejħulha y. Tibgħat messaġġ lin-nodi kollha bħal: "Aċċetta (n, y)", simili għar-riżultat preċedenti.
Fażi 2b: Aċċettata. Barra minn hekk, in-nodi li jaċċettaw, malli jirċievu l-messaġġ "Aċċetta (...)" mingħand il-mexxej, jaqblu miegħu (ibgħat konferma lin-nodi kollha li jaqblu mal-valur il-ġdid) biss jekk ma wegħdux xi (oħrajn) ) mexxej biex jipparteċipa fil-votazzjoni b’numru tond n’> n, inkella jinjoraw it-talba għall-konferma.
Jekk il-maġġoranza tan-nodi wieġbu lill-mexxej, u kollha kemm huma kkonfermaw il-valur il-ġdid, allura l-valur il-ġdid jitqies bħala aċċettat. Ħura! Jekk il-maġġoranza ma tintlaħaqx jew ikun hemm nodi li rrifjutaw li jaċċettaw il-valur il-ġdid, allura kollox jibda mill-ġdid.

Dan huwa kif jaħdem l-algoritmu Paxos. Kull wieħed minn dawn l-istadji għandu ħafna irqaq, aħna prattikament ma kkunsidrawx diversi tipi ta 'fallimenti, problemi ta' mexxejja multipli u ħafna aktar, iżda l-iskop ta 'dan l-artikolu huwa biss li jintroduċi lill-qarrej fid-dinja tal-kompjuters distribwiti f'livell għoli.

Ta 'min jinnota wkoll li Paxos mhuwiex l-uniku wieħed tat-tip tiegħu, hemm algoritmi oħra, pereżempju, Raft, iżda dan huwa suġġett għal artiklu ieħor.