Validation Atomique

Sacha KrakowiakUniversit Joseph Fourier

Projet Sardes (INRIA et IMAG-LSR)

http://sardes.inrialpes.fr/people/krakowia

Validation atomique

cole Doctorale de GrenobleMaster 2 Recherche Systmes et Logiciel

2 2003-2004, S. Krakowiak

Motivation et objectifs

! Excution de transactions rparties" Les transactions sont un outil de base pour la tolrance aux fautes" Transaction = suite dactions A = (A1 ; A2 ; ; An) possdant les

proprits ACID# Atomicit, Cohrence, Isolation, Durabilit (persistence)

" Dans une application rpartie, les actions peuvent sexcuter surdes sites diffrents, do ncessit dune coordination

! Validation" La validation (opration commit) est une opration cl de

lexcution dune transaction (elle rend les modificationsdfinitives)

" Nous allons examiner comment cette opration est ralise dansun systme rparti

" Intrt# pratique (ralisation de transactions rparties)# thorique (rsultats dimpossibilit ; relations avec autres

protocoles)


Plan

! Introduction la validation" Prambule sur la communication

" Spcification du problme

! Solutions historiques" Validation deux phases : le problme du blocage

" Validation trois phases

! Solutions utilisant la diffusion" Spcification du protocole de diffusion (UTRB)

" Ralisation de la validation

" Ralisation du protocole de diffusion

! [ voir plus tard] Relations entre validation et consensus


! Un premier rsultat dimpossibilit" Si le systme de communication perd des messages de manire

indtectable, il est impossible de raliser un protocole daccord enun nombre fini dtapes

! Le problme de lattaque coordonne

Prambule : le paradoxe des gnraux (1)

A ! B : message 36 : on attaque demain 5h00B ! A : bien reu 36A ! B : bien reu bien reu 36

A (1500)

C (2 000)

B (1500)

J. Gray, Notes on Database Operating Systems, in Operating Systems, An Advanced Course,Lecture Notes in Computer Science, nr 60, Springer-Verlag (1978)


Le paradoxe des gnraux (2)

Il nexiste pas de protocole rsolvant le problme de laccord avecun nombre fini de messages si la communication nest pas fiable

Supposons quil existe de tels protocoles, et considrons celui qui raliselaccord en utilisant le nombre de message minimal, soit n

Supposons que le dernier message soit de B vers A : A ! B : messagen1B ! A : messagen

Puisque B ne recevra plus de messages, B a pris une dcision avantlenvoi de messagen

Puisque le protocole doit fonctionner en cas de perte de messages, ladcision de A ne doit pas dpendre du contenu de messagen

Mais alors messagen ne sert rien, et on peut le supprimer.Ceci est contradictoire avec le fait que le protocole est minimal.


Le paradoxe des gnraux (3)

Comment vivre avec dans la pratique ?

Rappelons lhypothse de dfaillance : le systme de communicationperd des messages de manire indtectable

En pratique, on essaie de dtecter la perte de messages, soit par signaldu systme de communication lmetteur, soit en gnral au moyendun dlai de garde sur laller-retour (hypothse de synchronisme)

Exemple concret : laccord confirm

Le protocole dtablissement de liaison de TCP utilise laccord confirm(3 messages) :

A ! B : demandeB ! A : accordA ! B : accord confirm

Chaque partenaire voit donc un aller-retour


Le problme de la validation (commitment)

! Motivations" Pour terminer une transaction, il faut dcider de son issue!: validation

(commit) ou annulation (abort)

" La validation rend les modifications dfinitives!; lannulation ramne lesprocessus leur tat avant transaction (proprit datomicit)

" La dcision est prise linitiative dun participant quelconque, et doitvrifier diffrentes proprits (cf plus loin) pour satisfaire aux spcificationsdes transactions

! Hypothses" La communication est fiable (messages dlivrs sans altration)!et

synchrone (une borne est connue sur le temps de transmission desmessages, ainsi que sur les vitesses relatives des processus)

N.B. il suffit de faire cette hypothse sur une dure couvrant celle de la transaction

" Les processus peuvent subir des pannes franches. Un processus en pannepeut tre rpar et rintgrer la transaction. Un processus est dit correct silnest jamais tomb en panne

" Chaque processus peut crire des donnes en mmoire stable, oupermanente, qui survit aux dfaillances


Spcifications de la validation

Chaque processus contribue la dcision par un vote (OUI ou NON). Unprocessus qui vote OUI est prt rendre permanentes ses modifications. Leprotocole doit avoir les proprits suivantes :

Validit : La dcision est soit valider, soit annuler

Intgrit : Tout processus dcide au plus une fois (une dcision estdfinitive)

Accord uniforme : Tous les processus (corrects ou non) qui dcidentprennent la mme dcision

