Repair strategies should bias toward Adds about roshi

[peterbourgon]

If you delete (a, 99) from a set that has no element a in the add set, the element (a, 99) is put into the remove set. Selecting a will return the same result before and after the delete operation, but after the delete, only write operations that have a score higher than 99 will be able to successfully mutate the set.

Does it make sense?

[russelldb]

Yes, so you can remove elements that aren't present, and doing so with a very high time stamp will drop adds with a lower time stamp, what I think the cassandra community call "doomstones."

Got it, many thanks for answering the question. I ask as I am making an LWW-Element-Set for Riak and thought I'd use your semantic.

Many thanks

[russelldb]

I have a further question, please?

In State based CRDTs there is a merge function to get a single value from divergent CRDTs. In a Roshi LWW Element Set, given what you said above, what is the outcome if two sets merge where

Set A = Add(a,0), Rem()
Set B = Add(), Rem(a, 0)

From the table in your README it would seem that the Add wins?

A(a,1) R() remove(a,1) A(a,1) R()

But also remove wins?

A() R(a,1) add(a,1) A() R(a,1)

In the case of this two original states merging, what is the value of the Set? Say Line one is replica X and line two is replica Y, what happens when X LUB Y? Is it A(a, 1)R() or A(), R(a, 1) or something else?

[peterbourgon]

doomstones

Hehe. I like it.

what is the outcome if two sets merge where . . .

This initial condition could never exist in Roshi. Our write operations ensure that a given element a will only exist in the Add set or the Remove set for a given logical set—never both. Oops, I see what you mean.

If one cluster has A(a,1) R() and another has A() R(a,1), the merge would result in the add winning. But the reasoning is a little bit convoluted. The API between the cluster (a single logical CRDT node) and the farm (multiple nodes) is biased towards adds, i.e. it returns only the add sets. (That decision was taken deliberately, for reasons of performance.)

The farm will see cluster A returning (a,1) and cluster B returning nothing, and return (a,1) to the user, but would also detect that there's not perfect agreement and issue a read repair. So far so good. But since the scores are identical, the obvious path of the read repair is stymied. Looking at the code we don't explicitly deal with the case where multiple clusters return the same score but different "presence" indicators—so I guess we have underdefined behavior there. But we do have a bias on the write operation: an element must have a purely higher score to make it into the Remove set, but merely a greater-than-or-equal-to score to make it into the Add set, i.e. we're biased towards adds at that layer.

So I suppose I should update the read repair to exhibit the same bias, i.e. if an element has the same score but different presence indicators from multiple clusters, prefer to add it. If it's OK with you, I'll edit the title of this issue to reflect that concrete bit of work, and make a PR shortly.

Note this all assumes the SendAllReadAll read strategy. Other read strategies could shortcut parts of what I've described. And very interesting corner case! Thanks for bringing it up.

[russelldb]

Hey, you updated your reply as I was writing to you to describe the divergent behaviour you then described! Excellent.

I went for the same semantic (favour adds when add and remove timestamp are the same and both occur when merging divergent views of the data.)

This is has been a very valuable conversation for me, many thanks for taking the time!

[peterbourgon]

Closed with #33