Cours complet pour apprendre les différents types de bases de données et le langage SQL


précédentsommaire

XI. Concurrence et reprise

XI-A. Concept de transaction

Une transaction est un fragment de programme dont l'exécution fait passer une BD d'un état cohérent à un autre état cohérent.

Une transaction est une suite d'événements dont chacun peut être :

  • la lecture ou l'écriture d'une donnée ;
  • le verrouillage ou le déverrouillage d'une donnée ;
  • le démarrage ou l'arrêt de la transaction.

Une donnée est un fragment d'une BD :

  • une valeur d'attribut, un n-uplet, une table…

XI-B. Événements

événement

signification

start

démarrage de la transaction

read D

lecture d'une donnée D

write D

modification d'une donnée D

rollback

annulation de la transaction

commit

confirmation de la transaction

XI-C. Exemple de transaction

Image non disponible

XI-D. Propriétés d'une transaction

Atomicité

  • Soit toutes les modifications effectuées par une transaction sont enregistrées dans la BD, soit aucune ne l'est.
  • Si une transaction est confirmée (commit), toutes les modifications qu'elle a effectuées sont enregistrées dans la BD et rendues visibles aux autres utilisateurs.
  • Si une transaction est interrompue (rollback), alors aucune de ces modifications n'est enregistrée dans la BD.

Cohérence

  • Une transaction fait passer une BD d'un état cohérent à un autre état cohérent.
  • Un état cohérent est un état dans lequel les contraintes d'intégrité sont vérifiées.

Isolation

  • Une transaction se déroule sans être perturbée par les transactions concurrentes : tout se passe comme si elle se déroulait seule.

Durabilité

  • Une fois qu'une transaction a été confirmée, le SGBD garantit qu'aucune modification qu'elle a effectuée ne sera perdue, quels que soient les accidents qui surviendront : interruption, panne du système d'exploitation, « crash » de disque, etc.

XI-E. Problèmes dus à la concurrence

perte de mise à jour

lecture impropre

lecture non reproductible

objets fantômes

XI-E-1. Perte de mise à jour

T 1

T2

BD

A = 10

read A

   
 

read A

 

A = A + 10

   

write A

 

A = 20

 

A = A + 50

 
 

write A

A = 60

XI-E-2. Lecture impropre (données incohérentes)

T1

T2

BD

A + B = 200

A = 120
B = 80

read A

   

A = A - 50

   

write A

 

A = 70

 

read A

 
 

read B

 
 

display A + B
(150 est affiché)

 

read B

   

B = B + 50

   

write B

 

B = 130

XI-E-3. Lecture impropre (données non confirmées)

T1

T2

BD

A = 50

 

A = 70

 
 

write A

A = 70

read A
(70 est lu)

   
 

rollback
(La valeur initiale de A est restaurée)

A = 50

XI-E-4. Lecture non reproductible

T1

T2

BD

A = 10

 

read A
(10 est lu)

 

A = 20

   

write A

 

A = 20

 

read A
(20 est lu)

 

XI-E-5. Objet fantôme

T1

T2

BD

E = {1,2,3}

display card(E)
(3 est affiché)

   
 

insert 4 into E

E = {1,2,3,4}

display card(E)
(4 est affiché)

   

XI-F. Exécution sérialisable

Le principe sur lequel repose le contrôle de concurrence est celui de la sérialisabilité de l'exécution d'un ensemble de transactions.

En effet, lorsque les transactions sont exécutées les unes après les autres, il n'y a pas de problèmes de concurrence.

Appliquée systématiquement, cette solution serait très coûteuse en temps d'attente.

La solution adoptée consiste à exécuter un ensemble de transactions concurrentes de façon à ce que le résultat soit équivalent à une exécution en série de ces transactions :

  • une telle exécution est dite sérialisable.

XI-F-1. Définition de la sérialisabilité

L'exécution d'un ensemble de transactions est dite en série si, pour tout couple de transactions, tous les événements de l'une précèdent tous les événements de l'autre.

Deux exécutions d'un même ensemble de transactions sont équivalentes si et seulement si :

  • elles sont constituées des mêmes événements ;
  • elles produisent le même état final de la BD et les mêmes résultats pour les transactions :

    • les lectures produisent les mêmes résultats,
    • les écritures sont réalisées dans le même ordre.

