Le bloc logique est la plus petite unité d'allocation visible d'un système de fichiers à travers les appels systèmes. Cela signifie que le stockage d'un fichier dont la taille en octets est inférieure à la taille d'un bloc logique occupera sur disque la taille du bloc logique.

De même, si la taille d'un fichier n'est pas divisible de façon entière par la taille du bloc logique (ie. taille_fichier modulo taille_bloc != 0), le système de fichiers allouera un nouveau bloc qui ne sera pas rempli entièrement, gaspillant ainsi de l'espace disque. Ce gaspillage d'espace disque est ce que l'on appelle la fragmentation interne. Remarquons que plus la taille du bloc logique est importante, plus importante sera la fragmentation interne.

La fragmentation externe d'un fichier est le fait d'avoir les blocs constituant le fichier répartis de façon non contiguë sur tout le disque, réduisant ainsi les performances d'accès à ce fichier, du fait de l'augmentation des mouvements des têtes de lecture du disque nécessaire à l'accès à ce fichier.

Les extents sont des ensembles de blocs logiques contigus, utilisés dans divers systèmes de fichiers voire même dans certains SGBD. Le descripteur d'un extent ressemble à début, taille, offset, où début est l'adresse du premier bloc de l'extent, taille est la taille en nombre de blocs, offset est l'offset dans le fichier où se situe l'extent.

Extent

L'utilisation des extents améliore l'utilisation de l'espace, puisque tous les blocs d'un extent sont contigus. Cette amélioration amènera de meilleures performances en lecture séquentielle, car moins de mouvements de tête de lecture seront nécessaires. Remarquons ainsi que l'utilisation des extents réduit le problème de la fragmentation externe, puisque les blocs sont rassemblés. Mais l'utilisation d'extent n'est pas toujours la panacée. Par exemple, si nos applications demandent des extents d'une taille proche de celle des blocs logiques, tous les bénéfices seront perdus, puisque ces extents ressembleront à autant de blocs logiques.

Pour clore le chapitre amélioration des performances, l'utilisation d'extents améliore aussi les transferts simultanés de plusieurs blocs et améliore les taux de réussite des mémoires tampons des disques durs.

Arbre B+^[2] : les clés des nœuds sont ordonnées dans l'arbre, ce qui améliore les temps de recherche, recherche qui n'est plus séquentielle. Les feuilles sont chaînées entre elles.

1. Pour localiser le fichier resolv.conf, nous commençons à la racine de l'arbre, lisons séquentiellement, et trouvons qu'il n'y a pas de clé supérieure à celle de « resolv.conf », donc nous suivons le dernier pointeur (en rouge).

2. Nous sommes redirigés sur un autre nœud de l'arbre. On fait de même qu'avant, on lit les clés jusqu'à « securetty », qui est supérieure à « resolv.conf ». On suit donc le lien associé (en bleu).

3. Nous arrivons ainsi à une feuille de l'arbre. Il est temps de lire séquentiellement par ordre ascendant les clés présentes. Nous trouvons enfin la clé désirée, nous permettant d'utiliser le pointeur associé vers les données du fichier resolv.conf

La structure de données de type arbre B+ est depuis longtemps utilisée pour l'indexation de bases de données.

Cette structure apporte aux SGBD une manière rapide et stable dans les performances pour accéder à leurs enregistrements. Le terme arbre B+ vient de « arbre balancé », équilibré en français. Le signe « + » signifie que la structure arbre B+ est une version modifiée de l'arbre B. ^[3] original, modification qui consiste en le maintien de pointeurs entre les différentes feuilles de l'arbre, ce afin de ne pas pénaliser les accès séquentiels de feuille en feuille. Puisque les arbres B et B+ sont issus des bases de données, nous utiliserons des analogies avec celles-ci pour les expliquer.

Les arbres B+ sont constitués de deux types d'éléments : les nœuds et les feuilles. Les deux sont une paire (clé, pointeur), ordonnées de façon ascendante par les valeurs de clés, avec un pointeur final qui n'a pas de clé correspondante. Alors que les pointeurs des nœuds pointent sur d'autres nœuds ou feuilles, les pointeurs des feuilles pointent directement sur l'information utilisable. Chaque paire (clé, pointeur) organise l'information au sein de l'arbre B. En base de données, chaque enregistrement possède un champ-clé, un champ qui sert à distinguer un enregistrement particulier des tous les autres enregistrements de même type. Les B-arbres utilisent ces champs-clés pour indexer les enregistrements d'une base de données pour améliorer les temps d'accès à l'information.

