Bases de Datos NoSql Conceptos generales

Lic. Gerardo Rossel Lic. Fernando Bugni

Temas de la clase de hoy ● Limitaciones de las base de datos relacionales ● Motivacion para NoSQL ● Descripción breve de tipos de NoSql: ○ Key-value, ○ Document, ○ Column Oriented ○ Graph ● Describiendo problemas en sistemas distribuidos ○ Consistencia ○ Disponibilidad ○ Balanceando la carga

Bases Relacionales Ventajas ● Persistencia de datos ● Concurrencia – ACID - Recuperación ● Integración entre múltiples aplicaciones ○ Shared database integration

● Modelo estándar y profundamente estudiado ● SQL

Bases Relacionales Desventajas ● Impedance mismatch ● Bases de datos de integración vs. Bases de datos de aplicación. ● No diseñadas para clustering

Impedance mismatch Diferencia de representación entre BD y estructuras en memoria.

BD Integración vs. Applicación ● DB Integración soportan múltiples aplicaciones ○ Problemas si hay necesidades diferentes y son mantenidas por grupos separados

● SQL puede ser limitante como la única capa compartida ○ Servicios WEB se han transformado en una alternativa más flexible ○ Service-Oriented Architecture ○ JSON o XML proveen una estructura de datos más rica que SQL

● BD de Aplicaciones son más simples y fáciles de manejar ● La seguridad y flexibilidad son menos prioritarios.

CLUSTERS!!!!

CLUSTERS!!!! ● Diluvio de datos: ○ Links, redes sociales,logs, cartografía ○ Crece el volumen de datos no estructurados

● ¿Cómo escalar? ○ Scale UP (Vertical) vs Scale Out (Horizontal)

● Las bases de datos relacionales no están diseñadas para correr en clusters ○ Oracle RAC o MS SQL Server

CLUSTERS!!

CLUSTERS!!!

Inspiración Desajuste entre bases relacionales y clusters ● BigTable - Google ○ Fay Chang, et al. "Bigtable: A Distributed Storage System for Structured Data,"OSDI'06: Seventh Symposium on Operating System Design and Implementation, Seattle, WA, November, 2006 •

● Dynamo - Amazon ○ Giuseppe DeCandia, et al., Dynamo: amazon's highly available key-value store. In Proceedings of twentyfirst ACM SIGOPS symposium on Operating systems principles (SOSP '07). ACM, New York, NY, USA,

NoSQL ● 1998: NoSQL – A relational database management system. Carlo Strozzi ● Jon Oskarsson, 2009. Reunión en San Francisco ○ Buscaba un hashtag ○ ○

Eric Evans hizo el termino popular. "open source, distributed, non relational databases"

● “NoSQLers came to share how they had overthrown the tyranny of slow, expensive relational databases in favor of more efficient and cheaper ways of managing data.” Computerworld 2009 ● Eric Evans: NoSQL: What’s in a name? Not Only SQL

NoSQL - Definición ●

●

●

NoSQL is a set of concepts that allows the rapid and efficient processing of data sets with a focus on performance, reliability, and agility. Dan McCreary Ann Kelly NoSQL is used today as an umbrella term for all databases and data stores that don’t follow the popular and well established RDBMS principles and often relate to large data sets accessed and manipulated on a Web scale. This means NoSQL is not a single product or even a single technology. It represents a class of products and a collection of diverse, and sometimes related, concepts about data storage and manipulation. Shashank Tiwari NoSQL is an accidental neologism. There is no prescriptive definition— all you can make is an observation of common characteristics. Fowler Sadalage

Motivación ● Escalabilidad ○ ○

La capacidad de satisfacer eficientemente las necesidades de diferentes cargas de trabajo Scale Out

● Costo ○

La mayoría de las BD NoSQL son Open Source. Aunque este punto es discutible ya que hay poderosas bases relacionales Open Source

● Flexibilidad ○ ○

Adaptarse al problema A diferencia de las bases de datos relacionales, algunas bases de datos NoSQL no requieren una estructura de tablas fija.

● Disponibilidad ○ Clusters!!

NoSQL - Tipos

NoSQL - Tipos ● Key-values Stores ○ Keys: número de identificación ○ Value: valor de la entrada tipado

Ejemplo: cust1.account -> 1 cust1.name -> Name1 cust1.age -> 25 cust2.account -> 2 cust2.name -> Name2 cust2.age -> 38

Key-value Store Namespaces: Customers:

Shops:

cust1.account -> 1

shp1.address -> Str1

cust1.name -> Name1

shp2.address -> Str2

cust1.age -> 25

shp3.address -> Str3

cust2.account -> 2

...

cust2.name -> Name2 cust2.age -> 38 ...

Products: prd1.Name -> NameP1 prd1.price -> 15 prd2.Name -> NameP2 prd2.price -> 20 ...

