Beste Antwort
Dieses Dokument bietet eine auffallend klare Erklärung und einen Beweis: http://pdos.csail.mit.edu/6.824/papers/paxos-simple.pdf
Ich werde versuchen, hier eine klare Zusammenfassung zu liefern:
Das Ziel des Der Paxos-Algorithmus dient dazu, dass eine bestimmte Anzahl von Peers eine Einigung über einen Wert erzielt. Paxos garantiert, dass die Mehrheit niemals einen anderen Wert vereinbaren. Das Protokoll ist so konzipiert, dass jede Vereinbarung gehen muss Alle zukünftigen Versuche einer Einigung müssen, wenn sie erfolgreich sind, auch mindestens einen dieser Knoten durchlaufen. Also: Jeder Knoten, der nach einer Entscheidung vorschlägt, muss Kommunikation mit einem Knoten in der Mehrheit. Das Protokoll garantiert, dass es die zuvor ag lernen wird Schilf nach Wert aus dieser Mehrheit.
So funktioniert es:
Angenommen, wir haben 3 Knoten, A, B und C. A möchte das vorschlagen Wert „Foo“.
Der Algorithmus arbeitet in 3 Phasen. In jeder Phase muss die Bestätigung von einer Mehrheit der Knoten erreicht werden.
Zuerst haben wir die Vorbereitungsphase. A sendet eine Vorbereitungsanforderung an A, B und C. Paxos verlässt sich auf Sequenznummern an seine Garantien erreichen. Die Vorbereitungsanforderung fordert einen Knoten auf, zu versprechen: „Ich werde niemals einen Vorschlag mit einer Sequenznummer annehmen, die kleiner als die in der Vorbereitungsanforderung ist.“ Die Knoten antworten mit einem Wert, dem sie zuvor zugestimmt haben (falls vorhanden). (Und dies ist von entscheidender Bedeutung): Knoten A muss den Wert vorschlagen, den er mit der höchsten Sequenznummer empfängt. Diese Aktion bietet die Garantie, dass die zuvor vereinbarten Werte erhalten bleiben.
Als nächstes haben wir die Akzeptanzphase. A sendet eine Annahmeanforderung an A, B und C. Die Annahmeanforderung lautet: “ Akzeptieren Sie foo? “ Wenn die zugehörige Sequenznummer nicht unter dem liegt, was der Knoten zuvor versprochen oder angefordert hat, akzeptiert der Knoten zuvor den neuen Wert und die neue Sequenznummer.
Wenn Knoten A akzeptiert von akzeptiert Bei einer Mehrheit der Knoten wird der Wert festgelegt. Diese Runde von Paxos wird niemals einem anderen Wert zustimmen.
Die dritte Phase ist nicht unbedingt erforderlich, aber von entscheidender Bedeutung Optimierung in jeder produzierten Paxos-Implementierung. Nachdem A die Mehrheit der Akzeptierungen erhalten hat, sendet es entschiedene Nachrichten an A, B und C. Diese Nachrichten informieren alle Peers darüber, dass ein Wert ausgewählt wurde, und beschleunigen das Ende des Entscheidungsprozesses.
Ohne diese Nachricht müssten die anderen Peers versuchen, einen Wert vorzuschlagen, um von der Vereinbarung zu erfahren. In der Vorbereitungsphase würden sie von dem zuvor vereinbarten Wert erfahren. Sobald diese Vereinbarung zum Abschluss gebracht wurde, würde der Knoten die Vereinbarung erkennen.
Ich habe hier einige wichtige Punkte beschönigt:
- Alle Sequenznummern müssen monoton ansteigen und eindeutig pro Knoten sein. Das heißt, A und B können nicht beide eine Nachricht mit der Sequenznummer k senden. Alle im Protokoll gesendeten Nachrichten enthalten Sequenznummern. Ein Knoten muss die höchste Akzeptanzanforderung verfolgen, die er gesehen hat, sowie den höchsten Wert, den er in der Vorbereitungsphase versprochen hat.
- Fehlerbedingungen. Es ist durchaus möglich, dass eine Runde Paxos scheitert. Im Fehlerfall versucht ein Knoten einfach erneut, eine höhere Sequenznummer vorzuschlagen.
- Beendigungsbedingungen. Die Version von Paxos, die ich beschrieben habe, endet nicht unbedingt. Für einen formellen Kündigungsnachweis sind einige Änderungen erforderlich.
Antwort
Da Paxos einen Konsens erzielt, kann es auch zum Replizieren von Schreibvorgängen in einer verteilten Datenbank verwendet werden kann eine konsistente Reihenfolge der Ereignisse zwischen allen Knoten in einer Gruppe gewährleisten. Chubby von Google verwendet Paxos, um stark konsistente Dateien bereitzustellen. Hier entsteht die Verwirrung. Welche Beziehung besteht dann zwischen Ansichtssynchronität und Paxos, wenn beide für die Replikation verwendet werden können?
Wenig Geschichte: Lamport führte Anfang der 80er Jahre das Konzept der Replikation von Zustandsmaschinen ein. Zustandsmaschinenreplikation bedeutet, dass ein System Ereignisse in derselben Reihenfolge an alle Knoten liefert und diese deterministisch verarbeitet werden, um konsistente Zustände über alle Knoten in der Gruppe hinweg zu gewährleisten. Zum Zeitpunkt der Einführung dieses Konzepts waren jedoch alle möglichen Annahmen erforderlich, einschließlich der Synchronität des Netzwerks.Die Replikation von Zustandsmaschinen blieb also lediglich ein theoretisches Werkzeug ohne praktischen Nutzen. Zu diesem Zeitpunkt wurde die Ansichtssynchronität eingeführt, die darauf abzielt, Konsistenz zu erzielen, indem keine solchen Annahmen getroffen werden. Ziel war ein praktisches System, das solche Garantien bietet.
Die Veröffentlichung von Paxos erfolgte während der laufenden Arbeit an der Ansichtssynchronität. Paxos könnte eine Replikation der Zustandsmaschine erreichen, da Replikate nun mithilfe dieses Konsensalgorithmus die Ausführungsreihenfolge von Clientanforderungen vereinbaren könnten. Paxos machte keine Annahmen über synchrones Netzwerk oder Ausfälle. Paxos stellte auch ein Gruppenmitgliedschaftsprotokoll zur Verfügung. Die Unterschiede, die jetzt zwischen Ansichtssynchronität und Paxos bestehen blieben, bestanden nur in der Art und Weise, wie die Abstraktionen formuliert wurden. Beide bieten eine dynamische Mitgliedschaft und behandeln Fehler auf ähnliche Weise. Die Unterschiede liegen eigentlich nur im Modell. Einige Unterschiede, die hervorgehoben werden können, sind:
- Virtual Synchrony verfügt im Vergleich zu Paxos über ein einfaches Gruppenmitgliedschaftsprotokoll. Virtual Synchrony führt die Gruppenmitgliedschaft als separaten Dienst aus.
- Paxos kann in bestimmten Fällen von Partitionen, in denen virtuelle Synchronisationsblöcke blockiert sind, Fortschritte erzielen.
- Virtual Synchrony ist schneller als moderne Paxos.
Beide Systeme haben entwickelt und konvergiert . Nach heutigem Stand ist es sehr schwierig, signifikante Unterschiede zwischen den beiden zu erkennen.
Lalith erklärt das Virtual Synchrony-Protokoll klar und weist zu Recht darauf hin, dass Paxos oder jede andere Konsensvariante für die Ansichtssynchronität verwendet werden kann. Paxos bietet neben Konsens auch Gruppenmitgliedschaft und andere Funktionen, die Virtual Synchrony bereits bietet. Da sowohl die virtuelle Synchronität als auch Paxos dieselben Garantien bieten und ungefähr zur gleichen Zeit entwickelt wurden, verwendet die Spezifikation der virtuellen Synchronität Paxos nicht für einen Konsens. Das virtuelle Synchronisationsmodell verwendet jedoch das vollständig geordnete Sendeprotokoll (auch als ABCAST bekannt), um eine atomare Übertragung zu erreichen, und ein anderes Protokoll zum Aktualisieren von Gruppenansichten. Diese können als Konsensvariante wird verwendet.
Es könnte interessant sein festzustellen, dass das ISIS-2-Laufzeitmodell das Paxos-Modell mit dem virtuellen Synchronisationsmodell kombiniert, nicht um einen Konsens zu erzielen, sondern um die Gruppenmitgliedschaft als separaten Dienst in Paxos herauszufiltern. Dies beschleunigt Paxos in Fällen, in denen sich die Mitgliedschaft nicht dynamisch ändert. Durch die Kombination von Virtual Synchrony und Paxos kann ISIS2 bestimmte Schritte überspringen, die typische Paxos ausführen müssen. Im Wesentlichen sind Paxos und Virtual Synchrony unterschiedliche Modelle, um die gleiche Funktionalität zu erzielen, und können miteinander kombiniert werden, um Varianten oder Optimierungen zu erzielen.