Existem diversas implementações diferentes para o modelo MapReduce. É na implementação que devem ser resolvidas as questões relativas à paralelização, como a sincronização e a exclusão mútua. Uma boa realização depende também do ambiente onde ela será executada: máquinas muito velozes conectadas por uma rede muito lenta requerem uma implementação diferente de um cluster de máquinas mais lentas conectadas por uma rede muito veloz. Nesse trabalho abordaremos três construções: a da Google [1], o Hadoop [4] e a MOON [7]. Da primeira, falaremos de alguns problemas e soluções encontradas pela equipe Google; da segunda, trataremos do ponto de vista do usuário; em último, a motivação por trás do MOON.
Essa implementação foi feita pensando no ambiente de uso comum da Google: centenas ou milhares de computadores pessoais comuns, (processador dual x86, com 2 a 4 GB de memória) conectados em rede, com equipamentos de uso doméstico e um sistema de arquivos distribuído de discos IDE com alto índice de falhas.
De acordo com o modelo, o usuário implementa as funções map e reduce e a função MapReduce é chamada no programa do usuário. A partir daí, a seguinte sequência acontece:
- Os dados de entrada são fragmentados em fragmentos de 64MB de forma automática ou pelo programa do usuário.
- O programa do usuário é copiado e inicializado em todas as máquinas.
- Uma das máquinas é eleita a máquina mestre e, as outras, trabalhadoras. A mestre escolhe trabalhadoras livres e as envia tarefas.
- Máquinas trabalhadoras que executam tarefas de map guardam em memória os valores intermediários e as escrevem no disco local periodicamente, informando à máquina mestre onde os pares chave/valor intermediários estão.
- Máquinas trabalhadoras que executam tarefas de reduce recebem da máquina mestre autorização para começar as tarefas e também recebem os locais onde estão escritos os valores relacionados àquela redução.
- A máquina trabalhadora de redução que recebeu os parâmetros de entrada escreve seus valores de saída no final do arquivo de saída desssa redução.
- O mestre desbloqueia o programa do usuário.
O sistema tolera falhas fazendo com que o mestre envie e receba notificações das máquinas trabalhadoras. Se alguma destas fica muito tempo sem responder, o mestre para de designar tarefas a ela e designa sua tarefa atual a outra máquina. O mestre também mantém um arquivo sobre o estado da execução geral do MapReduce. Caso o mestre falhe, outra máquina pode ser eleita o mestre e começar a execução de onde o anterior falhou.
Hadoop
O Hadoop[4] é uma plataforma capaz de executar tarefas map e reduce com máquinas que são indicadas pelo usuário.
Para utilizar o Hadoop, o usuário escreve a função map implementando o método homônimo de uma interface Java® de nome Mapper. É possível encontrar um exemplo de código escrito em Java® no tutorial do Hadoop.
Além disso, o usuário precisa indicar para o Hadoop em quais máquinas serão executadas as tarefas, inicializar as máquinas, gerenciar falhas. Assim, a plataforma é voltada para usuários com experiência em programação.
MOON
MOON[7] (MapReduce On Opportunistic eNvironments, MapReduce em Ambientes Oportunistas) é uma plataforma de execução do MapReduce projetada para sistemas distribuídos onde a indisponibilidade de recursos é muito alta. Essa plataforma tem como objetivo facilitar a chamada "computação voluntária", onde pessoas doam ciclos ociosos de suas máquinas pessoais para ajudar projetos científicos.
A MOON utiliza o Hadoop[4] como núcleo e ferramentas de estatística para melhorar suas decisões de designação de tarefas, tolerância a falhas e outros problemas desse tipo de sistema distribuído.