Retrouvez cet article dans : Linux Magazine 79

L’informatique évolue de jour en jour. La capacité des disques durs et leur vitesse croissent continuellement. D’un autre côté, les systèmes doivent être toujours plus fiables. Évidemment, pour cela, le logiciel et l’organisation des données doivent évoluer. L’équipe de ReiserFS, avec la mouture v4 de leur système de fichiers, espère atteindre ces deux objectifs si difficilement conciliables.

Depuis dix ans, Hans Reiser, principal développeur de ReiserFS, souhaite obtenir un système de fichiers révolutionnaire. La disposition des fichiers par leur nom lui semble une technologie dépassée. À terme, de nouvelles primitives devraient apparaître pour classer les données différemment. L’idée des associations est née.
Le système lui-même pourra être comparé à une base de donnée. Vous souhaitez lire votre document sur la nourriture du chat ? Il vous suffira alors de demander la liste des documents traitant des félins.

Fig. 1 : Structure d’un arbre quelconque.

Malheureusement, cela reste encore en projet et nécessitera de lourdes modifications dans les systèmes d’exploitation. En plus, même si l’idée est présente, elle reste relativement floue pour les développeurs. Néanmoins, tout est réalisé dans ReiserFS pour faciliter le développement et intégrer des fonctionnalités nouvelles.

Fig. 2 : Un graphe (ci-dessus) diffère de l’arbre par son absence de hiérarchie.

Reiser4 est un système innovant, rompant toute compatibilité avec la version 3. Pour le moment, ce système de fichier n’est pas inclus dans la branche principale du noyau Linux : il vous faudra appliquer un patch. Vous pourrez récupérer la dernière version sur le site http://www.namesys.com. Cependant, le patch devra correspondre avec la version du noyau choisi.
Malheureusement, l’installation d’un Linux sur une nouvelle partition en Reiser4 sera assez complexe à mettre en œuvre. Vous devrez en effet créer votre propre disque d’installation avec le support de Reiser4 dans le noyau. Ou encore, si la distribution le supporte, vous pourrez également y parvenir en créant une disquette de pilotes.

 Fig. 3 : Un arbre balancé.

N´installez surtout pas Reiser4 sur un serveur ou tout autre poste en production. Pour le moment, seules des versions instables sont disponibles. Le système de fichiers n’est pas encore assez mature, prenez plutôt ReiserFS v3.

Une structure en couches

L’architecture n-tiers, utilisée dans Reiser4, permet une souplesse exemplaire dans le développement et la maintenance. En décomposant l’application en couches indépendantes les unes des autres, une modification n’altère que la couche concernée et non pas la totalité de l’application. Mais des échanges de données se réalisent.

Fig. 4 : Le nœud d’un B-Arbre.

Fig. 5 : Le nœud d’un B+Arbre.

La couche au niveau n peut communiquer avec la couche n+1, c’est-à-dire immédiatement supérieure, et la couche n-1, immédiatement inférieure. En aucun cas, une couche n communiquera avec une couche n-2. L’interface entre chaque couche est limitée, pour garantir une indépendance maximale. Tout d’abord, le driver « block device » du noyau gère les accès sur le disque dur. Une couche s’occupe alors de l’organisation physique des données grâce à un arbre utilisant des clés. Puis s’ajoute la couche sémantique donnant un sens aux données (fichier, répertoire, etc.).
Elle permet alors d’obtenir le système de fichiers tel que nous pouvons l´apercevoir en tant qu´utilisateur. Ainsi, en utilisant une couche sémantique différente, les interactions avec le système d’exploitation et l’utilisateur diffèrent. Par conséquent, pour l’implémentation des associations, seule cette couche doit être modifiée. La réalité est un peu plus complexe. En fait, il existe plus de couches, mais, pour la compréhension, seules celles citées ci-dessus sont nécessaires. Mais, en plus des points d’accès pour la communication inter-couches, des interfaces pour les plugins sont rajoutées dans chacune des couches. Cette notion est vraiment spécifique à ReiserFS.
Par exemple, si vous voulez crypter ou compresser votre système de fichiers, vous rajoutez le plugin correspondant. Vous pourrez donc accroître la sécurité, modifier le comportement des fichiers et des répertoires ou accéder à diverses fonctionnalités selon le besoin.

Fig. 6 : Structure d’un BLOB.

Fig. 7 : Structure d’un arbre dansant.

Attention cependant ! Vous pourrez rajouter autant de plugins que vous le souhaitez mais vous ne pourrez en aucun cas en supprimer un. En effet, dès lors que le plugin a servi pour modifier une donnée, le retirer empêche l’accès à cette dernière. Par exemple, avec le plugin de cryptage, vous inscrivez votre fichier sur le disque. Si vous retirez le plugin, vous ne pourrez plus décrypter le fichier en question. Actuellement, la couche sémantique offre les mêmes caractéristiques qu’un autre système de fichier. La hiérarchie est nécessaire pour garder la compatibilité avec les applications existantes. Nous retrouvons donc / avec ses sous-répertoires et les fichiers. Cette couche s’occupe de présenter les données aux applications.
Certaines conversions s´opèrent afin de correspondre aux exigences du système d´exploitation. Certaines particularités se retrouvent à ce niveau, comme les répertoires cachés. L’équipe de ReiserFS a également rajouté la notion de fichiers qui sont des répertoires.
Dès qu’ils sont interrogés en tant que fichiers, ils retournent des données, sinon une liste de fichiers. Cette notion permet d’obtenir des options avancées en matière de permissions et de divers attributs. Ainsi, plutôt que d’utiliser chmod, vous pourrez éditer le fichier des permissions du fichier-répertoire.