Une exécution concurrente d'un ensemble de transactions est dite sérialisable si et seulement si il existe une exécution en série équivalente.

XI-F-2. Condition de sérialisabilité

Deux opérations sont dites conflictuelles si elles appartiennent à deux transactions différentes et si elles ne sont pas permutables.

Deux opérations appartenant à deux transactions différentes sont conflictuelles si et seulement si elles portent sur la même donnée et que l'une des deux au moins est une opération d'écriture.

Une exécution concurrente est sérialisable si elle peut être transformée en une exécution en série équivalente par une suite de permutations d'opérations non conflictuelles.

XI-F-3. Exemple d'exécution sérialisable

T1

T2

read A

 

write A

 
 

read A

read B

 
 

write A

write B

 
 

read B

 

write B

T1

T2

read A

 

write A

 

read B

 
 

read A

write B

 
 

write A

 

read B

 

write B

T1

T2

read A

 

write A

 

read B

 

write B

 
 

read A

 

write A

 

read B

 

write B

XI-G. Verrouillage

Le verrouillage est la technique la plus classique pour résoudre les problèmes dus à la concurrence :

  • Avant de lire ou écrire une donnée, une transaction peut demander un verrou sur cette donnée pour interdire aux autres transactions d'y accéder.
  • Si ce verrou ne peut être obtenu, parce qu'une autre transaction en possède un, la transaction demandeuse est mise en attente.

Afin de limiter les temps d'attente, on peut jouer sur :

  • la granularité du verrouillage : pour restreindre la taille de la donnée verrouillée ;
  • le mode de verrouillage : pour restreindre les opérations interdites sur la donnée verrouillée.

XI-G-1. Granularité de verrouillage

On peut verrouiller :

  • un n-uplet et donc toutes ses valeurs ;
  • une page et donc tous ses n-uplets ;
  • une table et donc toutes ses lignes ;
  • la BD et donc toutes ses tables.

XI-G-2. Modes de verrouillage

Les deux modes les plus simples sont :

  • partagé (S) : demandé avant de lire une donnée ;
  • exclusif (X) : demandé avant de modifier une donnée.

Les règles qui régissent ces deux modes sont les suivantes :

  • un verrou partagé ne peut être obtenu sur une donnée que si les verrous déjà placés sur cette donnée sont eux-mêmes partagés :

    • commutativité lecture/lecture,
  • un verrou exclusif ne peut être obtenu sur une donnée que si aucun verrou n'est déjà placé sur cette donnée :

    • non commutativité lecture/écriture ou écriture/écriture sur la même donnée.

XI-G-3. Matrice de compatibilité

MC

S

X

S

oui

non

X

non

non

XI-G-4. Opérations de verrouillage

Opération

Signification

lock m D

demande d'un verrou en mode m sur la donnée D

unlock D

déverrouillage d'une donnée D

XI-G-5. Verrouillage à deux phases

Une transaction est bien formée si :

  • elle obtient un verrou sur une donnée avant de lire ou d'écrire cette donnée ;
  • elle libère tous ses verrous avant de se terminer.

Une transaction est à deux phases si elle est bien formée et si, après avoir libéré un verrou, elle n'en acquiert plus.

On distingue donc :

  • une phase d'acquisition des verrous ;
  • une phase de libération des verrous.
Image non disponible

Il est démontré que l'exécution d'un ensemble de transactions à deux phases est sérialisable.

En conséquence, il ne peut y avoir ni pertes de mise à jour, ni lectures impropres, ni lectures non reproductibles.

Les transactions sont sérialisées dans l'ordre du début de leur phase de libération.

Un verrouillage à deux phases est dit :

  • strict, si les verrous ne sont libérés qu'après la confirmation de la transaction ;
  • non strict dans le cas contraire.

L'avantage du verrouillage strict est que l'ordre de sérialisation est celui de leur point de confirmation, ce qui est intuitivement attendu par les utilisateurs.

Dans le cas de l'abandon d'une transaction, le respect du principe d'atomicité implique que tout se passe comme si cette transaction n'avait jamais existé :

  • on impose donc que les verrous en écriture ne soient libérés qu'après la confirmation de la transaction.

