Ordinamento dei valori prima che vengano inviano al riduttore

Question

Sto pensando di costruire una piccola applicazione di prova in Hadoop per ottenere il blocco del sistema.

L'applicazione che ho in mente sarà nel regno di fare statistiche. Voglio avere "I 10 peggiori valori per ogni chiave" dalla mia funzione riduttore (dove devo presumere la possibilità di un enorme numero di valori per alcuni tasti).

Quello che ho previsto è che i valori che vanno nella mia riduttore sarà essenzialmente essere la combinazione di "Il valore reale" e "La qualità / rilevanza del valore effettivo". Sulla base della rilevanza che "semplicemente" vuole prendere il 10 / migliori valori e le loro uscita peggiori dal riduttore.

Come faccio ad andare a fare che (assumendo un numero enorme di valori per un tasto specifico)? C'è un modo che io possa ordinare tutti i valori prima di essere inviati nel riduttore (e semplicemente smettere di leggere l'ingresso quando ho letto la prima 10) o devo questo essere fatto in modo diverso?

Può qualcuno qui mi punto ad un pezzo di codice di esempio posso avere uno sguardo?

---

Aggiornamento: Ho trovato due interessanti questioni Jira HADOOP-485 e < a href = "http://issues.apache.org/jira/browse/HADOOP-686" rel = "nofollow noreferrer"> HADOOP-686 .

Chiunque ha un frammento di codice su come utilizzare questo nel Hadoop 0.20 API?

Answer 1

Sembra che si desidera utilizzare un combinatore, che definisce che cosa fare con i valori vostro creano sul lato mappa prima di essere inviati al riduttore, ma dopo che sono raggruppate per chiave. Il combinatore è spesso destinato ad essere solo la classe riduttore (in modo da ridurre sul lato carta, e poi di nuovo sul lato ridurre).

Date un'occhiata a come l'esempio wordcount utilizza il combinatore di pre-calcolare i conteggi parziali:

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

---

Aggiorna Ecco quello che ho in mente per il vostro problema; è possibile ho frainteso ciò che si sta cercando di fare, però.

Ogni mapper emette coppie <key, {score, data}>.

Il combinatore ottiene un set parziale di queste coppie: <key, [set of {score, data}> e fa una sorta locale (ancora sui nodi mapping), e uscite <key, [sorted set of top 10 local {score, data}]> coppie

.

Il riduttore otterrà <key, [set of top-10-sets]> - tutto quello che deve fare è eseguire il punto di unione di sort-merge (senza ordinamento necessario) per ciascuno dei membri dei gruppi di valori, e fermare la fusione quando i primi 10 valori sono tirati.

---

Aggiornamento 2

Quindi, ora che sappiamo che il rango come cumilative e, di conseguenza, non è possibile filtrare i dati in anticipo utilizzando combinatori, l'unica cosa è di fare ciò che avete suggerito - ottiene un ordinamento secondario in corso. Hai trovato i biglietti giusti; v'è un esempio di come fare questo in Hadoop 20 in src / examples / org / apache / Hadoop / examples / SecondarySort.java (o, se non si desidera scaricare l'intero albero dei sorgenti, si può guardare l'esempio patch in https://issues.apache.org/jira/browse/HADOOP-4545 )

Answer 2

Suoni definitivamente come un SecondarySortProblem. Date un'occhiata in "Hadoop: La guida definitiva", se vi piace. E 'da O'Reilly. È anche possibile accedere online. Ci descrivono una buona implementazione.

ho implementato da me troppo. In pratica funziona in questo modo: Il programma di partizionamento si cura per tutti i valore di coppie di chiavi con la stessa chiave visitando una sola riduttore. Niente di speciale qui. Ma c'è anche la GroupingComparator, che formeranno gruppi. Un gruppo è in realtà passato come un iteratore ad un ridurre () - chiamata. Così una partizione può contenere più raggruppamenti. Ma la quantità di partizioni deve essere uguale al numero di riduttori. Ma il raggruppamento permette anche di fare un po 'di smistamento in quanto implementa un compareTo-metodo.

Con questo metodo, è possibile controllare, che i 10 migliori / peggiori / alta / bassa tuttavia chiavi raggiungeranno il riduttore prima. Così, dopo aver letto questi 10 tasti, è possibile lasciare il metodo di ridurre senza ulteriori iterazioni.

La speranza che era disponibile: -)

Answer 3

Se ho capito la domanda correttamente, è necessario utilizzare un TotalOrderPartitioner .