Fig. 8 : Un arbre avant rééquilibrage...

La couche de stockage

Une autre des principales exigences de Hans Reiser est l’atomicité des opérations. En fait, pour limiter la corruption du système en cas de plantage ou tout autre problème, soit l’opération est écrite entièrement, soit elle n’est pas prise en compte. De plus, l’utilisation d’un journal assure une sûreté de fonctionnement plus élevée. Ainsi, l’analyse de la partition concernée après un redémarrage forcé n’est pas toujours obligatoire. Mais comment fonctionne le journal ? En fait, une entrée du journal est créée à chaque transaction. Elle contient deux inodes de 64 bits à savoir la valeur actuelle sur le disque dur et la nouvelle.  En cas de problème, les deux valeurs seront différentes. Lors de l’analyse du journal, le système les comparera et écrasera la valeur du disque dur par celle du journal si nécessaire. Évidemment, chaque entrée est effacée dès que la transaction s’est effectuée entièrement.  Afin de préserver l’atomicité des opérations, la transaction ne se limite pas à une partie du fichier, mais à son ensemble. Ainsi, si un problème a interrompu une action, Reiser4 écrit tout simplement le contenu du journal sur le disque. L’organisation des données sur le disque, dans la couche de stockage, est régie par un arbre dansant. Cette notion a été inventée par Hans Reiser pour disposer d’un algorithme adapté. Elle se base sur les B+Arbres dont le fonctionnement est décrit ci-après.
Tout d’abord, les B-Arbres ont une hauteur h. Les feuilles se situent toujours au même niveau pour obtenir un arbre équilibré. En plus de cette notion, apparaît l’ordre n. Lorsqu’un nœud contient 2n+1 feuilles ou plus, une réorganisation rééquilibre l’arbre pour avoir n feuilles dans ce nœud. Si un manque de place empêche l’ajout d’une donnée supplémentaire, un niveau est créé.  Bien sûr, ce changement s’effectue sur l’ensemble de l’arbre afin de respecter la définition. Chaque donnée est identifiée par une clé pour faciliter les recherches. Comme l’arbre est trié par ordre croissant, il suffit de comparer la clé avec celles qui sont disponibles dans le nœud.

Fig. 9 : ...puis après.

Soit la clé est directement dans le nœud, soit elle est comprise entre deux valeurs et elle est située dans un nœud inférieur. Un nœud de B-Arbre contient effectivement des données contrairement aux B+Arbres. Ceci est l’unique différence entre les deux algorithmes. Seulement ni ReiserFS v3 ni Reiser4 n’utilisent ces algorithmes. Pour commencer, les fichiers sont enregistrés dans les feuilles. Chacune de ces dernières contient 4 ko par défaut sur une architecture x86 32 bits. Reiser3 utilise un BLOB. Il s’agit en fait d’un B+Arbre dont certaines feuilles contiennent des pointeurs sur un objet plus volumineux.  L’arbre n’est pas réellement balancé comme les précédents, mais garde le principe de l’algorithme. Les arbres dansant de Reiser4 enregistrent ces objets volumineux comme une feuille de taille supérieure. Il n’existe plus alors de pointeurs vers plusieurs positions dans le fichier.  Mais la notion la plus importante de cet algorithme est l’introduction de nœuds vides. Les données devront alors être enregistrées le plus à gauche possible. En réalité, la réorganisation de l’arbre est différée. Non seulement, cela permet de garder de la place pour les nouveaux fichiers mais, en plus, cela limite les accès aux disques lors de manipulations importantes.
Dans un souci de performance, la taille de l’arbre est limitée. Par défaut, la hauteur ne peut dépasser 8 niveaux pour un ordre de 32. Le nombre de feuilles reste conséquent et permet d’utiliser une partition de plus d’un million de téraoctets. Le noyau même de Linux ne permet pas une telle taille de partition. Hans Reiser et son équipe ont développé des concepts intéressants pour l’avenir, avec une architecture particulière et des algorithmes performants. Le but clairement affiché reste de surpasser les concurrents.  D’ailleurs, nous pouvons lire sur le site officiel que Reiser4 est le système le plus rapide, mais est-ce véridique ? Des benchmarks nous le montrent sur des critères particuliers. Mais comment estimer la performance ?
Tellement de critères sont possibles et chaque système de fichiers dispose de ses atouts et de ses défauts. ReiserFS, par exemple, sera plus efficace pour un volume conséquent de données.

Retrouvez cet article dans : Linux Magazine 79