Algorithmes et bases de données, année 2019

Transactions et gestion de la concurrence

La notion de transaction est centrale dans de nombreux système informatique. Une transaction est une suite d’opérations a exécuter comme un bloc. Les transactions vérifiant un certains nombre de propriétés (ACID) permettent à un système informatique une certaine robustesse en cas de panne, d’erreur, d’accès concurrents aux données.

Les propriétés ACID:

Aujourd’hui nous allons avant tout voir la gestion de la concurrence et notamment des niveau d’isolations entre transaction.

La gestion de la concurrence:

La gestion de la concurrence est un des rôles centrales des systèmes de données. Plusieurs mécanismes existent afin de garantir que des accès concurrents à la base n’entraîne pas d’incohérence dans les résultats.

Dans plusieurs système de bases de données, on maintient simultanément plusieurs version de la base de données afin que les différentes transactions ne se bloquent pas les unes les autres. Ce mécanisme s’appelle le MVCC pour MultiVersion Concurrency Control.

Ressources:

Problématiques

Deux processus veulent lire et écrire des informations dans une table:

nom quantité
chaussures 4
chaussette 4

Chaque processus représente une tentative d’achat d’un utilisateur qui souhaite acquérir un certains nombres de paires de chaussures. Si la quantité totale de chaussure est suffisantes, on peut valider l’achat et décroître la quantité restante.

Cette requête s’écrit simplement:

UPDATE produits SET quantité = quantité - 3 WHERE nom='chaussure' and quantité > 3;

Si cette requête est exécutée deux fois successivement, la seconde fois ne fonctionnera pas car la quantité de chaussures disponible sera trop petite. Si cette est requête est exécutée deux fois en parallèle, alors le gestionnaire de base de donnée doit trouver une stratégie pour résoudre un potentiel conflit.

Niveaux d’isolations

La gestion des conflits peut être gérées à plusieurs niveau en fonction des besoins en précision et en flexibilité du système de base de données. Les différents niveaux d’isolations permettent représentent des niveaux de contraintes que la base de données doit satisfaire pour une transaction courante.

Le standard SQL en définit quatre niveaux d’isolation en fonction de la relaxation des contraintes qu’on autorise:

  1. Read uncommitted les modifications faites par une autre transaction y compris celles non validées peuvent modifier les résultats.
  2. Read committed les modifications validées par une autre transaction permettent de modifier les valeurs des tuples d’une requête.
  3. Repeatable read les modifications validées par une autre transaction permettent de modifier l’ensemble des tuples d’une requête
  4. Serializable les modifications faites par les transactions doivent simulée une exécution séquentielles des transactions

Le niveau d’isolation est à définir au niveau de la transaction, donc deux transactions peuvent avoir des niveaux d’isolations différents

Niveaux d’isolation de PostgreSQL

En pratique, PostgreSQL propose trois niveaux d’isolations (même s’il est possible de déclarer tous les niveaux d’isolations du standards). Par défaut, PostgreSQL choisit le niveau le moins isolé: READ COMMITED. Autrement dit, les validations de transactions concurrentes changes le résultat d’une requête dans une même transaction.

Les deux niveaux d’isolation plus avancés Repeatable read et Serializable sont disponibles.

Mécanisme de contrôle de version

Le fonctionnement interne du système d’isolation repose sur une gestion des versions directement codé au niveau physique de la base de données, directement dans les pages. Chaque transaction (et sous transaction) possède un identifiant (entier codé sur 32bits) nommé txid (pour transaction id).

La fonction txid_current() permet ainsi de récupérer l’identifiant de la transaction courante.

Chaque tuple dans chaque page est accompagné d’une en-tête donnant des informations sur sa version:

À l’ajout ou modification d’un tuple, les valeurs de xmin et xmax correspondante sont ajustés afin de permettre d’avoir plusieurs version d’un même tuple simultanément.

Ce mécanisme de gestions des versions de la bases permet de maintenir des versions concurrentes avec peu de verrou lié aux accès concurrent. En particulier, les lectures ne sont pas bloqués par les écritures et réciproquement.

Verrous en écritures

Les différents niveau d’isolation entraîne l’utilisation de verrous de petite ou grosse granularité. Ces verrous sont gérés au niveau de la mémoire partagés. Ainsi, dans le mode d’isolation par défaut, les verrous sont présents uniquement au niveau de la requête et uniquement au niveau des tuples. Le mode d’isolation le plus restrictif (la sérialisation) met des verrous sur la table complète.

Gestions des tuples morts: l’aspirateur

Un tuple n’est jamais supprimé directement par un processus. La gestion des versions des tuples anciens est délégué à un mécanisme de nettoyage des pages des tables. Ce mécanisme va identifié les tuples morts et indiqué l’espace qu’ils occupent comme étant libre.

L’information de l’espace libre au milieu des pages est stocké dans un fichier annexe appelé free space visibility map. Le processus de nettoyage est automatique (et configurable). Il s’agit d’un processus coûteux mais indispensable pour éviter que l’espace disque (et le coût d’une lecture séquentielke) explose.

Lors de sont passage, l’aspirateur ou Vaccuum, va faire un certains nombre d’opérations:

Ce dernier fichier (visbility map) est utile pour indiquer à l’aspirateur quels pages contiennent des données modifiées. Cela lui permet de ne pas passer au travers des données trop ancienne qui n’ont pas été modifié récemment.

Ce fichier de visbibilité est un simple masque binaire pour les pages concernés qui est remis à 1 à chaque passage de l’aspirateur. On bascule le bit d’une page quand celle ci contient un tuple modifié. Ce fichier est également utilisé pour accéléré les lectures de table à l’aide d’index.

Il est possible, quand la table à subit des modifications trop importantes, de la compactée dans une nouvelle structure physique en éliminant les problèmes de fragmentation. Pour ce faire on utilise la commande VACUUM FULL qui va re-insérer chaque tuple vivant dans une nouvelle table. Ce processus est néanmoins coûteux et doit être évité autant que possible.