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

71–80 of 86 posts

Re: Collaborative Text Editing Without CRDTs or OT

#71

Post by SkiFire13 »

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…

That might be an improvement over git, but not automatically fixing the conflicts will be a dealbreaker for most people.

Fundamentally people want something that automatically fixes conflicts, and do so the way they expect it to, but this just doesn't exist yet.

Re: Collaborative Text Editing Without CRDTs or OT

#72

Post by practal »

Ok, so the main point that makes it different from CRDTs seems to be: if you have a central server, let the server do the synchronization (fixing an order among concurrent events), and not the data structure itself via an a-priori order.

Because all communication is between client and server, and never between clients, when the client connects to the server, the server can make sure that it first processes all of the client's local operations before sending it new remote updates.

Re: Collaborative Text Editing Without CRDTs or OT

#73

Post by [deleted] »

rendaw wrote: post #59
sdeframond wrote: post #40

Earlier quoted context omitted.

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?

[deleted]

Re: Collaborative Text Editing Without CRDTs or OT

#74

Post by lewisjoe »

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)

Re: Collaborative Text Editing Without CRDTs or OT

#75

Post by kamranjon »

mweidner wrote: post #48
bongodongobob wrote: post #42

Earlier quoted context omitted.

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

I wonder if you could sidestep the inefficiencies of storing ID's for every character by using redis streams to store the characters with id's "represented as delta-compressed macro nodes that are linked together by a radix tree" where the ids are "monotonically incrementing and has two parts: -. The time is in milliseconds and the counter increases for entries generated in the same milliseconds"

This would seem to avoid clashes and also compress the identifier storage in an efficient way.

https://antirez.com/news/128

Re: Collaborative Text Editing Without CRDTs or OT

#76

Post by gregoriol »

hbbio wrote: post #69

Someone should try to use a local LLM (maybe a 4b) to merge the diffs in case of conflict beyond straightforward cases... Not energy efficient but should work surprisingly well without CRDT, OT, or anything else.

How is an LLM supposed to merge the example from the article "My name is", insert "Charlie" after "is", insert "Dave" after "is"?

Re: Collaborative Text Editing Without CRDTs or OT

#77

Post by anon291 »

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…

Yeah, so this is an operational transform where the transform operation is just identity.

Re: Collaborative Text Editing Without CRDTs or OT

#78

Post by tangjurine »

rendaw wrote: post #59
sdeframond wrote: post #40

Earlier quoted context omitted.

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?

if there are multiple valid final states?

Re: Collaborative Text Editing Without CRDTs or OT

#79

Post by mweidner »

kamranjon wrote: post #75
mweidner wrote: post #48

Earlier quoted context omitted.

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

I wonder if you could sidestep the inefficiencies of storing ID's for every character by using redis streams to store the characters with id's "represented as delta-compressed macro nodes that are linked together by a radix tree" where the ids are "monotonically incrementing and has two parts: - . The time is in milliseconds and the counter increases for entries generated in the same milliseconds" This would seem to…

This sounds similar to the idea behind articulated (though with ids UUID-counter instead of time-counter): https://github.com/mweidner037/articulated

I will check out Antirez.

Re: Collaborative Text Editing Without CRDTs or OT

#80

Post by motorest »

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?

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

Yes. This article reads like the adage "a month in a lab saves you an hour in a library".

Post reply on HN