Verrouillage à deux phases

Verrouillage à deux phasesModifier

Selon le protocole de verrouillage à deux phases, une transaction gère ses verrous en deux phases distinctes et consécutives pendant l’exécution de la transaction :

1. Phase d’expansion (alias phase de croissance) : des verrous sont acquis et aucun verrou n’est libéré (le nombre de verrous ne peut qu’augmenter).
2. Phase de décroissance (alias phase de contraction) : des verrous sont libérés et aucun verrou n’est acquis.

Les règles de verrouillage en deux phases peuvent être résumées comme suit : ne jamais acquérir un verrou après qu’un verrou ait été libéré. La propriété de sérialisation est garantie pour un planning avec des transactions qui obéissent à cette règle.

Typiquement, sans connaissance explicite dans une transaction sur la fin de la phase 1, il est déterminé en toute sécurité seulement quand une transaction a terminé le traitement et a demandé le commit. Dans ce cas, tous les verrous peuvent être libérés en une seule fois (phase 2).

Verrouillage conservateur à deux phasesEdit

La différence entre 2PL et C2PL est que les transactions de C2PL obtiennent tous les verrous dont elles ont besoin avant que les transactions ne commencent. Ceci afin de garantir qu’une transaction qui détient déjà certains verrous ne se bloque pas en attendant d’autres verrous. Le 2PL conservateur empêche les blocages.

Verrouillage biphasé strictEdit

Pour être conforme au protocole S2PL, une transaction doit se conformer au 2PL, et libérer ses verrous d’écriture (exclusifs) seulement après qu’elle se soit terminée, c’est-à-dire en étant soit commise, soit avortée. D’autre part, les verrous de lecture (partagés) sont libérés régulièrement pendant la phase 2. Ce protocole n’est pas approprié dans les B-trees car il provoque un goulot d’étranglement (alors que les B-trees commencent toujours la recherche à partir de la racine parentale).

Strong strict two-phase lockingEdit

or Rigorousness, or Rigorous scheduling, or Rigorous two-phase locking

Pour se conformer au strong strict two-phase locking (SS2PL), le protocole de verrouillage libère les verrous d’écriture (exclusifs) et de lecture (partagés) appliqués par une transaction uniquement après la fin de la transaction, c’est-à-dire, seulement après avoir terminé l’exécution (être prêt) et avoir été validé ou interrompu. Ce protocole est également conforme aux règles S2PL. Une transaction obéissant à SS2PL peut être considérée comme ayant une phase 1 qui dure toute la durée d’exécution de la transaction, et aucune phase 2 (ou une phase 2 dégénérée). Ainsi, il ne reste en fait qu’une seule phase, et le terme « biphase » dans le nom semble être encore utilisé en raison du développement historique du concept à partir de 2PL, et 2PL étant une super-classe. La propriété SS2PL d’un horaire est également appelée Rigueur. C’est aussi le nom de la classe de planifications ayant cette propriété, et une planification SS2PL est aussi appelée une « planification rigoureuse ». Le terme « Rigueur » est libre de l’héritage inutile de « deux phases », et est indépendant de tout mécanisme (de blocage) (en principe, d’autres mécanismes de blocage peuvent être utilisés). Le mécanisme de verrouillage respectif de la propriété est parfois appelé 2PL Rigoureux.

SS2PL est un cas particulier de S2PL, c’est-à-dire que la classe d’ordonnancements SS2PL est une sous-classe propre de S2PL (chaque ordonnancement SS2PL est également un ordonnancement S2PL, mais il existe des ordonnancements S2PL qui ne sont pas SS2PL).

SS2PL a été le protocole de contrôle de concurrence de choix pour la plupart des systèmes de base de données et utilisé depuis leurs débuts dans les années 1970. Il s’est avéré être un mécanisme efficace dans de nombreuses situations, et fournit en plus de la sérialisation également la rigueur (un cas particulier de la récupérabilité sans cascade), qui est instrumentale pour la récupération efficace de la base de données, et aussi l’ordre d’engagement (CO) pour participer à des environnements distribués où une sérialisation distribuée basée sur CO et des solutions de sérialisation globale sont employées. Étant un sous-ensemble de CO, une mise en œuvre efficace de SS2PL distribué existe sans gestionnaire de verrouillage distribué (DLM), tandis que les blocages distribués (voir ci-dessous) sont résolus automatiquement. Le fait que SS2PL utilisé dans les systèmes de bases de données multiples assure la sérialisation globale était connu depuis des années avant la découverte de CO, mais ce n’est qu’avec CO que l’on a compris le rôle d’un protocole d’engagement atomique dans le maintien de la sérialisation globale, ainsi que l’observation de la résolution automatique des blocages distribués (voir un exemple détaillé de SS2PL distribué). En fait, SS2PL hérite des propriétés de Récupérabilité et de CO, ce qui est plus significatif que d’être un sous-ensemble de 2PL, qui par lui-même dans sa forme générale, en plus de comprendre un simple mécanisme de sérialisation (cependant la sérialisation est également impliquée par CO), n’est pas connu pour fournir à SS2PL toute autre qualité significative. 2PL dans sa forme générale, ainsi que lorsqu’elle est combinée avec Strictness, c’est-à-dire 2PL Strict (S2PL), ne sont pas connus pour être utilisés dans la pratique. La populaire SS2PL ne nécessite pas de marquer la « fin de la phase 1 » comme le font 2PL et S2PL, et est donc plus simple à mettre en œuvre. De plus, contrairement à la 2PL générale, la SS2PL fournit, comme mentionné ci-dessus, les propriétés utiles de Strictness et Commitment ordering.

