GESTIONE EFFICIENTE DEI DATI IN UN GESTIONE EFFICIENTE DEI DATI IN UN DATA STREAM MANAGEMENT SYSTEM DATA STREAM MANAGEMENT SYSTEM
Università degli studi di Modena e Reggio Emilia Università degli studi di Modena e Reggio Emilia
Facoltà di Scienze Matematiche, Fisiche e Naturali Corso di Laurea Magistrale in Informatica
Relatore:
Ing. Riccardo Martoglia Correlatori:
Dott. Federica Mandreoli
Ing. Luca Carafoli Candidato:
Federico Di Bernardo
Anno Accademico 2009-2010
INTRODUZIONE INTRODUZIONE
o Situazione Situazione critica critica del traffico nelle città del traffico nelle città
Aumento del Aumento del consumo consumo di carburante ed di carburante ed inquinamento
inquinamento
Incremento del numero di Incremento del numero di incidenti incidenti
Forte Forte congestionamento congestionamento della rete stradale della rete stradale
Necessità di una Necessità di una nuova concezione nuova concezione di mobilità e di mobilità e trasporto
trasporto
Sfida nell’ambito di ricerca dell’ Sfida nell’ambito di ricerca dell’ ICT ICT ( ( Information Information and Communication technology
and Communication technology ) )
INTRODUZIONE INTRODUZIONE
Mission del progetto:
Smart Navigation: Mobilità intelligente.
Urban Mobility: Incremento dell'efficienza nell'uso degli attuali mezzi di trasporto e delle infrastrutture.
Safety: Incremento della sicurezza e riduzione degli impatti ambientali.
PEGASUS
PEGASUS = = PProgErogEtto per la tto per la GGestione della mobilità estione della mobilità AAttraverso Sttraverso Sistemi istemi infotelematici per l’ambito
infotelematici per l’ambito UUrbano, per la rbano, per la SSicurezza di passeggeri, veicoli e merci.icurezza di passeggeri, veicoli e merci.
• Realizzato in collaborazione con Realizzato in collaborazione con l’università di Bologna.l’università di Bologna.
OBIETTIVO DELLA TESI:
OBIETTIVO DELLA TESI:
Studiare e sviluppare un sistema per la
Studiare e sviluppare un sistema per la gestione efficiente gestione efficiente dei dati dei dati provenienti dalle OBU (
provenienti dalle OBU ( On-Board Unit On-Board Unit ) installate sui veicoli urbani ) installate sui veicoli urbani
CONTENUTI:
CONTENUTI:
Panoramica sul Sistema PEGASUSPanoramica sul Sistema PEGASUS
Data Stream Management SystemData Stream Management System
Prototipo SoftwarePrototipo Software
Prove Sperimentali EffettuateProve Sperimentali Effettuate
Conclusioni e Sviluppi FuturiConclusioni e Sviluppi Futuri
Panoramica sul Sistema PEGASUS Panoramica sul Sistema PEGASUS
Data Stream Management System Data Stream Management System
Prototipo Software Prototipo Software
Prove Sperimentali Effettuate Prove Sperimentali Effettuate
Conclusioni e Sviluppi Futuri Conclusioni e Sviluppi Futuri
PANORAMICA SUL SISTEMA PEGASUS PANORAMICA SUL SISTEMA PEGASUS
OBU ( On-Board Unit )
=Dispositivo installato a bordo dei veicoli in grado di raccogliere varie
informazioni sul veicolo e comunicarle sottoforma di data stream
• VelocitàVelocità
• PosizionePosizione
• AccelerazioneAccelerazione
Real-time comms engine
Smart navigation engine
Maps &
real-time data User interface
GPS unit Accel unit
GPRS V2I unit
WiFi V2V unit
PANORAMICA SUL SISTEMA PEGASUS PANORAMICA SUL SISTEMA PEGASUS
ad-hoc, multi-hop, V2V communication ad-hoc, multi-hop, V2V communication
V2I communication V2I communication
BTSBTS BTSBTS
Control Centre Infrastructure d NetworkInfrastructure d Network OBUsOBUs
Comunicazioni Comunicazioni GPRS
GPRS costose costose ! !
Differenti Differenti tipologie di tipologie di
comunicazione:
comunicazione:
V2V V2V (WiFi)(WiFi) V2IV2I (GPRS) (GPRS)
Il Il Centro Di Centro Di Controllo
Controllo
colleziona ed colleziona ed
integra i dati e integra i dati e
gestisce i
gestisce i POI POI ed ed
EOI EOI
PANORAMICA SUL SISTEMA PEGASUS PANORAMICA SUL SISTEMA PEGASUS
Centro di Controllo Centro di Controllo
OBU OBU
OBU OBU
Communication Manager
EOI Ontolog
y
Recom- mender
System Recom- mender
System POI
Ontology
OBU OBU
V2I interaction
V2I interaction
V2Vinteracti on
V2Vinteracti on
Data acquisition Data acquisition Storage Manager
GIS tables
Query Processing Engine
DSM S
Communicati on-saving!
OBU
Panoramica sul Sistema PEGASUS Panoramica sul Sistema PEGASUS
Data Stream Management System Data Stream Management System
Prototipo Software Prototipo Software
Prove Sperimentali Effettuate Prove Sperimentali Effettuate
Conclusioni e Sviluppi Futuri Conclusioni e Sviluppi Futuri
DATA STREAM MANAGEMENT SYSTEM DATA STREAM MANAGEMENT SYSTEM
Applicazione di streaming data-intensive con Applicazione di streaming data-intensive con requisiti spaziali e temporali
requisiti spaziali e temporali
GIS DSMS TemporaleGIS DSMS Temporale
Linguaggio di interrogazione SQL-LikeLinguaggio di interrogazione SQL-Like
Acquisizione ed accesso a dati tempo e spazio Acquisizione ed accesso a dati tempo e spazio localizzati
localizzati
Streaming items utilizzati non solo per i servizi Streaming items utilizzati non solo per i servizi real-time
real-time
Query continueQuery continue
Ad-Hoc QueryAd-Hoc Query
Analisi OLAP su dati storiciAnalisi OLAP su dati storici
Tipiche soluzioni accoppiano il sistema di Storage Tipiche soluzioni accoppiano il sistema di Storage Management con quello di Query Processing
Management con quello di Query Processing
Scarsa flessibilitàScarsa flessibilità
Difficoltà di ottimizzazioneDifficoltà di ottimizzazione
DATA STREAM MANAGEMENT SYSTEM DATA STREAM MANAGEMENT SYSTEM
Storage Manager Storage Manager DSMSDSMS
Query Processing Engine Query Processing Engine
Query n Query 2
Query 1 …
Query Query Optimizer
Optimizer QueryQuery Executor
Executor QueryQuery Parser Parser
Interface
Read /
Setup ResultsSet
Storage Point 1
Storage Point 2
Storage Point n
…
LoadLoad Shedder Shedder
DataData Manager Manager OBUsOBUs
Input StreamInput Stream
GIS GIS
DBMS DBMS
DSMS profondamente diversi dai DSMS profondamente diversi dai DBMS DBMS
DATA STREAM MANAGEMENT SYSTEM DATA STREAM MANAGEMENT SYSTEM
DBMS:
Dati:
• Dati “statici” e persistenti
• Gestione del dato
“presente”
• Dati corretti
• Spazio “illimitato”
Query:
• Query one-shot complesse
• Risposte precise
• Update poco frequenti
• Query plan statico
• HADP (Human-Active, Database-Passive)
DSMS:
Dati:
• Stream transienti
• Nozione di “tempo”
• Memoria primaria limitata
• Dati danneggiati o mancanti
Query:
• Query continue
“semplici”
• Approximate answering
• Query plan dinamico
• Diverse query in esecuzione
• DAHP (Database-Active, Human-Passive)
DATA STREAM MANAGEMENT SYSTEM DATA STREAM MANAGEMENT SYSTEM
PROBLEMA : Dati potenzialmente infiniti e memoria primaria limitata !
Soluzioni Soluzioni
“ “ Lossless Lossless ”: ”:
Window Models Window Models
Presente vs Storico Presente vs Storico
Old tuples Newly arrival tuples
DBMS
Main Memory
WINDOW
DATA STREAM MANAGEMENT SYSTEM DATA STREAM MANAGEMENT SYSTEM
Ottimizzazioni Ottimizzazioni
“ “ Lossy Lossy ”: ”:
Load Shedding Load Shedding
Synopses Synopses
Batch Processing Batch Processing
Memory P = 0,33
DSMSDSMS
Incident detection
Near vehicle
Panoramica sul Sistema PEGASUS Panoramica sul Sistema PEGASUS
Data Stream Management System Data Stream Management System
Prototipo Software Prototipo Software
Prove Sperimentali Effettuate Prove Sperimentali Effettuate
Conclusioni e Sviluppi Futuri Conclusioni e Sviluppi Futuri
PROTOTIPO SOFTWARE PROTOTIPO SOFTWARE Sviluppo di un
Sviluppo di un Storage Management Storage Management System
System disaccoppiato dal modulo di disaccoppiato dal modulo di Query Query Processing Engine
Processing Engine
Storage Manager Storage Manager
Query produttore pull-basedQuery produttore pull-based
Registrazione queries consumatoreRegistrazione queries consumatore
Switch dinamicoSwitch dinamico delle strutture dati delle strutture dati
Gestione delle Gestione delle finestre temporalifinestre temporali
MigrazioneMigrazione dati storici dati storici
Storage Manager
Interface
Query Engine
PostGIS
OBUsOBUs
Input StreamInput Stream
read
setup results
Results Results
Query Processing Engine Query Processing Engine
Sottomissione query consumatoreSottomissione query consumatore
Esecuzione concorrenteEsecuzione concorrente di diverse queries di diverse queries
Invio comandi di lettura (con o senza filtri)Invio comandi di lettura (con o senza filtri)
Scrittura risultati su fileScrittura risultati su file
PROTOTIPO SOFTWARE PROTOTIPO SOFTWARE Strutture dati dinamiche
Strutture dati dinamiche
Never ConsumeOrdered ConsumeEager Consume Never Expire
Ordered Expire Unordered Expire
Replaced Expire
PERSISTENT
IN-PLACE IN-PLACE IN-PLACE
RANDOM RANDOM RANDOM
FIFO FIFO FIFO \ RANDOM
FIFO \ RANDOM FIFO
in scrittura
pieno pieno
consumati vuoti
FIFO –
FIFO –
Lista concatenata Lista concatenata circolarecircolareRANDOM – RANDOM –
Lista concatenataLista concatenataconsumato in scrittura
Produttore
Consumatore
PROTOTIPO SOFTWARE PROTOTIPO SOFTWARE
Esecuzione concorrente di diverse
Esecuzione concorrente di diverse query query continue
continue
Gestione overlapping Gestione overlapping finestre multiplefinestre multiple
Singola passata sui datiSingola passata sui dati
0 s 5 s 10 s 15 s 20 s 25 s 30 s
t1 t2 t3 t4 t5 t6 t7
C2
C3 C1
0 s 5 s 10 s 15 s 20 s 25 s 30 s
t1 t2 t3 t4 t5 t6 t7
C2
C3 C1
Newly arrival tuples
tt tt
Old Tuples Old Tuples Consumed Consumed
PostGIS
Polling 10 s Polling 10 s
PROTOTIPO SOFTWARE PROTOTIPO SOFTWARE
Dati storici gestiti tramite
Dati storici gestiti tramite DBMS DBMS PostgreSQL
PostgreSQL con estensione spaziale con estensione spaziale PostGIS PostGIS
Driver JDBC di tipo 4Driver JDBC di tipo 4
Estesione GIS molto utile per la gestione dei dati Estesione GIS molto utile per la gestione dei dati georeferenziati
georeferenziati
• obuid obuid
Identificativo vettura Identificativo vettura
• speed speed
Velocità al tempo t Velocità al tempo t
• time time
Tempo di ricezione della tupla Tempo di ricezione della tupla
• timestamp timestamp
Tempo logico di ricezione Tempo logico di ricezione
• position ( position ( lat, long lat, long ) )
Posizione spaziale modellato Posizione spaziale modellato
come punto bidimensionale come punto bidimensionale
PROTOTIPO SOFTWARE PROTOTIPO SOFTWARE
main()
startDSMS() stopDSMS() submitQuery() stopQuery()
DSMSCoordinator
submitConsumer() stop()
stopAll()
QueryEngine
start() stop() seqRead() randRead() setConsumer() removeConsumer()
StorageManager
ID
Latitude Longitude Speed Time ecc
Tuple
ConsumerType ProducerType Schema
ecc…
DataStructure
ConsumerID Window
SamplePeriod Filter
ecc…
Consumer
inizializeInterface() setTextOBU_Store() ecc…
DSMSInterface
inizializeInterface()
start()
submitConsumer()
GUI
StorageManagerInterface
seqRead() randRead() setConsumer() removeConsumer()
resultSet
<<use>>
<<use>>
<<use>>
Utente Utente
Grafo delle classi
Grafo delle classi
PROTOTIPO SOFTWARE PROTOTIPO SOFTWARE
Caratteristiche del produttore
produttore Caratteristiche del/dei Consumatore/i Consumatore/i
Produttore:
Produttore:
Dimensione Dimensione dei blocchi dei blocchi
FinestraFinestra
Tempo di Tempo di riesecuzione riesecuzione
Modalità di Modalità di inserimento inserimento
Consumatore Consumatore : :
Tipologia di Tipologia di consumo
consumo
FiltriFiltri
Polling timePolling time
ID queryID query
FinestraFinestra
Panoramica sul Sistema PEGASUS Panoramica sul Sistema PEGASUS
Data Stream Management System Data Stream Management System
Prototipo Software Prototipo Software
Prove Sperimentali Effettuate Prove Sperimentali Effettuate
Conclusioni e Sviluppi Futuri Conclusioni e Sviluppi Futuri
PROVE SPERIMENTALI PROVE SPERIMENTALI Misura dei
Misura dei tempi di risposta tempi di risposta al al variare di:
variare di:
N. Thread Consumer N. Thread Consumer
Frequenza di lettura Frequenza di lettura
delle tuple delle tuple
Quantità di tuple per Quantità di tuple per
file file
Algoritmo di lettura Algoritmo di lettura lineare
lineare O(K) O(K)
Singola passataSingola passata
Nessuna Nessuna
approssimazione approssimazione
Panoramica sul Sistema PEGASUS Panoramica sul Sistema PEGASUS
Data Stream Management System Data Stream Management System
Prototipo Software Prototipo Software
Prove Sperimentali Effettuate Prove Sperimentali Effettuate
Conclusioni e Sviluppi Futuri Conclusioni e Sviluppi Futuri
CONCLUSIONI CONCLUSIONI
E’ stato effettuato uno E’ stato effettuato uno studio approfondito delle studio approfondito delle
caratteristiche e delle problematiche relative ai sistemi per la caratteristiche e delle problematiche relative ai sistemi per la
gestione di stream di dati, ovvero dei
gestione di stream di dati, ovvero dei Data Stream Data Stream Management System
Management System
Sono stati Sono stati analizzanti i principali DSMSanalizzanti i principali DSMS in via sperimentale, in via sperimentale, come ad esempio: TelegrapCQ, STREAM, Cougar, Aurora e
come ad esempio: TelegrapCQ, STREAM, Cougar, Aurora e NiagaraCQ.
NiagaraCQ.
E’ stato progettato ed implementato un innovativo E’ stato progettato ed implementato un innovativo DSMSDSMS in in JavaJava, in cui la parte di gestione dei dati è ben , in cui la parte di gestione dei dati è ben
separata rispetto alla parte di query processing engine, in separata rispetto alla parte di query processing engine, in
modo da garantire la massima flessibilità ed ottime possibilita modo da garantire la massima flessibilità ed ottime possibilita
di ottimizzazione.
di ottimizzazione.
Per la gestione dei dati storici, ci si è appoggiati al Per la gestione dei dati storici, ci si è appoggiati al DBMS
DBMS PostgreSQLPostgreSQL, con l’estensione , con l’estensione PostGISPostGIS per poter per poter gestire i dati georeferenziati comunicati dalle OBU.
gestire i dati georeferenziati comunicati dalle OBU.
Sono state effettuate delle Sono state effettuate delle prove sperimentaliprove sperimentali in modo da in modo da misurare le prestazioni e la scalabilità del sistema.
misurare le prestazioni e la scalabilità del sistema.
Tutte le parti del lavoro di Tesi che mi è stato proposto sono Tutte le parti del lavoro di Tesi che mi è stato proposto sono state portate a termine in maniera
state portate a termine in maniera concretaconcreta e e completacompleta..
CONCLUSIONI CONCLUSIONI
… … studiati ed analizzati più di 20 studiati ed analizzati articoli scientifici articoli scientifici e documenti di ricerca nel campo dei DSMS:
e documenti di ricerca nel campo dei DSMS:
• I. Botan, G. Alonso, P. M. Fischer, D. Kossmann, and N. Tatbul.
Flexible and scalable storage management for data- Flexible and scalable storage management for data- intensive stream processing
intensive stream processing
• F. Mandreoli, R. Martoglia, W. Penzo, S. Sassatelli. Data Data
Management Issues for Intelligent Transportation Systems Management Issues for Intelligent Transportation Systems
• Lukasz Golab and M. Tamer Ozsu. Issues in Data Stream Issues in Data Stream Management
Management
• Brian Babcock Shivnath Babu Mayur Datar Rajeev Motwani
Jennifer-Widom. Models and Issues in Data Stream Systems.Models and Issues in Data Stream Systems.
• Arkady Zaslavsky Mohamed Medhat Gaber and Shonali Krishnaswamy. Mining Data Streams: A Review.Mining Data Streams: A Review.
• Ecc…
SVILUPPI FUTURI SVILUPPI FUTURI
Il progetto Il progetto
PEGASUSPEGASUS è un è un sistema molto complesso sistema molto complesso che richiederà all’università e ai collaboratori alcuni
che richiederà all’università e ai collaboratori alcuni anni di lavoro tra sviluppo e testing
anni di lavoro tra sviluppo e testing
Il lavoro prodotto si inserisce quindi nell’ambito di una Il lavoro prodotto si inserisce quindi nell’ambito di una problematica ben più vasta di quanto è possibile
problematica ben più vasta di quanto è possibile
trattare in una Tesi di Laurea e si presta di conseguenza trattare in una Tesi di Laurea e si presta di conseguenza
a molti ed interessanti sviluppi sotto diversi aspetti a molti ed interessanti sviluppi sotto diversi aspetti
Per quanto riguarda il DSMS, dovrà essere Per quanto riguarda il DSMS, dovrà essere implementata
implementata l’interfaccia di rete l’interfaccia di rete verso le OBU in verso le OBU in modo da gestire stream di dati reali e dovrà essere modo da gestire stream di dati reali e dovrà essere
sviluppato il motore di query processing engine sviluppato il motore di query processing engine
(query parsing, query optimization, etc.).
(query parsing, query optimization, etc.).
