Studienarbeit: Filteralgorithmen für Benachrichtigungssysteme Sven Bittner, 16.Juli 2002.

Studienarbeit:Studienarbeit:

Filteralgorithmen für Filteralgorithmen für BenachrichtigungssystemeBenachrichtigungssysteme

Sven Bittner, 16.Juli 2002 Sven Bittner, 16.Juli 2002

Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 2/20

ZielstellungZielstellung

• Implementierung eines baumbasierten Implementierung eines baumbasierten FilteralgorithmusFilteralgorithmus

• Bessere Filterperformance durch Umordnen der Bessere Filterperformance durch Umordnen der AttributreihenfolgeAttributreihenfolge

• Vergleich mit anderen SystemenVergleich mit anderen Systemen


Baumalgorithmus (gough95)Baumalgorithmus (gough95)

• schnellster Filteralgorithmus (fabret00)schnellster Filteralgorithmus (fabret00)

• Aufbau DFA aus ProfilenAufbau DFA aus Profilen– Zustände: AttributtestsZustände: Attributtests– Übergänge: TestauswertungenÜbergänge: Testauswertungen -Übergang: Nichtzutreffen aller regulären Kanten-Übergang: Nichtzutreffen aller regulären Kanten– Endzustände: Profilmengen der PfadeEndzustände: Profilmengen der Pfade

• FilternFiltern– durchlaufen des Baumesdurchlaufen des Baumes– Benachrichtigen der Profile in EndzuständenBenachrichtigen der Profile in Endzuständen

b

40a

10

b c P120 50

c

c

c

10

20

P3,4,5

100

P4100

P280

P4

100


Baumalgorithmus - BeispielBaumalgorithmus - Beispiel

Profilmenge:Profilmenge:

P1: a=10, b=20, c=50P1: a=10, b=20, c=50

P2: a=40, b=10, c=80P2: a=40, b=10, c=80

P3: a=40, b=20, c=100P3: a=40, b=20, c=100

P4: a=40, c=100P4: a=40, c=100

P5: a=40, b=20, c=100P5: a=40, b=20, c=100

b

40

a

10

b c P120 50

c

c

c

10

20

P3,4,5

100

P4100

P280

P4

100


Baumalgorithmus - Baumalgorithmus - ZustandsübergängeZustandsübergänge

• ElementaufzählungenElementaufzählungen- Speicherverbrauch:- Speicherverbrauch:

Wertebereich a: [0, 1000], 2 DezimalstellenWertebereich a: [0, 1000], 2 Dezimalstellen

Prädikate: a>= 100, a>=500Prädikate: a>= 100, a>=500

Elemente: 90000Elemente: 90000

+ ungeordnete Wertebereiche+ ungeordnete Wertebereiche

• Intervalle (Implementierung)Intervalle (Implementierung)- geordnete Wertebereiche- geordnete Wertebereiche

+ Speicherverbrauch:+ Speicherverbrauch:• 1 Intervall pro Übergang bzw.1 Intervall pro Übergang bzw.• 1 Wert pro Übergang - Halboffenes Intervall1 Wert pro Übergang - Halboffenes Intervall

Leerintervalle (Gleichheitstests)Leerintervalle (Gleichheitstests)

a

100.00, 100.01, 100.02, ..., 499.99 P1

P1,2500.00, 500.01, 500.02, ..., 1000.00

100.00 .. 499.99

a

P1

P1,2500.00 .. 1000.00


Baumalgorithmus - IntervalleBaumalgorithmus - Intervalle

Wertebereich:Wertebereich:

a:a: -100 .. 100-100 .. 100

Profilmenge:Profilmenge:

P1: a=10P1: a=10

P2: a>20P2: a>20

P3: a<7P3: a<7

P4: a=40P4: a=40

Arrays:Arrays:

IntervallIntervall

ProfileProfile

66 P3P3

99

1010 P1P1

2020

3939 P2P2

4040 P2, 3P2, 3

100100 P2P2

a

..6

7..9

10..10

11..20

21..39

40..40

41..

P3

P1

P2

P2,3

P2

KnotenKnoten::


SystembeschreibungSystembeschreibung

• Datentypen: ganze Zahlen, Dezimalzahlen (mit Stellenzahl), Datentypen: ganze Zahlen, Dezimalzahlen (mit Stellenzahl), AufzählungenAufzählungen

• Wertebereiche: aus Datentypen definierenWertebereiche: aus Datentypen definieren

• Operatoren: >, <, =, Mengentest, BereichstestOperatoren: >, <, =, Mengentest, Bereichstest

• Attribut: Name, WertebereichAttribut: Name, Wertebereich

