Comment fonctionne l'algorithme de tri MapReduce?

L'un des principaux exemples utilisés pour démontrer la puissance de MapReduce est le benchmark 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, bulle, ...) le fait simplement de manière intelligente.

Dans mon esprit, diviser l'ensemble de données en plusieurs éléments signifie que vous pouvez trier un seul élément, puis vous devez toujours intégrer ces éléments dans l'ensemble de données `` complet '' entièrement trié. Compte tenu de l'ensemble de données de téraoctets distribué sur des milliers de systèmes, je m'attends à ce que ce soit une tâche énorme.

Alors, comment est-ce vraiment fait? Comment fonctionne cet algorithme de tri MapReduce?

Merci de m'aider à comprendre.

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

TeraSort est un tri par mappage / réduction standard, sauf pour 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 réduction. En particulier, toutes les clés telles que sample [i - 1] <= key <sample [i] sont envoyées pour réduire i. Cela garantit que la sortie de la réduction i est inférieure à la sortie de la réduction i + 1. "

Leur astuce réside donc dans la manière dont ils déterminent les clés pendant la phase de carte. Essentiellement, ils garantissent que chaque valeur d'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 papier dans le blog de James Hamilton .

Référence Google: MapReduce: traitement simplifié des données sur de grands clusters

Apparu dans :
OSDI'04: Sixth Symposium on Operating System Design and Implementation,
San Francisco, Californie, décembre 2004.

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

Il y a aussi page Wikipédia avec une description avec des références d'implémentation.

Aussi critique,

David DeWitt et Michael Stonebraker, experts pionniers en bases de données parallèles et architectures sans partage, ont fait des affirmations controversées sur l'ampleur des problèmes pour lesquels 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étendaient être. Ils contestent les affirmations de nouveauté des partisans de MapReduce, citant Teradata comme un exemple de l'état de la technique qui existe depuis plus de deux décennies; ils ont comparé les programmeurs de MapReduce aux programmeurs de Codasyl, notant que les deux «écrivent dans un langage de bas niveau effectuant une manipulation d'enregistrements de bas niveau». L'utilisation de fichiers d'entrée par MapReduce et le manque de prise en charge des schémas empêchent les améliorations de performances permises par les fonctionnalités courantes du système de base de données telles que les arbres B et le partitionnement de hachage,

J'ai eu la même question en lisant l'article MapReduce de Google. @Yuval F de réponse à 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 de réduire).

Le papier utilise hash(key) mod R comme exemple de partitionnement, mais ce n'est pas le seul moyen de partitionner les données intermédiaires en différentes tâches de réduction.

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

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

Juste deviner ...

Étant donné un énorme ensemble de données, vous partitionneriez les données en quelques morceaux à traiter en parallèle (peut-être par numéro d'enregistrement, c'est-à-dire enregistrement 1 - 1000 = partition 1, et ainsi de suite).

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

Chaque nœud de cluster divisera (mappera) davantage la partition dans sa propre mini partition, peut-être par ordre alphabétique des clés. Donc, dans la partition 1, récupérez-moi toutes les choses qui commencent par A et affichez-les dans la mini partition A de x. Créez un nouveau A (x) s'il existe déjà un A (x). Remplacez x par un numéro séquentiel (c'est peut-être le travail du planificateur pour le faire) Ie Donnez-moi le prochain identifiant unique A (x).

Remettez (planifiez) les travaux terminés par le mappeur (étape précédente) aux nœuds de cluster «réduire». Réduire le cluster de nœuds affinera ensuite davantage le type de chaque partie A (x) qui se produira uniquement lorsque toutes les tâches du mappeur sont terminées va être une autre mini partition A en devenir). Affiche le résultat dans la partition triée finale (c.-à-d. Trié-A, Trié-B, etc.)

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

Il peut y avoir des étapes intermédiaires entre les deux ... Je ne suis pas sûr :). C'est-à-dire cartographier davantage et réduire après l'étape de réduction initiale.