• STATISTIQUES
  • Il y a eu un total de 0 membres et 32055 visiteurs sur le site dans les dernières 24h pour un total de 32 055 personnes!
    Membres: 2 605
    Discussions: 3 579
    Messages: 32 816
    Tutoriels: 78
    Téléchargements: 38
    Sites dans l'annuaire: 58


  • ANNUAIRE
  • [EN] Sabre Films
    Site de challenge présenté sous la forme d'une quête. Vous êtes un détective et devrez résoudre d...
    Challenges
    [EN] xda-developers
    Très bon site pour les gros bidouilleurs de smartphone de windows à androïd et de Apple jusqu'...
    Phreaking
    [FR] Zenk-Security
    La communauté zenk-security a pour objet principal la sécurité informatique, nous sommes des tou...
    Hacking
    [FR] dcode
    dcode.fr est le site indispensable pour décoder des messages, tricher aux jeux de lettres, résoudre des énigmes...
    Outils / Add-on
    [EN] Lost-chall
    Site de challenge présenté sous la forme de différente saison. Pour passer une saison vous devez avoir accumulÃ...
    Challenges
    [EN] Hack This Site
    Hack This Site est considéré comme un réel terrain d'entraînement légal pour le...
    Hacking
    [FR] Secuser
    Actualité de la sécurité informatique, fiches virus et hoax, alertes par email, antivirus gratui...
    Hacking

  • DONATION
  • Si vous avez trouvé ce site internet utile, nous vous invitons à nous faire un don du montant de votre choix via Paypal. Ce don servira à financer notre hébergement.

    MERCI!

    €



Note de ce sujet :
  • Moyenne : 0 (0 vote(s))
  • 1
  • 2
  • 3
  • 4
  • 5
La Prog Fonctionnelle, Partie I bis
19-09-2014, 11h09 (Modification du message : 19-09-2014, 13h51 par gruik.)
Message : #1
b0fh Hors ligne
Membre actif
*



Messages : 210
Sujets : 17
Points: 309
Inscription : Jul 2012
La Prog Fonctionnelle, Partie I bis
La Prog Fonctionnelle, Annexe: MapReduce

Faisons maintenant une petite parenthèse a propos de MapReduce, le framework théorique utilisé pour l'exécution de grosses requêtes dans Hadoop ou MongoDB.

Dans MapReduce, la structure de données de base est le dictionnaire (aka hash, aka table associative). Une requête MapReduce se compose de deux fonctions, un mapper et un reducer.

Le mapper sera d'abord exécuté sur toutes les paires clef-valeur de l'input, et retourne (éventuellement) une (ou plusieurs) nouvelle(s) paire(s) clef-valeur.

Ensuite, pour chaque clef dans les résultats fournis par le mapper, le reducer reçoit toutes les valeurs correspondantes. Il émet ensuite une valeur finale, et c'est cette valeur qui est stockée, avec la clef correspondante, dans l'output.

