Beste antwoord
Dit artikel biedt een opvallend duidelijke uitleg en bewijs: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Ik zal proberen hier een duidelijke samenvatting te geven:
Het doel van de Het Paxos-algoritme is bedoeld voor een aantal peers om overeenstemming te bereiken over een waarde. Paxos garandeert dat als een peer gelooft dat een bepaalde waarde is overeengekomen door een meerderheid, de meerderheid nooit eens worden over een andere waarde. Het protocol is zo ontworpen dat elke overeenkomst moet gaan via een meerderheid van knooppunten. Alle toekomstige pogingen tot overeenstemming moeten, indien succesvol, ook door ten minste een van die knooppunten gaan. Dus: Elk knooppunt dat een voorstel doet nadat een beslissing is genomen, moet communiceren met een knooppunt in de meerderheid. Het protocol garandeert dat het de vorige ag riet op waarde van die meerderheid.
Hier is hoe het werkt:
Stel dat we 3 knooppunten hebben, A, B en C. A zou graag de waarde “Foo.”
Het algoritme werkt in 3 fasen. Bij elke fase moet bevestiging van de meeste knooppunten worden bereikt.
Ten eerste hebben we de voorbereidingsfase. A stuurt een voorbereidingsverzoek naar A, B en C. Paxos vertrouwt op volgnummers om zijn garanties bereiken. Het voorbereidingsverzoek vraagt een knooppunt om te beloven: “Ik zal nooit een voorstel accepteren met een volgnummer lager dan dat in het voorbereidingsverzoek.” De knooppunten antwoorden met elke waarde waarmee ze eerder zijn overeengekomen (indien van toepassing). (En dit is van cruciaal belang): Knooppunt A moet de waarde voorstellen die het ontvangt met het hoogste volgnummer. Deze actie biedt de garantie dat de eerder overeengekomen waarden behouden blijven.
Vervolgens hebben we de acceptatiefase. A stuurt een acceptatieverzoek naar A, B en C. Het acceptatieverzoek luidt: ” Accepteert u foo? ” Als het bijbehorende volgnummer niet lager is dan wat het knooppunt eerder had beloofd of het verzoek dat het knooppunt eerder heeft geaccepteerd, accepteert het de nieuwe waarde en het volgnummer.
Als knooppunt A accepteert van een meerderheid van de nodes, de waarde wordt bepaald. Deze ronde van Paxos zal nooit akkoord gaan met een andere waarde.
De derde fase is niet strikt noodzakelijk, maar wel cruciaal optimalisatie in elke geproduceerde Paxos-implementatie. Nadat A een meerderheid van acceptaties heeft ontvangen, stuurt het besloten berichten naar A, B en C. Deze berichten laten alle peers weten dat er een waarde is gekozen en versnellen het einde van het besluitvormingsproces.
Zonder dit bericht zouden de andere peers moeten proberen een waarde voor te stellen om van de overeenkomst te vernemen. In de voorbereidingsfase zouden ze de eerder overeengekomen waarde leren kennen. Zodra die overeenkomst tot een goed einde was gebracht, zou het knooppunt de overeenkomst erkennen.
Ik heb hier een paar belangrijke kwesties verdoezeld:
- Alle volgnummers moeten monotoon oplopend zijn, en uniek per knoop . Dat wil zeggen, A en B kunnen niet beide een bericht sturen met volgnummer k. Alle berichten die in het protocol worden verzonden, bevatten volgnummers. Een knooppunt moet het hoogste acceptatieverzoek volgen dat het heeft gezien, evenals de hoogste waarde die het heeft beloofd in de voorbereidingsfase.
- Storingscondities. Het is heel goed mogelijk dat een ronde Paxos mislukt. In het geval van een storing, probeert een knoop eenvoudig opnieuw een voorstel te doen met een hoger volgnummer.
- Beëindigingsvoorwaarden. De versie van Paxos die ik heb beschreven, stopt niet noodzakelijk. Een paar aanpassingen zijn vereist voor een formeel bewijs van beëindiging.
Antwoord
Aangezien Paxos consensus bereikt, kan het ook worden gebruikt om schrijfbewerkingen in een gedistribueerde database te repliceren terwijl het kan een consistente volgorde van gebeurtenissen tussen alle knooppunten in een groep garanderen. Chubby van Google gebruikt Paxos voor het serveren van sterk consistente bestanden. Dit is waar de verwarring vandaan komt. Wat is dan de relatie tussen view synchrony en paxos als beide kunnen worden gebruikt voor replicatie?
Weinig geschiedenis: Lamport introduceerde het concept van replicatie van toestandsmachines in het begin van de jaren 80. Replicatie van toestandsmachines betekent dat een systeem gebeurtenissen in dezelfde volgorde aan alle knooppunten levert en dat ze deterministisch worden verwerkt, waardoor consistente toestanden voor alle knooppunten in de groep worden gegarandeerd. Ten tijde van de introductie van dit concept bracht het echter allerlei aannames met zich mee, waaronder het synchroon netwerk.Replicatie van staatsmachines bleef dus slechts een theoretisch hulpmiddel zonder praktisch nut. View synchrony werd op dit punt geïntroduceerd en was gericht op het bereiken van consistentie door dergelijke aannames niet te doen. Het doel was om een praktisch systeem te hebben dat dergelijke garanties biedt.
Publicatie van Paxos vond plaats terwijl het werk aan weergavesynchronisatie aan de gang was. Paxos kon replicatie van de statusmachine bereiken, aangezien replicas nu met dit consensusalgoritme overeenstemming konden bereiken over de uitvoeringsvolgorde van clientverzoeken. Paxos ging niet uit van synchrone netwerken of storingen. Paxos leverde ook een protocol voor groepslidmaatschap. De verschillen die nu overbleven tussen view synchrony en Paxos waren alleen in de manier waarop de abstracties werden geformuleerd. Beide bieden een dynamisch lidmaatschap en behandelen storingen op dezelfde manier. De verschillen zitten eigenlijk alleen in het model. Enkele verschillen die kunnen worden benadrukt zijn:
- Virtual Synchrony heeft een eenvoudig protocol voor groepslidmaatschap in vergelijking met Paxos. Virtual Synchrony voert groepslidmaatschap uit als een aparte service.
- Paxos kan vooruitgang boeken in bepaalde gevallen van partitie waar virtuele synchronisatie wordt geblokkeerd.
- Virtual Synchrony is sneller dan de huidige Paxos.
Beide systemen zijn geëvolueerd en geconvergeerd . Zoals het er nu uitziet, is het erg moeilijk om significante verschillen tussen de twee te trekken.
Lalith legt duidelijk het Virtual Synchrony-protocol uit en wijst er terecht op dat Paxos of elke andere consensusvariant kan worden gebruikt in view synchrony. Paxos biedt behalve consensus groepslidmaatschap en andere functies die Virtual Synchrony al biedt. Aangezien zowel virtuele synchronisatie als Paxos dezelfde garanties bieden en rond dezelfde tijd werden ontwikkeld, gebruikt de specificatie van virtuele synchronisatie Paxos niet voor consensus. Virtueel synchronisatiemodel gebruikt echter het volledig geordende verzendprotocol (ook bekend als ABCAST) om atomaire uitzendingen te bereiken en een ander protocol om groepsweergaven bij te werken en deze kunnen worden gezien als de consensusvariant gebruikt.
Het is misschien interessant om op te merken dat het ISIS-2 runtime-model het Paxos-model combineert met het virtuele synchronisatiemodel, niet voor consensus maar om het groepslidmaatschap als een aparte service in Paxos weg te werken. Dit maakt Paxos sneller in gevallen waarin het lidmaatschap niet dynamisch verandert. Door Virtual Synchrony en Paxos te combineren, kan ISIS2 bepaalde stappen overslaan die typische Paxos moeten uitvoeren. In wezen zijn Paxos en Virtual Synchrony verschillende modellen om dezelfde functionaliteit te bereiken en kunnen ze met elkaar worden gecombineerd om varianten of optimalisaties te bereiken.