Introduction au paradigme MapReduce

MapReduce (MR) est un paradigme de programmation qui a été introduit par les chercheurs de Google,  J. Dean et S. Ghemawat  en 2004. Ce modèle est destiné à la création de programmes parallèles qui traitent des grandes quantités de données, et qui s’exécutent sur des clusters de machines. Un programme MR s’écrit sous la forme de deux fonctions  map et reduce, et les données sont représentées sous la forme de paires (clé, valeur).

map (Cléin, Valeurin)  →  list (Cléint, Valeurint)

reduce (Cléint, list (Valeurint)) → (Cléout, Valeurout)

1Dans ce qui suit, nous allons expliquer le principe de MR à l’aide de l’exemple de calcul de nombre d’articles scientifiques par année. Nous disposons d’un ensemble d’articles scientifiques (entités) issues de plusieurs sources (ex. DPLP, ACM et Google Scholar). L’ensemble E d’entités en entrée est divisé en M partitions par la fonction Split tel que M représente le nombre de tâches map que l’utilisateur spécifie. Chaque tâche map lit la partition qui lui correspond, avec comme clé d’entrée (Cléin)  le numéro de la partition donnée et comme valeur d’entrée (Valeurin) l’ensemble des articles appartenant à cette partition. La lecture des différentes partitions se fait dans le même temps du fait que l’ensemble des tâches map s’exécutent en parallèle. Cela  permet d’obtenir un temps de lecture égal à T/M, tel que T représente le temps nécessaire pour la lecture de la totalité des entités en séquentiel. Chaque tâche map aura comme entrée une paire de la forme (Numéro de la partition, Les articles de la partition), où le numéro de la partition représente la Cléin  et le contenu de la partition (ensemble des articles de la partition) représente la Valin. Après avoir lu sa partition d’entités, chaque tâche map effectue les traitements  qui ont été spécifié par l’utilisateur et elle génère un ensemble de paires intermédiaires  (Cléint, Valeurint). Le choix de la clé d’entrée, la valeur d’entrée, la clé intermédiaire, la valeur intermédiaire et les traitements effectués par chaque tâche est effectué par l’utilisateur selon le besoin de son application. Dans notre exemple, la phase map servira principalement pour faire le blocking  qui est considéré comme une option par défaut du modèle MR. Dans ce cas, la sortie de chaque tâche map sera un ensemble de paires (Année, 1). Donc l’idée est qu’à chaque fois que la fonction map trouve un article dans la partition qui lui a été attribuée, elle génère une paire intermédiaire constituée de l’année de l’article et un compteur égal à 1. La fonction map ressemblera au pseudo-code suivant :

map (int cléin, valeurin)

// cléin : numéro de la partition

// valeurin : un article de la partition

Pour chaque article de la partition :

Générer (année, 1) ;

A la fin de la phase map, les paires (Cléint, Valeurint) seront regroupées automatiquement sans l’intervention de l’utilisateur, à l’aide de la fonction part qui établit le partitionnement  (blocking) des entités et affecte chaque partition  à la tâche reduce qui lui correspond parmi les R tâches reduce existantes. Ensuite, les tâches reduce qui s’exécutent en parallèle, établissent les traitements correspondants et écrivent les résultats (Cléout, Valeurout) soit dans un même fichier soit dans des fichiers différents. Dans le cas de notre exemple, chaque fonction reduce établit la somme des compteurs intermédiaires (les 1) correspondants à une année donnée, puis génère en sortie une paire (année, nombre d’articles).  La fonction reduce ressemblera au pseudo-code suivant :

reduce (int cléint,  List valeurint)

// cléint : l’année

// valeurint : liste des compteurs intermédiaires

Int somme =0 ;  

Pour chaque compteur de la liste valeur:

Somme = somme + compteur ;

Générer (année, somme) ;

Newsletter

Retrouvez l’essentiel de l’actualité du Big Data directement par mail !

Les experts de Formation-BigData décortiquent chaque mois l’actualité, les dernières innovations.