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

101–110 of 154 posts

Re: Faster CRDTs: An Adventure in Optimization

#101

Post by josephg »

trishume wrote: post #71
josephg wrote: post #2

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

Have you seen my Xi CRDT writeup from 2017 before? https://xi-editor.io/docs/crdt-details.html It's a CRDT in Rust and it uses a lot of similar ideas. Raph and I had a plan for how to make it fast and memory efficient in very similar ways to your implementation. I think the piece I got working during my internship hits most of the memory efficiency goals like using a Rope and segment list representation. However we p…

Oooohhhh no I haven’t read that - thanks for the link! I feel embarrassed to say this but I knew about Xi editor years ago but I totally forgot to go read & learn about your crdt implementation when I was learning about Yjs and automerge and others. I’ll have a read.

And thanks for writing such an in depth article. It’s really valuable going forward. Maybe it’s addressed in your write up but are there any plans for that code, or has everyone moved on? I’d love to have a zoom chat about it and hear about your experiences at some point if you’d be willing.

Re: Faster CRDTs: An Adventure in Optimization

#102

Post by toomim »

lewisjoe wrote: post #61

People who are interested in the topic: I just found out they have open meetings about the parent project and seems like anybody could join - https://braid.org/ Great way to share progress. Kudos! :)

Yep! Our next meeting is in two Mondays from now on August 2nd, at 4:00pm Pacific Time. All are welcome: https://braid.org/meeting-16

Re: Faster CRDTs: An Adventure in Optimization

#103

Post by shrimpx »

zladuric wrote: post #91
JW_00000 wrote: post #81

By the way, as someone who has published academic papers, if you're ever bothered about a paper or have some comments, don't hesitate to mail the authors. (Their e-mail addresses are always on the paper; especially target the first author because they have normally done the work.) We are happy to hear when someone has read our work and I at least would've liked to have known if someone found a problem with my papers.

> especially target the first author because they have normally done the work As someone living with a recently promoted? (is that the correct term?) PhD in social sciences, this surprises me. Is that something specific for my country, for social sciences or my wife simply landed in a case full of rotten apples?

In computer science the first author does the work and is usually a PhD student. The last author is usually the professor that pushed and helped develop the idea, provided funding, and probably wrote or was heavily involved in writing the paper’s abstract, intro and conclusion sections — the bulk of “framing” the work.

But there are exceptions. Some profs are less student-oriented or don’t like delegating so much, and remain “individual contributors” deep in their careers. Those tend to publish nonzero number of first- and single-author papers.

Edit: I’ve noticed that in Theory and Algorithms, profs tend to take first author even though the student slaved out the proofs. That field is kind of an outlier in that it’s close pure math, and I think borrows cultural artifacts from math research.

Re: Faster CRDTs: An Adventure in Optimization

#104

Post by [deleted] »

shrimpx wrote: post #103
zladuric wrote: post #91

Earlier quoted context omitted.

> especially target the first author because they have normally done the work As someone living with a recently promoted? (is that the correct term?) PhD in social sciences, this surprises me. Is that something specific for my country, for social sciences or my wife simply landed in a case full of rotten apples?

In computer science the first author does the work and is usually a PhD student. The last author is usually the professor that pushed and helped develop the idea, provided funding, and probably wrote or was heavily involved in writing the paper’s abstract, intro and conclusion sections — the bulk of “framing” the work. But there are exceptions. Some profs are less student-oriented or don’t like delegating so much, an…

[deleted]

Re: Faster CRDTs: An Adventure in Optimization

#105

Post by josephg »

pookeh wrote: post #78
josephg wrote: post #2

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

Wait it doesn't look like you used the performance branch of automerge (which is now merged into master). It is significantly faster. https://github.com/automerge/automerge/pull/253

I did use the performance branch. And I had a chat with a few people in the automerge community about the performance numbers I was seeing long before I published to see if I was doing anything wrong. I tested a few different versions of automerge but in this test there wasn’t much performance difference between 0.12, 1.0.x-preview versions (which are built from the merged performance branch) and I tried the unreleased automerge-rs. When I ran my tests timing numbers for automerge ranged from about 5m with the old non performance branch down to about 4m20s or so with automerge-rs. Still far from Yjs’s 0.9 seconds.

