Transcript Adam`s talk slides - Carnegie Mellon School of Computer Science

OPEN VERSUS CLOSED:
A CAUTIONARY TALE
Bianca Schroeder
Adam Wierman
Mor Harchol-Balter
Computer Science Department
Carnegie Mellon University
To appear at NSDI 2006
Carnegie Mellon University
Computer Science Department
1
THE RESEARCH PROCESS
new system has
smaller response time!
old
standard
system
new
system
new
This comparison
requires testing
the two systems
on realistic workloads
Carnegie Mellon University
Computer Science Department
2
MANY WAYS TO GENERATE REALISTIC WORKLOADS
User driven
Model the behavior
of a typical user then
fork one process for
each user.
User requests web page, receives page,
reads page, clicks on new link
think
send
receive
CLOSED SYSTEM MODEL
server
Carnegie Mellon University
Computer Science Department
3
MANY WAYS TO GENERATE REALISTIC WORKLOADS
Trace driven
1:01.12
1:01.20
1:01.25
1:01.27
1:01.28
1:01.35
1:01.45
ip1
ip2
ip1
ip1
ip3
ip4
ip2
GET
GET
GET
GET
GET
GET
GET
a.gif
b.htm
c.jpg
d.txt
a.htm
d.gif
e.htm
HTTP/1.0
HTTP/1.0
HTTP/1.0
HTTP/1.0
HTTP/1.0
HTTP/1.0
HTTP/1.0
arrival times
service demands
next arrival
time from
trace
:
:
xx
file sizes
from trace
x
new arrivals
OPEN SYSTEM MODEL
Carnegie Mellon University
Computer Science Department
server
4
MANY WAYS TO GENERATE REALISTIC WORKLOADS
Distribution driven
Use distributions of
interarrival times
and service demands
(typically using trace info)
interarrival time dist.
service demand dist.
sample
dist.
xx
sample
dist.
x
new arrivals
OPEN SYSTEM MODEL
Carnegie Mellon University
Computer Science Department
server
5
OPEN MODEL
CLOSED MODEL
Arrivals are independent
of completions
Arrivals are completely
dependent on departures
There is no max number of
simultaneous users
There is a fixed population
of users, called the
Multi-Programming-Level (MPL)
Carnegie Mellon University
Computer Science Department
6
Do you use an open or closed model?
WEB WORKLOAD
GENERATORS
OPEN MODEL
Surge
1. Workload
generators for the
sameSPECWeb
purpose use different
systemTPC-W
models!
Sclient
2. It’s often
not clear which
RUBiS
modelWebBench
workload generators
use! Webjamma
CLOSED MODEL
Carnegie Mellon University
Computer Science Department
7
OUR GOAL TODAY
What is the impact of
the choice of an open or
closed model?
Carnegie Mellon University
Computer Science Department
8
HOW DO WE COMPARE
OPEN AND CLOSED SYSTEMS?
OPEN
CLOSED
Carnegie Mellon University
Computer Science Department
1. Fix the service distribution across
the systems
2. Fix the load across the systems
load depends only
on mean arrival rate and
mean service demands
adjust load
using the
arrival rate
load depends on
MPL, think times, mean of
service demands, variability
of service demands,
scheduling policy, …
adjust load
using the
think time
9
How do open and closed
response times compare?
FCFS scheduling
open  Poisson arrival process
closed  Exponential think times
Carnegie Mellon University
Computer Science Department
10
FCFS scheduling
open  Poisson arrival process
closed  Exponential think times
mean response time
1000
Open
CLOSED << OPEN
100
Closed (MPL=10)
10
0
0.25
0.5
0.75
1
load
Carnegie Mellon University
Computer Science Department
11
FCFS scheduling
open  Poisson arrival process
closed  Exponential think times
mean response time
1000
Open
CLOSED  OPEN
Closed (MPL=1000)
100
Closed (MPL=100)
Closed (MPL=10)
10
0
0.25
0.5
0.75
1
load
Carnegie Mellon University
Computer Science Department
12
CLOSED  OPEN AS MPL GROWS
OPEN MODEL
VS
CLOSED MODEL
As MPL grows arrival rate becomes
independent of completion rate
Carnegie Mellon University
Computer Science Department
13
How quickly does Closed  Open?
mean response time
1500
Open
1000
Web
Workloads
Closed (MPL=1000)
500
Closed (MPL=100)
Closed (MPL=10)
low variability
Carnegie Mellon University
Computer Science Department
high variability
14
SUMMARY SO FAR
high
variability Open >> Closed
low
variability
Carnegie Mellon University
Computer Science Department
It depends
Open > Closed
Open ≈ Closed
Small MPL
Large MPL
15
OUR GOAL TODAY
What is the impact of
the choice of an open or
closed model?
It matters a lot!
1. What is the impact
on the effectiveness
of scheduling?
2. What is the impact
in practice?
Carnegie Mellon University
Computer Science Department
16
SCHEDULING IS A KEY COMPONENT OF SYSTEM DESIGN
WEB SERVERS
Standard design
Processor Sharing (PS)
Improved design
Shortest Remaining
Processing Time (SRPT)
Compare using a workload generator
Does the effectiveness of scheduling
depend on the system model (open vs. closed)?
Carnegie Mellon University
Computer Science Department
17
mean response time
SCHEDULING IN OPEN SYSTEMS
OPEN
PLJF
1000 FCFS
PS
600 SRPT
How do the closed
results compare?
300
0
0
Carnegie Mellon University
Computer Science Department
.25
.5
load
.75
1
18
mean response time
CONTRASTING THE IMPACT OF SCHEDULING
OPEN
CLOSED
PLJF
FCFS
PS
SRPT
PLJF
1000 FCFS
PS
600 SRPT
300
0
0
Why?
Carnegie Mellon University
Computer Science Department
.25
.5
load
.75
1
0
.25
.5
load
.75
1
1. Limited impact of variability in closed system
2. Bounded number of jobs in closed system
3. Dependencies between completions and arrivals
in closed system reduces burstiness
19
OUR GOAL TODAY
What is the impact of
the choice of an open or
closed model?
It matters a lot!
Especially when evaluating
scheduling policies
Carnegie Mellon University
Computer Science Department
What is the impact
in practice?
20
4 CASE STUDIES
OPEN VS CLOSED
IN PRACTICE
Carnegie Mellon University
Computer Science Department
1. Serving static web
content
2. Database backend of
an e-commerce site
3. Auctioning web site
4. Supercomputing center
testbed
implementation
trace-based
simulation
21
Closed
generator
Scheduling
policies
Static web (LAN)
Sclient on
World Cup trace
Modified Sclient
on World Cup
trace
PS, SRPT
E-commerce
Modified TPC-W
TPC-W
PS, PESJF
Trace-based
simulation
Trace-based
simulation
(top 10 auction site
trace)
(top 10 auction site
trace)
PS, SRPT
Case study Open generator
Auctioning
Carnegie Mellon University
Computer Science Department
22
STATIC WEB SERVER
OPEN VS CLOSED
IN PRACTICE
mean response time
OPEN
CLOSED
300
MPL=50
PS
200
100
0
.25
.5
load
SRPT
.75 1 0
.25
.5
load
PS
SRPT
.75 1
Different models give different
conclusion about benefits of SRPT
Carnegie Mellon University
Computer Science Department
23
OPEN
CLOSED
10
MPL=50
8
PS
mean response time
E-COMMERCE SITE
4
PS
PESJF
PESJF
0
20
load
loadMPL=50
PS
14
AUCTION SITE
7
0
0
.25
.5
load
Carnegie Mellon University
Computer Science Department
SRPT
.75 1 0
.25
.5
load
PS
SRPT
.75 1
24
OUR GOAL TODAY
What is the impact of
the choice of an open or
closed model?
It matters a lot in practice!
Especially when evaluating
scheduling policies
How can we identify
whether to use an open
or closed model?
Carnegie Mellon University
Computer Science Department
25
CHOOSING A SYSTEM MODEL
Web workloads
1.
2.
3.
4.
5.
6.
7.
8.
A site being “Slashdotted”
Online gaming site
Science Institute - USGS
Online dept. store
Financial service provider
Kasparov vs Deep Blue
CMU web server
World cup site
Carnegie Mellon University
Computer Science Department
Open or Closed?
26
NEITHER THE OPEN OR CLOSED
MODEL IS COMPLETELY REALISTIC
Carnegie Mellon University
Computer Science Department
27
A MORE REALISTIC ALTERNATIVE
send
think
receive
PARTLY-OPEN MODEL
with probability q
return to the system
xx
new arrivals
x
leave system
server
What parameters affect the load?
Does think time affect the load?
How do think times affect response times?
Carnegie Mellon University
Computer Science Department
28
STATIC WEB SERVER
THE EFFECT OF
THINK TIME
mean response time
300
200
PS
100
SRPT
0
1
10
100
1000
mean think time
Carnegie Mellon University
Computer Science Department
29
A MORE REALISTIC ALTERNATIVE
think
send
receive
PARTLY-OPEN MODEL
with probability q
return to the system
xx
new arrivals
x
leave system
server
Workload generators are only Open/Closed!
OPEN
q0
number of requests per visit ↓
Carnegie Mellon University
Computer Science Department
q1
?
CLOSED
? number of requests per visit ↑
30
STATIC WEB SERVER
THE TRANSITION FROM
OPEN  CLOSED
mean response time
300
200
PS open
CLOSED
OPEN
PS
100
SRPT
0
0
5
10
15
PS closed
20
mean number of requests per visit
Carnegie Mellon University
Computer Science Department
31
mean response time
THE PARTLY-OPEN SYSTEM IN PRACTICE
STATIC WEB
E-COMMERCE SITE
PS
SRPT
200
100
0
0
5
10
15
20
AUCTIONING
9
PS
PESJF 15
6
10
3
5
0
0
0
5
10
15
20
PS
SRPT
0
5
10
15
20
mean number of requests per visit
Carnegie Mellon University
Computer Science Department
32
CHOOSING A SYSTEM MODEL
Web workloads
A site being “Slashdotted” (1.2)
Financial service provider (1.4)
CMU web server (1.8)
Kasparov vs Deep Blue (2.4)
Science Institute USGS (3.6)
Online dept. store (5.4)
World cup site (11.6)
Online gaming site (12.9)
Carnegie Mellon University
Computer Science Department
OPEN
Open or Closed?
Use partly-open system
to decide
CLOSED
33
OUR GOAL
What is the impact of
the choice of an open or
closed model?
It matters a lot in practice!
Especially when evaluating
scheduling policies
How can we identify
whether to use an open
or closed model?
Carnegie Mellon University
Computer Science Department
34
WRAPUP
Carnegie Mellon University
Computer Science Department
35
OPEN AND CLOSED CAN BEHAVE VERY DIFFERENTLY
high Open >> Closed
variability
low
variability
It depends
Open ≈ Closed
Open > Closed
Small MPL
Large MPL
THESE DIFFERENCES ARE IMPORTANT IN PRACTICE
PARTLY-OPEN
OPEN
CLOSED
PS
SRPT
VS
PS
SRPT
Carnegie Mellon University
Computer Science Department
PS
SRPT
36
A CAUTIONARY TALE
Be careful of the underlying
model in workload generators:
open vs. closed has huge practical impact
Web workload generators
need to be flexible
SIMPLE GUIDELINES
When forced to use either open or closed,
the choice can be made using simple heuristics:
model the workload using a partly-open system
IMPACT ON DESIGN
Understanding the appropriate system
model give guidelines about
the effectiveness of scheduling
Carnegie Mellon University
Computer Science Department
37
OPEN VERSUS CLOSED:
A CAUTIONARY TALE
Bianca Schroeder
Adam Wierman
Mor Harchol-Balter
Computer Science Department
Carnegie Mellon University
To appear at NSDI 2006
Carnegie Mellon University
Computer Science Department
38