Classificando os valores antes que eles são enviados para o redutor

Question

Estou pensando em construir uma pequena aplicação de teste em Hadoop para pegar o jeito do sistema.

O aplicativo que tenho em mente vai estar no reino de fazer estatísticas. Quero ter "Os 10 piores valores para cada chave" da minha função de redutor (onde eu deve assumir a possibilidade de um grande número de valores para algumas teclas).

O que eu tenho planejado é que os valores que entram em minha redutor vai ser basicamente a combinação de "O valor real" e "A qualidade / relevância do valor real". Com base na relevância I "simplesmente" querer tomar as 10 piores melhores valores / e enviá-las a partir do redutor.

Como posso fazer sobre isso (supondo que um grande número de valores para uma chave específica)? Existe uma maneira que eu posso classificar todos os valores antes de serem enviados para o redutor (e simplesmente parar de ler a entrada quando eu li o primeiro 10) ou isso deve ser feito de forma diferente?

Pode alguém aqui me apontar para um pedaço de código de exemplo que posso dar uma olhada?

---

Update: Eu encontrei duas questões interessantes Jira HADOOP-485 e < a href = "http://issues.apache.org/jira/browse/HADOOP-686" rel = "nofollow noreferrer"> HADOOP-686 .

Qualquer um tem um fragmento de código sobre como usar isso na API Hadoop 0.20?

Answer 1

Parece que você quiser usar um combinador, que define o que fazer com os valores a sua criação no lado do mapa antes de serem enviados para o redutor, mas depois que eles são agrupados por chave. O combinador é muitas vezes definido para ser apenas a classe redutor (de modo a reduzir no lado do mapa, e depois novamente no lado reduzir).

Dê uma olhada em como o exemplo WordCount usa o combinador a contagem parcial de computação pré:

http://wiki.apache.org/hadoop/WordCount

---

Atualização Aqui está o que eu tenho em mente para o seu problema; é possível mal entendido I o que você está tentando fazer, no entanto.

A cada emite mapeador <key, {score, data}> pares.

O combinador recebe um conjunto parcial desses pares:. <key, [set of {score, data}> e faz uma espécie local (ainda nos nós mapeador), e saídas <key, [sorted set of top 10 local {score, data}]> pares

O redutor terá <key, [set of top-10-sets]> - tudo o que tem a fazer é realizar a etapa de fusão do tipo-merge (sem ordenação necessário) para cada um dos membros dos conjuntos de valores, e paragem de fusão quando os primeiros 10 valores são puxados.

---

update 2

Então, agora que sabemos que a classificação como cumilative e, como resultado, você não pode filtrar os dados no início usando combinadores, a única coisa é fazer o que você sugeriu - obter uma classificação secundária indo. Você encontrou os bilhetes à direita; há um exemplo de como fazer isso em Hadoop 20 em src / examples / org / apache / hadoop / examples / SecondarySort.java (ou, se você não quer baixar a árvore fonte inteira, você pode olhar para o exemplo remendo em https://issues.apache.org/jira/browse/HADOOP-4545 )

Answer 2

Sounds definitivamente como um SecondarySortProblem. Dê uma olhada em "Hadoop: The Definitive Guide", se você gosta de. É de O'Reilly. Você também pode acessá-lo on-line. Lá, eles descrevem uma implementação muito bom.

Eu implementei isso por mim também. Basicamente ele funciona desta maneira: O particionador vai cuidar de todos os valores-chave de pares com a mesma chave vai a um único redutor. Nada de especial aqui. Mas há também a GroupingComparator, que irá formar agrupamentos. Um grupo é, na verdade, passado como um iterador para uma reduzir () - chamada. Assim, uma partição pode conter várias agrupamentos. Mas a quantidade de partições deve ser igual ao número de redutores. Mas o agrupamento também permite fazer alguma classificação, uma vez que implementa um método-compareTo.

Com este método, você pode controlar, que os 10 melhores / piores / altos / menor no entanto chaves vai chegar ao redutor de primeira. Então, depois de ler estas 10 teclas, você pode deixar o método de reduzir sem mais iterações.

Espero que foi útil: -)

Answer 3

Se eu entendi a pergunta corretamente, você vai precisar usar um TotalOrderPartitioner .