Les problèmes de concurrence sont fréquents dans une base de données. Le verrouillage et l’estampillage sont deux techniques pour les éviter. Voici des exercices corrigés à ce sujet.
Préambule
Expression des contraintes
—————————
0. Préambule PL/SQL
SQL:
– Déclaratif donc pas de structures de contrôle (boucles, conditions,…)
– Données+opérations ensemblistes
=> Peu d’applications réalisables par simple suite de requête SQL; besoin d’enrichir SQL avec des capacités procédurales.
3 possibilités
– Embedded SQL (PRO*C…)
– API de communication (SQL-CLI…)
– Langage dédié (PL/SQL…)
Avantage langages dédiés: Procédures exécutées côté serveur -> Seuls les résultats sont retournés au client -> Echanges réseaux minimaux
Q0. Procédures PL/SQL
Q0.1
CREATE OR REPLACE PROCEDURE D
(noc IN COMPTES.Numero%TYPE,
credit IN NUMBER )
IS
BEGIN
UPDATE COMPTES SET SOLDE = SOLDE – debit
WHERE Numero = noc;
END;
/
Q0.2
CREATE OR REPLACE PROCEDURE C
(noc IN COMPTES.Numero%TYPE,
credit IN COMPTES.Solde%TYPE)
IS
BEGIN
UPDATE COMPTES SET SOLDE = SOLDE + credit
WHERE Numero = noc;
END;
/
Q0.3
CREATE OR REPLACE PROCEDURE S
(noc IN COMPTES.Numero%TYPE)
IS
leSolde COMPTES.Solde%TYPE;
BEGIN
SELECT Solde INTO leSolde
FROM COMPTES
WHERE Numero = noc;
DBMS_OUTPUT.PUT_LINE( leSolde ) ;
END;
/
Q0.4
CREATE OR REPLACE PROCEDURE V
(nofrom IN COMPTES.Numero%TYPE,
noto IN COMPTES.Numero%TYPE,
trans IN COMPTES.Solde%TYPE)
IS
BEGIN
D (nofrom, trans);
C (noto, trans);
END;
/
Q0.5
CREATE OR REPLACE FUNCTION check
(noc IN COMPTES.Numero%TYPE,
amount IN COMPTES.Solde%TYPE)
RETURN BOOLEAN
IS
estSolvable BOOLEAN;
leSolde COMPTES.Solde%TYPE;
BEGIN
SELECT Solde INTO leSolde
FROM COMPTES
WHERE Numero = noc;
IF leSolde >= amount THEN
estSolvable := TRUE;
ELSE
estSolvable := FALSE;
END IF;
RETURN estSolvable;
END check;
Exercice 1
Question 1
Afin d’éviter d’éventuels problèmes de concurrence, l’administrateur choisit d’exécuter les transactions en série. On se place dans le cas de deux transactions simultanées sur le compte X, dont le solde est initialement de 1000 Euros. Toutes les deux sont des débits, la première est de 400 Euros, la seconde est de 800 Euros.
Au moment précis où T1 lance son débit, T2 démarre.
Que se passe-t-il ?
Comment accélérer l’exécution de ces transactions ?
Question 2
Six gestionnaires de comptes bancaires réalisent chacun dans une transaction, et simultanément, des opérations sur 4 comptes A, B, C, et D. Soient Ei(A) une opération d’écriture sur le compte A par le gestionnaire i, et Li(A) une opération de lecture du compte A par le gestionnaire i. Soit la séquence d’opération suivante: E2(A), L2(B), L6(D), E5(C), E3(A), L5(A), L1(C), L2(D), L3(C), E4(C), E3(D), L4(B), L1(B).
- Construire le graphe de précédence de ces transactions.
- Quels problèmes d’exécution pourraient survenir ?
- Cette exécution est-elle sérialisable ?
Exercice 2
Question 3
On se place dans le cas du verrouillage, avec granule niveau tuple.
Montrer que l’algorithme de verrouillage « repère » le problème de cette exécution. Quel serait l’algorithme de résolution de conflit le plus adapté à cette exécution ?
Exercice 3
Question 4
Proposer un algorithme de lecture et un algorithme d’écriture avec estampillage. Est-on sûr de rendre cette exécution sérialisable avec le système d’estampillage ? Prouvez que cela est vrai pour toute exécution non sérialisable.
Question 5
Comparer les deux familles de techniques vues précédemment (verrouillage et estampillage). L’algorithme d’estampillage simple est-il mieux adapté à cette exécution que le verrouillage ?
Q4. Graphe de précédence
Le mécanisme de controle de concurrence doit fournir à chaque transaction l’illusion qu’elle est seule à s’exécuter sur la BD, ie, l’exécution effective (donc entrelacée) des transactions doit être équivalente à une exécution en série de celles ci (exécution: séquence ordonnée d’opérations de lecture/écriture).
Les exécutions équivalentes à une exécution série sont dites sérialisables. Le mécanisme de concurrence doit s’assurer de ne générer que des exécutions sérialisables.
Exécution: séquence ordonnée d’opérations de lecture/écriture par différentes transactions.
Exécution série: Les opérations de différentes transactions ne s’entrelacent pas.
Est il possible de réordonner l’exécution pour la rendre sérielle?
Non, car impossibilité de permuter les écritures avec tout autre opération -> Induit une relation de précédence entre transactions.
Plus formellement:
Ti précède Tj (« Ti < Tj ») si Ai a lieu avant
Aj dans l’exécution Ai et Aj impliquent le meme objet de la BD
Ai ou Aj est une action d’écriture
Cette relation de précédence génère le graphe de précédence, dans lequel un sommet est une transaction, et un arc orienté une relation de précédence.
Eg: Ti -> Tj signifie Ti précède Tj
Vision par objet des opérations (plus simple que vision globale, mais perd l’ordre des opérations au sein d’une transaction):
A: E2(A) E3(A) L5(A)
B: L2(B) L4(B) L1(B)
C: E5(C) L1(C) L3(C) E4(C)
D: L6(D) L2(D) E3(D)
Graphe de précédence:
T2 -> T3 <-> T5 -> T1 -> T4
T6 ->|
Propriété graphe de précédence:
Exécution sérializable ssi absence de cycle (eg, au dessus, T3 doit être effectuée avant T5, qui doit l’être avant T3)
Problème: détecter les cycles est NP Complet (Non déterministe, Polynomial, difficile)
Remarque:
Propriété d’Isolation = Transactions doivent s’exécuter COMME si elles étaient seules sur la base. La sérialisabilité assure que le résultat d’une exécution entrelacé est le même que celui d’une exécution série. Mais, la sérialisabilité n’est pas une condition suffisante pour assurer que les transactions s’exécutent en isolation.
Exemple d’exécution sérialisable non isolée (ABORT en cascade):
T1 < T2 < … < Tn
Q5. Mécanisme le plus utilisé pour l’isolation: verrouillage (lock et unlock)
Protocole de verrouillage le plus utilisé: 2 Phase lock
Phase 1: Tous les locks sont acquis, aucun unlock n’est effectué
Phase 2: Tous les unlocks sont effectués, aucun lock n’est acquis
Propriété: Assure la sérialisabilité de l’exécution d’un schedule légal (ie, lock1(X) ne peut pas être suivi de lock2(X) mais d’unlock1(X))
Quatre types de verrous: Partagés VS Exclusifs / Courts VS longs (cf matrice de compatibilité énoncé)
Deux types d’opération: Lecture et Ecriture.
Différents degrés d’isolation:
* Degré 0 (Read uncommited):
Pose de verrous courts exclusifs en écriture
-> Lit meme les objets modifiés par des transactions qui n’ont pas commité
* Degré 1 (Read commited):
Pose de verrous longs exclusifs en écriture
Pose de verrous courts partagés en lecture
-> Ne lit que les objets modifiés par des transactions qui ont commité
* Degré 2 (Repeatable Read):
Degré 1 + Pose de verrous longs partagés en lecture
-> Lecture reproductible
* Degré 3 (Serializable):
Degré 2 + Elimine les fantômes
Le verrouillage « repère » le problème de serialisabilité: deadlocks
Plusieurs façons de gérer les deadlocks
* TimeOut: Tue les transactions qui mettent plus de x secondes à s’exécuter
* Detection: Graphe d’attente
T5 <-> T3
<- T1
<- T4
Graphe Construit au fur et à mesure de l’exécution
Rollback toute transaction pouvant faire apparaitre un cycle dans le graphe d’attente
Exemple: 1. T5 -> T3 2. T1 -> T5 -> T3 3. T1 -> T5 <-> T3 ==> Rollback de T3
Probleme: Detection de cycle toujours NP complet; peut être long si graphe large
* Prévention: Timestamps
Donne la priorité aux vieilles transactions pour empêcher la production de deadlock.
Timestamp associé à chaque transaction.
T1 veut acquérir un lock sur un objet locké par T2.
Solution 1: Wait-Die
si T1 plus vieille que T2, T1 attend
sinon T1 Rollback (et est relancé avec le même timestamp)
Solution 2: Wound-Wait (attend les vieilles transactions)
si T1 plus vieille que T2, T2 doit lui laisser le verrou et Rollback
sinon T1 attend
-> Jamais de deadlock: T1 finira bien par être la plus vieille et donc s’exécuter en priorité.
Wait-die VS Wound-wait:
Locks acquis au début d’une transaction -> Les vieilles transactions ont plus de chance d’avoir leurs locks avant les jeunes
-> Wound-wait: provoque peu de Rollback car cf supposition
Wait-die provoque bcp de Rollback car cf supposition; mais à chaque fois au début des jeunes transactions
Estampilles:
T2: 1 T6: 2T5: 3T3: 4T1: 5T4: 6
Wait-die:
Estampilles:
T2: 1 T6: 2T5: 3T3: 4T1: 5T4: 6
Wound-wait:
Q5.b.
Verrouillage altruiste: Une transaction relâche ses verrous lorsqu’elle n’en a plus besoin.
+ : Efficace
– : (i) Probleme de dirty read; (ii) Exécution à priori non 2PL donc à priori non sérialisable.
Q6.
Système d’estampillage: Attribue à chaque transaction une estampille (généralement le timestamp de sa création), empêche les accès aux objets contraires à l’ordre des estampilles -> Priorité aux jeunes transactions. Les transactions arrivant en retard sont Rollbackées et redémarrées avec une nouvelle estampille. Fait partie de la famille des protocoles optimistes, ie, méthode efficace quand peu de conflits car peu d’overhead mais potentiellement bcp de rollback.
Deux rêgles:
Read too late: Une transaction ne peut lire une donnée que si elle est plus jeune que le dernier écrivain
Write too late: Une transaction ne peut écrire une donnée que si elle est plus jeune que les derniers lecteur et écrivain
Algorithme de base:
– Pose estampille sur chaque transaction
– Chaque objet conserve l’estampille du dernier lecteur ainsi que celle du dernier écrivain
– Lorsque que Ti veut lire l’objet O:
Si estampille < O.DernierEcrivain : Read too late -> Ti ROLLBACK puis redémarre avec nouvelle estampille
Sinon OK
– Lorsque que Ti veut ecrire l’objet O:
Si Ti.estampille < O.DernierLecteur || Ti.estampille < O.DernierEcrivain : Write too late -> Ti ROLLBACK puis redémarre avec nouvelle estampille
Sinon OK
Exemple:
Estampilles:
T2: 1-8 T6: 2T5: 3-7T3: 4T1: 5T4: 6
Objets:
A (L: ; E: 1) A (L: ; E: 4)
B (L: 1; E: )
C (L: 5; E: 3-6) C (L: 5; E: 6)
D (L: 2; E: 4)
Les graphes de précédence des exécutions par estampillage n’ont jamais de cycle.
Preuve par l’absurde:
Soit le graphe de précédence cyclique d’une exécution obtenue par estampillage:
T1 -> … -> Ti <-> Tj -> … -> Tn => Ti < Tj < Ti
<=> i < j < i
Contradiction
Q8.
Estampillage bon quand peu de conflits (pas d’attente); mauvais quand beaucoup de conflits (bcp de rollback).
Verrouillage bon quand beaucoup de conflits (moins de Rollback que l’estampillage); mauvais quand peu de conflits (attentes inutiles, overhead de gestion des verrous).
Des systèmes commerciaux tentent de combiner les avantages des deux: l’estampillage multiversion (variante de l’estampillage simple abordé plus haut) pour les transactions Read Only, et le verrouillage 2PL pour les transactions Read/Write. (cf p. 978 de « DB Systems: the complete book » de Widom et Ullmann)
