MIDDLEWARE SYSTEMS
RESEARCH GROUP
Event Processing with the
PADRES Publish/Subscribe
System
The PADRES Team
http://www.padres.msrg.utoronto.ca
Hans-Arno Jacobsen
Bell University Laboratory Chair
Middleware Systems Research Group
University of Toronto
Current PADRES Team






Chen Chen
Alex Cheung
Alton Chiu
Amer Farroukh
Patrick Lee
Guoli Li







MIDDLEWARE SYSTEMS
RESEARCH GROUP
Bala Maniymaran
Serge Mankovskii, CA
Vinod Muthusamy
Reza Sherafat
Naweed Tajuddin
Chunyang Ye
Young Yoon
Countless alumni (see our web site.)
PADRES started around 2004
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
2
Try it out: Java Kick Start PADRES!
MIDDLEWARE SYSTEMS
RESEARCH GROUP
http://www.padres.msrg.utoronto.ca
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
3
Querying the Future
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
MIDDLEWARE SYSTEMS
RESEARCH GROUP
4
Amazon to Chapters to You ....
Monday, October 10th in Cyberspace
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Thursday, November 15th,
in Toronto
Your book “...”
is available
at ....
$10 off
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
5
Border Security Scenario
MIDDLEWARE SYSTEMS
RESEARCH GROUP
[class,audit], [firm,ACME], [trust, 0]
[class, reading],[shipID,ACME123],[level, 4]
[class,manifest],[shipID,ACME123],[firm,ACME]
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
6
Business Process Example
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Loan Application Processing
Store in
DB
Request
… Approval
Reject
Credit
check 2
Credit
check
Check
score
Check
score 2
Approve
else
else
…
Request
Submission
Copyright © 2008 - Hans-Arno Jacobsen
Send to
officer
Check
Completion
CANOE Summer School, Norway, 2009
7
Large-scale Business Processes
Vendor
Goods
selection
Goods delivery
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Dispatch B
Packaging
Pick-up goods
Out-stock B
FedEx
Delivery
Sale
prediction
Sale
Manufactory
Confirm
features
Sign
Contract
Fill out-stock
bill
Control
Fill dispatch
bill
Material
Out-stock B
Make plan
Out
Take
Assign
Target price
Finance
Check stock
Determinate
plan
Raw
materials
Execute
plan
Audit
Process
control
Raw
Pay
Credit card
Check
Check dealer
Check credit
Approval
Approval
Signature
Confirm
Monitoring
Feature
selection
Print receipt
Statistic
Marketing
Process
Check order
Design
Prototype
Warehouse
Fill order
Determinate
plan
CCC
administrate
Pick up
Requirement
collection
Feedback
Strategy
Design
Copyright © 2008 - Hans-Arno Jacobsen
Monitor
Validate
Affirm order
Chart
Marketing
Manufactory
CANOE Summer School, Norway, 2009
Order
Payment
8
What is the Common Denominator?

Many applications are driven by asynchronous state
transitions.


Something happens, … an appropriate reaction is expected
and required.
Asynchronous state transitions represent events.


MIDDLEWARE SYSTEMS
RESEARCH GROUP
A process is triggered, a request submitted, …
Many applications require event management and
processing capabilities to run effectively.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
9
In Terms of the Examples

These applications are driven by events





MIDDLEWARE SYSTEMS
RESEARCH GROUP
Information matching the query is found and indexed
Person walks by a bookstore
Loan request is submitted online
Radioactivity is detected
Abstractly speaking events are disseminated and filtered
against expressions or queries
events
Copyright © 2008 - Hans-Arno Jacobsen
queries
CANOE Summer School, Norway, 2009
10
What Event Processing Support is
Required ?
MIDDLEWARE SYSTEMS
RESEARCH GROUP

De-coupled & loosely coupled many-to-many
interactions

Fine-grained filtering

In-network processing

Composite event detection and event correlation

Event dissemination
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
11
Many Applications are Event-based
Supply chain and logistics
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Workflows, business processes
and job scheduling
A
E
F
B
C
D
Event-Based
Light
Service oriented architectures
Copyright © 2008 - Hans-Arno Jacobsen
RFID and sensor networks
12
CANOE Summer School, Norway, 2009
What is an event?

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Etymology

Latin: eventus;

evenire to happen;

e- + venire
Copyright © 2008 - Hans-Arno Jacobsen
to come
CANOE Summer School, Norway, 2009
13
Various Interpretations





MIDDLEWARE SYSTEMS
RESEARCH GROUP
A postulated outcome, something that follows as
a result or consequence, condition, or eventuality;
“in the event that I am not there, you may …”
Any of the contests in a program of sports, a social
occasion or activity, a world event
The fundamental entity of observed physical
reality represented by a point designated by three
coordinates of place and one of time in the
space-time continuum postulated by the theory of
relativity
A subset of the possible outcomes of an
experiment (probabilities)
Something that happens, a noteworthy
happening, an occurrence
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
14
Event – My Working Definition





