3 Exercices Corrigés Concurrence

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.

concurrence

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).

  1. Construire le graphe de précédence de ces transactions.
  2. Quels problèmes d’exécution pourraient survenir ?
  3. Cette exécution est-elle sérialisable ?
Q1. Contraintes
Rappels contraintes
  a. Lors de la définition du schéma (check)
  b. Par la commande CREATE ASSERTION:
    Le programmeur définit ce qui doit toujours être vrai 
    Le DBMS repère les modifications de la base pouvant affecter les contraintes, et ne les rend pas effective si elles violent une contrainte.
  c. Par l’emploi de Trigger (Event-Condition-Action rules):
    Le programmeur définit des réactions du DBMS aux changements de la base.
    Le DBMS applique celles-ci.
 
  a. Lors de la définition du schéma:
  CREATE TABLE COMPTES (
    Numero INT PRIMARY KEY,
    …,
    Solde FLOAT CHECK (Solde>=0 AND (TYPE <> ‘Epargne’ OR Solde <= 2000))
  )
 
  b. Assertion
  CREATE ASSERTION BonSoldeAssert CHECK 
  (2000 <= ALL(Select Solde FROM COMPTES WHERE Type=’Epargne’) AND 0> (Select Solde FROM COMPTES)
  
  c. Trigger
  CREATE TRIGGER BonSolde
  BEFORE INSERT OR UPDATE ON Comptes 
  FOR EACH ROW
  WHEN (:NEW.Solde<0 OR (:NEW.Solde>2000 AND :NEW.Type=’Epargne’))
  ABORT TRANSACTION;
 
Q2. Observation transaction
 
T1: A<-1500
Affiche: « A<-1500 »  — TODO: L’affichage a t’il vraiment lieu?
A<-2100 ==> Viole la contrainte « solde de type epargne implique solde < 2000 »
==> Abort de toute la transaction (Roll Back)
==> A<-1000
 
T2: A<-700
B<-1300
COMMIT
 
T3: A<- -900 ==> Viole la contrainte « solde >= 0 »
==> Abort de toute la transaction
 
T4: Affiche « A<-700 »
Affiche « B<-1300 »

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 ?

Transaction: Suite d’opérations (Lecture – Ecriture) s’appliquant sur une BD; quatre mots clés: Commence par BEGIN, termine correctement par COMMIT, échoue par ABORT, est défaite par ROLLBACK.
 
Propriétés des transactions:
A tomicité: Une transaction est soit entièrement executée soit pas du tout
C ohérence: Une transaction fait passer la BD d’un état cohérent – où les contraintes (intégrité et autres) sont vérifiées – à un état cohérent.
I solation: Aucune intéraction entre les transactions exécutées en parallèle.
D urabilité: Pas de perte des résultats d’une transaction exécutée.
 
ACID assurée par: Tolérance aux pannes (A, C, et D) + Contrôle de concurrence (principalement I, mais I a des répercussions sur C et D)
 
Q3.
Solution triviale: 1 transaction à la fois s’exécute sur la BD bloquée pour elle. 
T1 puis T2
 
Pbmes de perfs: Lecture du même objet, ecriture d’objets différents, sont des actions qui ne mettent pas en péril l’isolation -> Possibilité de paralléliser les transactions.
Pour améliorer les perfs: entrelacement de l’exécution en s’assurant que l’exécution entrelacée est équivalente à l’exécution série.
 
Illustration probleme d’entrelacement des exécutions avec Q4:
contrôle de concurrence
Sans mécanisme de contrôle de concurrence, les exécutions sont non déterministe: le résultat dépend de l’ordre des opérations inter-transactions (lectures/écritures)

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.

contrôle de concurrence

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

contrôle de concurrence

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

contrôle de concurrence

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:

wait-die

Estampilles:

T2: 1 T6: 2T5: 3T3: 4T1: 5T4: 6

Wound-wait:

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.

verrouillage altruiste

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

estampillage

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)

estampillage

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)

Partager