Ainsi que nous l'avons vu, un nœud (clé, pointeur) est utilisé pour pointer sur un autre nœud ou sur une feuille. Dans les deux cas, la clé associée au pointeur aura une valeur supérieure à toutes les valeurs de clés stockées dans les nœuds cibles. De plus, les enregistrements ayant des valeurs de clés identiques devront être adressés par la paire suivante dans le nœud. Ce point est la principale raison de l'existence du pointeur de fin qui n'a aucune valeur de clé correspondante. Notons qu'à partir du moment où une clé est utilisée dans une paire, il doit exister un autre pointeur pour atteindre les enregistrements ayant cette même valeur de clé. Ce pointeur de fin est utilisé dans les feuilles pour pointer sur la feuille suivante. On peut ainsi passer les contenus en revue aussi de façon séquentielle.

Les arbres B+ doivent être équilibrés. Cela signifie que la longueur du chemin nous menant de la racine de l'arbre à chacune des feuilles doit toujours être la même. En plus, les feuilles doivent contenir un nombre minimal de paires pour exister. Quand le contenu d'une feuille tombe sous le seuil, les paires seront intégrées à une autre feuille.

Pour rechercher un enregistrement particulier, nous procéderons ainsi :

Supposons que nous recherchons un enregistrement ayant une clé K. Nous partons du nœud racine, et passons en revue séquentiellement les clés qu'il contient, jusqu'à ce que nous trouvions une clé de valeur supérieure à celle de K. Nous passons ensuite au nœud (ou feuille, nous ne savons pas encore) pointé par le pointeur associé à la clé. A ce stade, nous répétons la même opération si nous ne sommes pas arrivés à une feuille. Arrivé sur une feuille, nous criblons séquentiellement les paires contenues jusqu'à la valeur K. Moins de blocs sont nécessaires d'être lus pour arriver au bloc désiré, ce qui qualifie cette technique comme étant de moindre complexité qu'une recherche purement séquentielle, où dans le plus mauvais cas, nous devons lire tous les enregistrements pour trouver celui que nous recherchons.

C'est le nom du système de fichiers utilisé au début par SCO, System V^[4], et d'autres Unix. Le noyau Linux inclut le support optionnel d'UFS. La plupart des Unix continuent à utiliser UFS, avec néanmoins quelques améliorations mineures.

VFS est la couche logicielle du noyau^[5] qui fournit une interface de programmation applicative « API en anglais » unifiée pour accéder aux services des systèmes de fichiers, quel que soit le système de fichier particulier utilisé derrière. Tous les pilotes de systèmes de fichiers (VFAT, Ext2FS, JFS) doivent ainsi fournir un certain nombre de routines à la couche VFS pour être utilisables sous Linux. VFS est la couche qui permet aux applications de comprendre et d'utiliser tant de systèmes de fichiers différents, même les systèmes de fichiers commerciaux.

Je pars du principe que chacun sait ce qu'est un tampon d'écriture : un tampon alloué en mémoire qui permet d'accélérer les entrées / sorties. Ce type de tampon est couramment utilisé par les systèmes de fichiers (le cache/tampon disque), et les SGBD pour augmenter les performances. Un problème apparaît si le système plante avant que ces tampons ne soient écrits sur disque, ce qui va provoquer un comportement incohérent du système après son redémarrage. Imaginons qu'un fichier soit effacé en mémoire, mais pas sur disque. C'est à cause de ce problème que les SGBD et les systèmes de fichiers ont les moyens de revenir à une situation cohérente. Bien que les SGBD aient cette capacité depuis des années, les systèmes de fichiers dérivés de UFS ont tendance à voir le temps de correction des erreurs augmenter avec l'augmentation de la taille du système de fichiers. L'outil fsck pour Ext2FS doit parcourir toute la partition de disque pour pouvoir revenir à une situation cohérente. Cette opération consommatrice de temps inflige souvent une perte de temps d'exploitation des gros serveurs ayant en ligne plusieurs centaines de giga-octets, voire plusieurs tera-octets. Ceci est la principale raison de voir les systèmes de fichiers hériter des technologies de reprise sur incident des SGBD, et donc l'apparition des systèmes de fichiers journalisés.

