BASES DE DONNÉES RÉPARTIES
Master 1
MIF24
[Link]@[Link]
CM4
EVALUATION DE REQUÊTES RÉPARTIES
Evaluation de requêtes réparties
Plan d’exécution réparti
Modèles de coût
Algorithmes de décomposition de requêtes
Transactions réparties
Garantir un accès concurrent à des données réparties
MIF24
2
GESTION DE TRANSACTIONS
CONTRÔLE DE CONCURRENCE
EN CENTRALISÉ
Remerciements : Hubert Naacke (LIP6)
TRANSACTIONS
Transaction : séquence d’actions qui transforment
une BD d’un état cohérent vers un autre état cohérent
BD dans un La BD peut être dans BD dans un
état cohérent un état incohérent (autre) état cohérent
Begin Exécution End
Transaction Transaction
Actions : opérations de lecture et d’écriture de
données de différentes granularités
Granules = tuples, tables, pages disque, etc. MIF24
PROPRIÉTÉS DES TRANSACTIONS
ATOMICITE : Les opérations entre le début et la fin d’une
transaction forment une unité d’exécution (tout ou rien).
COHERENCE : Chaque transaction accède et retourne une base de
données dans un état cohérent (ex. pas de violation de contraintes
d’intégrité).
ISOLATION : Le résultat d’un ensemble de transactions
concurrentes et validées correspond à une exécution successive des
mêmes transactions (les mises à jour concurrentes sont invisibles) .
DURABILITE: Les mises-à-jour des transactions validées
persistent.
MIF24
EXEMPLE DE TRANSACTION SIMPLE
Begin_transaction Budget-update
Begin
EXEC SQL UPDATE Project
SET Budget = Budget * 1.1
WHERE Pname = ‘TheProjet’
End. {Budget-update}
La validation (commit) est automatique à la fin de
la transaction
PROPRIÉTÉS DES TRANSACTIONS
ATOMICITE : Les opérations entre le début et la fin d’une
transaction forment une unité d’exécution (tout ou rien).
COHERENCE : Chaque transaction accède et retourne une base de
données dans un état cohérent (ex. pas de violation de contraintes
d’intégrité).
ISOLATION : Le résultat d’un ensemble de transactions
concurrentes et validées correspond à une exécution successive des
mêmes transactions (les mises à jour concurrentes sont invisibles) .
DURABILITE: Les mises-à-jour des transactions validées
persistent.
MIF24
QUESTION : QUE SE PASSE-T-IL ?
BD
A B C D E
A B C D E A B C D E
Granule A Granule B Granule C
500 € 500 € 500 €
Compte Alice Compte Bob Compte Carla
T2 = transfert( B, C, 100)
T1 = transfert( A,B, 100)
MIF24
8
SI T1 EST COMPLÈTEMENT EFFECTUÉE AVANT T2
BD
A B C D E
A B C D E A B C D E
Granule A Granule B Granule C
400 € 500 € 600 €
Compte Alice Compte Bob Compte Carla
T2 = transfert( B, C, 100)
T1 = transfert( A,B, 100)
MIF24
9
EXPLICATION A
init:
B
init:
C
init:
500 500 500
500
T1 lit A X1=L1(A)
400
T1 écrit sur A E1(A, X1-100)
T1 500
T1 lit B Y1 = L1(B)
600
T1 écrit sur B E1(B, Y1 + 100)
600
T2 lit B X2 = L2(B)
500
T2 écrit sur B E2(B, X2 - 100)
T2 500
T2 lit C Y2 = L2(C)
600 MIF24
T2 écrit sur C E2(C, Y2 + 100)
10
SI LA CONCURRENCE ENTRE T1 ET T2 EST MAL GÉRÉE
BD
A B C D E
A B C D E A B C D E
Granule A Granule B Granule C
400 € 600 € 600 €
Compte Alice Compte Bob Compte Carla
T2 = transfert( B, C, 100)
T1 = transfert( A,B, 100)
MIF24
11
EXPLICATION A
init:
B
init:
C
init:
500 500 500
500
T1 lit A X1=L1(A)
400
T1 écrit sur A E1(A, X1-100)
500
T1 lit B Y1 = L1(B)
500
T2 lit B X2 = L2(B)
400
T2 écrit sur B E2(B, X2 - 100)
500
T2 lit C Y2 = L2(C)
600
T2 écrit sur C E2(C, Y2 + 100)
600 MIF24
T1 écrit sur B E1(B, Y1 + 100)
12
MORALITÉ
La mauvaise gestion de la concurrence entre T1
et T2 vient de faire :
gagner 100€ à Bob
perdre 100€ à la banque
Analyse du problème
La première exécution (correcte aux attentes) n’est pas
équivalente à la seconde.
La transaction T2 a lu une valeur ‘sale’ du granule B
La valeur lue faisait partie de l’état intermédiaire de T1
L’ordonnancement n’est donc pas correct
MIF24
13
EXÉCUTION (OU HISTOIRE)
Exécution : ordonnancement des
opérations d’un ensemble de transactions
Exemple
T1: Read(x) T2: Write(x) T3: Read(x)
Write(x) Write(y) Read(y)
Commit Read(z) Read(z)
Commit Commit
H1= {W2(x) R1(x) R3(x) W1(x) C1W2(y) R3(y) R2(z) C2 R3(z) C3}
MIF24
EXÉCUTION EN SÉRIE
Exécution en série (histoire sérielle): histoire
où il n’y a pas d’entrelacement des opérations
de transactions
T1: Read(x) T2: Write(x) T3: Read(x)
Write(x) Write(y) Read(y)
Commit Read(z) Read(z)
Commit Commit
Hs= W2(x) W2(y) R2(z) C2 R1(x) W1(x) C1 R3(x) R3(y) R3(z) C3
MIF24
T2 → T1 → T3
EXÉCUTION SÉRIALISABLE
Opérations conflictuelles :
deux opérations sont en conflit si elles accèdent le même
granule et une des deux opérations est une écriture.
Exécutions équivalentes :
deux exécutions H1 et H2 d’un ensemble de transactions
sont équivalentes (de conflit) si :
l’ordre des opérations de chaque transaction et
l’ordre des opérations conflictuelles (validées)
sont identiques dans H1 et H2.
Exécution sérialisable : exécution où il existe au
moins une exécution en série équivalente.
MIF24
EXÉCUTIONS ÉQUIVALENTES ET
SÉRIALISABLES
T1: Read(x) T2: Write(x) T3: Read(x)
Write(x) Write(y) Read(y)
Commit Read(z) Read(z)
Commit Commit
H1=W2(x) R1(x) R3(x) W1(x) C1 R3(y) W2(y) R2(z) C2 R3(z) C3
H2=W2(x) R1(x) W1(x) C1 R3(x) W2(y) R3(y) R2(z) C2 R3(z) C3
Hs= W2(x) W2(y) R2(z) C2 R1(x) W1(x) C1 R3(x) R3(y) R3(z) C3
H1 et H2 ne sont pas équivalentes !
H2 est équivalente à Hs, qui est sériel : MIF24
donc H2 est sérialisable !
GRAPHE DE PRÉCÉDENCE (GP)
Graphe de précédence GPH={V,P} pour l’exécution H:
V={T | T est une transaction validée dans H}
P={Ti → Tk si aij Ti et akl Tk sont en conflit et aij< H akl}
Théorème: l’exécution H est sérialisable
ssi GPH ne contient pas de cycle.
Exemple
• H1= W2(x) R1(x) R3(x) W1(x) C1 R3(y) W2(y) W2(z) C2 R3(z) C3
• H2= W2(x) R1(x) W1(x) C1 R3(x) W2(y) R3(y) W2(z) C2 R3(z) C3
T2 T1 T2 T1
T3 T3
H1 H2
CONTRÔLE DE CONCURRENCE
MIF24
CONTRÔLE DE CONCURRENCE
Objectif :
synchroniser les transactions concurrentes afin de
maintenir la cohérence de la BD, tout en maximisant
le degré de concurrence (multi-utilisateurs)
Principes:
exécution simultanée des transactions pour des
raisons de performance
Exemple: exécuter les opérations d’une autre transaction
quand la première commence à faire des accès disques
les résultats doivent être équivalents à des exécutions
non simultanées (isolation)
besoin de raisonner sur l’ordre d’exécution des transactionsMIF24
PROBLÈMES LIÉES À L’ISOLATION
Perte d’écritures :
L1(A) L2(A) W1(A) W2(A);
L’écriture de T1 est perdue (exemple précédent)
Lecture sale (lecture d’une mis à jour non ‘commitée’):
W1(A); R2(A); … ; abort1;
Non reproductibilité des lectures :
L1(A); W2(A’→A); L1(A);
pour A’ différent de la valeur initiale de A, alors T1 lit deux valeurs
différentes.
Lecture de tuples ‘fantôme’ :
L1(A); W2(A→); L1(B); W2(B→B’); W2(→C);
MIF24
LECTURE ‘SALE’
T1 lit B X1=L1(B) Lecture de A alors qu’il a
été modifié par une autre
T2 lit A X2 = L2(A) transaction non encore
‘Commitée’
T2 écrit sur A E2(A, X2 - 100)
T1 lit A Y1=L1(A)
T1 écrit sur B E1(B, X1 + Y1)
T2 commit abort
X
T1 commit
MIF24
22
LECTURES ‘NON-RÉPÉTABLES’
T1 lit A X1=L1(A)
T2 lit A X2 = L2(A) La seconde lecture de A
dans la même transaction
T2 écrit sur A E2(A, X2 - 100) ne retournera pas la
même valeur
T2 commit
T1 lit A Y1=L1(A)
T1 écrit sur B E1(B, X1 + Y1)
T1 commit
MIF24
23
LECTURE ‘FANTÔME’
B sera considéré à
la fin de T1 alors
T1 lit A X1=L1(A) qu’il n’existe plus
T1 lit B Y1=L1(B)
T2 supprime B E2(B, )
A n’est
T2 écrit sur A E2(A, X1 - 100) potentiellement
plus pertinent
T1 lit C Z1=L1(C) pour T1.
T2 insère D E1( ,D)
D était
T2 commit potentiellement
pertinent pour T1. MIF24
T1 commit
24
CONCRÈTEMENT SOUS ORACLE
Les différents niveaux d’isolation (10g)
READ UNCOMMITED
Permet à une transaction de lire des données qui ont été
changées mais pas encore validées
READ COMMITED
Assure qu’une transaction lit seulement des données
validées
REPETABLE READ
Place un verrou sur les données lues pour garantir que
toute relecture de la valeur dans la même transaction
retournera le même résultat
SERIALIZABLE
Assure qu’une transaction ne prend en compte que les MIF24
données validées avant le démarrage de la transaction
25
CONCRÈTEMENT SOUS ORACLE
Paramétrage du niveau d’isolation (11g)
Niveau Lecture ‘non Lecture
Lecture ‘sale’
d’isolation répétable’ ‘fantôme’
READ
Possible Possible Possible
UNCOMMITTED
READ
Impossible Possible Possible
COMMITTED
REPEARTABLE
Impossible Impossible Possible
READ
SERIALIZABLE Impossible Impossible Impossible
MIF24
26
CONCRÈTEMENT SOUS ORACLE
Paramétrage du niveau d’isolation (11g)
Niveau Lecture ‘non Lecture
Lecture ‘sale’
d’isolation répétable’ ‘fantôme’
READ
Possible Possible Possible
UNCOMMITTED
READ
Impossible Possible Possible
COMMITTED
REPEARTABLE
Impossible Impossible Possible
READ
SERIALIZABLE Impossible Impossible Impossible
Par défaut, Oracle est en « READ COMMITTED» MIF24
27
QUESTION
Pourquoi ne pas être par défaut en
‘SERIALIZABLE’?
C’est le niveau le plus restrictif qui assure une protection complète
mais qui a un impact sur les performances.
MIF24
28
ALGORITHMES DE CONTRÔLE DE
CONCURRENCE
Verrouillage à deux-phases (2PL)
Estampillage
MIF24
ALGORITHMES DE VERROUILLAGE
Les transactions font des demandes de verrous à un
gérant de verrous :
verrous en lecture (vl), appelés aussi verrous partagés (VP)
verrous en écriture (ve), appelés aussi verrous exclusifs (VX)
Compatibilité (de verrous sur le même granule) :
VP VX
VP Oui Non
(conflit)
VX Non Non
(conflit) (conflit)
VERROUILLAGE À DEUX PHASES
• Chaque transaction verrouille l’objet avant de l’utiliser.
• Quand une demande de verrou est en conflit avec un verrou
posé par une autre transaction en cours, la transaction qui
demande doit attendre.
• Quand une transaction libère son premier verrou, elle
ne peut plus demander d’autres verrous.
Point de verrouillage
Obtenir un verrou
Nb de verrous
Libérer un verrou
Phase 1 Phase 2
BEGIN END
GRAPHE D’ATTENTE (GA)
Graphe d’attente :
graphe dont les nœuds correspondent aux transactions et
les arc représentent les attentes entre transactions
Exemple
Pour X : L1, L2,E3 y
Pour Y : E2, L1, L3 T1 T2
Pour Z : L2, E3, L1
x,z x,y,z
T3
Granule VX VP Attente
x T1,T2 T3
y T2 T1 ,T3
z T2, T1 T3
PROBLÈME AVEC LE VERROUILLAGE : INTERBLOCAGE
Pour X : L1,E3
Pour Y : E3, L2
Pour Z : E2, L1
Granule Verrou-X Verrou-P Attente X Attente P
x T1 T3
y T3 T2
z T2 T1
z
Graphe d’attente : T1 T2
x y
MIF24
T3
Cycle => Interblocage
RÉSOLUTION DES INTERBLOCAGES
Prévention
définir des critères de priorité de sorte à ce que le
problème ne se pose pas
Exemple : priorité aux transactions les plus anciennes
Détection
gérer le graphe d’ attente
lancer un algorithme de détection de circuits dès
qu’une transaction attend trop longtemps
choisir une victime qui brise le circuit
MIF24
PRÉVENTION DES INTERBLOCAGES
Algorithme : Les transactions sont numérotées par
ordre d’arrivée et on suppose que Ti désire un verrou
détenu par Tj:
Choix préemptif (« priorité aux anciens »):
j > i : Ti prend le verrou et Tj est abandonnée.
j < i : Ti attend.
Choix non-préemptif (« priorité aux jeunes »):
j > i : Ti attend.
j < i : Ti est abandonnée.
Théorème : Il ne peut pas avoir d’interblocages, si
une transaction abandonnée est toujours relancée
avec le même numéro.
MIF24
TRANSACTIONS RÉPARTIES
TRANSACTION LOCALE VS TRANSACTION GLOBALE
Transaction locale
Transaction dont l’exécution s’effectue sur un seul site
Transaction globale
Transaction dont l’exécution s’effectue sur plusieurs sites
MIF24
GESTION DE TRANSACTIONS RÉPARTIES
application
Begin
Read
Write
Abort résultats
Commit
Gérant de
Transactions Globales
STrans. STrans.
Gérant de Gérant de
Transactions Locales Transactions Locales
MIF24
PROTOCOLE DE VALIDATION EN 2 ÉTAPES (2PC)
Objectif :
Exécuter un COMMIT pour une transaction répartie
Phase 1
Préparer à écrire les résultats des mises à jour dans la BD
Phase 2
Ecrire ces résultats dans la BD
Coordinateur
composant système d’un site qui applique le protocole
Participant
composant système d’un autre site qui participe dans l'exécution
MIF24
de la transaction
POINTS CLÉ DU PROTOCOLE 2PC
Lorsque le participant envoie OK au coordinateur
Le participant s’engage à valider
Le participant valide ssi le coordinateur le lui ordonne
Le coordinateur peut demander au participant d’abandonner
Lorsque le participant envoie NOK au coordinateur
Le participant peut abandonner unilatéralement
Le coordinateur décide de valider ssi tous les participants sont OK
Chaque site doit maintenir un journal des messages échangés
reprise après panne
MIF24
PROTOCOLE 2PC : MESSAGES ÉCHANGÉS
Coordinateur Participant
[Link] Initial prepare
Initial NOK
prepare* OK
NOK abort
OK* Wait Abort Ready Abort
abort* commit
commit*
Commit Commit
Légende: message reçu MIF24
message envoyé
* = de/à tous les participants
VALIDATION NORMALE
P1 Coordinateur P2
préparer préparer
prêt prêt
valider valider
fini fini
MIF24
PANNE D'UN PARTICIPANT AVANT D'ÊTRE PRÊT
P1 Coordinateur P2
préparer préparer
prêt
timeout
panne
abandon abandon
fini
} reprise
fini
MIF24
PANNE D'UN PARTICIPANT APRÈS S'ÊTRE DÉCLARÉ PRÊT
P1 Coordinateur P2
préparer préparer
prêt prêt
valider valider
panne
fini
prêt } reprise
valider
fait
MIF24
PANNE DU COORDINATEUR
P1 Coordinateur P2
préparer préparer
prêt prêt
préparer préparer
prêt prêt
valider valider
fini fini
MIF24
PROTOCOLES DE VERROUILLAGES RÉPARTIS
Traduire le verrouillage logique en verrouillages
physiques.
Sans réplication :
- gestionnaire de verrous local sur chaque site
+ facile à implémenter
+ peu de messages (2 pour verrouiller, 1 pour libérer)
- gestion des interblocages complexe
Avec réplication :
- plusieurs méthodes, dont le coût (nb de messages) dépend du
nombre de copies, du rapport lectures/écritures, de la
concurrence (verrous refusés)
MIF24
DÉTECTION DES INTERBLOCAGES
Par Timeout
Pb : bien déterminer le délai
+ pas de messages
- risque d’annulation de plusieurs transactions au lieu d’une seule
Par Graphe d’attente
Les nœuds sont les transactions. On a un arc de Ti ->Tj si Ti attend un
verrou tenu par Tj.
On construit des graphes locaux, mais les cycles doivent être
détectés sur le graphe global (union des graphes locaux).
T1 T2 T1 T2 T1 T2
Site 1 Site 2 Graphe global
MIF24
PRÉVENTION DES INTERBLOCAGES (1)
Estampille d'une transaction : e(T)
Même principe qu’en centralisé. Les transactions s’exécutent
sur n’importe quel site, et laissent une estampille pour la copie
en question. En cas d’écriture, la transaction écrit sur tous les
sites où se trouvent des copies.
Comparaison des estampilles:
T1 plus jeune que T2 e(T1) > e(T2)
Objectif: éviter les cycles dans le graphe d'attente
Situation d'attente :
T1 demande un verrou détenu par T2
T1 attend T2 seulement si T1 plus jeune que T2, sinon abandon.
Garantit un graphe d'attente sans cycle
Inconvénient: abandon d'une transaction plus ancienne
Problème: Étendre la notion d’estampille au réparti MIF24
impose d’harmoniser les horloges
PRÉVENTION DES INTERBLOCAGES (2)
Donner la priorité aux transactions les plus anciennes
wait-die : la transaction "plus jeune" abandonne au lieu d'attendre
Si T1 demande un verrou détenu par T2 et T1 plus jeune que T2
Alors T1 abandonne
wound-wait : la transaction "plus ancienne" force l'abandon des
transactions qui la gène
Si T1 demande un verrou détenu par T2 et T1 plus ancienne que T2
Alors forcer T2 à abandonner
Inconvénient : abandons aveugles
MIF24
PRÉVENTION DES INTERBLOCAGES (3)
Réduire les abandons
Abandonner seulement les transactions pouvant appartenir à un
cycle
Ne pas enlever les arcs qui ne peuvent pas appartenir à un cycle
Toujours autoriser T1 à attendre T2 si T2 n'attend aucune transaction
Recommencer les transactions abandonnées
Conserver l'estampille initiale
Evite le recommencement perpétuel des transactions
MIF24