Shuffle and sort

Hadoop et MapReduce en Java

Ce site ne sera plus alimenté de contenu après août 2014. Tous les nouveaux articles seront redigés pour www.waitingforcode.com
Les données traitées par MapReduce sont sous format "clé:valeur". Ce modèle de programmation garantit que les données entrantes sont toujours triées par la clé. C'est possible grâce à la fonctionnalité shuffle and sort.

A travers tout l'article on expliquera en quoi consiste cette fonctionnalité. On verra le fonctionnement de ce système ainsi comment il facilite le travail aux tâches de map et reduce.

Tout d'abord regardons quels sont les formats des données qui passent par le flux d'une tâche MapReduce. Dans notre court exemple on utilisera la liste des 5 meilleurs buteurs dans le championnat de France de football. A la fin on voudra récupérer la liste des meilleurs buteurs triée. La clé des données est le numéro de saison. Voici les fichiers d'entrée :

// file_1
2003/2004 : Alexander Frei 20 goals
// file_2
2003/2004 : Didier Drogba 18 goals
// file_3
2004/2005 : Pascal Feinduono 13 goals
// file_4
2003/2004 : Pauleta 18 goals
// file_5
2004/2005 : Mickäel Pagis 15 goals
// file_6
2004/2005 : Pauleta 14 goals
// file_7
2003/2004 : Djibril Cissé 26 goals
// file_8
2004/2005 : Alexander Frei 20 goals



  1. Phase map : on formatte les lignes de cette manière : "saison-joueur-buts_en_chiffre"
    On aura alors les données de sortie :

    2003/2004-Alexander Frei-20
    2003/2004-Didier Drogba-18
    2004/2005-Pascal Feinduono-13
    2003/2004-Pauleta-18
    2004/2005-Mickäel Pagis-15
    2004/2005-Pauleta-14
    2003/2004-Djibril Cissé-26
    2004/2005-Alexander Frei-20



  2. Phase de trie sort and shuffle (mêler et trier)
    C'est alors que MapReduce intervient pour trier les résultats et les placer dans le bon endroit (sous bonne clé). Voici ce qu'on aura avant la transmission de données à la méthode reduce :

    2003/2004 : ["Alexander Frei-20", "Didier Drogba-18", "Djibril Cissé-26", "Pauleta-18"]
    2004/2005 : ["Alexander Frei-20", "Mickäel Pagis-15", "Pascal Feinduono-13", "Pauleta-14"]



  3. Phase reduce
    C'est ici qu'on va splitter les résultats groupés par la phase de sort and shuffle pour les ordonner en fonction des buts marqués. On aura alors une sortie du type :

    2003/2004 : ["Djibril Cissé-26", "Alexander Frei-20", "Didier Drogba-18", "Pauleta-18"]
    2004/2005 : ["Alexander Frei-20", "Mickäel Pagis-15", "Pauleta-14", "Pascal Feinduono-13"]




Grâce à cette illustration on voit bien que l'étape entre map et reduce porte bien son nom "mêler et trier". Cette appellation s'explique à travers le fonctionnement des tâches map et reduce. Chaque tâche map crée un flux des données de sortie. Cependant, ces données sont peu exploitables car il est alors impossible de les grouper.

Chaque tasktracker divise d'abord le résultat de son calcul en plusieurs fichiers. En même temps une opération tourne dans la mémoire. Cette opération trie les partitions par leurs clés. Les fichiers de sortie sont alors fusionnés en un seul fichier final avant la fin de la tâche du mapping. C'est à ce moment-là, qu'une sauvegarde sur le disque a lieu. Le fichier est stocké sur le même disque qui a exécuté la tâche du mapping et il est prêt à être exploité par la tâche de reduce.

Le fichier qui sert à reduce est donc manipulé. Il subit le tri par étapes. Le nombre d'étapes est spécifié dans la propriété de configuration io.sort.factor. Chaque étape génère un fichier final composé d'un nombre de fichiers traités dans l'étape. Les valeurs de ce fichier sont triés par rapport à la clé. Regardons cette opération sur un exemple :
- 200 fichiers générés par les tâches map
- valeur de l'io.sort.factor = 10
- les fichiers seront donc traités en 10 étapes, 20 fichiers par étape
- au final on aura donc 10 fichiers, chacun composé de 20 autres de mapping, qui seront soumis à des tâches reduce

Maintenant l'appellation "mêler et trier" est plus clair. Pour résumer, on peut constater l'action de "mêler" dans la phase de réduction quand les fichiers du mapping sont fusionnés pour créer un fichier final. Ce fichier final sert ensuite en tant que l'entrée pour la fonction reduce. En ce qui concerne l'acte de "trier", toutes les valeurs de ce fichier final sont ordonnées. Elles ne sont pas placées aléatoirement, das un ordre illogique.
Bartosz KONIECZNY 08-09-2013 16:03 Hadoop
Moi

Développeur d'applications Internet et journaliste passionné par l'adjectif français. Un aigle polonais orienté vers la progression, volant très haut et écoutant du zouk après les matches du foot français.

Vous appréciez mon travail ?

Pour contribuer au développement de ce site, ou pour remercier pour des articles rédigés, vous pouvez faire un don.

Un conseil PHP

Comment créer une signature pour OAuth

La création d'une signature (paramètre oauth_signature) pour la requête OAuth est réalisée avec l'algorithme HMAC-SHA1. Son implémentation chez PHP se présente ainsi :

hash_hmac('sha1', "Message to hashed", "Secret key", true)
Le résultat de cet algorithme doit ensuite être encodé avec Base64. Un exemple d'utilisation chez le protocle OAuth peut se présenter de la manière suivante :
public function getSignature($baseString, $signatureKey)
{
  return base64_encode(hash_hmac('sha1', $baseString, $signatureKey, true));   
}