Que tipo de problemas o MapReduce resolve?

São basicamente problemas que são enormes, mas não difíceis. O vendedor ambulante depende crucialmente da distância entre qualquer par de cidades, portanto, embora possa ser dividido em várias partes, os resultados parciais não podem ser recombinados para que a solução globalmente ideal emerja (bem, provavelmente não Se você souber uma maneira, solicite sua medalha Fields agora).

Por outro lado, a contagem de frequências de palavras em um corpus gigantesco é trivialmente particionável, e trivialmente recombinável (você apenas soma os vetores calculados para os segmentos do corpus), então map-reduce é a solução óbvia.

Na prática, mais problemas tendem a ser facilmente recombináveis do que não, então a decisão de paralelizar uma tarefa ou não tem mais a ver com o quão grande é a tarefa, e menos com a dificuldade.

O problema pode ser resolvido eficientemente usando a computação distribuída?

Se a resposta a esta pergunta for sim, você tem um problema de candidato para o MapReduce. Isso ocorre porque o padrão do problema se presta a ser dividido em pequenos problemas isolados.

Sua tarefa: analisar este livro

Um exemplo funciona bem para ilustrar isso. Você tem um grande documento (Moby Dick, de Herman Melville, ) e seu trabalho é realizar uma análise de freqüência. de todas as palavras usadas nele.

A abordagem sequencial

Você pode fazer isso sequencialmente, obtendo sua máquina mais rápida (você tem muito por aí) e correndo sobre o texto do começo ao fim, mantendo um mapa de cada palavra que você encontrar (a chave) e incrementando a freqüência ) toda vez que você analisar uma palavra. Simples, direto e lento.

A abordagem do MapReduce

Aproximando-se disso de uma perspectiva diferente, você percebe que tem todas essas máquinas de reposição por aí e pode dividir essa tarefa em partes. Dê a cada máquina um bloco de texto de 1Mb para analisar em um mapa de hash e, em seguida, agrupe todos os mapas de hash de cada um em um único resultado. Esta é uma solução MapReduce em camadas.

O processo de ler uma linha de texto e reunir as palavras é a fase do Mapa (você cria um mapa simples representando as palavras na linha com sua frequência 1,2,3 etc), então a fase Reduzir é quando cada máquina agrupa seus mapas de linha em um único mapa agregado.

A solução global vem de uma outra fase Reduzir, onde todos os mapas agregados são agregados (essa palavra novamente) em um mapa final. Ligeiramente mais complexo, maciçamente paralelo e rápido.

Resumo

Então, para resumir, se o seu problema se presta a ser representado por chaves, valores, agregue operações nesses valores de forma isolada, então você tem um problema de candidato para o MapReduce.

O padrão MapReduce é retirado do mundo da programação funcional. É um processo para aplicar algo chamado de catamorfismo sobre uma estrutura de dados em paralelo. Os programadores funcionais usam catamorfismos para praticamente todas as transformações ou resumos simples.

Supondo que seus dados são uma árvore, o fator decisivo é se você pode calcular um valor para um nó usando apenas os dados contidos nesse nó e os valores calculados para seus filhos.

Por exemplo, você pode calcular o tamanho de uma árvore usando um catamorfismo; você calcularia a soma dos valores calculados para todos os filhos mais um.

Este WPI - Aplicativos de Redução de Mapa (ppt) podem ser de interesse para você. Ele discute diferentes aplicações do MR e, como um dos casos discutidos, mostra como usar 100 instâncias do EC2 e 24 horas, o New York Times conseguiu converter 4 TB de artigos digitalizados em 1,5 TB de documentos PDF.

Outro conjunto de exemplos em que o MR ajudou a acelerar o desempenho está em: Aster-SQL Map Reduce mostra alguns estudos de caso da tecnologia SQL-Map Reduce, incluindo Detecção de Fraudes, Transformações e outros.

Mapear / Reduzir é uma forma específica de um tipo específico de algoritmo. Você o usa para transformar um enorme conjunto de dados em outro conjunto de dados. (O conjunto de dados resultante pode ou não ser enorme.) Se você não deseja que uma saída de dados estáticos seja definida como resultado da entrada de dados estáticos, então Mapear / Reduzir não é apropriado. Map / Reduce pode facilmente dizer quantos John Smiths estão na lista telefônica de Manhattan, mas não é adequado para construir um servidor web.

