Cours4.pdf

Base de données et interopérabilité Département Informatique École supérieure d'ingénieurs Léonard-de-Vinci (ESILV) 12 Avril, 2024 Ruiwen HE [email protected] La sérialisabilité Contrôle de concurrence Protocoles basés sur les verrous Protocoles basés sur les estampilles Protocoles basés sur la v...

Base de données et interopérabilité Département Informatique École supérieure d'ingénieurs Léonard-de-Vinci (ESILV) 12 Avril, 2024 Ruiwen HE [email protected] La sérialisabilité Contrôle de concurrence Protocoles basés sur les verrous Protocoles basés sur les estampilles Protocoles basés sur la validation Gestion des deadlock (verrous mortels) B D D & i n t e r o p é r a b i l i t é Plan du cours 2 PÔLE LÉ ONARD DE VINCI LA SÉRIALISABILITÉ PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é & B D D 4 La sérialisabilité Définition Une exécution concurrente H de n transactions T1, T2, T3, T4, Tn est sérialisable si et seulement s’il existe toujours un ordonnancement H0 de T1, T2, T3, T4, Tn tel que le résultat de l’exécution de H est le même que celui de l’exécution en série de H0. Si j’ai deux transactions T1 et T2, leur exécution imbriquée est sérialisable ssi équivalente à T1 puis T2, ou à T2 puis T1 (en série). En d’autres termes, à une exécution en isolation complète PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é & B D D 5 Contrôle de concurrence L'un des moyens de garantir l'isolement consiste à exécuter toutes les transactions en série afin qu'elles n'interfèrent pas les unes avec les autres. Cependant, l'exécution en série est très inefficace. Afin d'augmenter le débit et de réduire le temps de réponse, les bases de données permettent généralement l'exécution simultanée de plusieurs transactions. Par conséquent, le module de contrôle de la concurrence doit garantir que l'effet de l'exécution concurrente des transactions est exactement le même que l'effet de l'exécution en série des transactions (sérialité) afin de satisfaire aux exigences en matière d'isolation. PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é Définition Deux opérations Oi [x] et Oj [x] sont en conflit, si Oi ou Oj est une écriture. Deux transactions accèdent au même donné, et (au moins) une veut le modifier. B D D & Les conflits dans la concurrence 6 PÔLE LÉ ONARD DE VINCI [email protected] Les conflits exigent que les conditions suivantes soient remplies simultanément : les deux opérations proviennent de transactions différentes au moins l'une d'entre elles est une opération d'écriture B D D & i n t e r o p é r a b i l i t é Les conflits dans la concurrence 7 les objets de l'opération sont les mêmes PÔLE LÉ ONARD DE VINCI B D D & i n t e r o p é r a b i l i t é [email protected] Les conflits dans la concurrence 8 Les conflits les plus courants sont les suivants : Conflits lecture-écriture. La transactionT1 lit d'abord une ligne de données, la transaction T2 modifie la ligne de données, et la transaction T2 modifie d'abord une ligne de transactions, la transaction T1 lit la ligne d'enregistrements après deux planifications. la transaction T1 lit des résultats différents. Ce conflit peut entraîner des anomalies de lecture non répétables et des anomalies de lecture sale. Conflit lecture-écriture. Les mêmes raisons que les conflits lectureécriture. Ce conflit peut entraîner des anomalies de lecture sale. Conflit écriture-écriture. Deux opérations écrivent un objet l'une après l'autre, et le résultat de la dernière opération détermine le résultat final de l'écriture. Ce type de conflit peut entraîner une anomalie de perte de mise à jour. PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é & B D D 9 Les conflits dans la concurrence Reprenons une nouvelle fois l’exemple des mises à jour perdues : L1(s)L1(c1)L2(s)L2(c2)E2(s)E2(c2)E1(s)E1(c1) L1(s) et E2(s) sont en conflit ; L2(s) et E1(s) sont en conflit ; E2(s) et E1(s) sont en conflit. PÔLE LÉ ONARD DE VINCI [email protected] Considérer un ordonnancement O des transactions T1,... Tn. Le graphe de précédence de O est un graphe (N,A) où N est l’ensemble des transactions Il y a un arc (Ti, Tj) s’il y a un conflit entre Ti et Tj sur un objet Q et Ti accède à Q avant Tj B D D & i n t e r o p é r a b i l i t é Graphes de sérialisabilité 10 PÔLE LÉ ONARD DE VINCI [email protected] B D D & i n t e r o p é r a b i l i t é Exemple de graphe de sérialisabilité 11 PÔLE LÉ ONARD DE VINCI Lesquels correspondent à une exécution sérialisable ? B D D & i n t e r o p é r a b i l i t é [email protected] Tester la sérialisabilité Important : un algorithme de contrôle de concurrence doit vérifier qu’aucun cycle ne peut intervenir dans ce graphe. 12 PÔLE LÉ ONARD DE VINCI CONTRÔLE DE CONCURRENCE PÔLE LÉ ONARD DE VINCI [email protected] Protocoles basés sur les verrous Protocoles basés sur les estampilles Protocoles basés sur la validation B D D & i n t e r o p é r a b i l i t é Contrôle de concurrence 14 Gestion des deadlock (verrous mortels) PÔLE LÉ ONARD DE VINCI [email protected] Un verrou est un mécanisme permettant de contrôler l'accès simultané à un élément de données Les éléments de données peuvent être verrouillés selon deux modes : Verrou partagé S Un verrou partagé, noté Lock-S, est posé par une transaction lors d'un accès en lecture sur cet objet. Un verrou partagé interdit aux autres transaction de poser un verrou exclusif sur cet objet et donc d'y accéder en écriture. B D D & i n t e r o p é r a b i l i t é Protocoles basés sur le verrouillage 15 Verrou exclusif X Un verrou exclusif, noté Lock-X, est posé par une transaction lors d'un accès en écriture sur cet objet. Un verrou exclusif interdit aux autres transactions de poser tout autre verrou (partagé ou exclusif) sur cet objet et donc d'y accéder (ni en lecture, ni en écriture). PÔLE LÉ ONARD DE VINCI Le contrôleur pose des verrous pour une transaction T On ne peut poser un verrou partagé sur un tuple a que s’il n’y a que des verrous partagés sur ce tuple. On ne peut poser un verrou exclusif que si il n’y a aucun autre verrou, ou, il y a un verrou partagé déjà posé par T elle-même (upgrade) B D D & i n t e r o p é r a b i l i t é [email protected] Règles de verrouillage 16 PÔLE LÉ ONARD DE VINCI [email protected] Verrous = blocages. Il faut en poser le moins possible, surtout pour les verrous exclusifs. pour la durée la plus courte possible B D D & i n t e r o p é r a b i l i t é Les verrous 17 PÔLE LÉ ONARD DE VINCI B D D & i n t e r o p é r a b i l i t é [email protected] Verrouillage à deux phases (Two-phase locking, 2PL) 18 Phase 1 : Phase de Growing: des opérations de verrouillage peuvent être effectuées à ce stade. Le verrou S est demandé et acquis avant qu'une opération de lecture ne soit effectuée sur des données, Le verrou X est demandé et acquis avant qu'une opération d'écriture ne soit effectuée. Si le verrouillage échoue, la transaction entre dans un état d'attente et ne se poursuit pas tant que le verrouillage n'a pas réussi. Phase 2 : Phase de Shrinking la transaction peut libérer les verrous la transaction ne peut pas obtenir de verrous PÔLE LÉ ONARD DE VINCI [email protected] Acquisition des verrous Si une transaction Ti veut lire/écrire un valeur A Pour l’opération de lecture : Si Ti a un verrou sur A Alors Lire(A) i n t e r o p é r a b i l i t é Tant que un verrou S sur A existe dans une autre transaction Tj Faire & Sinon Attendre jusqu’à la libération du A Fournir un verrou S à Ti sur A FinTantQue B D D Tant que un verrou X sur A existe dans une autre transaction Tj Faire FinTantQue Fournir un verrou S à Ti sur A Lire(A) 19 FinSi PÔLE LÉ ONARD DE VINCI [email protected] Acquisition des verrous Pour l’opération d’écriture : Si Ti a un verrou sur A Alors Écrire(A) Sinon Tant que un verrou X sur D existe dans une autre transaction Tj Faire i n t e r o p é r a b i l i t é Attendre jusqu’à la libération du A FinTantQue Si un verrou S sur A existe dans la transaction Ti Faire Transformer verrou S en verrou X B D D & Sinon Fournir un verrou S à Ti sur A Écrire(A) FinSi 20 FinSi PÔLE LÉ ONARD DE VINCI C1 = 0 C1=0 + 800 C1=0 + 300 Guichet A (T1) Guichet B (T2) Start transaction Start transaction Lecture C1 Lecture C1 Écriture C1 Écriture C1 Conflit écriture-écriture Committed Committed B D D & i n t e r o p é r a b i l i t é [email protected] Verrouillage pour les mises à jour perdues 21 C1=800 OR C1=300 PÔLE LÉ ONARD DE VINCI [email protected] Verrouillage pour les mises à jour perdues C1 = 0 Guichet B (T2) Start transaction LOCK-S C1 Lecture C1 Start transaction LOCK-X C1 LOCK-S C1 Écriture C1 ATTENT.. UNLOCK C1 C1 = 800 Lecture C1 LOCK-X C1 C1=800 + 300 Écriture C1 B D D & i n t e r o p é r a b i l i t é C1=0 + 800 Guichet A (T1) UNLOCK C1 Committed Committed C1=1100 22 PÔLE LÉ ONARD DE VINCI Un blocage se produit lorsque deux transactions ou plus attendent que l'autre libère les verrous et qu'aucune d'entre elles ne peut continuer. Considérez les deux transactions suivantes : Ordonnancement en blocages T1 T2 LOCK-X(A) B D D & i n t e r o p é r a b i l i t é [email protected] Blocages (Deadlocks) Écrire (A) LOCK-X(B) Écrire (A) Attente pour LOCK-X(A) Attente pour LOCK-X(B) 23 PÔLE LÉ ONARD DE VINCI [email protected] Rollback en cascade Rollback en cascade se produit lorsque l'échec d'une transaction entraîne le retour en arrière d'autres transactions. Cela se produit lorsque d'autres transactions lisent des données non validées de la transaction défaillante, ce qui entraîne une situation connue sous le nom de " dirty read" (lecture sale). B D D & i n t e r o p é r a b i l i t é T1 T2 T3 LOCK-X(A) Écrire (A) UNLOCK A LOCK-S(A) Lire(A) LOCK-S(A) Lire(A) ROLLBACK LOCK-X(B) Écrire(A+B) LOCK-X(C) Écrire(A+C) 24 PÔLE LÉ ONARD DE VINCI B D D & i n t e r o p é r a b i l i t é [email protected] Concurrence réduite 25 Dans le système 2PL, les transactions conservent leurs verrous jusqu'à leur achèvement, ce qui limite potentiellement le nombre de transactions pouvant être traitées simultanément. Si une autre transaction a besoin des mêmes ressources verrouillées, elle doit attendre, ce qui peut entraîner des retards et un arriéré de transactions en attente. T1 lance une opération de longue durée, comme la génération d'un rapport, qui nécessite un verrou partagé sur de nombreuses valeur de la table des comptes. T2 et T3, qui souhaitent mettre à jour certaines des valeur verrouillées, sont bloqués jusqu'à ce que T1 termine et libère ses verrous, même s'il s'agit d'opérations rapides. PÔLE LÉ ONARD DE VINCI [email protected] Le 2PL ne garantit pas l’absence de deadlocks Le 2PL ne garantit pas l’absence de cascades Extension : “2PL strict” et “2PL rigoureux” B D D & i n t e r o p é r a b i l i t é Verrouillage `a deux phases 26 PÔLE LÉ ONARD DE VINCI [email protected] Dans le 2PL stricte, les transactions gardent leurs verrous exclusifs LOCK-X jusqu’au commit. Dans le 2PL rigoureux, les transactions gardent tous leurs verrous jusqu’au commit. B D D & i n t e r o p é r a b i l i t é Extension du 2PL 27 PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é Le 2PL strict garantit que les transactions conservent tous leurs verrous exclusifs LOCK-X jusqu'à ce qu'elles se terminent, soit en s'engageant, soit en s'interrompant. En conservant les verrous d'écriture jusqu'à ce qu'une transaction soit entièrement finalisée, elle empêche les autres transactions d'accéder aux données verrouillées, minimisant ainsi le risque de retour en arrière en cascade. Les verrous partagés peuvent être libérés avant le commit/rollback. B D D & 2PL stricte 28 PÔLE LÉ ONARD DE VINCI [email protected] 2PL stricte example T1 T2 T3 LOCK-X(A) LOCK-S(B) Attente pour LOCK-S(A) Attente pour LOCK-X(B) ROLLBACK LOCK-S(A) & i n t e r o p é r a b i l i t é Écrire (A) B D D LOCK-X(B) Dans cette situation, la base de données n'a pas besoin d'annuler les transactions T2 et T3 parce qu'elles n'ont pas lu les données non validées de T1 (pas d'effet de cascade). 29 PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é & B D D 30 2PL rigoureux Rigorous 2PL adopte une approche plus conservatrice en demandant à une transaction de conserver tous ses verrous, exclusifs LOCK-X et partagés LOCK-S, jusqu'à ce qu'elle soit validée ou annulée. Cette approche réduit les risques de blocage puisque les ressources sont contrôlées de manière plus stricte, mais elle diminue également le niveau des opérations concurrentes puisque les ressources verrouillées, qu'elles soient partagées ou exclusives, sont conservées pendant toute la durée de la transaction. PÔLE LÉ ONARD DE VINCI [email protected] Extension du 2PL T1 T2 LOCK-X(A) LOCK-X(B) Écrire (A) Attente pour LOCK-X(A) Attente pour LOCK-X(B) B D D & i n t e r o p é r a b i l i t é Écrire (A) 31 Le problème de Deadlocks n’est pas encore résolu!!! PÔLE LÉ ONARD DE VINCI B D D & i n t e r o p é r a b i l i t é [email protected] Protocoles basés sur les estampilles 32 Le but est d’avoir des ordonnancements sérialisables équivalents à l’ordre chronologique des transactions A chaque transaction est associée une estampille relative au moment où elle “arrive”, i.e. Ti avant Tj, ST(Ti) < ST(Tj) (l’heure système ou bien un simple compteur) A chaque valeur A de la base sont associées 2 estampilles: E_ST(A) : la plus grande des estampilles des transactions qui ont écrit A avec succès L_ST(A) : la plus grande des estampilles des transactions qui ont lu A avec succès PÔLE LÉ ONARD DE VINCI [email protected] Protocoles basés sur les estampilles Supposons que Ti veuille lire A Si ST(Ti) ≥ E_ST(A), Si ST(Ti) < E_ST(A), alors Ti est “annulée” et relancée avec une nouvelle estampille (car cela veut dire que Ti essaye de lire une valeur qui a été écrite par une transaction qui est arrivée après elle) B D D & i n t e r o p é r a b i l i t é alors la lecture est autorisée et L_ST(A) ← max{ L_ST(A), ST(Ti) } 33 PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é & B D D 34 Protocoles basés sur les estampilles Supposons que Ti veuille écrire A Si ST(Ti) < L_ST(A), Dans ce cas, cela veut dire qu’il y a une transaction qui est arrivée après Ti et qui a lu A. Ti est annulée Si ST(Ti) < E_ST(A), Si on laisse faire cette écriture, alors elle va “écraser” celle faite par une transaction arrivée après Ti. Ti est annulée Sinon, l’écriture est réalisée E_ST(D) ← ST(Ti) PÔLE LÉ ONARD DE VINCI Soient les transactions T1, T2, T3, T4 et T5 avec les estampilles resp. 1, 2, 3, 4 et 5. L’ordonnancement suivant représente une situation où T2 et T4 sont annulées B D D & i n t e r o p é r a b i l i t é [email protected] Protocole avec estampillage 35 PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é & B D D 36 Protocole avec estampillage L’estampillage permet d’éviter les blocages (les transactions sont exécutées ou bien annulées) Il garantit la sérialisabilité puisque tous les arcs sont de la forme Ti →Tj avec ST(Ti) < ST(Tj) Par contre, le problème de récupérabilité persiste. Si Ti est annulée alors que Tj a lu une valeur écrite par Ti, alors Tj doit aussi être annulée. Si Tj a déjà validé, alors l’ordonnancement n’est pas récupérable. PÔLE LÉ ONARD DE VINCI [email protected] L’exécution d’une transaction Ti se fait en 3 phases : Lecture : Les écritures se font sur des “variables locales” Validation : Tester la validité des écritures (ne violent elles pas la sérialisabilité ?) Ecriture : Si la validation réussit, alors les écritures sont retranscrites sur la base B D D & i n t e r o p é r a b i l i t é Protocole basé sur la validation 37 PÔLE LÉ ONARD DE VINCI [email protected] Pour faire le test de validité, nous avons besoin de savoir à quels moments ont lieu les différentes phases. D’où l’utilisation d’estampilles : Début(Ti): Le moment où Ti a débuté Validation(Ti): Le moment où Ti a terminé sa phase précédente Fin(Ti): Le moment où Ti termine la phase d’écriture B D D & i n t e r o p é r a b i l i t é Le test de validité 38 PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é & B D D 39 Le test de validité La sérialisabilité est testée en se basant sur un estampillage des transactions correspondant à leur estampille de validation, i.e., ST(Ti) = Validation(Ti). La validation de Tj réussit si pour chaque Ti telle que ST(Ti) < ST(Tj): Fin(Ti) < Début(Tj), ou bien Début(Tj) < Fin(Ti) < Validation(Tj) et l’ensemble des données écrites par Ti est distinct de celui des données lues par Tj Pour le 2ème point: Les écritures de Tj n’ont pas d’effet sur les lectures de Ti (elles ont lieu après la fin des lectures de Ti) Les écritures de Ti n’ont pas d’effet sur les lectures de Tj (Tj ne lit aucun objet écrit par Ti) PÔLE LÉ ONARD DE VINCI [email protected] i n t e r o p é r a b i l i t é & B D D 40 Gestion des blocages: Prévenir Soit Ti qui demande un verrou en conflit avec celui déjà détenu par Tj Privilégier les plus anciennes transactions (estampillage): ST(Ti) < ST(Tj) Ti peut attendre Tj ST(Ti) > ST(Tj) Ti est annulée Si Ti est relancée avec une nouvelle estampille, alors elle risque d’attendre longtemps!! La relancer avec la même estampille. Noter qu’ici, seules les transactions demandeuses sont annulés Privilégier la transaction qui déteint le verrou ST(Ti) < ST(Tj) Ti est annulée ST(Ti) > ST(Tj) Ti peut attendre Tj PÔLE LÉ ONARD DE VINCI B D D & i n t e r o p é r a b i l i t é [email protected] Gestion des blocages: blocages détection 41 Les blocages peuvent être décrits comme un graphe d'attente, qui consiste en une paire G = (V,E) V est un ensemble de sommets (toutes les transactions du système)E est un ensemble d'arêtes ; chaque élément est une paire ordonnée Ti →Tj. Si Ti → Tj se trouve dans E, il existe une arête dirigée de Ti vers Tj, ce qui signifie que Ti attend que Tj libère un élément d'information. Lorsque Ti demande une donnée détenue par Tj, l'arête Ti Tj est insérée dans le graphe d'attente. Cette arête n'est supprimée que lorsque Tj ne détient plus l'élément de données dont Ti a besoin. Le système est dans un état de blocage si et seulement si le graphe d'attente a un cycle. Il faut invoquer périodiquement un algorithme de détection des impasses pour rechercher les cycles. PÔLE LÉ ONARD DE VINCI B D D & i n t e r o p é r a b i l i t é [email protected] Récupération du blocage 42 Lorsqu'un blocage est détecté : Une transaction devra être annulée (victime) pour sortir du blocage. Sélectionnez la transaction victime qui entraînera un coût minimal. Annulation -- déterminer jusqu'où annuler la transaction Annulation totale : Abandonner la transaction puis la relancer. Il est plus efficace de ne reculer la transaction que jusqu'au point nécessaire pour sortir du blocage. La famine se produit si la même transaction est toujours choisie comme victime. Inclure le nombre de retours en arrière dans le facteur de coût pour éviter la famine. PÔLE LÉ ONARD DE VINCI [email protected] Chapiter 17 "Database System Concepts, Seventh Edition." Avi Silberschatz, Henry F. Korth, S. Sudarshan (2020) B D D & i n t e r o p é r a b i l i t é Aller plus loin 43 PÔLE LÉ ONARD DE VINCI