Les SGBD « sérieux » utilisent la notion de transaction. Une transaction est un ensemble d'opérations qui satisfont à plusieurs propriétés. Ces propriétés sont surnommées ACID pour Atomicité, Cohérence, Isolation, et Durabilité. La propriété la plus importante pour notre explication est l'atomicité. Elle implique que toutes les opérations faisant partie d'une transaction sont soit intègres et terminées, soit en cas d'erreur ou d'annulation, ne produisent aucun changement. Cette fonctionnalité, associée à l'isolation, fait que les transactions peuvent être assimilées à des opérations atomiques qui ne peuvent être exécutées partiellement. Ces propriétés des transactions sont utilisées en bases de données du fait des problèmes rencontrés pour maintenir la cohérence des données tout en exploitant la simultanéité. Pour ce faire, les SGBD journalisent toutes les opérations simples (en écriture disque synchrone) d'une transaction dans un fichier dit journal. En fait, les opérations ne sont pas les seules journalisées : les arguments de ces opérations le sont aussi avant l'exécution de la transaction. A l'issue de chaque transaction, il doit y avoir une opération « commit », qui lance l'écriture des données sur disque. Ainsi, si le système plante, nous pouvons remonter dans l'historique du journal jusqu'à la première opération « commit », et ainsi écrire tous les contenus des précédentes transactions sur disque.

Les systèmes de fichiers journalisés utilisent cette même technique pour journaliser les opérations, autorisant ainsi une reprise d'activité dans un laps de temps très court.

Une différence majeure entre SGBD et système de fichier journalisé est que les SGBD journalisent et les données utilisateurs, et les données de contrôle, alors que les systèmes de fichiers ne journalisent que les meta-données. Les meta-données sont les structures de contrôle d'un système de fichier : inodes, tables d'allocation de l'espace libre, tables d'inodes, etc...

La plupart des nouveaux systèmes de fichiers ont vu la taille de certains de leurs champs internes s'étendre, afin de passer outre les limitations des systèmes actuels. Les nouvelles limites pour ces systèmes sont :

Supposons que nous venons de créer un nouveau fichier, et avons écrit deux octets au début de ce même fichier. Rien de particulier à cela. Qu'arrivera-t-il si maintenant nous tentons d'écrire à l'offset 10000 de ce fichier ? Le système de fichier devra donc évaluer le nombre de blocs nécessaires pour combler le trou entre l'offset 2 et l'offset 10000. Cela pourrait prendre un moment. Maintenant, pourquoi le système de fichier doit-il allouer ces blocs, alors que nous n'avons pas exprimé d'intérêt à leur égard ? La réponse à cette question est le support des fichiers à trou, support intégré aux systèmes de fichiers de nouvelle génération.

Le support des fichiers à trous est étroitement lié à la technique d'adressage des extents regroupant les blocs d'un fichier. Le champ « offset dans le fichier » de l'extent sera utilisé à cette fin. Ainsi, quand le système doit chercher des blocs d'espace libre pour combler le trou ouvert dans une situation comme celle décrite ci-dessus, il alloue un nouvel extent qui aura comme offset l'offset dans le fichier désiré. Ensuite, quand une application lira les octets correspondant au trou, elle se verra retourner une valeur nulle, puisque aucune information n'est présente. Enfin, le trou pourra être comblé par les applications qui voudront y écrire.

Quand nous avons parlé de fragmentation interne et de performance, nous avons signalé que les administrateurs système ont souvent le choix entre les performances et la perte d'espace utile. Si nous regardons le premier tableau, nous verrons que les systèmes de fichiers actuels peuvent gérer des blocs de tailles pouvant atteindre 64 Ko. Cette taille de bloc, voire même une taille inférieure, induit des pertes importantes d'espace utile, pertes dues à la fragmentation interne. Afin de rendre faisable l'utilisation de blocs de grande taille, ReiserFS met en application une technique qui résout le problème.

