Concurrence

Gestion de la concurrence

Bibliographie •

C.J. Date -- An introduction to database systems, Addison Wesley.

•

H. Garcia-Molina, J.D. Ullman, J. Widom -- Database system implementation. Prentice Hall.

•

R. Chapuis -- Les bases de données Oracle 8i. Développement, administration, optimisation. Dunod.

Introduction Une BD est une réservoir commun de données qui doit être partagé entre plusieurs utilisateurs concurrents. Exemple d’interactions avec une BD : Commandes SQL, Bloc PL/SQL, programme externe, … De nombreux problèmes se posent :  Concurrence d’accès difficile à maîtriser : qui peut accéder aux données ? Pour combien de temps ?…  Assurer la cohérence des données : gestion des mises à jours.

Contrôle des transactions Informellement, une transaction est une unité « logique » d’opérations d’interrogation ou de modifications d’une base de données formant un tout i.e. dont l’ensemble doit être soit validé soit annulé.

Une transaction démarre par l’exécution de n’importe quel ordre SQL.

Elle se termine soit de façon implicite (arrêt normal ou anormal de session, nouvel ordre de définition d’objet, etc…) soit de façon explicite par l’un des deux ordres COMMIT ou ROLLBACK.

Contrôle des transactions – commit, rollback COMMIT : termine une transaction par validation des données; rend accessible aux autres utilisateurs les modifications effectuées pendant la transaction; relâche les verrous (cf. plus tard pour cette notion). ROLLBACK : termine une transaction par l’annulation de toutes les modifications de données effectuées; relâche les verrous. Lorsqu’une transaction est longue, ont peut vouloir établir des points de sauvegardes intermédiaires de façon à pouvoir : - valider toutes les modifications ou, - valider une partie d’entre elles et en annuler d’autres le cas échéant.

Contrôle des transactions – savepoint On crée un point de sauvegarde par : SAVEPOINT <nom_repere>; Pour annuler la partie de la transaction depuis un point de repère, on exécute : ROLLBACK TO [SAVEPOINT] <nom_repere>; Exemple : UPDATE TABLE T… SAVEPOINT a DELETE FROM TABLE SAVEPOINT b UPDATE TABLE T’… COMMIT

UPDATE TABLE T… SAVEPOINT a DELETE FROM TABLE SAVEPOINT b UPDATE TABLE T’… ROLLBACK TO a

Validation de toute la transaction

Annule les ordres après le point a mais conserve les autres.

Concurrence de transactions L’intégrité des données d’une base est préservée par les mises à jours de transactions si celles-ci font passer la base d’un état cohérent à un autre état cohérent. Cohérence : définie par les contraintes d’intégrité posées sur les objets de la base à la création notamment.

Deux transactions sont concurrentes si elles sont exécutées simultanément par le serveur et accèdent aux même données.  Peut entraîner des anomalies (perte d’intégrité) même si chaque transaction, prise séparément, préserve l’intégrité interne.

Concurrence de transactions

T1

T2 Exécutions entrelacées

Exécutions en série

Deux transactions T1 et T2 interfèrent si le résultat de l’exécution en parallèle (entrelacée) de T1 et T2 est différent du résultat de l’exécution en série de T1 et T2 (T1 puis T2 ou T2 puis T1).

Trois problèmes de concurrence Les transparents qui suivent illustrent trois problèmes fréquents lié aux accès concurrents non contrôlés dans une base de données. Begin T Lire A A := A + 10 Ecrire A End T

« Lire A » : Lire une donnée A de la base (select into de PL/SQL, par exemple) « Ecrire A » : Ecrire dans la base (update ou insert de SQL) « A := A + 10 » : affectation locale

Mises à jours perdues (lost update problem) Begin T1 Begin T2 Lire A Lire C Lire A A := A + 10 A=A+C Ecrire A End T1 Ecrire A Supprimer C End T2

Si A = 5 et C = 15 au début, - Que vaut A dans la base à la fin ? - Que s’est il passé ? - Quels seraient les résultats des deux exécutions en série possibles ?

La mise à jour de T1 est perdue….

Lectures impropres (Uncommited dependancy problem ) Begin T1 Lire A A=A+20 Ecrire A Begin T2 Lire C Lire A A=A+C Ecrire A Supprimer C End T2 Rollback T1 End T1

Si A=10 au début, quelle est sa valeur à la fin ? Quels sont les résultats des exécutions en série. La valeur de A lue par T2 est impropre (à cause de l’annulation qui suit). Effet Domino : l’annulation d’une transaction T entraîne l’annulation de toute transaction ayant utilisé les résultats partiels de T et ainsi de suite….

Lecture non reproductible (Inconsistent analysis problem ) Begin T1 Lire A … …

Begin T2 Lire C Lire A A=A+C Pas de Ecrire A modification de A … Supprimer C … End T2 Lire A End T1

