El origen de Map y Reduce
Publicado el Junio 23, 2010 por Jose María Rey
Archivado bajo Tecnologías
(No valorado aún) 
Loading ...A principios de este año se concedió a Google la patente de MapReduce, un método de procesamiento que, según Google, permite tratar gandes cantidades de información en entornos masivamente paralelos. El método se presta también a ser ejecutado en entornos de alta disponibilidad, donde una unidad de procesamiento puede ser reemplazada por otra en caso de fallo.
En esencia, el método consiste en distribuir la carga de trabajo entre un cierto numero de procesadores (los workers), cada uno de los cuales puede ejecutar una de estas tareas:
- Map: Las tareas tipo map aplican una función a su entrada para obtener los datos transformados. En el entorno MapReduce, a cada dato de salida se le asocia una etiqueta que se usa en las tareas Reduce.
- Reduce: Las tareas tipo reduce toman los datos que llegan de los workers ejecutando tareas map y generan una salida que se obtiene de aplicar una función a todos aquellos pares recibidos que contengan la misma etiqueta. La salida puede contener uno o más registros.
El aspecto que probablemente sea más relevante del entorno MapReduce es su alta configurabilidad:
- Por un lado, se puede organizar los workers en la estructura de malla que se desee (es decir, se puede por ejemplo asignar a una tarea M nodos map que alimentan a R nodos reduce que a su vez vuelven a otro conjunto de nodos map…). Tampoco debemos olvidar que el criterio de partición del conjunto de datos entre los nodos map puede ser también adaptado a una tarea particular.
- Por otro lado, tanto los nodos map como los nodos reduce aplican funciones que no son fijas sino que pueden ser programadas para cada tarea específica.
Ambos pasos de procesamiento (map y reduce) están inspirados, como reconocen implícitamente los autores de la patente, en funciones que la programación funcional lleva usando desde hace mucho tiempo.
La programación funcional basa su modelo de funcionamiento casi exclusivamente en la composición de funciones y no hay casi estructuras de control (tales como bucles, propios de los lenguajes imperativos) por lo que el tratamiento de funciones debe ser necesariamente muy potente. Parte de esta potencia viene del hecho de que en programación funcional las funciones son un tipo de objetos como cualquier otro y por tanto pueden ser pasadas como argumento a otras funciones. Es verdad que ciertos lenguajes imperativos como C++ importaron esta característica pero la integración conseguida no es tan perfecta como en programación funcional.
En programación funcional, la función map realiza lo siguiente:
map(f,[a1,a2,...,an]) = [f(a1), f(a2), ..., f(an)]
Es decir, map recibe dos un argumentos: Una función unaria (f) una lista de datos sobre los que operar (los ai). La función map aplica f a cada uno de los elementos de la lista y retorna una lista con todos los valores resultantes. La potencia de map está precisamente en este argumento puesto que sin cambiar la definición de map se pueden hacer infinidad de cosas con una lista, simplemente definiendo una f adecuada.
El paralelismo entre el map funcional y el primero de los dos pasos de procesamiento de MapReduce resulta claro (se debe tener en cuenta que no hay problema en que la función f devuelva pares (etiqueta, valor)). La lista de valores recibida por map estaría compuesta por todos los elementos pertenecientes a una misma partición definida por el paso inicial de particionamiento.
El paso reduce resulta algo más complejo. En programación funcional, reduce (también conocida como fold) aplica una función binaria a los elementos de una lista pero en lugar de devolver un valor por cada valor de entrada, reduce acumula todas las aplicaciones para generar un único valor:
reduce(f,z, [a1, a2, ..., an])=f(f(…f(f(z, a1), a2), a3),…, an)
En la expresión anterior se ha presentado el caso del reduce que acumula a izquierdas (conocido como foldl) pero, por supuesto, se puede definir su versión que acumula a derechas (foldr). En Haskell, la función reduce a izquierdas se puede escribir como sigue:
reduce f z [] = z
reduce f z (x:xs) = reduce f (f z x) xs
La definición permite apreciar que z es una especie de elemento neutro que se devuelve cuando se recibe una lista de elementos vacía. La versatilidad de reduce es mucho mayor de lo que pueda parecer a primera vista. Por ejemplo:
- Sumar todos los elementos de una lista: reduce (+) 0 [a1, ... ,an]
- Multiplicar todos los elementos de una lista: reduce (*) 1 [a1, ... ,an]
donde (+) y (*) representan respectivante las funciones binarias que suman o multplican sus dos argumentos. Usando valores más complejos de f se pueden conseguir efectos tales como definir map en función de reduce.
En este caso, la correspondencia entre el reduce funcional y el segundo paso del entorno MapReduce no es tan cercana ya que en el entorno de Google la salida de un paso de reducción puede tener más de un valor mientras que la versión funcional devuelve un único valor y en el esquema MapReduce probablemente se puedan definir otros esquemas de uso de f pero en cualquier caso, la relación es clara.
Tags: Google, lenguajes de programacion
Comentarios
Deja una respuesta
Suscripciones
Creative Commons
Los contenidos de este blog están bajo una licencia de Creative Commons. Pueden utilizarse, pero sin fines comerciales y citando la fuente.
Suscríbete a La Cofa