Trier les 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 maîtriser le système.

L'application que j'ai à l'esprit sera dans le domaine de la statistique. 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, c'est que les valeurs qui vont dans mon réducteur seront essentiellement la combinaison de "La valeur réelle" et "La qualité/pertinence de la valeur réelle". En fonction de la pertinence, je "veux" simplement prendre les 10 valeurs les plus basses/les meilleures et les sortir du réducteur.

Comment est-ce que je fais cela (en supposant un grand nombre de valeurs pour une clé spécifique)? Existe-t-il un moyen de trier toutes les valeurs AVANT qu'elles soient envoyées dans le réducteur (et d'arrêter simplement de lire l'entrée quand j'ai lu les 10 premières) ou doit-il être fait différemment? Est-ce que quelqu'un ici peut me diriger vers un exemple de code que je peux consulter?

---

Mise à jour: je l'ai trouvé deux JIRA intéressantes HADOOP-485 et HADOOP-686.

Quelqu'un a un fragment de code sur la façon de l'utiliser dans l'API Hadoop 0.20?

Answer 1

Il semble que vous vouliez utiliser un combineur, qui définit ce qu'il faut faire avec les valeurs que vous créez sur le côté carte avant qu'elles ne soient envoyées au réducteur, mais après qu'elles soient groupées par clé. Le combineur est souvent configuré pour n'être que la classe de réduction (donc vous réduisez du côté de la carte, puis de nouveau du côté réduction).

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; Cependant, j'ai peut-être mal compris ce que vous essayez de faire. Chaque mappeur émet des paires <key, {score, data}>. Le combineur obtient un ensemble partiel de ces paires: <key, [set of {score, data}> et effectue un tri local (toujours sur les nœuds de mappeur), et génère des paires <key, [sorted set of top 10 local {score, data}]>.

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

---

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 avez suggéré - obtenir un tri secondaire allant. Vous avez trouvé les bons tickets; il y a un exemple de comment faire cela dans Hadoop 20 dans src/examples/org/apache/hadoop/examples/SecondarySort.java (ou, si vous ne voulez pas télécharger l'intégralité de l'arborescence source, vous pouvez consulter le patch exemple en https://issues.apache.org/jira/browse/HADOOP-4545)

Answer 2

Si je comprends bien la question, vous devrez utiliser un TotalOrderPartitioner.

Answer 3

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

Je l'ai mis en œuvre par moi-même aussi. Fondamentalement, il fonctionne de cette façon: Le partitionneur prendra soin de toutes les paires clé-valeur avec la même clé allant à un seul réducteur. Rien de spécial ici. Mais il y a aussi le GroupingComparator, qui va former des groupements. Un groupe est effectivement passé en tant qu' itérateur à un appel reduce(). Une partition peut donc contenir plusieurs groupes. Mais la quantité de partitions devrait être égale au nombre de réducteurs. Mais le regroupement permet aussi de faire un tri en implémentant une méthode compareTo.

Avec cette méthode, vous pouvez contrôler que les 10 touches meilleur/pire/plus haut/plus bas atteignent d'abord le réducteur. Ainsi, après avoir lu ces 10 clés, vous pouvez laisser la méthode réduire sans autre itération.

espoir qui a été utile :-)