metadatafs.html from Gulus at Krugle

Show metadatafs.html syntax highlighted

<PRE>
Solutions aux problèmes de Meta-data dans les file systems

                      A K A

       Soft updates    vs    Journalling file systems
----------------------------------------------------------

 Par Vincent Labrecque
     limitln à psyfreaks.ca

[Note: cet article provient de l'édition 2002-02 de LJNB, un journal qui
n'existe plus.]


Introduction
------------

 Un des problèmes qui est addressé depuis quelques années dans la recherche
sur les FS, la sauvegarde de l'integrité du métadata, est quelque chose qui
touche l'utilisation du systême assez directement.  Ce n'est pas une question
d'optimiser 4 picosecondes par année, c'est pour regler ce qui arrive si votre
petit frère décide d'appuyer sur le bouton `Power' de votre ordinateur, ou si
votre /sys/arch/i386/conf/MY_HACKED_KERNEL décide de crasher en beauté.

 Quelques solutions ont été proposées à ce problème, j'analyserai dans ce papier
deux techniques, parce qu'elles sont les plus utilisées presentement: Soft 
updates et les journaling FS. 

 Soft updates est un changement au niveau de l'implémentation du file-system, la
structure sur le disque est la même et on utilise divers algorithmes pour palier
le problème de synchronisation entre les mises à jour du métadata. Ça a été 
développé par Gregory R. Ganger, Marshall Kirk McKusick, Craig A. N. Soules et 
Yale N. Patt, et je suggère fortement la lecture du papier qu'ils ont écrit sur
le sujet [1].  McKusick a implementé softdep pour FFS dans FreeBSD, code qui a 
été integré dans OpenBSD et NetBSD aussitôt qu'il changea sa license (qui était
à l'origine etait trop restrictive).

 Les FS de journaling, ou logging FS, utilisent une autre approche.  On utilise
un 'log', soit comme un fichier sur le disque (ex: FFS-file) ou sur un périphé-
rique indépendant (un autre disque, de la mémoire non-volatile, etc).  On
enregistre les opérations dans le log et pour récupérer un état cohérent du
système, on rejoue le journal à l'envers jusqu'à l'obtention de quelque chose 
qui fasse du sens. (par exemple, juste après une opération complète).  Le 
problème est que ces systèmes sont souvent plus lents et requièrent parfois le 
changement de la structure des fichiers sur le disque. Des exemples de systèmes
basés sur cette méthode sont JFS, ReiserFS, ext3, etc.

 Je suis personnellement biaisé vers Soft Updates, car c'est une solution
beaucoup plus élégante (IMHO) et que c'est plus efficace dans la majorité des 
benchmarks.  En plus de permettre de mounter un FS qui n'a pas été unmounté
sans besoin d'outil comme fsck(1), ca ne requiert aucune modification sur le
format sur le disque.  Malgré ces avantages, la plupart des fans de linux
semblent s'axer vers des FS de journaling, avec log sur le même disque. Peut-
être parce que la solution n'a pas encore été implementée pour leur ext2fs,
mais je vais tenter de décrire les deux systèmes le mieux possible pour que vous
puissiez faire votre propre opinion et peut-être même l'implementer? :-)

Description générale du problème
--------------------------------

 Dans un FS, l'information comme la taille des fichiers, leurs noms, les
blocs où un inode pointe, etc, est très importante.  Si une entrée de
répertoire pointe vers un inode mal initialisée (disons que l'OS a crashé en
plein milieu de l'allocation), ou que cet inode pointe vers des blocs qui n'ont
pas étés marqués comme utilisés, ça fait un peu de trouble.  La plupart des
systèmes utilisent déjà, pour éviter les problèmes, un ordre particulier dans
leurs operations pour préparer leur metadata.  Par exemple, on va préparer les
blocs sur le disque en premier, puis on prépare l'inode qui y pointe, puis
finalement on prépare le direntry qui pointe vers cet inode.  Un des problèmes
vient du fait que pour éviter l'usage abusif du disque, on cache l'information,
puis on écrit les blocs qui ont été modifiés (marqués 'dirty') sur le disque
une fois toutes les N secondes.

 Si l'ordinateur est arreté sans que l'OS ait eu le temps de flusher ses caches,
le FS peut être laissé dans un état incohérent, où des direntries pointent vers
des inodes pas alloués, etc.

 La solution traditionnelle est l'outil fsck, (qui vient bien sûr de FileSystem
ChecK, pas f-ck) qui est roulé quand l'OS part pour vérifier tous les FS qui
n'ont pas étés marqués 'clean'. (quand on unmount la partition correctement,
par exemple en faisant 'shutdown(1)', le système marque la partition comme
'clean'.)  Le problème avec cette solution est que fsck ne peut pas toujours
réparer les problèmes et qu'il est souvent lent et augmente de beaucoup le
temps requis pour remettre le systeme 'up'.

 Maintenant que le problème est connu, regardons les solutions.

Description plus approfondie des deux types de systèmes
-------------------------------------------------------

