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. ³ 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- i

ing, the inputs are the workload characteristics Wc of an

i

application running on device i and the output is a performance metric P (bandwidth, throughput, or latency):

i

P = F (Wc ). ii i

( 1)

We refer to Equation 1 as an absolute model, to signify that the inputs Wc are absolute, and not relative to some other device.

i

However, in practice, one does not possess Wc , as this would
i
require running the workload on device i in order to obtain
them. Because running the workload to obtain Wc obvi-
i
ates the need for predicting the performance of device i, one
instead uses the characteristics Wc obtained from some other
j
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

ij

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.

Request Size

1 KB 2 KB 4 KB 8 KB

Bandwidth

15 MB/s 27 MB/s 47 MB/s 66 MB/s

figure 2: A regression tree that learns the performance of a disk drive for sequentially read data.

Request size �2KB

No

Yes

Request size �4KB

Request size �1KB

No

Yes

No

Yes

66 MB/s

47 MB/s

27 MB/s

15 MB/s

2. 1. the challenges with absolute models

The primary challenges with absolute models relate to workload characterization, which has been an open problem for decades. ⁴ First, one must discover the performance-affecting characteristics of a workload. This can be challenging given the heterogeneity of storage devices. ⁸ 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- i

j

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