Pra, le të imagjinojmë. Ka 5 mace të mbyllura në dhomë dhe për të shkuar të zgjojnë pronarin duhet të bien dakord të gjitha për këtë mes tyre, sepse mund të hapin derën vetëm me pesë prej tyre të mbështetur në të. Nëse njëra nga macet është macja e Schrödinger-it dhe macet e tjera nuk e dinë për vendimin e tij, lind pyetja: "Si mund ta bëjnë atë?"
Në këtë artikull, unë do t'ju tregoj me terma të thjeshtë për komponentin teorik të botës së sistemeve të shpërndara dhe parimet e funksionimit të tyre. Unë gjithashtu do të shqyrtoj sipërfaqësisht idenë kryesore që qëndron në themel të Paxos.
Kur zhvilluesit përdorin infrastruktura cloud, baza të të dhënave të ndryshme dhe punojnë në grupe të një numri të madh nyjesh, ata janë të sigurt se të dhënat do të jenë të plota, të sigurta dhe gjithmonë të disponueshme. Por ku janë garancitë?
Në thelb, garancitë që kemi janë garanci nga furnizuesit. Ato përshkruhen në dokumentacion si më poshtë: "Ky shërbim është mjaft i besueshëm, ka një SLA të dhënë, mos u shqetësoni, gjithçka do të funksionojë në mënyrë të shpërndarë siç prisni."
Ne priremi të besojmë në më të mirën, sepse djemtë e zgjuar nga kompanitë e mëdha na siguruan se gjithçka do të jetë mirë. Ne nuk shtrojmë pyetjen: pse, në fakt, kjo mund të funksionojë fare? A ka ndonjë justifikim formal për funksionimin korrekt të sistemeve të tilla?
Kohët e fundit shkova në dhe u frymëzua shumë nga kjo temë. Ligjëratat në shkollë ishin më shumë si klasa llogaritjeje sesa diçka që lidhej me sistemet kompjuterike. Por pikërisht kështu u vërtetuan njëherësh algoritmet më të rëndësishme që përdorim çdo ditë, pa e ditur as këtë.
Shumica e sistemeve moderne të shpërndara përdorin algoritmin e konsensusit Paxos dhe modifikimet e tij të ndryshme. Gjëja më interesante është se vlefshmëria dhe, në parim, vetë mundësia e ekzistencës së këtij algoritmi mund të vërtetohet thjesht me një stilolaps dhe një letër. Në praktikë, algoritmi përdoret në sisteme të mëdha që funksionojnë në një numër të madh nyjesh në re.
Një ilustrim i lehtë i asaj që do të diskutohet më pas: detyra e dy gjeneralëveLe të hedhim një vështrim për një ngrohje .
Ne kemi dy ushtri - të kuqe dhe të bardhë. Trupat e bardhë janë vendosur në qytetin e rrethuar. Trupat e kuqe të udhëhequra nga gjeneralët A1 dhe A2 ndodhen në dy anët e qytetit. Detyra e flokëkuqve është të sulmojnë qytetin e bardhë dhe të fitojnë. Sidoqoftë, ushtria e secilit gjeneral të kuq individualisht është më e vogël se ushtria e bardhë.
Kushtet e fitores për të kuqtë: të dy gjeneralët duhet të sulmojnë në të njëjtën kohë për të pasur një avantazh numerik ndaj bardhezinjve. Për ta bërë këtë, gjeneralët A1 dhe A2 duhet të arrijnë një marrëveshje me njëri-tjetrin. Nëse të gjithë sulmojnë veçmas, flokëkuqtë do të humbasin.
Për të arritur një marrëveshje, gjeneralët A1 dhe A2 mund t'i dërgojnë lajmëtarë njëri-tjetrit përmes territorit të qytetit të bardhë. Lajmëtari mund të arrijë me sukses një gjeneral aleat ose mund të kapet nga armiku. Pyetje: a ka një sekuencë të tillë komunikimi midis gjeneralëve flokëkuq (sekuenca e dërgimit të lajmëtarëve nga A1 në A2 dhe anasjelltas nga A2 në A1), në të cilën ata janë të garantuar të bien dakord për një sulm në orën X. Këtu, garancitë nënkuptojnë që të dy gjeneralët do të kenë konfirmim të qartë se një aleat (një gjeneral tjetër) do të sulmojë patjetër në kohën e caktuar X.
Supozoni se A1 dërgon një lajmëtar në A2 me mesazhin: "Le të sulmojmë sot në mesnatë!" Gjenerali A1 nuk mund të sulmojë pa konfirmimin e gjeneralit A2. Nëse lajmëtari nga A1 ka mbërritur, atëherë gjenerali A2 dërgon konfirmimin me mesazhin: "Po, le t'i vrasim të bardhët sot". Por tani gjenerali A2 nuk e di nëse i dërguari i tij ka mbërritur apo jo, ai nuk ka asnjë garanci nëse sulmi do të jetë i njëkohshëm. Tani gjenerali A2 përsëri ka nevojë për konfirmim.
Nëse përshkruajmë më tej komunikimin e tyre, bëhet e qartë se pa marrë parasysh sa cikle shkëmbimi mesazhesh ka, nuk ka asnjë mënyrë për të garantuar që të dy gjeneralët të kenë marrë mesazhet e tyre (duke supozuar se secili nga mesazherët mund të përgjohet).
Problemi i Dy gjeneralëve është një ilustrim i mrekullueshëm i një sistemi shumë të thjeshtë të shpërndarë ku ka dy nyje me komunikim jo të besueshëm. Kjo do të thotë që ne nuk kemi një garanci 100% që ato janë të sinkronizuara. Probleme të ngjashme diskutohen vetëm në një shkallë më të gjerë më vonë në artikull.
Ne prezantojmë konceptin e sistemeve të shpërndara
Një sistem i shpërndarë është një grup kompjuterësh (në tekstin e mëtejmë do t'i quajmë nyje) që mund të shkëmbejnë mesazhe. Çdo nyje individuale është një lloj entiteti autonom. Një nyje mund të përpunojë detyra vetë, por për të komunikuar me nyjet e tjera, ajo duhet të dërgojë dhe marrë mesazhe.
Si zbatohen saktësisht mesazhet, cilat protokolle përdoren - kjo nuk është me interes për ne në këtë kontekst. Është e rëndësishme që nyjet e një sistemi të shpërndarë të mund të shkëmbejnë të dhëna me njëri-tjetrin duke dërguar mesazhe.
Vetë përkufizimi nuk duket shumë i komplikuar, por duhet të kemi parasysh që një sistem i shpërndarë ka një sërë atributesh që do të jenë të rëndësishme për ne.
Atributet e sistemeve të shpërndara
- concurrency – mundësia e ndodhjes së ngjarjeve të njëkohshme ose të njëkohshme në sistem. Për më tepër, ne do t'i konsiderojmë ngjarjet që ndodhin në dy nyje të ndryshme si potencialisht të njëkohshme për sa kohë që nuk kemi një rend të qartë të ndodhjes së këtyre ngjarjeve. Por, si rregull, ne nuk e kemi atë.
- Nuk ka orë globale. Nuk kemi një renditje të qartë të ngjarjeve për shkak të mungesës së një ore globale. Në botën e zakonshme të njerëzve, ne jemi mësuar me faktin se kemi orë dhe kohë absolutisht. Çdo gjë ndryshon kur bëhet fjalë për sistemet e shpërndara. Edhe orët atomike ultra të sakta kanë lëvizur, dhe mund të ketë situata ku ne nuk mund të dallojmë se cila nga dy ngjarjet ka ndodhur e para. Prandaj, nuk mund të mbështetemi as në kohë.
- Dështimi i pavarur i nyjeve të sistemit. Ekziston një problem tjetër: diçka mund të shkojë keq thjesht sepse nyjet tona nuk zgjasin përgjithmonë. Hard disku mund të dështojë, makina virtuale në re mund të rindizet, rrjeti mund të pulsojë dhe mesazhet do të humbasin. Për më tepër, mund të ketë situata ku nyjet funksionojnë, por në të njëjtën kohë punojnë kundër sistemit. Klasa e fundit e problemeve madje mori një emër të veçantë: problem . Shembulli më popullor i një sistemi të shpërndarë me këtë problem është Blockchain. Por sot ne nuk do ta konsiderojmë këtë klasë të veçantë problemesh. Ne do të jemi të interesuar për situatat në të cilat thjesht një ose më shumë nyje mund të dështojnë.
- Modelet e komunikimit (modelet e mesazheve) ndërmjet nyjeve. Ne kemi vendosur tashmë që nyjet komunikojnë duke shkëmbyer mesazhe. Ekzistojnë dy modele të njohura të mesazheve: sinkron dhe asinkron.
Modelet e komunikimit ndërmjet nyjeve në sistemet e shpërndara
Modeli sinkron – ne e dimë me siguri se ekziston një delta e kufizuar kohore gjatë së cilës një mesazh garantohet të arrijë nga një nyje në tjetrën. Nëse kjo kohë ka kaluar dhe mesazhi nuk ka mbërritur, mund të themi me siguri se nyja ka dështuar. Në këtë model kemi kohë pritjeje të parashikueshme.
Modeli asinkron – në modelet asinkrone konsiderojmë se koha e pritjes është e fundme, por nuk ekziston një delta e tillë kohore pas së cilës mund të garantojmë se nyja ka dështuar. Ato. Koha e pritjes për një mesazh nga një nyje mund të jetë arbitrarisht e gjatë. Ky është një përkufizim i rëndësishëm, dhe ne do të flasim për të më tej.
Koncepti i konsensusit në sistemet e shpërndara
Para se të përcaktojmë zyrtarisht konceptin e konsensusit, le të shqyrtojmë një shembull të një situate ku na nevojitet, domethënë - Replikimi i makinës shtetërore.
Ne kemi disa regjistra të shpërndarë. Ne dëshirojmë që ai të jetë konsistent dhe të përmbajë të dhëna identike për të gjitha nyjet e sistemit të shpërndarë. Kur një nga nyjet mëson një vlerë të re që do të shkruajë në regjistër, detyra e tij bëhet të ofrojë këtë vlerë për të gjitha nyjet e tjera në mënyrë që regjistri të përditësohet në të gjitha nyjet dhe sistemi të kalojë në një gjendje të re konsistente. Në këtë rast, është e rëndësishme që nyjet të bien dakord mes tyre: të gjitha nyjet bien dakord që vlera e re e propozuar është e saktë, të gjitha nyjet e pranojnë këtë vlerë dhe vetëm në këtë rast të gjithë mund të shkruajnë vlerën e re në regjistër.
Me fjalë të tjera: asnjë nga nyjet nuk kundërshtoi se kishte informacion më të rëndësishëm dhe vlera e propozuar ishte e pasaktë. Marrëveshja midis nyjeve dhe marrëveshja për një vlerë të vetme të pranuar të saktë është konsensus në një sistem të shpërndarë. Më pas, do të flasim për algoritme që lejojnë që një sistem i shpërndarë të garantohet të arrijë konsensus.
Më formalisht, ne mund të përkufizojmë një algoritëm konsensusi (ose thjesht një algoritëm konsensusi) si një funksion të caktuar që transferon një sistem të shpërndarë nga gjendja A në gjendjen B. Për më tepër, kjo gjendje pranohet nga të gjitha nyjet dhe të gjitha nyjet mund ta konfirmojnë atë. Siç rezulton, kjo detyrë nuk është aspak aq e parëndësishme sa duket në shikim të parë.
Vetitë e Algoritmit të Konsensusit
Algoritmi i konsensusit duhet të ketë tre veti në mënyrë që sistemi të vazhdojë të ekzistojë dhe të ketë njëfarë progresi në lëvizjen nga një gjendje në tjetrën:
- Marrëveshje – të gjitha nyjet që funksionojnë në mënyrë korrekte duhet të kenë të njëjtën vlerë (në artikuj kjo veti referohet edhe si veti e sigurisë). Të gjitha nyjet që janë duke funksionuar aktualisht (nuk kanë dështuar ose humbur kontaktin me të tjerët) duhet të arrijnë një marrëveshje dhe të pranojnë një vlerë përfundimtare të përbashkët.
Është e rëndësishme të kuptohet këtu se nyjet në sistemin e shpërndarë që po shqyrtojmë duan të bien dakord. Kjo do të thotë, ne tani po flasim për sisteme në të cilat diçka thjesht mund të dështojë (për shembull, disa nyje dështojnë), por në këtë sistem nuk ka definitivisht nyje që punojnë qëllimisht kundër të tjerëve (detyra e gjeneralëve bizantinë). Për shkak të kësaj veçorie, sistemi mbetet i qëndrueshëm.
- ndershmëri — nëse të gjitha nyjet që punojnë siç duhet ofrojnë të njëjtën vlerë v, që do të thotë se çdo nyje që funksionon saktë duhet ta pranojë këtë vlerë v.
- Ndërprerja – të gjitha nyjet që funksionojnë në mënyrë korrekte përfundimisht do të marrin një vlerë të caktuar (veti të gjallërisë), e cila lejon algoritmin të përparojë në sistem. Çdo nyje individuale që funksionon saktë duhet herët a vonë të pranojë vlerën përfundimtare dhe ta konfirmojë atë: "Për mua, kjo vlerë është e vërtetë, unë jam dakord me të gjithë sistemin."
Një shembull se si funksionon algoritmi i konsensusit
Ndërsa vetitë e algoritmit mund të mos jenë plotësisht të qarta. Prandaj, do të ilustrojmë me një shembull se në cilat faza kalon algoritmi më i thjeshtë i konsensusit në një sistem me një model mesazhesh sinkron, në të cilin të gjitha nyjet funksionojnë siç pritej, mesazhet nuk humbasin dhe asgjë nuk prishet (a ndodh vërtet kjo?).
- Gjithçka fillon me një propozim martese (Propozim). Le të supozojmë se një klient është lidhur me një nyje të quajtur "Nyja 1" dhe ka filluar një transaksion, duke i kaluar një vlerë të re nyjes - O. Që tani e tutje, ne do të quajmë "Nyja 1" propozuesi. Si propozues, "Nyja 1" tani duhet të njoftojë të gjithë sistemin se ka të dhëna të freskëta dhe u dërgon mesazhe të gjitha nyjeve të tjera: "Shiko! Kuptimi "O" më erdhi dhe dua ta shkruaj! Ju lutemi konfirmoni se do të regjistroni gjithashtu "O" në regjistrin tuaj."
- Faza tjetër është votimi për vlerën e propozuar (Votimi). Për çfarë është? Mund të ndodhë që nyjet e tjera të kenë marrë informacion më të fundit dhe të kenë të dhëna për të njëjtin transaksion.
Kur nyja "Nyja 1" dërgon propozimin e saj, nyjet e tjera kontrollojnë regjistrat e tyre për të dhëna për këtë ngjarje. Nëse nuk ka kontradikta, nyjet njoftojnë: “Po, nuk kam të dhëna të tjera për këtë ngjarje. Vlera "O" është informacioni më i fundit që meritojmë."Në çdo rast tjetër, nyjet mund t'i përgjigjen "Nyjes 1": "Dëgjo! Unë kam të dhëna më të fundit për këtë transaksion. Jo 'O', por diçka më e mirë."
Në fazën e votimit, nyjet marrin një vendim: ose të gjithë pranojnë të njëjtën vlerë, ose njëri prej tyre voton kundër, duke treguar se ai ka të dhëna më të fundit.
- Nëse raundi i votimit ishte i suksesshëm dhe të gjithë ishin pro, atëherë sistemi kalon në një fazë të re - Pranimi i vlerës. "Nyja 1" mbledh të gjitha përgjigjet nga nyjet e tjera dhe raporton: "Të gjithë ranë dakord për vlerën "O"! Tani deklaroj zyrtarisht se "O" është kuptimi ynë i ri, i njëjtë për të gjithë! Shkruajeni atë në librin tuaj të vogël, mos harroni. Shkruajeni atë në regjistrin tuaj!”
- Nyjet e mbetura dërgojnë konfirmimin (Pranuar) se kanë shkruar vlerën "O"; asgjë e re nuk ka mbërritur gjatë kësaj kohe (një lloj angazhimi dyfazor). Pas kësaj ngjarje të rëndësishme, ne konsiderojmë se transaksioni i shpërndarë ka përfunduar.
Kështu, algoritmi i konsensusit në një rast të thjeshtë përbëhet nga katër hapa: propozoni, votoni (votoni), pranoni (pranoni), konfirmoni pranimin (pranoni).
Nëse në një hap nuk ishim në gjendje të arrinim marrëveshje, atëherë algoritmi fillon përsëri, duke marrë parasysh informacionin e dhënë nga nyjet që refuzuan të konfirmonin vlerën e propozuar.
Algoritmi i konsensusit në një sistem asinkron
Para kësaj, gjithçka ishte e qetë, sepse ne po flisnim për një model të mesazheve sinkron. Por ne e dimë se në botën moderne jemi mësuar të bëjmë gjithçka në mënyrë asinkrone. Si funksionon një algoritëm i ngjashëm në një sistem me një model mesazhesh asinkron, ku ne besojmë se koha e pritjes për një përgjigje nga një nyje mund të jetë arbitrarisht e gjatë (nga rruga, dështimi i një nyje mund të konsiderohet gjithashtu si një shembull kur një nyje mund të përgjigjet për një kohë arbitrare të gjatë).
Tani që ne e dimë se si funksionon në parim algoritmi i konsensusit, një pyetje për ata lexues kureshtarë që kanë arritur deri këtu: sa nyje në një sistem prej N nyjesh me një model mesazhi asinkron mund të dështojnë në mënyrë që sistemi të arrijë ende konsensus?
Përgjigja dhe arsyetimi i saktë janë prapa spoilerit.Përgjigja e saktë është: 0. Nëse edhe një nyje në një sistem asinkron dështon, sistemi nuk do të jetë në gjendje të arrijë konsensus. Ky pohim vërtetohet në teoremën FLP, e njohur në qarqe të caktuara (1985, Fischer, Lynch, Paterson, lidhje me origjinalin në fund të artikullit): “Pamundësia e arritjes së një konsensusi të shpërndarë nëse të paktën një nyje dështon. .
Djema, atëherë kemi një problem, jemi mësuar që gjithçka të jetë asinkrone. Dhe ja ku është. Si të vazhdoni të jetoni?
Ne po flisnim vetëm për teorinë, për matematikën. Çfarë do të thotë "konsensusi nuk mund të arrihet", duke përkthyer nga gjuha matematikore në tonën - inxhinieri? Kjo do të thotë se "nuk mund të arrihet gjithmonë", d.m.th. Ekziston një rast në të cilin konsensusi nuk arrihet. Çfarë lloj rasti është ky?
Ky është pikërisht cenimi i pasurisë së gjallërisë të përshkruar më sipër. Ne nuk kemi një marrëveshje të përbashkët dhe sistemi nuk mund të ketë progres (nuk mund të përfundojë në një kohë të caktuar) në rastin kur nuk kemi një përgjigje nga të gjitha nyjet. Sepse në një sistem asinkron, ne nuk kemi kohë të parashikueshme përgjigjeje dhe nuk mund të dimë nëse një nyje është rrëzuar ose thjesht kërkon shumë kohë për t'u përgjigjur.
Por në praktikë mund të gjejmë një zgjidhje. Lëreni algoritmin tonë të jetë në gjendje të funksionojë për një kohë të gjatë në rast të dështimeve (potencialisht mund të funksionojë pafundësisht). Por në shumicën e situatave, kur shumica e nyjeve funksionojnë siç duhet, do të kemi përparim në sistem.
Në praktikë, ne kemi të bëjmë me modele të komunikimit pjesërisht sinkron. Sinkronia e pjesshme kuptohet si më poshtë: në rastin e përgjithshëm, kemi një model asinkron, por një koncept i caktuar i "kohës së stabilizimit global" të një pike të caktuar kohore prezantohet zyrtarisht.
Ky moment në kohë mund të mos vijë për një kohë të gjatë, por duhet të vijë një ditë. Ora virtuale e ziles do të bjerë, dhe nga ai moment ne mund të parashikojmë deltën kohore për të cilën do të mbërrijnë mesazhet. Nga ky moment, sistemi kthehet nga asinkron në sinkron. Në praktikë, ne kemi të bëjmë me sisteme të tilla.
Algoritmi Paxos zgjidh problemet e konsensusit
është një familje algoritmesh që zgjidhin problemin e konsensusit për sistemet pjesërisht sinkrone, në varësi të mundësisë që disa nyje mund të dështojnë. Autori i Paxos është . Ai propozoi një provë zyrtare të ekzistencës dhe korrektësisë së algoritmit në 1989.
Por prova doli të ishte aspak e parëndësishme. Publikimi i parë u botua vetëm në 1998 (33 faqe) duke përshkruar algoritmin. Siç doli, ishte jashtëzakonisht e vështirë për t'u kuptuar, dhe në vitin 2001 u botua një shpjegim i artikullit, i cili mori 14 faqe. Vëllimi i botimeve është dhënë për të treguar se në fakt problemi i konsensusit nuk është aspak i thjeshtë dhe pas algoritmeve të tilla qëndron një punë e madhe nga njerëzit më të zgjuar.
Është interesante që vetë Leslie Lamport vuri në dukje në leksionin e tij se në artikullin e dytë shpjegues ka një deklaratë, një rresht (ai nuk specifikoi se cilën), e cila mund të interpretohet në mënyra të ndryshme. Dhe për shkak të kësaj, një numër i madh i zbatimeve moderne të Paxos nuk funksionojnë plotësisht si duhet.
Një analizë e detajuar e punës së Paxos do të kërkonte më shumë se një artikull, kështu që unë do të përpiqem të përcjell shumë shkurt idenë kryesore të algoritmit. Në lidhjet në fund të artikullit tim do të gjeni materiale për zhytje të mëtejshme në këtë temë.
Rolet në Paxos
Algoritmi Paxos ka një koncept të roleve. Le të shqyrtojmë tre kryesore (ka modifikime me role shtesë):
- Propozuesit (mund të përdoren edhe termat: udhëheqës ose koordinatorë). Këta janë djemtë që mësojnë për disa vlera të reja nga përdoruesi dhe marrin rolin e udhëheqësit. Detyra e tyre është të lëshojnë një raund propozimesh për një vlerë të re dhe të koordinojnë veprimet e mëtejshme të nyjeve. Për më tepër, Paxos lejon praninë e disa liderëve në situata të caktuara.
- Pranuesit (Votuesit). Këto janë nyje që votojnë për të pranuar ose refuzuar një vlerë të caktuar. Roli i tyre është shumë i rëndësishëm, sepse vendimi varet prej tyre: në çfarë gjendje do të shkojë (ose jo) sistemi pas fazës tjetër të algoritmit të konsensusit.
- nxënësit. Nyjet që thjesht pranojnë dhe shkruajnë vlerën e re të pranuar kur gjendja e sistemit ka ndryshuar. Ata nuk marrin vendime, ata thjesht marrin të dhënat dhe mund t'ia japin përdoruesit përfundimtarë.
Një nyje mund të kombinojë disa role në situata të ndryshme.
Koncepti i kuorumit
Ne supozojmë se kemi një sistem të N nyjet Dhe prej tyre maksimumi F nyjet mund të dështojnë. Nëse nyjet F dështojnë, atëherë duhet të kemi të paktën 2F+1 nyjet pranuese.
Kjo është e nevojshme në mënyrë që të kemi gjithmonë shumicën, edhe në situatën më të keqe, të nyjeve "të mira" që funksionojnë siç duhet. Kjo eshte F+1 Nyjet "të mira" që ranë dakord, dhe vlera përfundimtare do të pranohet. Përndryshe, mund të ketë një situatë ku grupet tona të ndryshme lokale marrin kuptime të ndryshme dhe nuk mund të bien dakord mes tyre. Prandaj na duhet një shumicë absolute për të fituar votën.
Ideja e përgjithshme se si funksionon algoritmi i konsensusit të Paxos
Algoritmi Paxos përfshin dy faza të mëdha, të cilat nga ana e tyre ndahen në dy hapa secila:
- Faza 1a: Përgatitja. Gjatë fazës përgatitore, drejtuesi (propozuesi) informon të gjitha nyjet: “Po fillojmë një fazë të re votimi. Kemi një raund të ri. Numri i këtij raundi është n. Tani do të fillojmë të votojmë”. Për momentin, ai thjesht raporton fillimin e një cikli të ri, por nuk raporton një vlerë të re. Detyra e kësaj faze është të fillojë një raund të ri dhe të informojë të gjithë për numrin e tij unik. Numri i raundit është i rëndësishëm, ai duhet të jetë një vlerë më e madhe se të gjithë numrat e mëparshëm të votimit nga të gjithë drejtuesit e mëparshëm. Sepse është falë numrit të rrumbullakët që nyjet e tjera në sistem do të kuptojnë se sa të fundit janë të dhënat e liderit. Ka të ngjarë që nyjet e tjera të kenë tashmë rezultate votimi nga raundet e mëvonshme dhe thjesht do t'i tregojnë liderit se ai është prapa kohës.
- Faza 1b: Premtimi. Kur nyjet pranuese kanë marrë numrin e fazës së re të votimit, dy rezultate janë të mundshme:
- Numri n i votës së re është më i madh se numri i çdo votimi të mëparshëm në të cilin ka marrë pjesë pranuesi. Më pas, pranuesi i dërgon një premtim udhëheqësit se nuk do të marrë pjesë në asnjë votim më të vogël se n. Nëse pranuesi ka votuar tashmë për diçka (d.m.th., ai ka pranuar tashmë një vlerë në fazën e dytë), atëherë ai i bashkangjit premtimit të tij vlerën e pranuar dhe numrin e votës në të cilën ka marrë pjesë.
- Përndryshe, nëse pranuesi tashmë e di për votën me numër më të lartë, ai thjesht mund të injorojë hapin e përgatitjes dhe të mos i përgjigjet udhëheqësit.
- Faza 2a: Prano. Udhëheqësi duhet të presë për një përgjigje nga kuorumi (shumica e nyjeve në sistem) dhe, nëse merret numri i kërkuar i përgjigjeve, atëherë ai ka dy opsione për zhvillimin e ngjarjeve:
- Disa nga pranuesit dërguan vlera për të cilat ata kishin votuar tashmë. Në këtë rast, drejtuesi zgjedh vlerën nga vota me numrin maksimal. Le ta quajmë këtë vlerë x, dhe ajo u dërgon një mesazh të gjitha nyjeve si: "Prano (n, x)", ku vlera e parë është numri i votimit nga hapi i tij i Propozimit dhe vlera e dytë është ajo për të cilën u mblodhën të gjithë, dmth. vlera për të cilën ne votojmë.
- Nëse asnjë nga pranuesit nuk ka dërguar ndonjë vlerë, por thjesht ka premtuar se do të votojë në këtë raund, drejtuesi mund t'i ftojë ata të votojnë për vlerën e tyre, vlerën për të cilën ai u bë lider në radhë të parë. Le ta quajmë y. Ai u dërgon një mesazh të gjitha nyjeve si: "Prano (n, y)", i ngjashëm me rezultatin e mëparshëm.
- Faza 2b: Pranohet. Më tej, nyjet pranuese, me marrjen e mesazhit "Prano(...)" nga lideri, pajtohen me të (dërgoni konfirmim të gjitha nyjeve se pajtohen me vlerën e re) vetëm nëse nuk kanë premtuar disa (të tjera) ) drejtuesi të marrë pjesë në votim me numër të rrumbullakët n' > n, në të kundërt ata injorojnë kërkesën e konfirmimit.
Nëse shumica e nyjeve i janë përgjigjur liderit dhe të gjitha konfirmojnë vlerën e re, atëherë vlera e re konsiderohet e pranuar. Hora! Nëse shumica nuk arrihet ose ka nyje që refuzuan të pranojnë vlerën e re, atëherë gjithçka fillon nga e para.
Kështu funksionon algoritmi Paxos. Secila prej këtyre fazave ka shumë hollësi, praktikisht nuk kemi marrë në konsideratë lloje të ndryshme dështimesh, probleme të drejtuesve të shumtë dhe shumë më tepër, por qëllimi i këtij artikulli është vetëm të prezantojë lexuesin në botën e llogaritjes së shpërndarë në një nivel të lartë.
Vlen gjithashtu të theksohet se Paxos nuk është i vetmi në llojin e tij, ka algoritme të tjera, për shembull, , por kjo është një temë për një artikull tjetër.
Lidhje me materialet për studime të mëtejshme
Niveli fillestar:
- , Preethi Kasireddy, artikull në blog në Medium
- , Adi Kancherla, artikull në blog në Medium
- , Ittai Abraham, blog
- , Ittai Abraham, artikull në blog
Niveli i Leslie Lamport:
- , Fischer, Lynch dhe Paterson, punim kërkimor, 1985
- , Leslie Lamport, punim kërkimor, 1998
- , Leslie Lamport, punim kërkimor, 2001
Burimi: www.habr.com