Structures de données hautement extensibles pour le stockage sur disque de séries temporelles hétérogènes

Les systèmes informatiques deviennent de plus en plus complexes, et les développeurs ont plus que jamais besoin de comprendre comment interagissent les nombreux composants de leurs systèmes. De nombreux outils existent pour instrumenter, mesurer et analyser les comportements et la performance des logiciels. Le traçage est une technique qui enregistre de nombreux points associés à des événements du système et l'estampille de temps à laquelle ils se sont produits. L'analyse manuelle des traces produites permet de comprendre différents problèmes, mais elle devient fastidieuse lorsque ces historiques contiennent de très grands nombres de points. Il existe des logiciels pour automatiser ces analyses et fournir des visualisations, mais ces derniers peuvent aussi montrer leurs limites pour se mettre à l'échelle des systèmes les plus étendus. Dans des travaux précédents, Montplaisir et coll. ont présenté une structure de données sur disque, optimisée pour stocker les résultats des analyses de traces sous forme d'intervalles d'états: <clé, t_{début}, t_{fin}, valeur>. La structure, nommée State History Tree (SHT), est un arbre pour lequel chaque nœud est associée à un bloc de disque, chaque nœud dispose donc d'une capacité fixe pour stocker des intervalles et est défini par un intervalle de temps tel que cet intervalle est inclus dans celui du nœud parent et que les intervalles de deux enfants ne se superposent pas. Cette structure était plus efficace que d'autres solutions génériques, mais pouvait dégénérer, dans des cas avec un très grand nombre de clés, pour une trace avec de nombreux fils par exemple, la profondeur de l'arbre était alors proportionnelle au nombre de fils, et de très nombreux nœuds "vides" étaient écrits sur disque, gaspillant de l'espace. De plus, les requêtes pour extraire les informations de la structure étaient souvent le goulot d'étranglement pour l'affichage des données. Dans ce travail, nous analysons les limites de la base de données actuelle qui la conduisent à dégénérer et nous étudierons les cas d'utilisation des requêtes. Nous proposons des modifications structurelles permettant d'éliminer les cas de dégénérescence lorsque la trace contient de nombreux attributs, tout en réduisant la taille sur disque de la structure pour tous types de traces. Nous ajoutons aussi des métadonnées aux nœuds de l'arbre pour réduire le nombre de nœuds lus pendant les requêtes. Ceci permet de réduire la durée des requêtes de 50% dans la plupart des cas. Ensuite, nous cherchons à optimiser le processus d'insertion des intervalles dans les nœuds de l'arbre afin de regrouper les intervalles qui seront demandés dans une même requête pour limiter le nombre de blocs de disque à lire pour répondre. Le nombre d'intervalles pris en compte dans l'optimisation peut augmenter avec le nombre de clés par exemple, ce qui permet de maintenir un équilibre entre le temps supplémentaire requis pour l'optimisation et les gains constatés sur les requêtes qui deviennent plus flagrants lorsque l'analyse produit de nombreuses clés. Nous introduirons aussi un nouveau type de requête profitant de ces optimisations et permettant de retourner en une requête un ensemble d'intervalles qui précédemment prenait plusieurs requêtes. De plus cette requête assure que chaque nœud est lu au plus une fois, alors que l'utilisation de plusieurs requêtes impliquait que certains nœuds étaient lus plusieurs fois. Nous montrons que l'utilisation de cette requête dans une des vues principales du logiciel de visualisation augmente considérablement sa réactivité. Nous profiterons ensuite de ces apprentissages pour faciliter la mise à l'échelle d'une seconde structure de données du logiciel d'analyse de trace, qui stocke des objets nommés "segments", sous la forme de <t_{début}, t_{fin}, valeur>. Ces objets étaient précédemment stockés en mémoire et donc le nombre que nous pouvions stocker était limité. Nous utilisons une structure en arbre fortement inspirée du SHT. Nous montrons que la structure sur disque est au pire un ordre de grandeur plus lent que les structures en mémoire à la lecture. De plus, cette structure est particulièrement efficace pour un cas d'usage qui demande à retourner des segments triés. En effet, nous utilisons un algorithme réalisant l'évaluation à la demande et un tri partiel entre les nœuds, qui utilise moins de mémoire que le tri de tous les segments.

Abstract

Computer systems are becoming more and more complex, and developers need more than ever to be able to understand how different components interact. Many tools have been developed for instrumenting, measuring and analysing the behavior and performance of software. One of these techniques is tracing, which records data-points and a timestamp associated to system events. Trace analysis can help solve a number of problems, but manual analysis becomes a daunting task when these traces contain a large number of points. Automated trace analysis software has been developed for this use case, but they too can face difficulties scaling up to the largest systems. In previous work, Montplaisir et al. presented a disk-based data structure, optimized for storing the results of trace analysis as state intervals: <key, t_{start}, t_{end}, value>. This State History Tree (SHT) is a tree for which each node is mapped to a block on disk, such that each node has a fixed capacity to store intervals and is defined by a time range that must be included in its parent's range and must not overlap with its siblings' ranges. This structure was demonstrated to be more efficient that other, generic solutions, but could still degenerate for corner cases with many keys, from traces with many threads for example. The tree's depth would then be proportional to the number of threads and many empty nodes would be written to disk, wasting space. Moreover, queries to extract data from the data structure were often the bottleneck for displaying data. In this work, we analyse the limitations of the current database which cause it to degenerate and study the different use cases for queries. We suggest structural changes to the data structure, which eliminate the corner case behavior for traces with many attributes, while reducing the disk usage for all types of traces. We also add meta data to the nodes to reduce the number of nodes searched during queries, speeding them up by 50%. Then, we look into optimizing the nodes into which intervals are inserted, so that those which will be queried together will be grouped. This helps to reduce the number of disk blocks that must be read to answer the query. The number of intervals and nodes taken into account by the optimization process can increase along with the number of attributes, as they are the main cause of query slowdown. This helps to balance the extra time required for the optimized insertion and the gains provided on the queries. We also introduce a new type of query to benefit from these optimizations and return all desired intervals in a single query instead of the many queries previously required. This single query reads each node at most once, while the previous version with many queries would read some nodes several times. We show that using this query for one of the main views in the trace visualization software makes it considerably more reactive. We benefit from all these lessons learned to increase the scalability of another internal backend, the segment store, used for the following type of objects: <t_{start}, t_{end}, value>. These were previously stored in memory, which would strongly limit the maximum capacity. We propose a new tree structure similar to the SHT instead. We show that the disk based structure is, in the worst case, only an order of magnitude slower for reads than the in-memory structures. Moreover, this structure is especially efficient for a typical segment store use case, which is a sorted segment query. Indeed by using partial sorts between nodes, memory usage is dramatically reduced compared to sorting all segments in memory.