Bloqueo de dos fases

En bases de datos y procesamiento de transacciones, el bloqueo en dos fases (2PL) es un método de control de concurrencia que garantiza la serialización. También es el nombre del conjunto resultante de programaciones de transacciones de la base de datos (historiales). El protocolo utiliza bloqueos, aplicados por una transacción a los datos, que pueden bloquear (interpretados como señales para detener) que otras transacciones accedan a los mismos datos durante la vida de la transacción.

Con el protocolo 2PL, los bloqueos se aplican y eliminan en dos fases:

1. Fase de expansión: se adquieren cerraduras y no se liberan cerraduras.
2. Fase de rociado: se liberan cerraduras y no se adquieren cerraduras.

El protocolo básico utiliza dos tipos de bloqueos: bloqueos compartidos y exclusivos. Los refinamientos del protocolo básico pueden usar más tipos de bloqueo. Al usar bloqueos que bloquean procesos, 2PL puede estar sujeto a interbloqueos que resultan del bloqueo mutuo de dos o más transacciones.

Bloqueos de acceso a datos

Un candado es un objeto del sistema asociado con un recurso compartido, como un elemento de datos de un tipo elemental, una fila en una base de datos o una página de memoria. En una base de datos, es posible que una transacción deba adquirir un bloqueo en un objeto de base de datos (un bloqueo de acceso a datos) antes de acceder al objeto. El uso correcto de bloqueos evita operaciones no deseadas, incorrectas o inconsistentes en recursos compartidos por otras transacciones simultáneas. Cuando otra transacción necesita acceder a un objeto de base de datos con un bloqueo existente adquirido por una transacción, el sistema verifica el bloqueo existente para el objeto y el tipo de acceso previsto. Si el tipo de bloqueo existente no permite este tipo de acceso simultáneo intentado específico, la transacción que intenta acceder se bloquea (de acuerdo con un acuerdo/esquema predefinido). En la práctica, un bloqueo en un objeto no bloquea directamente la operación de una transacción en el objeto, sino que impide que esa transacción adquiera otro bloqueo en el mismo objeto, que la transacción debe mantener o poseer antes de realizar esta operación.. Por lo tanto, con un mecanismo de bloqueo, el bloqueo de la operación necesaria se controla mediante un esquema de bloqueo de bloqueo adecuado, que indica qué tipo de bloqueo bloquea qué tipo de bloqueo.

Se utilizan dos tipos principales de candados:

• Escribir-lock ()Cerradura exclusiva) se asocia con un objeto de base de datos por una transacción (Terminología: "la transacción bloquea el objeto", o "aprenda cerradura para él") antes escritura (inserting/modifying/deleting) este objeto.
• Reloj de lectura ()Cerradura compartida) se asocia con un objeto de base de datos por una transacción antes lectura Este objeto.

Las interacciones comunes entre estos tipos de bloqueo se definen mediante el comportamiento de bloqueo de la siguiente manera:

• Una existente escriba-lock en un objeto de la base de datos bloquea una intención escribir sobre el mismo objeto (ya solicitado/publicado) por otra transacción bloqueando un respectivo escriba-lock de ser adquirido por la otra transacción. El segundo bloqueo de escritura será adquirido y la escritura solicitada del objeto tendrá lugar (materializar) después de que el bloqueo de escritura existente sea liberado.
• A escriba-lock bloques an intended (already requested/issued) leído por otra transacción bloqueando los respectivos read-lock .
• A read-lock bloques una intención escribir por otra transacción bloqueando los respectivos escriba-lock.
• A read-lock no bloquea un leído por otra transacción. Los respectivos read-lock para la lectura prevista se adquiere (compartida con la lectura anterior) inmediatamente después de que se solicite la lectura prevista, y luego se realiza la lectura prevista.

