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

51–60 of 86 posts

Re: Collaborative Text Editing Without CRDTs or OT

#51

Post by bikeshaving »

jahewson wrote: post #45
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.

Any algorithm that uses a central server as a tie-breaker could easily be replaced by one where client ids are used for the tie-breaker.

Re: Collaborative Text Editing Without CRDTs or OT

#52

Post by eiginn »

jahewson wrote: post #45
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.

I miss Wave a lot, very quirky in a good way imo. We ran a few D&D games over it. RIP

Re: Collaborative Text Editing Without CRDTs or OT

#53

Post by mweidner »

math_dandy wrote: post #47
mweidner wrote: post #31

Earlier quoted context omitted.

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”?

A decentralized, eventually consistent total order on operations is a fully general CRDT, in the sense that you can put whatever (deterministic) operations you want in the total order and clients will end up in eventually consistent states.

Whether the converged result is at all reasonable is a different question.

Re: Collaborative Text Editing Without CRDTs or OT

#54

Post by thebeardisred »

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?

I really want to believe you were trying to make a reference to cap'n jazz - https://en.m.wikipedia.org/wiki/Cap'n_Jazz

:)

Re: Collaborative Text Editing Without CRDTs or OT

#55

Post by yubblegum »

thebeardisred wrote: post #54
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?

I really want to believe you were trying to make a reference to cap'n jazz - https://en.m.wikipedia.org/wiki/Cap'n_Jazz :)

Never heard of them

:(

Re: Collaborative Text Editing Without CRDTs or OT

#56

Post by math_dandy »

mweidner wrote: post #53
math_dandy wrote: post #47

Earlier quoted context omitted.

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

A decentralized, eventually consistent total order on operations is a fully general CRDT, in the sense that you can put whatever (deterministic) operations you want in the total order and clients will end up in eventually consistent states. Whether the converged result is at all reasonable is a different question.

Ok, now I understand your reply. In retrospect, you were being perfectly clear all along and my confusion was due to me not appreciating the precise definition of a CRDT. Thanks!

Re: Collaborative Text Editing Without CRDTs or OT

#57

Post by criddell »

shermantanktop wrote: post #30
criddell wrote: post #28

Earlier quoted context omitted.

Could it? If you and I are simultaneously editing a list of people and you are trying to order them by age and I'm ordering them alphabetically, we are still going to have to reconcile the result.

By that definition, it's not a solvable problem, is it?

I don’t think so.

AFAIK, CRDTs don’t solve semantic conflict issues.

Re: Collaborative Text Editing Without CRDTs or OT

#58

Post by jonstokes »

bikeshaving wrote: post #51
jahewson wrote: post #45

Earlier quoted context omitted.

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

Any algorithm that uses a central server as a tie-breaker could easily be replaced by one where client ids are used for the tie-breaker.

If you used UUIDv7 you get time-ordered UUID and could use that for a tie breaker.

Re: Collaborative Text Editing Without CRDTs or OT

#59

Post by rendaw »

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.

How do you determine which operations are concurrent?

Re: Collaborative Text Editing Without CRDTs or OT

#60

Post by apgwoz »

pcthrowaway wrote: post #49
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

Isn’t this a NOP?

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

Post reply on HN