Que tipo de problemas o MapReduce resolve?

Eu tenho lido sobre o MapReduce por um tempo - mas o que não consigo entender é como alguém tomaria a decisão de usar (ou não usar) o MapReduce.

Quero dizer, quais são os padrões de problemas que sinalizam que o MapReduce pode ser usado.

São basicamente problemas enormes, mas não difíceis. O vendedor ambulante depende crucialmente da distância entre um determinado 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 surja (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); portanto, reduzir o mapa é a solução óbvia.

Na prática, mais problemas tendem a ser facilmente recombináveis ​​do que não; portanto, a decisão de paralelizar ou não uma tarefa tem mais a ver com o tamanho da tarefa e menos com a dificuldade.

O problema pode ser resolvido com eficiência usando computação distribuída?

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

Sua tarefa: Analisar este livro

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

A abordagem seqüencial

Você pode fazer isso sequencialmente, obtendo sua máquina mais rápida (você tem muitas coisas por aí) e passando o texto do início ao fim, mantendo um mapa de hash de cada palavra encontrada (a chave) e aumentando a frequência (valor) toda vez você analisa uma palavra. Simples, direto e lento.

A abordagem MapReduce

Abordando isso de uma perspectiva diferente, observe que você tem todas essas máquinas sobressalentes 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 coletar as palavras é a fase Mapa (você cria um mapa simples que representa as palavras na linha com a frequência 1,2,3 etc.); a fase Reduzir é quando cada máquina agrupa sua linha mapeia em um único mapa agregado.

A solução geral vem de uma fase adicional de Redução, na qual todos os mapas agregados são agregados (essa palavra novamente) em um mapa final. Um pouco mais complexo, massivamente paralelo e rápido.

Sumário

Portanto, para resumir, se o seu problema se presta a ser representado por chaves, valores, operações agregadas nesses valores isoladamente, você tem um problema candidato ao MapReduce.

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

Supondo que seus dados sejam 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ê computaria a soma dos valores calculados para todos os filhos mais um.

Este WPI - Aplicativos de redução de mapa (ppt) pode ser do seu interesse. Ele discute as diferentes aplicações do MR e, como um dos casos discutidos, mostra como, usando 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 grande conjunto de dados em outro. (O conjunto de dados do resultado pode ou não ser enorme.) Se você não deseja que uma saída de dados estática seja definida como resultado da entrada de dados estáticos, Mapear / Reduzir não é apropriado. O Map / Reduce pode facilmente dizer quantos John Smiths existem na lista telefônica de Manhattan, mas não é adequado para criar um servidor da web.

A maneira como 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 usa todos os valores de 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. (Obviamente, o valor "v3" pode ser um composto que inclui k2, que pode ser definido como igual a k1.)

Então você o usa:

1. Se você tiver tantos dados para começar, executar tudo sequencialmente em um ou dois servidores levaria muito tempo e

2. Você pode conceber os dados de saída como uma lista de valores ou pares de valores-chave (geralmente não muito difícil quando se lembra de 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 ​​seqüencialmente por um único servidor, como esse é o paradigma de computação dominante (os servidores para os quais os servidores foram criados e os programadores são treinados), use um único servidor.

O estágio do mapa deve 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 no estágio de redução), mas precisa atribuir exclusivamente cada par de valores de chave de entrada para contribuir com no máximo o valor de uma chave de saída. Se os dados estiverem muito inter-relacionados, a redução de mapa pode não ser capaz de lidar com o problema. Por outro lado, pode ser que você precise usar várias rodadas de mapa / redução.

Se você não consegue descobrir como transformar sua transformação de dados em um mapa / redução, é 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 exclusivos 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 fornecido.

Portanto, é difícil afirmar com certeza que uma transformação de dados não pode ser feita usando Map / Reduce, mas o acima fornece algumas orientações.

O MapReduce funciona em qualquer problema 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 entradas e a segunda função agrega os resultados.

Portanto, sempre que você desejar obter (1) resultado de (n) entradas, e todas as entradas puderem ser examinadas / usadas pela (1) função, você poderá usar o MapReduce. Novamente, isso está em algum 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.

Isso é útil quando você não sabe antecipadamente quanta entrada terá, quando precisa compartilhar "unidades" de trabalho discretas ou quando deseja que um único retorno represente o resultado inteiro (ou seja, cinco mil testes de unidade) e, se menos de x% falharem, retorne com êxito).

A maioria das respostas aqui parece ser uma variação de explicar o que o mapa reduz, o que é válido. Mas, para responder à pergunta, qual era o padrão que indicaria onde você pode usar a redução de mapa não é realmente abordado por isso.

Se a implementação ingênua e não funcional do problema que você está visualizando envolve repetir algo e depois atualizar algo fora do loop com algum estado de dentro do loop, é provável que você tenha algo que as portas sejam bem mapeadas para reduzir. Especialmente se você puder generalizar a atualização do estado central para uma função que funcione com apenas dois parâmetros e garantir que essa função seja comutativa e associativa.

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

Isso é bom se você estiver repetindo várias coisas, mas sua milhagem pode variar dependendo da complexidade do seu mapa / redução. É bastante comum acabar com uma cadeia seqüencial ou árvore de reduções de mapa, onde no final tudo ainda está prejudicado em alguma etapa complexa de redução no final da cadeia. Por exemplo, muitos algoritmos gráficos são difíceis de escalar eficientemente com apenas uma redução de mapa.

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

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

Como exemplo de um que surgiu para mim recentemente, tenho trabalhado em um analisador em Haskell. Para testar meu analisador, eu bombeio uma lista de fragmentos de string pelo analisador e, em seguida, desejo obter uma única string que possa gerar meus resultados para ver se ele foi analisado corretamente. Então, isso se parece com:

--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 atual parece um pouco diferente e usa mais funções internas (como fold concatnão é necessário, pois Haskell já inclui unlinesisso [String]->String). Meu ponto principal era que eu não previa o uso de um mapa / redução quando comecei, apenas alinhado às minhas necessidades. Eu queria fazer algumas coisas com listas e depois transformar minha lista em um único elemento de saída. O uso do mapa / redução surgiu naturalmente.

O processamento de strings (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 resultado da recomposição do texto resultante. Da mesma forma, um compilador pode 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 paralelizável é 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 está sendo dobrada), portanto, essa é uma propriedade bidirecional.

Digamos que você esteja pesquisando em um cluster de servidores e um deles não possa responder naquele momento. O que mapReduce fará é que, uma vez que não foi possível acessar esse nó da árvore para o Mapa maior, ele será reagendado para mais tarde e executará o Mapa ou o Reduzir. 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 eu uso para investigar uma decisão de usar (ou não usar) o MapReduce.

• É importante alcançar um desempenho razoável de execução paralela com o mínimo esforço do programador para um determinado problema?
• Eu tenho um grande número (centenas) de elementos de execução paralelos disponíveis?
• Existe excelente largura de banda / taxa de transferência de comunicação entre os elementos de execução paralelos?
• Preciso processar uma enorme quantidade (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 Map.

na verdade, é um padrão genérico de "dividir e conquistar", para que as soluções para distribuição do cálculo possam ser escritas genericamente.

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

o padrão é útil porque, uma vez que você obtém um mapa genérico / reduz o funcionamento da implementação, pode resolver qualquer problema usando a mesma camada de software, basta expressar seu problema em termos dele.