I hjertet er meget enkel

når den præsenteres på almindeligt engelsk, er den meget enkel. — Leslie Lamport 2001

jeg vil forsøge at forklare det fælles dekret På en måde, forhåbentlig, det er let at forstå.

til denne dag, IMO, John Ousterhout foredrag om det stadig den bedste derude. Materialet i dette indlæg låner tungt fra Prof. Ousterhout foredrag. Med John Ousterhout ‘ s aftale brugte jeg nogle af hans lysbilleder til at forklare ham.

konsensus

forsøger at løse konsensusproblemet. Sæt på almindeligt engelsk, det forsøger at løse et problem, at et system kun vælger en værdi, når en eller flere servere kan foreslå forskellige værdier.

det virkelige verdenseksempel ville være noget som et valg. Folk kan stemme på forskellige præsident. Men kun en præsident kan vælges.

er designet til at håndtere fail-stop/crash (ikke-bysantinske) og besked forsinkelse/tab. Der er også et livskravskrav om, at nogle foreslåede værdier til sidst vælges, så længe flertallet af serverne kører. Dette er for at undgå uinteressante løsninger som aldrig-acceptere-nogen-værdi. Hvis du ikke gør noget, vil du ikke gøre noget forkert. På samme måde vil du ikke have mere end en præsidenter valgt, og du vil have en præsident til sidst, så længe folk stemmer.

for at være ærlig mener jeg, at det er meget naturligt at forsøge at bruge afstemning som et eksempel til at forklare, at det i den oprindelige Deltidspapir fra Parlamentet er meget naturligt. Men på en eller anden måde fungerede det ikke særlig godt. Lamport sagde også det selv i en samtale, at det er en total fiasko, hvilket er uheldigt.

enkelt Acceptor

Screen-Shot-2018-11-13-at-11.17.43-PM
med en klynge af 2F+1 servere, Hvad sker der, hvis vi altid laver en bestemt boks for at acceptere forslag. Og uanset hvilket forslag, der accepteres af denne boks, vælges.

problemet med denne tilgang er, at en enkelt ned boks kan gøre tjenesten utilgængelig. Men kravet siger, at tjenesten skal være i gang, så længe flertallet af serverne kører (F+1 i dette tilfælde).

Bemærk, at dette faktisk er en enkelt masterreplikationsmodel. Og det er netop derfor, at nedetid er uundgåelig med master-slave replikation.

Kvorum

så hvis det at have en enkelt acceptor ikke fungerer, skal vi måske vente, indtil flere servere har accepteret et forslag, før vi hævder, at en værdi vælges.

hvor mange?

hvis acceptorer er faste, og det er <=F, igen, vi undlader at tolerere F crashed servere. Hvis acceptorerne kan være nogen servere, og det er <=F, i en klynge af 2F+1 servere, kan vi have to forskellige forslag, der går til to uensartede sæt acceptorer, der forårsager to værdier vælges.

så antallet af acceptorer skal være >=F+1. Da færre acceptorer jo bedre, lad os bare gå med F+1. Og det kan være alle F+1 servere i klyngen.

vi har allerede gjort nogle fremskridt! Hvis et forslag accepteres af F+1 servere, er det valgt.

accept af forslag

lad os nu se, hvordan acceptorer skal beslutte, om de vil acceptere et forslag eller ej.

accepter kun første forslag?
Screen-Shot-2018-11-13-at-11.17.27-PM

det ville ikke fungere, fordi vi kan ende med aldrig at have nogen værdi valgt som tilfældet ovenfor. Dette overtræder liveness krav.

det giver ikke mening at sige acceptere andet forslag eller noget lignende, fordi du aldrig ved, om der nogensinde vil være et andet forslag.

så vi er nødt til at acceptere det første forslag, men måske ikke kun det første forslag.

Accepter alle forslag?
Screen-Shot-2018-11-13-at-11.31.11-PM
dette ville krænke sikkerhedskravet, da vi kan ende med at have mere end en værdi valgt.

Core

her kommer tricket, som jeg synes er den mest interessante del af.

når en værdi er valgt, skal fremtidige forslag foreslå den samme værdi.

