MapReduce

Questa voce o sezione sull'argomento informatica è priva o carente di note e riferimenti bibliografici puntuali.

Commento: Un folto elenco di collegamenti esterni che dovrebbero essere passati a note puntuali

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.

Voci correlate

Apache Hadoop

Altri progetti

Wikimedia Commons

Wikimedia Commons contiene immagini o altri file su MapReduce

Collegamenti esterni

Articoli

(EN) "Interpreting the Data: Parallel Analysis with Sawzall" — paper by Rob Pike, Sean Dorward, Robert Griesemer, Sean Quinlan; from Google Labs
(EN) "Evaluating MapReduce for Multi-core and Multiprocessor Systems" — paper by Colby Ranger, Ramanan Raghuraman, Arun Penmetsa, Gary Bradski, and Christos Kozyrakis; from Stanford University
(EN) "Why MapReduce Matters to SQL Data Warehousing" — analysis related to the August, 2008 introduction of MapReduce/SQL integration by Aster Data Systems and Greenplum
(EN) "MapReduce for the Cell B.E. Architecture" — paper by Marc de Kruijf and Karthikeyan Sankaralingam; from University of Wisconsin–Madison
(EN) "Mars: A MapReduce Framework on Graphics Processors" — paper by Bingsheng He, Wenbin Fang, Qiong Luo, Naga K. Govindaraju, Tuyong Wang; from Hong Kong University of Science and Technology; published in Proc. PACT 2008. It presents the design and implementation of MapReduce on graphics processors.
(EN) "Map-Reduce-Merge: Simplified Relational Data Processing on Large Clusters" — paper by Hung-Chih Yang, Ali Dasdan, Ruey-Lung Hsiao, and D. Stott Parker; from Yahoo and UCLA; published in Proc. of ACM SIGMOD, pp. 1029–1040, 2007. (This paper shows how to extend MapReduce for relational data processing.)
(EN) FLuX: the Fault-tolerant, Load Balancing eXchange operator from UC Berkeley provides an integration of partitioned parallelism with process pairs. This results in a more pipelined approach than Google's MapReduce with instantaneous failover, but with additional implementation cost.
(EN) "A New Computation Model for Rack-Based Computing" — paper by Foto N. Afrati; Jeffrey D. Ullman; from Stanford University; Not published as of Nov 2009. This paper is an attempt to develop a general model in which one can compare algorithms for computing in an environment similar to what map-reduce expects.
(EN) Yi Shan Bo Wang, Jing Yan, Yu Wang, Ningyi Xu e Huazhong Yang, FPMR: MapReduce framework on FPGA - Published in: FPGA '10 Proceedings of the 18th annual ACM/SIGDA international symposium on Field programmable gate arrays, su portal.acm.org, pp. 93 - 102. URL consultato il 13 ottobre 2022 (archiviato dall'url originale il 23 febbraio 2013).
(EN) "Tiled-MapReduce: Optimizing Resource Usages of Data-parallel Applications on Multicore with Tiling" -- paper by Rong Chen, Haibo Chen and Binyu Zang from Fudan University; published in Proc. PACT 2010. It presents the Tiled-MapReduce programming model which optimizes resource usages of MapReduce applications on multicore environment using tiling strategy.
(EN) "Scheduling divisible MapReduce computations " -- paper by Joanna Berlińska from Adam Mickiewicz University and Maciej Drozdowski from Poznan University of Technology; Journal of Parallel and Distributed Computing 71 (2011) 450-459, doi:10.1016/j.jpdc.2010.12.004. It presents scheduling and performance model of MapReduce.

Libri

(EN) Jimmy Lin and Chris Dyer. "Data-Intensive Text Processing with MapReduce" Archiviato il 10 febbraio 2011 in Internet Archive. (manuscript)

Educational courses

(EN) Cluster Computing and MapReduce course from Google Code University contains video lectures and related course materials from a series of lectures that was taught to Google software engineering interns during the Summer of 2007.
(EN) MapReduce in a Week course from Google Code University contains a comprehensive introduction to MapReduce including lectures, reading material, and programming assignments.
(EN) MapReduce course Archiviato il 30 agosto 2009 in Internet Archive., taught by engineers of Google Boston, part of 2008 Independent Activities Period at MIT.