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

31–40 of 86 posts

Re: Collaborative Text Editing Without CRDTs or OT

#31

Post by mweidner »

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 still simpler than using a traditional CRDT/OT for each data type.

Re: Collaborative Text Editing Without CRDTs or OT

#33

Post by Animats »

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 for display purposes, but it is still kept for "insert after" position purposes.

This might have potential outside text editing. Game world synchronization, maybe.

Re: Collaborative Text Editing Without CRDTs or OT

#35

Post by filleokus »

Footkerchief wrote: post #20

Surprised to see no discussion of other data structures like dicts/maps, or arrays of arbitrary type. Hopefully they'd be a straightforward extension. IME, apps need collaborative data structures more often than they need pure collaborative text editing. 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 th…

> Surprised to see no discussion of other data structures like dicts/maps, or arrays of arbitrary type. Hopefully they'd be a straightforward extension. IME, apps need collaborative data structures more often than they need pure collaborative text editing.

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.

Re: Collaborative Text Editing Without CRDTs or OT

#36

Post by yubblegum »

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?

Re: Collaborative Text Editing Without CRDTs or OT

#37

Post by sdeframond »

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…

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

Re: Collaborative Text Editing Without CRDTs or OT

#38

Post by ori_b »

sdeframond wrote: post #37
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…

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 and a way to unwind misordered local state, but it means that it's not a CRDT.

Re: Collaborative Text Editing Without CRDTs or OT

#39

Post by Yoric »

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…

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?

Re: Collaborative Text Editing Without CRDTs or OT

#40

Post by sdeframond »

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…

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.

Post reply on HN