Concrete Logo
Hamburger button

MapReduce – parte III

  • Blog
  • 29 de Novembro de 2012
Share

O caso de contagem de frequência de palavras em um conjunto de documentos, é clássico e não podíamos deixar de citá-lo.

Mas há muitos outros exemplos listados no artigo MapReduce: Simplified Data Processing on Large Clusters. A listagem também foi repetida no capítulo 23-Distributed Programming with MapReduce, do livro Beautiful Code, O’Reilly 2007, escrito pelos mesmos autores do artigo, Jeffrey Dean and Sanjay Ghemawat.

São eles:

    – grep distribuído


      A função map emite uma linha se casar com um padrão fornecido de expressão regular. A função reduce apenas copia o resultado intermediário para a saída.


    – Contagem de frequência de acesso a URL

      
A função map processa logs de requisições às páginas web e emite como saída pares <URL, 1>. A função reduce soma todos os valores correspondentes a mesma URL e emite os pares <URL, total_count>
    – Grafo web-link reverso


      Um forward web-link graph tem um vértice saindo do nó URL1 para o nó URL2 caso a página em URL1 tenha um link para URL2. Um reverse web-link graph é o mesmo grafo com os vértices revertidos.
 A função map fornece pares <target, source> para cada link apontando para uma URL target em um documento source. A função reduce concatena todas as URLs de source, associadas com uma dada URL target e emite pares <target, list(source URLs)>.
    – Term vector per host


      Um term vector lista os termos do documento junto com o número de ocorrências do termo no documento. É uma lista de pares . A função map emite um par <hostname, term vector> para cada documento de input (onde hostname é extraído da URL do documento). A função reduce é passada para todos os term vectors de cada host. Ela adiciona os term vectors desprezando os termos de menor frequência e emitindo o par final <hostname, term vector>.

    – Índice invertido

      Um índice invertido é uma estrutura de dados tal que, para cada palavra lista os documentos que contém a tal palavra (em geral os documentos são identificados por um ID númerico de modo a manter compacto o índice). A função map parseia cada documento e emite uma sequência de pares <word, docid>. A função reduce aceita todos os docids para uma dada palavra, faz sort nos correspondentes documentos IDs e emite o par <word, list of docids>. O conjunto de todos os pares emitidos formam o indice invertido. É fácil incluir no processamento o controle das posições das palavras em cada documento.

    – Sort distribuído

      
Para fazer o sort em cima de uma determinada chave, a função map extrai a chave de cada registro e emite um par <key, record>. A função reduce apenas emite todos os pares.


 
Como diz o livro, há muitos outros exemplos de computações que podem ser expressas facilmente usando MapReduce. Para casos complexos, é geralmente fácil expressar o problema como uma sequência de passos MapReduce ou como uma aplicação iterativa, onde a saída de um é a entrada do próximo passo MapReduce.

Uma vez acostumado a pensar em termos de MapReduce, muitos problemas acabam sendo facilmente resolvidos usando o modelo. Um testemunho sobre isto, é que desde que começaram usar em 2003, até dezembro de 2006, já tinham sido escritos no Google mais de 6000 programas MapReduce distintos, com a participação de mais de mil desenvolvedores, sendo que alguns nunca tinham escrito um programa distribuído ou paralelo.

Segundo o livro Beautiful Code, eram mais de 35.000 jobs MapReduce por dia, processando cerca de 8 petabytes de dados de entrada por dia (em um ritmo sustentado de cerca de 100 gigabytes por segundo).

 

Observações sobre paralelismo com Mapreduce

    – As funções map são executadas em paralelo criando diferentes valores intermediários a partir de diferentes conjuntos de dados de entrada.

    – As funções reduce também rodam em paralelo, cada uma trabalhando em uma output_key diferente.

    – Todos os valores são processados de forma independente

    – Bottleneck: a fase de reduce não pode começar antes da fase map terminar completamente.

 

