Stellen wir uns also vor. 5 Katzen sind im Zimmer eingesperrt, und um den Besitzer zu wecken, müssen sich alle darauf einigen, denn sie können die Tür nur öffnen, indem sie sich zu fünft darauf stützen. Wenn eine der Katzen Schrödingers Katze ist und die anderen Katzen nichts von seiner Entscheidung wissen, stellt sich die Frage: „Wie können sie das tun?“
In diesem Artikel werde ich Ihnen in einfachen Worten die theoretische Komponente der Welt verteilter Systeme und die Prinzipien ihrer Arbeit erläutern. Und betrachten Sie auch oberflächlich die Hauptidee, die Paxos'a zugrunde liegt.
Wenn Entwickler Cloud-Infrastrukturen und verschiedene Datenbanken nutzen und in Clustern mit einer großen Anzahl von Knoten arbeiten, können sie sicher sein, dass die Daten konsistent, sicher und immer verfügbar sind. Aber wo sind die Garantien?
Tatsächlich handelt es sich bei den Garantien, die wir haben, um Lieferantengarantien. Sie werden in der Dokumentation wie folgt beschrieben: „Dieser Dienst ist ziemlich zuverlässig, er hat ein bestimmtes SLA, keine Sorge, alles wird verteilt so funktionieren, wie Sie es erwarten.“
Wir neigen dazu, an das Beste zu glauben, weil kluge Onkel von großen Unternehmen uns versichert haben, dass alles gut werden wird. Wir stellen nicht die Frage: Warum kann das überhaupt funktionieren? Gibt es eine formelle Begründung für den ordnungsgemäßen Betrieb solcher Systeme?
Ich war vor kurzem dort und war von diesem Thema sehr inspiriert. Die Vorlesungen in der Schule ähnelten eher einem Unterricht in mathematischer Analyse als etwas, das mit Computersystemen zu tun hatte. Aber genau so wurden einst die wichtigsten Algorithmen bewiesen, die wir täglich nutzen, ohne es zu ahnen.
Die meisten modernen verteilten Systeme verwenden den Paxos-Konsensalgorithmus und seine verschiedenen Modifikationen. Das Coolste ist, dass die Gültigkeit und im Prinzip auch die Möglichkeit der Existenz dieses Algorithmus einfach mit Stift und Papier bewiesen werden kann. Gleichzeitig wird der Algorithmus in der Praxis in großen Systemen eingesetzt, die auf einer großen Anzahl von Knoten in den Clouds laufen.
Leichte Veranschaulichung dessen, was als nächstes besprochen wird: das Problem zweier GeneräleWerfen wir einen Blick auf das Aufwärmen .
Wir haben zwei Armeen – eine rote und eine weiße. Weiße Truppen sind in der belagerten Stadt stationiert. Auf zwei Seiten der Stadt sind rote Truppen unter der Führung der Generäle A1 und A2 stationiert. Die Aufgabe der Rothaarigen besteht darin, die weiße Stadt anzugreifen und zu gewinnen. Allerdings ist die Armee jedes einzelnen rothaarigen Generals kleiner als die Armee der Weißen.
Siegbedingungen für die Rothaarigen: Beide Generäle müssen gleichzeitig angreifen, um einen zahlenmäßigen Vorteil gegenüber den Weißen zu haben. Dazu müssen die Generäle A1 und A2 miteinander einverstanden sein. Wenn jeder einzeln angreift, werden die Rothaarigen verlieren.
Um zu verhandeln, können sich die Generäle A1 und A2 gegenseitig Boten durch das Gebiet der weißen Stadt schicken. Der Bote kann erfolgreich einen verbündeten General erreichen oder vom Feind abgefangen werden. Frage: Gibt es eine solche Abfolge der Kommunikation zwischen den rothaarigen Generälen (die Abfolge des Sendens von Boten von A1 nach A2 und umgekehrt von A2 nach A1), bei der sie sich garantiert auf einen Angriff zur Stunde X einigen können? Unter Garantien wird verstanden, dass beide Generäle eine eindeutige Bestätigung haben, dass ein Verbündeter (ein anderer General) genau zum festgelegten Zeitpunkt X angreifen wird.
Angenommen, A1 schickt einen Messenger an A2 mit der Nachricht: „Lasst uns heute um Mitternacht angreifen!“. General A1 kann ohne Bestätigung von General A2 nicht angreifen. Wenn der Bote von A1 angekommen ist, sendet General A2 eine Bestätigung mit der Nachricht: „Ja, lasst uns heute die Weißen auffüllen.“ Aber jetzt weiß General A2 nicht, ob sein Bote angekommen ist oder nicht, er hat keine Garantien, ob der Angriff gleichzeitig erfolgen wird. Jetzt muss General A2 erneut bestätigt werden.
Wenn wir ihre Kommunikation näher beschreiben, stellt sich Folgendes heraus: Egal wie viele Nachrichtenaustauschzyklen es gibt, es gibt keine Möglichkeit, beiden Generälen zu garantieren, dass ihre Nachrichten empfangen wurden (vorausgesetzt, dass einer der Boten abgefangen werden kann).
Das Problem der zwei Generäle ist ein gutes Beispiel für ein sehr einfaches verteiltes System, in dem es zwei Knoten mit unzuverlässiger Kommunikation gibt. Daher können wir nicht zu 100 % garantieren, dass sie synchronisiert sind. Über ähnliche Probleme erst in größerem Maßstab später im Artikel.
Einführung in das Konzept verteilter Systeme
Ein verteiltes System ist eine Gruppe von Computern (im Folgenden Knoten genannt), die Nachrichten austauschen können. Jeder einzelne Knoten ist eine autonome Einheit. Ein Knoten kann Aufgaben selbstständig bearbeiten, aber um mit anderen Knoten kommunizieren zu können, muss er Nachrichten senden und empfangen.
Wie Nachrichten konkret umgesetzt werden, welche Protokolle verwendet werden – das interessiert uns in diesem Zusammenhang nicht. Wichtig ist, dass die Knoten eines verteilten Systems durch das Versenden von Nachrichten Daten untereinander austauschen können.
Die Definition selbst sieht nicht sehr kompliziert aus, aber bedenken Sie, dass ein verteiltes System eine Reihe von Attributen hat, die für uns wichtig sind.
Eigenschaften verteilter Systeme
- Nebenläufigkeit – die Möglichkeit des Auftretens gleichzeitiger oder konkurrierender Ereignisse im System. Darüber hinaus werden wir berücksichtigen, dass Ereignisse, die auf zwei verschiedenen Knoten aufgetreten sind, möglicherweise gleichzeitig auftreten, bis wir eine klare Reihenfolge haben, in der diese Ereignisse auftreten. Und normalerweise tun wir das nicht.
- Keine globale Uhr. Aufgrund des Fehlens einer globalen Uhr haben wir keine klare Reihenfolge der Ereignisse. In der gewöhnlichen Welt der Menschen sind wir daran gewöhnt, dass wir absolut Stunden und Zeit haben. Bei verteilten Systemen ändert sich alles. Sogar ultrapräzise Atomuhren weisen eine Drift auf, und es gibt Situationen, in denen wir nicht sagen können, welches der beiden Ereignisse zuerst eingetreten ist. Daher können wir uns auch nicht auf die Zeit verlassen.
- Unabhängiger Ausfall von Systemknoten. Es gibt noch ein weiteres Problem: Es kann etwas schief gehen, einfach weil unsere Knoten nicht ewig sind. Möglicherweise fällt die Festplatte aus, die virtuelle Maschine in der Cloud startet möglicherweise neu, das Netzwerk blinkt möglicherweise und Nachrichten gehen verloren. Darüber hinaus gibt es Situationen, in denen die Knoten funktionieren, aber gleichzeitig gegen das System arbeiten. Die letzte Problemklasse erhielt sogar einen eigenen Namen: das Problem . Das bekannteste Beispiel für ein verteiltes System mit einem solchen Problem ist Blockchain. Aber heute werden wir diese spezielle Klasse von Problemen nicht betrachten. Wir werden an Situationen interessiert sein, in denen nur ein oder mehrere Knoten ausfallen können.
- Kommunikationsmodelle (Messaging-Modelle) zwischen Knoten. Wir haben bereits herausgefunden, dass Knoten durch den Austausch von Nachrichten kommunizieren. Es gibt zwei bekannte Messaging-Modelle: synchron und asynchron.
Modelle der Kommunikation zwischen Knoten in verteilten Systemen
Synchrones Modell - Wir wissen mit Sicherheit, dass es ein endliches bekanntes Zeitdelta gibt, für das die Nachricht garantiert von einem Knoten zum anderen gelangt. Wenn diese Zeit abgelaufen ist und die Nachricht nicht angekommen ist, können wir mit Sicherheit sagen, dass der Knoten ausgefallen ist. In einem solchen Modell haben wir eine vorhersehbare Wartezeit.
Asynchrones Modell – Bei asynchronen Modellen gehen wir davon aus, dass die Wartezeit endlich ist, es aber kein Zeitdelta gibt, nach dem garantiert werden kann, dass der Knoten ausgefallen ist. Diese. Die Wartezeit auf eine Nachricht von einem Knoten kann beliebig lang sein. Dies ist eine wichtige Definition, über die wir weiter sprechen werden.
Das Konzept des Konsenses in verteilten Systemen
Bevor wir das Konzept des Konsenses formal definieren, betrachten wir ein Beispiel für eine Situation, in der wir ihn benötigen, nämlich − Zustandsmaschinenreplikation.
Wir haben ein verteiltes Protokoll. Wir möchten, dass es konsistent ist und identische Daten auf allen Knoten eines verteilten Systems enthält. Wenn einer der Knoten einen neuen Wert erfährt, den er in das Protokoll schreiben wird, besteht seine Aufgabe darin, diesen Wert allen anderen Knoten anzubieten, damit das Protokoll auf allen Knoten aktualisiert wird und das System in einen neuen konsistenten Zustand wechselt. Gleichzeitig ist es wichtig, dass sich die Knoten untereinander einig sind: Alle Knoten sind sich einig, dass der vorgeschlagene neue Wert korrekt ist, alle Knoten akzeptieren diesen Wert und nur in diesem Fall kann jeder einen neuen Wert loggen.
Mit anderen Worten: Keiner der Knoten beanstandete, dass er über aktuellere Informationen verfüge, und der vorgeschlagene Wert sei falsch. Eine Vereinbarung zwischen Knoten und eine Vereinbarung über einen einzelnen korrekt akzeptierten Wert ist der Konsens in einem verteilten System. Als nächstes werden wir über Algorithmen sprechen, die es einem verteilten System ermöglichen, einen garantierten Konsens zu erzielen.
Formaler können wir einen Konsensalgorithmus (oder einfach einen Konsensalgorithmus) als eine Funktion definieren, die ein verteiltes System von Zustand A in Zustand B bringt. Darüber hinaus wird dieser Zustand von allen Knoten akzeptiert und alle Knoten können ihn bestätigen. Wie sich herausstellt, ist diese Aufgabe gar nicht so trivial, wie es auf den ersten Blick scheint.
Eigenschaften des Konsensalgorithmus
Der Konsensalgorithmus muss drei Eigenschaften haben, damit das System weiterhin existiert und beim Übergang von einem Zustand zum anderen Fortschritte macht:
- Zustimmung – alle korrekt funktionierenden Knoten müssen den gleichen Wert annehmen (in Artikeln findet sich diese Eigenschaft auch als Sicherheitseigenschaft). Alle Knoten, die jetzt funktionieren (nicht außer Betrieb sind und den Kontakt zum Rest nicht verloren haben), müssen sich einigen und einen endgültigen gemeinsamen Wert akzeptieren.
Hier ist es wichtig zu verstehen, dass die Knoten im betrachteten verteilten System übereinstimmen wollen. Das heißt, wir sprechen jetzt von Systemen, in denen einfach etwas scheitern kann (zum Beispiel fällt ein Knoten aus), aber in diesem System gibt es definitiv keine Knoten, die absichtlich gegen andere arbeiten (die Aufgabe der byzantinischen Generäle). Aufgrund dieser Eigenschaft bleibt das System konsistent.
- Integrität - wenn alle korrekt funktionierenden Knoten den gleichen Wert bieten v, daher muss jeder korrekt funktionierende Knoten diesen Wert akzeptieren v.
- Kündigung - Alle korrekt funktionierenden Knoten werden irgendwann einen Wert (Lebendigkeitseigenschaft) annehmen, der es dem Algorithmus ermöglicht, im System voranzukommen. Jeder einzelne Knoten, der korrekt funktioniert, muss früher oder später den Endwert akzeptieren und bestätigen: „Für mich stimmt dieser Wert, ich stimme dem Gesamtsystem zu.“
Ein Beispiel für die Funktionsweise des Konsensalgorithmus
Allerdings sind die Eigenschaften des Algorithmus möglicherweise nicht ganz klar. Daher veranschaulichen wir anhand eines Beispiels, welche Phasen der einfachste Konsensalgorithmus in einem System mit einem synchronen Nachrichtenmodell durchläuft, in dem alle Knoten wie erwartet funktionieren, keine Nachrichten verloren gehen und nichts kaputt geht (kommt das wirklich vor?).
- Alles beginnt mit einem Heiratsantrag (Propose). Angenommen, ein Client stellt eine Verbindung zu einem Knoten namens „Knoten 1“ her, startet eine Transaktion und übergibt einen neuen Wert an den Knoten – O. Von nun an nennen wir ihn „Knoten 1“. vorschlagen. Da der Antragsteller „Knoten 1“ nun das gesamte System darüber informieren muss, dass er über neue Daten verfügt, sendet er Nachrichten an alle anderen Knoten: „Sehen Sie! Ich habe den Wert „O“ erhalten und möchte ihn aufschreiben! Bitte bestätigen Sie, dass Sie auch „O“ in Ihr Protokoll eintragen.“
- Der nächste Schritt ist die Abstimmung über den vorgeschlagenen Wert (Abstimmung). Wofür ist das? Es kann vorkommen, dass andere Knoten neuere Informationen erhalten haben und über Daten zu derselben Transaktion verfügen.
Wenn der Knoten „Knoten 1“ seine Propuse sendet, überprüfen die anderen Knoten ihre Protokolle auf Daten zu diesem Ereignis. Liegt kein Konflikt vor, verkünden die Knoten: „Ja, ich habe keine weiteren Daten für dieses Ereignis.“ Der „O“-Wert ist die aktuellste Information, die wir verdienen.“Ansonsten können die Knoten auf „Knoten 1“ antworten: „Hör zu!“ Zu dieser Transaktion liegen mir neuere Daten vor. Nicht „Oh“, sondern etwas Besseres.“
In der Abstimmungsphase treffen die Knoten eine Entscheidung: Entweder akzeptieren sie alle den gleichen Wert, oder einer von ihnen stimmt dagegen, was bedeutet, dass er über neuere Daten verfügt.
- Wenn die Abstimmungsrunde erfolgreich war und alle dafür waren, geht das System in eine neue Phase über – die Akzeptanz des Wertes (Akzeptieren). „Knoten 1“ sammelt alle Antworten anderer Knoten und meldet: „Alle waren sich über den Wert ‚O‘ einig!“ Jetzt erkläre ich offiziell, dass „O“ unsere neue Bedeutung ist, die für alle gleich ist! Schreiben Sie es in Ihr Notizbuch, vergessen Sie es nicht. Schreiben Sie in Ihr Protokoll!“
- Die restlichen Knoten senden eine Bestätigung (Accepted), dass sie für sich den Wert „O“ notiert haben, in dieser Zeit ist nichts Neues eingegangen (eine Art Zwei-Phasen-Commit). Nach diesem bedeutsamen Ereignis gehen wir davon aus, dass die verteilte Transaktion abgeschlossen ist.
Somit besteht der Konsensalgorithmus im einfachen Fall aus vier Schritten: Vorschlag, Abstimmung (Abstimmung), Annahme (Akzeptieren), Bestätigung der Annahme (Akzeptiert).
Wenn wir uns in einem bestimmten Schritt nicht einigen können, wird der Algorithmus neu gestartet, wobei die Informationen der Knoten berücksichtigt werden, die sich geweigert haben, den vorgeschlagenen Wert zu bestätigen.
Konsensalgorithmus im asynchronen System
Davor lief alles reibungslos, denn es ging um das synchrone Messaging-Modell. Aber wir wissen, dass wir in der modernen Welt es gewohnt sind, alles asynchron zu erledigen. Wie funktioniert ein ähnlicher Algorithmus in einem System mit einem asynchronen Nachrichtenmodell, bei dem wir glauben, dass die Wartezeit auf eine Antwort von einem Knoten beliebig lang sein kann (übrigens kann ein Knotenausfall auch als Beispiel angesehen werden, wenn ein Knoten kann beliebig lange antworten).
Nachdem wir nun wissen, wie der Konsensalgorithmus prinzipiell funktioniert, stellt sich für neugierige Leser, die an diesem Punkt angelangt sind, die Frage: Wie viele Knoten in einem System aus N Knoten mit einem asynchronen Nachrichtenmodell können ausfallen, damit das System noch einen Konsens erzielen kann? ?
Die richtige Antwort und Begründung hinter dem Spoiler.Die richtige Antwort ist: 0. Wenn auch nur ein Knoten in einem asynchronen System ausfällt, kann das System keinen Konsens erzielen. Diese Aussage wird im bekannten FLP-Theorem (1985, Fischer, Lynch, Paterson, Link zum Original am Ende des Artikels) bewiesen: „Die Unmöglichkeit, einen verteilten Konsens zu erreichen, wenn mindestens ein Knoten ausfällt.“
Leute, dann haben wir ein Problem, wir sind daran gewöhnt, dass bei uns alles asynchron ist. Und hier ist es. Wie weiterleben?
Wir haben gerade über Theorie gesprochen, über Mathematik. Was bedeutet „Es kann kein Konsens erzielt werden“ bei der Übersetzung aus der mathematischen Sprache in unsere – der Technik? Dies bedeutet, dass „nicht immer erreicht werden kann“, d. h. Es gibt einen Fall, in dem ein Konsens nicht erreichbar ist. Und was ist dieser Fall?
Dies ist genau die oben beschriebene Verletzung der Lebendigkeitseigenschaft. Wir haben keine gemeinsame Vereinbarung und das System kann nicht fortschreiten (kann nicht in einer endlichen Zeit beendet werden), wenn wir nicht von allen Knoten eine Antwort erhalten. Denn in einem asynchronen System haben wir keine vorhersehbare Antwortzeit und können nicht wissen, ob ein Knoten ausgefallen ist oder einfach nur lange braucht, um zu antworten.
Aber in der Praxis können wir eine Lösung finden. Lassen Sie unseren Algorithmus im Falle von Fehlern lange laufen (er kann möglicherweise unbegrenzt laufen). Aber in den meisten Situationen, wenn die meisten Knoten ordnungsgemäß funktionieren, werden wir Fortschritte im System erzielen.
In der Praxis haben wir es mit teilweise synchronen Kommunikationsmodellen zu tun. Teilsynchronismus wird wie folgt verstanden: Im allgemeinen Fall haben wir ein asynchrones Modell, aber ein bestimmtes Konzept der „globalen Stabilisierungszeit“ eines bestimmten Zeitpunkts wird formal eingeführt.
Dieser Moment wird vielleicht nicht auf unbestimmte Zeit kommen, aber eines Tages muss er kommen. Der virtuelle Wecker klingelt und von diesem Moment an können wir vorhersagen, in welchem Zeitdelta die Nachrichten ankommen. Ab diesem Zeitpunkt wechselt das System von asynchron zu synchron. In der Praxis beschäftigen wir uns mit solchen Systemen.
Der Paxos-Algorithmus löst Konsensprobleme
ist eine Familie von Algorithmen, die das Konsensproblem für teilweise synchrone Systeme lösen, vorausgesetzt, dass einige Knoten ausfallen können. Der Autor von Paxos ist . Er schlug 1989 einen formalen Beweis für die Existenz und Korrektheit des Algorithmus vor.
Doch der Beweis erwies sich keineswegs als trivial. Die erste Veröffentlichung erschien erst 1998 (33 Seiten) und beschrieb den Algorithmus. Wie sich herausstellte, war es äußerst schwer zu verstehen, und 2001 wurde eine Erklärung für den Artikel veröffentlicht, der 14 Seiten umfasste. Die Veröffentlichungsmengen werden angegeben, um zu zeigen, dass das Konsensproblem tatsächlich keineswegs einfach ist und hinter solchen Algorithmen eine enorme Arbeit der klügsten Leute steckt.
Es ist interessant, dass Leslie Lampor selbst in seinem Vortrag darauf hingewiesen hat, dass es in der zweiten Artikelerklärung eine Aussage, eine Zeile (er hat nicht angegeben, welche) gibt, die auf unterschiedliche Weise interpretiert werden kann. Und aus diesem Grund funktionieren viele moderne Paxos-Implementierungen nicht ganz korrekt.
Eine detaillierte Analyse der Arbeit von Paxos wird mehr als einen Artikel erfordern, daher werde ich versuchen, die Grundidee des Algorithmus ganz kurz zu vermitteln. In den Links am Ende meines Artikels finden Sie Materialien zum weiteren Eintauchen in dieses Thema.
Rollen bei Paxos
Der Paxos-Algorithmus verfügt über ein Rollenkonzept. Betrachten Sie drei Hauptaspekte (es gibt Modifikationen mit zusätzlichen Rollen):
- Antragsteller (es können auch Begriffe vorkommen: Leiter oder Koordinatoren). Das sind die Jungs, die vom Benutzer etwas Neues lernen und die Rolle des Anführers übernehmen. Ihre Aufgabe besteht darin, eine Vorschlagsrunde für einen neuen Wert zu starten und das weitere Vorgehen der Knoten zu koordinieren. Darüber hinaus ermöglicht Paxos in bestimmten Situationen die Anwesenheit mehrerer Führungskräfte.
- Akzeptanten (Wähler). Dies sind die Knoten, die dafür stimmen, einen bestimmten Wert zu akzeptieren oder abzulehnen. Ihre Rolle ist sehr wichtig, denn von ihnen hängt die Entscheidung ab: in welchen Zustand das System nach der nächsten Stufe des Konsensalgorithmus geht (oder nicht geht).
- Die Lernenden. Knoten, die einfach den neuen akzeptierten Wert akzeptieren und schreiben, wenn sich der Zustand des Systems geändert hat. Sie treffen keine Entscheidungen, sie empfangen lediglich Daten und können diese an den Endbenutzer weitergeben.
Ein Knoten kann in unterschiedlichen Situationen mehrere Rollen vereinen.
Das Konzept des Quorums
Wir gehen davon aus, dass wir ein System von haben N Knoten. Und die meisten davon F Knoten können ausfallen. Wenn F-Knoten ausfallen, sollten wir das zumindest tun 2F+1 Akzeptorknoten.
Dies ist notwendig, damit wir auch im schlimmsten Fall immer „gute“, korrekt funktionierende Knoten in der Mehrheit haben. Also F+1 „gute“ Knoten, die zugestimmt haben, und der Endwert wird akzeptiert. Andernfalls kann es zu Situationen kommen, in denen unterschiedliche lokale Gruppen unterschiedliche Bedeutungen annehmen und sich untereinander nicht einigen können. Wir brauchen also eine absolute Mehrheit, um die Abstimmung zu gewinnen.
Allgemeine Idee des Paxos-Konsensalgorithmus
Der Paxos-Algorithmus geht von zwei großen Phasen aus, die wiederum in jeweils zwei Schritte unterteilt sind:
- Phase 1a: Vorbereiten. Während der Vorbereitungsphase informiert der Leiter (Antragsteller) alle Knoten: „Wir beginnen eine neue Abstimmungsphase. Wir haben eine neue Runde. Die Nummer dieser Runde ist n. Wir beginnen jetzt mit der Abstimmung.“ Bisher meldet es nur den Beginn eines neuen Zyklus, aber nicht den neuen Wert. Die Aufgabe dieser Phase besteht darin, eine neue Runde zu starten und alle über ihre eindeutige Nummer zu informieren. Die Rundenzahl ist wichtig, sie muss größer sein als alle bisherigen Abstimmungszahlen aller bisherigen Anführer. Denn dank der runden Zahl können andere Knoten im System erkennen, wie aktuell die Daten des Anführers sind. Wahrscheinlich haben andere Knoten bereits Abstimmungsergebnisse aus viel späteren Runden und werden dem Anführer einfach mitteilen, dass er hinter der Zeit zurückliegt.
- Phase 1b: Versprechen. Wenn die Akzeptorknoten die Nummer der neuen Abstimmungsstufe erhalten haben, sind zwei Ergebnisse möglich:
- Die Anzahl n der neuen Abstimmung ist größer als die Anzahl aller vorherigen Abstimmungen, an denen der Akzeptator teilgenommen hat. Dann sendet der Akzeptor dem Anführer ein Versprechen, dass er an keinen Abstimmungen mit einer Zahl kleiner als n mehr teilnehmen wird. Wenn der Akzeptor bereits für etwas gestimmt hat (das heißt, er hat in der zweiten Phase bereits einen Wert akzeptiert), hängt er den akzeptierten Wert und die Nummer der Abstimmung, an der er teilgenommen hat, an sein Versprechen an.
- Andernfalls kann der Akzeptor, wenn er bereits von der Abstimmung mit der hohen Zahl weiß, den Vorbereitungsschritt einfach ignorieren und dem Anführer nicht antworten.
- Phase 2a: Akzeptieren. Der Leiter muss auf eine Antwort des Quorums (der meisten Knoten im System) warten und hat, wenn die erforderliche Anzahl von Antworten eingeht, zwei Möglichkeiten für die Entwicklung von Ereignissen:
- Einige der Akzeptanten haben Werte eingereicht, für die sie bereits gestimmt haben. In diesem Fall wählt der Anführer den Wert aus der Abstimmung mit der höchsten Zahl. Nennen wir diesen Wert x und senden wir eine Nachricht wie diese an alle Knoten: „Akzeptiere (n, x)“, wobei der erste Wert die Abstimmungszahl aus seinem eigenen Vorschlagsschritt ist und der zweite Wert das ist, wofür sich alle versammelt haben, d. h. Wert, für den wir tatsächlich stimmen.
- Wenn keiner der Akzeptanten Werte gesendet hat, sondern lediglich versprochen hat, in dieser Runde abzustimmen, kann der Anführer sie einladen, für ihren Wert zu stimmen, den Wert, für den er überhaupt zum Anführer geworden ist. Nennen wir es Y. Es sendet an alle Knoten eine Nachricht wie: „Akzeptiere (n, y)“, analog zum vorherigen Ergebnis.
- Phase 2b: Akzeptiert. Darüber hinaus stimmen die Akzeptorknoten nach Erhalt der Nachricht „Akzeptieren (...)“ vom Anführer dieser nur dann zu (senden sie eine Bestätigung an alle Knoten, dass sie mit dem neuen Wert einverstanden sind), wenn sie einige (andere) nicht versprochen haben Anführer, der mit der Nummer der Runde an der Abstimmung teilnimmt n' > nandernfalls ignorieren sie die Sicherheitsabfrage.
Wenn die Mehrheit der Knoten dem Anführer geantwortet hat und alle den neuen Wert bestätigt haben, gilt der neue Wert als akzeptiert. Hurra! Wenn die Mehrheit nicht typisiert ist oder es Knoten gibt, die sich weigern, den neuen Wert zu akzeptieren, beginnt alles von vorne.
So funktioniert der Paxos-Algorithmus. Jede dieser Phasen weist viele Feinheiten auf. Wir haben verschiedene Arten von Fehlern, Probleme mehrerer Führungskräfte und vieles mehr praktisch nicht berücksichtigt. Der Zweck dieses Artikels besteht jedoch lediglich darin, den Leser auf höchstem Niveau in die Welt des verteilten Rechnens einzuführen.
Es ist auch erwähnenswert, dass Paxos nicht der einzige seiner Art ist, es gibt auch andere Algorithmen, zum Beispiel , aber das ist ein Thema für einen anderen Artikel.
Links zu Materialien zum weiteren Studium
Anfängerniveau:
- , Preethi Kasireddy, Blogartikel auf Medium
- , Adi Kancherla, Blogartikel auf Medium
- Ittai Abraham-Blog
- , Ittai Abraham, Blogartikel
Leslie Lamport-Level:
- Fischer, Lynch und Paterson, Forschungsbericht, 1985
- , Leslie Lamport, Forschungsbericht, 1998
- , Leslie Lamport, Forschungsbericht, 2001
Source: habr.com