3 ejercicios de competición corregidos

Los problemas de concurrencia son comunes en una base de datos. El bloqueo y el estampado son dos técnicas para evitarlos. A continuación se muestran ejercicios corregidos sobre este tema.

concurrence

Preámbulo

Expresión de restricciones
—————————

0. Preámbulo de PL/SQL
SQL:
– Declarativo por lo tanto sin estructuras de control (bucles, condiciones, etc.)
– Operaciones de conjunto de datos
=> Pocas aplicaciones se pueden lograr mediante una simple secuencia de consultas SQL; necesidad de enriquecer SQL con capacidades procesales.
3 posibilidades
– SQL incorporado (PRO*C…)
– API de comunicación (SQL-CLI…)
– Lenguaje dedicado (PL/SQL…)

Ventaja de los lenguajes dedicados: Procedimientos ejecutados en el lado del servidor -> Sólo los resultados se devuelven al cliente -> Intercambios de red mínimos

P0. Procedimientos PL/SQL

P0.1
CREAR O REEMPLAZAR EL PROCEDIMIENTO D
(noc EN CUENTAS.Numero%TYPE,
crédito EN NÚMERO )
ES
COMENZAR
ACTUALIZAR CUENTAS ESTABLECER SALDO = SALDO – débito
DONDE Número = noc;
FIN;
/

P0.2
CREAR O REEMPLAZAR EL PROCEDIMIENTO C
(noc EN CUENTAS.Numero%TYPE,
crédito EN CUENTAS.Saldo%TYPE)
ES
COMENZAR
ACTUALIZAR CUENTAS ESTABLECER SALDO = SALDO + crédito
DONDE Número = noc;
FIN;
/

P0.3
CREAR O REEMPLAZAR EL PROCEDIMIENTO S
(noc EN CUENTAS.Número%TYPE)
ES
elSaldo CUENTAS.Saldo%TYPE;
COMENZAR
SELECCIONE el saldo EN theBalance
DE CUENTAS
DONDE Número = noc;
DBMS_OUTPUT.PUT_LINE(elSaldo);
FIN;
/

P0.4
CREAR O REEMPLAZAR EL PROCEDIMIENTO V
(no de EN CUENTAS.Numero%TYPE,
noto EN CUENTAS.Numero%TYPE,
trans EN CUENTAS.Saldo%TYPE)
ES
COMENZAR
D (no de, trans);
C (noto, trans);
FIN;
/

P0.5
CREAR O REEMPLAZAR FUNCIÓN comprobar
(noc EN CUENTAS.Numero%TYPE,
importe EN CUENTAS.Saldo%TYPE)
VOLVER BOOLEANO
ES
es Solvente BOOLEAN;
elSaldo CUENTAS.Saldo%TYPE;
COMENZAR
SELECCIONE el saldo EN theBalance
DE CUENTAS
DONDE Número = noc;
SI Saldo >= monto ENTONCES
essolvente := VERDADERO;
DEMÁS
esDisolvente := FALSO;
TERMINARA SI;
RETORNO es Solvente;
Comprobación FINAL;

Ejercicio 1

Pregunta 1

Para evitar posibles problemas de concurrencia, el administrador opta por ejecutar las transacciones en serie. Consideramos el caso de dos transacciones simultáneas en la cuenta X, cuyo saldo inicial es de 1000 euros. Ambos son débitos, el primero son 400 euros, el segundo son 800 euros.

En el preciso momento en que T1 inicia su flujo, comienza T2.

Qué esta pasando ?

¿Cómo podemos acelerar la ejecución de estas transacciones?

Pregunta 2

Seis administradores de cuentas bancarias realizan cada uno, en una transacción y simultáneamente, operaciones en 4 cuentas A, B, C y D. Sea Ei(A) una operación de escritura en la cuenta A por parte del administrador i, y Li( A) a operación de lectura de la cuenta A por parte del administrador i. Considere la siguiente secuencia de operación: 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. Constrúyelo grafico precedencia de estas transacciones.
  2. ¿Qué problemas de ejecución podrían surgir?
  3. ¿Esta ejecución es serializable?
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 »

Ejercicio 2

Pregunta 3

Nos situamos en el caso del bloqueo, con gránulo de nivel tupla.

Demuestre que el algoritmo de bloqueo “detecta” el problema de esta ejecución. ¿Cuál sería el algoritmo de resolución de conflictos más adecuado para esta ejecución?

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
Sin un mecanismo de control de concurrencia, las ejecuciones no son deterministas: el resultado depende del orden de las operaciones entre transacciones (lecturas/escrituras)

Ejercicio 3

Pregunta 4

