NOSQL - INF2030 & CS554: Advanced Database Systems

Anotações extraídas das aulas de INF2030 e do material do curso CS554: Advanced Database Systems

http://www.mathcs.emory.edu/~cheung/Courses/554/

http://www.mathcs.emory.edu/~cheung/Courses/554/Syllabus/91-NOSQL/

Big Data e 5V's

Volume, o q é grande? O limite do armazenamento de cada nó e a possibilidade de distribuir/particionar para melhor aproveitar os recursos computacionais

Velocidade, streaming, tempo real ... maior problema para o mundo Relacional por causa da manutenção da Integridade

Variedade ou Variabilidade, sem estrutura definida, sem uma única estrutura. O mundo Relacional impõe um esquema tabular e único, conhecido a priori (schema on write), que requer um esforço de abstração para transformar o mundo real em tabelas.

O primeiro tema de trabalho de INF2030 envolveu entender o que é serialização em Bancos de Dados Relacionais. No trabalho foi necessário definir re relacionar conceitos como Transação, ACID, Níveis de Isolamento e Locks além do protocolo 2PL. 

Elmasri & Navathe, cap 17 e 18

Escalonamento correto é equivalente a uma execução sequencial de T1 a Tn que preserva a consistência. Um plano serializável deve ser equivalente a uma ordem serial de transações, qualquer ordem, mas não podem produzir um resultado diferente de qualquer combinação serial. 

Read / Write e Write / Write são operações conflitantes. 

prova de 2PL com grafo direcionado acíclico de precedência: se houver ciclo não é serializável, cada transação Ti é um nó, os arcos entre Ti e Tj mostram a ligação entre operações conflitantes, a ordem topológica do DAG é um plano (pode haver mais de um). 

Níveis de isolamento flexibilizam o 2PL, evitar 3 tipos de problemas nas transações (leitura suja, leitura fantasma, leitura não repetida)

O segundo trabalho envolveu o aspecto da Consistência em bancos de dados NoSQL. Nesse trabalho foi necessário entender o Teorema CAP aplicado a sistemas distribuídos, revisar o C e I do ACID e comparar com a proposta BASE (Basically Available, Soft-state, Eventual consistency), conceituar estratégias de replicação, particionamento e escalabilidade. 

Que tipos de aplicações podem abrir mão da consistência forte? Seria um falso dilema entre Desempenho x Consitência? 

The "CAP" Theorem - Desirable properties in distributed systems

Strong Consistency

Ideally: consistency defined as serializability

High availability

Ideally: the distributed system is always available to process user requests

Tolerant to (network) partitioning:

Network failure can partition a distributed system into 2 or more operational systems. Nodes within the same partition can communicate with each other. Nodes in different partition cannot communicate with each other. If both operational halves are allowed to operate, the result may be inconsistent !!!

Ideally: we want all partitions to remain operational.

The CAP Theorem: It is impossible for a distributed system to provide (1) Strong Consistency, (2) High Availability and (3) Tolerance to Partitioning, at the same time

Consequence: The designer of a distributed system must choose 2 of the desirable properties that he/she want to have in his/her system....

In general, NOSQL systems dumps the Strong consistency property and uses less stringent condition named Eventual consistency.  

Characteristics of NOSQL systems

     

- High performance (fast access to data due to a large user population)

Methods to achieve higher performance:

a) Lower the processing load per node by distributing the data/requests over different nodes (sharding) as it increases the level of parallellism

Sharding = horizontal partitioning

Sharding combined with data replication to increase availability and performance

Sharding techniques:

Hashing: Used in key-value NOSQL systems. Data is sharded using the key

Range-based sharding: Data is sharded based on pre-defined ranges of key values and it can handle range-based queries. 

b) Relaxing the data consistency constraint as this will reduce the number of synchronization bottle necks and more processes can run simultaneously. Most of NOSQL systems does not enforce strict serializability as the consistency condition. In "Eventual" consistency, an update is applied to one copy without locking the other copies so the data can be temporally inconsistent (inconsistent window). requires conflict resolution. 

Consistência eventual não preserva a ordem (não é monotônica), a convergência das réplicas para valores idênticos é gradual, considerar o tempo de propagação das atualizações (janela). 

Read your writes: consistência da transação

Abordagem pessimista para lidar com conflitos: evitar

Abordagem otimista para lidar com conflitos: responder, conciliar

- High Availability (almost always operational, the likelihood that the system is operational)

Replication will eliminate any single point failures (SPOF). 

Data replication = placing multiple copies of the data on the system

Replication techniques (for data storage):

a) Master-slave replication:

One of the copies is the master copy and all write operations must apply to the master copy. The slave copies will eventually receive the updates propagated from master. Read operations usually can access any data copy for performance. 

b) Master-master (or multi-master) replication:

Allows read/write to any replica (copy). The write operation includes a time stamp. A reconciliation algorithm propagates the latest update to all replicas eventually. 

Adapting consistent hashing to support data replication: The data item is stored in its hashed range and in the next range. The data can be read from the storage in the hashed range or the read request can be also be serviced by the storage in the next hashed range (Load distribution -> Higher performance). 

Consistent hashing = a modified hashing technique such that when the hash table is resized, only a fraction of the search keys need to be remapped.

- Scalability (accommodate large user population, the ability of a system to handle a growing amount of work)

2 ways to achieve Scalability:

a) Vertical scalability: Handle more load by using faster processors        

b) Horizontal scalability: Handle more load by using more processors        

NOSQL systems are preferable horizontally scalable, processing/storage capacity in NOSQL systems are increased by adding more processing/storage nodes and is employed while the NOSQL system is operational (without downtime). 

O terceiro trabalho foi selecionado a partir de um conjunto de buzzwords que aparecem frequentemente nos materiais sobre NOSQL, são elas:

O meu trabalho foi sobre DHT, ou seja, Distributed Hashed Table

Sobre a questão do "esquema flexível" muito comentada como uma vantagem dos NoSQL temos: 

Beyond SQL: Not Only SQL (NOSQL)

Each relation in SQL systems defines a very strick structure.       

Consequence: "Free format" data cannot be stored in a Relational Data model and cannot therefore be processed by SQL

SQL's (strict) structured data model is too restrictive !!!

Data stored in NOSQL systems has a structure that does not comform to traditional table-based structure

Some NOSQL systems do not use any data description schema (in key-value NoSQL databases, no structure is imposed of the value part) and others use Semi-structured self-describing data like XML documents and JSON documents. 

The application program that access the data is responsible to structure in the data stored (schema on read x schema on write)

Schemaless (dados interpretados a nível de aplicação, não quer dizer sem esquema, não precisa de tratamento de NULOS) x Schemafull (esquema conhecido a priori antes da carga de dados, requer Data Definition Language e tratamento de NULOS)

SQL enforces a strick data consistency:

Consequence: Locking can reduce the level of parallellism. SQL cannot support millions of simultaneous users due to synchronozation bottlenecks. 

Query languages used and its functionality available in NOSQL systems

Completely unstructured data:

CRUD operations - Create (insert data); Read (access data); Update (modify data); Delete (remove data)

Semi-structured data (such as XML):

SCRUD operations - Search (lookup data using limited search criteria) + CRUD

Modelos de dados envolvem dois formalismos: estrutura e linguagem de manipulação. 

Por exemplo, tabelas no modelo relacional são representações no nível conceitual ( o armazenamento interno/persistência não é em tabelas)

O trabalho de conclusão da disciplina envolveu uma apresentação e um artigo (que deverá no futuro ser publicado como MCC do Departamento de Informática) em duplas sobre cada uma das categorias de banco de dados NoSQL. Eu juntamento com o Bruno trabalhamos com Graph Databases e estudamos o Neo4J e o Allegro (farei um post em separado). 

The main five categories of NOSQL systems: 

(1) Key-value based systems

Data model in key-value databases: Data model used is (key, value). A key-value database will only store data in the following format:

Key = a unique identifier associated with the data, used to locate the data item, index on the key field (e.g., a B+-tree) for fast access (Look UP)

Value = the data item itself, example of values: Movies, Images, Text files (such as JSON/XML documents), any string of bytes !!! Pode ser simples ou composto

The user can store any data in the value part but the format of the data that is stored in a key-value database must have the structure although the content is opaque. 

Facilidade para particionar e distribuir, independência das chaves para distribuição arbitrária entre nós.  

DHT

LSM (Log Structured Merge Trees): árvore B+ otimizada para a escrita, não realiza updates

