Upload
baylee
View
40
Download
0
Embed Size (px)
DESCRIPTION
TelegraphCQ. Manuel Hertlein. Inhalt. Einleitung Konzepte und Module Architektur Ausblick. Vergleich DBMS DSMS. Database Management System (DBMS). Data Stream Management System (DSMS). Persistente Daten Einmalige Anfragen Verarbeitung anfragegetrieben - PowerPoint PPT Presentation
Citation preview
TelegraphCQManuel Hertlein
2Manuel Hertlein - TelegraphCQ
• Einleitung
• Konzepte und Module
• Architektur
• Ausblick
Inhalt
3Manuel Hertlein - TelegraphCQ
Vergleich DBMS DSMS
Database Management System (DBMS)
Data Stream ManagementSystem (DSMS)
• Persistente Daten
• Einmalige Anfragen
• Verarbeitung anfragegetrieben
• Menge der Daten ist potenziell begrenzt
• Flüchtige Datenströme
• Kontinuierliche Anfragen
• Verarbeitung datengetrieben
• Menge der Daten ist potenziell unbeschränkt
4Manuel Hertlein - TelegraphCQ
• Aktuelle Anfragen in geeigneter Form festhalten und über bestimmten Zeitraum ausführen
• Eingehende Datenpakte an alle Anfragen leiten, die Daten des entsprechenden Typs beobachten
• Durch Anfrage dürfen Pakete nicht für andere Anfragen blockiert werden
• Auf Änderungen des Datenstroms bei laufender Abfrage durch Umstellen des Routing reagieren
Allgemeine Anforderungen an einDSMS-System
5Manuel Hertlein - TelegraphCQ
• Einleitung
• Konzepte und Module
• Architektur
• Ausblick
Inhalt
6Manuel Hertlein - TelegraphCQ
Kontinuierliche Abfragen mit TelegraphCQ
• TelegraphCQ Projekt der Datenbankforschungsgruppe der UC Berkely
• Framework mit Query-Engine für kontinuierliche, adaptive Abfragen auf Datenströme
• Vereint die Arbeiten und Erkenntnisse aus
• CACQ (Continously Adap-tive Continous Queries over Streams)
• PSoup
7Manuel Hertlein - TelegraphCQ
Eddies (1/4)
• Operator leitet Tupel aus ver-schiedenen Datenquellen zu Query-Operatoren
• Operatoren besitzen Eingangs-queue, in die zu bearbeitende Tupel abgelegt werden
• Anschließend an Eddy zurück-geschickt und von diesem wie-tergeleitet
• Für jedes Tupel kann indivi-duelle Reihenfolge zum Durch-laufen der Operatoren erstellt werden
8Manuel Hertlein - TelegraphCQ
Eddies (2/4) Einzelne Abfrage
Eddy
σa
S
σb
a
b
15
0
S1
S.b < 15 S.a > 10
Ready Done
σaσb
1 1
σaσb
0 0
SELECT *FROM SWHERE S.a > 10AND S.b < 15
9Manuel Hertlein - TelegraphCQ
Eddies (2/4) Einzelne Abfrage
Eddy
σa
S
σb
a
b
15
0
S1
S.b < 15 S.a > 10
Ready Done
σaσb
0 1
σaσb
1 0
SELECT *FROM SWHERE S.a > 10AND S.b < 15
10
Manuel Hertlein - TelegraphCQ
Eddies (3/4)
Aufbau Continuous Query Tupel Format
Data Fields
ready1 bit x O
done1 bit x O
sourceIdinteger
completedQueries1 bit x Q
O = #Operatoren in Eddy Q = #Queries in Eddy
Done Queriescompleted
σa σb σc
1 1 0
Q1 Q2
1 0
Completition Mask Q1
a b c
1 1 0
Completition Mask Q2
a b c
0 1 1
1 1 0 0 1 0
& &
Completition Mask
11
Manuel Hertlein - TelegraphCQ
Eddies (4/4) Mehrere Abfragen
Eddy
σa
S
σb
a
b
15
0
S2
S.b < 15 S.b < 10
S.a > 10
c 24
σc S.c = 15
Ready Done
σaσbσc
1 1 1
σaσbσc
0 0 0
Queriescompleted
Q1 Q2
0 0
SELECT *FROM SWHERE S.a > 10AND S.b < 15
Q1
SELECT *FROM SWHERE S.b < 10AND S.c = 15
Q2
12
Manuel Hertlein - TelegraphCQ
Eddies (4/4) Mehrere Abfragen
Eddy
σa
S
σb
a
b
15
0
S2
S.b < 15 S.b < 10
S.a > 10
c 24
σc S.c = 15
Ready Done
σaσbσc
0 1 1
σaσbσc
1 0 0
Queriescompleted
Q1 Q2
0 0
SELECT *FROM SWHERE S.a > 10AND S.b < 15
Q1
SELECT *FROM SWHERE S.b < 10AND S.c = 15
Q2
13
Manuel Hertlein - TelegraphCQ
Eddies (4/4) Mehrere Abfragen
Eddy
σa
S
σb
a
b
15
0
S2
S.b < 15 S.b < 10
S.a > 10
c 24
σc S.c = 15
Ready Done
σaσbσc
0 0 1
σaσbσc
1 1 0
Queriescompleted
Q1 Q2
1 0
SELECT *FROM SWHERE S.a > 10AND S.b < 15
Q1
SELECT *FROM SWHERE S.b < 10AND S.c = 15
Q2
14
Manuel Hertlein - TelegraphCQ
Gruppenfilter
S.a 8
P8: S.a ≠ 4 4 P8≠
P6: S.a = 6
P7: S.a = 8
P66
8 P7=
P4: S.a < 3
P5: S.a < 5
3
<5<3
P5P4
<
P1: S.a > 1
P2: S.a > 6
P3: S.a > 11
6
111
>6 >11>1
P2 P3P1
>
GruppenfilterPrädikateTupel
15
Manuel Hertlein - TelegraphCQ
State Modules (SteMs) (1/3)
Baum aus Hash Joins
SR
RxS T
R ST
16
Manuel Hertlein - TelegraphCQ
State Modules (SteMs) (2/3)
SteM
R
SteMR
T
SteMT
Eddy
S
SteMS
TR
probe PR PRS
PRSTbuild TR PR probe PRS
17
Manuel Hertlein - TelegraphCQ
State Modules (SteMs) (3/3) PSoup-Erweiterung
Date STeM
StreamingData
Sources
Query STeM
ClientsQueries
Build
Data
Build
PSoup-Eddy
Probe
Probe
Symmetric Join
18
Manuel Hertlein - TelegraphCQ
Routing
• Ziel: Anzahl der Operatoren, die durch-schnittlich durchlaufen werden, soll minimiert werden
• Operatoren werden je nach Selektivität mit Tickets versehen
• Jeder Operator bekommt ein Ticket wenn ein Tupel ihn betritt und eines abgezogen, wenn ein Tupel ihn verlässt
• Operatoren mit mehr Tickets (hoher Selektivität) werden bevorzugt ausgewählt
19
Manuel Hertlein - TelegraphCQ
Abfragefenster (1/2)
Datenquelle vibration_stream
Tupel location, value, timestamp
SELECT value, timestampFROM vibration_streamWHERE location = `Golden Gate Bridge´WINDOW vibration_stream, ST-7, ST)
Snapshot Query
SELECT value, timestampFROM vibration_streamWHERE location = `Golden Gate Bridge´ AND value > 50for (t = ST; t <= ST+100; t++) { WINDOW(vibration_stream, ST, t);}
Landmark Query
20
Manuel Hertlein - TelegraphCQ
Abfragefenster (2/2)
Sliding Query
SELECT AVG(value) FROM vibration_streamWHERE location = `Golden Gate Bridge´for (t = ST; t < ST + 70; t+=7) { WINDOW(vibration_stream, t-6, t);}
SELECT s2.*FROM vibration_stream1 AS s1, vibration_stream2 AS s2WHERE s1.location = `Golden Gate Bridge´AND s1.value < s2.valueAND s1.timestamp = s2.timestampfor (t = ST; t < ST + 70; t++) { WINDOW(vibration_stream1, t-6, t); WINDOW(vibration_stream2, t-6, t);}
Temporal Band-Join
21
Manuel Hertlein - TelegraphCQ
Fjords
• Schnittstelle für Kom-munikation und Daten-austausch zwischen Eddies, Operatoren, SteMs und Datenquellen
• Queues die sowohl Pull- (statische Daten) als auch Push-Techni-ken (Datenströme) implementieren
S
T
σPush
Pull
Push
get
22
Manuel Hertlein - TelegraphCQ
Flux
Flux = Fault-tolerant, Load-balancing eXchange
Ziele Umsetzung
Gleichmäßige Auslastung des parallelen Systems
Neuaufteilung des Input-Streams auf verschiedene Knoten
Höhere Ausfallsicherheit Wenn Knoten ausfällt, wird aktueller Input für diesen Knoten automatischauf andere Knoten umgelenkt
23
Manuel Hertlein - TelegraphCQ
• Einleitung
• Konzepte und Module
• Architektur
• Ausblick
Inhalt
24
Manuel Hertlein - TelegraphCQ
Design
25
Manuel Hertlein - TelegraphCQ
Arbeitsweise
TelegraphCQExecutor
Eddy
Query & Control
Data Tuples
TelegraphCQFront End
Listener
Parser
Optimizer
Catalog
SteMs
Shared Memory
Shared MemoryBuffer Pool
Query Plan Queue
Query Result Queue
Disk
TelegraphCQ Wrapper
26
Manuel Hertlein - TelegraphCQ
• Einleitung
• Konzepte und Module
• Architektur
• Ausblick
Inhalt
27
Manuel Hertlein - TelegraphCQ
Offene Themen
• Steuerung der Adaptivität
• Evaluierung und Weiterentwicklung von Routing-Schemata
• Gruppierung und Aufteilung von Anfragen auf einzelne Threads
• Effiziente Verwendung von Festplattenspeicher bei Auswertung von Streams
• Anpassung der Flux-Module für Cluster-Version
• Entwicklung einer verteilten Version von TelegraphCQ
28
Manuel Hertlein - TelegraphCQ
Zusammenfassung
• Entwicklung von Pervasive Computing entstehen Unmengen an Daten und Datenströmen
• Konventionelle Techniken stoßen an ihre Grenzen• TelegraphCQ vereint nützliche Techniken für
kontinuierliche, adaptive Datenabfragen• Baut auf Open-Source-Projekt PostgreSQL auf
(traditionelle Datenbanktechnik)• Kann von Erfahrungen und Entwicklung profitie-
ren, muss aber auch Kompromisse bei Design eingehen
• Unterscheidet sich von anderen Projekten durch großen Fokus auf Adaptivität
• TelegraphCQ Version 2.1 auf Projektseite verfügbar: http://telegraph.cs.berkeley.edu
29
Manuel Hertlein - TelegraphCQ
Fragen
30
Manuel Hertlein - TelegraphCQ
Quellen
S. Chandrasekaran, et al.: TelegraphCQ: Continuous Dataflow Processing for an Uncertain World. in CIDR (2003).
S. Madden, et al.: Continouosly Adaptive Continouos Queries over Streams. in SIGMOD (2002).
S. Manten: TelegraphCQ. in Neue Techniken der Anfragebearbeitung: Datenströme, kontinuierliche Anfragen und adaptive Auswertung (2005).