Justificationx : Si la dcision est valider, alors il y a au moins x processusqui ont vot OUI [diffrentes variantes du protocole selon choix de x ; enpratique, x = n (le nombre total de processus)]

Obligationx : Si x processus votent OUI, et si ces x processus sontcorrects, alors la valeur dcide est valider [en pratique x = n]

Terminaison : tout processus correct dcide au bout dun temps fini


Remarques sur les spcifications

Les dcisions valider et annuler ne sont pas symtriques. Il nest pasncessaire que tous les processus aient vot NON pour dciderdannuler

Limplication de la proprit de justification nest pas symtrique : ladcision dannuler peut tre prise mme si tous les processus ontvot OUI

Exemple : tous les processus ont vot OUI ; un processus tombe enpanne avant que la dcision de valider ne soit prise

La proprit dobligation est ncessaire pour exclure les solutionstriviales (par exemple : tous les processus dcident toujoursdannuler)

Lhypothse de la communication fiable et synchrone exclut lepartitionnement du rseau (le rseau est maintenu connexe malgrles pannes de site)

10 2003-2004, S. Krakowiak

Un peu dhistoire

Solution initiale : Gray (1978), protocole de validation 2 phases (2-phasecommit, ou 2PC)

Le protocole 2PC peut ne pas se terminer (mme avec communicationsynchrone). Recherche dun protocole de validation non bloquante (Non-Blocking Atomic Commitment, ou NBAC)

Protocole de validation non bloquant 3 phases (3PC) (Skeen, 1982)

Protocole non bloquant utilisant la diffusion uniforme temporise(Babaoglu - Toueg, 1992)

Relations entre validation et consensus (dtails plus tard)

La validation est plus difficile que le consensus, mais une forme plusfaible (pratiquement acceptable) de validation se ramne au consensus

avec le protocole Paxos (Lamport)

avec dtecteurs de pannes imparfaits (Chandra - Toueg)

11 2003-2004, S. Krakowiak

Protocole 2 phases (2PC)

coordinateurp0

coordinateurp0

participantpi

participantpiUn processus coordinateur interroge

tous les processus (participants)Chaque participant envoie son voteau coordinateurQuand le coordinateur a reu tous lesvotes, il prend sa dcision :

tous oui : validerautrement : annuler

Le coordinateur envoie la dcision tous les participants ; chacun dcideconformment ce message

enqute ?

vote vote

tousOUI

pastousOUI

valider annuler

Noter que le coordinateur et chaque participant voient un aller-retour(dlai de garde utilisable)

enqute ?

ph. 1

ph. 2

temps

12 2003-2004, S. Krakowiak

2PC : dtection de dfaillances

coordinateurp0

participantpi

enqute ?

vote

dlai de garde2" + #

Coordinateur : si des rponsesmanquent aprs le dlai de garde,dcision = annuler(tous les sites nont pas vot OUI)

coordinateurp0

participantpi

enqute ?

vote

dlai degarde 2" + T

Participant : si lecoordinateur na pasrpondu aprs le dlai degarde, on suppose quilest en panne

Le participant essaie de dterminer si unedcision a t prise, en interrogeant les autresparticipants (un autre participant peut avoirreu une rponse du coordinateur)

13 2003-2004, S. Krakowiak

2PC : scnario de blocage

coordinateurp0

participantpi

enqute ?voteOUI

zonedincertitude

Entre le moment o il a vot OUI et le moment o ilreoit une rponse du coordinateur, un participantest dans une zone dincertitude (un autre participantpeut se trouver soit en phase de validation soit enphase dannulation, et les deux issues sont possibles)

Cela peut conduire un scnario de blocage :

pi a vot OUI et se trouve dans la zonedincertitude

Le coordinateur tombe en panne aprs avoirenvoy une dcision valider ou annuler certains participants

ces participants tombent en panne leur tour

