Gestion des transactions

Report
Gestion des transactions
1.
2.
Introduction
Une des fonctions importante des SGBD modernes est d’autoriser les
utilisateurs d’effectuer des opérations simultanées (concurrentes) sur
des données partagées de la BD. Si ces op ne sont pas sous contrôle,
les accès interfèrent tôt ou tard les uns avec les autres et la BD
devient incohérente. Pour éviter cela, le SGBD met en place un
protocole de contrôle de simultanéité (ou de concurrence) qui
empêche les accès à la BD d’interférer.
Une autre fonction est la récupération de la base de données ou sa
restitution dans un état correct suite à une défaillance physique ou
logiciel.
Ces deux fonctions sont mutuellement dépendantes et sont basées sur la
notion centrale de transaction.
1
Transaction
• Beaucoup d'opérations sur une BD doivent être
atomiques:
• Transfert d'argent entre les comptes:
UPDATE Compte1
Set Val = Val -100;
UPDATE Compte2
Set Val = Val + 100;
• Si seulement une de ces requêtes est exécutée, la BD
perd sa consistance
2
Transactions
Une transaction est une action ou suite d’actions
demandée par un seul utilisateur ou un programme
d’application, qui appliquée à une base de données
cohérente, restitue une base de données cohérente
3
Transactions




action atomique : entièrement ou pas du tout
Préservant la consistance de la BD
Comme si l'usager était isolé sur la BD : ses résultats
intermédiaires (état temporairement incohérent) sont
masqués aux autres transactions.
A effet durable sur la BD, une fois terminées comme
prévu
Modèle ACID de transactions
4
Modélisation









Une transaction T est modélisée comme une suite finie d’actions portant sur des
objets.
T = < (t, Ai, Oi) >/i = 1, n.
t désigne le nom de la transaction (nom interne au système), Ai une opération et Oi
un objet.
Les opérations qui nous intéressent sont :
Begin Transaction : initialiser une nouvelle transaction
Commit : terminer une transaction
Read : lecture de la valeur d’un objet à partir de la base et stockage de cette valeur
dans l’espace de travail de la transaction ;
Write : à partir d’une valeur stockée dans l’espace de travail de la transaction, écrire
cette valeur dans la base pour l’objet désigné ;
Rollback : annuler une transaction (défaire toutes les mises à jour effectuées par la
transaction depuis son début).
En ce qui concerne les objets manipulés, ça peut être une relation, un n-uplet, ou
même la valeur d’un constituant (les deux premiers chez Oracles).
5
Modélisation
Lorsqu’un programme émet l’action
Begin transaction
ceci a pour effet de créer au niveau du SGBD une
nouvelle occurrence de transaction à laquelle est
associée :
 un identificateur interne ;
 un espace de travail ;
 et un contexte d’exécution formé d’une série de
blocs de contrôle.
6
Exemple de transaction en PL-SQL
BEGIN, COMMIT (validée), ROLLBACK (annulée)
BEGIN TRANSACTION
UPDATE Compte1
SET Val = Val -100
IF SQLCODE <> 0 ROLLBACK ; EXIT ;
UPDATE Compte2
SET Val = Val + 100
IF SQLCODE <> 0 ROLLBACK ; EXIT;
COMMIT
7
Nécessité du controle de Concurrence
Pb1 : des MAJ perdues
Solde = 100
R2 (solde)
R1 (solde)
solde := solde +200
solde := solde +100
W1 (solde)
Solde = 200
La base
8
Exemple
solde = 100
R2 (solde)
R1 (solde)
solde := solde+200
solde := solde +100
W1 (solde)
solde = 200
Solde = 300
W2 (solde)
La base
Au lieu de 400
9
Pb2 : dépendance non validée ou dirty read
Temps
t1
t2
t3
t4
t5
t6
t7
t8
T1
T2
begin transaction
read (soldex)
soldex = soldex + 100
begin transaction
write (soldex)
read(soldex)
.
soldex = soldex – 10 rollback
write(soldex)
commit
soldex
100
100
100
200
200
200
190
190
Au lieu de 90
Solution évidente :
permettre l’exécution que d’une seule transaction à la fois. Or la raison d’être
du SGBD est
Pb 3 : analyse incohérente
T2 calcule le total des soldes alors qu’en // T1 transfert 10 DA de soldex
à soldez
Temps T1
T2
soldex soldey
t1
begin trans
100
50
t2
begin trans
som = 0
100
50
t3
read (soldex) read (soldex)
100
50
t4
soldex=soldex-10 som=som+soldex 100
50
t5
write (soldex) read(soldey)
90
50
t6
read(soldez) som=som+soldey
90
50
t7
soldez=soldez +10
90
50
t8
write(soldez)
90
50
t9
commit
read(soldez)
90
50
soldez
25
25
25
25
25
25
25
35
35
0
0
100
100
150
150
150
150
t10
t11
35
35
185
185
som=som+soldez
commit
90
90
50
50
som
au lieu de 175
11
Lecture Fantôme
Un autre problème se produit lorsqu’une transaction exécute
une requête qui recherche un ensemble de tuples d’une
relation satisfaisant un certain prédicat, puis exécute un peu
plus tard la même requête pour constater que l’ensemble
obtenu contient un tuple supplémentaire ou fantôme
inséré entre temps par une autre transaction : lecture
fantôme.
12
Gestion de la concurrence
Objectif : planifier les transactions de manière à
éviter toute interférence entre elles et, donc
d’éviter les problèmes des types précédents tout
en gardant un niveau optimal de simultanéité, et
de parallélisme dans le système, de sorte que les
transactions
puissent
s’exécuter
sans
interférence, certes, mais surtout autant que
possible en parallèle.
13
Quelques définitions

Contrôleur (scheduleur) : un module du SGBD chargé de contrôler les accès
concurrents aux données.

Planification (schedule)
: une séquence d’opérations d’un ensemble de
transactions concurrentes qui préserve l’ordre des opérations dans chacune des
transactions.

Planification sérielle est une planification où les opérations de chaque transaction
sont exécutées de manière consécutive, sans aucun entrelacement avec d’autres
transactions (pas de parallélisme).
 Ces exécutions sont correctes mais peuvent donner des résultats différents
(voir TD).

