8. Contrôle de concurrence

Un SGBD doit garantir que l’exécution d’un programme effectuant des mises à jour dans un contexte multi-utisateur s’effectue “correctement”. Bien entendu la signification du “correctement” doit être définie précisément, de même que les techniques assurant cette correction : c’est l’objet du contrôle de concurrence.

S1: Les mécanismes

Supports complémentaires:

Le contrôle de concurrence est la partie de l’activité d’un SGBD qui consiste à ordonner l’exécution des transactions de manière à assurer la sérialisabilité et la recouvrabilité. Nous donnons ci-dessous un aperçu des différentes techniques utilisées, toujours dans l’optique de fournir au programmeur d’applications de bases de données une idée au moins intuitive des mécanismes sous-jacents au déroulement d’une application. Nous commençons donc par décrire les mécanismes assurant la recouvrabilité, avant de passer à la gestion de la sérialisabilité.

Versionnement

Il existe toujours deux choix possibles pour une transaction \(T\) en cours : effectuer un commit pour valider définitivement les opérations effectuées, ou un rollback pour les annuler. Pour que ces choix soient toujours disponibles, le SGBD doit maintenir, pendant l’exécution de T, deux versions des données mises à jour :

  • une version des données après la mise à jour ;
  • une version des données avant la mise à jour.

Ces deux versions sont stockées dans deux espaces de stockage séparés, que nous désignerons respectivement par les termes d’image après et d’image avant dans ce qui suit. Conceptuellement (les détails pouvant être assez compliqués), le déroulement d’une transaction T, basé sur ces deux images, s’effectue de la manière suivante. Chaque fois que T effectue la mise à jour d’un tuple, la version courante est d’abord copiée dans l’image avant, puis remplacée par la nouvelle valeur fournie par T. Dès lors le commit et le rollback sont implantés comme suit :

  • le commit consiste à s’assurer que les données de l’image après sont vraiment écrites sur disque, afin de garantir la durabilité ; l’image avant peut alors être effacée ;
  • le rollback prend les tuples de l’image avant et les écrit dans l’image après pour ramener la base à l’état initial de la transaction.

Un rollback effectué à la suite d’une panne fonctionne de la même manière, sous réserve bien entendu que la panne n’ait pas affecté l’image avant elle-même. Il est donc très important de s’assurer que les données de l’image avant sont régulièrement écrites sur disque. Pour des raisons de performance (répartition des entrées/sorties) et de minimisation des risques, on choisit d’ailleurs quand c’est possible de placer l’image avant et l’image après sur des disques différents.

Quand T effectue des lectures sur des données qu’elles vient de modifier, le système doit lire dans l’image après pour assurer une vision cohérente de la base, reflétant les opérations effectuées par une transaction. En revanche, quand c’est une autre transaction T’ qui demande la lecture d’un tuple modifié par T, il faut lire dans l’image avant pour éviter les effets de lectures sales.

On peut se poser la question du nombre de versions nécessaires. Que se passe-t-il par exemple quand T’ demande la mise à jour d’un tuple déjà modifié par T ? Si cette mise à jour était autorisée, il s’agirait d’une écriture sale et il faudrait prendre garde à créer une troisième version du tuple, l’image avant de T’ étant l’image après de T. La multiplication des versions rendrait la gestion des commit et rollback extrêmement complexe. En pratique les systèmes n’autorisent pas les écritures sales, s’appuyant pour contrôler cette règle sur des mécanismes de verrouillage exclusif qui seront présentés dans ce qui suit. Il s’ensuit que la gestion de la recouvrabilité ne nécessite pas plus de deux versions pour chaque tuple, une dans l’image avant et l’autre dans l’image après.

Le versionnement n’est pas seulement utile à la gestion de la recouvrabilité. Reprenons le problème des lectures non répétables. Elles sont dues au fait qu’une transaction T lit un tuple t qui a été modifié par une transaction T’après le début de T. Or, quand T’ modifie t, il existe avant la validation deux versions de t  : l’image avant et l’image après.

