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

81–86 of 86 posts

Re: Collaborative Text Editing Without CRDTs or OT

#81

Post by motorest »

apgwoz wrote: post #60
pcthrowaway wrote: post #49

Earlier quoted context omitted.

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

> Isn’t this a NOP?

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.

Re: Collaborative Text Editing Without CRDTs or OT

#82

Post by motorest »

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…

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

I don't get your point. The C in CRDT stands for "conflict-free". Why would a CRDT have conflict ranges?

Re: Collaborative Text Editing Without CRDTs or OT

#83

Post by motorest »

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?

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

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.

Re: Collaborative Text Editing Without CRDTs or OT

#84

Post by motorest »

lewisjoe wrote: post #74

This is technically a CRDT. It's just that the "order of operations" to apply over the doc is now resolved using a central server. For context, this is exactly how Google Docs and Zoho Writer works currently. Except that, they use OT with central-server based reconciliation and the proposal uses CRDT-istic approach. I agree this is more practical if your service anyway run over centralised servers (aka cloud)

> This is technically a CRDT. It's just that the "order of operations" to apply over the doc is now resolved using a central server.

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.

Re: Collaborative Text Editing Without CRDTs or OT

#85

Post by josephg »

motorest wrote: post #82
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…

> 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. I don't get your point. The C in CRDT stands for "conflict-free". Why would a CRDT have conflict ranges?

Because automatic merging isn’t always perfect. Especially when merging long lived changes to code in git, sometimes you need manual intervention to figure out the result. And we need to manually intervene sometimes.

Re: Collaborative Text Editing Without CRDTs or OT

#86

Post by nextaccountic »

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

> Like Raft is a "special case" of Paxos

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

Post reply on HN