Item — HN Reader

Author of the posted article here. For the last year or so, I've been doing a deep dive into operational transformation, trying to figure out why it's so hard, and whether CRDT is a better approach to collaborative text editing.

The result of this work is a hybrid technique which I think combines the best features of Operational Transformation (especially the RAM-efficiency) and CRDT (ability to work in arbitrary network topologies, not requiring a central server). It also turned out to be appealingly simple, about 400 lines of JavaScript. That's with a core data structure implemented as a balanced binary tree, to make the merge algorithm O(n log n), as opposed to O(n^2) for the best operational transform algorithm I know about (n is a measure of the number of edits in flight concurrently).

For anyone spinning up a new collaborative editor, I believe these techniques are a significant advance. Of course, if people disagree, I'd be more than happy to discuss.

4 comments

This is really cool! Have you discussed this work with Joseph Gentle, author of ShareJS/ShareDB? (He's the one who first exposed me to the concepts and seems like a sharp guy.)

No, but I did have a conversation with Nate Smith, also involved with that project. That was before I was able to release this code, though.

Yep. We had a great chat! Should catch up again.

I agree with Raph that OT and CRDT are closer in concept than many people currently think. Each have some interesting advantages. If we find a good way to combine them, perhaps it would be possible to engineer a system that has a different combination of advantages than today's OT or CRDTs provide.

If anyone is interested in a role working on OT, I'd love to hear from you! https://jobs.lever.co/lever/517c90b8-3519-48ee-b848-33282796...

Aw I'm HN-famous! I'm sorry I didn't see this post sooner. I'd love to catch up for virtual coffee if you're interested - check your email.

I'm not sure if your tree structure is needed to efficiently transform N operations together. Another approach is to simply compose the operations together and transform by the composed operation set, using the property that with a proper tombstone-using text ot type it holds that IT(IT(x, A), B) == IT(x, A.B). (where IT=transform, `.`=compose). Mind you, this approach is still a bit slower than your solution. (I think you can make it O(N*(log N)^3) or something like that. But still faster than O(N^2).)

I don't think this is technically a CRDT - I think its still technically just OT, but OT that holds some additional properties. My favourite differentiating characteristic is that CRDTs bundle information from the document's history with the document snapshot itself. This lets you apply an operation with an older operational context. Obviously applying an old operation would be trivial with an OT system too if you had the history and could transform the operation - its just inefficient. So in a sense, {tp2-ot+document history} is a CRDT. Just, an inefficient one. As far as I can tell what you're proposing doesn't bundle the history - and you still need that history to transform.

It has some other really nice properties though, to the point that I had a pass implementing a p2p system using something like this a few years ago, using IT and ET functions. (My researcher friend Torben Weis independently discovered that method back in 2011 but didn't publish it). But the downside is that its slow. Your tree-based approach for operations themselves might be enough to make it viable. Very cool stuff!

Great stuff! Would you mind elaborating on how does OT differ from operation-based CRDT? They seem very similar, one described as functions , the other as a data type with operations.

OT is a broad category that includes both commutative and non-commutative operations (in the OT literature, this is usually called the TP2 property). Most practical implementations are non-commutative, because people have only figured out how to do commutativity fairly recently. OT with commutative operations overlaps a lot with operation-based CRDT.

http://haslab.uminho.pt/ashoker/files/opbaseddais14.pdf is a good paper on this, and their idea of partially ordered logs provides theoretical support for my earlier essay about unifying operational transformation and CRDT - I'll definitely cite it in any future publications.

So the main diff would be that CRDTs must be commutative and OTs don't have to be? Are there any other differences?

What about state-based CRDTs, how do they fit the big picture?

That's the main substantive difference. I think there are differences in flavor considering that these came from rather different literatures. I have a feeling they'll converge.

State-based CRDT involves sending the entire document model, rather than just deltas from the last state. That's fine if documents are small or deltas are big chunks, but these tend not to be good assumptions in text editing. On the flip side, they're easier to reason about because connections don't have to be stateful.

There was a paper recently about delta state CRDTs with the relevant code. C++ code for reference https://github.com/CBaquero/delta-enabled-crdts

This is awesome! I think I missed it but is there a link to the JavaScript in the article?

Yes, it's here: https://github.com/google/ot-crdt-papers

(You should point out that you're the author of the article! :)

Good point, done. Otherwise, it would look like a pretty ham-handed attempt at sock-puppetry :)

'Show HN' implies that.