Hacker News Reader

Comment by shunza | Hacker News Reader

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

I fully agree, I don't understand the emphasis on performance both in the literature and in comments on the subject.

Additionally, it is more common to see CRDT libraries that make character-wise operations and create an object for each character (eg. y-js.org, github.com/google/ot-crdt-papers), which is not ideal.

Obviously there are also libraries such as Atom's Teletype that have string-wise operations.

The cynic in me feels like the CRDT vs. OT war misses the forest for the trees. What matters is lacking features, and the feature that is most needed and least described is a systematic way to offer a diff editor matching the normal experience. Indeed, after having been offline a while, one wants to see and select how their changes will integrate the shared resource.

I think you'll find the article supports your sentiment to an extent.

One of the key messages we tried to get across is that academic research for co-editing ought to go beyond theoretical analysis but rather drive research by pushing the envelope in new areas of application and/or features. OT's evolution has been symbiotic with new applications, while we haven't seen this in CRDT (for coediting) research. The reality is that you'll find new CRDT papers every year that still (a) make fairly broad claims of benefits are either theoretically dubious or not backed/validated by application/system implementations, (b) dwelling on technical issues that were resolve years ago. To move beyond this, we want to have put these issues in context (a general transformation approach) and dispel the most common fallacies in theoretical analysis.

Related to the 'visual-merging' feature you mentioned, when I worked on making MS Word collaborative as a research project, one of the UX research questions was how to allow users to visualize the different combined effects of updates to objects (e.g. if you changed the background of object X to red and I change it to yellow at the same time). We came up with a multi-versioning technique to display the potentially different combinations and help users select one that's the most desirable. It is definitely a interesting and challenging problem to consider for text documents.

My personal experience is different. OT tends to be quadratic in terms of computational complexity and codebase size. As long as you consider a simple case, 1^2 is 1. Then, add more data types (not just text), faulty servers, faulty network, non trivial network architectures... All these problems tend to interact. They easily go combinatorial, but again 1! is 1. I worked with an OT codebase that had C++ templates within C defines and I edited them using regexes (x types of operations => x^2 types of potential transformations).

OT aside, data sync in general is not a solved problem. Maybe I am especially unlucky, but I have yet to see a chat app that has no sync glitches. A chat is not the most difficult data structure to sync, but I saw bugs in Slack, Telegram, Instagram, Gchat, Skype, others... WhatsApp does not even try to sync...

A lot depends on the diversity of your use cases and the number of the nines you expect from the system...

<- This, concurs with our experience.

When we profiled our string OT implementation on a single 2-3 GHz CPU, with 2-3 CPI (Cycle Per Instruction)), it was able to handle about 10M transformations per second. On a half dozen of OT based system I've worked on, the OT implementation was never where we found the real engineering complexity or the performance bottleneck in working coeditors.

The significance of using string-wise operation model in OT is under appreciated and can't be emphasized enough for real world systems. The first string-wise OT transformation functions can be traced back to Achieving Convergence, Causality Preservation, and Intention Preservation in Real-Time Cooperative Editing Systems, 1998. We also found that skip, insert, and delete can improve compression of string edits.

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.

Reply on news.ycombinator.com