MapReduce e Processamento Paralelo de Dados

MapReduce e seus sucessores são modelos e frameworks de programação que processam grandes conjuntos de dados em paralelo através de clusters de máquinas comerciais, gerenciando automaticamente a distribuição, o agendamento e a tolerância a falhas.

Definition

MapReduce é um modelo de programação no qual uma computação é expressa como uma função de mapeamento (map) que emite pares chave-valor e uma função de redução (reduce) que agrega os valores para cada chave, executada em paralelo sobre dados particionados em um cluster com distribuição e tolerância a falhas gerenciadas pelo framework.

Scope

Este tópico aborda o modelo MapReduce — expressando a computação como funções de mapeamento (map) e redução (reduce) sobre pares chave-valor, com uma etapa automática de embaralhamento (shuffle) entre elas — e a maquinaria de execução circundante de particionamento, agendamento e tolerância a falhas via reexecução. Abrange a evolução para motores de fluxo de dados gerais e em memória (como o modelo de conjunto de dados distribuídos resilientes) e os sistemas de arquivos distribuídos que os sustentam. Exclui os modelos de armazenamento NoSQL e a teoria de consistência, que são tópicos adjacentes.

Core questions

• Como as fases de mapeamento (map), embaralhamento (shuffle) e redução (reduce) paralelizam uma computação?
• Como o framework lida com o particionamento de dados, o agendamento e os atrasos (stragglers)?
• Como a tolerância a falhas é alcançada através da reexecução de tarefas falhas?
• Por que os motores de fluxo de dados gerais e em memória sucederam o MapReduce para muitas cargas de trabalho?
• Que papel os sistemas de arquivos distribuídos desempenham no processamento paralelo de dados?

Key concepts

• funções de mapeamento (map) e redução (reduce)
• fase de embaralhamento (shuffle) e ordenação (sort)
• particionamento de dados
• agendamento de tarefas e atrasos (stragglers)
• tolerância a falhas por reexecução
• sistema de arquivos distribuído
• grafos de fluxo de dados
• conjuntos de dados distribuídos resilientes

Key theories

O modelo MapReduce

Programadores escrevem uma função de mapeamento (map) que transforma registros de entrada em pares chave-valor intermediários e uma função de redução (reduce) que combina todos os valores para uma chave; o framework lida com a execução paralela, o embaralhamento (shuffle) que agrupa valores por chave e a recuperação de falhas.

Tolerância a falhas por reexecução

Como as tarefas são funções determinísticas sobre entrada particionada, o framework tolera falhas de máquina simplesmente reexecutando tarefas de mapeamento (map) ou redução (reduce) falhas, e mitiga nós lentos lançando cópias de backup (especulativas) de tarefas atrasadas (straggling tasks).

Motores de fluxo de dados em memória

Sistemas posteriores generalizaram o MapReduce para grafos de fluxo de dados arbitrários e mantiveram dados intermediários em memória; a abstração de conjunto de dados distribuídos resilientes recupera partições perdidas recomputando-as a partir da linhagem, acelerando grandemente cargas de trabalho iterativas e interativas.

Clinical relevance

O processamento paralelo de dados tornou a computação em escala de cluster acessível a programadores comuns: MapReduce e seus sucessores processam logs, constroem índices de busca, treinam modelos e executam análises sobre petabytes, sendo ferramentas fundamentais da engenharia de dados e da ciência de dados em larga escala.

History

O Google introduziu o MapReduce (2004) sobre o Google File System (2003) para indexar a web em clusters de máquinas comerciais, e o Hadoop de código aberto reimplementou ambos, popularizando o modelo. No início dos anos 2010, motores de fluxo de dados em memória construídos sobre a abstração de conjunto de dados distribuídos resilientes (2012) substituíram o MapReduce para análises iterativas e interativas, mantendo suas ideias de tolerância a falhas.

Key figures

• Jeffrey Dean
• Sanjay Ghemawat
• Matei Zaharia

Seminal works

• dean2008
• ghemawat2003
• zaharia2012

Frequently asked questions

Por que o MapReduce foi tão influente apesar de sua simplicidade?

Seu poder estava no que ele ocultava. Ao restringir a computação a funções de mapeamento (map) e redução (reduce), o framework podia particionar dados automaticamente, agendar trabalho em milhares de máquinas, recuperar-se de falhas reexecutando tarefas e balancear a carga — permitindo que programadores processassem enormes conjuntos de dados sem escrever código de sistemas distribuídos.

Por que motores mais recentes substituíram o MapReduce para muitas tarefas?

O MapReduce clássico escreve resultados intermediários em disco entre cada estágio, o que é lento para trabalhos multi-etapas e iterativos, como aprendizado de máquina. Motores de fluxo de dados em memória mantêm os dados em memória entre os estágios e expressam grafos de computação mais ricos, oferecendo grandes ganhos de velocidade enquanto retêm a tolerância a falhas baseada em linhagem, tornando-se preferidos para muitas cargas de trabalho analíticas.