MIDDLEWARE SYSTEMS
RESEARCH GROUP
An event is an instantaneous and asynchronous state
transition in the environment of interest to applications,
systems, users.
Event versus event occurrence
 Like type or class versus instance
In my definition events do not extend over time
 Interval events are defined by starting and ending events
(a.k.a. composite events)
My definition does not capture world events
 Maybe important for a theory of events, but less so for the
effective processing of events
My definition does not capture interval events
 Events associated with a time span, but those can be
modeled as composite events
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
15
Synonymously Used
MIDDLEWARE SYSTEMS
RESEARCH GROUP
The terms
 Event
 Event occurrence
 (Event) message
 Event object
are often used synonymously in practice.
 Also the pattern for detecting an event is
often simply referred to as event.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
16
Similarly, …




Event source
Event producer
Event generation
Event publisher
Copyright © 2008 - Hans-Arno Jacobsen
MIDDLEWARE SYSTEMS
RESEARCH GROUP




… sink
… consumer
… capture
… subscriber
CANOE Summer School, Norway, 2009
17
Event Processing

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Event Processing is an emerging area and discipline
that aims to define and develop







Abstractions
Architectures
Systems
Languages
Patterns
Models
Standards
for the processing of events in systems, applications,
and by end users.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
18
A Note on CEP


Complex Event Processing (CEP)
Event processing must not be complex


MIDDLEWARE SYSTEMS
RESEARCH GROUP
Or else, a marketing nightmare, I suspect 
Meant was probably Complex-event Processing

Or maybe the processing of complex events

Not the complex processing of events

Let’s just keep to Event Processing and try to
make it as simple as possible, 
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
19
Events


MIDDLEWARE SYSTEMS
RESEARCH GROUP
Many applications are inherently
event-based.
An event is an instantaneous and
asynchronous state transition in the
environment of interest to
applications, systems, users.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
20
Agenda
MIDDLEWARE SYSTEMS
RESEARCH GROUP

What is the right abstractions for processing
events?

Our point of view

PADRES Event & Services Bus (ESB )

Innovative & Advanced Features

Building Applications with PADRES
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
21
What Abstractions Do Not Work?



Great for managing historic data
But what about future data (e.g., events)
Data streams



Cum gran
salis
Databases

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Great for managing structured streams of tuples
But what about un-structured, multi-typed, sporadic, unordered events from many sources
Rule-based expert systems


Great for inference and reasoning
But what about managing large numbers of fined-grained
filters in distributed environments
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
22
What Abstractions Enable Event
Processing?

MIDDLEWARE SYSTEMS
RESEARCH GROUP
The afore-mentioned points can best be
addressed by


The content-based publish/subscribe model
Realized by content-based message routing

Events are conveyed as publications.

Event listening, filtering and correlating is
based on content-based subscriptions
managed by the pub/sub system.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
23
Publish/Subscribe 101

Not all publish/subscribe is equal

Publish/Subscribe models and evolution

Channel-based



OMG Data Dissemination Service (partially), …
Content-based


WS Notifications, OMG Data Dissemination Service …
Type-based


OMG CORBA Event Service, …
Topic-based


MIDDLEWARE SYSTEMS
RESEARCH GROUP
The PADRES ESB (see below), …
State-based
Subject Spaces
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
24
Content-based Publish/Subscribe
TSX
Stock markets
NASDAQ
NYSE
Publisher
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Publisher
Publications
Broker(s)
Subscriptions:
IBM > 85
ORCL < 10
JNJ > 60
Notification
Subscriptions
Subscriber
Copyright © 2008 - Hans-Arno Jacobsen
Notification
Subscriber
CANOE Summer School, Norway, 2009
25
That’s Like Data Base Querying  !!
publication
subscriptions
data tuples
sets of tuples
About future
About past
query
MIDDLEWARE SYSTEMS
RESEARCH GROUP
sets of tuples
Query and subscription are very similar.
Data tuples and publication are very similar.
However, the two problem statements are inverse.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
26
The Content-based Model
events
MIDDLEWARE SYSTEMS
RESEARCH GROUP
P/S

Language and data model
notifications
Boolean functions over predicates
 Predicates are attribute-operator-value triples
 [class = reading]


Subscriptions are conjunctions of predicates
 [class = reading],[level > 3]

Publications are sets of attribute-value pairs
 [class,reading],[level,3],[id,5637]
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
27
Publish/Subscribe Matching Problem




MIDDLEWARE SYSTEMS
RESEARCH GROUP
Given a set of subscriptions, S, and a publication, e,
return all s in S matched by e.
e is referred to as event or publication
Splitting hairs
 The Event is the state transition of interest in the
environment
 The Publication is the information about the event
submitted to the publish/subscribe system
Simple problem statement, widely applicable, and lots of
open questions
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
28
Scope of the Content-based Model

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Matching semantic





