Effiziente Filterung in zentralisierten und verteilten Benachrichtigungssystemen Sven Bittner, 7....

Effiziente Filterung Effiziente Filterung in zentralisierten und verteilten in zentralisierten und verteilten

BenachrichtigungssystemenBenachrichtigungssystemen

Sven Bittner, 7Sven Bittner, 7. November 2003. November 2003

Arbeitsgruppe Datenbanken und Informationssysteme,Arbeitsgruppe Datenbanken und Informationssysteme,Prof. Schweppe, Freie Universität BerlinProf. Schweppe, Freie Universität Berlin

2/15

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/15

GliederungGliederung

• Zentralisierte FilterungZentralisierte Filterung

• Verteilte FilterungVerteilte Filterung

• ExperimenteExperimente

• ZusammenfassungZusammenfassung

4/15

Zentralisierte FilterungZentralisierte Filterung

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

–– Hauptspeicherbedarf sehr großHauptspeicherbedarf sehr groß

–– 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

5/15

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 [Bit02,Bit03] – System Erweiterte Struktur [Bit02,Bit03] – System PrimASPrimAS– 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

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

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

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

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

6/15

Verteilte FilterungVerteilte Filterung

1

3 4

5

BSBS

VerteiltesVerteiltes

62 Zentrale Filter-

komponenten

62

Azyklisches

Overlaynetz

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

S

A

Kommunikation mit

beliebigen Vermittler

7/15

• VerteilungsstrategienVerteilungsstrategien– Ereignisweiterleitung (EW)Ereignisweiterleitung (EW)

• Filterung nah bei den AbonnentenFilterung nah bei den Abonnenten• Kein Verbreiten von ProfilenKein Verbreiten 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

8/15

Verteilte Filterung: Verteilte Filterung: ProfilweiterleitungProfilweiterleitung

– Profilweiterleitung (PW)Profilweiterleitung (PW)• Filterung nah bei AnbieternFilterung nah bei 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

9/15

– Rendezvousknoten (RK)Rendezvousknoten (RK)• Weiterleitung aller Profile und Ereignissen an RKWeiterleitung aller Profile und Ereignissen an RK• PraxisPraxis

– Vermittler auf Weg von Abonnenten zu RK speichern Vermittler auf Weg von Abonnenten zu RK speichern ebenfalls Profilinformationenebenfalls Profilinformationen

– Ereignisse werden auch auf dem Weg zum RK Ereignisse werden auch auf dem Weg zum RK gefiltertgefiltert

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

10/15

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 passender EreignisseAnteil passender Ereignisse– VermittlerzahlVermittlerzahl– Überdeckungen zwischen ProfilenÜberdeckungen zwischen Profilen– Anzahl EreignistypenAnzahl Ereignistypen– Lokalitätverhalten zw. Ereignissen und ProfilenLokalitätverhalten zw. Ereignissen und Profilen– GesamtprofilanzahlGesamtprofilanzahl

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

11/15

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

• Einfluss der GesamtprofilanzahlEinfluss der Gesamtprofilanzahl

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

12/15

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

• Einfluss erfüllende EreignisseEinfluss erfüllende Ereignisse

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

13/15

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

• Einfluss VermittlerEinfluss Vermittler

Zentralisierte FilterungZentralisierte Filterung Verteilte FilterungVerteilte Filterung ExperimenteExperimente ZusammenfassungZusammenfassung

14/15

Experimente: FazitExperimente: Fazit

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

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

– EreignisweiterleitungEreignisweiterleitung• Sehr hohe Netzlast Sehr 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

15/15

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

16/15

LiteraturLiteratur

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

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

[GS95] J. Gough und G. Smith: [GS95] J. Gough und G. Smith: Efficient Recognition of Events Efficient Recognition of Events in a Distributed Systemin a Distributed System. In: . In: Proceedings of the 18th Proceedings of the 18th Australasian Computer Science Conference (ACSC-18)Australasian Computer Science 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 Efficient Distribution-Based Event FilteringEvent Filtering. In: Proceedings of Internation Conference of . In: Proceedings of Internation Conference of Distributed Computing Systems Workshops (ICDCSW´02), Distributed Computing Systems Workshops (ICDCSW´02), Wien, Österreich, 2.-5. Juli 2002.Wien, Österreich, 2.-5. Juli 2002.