MapReduce – Python (Parte 2)

Em nosso último post, o objetivo foi mostrar que um processo MapReduce é composto de 3 fases:

  1. Map -> Para cada “registro” de entrada, aplicamos uma função definida.
  2. Agrupamento e ordenação -> A saída da primeira etapa é reunida em grupos, que são ordenados.
  3. Reduce -> Para cada grupo da etapa 2, aplicamos uma função definida.

Hoje, mostraremos em detalhes como é definida cada etapa e qual a participação de cada uma na resolução de um problema.

Em primeiro lugar, devemos entender que este paradigma surgiu da necessidade de manipularmos uma enorme quantidade de dados, que em grande parte dos casos, não estão estruturados. Uma das implementações mais populares é o Hadoop, que iremos utilizar em nossos exemplos.

A partir disso, iremos trabalhar com uma base de dados sem schema (sem a definição explícita dos campos, relacionamentos, etc). Nossos dados devem sempre ser interpretados como pares de (chave, valor). Sendo assim, detalhando melhor nossas 3 etapas, temos:

Map

  • Entrada: (input_key, value)
  • Saída: (intermediate_key, intermediate_value)
  • Processo: para cada par (input_key, value), gerar (intermediate_key, intermediate_value).

Reduce

  • Entrada: grupos de pares (intermediate_key, intermediate_value) agrupados e ordenados pela chave intermediate_key.
  • Saída: (output_values)
  • Processo: combinar todos os valores para cada chave intermediate_key, gerando (output_values).

Exemplo:

Em uma base são guardadas os dados de curtir de uma determinada rede social entre amigos. A base é a seguinte:

Curtir,Joao,Eric
Curtir,Eric,Joao
Curtir,Eric,Maria
Curtir,Maria,Eric
Curtir,Jose,Eric

Quantas vezes cada usuário foi curtido por um amigo?

Nossa função da etapa Map receberia cada registro e emitiria todos os casos em que usuários foram curtidos:

('Eric', 1)
('Joao', 1)
('Maria', 1)
('Eric', 1)
('Eric', 1)

Os resultados seriam pares (usuário curtido, contagem), que na segunda etapa seriam agrupados pela chave que foi definida como sendo o nome dos usuários curtidos. A etapa Reduce faria a soma das contagens para cada chave:

('Eric', 3)
('Joao', 1)
('Maria', 1)

De maneira visual:

MapReduce2

No próximo post focaremos em passar alguns exemplos com suas respectivas implementações em Python.

Anúncios

Tags:, ,

Trackbacks / Pingbacks

  1. MapReduce – Python (Parte 1) | Eric Couto - 8 de junho de 2013

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: