Computacion Distribuida - Hadoop y otros frameworks

Procesar lenguaje natural usualmente plantea tres escenarios:

1. Se requiere procesar una gran cantidad de datos para obtener buenos resultados
2. El procesamiento que tiene que realizarse es muy complejo (computacionalmente hablando)
3. La combinacion de los escenarios anteriores.

Cuando trabajas en estos escenarios rapidamente puedes quedarte corto de poder computacional. Es decir, obtener resultados toma mucho tiempo, o simplemente no obtienes resultados.
La opcion mas obvia es actualizar la maquina con mas memoria ram o procesador, pero esta no es una solucion escalable a medida que el volumen de datos o la complejidad de diferentes procesamientos empiezan a aumentar.
Es alli cuando viene la idea de formar clusters de computadoras. En vez de tener una super computadora que resuelva el problema, es mas eficiente, barato y escalable tener muchas computadoras que puedan resolver un problema de manera conjunta.
Escalable? si, porque aumentar el poder computacional consiste simplemente en agregar nuevas computadoras al cluster.

Desde el punto de vista del desarrollo de software, resolver el problema en el cluster plantea retos, primero el problema tiene que ser divido, luego tiene que asignarse porciones de ese problema a cada maquina dentro del cluster y adicionalmente debe existir un mecanismo de comunicacion entre cada computadora para resolver el problema eficientemente.
Aqui es cuando Hadoop entra en juego.

Hadoop

Hadoop es  un sistema de archivos distribuido basado en el google file system y adicionalmente es un framework con el paradigma map and reduce que facilita el desarrollo de soluciones de manera distribuida.  Es decir, que para el usuario de hadoop es transparente todo lo relativo a como se distribuye y se solucionan los problemas a bajo nivel, el desarrollador solo se preocupa por la logica para solucionar el problema.

Hadoop empezo como una extension a apache lucene (framwork de recuperacion de informacion) y como una alternativa libre luego que google publicara un paper donde describian un sistema de archivos distribuidos que ellos llaman Google File System.
Eventualmente Yahoo, que tenia problemas de escalabilidad y estaba construyendo su propia solucion decidio aportar al desarrollo de Hadoop contratando a algunos de sus desarrolladores y usando Hadoop para solucionar varios problemas de escalabilidad en su buscador.

Hadoop es usado por companias como facebook, last.fm y yahoo.

HDFS (Hadoop Document File System)

Empezare por el sistema de archivos llamdo Hadoop Document File System (HDFS), es basicamente un sistema de archivos distrubidos basados en el GFS.
En un sistema de archivos distribuidos un archivo no se encuentra en su totalidad en una maquina, sino que se encuentra distribuido entre diferentes maquinas, y adicionalmente esta replicado 3 veces para asegurar su persistencia.

Ventajas

La capacidad de almacenamiento en discos duros ha aumentado notablemnte en los ultimos 10 anios, sin embargo la velocidad de lectura no va al mismo ritmo.
Esto quiere decir que leer un archivo por completo en un solo disco duro va a tardar mas, que si leemos pequenos trozos de el, en muchos discos duros al mismo tiempo.
Esto representa rapidez y escalabilidad en cuanto a capacidad de almacenamiento.

Map and Reduce

Map and reduce tambien fue introducido por Google, es un concepto muy sencillo basado en dividir y conquistar y el paradigma funcional.

Map and reduce es un paradigma para plantear y resolver un problema. De esta forma el desarrollador expresa su problema usando este paradigma y hadoop se encarga de todos los detalles a bajo nivel que tiene que ver con computucion distribuida.

Map & Reduce consiste basicamente en la definicion de dos funciones: la funcion Map, y la funcion Reduce.

La funcion Map se encarga de partir la entrada en subproblemas en tuplas (llave,Valor) , la funcion Reduce se encarga de unir las tuplas cuya llave es la misma, y resolver el problema en particular.

Por ejemplo, si quisieramos leer un texto y hacer una tabla de frecuencias de cuantas veces aparece una palabra usando map & reduce tendriamos algo parecido a:

 funcion map(Texto):  
  Para Palabra en Texto:  
       emitir(llave: palabra, 1)  

 funcion reduce(llave, valores):  
      cuentaTotal=largo(valores)  
      emitir(llave, cuentaTotal)  

Map en este caso se encarga de leer cada palabra del texto de entrada y de emitir un evento con una tupla, cuya llave es la palabra, y un valor, en este caso 1.

Reduce se encarga de recibir una llave con una lista de valores. Esta lista de Valores es la concatenacion de varios valores emitidos por map con la misma llave.

Reduce cuenta cuantos elementos tiene la lista, lo cual equivale a cuantas veces ha sido vista la palabra llave. Finalmente emite un evento, donde registra el resultado de contar cuantas veces fue vista la palabra llave.

Ejemplo:

suponga que el texto es:

 "A B C D A A B C"

map emitiria: (A,1) , (B,1) (C,1), (D,1) (A,1)(A,1),(B,1),(C,1)...

por lo cual la funcion Reduce seria llamda con los siguientes valores:

   reduce(A, [1,1,1]) , como resultado emitiria : (A,3)

   reduce (B, [1,1]),  como resultado emitiria:    ( B,2)

   ...

Para el desarrollador en hadoop bastaria con implementar estas dos funciones.

Todo lo demas estaria acargo de Hadoop. 

A continuacion escribo una breve descripcion sobre otros framework construidos sobre hadoop y que facilitan tareas de desarrollo.

Cascading

Para problemas mas complejos un solo map & reduce no es suficiente, probablemnte se requieran de varios map-reduce.

En este tipo de problemas el desarrollo puede convertirse en algo sucio, pues se tienen que manejar una cantidad de llaves ,tuplas y transformaciones entre tuplas.

Cascading es un framework hecho sobre hadoop que ayuda a desarrollar problemas mas complejos siguiendo el paradigma map & reduce.

Web: http://www.cascading.org/

Hive

Es un framework de Datawarehousing que funciona sobre hadoop. 

Las bases de datos corrientes funcionan sobre estructuras de datos basadas en B-Trees.

El problema con estas estructuras de datos es que tienen limites de escalabilidad.

Facebook  funcionaba sobre una BD oracle, en su momento cuando tuvo problemas de escalabilidad empezo a usar hive para hacer analisis sobre sus bases de datos.

Hive permite hacer consultas en un lenguaje muy parecido a SQL, la diferencia es que estas consultas corren a bajo nivel con procesos map&reduce,  y que la base de datos esta distribuida usando HDFS.

web: http://hive.apache.org/