Comment fonctionne l'algorithme de tri MapReduce ?

Question

L'un des principaux exemples utilisés pour démontrer la puissance de MapReduce est l'application Repère Terasort . J'ai du mal à comprendre les bases de l'algorithme de tri utilisé dans l'environnement MapReduce.

Pour moi, le tri consiste simplement à déterminer la position relative d'un élément par rapport à tous les autres éléments. Le tri consiste donc à comparer "tout" avec "tout". Votre algorithme de tri moyen (rapide, à bulles, ...) fait simplement cela de manière intelligente.

Dans mon esprit, diviser l'ensemble de données en plusieurs morceaux signifie que vous pouvez trier un seul morceau et qu'il vous reste à intégrer ces morceaux dans l'ensemble de données "complet" entièrement trié. Compte tenu du téraoctet de données réparti sur des milliers de systèmes, je m'attends à ce que ce soit une tâche énorme.

Comment cela se passe-t-il réellement ? Comment fonctionne cet algorithme de tri MapReduce ?

Merci de m'aider à comprendre.

Answer 1

Le tri est l'algorithme de base de MapReduce qui traite et analyse les données données. L'algorithme de tri est mis en œuvre par MapReduce pour trier les paires clé-valeur en sortie du mappeur en fonction de leurs clés.

Les méthodes de tri sont appliquées au sein de la classe mapper.

Dans la phase de triage, après la tokénisation des valeurs dans la classe de mappage, la classe définie par l'utilisateur (Contexte) obtient les clés valorisées correspondantes sous forme de collection.

La classe RawComparator aide la classe Mapper à collecter les paires clé-valeur similaires (clés intermédiaires) et à les trier.

Avant que les valeurs finales ne soient produites pour le réducteur, l'ensemble des paires clé-valeur intermédiaires pour un réducteur donné est automatiquement trié par Hadoop pour former des valeurs clés (K2, {V2, V2, }).