Hadoop, a distributed

framework for Big Data

Part(1)

Introduction
 Introduction

1. Introduction

1. Architecture
 What is Hadoop?

Hadoop est un système distribué, tolérant aux pannes, pour le

stockage de données et qui est hautement scalable. Cette capacité
de monter en charge est le résultat d'un stockage en cluster à
haute bande passante et répliqué, connu sous l'acronyme de
HDFS (Hadoop Distributed File System) et d'un traitement
distribué spécifique et robuste connu sous le nom de MapReduce.
 Introduction

Pourquoi Hadoop dans le cadre de l'IT ?

 Hadoop traite et analyse une multitude de nouvelles et anciennes données
pour en extraire de la connaissance significative sur les opérations
commerciales.

 Concrètement les données sont déplacées vers un nœud de calcul. Puis

Hadoop va traiter la donnée là où elle se trouve.
 Introduction

Pourquoi Hadoop dans le cadre de l'IT ?

 Hadoop permet de répondre aux problématiques suivantes :

- l'analyse des événements - quelles séries d'étapes mènent à un événement

- l'analyse de clics sur des flux web à grande échelle ;
- l'assurance des revenus et l'optimisation des prix ;
- la gestion des risques financiers ;
- et beaucoup d'autres…
 Introduction

Pourquoi Hadoop dans le cadre de l'IT ?

 Le cluster Hadoop ou cloud est innovateur dans l'architecture du SI. Certains
gestionnaires de ressources (en grid) peuvent être intégrés avec Hadoop. Le
principal avantage est que les traitements Hadoop peuvent être soumis et
ordonnancés à l'intérieur même du datacenter
 Introduction

Les types de données à traiter ?

 les données de base gérées par des SGBD relationnels
 Logs informatiques.
 Télémétrie par satellite (espionnage ou science).
 GPS.
 Capteurs de température et d'environnement.
 Capteurs industriels.
 Vidéos des caméras de surveillance.
 Dispositifs médicaux.
 Capteurs sismiques et géophysiques.
…
 Introduction

Un exemple d'utilisation d'Hadoop

 Netflix (NASDAQ: NFLX) est une offre de service en ligne de location de DVD
et Blu-ray par correspondance et de streaming vidéo aux États-Unis. Elle a plus
de 100.000 titres et 10 millions d'abonnés. La société dispose de 55 millions de
disques et envoie en moyenne 1,9 million de DVD à ses clients chaque jour.
Netflix offre aussi du streaming vidéo sur Internet, permettant la visualisation de
films directement sur PC ou sur un téléviseur à la maison.

 L'algorithme de recommandation de films de Netflix utilise Hive (qui s'appuie

sur Hadoop, HDFS et MapReduce) pour le traitement des requêtes et de la
Business Intelligence. Netflix recueille tous les logs du site web qui sont collectés
en streaming à l'aide d'Hunu.
 Introduction

Un exemple d'utilisation d'Hadoop

Aujourd'hui, de plus en plus d'applications de production de Yahoo! ont

migré sur Hadoop. Ces applications critiques contrôlent tous les aspects
du fonctionnement de Yahoo!, de la personnalisation de l'expérience
utilisateur à l'optimisation du placement d'annonces. Elles tournent 24/7,
et traitent plusieurs téraoctets de données par jour.
 Introduction

Un exemple d'utilisation d'Hadoop

 Télécommunication : Nokia collecte et analyse de grandes quantités de données
(un téraoctet par jour) issues des téléphones portables de sa marque.

 Transport : US Xpress, une importante société de transport routier aux États-Unis

utilise Apache Hadoop pour stocker les données de capteurs transmises par leur flotte
de véhicules (données de géolocalisation, par exemple). L'analyse permet d'optimiser le
déplacement de véhicules dans le but d'économiser sur le coût du carburant.

 Vente : Etsy, un site de e-commerce analyse les gros volumes des données de logs
pour déterminer le comportement utilisateur ou les recommandations de recherche.
 Introduction

Qui utilise hadoop ?

