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 avancées Concurrence d'accès et reprise Dan VODISLAV CY Cergy

Bases de données avancées Concurrence d'accès et reprise Dan VODISLAV CY Cergy Paris Université Master Informatique M1 Cours BDA Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 2 Plan • La notion de transaction • Les problèmes de la concurrence – Problèmes de cohérence – Problèmes d'annulation • Contrôle de concurrence • Algorithmes – Verrouillage à deux phases – Verrouillage hiérarchique – Estampillage – Niveaux d'isolation • Reprise après panne • Concurrence et reprise dans Oracle Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 3 La notion de transaction • Modèle de base de données – On ne considère pas un modèle de données en particulier (ex. relationnel) – Base de données = ensemble d'articles nommés, contenant n'importe quel type de valeur • Modèle général, compatible avec n'importe quel type de BD Ex. x:5, y: "toto", z: 2.78 – Opérations possibles sur les articles: lecture, écriture, création, etc. – Plusieurs programmes qui s'exécutent en même temps et font des opérations sur la BD • On se limite pour l'instant à deux opérations de base – Lecture: v = Lire(x) – Écriture: Ecrire(x, v) Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 4 Programme et transaction • Programme – L'exécution d'un programme peut produire une séquence d'opérations – On ne s'intéresse qu'aux opérations de lecture/écriture dans la BD – La séquence peut être découpée en plusieurs sous-séquences, chacune pouvant être validée (Commit) ou annulée (Rollback) • Exemple: programme de débit d'un compte Débit (Article solde, int montant){ int temp = Lire(solde); if (temp < montant) Rollback; else {Ecrire(solde, temp-montant); Commit;} } • Séquences possibles à l'exécution – Lire(solde), Rollback – Lire(solde), Ecrire(solde), Commit Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 5 Transactions • Transaction – Séquence d'opérations sur la BD produite par l'exécution d'un programme – Terminée par validation (Commit) ou annulation (Rollback) – La transaction a une cohérence logique • La séquence a une signification logique • Elle part d’un état cohérent de la BD et la transforme en un autre état cohérent • Relation programme – transaction – Une transaction provient de l'exécution d'un programme – Une exécution de programme produit une séquence d'opérations, qui peut être découpée en plusieurs transactions – Toute opération de l'exécution fait partie d'une transaction – Des exécutions différentes d'un même programme peuvent produire des séquences d'opérations (donc aussi des transactions) différentes – Plusieurs exécutions d'un même programme peuvent être présentes en même temps dans le système Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 6 Propriétés ACID • Propriétés des transactions que le SGBD doit assurer – "Contrat" transactionnel entre l'utilisateur et le SGBD • Quatre propriétés – Atomicité: une transaction s'exécute soit en totalité soit pas du tout – Cohérence: une transaction respecte les contraintes d'intégrité de la BD – Isolation: une transaction ne voit pas les effets des autres transactions qui s'exécutent en même temps – Durabilité: les effets d'une transaction validée ne sont jamais perdus Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 7 Atomicité, cohérence • Atomicité: une transaction s'exécute soit en totalité soit pas du tout – Une exécution partielle de la transaction est inacceptable – Une transaction qui ne peut pas se terminer doit être annulée – L'annulation (Rollback) peut venir: • du programme: l'annulation du débit si solde insuffisant • du système: blocage ou incohérence dans l'exécution concurrente – Annulation annulation de toutes les modifications (écritures) • Cohérence: une transaction respecte les contraintes d'intégrité de la BD – Les contraintes expriment la cohérence de la BD • Contraintes sur les données: compte.solde ≥0, en permanence • Contraintes sur les opérations: dans un transfert entre deux comptes source.solde + dest.solde = constant – Une transaction mène la BD d'un état cohérent vers un autre état cohérent • Pendant la transaction l'état peut être incohérent! Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 8 Isolation, durabilité • Isolation: une transaction ne voit pas les effets des autres transactions qui s'exécutent en même temps – Les écritures des autres transactions en cours sur les données manipulés par la transaction en question ne sont pas visibles – C'est comme si chaque transaction s'exécutait toute seule dans le SGBD – Conséquence: l'exécution de plusieurs transactions concurrentes est équivalente à une exécution séparée, en série des transactions • Durabilité: les effets d'une transaction validée ne sont jamais perdus – On ne doit pas annuler une transaction validée Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 9 Les problèmes de la concurrence • Concurrence de transactions – Plusieurs transactions actives (pas terminées) en même temps – Vision client-serveur • Les transactions/programmes = clients qui envoient des demandes au SGBD (demandes de lecture ou d'écriture d'articles) • Le SGBD = serveur qui reçoit ces demandes et les exécute – Le SGBD exécute les opérations en séquence, pas en parallèle! Concurrence = entrelacement des opérations des transactions • Concurrence parfaite: toute opération est exécutée dès son arrivée – Problème: certains entrelacements ne sont pas corrects • Contrôle de concurrence – Modifier l'entrelacement pour produire une exécution correcte des transactions Retardement des opérations, perte de performances Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 10 Phénomènes indésirables • Perte d'une mise à jour Exemple: compte X avec un solde de 500 euros initialement • T1: débit de 100 euros, T2: débit de 200 euros • Ordre d'exécution: • Résultat: solde de 300 euros au lieu de 200 euros 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) T1 T2 temp1 = Lire(X)(500) temp2 = Lire(X)(500) Ecrire(X, 400) Ecrire(X, 300) Commit Commit Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 11 Phénomènes indésirables (suite) • Analyse incohérente Exemple: comptes X (500 euros) et Y (200 euros), total Z • T1: transfert de 100 euros de X vers Y; T2: écriture de la somme X+Y dans Z • 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 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 Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 12 Phénomènes indésirables (suite) • É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 euros; T2: pareil, mais avec 200 euros • 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") T1 T2 Ecrire(X, 100) Ecrire(X, 200) Ecrire(Y, 200) Ecrire(Y, 100) Commit Commit Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 13 Phénomènes indésirables (suite) • Dépendances non-validées Exemple: compte X avec un solde de 500 euros initialement • T1: débit de 100 euros finalement annulé; T2: débit de 200 euros • 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") T1 T2 temp1 = Lire(X)(500) Ecrire(X, 400) temp2 = Lire(X)(400) Ecrire(X, 200) Commit Rollback Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 14 Le problème des annulations • Annulation d'une transaction T  – Annulation des effets de T dans la BD (annulation des écritures de T) – Annulation des transactions qui utilisent les valeurs écrites par T (annulations en cascade à cause des dépendances non validées) • L'exemple des dépendances non validées montre que l'annulation d'une transaction peut avoir des effets indésirables • Catégories d'exécutions par rapport aux annulations – Non recouvrable: permet l'annulation en cascade de transactions validées – Recouvrable: permet l'annulation en cascade, mais seulement de transactions non-validées – Sans annulations en cascade: évite les annulations en cascade – Stricte: évite les annulations en cascade et permet l'annulation des écritures à l'aide d'un journal d'écritures avant Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 15 Recouvrabilité et annulations en cascade • La cause des annulations en cascade: les "lectures sales" – Question: quand risque-t-on d'annuler une transaction déjà validée? – Réponse: quand la transaction qui fait la lecture sale est validée avant la fin de celle qui a fait l'écriture • Exécution recouvrable: pas d'annulation de transaction validée – Méthode: retarder le Commit des transaction ayant fait une lecture sale • Remarque: le caractère recouvrable ou non d'une exécution ne dépend pas de la présence explicite d'un Rollback ! T1 T2 temp1 = Lire(X)(500) Ecrire(X, 400) temp2 = Lire(X)(400) Ecrire(X, 200) Commit Rollback Cours BDA (CY Cergy Paris Université/M1): Concurrence et reprise 16 Éviter les annulations en cascade • Pour éviter les annulations en cascade éviter les uploads/Finance/ concurrence.pdf