Existen varias variaciones y mejoras de estos principales tipos de bloqueo, con sus respectivas variaciones de comportamiento de bloqueo. Si un primer bloqueo bloquea otro bloqueo, los dos bloqueos se denominan incompatibles; de lo contrario, los bloqueos son compatibles. A menudo, los tipos de bloqueo que bloquean las interacciones se presentan en la literatura técnica mediante una tabla de compatibilidad de bloqueo. El siguiente es un ejemplo con los principales tipos de bloqueo comunes:

Bloquear tabla de compatibilidad

Tipo de bloqueo	read-lock	escriba-lock
read-lock	✔	X
escriba-lock	X	X

✔ indica compatibilidad

X indica incompatibilidad, es decir, un caso cuando una cerradura del primer tipo (en la columna izquierda) en un objeto bloquea una cerradura del segundo tipo (en la fila superior) de ser adquirida en el mismo objeto (por otra transacción). Un objeto normalmente tiene una cola de espera solicitada (por transacciones) operaciones con cerraduras respectivas. El primer bloqueo bloqueado para la operación en la cola se adquiere tan pronto como el bloqueo existente se elimina del objeto, y luego se ejecuta su operación respectiva. Si un bloqueo para la operación en la cola no está bloqueado por cualquier bloqueo existente (existencia de múltiples bloqueos compatibles en un mismo objeto es posible simultáneamente), se adquiere inmediatamente.

Comentario: En algunas publicaciones, las entradas de mesa son simplemente "compatibles" o "incompatibles", o respectivamente "sí" o "no".

Bloqueo bifásico y sus casos especiales

Bloqueo de dos fases

Según el protocolo de bloqueo en dos fases, una transacción maneja sus bloqueos en dos fases distintas y consecutivas durante la ejecución de la transacción:

1. Fase de ampliación (aka Growing phase): se adquieren cerraduras y no se liberan cerraduras (el número de cerraduras sólo puede aumentar).
2. Fase de riego (aka Contracting phase): locks are released and no locks are acquired.

Las reglas de bloqueo de dos fases se pueden resumir como: nunca adquiera un bloqueo después de que se haya liberado. La propiedad de serialización está garantizada para un horario con transacciones que obedecen esta regla.

Normalmente, sin conocimiento explícito en una transacción al final de la fase 1, la regla se determina de forma segura solo cuando una transacción ha completado el procesamiento y ha solicitado confirmación. En este caso, todos los bloqueos se pueden liberar a la vez (fase 2).

Bloqueo bifásico conservador

La diferencia entre 2PL y C2PL es que las transacciones de C2PL obtienen todos los bloqueos que necesitan antes de que comiencen las transacciones. Esto es para garantizar que una transacción que ya tiene algunos bloqueos no bloquee la espera de otros bloqueos. 2PL conservador previene interbloqueos.

Estricto bloqueo de dos fases

Para cumplir con el protocolo S2PL, una transacción debe cumplir con 2PL y liberar sus bloqueos de escritura (exclusiva) solo después de que haya finalizado, es decir, que esté comprometida o abortado. Por otro lado, los bloqueos read (shared) se liberan regularmente durante la fase 2. Este protocolo no es apropiado en B-trees porque causa cuello de botella (mientras que B-trees siempre comienza a buscar desde la raíz principal).

Fuerte y estricto bloqueo de dos fases

o rigurosidad, o programación rigurosa, o bloqueo bifásico riguroso

Para cumplir con el bloqueo fuerte y estricto en dos fases (SS2PL), el protocolo de bloqueo libera tanto escritura (exclusivo) como lectura (compartido) bloqueos aplicados por una transacción solo después de que la transacción haya finalizado, es decir, solo después de completar la ejecución (estar listo) y convertirse en comprometido o abortado. Este protocolo también cumple con las reglas S2PL. Se puede considerar que una transacción que obedece a SS2PL tiene una fase 1 que dura toda la duración de la ejecución de la transacción, y no tiene una fase 2 (o una fase 2 degenerada). Por lo tanto, solo queda una fase y "dos fases" en el nombre parece que todavía se usa debido al desarrollo histórico del concepto de 2PL, y 2PL es una superclase. La propiedad SS2PL de un cronograma también se denomina rigorosidad. También es el nombre de la clase de programaciones que tienen esta propiedad, y una programación SS2PL también se denomina "programación rigurosa". El término "rigorosidad" está libre del legado innecesario de "bifásico," además de ser independiente de cualquier mecanismo (de bloqueo) (en principio se pueden utilizar otros mecanismos de bloqueo). El mecanismo de bloqueo respectivo de la propiedad a veces se denomina 2PL riguroso.