et des milliers d'entreprises et universités à travers le monde.

 Introduction

hadoop : avantages vs inconvénients

(+) Simple à utiliser et à déployer.
(+) Portable (clusters hétérogènes).
(+) Indéfiniment scalable.
(+) Très extensible et interconnectable avec d'autres solutions.

(-) Il a également des inconvénients: overhead supérieur à une solution

propriétaire spécifique dédiée à un problème; encore expérimental
et en développement...
 Architecture

Hadoop
 Hadoop est un système de gestion de données et de traitements distribués. Il
contient de beaucoup de composants, dont :

- HDFS un système de fichier qui répartit les données sur de nombreuses

machines

- YARN un mécanisme d’ordonnancement de programmes de type MapReduce.

 Architecture

Hadoop : HDFS
 HDFS: Hadoop Distributed File System.
● Système de fichiers distribué associé à Hadoop. C'est là qu'on stocke
données d'entrée, de sortie, etc.

 Caractéristiques:
● Distribué
● Redondé
● Conscient des caractéristiques physiques de l'emplacement des serveurs
(racks) pour l'optimisation.
 Architecture

Hadoop : HDFS
 Repose sur deux serveurs:

● Le NameNode, unique sur le cluster. Stocke les informations relative aux

noms de fichiers et à leurs caractéristiques de manière centralisée.

● Le DataNode, plusieurs par cluster. Stocke le contenu des fichiers eux-

même, fragmentés en blocs (64KB par défaut).

 Inspiré de GFS, lui-même issu de recherches de Google. « The Google

File System », 2003.
 Architecture

Hadoop : HDFS
 Architecture

Hadoop : HDFS
Ecriture d’un fichier
1. Le client contacte le NameNode du cluster, indiquant la taille du fichier et son nom.

2. Le NameNode confirme la demande et indique au client de fragmenter le fichier en bloc

et d'envoyer tel ou tel bloc à tel ou tel DataNode.

3. Le client envoie les fragments aux DataNode.

4. Les DataNodes assurent ensuite la réplication des blocs

 Architecture

Hadoop : HDFS
 Architecture

Hadoop : HDFS
Lecture d’un fichier
1. Le client contacte le NameNode du cluster, indiquant le fichier qu'il souhaite obtenir.

2. Le NameNode lui indique la taille, en blocs, du fichier, et pour chaque bloc une liste de
DataNodes susceptibles de lui fournir.

3. Le client contacte les DataNodes en question pour obtenir les blocs, qu'il reconstitue
sous la forme du fichier.

4. En cas de DataNode inaccessible/autre erreur pour un bloc, le client contacte un

DataNode alternatif de la liste pour l'obtenir.
 Architecture

Hadoop : HDFS
 Architecture

Hadoop : HDFS

 L'ensemble du système de fichier virtuel apparaît comme un disque

« unique »: on ne se soucie pas de l'emplacement réel des données.

 Tolérant aux pannes: blocs répliqués.

 Plusieurs drivers FUSE existent pour monter le système de fichier HDFS

d'une manière plus « directe ».
 Architecture

Hadoop : HDFS
Limites

 NameNode unique: si problème sur le serveur en question, HDFS est

indisponible.

 Optimisé pour des lectures concurrentes; sensiblement moins

performant pour des écritures concurrentes.
 Architecture

Hadoop: les serveurs

 Le JobTracker, unique sur le cluster. Reçoit les tâches map/reduce à