Il suffirait que T lise toujours l’image avant pour que le problème des tuples fantômes soit résolu. En d’autres termes ces images avant peuvent être vues comme un “cliché” de la base pris à un moment donné, et toute transaction ne lit que dans le cliché valide au moment où elle a débuté. De nombreux SGBD (dont ORACLE, PostgreSQL, MySQL/InnoDB) proposent un mécanisme de lecture cohérente basé sur ce système de versionnement qui s’appuie sur les principes suivants :

  • chaque transaction T se voit attribuer, quand elle débute, une estampille temporelle \(e_T\) ; chaque valeur d’estampille est unique et les valeurs sont croissantes : on garantit ainsi un ordre total entre les transactions.
  • chaque version validée d’un tuple a est de même estampillée par le moment \(e_a\) de sa validation ;
  • quand T doit lire un tuple a, le système regarde dans l’image après. Si t a été modifié par T ou si son estampille est inférieure à \(e_T\), le tuple peut être lu puisqu’il a été validé avant le début de T, sinon T recherche dans l’image avant la version de t validée et immédiatement antérieure à \(e_T\).

La seule extension nécessaire par rapport à l’algorithme de gestion de la recouvrabilité est la non-destruction des images avant, même quand la transaction qui a modifié le tuple valide par commit. L’image avant contient alors toutes les versions successives d’un tuple, marquées par leur estampille temporelle. Seule la plus récente de ces versions correspond à une mise à jour en cours. Les autres ne servent qu’à assurer la cohérence des lectures.

