Paxos i sitt hjärta är väldigt enkelt

Paxos-algoritmen, när den presenteras på vanlig engelska, är mycket enkel. — Leslie Lamport 2001

jag ska försöka förklara det enda dekretet Paxos på ett sätt, förhoppningsvis är det lätt att förstå.

till denna dag, IMO, John Ousterhout föreläsning om Paxos det fortfarande den bästa ute. Materialet i detta inlägg lånar tungt från professor Ousterhouts föreläsning. Med John Ousterhouts överenskommelse använde jag några av hans bilder för att förklara Paxos.

konsensus

Paxos som ett protokoll försöker lösa konsensusproblemet. Sätt på vanlig engelska, det försöker lösa ett problem att ett system bara väljer ett värde när en eller flera servrar kan föreslå olika värde(er).

det verkliga världsexemplet skulle vara något som ett val. Människor kan rösta på olika president. Men bara en president kan väljas.

Paxos är utformad för att hantera felstopp/krasch (icke-bysantinsk) och meddelandefördröjning/förlust. Det finns också ett liveness krav på att något föreslaget värde så småningom väljs så länge som majoriteten av servrarna körs. Detta för att undvika ointressanta lösningar som aldrig-acceptera-något-värde. Om du inte gör något, kommer du inte göra något fel. På samma sätt vill du inte att mer än en presidenter ska väljas och du vill ha en president så småningom så länge folk röstar.

på en sidoanteckning, för att vara ärlig, jag tror att försöka använda röstning som ett exempel för att förklara Paxos, i den ursprungliga deltids parlamentets papper är mycket naturligt. Men på något sätt fungerade det inte så bra. Lamport sa också det själv i en intervju att det är ett totalt misslyckande, vilket är olyckligt.

enda Acceptor

Screen-Shot-2018-11-13-at-11.17.43-PM
med ett kluster av 2F+1 servrar, vad händer om vi alltid gör en viss ruta för att acceptera förslag. Och vilket förslag som accepteras av den rutan väljs.

problemet med detta tillvägagångssätt är att en enda nedruta kan göra Tjänsten otillgänglig. Men kravet säger att tjänsten måste vara igång så länge majoriteten av servrarna körs (F+1 i det här fallet).

Lägg märke till att detta effektivt är en enda huvudreplikeringsmodell. Och det är just därför stilleståndstid är oundvikligt med master-slave-replikering.

Quorum

så om att ha en enda acceptor inte fungerar, kanske vi borde vänta tills flera servrar har accepterat ett förslag innan vi hävdar att ett värde väljs.

hur många?

om acceptorerna är fixade och det är <=F, igen, vi misslyckas med att tolerera F kraschade servrar. Om acceptorerna kan vara några servrar och det är <=F, i ett kluster av 2F+1 servrar, kan vi ha två olika förslag som går till två separata uppsättningar acceptorer som orsakar att två värden väljs.

så antalet acceptorer måste vara >=F+1. Eftersom färre acceptorer desto bättre, låt oss bara gå med F+1. Och det kan vara alla F+1 servrar i klustret.

vi har redan gjort några framsteg! Om något förslag accepteras av F+1 servrar, är det valt.

acceptera förslag

låt oss nu se hur acceptorer ska bestämma om de ska acceptera ett förslag eller inte.

Acceptera endast första förslaget?
Screen-Shot-2018-11-13-at-11.17.27-PM

det skulle inte fungera, för vi kan sluta aldrig ha något värde valt som fallet ovan. Detta bryter liveness krav.

det är inte meningsfullt att säga Acceptera andra förslag eller något liknande eftersom du aldrig vet om det någonsin kommer att bli ett andra förslag.

så vi måste acceptera det första förslaget, men kanske inte bara det första förslaget.

acceptera alla förslag?
Screen-Shot-2018-11-13-at-11.31.11-PM
detta skulle bryta mot säkerhetskravet eftersom vi kan sluta ha mer än ett värde valt.

kärna

här kommer tricket, som jag tycker är den mest intressanta delen av Paxos.

när ett värde har valts måste framtida förslag föreslå samma värde.

