Protocole de validation en deux phases - Two-phase commit protocol

« 2PC » redirige ici. Pour le jeu dans le football américain et canadien, voir Conversion en deux points . Pour le protocole cryptographique, voir Schéma d'engagement .

Dans le traitement des transactions , les bases de données et les réseaux informatiques , le protocole de validation en deux phases ( 2PC ) est un type de protocole d'engagement atomique (ACP). Il s'agit d'un algorithme distribué qui coordonne tous les processus qui participent à une transaction atomique distribuée sur l'opportunité de valider ou d'abandonner (annuler) la transaction (c'est un type spécialisé de protocole de consensus ). Le protocole atteint son objectif même dans de nombreux cas de défaillance temporaire du système (impliquant des défaillances de processus, de nœud de réseau, de communication, etc.) et est donc largement utilisé. Cependant, il n'est pas résilient à toutes les configurations de défaillance possibles et, dans de rares cas, une intervention manuelle est nécessaire pour remédier à un résultat. Pour permettre la récupération après un échec (automatique dans la plupart des cas), les participants au protocole utilisent la journalisation des états du protocole. Les enregistrements de journal, qui sont généralement lents à générer mais survivent aux échecs, sont utilisés par les procédures de récupération du protocole . Il existe de nombreuses variantes de protocole qui diffèrent principalement par les stratégies de journalisation et les mécanismes de récupération. Bien que généralement destinées à être utilisées rarement, les procédures de récupération constituent une partie substantielle du protocole, en raison de nombreux scénarios de défaillance possibles à prendre en compte et à prendre en charge par le protocole.

Dans une "exécution normale" d'une seule transaction distribuée (c'est-à-dire lorsqu'aucun échec ne se produit, ce qui est généralement la situation la plus fréquente), le protocole se compose de deux phases :

  1. La phase de demande de validation (ou phase de vote), dans laquelle un processus de coordination tente de préparer tous les processus participants de la transaction (participants nommés, cohortes ou travailleurs) pour prendre les mesures nécessaires pour valider ou annuler la transaction et pour voter, soit « Oui » : valider (si l'exécution de la partie locale du participant à la transaction s'est terminée correctement), ou « Non » : abandonner (si un problème a été détecté avec la partie locale), et
  2. La phase de validation, au cours de laquelle, sur la base du vote des participants, le coordinateur décide de valider (uniquement si tous ont voté « Oui ») ou d'annuler la transaction (sinon), et notifie le résultat à tous les participants. Les participants effectuent ensuite les actions nécessaires (validation ou annulation) avec leurs ressources transactionnelles locales (également appelées ressources récupérables ; par exemple, les données de base de données) et leurs portions respectives dans l'autre sortie de la transaction (le cas échéant).

Le protocole de validation en deux phases (2PC) ne doit pas être confondu avec le protocole de verrouillage en deux phases (2PL), un protocole de contrôle de la concurrence .

Hypothèses

Le protocole fonctionne de la manière suivante : un nœud est un coordinateur désigné, qui est le site maître, et les autres nœuds du réseau sont désignés comme participants. Le protocole suppose qu'il existe un stockage stable sur chaque nœud avec un journal d'écriture anticipée , qu'aucun nœud ne tombe en panne pour toujours, que les données du journal d'écriture anticipée ne sont jamais perdues ou corrompues lors d'un crash, et que deux nœuds peuvent communiquer avec l'un l'autre. La dernière hypothèse n'est pas trop restrictive, car la communication réseau peut généralement être réacheminée. Les deux premières hypothèses sont beaucoup plus fortes ; si un nœud est totalement détruit, des données peuvent être perdues.

Le protocole est initié par le coordinateur après avoir atteint la dernière étape de la transaction. Les participants répondent ensuite par un message d'accord ou un message d'abandon selon que la transaction a été traitée avec succès chez le participant.

Algorithme de base

