El ordenamiento 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 multinúcleo , CO también se ha utilizado cada vez más en programación concurrente , memoria transaccional y memoria transaccional de software (STM) para lograr serialización de manera optimista . CO también es el nombre de la propiedad de cronograma de transacciones resultante (historial), definida en 1988 con el nombre de atomicidad dinámica . [1] En un cronograma compatible con 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 serialización de conflictos y un medio efectivo ( confiable , de alto rendimiento, distribuido y escalable ) para lograr serialización global (serialización modular) en cualquier colección de sistemas de bases de datos que posiblemente usen diferentes mecanismos de control de concurrencia (CO también hace que cada sistema sea compatible con la serialización, si no lo es ya).
Cada sistema de base de datos que no cumple con CO se amplía con un componente CO (el coordinador de orden de compromiso, COCO) que ordena los eventos de compromiso para el cumplimiento de CO, sin interferencias de acceso a datos ni ninguna otra operación de transacción. Como tal, CO proporciona una solución general de baja sobrecarga para la serialización global (y serialización distribuida), instrumental para el control de concurrencia global (y control de concurrencia distribuida ) de sistemas de múltiples bases de datos y otros objetos transaccionales, posiblemente altamente distribuidos (por ejemplo, dentro de la computación en la nube , la computación en cuadrícula y las redes de teléfonos inteligentes ). Un protocolo de compromiso atómico (ACP; de cualquier tipo) es una parte fundamental de la solución, utilizada para romper ciclos globales en el gráfico de conflictos (precedencia, serialización). 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 lo 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 locales, bloqueos, marcas de tiempo o tickets). Generaliza la popular propiedad de bloqueo estricto fuerte en dos fases (SS2PL), que en conjunto con el protocolo de confirmación en dos fases (2PC), es el estándar de facto para lograr serialización global en todos 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 dichas soluciones basadas en SS2PL para lograr serialización global.
Además, los bloqueos globales basados en bloqueos se resuelven automáticamente en un entorno de múltiples bases de datos basado en CO, un beneficio secundario vital (incluido el caso especial de un entorno completamente basado en SS2PL; un hecho que anteriormente no se había detectado para SS2PL).
Además, el ordenamiento de compromiso estricto (SCO; Raz 1991c), la intersección de la rigurosidad y el CO, proporciona un mejor rendimiento (tiempo promedio de finalización de transacción más corto y, como resultado, un mejor rendimiento de la transacción ) que SS2PL siempre que existan conflictos de lectura y escritura (comportamiento de bloqueo idéntico para conflictos de escritura-lectura y escritura-escritura; sobrecarga de bloqueo comparable). La ventaja de SCO es especialmente durante la contención de bloqueo. La rigurosidad permite que tanto SS2PL como SCO utilicen los mismos mecanismos efectivos de recuperación de bases de datos .
Existen dos variantes generalizadoras principales de CO, CO extendido (ECO; Raz 1993a) y CO multi-versión (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 concurrencia y rendimiento. El ordenamiento de votos (VO o CO generalizado (GCO); Raz 2009) es un conjunto de programación de contenedores (propiedad) y técnica para 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 ). CO y sus variantes interoperan de forma transparente, lo que garantiza la serialización global y la resolución automática de bloqueos globales en un entorno mixto y heterogéneo con diferentes variantes.
La propiedad de programación Ordenamiento de compromiso (CO; Raz 1990, 1992, 1994, 2009) también se conoce como Atomicidad dinámica (desde 1988 [1] ), Ordenamiento de compromiso , Serializabilidad del orden de compromiso y Recuperabilidad fuerte (desde 1991). Este último es un nombre engañoso, ya que CO es incomparable con Recuperabilidad y el término "fuerte" implica un caso especial. Esto significa que una propiedad de recuperabilidad sustancial no necesariamente tiene la propiedad 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 conocidos previamente (desde la década de 1980): bloqueo , ordenamiento de marcas de tiempo y pruebas de gráficos de serialización , y como un facilitador para la interoperabilidad de sistemas que utilizan diferentes mecanismos de control de concurrencia. [2]
En un sistema de base de datos federada o cualquier otro sistema multibase de datos definido de forma más vaga, que normalmente se distribuyen en una red de comunicación, las transacciones abarcan múltiples bases de datos, posiblemente distribuidas . Imponer la serialización global en un sistema de este tipo es problemático. Incluso si cada programación local de una única base de datos sigue siendo serializable, la programación global de un sistema completo no es necesariamente serializable. Los intercambios masivos de información de 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; consulte también Serialización global ).
La aplicación de CO es una forma eficaz de aplicar la serialización de conflictos de forma global en un sistema distribuido, ya que aplicar CO de forma local en cada base de datos (u otros objetos transaccionales) también lo aplica de forma global. Cada base de datos puede utilizar cualquier tipo de mecanismo de control de concurrencia, posiblemente diferente. Con un mecanismo local que ya proporciona serialización de conflictos, la aplicación de CO de forma local no provoca ninguna otra interrupción, ya que la aplicación de CO de forma local no afecta la estrategia de programación de acceso a datos del mecanismo (esta programación determina las interrupciones relacionadas con la serialización; un mecanismo de este tipo normalmente no considera los eventos de compromiso ni su orden). La solución de CO no requiere sobrecarga de comunicación, ya que utiliza únicamente 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 desempeña un papel central en el algoritmo de CO distribuido, que aplica CO de forma global rompiendo ciclos globales (ciclos que abarcan dos o más bases de datos) en el gráfico de conflictos globales. CO, sus casos especiales y sus generalizaciones son interoperables y logran serialización global mientras se utilizan de manera transparente en conjunto en un único entorno distribuido heterogéneo que comprende objetos con posibles mecanismos de control de concurrencia diferentes. Como tal, el ordenamiento de compromiso , incluidos sus casos especiales y junto con sus generalizaciones (consulte las variantes de CO a continuación), proporciona una solución general, de alto rendimiento y completamente distribuida (no se necesita ningún componente de procesamiento central ni estructura de datos central) para garantizar la serialización global en entornos heterogéneos de sistemas de múltiples bases de datos y otros objetos transaccionales múltiples (objetos con estados a los que se accede y modifican solo mediante transacciones; por ejemplo, en el marco de procesos transaccionales y dentro de la computación en la nube y la computación en cuadrícula). La solución CO se escala con el tamaño de la red y la cantidad de bases de datos sin ningún impacto negativo en el rendimiento (suponiendo que las estadísticas de una sola transacción distribuida, por ejemplo, la cantidad promedio de bases de datos involucradas con 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 serialización en la memoria transaccional del software, y ya se han publicado numerosos artículos y patentes de STM que utilizan "orden de confirmación" (por ejemplo, Zhang et al. 2006 [3] ).
El orden de compromiso (CO) es un caso especial de serialización de conflictos. El CO se puede aplicar con mecanismos no bloqueantes (cada transacción puede completar su tarea sin que se bloquee su acceso a los datos, lo que permite un control de concurrencia optimista ; sin embargo, el compromiso podría bloquearse). En una programación CO, el orden de precedencia ( parcial ) de los eventos de compromiso de las transacciones corresponde al orden de precedencia (parcial) de las respectivas transacciones en el gráfico de conflictos ( dirigido ) (gráfico de precedencia, gráfico de serialización), tal como lo inducen sus operaciones de acceso conflictivas (generalmente operaciones de lectura y escritura (insertar/modificar/eliminar); el CO también se aplica a operaciones de nivel superior, donde son conflictivas si no son conmutativas , así como a conflictos entre operaciones sobre datos de múltiples versiones).
Los eventos de decisión de compromiso se generan mediante un mecanismo de compromiso local o un protocolo de compromiso atómico si diferentes procesos necesitan llegar a un consenso sobre si confirmar o abortar. El protocolo puede ser distribuido o centralizado. Las transacciones pueden confirmarse simultáneamente si el orden parcial de confirmación lo permite (si no tienen operaciones conflictivas). Supongamos que diferentes operaciones conflictivas inducen diferentes órdenes parciales de las mismas transacciones. En ese caso, el gráfico de conflictos tiene ciclos y la programación violará la serialización cuando se confirmen todas las transacciones en un ciclo. En este caso, no se puede encontrar ningún orden parcial para los eventos de compromiso. Por lo tanto, los ciclos en el gráfico de conflictos deben romperse abortando las transacciones. Sin embargo, cualquier programación serializable por 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.
Existe un algoritmo de cumplimiento de ordenamiento 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 comunicación adicional. El algoritmo distribuido es la combinación de procesos de algoritmo de CO local (para cada base de datos) y un protocolo de compromiso atómico (que puede ser completamente distribuido). El protocolo de compromiso atómico es esencial para hacer cumplir la atomicidad de cada transacción distribuida (para decidir si confirmarla o abortarla; este procedimiento siempre se lleva a cabo para transacciones distribuidas, independientemente del control de concurrencia y el 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 la transacción distribuida 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 alcanza un consenso entre los participantes sobre si se debe confirmar o cancelar una transacción distribuida (global) que abarca a estos participantes. Una etapa esencial en cada uno de estos protocolos es el voto SÍ (explícito o implícito) de cada participante, lo que significa una obligación del participante con derecho a voto de obedecer la decisión del protocolo, ya sea confirmar o cancelar. De lo contrario, un participante puede cancelar unilateralmente la transacción con un voto NO explícito. El protocolo confirma 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 cancela 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 las cantidades de trabajo y otros recursos informáticos necesarios en diferentes situaciones.
Toda la solución CO para la serialización global se basa en el hecho de que el protocolo de compromiso atómico eventualmente cancela esta transacción en caso de que falte un voto para una transacción distribuida.
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 los datos locales. En consecuencia, los votos SÍ en el protocolo de compromiso atómico se programan para cada transacción distribuida (no cancelada) (en lo sucesivo, "un voto" significa un voto SÍ). Supongamos que existe una relación de precedencia (conflicto) entre dos transacciones. En ese caso, no se votará sobre la segunda antes de que se complete la primera (ya sea que se confirme o cancele), para evitar una posible violación del orden de compromiso por parte del protocolo de compromiso atómico. Esto puede suceder ya que el orden de compromiso del protocolo no es necesariamente el mismo que el orden de votación. Si no existe una relación de precedencia, se pueden votar ambas al mismo tiempo. Esta estrategia de ordenamiento de votos garantiza que también el protocolo de compromiso atómico mantenga 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 ella, tanto el CO global como el CO local (una propiedad que significa que cada base de datos es compatible con el CO) pueden ser violados).
Sin embargo, dado que los sistemas de bases de datos programan sus transacciones de forma independiente, es posible que los órdenes de precedencia de las transacciones en dos bases de datos o más no sean compatibles (no existe ningún orden parcial global que pueda integrar los respectivos órdenes parciales locales). Con CO, los órdenes de precedencia son también los órdenes de compromiso. Cuando las bases de datos participantes en la misma transacción distribuida no tienen órdenes de precedencia locales compatibles para esa transacción (sin "saberlo"; normalmente no existe coordinación entre los sistemas de bases de datos en caso de conflictos, ya que la comunicación necesaria es masiva y degrada inaceptablemente el rendimiento), significa que la transacción reside en un ciclo global (que involucra dos o más bases de datos) en el gráfico de conflictos global. En este caso, el protocolo de compromiso atómico no podrá recolectar todos los votos necesarios para confirmar esa transacción: según la estrategia de orden de votos anterior, al menos una base de datos retrasará su votación para esa transacción indefinidamente para cumplir con su propio orden de compromiso (precedencia), ya que estará esperando la finalización de otra transacción precedente en ese ciclo global retrasada indefinidamente por otra base de datos con un orden diferente. Esto significa una situación de bloqueo de 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 una de esas transacciones le falta el voto de al menos un participante. La selección de la transacción específica en el ciclo que se abortará 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 mediante 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 la bloqueada (y por lo tanto bloqueadas) serán libres de votar. Vale la pena señalar que cada base de datos involucrada con el bloqueo de votación continúa votando regularmente sobre transacciones que no están en conflicto con su transacción bloqueada, típicamente casi todas las transacciones pendientes. Por lo tanto, en el caso de órdenes de compromiso locales (parciales) incompatibles, no es necesario realizar ninguna acción, ya que el protocolo de compromiso atómico lo resuelve automáticamente abortando 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 el CO global.
Se concluye lo siguiente:
CO global implica serialización global.
El algoritmo CO global comprende la aplicación de CO (local) en cada sistema de base de datos participante ordenando las confirmaciones de las transacciones locales (ver Aplicación de CO localmente a continuación) y la aplicación de la estrategia de ordenamiento de votos en el teorema anterior (para transacciones globales).
El proceso de eliminación del ciclo global antes mencionado mediante un bloqueo de la votación se puede explicar en detalle mediante la siguiente observación:
En primer lugar, se supone, para simplificar, que cada transacción alcanza el estado listo para confirmar y es votada por al menos una base de datos (esto implica que no se produce ningún bloqueo por bloqueos). Defina un gráfico de "esperar votación 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 de la segunda transacción (opuesto 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 votación para confirmar" es idéntico al gráfico de conflicto global. Un ciclo en el gráfico de "esperar votación para confirmar" 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 conflicto. 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 las transacciones bloqueadas con votos respectivos faltantes (bloqueados).
En segundo lugar, también se tratan los commits locales: Tenga en cuenta que al aplicar CO, también esperar un commit local regular de una transacción local puede bloquear los commits locales y las votaciones de otras transacciones en caso de conflictos, y la situación para las transacciones globales tampoco cambia sin la suposición simplificadora anterior: El resultado final es el mismo también con un compromiso local para transacciones locales, sin votar el compromiso atómico para ellas.
Por último, es necesario tener en cuenta el bloqueo por un bloqueo (que se ha excluido hasta ahora): un bloqueo bloquea una operación conflictiva y evita que se materialice un conflicto. Supongamos que el bloqueo se libera solo después de que finaliza la transacción. En ese caso, puede bloquear indirectamente una votación o una confirmación local de otra transacción (que ahora no puede llegar al estado listo), con el mismo efecto que un bloqueo directo de una votación o una confirmación local. Un ciclo se genera en el gráfico de conflictos solo si dicho bloqueo por un bloqueo también está representado por una arista. Con tales aristas agregadas que representan eventos de bloqueo por un bloqueo, el gráfico de conflictos se está convirtiendo en un gráfico de conflictos aumentado .
En presencia de CO, el gráfico de conflictos aumentado es, de hecho, un gráfico de espera de votación y confirmación local (de borde invertido) : existe un borde desde una primera transacción, ya sea local o global, hasta una segunda, si la segunda está esperando que finalice la primera para ser votada (si es global) o confirmada localmente (si es local). Todos los ciclos globales (en dos o más bases de datos) en este gráfico generan bloqueos de votación. Los ciclos globales del gráfico proporcionan una caracterización completa de los bloqueos de votación y pueden incluir cualquier combinación de conflictos materializados y no materializados. Solo los ciclos de conflictos (solo) materializados también son ciclos del gráfico de conflictos regular y afectan la serialización. Uno o más conflictos no materializados (relacionados con bloqueos) en un ciclo evitan que sea un ciclo en el gráfico de conflictos regular y lo convierten en un bloqueo relacionado con bloqueos. Todos los ciclos globales (bloqueos de votación) deben romperse (resolverse) para mantener la serialización global y resolver los bloqueos globales que involucran el bloqueo del acceso a los datos. De hecho, todos ellos están rotos por el protocolo de compromiso atómico debido a votaciones faltantes debido a un punto muerto en la votación.
Comentario: Esta observación también explica la corrección del CO extendido (ECO) que se muestra 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 someten a votación y sus confirmaciones (locales) no se bloquean en caso de conflicto. Esto da como resultado las mismas situaciones de bloqueo de votación y el proceso de eliminación del ciclo global resultante para ECO.
La situación de estancamiento en la votación se puede resumir de la siguiente manera:
Además, se concluye el siguiente caso especial basado en bloqueo:
Los puntos muertos en las votaciones son la clave para el funcionamiento del CO distribuido.
La eliminación de ciclos globales (aquí, resolución de bloqueos de votación por compromiso atómico ) y las ejecuciones de transacciones abortadas resultantes consumen 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 analogía completa con los ciclos/bloqueos generados en SS2PL local; con la distribución, cualquier coordinación de programación de transacciones u operaciones resulta en una violación de la autonomía y, por lo general, en una penalización sustancial del rendimiento). Sin embargo, su probabilidad se puede hacer muy baja en muchos casos implementando pautas de diseño de bases de datos y transacciones que reduzcan la cantidad de conflictos que involucran una transacción global. Esto, principalmente, manejando adecuadamente los puntos calientes (objetos de base de datos con acceso frecuente) y evitando conflictos mediante el uso de conmutatividad cuando sea posible (por ejemplo, cuando se usan ampliamente contadores, como en finanzas, y especialmente contadores de acumulación de múltiples transacciones , que generalmente son puntos calientes).
Los protocolos de compromiso atómico están pensados y diseñados para lograr atomicidad sin considerar el control de concurrencia de la base de datos. Se cancelan al detectar o encontrar heurísticamente (por ejemplo, por un tiempo de espera; a veces por error, innecesariamente) votos faltantes y, por lo general, no son conscientes de los ciclos globales. Estos protocolos se pueden mejorar especialmente para CO (incluidas las variantes de CO a continuación) para evitar cancelaciones innecesarias y acelerar las cancelaciones utilizadas para romper ciclos globales en el gráfico de conflicto global aumentado (para un mejor rendimiento mediante una liberación temprana al final de la transacción de los recursos informáticos y, por lo general, los datos bloqueados). Por ejemplo, los métodos de detección de bloqueo global basados en bloqueos existentes, distintos del tiempo de espera, se pueden generalizar también para considerar el bloqueo directo de votos y compromisos locales, además del bloqueo del acceso a los datos. Un posible compromiso en dichos mecanismos es detectar y cancelar 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 no detectados, mucho menos frecuentes y más largos.
El orden de compromiso se puede aplicar localmente (en una única base de datos) mediante un algoritmo de CO dedicado, o mediante cualquier algoritmo/protocolo que proporcione algún caso especial de CO. Un protocolo importante de este tipo, que se utiliza ampliamente en sistemas de bases de datos y que genera un cronograma de CO, es el protocolo de bloqueo estricto de dos fases (SS2PL: "liberar los bloqueos de la transacción solo después de que la transacción se haya confirmado o abortado"; consulte a continuación). SS2PL es un subconjunto adecuado de la intersección de 2PL y estrictez.
Un algoritmo CO local genérico (Raz 1992; Algoritmo 4.1) es un algoritmo independiente de los detalles de implementación que hace cumplir exactamente la propiedad CO. No bloquea el acceso a los datos (no es bloqueante) y consiste en abortar un determinado conjunto de transacciones (solo si es necesario) al confirmar una transacción. Aborta un conjunto mínimo (determinado de forma única en un momento dado) de otras transacciones no decididas (ni confirmadas ni abortadas) que se ejecutan localmente y que pueden causar una violación de serialización en el futuro (pueden generar más tarde ciclos de transacciones confirmadas en el gráfico de conflictos; este es el conjunto ABORT de una transacción confirmada T; después de confirmar T, no se puede confirmar ninguna transacción en ABORT en el momento de confirmación, y todas están condenadas a ser abortadas). Este conjunto consta de todas las transacciones no decididas con aristas dirigidas en el gráfico de conflictos a la transacción confirmada. El tamaño de este conjunto no puede aumentar cuando esa transacción está esperando ser confirmada (en el estado listo: el procesamiento ha terminado) 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 antes de confirmar 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 se deberán cancelar miembros del conjunto para romper los ciclos. Dado que en el caso de conflictos de CO se generan bloqueos en la confirmación, los ciclos locales en el gráfico de conflicto de aumentos (ver arriba) indican bloqueos de confirmación locales y se pueden usar técnicas de resolución de bloqueos como en SS2PL (por ejemplo, como timeout y wait-for graph ). Un ciclo local en el gráfico de conflicto aumentado con al menos un conflicto no materializado refleja un bloqueo basado en bloqueos. El algoritmo local anterior, aplicado al gráfico de conflicto aumentado local en lugar del gráfico de conflicto local regular, comprende el algoritmo de CO local mejorado genérico, un único mecanismo de eliminación de ciclo local, tanto para garantizar la serialización local como para gestionar bloqueos locales basados en bloqueos. 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 local cuando se ejecuta junto con cualquier otro mecanismo de control de concurrencia local. Afecta únicamente el orden de confirmación y, por esta razón, no necesita abortar más transacciones de las que se deben abortar para la prevención de violaciones de serialización por cualquier mecanismo de control de concurrencia local combinado. Como máximo, el efecto neto de CO puede ser un retraso de los eventos de confirmación (o votación en un entorno distribuido), para cumplir con el orden de confirmación necesario (pero no más retraso que sus casos especiales, por ejemplo, SS2PL, y en promedio significativamente menos).
Se concluye el siguiente teorema:
Con la proliferación de procesadores multinúcleo, las variantes del algoritmo CO local genérico también se han utilizado cada vez más en programación concurrente, memoria transaccional y, especialmente, en memoria transaccional de software para lograr 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.
Se supone que el sistema de base de datos se encuentra en un entorno de múltiples bases de datos. Desde el punto de vista de la arquitectura de software , un componente CO que implementa el algoritmo genérico de CO localmente, el Coordinador de Orden 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 es típicamente una parte integral del sistema de base de datos. Las funciones del COCO son votar para comprometer las transacciones globales listas (el procesamiento ha terminado) de acuerdo con el orden de compromiso local, votar para abortar las 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 pueden identificar), no se necesita votación. Para determinar el orden de compromiso, el COCO mantiene una representación actualizada del gráfico de conflictos local (o gráfico de conflictos local aumentado para capturar también bloqueos de bloqueo) de las transacciones no decididas (ni comprometidas ni abortadas) como una estructura de datos (por ejemplo, utilizando mecanismos similares al 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; preparación para votar sobre una transacción global o confirmar una local) y "abortar" 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 sobre 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 compromiso de las transacciones locales, en un orden de compromiso adecuado. El COCO, incluidas sus interfaces, se puede mejorar si implementa otra variante de CO (ver a continuación) o desempeña un papel en el mecanismo de control de concurrencia de la base de datos más allá de la votación en el compromiso atómico.
El COCO también garantiza el CO localmente en un único sistema de base de datos aislado, sin interfaz con un protocolo de compromiso atómico.
Supongamos que las bases de datos que participan en transacciones distribuidas (es decir, transacciones que abarcan más de una única base de datos) no utilizan ninguna información de control de concurrencia compartida y utilizan 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 serializabilidad global (una técnica de prueba se puede encontrar 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 una transacción . Significa que si no se cumple con CO, entonces no se puede garantizar la serializabilidad global 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 de protocolo de compromiso atómico). 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 la 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:
Utilizando esta definición se concluye lo siguiente:
Sin embargo, la definición de autonomía anterior implica, por ejemplo, que las transacciones se programen de manera que las transacciones locales (confinadas a una única 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 sistemas de base de datos de propósito general. Si la autonomía se aumenta con la capacidad de identificar transacciones locales, entonces el cumplimiento de una propiedad más general, el ordenamiento de compromiso extendido (ECO, por sus siglas en inglés, ver más abajo), hace que el ECO sea la condición necesaria.
Sólo en (Raz 2009) la noción de autonomía generalizada captura la noción pretendida de autonomía:
Esta definición es probablemente la más amplia posible en el contexto del control de concurrencia de bases de datos, y hace que CO junto con cualquiera de sus variantes generalizadoras (útil: sin distribución de información de control de concurrencia) (Orden de votos (VO); ver variantes de CO a continuación) sea la condición necesaria para la serialización global (es decir, la unión de CO y sus variantes generalizadoras es el conjunto necesario VO, que también puede incluir nuevas variantes generalizadoras útiles desconocidas).
La solución (técnica) de ordenamiento 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 multibase de datos cumple con CO, es decir, organiza los compromisos de sus transacciones locales y sus votos en transacciones (globales, distribuidas) al protocolo de compromiso atómico de acuerdo con el orden parcial local (a la base de datos) inducido por el gráfico de conflictos locales (gráfico de serialización) para las transacciones respectivas, entonces se garantizan CO global y 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 serialización de conflictos locales , sin afectar el proceso de ejecución o programación de ninguna transacción ni abortarlo. 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 bloqueo, pero sin bloqueo de acceso a datos; si no se detectan ya para otros fines) y el ordenamiento de los votos y los compromisos de transacciones locales de acuerdo con los conflictos.
En caso de órdenes parciales incompatibles de dos o más bases de datos (ninguna orden parcial global puede integrar las respectivas órdenes parciales locales), se genera un ciclo global (que abarca dos bases de datos o más) en el gráfico de conflictos globales. Esto, junto con el CO, da como resultado un ciclo de votos bloqueados. Se produce un bloqueo de votación para las bases de datos en ese ciclo (sin embargo, la votación simultánea permitida en cada base de datos, generalmente para casi todos los votos pendientes, continúa ejecutándose). En este caso, el protocolo de compromiso atómico no puede recopilar todos los votos necesarios para las transacciones bloqueadas en ese ciclo global. En consecuencia, el protocolo cancela algunas transacciones con un voto faltante. Esto rompe el ciclo global, se resuelve el bloqueo de votación y los votos bloqueados relacionados quedan libres para ejecutarse. Romper el ciclo global en el gráfico de conflictos globales garantiza 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 se necesita ninguna acción ya que el protocolo de compromiso atómico lo resuelve automáticamente cancelando una transacción que es una causa de la incompatibilidad. Además, los bloqueos globales debidos al bloqueo (ciclos globales en el gráfico de conflictos aumentado con al menos un bloqueo de acceso a datos) dan lugar a bloqueos en la 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 de protocolo de compromiso atómico (sin modificar), es decir, si las bases de datos son autónomas en el contexto del control de concurrencia. Esto significa que cada solución de serialización global para bases de datos autónomas debe cumplir con el CO. De lo contrario, la serialización global puede ser violada (y, por lo tanto, es probable que sea violada muy rápidamente en un entorno de alto rendimiento).
La solución CO se escala con el tamaño de la red y la cantidad de bases de datos sin afectar el rendimiento cuando utiliza una arquitectura de compromiso atómico distribuido común .
Una característica distintiva de la solución CO para la serialización distribuida con respecto a otras técnicas es el hecho de que no requiere información de conflicto distribuida (por ejemplo, relaciones de precedencia local, bloqueos, marcas de tiempo , tickets), lo que la hace excepcionalmente efectiva. En su lugar, utiliza mensajes de protocolo de compromiso atómico (sin modificar) (que ya se utilizan).
Una forma común de lograr 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 serialización distribuida en condiciones muy generales, sin un administrador de bloqueo distribuido, exhibiendo los beneficios ya explorados anteriormente para entornos de múltiples bases de datos; en particular: confiabilidad, alto rendimiento, escalabilidad, la posibilidad de usar control de concurrencia optimista cuando se desee, sin comunicaciones relacionadas con información de conflicto a través de la red (que han incurrido en sobrecarga y demoras) y resolución automática de bloqueos distribuidos .
Todos los sistemas transaccionales distribuidos dependen de algún protocolo de compromiso atómico para coordinar la atomicidad (ya sea para confirmar o abortar) entre los 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 deben confundirse con la propiedad de recuperabilidad de una programación) son accedidos directamente por un solo componente de administrador de datos transaccionales (también conocido como administrador de recursos ) que maneja subtransacciones locales (la parte de la transacción distribuida en una sola ubicación, por ejemplo, un nodo de red), incluso si estos datos son accedidos indirectamente por otras entidades en el sistema distribuido durante una transacción (es decir, el acceso indirecto requiere un acceso directo a través de una subtransacción local). Por lo tanto, los datos recuperables en un sistema transaccional distribuido generalmente se dividen entre los administradores de datos transaccionales. En dicho 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 (por ejemplo, mediante el uso de SS2PL, o COCO, o una combinación; ver arriba), entonces todo el sistema distribuido proporciona CO (por los teoremas anteriores; cada participante puede considerarse un objeto transaccional separado), y por lo tanto serializabilidad (distribuida). Además: Cuando CO se utiliza junto con un protocolo de compromiso atómico, también los bloqueos distribuidos (es decir, bloqueos que abarcan dos o más administradores de datos) causados por el bloqueo de acceso a los datos se resuelven automáticamente. Por lo tanto, se concluye el siguiente corolario:
Este teorema también significa que cuando SS2PL (o cualquier otra variante de CO) se utiliza localmente en cada administrador de datos transaccionales, y cada administrador de datos tiene control exclusivo de sus datos, no se necesita ningún administrador de bloqueo distribuido (que se utiliza a menudo para aplicar SS2PL distribuido) para la serialización y la SS2PL distribuida. Es relevante para una amplia gama de aplicaciones transaccionales distribuidas, que se pueden diseñar fácilmente para cumplir con las condiciones del teorema.
Para implementar el CO Optimista Distribuido (DOCO), se utiliza el algoritmo de CO local genérico en todos los participantes del protocolo de compromiso atómico en el sistema sin bloqueos de acceso a los datos y, por lo tanto, sin bloqueos locales. El teorema anterior tiene el siguiente corolario:
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 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 ambas 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), e y bajo el control exclusivo del administrador de datos en B.
Las respectivas subtransacciones locales en A y B (las porciones de y en cada uno de los nodos) son las siguientes:
La programación del sistema de base de datos en un momento determinado es la siguiente:
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 bloqueo distribuido, que también es un bloqueo de votación (ver más abajo) con un ciclo distribuido (global) de longitud 2 (número de aristas, conflictos; 2 es la longitud más frecuente). Las subtransacciones locales están en los siguientes estados:
Dado que el protocolo de compromiso atómico no puede recibir votos para subtransacciones bloqueadas (un bloqueo de votación), eventualmente abortará alguna transacción con uno o más votos faltantes antes de que se agote el tiempo de espera , ya sea , o , (o ambos, si los tiempos de espera son muy cercanos). Esto resolverá el bloqueo global. La transacción restante completará su ejecución, se votará y se confirmará. Una transacción abortada se reinicia y se vuelve a ejecutar de inmediato.
En el escenario anterior, ambos conflictos no se materializan y el bloqueo de votación global se refleja como un ciclo en el gráfico de espera global (pero no en el gráfico de conflictos globales ; consulte Caracterización exacta de bloqueos 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 situación de bloqueo de votación, y la misma resolución. Los conflictos pueden ser materializados o no materializados , según la variante de CO utilizada. Por ejemplo, si el sistema de base de datos distribuida utiliza SCO (a continuación) en lugar de SS2PL, entonces los dos conflictos en el ejemplo se materializan , todas las subtransacciones locales están en estados listos y se produce un bloqueo de votación 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 los conflictos, no se vota antes de que finalice, y no se vota antes de que finalice, lo que es un bloqueo de 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. Es poco probable que ocurra en un sistema de base de datos distribuida, pero es 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 en el gráfico de conflictos aumentado (la unión de los dos). Las distintas combinaciones se resumen en la siguiente tabla:
Comentario: Si bien los ejemplos anteriores describen la utilización real y recomendada de CO, este ejemplo es hipotético y solo tiene fines demostrativos.
Algunas bases de datos experimentales residentes en memoria distribuida abogan por entornos transaccionales de núcleos de subproceso único múltiples (MuSiC). "Un solo subproceso" se refiere únicamente a subprocesos de transacción y a la ejecución en serie de transacciones. El propósito es lograr posibles órdenes de magnitud de ganancia en el rendimiento (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 implementa de la manera convencional para CO distribuido, como se describió en secciones anteriores, entonces DOCO y Strictness existen automáticamente. Sin embargo, existen desventajas con esta implementación sencilla de dicho entorno, y su viabilidad 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 estas desventajas en la mayoría de las situaciones.
Comentario: La implementación sencilla de MuSiC descrita aquí (que utiliza, por ejemplo, como es habitual en CO distribuido, bloqueo de votación (y de hilo de transacción) en el protocolo de compromiso atómico cuando es necesario) es solo para demostración y no tiene conexión con la implementación en H-Store o cualquier otro proyecto.
En un entorno MuSiC, las programaciones locales son seriales . Por lo tanto, tanto la condición de estrategia de ordenamiento de votación de cumplimiento de CO global (CO Optimistic CO; ver más abajo) como la de CO Optimistic CO local 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) como la resolución automática de bloqueos globales (votación).
Además, también se sigue automáticamente la Estrictez local en un programa serial. Según el Teorema 5.2 de (Raz 1992; página 307), cuando se aplica la estrategia de ordenamiento de votos CO, también se garantiza la Estrictez global. Nótese que el modo serial local es el único que permite la rigurosidad y el "optimismo" (sin bloqueo de acceso a datos) juntos.
Se concluye lo siguiente:
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 generalizadoras (ECO y MVCO) contienen estrictamente la clase CO (es decir, también incluyen programaciones que no son compatibles con CO). Las variantes generalizadoras 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), al tiempo que relaja las restricciones de CO y utiliza información adicional (local) para una mejor concurrencia y rendimiento: ECO usa el conocimiento sobre las transacciones que son locales (es decir, confinadas a una sola base de datos), y MVCO usa la disponibilidad de valores de versiones de datos. Al igual que CO, ambas variantes generalizadoras son no 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 de 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 (incluidos ECO basados en múltiples versiones y MVECO). No se conocen otras variantes generalizadoras (que garanticen la serialización global sin distribución de información de control de concurrencia local), pero es posible que se descubran.
El bloqueo estricto fuerte de dos fases (SS2PL; también conocido como rigor o programación rigurosa ) significa que tanto los bloqueos de lectura como de escritura de una transacción se liberan solo después de que la transacción haya finalizado (ya sea confirmada o abortada). El conjunto de programaciones SS2PL es un subconjunto adecuado del conjunto de programaciones CO. Esta propiedad se utiliza ampliamente en sistemas de bases de datos y, dado que implica CO, las bases de datos que la utilizan y participan en transacciones globales generan juntas una programación global serializable (al utilizar cualquier protocolo de compromiso atómico, que es necesario para la atomicidad en un entorno de múltiples bases de datos). En este caso, no se necesita ninguna modificación o adición a la base de datos para participar en una solución distribuida CO: el conjunto de transacciones no decididas que se abortarán antes de confirmar en el algoritmo CO genérico local anterior está vacío debido a los bloqueos y, por lo tanto, dicho algoritmo es innecesario en este caso. Un sistema de base de datos puede votar una transacción inmediatamente después de entrar en un estado "listo", es decir, completar la ejecución de su tarea localmente. El sistema de base de datos libera sus bloqueos solo después de que el protocolo de compromiso atómico lo decida, y por lo tanto la condición del teorema de cumplimiento de CO global anterior se mantiene automáticamente. Si un sistema de base de datos utiliza un mecanismo de tiempo de espera local para resolver bloqueos SS2PL (locales), la interrupción de las transacciones bloqueadas no solo interrumpe los ciclos locales potenciales en el gráfico de conflictos globales (ciclos reales en el gráfico de conflictos aumentado), sino también los ciclos globales potenciales del sistema de base de datos como efecto secundario, si el mecanismo de interrupción del protocolo de compromiso atómico es relativamente lento. Tales interrupciones independientes por parte de varias entidades normalmente pueden dar como resultado interrupciones innecesarias 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 interrumpirá el ciclo global si el bloqueo de votación resultante no se resuelve antes en otra base de datos.
También se puede deducir directamente la SS2PL local junto con el compromiso atómico que implica serialización global: todas las transacciones, incluidas las distribuidas, obedecen las reglas de 2PL (SS2PL). El mecanismo del protocolo de compromiso atómico no es necesario aquí para el consenso sobre el compromiso, sino para el final del punto de sincronización de la fase dos. Probablemente por esta razón, sin considerar el mecanismo de votación del compromiso atómico, no se ha observado la resolución automática de bloqueos globales antes de CO.
El ordenamiento de compromiso estricto (SCO, por sus siglas en inglés; (Raz 1991c)) es la intersección de la estrictez (un caso especial de recuperabilidad) y el ordenamiento de compromiso estricto, y proporciona un límite superior para la concurrencia de una programación cuando existen ambas propiedades. Se puede implementar utilizando mecanismos de bloqueo (bloqueo) similares a los utilizados para el popular SS2PL con costos generales similares.
A diferencia de SS2PL, SCO no se bloquea en un conflicto de lectura-escritura, sino que posiblemente se bloquea en 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, las 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 a SCO, lo muestran claramente, con una ganancia de aproximadamente el 100% para algunas cargas de transacciones; también para cargas de transacciones idénticas, SCO puede alcanzar tasas de transacción más altas que SS2PL antes de que se produzca la superación de bloqueos ). Más concurrencia significa que con determinados recursos informáticos se completan más transacciones en la unidad de tiempo (mayor tasa de transacciones, rendimiento ) y la duración promedio de una transacción es más corta (finalización más rápida; consulte el gráfico). La ventaja de SCO es especialmente significativa durante la contención de bloqueos.
SCO es tan práctico como SS2PL ya que, como SS2PL, proporciona, además de serialización, también rigurosidad, que se utiliza ampliamente como base para la recuperación eficiente de bases de datos en caso de fallo. 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 una implementación SCO en (Perrizo y Tatarinov 1998). [7] Véase también Programador de bases de datos semioptimista .
SS2PL es un subconjunto adecuado de SCO (lo que constituye otra explicación de por qué SCO es menos restrictivo y proporciona más concurrencia que SS2PL).
Para implementar el ordenamiento de compromiso optimista (OCO), se utiliza el algoritmo de CO local genérico sin bloqueo de acceso a datos y, por lo tanto, sin bloqueos locales. El OCO sin restricciones de programación de transacciones u operaciones cubre toda la clase CO y no es un caso especial de la clase CO, sino más bien una variante útil de CO y una caracterización del mecanismo.
El orden de compromiso extendido (ECO; (Raz 1993a)) generaliza el CO. Cuando las transacciones locales (transacciones confinadas a una única 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 solo a las transacciones globales. 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 compromiso de transacciones globales únicamente (sin importancia para las transacciones locales) es coherente con su orden en el gráfico de conflictos local respectivo.
Existe un algoritmo distribuido para garantizar la existencia de 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).
Esta condición (ECO con serializabilidad local) es más débil que CO y permite mayor concurrencia a costa de un algoritmo local un poco más complicado (sin embargo, no existe ninguna diferencia práctica en términos de sobrecarga con CO).
Cuando se supone que todas las transacciones son globales (por ejemplo, si no hay información disponible sobre transacciones que son locales), ECO se reduce a CO.
Antes de que se confirme una transacción global, un algoritmo ECO genérico local (de una base de datos) aborta un conjunto mínimo de transacciones no decididas (ni confirmadas ni abortadas; ya sean transacciones locales o globales que se ejecutan localmente), que pueden causar más tarde un ciclo en el gráfico de conflictos. Este conjunto de transacciones abortadas (no únicas, al contrario de CO) se puede optimizar si se asigna a cada transacción un peso (que se puede determinar 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 se puede llevar a cabo, por ejemplo, mediante una reducción del problema de flujo máximo en redes (Raz 1993a)). Al igual que para CO, un conjunto de este tipo depende del tiempo y se vacía con el tiempo. En la práctica, casi en todas las implementaciones necesarias, una transacción debería confirmarse solo cuando el conjunto está vacío (y no es aplicable ninguna optimización de conjuntos). El mecanismo de control de concurrencia local (a la base de datos) (separado del algoritmo ECO) asegura que los ciclos locales sean eliminados (a diferencia de 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 pueden ser confirmadas concurrentemente (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 serializabilidad local) lo permite, también las transacciones globales pueden ser votadas para ser confirmadas concurrentemente (cuando todas sus transacciones globales transitivamente (indirectas) precedentes (a través del conflicto) son confirmadas, 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 CO distribuido, donde todas las transacciones transitivamente precedentes necesitan ser confirmadas).
La condición para garantizar el ECO Global se puede resumir de manera similar al CO:
La ECO global (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; se eliminan todos los ciclos locales) implican serialización global (se eliminan todos los ciclos). Esto significa que si cada sistema de base de datos en un entorno de múltiples bases de datos proporciona serialización local (por cualquier mecanismo) y aplica la estrategia de ordenamiento de votos del teorema anterior (una generalización de la estrategia de ordenamiento de votos de CO), entonces la serialización global está garantizada (ya no se necesita un CO local).
De manera similar a lo que ocurre con CO, la situación de estancamiento en la votación de ECO se puede resumir de la siguiente manera:
Al igual que con CO, esto significa que también los bloqueos globales debidos al bloqueo de acceso a datos (con al menos un bloqueo bloqueando) son bloqueos de votación y se resuelven automáticamente mediante compromiso atómico.
El ordenamiento 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 tales recursos es una forma común hoy en día de aumentar la concurrencia 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 que las operaciones de lectura de las transacciones sean de varias versiones relevantes (de cada objeto). MVCO implica una 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 presentada para MVCO, los conflictos se generalizan para diferentes versiones de un mismo recurso (a diferencia de las teorías de múltiples versiones anteriores). Para diferentes versiones, el orden cronológico de los conflictos se reemplaza por el orden de las versiones y posiblemente se invierte, mientras se mantienen las definiciones habituales para las operaciones en conflicto. Los resultados de los gráficos de conflicto regulares y aumentados no cambian y, de manera similar a CO, existe un algoritmo de aplicación de 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 múltiples versiones). 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 bloqueos globales basados en bloqueos se traducen en bloqueos de votación y se resuelven automáticamente. En analogía con CO, se cumple lo siguiente:
MVCO se puede generalizar aún más para emplear la generalización de ECO (MVECO).
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 de (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] consulte también Making snapshot insulation serializable y las referencias allí), para analizar conflictos en SI con el fin de hacerlo serializable. El método presentado en (Cahill et al. 2008), Serializable snapshot insulation (SerializableSI), una modificación de SI con baja sobrecarga, proporciona buenos resultados de rendimiento frente a SI, con solo una pequeña penalización por hacer cumplir 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, al ser compatible con MVCO, permite que los sistemas de bases de datos compatibles con COSI interoperan y participan de forma transparente en una solución CO para serialización distribuida/global (ver a continuación). Además de los costos generales, también es necesario comparar cuantitativamente los comportamientos de los protocolos. Por un lado, todos los cronogramas SI serializables pueden convertirse en MVCO mediante COSI (mediante posibles retrasos de confirmación cuando sea necesario) sin abortar transacciones. Por otro lado, se sabe que SerializableSI aborta y reinicia innecesariamente ciertos porcentajes de transacciones también en cronogramas SI serializables.
Con CO y sus variantes (por ejemplo, SS2PL, SCO, OCO, ECO y MVCO arriba) la serialización global se logra a través de 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 conflictos global aumentado (y por lo tanto también regular) (implícitamente; no se necesita una implementación de 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 bloqueo de votación relacionado con el acceso a los datos, ambos implicando un ciclo global en el gráfico de conflictos global aumentado y votos faltantes, el protocolo de compromiso atómico rompe dicho ciclo abortando una transacción no decidida en él (ver El algoritmo CO distribuido arriba). Las diferencias entre las diversas variantes existen solo a nivel local (dentro de los sistemas de bases de datos participantes). Cada instancia local de CO de cualquier variante tiene el mismo rol, determinar la posición de cada transacción global (una transacción que abarca dos o más bases de datos) dentro del orden de compromiso local, es decir, determinar cuándo es el turno de la transacción para ser votada localmente en el protocolo de compromiso atómico. Por lo tanto, todas las variantes de CO muestran el mismo comportamiento con respecto al compromiso atómico. Esto significa que todas son interoperables a través del compromiso atómico (usando las mismas interfaces de software, típicamente provistas como servicios , algunas ya estandarizadas para el compromiso atómico, principalmente para el protocolo de compromiso de dos fases , por ejemplo, X/Open XA ) y pueden utilizarse juntas de manera transparente en cualquier entorno distribuido (mientras que cada instancia de variante de CO posiblemente esté 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 procesos concurrentemente en cada una de esas bases de datos, y se ejecutan concurrentemente con transacciones locales y otras transacciones globales en cada una de esas bases 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 interrumpe por ningún aborto local) un bloqueo de votación que se resuelve por compromiso atómico exactamente de la misma manera que en un entorno de una única variante de CO. Los ciclos locales (ahora posiblemente con conflictos materializados y no materializados mixtos, tanto relacionados con la serialización como con el bloqueo de acceso a datos, por ejemplo, SCO) se resuelven localmente (cada uno por los mecanismos locales propios de su respectiva instancia de variante).
El ordenamiento de votos (VO o CO generalizado (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 el VO, se necesita serialización local (en su forma más general, basada en la conmutatividad e incluyendo multiversiones) y la estrategia de orden de votos (votación por orden de precedencia local).
Combinando los resultados de CO y sus variantes, se concluye lo siguiente:
