Stockage sur disque pour accès rapide d'attributs avec intervalles de temps

En informatique, le traçage est une méthode permettant de recueillir de l'information sur le comportement d'un système ou d'un programme donné. De manière très générale, le concept est d'ajouter des points de trace dans le code du programme qui, lorsqu'ils seront exécutés, notifieront le traceur pour dire « je suis rendu à X » ou « je viens de terminer Y », etc. Le traceur LTTng (Linux Tracing Toolkit Next Generation) a été développé au laboratoire DORSAL de l'École Polytechnique de Montréal. Ce traceur s'intègre au noyau Linux et permet d'en extraire des « traces noyau ». Une variante du traceur appelée UST (UserSpace Tracer) a également été développée pour s'intégrer plutôt à des applications utilisateur. On parle dans ce cas de « traces utilisateur ». Comme on peut s'en douter, la quantité d'information provenant d'un système tracé peut être très importante, surtout dans le cas de traces noyau. C'est tout un défi de simplement extraire cette information sans affecter la performance du système, mais c'est également un défi que d'analyser toute cette information. Il existe plusieurs outils d'analyse de traces. Parmi ceux-ci on retrouve les visualiseurs, qui permettent de donner une représentation graphique de l'information contenue dans une traces à l'aide de différentes vues. Un des besoins des visualiseurs de traces noyau est de pouvoir recréer l'état complet du système (table des processus, table des fichiers ouverts, etc.) tel qu'il était à n'importe quel point dans la trace. Pour ce faire, les visualiseurs de traces LTTV (Linux Tracing Toolkit Viewer) et TMF (Tracing and Monitoring Framework), développés par le laboratoire DORSAL et ses partenaires, utilisent une méthode de clichés de l'état. Cette méthode consiste à sauvegarder en mémoire plusieurs clichés, à intervalles réguliers, qui contiennent l'état complet du système à ces moments donnés. Lorsqu'une requête est faite pour connaître l'état à un temps t quelconque dans la trace, le cliché précédent le plus proche est rechargé. On relit ensuite les événements de le trace en mettant à jour l'état, jusqu'au moment t, obtenant ainsi l'état voulu. Cette méthode fonctionne bien pour les traces de petites tailles, mais rencontre certains problèmes à plus grande échelle. Par exemple, sur des gros systèmes avec beaucoup de processus actifs, plus d'événements seront générés par seconde, donc des clichés auront à être faits plus souvent (pour conserver le nombre d'événements entre les points, et par le fait même les temps de requêtes, constants). Chacun de ces clichés contiendra également plus d'information, ce qui cause un double problème d'espace. Il existe donc un besoin de concevoir une nouvelle méthode de stockage de cette information d'état, qui puisse être plus efficace en terme d'espace utilisé, sans trop sacrifier de performance. De plus, contrairement à la méthode des clichés, le stockage devrait être fait sur disque de manière à pouvoir supporter des traces de très grande taille. Dans ce mémoire, nous proposons un nouveau système d'état qui permet de définir les changements d'états de manière générique, stocke son information sur disque et conserve un temps de réponse O(log n) pour les requêtes. De plus, nous ne stockons pas d'information redondante. Pour ce faire, chaque état à être enregistré dans l'historique est représenté sous forme d'un intervalle, avec ses bornes égales aux temps de début et de fin de l'état. Les intervalles sont ensuite stockés sur disque, dans une structure spécialement conçue pour cet usage, que nous avons nommé arbre à historique. L'arbre à historique est une structure de données pour intervalles, optimisée pour l'accès sur disque. Les intervalles sont regroupés par nœuds, qui sont de taille constante sur le disque, et ce sont ces nœuds qui sont agencés en arbre. Le fait que les événements dans une trace soient automatiquement ordonnés chronologiquement garantit que les intervalles d'état seront triés par ordre croissant de temps de fin. Grâce à cette hypothèse, nous pouvons construire un arbre à historique de manière incrémentale. Ceci permet à la construction d'être arrêtée et reprise à tout moment, ce qui augmente la flexibilité : nous pouvons par exemple procéder à cette construction seulement lorsque le système est peu utilisé. Il est même possible de lancer des requêtes à l'arbre pendant que celui-ci est en construction. Cette propriété serait très utile pour l'intégration aux visualiseurs de traces, puisqu'elle permettrait à un utilisateur de commencer à utiliser l'information d'état qui a déjà été traitée, sans avoir à attendre que l'historique complet ne soit terminé. Enfin, nous avons testé les performances de l'arbre à historique comparées à celles du travail équivalent effectué par LTTV. Nous avons également testé le comportement du système en utilisant des méthodes de stockages plus générales et mieux connues, comme les R Trees et les bases de données spatiales. Le système d'état de LTTV est très performant, par contre, tel que mentionné plus tôt, il stocke de l'information redondante, est limité par l'espace mémoire, et est difficile à modifier ou étendre. Le nouveau système d'état générique est habituellement plus lent, mais capable de rester à l'intérieur d'un facteur de deux par rapport à LTTV. L'arbre à historique présente cependant un grand avantage par rapport aux structures comme les R Trees et les bases de données, principalement dû au fait que celui-ci n'a pas à être constamment rebalancé. Les temps de construction d'un historique basé sur ces dernières sont beaucoup trop grands pour être utilisable dans un visualiseur de traces. Il semble donc que l'arbre à historique remplit bien sa fonction de structure de stockage d'information d'état venant de traces, et offre un avantage apparent par rapport aux structures de données similaires existantes. En plus, la généricité du système proposé permettra de facilement créer de nouveaux système d'états ou d'en étendre des déjà existants. Cette flexibilité sera très utile pour définir les systèmes d'états d'applications utilisateur, provenant de traces provenant de programmes utilisateurs par exemple.