Collaborative Text Editing Without CRDTs or OT
mattweidner.com
mattweidner.com
- Label each text character with a globally unique ID (e.g., a UUID), so that we can refer to it in a consistent way across time - instead of using an array index that changes constantly.
- Clients send the server “insert after” operations that reference an existing ID. The server looks up the target ID and inserts the new characters immediately after it.
- Deletion hides a character for display purposes, but it is still kept for "insert after" position purposes.
This might have potential outside text editing. Game world synchronization, maybe.
My best guess is:
- Central-server collaborative editing work focuses on Operational Transformation (OT), likely due to inertia (studied since 1989) and the perception that storing an ID per character is inefficient. In fairness, it is, absent the optimizations introduced by RGASplit and Yjs (~2015).
- For decentralized editing, OT is very complicated, and CRDTs took over as the solution of interest (studied since 2005). Storing every operation permanently in a log - needed to use the linked approach without a server - feels inefficient, as does server reconciliation's undo/re-apply process. So CRDT research has focused on avoiding those inefficiencies, sacrificing simplicity along the way, instead of just embracing them as the easy way out.
To me, the "inefficiencies" seem quite manageable. Storage is cheap, text is small, and you probably want a complete op log anyway for auditing and document histories (cf. git). Server reconciliation's undo/re-apply process can be batched aggressively, e.g., only do it a few times per second; that just makes remote ops take a little longer to show up.
Granted, I have not built a complete app around server reconciliation or the linked approach, so perhaps there is a hidden catch. But I am encouraged by the success of Replicache (https://doc.replicache.dev/concepts/how-it-works), which is where I learned of server reconciliation.
This would seem to avoid clashes and also compress the identifier storage in an efficient way.
I will check out Antirez.
:)
:(
Yes. This article reads like the adage "a month in a lab saves you an hour in a library".
a{uuid=1}
b{uuid=2} insert-after{uuid=1}
c{uuid=3} insert-after{uuid=1}
abc
acb
I mean, a uuid is kind of a poor man's Lamport clock, isn't it?
I get what you mean though, having a central authority greatly relaxes the requirement.
It has all the flavor of CRDT, but adds a leader and a different way for the total ordering (basically using leader's local lamport clock to break tie).
Throw in leader reelection and some ledger syncing and then give everything some other names, I bet you can have "collaborative text editing on one page".
I don’t really understand the benefit of doing this when text CRDTs are small, simple and fast.
Hey, can you elaborate? Googling this I can find this other HN comment https://news.ycombinator.com/item?id=32472189 that states the same thing, but nothing more
Sounds like a naive implementation of delta state CRDT. I mean, what if the author has this major epiphany that it's nice to sync states to get convergence?
ctrl+x
ctrl+v
Good luck
I think you could batch these things though. You just need a slightly more advanced protocol. If B is the first id, and L is the last, create range(B, L) as R and insert R after L (assuming Ctrl-v a second time).
I think that's the point: conceptually it's a co-op, but the implementation forces each character to be individually removed following a ctrl-x, and then individually inserted back (after issuing a new UUID) following a ctrl-v.
Now, the outcome of neither a Ctrl+x nor a Ctrl+v is atomic, which means communicating each character operation through the wire takes time. In turn this means that this is a scenario where conflicts will take place (someone is editing text midway through another user does ctrl-a,ctrl-x) and where the choice of operation will result in important user impacts.
This is a basic test scenario of CRDTs, and why research focuses on higher-level operations instead of atomic character-level operations.
It should be noted that ctrl-a,ctrl-x,ctrl-v is an extreme case of a very frequent operation: copying and pasting text. Editor-level undo/redo can manifest the same way, too.
I implemented this in a decentralized context and as a CRDT though, so that the properties hold (commutative, idempotent and associative).
The motivating examples (update validation, partial loading, higher-level operations) are interesting, but I don't see a strong case that the reason Yjs etc. lack these features is the underlying CRDT implementation, as opposed to these features being intrinsically difficult to build.
Totally agree. I guess an array of "atomic" objects, where the properties of the objects can't be changed can be done just by replacing the string with your own type. Changes inside of the object is probably trickier, but maybe it's just about efficiently storing/traversing the tree?
I've also always thoguth it should be possible to create something where the consumer of the helper library (per OP terminology) can hook in their own lightweight "semantic model" logic, to prevent/manage invalid states. A todo item can't both have isDone: true and state: inProgress at the same time. Similar to rich text formatting semantics mentioned in the linked article.
Imagine if every git merge conflict you got was resolved automatically by picking one side. Most of the time it would do the wrong thing, sometimes even leading to code that fails to compile. Imagine then you were not there ready to fix the issue, it would lead to even more chaotic results!
This is why CRDTs are not more widespread, because they only fix the problem you think you have, not the problem you actually have, which is to fix conflicts in a way that preserves data, its validity and meaning.
And arguably they make this issue even worse because they restrict the ways you can solve these conflicts to only those that can be replicated deterministically.
I’ve been saying this for years, but there’s no reason you couldn’t make a crdt which emitted conflict ranges like git does. CRDTs have strictly more information than git when merging branches. It should be pretty easy to make a crdt which has a “merge and emit conflicts” mode for merging branches. It’s just nobody has implemented it yet.
(At this point I’ve been saying this for about 5 years. Maybe I need to finally code this up if only to demonstrate it)
Fundamentally people want something that automatically fixes conflicts, and do so the way they expect it to, but this just doesn't exist yet.
I don't get your point. The C in CRDT stands for "conflict-free". Why would a CRDT have conflict ranges?
Because all communication is between client and server, and never between clients, when the client connects to the server, the server can make sure that it first processes all of the client's local operations before sending it new remote updates.
In my experience if you are persisting your edits or document state, you have something that creates an ordering anyways. That thing is commonly an OLTP database. OLTPs are optimized for this kind of write-heavy workload and there's a lot of existing work on how to optimize them further.
But now even S3 has PUT-IF, so you could use that to create an ordering. https://docs.aws.amazon.com/AmazonS3/latest/userguide/condit...
As others in the comments argue, this is technically a CRDT (though a fully general one); also, undoing/replaying ops is itself non-trivial to implement. However, I hope this is still simpler than using a traditional CRDT/OT for each data type.
Whether the converged result is at all reasonable is a different question.
That's the whole point of CRDTs: multiple replicas of the same data structure are managed throughout many nodes, each replica is updated independently, and they all eventually converge.
The article mentions this:
> This contrasts with text-editing CRDTs, in which IDs are ordered for you by a fancy algorithm. That ordering algorithm is what differs between the numerous text-editing CRDTs, and it’s the complicated part of any CRDT paper; we get to avoid it entirely.
I can buy the idea that many apps have a central server anyway, so you can avoid the "fancy algorithm", though the server reconciliation requires undoing and replaying of local edits, so it's not 100% clear to me if that's much simpler.
For example, if your client-sent request to insert a character fails, do you just retry the request? What if an update arrived in the intervening time? (Edit: they acknowledge this case in the “Client-Side” section, the proposal is to rewind and replay, and a simpler proposal to block until the pending queue is flushed)
From a frontend vantage I feel like there may be a long tail of underspecified UI/UX edge cases, such that CRDT would be simpler overall. And how does the editor feel to use while riding the NYC subway where coverage is spotty?
In practice, it works quite well. Here's more info:
https://marijnhaverbeke.nl/blog/collaborative-editing.html https://marijnhaverbeke.nl/blog/collaborative-editing-cm.htm...
Not energy efficient but should work surprisingly well without CRDT, OT, or anything else.
Compare this to Git workflows. Git already handles merging most changes seamlessly.
Any given collaborative document will probably only see ~1k clientIds in its lifetime, so the odds of a collision are fairly low, though I'd be more comfortable with a 64-bit ID.
UUIDs/ULIDs/etc are fully distributed, you can have two clients assign an ID without coordinating with ~0% of collision.
Such an awesome approach.
AFAIK, CRDTs don’t solve semantic conflict issues.
I agree this is more practical if your service anyway run over centralised servers (aka cloud)
This is not true. One of the most basic traits of CRDTs is that updates are performed without coordination. Relying on a central server to coordinate conflict resolution rejects two of the main traits of CRDTs.
There is a name-drop, but there is no substance.