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!)

Collaborative text editor powered by Firebase called Firepad - https://firepad.io/ Check the code to get some inspiration https://github.com/FirebaseExtended/firepad — Tharanga Hewavithana, Oct 30 '19 at 04:52

score 61 · Accepted Answer · edited Mar 30 '13 at 16:09

61

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.)

edited Mar 30 '13 at 16:09

mb21

34,845
8
116
142

answered Jan 11 '10 at 16:58

Jörg W Mittag

363,080
75
446
653

6

Diff-Match-Patch, combined with the Differential Synchronization paper by Neil Frasier (http://neil.fraser.name/writing/sync/) did the trick! Many thanks for pointing me in the right direction. – gamers2000 Jan 14 '10 at 14:11
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. – gamers2000 Apr 23 '11 at 02:59
Any good news on "and more parts are coming" since this answer ? – Bertie Dec 09 '11 at 03:52
3

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: http://neil.fraser.name/writing/sync/ (OT is referenced in this document as Event passing). They are two very different methods. – Benja Feb 06 '12 at 12:59
5

this is old, but in case you mind, I have opensourced https://github.com/benjamine/JsonDiffPatch it uses Neil's Diff-Match-Patch for long strings, but it works for arbritrary js object graphs – Benja Mar 27 '13 at 00:13
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. – hebinda Feb 16 '14 at 02:24
Neil Fraser's site is down. You can find the refernced article also here: http://static.googleusercontent.com/media/research.google.com/en//pubs/archive/35605.pdf And you can find his Google tech talk here: http://www.youtube.com/watch?v=S2Hp_1jqpY8 – gijswijs Jul 16 '14 at 10:55

score 44 · Answer 2 · edited Jun 30 '17 at 21:32

44

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

edited Jun 30 '17 at 21:32

malhal

26,330
7
115
133

answered Oct 18 '11 at 21:57

hawkeye

34,745
30
150
304

1

ShareJS is probably simpler and better documented and more reusable than what MobWrite does with Google's Diff and Patch. – Luke Stanley Aug 21 '12 at 00:35

dmonad · Answer 3 · 2018-07-08T20:09:48.360

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

Google Drive API uses OT not DS. https://developers.google.com/drive/realtime/conflict-resolution — Mathias Bak, Apr 17 '15 at 13:37

score 6 · Answer 4 · edited Oct 13 '13 at 20:03

6

OT Libraries:

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.

edited Oct 13 '13 at 20:03

Beni Cherniavsky-Paskin

9,483
2
50
58

answered Mar 04 '11 at 08:52

Phrearch

211
2
7

score 5 · Answer 5 · answered Sep 11 '13 at 20:50

5

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

answered Sep 11 '13 at 20:50

Jarnal

2,138
2
26
43

alalonde · Answer 6 · 2018-02-26T16:51:35.057

Turnkey, or "drag and drop" solutions to this problem haven't really existed due to the complexity of reliably synchronizing shared mutable state. dmonad's response is a decent roundup, and I posted a more up-to-date overview of the available solutions here.

This question is quite old, but Convergence (disclaimer: I am a founder) provides the most turnkey solution out there, providing not just data synchronization but a host of other APIs useful for building out a collaborative UX. Here is an example showing exactly what you requested: synchronization of a text field across multiple clients.

Otherwise, ShareDB is a great open-source solution that fits a lot of people's needs.

score 4 · Answer 7 · answered Sep 30 '11 at 12:29

4

https://github.com/opencoweb/coweb

answered Sep 30 '11 at 12:29

Peter Parente

1,269
2
12
16

score 2 · Answer 8 · answered Feb 13 '13 at 15:44

Npm has some nice ot libraries for node.js:

https://npmjs.org/package/ot -- adapters for codemirror and ace built in as well as a client and server implementation
https://npmjs.org/package/changesets -- plain ot library usable in node and the browser; allows you to build 'changesets' (essentially diffs) that you can send around, transform against each other and apply on a document

score 2 · Answer 9 · answered Apr 01 '16 at 20:19

I have written a small unixy (do one thing and do it well) library that implements an OT control layer, allowing you to plug in different OT types (supports all shareJS compliant types). It's similar to shareJS but less opinionated and more abstract.

https://github.com/marcelklehr/gulf

score 2 · Answer 10 · answered Aug 11 '11 at 07:22

2

Also check out these Javascript Libraries:

https://github.com/vitotafuni/JSOTTEST < Client-side Javascript Implementation
https://github.com/fitzgen/operational-transformation-example < Node JS Client/Server Implementation

answered Aug 11 '11 at 07:22

Ryan D. Hatch

213
2
3

score 1 · Answer 11 · answered Jul 10 '13 at 10:59

We're building a collaborate editor that combines Operational Transformation with versioning. That way we can support both, offline and online collab. We released our own OT library yesterday as part of our open source stack.

http://interior.substance.io/modules/operator.html

We've also contributed a library for versioning.

http://interior.substance.io/modules/chronicle.html

Daniel Paull · Answer 12 · 2010-07-28T09:12:28.557

1

You could talk to the guys at Cedanet. Though Ceda is closed source and no free trial is available on their web site. I have been involved in the development of Ceda and continue to work with it in commercial projects, so I might be able to provide some feedback/advice if you head down this path.

edited Jul 28 '10 at 09:12

answered Jul 28 '10 at 07:51

Daniel Paull

6,797
3
32
41

score 1 · Answer 13 · answered Oct 06 '11 at 08:58

1

With a js client lib (Strophe.js) you could use a free XMPP server (like jabber.org) along with my client-side OT lib (JSOTTEST) to build a complete client-server system.

I will submit the src of a demo client-server chat system when I have time to revise the code.

answered Oct 06 '11 at 08:58

user981836

29
1

1

Almost two years ago you write "I will submit the src of a demo...". Did you ever finish that demo? – Bryan Oakley Sep 08 '13 at 13:50
Sorry... but I had no time to release a public demo! However it's very simple using Bosh lib for php!! bye – user981836 May 05 '14 at 22:31

score 0 · Answer 14 · answered Sep 23 '11 at 10:49

0

I thing etherpad.org with etherpad lite is superior to other solutions.

answered Sep 23 '11 at 10:49

gorn

5,042
7
31
46

2

Would you be able to substantiate etherpad's superiority with some example? – DL Narasimhan Apr 13 '15 at 11:27

Operational Transformation library?

14 Answers14

Linked