Is there a common way to ensure linearisability of replicated items?
As far as I know, linearisability is very hard to ensure..why is that?
I have some sketch algorithms in mind that tell me they should be
linearisable.
Principle :
- All get/put requests are serialized on the node responsible of the
related key.
- attach versions to the items
- if a put request returns OK. Then it is well-written. If it returns KO,
then it may or may not have been written (to 0, 1, ..., all replicas)
- an item is stored on a site only if its version is bigger than the
previously one.
Guarantees :
- If an item is well-written (Put returned OK), then all subsequent Get of
that key will return an item at least as new as the one written
- If an item is not well-written, then the first successful Get may return
that item or an older one. If it returns an older one, then the new one
will never appear in the future.
Do these guarantees ensure linearisability?
Here are the algorithms (I think they ensure my guarantees):
(we assume we have an algo that recovers the items and replicas when
crashes occur)
Put(K,V){
IF (I'm sure latest version of item of key K is well-written) THEN
(label)- perform local write (with version=latest+1)
- perform write to all replica sites (with version=latest+1)
- wait for all acks (for some time)
- IF not all acks received THEN
- latest version is NOT well-written
- return KO
ELSE - latest version is well-written
- return OK
ELSE
- fetch item of key K from all replica sites
- wait for all items to be received (for some time)
- IF all items got, THEN
- store locally the one of latest version
- GOTO (label)
ELSE return KO
}
Get(K){
IF (I'm sure latest version of item of key K is well-written) THEN
- return the item I store
ELSE
- fetch item of key K from all replica sites
- wait for all items to be received (for some time)
- IF all items got, THEN
- perform local write of the one of latest version (with
version=latest+1)
- perform write to all replica sites (with version=latest+1)
- wait for all acks (for some time)
- IF not all acks received THEN
- latest version is NOT well-written
- return KO
ELSE
- latest version is well-written
- return the item I store
ELSE return KO
}
What do you think about them?
Thank you.
Julien.
_______________________________________________
p2p-hackers mailing list
[email protected]
http://lists.zooko.com/mailman/listinfo/p2p-hackers
