Correction de TD7 - Gestion des données et transactions réparties

Exercice 1 : Propriétés des exécutions concurrentes

Question 1 - Principe de recouvrabilité

Le principe de recouvrabilité garantit que le système de gestion de base de données (SGBD) ne sera jamais contraint d'annuler une transaction qui a déjà été validée (c'est-à-dire qui a exécuté son Commit). Cela permet de respecter la propriété de durabilité des transactions.

Analyse de l'exemple non recouvrable : Tracé : w1(x) r2(x) w2(x) C2 R1

1. La transaction T1 écrit une valeur x.
2. La transaction T2 lit cette valeur x, puis la modifie et se valide avec succès (C2).
3. La transaction T1 échoue et s'annule (R1). Puisque T2 a lu une donnée non validée de T1 qui finit par s'annuler, la valeur lue par T2 est incorrecte. Pour maintenir la cohérence, le système devrait annuler T2. Or, T2 a déjà été validée (C2). Cette exécution est donc non recouvrable.

Analyse de l'exemple recouvrable : Tracé : w1(x) R1 r2(x) w2(x) C2 Ici, T1 écrit puis s'annule (R1) avant que T2 ne lise la donnée. T2 lira donc la valeur restaurée d'avant T1, et pourra se valider sans conflit.

Question 2 - Annulation en cascade

Tracé : r1(s) r1(c1) w1(s) r2(s) r2(c2) w2(s) w2(c2) w1(c1) R1

Le scénario est le suivant :

1. T1 modifie la ressource s avec w1(s).
2. T2 lit cette ressource s modifiée par T1 avec r2(s), puis la modifie avec w2(s).
3. T1 décide finalement d'annuler ses opérations (R1).