XI-G-6. Plus de perte de mise à jour

T1

T2

BD

A = 10

lock X A

   

read A

   
 

lock X A

 

A = A +10

attente

 

write A

attente

A = 20

unlock A

attente

 
 

read A

 
 

A = A + 50

 
 

write A

A = 70

 

unlock A

 

XI-G-7. Plus de lecture impropre

T1

T2

BD

A + B = 200

A = 120
B = 80

lock X A

   

read A

   

A = A - 50

 

A = 70

write A

   
 

lock S A

 

lock X B

attente

 

read B

attente

 

B = B + 50

attente

 

write B

attente

B = 130

commit

attente

 

suite T2

read A

lock S B

read B

display A + B
(200 est affiché)

XI-G-8. Plus de lecture non reproductible

T1

T2

BD

A = 10

 

lock S A

 
 

read A
(10 est lu)

 

lock X A

   

attente

read A
(10 est lu)

 

attente

unlock A

 

A = 20

   

write A

 

A = 20

XI-G-9. Granularité de verrouillage en SQL

Verrouillage des tables :

  • La sérialisabilité est assurée, mais l'inconvénient est la perte de concurrence due au verrouillage de tous les n-uplets de la table, qu'ils soient ou non accédés par la requête.

Verrouillage des n-uplets :

  • La concurrence est meilleure, mais la sérialisabilité n'est pas assurée à cause du problème des n-uplets fantômes.

Verrouillage à granularité multiple :

  • La sérialisabilité est assurée et la concurrence améliorée.

XI-H. n-uplets fantômes

Le verrouillage des n-uplets ne résout pas le problème.

T1

T2

 
Sélectionnez
1.
2.
3.
4.
SELECT COUNT(*)
FROM livre
WHERE année = 2003;
(réponse n)
 
Sélectionnez
1.
2.
3.
4.
5.
SELECT COUNT(*)
FROM livre
WHERE année = 2003;
(réponse n + 1)
COMMIT
 
Sélectionnez
1.
2.
3.
INSERT INTO livre
VALUES ("Les BD", 2003);
COMMIT

Chaque n-uplet de la table livre lu par T1 est verrouillé en lecture, mais cela n'a pas d'influence sur la création d'un nouveau n-uplet par T2.

Le verrouillage des tables empêche l'apparition de n-uplets fantômes.

T1

T2

 
Sélectionnez
1.
2.
3.
4.
5.
LOCK S livre
SELECT COUNT(*)
FROM livre
WHERE année = 2003;
(réponse n)
 
Sélectionnez
1.
2.
3.
4.
5.
SELECT COUNT(*)
FROM livre
WHERE année = 2003;
(réponse n)
COMMIT
 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
9.
LOCK X livre
attente
attente
attente
attente
attente
INSERT INTO livre
VALUES ("Les BD", 2003);
COMMIT

XI-I. Interblocage

T1

T2

lock X A

 
 

lock X B

lock S B

 

attente

lock S A

attente

attente

Image non disponible

XI-I-1. Résolution de l'interblocage

En détectant les interblocages :

  • On inspecte à intervalles réguliers le graphe d'attente pour détecter si un interblocage s'est produit. Dans ce cas, on défait l'une des transactions bloquées et on la relance un peu plus tard.
  • On annule une transaction dont le temps d'attente dépasse un certain seuil, et on la relance un peu plus tard.

En évitant les interblocages :

  • On fixe un ordre sur les données et on impose aux transactions de respecter cet ordre dans leur demande de verrous.

XI-J. La norme SQL

La norme SQL n'impose aucun choix sur l'implantation des mécanismes de gestion de la concurrence.

Elle spécifie, entre autres :

  • la définition d'une transaction ;
  • les niveaux d'isolation auxquels une transaction peut s'exécuter.

XI-J-1. Définition d'une transaction SQL

Une transaction est une suite de commandes SQL.

Une transaction est démarrée par un agent lorsqu'il exécute une commande SQL et qu'il n'y a pas de transactions en cours.

Une transaction est terminée explicitement par une commande COMMIT ou une commande ROLLBACK.

