| Linux Gazette n°55 | ||
|---|---|---|
| Précédent | Suivant | |
UFS et Ext2FS furent conçus alors que les capacités des disques durs et autres media de stockage étaient de taille moins importante que maintenant. La croissance rapide des media de stockage induirent des tailles de fichiers, de répertoires, et de partitions plus importantes, causant ainsi de plus en plus de problèmes aux systèmes de fichiers. Ces problèmes découlent des structures internes sous-tendant les systèmes de fichiers. Enfin, ces structures étaient adéquates pour les tailles moyennes observées des fichiers et répertoires, mais se sont avérées inefficaces pour les besoins actuels.
Il existe deux problèmes majeurs avec les anciennes structures :
Elles sont incapables de gérer les nouvelles capacités de stockage : ainsi que nous l'avons dit, les anciens systèmes de fichiers étaient conçus pour certains paramètres de taille de fichiers, répertoires et partitions. Les structures des systèmes de fichiers ont un nombre fixé de bits pour stocker la taille d'un fichier, pour stocker l'adresse d'un bloc, etc... En conséquence de quoi, les tailles de fichier, de répertoire, et de partition et le nombre de fichiers dans un répertoire sont eux aussi limités. Il manque ainsi aux anciennes structures la capacité de gérer les tailles de certains objets.
Elles sont peu adaptéesz à la gestion des nouvelles capacités de stockage : bien qu'elles puissent parfois gérer certaines tailles d'objets, elles sont parfois incapables de les gérer pour des raisons de performance. La principale raison étant que certaines structures se comportent correctement avec les anciennes volumétries, mais induisent des pertes parfois sévères de performances avec les nouvelles.
Les systèmes de fichiers de nouvelle génération ont été conçus pour pallier ces problèmes, gardant à l'esprit le problème de l'évolutivité. Un certain nombre de nouvelles structures de données et d'algorithmes ont ainsi été intégrés à ces nouveaux systèmes de fichiers. Nous allons maintenant expliquer plus avant les problèmes décrits plus haut et les techniques employées pour les surmonter.
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 :
Tableau 1. Limites des systèmes de fichiers
| Taille maximale du système de fichiers | Taille de blocs | Taille maximale de fichier | |
| XFS | 18 000 peta-octets (Po) | 512 octets à 64 Ko | 9 000 Po |
| JFS | Blocs de 512 octets : 4 Po | 512, 1024, 2048 et 4096 octets | Blocs de 512 octets : 512 To |
| Blocs de 4 Ko : 32 Po | Blocs de 4 Ko : 4 Po | ||
| ReiserFS | 4 milliards de blocs, soit 16 tera-octets | 64 Ko maximum, fixé actuellement à 4 Ko | 4 Go en v3.5 |
| 2^10 Po en v3.6 | |||
| Ext3FS | 4 To | De 1 à 4 Ko | 2 Go |
Actuellement, la taille maximale d'un périphérique en mode bloc limite la taille d'un système de fichiers à 2 To, la couche VFS induisant une autre limite : la taille d'un fichier inférieure à 2 Go. La bonne nouvelle est que nous avons maintenant des systèmes de fichiers capable d'évoluer en capacité, et qu'à la sortie du noyau 2.4, je suis sûr que ces limites seront étendues. Notons que XFS et JFS sont des portages de systèmes de fichiers commerciaux ; ils furent développés pour d'autres systèmes d'exploitation où ces limites n'existaient pas.
La plupart des systèmes de fichiers maintiennent des structures ont sont suivis les blocs libres. Ces structures sont souvent des listes chaînées, contenant les adresses de tous les blocs libres. Ainsi, le système de fichiers est capable de satisfaire les besoins d'allocation de stockage des applications. UFS et Ext2FS utilisent ce que l'on appelle une bitmap[1] pour le suivi de ces blocs libres. Cette carte est un est un tableau de bits, où chaque bit est associé à un bloc dans le système de fichier de la partition. L'état de l'allocation de chaque bloc est reflété dans la carte, où un «1» représente un bloc logique alloué, et un «0» un bloc non-alloué, libre. Le principal problème avec ce genre de structure est que plus la taille d'un système de fichiers augmente, plus la taille de la carte augmente, puisque chaque bloc doit avoir son bit correspondant dans la carte. Et tant que nous utiliserons un algorithme de recherche séquentielle des blocs libres, nous constaterons une perte de performance puisque le temps de recherche augmentera de façon linéaire (complexité en O(n), où n est la taille de la carte). Notons que l'approche carte n'est pas si mauvaise quand la taille du système de fichiers est raisonnable, mais plus la taille augmentera, moins bien la structure se comportera.
La solution fournie par les systèmes de fichiers de nouvelle génération est l'utilisation d'extents conjuguée à une organisation en arbre B+. L'approche extent est intéressante car elle permet de localiser plusieurs blocs disponibles en même temps. De plus, ils permettent aussi de réduire la taille de la structure de gestion, puisque plusieurs blocs sont gérés avec moins d'information. Par conséquent, un bit pour chaque bloc n'est plus nécessaire. En outre, avec l'utilisation des extents, la taille de la structure de gestions des blocs libre ne dépend plus de la taille du système de fichiers (la taille de structure dépend du nombre d'extents gérés). Néanmoins, si le système de fichiers est si fragmenté qu'il existe un extent pour chaque bloc libre, la structure de gestion serait plus grande que pour l'approche à bitmap. Notez que les performances devraient être sensiblement augmentées si notre structure gérait uniquement les blocs libres, puisque moins d'éléments auraient à être visités. En outre, avec l'utilisation d'extents, même s'ils sont gérés en liste et que des algorithmes séquentiels de balayage soient utilisés, les performances en seraient quand même améliorées puisque la structure englobe plusieurs blocs dans un extent, réduisant ainsi le temps de localisation d'un certain nombre de blocs libres.
La seconde approche pour surmonter le problème de gestion des blocs libres est l'utilisation de structures complexes qui amènent à l'utilisation d'algorithmes de balayage de moindre -complexité. Nous tous savons qu'il y a de meilleures voies d'organiser un ensemble d'éléments devant être localisés que l'utilisation des listes chaînées avec des algorithmes de balayage séquentiels. Les arbres B+ sont utilisés puisqu'ils peuvent localiser des objets rapidement. Ainsi, les blocs libres sont organisés en arbres B+ au lieu de listes, afin de tirer profit des algorithmes de recherche rapide. Quand plusieurs blocs libres sont demandés par les applications, le système de fichiers traverse «l'arbre de gestion des blocs libres», afin de localiser l'espace libre demandé. Il existe en outre l'approche «Arbre B+ d'extents», où des extents et non des blocs sont organisés dans l'arbre. Cette approche rend différentes techniques d'indexation possibles. L'indexation par taille d'extent, mais également par la position des extents, sont des techniques mises en application qui rendent le système de fichiers capable de localiser rapidement plusieurs blocs libres, que ce soit par leur taille ou par leur emplacement.
Tous les systèmes de fichiers utilisent un objet spécial appelé répertoire. Les répertoires, vus du système de fichiers, est un ensemble d'entrées de répertoire. Ces entrées sont des paires (numéro d'inode, nom de fichier), où le «numéro d'inode» est le numéro d'inode (structure interne du système de fichiers) utilisé pour gérer les informations relatives aux fichiers. Quand une application veut rechercher un certain fichier dans un répertoire, par son nom de fichier, la «structure d'entrées de répertoire» doit être balayée. Les anciens systèmes de fichiers ont organisé les entrées de répertoire par des listes chaînées, utilisant alors des algorithmes de recherche séquentiels. Par conséquent, avec des répertoires de grande taille, référençant des milliers de fichiers et d'autres répertoires, les performances se réduisent d'autant. Ce problème, comme celui décrit pour les blocs d'espace libre, est étroitement lié à la structure utilisée. Les systèmes de fichiers de nouvelle génération ont ainsi besoin de structures de données et d'algorithmes plus performants pour localiser rapidement un fichier dans un répertoire.
Solution employée : les systèmes de fichiers passés en revue ici utilisent les arbres B+ pour organiser les entrées de répertoire, ce qui améliore les temps de recherche. Dans ces systèmes de fichiers, les entrées de chaque répertoire sont indexées par le nom de fichier.
Ainsi, quand un fichier d'un répertoire donné est demandé, l'arbre B+ de ce répertoire est traversé pour localiser rapidement l'inode correspondant. L'utilisation des arbres B+ est liée à chaque système de fichiers. Il existe en effet des systèmes de fichiers qui gèrent un arbre par répertoire, alors que d'autres gèrent un arbre par arborescence de fichiers.
Quelques anciens systèmes de fichiers ont été conçus avec une certaine idée des conditions d'utilisation. Ext2fs et UFS ont été conçus en partant du principe que les systèmes de fichiers contiendraient essentiellement de petits fichiers. C'est ce qui expliquent ce à quoi ressemblent les inodes de Ext2FS ou UFS. Pour ceux qui ne connaissent pas encore la notion d'inode, nous allons l'expliquer brièvement.
Un inode est la structure employée par UFS et Ext2FS pour gérer les informations relatives aux fichiers. Sont gérés dans l'inode les permissions sur le fichier, son type, le nombre de liens[2], et les pointeurs sur les blocs du système de fichiers.
Un inode peut contenir des pointeurs directs qui sont les adresses logiques des blocs logiques du système de fichiers utilisés pour stocker le contenu du fichier, mais il peut aussi contenir des pointeurs indirects simples, voire doubles ou même triples. Les pointeurs indirects contiennent l'adresse de blocs logiques où sont d'autres pointeurs qui eux donnent l'adresses des blocs du fichier. Les indirections doubles pointent sur des blocs contenant des indirections simples. De même, les indirections triples pointent sur des indirections doubles. Le problème avec cette technique d'adressage est que si la taille du fichier croit, indirections simples, doubles et même triples sont utilisées.
Notons que l'utilisation de pointeurs indirects mène à l'augmentation du nombre d'accès disques, car un plus grand nombre de blocs doit être lu pour trouver le bloc demandé. Cela mène à une augmentation du temps de recherche en corrélation avec l'augmentation de la taille des fichiers. Vous pourriez vous demander pourquoi les créateurs d'Ext2FS n'ont pas uniquement utilisé les pointeurs indirects simples, démontrés plus rapides ?
La principale raison en est que les inodes ont une taille fixe, et que l'utilisation de pointeurs simples uniquement amènerait à utiliser des inodes de plus grande taille, pour stocker tous les pointeurs directs utilisables, ce qui gaspillerait inutilement de l'espace disque lorsque l'on stocke de petits fichiers.
Inode (Ext2FS) : les fichiers de plus grande taille nécessitent plus d'accès disque, car utilisant des indirections simples, voire doubles et même triples pour accéder aux données.
Solution employée : les nouveaux systèmes de fichiers doivent alors continuer à utiliser l'espace efficacement, et fournissent de meilleures techniques d'adressage pour des fichiers de plus grande taille. La principale différence avec les anciens systèmes de fichiers est, une fois de plus, l'utilisation d'arbres B+. Les systèmes de fichiers que nous étudions utilisent les arbres B+ pour gérer les blocs des fichiers. Les blocs sont classés par leur adresse (offset) dans le fichier; puis, quand une certaine adresse dans le fichier est demandée les sous-routines du système de fichiers parcourent l'arbre des blocs pour localiser le bloc requis. Ces techniques employées sont aussi propres à chaque système de fichier.
Afin de réduire au minimum l'utilisation des pointeurs indirects, nous pourrions penser à utiliser de plus grands blocs logiques. Ceci mènerait à un ratio d'information sur nombre de pointeurs plus élevé, ayant pour résultat une utilisation moindre des indirections. Mais, ces blocs logiques plus grands augmentant la fragmentation interne, d'autres techniques sont utilisées. L'utilisation des extents rassemblant un ensemble de plusieurs blocs logiques est une de ces techniques.
L'utilisation des extents en lieu et place des pointeurs sur blocs causerait le même effet que l'augmentation de la taille des blocs, puisque le taux information sur nombre de pointeurs augmente. Certains des systèmes de fichiers passés en revue utilisent des extents pour surmonter le problème de l'adressage dans les fichiers de grande taille.
D'ailleurs, des extents peuvent être indexés dans un arbre B+ par leur adresse à l'intérieur du fichier, améliorant ainsi les temps de lecture. Les nouveaux inodes maintiennent ainsi, jusqu'à un certain point, quelques pointeurs directs sur les extents, et, dans le cas où le fichier aurait besoin de plus d'extents, ceux-ci seront organisés dans un arbre B+. Pour maintenir un bon niveau de performance lors de l'accès aux fichiers de petite taille, les systèmes de fichiers de nouvelle génération stockent les données directement dans l'inode. Ainsi, chaque accès à l'inode permettra un accès immédiat aux données. Cette technique est particulièrement utile pour les liens symboliques où l'information stockée est infime.
Tableau 2. Capacités et particularités des systèmes de fichiers étudiés
| Techniques / Système de fichiers | Gestion des blocs libres | Utilisation d'extents pour l'espace libre | B-arbres pour les entrées de répertoire | B-arbres pour adresser les blocs des fichiers | Extents pour adresser les blocs des fichiers | Données de petits fichier dans l'inode) | Lien symbolique dans l'inode | Entrées de (petits) répertoires dans l'inode |
| XFS | Arbres B+, indexés par leur offset et leur taille | OUI | OUI | OUI | OUI | OUI | OUI | OUI |
| JFS | Arbre & Binary Buddy[a] | NON | OUI | OUI | OUI | NON | OUI | 8 au maximum |
| ReiserFS[b] | Bitmap based | Non supporté pour l'instant | Sous-arbre de l'arbre du SF | Dans l'arbre du SF | A venir dans la version 4 | [c] | [c] | [c] |
| Ext3FS | Ext3FS n'a pas été conçu à partir de rien ; c'est une surcouche de Ext2FS, et par le fait ne supporte pas les diverses techniques citées ci-dessus. Il apporte en fait la journalisation à Ext2FS, tout en préservant une compatibilité ascendante. | |||||||
| Remarques : a. Binary Buddy : JFS emploie une approche différente pour organiser les blocs libres. La structure est un arbre, où les feuilles sont des bitmaps au lieu d'extents. En fait, les feuilles sont la représentation de la technique d'allocation dite du Binary Buddy (la technique du binary buddy est utilisée pour suivre et rassembler les blocs contigus les groupes de blocs d'espace libre, pour en faire des groupes de grande taille - NdT : voir à ce sujet http://www.osinet.fr/code/glo.asp?Initial=B#binary-buddies). Comme pour la technique de la bitmap, chaque bit correspond à un bloc sur disque. Une valeur à 1de ce bit indique que le bloc est alloué, une valeur à 0 qu'il est libre. Ces bouts de bitmap, contenant chacun 32 bits, peuvent être représentés par un nombre hexadécimal. Ainsi, une valeur à «FFFFFFFF» signifie que tous les blocs correspondants sont tous alloués. Enfin, en utilisant cette valeur d'allocation ainsi que d'autres informations, JFS construit un arbre un groupe de blocs contigus peuvent être rapidement localisés. b. Le coeur de ce système de fichiers est l'arbre B* (une version améliorée de l'arbre B+). La principale différence en est que chaque objet est placé dans un seul et unique arbre. Cela signifie qu'il n'y a pas un arbre par répertoire, mais chaque répertoire a son sous-arbre de l'arbre principal du système de fichiers. Cet usage implique à ReiserFS d'utiliser des techniques d'indexation plus complexes. Une autre différence importante est que ReiserFS n'utilise pas les extents, bien que leur utilisation soit prévue à l'avenir. c. ReiserFS organise tous les objets du système de fichiers dans un arbre B*. Ces objets, répertoires, blocs de fichiers, attributs de fichiers, liens, et autres sont tous organisés dans le même arbre. Des techniques de hachage pour obtenir le champ clé qui permettra d'organiser les éléments de l'arbre. Le plus de cette technique est qu'en changeant de méthode de hachage, on change la façon dont le système de fichiers organise les éléments, et donc leur position relative dans l'arbre. Il y existe des méthodes de hachage qui aident à maintenir la localisation spatiale des éléments entre eux (les attributs avec les entrées de répertoire, les attributs avec les données des fichiers, etc...) | ||||||||
| [1] | NdT : carte de bits, mais nous conserverons le terme original |
| [2] | NdT : liens matériels, hard-links |
| Précédent | Sommaire | Suivant |
| Le journal de transactions | Autres améliorations |