FernUniversität in Hagen

Seminar 01912

im Sommersemester 2005

“Neue Techniken der Anfragebearbeitung: Datenströme, kontinuierliche Anfragen

und adaptive Auswertung”

Thema 8 Aurora

Referentin: Ute Quandt

Gliederung des Vortrags 1. Einführung

1.1 Charakteristik traditioneller DBMS 1.2 Probleme der Kontrollanwendungen in traditionellen DBMS und ihre

Anforderungen an DBMS 1.3 Aurora - Prototyp für eine bessere Unterstützung der

Kontrollanwendungen

2. Aurora-System-Modell

2.1 Grundlegende Funktionalität 2.2 Abfragemodell

2.3 SQuAl - Stream Query Algebra - Auroras Strom-Abfragealgebra

3. Aurora – Optimierung

3.1 Anforderungen an die Abfrageoptimierung

3.2 Dynamische kontinuierliche Abfrageoptimierung

Gliederung des Vortrags 4. Aurora - Laufzeitarchitektur

4.1 Allgemeines 4.2 QoS - Datenstrukturen

4.3 ASM - Aurora-Speicher-Manager

4.4 Echtzeit-Ablaufplanung 4.5 Selbstüberwachung

4.6 Lastabwurf (load shedding)

5. Stand der Arbeiten und Schlussfolgerungen 5.1 Aurora-graphische Benutzerschnittstelle

5.2 Zusammenfassung der Ergebnisse

5.3 Verwandte Arbeiten

1. Einführung 1.1 Charakteristik traditioneller DBMS

Traditionelle DBMS - Ausrichtung auf die geschäftliche Datenverarbeitung

Anforderungen: 1. HADP Human-Active, DBMS-Passive

2. Einzig wichtig ist der aktuelle Zustand der Daten

3. Alarmzustände und –auslöser sind zweitrangig

4. Synchronisierung der Daten 5. Anwendungen erfordern keinen Echtzeit-Service

1. Einführung 1.2 Probleme der Kontrollanwendungen in traditionellen DBMS und ihre Anforderungen an DBMS

Anforderungen: 1. DAHP DBMS-Active, Human-Passive

2. Berücksichtigung der Historie der Werte im Datenstrom durch das

Datenmanagement 3. Unterstützung der Orientierung der Kontrollanwendungen auf

Alarmauslöser durch das DBMS

4. Kompensierung von Datenverlusten

Bei Notwendigkeit ungefähre Antworten 5. Echtzeitanforderungen der Kontrollanwendungen

1. Einführung 1.3 Aurora-Prototyp für eine bessere Unterstützung der Kontrollanwendungen

Entwicklung an: • Brandeis University in Waltham – USA • Brown University in Providence – USA • M.I.T. in Cambridge – USA Lösungsmöglichkeiten für Anforderungen von Kontrollanwendungen bei traditionellen DBMS: • sehr teuer • sehr schwierig zu installieren • beeinträchtigen die Performance negativ • Schätzungsfragen wurde noch in keinem DBMS realisiert

alle Basis-Mechanismen in den gegenwärtigen DBMS überdacht

2. Aurora-System-Modell 2.1 Grundlegende Funktionalität

Basisaufgabe: Verarbeitung der eingehenden Ströme auf einem vom

Anwendungsadministrator definierten Weg

Funktionalitäten: • Datenfluss-System

• Behälter-und-Pfeile-Modell (boxes and arrows model)

• Kontrolle der Servicequalität (QoS)

• Aurora-Zeitstempel für jedes eingehende Tupel • einheitlicher Quell-Identifizierer pro Datenquelle

2. Aurora-System-Modell 2.1 Grundlegende Funktionalität

2. Aurora-System-Modell 2.2 Abfragemodell

2. Aurora-System-Modell 2.3 SQuAl – Stream Query Algebra – Auroras Strom-Abfragealgebra

Strom - zusammengefügte Serie von Tupeln mit einheitlichem Typ

Unterstützung von 7 stromorientierten Operatoren in Aurora

Zwei Arten der Operatoren:

Ordnungs-agnostische: Filter, Map, Union

Ordnungs-sensible: BSort, Aggregate, Join, Resample