Deux transactions ne peuvent pas être imbriquées :

  • un agent ne peut pas démarrer une transaction si sa transaction courante n'est pas terminée.

XI-J-2. Niveaux d'isolation

Par défaut, une transaction est exécutée en mode sérialisable.

Cependant, ce protocole a des conséquences sur les performances d'une transaction en diminuant la concurrence.

C'est pourquoi SQL autorise le développeur d'une application à choisir le niveau d'isolation d'une transaction afin de maximiser la concurrence.

Il devra bien entendu vérifier que le niveau d'isolation choisi garantit la cohérence de cette transaction.

Attention ! les transactions d'une même application peuvent s'exécuter à des niveaux d'isolation différents :

  • fixer le niveau d'isolation d'une transaction n'a pas d'implication sur le niveau d'isolation des autres transactions.

XI-J-2-a. Les 4 niveaux d'isolation

READ UNCOMMITED

  • il n'y a pas de perte de mise à jour ;
  • il peut y avoir des lectures impropres, des lectures non reproductibles, et des objets fantômes ;
  • il n'y a pas d'attente en lecture.

READ COMMITTED

  • il n'y a ni perte de mise à jour, ni lecture incohérente ;
  • il peut y avoir des lectures non reproductibles et des objets fantômes ;
  • les transactions n'ont accès qu'aux données produites par des transactions confirmées.

REPEATABLE READ

  • il n'y a ni perte de mise à jour, ni lecture incohérente, ni lecture non reproductible ;
  • il peut y avoir des objets fantômes.

SERIALIZABLE (par défaut)

  • il n'y a ni perte de mise à jour, ni lecture incohérente, ni lecture non reproductible, ni objet fantôme ;
  • l'isolation est totale, la visibilité de la BD est équivalente à un cliché réalisé au début de la transaction.

XI-J-2-b. Mode d'exécution d'une transaction

Le mode d'exécution d'une transaction est spécifié par la commande SET TRANSACTION qui la précède immédiatement :

 
Sélectionnez
1.
2.
3.
4.
5.
6.
7.
8.
SET TRANSACTION
  mode d′accès, ISOLATION LEVEL niveau d′isolation
  mode d′accès ::= READ ONLY | READ WRITE
  niveau d′isolation ::=
    READ UNCOMMITED
    | READ COMMITTED
    | REPEATABLE READ
    | SERIALIZABLE

Par défaut, le niveau d'isolation est SERIALIZABLE et le mode d'accès est READ ONLY.

Attention ! la commande SET TRANSACTION n'est pas un début de transaction et elle ne peut pas être utilisée si une transaction est en cours.

XI-J-2-c. Une mise en place des niveaux d'isolation

Nous montrons comment un niveau d'isolation peut être mis en place pour une transaction SQL, à l'aide de deux types de verrous :

  • des verrous de longue durée qui peuvent être demandés pour la lecture ou l'écriture d'un n-uplet ou d'une table et qui ne sont libérés qu'après la confirmation de la transaction ;
  • des verrous de courte durée qui sont demandés pour la lecture d'un n-uplet et libérés après la lecture de celui-ci.

Soit T la transaction considérée.

READ UNCOMMITED

  • On autorise T à lire un n-uplet sans demande préalable de verrou.
  • T peut donc lire une donnée verrouillée en écriture par une autre transaction et donc effectuer une lecture impropre.

READ COMMITTED

  • On impose à T d'obtenir un verrou de courte durée sur un n-uplet avant de pouvoir le lire.
  • Ce verrou ne pourra pas être obtenu si une autre transaction T' possède un verrou en écriture sur ce n-uplet, et puisque T' ne libérera ce verrou que lors de sa confirmation (les verrous en écriture sont de longue durée), T ne pourra pas donc pas lire un n-uplet non confirmé.
  • Par contre, une autre transaction pourra modifier un n-uplet entre deux lectures de celui-ci par T : les lectures de ce n-uplet par T pourront donc ne pas être reproductibles.

REPEATABLE READ

  • On impose à T d'obtenir un verrou de longue durée sur un n-uplet avant de pouvoir le lire.
  • Aucune autre transaction ne pourra donc modifier ce n-uplet avant que T soit confirmée.
  • Les lectures de ce n-uplet par T seront donc reproductibles.

