How can I implement a lossless CRDT using Gun?

user_609468 0
Viewed 315

How do I create a CRDT using Gun?

For instance, if I want to implement an grow-only array, where each element points to the next, how do I solve conflicts?

To simplify, let's create this scenario, where Alice and Bob are cooperating.

The array contains 3 elements, [a, b, d].

The internal representation of this array would be a linked list like this:

a => b => c

(of course, the internal representation would be something like {value: 'a', next: { value: 'b' next: { value: 'c' }}}), but I think you get my point with the terser notation.

Alice now wants to insert element c between b and d.

Concurrently, Bob wants to insert element C between b and d.

Concurrently, they have this internal representation of the array:

Alice: a => b => c => d

Bob: a => b => C => d

When they join the CRDT, they would converge to either one of the following values:

a => b => c => C => d

or

a => b => C => c => d

No matter what, a) both of them would converge on the same value and b) they would not lose each other's data.

Can we achieve this using Gun?

(This question is a simplification and follow-up question to https://github.com/amark/gun/issues/602)

crdt gun
1 Answers

Yes.

Here is a demo of code doing just that from a few years ago:

https://youtu.be/rci89p0o2wQ

You can create any other CRDT as a data structure on top of GUN's base CRDT.

We even did a whole cartoon explainer on generic algorithms for this type of stuff:

https://gun.eco/explainers/school/class.html

(Or see a more detailed explanation for a case-specific implementation, by the wonderful Martin Kleppmann starting at https://youtu.be/yCcWpzY8dIA?t=29m36s )

I haven't seen anybody implement RGA specifically on top of GUN, but given how short the code you sent over, it should be pretty easy. (Although the "delete" would need to be a null tombstone, but that is fine)

It is probably easiest to start by looking at the counter CRDT for "how to start saving data to GUN with a custom extension", a grow-only CRDT in just 12 lines of code:

https://gun.eco/docs/Counter

You note that it is very basic, RGA would be similar, you'd probably have some GUN extension (just a JS method/function, that makes it easier for developers to use) like

Gun.chain.rga = function(...

Then internally, like with the counter, you'd call gun.put( or gun.set( or whatever other commands to save data to the graph (put and set are themselves just extensions like RGA is, nothing fancy here) where you'd build/construct a graph/tree/table, or you could be lazy and just do something like:

// fictional code
var myData = {
  rgaTree: {left: {}, right: {}}
}
myData.rgaTree.left.next = myData.rgaTree.right;
myData.rgaTree.right.prev = myData.rgaTree.left;
// yes! circular references are supported!
gun.put(myData);

Obviously you might want to be more detailed and control the UUIDs with the cuids and stuff, but you get the point.

There is no reason to actually replace HAM CRDT directly or "inject" a CRDT along side it, just @pgte would model the CRDT's data structure on GUN (probably with a nice easy API via a GUN extension), then you'd also have that extension support a callback, which if passed you'd gun.get(... through the RGA graph/tree and run the various RGA logic before spitting the result back out to the developer. This tree can be dynamically mutated concurrently inside of GUN by many peers, like Alice and Bob!

Then, GUN will save that dynamically changing and updating data to disk via one of (many) storage engines (such as IPFS!) so IPFS can host the persistence of data over time, and GUN can manage the O(1) tree lookups that are the mutable/changing/dynamic tree/graph/index structures.

user_3422750
Related