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

Faster CRDTs: An Adventure in Optimization

josephg.com

Post reply on HN
Print view View original

141–150 of 154 posts

Re: Faster CRDTs: An Adventure in Optimization

#141

Post by josephg »

tekkk wrote: post #127
josephg wrote: post #109

Earlier quoted context omitted.

> Which version produces nicer results when two very diverged documents are merged. From the user’s perspective merging behaviour is basically identical in all of these systems. Diamond supports full per character change tracking. So you know who authored what. I think Yjs does this too. I’m not sure what you mean about materialising areas differently? I’d like to have full branch support in diamond at some point too…

From the user’s perspective merging behaviour is basically identical in all of these systems. Ah, ok. Neat. I’m not sure what you mean about materialising areas differently? I meant finding the ranges of the document that have been changed relative to snapshot x and showing them based on the user id who changed them. If that can be done in real-time as the changes come in that would be really impressive.

Ah. Yeah that’s doable. Diamond stores the client ID which authored each character in the document and I have a method for finding out which changes exist in one version but not in another. That would be doable

Re: Faster CRDTs: An Adventure in Optimization

#142

Post by josephg »

archagon wrote: post #138
josephg wrote: post #41

Earlier quoted context omitted.

Yep, this is the best practical advice at the moment. Well, for list CRDTs. State CRDTs (like a counter) are small and fast, and kinda better than OT in every way. List ("operation based") CRDTs and OT systems are "equivalent" in a very academic sense that nobody really talks about or understands. Its really not obvious unless you've been staring at this stuff for years but the equivalence is there: You can make a CR…

> OT systems have one big advantage which is that you don't have to ship the CRDT state to every peer... You can also have a hybrid server, which talks CRDT to full peers on the network but just does OT when talking to browser clients and things like that. Could you clarify what you mean? Assuming your CRDT is defined in terms of "operations" that contain (at minimum) an identifier+sequence tuple, zero or more refere…

Yes, my point was that the peer needs to translate a user’s insert of “insert f at position 3” into “insert f between ID B2 and B3”. To do that, you need the “crdt chum” - you basically need that peer to know the ID of every item in the document. This data compresses well, but it’s still annoying to ship around and complex to manage. OT doesn’t need any of that.

Re: Faster CRDTs: An Adventure in Optimization

#143

Post by josephg »

conaclos wrote: post #128
josephg wrote: post #70

Earlier quoted context omitted.

Cool! It'd be interesting to see those CRDT implementations added to Kevin Jahns' CRDT Benchmarks page[1]. The LogootSplit paper looks interesting. It looks like xray is abandoned, and I'm not sure about teletype. Though teletype's CRDT looks to be entirely implemented in javascript[2]? If the authors are around I'd love to see some benchmarks so we can compare approaches and learn what actually works well. And I'm n…

Yes, xray was abandoned and teletype is written in JS. I understand your point and as a researcher and engineer I know your feeling. I took some cautions by using "Some optimizations". I value engineering as much as research and I'm bothered when I heard any side telling the other side that their work is worthless. Your work and the work of Kevin Jahns are very valuable and could improve the way that researchers and…

Cool! What do you think is missing from wasm for maturity? It seems great for something like CRDTs, since the code is reasonably self contained. I hear you about rust - I'm not convinced it'll ever be as popular as java / C# / JS for exactly that reason. But rust doesn't need to be that popular for me to enjoy it, or for the people who use my software to reap the speed & safety benefits.

I'll have to take a read of LogootSplit. I suspect most / all list CRDTs can work with this approach (using a list internally and doing an insertion sort). But I don't know enough about how logoot / logootsplit works to know!

And I really hear you about writing papers taking time. That blog post we're talking about here took nearly a month of time in aggregate to write. I wrote the initial draft in about 2 days, but editing and adding diagrams and everything was exhausting. There's still more work I could have put into it before publishing - I anticipated some of the things people were confused by in this thread. But at the end of the day, published > perfect and I have code to write as well!

Re: Faster CRDTs: An Adventure in Optimization

#144

Post by omgtehlion »

dkellner_ wrote: post #126
omgtehlion wrote: post #65

Earlier quoted context omitted.

Thanks! I googled only 1 impl in Rust: https://github.com/dkellner/chronofold which seems to produce invalid results on some inputs. Actually the hard part (integration) is made of hacks there... That PoC Wiki sounds really interesting and the whole replicated.cc project! Any plans on releasing it?

May I ask which inputs produced invalid results for you and which parts you consider hacky? I'd very much like to improve the implementation, so a reply here or an issue on e.g. GitHub would be highly appreciated. Thanks!

Wow, thanks for reply!