SERIALIZABLE

  • On impose à T d'obtenir un verrou en lecture de longue durée sur chaque table lue et donc sur chaque n-uplet de cette table.
  • Aucune autre transaction ne pourra donc insérer un n-uplet dans une de ces tables, car cette opération est une opération d'écriture de cette table et est donc interdite si un verrou en lecture est déjà placé sur cette table, ce qui est le cas.
  • Il n'y aura donc pas de n-uplets fantômes dans les tables lues par T.

XI-K. Atomicité et durabilité

Le respect de l'atomicité peut impliquer de défaire les effets d'une transaction lorsque celle-ci a été abandonnée.

Le respect de la durabilité implique que le SGBD doit être capable de remettre la base de données en état après une panne :

  • les mises à jour faites par une transaction non confirmée avant la panne doivent être défaites.

C'est le gestionnaire de reprise qui assure cette tâche.

XI-L. Reprise

Les pannes d'un SGBD peuvent être classées en deux catégories :

  • panne d'ordinateur, par exemple à la suite d'une coupure de courant : les données enregistrées en mémoire centrale sont perdues, mais pas celles enregistrées sur disque ;
  • panne de disque : une partie ou toutes les données enregistrées sur ce disque sont perdues.

La reprise à chaud, après un abandon de transaction ou une panne d'ordinateur, peut être réalisée automatiquement et rapidement, en s'appuyant sur la tenue d'un journal qui garde en mémoire tous les événements d'une transaction.

La reprise à froid, après une panne de disque, est plus longue à mettre en œuvre. Elle nécessite de réaliser des copies régulières de la BD et un archivage des mises à jour entre deux copies.

Nous étudions la reprise à chaud.

XI-M. Journal de transaction

Le journal de transaction est un fichier qui contient une suite d'enregistrements dont chacun décrit un événement d'une transaction.

Un journal est enregistré sur une mémoire stable, c'est-à-dire une mémoire qui théoriquement ne peut pas être détruite.

Si nécessaire, le journal est dupliqué en plusieurs exemplaires (par exemple, sur un disque miroir).

Les enregistrements sont écrits à partir de la fin du journal (mode append) et donc des plus anciens aux plus récents.

XI-N. Exemple d'événements journalisés

Événement

Signification

(T start)

début de la transaction d'identificateur T

(T D a)

mise à jour la donnée D par la transaction T : son ancienne valeur était a

(T D n)

mise à jour la donnée D par la transaction T : sa nouvelle valeur est n

(T commit)

confirmation de la transaction T

(T abort)

abandon de la transaction T

(check point)

point de reprise

XI-O. Un extrait de journal

T1

T2

start

 

read A

 

A = A + 10

 

write A

 

rollback

 
 

start

 

read B

 

B = B + 20

 

write B

 

commit

Journal

T1 start

T1 A 30 40

T2 start

T2 B 70 90

T2 commit

XI-P. Point de reprise

Un point de reprise est une marque dans le journal qui indique qu'au moment où elle a été faite :

  • aucune transaction n'était en cours ;
  • toutes les données écrites par des transactions antérieures au point de reprise avaient été transférées sur disque.