Como é o framework do Google

    Visão geral da execução

    Na parte I mostramos uma figura fundamental para entender o modelo MapReduce, os combiners e o particioner.

    Agora vamos mostrar uma figura que é praticamente a justificativa da necessidade desta parte III. Nela aparece como o framework de MapReduce do Google faz o processamento:

    MapReduce no Google

     
    Reparem que tudo entra por um Master. Na prática ele não armazena nada além de metadados. Sua função principal é controlar tudo.

    Antes que você o aponte como um ponto único de falha, saíba que no framework do Google existe sempre um shadow do Master pronto para entrar em ação automaticamente. Quando falarmos de Hadoop, cuja implementação é baseada no framework do Google, veremos que nele não é tão automática a solução para a falha do Master (NameNode no linguajar do Hadoop).

    As invocações aos mappers são distribuídas por várias máquinas através de um particionamento automático dos dados de entrada em um conjunto de M splits. Os splits podem ser processados em paralelo por diferentes máquinas.

    As invocações aos reducers são distribuídas pelo particionamento do espaço das chaves intermediárias em R partições reducers (fazendo por exemplo hash(key) mod R). O número de partições R e a função de particionamento é fornecida pelo usuário. Tudo está muito bem explicado no artigo básico MapReduce: Simplified Data Processing on Large Clusters.


     

    Tolerância a falha

      – O Master que aparece na figura anterior detecta uma eventual falha em algum worker e reexecuta todas as tarefas. Reexecuta não só os mappers em andamento como também os completos. E reexecuta os reducers que estão em andamento.

      – Caso o Master detecte que algum par chave/valor causou um crash no map, manda pular tais valores na reexecução.

      – Se o Master falhar, o framework vai tentar repetir toda a operação.

     

    Otimizações

      – Como a fase de reduce não pode começar antes da fase map terminar completamente, pode existir um controlador de disco mais lento que acabará segurando todo o processo. O que se faz é detectar tarefas de map que são mais lentas e executá-las de forma redundante pegando o resultado da que terminar primeiro.


      – Pode existir casos em que a função reduce pode ser subdividida em funções “combiner”. São como se fossem mini reducers que acontecem antes da fase reduce real e visam salvar bandwidth. Já explicamos isto em MapReduce – Parte I.

     
    A vantagem principal do framework do Google é permitir manter o foco no problema e deixar que a biblioteca e o framework cuide dos detalhes.


 

Patentes

No fim da década passada, depois de muitas rejeições, o Google recebeu a patente relativa a sua implementação MapReduce (não a do modelo de programação que não foi sua invenção).

Dizem que não seria uma boa decisão de negócio o Google tentar usar seus direitos nesta patente, pelo riscos na imagem e riscos de consequências legais e monetárias caso venha a perder alguma batalha judicial nesta área.

Entre outros motivos, eu desconfio que as empresas grandes precisam das patentes justamente para não sofrer processos de empresas menores que podem tentar ganhar mais nos tribunais do que batalhando clientes.

 
Inclui este tópico porque existe uma outra implementação de MapReduce que parece infringir a patente do Google e que é justamente o motivo de ter falado tanto de MapReduce. O Hadoop, um dos principais assuntos desta série, é uma cópia da implementação do Google.

Caso o Google levasse a ferro e fogo a questão da patente da implementação e conseguisse a difícil tarefa de encurralar o Hadoop em algum dos muitos becos da lei, o Hadoop teria que mudar sua implementação.

De certa forma isto já começou a acontecer com o movimento de separar a base de código do HDFS em um módulo isolado.

Para o Hadoop os riscos de processo desapareceriam, caso viesse a adotar alguma arquitetura do tipo Cloud MapReduce, que é diferente da implementação do Google.

Em https://code.google.com/p/cloudmapreduce/ está escrito:

    Cloud MapReduce was initially developed at Accenture Technology Labs. It is a MapReduce implementation on top of the Amazon Cloud OS.

    Cloud MapReduce has minimal risk w.r.t. the MapReduce patent, compared to other open source implementations, as it is implemented in a completely different architecture than described in the Google paper.

    Ver mais sobre a questão da patente em Google’s MapReduce patent and its impact on Hadoop and Cloud MapReduce (Janeiro 2010
).

 

Conclusão

Agora todos sabem um mínimo sobre o modelo de processamento MapReduce, sobre o porquê da necessidade da existência de um framework que controle o processamento e das vantagens de tudo isto ser processado em um sistema de arquivos distribuído, que no Google é o GFS (Google File System) e no Hadoop é o HDFS (Hadoop Distributed File System).

Então poderemos seguir falando de Hadoop e do seu contexto no atual mundo em que BigData é a bola da vez (1.080.000.000 resultados no google), dados podem ser o novo Intel Inside (como disse em 2005 o Tim O’Reilly) e que por causa da onda de machine Learning (assunto que já abordamos várias vezes neste blog), estatística pode fazer parte das habilidades necessárias aos próximos “sexy jobs” (como disse em 2009 o professor Hal Varian, chefe dos economistas do Google).

É o que faremos nos próximos artigos. Aguardem.