View
242
Download
0
Category
Preview:
Citation preview
11/09/2009
1
PROCESAMIENTO DE TRANSACCIONES
Procesamiento de TransaccionesContenido
� Conceptos� Problemas de la Concurrencia� Necesidad de Recuperación� Transacciones� Clasificación de Planes según Recuperación� Seriabilidad
Cátedra de Bases de Datos 3
Expectativas del usuario final
� Los datos son correctos� El usuario siempre espera ver los datos correctos
� Los datos tienen que estar disponibles cuando los necesito� Todos pueden querer acceder al mismo tiempo� No importa que falle el hardware, que haya un apagón o incendio
� Los datos son para mí y mis socios� Sólo los usuarios debidamente autorizados pueden consultar y
modificar los datos
� Los tiempos de respuesta deben ser aceptables
4
CONCEPTOS BÁSICOS
� SGBD, clasificados por cantidad de usuarios concurrentes:� Monousuario � Multiusuario (multiprogramación)
� Ejecución: � Concurrente intercalada � Concurrente simultánea
Cátedra Bases de Datos
5
CONCEPTOS BÁSICOS (cont.) � Concurrencia intercalada programas A y B
A A
B B
t1 t2Cátedra Bases de Datos 6
CONCEPTOS BÁSICOS (cont.)
� Concurrencia simultanea programas C y D
C
D
t3 t4
Cátedra Bases de Datos
11/09/2009
2
7
CONCEPTOS BÁSICOS (cont.)
� Operaciones de lectura y escritura:� Leer_elemento(X): Lee un elemento de la base de
datos llamado X y lo coloca en una variable de programa (que suponemos también se llama X ).
� Escribir_elemento(X): Escribe el valor de la variable de programa X en el elemento de la base de datos llamado X.
� Transacción: ejecución de un programa que lee o modifica el contenido de la base de datos.
Cátedra Bases de Datos 8
Ejemplo de Transacciones
T1Leer_elemento(X); X:= X - N; Escribir_elemento(X);Leer_elemento(Y); Y:= Y + N; Escribir_elemento(Y);
Cátedra Bases de Datos
T2Leer_elemento(X);X:= X + M; Escribir_elemento(X);
9
¿PORQUÉ ES NECESARIO EL CONTROL DE CONCURRENCIA?
� Problema de actualización perdida
� Problema de actualización temporal (lectura sucia)
� Problema de resumen incorrecto
Cátedra Bases de Datos 10
Actualización PerdidaT1
Leer_elemento(X);
X:= X - N; Escribir_elemento(X);
Leer_elemento(Y); Y:= Y + N; Escribir_elemento(Y);
Cátedra Bases de Datos
T2
Leer_elemento(X);X:= X + M;
Escribir_elemento(X);
Se pierde la actualización realizada por T1
11
Lectura SuciaT1
Leer_elemento(X); X:= X - N; Escribir_elemento(X);
Leer_elemento(Y);
Cátedra Bases de Datos
T2
Leer_elemento(X);X:= X + M; Escribir_elemento(X);
Al fallar T1, el valor leído por T2 de X es incorrecto, y X queda inconsistente
Falla
12
Resumen IncorrectoT1
Leer_elemento(X); X:= X - N; Escribir_elemento(X);
Leer_elemento(Y); Y:= Y + N; Escribir_elemento(Y);
Cátedra Bases de Datos
T2suma :=0;Leer_Elemento (A) suma:= suma+A;
Leer_elemento(X);suma:=suma+X;Leer_elemento(Y);suma:=suma+Y
T2 lee X después de restarse NLee Y antes de sumársele NEl valor de suma es incorrecto
11/09/2009
3
13
¿PORQUÉ ES NECESARIA LA RECUPERACIÓN?
� Para ejecutar toda transacción el sistema debe asegurarse de que:
� Todas sus operaciones:� Se completen con éxito y su efecto quede � Asentado permanentemente en la base de datos,
ó� La transacción no tenga efecto alguno
sobre la base de datos ni sobre cualquierotra transacción
Cátedra Bases de Datos 14
TIPOS DE FALLOS
� Del Hardware� De la Transacción o del Sistema� Errores locales o condiciones de
excepción detectadas por la transacción (Exceptions).
� Imposición del control de concurrencia� Fallo del disco� Problemas o catástrofes físicos
Cátedra Bases de Datos
15
Control de Concurrencia y Recuperación: Temario
� Control de concurrencia� Estudio de un modelo y de los principios básicos que debe
implementar el manejador para garantizar la consistencia de la base en la situación de modificaciones concurrentes.
� Transacción� Historia (ejecución) y caracterización� Protocolos de Control de Concurrencia
� Mecanismos de Recuperación� Para asegurar un estado consistente frente a una falla.
Cátedra Bases de Datos
Transacciones
17
Modelo de transacciones / OPERACIONES
� Transacción: ejecución de un programa que lee o modifica el contenido de la base de datos
� Operaciones del programa que componen el modelo de transacción que estudiaremos
� Inicio de transacción� Leer o escribir (read o write) � Fin de transacción� Confirmar o validar (commit) � Abortar o revertir (abort)
Cátedra Bases de Datos 18
DIAGRAMA DE TRANSICIÓN DE ESTADOSPARA LA EJECUCIÓN DE TRANSACCIONES
Activa ParcialmenteConfirmada
Confirmada
Fallida
Terminada
Inicio
Transacción
Leer, Escribir
Abortar
Confirmar
Abortar
Fin de
Transacción
Cátedra Bases de Datos
11/09/2009
4
19
PROPIEDADES DE LAS TRANSACCIONES
� Atomicidad (Atomicity)
� Conservación de la consistencia (Consistency)
� Aislamiento (Isolation)
� Durabilidad o permanencia (Durability)
Se las conoce como las propiedades A C I D
Cátedra Bases de Datos 20
Propiedades ACID (cont.)
Atomicidad: una transacción es una unidad atómica de procesamiento, o bien se realiza por completo o no se realiza en absoluto
Consistencia: una ejecución correcta de la transacción debe llevar a la BD de un estado consistente a otro
Cátedra Bases de Datos
21
Aislamiento: Una transacción no debe dejar que otras puedan ver sus actualizaciones antes de ser confirmada
Durabilidad: si las modificaciones a la BD se han confirmado no deben perderse por un fallo siguiente
Cátedra Bases de Datos
Propiedades ACID (cont.)
22
Modelo de transacciones / PLANES
� Un plan (historia o schedule) P de ntransacciones T1, T2, ... Tn es � un ordenamiento para las operaciones de
las transacciones, tal que� para cada transacción Ti que participe en P, las operaciones de Ti en P deben aparecen en el mismo orden en que ocurren en Ti
Cátedra Bases de Datos
23
Ejemplo de planes
� Ejemplo:�T1: r1(x), w1 (x), c1
�T2: r2 (x), r2 (y), w2 (x), c2
�Ps: r1(x), w1 (x), c1, r2(x), r2 (y), w2 (x), c2
�Pe: r2(x), r1(x), w1(x), r2(y), c1, w2 (x), c2
Plan Serial
Plan
EntrelazadoCátedra Bases de Datos
Clasificación de los planes
� Según la complejidad del mecanismo de recuperación frente a fallas de las transacciones.
� Según el grado de concurrencia y su correctitud.
11/09/2009
5
25
Bitácora (log): Elemento básico de la recuperación
� ¿ Cómo recuperarse de los fallos ? � Mantenimiento de una bitácora (Log)
� se registran todas las operaciones de las transacciones que afectan a los valores de la BD.
� El log debe ser persistente, o sea� mantenerse en disco
� Operaciones � Deshacer (undo) � Rehacer (redo)
Cátedra Bases de Datos 26
� Tipos de registros de bitácora:� [ T, inicio ]� [ T, X ] (leer, depende del sistema si se registran o no)
� [ T, X, valor_anterior, valor_nuevo ] (escribir)
� Valor anterior o before image� [ T, confirmar ]� [ T, abortar ]
T: identificador de la Transacción
Cátedra Bases de Datos
LA BITACORA (Log) DEL SISTEMA
27
PUNTO DE CONFIRMACIÓN DE UNA TRANSACCIÓN [COMMIT]
� Una transacción T llega a su punto de confirmación cuando:� Todas sus operaciones que tienen acceso a
la base de datos se han ejecutado con éxito y
� El efecto de todas estas operaciones se ha asentado en la bitácora.
� Se registra en el Log un [ T, confirmar ]
Cátedra Bases de Datos
Clasificación según Recuperabilidad
29
Planes recuperables
Cátedra Bases de Datos
Plan Recuperable:
� Un plan es Recuperable si ninguna transacción T1 confirma
hasta que confirmaron todas las transacciones desde las cuales
T1 leyó elementos.
� Se dice que T1 lee de la transacción T2 en P, si T2 escribe
primero un elemento X que luego T1 lee.
Ejemplos
� P0r1(x), w1(x), r2(x), r1(y), w2(x), c2, a1
� P1
r1(x), w1(x), r2(x), r1(y), w2(x), a1
plan No
recuperable
plan
recuperable
11/09/2009
6
31
Caso de lectura suciaT1
Leer_elemento(X); Escribir_elemento(X);
Leer_elemento(Y);
Cátedra Bases de Datos
T2
Leer_elemento(X);Escribir_elemento(X);Commit
Al fallar T1, el valor leído por T2 de X es incorrectoFalla
32
Planes que Evitan Abortos en Cascada
Cátedra Bases de Datos
Plan que Evita Abortos en Cascada:
�Un plan Evita Abortos en Cascada si ninguna transacción
lee de transacciones no confirmadas.
� Aborto en cascada implica que una transacción no confirmada
tiene que revertirse porque leyó un elemento de una
transacción fallida
Ejemplo
� P1
r1(x), w1(x), r2(x), r1(y), w2(x), a1
� P2
w1(x, 5), w2(x, 8), a1
plan recuperable pero
NO Evita Abortos en
Cascada
Plan recuperable
que Evita Abortos
en Cascada
34
Planes estrictos
Cátedra Bases de Datos
Plan Estricto:
� Un plan es Estricto si ninguna transacción lee o escribe hasta
que todas las transacciones que escribieron ese elemento
fueron confirmadas.
Ejemplo
� P2
w1(x, 5), w2(x, 8), a1
� P3
a: r1(y), r2(z), w1(y), w2(z), c2, c1
b: r3(y), r4(z), r3(x), w4(z), w3(x), w4(u), c3, w4(x), c4
Plan Recuperable que
Evita Abortos en
Casacada pero NO
Estricto
Plan Estricto
Relación entre planes
Recuperable
Evita Abortos en Cascada
Estricto
P1 P2 P3x x xP0 x
Recuperable
11/09/2009
7
Beneficios...� Los planes recuperables aseguran que
� las transacciones confirmadas en planes entrelazados no serán revertidas, y que
� no queden datos erróneos que no se puedan corregir de una “manera simple”
� Al evitar abortos en cascada se disminuye el tiempo de recuperación evitando revertir otras transacciones.
� Los planes estrictos simplifican la recuperación de escrituras
Clasificación según su Correctitud
39
Planes Seriales y Serializables
Punto de partida sobre la “correctitud”� Si las transacciones se ejecutaran siempre en
forma serial, entonces � los datos siempre serían correctos, pero� no habría concurrencia
Cátedra Bases de Datos
Caso de la actualización perdidaT1
Leer_elemento(X);
X:= X - N; Escribir_elemento(X);
Leer_elemento(Y); Y:= Y + N; Escribir_elemento(Y);
T2
Leer_elemento(X);X:= X + M;
Escribir_elemento(X);
Se pierde la actualización realizada por T1
41
Planes Seriales y Serializables (cont.)
� Se necesitan planes entrelazados pero con comportamiento de seriales
� Un plan P de n transacciones es serializable si es equivalente a algún plan serial de las mismas n transacciones
� ¿ Cuando 2 planes son “equivalentes” ?
Cátedra Bases de Datos
Equivalencia de planes por conflicto
� Dos operaciones de un plan están en conflicto si:� Pertenecen a diferentes transacciones � Tienen acceso al mismo elemento X� Una de las dos operaciones es escribir_elemento(X)
� Dos planes son equivalentes por conflicto si� el orden de cualquier par de operaciones en conflicto es
el mismo en ambos planes
11/09/2009
8
43
Prueba de Seriabilidadpor Conflictos de un plan P
(1)Para cada transacción Ti que participaen el plan P
� Crear un nodo rotulado Ti en el grafode precedencia
Cátedra Bases de Datos 44
Prueba de Seriabilidadpor Conflictos de un plan P (cont.)
(2)Para cada caso en P donde Ti ejecuta una orden leer_elemento(X) antesde que Tj ejecuta una orden escribir_elemento(X)
� Crear una arista ( Ti → Tj ) en el grafo de precedencia;
Cátedra Bases de Datos
45
Prueba de Seriabilidadpor Conflictos de un plan P (cont.)
(3)Para cada caso en P donde Ti ejecuta escribir_elemento(X) antes de que Tj ejecuta leer_elemento(X)
� Crear una arista ( Ti → Tj ) en el grafo de precedencia;
Cátedra Bases de Datos 46
Prueba de Seriabilidadpor Conflictos de un plan P (cont.)
(4)Para cada caso en P donde Ti ejecuta una orden escribir_elemento(X) antes de que Tj ejecuta una orden escribir_elemento(X)
� crear una arista ( Ti → Tj ) en el grafo de precedencia;
Cátedra Bases de Datos
47
Prueba de Seriabilidadpor Conflictos de un plan P (cont.)
(5)
� El plan P es seriable si y sólo si el grafo de precedencia no tiene ciclos
Cátedra Bases de Datos
P1
48
PLANES EQUIVALENTES POR CONFLICTOS
� Ejemplo de cómo usarlo:T1: r1(x), w1(x), r1(y), w1(y), c1; T2: r2(x), w2(x), c2
� P1: r1(x), r2(x), w1(x), r1(y), w1(y), w2(x) , c1
� P2: r1(x), w1(x), r2(x), w2(x), r1(y), w1(y) , c2
T1 T2
P2
T1 T2No
Serializable
Serializable
Cátedra Bases de Datos
11/09/2009
9
Aplicado al caso …
� Retomemos la ejecución del caso de la actualización perdida
T1 T2
50
Caso resumen incorrectoT1
Leer_elemento(X); X:= X - N; Escribir_elemento(X);
Leer_elemento(Y); Y:= Y + N; Escribir_elemento(Y);
Cátedra Bases de Datos
T2suma :=0;Leer_Elemento (A) suma:= suma+A;
Leer_elemento(X);suma:=suma+X;Leer_elemento(Y);suma:=suma+Y
T2 lee X después de restarse NLee Y antes de sumársele NEl valor de suma es incorrecto
51
Aplicación de la serializabilidad� SGBD debe permitir la construcción de planes
serializables. Sin embargo, no se hace uso del test de serializabilidad
� Veremos métodos de control de concurrencia basados en demorar las operaciones en conflicto con otras anteriores hasta que éstas terminen
� Dos métodos: � Locking (uso de bloqueos o candados o locks) � Usando timestamps (estampillas de tiempo)
Cátedra Bases de Datos
Resumen� Necesidad de control de concurrencia y recuperación� Modelo incluyendo:
� Transacción y sus operaciones. � Planes � Caracterización de los planes
� Recuperabilidad: planes recuperables, que evitan abotros en cascada y estrictos
� Correctitud: Serializabilidad� Propiedades ACID de las Transacciones
Recommended