Planification non sérielle est une planification où les opérations d’un ensemble
de transactions sont exécutées de manière entrelacée.
 Une planification non sérielle sera correcte si elle produit les mêmes
résultats et a les mêmes effets sur la BD qu’une planification série des
mêmes transactions et cela quelque soit l’état initial de la base de données.
14
Principe de sérialisabilité
Ne laisser s’exécuter les transactions en parallèle que celles provoquant les
mêmes effets sur les données qu’une exécution en séquence de ces
mêmes transactions.
Définition : Un ordonnancement est correct s’il est sérialisable, c’est-à-dire
équivalent à un ordonnancement série formé des mêmes transactions.
Quelques résultats :
Si deux transactions ne font que lire des données, elles n’entrent pas en
conflit et leur ordre est sans importance.
 Si deux transactions soit lisent soit écrivent des données complètement
différentes, elles n’entrent pas en conflit et leur ordre est sans
importance.
 Si une transaction écrit dans des données et si une autre transaction lit
ou écrit dans les mêmes données, alors l’ordre de leur exécution
importe.

15
Temps
1 Begin TransactionT1
2 Read1(soldex)
3 Write1 (soldex)
4 Begin Transaction T2
5 Read2(soldex)
6 Write 2(soldex)
7 Read1(soldey)
8 Write1 (soldey)
9 Commit1
10 Read2(soldey)
11 Write2(soldey)
12 Commit2
(a)
Begin Transaction T1
Read1(soldex)
Write1 (soldex)
Begin Transaction T2
Read2(soldex)
Read1(soldey)
Write 2(soldex)
Write1 (soldey)
Commit1
Read2(soldey)
Write2(soldey)
Commit2
Begin Transaction T1
Read1(soldex)
Write1 (soldex)
Read1(soldey)
Write1 (soldey)
Commit1
Begin TransactionT2
Read2(soldex)
Write 2(soldex)
Read2(soldey)
Write2(soldey)
Commit2
(b)
(c)
La planification (c) est sérielle et comme (a) et (b) équivalent à (c), (a) et (b) sont des
planifications sérialisables.
 Une planification de sérialisation (en vue de résoudre) des conflits trie les
opérations conflictuelles d’une manière proche de l’exécution sérielle.
16
Test de conflits de la capacité de sérialisation
Sous la règle d’écriture contrainte, un graphe de précédence peut être produit pour
tester la sérialisation des conflits.
Pour une planification P, un graphe de précédence est un graphe orienté dirigé
G = (N, F)
Construit comme suit :
 Créer un nœud pour chaque transaction.
 Créer une flèche dirigée Ti
Tj si Tj lit la valeur d’un élément écrit par Ti
 Créer une flèche dirigée Ti
Tj si Tj écrit une valeur dans un élément après
qu’il a été lu par Ti
 Créer une flèche dirigée Ti
Tj si Tj écrit une valeur dans un élément après
qu’il a été écrit par Ti
Si une flèche Ti
Tj existe dans le graphe de précédence pour P, alors dans toute
planification sérielle S’ équivalente à S, Ti doit apparaître avant Tj.
Si le graphe de précédence contient un cycle, la planification n’est pas sérialisable en
vue de résoudre les conflits.
17
Planification
sans
sérialisation
des
conflits
La transaction T1 transfère 100 Da d’un compte de solde vers un autre compte
de solde, tandis que T2 augmente de 10% le solde de ces deux comptes.
Temps
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
t11
t12
t13
t14
T1
Begin Transaction
Read (soldex)
soldex = soldex - 100
Write(soldex)
Read(soldey)
soldey = soldey +100
Write(soldey)
Commit
T2
Begin Transaction
Read(soldex)
soldex = soldex * 1.1
Write(soldex)
Read(soldey)
soldey = soldey * 1.1
Write(soldey)
Commit
18
T1
T2
Le graphe de précédence présente un cycle : la planification ne permet pas la
sérialisation
En pratique, un SGBD ne teste pas l’aspect sérialisable d’une planification. Ce serait
irréalisable car les interférences des opérations des transactions concurrentes est surtout
dicté par le système d’exploitation. Au lieu de cela, l’approche choisie consiste à faire
appel à des protocoles qui selon leur réputation, produisent des planifications sérielles
Récupération
La capacité de sérialisation identifie des planifications qui conservent toute sa
cohérence à une base de données, en admettant qu’aucune transaction planifiée
n’échoue.
Si une transaction défaille, la propriété d’atomicité impose que nous annulions les
effets de la transaction. En outre, la propriété de durabilité indique qu’une fois
qu’une transaction est validée, il n’est plus possible d’annuler les modifications
qu ’elle a apportées.
Exemple diapos 18 avec un Rollback à la place du commit de la transaction T1. Dans
ce cas on doit défaire toutes ce qu’a fait T1. Or T2 a lu la valeur modifiée de soldex
fournie par T1 et elle a même modifié soldex, puis validé le changement.
A proprement parler, nous devrions défaire la transaction T2 aussi car elle a employé
une valeur de soldex qui a été défaite. Or la propriété de durabilité ne nous le
permet pas.
En fait cette planification est irrécupérable
Définition d’une planification récupérable: Une planification où, pour toute paire de
transactions Ti et Tj, si Tj lit une donnée provenant d’une écriture préalable de Ti,
alors l’opération de validation de Ti précède l’opération de validation de Tj
20
Techniques de contrôle de concurrence
Il existe deux techniques de contrôle de concurrence principales qui permettent
d’exécuter des transactions en parallèles en toutes sécurité, à condition de faire
appel à certaines contraintes : les méthodes de verrouillage et d’estampillage.
Ces méthodes sont fondamentalement conservatrices (ou pessimistes) : elles
provoquent un retardement des transactions au cas où elles entreraient en conflit
avec d’autres transactions dans un certain délai à venir
Les méthodes optimistes reposent sur l’hypothèse que les conflits sont rares, de sorte
qu’elles permettent aux transactions d e procéder de manière désynchronisée et ne
vérifient la présence de conflits qu’en fin de transactions lors de leur validation.
21
Verrouillage
Une procédure employée pour contrôler les accès concurrents aux données.
Lorsqu’une transaction accède à la base de données, un verrou est susceptible de
bloquer l’accès à d’autres transactions pour éviter de faux résultats.
Les approches de verrouillage sont les plus suivies pour garantir la sérialisation des
transactions concurrentes.
Il existe plusieurs variantes mais elles partagent toutes la même caractéristique
fondamentale :
une transaction doit réclamer un verrouillage partagé (en lecture) et
exclusif (en écriture) sur la donnée avant d’effectuer réellement l’opération de
lecture ou d’écriture sur la base de données correspondante
Le verrou empêche une autre transaction de modifier la donnée où même de la lire,
dans le cas d’un verrouillage exclusif
Le verrou est mis en place en pratique, soit par l’activation d’un bit dans la donnée qui
indique qu’une partie de la base de données est verrouillée, soit par le maintien
d’une liste des parties verrouillées de la base de données et autres… .
22
Règles de base du verrouillage
Verrou partagé:
Si une transaction dispose d’un verrou partagé sur la donnée, elle peut lire la
donnée mais pas la modifier.
Verrou exclusif :
Si une transaction possède un verrou exclusif sur la donnée, elle peut lire et
modifier cette donnée.
Comme des opérations de lecture ne génèrent aucun conflit, il est possible que
plusieurs transactions détiennent simultanément des verrous partagés sur la
même donnée
Par contre le verrou exclusif sur une donnée accorde à une transaction le
monopole d’accès à cette donnée. Dans ce cas aucune autre transaction n’est
en mesure de lire ou modifier la donnée.
23
Utilisation des verrous




