{lang: 'pt-BR'}

Introdução

MapReduce é um modelo de programação proposto pelo Google para para facilitar o processamento de grandes volumes de dados (Big Data). A partir de um paradigma inspirado em primitivas de programação funcional, foi criado um framework que permitisse a manipulação de grande volume de dados de forma paralela e distribuída, além de prover tolerância a falha, escalonamento de I/O e monitoramento. Um grande número de aplicações reais podem ser expressas nesse modelo de programação.

O modelo de programação MapReduce consiste na construção de um programa formado por duas operações basicas: map e reduce. A operação de map recebe um par chave/valor e gera um conjunto intermediário de dados, também no formato chave/valor. A operação de reduce é executada para cada chave intermediária, com todos os conjuntos de valores intermediários associados àquela chave combinados. Em geral a operação de map é usada para encontrar algo, e a operação de reduce é usada para fazer a sumarização do resultado.

Exemplo

Considere o problema de contar o número de ocorrências de uma palavra em uma grande coleção de documentos. Veja o pseudo-código para este problema usando MapReduce:

map(String input_key, String input_value):
    // input_key: document name
    // input_value: document contents
    for each word w in input_value:
        EmitIntermediate(w, "1");

reduce(String output_key, Iterator intermediate_values):
    // output_key: a word
    // output_values: a list of counts
    int result = 0;
    for each v in intermediate_values:
        result += ParseInt(v);
    Emit(AsString(result));

Para cara palavra do documento de entrada, a função map emite o valor ’1′ associado à chave que representa a palavra em questão. A função de reduce soma todas as contagens emitidas para uma mesma chave, ou seja, uma mesma palavra.

Execução

Execução paralela

A operação de map é distribuída em múltiplas máquinas a partir do particionamento dos dados em pedaços que podem ser processasdos em paralelo por diferente máquinas. A operação de reduce é distribuída através do particionamento das chaves intermediárias. O tamanho e a função de particionamento são parâmetros fornecidos pelo usuário.

Passo-a-passo de execução

  1. A biblioteca MapReduce, no programa do usuário, primeiro divide os dados de entrada em M pedaços. Em seguida inicia várias cópias do programa em um cluster de computadores.
  2. Uma das cópias do programa é especial – o master. As outras cópias são denominadas workers e recebem trabalho do master. Existem M tarefas de Map e R tarefas de reduce para serem assinaladas. O master seleciona workers ociosos e assinala a eles uma tarefa de map ou de reduce.
  3. Um worker que possui uma tarefa de map le o conteúdo correspondente ao pedaço da entrada. Ele interpreta os pares chave/valor a partir dos dados de entrada e passa como parâmetro para a função de map do usuário. Os pares chave/valor intermediários produzidos pela função de map são armazenados em memória.
  4. Periodicamente os pares de dados dos buffers são escritos em disco, particionados em R regiões pela função de particionamento. A localização desses pares de dados no disco é informada ao master, que irá repassar essa localização para os workers com tarefas de reduce.
  5. Quando um worker de reduce é notificado da localização dos dados pelo master, este usa uma chamada de procedimento remota para buscar os dados do disco local dos workers de map. Quando os dados já foram lidos, ele ordena os dados pelas chaves intermediárias, para que todas as ocorrências de uma mesma chave seja agrupada junto. A operação de ordenação é necessária, pois muitas chaves diferentes são mapeadas para a mesma tarefa de reduce. Se a quantidade de dados intermediários é muito grande para caber em memória, uma ordenação externa é usada.
  6. O worker de reduce percorrer os dados intermediários já ordenados e para cada chave encontrada, ele passa a chave os valores intermediários para a função de reduce definida pelo usuário. A saída de cada função de reduce é adicionada ao final de um arquivo de saída para aquela partição de reduce.
  7. Quando todas as tarefas de map e reduce foram terminadas, o master retorna o programa do usuário.

Ao final da execução do programa, o resultado está disponível em R arquivos (um para cada operação de reduce). É comum que os arquivos de resultados de uma operação de MapReduce sejam entradas para outra chamada de MapReduce.

Tolerância a falhas

Uma vez que o framework de MapReduce foi criado para ajudar o processamento de uma quantidade enorme de dados em um cluster com inúmeras máquinas, lidar com falhas é algo essencial. O processo master envia um ping periodicamente para cada worker. Se o master não receber uma resposta de um worker em um certo período de tempo, o master assume que aquela máquina falhou. Todas as tarefas de map completadas pelo worker são resetadas para seu estado inicial e são re-escalonadas para outro worker.  Essas tarefas precisam ser re-executadas em caso de falha, pois seus arquivos de saída são armazenado no disco local da máquina que falhou e, portanto, ficam inacessíveis. O mesmo acontece com as tarefas de map ou reduce que estão em progresso. Tarefas de reduce completadas não precisam ser re-executadas, pois seus arquivos de saída são armazenados no sistema de arquivo global.

No caso do processo master falhar, é necessário um controle mais complexo, pois o processo master é o elo entre a execução das tarefas de map e reduce. O processo master deve executar checkpoints periódicos de suas estruturas de dados. Em caso de falha, uma nova instância pode ser levantada, recuperando a partir do último estado que foi salvo. O MapReduce assume que só existirá um único processo master (Single Master), portanto, falhas neste processo são indesejáveis.

Ao final da execução do programa, algumas máquinas, apesar de ainda responderem, podem apresentar um tempo de resposta muito inferior a média das outras máquinas. Por exemplo, falhas nos discos podem reduzir a taxa de leitura de 30MB/s para 1MB/s. Para evitar que estes processo atrasem a execução do programa, quando o programa está perto de terminar, algumas cópias das tarefas restantes são iniciadas (tarefas backup). A tarefa será marcada como completada assim que, ou a tarefa primária ou uma tarefa de backup, responder. A título de exemplo, um programa de ordenação, pode demorar até 44% mais tempo se o mecanismo de tarefas de backup estiver desligado.

Localidade

A largura de banda é um recurso relativamente escasso neste ambiente de computação. A quantidade de comunicação é reduzida pelo fato de que os dados de entrada (gerenciados pelo sistema de arquivos global – GFS) está armazenado no disco local das máquinas que fazem parte do cluster. O GFS implementeado pelo Google divide cada arquivo em blocos de 64MB e armazena algumas cópias destes blocos em máquinas diferentes (tipicamente 3). O processo master do MapReduce leva em conta a localização dos dados na hora de escalonar as tarefas de map em uma máquina que contém uma das répicas dos dados de entrada.

Para saber mais, você pode acessar a página mantida pelo Google com informações sobre o MapReduce

Acesse também o projeto Hadoop, uma implementação open source de MapReduce em Java, mantida pelo grupo Apache.

{lang: 'pt-BR'}