Calculer sur des données massives

Le logiciel MapReduce a été inventé au Google Labs en 2004. Depuis, avec Hadoop, un environnement open-source, il est devenu très populaire.

Pour l’illustrer, nous allons considérer des calculs que doit faire une société, appelons-la N., qui propose des films et séries télévisées sur Internet. Toute ressemblance avec Netflix est évidemment fortuite.

Vidéo produite par wandida.com – Intervenant : Serge Abiteboul, édition : El Mahdi El Mhamdi – Creative Commons BY-NC-SA.

Le problème à résoudre

Supposons que N. a 200 000 films à son catalogue, 50 millions de clients et que chaque client a visionné en moyenne 20 films, qu’il a notés. Supposons aussi que N. veuille calculer pour chaque film la moyenne des notes. Cette tâche est « modeste » pour ce qui est de la quantité de données ; ce n’est pas encore vraiment du Big data. Elle est très simple comparée à d’autres tâches, comme de trouver des proximités de goût entre clients. Même si MapReduce, c’est quand même lourd pour ce « petit » problème, cet exemple nous permettra d’illustrer la technique.

Formalisons légèrement le problème :

• En entrée (Input), nous avons une relation Notes de 20 × 50 millions = 1 milliard d’enregistrements de la forme (Serge Tournesol, Manhattan, 4.5), c’est-à-dire, « Serge Tournesol a donné la note de 4.5 (sur 5) au film Manhattan ».
• En sortie (Output), nous voulons une relation Moyenne de 200 000 enregistrements de la forme (Manhattan, 4.1), c’est-à-dire, « La moyenne du film Manhattan est de 4.1 parmi les clients de N. ».

Un programmeur sait résoudre ce problème en écrivant un programme. Il va, par exemple, ordonner Notes en suivant l’ordre lexicographique sur les titres de films, puis parcourir la séquence obtenue et enfin, pour chaque film, dont les notes sont maintenant regroupées, calculer la moyenne. Ce programme, appelons-le P_mini. Le seul problème est que P_mini prendrait énormément de temps sur un seul ordinateur avec un milliard d’enregistrements. Alors, nous allons utiliser 1000 ordinateurs et MapReduce. Map est pris dans le sens de « transformer », et Reduce signifie « réduire ».

La technique

Nous allons partager le travail à faire entre un grand nombre d’ordinateurs. Nous allons distinguer deux catégories de travailleurs : les ordi-mappers et les ordi-reducers. Pour simplifier, prenons 500 de chaque. Nous allons utiliser trois programmes, mapper, reducer, et laposte.

Confions tout d’abord à chaque ordi-mapper un 1/500^e des comptes client. Quel est le rôle du programme mapper, qui tourne sur chaque ordi-mapper ? Sa tâche est très simple. Pour chacun des clients sous sa responsabilité, il va lire sur disque les évaluations de ce client et construit les enregistrements de Notes correspondants. Il va donc construire environ deux millions d’enregistrements de notes. Puis il transmet ces enregistrements au programme laposte qui tourne sur le même ordi-mapper que lui.

Comment fonctionne le programme laposte ?  Pour chaque enregistrement, ce programme applique une fonction H (pour hachage) au titre du film ; cette fonction lui retourne un nombre entier « aléatoire » entre 1 et 500. Si ce nombre est 1, laposte l’envoie au premier ordi-reducer, si c’est 2 au second, …, si c’est 500 au 500^e. Une « fonction de hachage », c’est un programme que vous trouvez facilement sur le Web. Vous lui donnez le titre d’un film, elle vous donne un entier entre 1 et 500, sans que vous ayez besoin de savoir comment elle le calcule. Pour que tout le travail n’aille pas au même ordi-reducer, la fonction choisit le plus aléatoirement possible entre tous les nombres entre 1 et 500. Un point important, c’est que la fonction ne change jamais d’avis. Si pour Manhattan, elle a répondu 333, si le même mapper ou un autre mapper pose encore la question pour Manhattan, la fonction retourne le même entier. Donc, tous les enregistrements pour un film particulier vont se retrouver sur le même ordi-reducer (le 333^e pour Manhattan).

Entre en scène le programme reducer, qui tourne sur un ordi-reducer.  Chaque ordi-reducer a maintenant environ 1/500^e du problème, parce que le travail a été partagé relativement équitablement. Comme il n’a qu’environ deux millions d’enregistrements (1 milliard/500) à traiter, chaque ordi-reducer peut maintenant résoudre sa partie du problème avec le programme reducer qui est quasiment l’équivalent de P_mini. Le résultat Moyenne consiste donc en 500 morceaux, un sur chaque ordi-reducer.

Que faut-il faire pour programmer tout ça ?

1. Écrire le programme mapper, quelques lignes de code. Ici mapper ne fait quasiment rien que construire la relation Notes et appeler le programme laposte.
2. Écrire le programme reducer, encore quelques lignes de code. C’est essentiellement le programme P_mini.

Il n’y a pas besoin d’écrire le programme laposte, qui distribue les données entre les ordi-reducers. En effet, quelqu’un a écrit ce programme une fois pour toutes, pour l’inclure dans le logiciel MapReduce. Il suffit donc d’utiliser ce logiciel. Pour que tout cela fonctionne, MapReduce fait beaucoup d’autres choses. Par exemple, il gère les pannes. Quand un ordinateur est défaillant, il sait détecter la panne, et demander à un autre ordinateur de remplacer celui qui est défaillant.

Pour résoudre notre problème, nous avons utilisé le travail de nombreuses machines et les programmes que d’autres ont écrit avant nous. L’informatique, une science pour fainéant ? Ce n’est pas faux. Des fainéants qui peuvent être géniaux quand ils inventent MapReduce…

Pour aller plus loin

• Web Data Management, chapitre Distributed Computing with MapReduce and Pig Latin (en accès libre).
• MapReduce pour les nuls, par Philippe Rigaux.
  
• Hadoop  sur Wikipédia (MapReduce, ainsi que d’autres logiciels Google comme GoogleFS et BigTable, a   inspiré l’environnement de programmation Hadoop, un logiciel libre très populaire).