2. Aurora-System-Modell 2.3 SQuAl – Stream Query Algebra – Auroras Strom-Abfragealgebra

Ordnungsagnostische Operatoren: Verarbeitung der Tupel in der Ordnung, in der sie ankommen

Filter Ähnlich dem relationalen select, filtert verschiedene Aussagen, kann die Tupel entsprechend führen

Filter (P1, ...Pm) (S)

2. Aurora-System-Modell 2.3 SQuAl – Stream Query Algebra – Auroras Strom-Abfragealgebra

Ordnungsagnostische Operatoren: Map Ähnlich dem relationalen projection,

wendet Funktionen auf die zu verarbeitenden Tupel an

Map (B1=F1, ... , Bm=Fm) (S)

Union Analog dem relationalen union, Mischung von 2 oder mehr Eingabeströmen zu einem Ausgabestrom

Union (S1, ... , Sn)

2. Aurora-System-Modell 2.3 SQuAl – Stream Query Algebra – Auroras Strom-Abfragealgebra

Ordnungssensible Operatoren:

Garantie der Ausführung bei:

• endlichem Pufferplatz

• endlicher Zeit • Gewährleistung einer Ordnung über die Eingabetupel

(mit begrenzter Unordnung)

Beschreibung der Ordnung ankommender Tupel Order (On A, Slack n, GroupBy B1, ..., Bm)

alle Tupel, die nicht mit der Ordnungsspezifikation übereinstimmen,

fallen weg

2. Aurora-System-Modell 2.3 SQuAl – Stream Query Algebra – Auroras Strom-Abfragealgebra

Ordnungssensible Operatoren:

BSort angenähert dem Sort-Operator

BSort (Assuming O) (S)

2. Aurora-System-Modell 2.3 SQuAl – Stream Query Algebra – Auroras Strom-Abfragealgebra

Ordnungssensible Operatoren: BSort Slack=2

Zeit

1

2

3

4

5

6

7

8

9

10

Eingabestrom

1

3

5

1

2

3

5

5

8

5

Puffer

1

1

1

3

3

3

5

5

5

5

3

3

5

5

5

3

5

5

8

5

1

2

3

5

5

8

5

Ausgabestrom

1

1

2

3

3

5

5

5

2. Aurora-System-Modell 2.3 SQuAl – Stream Query Algebra – Auroras Strom-Abfragealgebra

Ordnungssensible Operatoren:

Aggregate wendet „Fenster-Funktionen“ an, um das Fenster über dem Eingabestrom zu verschieben

Aggregate (F,Assuming O, Size s, Advance i) (S)

2. Aurora-System-Modell 2.3 SQuAl – Stream Query Algebra – Auroras Strom-Abfragealgebra

Beispiel: Erzeuge eine Ausgabe , wenn m Soldaten eine

Grenze k zur gleichen Zeit

überschritten haben! k>20, m=2, n(Slack)=1

(Sid,Time,Posn) (Sid,Time,Pos) (Time,Cnt) (Time,Cnt) (1,1,30) (1,1,30) (1,2) (1,2) (1,2,19) (2,2,23) (2,2) (2,2) (2,1,12) Filter (3,1,33) Aggregate (3,1) Filter (2,2,23) (3,2,23) (3,1,33) (3,3,39) (3,2,23) (3,3,39)

2. Aurora-System-Modell 2.3 SQuAl – Stream Query Algebra – Auroras Strom-Abfragealgebra

Ordnungssensible Operatoren:

Join Ähnlich dem relationalen join,

Binärer join-Operator

Join (P, Sizes s, Left Assuming O1, Right Assuming O2) (S1, S2)

Verkettung der Tupel der beiden Eingabeströme

2. Aurora-System-Modell 2.3 SQuAl – Stream Query Algebra – Auroras Strom-Abfragealgebra

Ordnungssensible Operatoren:

Resample Asymmetrischer semijoinartiger Synchronisationsoperator, Ausrichtung von Paaren von Strömen

Resample (F, Size s, Left Assuming O1, Right Assuming O2) (S1, S2)

Bildung interpolierter Werte aus S1 unter Verwendung von S2

