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.
- Kevin (Author of Yjs)
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?
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.
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.
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.
Can't wait for higher-level library (yJS or others) to support a matrix backend so i can mess around with that!
