2. Dispositifs de stockage

Une base de données est constituée, matériellement, d’un ou plusieurs fichiers stockés sur un support non volatile. Le support le plus couramment employé est le disque magnétique (“disque dur”) qui présente un bon compromis en termes de capacité de stockage, de prix et de performance. Un concurrent sérieux est le Solid State Drive, dont les performances sont nettement supérieures, et le coût en baisse constante, ce qui le rend de plus en plus concurrentiel.

Il y a deux raisons principales à l’utilisation de fichiers. Tout d’abord il est possible d’avoir affaire à des bases de données dont la taille dépasse de loin celle de la mémoire principale. Ensuite – et c’est la justification principale du recours aux fichiers, même pour des bases de petite taille – une base de données doit survivre à l’arrêt de l’ordinateur qui l’héberge, que cet arrêt soit normal ou dû à un incident matériel.

Important

Une donnée qui n’est pas sur un support persistant est potentiellement perdue en cas de panne.

L’accès à des données stockées sur un support persistant, par contraste avec les applications qui manipulent des données en mémoire centrale, est une des caractéristiques essentielles d’un SGBD. Elle implique notamment des problèmes potentiels de performance puisque le temps de lecture d’une information sur un disque est considérablement plus élevé que celui d’un accès en mémoire principale. L’organisation des données sur un disque, les structures d’indexation et les algorithmes de recherche utilisés constituent donc des aspects essentiels des SGBD du point de vue des performances.

Une bonne partie du présent cours est, de fait, consacrée à des méthodes, techniques et structures de données dont le but principal est de limiter le nombre et la taille de données lues sur le support persistant.

Un bon système se doit d’utiliser au mieux les techniques disponibles afin de minimiser les temps d’accès. Dans ce chapitre nous décrivons les techniques de stockage de données et le transfert de ces dernières entre les différents niveaux de mémoire d’un ordinateur. La première partie est consacrée aux dispositifs de stockage. Nous détaillons successivement les différents types de mémoire utilisées, en insistant particulièrement sur le fonctionnement des disques magnétiques. Nous abordons en seconde partie les principales techniques de gestion de la mémoire utilisées par un SGBD.

S1: Supports de stockage

Un système informatique offre plusieurs mécanismes de stockage de l’information, ou mémoires. Ces mémoires se différencient par leur prix, leur rapidité, le mode d’accès aux données (séquentiel ou par adresse) et enfin leur durabilité.

  • Les mémoires volatiles perdent leur contenu quand le système est interrompu, soit par un arrêt volontaire, soit à cause d’une panne.
  • Les mémoires persistantes comme les disques magnétiques, les SSD, les CD ou les bandes magnétiques, préservent leur contenu même en l’absence d’alimentation électrique.

Mémoires

D’une manière générale, plus une mémoire est rapide, plus elle est chère et – conséquence directe – plus sa capacité est réduite. Les différentes mémoires utilisées par un ordinateur constituent donc une hiérarchie (Fig. 2.1), allant de la mémoire la plus petite mais la plus efficace à la mémoire la plus volumineuse mais la plus lente.

  1. la mémoire cache est une mémoire intermédiaire permettant au processeur d’accéder très rapidement aux données à traiter ;
  2. la mémoire vive, ou mémoire principale stocke les données et les processus constituant l’espace de travail de la machine; toute information (donnée ou programme) doit être en mémoire principale pour pouvoir être traitée par un processeur ;
  3. les disques magnétiques constituent le principal périphérique de mémoire persistante; ils offrent une grande capacité de stockage tout en gardant des accès en lecture et en écriture relativement efficaces;
  4. les Solid State Drive ou SSD sont une alternative récente aux disques magnétiques; leurs peformances sont supérieures, mais leur coût élevé;
  5. enfin les CD ou les bandes magnétiques sont des supports très économiques mais leur lenteur les destine plutôt aux sauvegardes à long terme.
_images/hiermem.png

Fig. 2.1 Hiérarchie des mémoires

La mémoire vive (que nous appellerons mémoire principale) et les disques (ou mémoire secondaire) sont les principaux niveaux à considérer pour des applications de bases de données. Une base de données doit être stockée sur disque, pour les raisons de taille et de persistance déjà évoquées, mais les données doivent impérativement être transférées en mémoire vive pour être traitées. Dans l’hypothèse (réaliste) où seule une fraction de la base peut résider en mémoire centrale, un SGBD doit donc en permanence effectuer des transferts entre mémoire principale et mémoire secondaire pour satisfaire les requêtes des utilisateurs. Le coût de ces transferts intervient de manière prépondérante dans les performances du système.

Vocabulaire: Mais qu’est-ce qu’une “donnée”?

Le terme de donnée désigne le codage d’une unité d’information. Dans le contexte de ce cours, “donnée” sera toujours synonyme de nuplet (ligne dans une table). On parlera parfois d’enregistrement quand la perspective “stockage” est privilégiée.

Dans d’autres contextes, une donnée peut être un document, un flux d’octets, etc. Du point de vue de l’application, et de l’information qu’elle manipule, une “donnée” est l’unité de lecture et d’écriture.

La technologie évoluant rapidement, il est délicat de donner des valeurs précises pour la taille des différentes mémoires. Un ordinateur est typiquement équipé de quelques Gigaoctets de mémoire vive (typiquement 4 à 16 Go pour un ordinateur personnel, plusieurs dizaines de Go pour un serveur de données). La taille d’un disque magnétique est de l’ordre du Téraoctet, soit un rapport de 1 à 1 000 avec les données en mémoire centrale. Les SSD ont des tailles comparables à celles des disques magnétiques (pour un coût supérieur).

