MapReduce és un model de programació i d'implementació per a processar i generar jocs de dades grans, amb un algorisme paral·lel i distribuït, en un clúster.MapReduce: Simplified Data Processing on Large Clusters
Un programa MapReduce es compon d'un procediment Map() que efectua el filtrat i ordenat (per exemple ordenar estudiants pel primer cognom en cues, amb una cua per cognom) i un procediment Reduce(), que fa l'operació d'agregació (com, per exemple, comptar el nombre d'estudiants a cada cua, obtenint-ne la freqüència dels cognoms). El "Sistema MapReduce" (també conegut com a infraestructura o framework) orquestra el procés serialitzant (marshalling en anglès) els servidors distribuïts, executant diverses tasques en paral·lel, gestionant les comunicacions de transferència de dades entre les diverses parts del sistema i proporcionant redundància i tolerància a errors.
El model s'inspira en les funcions map i reduce usades habitualment en la programació funcional,"Our abstraction is inspired by the map and reduce primitives present in Lisp and many other functional languages." -"MapReduce: Simplified Data Processing on Large Clusters", by Jeffrey Dean and Sanjay Ghemawat; from Google Research tot i que el seu propòsit dins el framework MapReduce no és el mateix que en la seva forma original. Les contribucions clau del framework MapReduce no són específicament les funcions map i reduce, sinó l'escalabilitat i la tolerància a errors que n'obtenen les aplicacions en optimitzar-se el motor d'execució un sol cop. Així, una implementació MapReduce d'un sol fil d'execució, com MongoDB, no acostuma a ser gaire més ràpida que la implementació "no MapReduce" habitual i cal implementar-ho en forma multi-fil per a notar-ne la millora. El benefici del model MapReduce es nota sobretot quan s'utilitza l'optimització d'execució distribuïda (que redueix els costos de comunicació de xarxa) i la tolerància a errors. Optimitzar el cost de les comunicacions de xarxa és essencial per a un bon algorisme MapReduce.
Hi ha llibreries de funcions MapReduce per a molts 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.
El map reduce és un marc de treball dedicat al processament de problemes paral·lels amb un voluminós nombre de dades fent servir una gran quantitat de nodes (ordinadors). Aquest conjunt d'ordinadors s'anomena clúster quan tots es troben en la mateixa xarxa local i fan servir un hardware similar. Quan els nodes es comparteixen a través de sistemes distribuïts geomètricament i administrativament els anomenen graella. El processament de les dades es pot dur a terme tant en una base de dades (estructurada) com en un conjunt de dades emmagatzemades en un sistema d'arxius (no estructurats).
El sistema MapReduce està format per tres operacions: Map: cada node aplica la funció map sobre les dades locals i escriu l'output en un emmagatzemament temporal. Un node mestre s'assegura que només es processi una còpia de l'input data. Shuffle: els nodes redistribueixen les dades basant-se en les claus de sortida de manera que totes les dades corresponents a una clau estiguin localitzades en el mateix node. Reduce: cada node processa cada grup de dades resultants per clau en paral·lel.
El que permet MapReduce és fer el processament distribuït de les operacions de mapatge i reducció. Si les operacions de mapatge són independents les unes amb les altres, els maps es poden executar en paral·lel tot i que hi ha una limitació determinada per nombre de fonts de dades independents i el nombre de CPUs. De la mateixa manera, el conjunt de “reductors” poden realitzar la fase de reducció sempre que la fase de reducció sigui associativa o que totes les sortides de l'operació del map, que comparteixen la mateixa clau, es presentin en el mateix reductor, en el mateix temps. Tot i que aquest procés sol ser ineficient comparat amb altres algoritmes més seqüencials (ja que s'han d'executar múltiples instàncies del procés de reducció), el MapReduce pot ser aplicat sobre conjunts de dades amb un volum superior al que pot controlar un únic servidor bàsic. El paral·lelisme també ofereix la possibilitat de recuperar-se d'una falla parcial dels servidors o de l'emmagatzematge durant una operació, si un mapeig o un reductor fallar el treball es pot ser reprogramat. El Map-Reduce també es pot dur a terme amb 5 passes:
Preparar l'entrada de Map(): el sistema designa els processadors de Map, assigna la clau d'entrada K1 amb la que cada processador treballarà i proporciona les dades d'entrada associades a cada clau. Executar el codi Map() proporcionat: s'executa un Map() per cada clau K1 i genera outputs organitzats per la clau K2. “Barrejar” el resultat de Map per Reduir els processadors: el sistema MapReduce assigna processadors, una clau K2 per cada processador i proporciona al processador totes les claus associades a les dades generades pel Map. Executar el codi de Reduce(): s'executa Reduce() per cada clau K2 proporcionada. Produir el resultat final: el sistema MapReduce recull tots els outputs i els ordena per clau K2 per produir el resultat final.
Aquests 5 passos es poden executar en seqüencial, un darrere l'altre, encara que en la pràctica es poden intercalar sempre que el resultat final no es vegi afectat.
En moltes situacions, les dades d'entrada han estat ja prèviament distribuïdes entre els diferents servidors podent simplificar el primer pas assignant els servidors Map al processament de les dades d'entrada. De la mateixa manera, el pas tres podria ser accelerat assignant els processadors de reducció que estiguin els més propers possibles a les dades generades al mapa que han de processar.
Logical view No tots els processos poden ser abordats des del framework MapReduce. Concretament, són abordables només aquells que es poden disgregar en les operacions de map() i de reduce() i això és important a l'hora de poder triar aquest framework per resoldre un problema.
Les funcions Map() i Reduce() de MapReduce estan definides ambdues respecte a dades estructurades en tuples de tipus (clau, valor).
Funció Map() La funcio Map() pren un parell de dades amb un tipus en un domini de dades i retorna una llista de parelles en un domini diferent:
Map(k1,v1) → list(k2,v2)
La funció Map() s'encarrega del mapeig es aplicada en paral·lel a cada parella (de clau k1) del conjunt de dades d'entrada. Això produeix una llista de parells (de clau k2) per a cada crida. Després d'això, el framework del MapReduce recull totes les parelles amb la mateixa clau (k2) de totes les llistes i les agrupa, creant un grup per a cada clau. Des del punt de vista arquitectural el node màster pren l'input, el divideix en petites peces o problemes de menor identitat, i els distribueix als anomenats worker nodes. Un worker node pot tornar a subdividir, donant lloc a una estructura arbòria. El worker node processa el problema i passa la resposta al node mestre.
Funció Reduce() Aleshores, la funció Reduce() s'aplica en paral·lel a cada grup, i al mateix temps produeix una col·lecció de valors en el mateix domini.
Reduce(k2, list (v2)) → list((k3, v3))
Cada crida a la funció Reduce() normalment produeix un parell de valors de clau o un retorn buit, encara que una crida pot retornar més d'una parella de clau-valor. Els retorns de totes les crides es recullen com a llista de resultats desitjada.
Així doncs, el framework de MapReduce transforma una llista de parelles (clau, valor) en una altra llista de parelles (clau, valor). Aquest comportament és diferent de la combinació típica de programació funcional i mapa de reducció, que accepta una llista de valors arbitraris i retorna un únic valor que combina tots els valors retornats pel mapa.
És necessari però no suficient tenir implementacions del mapa i reduir abstraccions per implementar MapReduce. Les implementacions distribuïdes de MapReduce requereixen un mitjà per connectar els processos que realitzen les fases Map i Reduce. Aquest pot ser un sistema de fitxers distribuït. Hi ha altres opcions possibles, com ara la transmissió directa dels mappers als reductors, o que els processadors de mapeig ofereixin els seus resultats als reductors que els consulten.
Exemples Recompte de paraules L'exemple canònic de MapReduce compta l'aparició de cada paraula en un conjunt de documents: function map(String name, String document): // name: document name // document: document contents for each word w in document: emit (w, 1)
function reduce(String word, Iterator partialCounts): // word: a word // partialCounts: a list of aggregated partial counts sum = 0 for each pc in partialCounts: sum += pc emit (word, sum) Aquí, cada document es divideix en paraules, i cada paraula es compta amb la funció map() utilitzant la paraula com a clau de resultat. El framework agrupa tots els parells amb la mateixa clau i els introdueix a la mateixa crida per reduir. Per tant, aquesta funció només necessita sumar tots els seus valors d'entrada per trobar les aparences totals d'aquesta paraula.
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 dinputs Funció Map Funció de partició Funció de comparació Funció reduce Output writer=== Lector dinputs === El lector d'inputs divideix l'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 dinputs, llegeix un directori on es troben arxius de text i retorna cada línia en forma de 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ó Linput 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.
Consideracions de Rendiment