Latest revision as of 10:44, 22 November 2013

Présentation

Titre : Big Data et MapReduce
Auteur : Marion Dalle <Marion.Dalle@e.ujf-grenoble.fr>
Enseignants : Georges-Pierre Bonneau, Didier Donsez (EA2013)
Télécharger : File:MapReduce.pdf

Abstract

MapReduce is a programming model for distributed large datas. The computation is parallelize across large-scale clusters of machines. It take place in the univers of Big Data. This paradigm was popularize by Google. It uses by great webs sites in majority for commercial purpose like Facebook and Amazon. Users specify the computation in terms of a map and a reduce function. It is based on the master slave model, with master replication to conserve datas. That gives it a fault detection and know handle its.

Keywords

Big Data, data mining, programming model

Résumé

MapReduce est un patron d’architecture de développement informatique pour le calcul parallèle et distribué de données importantes. Il fait partie des traitements célèbre de l'univers du Big Data. Il a été popularisé par Google et est utilisé par d'autre site très célèbre comme Amazon et Facebook. Il permet de traiter un volume de données très importants. Son implémentation est faites de tel sorte qu'il détecte les pannes et sait les contourner. Il est basé sur le modèle de maître esclaves avec une réplication du maître, ce qui permet d'assurer la pérennité de nos données. Et il fonctionne avec seulement deux fonctions : Map et Reduce.

Mots-clés

Big Data, Data mining, Patron d'architecture, traitement de donnée

Synthèse

Big Data

Depuis quelques années, nous entendons parler du Big Data. Ce nouveau domaine est dû à l'explosion des données numériques. En effet, nous pouvons voir que lorsque Niels Amstrong est aller sur la lune il lui a fallu 32KB de mémoire (1969); aujourd'hui mon ordinateur personnel contient 8GB de RAM. Un autre exemple est celui des récoltes de données de Google. En deux ans, Google s'est mis à récolter quotidiennement ce qu'il récoltait en plus d'un mois. Il a donc fallu s’intéresser au traitement de ces dernières. Les bases de données n’étant plus assez performantes pour de tel quantité de données, de nouvel méthode ont été mise au point. C'est dans ce contexte que le MapReduce a été créé.

MapReduce

MapReduce est un patron d’architecture de développement informatique pour la calcul parallèle et distribué de données importante s. Il a été créé en 2004 et rendu célèbre par Google. D'autres site connu l'utilise afin de pouvoir utiliser leur donnée surtout a des fin commerciale. C'est le cas de Facebook et d'Amazon. Pour utiliser le MapReduce et traiter les données il faut déposer ces dernières sur un cluster qui permettra d'effectuer des calculs en parallèles.

Afin d'utiliser MapReduce, il y a des framework conçues pour son implémentation. J'ai pris le choix de m’intéresser à celui conçue par apache, Hadoop. Apache a aussi créé Hive qui un système de gestion d'entrepôts de données (datawarehouse), utilisable avec Hadoop. Ainsi que Mahout qui est un canevas de data mining. Ces algorithmes de regroupement (clustering), classification et filtrage collaboratif sont implémentés au dessus d'Hadoop et utilise le modèle MapReduce.

Les deux fonctions de bases Map() et Reduce()

Le MapReduce est comme son nom l'indique basé sur les deux fonctions Map() et Reduce().

Map()

Elle prend en paramètre des données, les découpes et renvoie une liste de doublons contenant des données rattachées à une clé. Elle est appeler de manière recursive sur chaque élément de la liste alors obtenue jusqu'à obtenir des listes de données où la taille a été assez réduite pour être traité par la fonction Reduce(). Chaque bloc ainsi obtenue est de la même tailles que les autres.

Ce qui nous donne à peu près le schéma suivant :

Reduce()

Prend en paramètre le résultat final de la fonction Map() et une clé qui lui indique quelles données regrouper. Il traite les données alors reçu en paramètre et rend une liste en fonction de la clé demandée. Il permet aussi de regrouper les résultats en un seul et même résultat final.

On a alors le schéma suivant, où les boites oranges sont les Reduce() :

Organisation du travail en nœuds de calcul

La répartition du travail est contrôlé par le maître. Ce dernier fait en sorte que chaque nœuds de calcul libre fassent une fonction en parallèles des autres quand cela est possible. Ce qui permet d'optimiser le temps de calcul. Chaque fonction réalisant un travail indépendant, il n'y a pas de difficulté à distribué les données entre les nœuds. Ce qui nos vaut que dès qu'un nœud a fini son travail le mâitre lui en affecte un autre.

Il est important de préciser que les fonctions sont bloquantes, c'est à dire que quand on débute une fonction il faut la finir dans sa totalité avant de pouvoir passer à un autre travail. Il n'est donc pas possible d'assigner un nouveau travail a un nœud en cours de traitements.

Détecter et réparer les pannes

Le système est organiser de la manière suivante :

Comme on peut le constater le maître et dupliquer afin d'assurer que si il tombe en panne un autre puisse prendre sont relai et qu'on ne perde pas la vue d'ensemble du système qui nous obligerai alors à recommencer tout le travail.

