vi unidad gestiÓn de transacciones distribuidas
TRANSCRIPT
VI UNIDAD.-GESTIÓN DE
TRANSACCIONES DISTRIBUIDAS
M.I.T.I. Laura López Núñez
Materia: BASES DE DATOS DISTRIBUIDAS
Contenido 6. GESTIÓN DE TRANSACCIONES DISTRIBUIDAS
6.1. Transacciones
6.1.1. Estructura de transacciones
6.1.2. Ejecución de transacciones centralizada y distribuida
6.1.3. Recuperación de transacciones
6.2. Control de concurrencia
6.2.1. Serialización de transacciones
6.3. Algoritmos de control de concurrencia
6.3.1. Basados en bloqueo
6.3.2. Basados en estampas de tiempo
6.3.3. Pruebas de validación optimistas
6.4. Confiabilidad
6.4.1. Conceptos básicos de confiabilidad
6.4.2. Puntos de verificación y recuperación
6.4.3. Integridad
Transacciones
Los sistemas distribuidos son muy confiables debido a la posibilidad de brindar redundancia y autonomía de recursos en diferentes nodos, esto posibilita detectar y localizar fallas, sin embargo tenemos varios aspectos que representan problemas para la integridad de los recursos y que a su vez motivan el uso de transacciones
Dificultad para mantener consistencia en los datos.
Una misma vía de comunicación no siempre puede ser utilizada para suministrar interacción entre dos procesos
Requerimientos de procesamientos en paralelo
Manejo interactivo de uno o mas usuarios.
Transacciones
Una transacción en un Sistema de Gestión de Bases de Datos
(SGBD), es un conjunto de órdenes que
se ejecutan formando una unidad de trabajo, es decir, en forma
indivisible o atómica.
Un SGBD es transaccional, si es capaz de mantener la
integridad de los datos, haciendo que estas transacciones no
puedan finalizar en un estado intermedio. Cuando por alguna
causa el sistema debe cancelar la transacción, empieza a
deshacer las órdenes ejecutadas hasta dejar la BD en su
estado inicial (llamado punto de integridad), como si la orden
de la transacción nunca se hubiese realizado.
Transacciones
El lenguaje de consulta de datos SQL, provee los
mecanismos para especificar que un conjunto de
acciones deben constituir una transacción.
BEGIN TRAN: Especifica que va a empezar una
transacción.
COMMIT TRAN: Le indica al motor que puede
considerar la transacción completada con éxito.
ROLLBACK TRAN: Indica que se ha alcanzado
un fallo y que debe restablecer la base al punto de
integridad.
Transacciones Un ejemplo de transacción
La transferencia de fondos entre dos cuentas corrientes de un banco. Si queremos transferir, supongamos 5000.00 pesos de la cuenta corriente de A y B y las cuentas tienen, respectivamente, 20000.00 pesos y 0.00 pesos de saldo los pasos lógicos serían:
1. Comprobar si en la cuenta A hay dinero suficiente.
2. Restar 5000.00 pesos de la cuenta de A, con lo que su saldo pasa a ser de15000.00 pesos
3. Sumar 5000.00 pesos a la cuenta de B, con lo que los saldos quedan A =15000.00 pesos y B= 5000.00 pesos Ahora bien, si entre el paso 2 y el 3 el sistema sufre una parada o error inesperado las cuentas quedarían como A =15000 y B = 0 con lo cual se han volatilizado 5000€ y presumiblemente ni A ni B estarán contentos, y hubiesen preferido que la transacción nunca hubiese sido iniciada.
Este ejemplo ilustra por qué las transacciones tienen un comportamiento deseado de Todo o nada, o se realiza completamente o no debe tener ningún efecto.
Transacciones
Toda transacción debe cumplir cuatro propiedades ACID
En bases de datos se denomina ACID a un conjunto de
características necesarias para que una serie de instrucciones
puedan ser consideradas como una transacción. Así pues, si un
sistema de gestión de bases de datos es ACID
compliant quiere decir que el mismo cuenta con las
funcionalidades necesarias para que sus transacciones tengan
las características ACID.
ACID es un acrónimo de Atomicidad, Consistencia,
Aislamiento y Durabilidad.
Transacciones
1. Atomicidad ( Atomicity): es la propiedad que asegura que la operación se ha realizado o no, y por lo tanto ante un fallo del sistema no puede quedar a medias.
2. Consistencia (Consistency): es la propiedad que asegura que sólo se empieza aquello que se puede acabar. Por lo tanto, se ejecutan aquellas operaciones que no van a romper la reglas y directrices de integridad de la base de datos.
3. Aislamiento (Isolation): es la propiedad que asegura que una operación no puede afectar a otras. Esto asegura que la realización de dos transacciones sobre la misma información nunca generará ningún tipo de error.
4. Permanencia (Durability): es la propiedad que asegura que una vez realizada la operación, ésta persistirá y no se podrá deshacer aunque falle el sistema.
Estructura de transacciones
La estructura de una transacción usualmente viene dada
según el modelo de la transacción, estas pueden ser
planas (simples) o anidadas.
Estructura de transacciones
Transacciones planas:
Consisten en una secuencia de operaciones primitivas
encerradas entre las palabras clave BEGIN y END. Por
ejemplo:
BEGIN _TRANSACTION Reservación
....
END.
Estructura de transacciones Transacciones Anidadas :
Consiste en tener transacciones que dependen de otras, estas transacciones están incluidas dentro de otras de un nivel superior y se las conoce como subtransacciones. La transacción de nivel superior puede producir hijos (subtransacciones) que hagan más fácil la programación del sistema y mejoras del desempeño.
En las transacciones anidadas las operaciones de una transacción pueden ser así mismo otras transacciones. Por ejemplo:
BEGIN _TRANSACTION Reservación
..........
BEGIN _TRANSACTION Vuelo
........
END.( Vuelo)
......
BEGIN _TRANSACTION Hotel
........
END
......
END.
Estructura de transacciones Una transacción anidada dentro de otra transacción conserva las
mismas propiedades que la de sus padres, esto implica, que puede contener así mismo transacciones dentro de ella. Existen restricciones obvias en una transacción anidada: debe empezar después que su padre y debe terminar antes que él. Más aún, el commit de una subtransacción es condicional al commit de su padre, en otras palabras, si el padre de una o varias transacciones aborta, las subtransacciones hijas también serán abortadas.
Las transacciones anidadas proporcionan un nivel más alto de concurrencia entre transacciones. Ya que una transacción consiste de varios transacciones, es posible tener más concurrencia dentro de una sola transacción. Así también, es posible recuperarse de fallas de manera independiente de cada subtransacción. Esto limita el daño a una parte más pequeña de la transacción, haciendo que el costo de la recuperación sea menor.
Estructura de transacciones
En el segundo punto de vista se considera el orden de las lecturas y escrituras. Si las acciones de lectura y escritura pueden ser mezcladas sin ninguna restricción, entonces, a este tipo de transacciones se les conoce como generales. En contraste, si se restringe o impone que un dato debe ser leído antes de que pueda ser escrito entonces se tendrán transacciones restringidas. Si las transacciones son restringidas a que todas las acciones de lectura se realicen antes de las acciones de escritura entonces se les conoce como de dos pasos. Finalmente, existe un modelo de acción para transacciones restringidas en donde se aplica aún más la restricción de que cada par <read,write> tiene que ser ejecutado de manera atómica.
Recuperación de transacciones
Para fines de recuperación, el sistema necesita mantenerse
al tanto de cuándo la transacción se inicia, termina y se
confirma o aborta. Así pues, el gestor de recuperación se
mantiene al tanto de las siguientes operaciones:
INICIO_DE_TRANSACCIÓN: Ésta marca el principio de
la ejecución de la transacción.
LEER o ESCRIBIR: Éstas especifican operaciones de
lectura o escritura de elementos de la base de datos que
se efectúan como parte de una transacción.
Recuperación de transacciones
FIN_DE_TRANSACCIÓN: Ésta especifica que las operaciones de LEER y ESCRIBIR de la transacción han terminado y marca el límite de la ejecución de la transacción. Sin embargo, en este punto puede ser necesario verificar si los cambios introducidos por la transacción se pueden aplicar permanentemente a la base de datos (confirmar) o si la transacción debe abortarse porque viola el control de concurrencia o por alguna otra razón.
CONFIRMAR _ TRANSACCIÓN: Ésta señala que la transacción terminó con éxito y que cualquier cambio (actualizaciones) ejecutadas por ella se pueden confirmar sin peligro en la base de datos y que no se cancelarán.
REVERTIR (o ABORTAR): Ésta indica que la transacción terminó sin éxito y que cualquier cambio o efecto que pueda haberse aplicado a la base de datos se deben cancelar.
Recuperación de transacciones
Además de las anteriores, algunas técnicas de recuperación requieren operaciones adicionales como las siguientes:
DESHACER: Similar a revertir, pero se aplica a una sola operación y no a una transacción completa.
REHACER: Ésta especifica que ciertas operaciones de transacción de deben repetir (rehacer) para asegurar que todas las operaciones de una transacción confirmada se hayan aplicado con éxito a la base de datos.
Recuperación de transacciones
Control de concurrencia
La Concurrencia en las base de datos es de suprema
importancia en los sistemas de información, ya que evita
errores en el momento de ejecutar las diferentes
transacciones.
En si la concurrencia es la propiedad de los sistemas que
permiten que múltiples procesos sean ejecutados al
mismo tiempo, y que potencialmente puedan interactuar
entre sí
Control de concurrencia
Razones para permitir la concurrencia:
Aumentar la productividad: número de transacciones
ejecutadas por minuto.
Aumentar la utilización de la CPU (menos tiempo ociosa) y
Control del disco.
Reducir el tiempo medio de respuesta de transacciones (las
‘pequeñas’ no esperan a las ‘grandes’).
Control de concurrencia
¿Por qué es necesario el control de la concurrencia?
... porque pueden surgir problemas si las transacciones concurrentes se ejecutan de manera no controlada
Ejemplo sencillo: sistema de bases de datos que permite hacer y anular reservas de plazas en vuelos de diferentes compañías aéreas.
Se almacena un registro por cada vuelo, que incluye, entre otras cosas, el número de asientos reservados en el vuelo
Sean dos transacciones T1 y T2 concurrentes:
T1 transfiere N reservas realizadas en un vuelo X a otro vuelo Y
T2 reserva M plazas en el vuelo X
Control de concurrencia
Problemas potenciales provocados por la concurrencia
Aunque las transacciones pueden ser perfectamente
correctas en sí mismas, la ejecución concurrente de T1 y T2
puede producir un resultado incorrecto, debido a la
intercalación de sus operaciones, poniendo en cuestión la
integridad y la coherencia de la base de datos
Transacción T1
leer_elemento(X); X:= X-N; escribir_elemento(X); leer_elemento(Y); Y:=Y+N; escribir_elemento(Y);
Transacción T2
leer_elemento(X); X:= X+M; escribir_elemento(X);
Control de concurrencia
Problemas potenciales provocados por la concurrencia
La actualización perdida T1 y T2 que acceden a los mismos datos, tienen sus operaciones
intercaladas de modo que hacen incorrecto el valor de algún dato
T1
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);
El elemento X tiene un valor
incorrecto porque su
actualización por T1 se
‘perdió’ (se sobreescribió)
Control de concurrencia
Problemas potenciales provocados por la concurrencia
La actualización temporal (o lectura sucia)
T1 actualiza un elemento X de la BD y luego falla, pero antes de que se restaure el valor original de X, T2 tiene acceso al «valor temporal» de X
T1
leer_elemento(X); X:= X-N; escribir_elemento(X); leer_elemento(Y); …
T2
leer_elemento(X); X:= X+M; escribir_elemento(X);
T1 falla y debe devolver a X su
antiguo valor; pero mientras, T2
ha leído el valor ‘temporal’
incorrecto de X (dato sucio)
Control de concurrencia
Problemas potenciales provocados por la concurrencia
El resumen incorrecto
Otra transacción T3 calcula una función agregada de resumen sobre varios registros (suma las plazas reservadas para todos los vuelos), mientras otras transacciones, como T1, actualizan dichos registros: puede que T3 considere unos registros antes de ser actualizados y otros después
T1
leer_elemento(X); X:= X-N; escribir_elemento(X); leer_elemento(Y); Y:=Y+N; escribir_elemento(Y);
T3 suma:=0; leer_elemento(A); suma:= suma+A; … … … leer_elemento(X); suma:= suma+X; leer_elemento(Y); suma:= suma+Y; … … …
T3 lee X después de
restar N, pero lee Y
antes de sumar N, así
que el resultado es un
resumen incorrecto
(discrepancia de N)
Control de concurrencia
Problemas potenciales provocados por la concurrencia
La lectura no repetible
T4 lee un elemento X dos veces y otra transacción, como T1, modifica dicho X entre las dos lecturas: T4 recibe diferentes valores para el mismo elemento
T1
leer_elemento(X); X:= X-N; escribir_elemento(X); leer_elemento(Y); Y:=Y+N; escribir_elemento(Y);
T4
leer_elemento(X); … leer_elemento(X); …
T4 lee X antes de
restar N
T4 lee X después
de restar N
Objetivo de un protocolo de control de concurrencia: Planificar las transacciones de forma que no ocurran
interferencias entre ellas, y así evitar la aparición de los problemas mencionados
Solución obvia: no permitir intercalación de operaciones de varias transacciones
Planificación A
T1 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);
Planificación B
T1 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);
Serialización de transacciones
Pero el objetivo de un SGBD multiusuario también es maximizar el grado de concurrencia del sistema
Si se permite la intercalación de operaciones, existen muchos órdenes posibles de ejecución de las transacciones
¿Existe algún modo de identificar las ejecuciones que está garantizado que protegen la consistencia de la base de datos?
Teoría de la Serializabilidad
Planificación C: actualización perdida!
T1 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);
Planificación D: correcta!
T1 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);
Serialización de transacciones
Cada transacción comprende una secuencia de operaciones
que incluyen acciones de lectura y escritura en la BD, que
finaliza con una confirmación (commit) o anulación (rollback)
Una planificación P de n transacciones concurrentes
T1, T2 ... Tn es una secuencia de las operaciones realizadas
por dichas transacciones, sujeta a la restricción de que
para cada transacción Ti que participa en P,
sus operaciones aparecen en P
en el mismo orden en el que ocurren en Ti
Planificación de transacciones
Serialización de transacciones
Para el control de la concurrencia (y recuperación de fallos) interesa prestar mayor atención a estas operaciones:
Ejemplos de planificaciones de transacciones
El subíndice de cada operación indica la transacción que la realiza
PA: l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; c1 ; l2(X) ; e2(X) ; c2 ;
PB: l2(X) ; e2(X) ; c2 ; l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; c1 ;
PC: l1(X) ; l2(X) ; e1(X) ; l1(Y) ; e2(X) ; c2 ; e1(Y) ; c1 ;
PD: l1(X) ; e1(X) ; l2(X) ; e2(X) ; c2 ; l1(Y) ; e1(Y) ; c1 ;
PE: l1(X) ; e1(X) ; l2(X) ; e2(X) ; c2 ; l1(Y) ; r1 ;
Planificación de transacciones
operación abreviatura
leer_elemento l
escribir_elemento e
commit c
rollback r
Serialización de transacciones
Una planificación serie P es aquella en la que las operaciones de cada transacción se ejecutan consecutivamente sin que se intercalen operaciones de otras transacciones PA: l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; c1 ; l2(X) ; e2(X) ; c2 ; PB: l2(X) ; e2(X) ; c2 ; l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; c1 ;
Toda planificación serie es correcta BD consistente
Pero no se garantiza que los resultados de todas las ejecuciones en serie de las mismas transacciones sean idénticos Ejemplo: cálculo del interés de una cuenta bancaria antes o después de
realizar un ingreso considerable
en general, son inaceptables en la práctica (ineficiencia)
Serialización de transacciones
Una planificación no serie P es aquella en la que las
operaciones de un conjunto de transacciones
concurrentes se ejecutan intercaladas
PC: l1(X) ; l2(X) ; e1(X) ; l1(Y) ; e2(X) ; c2 ; e1(Y) ; c1 ;
PD: l1(X) ; e1(X) ; l2(X) ; e2(X) ; c2 ; l1(Y) ; e1(Y) ; c1 ;
Hemos de determinar qué planificaciones no serie
permiten llevar la BD a un estado al que pueda
llegarse mediante una ejecución en serie
Este es el objetivo de la
Serializabilidad
KO
Serialización de transacciones
Una planificación P (no serie) es serializable si es
equivalente a alguna planificación serie de las mismas
n transacciones
Una planificación que no es equivalente a ninguna ejecución en
serie, es una planificación no serializable
Toda planificación serializable es correcta
Produce los mismos resultados que alguna ejecución en serie
Dos maneras de definir la equivalencia entre planificaciones:
Equivalencia por conflictos
Equivalencia de vistas
Serialización de transacciones
Si dos transacciones únicamente leen un determinado
elemento de datos, no entran en conflicto entre sí y el
orden de las operaciones no es importante
Si hay dos transacciones que leen o escriben elementos
de datos independientes, no entran en conflicto entre sí y
el orden de las operaciones no es importante
Si una de las transacciones escribe un elemento de datos y
la otra lee o escribe el mismo elemento, entran en
conflicto y el orden de las operaciones sí es
importante
Equivalencia por conflictos
Serialización de transacciones
En una planificación, 2 operaciones están en conflicto si
pertenecen a diferentes transacciones, tienen acceso al mismo elemento X, y al menos una de ellas es escribir_elemento(X) Operaciones en conflicto en las planificaciones PC y PD:
PC: l1(X) ; l2(X) ; e1(X) ; l1(Y) ; e2(X) ; c2 ; e1(Y) ; c1;
PD: l1(X) ; e1(X) ; l2(X) ; e2(X) ; c2 ; l1(Y) ; e1(Y) ; c1 ;
Dos planes son equivalentes por conflictos si el orden
de cualesquiera dos operaciones en conflicto es el mismo en ambos planes
Equivalencia por conflictos
Serialización de transacciones
Una planificación P es serializable por conflictos si
equivale por conflictos a alguna planificación serie S Podremos intercambiar cada dos operaciones de P consecutivas de
transacciones distintas y sin conflicto, hasta obtener la planificación serie equivalente PD : l1(X) ; e1(X) ; l2(X) ; e2(X) ; c2 ; l1(Y) ; e1(Y) ; c1 ;
PD1: l1(X) ; e1(X) ; l2(X) ; e2(X) ; l1(Y) ; c2 ; e1(Y) ; c1 ;
PD2: l1(X) ; e1(X) ; l2(X) ; e2(X) ; l1(Y) ; e1(Y) ; c2 ; c1 ;
PD3: l1(X) ; e1(X) ; l2(X) ; e2(X) ; l1(Y) ; e1(Y) ; c1 ; c2 ;
PD4: l1(X) ; e1(X) ; l2(X) ; l1(Y) ; e2(X) ; e1(Y) ; c1 ; c2 ;
PD5: l1(X) ; e1(X) ; l2(X) ; l1(Y) ; e1(Y) ; e2(X) ; c1 ; c2 ;
PD6: l1(X) ; e1(X) ; l2(X) ; l1(Y) ; e1(Y) ; c1 ; e2(X) ; c2 ;
PD7: l1(X) ; e1(X) ; l1(Y) ; l2(X) ; e1(Y) ; c1 ; e2(X) ; c2 ;
PD8: l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; l2(X) ; c1 ; e2(X) ; c2 ;
PD9: l1(X) ; e1(X) ; l1(Y) ; e1(Y) ; c1 ; l2(X) ; e2(X) ; c2 ;
Planificación serializable por conflictos
¡Es una planificación serie!
PD es serializable
Serialización de transacciones
Construcción del grafo de precedencia (o de serialización)
Es un grafo dirigido G = ( N, A )
N es un conjunto de nodos y A es un conjunto de aristas dirigidas
Algoritmo:
Crear un nodo por cada transacción Ti en P
Crear una arista Tj Tk si Tk lee el valor de un elemento después de que Tj lo
haya escrito
Crear una arista Tj Tk si Tk escribe el valor de un elemento después de que Tj
lo haya leído
Crear una arista Tj Tk si Tk escribe el valor de un elemento después de que Tj
lo haya escrito
Ti
Detección de la serializabilidad por conflictos
Tj Tk
Serialización de transacciones
Una arista Tj Tk indica que Tj debe aparecer antes que Tk en
una planificación serie equivalente a P, pues dos operaciones
en conflicto aparecen en dicho orden en P
Si el grafo contiene un ciclo, P no es serializable por conflictos
Un ciclo es una secuencia de aristas C=((Tj Tk), (Tk Tp),... (Ti Tj))
Si no hay ciclos en el grafo, P es serializable
Es posible obtener una planificación serie S equivalente a P, mediante una
ordenación topológica de los nodos
Detección de la serializabilidad por conflictos (y 2)
T1 T2 PA
T1 T2 PB
T1 T2
PC
T1 T2 PD
Serialización de transacciones
Planificación E
Ejemplo de planificación no serializable Transacción T1 leer_elemento(X); escribir_elemento(X); leer_elemento(Y); escribir_elemento(Y);
Transacción T2 leer_elemento(Z); leer_elemento(Y); escribir_elemento(Y); leer_elemento(X); escribir_elemento(X);
Transacción T3 leer_elemento(Y); leer_elemento(Z); escribir_elemento(Y); escribir_elemento(Z);
T1 leer_elemento(X); escribir_elemento(X); leer_elemento(Y); escribir_elemento(Y);
T2 leer_elemento(Z); leer_elemento(Y); escribir_elemento(Y); leer_elemento(X); escribir_elemento(X);
T3 leer_elemento(Y); leer_elemento(Z); escribir_elemento(Y); escribir_elemento(Z);
T1 T2
Y
X
T3
Y,Z Y
Hay dos ciclos:
T1→T2→T1 y
T1→T2→T3→T1
Serialización de transacciones
Planificación F
Ejemplo de planificación serializable Transacción T1 leer_elemento(X); escribir_elemento(X); leer_elemento(Y); escribir_elemento(Y);
Transacción T2 leer_elemento(Z); leer_elemento(Y); escribir_elemento(Y); leer_elemento(X); escribir_elemento(X);
Transacción T3 leer_elemento(Y); leer_elemento(Z); escribir_elemento(Y); escribir_elemento(Z);
T1 leer_elemento(X); escribir_elemento(X); leer_elemento(Y); escribir_elemento(Y);
T2 leer_elemento(Z); leer_elemento(Y); escribir_elemento(Y); leer_elemento(X); escribir_elemento(X);
T3 leer_elemento(Y); leer_elemento(Z); escribir_elemento(Y); escribir_elemento(Z);
T1 T2 X,Y
T3
Y,Z Y
La planificación serie
equivalente es T3 →
T1 → T2
Serialización de transacciones
Es el SO el que distribuye los recursos para los procesos, y determina la intercalación de las operaciones de las transacciones concurrentes (ejecutadas como procesos del SO)
Planificación P
(ordenamiento de las
operaciones)
• Carga del sistema
• Momento de
introducción de las
transacciones
• Prioridades de los
procesos
...
Planificador de
Tareas del SO
Aplicaciones de la serializabilidad
Es necesario encontrar técnicas que garanticen la serializabilidad,
sin tener que verificar a posteriori
¡¡enfoque muy
poco práctico!!
Parece, pues, que habría que
comprobar si P es serializable una
vez ejecutadas las transacciones
incluidas en P...
Ejecución de
Transacciones
NO SI
OK
Cancelar el
efecto de P
reintentar
¿P serializable?
Serialización de transacciones
Algoritmos de control de concurrencia
El criterio de clasificación más común de los algoritmos
de control de concurrencia es el tipo de primitiva de
sincronización. Esto resulta en dos clases:
Aquellos algoritmos que están basados en acceso
mutuamente exclusivo a datos compartidos (candados o
bloqueos).
Aquellos que intentan ordenar la ejecución de las
transacciones de acuerdo a un conjunto de reglas
(protocolos).
Algoritmos de control de concurrencia
Sin embargo, esas primitivas se pueden usar en algoritmos con dos puntos de vista diferentes: el punto de vista pesimista que considera que muchas transacciones tienen conflictos con otras, o el punto de vista optimista que supone que no se presentan muchos conflictos entre transacciones.
Los algoritmos pesimistas sincronizan la ejecución concurrente de las transacciones en su etapa inicial de su ciclo de ejecución. Los algoritmos optimistas retrasan la sincronización de las transacciones hasta su terminación.
El grupo de algoritmos pesimistas consiste de algoritmos basados en candados, algoritmos basados en ordenamiento por estampas de tiempo y algoritmos híbridos. El grupo de los algoritmos optimistas se clasifican por basados en candados y basados en estampas de tiempo
Basados en bloqueo En los algoritmos basados en candados, las transacciones indican sus
intenciones solicitando candados al despachador (llamado el administrador de candados). Los candados son de lectura (rl), también llamados compartidos, o de escritura (wl), también llamados exclusivos.
Como se aprecia en la tabla siguiente, los candados de lectura presentan conflictos con los candados de escritura, dado que las operaciones de lectura y escritura son incompatibles.
rl wl
rl si no
wl no no En sistemas basados en candados, el despachador es un administrador
de candados (LM). El administrador de transacciones le pasa al administrador de candados la operación sobre la base de datos (lectura o escritura) e información asociada, como por ejemplo el elemento de datos que es accesado y el identificador de la transacción que está enviando la operación a la base de datos.
Basados en bloqueo
El administrador de candados verifica si el elemento de datos que se quiere accesar ya ha sido bloqueado por un candado. Si candado solicitado es incompatible con el candado con que el dato está bloqueado, entonces, la transacción solicitante es retrasada.
De otra forma, el candado se define sobre el dato en el modo deseado y la operación a la base de datos es transferida al procesador de datos. El administrador de transacciones es informado luego sobre el resultado de la operación.
La terminación de una transacción libera todos los candados y se puede iniciar otra transacción que estaba esperando el acceso al mismo dato.
Basados en estampas de tiempo
Los algoritmos basados en estampas de tiempo no pretenden
mantener la seriabilidad por exclusión mutua. En lugar de eso,
ellos seleccionan un orden de serialización a priori y ejecutan
las transacciones de acuerdo a ellas. Para establecer este
ordenamiento, el administrador de transacciones le asigna a
cada transacción Ti una estampa de tiempo única ts (Ti) cuando
ésta inicia. Una estampa de tiempo es un identificador simple
que sirve para identificar cada transacción de manera única.
Otra propiedad de las estampas de tiempo es la monoticidad,
esto es, dos estampas de tiempo generadas por el mismo
administrador de transacciones deben ser monotonicamente
crecientes. Así, las estampas de tiempo son valores derivados
de un dominio totalmente ordenado.
Basados en estampas de tiempo
Existen varias formas en que las estampas de tiempo se
pueden asignar. Un método es usar un contador global
monotonicamente creciente. Sin embargo, el
mantenimiento de contadores globales es un problema
en sistemas distribuidos. Por lo tanto, es preferible que
cada nodo asigne de manera autónoma las estampas de
tiempos basándose en un contador local. Para obtener la
unicidad, cada nodo le agrega al contador su propio
identificador. Así, la estampa de tiempo es un par de la
forma.
Basados en estampas de tiempo
<contador local ,identificador de nodo>
El identificador de nodo se agrega en la posición menos
significativa, de manera que, éste sirve solo en el caso en
que dos nodos diferentes le asignen el mismo contador
local a dos transacciones diferentes. El administrador de
transacciones asigna también una estampa de tiempo a
todas las operaciones solicitadas por una transacción. Más
aún, a cada elemento de datos x se le asigna una estampa
de tiempo de escritura, wts(x), y una estampa de tiempo
de lectura, rts(x); sus valores indican la estampa de tiempo
más grande para cualquier lectura y escritura de x,
respectivamente.
Basados en estampas de tiempo
El ordenamiento de estampas de tiempo (TO) se realiza
mediante la siguiente regla:
Regla TO: dadas dos operaciones en conflicto, Oi y Ok,
perteneciendo a las transacciones Ti y
Tk, respectivamente, Oij es ejecutada antes de Okl , si y
solamente si, ts ( Ti) <ts( Tk ). En este caso Ti se dice ser
un transacción más vieja y T k se dice ser una
transacción más joven.
Basados en estampas de tiempo
Dado este orden, un conflicto entre operaciones se puede resolver de la
siguiente forma:
La acción de rechazar una operación, significa que la transacción que la
envió necesita reiniciarse para obtener la estampa de tiempo más
reciente del dato e intentar hacer nuevamente la operación sobre el dato
Basados en estampas de tiempo
Ordenamiento conservador por estampas de tiempo
El ordenamiento básico por estampas de tiempo trata de
ejecutar una operación tan pronto como se recibe una
operación. Así, la ejecución de las operaciones es
progresiva pero pueden presentar muchos reinicios de
transacciones. El ordenamiento conservador de estampas de
tiempo retrasa cada operación hasta que exista la seguridad de
que no será reiniciada. La forma de asegurar lo anterior
es sabiendo que ninguna otra operación con una estampa de
tiempo menor puede llegar al despachador. Un problema que
se puede presentar al retrasar las operaciones es que ésto
puede inducir la creación de interbloqueos (deadlocks).
Basados en estampas de tiempo
Ordenamiento por estampas de tiempo múltiples
Para prevenir la formación de interbloqueos se puede seguir la estrategia siguiente. Al hacer una operación de escritura, no se modifican los valores actuales sino se crean nuevos valores. Así, puede haber copias múltiples de un dato. Para crear copias únicas se siguen las siguientes estrategias de acuerdo al tipo de operación de que se trate:
1. Una operación de lectura Ri(x) se traduce a una operación de lectura de x de una sola versión encontrando la versión de X, digamos XV , tal que, Ts (XV) es la estampa de tiempo más grande que tiene un valor menor a Ts (Ti).
2. Una operación de escritura Wi(x) se traduce en una sola version, Wi(Xw ), y es aceptada si el despachador no ha procesado cualquier lectura Rj(xr ), tal que, ts(Ti)<ts(xr)< ts(Tj)
Pruebas de validación optimistas
Algoritmos optimistas: retrasan la fase de validación
justo antes de la fase de escritura. De esta manera, una
operación sometida a un despachador optimista nunca
es retrasada.
Confiabilidad
Un sistema manejador de bases de datos confiable es
aquel que puede continuar procesando las solicitudes de
usuario aún cuando el sistema sobre el que opera no es
confiable.
Conceptos básicos de confiabilidad
Sistema, estado y falla Un sistema: se refiere a un mecanismo que consiste de una colección de componentes y sus interacciones con el medio ambiente que responden a estímulos que provienen del mismo con un patrón de comportamiento reconocible.
Estado externo de un sistema: se puede definir como la respuesta que un sistema proporciona a un estímulo externo.
Sistema no confiable: es posible que el sistema caiga en un estado interno el cual no obedece a su especificación; a este tipo de estados se les conoce como estados erróneos. Error del sistema: parte del estado interno que es incorrecta.
Falta de sistema: es cualquier error en los estados internos de las componentes del sistema. Se clasifican en: Severas (hard): casi siempre son de tipo permanente y conducen a fallas del sistema. No severas (soft): por lo general son transitorias o intermitentes.
Conceptos básicos de confiabilidad
Tipos de fallas que pueden ocurrir en un SMBD distribuido:
1.- De transacciones: se pueden deber a un error debido a datos de entrada incorrectos así como a la detección de un interbloqueo.
2.- Del sistema: En este tipo de fallas se asume que el contenido de la memoria principal se pierde, pero el contenido del almacenamiento secundario es seguro.
3.- Del medio de almacenamiento: Se refieren a las fallas que se pueden presentar en los dispositivos de almacenamiento secundario que almacenan las bases de datos.
Fallas de comunicación: En un sistema distribuido son frecuentes. Estas se pueden manifestar como pérdida de mensajes lo que lleva en un caso extremo a dividir la red en varias subredes separadas.
Conceptos básicos de confiabilidad
Protocolos REDO/UNDO Recuperación in-place Dado que las actualización in-place hacen que los valores anteriores se pierdan, es necesario mantener suficiente información de los cambios de estado en la base de datos. Esta información puede incluir entre otras cosas: -Identificador de la transacción, --Tipo de operación realizada, --Los datos accesados por la transacción para realizar la acción, --El valor anterior del dato (imagen anterior), -El valor nuevo del dato (imagen nueva).
Operación de REDO: utiliza la información del registro de la base de datos y realiza de nuevo las acciones que pudieron haber sido realizadas antes de la falla. Genera una nueva
imagen. Operación UNDO: restablece un dato a su imagen anterior utilizando la información del registro de la base de datos.
Puntos de verificación y recuperación
Un registro checkpoint se graba periódicamente en el log justo en el punto en donde se guardó, en la base de datos en el disco, el efecto de todas las operaciones de escritura hechas por las transacciones que terminaron exitosamente (llegaron al commit). Si hay una falla, las transacciones que se completaron antes del checkpoint no deben ser rehechas en el recovery (no debe aplicarse un REDO).
El DBMS debe decidir cada cuando hace un checkpoint. Esto puede ser cada m minutos o cada N transacciones completadas exitosamente, estos son parámetros del sistema.
Hacer un checkpoint implica:
Puntos de verificación y recuperación
Un registro checkpoint se graba periódicamente en el log
justo en el punto en donde se guardó, en la base de datos
en el disco, el efecto de todas las operaciones de
escritura hechas por las transacciones que terminaron
exitosamente (llegaron al commit). Si hay una falla, las
transacciones que se completaron antes del checkpoint
no deben ser rehechas en el recovery (no debe aplicarse
un REDO).
El DBMS debe decidir cada cuando hace un checkpoint.
Esto puede ser cada m minutos o cada N transacciones
completadas exitosamente, estos son parámetros del
sistema.
Puntos de verificación y recuperación
1. Suspender temporalmente la ejecución de todas las
transacciones.
2. Forzar la escritura de todas las actualizaciones de las
operaciones de las transacciones que llegaron al commit
que están en los buffers de memoria principal al disco.
3. Escribir un registro checkpoint en el log y forzar la
escritura del log en el disco.
4. Reanudar la ejecución de las transacciones.
Integridad Integridad: Asegura que los datos y estructuras reflejan los cambios en una secuencia correcta.
La integridad de la base de datos se ve en peligro generalmente por las operaciones de acceso de las aplicaciones.
Las operaciones de acceso a una base de datos se organizan en transacciones.
Calidad de la información (perspectiva de la integridad): SGBD debe asegurar que los datos se almacenan correctamente
SGBD debe asegurar que las actualizaciones de los usuarios sobre la base de datos se ejecutan correctamente y que se hacen permanentes.
Herramientas del SGBD orientadas a la integridad: Comprobar (frente a actualizaciones) las restricciones de integridad del esquema
Controlar la ejecución correcta de las actualizaciones (entorno concurrente)
Recuperar (reconstruir) la base de datos en caso de pérdidas o accidentes
Integridad Los distintos niveles de integridad que tendremos que asegurar a nuestros datos. Una vez realizado el diseño de la base de datos, hemos de preocuparnos por los siguientes puntos:
Integridad de los datos:
La creación de un modelo de las entidades del espacio del problema y las asociaciones entre ellas es sólo una parte del proceso de modelización de los datos. También se deben captar las reglas que utilizará el sistema de base de datos para asegurar que los datos físicos que realmente mantiene son, si no correctos, al menos plausibles. En otras palabras, se debe modelar la integridad de los datos.
No puede garantizarse que los datos sean fidedignos; por ejemplo, que un pedido sea de 16 unidades o de 8 unidades depende del usuario introductor de datos, con lo que para el sistema las dos posibles entradas serían validas aunque claro esta solo es una de ellas. Pero sí se puede garantizar mediante el diseño de la base de datos que los datos son conformes a las restricciones de integridad definidas para ellos.
Integridad Integridad de dominios
Una restricción de dominio es una regla que define esos valores validos. La elección de los tipo de datos (fecha, texto, etc.) es el primer paso para la determinación de las restricciones de dominio de un sistema.
El siguiente aspectos a considerar sobre la integridad de dominio es si al dominio se le permite contemplar valores desconocidos o inexistentes.
Integridad de transiciones
Las restricciones de integridad de transiciones definen los estados por los que una tupla puede pasar válidamente. Por ejemplo solo se permitirá que el saldo de un cliente cambie a de “Normal” a “Preferente” si el límite de crédito del cliente supera un determinado valor o si lleva al menos un año comerciando con la empresa. El requisito del límite de crédito seguramente estará controlado por un atributo de la relación Clientes, pero puede que el tiempo que lleva el cliente trabajando con la empresa no esté explícitamente guardado en ningún sitio. Será necesario calcular el valor de acuerdo con el registro más antiguo en el que figure el cliente en la relación Pedidos.
Integridad Integridad de entidades
Las restricciones de entidades aseguran la integridad de las entidades que son modeladas por el sistema. En el nivel más simple, la existencia de una clave principal es una restricción de entidad que impone la regla “cada entidad debe estar identificada de forma única”.
Integridad referencial
“Las claves externas no pueden quedar huérfanas”. Es decir ningún registro de la tabla externa puede contener una clave externa que no se corresponda con algún registro de la tabla principal. Las tuplas que contienen claves externas que no tienen una correspondiente clave candidata, se denominan entidades huérfanas. Tres de las formas en las que se pueden crear entidades huérfanas: Se añade una tupla externa con una clave que no se corresponde con una clave
candidata en la tabla principal
La clave candidata de la tabla principal cambia
Se elimina en la tabla principal el registro referenciado
Integridad Integridad de transacciones
Una transacción es una serie de operaciones sobre la base de datos consideradas como una única operación, de manera que cuando se cierra la transacción la base de datos queda en un estado consistente.
Las restricciones de integridad de transacciones gobiernan las formas en que se puede manipular la base de datos. A diferencia de otras restricciones, las restricciones de transacción versan sobre el procesamiento y, por tanto, por sí mismas no son parte del modelo de datos. La base de datos debe respetar todas las restricciones de integridad definidas antes de que comience la transacción y una vez finalizada ésta, aunque se pueden violar temporalmente algunas de las restricciones durante la transacción.
Las transacciones pueden involucrar a múltiples registros, múltiples relaciones e incluso múltiples bases de datos. Siendo precisos, todas las operaciones sobre una base de datos son transacciones. Incluso la actualización de un único registro existente es una transacción. Estas transacciones de bajo nivel las realiza el motor de base de datos de forma transparente y, normalmente se puede ignorar este nivel de detalle.