Just use OT like normal people, it’s been proven to work. No tombstones, no infinite storage requirements or forced “compaction”, fairly easy to debug, algorithm is moderate to complex but there are reference open source implementations to cross check against. You need a server for OT but you’re always going to have a server anyway, one extra websocket won’t hurt you. We regularly have 30-50k websockets connected at a time. CRDTs are a meme and are not for serious applications.
Author here, I did not specifically mention OT in the article, since our main focus was to help people understand the downsides of the currently-most-popular system, which is built on CRDTs.
BUT, since you mention it, I'll say a bit here. It sounds like you have your own experience, and we'd love to hear about that. But OUR experience was: (1) we found (contrary to popular belief) that OT actually does not require a centralized server, (2) we found it to be harder to implement OT exactly right vs CRDTs, and (3) we found many (though not all) of the problems that CRDTs have, are also problems in practice for OT—although in fairness to OT, we think the problems CRDTs have in general are vastly worse to the end-user experience.
If there's interest I'm happy to write a similar article entirely dedicated to OT. But, for (3), as intuition, we found a lot of the problems that both CRDTs and OT have seem to arise from a fundamental impedance mismatch between the in-memory representation of the state of a modern editor, and the representation that is actually synchronized. That is, when you apply an op (CRDT) or a transform (OT), you have to transform the change into a (to use ProseMirror as an example) valid `Transaction` on an `EditorState`. This is not always easy in either case, and to do it right you might have to think very hard about things like "how to preserve position mappings," and other parts of editor state that are crucial to (say) plugins that manage locations of comment marks or presence cursors.
With all of that said, OT is definitely much closer to what modern editors need, in my opinion at least. The less-well-known algorithm we ended up recommending here (which I will call "Marjin Collab", after its author) is essentially a very lightweight OT, without the "transformation" step.
I always mentally slotted prosemirror-collab/your recommended solution in the OT category. What’s the difference between the “rebase” step and the “transformation” step you’re saying it doesn’t need?
Great question. Matt has a comment about this here, and he has an actual PhD on the subject! So rather than doing a worse job explaining I will leave it to him to explain: https://news.ycombinator.com/user?id=mweidner
Having a central server is not necessary, but we have one anyway and we use it, especially if you have a permissions system. It lets us use the "Google wave" algorithm which vastly simplifies things.
https://svn.apache.org/repos/asf/incubator/wave/whitepapers/...
> This is not always easy in either case, and to do it right you might have to think very hard about things like "how to preserve position mappings," and other parts of editor state that are crucial to (say) plugins that manage locations of comment marks or presence cursors.
Maintaining text editor state is normal. Yes you do need to convert the OT messages into whatever diff format your editor requires (and back), but that's the standard glue code.
The nice thing about OT is that you can just feed the positions of marks into the OT algorithm to get the new positional value. Worst case, you just have the server send the server side position when sending the OT event and the client just displays the server side position.
Josh eloquently explains how Google Wave's DACP (Distributed Application Canceling Protocol) works:
https://www.youtube.com/watch?v=4Z4RKRLaSug
One way to minimize impedance mismatch is to work with DOM-like or JSON-like structures mostly immune to transient bugs, which I am doing currently in the librdx project. It has full-CRDT RDX format[1] and essentially-JSON BASON[2] format. It does not solve all the problems, more like the set of problems is different. On the good side, it is really difficult to break. On the bad side, it lacks some of the rigor (esp BASON) that mature CRDT models have. But, those models are way more complex and, most likely, will have mismatching bugs in different implementations. No free lunch.
[1]: https://github.com/gritzko/librdx/tree/master/rdx [2]: https://github.com/gritzko/librdx/tree/master/json
Are there any major libraries for OT? I've been looking into this recently for a project at work, and OT would be completely sufficient for our use case, and does look simpler overall, but from what I could tell, we'd need to write a lot of stuff ourselves. The only vaguely active-looking project in JS at least seems to be DocNode (https://www.docukit.dev/docnode), and that looks very cool but also very early days.
Author here. I think it depends what you're doing! OT is a true distributed systems algorithm and to my knowledge there are no projects that implement true, distributed OT with strong support for modern rich text editor SDKs like ProseMirror. ShareJS, for example, is abandoned, and predates most modern editors.
If you are using a centralized server and ProseMirror, there are several OT and pseudo-OT implementations. Most popularly, there is prosemirror-collab[4], which is basically "OT without the stuff you don't need with an authoritative source for documents." Practically speaking that means "OT without T", but because it does not transform the ops to be order-independent, it has an extra step on conflict where the user has to rebase changes and re-submit. This is can cause minor edit starvation of less-connected clients. prosemirror-collab-commit[5] fixes this by performing the rebasing on the server... so it's still "OT without the T", but also with an authoritative conflict resolution pseudo-T at the end. I personally recommend prosemirror-collab-commit, it's what we use, and it's extremely fast and predictable.
If you just want something pedogocically helpful, the blessed upstream collaborative editing solution for CodeMirror is OT. See author's blog post[1], the @codemirror/collab package[2], and the live demo[3]. In general this implementation is quite good and worth reading if you are interested in this kind of thing. ShareJS and OTTypes are both very readable and very good, although we found them very challenging to adopt in a real-world ProseMirror-based editor.
[1]: https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...
[2]: https://codemirror.net/docs/ref/#collab
[3]: https://codemirror.net/examples/collab/
[4]: https://github.com/ProseMirror/prosemirror-collab
[5]: https://github.com/stepwisehq/prosemirror-collab-commit
In our case, we're not using a text editor, but instead building a spreadsheet, so a lot of these collab-built-into-an-editor are, like you say, pedagogically useful but less helpful as direct building blocks that we can just pull in and use. But the advice is very useful, thank you!
Cheers for plugging prosemirror-collab-commit! Nice to see it's getting used more.
When I was starting my research into collaborative editing as a PhD student 20+ years ago, rebase-and-resubmit was well known. It was used in one Microsoft team collab product (I forgot the name). It is 100% legit algo except intermittently-connected clients may face challenges (screw them then).
Unless you have to support some complicated scenarios, it will work. I believe Google Docs initially used something of the sort (diff-match-patch based). It annoyed users with alerts "lets rebase your changes", esp on bad WiFi. So they borrowed proper OT from Google Wave and lived happily since (not really).
One way to think about it: how many users will your product have and how strange your data races / corner cases can get. At Google's scale, 0.1% users complaining is a huge shit storm. For others, that is one crazy guy in the channel, no biggie. It all depends.
TLDR: people invented OT/CRDT for a reason.
First of all, thanks for chiming in! I wish someone would collect stuff like this and write it down in some sort of "oral history of collab editing."
Second of all, I actually think we're more aligned than it seems here. What we're really advocating for is being super clear about what your end-user goals are, and deriving technology decisions from them, instead of the reverse. Our goals for this technology are (1) users should be able to predict what happens to their data, (2) the editor always run at 60fps, and (3) we are reasonably tolerant of transient periods of disconnection (up to, say, 30s-1m).
Because of (1) in particular, a lot of our evaluation was focused on understanding which situations users would be unable to predict what was going to happen to their data. This is only our own experience, but what we found (and the impetus for part 1 of this series) is that almost 100% of the time, when there is a direct editing conflict, users interpret the results of the dominant CRDT and OT implementations as silently corrupting their data. So, the name of the game is to decrease the likelihood of direct editing conflicts, e.g. presence carets in the live-collab case. In particular, we did not notice a meaningful difference between how users view reconciliations of OT and CRDT implementations.
Since our users could not tell the difference, and in fact viewed all options as equally bad ("disastrous" as one user said), this freed us up to consider a much broader class of algorithms, including prosemirror-collab and prosemirror-collab-commit.
I know there is a rich history of why OT is OT, but our final determination was made pretty simple by the fact that the source of the majority of race conditions in our view come from the difficulty of integrating CRDTs and OT directly into modern editing stacks, like ProseMirror. As far as I am aware, prosemirror-collab-commit behaves as good or better on every dimension than, say, an OTTypes implementation would... and mostly that is because it is native to the expressive `Transaction` model of the modern editor. If we had to do interop I think we would have shipped something noticably worse, and much slower.
If you have a different experience I would love to hear about it, as we are perennially in the market for new ideas here.
https://github.com/josephg/sharejs
https://github.com/FirebaseExtended/firepad
https://github.com/Operational-Transformation/ot.js
https://github.com/ottypes/docs
Really nice demo: https://operational-transformation.github.io
Author of DocNode here. Yes, it’s still early days. But it’s a very robust library that I don’t expect will go through many breaking changes. It has been developed privately for over 2 years and has 100% test coverage. Additionally, each test uses a wrapper to validate things like operation reversibility, consistency across different replicas, etc.
DocSync, which is the sync engine mainly designed with DocNode in mind, I would say is a bit less mature.
I’d love it if you could take a look and see if there’s anything that doesn’t convince you. I’ll be happy to answer any questions.
I've looked through the site, and right now it's probably the thing I'd try out first, but my main concerns are the missing documentation, particular the more cookbook-y kinds of documentation — how you might achieve such-and-such effect, etc. For example, the sync example is very terse, although I can understand why you'd like to encourage people to use the more robust, paid-for solution! Also just general advice on how to use DocNode effectively from your experience would be useful, things like schema design or notes about how each operation works and when to prefer one kind of operation or structure over another.
All that said, I feel like the documentation has improved since the last time I looked, and I suspect a lot of the finer details come with community and experience.
Thanks! I've recently made some improvements to the documentation. I agree the synchronization section could be improved more. I'll keep your feedback in mind. If you'd like to try the library, feel free to ask me anything on Discord and I'll help you.
What does OT stand for so I can learn more?
Operational Transformation
Agreed. In my limited experience, conflict resolution rules are very domain specific, whereas CTDTs encourage a lazy attitude that "if it's associative and commutative it must be correct".
"CRDTs are a meme and are not for serious applications."
That is one hot take!
Let's balance the discussion a bit.
https://josephg.com/blog/crdts-are-the-future/
What is OT?
Operational Transformation: https://en.wikipedia.org/wiki/Operational_transformation