Résumé

  • Le LFS de Mendel Rosenblum et John Ousterhout transformait de nombreuses petites écritures aléatoires en grands transferts séquentiels, sans faire disparaître les anciennes versions qu’il fallait ensuite récupérer.
  • La mesure la plus éclairante de l’article de 1992 est le « coût d’écriture » : elle impute à la nouvelle donnée les lectures et réécritures effectuées par le nettoyeur.
  • Les travaux ultérieurs ont établi la limite : avec du vrai temps mort, le nettoyage peut rester discret ; avec un disque plein, des mises à jour aléatoires et peu de répit, il revient sous forme de contention.

Le reçu du premier plan

Une écriture vient d’être acquittée. Pour l’application, l’opération est terminée. Pour le système de stockage, plusieurs questions restent pourtant ouvertes : l’ancienne version occupe-t-elle encore un bloc ? existe-t-il un segment propre pour la prochaine rafale ? combien de données vivantes faudra-t-il déplacer afin de rendre l’espace réutilisable ? et, après une panne, jusqu’où faudra-t-il rejouer le journal ?

C’est dans cet écart entre l’accusé de réception et le cycle complet que se situe la portée du log-structured file system. Le travail publié en 1992 par Mendel Rosenblum et John K. Ousterhout n’était pas une simple préférence pour les accès séquentiels. L’équipe Sprite de Berkeley avait construit un système, l’avait exploité et avait rendu visible la facture différée.

Le mécanisme de départ était remarquablement mince. Les données et métadonnées modifiées étaient mises en tampon, puis écrites en grands transferts séquentiels. Des petites écritures synchrones et dispersées devenaient un flux asynchrone. La lecture, elle, ne parcourait pas le journal : des index ordinaires continuaient d’indiquer le bloc courant, et une carte des inodes conservait leur adresse présente. Le journal organisait le placement ; il ne remplaçait pas l’adressage.

Chaque modification créait une nouvelle version. L’ancienne devenait invalide, mais restait physiquement mêlée à des blocs encore vivants. Lorsque le journal faisait le tour du disque, réutiliser directement ces trous aurait détruit les grands transferts qui faisaient l’avantage du modèle. Sprite LFS regroupait donc le disque en segments et ne remettait en service que des segments entiers.

Nettoyer, c’est terminer l’écriture

Le nettoyeur lit des segments candidats, vérifie quels blocs sont toujours vivants, recopie ces blocs de manière compacte et libère les segments d’origine. Les résumés de segment enregistrent l’identité de chaque bloc — fichier et position logique — afin que le système puisse la comparer à l’état courant. Les mêmes informations servent au roll-forward après une panne.

La variable critique est la proportion de données vivantes dans le segment choisi. Un segment presque mort offre beaucoup d’espace pour peu de copie. Un segment très vivant exige beaucoup de lecture et de réécriture pour un gain faible. L’espace inoccupé devient ainsi une ressource de performance : une utilisation globale moins élevée augmente le choix de segments peu coûteux à nettoyer.

Rosenblum et Ousterhout ont refusé de cacher cette dépense derrière une belle latence. Leur « write cost » rapporte tout le trafic nécessaire — nouvelles données, lectures du nettoyeur, recopie des blocs vivants — aux seuls octets nouveaux. Un coût de un représente le cas idéal où rien d’autre ne bouge. Un coût de dix signifie qu’environ un dixième de la bande passante brute reste disponible pour la donnée nouvelle. Le calcul juge le cycle, pas seulement l’entrée.

Restait à choisir les segments. La stratégie gloutonne, qui prend le segment le moins utilisé, paraissait naturelle. Avec de la localité, elle pouvait pourtant mal se comporter : des données froides demeuraient prisonnières de segments partiellement vides, tandis que des données chaudes étaient recopiées juste avant d’être modifiées de nouveau. La politique coût-bénéfice combinait l’utilisation avec l’âge du bloc le plus jeune, selon une expression proche de (1-u) × âge / (1+u).

L’âge n’était pas une prédiction certaine ; il servait d’indice de stabilité. On pouvait nettoyer des segments froids à une utilisation encore élevée, puisque leurs blocs risquaient peu de rebouger, et attendre qu’un segment chaud soit beaucoup plus vide. Dans les simulations décrites, cette séparation réduisait parfois de moitié le coût d’écriture par rapport à la stratégie gloutonne. Un changement de régime restait cependant capable de transformer le froid d’hier en travail de demain.

Les chiffres avaient une frontière

Les microbenchmarks de l’article excluaient le nettoyage. Ils prouvaient l’avantage maximal du chemin d’écriture, pas son équilibre de long terme. La preuve la plus intéressante venait de quatre mois d’exploitation : dans cet environnement Sprite, le coût d’écriture se situait autour de 1,2 à 1,6 et le débit durable atteignait environ 70 % de la bande passante séquentielle maximale.

Ce sont de bons reçus de code en fonctionnement, non des lois universelles. Les auteurs signalaient eux-mêmes leur expérience limitée. Ils distinguaient aussi la reprise : un checkpoint fixait une base connue de la carte des inodes, puis le système avançait dans les segments plus récents. Des checkpoints fréquents alourdissent le fonctionnement normal ; des checkpoints espacés augmentent le parcours après panne. L’acquittement, le checkpoint et la durée de reprise décrivent trois réalités liées, mais différentes.

Les objections ont renforcé le modèle

Les implémentations suivantes n’ont pas donné une victoire générale à LFS. Margo Seltzer, Keith Bostic, Marshall Kirk McKusick et Carl Staelin ont porté l’idée dans BSD. Ils ont montré qu’un système de fichiers classique, mieux groupé, pouvait rattraper une partie du gain. LFS gardait son avantage le plus net sur les charges riches en métadonnées et en petits fichiers ; les gros fichiers donnaient des résultats comparables.

Dans une comparaison de 1995, le nettoyeur réduisait de plus de 33 % les performances transactionnelles avec le disque testé à moitié plein. D’autres mesures citées atteignaient 40 %. Un travail parallèle sur les heuristiques constatait toutefois que 97 % du nettoyage du système le plus chargé pouvait se faire en arrière-plan. Il n’y a pas contradiction. L’arrière-plan est un créneau de paiement. Lorsque le temps mort existe, la dette est réglée avant la concurrence. Quand la réserve diminue et que le flux ne s’arrête plus, la même opération prélève la bande passante visible.

Les méthodes adaptatives ont ensuite précisé la zone favorable : petites écritures fréquentes, lectures absorbées par le cache, temps mort suffisant. Les mises à jour aléatoires sur un disque plein, sans répit, formaient la zone défavorable. Taille des segments, politique de nettoyage et organisation des lectures pouvaient déplacer la frontière ; aucune ne l’abolissait.

L’apport d’Ousterhout ne tient donc pas dans la formule « séquentiel égale rapide ». Avec Rosenblum et l’équipe Sprite, il a contribué à une architecture où le coût futur devenait mesurable. Le journal d’une écriture réussie décrit une couche. La réserve de segments, le travail du nettoyeur et la capacité de reprise en décrivent d’autres.

Sources