WIXLIB

Departamento de InformáticaPROYECTO FIN DE CARRERABASES DE DATOS NOSQL:ARQUITECTURA YEJEMPLOS DE APLICACIÓNIngeniería InformáticaAutor: Raúl Herranz GómezTutor: Ana María Iglesias MaquedaLeganés, Junio de 2014

2

Título: BASES DE DATOS NOSQL: ARQUITECTURA Y EJEMPLOS DEAPLICACIÓNAutor: Raúl Herranz GómezDirector: Ana María Iglesias MaquedaEL TRIBUNALPresidente:Vocal:Secretario:Realizado el acto de defensa y lectura del Proyecto Fin de Carrera el día 27 de Junio de2014 en Leganés, en la Escuela Politécnica Superior de la Universidad Carlos III deMadrid, acuerda otorgarle la CALIFICACIÓN deVOCALSECRETARIOPRESIDENTE3

4

AgradecimientosHay muchas personas a las que me gustaría agradecer que hayan compartido conmigomuchos momentos importantes, personas que espero y deseo de corazón que me siganacompañando en muchos momentos más.Primero a mi familia, quienes me quieren y apoyan en cada paso que doy.Especialmente importante para mi es el apoyo incondicional que mi madre me ha dadoy me sigue dando cada día de mi vida. Me cuesta imaginar que sería de mí sin susconsejos y su ayuda. Y a mis hermanos, con los que tantas risas y peleas he tenido, ytanto nos hemos aguantado en casa en los buenos y en los malos momentos.A Sara, por todo lo que comparto contigo, la confianza, la complicidad, los buenosmomentos. También por esa seguridad que me aportas en los momentos clave. Ytambién por esos largos días de no ver el sol haciendo proyecto y master, sin los cualesno se si podría estar escribiendo esto.A toda la gente de la carrera que ha compartido conmigo algún momento, y en especiala aquellos que me siguen acompañando en el día a día. Ellos son Martín, Jesús, Aitor,Mario, Marcos, Patarino, Javi, Lalla, Juanto y mucha más gente de la UC3M.A mis amigos de toda la vida, de Fuenlabrada y de Collado Hermoso, por haber estadoahí en todo momento, por esas quedadas, por esos veranos, esos viajes y esos fines desemana increíbles.A Ana, mi tutora, por todo el apoyo y los consejos que me ha dado. Gracias porhaberme empujado y animado hasta conseguirlo.Y finalmente, a todo el mundo que alguna vez me ha preguntado que si ya habíaterminado el proyecto y que cuando iba a terminarlo. Gracias por preocuparos tanto, yano tendréis que hacerlo más. Ya está hecho.5

ResumenEn los últimos años, la cantidad de datos digitales que se genera el mundo se hamultiplicado. Las redes sociales y el cada vez más fácil acceso a Internet del quedisponemos las personas hacen que el volumen de tráfico y de datos que se generan seacada vez mayor.Con el surgimiento de las bases de datos relacionales las empresas encontraron el aliadoperfecto para cubrir sus necesidades de almacenamiento, disponibilidad, copiado deseguridad y gestión de sus datos.Pero debido a las tendencias actuales de uso de Internet, este tipo de sistemas hancomenzado a experimentar dificultades técnicas, en algunos casos bloqueantes, queimpiden el buen funcionamiento de los sistemas de algunas de las empresas másimportantes de Internet. Este tipo de datos que son masivamente generados reciben unnombre: BigData, y un tipo de tecnología ha surgido para tratar de poner solución amuchos de los problemas de los que adolecen los sistemas de almacenamientotradicionales cuando intentan manejar este tipo de datos masivos. Esta tecnología seconoce como NoSQL.En este Proyecto Fin de Carrera se profundizará en el movimiento conocido comoNoSQL, analizando las características y tipos de bases de datos que han surgido comoparte del movimiento. Además, se detallará la arquitectura y el modo de funcionar deseis de estos Sistemas Gestores de Bases de Datos, comparándolos entre sí y buscandoen qué casos funcionan mejor unos y otros.Finalmente, se describirá cómo instalar de dos de estos sistemas con susconfiguraciones más sencillas, así como un posible diseño de base de datos para unconjunto de información concreta.6

