Vortrag zur Diplomarbeit in der Arbeitsgruppe Datenbanken und Informationssysteme Entwurf und...

Vortrag zur Diplomarbeit in der Vortrag zur Diplomarbeit in der Arbeitsgruppe Datenbanken und InformationssystemeArbeitsgruppe Datenbanken und Informationssysteme

Entwurf und Analyse einesEntwurf und Analyse eineseffizienten verteilten effizienten verteilten

BenachrichtigungssystemsBenachrichtigungssystems

Sven Bittner, 9Sven Bittner, 9. Januar 2004. Januar 2004

Betreuung durchBetreuung durch

Dr. Annika Hinze und Prof. Dr.-Ing. Heinz F. SchweppeDr. Annika Hinze und Prof. Dr.-Ing. Heinz F. Schweppe

2/20

MotivationMotivation

Benach-Benach-richtigungs-richtigungs-

system system (BS)(BS)

e2: t=30°C

e3: r=0,2 liter

ee44:: r=2 r=2

literliter

ee11 :: t=15°C

t=15°C

EreignisseEreignisse

FilterungFilterung

Effiziente, skalier-Effiziente, skalier-bare Filterungbare Filterung

BenachricBenachrich-h-tigungentigungen

((ee 22))

(e1)

((ee33 ), ), ((ee

44 ))

Profile Profile AbonnentenAbonnenten

p1=(t>22°C)

p2=(t<18°C)

p3=(r>0,1 lit.)

AnbieterAnbieter(Sensoren)(Sensoren)

Gebäudesteuerung (mittleres Gebäude)Gebäudesteuerung (mittleres Gebäude)• >10>1044 ProfileProfile• >10>1033 EreignisseEreignisse//SekundeSekunde

3/20

GliederungGliederung

• Zentralisierte FilterungZentralisierte Filterung

• Verteilte FilterungVerteilte Filterung

• ExperimenteExperimente

• ZusammenfassungZusammenfassung

4/20

GliederungGliederung

• Zentralisierte FilterungZentralisierte Filterung

• Verteilte FilterungVerteilte Filterung

• ExperimenteExperimente

• ZusammenfassungZusammenfassung

5/20

Zentralisierte FilterungZentralisierte Filterung

• Schnellste Struktur [GS95]Schnellste Struktur [GS95]– Filterbaum über alle Attribute eines TypsFilterbaum über alle Attribute eines Typs– ProblemeProbleme

–– Hauptspeicherbedarf sehr groß (breiter Baum)Hauptspeicherbedarf sehr groß (breiter Baum)

–– Nur GleichheitsoperatorenNur Gleichheitsoperatoren

–– Statische FilterstrukturStatische Filterstruktur

p4=(s=1,t=20,r=2)p5=(s=2,t=10,r=4)p6=(s=2,t=20,r=8)p7=(s=2,r=8)p8=(s=2,t=20,r=8)

t

s

t

r

r

r

r

p4

p7

p6,7,8

p5

p7

1

2

20

1020

*

2

48

8

8

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

6/20

Zentralisierte Filterung: Zentralisierte Filterung: ErweiterungErweiterung

{p{p55, p, p66, p, p77, p, p88}} {p{p77}} {p{p66, p, p77, p, p88}}

ee55: (s=2,t=6,r=8): (s=2,t=6,r=8)

Passende Profile:Passende Profile:== {p{p77}}

1020*t

p5,7

p4,6,7,8

p7

248r

p4

p5

p6,7,8

sp4

p5,6,7,8

12

• Erweiterte Struktur – System PrimAS [Bit02, Erweiterte Struktur – System PrimAS [Bit02, Bit03]Bit03]– Einzelner Knoten je Attribut (Minibaum)Einzelner Knoten je Attribut (Minibaum)– EigenschaftenEigenschaften

++ Weniger Speicherbedarf (keine breiten Bäume) Weniger Speicherbedarf (keine breiten Bäume)

++ Kantenbeschreibung mit Intervallen Kantenbeschreibung mit Intervallen

++ Operatoren: <, >, =, Mengentest, Bereichstest Operatoren: <, >, =, Mengentest, Bereichstest

++ Dynamischer Umbau möglich Dynamischer Umbau möglich

Zusätzlich:Zusätzlich: - Optimierung der Auswertungsreihenfolge [HB02]- Optimierung der Auswertungsreihenfolge [HB02]

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

7/20

GliederungGliederung

• Zentralisierte FilterungZentralisierte Filterung

• Verteilte FilterungVerteilte Filterung

• ExperimenteExperimente

• ZusammenfassungZusammenfassung

8/20

Verteilte FilterungVerteilte Filterung

1

3 4

5

BSBS

VerteiltesVerteiltes

62 Zentrale Filter-

komponenten

62

Azyklisches Overlaynetz

zur Verteilung

von Profilen und

Ereignissen

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

S

A

Kommunikation mit

beliebigen Vermittler

9/20

