MapReduce Flashcards
Cos’è MapReduce?
MapReduce è un paradigma di programmazione e un modello di calcolo che viene utilizzato per elaborare ed analizzare grandi quantità di dati distribuiti su un cluster di computer.
Quali sono le fasi di un sistema MapReduce?
l concetto alla base di MapReduce si basa su due fasi principali: la fase di “map” e la fase di “reduce”. Ecco come funzionano:
Fase di Map: Durante questa fase, i dati vengono suddivisi in piccoli frammenti e distribuiti a vari nodi di calcolo. Ogni nodo applica una funzione di mappatura (il "mapper") ai propri dati locali. Questa funzione prende in input un singolo dato e lo trasforma in una serie di coppie chiave-valore. Queste coppie vengono quindi raggruppate in base alla chiave comune. Fase di Shuffle e Sort: Dopo la fase di map, i dati sono suddivisi in base alle chiavi e distribuiti tra i nodi di calcolo in modo che tutte le coppie chiave-valore con la stessa chiave vengano inviate allo stesso nodo. Questa fase è chiamata "shuffle". Successivamente, i dati vengono ordinati in base alle chiavi per prepararsi per la fase successiva. Fase di Reduce: Durante questa fase, i dati raggruppati vengono elaborati ulteriormente. I dati di una stessa chiave vengono passati ad una funzione di riduzione (il "reducer"), che combina le coppie chiave-valore e produce un insieme più piccolo di risultati. Questi risultati rappresentano l'output finale dell'elaborazione.
Quanti Map e Quanti reduce utilizzare?
Il numero di fasi di “Map” e “Reduce” dipende dall’applicazione specifica e dai dati da elaborare. In un’applicazione MapReduce, puoi avere più fasi di “Map” seguite da una o più fasi di “Reduce”, a seconda delle esigenze dell’elaborazione dei dati.
In generale, l’obiettivo è suddividere il lavoro in modo efficace tra le diverse fasi, in modo che il sistema possa sfruttare al massimo le capacità di elaborazione parallela offerte dai cluster di computer.
Quali sono i miglioramenti che possono essere fatti nel MapReduce?
- Backup Task: Workers lenti possono comportare un aumento nel completamento di un job, quindi
una soluzione può essere spawnare copie di quel task, così che il primo che finisce vince. - Combiners: un Map Task solitamente produce coppie di chiave-valori con chiavi diverse, ma anche
con la stessa chiave, quindi per salvare un tempo di comunicazione in rete, si possono utilizzare dei
costrutti (combiners) che combinano le stesse chiavi prima di mandare l’output - Funzione di partizione: si vuole controllare quante chiavi vengono partizionate, e solitamente si usa
la funzione hash(k)modR per questo. A volte è meglio effettuare l’override di questa, ed usare
hash(hostname(URL))modR
Quali sono gli utilizzi di MapReduce?
Il paradigma MapReduce NON è una soluzione ad ogni problema.
Infatti ha senso nel momento in cui stiamo usando una grossa mole di dati che raramente viene aggiornata.
L’obiettivo principale per cui Google ha implementato MapReduce era per eseguire una grossa
elaborazione matrice-vettore per il calcolo di PageRank.
Quindi i compiti erano così suddivisi tra i task:
* Map Function: elaborava un chunk di M (matrix). Produceva le chiavi-valori (i, mij, vj), dove “i”
rappresenta l’indice iesimo dell’elemento del vettore risultate, e gli altri due l’elemento della
matrice e il vettore di partenza.
* Reduce Function: effettua la somma di tutti i valori associati alla stessa chiave “i”. Il risultato sarà la
coppia (i,xi)