SS2PL es un caso especial de S2PL, es decir, la clase de horarios SS2PL es una subclase adecuada de S2PL (cada horario SS2PL es también un horario S2PL, pero existen horarios S2PL que no son SS2PL).

SS2PL ha sido el protocolo de control de concurrencia elegido por la mayoría de los sistemas de bases de datos y se ha utilizado desde sus inicios en la década de 1970. Se ha demostrado que es un mecanismo eficaz en muchas situaciones y proporciona, además de Serializabilidad, también Rigor (un caso especial de Recuperabilidad sin cascada), que es fundamental para la recuperación eficiente de la base de datos, y también Ordenación de compromiso (CO) para participar en entornos distribuidos donde un CO Se emplean soluciones basadas en serializabilidad distribuida y serializabilidad global. Al ser un subconjunto de CO, existe una implementación eficiente de SS2PL distribuido sin un administrador de bloqueo distribuido (DLM), mientras que los interbloqueos distribuidos (ver a continuación) se resuelven automáticamente. El hecho de que SS2PL se emplea en sistemas de múltiples bases de datos garantiza la serialización global se conoce desde hace años antes del descubrimiento de CO, pero solo con CO llegó la comprensión del papel de un protocolo de compromiso atómico en el mantenimiento de la serialización global, así como la observación de automático resolución de puntos muertos distribuidos (consulte un ejemplo detallado de Distributed SS2PL). De hecho, SS2PL que hereda las propiedades de Recuperabilidad y CO es más significativo que ser un subconjunto de 2PL, que por sí mismo en su forma general, además de comprender un mecanismo de serialización simple (sin embargo, la serialización también está implícita en CO), no se conoce. para proporcionar SS2PL con otras cualidades significativas. 2PL en su forma general, así como cuando se combina con Strictness, es decir, Strict 2PL (S2PL), no se sabe que se use en la práctica. El popular SS2PL no requiere marcar "fin de fase 1" como lo hacen 2PL y S2PL, y por lo tanto es más simple de implementar. Además, a diferencia del 2PL general, SS2PL proporciona, como se mencionó anteriormente, las útiles propiedades de ordenamiento de Rigurosidad y Compromiso.

Existen muchas variantes de SS2PL que usan varios tipos de bloqueo con varias semánticas en diferentes situaciones, incluidos los casos de cambio de tipo de bloqueo durante una transacción. Son notables las variantes que utilizan el bloqueo de granularidad múltiple.

Comentarios:

1. SS2PL vs. S2PL: Ambos proporcionan Serializability y Strictness. Puesto que S2PL es una superclase de SS2PL puede, en principio, proporcionar más concurrencia. Sin embargo, ninguna ventaja de concurrencia es típicamente notada (exactamente el mismo bloqueo existe para ambos, con prácticamente no mucho antes de la liberación de bloqueo para S2PL), y la parte superior de tratar con un mecanismo de fin de fase-1 en S2PL, separado del final de transacción, no está justificada. Además, mientras que SS2PL proporciona la orden de compromiso, S2PL no lo hace. Esto explica la preferencia de SS2PL sobre S2PL.
2. Especialmente antes de 1990, pero también después, en muchos artículos y libros, por ejemplo, (Bernstein et al. 1987, p. 59), el término "Strict 2PL" (S2PL) ha sido definido frecuentemente por el protocolo de bloqueo "Libera todas las cerraduras sólo después del final de transacción", que es el protocolo de SS2PL. Así, "Strict 2PL" no podría ser el nombre de la intersección de Strictness y 2PL, que es mayor que la clase generada por el protocolo SS2PL. Esto ha causado confusión. Con una definición explícita de S2PL como la intersección de Strictness y 2PL, un nuevo nombre para SS2PL, y una distinción explícita entre las clases S2PL y SS2PL, los artículos (Breitbart et al. 1991) y (Raz 1992) tienen la intención de aclarar la confusión: el primero utilizando el nombre "rigorousness", y el segundo "SS2PL".
3. Una propiedad más general de la SS2PL existe (un horario super-clase), Ordenación estricta del compromiso (Strict CO, o SCO), que también proporciona tanto serializability, strictness, y CO, y tiene una sobrecarga similar de bloqueo. A diferencia de SS2PL, SCO no bloquea un conflicto de lectura-escritura (una cerradura de lectura no bloquea la adquisición de una cerradura de escritura; tanto SCO como SS2PL tienen el mismo comportamiento para los conflictos de lectura de escritura y escritura) a costa de un posible compromiso retardado, y sobre dicho tipo de conflicto SCO tiene un tiempo de terminación promedio de transacción más corto y mejor rendimiento que SS2PL. Mientras SS2PL obedece a cuadro de compatibilidad de bloqueo arriba, la SCO tiene el siguiente cuadro:

Compatibilidad de bloqueo para SCO

Tipo de bloqueo	read-lock	escriba-lock
read-lock		X
escriba-lock	X	X

Tenga en cuenta que aunque SCO libera todas las cerraduras al final de transacción y cumple con las reglas de bloqueo 2PL, SCO no es un subconjunto de 2PL debido a su diferente tabla de compatibilidad de bloqueo. SCO permite la materialización de los conflictos de escritura de lectura entre dos transacciones en sus fases 1, que 2PL no permite en la fase 1 (ver sobre conflictos materializados en Serializability). Por otro lado, 2PL permite otros tipos de conflictos materializados en la fase 2 que SCO no permite en absoluto. Juntos esto implica que las clases programadas 2PL y SCO son incomparables (es decir, ninguna clase contiene la otra clase).

Resumen - Relaciones entre clases

Contención de las clases programadas: Una flecha de la clase A a la clase B indica que la clase A contiene estrictamente B; la falta de un camino dirigido entre clases significa que las clases son incomparables. Una propiedad es inherentemente bloqueando, si se puede aplicar solamente bloqueando las operaciones de acceso de datos de la transacción hasta que se produzcan ciertos eventos en otras transacciones. (Raz 1992)

Entre dos clases de horario (definidas por sus respectivas propiedades de horarios) que tienen horarios comunes, uno contiene al otro (contiene estrictamente si no lo son iguales), o son incomparables. Las relaciones de contención entre las clases 2PL y otras clases principales de programación se resumen en el siguiente diagrama. 2PL y sus subclases bloquean de forma inherente, lo que significa que no existen implementaciones optimistas para ellos (y cada vez que se menciona "2PL optimista" se refiere a un mecanismo diferente con una clase que incluye también horarios que no están en la clase 2PL).

Interbloqueos en 2PL

