Tutoriel de Bases de Données Relationnelles

Contrôle des accès concurrents et reprise

Introduction

Un SGBD est par définition multi-utilisateurs, par conséquent l'exécution simultanée de plusieurs applications peut poser des problèmes d'accès concurrents (une même information étant manipulée par plusieurs utilisateurs à la fois). L'unité de concurrence est la transaction qui joue également un rôle vis à vis du contrôle de l'intégrité des données. Une base de données doit être cohérente avant et après une transaction. Par contre, la cohérence peut être violée pendant l'exécution d'une transaction.

Transaction

Une transaction est une séquence d'opérations qui accèdent et modifient le contenu d'une base de données et qui est complètement exécutée ou pas du tout (unité atomique de traitement). Une transaction s'effectue soit complètement et alors les mises à jour qu'elle a effectuées sur la base de données sont validées, soit elle s'effectue incomplètement (annulation ou panne) et alors toutes les mises à jour effectuées depuis le début de la transaction sont invalidées.

Les propriétés d'une transaction sont les suivantes (ACID) :

• Atomicité : tout ou rien
• Cohérence : une transaction prend une base de données dans un état cohérent et la transforme dans une nouvelle base de données qui est dans un état cohérent (préservation de la cohérence)
• Isolation : les mises à jour faites par une transaction ne sont visibles à l'extérieur de celle-ci (pour les autres transactions) qu'après la validation de la transaction.
• Durabilité : après la fin d'une transaction, les mises à jour sont définitives même en cas de futurs problèmes matériels (grace au mécanisme de reprise)

Problèmes liés aux accès concurrents

On considère une transaction T1 qui consiste à annuler N réservations sur un vol V1 (X représente le nombre de places réservées sur le vol V1) et à réserver N places sur un vol V2 (Y représente le nombre de places réservées sur le vol V2). La transaction T2 réserve Mplaces sur le vol V1. L'exécution concurrente de T1 et T2 sans contraintes de synchronisation peut produire un certain nombre de problèmes dont les plus importants sont la perte d'opérations et les lectures impropres.

Perte d'opérations

       T1                               T2
lire(X) 
X := X-N 
                                      lire(X) 
                                      X := X+M 
écrire(X) 
lire(Y) 
                                      écrire(X) --> écrire(X:=X-N) est perdu par T1
Y := Y+N 
écrire(Y) 

Lectures impropres

       T1                             T2
lire(X) 
X := X-N 
écrire(X) 
                                     lire(X) 
                                     X := X+M 
lire(Y) 
annulation T1

La valeur de X lue par T2 est incohérente car X a été lu après la mise à jour faite par T1 qui a été ensuite invalidée par l'annulation de T1.

Il faut fixer une propriété déterminant une exécution correcte de transactions concurrentes. Cette propriété est la sérialisibilité à savoir une exécution concurrente de transactions est correcte si elle est équivalente (produit le même résultat) à une exécution en série. Il faut noter que cette définition n'est pas constructive, elle ne donne pas de moyens de garantir la propriété.

La sérialisation est une propriété forte qui limite le parallélisme à l'exécution donc les performances. Certains SGBD comme Oracle propose des assouplissements de cette propriété basés sur des protocoles multi-versions.

Mécanismes pour assurer la concurrence et la reprise

Transactions et journalisation

Une transaction peut échouer pour de nombreuses raisons :

