Sistemas de Bases de Datos III Control Concurrencia

Es la actividad de coordinar accesos concurrentes a la base de datos por parte de los usuarios de una forma multiprogramada mientras se mantiene la imagen de que cada usuario esta utilizndola solo en un sistema. Asegura que transacciones mltiples sometidas por usuarios diferentes no interfieran unas con otras de forma que se produzcan resultados incorrectos. Un aspecto interesante del control de concurrencia es el manejo de interbloqueos; el sistema no debe permitir que dos o ms transacciones se bloqueen entre ellas.

El control de transacciones concurrentes en una base de datos brinda un eficiente desempeo del Sistema de Base de Datos, puesto que permite controlar la ejecucin de transacciones que operan en paralelo, accesando a informacin compartida y, por lo tanto, interfiriendo potencialmente unas con otras.

Ejemplos El hecho de reservar un asiento en una avin mediante un sistema

basado en aplicaciones web, cuando decenas de personas en el mundo pueden reservarlo tambin, nos da una idea de lo importante y crucial que es el control de concurrencia en un sistema de base de datos a mediana o gran escala.

En una Base de Datos bancaria podra ocurrir que se paguen dos

cheques en forma simultnea sobre una cuenta que no tiene saldo suficiente para cubrirlos en su totalidad, esto es posible evitarlo si se tiene un control de concurrencia.

El control de concurrencia trata con los problemas de aislamiento y consistencia del procesamiento de transacciones. El control de concurrencia distribuido de un DDBMS asegura que la consistencia de la base de datos se mantiene en un ambiente distribuido multiusuario. Si las transacciones son internamente consistentes, la manera ms simple de lograr este objetivo es ejecutar cada transaccin sola, una despus de otra. Sin embargo, esto puede afectar grandemente el desempeo de un DDBMS dado que el nivel de concurrencia se reduce al mnimo. El nivel de concurrencia, el nmero de transacciones activas, es probablemente el parmetro ms importante en sistemas distribuidos. Por lo tanto, los mecanismos de control de concurrencia buscan encontrar un balance entre el mantenimiento de la consistencia de la base de datos y el mantenimiento de un alto nivel de concurrencia.

Si no se hace un adecuado control de concurrencia, se pueden presentar dos anomalas. En primer lugar, se pueden perder actualizaciones provocando que

los efectos de algunas transacciones no se reflejen en la base de datos. En segundo trmino, pueden presentarse recuperaciones de informacin inconsistentes.

La mayora de las bases de datos se utilizan en entornos multi-usuario, en los que muchos clientes estn utilizando la misma aplicacin, o muchas aplicaciones cada una con uno o muchos clientes accediendo a la misma base de datos. Cada una de esas aplicaciones enviar consultas al gestor, y normalmente cada hilo de ejecucin ser una transaccin diferente.

Por ejemplo, si tenemos una estructura de tablas relacional que incluye las siguientes: PEDIDO(id, num-cliente, id-prod, cantidad, precio) PRODUCTO(id-prod, nombre, ..., stock)

Pueden ocurrir diferentes problemas relacionados con la escritura simultnea con otras escrituras o lecturas, incluyendo los siguientes: Dos sentencias UPDATE que actualicen un mismo producto decrementando el stock del mismo en una unidad podran terminar en que una de ellas no se realizase. Si pensamos en un UPDATE como una secuencia de una lectura y una escritura, puede que ambos UPDATE hagan la lectura, por ejemplo, de un stock de 10, y despus las escrituras, decrementan ese dato, quedando el resultado en 9, mientras que lo correcto era un resultado de 8. Supongamos una sentencia que primero comprueba que hay stock del producto P, y despus inserta un nuevo PEDIDO de diez unidades del producto P, que tiene un stock de 10, seguido de un UPDATE al stock por esa cantidad. Puede que otra insercin de un pedido se ejecute antes del UPDATE pero despus de la comprobacin, haciendo quedar el stock del producto en negativo.

Una forma de controlar la concurrencia es hacer que cada transaccin deba adquirir un derecho de acceso exclusivo a cada fragmento de datos que necesite modificar. A estos derechos se les denomina bloqueos. Las tcnicas ms empleadas para controlar el accesos concurrente de las transacciones se basan en el concepto de bloquear elementos de datos.

Bloqueos

Binarios Bloqueos de Lectura/Escritura Bloqueo en 2 fases

Se caracterizan por tener dos valores posibles; bloqueado y desbloqueado. Cada elemento de la base de datos tiene un bloqueo distinto. El bloqueo seala si una transaccin est operando sobre el elemento o est libre para que se pueda operar con l. De esta manera se impide que dos o ms transacciones estn operando sobre un mismo elemento al mismo tiempo. La implementacin de un bloqueo binario es simple:Nombre de elemento de Datos Booleano (Bloqueo) Referencia a la transaccin que lo bloquea