A subscription matches if all its predicates match
Approximate semantic (e.g., close to, cheap, sunny)
Semantic and similarity-based matching
Probabilistic …
Top-k matches
Example
Treestructured
data
Graphstructured
data
Un-structured
data
Regular
languages
Relational
model
Subscription
XPath
RDF Query
Keywords
Regular
expressions
SQL
Publication
XML
RSS feeds
Text, documents
Sentences over
some alphabet
DBs, i.e., tables
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
29
Content-based Message Routing
MIDDLEWARE SYSTEMS
RESEARCH GROUP
[class,=,stock],[symbol,=,YHOO]
A1 [class,=,stock],[symbol,=,YHOO],[price,>,20]
S1
S1
P1
[class, stock],[symbol, YHOO],[price,25]
[class, stock],[symbol, YHOO],[price,45]
[class, stock],[symbol, MSFT],[price, 55]
P2
S2
A2
S2 [class,=,stock],[price,>,40]
[class,=,stock],[symbol,=,MSFT],[price,>,50]
Event-Based
Content Routing
Flexible
Decoupled
Declarative
Responsive
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
30
Publication Space
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Sub intersecting Adv
height
Pub matching Sub
height
90
75
70
70
20 25
20
weight
Adv: [height > 70],[weight > 25]
Sub: [height > 75],[weight > 20]
Copyright © 2008 - Hans-Arno Jacobsen
32
weight
Sub: [height > 75],[weight > 20]
Pub: [height , 90],[weight , 32]
CANOE Summer School, Norway, 2009
31
Publish/Subscribe in Industry

Standards
 CORBA Event Service
 CORBA Notification
Service
 OMG Data Dissemination
Service
 Java Messaging Service
 WS Eventing
 WS Notification, WS
Topics, WS Brokered
Notifications
 INFO-D (Grid Forum)
 AMQP
Copyright © 2008 - Hans-Arno Jacobsen

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Emerging technologies
 RSS aggregators


Real-time data
dissemination


TIBCO, RTI Inc.,
Mantara Software
Application integration


PubSub.com, FeedTree
Softwired
Hardware-based brokers

CANOE Summer School, Norway, 2009
Sarvega (Intel), Solace
Systems, DataPower
(IBM)
32
Publish/Subscribe in Academia

Research projects









MIDDLEWARE SYSTEMS
RESEARCH GROUP
Elvin (Australia)
Gryphon (IBM)
Hermes (Cambridge)
LeSubscribe (INRIA)
PADRES (Toronto)
REBECA (Darmstadt)
SIENA (Boulder)
ToPSS (Toronto)
… many more
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
33
ToPSS - The Toronto Publish/Subscribe System
Family [2000 – present]
ToPSS

Matching algorithms
 Language expressiveness
vs. efficient matching
Routing protocols
 Network architectures &
scalability
A-ToPSS CS-ToPSS
(matching)
(approximate) (composite subs)
S-ToPSS
L-ToPSS Rb-ToPSS
(semantic)
X-ToPSS
(XML matching)

(location-based)
Higher level abstractions
 Workflow execution
 Monitoring
(subject spaces)
M-ToPSS P2P-ToPSS LB-ToPSS
(mobile)
(peer-to-peer)
Federated-ToPSS
Historic-ToPSS
(historic data)
JS-ToPSS
(job scheduling)
Copyright © 2008 - Hans-Arno Jacobsen
(rule-based)
persistent-ToPSS
(federation of ToPSS brokers)

MIDDLEWARE SYSTEMS
RESEARCH GROUP
CANOE Summer School, Norway, 2009
(load balancing)
Ad hoc-ToPSS
(ad hoc networking)
FT-ToPSS
(fault tolerance)
BPEL-ToPSS
(BPEL execution)
34
Publish/Subscribe

Decoupling and interaction among many
sources & many sinks

Event filtering & matching

Event & data dissemination

Query the future (relaxed later)

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Service orchestration and
choreography
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
35
Agenda

MIDDLEWARE SYSTEMS
RESEARCH GROUP
PADRES Event & Services Bus (ESB )



PADRES ESB & Vision
PADRES Event Language
PADRES Internals

Innovative & Advanced Features

Building Applications with PADRES
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
36
PADRES Events & Services Bus

First generation of students, when I looked away 

http://padres.msrg.utoronto.ca
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Peng Alex David aRno Eli Serge

PADRES is Publish/subscribe Applied to Distributed
Resource Scheduling

PAdres is Distributed REsource Scheduling

http://www.padres.msrg.utoronto.ca
Acknowledgements
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
37
MIDDLEWARE SYSTEMS
RESEARCH GROUP
PADRES Vision
Business Process Management and Business Activity Monitoring
start
Deploy
Control
Redirect
Application
Events
7
add
remove
halt
resume
6
4
3
Visualize
Update
Monitor
...
Business Process Execution
Business Events
Content-based Routing (Publish/Subscribe)
Clients (publisher/subscriber)
Complex Events
Content-based Router
PADRES ESB
Computers
Computers
Laptops
Server Database
Network and
System Events
Server
Computers
Switch
Server Farm
Workstation
Switch
Database
Server
Computing, Storage, and Networking Resources
38
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
Laptops
2015/10/3
Event Management
Framework
38
PADRES Events & Services Bus

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Consists of pub/sub message brokers



