Transcript Jain ch 6,7 - Duke Computer Science

Workloads
Made-up
Microbenchmark
programs
Live
workload
Data
sets
Benchmark
applications
“Real”
workloads
You are here
monitor
generator
Traces
analysis
© 2003, Carla Ellis
Experimental
environment
prototype
real sys
Synthetic
benchmark
programs
execdriven
sim
Synthetic
traces
tracedriven
sim
Distributions
& other
statistics
stochastic
sim
Monitors
• Jain Ch 7
• A monitor is a tool used to observe system
activity
• Proper use of monitors is key to performance
analysis
• Also useful for other system observation
purposes
© 1998, Geoff Kuenning
Classifications of Monitors
• Hardware vs. software monitors
• Event-driven vs. sampling monitors
• On-line vs. batch monitors
© 1998, Geoff Kuenning
Hardware Vs. Software
Monitors
• Hardware monitors used primarily by
hardware designers
– Requires substantial knowledge of
hardware details
– VLSI limits monitoring possibilities
• Software monitors used (mostly) by everyone
else
© 1998, Geoff Kuenning
Event-Driven Vs. Sampling
Monitors
• Event-driven monitors notice every time a
particular type of event occurs
– Ideal for rare events
– Require low per-invocation overheads
• Sampling monitors check the state of the
system periodically
– Good for frequent events
– Can afford higher overheads
© 1998, Geoff Kuenning
On-Line Vs. Batch Monitors
• On-line monitors can display their information
continuously
– Or, at least, frequently
• Batch monitors save it for later
– Usually using separate analysis procedures
© 1998, Geoff Kuenning
PowerScope
A Tool for Profiling the Energy Usage of Mobile Applications
Jason Flinn and M. Satyanarayanan
Workshop on Mobile Computing
Systems and Applications
(WMCSA) , 1999.
Issues in Monitor Design
•
•
•
•
•
•
Activation mechanism
Buffer issues
Data compression/analysis
Enabling/disabling monitors
Priority issues
Abnormal events monitoring
© 1998, Geoff Kuenning
Activation Mechanism
• When do you collect the data?
– When an interesting event occurs, trap to
data collection routine
– Analyze every step taken by system
– Go to data collection routine when timer
expires
© 1998, Geoff Kuenning
Buffer Issues
• Buffer size
– Big enough to avoid frequent disk writes
– Small enough to make disk writes cheap
• Number of buffers
– At least two, typically
– One to fill up, one to record
• Buffer overflow
– Overwrite old data you haven’t recorded
– Or lose new data you don’t have room for
© 1998, Geoff Kuenning
Data Compression or
Analysis
•
•
•
•
•
Data can be literally compressed
Or can be reduced to a summary form
Both methods save space for holding data
But at the cost of extra overhead in gathering it
Sometimes can use idle time for this
– But might be better spent dumping data to
disk
© 1998, Geoff Kuenning
Enabling/Disabling Monitors
• Most system monitors have some overhead
• So users should be able to turn them off, if
high performance is required
• Not necessary if overhead is truly trivial
• Or if purpose of system is primarily gathering
data
– As is case with many research systems
© 1998, Geoff Kuenning
Priority of Monitor
• How high a priority should the monitor’s
operations have?
• Again, trading off performance impact against
timely and complete data gathering
• Not always a simple question
© 1998, Geoff Kuenning
Monitoring Abnormal Events
• Often, knowing about failures and errors
more important than knowing about normal
operation
• Sometimes requires special attention
– System may not be operating very well at
the time of the failure
© 1998, Geoff Kuenning
Monitoring
Distributed Systems
• Monitoring a distributed system is not
dissimilar to designing a distributed system
• Must deal with
– Distributed state
– Unsynchronized clocks
– Partial failures
© 1998, Geoff Kuenning
Viewing a Distributed Monitor In
Layers
Management
Console
Interpretatio
n
Presentation
Analysis
Collection
Observation
© 1998, Geoff Kuenning
Make system changes, as necessary
Control the overall system
Decide what the results mean
Present your results
Analyze what you’ve stored
Store what you’ve seen for later
Watch what happens
The Observation Layer
• Layer that actually gathers the data
• Implicit spying - watching what other sites do
without disturbing the activity
• Explicit instrumentation - inserting code to
monitor activities
• Probing - making feeler requests into system
to discover what’s happening
© 1998, Geoff Kuenning
The Collection Layer
• Data can be collected at one or several points in
the distributed system
• How does the data get from observer to
collector (if not co-located)?
– Advertising - observers send it out, collectors
listen and grab it
– Soliciting - collectors ask observers to send it
• Clock issues can be key, here
© 1998, Geoff Kuenning
The Analysis Layer
• In distributed system, may be more feasible
to analyze on the fly
• Can sometimes dedicate one (or more)
machines to analysis
• Often requires gathering all data to one point,
though
© 1998, Geoff Kuenning
Tools and Methods For
Software Measurement
• OK, so how do I actually measure a piece of
software?
• What are the practical tools and methods
available to me?
• How do I get my project done?
© 1998, Geoff Kuenning
Tools For
Software Measurement
•
•
•
•
Code instrumentation
Tracing packages
System-provided metrics and utilities
Profiling
© 1998, Geoff Kuenning
Code Instrumentation
• Adding monitoring code to the system under
study
• Basically, just add the code that does what
you want
© 1998, Geoff Kuenning
Advantages of
Code Instrumentation
+ Usually the most direct way to gather data
+ Complete flexibility of where to insert
monitoring code
+ Strong control over costs of monitoring
+ Resulting measurements always available
© 1998, Geoff Kuenning
Disadvantages of
Instrumenting the Code
– Requires access to the source (or binary
rewriting mechanism)
– Requires strong knowledge of the design and
many details of the code
– Instrumented source requires recompilation
to change monitoring facility
– If overdone, strong potential to affect
performance
© 1998, Geoff Kuenning
Binary Rewriting
© 1997, Romer et al
Tracing Packages
• Allow dynamic monitoring of code that doesn’t
have built-in monitors
• Basically, augment the code to call monitoring
routines when desired
• Akin to debuggers
• Typically allow counters and some forms of
logging
© 1998, Geoff Kuenning
Advantages
of Tracing Packages
+ Allows pretty arbitrary insertion of monitoring
code
+ Doesn’t require recompilation in order to
instrument code
+ Tremendous flexibility at measurement time
+ No instrumentation overhead when you’re not
using it
© 1998, Geoff Kuenning
Disadvantages
of Tracing Packages
– Somewhat higher overheads than building
instrumentation into code
– Really requires access to source, for effective
use
– And requires deep understanding of the
internals of the code
– Only produces data when special package is
used
– Usually specific to particular systems
© 1998, Geoff Kuenning
How Do Tracing Packages
Work?
• Much like debuggers – Attach them to running programs
– Use commands in the tracing packages to
associate data gathering with particular
points in the programs
– Replace normal code at that point in
program with preliminary calls to data
gathering code
© 1998, Geoff Kuenning
Typical Types of
Instrumentation
• Counters
– Cheap and fast
– But low level of detail
• Logs
– More detail
– But more costly
– Require occasional dumping or digesting
• Timers
– To determine elapsed time for operations
– Typically using OS-provided system calls
© 1998, Geoff Kuenning
Counters
• Useful only if number of times an event
occurs is of interest
• Can be used to accumulate totals
• In modern systems, make them wide enough
so they won’t overflow
© 1998, Geoff Kuenning
Counter Examples
• Count number of times a network protocol
transmits packets
• Count number of times programs are
swapped out due to exceeding their time
slices
• Count number of incoming requests to a Web
server
© 1998, Geoff Kuenning
Execution
Characteristics of
Desktop Applications on
Windows NT
Dennis C. Lee, Patrick J.
Crowley, Jean-Loup Baer,
Thomas E. Anderson, and
Brian N. Bershad
ISCA98
Time
• Many OSs provide system calls that start and
stop timers
• Allowing you to time how long things took
• Usually, only elapsed time measurable
– Not necessarily time spent running
particular process
• So care required to capture real meaning of
timings
© 1998, Geoff Kuenning
Timing Tools
• Tools that time the execution of a process
• Often several different times are provided
• E.g., Unix time command provides system
time, user time, and elapsed time
• Various components of the times provided
may depend on other system activities
– So just calling time on a command may
not tell the whole story
© 1998, Geoff Kuenning
Logs
• Can log arbitrarily complex data about an
event
• But more complex data takes more space
• Typically, log data into a reserved buffer
• When full, request for buffer to be written to
disk
– Often want a second buffer to gather data
while awaiting disk write
© 1998, Geoff Kuenning
Designing a Log Entry
• What form should a log entry take?
• Designing for compactness vs. human
readability
– Former better for most purposes
– Latter useful for system debugging
– But make sure no important information is
lost in compacting the log entry
© 1998, Geoff Kuenning
OS Accounting Logs
• Many operating systems maintain logs of
significant events
– Based either on event-driven or sampling
monitors
• Examples:
– logins
– full file systems
– device failures
© 1998, Geoff Kuenning
System Software
Accounting Logs
• Often, non-OS systems programs keep logs
• E.g., mail programs
• Usually only useful for monitoring those
programs
• But sometimes can provide indirect
information
– E.g., a notice of a failure to open a
connection to a name server may indicate
machine failure
© 1998, Geoff Kuenning
Workloads
Made-up
Microbenchmark
programs
Live
workload
Data
sets
Benchmark
applications
“Real”
workloads
monitor
generator
Traces
You are here
© 2003, Carla Ellis
analysis
Experimental
environment
prototype
real sys
Synthetic
benchmark
programs
execdriven
sim
Synthetic
traces
tracedriven
sim
Distributions
& other
statistics
stochastic
sim
Workload
Characterization
• Jain’s topics in Chapter 6
– Terminology
– Techniques
•
•
•
•
•
•
•
Averaging
Specifying Dispersion
Single-Parameter Histograms
Multi-Parameter Histograms
Principal-Component Analysis
Markov Models
Clustering
© 1998, Geoff Kuenning
Workload Characterization
Terminology
• User (maybe nonhuman) requests service
– Also called workload component or
workload unit
• Workload parameters or workload features
model or characterize the workload
© 1998, Geoff Kuenning
Selecting Workload
Components
• Most important is that components be
external: at the interface of the SUT
• Components should be homogeneous
• Should characterize activities of interest to
the study
© 1998, Geoff Kuenning
Choosing
Workload Parameters
• Select parameters that depend only on
workload (not on SUT)
• Prefer controllable parameters
• Omit parameters that have no effect on
system, even if important in real world
© 1998, Geoff Kuenning
Averaging
• Basic character of a parameter is its average
value
• Mean
• Median
• Mode
• All specify center of location of the distribution
of the observations in the sample
© 1998, Geoff Kuenning
Sample Mean
• Take sum of all observations
• Divide by the number of observations
• More affected by outliers than median or
mode
• Mean is a linear property
– Mean of sum is sum of means
– Not true for median and mode
© 1998, Geoff Kuenning
Sample Median
• Sort the observations
– In increasing order
• Take the observation in the middle of the
series
• More resistant to outliers
– But not all points given “equal weight”
© 1998, Geoff Kuenning
Sample Mode
• Plot a histogram of the observations
– Using existing categories
– Or dividing ranges into buckets
• Choose the midpoint of the bucket where the
histogram peaks
– For categorical variables, the most
frequently occurring
• Effectively ignores much of the sample
© 1998, Geoff Kuenning
Characteristics of Mean,
Median, and Mode
• Mean and median always exist and are
unique
• Mode may or may not exist
– If there is a mode, there may be more than
one
• Mean, median and mode may be identical
– Or may all be different
– Or some of them may be the same
© 1998, Geoff Kuenning
Mean, Median, and Mode
Identical
Median
Mean
Mode
pdf
f(x)
x
© 1998, Geoff Kuenning
Median, Mean, and Mode
All Different
pdf
f(x)
Mode
Median
Mean
x
© 1998, Geoff Kuenning
So, Which Should I Use?
• Depends on characteristics of the metric
• If data is categorical, use mode
• If a total of all observations makes sense, use
mean
• If not, and the distribution is skewed, use
median
• Otherwise, use mean
• But think about what you’re choosing
© 1998, Geoff Kuenning
Some Examples
• Most-used resource in system
– Mode
• Interarrival times
– Mean
• Load
– Median
© 1998, Geoff Kuenning
Specifying Dispersion
• Most parameters are non-uniform
• Usually, you need to know how much the rest
of the data set varies from that index of
central tendency
• Specifying variance or standard deviation
brings a major improvement over average
• Average and s.d. (or C.O.V.) together allow
workloads to be grouped into classes
– Still ignores exact distribution
© 1998, Geoff Kuenning
Why Is Variability
Important?
• Consider two Web servers:
– Server A services all requests in 1 second
– Server B services 90% of all requests in .5
seconds
• But 10% in 55 seconds
– Both have mean service times of 1 second
– But which would you prefer to use?
© 1998, Geoff Kuenning
Range
• Minimum and maximum values in data set
• Can be kept track of as data values arrive
• Variability characterized by difference
between minimum and maximum
• Often not useful, due to outliers
• Minimum tends to go to zero
• Maximum tends to increase over time
• Not useful for unbounded variables
© 1998, Geoff Kuenning
Example of Range
• For data set
2, 5.4, -17, 2056, 445, -4.8, 84.3, 92, 27, -10
– Maximum is 2056
– Minimum is -17
– Range is 2073
– While arithmetic mean is 268
© 1998, Geoff Kuenning
Variance (and Its Cousins)
• Sample variance is
1 n
2
s 
  xi  x 
