Concurrencia en Bases de Datos (I)

Concurrencia en Bases de Datos

CI-5313 Arquitectura y Administración de Bases de Datos

2

Concurrencia

Transacción

HistoriaConflicto

Serializable..Serial

OperacionesReadWrite

CommitRollback


3

Transacciones

Transacción 1 Transacción 2

update cuenta set saldo = saldo – 100 where cid=1

Select sum(saldo) from cuenta

update cuenta set saldo = saldo + 60 where cid=2

update cuenta set saldo = saldo + 60 where cid=2


4

Transacción

Unidad Lógica de procesamiento de bases de datos que incluye una o más operaciones de acceso (Read y Write)

Un programa de aplicación puede contener varias transacciones

begin

end


5

Procesamiento de transacciones

Sistema mono-usuario.

Sistema multi-usuario:Muchos usuarios pueden acceder de forma concurrente

ConcurrenciaProcesamiento intercalado:

Un solo CPUProcesamiento paralelo. Varios CPU

tiempo


6

Propiedades deseables de transacciones

AtomicidadTodas las actualizaciones se hacen o ninguna

ConsistenciaSatisface como un todo restricciones de integridad

Aislamiento (Isolation)Pareciera que las transacciones se ejecutan en serie

DurabilidadSi la transacción se compromete (commit), las actualizaciones no se perderán si hay fallas.


7

Operaciones de una transacción

ReadSe busca el bloque en disco y se transfiere a memoria - si no está ya allí

WriteSe lleva el bloque de memoria a disco – inmediatamente o posteriormente

begin

end


8

Operaciones de una transacción

CommitSeñala terminación exitosa. Las actualizaciones pueden ser comprometidas a la Base de Datos y no serán deshechas

RollbackLa transacción se aborta, se deshacen las actualizaciones y la Base de Datos retorna a su estado anterior

begin

end


9

Problemas de procesamiento intercalado

ACID no se satisface

Unrepeatable Read: T2 lee antes de que T1 añada N dando una suma incorrecta


sum:=0read(A)sum:=sum+A

read(X)X:=X-NWrite(X)

read(X)sum:=sum+Xread(Y)sum:=sum+Y

Read(Y)Y:=Y+NWrite(Y)

tiempo


10




Read(X)X:=X-N

read(X)X:=X+M

write(X)read(Y)

write(X)

y:=y+Mwrite(Y)

Lost Update: Las operaciones están intercaladas de tal manera que write(X) realizada por T1 se pierde

tiempo


11



Dirty Read: T1 falla y debe hacer ROLLBACK. T2 ha leido un valor “sucio” de T1


Read(X)X:=X-NWrite(X)

read(X)X:=X+MWrite(X)

read(Y)

falla

tiempo


12



Conflicto write-readDirty Read. Una transacción lee valor de un dato escrito por otra transacción que no ha hecho COMMIT

Conflicto read-writeUnrepeatable Read. Una transacción lee valor de un dato varias veces. Entre las lecturas, otra transacción la escribe

Conflicto write-writeLost Update. Dos transacciones actualizan el valor de un mismo dato. Una actualziación sobreescribe la otra

tiempo


13

Procesamiento intercalado transacciones – Historia (Schedule)

El orden de ejecución de las operaciones de varias transacciones conforma una Historia de Ejecución.

Una Historia S de T1 …, TnEs un ordenamiento de las operaciones de las transacciones, en donde para cada transacción Ti se debe mantener el orden de las operaciones de la transacción

EjemplosSa: r1(X);r2(X);w1(X);r1(Y);w2(X);w1(Y)Sb: r1(X);w1(X);r2(X);w2(X);r1(Y);a1

Transacciones


14


Conflicto

Par de operaciones en conflicto• Operaciones de dos transacciones

diferentes T1 y T2

• Sobre el mismo elemento de datos• Al menos una operación es write

r1(x), w2(x)w1(x), r2(x)w1(x), w2(x)

Transacciones


15


Serial…Serializable

Historia Serial:Si para cada transacción que participa en la Historia, todas las operaciones son ejecutadas consecutivamenteSi no se cumple es no serial.

Historia Serializable:Si es equivalente a alguna ejecución serial de las mismas transacciones

Transacciones


16

Procesamiento intercalado Transacciones – Historia (Schedule)

Serial

tiempo


read(A)A:=A+100write(A)

read(B)B:=B+100write(B)

read(A)A=A*2write(A)

read(B)B=B*2write(B)


17


Serializable

tiempo


read(A)A:=A+100write(A)


read(B)B:=B+100write(B)



18


No Serializable

tiempo


read(A)A:=A+100write(A)read(B)



B:=B+100write(B)

Lost Update: Las operaciones están intercaladas de tal manera que write(B) realizada por T2 se pierde


19


Equivalencia

tiempo

tiempo

Equivalentes?

Dos historias son Equivalentes por Conflicto si el orden de dos operaciones conflictivas es el mismo en ambas historias.

Una Historia es Serializable por Conflicto si es Equivalente por Conflcto a una Historia Serial.

El rol del DBMS es asegurar que las historias sean serializables


20


Chequeo Serializable por ConflictoGrafo de precedencia de la Historia

Un nodo por cada transacción Ti

Un arco de Ti a Tj si hay una operación conflictiva de las transacciones, y la operación de Ti precede a la de Tj

Si el grafo es acíclico, la Historia es Serializable por Conflicto


21


Chequeo Serializable por ConflictoGrafo de precedencia de la Historia

Un nodo por cada transacción Ti

Un arco de Ti a Tj si hay una operación conflictiva de las transacciones, y la operación de Ti precede a la de Tj

Si el grafo tiene un ciclo, la Historia es

No Serializable por Conflicto


22

ConcurrenciaOtros conceptos por desarrollar

Historias Recuperable

Cascadeless

Estricta

Control de Concurrencia Locks

Timestamps

23Departamento de Computación y Tecnología de la InformaciónProfesora Edna Ruckhaus

Concurrencia en Bases de Datos

Documents

Concurrencia en Bases de Datos (I)