Enseignement des Bases de Données

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).

Posté le 1 septembre 2009