Laten we ons eens voorstellen. Er zitten vijf katten opgesloten in de kamer, en om de eigenaar wakker te kunnen maken, moeten ze het allemaal onderling eens worden, omdat ze de deur alleen kunnen openen als ze met z'n vijven erop leunen. Als een van de katten de kat van Schrödinger is en de andere katten niet op de hoogte zijn van zijn beslissing, rijst de vraag: "Hoe kunnen ze dat doen?"
In dit artikel zal ik je in eenvoudige bewoordingen vertellen over de theoretische component van de wereld van gedistribueerde systemen en de principes van hun werking. Ik zal ook oppervlakkig de hoofdgedachte onderzoeken die ten grondslag ligt aan Paxos.
Wanneer ontwikkelaars cloudinfrastructuren en verschillende databases gebruiken en in clusters van een groot aantal knooppunten werken, hebben ze er vertrouwen in dat de gegevens compleet, veilig en altijd beschikbaar zullen zijn. Maar waar zijn de garanties?
De garanties die wij hebben zijn in essentie leveranciersgaranties. Ze worden in de documentatie als volgt beschreven: “Deze service is redelijk betrouwbaar, er is een bepaalde SLA, maak je geen zorgen, alles zal gedistribueerd werken zoals je verwacht.”
We zijn geneigd in het beste te geloven, omdat slimme jongens van grote bedrijven ons verzekerden dat alles goed komt. We stellen niet de vraag: waarom kan dit überhaupt werken? Bestaat er enige formele rechtvaardiging voor de correcte werking van dergelijke systemen?
Ik ben onlangs naar geweest en raakte erg geïnspireerd door dit onderwerp. Lezingen op school leken meer op rekenlessen dan op iets dat verband hield met computersystemen. Maar dit is precies hoe de belangrijkste algoritmen die we dagelijks gebruiken, zonder het zelfs maar te weten, ooit zijn bewezen.
De meeste moderne gedistribueerde systemen gebruiken het Paxos-consensusalgoritme en de verschillende aanpassingen ervan. Het coolste is dat de geldigheid en, in principe, de mogelijkheid van het bestaan van dit algoritme eenvoudigweg met pen en papier kan worden bewezen. In de praktijk wordt het algoritme gebruikt in grote systemen die op een groot aantal knooppunten in de cloud draaien.
Een lichte illustratie van wat hierna zal worden besproken: de taak van twee generaalsLaten we eens kijken voor een warming-up .
We hebben twee legers: rood en wit. Witte troepen zijn gelegerd in de belegerde stad. Rode troepen onder leiding van generaals A1 en A2 bevinden zich aan twee kanten van de stad. De taak van de roodharigen is om de witte stad aan te vallen en te winnen. Het leger van elke rode generaal afzonderlijk is echter kleiner dan het witte leger.
Overwinningsvoorwaarden voor de rode: beide generaals moeten tegelijkertijd aanvallen om een numeriek voordeel ten opzichte van de witten te hebben. Om dit te doen moeten de generaals A1 en A2 met elkaar tot overeenstemming komen. Als iedereen afzonderlijk aanvalt, verliezen de roodharigen.
Om tot overeenstemming te komen kunnen generaals A1 en A2 boodschappers naar elkaar sturen via het grondgebied van de witte stad. De boodschapper kan met succes een geallieerde generaal bereiken of kan worden onderschept door de vijand. Vraag: bestaat er zo'n reeks communicatie tussen de roodharige generaals (de reeks van het sturen van boodschappers van A1 naar A2 en vice versa van A2 naar A1), waarbij ze gegarandeerd overeenstemming bereiken over een aanval op uur X. Hier, Garanties betekenen dat beide generaals ondubbelzinnige bevestiging zullen hebben dat een bondgenoot (een andere generaal) definitief zal aanvallen op het afgesproken tijdstip X.
Stel dat A1 een boodschapper naar A2 stuurt met de boodschap: “Laten we vandaag om middernacht aanvallen!” Generaal A1 kan niet aanvallen zonder bevestiging van generaal A2. Als de boodschapper van A1 is gearriveerd, stuurt generaal A2 een bevestiging met de boodschap: “Ja, laten we vandaag de blanken vermoorden.” Maar nu Generaal A2 niet weet of zijn boodschapper is gearriveerd of niet, heeft hij geen garantie of de aanval gelijktijdig zal plaatsvinden. Nu heeft Generaal A2 opnieuw bevestiging nodig.
Als we hun communicatie verder beschrijven, wordt het duidelijk dat, ongeacht hoeveel berichtenuitwisselingscycli er zijn, er geen manier is om te garanderen dat beide generaals hun berichten hebben ontvangen (ervan uitgaande dat beide boodschappers kunnen worden onderschept).
Het Two Generals Problem is een goede illustratie van een heel eenvoudig gedistribueerd systeem met twee knooppunten met onbetrouwbare communicatie. Dit betekent dat we geen 100% garantie hebben dat ze gesynchroniseerd zijn. Soortgelijke problemen worden later in het artikel alleen op grotere schaal besproken.
We introduceren het concept van gedistribueerde systemen
Een gedistribueerd systeem is een groep computers (hierna zullen we ze knooppunten noemen) die berichten kunnen uitwisselen. Elk afzonderlijk knooppunt is een soort autonome entiteit. Een knooppunt kan zelfstandig taken verwerken, maar om met andere knooppunten te kunnen communiceren, moet het berichten verzenden en ontvangen.
Hoe berichten precies worden geïmplementeerd, welke protocollen worden gebruikt - dit is voor ons in deze context niet van belang. Het is belangrijk dat de knooppunten van een gedistribueerd systeem gegevens met elkaar kunnen uitwisselen door berichten te verzenden.
De definitie zelf ziet er niet erg ingewikkeld uit, maar we moeten er rekening mee houden dat een gedistribueerd systeem een aantal kenmerken heeft die voor ons belangrijk zullen zijn.
Kenmerken van gedistribueerde systemen
- samenloop – de mogelijkheid dat gelijktijdige of gelijktijdige gebeurtenissen plaatsvinden in het systeem. Bovendien beschouwen we gebeurtenissen die op twee verschillende knooppunten plaatsvinden als potentieel gelijktijdig, zolang we geen duidelijke volgorde hebben waarin deze gebeurtenissen plaatsvinden. Maar in de regel hebben we het niet.
- Geen mondiale klok. We hebben geen duidelijke volgorde van de gebeurtenissen vanwege het ontbreken van een mondiale klok. In de gewone mensenwereld zijn we eraan gewend dat we absoluut klokken en tijd hebben. Alles verandert als het gaat om gedistribueerde systemen. Zelfs ultra-precieze atoomklokken hebben drift, en er kunnen situaties zijn waarin we niet kunnen zeggen welke van de twee gebeurtenissen het eerst heeft plaatsgevonden. Daarom kunnen we ook niet op de tijd vertrouwen.
- Onafhankelijk falen van systeemknooppunten. Er is nog een probleem: er kan iets misgaan, simpelweg omdat onze knooppunten niet eeuwig meegaan. De harde schijf kan defect raken, de virtuele machine in de cloud kan opnieuw opstarten, het netwerk kan knipperen en berichten gaan verloren. Bovendien kunnen er situaties zijn waarin knooppunten werken, maar tegelijkertijd het systeem tegenwerken. De laatste klasse problemen kreeg zelfs een aparte naam: probleem . Het populairste voorbeeld van een gedistribueerd systeem met dit probleem is Blockchain. Maar vandaag zullen we deze speciale klasse van problemen niet beschouwen. We zullen geïnteresseerd zijn in situaties waarin eenvoudigweg een of meer knooppunten kunnen falen.
- Communicatiemodellen (berichtenmodellen) tussen knooppunten. We hebben al vastgesteld dat knooppunten communiceren door berichten uit te wisselen. Er zijn twee bekende berichtenmodellen: synchroon en asynchroon.
Modellen van communicatie tussen knooppunten in gedistribueerde systemen
Synchronisch model – we weten zeker dat er een eindige bekende tijddelta is waarin een bericht gegarandeerd van het ene knooppunt naar het andere reikt. Als deze tijd is verstreken en het bericht niet is aangekomen, kunnen we gerust zeggen dat het knooppunt is mislukt. In dit model hebben we voorspelbare wachttijden.
Asynchroon model – in asynchrone modellen gaan we ervan uit dat de wachttijd eindig is, maar er is geen tijdsdelta waarna we kunnen garanderen dat het knooppunt is mislukt. Die. De wachttijd voor een bericht van een knooppunt kan willekeurig lang zijn. Dit is een belangrijke definitie en we zullen er verder over praten.
Het concept van consensus in gedistribueerde systemen
Laten we, voordat we het concept van consensus formeel definiëren, een voorbeeld bekijken van een situatie waarin we dit nodig hebben, namelijk: State Machine-replicatie.
We hebben een gedistribueerd logboek. We willen dat het consistent is en identieke gegevens bevat op alle knooppunten van het gedistribueerde systeem. Wanneer een van de knooppunten een nieuwe waarde leert die het naar het logboek gaat schrijven, wordt het zijn taak om deze waarde aan alle andere knooppunten aan te bieden, zodat het logboek op alle knooppunten wordt bijgewerkt en het systeem naar een nieuwe consistente status gaat. In dit geval is het belangrijk dat de knooppunten het onderling eens zijn: alle knooppunten zijn het erover eens dat de voorgestelde nieuwe waarde correct is, alle knooppunten accepteren deze waarde en alleen in dit geval kan iedereen de nieuwe waarde naar het logboek schrijven.
Met andere woorden: geen van de knooppunten maakte bezwaar dat het meer relevante informatie had, en de voorgestelde waarde was onjuist. Overeenstemming tussen knooppunten en overeenstemming over een enkele correcte geaccepteerde waarde is consensus in een gedistribueerd systeem. Vervolgens zullen we het hebben over algoritmen waarmee een gedistribueerd systeem gegarandeerd consensus bereikt.
Formeel kunnen we een consensusalgoritme (of eenvoudigweg een consensusalgoritme) definiëren als een bepaalde functie die een gedistribueerd systeem van toestand A naar toestand B overbrengt. Bovendien wordt deze toestand door alle knooppunten geaccepteerd en kunnen alle knooppunten deze bevestigen. Het blijkt dat deze taak helemaal niet zo triviaal is als het op het eerste gezicht lijkt.
Eigenschappen van het consensusalgoritme
Het consensusalgoritme moet drie eigenschappen hebben zodat het systeem kan blijven bestaan en enige vooruitgang kan boeken bij de overgang van staat naar staat:
- Overeenkomst – alle correct werkende knooppunten moeten dezelfde waarde hebben (in artikelen wordt deze eigenschap ook wel veiligheidseigenschap genoemd). Alle knooppunten die momenteel functioneren (niet hebben gefaald of het contact met de anderen hebben verloren) moeten tot overeenstemming komen en een uiteindelijke gemeenschappelijke waarde accepteren.
Het is belangrijk om hier te begrijpen dat de knooppunten in het gedistribueerde systeem dat we overwegen het eens willen zijn. Dat wil zeggen, we hebben het nu over systemen waarin iets eenvoudigweg kan falen (een knooppunt faalt bijvoorbeeld), maar in dit systeem zijn er absoluut geen knooppunten die opzettelijk tegen anderen werken (de taak van Byzantijnse generaals). Dankzij deze eigenschap blijft het systeem consistent.
- Integriteit — als alle correct werkende knooppunten dezelfde waarde bieden v, wat betekent dat elk correct functionerend knooppunt deze waarde moet accepteren v.
- Beëindiging – alle correct werkende knooppunten zullen uiteindelijk een bepaalde waarde aannemen (liveness property), waardoor het algoritme vooruitgang kan boeken in het systeem. Elk individueel correct functionerend knooppunt moet vroeg of laat de uiteindelijke waarde accepteren en bevestigen: “Voor mij is deze waarde waar, ik ben het eens met het hele systeem.”
Een voorbeeld van hoe het consensusalgoritme werkt
Hoewel de eigenschappen van het algoritme misschien niet helemaal duidelijk zijn. Daarom zullen we met een voorbeeld illustreren welke stadia het eenvoudigste consensusalgoritme doorloopt in een systeem met een synchroon berichtenmodel, waarin alle knooppunten functioneren zoals verwacht, berichten niet verloren gaan en niets kapot gaat (gebeurt dit echt?).
- Het begint allemaal met een huwelijksaanzoek (Propose). Laten we aannemen dat een client verbinding heeft gemaakt met een knooppunt met de naam 'Knooppunt 1' en een transactie is gestart, waarbij een nieuwe waarde wordt doorgegeven aan het knooppunt - O. Vanaf nu noemen we 'Knooppunt 1'. voorstellen. Als voorsteller moet “Node 1” nu het hele systeem laten weten dat het nieuwe gegevens heeft, en stuurt het berichten naar alle andere knooppunten: “Kijk! De betekenis "O" kwam naar me toe en ik wil het opschrijven! Bevestig a.u.b. dat u ook “O” in uw log noteert.”
- De volgende fase is het stemmen voor de voorgestelde waarde (stemmen). Waar is het voor? Het kan gebeuren dat andere knooppunten recentere informatie hebben ontvangen en gegevens hebben over dezelfde transactie.
Wanneer knooppunt “Node 1” zijn voorstel verzendt, controleren de andere knooppunten hun logboeken op gegevens over deze gebeurtenis. Als er geen tegenstrijdigheden zijn, kondigen de knooppunten aan: “Ja, ik heb geen andere gegevens voor deze gebeurtenis. De “O”-waarde is de meest recente informatie die we verdienen.”In elk ander geval kunnen knooppunten reageren op “Knooppunt 1”: “Luister! Ik heb recentere gegevens over deze transactie. Niet 'O', maar iets beters."
In de stemfase komen de knooppunten tot een besluit: óf ze accepteren allemaal dezelfde waarde, óf een van hen stemt tegen, wat aangeeft dat hij over recentere gegevens beschikt.
- Als de stemronde succesvol was en iedereen vóór was, gaat het systeem naar een nieuwe fase: het accepteren van de waarde. “Node 1” verzamelt alle antwoorden van andere knooppunten en rapporteert: “Iedereen was het eens over de waarde “O”! Nu verklaar ik officieel dat "O" onze nieuwe betekenis is, hetzelfde voor iedereen! Schrijf het op in je boekje, vergeet het niet. Schrijf het op in je logboek!”
- De overige knooppunten sturen een bevestiging (geaccepteerd) dat ze de waarde “O” hebben opgeschreven; er is gedurende deze tijd niets nieuws binnengekomen (een soort tweefasige commit). Na deze belangrijke gebeurtenis zijn wij van mening dat de gedistribueerde transactie is voltooid.
Het consensusalgoritme bestaat dus in een eenvoudig geval uit vier stappen: voorstellen, stemmen (stemmen), accepteren (accepteren), acceptatie bevestigen (aanvaard).
Als we op een bepaalde stap niet tot overeenstemming konden komen, begint het algoritme opnieuw, rekening houdend met de informatie verstrekt door de knooppunten die weigerden de voorgestelde waarde te bevestigen.
Consensusalgoritme in een asynchroon systeem
Voordien verliep alles soepel, omdat we het hadden over een synchroon berichtenmodel. Maar we weten dat we in de moderne wereld gewend zijn alles asynchroon te doen. Hoe werkt een soortgelijk algoritme in een systeem met een asynchroon berichtenmodel, waarbij we van mening zijn dat de wachttijd op een reactie van een knooppunt willekeurig lang kan zijn (het falen van een knooppunt kan overigens ook als voorbeeld worden beschouwd wanneer een knooppunt kan voor een willekeurig lange tijd reageren).
Nu we weten hoe het consensusalgoritme in principe werkt, een vraag voor de nieuwsgierige lezers die zo ver zijn gekomen: hoeveel knooppunten in een systeem van N knooppunten met een asynchroon berichtenmodel kunnen falen zodat het systeem toch consensus kan bereiken?
Het juiste antwoord en de rechtvaardiging zitten achter de spoiler.Goed antwoord: 0. Als zelfs maar één knooppunt in een asynchroon systeem faalt, zal het systeem geen consensus kunnen bereiken. Deze bewering wordt bewezen in de in bepaalde kringen bekende FLP-stelling (1985, Fischer, Lynch, Paterson, link naar het origineel aan het einde van het artikel): “De onmogelijkheid om een gedistribueerde consensus te bereiken als ten minste één knooppunt faalt .”
Jongens, dan hebben we een probleem, we zijn eraan gewend dat alles asynchroon is. En hier is het. Hoe verder te leven?
We hadden het net over theorie, over wiskunde. Wat betekent ‘consensus kan niet worden bereikt’, vertaald van wiskundige taal naar de onze: techniek? Dit betekent dat “niet altijd kan worden bereikt”, d.w.z. Er is een geval waarin consensus niet haalbaar is. Wat voor soort geval is dit?
Dit is precies de schending van de hierboven beschreven levendigheidseigenschap. We hebben geen gemeenschappelijke overeenstemming, en het systeem kan geen vooruitgang boeken (kan niet in een eindige tijd worden voltooid) als we geen reactie van alle knooppunten krijgen. Omdat we in een asynchroon systeem geen voorspelbare responstijd hebben en we niet kunnen weten of een knooppunt is gecrasht of dat het gewoon lang duurt voordat het reageert.
Maar in de praktijk kunnen we wel een oplossing vinden. Laat ons algoritme bij storingen lang kunnen werken (mogelijk kan het voor onbepaalde tijd werken). Maar in de meeste situaties, wanneer de meeste knooppunten correct functioneren, zullen we vooruitgang boeken in het systeem.
In de praktijk hebben we te maken met deels synchrone communicatiemodellen. Gedeeltelijke synchronie wordt als volgt begrepen: in het algemene geval hebben we een asynchroon model, maar een bepaald concept van ‘mondiale stabilisatietijd’ van een bepaald tijdstip wordt formeel geïntroduceerd.
Dit moment zal misschien niet van lange duur zijn, maar het moet op een dag komen. De virtuele wekker gaat af en vanaf dat moment kunnen we voorspellen in welke tijdsdelta de berichten binnenkomen. Vanaf dit moment verandert het systeem van asynchroon naar synchroon. In de praktijk hebben we met precies zulke systemen te maken.
Het Paxos-algoritme lost consensusproblemen op
is een familie van algoritmen die het consensusprobleem voor gedeeltelijk synchrone systemen oplossen, met inachtneming van de mogelijkheid dat sommige knooppunten uitvallen. De auteur van Paxos is . Hij stelde in 1989 een formeel bewijs voor van het bestaan en de juistheid van het algoritme.
Maar het bewijs bleek verre van triviaal. De eerste publicatie verscheen pas in 1998 (33 pagina's) waarin het algoritme werd beschreven. Het bleek buitengewoon moeilijk te begrijpen en in 2001 werd een uitleg van het artikel gepubliceerd, die 14 pagina's besloeg. Het volume aan publicaties wordt gegeven om aan te tonen dat het probleem van consensus in feite helemaal niet eenvoudig is, en dat achter dergelijke algoritmen een enorme hoeveelheid werk schuilgaat van de slimste mensen.
Het is interessant dat Leslie Lamport zelf in zijn lezing opmerkte dat er in het tweede verklarende artikel één verklaring is, één regel (hij specificeerde niet welke), die op verschillende manieren kan worden geïnterpreteerd. En hierdoor werken een groot aantal moderne Paxos-implementaties niet helemaal correct.
Een gedetailleerde analyse van het werk van Paxos zou meer dan één artikel vergen, dus ik zal proberen het hoofdidee van het algoritme heel kort over te brengen. In de links aan het einde van mijn artikel vindt u materiaal waarmee u verder in dit onderwerp kunt duiken.
Functies bij Paxos
Het Paxos-algoritme heeft een concept van rollen. Laten we de drie belangrijkste bekijken (er zijn wijzigingen met extra rollen):
- Indieners van voorstellen (de termen kunnen ook worden gebruikt: leiders of coördinatoren). Dit zijn de jongens die een nieuwe waarde van de gebruiker leren kennen en de rol van leider op zich nemen. Hun taak is om een reeks voorstellen voor een nieuwe waarde te lanceren en verdere acties van de knooppunten te coördineren. Bovendien staat Paxos de aanwezigheid van meerdere leiders in bepaalde situaties toe.
- Acceptanten (kiezers). Dit zijn knooppunten die stemmen om een bepaalde waarde te accepteren of af te wijzen. Hun rol is erg belangrijk, omdat de beslissing van hen afhangt: naar welke toestand het systeem wel (of niet) zal gaan na de volgende fase van het consensusalgoritme.
- Lerenden. Knooppunten die eenvoudigweg de nieuwe geaccepteerde waarde accepteren en schrijven wanneer de status van het systeem is veranderd. Ze nemen geen beslissingen, ze ontvangen alleen de gegevens en kunnen deze aan de eindgebruiker geven.
Eén knooppunt kan meerdere rollen combineren in verschillende situaties.
Het concept van quorum
We gaan ervan uit dat we een systeem hebben van N knooppunten En daarvan het maximale F knooppunten kunnen falen. Als F-knooppunten falen, moeten we dat tenminste hebben 2F+1 acceptor knooppunten.
Dit is nodig zodat we altijd, zelfs in de slechtste situatie, over de meerderheid van “goede” knooppunten beschikken die correct werken. Dat is F+1 "goede" knooppunten die het daarmee eens zijn, en de uiteindelijke waarde wordt geaccepteerd. Anders kan er een situatie ontstaan waarin onze verschillende lokale groepen verschillende betekenissen aannemen en het onderling niet eens kunnen worden. Daarom hebben we een absolute meerderheid nodig om de stemming te winnen.
Het algemene idee van hoe het Paxos-consensusalgoritme werkt
Het Paxos-algoritme omvat twee grote fasen, die op hun beurt weer in twee stappen zijn verdeeld:
- Fase 1a: Voorbereiden. Tijdens de voorbereidingsfase informeert de leider (indiener) alle knooppunten: “We starten een nieuwe stemfase. We hebben een nieuwe ronde. Het nummer van deze ronde is n. Nu gaan we stemmen." Voorlopig rapporteert het eenvoudigweg het begin van een nieuwe cyclus, maar rapporteert het geen nieuwe waarde. De taak van deze fase is om een nieuwe ronde te starten en iedereen op de hoogte te stellen van het unieke nummer. Het ronde getal is belangrijk, het moet een waarde hebben die groter is dan alle voorgaande stemnummers van alle voorgaande leiders. Omdat het dankzij het ronde getal is dat andere knooppunten in het systeem zullen begrijpen hoe recent de gegevens van de leider zijn. Het is waarschijnlijk dat andere knooppunten al stemresultaten hebben van veel latere rondes en de leider eenvoudigweg zullen vertellen dat hij achterloopt op de tijd.
- Fase 1b: Belofte. Wanneer de acceptorknooppunten het nummer van de nieuwe stemfase hebben ontvangen, zijn er twee uitkomsten mogelijk:
- Het aantal n van de nieuwe stem is groter dan het aantal van eventuele eerdere stemmen waaraan de acceptor heeft deelgenomen. Vervolgens stuurt de acceptor een belofte aan de leider dat hij niet meer zal deelnemen aan stemmingen met een getal lager dan n. Als de acceptor al ergens op heeft gestemd (dat wil zeggen: hij heeft in de tweede fase al een bepaalde waarde geaccepteerd), dan koppelt hij de geaccepteerde waarde en het nummer van de stemming waaraan hij heeft deelgenomen aan zijn belofte.
- Anders kan de acceptor, als hij al op de hoogte is van de stem met een hoger nummer, de voorbereidingsstap eenvoudigweg negeren en niet reageren op de leider.
- Fase 2a: Accepteren. De leider moet wachten op een reactie van het quorum (de meerderheid van de knooppunten in het systeem) en als het vereiste aantal reacties wordt ontvangen, heeft hij twee opties voor de ontwikkeling van gebeurtenissen:
- Sommige acceptanten stuurden waarden op waar ze al op hadden gestemd. In dit geval selecteert de leider de waarde uit de stemming met het maximale aantal. Laten we deze waarde x noemen, en deze stuurt een bericht naar alle knooppunten, zoals: "Accepteer (n, x)", waarbij de eerste waarde het stemnummer is van de eigen stap Voorstellen, en de tweede waarde is waar iedereen voor verzameld heeft. d.w.z. de waarde waarvoor we daadwerkelijk stemmen.
- Als geen van de acceptanten waarden heeft gestuurd, maar ze hebben gewoon beloofd om in deze ronde te stemmen, kan de leider hen uitnodigen om op hun waarde te stemmen, de waarde waarvoor hij in de eerste plaats leider is geworden. Laten we het y noemen. Het stuurt een bericht naar alle knooppunten, zoals: “Accepteer (n, y)”, vergelijkbaar met de vorige uitkomst.
- Fase 2b: Geaccepteerd. Verder gaan de acceptorknooppunten, na ontvangst van het bericht “Accept(...)” van de leider, ermee akkoord (stuur een bevestiging naar alle knooppunten dat ze akkoord gaan met de nieuwe waarde) alleen als ze niet een aantal (andere) hebben beloofd) leider om deel te nemen aan de stemming met rond nummer n' > n, anders negeren ze het bevestigingsverzoek.
Als de meerderheid van de knooppunten op de leider heeft gereageerd en ze allemaal de nieuwe waarde hebben bevestigd, wordt de nieuwe waarde als geaccepteerd beschouwd. Hoera! Als de meerderheid niet wordt bereikt of als er knooppunten zijn die de nieuwe waarde weigeren te accepteren, begint alles opnieuw.
Dit is hoe het Paxos-algoritme werkt. Elk van deze fasen heeft veel subtiliteiten, we hebben praktisch geen rekening gehouden met verschillende soorten mislukkingen, problemen van meerdere leiders en nog veel meer, maar het doel van dit artikel is alleen om de lezer kennis te laten maken met de wereld van gedistribueerd computergebruik op een hoog niveau.
Het is ook vermeldenswaard dat Paxos niet de enige in zijn soort is, er zijn bijvoorbeeld andere algoritmen: , maar dit is een onderwerp voor een ander artikel.
Links naar materialen voor verdere studie
Beginnersniveau:
- , Preethi Kasireddy, blogartikel op Medium
- , Adi Kancherla, blogartikel op Medium
- , Ittai Abraham, blog
- , Ittai Abraham, blogartikel
Leslie Lamport-niveau:
- , Fischer, Lynch en Paterson, onderzoeksartikel, 1985
- , Leslie Lamport, onderzoekspaper, 1998
- , Leslie Lamport, onderzoekspaper, 2001
Bron: www.habr.com