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.
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-edi... [2]: https://github.com/dmonad/crdt-benchmarks
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).
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.