Beste svaret
Denne artikkelen gir en slående klar forklaring og bevis: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Jeg prøver å gi et klart sammendrag her:
Målet med Paxos-algoritmen er for et visst antall jevnaldrende å oppnå enighet om en verdi. Paxos garanterer at hvis en jevnaldrende mener at det er enighet om en verdi med et flertall, vil flertallet aldri blir enige om en annen verdi. Protokollen er utformet slik at enhver avtale må gå gjennom et flertall av noder. Eventuelle fremtidige forsøk på avtale, hvis det lykkes, må også gå gjennom minst en av disse noder. Dermed: Enhver node som foreslår etter at en beslutning er nådd, må kommunisere med en node i flertall. Protokollen garanterer at den vil lære den tidligere ag setter pris på verdien fra det flertallet.
Slik fungerer det:
Anta at vi har 3 noder, A, B og C. A vil foreslå verdi «Foo.»
Algoritmen opererer i 3 faser. I hver fase må bekreftelse fra et flertall av noder nås.
Først har vi forberedelsesfasen. A sender en forberedelsesforespørsel til A, B og C. Paxos er avhengig av sekvensnummer til oppnå sine garantier. Forberedelsesforespørselen ber en node om å love: «Jeg vil aldri godta noe forslag med et sekvensnummer mindre enn det i forberedelsesforespørselen.» Nodene svarer med en hvilken som helst verdi de tidligere har avtalt (hvis noen). (Og dette er kritisk viktig): Node A må foreslå verdien den mottar med det høyeste sekvensnummeret. Denne handlingen gir garantien for at de tidligere avtalte verdiene blir bevart.
Deretter har vi godta fasen. A sender en godta forespørsel til A, B og C. Godta forespørselen sier: » Godtar du foo? » Hvis det medfølgende sekvensnummeret ikke er under det noden tidligere hadde lovet eller ber om at noden tidligere har akseptert, vil det akseptere den nye verdien og sekvensnummeret.
Hvis node A mottar godtar fra et flertall av noder, verdien er bestemt. Denne runden av Paxos vil aldri godta en annen verdi.
Den tredje fasen er ikke strengt nødvendig, men er en avgjørende optimalisering i enhver produksjonsprodusert Paxos-implementering. Etter at A mottar et flertall aksepter, sender den bestemte meldinger til A, B og C. Disse meldingene gir alle jevnaldrende beskjed om at en verdi er valgt, og akselererer slutten på beslutningsprosessen.
Uten denne meldingen måtte de andre jevnaldrende prøve å foreslå en verdi for å lære om avtalen. I forberedelsesfasen lærte de om den tidligere avtalte verdien. Når denne avtalen ble drevet til konklusjon, ville noden gjenkjenne avtalen.
Jeg har gledet over noen viktige spørsmål her:
- Alle sekvensnumre må øke monotont, og unikt per node . Det vil si at A og B ikke begge kan sende en melding med sekvensnummer k. Alle meldinger som sendes i protokollen inkluderer sekvensnummer. En node må spore den høyeste godkjennelsesforespørselen den har sett, så vel som den høyeste verdien den har lovet i forberedelsesfasen.
- Feilforhold. Det er fullt mulig for en runde Paxos å mislykkes. I tilfelle feil, prøver en node bare å foreslå igjen med et høyere sekvensnummer.
- Oppsigelsesbetingelser. Versjonen av Paxos jeg «har beskrevet, avsluttes ikke nødvendigvis. Noen få tilpasninger kreves for et formelt bevis på avslutning.
Svar
Siden Paxos oppnår konsensus, kan den også brukes til å replikere skriv i en distribuert database når den kan garantere jevn rekkefølge av hendelser blant alle nodene i en gruppe. Chubby by Google bruker Paxos for å servere sterkt konsistente filer. Det er her forvirringen følger fra. Hva er da forholdet mellom synkronisering og paxos hvis begge kan brukes til replikering?
Lite historie: Lamport introduserte begrepet replikering av statsmaskiner tidlig på 80-tallet. Statlig maskinreplikasjon betyr at et system leverer hendelser i samme rekkefølge til alle nodene, og de behandles deterministisk og garanterer konsistente tilstander på tvers av alle nodene i gruppen. Da konseptet ble introdusert, innebar det imidlertid alle slags antakelser, inkludert nettverket som var synkron.Så tilstandsmaskinreplikasjon forble bare et teoretisk verktøy uten praktisk bruk. Visningssynkronisering ble introdusert på dette punktet og hadde som mål å oppnå konsistens ved ikke å gjøre slike antagelser. Målet var å ha et praktisk system som gir slike garantier.
Publisering av Paxos skjedde mens synkroniseringsarbeidet pågikk. Paxos kunne oppnå replikering av tilstandsmaskiner, da replikaer nå kunne bli enige om utførelsesrekkefølgen for klientforespørsler ved hjelp av denne konsensusalgoritmen. Paxos antok ingen antakelser om synkront nettverk eller feil. Paxos leverte også en protokoll for gruppemedlemskap. Forskjellene som nå forble mellom synkronisering og Paxos var bare i måten abstraksjonene ble formulert på. Begge gir dynamisk medlemskap og håndterer feil på samme måte. Forskjellene er egentlig bare i modellen. Noen forskjeller som kan fremheves er:
- Virtual Synchrony har en enkel gruppemedlemskapsprotokoll sammenlignet med Paxos. Virtual Synchrony kjører gruppemedlemskap som en egen tjeneste.
- Paxos kan gjøre fremgang i visse tilfeller av partisjon der virtuell synkronisering blokkeres.
- Virtual Synchrony er raskere enn moderne Paxos.
Begge systemene har utviklet seg og konvergerte . Slik det ser ut i dag, er det veldig vanskelig å trekke noen signifikante forskjeller mellom de to.
Lalith forklarer tydelig Virtual Synchrony-protokollen og påpeker med rette at Paxos eller hvilken som helst annen konsensusvariant kan brukes i synkronisering. Paxos bortsett fra konsensus gir gruppemedlemskap og andre funksjoner som virtuell synkronisering allerede gir. Siden både virtuell synkronisering og Paxos gir samme garantier og ble utviklet omtrent samtidig, bruker spesifikasjonen av virtuell synkronisering ikke Paxos for konsensus. Virtuell synkronismodell bruker imidlertid den fullstendig ordnede sendeprotokollen (også kjent som ABCAST) for å oppnå atomkringkasting og en annen protokoll for å oppdatere gruppevisninger, og disse kan sees på som konsensusvarianten span> den bruker.
Det kan være interessant å merke seg at kjøretidsmodellen ISIS-2 kombinerer Paxos-modellen med den virtuelle synkroniseringsmodellen, ikke for konsensus, men for å ta ut gruppemedlemskap som en egen tjeneste i Paxos. Dette gjør Paxos raskere i tilfeller der medlemskap ikke endres dynamisk. Ved å kombinere Virtual Synchrony og Paxos, er ISIS2 i stand til å hoppe over visse trinn som typiske Paxos trenger å utføre. I hovedsak er Paxos og Virtual Synchrony forskjellige modeller for å oppnå samme funksjonalitet og kan kombineres med hverandre for å oppnå varianter eller optimaliseringer.