Performances des mémoires

Comment mesurer les performances d’une mémoire? Nous retiendrons deux critères essentiels:

  • Temps d’accès: connaissant l’adresse d’une donnée, quel est le temps nécessaire pour aller à l’emplacement mémoire indiqué par cette adresse et obtenir l’information ? On parle de lecture par clé ou encore d’accès direct pour cette opération;
  • Débit: quel est le volume de données lues par unité de temps dans le meilleur des cas?

Le premier critère est important quand on effectue des accès dits aléatoires. Ce terme indique que deux accès successifs s’effectuent à des adresses indépendantes l’une de l’autre, qui peuvent donc être très éloignées. Le second critère est important pour les accès dits séquentiels dans lesquels on lit une collection d’information, dans un ordre donné. Ces deux notions sont essentielles.

Notion: accès direct/accès séquentiel

Retenez les notions suivantes:
  • Accès direct: étant donné une adresse dans la mémoire (et principalement sur un disque), on accède à la donnée stockée à cette adresse.
  • Accès séquentiel: on parcours la mémoire (et principalement un disque) dans un certain ordre pour lire les données au fur et à mesure.

Les performances des deux types d’accès sont extrêmement variables selon le type de support mémoire. Le temps d’un accès direct en mémoire vive est par exemple de l’ordre de 10 nanosecondes (\(10^{-8}\) sec.), de 0,1 millisecondes pour un SSD, et de l’ordre de 10 millisecondes (\(10^{-2}\) sec.) pour un disque. Cela représente un ratio approximatif de 1 000 000 (1 million!) entre les performances respectives de la mémoire centrale et du disque magnétique ! Il est clair dans ces conditions que le système doit tout faire pour limiter les accès au disque.

Le tableau suivant résumé les ordres de grandeur des temps d’acès pour les différentes mémoires.

Tableau 2.1 Performance des divers types de mémoire
Type mémoire Taille Temps d’accès aléatoire Temps d’accès séquentiel
Mémoire cache (Static RAM) Quelques Mo \(\approx 10^{-8}\) (10 nanosec.) Plusieurs dizaines de Gos par seconde
Mémoire principale (Dynamic RAM) Quelques Go \(\approx 10^{-8} - 10^{-7}\) (10-100 nanosec.) Quelques Go par seconde
Disque magnétique Quelques Tos \(\approx 10^{-2}\) (10 millisec.) Env. 100 Mo par seconde.
SSD Quelques Tos \(\approx 10^{-4}\) (0,1 millisec.) Jusqu’à quelques Gos par seconde.

Disques

Les disques sont les composants les plus lents, et pourtant ils sont indispensables pour la gestion d’une base de données. Il est donc très utile de comprendre comment ils fonctionnent. Nous parlons essentiellement des disques magnétiques, avec un bref aperçu des SSD (dont l’importance est sûrement amenée à croître rapidement).

Dispositif

Un disque magnétique est une surface circulaire magnétisée capable d’enregistrer des informations numériques. La surface magnétisée peut être située d’un seul côté (“simple face”) ou des deux côtés (“double face”) du disque.

Les disques sont divisés en secteurs, un secteur constituant la plus petite surface d’adressage. En d’autres termes, on sait lire ou écrire des zones débutant sur un secteur et couvrant un nombre entier de secteurs (1 au minimum: le secteur est l’unité de lecture sur le disque). La taille d’un secteur est le plus souvent de 512 octets.

La plus petite information stockée sur un disque est un bit qui peut valoir 0 ou 1. Les bits sont groupés par 8 pour former des octets, les octets groupés par 64 pour former des secteurs, et une suite de secteurs forme un cercle ou piste sur la surface du disque.

Un disque est entraîné dans un mouvement de rotation régulier par un axe. Une tête de lecture (deux si le disque est double-face) vient se positionner sur une des pistes du disque et y lit ou écrit les données. Le nombre minimal d’octets lus par une tête de lecture est physiquement défini par la taille d’un secteur (en général 512 octets). Cela étant le système d’exploitation peut choisir, au moment de l’initialisation du disque, de fixer une unité d’entrée/sortie supérieure à la taille d’un secteur, et multiple de cette dernière. On obtient des blocs, dont la taille est typiquement 512 octets (un secteur), 1 024 octets (deux secteurs) ou 4 096 octets (huit secteurs).

Chaque piste est donc divisée en blocs (ou pages) qui constituent l’unité d’échange entre le disque et la mémoire principale.

_images/disques.png

Fig. 2.2 Fonctionnement d’un disque magnétique.

Toute lecture ou toute écriture sur les disques s’effectue par blocs. Même si la lecture ne concerne qu’une donnée occupant 4 octets, tout le bloc contenant ces 4 octets sera transmis en mémoire centrale. Cette caractéristique est fondamentale pour l’organisation des données sur le disque. Un des objectifs du SGBD est de faire en sorte que, quand il est nécessaire de lire un bloc de 4 096 octets pour accéder à un entier de 4 octets, les 4 092 octets constituant le reste du bloc ont de grandes chances d’être utiles à court terme et se trouveront donc déjà chargée en mémoire centrale quand le système en aura besoin. C’est un premier exemple du principe de localité que nous discutons plus loin.

Notion: bloc

