Hispanopedia Wiki
Articulo de referencia

Protocolo de compromiso en dos fases

Una secuencia típica de una confirmación en dos fases. En el procesamiento de transacciones , bases de datos y redes informáticas , el protocolo de confirmación en dos fases ( 2...

Hispanopedia WikiContenido en espanolLectura gratuita
Una secuencia típica de una confirmación en dos fases.

En el procesamiento de transacciones , bases de datos y redes informáticas , el protocolo de confirmación en dos fases ( 2PC , tupac ) es un tipo de protocolo de confirmación atómica (ACP). Es un algoritmo distribuido que coordina todos los procesos que participan en una transacción atómica distribuida para decidir si confirmar o abortar (revertir) la transacción. Este protocolo (un tipo especializado de protocolo de consenso ) logra su objetivo incluso en muchos casos de fallos temporales del sistema (que involucran fallos de procesos, nodos de red , comunicación, etc.), y por lo tanto es ampliamente utilizado. [ 1 ] [ 2 ] [ 3 ] Sin embargo, no es resistente a todas las posibles configuraciones de fallo y, en raras ocasiones, se requiere intervención manual para remediar un resultado. Para permitir la recuperación de fallos (automática en la mayoría de los casos), los participantes del protocolo utilizan el registro de los estados del protocolo. Los registros, que suelen ser lentos de generar pero sobreviven a los fallos, son utilizados por los procedimientos de recuperación del protocolo . Existen muchas variantes del protocolo que difieren principalmente en las estrategias de registro y los mecanismos de recuperación. Aunque generalmente se prevé que se utilicen con poca frecuencia, los procedimientos de recuperación constituyen una parte sustancial del protocolo, debido a los numerosos escenarios de fallo posibles que deben considerarse y estar contemplados en el protocolo.

En una "ejecución normal" de cualquier transacción distribuida individual (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 confirmación (o fase de votación), en la que un proceso coordinador intenta preparar a todos los procesos participantes de la transacción (denominados participantes, cohortes o trabajadores) para que tomen los pasos necesarios para confirmar o abortar la transacción y votar, ya sea "Sí": confirmar (si la ejecución de la parte local del participante de la transacción ha finalizado correctamente), o "No": abortar (si se ha detectado un problema con la parte local), y
  2. La fase de confirmación, en la que, basándose en la votación de los participantes, el coordinador decide si confirmar la transacción (solo si todos han votado "Sí") o cancelarla (en caso contrario), y notifica el resultado a todos los participantes. A continuación, los participantes realizan las acciones necesarias (confirmar o cancelar) con sus recursos transaccionales locales (también llamados recursos recuperables; por ejemplo, datos de la base de datos) y sus respectivas partes en la otra salida de la transacción (si corresponde).

El protocolo de confirmación en dos fases (2PC) no debe confundirse con el protocolo de bloqueo en dos fases (2PL), que es un protocolo de control de concurrencia .

Supuestos

El protocolo funciona de la siguiente manera: un nodo es el coordinador designado, que es el sitio maestro, y el resto de los nodos de la red son los participantes. El protocolo asume que:

  1. Hay almacenamiento estable en cada nodo con un registro de escritura anticipada ,
  2. ningún nodo falla para siempre,
  3. Los datos en el registro de escritura anticipada nunca se pierden ni se corrompen en caso de un fallo, y
  4. Cualquier par de nodos puede comunicarse entre sí.

La última suposición no es demasiado restrictiva, ya que la comunicación en la red generalmente se puede redirigir. Las dos primeras suposiciones son mucho más estrictas: si un nodo se destruye por completo, se pueden perder datos.

El coordinador inicia el protocolo una vez alcanzado el último paso de la transacción. Los participantes responden entonces con un mensaje de confirmación o de cancelación, según si la transacción se ha procesado correctamente en su sistema.

Algoritmo básico

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

  1. El coordinador envía una consulta para confirmar el mensaje a todos los participantes y espera hasta recibir una respuesta de todos ellos.
  2. Los participantes ejecutan la transacción hasta el punto en que se les pedirá que la confirmen. Cada uno escribe una entrada en su registro de deshacer y una entrada en su registro de rehacer .
  3. Cada participante responde con:
ya sea un mensaje de acuerdo ( el participante vota Sí para comprometerse), si las acciones del participante tuvieron éxito;
o un mensaje de aborto (el participante vota No a confirmar), si el participante experimenta un fallo que le impedirá confirmar.

Fase de compromiso (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 confirmación 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 acuse de recibo al coordinador.
  4. El coordinador finaliza la transacción una vez recibidas todas las confirmaciones.

Falla

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

  1. El coordinador envía un mensaje de reversión a todos los participantes.
  2. Cada participante deshace la transacción utilizando el registro de deshacer y libera los recursos y bloqueos mantenidos durante la misma.
  3. Cada participante envía un acuse de recibo al coordinador.
  4. El coordinador deshace la transacción una vez recibidas todas las confirmaciones.

Flujo de mensajes

Coordinador Participante CONSULTA PARA CONFIRMAR --------------------------------> VOTE SÍ/NO preparar*/abortar* <------------------------------- Confirmar*/abortar* CONFIRMAR/RETROCEDER --------------------------------> ACUSE DE RECIBO commit*/abort* <-------------------------------- fin

Un * junto al tipo de registro significa que el registro se fuerza al almacenamiento permanente. [ 4 ]

Desventajas

  1. La principal desventaja del protocolo de confirmación en dos fases es que se trata de un protocolo de bloqueo.
  2. Si el coordinador falla de forma permanente, algunos participantes nunca resolverán sus transacciones: después de que un participante haya enviado un mensaje de acuerdo como respuesta al mensaje de solicitud de confirmación del coordinador, se bloqueará hasta que se reciba una confirmación o una reversión.
  3. Un protocolo de confirmación en dos fases no puede recuperarse de forma fiable si tanto el coordinador como un miembro del grupo fallan durante la fase de confirmación. Si solo falla el coordinador y ningún miembro del grupo recibe un mensaje de confirmación, se puede inferir con seguridad que no se ha producido ninguna confirmación. Sin embargo, si fallan tanto el coordinador como un miembro del grupo, es posible que este último haya sido el primero en ser notificado y, por lo tanto, haya realizado la confirmación. Incluso si se selecciona un nuevo coordinador, este no puede continuar con la operación con seguridad hasta que reciba el acuerdo de todos los miembros del grupo y, por consiguiente, debe bloquearse hasta que todos respondan.

Implementación del protocolo de confirmación en dos fases

Arquitectura común

En muchos casos, el protocolo 2PC se distribuye en una red informática. Su distribución se facilita mediante la implementación de múltiples componentes 2PC dedicados y similares entre sí, generalmente denominados gestores de transacciones (TM; también conocidos como agentes 2PC o monitores de procesamiento de transacciones), que ejecutan el protocolo para cada transacción (por ejemplo, X/Open XA de The Open Group ). Las bases de datos involucradas en una transacción distribuida, los participantes (tanto el coordinador como los participantes) se registran para cerrar los TM (generalmente ubicados en los mismos nodos de red que los participantes) para finalizar dicha transacción mediante 2PC. Cada transacción distribuida tiene un conjunto ad hoc de TM, a los que se registran los participantes. Existe un líder, el TM coordinador, para cada transacción, que coordina el 2PC para ella; normalmente, el TM de la base de datos coordinadora. Sin embargo, la función de coordinador puede transferirse a otro TM por motivos de rendimiento o fiabilidad. En lugar de intercambiar mensajes 2PC entre sí, los participantes intercambian los mensajes con sus respectivos TM. Los TM relevantes se comunican entre sí para ejecutar el esquema del protocolo 2PC descrito anteriormente, "representando" a los participantes respectivos, para finalizar dicha transacción. Con esta arquitectura, el protocolo es totalmente distribuido (no requiere ningún componente de procesamiento central ni estructura de datos ) y se escala eficazmente con el número de nodos de la red (tamaño de la red).

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 parte de los beneficios del protocolo de confirmación de dos fases, reduciendo al mismo tiempo los costos mediante optimizaciones del protocolo [ 1 ] [ 2 ] [ 3 ] y ahorrando operaciones del protocolo bajo ciertas suposiciones sobre el comportamiento del sistema.

Aborto presunto y confirmación presunta

El aborto presunto o la confirmación presunta son optimizaciones comunes de este tipo. [ 2 ] [ 3 ] [ 5 ] Una suposición sobre el resultado de las transacciones, ya sea confirmación o aborto, puede ahorrar tanto mensajes como operaciones de registro por parte de los participantes durante la ejecución del protocolo 2PC. Por ejemplo, cuando se presume el aborto, si durante la recuperación del sistema tras un fallo no se encuentra ninguna evidencia registrada de la confirmación de alguna transacción mediante el procedimiento de recuperación, entonces se asume que la transacción ha sido abortada y se actúa en consecuencia. Esto significa que no importa si los abortos se registran en absoluto, y dicho registro puede ahorrarse bajo esta suposición. Normalmente se paga una penalización de operaciones adicionales durante la recuperación tras un fallo, dependiendo del 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 fallos y resultados de transacciones.

Protocolo de confirmación de dos fases en árbol

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 aprovecha mejor la infraestructura de comunicación subyacente. Los participantes en una transacción distribuida se invocan típicamente en un orden que define una estructura de árbol, el árbol de invocación, donde los participantes son los nodos y las aristas son las invocaciones (enlaces de comunicación). El mismo árbol se utiliza comúnmente para completar la transacción mediante un protocolo 2PC, pero en principio también se puede utilizar otro árbol de comunicación para este fin. En un Tree 2PC, el coordinador se considera la raíz ("cima") de un árbol de comunicación (árbol invertido), mientras que los participantes son los demás nodos. El coordinador puede ser el nodo que originó la transacción (invocando recursivamente (transitivamente) a los demás participantes), pero también otro nodo en el mismo árbol puede asumir el rol de coordinador. Los mensajes 2PC del coordinador se propagan "hacia abajo" en el árbol, mientras que los mensajes dirigidos al coordinador son "recopilados" por un participante de todos los participantes que se encuentran debajo de él, antes de que este envíe el mensaje apropiado "hacia arriba" en el árbol (excepto un mensaje de aborto, que se propaga "hacia arriba" inmediatamente después de recibirlo o si el participante actual inicia el aborto).

El protocolo Dynamic two-phase commit (D2PC) [ 2 ] [ 6 ] es una variante de Tree 2PC sin coordinador predeterminado. Engloba varias optimizaciones propuestas anteriormente. Los mensajes de acuerdo (votos de "Sí") comienzan a propagarse desde todas las hojas, cada una al completar sus tareas en nombre de la transacción (quedando lista). Un nodo intermedio (no hoja) envía un mensaje de acuerdo al último nodo vecino del que aún no ha recibido un mensaje de acuerdo. El coordinador se determina dinámicamente mediante la concurrencia de mensajes de acuerdo en el árbol de transacciones, en el punto donde colisionan. La colisión se produce en un nodo del árbol de transacciones, que será el coordinador, o en una arista del árbol. En este último caso, se elige como coordinador uno de los dos nodos de la arista (cualquier nodo). D2PC es óptimo en cuanto al tiempo (entre todas las instancias de un árbol de transacciones específico y cualquier implementación específica del protocolo Tree 2PC; 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 como a cada participante en el menor tiempo posible, lo que permite la liberación más temprana posible de los recursos bloqueados en cada participante de la transacción (nodo del árbol).

Véase también

Referencias

  1. 1 2 3 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. 1 2 3 4 5 6 Gerhard Weikum , Gottfried Vossen (2001): Sistemas de información transaccional , Capítulo 19, Elsevier, ISBN 1-55860-508-8
  3. 1 2 3 Philip A. Bernstein, Eric Newcomer (2009): Principios del procesamiento de transacciones , 2.ª edición, 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 confirmación eficientes para el modelo de árbol de procesos de transacciones distribuidas" , ACM SIGOPS Operating Systems Review , 19(2), pp. 40-52 (abril de 1985)
  6. ↑ Yoav Raz (1995): "El protocolo de compromiso dinámico de dos fases (D2PC)" , Database Theory — ICDT '95 , Lecture Notes in Computer Science , Volumen 893/1995, pp. 162-176, Springer, ISBN 978-3-540-58907-5