Qual è lo scopo della fase di shuffling e ordinamento nel riduttore in Map Reduce Programming?

In Map Ridurre la programmazione la fase di riduzione ha shuffling, ordinamento e riduzione come le sue sottosezioni. L’ordinamento è un affare costoso.

Qual è lo scopo della fase di shuffling e ordinamento nel riduttore in Map Reduce Programming?

Prima di tutto il shuffling è il processo di trasferimento dei dati dai mappatori ai riduttori, quindi penso sia ovvio che sia necessario per i riduttori, poiché altrimenti non sarebbero in grado di avere alcun input (o input da ogni mappatore ). La mischia può iniziare anche prima che la fase della mappa sia finita, per risparmiare un po ‘di tempo. Ecco perché è ansible visualizzare uno stato di riduzione superiore allo 0% (ma inferiore al 33%) quando lo stato della mappa non è ancora al 100%.

Sorting consente di risparmiare tempo per il riduttore, aiutandolo a distinguere facilmente quando deve iniziare una nuova attività di riduzione. Inizia semplicemente una nuova attività di riduzione, quando la successiva chiave nei dati di input ordinati è diversa dalla precedente, per dirla semplicemente. Ogni attività di riduzione prende un elenco di coppie chiave-valore, ma deve chiamare il metodo reduce () che accetta un input chiave (valore), quindi deve raggruppare i valori per chiave. È facile farlo, se i dati di input sono pre-ordinati (localmente) nella fase mappa e semplicemente si uniscono-ordinati nella fase di riduzione (poiché i riduttori ottengono i dati da molti mappatori).

Partitioning , che hai menzionato in una delle risposte, è un processo diverso. Determina in quale riduttore verrà inviata una coppia (chiave, valore), uscita della fase mappa. Il partizionatore predefinito utilizza un hashing sulle chiavi per distribuirle alle attività di riduzione, ma è ansible sovrascriverle e utilizzare il proprio partizionatore personalizzato.

Una grande fonte di informazioni per questi passaggi è questo tutorial di Yahoo .

Una bella rappresentazione grafica di questo è il seguente (shuffle è chiamato “copia” in questa figura):

inserisci la descrizione dell'immagine qui

Si noti che lo shuffling e l’ sorting non vengono eseguiti affatto se si specificano riduttori di zero (setNumReduceTasks (0)). Quindi, il lavoro MapReduce si arresta alla fase della mappa e la fase della mappa non include alcun tipo di ordinamento (quindi anche la fase della mappa è più veloce).

AGGIORNAMENTO: Dato che stai cercando qualcosa di più ufficiale, puoi anche leggere il libro di Tom White “Hadoop: The Definitive Guide”. Ecco la parte interessante per la tua domanda.
Tom White è stato un committer Apache Hadoop da febbraio 2007 ed è membro della Apache Software Foundation, quindi credo sia abbastanza credibile e ufficiale …

Rivediamo le fasi chiave del programma Mapreduce.

La fase della mappa viene eseguita dai mappatori. I mapping vengono eseguiti su coppie chiave / valori di input non selezionati. Ogni mapper emette zero, uno o più coppie chiave / valore di uscita per ogni coppia chiave / valore di input.

La fase di combinazione viene eseguita da combinatori. Il combinatore dovrebbe combinare coppie chiave / valore con la stessa chiave. Ogni combinatore può eseguire zero, una volta o più volte.

La fase shuffle e sort è fatta dal framework. I dati di tutti i mappatori sono raggruppati per la chiave, suddivisi tra riduttori e ordinati per chiave. Ogni riduttore ottiene tutti i valori associati alla stessa chiave. Il programmatore può fornire funzioni di confronto personalizzate per l’ordinamento e un partizionatore per la suddivisione dei dati.

Il partizionatore decide quale riduttore otterrà una particolare coppia di valori chiave.

Il riduttore ottiene coppie ordinate / [lista valori], ordinate per chiave. L’elenco valori contiene tutti i valori con la stessa chiave prodotta dai mappatori. Ogni riduttore emette zero, una o più coppie chiave / valore di uscita per ogni coppia chiave / valore di ingresso .

Dai un’occhiata a questo articolo di javacodegeeks di Maria Jurcovicova e all’articolo di mssqltips di Datta per una migliore comprensione

Di seguito l’immagine tratta dall’articolo di safaribooksonline

inserisci la descrizione dell'immagine qui