La figure Lectures cohérentes avec image avant illustre le mécanisme de lecture cohérente. La transaction \(T_{23}\) a débuté à l’instant 23. Elle a modifié à l’instant 25 l’enregistrement e3, et la version précédente (dont l’estampille est 14) de e3 a été placée dans l’image avant. Maintenant, si \(T_{23}\) effectue une lecture, celle-ci accède à la version de \(e_3\) placée dans l’image après puisque c’est elle qui l’a modifiée. En revanche une transaction \(T'_{18}\) dont le moment de début est 18 lira la version de e3 dans l’image avant (il y a un pointeur de l’image avant vers l’image après).

En d’autres termes l’image avant peut être vue comme un “cliché” de la base pris à un moment donné, et toute transaction ne lit que dans le cliché “valide” au moment où elle a débuté.

_images/imageavant.png

Fig. 8.1 Lectures cohérentes avec image avant

L’image avant contient en revanche l’historique de toutes les versions successives d’un enregistrement, marquées par leur estampille temporelle. Seule la plus récente de ces versions correspond à une mise à jour en cours. Les autres ne servent qu’à assurer la cohérence des lectures. Certaines de ces versions n’ont plus aucune chance d’être utilisées : ce sont celles pour lesquelles il existe une version plus récente, antérieure à toutes les requêtes en cours. Cette propriété permet au SGBD d’effectuer un nettoyage (garbage collection) des versions devenues inutiles.

Verrouillage

Le mécanisme de versionnement décit ci-dessus est nécessaire mais pas suffisant pour assurer la recouvrabilité et la sérialisabilité des exécutions concurrentes. Le contrôle de concurrence doit parfois effectuer un réordonnancement de l’ordre d’arrivée des opérations pour assurer ces deux propriétés.

La technique la plus fréquente est basée sur le verrouillage des tuples lus ou mis à jour. L’idée est simple : chaque transaction désirant lire ou écrire un tuple doit auparavant obtenir un verrou sur ce tuple. Une fois obtenu (sous certaines conditions explicitées ci-dessous), le verrou reste détenu par la transaction qui l’a posé, jusqu’à ce que cette transaction décide de relâcher le verrou.

Il existe essentiellement deux types de verrous :

  • les verrous partagés autorisent la pose d’autres verrous partagés sur le même tuple.
  • les verrous exclusifs interdisent la pose de tout autre verrou, exclusif ou partagé, et donc de toute lecture ou écriture par une autre transaction.

On ne peut poser un verrou partagé que s’il n’y a que des verrous partagés sur le tuple. On ne peut poser un verrou exclusif que s’il n’y a aucun autre verrou, qu’il soit exclusif ou partagé. Les verrous sont posés par chaque transaction, et ne sont libérés qu’au moment du commit ou rollback.

Dans ce qui suit les verrous en lecture seront notés rl (comme read lock) dans ce qui suit, et ses verrous en écritures seront notés wl (comme write lock). Donc \(rl_i[x]\) indique par exemple que la transaction i a posé un verrou en lecture sur la resource x. On notera de même ru et wu le relâchement des verrous (read unlock et write unlock).

Il ne peut y avoir qu’un seul verrou exclusif sur un tuple. Son obtention par une transaction T suppose donc qu’il n’y ait aucun verrou déjà posé par une autre transaction T’. En revanche il peut y avoir plusieurs verrous partagés : l’obtention d’un verrou partagé est possible sur un tuple tant que ce tuple n’est pas verrouillé exclusivement par une autre transaction. Enfin, si une transaction est la seule à détenir un verrou partagé sur un tuple, elle peut poser un verrou exclusif.

Si une transaction ne parvient pas à obtenir un verrou, elle est mise en attente, ce qui signifie que la transaction s’arrête complètement jusqu’à ce que le verrou soit obtenu. Rappelons qu’une transaction est une séquence d’opérations, et qu’il n’est évidemment pas question de changer l’ordre, ce qui reviendrait à modifier la sémantique du programme. Quand une opération n’obtient pas de verrou, elle est mise en attente ainsi que toutes celles qui la suivent pour la même transaction.

Les verrous sont posés de manière automatique par le SGBD en fonction des opérations effectuées par les transactions/utilisateurs. Il est également possible de demander explicitement le verrouillage de certaines ressources (tuple ou même table) (cf. chapitre d’introduction à la concurrence).

Tous les algorithmes de gestion de la concurrence (voir les deux présentés ci-dessous) utilisent le verrouillage. L’idée générale est de bloquer l’accès à une donnée dès qu’elle est lue ou écrite par une transaction (“pose de verrou”) et de libèrer cet accès quand la transaction termine par commit ou rollback (“libération du verrou”).

En reprenant l’exemple de la réservation, et en supposant que tout accès en lecture ou en écriture pose un verrou bloquant les autres transactions, les transactions \(T_1\) et \(T_2\) s’exécuteront clairement en série et les anomalies disparaîtront. Le bloquage systématique des transactions est cependant une contrainte trop forte. L’exécution est correcte, mais le verrouillage total bloquerait pourtant sans nécessité la transaction \(T_2\).

Un bon algorithme doit garantir la sérialisabilité et la recouvrabilité au prix d’un minimum de blocages. On peut réduire ce blocage en jouant sur deux critères:

  • le degré de restriction (verrou partagé ou verrou exclusif) ;
  • la granularité du verrouillage (i.e. le niveau de la ressource à laquelle il s’applique : tuple, page, table, etc).

Tous les SGBD proposent un verrouillage au niveau du tuple, et privilégient les verrous partagés tant que cela ne remet pas en cause la correction des exécutions concurrentes. Un verrouillage au niveau du tuple est considéré comme moins pénalisant pour la fluidité, puisqu’il laisse libres d’autres transactions d’accéder à tous les autres tuples non verrouillés. Il existe cependant des cas où cette méthode est inappropriée. Si par exemple un programme parcourt une table avec un curseur pour modifier chaque tuple, et valide à la fin, on va poser un verrou sur chaque alors qu’on aurait obtenu un résultat équivalent avec un seul verrou au niveau de la table.

Note

Certains SGBD pratiquent également l’escalade des verrous : quand plus d’une certaine fraction des tuples d’une table est verrouillée, le SGBD passe automatiquement à un verrouillage au niveau de la table. Sinon on peut envisager, en tant que programmeur, la pose explicite d’un verrou exclusif sur la table à modifier au début du programme.

Exercices

S2: les algorithmes

Supports complémentaires:

Nous présentons dans cette section deux algorithmes de contrôle de concurrence, les plus utilisés en pratique. Ils s’appuient tous deux sur une condition qui permet au SGBD de décider si une exécution concurrente est sérialisable ou non. La notion de base est celle de conflits entre deux transactions sur la même ressource.

Définition.

Deux opérations \(p_i[x]\) et \(q_j[y]\) sont en conflit si x=y, \(i \not= j\), et p ou q est une écriture.

On étend facilement cette définition aux exécutions concurrentes : deux transactions dans un exécution sont en conflit si elles accèdent à la même donnée et si un de ces accès au moins est une écriture.

Exemple.

Reprenons une nouvelle fois l’exemple des mises à jour perdues. L’exécution correspond à deux transactions \(T_1\) et \(T_2\), accédant aux données s, \(c_1\) et \(c_2\). Les conflits sont les suivants :

  • \(r_1(s)\) et \(w_2(s)\) sont en conflit ;
  • \(w_2(s)\) et \(w_1(s)\) sont en conflit.

Noter que \(r_1(s)\) et \(r_2(s)\) ne sont pas en conflit, puisque ce sont deux lectures. Il n’y a pas de conflit sur c_1 et c_2.

De même, dans l’exécution de l’exemple~ref{ex:conc-rw} les conflits sont les suivants :

  • \(r_1(c_2)\) et \(w_2(c_2)\) sont en conflit ;
  • \(w_2(s)\) et \(r_1(s)\) sont en conflit.

Les conflits permettent de définir un ordre sur les transactions d’une exécution concurrente.

Définition.

Soit H une exécution concurrente d’un ensemble de transactions \(T = \{T_1, T_2, \cdots, T_n\}\). Alors il existe une relation \(\lhd\) sur cet ensemble, définie par :

\[T_i \lhd T_j \Leftrightarrow \exists p \in T_i, q \in T_j, p\ \rm{est\ en\ conflit\ avec} \ q\ et\ p <_H q\]

\(p <_H q\) indique que p apparaît avant q dans H.

Dans les deux exemples qui précèdent, on a donc \(T_1 \lhd T_2\), ainsi que \(T_2 \lhd T_1\). Une transaction \(T_i\) peut ne pas être en relation (directe) avec une transaction \(T_j\). La condition sur la sérialisabilité s’exprime sur le graphe de la relation \((T, \lhd)\), dit graphe de sérialisation :

Théorème.

Soit H une exécution concurrente d’un ensemble de transactions T. Alors H est sérialisable si et seulement si le graphe de \((T, \lhd)\) est acyclique.

La figure Exemples de graphes de sérialisation montre quelques exemples de graphes de sérialisation. Le premier correspond aux exemples données ci-dessus : il est clairement cyclique. Le second n’est pas cyclique et correspond donc à une exécution sérialisable. Le troisième est cyclique.

_images/graphe-serial.png

Fig. 8.2 Exemples de graphes de sérialisation

Les algorithmes de contrôle de concurrence ont donc pour objectifs d’éviter la formation d’un cycle dans le graphe de sérialisation. Nous présentons les deux principaux algorithmes dans ce qui suit.

Contrôle par verrouillage à deux phases

Le verrouillage à deux phases est le protocole le plus ancien pour assurer des exécutions concurrentes correctes. Le respect du protocole est assuré par un module dit {it scheduler} qui reçoit les opérations émises par les transactions et les traite selon l’algorithme suivant :

  • Le scheduler reçoit \(p_i[x]\) et consulte le verrou déjà posé sur x, \(ql_j[x]\), s’il existe.
  • si \(pl_i[x]\) est en conflit avec \(ql_j[x]\), \(p_i[x]\) est retardée et la transaction \(T_i\) est mise en attente.
  • sinon, \(T_i\) obtient le verrou \(pl_i[x]\) et l’opération \(p_i[x]\) est exécutée.
  • les verrous ne sont relâchés qu’au moment du commit ou du rollback.

Le terme “verrouillage à deux phases” s’explique par le processus détaillé ci-dessus : il y a d’abord accumulation de verrous pour une transaction T, puis libération des verrous à la fin de la transaction. Les transactions obtenues par application de cet algorithme satisfont les propriétés ACID. Il est assez facile de voir que les lectures ou écritures sales sont interdites, puisque toutes deux reviennent à tenter de lire ou d’écrire un tuple déjà écrit par une autre, et donc verrouillé exclusivement par l’algorithme.

Le protocole garantit que, en présence de deux transactions en conflit \(T_1\) et \(T_2\), la dernière arrivée sera mise en attente de la première ressource conflictuelle et sera bloquée jusqu’à ce que la première commence à relâcher ses verrous (règle 1). À ce moment là il n’y a plus de conflit possible puisque \(T_1\) ne demandera plus de verrou.

Pour illustrer l’intérêt de ces règles, on peut prendre l’exemple des deux transactions suivantes :

  • T_1: r_1[x] w_1[y] C_1
  • T_2: w_2[x] w_2[y] C_2

et l’exécution concurrente :

\[r_1[x] w_2[x] w_2[y] C_2 w_1[y] C_1\]

Maintenant supposons que l’exécution avec pose et relâchement de verrous se passe de la manière suivante :

  • \(T_1\) pose un verrou partagé sur x, lit x puis relâche le verrou ;
  • \(T_2\) pose un verrou exclusif sur x, et modifie x ;
  • \(T_2\) pose un verrou exclusif sur y, et modifie y ;
  • \(T_2\) relâche les verrous sur x et y, puis valide ;
  • \(T_1\) pose un verrou exclusif sur y, modifie y, relâche le verrou et valide.

On a violé la règle 3 : \(T_1\) a relâché le verrou sur x puis en a repris un sur y. Une “fenêtre} s’est ouverte qui a permis a \(T_2\) de poser des verrous sur x et y. Conséquence : l’exécution n’est plus sérialisable car \(T_2\) a écrit sur \(T_1\) pour x, et \(T_1\) a écrit sur \(T_2\) pour y. Reprenons le même exemple, avec un verrouillage à deux phases :

  • \(T_1\) pose un verrou partagé sur x, lit x mais ne relâche pas le verrou ;
  • \(T_2\) tente de poser un verrou exclusif sur x : impossible puisque \(T_1\) détient un verrou partagé, donc :math:`T_2` est mise en attente ;
  • \(T_1\) pose un verrou exclusif sur y, modifie y, et valide ; tous les verrous détenus par \(T_1\) sont relâchés ;
  • \(T_2\) est libérée : elle pose un verrou exclusif sur x, et le modifie ;
  • \(T_2\) pose un verrou exclusif sur y, et modifie y ;
  • \(T_2\) valide, ce qui relâche les verrous sur x et y.