Si A=10 au début, quelles sont les valeurs de A lues par T1 ? T1 lit deux valeurs différentes sans avoir modifié A….

Remarques sur les 3 problèmes Dans les exemples précédents, les ensembles de données modifiées par T1 et T2 ne sont pas disjoints. C’est la source de l’interférence. Nécessité d’avoir un mécanisme permettant de gérer au mieux l’exécution des transactions concurrentes. 2 extrêmes

Exécution des transactions les unes après les autres

Exécution anarchique des transactions

 : Sécurité maximale  : Rigide, lent, plus aucun avantage lié au parallélisme

 : Tire profit de la concurrence (Rapidité)  : Contraintes d’intégrité violées

Sérialisabilité Sans exécuter les transactions les uns après les autres (en série), on cherche à obtenir un mode d’exécution qui fournit des résultats similaires. On définit pour cela le concept d’exécution sérialisée.

Sérialisation : imbrication de transactions dont les effets sont identiques à ceux d’une exécution en série de ces transactions. Dans les problèmes vus jusqu’ici les exécutions ne sont pas sérialisés : les résultats obtenus (ou observés) étaient différents des exécutions de T1 puis T2 ou de T2 puis T1.

Exemple d’exécution sérialisée

Begin T1 Begin T2 Lire A Lire C Lire A C=C+A Lire B B := A + 10 Ecrire B End T1 Ecrire C Supprimer C End T2

Si A = 5, B= 10, C = 15, au début, -Que valent A, B et C dans la base à la fin ? -Aurait-on obtenu le même résultat en exécutant T1 puis T2 ou T2 puis T1 ?

Propriétés ACID Idéalement, on attend des transactions qu’elles vérifient les 4 propriétés suivantes : • • • •

A - Atomicité : Toute la transaction doit être validée ou aucune de ses actions ne doit l’être (Tout ou rien). C - Cohérence : Chaque transaction préserve la consistance de la base i.e. la laisse dans un état cohérent. I - Isolation (correspond à sérialisation) D - Durée : une fois validées, les mises à jour des transactions survivent dans la base de données, même en cas de crash

Résolution de l’interférence Il existe plusieurs méthodes pour résoudre les problèmes d’interférence dans l’exécution de transactions. Parmi elles: • •

Les mécanismes de verrouillage, Les mécanismes d’estampillage.

On va donner quelques détails sur le verrouillage dans ce cours.

Verrouillage • • • •

Principe général du verrouillage Problème lié au verrouillage. l’interblocage. Qu’est ce que l’on peut verrouiller ? granularité, verrouillage hiérarchisé. Comment verrouiller ? Protocole à deux phases.

A voir dans ce qui suit….

Principe du verrouillage Principe : Une transaction veut se réserver l’usage (exclusif ou partagé) d’une donnée aussi longtemps que nécessaire.  Elle va chercher à poser un verrou sur cette donnée. Dans ce qui suit, on suppose que l’on peut poser deux types de verrous : • LockR A : verrou partagé sur A (avant lecture de A : select) • LockX A : verrou exclusif sur A (avant écriture sur A: insert, update, delete, …). On suppose aussi que chaque transaction demande à poser un verrous correspondant avant de faire l’action et ne relâche celui-ci (par Unlock) qu’à la fin de la transaction. On réexamine nos trois exemples sous cet angle…

Mises à jours perdues Avec pose de verrous : Begin T1 LockX A Lire A A := A + 10 Ecrire A Unlock A End T1

Begin T2 LockR C Lire C Attente pour verrouillage de A

LockX A Lire A A=A+C Ecrire A Unlock A End T2

Les deux transactions commencent à s’exécuter « en parallèle », puis T2 attend la libération du verrous posé par T1 sur A. L’exécution est sérialisée : identique, dans ses effets, à la série T1 puis T2.

Lectures impropres Pose de verrous : Begin T1 Begin T2 LockX A LockR C Lire A Lire C A=A+20 Ecrire A Rollback T1 Unlock A LockX A End T2 Lire A A=A+C Ecrire A Unlock A,C End T2

L’annulation de T1 relâche le verrou et T2 peut s’en emparer et continuer…

Lecture non reproductible (Inconsistent analysis problem ) Begin T1 LockS A Lire A … Pas de modification de A … Lire A Unlock A End T1

Begin T2 LockS C Lire C … … Attente pour Verrouillage de A … LockX A Lire A A=A+C Ecrire A etc…. End T2

Cette fois T2 attend la libération de A…

Verrouillage et interblocage Un problème important peut survenir lié au verrouillage Begin T1 LockR A … … LockX B ? Demande de verrous X pour écriture sur B : attente de la libération par T2

Begin T2 LockR B …. ...

