Feature request: δ-CRDTs

[ckaran]

This is a feature request/future plans kind of comment.

Do you have any plans to implement δ-CRDTs in the future? I explained my use cases in this issue, but I suspect that others have similar requirements.

[davidrusu]

Sorry for taking so long to reply, work has been taking most of my time this past week.

I personally don't have a need for this, but I'm not against it and If you have a concrete use-case (and it sounds like you do) to drive the design of delta CRDT's I'm very happy to work with you to get them added into the library.

The reason why I'm hesitant to just go ahead and implement some papers directly is that there is a big engineering challenge in make these algorithms actually usable, as an example, take the problem of choosing at what point the delta should be calculated and shared across the network. Do the two actors negotiate with each other to compute the minimal delta's between the two of them? Does each actor collect up a log of delta's and distribute those (essentially a more compressed CmRDT)? Or do actors keep track of what they had sent to other actors and only compute delta's since last sync? These different approaches likely will influence the design of the CRDT

It sounds like you do have a concrete use-case that could drive these decisions so I would say you are in the best possible position to help with an implementation. I'd be more than happy to help you anywhere I can.

[ckaran]

Sorry for taking so long to reply, work has been taking most of my time this past week.

Honestly, I was very pleased with how quickly you responded!

The reason why I'm hesitant to just go ahead and implement some papers directly is that there is a big engineering challenge in make these algorithms actually usable, as an example, take the problem of choosing at what point the delta should be calculated and shared across the network. Do the two actors negotiate with each other to compute the minimal delta's between the two of them? Does each actor collect up a log of delta's and distribute those (essentially a more compressed CmRDT)? Or do actors keep track of what they had sent to other actors and only compute delta's since last sync? These different approaches likely will influence the design of the CRDT.

I was thinking of a simpler approach; define a set of traits that users can implement that handle some of those details, and provide a small set of supporting data structures that can be used as building blocks. I don't have enough experience with CRDTs to engineer them myself, so please view the following as thoughts that need to be mutually worked on.

• Methods/data structures/traits that represent a single, atomic delta. The deltas must be serializable, comparable, etc. This will likely need to be figured out first as all traits and operations are going to be over deltas.
• A trait for negotiating the difference in knowledge between some pair of nodes A and B (or possibly something like the union of A-B, A-C, A-D,...). Since VClock is built on a BTreeMap, and since that has the range() method, and the Range type, doing something with that could be a good place to start. The default blanket implementation always returns the complete contents of the first object (A in the example above). The issue is that the trait needs to be designed so that implementors can choose how much data they have to send around, how many communications attempts they need to make, etc., which means that the API will need to be very flexible, and carefully designed to allow these choices.
• A trait for prioritizing the order of sending deltas. This will need access to extra information (one or more clocks, some of which are real-time so you can predict the drift in knowledge), so the API needs to be designed to allow this. This will likely also require that deltas be splitable, joinable, and reorderable as needed. For my own use case, I can broadcast 1500 bytes in a single UDP packet, which means that if I can split a delta (or join several together) such that they all fit within a single packet, then it will be more efficient than would be otherwise. Others will have their own limitations. The default implementation would be first-come, first-transmitted.
• Ideally, these traits would be orthogonal to one another, and easily composable. That would allow experimentation with different stacks to see what works best in a particular situation.

It sounds like you do have a concrete use-case that could drive these decisions so I would say you are in the best possible position to help with an implementation. I'd be more than happy to help you anywhere I can.

Thank you! But as you noted, this is going to require significant engineering effort. I think what we should do for the moment is spend sometime designing things as far we're able to.

Do you have a lot of users, or a forum where you can post requests for comment? It might be something worth discussing with a larger group.

[DePizzottri]

A brief comment: you might probably know about latest research results about delta-state based CRDT optimization, showing that straightforward antientropy algorithms performs pretty well, having even better network transmission rate then op-based.

https://blog.acolyer.org/2019/03/11/efficient-synchronisation-of-state-based-crdts/

[ckaran]

@DePizzottri Actually, I didn't know about that, so thank you for the link! I'm mostly interested in just using the library, CRDTs aren't central to my research. But thank you again for the link.

[ngortheone]

@ckaran
It looks like δ-CRDT are implemented in this paper JSON CRDT

And there are Haskell and Scala implementations:

• https://github.com/amarpotghan/crjdt-haskell
• https://github.com/fthomas/crjdt

[ckaran]

@ngortheone Thank you for the link to the paper! I will read it shortly.

As for the Haskell and Scala implementations, since the rest of my codebase is in Rust, I'd prefer a Rust library. Crossing language boundaries always seems to hurt me at some point or other.

[davidrusu]

@ckaran Judging on the past month and a bit, my schedule does not seem to let me be of much help to you on this project.
It's looking like you'll need to lead this work yourself if you want it to be done anytime soon. I'll prioritize reviewing any PR's you put up, but I can't promise to help much besides that.

[ckaran]

@davidrusu I understand your being overworked, and unfortunately, I'm in the same boat. This will have to wait until after I defend my PhD.

[DePizzottri]

@ckaran
It looks like δ-CRDT are implemented in this paper JSON CRDT

And there are Haskell and Scala implementations:

* https://github.com/amarpotghan/crjdt-haskell

* https://github.com/fthomas/crjdt

JSON CRDT from these paper is op-based

[ngortheone]

@DePizzottri

It looks like δ-CRDT are implemented in this paper JSON CRDT
And there are Haskell and Scala implementations:

* https://github.com/amarpotghan/crjdt-haskell

* https://github.com/fthomas/crjdt

JSON CRDT from these paper is op-based

I agree, it looks like OP-based CRDT, but I spotted there are a few important differences:

• Idempotence. In OP-based CRDT operations is not idempotent[1][2], when it is in this paper. Confusion arises from the fact that merge function takes a list of Ops
• Membership tracking. OP-Based CRDT algorithm often requires upfront knowledge of the number of replicas, again that is not the case in this paper.

Interestingly, Shapiro[2] defines two mixed types: operation-based emulation of state-based object and state-based emulation of operation-based object. After reading the definitions carefully I think it might
be the latter.

[1] https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type#Operation-based_CRDTs
[2] https://hal.inria.fr/inria-00555588/

[DePizzottri]

@ngortheone

In OP-based CRDT operations is not idempotent[1][2], when it is in this paper.

merge function of JSON CRDT looks like that it rather means apply, or even apply_in_causal_order because it carries casual metadata to apply in right order. Op-based CRDT's operations are not obligated to be idempotent, but it is may be a useful property.

OP-Based CRDT algorithm often requires upfront knowledge of the number of replicas

If you mean the dependence on some incarnations of vector clock/version vector as causality tracking mechanism, that's true. And that's true for most delta-state based CRDTs.