bd/bd02.xhtml

   1 <?xml version="1.0" encoding="utf-8" ?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
   3           "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd"
   4 [
   5           <!ENTITY in  "<small style='font-size:small'>∈</small>">
   6           <!ENTITY notin  "<small style='font-size:small'>∉</small>">
   7           <!ENTITY mapsto  "↦">
   8 ]
   9           >
  10 <html xmlns="http://www.w3.org/1999/xhtml" >
  11   <head>
  12     <title>Stockage</title>
  13
  14     <meta http-equiv="Content-Type"
  15           content="text/html; charset=utf-8" />
  16     <meta name="copyright"
  17           content="Copyright &#169; 2013 Kim Nguyễn" />
  18
  19     <!-- Load jQuery -->
  20     <script src="../jquery-2.0.3.min.js" type="text/javascript" ></script>
  21     <script src="../libs/raphael-min.js" type="text/javascript" ></script>
  22     <!-- Load the library -->
  23     <script src="../simpleWebSlides.js" type="text/javascript" ></script>
  24
  25     <link rel="stylesheet" href="../simpleWebSlides.css" type="text/css"  media="all" />
  26     <!-- Load a custom Theme, the class-element marks this style-sheet
  27          a "theme" that can be swtiched dynamicaly -->
  28     <link class="sws-theme" rel="stylesheet"  title="U-Psud style"  href="../themes/uPsud.css" type="text/css" />
  29
  30     <!-- Customize some templates and initialize -->
  31
  32     <script type="text/javascript">
  33       SWS.Config['sws-slide-change'] = SWS.Effects.slideChangeFadeOutIn;
  34       SWS.Config['sws-object-deactivate'] =  SWS.Effects.objectDeactivateFadeOut;
  35       SWS.Config['sws-object-activate'] = SWS.Effects.objectActivateFadeIn;
  36
  37       //Ensures that we load SWS at the very end, after MathJax has
  38       //been initialized
  39
  40       $(window).load(SWS.Presentation.init);
  41     </script>
  42   </head>
  43   <body>
  44     <a href="bd01.xhtml" class="sws-previous"/>
  45     <div class="sws-slide sws-cover sws-option-nofooter">
  46       <h1>Bases de données</h1>
  47       <h3>Polytech Paris-Sud</h3>
  48       <h3>Apprentis 4<sup>ème</sup> année</h3>
  49       <h1>Cours 2 : Stockage</h1>
  50       <a href="mailto:kn@lri.fr">kn@lri.fr</a><br/>
  51       <a href="http://www.lri.fr/~kn/">http://www.lri.fr/~kn</a>
  52     </div>
  53
  54     <h1>Introduction</h1>
  55     <div class="sws-slide">
  56       <h1>Où stocker les données ?</h1>
  57       <p>Hierarchie mémoire :  </p>
  58       <table style="width:100%">
  59         <tr><td style="width:20%">Type</td>
  60           <td style="width:20%">Accès</td>
  61           <td style="width:20%">Taille max</td>
  62           <td style="width:20%">Coût</td>
  63           <td style="width:20%">durée de vie</td></tr>
  64         <tr>
  65           <td>Registre</td> <td> <tt>&lt;</tt> 1ns</td>
  66           <td>128 bits</td>
  67           <td>Très cher</td>
  68           <td>alimenté</td>
  69         </tr>
  70
  71         <tr>
  72           <td>Cache L1/2/3</td> <td> ~ 10 ns</td>
  73           <td>1ko ~ 1Mo</td>
  74           <td>Très cher</td>
  75           <td>alimenté</td>
  76         </tr>
  77         <tr>
  78           <td>RAM</td> <td> ~ 50 ns</td>
  79           <td>10 Go </td>
  80           <td>Cher</td>
  81           <td>alimenté</td>
  82         </tr>
  83         <tr>
  84           <td>Disque SSD </td> <td> ~ 0.1ms</td>
  85           <td>1 To </td>
  86           <td>- Cher</td>
  87           <td>Écritures limitées</td>
  88         </tr>
  89         <tr>
  90           <td>Disque dur </td> <td> ~ 5ms</td>
  91           <td>10 To </td>
  92           <td>Peu cher</td>
  93           <td>Fragiles</td>
  94         </tr>
  95
  96         <tr>
  97           <td>Bandes</td> <td> 10 s</td>
  98           <td>1 Po/Eo </td>
  99           <td>Donné</td>
 100           <td>Bonne</td>
 101         </tr>
 102       </table>
 103
 104     <ul><li>RAM : mémoire primaire</li>
 105       <li>Disques : mémoire secondaire</li>
 106       <li>Bandes magnétiques/Disques optiques : mémoire tertiaire</li>
 107     </ul>
 108     </div>
 109     <div class="sws-slide">
 110       <h1>Quels types de mémoire pour une BD ?</h1>
 111       <p>On attend en général d'une BD:</p>
 112       <ul><li>Stockage d'un nombre important de données</li>
 113         <li>Interrogation rapide (et si possible, mise à jour rapide
 114         aussi)</li>
 115         <li>Resistance aux pannes, aux corruptions</li>
 116         <li>…</li>
 117       </ul>
 118       <p>Celà implique l'utilisation de mémoire primaire (comme toutes
 119       les applications) <em>et secondaire</em></p>
 120       <p>Pas <em>d'adressage direct du disque</em> par le processeur, nécessité de
 121       « monter » les données en RAM</p>
 122       <p>Goulet d'étranglement : facteur 10 000 (SSD) ~ 100 000 (HDD) entre
 123       mémoire et disques</p>
 124       <p><s>Priorité des SGBD</s> (ce qu'on présente dans ce cours) :
 125       limiter <em>les accès disque</em></p>
 126     </div>
 127     <h1>Aspects bas-niveau</h1>
 128     <div class="sws-slide">
 129       <h1>Caractéristiques physiques de disques</h1>
 130       <p>Disques rotatifs:</p>
 131       <div>
 132         <img src="hdd.svg" style="margin-left:10%;width:50%;" alt="hdd"/>
 133       </div>
 134       <ul style="background:white"><li>Chaque plateau a deux faces</li>
 135         <li>Un plateau est composé de pistes concentriques</li>
 136         <li>Les pistes sont décomposées en secteurs</li>
 137         <li>Une tête de lecture/écriture travaille secteur par
 138         secteur</li>
 139         <li>Un secteur fait plusieurs octets (typiquement 512)</li>
 140         <li>Un <i>cylindre</i> est l'ensemble des pistes situées à la
 141         même positions sur tous les plateaux</li>
 142       </ul>
 143     </div>
 144     <div class="sws-slide">
 145       <h1>Temps d'accès à un disque</h1>
 146       <p>Accès à un secteur arbitraire :</p>
 147       <ul>
 148         <li>Positionner la tête sur la bonne piste (recherche)</li>
 149         <li>Attendre que le bon secteur soit sous la tête
 150         (rotation)</li>
 151         <li>Parcourir le secteur et renvoyer les données en mémoire
 152         (transfert)</li>
 153       </ul>
 154       <p>Tout cela constitue la <em>latence</em> du disque</p>
 155       <p>Une fois qu'on a payé le temps de latence, lire le secteur
 156       suivant ne demande que le temps de transfert</p>
 157       <p>On va donc essayer d'organiser les données de manière éviter
 158       les déplacements arbitraires</p>
 159     </div>
 160     <div class="sws-slide">
 161       <h1>Unité de transfert</h1>
 162       <p>On appelle <em>page</em> (ou <em>bloc</em>) la quantité de
 163       mémoire que le disque dur transfert de manière atomique en
 164       mémoire. En pratique 512o ~ 4ko (dépendant des disques).
 165       </p>
 166       <p>On doit lire/écrire <s>au moins une page</s> même si on ne
 167       désir lire/écrire qu'un octet</p>
 168       <p>Exemple : on souhaite stocker 5 chaines de caractères de 200o
 169       chacunes sur le disque</p>
 170       <ul><li>Si placés sur blocs différents (arbitraires) : 5 pages
 171       montées en mémoire, <tt>5 * temps de latence</tt></li>
 172         <li>Si placés sur deux blocs consécutifs : <tt>temps de
 173         latence + temps de transfert</tt> (on gagne un facteur presque 5)
 174         </li></ul>
 175     </div>
 176     <div class="sws-slide">
 177       <h1>Stratégies de placement</h1>
 178       <p>On peut placer en priorité les données « reliées » (qu'on
 179       veut utiliser en même temps):</p>
 180       <ol>
 181         <li>Dans le même bloc (T.A. à la deuxième donnée:
 182         0)</li>
 183         <li>Sur deux blocs contigus (T.A. à la deuxième donnée:
 184         T. transfert)</li>
 185         <li>Bloc à la même position sur un autre plateau (T.A. à la
 186         deuxième donnée: T. transfert)</li>
 187         <li>Sur la même piste (T.A. à la deuxième donnée:
 188         T. rotation)</li>
 189         <li>Sur des pistes proches</li>
 190       </ol>
 191     </div>
 192     <div class="sws-slide">
 193       <h1>Mise en place de la stratégies de placement</h1>
 194       <p>Pour mettre en place les stratégies de placement il faut
 195       connaître:</p>
 196       <ul><li>La liste des blocs libres et occupés</li>
 197         <li>La liste des blocs occupés par un « fichier » (i.e. qui
 198         stocke des informations reliées à la même donnée logique)</li>
 199         </ul>
 200       <p>On ne travaille pas page à page : on alloue
 201         un <em>buffer</em> de pages</p>
 202       <p ><table class="withborder" style="margin-left:20%;">
 203         <tr><td style="width:10pt;">
 204         P1 </td><td style="width:10pt">P132 </td><td style="width:10pt">
 205         P10 </td><td style="width:10pt">P99 </td></tr>
 206         <tr><td style="width:10pt">
 207         P2 </td><td style="width:10pt"> P1000  </td><td style="width:10pt">     P507 </td><td style="width:10pt">
 208  </td></tr>
 209         <tr><td style="width:10pt"> </td><td style="width:10pt"> </td><td style="width:10pt"> </td><td style="width:10pt">
 210         </td></tr>
 211         </table><br/>
 212         On maintient pour chaque page : un <em>compteur
 213         d'utilisation</em> et un <em>dirty-bit</em> qui indique si la
 214         page a été modifiée (on doit donc l'écrire sur le disque à un
 215         moment donné).<br/>
 216         Lorsque le buffer est plein, il faut supprimer des pages (et
 217         en monter d'autres en mémoire) suivant une stratégie:
 218         LRU, MRU, Random, FIFO, LIFO, …
 219       </p>
 220     </div>
 221     <div class="sws-slide">
 222       <h1>Qui gère les accès disques bas-niveau, le buffer, … ?</h1>
 223       <p>
 224         <ul>
 225           <li class="sws-pause">Dans le temps, le SGBD
 226           directement </li>
 227           <li class="sws-pause">De nos jours, le système
 228           d'exploitation via ses systèmes de fichiers et gestion de la
 229           mémoire virtuelle (<i>swap</i> ou fichier d'echange)</li>
 230         </ul>
 231       </p>
 232       <p>Les systèmes d'exploitation ont <i>énormément</i> progressé
 233       (les SGBD ne pouvaient pas reposer sur quelque chose d'aussi
 234       primitif que FAT ou NTFS, mais les systèmes de fichier modernes
 235       sont plus performant que le traitement natif du disque fais par
 236       les SGBD, en particulier pour les SSD).<br/>
 237         Pour prédire le bon comportement d'un SGBD il faut connaître
 238       non seulement ce dernier, <s>mais aussi</s>, de manière
 239       détaillée, les caractéristiques de l'OS et du système de
 240       fichier.
 241       </p>
 242     </div>
 243     <div class="sws-slide">
 244       <h1>Un mot sur les SSD</h1>
 245       <p><i>Solid State Disk</i> : « disque » dur composé entièrement
 246       de mémoire flash. Avantages:</p>
 247       <ul style="sws-pause">
 248         <li>Pas de temps de recherche et de rotation, uniquement temps
 249         de transfert. Accès arbitraires aussi rapides que les
 250         séquentiels</li>
 251         <li>Consomation électrique moindre, poid moindre, pas de
 252         pièce mobile (resistance aux chocs)</li>
 253       </ul>
 254       <ul><li>Couteux</li>
 255         <li>Écriture <s>très</s> complexe (écrire dans une cellule
 256         impose de l'effacer avant, nombre de cycle d'effaçage limité,
 257         etc)
 258         </li>
 259         <li>Nécessite une coopération à tous les niveaux, seul le
 260         système d'exploitation peut bien le gérer (bibliothèque
 261         système, gestion de la mémoire virtuelle, système de fichier,
 262         pilote du disque et <i>firmware</i>).</li>
 263       </ul>
 264     </div>
 265     <h1>Stockage pour les SGBD</h1>
 266     <div class="sws-slide">
 267       <h1>Utilisation du disque par les SGBD</h1>
 268       <ul>
 269         <li>n-uplet (ou ligne) : enregistrement, séquence contiguë
 270         d'octets </li>
 271         <li>table = ensemble de lignes = fichier </li>
 272         <li>base = ensemble de tables = ensemble de fichiers</li>
 273       </ul>
 274       <p>Opérations de base sur les enregistrements</p>
 275       <ul><li>recherche d'un enregistrement (<tt>SELECT</tt>)</li>
 276         <li>ajout d'un enregistrement à une table
 277         (<tt>INSERT</tt>)</li>
 278         <li>mise à jour d'un enregistrement (<tt>UPDATE</tt>)</li>
 279         <li>suppression d'un enregistrement (<tt>DELETE</tt>)</li>
 280       </ul>
 281       <p>Les fichiers (i.e. les tables) sont <em>paginées</em>
 282       (découpées en pages)</p>
 283     </div>
 284     <div class="sws-slide">
 285       <h1>Représentation des enregistrements fixes</h1>
 286       <ul><li>Nombre fixe d'attributs (schéma de la table)
 287         </li>
 288         <li>Champs de taille fixe
 289           (<tt>VARCHAR[50]</tt>, <tt>INTEGER</tt> (32 bits), …)
 290         </li>
 291       </ul>
 292       <p>
 293       <table style="margin-left:20pt;" class="withborder">
 294         <tr><td>C<sub>1</sub></td> <td>C<sub>2</sub></td> <td>C<sub>3</sub></td> <td>C<sub>4</sub></td> <td>C<sub>5</sub></td></tr>
 295       </table>
 296       <table >
 297         <tr><td>B</td><td>&nbsp;L<sub>1</sub></td> <td> &nbsp;L<sub>2</sub></td> <td>&nbsp;L<sub>3</sub></td> <td>&nbsp;L<sub>4</sub></td> <td>&nbsp;L<sub>5</sub></td></tr>
 298       </table> <br/>
 299 Pour accéder au i<sup>ème</sup> champ d'un enregistrement en
 300       connaissant l'addresse de base <tt>B</tt>, on ajout à <tt>B</tt>
 301       les longueurs des champs 0, 1, …, i-1.<br/>
 302       adresse de C<sub>4</sub> = B + L<sub>1</sub> + L<sub>2</sub> + L<sub>3</sub><br/>
 303       </p>
 304     </div>
 305
 306     <div class="sws-slide">
 307       <h1>Représentation des enregistrements variables</h1>
 308       <ul><li>Nombre fixe d'attributs (schéma de la table)
 309         </li>
 310         <li>Champs de taille variables (<i>blobs</i> de texte)
 311         </li>
 312       </ul>
 313       <p>
 314       <table style="margin-left:20pt;" class="withborder">
 315         <tr><td>C<sub>1</sub></td> <td>$</td><td>C<sub>2</sub></td> <td>$</td> <td>C<sub>3</sub></td> <td>$</td><td>C<sub>4</sub></td><td>$</td> <td>C<sub>5</sub></td></tr>
 316       </table>
 317       On utilise un séparateur spécial entre les champs (scan linéaire
 318       pour arriver au i<sup>ème</sup> champ.<br/>
 319       <table style="margin-left:20pt;" class="withborder">
 320         <tr><td>L<sub>1</sub></td> <td>L<sub>2</sub></td> <td>L<sub>3</sub></td> <td>L<sub>4</sub></td> <td>L<sub>5</sub></td><td>C<sub>1</sub></td> <td>C<sub>2</sub></td> <td>C<sub>3</sub></td> <td>C<sub>4</sub></td> <td>C<sub>5</sub></td></tr>
 321       </table>
 322       On stocke les longueurs dans l'enregistrement
 323       </p>
 324     </div>
 325     <div class="sws-slide">
 326       <h1>Méta-données</h1>
 327       <p>Chaque enregistrement possède un en-tête stockant des données
 328       auxiliaires</p>
 329       <ul><li>taille totale de l'enregistrement (avec entête)</li>
 330         <li>pointeur vers le schéma de la table (pour déterminer les
 331         tailles des champs)</li>
 332         <li>date de dernière mise à jour</li>
 333         <li>information de gestion des valeurs nulles:
 334           <ul class="sws-pause">
 335             <li>Stockage d'une valeur spéciale (pas toujours
 336             possible)</li>
 337             <li>Stockage d'un bitmap (masque) : 26<sub>10</sub> =
 338             11010<sub>2</sub> : valeur nulle dans les champ 0 et 2</li>
 339           </ul>
 340         </li>
 341       </ul>
 342     </div>
 343     <div class="sws-slide">
 344       <h1>Stockage des enregistrements dans une page </h1>
 345       <p>Chaque enregistrement à une adresse (<i>rid</i> : record id)
 346       constituée de l'adresse de la page et de la position de
 347       l'enregistrement au sein de la page</p>
 348       <p>Lors d'une insertion, on doit trouver un emplacement libre
 349         dans la page</p>
 350       <p>Lors d'une suppression, on doit « effacer » un emplacement
 351       occupé et éventuellement compacter la page</p>
 352     </div>
 353     <div class="sws-slide">
 354       <h1>Stockage compact vs non compact (taille fixe)</h1>
 355       <p>
 356       <img style="width:40%" src="page_comp.svg"/>
 357       <img style="margin-left:10%;width:40%" src="page_ncomp.svg"/>
 358       </p>
 359     </div>
 360     <div class="sws-slide">
 361       <h1>Stockage compact (taille variable)</h1>
 362       <p>
 363       <img style="margin-left:10%;width:70%" src="page_var.svg"/>
 364       </p>
 365     </div>
 366   </body>
 367 </html>