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

CRDT Benchmarks

jsonjoy.com

Post reply on HN
Print view View original

31–40 of 49 posts

Re: CRDT Benchmarks

#31

Post by josephg »

alserio wrote: post #26
fnordsensei wrote: post #13

Earlier quoted context omitted.

General CRDTs will guarantee valid data structures, but not schema/domain model validity. Kind of like how CRDTs applied to text will guarantee a string, but not valid English.

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 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.

Re: CRDT Benchmarks

#32

Post by josephg »

alserio wrote: post #24
jitl wrote: post #15

Earlier quoted context omitted.

You need to design your document to minimize these kinds of issues. You can treat properties in the document as a last-write-wins register to minimize “strange merge” consistency within that property. 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 R…

Why not going full OT then? Complexity?

OT systems generally require a single, centralised server to be a party in between any two changes. CRDTs make it really easy to do multi-server deployments or peer-to-peer data replication. That is (basically) not possible using OT based systems.

Re: CRDT Benchmarks

#33

Post by josephg »

Author 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 your code to see how you’ve pulled this off. Do you have anything you recommend I read to understand how your algorithm works?

Re: CRDT Benchmarks

#34

Post by alserio »

josephg wrote: post #31
alserio wrote: post #26

Earlier 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…

Thank you for your explanation

Re: CRDT Benchmarks

#35

Post by iudqnolq »

tantaman wrote: post #20
simonw wrote: post #7

I'm still hoping for a CRDT implementation with robust, thoroughly tested libraries for both Python and JavaScript that can talk to each other - I want to run Python on the server and JavaScript in the client and keep the two in sync with each other. 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-p…

Wouldn't any of the Rust implementations be what you need (Yrs, Diamond Types or the Automerge rust re-write)? Given you can bind to a Rust implementation in JS or Python or whatever else.

I've only looked into yrs. Unfortunately copying a js API into rust and using unsafe whenever you get a borrow check error feels doomed.

> 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.

Re: CRDT Benchmarks

#36

Post by streamich »

josephg wrote: post #33

Author 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…

> 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).

Re: CRDT Benchmarks

#37

Post by streamich »

josephg wrote: post #33

Author 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...

Re: CRDT Benchmarks

#38

Post by jitl »

alserio wrote: post #24
jitl wrote: post #15

Earlier quoted context omitted.

You need to design your document to minimize these kinds of issues. You can treat properties in the document as a last-write-wins register to minimize “strange merge” consistency within that property. 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 R…

Why not going full OT then? Complexity?

Yes, complexity! What I meant by OT-style operations is a command queue with optimistic updates on the client, and authoritative updates made by the server. This is an easy way to structure your application. "Full OT" means you need to be able to transform any operation type against any other operation of any type. It's quite complicated to implement your application's semantics in terms of operations while maintaining the M*M transform conditions.

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

Re: CRDT Benchmarks

#39

Post by Rapzid »

josephg wrote: post #32
alserio wrote: post #24

Earlier quoted context omitted.

Why not going full OT then? Complexity?

OT systems generally require a single, centralised server to be a party in between any two changes. CRDTs make it really easy to do multi-server deployments or peer-to-peer data replication. That is (basically) not possible using OT based systems.

Most people wanting to use CRDTs though want to use them in scenarios where a central authority is desirable for all sorts of other reasons.

Re: CRDT Benchmarks

#40

Post by josephg »

Rapzid wrote: post #39
josephg wrote: post #32

Earlier quoted context omitted.

OT systems generally require a single, centralised server to be a party in between any two changes. CRDTs make it really easy to do multi-server deployments or peer-to-peer data replication. That is (basically) not possible using OT based systems.

Most people wanting to use CRDTs though want to use them in scenarios where a central authority is desirable for all sorts of other reasons.

Oh, absolutely. And OT based approaches work great here. CRDTs have the advantage that multi-server deployments are also easy, and modern CRDTs are increasingly faster and better optimized than most OT systems (certainly the ones I've worked on). But OT is a great approach.
Post reply on HN