Aiuto nella comprensione di MapReduce Esempio di ordinamento

5

Dalla Sezione 5.3 del articolo di Google descrizione di MapReduce.

"A Map function extracts a 10-byte sorting key from a text line and emits the key and the original text line as the intermediate key/value pair. We used a built-in Identity function as the Reduce operator. This function passes the intermediate key/value pair unchanged as the output key/value pair. The final sorted output is written..."

Non capisco come avvenga l'ordinamento vero e proprio. Per quanto ho capito, la funzione Map estrae una coppia di valori chiave, quindi la funzione Reduce espelle in qualche modo i dati ordinati. Cos'è una "chiave di ordinamento"?

    
posta Bryan Glazer 18.01.2013 - 22:45
fonte

2 risposte

2

L'ordinamento dipende da alcuni dettagli di implementazione e funzionalità aggiuntive nel runtime di Google. Vedi la sezione 4.2:

We guarantee that within a given partition, the intermediate key/value pairs are processed in increasing key order. This ordering guarantee makes it easy to generate a sorted output file per partition, which is useful when the output file format needs to support efficient random access lookups by key, or users of the output find it convenient to have the data sorted.

Il sistema consente anche uno schema di partizionamento arbitrario (menzionato nella sezione 4.1). Il sistema di ordinamento utilizza questo schema:

The partitioning function uses the initial bytes of the key to segregate it into one of R pieces.

Quindi, quando la funzione Reduce viene eseguita su ogni partizione, non ci sono modifiche ai dati, ma l'output è garantito nell'ordine corretto (presumibilmente non c'è nulla di speciale nell'implementazione di questo - è solo un semplice tipo locale di qualche tipo ).

Una volta che hai le partizioni ordinate, tutto ciò che devi fare è concatenarle nell'ordine dei byte iniziali che sono stati usati per creare le partizioni e hai un elenco completamente ordinato.

(Sto prendendo una "chiave di ordinamento" per essere un riassunto del valore che è stato progettato in modo tale che quando le chiavi sono ordinate i valori sono anche nell'ordine corretto, almeno in una approssimazione ragionevole. Semplicemente troncando il primo le lettere di una stringa sarebbero sufficienti per creare una chiave di ordinamento grezza)

    
risposta data 18.01.2013 - 23:09
fonte
5

Dai un'occhiata a questo video di YouTube di un professore che spiega i concetti coinvolti nell'algoritmo MapReduce. Sfortunatamente, tutto il codice è in Scheme, quindi la leggibilità non è la migliore, ma fa un buon lavoro di spiegazione di ciò che accade.

Fondamentalmente, MapReduce ha più di quei due passaggi. Funziona così:

  • Mappa: per ogni input, produce 0, 1 o più coppie chiave-valore
  • Ordina: raccogli le coppie chiave-valore e ordinale per le loro chiavi in un gruppo di bucket
  • Riduci: ogni secchio viene ridotto in parallelo a un singolo risultato. I risultati di ciascun bucket vengono quindi combinati (ridotti) a un risultato finale.

Il passaggio di ordinamento è fondamentalmente lì così puoi eseguire l'operazione di Riduzione in modo distribuito, parallelo invece di dover fare tutto in serie, il che richiederebbe che l'intera attività di Riduzione venga gestita da un singolo sistema, che tipo di sconfigge lo scopo.

    
risposta data 18.01.2013 - 23:01
fonte

Leggi altre domande sui tag