n  1 i 1
2
• Variance is expressed in units of the
measured quantity squared
– Which isn’t always easy to understand
• Standard deviation and the coefficient of
variation are derived from variance
© 1998, Geoff Kuenning
Variance Example
• For data set
2, 5.4, -17, 2056, 445, -4.8, 84.3, 92, 27, -10
• Variance is 413746.6
• You can see the problem with variance:
– Given a mean of 268, what does that
variance indicate?
© 1998, Geoff Kuenning
Standard Deviation
• The square root of the variance
• In the same units as the units of the metric
• So easier to compare to the metric
© 1998, Geoff Kuenning
Standard Deviation Example
• For the sample set we’ve been using,
standard deviation is 643
• Given a mean of 268, clearly the standard
deviation shows a lot of variability from the
mean
© 1998, Geoff Kuenning
Coefficient of Variation
• The ratio of the mean and standard deviation
• Normalizes the units of these quantities into a
ratio or percentage
• Often abbreviated C.O.V.
© 1998, Geoff Kuenning
Coefficient of Variation
Example
• For the sample set we’ve been using,
standard deviation is 643
• The mean of 268
• So the C.O.V. is 643/268
= 2.4
© 1998, Geoff Kuenning
Percentiles
• Specification of how observations fall into
buckets
• E.g., the 5-percentile is the observation that is
at the lower 5% of the set
– While the 95-percentile is the observation
at
the 95% boundary of the set
• Useful even for unbounded variables
© 1998, Geoff Kuenning
Relatives of Percentiles
• Quantiles - fraction between 0 and 1
– Instead of percentage
– Also called fractiles
• Deciles - percentiles at the 10% boundaries
– First is 10-percentile, second is 20-percentile, etc.
• Quartiles - divide data set into four parts
– 25% of sample below first quartile, etc.
– Second quartile is also the median
© 1998, Geoff Kuenning
Single-Parameter
Histograms
• Fit probability distribution to shape of
histogram
• Ignores multiple-parameter correlations
© 1998, Geoff Kuenning
Plotting a Histogram
Suitable if you have a relatively large number of
data points
1. Determine range of observations
2. Divide range into buckets
3. Count number of observations in each bucket
4. Divide by total number of observations and
plot it as column chart
© 1998, Geoff Kuenning
Problem With
Histogram Approach
• Determining cell size
– If too small, too few observations per cell
– If too large, no useful details in plot
• If fewer than five observations in a cell, cell
size is too small
© 1998, Geoff Kuenning
Clustering
• Often useful to break workload into categories
• “Canonical example” of each category can be
used to represent all samples
• If many samples, generating categories is
difficult
• Clustering algorithms can solve this problem
© 1998, Geoff Kuenning
Steps in Clustering
•
•
•
•
•
•
•
•
Select sample
Choose and transform parameters
Drop outliers
Scale observations
Choose distance measure
Do clustering
Use results to adjust parameters, repeat
Choose representative components
© 1998, Geoff Kuenning
Selecting A Sample
• Clustering algorithms are often slow
– Must use subset of all observations
• Can test sample after clustering: can every
observation fit into some cluster?
• Sampling options
– Random
– Heaviest users of component under study
© 1998, Geoff Kuenning
Choosing and Transforming
Parameters
• Goal is to limit complexity of problem
• Concentrate on parameters with high impact,
high variance
– Use principal-component analysis
– Drop a parameter, re-cluster, see if
different
• Consider transformations such as Sec. 15.4
(logarithms, etc.)
© 1998, Geoff Kuenning
Dropping Outliers
• Must get rid of observations that would skew
results
– Need great judgment here
– No firm guidelines
• Drop things that you know are “unusual”
• Keep things that consume major resources
© 1998, Geoff Kuenning
Scale Observations
• Cluster analysis is often sensitive to
parameter ranges, so scaling affects results
• Options:
– Scale to zero mean and unit variance
– Weight based on importance or variance
– Normalize range to [0, 1]
– Normalize 95% of data to [0, 1]
© 1998, Geoff Kuenning
Choosing
a Distance Measure
• Endless possibilities available
• Represent observations as vectors in k-space
• Popular measures include:
– Euclidean distance, weighted or
unweighted
– Chi-squared distance
– Rectangular distance
© 1998, Geoff Kuenning
Clustering Methods
• Many algorithms available
• Computationally expensive (NP to find
optimum)
• Can be simple or hierarchical
• Many require you to specify number of
desired clusters
• Minimum Spanning Tree is only one option
© 1998, Geoff Kuenning
Minimum Spanning Tree
Clustering
• Start with each point in a cluster
• Repeat until single cluster:
– Compute centroid of each cluster
– Compute intercluster distances
– Find smallest distance
– Merge clusters with smallest distance
• Method produces stable results
– But not necessarily optimum
© 1998, Geoff Kuenning
Interpreting Clusters
• Art, not science
• Drop small clusters (if little impact on
performance)
• Try to find meaningful characterizations
• Choose representative components
– Number proportional to cluster size or to
total resource demands
© 1998, Geoff Kuenning
Drawbacks of Clustering
• Clustering is basically an AI problem
• Humans will often see patterns where
computer sees none
• Result is extremely sensitive to:
– Choice of algorithm
– Parameters of algorithm
– Minor variations in points clustered
• Results may not have functional meaning
© 1998, Geoff Kuenning
Reading for Next Time
An Analysis of Internet Content Delivery Systems
Stefan Saroiu, Krishna P. Gummadi, Richard J. Dunn, Steven D.
Gribble, and Henry M. Levy
OSDI 2002
http://www.cs.washington.edu/research/networking/websys/pubs/osdi_2
002/osdi.pdf
© 2003, Carla Ellis
Discussion Next Tuesday:
Destination Initial Hypothesis
Vague idea
“groping around”
experiences
Pre-proposal 1:
Sketch out what information
you would need to collect
(or have already gathered)
in a “groping around” phase
to get from a vague idea
to the hypothesis stage
for your planned project
© 2003, Carla Ellis
Initial
observations
Hypothesis
For Discussion Today
• Survey the types of workloads – especially
the standard benchmarks – used in your
proceedings (10 papers).
© 2003, Carla Ellis