Qu'est-ce que Map / Reduce?

Question

J'entends beaucoup parler de map / reduction, en particulier dans le contexte du système de calcul massivement parallèle de Google. C'est quoi exactement?

Answer 1

À partir de l'abrégé de Google MapReduce publications de la recherche page:

MapReduce est un modèle de programmation et associé à une mise en œuvre pour traitement et à la production de données de grande taille les ensembles. Aux utilisateurs de spécifier une fonction de mappage que les processus d'une paire clé/valeur à générer un ensemble d'intermédiaires des paires clé/valeur, et une fonction de réduction qui fusionne toutes les valeurs intermédiaires associée avec le même intermédiaire clé.

L'avantage de MapReduce est que le traitement peut être effectué en parallèle sur plusieurs nœuds de traitement (plusieurs serveurs) c'est donc un système capable de s'adapter très bien.

Puisque c'est sur la base de la programmation fonctionnelle, le modèle, l' map et reduce chaque étapes n'ont pas d'effets secondaires (l'état et les résultats de chaque paragraphe d'un map processus ne dépend pas d'une autre), de sorte que l'ensemble de données mappé et réduit peuvent être séparés sur plusieurs nœuds de traitement.

Joel est Votre Langage de Programmation le Faire? la pièce traite de la façon dont la compréhension de la programmation fonctionnelle a été essentiel dans Google pour venir avec MapReduce, qui alimente son moteur de recherche. C'est une très bonne lecture, si vous n'êtes pas familier avec la programmation fonctionnelle et comment il permet évolutive code.

Voir aussi: Wikipédia: MapReduce

Question connexe: Veuillez expliquer mapreduce simplement

Answer 2

La carte est une fonction qui applique une fonction à tous les éléments d'une liste, pour produire une liste avec toutes les valeurs de retour sur elle. (Une autre façon de dire "application de f à x" est "call f, passant de x". Alors parfois, il semble plus agréable de dire "appliquer" au lieu de "l'appel".)

C'est la façon dont la carte est probablement écrit en C# (on appelle Select et est dans la bibliothèque standard):

public static IEnumerable<R> Select<T, R>(this IEnumerable<T> list, Func<T, R> func)
{
    foreach (T item in list)
        yield return func(item);
}

Comme vous êtes un Java mec, et Joel Spolsky aime raconter des INÉQUITABLES se trouve sur la façon misérable Java est (en fait, il n'est pas mentir, c'est merdique, mais je vais essayer de vous faire gagner plus), voici ma tentative très grossière à une version de Java (je n'ai pas de compilateur Java, et je me souviens vaguement de Java version 1.1!):

// represents a function that takes one arg and returns a result
public interface IFunctor
{
    object invoke(object arg);
}

public static object[] map(object[] list, IFunctor func)
{
    object[] returnValues = new object[list.length];

    for (int n = 0; n < list.length; n++)
        returnValues[n] = func.invoke(list[n]);

    return returnValues;
}

Je suis sûr que cela peut être amélioré en un million de façons. Mais c'est l'idée de base.

Réduire est une fonction qui transforme tous les éléments d'une liste en une seule valeur. Pour ce faire, il doit être donné une autre fonction func qui transforme les deux éléments en une seule valeur. Il travail en donnant les deux premiers points de func. Le résultat de ce avec la troisième élément. Le résultat de ce que le quatrième élément, et ainsi de suite jusqu'à ce que tous les éléments ont disparu et nous sommes à gauche, avec une valeur.

En C# réduire est appelé Aggregate et est de nouveau dans la bibliothèque standard. Je vais passer directement à une version de Java:

// represents a function that takes two args and returns a result
public interface IBinaryFunctor
{
    object invoke(object arg1, object arg2);
}

public static object reduce(object[] list, IBinaryFunctor func)
{
    if (list.length == 0)
        return null; // or throw something?

    if (list.length == 1)
        return list[0]; // just return the only item

    object returnValue = func.invoke(list[0], list[1]);

    for (int n = 1; n < list.length; n++)
        returnValue = func.invoke(returnValue, list[n]);

    return returnValue;
}

Ces versions de Java besoin génériques en ajoutant à eux, mais je ne sais pas comment le faire en Java. Mais vous devriez être capable de les transmettre anonyme intérieure classes pour fournir des foncteurs:

string[] names = getLotsOfNames();

string commaSeparatedNames = (string)reduce(names, 
   new IBinaryFunctor {
       public object invoke(object arg1, object arg2)
           { return ((string)arg1) + ", " + ((string)arg2); }
   }

Espérons que les génériques serait de se débarrasser de la jette. Le typesafe équivalent en C# est:

string commaSeparatedNames = names.Aggregate((a, b) => a + ", " + b);

Pourquoi est-ce "cool"? Des moyens simples pour casser les plus gros calculs en petits morceaux, de sorte qu'ils peuvent être combinés de différentes manières, sont toujours fraîches. La façon dont Google s'applique cette idée est à la parallélisation, parce que les deux map et reduce peut être partagée sur plusieurs ordinateurs.

Mais l'essentiel n'est PAS que votre langue traiter fonctions en tant que valeurs. Tout langage OO peut le faire. Le besoin réel pour la parallélisation est que le peu d' func fonctions que vous passez à la carte et de réduire ne doit pas utiliser ou mettre à jour n'importe quel état. Ils doivent retourner une valeur qui dépend seulement de l'argument(s) passé pour eux. Sinon, les résultats seront complètement foiré quand vous essayez d'exécuter l'ensemble de la chose en parallèle.

Answer 3

MapReduce Explained .

Cela explique mieux que ce que je peux. Aide-t-il?

Answer 4

Après l'obtention de la plupart des frustrés avec soit très long waffley ou à très courte vague de messages de blog, j'ai finalement découvert ce très bon rigoureux concis papier.

Alors je suis allé de l'avant et il est plus concis en traduisant dans la Scala, où j'ai fourni le plus simple des cas où un utilisateur, il suffit juste de précise l' map et reduce parties de l'application. Dans Hadoop/Spark, à proprement parler, un modèle plus complexe de la programmation est à l'emploi qui obligent l'utilisateur à spécifier explicitement les 4 plus des fonctions décrites ici: http://en.wikipedia.org/wiki/MapReduce#Dataflow

import scalaz.syntax.id._

trait MapReduceModel {
  type MultiSet[T] = Iterable[T]

  // `map` must be a pure function
  def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)])
                              (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = 
    data.flatMap(map)

  def shufflePhase[K2, V2](mappedData: MultiSet[(K2, V2)]): Map[K2, MultiSet[V2]] =
    mappedData.groupBy(_._1).mapValues(_.map(_._2))

  // `reduce` must be a monoid
  def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)])
                             (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] =
    shuffledData.flatMap(reduce).map(_._2)

  def mapReduce[K1, K2, V1, V2, V3](data: MultiSet[(K1, V1)])
                                   (map: ((K1, V1)) => MultiSet[(K2, V2)])
                                   (reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)]): MultiSet[V3] =
    mapPhase(map)(data) |> shufflePhase |> reducePhase(reduce)
}

