Post on 21-Jul-2015
transcript
The Sequel to SQL:
Le nuove frontiere dei database
Prof Marcello MissiroliUniversità di Modena e Reggio Emilia
XII Settimane della Scienza e della TecnicaIIS Fermo Corni
Modena, 9 Dicembre 2014
Quiz
● 375.000.000 in 0,21 secondi● Il tempo di accesso medio di un SSD è 5ns, 5
nanosecondi = 5.0 × 10-9 secondi● 375.000.000×(5×10-9)=1,78s● Questi sono solo i risultati TROVATI da Google● Il numero delle pagina ANALIZZATE è circa
2.000.000.000.
I database relazionali
● Un grande idea● Una grande tecnologia● Ottime implementazioni● Un linguaggio quasi-standard (SQL) per
l'utilizzo
I database relazionali
● Un'idea del 1970● Boom negli anni 80● Tutti li usano (più o meno consciamente)● Però, oggi il mondo è cambiato (informatico e
non). MOLTO cambiato!
1. “Big data”
Esabyte (10 alla 18) salvati ogni anno nel mondo
Ogni anno creiamo più contenuto digitaledi quanto ne sia stato
creato negli anni precedenti.
La tendenza è In aumento.
(*) Immagine da “NoSQL for Dummies”
2. “Connectivity”
Nel corso del tempo, I dati diventano sempre
più interconnessi. Link, Hashtags, ...
“Con
nett
ività
” de
lle in
form
azio
ni
(*) Immagine da “NoSQL for Dummies”
3. Destrutturazione“C
onne
ttiv
ità”
delle
info
rmaz
ioni
● La tendenza alla personalizzazione impedisce di trovare un modello adatto per tutti.
● Necessario memorizzare molte informazioni per la stessa entità (accelerata dal cosiddetto “web 2.0”)
● Esempi di evoluzione: – “Titolo”
● negli anni 70: Stringa; ● oggi: Titolo multilinguaggio, con ideogrammi, multifont, da sinistra a destra
– “Ricavo da lavoro” ● negli anni 70: float. ● oggi: una lista di possibili lavori (occasionali, stagionali, fissi).
4. Architettura
Anni novanta: database come punto di connessione
(*) Immagine da “NoSQL for Dummies”
4. Architettura
Anni duemila: applicazioni indipendenti e interagenti
(*) Immagine da “NoSQL for Dummies”
Il risultato
Complessità di dati
Pe
rfo
rman
ce
Per tutti questi motivi, i DB relazionali non
sono più adeguati alle necessità delle grandi applicazioni moderne
(*) Immagine da “NoSQL for Dummies”
E che sarebbe?“C
onne
ttiv
ità”
delle
info
rmaz
ioni
● Sta per “Not OnlySQL”● Non vuol dire che SQL e i RDMBS non si
devono più usare!● Indica che ci sono soluzioni che
POTREBBERO funzionare meglio!
CS
C 8
101
- 20
14-2
015
– P.
Mis
sier
Evoluzione dei modelli di dati
(*) Renzo Angles and Claudio Gutierrez. 2008. Survey of graph database models. ACM Comput. Surv. 40, 1, Article 1 (February 2008), 39 pages. DOI=10.1145/1322432.1322433 http://doi.acm.org/10.1145/1322432.1322433
Quattro categorie di NoSQLDB“C
onne
ttiv
ità”
delle
info
rmaz
ioni
● Key-valueDB (Dynomite, Voldermort,TokyoTyrant, ...)
● BigTable DB (Hbase, Hypertable, Cassandra,...)
● Document DB (CouchDB, MongoDB, ...)● GraphDB (Neo4j, Pregel, ...)
GraphDB“C
onne
ttiv
ità”
delle
info
rmaz
ioni
● Come esempio guarderemo quest'ultimo perché....– Il tempo è limitato.
– E' quello che si discosta di più dagli altri
– E' quello che conosco meglio!
Cos'è un grafo?
● Un grafo è un insieme di elementi detti nodi che possono essere collegati fra loro da linee chiamate archi.
(*) Immagine da “A Walk in graph databases”
Grafo: il nodo
● Un identificatore● Varie proprietà● Lista di nodi in uscita
(*) Immagine da “A Walk in graph databases”
Grafo: l'arco
● Un identificatore● Varie proprietà● Un nodo d'ingresso● Un nodo in uscita
(*) Immagine da “A Walk in graph databases”
CS
C 8
101
- 20
14-2
015
– P.
Mis
sierEsempio concreto (in realtà MILIONI di nodi)
Type: userName:pippo
Type: tweetContent:”#saluti a pluto!”
Type: userName:pluto
Type: hashtagValue:”#saluti”
Type: userName:paperino
sentcontains
follo
ws
mentio
ns
follows
CS
C 8
101
- 20
14-2
015
– P.
Mis
sier
Elencare i dieci utenti con più follower
MATCH x-[:FOLLOWS]->y RETURN count(x), y ORDER BY count(x) DESC LIMIT 10
CS
C 8
101
- 20
14-2
015
– P.
Mis
sier
Verificare la teoria dei sei gradi di separazione
Trovare il numero massimo di salti necessari per collegare due qualsiasi utenti
MATCH x-[p:FOLLOWS*]->y RETURN max(length(p))
Pregel / Giraph
● Approccio fortemente parallelo (Bulk Synchronous Parallel)
● Una serie di iterazioni (supersteps)● Ogni vertice richiama una funzione in parallelo● Può leggere e spedire messaggi agli altri nodi● Può decidere di fermarsi● Quando tutti si fermano, l'algoritmo termina
2A∞
B∞
C∞
D∞
E∞
S0
5
30
Inizializzazione
● Tutti i nodi sono inizializzati a “infinito”
● Il nodo di partenza è inizializzato a “0”
● Il nodo di partenza è attivo
2
2
2
2
2A∞
B∞
C∞
D∞
E∞
S0
5
30
Superstep 1
● Il nodo attivo spedisce a tutti i vicini il proprio valore + la distanza
2
2
2
230
5
2
2A∞
B∞
C30
D5
E2
S0
5
30
Superstep 2
● Il nodo S non ha ricevuto messaggi, e si disattiva
● I nodi C,D,E si attivano● Aggiornano il proprio valore, se più
basso di quello memorizzato● Inviano il messaggio ai vicini
(tranne da dove è arrivato il messaggio con valore minimo)
2
2
2
27
432
2A7
B4
C30
D5
E2
S0
5
30
Superstep 3
● I nodi C,D,E non hanno ricevuto messaggi, e si disattivano
● I nodi A e B si attivano● Aggiornano il proprio valore, se più basso di
quello memorizzato (B riceve due messaggi, e memorizza il minore)
● Inviano il messaggio ai vicini (tranne da dove è arrivato il messaggio con valore minimo)
2
2
2
26
9
6
2A6
B4
C6
D5
E2
S0
5
30
Superstep 4
● Il nodo C si attiva● C e A aggiornano il
proprio valore, mentre B no
● C e A Inviano il messaggio
2
2
2
28
36
2A6
B4
C6
D5
E2
S0
5
30
Superstep 5
● A, B, C si disattivano● D ed S si attivano● Nessun
aggiornamento● Nessun messaggio
spedito
2
2
2
2
2A6
B4
C6
D5
E2
S0
5
30
Superstep 6
● D e S si disattivano● Tutti i nodi sono
disattivati: fine algoritmo
2
2
2
2
2A6
B4
C6
D5
E2
S0
5
30
Lo pseudocodice del programma
∀ Node v:
SS0: v.val = +inf;
SSn:
foreach msg in <incoming messages>
minimum = min (min, msg.value)
if (minimum < v.val) {
v.val = minimum;
send v.val + distance(v,v’) to all neighbours v’ except minimum origin
}
2
2
2
2
Riassumendo
● I Database relazionali, adatti a tanti problemi, non sono in grado di gestire la grande mole di dati dell'Information Age
● I Database NoSQL sono una possibile risposta: sono scalabili, flessibili e in grado di sfruttare le architetture parallele
● Non sono in competizione con i RDBMS, quanto uno strumento aggiuntivo a nostra disposizione.
Riassumendo
● Imparare i DB NoSQL è una freccia in più al vostro arco di conoscenza
● Forse al momento sembrano eccessivi, ma l'evoluzione tecnologica è inarrestabile: chi si limita all'esistente, rischia di restare indietro.
Per saperne di più
GRAZIE DELL'ATTENZIONE!
Marcello Missiroli (prof.missiroli@gmail.com)
CREDITSI.Paolo Missier, Dispense del corso “Introduction to Graph
Databases”.II.Tobias Ivarrson, “NoSQL for Dummies”.III. Pierre De Wilde “A Walk in Graph databases”
Per le parti di mia competenza, la licenza è CC BY-SA. Per tutto il resto la licenza è dei rispettivi autori.