A family of CRDTs supporting both State and Op based replication in Rust | Hacker News Reader

A family of CRDTs supporting both State and Op based replication in Rust

github.com

131 pointscpard14 comments

Quick lingo...

CRDT: Conflict Free Replicated Data Type. A kind of data structure and synchronization approach whereby beplicas can be updated independently and concurrently without typical coordination. Can be good for distributed collaborative real time editing, and/or syncing live data among machines.

State-based replication: send all CRDT state to each replica; no need to send operations. Typically good when state is small relative to operations, and/or when communications are unreliable. A.k.a. CvRDT, convergent replicated data types.

Operation-based replication: send all CRDT operations to each replica; no need to send state. Typically good when state is large relative to operations, and/or when communications are reliable. A.k.a. CmRDT, commutative replicated data types.

Git examples:

- Commits provide the state of each file at that snapshot.

- Diffs (patches) provide a minimal operation to move from one FS state to another.

I don' think git is a good example since if you edit two git repositories together and you try to merge them, you can get conflicts.

The point of CRDTs is that when you merge state, there CANNOT be a conflict, ever.

...right, because Git doesn't use CRDTs. Those example point to where Git has state/operations, not where Git uses CRDTs (because it doesn't).

Many thanks. I'd heard of CRDTs before but that's the best summary yet!

BTW, state and op CRDTs are technically equivalent, some more links that might help:

https://gritzko.gitbooks.io/swarm-the-protocol/content/crdt....

John Mumm - A CRDT Primer: Defanging Order Theory:

https://www.youtube.com/watch?v=OOlnp2bZVRs

And if you'd like a quick example, with some code from implementation, there's a Rustfest talk from 2018:

https://www.youtube.com/watch?v=CPbhrPPI1Xw

I find the explanation with cubes is a bit obtuse. I would find some short examples with Sets and Maps much faster to grasp.

When writing that up I was looking for a structure who's natural partial order could be neatly laid out in 2-dimensions.

But it seems this is not very clear, I'll take another look around for a more intuitive structure.

For those that want to go down the rabbit hole: https://github.com/alangibson/awesome-crdt

I'll be adding this link pretty soon.

I can't understand the illustration in the README, why cubes can be placed outside the 2 slots? What's the point of having slots if cubes can be outside?

As I understand it, it's a tuple of lists of cubes, i.e. a slot stores a head of a linked list of cubes.

Maintainer here, it's meant to be a visual representation of a 2-tuple of natural numbers.

But I get your point, there was another commentator here who expressed similar frustrations. When I find some time, I'll see about picking a clearer example for the README

then maybe it should say:

> a 2-tuple like structure that stores cubes in each slot.

instead of

> a 2-tuple like structure that stores cubes in two slots.

The flowing also confused me:

> It allows us to store a value and resolves concurrently set values by keeping both values.

"both" indicates the concurrency can only happen between two parties. I think saying "keeping all values" is more accurate.

I say great work in coming up with any visual example at all.

Visualizing multi-dimensional merges isn't easy. :)

That said, maybe an additional example of merging JSON blobs might be more intuitive for some.

Reply on news.ycombinator.com