Phase de demande d'engagement (ou de vote)

  1. Le coordinateur envoie un message de demande de validation à tous les participants et attend d'avoir reçu une réponse de tous les participants.
  2. Les participants exécutent la transaction jusqu'au point où il leur sera demandé de s'engager. Ils écrivent chacun une entrée dans leur journal d'annulation et une entrée dans leur journal de rétablissement .
  3. Chaque participant répond par un message d'accord (le participant vote Oui pour s'engager), si les actions du participant ont réussi, ou un message d'abandon (le participant vote Non, pour ne pas s'engager), si le participant rencontre un échec qui le rendra impossible à s'engager.

Phase d'engagement (ou d'achèvement)

Succès

Si le coordinateur a reçu un message d'accord de tous les participants pendant la phase de demande de validation :

  1. Le coordinateur envoie un message d'engagement à tous les participants.
  2. Chaque participant termine l'opération et libère tous les verrous et ressources détenus pendant la transaction.
  3. Chaque participant envoie un accusé de réception au coordinateur.
  4. Le coordinateur termine la transaction lorsque tous les accusés de réception ont été reçus.

Échec

Si un participant vote Non pendant la phase de demande de validation (ou si le délai d'expiration du coordinateur expire) :

  1. Le coordinateur envoie un message d'annulation à tous les participants.
  2. Chaque participant annule la transaction à l'aide du journal d'annulation et libère les ressources et les verrous détenus pendant la transaction.
  3. Chaque participant envoie un accusé de réception au coordinateur.
  4. Le coordinateur annule la transaction lorsque tous les accusés de réception ont été reçus.

Flux de messages

Coordinator                                          Participant
                             QUERY TO COMMIT
                 -------------------------------->
                             VOTE YES/NO             prepare*/abort*
                 <-------------------------------
commit*/abort*               COMMIT/ROLLBACK
                 -------------------------------->
                             ACKNOWLEDGMENT          commit*/abort*
                 <--------------------------------  
end

Un * à côté du type d'enregistrement signifie que l'enregistrement est forcé à un stockage stable.

Désavantages

Le plus grand inconvénient du protocole de validation en deux phases est qu'il s'agit d'un protocole bloquant. Si le coordinateur échoue définitivement, certains participants ne résoudront jamais leurs transactions : après qu'un participant a envoyé un message d'accord au coordinateur, celui-ci se bloquera jusqu'à ce qu'un commit ou un rollback soit reçu.

Implémentation du protocole de commit en deux phases

Architecture commune

Dans de nombreux cas, le protocole 2PC est distribué dans un réseau informatique. Il est facilement distribué en implémentant plusieurs composants 2PC dédiés similaires les uns aux autres, généralement nommés Transaction Managers (TM; également appelés agents 2PC ou Transaction Processing Monitors), qui effectuent l'exécution du protocole pour chaque transaction (par exemple, The Open Group ' s X/Ouvrir XA ). Les bases de données impliquées dans une transaction distribuée, les participants, à la fois le coordinateur et les participants, s'enregistrent pour fermer les TM (résidant généralement sur les mêmes nœuds de réseau respectifs que les participants) pour mettre fin à cette transaction à l'aide de 2PC. Chaque transaction distribuée a un ensemble ad hoc de MT, les MT auxquelles les participants à la transaction s'enregistrent. Un leader, le coordinateur TM, existe pour chaque transaction afin de coordonner 2PC pour elle, typiquement le TM de la base de données du coordinateur. Cependant, le rôle de coordinateur peut être transféré à une autre TM pour des raisons de performances ou de fiabilité. Plutôt que d'échanger des messages 2PC entre eux, les participants échangent les messages avec leurs MT respectifs. Les TM concernés communiquent entre eux pour exécuter le schéma de protocole 2PC ci-dessus, "représentant" les participants respectifs, pour mettre fin à cette transaction. Avec cette architecture, le protocole est entièrement distribué (ne nécessite aucun composant de traitement central ou structure de données) et s'adapte efficacement au nombre de nœuds du réseau (taille du réseau).

Cette architecture commune est également efficace pour la distribution d'autres protocoles d'engagement atomique en plus de 2PC, puisque tous ces protocoles utilisent le même mécanisme de vote et la même propagation des résultats aux participants au protocole.

