MapReduce : Une explication très simple

En 2004, Google a publié son document sur MapReduce. Vous avez surement entendu parler soit ici, ou ailleurs de ce modèle de programmation. Si vous l'avez considéré comme un buzzword, ou comme un mystère alors sachez que ce n'est pas le cas. Le concept de base est très simple. Dans cet article, je l'explique en de termes très simple et compréhensible par tous. C'est intentionnellement que j'ai évité d'utiliser les termes très complexes qui pourraient dérouter les débutants.

Le travail que votre patron vous donne.

Supposez que vous travaillez dans une grande entreprise. Votre hiérarchie souhaite lancer un projet d'étude de refonte d'une grande plateforme de blogs en ligne. Et le lendemain matin, au bureau vous recevez un mail de votre directeur concernant ce projet.

Cher <votre nom>,

Comme vous savez, nous sommes entrain de vouloir mettre en place un projet 

de blog en ligne blogger2.com. J'ai besoin de certaines statistiques, en 

parcourant l'ensemble des blogs de l'ancien site, combien de fois un mots d'un

caractère apparait (comme 'a', 'I'), combien de fois un mot de deux caractères 

apparait (comme 'be', 'is')... et ainsi de suite jusqu'à combien de fois de mots 

de 10 caractères apparaissent.

Je sais pertinemment que c'est un travail très difficile. Je te demande de 

travailler avec les 50000 employés de notre entreprise pendant une semaine. Je me

déplace le weekend et c'est très important que j'ai des résultats à mon retour.

NB: Très important, tout doit être fait manuellement, des copier-coller sur les

blogs sont permis dans Notepad. J'ai lu quelque part que si vous écrivez des

programmes, Google permettra de retrouver.

Cordialement.

Le Directeur général.

Imaginez-vous dans cette position pour le moment. Vous avez 50000 collègues pour vous aider pendant une semaine. Vous devez rechercher le nombre de mots d'un caractère, le nombre de mots de deux caractères, etc., et ce en parcourant un grand nombre de blogs dans le portail. Et à la fin, vous devez donner un rapport à votre directeur.

• Nombre d’occurrences de mots d'un caractère : approx. 937688399933
• Nombre d'occurrences de mots de deux caractères : approx. 23388383830753434
• ... jusqu'à nombre d’occurrences de mots de 10 caractères.

Si vous n'avez pas le choix entre un homicide, un suicide ou alors une démission, comment allez vous résoudre le problème ? Comment allez-vous éviter le chaos avec un nombre d'employés aussi grand ?
Comment allez-vous coordonner pour répartir les taches ? Vous décidez alors de prendre une journée pour réfléchir, et le jour suivant vous arrivez avec une idée géniale. (En riant, vous dites : "j'ai perdu déjà une journée.")

La bonne idée de génie

Le jour suivant, vous réunissez les 50000 employés et vous annoncez. Pendant une semaine, vous serez divisés en plusieurs groupes :

• Les Mappers (10000 personnes seront dans ce groupe)
• Le Grouper (Pour le moment une personne seule assurera ce rôle)
• Les Reducers (le reste)
• Le Maitre (vous-même)

Par la suite, vous organisez des réunions avec chaque groupe.

Votre discours avec les Mappers

Chaque Mapper aura 50 blogs et une grande feuille de papier. Chacun de vous ira sur chaque lien de blog et pour chaque mot dans ces blogs, écrire une ligne sur le papier. Le format de cette ligne devrait être le nombre de caractères dans le mot, ensuite une virgule, et enfin le mot lui-même.
Par exemple, si vous trouvez le mot "a", vous écrivez "1,a" dans une nouvelle ligne du papier. Parce que le mot "a" a un seul caractère. Si vous trouvez le mot "hello", vous écrivez "5,hello" dans une nouvelle ligne.
Chacun prends 4 jours. Ainsi, après 4 jours, votre feuille ressemblera à ceci:

• "1,a"
• "5,hello"
• "2,if"
• ... et plusieurs millions d'autres lignes

A la fin du 4ème jour, chacun de vous remettra sa feuille complètement remplie au Grouper.