Retenez la notion de bloc, zone mémoire contigue stockée sur disque, lue ou écrite solidairement. Le bloc est l’unité d’entrée/sortie entre la mémoire secondaire et la mémoire principale.

La tête de lecture n’est pas entraînée dans le mouvement de rotation. Elle se déplace dans un plan fixe qui lui permet de se rapprocher ou de s’éloigner de l’axe de rotation des disques, et d’accéder à l’une des pistes. Pour limiter le coût de l’ensemble de ce dispositif et augmenter la capacité de stockage, les disques sont empilés et partagent le même axe de rotation (voir Fig. 2.2). Il y a autant de têtes de lectures que de disques (deux fois plus si les disques sont à double face) et toutes les têtes sont positionnées solidairement dans leur plan de déplacement. À tout moment, les pistes accessibles par les têtes sont donc les mêmes pour tous les disques de la pile, ce qui constitue une contrainte dont il faut savoir tenir compte quand on cherche à optimiser le placement des données.

L’ensemble des pistes accessibles à un moment donné constitue le cylindre. La notion de cylindre correspond donc à toutes les données disponibles sans avoir besoin de déplacer les têtes de lecture.

Enfin le dernier élément du dispositif est le contrôleur qui sert d’interface avec le système d’exploitation. Le contrôleur reçoit du système des demandes de lecture ou d’écriture, et les transforme en mouvements appropriés des têtes de lectures, comme expliqué ci-dessous.

Entrées/sorties sur un disque

Un disque est une mémoire à accès dit semi-direct. Contrairement à une bande magnétique par exemple, il est possible d’accéder à une information située n’importe où sur le disque sans avoir à parcourir séquentiellement tout le support. Mais contrairement à la mémoire principale, avant d’accéder à une adresse, il faut attendre un temps variable lié au mécanisme de rotation du disque.

L’accès est fondé sur une adresse donnée à chaque bloc au moment de l’initialisation du disque par le système d’exploitation. Cette adresse est composée des trois éléments suivants :

  1. le numéro du disque dans la pile ou le numéro de la surface si les disques sont à double-face ;
  2. le numéro de la piste ;
  3. le numéro du bloc sur la piste.

La lecture d’un bloc, étant donné son adresse, se décompose en trois étapes :

  1. positionnement de la tête de lecture sur la piste contenant le bloc ;
  2. rotation du disque pour attendre que le bloc passe sous la tête de lecture (rappelons que les têtes sont fixes, c’est le disque qui tourne) ;
  3. transfert du bloc.

La durée d’une opération de lecture est donc la somme des temps consacrés à chacune des trois opérations, ces temps étant désignés respectivement par les termes délai de positionnement, délai de latence et temps de transfert. Le temps de transfert est négligeable pour un bloc, mais peu devenir important quand des milliers de blocs doivent être lus. Le mécanisme d’écriture est à peu près semblable à la lecture, mais peu prendre un peu plus de temps si le contrôleur vérifie que l’écriture s’est faite correctement.

La latence de lecture fait du disque une mémoire à accès semi-direct, comme mentionné précédemment. C’est aussi cette latence qui rend le disque lent comparé aux autres mémoires, surtout si un déplacement des têtes de lecture est nécessaire. Une conséquence très importante est qu’il est de très loin préférable de lire sur un disque en accès séquentiel que par une séquence d’accès aléatoires (cf. exercices).

Spécifications d’un disque

Le Tableau 2.2 donne les spécifications d’un disque, telles qu’on peut les trouver sur le site de n’importe quel constructeur. Les chiffres donnent un ordre de grandeur pour les performances d’un disque, étant bien entendu que les disques destinés aux serveurs sont beaucoup plus performants que ceux destinés aux ordinateurs personnels. Le modèle donné en exemple appartient au mileu de gamme.

Le disque comprend 5 335 031 400 secteurs de 512 octets chacun, la multiplication des deux chiffres donnant bien la capacité totale de 2,7 To. Les secteurs étant répartis sur 3 disques double-face, il y a donc 5 335 031 400 / 6 = 889 171 900 secteurs par surface.

Le nombre de secteurs par piste n’est pas constant, car les pistes situées près de l’axe sont bien entendu beaucoup plus petites que celles situées près du bord du disque. On ne peut, à partir des spécifications, que calculer le nombre moyen de secteurs par piste, qui est égal à \(889 171 900/15 300=58 115\). On peut donc estimer qu’une piste stocke en moyenne \(58 115 \times 512 = 29\) Mégaoctets. Ce chiffre donne le nombre d’octets qui peuvent être lus en séquentiel, sans délai de latence ni délai de positionnement.

Tableau 2.2 Spécification d’un disque
Caractéristique Performance
Capacité 2,7 To
Taux de transfert 100 Mo/s
Cache 3 Mo
Nbre de disques 3
Nbre de têtes 6
Nombre de cylindres 15 300
Vitesse de rotation 10 000 rpm (rotations par minute)
Délai de latence En moyenne 3 ms
Temps de positionnement moyen 5,2 ms
Déplacement de piste à piste 0,6 ms

Les temps donnés pour le temps de latence et le délai de rotation ne sont que des moyennes. Dans le meilleur des cas, les têtes sont positionnées sur la bonne piste, et le bloc à lire est celui qui arrive sous la tête de lecture. Le bloc peut alors être lu directement, avec un délai réduit au temps de transfert.

