Conceitos
MapReduce: execução em lote tolerante a falhas
Intuição
Imagine contar as palavras de milhares de livros dividindo os livros entre muitas pessoas, cada uma anotando suas contagens, e depois juntando as anotações por palavra. Com tanta gente trabalhando, alguém vai ficar doente ou ficar muito lento no meio do trabalho. Em vez de tentar impedir isso, o coordenador simplesmente entrega de novo o pedaço de quem sumiu para outra pessoa e, perto do fim, dá uma cópia do pedaço de quem está atrasado a mais alguém, valendo quem terminar primeiro; o resultado final sai igual.
Como funciona
O programador escreve só duas funções: map, que transforma um par chave/valor de entrada em pares chave/valor intermediários, e reduce, que combina todos os valores de uma mesma chave intermediária. A biblioteca divide a entrada em M splits (tipicamente 16 a 64 MB) e um master atribui tarefas de map e de reduce a workers ociosos, preferindo máquinas que já guardam uma réplica do bloco no GFS para economizar rede. Os workers de map gravam os dados intermediários no disco local, particionados em R regiões (por padrão hash(chave) mod R), e os workers de reduce os leem remotamente e ordenam por chave. O master checa os workers periodicamente; se um não responde, é marcado como falho. Tarefas de map concluídas por ele são reexecutadas, porque a saída estava no disco local agora inacessível, e as de reduce concluídas não, porque a saída já está no sistema de arquivos global. Os commits são atômicos: cada tarefa escreve em arquivo temporário e o reduce o renomeia atomicamente para o final, então, com map e reduce determinísticos, o resultado é igual ao de uma execução sequencial sem falhas. Para stragglers, perto do fim o master lança execuções de backup das tarefas restantes e vale a primeira a terminar. O master é único, e a implementação descrita aborta a computação se ele falhar, cabendo ao cliente tentar de novo.
Na prática
O paper relata um sort de cerca de 1 TB em 891 segundos, que levou 933 segundos (cerca de 5% a mais) com 200 workers mortos de propósito, e um caso em que manutenção de rede derrubou grupos de 80 máquinas e o job terminou mesmo assim; sem as tarefas de backup, o sort levou 44% mais tempo. Escolha esse modelo para processamento em lote de grandes volumes de dados (índices invertidos, contagens, grep e ordenação distribuídos, grafos) em clusters de máquinas comuns onde falhas são rotina, com entrada e saída num sistema de arquivos replicado como o GFS. Ele funciona melhor quando map e reduce são determinísticos e re-executáveis, e não serve para cargas interativas de baixa latência.
Use em um desenho
Pratique na escola de System Design os casos que dependem deste conceito.