[NO-SQL] Il Teorema di CAP e il No-SQL data model

Volendo continuare la serie sulla “filosofia” NO-SQL e sulle prerogative per cui è necessaria (vedi l’articolo riportato su questo blog, “NO-SQL e introduzione a MongoDB“), estrapolo qui le motivazioni e le caratteristiche lette negli articoli riportati su BigDataNERD:

Perché NO-SQL?

Per poter rispondere alla domanda occorre esaminare il “teorema di CAP” e ricordare che un concetto fondamentale degli RDBMS è quello delle “ACID transactions” (A=Atomicity, C=Consistency, I=Isolation, D=Durability)

  • A come Atomicità. La transazione è indivisibile, ossia o tutti gli statements che la compongono vengono applicati ad un database o nessuno.
  • C come Consistenza. Il database deve rimanere in uno stato consistente prima e dopo l’esecuzione di una transazione, quindi non devono verificarsi contraddizioni (inconsistency) tra i dati archiviati nel DB.
  • I come Isolamento. Quando transazioni multiple vengono eseguite da uno o più utenti simultaneamente, una transazione non vede gli effetti delle altre transazioni concorrenti.
  • D come Durabilità. Quando una transazione è stata completata (con un commit), i suoi cambiamenti diventano persistenti, ossia non vengono più persi.

I più comuni e diffusi RDBMS supportano le transazioni ACID e i principi su esposti sembrerebbero bastare. Ma dov’è il problema?

Nell’era del Web 2.0, le applicazioni devono lavorare su bilioni e trilioni di dati ogni giorno e la scalabilità è un concetto che in tale ambito ricopre un ruolo importantissimo. Per questo motivo i database hanno bisogno di essere distribuiti sulla rete per realizzare una scalabilità orizzontale. Esaminiamo qui il concetto di “CAP theorem” per valutare le caratteristiche di un siffatto sistema di storage distribuito dei dati.

Il teorema di CAP fu teorizzato da Eric Brewer nel 2000 (C=Consistency, A=Availability, P=Partition-Tolerance). Per maggiori informazioni si veda il seguente articolo: ACID vs. BASE il Teorema di CAP (di Stefano Pedone).

Nell’ambito di un sistema di storage distribuito, i 3 principi hanno la seguente definizione:

Consistency: se viene scritto un dato in un nodo e viene letto da un altro nodo in un sistema distribuito, il sistema ritornerà l’ultimo valore scritto (quello consistente).

Availability: Ogni nodo di un sistema distribuito deve sempre rispondere ad una query a meno che non sia indisponibile.

Partition-Tolerance: è la capacità di un sistema di essere tollerante ad una aggiunta o una rimozione di un nodo nel sistema distribuito (partizionamento) o alla perdita di messaggi sulla rete.

Secondo la teoria CAP, è impossibile garantire tutti e tre i principi del teorema di CAP. Infatti, si consideri un sistema distribuito e si supponga di aggiornare un dato su un nodo 1 e di leggerlo da un nodo 2, si verificheranno le seguenti conseguenze:

  1. Il nodo 2 deve ritornare l’ultima “miglior” versione del dato (quella consistente) per non violare il principio della Consistenza
  2. Si potrebbe attendere la propagazione del dato modificato nel nodo 2 e, quest’ultimo, potrebbe mettersi in attesa della versione più aggiornata, ma, in un sistema distribuito, si ha un’alta possibilità di perdita del messaggio di aggiornamento e il nodo 2 potrebbe attenderlo a lungo. Così non risponderebbe alle query (indisponibilità), violando il principio dell’Availability
  3. Se volessimo garantire sia la Consistency che l’Availability, non dovremmo partizionare la rete, violando il principio del Partition-Tolerance

Le web applications progettate in ottica Web 2.0, caratterizzate da architetture altamente scalabili e profondamente distribuite con politiche di prossimità geografica, puntano in maniera forte sulla garanzia di alte prestazioni ed estrema disponibilità dei dati. Si trovano quindi ad essere altamente scalabili e partizionate. La filosofia NO-SQL è sbilanciata verso la ridondanza dei nodi e la scalabilità.

Di seguito, si riporta una tabella dei maggiori database NO-SQL del momento:

Il NoSQL data model può essere implementato seguendo differenti approcci a seconda delle strutture dati con cui si rappresentano i record di dato.

  • Famiglie di colonne o “wide column store” (come Cassandra e HBase): le informazioni sono memorizzate in colonne, in coppie chiave/valore. Tipicamente sono usati nell’ambito della memorizzazione distribuita dei dati;
  • Document Store (come CouchDB, MongoDB): le informazioni sono organizzate in “Document“, rappresentati in XML, JSON o BSON, e l’accesso ai dati avviene attraverso API che interrogano veri e propri dizionari. Sono molto usati nello sviluppo di attuali web applications;
  • Key/Value Store (come Membase, Redis): la struttura dati di memorizzazione è una Hash Table (coppia chiave-valore). Indicate per sistemi di caching o Hash Table distribuite;
  • Graph Data Store (come Neo4J, InfoGrid, OrientDB). Il modello di programmazione è il grafo e l’accesso ad archi e nodi avviene attraverso algoritmi di ricerca su grafo. Tipicamente si usano nei social network.

 

[DB] Perché denormalizzare una basedati?

