Quels types de problèmes sont résolus par MapReduce?

Cela fait un moment que je lis sur MapReduce - mais ce que je ne comprends pas, c'est comment quelqu'un déciderait d'utiliser MapReduce (ou de ne pas l'utiliser).

Je veux dire, quels sont les modèles de problèmes qui signalent que MapReduce pourrait être utilisé.

Ce sont essentiellement des problèmes énormes, mais pas difficiles. Le voyageur de commerce dépend essentiellement de la distance qui sépare une paire de villes. Ainsi, bien qu’elle puisse être décomposée en plusieurs parties, les résultats partiels ne peuvent pas être recombinés, de sorte que la solution globale optimale émerge (enfin, probablement pas; si vous connaissez un moyen, demandez votre médaille Fields maintenant).

D'autre part, compter les fréquences de mots dans un gigantesque corpus est trivialement partitionnable et trivialement recombinable (vous additionnez simplement les vecteurs calculés pour les segments du corpus), alors map-reduction est la solution évidente.

En pratique, plus de problèmes ont tendance à être facilement recombinables qu'autrement, la décision de paralléliser ou non une tâche a donc plus à voir avec l'ampleur de la tâche et moins avec sa difficulté.

Le problème peut-il être résolu efficacement en utilisant l’informatique distribuée?

Si la réponse à cette question est oui, vous avez un problème potentiel pour MapReduce. Cela est dû au fait que le modèle de problème se prête bien à être scindé en problèmes isolés plus petits.

Votre tâche: analyser ce livre

Un exemple fonctionne bien pour illustrer cela. Vous avez un document volumineux ( Moby Dick de Herman Melville ) et votre travail consiste à effectuer une analyse de fréquence de tous les mots utilisés.

L'approche séquentielle

Vous pouvez le faire de manière séquentielle en obtenant votre machine la plus rapide (vous en avez beaucoup) et en parcourant le texte du début à la fin en maintenant une carte de hachage de chaque mot trouvé (la clé) et en incrémentant la fréquence (valeur) à chaque fois. vous analysez un mot. Simple, direct et lent.

L'approche MapReduce

En abordant cette question sous un angle différent, vous remarquerez que vous disposez de toutes ces machines de rechange et que vous pouvez scinder cette tâche en morceaux. Attribuez à chaque machine un bloc de texte de 1Mo à analyser dans une carte de hachage, puis associez toutes les cartes de hachage de chacune en un seul résultat. Ceci est une solution MapReduce en couches.

Le processus de lecture d'une ligne de texte et de regroupement des mots est la phase Carte (vous créez une carte simple représentant les mots de la ligne avec leur fréquence 1,2,3, etc.), puis la phase Réduire correspond au moment où chaque machine assemble sa ligne. cartes dans une seule carte agrégée.

La solution globale découle d'une phase de réduction supplémentaire dans laquelle toutes les cartes agrégées sont agrégées (ce mot à nouveau) en une carte finale. Un peu plus complexe, massivement parallèle et rapide.

Sommaire

Donc, pour résumer, si votre problème se prête à être représenté par des clés, des valeurs, des opérations d'agrégation sur ces valeurs isolément, vous avez un problème potentiel pour MapReduce.

Le modèle MapReduce est issu du monde de la programmation fonctionnelle. C'est un processus pour appliquer quelque chose appelé un catamorphisme sur une structure de données en parallèle. Les programmeurs fonctionnels utilisent des catamorphismes pour pratiquement toutes les transformations ou résumés simples.

En supposant que vos données soient un arbre, le facteur décisif est de savoir si vous pouvez calculer une valeur pour un nœud en utilisant uniquement les données contenues dans ce nœud et les valeurs calculées pour ses enfants.

Par exemple, vous pouvez calculer la taille d’un arbre en utilisant un catamorphisme; vous calculeriez la somme des valeurs calculées pour tous les enfants plus un.

Ce WPI - Applications de réduction de la carte (ppt) peut vous intéresser. Il aborde différentes applications de la gestion des droits des documents et, en tant qu’un des cas évoqués, montre comment, en utilisant 100 instances EC2 et 24 heures, le New York Times a été en mesure de convertir 4 To d’articles numérisés en 1,5 To de documents PDF.

Une autre série d’exemples où la gestion numérique a contribué à l’accélération des performances est la suivante: Aster - SQL Map Reduce présente des études de cas sur la technologie SQL-Map Reduce, notamment la détection des fraudes, les transformations et autres.

Carte / Réduire est une forme spécifique d'un type d'algorithme. Vous l'utilisez pour transformer un énorme ensemble de données en un autre. (Le jeu de données résultant peut ne pas être énorme.) Si vous ne voulez pas d'un jeu de sortie de données statique résultant d'une entrée de données statique, alors Mappage / Réduire n'est pas approprié. Map / Reduce peut facilement vous dire combien de John Smith sont dans l'annuaire téléphonique de Manhattan, mais il n'est pas bien adapté pour créer un serveur Web.

