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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 3/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 4/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 5/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 6/20
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::
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 7/20
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)
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 8/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 9/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 10/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 11/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 12/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 13/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 14/20
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%
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 15/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 16/20
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 17/20
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
Filteralgorithmus CORBA Elvin4Abw.: 1-2%
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
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 18/20
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
Filteralgorithmus CORBA Elvin4Abw.: 1-2%
Matchingzeit bei 10 Attributen, 500 Profilen
02468
101214161820
1 3 5 7 9
Zei
t p
ro E
reig
nis
in m
s
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 19/20
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]
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 20/20
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)
Sven Bittner - Filteralgorithmen für Benachrichtigungssysteme 21/20
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.