4 ms·

I've been looking for a practical OT alternative for our online word processor (https://zoho.com/writer https://zoho.com/writer). We already use OT for syncing

I've been looking for a practical OT alternative for our online word processor (https://zoho.com/writer https://zoho.com/writer). We already use OT for syncing our realtime edits and exploring CRDTs targetting stronger consistency for tackling offline edits (which are typically huge & defragmented, since the edits are not syncing in realtime) So the baseline is that OT has a better model for holding state in terms of performance/memory, since the edits can be compiled into plain string types. CRDTs in comparison forces us to hold deleted states as well and demands richer information per unit (character/string/etc) - which makes it harder on the CPU/RAM. Here's the story as I understand: 1. Automerge tackles this by just moving to a better lower-level runtime: Rust. 2. Yjs handles this by using a similar technique i.e relying on V8's hidden classes to handle the performance optimizations and assuming real-world cases to narrow down and optimize datastructures. But none of these, seem to be a fundamental breakthrough in the efficiency of the algorithm itself. They all at best look like a workaround and this keeps bothering me.

pfraze 5y ago
You can remove tombstones in a cleanup pass if you constrain behavior a bit. For instance, if there’s just a single server, after 5 minutes of no active connections you could clean out tombstones. After that, if a client connects with some changes they had been holding onto but got DCed, you can reject the write and let the user’s client merge by some other means (perhaps even manual).
josephg 5y ago
If you've got big offline edits (or you're merging multiple large sets of edits), even existing CRDTs will generally handle that more efficiently than OT will. OT algorithms are usually O(n * m) time complexity when merging n edits from one peer with m edits from another peer. A CRDT like diamond-types is O((n + m) * log(s)) where s is the current size of the document. In practice its super fast. As for holding deleted states and richer information per unit, its not so bad in absolute terms. 1-2mb of data in memory for a 17 page document is honestly fine. But there's also a few different techniques that exist to solve this in CRDTs: 1. Yjs supports "garbage collection" APIs. Essentially you say "anything deleted earlier than this point is irrelevant now" and the data structures will flatten all runs of items which were deleted earlier. So storage stays proportional to the size of the not-deleted content. 2. Sync9 has an algorithm called "antimatter" which mike still hasn't written up poke poke mike!. Antimatter actively tracks the set of all peers which are on the network. When a version is known to have been witnessed by all peers, all extra information is safely discarded. You can also set it up to assume any peer which has been offline for however long is gone forever. 3. Personally I want a library to have an API method for taking all the old data and just saving it to disk somewhere. The idea would be to reintroduce the same devops simplicity of OT where you can just archive old history when you know it probably won't ever be referenced again. Keep the last week or two hot, and delete or archive history at will. If you combined this with a "rename" operation, you could reduce the "hot" dataset to basically nothing. This would also make the implementation much simpler - because we wouldn't need all these performance tricks to make a CRDT like diamond-types fast if the dataset stayed tiny anyway.
kevinjahns 5y ago
I know that it is hard to comprehend why modern CRDT implementations are fast. But the data confirms that they work great. OT seems to be much simpler, but there are real advantages in using CRDTs. The performance problems have been solved through an efficient representation of the CRDT model. The gist of the below [1] read is that it is impossible for a human to create a document that Yjs can't handle (even in the worst case scenario). But yes, it handles real-world scenarios particularily well. The concept of "hidden classes" is super old. It has first been implemented in a fork of smalltalk and then became foundational concept of runtime engines for scripting languages. It is implemented in V8, python, ruby, spidermonkey, .. Yjs does not assume a "real-world scenario" and it is not optimized for any specific runtime engine. It runs fast in any browser. The benchmarks confirm this. [2] Yjs is being used in practice by several companies (eg Nimbus Notes with >3 million users) for quite some time now. I'm not aware of any performance problems. [1]: https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/ https://blog.kevinjahns.de/are-crdts-suitable-for-shared-edi... [2]: https://github.com/dmonad/crdt-benchmarks https://github.com/dmonad/crdt-benchmarks

pfraze 5y ago

You can remove tombstones in a cleanup pass if you constrain behavior a bit. For instance, if there’s just a single server, after 5 minutes of no active connections you could clean out tombstones. After that, if a client connects with some changes they had been holding onto but got DCed, you can reject the write and let the user’s client merge by some other means (perhaps even manual).

josephg 5y ago

If you've got big offline edits (or you're merging multiple large sets of edits), even existing CRDTs will generally handle that more efficiently than OT will. OT algorithms are usually O(n * m) time complexity when merging n edits from one peer with m edits from another peer. A CRDT like diamond-types is O((n + m) * log(s)) where s is the current size of the document. In practice its super fast. As for holding deleted states and richer information per unit, its not so bad in absolute terms. 1-2mb of data in memory for a 17 page document is honestly fine. But there's also a few different techniques that exist to solve this in CRDTs: 1. Yjs supports "garbage collection" APIs. Essentially you say "anything deleted earlier than this point is irrelevant now" and the data structures will flatten all runs of items which were deleted earlier. So storage stays proportional to the size of the not-deleted content. 2. Sync9 has an algorithm called "antimatter" which mike still hasn't written up poke poke mike!. Antimatter actively tracks the set of all peers which are on the network. When a version is known to have been witnessed by all peers, all extra information is safely discarded. You can also set it up to assume any peer which has been offline for however long is gone forever. 3. Personally I want a library to have an API method for taking all the old data and just saving it to disk somewhere. The idea would be to reintroduce the same devops simplicity of OT where you can just archive old history when you know it probably won't ever be referenced again. Keep the last week or two hot, and delete or archive history at will. If you combined this with a "rename" operation, you could reduce the "hot" dataset to basically nothing. This would also make the implementation much simpler - because we wouldn't need all these performance tricks to make a CRDT like diamond-types fast if the dataset stayed tiny anyway.

kevinjahns 5y ago

I know that it is hard to comprehend why modern CRDT implementations are fast. But the data confirms that they work great. OT seems to be much simpler, but there are real advantages in using CRDTs. The performance problems have been solved through an efficient representation of the CRDT model. The gist of the below [1] read is that it is impossible for a human to create a document that Yjs can't handle (even in the worst case scenario). But yes, it handles real-world scenarios particularily well. The concept of "hidden classes" is super old. It has first been implemented in a fork of smalltalk and then became foundational concept of runtime engines for scripting languages. It is implemented in V8, python, ruby, spidermonkey, .. Yjs does not assume a "real-world scenario" and it is not optimized for any specific runtime engine. It runs fast in any browser. The benchmarks confirm this. [2] Yjs is being used in practice by several companies (eg Nimbus Notes with >3 million users) for quite some time now. I'm not aware of any performance problems. [1]: https://blog.kevinjahns.de/are-crdts-suitable-for-shared-editing/ https://blog.kevinjahns.de/are-crdts-suitable-for-shared-edi... [2]: https://github.com/dmonad/crdt-benchmarks https://github.com/dmonad/crdt-benchmarks