On obtient donc, après réordonnancement, l’exécution suivante, qui est évidemment sérialisable :

\[r_1[x] w_1[y] w_2[x] w_2[y]\]

En général, le verrouillage permet une certaine imbrication des opérations tout en garantissant sérialisabilité et recouvrabilité. Notons cependant qu’il est un peu trop strict dans certains cas : voici l’exemple d’une exécution sérialisable impossible à obtenir avec un verrouillage à deux phases.

\[r_1[x] w_2[x] C_2 w_3[y] C_3 r_1[y] w_1[z] C_1\]

Un des inconvénients du verrouillage à deux phases est d’autoriser des interblocages : deux transactions concurrentes demandent chacune un verrou sur une ressource détenue par l’autre. Reprenons notre exemple de base : deux exécutions concurrentes de la procédure Réservation, désignées par \(T_1\) et \(T_2\), consistant à réserver des places pour le même spectacle, mais pour deux clients distincts c_1 et c_2. L’ordre des opérations reçues par le serveur est le suivant :

\[r_1(s) r_1(c_1) r_2(s) r_2(c_2) w_2(s) w_2(c_2) C_2 w_1(s) w_1(c_1) C_1\]

On effectue des lectures pour \(T_1\) puis \(T_2\), ensuite les écritures pour \(T_2\) puis \(T_1\). Cette exécution n’est pas sérialisable, et le verrouillage à deux phases doit empêcher qu’elle se déroule dans cet ordre. Malheureusement il ne peut le faire qu’en rejettant une des deux transactions. Suivons l’algorithme pas à pas :

  • \(T_1\) pose un verrou partagé sur s et lit s ;
  • \(T_1\) pose un verrou partagé sur c_1 et lit c_1 ;
  • \(T_2\) pose un verrou partagé sur s, ce qui est autorisé car :math:`T_1` n’a elle-même qu’un verrou partagé et lit s ;
  • \(T_1\) pose un verrou partagé sur c_2 et lit c_2 ;
  • \(T_2\) veut poser un verrou exclusif sur s : impossible à cause du verrou partagé de \(T_1\) : donc \(T_2\) est mise en attente ;
  • \(T_1\) veut à son tour poser un verrou exclusif sur s : impossible à cause du verrou partagé de \(T_2\) : donc \(T_1\) est à son tour mise en attente.

