Also, loosst eis virstellen. Et sinn 5 Kazen am Raum agespaart, a fir de Proprietaire ze erwächen, musse se sech alleguerten ënnereneen eens ginn, well se d'Dier nëmme kënnen opmaachen, mat fënnef vun hinnen drop lenken. Wann eng vun de Kazen dem Schrödinger seng Kaz ass, an déi aner Kazen wëssen net iwwer seng Entscheedung, stellt sech d'Fro: "Wéi kënnen se et maachen?"
An dësem Artikel wäert ech Iech an einfache Begrëffer soen iwwert d'theoretesch Komponent vun der Welt vun verdeelt Systemer an d'Prinzipien vun hirer Operatioun. Ech wäert och iwwerflächlech d'Haaptidee ënner dem Paxos ënnersicht.
Wann d'Entwéckler Cloud Infrastrukturen, verschidde Datenbanken benotzen an a Cluster vun enger grousser Zuel vu Wirbelen schaffen, si se zouversiichtlech datt d'Donnéeën komplett, sécher an ëmmer verfügbar sinn. Mee wou sinn d'Garantien?
Wesentlech sinn d'Garantien déi mir hunn Liwwergarantien. Si ginn an der Dokumentatioun beschriwwen wéi follegt: "Dëse Service ass zimlech zouverlässeg, et huet e bestëmmte SLA, maach der keng Suergen, alles funktionnéiert verdeelt wéi Dir erwaart."
Mir tendéieren un dat Bescht ze gleewen, well intelligent Kärelen vu grousse Firmen eis verséchert hunn datt alles gutt wäert sinn. Mir stellen d'Fro net: Firwat, tatsächlech, kann dat iwwerhaapt funktionnéieren? Gëtt et eng formell Begrënnung fir déi richteg Operatioun vun esou Systemer?
Ech sinn viru kuerzem zu a war ganz vun dësem Thema inspiréiert. Virträg an der Schoul ware méi wéi Berechnungsklassen wéi eppes am Zesummenhang mat Computersystemer. Awer genau esou goufen déi wichtegst Algorithmen, déi mir all Dag benotzen, ouni et emol ze wëssen, gläichzäiteg bewisen.
Déi meescht modern verdeelt Systemer benotzen de Paxos Konsens Algorithmus a seng verschidde Ännerunge. Déi coolst Saach ass datt d'Validitéit an am Prinzip d'Méiglechkeet vun der Existenz vun dësem Algorithmus einfach mat engem Bleistift a Pabeier bewisen ka ginn. An der Praxis gëtt den Algorithmus a grousse Systemer benotzt, déi op enger grousser Zuel vu Wirbelen an de Wolleken lafen.
Eng liicht Illustratioun vun deem wat duerno diskutéiert gëtt: d'Aufgab vun zwee GenereelLoosst eis e Bléck op eng Erwiermung kucken .
Mir hunn zwou Arméien - rout a wäiss. Wäiss Truppe baséieren an der belagerter Stad. Rout Truppen gefouert vun Genereel A1 an A2 sinn op zwou Säiten vun der Stad etabléiert. D'Aufgab vun de Redheads ass d'wäiss Stad z'attackéieren an ze gewannen. Wéi och ëmmer, d'Arméi vun all roude Generol individuell ass méi kleng wéi déi wäiss Arméi.
Victoire Konditioune fir déi Rout: Béid Genereel musse gläichzäiteg attackéieren fir en numeresche Virdeel iwwer déi Wäiss ze hunn. Fir dëst ze maachen, mussen d'Generaler A1 an A2 sech mateneen eens ginn. Wann jidderee getrennt attackéiert, verléieren d'Routheads.
Fir en Accord z'erreechen, kënnen d'Generaler A1 an A2 Messenger matenee schécken duerch d'Territoire vun der wäisser Stad. De Messenger kann erfollegräich en alliéierten Generol erreechen oder kann vum Feind ofgefaangen ginn. Fro: Gëtt et esou eng Sequenz vu Kommunikatiounen tëscht de rout-Hoer Genereel (d'Sequenz vu Sender vun A1 op A2 a vice-versa vun A2 op A1), an där se garantéiert sinn op en Ugrëff an der Stonn X. Hei, Garantie bedeit datt béid Genereel eng eendeiteg Bestätegung hunn datt en Alliéierten (en anere Generol) definitiv op der ernannter Zäit X attackéiert.
Ugeholl datt d'A1 e Messenger op A2 schéckt mat der Noriicht: "Loosst eis haut um Mëtternuecht attackéieren!" General A1 kann net ouni Bestätegung vum Generol A2 attackéieren. Wann de Messenger vun A1 ukomm ass, da schéckt de Generol A2 d'Bestätegung mam Message: "Jo, loosst eis haut d'Wäiss ëmbréngen." Awer elo weess de Generol A2 net op säi Messenger ukomm ass oder net, hien huet keng Garantie ob d'Attack gläichzäiteg wäert sinn. Elo brauch d'General A2 nees eng Confirmatioun.
Wa mir hir Kommunikatioun weider beschreiwen, gëtt et kloer datt egal wéi vill Messageaustauschzyklen et gëtt, et gëtt kee Wee fir ze garantéieren datt béid Genereel hir Messagen kritt hunn (ugeholl datt entweder Messenger kann ofgefaangen ginn).
The Two Generals Problem ass eng super Illustratioun vun engem ganz einfache verdeelte System wou et zwee Wirbelen mat onzouverlässeg Kommunikatioun sinn. Dëst bedeit datt mir keng 100% Garantie hunn datt se synchroniséiert sinn. Ähnlech Probleemer ginn eréischt méi spéit am Artikel op enger méi grousser Skala diskutéiert.
Mir presentéieren d'Konzept vun verdeelt Systemer
E verdeelt System ass eng Grupp vu Computeren (nodeem mir se Noden nennen) déi Messagen austausche kënnen. All eenzel Node ass eng Aart vun autonomer Entitéit. En Node kann Aufgaben eleng veraarbecht, awer fir mat anere Noden ze kommunizéieren, muss et Messagen schécken an kréien.
Wéi genee Messagen ëmgesat ginn, wéi eng Protokoller gi benotzt - dat ass eis net interesséiert an dësem Kontext. Et ass wichteg datt d'Node vun engem verdeelte System Daten matenee kënnen austauschen andeems Dir Messagen schéckt.
D'Definitioun selwer gesäit net ganz komplizéiert aus, awer mir musse berücksichtegen datt e verdeelt System eng Rei Attributer huet, déi fir eis wichteg sinn.
Attributer vun verdeelt Systemer
- Konklusioun - d'Méiglechkeet vu simultan oder concurrent Eventer am System. Ausserdeem wäerte mir Eventer, déi op zwee verschiddene Wirbelen optrieden, als potenziell gläichzäiteg betruechten soulaang mir keng kloer Uerdnung fir d'Optriede vun dësen Eventer hunn. Awer, als Regel, hu mir et net.
- Keng global Auer. Mir hu keng kloer Uerdnung vun Eventer wéinst dem Mangel vun enger globaler Auer. An der gewéinlecher Welt vu Leit si mir der Tatsaach Gewunnecht datt mir Aueren an Zäit absolut hunn. Alles ännert sech wann et ëm verdeelt Systemer kënnt. Och ultra-präzis atomar Aueren hunn Drift, an et kënne Situatiounen sinn, wou mir net soen, wéi eng vun zwee Eventer als éischt geschitt ass. Dofir kënne mir eis och net op Zäit vertrauen.
- Onofhängeg Echec vun System Wirbelen. Et gëtt en anere Problem: eppes kann schief goen einfach well eis Noden net fir ëmmer daueren. D'Festplack kann versoen, d'virtuell Maschinn an der Wollek kann nei starten, d'Netzwierk kann blénken an d'Botschafte ginn verluer. Ausserdeem kënnen et Situatiounen sinn, wou Wirbelen funktionnéieren, awer gläichzäiteg géint de System schaffen. Déi lescht Klass vu Probleemer krut souguer e separaten Numm: Problem . Dat populärste Beispill vun engem verdeelte System mat dësem Problem ass Blockchain. Awer haut wäerte mir dës speziell Klass vu Probleemer net betruechten. Mir wäerten an Situatiounen interesséiert sinn an deenen einfach een oder méi Wirbelen versoen.
- Kommunikatioun Modeller (Message Modeller) tëscht Wirbelen. Mir hu scho festgestallt datt Noden kommunizéieren andeems Dir Messagen austauscht. Et ginn zwee bekannte Messagerie Modeller: Synchron an asynchron.
Kommunikatiounsmodeller tëscht Noden a verdeelt Systemer
Synchronmodell - mir wësse sécher datt et e endlech bekannten Delta vun der Zäit ass, während där e Message garantéiert ass vun engem Node an en aneren z'erreechen. Wann dës Zäit vergaang ass an d'Botschaft net ukomm ass, kënne mir sécher soen datt den Node gescheitert ass. An dësem Modell hu mir prévisibel Waardezäiten.
Asynchrone Modell - an asynchrone Modeller betruechte mir datt d'Waardezäit endlech ass, awer et gëtt keng sou Delta vun der Zäit, duerno kënne mir garantéieren datt de Node gescheitert ass. Déi. D'Waardezäit fir e Message vun engem Node kann arbiträr laang sinn. Dëst ass eng wichteg Definitioun, a mir wäerte weider doriwwer schwätzen.
D'Konzept vum Konsens a verdeelt Systemer
Ier mer d'Konzept vum Konsens formell definéieren, loosst eis e Beispill vun enger Situatioun betruechten wou mir et brauchen, nämlech - Staat Machine Replikatioun.
Mir hunn e puer verdeelt Log. Mir wëllen datt et konsequent ass an identesch Donnéeën op all Node vum verdeelte System enthält. Wann ee vun de Wirbelen en neie Wäert léiert, deen et an de Logbuch schreift, ass seng Aufgab dëse Wäert un all aner Wirbelen ze bidden, sou datt de Logbuch op all Wirbelen aktualiséiert gëtt an de System an en neie konsequente Staat geet. An dësem Fall ass et wichteg datt d'Node sech ënnerenee stëmmen: all Node stëmmen datt de proposéierte neie Wäert richteg ass, all Node akzeptéieren dëse Wäert, an nëmmen an dësem Fall kann jiddereen den neie Wäert an de Logbuch schreiwen.
An anere Wierder: Keen vun de Wirbelen huet dogéint gemaach datt et méi relevant Informatioun huet, an de proposéierte Wäert war falsch. Accord tëscht Noden an Accord op engem eenzege korrekten akzeptéierte Wäert ass Konsens an engem verdeelte System. Als nächst wäerte mir iwwer Algorithmen schwätzen, déi et erlaabt datt e verdeelt System garantéiert ass fir Konsens z'erreechen.
Méi formell kënne mir e Konsens Algorithmus (oder einfach e Konsens Algorithmus) als eng gewësse Funktioun definéieren, déi e verdeelt System vum Staat A op Staat B transferéiert. Ausserdeem gëtt dësen Zoustand vun all Noden akzeptéiert, an all Node kënnen et bestätegen. Wéi et sech erausstellt, ass dës Aufgab guer net sou trivial wéi et op den éischte Bléck schéngt.
Eegeschafte vum Konsens Algorithmus
De Konsens Algorithmus muss dräi Eegeschaften hunn fir datt de System weider existéiert an e puer Fortschrëtter huet fir vu Staat zu Staat ze plënneren:
- Konventioun - all korrekt funktionéierend Noden mussen dee selwechte Wäert huelen (an Artikelen gëtt dës Immobilie och als Sécherheetseigendom bezeechent). All Wirbelen déi am Moment funktionnéieren (net gescheitert oder de Kontakt mat deenen aneren verluer hunn) musse sech eens ginn an e finalen gemeinsame Wäert akzeptéieren.
Et ass wichteg hei ze verstoen datt d'Noden am verdeelte System dee mir betruechte wëllen averstane sinn. Dat ass, mir schwätzen elo iwwer Systemer, an deenen eppes einfach ausfale kann (zum Beispill e puer Node feelt), awer an dësem System sinn et definitiv keng Wirbelen, déi bewosst géint anerer schaffen (d'Aufgab vun de byzantinesche Genereel). Wéinst dëser Propriétéit bleift de System konsequent.
- Integritéit - wann all richteg funktionnéierend Noden dee selwechte Wäert ubidden v, dat heescht datt all korrekt funktionnéiert Node dëse Wäert muss akzeptéieren v.
- Enn - all korrekt Operatiounsknäppchen wäerte schlussendlech e bestëmmte Wäert iwwerhuelen (Liewensqualitéit), wat den Algorithmus erlaabt Fortschrëtter am System ze maachen. All eenzel korrekt funktionnéierenden Node muss fréier oder spéider den definitive Wäert akzeptéieren an et bestätegen: "Fir mech ass dëse Wäert wouer, ech averstane mam ganze System."
E Beispill vu wéi de Konsens Algorithmus funktionnéiert
Wärend d'Eegeschafte vum Algorithmus vläicht net ganz kloer sinn. Dofir wäerte mir mat engem Beispill illustréieren, wéi eng Etappen den einfachsten Konsens Algorithmus duerchgeet an engem System mat engem synchrone Messagerie Modell, an deem all Node funktionnéieren wéi erwaart, Messagen net verluer ginn an näischt brécht (geet dat wierklech?).
- Et fänkt alles mat engem Bestietnes Propositioun un (Proposéieren). Loosst eis dovun ausgoen, datt e Client un engem Node verbonnen genannt "Node 1" an eng Transaktioun ugefaangen, laanschtgoungen en neie Wäert un de Node - O. Vun elo un, wäerte mir Opruff "Node 1" Offer. Als Proposer muss "Node 1" elo de ganze System matdeelen datt et frësch Donnéeën huet, an et schéckt Messagen un all aner Noden: "Kuckt! D'Bedeitung "O" ass bei mir komm an ech wëll et opschreiwen! Bestätegt w.e.g. datt Dir och "O" an Ärem Logbuch notéiert.
- Déi nächst Etapp ass de Vote fir de proposéierte Wäert (Stëmmen). Fir wat ass et? Et kann geschéien, datt aner Wirbelen méi rezent Informatiounen kritt hunn, a si hunn Daten iwwert déi selwecht Transaktioun.
Wann den Node "Node 1" säi Propose schéckt, kontrolléieren déi aner Node hir Logbicher fir Daten iwwer dëst Event. Wann et keng Kontradiktioune sinn, annoncéieren d'Noden: "Jo, ech hu keng aner Donnéeën fir dëst Evenement. Den "O" Wäert ass déi lescht Informatioun déi mir verdéngen.An all anere Fall kënnen Node op "Node 1" äntweren: "Lauschtert! Ech hu méi rezent Daten iwwer dës Transaktioun. Net 'O', awer eppes besseres.
Beim Ofstëmmungsstadium kommen d'Node zu enger Decisioun: entweder si akzeptéieren all dee selwechte Wäert, oder ee vun hinnen stëmmt géint, wat beweist datt hien méi rezent Donnéeën huet.
- Wann d'Wahlronn erfollegräich war a jidderee war dofir, da geet de System op eng nei Etapp - De Wäert akzeptéieren. "Node 1" sammelt all d'Äntwerte vun anere Wirbelen a bericht: "Jiddereen huet sech iwwer de Wäert "O" eens! Elo erklären ech offiziell datt "O" eis nei Bedeitung ass, déi selwecht fir jiddereen! Schreift et an Ärem klenge Buch, vergiesst net. Schreift et an Ärem Logbuch!"
- Déi verbleiwen Noden schécken Bestätegung (Akzeptéiert) datt se de Wäert "O" opgeschriwwen hunn; näischt Neies ass während dëser Zäit ukomm (eng Aart vun zwee-Phase Verpflichtung). No dësem bedeitende Event betruechte mir datt déi verdeelt Transaktioun ofgeschloss ass.
Also besteet de Konsens Algorithmus an engem einfache Fall aus véier Schrëtt: proposéieren, stëmmen (stëmmen), akzeptéieren (akzeptéieren), bestätegen Akzeptanz (akzeptéiert).
Wa mir op e puer Schrëtt net konnten d'Accord erreechen, da fänkt den Algorithmus erëm un, andeems d'Informatioun vun den Noden berücksichtegt gëtt, déi refuséiert de proposéierte Wäert ze bestätegen.
Konsens Algorithmus an engem asynchrone System
Virun dëser war alles glat, well mir iwwer e synchrone Messagerie Modell geschwat hunn. Awer mir wëssen datt mir an der moderner Welt gewinnt sinn alles asynchron ze maachen. Wéi funktionéiert en ähnlechen Algorithmus an engem System mat engem asynchrone Messageriemodell, wou mir gleewen datt d'Waardezäit fir eng Äntwert vun engem Node arbiträr laang ka sinn (iwwregens kann den Echec vun engem Node och als Beispill ugesi ginn wann en Node ka fir eng arbiträr laang Zäit reagéieren).
Elo wou mer wësse wéi de Konsens Algorithmus am Prinzip funktionnéiert, eng Fro fir déi virwëtzeg Lieser, déi et esou wäit gemaach hunn: wéivill Noden an engem System vun N Wirbelen mat engem asynchrone Messagemodell kënnen ausfalen, sou datt de System nach ëmmer Konsens erreechen kann?
Déi richteg Äntwert a Begrënnung stinn hannert dem Spoiler.Déi richteg Äntwert ass: 0. Wann souguer een Node an engem asynchrone System feelt, wäert de System net fäeg sinn Konsens z'erreechen. Dës Ausso gëtt am FLP-Theorem bewisen, bekannt a bestëmmte Kreesser (1985, Fischer, Lynch, Paterson, Link zum Original um Enn vum Artikel): "D'Onméiglechkeet fir e verdeelte Konsens z'erreechen wann op d'mannst een Node fällt. ".
Kärelen, dann hu mir e Problem, mir si gewinnt datt alles asynchron ass. An hei ass et. Wéi weider ze liewen?
Mir hu just iwwer Theorie geschwat, iwwer Mathematik. Wat heescht "Konsens kann net erreecht ginn", aus mathematescher Sprooch iwwersetzen an eis - Ingenieur? Dat heescht, datt "net ëmmer erreecht ka ginn", d.h. Et gëtt e Fall an deem Konsens net erreechbar ass. Wéi eng Fall ass dëst?
Dëst ass genee d'Verletzung vun der Liewensqualitéit hei uewen beschriwwen. Mir hunn net eng gemeinsam Accord, an de System kann net Fortschrëtter hunn (kann net an enger endlech Zäit komplett) am Fall wou mir keng Äntwert vun all Wirbelen hunn. Well an engem asynchrone System hu mir keng prévisibel Äntwertzäit a mir kënnen net wëssen ob e Knuet erofgefall ass oder just eng laang Zäit dauert fir ze reagéieren.
Mä an der Praxis kënne mir eng Léisung fannen. Loosst eisen Algorithmus fäeg sinn fir eng laang Zäit am Fall vu Feeler ze schaffen (potenziell kann et onbestëmmt funktionnéieren). Awer an de meeschte Situatiounen, wann déi meescht Noden korrekt funktionnéieren, hu mir Fortschrëtter am System.
An der Praxis këmmere mir eis mat deelweis synchrone Kommunikatiounsmodeller. Partiell Synchronie gëtt wéi follegt verstanen: am allgemenge Fall hu mir en asynchrone Modell, awer e gewësse Konzept vun der "globaler Stabiliséierungszäit" vun engem gewëssen Zäitpunkt gëtt formell agefouert.
Dëse Moment an der Zäit kënnt net fir eng laang Zäit, awer et muss enges Daags kommen. De virtuelle Wecker schellt, a vun deem Moment un kënne mir den Zäitdelta viraussoen, fir deen d'Messagen ukommen. Vun dësem Moment u gëtt de System vun asynchron op synchron. An der Praxis këmmere mir eis mat genee esou Systemer.
De Paxos Algorithmus léist Konsensproblemer
ass eng Famill vun Algorithmen déi de Konsensproblem fir deelweis Synchronsystemer léisen, ënnerleien der Méiglechkeet datt e puer Noden versoen. Den Auteur vu Paxos ass . Hien huet 1989 e formelle Beweis vun der Existenz an der Richtegkeet vum Algorithmus proposéiert.
Awer de Beweis huet sech wäit vun trivial erausgestallt. Déi éischt Verëffentlechung gouf eréischt am Joer 1998 verëffentlecht (33 Säiten) déi den Algorithmus beschreift. Wéi et sech erausstellt, war et extrem schwéier ze verstoen, an 2001 gouf eng Erklärung vum Artikel publizéiert, deen 14 Säiten huet. De Volume vun de Publikatioune gëtt uginn fir ze weisen datt de Problem vum Konsens guer net einfach ass, an hannert esou Algorithmen stécht eng grouss Quantitéit un Aarbecht vun de schlau Leit.
Interessant ass, datt de Leslie Lamport selwer a sengem Virtrag bemierkt huet, datt am zweeten Erklärungsartikel eng Ausso ass, eng Zeil (hien huet net uginn wéi eng), déi op verschidde Manéieren interpretéiert ka ginn. A wéinst dësem funktionnéieren eng grouss Zuel vu modernen Paxos Implementatiounen net ganz korrekt.
Eng detailléiert Analyse vum Paxos seng Aarbecht géif méi wéi een Artikel daueren, also probéieren ech ganz kuerz d'Haaptidee vum Algorithmus ze vermëttelen. An de Linken um Enn vu mengem Artikel fannt Dir Material fir weider an dëst Thema ze tauchen.
Rollen bei Paxos
De Paxos Algorithmus huet e Konzept vu Rollen. Loosst d'dräi Haaptrei betruecht (et ginn Ännerungen mat zousätzlech Rollen):
- Virschléi (d'Begrëffer kënnen och benotzt ginn: Leadere oder Koordinatoren). Dëst sinn d'Kärelen, déi iwwer e puer neie Wäert vum Benotzer léieren an d'Roll vum Leader iwwerhuelen. Hir Aufgab ass eng Ronn vu Virschléi fir en neie Wäert ze lancéieren an weider Aktiounen vun den Noden ze koordinéieren. Ausserdeem erlaabt Paxos d'Präsenz vu verschiddene Leader a bestëmmte Situatiounen.
- Akzepter (Wieler). Dëst sinn Noden déi stëmmen fir e bestëmmte Wäert ze akzeptéieren oder ze refuséieren. Hir Roll ass ganz wichteg, well d'Entscheedung hänkt dovun of: wéi en Zoustand de System wäert (oder net) no der nächster Etapp vum Konsens Algorithmus goen.
- Léierpersonal. Noden déi einfach den neien akzeptéierte Wäert akzeptéieren a schreiwen wann den Zoustand vum System geännert huet. Si huelen keng Entscheedungen, si kréien just d'Donnéeën a kënnen se dem Endbenotzer ginn.
Een Node kann verschidde Rollen a verschiddene Situatiounen kombinéieren.
D'Konzept vum Quorum
Mir ginn dovun aus, datt mir e System vun N Noden A vun hinnen de Maximum F Node kënnen ausfalen. Wann F Wirbelen versoen, da musse mir op d'mannst hunn 2F+1 acceptor Noden.
Dëst ass néideg fir datt mir ëmmer d'Majoritéit hunn, och an der schlëmmster Situatioun, vu "gudden" Knäppercher déi richteg funktionnéieren. Dat ass F+1 "gutt" Wirbelen déi ausgemaach, an der Finale Wäert wäert akzeptéiert ginn. Soss kann et eng Situatioun ginn, wou eis verschidde lokal Gruppen ënnerschiddlech Bedeitunge kréien a sech net ënnerenee kënnen eens ginn. Dofir brauche mir eng absolut Majoritéit fir de Vote ze gewannen.
Déi allgemeng Iddi wéi de Paxos Konsens Algorithmus funktionnéiert
De Paxos Algorithmus beinhalt zwou grouss Phasen, déi all Kéier an zwee Schrëtt opgedeelt sinn:
- Phase 1a: Preparéieren. Wärend der Virbereedungsphase informéiert de Leader (Proposer) all Noden: "Mir starten eng nei Ofstëmmungsphase. Mir hunn eng nei Ronn. D'Zuel vun dëser Ronn ass n. Elo fänken mer un ze stëmmen." Fir de Moment bericht et einfach den Ufank vun engem neien Zyklus, awer mellt keen neie Wäert. D'Aufgab vun dëser Etapp ass eng nei Ronn unzefänken a jidderee vu senger eenzegaarteger Zuel z'informéieren. D'Ronnzuel ass wichteg, et muss e Wäert méi grouss sinn wéi all fréier Wahlzuelen vun alle fréiere Leader. Well et ass dank der Ronn Zuel datt aner Wirbelen am System wäert verstoen wéi rezent de Leader d'Donnéeën ass. Et ass méiglech datt aner Node scho Wahlresultater vu vill méi spéit Ronnen hunn a wäerten dem Leader einfach soen datt hien hannert der Zäit ass.
- Phase 1b: Verspriechen. Wann d'Akzeptatornoden d'Zuel vun der neier Wahlstadium kruten, sinn zwee Resultater méiglech:
- D'Zuel n vum neie Vote ass méi grouss wéi d'Zuel vun all fréiere Vote an deem den Acceptor matgemaach huet. Da schéckt den Acceptor dem Leader e Verspriechen, datt hien net méi bei méi Stëmme mat enger Zuel méi niddereg wéi n wäert deelhuelen. Wann den Akzeptor schonn eppes gestëmmt huet (dat heescht, hien huet schonn an der zweeter Phase e Wäert akzeptéiert), dann setzt hien den akzeptéierte Wäert an d'Zuel vun de Vote un deem hien deelgeholl huet un säi Verspriechen.
- Soss, wann den Acceptor scho weess iwwer de méi héijen Zuelen Vote, kann et einfach de Virbereedungsschrëtt ignoréieren an net op de Leader reagéieren.
- Phase 2a: Akzeptéieren. De Leader muss op eng Äntwert vum Quorum waarden (d'Majoritéit vun de Wirbelen am System) a wann déi erfuerderlech Unzuel vun Äntwerte kritt ass, huet hien zwou Méiglechkeeten fir d'Entwécklung vun Eventer:
- E puer vun den Akzeptoren hunn Wäerter geschéckt fir déi se scho gestëmmt hunn. An dësem Fall wielt de Leader de Wäert aus dem Vote mat der maximaler Zuel. Loosst eis dëse Wäert x nennen, an et schéckt e Message un all Noden wéi: "Akzeptéieren (n, x)", wou den éischte Wäert d'Wahlnummer aus sengem eegene Propose Schrëtt ass, an den zweete Wäert ass wat jidderee gesammelt huet, d.h. de Wäert fir dee mir eigentlech stëmmen.
- Wann keen vun de acceptors all Wäerter geschéckt, mä si versprach einfach an dëser Ronn ze wielen, de Leader kann hinnen invitéieren fir hire Wäert ze wielen, de Wäert fir déi hien als Leader an der éischter Plaz gouf. Loosst eis et nennen y. Et schéckt e Message un all Noden wéi: "Akzeptéieren (n, y)", ähnlech wéi de fréiere Resultat.
- Phase 2b: Akzeptéiert. Weider sinn d'Akzeptéiernoden, wann se de "Accept(...)" Message vum Leader kréien, averstanen domat (schécke Bestätegung un all Noden datt se mam neie Wäert averstane sinn) nëmme wa se net e puer (aner) versprach hunn) Leader un der Ofstëmmung mat der Ronn Zuel deelzehuelen n > n, soss ignoréieren se d'Confirmatiounsufro.
Wann d'Majoritéit vun de Wirbelen dem Leader geäntwert hunn, an all vun hinnen den neie Wäert bestätegt, da gëtt den neie Wäert als akzeptéiert ugesinn. Hour! Wann d'Majoritéit net erreecht gëtt oder et Node gëtt, déi refuséiert hunn den neie Wäert ze akzeptéieren, da fänkt alles erëm un.
Dëst ass wéi de Paxos Algorithmus funktionnéiert. Jiddereng vun dësen Etappe huet vill Subtleties, mir hu praktesch net verschidden Aarte vu Feeler, Probleemer vu Multiple Leader a vill méi berücksichtegt, awer den Zweck vun dësem Artikel ass nëmmen de Lieser an d'Welt vum verdeelt Informatik op engem héijen Niveau virzestellen.
Et ass och derwäert ze notéieren datt Paxos net deen eenzege vu senger Aart ass, et ginn aner Algorithmen, zum Beispill, , awer dëst ass en Thema fir en aneren Artikel.
Linken op Material fir weider Studie
Ufänger Niveau:
- , Preethi Kasireddy, Blog Artikel iwwer Medium
- , Adi Kancherla, Blog Artikel iwwer Medium
- , Ittai Abraham, Blog
- , Ittai Abraham, Blog Artikel
Leslie Lamport Niveau:
- Fischer, Lynch & Paterson, Research Paper, 1985
- , Leslie Lamport, Fuerschungspabeier, 1998
- , Leslie Lamport, Fuerschungspabeier, 2001
Source: will.com