El pedido de compromiso ( CO ) es una clase de técnicas de serialización interoperables en el control de concurrencia de bases de datos , procesamiento de transacciones y aplicaciones relacionadas. Permite implementaciones optimistas (sin bloqueo). Con la proliferación de procesadores de múltiples núcleos , el CO también se ha utilizado cada vez más en la programación concurrente , la memoria transaccional y la memoria transaccional de software (STM) para lograr la serialización de manera optimista . CO es también el nombre del programa de transacciones resultante.(historia) propiedad, definida en 1988 con el nombre de atomicidad dinámica . [1] En un cronograma que cumple con la CO, el orden cronológico de los eventos de compromiso de las transacciones es compatible con el orden de precedencia de las transacciones respectivas. CO es un caso especial amplio de serializabilidad de conflictos y medios efectivos ( confiables , de alto rendimiento, distribuidos y escalables ) para lograr serializabilidad global (serializabilidad modular) en cualquier colección de sistemas de bases de datos que posiblemente utilicen diferentes mecanismos de control de concurrencia (CO también hace que cada compatible con la serialización del sistema, si aún no lo ha hecho).
Cada sistema de base de datos que no cumple con CO se aumenta con un componente de CO (el coordinador de órdenes de compromiso, COCO) que ordena los eventos de compromiso para el cumplimiento de CO, sin acceso a datos ni ninguna otra interferencia de operación de transacción. Como tal, CO proporciona una solución general de bajo costo para la serialización global (y serializabilidad distribuida), instrumental para el control de concurrencia global (y control de concurrencia distribuida ) de sistemas de bases de datos múltiples y otros objetos transaccionales , posiblemente altamente distribuidos (por ejemplo, dentro de la computación en la nube). , grid computing y redes de teléfonos inteligentes ). Un protocolo de compromiso atómico (ACP; de cualquier tipo) es una parte fundamental de la solución, que se utiliza para romper los ciclos globales en el gráfico de conflicto (precedencia, serializabilidad). CO es la propiedad más general (una condición necesaria ) que garantiza la serialización global, si los sistemas de base de datos involucrados no comparten información de control de concurrencia más allá de los mensajes del protocolo de compromiso atómico (sin modificar) y no tienen conocimiento de si las transacciones son globales o locales (los sistemas de base de datos son autónomos ). Por tanto, CO (con sus variantes) es la única técnica general que no requiere la distribución típicamente costosa de información de control de concurrencia local (por ejemplo, relaciones de precedencia local, bloqueos, marcas de tiempo o tickets). Generaliza la propiedad popular de bloqueo estricto de dos fases (SS2PL), que junto con el protocolo de confirmación de dos fases (2PC), es el estándar de facto para lograr la serialización global en los sistemas de bases de datos (basados en SS2PL). Como resultado, los sistemas de bases de datos compatibles con CO (con cualquier tipo de control de concurrencia diferente) pueden unirse de manera transparente a tales soluciones basadas en SS2PL para la serialización global.
Además, los interbloqueos globales basados en el bloqueo se resuelven automáticamente en un entorno de bases de datos múltiples basado en CO, un beneficio secundario vital (incluido el caso especial de un entorno completamente basado en SS2PL; un hecho previamente desapercibido para SS2PL).
Además, el orden de compromiso estricto (SCO; Raz 1991c ), la intersección de Strictness y CO, proporciona un mejor rendimiento (tiempo promedio de finalización de la transacción más corto y resulta en un mejor rendimiento de la transacción ) que SS2PL siempre que haya conflictos de lectura-escritura (comportamiento de bloqueo idéntico para escritura). -conflictos de lectura y escritura-escritura; sobrecarga de bloqueo comparable). La ventaja de SCO es especialmente durante la contención de bloqueo. El rigor permite que tanto SS2PL como SCO utilicen los mismos mecanismos efectivos de recuperación de bases de datos .
Existen dos variantes generalizantes principales de CO, CO extendido (ECO; Raz 1993a ) y CO de múltiples versiones (MVCO; Raz 1993b ). También proporcionan serialización global sin distribución de información de control de concurrencia local, se pueden combinar con cualquier control de concurrencia relevante y permiten implementaciones optimistas (sin bloqueo). Ambos utilizan información adicional para relajar las restricciones de CO y lograr una mejor simultaneidad y rendimiento. La ordenación de votos (VO o CO generalizado (GCO); Raz 2009 ) es un conjunto de programación de contenedores (propiedad) y una técnica para el CO y todas sus variantes. El VO local es necesario para garantizar la serialización global si los participantes del protocolo de compromiso atómico (ACP) no comparten información de control de concurrencia (tienen la propiedad de autonomía generalizada ). El CO y sus variantes interactúan de forma transparente, garantizando la serialización global y la resolución automática de interbloqueo global juntos en un entorno mixto y heterogéneo con diferentes variantes.
Descripción general
El ordenamiento Compromiso (CO; Raz 1990 , 1992 , 1994 , 2009 ) Propiedad horario se ha denominado también como dinámico atomicidad (desde 1988 [1] ), cometer pedido , cometer seriabilidad orden , y recuperabilidad fuerte (desde 1991). Este último es un nombre engañoso ya que el CO es incomparable con la recuperabilidad , y el término "fuerte" implica un caso especial. Esto significa que una propiedad de recuperabilidad sustancial no necesariamente tiene la propiedad de CO y viceversa.
En 2009, CO se ha caracterizado como un método de control de concurrencia importante, junto con los tres métodos principales previamente conocidos (desde la década de 1980): bloqueo , orden de marca de tiempo y prueba de gráficos de serialización , y como un habilitador para la interoperabilidad de sistemas que utilizan diferentes Mecanismos de control de concurrencia. [2]
En un sistema de base de datos federada o en cualquier otro sistema de base de datos múltiple más vagamente definido, que normalmente se distribuyen en una red de comunicación, las transacciones abarcan múltiples bases de datos y posiblemente distribuidas . Hacer cumplir la serialización global en tal sistema es problemático. Incluso si cada programa local de una sola base de datos sigue siendo serializable, el programa global de un sistema completo no es necesariamente serializable. Los intercambios masivos de comunicación de información sobre conflictos necesarios entre bases de datos para alcanzar la serialización de conflictos conducirían a un rendimiento inaceptable, principalmente debido a la latencia de la computadora y la comunicación . El problema de lograr la serialización global de manera efectiva se había caracterizado como abierto hasta la divulgación pública de CO en 1991 por su inventor Yoav Raz ( Raz 1991a ; ver también Serialización global ).
Hacer cumplir el CO es una forma eficaz de hacer cumplir la serialización de conflictos a nivel mundial en un sistema distribuido, ya que hacer cumplir el CO localmente en cada base de datos (u otros objetos transaccionales) también lo hace a nivel mundial. Cada base de datos puede utilizar cualquier tipo de mecanismo de control de concurrencia, posiblemente diferente. Con un mecanismo local que ya proporciona serializabilidad de conflicto, hacer cumplir el CO localmente no causa ningún otro aborto, ya que hacer cumplir el CO localmente no afecta la estrategia de programación de acceso a datos del mecanismo (esta programación determina los abortos relacionados con la serialización; tal mecanismo normalmente no lo hace). considerar los eventos de compromiso o su orden). La solución de CO no requiere gastos generales de comunicación, ya que utiliza solo mensajes de protocolo de compromiso atómico (sin modificar) , que ya necesita cada transacción distribuida para alcanzar la atomicidad. Un protocolo de compromiso atómico juega un papel central en el algoritmo de CO distribuido, que aplica el CO de forma global al romper los ciclos globales (ciclos que abarcan dos o más bases de datos) en el gráfico de conflicto global. El CO, sus casos especiales y sus generalizaciones son interoperables y logran serializabilidad global mientras se utilizan juntos de manera transparente en un único entorno distribuido heterogéneo que comprende objetos con posiblemente diferentes mecanismos de control de concurrencia. Como tal, el pedido de compromiso , incluidos sus casos especiales, y junto con sus generalizaciones (ver variantes de CO a continuación), proporciona una solución general, de alto rendimiento y completamente distribuida (no se necesita un componente de procesamiento central o una estructura de datos central) para garantizar la serialización global en entornos heterogéneos de sistemas de bases de datos múltiples y otros objetos transaccionales múltiples (objetos con estados accedidos y modificados solo por transacciones; por ejemplo, en el marco de procesos transaccionales y dentro de la computación en la nube y la computación en red). La solución de CO se amplía con el tamaño de la red y la cantidad de bases de datos sin ningún impacto negativo en el rendimiento (asumiendo que las estadísticas de una sola transacción distribuida, por ejemplo, la cantidad promedio de bases de datos involucradas en una sola transacción, no cambian).
Con la proliferación de procesadores multinúcleo , Optimistic CO (OCO) también se ha utilizado cada vez más para lograr la serialización en la memoria transaccional de software, y ya se han publicado numerosos artículos y patentes de STM que utilizan "orden de confirmación" (p. Ej., Zhang et al. 2006 [3] ).
La solución de pedidos de compromiso para la serialización global
Caracterización general del CO
El pedido de compromiso (CO) es un caso especial de serialización de conflictos. El CO se puede hacer cumplir con mecanismos de no bloqueo (cada transacción puede completar su tarea sin que se bloquee el acceso a los datos, lo que permite un control optimista de la concurrencia ; sin embargo, el compromiso podría bloquearse). En un calendario de CO, los eventos de compromiso ( parcial ) orden de precedencia de las operaciones corresponden a la precedencia orden (parcial) de las respectivas operaciones en el ( dirigida gráfico conflicto) (grafo de precedencia, gráfico de serialización), como inducida por su acceso en conflicto operaciones (generalmente operaciones de lectura y escritura (insertar / modificar / eliminar); CO también se aplica a operaciones de nivel superior, donde están en conflicto si no son conmutativas , así como a conflictos entre operaciones sobre datos de múltiples versiones).
- Definición: orden de compromiso
- Dejar ser dos transacciones comprometidas en un cronograma, de modo que está en conflicto con ( precede). El cronograma tiene la propiedad Orden de compromiso (CO), si por cada dos transacciones se compromete antes se compromete.
Los eventos de decisión de compromiso son generados por un mecanismo de compromiso local o un protocolo de compromiso atómico si diferentes procesos necesitan llegar a un consenso sobre si comprometerse o abortar. El protocolo puede estar distribuido o centralizado. Las transacciones se pueden confirmar simultáneamente si la orden de confirmación parcial lo permite (si no tienen operaciones en conflicto). Suponga que diferentes operaciones en conflicto inducen diferentes órdenes parciales de las mismas transacciones. En ese caso, el gráfico de conflictos tiene ciclos y el programa violará la serialización cuando se confirmen todas las transacciones de un ciclo. En este caso, no se puede encontrar un pedido parcial para los eventos de compromiso. Por lo tanto, los ciclos en el gráfico de conflictos deben romperse abortando transacciones. Sin embargo, cualquier programa serializable de conflicto se puede convertir en CO sin abortar ninguna transacción retrasando adecuadamente los eventos de confirmación para cumplir con el orden parcial de precedencia de las transacciones.
La aplicación de CO por sí sola no es suficiente como mecanismo de control de concurrencia, ya que CO carece de la propiedad de recuperabilidad, que también debería ser compatible.
El algoritmo de CO distribuido
Existe un algoritmo de ejecución de órdenes de compromiso global completamente distribuido que utiliza el CO local de cada base de datos participante y solo necesita mensajes de protocolo de compromiso Atómico (sin modificar) sin más comunicación. El algoritmo distribuido es la combinación de procesos de algoritmo de CO locales (para cada base de datos) y un protocolo de compromiso atómico (que se puede distribuir por completo). El protocolo de compromiso atómico es fundamental para hacer cumplir la atomicidad de cada transacción distribuida (para decidir si comprometerla o abortarla; este procedimiento siempre se lleva a cabo para transacciones distribuidas, independientemente del control de concurrencia y CO). Un ejemplo común de un protocolo de compromiso atómico es el protocolo de compromiso de dos fases , que es resistente a muchos tipos de fallas del sistema. En un entorno confiable, o cuando los procesos generalmente fallan juntos (por ejemplo, en el mismo circuito integrado ), se puede usar un protocolo más simple para el compromiso atómico (por ejemplo, un simple apretón de manos de los procesos participantes de transacciones distribuidas con algún participante especial arbitrario pero conocido, el coordinador de la transacción, es decir, un tipo de protocolo de compromiso de una fase ). Un protocolo de compromiso atómico llega a un consenso entre los participantes sobre si realizar o abortar una transacción distribuida (global) que abarca a estos participantes. Una etapa esencial en cada uno de estos protocolos es el voto SÍ (ya sea explícito o implícito) de cada participante, lo que significa una obligación del participante votante de obedecer la decisión del protocolo, ya sea para comprometerse o abortar. De lo contrario, un participante puede abortar unilateralmente la transacción con un voto NO explícito. El protocolo compromete la transacción solo si se han recibido votos SÍ de todos los participantes (por lo tanto, un voto faltante generalmente se considera un NO). De lo contrario, el protocolo aborta la transacción. Los diversos protocolos de compromiso atómico solo difieren en sus capacidades para manejar diferentes situaciones de falla del entorno informático y la cantidad de trabajo y otros recursos informáticos necesarios en diferentes situaciones.
Toda la solución de CO para la serialización global se basa en el hecho de que el protocolo de compromiso atómico eventualmente aborta esta transacción en caso de que falte un voto para una transacción distribuida.
Hacer cumplir el CO global
En cada sistema de base de datos, un algoritmo de CO local determina el orden de compromiso necesario para esa base de datos. Según la caracterización de CO anterior, este orden depende del orden de precedencia local de las transacciones, que resulta de los mecanismos de programación de acceso a datos locales. En consecuencia, los votos SÍ en el protocolo de compromiso atómico se programan para cada transacción distribuida (no interrumpida) (en lo que sigue, "un voto" significa un voto SÍ). Suponga que existe una relación de precedencia (conflicto) entre dos transacciones. En ese caso, el segundo no se votará antes de que se complete el primero (ya sea confirmado o abortado), para evitar una posible violación de la orden de compromiso por parte del protocolo de compromiso atómico. Esto puede suceder ya que el orden de compromiso por el protocolo no es necesariamente el mismo que el orden de votación. Si no existe una relación de precedencia, ambos pueden votarse al mismo tiempo. Esta estrategia de ordenamiento de votos asegura que también el protocolo de compromiso atómico mantiene el orden de compromiso, y es una condición necesaria para garantizar el CO global (y el CO local de una base de datos; sin él tanto el CO global como el CO local (una propiedad que significa que cada base de datos es Compatible con CO) puede ser violado).
Sin embargo, dado que los sistemas de bases de datos programan sus transacciones de forma independiente, es posible que las órdenes de precedencia de las transacciones en dos bases de datos o más no sean compatibles (no existe ninguna orden parcial global que pueda integrar las respectivas órdenes parciales locales juntas). Con CO, las órdenes de precedencia también son las órdenes de compromiso. Cuando las bases de datos que participan en la misma transacción distribuida no tienen órdenes de precedencia local compatibles para esa transacción (sin "saberlo"; por lo general, no existe coordinación entre los sistemas de bases de datos en los conflictos, ya que la comunicación necesaria es masiva y degrada el rendimiento de manera inaceptable) significa que el la transacción reside en un ciclo global (que involucra dos o más bases de datos) en el gráfico de conflicto global. En este caso, el protocolo de compromiso atómico no recopilará todos los votos necesarios para cometer esa transacción: según la estrategia de ordenación de votos anterior, al menos una base de datos retrasará su voto para esa transacción indefinidamente para cumplir con su propia orden de compromiso (precedencia). , ya que estará esperando la finalización de otra, transacciones anteriores en ese ciclo global retrasadas indefinidamente por otra base de datos con un orden diferente. Esto significa una situación de bloqueo de la votación que involucra a las bases de datos en ese ciclo. Como resultado, el protocolo eventualmente abortará alguna transacción bloqueada en este ciclo global, ya que a cada transacción le falta al menos el voto de un participante. La selección de la transacción específica en el ciclo que se cancelará depende de las políticas de aborto del protocolo de compromiso atómico (un mecanismo de tiempo de espera es común, pero puede resultar en más de un aborto necesario por ciclo; tanto la prevención de abortos innecesarios como el acortamiento del tiempo de aborto se pueden lograr por un mecanismo de aborto dedicado para CO). Tal aborto romperá el ciclo global que involucra esa transacción distribuida. Tanto las transacciones bloqueadas como posiblemente otras en conflicto con las bloqueadas (y por lo tanto bloqueadas) serán libres de votación. Vale la pena señalar que cada base de datos involucrada con el punto muerto de votación continúa votando regularmente sobre transacciones que no están en conflicto con su transacción en punto muerto, generalmente casi todas las transacciones pendientes. Así, en el caso de órdenes de compromiso locales (parciales) incompatibles, no es necesaria ninguna acción ya que el protocolo de compromiso atómico lo resuelve automáticamente al abortar una transacción que es causa de incompatibilidad. Esto significa que la estrategia de ordenamiento de votos anterior también es una condición suficiente para garantizar Global CO.
Se concluye lo siguiente:
- La estrategia de ordenamiento de votos para el teorema global de aplicación de CO
- Dejar Ser transacciones indecisas (ni comprometidas ni abortadas) en un sistema de base de datos que impone el CO para transacciones locales, de manera que es global y está en conflicto con ( precede). Entonces, teniendo terminó (ya sea comprometido o abortado) antes se vota para comprometerse (la estrategia de ordenamiento de votos ), en cada uno de estos sistemas de base de datos en un entorno de bases de datos múltiples, es una condición necesaria y suficiente para garantizar Global CO (la condición garantiza Global CO, que puede ser violada sin ella).
- Comentarios:
- La estrategia de ordenamiento de votos que hace cumplir el CO global se conoce comoen ( Raz 1992 ).
- La propiedad de CO local de una programación global significa que cada base de datos cumple con los requisitos de CO. De la discusión sobre la necesidad, la parte anterior se sigue directamente que el teorema también es cierto cuando se reemplaza "CO global" por "CO local" cuando hay transacciones globales. Juntos, significa que el CO global está garantizado si y solo si se garantiza el CO local (lo cual no es cierto para la serialización de conflictos globales y la serialización de conflictos locales: Global implica Local, pero no al revés).
El CO global implica la serialización global.
El algoritmo de CO global comprende hacer cumplir CO (local) en cada sistema de base de datos participante ordenando confirmaciones de transacciones locales (consulte Aplicación de CO localmente a continuación) y haciendo cumplir la estrategia de ordenación de votos en el teorema anterior (para transacciones globales).
La caracterización exacta de los bloqueos de votaciones por ciclos globales
El proceso de eliminación del ciclo global anterior mediante un punto muerto en la votación se puede explicar en detalle mediante la siguiente observación:
Primero, se asume, por simplicidad, que cada transacción alcanza el estado listo para confirmar y es votada por al menos una base de datos (esto implica que no ocurre ningún bloqueo por bloqueos). Defina un gráfico de "esperar voto para confirmar" como un gráfico dirigido con transacciones como nodos y un borde dirigido desde cualquier primera transacción a una segunda transacción si la primera transacción bloquea la votación para confirmar la segunda transacción (opuesta a la dirección del borde convencional en un gráfico de espera ). Tal bloqueo ocurre solo si la segunda transacción entra en conflicto con la primera transacción (ver arriba). Por lo tanto, este gráfico de "esperar voto para comprometerse" es idéntico al gráfico de conflicto global. Un ciclo en el gráfico "esperar voto para comprometerse" significa un punto muerto en la votación. Por lo tanto, hay un punto muerto en la votación si hay un ciclo en el gráfico de conflictos. Los mecanismos de serialización local eliminan los ciclos locales (confinados a una sola base de datos). En consecuencia, solo quedan ciclos globales, que luego son eliminados por el protocolo de compromiso atómico cuando aborta transacciones en punto muerto con votos respectivos faltantes (bloqueados).
En segundo lugar, también se tratan las confirmaciones locales: tenga en cuenta que al hacer cumplir el CO, también esperar una confirmación local regular de una transacción local puede bloquear las confirmaciones locales y los votos de otras transacciones en caso de conflicto, y la situación de las transacciones globales no cambia sin el Supuesto simplificador anterior: El resultado final es el mismo también con un compromiso local para las transacciones locales, sin votar en el compromiso atómico por ellas.
Finalmente, se debe considerar el bloqueo mediante un bloqueo (que ha sido excluido hasta ahora): un bloqueo bloquea una operación conflictiva y evita que se materialice un conflicto. Suponga que el bloqueo se libera solo después de que finaliza la transacción. En ese caso, puede bloquear indirectamente un voto o un compromiso local de otra transacción (que ahora no puede llegar al estado listo), con el mismo efecto que un bloqueo directo de un voto o un compromiso local. Un ciclo se genera en el gráfico de conflicto solo si dicho bloqueo por un candado también está representado por un borde. Con tales bordes agregados que representan eventos de bloqueo por bloqueo, el gráfico de conflicto se está convirtiendo en un gráfico de conflicto aumentado .
- Definición: gráfico de conflicto aumentado
- Un gráfico de conflicto aumentado es un gráfico de conflicto con bordes añadidos: además de los bordes originales, existe un borde dirigido de la transacción a la transacción si se cumplen dos condiciones:
- está bloqueado por un bloqueo de acceso a datos aplicado por (el bloqueo evita el conflicto de con de materializarse y tener una ventaja en el gráfico de conflicto regular), y
- Este bloqueo no se detendrá antes termina (confirma o aborta; verdadero para cualquier CO basado en bloqueo)
- El gráfico también se puede definir como la unión del gráfico de conflicto (regular) con el gráfico de espera (de borde inverso, regular)
- Comentarios:
- Aquí, a diferencia del gráfico de conflictos regular, que tiene bordes solo para conflictos materializados, todos los conflictos materializados y no materializados están representados por bordes.
- Tenga en cuenta que todos los bordes nuevos son todos los bordes (invertidos a los convencionales) del gráfico de espera . El gráfico de espera también se puede definir como el gráfico de conflictos no materializados. Según las convenciones comunes, la dirección del borde en un gráfico de conflicto define el orden de tiempo entre operaciones en conflicto, que es opuesto al orden de tiempo definido por un borde en un gráfico de espera .
- Tenga en cuenta que dicho gráfico global contiene (tiene incrustados) todos los gráficos de espera locales regulares (borde inverso) y también puede incluir ciclos globales basados en bloqueo (que no pueden existir en los gráficos locales). Por ejemplo, si todas las bases de datos en un ciclo global están basadas en SS2PL, entonces todas las situaciones de bloqueo de votos relacionadas son causadas por bloqueos (esta es la clásica y probablemente la única situación global de interbloqueo tratado en la literatura de investigación de bases de datos). Este es un caso de interbloqueo global en el que cada base de datos relacionada crea una parte del ciclo, pero el ciclo completo no reside en ningún gráfico de espera local.
En presencia de CO, el gráfico de conflicto aumentado es, de hecho, un gráfico de espera de votación y compromiso local (borde inverso) : existe un borde desde una primera transacción, ya sea local o global, a una segunda, si la segunda está esperando que termine el primero para ser votado (si es global) o comprometido localmente (si es local). Todos los ciclos globales (en dos o más bases de datos) en este gráfico generan puntos muertos de votación. Los ciclos globales del gráfico proporcionan una caracterización completa de los puntos muertos de la votación y pueden incluir cualquier combinación de conflictos materializados y no materializados. Solo los ciclos de (solo) conflictos materializados son también ciclos del gráfico de conflicto regular y afectan la serialización. Uno o más conflictos no materializados (relacionados con el bloqueo) en un ciclo impiden que sea un ciclo en el gráfico de conflicto normal y lo convierten en un punto muerto relacionado con el bloqueo. Todos los ciclos globales (votaciones-interbloqueo) deben romperse (resolverse) tanto para mantener la serialización global como para resolver los interbloqueos globales que implican el bloqueo del acceso a datos. De hecho, todos están rotos por el protocolo de compromiso atómico debido a la falta de votos en un punto muerto de votación.
Comentario: Esta observación también explica la corrección de Extended CO (ECO) a continuación: El orden de votación de las transacciones globales debe seguir el orden del gráfico de conflictos con bloqueo de votos cuando existe una relación de orden (ruta del gráfico) entre dos transacciones globales. Las transacciones locales no se votan y sus confirmaciones (locales) no se bloquean en caso de conflicto. Esto da como resultado las mismas situaciones de bloqueo de la votación y el proceso de eliminación del ciclo global resultante para ECO.
La situación de bloqueo de la votación se puede resumir de la siguiente manera:
- El teorema del punto muerto en las votaciones de CO
- Deje que un entorno de base de datos múltiple comprenda sistemas de base de datos compatibles con CO (que eliminan los ciclos locales ) que hacen cumplir cada CO global (utilizando la condición del teorema anterior). Se produce un punto muerto en la votación si y solo si existe un ciclo global (abarca dos o más bases de datos) en el gráfico de conflicto global aumentado (también el bloqueo mediante un bloqueo de acceso a datos está representado por un borde). Suponga que el ciclo no se rompe por ningún aborto. En ese caso, todas las transacciones globales en él están involucradas con el respectivo punto muerto de votación. Eventualmente, cada uno tiene su voto bloqueado (ya sea directa o indirectamente por un bloqueo de acceso a datos); si una transacción local reside en el ciclo, eventualmente, tiene su compromiso (local) bloqueado.
- Comentario: Puede ocurrir una situación poco común de un punto muerto en la votación (por falta de votos bloqueados), sin que ninguno de los sistemas de base de datos involucrados en estas transacciones vote por ninguna transacción en el ciclo relacionado. Esto puede ocurrir cuando las subtransacciones locales son multiproceso . La instancia de mayor probabilidad de un evento tan raro involucra dos transacciones en dos ciclos opuestos simultáneos. Estos ciclos globales (puntos muertos) se superponen con los ciclos locales que se resuelven localmente y normalmente se resuelven mediante mecanismos locales sin implicar un compromiso atómico. Formalmente también es un ciclo global, pero prácticamente es local (porciones de ciclos locales generan uno global; para ver esto, divida cada transacción global (nodo) en subtransacciones locales (sus porciones confinadas cada una a una sola base de datos); existe una ventaja dirigida entre transacciones si existe una ventaja entre cualquier subtransacción local respectiva; un ciclo es local si todas sus aristas se originan a partir de un ciclo entre subtransacciones de la misma base de datos, y global si no; global y local pueden superponerse: el mismo ciclo entre transacciones puede resultar de varios ciclos diferentes entre subtransacciones, y ser tanto locales como globales).
Además, se concluye el siguiente caso especial basado en bloqueo:
- El teorema del interbloqueo global basado en el bloqueo de CO
- En un sistema de base de datos múltiple compatible con CO, un interbloqueo global basado en bloqueo, que implica al menos un bloqueo de acceso a datos (conflicto no materializado) y dos o más sistemas de base de datos, es un reflejo de un ciclo global en el gráfico de conflicto global aumentado , lo que da como resultado un punto muerto en la votación. Tal ciclo no es un ciclo en el gráfico de conflicto global (regular) (que refleja solo conflictos materializados, por lo que tal ciclo no afecta la serialización ).
- Comentarios:
- Cualquier bloqueo (borde) en el ciclo que no sea por un bloqueo de acceso a datos bloquea directamente la votación o el compromiso local. Todos los puntos muertos de votación se resuelven (casi todos por compromiso de Atomic ; consulte el comentario anterior), incluido este tipo basado en bloqueo.
- Los interbloqueos globales basados en bloqueos también se pueden generar en un entorno distribuido completamente basado en SS2PL (caso especial de basado en CO). Todo el bloqueo de votos (y los puntos muertos de votación) son causados por bloqueos de acceso a datos. Muchos artículos de investigación se han ocupado durante años de la resolución de estos puntos muertos globales, pero ninguno (excepto los artículos de CO) se conoce (a partir de 2009) para notar que el compromiso atómico los resuelve automáticamente. Estas resoluciones automáticas pasan desapercibidas con regularidad en todos los sistemas de bases de datos múltiples basados en SS2PL, a menudo sin pasar por los mecanismos de resolución dedicados.
Los puntos muertos de votación son la clave para el funcionamiento del CO distribuido.
La eliminación del ciclo global (en este caso, la resolución del punto muerto de la votación por compromiso atómico ) y las re-ejecuciones de transacciones abortadas resultantes requieren mucho tiempo, independientemente del control de concurrencia utilizado. Si las bases de datos programan transacciones de forma independiente, los ciclos globales son inevitables (en una completa analogía con los ciclos / interbloqueos generados en SS2PL local; con la distribución, cualquier coordinación de programación de transacciones u operaciones da como resultado una violación de la autonomía y, por lo general, una penalización sustancial del rendimiento). Sin embargo, su probabilidad puede reducirse en muchos casos mediante la implementación de pautas de diseño de transacciones y bases de datos que reducen el número de conflictos que involucran una transacción global. Esto, principalmente mediante el manejo adecuado de los puntos calientes (objetos de la base de datos con acceso frecuente) y evitando conflictos mediante el uso de conmutatividad cuando sea posible (por ejemplo, cuando se utilizan contadores de forma extensiva, como en las finanzas, y especialmente contadores de acumulación de transacciones múltiples , que suelen ser puntos calientes). .
Los protocolos de compromiso atómico están pensados y diseñados para lograr la atomicidad sin considerar el control de concurrencia de la base de datos. Abortan al detectar o encontrar heurísticamente (p. Ej., Por un tiempo de espera; a veces por error, innecesariamente) votos faltantes y, por lo general, desconocen los ciclos globales. Estos protocolos se pueden mejorar especialmente para CO (incluidas las variantes de CO a continuación) para evitar abortos innecesarios y acelerar los abortos utilizados para romper los ciclos globales en el gráfico de conflicto global aumentado (para un mejor rendimiento mediante una versión anterior al final de la transacción de los recursos informáticos y los datos normalmente bloqueados ). Por ejemplo, los métodos de detección de interbloqueo globales basados en bloqueo existentes, distintos del tiempo de espera, se pueden generalizar también para considerar el compromiso local y el bloqueo directo de votos, además del bloqueo de acceso a datos. Un posible compromiso en tales mecanismos es detectar y romper de manera efectiva los ciclos globales de longitud 2 más frecuentes y relativamente simples de manejar, y usar el tiempo de espera para ciclos más largos, mucho menos frecuentes y no detectados.
Hacer cumplir el CO a nivel local
El orden de compromiso se puede hacer cumplir localmente (en una sola base de datos) mediante un algoritmo de CO dedicado, o mediante cualquier algoritmo / protocolo que proporcione un caso especial de CO. Un protocolo importante de este tipo, que se utiliza ampliamente en los sistemas de bases de datos, que genera un programa de CO, es el fuerte y estricto protocolo de bloqueo de dos fases (SS2PL: "liberar los bloqueos de la transacción solo después de que la transacción se haya confirmado o abortado"; ver más abajo). SS2PL es un subconjunto adecuado de la intersección de 2PL y rigor.
Un algoritmo de CO local genérico
Un algoritmo de CO local genérico ( Raz 1992 ; Algoritmo 4.1) es un algoritmo independiente de los detalles de implementación que aplica exactamente la propiedad de CO. No bloquea el acceso a los datos (sin bloqueo) y consiste en abortar un determinado conjunto de transacciones (solo si es necesario) al realizar una transacción. Anula un conjunto mínimo (determinado de forma única en un momento dado) de otras transacciones indecisas (ni comprometidas ni abortadas) que se ejecutan localmente y pueden causar una violación de serialización en el futuro (puede generar posteriormente ciclos de transacciones comprometidas en el gráfico de conflicto; esto es el conjunto ABORT de una transacción comprometida T; después de confirmar T, no se puede confirmar ninguna transacción en ABORT en el momento de la confirmación, y todas están condenadas a ser abortadas). Este conjunto consta de todas las transacciones indecisas con bordes dirigidos en el gráfico de conflicto a la transacción comprometida. El tamaño de este conjunto no puede aumentar cuando la transacción está esperando ser confirmada (en el estado listo: el procesamiento ha finalizado) y, por lo general, disminuye con el tiempo a medida que se deciden sus transacciones. Por lo tanto, a menos que existan restricciones en tiempo real para completar esa transacción, es preferible esperar con la confirmación de esa transacción y dejar que este conjunto disminuya de tamaño. Si existe otro mecanismo de serialización localmente (que elimina ciclos en el gráfico de conflicto local), o si no existe ningún ciclo que involucre esa transacción, el conjunto estará vacío eventualmente y no es necesario cancelar un miembro del conjunto. De lo contrario, el conjunto se estabilizará con transacciones en ciclos locales, y será necesario anular los miembros del conjunto para romper los ciclos. Dado que en el caso de los conflictos de CO generan bloqueos en la confirmación, los ciclos locales en el gráfico de conflictos de aumentos (ver arriba) indican puntos muertos de compromiso locales, y se pueden usar técnicas de resolución de puntos muertos como en SS2PL (por ejemplo, como tiempo de espera y gráfico de espera ) . Un ciclo local en el gráfico de conflicto aumentado con al menos un conflicto no materializado refleja un punto muerto basado en bloqueo. El algoritmo local anterior, aplicado al gráfico de conflicto local aumentado en lugar del gráfico de conflicto local regular, comprende el algoritmo de CO local mejorado genérico , un mecanismo de eliminación de ciclo local único, tanto para garantizar la serialización local como para manejar los interbloqueos locales basados en el bloqueo. Prácticamente siempre se utiliza un mecanismo de control de concurrencia adicional, incluso únicamente para hacer cumplir la recuperabilidad. El algoritmo CO genérico no afecta la estrategia de programación de acceso a datos locales cuando se ejecuta junto con cualquier otro mecanismo de control de concurrencia local. Afecta solo a la orden de confirmación y, por esta razón, no es necesario abortar más transacciones de las necesarias para la prevención de violaciones de serialización mediante cualquier mecanismo de control de concurrencia local combinado. A lo sumo, el efecto neto de CO puede ser un retraso de los eventos de compromiso (o la votación en un entorno distribuido), para cumplir con la orden de compromiso necesaria (pero no más retraso que sus casos especiales, por ejemplo, SS2PL, y en promedio significativamente menos).
Se concluye el siguiente teorema:
- El teorema del algoritmo de CO local genérico
- Cuando se ejecuta solo o junto con cualquier mecanismo de control de concurrencia en un sistema de base de datos, entonces
- El algoritmo de CO local genérico garantiza CO (local) (un programa compatible con CO).
- El algoritmo de CO local mejorado genérico garantiza tanto el CO (local) como la resolución de interbloqueo basada en bloqueo (local). Y (cuando no se usa un tiempo de espera y no se aplican restricciones de finalización de transacciones en tiempo real ) ninguno de los algoritmos aborta más transacciones que el mínimo necesario (que está determinado por la programación de operaciones de las transacciones, fuera del alcance de los algoritmos).
Ejemplo: programación concurrente y memoria transaccional
- Consulte también Programación concurrente y Memoria transaccional.
Con la proliferación de procesadores de múltiples núcleos, las variantes del algoritmo de CO local genérico también se han utilizado cada vez más en la programación concurrente, la memoria transaccional y, especialmente, en la memoria transaccional de software para lograr la serialización de manera optimista mediante "orden de confirmación" (por ejemplo, Ramadan et al. 2009, [4] Zhang et al. 2006, [3] von Parun et al. 2007 [5] ). Ya se han publicado numerosos artículos y patentes relacionados que utilizan CO.
Consideraciones de implementación: El Coordinador de Órdenes de Compromiso (COCO)
Se asume un sistema de base de datos en un entorno de bases de datos múltiples. Desde el punto de vista de la arquitectura del software , un componente CO que implementa el algoritmo CO genérico localmente, el Coordinador de órdenes de compromiso (COCO), puede diseñarse directamente como un mediador entre un sistema de base de datos (único) y un componente de protocolo de compromiso atómico ( Raz 1991b). ). Sin embargo, el COCO suele ser una parte integral del sistema de base de datos. Las funciones del COCO son votar para comprometerse en transacciones globales listas (el procesamiento ha finalizado) de acuerdo con la orden de compromiso local, votar para abortar transacciones para las cuales el sistema de base de datos ha iniciado un aborto (el sistema de base de datos puede iniciar el aborto para cualquier transacción). , por muchas razones), y pasar la decisión de compromiso atómico al sistema de base de datos. Para las transacciones locales (cuando se puede identificar), no es necesario votar. Para determinar el orden de compromiso, el COCO mantiene una representación actualizada del gráfico de conflicto local (o gráfico de conflicto local aumentado para capturar también interbloqueos de bloqueo) de las transacciones indecisas (ni comprometidas ni abortadas) como una estructura de datos (por ejemplo, utilizando mecanismos similares a bloqueo para capturar conflictos, pero sin bloqueo de acceso a datos). El componente COCO tiene una interfaz con su sistema de base de datos para recibir notificaciones de "conflicto", "listo" (el procesamiento ha finalizado; disposición para votar en una transacción global o confirmar una local) y notificaciones de "aborto" del sistema de base de datos. También interactúa con el protocolo de compromiso atómico para votar y recibir la decisión del protocolo de compromiso atómico en cada transacción global. Las decisiones se envían desde el COCO al sistema de base de datos a través de su interfaz, así como las notificaciones de confirmación de transacciones locales, en un orden de confirmación adecuado. El COCO, incluidas sus interfaces, se puede mejorar si implementa otra variante de CO (ver más abajo) o juega un papel en el mecanismo de control de concurrencia de la base de datos más allá de votar en el compromiso atómico.
El COCO también garantiza CO localmente en un único sistema de base de datos aislado sin interfaz con un protocolo de compromiso atómico.
El CO es una condición necesaria para la serialización global en sistemas de bases de datos autónomos.
Suponga que las bases de datos que participan en transacciones distribuidas (es decir, transacciones que abarcan más de una sola base de datos) no usan ninguna información de control de concurrencia compartida y usan mensajes de protocolo de compromiso atómico sin modificar (para alcanzar la atomicidad). En ese caso, mantener el orden de compromiso (local) o una de sus variantes generalizadoras (ver más abajo) es una condición necesaria para garantizar la serialización global (se puede encontrar una técnica de prueba en ( Raz 1992 ), y un método de prueba diferente para esto en ( Raz 1993a )); también es una condición suficiente . Este es un hecho matemático derivado de las definiciones de serializabilidad y transacción . Significa que si no cumple con CO, la serialización global no se puede garantizar bajo esta condición (la condición de que no se comparta información de control de concurrencia local entre bases de datos más allá de los mensajes del protocolo de confirmación atómica). El compromiso atómico es un requisito mínimo para una transacción distribuida, ya que siempre es necesario, lo que está implícito en la definición de transacción.
( Raz 1992 ) define la autonomía e independencia de la base de datos como el cumplimiento de este requisito sin utilizar ningún conocimiento local adicional:
- Definición: sistema de base de datos autónomo (basado en control de concurrencia)
- Un sistema de base de datos es autónomo , si no comparte ninguna información de control de concurrencia más allá de los mensajes del protocolo de compromiso atómico sin modificar con cualquier otra entidad. Además, no utiliza para el control de concurrencia ninguna información local adicional más allá de los conflictos (la última oración no aparece explícitamente sino implícita en una discusión adicional en Raz 1992 ).
Usando esta definición, se concluye lo siguiente:
- El teorema de serialización global y de CO
- El cumplimiento de CO de cada sistema de base de datos autónomo (u objeto transaccional) en un entorno de bases de datos múltiples es una condición necesaria para garantizar la serialización global (sin CO, se puede violar la serialización global).
- El cumplimiento de CO con cada sistema de base de datos es una condición suficiente para garantizar la serialización global.
Sin embargo, la definición de autonomía anterior implica, por ejemplo, que las transacciones se programan de manera que las transacciones locales (confinadas a una sola base de datos) no puedan ser identificadas como tales por un sistema de base de datos autónomo. Esto es realista para algunos objetos transaccionales, pero demasiado restrictivo y menos realista para los sistemas de bases de datos de propósito general. Si se aumenta la autonomía con la capacidad de identificar transacciones locales, entonces el cumplimiento de una propiedad más general, el pedido de compromiso extendido (ECO, ver más abajo), convierte a ECO en la condición necesaria.
Solo en ( Raz 2009 ) la noción de autonomía generalizada captura la noción pretendida de autonomía:
- Definición: autonomía generalizada
- Un sistema de base de datos tiene la propiedad de autonomía generalizada si no comparte ningún otro sistema de base de datos ninguna información de concurrencia local más allá de los mensajes del protocolo de compromiso atómico (no modificado) (sin embargo, se puede utilizar cualquier información local).
Esta definición es probablemente la más amplia posible en el contexto del control de concurrencia de la base de datos, y hace que CO junto con cualquiera de sus variantes generalizadoras (útil: no hay distribución de información de control de concurrencia) (ordenamiento de votos (VO); ver variantes de CO a continuación) el condición necesaria para la serialización global (es decir, la unión de CO y sus variantes de generalización es el conjunto VO necesario, que también puede incluir nuevas variantes de generalización útiles desconocidas).
Resumen
La solución (técnica) de pedido de compromiso (CO) para la serialización global se puede resumir de la siguiente manera:
Si cada base de datos (o cualquier otro objeto transaccional ) en un entorno de bases de datos múltiples cumple con CO, es decir, organiza sus compromisos de transacciones locales y sus votos sobre transacciones (globales, distribuidas) al protocolo de compromiso atómico de acuerdo con el protocolo local (a la base de datos) orden parcial inducido por el gráfico de conflicto local (gráfico de serialización) para las transacciones respectivas, entonces se garantizan el CO global y la serialización global . El cumplimiento de CO de una base de datos se puede lograr de manera efectiva con cualquier mecanismo de control de concurrencia basado en serializabilidad de conflicto local , sin afectar el proceso de ejecución o programación de ninguna transacción ni interrumpirlo. Además, no se viola la autonomía de la base de datos. La única sobrecarga baja en la que se incurre es la detección de conflictos (por ejemplo, con el bloqueo, pero sin bloqueo de acceso a datos; si no se ha detectado ya para otros fines) y la ordenación de votos y transacciones locales de acuerdo con los conflictos.
En caso de órdenes parciales incompatibles de dos o más bases de datos (ningún orden parcial global puede incrustar las respectivas órdenes parciales locales juntas), se genera un ciclo global (abarca dos bases de datos o más) en el gráfico de conflicto global. Esto, junto con el CO, da como resultado un ciclo de votos bloqueados. Un voting- estancamiento se produce por las bases de datos sobre ese ciclo (sin embargo, permite el voto concurrente en cada base de datos, por lo general para casi todos los votos en circulación, continuará ejecutando). En este caso, el protocolo de compromiso atómico no recopila todos los votos necesarios para las transacciones bloqueadas en ese ciclo global. En consecuencia, el protocolo aborta algunas transacciones con un voto faltante. Esto rompe el ciclo global, se resuelve el punto muerto de la votación y los votos bloqueados relacionados pueden ejecutarse libremente. Romper el ciclo global en el gráfico de conflicto global asegura que se mantengan el CO global y la serialización global. Por lo tanto, en el caso de órdenes de compromiso locales (parciales) incompatibles, no es necesaria ninguna acción ya que el protocolo de compromiso atómico lo resuelve automáticamente al abortar una transacción que es causa de la incompatibilidad. Además, los puntos muertos globales debidos al bloqueo (ciclos globales en el gráfico de conflicto aumentado con al menos un bloqueo de acceso a datos) dan como resultado puntos muertos de votación y se resuelven automáticamente mediante el mismo mecanismo.
El CO local es una condición necesaria para garantizar la serialización global si las bases de datos involucradas no comparten ninguna información de control de concurrencia más allá de los mensajes del protocolo de compromiso atómico (no modificado), es decir, si las bases de datos son autónomas en el contexto del control de concurrencia. Esto significa que todas las soluciones de serialización global para bases de datos autónomas deben cumplir con CO. De lo contrario, se puede violar la serialización global (y, por lo tanto, es probable que se viole muy rápidamente en un entorno de alto rendimiento).
La solución de CO se escala con el tamaño de la red y la cantidad de bases de datos sin penalización del rendimiento cuando utiliza una arquitectura de compromiso atómico distribuida común .
Serializabilidad distribuida y CO
CO distribuido
Una característica distintiva de la solución CO para la serialización distribuida de otras técnicas es el hecho de que no requiere distribución de información de conflicto (por ejemplo, relaciones de precedencia local, bloqueos, marcas de tiempo , tickets), lo que la hace excepcionalmente eficaz. En su lugar, utiliza mensajes de protocolo de compromiso atómico (sin modificar) (que ya se utilizan).
Una forma común de lograr la serialización distribuida en un sistema (distribuido) es mediante un administrador de bloqueo distribuido (DLM). Los DLM, que comunican información de bloqueo (conflicto no materializado) en un entorno distribuido, suelen sufrir latencia informática y de comunicación , lo que reduce el rendimiento del sistema. CO permite lograr serializabilidad distribuida en condiciones muy generales, sin un administrador de bloqueo distribuido, exhibiendo los beneficios ya explorados anteriormente para entornos de bases de datos múltiples; en particular: confiabilidad, alto rendimiento, escalabilidad, la posibilidad de utilizar un control de concurrencia optimista cuando se desee, comunicaciones sin conflicto de información relacionadas con la red (que han incurrido en sobrecarga y retrasos) y resolución de interbloqueo distribuido automático.
Todos los sistemas transaccionales distribuidos se basan en algún protocolo de compromiso atómico para coordinar la atomicidad (ya sea para comprometerse o abortar) entre procesos en una transacción distribuida . Además, los datos típicamente recuperables (es decir, los datos bajo el control de las transacciones, por ejemplo, los datos de la base de datos; que no debe confundirse con la propiedad de recuperabilidad de una programación) tienen acceso directo a un único componente de administrador de datos transaccionales (también conocido como administrador de recursos ). que maneja subtransacciones locales (la porción de la transacción distribuida en una única ubicación, por ejemplo, un nodo de red), incluso si otras entidades del sistema distribuido acceden indirectamente a estos datos durante una transacción (es decir, el acceso indirecto requiere un acceso directo a través de un subtransacción local). Por lo tanto, los datos recuperables en un sistema transaccional distribuido generalmente se dividen entre los administradores de datos transaccionales. En tal sistema, estos administradores de datos transaccionales generalmente comprenden a los participantes en el protocolo de compromiso atómico del sistema. Si cada participante cumple con CO (p. Ej., Mediante el uso de SS2PL, o COCO, o una combinación; ver más arriba), entonces todo el sistema distribuido proporciona CO (según los teoremas anteriores; cada participante puede considerarse un objeto transaccional separado) y, por lo tanto, serializabilidad (distribuida). Además: cuando se utiliza CO junto con un protocolo de compromiso atómico, también se resuelven automáticamente los interbloqueos distribuidos (es decir, los interbloqueos que abarcan dos o más administradores de datos) provocados por el bloqueo de acceso a los datos. Así se concluye el siguiente corolario:
- El teorema de serialización distribuida basado en CO
- Deje que un sistema transaccional distribuido (por ejemplo, un sistema de base de datos distribuido ) comprenda administradores de datos transaccionales (también llamados administradores de recursos ) que administran todos los datos recuperables del sistema . Los gestores de datos cumplen tres condiciones:
- Partición de datos: los datos recuperables se dividen entre los administradores de datos, es decir, cada dato recuperable (elemento de datos) está controlado por un solo administrador de datos (por ejemplo, como es común en una arquitectura de nada compartido ; incluso copias del mismo dato bajo diferentes administradores de datos son físicamente distinto, replicado ).
- Participantes en el protocolo de compromiso atómico: Estos administradores de datos son los participantes en el protocolo de compromiso atómico del sistema para coordinar la atomicidad de las transacciones distribuidas.
- Cumplimiento de CO: Cada uno de estos administradores de datos es compatible con CO (o alguna variante de CO compatible; ver más abajo).
- Luego
- Todo el sistema distribuido garantiza (CO distribuido y) serializabilidad , y
- Los puntos muertos distribuidos basados en el acceso a datos (puntos muertos que involucran a dos o más administradores de datos con al menos un conflicto no materializado) se resuelven automáticamente.
- Además: que los administradores de datos sean compatibles con CO es una condición necesaria para la serialización (distribuida) en un sistema que cumpla las condiciones 1, 2 anteriores, cuando los administradores de datos son autónomos , es decir, no comparten información de control de concurrencia más allá de los mensajes no modificados del protocolo de compromiso atómico.
Este teorema también significa que cuando SS2PL (o cualquier otra variante de CO) se usa localmente en cada administrador de datos transaccionales, y cada administrador de datos tiene control exclusivo de sus datos, no se necesita un administrador de bloqueo distribuido (que a menudo se utiliza para hacer cumplir SS2PL distribuido) para SS2PL distribuido y serializabilidad. Es relevante para una amplia gama de aplicaciones transaccionales distribuidas, que pueden diseñarse fácilmente para cumplir con las condiciones del teorema.
CO optimista distribuido (DOCO)
Para implementar Distributed Optimistic CO (DOCO), el algoritmo de CO local genérico se utiliza en todos los participantes del protocolo de compromiso atómico en el sistema sin bloqueo de acceso a datos y, por lo tanto, sin interbloqueos locales. El teorema anterior tiene el siguiente corolario:
- El teorema del CO optimista distribuido (DOCO)
- Si se utiliza DOCO, entonces:
- No se producen interbloqueos locales y
- Los interbloqueos globales (de votación) se resuelven automáticamente (y todos están relacionados con la serialización (con conflictos de no bloqueo) en lugar de relacionados con el bloqueo (con conflictos de bloqueo y posiblemente también de no bloqueo)).
- Por lo tanto, no se necesita manejo de interbloqueos.
Ejemplos de
SS2PL distribuido
Un sistema de base de datos distribuida que utiliza SS2PL reside en dos nodos remotos, A y B. El sistema de base de datos tiene dos administradores de datos transaccionales ( administradores de recursos ), uno en cada nodo, y los datos de la base de datos se dividen entre los dos administradores de datos de una manera que cada uno tiene un control exclusivo de su propia porción de datos (local al nodo): cada uno maneja sus propios datos y bloquea sin ningún conocimiento sobre los del otro administrador. Para cada transacción distribuida, dichos administradores de datos deben ejecutar el protocolo de compromiso atómico disponible.
Dos transacciones distribuidas, y , se ejecutan simultáneamente y ambos acceden a los datos x e y. x está bajo el control exclusivo del administrador de datos en A (el administrador de B no puede acceder a x), y y debajo de B.
- lee x en A y escribe y en B, es decir, cuando se utiliza la notación común para el control de simultaneidad.
- lee y en B y escribe x en A, es decir,
Las respectivas subtransacciones locales en A y B (las porciones de y en cada uno de los nodos) son los siguientes:
Subtransacciones locales NodoTransacciónA B
El horario del sistema de base de datos en un momento determinado es el siguiente:
- (además es posible)
mantiene un bloqueo de lectura en x y mantiene bloqueos de lectura en y. Por lo tanto y están bloqueados por las reglas de compatibilidad de bloqueo de SS2PL y no se pueden ejecutar. Esta es una situación de punto muerto distribuido, que también es un punto muerto de votación (ver más abajo) con un ciclo distribuido (global) de longitud 2 (número de bordes, conflictos; 2 es la longitud más frecuente). Las subtransacciones locales se encuentran en los siguientes estados:
- está listo (la ejecución ha terminado) y votado (en compromiso atómico)
- se está ejecutando y bloqueado (una situación de conflicto no materializado; no se puede votar al respecto)
- está listo y votado
- se está ejecutando y bloqueado (un conflicto no materializado; sin votación).
Dado que el protocolo de compromiso atómico no puede recibir votos para subtransacciones bloqueadas (un punto muerto de votación), eventualmente abortará alguna transacción con un voto faltante por tiempo de espera , ya sea, o , (o ambos, si los tiempos de espera caen muy cerca). Esto resolverá el estancamiento global. La transacción restante se completará, se votará y se comprometerá. Una transacción abortada se reinicia y se vuelve a ejecutar inmediatamente .
Comentarios
- La partición de datos (x en A; y en B) es importante ya que sin ella, por ejemplo, se puede acceder a x directamente desde B. Si una transacción se ejecuta en B al mismo tiempo que y y escribe directamente x, luego, sin un administrador de bloqueo distribuido, el bloqueo de lectura para x mantenido por en A no es visible en B y no puede bloquear la escritura de (o señalar un conflicto materializado para una variante de CO sin bloqueo; ver más abajo). Por tanto, se puede violar la serialización.
- Debido a la partición de datos, no se puede acceder a x directamente desde B. Sin embargo, la funcionalidad no está limitada y una transacción que se ejecuta en B aún puede emitir una solicitud de escritura o lectura de x (no es común). Esta solicitud se comunica a la subtransacción local de la transacción en A (que se genera, si aún no existe) que emite esta solicitud al administrador de datos local en A.
Variaciones
En el escenario anterior, ambos conflictos no se materializan , y el punto muerto de votación global se refleja como un ciclo en el gráfico de espera global (pero no en el gráfico de conflicto global ; consulte Caracterización exacta de puntos muertos de votación por ciclos globales más arriba) . Sin embargo, el sistema de base de datos puede utilizar cualquier variante de CO con exactamente los mismos conflictos y situaciones de bloqueo de votaciones, y la misma resolución. Los conflictos pueden materializarse o no materializarse , según la variante de CO utilizada. Por ejemplo, si el sistema de base de datos distribuida usa SCO (abajo) en lugar de SS2PL, entonces los dos conflictos en el ejemplo se materializan , todas las subtransacciones locales están en estado listo y el bloqueo de votos ocurre en las dos transacciones, una en cada nodo, debido a la regla de votación de CO aplicada independientemente tanto en A como en B: debido a conflictos no se vota antes termina, y no se vota antes finaliza, que es un punto muerto en la votación. Ahora el gráfico de conflictos tiene el ciclo global (todos los conflictos se materializan), y nuevamente se resuelve mediante el protocolo de compromiso atómico, y se mantiene la serialización distribuida. Poco probable para un sistema de base de datos distribuido, pero posible en principio (y ocurre en una base de datos múltiple), A puede emplear SS2PL mientras que B emplea SCO. En este caso, el ciclo global no está ni en el gráfico de espera ni en el gráfico de serialización, sino que todavía está en el gráfico de conflicto aumentado (la unión de los dos). Las diversas combinaciones se resumen en la siguiente tabla:
Caso | Nodo A | Nodo B | Posible horario | Conflictos materializados en ciclo | Conflictos no materializados | ||||
---|---|---|---|---|---|---|---|---|---|
1 | SS2PL | SS2PL | 0 | 2 | Listo Votado | Corriendo (bloqueado) | Corriendo (bloqueado) | Listo Votado | |
2 | SS2PL | OCS | 1 | 1 | Listo Votado | Listo Voto bloqueado | Corriendo (bloqueado) | Listo Votado | |
3 | OCS | SS2PL | 1 | 1 | Listo Votado | Corriendo (bloqueado) | Listo Voto bloqueado | Listo Votado | |
4 | OCS | OCS | 2 | 0 | Listo Votado | Listo Voto bloqueado | Listo Voto bloqueado | Listo Votado |
- Comentarios:
- Los conflictos y, por lo tanto, los ciclos en el gráfico de conflicto aumentado están determinados únicamente por las transacciones y su programación inicial, independientemente del control de concurrencia utilizado. Con cualquier variante de CO, cualquier ciclo global (es decir, abarca dos bases de datos o más) provoca un punto muerto en la votación . Diferentes variantes de CO pueden diferir en si un determinado conflicto se materializa o no .
- Son posibles algunos cambios de orden de operación limitados en los horarios anteriores, restringidos por las órdenes dentro de las transacciones, pero tales cambios no cambian el resto de la tabla.
- Como se señaló anteriormente, solo el caso 4 describe un ciclo en el gráfico de conflicto (regular) que afecta la serialización. Los casos 1-3 describen ciclos de interbloqueos globales basados en bloqueo (existe al menos un bloqueo de bloqueo). Todos los tipos de ciclos se resuelven por igual mediante el protocolo de compromiso atómico. El caso 1 es el SS2PL distribuido común, utilizado desde la década de 1980. Sin embargo, ningún artículo de investigación, excepto los artículos de CO, ha notado esta resolución de bloqueo automático global de interbloqueo a partir de 2009. Estos interbloqueos globales normalmente se han tratado mediante mecanismos dedicados.
- El caso 4 anterior también es un ejemplo de un bloqueo de votación típico cuando se usa el CO optimista distribuido (DOCO) (es decir, el caso 4 no cambia cuando el CO optimista (OCO; ver más abajo) reemplaza al SCO tanto en A como en B): Sin datos- se produce el bloqueo de acceso y solo existen conflictos materializados.
Entorno hipotético de núcleo múltiple de un solo hilo (MuSiC)
Comentario: Si bien los ejemplos anteriores describen la utilización real recomendada de CO, este ejemplo es hipotético, solo para demostración.
Ciertas bases de datos experimentales distribuidas residente en memoria abogan por entornos transaccionales de núcleo de un solo subproceso múltiple (MuSiC). "Un solo subproceso" se refiere únicamente a subprocesos de transacciones y a la ejecución en serie de transacciones. El propósito es una posible ganancia de rendimiento de órdenes de magnitud (por ejemplo, H-Store [6] y VoltDB ) en relación con la ejecución de transacciones convencionales en múltiples subprocesos en un mismo núcleo. En lo que se describe a continuación, MuSiC es independiente de la forma en que se distribuyen los núcleos. Pueden residir en un circuito integrado (chip), o en muchos chips, posiblemente distribuidos geográficamente en muchas computadoras. En un entorno de este tipo, si los datos recuperables (transaccionales) se dividen entre subprocesos (núcleos) y se implementan de la forma convencional para el CO distribuido, como se describe en las secciones anteriores, entonces DOCO y Strictness existen automáticamente. Sin embargo, existen desventajas con esta implementación sencilla de dicho entorno, y su practicidad como solución de propósito general es cuestionable. Por otro lado, se puede lograr una enorme ganancia de rendimiento en aplicaciones que pueden evitar estos inconvenientes en la mayoría de las situaciones.
Comentario: La implementación directa de MuSiC descrita aquí (que usa, por ejemplo, como es habitual en CO distribuido, bloqueo de votaciones (y subprocesos de transacciones) en el protocolo de compromiso atómico cuando sea necesario) es solo para demostración y no tiene conexión con la implementación en H- Tienda o cualquier otro proyecto.
En un entorno MuSiC, los horarios locales son en serie . Por lo tanto, tanto el Optimistic CO local (OCO; ver más abajo) como la condición de la estrategia de ordenamiento de votos de cumplimiento de CO Global para el protocolo de compromiso atómico se cumplen automáticamente. Esto da como resultado tanto el cumplimiento de CO distribuido (y por lo tanto la serialización distribuida) y la resolución automática de interbloqueo global (votación).
Además, también el rigor local sigue automáticamente en un horario en serie. Según el teorema 5.2 en ( Raz 1992 ; página 307), cuando se aplica la estrategia de ordenación de votos de la CO, también se garantiza la Estricción Global. Tenga en cuenta que el serial local es el único modo que permite el rigor y el "optimismo" (sin bloqueo de acceso a datos) juntos.
Se concluye lo siguiente:
- El teorema de MuSiC
- En entornos MuSiC, si los datos recuperables (transaccionales) se dividen entre núcleos (subprocesos), ambos
- OCO (y serializabilidad implícita ; es decir, DOCO y serializabilidad distribuida)
- Estricción (que permite una recuperación efectiva; 1 y 2 implican CO estricto; consulte el SCO a continuación) y
- (votación) resolución de punto muerto
- existen automáticamente a nivel mundial con una escalabilidad ilimitada en el número de núcleos utilizados.
- Comentario: Sin embargo, pueden existir dos desventajas importantes, que necesitan un manejo especial:
- Las subtransacciones locales de una transacción global se bloquean hasta que se confirman, lo que hace que los núcleos respectivos estén inactivos. Esto reduce sustancialmente la utilización del núcleo, incluso si la programación de las subtransacciones locales intenta ejecutarlas todas en la proximidad del tiempo, casi juntas. Puede superarse separando la ejecución de la confirmación (con algún protocolo de compromiso atómico) para transacciones globales, a costa de posibles abortos en cascada.
- aumentar el número de núcleos para una determinada cantidad de datos recuperables (tamaño de la base de datos) disminuye la cantidad promedio de datos (particionados) por núcleo. Esto puede hacer que algunos núcleos estén inactivos, mientras que otros estén muy ocupados, dependiendo de la distribución de la utilización de datos. Además, una transacción local (a un núcleo) puede volverse global (multi-core) para alcanzar sus datos necesarios, con gastos generales adicionales incurridos. Por lo tanto, a medida que aumenta el número de núcleos, la cantidad y el tipo de datos asignados a cada núcleo deben equilibrarse de acuerdo con el uso de datos, por lo que un núcleo no se abruma para convertirse en un cuello de botella, ni se vuelve inactivo con demasiada frecuencia y se subutiliza en un sistema ocupado. Otra consideración es poner en una misma partición central todos los datos a los que normalmente se accede mediante una misma transacción (si es posible), para maximizar el número de transacciones locales (y minimizar el número de transacciones globales distribuidas). Esto se puede lograr mediante una nueva partición de datos ocasional entre núcleos según el equilibrio de carga (equilibrio de acceso a datos) y los patrones de uso de datos por transacciones. Otra forma de mitigar considerablemente este inconveniente es mediante la replicación de datos físicos adecuada entre algunas particiones centrales de manera que las transacciones globales de solo lectura se eviten por completo (según los patrones de uso) y los cambios de replicación se sincronicen mediante un mecanismo de confirmación dedicado.
Variantes de CO: casos especiales y generalizaciones
Las clases de propiedad de programación de casos especiales (por ejemplo, SS2PL y SCO a continuación) están estrictamente contenidas en la clase CO. Las clases de generalización (ECO y MVCO) contienen estrictamente la clase CO (es decir, también incluyen horarios que no cumplen con CO). Las variantes de generalización también garantizan la serialización global sin distribuir información de control de concurrencia local (cada base de datos tiene la propiedad de autonomía generalizada : usa solo información local), mientras relaja las restricciones de CO y utiliza información adicional (local) para una mejor concurrencia y rendimiento: ECO usa el conocimiento sobre las transacciones son locales (es decir, se limitan a una sola base de datos) y MVCO utiliza la disponibilidad de los valores de las versiones de datos. Al igual que el CO, ambas variantes de generalización no son bloqueantes , no interfieren con la programación de operaciones de ninguna transacción y se pueden combinar sin problemas con cualquier mecanismo de control de concurrencia relevante.
El término variante CO se refiere en general a CO, ECO, MVCO, o una combinación de cada uno de ellos con cualquier mecanismo o propiedad de control de concurrencia relevante (incluido ECO basado en múltiples versiones, MVECO). No se conocen otras variantes de generalización (que garantizan la serialización global sin distribución de información de control de concurrencia local), pero pueden descubrirse.
Fuerte bloqueo estricto de dos fases (SS2PL)
El bloqueo estricto de dos fases (SS2PL; también conocido como rigurosidad o programación rigurosa ) significa que los bloqueos de lectura y escritura de una transacción se liberan solo después de que la transacción ha finalizado (ya sea confirmada o cancelada). El conjunto de programas SS2PL es un subconjunto adecuado del conjunto de programas CO. Esta propiedad se utiliza ampliamente en los sistemas de bases de datos, y dado que implica CO, las bases de datos que la usan y participan en transacciones globales generan juntas una programación global serializable (cuando se usa cualquier protocolo de compromiso atómico, que es necesario para la atomicidad en un entorno de bases de datos múltiples). . En este caso, no se necesita ninguna modificación o adición de la base de datos para participar en una solución distribuida de CO: el conjunto de transacciones indecisas que se deben abortar antes de comprometerse en el algoritmo de CO genérico local anterior está vacío debido a los bloqueos y, por lo tanto, dicho algoritmo es innecesario en este caso. Una transacción puede ser votada por un sistema de base de datos inmediatamente después de entrar en un estado "listo", es decir, después de completar la ejecución de su tarea localmente. Sus bloqueos son liberados por el sistema de base de datos solo después de que lo decida el protocolo de compromiso atómico y, por lo tanto, la condición en el teorema de aplicación global de CO anterior se mantiene automáticamente. Si un sistema de base de datos utiliza un mecanismo de tiempo de espera local para resolver puntos muertos SS2PL (locales), al abortar las transacciones bloqueadas se interrumpen no solo los ciclos locales potenciales en el gráfico de conflicto global (ciclos reales en el gráfico de conflicto aumentado), sino también el potencial global del sistema de base de datos. ciclos como efecto secundario, si el mecanismo de aborto del protocolo de compromiso atómico es relativamente lento. Tales abortos independientes por parte de varias entidades normalmente pueden resultar en abortos innecesarios para más de una transacción por ciclo global. La situación es diferente para los mecanismos basados en gráficos de espera locales : estos no pueden identificar ciclos globales, y el protocolo de compromiso atómico romperá el ciclo global, si el punto muerto de votación resultante no se resuelve antes en otra base de datos.
El SS2PL local junto con el compromiso atómico que implica la serialización global también se puede deducir directamente: todas las transacciones, incluidas las distribuidas, obedecen las reglas 2PL (SS2PL). El mecanismo de protocolo de compromiso atómico no es necesario aquí para el consenso sobre el compromiso, sino más bien para el final del punto de sincronización de la fase dos. Probablemente por esta razón, sin considerar el mecanismo de votación de compromiso atómico, la resolución automática de puntos muertos globales no se ha notado antes de CO.
Estricto CO (SCO)
El Orden de Compromiso Estricto (SCO; ( Raz 1991c )) es la intersección del rigor (un caso especial de recuperabilidad) y CO, y proporciona un límite superior para la concurrencia de un cronograma cuando ambas propiedades existen. Se puede implementar utilizando mecanismos de bloqueo (bloqueo) similares a los utilizados para el popular SS2PL con gastos generales similares.
A diferencia de SS2PL, SCO no bloquea en un conflicto de lectura y escritura, sino que posiblemente bloquea en su lugar la confirmación. SCO y SS2PL tienen un comportamiento de bloqueo idéntico para los otros dos tipos de conflicto: escritura-lectura y escritura-escritura. Como resultado, SCO tiene períodos de bloqueo promedio más cortos y más concurrencia (por ejemplo, simulaciones de rendimiento de una sola base de datos para la variante más significativa de bloqueos con uso compartido ordenado , que es idéntico al SCO, lo muestra claramente, con aproximadamente un 100% de ganancia para algunas cargas de transacción; también para cargas de transacción idénticos SCO pueden alcanzar tasas de transacción más altos que SS2PL antes de bloqueo thrashing se produce). Más simultaneidad significa que con los recursos informáticos dados se completan más transacciones en la unidad de tiempo (tasa de transacción más alta, rendimiento ) y la duración promedio de una transacción es más corta (finalización más rápida; ver gráfico). La ventaja de SCO es especialmente significativa durante la contención de bloqueo.
- La OCS vs. Teorema de rendimiento SS2PL
- SCO proporciona un tiempo promedio de finalización de transacciones más corto que SS2PL, si existen conflictos de lectura y escritura. De lo contrario, SCO y SS2PL son idénticos (tienen un comportamiento de bloqueo idéntico con conflictos de escritura-lectura y escritura-escritura).
SCO es tan práctico como SS2PL ya que, como SS2PL, proporciona además de serializabilidad también rigor, que se utiliza ampliamente como base para la recuperación eficiente de bases de datos en caso de fallas. Un mecanismo SS2PL se puede convertir en uno SCO para un mejor rendimiento de una manera sencilla sin cambiar los métodos de recuperación. Se puede encontrar una descripción de la implementación de una OCS en (Perrizo y Tatarinov 1998). [7] Véase también Planificador de bases de datos semi-optimista .
SS2PL es un subconjunto adecuado de SCO (que es otra explicación de por qué SCO es menos restrictivo y proporciona más concurrencia que SS2PL).
CO optimista (OCO)
Para implementar el orden de compromiso optimista (OCO), el algoritmo de CO local genérico se utiliza sin bloqueo de acceso a los datos y, por lo tanto, sin puntos muertos locales. OCO sin restricciones de programación de transacciones u operaciones cubre toda la clase de CO y no es un caso especial de la clase de CO, sino más bien una variante de CO útil y una caracterización del mecanismo.
CO extendido (ECO)
Caracterización general de ECO
El orden de compromiso extendido (ECO; ( Raz 1993a )) generaliza el CO. Cuando las transacciones locales (transacciones confinadas a una sola base de datos) se pueden distinguir de las transacciones globales (distribuidas) (transacciones que abarcan dos bases de datos o más), el orden de compromiso se aplica a transacciones solamente. Por lo tanto, para que una programación local (a una base de datos) tenga la propiedad ECO, el orden cronológico (parcial) de los eventos de confirmación de transacciones globales solamente (no importante para transacciones locales) es consistente con su orden en el gráfico de conflicto local respectivo.
- Definición: pedido de compromiso extendido
- Dejar ser dos transacciones globales comprometidas en una programación, de modo que exista una ruta dirigida de transacciones no canceladas en el gráfico de conflicto ( gráfico de precedencia ) de a ( precede , posiblemente transitivamente , indirectamente). La programación tiene la propiedad Pedido de compromiso extendido (ECO), si por cada dos transacciones de este tipo se compromete antes se compromete.
Existe un algoritmo distribuido para garantizar el ECO global. En cuanto a CO, el algoritmo solo necesita mensajes de protocolo de compromiso atómico (sin modificar). Para garantizar la serialización global, cada base de datos debe garantizar también la serialización de conflictos de sus propias transacciones mediante cualquier mecanismo de control de concurrencia (local).
- El ECO y el teorema de serialización global
- (Local, que implica global) ECO junto con la serializabilidad del conflicto local, es una condición suficiente para garantizar la serializabilidad del conflicto global.
- Cuando no se comparte información de control de concurrencia más allá de los mensajes de compromiso atómico fuera de una base de datos (autonomía) y se pueden identificar transacciones locales, también es una condición necesaria.
- Vea una prueba de necesidad en ( Raz 1993a ).
Esta condición (ECO con serializabilidad local) es más débil que CO y permite más simultaneidad a costa de un algoritmo local un poco más complicado (sin embargo, no existe una diferencia práctica con CO).
Cuando se supone que todas las transacciones son globales (por ejemplo, si no hay información disponible sobre transacciones locales), ECO se reduce a CO.
El algoritmo ECO
Antes de que se confirme una transacción global, un algoritmo ECO local genérico (a una base de datos) aborta un conjunto mínimo de transacciones indecisas (ni comprometidas ni canceladas; ya sean transacciones locales o globales que se ejecutan localmente), que pueden causar un ciclo posterior en el gráfico de conflicto. Este conjunto de transacciones abortadas (no únicas, contrariamente a CO) se puede optimizar, si a cada transacción se le asigna un peso (que puede ser determinado por la importancia de la transacción y por los recursos informáticos ya invertidos en la transacción en ejecución; la optimización puede llevarse a cabo , por ejemplo, mediante una reducción del problema de flujo máximo en redes ( Raz 1993a )). Como ocurre con el CO, este conjunto depende del tiempo y eventualmente se vaciará. Prácticamente, en casi todas las implementaciones necesarias, una transacción debe confirmarse solo cuando el conjunto está vacío (y no se aplica ninguna optimización de conjunto). El mecanismo de control de concurrencia local (a la base de datos) (separado del algoritmo ECO) asegura que se eliminen los ciclos locales (a diferencia del CO, que implica serializabilidad por sí mismo; sin embargo, prácticamente también para CO se utiliza un mecanismo de concurrencia local, al menos para asegurar la recuperabilidad). Las transacciones locales siempre se pueden realizar al mismo tiempo (incluso si existe una relación de precedencia, a diferencia de CO). Cuando el orden parcial local de las transacciones generales (que está determinado por el gráfico de conflicto local, ahora solo con posibles ciclos locales temporales, ya que los ciclos son eliminados por un mecanismo de serialización local) lo permite, también se pueden votar transacciones globales para que se comprometan simultáneamente ( cuando todas sus transacciones globales transitivamente (indirectas) precedentes (a través de conflicto) están comprometidas, mientras que las transacciones locales transitivamente precedentes pueden estar en cualquier estado. Esto en analogía con la condición de votación concurrente más fuerte del algoritmo de CO distribuido, donde todas las transacciones anteriores transitivamente deben ser comprometido).
La condición para garantizar Global ECO se puede resumir de manera similar a CO:
- El teorema de la estrategia de ordenación del voto de cumplimiento de ECO global
- Dejar Ser transacciones globales indecisas (ni comprometidas ni abortadas) en un sistema de base de datos que garantice la serialización localmente, de modo que exista una ruta dirigida de transacciones no canceladas en el gráfico de conflicto local (el de la base de datos en sí) desde a . Entonces, teniendo terminó (ya sea comprometido o abortado) antes se vota para comprometerse, en cada uno de estos sistemas de base de datos en un entorno de bases de datos múltiples, es una condición necesaria y suficiente para garantizar Global ECO (la condición garantiza Global ECO, que puede ser violado sin él).
Global ECO (todos los ciclos globales en el gráfico de conflicto global se eliminan por compromiso atómico) junto con la serialización local (es decir, cada sistema de base de datos mantiene la serialización localmente; todos los ciclos locales se eliminan) implican la serialización global (se eliminan todos los ciclos). Esto significa que si cada sistema de base de datos en un entorno de base de datos múltiple proporciona serialización local (mediante cualquier mecanismo) y aplica la estrategia de ordenación de votos en el teorema anterior (una generalización de la estrategia de ordenación de votos de CO), entonces la serialización global está garantizada (no se necesita CO local). nunca más).
De manera similar a CO, la situación de punto muerto en la votación de ECO se puede resumir de la siguiente manera:
- El teorema ECO de voto-punto muerto
- Deje que un entorno de bases de datos múltiples comprenda sistemas de bases de datos que refuercen, cada uno, tanto ECO global (usando la condición en el teorema anterior) como serializabilidad de conflicto local (que elimina los ciclos locales en el gráfico de conflicto global). Luego, se produce un punto muerto en la votación si y solo si existe un ciclo global (abarca dos o más bases de datos) en el gráfico de conflicto global aumentado (también el bloqueo por un bloqueo de acceso a datos está representado por un borde). Si el ciclo no se rompe por ningún aborto, entonces todas las transacciones globales en él están involucradas con el punto muerto de votación respectivo y, finalmente, cada una tiene su voto bloqueado (ya sea directa o indirectamente por un bloqueo de acceso a datos). Si una transacción local reside en el ciclo, puede estar en cualquier estado no cancelado (en ejecución, lista o comprometida; a diferencia de CO, no se necesita ningún bloqueo de confirmación local).
Al igual que con CO, esto significa que también los interbloqueos globales debidos al bloqueo de acceso a datos (con al menos un bloqueo de bloqueo) son interbloqueos de votación y se resuelven automáticamente mediante compromiso atómico.
CO de múltiples versiones (MVCO)
El pedido de compromiso de múltiples versiones (MVCO; ( Raz 1993b )) es una generalización de CO para bases de datos con recursos de múltiples versiones . Con tales recursos , las transacciones de solo lectura no se bloquean ni se bloquean para un mejor rendimiento. El uso de dichos recursos es una forma común hoy en día de aumentar la simultaneidad y el rendimiento al generar una nueva versión de un objeto de base de datos cada vez que se escribe el objeto y permitir las operaciones de lectura de transacciones de varias últimas versiones relevantes (de cada objeto). MVCO implica la serialización de una copia (1SER o 1SR), que es la generalización de la serialización para recursos de múltiples versiones. Al igual que CO, MVCO no es bloqueante y se puede combinar con cualquier mecanismo de control de concurrencia de múltiples versiones relevante sin interferir con él. En la teoría subyacente introducida para MVCO, los conflictos se generalizan para diferentes versiones de un mismo recurso (a diferencia de las teorías anteriores de múltiples versiones). Para diferentes versiones, el orden cronológico de los conflictos se reemplaza por el orden de las versiones, y posiblemente se invierte, manteniendo las definiciones habituales para las operaciones en conflicto. Los resultados para los gráficos de conflicto regulares y aumentados permanecen sin cambios, y de manera similar a CO, existe un algoritmo de aplicación MVCO distribuido, ahora para un entorno mixto con recursos de versión única y de múltiples versiones (ahora la versión única es un caso especial de versión múltiple ). En cuanto a CO, el algoritmo MVCO solo necesita mensajes de protocolo de compromiso atómico (sin modificar) sin sobrecarga de comunicación adicional. Los interbloqueos globales basados en bloqueos se traducen en interbloqueos de votación y se resuelven automáticamente. En analogía con el CO, se cumple lo siguiente:
- El teorema de serializabilidad de una copia global y MVCO
- El cumplimiento de MVCO de cada sistema de base de datos autónomo (u objeto transaccional) en un entorno de base de datos múltiple mixto de bases de datos de versión única y versión múltiple es una condición necesaria para garantizar la serialización global de una copia (1SER).
- El cumplimiento de MVCO de cada sistema de base de datos es una condición suficiente para garantizar Global 1SER.
- Los interbloqueos globales basados en bloqueos se resuelven automáticamente.
- Comentario : Ahora, un sistema de base de datos de una sola versión compatible con CO es automáticamente compatible con MVCO.
MVCO se puede generalizar aún más para emplear la generalización de ECO (MVECO).
Ejemplo: aislamiento de instantáneas basado en CO (COSI)
El aislamiento de instantáneas basado en CO (COSI) es la intersección del aislamiento de instantáneas (SI) con MVCO. SI es un método de control de concurrencia de múltiples versiones ampliamente utilizado debido a su buen rendimiento y similitud con la serialización (1SER) en varios aspectos. La teoría en (Raz 1993b) para MVCO descrita anteriormente se utiliza más adelante en (Fekete et al. 2005) y otros artículos sobre SI, por ejemplo, (Cahill et al. 2008); [8] ver también Hacer serializable el aislamiento de instantáneas y las referencias allí), para analizar los conflictos en SI con el fin de hacerlo serializable. El método presentado en (Cahill et al. 2008), Aislamiento de instantáneas serializables (SerializableSI), una modificación de baja sobrecarga de SI, proporciona buenos resultados de rendimiento frente a SI, con solo una pequeña penalización por imponer la serialización. Un método diferente, al combinar SI con MVCO (COSI), también hace que SI sea serializable, con una sobrecarga relativamente baja, de manera similar a la combinación del algoritmo CO genérico con mecanismos de versión única. Además, la combinación resultante, COSI, que cumple con MVCO, permite que los sistemas de bases de datos compatibles con COSI interactúen y participen de forma transparente en una solución de CO para la serialización distribuida / global (ver más abajo). Además de los gastos generales, los comportamientos de los protocolos deben compararse cuantitativamente. Por un lado, todos los horarios de SI serializables pueden hacerse MVCO por COSI (por posibles retrasos de compromiso cuando sea necesario) sin abortar transacciones. Por otro lado, se sabe que SerializableSI aborta y reinicia innecesariamente ciertos porcentajes de transacciones también en programas de SI serializables.
CO y sus variantes son interoperables de forma transparente para la serialización global
Con CO y sus variantes (por ejemplo, SS2PL, SCO, OCO, ECO y MVCO anteriores), la serialización global se logra mediante algoritmos distribuidos basados en el protocolo de compromiso atómico . Para CO y todas sus variantes, el protocolo de compromiso atómico es el instrumento para eliminar ciclos globales (ciclos que abarcan dos o más bases de datos) en el gráfico de conflicto global aumentado (y por lo tanto también regular) (implícitamente; no se necesita la implementación de una estructura de datos global). En casos de órdenes de compromiso locales incompatibles en dos o más bases de datos (cuando ninguna orden parcial global puede integrar las respectivas órdenes parciales locales juntas), o un punto muerto de votación relacionado con bloqueo de acceso a datos, ambos implican un ciclo global en el gráfico de conflicto global aumentado y votos faltantes, el protocolo de compromiso atómico rompe dicho ciclo al abortar una transacción indecisa en él (ver El algoritmo de CO distribuido más arriba). Las diferencias entre las diversas variantes existen solo a nivel local (dentro de los sistemas de bases de datos participantes). Cada instancia de CO local de cualquier variante tiene el mismo rol, para determinar la posición de cada transacción global (una transacción que abarca dos o más bases de datos) dentro de la orden de compromiso local, es decir, para determinar cuándo es el turno de la transacción para ser votada. localmente en el protocolo de compromiso atómico. Así, todas las variantes de CO exhiben el mismo comportamiento con respecto al compromiso atómico. Esto significa que todos son interoperables a través del compromiso atómico (utilizando las mismas interfaces de software, generalmente proporcionadas como servicios , algunos ya estandarizados para el compromiso atómico, principalmente para el protocolo de compromiso de dos fases , por ejemplo, X / Open XA ) y se pueden utilizar juntos de forma transparente. en cualquier entorno distribuido (mientras que cada instancia de variante de CO está posiblemente asociada con cualquier tipo de mecanismo de control de concurrencia local relevante).
En resumen, cualquier transacción global individual puede participar simultáneamente en bases de datos que pueden emplear cualquier variante de CO, posiblemente diferente (mientras se ejecutan simultáneamente procesos en cada base de datos y se ejecutan simultáneamente con transacciones locales y otras transacciones globales en cada base de datos). El protocolo de compromiso atómico es indiferente al CO y no distingue entre las diversas variantes de CO. Cualquier ciclo global generado en el gráfico de conflicto global aumentado puede abarcar bases de datos de diferentes variantes de CO y generar (si no se rompe por ningún aborto local) un punto muerto de votación que se resuelve mediante compromiso atómico exactamente de la misma manera que en un entorno de variante de CO único. Los ciclos locales (ahora posiblemente con conflictos mezclados materializados y no materializados, relacionados tanto con la serialización como con el bloqueo de acceso a datos, por ejemplo, SCO) se resuelven localmente (cada uno mediante los propios mecanismos locales de su instancia variante respectiva).
La ordenación de votos (VO o CO generalizada (GCO); Raz 2009 ), la unión de CO y todas sus variantes anteriores, es un concepto útil y una técnica de serialización global. Para cumplir con VO, se necesita la serialización local (en su forma más general, basada en conmutatividad e incluyendo múltiples versiones) y la estrategia de orden de votación (votación por orden de precedencia local).
Combinando resultados para CO y sus variantes, se concluye lo siguiente:
- El teorema de interoperabilidad de variantes de CO
- En un entorno de bases de datos múltiples, donde cada sistema de base de datos (objeto transaccional) es compatible con alguna propiedad de variante de CO (compatible con VO), cualquier transacción global puede participar simultáneamente en bases de datos de posibles variantes de CO diferentes, y la serialización global está garantizada ( condición suficiente para Serializabilidad global; y serializabilidad global de una copia (1SER), para un caso en el que existe una base de datos de múltiples versiones).
- Si cada sistema de base de datos utiliza solo información de control de concurrencia local (a un sistema de base de datos) (cada uno tiene la propiedad de autonomía generalizada , una generalización de autonomía ), entonces el cumplimiento de cada uno con alguna (cualquier) propiedad de variante de CO (cumplimiento de VO) es un problema. condición necesaria para garantizar la serialización global (y 1SER global; de lo contrario, se pueden violar).
- Además, en dicho entorno, los puntos muertos relacionados con el bloqueo de acceso a datos se resuelven automáticamente (cada uno de esos puntos muertos se genera mediante un ciclo global en el gráfico de conflicto aumentado (es decir, un punto muerto de votación ; ver más arriba), que implica al menos un bloqueo de acceso a datos (conflicto no materializado) y dos sistemas de base de datos; por lo tanto, no es un ciclo en el gráfico de conflicto regular y no afecta la serialización).
Referencias
- Raz, Yoav (agosto de 1992), "The Principle of Commitment Ordering, or Guaranteeing Serializability in a Heterogeneous Environment of Multiple Autonomous Resource Managers Using Atomic Commitment" (PDF) , Actas de la Decimoctava Conferencia Internacional sobre Bases de Datos Muy Grandes , Vancouver, Canadá , págs. 292–312(también DEC-TR 841, Digital Equipment Corporation , noviembre de 1990)
- Raz, Yoav (septiembre de 1994), "Serializability by Commitment Ordering", Information Processing Letters , 51 (5): 257–264, doi : 10.1016 / 0020-0190 (94) 90005-1
- Raz, Yoav (junio de 2009), Theory of Commitment Ordering: Summary , consultado el 11 de noviembre de 2011
- Raz, Yoav (noviembre de 1990), Sobre la importancia de los pedidos de compromiso (PDF) , Digital Equipment Corporation
- Yoav Raz (1991a): Patentes estadounidenses 5,504,899 (ECO) 5,504,900 (CO) 5,701,480 (MVCO)
- Yoav Raz (1991b): "El coordinador de órdenes de compromiso (COCO) de un administrador de recursos, o arquitectura para el control de concurrencia basado en órdenes de compromiso distribuido", DEC-TR 843, Digital Equipment Corporation, diciembre de 1991.
- Yoav Raz (1991c): "Orden de compromiso estricto basado en bloqueo, o cómo mejorar la simultaneidad en administradores de recursos basados en bloqueo", DEC-TR 844, diciembre de 1991.
- Yoav Raz (1993a): "Pedido de compromiso ampliado o garantía de serialización global mediante la aplicación de la selectividad del pedido de compromiso a las transacciones globales". Actas del Duodécimo Simposio de la ACM sobre los principios de los sistemas de bases de datos (PODS), Washington, DC, págs. 83-96, mayo de 1993 (también DEC-TR 842, noviembre de 1991).
- Yoav Raz (1993b): "Control de simultaneidad distribuido basado en pedidos de compromiso para unir recursos de versiones individuales y múltiples". Actas del tercer taller internacional del IEEE sobre cuestiones de investigación sobre ingeniería de datos: interoperabilidad en sistemas de bases de datos múltiples (RIDE-IMS), Viena, Austria, págs. 189-198, abril de 1993 (también DEC-TR 853, julio de 1992).
Notas al pie
- ^ a b Alan Fekete, Nancy Lynch , Michael Merritt, William Weihl (1988): Bloqueo basado en conmutatividad para transacciones anidadas (PDF) MIT, LCS lab, Informe técnico MIT / LCS / TM-370, agosto de 1988.
- ^ Philip A. Bernstein , Eric Newcomer (2009): Principles of Transaction Processing , 2nd Edition Archivado el 7 deagosto de 2010en Wayback Machine , Morgan Kaufmann (Elsevier), junio de 2009 ISBN 978-1-55860-623-4 (páginas 145, 360)
- ^ a b Lingli Zhang, Vinod K. Grover, Michael M. Magruder, David Detlefs, John Joseph Duffy, Goetz Graefe (2006): Orden de confirmación de transacciones de software y gestión de conflictos Patente de los Estados Unidos 7711678, concedida el 04/05/2010.
- ^ Hany E. Ramadan, Indrajit Roy, Maurice Herlihy, Emmett Witchel (2009): "Compromiso de transacciones conflictivas en un STM" ( PDF [ enlace muerto permanente ] ) Actas del 14 ° simposio ACM SIGPLAN sobre principios y práctica de programación paralela (PPoPP '09), ISBN 978-1-60558-397-6
- ^ Christoph von Praun, Luis Ceze, Calin Cascaval (2007) "Paralelismo implícito con transacciones ordenadas" ( PDF ), Actas del 12 ° simposio ACM SIGPLAN sobre principios y práctica de la programación paralela (PPoPP '07), ACM Nueva York © 2007, ISBN 978-1-59593-602-8 doi 10.1145 / 1229428.1229443
- ^ Robert Kallman, Hideaki Kimura, Jonathan Natkins, Andrew Pavlo, Alex Rasin, Stanley Zdonik , Evan Jones, Yang Zhang, Samuel Madden, Michael Stonebraker , John Hugg, Daniel Abadi (2008): "H-Store: un alto rendimiento, Sistema de procesamiento de transacciones de memoria principal distribuida " , Actas del VLDB 2008 , páginas 1496 - 1499, Auckland, Nueva Zelanda, agosto de 2008.
- ^ Perrizo, William; Tatarinov, Igor (11 de noviembre de 1998). Un programador de base de datos semi-optimista basado en la confirmación de pedidos . 1998 Congreso Internacional de Aplicaciones Informáticas en la Industria y la Ingeniería. Las Vegas. págs. 75–79. CiteSeerX 10.1.1.53.7318 .
- ^ Michael J. Cahill, Uwe Röhm, Alan D. Fekete (2008): "Aislamiento serializable para bases de datos instantáneas" , Actas de la conferencia internacional ACM SIGMOD de 2008 sobre gestión de datos , págs. 729-738, Vancouver, Canadá, junio de 2008 , ISBN 978-1-60558-102-6 (premio SIGMOD 2008 al mejor artículo
enlaces externos
- Página de pedidos del compromiso de Yoav Raz