donde el booleano es en s el indicador del bloqueo.

Una transaccin T debe realizar una operacin Bloquear_tem(X) antes que un Leer_tem(X) o Escribir_tem(X). Una transaccin T debe realizar una operacin Desbloquear_tem(X) despus de que todos los Leer_tem(X) y Escribir_tem(X) en T se han completado. Una transaccin T no realizar un Bloquear_tem(X) si ya posee el bloqueo de X. Una transaccin T no realizar un Desbloquear_tem(X) salvo que posea el bloqueo de X.

EjemploTiempo 1 2 3 4 5 1 2 3 4 5 Transaccin T1 T1 T1 T1 T1 T2 T2 T2 T2 T2 Paso Bloquear PRODUCT Leer Pro_QOH PROD_QOH =35+100 Escribir PROD_QOH Desbloquear PRODUCT Bloquear PRODUCT Leer Pro_QOH PROD_QOH =135-30 Escribir PROD_QOH Bloquear PRODUCT 105 135 135 35 Valor Guardado

Son una ampliacin de los bloqueos binarios. El sistema de bloqueos binarios es simple pero demasiado restrictivo, ya que no permite que dos transacciones que van a leer el mismo fragmento de datos A lo hagan simultneamente, cuando en realidad, no puede haber problemas en varios lectores simultneos. Los bloqueos de lectura/escritura hacen ms dbil la restriccin permitiendo la siguiente compatibilidad de Bloqueos.

Matriz i aria C Lectura Escritura Lectura Compatible Incompatible

ati ili ad Escritura Incompatible Incompatible

Las operaciones que las transacciones deben realizar: Bloquear(g, M): indica

al planificador el comienzo de una operacin o conjunto de ellas de modo definido por M sobre el grnulo g. al planificador el final de las operaciones realizadas por la transaccin correspondiente

Desbloquear(g): indica

Una transaccin T debe emitir la operacin bloquear_lectura(x) o bloquear_escritura(X) antes de que se realice cualquier operacin leer_elemento(X) de T. Una transaccin T debe emitir la operacin bloquear_escritura(X) antes de que realice cualquier operacin escribir_elemento(X) de T. Una transaccin T debe emitir la operacin desbloquear(X) una vez que se hayan completado todas las operaciones leer_elemento(X) y escribir_elemento(X) de T. Una transaccin T no emitir una operacin bloquear_lectura(X) si ya posee un bloqueo de lectura (compartido) o de escritura (exclusivo) para el elemento X. Una transaccin T no emitir una operacin bloquear_escritura(X) si ya posee un bloqueo de lectura (compartido) o de escritura (exclusivo) para el elemento X. Una transaccin T no emitir una operacin desbloquear(X) a menos que ya posea algn tipo de bloqueo sobre el elemento X.

Seriali acin de los bloqueos de lectura/escritura

La serializacin de las operaciones de lectura y escritura consiste en ordenar las operaciones para un conjunto de transacciones concurrentes de modo que los resultados de las operaciones sean correctos.

Por ejemplo, si tenemos las si uientes transacciones si uiente situaci n:

e Y, puede darse la

En s sit i n, l j i n Y l t ri inal s l s aya incr ntado na z, cuando t na ue aberse incrementado dos eces. in embar o, si ubi semos tenido suerte y todas las operaciones de se ubiesen realizado antes ue las de Y, el resultado abra sido correcto.

Se llama transaccin en dos fases aquella que no realiza ningn bloqueo despus de haber realizado alguna operacin de desbloquear.

Fase de expansin ( o de crecimiento), durante la cual se pueden adquirir nuevos bloqueos sobre elementos pero no se puede liberar ninguno. Fase de contraccin, durante la cual se pueden liberar todos los bloqueos existentes pero no se pueden adquirir nuevos bloqueos Su principal ventaja es que garantiza la seriabilidad, lo que no se consigue usando simplemente bloqueos.

Ejemplo

de operacin en 2 fases:

Cualquier planificacin que puede suceder es serializable.

El protocolo en dos fases limita la concurrencia pero garantiza que los planes sean serializables.

B2F bsico: va tomando bloqueos y luego los va liberando. B2F conservador: toma todos los bloqueos al principio y sino hay bloqueo, se espera (poco prctico). B2F estricto: no libera ningn bloqueo exclusivo hasta despus de confirmar o abortar. (asegura planificaciones estrictas) B2F riguroso: no libera ningn bloqueo hasta despus de confirmar o abortar