3. Aurora-Optimierung 3.1 Anforderungen an die Abfrage-Optimierung

Eines der wichtigsten Ziele:

Minimierung der Anzahl der Iterationen

Es wird erwartet: · eine große Menge von Boxen

· hohe Datenraten

· häufige Wechsel

· eine Offline-Nutzung des Netzwerks für eine Optimierung scheint unvernünftig

3. Aurora-Optimierung 3.2 Dynamische kontinuierliche Abfrageoptimierung

Ausgangspunkt: nicht optimiertes Aurora-Netzwerk

Während der Ausführung: • Erstellung der Laufzeit-Statistiken

• Laufzeit-Optimierung

Methode: Selektieren eines Teils des Netzwerkes

Auf das Subnetzwerk angewandte Taktiken: • eingefügte Projektionen (Inserting projections)

• kombinierte Boxen (Combining boxes)

• umorganisierte Boxen (Reordering boxes)

4. Aurora-Laufzeitarchitektur 4.1 Allgemeines

4. Aurora-Laufzeitarchitektur 4.2 QoS-Datenstrukturen

QoS (Quality of Service) - Servicequalität Maximierung des QoS für die produzierten Ausgaben Attribute der multidimensionalen QoS-Funktion : • Reaktionszeiten (response times) (a) • Tupel-Abwurf (Tupel drops) (b) • Produzierte Werte (values produced) (c)

(a) Delay-based

(b) Drop-based

(c) Value-based

4. Aurora-Laufzeitarchitektur 4.3 ASM Aurora-Storage-Manager (Aurora-Speicherverwaltung)

Zwei Anforderungen: 1. Organisierung der Speicherung der Tupel, die das Aurora-Netzwerk

durchlaufen 2. Gesonderte Tupel-Speicherung an den Verbindungspunkten Verwaltung der Warteschlange – Queue Management • Verwaltung einer Sammlung von Warteschlangen von Tupeln • Änderung der Priorität der Boxen durch Zeitablaufplaner • Periodisch Prüfung der Priorität für den Hauptspeicheraufenthalt der

Warteschlangen Verwaltung der Verbindungspunkte – Connection point management • Unterstützung von ad-hoc-Abfragen • Anforderung der Historie • Optionaler Speicherschlüssel

4. Aurora-Laufzeitarchitektur 4.4 Echtzeit-Ablaufplanung

Ziele von Aurora im gesamten System: 1. Maximierung der QoS 2. Reduktion der Verarbeitungskosten der Tupel Zeitablaufplanung für Züge (Train scheduling) Züge: Stapeln mehrerer Tupel als Eingabe für eine Einzelbox Superboxen: Tupelzug durch mehrere Boxen Ziele: 1. Reduzierung der pro Tupel durchgeführten E/A-Operationen 2. Minimierung der Anzahl von Boxenaufrufen pro Tupel Auswertung von Nichtlinearitäten zur Kostenreduktion: • Nichtlinearität zwischen den Boxen (Interbox non-linearity) • Nichtlinearität innerhalb der Box (Intrabox non-linearity)

4. Aurora-Laufzeitarchitektur 4.4 Echtzeit-Ablaufplanung

Hauptaufgabe der Echtzeit-Ablaufplanung: Prioritätenbestimmung für die Ausgaben Wartezeiten pro Ausgabe zur Maximierung der QoS

zwei Verfahren der Prioritätenbestimmung : 1. Statusbasiertes Verfahren

2. Rückkopplungsbasiertes Verfahren

Lösung des Problems: Nutzung von Erfahrungswerten für

Erfüllung der Echtzeit-Anforderungen und die Kostenreduktion durch Prioritätenbestimmung

4. Aurora-Laufzeitarchitektur 4.4 Echtzeit-Ablaufplanung

Leistung der Zeitablaufplanung: Aurora-Prototyp: Netzwerk mit 40 Boxen

Eingabe 50.000 Tupel 3200 Boxen pro Sekunde 830 Ausgabetupel pro Sekunde

Einzelboxverarbeitung

Tupelzugverarbeitung Verarbeitungszeit Reduktion um 0,48

Superbox-Zeitablaufplanung

zusätzliche

Verarbeitungszeit Reduktion um 0.43

