STORAGE NOSQL

I datastore di tipo relazionale garantiscono le proprietà ACID:

- Atomicity: le transazioni non possono avvenire parzialmente, o viene eseguita per intero oppure
non lascia alcun effetto sul sistema (regola “all or nothing”)
- Consistency: dopo una transazione, il database permane in uno stato corretto
- Isolation: I risultati di una transazione non completata non sono visibili alle altre transazioni
- Durability: I cambiamenti dovuti ad una transazione sono scritti su disco prima di mandare in
commit la transazione, in questo modo non si ha perdita di dati se c’è una failure

I vincoli di un RDBMS sono:

- Vincoli sul dominio di ogni attributo: ovvero restrizione sull’insieme dei possibili valori che
possono essere assunti da un attributo
- Vincoli di integrità delle entità: le chiavi primarie non possono essere nulle
- Vincoli di integrità referenziale: per mantenere la consistenza tra tutte le tuple in due relazioni,
ogni valore di un attributo in una relazione deve esistere come valore di un altro attributo nella
seconda relazione
- Foreign key: la chiave di una relazione deve coincidere con la chiave primaria di un’altra
relazione

Pro Contro
- Modello di consistenza ben definito (tipicamente - Performance e scalabilità non buone
linearizzabile o serializzabile) - Supporto non ottimale per strutture dati
- Proprietà ACID complesse
- I vincoli di integrità referenziale e quelli sulle entità - I DBMS commerciali sono più costosi
garantiscono integrità sulle relazioni - La creazione delle query richiede la completa
- Sono adatti ad applicazioni OLTP(Online conoscenza del DB
Transaction Processing): applicazioni online in cui si - Possono esserci limiti sulla grandezza di un
gestiscono le transazioni attributo
- Si basano su basi teoriche forti - L’integrazione tra diversi RDBMS può essere
- Stabili e standardizzati complicata

L’uso di RDBMS in una applicazione web non è scalabile, quindi si utilizzano due possibili soluzioni:
 - Replicazione
- Sharding

Replicazione

Si utilizza un’architettura master/worker,col master che coincide con una replica primaria che si occupa
di gestire la replicazione dell’operazione di scrittura su tutte le repliche (mentre quelle di lettura
possono avvenire su qualunque replica)

In questo modo, ho scalabilità sulle operazioni di lettura, ma non di scrittura

Sharding

Partizionamento dei dati su vari server separati.

Ho scalabilità sulle operazioni di lettura e scrittura,ma non posso eseguire transazioni su dati che
coinvolgono molteplici shard.

Per determinare a quale shard assegnare ad un server, si usa il consistent hashing.

Come si vede dalla figura, la scalabilità di un RDBMS è costosa ed inefficiente

Per ovviare a questo problema, è stato introdotto un data store non relazionale.

Le feature principali sono:

- Supporto a schemi flessibili: non c’è bisogno di avere un numero fisso di colonne in una tabella
- Scaling orizzonale: si possono partizionare e processare i dati su nodi distribuiti
- Alta disponibilità: dovuta alla replicazione dei dati su vari nodi
 - Utilizzo di una architettura shared-nothing: non ho spazio di memorizzazione condiviso e quindi
evito problemi di accesso in concorrenza
- Si evita tutto ciò che può introdurre complessità, come ad esempio le operazioni di join
- Supporto a modelli di consistenza meno stringenti, dovuti alla proprietà BASE (invece che ACID)

Le proprietà BASE sono:

- Basically Available: il sistema è disponibile per la maggior parte del tempo e possono esistere
dei sottosistemi che potrebbero non essere disponibili per un certo intervallo di tempo.
Si contrappone alla Availability dell’ACID
- Soft State: la persistenza dei dati è a carico degli utenti. Si contrappone alla Durability dell’ACID
- Eventually consistent: prima o poi i dati diventeranno consistenti tra le repliche, ma per un
periodo (finestra di consistenza) utenti che accedono allo stesso dato su repliche differenti,
potrebbero avere risultati diversi