Ce temps de transfert peut être considéré comme négligeable dans le cas d’un bloc unique, comme le montre le raisonnement qui suit, basé sur les performances du Tableau 2.2. Le disque effectue 10 000 rotations par minute, ce qui correspond à 166,66 rotations par seconde, soit une rotation toutes les 0,006 secondes (6 ms). C’est le temps requis pour lire une piste entièrement. Cela donne également le temps moyen de latence de 3 ms.

Pour lire un bloc sur une piste, il faudrait tenir compte du nombre exact de secteurs, qui varie en fonction de la position exacte. En prenant comme valeur moyenne 303 secteurs par piste, et une taille de bloc égale à 4 096 soit huit secteurs, on obtient le temps de transfert moyen pour un bloc :

\[\frac{6ms \times 8}{303} = 0,16 ms\]

Le temps de transfert ne devient significatif que quand on lit plusieurs blocs consécutivement. Notez quand même que les valeurs obtenues restent beaucoup plus élevées que les temps d’accès en mémoire principale qui s’évaluent en nanosecondes.

Dans une situation moyenne, la tête n’est pas sur la bonne piste, et une fois la tête positionnée (temps moyen 5.2 ms), il faut attendre une rotation partielle pour obtenir le bloc (temps moyen 3 ms). Le temps de lecture est alors en moyenne de 8.2 ms, si on ignore le temps de transfert.

Un mot sur les Solid State Drives

Un disque solid-state, ou SSD, est bâti sur la mémoire dite flash, celle utilisée pour les clés USB. Ce matériel est constitué de mémoires à semi-conducteurs à l’état solide. Contrairement aux disques magnétiques à rotation, les emplacements mémoire sont à accès direct, ce qui élimine le temps de latence.

Le temps d’accès direct est considérablement diminué, de l’ordre de quelques dixièmes de millisecondes, soit cent fois moins (encore une fois il s’agit d’un ordre de grandeur) que pour un disque magnétique. Le débit en lecture/écriture est également bien plus important, de l’ordre de 1 Go par sec, soit 10 fois plus efficace. La conclusion simple est que le meilleur moyen d’améliorer les performances d’une base de données est de la placer sur un disque SSD, avec des résultats spectaculaires ! Evidemment, il y a une contrepartie: le coût est plus élevé que pour un disque traditionnel, même si l’écart tend à diminuer. En 2015, il faut compter 200 à 300 Euros pour un disque SSD d’un demi Téraoctet, environ 10 fois moins pour un disque magnétiqe de même capacité.

Un problème technique posé par les SSD est que le nombre d’écritures possibles sur un même secteur est limité. Les constructeurs ont semble-t-il bien géré cette caractéristique, le seul inconvénient visible étant la diminution progressive de la capacité du disque à cause des secteurs devenus inutilisables.

En conclusion, les SSD ont sans doute un grand avenir pour la gestion des bases de données de taille faible à moyenne (disons de l’ordre du Téraoctet). Si on ne veut pas se casser la tête pour améliorer les performances d’un système, le passage du disque magnétique au SSD est une méthode sûre et rapide.

Quiz

  • Pourquoi faut-il placer une base de données sur une mémoire persistante?

    • Parce qu’elle est plus efficace.
    • Parce qu’elle peut stocker des données plus volumineuses.
    • Parce qu’elle n’est pas affectée par des pannes légères.
    • Parce la structure d’une base de données ne peut être encodée que sur un disque magnétique.
  • Qu’entend-on par accès direct

    • On va lire sur le disque sans passer par la mémoire principale.
    • On va lire sur le disque à un emplacement précis
    • On balaye les pistes du disque dans un ordre précis.
  • Qu’entend-on par accès aléatoire

    • On lit au hasard sur le disque.
    • On lit soit sur le disque, soit dans la mémoire RAM.
    • On va lire sur le disque sans tenir compte de la position des têtes de lecture.
  • Quelles affirmations sur les blocs sont vraies:

    • c’est un espace de taille variable qui contient un groupe de données
    • deux données d’un même bloc sont toujours transférées ensemble.
    • un bloc a un emplacement fixe sur un disque
    • un système peut choisir de lire ou dècrire un fragment d’un bloc.
  • Pourquoi vaut-il mieux lire une collection de données par un accès séquentiel plutôt que par un ensemble d’accès aléatoires.

    • Parce c’est plus simple à programmer (une adresse et une taille suffisent)
    • Parce qu’on limite au minimum les déplacements des têtes de lecture.
    • Parce qu’on ne risque pas de rater des données.

Exercices

Exercice: temps de lecture d’une base

Nous avons une base de 3 Tos. Quel est le temps de lecture minimal de la base complète sur un disque magnétique? Et en mémoire centrale (en supposant la capacité de cette dernière suffisante)?

On veut lire 100 objets de 10 octets. Combien de temps cela prend-il s’ils sont sur un disque? Et s’ils sont en mémoire centrale?

Exercice: lectures séquentielles et aléatoires sur un disque

On dispose d’une base de 3 Go constituée d’enregistrements dont la taille moyenne est 3 000 octets.

  • Combien de temps prend la lecture complète de cette base avec un parcours séquentiel ?
  • Combien de temps prend la lecture en effectuant un accès aléatoire pour chaque enregistrement ?

Vous pouvez prendre les valeurs du Tableau 2.1 pour les calculs.

Exercice: Spécifications d’un disque magnétique

