Bons exemplos de MapReduce [fechados]

O Map reduce é um quadro que foi desenvolvido para processar quantidades maciças de dados de forma eficiente. Por exemplo, se temos 1 milhão de registros em um dataset, e ele é armazenado em uma representação relacional - é muito caro para derivar valores e realizar qualquer tipo de transformações sobre estes. Por exemplo, em SQL, dada a data de nascimento, descobrir quantas pessoas têm mais de 30 anos por um milhão de registros levaria um tempo, e isso só aumentaria por ordem de grandeza. quando a complexidade da consulta aumenta. Map Reduce fornece uma implementação baseada em clusters onde os dados são processados de forma distribuída Aqui está um artigo da wikipedia explicando o que map-reduce é tudo sobre Outro bom exemplo é encontrar amigos via Map reduce pode ser um poderoso exemplo para entender o conceito, e uma mala de uso bem usada. Pessoalmente, achei esta ligação muito útil para compreender o conceito

Http://stevekrenzel.com/finding-friends-with-mapreduce

copiar a explicação fornecida no blog (no caso de a ligação ficar obsoleta)

Encontrar Amigos MapReduce é um framework originalmente desenvolvido no Google que permite para fácil computação distribuída em grande escala através de uma série de domínios. O Apache Hadoop é uma implementação de código aberto. Vou encobrir os detalhes, mas resume-se a ... definir dois funções: uma função de mapa e uma função de redução. A função do mapa toma um valor e Saídas chave: pares de valores. Por exemplo, se definirmos uma função de mapa que pega uma cadeia de caracteres e retorna o comprimento da palavra como a chave e a própria palavra como o valor então mapa (steve) iria retorno 5: steve e map (savannah) retornariam 8:savannah. Pode ter notei que a função de mapa é apátrida e só requer a entrada valor para calcular o seu valor de saída. Isto permite-nos correr mapa função contra valores em paralelo e fornece uma enorme vantagem. Antes de chegarmos à função de redução, os grupos de framework mapreduce todos os valores juntos por chave, de modo que se as funções do mapa saída o seguinte chave: pares de valores:

3 : the
3 : and
3 : you
4 : then
4 : what
4 : when
5 : steve
5 : where
8 : savannah
8 : research

Eles são agrupados como:

3 : [the, and, you]
4 : [then, what, when]
5 : [steve, where]
8 : [savannah, research]

Cada uma destas linhas seria então passada como um argumento para a redução função, que aceita uma chave e uma lista de valores. Neste caso, podemos estar a tentar descobrir como muitas palavras de certos comprimentos existe, então a nossa função de redução irá apenas contar o número de itens em a lista e o resultado da chave com o tamanho da lista, como:

3 : 3
4 : 3
5 : 2
8 : 2

As reduções também podem ser feitas em paralelo, mais uma vez proporcionando uma enorme vantagem. Podemos então olhar para estes resultados finais e ver que aí eram apenas duas palavras de comprimento 5 em nosso corpus, etc...

O exemplo mais comum de mapreduce é para contar o número de vezes as palavras ocorrem em corpus. Suponha que você tinha uma cópia da internet (Eu tenho tido a sorte de ter trabalhado em tal situação), e você queria uma lista de cada palavra na internet, bem como quantos vezes que ocorreu.

A forma como te aproximarias disto seria para mostrar os documentos que tens. tem (divide-o em palavras), e passa cada palavra a um mapeador. Mapa seria então cuspir a palavra de volta junto com um valor de 1. O a fase de agrupamento irá levar todas as chaves (neste caso palavras), e fazer um lista de 1's. a fase de redução, em seguida, toma uma chave (a palavra) e uma lista (uma lista de 1's para cada vez que a chave apareceu na internet), e resume a lista. O redutor então emite a palavra, junto com ela é contar. Quando tudo estiver dito e feito você terá uma lista de cada palavra sobre a internet, juntamente com quantas vezes apareceu. Fácil, não é? Se você já leu sobre mapreduce, o cenário acima não é nada de novo... é o "Olá, Mundo" de mapreduce. Então aqui está um caso de uso no mundo real (Facebook pode ou não fazer o a seguir, é apenas um exemplo): O Facebook tem uma lista de amigos (note que os amigos são bidirecionais) coisa no Facebook. Se eu sou seu amigo, você é meu). Eles também têm muito espaço em disco e servem centenas de milhões de Pedidos diario. Eles decidiram pré-calcular os cálculos quando podem. reduzir o tempo de processamento dos pedidos. Um pedido de tratamento comum é o" tu e o Joe têm 230 amigos em comum". Quando visite o perfil de alguém, você vê uma lista de amigos que você tem em comum. Esta lista não muda com frequência, por isso seria um desperdício recalculá-lo sempre que visitou o perfil (de certeza que pode usar uma estratégia de cache decente, mas não seria capaz de continuar. escrevendo sobre mapreduce para este problema). Nós vamos usar mapreduce para que possamos calcular OS amigos comuns de todos uma vez dia e loja resultante. Mais tarde, É só uma consulta rápida. Nós ... tem muito disco, é barato.

Suponha que os amigos são armazenados como pessoa-> [lista de amigos], os nossos a lista de amigos é então:

A -> B C D
B -> A C D E
C -> A B D E
D -> A B C E
E -> B C D

Cada linha será um argumento para um cartógrafo. Para cada amigo na lista de amigos, o mapper irá emitir um par de valores-chave. A chave irá sê amigo, juntamente com a pessoa. O valor será a lista de amigo. A chave será ordenada para que os amigos estejam em ordem, fazendo com que todos os pares de amigos vão para o mesmo redutor. Isto é difícil. para explicar com texto, então vamos apenas fazê - lo e ver se você pode ver o padrao. Depois de todos os carteiros terem acabado de correr, terás uma lista. assim:

For map(A -> B C D) :

(A B) -> B C D
(A C) -> B C D
(A D) -> B C D

For map(B -> A C D E) : (Note that A comes before B in the key)

(A B) -> A C D E
(B C) -> A C D E
(B D) -> A C D E
(B E) -> A C D E
For map(C -> A B D E) :

(A C) -> A B D E
(B C) -> A B D E
(C D) -> A B D E
(C E) -> A B D E
For map(D -> A B C E) :

(A D) -> A B C E
(B D) -> A B C E
(C D) -> A B C E
(D E) -> A B C E
And finally for map(E -> B C D):

(B E) -> B C D
(C E) -> B C D
(D E) -> B C D
Before we send these key-value pairs to the reducers, we group them by their keys and get:

(A B) -> (A C D E) (B C D)
(A C) -> (A B D E) (B C D)
(A D) -> (A B C E) (B C D)
(B C) -> (A B D E) (A C D E)
(B D) -> (A B C E) (A C D E)
(B E) -> (A C D E) (B C D)
(C D) -> (A B C E) (A B D E)
(C E) -> (A B D E) (B C D)
(D E) -> (A B C E) (B C D)

Cada linha será passada como argumento para redutor. A redução a função irá simplesmente Intersectar as listas de valores e saída da mesma forma chave com o resultado da intersecção. Por exemplo, reduzir (a B) - > (A C D E) (B C D)) produzirá (a b) : C D) e significa que os amigos A e B tem C E D como amigos comuns.

O resultado após a redução é:

(A B) -> (C D)
(A C) -> (B D)
(A D) -> (B C)
(B C) -> (A D E)
(B D) -> (A C E)
(B E) -> (C D)
(C D) -> (A B E)
(C E) -> (B D)
(D E) -> (B C)

Agora, quando o D visitar o perfil do B, podemos rapidamente olhar para cima e ver que têm três amigos em comum.