Ich erarbeite ein Problem, das mir schwer vorkommt, und ich erwarte keine einfache Lösung, aber vielleicht gibt es bewährte Praktiken oder weitere Lektüren, die dies erleichtern könnten. Ich bin mir ziemlich sicher, dass das allgemeine Problem in vielen Anwendungen auftaucht (zum Beispiel Speicherbereinigung oder Transaktionsdatenbanken).
Meine Anwendung hat ein Diagramm (ein DAG, wenn es darauf ankommt), das von mehreren Threads gleichzeitig durchlaufen wird. Einige versuchen nur, bestimmte Knoten zu finden oder einen Teilgraphen abzurufen, andere können die Struktur des Graphen ändern.
Die Richtlinie, die ich implementieren möchte, ist, dass ein Lese-Thread seine gesamte Operation auf einem "Snapshot" des Graphen durchführt, d. e. Sehen Sie die Struktur so, wie sie zu einem bestimmten Zeitpunkt war.
Mein aktueller Plan ist, etwas Ähnliches wie die Zeilenversionierung in transaktionalen DBs einzurichten, d. e. Ein Lese-Thread erhält zuerst eine aktuelle Versionsnummer und besucht dann nur Grafikknoten und Kanten, die diese Versionsnummer oder früher haben. Das Schreiben von Threads würde dann eine inkrementierte Versionsnummer auf neue Elemente schreiben (geänderte Elemente würden zuerst geklont), wodurch sie für das Ausführen von Lesern unsichtbar gemacht würden. Ein schreibender Thread kann dann seine neue Version "committen", wenn sie erfolgreich beendet wurde, und die Leser würden ihre Versionsnummer "freigeben", wodurch gelöschte Elemente für die Entfernung in Frage kommen.
Diese Strategie ist immer noch skizzenhaft und hat eine Reihe ungelöster Probleme wie den gleichzeitigen Schreibzugriff, aber im Allgemeinen scheint es ein brauchbarer Weg zu sein.
Eine Alternative wäre Persistente Datenstrukturen . Sie sind eine Datenstruktur, die immer die vorherige Version von sich selbst beibehält, wenn sie geändert wird .
Sie sind wie eine Protokolldatei, die geänderte Version ist immer zuletzt angelegt und daher unveränderlich, da ihre Operationen die Struktur nicht (sichtbar) aktualisieren, sondern immer eine neue aktualisierte Struktur ergeben. Programmiersprachen wie Clojure hat kürzlich diesen Ansatz (zumindest für mich ).
Ihre Vorgehensweise scheint mir gut zu klingen ...
Sie könnten jedoch Probleme damit haben, Kausalität zwischen Schreibvorgängen auf separaten Untergraphen sicherzustellen.
Wenn ein Schreiber den Untergraphen A ändert und ein anderer Schreiber den Untergraphen B ändert, aber andere Lese- / Schreiboperationen im Untergraphen C stattfinden, wo A und B in C sind, müssen Sie sicherstellen, dass die Version von Untergraphen C korrekt mit den Versionen ausgerichtet ist von B und A.
Ich würde ein Sperrschema in der DAG vorschlagen, das eine Teilgraphensperrung für mehrfaches Lesen / einzelnes Schreiben von einer gegebenen Wurzel enthält. Sie müssen das Diagramm jedoch nach zyklischen Abhängigkeiten durchsuchen, um sicherzustellen, dass Sie innerhalb des Diagramms nicht in einen Verhinderungs- / Deadlock-Zustand geraten.
Wenn Ihr Diagramm verteilt ist oder Ihr gleichzeitiger Zugriff Latenz hat, ist Ihr Transaktionssystem schwerer zu implementieren und erfordert wahrscheinlich zusätzliche Sicherheitsvorkehrungen.
Ihr Versionierungsansatz klingt gut, vorausgesetzt, Ihre Sperrbestimmungen stellen in allen Fällen sicher, dass eine Reihe von Revisionen für Knoten zu einem beliebigen Zeitpunkt T einen Integral-Status des Graphen darstellt. Die Menge der Knoten und Revisionen bei T = {n0, n1, n2, n3} und ein gleichzeitiges Revisions-Bumping von Untergraphen wird die Kopfschmerzen bereiten, den gesamten Satz von Revisionen und Knoten bei T ganzzahlig zu halten.
Wie dfa suggeriert oben stellt die Menge der Knoten und Revisionen an einem bestimmten Punkt eine Änderungsmenge der gesamten Struktur dar. Wenn es Integrität hat, repräsentiert dies die gesamte Struktur zu einem bestimmten Zeitpunkt.
Denken Sie daran: Zeit, Integrität, Kausalität und Nebenläufigkeit
Viel Glück!
Nun, ich dachte, ich wäre clever und google mehrere Keywords, um etwas Literatur zu finden. Das erste Ergebnis ... war diese Frage.
Es gibt also nicht viel zu diesem Thema! Interessant. Ich dachte nur, ich würde teilen.
Aiden Bell und DFA haben beide sehr gründliche Antworten gegeben, also werde ich nicht versuchen, sie zu übertreffen. :) Aber ich werde eine Beobachtung machen, bezüglich der DAG-Qualität des Graphen und des gleichzeitigen Schreibzugriffs. Das mag dir schon eingefallen sein, aber hey. :)
Sie können gleichzeitige Threads zulassen, ohne sich darum kümmern zu müssen, dass andere die Änderungen überschreiben, indem Sie einfach davon ausgehen, dass der von einem schreibenden Thread bewohnte -Knoten und alle untergeordneten Elemente dieses Knotens jederzeit "gesperrt" sind. von diesem bestimmten Schreib-Thread . Ich finde es am einfachsten, dies mit einem Baum zu visualisieren (was offensichtlich auch eine DAG ist). Jeder schreibende Thread hat grundsätzlich einen bestimmten Unterbaum gesperrt, aber wir können jetzt auch sagen, dass alle Geschwisterbäume oder irgendwelche Vorfahrenknoten glücklich beschreibbar sind.
Ein komplexeres DAG (wo ein Knoten insbesondere mehrere Eltern haben kann) wird in Wirklichkeit viele überlappende Unterbäume haben, und daher gibt es vielleicht nicht so viel Freiheit, aber die Regel gilt immer noch: alle Der Knoten, der nicht von oder der untergeordnete Knoten eines von einem Schreib-Thread bewohnten Knotens belegt ist, kann als schreibaktiviert betrachtet werden.
Offensichtlich kann es eine Menge Faktoren geben, warum die obige Idee nicht hilfreich ist, aber wenn mehrere Schreib-Threads oft in "verschiedene" Richtungen abgehen, kann es einige der Anforderungen erleichtern, die notwendig sind, um es Thread-sicher zu machen / p>
Hoffe, das hilft!
-Agor
Tags und Links computer-science concurrency graph