MapReduce

Iordache Sergiu 332CAsergiu@rosedu.org

Agenda

• Ce e MapReduce• Programare functională• Cum funcr ionează• Toleranc ă la defecniuni• Optimizări• Implementări• Exemplu MapReduce

Ce e MapReduce?

• MapReduce – framework software pentru calcul distribuit pe arhitecturi MIMD (clustere/grid-uri)

• Google• Programare funcRională (Map t 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 “obic 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 iei ire)

Toleran©a la defecy iuni

• Exista mecanisme de tolerare a defeca 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.

• Renuni area prelucrării pentru programele care nu funcr ionează.

• Ordonarea rezultatelor• Funcn ii de combinare

Toate logo-urile sunt propietatea respectivelor companii

Implementări

?CUDAMars

Cell BEFLOSSCmapreduce-cell

NokiaFLOSSErlang + Python (jobs)

Disco

Comercial-Greenplum

+ HDFSFLOSSJavaHadoop

+ GFSPropietarC++ + Java/Python(jobs)

Google

AlteleLicene ăLimbajNume

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.html• http://wiki.apache.org/hadoop/HadoopMapReduce

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 licenc ă Creative Commons

Prezentare sub licena ă Creative Commons Attribution-Noncommercial-Share Alike 2.0

http://creativecommons.org/licenses/by-nc-sa/2.0/deed.en