[SQL Server] Un peu de théorie sur l’architecture d’un fichier de données…

Ce billet présente les aspects théoriques des pages d’un fichier de données MDF (Microsoft Database File).

Présentation d’un fichier de données

Qu’est-ce qu’un fichier de données ?

Un fichier de données est un élément d’une base de données constitué d’un conglomérat de pages contigües destinées à physiquement organiser et stocker des données.

Contrairement à la plupart des autres systèmes de gestion de bases de données (SGBD) sur le marché, SQL Server ne propose pas la possibilité de configurer la taille d’une page pour différents types de données ou tables. De ce fait, toutes les pages de SQL Server sont de taille égale à 8 Ko.

Sous SQL Server, tout fichier de données primaire porte l’extension MDF (Microsoft Data File), par défaut. Toutefois, pour des soucis de lisibilité et de meilleure gestion, il est recommandé de donner une extension différente aux fichiers secondaires. Une extension comme NDF (Next Data File) est plus conventionnelle.
Notons, d’ailleurs, que SQL Server ne supporte, par base de données, que jusqu’à 32 000 fichiers.

Notions d’extents et d’unité d’allocation

Au sein d’un fichier de données, chaque page de données est stockée dans une unité de gestion de l’espace de stockage. Une telle unité est appelée extent (ou étendue, en français).

Un extent correspond à un ensemble de 8 pages contigües, ensemble pouvant être uniforme (dedicated extent) ou mixte (mixed extent). Un extent fait donc 64 ko (8 pages de 8 Ko).

Un extent est dit « uniforme »  s’il appartient à un seul et même objet tandis qu’il est dit « mixte » s’il est partagé par plusieurs objets. Par défaut, quand une table est crée, c’est un extent mixte qui lui est alloué pour des raisons d’optimisation de stockage, une table ne s’accaparant pas forcément tout l’espace total alloué par un extent uniforme.

Remarquons que dans un fichier de données, un ensemble de pages utilisées pour abriter des données (tables ou indexes) au sein d’une simple partition est appelé unité d’allocation. Il existe 3 types d’unités d’allocation :

  • IN-ROW (lignes de données dites « classiques »).
  • ROW-OVERFLOW (lignes de données de taille supérieure à 8 ko).
  • LOB (lignes de données pour les structures larges, comme les images, les vidéos,…).

Un index en cluster ou une table heap possède par défaut au moins une partition avec une unité d’allocation de type IN-ROW (<=8 Ko).

A noter également qu’une ligne de peut pas couvrir plusieurs pages mais que des parties de ladite ligne peuvent être déplacées hors de la page concernée de telle façon que la ligne peut, en réalité, atteindre une très grande taille (> 8 Ko). C’est le cas, par exemple, quand SQL Server déplace, de manière dynamique, une ou plusieurs colonnes d’une ligne « hors-norme » dans des pages d’unité d’allocation ROW_OVERFLOW.

Cette restriction (8 Ko) ne concerne, bien sûr, pas les pages de type Text ou Image.

Architecture des pages d’un fichier de données

Les pages de données

Lors de la création d’un fichier de données, SQL Server alloue des pages et des extents (ensemble de 8 pages de 8 Ko – voir plus loin) pour le stockage de données. Chaque page possède un numéro commençant par 0, le numéro de la dernière page étant déterminé par la taille du fichier de données concerné. Et chaque fois que la taille d’un fichier de données est augmentée (via ALTER DATABASE… MODIFY FILE, par exemple), de nouvelles pages sont créées et allouées en fin de fichier.

Chaque page possède un header (en-tête) de 96 octets qui permet de stocker les informations système relatives à la page concernée. Ces informations constituent principalement le numéro de page, le type de page, la quantité d’espace disponible sur la page et l’identifiant de l’unité d’allocation de l’objet auquel appartient ladite page. Dans une page, les lignes de données (dont chacune possède un identifiant de ligne, ou ROW ID, également appelé numéro de slot, pour la différencier des autres) sont placées séquenx²tiellement, à partir de l’en-tête. Et en fin de page, une table de décalage (offset)
de lignes est éditée afin de contenir une entrée (ou valeur d’offset) de 2 octets pour chaque ligne de la page dans un ordre inversé par rapport à la manière dont sont organisées les lignes de données.

