En bases de datos y procesamiento de transacciones , el bloqueo de dos fases ( 2PL ) es un método de control de concurrencia que garantiza la serialización . [1] [2] También es el nombre del conjunto resultante de transacción base de datos de horarios (historias). El protocolo utiliza bloqueos , aplicados por una transacción a los datos, que pueden bloquear (interpretados como señales para detener) otras transacciones para que no accedan a los mismos datos durante la vida de la transacción.
Mediante el protocolo 2PL, los bloqueos se aplican y eliminan en dos fases:
- Fase de expansión: se adquieren bloqueos y no se liberan bloqueos.
- Fase de contracción: los bloqueos se liberan y no se adquieren bloqueos.
El protocolo básico utiliza dos tipos de cerraduras: cerraduras compartidas y exclusivas . Los refinamientos del protocolo básico pueden utilizar más tipos de bloqueo. Al utilizar bloqueos que bloquean procesos, 2PL puede estar sujeto a puntos muertos que resultan del bloqueo mutuo de dos o más transacciones.
Cerraduras 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 concurrentes. Cuando un objeto de base de datos con un bloqueo existente adquirido por una transacción necesita ser accedido por otra 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 intento de acceso simultáneo 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 sobre el objeto, sino que bloquea esa transacción para que no adquiera otro bloqueo en el mismo objeto, que la transacción debe tener / 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 cerraduras:
- El bloqueo de escritura ( bloqueo exclusivo ) se asocia con un objeto de base de datos mediante una transacción (Terminología: "la transacción bloquea el objeto" o "adquiere un bloqueo para él") antes de escribir (insertar / modificar / eliminar) este objeto.
- El bloqueo de lectura ( bloqueo compartido ) se asocia con un objeto de base de datos mediante una transacción antes de leer (recuperar el estado de) este objeto.
Las interacciones comunes entre estos tipos de bloqueo se definen mediante el comportamiento de bloqueo de la siguiente manera:
- Un bloqueo de escritura existente en un objeto de base de datos bloquea una escritura prevista en el mismo objeto (ya solicitado / emitido) por otra transacción al bloquear un bloqueo de escritura respectivo para que no sea adquirido por la otra transacción. Se adquirirá el segundo bloqueo de escritura y la escritura solicitada del objeto se llevará a cabo (se materializará) después de que se libere el bloqueo de escritura existente.
- Un bloqueo de escritura bloquea una lectura prevista (ya solicitada / emitida) por otra transacción bloqueando el bloqueo de lectura respectivo .
- Un bloqueo de lectura bloquea una escritura prevista por otra transacción bloqueando el bloqueo de escritura respectivo .
- Un bloqueo de lectura no bloquea una lectura prevista por otra transacción. El bloqueo de lectura respectivo para la lectura deseada se adquiere (se comparte con la lectura anterior) inmediatamente después de que se solicita la lectura deseada, y luego tiene lugar la lectura deseada.
Existen varias variaciones y refinamientos de estos principales tipos de bloqueo, con respectivas variaciones de comportamiento de bloqueo. Si una primera cerradura bloquea otra cerradura, las dos cerraduras se denominan incompatibles ; de lo contrario, las cerraduras 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 tipos de bloqueo principales comunes:
Tabla de compatibilidad de cerraduras Tipo de bloqueo bloqueo de lectura bloqueo de escritura bloqueo de lectura ✔ X bloqueo de escritura X X
- ✔ indica compatibilidad
- X indica incompatibilidad, es decir, un caso en el que un candado del primer tipo (en la columna de la izquierda) en un objeto impide que un candado del segundo tipo (en la fila superior) sea adquirido en el mismo objeto (por otra transacción). Un objeto normalmente tiene una cola de operaciones solicitadas en espera (por transacciones) con sus respectivos bloqueos. El primer bloqueo bloqueado para la operación en la cola se adquiere tan pronto como el bloqueo de bloqueo existente se retira del objeto, y luego se ejecuta su operación respectiva. Si un bloqueo para la operación en la cola no está bloqueado por ningún bloqueo existente (la existencia de múltiples bloqueos compatibles en un mismo objeto es posible al mismo tiempo), se adquiere inmediatamente.
- Comentario: En algunas publicaciones, las entradas de la tabla simplemente se marcan como "compatible" o "incompatible", o respectivamente "sí" o "no".
Bloqueo bifásico y sus casos especiales
Bloqueo de dos fases
De acuerdo con el protocolo de bloqueo de dos fases , una transacción maneja sus bloqueos en dos fases consecutivas distintas durante la ejecución de la transacción:
- Fase de expansión (también conocida como fase de crecimiento): los bloqueos se adquieren y no se liberan bloqueos (el número de bloqueos solo puede aumentar).
- Fase de contracción (también conocida como fase de contratación): los bloqueos se liberan y no se adquieren bloqueos.
Las reglas de bloqueo de dos fases se pueden resumir como: nunca adquiera un bloqueo después de que se haya liberado un bloqueo. La propiedad de serialización está garantizada para una programación con transacciones que obedecen a esta regla.
Por lo general, sin conocimiento explícito en una transacción al final de la fase 1, se determina de manera segura solo cuando una transacción ha completado el procesamiento y solicitado la confirmación. En este caso, todos los bloqueos se pueden desbloquear a la vez (fase 2).
Bloqueo conservador de dos fases
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 bloqueará la espera de otros bloqueos. 2PL conservador evita los interbloqueos .
Bloqueo estricto de dos fases
Para cumplir con el protocolo S2PL, una transacción debe cumplir con 2PL y liberar sus bloqueos de escritura (exclusivos) solo después de que haya finalizado, es decir, si se confirma o se cancela . Por otro lado, los bloqueos de lectura (compartidos) se liberan regularmente durante la fase 2. Este protocolo no es apropiado en árboles B porque causa un cuello de botella (mientras que los árboles B siempre comienzan a buscar desde la raíz principal). [ cita requerida ]
Fuerte bloqueo estricto de dos fases
o rigor , o programación rigurosa , o bloqueo riguroso de dos fases
Para cumplir con un fuerte bloqueo estricto de dos fases (SS2PL), el protocolo de bloqueo libera los bloqueos de escritura (exclusivos) y de lectura (compartidos) aplicados por una transacción solo después de que la transacción ha finalizado, es decir, solo después de completar la ejecución (estar listo ) y convertirse ya sea cometido o abortada . 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 ejecución de la transacción, y ninguna fase 2 (o una fase 2 degenerada). Por lo tanto, solo queda una fase, y parece que todavía se utiliza "dos fases" en el nombre debido al desarrollo histórico del concepto de 2PL, y 2PL es una superclase. La propiedad SS2PL de un horario también se llama rigor . También es el nombre de la clase de horarios que tienen esta propiedad, y un horario SS2PL también se denomina "horario riguroso". El término "rigor" está libre del legado innecesario de "dos fases", 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 Rigorous 2PL .
SS2PL es un caso especial de S2PL, es decir, la clase de horarios SS2PL es una subclase adecuada de S2PL (cada horario SS2PL también es 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 Strictness (un caso especial de recuperabilidad sin cascada), que es fundamental para la recuperación eficiente de la base de datos , y también Commitment ordering (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 más abajo) se resuelven automáticamente. El hecho de que SS2PL empleado en sistemas de bases de datos múltiples asegura la serialización global se conoce desde hace años antes del descubrimiento del CO, pero solo con el CO se llegó a comprender el papel de un protocolo de compromiso atómico en el mantenimiento de la serialización global, así como la observación de la serialización automática. resolución de interbloqueo distribuido (consulte un ejemplo detallado de SS2PL distribuido ). De hecho, SS2PL 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 por CO), no se conoce. para dotar a SS2PL de otras cualidades importantes. 2PL en su forma general, así como cuando se combina con Strictness, es decir, Strict 2PL (S2PL), no se sabe que se utilice en la práctica. El popular SS2PL no requiere marcar el "final de la fase 1" como lo hacen 2PL y S2PL y, por lo tanto, es más sencillo de implementar. Además, a diferencia del 2PL general, SS2PL proporciona, como se mencionó anteriormente, las útiles propiedades de ordenación de Estricción y Compromiso .
Existen muchas variantes de SS2PL que utilizan varios tipos de bloqueo con diversas 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:
- SS2PL frente a S2PL: ambos proporcionan serialización y rigor. Dado que S2PL es una superclase de SS2PL, en principio, puede proporcionar más simultaneidad. Sin embargo, por lo general, no se nota prácticamente ninguna ventaja de concurrencia (existe exactamente el mismo bloqueo para ambos, y prácticamente no hay una liberación de bloqueo mucho más temprana para S2PL), y la sobrecarga de lidiar con un mecanismo de fin de fase 1 en S2PL, separado del final de la transacción. , no está justificado. Además, mientras que SS2PL proporciona pedidos de compromiso , S2PL no lo hace. Esto explica la preferencia de SS2PL sobre S2PL.
- Especialmente antes de 1990, pero también después, en muchos artículos y libros, por ejemplo, (Bernstein et al. 1987, p. 59), [1] el término "Strict 2PL" (S2PL) ha sido frecuentemente definido por el protocolo de bloqueo "Release todos los bloqueos solo después del final de la transacción ", que es el protocolo de SS2PL. Por lo tanto, "Strict 2PL" no podría ser el nombre de la intersección de Strictness y 2PL, que es más grande 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) [3] y (Raz 1992) [4 ] han tenido la intención de aclarar la confusión: el primero usando el nombre "rigor" y el segundo "SS2PL".
- Existe una propiedad más general que SS2PL (una superclase de programación), el orden de compromiso estricto (CO estricto o SCO), que también proporciona serializabilidad, rigor y CO, y tiene una sobrecarga de bloqueo similar. A diferencia de SS2PL, SCO no se bloquea ante un conflicto de lectura-escritura (un bloqueo de lectura no bloquea la adquisición de un bloqueo de escritura; tanto SCO como SS2PL tienen el mismo comportamiento para los conflictos de escritura-lectura y escritura-escritura) a costa de un posible retraso commit, y en tal tipo de conflicto, SCO tiene un tiempo promedio de finalización de transacción más corto y un mejor rendimiento que SS2PL. [5] Si bien SS2PL obedece a la tabla de compatibilidad de bloqueo anterior, SCO tiene la siguiente tabla:
Compatibilidad de bloqueo para SCO Tipo de bloqueo bloqueo de lectura bloqueo de escritura bloqueo de lectura X bloqueo de escritura X X
- Tenga en cuenta que aunque SCO libera todos los bloqueos al final de la transacción y cumple con las reglas de bloqueo de 2PL, SCO no es un subconjunto de 2PL debido a su tabla de compatibilidad de bloqueos diferente. SCO permite conflictos de lectura-escritura materializados entre dos transacciones en sus fases 1, que 2PL no permite en la fase 1 (ver sobre conflictos materializados en Serializabilidad ). Por otro lado, 2PL permite otros tipos de conflictos materializados en la fase 2 que SCO no permite en absoluto. En conjunto, esto implica que las clases de horario 2PL y SCO son incomparables (es decir, ninguna clase contiene a la otra clase).
Resumen: relaciones entre clases
Entre dos clases de horario (definidas por las propiedades respectivas de sus horarios) que tienen horarios comunes, una contiene a la otra ( contiene estrictamente si no son iguales) o son incomparables . Las relaciones de contención entre las clases 2PL y otras clases de programación principales se resumen en el siguiente diagrama. 2PL y sus subclases son intrínsecamente bloqueantes , lo que significa que no existen implementaciones optimistas para ellos (y siempre que se menciona "Optimistic 2PL" 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 , donde la ejecución de estas transacciones se detiene y no se puede llegar a una finalización. Por lo tanto, los puntos muertos deben resolverse para completar las ejecuciones de estas transacciones y liberar los 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 relacionada 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 no materializados en la base de datos debido a operaciones bloqueadas no se reflejan en el gráfico de precedencia y no afectan la serialización ), que indica qué transacción está "esperando" la liberación del bloqueo mediante qué transacción, y un ciclo significa un punto muerto. Abortar una transacción por ciclo es suficiente para romper el ciclo. Si una transacción se ha cancelado debido a la resolución de un punto muerto, la aplicación debe 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 tiempo suficiente a otras transacciones para que finalicen y así evitar causar otro punto muerto. [6]
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 participantes de 2PC (es decir, cada objeto de datos está controlado por un solo participante de 2PC), los puntos muertos distribuidos (globales), los puntos muertos que involucran a dos o más participantes en 2PC, se resuelven automáticamente de la siguiente manera:
Cuando SS2PL se utiliza eficazmente en un entorno distribuido, los puntos muertos globales debidos al bloqueo generan puntos muertos de votación en 2PC y se resuelven automáticamente mediante 2PC (consulte Orden de compromiso (CO), en Caracterización exacta de los puntos muertos de votación por ciclos globales ; Sin referencia excepto que se sabe que los artículos de CO notan esto). Para el caso general de 2PL, los interbloqueos globales se resuelven de manera similar automáticamente 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 "votando" (notificando el final de la fase 1 local) y propagándose al 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 en conflicto en 2PL no puede ocurrir antes del punto de sincronización final de la fase 1, con el mismo punto muerto de votación resultante en el caso de un punto muerto de acceso a datos global; el punto muerto de votación (que también es un punto muerto global basado en bloqueo) se resuelve automáticamente mediante el protocolo que aborta alguna transacción involucrada, con un voto faltante, generalmente usando un tiempo de espera ).
Comentario :
- Cuando los datos se dividen entre los participantes del protocolo de compromiso atómico (por ejemplo, 2PC), la resolución automática de interbloqueo global se ha pasado por alto en la literatura de investigación de bases de datos, aunque los interbloqueos en tales sistemas ha 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 se ha notado solo en los artículos de CO. Sin embargo, se ha observado en la práctica que en muchos casos los interbloqueos globales son detectados con muy poca frecuencia por los mecanismos de resolución dedicados, menos de lo que podría esperarse ("¿Por qué vemos tan pocos interbloqueos globales?"). La razón es probablemente los puntos muertos que se resuelven automáticamente y, por lo tanto, no son manejados ni contabilizados por los mecanismos;
- Para 2PL en general, la resolución automática mediante el protocolo de punto de sincronización de final de fase uno (obligatorio) (que tiene el mismo mecanismo de votación que el protocolo de compromiso atómico y el mismo manejo de votos faltantes en el punto muerto de la votación, lo que resulta en una resolución de punto muerto global). no se ha mencionado hasta hoy (2009). Prácticamente solo se utiliza el caso especial SS2PL, donde no se necesita sincronización de final de fase uno además del protocolo de compromiso atómico.
- En un entorno distribuido donde los datos recuperables no están divididos entre los participantes del protocolo de compromiso atómico, no existe tal resolución automática y los puntos muertos distribuidos deben resolverse mediante técnicas dedicadas.
Ver también
- Serializabilidad
- Lock (informática)
Referencias
- ^ a b Philip A. Bernstein , Vassos Hadzilacos, Nathan Goodman (1987): Control de concurrencia y recuperación en sistemas de bases de datos , Addison Wesley Publishing Company, ISBN 0-201-10715-5
- ^ Gerhard Weikum , Gottfried Vossen (2001): Sistemas de información transaccional , Elsevier, ISBN 1-55860-508-8
- ^ Yuri Breitbart, Dimitrios Georgakopoulos, Marek Rusinkiewicz, Abraham Silberschatz (1991): "Sobre la programación rigurosa de transacciones" , IEEE Transactions on Software Engineering (TSE), septiembre de 1991, volumen 17, número 9, págs. 954-960, ISSN 0098-5589
- ^ Yoav Raz (1992): "El principio de orden de compromiso o garantía de serialización en un entorno heterogéneo de administradores de recursos autónomos múltiples que utilizan compromiso atómico" Archivado 2007-05-23 en Wayback Machine ( PDF ), Actas de la Decimoctava Conferencia Internacional on Very Large Data Bases (VLDB), págs. 292-312, Vancouver, Canadá, agosto de 1992, ISBN 1-55860-151-1 (también DEC-TR 841, Digital Equipment Corporation , noviembre de 1990)
- ^ Yoav Raz (1991): "Bloqueo de pedidos de compromiso estricto o cómo mejorar la simultaneidad en el bloqueo de administradores de recursos", DEC-TR 844, diciembre de 1991.
- ^ Principios del procesamiento de transacciones; ISBN 9780080948416 ; Capítulo 6 Página 152