Índice General1Introducción.151.1Motivación . 151.2Objetivos . 161.3Estructura del documento. 162Estadodelarte.192.1Big Data . 192.1.1¿Qué es Big Data? . 192.1.2¿Para que sirve el Big Data? . 212.1.3Características del Big Data : las 3 V’s . 212.1.4Un ejemplo de sistema de almacenamiento para Big Data: Hadoop . 232.2Sistemas Tradicionales de Almacenamiento de Información . 312.2.1Bases de Datos Relacionales . 312.2.2Bases de Datos NoSQL . 343NoSQL.423.1El Movimiento NoSQL . 433.1.1Motivaciones principales del movimiento NoSQL . 433.1.2Crítica general y oposición . 453.2Bases de Datos NoSQL . 473.2.1Conceptos básicos, técnicas y patrones . 474Basesdedatosclave- ‐valor.575DynamoDB.575.1Introducción . 575.2Características principales. 575.2.1Aprovisionado . 575.2.2Regiones y Zonas de Disponibilidad . 585.2.3Influencias . 595.3Arquitectura . 595.3.1Interfaces del sistema . 605.3.2Algoritmo de particionado. 605.3.3Replicación . 615.3.4Versionado de Datos . 615.3.5Ejecución de operaciones getItem() y putItem() . 645.3.6Gestión de errores . 645.3.7Gestión de Nodos . 665.4Modelo de Datos . 665.4.1Tablas . 665.4.2Elementos. 675.4.3Atributos . 677

5.5Implementación y Optimizaciones. 675.6Ejemplos reales de uso del SGBD . 695.6.1IMDB . 695.6.2SmugMug . 696Redis.716.1Introducción . 716.2Características principales. 716.2.1Tipos de datos . 716.2.2Usos del SGBD . 726.3Arquitectura . 726.3.1Almacenamiento en memoria y persistencia asíncrona . 726.3.2Replicación y Consistencia . 736.3.3Particionado . 746.3.4Gestión de colas: paradigma de mensajes generador - consumidor . 756.3.5Transacciones y Atomicidad . 766.3.6Consistencia. 776.4Modelo de Datos . 786.4.1Cadenas de texto . 786.4.2Diccionarios . 786.4.3Listas . 796.4.4Conjuntos . 796.4.5Conjuntos ordenados . 806.4.6Bases de datos . 816.5Ejemplos reales de uso del SGBD . 816.5.1Pinterest . 816.5.2Twitter . �n . 848.2Características principales. 858.2.1Distribuido . 858.2.2Mapa Ordenado . 858.2.3Multidimensional . 858.2.4Disperso . 888.3Arquitectura . 888.3.1Diseño del Sistema. 898.3.2Funcionamiento . 918.4Modelo de Datos . 928.4.1Filas . 928.4.2Column Families. 938.4.3Timestamps . 938.4.4Diseño conceptual . 938.4.5Diseño físico . 948.5Zookeeper. 958.6Ejemplos reales de uso del SGBD . 958.6.1Facebook . 958.7Diseño de una base de datos real con HBase . 968.7.1Instalación de Hadoop y HBase . 968.7.2Diseño de tablas por fichero . 978.7.3Diseño general de tablas . 1019Cassandra.1049.1Introducción . 1048

9.2Características Principales . 1049.2.1Distribuido . 1049.2.2Descentralizado . 1059.2.3Alta Escalabilidad . 1059.2.4Tolerancia a Fallos . 1059.2.5Eventualmente Consistente . 1059.3Arquitectura . 1069.3.1Espacio de Claves . 1069.3.2Peer to Peer . 1079.3.3Particionado . 1079.3.4Replicación . 1079.3.5Gossiping . 1089.3.6Anti entropía . 1089.3.7Procedimiento de escritura . 1099.3.8Tombstones . 1099.3.9Compactación . 1099.3.10Filtros Bloom . 1109.3.11SEDA . 1109.4Modelo de Datos . 1119.4.1Clúster . 1119.4.2Keyspaces . 1119.4.3Column Families. 1129.4.4Columas . 1139.4.5Supercolumnas. 1149.5Ejemplos reales de uso del SGBD . 1159.5.1Hulu . 1159.5.2Spotify . Introducción . 11611.2Características generales . 11611.3Arquitectura . 11711.3.1Replicación . 11711.3.2Sharding. 11911.4Modelo de datos . 12311.4.1BSON . 12411.4.2Estructura del documento . 12411.4.3Índices . 12611.5Usos reales del SGBD . 12711.5.1Foursquare . 12711.5.2MTV Networks . 12711.6Anexo IV: Diseño real de una base de datos en MongoDB. 12811.6.1Instalación de MongoDB . 12811.6.2Primeros pasos . 12811.6.3Comandos de inserción y búsqueda . 12911.6.4Diseño literal de la base de datos. . 12911.6.5Diseño del corpus adaptado a MongoDB . 13011.6.6Todos los ficheros de tweets bajo la misma colección . 3.1Introducción . 13313.2Grafos . 1339

