Synchronisation de traces distribuées à l'aide d'événements de bas niveau

Le traçage d'événement a prouvé son efficacité dans l'identification de problèmes de fonctionnalité et de performance. Il peut s'appliquer dans le développement d'applications, de systèmes d'exploitation et de pilotes matériels. Pour l'appliquer également à des systèmes distribués, il est possible d'enregistrer des traces individuellement sur chaque noeud puis de regrouper ces traces lors de l'analyse a posteriori. Il faut alors que les estampilles de temps associées aux événements soient synchronisées avec fidélité et justesse. Ce mémoire traite de la synchronisation hors ligne de groupes de traces enregistrées sur un système distribué. L'objectif est d'identifier un algorithme de synchronisation de trace précis, qui s'exécute en temps linéaire par rapport au nombre d'événements dans le groupe de traces, qui garantit l'absence d'inversion de message et qui peut déterminer des bornes sur la justesse. Dans l'approche préconisée, le traçage noyau enregistre avec une faible intrusivité des événements correspondant à l'envoi et la réception de messages réseau. Les relations d'ordre entre ces événements sont utilisées pour construire une base de temps globale. L'approche se concentre sur la synchronisation de paires de traces à l'aide de fonctions linéaires de correction d'horloge. Les paramètres de ces fonctions sont identifiés à l'aide de l'algorithme basé sur la méthode des enveloppes convexes. Cet algorithme garantit l'absence d'inversion de message et il a été étendu afin de déterminer des bornes sur la justesse à tout moment lors du traçage. L'algorithme a été intégré à un outil de visualisation de trace. Son application à des traces réelles, variées et de grandes tailles révèle que la précision de la synchronisation est favorisée par l'utilisation d'un réseau à plus faible latence ou d'un débit de message plus élevé. En contrepartie, une durée de traçage plus longue réduit la précision et fausse la détermination des bornes de justesse. Cette situation est mise en évidence grâce à l'utilisation de métriques sur les temps de transfert des messages après synchronisation. L'étude de la performance de l'algorithme confirme qu'il peut réaliser la synchronisation avec un ordre d'exécution linéaire. La détermination des bornes de justesse a un comportement quadratique dans le pire des cas, mais, avec des traces réelles, elle s'exécute en temps presque linéaire. Lors de nos expériences, nous avons atteint une justesse de ±15 us et une précision estimée à 9 us sur un réseau comportant une latence minimale estimée à 39 us. La détermination de bornes sur la justesse de la synchronisation représente une avancée scientifique alors que l'implantation efficace de l'algorithme de synchronisation dans un système de traçage pratique représente une avancée technique.

Abstract

Event tracing has proven to be a valuable tool for identifying functional and performance problems. It has helped to identify problems at the application, operating system and device driver level. In order to extend its benefits to distributed systems, one approach is to record traces individually on each node and to analyze them in a post-processing step. In order for this to be meaningful, the timestamps in the traces have to be synchronized with precision and accuracy. This dissertation focuses on offline synchronization of traces recorded on distributed systems. The objective is to identify a trace synchronization algorithm that is precise, has a linear run time order in regards to the number of events in the traces, that can guarantee the absence of message inversions and identify accuracy bounds. The method put forward uses kernel tracing to record network events with a low intrusiveness. A global timebase is built by analyzing the strict ordering relationships between events that correspond to the emission and reception of messages. We concentrate on the synchronization of pair of traces using linear clock correction functions. The parameters of these functions are identified using the convex hull algorithm. It guarantees the absence of message inversions and it has been extended to identify accuracy bounds at any point in the tracing interval. This algorithm was contributed to a trace analysis tool and was used on a variety of long running and large traces recorded on real systems. The experiments conducted show that offline synchronization accuracy is improved by using a network with lower latency and by using a higher message rate. With a constant message rate, lengthening the trace duration reduces precision and gives a false impression of improving accuracy. This is detected using metrics based on message propagation delays after synchronization. Synchronization factors can be found in linear time. The time to find accuracy bounds is quadratic in the worst case but it scales almost linearly on practical traces. During our experiments, we have achieved a synchronization accuracy of ±15 us and an estimated precision of 9 us on a network with an estimated minimum propagation delay of 39 us. Identifying strict accuracy bounds during offline synchronization of traces represents a scientific advance whereas the efficient implementation of a trace synchronization algorithm in a practical tool represents a technical progress.