= Soft Updates =

 Avec Soft Updates, la solution se résume en deux points: avoir un ordre strict
d'opérations et de s'assurer d'avoir constemment un état cohérent sur le disque.
De plus, le système ammène des performances meilleures que FFS normal. (près de
la vitesse de FFS-async (mount -o async [...]))

 Pour garder la cohérence, on utilise une liste de dépendances associée à chaque
objet.  Que sont les objets?  Si on regarde les dépendances au niveau des blocs
sur le disque, on peut facilement arriver a un deadlock.  Par exemple, si on
relie un inode sous le nom X dans le répertoire B, puis qu'on efface le fichier
Y dans le même répertoire, la logique nous dit qu'on doit effacer l'entrée de Y
dans B avant de libérer le bloc, tandis que la création nous oblige à écrire le
bloc avant de le faire le lien dans B.  En gros, on a :

   [libre][nom] &lt;--dependences--&gt; &lt; nom, inode &gt;

 Original:
   {Inode block}     {Directory block}
   [*][Inode #4 ]    &lt; -- , #0 &gt;
   [ ][Inode #5 ]    &lt; B  , #5 &gt;
   [*][Inode #6 ]    &lt; C  , #7 &gt;
   [ ][Inode #7 ]

 Create(A)

   {Inode block}     {Directory block}
   [ ][Inode #4 ] &lt;- &lt; A  , #4 &gt;

   [ ][Inode #5 ]    &lt; B  , #5 &gt;
   [*][Inode #6 ]    &lt; C  , #7 &gt;
   [ ][Inode #7 ]

 Delete(B)

   {Inode block}     {Directory block}
   [ ][Inode #4 ] &lt;- &lt; A  , #4 &gt;
   [*][Inode #5 ] -&gt; &lt; -- , #0 &gt;

   [*][Inode #6 ]    &lt; C  , #7 &gt;
   [ ][Inode #7 ]

 La solution? On regarde les dépendances à un niveau plus bas encore.

 Même maintenant qu'on a les dépendances à un niveau acceptable, le problème de
dépendances circulaire existe toujours.  Par exemple (exemple volé gratuitement 
du paper[1] de Ganger et al):

      En memoire                           Sur le disque

1 - Après la mise à jour du metadata :

   {Inode block}     {Directory block}     {Inode block}   {Directory block}
   [ ][Inode #4 ] &lt;- &lt; A  , #4 &gt;           [*][Inode #4]   &lt; --, #0 &gt;
   [*][Inode #5 ] -&gt; &lt; -- , #0 &gt;           [ ][Inode #5]   &lt; B , #5 &gt;

   [*][Inode #6 ]    &lt; C  , #7 &gt;           [*][Inode #6]   &lt; C , #7 &gt;
   [ ][Inode #7 ]                          [ ][Inode #7]

2 - On écrit une version sure du directory block sur le disque, une dépendance
    s'en va.
   {Inode block}     {Directory block}     {Inode block}   {Directory block}
   [ ][Inode #4 ] &lt;- &lt; A  , #4 &gt;           [*][Inode #4]   &lt; --, #0 &gt; 
   [*][Inode #5 ]    &lt; -- , #0 &gt;           [ ][Inode #5]   &lt; --, #0 &gt;
   [*][Inode #6 ]    &lt; C  , #7 &gt;           [*][Inode #6]   &lt; C , #7 &gt; 
   [ ][Inode #7 ]                          [ ][Inode #7]             

3 - Ensuite, on écrit le bloc d'inode pour indiquer que l'inode 4 est/va être
    utilisé et que l'inode 5 est libre.

   {Inode block}     {Directory block}     {Inode block}   {Directory block}
   [ ][Inode #4 ]    &lt; A  , #4 &gt;           [ ][Inode #4]   &lt; --, #0 &gt;
   [*][Inode #5 ]    &lt; -- , #0 &gt;           [*][Inode #5]   &lt; --, #0 &gt; 
   [*][Inode #6 ]    &lt; C  , #7 &gt;           [*][Inode #6]   &lt; C , #7 &gt;
   [ ][Inode #7 ]                          [ ][Inode #7]                   

4 - On écrit le nouveau directory block maintenant que les inodes sont
    correctement initialisées.

   {Inode block}     {Directory block}     {Inode block}   {Directory block}
   [ ][Inode #4 ]    &lt; A  , #4 &gt;           [ ][Inode #4]   &lt; A,  #4 &gt; 
   [*][Inode #5 ]    &lt; -- , #0 &gt;           [*][Inode #5]   &lt; --, #0 &gt;
   [*][Inode #6 ]    &lt; C  , #7 &gt;           [*][Inode #6]   &lt; C , #7 &gt; 
   [ ][Inode #7 ]                          [ ][Inode #7]                   

 On montre D += A, puis D -= B, ce qui est en gros l'exemple décrit précedem-
ment.  Premièrement, on écrit le bloc du répertoire avec l'entrée de B en moins.
Ensuite, on écrit le bloc des inodes avec l'entrée de A marquée comme utilisée 
et celle de B comme étant libre.  Les deux n'ayant aucune dépendance, si le
système est arreté, le pire qui puisse arriver est que l'inode de 4 soit marquée
comme utilisée même si aucune entrée de répertoire n'y pointe. (voir plus loin 
pour la solution) Enfin, on écrit le bloc de répertoire avec l'entrée de A.

 Tadam!

 À toutes les étapes, le système est dans un état consistant, ce qui était le
but visé.  Pour chaque changement d'un élément de metadata (créations d'un
inode, ajout d'une entrée dans un répertoire), on garde la version 'avant' et
'après'.  Un bloc peut être écrit à n'importe quel moment, en autant qu'on roll-
back toutes les dépendances avant de le faire.  Pendant l'écriture sur le disque
(les disques ne sont pas encore assez rapide pour que ce soit une opération
atomique), le bloc est verrouillé pour empêcher les applications de voir l'état
'undone'.  (si le système est arreté, le fait qu'une application voyait un état
qui n'était pas le même que celui sur le disque ne change rien)

 Se rappeller que ces opérations de roll-back sont faites uniquement quand le OS
flush ses caches, ce qui permet d'optimiser beaucoup les choses. Parfois deux
opérations inverses vont s'annuler, etc.  Le système essaie aussi de clusterer 
(regrouper) les écritures sur le disque pour réduire les accès au disque.

 Le disque étant toujours dans un état cohérent, l'usage de fsck est inutile.  Le
système peut être repartit sans problème. (si l'information sur le disque (ex:
le superblock) n'a pas été endomagée, bien sûr!)

 Pour le problème des inodes qui sont libres mais marquées comme utilisées, le 
système peut rouler un background-fsck. Ce programme utiliserait le temps libre 
de la machine pour recalculer les inodes utilisées et corriger les problèmes 
pendant que le système roule. Ça permet d'avoir un système fonctionnel immédia-
tement, quite a perdre quelques bytes sur le disque tout de suite après le 
démarrage.  Pas si mal quand même :-)

 Ce programme n'a pas encore été implémenté, mais il est (je crois) en dévelop-
pement et devrait être disponible éventuellement.

 Pour plus de détails, lire le "Soft updates: A Solution to the Metadata Update
Problem in File Systems."[1] C'est très intéressant et ça va plus en détails 
dans la théorie, en plus d'expliquer l'implémentation sur FFS et les problèmes 
rencontrés.


= Journaling File Systems =

 Leur solution au problème est de garder un log de toutes les operations 
effectuées sur du metadata, pour pouvoir, quand le système redémarre, remonter
dans le log jusqu'à un état cohérent.  Pour ça, on utilise des marqueurs qui
indiquent les operations qui ont été effectuées sur le disque.

 Le problème avec ça, c'est que pour que ce soit efficace, le log doit être
gardé sur un mini-disque ultra-rapide dédié au log, ou dans un espace de RAM
non-volatile.  Même si les logs sont écrits en streams (flots de données), donc
en éliminant le besoin des seeks (accès à l'information), si c'est sur le même 
disque, il va seeker constemment quand même.

 La seule (IMO) chose un peu plus cool, dans ext3 [3], c'est qu'il sauve aussi
les changements de data, pas seulement de metadata. Ca veut dire que les données
vont être dans un état consistant, pas seulement l'arborescence du système de
fichiers.

 Bon, le système est assez simple, alors ma couverture s'arrête ici. La lecture
des benchmarks Softdep VS Journaling[2] est instructive, je vous recommande 
fortement sa lecture. Ça inclue en même temps une introduction aux deux systèmes
qui est peut-etre meilleure que la mienne :-) (ça montre plus d'exemples, ça 
c'est sur.)

Conclusion
----------

 Euh, utilisez votre cerveau pour conclure comme vous voulez!

References
----------
   [1] Soft updates: A Solution to the Metadata Update Problem in File
Systems:
         <a href="http://www.ece.cmu.edu/%7Eganger/papers/softupdates.pdf">http://www.ece.cmu.edu/~ganger/papers/softupdates.pdf</a>
   [2] Journaling Versus Soft Updates: Asynchronous Meta-data Protection in 
       File Systems: <a href="http://www.usenix.org/publications/library/proceedings/usenix2000/general/full_papers/seltzer/seltzer_html/index.html">http://www.usenix.org/publications/library/proceedings/usenix2000/</a>
	 (suite) <a href="http://www.usenix.org/publications/library/proceedings/usenix2000/general/full_papers/seltzer/seltzer_html/index.html">http://www.usenix.org/publications/library/proceedings/usenix2000/"&gt;general/full_papers/seltzer/seltzer_html/index.html</a>
   [3] Ext3: <a href="http://www.redhat.com/support/wpapers/redhat/ext3/index.html">http://www.redhat.com/support/wpapers/redhat/ext3/index.html</a>


Vincent Labrecque limitln à psyfreaks.ca
See more files for this project here