CRDT Benchmarks
jsonjoy.com
jsonjoy.com
Closest I've seen to that is automerge but the Python version doesn't appear to be actively maintained or packaged for PyPI yet: https://github.com/automerge/automerge-py
UPDATE: It looks like this might be what I'm after: https://github.com/y-crdt/ypy
I'm thinking about something relatively basic, let's say a shared markdown document and/or shared dataframe view of a database table?
More importantly, I prefer not to be the only user of something like this - a Rust-Python wrapper that someone else has already tried running in production is a lot more trustworthy than something I knock together myself.
> Currently we didn't have any known undefined behaviour bugs caused by [casting pointers we don't have exclusive access to to mutable references]. In the future we may want to adopt different way of working with blocks with more respect regarding borrow checker rules, but currently priority was compatibility with Yjs.
https://github.com/y-crdt/y-crdt/issues/233#issuecomment-136...
Edit: I've only played around with my own toy crdt implementations, but I think this is also completely unnecessary. Yrs has a whole transaction API for concurrently mutating the same document instance through a shared handle. Not only is it unsound but there are also a bunch of places that will just panic if called concurrently. But you can just structure your program differently. For example, you could have a single thread/task per document that all the clients connect to.
That isn't to say yrs isn't impressive. It's quite good for someone's first rust project written all at once in a short period of time. But I don't think it's production ready, and I'm skeptical it's fundamental architecture can be.
RIP my morning. I’m going to have to pour through your code to see how you’ve pulled this off. Do you have anything you recommend I read to understand how your algorithm works?
Not really, you should already know those. It is just Block-wise RGA with a tree for blocks and a tree for identifiers, also, with split link and insert-in-between optimization from Briot et. al (2016).
https://appsets.jsonjoy.com/blogposts/list-crdt-internals/wi...
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.
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 values and decide what to do about that.
But nobody (as far as I know) has yet made a crdt for code editing which uses this same trick to mark & annotate editing conflicts. And that seems like a missing piece if we want to replace git with something better.
Also, do you mean a conflict from the perspective of “malformed data structures” or “domain invariant violated”?
When conflicting writes happen to a key in a map, a good crdt will either transparently pick a “winner” (and the other write disappears) or when you read, you can read all conflicting values and your application can choose what to do.
The downside of all this is you can’t have database style transactions, so many application side data integrity constraints are hard or impossible to implement. Like, you can’t enforce a constraint that a list has < 10 values in it because the merging algorithm may merge two inserts and put the list over your limit.
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.
For use cases with a central server, you can use server reconciliation to handle “true conflicts”, essentially doing layer of OT-style ops at the application level around CRDT structures provided by a library. See how Replicache suggests handling text for example. They provide a server reconciliation framework, and suggest you use a CRDT for text within that semantics.
Again, Replicache/Reflect.net is a very practical server-reconciliation based system that uses user-defined commands for application semantics, and delegates tricky merge situations to CRDTs; see https://reflect.net/#benefits:~:text=First%2DClass%20Text,st....
Notion also uses a command queue, but we don't use a CRDT for text - although I've been thinking about that for a long time
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.
Subscribe on Substack for updates.
It has many providers, easy persistence, and many integrations.
Maybe make a compatibility layer to use the Y.JS ecosystem?
Always excited for any CRDT innovations though, and I'm sure there is stuff to learn from this work.
As a note, it appears to use Elastic's 2.0 license preventing selling software that includes this library [1]
[0] https://nlnet.nl/project/JSON-Joy/
[1] https://github.com/streamich/json-joy/blob/master/LICENSE
I really want json based CRDTs to be fast, but one of the problems we have optimising this stuff is that there aren’t a lot of real world data traces around to use as baselines for benchmarking. I don’t know which parts of automerge are slow, and without that knowledge I can’t make them fast. If we have some data from your application, most upcoming json based CRDTs will almost certainly work well for your use case.
If you’re up for it, flick me an email or just open a PR on https://github.com/josephg/editing-traces
I don’t think the main point is the supposed superiority of WASM vs JS in terms of performance, as the article surmises.