Bedste svar
Dette papir giver en slående klar forklaring og bevis: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Jeg forsøger at give et klart resume her:
Målet med Paxos-algoritmen er for, at et antal kammerater skal nå til enighed om en værdi. Paxos garanterer, at hvis en kammerat mener, at en værdi er aftalt med et flertal, vil flertallet aldrig er enige om en anden værdi. Protokollen er designet, så enhver aftale skal gå gennem et flertal af noder. Eventuelle fremtidige forsøg på aftale, hvis det lykkes, skal også gå gennem mindst en af disse noder. Således: Enhver node, der foreslår, når en beslutning er nået, skal kommunikere med en node i flertallet. Protokollen garanterer, at den lærer den tidligere ag reed på værdi fra dette flertal.
Sådan fungerer det:
Antag, at vi har 3 noder, A, B og C. A vil gerne foreslå værdi “Foo.”
Algoritmen fungerer i 3 faser. I hver fase skal bekræftelse fra et flertal af noder nås.
Først har vi forberedelsesfasen. A sender en forbered anmodning til A, B og C. Paxos er afhængig af sekvensnumre til opnå sine garantier. Forberedelsesanmodningen beder en node om at love: “Jeg accepterer aldrig ethvert forslag med et sekvensnummer, der er mindre end det, der er i forberedelsesanmodningen.” Knudepunkterne svarer med enhver værdi, de tidligere har accepteret (hvis nogen). (Og dette er kritisk vigtigt): Node A skal foreslå den værdi, den modtager med det højeste sekvensnummer. Denne handling giver garanti for, at de tidligere aftalte værdier bevares.
Dernæst har vi acceptfasen. A sender en acceptanmodning til A, B og C. I acceptanmodningen hedder det: ” Accepterer du foo? ” Hvis det ledsagende sekvensnummer ikke er under det, som noden tidligere havde lovet eller anmoder om, at noden tidligere har accepteret, accepterer det den nye værdi og sekvensnummeret.
Hvis node A modtager accepterer fra et flertal af noder, værdien er bestemt. Denne runde af Paxos vil aldrig acceptere en anden værdi.
Den tredje fase er ikke strengt nødvendig, men er en afgørende optimering i enhver produceret Paxos-implementering. Når A modtager et flertal af accepter, sender den besluttede meddelelser til A, B og C. Disse meddelelser fortæller alle jævnaldrende, at der er valgt en værdi og fremskynder afslutningen på beslutningsprocessen.
Uden denne besked skulle de andre jævnaldrende forsøge at foreslå en værdi for at lære af aftalen. I forberedelsesfasen lærte de om den tidligere aftalte værdi. Når denne aftale var drevet til afslutning, ville noden genkende aftalen.
Jeg har gennemgået et par vigtige spørgsmål her:
- Alle sekvensnumre skal være monotont stigende og unikke pr. node . Det vil sige, A og B kan ikke begge sende en besked med sekvensnummer k. Alle meddelelser, der sendes i protokollen, inkluderer sekvensnumre. En node skal spore den højeste acceptanmodning, den har set, såvel som den højeste værdi, den har lovet i forberedelsesfasen.
- Fejlforhold. Det er meget muligt for en runde Paxos at mislykkes. I tilfælde af fejl forsøger en node blot at foreslå igen med et højere sekvensnummer.
- Opsigelsesbetingelser. Den version af Paxos I, der er beskrevet, slutter ikke nødvendigvis. Et par tweaks er nødvendige for et formelt bevis for opsigelse.
Svar
Da Paxos opnår konsensus, kan det også bruges til at replikere skrivninger i en distribueret database, da det kan garantere ensartet rækkefølge af begivenheder blandt alle noder i en gruppe. Chubby by Google bruger Paxos til at levere stærkt konsistente filer. Det er her forvirringen følger fra. Hvad er så forholdet mellem synkronisering og paxos, hvis begge kan bruges til replikering?
Lille historie: Lamport introducerede begrebet replikering af statsmaskiner tidligt i 80erne. Replikering af statsmaskiner betyder, at et system leverer hændelser i samme rækkefølge til alle knudepunkterne, og de behandles deterministisk og garanterer ensartede tilstande på tværs af alle knudepunkter i gruppen. På det tidspunkt, hvor dette koncept blev introduceret, medførte det imidlertid alle mulige antagelser, herunder at netværket var synkron.Så tilstandsmaskinreplikering forblev blot et teoretisk værktøj uden praktisk brug. Visningssynkron blev introduceret på dette tidspunkt og havde til formål at opnå konsistens ved ikke at antage sådanne antagelser. Målet var at have et praktisk system, der giver sådanne garantier.
Offentliggørelse af Paxos skete, mens synkroniseringsarbejdet var i gang. Paxos kunne opnå replikering af statsmaskiner, da replikaer nu kunne blive enige om udførelsesrækkefølgen for klientanmodninger ved hjælp af denne konsensusalgoritme. Paxos antog ingen antagelser om synkront netværk eller fejl. Paxos leverede også en protokol til gruppemedlemskab. Forskellene, der nu forblev mellem synkronisering og Paxos, var kun i den måde abstraktionerne blev formuleret på. Begge giver dynamisk medlemskab og håndterer fejl på samme måde. Forskellene er egentlig kun i modellen. Nogle forskelle, der kan fremhæves, er:
- Virtual Synchrony har en simpel gruppemedlemskabsprotokol sammenlignet med Paxos. Virtual Synchrony kører gruppemedlemskab som en separat tjeneste.
- Paxos kan muligvis gøre fremskridt i visse tilfælde af partitioner, hvor virtuel synkronisering blokerer.
- Virtual Synchrony er hurtigere end nutidige Paxos.
Begge systemer har udviklet og konvergeret . Som det er i dag, er det meget vanskeligt at tegne nogen væsentlige forskelle mellem de to.
Lalith forklarer tydeligt Virtual Synchrony-protokollen og påpeger med rette, at Paxos eller enhver anden konsensusvariant kan bruges i synkronisering. Paxos bortset fra konsensus giver gruppemedlemskab og andre funktioner, som virtuel synkronisering allerede giver. Da både virtuel synkronisering og Paxos giver samme garantier og blev udviklet omkring samme tid, bruger specifikationen af virtuel synkronisering ikke Paxos til konsensus. Virtuel synkronmodel bruger dog den totalt ordnede sendeprotokol (også kendt som ABCAST) for at opnå atomudsendelse og en anden protokol til opdatering af gruppevisninger, og disse kan ses som konsensusvariant det bruger.
Det kan være interessant at bemærke, at ISIS-2 runtime-modellen kombinerer Paxos-modellen med Virtual synchrony-modellen, ikke for konsensus, men for at udregne gruppemedlemskab som en separat tjeneste i Paxos. Dette gør Paxos hurtigere i tilfælde, hvor medlemskab ikke ændres dynamisk. Ved at kombinere Virtual Synchrony og Paxos er ISIS2 i stand til at springe over bestemte trin, som typiske Paxos skal udføre. I det væsentlige er Paxos og Virtual Synchrony forskellige modeller for at opnå den samme funktionalitet og kan kombineres med hinanden for at opnå varianter eller optimeringer.