Toute transaction devant accéder à une donnée verrouille d’abord la donnée,
demandant soit un verrouillage partagé dans le cas d’un accès en lecture, soit un
verrouillage exclusif dans le cas d’un accès tant en lecture qu’en modification
Si la donnée n’est pas déjà verrouillée par une autre transaction, le verrou est
accordé.
Si la donnée est déjà verrouillée par une autre transaction au moment de la
demande, le SGBD détermine si la demande est compatible avec le verrou actuel.
Si c’est un verrou partagé que la transaction demande, alors qu’un verrou partagé
est déjà placé sur la donnée, la requête peut être satisfaite et le verrou est accordé;
dans le cas contraire, la transaction demanderesse doit attendre que le verrou se
libère.
Une transaction qui détient un verrou le conserve tant qu’elle ne le libère pas
explicitement pendant l’exécution ou implicitement lorsqu’elle se termine (par une
annulation ou une validation). Ce n’est que lorsqu’un verrou exclusif est libéré que
les effets de l’opération d’écriture qui a motivé le verrou deviennent visibles aux
autres transactions.
24
Cet usage des verrous ne garantit pas la sérialisation des planifications
Application des règles à l’exemple de la diapos 18
P = { verrou_écriture (T1, soldex), lecture (T1, soldex), écriture (T1, soldex),
déverrouillage(T1, soldex), verrou_écriture (T2, soldex), lecture (T2, soldex),
écriture (T2, soldex), déverrouillage(T1, soldex), verrou_écriture (T2, soldey),
lecture (T2, soldey), écriture (T2, soldey), déverrouillage(T2, soldey),
validation(T2), verrou_écriture (T1, soldey), lecture (T1, soldey), écriture (T1,
soldey), déverrouillage(T1, soldey), validation (T1)}
Si, préalablement à l’exécution, soldex = 100, soldey = 400, le résultat devrait être
 soldex = 220, soldey = 330, si T1 s’exécute d’abord, ou
 soldex = 210, soldey = 340, si T2 s’exécute avant.
En fait, le résultat de la planification P devrait donner
 soldex = 220, soldey = 340.
P n’est pas une planification sérialisable.
25
Pourquoi ça ne marche pas?

Le problème de cet exemple est que la planification libère les verrous
détenus par une transaction aussitôt que la lecture ou l’écriture
associée a été réalisée et qu’il n’est plus utile d’accéder à l’élément
sujet du verrou (par exemple soldex). Néanmoins, la transaction en
elle-même verrouille encore des données (soldey) après la libération
du premier verrou.
 Donc, même si cette approche semble améliorer la simultanéité des transactions,
