Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Collaborative Text Editing Without CRDTs or OT

mattweidner.com

Post reply on HN
Print view View original

41–50 of 86 posts

Re: Collaborative Text Editing Without CRDTs or OT

#41

Post by 3cats-in-a-coat »

sdeframond wrote: post #40
ori_b wrote: post #38

Earlier quoted context omitted.

No; there is no single consistent final state that the system must converge to if the parts go offline. If you have this document: a{uuid=1} and two clients send the following operations: b{uuid=2} insert-after{uuid=1} c{uuid=3} insert-after{uuid=1} then the following two documents are both valid final states: abc acb That's fine as long as you have an authoritative server that observes all events in a single order a…

What about ordering concurrent operations by id? Then "abc" is the only consistent final state. I get what you mean though, having a central authority greatly relaxes the requirement.

We could generalize having a tree of known authorities upstream with what a CRDT does, resulting in both being two special cases of a more general consistent event processing model. CRDT makes the order of events commutative, hence the "authority" becomes a property of the math itself, rather than a physical service.

Re: Collaborative Text Editing Without CRDTs or OT

#42

Post by bongodongobob »

yubblegum wrote: post #36
Animats wrote: post #33

That is very neat. The algorithm: - 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…

Is this really that novel? I mean using a central process for serializing a distributed system is like a no brainer -- didn't we start off from here originally? -- until you have to worry about network partitions, and CAP and all that jazz. You also now have a single point of failure. Also I skimmed the thing but was performance discussed?

Yeah I have the same question. I'm not familiar with the problem space but this seems like my naive first idea so I'm wondering what the catch is.

Re: Collaborative Text Editing Without CRDTs or OT

#43

Post by ori_b »

Yoric wrote: post #39
ori_b wrote: post #38

Earlier quoted context omitted.

No; there is no single consistent final state that the system must converge to if the parts go offline. If you have this document: a{uuid=1} and two clients send the following operations: b{uuid=2} insert-after{uuid=1} c{uuid=3} insert-after{uuid=1} then the following two documents are both valid final states: abc acb That's fine as long as you have an authoritative server that observes all events in a single order a…

If you have the additional semantics that says "operation with lowest uuid gets applied first", don't you essentially get a CRDT? I mean, a uuid is kind of a poor man's Lamport clock, isn't it?

Yes, you can extend the algorithm that was described with additional semantics, and you can turn it into a CRDT.

Re: Collaborative Text Editing Without CRDTs or OT

#44

Post by YoumuChan »

ori_b wrote: post #38
sdeframond wrote: post #37

Earlier quoted context omitted.

What you describe is a CRDT, isn't it ?

No; there is no single consistent final state that the system must converge to if the parts go offline. If you have this document: a{uuid=1} and two clients send the following operations: b{uuid=2} insert-after{uuid=1} c{uuid=3} insert-after{uuid=1} then the following two documents are both valid final states: abc acb That's fine as long as you have an authoritative server that observes all events in a single order a…

Like Raft is a "special case" of Paxos, this feels like a "special case" of CRDT.

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".

Re: Collaborative Text Editing Without CRDTs or OT

#45

Post by jahewson »

Animats wrote: post #33

That is very neat. The algorithm: - 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…

This is literally a degenerate CRDT. Central server for tie-breaking goes back to Google Wave.

Re: Collaborative Text Editing Without CRDTs or OT

#46

Post by coolcase »

Is collaborative text editing with offline sync a nerd snipe [0]? I work for a big tech and write a lot and usually worse case someone else edits at the same time and the server can figure it out. yes it needs some kind of algo but most concurrent edits are on different parts of a huge doc.

Compare this to Git workflows. Git already handles merging most changes seamlessly.

[0] https://xkcd.com/356/

Re: Collaborative Text Editing Without CRDTs or OT

#47

Post by math_dandy »

mweidner wrote: post #31
math_dandy wrote: post #15

Is the take-home message of the post that the full complexity of CRDTs/OT is necessary only in the absence of a central server?

Even in the absence of a central server, you can still avoid CRDT/OT complexity if you have a decentralized way to eventually total order operations & apply them in that order: https://mattweidner.com/2025/05/21/text-without-crdts.html#d... 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 s…

Did you perhaps mean to write, “though not a fully general one”?

Re: Collaborative Text Editing Without CRDTs or OT

#48

Post by mweidner »

bongodongobob wrote: post #42
yubblegum wrote: post #36

Earlier quoted context omitted.

Is this really that novel? I mean using a central process for serializing a distributed system is like a no brainer -- didn't we start off from here originally? -- until you have to worry about network partitions, and CAP and all that jazz. You also now have a single point of failure. Also I skimmed the thing but was performance discussed?

Yeah I have the same question. I'm not familiar with the problem space but this seems like my naive first idea so I'm wondering what the catch is.

As the author, same.

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.

Re: Collaborative Text Editing Without CRDTs or OT

#49

Post by pcthrowaway »

Animats wrote: post #33

That is very neat. The algorithm: - 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…

ctrl+a

ctrl+x

ctrl+v

Good luck

Re: Collaborative Text Editing Without CRDTs or OT

#50

Post by n_u »

sampton wrote: post #27
math_dandy wrote: post #15

Is the take-home message of the post that the full complexity of CRDTs/OT is necessary only in the absence of a central server?

OT requires centralized server.

Some OTs do, some don't. OTs with the TP2 property do not require a central authority to order edits I believe.

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...

Post reply on HN