\(T_1\) et \(T_2\) sont en attente l’une de l’autre : il y a interblocage (deadlock en anglais). Cette situation ne peut pas être évitée et doit donc être gérée par le SGBD : en général ce dernier maintient un graphe d’attente des transactions et teste l’existence de cycles dans ce graphe. Si c’est le cas, c’est qu’il y a interblocage et une des transactions doit être annulée autoritairement, ce qui est à la fois déconcertant pour un utilisateur non averti, et désagréable puisqu’il faut resoumettre la transaction annulée. Cela reste bien entendu encore préférable à un algorithme qui autoriserait un résultat incorrect.

Notons que le problème vient d’un accès aux mêmes ressources, mais dans un ordre différent : il est donc bon, au moment où l’on écrit des programmes, d’essayer de normaliser l’ordre d’accès aux données.

Dès que 2 transactions lisent la même donnée avec pour objectif d’effectuer une mise à jour ultérieurement, il y a potentiellement interblocage. D’où l’intérêt de pouvoir demander dès la lecture un verrouillage exclusif (écriture). C’est la commande select .... for update que l’on trouve dans certains SGBD.

Contrôle de concurrence multi-versions

Les systèmes qui s’appuient sur des lectures cohérentes et gèrent donc des bases multi-versions, peuvent tirer parti du fait que les lectures s’appuient toujours sur une version cohérente (le “cliché”) de la base. Tout se passe comme si les lectures effectuées par une transaction \(T(t_{0})\) débutant à l’instant \(t_0\) lisaient la base, dès le début de la transaction, donc dans l’état \(t_0\).

