PDF de programación - Implementación de un sistema de cómputo distribuido Map-Reduce sobre AMQP

Implementación de un sistema de
cómputo distribudo Map-Reduce sobre
AMQP
Aprendizaje automático sobre grandes volúmenes de
datos

Docente: Dr. Pablo Duboue

Autor: Juan B Cabral

5 de diciembre de 2014
Facultad de Matemática Astronomía y Física
Universidad Nacional de Córdoba

Índice general

1. Introducción

2. Antecedentes

2.1.
2.2. Modelos Computo distribuido .
2.3. Apache Hadoop .
.
.
.
2.4. Apache Mahout

Implicancias del Computo Distribuido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.
.

.
.

.
.

.
.

.
.

.
.

3. Herramientas y Motivaciones
.
.

3.1. Python .
.
3.2. Motivación .

.
.

.
.

.
.

.
.

.

.
.

.
.

.
.

.
.

.
.

.
.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4. Resultados - Poopy

4.1. Colas y Procesos .
.
4.2. Esperas y Timeouts .
4.3. Análisis del ciclo de vida del comando run . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . .

. . . . . . .

. . .

.
.

.
.

.
.

.
.

.
.

.
.

5. Conclusión

5.1. Cierre .

.

.

.

.

.

.

.

.

.

.

.

.

.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6. Apéndice A: Pseudo Código de Poopy

6.1. Código perteneciente al nodo central encargado de lanzar las tareas distribuidas . . . . . . . . . . . .
6.2. Código de nodos clientes .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

.

.

.

1

3
3
4
5
6

7
7
8

9
9
11
14

15
15

17
17
20

I

II

CAPÍTULO 1

Introducción

Nullius in verba

—Lema de la Real Sociedad de Londres

El advenimiento de grandes volúmenes de datos (o Big Data1) esta generando una necesidad de productos que sirvan
para la manipulación y resumen de los mismos. Big Data puede considerarse de manera mas o menos precisa (no es
mas que un numero comercial) como una cantidad de información tal que no puede procesarse ni almacenarse en un
único ordenador.
Las dificultades más habituales vinculadas a la gestión de estas cantidades de datos se centran en la captura, el alma-
cenamiento,2 búsqueda, compartición, análisis y visualización. La tendencia a manipular ingentes cantidades de datos
se debe a la necesidad en muchos casos de incluir los diferentes conjuntos de datos relacionados.
La tendencia actual es el almacenamiento y el procesamiento a través de nodos distribuidos en una red de la manera
mas transparente posible para el programador, haciéndolo parecer que esta ejecutando todo localmente; despegándose
un poco del modelo propuesto por el ya tradicional modelo distribuido de MPI2 (del inglés Interfaz de Paso de Mensaje)
de hacer evidente la no localidad del computo.
Por el dado del análisis de datos; en la presencia de una cantidad ingente de información como la que planteamos
hace necesario el disponer de mecanismos automáticos para el procesamiento de estos volúmenes. Es en este campo
donde una herramienta como el aprendizaje automático3 (o ML) obtiene un valor de piedra angular. El aprendizaje
automático es una rama de la de la Inteligencia Artificial4 que consiste en crear programas que buscan de manera
autónoma patrones en la información a partir de ejemplos.
En el siguiente trabajo analiza la implementación del modelo mas popular de los últimos años para el computo dis-
tribuido: Map-Reduce5 así como un sistema distribuido de almacenamiento de archivos utilizando como sistema de
transporte de información el modelo de colas de mensajes AMQP6 y utilizando como lenguaje de programación Pyt-
hon7 y su librería de aprendizaje automático Scikit-Learn8.
El trabajo resultante se hizo publico bajo una licencia laxa bajo del nombre de Poopy9 en la siguiente dirección web
http://poopy.jbcabral.org.
Las fuentes de este trabajo pueden encontrarse en: https://bitbucket.org/leliel12/bigdata_famaf

1http://es.wikipedia.org/wiki/BigData
2http://en.wikipedia.org/wiki/Message_Passing_Interface
3http://en.wikipedia.org/wiki/Machine_learning
4http://en.wikipedia.org/wiki/Artificial_intelligence
5http://research.google.com/archive/mapreduce.html
6http://www.amqp.org/
7http://python.org
8http://scikit-learn.org
9http://poopy.jbcabral.org

1

Implementación de un sistema de cómputo distribudo Map-Reduce sobre AMQP

2

Capítulo 1.

Introducción

CAPÍTULO 2

Antecedentes

A distributed system is one in which the failure of a computer you didn’t even know existed can render
your own computer unusable.

—Leslie Lamport, Premio Turing Award 2014 por sus contribuciones al cómputo distribuido