Votre discours avec le Grouper

Je vous remettrai des feuilles de papier. Le premier papier sera marqué 1, le second sera marqué 2, et ainsi de suite jusqu'à 10. Vous collectez les données des Mappers et pour chaque ligne dans les feuilles des Mappers, si vous avez "1, ", vous écrivez la ligne sur la feuille 1, si vous avez "2, ", vous écrivez cela sur la feuille 2.
Par exemple, si la première ligne dans une feuille de Mapper, il y a "1,a", vous écrivez "a" sur la feuille 1, si il y a "2,if", vous écrivez "if" sur la feuille 2. Si vous voyez "5,hello", vous écrivez "hello" sur la feuille 5.
A la fin de ton travail, les 10 feuilles que tu possèdes ressembleront à ceci:

• Feuille 1 : a, a, a, I, I, i, a, a, i, i, .... millions d'autres
• Feuille 2 : if, of, it, at, am, im, .... millions d'autres
• Feuille 3 : the, the, and, for, met, bet, the, and, .... millions d'autres
•  ...
• Feuille 10 : ....

Une fois que c'est fait, vous distribuez chaque feuille à un Reducer. Par exemple, la feuille 1 va au Reducer 1, la feuille 2 va au Reducer 2 et ainsi de suite.

Votre discours avec les Reducers

Chacun de vous a une feuille que le Grouper lui a remis. Pour chacune de ces feuilles, vous comptez le nombre de mots écrits dessus et écrivez le résultat en gras au verso de la feuille. Par exemple, si vous êtes le Reducer 2. Vous avez obtenu la feuille 2 dont le contenu ressemble à ceci:
Feuille 2 : if, of, it, of, of, if, at, im, is, is, of, of ...
Vous devez compter le nombre de mots sur cette feuille et dire le nombre de mots est : 2883830044. Vous écrivez ce résultat au verso de la feuille de papier en gras et vous me la remettez.

Le contrôle du climat et de l'ambiance de travail

A la fin de ce processus, vous avez 10 feuilles. La feuille 1 possède le décompte des mots d'un caractère au verso. La feuille 2 possède la même information pour les mots de deux caractères. Vous l'avez fait. Vous êtes des génies.

Vous avez essentiellement fait du MapReduce. Le plus grand avantage dans votre approche était ceci:

• Les Mappers pouvaient travailler de façon indépendante
• Les Reducers pouvaient travailler de façon indépendante
• Le grouper peut travailler très rapidement, parce qu'il n'a pas à compter les mots, il les place juste sur la bonne feuille en regardant juste le premier nombre

Le processus peut être facilement appliquée à plusieurs autres types de problèmes. Dans ces cas :

• Le travail du Master (diviser et répartir le travail) et le grouper (regroupe les valeurs par clé, la valeur avant la virgule) reste le même. C'est ce que toutes les librairies MapReduce fournissent.
• Le travail des Mappers et des Reducers diffère en fonction des problèmes. C'est ce que vous devez produire (écrire un programme)

Vous pouvez optimiser ceci un peu plus. Par exemple, vous ne devez même pas mentionner les mots quelque part. Vous pouvez juste écrire "x" au lieu du mot réel jusqu'à la fin, tout ce dont nous avons à faire c'est de compter les mots.
De plus, les choses ne doivent pas se produire séquentiellement comme dans un programme procédural. En outre, le Mapper peut faire le travail du Grouper et vice versa. Il suffit de donner à chacun une idée et vous aurez un résultat.
Ainsi, vous résolvez un grand challenge qui vous a été soumis. Après une semaine, vous collectez les feuilles de papier des Reducers. Le verso de la feuille 1 aura le nombre d’occurrences de mots d'un caractère. Le verso de la feuille 2 aura le nombre d'occurrences de mots de deux caractères et ainsi de suite...
Vous faites une feuille Excel ou vous enregistrez toute l'information, vous imprimez et vous la ramenez à votre directeur général avec un grand sourire.

"Bon travail, posez la sur mon bureau, je vais regarder cela dans un mois": he says, :)

Source : http://ksat.me/map-reduce-a-really-simple-introduction-kloudo/