MapReduce: diferència entre les revisions
Contingut suprimit Contingut afegit
Recuperant 1 fonts i marcant-ne 0 com a no actives.) #IABot (v2.0.8.6 |
addició de l'apartat dataflow |
||
Línia 10:
Hi ha[[Biblioteca_informàtica | llibreries de funcions]] MapReduce per a molts [[llenguatge de programació |llenguatges de programació]], amb diversos nivells d'optimització. Una de les més populars és la d'Apache Hadoop. El nom MapReduce inicialment feia referència a la tecnologia privativa de [[Google]], però fa temps que s'utilitza com a terme genèric.
== Dataflow ==
L'arquitectura de MapReduce s'adhereix al principi open/closed, en el qual el codi es divideix en entitats "tancades" no modificables i entitats "obertes" extensibles. L'entitat no modificable del MapReduce es troba a l'ordenació. Per la seva part, les entitats extensibles són:
* Lector d'''inputs''
* Funció ''Map''
* Funció de partició
* Funció de comparació
* Funció ''reduce''
* ''Output writer''
=== Lector d'''inputs'' ===
El lector d'<nowiki/>''inputs'' divideix l'<nowiki/>''input'' perquè el framework assigni cadascuna d'aquestes divisions a una funció ''Map'' diferent. El lector d'''inputs'' llegeix les dades de memòria i genera parelles clau/valor.
Per exemplificar, el lector d'''inputs'', llegeix un directori on es troben arxius de text i retorna cada línia en forma de [[Registre (estructura de dades)|registre]].
=== Funció ''Map'' ===
La funció ''Map'' pren una sèrie de parelles clau/valor i genera zero o més parelles clau/valor de sortida. Els tipus d'entrada i sortida del ''Map'' poden ser (i sovint ho són) diferents entre si.
Si l'aplicació està fent un recompte de paraules, la funció ''Map'' dividiria la línia en paraules i emetria un parell clau/valor per a cada paraula. Cada parell de sortida contindria la paraula com a clau i el nombre d'instàncies d'aquesta paraula en la línia com a valor.
=== Funció de partició ===
La funció de partició de l'aplicació assigna cadascun dels ''outputs'' de la funció ''Map'' a un ''reducer'' particular. La funció de partició rep la clau i el nombre de ''reducers'' i retorna l'índex del ''reducer'' desitjat.
Entre les etapes de ''Map'' i ''reduce'', les dades són passades per l'algorisme de ''shuffle'' per ser desplaçades des del node del ''Map'' que els va produir fins al fragment en el qual seran passades pel ''reduce''. Aquest ''shuffle'' pot trigar més que la computació en sí, depenent de l'amplada de banda de la xarxa, la velocitat de la CPU, les dades produïdes i el temps emprat en els càlculs de ''Map'' i ''reduce''.
=== Funció de comparació ===
L'''input'' per a cada ''reduce'' s'extreu de la màquina on es va executar el ''Map'' i s'ordena utilitzant la funció de comparació de l'aplicació.
=== Funció ''reduce'' ===
El framework crida la funció ''reduce'' de l'aplicació tantes vegades com claus úniques hi hagi en l'ordenament. La funció ''Reduce'' itera per cadascun dels valors associats amb aquesta clau i poden produir zero o més sortides.
En l'exemple del recompte de paraules, la funció ''Reduce'' pren els valors d'entrada, els suma i genera una única sortida de la paraula i la suma final.
=== ''Output writer'' ===
L'''output writer'' escriu la sortida de la funció ''Reduce'' en memòria.
== Referències ==
| |||