En la actualidad la herramienta mas popular de computo distribuido es sin dudas Hadoop1. Hadoop es una implemen-
tación del algoritmo MapReduce realizada íntegramente en Java2, que ha servido de inspiración y guía a lo en todo
este trabajo.
Con el objeto de entender mejor el trabajo realizado, a largo de este capitulo analizaremos algunos implicancias del
computo distribuido (teorema CAP), dos modelos de computo distribuido (AMQP y MapReduce) y cerraremos con el
análisis de una herramienta construida con el objeto de hacer aprendizaje automático sobre grandes en un cluster de
computadoras.

2.1 Implicancias del Computo Distribuido

Un sistema distribuido se define como una colección de computadoras separadas físicamente y conectadas entre sí por
una red de comunicaciones; cada máquina posee sus componentes de hardware y software.

2.1.1 Teorema CAP

El teorema CAP surge de una conjetura muy sencilla:

No se puede garantizar consistencia, disponibilidad (Availability en inglés) y ser tolerante a las particiones
en un sistema de cómputo distribuido.

Esta conjetura fue realizada por Eric Bewer3 en la Universidad de California Berkley4 y demostrada debidamente por
Gilber y Lynch5 en el MIT6.
Según satisfagan estos criterios podemos clasificar varios sistemas como por ejemplo

Disponibilidad y tolerancia a las particiones: Cassandra7 y CouchDB8.

1http://hadoop.apache.org/
2https://www.java.com
3http://www.cs.berkeley.edu/ brewer/
4http://www.berkeley.edu/index.html
5http://people.csail.mit.edu/lynch/
6http://web.mit.edu/
7http://cassandra.apache.org/
8http://couchdb.apache.org/

3

Implementación de un sistema de cómputo distribudo Map-Reduce sobre AMQP

Consistencia y tolerancia a las particiones: HBase9 y Paxos.
Consistencia y Disponibilidad: RDBMS10.

2.2 Modelos Computo distribuido

Existen varios modelos de computo distribuido de los cuales analizaremos 2 que tienen relevancia para el proyecto:
AMQP11 y MapReduce

2.2.1 AMQP

AMQP12 (del ingles Advanced Message Queuing Protocol - Protocolo avanzado de colas de mensajes) es un estandar
en el nivel de aplicación13 para middlewares oriantados a mensajes. Sus características principales son:

Orientación a mensajes
Colas
Enrutamientos (punto a punto y publicador-suscripción)
Exactitud y seguridad

AMQP estipula a nivel binario el comportamiento tanto del servidor que provee los mensajes como del cliente de la
mensajería hasta el punto de que las implementaciones en diferentes lenguajes son totalmente inter operables; de la
misma forma que lo lograron SMPT14, HTTP15 y SFTP16.
La infraestructura de AMQP es la siguiente:

El corredor de mensajes (o Broker): un servidor al que los clientes AMQP se conectan usando el protocolo
AMQP.
Usuario (o cliente): un usuario es una entidad que, mediante la presentación de credenciales tales como una
contraseña, puede ser autorizado (o puede no ser autorizado) a conectarse a un corredor.
Conexión: una conexión física usando por ejemplo TCP/IP o SCTP. Una conexión está ligada a un usuario.
Canal: una conexión lógica que está unida a una conexión. Así pues, la comunicación a través de un canal
posee un estado. Aquellos clientes que realicen operaciones concurrentes mediante una misma conexión deben
mantener un canal distinto para cada una de ellas.

Implementaciones populares de AMQP son rabbitMQ17, y Apache ActiveMQ18
Si usamos extenciones para distribuirs brokers AMQP, segun el Teorema CAP, puede ser AP (si usamos Federation19
/ Shovel20) y CA Si usamos AMQP Clustering21

9http://hbase.apache.org/
10http://en.wikipedia.org/wiki/Relational_database_management_system
11http://www.amqp.org/
12http://www.amqp.org/
13http://en.wikipedia.org/wiki/Application_layer
14https://tools.ietf.org/html/rfc821
15http://tools.ietf.org/html/rfc2774
16http://tools.ietf.org/html/draft-ietf-secsh-filexfer-13
17http://www.rabbitmq.com
18http://activemq.apache.org/
19https://www.rabbitmq.com/federation.html
20https://www.rabbitmq.com/shovel.html
21https://www.rabbitmq.com/distributed.html

4

Capítulo 2. Antecedentes

Implementación de un sistema de cómputo distribudo Map-Reduce sobre AMQP

2.2.2 MapReduce

MapReduce es un modelo de cómputo que simplifica el uso de clusters22; el cual computa una función que recibe
como parámetros un conjunto de elementos llave-valor, y lo convierte en un nuevo conjunto el cual cada elemento es
una llave y una lista de valores.