Map Reduce

MapReduce Iordache Sergiu 332CA [email protected]

Agenda • • • • • • •

Ce e MapReduce Programare functională Cum funcționează Toleranță la defecțiuni Optimizări Implementări Exemplu MapReduce

Ce e MapReduce? • MapReduce – framework software pentru calcul distribuit pe arhitecturi MIMD (clustere/grid-uri) • Google • Programare funcțională (Map și Reduce) • Procesare pe seturi foarte mari de date • Mecanisme de asigurare a unui calcul corect

Remember PP • Map – aplică o funcție unei liste • Reduce – procesează o listă obținând un rezultat • Fără efecte laterale! • Rezultă paralelizare maximă.

Cum funcționeaza? • Tipic rulat pe sute/mii de calculatoare “obișnuite” • Un master planifica workerii • De obicei mult mai multe task-uri decât mașini(oferă diverse avantaje)

Cum funcționeaza?(2) • Datele sunt structurate in perechi (cheie, valoare) • Map(k_in, val) -> listă(k_out, val_intermediară) • Reduce(k_out, listă(val_intermediare)) -> listă(valori ieșire)

Toleranța la defecțiuni • Exista mecanisme de tolerare a defecțiunilor • Sanse foarte mici sa de defecteze master-ul(de obicei nu se tratează cazul) • Daca se defectează worker-ul se execută task-urile in progres sau cele efectuate.

Optimizări • Duplicarea task-urilor spre finalul procesării. • Localizarea eficentă a datelor în sistemul distribuit. • Renunțarea prelucrării pentru programele care nu funcționează. • Ordonarea rezultatelor • Funcții de combinare

Implementări Licență

Nume

Limbaj

Google Hadoop

C++ + Propietar Java/Python(jobs) Java FLOSS

Greenplum

-

Comercial

Disco

Erlang + Python (jobs) C

FLOSS

Nokia

FLOSS

Cell BE

CUDA

?

mapreducecell Mars

Altele + GFS + HDFS

Toate logo-urile sunt propietatea respectivelor companii

Exemplul clasic MapReduce map(String name, String document): // key: document name // value: document contents for each word w in document: EmitIntermediate(w, 1); reduce(String word, Iterator partialCounts): // key: a word // values: a list of aggregated partial counts int result = 0; for each v in partialCounts: result += ParseInt(v); Emit(result);

Intrebări?

Link-uri

• http://en.wikipedia.org/wiki/MapReduce • http://labs.google.com/papers/mapreduce.htm • http://wiki.apache.org/hadoop/HadoopMapRed

Surse poze • • • • • •

(3) http://www.flickr.com/photos/mybloodyself/501572092/ (4) http://www.flickr.com/photos/88319047@N00/3148384136/ (5,6,7) http://www.flickr.com/photos/antichrist/3427853501/ (8,9) http://www.flickr.com/photos/bcostin/94192319/ (13) http://www.flickr.com/photos/oberazzi/318947873/ (1,2,12,14,15) http://www.flickr.com/photos/gavlart/2475205408/ Poze sub licență Creative Commons Prezentare sub licență Creative Commons Attribution-NoncommercialShare Alike 2.0 http://creativecommons.org/licenses/by-nc-sa/2.0/deed.en