Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

OT and CRDT trade-offs for Real-Time collaboration

tiny.cloud

Post reply on HN
Print view View original

41–50 of 60 posts

Re: OT and CRDT trade-offs for Real-Time collaboration

#41

Post by josemaenzo »

marknadal wrote: post #37
josemaenzo wrote: post #27

Earlier quoted context omitted.

Do you have any document that explain what resolution algorithm uses in what cases? For example, one peer change a property value and the other peer deletes it.

Same algorithm for everything. This cartoon explains it: https://gun.eco/distributed/matters.html It is a vector + timestamp + lexical sort. A delete is changing a value to `null`, it would lose (I assume you are asking if/when these 2 changes happen at the exact same microsecond time, conflicting?) as is it has a lower lexical rank.

Can you refer me to a document where you explain the "lexical rank" that you are referring to?

The cartoon explanation do not tackle those terms.

Re: OT and CRDT trade-offs for Real-Time collaboration

#42

Post by marknadal »

josemaenzo wrote: post #41
marknadal wrote: post #37

Earlier quoted context omitted.

Same algorithm for everything. This cartoon explains it: https://gun.eco/distributed/matters.html It is a vector + timestamp + lexical sort. A delete is changing a value to `null`, it would lose (I assume you are asking if/when these 2 changes happen at the exact same microsecond time, conflicting?) as is it has a lower lexical rank.

Can you refer me to a document where you explain the "lexical rank" that you are referring to? The cartoon explanation do not tackle those terms.

JSON.stringify('a') https://en.wikipedia.org/wiki/Lexicographical_order

Re: OT and CRDT trade-offs for Real-Time collaboration

#43

Post by josemaenzo »

marknadal wrote: post #42
josemaenzo wrote: post #41

Earlier quoted context omitted.

Can you refer me to a document where you explain the "lexical rank" that you are referring to? The cartoon explanation do not tackle those terms.

JSON.stringify('a') https://en.wikipedia.org/wiki/Lexicographical_order

Cool! Make sense.

Let's say our state have an array like ['a','b'].

What about if Peer-A splice the first element (0) which results in ['b'] and Peer-B wants to mutate 'a' to 'A' which results in ['A','b'] and they both make the mutation at the same millisecond?

Re: OT and CRDT trade-offs for Real-Time collaboration

#44

Post by spyder81 »

phedkvist wrote: post #31

Thanks for linking to my blog post :) "This is the exact "split node" scenario I described earlier; applying bold near the start of a text node necessarily has to split the text node into three parts (before, bold, and after)." Not sure why you split it up into sections. In my CRDT implementation, I would add meta-data to each character, with the boolean property which is either bold or not. It's certainly cumbersome…

I definitely read a few of your posts during my research, thanks for your hard work :)

The best CRDTs do treat each character separately (as I think I mentioned at one point?). But not all of them - the video and my example is an example of one that doesn't.

It's also very difficult to support arbitrary nested trees with a per-character data type, which leads to the compromises I talked about.

Re: OT and CRDT trade-offs for Real-Time collaboration

#45

Post by spyder81 »

phsource wrote: post #12

Wanderlog ( https://wanderlog.com ) is a Google Docs for planning travel, and naturally, we had to figure this out early in the process. If you're on a Node.js/React stack, we highly recommend using the combination of OT-JSON0 [1] and ShareDB [2], two excellent libraries. OT-JSON0 lets you perform operational transforms on any JSON-serializable structure pretty intuitively, and ShareDB handles synchronizing it betwee…

I'll cover this in the second post but we will be using ShareDB for our initial launch (although probably building our own once we hit production release).

Re: OT and CRDT trade-offs for Real-Time collaboration

#46

Post by spyder81 »

migueloller wrote: post #34
phsource wrote: post #12

Wanderlog ( https://wanderlog.com ) is a Google Docs for planning travel, and naturally, we had to figure this out early in the process. If you're on a Node.js/React stack, we highly recommend using the combination of OT-JSON0 [1] and ShareDB [2], two excellent libraries. OT-JSON0 lets you perform operational transforms on any JSON-serializable structure pretty intuitively, and ShareDB handles synchronizing it betwee…

We’re actually using ShareDB at Makeswift right now and for us it has become a horrible burden. There are very subtle bugs on their data persistence layer with concurrency and the API is a bit of a mess to work with in my opinion. I’m glad to see other people are having success with it, though.

I've been given advice that ShareDB is "pretty antiquated and not well supported". I'm told it is not difficult to rewrite in modern NodeJS, replacing things like callbacks and event emitters with async/await produces a much simpler and more reliable server.

Re: OT and CRDT trade-offs for Real-Time collaboration

#47

Post by spyder81 »

codebeaker wrote: post #23
ergl wrote: post #19

Earlier quoted context omitted.

No, the state of the art CRDT solution for json is something like Automerge ( https://github.com/automerge/automerge ), that treats the document like a collection/combination of CRDTs of different types. (the author doesn't mention it explicitly, but it's linked at the end)

I have been using Automerge recently for a project, and I have found it to be very, very user-friendly. Our use-case is offline-editing of documents with an eventual sync-with-yourself-online. It's mostly there as a sync tool, not as a p2p colalb editing. Unless you count yourself as a peer, I guess! We store a document in local storage which is the result of `Automerge.save(automergedoc) => serializable string`. Tha…

I'm a big fan of Automerge, I look forward to where the research takes it!

Re: OT and CRDT trade-offs for Real-Time collaboration

#48

Post by spyder81 »

jiofih wrote: post #17

So.. we’re left with no real explanation to why OT is better than CRDT other than a 5s video showing a poorly managed text node update that moves the cursor. I feel tricked.

I wasn't really trying to say OT is better than CRDT. Nor was I intending to provide a complete detailed explanation (there's enough research already).

I was driving at CRDT not being capable enough for arbitrary HTML structures, and giving a quick summary of what was an extended multi-week research process.

Re: OT and CRDT trade-offs for Real-Time collaboration

#49

Post by spyder81 »

eudoxus wrote: post #32
Vinnl wrote: post #30

Earlier quoted context omitted.

Huh, the article gave me the impression that preserving the position was a crucial problem there. As for the last question, I think the later posts will get to that.

Preserving the position of the cursor is a crucial feature for collab editors. However, he doesnt go into detail explaining why CRDTs make this feature impossible. Sure the CRDT route splits the text, but I fail to see why that makes cursor pos preservation impossible?

It's not impossible, particularly in cases where the model is fairly flat.

In complex models it is symptomatic of a larger issue with complexity in CRDTs; the post was already quite long and I didn't want to repeat any more of the research I'd linked to.

Re: OT and CRDT trade-offs for Real-Time collaboration

#50

Post by spyder81 »

lxpz wrote: post #26

> the prospect of peer-to-peer editing with end-to-end encryption is an exciting one Have you heard of CryptPad ? Not exactly peer-to-peer but has encryption so that the server sees nothing.

I haven't! This is what our server team is looking at as an option for encrypting our RTC traffic.

https://tweetnacl.js.org/ https://github.com/dchest/tweetnacl-js/wiki/Examples

Post reply on HN