Comments (6)
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?
from roshi.
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
from roshi.
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?
from roshi.
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 Oops, I see what you mean.a
will only exist in the Add set or the Remove set for a given logical set—never both.
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.
from roshi.
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!
from roshi.
Closed with #33
from roshi.
Related Issues (17)
- Data races in farm HOT 1
- CRDT semantics violated if same timestamp? HOT 2
- document use cases HOT 2
- Support service discovery using Etcd or Consul HOT 1
- Support twemproxy as a proxy for roshi HOT 4
- Incorrect deleted field in response HOT 2
- README.mk - LWW-element-set formalism HOT 1
- Eventually, remove SelectOffset HOT 1
- Storage engine notes / options HOT 1
- Cursor instead of pagination HOT 2
- cursor.Parse() should treat EOF as empty member HOT 3
- Cursor-based pagination to fetch the "previous" page HOT 1
- roshi-server golang app select and map order ? HOT 4
- docstore support
- Failed in testing repairs HOT 3
- Project status HOT 2
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from roshi.