Archives par étiquette : reduce

MongoDB : un exemple de map-reduce

Le concept de map-reduce (on lit parfois les termes de paradigme de programmation ou de design pattern associés à map-reduce) n’a rien de nouveau : il s’inspire grandement des principes de base de la programmation fonctionnelle (i.e, par usage de fonctions mathématiques).

Comme son nom l’indique, map-reduce se compose de deux fonctions :

  • map, qui passe à reduce une clé et des données à traiter
  • reduce qui, pour chaque clé donnée par map, va opérer une réduction sur les données en provenance de map selon une logique que vous allez devoir écrire.

Map-reduce a connu un renouveau avec l’apparition des data stores de très grande capacité (on parle ici en pétaoctets) sur le web et doit en grande partie son retour sous les feux de la rampe à Google qui s’en est servi (et s’en sert toujours) pour distribuer/paralléliser les traitements, sur des clusters de machines. Le principe est simple: découper un gros problème en plusieurs petits, résolus par distribution à des nœuds fils (réducteurs) qui ensuite remontent le résultat de ces opérations aux nœuds de niveau supérieur, et ce récursivement jusqu’à remonter au la racine de l’arbre, qui a initié le calcul et en récupère donc le résultat final.

Ici nous n’aurons par cette notion de master nodes / worker nodes car nous travaillons sur une seule instance de MongoDB, située sur un seul serveur (ma machine) et non sur une architecture basée sur des shards ou des replica sets.

Image provenant de http://www.pal-blog.de/

Image provenant de PAL-Blog [http://www.pal-blog.de]


Map traverse tous les documents de votre collection MongoDB et va pousser des infos à reduce selon une clé définie. Passons à la pratique sans plus tarder…

Notre collection de test

Nous allons constituer une collection dénommée commandes et qui va contenir les commandes passées sur notre site web. Ces commandes seront évidemment des documents dont la structure est la suivante :

  • userid : l’identifiant de l’utilisateur à l’origine de la commande
  • date : la date de passage (ou de validation, pourquoi pas) de la commande
  • codepost : le code postal de la ville de résidence de l’utilisateur
  • articles : la liste des articles commandés (il y en a autant que souhaité)
  • totalttc : le prix TTC de la totalité de la commande
  • totalht : le prix HT de la totalité de la commande
  • tva : le montant de TVA applicable à la commande
sebastien.ferrandez@sebastien:~$ mongo
 MongoDB shell version: 2.0.6
 connecting to: test
>db.createCollection('commandes');
 { "ok" : 1 }
>show collections;
 commandes
 system.indexes

>db.commandes.insert({userid: 54845, date: new Date("Apr 28, 2013"), codepost:13100, articles:[{id:1,nom:'livre',prix:29.90}, {id:9, nom:'eponge', prix:2.90}], totalttc:32.80, tva:5.38, totalht:27.42});

>db.commandes.insert({userid: 54846, date: new Date("Apr 29, 2013"),codepost:13290, articles:[{id:45,nom:'robinet',prix:69.90}, {id:9, nom:'laitx6', prix:9.90}], totalttc:79.80, tva:13.08, totalht:66.72});

>db.commandes.insert({userid: 54847, date: new Date("Apr 30, 2013"),codepost:13008, articles:[{id:76,nom:'clavier',prix:49.90}, {id:2, nom:'fromage', prix:1.50}], totalttc:51.40, tva:8.42, totalht:42.98});

>db.commandes.insert({userid: 54848, date: new Date("Apr 28, 2013"),codepost:13600, articles:[{id:2987,nom:'presse',prix:2}], totalttc:2, tva:0.33, totalht:1.67});

>db.commandes.insert({userid: 54848, date: new Date("Apr 29, 2013"),codepost:13600, articles:[{id:2988,nom:'presse',prix:5.90}], totalttc:5.90, tva:0.97, totalht:4.93});

>db.commandes.insert({userid: 54848, date: new Date("Apr 30, 2013"),codepost:13600, articles:[{id:3989,nom:'presse',prix:1.20}], totalttc:1.20, tva:0.20, totalht:1});

>db.commandes.insert({userid: 54847, date: new Date("Apr 25, 2013"),codepost:13008, articles:[{id:2987,nom:'presse',prix:2}], totalttc:2, tva:0.33, totalht:1.67});

Structure du JSON

Voici la structure de l’un de nos documents :

{
    "_id": ObjectId("517fb463b53bb7169584f3c7"),
    "userid": 54847,
    "date": ISODate("2013-04-29T22:00:00Z"),
    "codepost": 13008,
    "articles": [
        {
            "id": 76,
            "nom": "clavier",
            "prix": 49.9
        },
        {
            "id": 2,
            "nom": "fromage",
            "prix": 1.5
        }
    ],
    "totalttc": 51.4,
    "tva": 8.42,
    "totalht": 42.98
}

Le JavaScript de notre map-reduce

Maintenant, nous allons écrire le map-reduce qui va opérer sur ces données; notre but est d’afficher, par code postal, le chiffre d’affaire généré par notre site en ligne. Créons donc un fichier mapred.js qui contiendra notre MR :

use commandes;

map = function() {
	emit(this['codepost'], {totalttc: this['totalttc']});
	};

reduce = function(cle, valeur) {
			var s = {somme : 0};
			valeur.forEach(function(article) {
				s.somme += article.totalttc;
			});
			return s;
		};

db.commandes.mapReduce(map, reduce, {out:'total_cmdes_par_ville'});

db.total_cmdes_par_ville.find();

And…action !

Nous injectons notre fichier JS dans Mongo

sebastien.ferrandez@sebastien:~$ mongo < /tmp/mapred.js

Et voici le résultat produit :

MongoDB shell version: 2.0.6
connecting to: test
function () {
    emit(this.codepost, {totalttc:this.totalttc});
}
function (cle, valeur) {
    var s = {somme:0};
    valeur.forEach(function (article) {s.somme += article.totalttc;});
    return s;
}
{
        "result" : "total_cmdes_par_ville",
        "timeMillis" : 33,
        "counts" : {
                "input" : 7,
                "emit" : 7,
                "reduce" : 2,
                "output" : 4
        },
        "ok" : 1,
}
{ "_id" : 13008, "value" : { "somme" : 53.4 } }
{ "_id" : 13100, "value" : { "totalttc" : 32.8 } }
{ "_id" : 13290, "value" : { "totalttc" : 79.8 } }
{ "_id" : 13600, "value" : { "somme" : 9.1 } }
bye

La fonction map va émettre (emit) des paires clé/valeur sur lesquelles reduce va travailler. Pour faire simple, reduce va faire la somme de tous les montants TTC des commandes pour un code postal donné. Une collection est créée pour abriter le résultat de l’exécution de map-reduce : nous avons décider de la nommer total_cmdes_par_ville. Elle est persistante, elle ne sera pas détruite une fois que vous vous déconnectez du shell MongoDB.