Processamento de Dados Massivos/O modelo de programação MapReduce

O modelo MapReduce

Conforme discutido anteriormente, um dos aspectos essenciais do processamento de dados massivos é exprimir o processamento de forma que o maior volume possível de dados seja acessado (lido) e processado em paralelo, aumentando a velocidade final do processamento. Um modelo que se mostrou particularmente bem sucedido nesse aspecto foi o MapReduce, proposto pela Google em 2004 .

Princípio geral

O modelo opera sobre o Google File System, de onde os dados podem ser lidos de forma eficiente, em paralelo. Os arquivos são vistos como listas de registros simples, como linhas, ou registros formatados segundo algum padrão definido pelo usuário. Cada registro lido do arquivo é representado por um par (chave,valor) (p.ex., o número de cada linha e o texto nela encontrado).

O processamento a ser realizado deve ser então descrito por duas funções simples que dão nome ao modelo e operam sobre chaves e valores:

• map(), que recebe como entrada pares chave/valor e os processa, gerando como saída novos pares chave/valor, potencialmente de tipos diferentes dos anteriores,
• reduce(), que recebe como entrada chaves produzidas como saída da função anterior, junto com uma lista de todos os valores associados a cada chave, e produz novamente como saída outro(s) par(es) chave/valor.

Conceitualmente, o modelo se reduz a uma versão particular do divisão-e-conquista já discutido anteriormente. Em particular, cada registro (par chave/valor) extraído do arquivo de entrada pode ser potencialmente processado em paralelo, de forma independente de todos os demais. A sincronização durante o processamento ocorre ao final da fase do map, quando todos os pares com chaves iguais devem ser agrupados para serem processados juntos na fase de redução. Novamente há potencialmente oportunidade para um alto grau de paralelismo, já que cada chave (com sua lista de valores) pode ser processada separadamente.

Exemplo de aplicação

Com base na descrição resumida das primitivas na seção anterior, podemos ilustrar melhor o modelo com uma aplicação simples, ContaPalavras, que visa contar todas as ocorrências de cada palavra encontrada em uma base de dados textual. O arquivo original seria, então, o texto base, de onde o sistema é capaz de identificar e ler as linhas a partir dos blocos do arquivo. Nesse caso, o MapReduce gera pares do tipo (posição,linha), com a posição no arquivo (em bytes) onde cada linha se inicia como chave e o texto de cada linha nele encontrada como valor.

A função de mapeamento, nesse caso, deve então quebrar a linha em palavras e emitir um valor unitário para cada palavra (como que contando aquela ocorrência):

    map(key, value):
    // key: posição da linha; value: texto da mesma
         for each word w in value:
            emit(w, 1) // O valor e' definido com 1 sempre

No modelo original do MapReduce, emit() é a função usada para produzir novos pares chave/valor de saída, que seriam então armazenados em um novo arquivo, novamente sobre o Google File System.

A função de redução então receberia uma lista de uns para cada palavra encontrada no texto e bastaria então contar (somar) todos os valores recebidos:

    reduce(key, values):
    // key: uma palavra; value: iterador para a lista
        result = 0
        for each count v in values:
           result += v
        emit(key, result) // contagem de cada palavra

O resultado final, então, serão pares de palavras e inteiros indicando o número de vezes que cada palavra foi encontrada.

Aspectos de execução

Apesar de sua relativa simplicidade, a grande aceitação do modelo se deveu em parte à facilidade com que questões como o aproveitamento de paralelismo em diversos níveis (p.ex., máquinas multicore em um cluster), balanceamento de carga e tolerância a falha são facilmente tratados.

Para melhor aproveitar o poder computacional de cada nó de processamento, o modelo permite ainda a definição de uma função combine(), que serve para realizar o pré-processamento das listas de valores gerados por cada nó que executa a função map(), quando esse processamento pode reduzir o volume de comunicação entre nós. Essa função pode ser usada para já gerar um valor agregado para todos os valores associados por cada chave em um nó, de forma que apenas um valor precise ser enviado para os nós redutores para cada chave. No caso do programa ContaPalavras, o mesmo código da função reduce() poderia ser usado: todas as ocorrências de uma dada palavra em um nó seriam combinadas e ao invés de enviar uma lista de uns para o redutor, cada nó já enviaria o resultado da contagem (soma) da lista local para o redutor, que continuaria somando os valores recebidos dos vários nós de map() para obter a contagem final.

O balanceamento de carga e a tolerância a falhas são obtidos por um mesmo mecanismo: o sistema acompanha o término das tarefas no sistema e quando começa a ter recursos desocupados re-edita tarefas que ainda não foram completadas, aproveitando o primeiro resultado que se torne disponível.