Clochix

Ca fait quelques temps que papy entend parler de "MapReduce", mais comme son processeur n'est plus de toute première jeunesse, il lui a fallu quelques lectures pour commencer à saisir de quoi il retourne. Je me dépêche d'en toucher 2 mots ici dans l'espoir que ça me servira demain quand j'aurai oublié.

Imaginons qu'à la maison de retraite des Octets verts, pour vous faire tenir tranquille, la matoninfirmière Chef vous ait ordonné de compter le nombre d'occurrences de chaque mot dans l'anthologie de la blogosphère francophone publiée par la Pléïade, et ce avant le goûter, sous peine d'en être privé. Mission impossible ? Non, pas en faisant appel à super MapReduce. Aussi sec, vous mobilisez quelques stagiaires^[1] et mettez en place votre logistique:

1. commencez par débrocher le livre;
2. donnez-en une page à chaque stagiaire, en lui demandant de créer une fiche par mot de la page et d'y compter les apparitions de ce mot. Chaque fiche contiendra donc une clé, le mot, et une valeur, son nombre d'occurrences. Une fois la page traitée, il répartit les fiches dans 26 boîtes, en fonction de la première lettre du mot. Vous supervisez tout le travail: chaque fois qu'un stagiaire a fini une page, vous lui en redonnez une autre. Si l'un meurt à la tâche, vous reprenez la feuille et la confiez à un autre;
3. cette première phase achevée, vous avez 26 boîtes contenant chacune les fiches de tous les mots commençant par une lettre. Prenez alors 26 nouveaux stagiaires (les premiers sont fatigués), confiez à chacun une boîte, et priez-le de trier les fiches;
4. le tri effectué, il ne reste plus à vos 54 petites mains qu'à parcourir une dernière fois les fiches en notant sur une nouvelle chaque mot et la liste de son nombre d'occurrences sur chacune des fiches initiales;
5. dernière étape, confiez ces fiches à une nouvelle série de stagiaires, des forts en math, en leur demandant d'additionner les valeurs. Il ne vous reste plus qu'à ramasser les copies, et vous avez le résultat à temps pour aller savourer votre tartine de Nutella.

Au total, l'opération a demandé plus d'efforts que si vous l'aviez effectuée vous même. Le coût est assez élevé: des stagiaires, des milliers de fiches cartonnées, etc. Mais le résultat a été obtenu en un temps record, et c'est ce qui compte. Et puis globalement, ce ne sont pas les stagiaires qui manquent, et ils ne coûtent pas bien chers. Quand aux fiches cartonnées, il suffit d'écrire dessus au crayon de papier pour pouvoir gommer et les réutiliser.

Ah, et le rapport avec mon titre ? Dans cette opération, seules 2 étapes sont spécifiques à ce que je voulais faire: la transformation des pages en fiches, et l'addition des résultats. Toutes les autres étapes sont génériques. En donnant d'autres instructions aux travailleurs chargés de ces étapes, je pourrais utiliser ma chaîne pour réaliser d'autres traitements en parallèle. C'est le principe du MapReduce: une chaîne de traitement à laquelle on passe 2 fonctions:

• map va convertir une donnée en une série de paires clé/valeur
• reduce va appliquer un traitement à l'ensemble des valeurs trouvées pour une clé.

Cette méthode, formalisée par Google à partir de concepts de la programmation fonctionnelle, permet d'utiliser la parallélisation pour effectuer rapidement des calculs sur d'immenses quantités de données, par exemple pour générer ses index. A une autre échelle la base de données CouchDB l'utilise pour créer des vues: une fonction est appliquée en parallèle à tous les documents, et le résultat synthétisé pour renvoyer les documents voulus.

Pour aller plus loin, je vous conseille la lecture du document de référence, MapReduce: Simplified Data Processing on Large Clusters , par Jeffrey Dean and Sanjay Ghemawat, de Google (enfin surtout de l'explication de l'implémentation, le reste du document étant très technique).

Et si vous voulez vous lancer, il existe de nombreuses implémentations libres de MapReduce, une des plus connue étant Hadoop, en Java, mais pratiquement chaque langage commence à avoir la sienne.