Content-based publish/subscribe interface
Content-based message routing
Store-and-forward message queuing

Comprised of a federation of brokers deployed as
overlay

Offers a slim client library for development

Available under the Eclipse Public License (EPL) –
a BSD-like open (source) license model
http://padres.msrg.utoronto.ca
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
39
!
MIDDLEWARE SYSTEMS
RESEARCH GROUP
PADRES EVENT LANGUAGE
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
40
PADRES Event Language






MIDDLEWARE SYSTEMS
RESEARCH GROUP
Event schema
Event instances (a.k.a., publications or events)
Subscriptions (a.k.a., atomic subscriptions)
Composite subscriptions
Historic event queries (a.k.a., historic
subscriptions)
Combinations of the former
The above are unified in the PADRES SQL (PSQL),
not covered today.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
41
PADRES Event Language

Event schema: Advertisements




A1: [class,=,reading], [shipID,=,*], [level,<,10]
A2: [class,=,manifest], [shipID,=,*], [firm,=,*], [content,=,*]
A3: [class,=,audit], [firm,=,*], [trust,>=,0]
Source: Publications / events




MIDDLEWARE SYSTEMS
RESEARCH GROUP
P1: [class, reading],[shipID,ACME123],[level, 4]
P2: [class, manifest],[shipID,ACME123],[firm,ACME]
P3: [class, reading],[shipID,ACME123],[level, 12]
(induced from A1)
(induced from A2)
(not induced from A1)
Sink: Atomic & (composite) subscriptions


S1: [class,=,reading], [level,>,3]
S2: [class,=,audit], [firm,=,*],[trust, >=, 3]
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
42
Composite Subscription I
AND
S5
AND
OR
S1
S3
Composite subscriptions (CS) are used for
event correlation, in-network filtering, and the
detection of composite events (complex event).
A composite event is the constellation of
events being detected by the composite
subscription.
OR
S2
MIDDLEWARE SYSTEMS
RESEARCH GROUP
S4
Use of composite subscriptions:
Event correlation
Business process management (shown later)
Business activity monitoring (shown later)
CS={ {S1 OR S2} AND {S3 OR S4} AND S5 }
Si are atomic subscriptions. I.e., they are satisfied by a
single, multi-attribute publication / event.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
43
Composite Subscription II

A composite subscription consists of atomic subscriptions
connected by operators



MIDDLEWARE SYSTEMS
RESEARCH GROUP
AND, OR
Variable join
firm
AND
Examples:
[class,=,reading], [level,>,3]
OR
[class,=,audit], [firm,=,*], [trust, <=, 3]
shipID
S1
AND
S3
S2
[class,=,reading], [shipID,=,$X], [level,>,3]
AND
[class,=,manifest], [shipID,=,$X], [firm,=,$Y], [content,!=,fertilizer]
AND
[class,=,audit], [firm,=,$Y], [trust,>,7]
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
44
Atomic Historic Event Query

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Future atomic subscription
[class,=,reading], [level,>,3]

Historic atomic subscription
[class,=,reading], [level,>,3],
[start_time,<,NOW]

# of events per match
Hybrid atomic subscription
[class,=,reading],
[level,>,3],
[start_time,=,NOW-1h],
[end_time,=,NOW+4h]
Past
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
now
Future
time
45
Composite Historic Event Query

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Future composite subscription
[class,=,reading],[level,>,3],[shipID,=,$X]
AND
[class,=, manifest], [shipID,=,$X],[content,!=fertilizer]

Historic composite subscription
[class,=,manifest],[firm,=,$X],[start_time,<,NOW]
AND
[class,=,audit],[firm,=,$X],[trust,>,7],[start_time,<,NOW]

Hybrid composite subscription
[class,=,reading],[shipID,=,$X],[level,>,3]
AND
[class,=,manifest],[shipID,=,$X],[firm,=,$Y],
[content,!=,fertilizer]
AND
[class,=,audit],[firm,=,$Y],[trust,>,7],
[start_time,=,now-2 months]
Copyright © 2008 - Hans-Arno Jacobsen
Past
CANOE Summer School, Norway, 2009
# of events
per match
now
Future
time
46
PADRES Event Language

Queries about future events

