# MapReduce

MapReduce è un framework software brevettato e introdotto da Google per supportare la computazione distribuita su grandi quantità di dati in cluster di computer. Il framework è ispirato alle funzioni map e reduce usate nella programmazione funzionale, sebbene il loro scopo nel framework MapReduce non sia lo stesso che nella forma originale. Le librerie MapReduce sono scritte in C++, C#, Erlang, Java, OCaml, Perl, Python, Ruby, F# e altri linguaggi di programmazione.

## Panoramica

Il framework MapReduce è composto da diverse funzioni per ogni step:
* Input Reader
* Map Function
* Partition Function
* Compare Function
* Reduce Function
* Output Writer
L'Input Reader legge i dati dalla memoria di massa, che generalmente è un file system distribuito, e divide l'input in diversi S split (tipicamente da 64 MB e 128 MB) che vengono successivamente distribuiti a M macchine di un cluster che hanno funzione di Map. L'Input Reader ha inoltre il compito di generare una coppia (chiave, valore). Le macchine di cluster vengono suddivise in N fra master e slave: un master che si occupa di individuare gli slave in idle e di assegnargli un task, N-1 slave che ricevono i task assegnati dal nodo master. In tutto vengono assegnate M task con funzione di Map e R task con funzione di Reduce. Lo slave a cui è stato assegnato un M-esimo task legge il contenuto dell'input, estrae le coppie (chiave, valore) dall'input e le passa alla funzione di Map definita dall'utente che genera zero o più coppie (chiave, valore) in uscita. Queste coppie vengono bufferizzate in memoria. Periodicamente le coppie bufferizzate vengono memorizzate a disco e partizionate in R sezioni dalla partition fuction. Gli indirizzi delle sezioni partizione vengono poi passate al nodo master che è responsabile di girare le locazioni agli slave che processano funzioni di riduzione. Tra lo slave con funzione di Map e quello con funzione di Reduce vengono riordinate tutte le coppie in modo da trovare quelle che puntano allo stesso valore che spesso hanno anche la stessa chiave. Trovate quelle che puntano allo stesso valore con la funzione di comparazione si fa un'operazione di merge. Per ogni chiave viene associato uno slave con funzione di Reduce che iterando su tutte le chiavi, prende i valori con la stessa chiave e li passa alla funzione di Reduce definita dall'utente che genera zero o più uscite. L'Output Writer avrà il compito di scrivere i risultati in memoria di massa e una volta finiti tutti i task di Map e Reduce il master avrà il compito di attivare l'applicativo utente.
Il sistema di runtime si occupa del partitioning dei dati in ingresso, dello scheduling dell'esecuzione su un set di macchine e della gestione della comunicazione tra di esse. Il vantaggio della Map Reduce è che permette una elaborazione distribuita delle operazioni di mappatura e riduzione. Fornendo ogni operazione di map indipendente dalle altre, tutte le map possono essere eseguite in parallelo - sebbene nella pratica ciò è limitato dalla sorgente dati e/o dal numero di CPU vicine a quel dato. Alla stessa maniera, una serie di "riduttori" può eseguire la fase di riduzione - tutto quello che è richiesto è che le uscite della map la quale condivide la stessa chiave sia presentata allo stesso riduttore, allo stesso tempo. Mentre questo processo può spesso apparire inefficiente comparato agli algoritmi che sono più sequenziali, MapReduce può essere applicato a maggiori quantità di dati che i server possono gestire comodamente - una grande server farm può usare MapReduce per ordinare petabyte di dati in sole poche ore. Il parallelismo offre anche la possibilità di recuperare dati dal parziale fallimento di server o di dispositivi di archiviazione durante l'operazione se qualche map o reduce fallisce il lavoro può essere riprogettato, assumendo che i dati in entrata siano ancora disponibili.