Une contrainte supplémentaire est que le reducer doit être une fonction associative (oui oui, comme l'associativité de l'addition que vous avez vu a l'école) et commutative. Le résultat de reduce([reduce([a,d]), reduce([b, reduce([c,e]), f])), par exemple, doit être identique à reduce([a,b,c,d,e,f]).

Enfin, le mapper comme le reducer ne peuvent pas avoir d'effets de bord. Interdites donc les variables globales ou la communication avec l'extérieur.

Prenons un exemple extrêmement simple: le comptage des mots dans une collection de documents (ce que ferait un moteur de recherche pour trouver les mots les plus populaires.)

Notre input est donc une collection de documents, on peut imaginer

Code :
input = {'0001': 'blah bli blu', '0002': 'YOU LOST THE GAME', ... }

Notre mapper va compter les mots, et émettre la valeur 1 pour chaque mot trouvé:

Code :
def mapper(key, value):
    # key = ID du document, value = contenu du document
    for word in value.split():
        emit(word, 1)  # emission de la paire clef-valeur en sortie

Notre reducer va calculer la somme des valeurs:

Code :
def reducer(key, values):
    return sum(values)

On soumettra la requête a la base, avec quelque chose du genre

Code :
output = runMapReduce(input, mapper, reducer)

Oui oui, mais quel intérêt ?

Il se trouve que ce modèle est particulièrement adapté pour exécuter, sur des gros clusters, des requêtes de type analytique, qui ont besoin de lire une table entière, pas juste accéder à un index.

On peut stocker les données sur un énorme cluster de machines relativement modestes. Chaque machine est responsable de son propre disque, et peut le lire entièrement en un temps raisonnable. Pour augmenter la puissance du cluster, on ajoute simplement des machines, mais leur taille ne change pas.

Quand un système pareil grandit, le coût des communications réseau devient de plus en plus élevé, alors que les coûts d'I/O ou de calcul ne changent pas. Les coûts réseau finissent donc par dominer le temps d'exécution de la requête.

Les tables clef-valeur sont stockées distribuées sur toutes les machines; chaque machine est responsable d'un petit sous-ensemble de clefs. L'allocation se fait en utilisant une fonction de hachage, de cette manière n'importe quel noeud sait instantanément sur quel autre machine se trouve une clef donnée.

Comme les mappers s'exécutent clef par clef et ne peuvent pas communiquer entre eux, ils peuvent tous être exécutés en parallèle par toutes les machines du cluster, sans aucun problème.

Les résultats collectés, peuvent ensuite passer optionnellement par une phase reduce locale, ce qui permet de réduire la taille de l'output intermédiaire. La aussi, tout est fait complètement en parallèle.

Arrive ensuite la phase du shuffle: chaque machine examine son output intermédiaire, et le transmet, en fonction de la nouvelle clef produite par le mapper, à la machine responsable de cette clef. Conséquemment, chaque machine reçoit de toutes les autres les résultats intermédiaires. C'est l'étape qui est limitée par le réseau.

Enfin, chaque machine exécute un reducer final sur les clefs collectées, avant de placer le résultat dans l'output. La aussi, cette phase se fait entièrement en parallèle.

Un petit exemple visuel

Au départ:
  • Machine 1:
    Code :
    0001: I LIKE TURTLES
    0002: I LOST THE GAME

  • Machine 2:
    Code :
    0003: I LIKE THE GAME
    0004: I LOST MY KEYS

Après l'exécution du mapper, et du premier reducer:
  • Machine 1:
    Code :
    I: 2
    GAME: 1
    LIKE: 1
    LOST: 1
    THE: 1
    TURTLES: 1

  • Machine 2:
    Code :
    I: 2
    GAME: 1
    KEYS: 1
    LIKE: 1
    LOST: 1
    MY: 1
    THE: 1

Après le shuffle (la répartition des clefs est choisie par hash, donc sans logique apparente, mais ici j'ai choisi un pseudo-ordre alphabétique):
  • Machine 1:
    Code :
    I: 2
    I: 2
    GAME: 1
    GAME: 1
    KEYS: 1
    LIKE: 1
    LIKE: 1

  • Machine 2:
    Code :
    LOST: 1
    LOST: 1
    MY: 1
    THE: 1
    THE: 1
    TURTLES: 1

Et après l'exécution du reducer final:
  • Machine 1:
    Code :
    I: 4
    GAME: 2
    KEYS: 1
    LIKE: 1

  • Machine 2:
    Code :
    LOST: 2
    MY: 1
    THE: 2
    TURTLES: 1

Exercice

Ecrivez une fonction MapReduce qui calcule le mot le plus courant de toute la collection

Fin de la parenthèse, et retour à un aspect plus théorique de la programmation !
+1 (5) -1 (0) Répondre


Sujets apparemment similaires…
Sujet Auteur Réponses Affichages Dernier message
  La Prog Fonctionnelle, Partie I b0fh 1 238 08-04-2016, 22h40
Dernier message: lanodan
  La Prog Fonctionnelle, Partie II b0fh 0 108 20-09-2014, 12h44
Dernier message: b0fh
  La Prog Fonctionnelle, Partie III b0fh 0 87 20-09-2014, 00h23
Dernier message: b0fh

Atteindre :


Utilisateur(s) parcourant ce sujet : 1 visiteur(s)
N-PN
Accueil | Challenges | Tutoriels | Téléchargements | Forum | Retourner en haut