Bases NoSQL (JSON): MongoDB

Nous allons consacrer ce chapitre à une base dite “documentaire” qui représente les données au format JSON. Il s’agit de MongoDB, un des systèmes NoSQL les plus populaires du moment. MongoDB est particulièrement apprécié pour sa capacité à passer en mode distribué pour répartir le stockage et les traitements: nous verrons cela ultéieurement. Ce chapitre se concentre sur MongoDB vu comme une base centralisée pour le stockage de documents JSON.

L’objectif est d’apprécier les capacités d’un système de ce type (donc, non relationnel) pour les fonctionnalités standard attendues d’un système de gestion de bases de données. Comme nous le verrons, MongoDB n’impose pas de schéma, ce qui peut être vu comme un avantage initialement, mais s’avére rapidement pénalisant puisque la charge du contrôle des données est reportée du côté de l’application; MongoDB propose un langage d’interrogation qui lui est propre (donc, non standardisé), pratique mais limité; enfin MongoDB n’offre aucun support transactionnel.

Les données utilisées en exemple ici sont celles de notre base de films, que vous pouvez récupérer sur le site du Webscope, http://webscope.bdpedia.fr/index.php?ctrl=xml. Choisissez bien entendu les exports en JSON. Si vous disposez de documents JSON plus proches de vos intérêts, vous êtes bien entendu invités à les prendre comme base d’essai.

S1: installation, mise en route

MongoDB est un système libre de droits (pour sa version de base), téléchargeable à http://www.mongodb.org/downloads.

Installation de MongoDB

Si le système n’est pas déjà installé, téléchargez la version correspondant à votre système d’exploitation, et décompressez l’archive récupérée. Vous obtenez un répertoire nommé mongo, agrémenté du numéro de version et autres indicateurs. Nous le désignerons par mongodir pour faire simple: vous devriez ajouter mongodir/bin dans la variable d’environnement PATH. Par exemple, si vous utilisez le bash shell:

export MONGO_HOME=/usr/local/mongo2.6
export PATH=$PATH:$MONGO_HOME/bin

MongoDB fonctionne en mode classique client/serveur. Pour lancer le serveur, exécutez simplement la commande mongod qui se trouve dans bin, et c’est tout. Ce qui donne, sous un système Unix, à partir du répertoire courant mongodir:

bin/mongod &

Ou tout simplement mongod si le répertoire bin est dans votre PATH, comme recommandé. Si tout se passe bien, le démarrage du serveur se concrétise pas des messages divers se terminant par:

[initandlisten] waiting for connections on port 27017

Le serveur mongod est donc en attente sur le port 27017. Maintenant, il nous faut une application cliente.

Clients MongoDB

Il s’agit bien des applications clientes. Nous avons en gros deux possibilités: l’interpréteur de commande mongo ou une application graphique plus agréable à utiliser. Parmi ces dernières, deux choix recommandables sont RockMongo, une application Web d’administration de MongoDB à peu près équivalente à phpMyAdmin, et RoboMongo, plus facile d’installation.

Le client mongo

L’interpréteur de commande se lance comme suit:

$ mongo
  MongoDB shell version: 2.4.7
  connecting to: test
  >

La base par défaut est test. Cet outil est en fait un interpréteur javascript (ce qui est cohérent avec la représentation JSON) et on peut donc lui soumettre des instructions en Javascript, ainsi que des commandes propres à MongoDB. Voici quelques instructions de base.

  • Pour se placer dans une base:

    use <nombase>
    
  • Une base est constituée d’un ensemble de collections, l’équivalent d’une table en relationnel. Pour créer une collection:

    db.createCollection("movies")
    
  • La liste des collections est obtenue par:

    show collections
    
  • Pour insérer un document JSON dans une collection (ici, movies):

    db.movies.insert ({"nom": "nfe024"})
    

    Il existe donc un objet (javascript) implicite, db, auquel on soumet des demandes d’exécution de certaines méthodes.

  • Pour afficher le contenu d’une collection:

    db.movies.find()
    

    C’est un premier exemple d’une fonction de recherche avec MongoDB. On obtient des objets (javascript, encodés en JSON)

    { "_id" : ObjectId("5422d9095ae45806a0e66474"), "nom" : "nfe024" }
    

    MongoDB associe un identifiant unique à chaque document, de nom conventionnel _id, et lui attribue une valeur si elle n’est pas indiquée explicitement.

  • Pour insérer un autre document:

    db.movies.insert ({"produit": "Grulband", prix: 230, enStock: true})
    

    Vous remarquerez que la structure de ce document n’a rien à voir avec le précédent: il n’y a pas de schéma (et donc pas de contrainte) dans MongoDB. On est libre de tout faire (et même de faire n’importe quoi). Nous sommes partis pour mettre n’importe quel objet dans notre collection movies, ce qui revient à reporter les problèmes (contrôles, contraintes, tests sur la structure) vers l’application.

  • On peut affecter un identifiant explicitement:

    db.movies.insert ({_id: "1", "produit": "Kramölk", prix: 10, enStock: true})
    
  • On peut compter le nombre de documents dans la collection:

    db.movies.count()
    
  • Et finalement, on peut supprimer une collection:

    db.movies.drop()
    