Pour obtenir un point de reprise, il faut :

  • interdire le début de nouvelles transactions ;
  • laisser se terminer les transactions en cours (c'est-à-dire jusqu'à ce qu'elles aient écrit COMMIT ou ABORT dans le journal) ;
  • écrire sur le disque les blocs du journal encore en mémoire centrale ;
  • écrire (checkpoint) dans le journal ;
  • écrire sur le disque les blocs du journal encore en mémoire centrale.

XI-Q. Forcer l'écriture sur disque

Une écriture dans la BD (write) ou dans le journal se fait au travers d'un tampon :

  • une donnée écrite par write l'est dans le tampon et pourra n'être écrite sur le disque que bien plus tard ;
  • un enregistrement écrit dans le journal l'est dans le tampon et pourra n'être écrit sur le disque que bien plus tard.

Pour être sûr qu'une donnée écrite par write soit enregistrée sur disque, il faut forcer l'écriture sur disque de la page du tampon contenant cette donnée si elle ne l'a pas été.

Pour être sûr que le journal soit entièrement enregistré sur disque, il faut forcer l'écriture sur disque des pages qui résident dans le tampon qui n'ont pas encore été écrites sur le disque ou qui ont été modifiées.

XI-R. Modes de mise à jour

On distingue trois modes de mise à jour :

  • Mise à jour immédiate. Les mises à jour d'une transaction sont écrites sur disque avant la confirmation de cette transaction.
  • Mise à jour différée. Les mises à jour d'une transaction sont mémorisées dans le journal et ne sont écrites sur disque qu'après confirmation de cette transaction.
  • Combinaison des deux.

XI-R-1. Mise à jour immédiate

Les mises à jour (write) faites par une transaction sont écrites sur disque avant la confirmation de cette transaction.

Si cette transaction est annulée (rollback) ou si une panne s'est produite avant sa confirmation, il faut annuler ces mises à jour.

XI-R-1-a. Journalisation

Pour chaque événement start d'une transaction T :

  • écrire (start T) dans le journal.

Pour chaque événement write D d'une transaction T :

  • écrire (T D a) dans le journal (write-ahead logging) où a est l'ancienne valeur de D,
  • forcer l'écriture sur disque de D.

Pour chaque événement commit d'une transaction d'identificateur T :

  • écrire (commit T) dans le journal.

XI-R-1-b. Annulation d'une transaction

Soit T la transaction à annuler.

  • dérouler le journal à l'envers jusqu'à l'enregistrement (T start) ;
  • dérouler le journal à l'endroit et pour chaque enregistrement (T D a) :

    • D := a,
    • forcer l'écriture sur disque de D ;
  • écrire (T abort)dans le journal ;
  • forcer l'écriture sur disque du journal.

XI-R-1-c. Reprise

Dérouler le journal à l'envers jusqu'au dernier point de reprise, et pour chaque enregistrement e :

  • si e = (commit T) :

    • noter que T est confirmée,
  • si e = (abort T) :

    • noter que T est annulée,
  • si e =(T D a) et T n'est ni confirmée, ni annulée :

    • écrire l'ancienne valeur a de D dans la BD,
    • noter que T est incomplète.

Pour chaque transaction T incomplète :

  • écrire (abort T) dans le journal ;
  • forcer l'écriture du journal sur le disque.

XI-R-2. Mise à jour différée

Les nouvelles valeurs des données mises à jour par une transaction sont écrites dans le journal et ne sont écrites sur disque qu'après confirmation de cette transaction (commit).

Une transaction non confirmée n'a donc rien écrit sur le disque :

  • Si cette transaction est annulée (rollback) ou si une panne s'est produite avant sa confirmation, il n'y a rien à faire.
  • Si une panne se produit après sa confirmation, il faut écrire les nouvelles valeurs de ces données sur disque, car il n'est pas sûr qu'elles l'ont été. Ces nouvelles valeurs sont écrites dans le journal.

XI-R-2-a. Journalisation

Pour chaque événement start d'une transaction T :

  • écrire (start T) dans le journal.

Pour chaque événement write D d'une transaction T :

  • écrire (T D n) dans le journal où n est la nouvelle valeur de D (write-ahead logging) ;
  • noter la nouvelle valeur n de D.

Pour chaque événement commit d'une transaction T :

  • écrire (commit T) dans le journal ;
  • forcer l'écriture du journal sur le disque ;
  • pour chaque donnée D mise à jour par T :

    • forcer l'écriture sur disque de la nouvelle valeur de D.

XI-R-2-b. Reprise

Dérouler le journal à l'envers jusqu'au dernier point de reprise et noter les transactions confirmées et les transactions incomplètes (ni confirmées, ni annulées).

Dérouler le journal à l'endroit (depuis ce point de reprise) et pour chaque enregistrement (T D n) d'une transaction T confirmée :

  • forcer l'écriture de D sur le disque.

Pour chaque transaction T incomplète :

  • écrire (abort T) dans le journal ;
  • forcer l'écriture du journal sur le disque.

précédentsommaire

Vous avez aimé ce tutoriel ? Alors partagez-le en cliquant sur les boutons suivants : Viadeo Twitter Facebook Share on Google+