Context Notion of history

An operation in a history may have or not a matching response.

Client Tier Server Tier
In the history below operation (x++) has a matching response but not (x- -).
(3) H2 = (inv, x++,p).(inv, x--,q).(res, x++,p)
(2)
An operation is pending in a history when there is no matching response.
(1)
A history is complete when every invocation has a matching response.
(1) invocation
Clients Proxy Endpoints Servers (2) some magic !
(e.g., REST) (3) response
points d'accè s
3 6
Outline Notion of history
Introduction A history is a sequence of invocations and responses by the client processes on
Context one or more shared objects.exemple : un compteur est un obj partagé
Notion of history
What is Data Consistency? For instance,
Anomalies H1 = (inv, x++,p).(inv, x--,q).(res, x++,p).(inv,r(x),p).(res, x--,q).(res,r(x),1,p)
Common Criteria
Causal Consistency A history is commonly represented as a timeline.
Linearizability
x++ r(x) 1
Sequential Consistency
Eventual Consistency p
x--
A Comparison
q
2 5
Running example
Clients p and q share counters x, y, …
Each counter can be incremented (++), decremented (- -),
or its content fetched locally (r).
Cloud computing infrastructures: x et y des compteurs contenu de x
x++ r(x) 1
Shared objects and consistency
p
Pierre Sutra Servers
Télécom SudParis
q
first.last@telecom-sudparis.eu
x--
ici une API qui expose des compteurs ici par exemple on a ht une place de concert et on annule la transactions
4
Bcp de datastore ou il y a des compteurs, ex : Redis
Data consistency Anomalies
Definition de la cohé rence (est une propriete de sureté ) An anomaly is the observation (by the client processes) of a behavior that is not
A set of histories S is prefix-closed if, and only if, possible in a sequential execution. cad on peut pas le voir ds une execution sequentielle
for every history h, every prefix p of h is in S.
There is a trade-off between anomalies and performance. This trade-off comes from
For instance, the set below is prefix-closed. the fact that synchronizing storage nodes is expensive, in terms of network and
CPU usage. Ds le systeme reparti qui font les sefivces parfois on veut laisser les anomalies pour etre + performants.
S = { (inv, x++,p).(inv, x--,q).(res, x++,p),
As a consequence, a data store may deliberately expose anomalies.
(inv, x++,p).(inv, x--,q),
(inv, x++,p) }
The programmer should deal with anomalies, and must design its application in
consequence.
9 12
notion de phnomene : qualifie des comportements qui sont pas attendus
Data consistency : dé fini le type d'histoire ré alisable pour le client Read-my-writes
Recall that a property P on a system can be A basic consistency criterion is read-my-writes (RMW).
a liveness property (something good eventually happens), vivacite
a safety property (something bad never happens), or surete RMW states that a client always sees its past updates. un client voit tj ses maj : critè re de Read-my-write
both.
An example,
Such a property is expressed on the histories produced by the system. Dans cette histoire on satisfait le critè re RMW.
For instance, x++ r(x) 1 Rouge voit l'incrementation puis sa
dé crementation
( P1 ) a client process always sees a value written in the past, or concurrently to
its read operation. x-- r(x) 0
( P2 ) a shared counter is lock-free when it is always true that at least one of
the pending calls eventually complete.
8 11
Notion of history Data consistency
A history is sequential when it corresponds to a non-interleaved sequence of Definition
invocations and matching responses, possibly terminated by a non-returning A consistency criterion is a prefix-closed set of histories.
invocation.
As a consequence, a consistency criterion defines the possible responses of an
A sequential history h is legal when it satisfies the sequential specification of every operation from the perspective of the clients.
object used in h. i.e, l'API des objets specification : preciser precisement ce que fait qlqchose
satisfaire la spé cification des objets : les operations correspondent bien à l'API. Si on fait ++ on a bien le chiffre qui a incré menté .
In general, a consistency criteria is a safety property.
[Q] What are the properties of x ++ r(x)
this history?
cette histoire est sequentielle
l'histoire est lé gale car quand on fait ++ on lit bien 1
r(x) 1 x ++
7 10
Common anomalies Real-time ordering
(non-causal read) a client observes an update u, u causally follows v, yet the client For some history h, relation o <h o’ holds, when res(o) precedes inv(o’) in h.
does not observe v. lecture non causale : le fait d'obserfver qlqchose apres causalement qu'une premiere maj a eu lieu mais on observe pas la maj
r(y) 1 r(x) 0 Relation (<h ) captures the real-time ordering between operations.
x ++ y ++
In the history below, (x++) <h r(x) and (x++) <h (x - -) is true.
(fork) two clients observe two writes in a non-compatible order fourchette/croisement r(x) 1
les lectures qui sont faites par le clients sont
x++ r(y) 0 incompatibles.
x ++ x --
Ici on arrive pas a linerise les operations en
conservant l'ordre dexecution des clients.
Ils ne voient pas les maj apporte par les autres.
y-- r(x) 0 Il y a eu une bifurcation.
Cette relation s'appelle l'ordre des processus : on prend en compte les deux relations d'ordres
15 18
Common anomalies Outline
histoire : ce que voit un client quand il accè de à un service à pls.
(non-monotonic read) a client observe updates U then U’, yet U ⊄ U’ lecture non monotone Introduction
on a incrementer et on est revenu en
Context
x++ r(x) 0 r(x) 1 arriere : on a perdu loperation
Notion of history
x-- What is Data Consistency?
Anomalies
Common Criteria Critè re de cohé rences les + communs
(lost update) some update is never applied to the data store si le serveur a plante, la maj arrive jamais. Causal Consistency
Linearizability
r(x) 0 r(x) 0 Sequential Consistency
Eventual Consistency
x ++
A Comparison
14 17
Common anomalies Anomalie les + classiques Anomalies
un client ne va jamais maqnue ses maj mai il peut bserve des lecture non monotone.
(fuzzy read) a client observes an intermediate/partial state Quand on voit un etat partiel Under RMW, clients may miss updates
and observe non-monotonic reads.
r(x) 0.5 ici pbl de type on est cense avoir un entier
h1 : x++, x--,r(x) = 0
x ++ h1' : x++,r(x)=1
x++ r(x) 0 r(x) 1 on a pas monotonie de la lecture mais le
critere de coherence dis que cest bon car
on voit les maj au cour du tmps
(real-time violation) a client does not observe the latest state pbl de tmps reel. On voit pas encore
l'incrementation pourtant elle a eu lieu x--
r(x) 0
x ++
13 16
 timestamps : exemple de versionnage
