Cluster - Gegenseitiges überschreiben der Daten verhindern

  • Hi,

    Ich habe in Java eine Art Cluster-System geschrieben. Cluster bedeutet in diesem Fall, dass ich Pakete zwischen den einzelnen Knoten senden und empfangen kann.

    Das hat bisher sehr gut funktioniert, aber ich stehe jetzt vor einem anderen Problem:


    Ich benutze diese Pakete, um die Daten im Cluster auf dem neuesten Stand zu halten.

    Dazu sendet der Knoten, der eine Änderung hat, einfach ein Broadcast-Paket an alle anderen und diese wenden die Änderungen auf sich selbst an.

    Was aber, wenn die Pakete so gesendet werden, dass z. B. Knoten-1 sich selbst aktualisiert und ein Broadcast-Paket sendet, aber

    Knoten-2 sich ebenfalls aktualisiert und ein Broadcast-Paket sendet, bevor das Paket vom ersten Knoten empfangen wird?

    Das würde ja an sich bedeuten, dass sich beide Knoten (nachdem beide Pakete vom anderen empfangen wurden) in unterschiedlichen "Datenzuständen" befinden.


    Ich würde genau das gerne verhindern, jedoch habe ich gerade einen Knoten im Hirn und mir fällt keine geeignete Lösung ein.


    LG Dominic

  • Jeder Zustand benötigt eine ID-Bit. Bevor der Zustand verändert wird, muss von allen Knoten diese Zustandsänderung abgenickt werden. Sollten weitere Änderungen gleichzeitig beantragt werden, so kann man das dann entsprechend mittels dieses ID-Bits erkennen. Dann kann man z.B. mittels Abstimmen oder mittels einer vorher festgelegten Knoten-ID die priorisierte Änderung festlegen (wichtig: vor Festlegung müssen sich dann alle Knoten in einen Ausnahmezustand bewegen, was wieder von allen bestätigt werden muss, bevor weiteres passiert, ansonsten sendet noch irgendein Knoten eine weitere Änderungsanfrage und bringt damit alles durcheinander), diese durchführen und die andere(n) wird/werden dann nach Rückkehr in den "Normalbetrieb" und einem entsprechenden Flip des Zustandsbits erneut beantragt.

    Das wäre vermutlich so die primitivste Lösung, die mir einfällt.

    MfG


    00110101 00110001 00110101 00111000 00110100 00110110 00110011 00110001 00110101 00111001 00110101 00110111 00110100 00110110 00110011 00110000 00110110 00110001 00110101 00110111 00110100 01000100 00110011 01000100 8o

  • Bei einem einzelnen Bit kommt mir das ganze fast so vor, als versuche man an der Stelle eine Art Alternating Bit Protocol zu verwenden, um den Datenaustausch zu regeln. Das ist für die direkte Kommunikation zwischen 2 Clients vielleicht praktisch, bei 3 aufwendig und ab 4 würde ich fast sagen unmachbar.


    Ich würde an der Stelle vielleicht versuchen eine Art von Collision Detection bzw Collision Avoidance zu verwenden. Eine solche Collision Detection wird häufig im Netzwerk-Bereich verwendet (CSMA/CD) und speziell bei drahtlosen Netzwerken kommt die Technik von Collision Avoidance (CSMA/CA) zum Einsatz.

    Bei CSMA/CD, bzw. CSMA/CA besteht eine Übertragung zwischen mehreren Clients, die das gleiche Medium zur Übertragung verwenden, aus mehreren Schritten, die den kollisionsfreien Zugriff auf das Medium sicherstellen sollen.

    Du kannst zur genauen Funktionsweise gerne selber ein wenig recherchieren. Ich hätte so auf Anhieb hier einmal den Link zum entsprechenden Wikipedia-Eintrag. Meine Vorlesungsfolien darf ich wegen Urheberrecht leider nicht einfach hier reinstellen, auch wenn die das etwas kleinschrittiger erklären: https://de.wikipedia.org/wiki/…ccess/Collision_Detection bzw. https://de.wikipedia.org/wiki/…ccess/Collision_Avoidance


    Du kannst es dir ja mal anschauen. Vielleicht hat Aquaatic aber auch was anderes gemeint. Dann siehe meinen Beitrag nicht als Ergänzung, sondern als weiteren Vorschlag :)

  • eine Art Alternating Bit Protocol

    Ja, das hatte ich tatsächlich etwas im Hinterkopf. Ich sehe aber nicht, warum das nicht funktioneren sollte. Man muss aber auf jeden Fall etwas optimieren, im worst-case bei einer voll-vernetzten Topologie würde ich sonst auf n + n² Pakete pro normaler Änderung kommen, wobei n die Cluster-Größe ist. Ich würde mal behaupten, das Quadrat ist inakzeptabel bei häufigeren Änderungen.

    Mit einer Linien-Topologie sollte man das aber auf irgendwas in O(n) drücken können - zumindest in meinen Vorstellungen...

    Was meinst du genau mit dem ID-Bit?

    z.B. ein boolean, der irgendwo in deinem Knoten gespeichert ist. Wofür der genau gut ist, merkst du spätestens, wenn du mal versuchst, das ohne dieses in einem State-Chart zu modellieren:

    hier hätte ich das mal grob versucht. Problem ist: was, wenn ein Knoten jetzt aus consens schon wieder in wait zurückgekehrt ist und eine Änderung anfragt, ein anderer aber noch auf ein Ack eines anderen Knoten wartet? Dann geht ein Knoten in den conflict_enter-Zustand und bleibt dort hängen. Mit dem State-Bit kann man solche Situationen erkennen. Es wird stets dann geflippt, wenn eine Änderung vollzogen wurde. Dann kann man überprüfen, ob das state-Bit, das den Paketen beigefügt wird, bei den Zustandsübergängen im consens-Zustand dem lokal gespeicherten entspricht. Wenn nicht, bedeutet das dann, dass dieses Paket für eine spätere Änderung bestimmt ist (im Übrigen ist dann formal garantiert, dass die Veränderung, aufgrund der man sich gerade im consens-Zustand befindet, glücken wird, da ja ein Knoten offensichtlich schon alle acks erhalten hat).

    MfG


    00110101 00110001 00110101 00111000 00110100 00110110 00110011 00110001 00110101 00111001 00110101 00110111 00110100 00110110 00110011 00110000 00110110 00110001 00110101 00110111 00110100 01000100 00110011 01000100 8o

    Einmal editiert, zuletzt von Aquaatic ()

  • Ich sehe aber nicht, warum das nicht funktioneren sollte.

    Also mein "unmachbar" war vielleicht nicht ganz richtig, das stimmt. Aber das Alternating Bit Protocol wird ja im ersten Sinne dazu genutzt, bei der Kommunikation zwischen zwei einzelnen Kommunikationspartner Datenverlust zu erkennen, indem Nutzer A mit z.B. Bit-Wert 0 ein Paket schickt und erst das Paket mit Bit-Wert 1 verschickt, sobald Paket 0 von Nutzer B geacked wurde.


    Ich selber weiß auch jetzt noch nicht, wie man mit nur 1 Bit (im Zweifel) endlos viele Clients ohne Master synchronisieren möchte, sodass die ihre Schreiboperationen nicht überschreiben. Wie du sagtest, könnte man es sicher mit n Bits machen, aber das wird auch schwierig, je größer das Cluster wird. Daher auch der Vorschlag von CSMA/CA, worin ich eine bessere Lösung für das Problem sehe.


    Eine Alternative wäre noch, solche Operationen über einen Master im Cluster zu kontrollieren. Dort gibt es auch Ansätze, die nicht mal zwingend einen eigenständigen Master benötigen, da reicht es, wenn ein Client den Master übernimmt und fällt dieser aus, übernimmt ein anderer Client im System den Master. Da könntest du dann die Anfragen zum Schreiben über den Master organisieren, den Clients die Erlaubnis erteilen und die kümmern sich dann um den Broadcast.


    Du könntest dir auch noch Konsens-Algorithmen anschauen. Ein Beispiel dafür wäre der Raft Consensus Algorithm: https://raft.github.io/