Le schéma ci-dessous présente de manière simple l’architecture d’une page de données (les valeurs d’offset sont arbitraires. En effet, ici : 1) chaque ligne de données vaut 22 octets ; 2) l’offset de départ de chaque ligne est de 22 octets + l’offset de la ligne précédente. Par exemple, pour la ligne de données 1 : 96+22=118 ; pour la ligne de données 2 : 118+22=140) :


Lorsqu’un enregistrement existant est supprimé, la table de décalage de lignes est mise à jour en réinitialisant la valeur d’offset correspondante à 0. Par exemple, pour reprendre le schéma ci-dessus, si la ligne de données 1 est supprimée, alors la valeur d’offset 118 correspondant à ladite ligne, au sein de la table de décalage de lignes, sera réinitialisé à 0, indiquant ainsi la présence d’un « trou » ou d’un (nouvel) espace disponible.

Dans le but d’être plus concret, imaginons le scénario suivant : suppression d’un enregistrement (celui précédemment cité) et ajout de deux nouveaux enregistrements de 22 octets chacun. Supposons que les lignes de données 0, 1 et 2 contiennent pour enregistrement respectivement ABM, Macrosoft et Oricle. Après avoir supprimé, par exemple, Macrosoft (ligne de données 1), il faudra noter que (et l’on s’inscrit, ici, dans le cas d’une page de données d’une table heap) :

  • La suppression ne supprimera pas physiquement les informations associées stockées dans la page de façon instantanée. Par contre, comme évoqué plus haut, la valeur d’offset (118) associée à la ligne de données 1 sera réinitialisé à 0 (unused).
  • Lorsqu’un nouvel enregistrement sera ajouté (appelons-le Mucrosoft), il deviendra la nouvelle ligne de données numéro 1, mais prendra place en dernière position de la liste des lignes de données, juste après la dernière ligne utilisée (tant que de l’espace est disponible). De plus, il aura un nouvelle valeur d’offset (supposons 162, si la ligne vaut 22 octets, soit 140+22=162, où 140 est le dernier offset).

    Cet ajout ne va donc pas remplacer l’espace laissé vacant par la suppression de la ligne de données 1 (Macrosoft). Par contre, au niveau de la table de décalage de lignes, la valeur d’offset 0 (donc appartenant précédemment à Macrosoft dont la valeur d’offset était, avant suppression, 118) sera remplacée par celle de Mucrosoft (162) :


  • En cas d’indisponibilité d’espace, et si jamais une nouvelle ligne doit être insérée (appelons-la MaSQL), les lignes sont compactées, ce qui signifie que, si l’on reprend le schéma ci-dessus (en supposant bien sûr qu’il n’y ait plus d’espace disponible après la dernière ligne de données utilisée), Oricle (ligne de données 2) prend la place de l’espace vide laissé par l’ancienne ligne de données 1 Macrosoft (qui disparaîtra, alors, physiquement pour de bon), la nouvelle ligne de données 1 Mucrosoft prendra la place d’Oricle. Et enfin, le nouvel enregistrement à ajouter prendra la place de Mucrosoft (avec création d’une nouvelle ligne dans la table des offsets) :


Au vu des explications schématisées, voici les 3 principaux points que l’on peut relever :

  • Chaque fois qu’une ligne de données est supprimée, elle est remplacée par la prochaine ligne de données insérée (au sens logique, c’est-à-dire, au niveau de la table de décalage des lignes). Au sens physique, la prochaine ligne de données insérée est placée dans une nouvelle partition située après la fin de la dernière ligne de données, tant qu’il y a de l’espace disponible.
  • Durant tous les changements effectués (y compris au niveau des valeurs d’offset de la table de décalage des lignes), les IDs de ligne de données (0, 1, 2,…) n’ont pas été modifiés par SQL Server pour les lignes existantes. En d’autres termes : une table de décalage de lignes a l’avantage de permettre de changer la position d’une ligne de données sans modifier son identifiant. C’est d’autant très utile qu’elle assure aux entrées d’indexes de ces lignes la possibilité de ne pas avoir à systématiquement être mises à jour à chaque changement, aidant ainsi SQL Server à gagner du temps durant la mise-à-jour des données des indexes concernés.
  • Au sein d’une page d’une table heap, les lignes de données ne sont pas organisées physiquement en cas de mises-à-jour significatives (i.e., insertions,…).
