4 ms·
A family of CRDTs supporting both State and Op based replication in Rust
- jph 6y agoQuick 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.
- jhardy54 6y agoGit 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.
- zaarn 6y agoI 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.
- jhardy54 6y ago...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).
- kitd 6y agoMany thanks. I'd heard of CRDTs before but that's the best summary yet!
- hardwaresofton 6y agoBTW, state and op CRDTs are technically equivalent, some more links that might help: https://gritzko.gitbooks.io/swarm-the-protocol/content/crdt.html https://gritzko.gitbooks.io/swarm-the-protocol/content/crdt.... John Mumm - A CRDT Primer: Defanging Order Theory: https://www.youtube.com/watch?v=OOlnp2bZVRs 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 https://www.youtube.com/watch?v=CPbhrPPI1Xw
- deleted 6y ago[deleted]
- billconan 6y agoI 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?
- pretty_lorelei 6y agoAs I understand it, it's a tuple of lists of cubes, i.e. a slot stores a head of a linked list of cubes.
- davidrusu 6y agoMaintainer 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
- billconan 6y agothen 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.
- eigenrick 6y agoI 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.
- jackric 6y agoI find the explanation with cubes is a bit obtuse. I would find some short examples with Sets and Maps much faster to grasp.
- davidrusu 6y agoWhen 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.
- alangibson 6y agoFor those that want to go down the rabbit hole: https://github.com/alangibson/awesome-crdt https://github.com/alangibson/awesome-crdt I'll be adding this link pretty soon.