• VerteilungsstrategienVerteilungsstrategien– Ereignisweiterleitung (EW) [CRW99]Ereignisweiterleitung (EW) [CRW99]

• Filterung nah bei den AbonnentenFilterung nah bei den Abonnenten• Keine Weiterleitung von ProfilenKeine Weiterleitung von Profilen• Fluten von EreignissenFluten von Ereignissen

Verteilte Filterung: Verteilte Filterung: EreignisweiterleitungEreignisweiterleitung

1

3 4

5

62 BSBS

VerteiltesVerteiltesS1

e3: r=0,2lit.

A1

p3=(r>0,1lit

.)

p3 (e3)

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

10/20

Verteilte Filterung: Verteilte Filterung: ProfilweiterleitungProfilweiterleitung

– Profilweiterleitung (PW) [CRW99]Profilweiterleitung (PW) [CRW99]• Filterung nah bei den AnbieternFilterung nah bei den Anbietern• Fluten von ProfilenFluten von Profilen• Keine Weiterleitung von EreignissenKeine Weiterleitung von Ereignissen

1

3 4

5

62 BSBS

VerteiltesVerteiltesS1

e3: r=0,2lit.

A1

p3=(r>0,1lit.

)

p3

p3

p3

p3

p3

p3

(e3)

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

11/20

– Rendezvousknoten (RK) [PB02]Rendezvousknoten (RK) [PB02]• Filterung in spezialisierten ereignistypabhängigen Filterung in spezialisierten ereignistypabhängigen

RKRK• Gerichtete Weiterleitung der Profile und Ereignisse Gerichtete Weiterleitung der Profile und Ereignisse

an RKan RK• Praxis: Filterung auch in UnterwegsknotenPraxis: Filterung auch in Unterwegsknoten

Verteilte Filterung: Verteilte Filterung: RendezvousknotenRendezvousknoten

Filterung von Niederschlags-ereignissen

1

3 4

5

62 BSBS

VerteiltesVerteiltesS1

e3: r=0,2lit.

A1

p3=(r>0,1lit

.)p3

(e3)

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

12/20

– Ausnutzen von Bedeckungen zwischen ProfilenAusnutzen von Bedeckungen zwischen Profilen• Intuitiv: pIntuitiv: pxx > p > pyy (überdeckt) gdw. zu p (überdeckt) gdw. zu pxx genau die oder genau die oder

mehr Ereignisse als zu pmehr Ereignisse als zu pyy passen passen

– AnwendungAnwendung• Weiterleiten von Profil pWeiterleiten von Profil pxx an Nachbarn nur dann, wenn an Nachbarn nur dann, wenn

noch kein pnoch kein pyy mit p mit pyy > p > px x weitergeleitet wurdeweitergeleitet wurde

• Wenn Profil pWenn Profil pxx von Nachbarn eintrifft, können alle p von Nachbarn eintrifft, können alle pyy dieses Nachbarn mit pdieses Nachbarn mit pxx > p > pyy entfernt werden entfernt werden

– BerechnungBerechnung• Bereichsbasierte Berechnung (aufbauend auf Bereichsbasierte Berechnung (aufbauend auf

Filterstruktur)Filterstruktur)– Analyse der Kanten der Minibäume abhängig vom OperatorAnalyse der Kanten der Minibäume abhängig vom Operator– Bildung der Schnittmenge der Überdeckungen der Bildung der Schnittmenge der Überdeckungen der

AttributeAttribute

Verteilte Filterung: OptimierungVerteilte Filterung: Optimierung

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

13/20

GliederungGliederung

• Zentralisierte FilterungZentralisierte Filterung

• Verteilte FilterungVerteilte Filterung

• ExperimenteExperimente

• ZusammenfassungZusammenfassung

14/20

ExperimenteExperimente

• Realisierung der verteilten Filtervarianten und der Realisierung der verteilten Filtervarianten und der zentralisierten Filterkomponente in Prototyp DASzentralisierten Filterkomponente in Prototyp DAS

• Messungen unter Variation zahlreicher ParameterMessungen unter Variation zahlreicher Parameter

– Anteil passender ProfileAnteil passender Profile– Anteil erfüllender EreignisseAnteil erfüllender Ereignisse– VermittlerzahlVermittlerzahl– Überdeckungen zwischen ProfilenÜberdeckungen zwischen Profilen– Anzahl EreignistypenAnzahl Ereignistypen– Lokalitätsverhalten zw. Ereignissen und ProfilenLokalitätsverhalten zw. Ereignissen und Profilen– GesamtprofilanzahlGesamtprofilanzahl

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

15/20

Experimente: Auswahl (1)Experimente: Auswahl (1)

• Einfluss der GesamtprofilanzahlEinfluss der Gesamtprofilanzahl

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

16/20

Experimente: Auswahl (2)Experimente: Auswahl (2)

• Einfluss der erfüllenden EreignisseEinfluss der erfüllenden Ereignisse

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

17/20

Experimente: Auswahl (3)Experimente: Auswahl (3)

