MapReduce est-il autre chose qu'une simple application de division et de conquête?

Diviser un problème en plus petits jusqu'à ce que les problèmes individuels puissent être résolus indépendamment, puis les combiner pour répondre à la question d'origine est connu sous le nom de technique de conception d'algorithmes de division et de conquête . [Voir: Introduction aux algorithmes par CLR]

Récemment, cette approche pour résoudre des problèmes de calcul, en particulier dans le domaine des ensembles de données très volumineux, a été appelée MapReduce plutôt que diviser pour mieux régner.

Ma question est la suivante: MapReduce est-il autre chose qu'un cadre propriétaire qui repose sur l'approche diviser pour régner, ou y a-t-il des détails qui le rendent unique à certains égards?

Si vous posez des questions sur l'architecture MapReduce, il ne s'agit que d'une technique de division et de conquête . Cependant, toute architecture MapReduce utile aura des montagnes d'autres infrastructures en place pour "diviser", "conquérir" et enfin "réduire" l'ensemble de problèmes. Avec un grand déploiement MapReduce (des milliers de nœuds de calcul), ces étapes pour partitionner le travail, calculer quelque chose et enfin collecter tous les résultats ne sont pas triviales. Des choses comme l'équilibrage de charge, la détection des nœuds morts, l'enregistrement de l'état intermédiaire (pour les problèmes de longue durée), sont des problèmes difficiles en eux-mêmes.

MapReduce est un cadre pour implémenter des algorithmes de division et de conquête d'une manière extrêmement évolutive , en distribuant automatiquement des unités de travail aux nœuds dans un cluster d'ordinateurs arbitrairement grand et en gérant automatiquement les défaillances de nœuds individuels en redistribuant l'unité de travail vers un autre nœud.

Ce n'est pas un concept super sophistiqué, mais une infrastructure très utile.

MapReduce diverge de la plupart des systèmes de division et de conquête d'une manière assez fondamentale, mais si simple que beaucoup de gens la manquent presque. Le vrai génie est de marquer les résultats intermédiaires.

Dans un système de division et de conquête classique (précédent), vous divisez le travail en série, exécutez des paquets de travail en parallèle, puis fusionnez à nouveau les résultats de ce travail en série.

Dans MapReduce, vous divisez le travail en série, exécutez des paquets de travail en parallèle et étiquetez les résultats pour indiquer quels résultats vont avec quels autres résultats. La fusion est alors en série pour tous les résultats avec la même balise, mais peut être exécutée en parallèle pour les résultats qui ont des balises différentes.

Dans la plupart des systèmes précédents, l'étape de fusion est devenue un goulot d'étranglement pour toutes les tâches sauf les plus triviales. Avec MapReduce, cela peut toujours être le cas si la nature des tâches nécessite que toutes les fusions soient effectuées en série. Si, cependant, la tâche permet un certain degré de fusion parallèle des résultats, alors MapReduce donne un moyen simple de tirer parti de cette possibilité. La plupart des autres systèmes font l'une des deux choses suivantes: soit exécutez toutes les fusions en série simplement parce que cela peut être nécessaire pour certaines tâches, soit définissez statiquement la fusion parallèle pour une tâche particulière. MapReduce vous donne suffisamment de données à l'étape de la fusion pour planifier automatiquement autant en parallèle que possible, tout en garantissant (en supposant que vous n'avez pas fait d'erreur dans l'étape de mappage) que la cohérence est maintenue.

Notez également que dans MapReduce, il est implicite que toutes les étapes peuvent être récursives, donc je pourrais avoir une étape de mappage initiale qui décompose une grosse tâche en 5 tâches plus petites qui peuvent être exécutées en parallèle - mais chacune d'entre elles pourrait (dans tourner) pour être mappé sur un certain nombre d'autres tâches parallèles plus petites, etc.

Cela conduit à une structure arborescente à la fois sur les côtés de cartographie et de réduction pour décomposer rapidement une tâche importante en suffisamment de morceaux pour tirer parti de nombreuses machines.

MapReduce n'est pas simplement une technique de division et de conquête, bien qu'elle ressemble à cela dans de nombreux exemples.

Au cours de l'étape de mappage, vous pouvez et souhaitez fréquemment effectuer une relation un-à-plusieurs. Ainsi, vous ne vous divisez pas simplement en cas.

Entre la carte et la réduction, il y a soit (selon l'implémentation) une étape de tri ou de hachage. L'efficacité de cette opération est extrêmement importante pour les besoins globaux en ressources. Ses détails sont invisibles pour le programmeur d'application, mais cette étape est au cœur du framework.

L'opération de réduction est un type de fusion. Ce qui peut être considéré comme une conquête, mais dans la pratique, il a tendance à «émettre des données pour une utilisation ultérieure» ou à «enregistrer des données dans un magasin de données». (Remarque: si vous avez de grands ensembles de données, vous voulez vraiment que tout soit distribué, y compris les résultats d'entrée et les résultats finaux. Un stockage de clé / valeur distribué a donc un sens à la fois comme un endroit pour obtenir l'entrée et pour stocker la sortie.)