Queries about past events

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Queries that express composite events
over past and future
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
47
MIDDLEWARE SYSTEMS
RESEARCH GROUP
PADRES INTERNALS
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
48
PADRES Broker
MIDDLEWARE SYSTEMS
RESEARCH GROUP
S
P
Publications
B1
input
queue
B
B
Matching
Engine
+
RoutingB
Table
subscription
temperature > 37
temperature > 40
B
dest
B2
B3
output output
queue queue
B2
B3
B
temperature = 36
38
42
P
S
P = publisher
S = subscriber
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
49
Broker Internals & Routing Tables
MIDDLEWARE SYSTEMS
RESEARCH GROUP
PADRES Broker
Output Queues
Matcher
S1
B2
S1
S2
Pre Processor
Pub/Sub Messages
SRT
B1
IfIf sub
sub intersects
intersects
Send
Sendtoto
S2
[class,=,foo],[attr,>,17]
[class,=,foo],[attr,>,17]
B2B2
S1
[class,=,foo],[attr,>,5]
B3
s
S1
B3
S
s
S2
[class,=,foo],[attr,>,30]
[class,=,foo],[attr,<,4]
PRT S1
pub intersects
matches
IfIf sub
Send
Send to
[class,=,foo],[attr,>,20]
[class,=,foo],[attr,>,20]
B3
B2
[class,=,foo],[attr,>,30]
B1
[class,foo],[attr,24]
[class,foo],[attr,11]
Queue Handler
Advertisement
Copyright © 2008 - Hans-Arno Jacobsen
B4
Post Processor
Forwarder
Input Queue
Queue Handler
Subscription
the International CANOE Summer School, Norway, 2009
CANOE Summer School, Norway, 2009
Publication
50
Algorithm: Subscription Insertion
MIDDLEWARE SYSTEMS
RESEARCH GROUP
firm
CS:
[class,=,reading],[level,>,3],[shipID,=,$X]
S1: [class,=,manifest],[content,!=,fertilizer]
S2:
[class,=,reading],[level,>,3]
AND
[class,=,manifest],[content,!=,fertilizer] ,[shipID,=,$X],[firm,=,$Y]
AND
[class,=,audit],[firm,=,$Y],[trust,>,7]
AND
shipID AND
S3
Root
S1
S2
class,=,reading
class,=,manifest
class,=,audit
level,>,3
content,!=,fertilizer
firm,=,$Y
shipID,=,$X
firm,=,$Y
trust,>,7
shipID,=,$X
AND
S1
Copyright © 2008 - Hans-Arno Jacobsen
S2
CANOE Summer School, Norway, 2009
AND
CS
51
Algorithm: Event Matching
[class, audit],
reading],[level,6],[shipID,ACME123]
manifest],[content,stone],[firm,ACME],[shipID,ACME123]
[firm,ACME],[trust,10]
Root
firm
shipID AND
S1
MIDDLEWARE SYSTEMS
RESEARCH GROUP
AND
S3
S2
class,=,reading
class,=,manifest
class,=,audit
level,>,3
content,!=,fertilizer
firm,=,$Y
shipID,=,$X
firm,=,$Y
trust,>,7
shipID,=,$X
AND
S1
S2
CANOE Summer School, Norway, 2009
Copyright © 2008 - Hans-Arno Jacobsen
AND
CS
52
Routing & Matching
MIDDLEWARE SYSTEMS
RESEARCH GROUP

Content-based matching

Can emulate topic-based model

Built-in composite subscription processing

Initially based on JESS expert system shell

Replaced by our own Rete-like matching
due to limited control over JESS engine
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
53
Agenda
MIDDLEWARE SYSTEMS
RESEARCH GROUP

PADRES Event & Services Bus

Innovative & Advanced Features





Composite Event Detection
Historic Event Query
Robustness and Resilience
Cost-based Event Routing & Detection
Building applications with PADRES
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
54
Innovative & Advanced Features
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Historic
Access
Composite
Events
Management
A
E
F
B
C
D
Security
Robustness
Load
Balancing
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
55
MIDDLEWARE SYSTEMS
RESEARCH GROUP
COMPOSITE EVENT
DETECTION
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
56
Composite Event Detection

MIDDLEWARE SYSTEMS
RESEARCH GROUP
cs
Simple CS routing
AND
cs’
S3
AND
1
P
S cs
p123
s1 s2 s3
S1
6
S2
p1
3
2
P
P
p2
Copyright © 2008 - Hans-Arno Jacobsen
4
CANOE Summer School, Norway, 2009
p3
5
57
Composite Event Detection

