Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

4.2 Control de concurrencia Base de datos distribuida

Control de concurrencia y algoritmos de control de concurrencia
by

Hendrixs Money

on 13 November 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of 4.2 Control de concurrencia Base de datos distribuida

Algoritmos basados
en estampas de tiempo El grupo de algoritmos pesimistas consiste de
Algoritmos basados en candados
Algoritmos basados en ordenamiento por estampas de tiempo
Algoritmos híbridos. Base de datos distribuidas 4.2 Control de concurrencias Algoritmos de
control de concurrencia Algoritmo
Basado en Bloqueos Control de concurrencia Serialización de transacciones El criterio de clasificación más común de los algoritmos de control de concurrencia es el tipo de primitiva de sincronización Es la actividad de coordinar accesos concurrentes a la base de datos, es decir, es la forma en que el DBMS maneja las ejecuciones paralelas en la BD. Si se intercalan las operaciones de dos transacciones que contengan lecturas y escrituras sobre el mismo elemento de datos, es posible que la base de datos quede en un estado inconsistente. En cambio esto no ocurriría si una transacción se ejecutase después que la otra de forma secuencial, sin ningún grado de paralelismo. En este caso diríamos que las transacciones se ejecutan en serie. Control de concurrencias Algoritmos Para esto existen dos formas básicas: Autónoma: Copia Primaria: Una transacción sobre un elemento con n replicas requiere n mensajes
Petición del recurso
Aprobación de la petición
Mensaje de la transacción
Reconocimientos de transacción exitosa
Peticiones de liberación de recursos Una transacción sobre un elemento con n copias requiere n mensajes
Una petición del recurso
Una aprobación de la petición
n mensajes de la transacción
n reconocimientos de transacción exitosa
Una petición de liberación de recurso Basados en bloqueo Bloqueo de dos fases (2PL) En el caso de las BD distribuidas usar bloqueo de recursos, peticiones para probar, establecer o liberar bloqueos requiere mensajes entre los manejadores de transacciones y el calendarizador. Se dividen en: Un bloqueo en general es cuando una acción que debe ser realizada está esperando a un evento. Esto se debe a varios factores : 1.El manejador de la BDD es responsable de localizar y actualizar el dato duplicado.

2.Si un nodo falla mientras se realiza una actualización, el manejador debe asegurarse de que los efectos se reflejen una vez el nodo se recupere del fallo.

3.La sincronización de transacciones en sitios o nodos múltiples es difícil; los nodos no pueden obtener información inmediata de las acciones realizadas en otros nodos concurrentemente. El algoritmo 2PL utiliza bloqueos de lectura y escritura para prevenir conflictos entre operaciones. Consiste en los siguientes pasos para una transacción T: Ejemplos del algoritmo 2PL son:

1. Copia primaria:

2. De voto:

3. Centralizado: Es necesario considerar distintos factores como:

Cual es la unidad atómica más pequeña que el sistema permite bloquear

Cual es el intervalo de sincronización para todas las copias de un elemento

Donde se deben colocar las tablas con la información de los bloqueos

Que tan probable es que ocurra por los factores anteriores un bloqueo mutuo Las reglas para manejar los bloqueos son:

Lectura-escritura o escritura-escritura, no pueden tener acceso simultáneamente a un elemento