dette betyder, at en tofaseprotokol ville være nødvendig. I den første fase skal forslagsstillerne finde ud af, om der allerede er valgt nogen værdi. Og Foreslå i anden fase.

hvis du er en distribueret systemveteran, skal du allerede have bemærket et nøgleord i den forrige erklæring. Det er “fremtiden”. Jeg gennemgik tid og orden før. Distribueret system handler om bestilling. “fremtid” her indebærer bestilling (ske-før forhold). Så vi er nødt til at bestille alle forslag. Så i eksemplet nedenfor kan vi afvise red fordi vi ved blue er valgt og red er et gammelt forslag.

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

stemmeseddel

en nem måde at bestille forslag på er at have et unikt stemmeseddelnummer for hvert forslag i form af <seq_id, server_id>. For at garantere bestilling skal seq_id være vedvarende cross crash / genstart. Så det skal opbevares holdbart lokalt.

Pakos

nu er vi alle klar til at beskrive den virkelige tofasede pakos-protokol. Vi kalder den første fase prepare fase og anden fase accept fase. prepare fase tjener to formål i en rundtur.

  1. Lær om enhver værdi, der allerede er valgt
  2. forhindre acceptorer, der accepterer ældre forslag (meget ligesom RESERVETRINNET i Tofaseforpligtelse)

Screen-Shot-2018-11-13-at-11.53.52-PM
Acceptor skal varigt opbevare et par ting

  • minProposal
  • acceptedProposal
  • acceptedValue
    Bemærk, at i stedet for “broadcast til alle servere”, skal det være “broadcast til mindst F+1 servere”. Og forslagsstilleren skal sende acceptmeddelelsen til det samme sæt F+1-servere som i forberedelsesfasen.

lad os se nærmere på hvert trin.

Forbered fase

i denne fase forsøger forslagsstilleren at få et løfte fra acceptor om ikke at acceptere nogen forslag, der er ældre end hans. Samtidig vil acceptorer informere forslagsstillerne om, hvilke værdier der allerede er accepteret indtil videre.

i trin 3 og 4 vil en forslagsstiller ændre sit forslag til det seneste accepterede forslag fra acceptorer, det talte med. Det ser ud til at være meget konservativt, fordi du måske får et accepteret forslag, der ikke er valgt, og forslagsstilleren ender med at opgive sit forslag. Men det er OK, da vi kun bekymrer os om konsensus. I den første fase er det svært for forslagsstilleren at vide, om en værdi er valgt eller ej. En accepteret værdi vælges muligvis ikke. Men en valgt værdi skal accepteres af et flertal af serverne! Og acceptorer afviser ældre forslag (trin 6). Med to invarianter ved vi, at det seneste accepterede forslag, der blev returneret til forslaget i fase et, enten allerede er valgt, eller at der ikke er valgt nogen værdi i øjeblikket. Uanset hvad er det sikkert at foreslå den værdi.

hvorfor holde styr på minProposal?
der kan være to racerforslag i forberedelsesfasen, mens intet er blevet accepteret endnu. Det betyder, at de begge vil flytte til at acceptere fase. Takket være den samlede bestilling, Vi har for alle forslag og F+1 kravet, vil mindst en acceptor se det nyere forslag og afvise accept meddelelsen fra det tabende/ældre forslag. Den invariant her er, at minProposal >= acceptedProposal.

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

dette er sandsynligvis det mest interessante tilfælde, da den anden forslagsstiller ikke så den tidligere accepterede værdi, og en værdi ikke blev valgt på det tidspunkt i forberedelsesfasen. I dette tilfælde vil det gå videre og sende accept(Y) til andre servere. Fordi S3 har lovet, at den kun vil acceptere forslag senere end 4.5, afviser den X. Hvis vi ikke holder styr på minProposal, vil Xblive accepteret af S3. Derefter ville både X og Y være blevet accepteret af tre servere og betragtes som valgt, hvilket overtræder sikkerhedskravet.

der har du det. Dette er det fælles dekret. Det har vist sig at være meget svært at implementere.

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

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

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

Skriv et svar

Din e-mailadresse vil ikke blive publiceret.