Linux Gazette n°55
PrécédentSuivant

Autres améliorations

Il existe d'autres limitations sur les systèmes de fichiers comme UFS. Par exemple, l'incapacité de gérer les fichiers à trous (sparse files), ou encore le problème du nombre fixe d'inode sur un système de fichiers.

Support des fichiers à trous

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écessaire 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.

La solution à la fragmentation interne de ReiserFS

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*[1] 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 noeuds non formatés. Les noeuds 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[2] 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 que veut faire l'administrateur. Une fois encore, comme auparavant, c'est encore au choix de l'administrateur.

Allocation dynamique d'inode

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.

Tableau 3.

TechniquesAllocation dynamique d'inodesSuivi dynamique des inodesSupport des fichiers à trous
XFSOUIArbre B+OUI
JFSOUIArbre B+ et extents d'inodesOUI
ReiserFSOUIArbre B* principal[a]OUI[b]
Ext3FSNDNONND
Remarques :
a. car ainsi que nous l'avons expliqué dans la section sur la solution de ReiserFS à la fragmentation interne, ReiserFS se sert des éléments d'état pour stocker l'information à propos des fichiers. Le nombre de liens, les identifiants de propriétaire et de groupe, le type de fichier, les permissions, la taille du fichier, etc..., sont toutes stockées l'élément d'état correspondant au fichier. Cet élément d'état remplace en fonctionnalité l'inode, sauf pour ce qui est de pointer sur les blocs de données du fichier. De plus, les éléments de ReiserFS sont créés dynamiquement et organisés dans l'arbre B* principal, ce qui amène un équivalent d'allocation dynamique d'inode. Enfin, chaque élément du système de fichier a son propre champ de clé, qui sert à le localiser dans l'arbre B*. Cette clé a un certain nombre de bits à la fin du champ, bits dédiés à l'identification du type d'élément, et qui nous permet de savoir si l'élément est un élément de statut, direct, indirect, etc... Nous pouvons ainsi dire que l'organisation des inodes se fait par l'utilisation de l'arbre B*.
b. Actuellement, le support des fichiers à trous de ReiserFS n'est pas aussi rapide que prévu. Ce problème devrait être corrigé dans la version 4 de ReiserFS.

Notes

[1]

NdT : un descendant des arbres B et B+

[2]

NdT : du terme anglais « tail », qui sont en fait les données en fin du fichier qui ne remplissent pas un bloc entier. Voir à ce sujet l'option de montage notail de ReiserFS, utilisée par exemple avec LILO pour démarrer Linux grâce à une simple liste de blocs.


PrécédentSommaireSuivant
Problèmes connus, comment répondre au besoin d'évolutivité Références