Le fonctionnement de Map / Reduce est:

• Map prend des paires de clés (k1) et de valeurs (v1) et les mappe dans un nouvel ensemble de clés (k2) et de valeurs (v2).
• Réduire prend toutes les valeurs v2 avec la même clé k2 et produit une nouvelle valeur (v3).

Le résultat est qu'une liste de paires (k1, v1) est transformée en une liste de (v3) s. (Bien entendu, la valeur "v3" peut être un composite comprenant k2, qui pourrait être défini comme étant égal à k1.)

Donc vous l'utilisez:

1. Si vous avez tellement de données pour commencer, il serait trop long de tout exécuter de manière séquentielle sur un ou deux serveurs.

2. Vous pouvez concevoir les données de sortie comme étant une liste de valeurs ou des paires de valeurs de clé (généralement pas trop difficile lorsque vous vous souvenez que "clé" signifie uniquement "étiquette unique"), et

3. Quelle que soit la relation, vous êtes certain que chaque élément de données d'entrée n'a un impact que sur la valeur de sortie d'une clé de sortie.

Si vos données peuvent toutes être traitées de manière séquentielle par un seul serveur, utilisez-le, puisqu'il s'agit du paradigme informatique dominant (les serveurs sont conçus pour et les programmeurs sont formés), utilisez un seul serveur.

L'étape de mappage doit partitionner toutes les données d'entrée par clé de sortie. Il n'a pas à produire la valeur de sortie associée à la clé de sortie (cela se fait par l'étape de réduction), mais il doit affecter de manière unique chaque paire de valeurs de clé d'entrée pour contribuer au maximum à la valeur d'une clé de sortie. Si les données sont trop interdépendantes, la réduction de la carte pourrait ne pas être en mesure de gérer le problème. D'autre part, il se peut simplement que vous deviez utiliser plusieurs tours de carte / réduction.

Si vous ne savez pas comment transformer votre transformation de données en une carte / réduction, alors bien sûr, ce n'est pas une solution.

Déterminer si un problème peut être décomposé en quelque chose que Map / Reduce peut gérer est un véritable art. Par exemple, v1 et v2 peuvent ne pas être du tout dans les fichiers de données d'entrée ou de sortie. Si vous souhaitez simplement compter des éléments uniques dans les données d'entrée, alors k1 = k2 = un élément et v1 = v2 = 1 ou 0 ou vraiment n'importe quoi. Réduire ne produit que v3 sous forme de somme du nombre de k2 qui lui a été attribué.

Il est donc difficile de dire avec certitude qu’une transformation de données ne peut pas être réalisée à l’aide de Mapper / Réduire, mais ce qui précède vous donne quelques repères.

MapReduce s’applique à tous les problèmes comportant exactement 2 fonctions à un niveau d’abstraction donné. La première fonction est appliquée à chacun des éléments du jeu d'entrées et la deuxième fonction agrège les résultats.

Donc, chaque fois que vous voulez obtenir (1) le résultat de (n) entrées, et que toutes les entrées peuvent être examinées / utilisées par (1), vous pouvez utiliser MapReduce. Encore une fois, ceci est à un niveau spécifique d'abstraction. La fonction (1) peut être une fonction de regroupement qui vérifie l’entrée et décide laquelle des autres fonctions à utiliser.

Ceci est utile lorsque vous ne savez pas à l’avance le nombre d’entrées que vous aurez, si vous avez besoin de partager des «unités» de travail discrètes, ou si vous voulez un seul rapport représentant le résultat entier (IE exécute cinq mille tests unitaires). , et si moins de x% échouent, renvoyez le succès).

La plupart des réponses ici semblent être une variante de l'explication de ce que la réduction de carte fait, ce qui est valable. Mais répondre à la question de savoir quel modèle indiquerait où vous pourriez utiliser Map Réduire n’est pas vraiment abordé.

Si la mise en œuvre naïve, non fonctionnelle, du problème que vous étudiez implique de boucler sur quelque chose, puis de mettre à jour quelque chose en dehors de la boucle avec un état de l'intérieur de la boucle, il y a des chances que vous ayez quelque chose que les ports bien mappent à réduire. Surtout si vous pouvez généraliser la mise à jour de l'état central à une fonction qui fonctionne avec seulement deux paramètres et peut garantir que cette fonction est commutative et associative.

La raison pour laquelle vous voudriez peut-être utiliser la réduction de carte si cela est vrai est double: 1) il pourrait être un peu plus propre et plus facile à tester et à déboguer si vous décomposez des éléments dans la carte et réduisez les fonctions. 2) les fonctions de réduction de carte sont sans état et peuvent être exécutées simultanément, ce qui accélère les choses si vous avez plusieurs processeurs disponibles et quelque chose comme hadoop ou spark qui utilise cela pour exécuter des tâches dans un cluster.