// Kinda how MapReduce works in Hadoop and Spark except `.par` would ensure 1 element gets a process/thread on a cluster
// Furthermore, the splitting here won't enforce any kind of balance and is quite unnecessary anyway as one would expect
// it to already be splitted on HDFS - i.e. the filename would constitute K1
// The shuffle phase will also be parallelized, and use the same partition as the map phase.  
abstract class ParMapReduce(mapParNum: Int, reduceParNum: Int) extends MapReduceModel {
  def split[T](splitNum: Int)(data: MultiSet[T]): Set[MultiSet[T]]

  override def mapPhase[K1, K2, V1, V2](map: ((K1, V1)) => MultiSet[(K2, V2)])
                                       (data: MultiSet[(K1, V1)]): MultiSet[(K2, V2)] = {
    val groupedByKey = data.groupBy(_._1).map(_._2)
    groupedByKey.flatMap(split(mapParNum / groupedByKey.size + 1))
    .par.flatMap(_.map(map)).flatten.toList
  }

  override def reducePhase[K2, V2, V3](reduce: ((K2, MultiSet[V2])) => MultiSet[(K2, V3)])
                             (shuffledData: Map[K2, MultiSet[V2]]): MultiSet[V3] =
    shuffledData.map(g => split(reduceParNum / shuffledData.size + 1)(g._2).map((g._1, _)))
    .par.flatMap(_.map(reduce))
    .flatten.map(_._2).toList
}