stringtranslate.com

Protocolo de confirmación de 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 sobre 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 falla temporal del sistema (que involucran fallas de proceso, nodo de red, comunicación, etc.) y, por lo tanto, se usa ampliamente. [1] [2] [3] Sin embargo, no es resistente a todas las configuraciones de falla posibles y, en casos raros, se necesita una intervención manual para remediar un resultado. Para dar cabida a la recuperación de la falla (automática en la mayoría de los casos), los participantes del protocolo utilizan el registro de los estados del protocolo. Los registros de registro, que normalmente son lentos de generar pero sobreviven a las fallas, son utilizados por los procedimientos de recuperación del protocolo . Existen muchas variantes de protocolo que difieren principalmente en las estrategias de registro y los mecanismos de recuperación. Aunque generalmente están pensados ​​para usarse con poca frecuencia, los procedimientos de recuperación componen una parte sustancial del protocolo, debido a los muchos escenarios de falla posibles que el protocolo debe considerar y respaldar.

En una "ejecución normal" de cualquier 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 confirmación (o fase de votación), en la que un proceso coordinador intenta preparar a todos los procesos participantes de la transacción (participantes nombrados, cohortes o trabajadores) para que tomen los pasos necesarios para confirmar o abortar la transacción y votar "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, en función de la votación de los participantes, el coordinador decide si se confirma (solo si todos han votado "Sí") o se cancela la transacción (en caso contrario), y notifica el resultado a todos los participantes. Los participantes luego 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 porciones en el resto de la salida de la transacción (si corresponde).

El protocolo de confirmación 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 el coordinador designado, que es el sitio maestro, y el resto de los nodos de la red son los participantes designados. El protocolo supone que:

  1. Hay un almacenamiento estable en cada nodo con un registro de escritura anticipada ,
  2. Ningún nodo se bloquea para siempre,
  3. Los datos en el registro de escritura anticipada nunca se pierden ni se corrompen en caso de falla, y
  4. Dos nodos cualesquiera pueden comunicarse entre sí.

El último supuesto no es demasiado restrictivo, ya que la comunicación de la red normalmente se puede redireccionar. Los dos primeros supuestos son mucho más sólidos: si un nodo se destruye por completo, se pueden perder los datos.

El protocolo lo inicia el coordinador una vez que se ha alcanzado el último paso de la transacción. Los participantes responden con un mensaje de aceptación o de cancelación, dependiendo de si la transacción se ha procesado correctamente en el participante.

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 los participantes.
  2. Los participantes ejecutan la transacción hasta el punto en el que se les solicita 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 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 para comprometerse), si el participante experimenta una falla que hará imposible comprometerse.

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 confirmación:

  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 acuse de recibo al coordinador.
  4. El coordinador completa la transacción cuando se han recibido todos los reconocimientos.

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 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 acuse de recibo al coordinador.
  4. El coordinador deshace la transacción cuando se han recibido todos los reconocimientos.

Flujo de mensajes

Coordinador Participante CONSULTA PARA COMPROBAR --------------------------------> VOTA SI/NO prepara*/aborta* <-------------------------------confirmar*/abortar* CONFIRMACIÓN/ROLLBACK --------------------------------> RECONOCIMIENTO commit*/abort* <-------------------------------- fin

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

Desventajas

  1. La mayor desventaja del protocolo de confirmación de dos fases es que es un protocolo de bloqueo.
  2. Si el coordinador falla permanentemente, 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 manera confiable de una falla tanto del coordinador como de un miembro de la cohorte durante la fase de confirmación. Si solo el coordinador hubiera fallado y ningún miembro de la cohorte hubiera recibido un mensaje de confirmación, se podría inferir con seguridad que no se produjo ninguna confirmación. Sin embargo, si tanto el coordinador como un miembro de la cohorte fallaron, es posible que el miembro de la cohorte que falló haya sido el primero en recibir la notificación y que haya realizado la confirmación. Incluso si se selecciona un nuevo coordinador, no puede proceder con confianza con la operación hasta que haya recibido el acuerdo de todos los miembros de la cohorte y, por lo tanto, debe bloquear hasta que todos los miembros de la cohorte respondan.

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

Arquitectura común

En muchos casos, el protocolo 2PC se distribuye en una red informática. Se distribuye fácilmente implementando múltiples componentes 2PC dedicados similares entre sí, normalmente denominados gestores 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, X/Open XA de The Open Group ). Las bases de datos implicadas en una transacción distribuida, los participantes, tanto el coordinador como los participantes, se registran para cerrar los TM (que normalmente residen en los mismos nodos de red respectivos que los participantes) para finalizar esa transacción utilizando 2PC. Cada transacción distribuida tiene un conjunto ad hoc de TM, los TM en los que se registran los participantes de la transacción. 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, el papel de coordinador se puede transferir a otro TM por razones de rendimiento o fiabilidad. En lugar de intercambiar mensajes 2PC entre ellos, los participantes intercambian los mensajes con sus respectivos TM. Los TM pertinentes se comunican entre sí para ejecutar el esquema de protocolo 2PC mencionado anteriormente, "representando" a los participantes respectivos, para finalizar esa transacción. Con esta arquitectura, el protocolo está completamente distribuido (no necesita ningún componente de procesamiento central ni 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 efectiva 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 de bases de datos sobre formas de obtener la mayoría de los beneficios del protocolo de confirmación de dos fases y al mismo tiempo reducir los costos mediante optimizaciones de protocolo [1] [2] [3] y ahorros en las operaciones de protocolo bajo ciertos supuestos de comportamiento del sistema.

Presunto aborto y presunto compromiso

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

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 típicamente 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 ("parte 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 (invoca recursivamente (transitivamente) a los otros participantes), pero también otro nodo en el mismo árbol puede asumir el papel de coordinador en su lugar. Los mensajes 2PC del coordinador se propagan "hacia abajo" del árbol, mientras que los mensajes al coordinador son "recogidos" por un participante de todos los participantes que se encuentran debajo de él, antes de enviar el mensaje apropiado "hacia arriba" del á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 de confirmación dinámica en dos fases (Dynamic two-phase commit, D2PC) [2] [6] es una variante de Tree 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 cuando completa sus tareas en nombre de la transacción (está lista). Un nodo intermedio (que no es una hoja) envía un mensaje de listo cuando se envía un mensaje de acuerdo al último nodo vecino (único) del cual aún no se ha recibido el mensaje de acuerdo. El coordinador se determina dinámicamente haciendo que los mensajes de acuerdo se transmitan por el árbol de transacciones, en el lugar donde colisionan. Colisionan en un nodo del árbol de transacciones, para ser el coordinador, o en un borde del árbol. En el último caso, uno de los nodos de los dos bordes se elige como coordinador (cualquier nodo). D2PC es óptimo en términos de 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 mínimo 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. ^ abc 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. ^ abcdef Gerhard Weikum , Gottfried Vossen (2001): Sistemas de información transaccional, capítulo 19, Elsevier, ISBN 1-55860-508-8 
  3. ^ abc 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)", Teoría de bases de datos — ICDT '95 , Apuntes de clase sobre informática , Volumen 893/1995, págs. 162-176, Springer, ISBN 978-3-540-58907-5