Le Tableau 2.3 donne les spécifications partielles d’un disque magnétique. Répondez aux questions suivantes.

  • Quelle est la capacité d’une piste?, d’un cylindre? d’une surface? du disque?
  • Quel est le temps de latence maximal?
  • Quel est le temps de latence moyen?
  • Quel est le taux de transfert (en Mo/sec) nécessaire pour pouvoir transmettre le contenu d’une piste en une seule rotation?
Tableau 2.3 Un (vieux) disque magnétique
Caractéristique Valeur
Taille d’un secteur 512 octets
Nbre de plateaux 5
Nbre de têtes 10
Nombre de secteurs 5 335 031 400,00
Nombre de cylindres 10 000
Nombre de secteurs par piste 400
Temps de positionnement moyen 10 ms
Vitesse de rotation 7 400 rpm
Déplacement de piste à piste 0,5 ms

S2: Gestion des mémoires

Un SGBD doit gérer essentiellement deux mémoires: la mémoire principale, et la mémoire secondaire (le disque). Toutes les données doivent être en mémoire secondaire, pour des raisons de persistance. Une partie de ces données est en mémoire principale, pour des raisons de performance.

La Fig. 2.3 illustre ces deux composants essentiels. Tout serveur de base de données s’exécute sur une machine qui lui alloue une partie de sa mémoire RAM, que nous appelerons mémoire tampon ou cache pour faire simple, ainsi qu’une partie du disque magnétique. Ces deux ressources sont gérées par un module du SGBD, le gestionnaire des accès (GA dans ce qui suit).

_images/buffer-disque.png

Fig. 2.3 Le cache et le disque, ressources mémoires allouées au SGBD

Les données sont disponibles dans des blocs qui constituent l’unité de lecture et d’écriture sur le disque. Le GA exécute des requêtes de lecture ou d’écriture de données, et nous allons considérer comme acquis que ces requêtes comprennent toujours l’adresse du bloc. Cette section explique comment ces requêtes sont exécutées.

Les lectures

Comme le montre la Fig. 2.3, le cache est constitué de blocs en mémoire principale qui sont des copies de blocs sur le disque. Quand une lecture est requise, deux cas sont possibles:

  • la donnée fait partie d’un bloc qui est déjà dans le cache, le GA prend le bloc, accède à la donnée et la retourne;
  • sinon il faut d’abord lire un bloc du disque, et le placer dans le cache, pour se ramener au cas précédent.

La demande d’accès est appelée lecture logique: elle ignore si la donnée est présente en mémoire ou non. Le GA détermine si une lecture physique sur le disque est nécessaire. La lecture physique implique le chargement d’un bloc du disque vers le cache

Note

Comment faire pour savoir si un bloc est ou non en cache? Grâce à une table de hachage (illustrée sur la Fig. 2.3) qui pointe sur les blocs chargés en mémoire. L’accès à bloc, étant donnée son adresse, est extrêmement rapide avec une telle structure.

Un SGBD performant cherche à maintenir en mémoire principale une copie aussi large que possible de la base de données, et surtout la partie la plus utilisée. Le paramètre qui mesure l’efficacité d’une mémoire tampon est le hit ratio, défini comme suit :

\[\text{hit ratio} = \frac{\text{nbLecturesLogiques} - \text{nbLecturesPhysiques}}{\text{nbLecturesLogiques}}\]

Si toutes les lectures logiques (demande de bloc) aboutissent à une lecture physique (accès au disque), le hit ratio est 0 ; s’il n’y a aucune lecture physique (toutes les données demandées sont déjà en mémoire), le hit ratio est de 1.

Il est très important de comprendre que le hit ratio n’est pas simplement le rapport entre la taille de la mémoire cache et celle de la base. Ce serait vrai si tous les blocs étaient lues avec une probabilité uniforme, mais le hit ratio représente justement la capacité du système à stocker dans le cache les pages les plus lues.

Plus la mémoire cache est importante, et plus il sera possible d’y conserver une partie significative de la base, avec un hit ratio élevé et des gains importants en terme de performance. Cela étant le hit ratio ne croît toujours pas linéairement avec l’augmentation de la taille de la mémoire cache. Si la disproportion entre la taille du cache et celle de la base est élevée, le hit ratio est conditionné par le pourcentage des accès à la base qui peuvent lire n’importe quelle page avec une probabilité uniforme. Prenons un exemple pour clarifier les choses.

Un exemple pour comprendre

La base de données fait 2 GigaOctets, le cache 30 MégaOctets.

Supposons qued dans 60 % des cas une lecture logique s’adresse à une partie limitée de la base, correspondant aux principales tables de l’application, dont la taille est, disons 200 Mo. Dans les 40 % de cas suivants les accès se font avec une probabilité uniforme dans les 1,8 Go restant.

En augmentant la taille du cache jusqu’à 333 Mo, on va améliorer régulièrement le hit ratio jusqu’à environ 0,6. En effet les 200 Mo correspondant à 60 % des lectures vont finir par se trouver placées en cache (\(200\ Mo\ =\ 333 \times 0,6\)), et n’en bougeront pratiquement plus. En revanche, les 40 % des autres accès accèderont à 1,8 Go avec seulement 133 Mo et le hit ratio restera très faible pour cette partie-là.

Conclusion : si vous cherchez la meilleure taille pour un cache sur une très grosse base, faites l’expérience d’augmenter régulièrement l’espace mémoire alloué jusqu’à ce que la courbe d’augmentation du hit ratio s’applatisse. En revanche sur une petite base où il est possible d’allouer un cache de taille comparable à la base, on a la possibilité d’obtenir un hit ratio optimal de 1.

