Root, Kinder und mehrere Schlösser

Question

Vereinfachte Struktur von dem, was ich habe, ist:

• einige einzelne Wurzeln
• jede Wurzel hat viele (zB 100s) von Kindern

Nutzer kann die Wurzel aktualisieren Informationen, und keine andere Operation an Kindern sollte erlaubt sein (weil Root-Änderung alle betreffen kann).

Benutzer können auch mit Kindern arbeiten (wenn root nicht verwendet wird). Zum Beispiel kann der Benutzer 2 Kinder gleichzeitig ändern, und dies ist erlaubt, da jedes Kind unabhängig ist.

Ich brauche Schlösser in dieser Struktur, um sicher zu sein, gibt es keine Verfälschungen:

• , wenn Kinder in Gebrauch ist, sperren die Kinder. Dies ermöglicht nicht zwei Operationen für dieselben Kinder gleichzeitig.
• Wenn Root verwendet wird, sperren Sie Stamm und alle die Kinder. Dies verbietet die Operationen auf irgendwelchen Kindern, während root aktualisiert wird.

Was mich hier stört, ist die Notwendigkeit alle die Kinder zu sperren - in einem verteilten System, das auf verteilte Sperre, dass viele Anfragen Mittel sendet.

Gibt es eine bessere Lösung, die ich nicht sehe?

Answer 1

Sie vermissen zwei Dinge. Erstens ist es für mehrere Threads sicher, gleichzeitig von einem Knoten zu lesen, solange niemand darauf schreibt. Zweitens können die Kindknoten als ihre eigenen Wurzeln von kleineren Bäumen betrachtet werden, so dass derselbe Algorithmus/Lösung auf alle Knoten außer Blattknoten angewendet werden kann. Der erste ist am wichtigsten. So können Sie das tun:

Verwenden Sie einen Lese-/Schreib-Mutex für alle Knoten in der Struktur. Dadurch können beliebig viele Prozesse gleichzeitig gelesen werden oder ein einzelner Prozess kann jederzeit auf einen Knoten schreiben.

zu lesen:

1. Lese-Lock-Knoten und alle Eltern den ganzen Weg bis zu root.
2. lesen.
3. geben Sie alle Lesesperren frei.

schreiben:

1. Schreib sperren die am wenigsten obere Grenze der Knoten, die Sie ändern möchten. Wenn Sie einen Knoten (und möglicherweise einen seiner untergeordneten Knoten) ändern, sperren Sie diesen Knoten.
2. tun, um Ihre Änderungen
3. Freigabe der Schreibsperre

Das bedeutet, zwei Geschwister gleichzeitig modifiziert werden können, und dass eine beliebige Anzahl von liest können gleichzeitig ausgeführt werden.Die Kosten für das Lesen sind jedoch, dass Sie O (log100 (tree_height)) Lese-Locks für einen Baum mit etwa 100 Kindern auf jeder Ebene greifen müssen. Es ist unwahrscheinlich, dass es ein echtes Problem ist, es sei denn, Ihr Baum ist riesig, mit extrem vielen Lese- und Schreibvorgängen auf demselben Blattknoten.

Dies setzt voraus, dass kein Kind seine Eltern ändern kann.