Explizite DAG anstelle von Vector Clocks für die Synchronisation

13

Ich habe angefangen, Ansätze für die Datensynchronisation zwischen einer Reihe von Peers zu untersuchen. Die Peers müssen in der Lage sein, getrennt zu arbeiten und dann miteinander zu synchronisieren, um ihre lokalen Änderungen zusammenzuführen.

Peers sollten in der Lage sein, lokale Updates mit einem "Drei-Wege-Merge" zusammenzuführen . Bei der Synchronisation sollten Peers wissen, welche Fakten aktueller sind, aber wo es keine strikte Reihenfolge gibt, sollten sie in der Lage sein, die Fakten basierend auf der gemeinsamen Wurzel zusammenzuführen.

Wenn unabhängige Kollegen Änderungen vornehmen, können sie diese mit einer "Uhr" versehen. Ich benutze die Begriffe "Uhr" und "Zeitstempel", meine aber keine Wanduhr. Ich meine eine Art Teilordnung von Ereignissen, die die Kausalität klar macht. Es ist die Beziehung, die zwischen Ereignissen vorher stattgefunden hat , die einen gerichteten azyklischen Graphen (DAG) bildet.

Es scheint, als ob die "übliche" Art, diese Teilordnung aufzubauen, die Verwendung einer Vektoruhr ist . Diese können jedoch sehr groß werden. Neuere Entwicklungen wie Intervallbaumuhren ermöglichen eine kompaktere Speicherung von Zeitstempeln.

Was mir überhaupt nicht klar ist, warum Synchronisationsprotokolle die DAG anscheinend nicht "einfach" explizit speichern. (Oder doch?)

Peers können unabhängig voneinander einen Zeitstempel erstellen, indem sie eine UUID zufällig generieren (oder auf andere Weise, wie z. B. <peer-name> + <local-monotonically-increasing-counter>). Die Reihenfolge dieses Zeitstempels ist für diesen Peer völlig klar.

Wenn zwei Peers miteinander synchronisiert sind, können sie sich auf einen neuen Zeitstempel einigen. Auch hier ist die Reihenfolge dieses Zeitstempels für beide Peers klar.

Es ist jetzt erforderlich, die vor der DAG erfolgte Weitergabe zwischen Peers durchzuführen, die Speicher- und Bandbreitenanforderungen hierfür sind jedoch gering. Zeitpunkte sind Diagrammscheitelpunkte. Als solche haben sie 1 oder 2 eingehende Kanten (1 für ein Ereignis auf einem Client und 2 für eine Synchronisierung zwischen Clients). Dies ist begrenzt und unabhängig von der Anzahl der Peers im Netzwerk.

Um einen einzelnen Zeitpunkt zu verwenden, benötigen Sie das Diagramm der Zeitpunkte, die dazu führen. Aber soweit ich sehen kann, jeder Peer die in der Lage ist , zu wissen , von einem Zeitpunkt (es hat sich selbst erzeugt, oder durch eine anderen Peer erzeugt, oder hat sie von einem anderen Peer gesagt worden , wenn sie mit ihm zu synchronisieren) hat auch hat eine Gelegenheit, etwas über die Geschichte zu erfahren, die bis zu diesem Zeitpunkt geführt hat. Ich denke, es gibt wahrscheinlich einen induktiven Beweis dafür.

Da das Speichern und Synchronisieren der DAG explizit einfach erscheint: Wird dies in der Praxis verwendet? Wenn nicht, warum werden Vektoruhren bevorzugt?

Anmerkungen

Peer-To-Peer

Ich würde eine Peer-to-Peer-Lösung einer Client-Server-Lösung vorziehen.

Die wahrscheinliche Endtopologie sind viele Clients, die eine Verbindung zu einer viel kleineren Gruppe von Servern herstellen, die sich untereinander replizieren. Es wäre jedoch schön, eine allgemeine Lösung zu haben, die diese spezielle Topologie unterstützt, und keine Lösung, die diese spezielle Topologie erfordert.