Les mises à jour

Pour les lectures, les techniques sont finalement assez simple. Avec les écritures cela se complique, mais cela va nous permettre de vérifier la mise en œuvre d’un principe fondamental que nous retrouverons systématiquement par la suite:

Principe (rappel)

Il faut toujours éviter dans la mesure du possible d’effectuer des écritures aléatoires et préférer des écritures séquentielles.

À ce principe correspond un technique, elle aussi fondamentale (elle se retrouve bien au-delà des SGBD), celle des fichiers journaux (logs).

Une approche naïve

En première approche, on peut procéder comme pour une lecture

  • on trouve dans le cache le bloc contenant la donnée, ou on le charge dans le cache s’il n’y est pas déjà;
  • on effectue la mise à jour sur la donnée dans le cache;

On se retrouve dans la situation de la Fig. 2.4: le bloc contenant la donnée est marquée comme étant “modifié” (en pratique, chaque bloc contient un marqueur dit dirty qui indique si une modification a été effectuée par rapport à la version du même bloc sur le disque). On se trouve alors face à deux mauvais choix:

  • soit on garde le bloc modifié en mémoire, en attendant qu’une opportunité se présente pour effectuer l’écriture sur le disque; dans l’intervalle, toute panne du serveur entraîne la perte de la modification;
  • soit on écrit le bloc sur le disque pour remplacer la version non modifiée, et on se ramène à des écritures non ordonnées, aléatoires et donc pénalisantes.
_images/write-naif.png

Fig. 2.4 Gestion naïve des écritures: les blocs doivent être écrits en ordre aléatoire.

Il faut bien réaliser qu’un bloc peut contenir des centaines de données, et que déclencher une écriture sur disque dès que l’une d’entre elles est modifiée va à l’encontre d’un principe de regroupementqui vise à limiter les entrées/sorties sur la mémoire persistante.

Les fichiers journaux (logs)

La bonne technique est plus complexe, mais beaucoup plus performante. Elle consiste à procéder comme dans le cas naïf, et à écrire séquentiellement la mise à jour dans un fichier séquentiel, distinct de la base, mais utilisable pour effectuer une reprise en cas de panne.

La méthode est illustrée par la Fig. 2.5. Le cache est divisé en deux parties, ainsi que la mémoire du disque. Idéalement, on dispose de deux disques (nous reviendrons sur ces aspects dans le chapitre Reprise sur panne). Le premier cache est celui de la base, comme précédemment. Le second sert de tampon, intermédiaire à un fichier particulier, le journal (ou log) qui enregistre toutes les opérations de mise à jour.

Au moment d’une mise à jour, le bloc de la base modifié n’est pas écrit sur disque. En revanche la commande de mise à jour est écrite séquentiellement dans le fichier journal.

_images/recovery.png

Fig. 2.5 Gestion des écritures avec fichier journal

On évite donc les écritures aléatoires, tout en s’assurant que toute commande de mise à jour est écrite sur disque et pourra donc servir à une reprise en cas de panne.

Que devient le bloc modifié dans le cache de la base? Et bien, il sera écrit sur disque de manière opportuniste, quand un événement rendra cette écriture nécessaire. Par exemple:

  • le cache est plein et il faut faire de la place;
  • le serveur est arrêté;
  • la base est inactive, et le système estime que le moment est venu de déclencher une synchronisation.

Le point important, c’est qu’au moment de l’écriture effective, l’opération sera probablement bien plus “rentable” qu’avec la solution naïve. En premier lieu, le bloc contiendra sans doute n données modifiées, et on aura donc remplacé n écritures (solution naïve) par une seule. En second lieu, il est possible que plusieurs blocs contigus sur le disque doivent être écrits, ce qui permet une écriture séquentielle évitant le délai de latence. Enfin, le système gagne ainsi une marge de manœuvre pour choisir le bon moment pour déclencher les écritures.

En résumé, cette technique basée sur les fichiers journaux, outre son intérêt intrinsèque, est une excellente illustration des efforts consacrés par les SGBD à privilégier les accès groupés et séquentiels au dépend des accès aléatoires et individuels.

Important

Les fichiers journaux sont à la base des techniques de reprise sur panne décrites dans le chapitre Reprise sur panne.

Le principe de localité

L’ensemble des techniques utilisées dans la gestion du stockage relève d’un principe assez général, dit de localité. Il résulte d’une observation pragmatique: l’ensemble des données utilisées par une application pendant une période donnée forme souvent un groupe bien identifié et présentant des caractéristiques de proximité.

  • Proximité spatiale: Si une donnée d est utilisée, les données “proches” de d ont de fortes chances de l’être également
  • Proximité temporelle: quand une application accède à une donnée d, il y a de fortes chances qu’elle y accède à nouveau peu de temps après.
  • Proximité de référence: si une donnée d1 référence une donnée d2, l’accès à d1 entraîne souvent l’accès à d2.

Sur la base de ce principe, un SGBD cherche à optimiser le placement les données “proches” de celles en cours d’utilisation. Cette optimisation se résume essentiellement à déplacer dans la hiérarchie des mémoires des groupes de données proches de la donnée utilisée à un instant t. Le pari est que l’application accèdera à d’autres données de ce groupe. Voici quelques mises en application de ce principe.

Localité spatiale: regroupement

