Protocolo de compromiso de dos fases

"2PC" vuelve a dirigir aquí. Para el juego en fútbol americano y canadiense, consulte Conversión de dos puntos . Para el protocolo criptográfico, consulte Esquema de compromiso .

En el procesamiento de transacciones , bases de datos y redes de computadoras , el protocolo de compromiso de dos fases ( 2PC ) es un tipo de protocolo de compromiso atómico (ACP). Es un algoritmo distribuido que coordina todos los procesos que participan en una transacción atómica distribuida sobre si confirmar o abortar ( revertir ) la transacción (es un tipo de consenso especializadoprotocolo). El protocolo logra su objetivo incluso en muchos casos de fallas temporales del sistema (que involucran fallas de procesos, nodos de red, comunicaciones, etc.) y, por lo tanto, se usa ampliamente. ^{[1] [2] [3]} Sin embargo, no es resistente a todas las posibles configuraciones de falla y, en casos raros, se necesita una intervención manual para remediar un resultado. Para adaptarse a la recuperación de fallas (automática en la mayoría de los casos), los participantes del protocolo utilizan el registro de los estados del protocolo. Los procedimientos de recuperación del protocolo utilizan registros de registro, que suelen ser lentos para generar pero que sobreviven a las fallas.. Existen muchas variantes de protocolo que difieren principalmente en las estrategias de registro y los mecanismos de recuperación. Aunque por lo general se pretende que se utilicen con poca frecuencia, los procedimientos de recuperación componen una parte sustancial del protocolo, debido a muchos posibles escenarios de fallas que el protocolo debe considerar y respaldar.

En una "ejecución normal" de una sola transacción distribuida (es decir, cuando no se produce ningún fallo, que suele ser la situación más frecuente), el protocolo consta de dos fases:

1. La fase de solicitud de compromiso (o fase de votación ), en la que un proceso de coordinación intenta preparar todos los procesos participantes de la transacción ( participantes nombrados , cohortes o trabajadores ) para tomar los pasos necesarios para comprometer o abortar la transacción y votar , ya sea "Sí": confirmar (si la ejecución de la porción local del participante de la transacción ha finalizado correctamente), o "No": cancelar (si se ha detectado un problema con la porción local), y
2. La fase de compromiso , en la que, basándose en la votación de los participantes, el coordinador decide si comprometer (solo si todos han votado "Sí") o abortar la transacción (en caso contrario), y notifica el resultado a todos los participantes. Luego, los participantes siguen con las acciones necesarias (confirmar o abortar) con sus recursos transaccionales locales (también llamados recursos recuperables ; por ejemplo, datos de base de datos) y sus respectivas partes en el otro resultado de la transacción (si corresponde).

Tenga en cuenta que el protocolo de compromiso de dos fases (2PC) no debe confundirse con el protocolo de bloqueo de dos fases (2PL), un protocolo de control de concurrencia .

Supuestos

El protocolo funciona de la siguiente manera: un nodo es un coordinador designado , que es el sitio maestro, y el resto de los nodos de la red se designan como participantes . El protocolo asume que hay un almacenamiento estable en cada nodo con un registro de escritura anticipada , que ningún nodo se bloquea para siempre, que los datos en el registro de escritura anticipada nunca se pierden ni se corrompen en una falla y que dos nodos pueden comunicarse con El uno al otro. La última suposición no es demasiado restrictiva, ya que la comunicación de red normalmente se puede desviar. Los dos primeros supuestos son mucho más sólidos; si un nodo se destruye por completo, se pueden perder datos.

El protocolo es iniciado por el coordinador después de que se haya alcanzado el último paso de la transacción. A continuación, los participantes responden con un mensaje de acuerdo o un mensaje de cancelación dependiendo de si la transacción se ha procesado correctamente en el participante.

Algoritmo básico

Fase de solicitud (o votación) de confirmación

1. El coordinador envía una consulta para enviar un mensaje a todos los participantes y espera hasta recibir una respuesta de todos los participantes.
2. Los participantes ejecutan la transacción hasta el punto en que se les pedirá que se comprometan. Cada uno escribe una entrada en su registro de deshacer y una entrada en su registro de rehacer .
3. Cada participante responde con un mensaje de acuerdo (el participante vota Sí para comprometerse), si las acciones del participante tuvieron éxito, o un mensaje de cancelación (el participante vota No , no comprometerse), si el participante experimenta una falla que hará que sea imposible comprometerse.

Fase de confirmación (o finalización)

Éxito

Si el coordinador recibió un mensaje de acuerdo de todos los participantes durante la fase de solicitud de compromiso:

