Szóval képzeljük el. 5 macska van bezárva a szobában, és ahhoz, hogy felébressze a gazdit, mindannyiuknak meg kell egyeznie egymással, mert csak öten támaszkodva tudják kinyitni az ajtót. Ha az egyik macska Schrödinger macskája, és a többi macska nem tud a döntéséről, akkor felmerül a kérdés: „Hogyan tehetik meg?”
Ebben a cikkben az elosztott rendszerek világának elméleti összetevőiről és működési elveiről fogok leegyszerűsíteni. Felületesen megvizsgálom a Paxos alapgondolatát is.
Amikor a fejlesztők felhő infrastruktúrákat, különféle adatbázisokat használnak, és nagyszámú csomópontból álló klaszterekben dolgoznak, biztosak abban, hogy az adatok teljesek, biztonságosak és mindig elérhetőek lesznek. De hol vannak a garanciák?
A mi garanciáink lényegében beszállítói garanciák. Ezek leírása a dokumentációban a következő: „Ez a szolgáltatás meglehetősen megbízható, adott SLA-val rendelkezik, ne aggódjon, minden elosztottan fog működni, ahogy elvárja.”
Hajlamosak vagyunk a legjobbban hinni, mert a nagy cégek okos srácai biztosítottak minket, hogy minden rendben lesz. Nem tesszük fel a kérdést: valójában miért működhet ez egyáltalán? Van-e formális indoka az ilyen rendszerek megfelelő működésének?
Nemrég jártam és nagyon megihlette ez a téma. Az iskolai előadások inkább számítottak számítástechnikai óráknak, mint valami számítógépes rendszerekkel kapcsolatosnak. De pontosan így bizonyítottak egy időben azok a legfontosabb algoritmusok, amelyeket nap mint nap használunk, anélkül, hogy tudnánk.
A legtöbb modern elosztott rendszer a Paxos konszenzus algoritmust és annak különféle módosításait használja. A legmenőbb az, hogy ennek az algoritmusnak az érvényessége és elvileg a létezésének lehetősége is egyszerűen tollal és papírral bizonyítható. A gyakorlatban az algoritmust nagy rendszerekben használják, amelyek a felhők hatalmas számú csomópontján futnak.
Könnyű illusztrációja annak, amiről ezután lesz szó: két tábornok feladataVessünk egy pillantást bemelegítésre .
Két hadseregünk van - vörös és fehér. A fehér csapatok az ostromlott városban tartózkodnak. Az A1 és A2 tábornok vezette vörös csapatok a város két oldalán helyezkednek el. A vörös hajúak feladata, hogy megtámadják a fehér várost és nyerjenek. Azonban minden vörös tábornok serege külön-külön kisebb, mint a fehér sereg.
A pirosak győzelmi feltételei: mindkét tábornoknak egyszerre kell támadnia, hogy számbeli előnyt szerezzen a fehérekkel szemben. Ehhez az A1 és A2 tábornoknak meg kell állapodniuk egymással. Ha mindenki külön támad, a vörös hajúak veszítenek.
A megegyezés érdekében A1 és A2 tábornok futárokat küldhet egymásnak a fehér város területén keresztül. A hírnök sikeresen elérheti a szövetséges tábornokot, vagy elfoghatja az ellenség. Kérdés: van-e olyan kommunikációs sorozat a vörös hajú tábornokok között (a hírnökök A1-ből A2-be és fordítva A2-ből A1-be küldésének sorrendje), amelyben garantáltan megállapodnak a támadásban X órában. A garanciák azt jelentik, hogy mindkét tábornok egyértelmű megerősítést kap arról, hogy egy szövetséges (egy másik tábornok) határozottan támadni fog a megjelölt X időpontban.
Tegyük fel, hogy A1 küldöncöt küld A2-nek a következő üzenettel: „Támadjunk ma éjfélkor!” Az A1 tábornok nem támadhat az A2 tábornok jóváhagyása nélkül. Ha megérkezett az A1 hírnöke, akkor A2 tábornok visszaigazolást küld a következő üzenettel: "Igen, öljük meg ma a fehéreket." De most A2 tábornok nem tudja, hogy a hírnöke megérkezett-e vagy sem, nincs garancia arra, hogy a támadás egyidejű lesz-e. Most a General A2 ismét megerősítésre szorul.
Ha tovább írjuk a kommunikációjukat, világossá válik, hogy akárhány üzenetváltási ciklus van, semmi sem garantálható, hogy mindkét tábornok megkapta az üzenetét (feltételezve, hogy bármelyik hírnök elfogható).
A Two Generals Probléma egy nagyon egyszerű elosztott rendszer nagyszerű példája, ahol két csomópont van megbízhatatlan kommunikációval. Ez azt jelenti, hogy nincs 100%-os garanciánk a szinkronizálásra. Hasonló problémákat a cikk későbbi részében csak nagyobb léptékben tárgyalunk.
Bemutatjuk az elosztott rendszerek fogalmát
Az elosztott rendszer számítógépek csoportja (a továbbiakban csomópontoknak nevezzük őket), amelyek képesek üzeneteket cserélni. Minden egyes csomópont valamilyen autonóm entitás. Egy csomópont képes önállóan is feldolgozni a feladatokat, de ahhoz, hogy más csomópontokkal kommunikálhasson, üzeneteket kell küldenie és fogadnia.
Hogy pontosan hogyan valósítják meg az üzeneteket, milyen protokollokat használnak - ez ebben az összefüggésben nem érdekes számunkra. Fontos, hogy egy elosztott rendszer csomópontjai üzenetek küldésével adatokat cserélhessenek egymással.
Maga a meghatározás nem tűnik túl bonyolultnak, de figyelembe kell vennünk, hogy egy elosztott rendszernek számos olyan tulajdonsága van, amelyek fontosak lesznek számunkra.
Elosztott rendszerek attribútumai
- Konkurencia – egyidejű vagy egyidejű események előfordulásának lehetősége a rendszerben. Ezenkívül a két különböző csomóponton előforduló eseményeket potenciálisan egyidejűnek tekintjük mindaddig, amíg nincs egyértelmű sorrendjük ezeknek az eseményeknek. De nálunk általában nincs ilyen.
- Nincs globális óra. Globális óra hiánya miatt nincs egyértelmű eseménysorunk. Az emberek hétköznapi világában megszoktuk, hogy óráink és időnk abszolút megvan. Minden megváltozik, ha az elosztott rendszerekről van szó. Még az ultraprecíz atomórák is sodródnak, és előfordulhatnak olyan helyzetek, amikor nem tudjuk megmondani, hogy a két esemény közül melyik történt előbb. Ezért nem támaszkodhatunk az időre sem.
- A rendszercsomópontok független meghibásodása. Van egy másik probléma: valami elromolhat egyszerűen azért, mert csomópontjaink nem tartanak örökké. A merevlemez meghibásodhat, a felhőben lévő virtuális gép újraindulhat, a hálózat villoghat, és az üzenetek elvesznek. Ezenkívül előfordulhatnak olyan helyzetek, amikor a csomópontok működnek, de ugyanakkor a rendszer ellen dolgoznak. Az utolsó problémaosztály még külön nevet is kapott: probléma . Az ezzel a problémával küzdő elosztott rendszer legnépszerűbb példája a Blockchain. De ma nem foglalkozunk ezzel a speciális problémákkal. Érdekelnek minket azok a helyzetek, amikor egyszerűen egy vagy több csomópont meghibásodhat.
- Kommunikációs modellek (üzenetküldési modellek) a csomópontok között. Azt már megállapítottuk, hogy a csomópontok üzenetváltással kommunikálnak. Két jól ismert üzenetküldési modell létezik: szinkron és aszinkron.
Csomópontok közötti kommunikáció modelljei elosztott rendszerekben
Szinkron modell – pontosan tudjuk, hogy van egy véges ismert delta idő, amely alatt az üzenet garantáltan eljut egyik csomóponttól a másikig. Ha ez az idő eltelt, és az üzenet nem érkezett meg, akkor nyugodtan kijelenthetjük, hogy a csomópont meghibásodott. Ebben a modellben kiszámítható várakozási időink vannak.
Aszinkron modell – az aszinkron modelleknél a várakozási időt végesnek tekintjük, de nincs olyan idődelta, amely után garantálni tudjuk, hogy a csomópont meghibásodott. Azok. A csomóponttól érkező üzenetek várakozási ideje tetszőlegesen hosszú lehet. Ez egy fontos meghatározás, és még fogunk róla beszélni.
A konszenzus fogalma elosztott rendszerekben
Mielőtt formálisan meghatároznánk a konszenzus fogalmát, vegyünk egy példát egy olyan helyzetre, ahol szükségünk van rá, nevezetesen - Állapot gépi replikáció.
Van néhány elosztott naplónk. Szeretnénk, ha konzisztens lenne, és az elosztott rendszer összes csomópontján azonos adatokat tartalmazna. Amikor az egyik csomópont megtanul egy új értéket, amelyet a naplóba írni fog, feladata az lesz, hogy felajánlja ezt az értéket az összes többi csomópontnak, így a napló minden csomóponton frissül, és a rendszer egy új konzisztens állapotba lép. Ebben az esetben fontos, hogy a csomópontok megegyezzenek egymással: minden csomópont egyetért abban, hogy a javasolt új érték helyes, minden csomópont elfogadja ezt az értéket, és csak ebben az esetben írhatja mindenki az új értéket a naplóba.
Más szóval: egyik csomópont sem kifogásolta, hogy relevánsabb információi vannak, és a javasolt érték helytelen volt. A csomópontok közötti egyetértés és az egyetlen helyes elfogadott érték megegyezése konszenzus egy elosztott rendszerben. Ezután azokról az algoritmusokról lesz szó, amelyek lehetővé teszik, hogy egy elosztott rendszer garantáltan konszenzusra jusson.
Formálisabban definiálhatunk egy konszenzus-algoritmust (vagy egyszerűen egy konszenzus-algoritmust) egy bizonyos függvényként, amely egy elosztott rendszert A állapotból B állapotba visz át. Ráadásul ezt az állapotot minden csomópont elfogadja, és minden csomópont megerősítheti. Mint kiderült, ez a feladat egyáltalán nem olyan triviális, mint amilyennek első pillantásra tűnik.
A konszenzus algoritmus tulajdonságai
A konszenzus algoritmusnak három tulajdonsággal kell rendelkeznie ahhoz, hogy a rendszer továbbra is létezhessen, és némi előrehaladást érjen el az állapotról állapotra való mozgásban:
- Megállapodás – minden megfelelően működő csomópontnak azonos értéket kell vennie (a cikkekben ezt a tulajdonságot biztonsági tulajdonságnak is nevezik). Minden jelenleg működő csomópontnak (nem hibásodott meg vagy veszítette el a kapcsolatot a többiekkel) meg kell állapodnia, és el kell fogadnia valamilyen végső közös értéket.
Itt fontos megérteni, hogy az általunk fontolóra vett elosztott rendszer csomópontjai megegyezni akarnak. Vagyis most olyan rendszerekről beszélünk, amelyekben valami egyszerűen meghibásodhat (például egy csomópont meghibásodik), de ebben a rendszerben biztosan nincsenek olyan csomópontok, amelyek szándékosan mások ellen dolgoznának (bizánci tábornokok feladata). Ennek a tulajdonságnak köszönhetően a rendszer konzisztens marad.
- Sértetlenség — ha minden megfelelően működő csomópont ugyanazt az értéket kínálja v, ami azt jelenti, hogy minden megfelelően működő csomópontnak el kell fogadnia ezt az értéket v.
- Befejezés – minden helyesen működő csomópont idővel felvesz egy bizonyos értéket (élesség tulajdonság), ami lehetővé teszi, hogy az algoritmus előrehaladjon a rendszerben. Minden egyes helyesen működő csomópontnak előbb-utóbb el kell fogadnia a végső értéket és meg kell erősítenie: „Számomra ez az érték igaz, egyetértek az egész rendszerrel.”
Példa a konszenzus algoritmus működésére
Bár az algoritmus tulajdonságai nem biztos, hogy teljesen egyértelműek. Ezért egy példával szemléltetjük, hogy a legegyszerűbb konszenzusos algoritmus milyen szakaszokon megy keresztül egy szinkron üzenetküldő modellel rendelkező rendszerben, amelyben minden csomópont az elvárásoknak megfelelően működik, az üzenetek nem vesznek el és nem törik el semmi (ez tényleg megtörténik?).
- Minden egy házassági ajánlattal (Propose) kezdődik. Tegyük fel, hogy egy kliens csatlakozott egy "Node 1" nevű csomóponthoz, és elindított egy tranzakciót, új értéket adva át a csomópontnak - O. Ezentúl az "1. csomópontot" fogjuk hívni. ajánlat. Javaslattevőként az „1. csomópont”-nak értesítenie kell az egész rendszert, hogy friss adatokkal rendelkezik, és üzenetet küld az összes többi csomópontnak: „Nézd! Az „O” jelentése jutott eszembe, és le akarom írni! Kérjük, erősítse meg, hogy az „O” betűt is rögzíti a naplójában.”
- A következő lépés a javasolt érték megszavazása (Szavazás). Mire való? Előfordulhat, hogy más csomópontok újabb információkat kaptak, és ugyanarról a tranzakcióról rendelkeznek adatokkal.
Amikor az „1. csomópont” elküldi a javaslatát, a többi csomópont ellenőrzi a naplójukban az eseményre vonatkozó adatokat. Ha nincs ellentmondás, a csomópontok közlik: „Igen, nincs más adatom ehhez az eseményhez. Az „O” érték a legfrissebb információ, amelyet megérdemelünk.”Minden más esetben a csomópontok válaszolhatnak az „1. csomópontra”: „Figyelj! Frissebb adataim vannak erről a tranzakcióról. Nem "O", hanem valami jobb."
A szavazás során a csomópontok döntésre jutnak: vagy mindannyian ugyanazt az értéket fogadják el, vagy egyikük ellene szavaz, jelezve, hogy frissebb adatai vannak.
- Ha a szavazás sikeres volt és mindenki mellette volt, akkor a rendszer egy új szakaszba lép – az érték elfogadása. Az „1. csomópont” összegyűjti a többi csomópont összes választ, és a következőket jelenti: „Mindenki egyetértett az „O” értékkel! Most hivatalosan kijelentem, hogy az „O” az új jelentésünk, mindenki számára ugyanaz! Írd le a kis könyvedbe, ne felejtsd el. Írd le a naplódba!”
- A fennmaradó csomópontok visszaigazolást küldenek (Elfogadva), hogy felírták az „O” értéket, ezalatt semmi új nem érkezett (egyfajta kétfázisú véglegesítés). E jelentős esemény után úgy tekintjük, hogy az elosztott tranzakció befejeződött.
Így a konszenzusos algoritmus egy egyszerű esetben négy lépésből áll: javaslattétel, szavazás (szavazás), elfogadás (elfogadás), elfogadás megerősítése (elfogadva).
Ha valamelyik lépésnél nem tudtunk megegyezni, akkor az algoritmus újraindul, figyelembe véve azon csomópontok információit, amelyek megtagadták a javasolt érték megerősítését.
Konszenzus algoritmus aszinkron rendszerben
Előtte minden zökkenőmentes volt, mert egy szinkron üzenetküldési modellről beszéltünk. De tudjuk, hogy a modern világban hozzászoktunk, hogy mindent aszinkron módon csináljunk. Hogyan működik egy hasonló algoritmus egy aszinkron üzenetküldési modellel rendelkező rendszerben, ahol úgy gondoljuk, hogy egy csomópont válaszának várakozási ideje tetszőlegesen hosszú lehet (egy csomópont meghibásodása egyébként szintén példaként értelmezhető, amikor egy csomópont tetszőlegesen hosszú ideig tud válaszolni ).
Most, hogy tudjuk, hogyan működik elvileg a konszenzus algoritmus, kérdés azoknak a kíváncsi olvasóknak, akik idáig eljutottak: egy N csomópontból álló rendszerben hány csomó hibásodhat meg egy aszinkron üzenetmodellel, hogy a rendszer még konszenzusra jusson?
A helyes válasz és indoklás a spoiler mögött van.A helyes válasz: 0. Ha egy aszinkron rendszerben akár csak egy csomópont is meghibásodik, a rendszer nem tud konszenzusra jutni. Ezt az állítást bizonyítja a bizonyos körökben jól ismert FLP-tétel (1985, Fischer, Lynch, Paterson, hivatkozás az eredetire a cikk végén): „Lehetetlen az elosztott konszenzus elérésére, ha legalább egy csomópont meghibásodik. .”
Srácok, akkor van egy probléma, megszoktuk, hogy minden aszinkron. És itt van. Hogyan lehet tovább élni?
Csak az elméletről beszéltünk, a matematikáról. Mit jelent a „konszenzus nem érhető el” a matematikai nyelvről a miénkre – mérnöki nyelvre – fordítva? Ez azt jelenti, hogy „nem mindig lehet elérni”, pl. Van olyan eset, amikor a konszenzus nem érhető el. Milyen esetről van szó?
Pontosan ezzel sérti a fent leírt élőképességet. Nincs közös megegyezésünk, és a rendszer nem haladhat előre (nem tud véges idő alatt befejezni) abban az esetben, ha nem kapunk választ minden csomóponttól. Mivel egy aszinkron rendszerben nincs megjósolható válaszidőnk, és nem tudhatjuk, hogy egy csomópont összeomlott-e, vagy csak hosszú ideig tart a válaszadás.
De a gyakorlatban találhatunk megoldást. Legyen az algoritmusunk hosszú ideig működőképes meghibásodások esetén (potenciálisan korlátlan ideig működhet). De a legtöbb esetben, amikor a legtöbb csomópont megfelelően működik, fejlődést tapasztalunk a rendszerben.
A gyakorlatban részlegesen szinkron kommunikációs modellekkel foglalkozunk. A részleges szinkront a következőképpen értjük: általános esetben van egy aszinkron modellünk, de formálisan bevezetik egy bizonyos időponthoz tartozó „globális stabilizációs idő” fogalmát.
Lehet, hogy ez a pillanat nem jön el sokáig, de egyszer el kell jönnie. Megszólal a virtuális ébresztőóra, és ettől a pillanattól kezdve meg tudjuk jósolni, hogy milyen idődeltára érkeznek az üzenetek. Ettől a pillanattól kezdve a rendszer aszinkronból szinkronba változik. A gyakorlatban pontosan ilyen rendszerekkel foglalkozunk.
A Paxos algoritmus konszenzusos problémákat old meg
egy olyan algoritmuscsalád, amely megoldja a részlegesen szinkron rendszerek konszenzusos problémáját, azzal a lehetőséggel, hogy egyes csomópontok meghibásodhatnak. A Paxos szerzője az . 1989-ben javasolta az algoritmus létezésének és helyességének formális bizonyítását.
De a bizonyíték korántsem triviálisnak bizonyult. Az első publikáció csak 1998-ban jelent meg (33 oldal), amely az algoritmust ismerteti. Mint kiderült, rendkívül nehéz volt megérteni, és 2001-ben megjelent a cikk magyarázata, amely 14 oldalt vett igénybe. A publikációk mennyiségét azért adjuk meg, hogy megmutassuk, a konszenzus problémája valójában egyáltalán nem egyszerű, és az ilyen algoritmusok mögött a legokosabb emberek hatalmas munkája húzódik meg.
Érdekesség, hogy maga Leslie Lamport is megjegyezte előadásában, hogy a második magyarázó cikkben egy állítás, egy sor van (nem részletezte, hogy melyik), amely többféleképpen értelmezhető. Emiatt a modern Paxos megvalósítások nagy része nem működik teljesen megfelelően.
Paxos munkájának részletes elemzéséhez több cikkre lenne szükség, ezért megpróbálom nagyon röviden átadni az algoritmus fő gondolatát. A cikkem végén található hivatkozásokban anyagokat találhat a téma további búvárkodásához.
Szerepek a Paxosnál
A Paxos algoritmus rendelkezik a szerepek fogalmával. Tekintsünk három főt (vannak módosítások további szerepekkel):
- Javaslattevők (a kifejezések használhatók: vezetők vagy koordinátorok). Ezek azok a srácok, akik valami új értéket tanulnak meg a felhasználótól, és átveszik a vezető szerepét. Feladatuk egy új értékre vonatkozó javaslati kör elindítása és a csomópontok további intézkedéseinek összehangolása. Sőt, a Paxos bizonyos helyzetekben több vezető jelenlétét is lehetővé teszi.
- Elfogadók (szavazók). Ezek olyan csomópontok, amelyek egy adott érték elfogadására vagy elutasítására szavaznak. Szerepük nagyon fontos, hiszen rajtuk múlik a döntés: milyen állapotba kerül (vagy nem) a rendszer a konszenzusos algoritmus következő szakasza után.
- A tanulók. Csomópontok, amelyek egyszerűen elfogadják és kiírják az új elfogadott értéket, amikor a rendszer állapota megváltozik. Nem hoznak döntéseket, csak megkapják az adatokat, és átadhatják a végfelhasználónak.
Egy csomópont több szerepet is kombinálhat különböző helyzetekben.
A határozatképesség fogalma
Feltételezzük, hogy van egy rendszerünk N csomópontok És közülük a maximum F csomópontok meghibásodhatnak. Ha az F csomópontok meghibásodnak, akkor legalább rendelkeznünk kell 2F+1 elfogadó csomópontok.
Erre azért van szükség, hogy a legrosszabb helyzetben is mindig meglegyen a legtöbb „jó” csomópont, amely megfelelően működik. Azaz F+1 "jó" csomópontok megegyeztek, és a végső érték elfogadásra kerül. Ellenkező esetben előfordulhat, hogy különböző helyi csoportjaink eltérő jelentést kapnak, és nem tudnak megegyezni egymás között. Ezért abszolút többségre van szükségünk a szavazás megnyeréséhez.
A Paxos konszenzus algoritmus működésének általános ötlete
A Paxos algoritmus két nagy fázisból áll, amelyek viszont két-két lépésre oszlanak:
- 1a fázis: Felkészülés. Az előkészítő szakaszban a vezető (ajánlattevő) minden csomópontot tájékoztat: „Új szavazási szakaszt indítunk. Új körünk van. Ennek a körnek a száma n. Most elkezdjük a szavazást." Egyelőre egyszerűen csak egy új ciklus kezdetét jelzi, de nem jelent új értéket. Ennek a szakasznak az a feladata, hogy egy új fordulót kezdeményezzen és mindenkit értesítsen annak egyedi számáról. A kerek szám fontos, nagyobbnak kell lennie, mint az összes korábbi vezető szavazati száma. Mert a kerek számnak köszönhetően a rendszer többi csomópontja megérti, hogy a vezető adatai mennyire frissek. Valószínű, hogy más csomópontok már rendelkeznek szavazási eredményekkel sokkal későbbi fordulókból, és egyszerűen azt mondják a vezetőnek, hogy le van maradva az időkről.
- 1b fázis: Ígéret. Ha az elfogadó csomópontok megkapták az új szavazási szakasz számát, két kimenetel lehetséges:
- Az új szavazat n száma nagyobb, mint bármely korábbi szavazás száma, amelyben az elfogadó részt vett. Ezután az elfogadó ígéretet küld a vezetőnek, hogy nem vesz részt több n-nél kisebb szavazáson. Ha az elfogadó valamire már szavazott (vagyis a második fázisban már elfogadott valamilyen értéket), akkor ígéretéhez csatolja az elfogadott értéket és annak a szavazatnak a számát, amelyben részt vett.
- Ellenkező esetben, ha az elfogadó már tud a magasabb számú szavazásról, egyszerűen figyelmen kívül hagyhatja az előkészítő lépést, és nem válaszol a vezetőnek.
- 2a fázis: Elfogadás. A vezetőnek meg kell várnia a határozatképesség (a rendszer csomópontjainak többsége) válaszát, és ha a szükséges számú válasz érkezik, akkor két lehetősége van az események fejlesztésére:
- Néhány elfogadó olyan értékeket küldött, amelyekre már szavazott. Ebben az esetben a vezető választja ki a szavazatból azt az értéket, amelyen a maximális szám szerepel. Nevezzük ezt az értéket x-nek, és egy üzenetet küld az összes csomópontnak, például: „Accept (n, x)”, ahol az első érték a saját Javaslat lépésének szavazati száma, a második pedig az, amire mindenki összegyűlt. azaz az az érték, amelyre valójában szavazunk.
- Ha egyik elfogadó sem küldött értéket, de egyszerűen megígérte, hogy ebben a körben szavaz, akkor a vezető felkérheti őket, hogy szavazzanak az értékükre, amiért eleve vezető lett. Nevezzük y-nek. Üzenetet küld az összes csomópontnak, például: „Accept (n, y)”, hasonlóan az előző eredményhez.
- 2b. fázis: Elfogadva. Továbbá az elfogadó csomópontok, miután megkapták az „Elfogadás(...)” üzenetet a vezetőtől, egyetértenek vele (csak akkor küldenek visszaigazolást minden csomópontnak, hogy egyetértenek az új értékkel), ha nem ígértek néhányat (egyéb) vezető részt venni a szavazáson kerek számmal n' > n, ellenkező esetben figyelmen kívül hagyják a megerősítési kérést.
Ha a csomópontok többsége válaszolt a vezetőnek, és mindegyik megerősítette az új értéket, akkor az új értéket elfogadottnak tekintjük. Hurrá! Ha nem érik el a többséget, vagy vannak olyan csomópontok, amelyek nem hajlandók elfogadni az új értéket, akkor minden kezdődik elölről.
Így működik a Paxos algoritmus. Mindegyik szakasznak számos finomsága van, gyakorlatilag nem vettük figyelembe a különféle típusú hibákat, több vezető problémáit és még sok mást, de ennek a cikknek az a célja, hogy magas szinten bemutassa az olvasót az elosztott számítástechnika világába.
Azt is érdemes megjegyezni, hogy a Paxos nem az egyetlen a maga nemében, vannak más algoritmusok is, pl. , de ez egy másik cikk témája.
Linkek a további tanulmányozáshoz szükséges anyagokhoz
Kezdő szint:
- , Preethi Kasireddy, blog cikk a Médiumról
- , Adi Kancherla, blog cikk a Médiumról
- , Ittai Abraham, blog
- , Ittai Abraham, blog cikk
Leslie Lamport szint:
- , Fischer, Lynch és Paterson, kutatási cikk, 1985
- , Leslie Lamport, kutatási cikk, 1998
- , Leslie Lamport, kutatási cikk, 2001
Forrás: will.com