Le maître déclare un nœud mort quand il ne voit plus de résultat envoyé de sa part au bout d'un laps de temps déterminé (Timeout). Il assigne alors son travail au premier nœud de libre.

Les performances

Chaque nœuds doit rentrer les données qu'il reçoit dans sa mémoire locale. Il fait cela pour pouvoir les parser puis les transformer en objet. Toutes ces étapes prenne donc un certain temps non négligeable qui affecte les performances du modèle.
Les nœuds ne gère qu'un seul flot de données, ce qui oblige à avoir un seul éléments en entré et un seul en sorti.
Il n'y a pas non plus d'optimisation au niveau du transfert de données entre les nœuds. Cependant il fait en sorte de faire le Reduce après le Map sur le même nœud car il contient déjà les données en mémoire. Cela évite une surcharge inutile de la bande passante.
L'utilisation de ce paradigme au sein même d'une base de donnée est totalement inutile. En effet, il faut lire la valeur, l'enregistrer, la stocker en paire, alors que le traitement direct via la base de donnée était possible.
Il y aussi le système de planification qui fait baisser les performances. Il permet d'assigner les tâches aux nœuds, mais plus les blocs de données sont importants (en terme de taille) et plus l'algorithme de planification va vite mais plus on a de risque que le MapReduce échoue. Il faut donc trouver le juste milieu entre optimisation du temps d’exécution de cet algorithme et les chances de réussite du traitement.

Les avantages

Ce modèle permet de de gérer de nombreux type de traitements de données comme les fouilles, les graphes et autres. De plus, il est totalement indépendant du système de stockage et du nombre de type de variable dans nos données.

Il permet aussi l'utilisation de deux techniques de décodage des données :

De manière immuable, qui transforme en objet immuable (objet à état non modifiable) ce qui nous donne autant d'objet que de de données. Et c'est celle-ci qui est utilisée par défaut.
De manière mutable, on crée un objet mutable qui est réutilisé pour décoder tous les objet. Cette méthode nous permet de créé un seul objet.

Il y a aussi deux techniques pour la mémorisation des données :

De manière direct, en passant du mémoire en cache à la mémoire en lecture.
Via le streaming qui permet la communication entre les processus.

Quelques examples d'utilisation

Ce paradigme est utilisé pour de nombreux cas comme :

Grep distribué
Tri distribué
Inversion de graphe des liens webs
Classification automatique
Traduction automatique

Démonstration

Voici une petite démonstration donné en exemple dans le framework d'apache Hadoop. Elle consiste a faire un grep sur tous les fichiers de configuration du framework pour retrouver les mots commençant par « dfs ».

Cet démonstration se fait en ligne de commande de la manière suivante :