Ho pensato di aggiungere alcuni punti mancanti nelle risposte precedenti. Questo diagramma preso da qui indica chiaramente cosa sta realmente accadendo.

inserisci la descrizione dell'immagine qui

Se ripeto il vero scopo di

  • Dividi: migliora l’elaborazione parallela distribuendo il carico di elaborazione su diversi nodes (Mapper), il che farebbe risparmiare tempo di elaborazione complessivo.

  • Combina: riduce l’output di ciascun mappatore. Farebbe risparmiare tempo per lo spostamento dei dati da un nodo a un altro.

  • Sort (Shuffle & Sort): rende facile per il run-time pianificare (spawn / start) nuovi riduttori, mentre mentre si passa attraverso l’elenco degli elementi ordinati, ogni volta che la chiave corrente è diversa dalla precedente, può generare un nuovo riduttore .

Alcuni dei requisiti di elaborazione dei dati non hanno bisogno di ordinare affatto. Syncsort aveva reso selezionabile l’ordinamento in Hadoop. Ecco un bel blog da loro su come ordinare. Il processo di spostamento dei dati dai mappatori ai riduttori è chiamato shuffling, controlla questo articolo per maggiori informazioni sullo stesso.

Shuffling è il processo mediante il quale i dati intermedi dai mapper vengono trasferiti a 0,1 o più riduttori. Ogni riduttore riceve 1 o più chiavi e i relativi valori associati in base al numero di riduttori (per un carico bilanciato). Inoltre i valori associati a ogni chiave sono ordinati localmente.

Ho sempre pensato che fosse necessario poiché l’output del mapper è l’input per il riduttore, quindi è stato ordinato in base allo spazio delle chiavi e quindi suddiviso in bucket per ciascun input del riduttore. Volete assicurarvi che tutti gli stessi valori di una chiave finiscano nello stesso secchio andando al riduttore in modo che vengano ridotti insieme. Non ha senso inviare K1, V2 e K1, V4 a riduttori diversi in quanto devono essere uniti per essere ridotti.

Ho provato a spiegarlo nel modo più semplice ansible

Ci sono solo due cose che MapReduce fa NATIVAMENTE: Ordinamento e (implementato per ordinamento) GroupBy scalabile.

La maggior parte delle applicazioni e dei design pattern su MapReduce sono costruiti su queste due operazioni, che sono fornite da shuffle e sort.

Questa è una buona lettura. Spero che sia d’aiuto. In termini di ordinamento sei preoccupante, penso che sia per l’operazione di fusione nell’ultima fase di Map. Quando l’operazione mappa è terminata e occorre scrivere il risultato sul disco locale, verrà eseguita una multi-unione sulle divisioni generate dal buffer. E per un’operazione di unione, l’ordinamento di ciascuna partizione in avanzato è utile.

Bene, in Mapreduce ci sono due frasi importanti chiamate Mapper e riduttore entrambe troppo importanti, ma il Riduttore è obbligatorio. In alcuni programmi i riduttori sono opzionali. Ora vieni alla tua domanda. Mischiare e ordinare sono due operazioni importanti in Mapreduce. Il primo framework Hadoop utilizza dati strutturati / non strutturati e separa i dati in Chiave, Valore.

Ora il programma Mapper separa e organizza i dati in chiavi e valori da elaborare. Genera valori chiave 2 e valore 2. Questi valori dovrebbero essere elaborati e riordinati nell’ordine corretto per ottenere la soluzione desiderata. Ora questo shuffle e lo smistamento sono fatti nel tuo sistema locale (il Framework si occupa di esso) e processano nel sistema locale dopo che il framework dei processi pulisce i dati nel sistema locale. Ok

Qui usiamo il combinatore e la partizione anche per ottimizzare questo shuffle e il processo di ordinamento. Dopo una corretta sistemazione, tali valori chiave passano a Reducer per ottenere l’output del Cliente desiderato. Infine, Reducer ottiene l’output desiderato.

K1, V1 -> K2, V2 (scriveremo il programma Mapper), -> K2, V ‘(qui shuffle e soft i dati) -> K3, V3 Genera l’uscita. K4, V4.

Si prega di notare che tutti questi passaggi sono solo operazioni logiche, non modificare i dati originali.

La tua domanda: qual è lo scopo della fase di shuffling e ordinamento nel riduttore in Map Reduce Programming?

Risposta breve: elaborare i dati per ottenere l’output desiderato. Mischiare è aggregare i dati, ridurre è ottenere l’output previsto.