• Einfluss der VermittleranzahlEinfluss der Vermittleranzahl

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

18/20

Experimente: FazitExperimente: Fazit

• Ergebnisse (Überblick)Ergebnisse (Überblick)– ProfilweiterleitungProfilweiterleitung

• Meist beste Filtereffizienz und geringste NetzlastMeist beste Filtereffizienz und geringste Netzlast• Jedoch größten SpeicherbedarfJedoch größten Speicherbedarf

– EreignisweiterleitungEreignisweiterleitung• Sehr hohe NetzlastSehr hohe Netzlast• Speicherbedarf optimalSpeicherbedarf optimal• Hoher Anteil passender Ereignisse Hoher Anteil passender Ereignisse beste beste

FiltereffizienzFiltereffizienz• Hohe Profilanzahl Hohe Profilanzahl beste Skalierbarkeit beste Skalierbarkeit

– RendezvousknotenRendezvousknoten• Unter keiner getesteten Konfiguration bessere Unter keiner getesteten Konfiguration bessere

Ergebnisse als andere VerfahrenErgebnisse als andere VerfahrenZentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

19/20

GliederungGliederung

• Zentralisierte FilterungZentralisierte Filterung

• Verteilte FilterungVerteilte Filterung

• ExperimenteExperimente

• ZusammenfassungZusammenfassung

20/20

ZusammenfassungZusammenfassung

• Zentrale Filterkomponente PrimAS mit neuer Zentrale Filterkomponente PrimAS mit neuer Filterstruktur Filterstruktur

• Verteiltes Benachrichtigungssystem DAS mit Verteiltes Benachrichtigungssystem DAS mit drei verteilten Filteralgorithmendrei verteilten Filteralgorithmen

• Experimente: Optimaler Algorithmus abhängig Experimente: Optimaler Algorithmus abhängig von Systemlast, -nutzung und Anwendungvon Systemlast, -nutzung und Anwendung

System sollte verschiedene Filteralgorithmen System sollte verschiedene Filteralgorithmen unterstützen und dynamisch anpassenunterstützen und dynamisch anpassen

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

21/20

LiteraturLiteratur

[Bit02] S. Bittner: [Bit02] S. Bittner: Implementierung eines effizienten Matchingverfahrens für Implementierung eines effizienten Matchingverfahrens für BenachrichtigungssystemeBenachrichtigungssysteme, Studienarbeit, Freie Universität Berlin, Institut , Studienarbeit, Freie Universität Berlin, Institut für Informatik, September 2002.für Informatik, September 2002.

[Bit03] S. Bittner: [Bit03] S. Bittner: Entwurf und Analyse eines effizienten verteilten Entwurf und Analyse eines effizienten verteilten BenachrichtigungssystemsBenachrichtigungssystems. Diplomarbeit, Freie Universität Berlin, Institut . Diplomarbeit, Freie Universität Berlin, Institut für Informatik, September 2003.für Informatik, September 2003.

[CRW99] A. Carzaniga, D. S. Rosenblum, A. L. Wolf: [CRW99] A. Carzaniga, D. S. Rosenblum, A. L. Wolf: Interfaces and Algorithms Interfaces and Algorithms for a Wide-Area Event Notification Servicefor a Wide-Area Event Notification Service. Technischer Bericht CU-CS-888-. Technischer Bericht CU-CS-888-99, Universität Colorado, Fachbereich Informatik, Oktober 1999.99, Universität Colorado, Fachbereich Informatik, Oktober 1999.

[GS95] J. Gough und G. Smith: [GS95] J. Gough und G. Smith: Efficient Recognition of Events in a Distributed Efficient Recognition of Events in a Distributed SystemSystem. In: . In: Proceedings of the 18th Australasian Computer Science Proceedings of the 18th Australasian Computer Science Conference (ACSC-18)Conference (ACSC-18),, Adelaide, Australien, 1.-3. Februar 1995. Adelaide, Australien, 1.-3. Februar 1995.

[HB02] A. Hinze und S. Bittner: [HB02] A. Hinze und S. Bittner: Efficient Distribution-Based Event FilteringEfficient Distribution-Based Event Filtering. In: . In: Proceedings of the International Conference on Distributed Computing Proceedings of the International Conference on Distributed Computing Systems Workshops (ICDCSW´02),Systems Workshops (ICDCSW´02), Wien, Österreich, 2.-5. Juli 2002. Wien, Österreich, 2.-5. Juli 2002.

[PB02] P. Pietzuch, J. Bacon: [PB02] P. Pietzuch, J. Bacon: Hermes: A Distributed Event-Based Middleware Hermes: A Distributed Event-Based Middleware ArchitectureArchitecture. . In: Proceedings of the International Conference on Distributed In: Proceedings of the International Conference on Distributed Computing Systems Workshops (ICDCSW´02),Computing Systems Workshops (ICDCSW´02), Wien, Österreich, 2.-5. Juli Wien, Österreich, 2.-5. Juli 2002.2002.