On formate le système de fichier distribué
- $bin/hadoop namenode -format
On active le démon qui va permettre de faire les calculs
- $bin/start-all.sh
On copie les fichier de configuration (conf) dans le nouveau système de fichier distribué comme donnée d'entrée (input)
- $bin/hadoop fs -put conf input
On lance le grep
- $bin/hadoop jar hadoop-examples-*.jar grep input output 'dfs[a-z.]+'
On récupère le fihier contenant les résultats (output) afin de le mettre en local pour pouvoir le consulter
- $bin/hadoop fd -get output output
On consulte le fichier
- $cat output/*
  - 1 dfs.replication
  - 1 dfs.server.namenode.
  - 1 dfsadmin
On termine en arrêtant le démon
- $bin/stop-all.sh

@@ Line 21: / Line 21: @@
 ==MapReduce==
 MapReduce est un patron d’architecture de développement informatique pour la calcul parallèle et distribué de données importante s. Il a été créé en 2004 et rendu célèbre par Google. D'autres site connu l'utilise afin de pouvoir utiliser leur donnée surtout a des fin commerciale. C'est le cas de Facebook et d'Amazon. Pour utiliser le MapReduce et traiter les données il faut déposer ces dernières sur un cluster qui permettra d'effectuer des calculs en parallèles.
@@ Line 26: / Line 27: @@
 === Les deux fonctions de bases Map() et Reduce() ===
 Le MapReduce est comme son nom l'indique basé sur les deux fonctions Map() et Reduce().
 ====Map()====
 Elle prend en paramètre des données, les découpes et renvoie une liste de doublons contenant des données rattachées à une clé. Elle est appeler de manière recursive sur chaque élément de la liste alors obtenue jusqu'à obtenir des listes de données où la taille a été assez réduite pour être traité par la fonction Reduce(). Chaque bloc ainsi obtenue est de la même tailles que les autres.
@@ Line 32: / Line 35: @@
 Ce qui nous donne à peu près le schéma suivant :
+[[File:map.jpg|centre|400px|alt=Recursivité des Map|Première partie du MapReduce : Map()]]
-[[File:map.jpg]]
 ====Reduce()====
 Prend en paramètre le résultat final de la fonction Map() et une clé qui lui indique quelles données regrouper. Il traite les données alors reçu en paramètre et rend une liste en fonction de la clé demandée. Il permet aussi de regrouper les résultats en un seul et même résultat final.
-On a alors le schéma suivant :
+On a alors le schéma suivant, où les boites oranges sont les Reduce() :
-[[File:MapRed.jpg]]
+[[File:MapRed.jpg|centre|400px|alt=MapReduce|MapReduce]]
-Les boites oranges sont les Reduce()
 ===Organisation du travail en nœuds de calcul===
 La répartition du travail est contrôlé par le maître. Ce dernier fait en sorte que chaque nœuds de calcul libre fassent une fonction en parallèles des autres quand cela est possible. Ce qui permet d'optimiser le temps de calcul. Chaque fonction réalisant un travail indépendant, il n'y a pas de difficulté à distribué les données entre les nœuds. Ce qui nos vaut que dès qu'un nœud a fini son travail le mâitre lui en affecte un autre.
@@ Line 48: / Line 51: @@
 ===Détecter et réparer les pannes===
 Le système est organiser de la manière suivante :
+[[File:Archi.jpg|centre|400px|alt=Architecture du système|Architecture du système]]
+Comme on peut le constater le maître et dupliquer afin d'assurer que si il tombe en panne un autre puisse prendre sont relai et qu'on ne perde pas la vue d'ensemble du système qui nous obligerai alors à recommencer tout le travail.
+Le maître déclare un nœud mort quand il ne voit plus de résultat envoyé de sa part au bout d'un laps de temps déterminé (Timeout). Il assigne alors son travail au premier nœud de libre.
+===Les performances===
+* Chaque nœuds doit rentrer les données qu'il reçoit dans sa mémoire locale. Il fait cela pour pouvoir les parser puis les transformer en objet. Toutes ces étapes prenne donc un certain temps non négligeable qui affecte les performances du modèle.
+* Les nœuds ne gère qu'un seul flot de données, ce qui oblige à avoir un seul éléments en entré et un seul en sorti.
+* Il n'y a pas non plus d'optimisation au niveau du transfert de données entre les nœuds. Cependant il fait en sorte de faire le Reduce après le Map sur le même nœud car il contient déjà les données en mémoire. Cela évite une surcharge inutile de la bande passante.
+* L'utilisation de ce paradigme au sein même d'une base de donnée est totalement inutile. En effet, il faut lire la valeur, l'enregistrer, la stocker en paire, alors que le traitement direct via la base de donnée était possible.
+* Il y aussi le système de planification qui fait baisser les performances. Il permet d'assigner les tâches aux nœuds, mais plus les blocs de données sont importants (en terme de taille) et plus l'algorithme de planification va vite mais plus on a de risque que le MapReduce échoue. Il faut donc trouver le juste milieu entre optimisation du temps d’exécution de cet algorithme et les chances de réussite du traitement.
+===Les avantages===
+Ce modèle permet de de gérer de nombreux type de traitements de données comme les fouilles, les graphes et autres. De plus, il est totalement indépendant du système de stockage et du nombre de type de variable dans nos données.
+Il permet aussi l'utilisation de deux techniques de décodage des données :
+* De manière immuable, qui transforme en objet immuable (objet à état non modifiable) ce qui nous donne autant d'objet que de de données. Et c'est celle-ci qui est utilisée par défaut.
+* De manière mutable, on crée un objet mutable qui est réutilisé pour décoder tous les objet. Cette méthode nous permet de créé un seul objet.
+Il y a aussi deux techniques pour la mémorisation des données :
+* De manière direct, en passant du mémoire en cache à la mémoire en lecture.
+* Via le streaming qui permet la communication entre les processus.
+===Quelques examples d'utilisation===
+Ce paradigme est utilisé pour de nombreux cas comme :
+* Grep distribué
+* Tri distribué
+* Inversion de graphe des liens webs
+* Classification automatique
+* Traduction automatique
+=Démonstration=
+Voici une petite démonstration donné en exemple dans le framework d'apache Hadoop. Elle consiste  a faire un grep sur tous les fichiers de configuration du framework pour retrouver les mots commençant par « dfs ».
+Cet démonstration se fait en ligne de commande de la manière suivante :
-Comme on peut le constater le maître et dupliquer afin d'assurer que si il tombe en panne un autre puisse prendre sont relai et qu'on ne perde pas la vue d'ensemble du système qui nous obligerai alors à recommencer tout le travail.
+* On formate le système de fichier distribué
-==Démonstration==
+** $bin/hadoop namenode -format
+* On active le démon qui va permettre de faire les calculs
+** $bin/start-all.sh
+* On copie les fichier de configuration (conf) dans le nouveau système de fichier distribué comme donnée d'entrée (input)
+** $bin/hadoop fs -put conf input
+* On lance le grep
+** $bin/hadoop jar hadoop-examples-*.jar grep input output 'dfs[a-z.]+'
+* On récupère le fihier contenant les résultats (output) afin de le mettre en local pour pouvoir le consulter
+** $bin/hadoop fd -get output output
+*On consulte le fichier
+** $cat output/*
+*** 1     dfs.replication
+*** 1	  dfs.server.namenode.
+*** 1	  dfsadmin
+*On termine en arrêtant le démon
+** $bin/stop-all.sh
 =Sources=

EA2013/mapreduce: Difference between revisions