On Line Trace Synchronization for Large Scale Distributed Systems

Les systèmes distribués en réseau fournissent une plate-forme informatique polyvalente pour soutenir diverses applications, telles que des algorithmes de routage dans les réseaux de télécommunication, les systèmes bancaires dans les applications de réseau, les systèmes de contrôle d'aéronefs dans le contrôle de processus en temps réel, ou le calcul scientifique, y compris les grilles et grappes de calcul en calcul parallèle. Ces systèmes sont généralement supervisés afin de détecter, de déboguer et d'éviter les problèmes de sécurité ou de performance. Un outil de traçage est une des méthodes les plus efficaces et précises, avec laquelle toutes les informations détaillées pour chaque noeud individuel dans le système peuvent être extraites et étudiées. Typiquement, une tâche énorme est divisée en de nombreuses tâches, qui sont distribuées et exécutées sur plusieurs ordinateurs coopérant en réseau. Ainsi, afin de contrôler la fonctionnalité des systèmes distribués actuels, toutes les informations sont collectées à partir de plusieurs systèmes et appareils embarqués pour une analyse et une visualisation à la fois en ligne et hors ligne. Cette information de traçage, générée à un rythme effarant, est livrée avec estampilles de temps générées localement sur chaque noeud. Ces estampilles sont généralement fondées sur des compteurs de cycle, avec une granularité du niveau de la nanoseconde. Toutefois, les horloges de chaque noeud sont indépendantes et donc asynchrones les unes des autres. Néanmoins, les utilisateurs s'attendent à voir la sortie de l'analyse en temps réel, sur un axe de référence de temps commun, afin d'être en mesure de diagnostiquer les problèmes plus facilement. La portée de l'oeuvre proposée ici est la synchronisation efficace et en direct de traces générées dans un environnement de grande grappe d'ordinateurs avec des estampilles de temps de granularité du niveau de la nanoseconde, produites par des horloges non synchronisées. Par ailleurs, le modèle de trafic du réseau, le nombre de noeuds informatiques disponibles et même la topologie du réseau peuvent changer. En effet, les grands centres de données roulent un ensemble diversifié et en constante évolution d'applications. Les noeuds peuvent échouer ou revenir en ligne à tout moment, et même le réseau peut être reconfiguré dynamiquement. Ainsi, motivé par la grande échelle des systèmes ciblés, le volume élevé de flux de traces de données associés, la limitation des tampons mémoire et la nécessité d'une analyse en direct, et la haute précision de synchronisation requise, nous avons conçu une nouvelle approche incrémentale pour synchroniser les traces de plusieurs ordinateurs connectés à un réseau dynamique à grande échelle. Tout d'abord, nous présentons une nouvelle technique de synchronisation en direct des connexions individuelles basée sur la classification rapide des paquets échangés, soit comme des paquets précis ou des paquets inintéressants. Cette méthode permet d'obtenir à la fois le plus bas coût de calcul, une latence minimale et une meilleure précision. Deuxièmement, nous avons proposé un algorithme efficace pour calculer incrémentalement l'arbre couvrant minimum des liaisons réseau avec la meilleure précision (plus faible inexactitude) afin de permettre le calcul efficace de paramètres de synchronisation transitive entre deux noeuds qui ne sont pas connectés directement. Ce problème est un défi multiple puisque l'exactitude des liens change au fur et à mesure que des paquets sont échangés entre deux noeuds, de nouveaux liens peuvent apparaître lorsque les noeuds commencent à échanger des paquets, et de nouveaux noeuds peuvent aussi apparaître. Enfin, nous avons proposé un nouvel algorithme pour identifier efficacement et mettre à jour le noeud de référence optimal dans l'arbre couvrant minimum, afin d'utiliser ce noeud comme référence de temps pour l'analyse et la visualisation des traces de plusieurs noeuds. En résumé, nous avons conçu et mis en oeuvre une nouvelle procédure efficace et complète pour la synchronisation de trace optimale, dans un environnement de très grande grappe d'ordinateurs, en direct. Le Linux Trace Toolkit next generation (LTTng), développé à l'École Polytechnique de Montréal, offre une trace d'exécution détaillée des systèmes Linux avec faible surcharge. Notre nouvelle procédure a été programmée et validée par la synchronisation en ligne d'énormes traces LTTng dans de grands réseaux dynamiques.

Abstract

Networked distributed systems provide a versatile computing platform for supporting various applications, such as routing algorithms in telecommunication networks, banking systems in network applications, aircraft control systems in real-time process control, or scientific computing including cluster and grid computing in parallel computation. These systems are typically monitored to detect, debug and avoid security or performance problems. A tracing tool is one of the most efficient and precise methods, in which all the detailed information for every individual node in the system can be extracted and studied. Typically, a particular huge task is divided into many tasks, which are distributed and run on several cooperating networked computers. Hence, in order to monitor the functionality of current distributed systems, all information is collected, from multiple systems and embedded devices, for both online and a posteriori offline analysis and viewing. This tracing information, generated at a staggering rate, comes with timestamps locally generated on each node. These timestamps are typically based on cycle counters, with a nanosecond level granularity. However, the clocks in each node are independent and thus asynchronous from one another. Nonetheless, users expect to see the analysis output in real-time, on a common time reference axis, in order to be able to diagnose problems more easily. The scope of the work proposed here is the efficient and live synchronization of traces generated in distributed systems with nanosecond granularity timestamps produced by unsynchronized clocks. Moreover, the pattern of network traffic, the number of available computer nodes and even the network topology can change. Indeed, distributed systems run a diverse and changing set of applications, nodes may fail or come back online at any time, and even the network can be reconfigured dynamically. Thus, motivated by the large scale of targeted systems, the high volume of associated trace data streams, the data buffering limitations, and the need for live analysis and high synchronization precision, we designed a new incremental approach to synchronize traces from multiple connected computers in a large scale dynamic network. First, we present a novel schema for live synchronization of individual connections based on the fast classification of exchanged packets as either accurate packets or uninteresting packets. This method achieves at the same time the lowest computing cost, lowest latency and best accuracy. Secondly, we proposed an efficient algorithm to incrementally compute the minimum spanning tree of network links with the best precision (lowest inaccuracy) in order to allow the efficient computation of synchronization parameters transitively between two nodes which are not connected directly. This problem is a multiple challenge since the accuracy of links changes as more packets are exchanged between two nodes, new links may appear when nodes start exchanging packets, and new nodes may appear as well. Finally, we proposed a new algorithm to efficiently identify and update the optimal reference node in the minimum spanning tree, in order to use this node as time reference when analyzing and visualizing traces from multiple nodes. In summary, we designed and implemented a new efficient procedure for optimum trace synchronization in a live distributed systems. The Linux Trace Toolkit next generation (LTTng), developed at Polytechnique Montreal, provides a detailed execution trace of Linux systems with low overhead. Our new procedure was programmed and validated through the online synchronization of huge LTTng traces in large dynamic networks.