C’est bien si vous parcourez beaucoup de choses mais que votre kilométrage peut varier en fonction de la complexité de votre carte / réduction. Il est assez courant de se retrouver avec une chaîne séquentielle ou une arborescence de réductions de carte où, au final, tout est encore goulot d’étranglement lors d’une étape de réduction complexe en bout de chaîne. Par exemple, de nombreux algorithmes de graphes sont difficiles à mettre à l’échelle efficacement avec juste une réduction de carte.

L’exemple le plus simple qui fonctionne bien avec la réduction de carte, est le comptage des éléments, ce qui est une réduction très économique. C'est pourquoi le nombre de mots est un exemple souvent utilisé pour réduire la carte. Vous pouvez vous attendre à une évolutivité linéaire des performances avec cette cas d'utilisation: chaque unité centrale que vous ajoutez le rend plus rapide.

Si vous faites beaucoup de programmation fonctionnelle, vous commencez à vous retrouver dans des situations qui nécessitent une carte générale et à réduire. Vous les voyez probablement même dans la programmation impérative, mais ne les reconnaissez pas derrière le masque des boucles et des accumulateurs.

En tant qu'exemple cité récemment, j'ai travaillé sur un analyseur syntaxique à Haskell. Pour tester mon analyseur, je pompe une liste de fragments de chaîne dans l'analyseur, puis je souhaite obtenir une seule chaîne que je puisse afficher en sortie de mes résultats pour voir si elle est analysée correctement. Cela ressemble donc à:

--my initial set of test data, a list
tests = ["string1", "string2", "string3", ...]

--Map Step: turn strings into parsed results
--note the type, which demonstrates the map
applyParser :: [String] -> [Token]
--The actual function
applyParser input = map parser input

--Second map, turn tokens into output
showTokens :: [Token] -> [String]
showTokens t = map show t

--Reduce step, concat the results
combineResults :: [String] -> String
--In haskell, reduce is the foldl function, which takes an operation to fold with, a starting element, and a list to fold on
combineResults strings = foldl concat "" strings

--Finished program
testParser = print (combineResults(showTokens(applyParser tests)))

Bien sûr, cela n’est que pédagogique. Mon code actuel est un peu différent et utilise plus de fonctions internes ( fold concatinutile de le faire puisque Haskell inclut déjà unlinescela [String]->String). Mon point principal était que je n’avais pas prévu d’utiliser une carte / réduire au début, c’est simplement conforme à mes besoins. Je voulais faire des choses avec des listes, puis transformer ma liste en un seul élément de sortie. L'utilisation de carte / réduire est apparue naturellement.

Le traitement des chaînes (comme l'analyse) est une utilisation très évidente de la réduction de carte, la cartographie consiste à appliquer diverses transformations au texte d'entrée et à le réduire en remettant le texte de résultat en sortie. De même, un compilateur pourrait être similaire, en utilisant des plis pour transformer un flux d’éléments d’arbre de syntaxe abstraite en une meilleure forme (optimisation).

Est-ce parallélisable?

Tout problème parallélisable est essentiellement une carte et un pli; inversement, l’étape de mappage est intrinsèquement parallélisable (et l’étape de repli peut être fonction de la structure sur laquelle elle est repliée); il s’agit donc d’une propriété bidirectionnelle.

Supposons que vous recherchez un cluster de serveurs et que l’un ne soit pas en mesure de répondre à ce moment. Ce que mapReduce fera, c'est qu'il ne pourra pas accéder à ce nœud d'arborescence à la carte plus grande, car il le replaniera pour plus tard et effectuera alors la carte ou la réduction. Essentiellement, il tente de garantir que toutes les informations sont disponibles avec l'imprévisibilité des logiciels et du matériel dans les environnements.

Voici les principales questions que j'utilise pour analyser une décision d'utiliser (ou non) MapReduce.

• Atteindre une performance d'exécution parallèle raisonnable avec un minimum d'effort du programmeur est-il important pour un problème donné?
• Est-ce que j'ai un grand nombre (des centaines) d'éléments d'exécution parallèle disponibles?
• La bande passante / le débit de communication est-il excellent entre les éléments d’exécution parallèles?
• Dois-je traiter une quantité énorme de données?

• Est-ce que le problème que je tente de résoudre se décompose en opérations Map and Reduce?

  • Carte: exécute la même opération sur toutes les données.
  • Réduire: Exécutez la même opération sur chaque groupe de données générées par Map.

En fait, il s'agit d'un modèle générique "diviser pour régner", de sorte que les solutions de répartition du calcul puissent être écrites de manière générique.

un exemple simple est comme un grand document. le problème est que vous voulez compter le nombre de lettres dans ce document. au lieu de fonctionner sur une seule machine, vous pouvez le décomposer en un tableau de tous les mots du document. Ensuite, vous pouvez traiter chaque mot individuellement et les résultats réunis.

le modèle est utile, car une fois que vous obtenez une carte générique / une implémentation réduite, vous pouvez résoudre n'importe quel problème en utilisant la même couche logicielle, il vous suffit d'exprimer votre problème en termes de problème.