MapReduce
Conceitos e Aplicações
Tiago Pedroso da Cruz de Andrade
Introdução
Introdução
• Com a evolução dos sistemas de informação e o aumento da
quantidade de serviços disponibilizados a seus usuários, cresce
também o volume de dados que precisam ser processados
pelos sistemas computacionais.
• Para que a computação dessa quantidade de informação seja
realizada em tempo viável, cada vez mais faz-se necessária a
exploração de paradigmas de programação paralela e processamento distribuído.
Introdução
• Porém, desenvolver software para ambientes distribuídos é
uma tarefa complexa, pois envolve uma série de conceitos e
problemas que devem ser considerados pelos programadores.
• A fim de facilitar este processo, foi desenvolvido o MapReduce,
um modelo de programação paralela para processamento
largamente distribuído de grandes volumes de dados.
Conceitos
Conceitos
• O paradigma de programação MapReduce inspira-se nas
primitivas Map e Reduce presentes em diversas linguagens
funcionais.
• Essa abordagem foi adotada pois verificou-se que, em muitos
casos, era necessário mapear fragmentos dos dados de entrada
a uma chave identificadora, e então processar todos os fragmentos que compartilhassem a mesma chave.
• Demonstrou ser adequado para trabalhar com problemas que
podem ser divididos ou fragmentados em subproblemas.
Conceitos
• É executado em cima de um cluster computacional de máquinas, que podem ser de prateleira ou não.
• Se a quantidade de dados for grande, pode ser dividido para a
execução de diversas funções Map ao mesmo tempo, em
paralelo.
• Podemos aplicar separadamente as funções Map e Reduce a
um conjunto de dados.
Conceitos
• Todo o trabalho de distribuição do sistema – incluindo
problemas de comunicação, tolerância a falhas, concorrência,
etc. – é abstraído, e fica a cargo do próprio framework.
• A tarefa principal do programador é implementar estas duas
funções, indicando como o mapeamento e a redução dos dados
serão compostos.
• O modelo MapReduce pode ser executado sobre uma variedade
de plataformas e ambientes distintos. Logo, a melhor
implementação do framework depende do ambiente alvo.
Conceitos
Modelo de Programação
Modelo de Programação
• A base de uma aplicação MapReduce consiste em dividir e
processar conjuntos de dados com o uso das funções Map e
Reduce.
• A função Map recebe uma tupla <chave,valor> como
entrada e gera um conjunto intermediário de dados, também
no formato <chave,valor>.
• A função Reduce também recebe como entrada uma tupla
<chave,valor>. Ela é executada para cada chave intermediária, com todos os conjuntos de valores intermediários
associados àquela chave combinados.
Modelo de Programação
• O processamento é dividido em três etapas:
– Uma etapa inicial de mapeamento, onde são executadas
diversas tarefas de mapeamento.
– Uma etapa intermediária, onde os dados são recolhidos das
tarefas de mapeamento, agrupados e disponibilizados para
as tarefas de redução.
– Uma etapa de redução onde são executadas diversas tarefas
de redução, agrupando os valores comuns e gerando a saída
da aplicação.
Modelo de Programação
Modelo de Programação
• Exemplo de aplicação:
– Considere o problema de contar o número de ocorrências de
uma palavra em uma grande coleção de documentos.
– A seguir será mostrado o pseudocódigo das funções Map e
Reduce.
Modelo de Programação
map(String key, String value):
// key: nome do documento
// value: conteúdo do documento
for each word w in value:
emitIntermediate(w, “1”);
Modelo de Programação
reduce(String key, Iterator value):
// key: uma palavra
// value: uma lista de contadores
int result = 0;
for each v in value:
result += parseInt(v);
emit(key, asString(result));
Modelo de Programação
• No pseudocódigo:
– Cada chamada da função Map recebe como entrada o
conteúdo de um dos documentos da coleção.
– Para cada palavra do documento de entrada, a função Map
emite o valor “1” associado à chave que representa a palavra
em questão.
– Cada chamada da função Reduce recebe como entrada uma
palavra e um iterador para todos os valores emitidos pela
função Map, associados com a palavra em questão.
– Todos os valores são então somados em uma tupla contendo
a palavra e seu total de ocorrências.
Arquitetura
Arquitetura
• O MapReduce é realizado em um cluster computacional
constituído por basicamente dois tipos de nós: Mestre e
Escravo.
• O nó Mestre tem como função atender requisições de execução
efetuadas pelos usuários e gerenciá-las, criando várias tarefas e
delegando-as aos nós Escravos.
• Os nós Escravos, por sua vez, são encarregados de executar de
fato essas tarefas, aplicando de acordo com seu tipo as função
Map ou Reduce definidas pelo usuário.
• Também é usado um sistema de arquivos distribuído.
Etapas do Processo
Etapas do Processo
• O primeiro passo do MapReduce é dividir os dados em partes e
iniciar uma série de cópias do programa nas máquinas do
cluster computacional.
Etapas do Processo
• Uma destas cópias é o Mestre e as outras são todas Escravos.
Etapas do Processo
• O trabalho consiste em realizar X tarefas de mapeamento e Y
tarefas de redução, sendo o Mestre responsável por atribuir aos
Escravos essas tarefas.
Etapas do Processo
• O Escravo para o qual foi atribuída uma tarefa de mapeamento
deve ler o conteúdo de uma parte do arquivo, separar todas as
tuplas e enviar para a função de mapeamento. As tuplas
produzidas pela função de mapeamento são armazenadas em
memória.
Etapas do Processo
• Periodicamente, as tuplas armazenadas em memória são
escritas em disco. Para isso é usado o sistema de arquivos
distribuído.
Etapas do Processo
• Os Escravos para os quais foram atribuídas tarefas de redução
devem pegar todos os valores de uma determinada chave, que
foi produzido pelas tarefas de mapeamento, e enviar para a
função de redução.
Etapas do Processo
• Quando todas as tarefas de mapeamento e redução forem
concluídas, o Mestre acorda o programa do usuário e retorna o
controle para ele.
Tolerância a Falhas
Tolerância a Falhas
• Escravos:
– O Mestre detecta falhas através de pings periódicos.
– As tarefas de mapeamento são reexecutadas – tanto as em
progresso quanto as concluídas.
– As tarefas de redução em progresso são reexecutadas.
Tolerância a Falhas
• Mestre:
–
–
–
–
Possui um único Mestre e sua falha é indesejável.
Necessita de um controle mais complexo.
Executa checkpoints periódicos.
Uma nova instância pode ser criada a partir dos checkpoints.
Conclusão
Conclusão
• Fácil de usar, mesmo por programadores sem experiência em
processamento distribuído.
• Permite o programador focar no problema e esquecer os
detalhes.
• Uma grande variedade de problemas podem ser expressos em
MapReduce.
• Simplificou computações em larga escala de grandes volumes
de dados.
Referências
Referências
1. “MapReduce: Simplified data processing on large clusters”
2. “The Google File System”
3. “Evaluating MapReduce for multi-core and multiprocessor
systems”
4. “A dynamic
workloads”
MapReduce
scheduler
for
heterogeneous
in
heterogeneous
5. “Hadoop: The Definitive Guide”
6. “Improving MapReduce
environments”
performance