• Ereignistyp: Name, AttributmengeEreignistyp: Name, Attributmenge

• Ereignis: Anbieter, Ereignistyp, Menge von Attribut-Wert-PaarenEreignis: Anbieter, Ereignistyp, Menge von Attribut-Wert-Paaren

• Profil: Ereignistyp, Prädikatmenge, Benachrichtigung(en)Profil: Ereignistyp, Prädikatmenge, Benachrichtigung(en)

• Prädikat: Attribut, Operator, Vergleichswert (z.B. a=10)Prädikat: Attribut, Operator, Vergleichswert (z.B. a=10)


ImplementierungImplementierung

• Sprache: JavaSprache: Java

• Standarddatentypen und Felder statt Standarddatentypen und Felder statt Containerklassen der BibliothekenContainerklassen der Bibliotheken

• Option: Native-Language-Code (C++) bei Option: Native-Language-Code (C++) bei Performanceproblemen (JNI)Performanceproblemen (JNI)

• relationale Datenbank für Speicherung relationale Datenbank für Speicherung persistenter Datenpersistenter Daten


Implementierung - TeilbäumeImplementierung - Teilbäume

• ProblemProblemSpeicherverbrauch des Speicherverbrauch des

BaumesBaumes

• LösungLösung– identifizieren identischer identifizieren identischer

TeilbäumeTeilbäume– gleiche Profilmengen gleiche Profilmengen

gleiche Teilbäumegleiche Teilbäume

• VerbesserungVerbesserung Faktor 7000 (bei 40 Faktor 7000 (bei 40

Profilen)Profilen)

0

50

100

150

200

250

10 15 20 25 30 35 40

Profilanzahl

Sp

eich

er in

MB

Teilbäume als Verweise Teilbäume als Kopien

Speicherverbrauch bei 10 Attributen,1 Ereignistyp

0

5

10

15

20

25

30

35

10 15 20 25 30 35 40

Sp

eich

er in

kB


Implementierung - KnotenzahlImplementierung - Knotenzahl

• ProblemProblemKnotenzahl des BaumesKnotenzahl des Baumes

• LösungLösung– kein Baum, nur 1 kein Baum, nur 1

Knoten pro AttributKnoten pro Attribut– Schneiden der Schneiden der

ProfilmengenProfilmengen

• Verbesserung (Speicher)Verbesserung (Speicher) Faktor 42 (bei 300 Faktor 42 (bei 300

Profilen)Profilen)

0

10000

20000

30000

40000

50000

60000

70000

80000

90000

100000

100 125 150 175 200 225 250 275 300

Profilanzahl

Sp

eich

er in

kB

1 Knoten je Attribut Baum

Speicherverbrauch bei 10 Attributen, 1 Ereignistyp

0

500

1000

1500

2000

2500

100 125 150 175 200 225 250 275 300

Sp

eich

er in

kB

0

0,1

0,2

0,3

0,4

0,5

0,6

0,7

100 125 150 175 200 225 250 275 300

Profilanzahl

Zei

t p

ro E

reig

nis

in m

s

1 Knoten je Attribut BaumAbw.: 1-2%

Matchingzeit bei 10 Attributen, 1 Ereignistyp

0

0,002

0,004

0,006

0,008

0,01

0,012

0,014

100 125 150 175 200 225 250 275 300

Zei

t p

ro E

reig

nis

in m

s


Implementierungsansatz - Implementierungsansatz - Verweise (1)Verweise (1)

• ProblemProblemSpeicherverbrauch der ProfilverweiseSpeicherverbrauch der Profilverweise

• LösungLösung– Verweise als BitlisteVerweise als Bitliste– Verweise als Zwischenraumliste (feste/variable Verweise als Zwischenraumliste (feste/variable

Breite)Breite)

• Beispiel (1000 Profile, 1 Ereignistyp, 10 Beispiel (1000 Profile, 1 Ereignistyp, 10 Attribute)Attribute)– 700 Kanten pro Knoten700 Kanten pro Knoten– 700 Verweise pro Ausgangskante700 Verweise pro Ausgangskante


Implementierungsansatz - Implementierungsansatz - Verweise (2)Verweise (2)

• SpeicherverbrauchSpeicherverbrauch

– Objektverweise(Standardmethode)Objektverweise(Standardmethode)# Kanten * # Profile je Kante * Speicher Verweis * # # Kanten * # Profile je Kante * Speicher Verweis * #

Knoten = 700 * 700 * 4 * 10 = 18.69 MBKnoten = 700 * 700 * 4 * 10 = 18.69 MB

– BitlisteBitlisteFeld aller Profile + # Intervalle * Speicher Bitliste * # Feld aller Profile + # Intervalle * Speicher Bitliste * #