Utilizacin de algoritmos de Cerradura en bloqueo en 2 fasesEn los candados de dos fases una transaccin le pone un candado a un objeto antes de usarlo. Cuando un objeto es bloqueado con un candado por otra transaccin, la transaccin solicitante debe esperar. Cuando una transaccin libera un candado, ya no puede solicitar ms candados. En la primera fase solicita y adquiere todos los candados sobre los elementos que va a utilizar y en la segunda fase libera los candados obtenidos uno por uno. La importancia de los candados de dos fases es que se ha demostrado de manera terica que todos las calendarizaciones generadas por algoritmos de control de concurrencia que obedecen a los candados de dos fases son serializables

El mero mecanismo de los bloqueos garantiza el acceso exclusivo a un dato o fragmento de informacin (evitando ciertos problemas), pero los problemas asociados a la intercalacin de las operaciones compuestas an pueden darse. Por lo tanto, hace falta alguna poltica o mecanismo de adquisicin y liberacin de bloqueos que permita hacer las operaciones serializables. Aun cuando los bloqueos en 2 fases intentan permitir el uso de operaciones serializables estas traen consigo algunos inconvenientes tales como:

Bloquea los elementos que podran ser desbloqueados tras su uso ocupados hasta la segunda fase, impidiendo que otras transacciones que los necesiten los utilicen. Esto hace que el rendimiento de este protocolo se degrade conforme aumenta el grado de concurrencia. No permite todos los planes serializables posibles. La implementacin de este este bloqueo depende del programador, que puede no realizar su tarea convenientemente.

Un enfoque para garantizar la seriabilidad de los planes supone usar marcas de tiempo para ordenar la ejecucin de estas.

Las marcas de tiempo se asignan en el orden en que las transacciones se introducen en el sistema. Generacin de marcas de tiempo: Contador Reloj del sistema La marca de tiempo de grnulo es un valor numrico asociado con un grnulo que almacena la marca de tiempo de la ltima transaccin que oper sobre el grnulo

Marcas de tiempo por ordenacin Total Marca de tiempo por ordenacin Parcial Regla de escritura de Thomas

Se basa en asegurar que el acceso a los grnulos por las transacciones se realiza en el orden asignado inicialmente(que es el orden de inicio de las transacciones). Si esto no se cumple: se debe abortar una transaccin (la que produjo el conflicto) se revierte la transaccin y se relanza asignndole otra marca tiempo

Se intenta ordenar aquellas operaciones que son conflictivas (y que no son permutables). Se definen dos marcas de tiempo para un grnulo: Marca de tiempo de lectura ( MT_lec(g) ): corresponde a la mayor

(la ms alta) marca de tiempo de las transacciones que han ledo el granulo. Marca de tiempo de escritura ( MT_esc(g) ): corresponde a la mayor (la ms alta) marca de tiempo de las transacciones que han escrito en el granulo.

Este algoritmo comprueba si las operaciones en conflicto respetan el orden asignado a las transacciones. Se realizan comprobaciones diferentes para las operaciones de lectura y escritura

Es posible ue se produzca un reinicio cclico de al una de las transacciones (espera indefinida).

in embar o existen planificaciones serializables ue no se pueden ejecutar con este al oritmo.

odas las planificaciones ue este al oritmo permite ejecutar son serializables (por conflictos).

Este al oritmo detecta operaciones en conflicto ue ocurren en orden incorrecto y aborta la ms reciente(mayor marca de tiempo).

Ventajas: Al ser un mtodo semioptimista, da mejor rendimiento cuando la interaccin entre las transacciones es reducida. Con este mtodo no se puede producir interbloqueo. Inconvenientes: Una transaccin puede verse sometida a un reinicio cclico. Si existe mucha interaccin, puede ser muy costoso, al tener que deshacer muchas veces. Se puede producir una restauracin en cascada: Al deshacer una transaccin T1, cualquier transaccin T2 que haya utilizado un valor escrito por T1 habr de deshacerse tambin, y as sucesivamente.

Constituye una mejora del algoritmo anterior en la escritura. Si una transaccin pretende escribir en un grnulo con una MT_esc > MT de la transaccin, se puede ignorar dicha escritura (siempre que ninguna transaccin con marca posterior haya ledo el granulo).

Este algoritmo consiste en ir guardando varias versiones del mismo dato (grnulo) : se conservan los valores antiguos de los grnulos que se han actualizado. Lectura: Cuando una Transaccin necesita leer algn

grnulo, se elige una versin adecuada para mantener la seriabilidad de la planificacin, si es posible. escribe una nueva versin de ese grnulo, conservndose adems la versin anterior.

Escritura: Cuando una Transaccin escribe un grnulo,

Protocolo de ordenacin por marcas de tiempo multiversin Protocolo de bloqueo en dos fases multiversin

Para cada elemento , el sistema uarda arias ersiones, , ,..., , teniendo para cada ersi n una marca_lectura(Xi), y una marca_escritura(Xi)

