Ich habe mit meinem eigenen Javascript-Editor herumgespielt, dessen Funktionen denen von Google Docs ähneln (so dass mehrere Personen gleichzeitig daran arbeiten können). Eine Sache, die ich nicht verstehe:
Nehmen wir an, Sie haben Benutzer A und Benutzer B direkt miteinander verbunden mit einer Netzwerkverzögerung von 10 ms. Ich gehe davon aus, dass der Editor ein Diff-System verwendet (wie ich es bei Docs verstehe), wo Bearbeitungen wie "Text einfügen" bei Index 3 dargestellt werden, und dass Diffs mit Zeitmarken versehen und von allen Clients chronologisch angewendet werden müssen.
Beginnen wir mit einem Dokument, das den folgenden Text enthält: "xyz123"
Benutzer A gibt "abc" am Anfang des Dokuments bei Zeitstempel 001ms ein, während Benutzer B "hallo" zwischen "xyz" und "123" bei Zeitstempel 005ms eingibt.
Beide Benutzer würden erwarten, dass das Ergebnis lautet: "abcxyzhello123", jedoch unter Berücksichtigung der Netzwerkverzögerung:
Natürlich ist " abchello xyz123" nicht dasselbe wie " abc xyz hallo 123"
Abgesehen davon, dass ich buchstäblich jedem einzelnen Charakter seine eigene eindeutige ID gebe, kann ich mir nicht vorstellen, wie Google dieses Problem effektiv lösen könnte.
Einige Möglichkeiten, an die ich gedacht habe:
Ich lese Ссылка , würde aber gerne alle möglichen Ansätze zur Behebung dieses Problems hören.
Es gibt verschiedene Möglichkeiten, die gleichzeitige Änderung von Replikaten zu realisieren, abhängig von der Topologie des Szenarios und mit unterschiedlichen Kompromissen.
Das häufigste Szenario ist ein zentraler Server, mit dem alle Clients kommunizieren müssen.
Der Server kann verfolgen, wie das Dokument jedes Teilnehmers aussieht. Sowohl A als auch B senden dann ein Diff mit ihren Änderungen an den Server. Der Server würde dann die Änderungen auf die entsprechenden Tracking-Dokumente anwenden. Dann würde es eine Drei-Wege-Zusammenführung durchführen und die Änderungen auf das Hauptdokument anwenden. Es würde dann das Diff zwischen dem Master-Dokument und den Tracking-Dokumenten an die jeweiligen Clients senden. Dies nennt man differentielle Synchronisation .
Ein anderer Ansatz wird als Operation (al) transformation bezeichnet, die ähnlich zu einer Rebasing in traditionellen Versionskontrollsystemen ist. Es benötigt keinen zentralen Server, aber wenn Sie einen haben, wird es viel einfacher, wenn Sie mehr als 2 Teilnehmer haben (siehe OT FAQ ). Das Wichtigste ist, dass Sie die Änderungen in einer Bearbeitung so umwandeln, dass die Bearbeitung davon ausgeht, dass die Änderungen einer anderen Bearbeitung bereits stattgefunden haben. Z.B. A würde B's Bearbeitung insert(3, hello) gegen seine Bearbeitung insert(0, abc) mit dem Ergebnis insert(6, hello) transformieren.
Der Unterschied zwischen Rebasing und OT besteht darin, dass Rebasing keine Konsistenz garantiert, wenn Sie Bearbeitungen in verschiedenen Ordnungen anwenden (z. B. wenn B die Editierung von A umgekehrt durchführen würde, kann dies zu divergierenden Dokumentenzuständen führen). Die Verheißung von OT auf der anderen Seite ist es, jede Reihenfolge zu erlauben, wenn Sie die richtigen Transformationen durchführen.
Es gibt OT-Algorithmen, die mit Peer-to-Peer-Szenarien umgehen können (mit dem Ziel, die Komplexität der Implementierung auf der Kontrollschicht zu erhöhen und die Speicherauslastung zu erhöhen). Anstelle eines einfachen Zeitstempels kann ein Version Vektor verwendet werden, um den Status einer Bearbeitung zu verfolgen. Dann können eingehende Bearbeitungen (abhängig von der Fähigkeit Ihres OT-Algorithmus, insbesondere Transformationseigenschaft 2 ) so transformiert werden, dass sie in der Reihenfolge, in der sie empfangen werden, passen, oder der Versionsvektor kann zum Auferlegen einer Teilaufgabe verwendet werden bei den Bearbeitungen - in diesem Fall muss der Verlauf "neu geschrieben" werden, indem Bearbeitungen rückgängig gemacht und transformiert werden, so dass sie der von den Versionsvektoren auferlegten Reihenfolge entsprechen.
Schließlich gibt es eine Gruppe von Algorithmen namens CRDT, WOOT, Treedoc und Logoot, die versuchen, das Problem mit speziell entworfenen Datentypen zu lösen, die es Operationen erlauben, zu pendeln, so dass die Reihenfolge, in der sie angewendet werden, keine Rolle spielt ( Das ist ähnlich wie bei Ihrer Idee einer ID für jedes Zeichen. Die Kompromisse hier sind Speicherverbrauch und Overhead in Betrieb Konstruktion.
Tags und Links editing google-docs operational-transform collaborative-editing