Some time ago (~7-8months) I tried to implement a chronofold-based app myself in not so fancy language (c#). The data structure itself is very nicely described in the paper, but for merging strategy there are only references to other papers... So I tried to find it implemented in other langs, most of repos were bare bones, yours was the most complete, so I took it as a reference. I lifted the merging strategy verbatim from it, and it passed all the tests in repo plus some additional tests. But when faced a real user input strange things happened.

I will try to find exact cases and open an issue, but not today, unfortunately :(

Edit: AFAIR, I had problems with this func: https://github.com/dkellner/chronofold/blob/16773193b2d21f81... and the problem manifested itself for concurrent deletes. Plus it has reversed order for consecutive deletes regarding to original paper. I have not succeeded with fixing it and just scratched the whole thing and used a simpler (yet not as performant) merging strategy...

Re: Faster CRDTs: An Adventure in Optimization

#145

Post by dkellner_ »

omgtehlion wrote: post #144
dkellner_ wrote: post #126

Earlier quoted context omitted.

May I ask which inputs produced invalid results for you and which parts you consider hacky? I'd very much like to improve the implementation, so a reply here or an issue on e.g. GitHub would be highly appreciated. Thanks!

Wow, thanks for reply! Some time ago (~7-8months) I tried to implement a chronofold-based app myself in not so fancy language (c#). The data structure itself is very nicely described in the paper, but for merging strategy there are only references to other papers... So I tried to find it implemented in other langs, most of repos were bare bones, yours was the most complete, so I took it as a reference. I lifted the m…

Don't worry, your details already help a lot! I will look into it later this week.

The published version indeed has one bug regarding inserts referencing a deleted element. Maybe that is (part of) what you saw as well. I've fixed that locally already, but unfortunately only after I've made signifant other changes which are still to be refactored & published ;-). Probably time to just backport the fix and release it.

Re: Faster CRDTs: An Adventure in Optimization

#146

Post by dkellner_ »

dkellner_ wrote: post #145
omgtehlion wrote: post #144

Earlier quoted context omitted.

Wow, thanks for reply! Some time ago (~7-8months) I tried to implement a chronofold-based app myself in not so fancy language (c#). The data structure itself is very nicely described in the paper, but for merging strategy there are only references to other papers... So I tried to find it implemented in other langs, most of repos were bare bones, yours was the most complete, so I took it as a reference. I lifted the m…

Don't worry, your details already help a lot! I will look into it later this week. The published version indeed has one bug regarding inserts referencing a deleted element. Maybe that is (part of) what you saw as well. I've fixed that locally already, but unfortunately only after I've made signifant other changes which are still to be refactored & published ;-). Probably time to just backport the fix and release it.

Well, that was a productive lunch break ;-). I've just published version 0.2.1, fixing the bug mentioned above.

Re: Faster CRDTs: An Adventure in Optimization

#147

Post by fulafel »

josephg wrote: post #2

Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia

Terminology nit: cache coherence refers to CPU cache implementation behaviours at hw level in presence of concurrent access from multiple cores. Data locality or cache friendly data layout could work better here.

Re: Faster CRDTs: An Adventure in Optimization

#148

Post by ta988 »

josephg wrote: post #107
ta988 wrote: post #62

Earlier quoted context omitted.

This was a great read, thank you. I wish there were more explanations of the "black magic" part of Yjs. I'll have to dig into that.

If you’re interested in learning more about Yjs’s internals, I interviewed Kevin for 3 hours on zoom and got him to take me through Yjs’s code. He’s a great guy. The video of that conversation is here: https://youtu.be/0l5XgnQ6rB4

Thanks a lot. Thats on my video queue.

Re: Faster CRDTs: An Adventure in Optimization

#150

Post by drewmccormack »

josephg wrote: post #108
lewisl9029 wrote: post #100

Earlier quoted context omitted.

First of all, thank you for the amazing read! I thoroughly enjoyed the entire article, and it gave me a new perspective on the feasibility of CRDTs for real world applications performance-wise. Though I am curious now to hear your thoughts on the conflict resolution side of the equation for complex data structures like deeply nested JSON. The biggest takeaway I got from Martin's talk on the topic from a few years ago…

I’m not sure how much the field has improved - good chance there’s some new papers I haven’t read. But I think it’s pretty doable. For all the talk of concurrent editing, the reality is that having multiple users edit the same value at the same time in most applications is incredibly rare. It’s rare enough that concurrent editing is just basically broken in most web apps and nobody seems to mind or talk about it. For…

Thanks for the great post. Indeed, as a former scientist myself, I can say you have to take everything you read with a grain of salt. I've seen inside the sausage factory, and concluded that YMMV.

> The other thing I would love to see solved is how you would add git style conflicts into a crdt. The best effort merging strategy of most OT & CRDT systems is fine for real-time editing but it isn’t what you want when merging distant branches.

I found this comment very interesting. I have been playing with the idea of 3-way merging CRDTs, similar to the git approach. Have even used this type of branching in commercial software I work on for handling concurrent changes to files.

Be very interested to know if any efforts are being made on this in the CRDT community. (I'm more of an interested onlooker. I use a lot of the same concepts in my software, but not rigorously.)

Post reply on HN