Il existe de nombreuses variantes de la SS2PL qui utilisent divers types de verrou avec diverses sémantiques dans différentes situations, y compris les cas de changement de type de verrou pendant une transaction. Notamment les variantes qui utilisent le verrouillage à granularité multiple.

1. SS2PL vs. S2PL : Les deux fournissent la sérialisation et la rigueur. Comme S2PL est une superclasse de SS2PL, il peut, en principe, fournir plus de concurrence. Toutefois, aucun avantage en termes de concurrence n’est généralement perceptible dans la pratique (le verrouillage est exactement le même pour les deux, avec une libération des verrous à peine plus précoce pour S2PL), et les frais généraux liés à la gestion d’un mécanisme de fin de phase 1 dans S2PL, distinct de la fin de la transaction, ne sont pas justifiés. De plus, alors que SS2PL fournit l’ordre d’engagement, S2PL ne le fait pas. Ceci explique la préférence de SS2PL sur S2PL.
2. En particulier avant 1990, mais aussi après, dans de nombreux articles et livres, par exemple (Bernstein et al. 1987, p. 59), le terme « Strict 2PL » (S2PL) a été fréquemment défini par le protocole de verrouillage « Release all locks only after transaction end », qui est le protocole de SS2PL. Ainsi, « Strict 2PL » ne pourrait pas être là le nom de l’intersection de Strictness et 2PL, qui est plus large que la classe générée par le protocole SS2PL. Cela a provoqué une certaine confusion. Avec une définition explicite de S2PL comme l’intersection de Strictness et 2PL, un nouveau nom pour SS2PL, et une distinction explicite entre les classes S2PL et SS2PL, les articles (Breitbart et al. 1991) et (Raz 1992) ont voulu dissiper la confusion : le premier utilisant le nom de « rigueur », et le second « SS2PL. »
3. Il existe une propriété plus générale que SS2PL (une super-classe d’ordonnancement), le Strict commitment ordering (Strict CO, ou SCO), qui assure aussi bien la sérialisation, la rigueur, que le CO, et présente un surcoût de verrouillage similaire. Contrairement à SS2PL, SCO ne bloque pas lors d’un conflit de lecture-écriture (un verrou de lecture ne bloque pas l’acquisition d’un verrou d’écriture ; SCO et SS2PL ont le même comportement pour les conflits d’écriture-lecture et d’écriture-écriture) au prix d’un éventuel retard de validation, et lors d’un tel type de conflit, SCO a un temps moyen d’achèvement de transaction plus court et de meilleures performances que SS2PL. Alors que SS2PL obéit à la table de compatibilité des verrous ci-dessus, SCO a la table suivante :

Notez que bien que SCO libère tous les verrous à la fin de la transaction et se conforme aux règles de verrouillage 2PL, SCO n’est pas un sous-ensemble de 2PL en raison de sa table de compatibilité des verrous différente. SCO autorise les conflits matérialisés en lecture-écriture entre deux transactions dans leurs phases 1, ce que 2PL n’autorise pas en phase 1 (voir à propos des conflits matérialisés dans Serializability). D’autre part, 2PL autorise d’autres types de conflits matérialisés en phase 2 que SCO n’autorise pas du tout. L’ensemble de ces éléments implique que les classes d’ordonnancement 2PL et SCO sont incomparables (c’est-à-dire qu’aucune classe ne contient l’autre classe).

Résumé – Relations entre les classesEdit

Confinement des classes d’horaire : Une flèche allant de la classe A à la classe B indique que la classe A contient strictement B ; l’absence de chemin dirigé entre les classes signifie que les classes sont incomparables. Une propriété est intrinsèquement bloquante, si elle ne peut être appliquée qu’en bloquant les opérations d’accès aux données de la transaction jusqu’à ce que certains événements se produisent dans d’autres transactions. (Raz 1992)

Entre deux classes d’horaires quelconques (définies par les propriétés respectives de leurs horaires) qui ont des horaires communs, soit l’une contient l’autre (contient strictement si elles ne sont pas égales), soit elles sont incomparables. Les relations de confinement entre les classes 2PL et les autres principales classes d’horaires sont résumées dans le diagramme suivant. 2PL et ses sous-classes sont intrinsèquement bloquants, ce qui signifie qu’il n’existe pas d’implémentation optimiste pour eux (et chaque fois que « 2PL optimiste » est mentionné, cela fait référence à un mécanisme différent avec une classe qui inclut également des horaires qui ne sont pas dans la classe 2PL).