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! :)
Faster CRDTs: An Adventure in Optimization
61–70 of 154 posts
Re: Faster CRDTs: An Adventure in Optimization
#62Hello 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.
Re: Faster CRDTs: An Adventure in Optimization
#63Earlier quoted context omitted.
Have you used CRDTs to solve any practical problems? If so, how does the CRDT solution compare to a non-CRDT solution? If a non-CRDT solution is feasible at all?
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…
> 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 automatic merging algorithms to mess up the syntax of your XML / JSON content. And thats really hard for non-programmers to fix.
The right answer for this stuff is to just make CRDTs which support other data types, the same way we did for OT with ot-types[1]. We need CRDT code for lists + text (working now - text is just a list of characters). And rich-text and JSON. And that'd cover 99% of the use cases. I'm tackling strings first in diamond-types because its probably the hardest case; but I want to have native support for other data structures soon too.
Yjs and automerge already do this. They have support for plain text, XML and arbitrary JSON structures.
The simplest implementation for JSON structures + tuples is probably shelf[2], which is so simple you can implement it in about 25 lines of javascript. Shelf doesn't support lists, but combining shelf with the list code I already have in diamond-types is probably going to be good enough for most applications.
[1] https://github.com/ottypes/
[2] Shelf's description + code is here: https://braid.org/algorithms/shelf . Or you can watch the video of Greg (shelf's author) discussing the algorithm here: https://braid.org/meeting-8 . Kevin Jahns (Yjs's author) is in that recording too, and he's super jazzed about how simple and beautiful shelf is.
Re: Faster CRDTs: An Adventure in Optimization
#64Earlier quoted context omitted.
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.
What I've read talks about character insertion and concepts that apply to editing text. Perhaps I just need to find bedrock to build up from about the properties of a stronger datatype that allow CRDTs to work.
https://arxiv.org/pdf/1805.06358.pdf looks like a decent starting point, with references to work on other types.
Re: Faster CRDTs: An Adventure in Optimization
#65Earlier quoted context omitted.
That is nice! A couple of questions: Do you have released a CT implementation in top of Chronofold? Have you any plans to benchmark it against other algs?
Thanks. No, I didn't release it, although there are implementations on GitHub. Rust and Kotlin, at least. The RON proof-of-concept wiki runs on the (unreleased) C++ implementation [1]. I benchmarked it at some point, everything was like "k nanoseconds" [2]. [1]: http://doc.replicated.cc/%5EWiki/ron.sm [2]: https://github.com/dmonad/crdt-benchmarks/issues/3#issue-599...
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?
Re: Faster CRDTs: An Adventure in Optimization
#66Earlier quoted context omitted.
What I've read talks about character insertion and concepts that apply to editing text. Perhaps I just need to find bedrock to build up from about the properties of a stronger datatype that allow CRDTs to work.
https://arxiv.org/pdf/1805.06358.pdf looks like a decent starting point, with references to work on other types.
and pointers to other papers, too - thanks!
Re: Faster CRDTs: An Adventure in Optimization
#67Earlier quoted context omitted.
Thanks. No, I didn't release it, although there are implementations on GitHub. Rust and Kotlin, at least. The RON proof-of-concept wiki runs on the (unreleased) C++ implementation [1]. I benchmarked it at some point, everything was like "k nanoseconds" [2]. [1]: http://doc.replicated.cc/%5EWiki/ron.sm [2]: https://github.com/dmonad/crdt-benchmarks/issues/3#issue-599...
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?
Here is Kotlin https://github.com/decentralized-hse/collab-edit
libron will be released, yes.
Re: Faster CRDTs: An Adventure in Optimization
#68Earlier quoted context omitted.
Have you used CRDTs to solve any practical problems? If so, how does the CRDT solution compare to a non-CRDT solution? If a non-CRDT solution is feasible at all?
Article mentions at the beginning that the author used CRDT in Google Wave/ShareJS.
My mistake, it says OT was used, thank you for correcting me.
Re: Faster CRDTs: An Adventure in Optimization
#69About a decade ago, I implemented the Causal Tree CRDT (aka RGA, Timestamped Insertion Tree) in regular expressions using a Unicode string as a storage. Later we made a collaborative editor for Yandex based on that code. It used many of the tricks as described in the text, even the optimization where you remember the last insertion point. So I am terribly glad it all gets rediscovered. The code is on GitHub [1] There…
I remember seeing that (regex CTs) and immediately thinking "wtf, why would anyone want to do that". Took me quite a while to understand that it's actually a pretty clever way to write fast state machines in browserland. So thank you for this work!
Re: Faster CRDTs: An Adventure in Optimization
#70Hello HN! Post author here. I’m happy to answer questions & fix typos once morning rolls around here in Australia
Hi josephg, I'm a CRDT researcher. This is great to see so much work around CRDT nowadays! Some optimizations whom you discuss are already proposed by some papers and implementations. For instance, LogootSplit [1] proposes an implementation based on an AVL tree with extra metadatas to get a range tree. LogootSplit proposes also a block-wise approach that stores strings instead of individual characters. Xray [2], an e…
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 not surprised these techniques have been invented before. Realising a tree is an appropriate data structure here is a pretty obvious step if you have a mind for data structures.
To name it, I often find myself feeling defensive when people read my work and respond with a bunch of links to academic papers. Its probably totally unfair and a complete projection from my side, but I hear a voice in my head reword your comment to instead say something awful like: "Cool, but everything you did was done before. Even if they didn't make any of their work practical, usable or good they still published first and you obviously didn't do a good enough literature review if you didn't know that." And I feel an unfair defensiveness arise in me as a result that wants to find excuses to dismiss the work, even if the work might be otherwise interesting.
Its hard to compare their benchmark results because they used synthetic randomized editing traces, which always have different performance profiles than real edits for this stuff. Their own university gathered some great real world data in an earlier study. It would have been much more instructive if that data set was used here. At a glance their RAM usage looks to be about 2 orders of magnitude worse than diamond-types or yjs. And their CPU usage... ?? I can't tell because they have no tables of results. Just some hard to read charts with log scales, so you can't even really eyeball the figures. So its really hard to tell if their work ends up performance-competitive without spending a couple days getting their enterprise style java code running with a better data set. Do you think thats worth doing?