Une dcision a t prise mais pi (correct) na aucunmoyen de la connatre (au moins jusqu' un ventuelredmarrage du coordinateur)

14 2003-2004, S. Krakowiak

2PC : scnario de blocage (2)

La possibilit de blocage provient de lincertitude sur ltat global(pas de connaissance partage)

vot (OUI) vot (NON)dcidvalider

dcidannuler

possible

possible

possible

possible

possible

possible

possible

possible

possible

possible

possible

possible

vot (OUI)

vot (NON)

dcidvaliderdcidannuler

tat pi

tat pj

la suite dun vote OUI, toutes les possibilits restent ouvertes

15 2003-2004, S. Krakowiak

Protocole 3 phases (3PC)

coordinateurp0

coordinateurp0

participantpi

participantpi

enqute ?

vote vote

tousOUI

pastousOUI

valider

annuler

enqute ?

prparer

ack

tousack

ph. 1

ph. 1

ph. 3

Le coordinateur interroge les participants Chaque participant renvoie son vote Si la dcision est annuler, elle est envoye

aux participants (comme en 2PC) Sinon, le coordinateur envoie prparer Chaque participant renvoie un

acquittement Quand il a reu tous les acquittements, le

coordinateur renvoie valider

N.B. sil ny a pas de perte de messages,alors les acquittements sont redondants

16 2003-2004, S. Krakowiak

3PC : dtection de dfaillances

Raction lcoulement du dlai de garde1. Dcider annuler2. lire un nouveau coordinateur3. Rien4. lire un nouveau coordinateur

Le nouveau coordinateur interroge les participants certains annuls : dcider annuler certains valids : dcider valider tous incertains : dcider annuler certains prts mais aucun valid :

reprendre lenvoi du message prparer

coordinateurp0

participantpi

enqute ?

vote

valider

prparer

ack

1

2

4

Reprise aprs dfaillance si navait pas vot : annuler si avait dcid : continuer avec dcision prise si incertain : consulter autres participants

3

incertain

valid

prt

17 2003-2004, S. Krakowiak

3PC : connaissance partage

Il ny a pas dtat o pi soit incertain (aprs vote OUI) et pj ait dcid valider.Le protocole 3PC introduit une connaissance partage.

2PC : un processus qui dcide valider sait que tous ont vot OUI 3PC : un processus qui dcide valider sait (en outre) que tous savent

que tous ont vot OUI

vot (OUI) vot (NON)dcidvalider

dcidannuler

possible

possible

possible

possible

possible

possible

possible

possible

possible

possible

vot (OUI)

vot (NON)

dcidvaliderdcidannuler

tat pi

tat pj

prt

prt

possible

possible

possible

possible

possible

18 2003-2004, S. Krakowiak

Validation utilisant la diffusion

! Motivations" Le problme de la connaissance partage identifi dans 3PC peut

tre abord en utilisant un protocole de diffusion" Il existe de nombreux protocoles de diffusion (tudis plus tard

dans le cours). Les spcifications de chaque protocole doivent treadaptes aux hypothses de dfaillance et aux besoins spcifiquesdutilisation

! Dmarche" Dfinir un protocole gnrique de validation utilisant la diffusion

# gnrique : acceptant un protocole de diffusion quelconque" Spcifier un protocole de diffusion ayant les proprits souhaites" Examiner la ralisation de la validation avec ce protocole" Examiner la ralisation du protocole de diffusion

Un protocole gnrique de validation (1)

Programme des participants (y compris initiateur)

upon (receipt of [transaction, !c, participants])Cknow = local clock // perform operations requested by transactionif (willing and able to make updates permanent) then

vote = YESelse

vote = NO// decide commit or abort for the transactionatomic_commitment(transaction, participants)

Schma densemble dune transaction

Initialisation (par un processus quelconque)send [transaction, !c, participants] to all participants

19

. Babaoglu, S. Toueg, Non-blocking Atomic Commitment, in S. Mullender (ed.), Distributed Systems (2ndedition), Addison-Wesley, 1993

Un protocole gnrique de validation (2)

La structure est la mme quecelle du protocole 2PC

Coordinator