Knoten = 1000 * 4 + 700 * (1000/8) * 10 = 858,4 KBKnoten = 1000 * 4 + 700 * (1000/8) * 10 = 858,4 KB

• VerbesserungVerbesserung Faktor 22Faktor 22


Implem. - Verteilungsabhängigkeit Implem. - Verteilungsabhängigkeit (1)(1)

• Umordnung der Attribute im BaumUmordnung der Attribute im Baum

• zwei Ansätze (hinze02)zwei Ansätze (hinze02)

– A1: Anteil unbedeckter Wertebereich in ProfilenA1: Anteil unbedeckter Wertebereich in Profilen– A2: Anteil unbedeckter Wertebereich in Profilen unter A2: Anteil unbedeckter Wertebereich in Profilen unter

Berücksichtigung der Wahrscheinlichkeit bei Berücksichtigung der Wahrscheinlichkeit bei EreignissenEreignissen

• Nutzung: Übergabe der Profile / Ereignisse beim Nutzung: Übergabe der Profile / Ereignisse beim Aufbau der FilterstrukturAufbau der Filterstruktur

• Erweiterung: Historie + Umordnung bei BedarfErweiterung: Historie + Umordnung bei Bedarf


Implem. - Verteilungsabhängigkeit Implem. - Verteilungsabhängigkeit (2)(2)

• sukzessives Schneiden nach jedem Attributsukzessives Schneiden nach jedem Attribut

• Abbruch (kein Profil passend) bei Erreichen der Abbruch (kein Profil passend) bei Erreichen der leeren Mengeleeren Menge

• u.U. Probleme - Bsp: 10 Knotenu.U. Probleme - Bsp: 10 Knoten– sukzessives Schneiden: max. 18 Mengen sukzessives Schneiden: max. 18 Mengen

schneidenschneiden– 1 Schnitt: 10 Mengen schneiden1 Schnitt: 10 Mengen schneiden

Profile für jeden Event/kleine Attributanzahl Profile für jeden Event/kleine Attributanzahl 1 1 Schnitt aller Attribute schnellerSchnitt aller Attribute schneller

Matchingzeit bei 10 Attributen, 1 Eventtyp

0

2

4

6

8

10

12

500 750 1000 1250 1500 1750 2000 2250 2500 2750 3000

Profilanzahl

Zei

t p

ro E

ven

t in

ms

einmaliges Schneiden sukzessives Schneiden

Matchingzeit bei 20 Attributen, 1 Eventtyp

0

2

4

6

8

10

12

14

16

18

20

500 750 1000 1250 1500 1750 2000 2250 2500 2750 3000

Profilanzahl

Zei

t p

er E

ven

t in

ms

einmaliges Schneiden sukzessives SchneidenAbw.: 1-2% Abw.: 1-2%


VergleichssystemeVergleichssysteme

• CORBA-Notification-Service CORBA-Notification-Service (Common Object Request Broker (Common Object Request Broker Architecture)Architecture)

– Schnittstellenbeschreibung der OMGSchnittstellenbeschreibung der OMG– Implementierung: OpenORB - JavaImplementierung: OpenORB - Java– NS baut auf CORBA-Standard aufNS baut auf CORBA-Standard auf– Erweiterung des Event-Service (kein Filtern)Erweiterung des Event-Service (kein Filtern)– getypte, strukturierte Ereignissegetypte, strukturierte Ereignisse

• Elvin4Elvin4– Implementierung in C, Ansprechen in JavaImplementierung in C, Ansprechen in Java– verteilte Client-/Serverarchitekturverteilte Client-/Serverarchitektur– keine getypten Ereignissekeine getypten Ereignisse

• Simulation durch zusätzliches AttributSimulation durch zusätzliches Attribut• Abonnent: Typ als Prädikat ; Anbieter: zusätzl. Attribut-Wert-Abonnent: Typ als Prädikat ; Anbieter: zusätzl. Attribut-Wert-

PaarPaar


Performance - steigende ProfilzahlPerformance - steigende Profilzahl

• Anstieg etwa linearAnstieg etwa linear

• Elvin4 ca. 18-22 mal Elvin4 ca. 18-22 mal langsamerlangsamer

• CORBA ca. 1800-2800 CORBA ca. 1800-2800 mal langsamermal langsamer

0

200

400

600

800

1000

1200

250 500 750 1000 1250 1500 1750 2000

Profilanzahl

Zei

t p

ro E

reig

nis

in m

s

Filteralgorithmus CORBA Elvin4Abw.: 1-2%

Matchingzeit bei 10 Attributen, 10 Ereignistypen

0

2

4

6

8

10

12

250 500 750 1000 1250 1500 1750 2000