I just checked and it looks like automerge 1.0.1-preview-4 has landed. I wrote the post benchmarking preview-2. I’ve been knee deep in diamond types lately and haven’t been watching. Fingers crossed there’s some more performance improvements in the pipeline. I’d love to do a follow up in 6 months showing much improved performance.

Re: Faster CRDTs: An Adventure in Optimization

#106

Post by josephg »

jg23 wrote: post #76
josephg wrote: post #36

Earlier quoted context omitted.

I didn't explain this well but the transformation is lossless. No data is lost from compressing like this. It has no impact on the concurrency protocol or network protocol; it just impacts how the data is stored locally. If we need to, we could split the run back out again into individual characters without losing information. And that does happen - we do that if something later gets inserted into the middle of the r…

I have a related question to this, if you’re storing [“hello”] as one chunk, what happens when you perform an edit to say adding an extra [“e”] after the [“e”]? In the unoptimised structure I know you can just add the new [“e”] as a child of the original [“e”]. So here would you then delete the chunk [“hello”] and split it into two halves like [“he”] and [“llo”]?

Yes exactly. You replace the chunk with “he” and “llo” then insert the extra item in the middle. The result is [“he”, “e”, “llo”]. The code to do all this inline in a b-tree is pretty hairy but it works pretty well!

Re: Faster CRDTs: An Adventure in Optimization

#107

Post by josephg »

ta988 wrote: post #62
josephg wrote: post #2

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

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

Re: Faster CRDTs: An Adventure in Optimization

#108

Post by josephg »

lewisl9029 wrote: post #100
josephg wrote: post #63

Earlier quoted context omitted.

> Today, it seems one would still have to transform that data to a large flat string underneath, and implement an editor that only performs edits that maintain the integrity of the higher-level object, while the flat string provides collaboration features. Lots of people think this and have mentioned it over the years, but its a dangerous idea. The way concurrent edits are handled makes it really easy for the automat…

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 structured / database data, the best effort merges of current systems (or doing simple last writer wins stuff) is a fine solution in 95% of applications.

But ideally we want something like the semantics of ot-json-1 [1] which supports arbitrary move operations. This is necessary if you wanted to implement a program like workflowy on top of a crdt. Martin thinks this is possible in a crdt by sort of embedding part of an OT system and doing transform, but I don’t feel very satisfied with that answer either.

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.

Automerge today supports arbitrary json data, inserts, deletes and local moves. I think that’s plenty for the data model in 99% of software. I think most software that fits well into a classical database model should be reasonably straightforward to adapt.

I’m not sure if that answers your question but yeah, I’m thinking about this stuff too.

[1] https://github.com/ottypes/json1

Re: Faster CRDTs: An Adventure in Optimization

#109

Post by josephg »

tekkk wrote: post #82

Excellent article! As someone who has to work with collaborative editing I must say the complexity of the whole area is at times daunting to say the least. So many edge-cases. So many mines to step on. Now I think I am convinced that the OT vs CRDT performance comparison is kind of moot point and the question is more about the user experience. Which version produces nicer results when two very diverged documents are…

> 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, so you can work in a branch, switch branches, merge branches, and all of that.

Re: Faster CRDTs: An Adventure in Optimization

#110

Post by sagichmal »

detaro wrote: post #51
Jailbird wrote: post #50

Earlier quoted context omitted.

Drifting off-topic but I've wondered this myself - I've been interested in CRDTs in a "read the news" way but not a "this rises to something I'm going to implement" way. Perhaps it's blindingly obvious to all here, so no one mentions it: Thinking about more practical and real-world problems seems like collaboration on on more complex/structured data. Today, it seems one would still have to transform that data to a la…

CRDT is a general concept, editing text is just one possible application. If you have a stronger datatype, great, you can build operations on top of it to implement a CRDT system, depending on its properties.

It would be a little bit strange to build a CRDT system on top of a more traditional data system. CRDTs solve problems at the network layer at enormous cost basically everything else. If you're not using them there, I can't quite understand what they're doing for you?
Post reply on HN