send [VOTE_REQUEST] to allset-timeout (local_clock + 2")wait-for (receipt of votes from all)

if (all votes YES) thenbroadcast(commit, participants)

else broadcast(abort, participants)on-timeout

broadcast(abort, participants)

Participant

set-timeout (Cknow + $c + ")wait-for (receipt of VOTE_REQUEST from coord.)

send (vote) to coordinatorif (vote = NO) then

decide (abort)else

set-timeout (Cknow + $c + 2" + $b )wait-for(delivery of decision messages)

if (decision mess. is abort) thendecide (abort)

else decide (commit)on-timeout // coordinator failed

decide according to termin. protocolon-timeout

decide (abort). Babaoglu, S. Toueg, Non-blocking AtomicCommitment, in S. Mullender (ed.), DistributedSystems (2nd edition), Addison-Wesley, 1993

20

21 2003-2004, S. Krakowiak

Validation avec diffusion simple (1)

Les proprits de lalgorithme de validation dpendent du protocole broadcastinsr dans le protocole gnrique

Cas 1 : broadcast = diffusion simple (synchrone) : si un processus correct diffuse m, tous les processus destinataires corrects dlivrent m pour tout message m, tout destinataire dlivre m au plus une fois, et

seulement si un processus a diffus m il existe une constante connue $b telle que si la diffusion a t lance au

temps (physique) t, aucum message ne sera dlivr aprs t + $b

Cette diffusion na pas la proprit tout ou rien (diffusion fiable). En cas depanne de lmetteur pendant la diffusion, un message peut tre dlivr certains destinataires seulement

22 2003-2004, S. Krakowiak

Validation avec diffusion simple (2)

Le protocole de terminaison (raction la panne du coordinateur) tente dedterminer si une dcision a t prise en contactant les participantssurvivants.Sa terminaison en temps fini nest pas garantie

Exemple (dj vu) : le coordinateur prend une dcision, la diffuse certains participants, puis

tombe en panne ces participants tombent en panne leur tour

En fait le protocole de validation qui utilise la diffusion simple nest autre que2PC

Il faut renforcer les spcifications de l'algorithme de diffusion pour quil ait laproprit tout ou rien

23 2003-2004, S. Krakowiak

Validation avec diffusion fiable uniforme (1)

Cas 2 : broadcast = diffusion fiable uniforme synchrone : si un processus correct diffuse m, tous les processus destinataires corrects dlivrent m pour tout message m, tout destinataire dlivre m au plus une fois, et

seulement si un processus a diffus m il existe une constante connue $b telle que si la diffusion a t lance au

temps (physique) t, aucun message ne sera dlivr aprs t + $b + accord uniforme

si un processus (correct ou non) dlivre m, tous les processus correctsdlivrent m

uniformit

diffu

sion

sim

ple

Cette diffusion a la proprit tout ou rien (diffusion fiable). En cas de panne delmetteur pendant la diffusion, le message est dlivr tous les participants ou aucun. En outre luniformit garantit laccord entre tous les processus : si unprocessus a dcid avant de tomber en panne, tous les processus correctsdestinataires sont au courant de cette dcision. Donc le scnario de blocage estimpossible


Participant

set-timeout (Cknow + $c + ")wait-for (receipt of VOTE_REQUEST from coord.)

send (vote) to coordinatorif (vote = NO) then

decide (abort)else

set-timeout (Cknow + $c + 2" + $b )wait-for(delivery of decision messages)

if (decision mess. is abort) thendecide (abort)

else decide (commit)on-timeout

decide (abort)on-timeout

decide (abort)

Le protocole du coordinateur estinchang (broadcast est maintenantla diffusion UTRB)

Le protocole des participants estinchang, sauf pour le protocole determinaison (panne du coordinateur)devenu inutile : on dcide dannulercar on sait quaucune dcisioncontradictoire ne peut avoir t prise

Le protocole de diffusion fiableuniforme synchrone est appelUTRB (Uniform Timed ReliableBroadcast)

. Babaoglu, S. Toueg, Non-blocking AtomicCommitment, in S. Mullender (ed.), DistributedSystems (2nd edition), Addison-Wesley, 1993

24

25 2003-2004, S. Krakowiak


On peut dmontrer (cf Babaoglu & Toueg) que le protocole de validation utilisantla diffusion fiable uniforme synchrone (UTRB) satisfait aux spcifications de lavalidation, y compris labsence de blocage :

Tout processus correct dcide

On peut en outre prvoir le cas de restauration dun processus dfaillant(protocole de reprise). On peut ainsi assurer que :

Tout participant au courant de la transaction dcide, condition de restervivant suffisamment longtemps (borne connue) aprs sa reprise surdfaillance

Diffusion simple

Diffusion simple dans un groupe G de processus(composition fixe)

metteur :send (m) to all processes in Gdeliver (m)

destinataire (" metteur) :upon (receipt of m)

deliver (m)

Pour conclure ltude de la validation, il reste fournir une ralisation desprotocoles de diffusion

" diffusion simple

" diffusion fiable uniforme synchrone (UTRB)

Rappel : un messageenvoy via send par unprocessus correct parvient son destinataire(correct) en un temps t < "

26

Diffusion fiable uniforme synchrone (UTRB)

Diffusion fiable uniforme synchrone dans ungroupe G de processus (composition fixe)

metteur :send (m) to all processes in Gdeliver (m)

destinataire (" metteur) :upon (first receipt of m)

send (m) to all processes in Gdeliver (m)

Rappel : un message envoy viasend par un processus correctparvient son destinataire(correct) en un temps t < "

Un premier algorithme, simple mais peu efficace (nombre de messages % n2)

Un algorithme plus efficace sera prsent plus tard

27 28 2003-2004, S. Krakowiak

Conclusion (provisoire) sur la validation

! Importance" Pratique : algorithme de base pour la ralisation de transactions

rparties

" Thorique : un des deux problmes fondamentaux de prise dedcision concerte (lautre est le consensus, voir plus tard)

! Solutions" Ncessitent en pratique des hypothses fortes sur la

communication et le synchronisme

" Protocoles de base : 2PC, 3PC

! Reste voir" Relations entre validation et consensus

# consquences thoriques

# consquences pratiques

Documents

Validation Atomique