{"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":"Die Katze Schr\u00f6dingers ohne Kiste: das Konsensproblem in verteilten Systemen","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Stellen wir uns vor. In einem Raum sind 5 Katzen eingesperrt, und 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 die Katze Schr\u00f6dingers ist und die anderen Katzen nichts von ihrer Entscheidung wissen, stellt sich die Frage: \u201eWie k\u00f6nnen sie das tun?\u201c <\/p>\n

In diesem Artikel werde ich Ihnen einfach die theoretischen Grundlagen der verteilten Systeme und die Prinzipien ihrer Funktionsweise erl\u00e4utern. Au\u00dferdem werde ich kurz die zentrale Idee, die Paxos zugrunde liegt, anrei\u00dfen. <\/p>\n

\"Die
\n<\/a><\/noindex>
\nWenn Entwickler Cloud-Infrastrukturen, verschiedene Datenbanken und Cluster mit einer gro\u00dfen Anzahl von Knoten nutzen, sind sie sich sicher, dass die Daten intakt, gesichert und jederzeit verf\u00fcgbar sind. Aber woher kommen die Garantien?<\/p>\n

Im Grunde genommen sind die Garantien, die wir haben, die Garantien des Anbieters. Diese werden in der Dokumentation ungef\u00e4hr wie folgt beschrieben: \u201eDieser Service ist zuverl\u00e4ssig genug, er hat ein vorgegebenes SLA, machen Sie sich keine Sorgen, alles wird verteilt funktionieren, wie Sie es erwarten.\u201c <\/p>\n

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

Vor kurzem bin ich zu einer Schule f\u00fcr verteilte Berechnungen<\/a><\/noindex> gefahren und war von diesem Thema sehr inspiriert. Die Vorlesungen in der Schule erinnerten mehr an Mathematikanalysis, als an etwas, das mit Computersystemen zu tun hat. Aber genau so wurden zur damaligen Zeit die entscheidenden Algorithmen bewiesen, die wir jeden Tag nutzen, 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 prinzipiell die M\u00f6glichkeit, dass dieser Algorithmus existiert, einfach mit Stift und Papier bewiesen werden kann. Gleichzeitig wird der Algorithmus in der Praxis in gro\u00dfen Systemen eingesetzt, die auf einer riesigen Anzahl von Knoten in Clouds laufen. <\/p>\n

Eine einfache Illustration daf\u00fcr, worum es gleich gehen wird: das Problem der zwei Gener\u00e4le.<\/b>Lassen Sie uns zur Auflockerung die Aufgabe der zwei Gener\u00e4le betrachten.<\/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 Kommando der Gener\u00e4le A1 und A2 sind auf beiden Seiten der Stadt positioniert. Die Aufgabe der Roten ist es, die wei\u00dfe Stadt anzugreifen und zu siegen. Allerdings ist die Armee jedes roten Generals f\u00fcr sich genommen kleiner als die der Wei\u00dfen.<\/p>\n

\"Die
\n
\nDie Bedingungen f\u00fcr den Sieg der Roten: Beide Gener\u00e4le m\u00fcssen gleichzeitig angreifen, um einen zahlenm\u00e4\u00dfigen Vorteil gegen\u00fcber den Wei\u00dfen zu erlangen. Dazu m\u00fcssen sich die Gener\u00e4le A1 und A2 einigen. Wenn jeder separat angreift, verlieren die Roten. <\/p>\n

Um sich zu verst\u00e4ndigen, k\u00f6nnen die Gener\u00e4le A1 und A2 Boten durch das Gebiet der wei\u00dfen Stadt senden. Ein Bote kann den verb\u00fcndeten General erfolgreich erreichen oder von den Gegnern abgefangen werden. Frage: Gibt es eine solche Abfolge von Kommunikationen zwischen den roten Gener\u00e4len (eine Sequenz von Boten, die von A1 zu A2 und umgekehrt von A2 zu A1 gesendet werden), bei der sie garantiert eine Einigung \u00fcber den Angriff zur Stunde X erreichen? Hierbei wird unter Garantien verstanden, dass beide Gener\u00e4le eine eindeutige Best\u00e4tigung erhalten, dass der Verb\u00fcndete (der andere General) genau zur vereinbarten Zeit X angreift.<\/p>\n

Angenommen, A1 sendet einen Boten zu A2 mit der Botschaft: \u201eLass uns heute 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 Botschaft: \u201eJa, lass uns heute die Wei\u00dfen \u00fcberrennen\u201c. Doch jetzt wei\u00df General A2 nicht, ob sein Bote angekommen ist oder nicht, er hat keine Garantien, dass der Angriff gleichzeitig erfolgt. Nun ben\u00f6tigt auch General A2 wieder eine Best\u00e4tigung.<\/p>\n

Wenn man ihre Kommunikation weiter ausf\u00fchrt, wird sich Folgendes herausstellen: Egal wie viele Zyklen des Nachrichtenaustauschs es gibt, es gibt keinen Weg, beide Gener\u00e4le garantiert dar\u00fcber zu informieren, dass ihre Nachrichten erhalten wurden (vorausgesetzt, dass einer der Boten abgefangen werden kann).<\/p>\n

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

Wir f\u00fchren den Begriff der verteilten Systeme ein.<\/h2>\n

\nEin verteiltes System ist eine Gruppe von Computern (im Folgenden als Knoten bezeichnet), die Nachrichten austauschen k\u00f6nnen. Jeder einzelne Knoten ist eine gewisse autonome Entit\u00e4t. Der Knoten kann Aufgaben eigenst\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, interessiert uns in diesem Kontext nicht. Wichtig ist, dass die Knoten des verteilten Systems Daten miteinander austauschen k\u00f6nnen, indem sie Nachrichten senden.<\/p>\n

Die Definition selbst scheint nicht sehr komplex zu sein, aber man muss bedenken, dass ein verteiltes System eine Reihe von Attributen hat, die f\u00fcr uns wichtig sein werden.<\/p>\n

Attribute vernetzter Systeme<\/h4>\n

<\/p>\n

    \n
  1. Nebenl\u00e4ufigkeit<\/b> \u2013 die M\u00f6glichkeit des Auftretens gleichzeitiger oder konkurrierender Ereignisse im System. Dar\u00fcber hinaus werden wir davon ausgehen, dass Ereignisse, die an zwei verschiedenen Knoten aufgetreten sind, potenziell konkurrierend sind, solange wir keine klare Reihenfolge haben, in der diese Ereignisse aufgetreten sind. Und normalerweise haben wir diese nicht.<\/li>\n
  2. Fehlen globaler Uhren<\/b>. Wir haben keine klare Reihenfolge der Ereignisse aufgrund des Fehlens globaler Uhren. In der normalen Welt der Menschen sind wir es gewohnt, dass wir Uhren haben und die Zeit absolut ist. Alles \u00e4ndert sich, wenn es um verteilte Systeme geht. Selbst hochpr\u00e4zise Atomuhren haben einen Drift, und es kann Situationen geben, in denen wir nicht sagen k\u00f6nnen, welches der beiden Ereignisse zuerst aufgetreten ist. Daher k\u00f6nnen wir uns auch nicht auf die Zeit verlassen.<\/li>\n
  3. Unabh\u00e4ngiger Ausfall der Knoten im System<\/b>. Es gibt ein weiteres Problem: Etwas kann einfach schiefgehen, weil unsere Knoten nicht ewig sind. Eine Festplatte kann ausfallen, eine virtuelle Maschine in der Cloud kann neu gestartet werden, das Netzwerk kann aussetzen und Nachrichten k\u00f6nnen verloren gehen. Dar\u00fcber hinaus kann es Situationen geben, in denen Knoten funktionieren, aber dabei 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 den Knoten<\/b>. Wir haben bereits festgestellt, dass Knoten \u00fcber den Austausch von Nachrichten kommunizieren. Es gibt zwei bekannte Modelle f\u00fcr den Nachrichtenaustausch: 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 eine endliche, bekannte Zeitdifferenz besteht, nach der eine Nachricht garantiert von einem Knoten zum 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 gehen wir davon aus, dass die Wartezeit endlich ist, jedoch gibt es keine solche Zeitdifferenz, nach deren Ablauf wir garantieren k\u00f6nnen, dass der Knoten ausgefallen ist. Das hei\u00dft, die Wartezeit auf eine Nachricht von einem Knoten kann beliebig lang sein. Dies ist eine wichtige Definition, \u00fcber die wir weiter sprechen werden. <\/p>\n

    Der Begriff des Konsenses in verteilten Systemen<\/h2>\n

    \nEhe wir den Begriff Konsens formal definieren, betrachten wir ein Beispiel, in dem er ben\u00f6tigt wird, n\u00e4mlich \u2013 State Machine Replication<\/b>. <\/p>\n

    Wir haben ein gewisses verteiltes Protokoll. Wir m\u00f6chten, dass es konsistent ist und identische Daten auf allen Knoten des verteilten Systems enth\u00e4lt. Wenn einer der Knoten einen neuen Wert erf\u00e4hrt, den er im Protokoll speichern m\u00f6chte, besteht seine Aufgabe darin, diesen Wert allen anderen Knoten vorzuschlagen, damit das Protokoll auf allen Knoten aktualisiert wird und das System in einen neuen konsistenten Zustand \u00fcbergeht. Dabei ist es wichtig, dass sich die Knoten untereinander einigen: Alle Knoten stimmen zu, dass der vorgeschlagene neue Wert korrekt ist, alle Knoten haben diesen Wert akzeptiert, und nur in diesem Fall k\u00f6nnen alle den neuen Wert im Protokoll speichern. <\/p>\n

    Mit anderen Worten: Keiner der Knoten hat widersprochen, dass er aktuellere Informationen hat und dass der vorgeschlagene Wert falsch ist. Die Vereinbarung zwischen den Knoten und die Einigung \u00fcber einen einheitlichen, akzeptierten Wert ist der Konsens in einem verteilten System. Im Folgenden werden wir \u00fcber Algorithmen sprechen, die es dem verteilten System erm\u00f6glichen, konsistent Konsens zu erreichen.
    \n\"Die
    \nFormell gesagt k\u00f6nnen wir den Konsensalgorithmus (oder einfach Konsensalgorithmus) als eine Funktion definieren, die ein verteiltes System von Zustand A nach Zustand B \u00fcberf\u00fchrt. Dabei ist dieser Zustand von allen Knoten akzeptiert, und alle Knoten k\u00f6nnen ihn best\u00e4tigen. Wie sich herausstellt, ist diese Aufgabe alles andere als trivial, wie es auf den ersten Blick scheint.<\/p>\n

    Eigenschaften des Konsensalgorithmus<\/h4>\n

    \nDer Konsensalgorithmus muss drei Eigenschaften aufweisen, damit das System weiterhin besteht und einen Fortschritt beim \u00dcbergang von einem Zustand zum n\u00e4chsten hat:<\/p>\n

      \n
    1. Einigungszustimmung <\/b> \u2013 alle korrekt funktionierenden Knoten m\u00fcssen denselben Wert akzeptieren (dieses Merkmal wird in den Artikeln auch als Sicherheitsmerkmal bezeichnet). Alle Knoten, die derzeit funktionsf\u00e4hig sind (nicht ausgefallen oder desynchronisiert sind), m\u00fcssen sich einigen und einen bestimmten endg\u00fcltigen gemeinsamen Wert annehmen.\n

      Hier ist es wichtig zu verstehen, dass die Knoten in dem von uns betrachteten verteilten System sich einigen wollen. Das hei\u00dft, wir sprechen jetzt \u00fcber Systeme, in denen einfach etwas ausfallen kann (zum Beispiel kann ein bestimmter Knoten ausfallen), aber in diesem System gibt es keine Knoten, die absichtlich gegen andere arbeiten (wie bei dem Problem der byzantinischen Gener\u00e4le). Aufgrund dieser Eigenschaft bleibt das System konsistent.<\/li>\n

    2. Integrit\u00e4t <\/b> \u2013 wenn alle korrekt funktionierenden Knoten denselben Wert vorschlagen v<\/b>, bedeutet das, dass jeder korrekt funktionierende Knoten diesen Wert annehmen muss. v<\/b>. <\/li>\n
    3. Beendigung <\/b>\u2013 alle korrekt funktionierenden Knoten m\u00fcssen schlie\u00dflich einen bestimmten Wert annehmen (Lebensf\u00e4higkeitseigenschaft), was dem Algorithmus Fortschritt im System erm\u00f6glicht. Jeder einzelne korrekt funktionierende Knoten muss irgendwann 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 die Funktionsweise des Konsensalgorithmus<\/h4>\n

      \nW\u00e4hrend die Eigenschaften des Algorithmus m\u00f6glicherweise nicht ganz klar sind, wollen wir an einem Beispiel veranschaulichen, welche Phasen der einfachste Konsensalgorithmus in einem System mit synchronem Nachrichtenmodell durchl\u00e4uft, in dem alle Knoten ordnungsgem\u00e4\u00df funktionieren, Nachrichten nicht verloren gehen und nichts kaputt geht (passiert das tats\u00e4chlich?)).<\/p>\n

        \n
      1. Alles beginnt mit dem Vorschlag zur Hand und zum Herzen (Propose). Angenommen, ein Client hat sich mit dem Knoten namens \u201eKnoten 1\u201c verbunden und eine Transaktion gestartet, indem er dem Knoten den neuen Wert \u2013 O \u2013 \u00fcbermittelt hat. 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 frische Daten hat, und er sendet an alle anderen Knoten Nachrichten: \u201eSeht her! Mir wurde der Wert \u201eO\u201c \u00fcbermittelt, und ich m\u00f6chte ihn speichern! Bitte best\u00e4tigt, dass auch ihr \u201eO\u201c in euer Protokoll aufnehmen werdet.\u201c\n

        \"Die<\/li>\n

      2. Die n\u00e4chste Phase ist die Abstimmung \u00fcber den vorgeschlagenen Wert (Voting). Warum ist sie notwendig? Es k\u00f6nnte sein, dass anderen Knoten aktuellere Informationen zugetragen wurden und sie Daten zu derselben Transaktion haben.\n

        \"Die
        \n
        \nWenn der Knoten \u201eKnoten 1\u201c seinen Vorschlag sendet, \u00fcberpr\u00fcfen die anderen Knoten in ihren Protokollen die Daten zu diesem Ereignis. Wenn es keine Widerspr\u00fcche gibt, erkl\u00e4ren die Knoten: \u201eJa, ich habe keine anderen Daten 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 zu! Ich habe aktuellere Daten 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 daf\u00fcr waren, geht das System in die n\u00e4chste Phase \u00fcber \u2013 die Annahme des Wertes (Accept). \u201eKnoten 1\u201c sammelt alle Antworten der anderen Knoten und teilt mit: \u201eAlle haben dem Wert \u201eO\u201c zugestimmt! Jetzt erkl\u00e4re ich offiziell, dass \u201eO\u201c unser neues, einheitliches Wert ist! Schreibt es euch in euer Notizbuch, vergesst es nicht. Tragt es in euer Protokoll ein!\u201c\n

        \"Die<\/li>\n

      4. Die anderen Knoten senden eine Best\u00e4tigung (Accepted), dass sie den Wert \u201eO\u201c in ihr Protokoll aufgenommen haben, und es gab in der Zwischenzeit keine neuen Informationen (eine Art zweiphasiger Commit). Nach diesem denkw\u00fcrdigen Ereignis betrachten wir die verteilte Transaktion als abgeschlossen.
        \n \"Die <\/li>\n<\/ol>\n

        \nSo besteht der Konsensalgorithmus im einfachsten Fall aus vier Schritten: propose, Abstimmung (voting), Annahme (accept), Best\u00e4tigung der Annahme (accepted).<\/p>\n

        Wenn wir in einem Schritt keinen Konsens erreichen konnten, wird der Algorithmus neu gestartet, unter Ber\u00fccksichtigung der Informationen, die die Knoten, die sich weigerten, den vorgeschlagenen Wert zu best\u00e4tigen, bereitstellen.<\/p>\n

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

        \nBis jetzt lief alles glatt, denn es ging um ein synchrones Kommunikationsmodell. Aber wir wissen, dass wir in der modernen Welt alles asynchron machen. Wie funktioniert also ein \u00e4hnlicher Algorithmus in einem System mit asynchronem Nachrichtenaustausch, in dem wir annehmen, dass die Wartezeit auf eine Antwort von einem Knoten beliebig lang sein kann (zumal man auch den Ausfall eines Knotens als Beispiel betrachten kann, wenn der Knoten beliebig lange antworten kann). <\/p>\n

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

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

        Wir haben gerade \u00fcber Theorie, \u00fcber Mathematik gesprochen. Was bedeutet es, dass \u201eKonsens nicht erreicht werden kann\u201c, wenn wir aus der mathematischen Sprache in unsere Ingenieursprache \u00fcbersetzen? Das bedeutet, dass \u201enicht immer erreicht werden kann\u201c, d.h. es gibt einen Fall, in dem Konsens nicht erreichbar ist. Aber was ist das f\u00fcr ein Fall? <\/p>\n

        Das ist genau das Versagen der liveness property, die oben beschrieben wurde. Wir haben kein gemeinsames Einvernehmen, und das System kann keinen Fortschritt haben (kann nicht innerhalb einer endlichen Zeit abgeschlossen werden), wenn wir keine Antwort von allen Knoten haben. 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 antwortet.<\/p>\n

        Aber in der Praxis k\u00f6nnen wir eine L\u00f6sung finden. Nehmen wir an, unser Algorithmus k\u00f6nnte im Falle von Ausf\u00e4llen lange arbeiten (potenziell unbegrenzt). Doch in den meisten Situationen, wenn die Mehrheit der Knoten korrekt funktioniert, werden wir Fortschritt im System haben. <\/p>\n

        In der Praxis haben wir es mit teilweise synchronen Kommunikationsmodellen zu tun. Teilweise Synchronit\u00e4t bedeutet, dass wir im Allgemeinen ein asynchrones Modell haben, aber formal wird ein gewisses Konzept der \"globalen Stabilisationszeit\" an einem bestimmten Moment eingef\u00fchrt. <\/p>\n

        Dieser Moment kann unbegrenzt lange auf sich warten lassen, aber eines Tages muss er eintreten. Ein virtueller Wecker wird klingeln und ab diesem Moment k\u00f6nnen wir die Zeitdifferenz vorhersagen, die ben\u00f6tigt wird, damit die Nachrichten ankommen. Ab diesem Moment wird das System von asynchron in synchron umgewandelt. In der Praxis haben wir es genau mit solchen Systemen zu tun. <\/p>\n

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

        \nPaxos <\/a><\/noindex> ist ein Algorithmusfamilie, die das Konsensproblem f\u00fcr teilweise synchronisierte Systeme l\u00f6st, wobei einige Knoten ausfallen k\u00f6nnen. Der Autor von Paxos ist Leslie Lamport<\/a><\/noindex>. Er schlug 1989 einen formalen Beweis f\u00fcr die Existenz und Korrektheit des Algorithmus vor. <\/p>\n

        Aber der Beweis stellte sich als alles andere als trivial heraus. Die erste Ver\u00f6ffentlichung erschien erst 1998 (33 Seiten) mit einer Beschreibung des Algorithmus. Wie sich herausstellte, war er \u00e4u\u00dferst schwer verst\u00e4ndlich, und im Jahr 2001 wurde eine Erl\u00e4uterung zu dem Artikel ver\u00f6ffentlicht, die 14 Seiten umfasste. Die Seitenzahlen wurden erw\u00e4hnt, um zu zeigen, dass das Konsensproblem in Wirklichkeit alles andere als einfach ist und hinter solchen Algorithmen immense M\u00fchen der kl\u00fcgsten K\u00f6pfe stehen.<\/p>\n

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

        \nEine detaillierte Analyse des Paxos-Algorithmus w\u00fcrde nicht nur einen Artikel in Anspruch nehmen, daher werde ich versuchen, die Hauptidee des Algorithmus sehr kurz zu vermitteln. In den Links am Ende meines Artikels finden Sie Materialien f\u00fcr eine vertiefte Auseinandersetzung mit diesem Thema.<\/p>\n

        Rollen in Paxos<\/h4>\n

        \nIm Paxos-Algorithmus gibt es das Konzept der Rollen. Lassen Sie uns die drei Hauptrollen betrachten (es gibt Modifikationen mit zus\u00e4tzlichen Rollen):<\/p>\n

          \n
        1. Proposers (auch k\u00f6nnen die Begriffe: Leiter oder Koordinatoren verwendet werden)<\/b>. Das sind die Leute, die von einem neuen Wert des Benutzers erfahren und die Rolle des Leaders \u00fcbernehmen. Ihre Aufgabe ist es, eine Runde zur Einf\u00fchrung eines neuen Wertes zu starten und die weiteren Schritte der Knoten zu koordinieren. Paxos erlaubt dabei das Vorhandensein mehrerer Leader in bestimmten Situationen.<\/li>\n
        2. Akzeptoren (W\u00e4hler)<\/b>. Das sind Knoten, die f\u00fcr die Annahme oder Ablehnung eines bestimmten Wertes stimmen. Ihre Rolle ist sehr wichtig, denn von ihnen h\u00e4ngt die Entscheidung ab, in welchen Zustand das System nach der n\u00e4chsten Phase des Konsensalgorithmus \u00fcbergeht (oder nicht \u00fcbergeht).<\/li>\n
        3. Lerner<\/b>. Knoten, die einfach den neuen angenommenen Wert akzeptieren und aufzeichnen, wenn sich der Zustand des Systems \u00e4ndert. Sie treffen keine Entscheidungen, sondern erhalten lediglich Daten und k\u00f6nnen diese an den Endbenutzer weitergeben. <\/li>\n<\/ol>\n

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

          Das Konzept des Quorums<\/h4>\n

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

          Dies ist notwendig, damit wir immer, selbst in der schlechtesten Situation, eine Mehrheit aus \"guten\", korrekt funktionierenden Knoten haben. Das hei\u00dft, F + 1<\/b> \"gute\" Knoten, die zugestimmt haben, und der finale Wert wird angenommen. Andernfalls k\u00f6nnte es zu einer Situation kommen, in der verschiedene lokale Gruppen unterschiedliche Werte annehmen und sich nicht einigen k\u00f6nnen. Daher ben\u00f6tigen wir eine absolute Mehrheit, um in der Abstimmung zu gewinnen.<\/p>\n

          Die allgemeine Idee des Paxos-Konsensusalgorithmus<\/h4>\n

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

            \n
          1. Phase 1a: Vorbereiten<\/b>. In der Vorbereitungsphase informiert der F\u00fchrer (proposer) alle Knoten: \u201eWir beginnen eine neue Phase der Abstimmung. Wir haben eine neue Runde. Die Nummer dieser Runde ist n. Jetzt beginnen wir zu votieren\u201c. Er informiert lediglich \u00fcber den Beginn eines neuen Zyklus, ohne jedoch einen neuen Wert bekannt zu geben. Die Aufgabe dieses Schrittes ist es, eine neue Runde einzuleiten und allen seine einzigartige Nummer mitzuteilen. Die Rundenummer ist wichtig; sie muss gr\u00f6\u00dfer sein als alle vorherigen Abstimmungsnummern von allen vorherigen F\u00fchrern. Denn nur durch die Rundenummer werden andere Knoten im System verstehen, wie aktuell die Daten des F\u00fchrers sind. Wahrscheinlich haben die anderen Knoten bereits Abstimmungsergebnisse aus deutlich sp\u00e4teren Runden und werden dem F\u00fchrer einfach mitteilen, dass er hinterherhinkt.<\/li>\n
          2. Phase 1b: Versprechen<\/b>. Wenn die acceptor-Knoten die Nummer der neuen Abstimmungsrunde erhalten haben, sind zwei Ergebnisse m\u00f6glich: \n