MIDDLEWARE SYSTEMS
RESEARCH GROUP
cs
Topology-based CS routing
AND
cs’
P
p1
S1
s1
3p12
s2
2
P
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
6
S2
cs’
p123
4s3
P
p2
cs
cs
S3
AND
1
S
p3
5
58
MIDDLEWARE SYSTEMS
RESEARCH GROUP
HISTORIC EVENT QUERY
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
59
Historic Event Query
MIDDLEWARE SYSTEMS
RESEARCH GROUP
• Partition the publication space
• Assign partitions
Publication space P(A)
P1
P3
S
3
1
3
4
2
2
5
5
Partition
Copyright © 2008 - Hans-Arno Jacobsen
P5
6
1
P
P4
Subscriber
DB Admin
Publisher
P2
CANOE Summer School, Norway, 2009
4
60
Assigning A Partition
MIDDLEWARE SYSTEMS
RESEARCH GROUP
[class,DB_CONTROL],[command,STORE],[db,B3-DB],
[partition_spec,” [class,=,reading],[level,>,0] ”]
Subscriber
• Partitioning
DB Admin
1
• Partial replication
41
• Full replication
1
3
4
3
1
Publisher
P
[class,DB_CONTROL],[command,STORE],[db,B3-DB],
[partition_spec,`[class,=,reading],[level,>,0]`]
[class,=,reading],[level,>,0]
2
5
52
2
Advertisement
Copyright © 2008 - Hans-Arno Jacobsen
S
6
Subscription
CANOE Summer School, Norway, 2009
Publication
Partition
61
MIDDLEWARE SYSTEMS
RESEARCH GROUP
ROBUSTNESS, RESILIENCE &
COST-BASED ROUTING
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
62
General Overlay Network
Robust
Flexible
Self-healing
Adaptive
MIDDLEWARE SYSTEMS
RESEARCH GROUP
S
P
P
PP
P
Congested Link
P
Copyright © 2008 - Hans-Arno Jacobsen
P
CANOE Summer School, Norway, 2009
63
Challenges With General Overlays
• Subscriptions are
routed in loops
• Brokers receive
duplicate
subscriptions
• Subscription copies
exacerbate the
problem
• Same problem for
publications
Copyright © 2008 - Hans-Arno Jacobsen
S
Adv 1
CANOE Summer School, Norway, 2009
MIDDLEWARE SYSTEMS
RESEARCH GROUP
X
S
1
2
3
4
S
5
6
Adv 2
64
TID-based Routing Approach


Each advertisement
is assigned a unique
tree identifier (TID)
Each subscription
has a TID predicate
with a variable
S
MIDDLEWARE SYSTEMS
RESEARCH GROUP
X
1
2
3
4
5
6
Adv 1
Adv 2
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
65
Subscription Routing
S: [class=stock][symbol=*] [TID=$Z]
MIDDLEWARE SYSTEMS
RESEARCH GROUP
S
At Broker 1:
X
SA1 SA2
Adv1:
1
2
3
4
5
6
Adv 1
[class=stock][symbol=IBM] [TID=Adv1]
Adv2:
[class=stock][symbol=HP] [TID=Adv2]
S matching Adv1:
[class=stock][symbol=*][TID=Adv1]
Adv 2
S matching Adv2: [class=stock][symbol=*] [TID=Adv2]
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
66
Publication Routing

Each publication is assigned the TID of its
matching advertisement


MIDDLEWARE SYSTEMS
RESEARCH GROUP
e.g., p [class, stock][symbol,HP][TID, adv_msg_id]
Publications are routed:


Fixed TID routing: a publication is routed to
subscribers along its advertisement tree.
Dynamic publication routing: a publication may be
routed to subscribers across advertisement trees.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
67
Fixed TID Routing
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Adv 1

P
Property

No broker receives
Adv 2
P
duplicate publication
messages
1
2
3
4
5
6
Sub
X
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
68
Dynamic Publication Routing
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Adv 1


Publication’s TID is
changeable
Routing heuristic


Adv 2
P
2
3
4
5
6
Util = Routput / Rsending
Property

1
Changing a
publication’s TID while
in transit will not change
the set of notified
subscribers.
Sub
X
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
69
Side Effect: Faster Matching



MIDDLEWARE SYSTEMS
RESEARCH GROUP
Subscriptions are augmented with TIDs only
once at the first broker.
Other brokers can route the subscription
based on the TID alone.
Similar argument applies to publication
routing.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
70
Evaluation



MIDDLEWARE SYSTEMS
RESEARCH GROUP
32 overlay brokers, 20 publishers, 30
subscribers
20 machines & PlanetLab
Workload


http://research.msrg.utoronto.ca/Padres/DataSets
Yahoo!Finance stock quote traces
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
71
Dense vs. Sparser Topologies
MIDDLEWARE SYSTEMS
RESEARCH GROUP
4%
20%
Note: The benefit is not proportional to the connection degree.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
72
On PlanetLab
Copyright © 2008 - Hans-Arno Jacobsen
MIDDLEWARE SYSTEMS
RESEARCH GROUP
CANOE Summer School, Norway, 2009
73
High Publication Rate
MIDDLEWARE SYSTEMS
RESEARCH GROUP
stabilized
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
74
Publication Burst
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Burst
1500msg/min
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
75
With Broker Failures
MIDDLEWARE SYSTEMS
RESEARCH GROUP
2nd failure
1st failure
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
76
Advantages of TID-based Routing





