MapReduce

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.

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, 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.

Vista general

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 el denominem 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:

1. 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.
2. 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.
3. 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 mapeig i reducció. Si les operacions de mapeig 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:

1. 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.
2. Executar el codi Map() proporcionat: s’executa un Map() per cada clau K1 i genera outputs organitzats per la clau K2.
3. “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.
4. Executar el codi de Reduce(): s’executa Reduce() per cada clau K2 proporcionada.
5. 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 d'inputs
• Funció Map
• Funció de partició
• Funció de comparació
• Funció reduce
• Output writer

Lector d'inputs

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 d'inputs, 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ó

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.

Consideracions de Rendiment

No es garanteix que els programes MapReduce siguin ràpids. El principal avantatge d'aquest model de programació és explotar l'operació shuffle optimitzada de la plataforma, i només haver d'escriure les parts Map i Reduce del programa. No obstant això, en la pràctica, l'autor d'un MapReduce ha de tenir en compte el shuffle, ja que la quantitat de dades escrites per la funció Map pot tenir un gran impacte en el rendiment i l'escalabilitat.

La majoria d'implementacions de l'algorisme de MapReduce, requereixen escriure a memòria totes les comunicaciones, és per això que el cost de comunicació sovint domina al cost de computació. Per l'autor de l'algorisme és essencial equilibrar els dos costos.

Per tal de calcular el rendiment de MapReduce, cal tenir en compte la complexitat del mapping, el shuffle, l'ordenació (agrupació per la clau) i el reduce. La quantitat de dades produïdes en l'etapa de la funció de map, és un paràmetre clau que ens indicarà on es trobarà la major part del cost computacional (map o reduce). La reducció inclou l'ordenació que té una complexitat no lineal. Per tant, les divisions en grups petits de les dades redueixen el temps de classificació, però fins a un límit, ja que un gran nombre de reductors pot ser poc pràctic.

Per als processos que es completen ràpidament, i en els quals les dades caben en la memòria principal d'una sola màquina o d'un petit clúster, l'ús d'un framework MapReduce no sol ser eficaç. Aquests frameworks estan dissenyats per a recuperar-se de la pèrdua de nodes sencers durant la computació, és per això que escriuen els resultats intermedis en memòria distribuïda. Aquesta recuperació de fallades és costosa, i només resulta rendible quan el còmput implica molts ordinadors i un llarg temps d'execució del còmput. Una tasca que es completa en segons només pot reiniciar-se en cas d'error, i la probabilitat que almenys una màquina falli creix ràpidament amb la grandària del clúster. En aquesta mena de problemes, les implementacions que mantenen totes les dades en memòria i simplement reinicien un càlcul en cas de fallada d'un node o -quan les dades són prou petits- les solucions no distribuïdes seran sovint més ràpides que un sistema MapReduce.

Distribució i Fiabilitat

L'arquitectura MapReduce aconsegueix fiabilitat desglossant una sèrie d'operacions al conjunt de dades per cada node de la xarxa. S'espera que cada node faci 'feedback' de forma periòdica amb la tasca completada i amb actualitzacions de l'estat. Si un node no retorna cap informació i, per tant, roman en silenci per un període major al d'un cert interval, el Node Màster o node principal registra a aquest node com a mort. Quan això succeeix, el mateix node principal envia la part de la tasca assignada al node actualment mort a altres nodes operatius. Les operacions individuals utilitzen operacions atòmiques per a donar nom als outputs. Això, es fa per a comprovar que no hi ha processos paral·lels conflictius entre ells.

Quan es reanomenen els arxius, també és possible copiar-los a un altre nom, a més del nom de la tasca.

Les operacions de reducció funcionen aproximadament de la mateixa forma. Com té pitjors propietats per a paral·lelitzar operacions, el node principal intenta fer la reducció d'operacions en el mateix node o al mateix grup de nodes on trobem el node que conté les dades requerides per a operar. És desitjable que tingui aquesta propietat, ja que així es conserva l'amplada de banda a través de la xarxa troncal del centre de dades.

Les implementacions no sempre tenen una alta fiabilitat. Per exemple, a les versions antigues de Hadoop el "NameNode" era un punt únic de falla per al sistema d'arxius. Les versions posteriors de Hadoop ja tenen una alta disponibilitat amb tolerància davant la falla del "NameNode"

Usos

Per norma general, s'utilitza MapReduce en aquells problemes de Computació concurrent entre els quals es troben involucrats grans datasets que han de ser processats per una gran quantitat de computadores (nodes), als que ens referim de forma col·lectiva com a clústers (sempre que tots els nodes es trobin a la mateixa xarxa d'àrea local i utilitzin el mateix hardware), o a graelles de càlcul (si els nodes es comporten de forma distribuïda al llarg de zones geogràfiques o administratives extenses, i que generalment posseeixen un hardware més heterogeni). El processament paral·lel es pot donar tant amb l'ús de dades emmagatzemades tant en sistemes de fitxers (no estructurats) o en una database (estructurats). Per aquesta raó s'usa en aplicacions que posseeixen dades a gran escala, tals com les aplicacions paral·leles, la indexació web, data mining i la simulació científica.