Ordonnancement dynamique pour un équilibrage de charge quasi-optimal dans les systèmes de traitement de flux

La repartition de la charge sur les operateurs sans etat parallelise dans un systeme de traitement de flux repose principalement sur le groupement aleatoire des tuples. Chacun de ces derniers peut etre assigne a n'importe quelle instance disponible de l'operateur considere, independamment des assignations precedentes. L'approche classique consiste a transmettre a tour de role les tuples aux differentes instances paralleles existantes. Cette politique convient bien tant que le temps d'execution de tous les tuples est plus ou moins le meme. Cette hypothese est cependant rarement verifiee en pratique, ou les temps d'execution reposent principalement sur le contenu des tuples, et peut causer un desequilibre imprevisible menant in fine a un accroissement indesirable des temps d'execution et potentiellement a la defaillance du systeme. Dans cet article, nous proposons Online Shuffle Grouping (OSG), une solution de groupement permettant de reduire le temps d'execution global des tuples. OSG commence par estimer, par l'utilisation d'agregats, la duree d'execution de chaque tuple, avec des taux d'erreur d'approximation faibles et bornes, lui permettant d'effectuer un ordonnancement pro-actif en temps-reel. Nous proposons une analyse probabiliste de OSG et evaluons son impact sur des applications de traitement de flux, en terme de robustesse et de fiabilite, par une large experimentation sur la plateforme Microsoft Azure.