Optimisations de protocole

Des recherches dans les bases de données ont été effectuées sur les moyens d'obtenir la plupart des avantages du protocole de validation en deux phases tout en réduisant les coûts grâce à des optimisations de protocole et à des opérations de protocole économisant sous certaines hypothèses de comportement du système.

Abandon présumé et commit présumé

L'abandon présumé ou la validation présumée sont de telles optimisations courantes. Une hypothèse sur le résultat des transactions, soit commit, soit abort, peut sauver à la fois les messages et les opérations de journalisation par les participants pendant l'exécution du protocole 2PC. Par exemple, en cas d'abandon présumé, si pendant la récupération du système suite à un échec, aucune preuve consignée pour la validation d'une transaction n'est trouvée par la procédure de récupération, alors elle suppose que la transaction a été abandonnée et agit en conséquence. Cela signifie qu'il n'a pas d'importance si les abandons sont enregistrés, et une telle journalisation peut être enregistrée dans cette hypothèse. En règle générale, une pénalité d'opérations supplémentaires est payée lors de la récupération après une défaillance, en fonction du type d'optimisation. Ainsi, la meilleure variante d'optimisation, le cas échéant, est choisie en fonction des statistiques d'échec et de résultat des transactions.

Protocole de validation en deux phases de l'arborescence

Le protocole Tree 2PC (également appelé Nested 2PC ou Recursive 2PC) est une variante courante de 2PC dans un réseau informatique , qui utilise mieux l'infrastructure de communication sous-jacente. Les participants à une transaction distribuée sont généralement appelés dans un ordre qui définit une structure arborescente, l'arbre d'invocation, où les participants sont les nœuds et les bords sont les invocations (liens de communication). Le même arbre est couramment utilisé pour terminer la transaction par un protocole 2PC, mais un autre arbre de communication peut également être utilisé pour cela, en principe. Dans un arbre 2PC le coordinateur est considéré comme la racine ("top") d'un arbre de communication (arbre inversé), tandis que les participants sont les autres nœuds. Le coordinateur peut être le nœud à l'origine de la transaction (invoqué de manière récursive (transitivement) par les autres participants), mais un autre nœud du même arbre peut également assumer le rôle de coordinateur. Les messages 2PC du coordinateur sont propagés "en bas" de l'arbre, tandis que les messages au coordinateur sont "collectés" par un participant à partir de tous les participants en dessous, avant d'envoyer le message approprié "en haut" de l'arbre (sauf un message d'abandon, qui est propagé « up » immédiatement après sa réception ou si le participant actuel initie l'abandon).

Le protocole Dynamic two-phase commit (Dynamic two-phase commit, D2PC) est une variante de Tree 2PC sans coordinateur prédéterminé. Il englobe plusieurs optimisations qui ont été proposées précédemment. Les messages d'accord (votes Oui) commencent à se propager à partir de toutes les feuilles, chaque feuille lorsqu'elle termine ses tâches au nom de la transaction (se prépare). Un nœud intermédiaire (non feuille) envoie prêt lorsqu'un message d'accord est envoyé au dernier (unique) nœud voisin dont le message d'accord n'a pas encore été reçu. Le coordinateur est déterminé dynamiquement par la course des messages d'accord sur l'arbre de transaction, à l'endroit où ils entrent en collision. Ils entrent en collision soit au niveau d'un nœud d'arbre de transaction, pour être le coordinateur, soit sur un bord d'arbre. Dans ce dernier cas, l'un des deux nœuds du bord est élu comme coordinateur (n'importe quel nœud). D2PC est optimal dans le temps (parmi toutes les instances d'un arbre de transaction spécifique et toute implémentation de protocole Tree 2PC spécifique ; toutes les instances ont le même arbre ; chaque instance a un nœud différent en tant que coordinateur) : en choisissant un coordinateur optimal, D2PC engage à la fois le coordinateur et chaque participant dans un temps minimum possible, permettant la libération la plus tôt possible des ressources verrouillées dans chaque participant à la transaction (nœud d'arborescence).

Voir également

Les références