• problème système,
• erreur dans la transaction (définie dans le programme) ou interruption volontaire de l'utilisateur,
• arrêt involontaire de la transaction (interblocage du à une demande croisée d'allocation de ressources avec une autre transaction),
• problème matériels (disque, ...).

Cet échec de la transaction peut entrainer une incohérence si une partie seulement des mises à jour ont été effectuées (ne respecte pas la propriété d'atomicité). Par conséquent, il faut restituer l'état antérieur de la base grace à un mécanisme de reprise.

La notion de transaction sert de granule de contrôle de la concurrence et permet également de faire des reprises sur erreurs logicielles (la base se trouve dans un état cohérent à chaque point observable). Ce mécanisme est appelé "reprise à chaud".

La vie d'une transaction dans le système peut se décrire de la manière suivante :

 

Les pannes matérielles ou logicielles graves ne peuvent se traiter par un simple mécanisme transactionnel. Le principe général est de garder un historique persistant de tout ce qui se passe sur la base de données. A partir de cet historique (appelé journal) et d'états antérieurs (sauvegardes) de la base de données, on peut reconstituer la base de données dans l'état cohérent qui précède la panne. Ce mécanisme est appelé "reprise à froid".

Le journal est donc un support sur disque qui maintient les informations nécessaires pour la reprise :

• début d'une transaction T,
• si écriture sur une donnée X : ancienne valeur, nouvelle valeur
• si lecture sur une donnée X : X
• fin d'une transaction T,
• point de reprise P.

Un point de reprise consiste à écrire sur disque les mises à jour des transactions validées (copie du buffer sur le disque). Ce mécanisme s'effectue périodiquement, toutes les N secondes, toutes les N transactions, ... Le journal est également sauvegardé sur disque à ce moment là.

Concurrence par verrouillage

On peut distinguer 2 grandes techniques pour assurer la sérialisibilité :

• approche pessimiste ou a priori (on fait en sorte que l'on ne puisse pas avoir d'exécution non correcte) : on trouve ici les techniques de verrouillage ou d'estampillage,
• approche optimiste ou a postériori (on laisse s'exécuter les transaction sans contraintes et on moment de la validation on vérifie qu'il n'y a pas de conflits avec les autres transactions).

De manière industrielle, la seule solution implantée est l'appoche par verrouillage.

Un verrou est une variable d'état associée à un objet X de la base et indiquant son état vis à vis des opérations de lecture / écriture.

Un verrou peut être binaire (deux états verrouillé ou libre avec deux opérations verrouiller(X) et libérer(X)) ou ternaire. Un verrou binaire est trop restrictif puisqu'un objet est bloqué pour toute opération que l'on veut effectuer sur lui, ce qui implique qu'on ne peut faire des lectures simultanées.

Un verrou ternaire permet 3 états, en lecture (ou partagé), en écriture, ou libre. Le verrou en écriture n'est alloué que si l'objet est libre, c'est à dire si aucune opération ni de lecture, ni d'écriture ne s'effectue sur cet objet. Le verrou en lecture est alloué si l'objet est libre ou si aucune opération d'écriture ne s'effectue sur lui (par contre des opérations de lecture peuvent se dérouler simultanément, ce qui nécessite de maintenir un compteur pour connaitre le nombre de transactions "lisant" cet objet).

Un protocole de verrouillage sans aucune contrainte sur l'allocation des verrous, ne permet pas de garantir la propriété de sérialisabilité. De nombreux protocoles ont été proposés, le plus classique étant le protocole de verrouillage à deux phases.

Dans ce protocole, toutes les acquisitions de verrous sont faites avant la première libération. On dit qu'il y a une phase d'expansion suivie d'une phase de libération.

Le protocole de verrouillage à 2 phases garantit la propriété de sérialisabilité mais ne permet pas d'éviter les situations d'interblocage. Un interblocage se produit lorsque une transaction est bloquée en attente de ressources provenant d'une autre transaction (et réciproquement). Plus généralement, un interblocage peut se passer entre n transactions. Deux techniques sont possibles, une pessimiste et une optimiste :

• prévention : on donne un ordre total sur les transactions et on vérifie que les attentes entre transactions sont conformes à cet ordre (approche par estampillage),
• détection : on maintient un graphe de dépendances entre les transactions qui permet de détecter les situations d'interblocage (présence d'un cycle dans le graphe). Il faut alors tuer ("assassiner") une des transactions participant à l'interblocage. Le choix se fait de manière heuristique (transaction ayant le moins de mises à jour à défaire, transaction la plus récente, ...). C'est cette technique qui est implantée dans les systèmes commerciaux.

Granularité de contrôle de concurrence

Différentes granularités de contrôle de la concurrence sont possibles :

• valeur d'un attribut de n-uplet,
• un n-uplet,
• une page ou bloc,
• une relation,
• une base.

Plus la granularité est petite, plus le niveau de concurrence augmente. Par contre le niveau de complexité de gestion des verrous augmente et les performances baissent.

A priori le choix est dépendant du type des transactions (nature des informations manipulées). La plupart du temps dans les systèmes commerciaux la granularité est fixe (sauf indiquée explicitement). Certains systèmes font du verrouillage adaptatif en tenant compte de la hiérarchie des objets (plutot que de bloquer tous les attributs d'un n-uplet il vaut mieux bloquer le n-uplet et ainsi de suite). Dans les systèmes actuels le niveau offert est celui du n-uplet. 

Principes généraux de la reprise

L'échec d'une transaction (suicide ou assassinat) entraine un état incohérent de la base de données. Il faut donc ramener la base de données dans l'état cohérent précédent le plus proche. Pour cela, un mécanisme de reprise offre deux opérations "défaire" et "refaire". Défaire une opération peut amener en à défaire d'autres. Deux techniques de reprise sont utilisées, mise à jour différée ou mise à jour immédiate.

Reprise basée sur la mise à jour différée :

La mise à jour différée consiste à ne faire les écritures effectives qu'au moment de la validation de la transaction. Les modifications sur la base de données sont enregistrées dans le journal lors de la validation. La procédure de reprise consiste alors à parcourir le journal pour refaire les opérations d'écriture des transactions validées depuis le dernier point de reprise (dans l'ordre d'apparition du journal).

Par contre, il n'y a rien à faire pour les transactions non validées (la base de données n'a pas été mise à jour).

Reprise basée sur la mise à jour immédiate :

Les écritures sont effectuées sur la base de données immédiatement et les anciennes valeurs des informations modifiées sont enregistrées dans le journal. La procédure de reprise consiste alors à :

• refaire les opérations d'écriture des transactions validées depuis le dernier point de reprise (dans l'ordre d'apparition du journal),
• défaire toutes les opérations d'écriture des transactions invalidées depuis le dernier point de reprise (dans l'ordre inverse d'apparition).