cbaquero / delta-enabled-crdts Goto Github PK

Hi Carlos!

We are experimenting around the topic of real-time collaborative editors, and I remarked that I only saw existing solutions based upon operation-CRDTs. I came across your amazing articles about delta-state CRDTs (notably Efficient Synchronization of State-Based CRDTs), and I was wondering whether or not it could be a good candidate to implement a real-time collaborative editor. By looking more closely in the various articles, I don't have the impression that you define somewhere a delta-based sequence CRDT. However, in this repository the ORSeq CRDT seems to be the one I have been looking for.

Could you tell me if it's only a prototype or a "stable" implementation. Additionally, do you have some write up about how it works besides the code? Also, if you have already tried something in the same vein, I would be very glad to have your input on the subject 😄

Cheers!

Greetings.

I've been working on implementing these delta-state convergent replicated data types in another language (Pony). If you're interested in seeing my implementation so far, you can find it here.

While implementing, I noticed that your lwwreg::join operation is not commutative. That is, when multiple join operations are applied with the same timestamp (U), the final value for any particular replica of the register depends on the order in which the operations were applied. Specifically, for a set of operations whose timestamp is the same, and that timestamp is the highest timestamp that the replicas will see, the first of such join operations will "win".

Here's a trivial worked example, where more than one value arrives with a logical timestamp of "6":

replica A receives: (5, "foo"), (6, "bar"), (6, "baz"); final: (6, "bar")
replica B receives: (6, "bar"), (5, "foo"), (6, "baz"); final: (6, "bar")
replica C receives: (6, "baz"), (6, "bar"), (5, "foo"); final: (6, "baz")

In the example, two of the replicas end with a final value of "bar", and one replica ends with a final value of "baz", because of the order in which the delta-states was applied. Even with infinite retransmission of those delta-states, the result in each replica will not change from the shown final value.

The workaround I used to make the join operation fully commutative and salvage this data structure as a CRDT is to:

• require that the value type (T) is also comparable.
• introduce a "bias" by value, that favors either the greater or the lesser value in cases where the timestamp is equal.

This strategy ensures that all replicas will eventually converge to the same final value and timestamp.

In essence, the "Last Writer Wins Register" (LWWReg) must become either a "Last Writer Greater Value Wins Register" (LWGVWReg) or a "Last Writer Lesser Value Wins Register".

If both the timestamp and the value are equivalent (neither side is greater or lesser in either case), then there is no conflict to resolve.

You can see my implementation of LWWReg here, including a bias type parameter named B which accepts either BiasGreater or BiasLesser as the type argument, so that the bias strategy is selected at compile time and is part of the type signature.

Just because it might help make sense of the code, I'll note that one additional change I've made from your model is that my delta-mutator methods accept a delta-state-so-far as a parameter, so that the pattern of accumulating several delta-states before sending it to the other replicas is facilitated with fewer object allocations.

In closing, thank you for your work on this highly important paper, and on this reference implementation. I hope this issue ticket can be of some help in the overall goal of increasing adoption of these concepts.

first all thanks for share this approach to address some state-CRDTs problems,e.g. huge ORMap...
i have read “http://gsd.di.uminho.pt/members/cbm/ps/delta-crdt-draft16may2014.pdf” this paper, it is somewhere to find a classic example?
and have see your youtube's 'Designing for Partition Tolerance with CRDTs',what is the 'buffer' function?
and when one delta msg is lost in network problem, because state-type CRDT is not care about network problem, it can send full state in the next time, what can be done in this situation?
and in one scenario we have 3 replicas r_a/r_b/r_c. and now r_a occur update(u1) on one ORMap instance, what the interaction flow between r_a/b/c? thanks

I ran into a crash while walking through the example code in Visual Studio, and was able to get some help from the VC++ team in tracking it down:

https://github.com/CBaquero/delta-enabled-crdts/blob/master/delta-crdts.cc#L416-L427

       dotkernel<T, K> add(const K& id, const T& val)
       {
              dotkernel<T, K> res;
              // get new dot
              pair<K, int> dot = c.makedot(id);
              // add under new dot
              ds.insert(pair<pair<K, int>, T>(dot, val));
              // make delta
              res.ds.insert(pair<pair<K, int>, T>(dot, val));
              res.c.insertdot(dot);
              return res;
       }

res is created on the stack, which ends up using the stack allocated res.cbase when assigning the reference to res.c in the ctor.

https://github.com/CBaquero/delta-enabled-crdts/blob/master/delta-crdts.cc#L312-L315

  dotkernel() : c(cbase) {} 
  // if supplied, use a shared causal context
  dotkernel(dotcontext<K> &jointc) : c(jointc) {} 
//  dotkernel(const dotkernel<T,K> &adk) : c(adk.c), ds(adk.ds) {}

Once res is copied by value on return the stack allocated value is destroyed and c is left with a dangling reference and an eventual crash. I'm not proficient enough in C++ to advise on a fix, but figured I'd pass this along.

The crash occurs in ccounter::inc when r.dk joins the result of dk.add or dk.rmv: https://github.com/CBaquero/delta-enabled-crdts/blob/master/delta-crdts.cc#L670-L687

  ccounter<V,K> inc (const V& val=1) 
  {
...
    for(const auto & dot : dots)
      r.dk.join(dk.rmv(dot));
    r.dk.join(dk.add(id,base+val));
    return r;
  }