elMeu blog

Què és realment MapReduce ?

Des de fa uns anys paraules com ara MapReduce, BigTable, GoogleFileSystem o Google Batch Queue estan prenent protagonisme. Aquestes representen un nou paradigma tecnològic del qual podriem dir-ne que Google n'es el principal creador.

Totes aquestes tecnologies s'ha anat pensant, modelant i portant a la pràctica en una arquitectura hardware anomenada Commodity PC, formada per desenes de milers de nodes repartits per diferents data centers. Google ha sabut exprimir aquest concepte i ha sapigut aplicar una política de desenvolupament tremendament senzilla, basada en la màxima de Divide and conquer.

Algunes d'aquestes tecnologies ja s'estan projectant en el mon del programari lliure, aquest és el cas de Hadoop com a port de MapReduce. Però què és MapReduce exactament ?

Existeix un paper molt bo i no gaire dens escrit pels seus creadors i que en recomano la seva lectura, jo faré una petita aproximació tècnica i didàctica d'aquesta tecnologia.

MapReduce és una eina per tractar grans quantitats d'informació de forma automàtica amb un conjunt de nodes, on aquest conjunt pot anar de les poques desenes als diversos centenars de nodes. Per a poder processar de forma parl.lela la informació en diversos nodes MapReduce utiliza un parell de funcions anomenades Mapping i Reduce proveides per a l'usuari.

La funció Maping agafa com a paràmetre un valor, normalment una de les parts de l'entrada, realitza la lògica algorítmica i emet un un conjunt de parells clau, valor.

La funció Reduce agafa com a paràmetre una clau i el conjunt de valors possibles per aquella clau processats per la funció Mapping.

Anem a veure un exemple. Imaginem el problema de realitzar la cerca i comptatge d'un patró determinat en un arxiu. Un model bàsic seria força semblant al següent programa :

 
def grep(file_name, pattern):
    count = 0
    fd = fopen(file_name, "r")
    for line in fd.readlines():
        if ( re.search(pattern, line) )
            count = count + 1
 
    return count
 

MapReduce ens permet atacar aquest tipus de problemes d'una forma diferent, mitjançant la reducció del conjunt d'elements d'entrada.

Si haguessim de reescriure l'aplicació anterior a un format de MapReduce probablement tindriem quelcom semblant a això :

 
def map(part_file):
    for line in part_file.readlines():
        if ( re.search(pattern, line) ):
            emit(pattern, "1")
 
def reduce(key, list_values):
    count = 0
 
    for value in list_value:
        count = count + 1
 
    return count
 

Com podem observer ara tenim dues funcions, la funció map que agafa com a paràmetre una porció de l'arxiu d'entrada i la funció reduce que agafa com a paràmetre una clau i un conjunt de valors associats a aquesta clau.

Per poder respondre el perquè dels paràmetres i de les funcions el més útil es que veiem pas per pas que passa en una arquitectura MapReduce davant del problema i les funcions que s'han donat.

• MapReduce separa en N sub arxius l'arxiu orIginal. En el cas de MapReduce de Google això ja no serà necessari per la propia arqutiectura de Google File System.
• Cada sub arxiu o pedaç de buffer es passat a la funció definida per nosaltres i anomenada map, aquesta es podrà estar executant en qualsevol node de la infraestructura comodity PC. De fet tindrem múltiples intàncies d'aquesta funció executant-se en desenes de nodes.
• Cada una de les instàncies emet un conjunt de parells clau, valor. En el cas que presentem la funció map només emetrà valors del tipus pattern, 1
• A mida que les instàncies de les funcions map es van acabant, un conjunt d'instancies de les funcions reduce agafen les sortides amb el format clau, llista de valors
• Cada instància de reduce pot agafar una clau idèntica amb una llista de valors diferents, en el cas que ens ocupa les nostres instàncies de la funció reduce només reben la clau pattern, amb una llista de "1" que signifiquen comptatges del patró de les sortides de les funcions map

Aquesta és, simplificada, la metodologia de treball de MapReduce. La finalitat de MapReduce és doncs dividir el conjunt d'entrades per separar el seu processament en un cluster de nodes, aplicant la política de Divide and conquer

Existeixen múltiples problemes on aquesta solució és realment interessant, i en molts casos els problemes originals poden ser re escrits per aprofitar aquesta arquitectura. Análisis de logs, creació d'arxius invertits de frequenecies de paraules, treball sobre grafs, etc

Podeu trobar aquesta informació més ampliada al següent paper.