NoSQL - Tipos ● Document { firstName: “Pedro”, lastName: “Lopez”, phoneNumber: “15-5515-8895”, birthDate: “1-Apr-1980” } ● ●

Notación JSON o XML No hay un esquema definido para cada documento. Se puede agregar un empleado que tenga más campos, por ejemplo "address", y sólo ése empleado tiene definido ese campo.

Document ● Consultas a través de una API de la forma: db.employers.find({name: "John")}

● Se pueden agregar atributos con listas de elementos. Ejemplo: ... prevJobs: [{name: "Globant", startDate: "1-Apr-2005", endDate: "3-Oct-2007}, {name: "Baufest", startDate: "1-Apr-2005", endDate: "3-Oct-2007}]

NoSQL - Tipos ● Column Family Databases ○ Columnas: definición nombre -> valor ●

name -> John

○ Filas: conjunto de columnas ● ●

Fila 1 = {name-> John, age-> 25} Fila 2 = {name-> Fred, age-> 30}

○ Column Families: {name, age} ○ Sin esquema fijo. Se puede agregar cualquier columna en una fila. ○ Esquema de consultas similar a SQL pero sin joins.

NoSQL - Tipos ● Graph Databases ○ Modelado utilizando vértices y arcos. ○ Ambos elementos pueden guardar atributos o listas de atributos. Martín: {age: 25} {since: ‘21-Sep-2000’} {since: ‘10-Apr-2005’} Pedro: {age: 28}

{since: ‘14-Nov-2002’} Juan: {age: 20}

{since: ‘1-Feb-1999’} Flor: {age: 20}

●

¿Se puede representar esto en una base de datos relacional?

Bases de Datos NoSql Consistencia y distribución

Lic. Gerardo Rossel Lic. Fernando Bugni

Consistencia: Tipos ● Consistencia de actualización. ○ Conflicto write-write. ○ Control Pesimista / Optimista ○ ¿Multiples Nodos? ■ Método simil control de versiones

Consistencia: Tipos ● Consistencia de lectura ○ Conflicto read-write. ■ Consistencia Lógica: garantizar que los diferentes elementos de datos tienen sentido juntos

Consistencia ○ Aggregate-oriented database. Actualización atómica a nivel agregado. ○ Ventana de inconsistencia ¿Durante cuánto tiempo hay inconsistencia? ■ Servicio SimpleDB de Amazon: < 1 segundo.

Consistencia Eventual ● Consistencia de Replicación ○ los mismos ítems de datos tienen el mismo valor cuando son leídos desde diferentes réplicas

● Consistencia Eventual

Consistencia ● Datos desactualizados: stale. ● La replicación aumenta la ventana de inconsistencia. ● La consistencia requerida no es global a la aplicación. ○

Se puede usar consistencia débil la mayor parte del tiempo

● Consistencia de Sesión - Read-your-Write ○ sticky session o session affinity (atada a un nodo) ■ Problemas en Master-Slave. ○ Version Stamp. ■ Cada interacción incluye el último version stamp visto por la sesión. ■ El nodo de servidor debe asegurarse de que tiene las actualizaciones que incluyen esa version stamp antes de responder a una solicitud

Relajando la consistencia Consistencia

tradeoff

Otras cosas

● Niveles de aislamiento en SQL ● Dependiendo del dominio ● Sistemas que olvidan completamente las transacciones ● Interactuar con sistemas externos

CAP - BASE - ACID

Teorema CAP ● Consistency: Todos ven los mismos datos al mismo tiempo ● Availability: Si se puede comunicar con un nodo en el cluster entonces se pueden leer y escribir datos. ○

“every request received by a non failing node in the system must result in a response”

● Partition tolerance: El cluster puede sobrevivir a roturas de comunicación que lo dividan en particiones que no pueden comunicarse entre ellas.

Teorema CAP ● Eric Brewer: Towards robust distributed systems 2000 ○

Proceedings of the nineteenth annual ACM symposium on Principles of distributed computing

● Seth Gilbert Nancy Lynch: Brewer’s Conjecture and the Feasibility of Consistent, Available, Partition-Tolerant Web Services ○

ACM SIGACT Volume 33 Issue 2, June 2002

● Dado C, A y P: sólo se puede tener un máximo de dos de estas propiedades para cualquier sistema de datos compartidos

Teorema CAP

CAP - Falacias de la computación distribuida ● ● ● ● ● ● ● ●

La red es fiable. La latencia es cero. El ancho de banda es infinito. La red es segura. La topología no cambia. Hay un administrador. El costo del transporte es cero. La red es homogénea.

Fallos de red le suceden a su sistema y no puede elegir cuando se producen.

Teorema CAP Fallos de red le suceden a su sistema y no puede elegir cuando se producen.

● Dado que la red falla: Hay que tolerar particiones! ● CP - Consistency/Partition Tolerance ● AP - Availability/Partition Tolerance ● No es una decisión binaria. Un poco de uno a costa del otro. ● Pero las particiones pueden ser raras, por lo cual CAP podría permitir C y A la mayor parte del tiempo.