Prenons un exemple simple pour se persuader de l’importance d’un bon regroupement des données sur le disque : le SGBD doit lire 5 chaînes de caractères de 1000 octets chacune. Pour une taille de bloc égale à 4096 octets, deux blocs peuvent suffire. La Fig. 2.6 montre deux organisations sur le disque. Dans la première chaque chaîne est placée dans un bloc différent, et les blocs sont répartis aléatoirement sur les pistes du disque. Dans la seconde organisation, les chaînes sont rassemblés dans deux blocs qui sont consécutifs sur une même piste du disque.

_images/orgadisk.png

Fig. 2.6 Mauvaise et bonne organisation sur un disque.

La lecture dans le premier cas implique 5 déplacements des têtes de lecture, et 5 délais de latence ce qui donne un temps de math:5 times (5.2 + 3) = 41 ms. Dans le second cas, on aura un déplacement, et un délai de latence pour la lecture du premier bloc, mais le bloc suivant pourra être lu instantanément, pour un temps total de 8,2 ms.

Les performances obtenues sont dans un rapport de 1 à 5, le temps minimal s’obtenant en combinant deux optimisations : regroupement et contiguïté. Le regroupement consiste à placer dans le même bloc des données qui ont de grandes chances d’êtres lues au même moment. Les critères permettant de déterminer le regroupement des données constituent un des fondements des structures de données en mémoire secondaire qui seront étudiées par la suite. Le placement dans des blocs contigus est une extension directe du principe de regroupement. Il permet d’effectuer des lectures séquentielles qui, comme le montre l’exemple ci-dessus, sont beaucoup plus performantes que les lectures aléatoires car elles évitent des déplacements de têtes de lecture.

Plus généralement, le gain obtenu dans la lecture de deux données \(d_1\) et \(d_2\) est d’autant plus important que les données sont “proches”, sur le disque, cette proximité étant définie comme suit, par ordre décroissant :

  1. la proximité maximale est obtenue quand \(d_1\) et \(d_2\) sont dans le même bloc : elles seront alors toujours lues ensembles ;
  2. le niveau de proximité suivant est obtenu quand les données sont placées dans deux blocs consécutifs ;
  3. quand les données sont dans deux blocs situés sur la même piste du même disque, elles peuvent être lues par la même tête de lecture, sans déplacement de cette dernière, et en une seule rotation du disque ;
  4. l’étape suivante est le placement des deux blocs dans un même cylindre, qui évite le déplacement des têtes de lecture ;
  5. enfin si les blocs sont dans deux cylindres distincts, la proximité est définie par la distance (en nombre de pistes) à parcourir.

Les SGBD essaient d’optimiser la proximité des données au moment de leur placement sur le disque. Une table par exemple devrait être stockée sur une même piste ou, dans le cas où elle occupe plus d’une piste, sur les pistes d’un même cylindre, afin de pouvoir effectuer efficacement un parcours séquentiel.

Pour que le SGBD puisse effectuer ces optimisations, il doit se voir confier, à la création de la base, un espace important sur le disque dont il sera le seul à gérer l’organisation. Si le SGBD se contentait de demander au système d’exploitation de la place disque quand il en a besoin, le stockage physique obtenu risque d’être très fragmenté.

Important

Retenez qu’un critère essentiel de performance pour une base de données est le stockage le plus contigu possible des données.

Localité temporelle: ordonnancement

En théorie, si un fichier occupant n blocs est stocké contiguement sur une même piste, la lecture séquentielle de ce fichier sera – en ignorant le temps de transfert – approximativement n fois plus efficace que si tous les blocs sont répartis aléatoirement sur les pistes du disque.

Cet analyse doit cependant être relativisée car un système est souvent en situation de satisfaire simultanément plusieurs utilisateurs, et doit gérer leurs demandes concurramment. Si un utilisateur A demande la lecture du fichier F1 tandis que l’utilisateur B demande la lecture du fichier F2, le système alternera probablement les lectures des blocs des deux fichiers. Même s’ils sont tous les deux stockés séquentiellement, des déplacements de tête de lecture interviendront alors et minimiseront dans une certaine mesure cet avantage.

_images/seqdisk.png

Fig. 2.7 Séquencement des entrées/sorties

Le système d’exploitation, ou le SGBD, peuvent réduire cet inconvénient en conservant temporairement les demandes d’entrées/sorties dans une zone tampon (cache) et en réorganisant (séquencement) l’ordre des accès. La Fig. 2.7 montre le fonctionnement d’un séquenceur. Un ensemble d’ordres de lectures est reçu, L(1-16) désignant par exemple la demande de lecture du bloc 16 sur la piste 1. On peut supposer sur cet exemple que deux utilisateurs effectuent séparément des demandes d’entrée/sortie qui s’imbriquent quand elles sont transmises vers le contrôleur.

Pour éviter les accès aléatoires qui résultent de cette imbrication, les demandes d’accès sont stockées temporairement dans un cache. Le séquenceur les trie alors par piste, puis par bloc au sein de chaque piste, et transmet la liste ordonnée au contrôleur du disque. Dans notre exemple, on se place donc tout d’abord sur la piste 1, et on lit séquentiellement les blocs 16, 17 et 18. Puis on passe à la piste 2 et on lit les blocs 23 et 24. Nous laissons au lecteur, à titre d’exercice, le soin de déterminer le gain obtenu.

