Qual é a novidade do MapReduce?

68

Alguns anos atrás, o MapReduce foi aclamado como uma revolução da programação distribuída. Também houve críticas, mas em geral houve um entusiasmo entusiasmado. Até foi patenteado! [1]

O nome é uma reminiscência de mape reducena programação funcional, mas quando li (Wikipedia)

Etapa do mapa: O nó principal pega a entrada, a divide em subproblemas menores e as distribui para os nós trabalhadores. Um nó de trabalho pode fazer isso novamente por sua vez, levando a uma estrutura em árvore de vários níveis. O nó do trabalhador processa o problema menor e passa a resposta de volta ao seu nó mestre.

Reduzir etapa: O nó mestre, em seguida, coleta as respostas para todos os subproblemas e as combina de alguma forma para formar a saída - a resposta para o problema que estava originalmente tentando resolver.

ou [2]

Internos do MAP: [...] MAP divide o valor de entrada em palavras. [...] MAP destina-se a associar cada par de chave / valor da entrada com potencialmente muitos pares de chave / valor intermediários.

Internos de REDUCE: [...] [REDUCE] executa agregação imperativa (por exemplo, redução): pegue muitos valores e reduza-os a um único valor.

Não posso deixar de pensar: isso é dividir e conquistar (no sentido de Mergesort), puro e simples! Então, há alguma novidade (conceitual) no MapReduce em algum lugar ou é apenas uma nova implementação de idéias antigas úteis em determinados cenários?


  1. Patente US 7.650.331: "Sistema e método para processamento eficiente de dados em larga escala" (2010)
  2. Modelo de programação MapReduce do Google - revisitado por R. Lämmel (2007)
Rafael
fonte
7
Não há novidade. Não vou responder a isso, mas é minha opinião forte que nada de novo em computação, ou mesmo computação distribuída, foi descoberto pelo MapReduce.
EdA-qa mort-ora-y
@Aryabhata: Se houver novidade, esta pergunta terá uma resposta boa e construtiva. Se não houver, pouco pode ser dito para provar isso (exceto, talvez, reduzindo o MapReduce para uma técnica mais antiga explicitamente), true. Mas se você se sente assim, por todos os meios, vote!
Raphael
@ edA-qamort-ora-y: Nesse caso, poderíamos expressar o MapReduce em termos mais antigos, e isso daria uma boa resposta!
Raphael
11
@ Rafael, eu concordo, mas não tenho certeza se posso fazer isso. No entanto, posso observar que, conforme descrito aqui (primeira citação), a classificação por mesclagem usa o método exato de mapear / reduzir. Pode, de fato, ser distribuído com alteração zero.
EdA-qa mort-ora-y

Respostas:

47

Não consigo deixar de pensar: isso é dividir e conquistar, puro e simples!

M / R não é dividir e conquistar. Não envolve a aplicação repetida de um algoritmo para um subconjunto menor da entrada anterior. É um pipeline (uma função especificada como uma composição de funções mais simples) em que os estágios do pipeline alternam o mapa e reduzem as operações. Diferentes estágios podem executar operações diferentes.


Então, há alguma novidade (conceitual) no MapReduce em algum lugar ou é apenas uma nova implementação de idéias antigas úteis em determinados cenários?

O MapReduce não abre novos caminhos na teoria da computação - não mostra uma nova maneira de decompor um problema em operações mais simples. Isso mostra que operações mais simples são práticas para uma classe de problemas específica.


A contribuição do artigo MapReduce foi

  1. avaliar um pipeline de dois operadores ortogonais bem compreendidos que podem ser distribuídos de forma eficiente e tolerante a falhas em um problema específico: criar um índice de texto de corpus grande
  2. mapa de benchmarking - reduza esse problema para mostrar a quantidade de dados transferidos entre os nós e como as diferenças de latência nos estágios afetam a latência geral
  3. mostrando como tornar o sistema tolerante a falhas para que as falhas da máquina durante o cálculo possam ser compensadas automaticamente
  4. identificação de escolhas e otimizações de implementação úteis específicas

