Qual é a finalidade da fase de embaralhamento e classificação no redutor na Programação Map Reduce?

Na programação do Map Reduce, a fase de redução tem embaralhamento, classificação e redução como suas sub-partes. A classificação é um assunto caro.

Qual é a finalidade da fase de embaralhamento e classificação no redutor na Programação Map Reduce?

Em primeiro lugar, shufflingé o processo de transferência de dados dos mapeadores para os redutores, então eu acho que é óbvio que é necessário para os redutores, pois caso contrário, eles não seriam capazes de ter nenhuma entrada (ou entrada de cada mapeador) . O embaralhamento pode começar antes mesmo de a fase do mapa terminar, para economizar algum tempo. É por isso que você pode ver um status de redução maior que 0% (mas menor que 33%) quando o status do mapa ainda não é 100%.

Sortingeconomiza tempo para o redutor, ajudando-o a distinguir facilmente quando uma nova tarefa de redução deve ser iniciada. Ele simplesmente inicia uma nova tarefa de redução, quando a próxima chave nos dados de entrada classificados for diferente da anterior, para simplificar. Cada tarefa de redução leva uma lista de pares de valores-chave, mas tem que chamar o método reduce () que usa uma entrada de lista de chaves (valor), então tem que agrupar os valores por chave. É fácil fazer isso, se os dados de entrada forem pré-classificados (localmente) na fase de mapa e simplesmente classificados por mesclagem na fase de redução (já que os redutores obtêm dados de muitos mapeadores).

Partitioning, que você mencionou em uma das respostas, é um processo diferente. Determina em qual redutor será enviado um par (chave, valor), saída da fase do mapa. O Particionador padrão usa um hash nas chaves para distribuí-las para as tarefas de redução, mas você pode substituí-lo e usar seu próprio Particionador personalizado.

Uma ótima fonte de informações para essas etapas é este tutorial do Yahoo .

Uma bela representação gráfica disso é a seguinte (o shuffle é chamado de "cópia" nesta figura):

Observe que shufflinge sortingnão são executados se você especificar redutores zero (setNumReduceTasks (0)). Então, o trabalho MapReduce para na fase do mapa, e a fase do mapa não inclui nenhum tipo de classificação (portanto, mesmo a fase do mapa é mais rápida).

ATUALIZAÇÃO: Já que você está procurando por algo mais oficial, também pode ler o livro "Hadoop: The Definitive Guide" de Tom White. Aqui está a parte interessante da sua pergunta.
Tom White é um committer do Apache Hadoop desde fevereiro de 2007 e é membro da Apache Software Foundation, então eu acho que é bastante confiável e oficial ...

Vamos revisitar as principais fases do programa Mapreduce.

A fase do mapa é feita por mapeadores. Os mapeadores são executados em pares chave / valores de entrada não classificados. Cada mapeador emite zero, um ou vários pares de chave / valor de saída para cada par de chave / valor de entrada.

A fase de combinação é feita por combinadores. O combinador deve combinar pares de chave / valor com a mesma chave. Cada combinador pode executar zero, uma ou várias vezes.

A fase de embaralhamento e classificação é feita pela estrutura. Os dados de todos os mapeadores são agrupados pela chave, divididos entre redutores e classificados pela chave. Cada redutor obtém todos os valores associados à mesma chave. O programador pode fornecer funções de comparação personalizadas para classificação e um particionador para divisão de dados.

O particionador decide qual redutor obterá um par de valores-chave específico.

O redutor obtém pares de chave / [lista de valores] classificados, classificados pela chave. A lista de valores contém todos os valores com a mesma chave produzida por mapeadores. Cada redutor emite zero, um ou vários pares de chave / valor de saída para cada par de chave / valor de entrada .

Dê uma olhada neste artigo javacodegeeks de Maria Jurcovicova e no artigo mssqltips de Datta para uma melhor compreensão

Abaixo está a imagem do artigo safaribooksonline

