Ich suche nach einem Algorithmus, bei dem Gruppen verbundener Knoten zu einer neuen Gruppe zusammengeführt werden können (indem Verknüpfungen zwischen Knoten aus verschiedenen Gruppen erstellt werden). Und wo eine Gruppe partitioniert werden kann, um neue Partitionen zu bilden.
Im Gegensatz zum Konsensus-Stil von Mitgliedschaftsprotokollen (z. B. dem im Raft-Papier beschriebenen), bei dem nur eine Gruppe nach der Partition verbleiben kann, möchte ich, dass jede neue Partition eine neue Gruppe bildet.
Ich möchte auch, dass sich jeder seiner Mitglieder für jede Partition darauf verständigt, wer zu dieser Partition gehört, mit einer starken Konsistenzgarantie.
Oder anders gesagt, möchte ich, dass die folgende Eigenschaft gilt: Nachdem eine Gruppe eine Änderung der Mitgliedschaft erfährt, sollten zwei Knoten, die zur ursprünglichen Gruppe gehörten, immer noch miteinander kommunizieren können (es gibt einen Pfad zwischen den beiden) über die Reihenfolge der Änderungen, die der Gruppe passiert sind.
Mein Verständnis ist, dass die Tatsache, dass jede neue Partition sich auf eine andere Gruppe von Mitgliedern in gewisser Weise einigen wird, impliziert, dass der Konsistenzteil aus dem CAP-Theorem gelockert ist. Ich hoffe, dass ein solches Protokoll existiert (?).
Kein Konsens-Protokoll (wie Paxos, Raft usw.) kann genutzt werden, um ein Mehrgruppen-Mitgliedschaftsprotokoll zu entwickeln. Dies liegt daran, dass alle Konsensprotokolle auf der Grundidee basieren, dass eine Entscheidung nur dann getroffen werden kann, wenn die Mehrheit der Mitglieder "zugestimmt" hat. Auf diese Weise wird das "split-brain" -Phänomen vermieden, da es keine 2 Partitionen (mit einer Größe größer als die Mehrheit: (n/2)+1 ) geben könnte, die sich auf einen anderen Leader (und damit Mitgliedssatz) geeinigt haben, zumindest seit Ein Mitglied würde Mitglied beider Partitionen sein und hätte nur für eine der Partitionen gewählt (die erste, die nach der Stimme gefragt hat).
Ein Protokoll, das möglicherweise zum Erstellen eines Mitgliedschaftsprotokolls für mehrere Gruppen verwendet werden kann, ist das Virtual Synchrony . Beachten Sie jedoch, dass die virtuelle Synchronität ein Protokoll ist, mit dem Nachrichten an (statisch) vordefinierte Prozessgruppen gesendet werden, auch an die derzeit vorhandenen Mitglieder dieser Gruppen. Daher ist es nicht für Fälle gedacht, in denen neue Prozessgruppen (dynamisch) bei jeder neuen Partition erstellt werden sollten. Beachten Sie auch, dass die virtuelle Synchronität ein Protokoll ist, das nicht auf größere Mitglieder skaliert, da die Nachrichtenlatenz proportional zur Gruppengröße ist.
Ich glaube, dass Sie mit dem Virtual-Synchrony-Protokoll ein solches Membership-Protokoll entwickeln könnten, das die Bedingung
erfüllen könnteNachdem eine Gruppe eine Änderung der Mitgliedschaft vorgenommen hat, sollten zwei Knoten, die zur ursprünglichen Gruppe gehörten, immer noch kommunizieren können (es gibt einen Pfad zwischen den beiden). Sie sollten sich über die Reihenfolge der Änderungen einigen, die der Gruppe passiert ist
Beachten Sie jedoch, dass diese Mitgliedschaft im strengen Sinne nicht stark konsistent ist, da der Ausfall eines Knotens möglicherweise innerhalb der Gruppe weitergegeben wird. Nichtsdestoweniger werden die Nachrichtenlieferungen (was am wichtigsten ist) so geliefert, dass diese Lieferungen den Mitgliedschaften der Gruppe gehorchen. Dies wird erreicht, indem auf der Mitgliederseite Befehle für die Nachrichtenzustellung festgelegt werden.
Ein anderer alternativer Ansatz für ein Mitgliedschaftsprotokoll sind klatschbasierte Mitgliedschaftsprotokolle , wobei reale Implementierungen in verschiedene integriert sind Werkzeuge in der Industrie, wie Konsul . Um diesen Ansatz zu nutzen, könnten Sie je nach den verschiedenen Gruppen, die Sie überwachen möchten, mehrere verschiedene Nachrichtenklassen von jedem Mitglied ausgeben. Jedoch sind diese Gruppen wiederum innerhalb des Protokolls statisch definiert und schließlich konsistent (was bedeutet, dass jeder Fehler schließlich von allen aktiven Mitgliedern erkannt wird).
Als Schlussfolgerung denke ich, dass ein streng konsistentes Mitgliedschaftsprotokoll in einer strikten Definition nicht durchführbar ist, da Sie nicht zwischen einem Mitglied, das gescheitert ist, und einem Mitglied, das wirklich sehr langsam reagiert (basierend auf FLP und CAP-Theorem).
Tags und Links algorithm distributed consistency membership