MIDDLEWARE SYSTEMS
RESEARCH GROUP
Retains the publish/subscribe client interface
Speeds up subscription and publication
matching
Avoids duplicate subscriptions and
publications
Routes publications dynamically across
multiple alternative paths
Enables routing around failures, congestion
and load imbalances
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
77
MIDDLEWARE SYSTEMS
RESEARCH GROUP
COST-BASED EVENT
ROUTING & DETECTION
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
78
Implications for CS Routing
MIDDLEWARE SYSTEMS
RESEARCH GROUP
• CS may be routed according to potential
publication traffic, bandwidth, latency, etc.
Adv 2
Adv 2
2
1
Adv 1
2
3
1
CS={S1 AND S2} Adv 1
CS={S1 AND S2}
(b)
(a)
Copyright © 2008 - Hans-Arno Jacobsen
3
CANOE Summer School, Norway, 2009
79
Topology-based CS Routing
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Adv 3
Adv 2
2
1
7
S2
3
5
S1
4
CS’
8
6
S3
Broker 4 and 8
are the join
point brokers
9
Adv 1
CS
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
CS={{S1 AND S2} ANDS3}
80
Dynamic CS Routing (DCSR)
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Adv 3
Adv 2
1
2
3
4
5
6
7
CS’
8
S3
Broker 5 and 8
are the join
point brokers
S2
Adv 1
9
S1
CS
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
CS={{S1 AND S2} ANDS3}
81
Dynamic Join Point Movement
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Adv 3
Adv 2
S1
1
2
7
3
4
8 CS
6
9
Broker 1 and 8
are the join
point brokers
CS’
5
Adv 1
CS={{S1 AND S2} ANDS3}
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
82
Composite Event Detection
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
MIDDLEWARE SYSTEMS
RESEARCH GROUP
83
MIDDLEWARE SYSTEMS
RESEARCH GROUP
BUILDING APPLICATIONS
WITH PADRES
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
84
Applications Built with PADRES








MIDDLEWARE SYSTEMS
RESEARCH GROUP
Semantic data fusion in sensor networks
(DEBS’07)
Service selection (DEBS’08)
Resource discovery (DEBS’09)
Job scheduling (Middleware’04)
Business process execution
Business activity monitoring
SLA monitoring & control (CASCON’08 & ’09)
…
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
85
Business Process Deployment
MIDDLEWARE SYSTEMS
RESEARCH GROUP
BPEL
Receive
sub/advs
sub/advs
sub/advs
sub/advs
JobCD
Job
Job
B
Receive
Assign
Deployer
Flow
Invoke
Wait
Reply
1
PADRES Broker Overlay
3
sub/advs
Receive
Copyright © 2008 - Hans-Arno Jacobsen
4
2
5
sub/advs
Assign
Activity
Agent
6
sub/advs
Invoke
sub/advs
Reply
Process Deployer
CANOE Summer School, Norway, 2009
86
Distributed BPEL Execution
MIDDLEWARE SYSTEMS
RESEARCH GROUP
END
BPEL
WS Gateway
Agent
Receive
Assign
Flow
Invoke
WS
Client
Wait
Reply
1
PADRES Broker Overlay
3
2
6
4
Web
Service
5
Pub/Sub
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
Web
Service
HTTP/SOAP
87
Evaluation

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Setup


Cluster with 20 nodes
Different approaches




Centralized
Clustered
Distributed
Workloads



BPEL process with 2 external Web services
Parallel: BPEL process with 10 parallel branches
Sequential: BPEL process with 2 parallel branches
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
88
Changing Request Rate
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
MIDDLEWARE SYSTEMS
RESEARCH GROUP
89
Sequential vs. Parallel
(b) Parallel Process
(a) Sequence Process
Copyright © 2008 - Hans-Arno Jacobsen
MIDDLEWARE SYSTEMS
RESEARCH GROUP
CANOE Summer School, Norway, 2009
90
Publish/Subscribe



MIDDLEWARE SYSTEMS
RESEARCH GROUP
Not just message dissemination
Viable solution for building event processing
networks and event-based applications
Besides dissemination and decoupling,
pub/sub offers efficient



Event filtering
Event correlation
In-network event processing
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
91
Summary: Benefits of Content-based
Publish/Subscribe




MIDDLEWARE SYSTEMS
RESEARCH GROUP
Simplifies IT development and maintenance by
decoupling enterprise components
Supports sophisticated interactions among
components using expressive subscription
languages – going beyond the limits of topics
Allows fine-grained queries and event
management
Achieves scalability with in-network filtering
and processing
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
92
Conclusions
MIDDLEWARE SYSTEMS
RESEARCH GROUP

The right abstraction for event processing is
content-based publish/subscribe - IMHO

Event processing & publish/subscribe are
interesting research areas.

ToPSS and PADRES explore many aspects
of these areas.
http://padres.msrg.utoronto.ca
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
93
References








The DEBS Conference
http://www.debs.org
July 2009 at Vanderbilt U.
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Everything events Portal
http://www.event-based.org
The PADRES ESB project home
 http://padres.msrg.utoronto.ca
An eQoSystem for declarative distributed applications with SLAs
 http://research.msrg.utoronto.ca/Eqosystem/