synchronization Benjohn
quelle
Ich kann falsch verstehen, was Sie sagen, aber es ist unklar, wie ein Diagramm aller Ereignisse, die zu einem Zustand führen, kleiner sein kann als ein Vektor von Zählern. Es sei denn, Sie befinden sich in einem System mit einer extrem großen Anzahl von Knoten und einer extrem geringen Anzahl von Änderungen.
kdgregory
Danke @kdgregory - guter Punkt. Um in Zukunft eine Drei-Wege-Zusammenführung berechnen zu können, müssen Sie die Vergangenheit kennen (und in der Lage sein, die DAG der vergangenen Zeitpunkte zu bestimmen). Wenn Sie also diese vergangenen Zeitpunkte speichern, ist das explizite Speichern der DAG günstiger. Wenn Sie diese vergangenen Zeitpunkte nicht speichern, können Sie ohnehin keine Drei-Wege-Zusammenführung von Daten berechnen. - Ich frage mich, ob diese Drei-Wege-Anforderung das Richtige sein könnte. Wenn Sie keine 3-Wege-Taktung wünschen, sind Vektortakte vielleicht besser als explizite DAG?
Benjohn
Ich gehe davon aus, dass dies der entscheidende Punkt in @kdgregory sein könnte, deshalb habe ich der Frage ein wenig hinzugefügt. Ich gehe davon aus, dass es möglich ist, eine 3-Wege-Fusion durchzuführen, was auch impliziert, dass die gesamte Geschichte bekannt ist. Wenn die gesamte Geschichte bekannt ist, ist (wie ich finde) eine explizite DAG billiger. Wenn die Historie abgeschnitten ist, sind Vektortakte wahrscheinlich der kostengünstigere Ansatz.
Benjohn
1
Mein Verständnis von Vektoruhren ist, dass sie nur für eine Annahme- / Ablehnungsentscheidung gedacht sind: "Knoten C versucht, diese Daten zu aktualisieren, aber es ist nicht bekannt, dass Knoten B aktualisiert wird".
kdgregory

Antworten:

1

Soweit ich weiß, verwenden Versionskontrollsysteme wie Git und Mercurial den DAG-Ansatz anstelle von Vektoruhren.

bikeman868
quelle
1
Ohne eine Erklärung kann diese Antwort für den Fall unbrauchbar werden, dass jemand anders eine gegenteilige Meinung äußert. Wenn zum Beispiel jemand eine Behauptung aufstellt wie "Propversion Control-Systeme wie Git und Mercurial verwenden Vektoruhren anstelle des DAG-Ansatzes" , wie würde diese Antwort dem Leser helfen, zwei gegensätzliche Meinungen zu ermitteln? Betrachten wir bearbeiten es in eine bessere Form ing, zu treffen wie man Antwort Qualitätsstandards.
gnat
2
So wie ich die Frage verstand, fragten sie, ob es reale Beispiele dafür gibt, wo DAG anstelle von Vektoruhren verwendet wird.
Bikeman868
1
Sowohl Git als auch Mecurial sind echte Beispiele für Peer-to-Peer-Änderungssynchronisation mit DAG, und ich hoffe, dass Benjamin meine Antwort hilfreich finden wird, obwohl Sie sie abgelehnt haben.
bikeman868
Hi @ bikeman868 Ich habe dich für eine Netto-0 gestimmt (sorry). Ihre Antwort ist hilfreich, auch wenn Sie unsicher sind! Referenzen oder verbindliche Antworten sind zwar immer nett, aber Stapelaustausch verlangt das nicht! Ihr Vorschlag ist mit Punkten in Kommentaren zu der Frage sinnvoll. Wenn Sie die Historie speichern und Historien zusammenführen möchten, ist eine DAG geeignet. Wenn Sie keinen Verlauf speichern und eine Synchronisierung und einen Konsens über den aktuellen Status wünschen, sind Vektoruhren genau das, was Sie brauchen.
Benjohn
1

Schauen Sie sich das Konsensproblem an . Abhängig von Ihren Aufgabenanforderungen (wie viele Daten haben Sie, wie viele Synchronisierungsknoten, wie oft usw.) sind möglicherweise vorhandene Lösungen für dieses Problem (wie "Raft") für Ihren Fall geeignet.

Ein anderer (möglicherweise tangentialer) Ansatz für dieses Problem ist das Entwerfen einer CRDT .

battlmonstr
quelle
Braid HTTP versucht, ein CRDT-basiertes Statussynchronisationsprotokoll über die Erweiterung von HTTP zu erstellen. Sie bieten eine hervorragende Visualisierung einer Zeit- und einer Raum-DAG sowie der Wechselbeziehung dieser beiden Konzepte, um zu einer endgültigen Konsistenz zu gelangen.
Duane J