I’ve been working on a “CRDT-inspired” adaptation of prosemirror-collab, which you can find here, with the interesting code in prosemirror_wrapper.ts. It is just a prototype for now, but I wanted to share it and would be happy to hear any feedback.
The architecture is almost the same as prosemirror-collab, with a central server that totally orders all changes to the document. The difference is in how it rebases on top of concurrent changes: instead of mapping ProseMirror positions through the concurrent changes (OT-style), it annotates the original steps with immutable IDs (CRDT-style), then looks up where those IDs belong in the current document. The IDs (confusingly also called “Positions”) come from my list-positions library.
Relative to prosemirror-collab, this eliminates the need for clients to resubmit changes to the server: the server can append changes to the log as-is, and the IDs will still “make sense”, even if there were intervening concurrent changes.
Relative to y-prosemirror, the server’s authoritative log makes it easy to reject/modify changes on the server. Additionally, clients always apply remote changes using native ProseMirror steps, which can be useful for plugins/decorations (cf y-prosemirror issue 113).
I also found implementing this a lot easier than trying to figure out a “ProseMirror CRDT” that somehow makes all concurrent updates commute.
Yes, the server and clients each store a tree describing the order on IDs, plus an “Outline” describing which IDs are currently present in the ProseMirror document.
For compactness, the tree groups sequential insertions by the same user into “bunches” of IDs, which are internally represented with a single object (instead of one object per ID). There’s more info in the list-positions internals.
@ProTip I’d be curious to hear about your experience with prosemirror-collab-commit, since it nominally addresses the same question - how to avoid client-side op resubmission while still working with native ProseMirror steps. Are there particular challenges you ran into while implementing it, or additional problems that it solves?
It took a lot of ProseMirror domain knowledge to feel comfortable the implementation was “correct”. In particular the importance and function of setMirror wasn’t clear to me until after I translated ProseMirror to C# and had to debug my bit-shifting logic. At least when I created the plugin setMirror was still not a public API.
Re-using the prosemirror-collab test harness and test suite was clutch in getting everything ironed out.
One of my requirements was to validate the schema server-side on every update. I’ve seen very heavily augmented and actively developed ProseMirror implementations introduce bugs that corrupt the step history in the server. As well, I want to be able to create valid document edits, or modify submitted commits, server-side.
I have also created a fully featured(edit history, spashots, branches, etc) backend based on YJS and have heavily customized the official ProseMirror bindings. This experience led me to believe that, for my requirements, CRDTs added an extra unneeded layer of complexity and abstraction.
Thanks, this is all good to know. I should set up the prosemirror-collab test suite as well. (The underlying CRDT library has similar tests, but not the ProseMirror-specific code.)
I have also created a fully featured(edit history, spashots, branches, etc) backend based on YJS and have heavily customized the official ProseMirror bindings. This experience led me to believe that, for my requirements, CRDTs added an extra unneeded layer of complexity and abstraction.
Impressive! Yes, this sounds like a lot of effort relative to a server that has direct control over the actual ProseMirror steps + state.
Interesting work in both @mweidner037 and @ProTip libraries I’ve come to a half-way conclusion that if you’re doing anything more complicated than read-write for documents and need to customize the sync server either way CRDTs are perhaps a bit too much. Only problem with collab has been perf with many users but if these implementations fix them, I am intrigued to try them out.
So these IDs are client-generated for each step? One particular problem with ProseMirror docs is the lack of global IDs for nodes which many resolve to add manually for linking purposes and just to prevent constant remapping & iterating of the doc. This in theory maps nicely with CRDTs as the blocks have unique IDs but afaik they are not used at least by default libraries. But it’d be nice if this was easily achievable since IDs are so commonly used.
I suppose access control works normally with these enhanced collabs? You just look at the changed range and revert/discard the step if unauthorized?
One benefit of CRDTs is the added bonus of optimized implementations which probably are an order of magnitude faster than any NodeJS server can do. But in scale most people operate, it’s cheaper to just buy a bigger server.
So these IDs are client-generated for each step? One particular problem with ProseMirror docs is the lack of global IDs for nodes which many resolve to add manually for linking purposes and just to prevent constant remapping & iterating of the doc. This in theory maps nicely with CRDTs as the blocks have unique IDs but afaik they are not used at least by default libraries. But it’d be nice if this was easily achievable since IDs are so commonly used.
Yes, a client assigns an immutable ID for each ProseMirror position that is “created” by a local ReplaceStep or ReplaceAroundStep. You can use the ID corresponding to a node’s starting position as a global “node ID” and look up the corresponding node in any future state.
Caveat: Currently, if you replace a node with one of a different type (e.g., converting a <p> into an <h1>), the demo models that as a delete-then-insert. So the replaced node gets a new, different ID. This should be fixable.
I suppose access control works normally with these enhanced collabs? You just look at the changed range and revert/discard the step if unauthorized?
Yes, the server has complete control over the log and can read/reject/add AnnotatedSteps at will. Concurrent client updates should still “make sense” even though this changes the state to which they’re applied. (In theory - I have not yet tested this yet.)
One benefit of CRDTs is the added bonus of optimized implementations which probably are an order of magnitude faster than any NodeJS server can do.
In experiments on a predecessor of list-positions (Collabs), we were able to shove 100+ active users into a rich-text document without overwhelming a simple NodeJS server running on an AWS t2.medium. The main bottleneck was client-side Quill rendering; I ought to try again with list-positions + ProseMirror and see what happens.
Fascinating! Seems like this could solve many annoying parts of the other syncing libraries.
Just not an easy task to switch from a tried-and-true approach, such as Yjs, so having a good test suite and working examples is very much required. The edge-cases are also the one thing that bites you in the ass hard so it would be nice to know there’s solid error-handling incase things go wrong eg your schemas go out of sync or there’s some network error.
@mweidner037 This looks incredible! I’ve always thought manipulating indexes led to a bunch of complexity that would be avoided if we just addressed elements by ids. It’s exciting to see someone try that out! I’m most excited by this part:
this eliminates the need for clients to resubmit changes to the server: the server can append changes to the log as-is, and the IDs will still “make sense”, even if there were intervening concurrent changes.
In looking at the code and this post, I have some questions:
It is just a prototype for now, but I wanted to share it and would be happy to hear any feedback.
What do you think the next steps are to making this production ready?
I’m curious if I’d need to save a log of all the transactions for all the edits or would I load the current JSON of the document and then receive updates as they come in?
In the current demo, clients don’t store data locally; instead, the server stores the log of steps (in memory) and sends them to clients upon connection.
In principle, the server could store the current JSON (+ list-positions metadata) instead of the log of steps. Note that the server does need some way to remember which steps have been applied, so that it can filter duplicates after a client reconnects.
It’s also possible in theory to let clients cache the latest state in IndexedDB. On startup, they can load this cached state, then replace it with (server’s latest state # pending local steps) once they hear from the server.
instead, the server stores the log of steps (in memory) and sends them to clients upon connection.
So, if I was implementing this and storing the data in our database, I would:
Store the log of steps
When the text area is rendered, use the wrapper’s receive function to load the existing steps into the editor. Do I have that right?
validate it with various schemas & plugins
While validating with schema and plugins is definitely important, are there any obvious areas you’d be worried about it not working? Like, is that just for completeness or are there behaviors of this library that you think are likely to have weird incompatibility issues with schemas and plugins?
Yes, exactly. This should work fine but could be a performance challenge for docs with a long history - with the usual workaround (state snapshots).
While validating with schema and plugins is definitely important, are there any obvious areas you’d be worried about it not working? Like, is that just for completeness or are there behaviors of this library that you think are likely to have weird incompatibility issues with schemas and plugins?
Some schemas have constraints that are hard to enforce collaboratively, like mandating that a node contains at least one child node of a given type. (What if it starts with two children and two users concurrently delete one each?) I’m not sure what the editor will do in these situations; I hope it will be roughly equivalent to prosemirror-collab’s behavior (since it uses the same log-of-steps abstraction) but I need to check.
Likewise for plugins: they should end up seeing a nice sequence of steps like when using prosemirror-collab (instead of complete state replacements), but it’s possible some weird interactions crop up.
I’ve come to a half-way conclusion that if you’re doing anything more complicated than read-write for documents and need to customize the sync server either way CRDTs are perhaps a bit too much. Only problem with collab has been perf with many users but if these implementations fix them, I am intrigued to try them out.