Perhaps the simplest of all black-box models is a numeric
average. For example, the fuel efficiency of a car (average
miles per gallon) and a soccer player’s performance (
average goals per game) are both black-box models. Of course,
such models can be easily extended with workload characteristics (e.g., highway or city, home game or away), and an
average can be maintained for each type of workload.
Table 1 shows a simple black-box model of a storage device
(a table of performance averages), and Figure 2 shows the same
information in a regression tree.
3 Both models are indexed using
one workload characteristic (the average request size of the I/O
that is issued to the storage device by the application), and both
models must be trained with sample workloads in order to learn
performance averages for various request sizes. Some form of
interpolation is required when an exact match is not found in
the model. For example, to predict the performance of a workload with 3KB requests, using Table 1, one might average the 2
and 4KB performance and predict 37MB/s. Of course, storage
researchers have explored a number of workload characteristics
in addition to request size, including the read/write ratio, multiprogramming level (queue depth), I/O inter-arrival delay, and
spatial locality. More complex characteristics (e.g., I/O bursti-ness, spatio-temporal correlation) have also been investigated.
More formally, a model of a storage device i (white-box or
black-box) can be expressed as a function F . During train-
ing, the inputs are the workload characteristics Wc of an
application running on device i and the output is a performance metric P (bandwidth, throughput, or latency):
P = F (Wc ).
We refer to Equation 1 as an absolute model, to signify that the
inputs Wc are absolute, and not relative to some other device.
However, in practice, one does not possess Wc , as this would
require running the workload on device i in order to obtain
them. Because running the workload to obtain Wc obvi-
ates the need for predicting the performance of device i, one
instead uses the characteristics Wc obtained from some other
storage device j. That is, the model assumes that the character-
istics of a workload are static and will not differ across storage
devices. More precisely, the model assumes that Wc and Wc
are equivalent. However, this is not always a safe assumption.
table 1: A table-based model that records the performance of a disk
drive for sequentially-read data.
figure 2: A regression tree that learns the performance of a disk
drive for sequentially read data.
2. 1. the challenges with absolute models
The primary challenges with absolute models relate to workload characterization, which has been an open problem for
4 First, one must discover the performance-affecting
characteristics of a workload. This can be challenging given
the heterogeneity of storage devices.
8 For example, a storage
array with a large cache may be less sensitive to the spatial
access pattern than an array with little cache, so models of
the devices would likely focus on different workload characteristics when predicting performance.
Second, one must manage the trade-off between expressiveness and conciseness. Most models expect numbers as
input, and it can be challenging to describe complex workloads with just a few numbers. In effect, workload characterization compresses the I/O stream to just a few distinguishing
features. The challenge is to compress the stream without
losing too much information.
Third, and more fundamentally, an absolute model does
not capture the connection between a workload and the storage device on which it executes. While the assumption of static
workload characteristics (i.e., Wc = Wc ) is safe for open work-
loads, where the workload characteristics are independent
of the I/O service time, it is not safe for closed workloads. The
most obvious change for a closed workload is the I/O arrival
rate: if a storage device completes the I/O faster, then an application is likely to issue I/O faster. And other characteristics can
change, such as the average request size, access pattern, read/
write ratio, and queue depth. Such effects occur when file systems, page caches, and other OS middleware reside between
an application and the storage device. Although the application may issue the same I/O, the characteristics of the I/O as
seen by the storage device could change due to write reordering, aggregation and coalescing, caching, prefetching, and
other interactions between an operating system and a storage
device. For example, a slower device can result in a workload
with larger inter-arrival times and larger write requests (due to
request coalescing) when compared to a faster device.
Collectively, these challenges motivate the work presented in this article. Rather than attempt to solve the difficult problem of identifying workload characteristics that are
expressive, yet concise and static across devices, we choose
to use performance and resource utilization. That is, we use
92 communicAtionS of the Acm | aPril 2009 | Vol. 52 | no. 4