Algumas das críticas se enquadram nessas classes:

  1. "Mapear / reduzir não abre novos caminhos na teoria da computação." Verdadeiro. A contribuição do artigo original foi que esses operadores bem compreendidos, com um conjunto específico de otimizações, foram usados ​​com sucesso para resolver problemas reais com mais facilidade e tolerância a falhas do que soluções pontuais.
  2. "Este cálculo distribuído não se decompõe facilmente em operações de mapeamento e redução". Justo, mas muitos o fazem.
  3. "Um pipeline de n estágios de mapa / redução requer latência proporcional ao número de etapas de redução do pipeline antes que quaisquer resultados sejam produzidos." Provavelmente verdade. O operador de redução precisa receber toda a sua entrada antes que possa produzir uma saída completa.
  4. "Mapear / reduzir é um exagero para este caso de uso." Talvez. Quando os engenheiros encontram um novo martelo brilhante, tendem a procurar qualquer coisa que se pareça com um prego. Isso não significa que o martelo não seja uma ferramenta bem feita para um determinado nicho.
  5. "Mapear / reduzir é um mau substituto para um banco de dados relacional." Verdadeiro. Se um banco de dados relacional se ajusta ao seu conjunto de dados, então é maravilhoso para você - você tem opções.
Mike Samuel
fonte
Bem, eles chamam o artigo original de "seminal", então espero algo novo. Não entendo seu primeiro parágrafo: claramente existem muitas técnicas algorítmicas que não são divididas e conquistadas . Se o MapReduce é "apenas" uma implementação eficiente da d & c para um conjunto de problemas específico, certamente não é nada seminal ou digno de patente em algoritmos (imho). Isso não diz que não é um bom sistema. Observe que minha crítica é menos com o próprio MapReduce (acho que é bom para o que foi feito) do que com a recepção pela comunidade.
Raphael
11
@ Rafael, eu não acho que M / R é dividir e conquistar no sentido em que você está vinculado. Não envolve a aplicação repetida de um algoritmo para um subconjunto menor da entrada original. É um pipeline em que os estágios do pipeline alternam o mapa e reduzem as operações.
Mike Samuel
É verdade. Interpretei "Um nó de trabalho pode fazer isso novamente por sua vez, levando a uma estrutura em árvore de vários níveis". dessa maneira, mas é claro que isso não implica que o mesmo ocorra em todos os níveis.
Raphael
11
@ ex0du5, acho que você pode estar condenando-o por alegações de que não faz. "Muitos sistemas forneceram modelos de programação restritos e usaram as restrições para paralelizar a computação automaticamente. ... O MapReduce pode ser considerado uma simplificação e destilação de alguns desses modelos com base em nossa experiência com grandes computações do mundo real. , a maioria dos sistemas de processamento paralelo foi implementada apenas em escalas menores e deixa os detalhes de manipulação de falhas da máquina para o programador ". Cita artigos de Rabin e Valiant sobre isso, mas não o artigo de Liskov.
Mike Samuel
11
@ ex0du5, bastante justo. Eu pensei que "" Mapear / reduzir não abre novos caminhos na teoria da computação. "Verdade. foi claro o suficiente, mas reescrevi a lista de contribuições.
Mike Samuel
21

EDIT (março de 2014) Devo dizer que, desde então, trabalhei mais em algoritmos para modelos de computação do tipo MapReduce e sinto que estava sendo excessivamente negativo. A técnica Divide-Compress-Conquer de que falo abaixo é surpreendentemente versátil e pode ser a base de algoritmos que considero não triviais e interessantes.


Deixe-me oferecer uma resposta que será muito inferior à de Mike em termos de abrangência, mas do ponto de vista do modelo de teoria da computação / algoritmo.

