[deleted]
CRDT Benchmarks
41–49 of 49 posts
Re: CRDT Benchmarks
#42[deleted]
Re: CRDT Benchmarks
#43Earlier quoted context omitted.
This is a great analogy for something I've struggled to put into words. I’ll add: if you have invariants, you almost by definition have conflicts. The C in CRDT is for conflict-free, so if you can have conflicts in the data domain you probably want something that can preserve them (like state machine synchronization) rather than a CRDT.
A CRDT (well, an operation based crdt) has all the information it needs to tell that conflicts have occurred, and which operations caused them. Something I’ve wanted for awhile is a crdt which can use that information to place the data in a “conflict” state. We can do this today with keys / values pretty easily with “MV (multi value) Registers”. If two writers concurrently set the value, the next read can see both va…
I’m having trouble visualizing how a conflicted state might work. We still have to produce a valid state for the next edit to work on. Do you mean supplying conflict resolution handlers?
Also, do you mean a conflict from the perspective of “malformed data structures” or “domain invariant violated”?
Re: CRDT Benchmarks
#44Earlier quoted context omitted.
But a JSON CRDT is in a sense a string with a particular grammar... However, my intuition ends here. You could probably model the operations on a particular document structure at a higher level and try to find a simpler domain where it's easier handling logical merges, but it sounds like something that quicky becomes too complex
A “json crdt” doesn’t edit a string containing json grammar. That’s a misleading idea. Instead, a json crdt stores a tree of values. Values can be lists / strings / numbers / maps / etc. Operations modify that tree of data - maybe by setting a key in an object (map). That set operation will be replicated to other peers. Or by inserting into a list, or editing a text document. When conflicting writes happen to a key i…
Perhaps relating to your other comment; is it theoretically possible to inject yourself into this logic? I.e., extend a general CRDT to be a domain specifc one, and do custom resolution before the "truth" is established?
Re: CRDT Benchmarks
#45Earlier quoted context omitted.
A “json crdt” doesn’t edit a string containing json grammar. That’s a misleading idea. Instead, a json crdt stores a tree of values. Values can be lists / strings / numbers / maps / etc. Operations modify that tree of data - maybe by setting a key in an object (map). That set operation will be replicated to other peers. Or by inserting into a list, or editing a text document. When conflicting writes happen to a key i…
Perhaps relating to your other comment; is it theoretically possible to inject yourself into this logic? I.e., extend a general CRDT to be a domain specifc one, and do custom resolution before the "truth" is established?
Can you give some examples of what sort of domain specific rules you want to apply?
The trick is coming up with rules that let you merge concurrent edits in a consistent way on all peers, regardless of the order that any changes come in. Some things are easy - Max() is a valid CRDT. But lots of stuff is much harder than it sounds.
Re: CRDT Benchmarks
#46Author of Diamond types (and the data sets you’re using) here! Congratulations on getting this insane performance. I’d love to know how you’re doing it - that’s truly excellent work. I didn’t know it was even possible to get javascript to go that fast on this problem. And I say that as someone who has thought about crdt / text performance way more than is reasonable. RIP my morning. I’m going to have to pour through…
A sneak peak to some future blogpost, this is what happens when "OOD " is inserted into "GG WP" to get "GOOD G WP": https://appsets.jsonjoy.com/blogposts/list-crdt-internals/wi...
Can't wait for the future blogpost! I got the Rope text data structure both from the pic, and from the data structure in AbstractRga, but am unsure of the identifier table, I am guessing thats the ID -> Chunks binary tree.
Re: CRDT Benchmarks
#47Earlier quoted context omitted.
A sneak peak to some future blogpost, this is what happens when "OOD " is inserted into "GG WP" to get "GOOD G WP": https://appsets.jsonjoy.com/blogposts/list-crdt-internals/wi...
Can't wait for the future blogpost! I got the Rope text data structure both from the pic, and from the data structure in AbstractRga, but am unsure of the identifier table, I am guessing thats the ID -> Chunks binary tree.
Subscribe to our mailing list to not miss it: https://jsonjoy.substack.com/
Re: CRDT Benchmarks
#48Author of Yjs here. I'm all for faster data structures. But only benchmarking one dimension looks quite fishy to me. A CRDT needs to be adequate at multiple dimensions. At least you should describe the tradeoffs in your article.
The time to insert characters is the least interesting property of a CRDT. It doesn't matter to the user whether a character is inserted within .1ms or .000000001ms. No human can type that fast.
It would be much more interesting to benchmark the time it takes to load a document containing X operations. Yjs & Yrs are pretty performant and conservative on memory here because they don't have to build an index (it's a tradeoff that we took consciously).
When benchmarking it is important to measure the right things and interpret the results somehow so that you can give recommendations when to use your algorithm / implementation. Some things can't be fast/low enough (e.g. time to load a document, time to apply updates, memory consumption, ..) other things only need to be adequate (e.g. time to insert a character into a document).
Unfortunately, a lot of academic papers set a bad trend of only measuring one dimension. Yeah, it's really easy to succeed in one dimension (e.g. memory or insertion-time) and it is very nice click-bait. But that doesn't make your CRDT a viable option in practice.
I maintain a set of benchmarks that tests multiple dimensions [1]. I'd love to receive a PR from you.
Re: CRDT Benchmarks
#49Earlier quoted context omitted.
Can't wait for the future blogpost! I got the Rope text data structure both from the pic, and from the data structure in AbstractRga, but am unsure of the identifier table, I am guessing thats the ID -> Chunks binary tree.
Subscribe to our mailing list to not miss it: https://jsonjoy.substack.com/
Any ETA on the blog post?