On the Matrix core team, we're working on 'native' collaborative editing collaboration via the Matrix DAG - while shamelessly learning from CRDT-over-Matrix projects like this one :)
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!
