MapReduce: Simplified Data Processing on Large

ClustersPrésenté par: Mathieu Dumoulin

Université Laval, H2013

1

C’est l’histoire d’une jeune compagnie…

• Des compétiteurs féroces et riches

• Doit traiter des TRÈS gros volumes de

données

• Des besoins en pleine évolution

• En expansion rapide

2

Vous la connaissez peut-être…

3

Deux gros problèmes

1. Données à très grande échelle

2. Ressources financières limitées4

Réfléchissons au problème de taille

• On veut trouver les 5 mots les plus fréquents dans

une collection de textes.

• Faisons un petit algo en pseudo-code:

def wordCount(text):counts = defaultdict(int)for word in text:

counts[word] += 1

5

La croissance de taille est un problème majeur

6

Problème SolutionTaille

• 100M mots

• 1000M mots

• 100MM mots

• 1000MM mots

• Plus encore!

• Pas de problèmes

• Mémoire insuffisante

• Processeur insuffisant

• 1 ordinateur insuffisant

• Réseau insuffisant, contrôleur surchargé

• Naïve avec 1 seul ordinateur

• Utiliser le disque, Fenêtre glissante

• Multithreading, éliminer < N

• Distribuer le calcul

• ???

Le problème du coûtQuelques faits:

• Une grappe hyper robuste coûte très cher

• ça brise quand même!

Une piste de solution:

• Est-ce possible d’utiliser du matériel orienté consommateur?

• Mais… quoi faire avec les défaillances

7

Les défaillances à grande échelle:

Un problème incontournable

Mathieu Dumoulin 8

En fait

Une grappe de grande envergure n’est jamais fonctionnelle à 100% quel que soit le prix

Mathieu Dumoulin 9

La solution de Google: MapReduce (et GFS)

10

• Un framework C++

• Calcul distribué

automatiquement

• Grappe de milliers

d’ordinateurs PC standards

• Robuste aux défaillances

• Programmation simple

Plan

• Comment s’en servir?

• Retour sur WordCount

• Comment ça marche?

• Pourquoi ça marche?

• Et ça marche?

• MapReduce en action

• Conclusion

11

Comment s’en servirLe modèle de programmation

L’exemple WordCount

12

La programmation parallèle, pas facile…

• Coordination de la communication

• Gérer les défaillances matérielles

• Prendre et afficher des mesures sur la progression

des tâches

• Débogage

• Optimisation des applications

• Tirer profit de la localité des données

13

MapReduce: modèle de

programmation• Entrée et sortie: des paires de clef-valeur (Key/value)

• Le programmeur spécifie 2 fonctions (et un main):

map (in_key, in_value) -> list(out_key, intermediate_value)

• Appliquer une transformation sur l’entrée

• Émettre une nouvelle paire clef-valeur intermédiaire en sortie

Reduce (out_key, list(intermediate_value)) -> list(out_value)

• Combiner les valeurs intermédiaires pour chaque clef

• Produire un ensemble de sortie qui combine tous les résultats

Mathieu Dumoulin 14

Exemple WordCountpublic static class Map extends Mapper<LongWritable, Text, Text, IntWritable> {

private final static IntWritable one = new IntWritable(1);

private Text word = new Text();

public void map (LongWritable key, Text value, Context context) throws Exception {

String line = value.toString();

StringTokenizer tokenizer = new StringTokenizer(line);

while (tokenizer.hasMoreTokens()) {

word.set(tokenizer.nextToken());

context.write(word, one);

}

}

}

15

Exemple WordCountpublic static class Reduce extends Reducer<Text, IntWritable, Text, IntWritable> {

public void reduce(Text key, Iterable<IntWritable> values, Context context) throws Exception {

int sum = 0;

for (IntWritable val : values) {

sum += val.get();

}

context.write(key, new IntWritable(sum));

}

}

Mathieu Dumoulin 16

Comment ça marche?Exécution d’une tâche MapReduce

17

Exécution de WordCount

18

Exécution d’une tâche MapReduce

19

Pourquoi ça marche?L’architecture de la grappe

NameNode: le contrôleur de la grappeLa robustesse: essentielle

Dans la pratiqueRaffinements

20

Une grappe MapReduce: Architecture

21

NameNode• Un seul NameNode enregistre le metadata

• Garde toutes les informations sur les

DataNodes (block, owner, group, etc.)

• Tout est gardé en mémoire vive

• La taille de la grappe est limitée par la

mémoire vive de l’ordinateur NameNode

Data Node• DataNodes store file contents

• Stored as opaque ‘blocks’ on the underlying

filesystem

• Different blocks of the same file will be

stored on different DataNodes

• Same block is stored on three (or more)

DataNodes for redundancy

Et les défaillances?• Les DataNodes envoient un battement de

coeur au NameNode• Le NameNode gère les DataNodes

activement• Les défaillances sont transparentes aux

programmes utilisateurs

On transforme un groupe d’ordinateurs

individuellement peu fiables en une

grappe super fiable de façon générale

qui bénéficie à tous les utilisateurs de la

librairie automatiquement.

Dans la pratique• Yahoo en 2009: MTBF moins de 1jour

• Google en 2009, taux de défaillances par année:o Disque dur: 1-5%