CAP en el mundo real ● Boston y Bs As deben ponerse comunicarse ○ Acordar la serialización de sus requerimientos ○ Si se cae la red se pierde Disponibilidad (Availability) ● Designar un nodo como Master. ○ Pero otro nodo no puede reservar: se pierde disponibilidad ● Permitir que ambos acepten reservas ○ Depende del dominio.

CAP - Eric Brewer 2012 ● I think this was the right phrasing for 2000 ○ But probably not for 2010

ACID vs BASE ● ACID ○

○

○ ○

Atomic: Una transacción tiene éxito o no. Las transacciones son completas Consistent: Una transacción no puede dejar la BD en un estado inconsistente Isolated: Las transacciones no interfieren entre si Durable: Las transacciones completas persisten incluso si el sistema falla

● BASE ○

○

○

Basic Availability: Puede haber una falla parcial en alguna parte del sistema distribuido y el resto sigue trabajando Soft-state: Los datos pueden ser sobreescritos por datos más recientes Eventual consistency: Algunas veces la BD puede estar inconsistente

Durabilidad ● Durabilidad vs. Performance. ○ Datos en memoria. ○ A menudo, se puede especificar las necesidades durabilidad por cada llamada, de tal manera que las actualizaciones más importantes pueden forzar su escritura a disco.

● Durabilidad de replicación ○ Un nodo puede procesar una actualización y falla antes de que se replique en otros nodos ○ Master/Esclavo: Se puede mejorar esperando por algunas réplicas antes confirmar al cliente.

Quórum ● Mientras más nodos se vean involucrados en un requerimiento hay mayor posibilidad de evitar inconsistencia ● Quorum ○ Factor de replicación N (número de nodos involucrados en replicación) ○ W (write quórum): W > N/2 (Sólo una escritura puede tener mayoría) ○ R (read quórum): R + W > N W = N y R= 1

Optimizado para lectura. Fuerte consistencia

W=1 y R= N

Optimizado para escritura. Fuerte Consistencia

W + R N

Consistencia fuerte. Una lectura lee al menos una copia actualizada

Modelos de distribución ● Single Server ● Sharding ● Master-Slave Replication ● Peer-to-Peer Replication

Sharding ● Idea: dividir los datos en varios servidores. ○ Motivación: balancear la carga de datos Si tenemos 4 servidores, cada uno de ellos debe manejar el 25% de la información total. Ejemplo: clientes divididos en varios servidores

Clientes de:

A-G

H-M

Nota: esta es una posible división. Puede haber miles.

N-S

T-Z

Sharding - características ● Balanceo de carga variable ○ No posee distribución uniforme: hay más clientes con nombre entre las letras C y H que en el resto. ● Solución: auto-sharding La propia base de datos distribuye la información ingresada en los distintos servidores.

● Si empezamos utilizando un sólo servidor y luego queremos aplicar sharding el pasaje no es trivial. ● Si se sabe que va a crecer es mejor ya armarlo de principio

● ¿Qué sucede si se rompe un nodo?

Master-Slave Replication ● Master: primer encargado de recibir los cambios en la información.

● Slave: periódicamente se actualiza este servidor con la información de Master. Puede haber más de uno.

Master-Slave Replication ● Bueno para escenarios con muchas lecturas ○

Se puede distribuir las lecturas en cada uno de los Slaves. De esta forma se distribuye la carga.

● Siempre es bueno hacer backups. Y más si son automáticos. ● Problema de consistencia ○ ○

¿Cuándo actualizo el/los Slave/s? Teniendo los reads distribuidos a los Slaves: dos clientes pueden leer de dos Slaves distintos y obtener datos distintos si justo en ese momento se están actualizando los servidores. Ni hablar si en este proceso se rompe el Master.

Peer-to-Peer Replication ● No tengamos Master! Anarquia! ● Todos los servidores tienen el mismo peso. ● Se actualizan periódicamente entre sí.

Seguimos con problemas de consistencia! ● Lecturas de un ítem actualizado en otro nodo. ● Dos lecturas en dos nodos distintos.

Sharding y Replication ● Podemos aplicar ambas técnicas.

Master: Clientes A a la M Slave: Clientes N a la Z

Master: Clientes N a la Z Slave: Clientes A a la M

● Usado en Column-family database ● Se pone más interesante teniendo más de dos nodos

Bibliografía ● NoSQL for Mere Mortals - Dan Sullivan ● NoSQL Distilled. A Brief Guide to the Emerging World of Polyglot Persistence - Pramod J. Sadalage y Martin Fowler ● Mining of Massive Datasets - Jure Leskovec, Anand Rajarama y Jeffrey D. Ullman ● Hadoop MapReduce Cookbook - Srinath Perera y Thilina Gunarathne