1. El coordinador envía un mensaje de compromiso a todos los participantes.
2. Cada participante completa la operación y libera todos los bloqueos y recursos retenidos durante la transacción.
3. Cada participante envía un reconocimiento al coordinador.
4. El coordinador completa la transacción cuando se han recibido todos los reconocimientos.

Fracaso

Si algún participante vota No durante la fase de solicitud de compromiso (o el tiempo de espera del coordinador expira ):

1. El coordinador envía un mensaje de retroceso a todos los participantes.
2. Cada participante deshace la transacción utilizando el registro de deshacer y libera los recursos y bloqueos retenidos durante la transacción.
3. Cada participante envía un reconocimiento al coordinador.
4. El coordinador deshace la transacción cuando se han recibido todos los reconocimientos.

Flujo de mensajes

Participante Coordinador CONSULTA PARA COMPROMETER --------------------------------> VOTAR SÍ / NO preparar * / cancelar * <-------------------------------confirmar * / abortar * COMPROMISO / ROLLBACK --------------------------------> RECONOCIMIENTO cometer * / abortar * <-------------------------------- fin

Un * junto al tipo de registro significa que el registro está obligado a almacenamiento estable. ^[4]

Desventajas

La mayor desventaja del protocolo de confirmación de dos fases es que es un protocolo de bloqueo. Si el coordinador falla permanentemente, algunos participantes nunca resolverán sus transacciones: después de que un participante haya enviado un mensaje de acuerdo al coordinador, se bloqueará hasta que se reciba una confirmación o una reversión .

Implementación del protocolo de compromiso de dos fases

Arquitectura común

