CONTROL DE CONCURRENCIA - Bases de Datos Distribuidas 2013

CONCURRENCIA
•El nivel de concurrencia (número de transacciones
concurrentes) es probablemente uno de los parámetros mas
importantes en los sistemas distribuidos.
•El mecanismo de control de concurrencia busca encontrar
un equilibrio entre el mantenimiento de la consistencia de las
base de datos y el mantenimiento del alto nivel de
concurrencia.
CONCEPTOS BÁSICOS
• Historia (también llamada “Schedule”): esta definida por
un conjunto de transacciones (T = {T1,T2,..Tn}) y la
especificación del orden intercalado de la ejecución de sus
operaciones.
• Historia Serial : Una historia H se dice que es serial si las
operaciones de varias transacciones no están intercaladas.
• Historias Serializables: Una historia H se dice que es
serializable si y solo si es equivalente a una historia serial
MECANISMOS DE CONTROL DE CONCURRENCIA
Clasificación:
• De acuerdo a la topología de red requerida.
• De acuerdo a la replicación requerida.
• Por sincronización:
► Bloqueo(locking)
► Protocolo-Conjunto de reglas (protocols)
• Pesimista u Optimista.
MECANISMO DE CONTROL DE CONCURRENCIA
ALGORITMOS PESIMISTAS
Los pesimistas “ven que muchas transacciones terminaran
en conflicto entre ellas”
Los algoritmos pesimistas validan antes del ciclo de vida
ALGORITMOS OPTIMISTAS
Los optimistas “NO ven que muchas transacciones
terminaran en conflicto entre ellas”
• Los algoritmos optimistas retrasan la validación hasta antes de la fase de escritura
• Cada transacción mantiene una copia de datos
• La fase de validación comprueba si la base de datos puede quedar inconsistente
CONTROL POR BLOQUEO (LOCKING-BASED)
• Se puede acceder a un dato (unit lock) si y solo si se
tiene el lock correspondiente
• Una unidad de bloqueo no puede ser accedida por una
operación si esta ya ha sido previamente bloqueada por
otra
• El Bloqueo (“lock”) es seteado (puesto) por una
transacción antes de que esta se acceda y liberado al
final de la misma.
CONTROL POR BLOQUEO (LOCKING-BASED)
Clasificación de bloqueo(lock)
• Read Lock (RL)
• Write Lock(WL)
Compatibilidad entre modos de bloqueo.
CONTROL POR BLOQUEO (LOCKING-BASED)
Lock manager (LM):
• Maneja los locks para cada
operación
• Ofrece transparencia para el
usuario
CONTROL POR BLOQUEO (LOCKING-BASED)
PROBLEMA:
SOLUCIÓN:
• PERDIDA DE INSOLACIÓN
BLOQUEO DE 2 FASES
• PERDIDA DE ATOMICIDAD
BLOQUEO 2 FASES (TWO-PHASE LOCKING-2PL)
REGLA:
► Establece que ninguna transacción debe solicitar un bloqueo(LOCK) después de
liberar uno de sus bloqueos.
(O ALTERNATIVAMENTE)
► Una transacción no debe liberar un lock hasta que este segura de que no
necesitara otro.
• Las transacciones se ejecutan en dos fases: “growing phase” y
“shrinking phase”
• Se ha demostrado que cualquier historia generada por un algoritmo
de control de concurrencia que obedece la regla 2PL es
serializable
MANERAS DE “LIBERACIÓN”- 2PL LOCK
MANERAS DE “LIBERACIÓN”- STRICK 2PL LOCK
EJEMPLO
2PL CENTRALIZADO – C2PL
Delega la responsabilidad del lock manager a un solo sitio
2PL DISTRIBUIDO – D2PL
Se basa en la idea de que cada sitio tiene un lock manager
disponible
TIMESTAMP
• Trata de establecer un orden para la ejecución de
transacciones.
• El Transaction Manager (TM) asigna a cada transacción
un único Timestamp. (TS (Ti))
• No necesariamente el Timestamp es tiempo (p.e puede
ser un contador)
• El Timestamp debe ser incremental.
TIMESTAMP-REGLAS
Regla timestamp ordering (TO):
► Sean 01 y O2 operaciones conflictivas que pertenecen a
transacciones T1 y T2 respectivamente, 01 se ejecutara antes si y
solo sí TS(T1) < TS(T2)
-T1 es “la transacción vieja” y T2 es “la transacción joven”
• En caso de que llega otra operación conflictiva con las previamente
ordenadas
► Si TS( Operación nueva) < TS(operación programada)
Se aborta y se reinicia con un nuevo timestamp
► Si TS(operación programada) < TS(operación nueva)
Se agrega la nueva operación
TIMESTAMP-PROBLEMA
La comparación entre los timestamps de las
transacciones sólo se pueden realizar si el scheduler
ha recibido todas las operaciones.
Solución:
Cada dato en la BBDD tiene 2 timestamps:
►
READ TIMESTAMP RTS(X)
►
WRITE TIMESTAMP WTS(X)
ALGORITMO BÁSICO TO (BASIC TO)
1.El coordinating transaction manager” asigna un timestamp a la
transacción
2.Se determinan los sitios donde están los datos y se manda la
operación correspondiente al scheduler de ese sitio
3.El scheduler del sitio ejecutara
Si la operación se
rechaza la transacciones
se reinicia con un
timestamp nuevo
ALGORITMO BÁSICO TO (BASIC TO)-PROBLEMAS
•¿Qué sucede si en el Data Proccesor de un sitio
determinado hay una operación pendiente y el
scheduler manda otro ?
► El
método timestamp no usa locks , es probable que la
base quede inconsistente.
El scheduler espera la respuesta del Data proccesor para
mandarle otra operación (puede ser implementado con una
cola)
►
•El protocolo timestamp nunca genera deadlock.
CONSERVATIVE TO
• El algoritmo conservative trata de reducir la sobrecarga
del sistema al minimizar el número de reinicios de las
transacciones.
• Trata de retrasar las operaciones hasta que se pueda
establecer un orden y haya altas posibilidades de
ejecutar la transacción.
• Cada scheduler mantiene una cola para cada
Transaction manager que haya.
• Alguna de las implementación pueden ocasionar
deadlock.
MULTIVERSION TO
• El multiversion TO también desea reducir el ”restart” de
las transacciones.
• La mayoría de los trabajos de multiversión TO se han
focalizado en bases de datos centralizadas.
• En multiversión TO , los cambios no modifican la base de
datos , sino que cada operación de escritura crea una
nueva versión de ese dato.
• Cada versión está marcada por un timestamp de la
transacción que la crea.
DEADLOCK
• Ocurre DEADLOCK si dos
transacciones se están
esperando mutuamente.
• Una buena técnica para detectar
deadlock es armando un grafo
wait-for graph (WFG).
• Para aplicarlo en base de datos
distribuidas se debe hacer un
WFG global.
DEADLOCK
• Ocurre DEADLOCK si dos
transacciones se están
esperando mutuamente.
• Una buena técnica para detectar
deadlock es armando un grafo
wait-for graph (WFG).
• Para aplicarlo en base de datos
distribuidas se debe hacer un
WFG global.
DEADLOCK MÉTODOS
• DEADLOCK PREVENTION
El Transaction manager comprueba la transacción cuando se inicia y no le
permite proceder si puede producirse un deadlock.
► Se requiere que todos los datos que serán accedidos por una transacción
sean pre declarados.
► No son muy adecuados para los entornos de bases de datos.
►
• DEADLOCK AVOIDANCE
► Emplea
técnicas de control de concurrencia que no dan lugar a
deadlocks.
Ej Tecnicas:Las unidades de bloqueo(unit locks) son ordenadas y las transacciones
siempre solicitan bloqueos en ese orden(GLOBAL o LOCAL).
► Si
las técnicas fallan se resuelve el deadlock en forma temprana para que
no se produzca.
Ej Tecnica falla: Uso de Timestamp con prioridades.
DEADLOCK MÉTODOS
• DEADLOCK DETECTION AND RESOLUTION
►
Es el método más popular y mejor estudiado.
►
La detección se realiza mediante el estudio del GWFG para la formación
de ciclos.
►
La resolución de deadlocks se realiza normalmente por la selección de
una o más transacciones víctima (s) que será anulada y abortada con el
fin de romper los ciclos en el GWFG.
1)El esfuerzo invertido en la transacción.
2)El costo de aborto.
3)La cantidad de esfuerzo para terminarlo.
4)La cantidad de ciclos en que esta la transacción.
DEADLOCK MÉTODOS
Hay tres métodos fundamentales
• Centralized Deadlock Detection,
• Distributed Deadlock Detection.
• Hierarchical deadlock detection.
DETECCION CENTRALIZADA DE DEADLOCK
(CENTRALIZED DEADLOCK DETECTION)
• Un sitio se designa como el detector de deadlocks de
todo el sistema.
• Periódicamente, cada lockmanager transmite su LWFG a
el detector de deadlock , quien entonces forma el GWFG
DETECCIÓN JERÁRQUICA DE DEADLOCK
(HIERARCHICAL DEADLOCK DETECTION)
• Construcción de una jerarquía de detectores de deadlocks.
• Cada detector de deadlocks envía su LWFG al del siguiente nivel.
DETECCION DISTRIBUIDA DE DEADLOCK
(DISTRIBUTED DEADLOCK DETECTION)
• Los algoritmos de detección de deadlocks distribuido delegan la
responsabilidad de detectar deadlocks a sitios individuales.
• Si hay un ciclo que :
►
Incluye los bordes externos  se maneja a nivel local
►
No incluye hay un deadlock distribuido y debe ser comunicado
CONCLUSIÓN
• El control de concurrencia trata con los problemas de
aislamiento y consistencia del procesamiento de
transacciones.Buscando la atomicidad.
• El control de concurrencia distribuido de una DDBMS asegura
que la consistencia de la base de datos se mantiene en un
ambiente multiusuario
• El control de concurrencia en las base de datos es de suprema
importancia ya que evita errores en el momento de ejecutar
las diferentes transacciones
BIBLIOGRAFIA
• Principles of Distributed Database Systems Third Edition
(M. Tamer Özsu Patrick Valduriez)
• Grimpi IT blog
(http://grimpidev.wordpress.com/2011/02/08/control-de-concurrencia-multiversionmvcc/)

Download Report