C’est un bref aperçu des commandes. On peut se lasser au bout d’un certain temps d’entrer des commandes à la main, et préferer utiliser une interface grahique. Il n’existe pas d’interface native fournie par 10gen, l’entreprise qui développe MongoDB, mais on trouve beaucoup d’outils en Open Source (cf. la liste http://docs.mongodb.org/ecosystem/tools/administration-interfaces/).

Le client RoboMongo

RoboMongo est un client graphique disponible pour toutes les plate-formes à robomongo.org. C’est sans doute le choix à privilégier. l’installation est très simple, l’outil semble assez complet et en évolution rapide. La figure L’interface RoboMongo montre l’interface en action.

_images/RoboMongo.png

L’interface RoboMongo

Le client RockMongo

C’est une application PHP disponible ici: http://www.rockmongo.com. Il vous faut donc un serveur Apache/PHP, probablement déjà disponible sur votre machine. Si ce n’est pas le cas, c’est tellement standard que vous devriez pouvoir l’installer en 2 clics.

Il est nécessaire d’installer l’extension PHP de connexion à MongoDB. La méthode varie selon votre système: la page http://rockmongo.com/wiki/installation donne les indications nécessaires.

En ce qui concerne RockMongo, récupérez la dernière version sur le site ci-dessus, installez-là dans votre répertoire htdocs, et laissez la configuration par défaut. En accédant à http://localhost/rockmongo (en supposant que rockmongo soit le nom du répertoire dans htdocs), vous devriez accéder à une fenêtre de connexion. Le compte par défaut est admin / admin. Une fois connecté, l’affichage devrait ressembler à celui de la figure L’interface RockMongo.

_images/rockmongo.png

L’interface RockMongo

Important

Ce qui précède est valable pour une installation sur une machine locale, avec un serveur mongod en local également.

L’interface ressemble à celle de phpMyAdmin, pour ceux qui connaissent. En particulier, la barre à gauche montre la liste des bases de données existantes,

Création de notre base

Nous allons insérer des documents plus sérieux pour découvrir les fonctionnalités de MongoDB. Notre base de films nous fournit des documents JSON, comme celui-ci par exemple:

{
  "_id": "movie:100",
  "title": "The Social network",
  "summary": "On a fall night in 2003, Harvard undergrad and
     programming genius Mark Zuckerberg sits down at his
     computer and heatedly begins working on a new idea. (...)",
  "year": 2010,
  "director": {"last_name": "Fincher",
                "first_name": "David"},
  "actors": [
    {"first_name": "Jesse", "last_name": "Eisenberg"},
    {"first_name": "Rooney", "last_name": "Mara"}
   ]
}

Comme il serait fastidieux de les insérer un par un, nous allons utiliser l’utilitaire d’import de MongoDB. Il prend en entrée un tableau JSON contenant la liste des objets à insérer. Dans notre cas, nous allons utiliser l’export JSON de la base Webscope dont le format est le suivant.

  [
   {
    "_id": "movie:1",
    "title": "Vertigo",
    "year": "1958",
    "director":       {
          "_id": "artist:3",
          "last_name": "Hitchcock",
          "first_name": "Alfred",
          "birth_date": "1899"
        },
    "actors": [
         {
          "_id": "artist:15",
          "first_name": "James",
          "last_name": "Stewart",
         },
         {
          "_id": "artist:16",
          "first_name": "Kim",
          "last_name": "Novak",
         }
        ]
  },
  {
    "_id": "movie:2",
    "title": "Alien",
    ...
  }
]

En supposant que ce tableau est sauvegardé dans movies.json, on peut l’importer dans la collection movies de la base nfe204 avec la commande suivante:

mongoimport -d nfe204 -c movies --file movies.json --jsonArray

Ne pas oublier l’argument jsonArray qui indique à l’utilitaire d’import qu’il s’agit d’un tableau d’objets à créer individuellement, et pas d’un unique document JSON.

Exercices

Exercice: mise en route de MongoDB

Votre tâche est simple: installer MongoDB, le client RockMongo ou RoboMongo (ou un autre de votre choix), reproduire les commandes ci-dessus et créer une base movies avec nos films. Profitez-en pour vous familiariser avec l’interface graphique.

Vous pouvez également créer une base moviesref avec deux collections: une pour les films et l’autre pour les artistes, les premiers référençant les seconds. Les commandes d’import devraient être les suivantes:

mongoimport -d moviesref -c movies --file movies-refs.json --jsonArray
mongoimport -d moviesref -c artists --file artists.json --jsonArray

S2: requêtes avec MongoDB

Supports complémentaires:

Précisons tout d’abord que le langage de requête sur des collections est spécifique à MongoDB. Essentiellement, c’est un langage de recherche dit “par motif” (pattern). Il consiste à interroger une collection en donnant un objet (le “motif/pattern”, en JSON) dont chaque attribut est interprété comme une contrainte sur la structure des objets à rechercher. Voici des exemples, plus parlants que de longues explications. Nous travaillons sur la base contenant les films complets, sans référence (donc, celle nommée nfe204 si vous avez suivi les instructions précédentes).

Sélections

Commençons par la base: on veut parcourir toute une collection. On utilise alors find() dans argument.

db.movies.find ()

Si’il y a des millions de documents, cela risque de prendre du temps... D’ailleurs, comment savoir combien de documents comprend le résultat?

db.movies.count ()

Comme en SQL (étendu), les options skip et limit permettent de “paginer” le résultat. La requête suivante affiche 12 documents à partir du dixième inclus.

db.movies.find ().skip(9).limit(12)

Implicitement, cela suppose qu’il existe un ordre sur le parcours des documents. Par défaut, cet ordre est dicté par le stockage physique: MongoDB fournit les documents dans l’ordre où il les trouve (dans les fichiers). On peut trier explicitement, ce qui rend le résultat plus déterministe. La requête suivante trie les documents sur le titre du film, puis pagine le résultat.

db.movies.find ().sort({"title": 1}).skip(9).limit(12)

La spécification du tri repose sur un objet JSON, et ne prend en compte que les noms d’attribut sur lesquels s’effectue le tri. La valeur (ici, celle du titre) ne sert qu’à indiquer si on trie de manière ascendante (valeur 1) ou descendante (valeur -1).

Attention, trier n’est pas anodin. En particulier, tout tri implique que le système constitue l’intégralité du résultat au préalable, ce qui induit une latence (temps de réponse) potentiellement élevée. Sans tri, le système peut délivrer les documents au fur et à mesure qu’il les trouve.

Critères de recherche

Si on connaît l’identifiant, on effectue la recherche ainsi.

db.movies.find ({"_id": "movie:2"})

Une requête sur l’identifiant ramène (au plus) un seul document. Dans un tel cas, on peut utiliser findOne.

db.movies.findOne ({"_id": "movie:2"})

Cette fonction renvoie toujours un document (au plus), alors que la fonction find renvoie un curseur sur un ensemble de documents (même si c’est un singleton). La différence est surtout importante quand on utilise une API pour accéder à MongoDB avec un langage de programmation.

Sur le même modèle, on peut interroger n’importe quel attribut.

db.movies.find ({"title": "Alien"})

Ca marche bien pour des attributs atomiques (une seule valeur), mais comment faire pour interroger des objets ou des tableaux imbriqués? On utilise dans ce cas des chemins, un peu à la XPath, mais avec une syntaxe plus “orienté-objet”. Voici comment on recherche les films de Quentin Tarantino.

db.movies.find ({"director.last_name": "Tarantino"})

Et pour les acteurs, qui sont eux-mêmes dans un tableau? Ca fonctionne de la même manière.

db.movies.find ({"actors.last_name": "Tarantino"})

La requête s’interprète donc comme: “Tous les films dont l’un des acteurs se nomme Tarantino”.

Conformément aux principes du semi-structuré, on accepte sans protester la référence à des attributs ou des chemins qui n’existent pas. En fait, dire “ce chemin n’existe pas” n’a pas grand sens puisqu’il n’y a pas de schéma, pas de contrainte sur la structure des objets, et que donc tout chemin existe potentiellement: il suffit de le créer. La requête suivante ne ramène rien, mais ne génére pas d’erreur.

db.movies.find ({"actor.last_name": "Tarantino"})

Important

Contrairement à une base relationnelle, une base semi-structurée ne proteste pas quand on fait une faute de frappe sur des noms d’attributs.

Quelques raffinements permettent de dépasser la limite sur le prédicat d’égalité implicitement utilisé ici pour comparer les critères donnés et les objets de la base. Pour les chaînes de caractères, on peut introduire des expressions régulières. Tous les films dont le titre commence par Re? Voici:

db.movies.find ({"title": /^Re/}, {"actors": null, "summary": 0} )

Pas d’apostrophes autour de l’expression régulière. On peut aussi effectuer des recherches par intervalle.

db.movies.find( {"year": { $gte: "2000", $lte: "2005" } }, {"title": 1} )

Projections

Jusqu’à présent, les requêtes ramènent l’intégralité des objets satisfaisant les critères de recherche. On peut aussi faire des projections, en passant un second argument à la fonction find().

db.movies.find ({"actors.last_name": "Tarantino"}, {"title": true, "actors": 'j'} )

Le second argument est un objet JSON dont les attributs sont ceux à conserver dans le résultat. La valeur des attributs dans cet objet-projection ne prend que deux interprétations. Toute valeur autre que 0 ou null indique que l’attribut doit être conservé. Si on choisit au contraire d’indiquer les attributs à exclure, on leur donne la valeur 0 ou null. Par exemple, la requête suivante retourne les films sans les acteurs et sans le résumé.

db.movies.find ({"actors.last_name": "Tarantino"}, {"actors": null, "summary": 0})

Opérateurs ensemblistes

Les opérateurs du langage SQL in, not in, any et all se retrouvent dans le langage d’interrogation. La différence, notable, est que SQL applique ces opérateurs à des relations (elles-mêmes obtenues par des requêtes) alors que dans le cas de MongoDB, ce sont des tableaux JSON. MongoDB ne permet pas d’imbriquer des requêtes.

Voici un premier exemple: on cherche les films dans lesquels joue au moins un des artistes dans une liste (on suppose que l’on connaît l’identifiant).

db.artists.find({"actors._id": {$in: ["artist:34","artist:98","artist:1"]}})

Gardez cette recherche en mémoire: elle s’avèrera utile pour contourner l’absence de jointure en MongoDB. Le in exprime le fait que l’une des valeurs du premier tableau (actors._id) doit être égale à l’une des valeurs de l’autre. Il correspond implicitement, en SQL, à la clause ANY. Pour exprimer le fait que toutes les valeurs de premier tableau se retrouvent dans le second (en d’autres termes, une inclusion), on utilise la clause all.

db.movies.find({"actors._id": {$all: ["artist:23","artist:147"]}})

Le not in correspond à l’opérateur $nin.

db.artists.find({"_id": {$nin: ["artist:34","artist:98","artist:1"]}})

Comment trouver les films qui n’ont pas d’attribut summary?

db.movies.find({"summary": {$exists: false}}, {"title": 1})

Opérateurs Booléens

Par défaut, quand on exprime plusieurs critères, c’est une conjonction (and) qui est appliquée. On peut l’indiquer explicitement. Voici la syntaxe (les films tournés avec Leonardo DiCaprio en 1997):

db.movies.find({$and : [{"year": "1997"}, {actors.last_name: "DiCaprio"]} )

L’opérateur and s’applique à un tableau de conditions. Bien entendu il existe un opérateur or avec la même syntaxe. Les films parus en 1997 ou avec Leonardo DiCaprio.

db.movies.find({$or : [{"year": "1997"}, {actors.last_name: "DiCaprio"]} )

Voici pour l’essentiel en ce qui concerne les recherches portant sur une collection et consistant à sélectionner des documents. Grosso modo, on obtient la même expressivité que pour SQL dans ce cas. Que faire quand on doit croiser des informations présentes dans plusieurs collections? En relationnel, on effectue des jointures. Avec Mongo, il faut bricoler.

Jointures

La jointure, au sens de: associer des objets distincts, provenant en général de plusieurs collections, pour appliquer des critères de recherche croisés, n’existe pas en MongoDB. C’est une limitation très importante du point de vue de la gestion de données. On peut considérer qu’elle est cohérente avec une approche documentaire dans laquelle les documents sont supposés indépendants les uns des autres, avec une description interne suffisamment riche pour que toute recherche porte sur le contenu du document lui-même. Cela étant, on peut imaginer toutes sortes de situations où une jointure est nécessaire dans une aplication de traitement de données.

Le serveur ne sachant pas effectuer de jointures, on en est réduit à les faire côté client, comme illustré sur la figure Jointure côté serveur et côté client. Cela revient essentiellement à appliquer l’algorithme de jointures par boucle imbriquées en stockant des données temporaires dans des structures de données sur le client, et en effectuant des échanges réseaux entre le client et le serveur, ce qui dans l’ensemble est inefficace.

_images/jointure-serveur-client.png

Jointure côté serveur et côté client

Comme l’interpréteur mongo permet de programmer en Javascript, nous pouvons en fait illustrer la méthode assez simplement. Considérons la requête: “Donnez tous les films dont le directeur est Clint Eastwood”.

Note

Nous travaillons sur la base moviesref dans laquelle un film ne contient que la référence au metteur en scène, ce qui évite les redondances, mais complique la reconstitution de l’information.

La première étape dans la jointure côté client consiste à chercher l’artiste Clint Eastwood et à le stocker dans l’espace mémoire du client (dans une variable, pour dire les choses simplement).

eastwood = db.artists.findOne({"first_name": "Clint", "last_name": "Eastwood"})

On dispose maintenant d’un objet eastwood. Une seconde requête va récupérer les films dirigés par cet artiste.

db.movies.find({"director._id": eastwood['_id']}, {"title": 1})

Voilà le principe. Voyons maintenant plus généralement comment on effectue l’équivalent des jointures en SQL. Prenons la requête suivante:

select m.titre, a.*  from Movie m, Artist a
where m.id_director = a.id

On veut donc les titres des films et le réalisateur. On va devoir coder, du côté client, un algorithme de jointure par boucles imbriquées. Le voici, sous le shell de MongoDB (et donc en programmation javascript).

var lesFilms = db.movies.find()
while (lesFilms.hasNext()) {
  var film = lesFilms.next();
  var mes = db.artists.findOne({"_id": film.director._id});
  printjson(film.title);
  printjson(mes);
}

On a donc une boucle, et une requête imbriquée, exécutée autant de fois qu’il y a de films. C’est exactement la méthode qui serait utilisée par le serveur si ce dernier implantait les jointures. L’exécuter du côté client induit un surcoût en programmation, et en échanges réseau entre le client et le serveur.

Exercices

Exercice: requêtes sur la base des films.

Sur votre base movies,

  • tous les titres;
  • tous les titres des films parus après 2000;
  • le résumé de Spider-Man;
  • qui est le metteur en scène de Gladiator?
  • titre des films avec Kirsten Dunst;
  • quels films ont un résumé?
  • les films qui ne sont ni des drames ni des comédies.
  • affichez les titres des films et les noms des acteurs.
  • dans quels films Clint Eastwood est-il acteur mais pas réalisateur (aide: utilisez l’opérateur de comparaison $ne).
  • Difficile: Comment chercher les films dont le metteur en scène est aussi un acteur? Pas sûr que ce soit possible sans recourir à une auto-jointure, côté client...

Correction

Correction

  • db.movies.find({}, {"title": 1})
  • db.movies.find({"year": {$gt: "2000"}}, {"title": 1, "year": 1})
  • db.movies.find({"title": "Spider-Man"}, {"summary": 1})
  • db.movies.find({"title": "Gladiator"}, {"director": 1})
  • db.movies.find({"actors.last_name": "Dunst"}, {"title": 1})
  • db.movies.find({"summary": {$exists: true}}, {"title": 1})
  • db.movies.find({"genre": {$nin: ["Drame", "Comédie"]}}, {"title": 1, "genre": 1})
  • db.movies.find({}, {"title": 1, "actors.first_name": 1, "actors.last_name": 1})
  • db.movies.find({"actors.last_name": "Eastwood", "director.last_name": {$ne: "Eastwood"}}, {"title": 1})

Exercice: requêtes sur votre base

Si vous avez constitué une base de documents JSON (bureautique, météo, données géolocalisées Google), je vous encourage à l’importer dans MongoDB et à tester des requêtes qui vous semblent typique d’une application basée sur ces données.

S3: MapReduce et MongoDB

Supports complémentaires:

Les requêtes vues jusqu’à présent prennent en entrée une collection et produisent en sortie un sous-ensemble des documents de la collection, eux-même éventuellement “réduits” par une projection.

Nous abordons maintenant un processus plus complet pour le traitement d’une collection, que nous allons appeler chaîne de traitement par traduction de “data processing pipelines”. Le principe général est de soumettre chaque document d’une collection à une séquence d’opérations, comme par exemple:

  • un filtrage, en ne gardant le document que s’il satisfait certains critères;
  • une restructuration, en changeant la forme du document;
  • une annotation, par ajout au document de propriétés calculées;
  • un regroupement avec d’autres documents sur certains critères;
  • des opérations d’agrégation sur des groupes de documents.

Une chaîne de traitement permet entre autres de calculer des agrégations, comme le group by de SQL. Leur pouvoir d’expression va au-delà, notamment par la possibilité d’ajouter en cours de route des attributs calculés, ou de changer complètement la structure des informations manipulées. Enfin, et c’est essentiel, ces chaînes sont conçues pour pouvoir s’exécuter dans un environnement distribué, avec un effet de passage à l’échelle obtenu par la parallélisation. Ce dernier aspect sera abordé ultérieurement.

La spécification d’une chaîne de traitement s’appuie sur un paradigme nommé MapReduce que nous rencontrerons de manière récurrente. Nous nous en tenons au contexte centralisé (un seul serveur) dans ce qui suit, ce qui permet d’introduire les concepts sans les surcharger.

MapReduce: le principe

Le principe est ancien et provient de la programmation fonctionnelle. Il se résume ainsi: étant donné une collection d’items (ça peut être n’importe quoi – pour nous ce sera des documents), on va appliquer un traitement en deux phases:

  • dans la première phase (map), une fonction \(F_{map}\) est appliquée à chaque item de la collection, et produit une valeur placée dans un accumulateur (une zone mémoire);
  • dans une seconde phase, les valeurs placées dans l’accumulateur sont traitées par une fonction d’agrégation (reduce) \(F_{red}\), produisant une valeur finale.

Un exemple très simple est le count(): durant la phase de map on produit la valeur 1 que l’on place dans l’accumumateur; durant la phase de reduce on fait la somme: le résultat est le nombre d’items. En SQL, cela donnerait

select count(*) from Collection

Un premier raffinement consister à partitionner les valeurs produites par le map en plusieurs groupes. Il suffit de modifier la fonction \(F_{map}\) pour qu’elle produise non plus une valeur, mais une paire (k, v), où k est l’identifiant du groupe et v la valeur à placer dans le groupe. L’identifiant du groupe est déterminé à partir de l’item traité. Si, par exemple, l’item a un attribut année, on peut créer un groupe par année en produisant la paire (année, item) avec \(F_{map}\). Avec ce raffinement, la fonction \(F_{red}\) s’applique à chaque groupe. Si c’est la fonction count() par exemple, on obtient l’équivalent de la requête SQL suivante.

select count(*) from Collection group by annee

Second raffinement: au lieu de produire une valeur pour un item, la fonction \(F_{map}\) peut “émettre” 0, 1 ou plusieurs valeurs. Par exemple, si l’item en entrée est un texte, \(F_{map}\) peut émettre une paire (clé, valeur) pour chaque terme rencontré dans le texte, la valeur étant un indicateur comme, par exemple, le nombre d’occurrences du terme. Cette fois il n’y a plus d’équivalent SQL: MapReduce s’apparente au group by dans le mécanisme de calcul, mais la possibilité d’appliquer des fonctions quelconques, et celle de restructurer complètement les données pendant la phase de map, le rendent beaucoup plus puissant.

Un traitement MapReduce repose sur la notion de fonction de second ordre. Pas de panique: cela signifie simplement que l’environnement (framework) fournit deux fonctions, map() et reduce(), qui prennent chacune en entrée, respectivement, les fonctions \(F_{map}\) et \(F_{red}\) mentionnées ci-dessus. Ce sont des fonctions qui prennent en argument d’autres fonctions et les appliquent aux données, d’où la notion de “second-ordre”.

Note

Pour votre culture: la caractérisation d’un framework (du moins quand on est attaché à utiliser un vocabulaire précis) est justement celle d’un environnement basé sur un modèle d’exécution pré-défini. Ce modèle applique des fonctions fournies par le développeur qui n’est donc pas en charge du contrôle (pris en charge par le framework) mais de la spécification. On parle d’inversion de contrôle, et un exemple typique est fourni par les frameworks MVC. Fin de la parenthèse.

Résumons avec la figure MapReduce (en centralisé), et plaçons-nous maintenant dans le cadre de nos bases documentaires. Nous avons une collection de documents \(d_1, d_2, \cdots, d_n\). La fonction \(F_{map}\) produit, de manière générale, des documents \(dj_i\) (notez les doubles flêches: un document en entrée peut engendrer plusieurs documents en sortie du map) et les place dans un groupe \(G_j, j \in [1, k]\). Quand la phase de map est terminée (et pas avant!), on peut passer à la phase de reduce qui applique successivement \(F_{red}\) aux documents de chaque groupe. On obtient, pour chaque groupe, une valeur (un document de manière générale) \(v_j\).

_images/mapreduce-mongo.png

MapReduce (en centralisé)

Voici pour la théorie. En complément, notons dès maintenant que ce mécanisme a une double propriété extrêmement intéressante:

  • il est très générique,
  • il se parallélise très facilement.

Pour ce dernier aspect, il est important que chaque document soit traité indépendamment du contexte. Concrètement, l’application de \(F_{map}\) à un document d doit donner un résultat qui ne dépend ni de la position de d dans la collection, ni de ce qui s’est passé avant ou après dans la chaîne de traitement, ni de la machine ou du système, etc. En pratique, cela signifie que la fonction \(F_{map}\) ne conserve pas un état qui pourrait varier et influer sur le résultat produit quand elle est appliquée à d.

Si cette propriété n’était pas respectée, on ne pourrait pas paralléliser et conserver un résultat invariant. Si \(F_{map}\) dépendait par exemple du système d’exploitation, de l’heure, ou de n’importe quelle variable extérieure au document traité (un état), l’exécution en parallèle aboutirait à des résultats non déterministes.

Passons à la pratique, en restant dans un contexte centralisé.

Un premier exemple

Nous allons produire un document par réalisateur, avec la liste des films qu’il/elle a réalisé. Conceptuellement, nous créons un groupe par réalisateur, plaçons dans ce groupe les films pendant la phase de map et construisons le document final dans la phase de reduce.

La spécification consiste à définir les deux fonctions à appliquer (\(F_{map}\) et \(F_{red}\)). Voici la fonction de map.

var mapRealisateur = function() {
              emit(this.director._id, this.title);
      };

En javascript, les fonctions peuvent se stocker dans des variables. L’instruction emit produit une paire (clé, valeur), constituée ici de l’identifiant du réalisateur, et du titre du film. Notez que la fonction ne prend aucun argument: implictement, elle dispose comme contexte du document auquel elle s’applique, désigné par this. Et c’est tout.

Voici la fonction de reduce.

var reduceRealisateur = function(directorId, titres) {
   var res = new Object();
   res.director = directorId;
   res.films = titres;
   return res;
 };

Une fonction de reduce prend deux arguments: l’identifiant du groupe auquel elle s’applique (ici, directorId) et la liste (un tableau en javascript) des valeurs produites par le map.

Dans notre exemple, nous construisons la valeur de résultat comme un objet res auquel on affecte deux propriétés: director et titres.

Il ne reste plus qu’à lancer un traitement, avec la fonction mapReduce sur la collection movies. Voici la syntaxe.

db.movies.mapReduce(mapRealisateur,  reduceRealisateur, {out: {"inline": 1}} )

Le premier paramètre est la fonction de map, le second la fonction de reduce, et le troisième indique la sortie, ici l’écran.

À ce stade vous brûlez sans doute d’envie de tester cette exécution. Allez-y: vous devriez obtenir, pour chaque groupe, un résultat de la forme suivante.

{
        "_id" : "artist:3",
        "value" : {
                "director" : "artist:3",
                "films" : [
                        "Vertigo",
                        "Psychose",
                        "Les oiseaux",
                        "Pas de printemps pour Marnie",
                        "Fenêtre sur cour",
                        "La mort aux trousses"
                ]
        }
}

Devinez de quel réalisateur il s’agit? Ici, ça se devine (?), mais en général on aimerait bien disposer au moins du nom. Reportez-vous aux exercices.

MongoDB propose plusieurs options pour l’exécution d’un traitement MapReduce. La plus utile (et la plus générale, présente dans tous les systèmes) consiste à prendre en entrée non pas une collection entière, mais le résultat d’une requête. On passe pour cela un objet query dans le document-paramètre en troisième position. Voici un exemple.

db.movies.mapReduce(mapRealisateur,  reduceRealisateur,
         {out: {"inline": 1}, query: {"country": "USA"}} )

Une autre possibilité intéressante est le calcul incrémental d’un traitement MapReduce. En bref, on peut stocker le résultat dans une nouvelle collection, avec mettre à jour cette collection, sans avoir à tout recalculer, quand de nouveaux documents apparaissent dans la collection en entrée. Il s’agit d’une spécificité MongoDB, donc nous n’allons pas insister dessus: reportez-vous à la documentation.

Jointures avec MapReduce

MapReduce est un mécanisme de base qui peut être utilisé pour implanter des opérateurs de plus haut niveau. La méthode utilisée pour transposer une opération comme la jointure en MapReduce n’est pas forcément très élégante, mais elle a le mérite de bénéficier de la scalabilité du calcul (par parallélisation/distribution) dans des systèmes conçus pour gérer de grands vollumes de données. Elle est aussi représentative de la transposition en MapReduce de traitements plus sophistiqués, même si elle passe par des contournements peu satisfaisants.

Nous montrons donc cette méthode. Notre base est celle contenant les films avec références, et nous avons déjà vu que la technique consistant à implanter côté client, bien qu’effective, ne passe pas à l’échelle.

Le but est de partir des films avec une référence vers l’artiste / réalisateur, et d’obtenir pour chaque film le document complet représentant ce réalisateur (nom, date de naissance, etc.)

Première étape: nous devons accéder dans un même traitement MapReduce aux films (dans movies) et aux artistes (dans artists). Malheureusement, le MapReduce de MongoDB semble ne pouvoir prendre qu’une seule collection en entrée (les autres systèmes n’ont pas cette limitation). Nous allons donc commencer par copier les données dans une collection commune, nommée jointure:

mongoimport -d moviesref -c jointure --file movies-refs.json --jsonArray
mongoimport -d moviesref -c jointure --file artists.json --jsonArray

Voici maintenant le code des deux fonctions de map et de reduce. La fonction de map est donnée ci-dessous: essayez de la comprendre, en vous aidant des commentaires internes donnés par la suite.

var mapJoin = function() {
  // Est-ce que la clé du document contient le mot "artist"?
  if (this._id.indexOf("artist") != -1) {
    // Oui ! C'est un artiste. Ajoutons-lui son type.
    this.type="artist";
    // On produit une paire avec pour clé celle de l'artiste
    emit(this._id, this);
  }
  else {
    // Non: c'est un film. Ajoutons-lui son type.
   this.type="film";
   // Simplifions un peu le document pour l'affichage
   delete this.summary;
   delete this.actors;
    // On produit une paire avec pour clé celle du metteur en scène
   emit(this.director._id, this);
 }
};

Donc, la fonction s’appliquera en entrée à notre collection jointure qui contient maintenant des documents artistes et des documents films. La fonction doit d’abord savoir à quel type de document elle a affaire. Dans notre cas, c’est simple, les clés des artistes sont de la forme artist:xx et les clés des films de la forme movie:yy. C’est ce que teste la fonction Javascript indexOf.

La fonction produit donc, à l’attention du reduce, soit un document artist, soit un document film (notez que nous les “annotons” avec leur type pour rendre les choses plus faciles ensuite). Nous voulons regrouper les metteurs en scène avec les films qu’ils/elles ont réalisés: on y arrive en émettant les documents à regrouper avec la même valeur de clé.

Ici, on émet les artistes avec leur identifiant, et les films avec l’identifiant de leur metteur en scène. Le résultat est donc bien celui souhaité. Si cela vous semble obscur, réfléchissez soigneusement et prenez un exemple.

Note

Et pour les artistes qui n’ont jamais réalisé de film? Et bien ils seront solitaires dans leur groupe. On n’a pas vraiment moyen de les éliminer à ce stade, car on ne sait pas décider si un artiste, considéré isolément, est ou non un réalisateur.

Il s’agit du mécanisme de base d’une implantation à base de MapReduce. Le préalable à toute manipulation conjointe de documents distincts est de le regrouper avec le map pour les traiter ensemble avec le reduce.

Voici maintenant la fonction de reduce.

var reduceJoin = function(id, items) {

  var director = null, films={result: []}

  // Commençons par chercher l'artiste dans cette liste
  for (var idx = 0; idx < items.length; idx++) {
    if (items[idx].type=="artist") {
         director = items[idx];
     }
  }

  // Maintenant, 'director' contient l'artiste : on l'affecte aux films
  for (var idx = 0; idx < items.length; idx++) {
     if (items[idx].type=="film"  && director != null) {
         items[idx].director = director;
         films.result.push (items[idx]);
      }
   }
   return films;
 };

On dispose en entrée d’une liste “d’items”, dont on sait qu’elle contient un artiste (au plus) et des films (peut-être aucun, peut-être plusieurs). On effectue donc la jointure localement. On identifie d’abord le metteur en scène, et on le place dans la variable director. Puis on affecte ce document à l’attribut director de chaque film.

On retourne finalement un objet films contenant le résultat de la jointure locale. Pour des raisons liées à des limitations du MapReduce sous MongoDB, nous ne pouvons pas (i) émettre plusieurs documents dans une exécution de la fonction ou même (ii) émettre un tableau de documents. Nous avons donc dû “encapsuler” ce tableau dans la valeur retournée. Vous étiez prévenu: ce n’est pas très élégant.

Il reste à exécuter ce traitement MapReduce, avec l’instruction suivante.

db.jointure.mapReduce(mapJoin, reduceJoin, {out: {"inline": 1}});

Regardez bien le résultat. La fonction de reduce produit des paires clé-valeur, la clé étant l’identifiant de l’artiste, et la valeur est celle produite par notre fonction reduce(). Dans le cas des artistes qui ne sont pas réalisateurs, l’artiste est émis tel quel: MongoDB n’appelle pas la fonction reduce() pour des groupes contenant un seul document.

Ce qu’il faut retenir avant tout, c’est le mécanisme qui permet d’associer des documents initialement distincts. MapReduce n’étant pas conçu (au départ) pour ce genre de manipulation, il faut accepter quelques inconvénients, et bricoler quelque peu. Ici, l’application client devrait “nettoyer” le résultat obtenu, mais pour l’essentiel l’objectif visé est atteint.

Exercices

Exercice: implanter le sum().

Implantez en MapReduce le calcul équivalent à

select sum(*) from movies

Puis faites la même chose pour

select sum(*) from movies group by genre

Exercice: afficher le nom du réalisateur

Reprenez l’exemple (mapRealisateur, joinRealisateur), et effectuez les modifications suivantes:

  • modifiez les fonctions pour afficher le nom du réalisateur avec la liste de ses films. (Astuce: la clé émise par la fonction de map peut être un objet avec plusieurs valeurs).
  • appliquez le traitement aux films français parus avant 2000 (attention, les années sont codées comme des chaînes de caractères).

Exercice: compter les termes d’un texte

Objectif: construire un groupe pour chaque terme (mot) apparaissant dans le titre d’un film, et lui associer des informations. Voici une version de base. La fonction de map:

var mapTermes = function() {
  var tokens = this.title.match(/\S+/g)
  for (var i = 0; i < tokens.length; i++) {
           emit(tokens[i], this.title);
   }
}

La fonction de reduce:

var reduceTermes = function(terme, titres) {
   var res = new Object();
   res.terme = terme;
   res.titres = titres;
   return res;
};

Commencez par vérifier que cela fonctionne, regardez les mots qui apparaissent dans plusieurs titres. Ensuite, traitez le résumé de chaque film, et faites les calculs suivants:

  • Pour chaque terme, affichez le titre du film et le nombre d’occurrences dans le résumé du film.
  • Pour chaque terme, affichez de plus le nombre total d’occurences du terme dans la collection.
  • Enfin, identifiez les termes qui apparaissent très souvent et sont peu significatifs (“de”, “un”, “le”, etc.). Faitez-en une liste et éliminez-les du résultat.

Quand vous serez arrivés au bout, vous aurez fait un bon pas vers un algorithme de construction d’un index plein texte sur votre base documentaire.

Exercice: classification de documents (basique)

Nous voulons grouper les films. Ecrivez le traitement MapReduce pour

  • un classement par genre,
  • un classement par décennie (les années 70, les années 80, etc.)

Si vous vous sentez en forme, réflechissez au problème suivant: comment appliquer un algorithme de classification kMeans sur les films (pour les grouper par période par exemple) ou les artistes (les grouper par génération par exemple). Bon brainstorming, mais pas d’inquiétude, nous y reviendrons.

Exercice: encore une jointure

Reprenez l’implantation de la jointure décrite précédemment, et transformez-là pour calculer celle des films et des acteurs.