Paxos made simple

TL; DR:

Paxos är ett protokoll som löser problemet att få en grupp noder att komma överens eller nå enighet om ett enda värde.

sammanfattning:

i detta dokument introducerar författaren Paxos, som är en feltolerant algoritm som används för att nå konsensus bland en samling datorer i asynkron och icke-bysantinsk modell.

problemet med konsensus är att få en samling datorer att bestämma en sak som om de var en dator. Den största skillnaden mellan konsensus och andra avtalsproblem är att konsensusprotokoll måste vara feltoleranta, vilket innebär att det inte finns någon enda felpunkt. Däremot, i protokoll som tvåfas commit, om samordnaren skulle krascha, skulle hela systemet kanske inte kunna göra några framsteg. Om det finns en stabil ledare blir konsensus trivial, eftersom ledaren kan upprätta en total ordning över alla operationer själv och låta andra noder följa den. Ledarens misslyckande kommer dock att förhindra att systemet gör några framsteg. Dessutom, om ledarvalsalgoritmen misslyckas (vilket sannolikt kommer att hända vid nätverkspartition) kan det finnas flera ledare och bryter mot avtalets egendom.

papperet definierar tre klasser av agenter:

1.Förslag (noder som föreslår värde) 2.Acceptorer (kom ihåg de föreslagna värdena) 3.Elever (upptäck de valda värdena).

sedan beskriver den följande misslyckade försök att lösa konsensus:

1.Enda acceptor agent (fungera som ledare). Otillfredsställande på grund av den enda punkten av misslyckande. 2.Flera acceptormedel. – acceptorer accepterar det första värdet de får – ett värde väljs om det accepteras av en majoritet acceptorer otillfredsställande eftersom vi lätt kan konstruera fall där inget värde accepteras av en majoritet av accepterar, bryter uppsägning. 3. Acceptera mer än en värden otillfredsställande eftersom meddelandet kan levereras i ordning, bryter mot avtalet.

Paxos algoritm:

Förbered fas:

för förslagsställaren väljer den ett nytt förslagsnummer n och sänder en förberedningsförfrågan(inkluderar n) till acceptorer. För acceptor jämför den n med det accepterade förslaget med det högsta antalet. Om n är större skickar acceptorn tillbaka ett löfte att följa den förslagsställaren och det högsta numrerade förslaget(och värdet associerat med förslaget) som det har accepterat, om något.

Accept Phase:

efter att förslagsställaren fått svar från en majoritet av acceptorerna skickar förslagsställaren en acceptansbegäran till alla acceptorer. Accept-meddelandet innehåller förslagsnumret och ett värde(värdet på det högst numrerade förslaget eller något värde om alla acceptorer svarar ingen) när en acceptor tar emot en accept-begäran kommer den att acceptera begäran om förslagsnumret är större än eller lika med det högsta numrerade förslaget som det har accepterat. Slutligen, om en accept-begäran accepteras av en majoritet av acceptorerna. Förslaget väljs (eller beslutas).

Notera: 1.Acceptorn måste komma ihåg det högsta numrerade förslaget som det har accepterat om något även om det misslyckas och återhämtar sig. Förslagsställaren kan glömma sina förslag så länge den aldrig försöker utfärda ett annat förslag med samma förslag nummer 2.Förslagsnumret måste vara globalt unikt och monotont öka 3.”Dueling proposers problem”.

när två förslagsställare vill föreslå samtidigt kan de försöka blockera varandra genom att utfärda förslag med ett tal som är större än det tidigare förslaget. Denna situation kan fortsätta för alltid och bryter mot uppsägning. Möjliga lösningar inkluderar ledarval och slumpmässig backoff.

fråga:

1. Vad är ledarvalsalgoritmen i avsnitt 3?

2.Papperet presenterar flera optimeringar, men det förklarar inte varför och hur detta arbete kommer att förbättra prestandan hos Paxos

3.As jag läste tidningen, Jag kände att Paxos kan vara för svårt eller dyrt att genomföra utan några andra optimeringar

4.Antagandet att meddelandena inte kan skadas verkar för starkt

5.Papperet verkar något ofullständigt. 1.it tar inte upp om duelleringsförespråkarnas problem som beskrivs ovan såväl som lösningen. 2. Hur väljer man förslagsnumret för att göra det globalt unikt och monotont ökande? 3.Vad sägs om membership management?

Lämna ett svar

Din e-postadress kommer inte publiceras.