A maneira como o Map / Reduce funciona é:

• O mapa pega pares de chaves (k1) e valores (v1) e os mapeia em um novo conjunto de chaves (k2) e valores (v2).
• Reduzir leva todos os valores v2 com a mesma chave k2 e produz um novo valor (v3).

O resultado é que uma lista de pares (k1, v1) é transformada em uma lista de (v3) s. (É claro que o valor "v3" pode ser um composto que inclua k2, que pode ser definido como igual a k1.)

Então você usa:

1. Se você tiver muitos dados para começar, a execução sequencial de um ou dois servidores demoraria muito tempo e

2. Você pode conceber os dados de saída como uma lista de valores ou pares de valores de chave (geralmente não é muito difícil quando você lembra que "chave" significa apenas "rótulo exclusivo") e

3. Qualquer que seja o relacionamento, você tem certeza de que cada dado de entrada afeta apenas o valor de saída de uma chave de saída.

Se todos os seus dados puderem ser processados sequencialmente por um único servidor, então, como esse é o paradigma de computação dominante (para os quais os servidores são criados e os programadores são treinados), use um único servidor.

O estágio do mapa tem que particionar todos os dados de entrada pela chave de saída. Ele não precisa produzir o valor de saída associado à chave de saída (isso é feito pelo estágio de redução), mas deve atribuir exclusivamente cada par de valores de chave de entrada para contribuir com no máximo um valor de chave de saída. Se os dados estiverem muito inter-relacionados, o map reduce poderá não ser capaz de lidar com o problema. Por outro lado, pode ser que você precise usar várias rodadas de map / reduce.

Se você não consegue descobrir como transformar sua transformação de dados em um mapa / reduzir, é claro que não é uma solução.

Existe uma verdadeira arte para descobrir se um problema pode ser decomposto em algo que o Map / Reduce pode manipular. Por exemplo, v1 e v2 podem não estar nos conjuntos de dados de entrada ou saída. Se você quiser apenas contar itens únicos nos dados de entrada, então k1 = k2 = um item e v1 = v2 = 1 ou 0 ou realmente qualquer coisa. Reduzir apenas produz v3 como a soma do número de k2 que foi dado.

Portanto, é difícil dizer com certeza que uma transformação de dados não pode ser feita usando Mapear / Reduzir, mas o que foi descrito acima fornece algumas diretrizes.

MapReduce funciona em qualquer problema que é composto de exatamente 2 funções em algum nível de abstração. A primeira função é aplicada a cada um dos itens no conjunto de entrada e a segunda função agrega os resultados.

Assim, sempre que você quiser obter (1) o resultado de (n) entradas, e todas as entradas puderem ser examinadas / usadas pela (1) função, você pode usar o MapReduce. Novamente, isso está em um nível específico de abstração. A função (1) pode ser uma função de agrupamento que verifica a entrada e decide qual das várias outras funções usar.

Isto é útil quando você não sabe antecipadamente quanta entrada você terá, quando você precisa dividir "unidades" de trabalho discretas, ou quando você quer que um único retorno represente o resultado inteiro (ou seja, executando cinco mil testes de unidade, e se menos de x% falhar, retorne o sucesso).

A maioria das respostas aqui parece ser alguma variação de explicar o que o mapa reduz, o que é válido. Mas, para responder à pergunta, qual seria o padrão que sinalizaria onde você poderia usar o mapa, a redução não é realmente abordada por isso.

Se a implementação ingênua, não funcional, do problema que você está procurando envolver um loop sobre algo e, em seguida, atualizar algo fora do loop com algum estado de dentro do loop, é provável que você tenha algo que portas bem reduzam. Especialmente se você puder generalizar a atualização do estado central para uma função que funcione com apenas dois parâmetros e possa garantir que essa função seja comutativa e associativa.

O motivo pelo qual você poderia querer usar o mapa reduzir se isso for verdade é duplicado: 1) pode ser um pouco mais limpo e mais fácil de testar e depurar se você dividir as coisas no mapa e reduzir as funções. 2) map reduzir funções são stateless e podem ser executadas simultaneamente, o que acelera as coisas se você tiver vários processadores disponíveis e algo como hadoop ou faísca que faz uso disso para executar coisas em um cluster.