Por que há emoção : MapReduce intercala computação paralela e seqüencial; cada processador tem acesso a um pedaço não trivial (por exemplo, ) da entrada e pode executar uma operação não trivial nela; isso é muito diferente dos modelos PRAM e parece uma idéia interessante que pode levar a novas técnicas algorítmicas. Em particular, alguns problemas podem ser resolvidos em poucas rodadas de cálculo (constante no tamanho da entrada), enquanto nenhum problema não trivial pode ser resolvido na PRAM em .O(nϵ)o(logn)

Por que o modelo está ficando um pouco frustrante para mim : A única técnica algorítmica que parece funcionar para obter algoritmos de arredondamento e é algo novo é a seguinteO(1)

  • Particionar a instância do problema (geralmente aleatoriamente)
  • Faça algum cálculo em cada partição em paralelo e represente o resultado do cálculo compactamente
  • Combine todas as soluções de subproblemas representadas compactamente em um único processador e termine o cálculo lá

Exemplo muito simples da técnica: calcule a soma de números. Cada processador possui da matriz e calcula a soma dessa parte. Todas as somas podem ser combinadas em um único processador para calcular a soma total. Um exercício um pouco mais interessante é calcular todas as somas de prefixos dessa maneira (é claro que nesse caso a saída deve ser representada de forma distribuída). Ou calcule uma árvore de abrangência de um gráfico denso.nO(n)n

Agora, acho que isso é realmente uma reviravolta interessante na divisão e conquista, a reviravolta é que, após o estágio de divisão, você precisa compactar soluções de subproblemas para que um único processador possa conquistar. No entanto, essa realmente parece ser a única técnica que criamos até agora. Ele falha em problemas com gráficos esparsos, como conectividade esparsa, por exemplo. Compare isso com o modelo de streaming, que levou a uma riqueza de novas idéias, como o algoritmo de amostragem ingênuo de Flajolet e Martin, o algoritmo de emparelhamento determinístico de Misra e Gries, o poder de técnicas simples de desenho etc.

Como paradigma de programação, a redução de mapas tem sido muito bem-sucedida. Meus comentários consideram o mapa reduzido como um modelo interessante de computação. Bons modelos teóricos são um pouco estranhos. Se eles seguem a realidade muito de perto, são difíceis de manejar, mas o mais importante é que (para emprestar um termo do aprendizado de máquina) os teoremas provados para modelos muito específicos não generalizam, ou seja, não são válidos em outros modelos. É por isso que queremos abstrair o máximo de detalhes possível, deixando ainda o suficiente para nos desafiar a criar novos algoritmos. Por fim, essas novas idéias poderão, eventualmente, encontrar o caminho de volta ao mundo real. O PRAM é um modelo irrealista que levou a idéias interessantes, mas essas idéias provaram ser raramente aplicáveis ​​à computação paralela no mundo real. Por outro lado, o streaming também não é realista, mas inspirou idéias algorítmicas que são realmente empregadas no mundo real. Vejoesboço de contagem-min . As técnicas de desenho também são usadas em sistemas baseados em redução de mapa.

Sasho Nikolov
fonte
Indiscutivelmente M / R é um modelo mais realista (útil) do que PRAM ou fluxos. (Pelo menos para alguns razoavelmente grande conjunto de problemas.)
Xodarap
"você precisa compactar soluções de subproblemas para que um único processador possa conquistar" - Você parece estar dizendo que o conjunto de problemas que podem ser resolvidos pelo M / R é um subconjunto daqueles para os quais existem cache ou cache que podem ser rastreados soluções -blivious. Se estiver certo, parece-me que essa afirmação se aplica igualmente bem à maioria dos esquemas de computação distribuídos.
Mike Samuel
11
@Xodarap que pode muito bem ser. aqui estou usando um ponto de vista teórico puramente de algoritmos: um modelo é útil se leva a novas perspectivas algorítmicas. por essa medida, o streaming não é totalmente realista, mas levou a inúmeras novas técnicas que são realmente úteis na prática. o ponto é: qual é a abstração correta que leva a um novo pensamento. abstrações atuais de MR têm misto de sucesso (mas acho que é um pouco de sucesso)
Sasho Nikolov 03/08/2012
11
@ MikeSamuel, a "necessidade" nessa frase significa que é isso que a técnica exige para funcionar, não que seja a única coisa possível a ser feita. não existem resultados teóricos negativos para a RM que eu conheça. minha queixa não é que o MR seja estritamente menos poderoso que o CO. é que não vimos muito novo pensamento algorítmico inspirado no modelo (o que é bom para um sistema, mas decepcionante para um modelo de computação). do outro em si obliviousness cache de mão é uma idéia incrível imo
Sasho Nikolov
@SashoNikolov, Entendido. Obrigado por explicar.
Mike Samuel
6