Sugerir un algoritmo algoritmo de lectura y escritura con estampación. ¿Estamos seguros de que esta ejecución sea serializable con el sistema de estampado? Demuestre que esto es cierto para cualquier ejecución no serializable.

Pregunta 5

Compare las dos familias de técnicas vistas anteriormente (bloqueo y estampado). ¿El algoritmo de estampado simple es más adecuado para esta ejecución que el bloqueo?

P4. Gráfico de precedencia

El mecanismo de control de la competencia debe proporcionar a cada transacción la ilusión de que es la única que se ejecuta en la BD, es decir, la ejecución efectiva (por lo tanto entrelazada) de las transacciones debe ser equivalente a una ejecución en serie de éstas (ejecución: secuencia ordenada de lecturas). /operaciones de escritura).
Las ejecuciones equivalentes a una ejecución en serie se denominan serializables. El mecanismo de concurrencia debe garantizar que solo genere ejecuciones serializables.

Ejecución: secuencia ordenada de operaciones de lectura/escritura por diferentes transacciones.
Ejecución en serie: Las operaciones de diferentes transacciones no se entrelazan.

contrôle de concurrence

¿Es posible reordenar la ejecución para que sea serial?

No, porque es imposible intercambiar entradas con cualquier otra operación -> Induce una relación de precedencia entre transacciones.

Más formalmente:
Ti precede a Tj (“Ti < Tj”) si Ai ocurre antes

Aj en la ejecución Ai y Aj implican el mismo objeto del BD

Ai o Aj es una acción de escritura.

Esta relación de precedencia genera el gráfico de precedencia, en el que un vértice es una transacción y una arista dirigida es una relación de precedencia.

Por ejemplo: Ti -> Tj significa que Ti precede a Tj

Vista por objeto de operaciones (más simple que la vista global, pero pierde el orden de las operaciones dentro de una transacción):

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)

Gráfico de precedencia:

T2 -> T3 <-> T5 -> T1 -> T4

T6 ->|

Propiedad del gráfico de precedencia:

Ejecución serializable si no hay ciclo (por ejemplo, arriba, T3 debe realizarse antes que T5, que debe realizarse antes de T3)

Problema: la detección de ciclos es NP completa (no determinista, polinómica, difícil)

Observó:

Propiedad de aislamiento = Las transacciones deben ejecutarse AS si estuvieran solas en la base de datos. La serialización garantiza que el resultado de una ejecución intercalada sea el mismo que el de una ejecución en serie. Pero la serialización no es una condición suficiente para garantizar que las transacciones se ejecuten de forma aislada.

Ejemplo de ejecución serializable no aislada (ABORTO en cascada):

T1 < T2 < … < Tn

contrôle de concurrence

P5. Mecanismo de aislamiento más utilizado: bloquear y desbloquear

Protocolo de bloqueo más utilizado: Bloqueo bifásico

Fase 1: se adquieren todos los bloqueos, no se realiza ningún desbloqueo

Fase 2: se completan todos los desbloqueos, no se adquieren bloqueos

Propiedad: Garantiza la serialización de la ejecución de un cronograma legal (es decir, lock1(X) no puede ir seguido de lock2(X) sino de unlock1(X))

Cuatro tipos de bloqueos: compartido VS exclusivo/corto VS largo (consulte la matriz de compatibilidad indicada)

Dos tipos de operación: Lectura y Escritura.

Diferentes grados de aislamiento:

* Grado 0 (Leer no comprometido):

Instalación de bloqueos exclusivos de escritura corta.

-> Lee incluso objetos modificados por transacciones que no se han comprometido

* Grado 1 (Lectura comprometida):

Instalación de bloqueos exclusivos de escritura larga.

Establecer bloqueos de lectura compartidos breves

-> Solo leer objetos modificados por transacciones confirmadas

* Grado 2 (Lectura Repetible):

Grado 1 + Instalación de bloqueos de lectura compartidos largos

-> Lectura repetible

* Grado 3 (Serializable):

Nivel 2 + Elimina fantasmas

El bloqueo “detecta” el problema de serialización: puntos muertos

contrôle de concurrence

Varias formas de gestionar los puntos muertos

* TimeOut: elimina las transacciones que tardan más de x segundos en ejecutarse

* Detección: Gráfico de espera

T5 <-> T3

   <- T1

   <- T4

   Gráfico construido a medida que avanza la ejecución

   Revertir cualquier transacción que pueda causar que aparezca un ciclo en el gráfico de espera

   Ejemplo: 1. T5 -> T3 2. T1 -> T5 -> T3 3. T1 -> T5 <-> T3 ==> Reversión 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)

Compartir, repartir