exécuter (sous la forme d'une archive Java .jar), organise leur exécution
sur le cluster.

 Le TaskTracker, plusieurs par cluster. Exécute le travail map/reduce lui-

même (sous la forme de tâches map et reduce ponctuelles avec les
données d'entrée associées).

 Chacun des TaskTrackers constitue une unité de calcul du cluster

 Architecture

Hadoop: les serveurs

 Le serveur JobTracker est en communication avec HDFS; il sait où sont
les données d'entrée du programme map/reduce et où doivent être
stockées les données de sortie. Il peut ainsi optimiser la distribution des
tâches selon les données associées.

 Pour exécuter un programme map/reduce, on devra donc:

1. Écrire les données d'entrée sur HDFS.
2. Soumettre le programme au JobTracker du cluster.
3. Récupérer les données de sortie depuis HDFS.
 Architecture

Hadoop: Architecture générale

 Architecture

Hadoop: Exécuter une tâche

 Tous les TaskTrackers signalent leur statut continuellement par le biais de
paquets heartbeat.

 En cas de défaillance d'un TaskTracker (heartbeat manquant ou tâche échouée)

, le JobTracker avise en conséquence: redistribution de la tâche à un autre nœud.

 Au cours de l'exécution d'une tâche, on peut obtenir des statistiques détaillées

sur son évolution (étape actuelle, avancement, temps estimé avant complétion, etc.)
toujours par le biais du client console hadoop.
 Architecture

Hadoop: Exécuter une tâche

 Un seul JobTracker sur le serveur: point de défaillance unique.

 Les deux serveurs « uniques » NameNode et JobTracker sont souvent actifs au

sein d'une seule et même machine: le noeud maître du cluster.

Tout changement dans la configuration du cluster est répliqué depuis le noeud

maître sur l'intégralité du cluster.
 Architecture

Hadoop: Architecture détaillée

 Hadoop, a distributed
framework for Big Data
Part(2)

Le modèle map/reduce
 Plan

1. Présentation

1. Exemples

1.Map/reduce and Hadoop

 Présentation

 Pour exécuter un problème large de manière distribué, il faut pouvoir découper le

problème en plusieurs problèmes de taille réduite à exécuter sur chaque machine
du cluster (stratégie algorithmique dite du divide and conquer / diviser pour régner).

 MapReduce est un paradigme (un modèle) visant à généraliser les approches

existantes pour produire une approche unique applicable à tous les problèmes.
 Présentation

 MapReduce définit deux opérations distinctes à effectuer sur les données

d'entrée:

1. MAP, va transformer les données d'entrée en une série de couples clef/valeur. Elle va
regrouper les données en les associant à des clefs, choisies de telle sorte que les couples
clef/valeur aient un sens par rapport au problème à résoudre.

On doit pouvoir découper les données d'entrée en plusieurs fragments, et faire exécuter
l'opération MAP à chaque machine du cluster sur un fragment distinct.

2. La seconde, REDUCE, va appliquer un traitement à toutes les valeurs de chacune des

clefs distinctes produite par l'opération MAP. Au terme de l'opération REDUCE, on aura un
résultat pour chacune des clefs distinctes.

on attribuera à chacune des machines du cluster une des clefs uniques produites par MAP,
en lui donnant la liste des valeurs associées à la clef. Chacune des machines
effectuera alors l'opération REDUCE pour cette clef.
Présentation
 Présentation

On distingue donc 4 étapes distinctes dans un traitement MapReduce:

1. Découper (split) les données d'entrée en plusieurs fragments.

2. Mapper chacun de ces fragments pour obtenir des couples (clef ; valeur).

3. Grouper (shuffle) ces couples (clef ; valeur) par clef.

4. Réduire (reduce) les groupes indexés par clef en une forme finale, avec une
valeur pour chacune des clefs distinctes.
Présentation
 Présentation

Pour résoudre un problème via la méthodologie MapReduce avec

Hadoop, on devra donc:

● Choisir une manière de découper les données d'entrée de telle sorte que
l'opération MAP soit parallélisable.

● Définir quelle CLEF utiliser pour notre problème.

● Écrire le programme pour l'opération MAP.

● Ecrire le programme pour l'opération REDUCE.

… et Hadoop se chargera du reste (problématiques calcul distribué,

groupement par clef distincte entre MAP et REDUCE, etc.).
 Exemples

Exemple1:
Imaginons qu'on nous donne un texte écrit en langue Française. On souhaite
déterminer pour un travail de recherche quels sont les mots les plus utilisés au
sein de ce texte (exemple Hadoop très répandu).

Etape1 : Déterminer une manière de découper (split) les données d'entrée pour
que chacune des machines puisse travailler sur une partie du texte.
Idée : découper les données d'entrée ligne par ligne. Chacune des lignes du
texte sera un fragment de nos données d'entrée. Pour simplifier le traitement on
A choisir de passer l'intégralité du texte en minuscules
 Exemples

Texte avant découpage (split) :

Texte de sortie (après découpage):

4 fragments depuis nos données d'entrée.

 Exemples

Exemple1:
Etape 2 : Déterminer la clé à utiliser pour notre opération MAP, et écrire le
code de l'opération MAP elle-même.
 Puisqu'on s'intéresse aux occurrences des mots dans le texte, et qu'à terme on
aura après l'opération REDUCE un résultat pour chacune des clefs distinctes,
la clef qui s'impose logiquement dans notre cas est: le mot-lui même.

clef/valeur: (MOT ; 1)

La valeur indique ici l’occurrence pour cette clef - puisqu'on a croisé

le mot une fois, on donne la valeur « 1 ».
 Exemples

Exemple1:
Etape 3 : Coder l’opération Map
Le pseudo code de map est le suivant :

Pour chacun de nos fragments, les couples (clef; valeur) générés

seront :
 Exemples

Exemple1:

 Une fois notre opération MAP effectuée (de manière distribuée), Hadoop groupera
(shuffle) tous les couples par clef commune. Cette opération est effectuée
automatiquement par Hadoop. Elle est, là aussi, effectuée de manière distribuée en
utilisant un algorithme de tri distribué, de manière récursive. Après son exécution,
on obtiendra les 15 groupes suivants:
 Exemples

Exemple1:
Etape 3 : Coder l’opération Reduce
Il nous reste à créer notre opération REDUCE, qui sera appelée pour chacun
des groupes/clef distincte. Dans notre cas, elle va simplement consister
à additionner toutes les valeurs liées à la clef spécifiée:

Une fois l'opération REDUCE effectuée, on obtiendra donc une valeur

unique pour chaque clef distincte. En l’occurrence, notre résultat sera:

le mot le plus utilisé dans notre texte est :

« qui », avec 4 occurrences,
 Exemples

Exemple1:

Idée : utiliser les mêmes implémentations de MAP et REDUCE sur l'intégralité

des textes d'une bibliothèque, et obtenir ainsi un bon échantillon des mots les
plus utilisés dans la langue Française. On bénéficier effectuer le traitement
sur un nombre variable de machines de manière distribuée (apport de
map/reduce).
 Exemples

Exemple 1: recap
 Exemples

Exemple 2: Statistiques web

compter le nombre de visites sur chacune des pages d'un site Internet.
On dispose des fichiers de logs sous la forme suivante:

Appliquer le map/reduce ?
- Découpage (split) : les ligne de fichier log
- La clé : l’adresse URL, nb occurence
- Map : générer les clés
- Reduce : calculer
 Exemples

Exemple 3: réseau social : « le nombre des amis en commun »

 Dans un réseau social (facebook, google+..) comportant des millions

d'utilisateurs. Pour chaque utilisateur, on a dans notre base de données
la liste des utilisateurs qui sont ses amis sur le réseau (via une requête
SQL). On souhaite afficher quand un utilisateur va sur la page d'un autre
utilisateur une indication « Vous avez N amis en commun ».

 On ne peut pas se permettre d'effectuer une série de requêtes SQL à

chaque fois que la page est accédée (trop lourd en traitement). On va
donc développer des programmes MAP et REDUCE pour cette opération
et exécuter le traitement toutes les nuits sur notre base de données, en
stockant le résultat dans une nouvelle table.
 Exemples

Exemple 3: réseau social : « le nombre des amis en commun »

Les données d'entrée sous la forme Utilisateur => Amis:

Puisqu'on est intéressé par l'information « amis en commun entre deux

utilisateurs » et qu'on aura à terme une valeur par clef, on va choisir
pour clef la concaténation entre deux utilisateurs. Par exemple, la clef « A-B »
désignera « les amis en communs des utilisateurs A et B ».On peut segmenter
les données d'entrée là aussi par ligne.
 Exemples

Exemple 3: réseau social : « le nombre des amis en commun »

Les données d'entrée sous la forme Utilisateur => Amis:

Notre opération MAP va se contenter de prendre la liste des amis fournie

en entrée, et va générer toutes les clefs distinctes possibles à partir de
cette liste. La valeur sera simplement la liste d'amis, telle quelle.
On fait également en sorte que la clef soit toujours triée par ordre
alphabétique (clef « B-A » sera exprimée sous la forme « A-B »).
 Exemples

Exemple 3: réseau social : « le nombre des amis en commun »

MAP

Ligne Clé
 Exemples

Exemple 3: réseau social : « le nombre des amis en commun »

Tri de hadoop

On obtient bien, pour chaque clef « USER1-USER2 », deux

listes d'amis: les amis de USER1 et ceux de USER2.
 Exemples

Exemple 3: réseau social : « le nombre des amis en commun »

Reduce

On sait ainsi que A et B ont pour amis communs

les utilisateurs C et D, ou encore que B et C ont
pour amis communs les utilisateurs A, D et E.
 Exemples

Exemple 4: anagrammes :

à partir d'une liste de mots, on cherche à déterminer lesquels sont des

anagrammes : les données d’entrée :

map: renvoie un couple (clef;valeur), avec le mot pour valeur et les

lettres du mot ordonnées dans l'ordre alphabétique pour clef.
 Exemples

Exemple 4: anagrammes :

Aprés l'étape de shuffle:

 Exemples

Exemple 4: anagrammes :

reduce: concatène toutes les valeurs d'entrée pour la clef unique;

renvoie un couple (clef;valeur) avec la clef d'entrée pour clef et la
chaîne ainsi concaténée pour valeur.
 Exemples

Exemple 4: sentiment client/twitter :

une entreprise dispose d'un compte twitter pour son service aprés vente,
recevant plusieurs dizaines de milliers de tweets par jour. Elle cherche à
déterminer le taux de satisfaction de ses clients à partir du compte twitter.
 Exemples

Exemple 4: sentiment client/twitter :

Clef: un descripteur de sentiment client (« satisfait », « insatisfait » ou

« attente », « inconcluant »).

● map: génère un couple (clef;valeur) par sentiment client détecté (mot

correspondant à une liste prédéfinie).

● Si deux sentiments contradictoires détectés: renvoyer inconcluant.

● On renvoie un couple (clef;valeur) pour chaque fragment des données

d'entrée: chaque tweet
 Exemples

Exemple 4: sentiment client/twitter :

Pseudo code:
 Exemples

Exemple 4: sentiment client/twitter :

Après exécution::
 Exemples

Exemple 4: sentiment client/twitter :

Reduce : additionne les valeurs associées à la clef unique; renvoie le total
pour valeur (identique au reducer du compteur d'occurences de mots).

Conclusion: lors de la dernière heure, 33% de tweets exprimant de la

satisfaction.
 Exemples

Exemple 5: publication

Chaque article scientifique publié dans journal, conférence ou autre, et signé par
une liste d’auteurs. On veut calculer, pour chaque trio d’auteurs (x, y, z), le
nombre d’articles que ces trois auteurs ont co-signés. Précisions: si les auteurs
d’un article sont un sur-ensemble de (x, y, z) (par ex. (x, u, v, y, w, z)) ça compte
pour 1. L’ordre des auteurs ne compte pas: (z, y, x) est considéré comme une
occurrence.

Comment faire ce calcul en MapReduce?

 Exemples

Exemple 5: publication

Pour chaque publication, on prend la liste des auteurs, et on en extrait

toutes les combinaisons possibles de 3 auteurs distincts

Pour chaque combinaison C, il faut émettre la paire (C, 1). Le regroupement se

fera sur la combinaison, et la somme des 1 donnera le nombre d’occurrences
sur l’ensemble de la collection. Encore une fois, c’est le choix de la clé qui est
essentiel.

Donner la démarche map/reduce ?