Una vez se libere un bloqueo no se puede pedir otro Lee el elemento L
Escribe en el elemento E
Libera el bloqueo de L
Libera el bloqueo de E El ordenamiento de estampas de tiempo (TO) se realiza mediante la siguiente regla: Timestamp es un mecanismo en que el orden del serialización se selecciona a priori; la ejecución de la transacción es obligada a obedecer este orden. En el timestamp, cada transacción tiene asignado un único timestamp por el sincronizador. A diferencia de los algoritmos basados en candados, los algoritmos basados en estampas de tiempo no pretenden mantener la seriabilidad por exclusión mutua. 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 igualmente crecientes. Así, las estampas de tiempo son valores derivados de un dominio totalmente ordenado. <Contador local, identificador de nodo> Obviamente, para lograr un único timestamp para las transacciones que llegan de nodos diferentes de un sistema distribuido, todos los relojes en todos los nodos deben sincronizarse y además deben resolverse dos timestamps idénticos. Lamport ha descrito un algoritmo para sincronizar los relojes distribuidos vía el paso de un mensaje. Si un mensaje llega a un nodo local de un nodo remoto con un timestamp más alto, se supone que el reloj local es más lento que el anterior. El reloj local es incrementado por el timestamp del recientemente mensaje recibido. De esta manera todos los relojes están avanzados hasta que ellos sean sincronizados En el otro esquema dónde dos timestamps idénticos no deben asignarse a dos transacciones, cada nodo asigna un timestamp a sólo una transacción a cada tictac del reloj. Además el tiempo del reloj local se guarda en los bits de MSI Y los identificadores del nodo son guardados en los bits LSI. Dado que los identificadores de los nodos son diferentes, este procedimiento asegurará un único timestamp. Cuando las operaciones de dos transacciones entran en conflicto, se exige ser procesadas en el orden del timestamp. Esencialmente cada nodo procesa los funcionamientos contradictorios que el timestamp pida, cada relación de conflicto leer-escribe y escribir-escribir está resuelta por el orden del timestamp. Por consiguiente todos los caminos en la relación están en el orden del timestamp y, desde que todas las transacciones tienen un único timestamp, se asume que ningún ciclo es posible en un gráfico. 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. Regla TO: dadas dos operaciones en conflicto, Oij y Oki, perteneciendo a las transacciones Ti y Tk, respectivamente, Oij es ejecutada antes de Oki, si y solamente si, ts (Ti) < ts (lk). En este caso Ti se dice ser un transacción más vieja y Tk se dice ser una transacción más joven. 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. Tipos de ordenamiento Ordenamiento conservador por estampas de tiempo Ordenamiento por estampas de tiempo múltiples Conclusiones 1 2 f 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 esto puede inducir la creación de interbloqueos (dead locks). En este algoritmo se guardan el momento (tiempo) en que se realizó alguna operación sobre la base de datos. Estas estampas de tiempo son utilizadas en el vector de recepción. Cada sitio participante P compara su vector de recepción con la entrada del coordinador en el sitio C, tendiendo los casos: Al término de la transacción el coordinador fuerza la escritura de un registro de terminación exitosa (commit) en el archivo, causando la atomicidad, y una confirmación independiente en el sitio coordinador. El coordinador del sitio C (lugar donde se genera la transacción) ejecuta todas sus lecturas y escrituras localmente, posteriormente se transmiten las operaciones a los otros sitios participantes en la operación, junto con el vector de recepción con la entrada del sitio C actualizada con la estampa de tiempo de la transacción Sí la entrada del vector de recepción que acaba de recibir es igual al de su propio vector, el participante puede realizar la escritura, ya que el sitio P ha ejecutado todas las acciones sobre el objeto “o” originadas en C, y se le asigna la estampa de tiempo de P al vector de recepción en la entrada del sitio C. Sí la comparación falla, es decir, la estampa de tiempo del participante no es igual a la del coordinador, se cancelará la transacción en P, y no se aceptará ninguna escritura posterior para esa transacción en particular. En el caso de los que no pudieron participar o cancelaron, el coordinador no recibe un acuse de esta decisión. Por lo que en cada sitio se guarda un registro de reconciliación en donde se almacenan los datos (objeto, sitio) en una tabla llamada Registro. El sitio coordinador envía esta decisión a los demás sitios participantes, cada participante que aceptó todas las escrituras, confirma hasta que se recibe la decisión del coordinador, registrando en el archivo el registro commit, después envía un mensaje al coordinador indicando que la confirmación fue satisfactoriamente ejecutada El coordinador nota que un participante P no ha aceptado su decisión, por lo que inserta un registro en la tabla de reconciliación. La reconciliación entre dos sitios (S y P) sobre el objeto “o” se efectúa de la siguiente manera: Si el sitio S tiene una tupia (o, p) en su tabla Registro, S inicia la reconciliación enviando una solicitud de reconciliación al sitio P junto con el vector de recepción. Si el nodo P acepta la reconciliación, P envía a S su vector de recepción para el objeto “o” de la tupla. Cada sitio utiliza el vector de recepción que ha recibido y busca en su propio archivo aquellas acciones que no se han ejecutado en el otro sitio, tales acciones son seleccionadas comparando la estampa de tiempo de cada una de las opciones con la entrada de su sitio coordinador en el vector de recepción. Estas acciones son extraídas y enviadas al otro sitio. Cuando el sitio recibe estas acciones, las ejecuta y las agrega a su archivo. Al final de la reconciliación, se actualiza el vector de recepción de ambos sitios El algoritmo de Bloqueo de Dos Fases tiene como característica primordial el bloqueo y la división de los bloqueos en dos fases primordiales. Estas fases permitirán asegurar del todo que las operaciones no caigan en conflicto, con la desventaja de que las copias de los datos en cualquiera de los nodos participantes estarán totalmente inservibles hasta el momento de que la transacción correspondiente haga commit. El algoritmo de Estampas de Tiempo, logra evitar los bloqueos a los datos y cualquier tipo de inconveniencia con un acceso libre a la información. Propone una sincronización con tiempos que facilita enormemente el control de la concurrencia en todo el sistema. Ya que las operaciones deben seguir un orden establecido por la marca de tiempo que los acompaña. Por otro lado usa muchas estructuras para almacenar la información del estado de las transacciones y las operaciones. Preguntas: Control de concurrencia Serialización Algoritmos pesimistas Algoritmos optimistas Tipos de algoritmos Bloqueos Tipos de bloqueos Estampas de tiempo Tipos de estampas de tiempo Serializabilidad de un plan Serializabilidad de conflictos Serializabilidad de vistas Serializabilidad Propiedad que indica que las operaciones de dos transacciones pueden intercalarse de forma que se comporten como si se estuviesen ejecutando en serie. Ejecutar las transacciones en serie, de forma que solo haya una transacción activa cada momento. No importa que transacción se ejecute primero, y siempre que las transacciones se ejecuten de forma atómica la base de datos se mantendrá en un estado consistente. Un plan de n transacciones es serializable si es equivalente a un plan en serie de las n transacciones, es decir produce los mismos resultados que alguna ejecución en serie. La ordenación de las operaciones de lectura y escritura es importante:
Si dos transacciones únicamente leen un determinado elemento de datos, no entran en conflicto entre si y el orden no es importante. Si una de las transacciones escribe un elemento y otra lee o escribe en el mismo elemento, el orden de ejecución si es importante. Si hay dos transacciones que leen o escriben elementos de datos completamente independientes, no entran en conflicto entre si y el orden no es importante. Para que una planificación sea serializable en cuanto vistas debe cumplir: Para cada operación de lectura sobre el elemento de datos x por parte de la transacción Ti en la planificación S1, si el valor leído de x ha sido escrito por la transacción Tj, entonces la transacción Ti también debe de leer el valor x producido por la transacción Tj en la planificación S2 Para cada elemento de datos x, si la última operación de escritura sobre x fue realizada por la transacción Ti en la planificación S1, la misma transacción debe realizar la escritura final del elemento de datos x en la planificación S2 Para cada elemento de datos x, si la transacción Ti lee el valor inicial de x es la planificación S1 entonces la transacción Ti también debe leer el valor inicial de x en la planificación S2. Tipos de serialización Asegura que transacciones múltiples sometidas por usuarios diferentes no interfieran unas con otras de forma que se produzcan resultados incorrectos. El control de concurrencia en base de datos distribuidas es más compleja que en sistemas centralizados. Un aspecto interesante del control de concurrencia es el manejo de interbloqueos, el sistema no debe permitir que dos o más transacciones se bloqueen entre ellas. El hecho de reservar un asiento en un avión mediante un sistema basado en aplicaciones web, cuando decenas de personas en el mundo pueden reservarlo también, 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 Otro ejemplo en el que podemos observar la incidencia del control de concurrencia es el siguiente: en una Base de Datos bancaria podría ocurrir que se paguen dos cheques en forma simultánea sobre una cuenta que no tiene saldo suficiente para cubrirlos en su totalidad, esto es posible evitarlo si se tiene un control de concurrencia. La manera más simple de lograr este objetivo es ejecutar cada transacción sola, una después de otra. Sin embargo, esto puede afectar grandemente el desempeño de un DBMS dado que el nivel de concurrencia se reduce al mínimo. El número de transacciones activas, es probablemente el parámetro más importante para 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 El control de concurrencia presenta principalmente dos enfoques: Ejemplo •Aislamiento de transacciones: •Consistencia del procesamiento de transacciones El control de concurrencia trata con dos problemas principalmente: Define el grado en que se debe aislar una transacción de las modificaciones de recursos o datos realizadas por otras transacciones. Los niveles de aislamiento se describen en función de los efectos secundarios de la simultaneidad que se permiten, como las lecturas de datos sucios o las lecturas fantasmas. La consistencia de una transacción es simplemente su correctitud. Podría definirse como la coherencia entre todos los datos de la base de datos. La consistencia entre transacciones se garantiza mediante el aislamiento de las mismas. Un lock es una estructura que solo puede ser adquirida por una hebra de ejecución (thread) a la vez.
Si dos ejecuciones tratan de obtener un lock para actualizar una tabla, la primera que trate de obtenerlo tendrá acceso exclusivo a la tabla, la segunda debe esperar a que la primera lo suelte para obtener el acceso. Los locks pueden tener distintas granularidades: Base de Datos, Tabla, Tupla, Atributo.
Además de los locks exclusivos existen locks de solo lectura o locks compartidos que pueden estar simultáneamente siendo utilizados por distintas ejecuciones. Un método de control de concurrencia es correcto si es serializable, es decir existe una secuencia equivalente en que las operaciones de cada transacción aparecen antes o después de otra transacción pero no entremezcladas. Una ejecución serial de transacciones es siempre correcta. • Pesimista: asume que es muy probable que ocurran problemas =>actúa a la defensiva impidiendo la aparición de conflictos usando locks. • Optimista: supone que los conflictos son escasos=> permitir acceso concurrente y deshacer las acciones problemáticas. Aquellos algoritmos que están basados en acceso mutuamente exclusivo a datos compartidos (candados) Aquellos que intentan ordenar la ejecución de las transacciones de acuerdo a un conjunto de reglas (protocolos) Esto resulta en dos clases: Pesimistas Optimistas. Esas primitivas se pueden usar en algoritmos con dos puntos de vista diferentes: 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 los algoritmos optimistas se clasifican por basados en candados y basados en estampas de tiempo Para manejar los bloqueos hay distintos acercamientos: prevención, detección, y recuperación. Gracias!
Full transcript