Sous SQL Server, la gestion des mises-à-jour d’enregistrements sur une table avec index en cluster est similaire à ce qui se fait pour une table sans index en cluster (« heap »). La différence est que quand une page est compactée, la table de décalage de lignes est ajustée de façon à permettre aux lignes de l’index de clé primaire d’être ordonnées par numéro de ligne. De cette façon, SQL Server permet aux lignes de données d’un index en cluster d’être ordonnées (physiquement à la reconstruction ou logiquement sinon) ce qui favorise les performances en lecture.
Notons d’ailleurs que les pages de données d’une table heap n’étant pas physiquement reliées entre elles (contrairement aux pages d’index en cluster), ce sont les pages IAM (Index Allocation Map, voir section sur les pages d’allocation) qui se chargent de leur liaison, permettant ainsi à SQL Server de se déplacer d’une page à l’autre.

Les pages d’indexes

Un index est une structure de données organisée de la même manière qu’un arbre équilibré (Balanced tree ou B-Tree). Un arbre équilibré est une structure informatique, constituée de feuilles et de nœuds (contenant une ou plusieurs lignes d’enregistrements), mise en œuvre sous une forme triée et permettant une exécution rapide des opérations de recherche, d’insertion et de suppression.

Nous y reviendrons plus en détail dans un prochain billet.


Les pages LOB (Large Object Binary)

Il s’agit essentiellement des pages de type Text ou Image.

Ce type fait référence aux pages contenant des lignes de données « larges » ou LOB (i.e., > à 8 Ko) référençant tout sauf des indexes (i.e., les tables). C’est-à-dire des lignes de données contenant des données « larges » telles que : (N)TEXT, IMAGE, (N)VARCHAR(MAX), VARBINARY(MAX) et XML.

La taille de ce type de pages est naturellement supérieure à 8 Ko, mais nous n’allons pas les traiter en détail dans la version de ce document.


Les pages d’allocation

Les différents types de pages d’allocation

Chaque fichier de données est constitué de principalement 6 différents types de pages d’allocation ayant, chacun, une utilité bien spécifique :