Isso é bom se você estiver dando muitas voltas, mas sua milhagem pode variar dependendo de quão complexos são seus mapas / reduções. É bastante comum acabar com uma cadeia sequencial ou uma árvore de reduções de mapa, onde no final tudo ainda é limitado em alguma etapa de redução complexa no final da cadeia. Por exemplo, muitos algoritmos gráficos são difíceis de dimensionar eficientemente com apenas redução de mapa.

O exemplo mais simples que funciona bem com redução de mapa, é contar as coisas, o que é uma redução muito barata. É por isso que a contagem de palavras é um exemplo frequentemente usado para redução de mapas. Você pode esperar uma escalabilidade linear para desempenho com esse uso: cada cpu que você adiciona o torna mais rápido.

Se você faz muita programação funcional, você começa a se deparar com situações que exigem um mapa geral e reduzem. Você provavelmente até os vê em programação imperativa, mas não os reconhece atrás da máscara de loops e acumuladores.

Como exemplo de um que surgiu para mim recentemente, trabalhei em um analisador em Haskell. Para testar meu analisador, eu insiro uma lista de fragmentos de seqüência de caracteres por meio do analisador e, em seguida, desejo obter uma única cadeia de caracteres que possa gerar meus resultados para ver se ela foi analisada corretamente. Então, parece que:

--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)))

Claro, isso é apenas pedagógico. Meu código real parece um pouco diferente e usa mais funções internas (como fold concat não é necessário, pois o Haskell já inclui unlines que faz [String]->String ). Meu ponto principal foi que eu não esperava usar um mapa / reduzir quando comecei, apenas alinhado às minhas necessidades. Eu queria fazer algumas coisas com listas, depois transformar minha lista em um único elemento de saída. O uso de mapa / redução surgiu naturalmente.

O processamento de sequências (como a análise) é um uso muito óbvio da redução de mapa, o mapeamento é a aplicação de várias transformações no texto de entrada e reduz o retorno do texto do resultado como saída. Da mesma forma, um compilador poderia ser semelhante, usando dobras para transformar um fluxo de elementos da Árvore de Sintaxe Abstrata em uma forma melhor (otimização).

É paralelizável?

Qualquer problema de paralelismo é essencialmente mapear e dobrar; Por outro lado, a etapa do mapa é inerentemente paralelizável (e a etapa de dobra pode ser, dependendo da estrutura sobre a qual ela está sendo dobrada), portanto, essa é uma propriedade bidirecional.

Digamos que você esteja pesquisando um cluster de servidores e não seja possível responder nesse momento. O que mapReduce fará é que ele não poderia acessar o nó da árvore para o mapa maior, pois ele reagendará para mais tarde e executará o Map ou o Reduce. Essencialmente, ele tenta garantir que todas as informações estejam disponíveis com a imprevisibilidade de software e hardware em ambientes.

Aqui estão as principais perguntas que uso para investigar uma decisão de usar (ou não usar) o MapReduce.

• A obtenção de um desempenho razoável de execução paralela com um esforço mínimo do programador é importante para um determinado problema?
• Eu tenho um grande número (centenas) de elementos de execução paralela disponíveis?
• Existe excelente largura de banda / throughput de comunicação entre os elementos de execução paralela?
• Preciso processar uma quantidade enorme (TB) de dados?

• O problema que estou tentando resolver se decompõe na operação Mapear e Reduzir?

  • Mapa: execute a mesma operação em todos os dados.
  • Reduzir: execute a mesma operação em cada grupo de dados produzidos pelo Mapa.

na verdade, é um padrão genérico de "dividir e conquistar", de modo que as soluções para distribuir a computação possam ser escritas genericamente.

um exemplo simples é como um documento grande. O problema é que você quer contar o número de letras nesse documento. em vez de rodar em uma única máquina, você pode dividi-la em uma matriz de todas as palavras do documento. então você pode processar cada palavra individualmente e os resultados juntos novamente.

o padrão é útil, porque uma vez que você tenha um mapa genérico / reduza a implementação, você pode resolver qualquer problema usando a mesma camada de software, você só precisa expressar o seu problema em termos disso.