Paxos på sitt hjerte er veldig enkelt

Paxos-algoritmen, når den presenteres på vanlig engelsk, er veldig enkel. — Leslie Lamport 2001

jeg skal prøve å forklare enkelt dekret Paxos på en måte, forhåpentligvis, det er lett å forstå.

TIL denne dag ER IMO, John Ousterhouts foredrag om Paxos det fortsatt DET BESTE der ute. Materialet i dette innlegget låner tungt Fra Prof. Ousterhouts foredrag. Med John Ousterhouts avtale brukte jeg noen av hans lysbilder for å forklare Paxos.

Konsensus

Paxos som protokoll, prøver å løse konsensusproblemet. Sett på vanlig engelsk, det prøver å løse et problem at et system bare vil velge en verdi når en eller flere servere kan foreslå forskjellige verdier.

det virkelige verdenseksemplet ville være noe som et valg. Folk kan stemme på en annen president. Men bare en president kan velges.

Paxos er designet for å håndtere fail-stop / crash (ikke-Bysantinsk) og meldingsforsinkelse/tap. Det er også et krav om livskraft at noen foreslåtte verdier til slutt velges så lenge flertallet av serverne kjører. Dette er for å unngå uinteressante løsninger som aldri-godta-noen-verdi. Hvis du ikke gjør noe, vil du ikke gjøre noe galt. På samme måte vil du ikke at flere presidenter skal velges, og du vil ha en president til slutt så lenge folk stemmer.

På en side notat, for å være ærlig, tror jeg å prøve å bruke stemme som et eksempel for å forklare Paxos, i det opprinnelige Deltidsparlamentet er det veldig naturlig. Men på en eller annen måte fungerte det ikke veldig bra. Lamport sa også det selv i et intervju at det er en total fiasko, noe som er uheldig.

Enkelt Akseptor

Screen-Shot-2018-11-13-at-11.17.43-PM
Med en klynge av 2F+1 servere, hva skjer hvis vi alltid lager en bestemt boks for å godta forslag. Og hva forslaget blir akseptert av den boksen er valgt.

problemet med denne tilnærmingen er at en enkelt nedboks kan gjøre tjenesten utilgjengelig. Men kravet sier at tjenesten må være oppe så lenge flertallet av serverne kjører (F+1 i dette tilfellet).

Legg merke til at dette er en enkelt master replikasjonsmodell. Og dette er nøyaktig hvorfor nedetid er uunngåelig med master-slave replikering.

Quorum

Så hvis det ikke virker å ha en enkelt akseptor, bør vi kanskje vente til flere servere har akseptert et forslag før vi hevder at en verdi blir valgt.

Hvor mange?

Hvis akseptorene er faste og det er <=F, igjen, klarer vi ikke å tolerere F krasjet servere. Hvis akseptorene kan være noen servere og det er <=F, i en klynge av 2F+1 servere, kan vi ha to forskjellige forslag som går til to disjoint sett med akseptorer som forårsaker at to verdier velges.

så antall akseptorer må være >=F+1. Siden færre akseptorer jo bedre, la oss bare gå med F+1. Og det kan være noen F+1 servere i klyngen.

Vi har allerede gjort noen fremskritt! Hvis et forslag er akseptert av F+1 servere, er det valgt.

Godta forslag

la Oss nå se hvordan akseptorer skal bestemme om de skal godta et forslag eller ikke.

Godta bare første forslag?
Screen-Shot-2018-11-13-at-11.17.27-PM

Det ville ikke fungere, fordi vi kan ende opp med å aldri ha noen verdi valgt som tilfellet ovenfor. Dette er i strid med livskravet.

det er ikke fornuftig å si godta andre forslag eller noe sånt fordi du aldri vet om det noen gang vil være et andre forslag.

så vi må godta det første forslaget, men kanskje ikke bare det første forslaget.

Godta alle forslag?
Screen-Shot-2018-11-13-at-11.31.11-PM
Dette ville bryte sikkerhetskravet da vi kan ende opp med å ha mer enn en verdi valgt.

Kjerne

Her kommer trikset, som jeg synes Er Den mest interessante delen Av Paxos.

når en verdi er valgt, må fremtidige forslag foreslå samme verdi.

Dette betyr at en tofaseprotokoll ville være nødvendig. I første fase må forslagsstillerne finne ut om noen verdi allerede er valgt. Og foreslå i den andre fasen.

