Large-scale content based publish, subscribe systems [Elektronische Ressource] / vorgelegt von Gero Mühl

Gero M"Uhl

Sujets

• Informatik

Informations

• Publié par: technischen_universitat_darmstadt
• Publié le: 01 janvier 2002
• Nombre de lectures: 28
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Large-Scale Content-Based
Publish/Subscribe Systems
Vom Fachbereich Informatik
der Technischen Universitat Darmstadt
genehmigte
Dissertation
zur Erlangung des akademischen Grades
eines Doktor-Ingenieurs (Dr.-Ing.)
vorgelegt von
Dipl.-Inform. Dipl.-Ing. Gero Muhl
aus Ludenscheid
Referenten: Prof. A. P. Buchmann, Ph.D.
J. M. Bacon, Ph.D.
Datum der Einreichung: 19. August 2002 der mundlic hen Prufung: 30. September 2002
Darmstadt 2002, Darmstadter Dissertationen D17Abstract
Today, the architecture of distributed computer systems is dominated by cli-
ent/server platforms relying on synchronous request/reply. This architecture is
not well suited to implement information-driven applications like news delivery,
stock quoting, air tra c control, and dissemination of auction bids due to the
inherent mismatch between the demands of these and the character-
istics of those platforms. In contrast to that, publish/subscribe directly re ects
the intrinsic behavior of information-driven applications because communication
here is indirect and initiated by producers of information: Producers publish
noti cations and these are delivered to subscribed consumers by the help of a
noti cation service that decouples the producers and the consumers. Therefore,
publish/subscribe should be the rst choice for implementing such applications.
The expressiveness of the noti cation selection mechanism used by the con-
sumers to describe the noti cations they are interested in is crucial for the
exibilit y of a noti cation service. Content-based noti cation selection is most
expressive because it allows to evaluate lter predicates over the whole con-
tent of a noti cation. The advantage in expressiveness compared to channel-
or subject-based selection results in increased exibilit y facilitating extensibil-
ity and change. On the other hand, scalable implementations of content-based
noti cation services are di cult to realize. Indeed, the expressiveness of noti-
cation selection must be carefully chosen in large-scale systems, because ex-
pressiveness and scalability are interdependent. Hence, the most fundamental
problem in the area of content-based publish/subscribe systems is probably the
scalable routing of noti cations from their producers to their respective con-
sumers. Unfortunately, existing content-based noti cation services are not ma-
ture enough to be used in large-scale, widely-distributed environments. Most
existing noti cation services are either centralized, use o oding, or use simple
routing algorithms that assume that each event broker has global knowledge
about all active subscriptions. All these approaches exhibit severe scalability
problems in large-scale systems. In contrast to that, this thesis concentrates on
mechanisms to improve the scalability of content-based routing algorithms and
presents more advanced routing algorithms that do not rely on global knowledge.
The algorithms presented here exploit similarities between subscriptions by us-
ing identity- and covering-tests, and by merging lters. While identity-based
routing is a simpli ed version of covering-based routing, merging-based routing
iis more advanced because it exploits the concept of lter merging. Furthermore,
the idea of imperfect routing algorithms is introduced.
The thesis consists of a theoretical and a practical part. The theoretical part
presents a formal speci cation of publish/subscribe systems, a routing frame-
work and a set of routing algorithms, and discusses how the routing optimiza-
tions can be broken down to the actual data/ lter model. The practical part
presents the implementation of the Rebeca noti cation service which supports
advertisements and all the routing algorithms mentioned above. A detailed prac-
tical evaluation of the implemented based upon the prototype is also
presented.
iiZusammenfassung
Heutzutage wird die Architektur verteilter Systeme von Client/Server-Platt-
formen dominiert, die auf dem synchronen Request/Reply Paradigma aufbauen.
Diese Architektur ist jedoch nicht dafur geeignet, informationsgetriebene Appli-
kationen (z.B. Nachrichtendienste, Aktienkursdienste, Flugub erwachungsdienste
oder die Verbreitung von Auktionsgeboten) zu implementieren. Dies liegt dar-
an, dass die Anforderungen dieser Applikationen und die Charakteristika von
Client/Server Plattformen sich grundlegend voneinander unterscheiden. Im Ge-
gensatz dazu bilden Publish/Subscribe Systeme die Eigenschaften von informa-
tionsgetriebenen Applikationen direkt ab, da in diesem Fall die Kommunikation
indirekt ist und vom Produzenten der jeweiligen Informationen angesto en wird:
Produzenten vero en tlichen Benachrichtigungen und diese werden allen subskri-
bierten Konsumenten durch einen zwischengeschalteten Benachrichtigungsdienst
zugestellt. Daher bieten sich Publish/Subscribe-basierte Implementationen fur
die Umsetzung derartiger Applikationen an.
Die Ausdrucksfahigkeit der von den Konsumenten benutzten Nachrichten-
selektion ist entscheidend fur die Flexibilitat eines Benachrichtigungsdienstes.
Inhaltsbasierte Nachrichtenselektion ist am ausdrucksstarksten, weil in diesem
Fall Pradikate ub er dem gesamten Inhalt einer Nachricht ausgedruc kt werden
konnen. Diese im Vergleich zu kanalbasierter und themenbasierter Selektion
erhohte Ausdrucksfahigkeit vergro ert die Flexibilitat und begunstigt somit die
Erweiterbarkeit und Anderbarkeit. Andererseits ist ein skalierbarer inhaltsba-
sierter Benachrichtigungsdienst schwierig zu realisieren. In der Tat muss die
Ausdrucksfahigkeit der Nachrichtenselektion in gro en Systemen sorgfaltig fest-
gelegt werden, weil Ausdrucksfahigkeit und Skalierbarkeit voneinander abhangig
sind. Daher ist das wohl grundlegendste Problem im Bereich der inhaltsbasierten
Publish/Subscribe Systeme das skalierbare Routen von Nachrichten von den Pro-
duzenten zu den entsprechenden Konsumenten. Unglucklicherweise sind die heu-
tigen Benachrichtigungsdienste nicht weit genug entwickelt, um in gro en, weit
verteilten Umgebungen genutzt werden zu konnen. Die meisten existierenden
Benachrichtigungsdienste sind entweder zentralisiert, benutzen Flooding\ oder
"
basieren auf einfachen Routing-Algorithmen, die annehmen, dass jeder Broker
globales Wissen uber alle im System aktiven Subskriptionen hat. Diese Ansatze
haben allerdings ausgepragte Skalierbarkeitsprobleme in gro en Systemen. Die-
se Arbeit konzentriert sich auf Mechanismen, welche die Skalierbarkeit von in-
iiihaltsbasierten Routing-Algorithmen erhohen und prasentiert verbesserte Algo-
rithmen, die kein globales Wissen voraussetzen. Die Algorithmen basieren auf
Tests, die bestimmte Ahnlichkeiten\ zwischen Subskriptionen erkennen konnen
"(Identitats- und Uberdeckungstests) und auf dem Konzept der Verschmelzung
von Filtern. Daruber hinaus wird auch die Idee der nicht perfekten\ Routing-
"
Algorithmen eingefuhrt.
Im Einzelnen besteht die hier vorgestellte Arbeit aus einem theoretischen
und einem praktischen Teil. Der theoretische Teil stellt eine formale Spezi-
k ation von Publish/Subscribe Systemen, ein Routing-Framework und einige
Routing-Algorithmen vor. Daneben wird auch diskutiert, wie die vorgeschlage-
nen Routing-Optimierungen auf das eigentliche Daten- und Filtermodell her-
untergebrochen werden konnen. Der praktische Teil der Arbeit stellt die Im-
plementierung des Benachrichtigungsdienstes Rebeca vor, der die diskutier-
ten Routing-Algorithmen und zusatzlich zu Subskriptionen auch Ankundigun-
gen von Produzenten unterstutzt. Au erdem wird eine detaillierte praktische
Evaluation der Routing-Algorithmen vorgestellt, die auf dem implementierten
Prototypen basiert.
ivPreface
Acknowlegements
First of all I would like to thank my advisor Prof. Alejandro P. Buchmann,
Ph.D., for his invaluable help and advice, and Jean M. Bacon, Ph.D. for tak-
ing over the part of the second referee. Special thanks go to Ludger Fiege and
Dr. Felix C. G artner. It has been a great pleasure to work with them. I also ap-
preciate my friends and colleagues in the \Databases and Distributed Systems"
group as well as in the Ph.D. Program \Enabling Technologies for Electronic
Commerce" for their friendship and support. Furthermore, I am grateful to
the DFG (Deutsche Forschungsgemeinschaft) that funded my work in form of a
scholarship as part of the Ph.D. Program \Enabling Technologies for Electronic
Commerce". Last but not least, I would like to thank my family for supporting
me.
Publications
Parts of this Thesis are based on previous publications: Chapter 2 is based on
joint work with Ludger Fiege and Felix C. G artner [42]. 4 is partially
based on joint work with Ludger Fiege and Alejandro Buchmann [73, 75, 77].
Chapter 6 is based on a publication with Ludger Fiege, Felix C. G artner, and
Alejandro Buchmann [78]. A number of additional publications has not been
incorporated into this thesis [38, 41, 43, 74, 76].
vviContents
1 Introduction 1
1.1 Publish/Subscribe Systems . . . . . . . . . . . . . . . . . . . . . 2
1.2 Noti cation Selection Mechanisms . . . . . . . . . . . . . . . . . 3
1.3 Content-based Routing . . . . . . . . . . . . . . . . . . . . . . . . 5
1.4 Shortcomings of Current Approaches . . . . . . . . . . . . . . . . 7
1.5 Focus and Contribution of this Thesis . . . . . .