Pensando en paralelo - Introduccion a Map/Reduce
Como se habrán dado cuenta (al menos si me siguen en Twitter o sino lo pueden ver ahora) me he pasado los últimos días jugando con Hadoop que es la implementación mas popular del paradigma MapReduce para procesamientos de datos en paralelo. Para ello comencé a escribir una serie de APIs para su fácil manipulación desde PHP, asi podriamos escribir aplicaciones que se ejecuten en paralelo desde PHP, lo que voy a usar por primera vez en mi proyecto del Google Summer of Code como un plus del proyecto. Este post es una introducción cuasi-teórica sobre la programación concurrente (o en paralelo).
Imagínense que el siguiente pseudo-código C se ejecuta en 8 minutos en una computadora normal, y esta optimizado al máximo.
int i;
long * result;
for (i = 0; i < 3984; i++) {
*(result + i) = operation(i);
}
Asumiendo que la función operation no modifica ninguna variable global, el orden de la ejecución del ciclo no afectaría en nada el resultado. Partiendo de esa afirmación, si la computadora que ejecuta el programa cuenta con mas de 1 procesador/núcleo (para el ejemplo asumiremos que cuenta con 8), entonces podríamos crear 8 hilos/procesos y que cada uno vaya resolviendo una iteración del ciclo, así resolveríamos aproximadamente 8 veces mas rápido (hay una pequeña perdida por la partición de los datos y asignación de iteración a cada hilo/proceso). Este es el concepto de la computación concurrente o en paralelo.
Por supuesto, no todos los problemas pueden ser resueltos de forma concurrente, ejemplo el siguiente pseudo-código escrito en C. Esto no puede ser concurrente ya que esta vez la función operation recibe como parámetro el resultado de la iteración anterior, lo que fuerza la ejecución secuencial y en orden del ciclo.
int i;
long * result;
long xout = 0;
for (i = 0; i < 3984; i++) {
xout = operation(i, xout);
*(result + i) = xout;
}
Los lenguajes funcionales, son por naturaleza concurrente, ya que no existen el concepto de variable y una cada función nunca modifica un dato, siempre crea una nueva copia y lo modifica, ademas las funciones son como funciones puramente matemáticas, en las que se verifican ciertas propiedades como la transparencia referencial y por tanto, la carencia total de efectos laterales.
Personalmente, entre las pocas cosas que aprendí estudiando se destaca ampliamente Haskell, que me ayudó bastante a la hora de leer sobre MapReduce, altamente recomendado para ejercitar la mente para resolver problemas concurrentes.
Ahora que tenemos los conceptos básicos, podemos entrar un poco en lo que sea MapReduce. Básicamente existen dos funciones map y reduce que son aplicados a todos los datos. Al ser la programación concurrente, esto es divido en procesos que son proporcional al numero de datos a procesar y al numero de recurso de hardware disponible (núcleos, memoria ram, etc) para su ejecución. Los datos de entrada están formadas por una (clave, valor) y a cada dato es aplicada la función map, la cual produce una serie de resultados intermedios (de 0 a N), dichos resultados también están formados por (clave, valor). Luego, una vez finalizado todas las funciones map el proceso de MapReduce agrupa por clave los resultados intermedios, y a cada dato (clave, [resultado1, resultado2, ... resultadoN]) aplica la función reduce.
Hadoop (la mas popular Codigo Libre) o cualquier otra implementación del paradigma MapReduce, es una gran abstracción para el programador, que a diferencia de antes se centra en como resolver un problema utilizando solo funciones map y reduce. Parte de la abstracción incluye la partición de los datos, asignación y monitoreo de tareas, distribución de los datos a través de las maquinas utilizando un sistema de archivo distribuido, entre otras cosas. Este es un simple pseudo-código en PHP de como seria un indice invertido para Hadoop. (Funciona con la API que mencione anteriormente, esta en fase de desarrollo entonces me lo guardo para mi hasta que este terminado)
final class InvertedIndex extends Job
{
function map($key, &$value)
{
$value = strtolower($value);
foreach (preg_split("/[^a-záéíóúüñ]/i", $value) as $word) {
$this->EmitIntermediate($word, $key);
}
}
function reduce($key, &$values)
{
$this->Emit($key, array_unique($values));
}
}
El código de arriba, toma datos (id, textos) y construye un Indice Invertido, que básicamente es una lista de palabras y las referencias de los documentos en donde aparece, ejemplo (palabra, [doc1, doc2, doc3]). Básicamente por cada documento, se emite la palabra y la clave del documento en el cual aparece (en la función map), y la función reduce retorna una lista única de palabras.
Obviamente, para la resolución de problemas, se necesitan varios trabajos, entiéndase como trabajo aplicar las funciones map y reduce a una serie de datos, un claro ejemplo seria el algoritmo de agrupación por similitud de datos K-means, que luego de terminar y optimizar la versión convencional del algoritmo lo estoy escribiendo en versión concurrente.
Espero que esta pequeña introducción les haya sido entendible y útil, mas adelante escribiré mas sobre Hadoop y ejemplos prácticos
if __name__ == "__main__":
main()
![[FSF Associate Member]](http://cesar.la/fsf.png){kind=small}
