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 M1-SEM Dr. A. TACHOUCHE VII. contrôle de la concurren

Bases de Données Avancées M1-SEM Dr. A. TACHOUCHE VII. contrôle de la concurrence et reprise sur panne Rappels et notions de base • 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 BDD, Ex. x:5, y: "moi", 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) 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 Bases de Données Avancées M1-SEM Dr. A. TACHOUCHE Transactions – 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 Propriétés ACID • Quatre propriétés des transactions que le SGBD doit assurer – 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 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 Bases de Données Avancées M1-SEM Dr. A. TACHOUCHE • 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 Un SGBD doit garantir que l’exécution d’un programme effectuant des mises à jour dans un contexte multi-utisateur s’effectue “correctement”. Bien entendu la signification du “correctement” doit être définie précisément, de même que les techniques assurant cette correction : c’est l’objet du contrôle de concurrence. 1. Les mécanismes Le contrôle de concurrence est la partie de l’activité d’un SGBD qui consiste à ordonner l’exécution des transactions de manière à assurer la sérialisabilité et la recouvrabilité. Nous commençons par décrire les mécanismes assurant la recouvrabilité, avant de passer à la gestion de la sérialisabilité. Versionnement Il existe toujours deux choix possibles pour une transaction TT en cours : effectuer un ”commit” pour valider définitivement les opérations effectuées, ou un ”rollback” pour les annuler. Pour que ces choix soient toujours disponibles, le SGBD doit maintenir, pendant l’exécution de T, deux versions des données mises à jour : une version des données après la mise à jour ; une version des données avant la mise à jour. Ces deux versions sont stockées dans deux espaces de stockage séparés, que nous désignerons respectivement par les termes d’image après et d’image avant dans ce qui suit. Conceptuellement, le déroulement d’une transaction T, basé sur ces deux images, s’effectue de la manière suivante. Chaque fois que T effectue la mise à jour d’un tuple, la version courante est d’abord copiée dans l’image avant, puis remplacée par la nouvelle valeur fournie par T. Dès lors le ”commit” et le ”rollback” sont implantés comme suit : le ”commit” consiste à s’assurer que les données de l’image après sont vraiment écrites sur disque, afin de garantir la durabilité ; l’image avant peut alors être effacée ; le ”rollback” prend les tuples de l’image avant et les écrit dans l’image après pour ramener la base à l’état initial de la transaction. Un ”rollback” effectué à la suite d’une panne fonctionne de la même manière, sous réserve bien entendu que la panne n’ait pas affecté l’image avant elle-même. Il est donc très important de s’assurer que les données de l’image avant sont régulièrement écrites sur disque. Pour des raisons de performance (répartition des entrées/sorties) et de minimisation des risques, on choisit d’ailleurs quand c’est possible de placer l’image avant et l’image après sur des disques différents. Quand T effectue des lectures sur des données qu’elles viennent de modifier, le système doit lire dans l’image après pour assurer une vision cohérente de la base, reflétant les opérations effectuées par une Bases de Données Avancées M1-SEM Dr. A. TACHOUCHE transaction. En revanche, quand c’est une autre transaction T’ qui demande la lecture d’un tuple modifié par T, il faut lire dans l’image avant pour éviter les effets de lectures sales. On peut se poser la question du nombre de versions nécessaires. Que se passe-t-il par exemple quand T’ demande la mise à jour d’un tuple déjà modifié par T ? Si cette mise à jour était autorisée, il s’agirait d’une écriture sale et il faudrait prendre garde à créer une troisième version du tuple, l’image avant de T’ étant l’image après de T. La multiplication des versions rendrait la gestion des ”commit” et ”rollback” extrêmement complexe. En pratique les systèmes n’autorisent pas les écritures sales, s’appuyant pour contrôler cette règle sur des mécanismes de verrouillage exclusif qui seront présentés dans ce qui suit. Il s’ensuit que la gestion de la recouvrabilité ne nécessite pas plus de deux versions pour chaque tuple, une dans l’image avant et l’autre dans l’image après. Le versionnement n’est pas seulement utile à la gestion de la recouvrabilité. Reprenons le problème des lectures non répétables. Elles sont dues au fait qu’une transaction T lit un tuple t qui a été modifié par une transaction T’ après le début de T. Or, quand T’ modifie t, il existe avant la validation deux versions de t : l’image avant et l’image après. Il suffirait que T lise toujours l’image avant pour que le problème des tuples fantômes soit résolu. En d’autres termes ces images avant peuvent être vues comme un “cliché” de la base pris à un moment donné, et toute transaction ne lit que dans le cliché valide au moment où elle a débuté. De nombreux SGBD (dont ORACLE, PostgreSQL, MySQL/InnoDB) proposent un mécanisme de lecture cohérente basé sur ce système de versionnement qui s’appuie sur les principes suivants : chaque transaction T se voit attribuer, quand elle débute, une estampille temporelle eTeT ; chaque valeur d’estampille est unique et les valeurs sont croissantes : on garantit ainsi un ordre total entre les transactions. chaque version validée d’un tuple a est de même estampillée par le moment eaea de sa validation ; quand T doit lire un tuple a, le système regarde dans l’image après. Si t a été modifié par T ou si son estampille est inférieure à eTeT, le tuple peut être lu puisqu’il a été validé avant le début de T, sinon T recherche dans l’image avant la version de t validée et immédiatement antérieure à eTeT. La seule extension nécessaire par rapport à l’algorithme de gestion de la recouvrabilité est la non- destruction des images avant, même quand la transaction qui a modifié le tuple valide par ”commit”. L’image avant contient alors toutes les versions successives d’un tuple, marquées par leur estampille temporelle. Seule la plus récente de ces versions correspond à une mise à jour en cours. Les autres ne servent qu’à assurer la cohérence des lectures. La figure suivante illustre le mécanisme de lecture cohérente. La transaction T23T23 a débuté à l’instant 23. Elle a modifié à l’instant 25 l’enregistrement e3, et la version précédente (dont l’estampille est 14) de e3 a été placée dans l’image avant. Maintenant, si T23T23 effectue une lecture, celle-ci accède à la version de e3e3 placée dans l’image après puisque c’est elle qui l’a modifiée. En revanche une transaction T′18T18′ dont le moment de début est 18 lira la version de e3 dans l’image avant (il y a un pointeur de l’image avant vers l’image après). Bases de Données Avancées M1-SEM Dr. A. TACHOUCHE En d’autres termes l’image avant uploads/Litterature/cour-7-bda.pdf