ti-enxame.com

Classificando dados grandes usando o MapReduce / Hadoop

Estou lendo sobre o MapReduce e a seguinte coisa está me confundindo.

Suponha que tenhamos um arquivo com 1 milhão de entradas (inteiros) e queremos classificá-las usando o MapReduce. O jeito que eu entendi é o seguinte:

Escreva uma função de mapeador que classifique números inteiros. Portanto, a estrutura dividirá o arquivo de entrada em vários pedaços e os daria a diferentes mapeadores. Cada mapeador classificará seus blocos de dados independentemente um do outro. Quando todos os mapeadores estiverem prontos, passaremos cada um dos resultados para o Reducer, que combinará o resultado e fornecerá a saída final.

A minha dúvida é que, se temos um redutor, como ele aproveita a estrutura distribuída, se, eventualmente, precisamos combinar o resultado em um único local? O problema se resume a mesclar 1 milhão de entradas em um só local. É assim ou estou faltando alguma coisa?

Obrigado, Chander

32
Chander Shivdasani

Confira a classificação por mesclagem.

Acontece que classificar listas parcialmente classificadas é muito mais eficiente em termos de operações e consumo de memória do que classificar a lista completa.

Se o redutor obtiver 4 listas ordenadas, ele precisará apenas procurar o menor elemento das 4 listas e escolher essa. Se o número de listas for constante, essa redução é uma operação O(N).

Além disso, normalmente os redutores também são "distribuídos" em algo como uma árvore, para que o trabalho também possa ser paralelo.

23
Peter Tillemans

Como outros já mencionaram, a fusão é muito mais simples do que a classificação, então há uma grande vitória lá.

No entanto, fazer uma operação serial O(N) em um conjunto de dados gigante também pode ser proibitivo. Como você aponta corretamente, é melhor encontrar uma maneira de fazer a mesclagem em paralelo, também .

Uma maneira de fazer isso é substituir a função de particionamento do particionador aleatório (que é normalmente usado) por algo um pouco mais inteligente. O que o Pig faz para isso, por exemplo, é exemplo de seu conjunto de dados para obter uma aproximação aproximada da distribuição de seus valores e depois atribuir intervalos de valores a diferentes redutores. O redutor 0 obtém todos os elementos <1000, o redutor 1 obtém todos os elementos> = 1000 e <5000 e assim por diante. Em seguida, você pode fazer a mesclagem em paralelo, e o resultado final é classificado conforme você sabe o número de cada tarefa do redutor.

13
SquareCog

Portanto, a maneira mais simples de classificar usando a redução de mapa (embora não seja a mais eficiente) é fazer o seguinte

Durante a fase do mapa (Input_Key, Input_Value) é emitida (Input_Value, Input Key)

Redutor é um redutor de identidade

Assim, por exemplo, se nossos dados são de um aluno, banco de dados de idade, a entrada do seu mapeador seria ('A', 1) ('B', 2) ('C', 10) ... e a saída seria (1, A) (2, B) (10, C)

Ainda não tentei essa lógica, mas é um problema no dever de casa em que estou trabalhando. Colocará um código-fonte atualizado/link lógico.

7
rOrlig

Desculpe pelo atraso, mas para os futuros leitores, sim, Chander, você está perdendo alguma coisa.

A lógica é que o Redutor pode manipular dados embaralhados e, em seguida, classificar os dados de seu nó apenas no qual está sendo executado. Quero dizer, o redutor que é executado em um nó não pode olhar para os dados de outros nós, ele aplica o algoritmo de redução apenas em seus dados. Portanto, o procedimento de mesclagem da classificação por mesclagem não pode ser aplicado.

Portanto, para big data, usamos o TeraSort, que nada mais é do que mapeador e redutor de identidade com o particionador personalizado. Você pode ler mais sobre isso aqui Implementação do Hadoop para TeraSort . Afirma:

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

2
Alok Nayak

A classificação pode ser implementada com eficiência usando o MapReduce. Mas você parece estar pensando em implementar a classificação por mesclagem usando o mapreduce para atingir esse objetivo. Pode não ser o candidato ideal.

Como você mencionou, o mergesort (com redução de mapa) envolveria as seguintes etapas:

  1. Particione os elementos em pequenos grupos e atribua cada grupo aos mapeadores de maneira round robin
  2. Cada mapeador classificará o subconjunto e retornará {K, {subconjunto}}, onde K é o mesmo para todos os mapeadores
  3. Como o mesmo K é usado em todos os mapeadores, apenas um reduz e, portanto, apenas um redutor. O redutor pode mesclar os dados e retornar o resultado classificado

O problema aqui é que, como você mencionou, pode haver apenas um redutor que impede o paralelismo durante a fase de redução. Como foi mencionado em outras respostas, mapreduce implementações específicas como terasort podem ser consideradas para esse fim.

Encontrei a explicação em http://www.chinacloud.cn/upload/2014-01/14010410467139.pdf

Voltando à classificação por mesclagem, isso seria viável se a ferramenta hadoop (ou equivalente) fornecer hierarquia de redutores em que a saída de um nível de redutores vá para o próximo nível de redutores ou faça um loop no mesmo conjunto de redutores

1
prabhakar palanivel

Eu acho que combinar vários itens classificados é eficiente do que combinar vários itens não classificados. Portanto, os mapeadores executam a tarefa de classificar os pedaços e o redutor os mescla. Se os mapeadores não tivessem feito a classificação, o redutor terá dificuldade em fazer a classificação.

1
Gopi