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

21–30 of 66 posts

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

#21

Post by amsha »

shunza wrote: post #16
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.

My understanding of OT is that each change requires traveling backward though the edit history to find the first state that is consistent between sites, then traveling forward to transform the new change against past edits. In the worst case, an edit requires transformation against the document’s origin state.

Is that not the case?

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

#22

Post by shunza »

amsha wrote: post #21
shunza wrote: post #16

Earlier quoted context omitted.

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

My understanding of OT is that each change requires traveling backward though the edit history to find the first state that is consistent between sites, then traveling forward to transform the new change against past edits. In the worst case, an edit requires transformation against the document’s origin state. Is that not the case?

Most OT systems only transform concurrent operations.

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

#23

Post by josephg »

shunza wrote: post #16
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.

I've been working in OT systems for years (G Wave, ShareJS, ShareDB, some other stuff). I'm consistently surprised by how badly academic papers predict OT systems will perform. In reality, they perform great. My little C implementation of text OT can handle about 20M text operation transforms / second[1].

Part of the gap is that many academic papers model text operations as just single character edits. If you do that, copy+pasting some text into an editor can inject thousands of insert operations into the system all at once. But that design is really sloppy - nobody actually designs real world OT systems like that. A much better way to design text OT operations uses a list of skip, insert and delete parts. That way you can arbitrarily compose edits together. This way an entire pasted string just gets inserted in one operation and performance is fine. (Or if the user goes offline, you can merge all the edits they do into a single change, then transform & commit it all at once).

I've still never seen the OT algorithms of anything I've worked on have a meaningful impact on performance. Actually thinking about it I'm not sure if I've ever even seen the OT code show up in profile traces.

[1] https://github.com/ottypes/libot

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

#24

Post by amsha »

shunza wrote: post #22
amsha wrote: post #21

Earlier quoted context omitted.

My understanding of OT is that each change requires traveling backward though the edit history to find the first state that is consistent between sites, then traveling forward to transform the new change against past edits. In the worst case, an edit requires transformation against the document’s origin state. Is that not the case?

Most OT systems only transform concurrent operations.

That's true. My performance claims are biased toward offline-capable editors, where the last consistent state between sites may be thousands or millions of edits ago. For online-only editors the set of edits between now and the most recent consistent state may be much smaller.

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

#25

Post by alangibson »

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.

Some background on the Causal Tree (CT) that gritzko is referring to: http://archagon.net/blog/2018/03/24/data-laced-with-history.

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

#26

Post by alangibson »

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.

I'm not accusing the authors of this, but some people seem to have knee-jerk reaction against CRDTs because from far away they look like magic. "Use this magic data structure and all your conflicts shall disappear." Of course, once you look closely you see there are plenty of tradeoffs, just like anything else.

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

#27

Post by josephg »

m12k wrote: post #11
shunza wrote: post #5

Earlier quoted context omitted.

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

Simple OT algorithms do work a lot better with a centralized server.

With a centralized server, you can consider every resolution as happening between 2 nodes (server and client). This means transform / catchup is as simple as a for loop.

In contrast, in decentralized context OT code needs to support Transform Property 2[1] in order to converge correctly in all cases. TP2 dramatically complicates the OT implementation, and you need a much more complicated resolution algorithm to merge arbitrary changes between nodes.

For text, this means you need:

- Tombstones (or something like it) - eg https://github.com/josephg/TP2/blob/master/src/text.coffee

- Either an operation prune function (anti-transform) or full history, forever.

- A resolution algorithm that can flatten DAGs of operations into a transformed list. This stuff gets really hairy, and hard to implement efficiently. This is my attempt from a few years ago. Its correct, but super slow: https://github.com/josephg/tp2stuff/blob/master/node3.coffee

Implementing high performance OT with centralized servers is easy. Implementing OT in a decentralized network is hard to do correctly, and much harder to implement in a highly performant way. For decentralized systems, CRDTs are a much better approach imo.

[1] https://en.wikipedia.org/wiki/Operational_transformation#Tra...

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

#29

Post by irq-1 »

josephg wrote: post #27
m12k wrote: post #11

Earlier quoted context omitted.

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

Simple OT algorithms do work a lot better with a centralized server. With a centralized server, you can consider every resolution as happening between 2 nodes (server and client). This means transform / catchup is as simple as a for loop. In contrast, in decentralized context OT code needs to support Transform Property 2[1] in order to converge correctly in all cases. TP2 dramatically complicates the OT implementatio…

Thanks! That was super informative.

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

#30

Post by shunza »

josephg wrote: post #27
m12k wrote: post #11

Earlier quoted context omitted.

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

Simple OT algorithms do work a lot better with a centralized server. With a centralized server, you can consider every resolution as happening between 2 nodes (server and client). This means transform / catchup is as simple as a for loop. In contrast, in decentralized context OT code needs to support Transform Property 2[1] in order to converge correctly in all cases. TP2 dramatically complicates the OT implementatio…

Several decentralized OT systems [1] can avoid the TP2 constraint on transformation functions.

[1] https://dl.acm.org/citation.cfm?id=2914099

Post reply on HN