Download Bases de Datos NoSql

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 eventual débil. Se podrían leer copias no actualizadas
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