Cette remarque réduit considérablement les cas possibles de conflits, comme le montre le raisonnement suivant. Prenons une lecture \(r_1[d]\) effectuée par la transaction \(T_1(t_0)\). Cette lecture accède à la version validée la plus récente de d qui précède \(t_0\), par définition de l’état de la base à \(t_0\). Deux cas de conflits sont envisageables :

  • \(r_1[d]\) est en conflit avec une écriture \(w_2[d]\) qui a eu lieu avant \(t_0\) ;
  • \(r_1[d]\) est en conflit avec une écriture \(w_2[d]\) qui a eu lieu après \(t_0\).

Dans le premier cas, \(T_2\) a forcément effectué son commit avant \(t_0\), puisque \(T_1\) lit l’état de la base à \(t_0\) : tous les conflits de \(T_1\) avec \(T_2\) sont dans le même sens, et il n’y a pas de risque de cycle (Figure Contrôle de concurrence multi-versions : conflit avec les écritures précédentes).

_images/cc-multiversions.png

Fig. 8.3 Contrôle de concurrence multi-versions : conflit avec les écritures précédentes

Le second cas est celui qui peut poser problème. Si \(T_1\) cherche à écrire d après l’écriture \(w_2[d]\), alors un conflit cyclique apparaît (Figure Contrôle de concurrence multi-versions : conflit avec une écriture d’une autre transaction.). Notez qu’une nouvelle lecture de d par \(T_1\) n’introduit pas de cycle puisque toute lecture s’effectue à \(t_0\).

_images/cc-multiversions2.png

Fig. 8.4 Contrôle de concurrence multi-versions : conflit avec une écriture d’une autre transaction.