The Micro-ToPSS event processing middleware for sensor networks
 http://microToPSS.msrg.utoronto.ca/
Mobile-ToPSS – publish/subscribe for mobile and location-based applications
 http://research.msrg.utoronto.ca/Mobile/
ToPSS - the Toronto Publish/Subscribe System Family Portal
 http://www.ToPSS.biz (coming soon  )
Quantifying events in software to increase modularity & customization in Cbased systems and software-based product lines
 http://www.AspeCtC.net (ACC - the AspeCt-oriented C compiler)
The Middleware Systems Research Group
 http://www.msrg.utoronto.ca
My web site
 http://www.eecg.toronto.edu/~jacobsen
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
@ the University
of Toronto
94
Questions?
MIDDLEWARE SYSTEMS
RESEARCH GROUP
P ADRES
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
95
Cost Model

MIDDLEWARE SYSTEMS
RESEARCH GROUP
Routing cost of CS

Matchin
g Engine
+
Routing
Table
subscription
RC(CS)) =
+
input
queue
+
temperature > 37 B1
temperature > 40 B2

dest
output output
queue queue
B1
B2
Subscription cardinality

|P(S)| : The number of matching
publications per unit of time.

|P(S)|

|P(CS)| =
=
Copyright © 2008 - Hans-Arno Jacobsen
|P(Sl)| + |P(Sr)|
if op = OR
CANOE Summer School, Norway, 2009
96
Faster Matching with TIDs



Subscriptions are
augmented with TIDs
only once at the first
broker.
Other brokers can route
the subscription based
on the TID alone.
Similar argument
applies to publication
routing.
Copyright © 2008 - Hans-Arno Jacobsen
S
MIDDLEWARE SYSTEMS
RESEARCH GROUP
X
S
S
Adv1 Adv2
1
2
3
4
5
6
Adv 1
CANOE Summer School, Norway, 2009
Adv 2
97
Sparser Topology
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
MIDDLEWARE SYSTEMS
RESEARCH GROUP
98
Effect of Subscriber Distance
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Distance
Fixed(ms)
Dynamic(ms)
Improvement
6 Hops
47.202
47.568
-0.78%
10 Hops
64.477
52.895
17.96%
12 Hops
74.416
60.598
18.57%
Max Diff
57.65%
27.39%
CANOE Summer School, Norway, 2009
Copyright © 2008 - Hans-Arno Jacobsen
99
More Publishers
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
MIDDLEWARE SYSTEMS
RESEARCH GROUP
100
Publication Burst
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
MIDDLEWARE SYSTEMS
RESEARCH GROUP
101
More Results

Faster matching



MIDDLEWARE SYSTEMS
RESEARCH GROUP
1926 publications cause 16997 times of matching
operations in the “Dense Topology” experiment.
About 89% of the matching operations can be saved if we
apply the TID-based faster matching.
Overhead of dynamic publication routing


Average CPU usage: 6.3% more than the Fixed routing
Average memory usage: 8.9% more than the Fixed routing
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
102
CS Routing Traffic
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
MIDDLEWARE SYSTEMS
RESEARCH GROUP
103
Summary




MIDDLEWARE SYSTEMS
RESEARCH GROUP
Minimize redundant traffic induced by cycles
Improve scalability and robustness of
pub/sub systems by offering routing path
alternatives
Enable flexible composite subscription
routing
Simplify solutions for failure recovery and
load balancing
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
104
Cost Model

Routing cost of CS


RCB(CS)) = Σi Tin*|P(CSBi)| +
Σi Tmatching*|P(CSBi)| +
Σi Tout_i*|P(CS)|
input
Selection factor (SF)



MIDDLEWARE SYSTEMS
RESEARCH GROUP
output
Rete s
SFA(S) = |σS P(A)| / |P(A)|
e.g., SFA(a = v) = 1 / (max - min)
Subscription cardinality


|P(S)| = Σi ri * SFAi (S)
|P(Sl)| + |P(Sr)|
if op = or
min (|P(Sl)| , |P(Sr)|)
if op = and
|P(CS)| =
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
105
Fast Matching


MIDDLEWARE SYSTEMS
RESEARCH GROUP
1926 publications cause 16997 matching
operations in the “Dense Topology”
experiment.
89% of the matching operations can be
saved with TID-based fast matching.
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
106
CS Routing Traffic
MIDDLEWARE SYSTEMS
RESEARCH GROUP
Simple routing
Topology-based routing
DCSR
3. Join point broker of
topology-based
routing
Msgs
1. CS
Subscriber
2. Publisher with
a higher
publication rate
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
107
Dynamic Join Point Movement
MIDDLEWARE SYSTEMS
RESEARCH GROUP
DCSR (static)
DCSR (changing)
Join Point Movement
CS subscriber
Msgs
Publisher
with a higher
publication
rate
Copyright © 2008 - Hans-Arno Jacobsen
CANOE Summer School, Norway, 2009
108
Descargar

PADRES A Content-based Pub/Sub System