Como funciona o algoritmo de classificação MapReduce?

Um dos principais exemplos usados ​​para demonstrar o poder do MapReduce é o benchmark Terasort . Estou tendo problemas para entender os fundamentos do algoritmo de classificação usado no ambiente MapReduce.

Para mim, a classificação envolve simplesmente determinar a posição relativa de um elemento em relação a todos os outros elementos. Assim, a classificação envolve comparar "tudo" com "tudo". Seu algoritmo de classificação médio (rápido, bolha, ...) simplesmente faz isso de maneira inteligente.

Na minha opinião, dividir o conjunto de dados em muitas partes significa que você pode classificar uma única parte e, então, ainda terá que integrar essas partes no conjunto de dados totalmente classificado "completo". Dado o conjunto de dados de terabytes distribuídos em milhares de sistemas, espero que seja uma tarefa gigantesca.

Então, como isso é realmente feito? Como funciona esse algoritmo de classificação MapReduce?

Obrigado por me ajudar a entender.

Aqui estão alguns detalhes sobre a implementação do Hadoop para Terasort :

TeraSort é uma classificação padrão de mapa / redução, exceto para um particionador personalizado que usa uma lista classificada de N - 1 chaves de amostra que definem o intervalo de chave para cada redução. Em particular, todas as chaves como amostra [i - 1] <= chave <amostra [i] são enviadas para reduzir i. Isso garante que a saída de reduzir i seja menor do que a saída de reduzir i + 1. "

Portanto, o truque deles está na maneira como determinam as chaves durante a fase do mapa. Essencialmente, eles garantem que cada valor em um único redutor seja 'pré-classificado' em relação a todos os outros redutores.

Eu encontrei a referência de papel através do Blog Post de James Hamilton .

Referência do Google: MapReduce: processamento de dados simplificado em grandes clusters

Publicado em :
OSDI'04: Sexto Simpósio sobre Projeto e Implementação de Sistema Operacional,
San Francisco, CA, dezembro de 2004.

Esse link tem uma referência de PDF e HTML-Slide.

Há também uma página da Wikipedia com descrição e referências de implementação.

Também críticas,

David DeWitt e Michael Stonebraker, especialistas pioneiros em bancos de dados paralelos e arquiteturas não compartilhadas, fizeram algumas afirmações controversas sobre a amplitude de problemas para os quais o MapReduce pode ser usado. Eles chamaram sua interface de nível muito baixo e questionaram se ela realmente representa a mudança de paradigma que seus proponentes afirmam que é. Eles desafiam as alegações de novidade dos proponentes do MapReduce, citando o Teradata como um exemplo de técnica anterior que existe há mais de duas décadas; eles compararam programadores MapReduce a programadores Codasyl, observando que ambos estão "escrevendo em uma linguagem de baixo nível, realizando manipulação de registros de baixo nível". O uso de arquivos de entrada do MapReduce e a falta de suporte a esquema evita as melhorias de desempenho habilitadas por recursos comuns do sistema de banco de dados, como árvores B e particionamento hash,

Eu tive a mesma pergunta enquanto lia o artigo MapReduce do Google. A resposta de @Yuval F praticamente resolveu meu quebra-cabeça.

Uma coisa que notei ao ler o jornal é que a mágica acontece no particionamento (depois do mapa, antes de reduzir).

O papel usa hash(key) mod R como exemplo de particionamento, mas esta não é a única maneira de particionar dados intermediários para diferentes tarefas de redução.

Basta adicionar condições de contorno para @Yuval F 's resposta para completá-lo: min supõem (S) e max (S) é a chave mínimo e máximo da chave entre as chaves amostrados; todas as chaves <min (S) são particionadas em uma tarefa de redução; vice-versa, todas as chaves> = max (S) são particionadas em uma tarefa de redução.

Não há limitação rígida nas chaves de amostra, como mín ou máx. Apenas, mais uniformemente essas chaves R distribuídas entre todas as chaves, mais "paralelo" este sistema distribuído é e menos provável que um operador de redução tenha problema de estouro de memória.

Apenas adivinhando...

Dado um grande conjunto de dados, você particionaria os dados em alguns blocos para serem processados ​​em paralelo (talvez pelo número do registro, ou seja, registro 1 - 1000 = partição 1 e assim por diante).

Atribua / agende cada partição a um nó específico no cluster.

Cada nó do cluster irá dividir (mapear) a partição em sua própria minipartição, talvez pela ordem alfabética principal. Então, na partição 1, pegue todas as coisas que começam com A e produza na minipartição A de x. Crie um novo A (x) se atualmente já houver um A (x). Substitua x pelo número sequencial (talvez este seja o trabalho do planejador para fazer isso). Ie Dê-me o próximo A (x) id exclusivo.

Transfira (agende) os trabalhos concluídos pelo mapeador (etapa anterior) para os nós de cluster "reduzir". Reduzir o cluster de nós irá então refinar ainda mais o tipo de cada parte A (x) que acontecerá somente quando todas as tarefas do mapeador forem concluídas (não é possível começar a classificar todas as palavras começando com w / A quando ainda há possibilidade de que ainda haja vai ser outra partição A mini em construção). Produza o resultado na partição final classificada (ou seja, Sorted-A, Sorted-B, etc.)

Uma vez feito isso, combine a partição classificada em um único conjunto de dados novamente. Neste ponto, é apenas uma simples concatenação de n arquivos (onde n pode ser 26 se você estiver apenas fazendo A - Z), etc.

Pode haver etapas intermediárias entre ... Não tenho certeza :). Ou seja, mapeie e reduza ainda mais após a etapa de redução inicial.