Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Chapitre 3 Gestion des transactions et contrôle de concurrence 1- Notion de tra

Chapitre 3 Gestion des transactions et contrôle de concurrence 1- Notion de transaction 2- Théorie de la concurrence 3- Méthodes de contrôle de la concurrence 3.1- Verrouillage 4- Transactions de base de données, Ex: Oracle Qu’est ce qu’une transaction? C'est une séquence d'opérations (lectures/ écritures) qui doit être exécutée dans son intégralité, amenant la BD d'un état cohérent a un autre état cohérent. S’il n'est pas possible d'accéder à un état cohérent, rien ne doit être fait. 3 Propriétés d’une transaction Une transaction est caractérisée par 4 propriétés dite ACID (Atomicité, Cohérence, Isolation, Durabilité) Atomicité Toutes les mises-a-jour doivent être effectuées ou aucune. La séquence d’actions d’une transaction est indivisible En cas d’échec, le système doit annuler toutes les modifications réalisées. 4 Propriétés d’une transaction Cohérence La base de données doit passer d'un état cohérent a un autre état cohérent. En cas d’échec, il faut restaurer l’état initial cohérent. Isolation Les résultats d'une transaction ne sont rendus visibles aux autres transactions qu'une fois celle-ci validée. Les accès concurrents peuvent mettre en question l'isolation. 5 Propriétés d’une transaction Durabilité Les modifications d'une transaction validée sont persistantes. Principal problème survient en cas de panne disque. 6 Théorie de la concurrence La théorie de la concurrence permet de garantir la cohérence et l'isolation des transactions Elle est basée sur la théorie de la sérialisabilité des transactions. Objectif: rendre invisible aux clients le partage simultané des données. 7 Exemple de transaction Exemple : Réservation des places pour une séance de spectacle. Programme RESERVATION Entrée : Une séance s, le nombre de places souhaitées Nbplaces, le client c Début Lire la séance s Si Nombre de places libres > Nbplaces Lire le compte du client c Soustraire Nbplaces au nombre de places libres Débiter le compte du client Ecrire la séance s Ecrire le compte du client c Fin 8 Exemple de transaction Pour le contrôle de concurrence, les instructions prises en compte sont les accès aux données. Les lectures notées r (ou R) Les écritures notées w (ou W) le programme RESERVATION se représente simplement par la séquence R(s) R(c) W(s) W(c). Cette séquence est appelée ordonnancement : séquence ordonnée d’opérations de lecture et d’écriture d’une ou plusieurs transactions. 9 Exécution concurrente et sérialisabilté Exécution concurrente du programme Réservation notées P1et P2. Chaque programme veut réserver des places dans la même séance s par deux clients différents c1et c2. Soit l’ordonnancement concurrent: R1(s) R1(c1) R2(s) R2(c2) W2(s) W2(c2) W1(s) W1(c1) P1 veut réserver 5 places et P2 veut réserver 2 places. 10 Exécution concurrente et sérialisabilté P1 lit s et c1 : nombre de places vides=50 P2 lit s et c2 : nombre de places vides=50 P2 écrit nombre de places=48(50-2) P2 écrit le nouveau compte de c2 P1 écrit nombre de places=45(50-5) P1 écrit le nouveau compte de c1 A la fin de l’exécution il y a un problème (normalement nombre de places libres=50-2-5=43). Problème: P2 lit et modifie une information que P1 a déjà lu en vue de la modifier. 11 Exécution concurrente et sérialisabilté Exemple d’une exécution imbriquée correcte: R1(s) R1(c1) W1(s) R2(s) R2(c2) W2(s) W1(c1) W2(c2) Après exécution on aura nombre de places libres=43. Cette exécution imbriquée (ou concurrente) est sérialisable c’est à dire équivalente à une exécution ou ordonnancement en série. 12 Exécution concurrente et sérialisabilté Définition 1 : Un ordonnancement est correct s’il est sérialisable c'est-à-dire équivalent à un ordonnancement série formé des mêmes transactions. Définition 2 : Deux ordonnancements H et H’ sont équivalents si : ils sont définis sur les mêmes transactions et possédent les mêmes opérations. Ils ordonnent les opérations conflictuelles des transactions non avortées de la même manière. 13 Exécution concurrente et sérialisabilté Définition 3 : Deux opérations issues de deux transactions différentes sont en conflit si : elles concernent le même élément de données l’une d’elles est une écriture. 1er cas : Ri(X) Wj(X) 2e cas : Wi(X) Wj(X) 3e cas : Wi(X) Rj(X) Dans ces 3 cas (ij) les opérations sont en conflit. 14 Exécution concurrente et sérialisabilté Première méthode: permutation d’opérations non conflictuelles H: R1(a) W1(a) W2(a) R1(b) W1(b) R2(b)W2(b) R1(a) W1(a) R1(b) W2(a) W1(b) R2(b)W2(b) R1(a) W1(a) R1(b) W1(b) W2(a) R2(b)W2(b) Donc H est sérialisable (équivalent à l’ordonnancement série T1- T2) donc ordonnancement correct 15 Exécution concurrente et sérialisabilté Deuxième méthode: le graphe de précédence ou de sérialisation Définition : un graphe de précédence est un graphe orienté dont les nœuds sont les transactions. Un arc relie Ti à Tj si et seulement si une opération de Ti précède une opération de Tj et si ces deux opérations sont en conflit. Un ordonnancement est sérialisable si et seulement si son graphe de précédence est sans cycle. 16 Exécution concurrente et sérialisabilté Pour l’exemple de l’ordonnancement H sont graphe de précédence est : T1 T2 17 Problèmes consécutifs à une concurrence sans contrôle Perte d'une mise à jour Exemple: compte X avec un solde de 500 initialement • T1: débit de 100 , T2: débit de 200 • Ordre d'exécution: T1 T2 temp1 = Lire(X)(500) temp2 = Lire(X)(500) Ecrire(X, 400) Ecrire(X, 300) Commit Commit 18 Problèmes consécutifs à une concurrence sans contrôle Résultat: solde de 300 au lieu de 200 Perte de la première mise à jour • Isolation non respectée: dans T2, la lecture trouve X=500, mais avant l'écriture X=400 (lecture non répétable) 19 Problèmes consécutifs à une concurrence sans contrôle Analyse incohérente Exemple: comptes X (solde: 500) et Y (200), total Z • T1: transfert d’un montant de 100 de X vers Y; T2: écriture de la somme X+Y dans Z T1 T2 temp1 = Lire(X)(500) Ecrire(X, 400) temp2 = Lire(X)(400) temp3= Lire(Y)(200) Ecrire(Z, 600) Commit temp1= Lire(Y)(200) Ecrire(Y, 300) Commit 20 Problèmes consécutifs à une concurrence sans contrôle • La somme X+Y=700 avant et après le transfert, mais au milieu du transfert le total calculé par T2 est incohérent • Isolation non respectée: T2 voit la modification de X faite par T1 21 Problèmes consécutifs à une concurrence sans contrôle Écritures incohérentes Exemple: comptes X et Y, qui doivent toujours avoir le même solde (X=Y) • T1: initialiser X et Y avec 100; T2: pareil, mais avec 200 T1 T2 Ecrire(X, 100) Ecrire(X, 200) Ecrire(Y, 200) Ecrire(Y, 100) Commit Commit 22 Problèmes consécutifs à une concurrence sans contrôle A la fin X=200 et Y=100, bien que T1 et T2 respectent la contrainte X=Y Les écritures sont incohérentes, les contraintes d'intégrité ne sont pas respectées • Isolation non respectée: T1 peut voir la modification de X faite par T2 – Écriture d'une valeur non-validée ("écriture sale") 23 Problèmes consécutifs à une concurrence sans contrôle Dépendances non-validées Exemple: compte X avec un solde de 500 initialement • T1: débit de 100 finalement annulé; T2: débit de 200 T1 T2 temp1 = Lire(X)(500) Ecrire(X, 400) temp2 = Lire(X)(400) Ecrire(X, 200) Commit Rollback 24 Problèmes consécutifs à une concurrence sans contrôle T2 utilise la valeur X=400 écrite par T1, qui est finalement annulée L'annulation de T1 implique l'annulation de T2 aussi (annulation en cascade) • Durabilité non respectée: T2, qui est validée, doit être annulée – Cause: lecture d'une valeur non validée ("lecture sale") Pour éviter les annulations en cascade éviter les lectures sales – Méthode: retarder la lecture après la fin de la transaction qui a fait l'écriture 25 Méthodes de contrôle de concurrence L'objectif du contrôle de concurrence: produire des exécutions sérialisables Algorithmes de contrôle de concurrence: Modifient l'entrelacement des transactions pour rendre l'exécution sérialisable: réordonnancement des opérations Ordonnanceur ("scheduler"): module logiciel qui exécute l'algorithme de contrôle de concurrence • Le SGBD reçoit une séquence d'exécution d'entrée que l'ordonnanceur modifie pour rendre l'exécution concurrente correcte 26 Méthodes de contrôle de concurrence Les méthodes pessimistes (ou préventives) : elles interviennent avant l’occurrence d’une opération rendant l’ordonnancement non sérialisable en bloquant (faire attendre) la transaction en question (mettre en attente la transaction. Exemple : verrouillage à deux phases (2 PL). Méthodes optimistes : elles interviennent après l’occurrence d’une opération qui rend l’ordonnancement non sérialisable et avortent (ou annulent) une ou plusieurs transactions. Elles laissent les conflits se produire mais les détectent et annulent leurs effets. Exemple: Estampillage 27 Le verrouillage à deux phases : Le 2PL est le protocole le plus répandu pour assurer des exécutions concurrentes correctes. Principe : En plus des opérations de Lecture/Ecritures, une transaction doit acquérir des verrous et libérer des verrous. 28 Le verrouillage à deux phases : Stratégie pessimiste: essaie de prévenir les incohérences en mettant en attente des opérations Principe: Un verrou associé à chaque article, accordé aux transactions Objectif: marquer (verrouiller) les opérations réalisées sur l'article par les transactions afin de ne laisser passer que des opérations commutables (non conflictuelles) • Une opération en conflit avec des opérations déjà acceptées des transactions en cours bloquée 29 Le verrouillage à deux phases : Régles d’utilisation : Une transaction ne peut lire ou écrire un élément de données sans l’avoir préalablement verrouiller. Si une transaction verrouille un élément de données, elle doit le libérer plutard. Le protocole 2PL utilise des verrous en lecture notés RL (Read uploads/Finance/ transaction-concurrence-traitement-d-x27-image.pdf