Si la transaccin T emite una operacin escribir_elemento(X), tomamos versin de X, llammosla Xi, con mayor mar a_l t ra( ). Si st valor s mayor q la mar a d tiempo de T, abortamos y deshacemos la transaccin. Caso contrario, se crea una nueva versin de X y se asigna la etiqueta de tiempo de T a sus valores mar a_l t ra( ) y mar a_es rit ra( ). Si la transaccin T emite una operacin leer_elemento(X), se busca la versin Xi que tenga su mar a_es rit ra( i) mayor posible pero si sobrepasar la mar a de tiempo de T. Se utiliza este elemento y despus asignamos a mar a_lect ra( i) el mayor valor entre lamarca de tiempo de T y el valor que tuviera antes.

Ventaja: No hay operacin de lectura rechazada, que provoque un reinicio de la transaccin. Desventajas: El mantener varias versiones de un elemento puede llegar a resultar costoso. En el caso peor, la base de datos puede degenerar en una base de datos temporal, que sigue la pista a todos los cambios y los momentos en los que ocurrieron.

En este mtodo, abortar una transaccin puede provocar una restauracin en cascada, ya comentada antes.

Es una ampliacin del bloqueo en dos fases. En esta versin se tienen tres tipos de bloqueo: los dos anteriores, de escritura y lectura, y uno ms, llamado de certificacin. Al contrario que en el bloqueo en dos fases simple, un bloqueo de escritura no impide que otras transacciones bloqueen otros elementos para lectura. Lo que se hace, en caso de que transaccin bloquee un elemento para lectura, para poder conseguir esto es crear una nueva versin de X, llammosla X', en la que la transaccin bloqueante podr realizar cuantos cambios quiera, mientras las dems transacciones seguirn viendo el valor anterior de X para lectura. Es importante sealar, que si bien con este mtodo se pueden realizar una lectura y una escritura simultneas, sigue sin poder realizarse dos escrituras al mismo tiempo. Cuando una transaccin que haya bloqueado un elemento para escritura est lista para confirmarse, debe obtener el bloqueo de certificacin de X. Ahora s, el bloqueo de certificacin es exclusivo respecto a los otros dos. Una vez lo obtiene, el valor de X pasa a ser el de X', con lo que a partir de ese momento es visible para todas las transacciones.

Ventajas y desventajas: La novedad de este mtodo con respecto al bloqueo en dos fases ya visto es que permite la lectura a mismo tiempo que la escritura. Sin embargo, una transaccin deber esperar a confirmarse hasta tener los bloqueos de certificacin de todos los elementos que ha modificado.

Este esquema evita el aborto en cascada, ya que siempre se leen versiones confirmadas de X. Sin embargo, si permitimos que un bloqueo se convierta en un bloqueo de escritura, tal como ya vimos anteriormente para la versin simple de este bloqueo, se puede producir un interbloqueo.

Un algoritmo optimista asume ciertas condiciones que Simplifican el desarrollo de una tarea. Por ejemplo, un esquema de control de concurrencia optimista, en su primera etapa, puede asumir que una Transaccin no tendr conflictos con otras transacciones concurrentes. En ese caso, las escrituras se hacen sin restriccin ya que no Deben verificarse la inexistencia de conflictos. En un segunda etapa del algoritmo, se realiza una validacin Para chequear si las condiciones asumidas fueron ciertas. De no ser ciertas, la transaccin debe ser retrocedida y ejecutada Nuevamente.

Este algoritmo tiene tres fases: Fase

de lectura: leo las valores de los grnulos en la BD pero no modifica ningn grnulo (copias locales).

Fase

de validacin: se efecta una verificacin para comprobar si hay algn problema con las operaciones realizadas. de escritura: si la fase anterior termina con xito se actualiza la BD.

Fase

Se comprueba si existe algn grnulo que haya sido ledo por la transaccin a certificar y escrito por otra transaccin certificada despus del comienzo de la transaccin que estamos certificando

En MySQL, tanto las solicitudes de bloqueos como las liberaciones se realizan mediante una sola llamada del API de los gestores de almacenamiento:

store_lock(THD *thd, THR_LOCK_DATA **to, enum thr_lock_type lock_type)Cada llamada a utiliza el manejador de una tabla concreta, y se indica la informacin de los datos a bloquear mediante la variable , y el tipo de bloqueo mediante (el nmero de tipos definidos en MySQL es muy grande, ya que cubre todos los tipos de bloqueo que implementan los mltiples gestores de almacenamiento disponibles). Adems en MySQL hay gestores de almacenamiento que ofrecen bloqueo a nivel de fila, y otros bloqueos a nivel de tabla. No obstante lo anterior, hay sentencias que siempre producirn un bloqueo de tabla, como por ejemplo una sentencia ALTER TABLE.