Remerciez-le!

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

Cours “Bases de données” Concurrence d’accès 3° année (MISI) Antoine Cornuéjols

Cours “Bases de données” Concurrence d’accès 3° année (MISI) Antoine Cornuéjols www.lri.fr/~antoine antoine.cornuejols@agroparistech.fr Contrôle de la concurrence d’accès 1. Introduction 1.1. Systèmes multi-utilisateurs 1.2. Pourquoi contrôler 2. Concepts des transactions 3. Techniques de contrôle de la concurrence 3.1. Verrouillage à deux phases 3.2. Contrôle par tri des estampilles 3.3. Autres problèmes Contrôle de la concurrence d’accès 1. Introduction 1.1. Systèmes multi-utilisateurs 1.2. Pourquoi contrôler 2. Concepts des transactions 3. Techniques de contrôle de la concurrence 3.1. Verrouillage à deux phases 3.2. Contrôle par tri des estampilles 3.3. Autres problèmes Contrôle de concurrence 4 Introduction GSBD Multi-utilisateurs Souvent des centaines, voire des milliers d’utilisateurs E.g. : système de réservation de sièges dans les compagnies aériennes ; opérations bancaires ; ... Contraintes de temps réel Comment éviter les interactions négatives entre les différents utilisateurs et garantir la cohérence de la base de données ? Contrôle de concurrence 5 Introduction Transaction Programme formant une unité logique de traitement Souvent délimitée par des instructions de début et de fin de transaction Lire_element(x) lit un élément nommé x et le stocke dans une variable de programme. (On suppose que la variable de programme se nomme aussi x). Opérations élémentaires d’accès à la base de données : Ecrire_element(x) écrit la valeur de la variable de programme x et le stocke dans l’élément de données x. Contrôle de concurrence 6 Introduction T1 ____________________________ lire_element(X); X := X-N ; ecrire_element(X); lire_element(Y); Y := Y +N ; ecrire_element(Y); Exemples : T2 ____________________________ lire_element(X); X := X + M ; ecrire_element(X); Accède à {X,Y} Accède à {X} Contrôle de concurrence 7 Introduction : pourquoi contrôler ? Mises à jour perdues T1 T2 lire_element(X); X := X-N; ecrire_element(X); lire_element(Y); Y := Y + N; ecrire_element(Y); lire_element(X); X := X + M; ecrire_element(X); L’élément X a une valeur incorrecte car sa mise à jour par T1 est “perdue” (écrasée). Contrôle de concurrence 8 Introduction : pourquoi contrôler ? T1 T2 lire_element(X); X := 80 - 5; ecrire_element(75); lire_element(Y); Y := 20 + 5; ecrire_element(25); lire_element(X); X := 80 + 3; ecrire_element(83); L’élément X a une valeur incorrecte car sa mise à jour par T1 est “perdue” (écrasée). X = 83 et Y = 25 au lieu de X = 78 et Y = 25 Mises à jour perdues Contrôle de concurrence 9 Introduction : pourquoi contrôler ? Mises à jour temporaires (ou “lectures sales”) T1 T2 lire_element(X); X := X-N; ecrire_element(X); lire_element(Y); lire_element(X); X := X + M; ecrire_element(X); La transaction T1 échoue et doit rétablir l’ancienne valeur de X ; au même moment, T2 a lu la valeur “temporaire” Anomalies transactionnelles 10 Lecture impropre L'utilisateur 1 ajoute 10 places et annule sa transaction, l'utilisateur 2 veut 7 places si elles sont disponibles... Contrôle de concurrence 11 Introduction : pourquoi contrôler ? Résumés incorrects T1 T3 lire_element(X); X := X-N; ecrire_element(X); lire_element(Y); Y := Y + N; ecrire_element(Y); somme := 0; lire_element(A); somme := somme + A; . . . lire_element(X); somme := somme + X; lire_element(Y); somme := somme + Y; T3 lit X après que N ait été soustrait et lit Y avant que N ne soit ajouté. Il en résulte un résumé incorrect (différence de N). Anomalies transactionnelles 12 Lecture non répétable Cas où notre opérateur désire toutes les places d'un vol si il y en à plus de 4... Anomalies transactionnelles 13 Lecture fantôme Notre utilisateur 2 désire n'importe quel vol pas cher pour emmener son équipe de foot (soit 11 personnes) à une destination quelconque. Résultat : 11 places volatilisées du vol AF111 (histoire hélas véridique ...!) Anomalies transactionnelles 14 Lecture fantôme 15 Introduction : Isolation des transactions Phénomènes indésirables : Contrôle de concurrence Lecture sale : Une transaction lit des données écrites par une transaction concurrente mais non validée Lecture non reproductible : Une transaction lit de nouveau des données qu’il a lues précédemment et trouve que les données ont été modifiées par une autre transaction (qui a validé depuis la lecture initiale) Lecture fantôme : Une transaction ré-exécute une requête renvoyant un ensemble de lignes satisfaisant une condition de recherche et trouve que l’ensemble des lignes satisfaisant la condition a changé à cause d’une transaction récemment validée. Contrôle de la concurrence d’accès 1. Introduction 1.1. Systèmes multi-utilisateurs 1.2. Pourquoi contrôler 2. Concepts des transactions 3. Techniques de contrôle de la concurrence 3.1. Verrouillage à deux phases 3.2. Contrôle par tri des estampilles 3.3. Autres problèmes 17 Introduction : Importance de la reprise toutes les opérations de la transaction ont bien réussi et que leurs effets ont bien été enregistrés dans la base de données la transaction n’a aucun effet sur la base de données ou sur toute autre transaction Le SGBD doit vérifier que : Contrôle de concurrence ou bien que : 18 Introduction : Importance de la reprise Types de pannes : Contrôle de concurrence Panne informatique (crash système) : affectent surtout la mémoire centrale Erreur de la transaction ou erreur système : (e.g. erreur d’opération (débordement, division par zéro)) Erreur locale ou conditions d’exception détectées par la transaction : ne doit pas être considérée comme une panne mais traitée au niveau de la transaction Application du contrôle de la concurrence : E.g. si situation d’interblocage Panne de disque Problèmes physiques ou catastrophes Contrôle de concurrence 19 Concept de transaction Transaction Unité atomique de travail soit totalement terminée ; soit pas du tout. DEBUT_TRANSACTION LIRE ou ECRIRE FIN_TRANSACTION COMMIT signale que la transaction s’est bien terminée. ROLL-BACK signale que la transaction ne s’est pas bien terminée. Toutes les modifications effectuées doivent être annulées. Opérations surveillées : Contrôle de concurrence 20 Concept de transaction Les opérations de transaction sont écrites dans un journal archivé sur disque dur et sur sauvegarde. [début_transaction, T] : indique que la transaction a démarré [ecrire_element, T, x, ancienne_valeur, nouvelle_valeur] [lire_element, T, x] [valider, T] : indique que la transaction s’est terminée sans problème et que ses opérations peuvent être validées (enregistrées de façon permanente dans la base de données) [annuler, T] : indique que T a été annulée. Contrôle de concurrence 21 Concept de transaction Les propriétés ACID Atomicité. Une transaction est une unité atomique de traitement. Cohérence. Une transaction préserve la cohérence si son exécution complète fait passer la base de données d’un état cohérent à un autre. Isolation. Les résultats d’une transaction doivent être invisibles pour les autres transactions tant qu’elle n’est pas validée. Autrement dit, les exécutions ne doivent pas interférer les unes avec les autres. Durabilité. Les changements appliqués à la BD par une transaction validée doivent persister dans celle-ci. Ces changements ne doivent pas être perdues, même à la suite d’une défaillance. Contrôle de concurrence 22 Concept de transaction Sérialisabilité Les accès simultanés aux mêmes objets d’une BD doivent être sérialisés pour que ses utilisateurs puissent travailler indépendamment les uns des autres. Un ensemble de transactions concurrentes est correctement synchronisé si leur exécution séquentielle génère un état de la BD identique à celui qui serait obtenu si elles étaient exécutées indépendamment (par un seul utilisateur). Contrôle de concurrence 23 Concept de transaction Équivalence d’exécutions Deux exécutions sont équivalentes si : Ont les mêmes transactions et les mêmes opérations Produisent les mêmes effets sur la base Produisent les mêmes effets dans les transactions T1 = r1[x] x=x*5 w1[x] C1 T2 = r2[x] x=x+10 w2[x] C2 T1 T2 non équivalent à T2 T1 Contrôle de concurrence 24 Sérialisabilité Graphe de précédence pour la donnée b LOG (b) ________________________ T2 : READ T1 : READ T2 : WRITE T1 : READ T2 T1 READ-WRITE WRITE-WRITE Contrôle de concurrence 25 Sérialisabilité Critère de sérialisabilité Un ensemble de transactions est sérialisable si le graphe de précédence correspondant ne contient aucun cycle. Traitement et optimisation des requêtes Exercices Détecter les conflits et construire les graphes de sérialisation pour les exécutions suivantes. Indiquer les exécutions sérialisables et vérifier s'il y a des exécutions équivalentes. H1: w2[x] w3[z] w2[y] c2 r1[x] w1[z] c1 r3[y] c3 H2: r1[x] w2[y] r3[y] w3[z] c3 w1[z] c1 w2[x] c2 H3: w3[z] w1[z] w2[y] w2[x] c2 r3[y] c3 r1[x] c1 Contrôle de concurrence 27 Concept de transaction Prise en charge par SQL Pas d’instruction Debut_Transaction Chaque instruction doit avoir une instruction finale explicite : COMMIT ou ROLLBACK. Chaque transaction possède certaines caractéristiques spécifiées par une instruction SET TRANSACTION. Mode d’accès, taille, taille de la zone de diagnostic, niveau d’isolation. Contrôle de concurrence 28 Concept de transaction Prise en charge par SQL Type de violation Niveau d’isolation Lecture sale Lecture non reproductible Lecture fantôme READ UNCOMMITTED Oui Oui Oui READ COMMITTED Non Oui Oui REPEATABLE READ Non Non Oui SERIALIZABLE Non Non Non Contrôle de concurrence 29 Concept de transaction Exemple de transaction SQL EXEC SQL WHENEVER SQLERROR GOTO UNDO; EXEC SQL SET TRANSACTION READ WRITE DIAGNOSTIC SIZE 5 ISOLATION LEVEL SERIALIZABLE; EXEC SQL INSERT INTO EMPLOYE (PRENOM, NOM, NOSS, NoSce, SALAIRE) VALUES (‘Robert’, ‘Forgeron’, ‘1550222111999’, 2, 35000); EXEC SQL UPDATE EMPLOYE SET SALARY = SALARY * 1.1 WHERE NOSERVICE = 2; EXEC SQL COMMIT; GOTO LA_FIN; UNDO: EXEC SQL ROLLBACK; LA_FIN: ...; Contrôle de la concurrence d’accès 1. uploads/Finance/ cours-bd-concurrence-2007-pdf.pdf