Dans ce scénario (fréquent), T1 attend T2 qui attend T1.

Il y a interblocage!!! LockX A ? Demande de verrous X pour écriture sur A : attente de la libération par T1

On ne peut en sortir sans intervention du système.

Interblocage Ce phénomène apparaît lorsque deux ou plusieurs transactions s’attendent mutuellement (pour pouvoir poser des verrous sur certaines données, par exemple). Deux solutions : •

Faire en sorte que cela ne se produise pas (mécanismes de prévention d’interblocage par estampillage, notamment).

•

Détecter puis résoudre l’interblocage.

Détection de l’interblocage Se fait en deux temps : -

On commence par construire un graphe d’attente (en regardant le journal des transactions) : T1 attend T2, T3 attend T2, etc… T2

T1 T3

T4

T5

- On détecte (par une recherche de cycle(s) dans le graphe) s’il y a un interblocage. Si oui, une ou plusieurs transactions (bien choisies) doivent être interrompues et relancées plus tard.

Niveaux de verrouillage Constat : Il n’est pas utile de bloquer une relation entière pour modifier un tuple… On peut vouloir poser des verrous sur des objets de taille très différentes. On parle alors de granularité de verrouillage. Au niveau « logique » : base toute entière, relation, un groupe de tuples, un tuple, un champs d’un tuple…. Au niveau « physique » : fichier, blocs ou groupes de blocs. On peut tirer profit de cette hiérarchie pour affiner le mécanisme de verrouillage et de le rendre plus efficace.

Verrouillage hiérarchisé Verrou d’intention : verrous placés sur certains objets pour signaler que des objets plus petits (plus bas dans la hiérarchie) sont verrouillés et qui autorisent certaines formes d’accès aux autres objets plus petits. On passe d’un système à deux verrous S (Shared = partagé) et X (eXclusif) à un mécanisme utilisant 5 types de verrous différents : X, S, IX, IS, SIX • •

X (eXclusive) : Verrouillage exclusif (écriture), verrouillage X implicite pour tous les fils. S (Shared) : Verrouillage partagé (accès concurrent en lecture autorisé), verrouillage S implicite pour tous les fils.

Verrouillage hiérarchisé •

IS (Intention Shared) : Verrouillage d’intention partagé, permet le verrouillage en mode S ou IS par la suite sur les fils.

•

IX (Intention eXclusive) : Verrouillage d’intention exclusif, permet le verrouillage en mode IX ou X sur ce nœud ou sur ses fils par la suite.

•

SIX (S+IX) : Verrou partagé et intention exclusif, de même que IX mais avec un verrouillage implicite des fils en mode S.  A utiliser lorsque l’on souhaite lire un grand nombre de fils (évite de verrouiller explicitement chacun).

Verrous hiérarchisés – Compatibilités Demandé

X

X

N

N

SIX

N

IX

Posé

SIX IX

S

IS

N

N

N

N

N

N

O

N

N

O

N

O

S

N

N

N

O

O

IS

N

O

O

O

O

X

SIX

IX

S

IS

Pose de verrous hiérarchiques Protocole : les verrous sont posés du haut vers le bas de la hiérarchie. Ils sont relâchés du bas vers le haut. De plus : • Avant de pouvoir poser un verrou S ou IS sur un objet, une transaction doit avoir posé un verrou IS (ou supérieur) sur le nœud parent. • Avant de pouvoir poser un verrou X, IX ou SIX sur un objet, une transaction doit avoir posé un verrou IX (ou supérieur) sur le nœud parent. • Tout verrou X (resp. S et SIX) posé sur un objet implique un verrouillage implicite de type X (resp. de type S) de tous les enfants de cet objet.

Pose de verrous hiérarchiques Transaction T: lire le tuple t1. IS

S

t1

R2 SIX

R1

IS

t2

Base IX

th

R3

Transaction S : Lire tous les tuples de R2 et modification éventuelle de certains d’entre eux…

Pose de verrous hiérarchiques 2

IS IS

Transaction T : lire le tuple t1.

Base IX

Transaction S : Ecrire sur le tuple tk IS

S R2 IX

R1

R3 Transaction S’ : lire la relation R2. Incompatible avec S!

S

t1

t2

th

tk X

Protocole de verrouillage à deux phases Indépendamment de la taille (granularité) des objets verrouillés, on peut mettre au point un protocole sur l’ordre de pose et de relâchement des verrous qui assure la sérialisabilité.

Une transaction est dite bien formée si : •

Chaque lecture ou écriture est précédée de la pose d’un verrou adéquat.

•

Aucun granule ne reste verrouillé après la fin d’une transaction.

Protocole de verrouillage à deux phases Une transaction suit un protocole de verrouillage à deux phases si elle possède : •

Une seule phase croissante d’acquisition de verrous, suivie par

•

Une phase décroissante de libération de verrous.

