Groupement de clés efficace pour un équilibrage de charge quasi-optimal dans les systèmes de traitement de flux

International audience; Key grouping is a technique used by stream processing frame- works to simplify the development of parallel stateful opera- tors. Through key grouping a stream of tuples is partitioned in several disjoint sub-streams depending on the values con- tained in the tuples themselves. Each operator instance tar- get of one sub-stream is guaranteed to receive all the tuples containing a specific key value. A common solution to imple- ment key grouping is through hash functions that, however, are known to cause load imbalances on the target operator instances when the input data stream is characterized by a skewed value distribution. In this paper we present DKG, a novel approach to key grouping that provides near-optimal load distribution for input streams with skewed value distri- bution. DKG starts from the simple observation that with such inputs the load balance is strongly driven by the most frequent values; it identifies such values and explicitly maps them to sub-streams together with groups of less frequent items to achieve a near-optimal load balance. We provide theoretical approximation bounds for the quality of the map- ping derived by DKG and show, through both simulations and a running prototype, its impact on stream processing applications.; Le groupement de clés est une technique utilisée dans les plateformes de traitement de flux pour simplifier le dé-ploiement parallèle d'opérateurs à états. Cette méthode consiste à subdiviser le flux de tuples en plusieurs sous-flux disjoints, au regard d'une clef définie pour chaque tuple. Chaque opérateur recevant l'un de ces sous-flux est donc as-suré de recevoir tous les tuples contenant une clé spécifique. Une solution classique est de grouper les clés en utilisant des fonctions de hachage, induisant potentiellement un déséquilibre de charge des opérateurs en cas de distribution bi-aisée des clefs du flux d'entrée. Nous présentons une solution permettant d'obtenir une répartition de la charge proche de l'optimal, quelque soit la distribution. Cette solution repose sur le fait que l'équilibre est majoritairement influencé par les clés les plus fréquentes. En identifiant ces valeurs dominantes et en les groupant judicieusement avec des clés plus rares, les sous-flux ainsi obtenus permettent d'atteindre un équilibrage de charge quasi-optimal. Nous présentons une analyse théorique des bornes de qualité obtenu avec notre algorithme et illustrons son impact sur des applications de traitement de flux, via des simulations intensives et un prototype opérationnel.