4. Aurora-Laufzeitarchitektur 4.5 Selbstüberwachung

Ziel: Überlastungssituationen vorhersagen und entdecken Statische Analyse Stabiler Status abhängig von Tupelverarbeitungskosten und Rate der Tupelproduktion Kein stabiler Status erreichbar Lösung: Neuentwurf der Anwendung unter Änderung der

Ressourcenanforderung, Verfügbarkeit neuer Ressourcen zur Erhöhung der Systemkapazität,

Lastabwurf (load shedding) Dynamische Analyse Übergabe der Ausgabetupel (mit Zeitstempel) Prüfung des korrespondierenden verzögerungsbasierten QoS-Graphen auf „gute Zone“ des QoS-Graphen (good zone)

4. Aurora-Laufzeitarchitektur 4.6 Lastabwurf (load shedding)

statischen oder dynamischen Analyse Überlast Lastabwurf Lastabwurf durch wegfallende Tupel Realisierung in Netzwerkbereichen, in denen größere Abweichungen akzeptiert werden Als Resultat der statischen Analyse – Nutzung Abwurf-basierter QoS-Graphen Als Resultat der dynamischen Analyse – Nutzung verzögerungs-

basierter QoS-Graphen Semantischer Lastabwurf durch gefilterte Tupel Kontrolle der Wirkung der wegfallenden Tupel auf die Anwendungssemantik - Nutzung wertebasierter QoS-Graphen Filterboxen mit den am geringsten frequentierten Aussagen

5. Stand der Arbeiten und Schlussfolgerungen 5.1 Aurora - Grafische Benutzerschnittstelle

Implementierung

Prototyp Aurora

März 2003

Laufzeit-System:

Zeitablaufplaner

Rudimentärer Speichermanager

Code zur Boxenausführung

5. Stand der Arbeiten und Schlussfolgerungen 5.1 Aurora - Grafische Benutzerschnittstelle

Werkzeug zur

Überwachung der Warteschlangen

5. Stand der Arbeiten und Schlussfolgerungen 5.2 Zusammenfassung der Ergebnisse

Aurora

DAHP-System

Verarbeitung von Datenströmen für Kontrollanwendungen

SQuAl – 7 stromorientierte Operatoren

Speicherorganisation

Optimierung des Aurora-Netzwerkes

Echtzeit-Ablaufplanung

Selbstüberwachung

QoS-Graphen

Lastabwurf

5. Stand der Arbeiten und Schlussfolgerungen 5.2 Zusammenfassung der Ergebnisse

Aurora

Verarbeitung von Massendaten

Datenquelle – Hardwaresensoren

Banken / Steuerveraltung

Verarbeitung von Massendaten

Datenquelle – Datenfernübertragung

Hohe Sicherheit – kein Lastabwurf

Selbstüberwachungssysteme interessant

Lösungen für verteilte Systeme – u.a. wegen Lastspitzen

Weiterentwicklung Aurora Verarbeitung auf Einzelcomputer Verteilte Architektur Arbeit mit replizierten Boxen

5. Stand der Arbeiten und Schlussfolgerungen 5.3 Verwandte Arbeiten

STREAM

Realisierung eines umfassenden Datenmanagements

Erzielung von Verarbeitungsfunktionalitäten

Gemeinsamkeit zu Aurora:

Daten- und Ressourcen-Management, aber unterschiedliche Lösungen

STREAM Aurora

QoS unbekannt QoS-Spezifikationen

SQL spezielle Operatoren

5. Stand der Arbeiten und Schlussfolgerungen 5.3 Verwandte Arbeiten

Aurora Medusa

Borealis

Verteilte Stromverarbeitungsmaschine der zweiten Generation

Stromverarbeitungsfunktionalität Teilungsfunktionalität

Modifikation und Erweiterung

Unterstützung der Überarbeitung von Informationen in einem Strom mit drei Arten von Stromnachrichten

Wechsel der Boxensemantik während der Abarbeitung

QoS-basiertes Optimierungsmodell – operiert zwischen Server- und Sensornetzwerken

Fehler-Toleranz der Stromverarbeitung

Vielen Dank für die Aufmerksamkeit !