T1 annulant ses modifications, la lecture effectuée par T2 devient obsolète et fausse (elle a lu une donnée qui n'a "jamais existé"). Bien que T2 n'ait pas encore validé, le système est forcé d'annuler T2 pour maintenir une base de données cohérente. Si T2 avait été lue par une transaction T3, T3 devrait aussi être annulée, d'où le terme d'annulation en cascade.

(Note : La mention isolée "ã Ì" dans le document source est un artefact d'extraction et n'a aucune signification fonctionnelle ici).

Question 3 - Le problème de l'écriture sale (Dirty Write)

Tracé : r1(s) r1(c1) w1(s) r2(s) r2(c2) w2(s) w2(c2) w1(c1) R1

Correction de l'énoncé source : L'explication fournie dans le document source indique que "T1 a validé après que T1 ait écrit dans s". Ceci est en contradiction directe avec le tracé fourni qui se termine par l'annulation de T1 (R1). Le tracé fait foi : T1 s'annule bien à la fin.

Le problème illustré ici est qu'une transaction (T2) écrit sur une donnée qui a été modifiée par une transaction non validée (T1).

1. T1 écrit dans s (w1(s)).
2. T2 lit et écrase cette valeur dans s (w2(s)) alors que T1 est toujours active.
3. T1 s'annule (R1).

Au moment de l'annulation de T1 (Rollback), le gestionnaire de transaction a pour instruction de restaurer la valeur de s à son état initial (avant w1(s)). Ce faisant, le système écrase brutalement la mise à jour effectuée par T2. C'est ce qu'on appelle une écriture sale.

Exercice 2 : Sérialisabilité et verrouillage à deux phases

Question 1 - Définition de la sérialisabilité

La sérialisabilité est un critère de correction. Une exécution (ou ordonnancement / schedule) de transactions concurrentes est dite sérialisable si son résultat final est strictement identique à celui qu'aurait produit une exécution en série de ces mêmes transactions (l'une après l'autre, sans aucun chevauchement). Cela garantit l'isolation des transactions tout en maximisant les performances via la concurrence.

Question 2 - Le verrouillage à deux phases (2PL)

Le verrouillage à deux phases est un protocole qui impose à chaque transaction de respecter deux étapes distinctes :

1. Phase de croissance : La transaction demande et acquiert tous les verrous (en lecture ou en écriture) dont elle a besoin. Elle ne peut en relâcher aucun.
2. Phase de décroissance : Une fois le premier verrou relâché, la transaction entre dans la phase de décroissance. Elle ne peut plus acquérir de nouveaux verrous.

Cette méthode prévient les conflits et garantit mathématiquement la sérialisabilité des transactions, au prix d'une perte potentielle de concurrence.

Question 3 - Non-respect de la règle de relâchement des verrous

Transactions étudiées : T1: r1(x) w1(y) C1 T2: w2(x) w2(y) C2

Tracé de l'exécution : rl1(x) r1(x) ru1(x) wl2(x) w2(x) wl2(y) w2(y) wu2(x) wu2(y) C2 wl1(y) w1(y) wu1(y) C1

Légende des verrous : rl = read lock, wl = write lock, ru/wu = read unlock / write unlock.

T1 viole le protocole du verrouillage à deux phases : elle relâche son verrou sur x (ru1(x)) avant d'avoir demandé son verrou sur y (wl1(y)). Cette violation ouvre une brèche qui permet à T2 de s'intercaler, de verrouiller x et y, et de s'exécuter. L'exécution résultante n'est plus sérialisable, car on observe un cycle de dépendances :

• Pour x, T1 lit avant que T2 n'écrive : dépendance T1 -> T2.
• Pour y, T2 écrit avant que T1 n'écrive : dépendance T2 -> T1. Il y a conflit et impossibilité de trouver un ordre d'exécution en série équivalent.

Question 3 (bis) - Détection de cycles de dépendances

(Note : Le document source comporte une erreur de numérotation et propose une deuxième question 3. La séquence i. présente également des répétitions suspectes "w1(x) w1(x) w1(x)", typiques d'une mauvaise extraction, mais qui n'impactent pas l'analyse du cycle).

i. Tracé : w1(x) r2(x) w1(y) w2(y) w3(x) C3 w1(x) ... C1 C2 Pour vérifier la sérialisabilité, on construit le graphe de précédence en observant les opérations conflictuelles :

• w1(x) précède r2(x) => T1 -> T2
• r2(x) précède w3(x) => T2 -> T3
• w3(x) précède w1(x) (à la fin) => T3 -> T1 Il y a un cycle formel (T1 -> T2 -> T3 -> T1). L'exécution est non sérialisable.

ii. Tracé : r1(x) w2(x) C2 w3(y) C3 r1(y) w1(z) C1 Analyse des conflits :

• r1(x) précède w2(x) => T1 -> T2
• w3(y) précède r1(y) => T3 -> T1 Il n'y a pas d'autres conflits (les variables z et les autres accès sont indépendants). Les dépendances sont T3 -> T1 -> T2. Il n'y a aucun cycle, l'exécution est donc sérialisable.

Question 4 - Analyse des ordonnancements sous verrouillage

Cette section détaille le mécanisme de mise en attente (blocage) causé par des conflits de verrous.

Pour H1 : r1(x) w2(x) C2 w3(y) C3 r1(y) w1(z) C1

• T1 prend un verrou partagé (lecture) sur x.
• T2 demande un verrou exclusif (écriture) sur x, mais x est tenu par T1. T2 est bloquée.
• T3 s'exécute librement sur y (verrou écriture) puis valide (C3).
• T1 poursuit, lit y, écrit z, puis valide (C1).
• La validation de T1 (C1) relâche le verrou sur x.
• T2 est débloquée, peut effectuer son w2(x) et valider (C2).

Pour H2 : r1(x) r2(y) r3(x) r1(z) r1(u) w3(x) r1(y) r3(u) w2(y) C2 C1 w3(u) C3 L'ordonnanceur pose des verrous selon la nature de l'opération :

• Les lectures (r) partagent les verrous. r1(x) et r3(x) cohabitent sans problème. r2(y) et r1(y) cohabitent également.
• T3 demande à écrire sur x (w3(x)). Or, T1 possède un verrou de lecture en cours sur x. T3 est bloquée. En conséquence, r3(u) est mis en attente.
• T2 demande à écrire sur y (w2(y)). Or, T1 possède un verrou de lecture en cours sur y (obtenu via r1(y)). T2 est bloquée.
• T1 finit ses opérations (C1) et relâche tous ses verrous.
• T3 (bloquée sur x) et T2 (bloquée sur y) sont libérées et peuvent terminer leurs exécutions.

Exercice 3 : Estampillage

Question 1 - Le problème d'interblocage (Deadlock)

L'interblocage survient lorsque deux transactions attendent mutuellement la libération d'une ressource détenue par l'autre.

Exemple : T1: r1(x) w1(y) C1 T2: r2(y) w2(x) C2

Sous un protocole de verrouillage à deux phases :

1. T1 verrouille x en lecture : rl1(x).
2. T2 verrouille y en lecture : rl2(y).
3. T1 veut écrire sur y et demande wl1(y). La ressource y est détenue par T2. T1 est mise en attente.
4. T2 veut écrire sur x et demande wl2(x). La ressource x est détenue par T1. T2 est mise en attente. T1 attend T2, et T2 attend T1. L'exécution est définitivement paralysée. Le SGBD doit intervenir en détectant le cycle dans le graphe d'attente (ou via un timeout) et avorter l'une des deux transactions.

Question 2 - Principe de l'estampillage

L'estampillage est une approche optimiste de gestion de la concurrence, qui n'utilise pas de verrous. Chaque transaction Ti reçoit à son lancement une estampille unique, notée TS(Ti) (pour Timestamp), basée sur l'heure système ou un compteur monotone croissant. L'ordre de sérialisabilité est fixé a priori par cette estampille : une transaction plus ancienne (estampille plus petite) est toujours prioritaire devant une transaction plus jeune.

Règle générale : Si une action d'une transaction Ti entre en conflit avec une action validée par une transaction Tj, on compare leurs estampilles. Si TS(Ti) > TS(Tj) (c'est-à-dire que Ti est plus récente), on accepte généralement l'action selon les règles d'écriture/lecture. Mais si une transaction essaye d'interagir avec une donnée du "futur" (modifiée ou lue par une transaction ayant une estampille supérieure), elle est abortée.

Question 3 - Rejet d'une transaction par estampillage

Tracé : r1(s) w2(x) r3(x) r2(x) w1(x)

Dans ce modèle, on admet que le numéro de la transaction correspond à son estampille (TS(T1) = 1, TS(T2) = 2, TS(T3) = 3). La transaction T1 (la plus ancienne) tente d'écrire sur la donnée x avec w1(x) tout à la fin du tracé. À ce stade, x a déjà été manipulée par T2 (écriture) et T3 (lecture). La règle de l'estampillage stipule que si une transaction tente d'écrire une donnée qui a déjà été lue par une transaction plus jeune (TS(T1) < TS(T3)), alors cette écriture est invalide car elle aurait dû être lue par cette transaction plus jeune dans un ordonnancement sériel. Par conséquent, T1 est rejetée (annulée) au moment où elle tente son w1(x).

Question 4 - Inconvénients de la méthode de l'estampillage

Le mécanisme de l'estampillage présente deux principaux défauts :

1. Abandons inutiles : Le contrôle étant très strict, le gestionnaire annule des transactions pour des conflits temporels, même si dans les faits, l'exécution aurait pu rester cohérente sans avortement.
2. Risque de privation (Starvation) : Si une transaction ancienne et longue entre souvent en conflit avec des transactions courtes et plus récentes, elle se fera perpétuellement annuler, relancer (avec une nouvelle estampille) et annuler de nouveau, ne parvenant jamais à valider ses traitements.

Méthode

Face à une épreuve sur la gestion des transactions, la clé est la rigueur du suivi des états (verrous ou estampilles).

1. Identifiez le protocole : La question porte-t-elle sur le verrouillage (2PL) ou l'estampillage ? Les règles d'annulation sont opposées : le 2PL bloque et met en attente (avec risque de deadlock), tandis que l'estampillage n'attend jamais mais avorte les transactions fautives.
2. Dessinez les graphes : Qu'il s'agisse d'un graphe de précédence (pour prouver la sérialisabilité) ou d'un graphe d'attente (pour prouver l'interblocage), tracez un nœud par transaction et tirez une flèche dès qu'une ressource est partagée avec au moins une écriture. Un cycle équivaut toujours à un échec (non sérialisable ou deadlock).
3. Tracez les chronologies pas à pas : Comme dans la question 2.4, lisez le tracé de gauche à droite. Maintenez mentalement (ou sur un brouillon) une table des verrous acquis. Dès qu'une requête de verrou exclusif percute un verrou existant, mettez la transaction en pause et passez à l'opération suivante dans le temps. Ne la reprenez que lorsqu'un Commit (C) ou un Rollback (R) libère la ressource bloquante.