Author of Yjs here. I'm all for faster data structures. But only benchmarking one dimension looks quite fishy to me. A CRDT needs to be adequate at multiple dimensions. At least you should describe the tradeoffs in your article.
The time to insert characters is the least interesting property of a CRDT. It doesn't matter to the user whether a character is inserted within .1ms or .000000001ms. No human can type that fast.
It would be much more interesting to benchmark the time it takes to load a document containing X operations. Yjs & Yrs are pretty performant and conservative on memory here because they don't have to build an index (it's a tradeoff that we took consciously).
When benchmarking it is important to measure the right things and interpret the results somehow so that you can give recommendations when to use your algorithm / implementation. Some things can't be fast/low enough (e.g. time to load a document, time to apply updates, memory consumption, ..) other things only need to be adequate (e.g. time to insert a character into a document).
Unfortunately, a lot of academic papers set a bad trend of only measuring one dimension. Yeah, it's really easy to succeed in one dimension (e.g. memory or insertion-time) and it is very nice click-bait. But that doesn't make your CRDT a viable option in practice.
I maintain a set of benchmarks that tests multiple dimensions [1]. I'd love to receive a PR from you.
It's interesting to me that people still doubt that CRDTs can be used in practice. The fact is that they are already being used in practice by many companies with millions of users for applications like rich-text editing and state management in 3d applications. See https://github.com/yjs/yjs#who-is-using-yjs
In fact, Yjs - a CRDT implementation- is the most downloaded solution for collaborative applications. Even more than ShareDB (the most popular OT-based solution).
What I dislike about these attempts is that you will just end up with yet another CRDT implementation that is incompatible with the existing ecosystem (editors, drawing apps, state management, ...).
Instead, I want to encourage you to build an API that others can use to
efficiently store shared data. Feel free to ping me if you need input.
I'm happy to see representatives from both the matrix and yjs communities interact more directly.
Can you expand on what you mean by this?
> an API that others can use to efficiently store shared data
What would you expect this API look like in a bit more detail? Would it be able to abstract any of the underlying CRDT logic? Would it just be a raw stream of authenticated messages with partial ordering? Something in-between?
Instead of building another shared-editing solution specialized for Matrix, there could be an API that can be used to store and distribute real-time updates efficiently (probably in the Matrix DAG).
The matrix-crdt works really well. To reduce overloading the Matrix server with many small messages (each single keystroke produces an update message), it stores merged updates in the DAG after a short debounce. The optional WebRTC extension allows you to distribute messages immediately "of the chain", so you don't notice the debounce.
After a time the message-log gets pretty huge. So in matrix-crdt, a random client will eventually store a "snapshots" of the current state in the DAG and removes old entries. This way, new clients don't need to download the huge message-log.
It would be nice if there was a possibility to create a server-component that does the merging.
(Btw, all credit to the above approach goes to Yousef)
Now, there might be a better solution to store CRDT data in the Matrix DAG - the developers probably know best and might be able to expose some hidden API that would make everything even more efficient.
I'm just asking that instead of creating yet another CRDT and integrating it into Matrix, open up this space, provide better APIs, and let others integrate their CRDTs.
> Would it be able to abstract any of the underlying CRDT logic?
Modern shared-editing frameworks don't require you to think about internal logic. They just set some requirements on the ordering of update messages. CRDTs in particular don't care in which order you transmit data, which makes them a very interesting choice in practice.
It might be worth putting together a chat between matrix and a few of us! I have some thoughts on this too, having written two differently designed CRDTs with diamond types.
Replaying a series of changes from an operation log is quite doable (blog post incoming). But having a way to compress / annotate the operation stream will lead to far better performance in lots of ways. Especially as Kevin says - with CRDTs like Yjs and automerge which consider document order (not time order) as the canonical representation.
Have you guys taken a look at all of the various torrent-based[0] approaches that's been going around HN? Feels like if you combine the storage component of those with the real-time approach you've got here, it would feel like magic.
So to be clear, on the Matrix side we have absolutely zero desire to build another general purpose CRDT implementation - Yjs, automerge, Collabs etc are already here :)
However, all the current collaborative editing apps which use Matrix operate by serialising opaque CRDT updates as Matrix events - a bit like Wave used to send blobs of base64 as OT updates over XMPP. Matrix-CRDT is cool in terms of also transporting updates over a WebRTC ephemeral transport to get lower latency (although it's missing a trick that the WebRTC looks to be signalled over websockets rather than just using Matrix's VoIP signalling to give you E2EE decentralised WebRTC signalling for free ;)
Now, Matrix already is a constrained CRDT (monotonic semi-lattice, i think?) which provides primitives for key-value and conversation-timeline storage. Our merge resolution algorithm is detailed at https://matrix.org/blog/2020/06/16/matrix-decomposition-an-i.... However, we always intended to be able to store object graphs in Matrix too - and have been experimenting with APIs for traversing a DAG of objects overlaid within Matrix's room DAG (e.g. https://github.com/matrix-org/matrix-doc/blob/kegan/msc/thre... - which isn't really about threading specifically, but could be traversing any kind of object graph).
So, what we're looking at now is (i think?) precisely what you're proposing that we do - i.e. use an existing CRDT implementation to model the collaborative evolution of an arbitrary object graph - while also snapshotting that as we go as evolutions within the Matrix room DAG. I haven't been working on it myself, and we haven't published the research yet, but I'd assume we'd do something like pass CRDT updates as Matrix EDUs (Ephemeral Data Units) between clients, with the server then maintaining or generating snapshots of views of the graph. The key thing we're aiming for is to build on the existing decentralised namespace and identity model and end-to-end encryption that Matrix already provides.
This could look something like:
* Client A negotiates a WebRTC data channel with Client B for low-latency collaboration (via standard Matrix m.call.invite WebRTC signalling, so you get E2EE and decentralisation for free)
* CRDT updates also get sent to the server via the Matrix client-server API (n.b. that in the nearish future the server may actually be running locally within the client, thanks to P2P Matrix: https://matrix.org/blog/2021/05/06/introducing-the-pinecone-...). For E2EE rooms, updates would have to be at the granularity of an encrypted event (but perhaps clients participating in the E2EE could decrypt, coalesce and re-store these).
* Server maintains a view of the object graph, letting clients navigate lazily through the tree, view it or bits of it as versioned snapshots, or start participating in the CRDT itself.
(It's worth noting that Matrix events are deliberately capped to 65KB - anything bigger than that should be persisted as a binary blob on disk. In this model it's probably fine, given you'd want events to be as small as possible - possibly even keystrokes.)
Again, this is very handwavy and I'm not actually working on it myself, but it hopefully gives a vague idea of what we're thinking about.
This is pretty cool! Some people were asking on another thread about the differences between XMPP and Matrix the other day: first-class support for CRDTs (or equivalent consensus-reaching) is in my view a key property of Matrix and despite not using Matrix for chat yet, i can definitely see myself using it for collaborative apps (Etherpad is still bugged after all these years, and HedgeDoc is in my personal opinion going in the wrong direction by removing explicit macros).
Can't wait for higher-level library (yJS or others) to support a matrix backend so i can mess around with that!
I can only answer to the last question. Yjs uses several performance optimizations to produce small documents (both in memory and in the encoded state). Since humans type relatively slow (<60 actions per minute), it is impossible for humans to create a document that has performance problems. I showed this in [1].
Relm [2] even models a 3d world using Yjs. I don't necessarily recommend doing this as 3d applications usually produce a lot more actions per minute than text applications. This required some workarounds and deep knowledge of how Yjs' optimizations work. But it's definitely possible.
Yjs author here. On network failure, the client will automatically reconnect and synchronize with the backend. And yes, you can get an event that notifies you about the current connection status. When syncing with the server, you will only exchange the differences that were created while offline.
Yjs author here. Yjs ships a flexible selective undo-redo manager. You can define one (or several) undo managers that listen to changes that you want to be able to undo&redo.
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.
Yjs is exactly that. It is a simple abstraction for building any kind of collaborative application. It has ready to use solutions for most problems related to this problem space. The selective UndoManager, for example, is generic&configurable and can be reused for all kinds of stuff. It supports many different editors. It supports many different (scalable) backends.
It is much more than state synchronization.
If there is anything missing, then let's work on it. Yjs is extensible and allows for custom features that others can reuse.
The time to insert characters is the least interesting property of a CRDT. It doesn't matter to the user whether a character is inserted within .1ms or .000000001ms. No human can type that fast.
It would be much more interesting to benchmark the time it takes to load a document containing X operations. Yjs & Yrs are pretty performant and conservative on memory here because they don't have to build an index (it's a tradeoff that we took consciously).
When benchmarking it is important to measure the right things and interpret the results somehow so that you can give recommendations when to use your algorithm / implementation. Some things can't be fast/low enough (e.g. time to load a document, time to apply updates, memory consumption, ..) other things only need to be adequate (e.g. time to insert a character into a document).
Unfortunately, a lot of academic papers set a bad trend of only measuring one dimension. Yeah, it's really easy to succeed in one dimension (e.g. memory or insertion-time) and it is very nice click-bait. But that doesn't make your CRDT a viable option in practice.
I maintain a set of benchmarks that tests multiple dimensions [1]. I'd love to receive a PR from you.
[1]: https://github.com/dmonad/crdt-benchmarks