Map/Reduce ?

Le principe du paradigme Map/Reduce (oui j'ai choisi de considérer qu'il s'agissait d'un paradigme... carrément) Map/Reduce est de diviser les données à traiter en partitions indépendantes, traiter ces partitions en parallèle et finalement combiner les résultats des traitements parallèles.

Le Map consiste en l'étape de découpage puis de distribution des différentes partitions de données constituées. La mise en œuvre se réalise habituellement à l'échelle d'une grappe de serveurs. Le Map est alors réalisé par un nœud qui distribue les données à d'autres nœuds. Chaque nœud en réception se charge alors du traitement sur les données reçues.

Le Reduce est l'opération inverse du Map qui consiste à récolter tous les résultats calculés en parallèle et les fusionner (reduce) en un seul résultat global. Chaque partition de données distribuée se structure comme un couple clée/valeur. La clée est utilisée lors de la fusion pour regrouper les valeurs qui vont ensemble. Toutes les valeurs associées à une clée sont donc réunies à la fin du Reduce.

Le schéma ci-dessous résume le principe général :

Principe général du Map/Reduce

... et dans MongoDB ?

Le principe de Map/Reduce est directement implémenté dans l'API de MongoDB, soit par les divers pilotes, soit par le shell à travers la méthode mapReduce des collections. La méthode mapReduce prend en paramètre une fonction map, une fonction reduce et un certain nombre d'autres paramètres optionnels passés comme un objet.

La fonction Map

La fonction map ne prend pas de paramètre mais elle accède directement à l'entrée de la collection considérée par le biais de this. Le rôle principal de cette méthode est d'émettre, à l'aide de la fonction emit, un couple clé/objet. Par exemple, la fonction ci-dessous retourne un tel couple avec pour clé la valeur de l'attribut croisclus de l'entrée et pour objet une simple paire clé/valeur : instances/1 :

m = function () {
  emit(this.croisclus, {instances: 1});
}

La fonction Reduce

La fonction reduce prend en paramètres une clé et une collection d'objets associés à cette clé tels que générés par la fonction map. Elle produit en retour un objet de même structure que ceux passés en paramètre. Étant donné que la fonction reduce peut-être appelée de manière itérative avec en paramètre des objets qu'elle a elle même générée, il est important qu'elle soit idempotente. En d'autres termes, les égalités suivantes doivent être respectées :

  • reduce(k, A ,B) == reduce(k, B, A)
  • reduce(k, A ,B) == reduce(k, reduce(k, A,B))

Par exemple, la fonction ci-dessous consomme les couples générés par la fonction map et additionne les valeurs de l'attribut instances qui sont associées à une même clée k. En d'autre terme elle fusionne tous les objets de même clé k en un seul objet en additionnant leurs valeurs instances :

r = function (k, vals) {
  var result = {instances: 0};
  vals.forEach( function(value) {
      result.instances += value.instances; 
    }
  );
  return result;
}

La fonction mapReduce

Une fois ces deux fonctions écrites, il ne reste plus qu'à lancer l'opération de Map/Reduce sur la collection ou éventuellement sur un sous-ensemble de la collection définie par une requête. Depuis la version 1.8 de MongoDB, il est nécessaire de préciser le nom de la collection où seront stockés les résultats du processus à l'aide d'un attribut out dans le paramètre optionnel :

res = db.nano.mapReduce(m, r, {out: 'test1'})
{
	"result" : "test1",
	"timeMillis" : 39517,
	"counts" : {
		"input" : 167340,
		"emit" : 167340,
		"output" : 2332
	},
	"ok" : 1,
}

Les résultats du processus sont alors disponibles dans ladite collection :

db.test1.find().limit(10)
{ "_id" : "C10M10", "value" : { "instances" : 2 } }
{ "_id" : "C10M11", "value" : { "instances" : 3 } }
{ "_id" : "C10M12", "value" : { "instances" : 5 } }
{ "_id" : "C10M13", "value" : { "instances" : 10 } }
{ "_id" : "C10M15", "value" : { "instances" : 1 } }
{ "_id" : "C10M16", "value" : { "instances" : 10 } }
{ "_id" : "C10M17", "value" : { "instances" : 21 } }
{ "_id" : "C10M18", "value" : { "instances" : 19 } }
{ "_id" : "C10M19", "value" : { "instances" : 674 } }
{ "_id" : "C10M20", "value" : { "instances" : 2 } }