Ajuda a entender o MapReduce Classificar exemplo

5

Na seção 5.3 do artigo do Google descrevendo o MapReduce.

"A Map function extracts a 10-byte sorting key from a text line and emits the key and the original text line as the intermediate key/value pair. We used a built-in Identity function as the Reduce operator. This function passes the intermediate key/value pair unchanged as the output key/value pair. The final sorted output is written..."

Eu não entendo como a classificação real acontece. Tanto quanto eu entendo, eles mapeiam a função extrai um par de valores-chave, e então a função Reduzir de alguma forma expulsa os dados ordenados. O que é uma "chave de classificação"?

    
por Bryan Glazer 18.01.2013 / 22:45
fonte

2 respostas

2

A classificação depende de alguns detalhes de implementação e funcionalidades adicionais no tempo de execução do Google. Veja a seção 4.2:

We guarantee that within a given partition, the intermediate key/value pairs are processed in increasing key order. This ordering guarantee makes it easy to generate a sorted output file per partition, which is useful when the output file format needs to support efficient random access lookups by key, or users of the output find it convenient to have the data sorted.

O sistema também permite um esquema de particionamento arbitrário (mencionado na seção 4.1). O sistema de classificação usa esse esquema:

The partitioning function uses the initial bytes of the key to segregate it into one of R pieces.

Assim, quando a função Reduzir é executada em cada partição, não há alterações nos dados, mas a saída é garantida na ordem correta (presumivelmente não há nada especial sobre a implementação disso - é apenas um tipo local simples de algum tipo ).

Uma vez que você tenha suas partições classificadas, tudo o que você precisa fazer é concatená-las na ordem dos bytes iniciais que foram usados para criar as partições e você tem uma lista totalmente classificada.

(Eu estou tomando uma "chave de classificação" para ser um resumo do valor que é projetado, então quando as chaves são classificadas, os valores também estão na ordem correta, pelo menos para uma aproximação razoável. Simplesmente truncando o primeiro letras de uma corda seria suficiente para fazer uma chave de classificação bruta)

    
por 18.01.2013 / 23:09
fonte
5

Dê uma olhada em este vídeo do YouTube, de um professor explicando os conceitos envolvidos no algoritmo MapReduce. Infelizmente, todo o código está em Scheme, portanto, a legibilidade não é a melhor, mas ele explica bem o que acontece.

Basicamente, MapReduce tem mais do que apenas essas duas etapas. É assim:

  • Mapa: para cada entrada, produza 0, 1 ou mais pares de valores-chave
  • Classificar: reúna os pares de valores-chave e classifique-os por suas chaves em um grupo de blocos
  • Reduzir: cada balde é reduzido em paralelo a um único resultado. Os resultados de cada depósito são então combinados (reduzidos) para um resultado final.

A etapa de classificação está basicamente lá para que você possa executar a operação Reduzir de forma distribuída e paralela em vez de fazer a coisa toda em série, o que exigiria que toda a tarefa Reduza fosse manipulada por um único sistema, que derrota o propósito.

    
por 18.01.2013 / 23:01
fonte