Eu concordo plenamente com você. De uma perspectiva conceitual, não há nada realmente novo: o Map / Reduce era originalmente conhecido na Parallel Computing como um modelo de programação de fluxo de dados. No entanto, do ponto de vista prático, o Map / Reduce, conforme proposto pelo Google e com as subsequentes implementações de código aberto, também alimentou a computação em nuvem e agora é bastante popular para decomposições e processamento paralelos muito simples. Obviamente, não é adequado para qualquer outra coisa que exija domínio complexo ou decomposições funcionais.

Massimo Cafaro
fonte
3

Acho que você acertou a cabeça com seu comentário.

Não é verdade que, em qualquer idioma funcional, os mapas possam ser paralelizados - o idioma deve ser puro . (Acredito que Haskell é a única linguagem puramente funcional e vagamente convencional. Lisp, OCaml e Scala são todos não puros.)

Sabemos dos benefícios do código puro desde antes do compartilhamento do tempo, quando os engenheiros fizeram o pipeline de seus processadores. Então, como é que ninguém usa uma linguagem pura?

É muito, muito, muito difícil. Programar em uma linguagem pura geralmente é como programar com as duas mãos amarradas nas costas.

O que o MR faz é relaxar um pouco a restrição de pureza e fornecer uma estrutura para outras partes (como a fase aleatória), facilitando a gravação de código distribuível para uma grande fração de problemas.

Acho que você esperava uma resposta como "Isso prova esse importante sub-lema de " e não acho que faça algo desse tipo. O que isso faz é mostrar que uma classe de problemas conhecidos por serem distribuíveis é "facilmente" distribuível - se isso é uma "revolução", na sua opinião, provavelmente depende de quanto tempo você passou depurando código distribuído em um mapa pré-mapa / redução mundo.NC=P

Xodarap
fonte
Não estou familiarizado com o MapReduce, mas sua apresentação não parece diferente do que me lembro de ter sido apresentado como o caso ideal no Paralelismo 101 no século anterior.
Gilles 'SO- stop be evil'
@Gilles: Minha intenção era apenas mostrar que "dividir e conquistar"! = " Dividir e conquistar distribuível ". M / R é menos trivial, embora, sem dúvida, ainda não seja original.
Xodarap
Na programação funcional, todos os mapas podem ser paralelos (embaraçosamente); então, por que não seguir esse paradigma? Não vejo como counté uma variável compartilhada no seu pseudo-código; simplesmente passar seu valor atual para do_somethingdeve funcionar. Você pode dar um exemplo de um algoritmo d & c "real" (Mergesort, Quicksort, ...) do qual as chamadas recursivas dependem uma da outra (após a emissão da chamada)?
Raphael
@ Rafael: Eu reescrevi minha resposta para responder melhor ao seu comentário. Posso adicionar um exemplo de quando a pureza é irritante, se você ainda quiser.
Xodarap 08/08
11
@ Rafael: Eu concordo que minha resposta seria muito melhor se eu pudesse citar algum artigo mostrando que o tempo de programação cai de X horas para Y usando M / R ou aumenta de A para B impondo pureza, mas acho que tudo o que posso fazer é acenar furiosamente minhas mãos e insistir que as diferenças não são triviais.
Xodarap