detta innebär att ett tvåfasprotokoll skulle behövas. I den första fasen måste förslagsställarna ta reda på om något värde redan har valts. Och Föreslå i den andra fasen.

om du är en distribuerad systemveteran måste du redan ha märkt ett nyckelord i föregående uttalande. Och det är “framtiden”. Jag granskade tid och ordning innan. Distribuerat system handlar om beställning. “framtid” här innebär beställning (hända-före förhållande). Så vi måste beställa alla förslag. Sedan i exemplet nedan kan vi avvisa red eftersom vi vet att blue är valt och red är ett gammalt förslag.

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

Omröstningsnummer

ett enkelt sätt att beställa förslag är att ha ett unikt omröstningsnummer för varje förslag i form av <seq_id, server_id>. För att garantera beställning, seq_id måste kvarstå cross krasch / omstart. Så det måste lagras varaktigt lokalt.

Paxos

nu är vi alla inställda för att beskriva det verkliga tvåfasiga Paxos-protokollet. Vi kommer att kalla den första fasen prepare fas och andra fasen accept fas. prepare fas tjänar två syften i en rundresa.

  1. lär dig om något värde som redan är valt
  2. förhindra acceptorer att acceptera några äldre förslag (mycket som RESERVSTEGET i tvåfas Commit)

Screen-Shot-2018-11-13-at-11.53.52-PM
Acceptor måste varaktigt lagra några saker

  • minProposal
  • acceptedProposal
  • acceptedValue
    Lägg märke till att istället för att “sända till alla servrar” ska det “sändas till minst F+1-servrar”. Och förslagsställaren ska skicka acceptmeddelandet till samma uppsättning F+1-servrar som i förberedelsefasen.

Låt oss ta en närmare titt på varje steg.

Förbered fas

i denna fas försöker proposer att få ett löfte från acceptor att inte acceptera några förslag som är äldre än hans. Samtidigt kommer acceptorerna att informera förslagsställarna vilka värden som redan har accepterats hittills.

i steg 3 och 4 kommer en förslagsställare att ändra sitt förslag till det senaste accepterade förslaget från acceptorer som det pratade med. Det verkar vara mycket konservativt eftersom du kan få ett accepterat förslag som inte är valt och förslagsställaren slutar ge upp sitt förslag. Men det är OK eftersom vi bara bryr oss om konsensus. I den första fasen är det svårt för förslagsställaren att veta om ett värde väljs eller inte. Ett accepterat värde kanske inte väljs. Men ett valt värde måste accepteras av en majoritet av servrarna! Och acceptorer avvisar äldre förslag (steg 6). Med två invarianter vet vi att det senast accepterade förslaget återvände till förslaget i fas ett antingen redan har valts, eller inget värde har valts för tillfället. Hur som helst är det säkert att föreslå det värdet.

varför hålla reda på minProposal?
det kan finnas två tävlingsförslag i förberedelsefasen medan ingenting har accepterats ännu. Detta innebär att de båda kommer att flytta för att acceptera fas. Tack vare den totala beställningen vi har för alla förslag och F+1 – kravet kommer minst en acceptor att se det nyare förslaget och avvisa accept – meddelandet från det förlorande/äldre förslaget. Invarianten här är att minProposal >= acceptedProposal.

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

detta är förmodligen det mest intressanta fallet, eftersom den andra förslagsställaren inte såg det tidigare accepterade värdet och ett värde valdes inte vid tiden i förberedelsefasen. I det här fallet kommer det att gå vidare och skicka accept(Y) till andra servrar. Eftersom S3 har lovat att det bara kommer att acceptera förslag senare än 4.5, avvisar det X. Om vi inte håller reda på minProposal, kommer X att accepteras av S3. Då skulle både X och Y ha accepterats av tre servrar och anses vara utvalda, vilket bryter mot säkerhetskravet.

där har du det. Detta är det enda dekretet Paxos. Det sägs att implementering av Paxos har visat sig vara väldigt svårt.

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

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

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

Lämna ett svar

Din e-postadress kommer inte publiceras.