Ordonnancement dynamique pour un équilibrage de charge quasi-optimal dans les systèmes de traitement de flux
Abstract
La répartition de la charge sur les opérateurs sans état parallélisé dans un système de traitement de flux repose principalement sur le groupement aléatoire des tuples. Chacun de ces derniers peut être assigné à n'importe quelle instance disponible de l'opérateur considéré, indépendamment des assignations précédentes. L'approche classique consiste à transmettre à tour de rôle les tuples aux différentes instances parallèles existantes. Cette politique convient bien tant que le temps d'exécution de tous les tuples est plus ou moins le même. Cette hypothèse est cependant rarement vérifiée en pratique, où les temps d'exécution reposent principalement sur le contenu des tuples, et peut causer un déséquilibre imprévisible menant in fine à un accroissement indésirable des temps d'exécution et potentiellement à la défaillance du système. Dans cet article, nous proposons Online Shuffle Grouping (OSG), une solution de groupement permettant de réduire le temps d'exécution global des tuples. OSG commence par estimer, par l'utilisation d'agrégats, la durée d'exécution de chaque tuple, avec des taux d'erreur d'approximation faibles et bornés, lui permettant d'effectuer un ordonnancement pro-actif en temps-réel. Nous proposons une analyse probabiliste de OSG et évaluons son impact sur des applications de traitement de flux, en terme de robustesse et de fiabilité, par une large expérimentation sur la plateforme Microsoft Azure.
Origin : Files produced by the author(s)
Loading...