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

61–70 of 86 posts

Re: Collaborative Text Editing Without CRDTs or OT

#61

Post by motorest »

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…

> No; there is no single consistent final state that the system must converge to if the parts go offline.

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?

Re: Collaborative Text Editing Without CRDTs or OT

#62

Post by yanowitz »

jonstokes wrote: post #58
bikeshaving wrote: post #51

Earlier quoted context omitted.

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.

Don’t you have to be confident the clocks are sufficiently synced across the system?

Re: Collaborative Text Editing Without CRDTs or OT

#63

Post by boxed »

yanowitz wrote: post #62
jonstokes wrote: post #58

Earlier quoted context omitted.

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

Don’t you have to be confident the clocks are sufficiently synced across the system?

And you know.. simultaneity is not a thing in reality...

Re: Collaborative Text Editing Without CRDTs or OT

#64

Post by ChadNauseam »

boxed wrote: post #63
yanowitz wrote: post #62

Earlier quoted context omitted.

Don’t you have to be confident the clocks are sufficiently synced across the system?

And you know.. simultaneity is not a thing in reality...

It's even less of a thing in distributed systems, but you have to pick something to show the user and clocks are often good enough :D

Re: Collaborative Text Editing Without CRDTs or OT

#65

Post by SkiFire13 »

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…

CRDTs essentially work by deterministically picking one side when a conflict arises. The issue is that in general this does not guarantee the lack of data loss nor data being valid (you can resolve the conflict between two pieces of valid data and get invalid data as a result).

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.

Re: Collaborative Text Editing Without CRDTs or OT

#66

Post by josephg »

YoumuChan wrote: post #44
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…

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

Yeah. It’s also quite inefficient by default - because you’re storing deleted items and you have a uuid per character. And you usually want the other parts from a crdt which this discards. Like, a consistent ordering rule for siblings. Doing so barely adds any code (like 10 lines or so) and it makes the system way more useful.

I don’t really understand the benefit of doing this when text CRDTs are small, simple and fast.

Re: Collaborative Text Editing Without CRDTs or OT

#67

Post by josephg »

SkiFire13 wrote: post #65
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…

CRDTs essentially work by deterministically picking one side when a conflict arises. The issue is that in general this does not guarantee the lack of data loss nor data being valid (you can resolve the conflict between two pieces of valid data and get invalid data as a result). 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, som…

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

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)

Re: Collaborative Text Editing Without CRDTs or OT

#68

Post by hansworst »

josephg wrote: post #67
SkiFire13 wrote: post #65

Earlier quoted context omitted.

CRDTs essentially work by deterministically picking one side when a conflict arises. The issue is that in general this does not guarantee the lack of data loss nor data being valid (you can resolve the conflict between two pieces of valid data and get invalid data as a result). 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, som…

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

Automerge has this: https://automerge.org/automerge/api-docs/js/functions/getCon...

Re: Collaborative Text Editing Without CRDTs or OT

#70

Post by josephg »

hansworst wrote: post #68
josephg wrote: post #67

Earlier quoted context omitted.

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

Automerge has this: https://automerge.org/automerge/api-docs/js/functions/getCon...

Reading the docs, it looks like that only works for object keys that have been concurrently set to different values. Not text documents.
Post reply on HN