13.2.1Aplicaciones reales . 13413.3Características principales. 13513.3.1Rendimiento . 13513.3.2Flexibilidad . 13613.3.3Agilidad . 13613.3.4Transacciones ACID . 13613.4Arquitectura . 13713.4.1Alta disponibilidad . 13713.4.2Backup . 13813.5Modelo de consultas. 13813.6Ejemplos de uso real del SGBD . 13913.6.1eBay . 13913.6.2Infojobs . 13914Discusiónsobrelossistemasvistos.14114.1Uso de Clave – Valor . 14214.2Uso basado en Columnas . 14314.3Uso basado en documentos . 14314.4Uso basado en Grafos . 14414.5NoSQL vs Relacional. io.14818Bibliografía.14919Anexos.15319.1Anexo I: Instalación de Hadoop y HBase . 15319.1.1Configuración del Hadoop . 15319.1.2Configuración de SSH . 15419.1.3Instalación de HBase . 15519.2Anexo II: Descripción de los tweets que conforman el corpus. 15619.2.1Diseño de bases de datos para el almacenamiento de datos reales. . 15619.2.2Descripción del Corpus . 15610

Índice de IlustracionesIlustración 1. Big Data Cloud Tags . 20Ilustración 2. Las 3 Vs del BigData . 22Ilustración 3. Arquitectura de funcionamiento del HDFS . 26Ilustración 4. Diseño de una aplicación MapReduce . 29Ilustración 5. Arquitectura YARN. 31Ilustración 6. Formas normales . 32Ilustración 7. Teorema de CAP . 48Ilustración 8. Transacciones ACID . 50Ilustración 9. Consistent Hashing 1 . 52Ilustración 10. Consistent Hashing 2 . 53Ilustración 11. Ejemplo de MapReduce con Consistent Hashing . 56Ilustración 12. Replicación de los N-1 nodos virtuales consecutivos . 61Ilustración 13. Esquema de la evolución de un objeto a lo largo del tiempo . 63Ilustración 14. Estructura de un Árbol Merkle . 66Ilustración 15. Grafo de followers de Pinterest . 82Ilustración 16. Flujo de escritura de Tweets desde una aplicación y sus actualizacionesen Redis . 83Ilustración 17. Integración de HBase con los componentes de Hadoop . 84Ilustración 18. Dispersión en una tabla de HBase . 88Ilustración 19. Arquitectura HBase . 91Ilustración 20. Ejemplo de una fila en una tabla de HBase . 9211

Ilustración 21. Arquitectura desplegada en HydraBase. 103Ilustración 22. Erro de un nodo en HydraBase . 103Ilustración 23. Representación de la escalabilidad casi lineal de Cassandra. 107Ilustración 24. Diseño de una Column Family . 113Ilustración 25. diseño de una súper columna . 114Ilustración 26. Ejemplo de Documento en MongoDB . 116Ilustración 27. Caída del nodo primario y elección para obtener uno nuevo . 119Ilustración 28. Colección dividida en 4 shards . 120Ilustración 29. Arquitectura de un sharded clúster . 122Ilustración 30. Ejemplo de sharding basado en rangos . 123Ilustración 31. Ejemplo de sharding basado en hashes . 123Ilustración 32. Modelado de datos utilizando enlaces entre documentos. 125Ilustración 33. Documentos embebidos en otro . 126Ilustración 34. Interrelaciones de elementos de un grafo . 13412

Índice de TablasTabla 1. Tabla comparativa de almacenamiento en filas vs almacenamiento en columnas. 38Tabla 2. Tabla de compras de un supermercado . 39Tabla 3. Teorema CAP .

NoSQL, analizando las características y tipos de bases de datos que han surgido como parte del movimiento. Además, se detallará la arquitectura y el modo de funcionar de seis de estos Sistemas Gestores de Bases de Datos, comparándolos entre sí y buscando en qué casos funcionan mejor unos y otros.