1
Administración de Bases de Datos
Integridad
Transacciones
Control de concurrencia
2
Administración de Bases de Datos
Transacciones
Objetivos Entender el concepto de transacción en un SGBD Entender las propiedades básicas que toda
transacción debe poseer Identificar las operaciones que pueden realizarse
dentro de una transacción Comprender los conceptos de confirmación y
reversión de una transacción Comprender los distintos estados por los que pasa
una transacción desde su inicio hasta su finalización
3
Administración de Bases de Datos
Transacciones
Contenidos
Concepto de transacción Propiedades deseables de una transacción Operaciones de una transacción
Anexo: Control de transacciones en Oracle
4
Administración de Bases de Datos
Transacción
Unidad lógica de procesamiento Secuencia de operaciones de acceso (inserción,
borradon, modificación o consulta) de la BD Pero también se considera:
Unidad lógica de integridad Unidad lógica de concurrencia Unidad lógica de recuperación
Una transacción es atómica O se ejecutan todas las operaciones que componen
la transacción, o no se realiza ninguna Ejemplo: transferencia de dinero entre dos cuentas
5
Administración de Bases de Datos
Transacción
Conjunto de lecturas/escrituras entre los límites explícitos de una transacción: Begin transaction (set_transaction) End transaction (commit, rollback)
Fin de la transacción:
COMMIT: La transacción acabó con éxito. Las modificaciones realizadas se confirman.
ROLLBACK: La transacción termina en fracaso. Las actualizaciones realizadas por la transacción deben deshacerse.
6
Administración de Bases de Datos
Propiedades deseables de las transacciones
ACID
Atomicity: La transacción es una unidad atómica de procesamiento. La transacción no puede realizarse a medias. Todo o nada.
Consistency: La transacción pasa la BD de un estado consistente a otro (antes y después de la transacción).
Isolation: La transacción debe aparecer como realizada independientemente de otras transacciones. La ejecución de una transacción no puede ser interferida por otras.
Durability: Los cambios realizados en la BD tras un COMMIT deben persistir en la BD
7
Administración de Bases de Datos
Ejemplo de transacción (1)
Transferencia de Q euros entre dos cuentas
set_transaction(CuentaO, CuentaD, Q) read(cuentaO, SaldoO)SaldoO = SaldoO – Qwrite(CuentaO, SaldoO)leer(CuentaD, SaldoD)SaldoD = SaldoD + Qwrite(CuentaD, SaldoD)
commit
No puede quedarse a medias a riesgo de dejar la BD inconsistente
Es la aplicación quien define qué conjunto de acciones constituyen una transacción
8
Administración de Bases de Datos
Ejemplo de transacción (2) pasajero(nombre, ...) vuelo(código, ...) pasajero_vuelo(nombre, código)
RI1: todo pasajero debe estar en un vuelo RI2: todo vuelo tiene al menos un pasajero
set_transactionINSERT INTO vuelo values(122, ...)INSERT INTO pasajero values(german, ...)INSERT INTO pasajero_vuelo(german, 122)
commit
Durante la transacción pueden no cumplirse las restricciones de integridad
9
Administración de Bases de Datos
Estados y operaciones de una transacción
activa Parcialmente confirmada confirmada
fallida terminada
abortar abortar
confirmarinicio fin
leer/escribir
rollback
commitprotocolos
de recuperació
n
10
Administración de Bases de Datos
Anexo: Control de transacciones en Oracle
Gestión implícita (por parte del SGBD) Inicio de transacción: ejecuta sentencia SQL Fin de transacción normal (commit), o anormal
(rollback)
Gestión explícita (por parte del usuario/programador): No existe sentencia de tipo BEGIN TRANSACTION COMMIT, ROLLBACK, SAVEPOINT ...; SET TRANSACTION <lista opciones>;
Establece modo de acceso y nivel de aislamiento de la siguiente transacción
11
Administración de Bases de Datos
Control de la concurrencia
Objetivos
Conocer la problemática asociada a la concurrencia de transacciones en los SGBD
Entender el significado de la seriabilidad y su aplicación al control de la concurrencia
Comprender algunas técnicas para el control de la concurrencia empleadas por los SGBD
12
Administración de Bases de Datos
Control de la concurrencia
Contenidos
Introducción y problemas de la concurrencia Planes de transacciones Técnicas de control de la concurrencia
Anexo 1: Niveles de aislamiento de transacciones en SQL2
Anexo 2: Acerca del control de la concurrencia en Oracle
13
Administración de Bases de Datos
Control de la concurrencia
Queremos que el SGBD multiusuario proporcione acceso simultáneo a varios clientes y usuarios ...
... pero el acceso simultáneo a los mismos datos no nos lleva necesariamente a estados consistentes
Varias transacciones introducidas por los usuarios, que se ejecutan de manera concurrente, pueden leer/modificar los mismos elementos
Posibles problemas:
Pérdida de actualizaciones Actualizaciones temporales (o valores sucios) Totales incorrectos
14
Administración de Bases de Datos
Ejemplo: control de concurrencia
Imaginemos un sistema de reserva de vuelos T1 transfiere N reservas del vuelo X al Y T2 reserva un asiento en el vuelo X
T1 T2
read(x) read(x)x = x – N x = x + 1write(x) write(x)read(y)y = y + Nwrite(y)
15
Administración de Bases de Datos
Actualización perdida
T1 T2
read(x)x = x - N. read(x). x = x + 1write(x) .read(y) .. write(x)y = y + Nwrite(y)
x tiene un valor incorrecto porque T2
sobreescribió su valor
16
Administración de Bases de Datos
Actualización temporal (lectura sucia)
T1 T2
read(x)x = x - Nwrite(x). read(x). x = x + 1. write(x)read(y)... Fallo!
T2 ha leído un valor sucio temporal
El sistema restaura el
valor original de x
17
Administración de Bases de Datos
FantasmasT1 T3
. s = 0
. read(a)
. s = s + aread(x) .x = x – N .write(x) .. read(x). s = s + x. read(y). s = s + yread(y)y = y + Nwrite(y)
T3 lee x después de restar N y lee
y antes que N sea añadida: se
obtiene una suma errónea
18
Administración de Bases de Datos
Lectura irrepetible
T1 T2
. read(x)read(x) .x = x – N .write(x) .. read(x)
T2 recibe diferentes valores
para el mismo elemento
19
Administración de Bases de Datos
Planes de transacciones
Un plan es un orden de ejecución de las operaciones de varias transacciones que se ejecutan de manera concurrente
Un plan P de N transacciones T1, T2, ... TN es un ordenamiento de las operaciones de las transacciones, sujeto a la siguiente restricción: Para cada transacción Ti que participa en P, sus operaciones deben aparecer en P en el mismo orden en que ocurren en Ti
En P, las operaciones de otras Tk pueden intercalarse en las de Ti
20
Administración de Bases de Datos
Planes de transacciones
Una planificación es una serie intercalada de acciones de distintas transacciones donde se respeta el orden relativo de la acción dentro de la transacción
Para el control de la concurrencia (y recuperación de fallos) nos centraremos en: Read R Write W CommitC Rollback B
Ejemplos Pa: R1(X); R2(X); W1(X); R1(Y); W2(X); C2; W1(Y); C1; Pb: R1(X); W1(X); R2(X); W2(X); C2; R1(Y); B1;
21
Administración de Bases de Datos
Planes de transacciones
Una planificación en serie es aquella donde no se solapan las transacciones. No se aprovecha la concurrencia y el resultado es poco eficiente.
Si se permite la intercalación de las operaciones de varias transacciones, existen muchos órdenes posibles
La teoría de la serialización, nos dirá cuáles son correctos y las técnicas de control de concurrencia que eviten planes incorrectos
Una planificación es serializable si produce un resultado equivalente a una planificación en serie de las mismas transacciones Si producen el mismo estado final en la BD Si las operaciones sobre cada dato afectado por los planes, se
aplican al mismo elemento en el mismo orden en ambos planes
22
Administración de Bases de Datos
Planes de transacciones
Dos operaciones de un plan P están en conflicto si
Pertenecen a diferentes transacciones, tienen acceso al mismo elemento X, y al menos una de ellas es write(X).
Operaciones en conflicto en Pa: R1(X); R2(X); W1(X); R1(Y); W2(X); C2; W1(Y); C1; R1(X); R2(X); W1(X); R1(Y); W2(X); C2; W1(Y); C1; R1(X); R2(X); W1(X); R1(Y); W2(X); C2; W1(Y); C1;
Operaciones NO en conflicto en Pa: R1(X); R2(X); W1(X); R1(Y); W2(X); C2; W1(Y); C1; R1(X); R2(X); W1(X); R1(Y); W2(X); C2; W1(Y); C1;
23
Administración de Bases de Datos
Planes de transacciones
Dos planes son equivalentes por conflictos si el orden de cualesquiera dos operaciones en conflicto es el mismo en ambos planes
Un plan P es serializable por conflictos si es equivalente por conflictos a algún plan en serie S El orden de las operaciones en conflicto en P coincide con el
orden en que se ejecutarían en algún plan en serie Podremos reordenar las operaciones de P que no estén en
conflicto, hasta obtener el plan en serie S equivalente a P
Pa: R1(X); W1(X); R1(Y); W1(Y); R2(X); W2(X); (plan en serie) Pb: R2(X); W2(X); R1(X); W1(X); R1(Y); W1(Y); (plan en serie) Pc: R1(X); R2(X); W1(X); R1(Y); W2(X); W1(Y); (plan no seriable) Pd: R1(X); W1(X); R2(X); W2(X); R1(Y); W1(Y); (plan seriable, a
Pa)
24
Administración de Bases de Datos
Planes de transacciones
Prueba de serialización por conflictos de un plan
Considerar sólo operaciones Read(X) y Write(X) Construir un grafo de precedencia dirigido y etiquetado
G={N,A}
N = {T1, T2, ..., TN} Crear un nodo por cada transacción Ti en P
A = {a1, a2, ..., aM} Conjunto de arcos dirigidos
Si una operación Ti aparece en el plan antes que alguna operación en conflicto de Tj, crear el arco de Ti a Tj
25
Administración de Bases de Datos
Planes de transacciones
Si hay un ciclo en el grafo, P no es serializable por conflictos Un ciclo es una secuencia de aristas:
C=((Ti -> Tj), (Tk -> Tl), ..., (Tm -> Ti))
Si no hay ciclos el plan es serializable Es posible crear un plan en serie S equivalente a P, mediante
una ordenación de las transacciones (Ti -> Tj) indica que Ti debe ir antes que Tj en un plan en serie
equivalente a P
T1 T2 T1 T2
T1 T2 T1 T2
Pa Pb
Pc Pd
x
xx
xx
26
Administración de Bases de Datos
Planes de transacciones
... pero al introducir continuamente transacciones en el sistema es muy difícil comprobar por anticipado la serialización de P: por ejemplo: cuándo comienza y termina un plan?
Para asegurar que las transacciones se “enreden” de forma serializable, el SGBD impone un conjunto de reglas (o protocolo) basado en la teoría de la serialización, tal que: si todas las transacciones las cumplen, o Si automáticamente, el subsistema de control de concurrencia
del SGBD las impone ... aseguran la serialización de todo el plan de transacciones
Tipos de protocolos Basados en reservas o bloqueos (locks) Basados en marcas de tiempo (time stamping)
27
Administración de Bases de Datos
Técnicas de control de la concurrencia
Protocolos basados en reservas o bloqueos (locks)
Protocolos basados en marcas de tiempo (time stamping)
Protocolos de concurrencia multiversión
Protocolos optimistas
28
Administración de Bases de Datos
Protocolos basados en bloqueos
Ya que los conflictos se producen cuando varias transacciones acceden concurrentemente a los mismos datos, una forma de asegurar la serialización es proporcionar protocolos de acceso a los datos mediante reservas, bloqueos o candados (locks)
Protocolo
Antes de acceder a un dato, se realiza una petición de reserva
Si la petición no puede ser atendida, la petición tendrá que esperar hasta que el dato se libere
29
Administración de Bases de Datos
Protocolos basados en bloqueos
El Gestor de bloqueos (subsistema del SGBD) gestiona y controla las reservas y candados
Un candado: Es una variable asociada a un elemento de información X Describe su estado respecto a las operaciones aplicables a X Sincroniza el acceso al elemento X por parte de transacciones
concurrentes
Tipos de candados: binarios (acceso exclusivo) ternarios (acceso exclusivo/compartido)
30
Administración de Bases de Datos
Bloqueos Binarios
Un candado binario tiene dos estados o valores posibles: Bloqueado (1) Desbloqueado (0)
Si lock(X)=1, ninguna transacción T que solicite X tendrá acceso a X
Si lock(X)=0, T podrá acceder a X cuando lo solicite
Proporciona exclusión mutua sobre X Las transacciones se esperan hasta que el acceso a X queda
liberado
Las transacciones deberán incluir las operaciones... LOCK(X), para solicitar el acceso al elemento X (bloquear) UNLOCK(X), para desbloquear el elemento X (desbloquear)
31
Administración de Bases de Datos
Bloqueos Binarios
Reglas del bloqueo binario
1. T debe reservar X usando LOCK(X), antes de realizar cualquier operación READ(X) o WRITE(X) en T
2. T debe desbloquear X usando UNLOCK(X), después de haber completado todas las operaciones READ(X) o WRITE(X) en T
3. T no reservará X si ya lo tiene bloqueado4. T no desbloqueará X a menos que lo tenga reservado
Sólo una transacción puede bloquear X Dos transacciones no pueden tener acceso concurrente al mismo
elemento (acceso exclusivo a X)
Método bastante restrictivo.
32
Administración de Bases de Datos
Bloqueo ternario
Un candado ternario tiene tres estados o valores posibles: Bloqueado para lectura Bloqueado para escritura Desbloqueado
Las transacciones deberán incluir las operaciones... RLOCK(X), bloquear para leer el elemento X (SHARED) WLOCK(X), bloquear para escribir el elemento X (EXCLUSIVE) UNLOCK(X), desbloquear el elemento X
Un elemento X bloqueado para: Lectura: tiene un candado compartido; otras Ts pueden leer X Escritura: tiene un candado exclusivo; T accede a X en
exclusiva
33
Administración de Bases de Datos
Bloqueo ternario
Reglas del bloqueo ternario
1. T debe reservar X usando RLOCK(X) o WLOCK(X) antes de realizar cualquier operación READ(X) en T
2. T debe reservar X usando WLOCK(X) antes de realizar cualquier operación WRITE(X) en T
3. T debe desbloquear X usando UNLOCK(X), después de haber completado todas las operaciones READ(X) o WRITE(X) en T
4. T no reservará X con RLOCK(X) si ya lo tiene bloqueado (*)5. T no reservará X con WLOCK(X) si ya lo tiene bloqueado (*)6. T no desbloqueará X a menos que lo tenga reservado
(*) esta regla puede permitir excepciones
34
Administración de Bases de Datos
Bloqueo ternario
Excepciones para las reglas 4 y 5 Promoción o degradación de reservas
Si T tiene X bloqueado para lectura, luego puede promover la reserva con WLOCK(X):
OK si T es la única que tiene X bloqueado para lectura, Si no, T debe esperar e intentarlo después ...
Si T tiene X bloqueado para escritura, luego puede degradar la reserva con RLOCK(X)
Así permite que otras transacciones lean X
35
Administración de Bases de Datos
Protocolos basados en bloqueos
T1 T2rlock(y) rlock(x)read(y) read(x)unlock(y) unlock(x)wlock(x) wlock(y)read(x) read(y)x = x + y y = x + ywrite(x) write(y)unlock(x) unlock(y)
Con valores iniciales:X=20, Y=30
T1, T2: X=50, Y=80T2, T1: X=70, Y=50
36
Administración de Bases de Datos
Protocolos basados en bloqueosT1 T2rlock(y) read(y) unlock(y)
rlock(x)read(x)unlock(x)wlock(y)read(y)y = x + ywrite(y)unlock(y)
wlock(x)read(x)x = x + ywrite(x)unlock(x)
Con valores iniciales:X=20, Y=30
el resultado esX=50, Y=50
No serializable!
37
Administración de Bases de Datos
Protocolo de Bloqueo de Dos Fases (2PL) El uso de reservas para la programación de transacciones
no garantiza la serialización de los planes
Es necesario seguir un protocolo adicional que indique dónde colocar las operaciones de bloqueo y desbloqueo de reservas dentro de las transacciones
El protocolo más conocido, que permite emitir de forma adecuada las operaciones de bloqueo y desbloqueo, es el Protocolo de Bloqueo de Dos Fases (2PL)
38
Administración de Bases de Datos
Protocolo de Bloqueo de Dos Fases (2PL)
Para garantizar la serialización en conflicto se añade una tercera regla al protocolo ya existente:
En toda transacción, todas las peticiones de reserva deben preceder a cualquier petición de liberación
Dentro de toda transacción se distinguen dos fases: Fase de expansión (o crecimiento)
T puede realizar (o promover) bloqueos T no puede liberar ningún bloqueo
Fase de contracción T puede liberar (degradar) bloqueos T no puede realizar ningún bloqueo
39
Administración de Bases de Datos
Protocolo de Bloqueo de Dos Fases (2PL)
T1 T2rlock(y) rlock(x)read(y) read(x)unlock(y) unlock(x)wlock(x) wlock(y)read(x) read(y)x = x + y y = x + ywrite(x) write(y)unlock(x) unlock(y)
No siguen el protocolo 2PLDespués de un unlock() hay un wlock()!
40
Administración de Bases de Datos
Protocolo de Bloqueo de Dos Fases (2PL)
T1’ T2’rlock(y) rlock(x)read(y) read(x)wlock(x) wlock(y) unlock(y) unlock(x)read(x) read(y)x = x + y y = x + ywrite(x) write(y)unlock(x) unlock(y)
Siguen el protocolo 2PL: serializable!
41
Administración de Bases de Datos
Protocolo de Bloqueo de Dos Fases (2PL)
Se puede demostrar que si toda transacción de un plan sigue el protocolo de dos fases, entonces el plan es serializable
Ya no es necesario comprobar la serialización de los planes. Al imponer las reglas del bloqueo, también se impone la
serialización
El 2PL puede limitar el grado de concurrencia en un plan Es el sobrecoste que requiere poder garantizar la serialización
de todos los planes sin tener que examinarlos
... pero emplear bloqueos puede provocar problemas de ... Bloqueo mortal (deadlock) Espera indefinida
42
Administración de Bases de Datos
Protocolo de Bloqueo de Dos Fases (2PL)
Bloqueo en dos fases conservador o estático T debe bloquear todos los elementos a los que tendrá acceso
antes de comenzar a ejecutarse Si no es posible bloquear algún elemento, T no bloqueará ninguno y
esperará para reintentarlo más tarde Protocolo libre de bloqueo mortal
Bloqueo en dos fases estricto (el más utilizado) T no libera ninguna reserva de escritura hasta terminar
Ninguna otra transacción lee o escribe un elemento modificado por T, salvo si T se ha completado: plan de transacciones estricto
No libre de bloqueo mortal (excepto si se combina con 2PL estático)
Bloqueo en dos fases riguroso (más restrictivo que 2PL estricto)
T no libera ninguna reserva hasta que termina
43
Administración de Bases de Datos
Bloqueo mortal
Todas las transacciones involucradas esperan que otra libere su reserva sobre cierto elemento de información
Protocolos de prevención Cada transacción reserva todos sus datos desde el principio
- Los datos están reservados durante más tiempo- Requiere conocer todos los datos que van a usarse al principio
Protocolos de detección Periódicamente, el sistema comprueba que no se han
producido bloqueos entre las transacciones
Factores de riesgo Número de datos, tamaño, duración de las transacciones,
grado de compartición de los datos, etc.
44
Administración de Bases de Datos
Bloqueos mortales
T1’ T2’rlock(y) .read(y) .. rlock(x). read(x)wlock(x) .
wlock(y)
Evitar los bloqueos mortales: técnicas de prevención Detectar los bloqueos mortales: técnicas de detección
a) T1’ espera hasta que X se libere
b) T2’ espera hasta que Y se libere
45
Administración de Bases de Datos
Bloqueo mortal
Protocolos de prevención Bloqueo por adelantado Bloqueo ordenado Uso de marcas de tiempo de transacción Protocolo de no esperar Protocolo de espera cautelosa Uso de tiempos predefinidos
Protocolos de detección Uso de grafos de espera
46
Administración de Bases de Datos
Protocolos de prevención
Bloqueo por adelantado Empleado por 2PL conservador Toda T debe bloquear por adelantado todos los
elementos que necesita de lectura y escritura Si no puede bloquearlos todos, espera y lo reintenta
después Concurrencia muy limitada!
Bloqueo ordenado Ordenar los elementos de la BD y asegurar que si T
necesita varios elementos, los bloqueará en ese orden
Concurrencia muy limitada! Poco Práctico: el programador debe conocer el orden
47
Administración de Bases de Datos
Protocolos de prevención
Si Tj está implicada en un posible bloqueo mortal: esperar abortar hacer que otra transacción aborte
Marca de tiempo de la transacción T(T): Identificador único de T Numeración ordenada de las transacciones La T más antigua tiene el T(T) menor La T más reciente tiene el T(T) mayor
Hay dos esquemas que usan time stamping y evitan deadlock
Si Ti intenta bloquear el elemento X, pero X ya está bloqueado por Tj con un candado en conflicto:
Esperar – Morir Herir – Esperar
48
Administración de Bases de Datos
Protocolos de prevención
Esperar – Morir
IF T(Ti) < T(Tj) THEN Ti espera
ELSETi aborta y después se reinicia con la misma marca de tiempo
Una Ti más antigua espera a que termine otra Tj más reciente Una Ti más reciente, que solicita un elemento bloqueado por
una Tj más antigua, es abortada y reiniciada
La transacción más vieja se espera a la más joven Se aborta la transacción más joven que puede provocar un
bloqueo mortal
49
Administración de Bases de Datos
Protocolos de prevención
Herir – Esperar
IF T(Ti) < T(Tj) THEN Tj aborta y después se reinicia con la misma marca de tiempo
ELSETj espera
Una Tj más reciente espera a que termine otra Ti más vieja Una Tj más reciente, que solicita un elemento bloqueado
por una Ti más antigua, es abortada y reiniciada
La transacción más vieja es espera a la más joven Se aborta la transacción más joven que puede provocar un
bloqueo mortal
50
Administración de Bases de Datos
Protocolos de prevención
Ambas técnicas basadas en time stamping impiden los posibles deadlocks
Ambas técnicas abortan y reinician transacciones que podrían provocar un bloqueo mortal ...... aunque tal cosa podría no ocurrir nunca!
51
Administración de Bases de Datos
Protocolos de prevención
Protocolo de no esperar Si T no puede realizar una reserva, es abortada y reiniciada
después T al abortar, no comprueba si realmente ocurrirá un bloqueo
mortal! Demasiados abortos y reinicios inncesarios!
Protocolo de espera cautelosa Para mejorar el protocolo de no esperar Si Ti intenta bloquear el elemento X, pero X ya está bloqueado por
Tj con un candado en conflicto: Si Tj no está esperando entonces Ti puede esperar, si no Ti aborta Protocolo libre de bloqueo mortal
Uso de tiempos predefinidos “timeouts” Si T espera un tiempo > tiempo predefinido
entonces el sistema supone que está en deadlock y aborta T Tampoco se comprueba que haya un deadlock efectivo
52
Administración de Bases de Datos
Protocolos de detección
Uso de un grafo de espera para detectar bloqueos mortales
Crear un nodo por cada transacción en ejecución, etiquetado con el identificador de la transacción
Si Ti está esperando para reservar un dato X, ya reservado por Tj, crear un arco dirigido y etiquetado desde Ti a Tj
Cuando Tj libera X, borrar la arista correspondiente
Si en algún momento existe un ciclo en el grafo de espera, entonces se ha detectado un bloqueo mortal entre las transacciones.
Se aborta la transacción que lleva realizadas menos escrituras
Ti Tj
x
53
Administración de Bases de Datos
Protocolos de detección
¿Cuándo detectar los ciclos? Cada un cierto tiempo fijo: detección periódica Cuando hay un cierto número de transacciones en
ejecución Cuando varias transacciones están esperando cierto
tiempo reservar
Selección de víctimas
No elegir transacciones que lleven mucho tiempo en ejecución hayan realizado muchas modificaciones
Elegir transacciones que participan en varios ciclos de bloqueos mortales
54
Administración de Bases de Datos
Inanición (starvation)
Una transacción no puede ejecutarse, mientras otras transacciones se procesan con normalidad
En un esquema de espera injusto: se da más prioridad a unas transacciones que a otras
Una transacción es seleccionada para ser abortada (victima) sucesivamente: nunca termina su ejecución
La solución es asignar prioridades más altas a las transacciones abortadas, para no ser siempre víctimas
Los esquemas Esperar-Morir y Herir-Esperar evitan la espera indefinida
55
Administración de Bases de Datos
Granularidad de los datos
Un dato puede ser: campo, registro, bloque, fichero, BD Granularidad: tamaño del elemento de información Para cada dato se tiene un candado distinto El tamaño del dato afecta al grado de concurrencia
Menor tamaño => Mayor grado de concurrencia Pero también:
Mayor número de elementos (y de candados) Mayor trabajo para el gestor de bloqueos y Mayor el tamaño ocupado en las estructuras de datos
asociadas ¿Cuál es el tamaño adecuado de reserva?
Si una T representativa accede a pocos registros Elegir granularidad de registros
SI T accede a muchos registros de una misma tabla Elegir granularidad de tabla
56
Administración de Bases de Datos
Protocolos basados en marcas de tiempo
Cada transacción Ti tiene asociada una marca de tiempo T(Ti) asignada por el sistema al empezar su ejecución
No tiene que ser necesariamente del tipo TIME
Si T1 llegó al SGBD antes que T2, T(T1) < T(T2)
Cada elemento X tiene dos marcas de tiempo: TSREAD(X): marca de tiempo de lectura más reciente TSWRITE(X): marca de tiempo de escritura más reciente
Al acceder una transacción Ti al dato X, se compara T(Ti) con TSREAD(X) y TSWRITE(X) para comprobar que la planificación en serie equivalente no es violada
57
Administración de Bases de Datos
Protocolos basados en marcas de tiempo
T realiza un WRITE(X)IF TSREAD(X)>T(T) ó TSWRITE(X) > T(T) THEN
ROLLBACK TELSE
WRITE(X)TSWRITE(X) = T(T)
T realiza un READ(X)IF TSWRITE(X)>T(T) THEN
ROLLBACK TELSE
READ(X)TSREAD(X) = max(T(T), TSREAD(X))
Una transacción más joven que T ha leído o escrito el valor de X antes que T haya podido escribirlo: violación de la ordenaciónUna transacción más joven que T ha escrito el valor de X antes que T haya podido leerlo: violación de la ordenación
58
Administración de Bases de Datos
Protocolos basados en marcas de tiempo
Planificación en serie equivalente: planificación en serie que resulta de ordenar las transacciones por su marca de tiempo
T(T1) < T(T2) < T(T3) Siempre que el algoritmo detecte dos operaciones
conflictivas que ocurran en orden incorrecto, rechazará la última de las dos operaciones abortando la transacción que la realizó
Dos operaciones están en conflicto si Pertenecen a diferentes transacciones, tienen acceso al mismo elemento X, y al menos una de ellas es WRITE(X).
De esta manera, este algoritmo garantiza que las transacciones son serializables en conflicto (al igual que 2PL)
59
Administración de Bases de Datos
Protocolos basados en marcas de tiempo
Ti quiere ... anteriormente otra acción detección transacción Tj más joven ...
READ(X) READ(X) CONTINUARWRITE(X) READ(X) ROLLBACK Ti TSREAD(X)>T(Ti)READ(X) WRITE(X) ROLLBACK Ti
TSWRITE(X)>T(Ti)WRITE(X) WRITE(X) IGNORAR*
TSWRITE(X)>T(Ti)
* Thomas write rule: rechaza menos operaciones de escritura
60
Administración de Bases de Datos
Protocolos de concurrencia multiversión
Protocolos de concurrencia multiversión mantienen varias versiones (antiguos valores) de un mismo dato
Cada operación WRITE(X) crea una nueva versión
Cuando una transacción requiere acceder a ese dato, el SGBD selecciona, siempre que sea posible, la versión adecuada para mantener la serialización
La idea es aceptar algunas operaciones de lectura proporcionando versiones antiguas del dato para evitar ser rechazadas
61
Administración de Bases de Datos
Protocolos basados en marcas de tiempo
Ti quiere ... anteriormente otra acción detección transacción Tj más joven ...
READ(X) READ(X) CONTINUARWRITE(X) READ(X) ROLLBACK Ti TSREAD(X)>T(Ti)READ(X) WRITE(X) ROLLBACK Ti
TSWRITE(X)>T(Ti)WRITE(X) WRITE(X) IGNORAR*
TSWRITE(X)>T(Ti)
* Thomas write rule: rechaza menos operaciones de escritura
62
Administración de Bases de Datos
Protocolos de concurrencia multiversión
Para almacenar versiones distintas de un mismo dato se requiere muchísimo más espacio
Sin embargo, de todos modos igual debemos guardar esas versiones (por ejemplo, para realizar recuperaciones)
El caso extremo son las BD temporales. Mantienen todos los cambios y los instantes en que ocurrieron
En estos casos no se requiere más espacio que el que ya se consume
63
Administración de Bases de Datos
Protocolos optimistas
Llamadas también técnicas de validación o certificación
No se realiza ninguna comprobación mientras se realiza la transacción
Las modificaciones no se realizan directamente sobre la BD: todas las modificaciones se realizan sobre copias locales
Las modificaciones no se realizan hasta el final de la transacción
La transacción finaliza correctamente, si no se viola la serialización. En caso contrario se aborta la transacción (sin modificar la BD!)
64
Administración de Bases de Datos
Protocolos optimistas
La transacción se ejecuta en tres fases:
Fase de lectura: una transacción puede leer valores y almacenarlos en variables locales. Las modificaciones se realizan sobre las variables locales
Fase de validación: se verifica la serialización de la transacción
Fase de escritura: si la transacción es serializable, se modifica la BD con los datos locales. En otro caso, rollback (la transacción no ha tenido repercusión)
65
Administración de Bases de Datos
Protocolos optimistas
Enfoque similar a la marca de tiempo, pero aquí ...
... la marca de tiempo es su validación. Por tanto, ...
... la planificación en serie equivalente es la que resulta de ordenar las transacciones en función del comienzo de la fase de validación
Se llama técnica optimista porque asume poca interferencia entre las transacciones
66
Administración de Bases de Datos
Comparación de técnicas de concurrencia
Espacio de almacenamiento
Reserva: se guarda un “estado” para cada dato (granularidad)
Marca de tiempo: marca por cada dato marca por cada transacción
Validación Marca de tiempo por cada transacción Write-set (conjunto de datos de escritura) por cada
transacción Read-set (conjunto de datos de lectura) por cada
transacción
67
Administración de Bases de Datos
Comparación de técnicas de concurrencia
Eficiencia
Reserva: Evita rollbacks incluso con un alto solapamiento entre
transacciónes
Marca de tiempo: Eficientes si las transacciones son de sólo lectura Eficientes si hay poco solapamiento entre transacciones
Validación Detecta la no serialización un poco más tarde que las otras
técnicas
68
Administración de Bases de Datos
Niveles de aislamiento de transacciones en SQL2
El nivel de aislamiento establece el grado de interferencia que una transacción tolera cuando se ejecuta concurrentemente con otras transacciones
El nivel de aislamiento debería ser el máximo (serializable, mínimo solapamiento), pero por cuestiones prácticas, pueden permitirse niveles de aislamiento inferiores, para permitir un mayor grado de concurrencia
Si alguna transacción se ejecuta a un nivel de aislamiento menor, no puede garantizarse la serialización.
SQL2 considera sólo tres formas donde esto pueda ocurrir: Lectura sucia, lectura no repetible y fantasmas
69
Administración de Bases de Datos
Actualización temporal (lectura sucia)
T1 T2
read(x)x = x - Nwrite(x). read(x). x = x + 1. write(x)read(y)... Fallo!
T2 ha leído un valor sucio temporal
El sistema restaura el
valor original de x
70
Administración de Bases de Datos
Problema de los “dirty reads”
Un dato se dice “sucio” si ha sido escrito por una transacción que todavía no ha sido confirmada
Una transacción Tj depende de una Ti, si Tj lee datos “sucios” escritos por Ti
Abortos en cadena “cascading rollbacks”: cuando una transacción Ti aborta, todas aquellas otras transacciones dependen de ella Tj, también se ven obligadas a abortar, y así sucesivamente otras dependiendes de Tj ...
71
Administración de Bases de Datos
Lectura irrepetible
T1 T2
. read(x)read(x) .x = x – N .write(x) .. read(x)
T2 recibe diferentes valores
para el mismo elemento
72
Administración de Bases de Datos
FantasmasT1 T3
. s = 0
. read(a)
. s = s + aread(x) .x = x – N .write(x) .. read(x). s = s + x. read(y). s = s + yread(y)y = y + Nwrite(y)
T3 lee x después de restar N y lee
y antes que N sea añadida: se
obtiene una suma errónea
73
Administración de Bases de Datos
Niveles de aislamiento de transacciones en SQL2
Serializable: la transacción se ejecuta cómo si fuese instantánea
Repetable read: la transacción sólo puede leer datos confirmados (y siempre són los mismos y tienen el mismo valor)
Read commited: la transacción sólo puede leer datos confirmados
Read uncommited: se pueden leer datos no confirmados
- aisl
amie
nto
+
+ co
ncur
renc
ia -
74
Administración de Bases de Datos
Niveles de aislamiento de transacciones en SQL2
Nivel de aislamiento dirty non-repetablephantom
Serializable Sí Sí SíRepetable read Sí Sí NoRead Commited Sí No NoRead uncommited No No No
Sí: el nivel de aislamiento previene el problema No: el nivel de aislamiento no previene el problema
Un SGBD que admita niveles distintos de serializable, debería proporcionar control explícito de la concurrencia (p.e. LOCK) para permitir a los usuarios definir transacciones válidas
75
Administración de Bases de Datos
Niveles de aislamiento de transacciones en SQL2
Inicio:
SET TRANSACTION <ModoAcceso> ISOLATION LEVEL <Nivel>
<ModoAcceso> ::= READ WRITE | READ ONLY<Nivel> ::= READ UNCOMMITTED | READ COMMITTED |
REPETABLE READ | SERIALIZABLE
Final:
COMMIT ROLLBACK
76
Administración de Bases de Datos
Acerca del control de la concurrencia en Oracle
Prioridades
Los datos deben ser leídos y modificados de manera consistente
La concurrencia de datos de un sistema multiusuario debe ser maximizada
Conseguir la máxima eficiencia
Mecanismos
Varios tipos de bloqueos
Consistencia multiversión
77
Administración de Bases de Datos
Acerca del control de la concurrencia en Oracle
Consistencia de lectura
Asegura que dentro de una transacción los datos de lectura son consistentes
Asegura que los lectores de datos de la BD no esperan a los escritores u otros lectores de los mismos datos
Asegura que los escritores de datos no esperan a los lectores de los mismos datos
Asegura que los escritores sólo esperan a otros escritores si éstos intentan modificar los mismos registros en transacciones concurrentes
78
Administración de Bases de Datos
Acerca del control de la concurrencia en Oracle
Segmentos de rollback
Cuando se actualizan datos, los valores originales (de los datos afectados por la modificación) son almacenados en segmentos de rollback
Mientras no se confirme la transacción de actualización, cualquier otra transacción que consulte esos datos verá los valores originales
Cuando se confirma la transacción, los cambios se hacen permanentes
79
Administración de Bases de Datos
Acerca del control de la concurrencia en Oracle
Transacciones de sólo lectura
Permite realizar múltiples consultas dentro de una misma transacción, garantizando la consistencia de los datos respecto al momento de creación de la transacción
Bloqueo implícito
Se permite realizar bloqueos exclusivos y compartidos a nivel de registros.
Bloqueo explícito
LOCK TABLE