Causality Causal consistency
causalement cohé rent
Simplifying assumptions A history h is causally consistent (CC) when for every client process p,
there exists a sequential legal history L such that
Each write brings the object into a unique state (e.g., x1). (L|p) is equivalent to (h|p),
Each read observes either the initial state (x0) or some write. (L|W) is equivalent to (h|W), and
*
L respects the order ↝h (if o’ ↝h o holds then o’ <L o is true)
There are only read (r) and write (w) operations.
pour chacun des processus on doit trouver une
w(x1) r(x1)
r(x1) Example p
hostoire cohé rente et qui respecte la causalite.
on trouve une histoire sequentiel pour chaque
h w(x2) r(x2) processus, qui contient les actions realisé es.
w(x1)
ordre du pgm :
q on prend les actions de p et on ajoute les maj
manquantes. Same pour q.
on dé finit les versions des objets
h = { (w(x1).r(x1)), (w(x2), r(x2))} L_p = w(x2).w(x1).r(x1) seule relation dordre w(x2) < r(x1) L_q = w(x2).w(x1).r(x2)
w(x2) on donne un numé ro pour dire cest la maj n°k
For process p, the sequential history is w(x2).w(x1).r(x1). on a ajoute w(x2) ds L_p car c'est une é criture
cf *
In the case of q, this is w(x1).w(x2).r(x2).
21 24
Causality Some more definitions
A problem. Definition (equivalence of histories) histoire equivalente
In history below, what is the causal past of the operation by p? Two histories are equivalent when they contain the same events, i.e., the same set
on ne sait pas si p lit l'operation de rouge ou s'il
of responses and invocations by the same processes.
r(x) 1 lit l'operation de bleu. w(x1)
ici h1 ~ h0
On introduit la notion de version
p h1
Definition (projection)
x ++ r(x1) r(y0)
q Given a history h and some process p,
x ++ (h|p) is the restriction to the events (invocations and response) of p,
r (h|W) is the restriction to the writes events on any object. on s'interesse qu'aux ecritures
Definition (complete)
Complete(h) is built from h by removing the operations pending in h.
en cour
par exemple si w(x1) se finit pas on aurait complte(h1) = r(x1).r(y0)
20 23
Causality Causality
In a history, each client executes one operation after another. A history induces a causality relation between its operations.
This relation between operations is named process order.
It is a subset of the real-time order. Operation o causally depends on operation o’ (written o’ ↝h o) when
par ex : b suit causalement a si a < b o precedes o’ at some process,
The process order is a form of causality between operations.
si je lis x_a alors je depend causalement
Clearly, this is not the only one. o is a read r( x ) and o’ is the corresponding write w(xa), or
a de loperaton qui a modifie x en x_a
In history below, the operation of p observes the increment operation of q. for some operation o’’ in h, o’ ↝h o’’ and o’’ ↝h o on fait la fermeture transatives des deux relations d'ordre
aux deux lignes d'avant
objet registres :on fait sur eux que des lecture et ecriture
r(x) 1 un systeme doit au minimum assuré la cohé rence causale (meme s'il y en a qui ne le font pas)
p
x ++ exemple de cas (on fait ici la fermetures transitives des relations)
on a w(x1) ~> r(x1) car r(x1) a besoin que x est ete modifie en x1 par w(x1)
w(x1)
q et r(x1) < r(y0) donc r(x1) ~> r(y0)
19 h0 r(x1) r(y0) ce qui donne => w(x1) ~> r(y0) : fermture transitive 22
 Linearizability Eventual consistency
Proposition Definition (eventual consistency)
Linearizability is a non-blocking property, that is if an operation o is pending in h, A history h is eventually consistent (EC) when for every object x
then there always exists a response r to o such that h.r is linearizable. if there is a bounded amount of write operations on x in h,
then eventually all the read operation observe the same state.
Il y a un moment ou tout le monde voit la mê me chose
Corollary
Implementing a linearizable data store in a non-blocking manner w(x ) 1
r(x )
1
r(x )
1
r(x2)
p
is always possible.
w(x2) r(x2) r(x2) r(x2)
q
27 30
Linearizability Sequential consistency
cohé rence sequentielle : l'ordre par pgm
Proposition Definition (sequential consistency) [Lam79]
Linearizability is a non-blocking property, that is if an operation o is pending in h, A history h is sequentially consistent (SC) when one may append zero or more
then there always exists a response r to o such that h.r is linearizable. responses to h to form a history h’ such that
on peut tj trouver une valeur de ré ponses aux operations complete(h’) is equivalent to some sequential and legal history L, and
composition : si on prend deux services linearisable cest comme si on avait un seul service linearisable.
the per-process ordering in h is preserved in L
Proof.
Assume that for some linearization L of h, L contains a response r=(res,o,p), cf feuille
Proposition
where p is the caller of o. We append r to h and observe that L is also a
linearization of h.r. SC is not a local property. w(x1) r(y0)
si on a un service qui assure la cohé rence sequentielle
Otherwise, let s be the state of the shared object at the end of L. We apply o to s et un autre, le produit ne donne pas un service sequentiel
w(y2) r(x0)
leading to some response r. Then, a linearization of h.r is L.(inv,o,p).r.
par objet : c'est cohé rent sequentiellement mais l'histoire
n'et pas coherente sequentiellement dans son ensemble car on
ne peut pas trouver h', on ne peut pas liné arisé .
Ici on lit r(y0) avant w(y2) et r(x0) avant w(x1) => on a uncycle : pas linearisable.
26 29
w(x1) < r(y0) et w(y2) < r(x2) et on à l'ordre des versions tels que x0 << x1 (ie version x0 installé ds le systeme avant x1), y0 << y2
Linearizability Linearizability
Definition (linearizability) [HW90] Proposition
A history h is linearizable if one may append zero or more responses to h Linearizability is a local property, i.e., if for every object x, (h|x) is linearizable
to form a history h’ such that then h is also linearizable.
complete(h’) is equivalent to some sequential and legal history L, and
the real-time ordering in h is preserved (i.e., <h ⊆ <h’ ⊆ <L ) Corollary
To implement a linearizable set of objects X, it suffices that the implementation
x-- r(x)
of each object (x ∊ X) is linearizable.
[Q] Is this history linearizable?
attention : r(x) n'est pas fini r(x) 0 x ++ Linearizability is the “common” model when considering a shared object.
L_1 = r(x)0, x--, x++
L_2 = r(x)0, x--, r(x)-1, x++ For instance, all objects in java.utils.concurrent are linearizable.
L_1 est une linearisation de h, tout comme L_2
Et la precedence temporel de L_1 est contenu dans la celle de h1' (same pour 2)
car
L_1 ~ complete(h_1') où h_1' = h\{r(x)}
Proposition : h est linearizable ssi pour chaque operations il existe un point ds le tmp to ,tel que
et L_2 ~ complete (h_2') où h_2' = h; resp(r(x), -1, p)
si on considere lexecution sequentielle (ds l'ordre des to) cette execution est legale.
25 28
References
[HW90] Linearizability: A Correctness Condition for. Concurrent Object, M. Herlihy,
J. M. Wing, TOPLAS, 1990.
[Lam79] How to Make a Multiprocessor Computer That Correctly Executes
Multiprocess Programs, L. Lamport, TOCS, 1979.
[FGL96] Eventually-serializable data services, A. Fekete, D. Gupta, V. Luchango, N.
Lynch, A. Schvartsman, PODC, 1996
[Aham94] Causal Memory: Definitions, Implementations and Programming, M.
Ahamad et al., Distributed Computing, 1994
33
Comparing consistency criteria
A consistency criteria is defined as a prefix-closed set of histories.
As a consequence, one may compare two consistency criteria
by an inclusion relation (⊆).
Proposition
It is true that (LIN ⊊ SC ⊊ CC ⊊ RMW).
32
Comparing consistency criteria
real-time lost update fork non-monotonic non-causal fuzzy read
violation read read
EC
RMW
CC
SC
LIN
= disallowed anomaly
31