.
[hacks/simpleWebSlides.git] / 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). Une
165       page fait <em>au moins un secteur</em>. De plus, une page ne
166       peut pas déborder sur <em>plus d'une piste</em>.
167       </p>
168       <p>On doit lire/écrire <s>au moins une page</s> même si on ne
169       veut lire/écrire qu'un octet</p>
170       <p>Exemple : on souhaite stocker 5 chaines de caractères de 200o
171       chacunes sur le disque</p>
172       <ul><li>Si placés sur blocs différents (arbitraires) : 5 pages
173       montées en mémoire, <tt>5 * temps de latence</tt></li>
174         <li>Si placés sur deux blocs consécutifs : <tt>temps de
175         latence + temps de transfert</tt> (on gagne un facteur 5)
176         </li></ul>
177     </div>
178     <div class="sws-slide">
179       <h1>Stratégies de placement</h1>
180       <p>On peut placer en priorité les données « reliées » (qu'on
181       veut utiliser en même temps):</p>
182       <ol>
183         <li>Dans le même bloc (T.A. à la deuxième donnée:
184         0)</li>
185         <li>Sur deux blocs contigus (T.A. à la deuxième donnée:
186         T. transfert)</li>
187         <li>Bloc à la même position sur un autre plateau (T.A. à la
188         deuxième donnée: T. transfert)</li>
189         <li>Sur la même piste (T.A. à la deuxième donnée:
190         T. rotation)</li>
191         <li>Sur des pistes proches</li>
192       </ol>
193     </div>
194     <div class="sws-slide">
195       <h1>Mise en place de la stratégies de placement</h1>
196       <p>Pour mettre en place les stratégies de placement il faut
197       connaître:</p>
198       <ul><li>La liste des blocs libres et occupés</li>
199         <li>La liste des blocs occupés par un « fichier » (i.e. qui
200         stocke des informations reliées à la même donnée logique)</li>
201         </ul>
202       <p>On ne travaille pas page à page : on alloue
203         un <em>buffer</em> de pages</p>
204       <p ><table class="withborder" style="margin-left:20%;">
205         <tr><td style="width:10pt;">
206         P1 </td><td style="width:10pt">P132 </td><td style="width:10pt">
207         P10 </td><td style="width:10pt">P99 </td></tr>
208         <tr><td style="width:10pt">
209         P2 </td><td style="width:10pt"> P1000  </td><td style="width:10pt">     P507 </td><td style="width:10pt">
210  </td></tr>
211         <tr><td style="width:10pt"> </td><td style="width:10pt"> </td><td style="width:10pt"> </td><td style="width:10pt">
212         </td></tr>
213         </table><br/>
214         On maintient pour chaque page : un <em>compteur
215         d'utilisation</em> et un <em>dirty-bit</em> qui indique si la
216         page a été modifiée (on doit donc l'écrire sur le disque à un
217         moment donné).<br/>
218         Lorsque le buffer est plein, il faut supprimer des pages (et
219         en monter d'autres en mémoire) suivant une stratégie:
220         LRU, MRU, Random, FIFO, LIFO, …
221       </p>
222     </div>
223     <div class="sws-slide">
224       <h1>Qui gère les accès disques bas-niveau, le buffer, … ?</h1>
225       <p>
226         <ul>
227           <li class="sws-pause">Dans le temps, le SGBD
228           directement </li>
229           <li class="sws-pause">De nos jours, le système
230           d'exploitation via ses systèmes de fichiers et gestion de la
231           mémoire virtuelle (<i>swap</i> ou fichier d'echange)</li>
232         </ul>
233       </p>
234       <p>Les systèmes d'exploitation ont <i>énormément</i> progressé
235       (les SGBD ne pouvaient pas reposer sur quelque chose d'aussi
236       primitif que FAT ou NTFS, mais les systèmes de fichier modernes
237       sont plus performant que le traitement natif du disque fais par
238       les SGBD, en particulier pour les SSD).<br/>
239         Pour prédire le bon comportement d'un SGBD il faut connaître
240       non seulement ce dernier, <s>mais aussi</s>, de manière
241       détaillée, les caractéristiques de l'OS et du système de
242       fichier.
243       </p>
244     </div>
245     <div class="sws-slide">
246       <h1>Un mot sur les SSD</h1>
247       <p><i>Solid State Disk</i> : « disque » dur composé entièrement
248       de mémoire flash. Avantages:</p>
249       <ul style="sws-pause">
250         <li>Pas de temps de recherche et de rotation, uniquement temps
251         de transfert. Accès arbitraires aussi rapides que les
252         séquentiels</li>
253         <li>Consomation électrique moindre, poid moindre, pas de
254         pièce mobile (resistance aux chocs)</li>
255       </ul>
256       <ul><li>Couteux</li>
257         <li>Écriture <s>très</s> complexe (écrire dans une cellule
258         impose de l'effacer avant, nombre de cycle d'effaçage limité,
259         etc)
260         </li>
261         <li>Nécessite une coopération à tous les niveaux, seul le
262         système d'exploitation peut bien le gérer (bibliothèque
263         système, gestion de la mémoire virtuelle, système de fichier,
264         pilote du disque et <i>firmware</i>).</li>
265       </ul>
266     </div>
267     <h1>Stockage pour les SGBD</h1>
268     <div class="sws-slide">
269       <h1>Utilisation du disque par les SGBD</h1>
270       <ul>
271         <li>n-uplet (ou ligne) : enregistrement, séquence contiguë
272         d'octets </li>
273         <li>table = ensemble de lignes = fichier </li>
274         <li>base = ensemble de tables = ensemble de fichiers</li>
275       </ul>
276       <p>Opérations de base sur les enregistrements</p>
277       <ul><li>recherche d'un enregistrement (<tt>SELECT</tt>)</li>
278         <li>ajout d'un enregistrement à une table
279         (<tt>INSERT</tt>)</li>
280         <li>mise à jour d'un enregistrement (<tt>UPDATE</tt>)</li>
281         <li>suppression d'un enregistrement (<tt>DELETE</tt>)</li>
282       </ul>
283       <p>Les fichiers (i.e. les tables) sont <em>paginées</em>
284       (découpées en pages)</p>
285     </div>
286     <div class="sws-slide">
287       <h1>Représentation des enregistrements fixes</h1>
288       <ul><li>Nombre fixe d'attributs (schéma de la table)
289         </li>
290         <li>Champs de taille fixe
291           (<tt>VARCHAR[50]</tt>, <tt>INTEGER</tt> (32 bits), …)
292         </li>
293       </ul>
294       <p>
295       <table style="margin-left:20pt;" class="withborder">
296         <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>
297       </table>
298       <table >
299         <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>
300       </table> <br/>
301 Pour accéder au i<sup>ème</sup> champ d'un enregistrement en
302       connaissant l'addresse de base <tt>B</tt>, on ajout à <tt>B</tt>
303       les longueurs des champs 0, 1, …, i-1.<br/>
304       adresse de C<sub>4</sub> = B + L<sub>1</sub> + L<sub>2</sub> + L<sub>3</sub><br/>
305       </p>
306     </div>
307
308     <div class="sws-slide">
309       <h1>Représentation des enregistrements variables</h1>
310       <ul><li>Nombre fixe d'attributs (schéma de la table)
311         </li>
312         <li>Champs de taille variables (<i>blobs</i> de texte)
313         </li>
314       </ul>
315       <p>
316       <table style="margin-left:20pt;" class="withborder">
317         <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>
318       </table>
319       On utilise un séparateur spécial entre les champs (scan linéaire
320       pour arriver au i<sup>ème</sup> champ.<br/>
321       <table style="margin-left:20pt;" class="withborder">
322         <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>
323       </table>
324       On stocke les longueurs dans l'enregistrement
325       </p>
326     </div>
327     <div class="sws-slide">
328       <h1>Méta-données</h1>
329       <p>Chaque enregistrement possède un en-tête stockant des données
330       auxiliaires</p>
331       <ul><li>taille totale de l'enregistrement (avec entête)</li>
332         <li>pointeur vers le schéma de la table (pour déterminer les
333         tailles des champs)</li>
334         <li>date de dernière mise à jour</li>
335         <li>information de gestion des valeurs nulles:
336           <ul class="sws-pause">
337             <li>Stockage d'une valeur spéciale (pas toujours
338             possible)</li>
339             <li>Stockage d'un bitmap (masque) : 26<sub>10</sub> =
340             11010<sub>2</sub> : valeur nulle dans les champ 0 et 2</li>
341           </ul>
342         </li>
343       </ul>
344     </div>
345     <div class="sws-slide">
346       <h1>Stockage des enregistrements dans une page </h1>
347       <p>Chaque enregistrement à une adresse (<i>rid</i> : record id)
348       constituée de l'adresse de la page et de la position de
349       l'enregistrement au sein de la page</p>
350       <p>Lors d'une insertion, on doit trouver un emplacement libre
351         dans la page</p>
352       <p>Lors d'une suppression, on doit « effacer » un emplacement
353       occupé et éventuellement compacter la page</p>
354     </div>
355     <div class="sws-slide">
356       <h1>Stockage compact vs non compact (taille fixe)</h1>
357       <p>
358       <img style="width:40%" src="page_comp.svg"/>
359       <img style="margin-left:10%;width:40%" src="page_ncomp.svg"/>
360       </p>
361     </div>
362     <div class="sws-slide">
363       <h1>Stockage compact (taille variable)</h1>
364       <p>
365       <img style="margin-left:10%;width:70%" src="page_var.svg"/>
366       </p>
367     </div>
368   </body>
369 </html>