Paras vastaus
Tämä artikkeli tarjoaa hämmästyttävän selkeän selityksen ja todistuksen: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Yritän antaa selkeän yhteenvedon täältä:
Paxos-algoritmin on määrä vertaisjoukkoja pääsemään sopimukseen arvosta. Paxos takaa, että jos yksi vertainen uskoo, että jokin arvo on sovittu enemmistöllä, enemmistö ei koskaan sovi eri arvosta. Protokolla on suunniteltu siten, että kaikkien sopimusten täytyy mennä solmun enemmistön kautta. Mahdolliset tulevat sopimusehdot, jos ne onnistuvat, on myös suoritettava vähintään yhden näistä solmuista. Siten: Kaikkien solmien, jotka ehdottavat päätöksen tekemisen jälkeen, on oltava kommunikoida solmun kanssa enemmistössä.Protokolla takaa, että se oppii aiemmin ag hyötyä tuon enemmistön arvosta.
Näin se toimii:
Oletetaan, että meillä on 3 solmua, A, B ja C. A haluaa ehdottaa arvo ”Foo”.
Algoritmi toimii kolmessa vaiheessa. Jokaisessa vaiheessa on saavutettava vahvistus solmujen enemmistöltä.
Ensinnäkin meillä on valmisteluvaihe. A lähettää valmistelupyynnön A: lle, B: lle ja C: lle. Paxos luottaa järjestysnumeroihin saavuttaa takuut. Valmistelupyyntö pyytää solmua lupaamaan: ”En koskaan hyväksy yhtään ehdotusta, jonka järjestysnumero on pienempi kuin valmistelupyynnössä.” Solmut vastaavat kaikilla arvoilla, joihin ne ovat aiemmin sopineet (jos sellaisia on). (Ja tämä on kriittisen tärkeää): Solmun A on ehdotettava arvo, jonka se saa suurimmalla järjestysnumerolla. Tämä toiminto takaa aiemmin sovitut arvot.
Seuraavaksi meillä on hyväksymisvaihe. A lähettää hyväksymispyynnön A: lle, B: lle ja C: lle. Hyväksymispyynnössä todetaan: ” Hyväksytkö foo? ” Jos mukana oleva järjestysnumero ei ole sen solmun alapuolella, jonka solmu oli aiemmin luvannut tai jonka solmu on aiemmin hyväksynyt, se hyväksyy uuden arvon ja järjestysnumeron.
Jos solmu A vastaanottaa hyväksynnän suurin osa solmuista, arvo päätetään. Tämä Paxos-kierros ei koskaan suostu toiseen arvoon.
Kolmas vaihe ei ole ehdottoman välttämätön, mutta on tärkeä optimointi kaikissa tuotetuissa Paxos-sovelluksissa. Kun A on saanut enemmistön hyväksynnöistä, se lähettää päättetyt viestit osoitteeseen A, B ja C. Nämä viestit kertovat kaikille vertaiskäyttäjille, että arvo on valittu, ja nopeuttavat päätöksentekoprosessin päättymistä.
Ilman tätä viestiä muiden vertaisryhmien olisi yritettävä ehdottaa arvoa sopimuksesta oppimiseksi. Valmisteluvaiheessa he oppivat aiemmin sovitusta arvosta. Kun sopimus on saatu päätökseen, solmu tunnistaa sopimuksen.
Olen esittänyt muutamia keskeisiä kysymyksiä tässä:
- Kaikkien järjestysnumeroiden on oltava monotonisesti kasvavia ja yksilöllisiä solmua kohden . Toisin sanoen A ja B eivät molemmat voi lähettää viestiä järjestysnumerolla k. Kaikki protokollassa lähetetyt viestit sisältävät järjestysnumerot. Solmun on seurattava korkeinta hyväksymispyyntöä, jonka se on nähnyt, sekä korkeimman arvon, jonka se on luvannut valmisteluvaiheessa.
- Epäonnistumisolosuhteet. On täysin mahdollista, että kierros Paxosia epäonnistuu. Epäonnistumisen yhteydessä yksi solmu yksinkertaisesti yrittää ehdottaa uudelleen suuremmalla järjestysnumerolla.
- Loppuehdot. Kuvaamani Paxos-versio ei välttämättä lopu. Muutama muutos vaaditaan virallisen lopetustodistuksen saamiseksi.
Vastaus
Koska Paxos saavuttaa yksimielisyyden, sitä voidaan käyttää myös kopioimaan kirjoituksia hajautetussa tietokannassa, kun se voi taata tapahtumien yhdenmukaisen järjestyksen ryhmän kaikkien solmujen välillä. Chubby by Google käyttää Paxosia vahvasti yhdenmukaisten tiedostojen tarjoamiseen. Täältä syntyy sekaannus. Mikä on sitten näkymän synkronoinnin ja pakettien suhde, jos molempia voidaan käyttää replikointiin?
Pieni historia: Lamport esitteli valtion koneiden replikoinnin käsitteen 80-luvun alussa. Tilakoneen replikointi tarkoittaa, että järjestelmä toimittaa tapahtumia samassa järjestyksessä kaikille solmuille ja ne käsitellään deterministisesti taaten yhdenmukaiset tilat kaikissa ryhmän solmuissa. Siihen aikaan, kun tämä käsite otettiin käyttöön, siihen sisältyi kaikenlaisia oletuksia, mukaan lukien verkon synkronointi.Joten tilakoneen replikointi pysyi vain teoreettisena työkaluna ilman käytännön käyttöä. Näkymäsynkronia otettiin käyttöön tässä vaiheessa ja sen tarkoituksena oli saavuttaa johdonmukaisuus tekemättä mitään tällaisia oletuksia. Tavoitteena oli saada käytännön järjestelmä, joka antaa tällaiset takuut.
Paxos julkaistiin, kun näkymien synkronointityö oli käynnissä. Paxos pystyi saavuttamaan tilakoneen replikoinnin, koska kopiot pystyivät nyt sopimaan asiakaspyyntöjen suoritusjärjestyksestä tämän konsensusalgoritmin avulla. Paxos ei tehnyt oletuksia synkronisesta verkosta tai virheistä. Paxos toimitti myös ryhmäjäsenyysprotokollan. Näkymäsynkronian ja Paxosin välillä jäljellä olevat erot olivat vain abstraktien muotoilussa. Molemmat tarjoavat dynaamisen jäsenyyden ja käsittelevät epäonnistumisia samalla tavalla. Erot ovat oikeastaan vain mallissa. Joitakin korostettavia eroja ovat:
- Virtuaalisynkronoinnilla on yksinkertainen ryhmäjäsenyysprotokolla verrattuna Paxosiin. Virtuaalinen synkronointi hoitaa ryhmäjäsenyyden erillisenä palveluna.
- Paxos voi edistyä tietyissä osiointitapauksissa, joissa virtuaalinen synkronointi estää.
- Virtuaalinen synkronointi on nopeampaa kuin nykyiset Paxot.
Molemmissa järjestelmissä on kehittynyt ja lähentynyt . Nykyään on erittäin vaikea tehdä merkittäviä eroja näiden kahden välillä.
Lalith selittää selvästi Virtual Synchrony -protokollan ja huomauttaa perustellusti, että Paxosia tai mitä tahansa muuta konsensusvaihtoehtoa voidaan käyttää näkymän synkronoinnissa. Paxos tarjoaa konsensuksen lisäksi ryhmään kuulumisen ja muita ominaisuuksia, jotka virtuaalinen synkronointi jo tarjoaa. Koska sekä virtuaalinen synkronointi että Paxos tarjoavat samat takuut ja ne on kehitetty samaan aikaan, virtuaalisen synkronoinnin määrittely ei käytä Paxosia konsensukseen. Virtuaalinen synkronismalli käyttää kuitenkin täysin järjestettyä lähetysprotokollaa (tunnetaan myös nimellä ABCAST) atomilähetyksen aikaansaamiseksi ja toista protokollaa ryhmänäkymien päivittämiseen, ja ne voidaan nähdä konsensusvaihtoehtona se käyttää.
Voi olla mielenkiintoista huomata, että ISIS-2-ajonaikaisessa mallissa Paxos-malli yhdistetään Virtual Synchrony -malliin, ei konsensuksen vuoksi, vaan ryhmän jäsenyyden huomioon ottamiseksi erillisenä palveluna Paxosissa. Tämä tekee Paxoksesta nopeamman tapauksissa, joissa jäsenyys ei muutu dynaamisesti. Yhdistämällä virtuaalisen synkronoinnin ja Paxot ISIS2 pystyy ohittamaan tietyt vaiheet, jotka tyypillisten Paxojen on suoritettava. Pohjimmiltaan Paxos ja Virtual Synchrony ovat erilaisia malleja saman toiminnallisuuden saavuttamiseksi ja ne voidaan yhdistää keskenään muunnosten tai optimointien saavuttamiseksi.