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

Voici quelques détails sur L'implémentation d'Hadoop pour Terasort :

TeraSort est un tri map/reduce standard, à l'exception d'un partitionneur personnalisé qui utilise une liste triée de N 1 clés échantillonnées qui définissent la plage de clés pour chaque reduce. En particulier, toutes les clés telles que sample[i 1] <= key < sample[i] sont envoyées à reduce i. Cela garantit que les sorties de reduce i sont toutes inférieures aux sorties de reduce i+1."

Leur astuce réside donc dans la façon dont ils déterminent les clés pendant la phase de cartographie. Essentiellement, ils s'assurent que chaque valeur dans un seul réducteur est garantie d'être "pré-triée" par rapport à tous les autres réducteurs.

J'ai trouvé la référence du papier par Blogue de James Hamilton .

Answer 2

Référence Google : MapReduce : Traitement simplifié des données sur les grands clusters

Apparu dans :
OSDI'04 : Sixième symposium sur la conception et la mise en œuvre des systèmes d'exploitation,
San Francisco, CA, décembre 2004.

Ce lien comporte une référence PDF et HTML-Slide.

Il existe également un Page Wikipedia avec description avec des références de mise en œuvre.

Critique également,

David DeWitt et Michael Stonebraker, experts pionniers en matière de bases de données parallèles et d'architectures à rien partagé, ont fait des affirmations controversées sur l'étendue des problèmes auxquels MapReduce peut être utilisé. Ils ont qualifié son interface de trop bas niveau et se sont demandé si elle représentait vraiment le changement de paradigme que ses partisans prétendent. Ils contestent les affirmations de nouveauté des partisans de MapReduce, citant Teradata comme exemple d'art antérieur existant depuis plus de vingt ans ; ils ont comparé les programmeurs de MapReduce aux programmeurs de Codasyl, notant que tous deux "écrivent dans un langage de bas niveau en effectuant une manipulation d'enregistrement de bas niveau". L'utilisation par MapReduce de fichiers d'entrée et l'absence de prise en charge des schémas empêchent les améliorations de performances permises par les fonctionnalités courantes des systèmes de bases de données telles que les arbres B et le partitionnement de hachage, bien que des projets tels que PigLatin et Sawzall commencent à s'attaquer à ces problèmes.

Answer 3

• Description avec chiffres - http://www.slideshare.net/tungld/terasort
• Code - http://grepcode.com/file/repository.cloudera.com/content/repositories/releases/com.cloudera.hadoop/hadoop-examples/0.20.2-320/org/apache/hadoop/examples/terasort/TeraSort.java?av=f

Answer 4

Je me suis posé la même question en lisant le document de Google sur MapReduce. @Yuval F 's réponse a à peu près résolu mon puzzle.

Une chose que j'ai remarquée en lisant l'article est que la magie se produit dans le partitionnement (après la carte, avant la réduction).

Le document utilise hash(key) mod R comme exemple de partitionnement, mais ce n'est pas la seule façon de partitionner des données intermédiaires pour différentes tâches de réduction.

Il suffit d'ajouter des conditions limites à @Yuval F 's réponse pour le rendre complet : supposons que min(S) et max(S) sont la clé minimale et la clé maximale parmi les clés échantillonnées ; toutes les clés < min(S) sont partitionnées à une tâche de réduction ; vice versa, toutes les clés >= max(S) sont partitionnées à une tâche de réduction.

Il n'y a pas de limite stricte sur les clés échantillonnées, comme min ou max. Simplement, plus ces clés R sont réparties uniformément parmi toutes les clés, plus le système distribué est "parallèle" et moins l'opérateur de réduction risque d'avoir un problème de dépassement de mémoire.

Answer 5

Juste une supposition...

Si l'on dispose d'un énorme ensemble de données, on peut les partitionner en plusieurs parties à traiter en parallèle (peut-être par numéro d'enregistrement, c'est-à-dire enregistrement 1 - 1000 = partition 1, et ainsi de suite).

Assignez / planifiez chaque partition à un nœud particulier du cluster.

Chaque nœud de cluster divise ensuite (mappe) la partition en sa propre mini partition, peut-être par ordre alphabétique des clés. Ainsi, dans la partition 1, récupérez toutes les choses qui commencent par A et sortez-les dans la mini partition A de x. Créez un nouveau A(x) s'il existe déjà un A(x). Remplacer x par un numéro séquentiel (c'est peut-être le travail de l'ordonnanceur de le faire). C'est-à-dire, donnez-moi l'identifiant unique du prochain A(x).

Transmettre (planifier) les tâches effectuées par le mappeur (étape précédente) aux nœuds du cluster "reduce". Le cluster de nœuds de réduction affinera ensuite le tri de chaque partie de A(x), ce qui ne se produira que lorsque toutes les tâches du mappeur seront terminées (on ne peut pas commencer à trier tous les mots commençant par A alors qu'il est toujours possible qu'il y ait une autre mini partition A en cours). Sortir le résultat dans la partie triée finale (i.e. Trié-A, Trié-B, etc.).

Une fois cela fait, combinez à nouveau la partition triée en un seul ensemble de données. À ce stade, il s'agit d'une simple concaténation de n fichiers (où n pourrait être 26 si vous ne faites que A - Z), etc.

Il pourrait y avoir des étapes intermédiaires entre les deux... Je ne suis pas sûr :). C'est-à-dire d'autres map et reduce après l'étape initiale de reduce.