Operational Transformation library?

Question

I'm looking for a library that would allow me to synchronize text in real-time between multiple users (ala Google Docs).

I've stumbled upon Operational Transformation, which seems to fit my needs. Having said that, I understand the gist of OT, but not the math nor implementation of OT.

Thus, I was wondering if there was a drag'n'drop Javascript library that would hook into a text area, generate the transforms, then allow me to apply those transformations onto another client?

(I've gotten the Etherpad source, but I can't make head or tails out of it. If anyone could point out how to leverage on Etherpad's OT implementation, that'll be great too!)

Solution 1

I think that parts of Google Wave's OT implementation are Open Source (and more parts are coming).

I'm not sure if this is what you are looking for, but an alternative to OT is Differential Synchronization:

• Google-Diff-Match-Patch - Diff, Match and Patch libraries for Plain Text: "The Diff Match and Patch libraries offer robust algorithms to perform the operations required for synchronizing plain text."
• Google-MobWrite - Real-time Synchronization and Collaboration Service: "MobWrite converts forms and web applications into collaborative environments. Create a simple single-user system, add one line of JavaScript, and instantly get a collaborative system." (Uses Google-Diff-Match-Patch.)

Solution 2

One of the ex-Wave engineers has released a Coffeescript implementation of its collaborative editing algorithm called ShareJS, now named ShareDB.

Solution 3

I'll summarize the solutions I found.

• Operational Transformation: E.g.

  • Google Wave OT. The approach is based on the so called Jupiter approach.
  • ShareJs. Based on the same OT algorithm as Google Wave OT.
  • Coweb-jsoe. Based on COT - a very sophisticated OT approach that also supports p2p message propagation.
  • OpenCoweb. It leverages OpenCoweb-jsoe in order to provide a full-fledged Framework for a lot of similar problems.
  • OT.js is based on the operation-types of ShareJs.
  • DriveSDK. A very interesting API that can do a lot of things - e.g. collaboration on graphs.
  • SwellRT is a Fork of Apache Wave. Is is federated, and supports rich text.

• Differential Synchronization:

  • Diff-Match-Patch from Neil Fraser.
  • MobWrite leverages the Diff-Match-Patch algorithm.

• CRDT (Commutative Replicated Data Type):

  • There are a lot of different CRDT algorithms that allow the implementation of shared types. Some CRDTs work with P2P message propagation, some rely on client-server models
  • Yjs allows you to share arbitrary data types (RichText, Array, Hash Maps, .. extendable). Offline support and support for P2P communication protocols (there are modules for XMPP, Websockets, and WebRTC)
  • SwarmJS Client server shared database with offline support. Works well with React
  • Woot An implementation of the Woot CRDT
  • CRDT Another CRDT implementation
  • Automerge

Solution 4

OT Libraries:

• https://github.com/sveith/jinfinote
• https://github.com/jvanveen/py-infinote

Within the HWIOS websocket project, i've succesfully used a combo of both(py-infinote at the serverside, jinfinote at clientside) to sync document states.

Solution 5

The ot.js library https://github.com/Operational-Transformation/ot.js may be useful for multi-user scenarios.

View more solutions

Comments

[Tharanga Hewavithana]

Collaborative text editor powered by Firebase called Firepad - firepad.io Check the code to get some inspiration github.com/FirebaseExtended/firepad

[gamers2000]

Diff-Match-Patch, combined with the Differential Synchronization paper by Neil Frasier (neil.fraser.name/writing/sync) did the trick! Many thanks for pointing me in the right direction.

[gamers2000]

From what I understand, Diff-Match-Patch, and by extension, MobWrite (since the latter uses the former) only supports text, not binary changes. However, there is a demo of collaboration with HTML form elements, which would indicate it doesn't only support plain text.

[Albert Gan]

Any good news on "and more parts are coming" since this answer ?

[Benja]

Actually, Google-Diff-Match-Patch is aimed to implement the alternative method to Operational Transformations, which is Differential Synchronization, to understand the differences you can read the Neil Fraser document of DS: neil.fraser.name/writing/sync (OT is referenced in this document as Event passing). They are two very different methods.

[Luke Stanley]

ShareJS is probably simpler and better documented and more reusable than what MobWrite does with Google's Diff and Patch.

[Benja]

this is old, but in case you mind, I have opensourced github.com/benjamine/JsonDiffPatch it uses Neil's Diff-Match-Patch for long strings, but it works for arbritrary js object graphs

[Russell Smith]

Almost two years ago you write "I will submit the src of a demo...". Did you ever finish that demo?

[hebinda]

Operational transformation intends to solve synchronization problem by only sending the change operations instead of the entire text to avoid huge network traffic. However DiffMatchPatch requires entire text of different versions to compute the difference. They are not achieving the same thing.

[user981836]

Sorry... but I had no time to release a public demo! However it's very simple using Bosh lib for php!! bye

[gijswijs]

Neil Fraser's site is down. You can find the refernced article also here: static.googleusercontent.com/media/research.google.com/en//p‌​ubs/… And you can find his Google tech talk here: youtube.com/watch?v=S2Hp_1jqpY8

[DL Narasimhan]

Would you be able to substantiate etherpad's superiority with some example?

[Mathias Bak]

Google Drive API uses OT not DS. developers.google.com/drive/realtime/conflict-resolution