Los bloqueos bloquean las operaciones de acceso a datos. El bloqueo mutuo entre transacciones da como resultado un punto muerto, en el que la ejecución de estas transacciones se detiene y no se puede completar. Por lo tanto, es necesario resolver los interbloqueos para completar estas transacciones. ejecuciones y liberación de recursos informáticos relacionados. Un interbloqueo es un reflejo de un ciclo potencial en el gráfico de precedencia, que ocurriría sin el bloqueo. Un interbloqueo se resuelve abortando una transacción involucrada con dicho ciclo potencial y rompiendo el ciclo. A menudo se detecta utilizando un gráfico de espera (un gráfico de conflictos bloqueados por bloqueos para que no se materialicen; los conflictos que no se materializan en la base de datos debido a operaciones bloqueadas no se reflejan en el gráfico de precedencia y no afectan serializabilidad), que indica qué transacción está "esperando por" liberación de bloqueo por la cual transacción, y un ciclo significa un interbloqueo. Abortar una transacción por ciclo es suficiente para romper el ciclo. Si una transacción ha sido abortada debido a la resolución de interbloqueos, depende de la aplicación decidir qué hacer a continuación. Por lo general, una aplicación reiniciará la transacción desde el principio, pero puede retrasar esta acción para dar a otras transacciones suficiente tiempo para finalizar para evitar que se produzca otro interbloqueo.

En un entorno distribuido, se utiliza un protocolo de compromiso atómico, normalmente el protocolo de compromiso de dos fases (2PC), para la atomicidad. Cuando los datos recuperables (datos bajo control de transacciones) se dividen entre los participantes de 2PC (es decir, cada objeto de datos está controlado por un solo participante de 2PC), los interbloqueos distribuidos (globales), los interbloqueos que involucran a dos o más participantes en 2PC, se resuelven automáticamente de la siguiente manera:

Cuando SS2PL se usa efectivamente en un entorno distribuido, los interbloqueos globales debidos al bloqueo generan interbloqueos de votación en 2PC, y son resueltos automáticamente por 2PC (ver Orden de compromiso (CO), en Caracterización exacta de interbloqueos de votación por ciclos globales; No se conoce ninguna referencia excepto los artículos CO para notar esto). Para el caso general de 2PL, los interbloqueos globales se resuelven automáticamente de manera similar mediante el protocolo de punto de sincronización del final de la fase 1 en una transacción distribuida (el punto de sincronización se logra mediante la "votación" (notificando el final de la fase 1 local), y se propaga a los participantes en una transacción distribuida de la misma manera que un punto de decisión en el compromiso atómico; en analogía con el punto de decisión en CO, una operación conflictiva en 2PL no puede ocurrir antes del punto de sincronización final de la fase 1, con la misma votación resultante: interbloqueo en el caso de un interbloqueo de acceso a datos global; el interbloqueo de votación (que también es un interbloqueo global basado en bloqueo) se resuelve automáticamente mediante el protocolo abortando alguna transacción involucrada, con un voto faltante, generalmente usando un tiempo de espera).

Comentario:

Cuando los datos se dividen entre protocolo de compromiso atómico (por ejemplo, 2PC) participantes, automático estancamiento mundial la resolución se ha pasado por alto en la literatura de investigación de bases de datos, aunque los estancamientos en esos sistemas han sido un área de investigación bastante intensiva:

• Para CO y su caso especial SS2PL, la resolución automática por el protocolo de compromiso atómico ha sido notado sólo en los artículos de CO. Sin embargo, se ha notado en la práctica que en muchos casos los estancamientos globales son detectados muy infrecuentemente por los mecanismos de resolución dedicados, menos de lo que cabría esperar ("¿Por qué vemos tan pocos estancamientos globales?"). La razón es probablemente los estancamientos que se resuelven automáticamente y por lo tanto no se manejan y descubrin por los mecanismos;
• Para 2PL en general, la resolución automática por el (mandatorio) protocolo de punto de sincronización final de fase (que tiene el mismo mecanismo de votación que el protocolo de compromiso atómico, y el mismo manejo de votos perdidos al momento de la votación, lo que da lugar a una resolución global de estancamiento) no se ha mencionado hasta hoy (2009). Prácticamente sólo se utiliza el caso especial SS2PL, donde no se necesita sincronización de fin de fase uno además de protocolo de compromiso atómico.

En un entorno distribuido donde los datos recuperables no se dividen entre los participantes en el protocolo de compromiso atómico, no existe tal resolución automática, y los estancamientos distribuidos deben ser resueltos por técnicas específicas.