Autrement dit : dès qu’une donnée a été déverrouillée, tout verrouillage nouveau est interdit !

Protocole de verrouillage à deux phases Scénario : Nombre de granules verrouillés

Temps Phase de verrouillage

Phase de déverrouillage

« Théorème » : Si chaque transaction est bien formée et suit le protocole de verrouillage à deux phases alors tout ordonnancement de transactions est équivalent à un ordonnancement séquentiel (i.e. est sérialisé). Mais n’évite pas les interblocages !!!!

Compléments : les niveaux d’isolation Un niveau d’isolation d’une transaction T définit le degré « d’isolement » de T vis à vis des transaction exécutées simultanément. Est spécifié : • •

Le degré de visibilité des lectures et écritures de T par les autres transactions. Le degré de visibilité par T des mises à jours effectuées par les autres transactions i.e. T peut-il être affecté par les mises à jours de transactions concurrentes éventuellement non encore validées.

Permet des degrés de tolérance divers : améliore l’efficacité de traitement mais rend la cohérence plus difficile à assurer.

Les niveaux d’isolation La norme SQL92 prévoit 3 niveaux d’isolation (en plus de sérialisable). Leur support par les SGBDs est souvent incomplet ou ne correspond pas toujours aux recommandations de la norme…. Rappel : le niveau d’isolation « sérialisable » rend chaque transaction complètement isolée i.e. insensible aux changements intermédiaires des autres. Les trois niveaux prévus sont : READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ. Ils se distinguent par la possibilité ou l’impossibilité d’obtenir certains effets…

Les niveaux d’isolation Dirty read (lecture impropre) : T peut lire les modifications faites par d’autres transactions S. Si ces transactions effectuent un ROLLBACK, de nouvelles lectures par T des mêmes variables renverront les anciennes valeurs (après annulation), de nouveaux tuples anciennement supprimés par S pourront réapparaître pour T, des tuples ajoutés par S pourront disparaître pour T. Non-repeatable read (lecture non reproductible) : Deux lectures par T d’une même variable x peut donner des résultats différents si, entretemps, une autre transaction à modifié x et a fait un commit. Phantoms (fantome) : T peut voir apparaître d’une lecture à l’autre (d’une table, par exemple) des lignes insérées par d’autres transactions.

Les niveaux d’isolation Les caractéristiques pour chaque niveau d’isolation sont les suivantes : Dirty read

Nonrepeatable read

Phantoms

Read uncommitted

Y

Y

Y

Read Committed

N

Y

Y

Repeatable Read

N

N

Y

Serializable

N

N

N

Reprise sur pannes

Reprise sur pannes But : assurer la persistance des données d’une base de données en dépit de toutes sortes de pannes. Plusieurs types de mémoires mises en jeu : volatile (mémoire centrale, par exemple), en ligne non volatile (disques), hors ligne non volatile (supports de sauvegarde). Plusieurs types de pannes : défaillance de la machine, d’un périphérique, problème logiciel, etc…

Exemple Début : 0, fin : n T1 T2 T3 T4 T5 temps 0 n Au temps n, les effets des transactions T2, T3 et T5 doivent survivre dans la base, les effets de T1 et T6 doivent être défaits.

Résister aux pannes • •

Copie de l’état de la base à intervalle régulier sur un support « sûr », Tenue d’un journal notant toutes les opérations effectuées depuis la dernière sauvegarde.

Journal de transactions : comprend l’enregistrement de toutes les modifications intervenant dans la base. Ces informations doivent permettre de défaire et refaire les actions des transactions en cas de reprise ultérieure sur panne. Il ne doit pas être détruit…. En général, plusieurs copies maintenues par le SGBD à divers endroits de l’arborescence.

Journal des transactions Parmi les informations collectées dans le journal, on trouve : • • • • •

L’identifiant de la transaction T L’état de la transaction Le type d’action effectuée (lecture, écriture, commit, rollback, point de sauvegarde). L’ancienne valeur de la donnée (en cas de modification). Appelée « image avant » : sert à défaire l’action. La nouvelle valeur de la donnée. Appelée « image après » : sert à refaire l’action.

Défaire / refaire Nouvel état de l’objet

Défaire

Ancien état de l’objet

Refaire

Nouvel état de l’objet

Journal

Ancien état de l’objet Journal

Point de sauvegarde - Checkpoint Pour savoir exactement ce qui doit être refait ou défait après une panne (et limiter le nombre d’action), on utilise la technique du checkpoint. Checkpoint (Point de reprise) : point de synchronisation entre la BD et le journal. Toute opération mentionnée avant le checkpoint est, à coup sûr, validée dans la base. Besoin de refaire toutes les transactions ayant fait un COMMIT depuis le dernier point de sauvegarde (cf. SAVEPOINT, déjà vu).