ACID BASE
- Availability - Basically Available
- Consistency - Soft State
- Isolation - Eventually consistent
- Durability
Approccio ottimistico, i conflitti possono
Approccio pessimistico, si cerca di avvenire ma vengono trovati e risolti
prevenire eventuali conflitti (di solito con tramite:
l’utilizzo di write locks, che possono
 Conditional updated: si controlla il
portare a deadlocks)
valore prima di aggiornarlo
Non è scalabile se si gestiscono grandissime  Save both updates: si tiene traccia del
quantità di dati fatto di avere due dati in conflitto per
poi farne il merge (oppure favorire la
scrittura più recente
La differenza sostanziale riguarda la consistenza:

Come si vede in figura, la scalabilità di un database NoSQL può essere ottenuta con dei costi moderati:
 PRO CONTRO

- Facilmente scalabile - Non ho garanzie ACID

- Ottime performance all’aumentare dei - Non avendo uno schema fisso, non ho un
dati modello di storage comune
- Condivisione di dati tra server - Non ho un vero e proprio standard
- Availability e Fault Tolerance garantiti - Supporto limitato verso operazioni
tramite replicazione aggregate (somme, medie, conteggi)
- Supporto a strutture dati ed oggetti - Pessime performance per join complesse
complessi - Non esiste un approccio ben definito per
- Supporto a dati non strutturati la progettazione del DB
- Retrieve dei dati molto rapido

I sistemi NoSQL possono avere differenti data models:

- Modelli aggregate-oriented: Key-Value, Documenti, Column-Family

- Graph-Based

Modelli Aggregati
In questo modello, ogni dato può avere una struttura molto più complessa di quello che si avrebbe con
una riga del modello relazionale.

Overview sui modelli NoSQL: [Link]

Per quanto riguarda le transazioni, c’è un supporto parziale: le operazioni sono atomiche solo nel singolo
aggregato. Le transazioni che invece richiedono l’accesso a più aggregati non possono garantirlo e
quindi, in caso di update multipli sullo stesso aggregato, potrebbero esserci letture inconsistenti.
Modello Key-Value

I dati sono raccolti come insieme di coppie (chiave,valore).

Sono modelli aggregate-oriented: ci sono molti aggregati ed ogni aggregato ha la sua chiave. Per
accedere ad un aggregato, si fa una ricerca in base alla chiave

I datastore chiave-valore possono essere di vario tipo:

 Possono ordinare le chiavi in modo da fare delle ricerche più rapide

 Alcuni lavorano su RAM, altri su SSD o HDD
 Alcuni datastore consentono di definire delle User Defined Function (UDF) per aggiungere delle
operazioni che possono essere fatte sui dati

In questo tipo di datastore, ci possono essere diversi modelli di consistenza (dalla eventual consistency a
quella serializzabile).

Uno dei problemi principali è che, partendo da un insieme di coppie (chiave,valore), non è possibile
effettuare delle query considerando il valore (non posso fare delle query che nel DB relazionale farei con
la clausola WHERE).

Use case per i datastore Key-Value:

- Salvatagio di informazioni di sessione di una web app: assegno ad ogni sessione un ID e salvo
tutto ciò che riguarda quella sessione facendo un’operazione di put. Le informazioni possono
essere poi lette tramite operazione di get
- Definizione del profilo di un utente
- Salvataggio dati del carrello: salvando tutte le informazioni dei prodotti del carrello con chiave =
user ID
- Raccomandazione di prodotti
Modello basato su documenti

Un documento è un insieme di attributi e dati, ad esempio in formato JSON o YAML.

È simile al modello key-value, ma adesso posso utilizzare delle query anche in base alla struttura interna
del documento (col chiave-valore, potevo solo accedere al valore)

La differenza rispetto a delle tabelle SQL è che i documenti non devono avere tutti la stessa struttura,
rendendo questo modello molto più flessibile (le applicazioni possono salvare dati diversi se cambiano i
requisiti, senza la necessità di effettuare delle migrazioni)

Le operazioni tipiche sono quelle CRUD (Create, Retrieve, Update e Delete),ma non sono standardizzate
(ogni implementazione può essere implementata in modo leggermente diverso).

Le operazioni di scrittura/lettura nello stesso documento tipicamente sono atomiche, ma non è detto
che lo siano anche tra documenti diversi

Considerazioni su scelte progettuali

Come modellare una relazione 1:N?

- One-to-few: embedding, ovvero invece di avere 2 o più oggetti tra cui definisco una relazione,
incorporo il valore a cui sono “collegato” direttamente all’oggetto che gli fa riferimento. Miglioro
la lettura (perchè ne faccio solo una) ma occupo più spazio
Un esempio è quello in cui devo assegnare ad una persona tutti gli indirizzi in cui abita. Dato che
in generale sono pochi, posso fare embedding e leggerli tutti con una sola lettura
- One-to-many: lascio la referenziazione. Un esempio è la raccolta di tutti i pezzi di ricambio
disponibili per una certa automobile. In questo caso posso avere nell’oggetto automobile i
“puntatori” ai singoli pezzi di ricambio.
- One-to-big: parent-referencing. Un esempio può essere una attività di logging, in cui faccio una
referenziazione al contrario (invece che dal parent verso gli oggetti puntati, dagli oggetti puntati
al parent). Quindi potrei far puntare la macchina all’evento a cui fa riferimento invece che far
fare al server un riferimento a tutti i possibili log
 In questo modo evito di avere un numero enorme di riferimenti.

Normalizzazione o Denormalizzazione?

Normalizzazione = descrivo le relazioni utilizzando dei riferimenti tra i diversi documenti

In generale, è consigliabile utilizzare modelli di dati normalizzati quando l’embedding porterebbe ad una
elevata duplicazione di dati, non avendo quindi un sufficiente vantaggio in termini di letture.

La normalizzazione inoltre può essere usata per tutte le situazioni in cui si vuole modellare una relazione
many-to-many o per modellare dei dataset con tanti livelli di gerarchie.

Denormalizzazione = metto tutti i dati che mi servono in un singolo documento

In questo modo ho tutte le informazioni che mi servono in un singolo record, quindi l’aggiornamento
delle informazioni per quel record sono più rapide e posso modificare tutto ciò che riguarda il
documento con una singola operazione atomica
Il lato negativo è che sono limitato sulla grandezza del singolo documento e non posso fare scritture
atomiche su più documenti insieme.

Dunque la normalizzazione ha senso solo quando ho un alto tasso di scritture

Use case per i modelli a documento:

- Adatti quando bisogna salvare grandi quantità di dati semi strutturati, con un numero variabile
di attributi (testi, messaggi) che richiederebbero una grande quantità di null in un RDBMS
Un esempio possono essere dei dati di log o dei commenti

Quando non conviene usarli:

- Quando servono transazioni che variano tra molti documenti

- Quando le query sono su dati che cambiano struttura in modo molto frequente: in quel caso la
sua struttura verrà memorizzata dal datastore nel livello di granularità più basso

COLUMN FAMILY DATA MODEL

Simile al modello chiave-valore, ma il valore può avere attributi multipli (colonne) che possono a loro
volta essere organizzate in famiglie

Ad una certa chiave di riga, assegno due famiglie di attributi: quella sulla famiglia (contenenti
informazioni su nome e indirizzo) e quella sugli ordini

Digressione: Row-Store vs Column-store per i database

Il Row-Store ci permette di avere performance migliori quando faccio operazioni su grandi insiemi di dati su tutta la tabella

Il column-store ci permette di accededere solo ai dati che ci servono (con il row-store dovrei leggere la riga e scartare tutti quei
dati che non mi interessano)

Nel column-family model, può accadere che le righe e le colonne di una stessa tabella possano essere
divise tra diversi server tramite sharding per massimizzare la scalabilità.

Inoltre le famiglie di colonne vengono memorizzate nella stessa partizione.

Sono molto adatti per situazioni in cui si hanno molte letture e poche scritture.

Proprietà del column-family store:

- Ogni colonna deve far parte di una singola famiglia di colonne (non posso avere la stessa
colonna che appartiene a due famiglie diverse)
- Righe differenti appartenenti alla stessa tabella possono avere un numero differente di colonne
- Posso pensare alla struttura dei dati in due modi:
 Orientati alle righe: ogni riga rappresenta un aggregato (ad esempio l’utente con
ID= 1234) e la famiglia di colonne rappresentano dei chunks di dati appartenenti
all’aggregato (profilo dell’utente, storico degli ordini...)
 Orientati alle colonne: ogni famiglia di colonne definisce un tipo di record (ad es.
il profilo utente_ ed ogni riga è l’insieme di record che appartengono a tutte le
famiglie di colonne che abbiamo su quella specifica riga

Use case per Column-Family stores:

- Query che coinvolgono solo qualche colonna

- Aggregazione che coinvolgono grandi quantità di dati (ad es. calcolo della media dei valori di una
colonna)
- Applicazioni con un potenziale volume di dati molto grande
- Applicazioni geograficamente distribuite tra multipli data center

Graph Data Model

Usa delle strutture a grafo per rappresentare i dati.

- Nodi = entità che hanno un insieme di attributi

- Archi = relazioni tra entità (ad esempio la pubblicazione di un commento). Possono essere diretti
o indiretti

Sia i nodi che gli archi possono avere delle loro proprietà rappresentate con coppie (chiave,valore)
Pro:

- Ogni nodo conosce i suoi adiacenti e può arrivarci in un numero finito di passi (ognuno con
stesso costo)

Contro:

- Scalabilità orizzontale: quando ho nodi del grafo memorizzati su server differenti, ho un degrado
di prestazioni
- Sharding difficile da implementare
- Progettarli richiede uno sforzo mentale considerevole

L’utilizzo di database a grafo è consigliato per applicazioni in cui si vuole modellare l’interazione tra i dati
(social network, recommendation systems, path finding in problemi di navigazione)

USE CASES
Amazon Dynamo

Key-value data store di Amazon che garantisce AP (Availability e Partition Tolerance)

Ha delle API semplici che espongono operazioni di get e put.

Soddisfano dei Service Level Agreements molto stringenti sul tempo di risposta (circa 300 ms con un
carico di richieste di 500 richieste/secondo)

Principi di progettazione

Adotta un modello BASE: lascio avvenire i conflitti per poi risolverli.

La cosa importante è capire quando risolvere i conflitti e chi deve risolverli:

- Quando: la risoluzione viene fatta durante le read (invece che durante le write), always
writeable data store
- Chi: i data store o le applicazioni (qualora sia il data store, vengono usate policy semplici come la
last write wins)

Un altro principio è quello della scalabilità incrementale, ovvero la capacità di fare scale out senza grandi
impatti sul sistema.

Dynamo inoltre ha un elevato grado di decentralizzazione

I problemi risolti con le relative tecniche di risoluzione sono riassunti in tabella:

Il partizionamento dei dati avviene tramite consistent hashing, simile a Chord ma senza il concetto di
finger table (il routing si fa passando da un nodo all’altro).
I nodi sono virtuali, dunque un nodo fisico può essere responsabile di più nodi virtuali. Inoltre ciascun
nodo gestisce una quantità di oggetti che è proporzionale alla capacità del nodo stesso (questo perchè
non è detto che i server abbiano tutti le stesse capacità)
La replicazione permette di ottenere alta disponibilità.

Ogni oggetto è replicato su N nodi e ciascun nodo mantiene una preference list contenente la lista dei
nodi responsabili per lo store di una particolare key.

Ad esempio in figura, l’oggetto identificato dalla chiave K è replicato sui nodi B,C e D.

In particolare il nodo D andrà a memorizzare anche tutte le chiavi che sono nel range (A,B]. (B,C] e (C,D]

L’alta disponibilità per le write viene ottenuta tramite l’uso di clock vettoriali che vengono utilizzati per
riconciliare i conflitti durante le operazioni di scrittura. Dunque avrò diverse versioni dell’oggetto che
dovranno poi essere riconciliate

Per gestire i fallimenti temporanei, viene utilizzato un quorum flessibile sul numero di letture/scritture

Per gestire la tolleranza ai guasti, viene utilizzato un algoritmo di gossiping per capire quali sono i nodi
nel sistema e diffondere informazioni relative al fallimento dei nodi.
Vengono inoltre usati degli alberi di Merkle per rilevare inconsistenze dei dati dovute al fallimento di
nodi

Use Case: Bigtable

Prodotto ad uso interno da Google, per poter essere usato con Map-Reduce. Si basa su GFS, Chubby
(equivalente Zookeeper) e SSTable.

Caratteristiche:

La caratteristica fondamentale è il fatto che tutto viene gestito da una sola grande tabella le cui righe
sono distribuite su molteplici server e memorizzate a livello di storage utilizzando il GFS.

È fault tolerant, scalabile e autogestito (caratteristiche self*)

Sistema CP: consistente e tollerante alle partizioni

Il modello dei dati è composto da:

- Tabelle:
o Mappa ordinata, distribuita e multidimensionale, resa persistente con SSTable e GFS
- Righe:
o Ordinate sulla chiave di riga con ordine lessicografico
o Ogni lettura/scrittura su una riga è atomica
- Colonne:
o Unità di base su cui fare l’accesso ai dati
o Righe differenti possono avere colonne differenti (la tabella è sparsa)
o Si possono definire famiglie di colonne

Analizziamo le proprietà delle tabelle:

Multi dimensionali

Le righe e le famiglie di colonne identificano i dati secondo una gerarchia con 3 dimensioni di
indicizzazione (righe, colonne, famiglie di colonne)

Si può vedere come l’ordinamento delle chiavi di riga avvenga in modo lessicografico

Time Based

Oltre alle 3 dimensioni di indicizzazioni, ce n’è una quarta data dal tempo.

Ogni cella ha diverse versioni, identificate da timestamp

Vengono dei finiti dei Tablet: insieme consecutivo di righe salvate insieme, e rappresentano l’unità base
per la memorizzazione e la distribuzione dei dati. Diventa quindi importante scegliere bene la chiave di
riga per fare le query (per fare in modo di avere i dati che ci interessano all’interno della stessa tablet)

Le tablets sono divise dal sistema quando diventano troppo grandi ed ognuna di esse è gestito da un
solo tablet server

Architettura:

Composta da 3 componenti:

- Master Server
- Tablets Server
- Client Library

Master Server

Singolo server che rileva aggiunte o cancellazioni di tablet servers, funge da load balancer tra i tablet
servers e da garbage collector per GFS

Inoltre, assegna i tablets ai tablet servers

Tablet Servers

Possono essere molti e possono essere aggiunti o rimossi in modo dinamico.

Ogni tablet server può :

- Gestire un insieme di tablets (tra i 10 e i 1000)

 - Gestire le richieste di scrittura/lettura
- Dividere i tablets quando sono troppo grandi

Client library

Libreria utilizzata da ogni client.

Viene utilizzata per comunicare con i tablets server (la comunicazione con il master avviene solo per
comunicare i metadati)

3 componenti esterni che costituiscono Big Table sono:

- Google File System per lo storage

- Chubby per offrire un sistema di lock distribuito
- Cluster scheduler per schedulare i job sui cluster server

Chubby

Lock service distribuito e altamente disponibile.

Per mantenere il locking utilizza una struttura simile ad un file system (mantiene un albero per
identificare quale è la porzione dei dati sui quali prendere il lock).

Utilizza l’algoritmo di consenso Paxos per mantenere le repliche consistenti.

Nel contesto di Big Table viene utilizzato per diversi scopi:

- Si assicura che solo un master è attivo

- Meccanismo di monitoraggio del corretto funzionamento dei tablet server
- Mantiene l’organizzazione dello schema (quali sono le righe, quali sono le colonne e quali
colonne compongono una famiglia)
- Mantiene delle liste di controllo degli accessi

Chubby mantiene inoltre la locazione della root tablet,che contiene tutti i metadati delle altre tablets
(ogni metadato rappresenta la posizione di un insieme di tablets)

Viene fatto client-side caching per evitare ogni volta di passare per la root table

Fase di startup del master:

- Richiede un ID unico a Chubby

- Scansiona la tablet servers directory di Chubby per trovare i server attivi
- Comunica con questi server per sapere quali tablet sono a loro assegnati
 - Scansiona la tabella dei metadati per trovare dei tablets che non sono assegnati a nessun server.
Per farlo, controlla periodicamente che su Chubby risulti il lock di un tablet server (quando il
tablet server diventa attivo, prende un lock su Chubby)

SSTable

Formato dei file utilizzato per salvare i dati di BigDable in modo duraturo.

È una mappa (chiave,valore) persistente e immutabile, ordinata in base alla chiave.

Viene salvata come di una serie di blocchi di 64Kb più un blocco (che viene caricato in memoria) che
permette di localizzare gli altri blocchi.

Per velocizzare le letture, viene usato un filtro di Bloom per verificare se la riga esiste senza dover
accedere alla SSTable, prima di accedere alla SSTable sul disco.

Filtro Bloom: struttura dati efficiente in termini di velocità di accesso, utilizzata per verificare la presenza
di un elemento in un certo insieme. È probabilistica: stabilisce se un elemento certamente non è
nell’insieme oppure se potrebbe esserci (dunque posso avere dei falsi positivi, ma non falsi negativi: se
un elemento non è contenuto ne sono certo, altrimenti posso avere la situazione in cui mi risulta che
l’elemento è presente ma poi in realtà non c’è)

Per supportare delle scritture veloci, prima si scrive in memoria e poi viene fatto il flush su disco.

Mantengo un log di commit su cui memorizzo l’ordine delle varie operazioni di scrittura. Le write che
sono state committate recentemente vengono anche messe in una cache in memoria, mentre quelle più
vecchie vengono messe in una serie di SSTables.

Quando faccio operazioni di lettura, può accadere che le informazioni sono non memorizzate su disco
nelle SSTable , ma sono ancora nelle memtable. Quindi nelle operazioni di lettura faccio un merge tra la
memtable e le SSTable.
Un tablet server, per poter caricare un tablet, esegue le seguenti istruzioni:

- Trova la posizione del tablet tramite i metadati (includono una lista di SSTable)
- Legge l’indice della SSTable
- Legge il log di commit e ricostruisce il contenuto della memtable

Non si ha scalabilità quando ho una lettura in un punto qualunque: questo perchè le tablet sono
ordinate in modo lessicografico (mentre se faccio una scansione di righe tra loro consecutive, ho
prestazioni elevate)

Non ho invece grande differenza per le scritture (perchè avvengono sulla memtable, non ho una
differenza se le scritture sono su righe vicine)

La consistenza forte di BigTable è data dal fatto che solo un tablet server è responsabile di un certo
insieme di dati

Abbiamo un degrado di disponibilità quando un tablet server subisce un fallimento

- In quel caso, la sua porzione di dati è indisponibile finchè non gli viene assegnato un nuovo
tablet server (NB, posso recuperare i dati perchè le tablet sono GESTITE dai tablet servers, ma
MEMORIZZATE nel GFS, dunque accessibili)

Confronto tra Dynamo e BigTable:

Cloud BigTable

BigTable offerto come servizio cloud, che offre le stesse cose di BigTable.
In questo caso supporto anche le replicazioni multi regione, ma perdiamo di consistenza (che diventa
finale)
CASSANDRA
Sviluppato da Facebook, prende spunto da Dynamo e da BigTable.

Da Dynamo prende:

- Architettura P2P
- Discovery e fault detection basati su gossiping

Da BigTable prende:

- Dati organizzati secondo il modello column-based

- La architettura di storage (SSTable, memtable)

Caratteristiche di Cassandra:

- Alta disponibilità e scalabilità incrementale

- Supporto molto robusto alla scalabilità geografica (che va un pò contro l’uso di un pattern
master worker. Se il master è in un’area geografica differente rispetto al worker, ho molta
latenza) Per risolvere la cosa, Cassandra usa una policy di replicazione senza master, simile a
quella di Dynamo. Inoltre la replicazione è asincrona (perdo consistenza)
- Tutte le considerazioni fatte su righe/colonne di Big Table valgono anche per Cassandra
- Sistema orientato alle write, al contrario di Big Table che era orientato alle read
- Maggiore enfasi sulla denormalizzazione rispetto a normalizzazioni e joins
Consistenza:

La consistenza viene gestita in modo decentralizzato tramite protocolli quorum based:

 Se R+W > N e W > N/2 + 1, ho strong consistency

Vari livelli di consistenza disponibili, che possono essere settati anche su una singola query:

- ONE: solo una replica deve rispondere

- QUORUM: la maggioranza delle repliche deve rispondere
- ALL: tutte le repliche devono rispondere
- LOCAL_QUORUM: la maggioranza delle repliche in un datacenter locale deve rispondere

NEO4J
Database a grafo con proprietà ACID

Ogni nodo ha una label, per poterlo raggruppare in insiemi

Ad ogni nodo/arco aggiungo delle proprietà che sono della forma nome-valore

La replicazione è gestita tramite architettura master-worker con primary backup:

- Singolo read/write master e read-only workers multipli

- Non ho partizioni su server multipli (dunque ho limitzioni sulla dimensione dei dati)

Il throughput dei dati viene incrementato tramite una cache multi livello
Neo4j utilizza Cypher come linguaggio per ottenere i dati

Grazie alla sua natura a grafo, possiamo trovare algoritmi come Page Rank per trovare i nodi più
influenti oppure algoritmi come Louvain per trovare delle comunità nel grafo

Social Network Analysis

Possiamo definire degli algoritmi di centralità sulla base di alcune misure come la Degree Centrality, la
Betweenness centrality e la PageRank centrality

Degree Centrality

Numero di archi entranti o uscenti da un nodo

Non sempre però è una misura sufficiente:

Il nodo 2 centrale del grafo a sinistra dovrebbe essere più centrale rispetto a quello di sinistra.

Possiamo quindi modellare la centralità di un nodo come l’importanza di quel nodo rispetto alla
connessione rispetto agli altri nodi del grafo, con la Betweennes Centrality

Betweennes Centrality
Quantifica il numero di volte in cui un nodo fa da ponte rispetto al cammino minimo tra due nodi
In questi esempi il nodo x ha la maggior betweennes rispetto ad y

PageRanks centrality

Algoritmo di Google per fare il ranking delle pagine:

L’equazione è ricorsiva e si ferma finchè il calcolo non converge

Community Detection

L’obiettivo è trovare una sottorete in cui i nodi hanno molti più archi nei nodi della sottorete rispetto ai
nodi di altre sottoreti

Avviene tramite algoritmo di Louvain, il cui obiettivo è massimizzare la modularita, un valore tra -1 e 1
che misura la densità di connessioni dentro una comunità rispetto alla densità di connessioni verso le
altre comunità

Avviene in due fasi ripetute:

1. Ogni nodo della rete viene assegnato alla sua comunità. Successivamente, ogni nodo viene
spostato in una comunità adiacente e ne viene calcolato il cambio di modularità (questo viene
fatto per ogni comunità adiacente). Il nodo verrà quindi assegnato alla comunità che ha
mostrato il maggior incremento di modularità
2. I nodi vengono raggruppati in base alla comunità e viene ripetuto il passo 1

Complessità O(N^2)

Considerazioni finali sui datastore NoSql

- Non c’è un tipo di datastore che funziona per tutto, dipende da:
 Distribuzione degli accessi in scrittura/lettura: ovvero la distribuzione di
scritture/letture e accesso random/sequenziale ai dati
 Proprietà dei dati: volume dei dati, flessibilità dello schema, complessità
- Tipo di query
- Requisiti non funzionali, come:
 Performance
 Scalabilità
 Consistenza
 Parzionamento
 Replicazione
 Load Balancing
 CAP tradeoff
- Non c’è un chiaro vincitore in termini di performance

Spesso utilizzare un singolo data store engine non porta a soluzioni ottime, dunque ci sono due approcci:

- Polyglot persistence: utilizzo data-store multipli per la stessa applicazione, in base al caso d’uso
- Multi-model databases: seconda generazione di datastore NoSQL che supportano diversi
modelli di dati

L’uso di questi modelli permette una complessità e costi minori, dovuti al fatto di non dover
mantenere consistenza tra data-store diversi.
Di contro, le performance non sono ottimizzate per nessun modello specifico