Come funziona l'algoritmo di ordinamento MapReduce?

Question

Uno degli esempi principali utilizzati per dimostrare la potenza di MapReduce è Terasort benchmark. Ho difficoltà a comprendere le basi dell'algoritmo di ordinamento utilizzato nell'ambiente MapReduce.

Per me l'ordinamento consiste semplicemente nel determinare la posizione relativa di un elemento in relazione a tutti gli altri elementi. Quindi l'ordinamento implica il confronto di "tutto" con "tutto". Il tuo algoritmo di ordinamento medio (veloce, bolla, ...) lo fa semplicemente in modo intelligente.

Nella mia mente suddividere il set di dati in molti pezzi significa che è possibile ordinare un singolo pezzo e quindi è ancora necessario integrare questi pezzi nel set di dati 'completo' completamente ordinato. Dato il dataset di terabyte distribuito su migliaia di sistemi, mi aspetto che questo sia un compito enorme.

Quindi, come è fatto? Come funziona questo algoritmo di ordinamento MapReduce?

Grazie per avermi aiutato a capire.

Answer 1

Ecco alcuni dettagli sul Hadoop's implementation for Terasort:

TeraSort è una mappa standard/ridurre sorta, ad eccezione di un partizionamento personalizzato che utilizza un elenco ordinato di N - 1 Tasti campionati che definiscono il campo chiave per ogni ridurre . In particolare, tutte le chiavi che campionano [i - 1] < campione [i] campione [i] sono inviate per ridurre i. Ciò garantisce che l'uscita di riduzione i sia inferiore all'uscita di riduzione i + 1. "

Quindi il loro trucco è nel modo in cui determinano le chiavi durante la fase della mappa. un singolo riduttore è garantito per essere 'pre-ordinato' contro tutti gli altri riduttori.

ho trovato il riferimento carta attraverso James Hamilton's Blog Post.

Answer 2

Google Riferimento: MapReduce: Simplified Data Processing on Large Clusters

Apparso in:
OSDI'04: VI Simposio sul sistema operativo Progettazione e Realizzazione,
San Francisco, CA, dicembre 2004.

Questo link ha un riferimento PDF e HTML-Slide.

C'è anche un Wikipedia page with description con riferimenti di implementazione.

anche la critica,

David DeWitt e Michael Stonebraker, esperti pionieristici nei database paralleli e architetture niente in comune, hanno fatto alcune affermazioni controverse circa l'ampiezza dei problemi che MapReduce può essere utilizzato per. Hanno chiamato la sua interfaccia troppo a basso livello e si sono chiesti se rappresenti davvero il cambio di paradigma che i suoi sostenitori hanno affermato di essere. Sfidano le rivendicazioni di novità dei sostenitori di MapReduce, citando Teradata come un esempio di arte nota che esiste da oltre due decenni; hanno confrontato i programmatori di MapReduce con i programmatori di Codasyl, notando che entrambi "scrivono in un linguaggio di basso livello che esegue una manipolazione dei record di basso livello". L'uso dei file di input di MapReduce e la mancanza di supporto dello schema prevengono i miglioramenti delle prestazioni abilitati dalle comuni funzionalità del sistema di database come B-tree e il partizionamento hash, sebbene progetti come PigLatin e Sawzall stiano iniziando a risolvere questi problemi.

Answer 3

solo indovinare ...

Dato un insieme enorme di dati, si partizionare i dati in alcuni pezzi da lavorare in parallelo (forse per numero record di esempio, il registro 1-1000 = partizione 1, e presto).

Assegnare/programmare ciascuna partizione a un nodo particolare nel cluster.

Ogni nodo del cluster interromperà ulteriormente (mapperà) la partizione nella propria mini partizione, forse con l'ordine alfabetico della chiave. Quindi, nella partizione 1, prendi tutte le cose che iniziano con A e le metti in uscita nella mini partizione A di x. Crea una nuova A (x) se attualmente c'è già una A (x). Sostituisci x con un numero sequenziale (forse questo è il lavoro del programmatore per farlo). CioèDammi il prossimo ID unico (x).

Consegna (pianificazione) dei lavori completati dal mappatore (passaggio precedente) ai nodi del cluster "reduce". Ridurre il cluster di nodi quindi perfezionerà ulteriormente il tipo di ciascuna delle parti A (x) che si verificano quando si eseguono tutte le attività del mappatore (Impossibile iniziare a ordinare tutte le parole che iniziano con w/A quando c'è ancora la possibilità che ci sia ancora sarà un'altra mini partizione in preparazione). Output del risultato nella parzializzazione finale ordinata (ad esempio Sorted-A, Sorted-B, ecc.)

Una volta terminato, unire nuovamente la partizione ordinata in un unico set di dati. A questo punto è solo una semplice concatenazione di n file (dove n potrebbe essere 26 se si sta facendo solo A - Z), ecc.

Ci potrebbero essere passaggi intermedi tra ... Non sono sicuro:). Cioè ulteriormente mappare e ridurre dopo la fase iniziale di riduzione.

Answer 4

ho avuto la stessa domanda durante la lettura della carta MapReduce di Google. @Yuval F 's answer praticamente risolto il mio puzzle.

Una cosa che ho notato leggendo la carta è che la magia avviene nel partizionamento (dopo la mappa, prima di ridurla).

La carta utilizza hash(key) mod R come esempio di partizionamento, ma questo non è l'unico modo per suddividere i dati intermedi in attività di riduzione diverse.

Basta aggiungere condizioni al contorno per @Yuval F s' answer per renderla completa: min supponiamo (S) e Max (S) è la chiave di minima e massima della chiave tra i tasti campionati; tutte le chiavi < min (S) sono partizionate su un compito di riduzione; viceversa, tutte le chiavi> = max (S) sono partizionate per un compito di riduzione.

Non ci sono limiti rigidi sui tasti campionati, come min o max. Semplicemente, più uniformemente queste chiavi R sono distribuite tra tutte le chiavi, più "parallelo" è questo sistema distribuito e meno probabilmente un operatore di riduzione ha problemi di overflow di memoria.