Analyse de variations de performance par comparaison de traces d'exécution

La performance est un requis très important pour bon nombre d'applications. Malheureusement, plusieurs facteurs affectent cette performance : contention pour l'accès à une ressource, mauvais algorithmes de synchronisation, attente de données en provenance du disque, etc. En raison de la taille du code source de certaines applications et des multiples niveaux d'abstraction entre le code applicatif et le matériel, plusieurs développeurs ne soupçonnent pas l'existence de toutes ces sources de latence. Le traçage est une technique qui consiste à enregistrer des événements qui surviennent dans un système informatique. Un grand nombre de problèmes de performance peuvent être diagnostiqués à partir de l'information contenue dans une trace d'exécution. En raison de leur faible surcoût, les traceurs modernes peuvent être activés en continu sur des systèmes en production pour capturer des problèmes survenant rarement. Des outils spécialisés facilitent la navigation à travers le grand nombre d'événements contenus une trace d'exécution. Malheureusement, même avec ces outils, il peut être difficile de juger si le comportement observé est celui attendu sans une connaissance exhaustive du système analysé. L'objectif de ce travail de recherche est de vérifier si le diagnostic de variations de performance peut être facilité par un algorithme qui identifie automatiquement les différences entre deux groupes de traces d'exécution. L'algorithme doit mettre en évidence les latences présentes dans un groupe d'exécutions anormalement longues, mais pas dans un groupe d'exécutions normales. Un développeur peut alors tenter d'éliminer ces latences. Pour ce faire, nous introduisons d'abord deux nouveaux événements pour le traceur LTTng. L'événement cpu_stack rapporte périodiquement la pile d'appels des fils d'exécution utilisant le processeur. L'événement syscall_stack rapporte la pile d'appels des longs appels système. Ces deux événements nous permettent de déterminer si des latences présentes dans des traces d'exécution différentes ont été causées par le même code applicatif. Le traçage de l'événement syscall_stack a un surcoût moindre que celui du traçage traditionnel des appels système. Nous proposons aussi une nouvelle structure de données appelée « enhanced calling context tree » (ECCT) pour représenter les latences affectant le temps de complétion d'une tâche. Ces latences peuvent être au niveau du matériel, du système d'exploitation ou du code applicatif. En présence d'interactions entre plusieurs fils d'exécution, nous utilisons un algorithme de calcul du chemin critique pour inclure dans le ECCT les latences introduites par chacun de ces fils. Nous utilisons les ECCTs à la fois pour stocker des métriques de performance de façon compacte et comme entrée de notre algorithme de comparaison. Ensuite, nous présentons une interface graphique permettant de visualiser les différences entre des groupes d'exécution. Les groupes à comparer sont définis par l'utilisateur à l'aide de filtres. Les différences sont montrées à l'aide d'un outil de visualisation appelé « flame graph » différentiels ainsi que d'histogrammes. Les vues sont rafraîchies rapidement lorsque les filtres sont modifiés grâce à un algorithme de « map-reduce ». L'efficacité de notre solution pour détecter, diagnostiquer et corriger des problèmes de performance majeurs est démontrée grâce à quatre études de cas menées sur des logiciels libres et d'entreprises. Nous mesurons aussi le surcoût du traçage des événements requis par notre analyse sur différents types d'applications et concluons qu'il est toujours entre 0.2% et 9%. Enfin, nous démontrons que notre solution développée pour Linux peut être adaptée pour fonctionner sur les systèmes d'exploitation Windows et Mac OS X.

Abstract

Performance is a critical requirement for many applications. Unfortunately, many factors can affect performance: resource contention, bad synchronization algorithms, slow disk operations, etc. Because of the large codebase of some applications and because of the multiple levels of abstraction between application code and hardware, many developers are not aware of the existence of these sources of latency. Tracing is a technique that consists of recording events that occur in a system. Many performance problems can be diagnosed using the information contained in an execution trace. Popular tracers achieve low overhead, which allows them to be enabled on production systems to capture bugs that occur infrequently. Specialized tools allow efficient navigation in the large number of events contained in execution traces. However, even with these tools, it is hard to determine whether the observed behavior is normal without a deep knowledge of the analyzed system. The objective of this research project is to verify whether we can facilitate the diagnosis of performance variations with an algorithm that automatically identifies differences between two groups of execution traces. The algorithm must highlight delays that appear in a group of slow executions, but not in a group of normal executions. A developer can then try to eliminate these delays. First, we introduce two new events for the LTTng tracer. The cpu_stack event periodically reports the call stack of threads running on the CPU. The syscall_stack reports the call stack of long system calls. Call stacks allow us to determine whether delays that appear in different execution traces are caused by the same application code. The overhead of tracing the syscall_stack event is less than that of traditional tracing of system calls. Second, we propose a new data structure called enhanced calling context tree (ECCT) to describe delays that affect the completion time of a task execution. These delays can be at the hardware, operating system or application levels. When a task execution involves interactions between several threads, a critical path algorithm is used to include delays caused by each of them in the ECCT. We use ECCTs to store performance metrics compactly and as an input to our comparison algorithm. Third, we present a GUI that shows differences between groups of executions. The user defines two groups of executions to compare using filters. Differences are shown using a visualization tool called differential flame graph along with histograms. A map-reduce algorithm is used to quickly refresh the views when filters are modified. We present four case studies, carried on open-source and enterprise software, to demonstrate that our solution helps to detect, diagnose and fix major performance problems. We measure the overhead of tracing the events required by our analysis on different kinds of applications and conclude that it is always between 0.2% and 9%. Finally, we show that our solution, developed for Linux, can be adapted for the Windows and Mac OS X operating systems.