Tri des valeurs avant qu'elles ne soient envoyées au réducteur

Question

Je pense à la construction d'une petite application de test dans Hadoop pour obtenir le blocage du système.

L'application que j'ai à l'esprit sera dans le domaine des statistiques faisant. Je veux avoir « Les 10 pires valeurs pour chaque touche » de ma fonction réducteur (où je dois supposer la possibilité d'un grand nombre de valeurs pour certaines touches).

Ce que j'ai prévu est que les valeurs qui vont dans mon réducteur sera essentiellement la combinaison de « La valeur réelle » et « La qualité / pertinence de la valeur réelle ». Sur la base de la pertinence I « simplement » envie de prendre les 10 pires / meilleurs valeurs et les sortie du réducteur.

Comment vais-je à faire cela (en supposant un grand nombre de valeurs pour une clé spécifique)? Est-il possible que je peux trier toutes les valeurs avant d'être envoyés dans le réducteur (et simplement arrêter la lecture de l'entrée quand j'ai lu les 10 premiers) ou faut-il être fait différemment?

Quelqu'un peut-il indiquer ici moi un morceau de code exemple, je peux jeter un oeil à?

---

Mise à jour: je l'ai trouvé deux questions intéressantes Jira Hadoop-485 et < a href = "http://issues.apache.org/jira/browse/HADOOP-686" rel = "nofollow noreferrer"> Hadoop-686 .

Toute personne a un fragment de code sur la façon d'utiliser l'API Hadoop 0,20?

Answer 1

On dirait que vous voulez utiliser un combinateur, qui définit ce qu'il faut faire avec les valeurs de votre côté créer sur la carte avant d'être envoyés au réducteur, mais après ils sont regroupés par clé. Le combinateur est souvent mis à être juste la classe réducteur (si vous réduisez sur le côté de la carte, puis à nouveau sur le côté réduire).

Jetez un oeil à la façon dont l'exemple wordcount utilise le combinateur de pré-calculer les comptes partiels:

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

---

Mise à jour Voici ce que je pense à votre problème; il est possible d'avoir mal compris ce que vous essayez de faire, cependant.

Chaque mappeur émet des paires de <key, {score, data}>.

Le combineur reçoit un ensemble partiel de ces paires: <key, [set of {score, data}> et fait un tri local (toujours sur les noeuds du mappeur), et les sorties des paires <key, [sorted set of top 10 local {score, data}]>

.

Le réducteur va se <key, [set of top-10-sets]> - tout ce qu'il a à faire est de réaliser l'étape de fusion de tri-fusion (pas de tri nécessaire) pour chacun des membres des ensembles de valeurs, et d'arrêter la fusion lorsque les 10 premières valeurs sont tirés.

---

Mise à jour 2

Alors, maintenant que nous savons que le rang cumilative et par conséquent, vous ne pouvez pas filtrer les premières données en utilisant combineurs, la seule chose est de faire ce que vous suggérez - obtenir une sorte secondaire va. Vous avez trouvé les bons billets; il est un exemple de la façon de le faire dans Hadoop 20 dans src / examples / org / apache / Hadoop / examples / SecondarySort.java (ou, si vous ne voulez pas télécharger l'arbre source entier, vous pouvez regarder l'exemple patcher https://issues.apache.org/jira/browse/HADOOP-4545 )

Answer 2

Sons définitivement comme un SecondarySortProblem. Jetez un coup d'oeil dans « Hadoop: Le guide définitif », si vous le souhaitez. Il est de O'Reilly. Vous pouvez également y accéder en ligne. Là, ils décrivent une très bonne mise en œuvre.

Je mis en œuvre aussi par moi-même. Fondamentalement, il fonctionne de cette façon: Le partitionneur prendra soin de toutes les valeurs-clés paires avec la même clé allant à un seul réducteur. Rien de spécial ici. Mais il y a aussi la GroupingComparator, qui formera des groupes. Un groupe est en fait passé comme un itérateur à une baisse () - appeler. Ainsi, une partition peut contenir plusieurs groupements. Mais la quantité de partitions doit être égal au nombre de réducteurs. Mais le regroupement permet également de faire un peu de tri car il met en œuvre une méthode compareTo.

Avec cette méthode, vous pouvez contrôler, que les 10 meilleurs mais les touches / pire / maximum / minimum atteindra le réducteur premier. Donc, après avoir lu ces 10 touches, vous pouvez laisser la méthode sans réduire d'autres itérations.

Hope qui a été utile: -)

Answer 3

Si je comprends bien la question, vous aurez besoin d'utiliser un TotalOrderPartitioner .