Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Real Differences Between OT and CRDT for Co-Editors

arxiv.org

Post reply on HN
Print view View original

11–20 of 66 posts

Re: Real Differences Between OT and CRDT for Co-Editors

#11

Post by m12k »

shunza wrote: post #5
marknadal wrote: post #2

Sorry, what? OT requires centralized servers to do intention resolution. CRDTs are a set of operations that can work on any peer and resolve correctly, without extra coordination or central resolution. The two things are about opposite as they can get. Some CRDTs can be used to make Google Docs style OT, but are not specific to OT use cases. Source: Me, I'm the leading industry and open source expert on CRDTs which p…

Why OT cannot be applied on P2P networks? Does Google Docs use a transformation-based server mean that all OT need a central server?

Yeah, I thought the whole point of OT was that it allowed any client to do resolution (because all operations transform other operations in a way to make them all resolve the same way no matter their order) Which is what made it seem like such overkill for Google Docs where there is a central authoritative server, so a much simpler architecture could have done the job...

Re: Real Differences Between OT and CRDT for Co-Editors

#12

Post by zzzcpan »

gritzko wrote: post #10

An article of disappointing quality from well known OT authors. Like,algo x has issue X, algo y has issue Y, z has Z, so CRDT has issues X, Y and Z... and many things like that.

I agree. I don't understand why they are attacking CRDTs at all.

Re: Real Differences Between OT and CRDT for Co-Editors

#13

Post by shunza »

zzzcpan wrote: post #12
gritzko wrote: post #10

An article of disappointing quality from well known OT authors. Like,algo x has issue X, algo y has issue Y, z has Z, so CRDT has issues X, Y and Z... and many things like that.

I agree. I don't understand why they are attacking CRDTs at all.

Be specific. Which statements are attacking CRDTs?

Re: Real Differences Between OT and CRDT for Co-Editors

#14

Post by amsha »

Here's the key sentence: "concrete implementations of CRDT in co-editors revealed key missing steps in CRDT literature." This paper may be correct for academic CRDTs but it is very wrong when looking at industry implementations.

My hunch is that because CRDTs are so much easier to grok than OT, engineers are empowered to make use case-specific improvements that aren't reflected in academic literature.

For example, the Logoot/LSEQ CRDTs have issues with concurrent insert interleaving; however, this can be solved by dedicating a bit-space in each ID solely for followup inserts. The "Inconsistent-Position-Integer-Ordering" problem is solved by comparing ids level-by-level instead of in one shot.

Fundamentally, CRDTs have strong strategic advantages over OT. Given a document size N and a document edit history H:

* CRDT size is O(N) where OT is O(H)

* CRDT updates are O(log N) where OT is O(H^2)

In any nontrivial document, H ≫ N. This means CRDTs have much better perf than OT. Additionally, the best CRDTs (like Logoot/LSEQ) don't require tombstones, garbage collection, or "quiescence." The complexity burden is far lower.

To top it off, CRDTs are offline-capable by default.

Re: Real Differences Between OT and CRDT for Co-Editors

#15

Post by zzzcpan »

"most other OT solutions ... do not require a central server to do (any part of) the OT work, but only require the use of an external causal-order-preserving communication service (the same as most CRDT solutions). "

CRDTs don't require an external causal-order-preserving communication service. That's kind of the whole point of CRDTs. At the same time this is what imposes certain limitations on how they can be used. But so is automatic conflict resolution in collaborative editing.

Re: Real Differences Between OT and CRDT for Co-Editors

#16

Post by shunza »

amsha wrote: post #14

Here's the key sentence: "concrete implementations of CRDT in co-editors revealed key missing steps in CRDT literature." This paper may be correct for academic CRDTs but it is very wrong when looking at industry implementations. My hunch is that because CRDTs are so much easier to grok than OT, engineers are empowered to make use case-specific improvements that aren't reflected in academic literature. For example, th…

The time complexity of most OT systems is not related to H.

Re: Real Differences Between OT and CRDT for Co-Editors

#17

Post by shunza »

zzzcpan wrote: post #15

"most other OT solutions ... do not require a central server to do (any part of) the OT work, but only require the use of an external causal-order-preserving communication service (the same as most CRDT solutions). " CRDTs don't require an external causal-order-preserving communication service. That's kind of the whole point of CRDTs. At the same time this is what imposes certain limitations on how they can be used.…

Except for WOOT, which CRDT for co-editor does not require causal ordering?

Re: Real Differences Between OT and CRDT for Co-Editors

#18

Post by gritzko »

shunza wrote: post #17
zzzcpan wrote: post #15

"most other OT solutions ... do not require a central server to do (any part of) the OT work, but only require the use of an external causal-order-preserving communication service (the same as most CRDT solutions). " CRDTs don't require an external causal-order-preserving communication service. That's kind of the whole point of CRDTs. At the same time this is what imposes certain limitations on how they can be used.…

Except for WOOT, which CRDT for co-editor does not require causal ordering?

RON CT/RGA may consume inputs in arbitrary order.

Re: Real Differences Between OT and CRDT for Co-Editors

#19

Post by josephg »

lowry wrote: post #9
zawerf wrote: post #6

Only tangentially related, but today I was reading about collaborative editing using Quill.js (a rich text editor) and found a really nice solution based on sharedb (using ottypes/rich-text): https://github.com/pedrosanta/quill-sharedb-cursors Before I dive knee deep into this, does anyone have any opinion on sharedb or better alternatives? (it was listed in this post under it's old name, sharejs, as one of the more…

The article above says sharedb is originally written by a Google Wave developer.

waves Y'all are talking about me. I was indeed on the wave team, although I joined Wave right near the end. (And then I stayed on to help opensource the whole thing.)

We wrote ShareDB at Lever[1], which was in the 2012 YC batch (iirc). We wrote it to allow realtime collaborative editing in our application of all our data fields by default. I'm still really proud of that work. ShareDB primarily uses JSON-OT[2], which lets you do realtime OT over arbitrary application data. The lever team has been maintaining & improving sharedb for the last few years, which is really lovely to see as I've moved on to other projects.

One nice thing about OT is that its much easier to implement. The original quilljs author (Jason Chen) wrote the rich text OT implementation. ShareDB works with any OT code (so long as operations can be JSON stringified / parsed). And its all hooked up in quill, which is super neat. And looking at the quill github[3], it looks like David Greenspan has been maintaining quill recently. David Greenspan is one of the original authors of Etherpad, which is one of the first web based text OT engines.

[1] https://lever.co/

[2] https://github.com/ottypes/json0

[3] https://github.com/quilljs/quill

Re: Real Differences Between OT and CRDT for Co-Editors

#20

Post by shunza »

gritzko wrote: post #18
shunza wrote: post #17

Earlier quoted context omitted.

Except for WOOT, which CRDT for co-editor does not require causal ordering?

RON CT/RGA may consume inputs in arbitrary order.

In the original paper of RGA, RGA does require that operations are received with respect to the causal ordering. And RGA preserves causality by state vector technique.
Post reply on HN