Pensei apenas em adicionar alguns pontos que faltam nas respostas acima. Este diagrama retirado daqui afirma claramente o que realmente está acontecendo.

Se eu declarar novamente o verdadeiro propósito de

• Divisão: melhora o processamento paralelo, distribuindo a carga de processamento entre nós diferentes (mapeadores), o que economizaria o tempo de processamento geral.

• Combinar: reduz a saída de cada mapeador. Isso economizaria tempo gasto para mover os dados de um nó para outro.

• Sort (Shuffle & Sort): torna mais fácil para o tempo de execução agendar (spawn / start) novos redutores, onde ao percorrer a lista de itens classificados, sempre que a chave atual for diferente da anterior, ela pode gerar um novo redutor .

Alguns dos requisitos de processamento de dados não precisam de classificação. O Syncsort tornou a classificação no Hadoop plugável. Aqui está um bom blog deles sobre classificação. O processo de mover os dados dos mapeadores para os redutores é chamado de embaralhamento, consulte este artigo para obter mais informações sobre o mesmo.

Sempre presumi que isso era necessário, pois a saída do mapeador é a entrada para o redutor, então ela foi classificada com base no keyspace e então dividida em depósitos para cada entrada do redutor. Você quer garantir que todos os mesmos valores de uma chave acabem no mesmo balde indo para o redutor, de forma que sejam reduzidos juntos. Não adianta enviar K1, V2 e K1, V4 para redutores diferentes, pois eles precisam estar juntos para serem reduzidos.

Tentei explicar da forma mais simples possível

O embaralhamento é o processo pelo qual os dados intermediários dos mapeadores são transferidos para 0,1 ou mais redutores. Cada redutor recebe 1 ou mais chaves e seus valores associados dependendo do número de redutores (para uma carga balanceada). Além disso, os valores associados a cada chave são classificados localmente.

O MapReduce faz apenas duas coisas NATIVELMENTE: Classificar e (implementado por classificação) GroupBy escalável.

A maioria dos aplicativos e Design Patterns sobre MapReduce são construídos sobre essas duas operações, que são fornecidas por shuffle e sort.

Esta é uma boa leitura. Espero que ajude. Em termos de classificação, acho que é para a operação de mesclagem na última etapa do Mapa. Quando a operação de mapa for concluída e precisar gravar o resultado no disco local, uma mesclagem múltipla será operada nas divisões geradas do buffer. E para uma operação de mesclagem, classificar cada partição em avançado é útil.

Bem, no Mapreduce há duas frases importantes chamadas Mapeador e redutor, ambas muito importantes, mas Redutor é obrigatório. Em alguns programas, os redutores são opcionais. Agora vamos à sua pergunta. Embaralhar e classificar são duas operações importantes no Mapreduce. A primeira estrutura Hadoop pega dados estruturados / não estruturados e separa os dados em Chave, Valor.

Agora o programa Mapper separa e organiza os dados em chaves e valores a serem processados. Gere os valores da chave 2 e do valor 2. Esses valores devem ser processados ​​e reorganizados na ordem adequada para obter a solução desejada. Agora, esse embaralhamento e classificação são feitos em seu sistema local (o Framework cuida disso) e o processo no sistema local após a limpeza do framework do processo no sistema local. Está bem

Aqui, usamos combinador e partição também para otimizar esse processo de embaralhamento e classificação. Após o arranjo adequado, esses valores-chave passam para o Redutor para obter a saída desejada do Cliente. Finalmente, o Redutor obtém a saída desejada.

K1, V1 -> K2, V2 (escreveremos o programa Mapper), -> K2, V '(aqui embaralhe e suavize os dados) -> K3, V3 Gere a saída. K4, V4.

Observe que todas essas etapas são apenas operações lógicas, não alteram os dados originais.

Sua pergunta: Qual é o propósito da fase de embaralhamento e classificação no redutor na Programação Map Reduce?

Resposta curta: Para processar os dados para obter a saída desejada. O embaralhamento é agregar os dados, reduzir é obter a saída esperada.