Acc`es concurrents et Sécurité de fonctionnement

SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-1
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-2
Introduction a` la notion de transaction
Syst`emes de Gestion des Bases de Donn´ees
Partage des ressources dans les syst`emes d’exploitation
Base de donn´ees acc´ed´ee par plusieurs utilisateurs (ou programmes)
Sous-syst`eme de gestion des acc`es concurrents
Acc`es concurrents et S´ecurit´e de fonctionnement
Techniques : Verrouillage, exclusion mutuelle
Ressources partag´ees : Donn´ees et m´eta-donn´ees
Transaction
Nacer Boudjlida
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-3
Transactions : probl`eme 1 : (Non) Atomicit´e
Virement de compte a` compte : C1 = C1-m;
Programme (acc`es, modiﬁcation)
Acc`es concurrents
Probl`emes
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-4
Transactions : probl`eme 2 : (Non) Isolation
C2 = C2 + m
Transaction T1 : D´ebiter X de N
1)
2)
3)
4)
5)
6)
Transaction T2 : Cr´editer X de M
T1
T2
Si arrˆet du programme avant Ecrire(y) : Incoh´erence
Atomicit´e : “Tout ou rien”
“Tout”
Durabilit´e (Permanence des modiﬁcations)
“Rien”
Annulation des modiﬁcations
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-5
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
Probl`eme 2 : (Non) Isolation
TR-6
Probl`eme 3 : (Non) Coh´erence
Contrainte : A = B
X = 100; N = 10; M = 50
Ex´ecution avec entrelacement
T1 :
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
100
T1 :
T2 :
T2 :
T1 :
T2 :
T1 :
T2 :
t11 :
t21 :
t12 :
t22 :
t13 :
t23 :
t14 :
t24 :
t15 :
t25 :
t16 :
t26 :
Perte de mise a` jour : X = X-N
t11; t12; t13; t21; t22; t23; t14; t15; t16; t24; t25; t26 : Correct
Isolation : pas d’interf´erence pendant l’ex´ecution
t21; t22; t11; t12; t23; t13; t14; t15; t16; t24; t25; t26 : Incorrect
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-7
Probl`eme 4 : (Non) Permanence des modiﬁcations
TR-8
Probl`eme 4 : (Non) Permanence des modiﬁcations
a) (Non) R´ep´etabilit´e des lectures
Transaction T1
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
b) Tuples “fantˆomes”
Transaction T2
Transaction T1
Transaction T2
1.
Imprimer(b)
2. Imprimer(V)
3. Supprimer tout a tel que
4.
5. Imprimer(V)
Imprimer(b)
Deuxi`eme impression de
Impressions de T2 : valeurs diff´erentes
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-9
vide
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
Transactions et niveaux d’isolation : SQL 92
TR-10
Transactions et reprise
Niveau 0 : lectures “sales” permises
N´ecessit´e de contrˆoler les acc`es concurrents
- D en cours de modiﬁcation par T
- Transactions autres que T, avant validation par T :
Causes d’´echec des transactions :
* bloqu´ees en modiﬁcation
* autoris´ees a` lire D
– Erreur logiciel ou mat´eriel
– Avortement par le sous-syst`eme de gestion de la concurrence
– “Catastrophe naturelle”, etc.
Niveau 1 : lectures “sales” interdites
N´ecessit´e de r´etablir la coh´erence : Reprise
Niveau 2 : non r´ep´etabilit´e des lectures avant validation
– Revenir a` l’´etat coh´erent le plus proche de l’instant de l’incident
– M´ecanisme : Journal ou Log (“Histoire des transactions”)
Niveau 3 (Par d´efaut) : empˆecher les tuples fantˆomes
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-11
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-12
Sch´ema d’ex´ecution des transactions
Sch´ema d’ex´ecution des transactions
Transactions de mise a` jour : s´equences
Validation : rendre effectives les modiﬁcations
1. Lecture (Base
Annulation : d´efaire les actions de la transaction
M´emoire centrale)
2. Traitement (en m´emoire centrale)
´
Base)
3. Ecriture
(M´emoire centrale
Diagramme d’´etats d’une transaction
Lire
Ecrire
Politique “du tout ou rien” (Atomicit´e) :
Début de la
transaction
Active
Fin de la
transaction
Partiellement
valide
COMMIT
ROLLBACK
Si toutes les actions se sont bien pass´ees
Alors Valider la transaction (COMMIT)
Sinon Annuler ses effets (ROLLBACK)
Finsi
UHP Nancy 1, FST/MIAE, Dept Informatique
Validée
Echec
Terminée
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-13
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
Journalisation, points de validation et de contrˆole
Sch´ema d’ex´ecution des transactions
Journal :
Validit´e partielle :
– Des techniques testent l’absence d’interf´erences
– Trace des op´erations effectu´ees sur la base
– Des protocoles de reprise s’assurent qu’ils peuvent effectivement
enregistrer les modiﬁcations
– Support non volatile + Archivage p´eriodique
Types d’informations du journal, pour chaque transaction :
–
Parfois : Annulation/R´e-ex´ecution (UNDO/REDO) d’une op´eration
–
d´ebut transaction, identiﬁcation de T ;
e´ criture, identiﬁcation de T, donn´ee concern´ee, ancienne valeur,
nouvelle valeur ;
–
lecture, identiﬁcation de T, donn´ee concern´ee
–
COMMIT, identiﬁcation de T .
a Certains
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-15
a
;
syst`emes ne conservent pas de trace des op´erations de lecture.
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
Journalisation, points de validation et de contrˆole
TR-16
Journalisation, points de validation et de contrˆole
Points de contrˆole
Point de validation :
– Instant de journalisation de
TR-14
– Inscrits p´eriodiquement dans le Log
COMMIT, identiﬁcation de T
– P´eriode : intervalle de temps, nombre donn´e de mise a` jour ou
combinaison des deux
– Les actions de T ont e´ t´e r´eussi
´
– + Ecritures
dans le journal r´eussies
– Prise de point de contrˆole :
1.
2.
3.
4.
– Au-del`a de ce point : T est valide et ses MaJ sont permanentes
– En cas d’incident : le syst`eme sait quoi
annuler (“histoire en arri`ere”)
relancer, e´ ventuellement (“histoire en avant”)
UHP Nancy 1, FST/MIAE, Dept Informatique
les actions des transactions dont le point de validation dans le
journal pr´ec`ede un point de contrˆole pourront
ne pas eˆ tre r´e-ex´ecut´ees en cas d’incident
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-17
Points de validation et Points de contrˆole
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
c [email protected]
TR-18
Points de validation et Points de contrˆole
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-19
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-20
S´erialisabilit´e et plan d’ex´ecution
Transactions : S´erialisabilit´e et plan d’ex´ecution
A et I : par la m´ethode de reprise
Gestion de la concurrence fond´ee sur la s´erialisabilit´e :
C : par le programmeur et le sous-syst`eme d’int´egrit´e
L’ex´ecution concurrente de n transactions doit eˆ tre e´ quivalente
D : par les m´ecanismes de reprise et de contrˆole de la concurrence
a` (avoir le mˆeme effet pour chaque transaction que)
S´erialisabilit´e : par le contrˆole de la concurrence
leur ex´ecution s´equentielle
Plan d’ex´ecution
(ou schedule) de n transactions :
Propri´et´es (ACID) a` assurer par un g´erant de transactions :
Ordre sur les op´erations des transactions tel que pour toute
1. Atomicit´e : politique du “tout ou rien” ;
transaction
dans
2. Coh´erence : satisfaction des contraintes d’int´egrit´e ;
3. Isolation : pas d’interf´erence entre les transactions ;
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-21
pr´ec`ede une op´eration
dans
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-22
Contrˆole de la concurrence : Verrouillage
Ex´ecution s´equentielle = Succession = Plan correct
des transactions
pr´ec`ede aussi
UHP Nancy 1, FST/MIAE, Dept Informatique
S´erialisabilit´e et plan d’ex´ecution
Un plan d’ex´ecution
, si une op´eration
Possibilit´e d’entrelacement des transactions
non unique
n’autoriser que les plans d’ex´ecution corrects
4. Durabilit´e : permanence des modiﬁcations effectu´ees.
UHP Nancy 1, FST/MIAE, Dept Informatique
de
alors
Verrou : Variable associ´ee a` un granule et dont la valeur indique le type
d’op´eration possible sur un granule
est une
succession (ou serial schedule) s’il existe une permutation
Granule : unit´e de verrouillage
de (1, . . . , n) telle que P
– Base, Relation, Partie de relation, etc.
Ex´ecution s´erialisable : Plan correct
Une ex´ecution de
elle donne, pour chaque
Petite taille :
est s´erialisable si et seulement si
, le mˆeme r´esultat qu’une succession
(+)
degr´e concurrence
(-)
temps de son contrˆole
Probl`eme : n’autoriser que les ex´ecutions s´erialisables
Grande taille :
– Protocoles pessimistes : verrouillage, estampillage
(-)
– Protocoles optimistes : contrˆole a` la ﬁn d’une transaction
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-23
Contrˆole de la concurrence : Types de verrous
temps d’attente
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-24
Contrˆole de la concurrence : Types de verrous
1. Verrou binaire :
3. Verrou d’intention :
Deux e´ tats : Libre Occup´e
Transaction demande un verrou de mise a` jour
avec intention d’´ecriture
(-) Une seule transaction d´etient un granule
verrou de lecture
Compatibilit´e :
2. Verrou partag´e (Share) et verrou exclusif (Exclusive) :
Partag´e
Exclusif
Mise a` jour
En mise a` jour : Un acc`es [+ des attentes]
Partag´e
Oui
Non
Non
Compatibilit´e des verrous :
Exclusif
Non
Non
Non
Mise a` jour
Oui
Non
Non
Acc`es multiples en lecture
Partag´e
Exclusif
Partag´e
Exclusif
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-25
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-26
Verrouillage et Interblocage
Gestion des transactions : Verrouillage a` deux phases
Two Phase Locking Protocol : le plus souvent implant´e
Attentes mutuelles
1. Phase 1 (expansion) : acquisition
2. Phase 2 (r´etr´ecissement) : lib´eration et plus aucune autre acquisition
Pr´evention : Imposer a` toute transaction de verrouiller en avance tous
les e´ l´ements dont elle a besoin et n’apposer aucun verrou si un de ces
e´ l´ements n’est pas libre
Garantie de la s´erialisabilit´e
D´etection : Cycle dans un graphe d’attente
Mais verrouillage
– Nœuds : Transactions
Risques :
1. Interblocage (Deadlock)
– Arc
2. Famine (Livelock)
– Pr´esence de cycle :
1. Tuer une transaction
2. D´efaire ses actions
3. Lib´erer ses ressources
Note : Two Phase Locking strict
UHP Nancy 1, FST/MIAE, Dept Informatique
: T1 attend un granule d´etenu par T2
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-27
Verrouillage, Interblocage et Famine
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-28
Contrˆole de la concurrence : Estampillage
Exemple d’interblocage :
Estampille : Identiﬁant de transaction (date de d´ebut)
Technique fond´ee sur un ordre sur les estampilles : s´erialisabilit´e sans
interblocage
– Plan d’ex´ecution s´erialisable s’il se conforme a` l’ordre
– Succession e´ quivalente = transactions ordonn´ees sur les estampilles
Granule
acc´ed´e
Famine : Attente inﬁnie
Actions sur
– Exemple : Priorit´e toujours aux mˆemes transactions
estampill´ees
Actions estampill´ees
Rollback
– Solutions : Priorit´es dynamiques ou FIFO
UHP Nancy 1, FST/MIAE, Dept Informatique
“marqu´e” par la date de la derni`ere transaction qui y a
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-29
Contrˆole de la concurrence : Techniques “optimistes”
: autoris´ees
: violation de la s´erialisabilit´e
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
c [email protected]
TR-30
Reprise en cas d’incident (Recovery)
Reconstruire un e´ tat coh´erent a` partir “du pass´e” (Log)
Pas de contrˆole pendant l’ex´ecution des transactions
´ le plus proche possible de l’instant de l’incident
Etat
Mises a` jour locales a` la transaction
Fin de transactions : test de non violation de la s´erialisabilit´e
Adapt´ees aux transactions ayant peu d’interf´erence
Strat´egie de reprise d´epend de la gravit´e de l’incident
1. Reprise “`a foid : si d´egˆats importants
(a) Charger une sauvegarde de la base
(b) Re-ex´ecuter les transactions valides des journaux
2. Reprise “`a chaud” : D´efaire [et refaire] des actions
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-31
Reprise “`a chaud”, Technique 1 : Mise a` jour diff´er´ee
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-32
Reprise “`a chaud”, Technique 1 : Mise a` jour diff´er´ee
Mise a` jour effective apr`es le point de validation de la transaction
Modiﬁcations de donn´ees “au brouillon” (copies)
Cas e´ chec : base inchang´ee
Cas succ´es : Substitution Copie/“Original” (Shadow paging)
Cas incident au moment de la substitution : Refaire certaines actions de
transactions valid´ees
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-33
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-34
Write Ahead Log Protocol
Reprise “`a chaud” : Technique 2 : Mise a` jour imm´ediate
Journalisation des modiﬁcations avant e´ criture dans la base avant le
point de validation
Write Ahead Log Protocol :
– Implant´e dans la plupart des SGBD
– Permet la reprise mˆeme en cas d’incident entre l’´ecriture dans le
journal et l’´ecriture dans la base
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-35
WAL et reprises
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-36
Gestion des transactions : un peu de Th´eorie
Cas reprise a` chaud : Annuler les transactions non valid´ees (cf. Log)
Transaction (A.C.I.D.)
Cas reprise a` froid :
Validation (COMMIT)
1. Charger une base coh´erente (exemple : B1)
Annulation (ROLLBACK)
2. Charger les journaux ad´equats (exemple : J2, J3)
Journalisation (LOG)
3. R´e-ex´ecuter automatiquement les transactions valid´ees
S´erialisabilit´e : Ex´ecution concurrente de n transactions “´equivalente”
a` une ex´ecution s´equentielle
Remarque : cascade de ROLLBACK
– Rollback T1
– T2 a utilis´e des valeurs modiﬁ´ees par T1
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-37
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
Gestion des Transactions : un peu de Th´eorie
TR-38
1- Transactions : D´eﬁnitions
Transaction : S´equence indivisible d’actions
1. Transaction : D´eﬁnitions et probl`emes
Fin d’une transaction par :
2. Notion de s´erialisabilit´e
– Succ`es/Validation : Effets de ses op´erations sur les objets
deviennent d´eﬁnitifs ;
´
: Annulation des effets sur les objets.
– Echec/Abandon
3. M´ethodes de contrˆole de la concurrence
´ enements pour un syst`eme transactionnel :
Ev´
– Op´erations (lire, e´ crire);
– Valider/Annuler.
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-39
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
1- Transactions : D´eﬁnitions
TR-40
1- Transactions : D´eﬁnitions
Ex´ecution concurrente ou histoire d’un ensemble
Transaction
de transactions :
´ enements associ´es
= Ev´
:
– Ordre partiel sur les
– Ordre total sur les op´erations de
1.
;
2.
: Ordre partiel sur
3. L’ordre
qui concernent un mˆeme objet
;
est conserv´e dans
:
4. Les op´erations sur un mˆeme objet sont totalement ordonn´ees :
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-41
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-42
2.1- Ex´ecution s´erialisable
2- Notion de S´erialisabilit´e
´
S´erialisabilit´e : Equivalence
ex´ecution concurrente, ex´ecution
s´equentielle
D´eﬁnitions formelles
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
Techniques et m´ethodes
Plan :
Ex´ecution s´erialisable :
Une ex´ecution concurrente de transactions valid´ees est
s´erialisable si et seulement si il existe une ex´ecution en s´erie
e´ quivalente
Ex´ecution en s´erie (serial schedule) : Si pour tout couple
de
transactions, tous les e´ v´enements de l’une pr´ec`edent ceux de l’autre
dans l’ordre .
1. Ex´ecution s´erialisable
2. Ex´ecution s´erialisable commutable
Ex´ecutions e´ quivalentes : Deux ex´ecutions d’un ensemble T de
transactions sont e´ quivalentes si et seulement si,:
3. Ex´ecution s´erialisable stricte
4. Conﬂits et graphe de d´ependances
1. elles sont constitu´ees des mˆemes e´ v´enements ;
5. Modes de mise a` jour
2. elles produisent le mˆeme e´ tat ﬁnal des objets et les mˆemes r´esultats
pour les transactions.
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-43
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
2.1- Ex´ecution s´erialisable : Exemple
2.1- Ex´ecution s´erialisable : Exemple
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-45
UHP Nancy 1, FST/MIAE, Dept Informatique
TR-46
2.2- Ex´ecution s´erialisable commutable
Cas particulier d’ex´ecution s´erialisable
sur un objet
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
2.2- Ex´ecution s´erialisable commutable
Deux op´erations
TR-44
La Composition :
–
commutent si :
, e´ tat initial de ,
–
a le mˆeme effet que
sont commutatifs si :
Plus formellement :
–
: effet de
–
:
sur , e´ tant donn´e
1.
;
2.
Effet sur T de l’ex´ecution de
sur
a`
Param`etres/Valeurs retourn´es par
3.
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-47
2.2- Ex´ecution s´erialisable commutable
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-48
Une ex´ecution commutable est s´erialisable : il existe toujours une
ex´ecution en s´erie e´ quivalente a` l’ex´ecution commutable (c’est
l’ex´ecution en s´erie des transactions dans l’ordre de leurs
validations).
Remarques :
1. Commute(lire(x), lire(x)) : toujours
), e´ crire(
c [email protected]
B.2.2- Ex´ecution s´erialisable commutable (ﬁn)
Notation : Commute
2. Commute(´ecrire(
UHP Nancy 1, FST/MIAE, Dept Informatique
)) si
Ex´ecution de transactions valid´ees commutable si et seulement si :
Exemple :
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-49
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
2.3- Ex´ecution s´erialisable stricte
TR-50
2.3- Ex´ecution s´erialisable stricte (ﬁn)
Cas particulier d’ex´ecution commutable ;
Ex´ecution stricte caract´eris´ee par :
Op´erations limit´ees a` lire, e´ crire ;
1. D`es que lit un objet, d’autres transactions peuvent le lire
mais pas l’´ecrire avant la ﬁn de ;
Sans exploitation des param`etres, seules (lire, lire) commutent ;
2. D`es que e´ crit un objet, aucune transaction ne peut le lire
ou l’´ecrire tant que n’est pas termin´ee.
De la d´eﬁnition d’une ex´ecution commutable, on a :
–
Remarque :
–
– G´en´eralisable a` d’autres op´erations de consultation (
modiﬁcation ( e´ crire) ;
–
– Exploitation de la seule la commutativit´e des op´erations de
consultation.
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
c [email protected]
TR-51
lire) et de
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-52
2.4- Conﬂits et Graphe de d´ependances
2- Notion de S´erialisabilit´e : Plan
Graphe de d´ependances : Approche th´eorique permettant de valider les
m´ethodes pratiques de contrˆole de la concurrence
Plan :
1. Ex´ecution s´erialisable
3. Ex´ecution s´erialisable stricte
et
que
4. Conﬂits et graphe de d´ependances
Graphe de d´ependances :
2. Ex´ecution s´erialisable commutable
sont en conﬂit s’il existe x acc´ed´e par
.
(
5. Modes de mise a` jour
entre
et
d´epend de
et si
et
et
) si et seulement si un conﬂit existe
S´erialisabilit´e et Graphe de d´ependances :
Si le graphe de d´ependances ne comporte pas de circuit, alors
l’ex´ecution est s´erialisable.
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
c [email protected]
TR-53
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-54
2.5- Modes de mise a` jour et journalisation
2.4- Conﬂits et Graphe de d´ependances : Exemple
Annulation d´epend du mode de mise a` jour
1. Mise a` jour diff´er´ee :
Modiﬁcation sur une copie des objets (“brouillon”)
Validation par recopie du “brouillon”
2. Mise a` jour imm´ediate :
Modiﬁcation “directement” sur les objets
Effets peuvent eˆ tre visibles avant la ﬁn de la transaction (dirty
reads)
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-55
2.5- Modes de mise a` jour et journalisation
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-56
Gestion des Transactions : un peu de Th´eorie
cf. Write Ahead Log Protocol
1. Transaction : D´eﬁnitions et probl`emes
2. Notion de s´erialisabilit´e
3. M´ethodes de contrˆole de la concurrence
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-57
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-58
3- M´ethodes pessimistes de contrˆole de la concurrence
3- M´ethodes de contrˆole de la concurrence
1. Estampillage : Ordre sur des dates
1. Pessismiste : Contrˆole continu
D´etection des conﬂits au fur et a` mesure de leur apparition
2. Verrouillage : Ordre par attente
Si conﬂit : Abandon ou mise en attente de transactions
2. Optimiste : Contrˆole par certiﬁcation
` la ﬁn de la transaction : Violation de la s´erialisabilit´e ?
A
Adapt´e pour des transactions ayant peu d’interf´erences
Mal adapt´e avec mises a` jour imm´ediates : des transactions peuvent
utiliser des objets modiﬁ´es par une transaction qui sera annul´ee
Risque de cascades d’abandons)
(
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-59
3.1- Verrouillage et contrˆole de la concurrence
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-60
3.2- Estampillage (basique) et contrˆole de la concurrence
Verrous Exclusifs/Partag´es/++ : S´erialisabilit´e non assur´ee
Estampille : Date associ´ee a` chaque transaction
cf. Types de verrous et compatibilit´e
Mˆeme estampille pour une trasnsaction et chacune de ses op´erations
cf. Protocole de Verrouillage a` deux phases (Two-Phase Locking
Protocol) er s´erailisabilit´e
Objets marqu´es par l’estampille de la derni`ere transaction qui y a
acc´ed´e
cf. Probl`emes
Ordre de s´erialisation : Ordre total sur les estampilles
– Interblocage (Deadlock) : Graphe d’attente
D´ependance a priori :
– Famine (Livelock)
.
Mise en œuvre : Association a` chaque objet
1. R(x) : Estampille de lecture
2. W(x) : Estampille d’´ecriture
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-61
3.2.1- Estampillage et Mise a` jour imm´ediate
TR-62
3.2.1- Estampillage et Mise a` jour imm´ediate
b. Conﬂits (lire, e´ crire) et (´ecrire, e´ crire) :
a. Conﬂit (´ecrire, lire) : Lecture de x par T estampill´ee t
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-63
3.2.1- Estampillage et Mise a` jour imm´ediate : Exemple
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-64
3.2.1- Estampillage et Mise a` jour imm´ediate : Exemple
T1 estampill´ee 10; T2 estampill´ee 15
Histoire d’une ex´ecution concurrente :
lire
(x); lire
(y); e´ crire
(y); e´ crire
(x).
W(x) = 8; R(x) = 12
W(y) = R(y) = 8
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-65
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
SGBD : Acc`es concurrents et S´ecurit´e de fonctionnement
TR-66
Concurrence et Reprise : Conclusion
3.2.2- Estampillage et Mise a` jour diff´er´ee
Modiﬁcation de l’estampille a` la ﬁn de la transaction
S´erialisabilit´e et ACID“-it´e”
En cas de conﬂit (´ecrire, e´ crire) : Validation et e´ criture dans l’ordre des
estampilles.
Verrouillage a` deux phases (Interblocage)
Write Ahead Log Protocol
Shadow Paging
Autres m´ethodes : Utilisation de la s´emantique (typage) des op´erations.
Reprise en cas d’incident
S´ecurit´e par duplication (Mirroring)
Organisation de l’exploitation des bases (ofﬁcier de s´ecurit´e)
Transactions plates : mˆeme comportement sur tous les SGBD
Transactions imbriqu´ees : pas de mod`ele d’ex´ecution universel
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]
UHP Nancy 1, FST/MIAE, Dept Informatique
c [email protected]