Une technique pour systématiser cette stratégie est celle dite “de l’ascenseur”. L’idée est que les têtes de lecture se déplacent régulièrement du bord de la surface du disque vers l’axe de rotation, puis reviennent de l’axe vers le bord. Le déplacement s’effectue piste par piste, et à chaque piste le séquenceur transmet au contrôleur les demandes d’entrées/sorties pour la piste courante.

Cet algorithme réduit au maximum de temps de déplacement des têtes puisque ce déplacement s’effectue systématiquement sur la piste adjacente. Il est particulièrement efficace pour des systèmes avec de très nombreux processus demandant chacun quelques blocs de données. En revanche il peut avoir des effets assez désagréables en présence de quelques processus gros consommateurs de données. Le processus qui demande des blocs sur la piste 1 alors que les têtes viennent juste de passer à la piste 2 devra attendre un temps respectable avant de voir sa requête satisfaite.

Remplacement des blocs dans le cache

Pour finir sur les variantes de la localité, revenons sur ce qui se passe quand la mémoire cache est pleine et qu’un nouveau bloc doit être lu sur le disque. Un algorithme de remplacement doit être adopté pour retirer un des blocs de la mémoire et le replacer sur le disque (opérations dite de flush). L’algorithme le plus courant est dit Least Recently Used (LRU). Il consiste à choisir comme “victime” le bloc dont la dernière date de lecture logique est la plus ancienne. Ce bloc est alors soustrait de la mémoire centrale (il reste bien entendu sur le disque) et le nouveau bloc vient le remplacer.

Important

Si le bloc est marqué comme dirty (contenant des mises à jour) il faut l’écrire sur le disque.

La conséquence de cet algorithme est que le contenu du cache est une image fidèle de l’activité récente sur la base de données. Pour donner une illustration concrète de cet effet, supposons qu’une base soit divisée en trois parties distinctes X, Y et Z. L’application A1 ne lit que dans X, l’application A2 ne lit que dans Y, et l’application A3 ne lit que dans Z.

Si, dans la période qui vient de s’écouler, la base a été utilisée à 20% par A1, à 30% par A2 et à 50% par A3, alors on trouvera les mêmes proportions pour X, Y et Z dans le cache. Si seule A1 a accédé à la base, alors on ne trouvera que des données de X (en supposant que la taille de cette dernière soit suffisante pour remplir le cache).

Quand il reste de la place dans le cache, on peut l’utiliser en effectuant des lectures en avance (read ahead, ou prefetching). Une application typique de ce principe est donnée par la lecture d’une table. Comme nous le verrons au moment de l’étude des algorithmes de jointure, il est fréquent d’avoir à lire une table séquentiellement, bloc à bloc. Il s’agit d’un cas où, même si à un moment donné on n’a besoin que d’un ou de quelques blocs, on sait que toute la table devra être parcourue. Il vaut mieux alors, au moment où on effectue une lecture sur une piste, charger en mémoire tous les blocs de la relation, y compris ceux qui ne serviront que dans quelques temps et peuvent être placés dans un cache en attendant.

Quiz

  • Que contient le cache?

    • une copie des blocs de la base
    • des données complémentaires à celles stockées sur le disque
    • c’est un espace mémoire fourni aux applications qui utilisent la base.
  • Un cache peut-il être plus grand que la base sur le disque?

    • non
    • oui, et ça peut être utile
    • oui, mais ça n’a aucun intérêt
  • Une mise à jour se fait:

    • sur le disque, puis le bloc est transféré dans le cache?
    • dans le cache, puis le bloc est transféré sur le disque?
    • dans le cache, sans transfert immédiat.
  • Quel est l’inconvénient d’effectuer une mise à jour dans le cache et pas sur le disque?

    • la mise à jour n’est pas visible en lecture par les autres applications
    • la mise à jour peut être perdue en cas de panne
    • on perd en performance.
  • Quel est l’intérêt de ne pas écrire immédiatement un bloc contenant une donnée modifiée (plusieurs bonnes réponses possibles).

    • on évite d’écrire un bloc complet à chaque modification
    • on peut modifier une même donnée plusieurs fois de suite sans avoir à écrire sur le disque
    • on peut changer d’avis et revenir à la version stockée sur le disque.
  • Que signifie “proximité” sur un disque magnétique? Classez les critères suivants par ordre d’importance.

  • être sur des pistes proches.
  • être sur la même piste
  • être dans le même bloc
  • être dans le même cylindre

Exercices

Exercice: estimer des temps de lecture

Quelques calculs simples pour se convaincre de l’importance du regroupement sur disque. On dispose d’une table de 3 Go constituée de 300 000 enregistrements (je vous laisse calculer la taille moyenne d’un enregistrement).

  • quelle est la taille moyenne d’un enregistrement.
  • combien de temps prend la lecture complète de cette base avec un parcours séquentiel ?
  • combien de temps prend la lecture en effectuant un accès aléatoire pour chaque enregistrement ?

Prenez comme hypothèse les performances moyennes des disques vues précédemment.

Exercice: comprendre le hit ratio

On considère un fichier de 1 Go et un cache de 100 Mo.

  • quel est le hit ratio en supposant que la probabilité de lire les blocs est uniforme?
  • même question, en supposant que 80% des lectures concernent 200 Mo, les 20 % restant étant répartis uniformément sur 800 Mo?
  • avec l’hypothèse précédente, jusqu’à quelle taille de cache peut-on espérer une amélioration significative du hit ratio?

Prenez l’hypothèse que la stratégie de remplacement est de type LRU.