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.

Abstract

The tracing of computer systems allows programmers and users to extract precious behavioural data about their systems or applications. From a very high-level point of view, the concept of tracing relies on inserting trace points, or probes, at specific places in a program's code. Whenever execution reaches those points, the application will notify the tracer, to say “I just got to point X”, “I just finished Y” or anything similar. The LTTng tracer (Linux Tracing Toolkit Next Generation) was developed by the DORSAL lab in the École Polytechnique de Montréal. This tracer integrates with the Linux kernel and allows taking kernel traces. A variant called UST (UserSpace tracer) allows instrumenting and tracing userspace applications. Traces coming from userspace applications are called, simply, userspace traces. As one could expect, the amount of information coming from a running system can be quite big, especially in the case of kernel traces. Extracting and saving this information without affecting the running system is already quite a challenge, but analyzing this huge amount of information is also a challenge by itself. There are many tools available to analyze such traces. Among those are trace viewers, which allow seeing a graphical representation of the different elements in a trace. In the case of kernel trace viewers, it is useful to be able to reproduce the state of the traced system, like the process table, the open files, etc. at any point in the trace. To do so, viewers like LTTV (Linux Tracing Toolkit Viewer) or TMF (Tracing and Monitoring Framework, an Eclipse plugin part of Linux Tools), use a checkpoint method. This method consists in saving, in memory and at regular intervals, complete dumps of the system state. We call those dumps the ``checkpoints''. Whenever a request to regenerate the state at an arbitrary time t is sent, the state system will reload the previous checkpoint, seek to the corresponding location in the trace, then replay the events and update its temporary state until we reach time t. Using such a method avoids having to start from the beginning of the trace every time. The checkpoint method works well enough for small traces, but is problematic at larger scales. The number of events between checkpoints is kept constant, to keep the average time for requests constant too. This means that the number of checkpoints will increase with the number of events in the trace. In addition, the size of each checkpoint will increase if there are more processes running and more stuff going on at the same time. And since these checkpoints are stored in RAM, there is a hard limit on the size of the trace that can be analyzed. We could, up to a certain point, reduce the amount of checkpoints, but that would degrade the performance of the state system. There is clearly a need for a new method of state storage, which should allow opening and analyzing traces up to the terabyte range. It is obvious that whatever information we store about the state will have to be written to disk (since the amount of state information increases linearly with the size of the trace but we can't, unfortunately, expect RAM sizes to increase linearly with disk space). In this thesis, we propose a new state system for trace viewers, which diminishes the weaknesses presented previously. This new system also provides a generic way of defining state changes (the current kernel state systems are hard-coded into the viewers). It stores its information on disk but maintains a reasonable response time, which scales with O(log n). It also avoids storing any redundant information. To do so, every state is saved as an interval of time. The start and end of the interval correspond to the start time and end time of the state. These intervals are then stored on disk, inside a container specifically designed for this task. We have called this new container the History Tree. The History Tree is a data structure for intervals optimized for disk access. The intervals are stored in nodes, which occupy a predefined constant amount of space on disk. It's those nodes which are arranged in a tree structure. Since the events in the trace are sorted chronologically, the corresponding states are created and inserted in the History Tree by ascending order of end times. The History Tree has been specifically tailored to receive intervals ordered in such a way. For example, it does not need rebalancing: when a node is full, it is marked as done and a sibling node is created. This allows for incremental construction, which can even be stopped and resumed at any time. It is also very possible to query the Tree while it's being built. This feature will be very interesting for the integration in trace viewers : the users could start working with the data that has already been parsed, without having to wait for the entire history to be built. We've then compared the performance of the History Tree to the one of LTTV. We have also tested the new state system using more generic data structures, like R-Trees or spatial databases, as a back-end instead of the History Tree. It was hard to beat the performance of LTTV's hard-coded state system. However, the new generic state system using the History Tree could usually remain within a factor of two of LTTV's performance when comparing history construction times. The History Tree however proved much better suited at handling our state intervals than the preexisting data structures like the R-Tree and the database. While the History Tree was designed around the fact that the intervals are received by ascending order of end times, the R-Trees had to be constantly rebalanced to cope with it. This resulted in very long history construction times, which made them inappropriate for use in trace viewers. Finally, we can say that the History Tree is an efficient data structure for storing state intervals coming from kernel traces. It also offers obvious advantages over well-known preexisting data structures like R-Trees, at least in our particular use cases. The genericity of the new proposed framework will also allow users to easily extend existing state systems, as well as create new ones. This will be useful when defining custom state systems for userspace applications, for example.