Remerciez-le!

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

BASES DE DONNÉES RÉPARTIES nicolas.lumineau@univ-lyon1.fr CM4 Master 1 MIF24 MI

BASES DE DONNÉES RÉPARTIES nicolas.lumineau@univ-lyon1.fr CM4 Master 1 MIF24 MIF24 EVALUATION DE REQUÊTES RÉPARTIES Evaluation de requêtes réparties Plan d’exécution réparti Modèles de coût Algorithmes de décomposition de requêtes Transactions réparties Garantir un accès concurrent à des données réparties 2 GESTION DE TRANSACTIONS CONTRÔLE DE CONCURRENCE EN CENTRALISÉ Remerciements : Hubert Naacke (LIP6) MIF24 TRANSACTIONS Transaction : séquence d’actions qui transforment une BD d’un état cohérent vers un autre état cohérent Actions : opérations de lecture et d’écriture de données de différentes granularités Granules = tuples, tables, pages disque, etc. BD dans un état cohérent La BD peut être dans un état incohérent Begin Transaction End Transaction Exécution BD dans un (autre) état cohérent MIF24 PROPRIÉTÉS DES TRANSACTIONS ATOMICITE : Les opérations entre le début et la fin d’une transaction forment une unité d’exécution (tout ou rien). COHERENCE : Chaque transaction accède et retourne une base de données dans un état cohérent (ex. pas de violation de contraintes d’intégrité). ISOLATION : Le résultat d’un ensemble de transactions concurrentes et validées correspond à une exécution successive des mêmes transactions (les mises à jour concurrentes sont invisibles) . DURABILITE: Les mises-à-jour des transactions validées persistent. EXEMPLE DE TRANSACTION SIMPLE Begin_transaction Budget-update Begin EXEC SQL UPDATE Project SET Budget = Budget * 1.1 WHERE Pname = ‘TheProjet’ End. {Budget-update} La validation (commit) est automatique à la fin de la transaction MIF24 PROPRIÉTÉS DES TRANSACTIONS ATOMICITE : Les opérations entre le début et la fin d’une transaction forment une unité d’exécution (tout ou rien). COHERENCE : Chaque transaction accède et retourne une base de données dans un état cohérent (ex. pas de violation de contraintes d’intégrité). ISOLATION : Le résultat d’un ensemble de transactions concurrentes et validées correspond à une exécution successive des mêmes transactions (les mises à jour concurrentes sont invisibles) . DURABILITE: Les mises-à-jour des transactions validées persistent. MIF24 QUESTION : QUE SE PASSE-T-IL ? 8 BD T1 = transfert( A,B, 100) A B C D E A B C D E A B C D E Compte Alice Compte Bob Compte Carla Granule A 500 € T2 = transfert( B, C, 100) Granule B 500 € Granule C 500 € MIF24 SI T1 EST COMPLÈTEMENT EFFECTUÉE AVANT T2 9 BD T1 = transfert( A,B, 100) A B C D E A B C D E A B C D E Compte Alice Compte Bob Compte Carla Granule A 400 € T2 = transfert( B, C, 100) Granule B 500 € Granule C 600 € MIF24 EXPLICATION T1 lit A X1=L1(A) T1 écrit sur A E1(A, X1-100) T1 lit B Y1 = L1(B) T1 écrit sur B E1(B, Y1 + 100) T2 lit B X2 = L2(B) T2 écrit sur B E2(B, X2 - 100) T2 lit C Y2 = L2(C) T2 écrit sur C E2(C, Y2 + 100) 10 A init: 500 B init: 500 C init: 500 500 400 500 600 600 500 500 600 T1 T2 MIF24 SI LA CONCURRENCE ENTRE T1 ET T2 EST MAL GÉRÉE 11 BD T1 = transfert( A,B, 100) A B C D E A B C D E A B C D E Compte Alice Compte Bob Compte Carla Granule A 400 € T2 = transfert( B, C, 100) Granule B 600 € Granule C 600 € MIF24 EXPLICATION T1 lit A X1=L1(A) T1 écrit sur A E1(A, X1-100) T1 lit B Y1 = L1(B) T2 lit B X2 = L2(B) T2 écrit sur B E2(B, X2 - 100) T2 lit C Y2 = L2(C) T2 écrit sur C E2(C, Y2 + 100) T1 écrit sur B E1(B, Y1 + 100) 12 A init: 500 B init: 500 C init: 500 500 400 500 500 400 500 600 600 MIF24 MORALITÉ La mauvaise gestion de la concurrence entre T1 et T2 vient de faire :  gagner 100€ à Bob perdre 100€ à la banque 13 Analyse du problème La première exécution (correcte aux attentes) n’est pas équivalente à la seconde. La transaction T2 a lu une valeur ‘sale’ du granule B La valeur lue faisait partie de l’état intermédiaire de T1 L’ordonnancement n’est donc pas correct MIF24 EXÉCUTION (OU HISTOIRE) Exécution : ordonnancement des opérations d’un ensemble de transactions Exemple H1= {W2(x) R1(x) R3(x) W1(x) C1W2(y) R3(y) R2(z) C2 R3(z) C3} T1: Read(x) T2: Write(x) T3: Read(x) Write(x) Write(y) Read(y) Commit Read(z) Read(z) Commit Commit MIF24 EXÉCUTION EN SÉRIE Exécution en série (histoire sérielle): histoire où il n’y a pas d’entrelacement des opérations de transactions T1: Read(x) T2: Write(x) T3: Read(x) Write(x) Write(y) Read(y) Commit Read(z) Read(z) Commit Commit Hs= W2(x) W2(y) R2(z) C2 R1(x) W1(x) C1 R3(x) R3(y) R3(z) C3 T2 T1 T3   MIF24 EXÉCUTION SÉRIALISABLE Opérations conflictuelles : deux opérations sont en conflit si elles accèdent le même granule et une des deux opérations est une écriture. Exécutions équivalentes : deux exécutions H1 et H2 d’un ensemble de transactions sont équivalentes (de conflit) si : l’ordre des opérations de chaque transaction et l’ordre des opérations conflictuelles (validées) sont identiques dans H1 et H2. Exécution sérialisable : exécution où il existe au moins une exécution en série équivalente. MIF24 EXÉCUTIONS ÉQUIVALENTES ET SÉRIALISABLES H1=W2(x) R1(x) R3(x) W1(x) C1 R3(y) W2(y) R2(z) C2 R3(z) C3 H2=W2(x) R1(x) W1(x) C1 R3(x) W2(y) R3(y) R2(z) C2 R3(z) C3 Hs= W2(x) W2(y) R2(z) C2 R1(x) W1(x) C1 R3(x) R3(y) R3(z) C3 H1 et H2 ne sont pas équivalentes ! H2 est équivalente à Hs, qui est sériel : donc H2 est sérialisable ! T1: Read(x) T2: Write(x) T3: Read(x) Write(x) Write(y) Read(y) Commit Read(z) Read(z) Commit Commit GRAPHE DE PRÉCÉDENCE (GP) Graphe de précédence GPH={V,P} pour l’exécution H: V={T | T est une transaction validée dans H} P={Ti Tk si aij Ti et akl Tk sont en conflit et aij< H akl} Théorème: l’exécution H est sérialisable ssi GPH ne contient pas de cycle. Exemple • H1= W2(x) R1(x) R3(x) W1(x) C1 R3(y) W2(y) W2(z) C2 R3(z) C3 • H2= W2(x) R1(x) W1(x) C1 R3(x) W2(y) R3(y) W2(z) C2 R3(z) C3 T2 T1 T3 H1 T2 T1 T3 H2 MIF24 CONTRÔLE DE CONCURRENCE MIF24 CONTRÔLE DE CONCURRENCE Objectif : synchroniser les transactions concurrentes afin de maintenir la cohérence de la BD, tout en maximisant le degré de concurrence (multi-utilisateurs) Principes: exécution simultanée des transactions pour des raisons de performance Exemple: exécuter les opérations d’une autre transaction quand la première commence à faire des accès disques les résultats doivent être équivalents à des exécutions non simultanées (isolation) besoin de raisonner sur l’ordre d’exécution des transactions MIF24 PROBLÈMES LIÉES À L’ISOLATION Perte d’écritures : L1(A) L2(A) W1(A) W2(A); L’écriture de T1 est perdue (exemple précédent) Lecture sale (lecture d’une mis à jour non ‘commitée’): W1(A); R2(A); … ; abort1; Non reproductibilité des lectures : L1(A); W2(A’→A); L1(A); pour A’ différent de la valeur initiale de A, alors T1 lit deux valeurs différentes. Lecture de tuples ‘fantôme’ : L1(A); W2(A→); L1(B); W2(B→B’); W2(→C); MIF24 LECTURE ‘SALE’ T1 lit B X1=L1(B) T2 lit A X2 = L2(A) T2 écrit sur A E2(A, X2 - 100) T1 lit A Y1=L1(A) T1 écrit sur B E1(B, X1 + Y1) T2 commit T1 commit 22 Lecture de A alors qu’il a été modifié par une autre transaction non encore ‘Commitée’ X abort MIF24 LECTURES ‘NON-RÉPÉTABLES’ T1 lit A X1=L1(A) T2 lit A X2 = L2(A) T2 écrit sur A E2(A, X2 - 100) T2 commit T1 lit A Y1=L1(A) T1 écrit sur B E1(B, X1 + Y1) T1 commit 23 La seconde lecture de A dans la même transaction ne retournera pas la même valeur MIF24 LECTURE ‘FANTÔME’ T1 lit A X1=L1(A) T1 lit B Y1=L1(B) T2 supprime B E2(B, ) T2 écrit sur A E2(A, X1 - 100) T1 lit C Z1=L1(C) T2 insère D E1(,D) T2 commit T1 commit 24 D était potentiellement pertinent pour T1. A n’est potentiellement plus pertinent pour T1. B sera considéré à la fin de T1 alors qu’il n’existe plus MIF24 CONCRÈTEMENT SOUS ORACLE Les différents niveaux d’isolation (10g) READ UNCOMMITED Permet à une transaction de lire des données qui ont été changées mais pas encore validées READ COMMITED Assure qu’une transaction lit seulement des données validées REPETABLE READ Place un verrou sur les données lues pour garantir que toute relecture de la valeur dans la même transaction retournera le même résultat SERIALIZABLE Assure qu’une transaction ne prend en compte que les données validées avant le démarrage de la transaction 25 MIF24 CONCRÈTEMENT SOUS ORACLE Paramétrage du niveau d’isolation (11g) 26 Niveau d’isolation Lecture ‘sale’ Lecture ‘non répétable’ Lecture ‘fantôme’ READ UNCOMMITTED Possible Possible Possible READ COMMITTED Impossible Possible Possible REPEARTABLE READ Impossible Impossible Possible SERIALIZABLE Impossible Impossible Impossible MIF24 CONCRÈTEMENT SOUS ORACLE Paramétrage du niveau d’isolation (11g) Par défaut, Oracle est en « READ COMMITTED» 27 Niveau d’isolation Lecture ‘sale’ Lecture ‘non répétable’ Lecture ‘fantôme’ READ UNCOMMITTED Possible Possible Possible READ COMMITTED Impossible Possible Possible REPEARTABLE READ Impossible Impossible Possible SERIALIZABLE Impossible Impossible Impossible MIF24 QUESTION Pourquoi ne pas être par défaut en ‘SERIALIZABLE’? 28 C’est le niveau le plus restrictif qui uploads/Finance/ transaction.pdf