Zei

t p

ro E

reig

nis

in m

s


Performance - steigende Performance - steigende AttributzahlAttributzahl

• Anstieg etwa linearAnstieg etwa linear

• Elvin 10-20 mal Elvin 10-20 mal langsamerlangsamer

• CORBA 1300-1800 mal CORBA 1300-1800 mal langsamerlangsamer

• Filteralgorithmus: Filteralgorithmus: Abweichung wegen Abweichung wegen

sukzes. Schneidensukzes. Schneiden0

500

1000

1500

2000

2500

1 3 5 7 9 11 13 15 17 19

Attributanzahl

Zei

t p

ro E

reig

nis

in m

s


Matchingzeit bei 1 Ereignistyp, 500 Profilen

0

5

10

15

20

25

30

35

40

1 3 5 7 9 11 13 15 17 19

Zei

t p

ro E

reig

nis

in m

s


Performance - steigende TypanzahlPerformance - steigende Typanzahl

• Elvin 14-19 mal Elvin 14-19 mal langsamerlangsamer

• CORBA 1200-3000 mal CORBA 1200-3000 mal langsamerlangsamer

• keine Typunterstützung keine Typunterstützung kein Hindernis (zuerst kein Hindernis (zuerst Typtest) Typtest)

0

200

400

600

800

1000

1200

1400

1600

1800

1 3 5 7 9

Ereignistypanzahl

Zei

t p

ro E

reig

nis

in m

s


Matchingzeit bei 10 Attributen, 500 Profilen

02468

101214161820

1 3 5 7 9

Zei

t p

ro E

reig

nis

in m

s


Systemvergleich - Systemvergleich - ZusammenfassungZusammenfassung

• Geschwindigkeit:Geschwindigkeit:

– Elvin Elvin 10 - 25 mal langsamer 10 - 25 mal langsamer– CORBA CORBA 1200 - 3000 mal langsamer 1200 - 3000 mal langsamer

• Vergleichbarkeit:Vergleichbarkeit:

– Filteralgorithmus: Ansprechen im gleichen Filteralgorithmus: Ansprechen im gleichen AdressraumAdressraum

– Elvin/CORBA: Kommunikation via TCP/IP (Sockets)Elvin/CORBA: Kommunikation via TCP/IP (Sockets)

• COBEA zeigt ähnliche Geschwindigkeiten[Ma98]COBEA zeigt ähnliche Geschwindigkeiten[Ma98]


Ausblick (Diplomarbeit)Ausblick (Diplomarbeit)

– bessere Speichernutzung durch Bitlistenbessere Speichernutzung durch Bitlisten

– Umordnen (Auswertungsreihenfolge) nach Aufbau Umordnen (Auswertungsreihenfolge) nach Aufbau der Strukturder StrukturHistorie aller Ereignisse bzw. deren VerteilungHistorie aller Ereignisse bzw. deren Verteilung

– Verteilung des SystemsVerteilung des Systems

– event. Einarbeitung anderer Filteransätzeevent. Einarbeitung anderer Filteransätze

– Composite Events (Diplomarbeit Steven)Composite Events (Diplomarbeit Steven)


LiteraturLiteratur

• [fabret00] - F. Fabret, F. Llirbat, J.Pereira, and D. Shasha. [fabret00] - F. Fabret, F. Llirbat, J.Pereira, and D. Shasha. Efficient matching for content-based publish/subscribe Efficient matching for content-based publish/subscribe systems. Technical report, INRIA, 2000.systems. Technical report, INRIA, 2000.

• [gough95] - John Gough, Glenn Smith. Efficient [gough95] - John Gough, Glenn Smith. Efficient Recognition of Events in a Distributed System. In Recognition of Events in a Distributed System. In Proceedings of the ACSC-18, 1995.Proceedings of the ACSC-18, 1995.

• [hinze02] - Annika Hinze, Sven Bittner. Efficient [hinze02] - Annika Hinze, Sven Bittner. Efficient Distribution-Based Event Filtering. Proceedings of DEBS at Distribution-Based Event Filtering. Proceedings of DEBS at ICDCS, 2002.ICDCS, 2002.

• [ma98] - Chaoying Ma, Jean Bacon. COBEA: A CORBA-[ma98] - Chaoying Ma, Jean Bacon. COBEA: A CORBA-Based Event Architecture. Cambridge, 1998.Based Event Architecture. Cambridge, 1998.

Date post:	06-Apr-2015
Category:	Documents
Upload:	elfriede-echternach
View:	109 times
Download:	3 times

Studienarbeit: Filteralgorithmen für Benachrichtigungssysteme Sven Bittner, 16.Juli 2002.

Documents