En résumé le contrôle de concurrence peut alors se limiter à vérifier, au moment de l’écriture d’un tuple a par une transaction T, qu’aucune transaction T’ n’a modifié a entre le début de T et l’instant présent. Si on autorisait la modification de a par T, des risques de conflits cycliques apparaîtraient avec T’. Autrement dit une mise à jour n’est possible que si la partie de la base à modifier n’a pas changé depuis que T a commencé à s’exécuter.

Le contrôle de concurrence multi-versions s’appuie sur les règles suivantes. Rappelons que pour chaque transaction T on connaît son estampille temporelle de début d’exécution \(e_T\); et pour chaque version d’un tuple a son estampille de validation \(e_a\).

  • toute lecture \(r_T[a]\) lit la plus récente version de a telle que \(e_a \leq e_T\); aucun verrou n’est posé;

  • en cas d’écriture \(w_T[a]\),
    • si \(e_a \leq e_T\) et aucun verrou n’est posé sur a : T pose un verrou exclusif sur a, et effectue la mise à jour ;
    • si \(e_a \leq e_T\) et un verrou est posé sur a : T est mise en attente ;
  • si \(e_a > e_T\), T est rejetée.

  • au moment du commit d’une transaction T, tous les enregistrements modifiés par T obtiennent une nouvelle version avec pour estampille l’instant du commit.

Avec cette technique, on peut ne pas poser de verrou en lecture. En revanche les verrous exclusifs sont toujours indispensables pour les écritures, afin d’éviter lectures ou écritures sales.

Voici un déroulé de cette technique, toujours sur notre exemple d’une exécution concurrente du programme de réservation avec l’ordre suivant :

\[r_1(s) r_1(c_1) r_2(s) r_2(c_2) w_2(s) w_2(c_2) C_2 w_1(s) w_1(c_1) C_1\]

On suppose que \(e_{T_{1}} = 100\), \(e_{T_{2}} = 120\). On va supposer qu’une opération est effectuée toutes les 10 unités de temps, même si seul l’ordre compte, et pas le délai entre deux opérations. Le déroulement de l’exécution est donc le suivant :

  • \(T_1\) lit s, sans verrouiller ;
  • \(T_1\) lit c_1, sans verrouiller ;
  • \(T_2\) lit s, sans verrouiller ;
  • \(T_2\) lit c_2, sans verrouiller ;
  • \(T_2\) veut modifier s : l’estampille de s est inférieure à \(e_{T_{2}} = 120\), ce qui signifie que s n’a pas été modifié par une autre transaction depuis que \(T_2\) a commencé à s’exécuter; on pose un verrou exclusif sur s et on effectue la modification :
  • \(T_2\) modifie c_2, avec pose d’un verrou exclusif ;
  • \(T_2\) valide et relâche les verrous ; deux nouvelles versions de s et \(c_2\) sont créées avec l’estampille 150 ;
  • \(T_1\) veut à son tour modifier s, mais cette fois le contrôleur détecte qu’il existe une version de s avec \(e_s > e_{T_{1}}\), donc que s a été modifié après le début de \(T_1\). Le contrôleur doit donc rejeter \(T_1\) sous peine d’obtenir une exécution non sérialisable.

Comme dans le verrouillage à deux phases, on obtient le rejet de l’une des deux transactions, mais le SGBD effectue dans ce cas un contrôle à postériori au lieu d’effectuer un blocage à priori comme le verrouillage à deux phases. On parle parfois d’approche “pessimiste” pour le verrouillage à deux phases et “optimiste” pour le contrôle multi-versions, exprimant ainsi l’idée que la première technique tente de prévenir les problèmes, alors que la seconde choisit de laisser faire et d’intervenir seulement quand ils surviennent réellement.

L’absence de verrouillage en lecture favorise la fluidité des exécutions concurrentes par rapport au verrouillage à deux phases, et limite le coût de la pose de verrous. On peut le vérifier par exemple sur l’exécution concurrente de l’exemple impliquant la procédure de contrôle. Bien entendu le coût en contrepartie est la nécessité de gérer les versions et de maintenir une vue cohérente de la base pour chaque transaction.

Exercices

Références