Parallelism, load balancing and scalability in BigData computing
Parallélisme, équilibrage de charges et extensibilité dans le traitement des mégadonnées sur des systèmes à grande échelle
Résumé
Over the past two decades, owing to the reduction of storage, exchange and data processing costs, the volume of data generated each year continues to explode. The challenges related to big data processing are often described by the 3Vs : volume, variety and velocity of data creation, analysis, and sharing. To store and analyze these large datasets, it is essential to use clusters of machines and scalable algorithms that are insensitive to load imbalance that may occur among processing nodes. Applications such as collaborative filtering, deduplication and entity resolution are necessary to identify relationships in big datasets relying on a notion of similarity between records. These applications enable finding users with similar tastes, cleaning data and detecting frauds in large datasets. In these cases, similarity join and similarity search operations are often used to retrieve all similar records in one or more datasets using a distance and a user-defined threshold. Although parallel joins have been widely studied and successfully implemented on parallel and distributed architectures, the algorithms are not suitable for similarity join operation, since there is no hashing or sorting techniques, in the literature, that can retrieve all potentially similar record pairs in one step. Many techniques have been introduced in the literature to reduce the search space while ensuring the completeness of the result and avoiding the computation of a Cartesian product and the comparison of all record pairs. However, the scalability of these techniques is limited and does not allow efficient processing of big datasets on large-scale systems. Approximate methods have been proposed to handle similarity join by ignoring a very small part of the result and providing a probabilistic guarantee on the completeness of the results, while reducing the search space. These methods rely on hash functions whose collision probabilities are sensitive to the objects' similarity. We rely on these techniques to propose efficient solutions for similarity join and similarity search processing, based on LSH (Locality Sensitive Hashing), distributed histograms, and randomized communication schemes in order to reduce processing time, communication, and disks I/O costs to only relevant data for various distances and objects. The aim is to propose a generic framework based on the MapReduce programming model that meets the challenges of volume, variety, and velocity of big data analysis.The efficiency and scalability of the proposed solutions were studied using a cost model and confirmed by a series of experiments measuring the result completeness and the reduction of the search space, while guaranteeing efficient similarity join processing regardless the data size and data skew, the distance and the user-defined thresholds.
Durant les deux dernières décennies, grâce à la réduction des coûts de stockage, d'échange et de traitement de l'information, le volume de données générées chaque année ne cesse d'exploser. Les enjeux liés au traitement de ces mégadonnées sont souvent décrits par la règle des 3V : le volume, la variété et la vitesse de création, de collecte, d'analyse et de partage des données. Pour stocker et analyser ces ensembles de données volumineux, il est essentiel d'utiliser des grappes de machines et des algorithmes extensibles et insensibles aux déséquilibres pouvant se produire pour répartir équitablement la charge sur l'ensemble des machines de traitement. Des applications telles que le filtrage collaboratif, la déduplication et la résolution d'entités sont nécessaires pour identifier des relations dans des mégadonnées en se reposant sur une notion de similarité entre les enregistrements. Ces applications permettent entre autres de retrouver des utilisateurs ayant des goûts similaires, de nettoyer les données et de détecter des fraudes. Dans ces cas, les opérations de jointure et de recherche par similarité sont utilisées pour retrouver tous les enregistrements similaires dans une ou plusieurs collections de données en utilisant une distance et un seuil défini par l'utilisateur. Bien que les équi-jointures parallèles aient été largement étudiées et mises en œuvre avec succès sur des architectures parallèles et distribuées, ces algorithmes ne sont pas adaptés à l'opération de jointure par similarité, car il n'y aucune technique de hachage ou de tri dans la littérature permettant de retrouver tous les couples d'enregistrements potentiellement similaires en une seule étape. Des techniques existent dans la littérature pour réduire l'espace de recherche tout en garantissant la complétude du résultat et en évitant le calcul d'un produit Cartésien et la comparaison de tous les couples d'enregistrements. Cependant, l'extensibilité de ces techniques est limitée et ne permet pas le traitement efficace de mégadonnées sur des systèmes à grandes échelles. Des méthodes approximatives ont été proposées pour traiter la jointure par similarité en renonçant à une petite partie du résultat et en fournissant une garantie probabiliste sur l'exhaustivité des résultats et permettant de réduire l'espace de recherche. Ces méthodes reposent sur des fonctions de hachages dont les probabilités de collisions sont sensibles à la similarité des objets. Nous nous reposons sur ces techniques pour proposer des solutions efficaces, pour le traitement de la jointure et de la recherche par similarité, basées sur l'utilisation de LSH (Locality Sensitive Hashing), d'histogrammes distribués et de schémas de communication randomisés dans le but de réduire les coûts de traitement, de communication et de lecture/écriture de données sur disques aux seules données pertinentes pour diverses distances et sur divers objets, et ce, dans le but de proposer un framework générique basé sur le modèle de programmation MapReduce répondant aux enjeux de volume, de variété et de vitesse d'analyse des données. L'efficacité et l'extensibilité des solutions proposées ont été étudiées en utilisant un modèle de coût et ont été confirmées par une série d'expériences mesurant également l'exhaustivité du résultat et la réduction de l'espace de recherche, garantissant ainsi une solution efficace quels que soient la taille, le déséquilibre des données en entrée, la distance et les seuils fournis par l'utilisateur.
| Origine | Version validée par le jury (STAR) |
|---|