En muchos casos, el protocolo 2PC se distribuye en una red informática. Se distribuye fácilmente mediante la implementación de varios componentes dedicados de 2PC similares entre sí, normalmente denominados administradores de transacciones (TM; también denominados agentes 2PC o monitores de procesamiento de transacciones), que llevan a cabo la ejecución del protocolo para cada transacción (por ejemplo, The Open Group ' s X / Abrir XA ). Las bases de datos involucradas con una transacción distribuida, los participantes , tanto el coordinador como los participantes, se registranpara cerrar TM (que normalmente residen en los mismos nodos de red respectivos que los participantes) para terminar esa transacción usando 2PC. Cada transacción distribuida tiene un conjunto ad hoc de TM, las TM en las que se registran los participantes de la transacción. Un líder, el coordinador TM, existe para cada transacción para coordinar 2PC para ella, generalmente el TM de la base de datos del coordinador. Sin embargo, el rol de coordinador se puede transferir a otra MT por razones de desempeño o confiabilidad. En lugar de intercambiar mensajes 2PC entre ellos, los participantes intercambian los mensajes con sus respectivas TM. Los TM relevantes se comunican entre sí para ejecutar el esquema de protocolo 2PC anterior, "representando" a los participantes respectivos, para terminar esa transacción.Con esta arquitectura, el protocolo está completamente distribuido (no necesita ningún componente de procesamiento central o estructura de datos) y se escala con la cantidad de nodos de red (tamaño de la red) de manera efectiva.

Esta arquitectura común también es eficaz para la distribución de otros protocolos de compromiso atómico además de 2PC, ya que todos estos protocolos utilizan el mismo mecanismo de votación y propagación de resultados a los participantes del protocolo. ^{[1] [2]}

Optimizaciones de protocolo

Se han realizado investigaciones en bases de datos sobre formas de obtener la mayoría de los beneficios del protocolo de compromiso de dos fases mientras se reducen los costos mediante optimizaciones de protocolo ^{[1] [2] [3]} y ahorro de operaciones de protocolo bajo ciertos supuestos de comportamiento del sistema.

Supuesto aborto y presunto compromiso

El supuesto aborto o el supuesto compromiso son optimizaciones habituales. ^{[2] [3] [5]}Una suposición sobre el resultado de las transacciones, ya sea de confirmación o de cancelación, puede guardar tanto los mensajes como las operaciones de registro de los participantes durante la ejecución del protocolo 2PC. Por ejemplo, cuando se presume que se canceló, si durante la recuperación del sistema después de una falla no se encuentra evidencia registrada para el compromiso de alguna transacción mediante el procedimiento de recuperación, entonces asume que la transacción ha sido abortada y actúa en consecuencia. Esto significa que no importa si los abortos se registran en absoluto, y dicho registro se puede guardar bajo esta suposición. Normalmente, se paga una penalización de operaciones adicionales durante la recuperación de un error, según el tipo de optimización. Por lo tanto, la mejor variante de optimización, si la hay, se elige de acuerdo con las estadísticas de fallas y resultados de transacciones.

Protocolo de confirmación de árbol en dos fases

El protocolo Tree 2PC ^[2] (también llamado Nested 2PC o Recursive 2PC ) es una variante común de 2PC en una red informática , que utiliza mejor la infraestructura de comunicación subyacente. Los participantes en una transacción distribuida se invocan normalmente en un orden que define una estructura de árbol, el árbol de invocación, donde los participantes son los nodos y los bordes son las invocaciones (enlaces de comunicación). El mismo árbol se utiliza comúnmente para completar la transacción mediante un protocolo 2PC, pero también se puede utilizar otro árbol de comunicación para esto, en principio. En un árbol 2PC, el coordinador se considera la raíz ("superior") de un árbol de comunicación (árbol invertido), mientras que los participantes son los otros nodos. El coordinador puede ser el nodo que originó la transacción (invocado recursivamente (transitivamente) a los otros participantes), pero también otro nodo en el mismo árbol puede tomar el rol de coordinador. Los mensajes de 2PC del coordinador se propagan "hacia abajo" en el árbol, mientras que los mensajes para el coordinador son "recopilados" por un participante de todos los participantes debajo de él, antes de enviar el mensaje correspondiente "hacia arriba".el árbol (excepto unmensaje de aborto , que se propaga "hacia arriba" inmediatamente después de recibirlo o si el participante actual inicia el aborto).

El protocolo de compromiso dinámico de dos fases ( compromiso dinámico de dos fases, D2PC) ^{[2] [6]} es una variante del árbol 2PC sin un coordinador predeterminado. Incluye varias optimizaciones que se han propuesto anteriormente. Los mensajes de acuerdo ( votos de Sí ) comienzan a propagarse desde todas las hojas, cada hoja al completar sus tareas en nombre de la transacción ( preparándose ). Un nodo intermedio (no hoja) envía listo cuando un mensaje de acuerdo al último (único) nodo vecino desde el cual aún no se ha recibido el mensaje de acuerdo . El coordinador se determina dinámicamente por acuerdo de carrera.mensajes sobre el árbol de transacciones, en el lugar donde chocan. Chocan en un nodo del árbol de transacciones, para ser el coordinador o en el borde de un árbol. En el último caso, uno de los nodos de los dos bordes se elige como coordinador (cualquier nodo). D2PC es el tiempo óptimo (entre todas las instancias de un árbol de transacciones específico y cualquier implementación del protocolo Tree 2PC específico; todas las instancias tienen el mismo árbol; cada instancia tiene un nodo diferente como coordinador): Al elegir un coordinador óptimo, D2PC compromete tanto al coordinador y cada participante en el mínimo tiempo posible, permitiendo la liberación más temprana posible de los recursos bloqueados en cada participante de la transacción (nodo de árbol).

Ver también

• Compromiso atómico
• Comprometerse (gestión de datos)
• Protocolo de compromiso trifásico
• XA
• Algoritmo de Paxos
• El problema de dos generales

Referencias

1. Philip A. Bernstein , Vassos Hadzilacos, Nathan Goodman (1987): Control de concurrencia y recuperación en sistemas de bases de datos , Capítulo 7, Addison Wesley Publishing Company, ISBN  0-201-10715-5
2. Gerhard Weikum , Gottfried Vossen (2001): Sistemas de información transaccional , Capítulo 19, Elsevier, ISBN 1-55860-508-8 
3. Philip A. Bernstein, Eric Newcomer (2009): Principles of Transaction Processing , 2nd Edition Archivado el 7 de agosto de 2010 en Wayback Machine , Capítulo 8, Morgan Kaufmann (Elsevier), ISBN 978-1-55860-623 -4 
4. C. Mohan , Bruce Lindsay y R. Obermarck (1986): "Gestión de transacciones en el sistema de gestión de bases de datos distribuidas R *" , ACM Transactions on Database Systems (TODS) , Volumen 11 Número 4, diciembre de 1986, páginas 378 - 396
5. C. Mohan , Bruce Lindsay (1985): "Protocolos de compromiso eficientes para el modelo de árbol de procesos de transacciones distribuidas" , Revisión de sistemas operativos ACM SIGOPS , 19 (2), págs. 40-52 (abril de 1985)
6. Yoav Raz (1995): "El protocolo de compromiso dinámico de dos fases (D2PC)" , Teoría de la base de datos - ICDT '95 , Lecture Notes in Computer Science , Volumen 893/1995, págs. 162-176, Springer, ISBN 978-3- 540-58907-5 

Enlaces externos

• Protocolo de confirmación de dos fases explicado en imágenes por exploreDatabase