Example: DynamoDB By Amazon (Available in Amazon's cloud services)

Uso para cache de aplicações, lookup chave para recuperar valor mas não tem suporte nativo a busca por valores específicos e nem range, se implementadas estruturas e operações mais complexas dificultam o tratamento de transações atômicas (trade-off)

Ignite: possui linguagem SQL, índices secundários, permite definição de regras de afinidade para particionamento, suporte a transação, ACID, consistent hashing

Redis: índices secundários, suporte a transação atômica, replicação mestre-escravo, não é MPP, manipula dados em memória enquanto a transação está em andamento e persiste em disco o que for "definitivo". 

(2) Document based systems

Text documents in semi-structured format (e.g., XML, JSON)

User can specify an index on a certain type of field in the document, Fast access (search) to documents uses the available indexes

Collections/Buckets: agregar documentos da mesma categoria, poderiam refletir Classes / Entidades a nível macro/modelo, agregar com base na similaridade (de estrutura ou de conteúdo?)

Como modelar relacionamentos entre documentos: Desnormalização, Duplicação, Modelo híbrido de grafos de documentos. Documentos podem referenciar outros (intra ou inter collection) ou podem ter outros documentos embutidos (desnormalização, relacionamentos 0..1, 1..1, 0..*, 1..*, não se aplica a *..*, N x N)

JSON é mais compacto do que XML. 

Example: MongDB (Data storage system for documents in the JSON format, possui conceito de Collection), CouchBase (não tem collection mas tem um atributo de tipo que pode auxiliar no agrupamento), ArangoDB, Virtuoso (XML)

N1QL (usada no CouchBase) parece SQL mas aceita valores não atômicos, Non-first Normal Form Query Language (na primeira forma normal só se aceitam valores atômicos)

MongoDB usa compressão de índice bitmap. 

CouchDB usa MVCC (nível de isolamento, snapshot no início da transação), é lock-free, indexação com B+ tree (tempo de busca é log n), consistência eventual, tem recursos de materialized views, a linguagem cURL é usada para as operações de CRUD nos documentos, tem biblioteca python (onde o dicionário é em formato json)

MongoDB: formato BSON para persistência (nível físico), armazena números como tipos numéricos (não faz conversão para string), transações atômica a nível de um documento, replicação mestre-escravo, particionamento (range, hash ou zona), permite a definição de esquema e possui um validados (JSON schema)

(3) Column based systems

Semelhante ao relacional mas as colunas são agrupadas por características de acesso compartilhadas. Pode ser interpretado como uma extensão do KV onde os valores seriam estruturas aninhadas de pares chave-valor

Particionamento vertical e horizontal

Example: BigTable. Google developed BigTable to store the vast amount of data in: Webpage indexing, Gmail, Google Map, etc...

No BigTable a família de colunas é um esquema flexível. Faz flush de memória em disco. 

Paradigma MapReduce: função Map é aplicada em todos os nós para gerar resultados intermediários com as listas das chaves, cada redutor recebe cada saída das funções de map, necessário coordenar das operações distribuídas, combiner é usado como um pré-reduce para ganho de desempenho reduzindo o tráfego de dados entre nós/máquinas. 

Ecossistema do Haddop: HIVE, Spark

Bloom Filter: identifica falsos positivos mas não identifica falsos negativos, pode ser vetor de bits (bitmap) ou de contadores (counting), checar a possibilidade de um dado estar presente antes de acessar, usa uma ou mais funções de hash, quanto mais elementos maior a chance de retornar falso positivo e quanto maior o tamanho do vetor de bits menor a chande de gerar falso positivo. (HBasse, Cassandra e Big Table)

HBase: open source do Big Table, usa HDFS (FS do Hadoop), CP, armazenamento ordenado no disco pela chave das colunas, o número de versões do dado é configurável, 

Cassandra: permite diferentes níveis de consistência (AP, CP), linguagem CQL (Cassandra Qery Language), utiliza gossip protocol (shared nothing), particionamento por hash, replicação assíncrona, possui conceito de chave primária, parâmetros do Bloom Filter são configuráveis (uso + memória se o % de chance de falso negativo aumentar)

(4) Graph database systems

Data is represented as graphs, Related nodes can be found by traversing the graph

Example: Neo4J (LPG model), AllegroGraph (RDF, Triple Store), Virtuoso, AnzoGraph (MPP distributed graph database) 

RDBMS e Document Stores podem ser usados para armazenar dados em grafos

Matriz ou Lista de Adjacência

Navegação online no grafo: basic query path (caminho + curto, sem repetir nós e/ou arestas), pattern query matching (isomorfismo, achar sub grafos, NP completo em geral e Polinomial em caso de grafos como árvore)

Navegação offline: algoritmos para achar componentes conexos, usar em particionamento

Linguagens: SPARQL (Allegro, Virtuoso), Cypher (Neo4J), Gremlin, AQL (ArangoDB, faz DFS por padrão, BFS é opcional)

CSR: Compressed Sparce Rows, Lista de Adjacências, Lista de Arestas

(5) Polystores

Some NOSQL system use features from 2 different types of NOSQL systems

Example: Cassandra By Facebook. Cassandra is a hybrid system beased on: the key-value and the column-based system

Virtuoso é polystore (grafo em RDF, suporta XQuery e R2RML) assim como o ArangoDB (usa AQL para acessar grafo, lista de vértices e arestas). 

Loosely coupled: queries são traduzidas em linguagens próprias do BD alvo, cada BD alvo ainda mantém autonomia e pode ser acessado pelos seus respectivos sistemas/SGBDs, comumente read only. 

Tightly coupled: os BDs alvos só podem ser acessados pela interface do polystore, permite escrita, usam materialized views

 

Polystore não é multi-modelo.