Prima di parlare della denormalizzazione di una basedati, ricordiamo cos’è la sua normalizzazione: è il procedimento che ha come conseguenza la riduzione della ridondanza all’interno del database, e che quindi consente un risparmio in termini di spazio occupato. Tale operazione andrebbe eseguita in fase di progettazione, riuscendo quindi subito ad identificare i dati raggruppabili in tabelle separate da mettere in relazione. Effettuare subito questo procedimento porta anche ad una migliore comprensione del database e dei legami che intercorrono tra le varie tabelle.

Ci sono tre diverse forme di normalizzazione (dette forme normali di Boyce e Codd):

  • la 1° Forma Normale (1NF) consiste nel fare in modo di non presentare gruppi di attributi che si ripetono (ossia ciascun attributo è definito su un dominio con valori atomici) e nel far esistere una chiave primaria per ciascuna relazione (ossia esiste un insieme di attributi, che identifica in modo univoco ogni tupla della relazione)
  • una volta portato il database alla 1° Forma Normale, dobbiamo portarlo alla 2° Forma Normale (2NF), ossia per ogni relazione tutti i campi non chiave dipendono funzionalmente dall’intera chiave composta e non da una parte di essa.
  • la 3° Forma Normale (3NF) si ha quando la relazione è, innanzitutto, in 2° forma normale e tutti gli attributi non-chiave dipendono dalla chiave soltanto, ossia non esistono attributi che dipendono da altri attributi non-chiave.

Per definizione, una relazione R è in forma normale di Boyce e Codd (BCNF) se e solo se è in 3NF e, per ogni dipendenza funzionale non banale X –> Y,  dove X è una superchiave per R.

In questo modo si riducono ulteriormente sia la ridondanza dei dati nelle tabelle che la possibilità di errori umani in fase di inserimento dei dati.

La denormalizzazione, invece, è il processo che permette di ottimizzare le performance in lettura di un database aggiungendo ridondanza nei dati o raggruppandoli. Tale operazione viene effettuata spesso per risolvere l’inefficienza dei database relazionali, visto che, se normalizzati, possono soffrire di pesantezza nel caricamento dei dati.

Quando si valuta la normalizzazione tra le alternative di progettazione di una basedati, è utile tenere presente le diverse tecniche che consentono di denormalizzare intenzionalmente un database. La denormalizzazione intenzionale dei dati può essere motivata dal rilevamento di problemi di prestazioni oppure nel caso in cui si desideri semplificare la creazione di report ad-hoc. I problemi di prestazioni derivano dalle query per le quali, in produzione, è richiesto un numero troppo elevato di join di tabelle con un accesso intensivo al disco. Lo scopo della creazione di report ad-hoc è consentire anche agli utenti finali di eseguire query non strutturate, in quanto è possibile che utenti finali poco esperti non siano certi delle procedure necessarie per ottenere informazioni da più tabelle correlate.

Continua la lettura

Creative Commons License
This work by Francesco Ficetola is licensed under a Creative Commons Attribution 4.0 International License.
Based on a work at www.francescoficetola.it.
Permissions beyond the scope of this license may be available at http://www.francescoficetola.it/2012/06/07/db-perche-denormalizzare-una-basedati/.

[JSON] Introduzione al diffuso formato di scambio dei dati

JSON (JavaScript Object Notation) è un semplice formato per lo scambio di dati. Per le persone è facile da leggere e scrivere, mentre per le macchine risulta facile da generare e analizzarne la sintassi. Si basa su un sottoinsieme del Linguaggio di Programmazione JavaScript, Standard ECMA-262 Terza Edizione – Dicembre 1999.

JSON è un formato di testo completamente indipendente dal linguaggio di programmazione, ma utilizza convenzioni conosciute dai programmatori di linguaggi della famiglia del C, come C, C++, C#, Java, JavaScript, Perl, Python, e molti altri. Questa caratteristica fa di JSON un linguaggio ideale per lo scambio di dati.

JSON è basato su due strutture:

  • Un insieme di coppie nome/valore. In diversi linguaggi, questo è realizzato come un oggetto, un record, uno struct, un dizionario, una tabella hash, un elenco di chiavi o un array associativo.
  • Un elenco ordinato di valori. Nella maggior parte dei linguaggi questo si realizza con un array, un vettore, un elenco o una sequenza.

Queste sono strutture di dati universali. Virtualmente tutti i linguaggi di programmazione moderni li supportano in entrambe le forme. E’ sensato che un formato di dati che è interscambiabile con linguaggi di programmazione debba essere basato su queste strutture.

In JSON:

  • Un oggetto è una serie non ordinata di nomi/valori. Un oggetto inizia con { (parentesi graffa sinistra) e finisce con } (parentesi graffa destra). Ogni nome è seguito da : (due punti) e la coppia di nome/valore sono separata da , (virgola).

  • Un array è una raccolta ordinata di valori. Un array comincia con [ (parentesi quadra sinistra) e finisce con ] (parentesi quadra destra). I valori sono separati da , (virgola).

  • Un valore può essere una stringa tra virgolette, o un numero, o vero o falso o nullo, o un oggetto o un array. Queste strutture possono essere annidate.

  • Una stringa è una raccolta di zero o più caratteri Unicode, tra virgolette; per le sequenze di escape utilizza la barra rovesciata. Un singolo carattere è rappresentato come una stringa di caratteri di lunghezza uno. Una stringa è molto simile ad una stringa C o Java.

  • Un numero è molto simile ad un numero C o Java, a parte il fatto che i formati ottali e esadecimali non sono utilizzati.

I caratteri di spaziatura possono essere inseriti in mezzo a qualsiasi coppia di token.

A parte alcuni dettagli di codifica, questo descrive totalmente il linguaggio.

Fonte: http://www.json.org/json-it.html