DBMS distribuido: control de la concurrencia
Las técnicas de control de simultaneidad aseguran que se ejecuten múltiples transacciones simultáneamente mientras se mantienen las propiedades ACID de las transacciones y la serialización en los horarios.
En este capítulo, estudiaremos los diversos enfoques para el control de concurrencia.
Bloqueo de protocolos de control de simultaneidad
Los protocolos de control de concurrencia basados en bloqueo utilizan el concepto de bloqueo de elementos de datos. UNAlockes una variable asociada con un elemento de datos que determina si se pueden realizar operaciones de lectura / escritura en ese elemento de datos. Generalmente, se usa una matriz de compatibilidad de bloqueo que establece si un elemento de datos se puede bloquear mediante dos transacciones al mismo tiempo.
Los sistemas de control de concurrencia basados en bloqueos pueden utilizar protocolos de bloqueo de una o dos fases.
Protocolo de bloqueo de una fase
En este método, cada transacción bloquea un artículo antes de su uso y libera el bloqueo tan pronto como termina de usarlo. Este método de bloqueo proporciona la máxima simultaneidad, pero no siempre impone la serialización.
Protocolo de bloqueo de dos fases
En este método, todas las operaciones de bloqueo preceden a la primera operación de desbloqueo o desbloqueo. La transacción consta de dos fases. En la primera fase, una transacción solo adquiere todos los candados que necesita y no libera ningún candado. A esto se le llama expansión ogrowing phase. En la segunda fase, la transacción libera los bloqueos y no puede solicitar ningún bloqueo nuevo. Esto se llamashrinking phase.
Se garantiza que cada transacción que sigue el protocolo de bloqueo de dos fases es serializable. Sin embargo, este enfoque proporciona un bajo paralelismo entre dos transacciones en conflicto.
Algoritmos de control de simultaneidad de marca de tiempo
Los algoritmos de control de concurrencia basados en marcas de tiempo utilizan la marca de tiempo de una transacción para coordinar el acceso simultáneo a un elemento de datos para garantizar la serialización. Una marca de tiempo es un identificador único proporcionado por DBMS a una transacción que representa la hora de inicio de la transacción.
Estos algoritmos aseguran que las transacciones se confirmen en el orden dictado por sus marcas de tiempo. Una transacción más antigua debe confirmarse antes que una transacción más joven, ya que la transacción más antigua ingresa al sistema antes que la más joven.
Las técnicas de control de simultaneidad basadas en marcas de tiempo generan programas serializables de manera que el programa serial equivalente se organiza en orden de antigüedad de las transacciones participantes.
Algunos de los algoritmos de control de concurrencia basados en marcas de tiempo son:
- Algoritmo básico de ordenación de marcas de tiempo.
- Algoritmo de orden conservador de marca de tiempo.
- Algoritmo de múltiples versiones basado en el orden de la marca de tiempo.
Los pedidos basados en marcas de tiempo siguen tres reglas para hacer cumplir la serialización:
Access Rule- Cuando dos transacciones intentan acceder al mismo elemento de datos simultáneamente, para operaciones en conflicto, se da prioridad a la transacción anterior. Esto hace que la transacción más joven espere a que la transacción anterior se confirme primero.
Late Transaction Rule- Si una transacción más reciente ha escrito un elemento de datos, entonces una transacción anterior no puede leer o escribir ese elemento de datos. Esta regla evita que la transacción anterior se confirme después de que la transacción más reciente ya se haya comprometido.
Younger Transaction Rule - Una transacción más reciente puede leer o escribir un elemento de datos que ya ha sido escrito por una transacción anterior.
Algoritmo de control de simultaneidad optimista
En sistemas con bajas tasas de conflicto, la tarea de validar cada transacción para la serialización puede reducir el rendimiento. En estos casos, la prueba de serialización se pospone justo antes de la confirmación. Dado que la tasa de conflicto es baja, la probabilidad de abortar transacciones que no son serializables también es baja. Este enfoque se denomina técnica de control de concurrencia optimista.
En este enfoque, el ciclo de vida de una transacción se divide en las siguientes tres fases:
Execution Phase - Una transacción recupera elementos de datos en la memoria y realiza operaciones sobre ellos.
Validation Phase - Una transacción realiza verificaciones para garantizar que la confirmación de sus cambios en la base de datos pase la prueba de serialización.
Commit Phase - Una transacción vuelve a escribir el elemento de datos modificado en la memoria en el disco.
Este algoritmo utiliza tres reglas para hacer cumplir la serialización en la fase de validación:
Rule 1- Dadas dos transacciones T i y T j , si T i está leyendo el elemento de datos que T j está escribiendo, entonces la fase de ejecución de T i no puede superponerse con la fase de confirmación de T j . T j puede comprometerse solo después de que T i haya finalizado la ejecución.
Rule 2- Dadas dos transacciones T i y T j , si T i está escribiendo el elemento de datos que T j está leyendo, entonces la fase de confirmación de T i no puede superponerse con la fase de ejecución de T j . T j puede comenzar a ejecutarse solo después de que T i ya se haya comprometido.
Rule 3- Dadas dos transacciones T i y T j , si T i está escribiendo el elemento de datos que T j también está escribiendo, entonces la fase de compromiso de T i no puede superponerse con la fase de compromiso de T j . T j puede comenzar a comprometerse solo después de que T i ya se haya comprometido.
Control de concurrencia en sistemas distribuidos
En esta sección, veremos cómo se implementan las técnicas anteriores en un sistema de base de datos distribuida.
Algoritmo de bloqueo distribuido de dos fases
El principio básico del bloqueo distribuido de dos fases es el mismo que el del protocolo básico de bloqueo de dos fases. Sin embargo, en un sistema distribuido hay sitios designados como administradores de bloqueo. Un administrador de bloqueo controla las solicitudes de adquisición de bloqueo de los monitores de transacciones. Con el fin de reforzar la coordinación entre los administradores de esclusas en varios sitios, al menos un sitio tiene la autoridad para ver todas las transacciones y detectar conflictos de cerraduras.
Dependiendo de la cantidad de sitios que pueden detectar conflictos de bloqueo, los enfoques de bloqueo distribuidos en dos fases pueden ser de tres tipos:
Centralized two-phase locking- En este enfoque, un sitio se designa como administrador de bloqueo central. Todos los sitios en el entorno conocen la ubicación del administrador de bloqueo central y obtienen el bloqueo durante las transacciones.
Primary copy two-phase locking- En este enfoque, varios sitios se designan como centros de control de esclusas. Cada uno de estos sitios tiene la responsabilidad de administrar un conjunto definido de bloqueos. Todos los sitios saben qué centro de control de bloqueo es responsable de administrar el bloqueo de qué elemento de tabla / fragmento de datos.
Distributed two-phase locking- En este enfoque, hay varios administradores de bloqueo, donde cada administrador de bloqueo controla los bloqueos de elementos de datos almacenados en su sitio local. La ubicación del administrador de bloqueo se basa en la distribución y replicación de datos.
Control de simultaneidad de marca de tiempo distribuida
En un sistema centralizado, la marca de tiempo de cualquier transacción está determinada por la lectura del reloj físico. Pero, en un sistema distribuido, las lecturas del reloj físico / lógico local de cualquier sitio no se pueden usar como marcas de tiempo globales, ya que no son únicas a nivel mundial. Entonces, una marca de tiempo se compone de una combinación de la identificación del sitio y la lectura del reloj de ese sitio.
Para implementar algoritmos de ordenación de marcas de tiempo, cada sitio tiene un programador que mantiene una cola separada para cada administrador de transacciones. Durante la transacción, un administrador de transacciones envía una solicitud de bloqueo al programador del sitio. El planificador coloca la solicitud en la cola correspondiente en orden de marca de tiempo creciente. Las solicitudes se procesan desde el principio de las colas en el orden de sus marcas de tiempo, es decir, las más antiguas primero.
Gráficos de conflicto
Otro método consiste en crear gráficos de conflictos. Para esta transacción se definen clases. Una clase de transacción contiene dos conjuntos de elementos de datos denominados conjunto de lectura y conjunto de escritura. Una transacción pertenece a una clase particular si el conjunto de lectura de la transacción es un subconjunto del conjunto de lectura de la clase y el conjunto de escritura de la transacción es un subconjunto del conjunto de escritura de la clase. En la fase de lectura, cada transacción emite sus solicitudes de lectura para los elementos de datos en su conjunto de lectura. En la fase de escritura, cada transacción emite sus solicitudes de escritura.
Se crea un gráfico de conflictos para las clases a las que pertenecen las transacciones activas. Contiene un conjunto de bordes verticales, horizontales y diagonales. Un borde vertical conecta dos nodos dentro de una clase y denota conflictos dentro de la clase. Un borde horizontal conecta dos nodos en dos clases y denota un conflicto de escritura-escritura entre diferentes clases. Un borde diagonal conecta dos nodos en dos clases y denota un conflicto de escritura-lectura o lectura-escritura entre dos clases.
Los gráficos de conflicto se analizan para determinar si dos transacciones dentro de la misma clase o entre dos clases diferentes se pueden ejecutar en paralelo.
Algoritmo de control de simultaneidad optimista distribuido
El algoritmo de control de concurrencia optimista distribuido extiende el algoritmo de control de concurrencia optimista. Para esta extensión, se aplican dos reglas:
Rule 1- De acuerdo con esta regla, una transacción debe validarse localmente en todos los sitios cuando se ejecuta. Si se determina que una transacción no es válida en cualquier sitio, se cancela. La validación local garantiza que la transacción mantiene la serialización en los sitios donde se ha ejecutado. Una vez que una transacción pasa la prueba de validación local, se valida globalmente.
Rule 2- De acuerdo con esta regla, después de que una transacción pasa la prueba de validación local, debe ser validada globalmente. La validación global asegura que si dos transacciones en conflicto se ejecutan juntas en más de un sitio, deben confirmarse en el mismo orden relativo en todos los sitios que ejecutan juntas. Esto puede requerir que una transacción espere a la otra transacción en conflicto, después de la validación antes de confirmar. Este requisito hace que el algoritmo sea menos optimista, ya que es posible que una transacción no pueda confirmarse tan pronto como se valide en un sitio.