elle permet encore à des transactions d’interférer entre elles, perdant ainsi
l’isolation absolue et l’atomicité.
Pour régler ce problème d’autres protocoles ont été mis en place par
exemple le protocole de verrouillage en deux phases (V2P ou 2PL
(two_phase locking)
26
Verrouillage en deux phases : V2P
Une transaction suit le protocole en deux phases si toutes les
opérations de verrouillage précèdent la première opération de
déverrouillage dans la transaction.
Toute transaction est divisible en deux phases : une première phase
dite de croissance où elle acquiert tous les verrous mais ne peut
en libérer aucun et une phase de résorption, au cours de laquelle
elle libère tous les verrous et ne peut plus en obtenir aucun.
27
Eviter le problème de la mise à jour perdue à l’aide du V2P
Temps
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
T1
T2
begin transaction
begin transaction
verrou-écriture(solde)
verrou-écriture(solde)
Read(solde)
attente
solde = solde +100
attente
Write(solde)
attente
commit/déverrouillage(solde)
Read(solde)
solde = solde + 200
Write(solde)
commit/déverrouillage(solde)
solde
100
100
100
100
200
200
200
200
400
400
28
Eviter le problème de la dépendance non validée à l’aide du V2P
Temps
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
T1
T2
begin transaction
verrou-écriture( soldex)
read (soldex)
begin transaction
soldex = soldex + 100
verrou-écriture( soldex) write (soldex)
Attente
rollback/ déverrouillage(soldex)
read(soldex)
.
soldex = soldex – 10
write(soldex)
commit/ déverrouillage (soldex)
soldex
100
100
100
100
200
100
100
100
90
90
T1 est obligée d’attendre que le verrou soit libéré par T2. Ceci n’a lieu que lorsque
l’annulation de T2 est achevée.
29
Eviter le problème de l’analyse incohérente grâce au V2P
Time T1
T2
t1
begin trans
t2
begin trans
som = 0
t3 verrou_écriture(soldex)
t4
read (soldex)
verrou_lecture(soldex)
t5
soldex=soldex-10
Attente
t6
write (soldex)
Attente
t7 verrou_écriture(soldez)
Attente
t8
read(soldez)
Attente
t9
soldez=soldez +10
Attente
t10
write(soldez)
Attente
t11 commit/ déverrouillage
Attente
t12
read (soldex)
t13
som=som+soldex
t14
verrou_lecture(soldey)
t15
read (soldey)
t16
som=som+soldey
t17
verrou_lecture(soldez)
t18
read(soldez)
t19
som=som+soldez
t20
commit/déverrouillage
soldex
100
100
100
100
100
90
90
90
90
90
90
90
90
90
90
90
90
90
90
90
soldey
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
50
31
soldez
25
25
25
25
25
25
25
25
25
35
35
35
35
35
35
35
35
35
35
35
som
0
0
0
0
0
0
0
0
0
0
0
90
90
90
140
140
140
175
175
Il est possible de prouver que si toutes les transactions
dans une planification suivent le protocole de
verrouillage en deux phases, alors la planification
garantit qu’elle est sérialisable pour résoudre les
conflit(Eswaran et al.) cependant, le protocole de
verrouillage en deux phases ne garantit pas l’aspect
sérialisable.
31
Annulations en cascade
Time
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
t11
t12
t13
t14
t15
t16
t17
t18
t19
T1
begin transaction
verrou_écriture(soldex)
read(soldex)
verrou_lecture(soldey)
read(soldey)
soldex = soldey + soldex
write(soldex)
déverrouillage(soldex)
:
:
:
:
:
:
rollback
T2
T3
begin transaction
verrou_écriture(soldex)
read(soldex)
soldex = soldex + 100
write(soldex)
déverrouillage(soldex)
:
:
begin-transaction
verrou_lecture(soldex)
rollback
:
rollback
32
Problème : les annulations en cascade ne sont jamais souhaitables, parce qu’elles induisent
potentiellement la destruction d’un volume significatif de travail accompli.
Solution : reporter la libération de tous les verrous à la fin des transactions, comme dans les
exemples précédents. De cette façon, le problème précédent ne pourrait apparaître ,
puisque T3 n’obtiendrait pas le verrou exclusif qu’elle exige avant que T1 ait terminé
son annulation. C’est le principe même du verrouillage rigoureux en deux phases. Dans
ce cas on arrive à montrer que les transactions peuvent être mises en série dans l’ordre
de leurs validations.
Autre variante, le verrouillage strict en deux phases : ne retient que les verrous exclusifs
jusqu’à la fin des transactions. La plupart des SGBD mettent en place une de ces deux
variantes du verrouillage en deux phases
Autres problème s:
 verrous indéfinis (deadlock) : quand les deux transactions attendent l’une des verrous
détenus par l’autre et vice versa. Il faut pouvoir les détecter et les résoudre.
 Verrou infini (livelock) : quand une transaction est maintenue indéfiniment dans un état
d’attente, si l’algorithme d’attente qui régit les transactions est injuste et ne tient pas
compte du temps maximum d’attente des transactions
Solution : mettre en place un système d’arbitrage des priorités, par lequel, plus le temps
d’attente d’une transaction est long, plus forte est la priorité de cette transaction (file
d’attente fifo)
33
Contrôle de concurrence et structures d’index
Administration de chaque page d’index comme un élément de donnée et
application du protocole v2p.
Problème : les niveaux supérieurs d’index sont susceptibles d’accès
fréquents (recherche de haut en bas) et les conflits sont quasi
systématiques.
Observations :
 Le chemin de recherche part toujours de la racine de l’arborescence et
descend vers les nœuds feuilles de l’arbre sans retour : qd un nœud de
niveau inférieur est atteint, les niveaux supérieurs deviennent inutiles.
 Qd une nouvelle valeur d’index (une clé et un pointeur) est insérée
dans un nœud et si le nœud n’est pas plein, l’insertion ne provoque
pas de changement aux nœuds de niveaux supérieurs. Ceci suggère
que, dans ce cas, nous n’avons besoin de verrouiller exclusivement
que le nœud feuille, et de ne verrouiller exclusivement les nœuds de
niveaux supérieurs que quand un nœud est plein et qu’il faut l’éclater.
34
Contrôle de concurrence et structures d’index
Stratégie de verrouillage :
 Pour des recherches, demander des verrous partagés sur les nœuds à partir de la
racine et de proche en proche en descendant le long du chemin de recherche dans
l’arborescence. Libérer le verrou sur un nœud (parent) dès qu’un verrou est obtenu
sur un nœud enfant de celui-ci.
 Dans les cas d’insertions, une approche conservatrice consiste à demander des
verrous exclusifs sur tous les nœuds à mesure que nous descendons vers le nœud
feuille à modifier. Ceci garantit qu’un éclatement d’un nœud enfant peut se
propager du bas vers le haut, pour remonter jusqu’à la racine c’est nécessaire.
Cependant, si un nœud enfant n’est pas plein, le verrou sur son nœud parent peut
être libéré.
 Une approche plus optimiste consisterait à demander des verrous partagés sur
tous les nœuds parcourus pendant la descente jusqu’au nœud feuille à modifier.
Pour ce dernier, nous demandons un verrou exclusif sur le nœud feuille même.
S’il faut éclater ce nœud, nous demandons l’élévation du verrou partagé en
verrou exclusif sur le nœud parent.. Nous poursuivons l’élévation si c’est
nécessaire jusqu’à la racine. La probabilité de devoir éclater un nœud est
généralement faible, ce qui fait de cette approche la meilleur à adopter.
La technique du verrouillage d’un nœud enfant et la libération du verrou sur le parent
s’appellent le couplage de verrouillage ou crabbing
35
Verrou mortel Deadlock
C’est l’impasse générée par deux transactions (ou plus) qui attendent l’une, que des
verrous se libèrent, alors qu’ils sont détenus par l’autre.
Time
T1
T2
t1
begin transaction
t2
verrou_écriture (soldex)
begin transaction
t3
read(soldex)
verrou_écriture(soldey)
t4
soldex = soldex – 10
read(soldey)
t5
write(soldex)
soldey = soldey + 100
t6
verrou_écriture(soldey)
write(soldey)
t7
Attente
verrou_écriture(soldex)
t8
Attente
Attente
t9
:
:
Il faut que le SGBD reconnaisse la présence du verrou indéfini ou motel (deadlock)et
qu’il le brise d’une manière ou d’une autre. Il n’existe malheureusement qu’une
seule solution pour contrer les deadlocks : abandonner une ou plusieurs des
transactions. Ceci suppose de défaire toutes les modifications apportées par la (ou
les) transaction(s) annulée(s). Dans notre cas si on annule la transaction T2, les
verrous détenus par cette transaction sont libérés, T1 pourra poursuivre son travail.
36
Verrou mortel Deadlock
Le deadlock est transparent à l’utilisateur. Le SGBD relancera lui-même les
transactions annulées.
Trois techniques permettent de gérer les deadlocks
1.
Délai impartis :
c’est l’approche la plus simple et la plus pratique. Elle est utilisée par la plupart
des SGBD commerciaux. L’inconvénient est que peut être que la transaction
qui a dépassé le temps qui lui a été imparti, n’était pas en deadlock mais
simplement en attente d’une donnée qui n’a pas encore été libéré.
2.
Prévention des deadlocks
(méthode d’estampillage) ou une variante de V2P ( le V2P conservateur), une
transaction demande et obtient tous ses verrous au moment où elle débute et,
si elle ne les obtient pas tous, attend qu’ils soient disponibles avant de
démarrer effectivement. Ce protocole présente l’avantage que si la lutte est
acharnée pour obtenir les verrou, le temps de conservation des verrous se
trouve réduit parce que les transactions ne sont jamais bloquées et
n’attendent donc pas une fois démarrées. Sauf que s’il n’y a pas beaucoup de
conflits, les verrous sont détenus plus longtemps pour rien. De plus la charge
de verrouillage/dévérouillage est élevée. Et si elle échoue dans l’obtention
d’un verrou, elle doit libérer tous les autres déjà obtenus, puis recommencer.
En pratique, une transaction n’est pas en mesure de connaître au départ les
verrous dont elle aura réellement besoin et de ce fait, risque de verrouiller
plus de données que nécessaire. (protocole rarement utilisé).
3.
Détection des deadlocks.
37
Détection des deadlocks
Construction d’un graphe des attentes indiquant les
dépendances des transactions : une transaction Ti
dépend d’une transaction Tj qd la transaction Tj
détient un verrou sur la donnée que Ti attend.
Le graphe G(N,F) est construit comme suit :
 Créer un nœud pour chaque transaction.
 Créer une flèche Ti
Tj quand la transaction Ti attend de
verrouiller un élément actuellement verrouillé par Tj
Un deadlock existe ssi le graphe des attentes contient un cycle.
y
T1
T2
x
38
Fréquence de la détection des deadlocks et choix des victimes
Comme un cycle dans le graphe des attentes est une condition nécessaire et suffisante
pour qu’un deadlock existe, l’algorithme de détection des deadlocks génère le
graphe des attentes à des intervalles réguliers dans le temps et vérifie la présence
d’un cycle.
Le choix de la longueur de l’intervalle entre les exécutions de l’algorithme est
important.
Si cet intervalle est trop court, la détection prend beaucoup du temps du processeur;
s’il est trop long, les verrous risquent de ne pas être détectés dans un intervalle
important.
Un algorithme dynamique de détection de deadlock part avec une taille initiale
d’intervalle. Chaque fois qu’aucun deadlock n’est détecté, l’intervalle de détection
peut être augmenté, et à chaque fois qu’un deadlock est détecté, l’intervalle peut
être réduit.
Dans le cas d’un deadlock, le choix de la (les) transaction(s) victime(s) dépend :
 Du temps depuis lequel la transaction s’exécute (la plus récente est moins coûteuse)
 Du nombre de données modifiées par la transaction
 Le nombre de données que la transaction doit encore mettre à jour.
Malheureusement les SGBD ne peuvent le savoir
 La victime doit avoir une priorité lors de sa relance (gestion de la famine)
39
Estampillage
Une autre approche, qui garantit aussi la sérialisation, fait appel à des estampilles de
temps, cachetées sur les transactions, de façon à classer l’exécution des transactions
dans une planification sérielle équivalente. Comme elles ne font intervenir aucun
verrou, elles ne peuvent donner lieu à des deadlocks.
Avec ces méthodes il n’y a aucune attente : les transactions qui entrent en conflit sont
simplement annulées et redémarrées avec une nouvelle estampille.
Les estampilles sont générées simplement à partir de l’horloge système au moment du
démarrage des transactions ou plus généralement, par incrémentation d’un
compteur logique lors de chaque démarrage de transaction.
Estampillage
Un protocole de contrôle de concurrence qui classe les transactions dans un ordre tel
que les transactions plus anciennes, qui portent les estampilles les plus petites,
obtiennent la plus grande priorité dans l’éventualité d’un conflit.
En plus des estampilles sur les transactions, il y aussi des estampilles sur les données
elles-mêmes. Chaque donnée possède une estampille de lecture indiquant
l’estampille de la dernière transaction ayant lu la donnée et une estampille
d’écriture indiquant l’estampille de la dernière transaction qui a effectuée une
écriture sur cette donnée.
40
Protocole de classement par ordre d’estampille
Soit une donnée A et Ti une transaction qui utilise A :
I est l’estampille de T et EL(A) l’estampille de lecture sur A et EE(A) l’estampille
d’écriture sur A.
Procédure de lecture
Si EE(A)  i alors
‘’Exécuter la lecture’’ ;
EL(A) : = Max (EL(A), i) ;
Sinon rejeter ;
Finsi
Procédure d’écriture
Si (EL(A)  i) et EE(A)  i alors
Exécuter l’écriture
EE(A) : = i ;
Sinon rejeter
Finsi
41
Algorithme avec la règle d’écriture de Thomas :
Si EL(A)  i alors
Si EE(A)  i alors
Executer l’écriture
EE(A) : = i ;
Finsi
Sinon rejeter ; finsi ;
Exemple : soient les transactions T1, T2 et T3 avec les estampilles respectives e(T1),
e(T2), e(T3), avec e(T1) < e(T2) < e(T3)
Au temps t8, l’opération d’écriture par T2 transgresse la première règle d’écriture, de
sorte que T2 est annulée et redémarrée au temps t14
Au temps t14, l’écriture par la transaction T1 peut être ignorée en toute sécurité en
respect de la règle d’écriture obsolète ignorée, puisqu’elle aurait été écrasée par
l’opération d’écriture de la transaction T3 au temps t12
42
Time
t1
t2
t3
t4
t5
t6
t7
t8
t9
t10
t11
t12
t13
t14
t15
t16
t17
t18
opération
T1
T2
T3
begin transaction
read(soldex)
read(soldex)
soldex=soldex+10 soldex=soldex+10
write(soldex)
write(soldex)
begin tansaction
read(soldey)
read(soldey)
soldey=soldey+20
soldey=soldey+20
Begin transaction
read(soldey)
read(soldey)
write(soldey)
write(soldey)
soldey=soldey+30
soldey=soldey+20
write(soldey)
write(soldey)
soldez= 100
soldez= 100
write(soldez)
write(soldez)
soldez= 50
soldez=50
commit
read(soldez)
read(soldez)
begin transaction
read(soldey)
commit
read(soldey)
soldey=soldey+20
soldey=soldey+20
write(soldey)
write(soldey)
commit
43
Récupération d’une base de données
Le processus de restauration de la base de données à un état correct dans l’éventualité
d’une défaillance
Le stockage des données fait généralement appel à différents types de supports, du
moins fiable au plus fiable : la mémoire principale, les disques magnétiques, et les
bandes magnétiques.
La mémoire principale ou mémoire vive est un système de stockage volatile, qui ne
résiste habituellement pas aux plantages du système.
Les disques magnétiques fournissent un stockage en ligne non volatile/ à la mem
principale ils sont plus fiables et bien meilleurs marché mais ils sont plus lents
(environ 100 fois plus lents).
La bande magnétique est un support de stockage hors ligne non volatile, beaucoup plus
fiable que le disque, un peu moins cher mais beaucoup plus lent puisqu’il ne
permet que des accès séquentiels.
La mémoire est considérée comme le composant de stockage principal, tandis que les
autres forment les périphériques de stockage secondaire.
Un stockage stable représente des informations dupliquées sur plusieurs supports de
stockage non volatiles (généralement des disques) qui présentent des modes de
défaillance différents (exemple la technologie des disques RAID : matrice
redondante de disques indépendants).
44
Défaillances possibles
Les plantages système dus aux erreurs de matériel ou de logiciels, conduisant à la
perte de mémoire principale.
 Les défaillances de supports de données, telles que cassures de tête de lecture ou les
supports illisibles entraînant la perte de parties du stockage secondaire
 Les erreurs de logiciel d’application, telles que les erreurs logiques dans un
programme qui accède à la base de données, provoquant la défaillance d’une ou
plusieurs transactions.
 Les catastrophes naturelles, comme les incendies, les inondations, les tremblements
de terre ou de coupures d’alimentation électrique
 Le manque de soin ou la destruction non intentionnelle des données ou des
utilitaires par les opérateurs ou les utilisateurs.
 Le sabotage, cad, la corruption ou la destruction intentionnelle des données du
matériel ou des utilitaires logiciels.
Quelque que soit la cause de la défaillance, nous devons tenir compte de deux de ses
effets : la perte de la mémoire principale, y compris des tampons de base de
données et la perte de la copie sur disque de la base de données.
Objectif : réduire ces effets et récupérer le plus de données possible.

45
L’objectif de la récupération est de réaliser deux des quatre propriétés ACID soit
l’atomicité et la durabilité en présence de défaillances. Le gestionnaire de
récupération doit s’assurer de ce que, lors de la récupération après une défaillance,
soit tous les effets d’une transaction donnée sont enregistrés de manière permanente
dans la base de données, soit aucun d’entre eux.
La situation se complique du fait que l’écriture dans la base de données n’est pas une
action atomique (en une seule étape) et qu’il se peut donc qu’une transaction ait été
validée, mais que ses effets n’aient pas encore été enregistrés dans la base de
données, simplement parce qu’ils n’ont pas encore pu atteindre la base de données.
Si une défaillance se produit entre le temps de validation et l’écriture proprement dite
dans la BD, le gestionnaire de récupération doit déterminer l’état de la transaction
ayant effectué l’écriture au moment de la défaillance. Si elle a effectué sa validation
alors, pour assurer la durabilité, le gestionnaire de récupération doit refaire (redo)
les modifications de cette transaction dans la BD (rollfarward ou annulation vers
l’avant).
A l’inverse, si la transaction ne s’est pas validée au moment de la défaillance, le
gestionnaire de récupération doit défaire (undo) ou annuler(rollback) tous les effets
de cette transaction sur la BD, pour assurer l’atomicité de la transaction
46
Undo/Redo
T1
T2
T3
T4
T5
T6
t0
tvalidation
tdéfaillance
47
T1 et T6 ne sont pas validées au moment du plantage; de ce fait au redémarrage, le
gestionnaire de récupération doit les défaire (undo).
En absence de toute information le gestionnaire de récupération doit imposer le redo
des transactions T2, T3, T4 et T5. La raison de cette incertitude réside dans le fait que
les tampons de BD volatiles ont peut être été écrits sur le disque ou peut être pas.
La gestion des tampons joue donc un rôle important dans le processus de récupération;
Utilitaires de récupération
Un SGBD doit proposer les utilitaires suivants, destinés à faciliter la récupération :
• Un mécanisme de sauvegarde, qui s’occupe des sauvegardes périodiques de copies
de la BD.
• Des outils de journalisation, qui conservent une trace de l’état actuel des transactions
et des modifications de la BD.
• Un utilitaire de points de contrôle, qui permet de rendre permanentes des
modifications de la BD en cours de progression.
• Un gestionnaire de récupération, qui permet de restaurer la BD dans un état cohérent
à la suite d’une défaillance.
48
Mécanisme de sauvegarde
Le SGBD doit offrir un mécanisme qui permette de sauvegarder des copies de la BD et
du fichier de journalisation à des intervalles réguliers, sans imposer d’arrêt
préalable du système. La copie de sauvegarde de la BD peut ensuite servir dans
l’éventualité d’une destruction de la BD ou même de simples dégâts ponctuels. La
sauvegarde peut porter sur une copie complète de la BD ou, dans le cas d’une
sauvegarde incrémentielle, des modifications apportées depuis la dernière
sauvegarde complète ou incrémentielle. La copie est généralement conservée sur un
périphérique de stockage hors ligne, tel qu’une bande magnétique.
Fichier de journalisation
Pour garder une trace de toutes les transactions de la base de données, le SGBD
entretient un fichier spécial, appelé un journal (ou log) contenant les informations
des mises à jour appliquées à la BD. Le journal comporte les données suivantes :
 Enregistrements de transactions :
 L’idf de la transaction;
 Le type d’enrgt de journal (début de trans, ajout, modif, sup, annulation,
validation);
 L’image avant de la donnée: sa val avant le chgt (seulement pour la modif et la sup)
 L’image après de la donnée: sa val après le chgt.(pour l’ajout et la modif.)
 Les infos de gestion du journal : un ptr. vers les enrgts de journal précédent et
suivant, pour cette transaction (toutes opérations).
 Enregistrements des points de contrôles.
49
Exemple de segment de fichier journal
num
T
Heure Opération
T1
T1
T2
T2
T2
T2
T3
T1
10:12
10:13
10:14
10:16
10:17
10:17
10:18
10:18
10:19
10:19
10:20
10:21
T2
T3
T3
DEMARRAGE
MODIFICATION
DEMARRAGE
AJOUT
SUPPRESSION
MODIFICATION
DEMARRAGE
VALIDATION
Pt CONTRÔLE
VALIDATION
AJOUT
VALIDATION
Objet
PersonnelEP21
PersonnelEM37
PersonnelEG9
PropriétéLM16
Image
avant
(anc val)
Image
après
(nouv val)
(nouv val)
(anc val)
(anc val)
(nouv val)
PtrP Ptr
S
0
1
0
3
4
5
0
2
2
8
4
5
6
9
11
0
6
7
11
0
12
0
T2, T3
Propriété LM4
(nouv val)
Les colonnes PtrP et PtrS représentent des pointeurs respectivement vers les enregts
de journal précédent et suivant pour chaque transaction
Etant donné l’importance du fichier journal dans le processus de récupération, celui-ci
est parfois duplexé ou triplexé (copies stockées dans des supports fiables et rapides
(disques magnétiques)
50
Le fichier journal est nécessaire en ligne pour une récupération rapide à la suite de
défaillances mineurs (annulation d’une transaction à la suite d’un deadlock, par
exemple).
Les défaillances majeures, telles que les cassures de tête de lecture, prennent plus de
temps et peuvent exiger d’accéder à une grande partie du journal, auquel cas, il est
acceptable d’attendre la mise en ligne de parties du fichier journal à partir de
périphériques de stockage hors-ligne.
Une approche de gestion de la mise hors ligne du journal consiste à scinder le journal
en ligne en deux fichiers à accès direct distincts. Les enrgts. du journal sont écrits
au fur et à mesure dans le premier fichier, jusqu’à ce que sa taille atteigne un niveau
de remplissage donné, par exemple à 70%. Un deuxième fichier journal est alors
ouvert, où tous les enrgts de journal des nouvelles transactions sont inscrits. Les
anciennes transactions continuent à s’inscrire dans le premier fichier jusqu’à leur
terme; auquel cas, le premier fichier est fermé et transféré à un stockage hors-ligne.
Après une défaillance, se pose les questions :
jusqu’à quel point il est nécessaire de remonter dans le journal?
et comment éviter de refaire des transactions validées et écrites en toute sécurité dans
la BD?
Technique des points de contrôle
51
Point de contrôle : Le point de synchronisation entre la BD et le fichier journal de
transaction. L’écriture de tous les tampons est alors forcée sur le stockage sec.
Les pts de contrôles sont planifiés à des intervalles prédéterminés et impliquent les op :
 L’écriture dans le stockage sec de tous les enregts de journal présents en M.P.
 L’écriture dans le stockage sec de tous les blocs modifiés des tampons de la BD
 L’écriture dans le fichier journal d’un enregt de point de contrôle. Cet enregt
mentionne les idfs de toutes les transactions actives au moment du point de contrôle
Si les transaction sont exécutées en série, alors, qd se produit une défaillance, nous
vérifions le fichier journal pour y trouver la dernière transaction ayant démarré
avant le dernier point de contrôle. Toute transaction plus ancienne aura été validée
auparavant et aura, de ce fait, été écrite dans la BD au moment du point de contrôle.
Nous devons refaire que la transaction active au moment du point de contrôle et
toutes les transactions subséquentes dont les enregts de démarrage et de validation
apparaissent dans le journal. Si une transaction est active au moment de la
défaillance, il est nécessaire de la défaire .
Si des transactions s’exécutent simultanément, nous refaisons toutes les transactions
validées depuis le point de contrôle et défaisons toutes les transactions actives au
moment du plantage
La gestion des points de contrôle étant coûteuse, il est fréquent de se limiter à 3 ou 4 pts
de contrôle/heure. De cette manière, il n’est pas nécessaire de récupérer plus de 15
à 20 mn de travail.
52
Undo/Redo
T1
T2
T3
T4
T5
T6
t0
Tvalidation
= tc
tdéfaillance
dans ce cas on peut éviter de refaire T2 etT3
53
Techniques de récupération
Si la base de données est endommagée de manière étendue, par exemple parce
qu’une cassure de tête de lecture d’un disque s’est produite et a détruit la BD, alors
il est nécessaire de restaurer la dernière copie de sauvegarde de la B.D. et de refaire
toutes les opérations de modif. Des transactions validées grâce au fichier journal.
Ceci suppose que le fichier journal n’a pas été endommagé lui aussi.
Généralement on recommande de placer le fichier journal sur un disque différent de
celui des principaux fichiers de la BD.
 Si la BD n’a pas été endommagée sur le plan physique mais est devenue
incohérente, parce que le système s’est planté pendant que les transactions
s’exécutaient, alors il est nécessaire de défaire les changements qui ont provoqué
l’incohérence. Il peut être également nécessaire de refaire certaines transactions
pour garantir que les maj qu’elles ont effectuées ont bien atteint le stockage
secondaire. Dans ce cas nous n’avons plus besoin de la copie de sauvegarde de la
BD car nous pouvons récupérer la BD dans un état cohérent grâce aux images
avant et après contenues dans le fichier journal.

54
Techniques de récupération à l’aide de maj différées
Dans ce cas le gestionnaire n’écrit pas les modifs dans la BD tant qu’une transaction
n’a pas atteint son pt de validation : les informations sont stockées uniquement sur
le journal.
Si une transaction défaille avant d’atteindre ce pt, elle n’aura pas l’opportunité de
modifier la BD et il n’est donc pas nécessaire de défaire ses modifications, nous
n’aurons qu’à ignorer les données du journal.
Par contre si elle défaille alors qu’elle a déjà atteint son point de validation, il faut
refaire ces transactions, si leur effets n’auront pas atteint la BD. Ceci s’effectue à
l’aide des informations du journal.
Dans l’éventualité d’une défaillance nous examinons le journal pour identifier les
transactions en progression au moment de la défaillance. En commençant par la
dernière entrée dans le fichier journal, nous remontons au point de contrôle le plus
récent.
55
Techniques de récupération à l’aide de maj immédiate
Les maj sont appliquées à la BD au fur et à mesure de leur apparition sans attendre le
point de validation. Il est essentiel d’écrire les enregistrements dans le journal avant
les écritures correspondantes dans la BD. (protocole de préécriture journal).
De même que nous devons refaire les maj des transactions validées à la suite d’une
défaillance, il est éventuellement nécessaire de défaire les effets des transactions qui
n’ont pas pu se valider à temps au moment de la défaillance. Dans ce cas le fichier
journal est utilisé. Pour défaire et refaire les transactions.
Toute transaction dont le journal mentionne un enregistrement de démarrage mais
aucun enregistrement de validation , nous devons défaire cette transaction. Cette
fois, les enregistrement du journal permettent d’écrire les images avant des champs
affectés et donc de restaurer la BD à son état avant le début de la transaction.
Les opérations de démontage (undo) son exécutées dans l’ordre inverse de leur
consignation dans le journal.
56
Sécurité d’utilisation
Tout SGBD, dans la mesure où il manipule bon nombre
d’informations plus ou moins confidentielles, doit s ‘assurer que
ces informations ne sont accédées que par des usagers (personnes
ou programmes) qui en ont le droit.
Le SGBD doit comporter des mécanisme assurant la sécurité de
l’information stockée.
Pour une base de données médicales, il doit permettre le secret
médical, pour une base de données sur un recensement, les
informations doivent rester confidentielles. Il y a quatre grande
classe de techniques à assurer la sécurité d’un système manipulant
des donnée




contrôle d’accès ou autorisation
contrôle de flux de données
contrôle d’inférence
cryptograhie
57
1. Les contrôles d’accès vérifient l’identité des usagers qui se
présentent pour utiliser le système et en conséquence leur assignent
des droits d’accès sur tel ou tel ensemble de données.
2. Les contrôles de flux consistent à surveiller les chemins
qu’emprunte l’information pour éviter qu’elle n’arrive entre les
mains de personnes mal intentionnées.
3. Contrôle d’inférence ont pour but d’éviter qu’un usager déduise, à
partir de données auxquelles il a accès, des informations qu’il ne
doit pas connaître.
4. La cryptographie a pour but de stocker ou de transporter
l’information sous une forme telle que seuls les usagers en
possession du code sont susceptibles de la comprendre.
58
Dans le cadre d’une base de données relationnelle, il n’y a pas de
distinction radicale entre l’administrateur de la base de données
qui écrit le schéma et qui fixe les droits de chacun, et le usagers
qui accèdent à la base. Dans la mesure où il est possible à tout
instant de créer (ou détruire) des relations, le schéma de la base
de données évolue dynamiquement.
Il faut donc disposer de mécanismes d’autorisation dynamiques qui
sont capables à tout moment de prendre en compte de nouveaux
droits d’accès ou au contraire d’en supprimer.
Tout usager d’un SGBD relationnel doit pouvoir créer ses propres
relations, les manipuler comme il le désire et éventuellement
autoriser d’autres usagers à les manipuler. Il peut ainsi autoriser
x à lire telle relation ou y à modifier telle autre. Cependant s’il
décide de détruire une relation, il faut que le SGBD annule
automatiquement les droits qu’il a donné à d’autres sur cette
relation. Ceci est possible, encore une fois grâce à la notion de
catalogue
59
L’usager dispose d’instructions dans le langage pour autoriser ou
interdire tel ou tel accès aux objets de la base. Tout usager qui
exploite une base de données est connu par son nom. Dans les
catalogues ce nom sert de préfixe à tous les noms d’objets crées
par cet usager de façon à permettre à des usagers différents de
posséder des objets de nom identique.
Deux commandes sont disponibles dans SQL : GRANT et
REVOQUE
A tout instant un usager qui a le droit de transmettre des privilèges
sur un objet peut utiliser la commande GRANT pour transmettre
ce privilège. Il y a le donneur et le receveur (le donneur n’est
pas forcement le propriétaire de l’objet, c’est quelqu’un qui a
reçu le privilège de transmettre le privilège à d’autres).
60
Sur une relation ou vue les privilèges sont : lire, insérer, modifier, ajouter un attribut, supprimer
une relation ou créer des index. La forme générale est :
Grant privilèges on objet to liste d’usagers [with Grant option]
Cette dernière permet au donneur d’autoriser le receveur à transmettre à d’autres les privilèges
qu’il reçoit.
Par exemple : Mohamed en tant que propriétaire de la relation Pièce à tous les droit sur cette
relation. S’il veut autoriser Ali à lire et insérer des n-uplets sur Pièce, il doit émettre la
commande :
Mohamed : Grant Read, Insert on Pièce to Ali with grant option
Le catalogue d’autorisation contient les informations suivantes :
Autorisation(donneur, nomrelation, type-relation, receveur, liste privilège)
Tout usager ayant donné un privilège peut à tout moment retirer ce privilège grâce à la
commande Revoke
Revoque privilèges on objet from liste d’usagers
On enlève les privilèges à l’usager sauf s’il les a reçu d’une autre source. Il faut appliquer cette
commande récursivement car l’usager a pu transmettre lui aussi ses privilèges à d’autres.
Problème : cas de sources multiples
61
62

similar documents