Joten kuvitellaan. Huoneessa on 5 kissaa lukittuna ja lähteäkseen herättämään omistajan, heidän kaikkien on sovittava tämä keskenään, koska he voivat avata oven vain viiden nojaten siihen. Jos yksi kissoista on Schrödingerin kissa ja muut kissat eivät tiedä hänen päätöksestään, herää kysymys: "Kuinka he voivat tehdä sen?"
Tässä artikkelissa kerron sinulle yksinkertaisesti hajautettujen järjestelmien maailman teoreettisesta komponentista ja niiden toimintaperiaatteista. Tarkastelen myös pintapuolisesti Paxoksen taustalla olevaa pääideaa.
Kun kehittäjät käyttävät pilviinfrastruktuureja, erilaisia tietokantoja ja työskentelevät useiden solmujen klustereissa, he luottavat siihen, että tiedot ovat täydellisiä, turvallisia ja aina saatavilla. Mutta missä ovat takuut?
Pohjimmiltaan antamamme takuut ovat toimittajatakuita. Ne on kuvattu dokumentaatiossa seuraavasti: "Tämä palvelu on melko luotettava, sillä on tietty SLA, älä huoli, kaikki toimii hajautetusti kuten odotat."
Meillä on tapana uskoa parhaaseen, koska isojen yritysten älykkäät kaverit vakuuttivat meille, että kaikki tulee olemaan hyvin. Emme kysy kysymystä: miksi tämä itse asiassa voi toimia ollenkaan? Onko tällaisten järjestelmien oikealle toiminnalle olemassa muodollisia perusteita?
Kävin äskettäin ja inspiroitui suuresti tästä aiheesta. Luennot koulussa olivat enemmän laskentatunteja kuin jotain tietokonejärjestelmiin liittyvää. Mutta juuri tällä tavalla tärkeimmät algoritmit, joita käytämme päivittäin, tietämättämme, todistettiin kerralla.
Useimmat nykyaikaiset hajautetut järjestelmät käyttävät Paxos-konsensusalgoritmia ja sen erilaisia muunnelmia. Hienointa on, että tämän algoritmin pätevyys ja periaatteessa koko olemassaolon mahdollisuus voidaan todistaa yksinkertaisesti kynällä ja paperilla. Käytännössä algoritmia käytetään suurissa järjestelmissä, jotka toimivat valtavalla määrällä pilvien solmuja.
Kevyt esimerkki siitä, mistä seuraavaksi keskustellaan: kahden kenraalin tehtäväKatsotaanpa lämmittelyä .
Meillä on kaksi armeijaa - punainen ja valkoinen. Valkoiset joukot sijaitsevat piiritetyssä kaupungissa. Kenraalien A1 ja A2 johtamat punaiset joukot sijaitsevat kahdella puolella kaupunkia. Punapäisten tehtävänä on hyökätä valkoista kaupunkia vastaan ja voittaa. Jokaisen punaisen kenraalin armeija erikseen on kuitenkin pienempi kuin valkoisen armeijan.
Punaisten voittoehdot: molempien kenraalien on hyökättävä samanaikaisesti saadakseen numeerisen edun valkoisiin nähden. Tätä varten kenraalien A1 ja A2 on päästävä sopimukseen keskenään. Jos kaikki hyökkäävät erikseen, punapäät häviävät.
Päästäkseen sopimukseen kenraalit A1 ja A2 voivat lähettää sanansaattajia toisilleen valkoisen kaupungin alueen läpi. Sanansaattaja voi onnistuneesti tavoittaa liittoutuneen kenraalin tai vihollinen voi siepata hänet. Kysymys: onko punatukkaisten kenraalien välillä olemassa sellaista viestintäjärjestystä (sanansaajien lähettäminen A1:stä A2:een ja päinvastoin A2:sta A1:een), jossa heidän taataan sopivan hyökkäyksestä tunnilla X. Tässä, takuut tarkoittavat, että molemmat kenraalit saavat yksiselitteisen vahvistuksen siitä, että liittolainen (toinen kenraali) hyökkää ehdottomasti määrättynä aikana X.
Oletetaan, että A1 lähettää viestin A2:lle sanomalla: "Hyökkäämme tänään keskiyöllä!" Kenraali A1 ei voi hyökätä ilman kenraalin A2 vahvistusta. Jos lähetti A1:ltä on saapunut, kenraali A2 lähettää vahvistuksen viestillä: "Kyllä, tapetaan valkoiset tänään." Mutta nyt kenraali A2 ei tiedä onko hänen sanansaattajansa saapunut vai ei, hänellä ei ole takeita siitä, tuleeko hyökkäys samanaikaisesti. Nyt General A2 tarvitsee jälleen vahvistuksen.
Heidän kommunikaatioidensa kuvaaminen paljastaa edelleen seuraavan: riippumatta siitä, kuinka monta viestijaksoa on, ei ole mitään keinoa taata, että molemmille kenraaleille on ilmoitettu, että heidän viestinsä on vastaanotettu (olettaen, että jompikumpi sanansaattaja voidaan siepata).
Two Generals -ongelma on loistava esimerkki hyvin yksinkertaisesta hajautetusta järjestelmästä, jossa on kaksi solmua, joiden viestintä on epäluotettavaa. Tämä tarkoittaa, että meillä ei ole 100-prosenttista takuuta niiden synkronoinnista. Samanlaisia ongelmia käsitellään vain suuremmassa mittakaavassa myöhemmin artikkelissa.
Esittelemme hajautettujen järjestelmien käsitteen
Hajautettu järjestelmä on ryhmä tietokoneita (jäljempänä kutsumme niitä solmuiksi), jotka voivat vaihtaa viestejä. Jokainen yksittäinen solmu on jonkinlainen itsenäinen kokonaisuus. Solmu voi käsitellä tehtäviä itse, mutta kommunikoidakseen muiden solmujen kanssa sen on lähetettävä ja vastaanotettava viestejä.
Miten viestit tarkalleen toteutetaan, mitä protokollia käytetään - tämä ei kiinnosta meitä tässä yhteydessä. On tärkeää, että hajautetun järjestelmän solmut voivat vaihtaa tietoja keskenään lähettämällä viestejä.
Määritelmä itsessään ei näytä kovin monimutkaiselta, mutta meidän on otettava huomioon, että hajautetussa järjestelmässä on useita meille tärkeitä ominaisuuksia.
Hajautettujen järjestelmien attribuutit
- samanaikaisuuden – samanaikaisten tai samanaikaisten tapahtumien mahdollisuus järjestelmässä. Lisäksi pidämme kahdessa eri solmussa tapahtuvia tapahtumia mahdollisesti samanaikaisina niin kauan kuin meillä ei ole näiden tapahtumien selkeää esiintymisjärjestystä. Mutta yleensä meillä ei ole sitä.
- Ei globaalia kelloa. Meillä ei ole selkeää tapahtumien järjestystä globaalin kellon puutteen vuoksi. Tavallisessa ihmisten maailmassa olemme tottuneet siihen, että meillä on kellot ja aika ehdottomasti. Kaikki muuttuu hajautettujen järjestelmien suhteen. Jopa erittäin tarkoissa atomikelloissa on ajautuminen, ja saattaa olla tilanteita, joissa emme voi kertoa, kumpi kahdesta tapahtumasta tapahtui ensin. Siksi emme myöskään voi luottaa aikaan.
- Järjestelmäsolmujen itsenäinen vika. On toinenkin ongelma: jokin voi mennä pieleen yksinkertaisesti siksi, että solmumme eivät kestä ikuisesti. Kiintolevy saattaa epäonnistua, pilvessä oleva virtuaalikone voi käynnistyä uudelleen, verkko saattaa vilkkua ja viestit katoavat. Lisäksi voi olla tilanteita, joissa solmut toimivat, mutta samalla toimivat järjestelmää vastaan. Viimeinen ongelmaluokka sai jopa erillisen nimen: ongelma . Suosituin esimerkki hajautetusta järjestelmästä, jolla on tämä ongelma, on Blockchain. Mutta tänään emme tarkastele tätä erityistä ongelmaluokkaa. Olemme kiinnostuneita tilanteista, joissa yksinkertaisesti yksi tai useampi solmu voi epäonnistua.
- Viestintämallit (viestintämallit) solmujen välillä. Olemme jo todenneet, että solmut kommunikoivat vaihtamalla viestejä. Tunnettuja viestintämalleja on kaksi: synkroninen ja asynkroninen.
Solmujen välisen viestinnän mallit hajautetuissa järjestelmissä
Synkroninen malli – Tiedämme varmasti, että on olemassa rajallinen aikadelta, jonka aikana viesti taatusti saapuu solmusta toiseen. Jos tämä aika on kulunut eikä viesti ole saapunut, voimme turvallisesti sanoa, että solmu on epäonnistunut. Tässä mallissa meillä on ennakoitavissa olevat odotusajat.
Asynkroninen malli – asynkronisissa malleissa katsotaan, että odotusaika on rajallinen, mutta sellaista aikadeltaa ei ole, jonka jälkeen voisimme taata, että solmu on epäonnistunut. Nuo. Solmun viestin odotusaika voi olla mielivaltaisen pitkä. Tämä on tärkeä määritelmä, ja puhumme siitä lisää.
Konsensuksen käsite hajautetuissa järjestelmissä
Ennen kuin määrittelemme muodollisesti konsensuksen käsitteen, tarkastellaan esimerkkiä tilanteesta, jossa tarvitsemme sitä, nimittäin - Tilan konereplikointi.
Meillä on jaettu loki. Haluamme sen olevan johdonmukainen ja sisältävän identtiset tiedot hajautetun järjestelmän kaikista solmuista. Kun yksi solmuista oppii uuden arvon, jonka se aikoo kirjoittaa lokiin, sen tehtävänä on tarjota tämä arvo kaikille muille solmuille, jotta loki päivitetään kaikissa solmuissa ja järjestelmä siirtyy uuteen johdonmukaiseen tilaan. Tässä tapauksessa on tärkeää, että solmut sopivat keskenään: kaikki solmut ovat yhtä mieltä siitä, että ehdotettu uusi arvo on oikea, kaikki solmut hyväksyvät tämän arvon ja vain tässä tapauksessa kaikki voivat kirjoittaa uuden arvon lokiin.
Toisin sanoen: yksikään solmu ei vastustanut sitä, että sillä oli enemmän oleellista tietoa, ja ehdotettu arvo oli virheellinen. Solmujen välinen sopimus ja yksimielisyys yhdestä oikeasta hyväksytystä arvosta on konsensus hajautetussa järjestelmässä. Seuraavaksi puhumme algoritmeista, joiden avulla hajautetun järjestelmän taataan pääsevän yksimielisyyteen.
Muodollisemmin voimme määritellä konsensusalgoritmin (tai yksinkertaisesti konsensusalgoritmin) tietyksi funktioksi, joka siirtää hajautetun järjestelmän tilasta A tilaan B. Lisäksi kaikki solmut hyväksyvät tämän tilan, ja kaikki solmut voivat vahvistaa sen. Kuten käy ilmi, tämä tehtävä ei ole ollenkaan niin triviaali kuin miltä näyttää ensi silmäyksellä.
Konsensusalgoritmin ominaisuudet
Konsensusalgoritmilla on oltava kolme ominaisuutta, jotta järjestelmä voi jatkaa olemassaoloaan ja edistyä jonkin verran tilasta toiseen:
- sopimus – kaikilla oikein toimivilla solmuilla on oltava sama arvo (artikkeleissa tätä ominaisuutta kutsutaan myös turvallisuusominaisuutena). Kaikkien tällä hetkellä toimivien solmujen (eivät ole epäonnistuneet tai menettäneet yhteyttä muihin) on päästävä sopimukseen ja hyväksyttävä jokin lopullinen yhteinen arvo.
Tässä on tärkeää ymmärtää, että harkitsemamme hajautetun järjestelmän solmut haluavat olla samaa mieltä. Eli puhumme nyt järjestelmistä, joissa jokin voi yksinkertaisesti epäonnistua (esimerkiksi jokin solmu epäonnistuu), mutta tässä järjestelmässä ei todellakaan ole solmuja, jotka toimivat tarkoituksella muita vastaan (bysantin kenraalien tehtävä). Tämän ominaisuuden ansiosta järjestelmä pysyy yhtenäisenä.
- Eheys — jos kaikki oikein toimivat solmut tarjoavat saman arvon v, mikä tarkoittaa, että jokaisen oikein toimivan solmun on hyväksyttävä tämä arvo v.
- Lopettaminen – kaikki oikein toimivat solmut saavat lopulta tietyn arvon (elävyysominaisuuden), mikä mahdollistaa algoritmin edistymisen järjestelmässä. Jokaisen yksittäisen oikein toimivan solmun on ennemmin tai myöhemmin hyväksyttävä lopullinen arvo ja vahvistettava se: "Minulle tämä arvo on totta, olen samaa mieltä koko järjestelmän kanssa."
Esimerkki konsensusalgoritmin toiminnasta
Vaikka algoritmin ominaisuudet eivät ehkä ole täysin selviä. Siksi havainnollistetaan esimerkillä, mitä vaiheita yksinkertaisin konsensusalgoritmi käy läpi synkronisen viestinvälitysmallin järjestelmässä, jossa kaikki solmut toimivat odotetusti, viestit eivät katoa eikä mikään katkea (tapahtuuko tämä todella?).
- Kaikki alkaa avioliittoehdotuksesta (Propose). Oletetaan, että asiakas liittyi solmuun nimeltä "Node 1" ja aloitti tapahtuman välittäen uuden arvon solmulle - O. Tästä eteenpäin kutsumme "Solmu 1" tarjous. Ehdotuksen tekijänä "Solmun 1" on nyt ilmoitettava koko järjestelmälle, että sillä on tuoretta dataa, ja se lähettää kaikille muille solmuille viestin: "Katso! Merkitys "O" tuli mieleeni ja haluan kirjoittaa sen ylös! Vahvista, että kirjoitat myös "O" lokiisi."
- Seuraava vaihe on äänestäminen ehdotetun arvon puolesta (äänestys). Mitä varten se on? Saattaa käydä niin, että muut solmut ovat saaneet tuoreempaa tietoa ja heillä on tietoa samasta tapahtumasta.
Kun solmu “Node 1” lähettää ehdotuksensa, muut solmut tarkistavat lokeistaan tämän tapahtuman tiedot. Jos ristiriitoja ei ole, solmut ilmoittavat: ”Kyllä, minulla ei ole muita tietoja tästä tapahtumasta. "O"-arvo on viimeisin tieto, jonka ansaitsemme."Kaikissa muissa tapauksissa solmut voivat vastata "solmuun 1": "Kuuntele! Minulla on tuoreempaa tietoa tästä kaupasta. Ei "O", vaan jotain parempaa."
Äänestysvaiheessa solmut tekevät päätöksen: joko kaikki hyväksyvät saman arvon tai yksi äänestää vastaan, mikä osoittaa, että hänellä on tuoreempia tietoja.
- Jos äänestyskierros onnistui ja kaikki kannattivat, järjestelmä siirtyy uuteen vaiheeseen - arvon hyväksymiseen. "Solmu 1" kerää kaikki vastaukset muilta solmuilta ja raportoi: "Kaikki olivat yhtä mieltä arvosta "O"! Nyt julistan virallisesti, että "O" on uusi merkityksemme, sama kaikille! Kirjoita se pieneen kirjaasi, älä unohda. Kirjoita se lokiisi!"
- Loput solmut lähettävät vahvistuksen (Hyväksytty), että he ovat kirjoittaneet arvon "O"; mitään uutta ei ole saapunut tänä aikana (eräänlainen kaksivaiheinen vahvistus). Tämän merkittävän tapahtuman jälkeen katsomme, että hajautettu tapahtuma on suoritettu.
Siten konsensusalgoritmi yksinkertaisessa tapauksessa koostuu neljästä vaiheesta: ehdota, äänestä (äänestys), hyväksy (hyväksy), vahvista hyväksyntä (hyväksytty).
Jos emme jossain vaiheessa päässeet yhteisymmärrykseen, algoritmi käynnistyy uudelleen ottaen huomioon niiden solmujen tiedot, jotka kieltäytyivät vahvistamasta ehdotettua arvoa.
Konsensusalgoritmi asynkronisessa järjestelmässä
Ennen tätä kaikki oli sujuvaa, koska puhuimme synkronisesta viestintämallista. Mutta tiedämme, että nykymaailmassa olemme tottuneet tekemään kaiken asynkronisesti. Kuinka samanlainen algoritmi toimii järjestelmässä, jossa on asynkroninen viestintämalli, jossa uskomme, että solmun vastauksen odotusaika voi olla mielivaltaisen pitkä (muuten, solmun vikaa voidaan pitää myös esimerkkinä, kun solmu voi vastata mielivaltaisen pitkän ajan ).
Nyt kun tiedämme, miten konsensusalgoritmi periaatteessa toimii, kysymys niille uteliaille lukijoille, jotka ovat päässeet tähän asti: kuinka monta solmua N solmun järjestelmässä, jossa on asynkroninen viestimalli, voi epäonnistua, jotta järjestelmä voi silti päästä konsensukseen?
Oikea vastaus ja perustelut ovat spoilerin takana.Oikea vastaus on: 0. Jos yksikin solmu asynkronisessa järjestelmässä epäonnistuu, järjestelmä ei pääse yksimielisyyteen. Tämä väite on todistettu FLP-lauseessa, joka tunnetaan hyvin tietyissä piireissä (1985, Fischer, Lynch, Paterson, linkki alkuperäiseen artikkelin lopussa): "Mahdottomuus saavuttaa hajautettua konsensusta, jos vähintään yksi solmu epäonnistuu .”
Kaverit, sitten meillä on ongelma, olemme tottuneet siihen, että kaikki on asynkronista. Ja tässä se on. Kuinka jatkaa elämää?
Puhuimme vain teoriasta, matematiikasta. Mitä "konsensusta ei voida saavuttaa" tarkoittaa käännettynä matemaattisesta kielestä omaan - tekniikkaan? Tämä tarkoittaa, että "aina ei voida saavuttaa", ts. On tapaus, jossa yksimielisyyttä ei voida saavuttaa. Millainen tapaus tämä on?
Tämä on juuri edellä kuvatun eloisuusominaisuuden loukkaus. Meillä ei ole yhteistä sopimusta, eikä järjestelmä voi edistyä (ei voi valmistua rajallisessa ajassa), jos meillä ei ole vastausta kaikista solmuista. Koska asynkronisessa järjestelmässä meillä ei ole ennustettavaa vasteaikaa, emmekä voi tietää, onko solmu kaatunut vai kestääkö sen vastaaminen vain kauan.
Mutta käytännössä voimme löytää ratkaisun. Anna algoritmimme toimia pitkään vikojen sattuessa (mahdollisesti se voi toimia loputtomiin). Mutta useimmissa tilanteissa, kun useimmat solmut toimivat oikein, järjestelmä edistyy.
Käytännössä käsittelemme osittain synkronisia viestintämalleja. Osittainen synkronointi ymmärretään seuraavasti: yleisessä tapauksessa meillä on asynkroninen malli, mutta muodollisesti otetaan käyttöön tietty käsite tietyn ajankohdan "globaalista stabilointiajasta".
Tämä hetki ei voi tulla pitkäksi aikaa, mutta sen täytyy tulla jonain päivänä. Virtuaalinen herätyskello soi, ja siitä hetkestä lähtien voimme ennustaa aikadeltan, jolle viestit saapuvat. Tästä hetkestä lähtien järjestelmä muuttuu asynkronisesta synkroniseksi. Käytännössä käsittelemme juuri tällaisia järjestelmiä.
Paxos-algoritmi ratkaisee konsensusongelmia
on algoritmiperhe, joka ratkaisee osittain synkronisten järjestelmien konsensusongelman sillä mahdollisuudella, että jotkin solmut saattavat epäonnistua. Paxoksen kirjoittaja on . Hän ehdotti muodollista todistetta algoritmin olemassaolosta ja oikeellisuudesta vuonna 1989.
Mutta todiste osoittautui kaukana triviaalista. Ensimmäinen algoritmia kuvaava julkaisu julkaistiin vasta vuonna 1998 (33 sivua). Kuten kävi ilmi, se oli erittäin vaikea ymmärtää, ja vuonna 2001 artikkelista julkaistiin selitys, joka kesti 14 sivua. Julkaisujen määrä on annettu osoittamaan, että itse asiassa konsensuksen ongelma ei ole ollenkaan yksinkertainen, ja tällaisten algoritmien takana on valtava määrä älykkäimpien ihmisten työtä.
On mielenkiintoista, että Leslie Lamport itse totesi luennossaan, että toisessa selittävässä artikkelissa on yksi lausunto, yksi rivi (hän ei täsmentänyt, mikä), jota voidaan tulkita eri tavoin. Ja tämän vuoksi monet nykyaikaiset Paxos-toteutukset eivät toimi täysin oikein.
Yksityiskohtainen analyysi Paxoksen työstä vaatisi useamman artikkelin, joten yritän hyvin lyhyesti välittää algoritmin pääidean. Artikkelini lopussa olevista linkeistä löydät materiaalia tämän aiheen syventämiseen.
Roolit Paxosissa
Paxos-algoritmissa on roolikonsepti. Tarkastellaan kolmea pääasiallista (muokkauksia on lisärooleilla):
- Hakijat (termejä voidaan käyttää myös: johtajat tai koordinaattorit). Nämä ovat tyyppejä, jotka oppivat uutta arvoa käyttäjältä ja ottavat johtajan roolin. Heidän tehtävänsä on käynnistää ehdotuskierros uudelle arvolle ja koordinoida solmujen jatkotoimia. Lisäksi Paxos mahdollistaa useiden johtajien läsnäolon tietyissä tilanteissa.
- Hyväksyjät (äänestäjät). Nämä ovat solmuja, jotka äänestävät tietyn arvon hyväksymisestä tai hylkäämisestä. Heidän roolinsa on erittäin tärkeä, koska päätös riippuu heistä: mihin tilaan järjestelmä menee (tai ei mene) konsensusalgoritmin seuraavan vaiheen jälkeen.
- oppijat. Solmut, jotka vain hyväksyvät ja kirjoittavat uuden hyväksytyn arvon, kun järjestelmän tila on muuttunut. He eivät tee päätöksiä, he vain vastaanottavat tiedot ja voivat antaa sen loppukäyttäjälle.
Yksi solmu voi yhdistää useita rooleja eri tilanteissa.
Päätösvaltaisuuden käsite
Oletetaan, että meillä on järjestelmä N solmut Ja niistä maksimi F solmut voivat epäonnistua. Jos F-solmut epäonnistuvat, meillä on oltava vähintään 2F+1 hyväksyjäsolmut.
Tämä on välttämätöntä, jotta meillä on aina, pahimmassakin tilanteessa, suurin osa "hyvistä" solmuista, jotka toimivat oikein. Tuo on F+1 "hyviä" solmuja, jotka sopivat, ja lopullinen arvo hyväksytään. Muuten voi syntyä tilanne, jossa erilaiset paikalliset ryhmämme saavat erilaisia merkityksiä eivätkä pääse yksimielisyyteen keskenään. Siksi tarvitsemme ehdottoman enemmistön voittaaksemme äänestyksen.
Yleinen idea Paxos-konsensusalgoritmin toiminnasta
Paxos-algoritmi sisältää kaksi suurta vaihetta, jotka puolestaan on jaettu kahteen vaiheeseen:
- Vaihe 1a: Valmistaudu. Valmisteluvaiheessa johtaja (ehdotuksen tekijä) ilmoittaa kaikille solmuille: ”Aloitamme uuden äänestysvaiheen. Meillä on uusi kierros. Tämän kierroksen numero on n. Nyt aletaan äänestää." Toistaiseksi se vain raportoi uuden syklin alkamisen, mutta ei ilmoita uutta arvoa. Tämän vaiheen tehtävänä on käynnistää uusi kierros ja ilmoittaa kaikille sen yksilöllinen numero. Pyöreä numero on tärkeä, sen on oltava suurempi kuin kaikkien aikaisempien johtajien äänestysnumerot. Koska pyöreän luvun ansiosta muut järjestelmän solmut ymmärtävät kuinka tuoretta johtajan tiedot ovat. On todennäköistä, että muilla solmuilla on jo äänestystuloksia paljon myöhemmiltä kierroksilta ja ne kertovat johtajalle, että hän on ajastaan jäljessä.
- Vaihe 1b: Lupaus. Kun hyväksyjäsolmut saivat uuden äänestysvaiheen numeron, kaksi lopputulosta on mahdollista:
- Uuden äänen numero n on suurempi kuin minkä tahansa edellisen äänestyksen lukumäärä, johon hyväksyjä osallistui. Sitten hyväksyjä lähettää johtajalle lupauksen, että se ei osallistu enää äänestyksiin, joiden numero on pienempi kuin n. Jos hyväksyjä on jo äänestänyt jotain (eli on jo hyväksynyt jonkin arvon toisessa vaiheessa), se liittää lupaukseensa hyväksytyn arvon ja äänestyksen numeron, johon se osallistui.
- Muussa tapauksessa, jos hyväksyjä tietää jo suuremman numeron annetusta äänestyksestä, se voi yksinkertaisesti jättää valmisteluvaiheen huomiotta ja olla vastaamatta johtajalle.
- Vaihe 2a: Hyväksy. Johtajan on odotettava vastausta päätösvaltaiselta (valtaosa järjestelmän solmuista) ja jos vaadittu määrä vastauksia saadaan, hänellä on kaksi vaihtoehtoa tapahtumien kehittämiseen:
- Jotkut hyväksyjistä lähettivät arvoja, joita he olivat jo äänestäneet. Tässä tapauksessa johtaja valitsee äänestyksestä arvon, jolla on enimmäismäärä. Kutsutaan tätä arvoa x, ja se lähettää kaikille solmuille viestin, kuten: "Hyväksy (n, x)", jossa ensimmäinen arvo on äänestysnumero omasta ehdotusvaiheestaan ja toinen arvo on se, mitä varten kaikki kokoontuivat, eli arvo, jota todella äänestämme.
- Jos kukaan hyväksyjistä ei lähettänyt arvoja, mutta he yksinkertaisesti lupasivat äänestää tällä kierroksella, johtaja voi kutsua heidät äänestämään arvoaan, jonka johtajaksi hän alun perin tulikin. Kutsutaan sitä y:ksi. Se lähettää viestin kaikille solmuille, kuten: "Hyväksy (n, y)", samanlainen kuin edellinen tulos.
- Vaihe 2b: Hyväksytty. Lisäksi hyväksyjäsolmut, saatuaan "Hyväksy(...)" -viestin johtajalta, hyväksyvät sen (lähettävät vahvistuksen kaikille solmuille, että he ovat samaa mieltä uudesta arvosta) vain, jos he eivät ole luvanneet jotain (muuta) ) johtaja osallistua äänestykseen pyöreällä numerolla n'> n, muuten he jättävät vahvistuspyynnön huomiotta.
Jos suurin osa solmuista vastasi johtajalle ja kaikki vahvistivat uuden arvon, uusi arvo katsotaan hyväksytyksi. Hurraa! Jos enemmistöä ei saavuteta tai on solmuja, jotka kieltäytyivät hyväksymästä uutta arvoa, kaikki alkaa alusta.
Näin Paxos-algoritmi toimii. Jokaisella näistä vaiheista on monia hienouksia, emme käytännössä tarkastelleet erilaisia vikoja, useiden johtajien ongelmia ja paljon muuta, mutta tämän artikkelin tarkoituksena on vain esitellä lukija hajautetun laskennan maailmaan korkealla tasolla.
On myös syytä huomata, että Paxos ei ole ainoa laatuaan, on olemassa muitakin algoritmeja, esim. , mutta tämä on toisen artikkelin aihe.
Linkkejä materiaaliin lisätutkimuksia varten
Aloittelijataso:
- , Preethi Kasireddy, blogiartikkeli Mediumista
- , Adi Kancherla, blogiartikkeli Mediumista
- , Ittai Abraham, blogi
- , Ittai Abraham, blogiartikkeli
Leslie Lamportin taso:
- , Fischer, Lynch ja Paterson, tutkimuspaperi, 1985
- , Leslie Lamport, tutkimuspaperi, 1998
- , Leslie Lamport, tutkimuspaperi, 2001
Lähde: will.com