Tutoriel pour implémenter un algorithme de MapReduce en JavaScript classique et ES6

Ce tutoriel s'adresse à des lecteurs qui connaissent déjà le langage JavaScript.

Nous n'utiliserons pour ce tutoriel que le langage JavaScript implémenté en standard dans le navigateur (EcmaScript 5) ainsi que sa dernière mouture (EcmaScript 6) également en standard dans le framework Node.js (JavaScript côté serveur).

Aucune bibliothèque complémentaire ne sera nécessaire dans ce tutoriel.

Ce modèle de programmation popularisé par Google permet, à travers deux macro-fonctions, de découper un problème en sous-problèmes (phase de Map), puis de collecter les résultats issus de la résolution de ces sous-problèmes pour fournir un résultat global (phase de Reduce).

Dans un contexte de Big Data, les sous-problèmes issus de la phase de Map sont distribués sur différents nœuds pour être traités en parallèle.

L'essentiel des traitements consiste à créer des listes de clés/valeurs à partir de données brutes et de les trier.

Dans le cadre de cet article, l'exemple pédagogique que nous traiterons ne comprendra qu'un sous-problème traité dans son ensemble par un nœud unique.

Dans son Tutoriel Hadoop, Mickael Baron décrit très clairement le patron de conception MapReduce et nous en propose une implémentation en langage Java sur un exemple pédagogique très simple. L'objet de cet article est de réaliser sur le même exemple un traitement similaire en utilisant JavaScript.

Pour expliquer les concepts de Map et de Reduce, nous prendrons donc l'exemple du compteur de mots fréquemment utilisés, avec une légère variante. Tous les mots sont comptabilisés à l'exception du mot « se ». Le jeu de données à analyser sera le suivant :

var inputString = "voiture la le elle de elle la se la maison voiture";

La figure ci-dessous énumère les différentes étapes qui seront présentées par la suite.

I-C-1. La fonction Map▲

I-C-2. les fonctions Sort et Shuffle▲

I-C-3. La fonction Reduce▲

Sans surprise, on découvre qu'il existe quelques modules Node.js pour réaliser rapidement ce travail. J'utilise personnellement dans mes activités de Big Data le module npm MapReducequi permet aisément d'implémenter l'algorithme de la façon suivante :

var mr = new maprereduce(function(item) {
    // la fonction de Map
}, function(result) {
    // la fonction de Reduce
}, function(item1, item2) {
    // la fonction de Reduce finale globale
});

Pour installer ce plugin, on fait classiquement :npm install maprereduce.Mais pour rester dans le JavaScript pédagogique et vraiment comprendre le MapReduce, nous n'utiliserons pas cette bibliothèque. En effet, l'objectif de cet article est de comprendre dans les détails les mécanismes de cet algorithme en l'implémentant en pur JavaScript.

Le JavaScript se prête particulièrement à ce type de traitement, car ce langage offre un objet Array qui possède un arsenal de méthodes pour les tris, les extractions ou les recherches…

Nous utiliserons les méthodes map() et reduce() de l'objet Array. Et pour la partie shuffle et sort de l'algorithme, on s'appuiera sur les méthodes sort() et filter() de ce même objet.

Voici le code source de l'algorithme qui fonctionne sur tous les navigateurs :

var inputString = "voiture la le elle de elle la se la maison voiture";

// Fonction qui retourne une liste clé/valeur et élimine 'se'
var map = function (str) {
    return str.split(" ").map(function(str) {
      if (str.valueOf() === "se")
        return [str, [0]];
      else
        return [str, [1]];
    }).filter(function(array){
      return array[1][0] > 0;
    });
}

// Fonction qui regroupe des valeurs par clé
var shuffle = function (arr) {
  var sortedArray = arr.sort();
  var size = sortedArray.length - 1;
  for(var i = 0; i < size; i++) {
    if (sortedArray[i][0] == sortedArray[i+1][0]) {
      sortedArray[i][1].push(1);
      sortedArray.splice(i+1, 1);
      size--;
      i--;
    }
  }
  return sortedArray
}

// Fonction qui renvoie un tableau de clé-->nombre d'occurrences
var reduce = function (arr){
  for (var i = 0; i < shuffledArray.length; i++)
  {
    shuffledArray[i][1] = shuffledArray[i][1].reduce(function(a, b) {
      return a + b;
    });
  }
}

var mappedArray = map(inputString);
var shuffledArray = shuffle(mappedArray);
reduce(shuffledArray);

console.log(shuffledArray);

II-B-1. Implémentation en EcmaScript 6▲

var inputString = "voiture la le elle de elle la se la maison voiture";

// Fonction qui retourne une liste clé/valeur et élimine 'se'
var map = (str) => str.split(" ").map(str => (str.valueOf() === "se") ? [str, [0]] : [str, [1]]).filter(elem => elem[1][0] > 0);

// Fonction qui regroupe des valeurs par clé
var  shuffle = (arr) => {
                          var sortedArray = arr.sort();
                          sortedArray.forEach((elem, index, arr) => {
                            while (arr[index + 1] && elem[0] === arr[index + 1][0]){
                              arr[index][1].push(1);
                              arr.splice(index + 1, 1);
                            }
                          });
                          return sortedArray;
};

// Fonction qui renvoie un tableau de clé-->nombre d'occurrences
var reduce = (arr) => arr.map(elem => [elem[0],elem[1].reduce((a, b) => a + b)]);

var mappedArray = map(inputString);
var shuffledArray = shuffle(mappedArray);
var reducedArray = reduce(shuffledArray);

console.log(reducedArray);