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▲
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 |
||
|
read A |
||
|
A = A - 50 |
||
|
write A |
A = 70 |
|
|
read A |
||
|
read B |
||
|
display A + B |
||
|
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 |
||
|
rollback |
A = 50 |
XI-E-4. Lecture non reproductible▲
|
T1 |
T2 |
BD |
|---|---|---|
|
A = 10 |
||
|
read A |
||
|
A = 20 |
||
|
write A |
A = 20 |
|
|
read A |
XI-E-5. Objet fantôme▲
|
T1 |
T2 |
BD |
|---|---|---|
|
E = {1,2,3} |
||
|
display card(E) |
||
|
insert 4 into E |
E = {1,2,3,4} |
|
|
display card(E) |
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▲
|
→ |
|
→ |
|
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.
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▲
|
suite T2
|
XI-G-8. Plus de lecture non reproductible▲
|
T1 |
T2 |
BD |
|---|---|---|
|
A = 10 |
||
|
lock S A |
||
|
read A |
||
|
lock X A |
||
|
attente |
read A |
|
|
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.
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.
|
XI-I. Interblocage▲
|
|
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 :
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▲
|
|
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.