Comme nous l'avons dit plus haut, ReiserFS utilise un arbre B*^[8] pour organiser les objets du système de fichiers. Ces objets sont les structures utilisées pour gérer les informations sur les fichiers, par exemple les dates d'accès, permissions, etc... En d'autres termes, les informations contenues habituellement dans un inode, les répertoires et les données des fichiers. ReiserFS appelle respectivement ces objets éléments de statut, éléments de répertoire, et éléments directs / indirects. Les éléments indirects sont une série de pointeurs vers des nœuds non formatés. Les nœuds non formatés sont des blocs logiques sans format particulier, utilisés pour stocker les données des fichiers. Les éléments directs contiennent directement les données des fichiers. En outre, ces éléments sont de taille variable et sont enregistrés dans les feuilles de l'arbre, parfois avec d'autres au cas où il y aurait assez d'espace dans la feuille. C'est pourquoi nous avons dit plus haut que l'information à propos d'un fichier est stockée au plus près des données des fichiers, puisque le système de fichiers essaye toujours de garder ensemble les éléments de statut et les éléments directs et indirects d'un même fichier. Remarquons enfin que, comparées aux éléments directs, les données du fichier pointées par les éléments indirects ne sont pas enregistrées dans l'arbre. Cette gestion spéciale des éléments directs est due au support des fichiers de petite taille.

Les éléments directs sont destinés à enregistrer les données de fichiers de petite taille, et même les queues^[9] des fichiers. Par conséquent, plusieurs queues de fichiers peuvent être stockées dans la même feuille, réduisant ainsi le gaspillage d'espace dû à la fragmentation interne. Le problème corrolaire à cette technique est l'éventuelle augmentation de la fragmentation externe, puisque les données des fichiers s'éloignent des données de queues. D'ailleurs, la tâche de compactage des queues prend du temps et amène à une diminution des performances. C'est une conséquence des décalages de mémoire nécessaires quand quelqu'un ajoute des données à un fichier. Quoi qu'il en soit, l'utilisation de la technique de compactage des queues peut être interdite en fonction de ce que veut faire l'administrateur. Une fois encore, comme auparavant, c'est encore au choix de l'administrateur.

Un des problèmes principaux des systèmes de fichiers du type de UFS est leur restriction à un nombre fixe d'inodes. Ces inodes contiennent les informations liées à chaque objet du système de fichiers. Ainsi, ce nombre fixe d'inode restreint le nombre d'objets gérables sur un système de fichiers. Au cas où tous les inodes du système de fichiers seraient utilisés, nous devons sauvegarder la partition, puis recréer le système de fichiers avec un plus grand nombre d'inodes. La raison de la fixité de ce nombre est que UFS emploie des structures de  taille fixe pour gérer l'état des inodes, de la même façon que pour les blocs d'espace libre.

En outre, UFS alloue l'emplacement pour les inodes à des adresses fixées à l'avance. Cela évite de gérer d'autres pointeurs pour chercher et utiliser ces inodes.

Le problème pour les administrateurs est de savoir combien d'objets auront à gérer leur système de fichier. La politique « créer un système de fichier avec le maximum d'inodes possible » n'est pas toujours la meilleure, puisque l'espace pour les inodes est réservé, et ne peut être utilisé pour autre chose. Cela gaspillerait beaucoup d'espace.

Pour surmonter ce problème est apparue l'allocation dynamique d'inode. Cela évite aux administrateurs système de devoir deviner le nombre maximal d'objets au moment de la création du système de fichier. Mais cette utilisation de structures dynamiques apporte d'autres problèmes : allocation et adressage des inodes dans l'espace des blocs logiques, etc...

Les systèmes de fichiers vus ici utilisent des arbres B+ pour organiser les inodes. Mieux, JFS utilise des extents d'inodes qui forment les feuilles de l'arbre et qui peuvent contenir jusque 32 inodes. Il existe aussi d'autres structures permettant d'allouer les inodes auprès des autres objets du système de fichier. En conséquence, l'utilisation de techniques d'allocation dynamique d'inodes est complexe et prend du temps, mais aide à dépasser les limites des anciens systèmes de fichiers.

L'auteur aimerait remercier Stephen C. Tweedie, Dave Kleikamp, Steve Best, Hans Reiser, les assidus des listes de distribution de JFS et ReiserFS pour les discussions fructueuses et leurs réponses.