MapReduce: Simplified Data Processing on Large

ClustersAutores: Jeffrey Dean e Sanjay Ghemawat

(Engenheiros do Google)

Palestrante: Augusto Souza

Agenda

1. Introdução2. Modelo de Programação3. Implementação4. Extensões5. Desempenho6. Experiência7. Conclusões8. Referências9. Perguntas

Introdução

● MapReduce é um modelo de programação e uma abstração para processamento e geração de grandes conjuntos de dados

● Modelo de programação: programador implementa funções Map e Reduce

● Programas que seguem este modelo são automaticamente paralelizados e executados em um cluster de "commodity machines"

Introdução

● Os autores notaram que diversos de seus trabalhos exigiam uma computação relativamente simples porém sobre uma grande quantidade de dados

● Trabalhar com um cluster não era simples por questões como:○ Como paralelizar a computação?○ Como distribuir os dados?○ Como tratar falhas?○ Como balancear a carga?

Introdução

● Foi a abstração criada para expressar a computação simples, escondendo os detalhes de sistemas distribuídos

● Baseado nas diretivas Map e Reduce do Lisp (e outras linguagens funcionais)

● Essa abordagem funcional permite paralelização e tolerância a falhas por re-execução

Modelo de Programação

● Usuário especifica a computação em termos de duas funções:○ Map: recebe um par "key/value" como entrada e

produz um conjunto intermédiário de dados que são combinados pela biblioteca de MapReduce de acordo com a sua chave

○ Reduce: recebe uma chave e uma lista (iterator) de valores para aquela chave, então executa uma computação em cima dessa lista produzindo um conjunto menor de valores

Modelo de Programação

● Exemplo:

Modelo de Programação

Fonte: http://www.rabidgremlin.com/data20/MapReduceWordCountOverview1.png

Modelo de Programação

● Tipos:

● Outros exemplos:○ Contagem de frequencia de acessos a URLs○ Grafo de links reversos da web○ Grep distribuído○ Term-Vector de um Host○ Indíce inverso○ Ordenação

Implementação

● Desde a publicação do artigo surgiram algumas versões open source:○ Hadoop: conjunto de projetos (principais são

MapReduce e HDFS) mantido pela Apache, foco em clusters

○ Phoenix: versão de MapReduce criada em Stanford para chips multi-core e multi-processadores de memória compartilhada

Implementação● Execução:

Implementação

● Estrutura de dados do Master:○ Estado (idle, in-progress ou completed)○ ID do worker (para tarefas que não estão idle)○ Localização e tamanho dos arquivos intermediários

das tarefas de map que finalizaram.● Tolerância a falhas:

○ Falhas do worker: controle por ping e recuperação por re-execução

○ Falha do master: no artigo de 2004 os autores comentam que não se preocupam em tratar esta falha, pois ela é estatisticamente improvável, mas seria tratável com checkpoints periódicos.

● Localidade, Granularidade e Backup Tasks

Extensões

● Usuário pode especificar a função de particionamento para determinar o mapeamento de valores intermediários para as R tarefas de Reduce

● Ordenação garantida dos pares key/value intermediários por ordem crescente de chave

● Usuário pode especificar a função de combinação que roda após o Map agrupando os valores que possuem a mesma chave, o objetivo é reduzir a quantidade de dados intermediários

Extensões

● Tipos customizáveis para I/O, assim pode-se ler diferentes formatos de entrada e produzir diferentes formatos de saída

● Execução em uma única máquina para facilitar debugging e testes em pequena escala

Desempenho

● Aplicação Grep

Desempenho● Aplicação Sort

Experiência● Aceitação no Google no paper de 2004:

Experiência● Aceitação no Google no paper de 2008:

Experiência

Conclusões

● MapReduce tem sido bastante utilizado pelo Google para diferentes propósitos

● É um modelo de programação fácil de ser utilizado por programadores sem experiência com sistemas distribuídos

● Grande quantidade de problemas podem ser expressos em termos de funções de Map e Reduce (geração de dados para o search, ordenação, data mining, machine learning)

● Escalável para clusters com milhares de máquinas● Foram feitas otimizações para reduzir a quantidade de

dados trafegados● Execução redundante pode ser utilizada para reduzir o

impacto de máquinas lentas e para tratar falhas

Referências

1. Artigo "MapReduce: Simplified Data Processing on Large Clusters" (versões de 2004 e 2007): http://research.google.com/archive/mapreduce.html

2. Site do projeto Hadoop: http://hadoop.apache.org/

3. Site do projeto Phoenix: http://mapreduce.stanford.edu/

4. Site do projeto JSMapReduce: http://jsmapreduce.com/

Perguntas?