MapReduce est un schéma de développement (design pattern) proposé par Google en 2004 permettant de traiter de gros volumes de données de manière parallèle et distribuée (merci Wikipédia). D’accord, mais une fois qu’on a dit ça, on est bien avancés. Je vous propose, dans le contenu qui va suivre, d’aborder le problème de fond qui a mené à ce type de solution, et l’application de MapReduce sur un cas simple et que l’on peut se représenter.
Quel est le problème ?
Au cours des 20 dernières années, avec la croissance de l’usage d’internet et de ses applications, les volumes de données stockées, traitées a considérablement grossi. Au point où, pour les stocker, les transporter et les traiter, il n’est plus possible de le faire sur un seul serveur, localisé à un même endroit.
Les données des applications sont donc maintenant distribuées sur plusieurs machines, parfois sur plusieurs pays ou continents. Pour bien comprendre le problème, nous allons l’illustrer avec un exemple simple.
Imaginons une application qui permette de suivre la santé de ses utilisateurs. À ces fins elle conserve pour chaque utilisateur son poids et sa taille. Disons que l’on veut obtenir des données sur l’ensemble de nos utilisateurs, telles que le poids moyen, ou l’IMC moyen. Voici ce à quoi ressemble un utilisateur :
user {
id: 8374702028476,
name: "Pierre Ponce",
weight: 78,
height: 183,
}
Dans une petite application, ces utilisateurs sont stockés dans un SGBD relationnel dont nous avons l’habitude (tel que MySQL, PostgreSQL, Oracle, …). Les données sont donc dans une table, et l’on va opérer dessus en faisant des requêtes SQL sur l’ensemble ou un sous-ensemble du jeu de données. Il est très facile de compter le nombre de d’utilisateurs, obtenir la somme de tous les poids ou de toutes les tailles avec ce type de systèmes. On peut, par exemple, simplement calculer le poids moyen de l’ensemble de nos utilisateurs avec ce genre de requêtes. Je vous laisse me faire confiance, ou faire un tour du coté de SQL pour voir ce qui est possible.
Que se passe-t-il lorsque l’on veut faire ce type de traitement mais que les données sont distribuées pour des questions de volume, de proximité géographique ou de performances ? Comment utiliser les ressources parallèles de nos infrastructures pour accélérer ces traitements ?
On ne peut effectivement pas transférer toutes les données au même endroit pour faire ces calculs …
Quelques pistes
En se creusant un peu la tête on peut avoir une idée d’approche. Dans notre cas de poids moyen, il suffit de s’intéresser aux propriétés de la moyenne. Pour des utilisateurs A, B, …, F, le poids moyen se calcule de la manière suivante :
Mais on peut aussi le calculer de la manière suivante :
Ça commence à ressembler à un calcul distribué ça non ? Si on considère que les données de nos utilisateurs sont distribuées sur plusieurs serveurs, on peut tout à fait commencer par calculer une moyenne localement sur chacun, et ensuite terminer le calcul autre part. On a ainsi distribué le travail, et transféré peu de données à la fin. En conservant ça à l’esprit, on peut attaquer MapReduce.
Le principe de MapReduce
Le principe de cette méthode est d’appliquer deux opérations map() et reduce(). pour traiter le problème.
L’opération map() a pour but de nous aider à de découper le problème initial en sous problèmes plus petits et traitables en parallèle. Elle prend en général en entrée une donnée et produit un à plusieurs couples (clé, valeur) qui seront ensuite traités par reduce(). map() peut ainsi être réalisée simultanément sur un grand nombre de données, là où elles se trouvent.
Les données émises sont groupées par clés avant d’être fournies à reduce(), par exemple :
(key_1, "value_a") (key_2, "value_b") (key_1, "value_c")
deviendra :
(key_1, ["value_a", "value_c"]) (key_2, ["value_b"])
On peut alors appliquer reduce() sur ces nouveaux couples (clef, liste de valeurs) et pour chacun d’entre eux, et calculer une valeur finale. Là aussi, cette opération peut être réalisée en parallèle sur chaque couple. Nous allons voir une application dans les paragraphes suivants. Pour plus de détails sur la partie théorique, je vous invite à lire la publication de Google sur le sujet.
Application
Partons d’un ensemble de clients dont nous avons quelques informations corporelles, et nous souhaitons calculer l’IMC moyen de notre groupe d’utilisateurs. Pour rappel l’IMC se calcule de la manière suivante :
Voici quelques utilisateurs :
{id: 7638, name: "Pierre", height: 1.78, weight: 76},
{id: 5932, name: "Arthur", height: 1.83, weight: 65},
{id: 213, name: "Susanne", height: 1.65, weight: 58},
...
Voici l’implémentation de map() que nous allons appliquer :
map(Client c) {
imc = c.weight / (c.height * c.height);
// Emit is the classic way for map() to produce (key, value)
emit("imc", imc);
}
Nous obtenons alors les couples suivants :
("imc", 23.99)
("imc", 19.41)
("imc", 21.30)
Qui seront transformés de la manière suivante avant d’être transmis à reduce() :
("imc", [23.99, 19.41, 21.30])
Voici l’implémentation de reduce() que l’on va appliquer :
reduce(key, values[]) {
sum = 0;
count = 0;
for (v in values) {
sum += v;
count++;
}
// Emit is the classic way for reduce() to produce the final value
emit(sum/count);
}
Le résultat de notre map/reduce est donc bien l’IMC moyen de notre ensemble d’utilisateurs.
Ici on voit bien que les map() sont exécutables en parallèle car les données en entrée sont indépendantes. Ils peuvent être exécutés sur les machines où sont stockées les données, et avec toutes les capacités de calcul disponibles localement. Par la suite, reduce() peut aussi être exécuté localement sur les résultats de map() collectés. Il faudra alors terminer le calcul de moyenne en récupérant les résultats de ce map/reduce. Mais devinez quoi ? Il ne reste que très peu de données à regrouper et calculer !
Pour creuser le problème, je vous invite à consulter les références listées ci-dessous, vous aurez ainsi plus de détails ainsi que des exemples d’implémentations.
Remerciements
À Ningyu Li qui a toujours soif d’apprendre et m’a obligé à mettre mes idées en ordre sur le sujet.