Type de pages Description Taille Positionnement
GAM (Global Allocation Map Les pages GAM stockent les informations sur l’ensemble des extents alloués à un fichier de données (qu’il s’agisse d’un extent mixte ou uniforme). Elles contiennent des bits (0 ou 1) qui permettent à SQL Server de déterminer quel extent est alloué (bit=0) ou non (bit=1).
Quand une nouvelle page a besoin d’être allouée, SQL Server lit toujours les pages GAM pour trouver les extents disponibles. Quand un extent est « désalloué », le bit de cet extent est réinitialisé à 1 afin de le rendre disponible pour toute (ré)allocation future.
La taille d’une page GAM est de 8 Ko et un extent valant 8 pages de données, cela signifie qu’une page GAM peut donc gérer 64 000 extents (pour être exact : 8000×8=64000). Par conséquent, un espace GAM « pèse » au total jusqu’à 4 Go (64000×64 Ko=4 Go). Au sein d’un fichier de données, une page GAM correspond toujours à la 3ème page (page d’ID 2). On retrouve une page GAM toutes les 511230 pages (ou 64000 extensions) après la 1ère page GAM si la capacité de stockage de la base de données dépasse les 4 Go.
SGAM (Shared Global Allocation Map) Les pages SGAM contiennent des bits (0 ou 1) qui permettent à SQL Server de déterminer la présence d’extents mixtes avec au moins une page de données libre (bit=1) ou la présence d’extents (uniformes ou mixtes) avec que des pages de données utilisées (bit=0).
Autrement dit : l’intérêt des pages de ce type est qu’elles stockent les informations sur l’ensemble des extents mixtes qui possèdent au moins une page libre. Si aucun extent mixte ne possède de pages libres, SQL Server recherche des pages libres dans l’espace GAM. Et une fois une page libre trouvée, elle sera allouée à l’espace SGAM.
Si, par contre, aucun extent de disponible n’existe dans l’espace GAM (tout comme dans l’espace SGAM), le fichier de données apparaîtra comme plein, et de nouveaux extents devront être alloués.
A l’instar d’une page GAM, la taille d’une page SGAM est de 8 Ko et un extent valant 8 pages de données, cela signifie donc qu’une page SGAM peut donc gérer 64 000 extents (pour être exact : 8000×8=64000). Par conséquent, un espace
SGAM « pèse » au total jusqu’à 4 Go (64000×64 Ko=4 Go).
Au sein d’un fichier de données, une page SGAM correspond toujours à la 4ème page (page d’ID 3). On retrouve une page SGAM toutes les 511230 pages (ou 64000 extents) après la 1ère page SGAM, si la capacité de stockage de la base de données dépasse les 4 Go.
PFS (Page Free Space) Les pages PFS fournissent des informations sur le degré de saturation des pages de données. Elles capturent également les informations relatives à l’état d’allocation de chaque page de données.
En d’autres termes, SQL Server utilise les pages PFS pour déterminer quelles pages peuvent être utilisées pour répondre aux demandes d’allocation. Notons toutefois que le pourcentage d’espace disponible est seulement géré pour les tables sans index en cluster (« heaps ») ou pour les pages larges (objets LOB).
Si une page a de l’espace libre, elle peut être utilisée pour les nouvelles lignes à insérer.
Contrairement aux autres types de page, une page PFS associe un ensemble de 8 octets à une page de données dans un espace de 8000 pages environ (soit 64 Mo en tout). Une page PFS vient juste après la page d’en-tête (page d’ID 0) d’un fichier ce qui la place en 2ème position (page d’ID 1). Il y a une page PFS approximativement 8000 pages après la 1ère page PFS.
IAM (Index Allocation Map) Les pages IAM stockent des informations sur les extents utilisés soit par des tables sans index en cluster (« heaps »), soit par des indexes au sein d’une unité d’allocation.
Quand une requête d’insertion est exécutée, SQL Server vérifie les extents actuellement alloués à la table à traiter, et après avoir consulté l’espace PFS pour déterminer si la ou les lignes issues du résultat de la requête d’insertion peuvent être ajoutées dans des pages déjà allouées. Si de telles pages existent, il utilise l’espace IAM pour trouver quels sont les extents de la (ou les) page(s) concerné(e)s alloués dans l’unité d’allocation correspondante. Dans le cas échéant (pas de page disponible), il allouera, dans la mesure du possible, de nouveaux extents.
Remarquons qu’étant donné que les tables heap ne sont pas physiquement liées comme pour un index en cluster, le seul moyen, pour SQL Server, de connaître l’ensemble des pages allouées est de lire l’ensemble des pages IAM allouées à chaque table concernée.
A l’instar des pages GAM et SGAM, la taille d’une page IAM est de 8 Ko et un extent valant 8 pages de données, cela signifie donc qu’une page IAM peut donc gérer 64 000 extents (pour être exact : 8000×8=64000) sur un espace GAM de jusqu’à 4 Go.
De ce fait, une base de données de 4 Go possèdera plusieurs pages IAM, sachant qu’une seule sera dédiée à chaque espace de 4 Go maximum supplémentaire. De même, si une table est partitionnée (sur plusieurs fichiers de données distincts), celle-ci sera traitée par plusieurs pages IAM (une pour chaque partition) située chacune sur un espace de jusqu’à 4 Go de données.
Etant donné qu’une base de données possède très peu de pages IAM et qu’elles sont liées par une liste chaînée, SQL Server les met généralement en cache afin de les retrouver rapidement.
DCM (Differential Change Map) Les pages DCM stockent des informations sur tous les extents ayant été modifiés (bit=1) depuis la dernière sauvegarde complète de la base de données. Lorsqu’une sauvegarde différentielle est lancée, SQL Server scanne les pages DCM et copie seulement les extents ayant été modifiés depuis la dernière sauvegarde complète.
En ne traitant que les extents ayant été modifiés depuis la dernière sauvegarde complète, SQL Server permet de rendre la sauvegarde différentielle plus rapide.
Lors d’une sauvegarde complète, le bit des extents concernés par une page DCM est réinitialisé à 0.
Tout comme les pages GAM et SGAM, une page DCM peut gérer jusqu’à 64000 extents. Une page DCM correspond à la 7ème page (page d’ID 6) d’un fichier de données. Et il y a une page DCM toutes les 511230 pages si la base de données est supérieure à 4 Go en termes de stockage de données.
BCM (Bulk-logged Change Map) ou, parfois, MLM (Minimally-Logged Map) Les pages BCM stockent des informations sur les extents modifiées (bit=1) par des opérations de mises-à-jour de masse de type BULK telles que BULK INSERT ou bcp (Bulk Copy Program). Les pages BCM ne s’intéressent qu’aux extents modifiés par des opérations de type BULK depuis la dernière sauvegarde transactionnelle.
En fait, les pages BCM ne sont pertinentes que si la base de données concernée est en mode de récupération BULK-LOGGED (journalisation minimale des opérations de mises-à-jour de masse). En effet, dans ce mode de récupération, les sauvegardes transactionnelles incluent les extents modifiés par les opérations de type BULK de façon à pouvoir permettre à SQL Server de restaurer (si souhaité) une base de données avec ses opérations BULK. C’est pour cette raison que les fichiers de sauvegarde transactionnelle peuvent être anormalement gros.
Lors d’une sauvegarde transactionnelle, le bit des extents concernés par une page BCM est réinitialisé à 0.
Tout comme les pages GAM et SGAM, une page DCM peut gérer jusqu’à 64000 extents. Une page DCM correspond à la 8ème page (page d’ID 7) d’un fichier de données. Et il y a une page DCM toutes les 511230 pages si la base de données est supérieure à 4 Go en termes de stockage de données.
Notons que dans le cas des pages PFS, il n’y a pas de bit pour chaque extent à proprement parler. En effet, SQL Server utilise un byte (ou unité d’adressage) pour chaque page, sachant que les bits de chaque byte sont encodés de la façon suivante :

  • bits 0 à 2 à quantité d’espace disponible dans une page :
    • 0x00 signifie que la page est libre.
    • 0x01 signifie que le taux de saturation est compris entre 1 et 50%.
    • 0x02 signifie que le taux de saturation est compris entre 51 et 80%.
    • 0x03 signifie que le taux de saturation est compris entre 81 et 95%.
    • 0x04 signifie que le taux de saturation est compris entre 96 et 100%.
  • bit 3 (0x08) à détermine la présence ou non d’enregistrements fantômes dans la page.
  • bit 4 (0x10) à détermine si la page est une page IAM.
  • bit 5 (0x20) à détermine si la page est une page mixte.
  • bit 6 (0x40) à détermine si la page est une page allouée.
  • Bit 7 à détermine si la page est inutilisée.

Au regard de l’ensemble des informations fournies dans le tableau ci-dessus, et relatives aux différents types de pages constituant un fichier de données, on peut arriver au schéma tabulaire des pages d’allocation au sein de l’architecture d’un fichier de données suivant :


L’exemple ci-dessus montre le positionnement des différents types de pages de données au sein d’un fichier d’une taille supérieure à 4 Go. Pour rappel, un fichier de données de plus de 4 Go possède plusieurs espaces GAM, SGAM, IAM (1 par espace GAM), DCM et BCM. On rappelle également qu’une page IAM peut se retrouver en mémoire.



Tableau des différentes combinaisons de bits des pages GAM, SGAM et IAM

Le tableau ci-dessous donne un aperçu du résultat des combinaisons de bits des pages GAM, SGAM et IAM pour un extent :

GAM SGAM IAM Résultat
0 0 0 Extent mixte avec toutes les pages allouées.
0 0 1 Extent uniforme (et devant être alloué à une seule page IAM).
0 1 0 Extent mixte avec au moins une page non-utilisée.
0 1 1 Etat incorrect.
1 0 0 Extent non-alloué.
1 0 1 Etat incorrect.
1 1 0 Etat incorrect.
1 1 1 Etat incorrect.

On peut noter que seules 4 combinaisons sur 8 pour n’importe quel extent sont valides. Par contre, toute autre combinaison peut mener vers des problèmes de corruptions.

Pour aller plus loin…

Dans ce billet, on a pu aborder et comprendre l’architecture d’un fichier de données. Dans de futurs billets, nous étudierons l’architecture d’un index, ainsi que la gestion efficace de fichiers de données.

Références

Publicités

Laisser un commentaire

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l'aide de votre compte WordPress.com. Déconnexion / Changer )

Image Twitter

Vous commentez à l'aide de votre compte Twitter. Déconnexion / Changer )

Photo Facebook

Vous commentez à l'aide de votre compte Facebook. Déconnexion / Changer )

Photo Google+

Vous commentez à l'aide de votre compte Google+. Déconnexion / Changer )

Connexion à %s