Quality of Service Aware Mechanisms for (Re)Configuring Data Stream Processing Applications on Highly Distributed Infrastructure
Mécanismes prenant en compte la qualité de service pour la (re)configuration d’applications de traitement de flux de données sur une infrastructure hautement distribuée
Abstract
There is an increasing demand for handling massive amounts of data in a timely manner via Distributed Stream Processing (DSP). A DSP application is often structured as a directed graph whose vertices are operators that perform transformations over the incoming data and edges representing the data streams between operators. DSP applications are traditionally deployed on the cloud to explore the virtually unlimited number of resources. Edge computing has emerged as a suitable paradigm for executing parts of DSP applications by offloading certain operators from the cloud and placing them close to where the data is generated (i.e., highly distributed infrastructure), hence minimising the overall time required to process data events (i.e., the end-to-end latency). The task of scheduling DSP operators on highly distributed infrastructure with heterogeneous resources is generally referred to as application configuration and has proven to be NP-hard. We introduce a set of strategies to place operators onto cloud and edge while considering characteristics of resources and meeting the requirements of applications. In particular, we first decompose the application graph by identifying behaviours such as forks and joins, and then dynamically split the dataflow graph across the edge and cloud. Comprehensive simulations and a real testbed considering multiple application settings demonstrate that the strategies can improve the end-to-end latency in over 50% and even other QoS metrics. As DSP applications are long-running, the load and infrastructure conditions can change during their execution. The application reconfiguration consists of changing the initial placement by reassigning operators to different devices given target performance metrics, variable application workload or device failures. We model the operator reconfiguration as a Reinforcement Learning (RL) problem and define a multi-objective reward considering metrics regarding operator reconfiguration, and infrastructure and application improvement. Experimental results show that reconfiguration algorithms that minimise only end-to-end processing latency can have a substantial impact on WAN traffic and communication cost. The results also demonstrate that when reconfiguring operators, RL algorithms improve by over 50% the performance of the initial placement provided by state-of-the-art approaches.
La déploiement massif de capteurs, de téléphones mobiles et d'autres appareils a entraîné une explosion du volume, de la variété et de la vitesse des données générées (messages, événements, tuplets), et qui nécessitent d'être analysées. Notre société devient de plus en plus interconnectée et produit de grandes quantités de données provenant des processus métier instrumentés, de la surveillance de l'activité des utilisateurs, des objets connectés et assistants portables, des capteurs, des processus financiers, des systèmes à large échelle, d'expériences scientifiques, entre autres. Ce déluge de données est souvent qualifié de big data en raison des problèmes qu'il pose aux infrastructures existantes en matière de transfert, de stockage et de traitement de données. Une grande partie de ces données volumineuses ont plus de valeur lorsqu'elles sont analysées rapidement, au fur et à mesure de leur génération. Dans plusieurs scénarios d'application émergents, tels que les villes intelligentes, la surveillance opérationnelle de grandes infrastructures et l'Internet des Objets (IoT, Internet of Things), des flux continus de données doivent être traités dans des délais très brefs. Dans plusieurs domaines, ce traitement est nécessaire pour détecter des modèles, identifier des défaillances et pour guider la prise de decision. Les données sont donc souvent rassemblées et analysées par des environnements logiciels conçus pour le traitement de flux continus de données. Ces environnements logiciels pour le traitement de flux de données déploient les applications sous-la forme d'un graphe orienté ou de dataflow. Un dataflow contient une ou plusieurs sources (i.e. capteurs, passerelles ou actionneurs); opérateurs qui effectuent des transformations sur les données (e.g., filtrage et agrégation); et des sinks (i.e., éviers qui consomment les requêtes ou stockent les données). La plupart des transformations effectuées par les opérateurs complexes -- appelées aussi opérateurs avec état -- stockent des informations en mémoire entre les executions. Un flux de données peut également avoir des opérateurs sans état qui prennent en compte uniquement les données requises par l'exécution actuelle. Traditionnellement, les applications de traitement de flux de données ont été conçues pour fonctionner sur des grappes de ressources homogènes (i.e., cluster computing) ou sur le cloud. Dans un déploiement cloud, l'application entière est placée sur un seul fournisseur cloud pour que l’application puisse bénéficier d’un nombre virtuellement infini de ressources. Cette approche permet aux applications élastiques de traitement de flux de données d'allouer des ressources supplémentaires ou de libérer une capacité inactive à la demande pendant l'exécution d'une application, afin de répondre dynamiquement aux besoins. Dans de nombreux scénarios, l'élasticité des nuages ne suffit pas à respecter les contraintes de temps du traitement de flux de données en raison de l'emplacement des sources de données et des changements lors du cycle de vie de l'application. Dans les scénarios IoT, les sources de données sont principalement situées aux extrémités de l'Internet et les données sont transférées vers le cloud par des liens longue distance, ce qui augmente la latence de bout en bout des applications, aussi appelé temps de réponse; c'est à dire, la différence entre le temps où les données sont générées jusqu'au moment où elles atteignent les sinks). La surcharge de communication liée au transfert de données par des liens Internet à haute latence rend impossible le traitement en temps quasi réel sur des architectures composées uniquement de clouds. Une infrastructure cloud souvent utilisée pour les scénarios IoT -- appelée ici infrastructure massivement distribuée – est celle où les données sont produites en permanence par plusieurs capteurs et contrôleurs, puis transmises à des passerelles, des commutateurs ou des concentrateurs situés à la périphérie du réseau et finalement traitées dans dans les noeuds de calcul des centres de calcul et données. Une infrastructure edge en périphérie comprend généralement des périphériques avec des capacités de mémoire et de processeur faibles, mais non négligeables, regroupés en fonction de leur emplacement ou de la latence du réseau. Un groupe de périphérie peut transférer des données vers un autre groupe ou vers le cloud, et le canal utilisé pour la communication est souvent l'Internet. Plus récemment, des environnements logiciels et des architectures ont été proposés pour le traitement de flux de données sur des infrastructures hautement distribuées afin d'améliorer l'évolutivité et les latences de bout en bout des applications. Les ressources périphériques, souvent appelés edge computing, peuvent être exploités pour compléter les capacités informatiques du cloud et réduire la latence de bout en bout globale des applications, leurs besoins en bande passante et d'autres mesures de performances. L'exploration d'une telle infrastructure permet d'utiliser plusieurs modèles de performance et de minimiser les coûts liés à l'exécution de traitement de flux de données. L'utilisation d'une infrastructure cloud présente des défis supplémentaires en matière de planification des applications, d'élasticité des ressources et de modèles de programmation. La tâche de planification ou de configuration des opérateurs de traitement de flux de données sur une infrastructure hautement distribuée avec des ressources hétérogènes est généralement appelée placement d'opérateur, et s'est révélée être NP-difficile. Déterminer comment déployer les opérateurs ou les migrer du cloud aux ressources périphériques du type edge computing est également un défi en raison des limitations des périphériques (en termes de mémoire, processeur, bande passante réseau) et du réseau (i.e., Internet). Les applications de traitement de flux de données ont une longue durée de fonctionnement pendant laquelle les conditions de charge et d’infrastructure peuvent changer. Après leur placement, il peut être nécessaire de réaffecter des opérateurs en raison de charges de travail variables ou de défaillances de périphériques. Le processus de réorganisation ou de migration des opérateurs d’une application de traitement de flux de données sur des ressources de calcul est appelé ici reconfiguration. Cette reconfiguration et le choix des opérateurs à réaffecter sont également NP-difficile. L'espace de recherche de solution permettant de déterminer le placement des opérateurs de traitement de flux de données ou leur reconfiguration peut être énorme en fonction du nombre d'opérateurs, de flux, de ressources et de liens réseau. Le problème devient encore plus complexe lorsqu’on considère plusieurs métriques de qualité de service, par exemple, la latence de bout en bout, le volume de trafic utilisant des liens réseau edge-cloud, le coût monétaire lié au déploiement de l'application et la surcharge liée à la sauvegarde de l'application. À mesure que l'infrastructure et les applications cloud prennent de l'ampleur, essayer de concevoir un plan de (re)configuration tout en optimisant plusieurs objectifs peut entrainer un espace de recherche plus consequent. Nous proposons dans cette thèse un ensemble de stratégies pour placer les opérateurs dans une infrastructure massivement distribuée cloud-edge en tenant compte des caractéristiques des ressources et des exigences des applications. En particulier, nous décomposons tout d'abord le graphe d'application en identifiant quelques comportements tels que des forks et des joints, puis nous le plaçons dynamiquement sur l'infrastructure. Des simulations et un prototype prenant en compte plusieurs paramètres d'application démontrent que notre approche peut réduire la latence de bout en bout de plus de 50% et aussi améliorer d'autres métriques de qualité de service. L'espace de recherche de solutions pour la reconfiguration des opérateurs peut être énorme en fonction du nombre d'opérateurs, de flux, de ressources et de liens réseau. De plus, il est important de minimiser le coût de la migration tout en améliorant la latence. Des travaux antérieurs, Reinforcement Learning (RL) et Monte-Carlo Tree Search (MCTS) ont été utilisés pour résoudre les problèmes liés aux grands nombres d’actions et d’états de recherche. Nous modélisons le problème de reconfiguration d'applications sous la forme d'un processus de décision de Markov (MDP) et étudions l'utilisation des algorithmes RL et MCTS pour concevoir des plans de reconfiguration améliorant plusieurs métriques de qualité de service. Les principales contributions de cette thèse sont énumérées ci-dessous:
* Une exploration de l’élasticité des applications de traitement de flux de données et le placement d’opérateurs d’application de traitement de flux de données dans des infrastructures hétérogènes;
* Un modèle décrivant le calcul et les services de communication en se concentrant sur le temps de latence de bout en bout, ainsi que sur les contraintes de ressources en matière d'application et de calcul;
* Des stratégies de configuration des applications de traitement de flux de données prenant en compte l'optimisation mono et multi-objectifs;
* Une modélisation MDP utilisée par les algorithmes RL en considérant l’optimisation d’un ou de plusieurs objectifs pour reconfigurer les applications de traitement de flux de données.
Origin : Files produced by the author(s)
Loading...