o PC: 2-4%

Et avec MapReduce?

• A résisté à la perte simultanée de plus de 800

ordinateurs, aucune perte de travail!

25

Implémentation typique à

Google (2003-2004)

Mathieu Dumoulin

• 100-1000 serveurs (2 CPU Intel, 2-4GB RAM)

• Disques durs « ordinaires » IDE

26

Raffinement: Exécution locale• Principe: Amener le code aux données

• Résultat: La bande passante totale d’une tâche peut dépasser la vitesse maximale du réseau!

30 GB/s > 10 GB/s

27

Raffinement: Exécution redondante

C’est possible d’aller plus vite en faisant plus de travail

en double:

• Les esclaves lents vont ralentir l’exécution de la

tâche entière:o D’autres tâches utilisent les ressources à ce moment

o Disque dur ayant des erreurs récupérables

o Autres situations bizarres: processeur avec la cache désactivée (!!)

• Solution: vers la fin d’une phase, on relance toutes

les tâches en attente à des esclaves disponibles.o Le premier qui finit une tâche « l’emporte »

Le résultat: une exécution totale

dramatiquement accélérée.

28

Raffinement: Sauter les entrées problématiques

• Résultat: Les bugs dans les librairies peuvent

être gérées de façon élégante

• Principe: Amener le code aux données

• Politique de planification du maître:o Demander au GFS l’adresse physique des répliques pour les blocs des

fichiers d’entrée

o Les tâches map sont généralement divisées en « split » de 64MB.

o Aiguiller les tâches pour que les maps s’exécutent sur des données locales

à la machine, ou sur le même routeur.

29

Autres raffinements• Garanties sur l’ordre trié pour chaque partition

reduce.

• Compression des données intermédiaireso La bande passante est un facteur limitant important

• Combination: reduce local à chaque machine

avant d’envoyer les valeurs intermédiaires sur le

réseau

• Possibilité d’exécution en mode local pour aider les

développeurs

• Compteurs

Lire l’article pour les détails…

30

Et ça marche?Résultats expérimentaux

Métriques

Performance

Expérience de migration à MapReduce: PageRank

31

Performance• Grappe de production de 1800 machines:

o 4GB de mémoire

o Processeurs double cœur 2GHz Xeon de Intel avec Hyperthreading

o 2x HDD 160GB IDE

o Accès au réseau: Gigabit Ethernet

o Bande passante entre groupes de serveurs (racks): 100 Gbps

• Mesures de performance:o MR_Grep: Rechercher globalement les correspondances avec

l'expression rationnelle (en anglais, regular expression), et imprimer (print) les lignes dans lesquelles elle correspond.

• Taille: 10 milliards de lignes, expression rare (92,000 lignes

correspondent)

o MR_Sort: Faire un tri sur 10 milliards d’éléments (TeraSort benchmark )

32

Métriques

33

MR_SortNormal Avec backup

200 processus défaillants

34

Expérience: Migration de

l’indexeur de Google

• L’indexeur du moteur de recherche de Google a

été converti en ensemble de tâches MapReduce:o Ensemble de 10, 14, 17, 21 opérations MapReduce

o Le nouveau code est beaucoup plus simple et facile à

comprendre

o Robustesse incluse automatiquement

o On peut accélérer le traitement en ajoutant des machines, sans

modifier le code.

35

MapReduce en action à Google

Utilisation courante

36

MapReduce apprécié par les ingénieurs de Google

Mathieu Dumoulin 37

Utilisation de la grappe MapReduce à Google 2003-2004N

om

bre

de

pro

jets

Exemple: Google Maps

MapReduce est utilisé partout à Google, dont Google Maps par exemple

Mathieu Dumoulin 38

En production à Google (2004)• Number of jobs 29,423

• Average job completion time 634 secs

• Machine days used 79,186 days

• Input data read 3,288 TB

• Intermediate data produced 758 TB

• Output data written 193 TB

• Average worker machines per job 157

• Average worker deaths per job 1.2

• Average map tasks per job 3,351

• Average reduce tasks per job 55

• Unique map implementations 395

• Unique reduce implementations 269

• Unique map/reduce combinations 426

39

ConclusionForces et faiblesses

Retour sur les objectifs

Objectifs atteints

40

MapReduce: Pas une panacée!

• Difficile

• Lent, peu efficace

• Cher

• Alternatives mieux adaptées

41

• Pig et Hive plus facile!

• Domaine de recherche activeo Dremel et BigQuery

• Une question d’échelle et de besoins

• Bénéfices de la standardisation

Conclusion: Objectifs de MapReduce

• Peut grandir à des tailles de données gigantesques

(Petabytes)

• Économique: Utiliser du matériel standardisé et peu

cher

• Robuste

• Général

• Facile à utiliser pour les développeurs

42

Objectifs atteints!• L’abstraction MapReduce est utile.

• Le traitement de données à grande échelle est

significativement simplifiée à Googleo Traitement de données à une échelle inédite à cette époque

• L’utilisateur est heureux: aucun souci avec les

détails difficiles. On peut se concentrer sur le

problème.

• L’utilisation de matériel informatique « ordinaire »

permet un ratio de puissance-coût qui dépasse de

beaucoup l’état de l’art.

43