hvis du er en distribuert system veteran må du allerede har lagt merke til ett nøkkelord i forrige uttalelse. Det er “fremtiden”. Jeg har vurdert Tid og Bestilling før. Distribuert system handler om bestilling. “future” her innebærer bestilling(skje – før forholdet). Så vi må bestille alle forslag. Så i eksemplet nedenfor kan vi avvise red fordi vi vet at blue er valgt og red er et gammelt forslag.

Screen-Shot-2018-11-13-at-11.39.37-PM

Stemmeseddel

en enkel måte å bestille forslag på er å ha et unikt stemmeseddelnummer for hvert forslag i form av <seq_id, server_id>. For å garantere bestilling må seq_id vedvare krysskrasj / omstart. Så det må være varig lagret lokalt.

Paxos

Nå er vi alle satt opp for å beskrive den virkelige tofasede Paxos-protokollen. Vi vil kalle den første fasen prepare fase og andre fase accept fase. prepare fase tjener to formål i en rundtur.

  1. lær om hvilken som helst verdi som allerede er valgt
  2. forhindre akseptorer som godtar eldre forslag (veldig MYE SOM RESERVETRINNET i Tofase Commit)

Screen-Shot-2018-11-13-at-11.53.52-PM
Acceptor har å varig lagre et par ting

  • minProposal
  • acceptedProposal
  • acceptedValue
    Legg merke til at i stedet for “kringkasting til alle servere”, bør den “sendes til Minst F + 1 servere”. Og proposeren skal sende akseptmeldingen til samme sett Med F + 1-servere som i forberedelsesfasen.

La oss ta en nærmere titt på hvert trinn.

Forbered fase

i denne fasen forsøker proposeren å få et løfte fra akseptor om ikke å godta noen forslag eldre enn hans. Samtidig vil akseptorer informere forslagsstillerne hvilke verdier som allerede er akseptert så langt.

i trinn 3 og 4 vil et forslag endre sitt forslag til det siste aksepterte forslaget fra akseptorer det snakket med. Det ser ut til å være veldig konservativt fordi du kan få et akseptert forslag som ikke er valgt, og proposeren ender med å gi opp sitt forslag. Men DET ER OK siden vi bare bryr oss om konsensus. I første fase er det vanskelig for forslagsstilleren å vite om en verdi er valgt eller ikke. En akseptert verdi kan ikke velges. Men en valgt verdi må aksepteres av et flertall av serverne! Og akseptorer avviser eldre forslag (trinn 6). Med to invariants vet vi at det siste aksepterte forslaget som returneres til forslaget i fase ett, enten allerede er valgt, eller ingen verdi er valgt for øyeblikket. Uansett er det trygt å foreslå den verdien.

Hvorfor holde styr på minProposal?
det kan være to racing forslag i forberedelsesfasen mens ingenting har blitt akseptert ennå. Dette betyr at de begge vil flytte for å akseptere fasen. Takket være den totale bestillingen vi har for alle forslag og kravet F+1, vil minst en akseptor se det nyere forslaget og avvise meldingen accept fra det tapende/eldre forslaget. Invarianten her er det minProposal >= acceptedProposal.

Screen-Shot-2018-11-14-at-12.28.11-AM

dette er trolig det mest interessante tilfellet, da den andre proposeren ikke så den forrige aksepterte verdien, og en verdi ble ikke valgt på tidspunktet i forberedelsesfasen. I dette tilfellet vil det gå videre og sende accept(Y) til andre servere. Fordi S3 har lovet at det bare vil godta forslag senere enn 4.5, avviser det X. Hvis vi ikke holder styr på minProposal, vil X bli akseptert av S3. Da ville både X og Y blitt akseptert av tre servere og vurdert valgt, noe som bryter med sikkerhetskravet.

Der har du det. Dette er det eneste dekretet Paxos. Det er sagt at implementering Av Paxos har vist seg å være veldig veldig vanskelig.

  1. Paxos gjort enkelt https://lamport.azurewebsites.net/pubs/paxos-simple.pdf ↩︎

  2. Deltidsparlamentet https://lamport.azurewebsites.net/pubs/lamport-paxos.pdf ↩︎

  3. Paxos made live https://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf ↩︎

Legg igjen en kommentar

Din e-postadresse vil ikke bli publisert.