Transcript msem-apr15 - Carnegie Mellon University

Mercury: Building Distributed
Applications with PublishSubscribe
Ashwin Bharambe
Carnegie Mellon University
Monday Seminar Talk
Quick Terminology Recap

Basics




Mercury: distributed publish-subscribe system


Publishers: inject data/events/publications
Subscribers: register interests/subscriptions
Brokers: match subscriptions with publications and deliver to
subscribers
Performs matching and content routing in distributed fashion
Data model
Name = ashwin
Age = 23
X = 192.3
Y = 223.4
Publication
Ashwin Bharambe
Name = *
Age > 35
X > 100
X < 180
Subscription
Carnegie Mellon University
Virtual reality example
(50,250)
(100,200)
Events
x 100
y 200
User
x
x
y
y
≥
≤
≥
≤
50
150
150
250
Interests
Ashwin Bharambe
Arena
(150,150)
Virtual World
Carnegie Mellon University
Mercury goals

Implement distributed publish-subscribe



Support range queries
Avoid hot-spots in the system
Flooding anything is bad


Avoid publication flooding completely
Avoid subscription flooding as much as is possible


Consider queries like SELECT * from RECORDS
Peer-to-peer scenario


No dedicated brokers
Highly dynamic network
Ashwin Bharambe
Carnegie Mellon University
Talk Contents




Mercury Architecture
Overlay construction
Routing guarantees
Overlay properties



How randomness is useful
Load balancing; histogram maintenance
Application Design
Ashwin Bharambe
Carnegie Mellon University
Attribute Hubs
1000
0
150
250
900
age
X - hub
name
x
y
700
450
Hubs in the system


Structure of a single hub
Each attribute range is divided into bins
A node responsible for range of attribute values

Assigned when the node joins; can change dynamically
Ashwin Bharambe
Carnegie Mellon University
Routing
Generating point
y
S
age
S
name
Subscription 
x

Name = *
X > 100
X < 180
Send a subscription to one hub


Which one? Interesting question in itself!
Determine query selectivity – send to “highest selective” hub
Ashwin Bharambe
Carnegie Mellon University
Routing (contd.)
Generating point
x
age
P
P
P
name
y

Publication 
Name = ashwin
Age = 23
We must send publications to all hubs

Ensures matching
Ashwin Bharambe
Carnegie Mellon University
Routing illustrated
Subscription
[240, 320)
[160, 240)
Hx
Rendezvous
[80, 160)
point
Ashwin Bharambe
50 ≤ x ≤ 150
150 ≤ y ≤ 250
[0, 105)
[0, 80)
Publication
x 100
y 200
Hy
[105, 210)
[210, 320)
Carnegie Mellon University
Hub structure and routing (~Symphony)


Naïve routing along the circle scales linearly
Utilize the small-world phenomenon [Kleinberg 2000]



Know thy neighbors and one random person; and you can
contact anybody quickly
Routing policy: choose the link which gets you closest to destn
Performance

Average hop length = O(log2 (n)/k) with k “random” links
Choose this link with probability:
P(x) = 1/(x ln n)
x
Need to be careful when node ranges are not uniform
Ashwin Bharambe
Carnegie Mellon University
Caching

O(log2 (n)) is good, but each hop is still an application
level hop




Latency can be quite large if overlay non-optimized
For distributed applications like games, this is way off from
optimal
Exploit locality in the access patterns of an application
In addition to k “random” links, have cached links

Store nodes which were the rendezvous points for recent
publications
Ashwin Bharambe
Carnegie Mellon University
Performance (Uniform workload)
#long links = 6
#cache links = log(n)
Publications were generated from a uniform distribution
Ashwin Bharambe
Carnegie Mellon University
Performance (Skewed workload)
#long links = 6
#cache links = log(n)
Publications were generated from a high skew Zipf distribution
Ashwin Bharambe
Carnegie Mellon University
Performance (Memory reference
trace)
#long links = 6
#cache links = log(n)
Publications were generated from memory references of SPEC2000 benchmark
Ashwin Bharambe
Carnegie Mellon University
Two Problems
1. Load Balancing

Pr(X=x)

Concern because publication values need not follow a uniform,
or a priori known, distribution
Node ranges are assigned when the nodes join
x
Ashwin Bharambe
Carnegie Mellon University
Problems (contd.)
2. Hub Selectivity



Recall: subscription is sent to one “randomly” chosen hub!
Ideally, it should be sent to the “highest selective” hub
Need to estimate selectivity of a subscription
Name = *
X > 100
X < 180
Sending to Name hub vs. X hub
Ashwin Bharambe
Carnegie Mellon University
Hail randomness

Randomized construction of the network gives
additional benefits!



Uniform sampling non-trivial


Node ranges are not uniform across nodes
Random walks: efficient way of sampling


Turns out, this network is an Expander with high probability
Random walks mix rapidly – i.e., they approach the stationary
distribution rapidly
No explicit hierarchy required (as in RANSUB [USITS ’03])
In general, several statistics about a very dynamic
network can be efficiently maintained
Ashwin Bharambe
Carnegie Mellon University
Hub Selectivity (ideas)


Use sampling to build approximate histograms
Approach 1: (Push)




Each “Rendezvous point” selects publications with a certain
probability and sends them off with specific TTL
log2(n) length random walk ensures good mixing
Traffic overhead / #publications
Approach 2: (Pull)



Perform uniform random sampling periodically
Each sample = histogram of sampled node
Question: how to combine histograms?
Ashwin Bharambe
Carnegie Mellon University
Load balancing (ideas)



Sample “average” load in the system
Utilize the histograms to quickly know high/low load
areas
Strategy 1:



A “light” load gracefully leaves the overlay
Re-inserts itself into a “high” load area
Strategy 2:

Use load “diffusion” – “heavy” nodes shed load to neighbors
 Only if the neighbor is “light”
Ashwin Bharambe
Carnegie Mellon University
Distributed Game Design


Current implementation: Distributed version of the
Asteroids game!
Questions:



How is state distributed across the system?
How is consistency handled in the system?
Cheating???
Ashwin Bharambe
Carnegie Mellon University
Conclusion

Distributed publish-subscribe system supporting



Randomized network construction





Range queries
Scalable routing and matching
Provides routing guarantees
Also yields an elegant way of sampling in a distributed system
Exports an API for applications
Implemented; deployed on Emulab
Distributed game using Mercury


Almost done
To be deployed on Planetlab soon
Ashwin Bharambe
Carnegie Mellon University