{"id":37335,"date":"2019-10-31T22:17:01","date_gmt":"2019-10-31T19:17:01","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah\/"},"modified":"2019-10-31T22:17:01","modified_gmt":"2019-10-31T19:17:01","slug":"kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","status":"publish","type":"post","link":"https:\/\/prohoster.info\/de\/blog\/administrirovanie\/kot-shryodingera-bez-korobki-problema-konsensusa-v-raspredelyonnyh-sistemah","title":{"rendered":"Schr\u00f6dingers Katze ohne Box: das Konsensproblem in verteilten Systemen","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Stellen Sie sich vor, in einem Raum sind f\u00fcnf Katzen eingesperrt. Um ihren Besitzer zu wecken, m\u00fcssen sie sich gemeinsam darauf einigen, denn die T\u00fcr k\u00f6nnen sie nur zu f\u00fcnft aufdr\u00fccken. Wenn eine der Katzen Schr\u00f6dingers Katze ist und die anderen nichts von ihrer Entscheidung wissen, stellt sich die Frage: \u201eWie k\u00f6nnen sie das anstellen?\u201c <\/p>\n

In diesem Artikel erkl\u00e4re ich Ihnen einfach die theoretischen Grundlagen der verteilten Systeme und deren Funktionsprinzipien. Zudem werde ich die zentrale Idee des Paxos-Algorithmus oberfl\u00e4chlich betrachten. <\/p>\n

\"Schr\u00f6dingers
\n<\/a><\/noindex>
\nWenn Entwickler Cloud-Infrastrukturen nutzen, mit verschiedenen Datenbanken arbeiten oder in Clustern aus vielen Knoten agieren, sind sie \u00fcberzeugt, dass die Daten intakt, sicher und immer verf\u00fcgbar sind. Aber woher kommen diese Garantien?<\/p>\n

Im Wesentlichen sind die Garantien, die wir haben, die Garantien des Anbieters. Diese sind in der Dokumentation etwa so beschrieben: \u201eDieser Dienst ist ausreichend zuverl\u00e4ssig, er hat einen festgelegten SLA, machen Sie sich keine Sorgen, alles wird verteilt funktionieren, wie Sie es erwarten.\u201c <\/p>\n

Wir neigen dazu, an das Beste zu glauben, denn kluge K\u00f6pfe gro\u00dfer Unternehmen haben uns versichert, dass alles gut wird. Wir stellen uns nicht die Frage: Warum k\u00f6nnte das eigentlich funktionieren? Gibt es eine formale Begr\u00fcndung f\u00fcr die Richtigkeit solcher Systeme?<\/p>\n

K\u00fcrzlich war ich auf einer Schule f\u00fcr verteilte Berechnungen<\/a><\/noindex> und war von diesem Thema sehr inspiriert. Die Vorlesungen an der Schule erinnerten eher an Mathematikunterricht als an etwas, das mit Computersystemen zu tun hat. Doch genau so wurden damals die wichtigsten Algorithmen bewiesen, die wir jeden Tag benutzen, oft ohne es zu merken. <\/p>\n

In den meisten modernen verteilten Systemen wird der Konsensalgorithmus Paxos und seine verschiedenen Modifikationen verwendet. Das Beste daran ist, dass die Begr\u00fcndung und die grunds\u00e4tzlich m\u00f6gliche Existenz dieses Algorithmus einfach mit Stift und Papier bewiesen werden kann. In der Praxis wird der Algorithmus in gro\u00dfen Systemen eingesetzt, die auf einer enormen Anzahl von Knoten in der Cloud arbeiten. <\/p>\n

Eine einfache Illustration dessen, was als N\u00e4chstes folgt: die Aufgabe der zwei Gener\u00e4le<\/b>Lassen Sie uns zur Aufw\u00e4rmung die Aufgabe der zwei Gener\u00e4le besprechen<\/a><\/noindex>. <\/p>\n

Wir haben zwei Armeen \u2013 die Rote und die Wei\u00dfe. Die wei\u00dfen Truppen sind in der belagerten Stadt stationiert. Die roten Truppen unter dem Befehl der Gener\u00e4le A1 und A2 sind auf beiden Seiten der Stadt positioniert. Die Aufgabe der Roten besteht darin, die wei\u00dfe Stadt anzugreifen und zu gewinnen. Allerdings ist das Heer jedes roten Generals f\u00fcr sich genommen kleiner als das der Wei\u00dfen.<\/p>\n

\"Schr\u00f6dingers
\n
\nDie Bedingungen f\u00fcr den Sieg der Roten: Beide Gener\u00e4le m\u00fcssen gleichzeitig angreifen, um einen numerischen Vorteil gegen\u00fcber den Wei\u00dfen zu haben. Dazu m\u00fcssen sich die Gener\u00e4le A1 und A2 miteinander abstimmen. Wenn jeder separat angreift, werden die Roten verlieren. <\/p>\n

Um sich abzustimmen, k\u00f6nnen die Gener\u00e4le A1 und A2 Boten durch das Gebiet der wei\u00dfen Stadt schicken. Ein Bote kann erfolgreich zu dem verb\u00fcndeten General gelangen oder von den Gegnern abgefangen werden. Die Frage ist: Gibt es eine solche Abfolge der Kommunikation zwischen den roten Gener\u00e4len (die Reihenfolge, in der Boten von A1 zu A2 und umgekehrt von A2 zu A1 geschickt werden), bei der sie garantiert eine Vereinbarung f\u00fcr den Angriff zur Stunde X erreichen? Hierbei wird unter Garantie verstanden, dass beide Gener\u00e4le eine eindeutige Best\u00e4tigung erhalten, dass der Verb\u00fcndete (der andere General) definitiv zur festgelegten Zeit X angreift.<\/p>\n

Angenommen, A1 schickt einen Boten zu A2 mit der Nachricht: \u201eLass uns heute Nacht um Mitternacht angreifen!\u201c. General A1 kann nicht angreifen, ohne eine Best\u00e4tigung von General A2 zu erhalten. Wenn der Bote von A1 angekommen ist, sendet General A2 eine Best\u00e4tigung mit der Nachricht: \u201eJa, lass uns heute die Wei\u00dfen \u00fcberfallen\u201c. Aber nun wei\u00df General A2 nicht, ob sein Bote angekommen ist oder nicht, er hat keine Garantie, dass der Angriff gleichzeitig erfolgen wird. Jetzt ben\u00f6tigt General A2 wieder eine Best\u00e4tigung.<\/p>\n

Wenn wir ihre Kommunikation weiter ausf\u00fchren, zeigt sich Folgendes: So viele Nachrichtenaustauschzyklen es auch geben mag, es gibt keine M\u00f6glichkeit, beide Gener\u00e4le garantiert dar\u00fcber zu informieren, dass ihre Nachrichten empfangen wurden (vorausgesetzt, einer der Boten k\u00f6nnte abgefangen werden).<\/p>\n

Das Problem der zwei Gener\u00e4le ist eine hervorragende Veranschaulichung eines sehr einfachen verteilten Systems, in dem es zwei Knoten mit unzuverl\u00e4ssiger Kommunikation gibt. Das bedeutet, wir haben keine 100% Garantie, dass sie synchronisiert werden. \u00dcber \u00e4hnliche Probleme in gr\u00f6\u00dferem Ma\u00dfstab werden wir sp\u00e4ter im Artikel sprechen.<\/p>\n

Wir f\u00fchren das Konzept der verteilten Systeme ein.<\/h2>\n

\nEin verteiltes System ist eine Gruppe von Computern (im Folgenden Knoten genannt), die Nachrichten austauschen k\u00f6nnen. Jeder einzelne Knoten ist eine autonome Einheit. Ein Knoten kann Aufgaben selbstst\u00e4ndig bearbeiten, aber um mit anderen Knoten zu interagieren, muss er Nachrichten senden und empfangen. <\/p>\n

Wie genau die Nachrichten implementiert sind und welche Protokolle verwendet werden, ist in diesem Kontext nicht von Interesse. Wichtig ist, dass die Knoten des verteilten Systems Daten austauschen k\u00f6nnen, indem sie Nachrichten senden.<\/p>\n

Die Definition scheint nicht sehr kompliziert zu sein, jedoch m\u00fcssen wir ber\u00fccksichtigen, dass ein verteiltes System eine Reihe von Attributen aufweist, die f\u00fcr uns relevant sind.<\/p>\n

Attribute verteilter Systeme<\/h4>\n

<\/p>\n

    \n
  1. Nebenl\u00e4ufigkeit<\/b> \u2013 die M\u00f6glichkeit gleichzeitiger oder konkurrierender Ereignisse im System. Dar\u00fcber hinaus werden wir davon ausgehen, dass Ereignisse, die auf zwei verschiedenen Knoten auftreten, potenziell konkurrierend sind, solange wir keine klare Reihenfolge dieser Ereignisse haben. Und in der Regel haben wir eine solche klare Reihenfolge nicht.<\/li>\n
  2. Fehlen globaler Uhren<\/b>. Wir haben keine klare Abfolge von Ereignissen aufgrund des Fehlens globaler Uhren. In der gewohnten Welt der Menschen sind wir daran gew\u00f6hnt, dass wir Uhren und eine absolute Zeit haben. Alles \u00e4ndert sich, wenn es um verteilte Systeme geht. Selbst bei hochpr\u00e4zisen Atomicuhren gibt es Drift, und es k\u00f6nnen Situationen auftreten, in denen wir nicht sagen k\u00f6nnen, welches von zwei Ereignissen zuerst passiert ist. Daher k\u00f6nnen wir uns auch nicht auf die Zeit verlassen.<\/li>\n
  3. Unabh\u00e4ngiger Ausfall von Systemknoten<\/b>. Es gibt ein weiteres Problem: Etwas kann schiefgehen, einfach weil unsere Knoten nicht ewig funktionieren. Eine Festplatte kann ausfallen, eine virtuelle Maschine in der Cloud kann neu starten, das Netzwerk kann flackern und Nachrichten gehen verloren. Dar\u00fcber hinaus sind Situationen m\u00f6glich, in denen Knoten funktionieren, aber gegen das System arbeiten. Diese letzte Klasse von Problemen hat sogar einen eigenen Namen erhalten: das Problem der byzantinischen Gener\u00e4le<\/a><\/noindex>. Das bekannteste Beispiel f\u00fcr ein verteiltes System mit diesem Problem ist die Blockchain. Aber heute werden wir diese spezielle Klasse von Problemen nicht betrachten. Uns interessieren Situationen, in denen einfach einer oder mehrere Knoten ausfallen k\u00f6nnen.<\/li>\n
  4. Kommunikationsmodelle (Nachrichten\u00fcbertragungsmodelle) zwischen Knoten<\/b>. Wir haben bereits festgestellt, dass Knoten durch den Austausch von Nachrichten kommunizieren. Es gibt zwei bekannte Modelle des Nachrichtenaustauschs: synchron und asynchron.<\/li>\n<\/ol>\n

    <\/p>\n

    Kommunikationsmodelle zwischen Knoten in verteilten Systemen<\/h4>\n

    \nSynchrones Modell<\/b> \u2013 wir wissen genau, dass es eine endliche, bekannte Zeitspanne gibt, in der eine Nachricht garantiert von einem Knoten zu einem anderen gelangt. Wenn diese Zeit abgelaufen ist und die Nachricht nicht eingetroffen ist, k\u00f6nnen wir mit Sicherheit sagen, dass der Knoten ausgefallen ist. In einem solchen Modell haben wir eine vorhersehbare Wartezeit. <\/p>\n

    Asynchrones Modell<\/b> \u2013 in asynchronen Modellen nehmen wir an, dass die Wartezeit endlich ist, aber es gibt keine solche Zeitspanne, nach der man garantieren kann, dass ein Knoten ausgefallen ist. Das hei\u00dft, die Wartezeit auf eine Nachricht von einem Knoten kann beliebig lang sein. Dies ist eine wichtige Definition, und wir werden sp\u00e4ter weiter dar\u00fcber sprechen. <\/p>\n

    Das Konzept des Konsenses in verteilten Systemen<\/h2>\n

    \nBevor wir das Konzept des Konsenses formal definieren, betrachten wir ein Beispiel f\u00fcr eine Situation, in der wir ihn ben\u00f6tigen, n\u00e4mlich \u2013 State Machine Replication<\/b>. <\/p>\n

    Wir haben ein verteiltes Protokoll, das konsistent sein und identische Daten auf allen Knoten des verteilten Systems enthalten sollte. Wenn ein Knoten einen neuen Wert ermittelt, den er in das Protokoll aufnehmen m\u00f6chte, 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 \u00fcbergeht. Dabei ist es wichtig, dass die Knoten sich untereinander einigen: Alle Knoten m\u00fcssen zustimmen, dass der vorgeschlagene neue Wert korrekt ist, und alle Knoten m\u00fcssen diesen Wert akzeptieren, bevor sie gemeinsam den neuen Wert in das Protokoll schreiben k\u00f6nnen. <\/p>\n

    Mit anderen Worten: Kein Knoten hat widersprochen, dass er aktuellere Informationen hat und der vorgeschlagene Wert falsch ist. Die Vereinbarung zwischen den Knoten und die Zustimmung zu einem einheitlichen, anerkannten Wert ist der Konsens in einem verteilten System. Im Folgenden werden wir \u00fcber Algorithmen sprechen, die es einem verteilten System erm\u00f6glichen, Konsens verl\u00e4sslich zu erreichen.
    \n\"Schr\u00f6dingers
    \nFormell k\u00f6nnen wir den Konsensalgorithmus (oder einfach den Konsensalgorithmus) als eine Funktion definieren, die ein verteiltes System von Zustand A in Zustand B \u00fcberf\u00fchrt. Dieser Zustand muss von allen Knoten akzeptiert werden, und alle Knoten m\u00fcssen ihn best\u00e4tigen k\u00f6nnen. Wie sich herausstellt, ist diese Aufgabe alles andere als trivial.<\/p>\n

    Eigenschaften des Konsensalgorithmus<\/h4>\n

    \nDer Konsensalgorithmus muss drei Eigenschaften aufweisen, damit das System weiterhin existiert und Fortschritte beim \u00dcbergang von einem Zustand in einen anderen erzielt:<\/p>\n

      \n
    1. Zustimmung <\/b> \u2013 alle korrekt arbeitenden Knoten m\u00fcssen denselben Wert akzeptieren (in Artikeln wird dieses Merkmal auch als Sicherheitsmerkmal bezeichnet). Alle Knoten, die derzeit funktionsf\u00e4hig sind (nicht ausgefallen oder vom Rest getrennt), m\u00fcssen zu einer \u00dcbereinstimmung kommen und einen bestimmten endg\u00fcltigen gemeinsamen Wert akzeptieren.\n

      Hier ist es wichtig zu verstehen, dass die Knoten in unserem betrachteten verteilten System eine \u00dcbereinstimmung anstreben. Das bedeutet, wir sprechen jetzt \u00fcber Systeme, in denen etwas ausfallen kann (zum Beispiel kann ein Knoten ausfallen). In diesem System gibt es jedoch keine Knoten, die absichtlich gegen andere arbeiten (das Problem der byzantinischen Gener\u00e4le). Durch dieses Merkmal bleibt das System konsistent.<\/li>\n

    2. Integrit\u00e4t <\/b> \u2014 wenn alle korrekt funktionierenden Knoten denselben Wert anbieten v<\/b>, dann muss jeder korrekt funktionierende Knoten diesen Wert akzeptieren v<\/b>. <\/li>\n
    3. Beendigung <\/b>\u2013 alle korrekt funktionierenden Knoten werden letztendlich einen bestimmten Wert annehmen (Liveness-Eigenschaft), was es dem Algorithmus erm\u00f6glicht, im System Fortschritte zu erzielen. Jeder einzelne korrekt funktionierende Knoten sollte fr\u00fcher oder sp\u00e4ter den endg\u00fcltigen Wert annehmen und dies best\u00e4tigen: \u201eF\u00fcr mich ist dieser Wert wahr, ich stimme mit dem gesamten System \u00fcberein.\u201c<\/li>\n<\/ol>\n

      <\/p>\n

      Beispiel f\u00fcr das Funktionieren eines Konsensalgorithmus<\/h4>\n

      \nW\u00e4hrend die Eigenschaften des Algorithmus m\u00f6glicherweise nicht ganz verst\u00e4ndlich sind, lassen Sie uns anhand eines Beispiels veranschaulichen, welche Phasen ein einfacher Konsensalgorithmus in einem System mit synchronem Nachrichtenaustausch durchl\u00e4uft, in dem alle Knoten ordnungsgem\u00e4\u00df funktionieren, Nachrichten nicht verloren gehen und nichts kaputtgeht (passiert das wirklich?).<\/p>\n

        \n
      1. Alles beginnt mit dem Vorschlag (Propose). Angenommen, ein Client hat sich mit einem Knoten namens \u201eKnoten 1\u201c verbunden und eine Transaktion gestartet, indem er dem Knoten einen neuen Wert \u2013 O \u2013 \u00fcbertr\u00e4gt. Ab diesem Moment nennen wir \u201eKnoten 1\u201c proposer<\/b>. Als proposer muss \u201eKnoten 1\u201c nun das gesamte System dar\u00fcber informieren, dass er neue Daten hat, und er sendet an alle anderen Knoten die Nachricht: \u201eSehen Sie! Ich habe den Wert \u201eO\u201c erhalten und m\u00f6chte ihn aufzeichnen! Bitte best\u00e4tigen Sie, dass Sie ebenfalls \u201eO\u201c in Ihr Protokoll aufnehmen werden.\u201c\n

        \"Schr\u00f6dingers<\/li>\n

      2. Die n\u00e4chste Phase ist die Abstimmung \u00fcber den vorgeschlagenen Wert (Voting). Warum ist sie notwendig? Es k\u00f6nnte sein, dass andere Knoten aktualisierte Informationen erhalten haben, und sie verf\u00fcgen \u00fcber Daten zu derselben Transaktion.\n

        \"Schr\u00f6dingers
        \n
        \nWenn der Knoten \u201eKnoten 1\u201c seinen Vorschlag sendet, \u00fcberpr\u00fcfen die anderen Knoten die zugeh\u00f6rigen Daten in ihren Protokollen. Wenn es keine Widerspr\u00fcche gibt, erkl\u00e4ren die Knoten: \u201eJa, ich habe keine anderen Informationen zu diesem Ereignis. Der Wert \u201eO\u201c ist die aktuellste Information, die wir haben.\u201c <\/p>\n

        In jedem anderen Fall k\u00f6nnen die Knoten \u201eKnoten 1\u201c antworten: \u201eH\u00f6r mal! Ich habe aktuellere Informationen zu dieser Transaktion. Nicht \u201eO\u201c, sondern etwas Besseres.\u201c<\/p>\n

        In der Abstimmungsphase kommen die Knoten zu einer Entscheidung: Entweder akzeptieren alle einen Wert oder einer von ihnen stimmt dagegen und zeigt an, dass er aktuellere Daten hat. <\/li>\n

      3. Wenn die Abstimmungsrunde erfolgreich war und alle \u201ef\u00fcr\u201c gestimmt haben, wechselt das System in die n\u00e4chste Phase \u2013 die Annahme des Wertes (Accept). \u201eKnoten 1\u201c sammelt alle Antworten der anderen Knoten und meldet: \u201eAlle haben dem Wert \u201eO\u201c zugestimmt! Jetzt erkl\u00e4re ich offiziell, dass \u201eO\u201c unser neuer Wert ist, einheitlich f\u00fcr alle! Notiert es euch, vergesst es nicht. Schreibt es in euer Protokoll!\u201c\n

        \"Schr\u00f6dingers<\/li>\n

      4. Die anderen Knoten senden eine Best\u00e4tigung (Accepted), dass sie den Wert \u201eO\u201c gespeichert haben; in der Zwischenzeit sind keine neuen Informationen eingegangen (eine Art zweiphasiger Commit). Nach diesem bedeutsamen Ereignis betrachten wir die verteilte Transaktion als abgeschlossen.
        \n \"Schr\u00f6dingers <\/li>\n<\/ol>\n

        \nDer Konsensalgorithmus besteht in einfachen F\u00e4llen aus vier Schritten: Vorschlag (propose), Abstimmung (voting), Akzeptanz (accept) und Best\u00e4tigung der Akzeptanz (accepted).<\/p>\n

        Wenn wir in einem der Schritte keinen Konsens erzielen k\u00f6nnen, wird der Algorithmus neu gestartet, wobei die Informationen ber\u00fccksichtigt werden, die die Knoten bereitstellen, die sich geweigert haben, den vorgeschlagenen Wert zu best\u00e4tigen.<\/p>\n

        Der Konsensalgorithmus in einem asynchronen System<\/h2>\n

        \nBis zu diesem Punkt verlief alles reibungslos, da wir von einem synchronen Nachrichtenmodell sprachen. Aber wir wissen, dass wir in der heutigen Welt alles asynchron erledigen. Wie funktioniert ein \u00e4hnlicher Algorithmus in einem System mit einem asynchronen Nachrichtenmodell, in dem wir davon ausgehen, dass die Wartezeit auf eine Antwort des Knotens beliebig lang sein kann (\u00fcbrigens kann der Ausfall eines Knotens ebenfalls als Beispiel betrachtet werden, bei dem der Knoten beliebig lange antworten kann). <\/p>\n

        Jetzt, da wir wissen, wie der Konsensalgorithmus grunds\u00e4tzlich funktioniert, richtet sich die Frage an die neugierigen Leser, die bis hierher gelesen haben: Wie viele Knoten in einem System mit N Knoten und einem asynchronen Nachrichtenmodell k\u00f6nnen ausfallen, damit das System weiterhin Konsens erreichen kann?<\/p><\/blockquote>\n

        \nDie richtige Antwort und die Begr\u00fcndung finden Sie hinter dem Spoiler.<\/b>Die richtige Antwort lautet: 0<\/b>. Wenn auch nur ein Knoten in einem asynchronen System ausf\u00e4llt, kann das System keinen Konsens erreichen. Diese Aussage wurde in der bekannten FLP-Theorem (1985, Fischer, Lynch, Paterson, Link zum Original am Ende des Artikels) bewiesen: \u201eDie Unm\u00f6glichkeit, einen verteilten Konsens zu erreichen, wenn mindestens ein Knoten ausf\u00e4llt\u201c.
        \n\"Schr\u00f6dingers
        \nLeute, dann haben wir ein Problem, wir sind es doch gewohnt, dass alles asynchron ist. Und jetzt ist da so etwas. Wie geht es weiter? <\/p>\n

        Wir haben gerade \u00fcber Theorie und Mathematik gesprochen. Was bedeutet \u201eKonsens kann nicht erreicht werden\u201c, wenn wir es von der mathematischen Sprache in unsere \u2013 ingenieurtechnische \u2013 \u00fcbersetzen? Das bedeutet, dass \u201enicht immer ein Konsens erreicht werden kann\u201c, d.h. es gibt einen Fall, in dem Konsens unerreichbar ist. Und welcher Fall ist das? <\/p>\n

        Dies stellt einen Versto\u00df gegen die oben beschriebene Liveness-Eigenschaft dar. Es gibt kein gemeinsames Einvernehmen und das System kann keinen Fortschritt erzielen (kann nicht innerhalb einer endlichen Zeit abgeschlossen werden), wenn wir keine Antwort von allen Knoten erhalten. Denn in einem asynchronen System haben wir keine vorhersehbare Antwortzeit, und wir k\u00f6nnen nicht wissen, ob ein Knoten ausgefallen ist oder einfach nur lange braucht, um zu antworten.<\/p>\n

        In der Praxis k\u00f6nnen wir jedoch eine L\u00f6sung finden. Angenommen, unser Algorithmus kann im Falle von Ausf\u00e4llen lange arbeiten (potenziell unbegrenzt). In den meisten Situationen, in denen die meisten Knoten korrekt funktionieren, werden wir Fortschritte im System machen. <\/p>\n

        In der Praxis arbeiten wir mit teilweise synchronen Kommunikationsmodellen. Teilweise Synchronit\u00e4t wird so verstanden: Im Allgemeinen haben wir ein asynchrones Modell, aber formal wird ein Begriff von \u201eglobaler Stabilisationszeit\u201c an einem bestimmten Zeitpunkt eingef\u00fchrt. <\/p>\n

        Dieser Zeitpunkt kann lange auf sich warten lassen, doch eines Tages wird er kommen. Der virtuelle Wecker wird l\u00e4uten, und ab diesem Moment k\u00f6nnen wir die Zeitdifferenz vorhersagen, in der Nachrichten ankommen. Von diesem Augenblick an verwandelt sich das System von asynchron in synchron. In der Praxis haben wir es mit genau solchen Systemen zu tun. <\/p>\n

        Der Paxos-Algorithmus l\u00f6st Konsensprobleme<\/h2>\n

        \nPaxos <\/a><\/noindex> \u2013 ist eine Familie von Algorithmen, die das Konsensproblem f\u00fcr teilweise synchronisierte Systeme l\u00f6sen, unter der Annahme, dass einige Knoten ausfallen k\u00f6nnen. Der Autor des Paxos-Algorithmus ist Leslie Lamport<\/a><\/noindex>. Er pr\u00e4sentierte einen formalen Beweis f\u00fcr das Bestehen und die Korrektheit des Algorithmus im Jahr 1989. <\/p>\n

        Doch der Beweis erb proved sich als alles andere als trivial. Die erste Ver\u00f6ffentlichung erschien erst im Jahr 1998 (33 Seiten) mit einer Beschreibung des Algorithmus. Es stellte sich heraus, dass sie \u00e4u\u00dferst schwer verst\u00e4ndlich war, und im Jahr 2001 wurde eine Erl\u00e4uterung des Artikels ver\u00f6ffentlicht, die 14 Seiten umfasste. Die Umfangsangaben der Ver\u00f6ffentlichungen sollen verdeutlichen, dass das Konsensproblem in der Tat nicht einfach ist und hinter solchen Algorithmen eine enorme Anstrengung der kl\u00fcgsten K\u00f6pfe steht.<\/p>\n

        Interessanterweise bemerkte Leslie Lamport in seinem Vortrag, dass es in dem zweiten erkl\u00e4renden Artikel eine Aussage gibt, eine Zeile (er pr\u00e4zisierte nicht welche), die unterschiedlich interpretiert werden kann. Aus diesem Grund funktionieren viele moderne Implementierungen von Paxos nicht ganz korrekt. <\/p><\/blockquote>\n

        \nEine detaillierte Analyse der Funktionsweise von Paxos w\u00fcrde mehrere Artikel erfordern, daher versuche ich, die Hauptidee des Algorithmus sehr kurz zu vermitteln. In den Links am Ende dieses Artikels finden Sie Materialien f\u00fcr eine tiefere Auseinandersetzung mit diesem Thema.<\/p>\n

        Rollen in Paxos<\/h4>\n

        \nIm Algorithmus Paxos gibt es das Konzept von Rollen. Schauen wir uns die drei Hauptrollen an (es gibt Modifikationen mit zus\u00e4tzlichen Rollen):<\/p>\n

          \n
        1. Proposers (manchmal auch als: F\u00fchrer oder Koordinatoren bezeichnet)<\/b>. Das sind die Leute, die von einem neuen Wert des Nutzers erfahren und die Rolle des F\u00fchrers \u00fcbernehmen. Ihre Aufgabe ist es, eine Runde zur Vorschlag eines neuen Wertes einzuleiten und die weiteren Aktionen der Knoten zu koordinieren. Dabei erlaubt Paxos in bestimmten Situationen mehrere F\u00fchrer.<\/li>\n
        2. Acceptors (W\u00e4hler)<\/b>. Dies sind Knoten, die \u00fcber die Annahme oder Ablehnung eines bestimmten Wertes abstimmen. Ihre Rolle ist sehr wichtig, da sie die Entscheidung treffen, in welchen Zustand das System nach der n\u00e4chsten Phase des Konsensalgorithmus \u00fcbergehen wird (oder auch nicht).<\/li>\n
        3. Lernende<\/b>. Knoten, die einfach den neuen angenommenen Wert annehmen und aufzeichnen, wenn sich der Zustand des Systems ge\u00e4ndert hat. Sie treffen keine Entscheidungen, sondern erhalten nur Daten und k\u00f6nnen diese an den Endbenutzer weitergeben. <\/li>\n<\/ol>\n

          \nEin Knoten kann in unterschiedlichen Situationen mehrere Rollen kombinieren. <\/p>\n

          Der Begriff Quorum<\/h4>\n

          \nWir nehmen an, dass wir ein System aus N<\/b> Knoten haben. Und aus diesen k\u00f6nnen maximal F<\/b> Knoten ausfallen. Wenn F Knoten ausfallen, muss unser Cluster mindestens 2F + 1<\/b> Acceptorknoten. <\/p>\n

          Dies ist notwendig, damit wir selbst in der schlimmsten Situation immer 'gute', korrekt arbeitende Knoten in der Mehrheit haben. Das hei\u00dft, F + 1<\/b> Die \u201eguten\u201c Knoten, die sich bereit erkl\u00e4rt haben, und der endg\u00fcltige Wert wird angenommen. Andernfalls k\u00f6nnte es zu einer Situation kommen, in der unsere verschiedenen lokalen Gruppen unterschiedliche Werte annehmen und sich nicht einigen k\u00f6nnen. Daher ben\u00f6tigen wir eine absolute Mehrheit, um im Voting zu gewinnen.<\/p>\n

          Das Grundkonzept des Paxos-Konsensalgorithmus<\/h4>\n

          \nDer Paxos-Algorithmus umfasst zwei gro\u00dfe Phasen, die jeweils in zwei Schritte unterteilt sind:<\/p>\n

            \n
          1. Phase 1a: Vorbereiten<\/b>. In der Vorbereitungsphase informiert der Lieder (Proposer) alle Knoten: \u201eWir beginnen eine neue Abstimmungsrunde. Wir haben eine neue Runde. Die Nummer dieser Runde ist n. Jetzt werden wir abstimmen.\u201c W\u00e4hrend er lediglich den Beginn eines neuen Zyklus ank\u00fcndigt, gibt er noch keinen neuen Wert bekannt. Das Ziel dieser Phase besteht darin, eine neue Runde einzuleiten und allen seinen einzigartigen Nummern mitzuteilen. Die Rundenummer ist wichtig; sie muss gr\u00f6\u00dfer sein als alle vorherigen Abstimmungsnummern aller vorherigen Leiter. Denn nur durch die Rundenummer k\u00f6nnen die anderen Knoten im System verstehen, wie aktuell die Daten des Leiters sind. Vermutlich verf\u00fcgen die anderen Knoten bereits \u00fcber Abstimmungsergebnisse aus wesentlich sp\u00e4teren Runden und k\u00f6nnen dem Leiter einfach mitteilen, dass er hinterherh\u00e4ngt.<\/li>\n
          2. Phase 1b: Versprechen<\/b>. Wenn die Acceptor-Knoten die Nummer des neuen Abstimmungsdurchgangs erhalten haben, gibt es zwei m\u00f6gliche Ergebnisse: \n