Bästa svaret
Detta papper ger en slående tydlig förklaring och bevis: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Jag försöker ge en tydlig sammanfattning här:
Målet med Paxos-algoritmen är för att ett visst antal kamrater ska komma överens om ett värde. Paxos garanterar att om en kamrat tror att något värde har överenskommits av majoriteten kommer majoriteten att aldrig enas om ett annat värde. Protokollet är utformat så att alla avtal måste gå genom en majoritet av noder. Eventuella framtida försök till överenskommelse, om de lyckas måste också gå igenom minst en av dessa noder. Således: Noder som föreslår efter att ett beslut har nåtts måste kommunicera med en nod i majoriteten. Protokollet garanterar att det lär sig den tidigare ag reed på värde från den majoriteten.
Så här fungerar det:
Anta att vi har tre noder, A, B och C. A skulle vilja föreslå värde ”Foo.”
Algoritmen fungerar i tre faser. Vid varje fas måste bekräftelse från en majoritet av noder nås.
Först har vi förberedelsefasen. A skickar en förbereder begäran till A, B och C. Paxos förlitar sig på sekvensnummer till uppnå sina garantier. Förberedelseförfrågan ber en nod att lova: ”Jag accepterar aldrig något förslag med ett sekvensnummer som är mindre än det i förberedelseförfrågan.” Noderna svarar med vilket värde de tidigare har godkänt (om något). (Och detta är kritiskt viktigt): Nod A måste föreslå det värde den får med det högsta sekvensnumret. Denna åtgärd ger garanti för att de tidigare överenskomna värdena kommer att bevaras.
Därefter har vi acceptfasen. A skickar en godkännande förfrågan till A, B och C. Godkännande begäran säger: ” Accepterar du foo? ” Om det tillhörande sekvensnumret inte är under det som noden tidigare lovat eller begär noden tidigare har accepterat, kommer det nya värdet och sekvensnumret att accepteras.
Om nod A får accepterar från en majoritet av noder, värdet bestäms. Denna omgång av Paxos kommer aldrig överens om ett annat värde.
Den tredje fasen är inte absolut nödvändig, men är en avgörande optimering i alla tillverkade Paxos-implementeringar. Efter att A får en majoritet av accepterar skickar den beslutade meddelanden till A, B och C. Dessa meddelanden låter alla kollegor veta att ett värde har valts och påskyndar slutet på beslutsprocessen.
Utan detta meddelande måste de andra kamraterna försöka föreslå ett värde för att lära sig avtalet. I förberedelsefasen lärde de sig om det tidigare överenskomna värdet. När det avtalet drevs till slut skulle noden känna igen avtalet.
Jag har glansat över några viktiga frågor här:
- Alla sekvensnummer måste öka monotont och unikt per nod . Det vill säga att A och B inte båda kan skicka ett meddelande med sekvensnummer k. Alla meddelanden som skickas i protokollet innehåller sekvensnummer. En nod måste spåra den högsta acceptbegäran som den har sett samt det högsta värdet som den har lovat i förberedelsefasen.
- Felvillkor. Det är fullt möjligt för en runda Paxos att misslyckas. I händelse av misslyckande försöker en nod helt enkelt föreslå igen med ett högre sekvensnummer.
- Avslutningsvillkor. Den version av Paxos I som beskrivits slutar inte nödvändigtvis. Några justeringar krävs för ett formellt bevis på uppsägning.
Svar
Eftersom Paxos uppnår samförstånd kan det också användas för att replikera skrivningar i en distribuerad databas eftersom den kan garantera konsekvent ordning av händelser bland alla noder i en grupp. Chubby by Google använder Paxos för att servera starkt konsekventa filer. Det är här förvirringen följer. Vad är då förhållandet mellan synkronisering och paxos om båda kan användas för replikering?
Lite historia: Lamport introducerade begreppet statlig maskinreplikering tidigt på 80-talet. Statlig maskinreplikering innebär att ett system levererar händelser i samma ordning till alla noder och de bearbetas deterministiskt och garanterar konsekventa tillstånd i alla noder i gruppen. Men när konceptet introducerades innebar det alla möjliga antaganden inklusive nätverket att vara synkron.Så statlig maskinreplikering förblev bara ett teoretiskt verktyg utan praktisk användning. Synkronisering infördes vid denna tidpunkt och syftade till att uppnå konsekvens genom att inte göra några sådana antaganden. Målet var att ha ett praktiskt system som ger sådana garantier.
Publicering av Paxos hände medan synkroniseringsarbetet pågår. Paxos kan uppnå statlig maskinreplikering eftersom repliker nu kan komma överens om körningsordningen för klientförfrågningar med hjälp av denna konsensusalgoritm. Paxos gjorde inga antaganden om synkront nätverk eller fel. Paxos tillhandahöll också ett protokoll för gruppmedlemskap. Skillnaderna som nu förblev mellan synkronisering och Paxos var bara i hur abstraktionerna formulerades. Båda ger dynamiskt medlemskap och hanterar misslyckanden på samma sätt. Skillnaderna är egentligen bara i modellen. Några skillnader som kan markeras är:
- Virtual Synchrony har ett enkelt gruppprotokoll jämfört med Paxos. Virtual Synchrony kör gruppmedlemskap som en separat tjänst.
- Paxos kan göra framsteg i vissa fall av partition där virtuell synkronisering blockeras.
- Virtual Synchrony är snabbare än samtida Paxos.
Båda systemen har utvecklats och konvergerats . Så som det ser ut idag är det mycket svårt att dra några betydande skillnader mellan de två.
Lalith förklarar tydligt Virtual Synchrony-protokollet och påpekar med rätta att Paxos eller vilken annan konsensusvariant som helst kan användas i synkronisering. Paxos förutom konsensus tillhandahåller gruppmedlemskap och andra funktioner som virtuell synkronisering redan tillhandahåller. Eftersom både virtuell synkronisering och Paxos ger samma garantier och utvecklades ungefär samma tid använder specifikationen av virtuell synkronisering inte Paxos för konsensus. Virtuell synkronismodell använder dock det helt ordnade sändprotokollet (även känt som ABCAST) för att uppnå atomutsändning och ett annat protokoll för att uppdatera gruppvyer och dessa kan ses som konsensusvariant den använder.
Det kan vara intressant att notera att ISIS-2 runtime-modellen kombinerar Paxos-modellen med Virtual synchrony-modellen, inte för konsensus utan för att ta med gruppmedlemskap som en separat tjänst i Paxos. Detta gör Paxos snabbare i fall där medlemskap inte förändras dynamiskt. Genom att kombinera Virtual Synchrony och Paxos kan ISIS2 hoppa över vissa steg som vanliga Paxos behöver utföra. I grund och botten är Paxos och Virtual Synchrony olika modeller för att uppnå samma funktionalitet och kan kombineras med varandra för att uppnå varianter eller optimeringar.