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.