A Storage System Workload Analyzer

Tech Report: CS06-02-00

P. G. Sikalinda, L. Walters and P. S. Kritzinger

Data Network Architectures Group,

Computer Science Department University of Cape Town, Private Bag, Rondebosch 7700, South Africa Email: {psikalin,lwalters,psk@cs.uct.ac.za}

Abstract - The analysis of storage system workloads is important for a number of reasons. It is necessary to understand the usage patterns of secondary storage to enable architects to understand and build a new, or improve upon an existing storage system. It is also important for a storage administrator to understand the workload profile when configuring and tuning a system. Furthermore, the analysis of workloads is necessary to understand the storage requirements and behavior of application software. A different reason for workload analysis, is the need to come up with adequate models for performance evaluation. For the evaluation, based on simulation or otherwise, to be reliable one has to analyze, understand and adequately model the workloads.

In this paper we describe a methodology to go about storage system workload analysis and illustrate it with a general tool we call the Enterprize Storage System Workload Analyzer or ESSWA. Although such analyzes are not new, we believe our proposals have a number of advantages over previous analyzers described in the literature. We experimented with ESSWA by analyzing workloads represented by three sets of publicly available workload traces.

Keywords: Storage System, I/O Trace, Statistics, Simulation, Probability Distribution Functions, Synthetic Workloads.

I. Introduction

This paper is about analyzing storage system workloads recorded in a trace file. Although there are exceptions, storage system workloads are mainly described by the following parameters:

– Logical volume identifier. A logical volume is simply a collection of data which forms a conceptual logical entity such as a file, and which is located on fixed-disk drives, called the physical volumes.

– Logical Block Address (LBA). This is the logical start address of the transfer request. The disk controller has to translate this to a Physical Block Number (PBN) to do the physical transfer.

– Operation type i.e., whether a read or write.

– Request size in terms of the number of bytes transferred.

– A time stamp in the form of a floating point real number which records the time, usually accurate to a microsecond.

In this paper we derived 3 further parameters from the parameters mentioned. These are;

1) Request inter-arrival time, which is the difference between any two consecutive time stamps.

2) Secondly, a parameter we refer to as the logical seek distance which is the difference between any two consecutive start addresses on the same logical volume.

3) Lastly a parameter we call the degree of parallelism defined as the number of I/O requests with the same time stamp.

II. Objectives

Reported in this paper is a general tool that is an improvement on those tools currently available for analyzing enterprize storage system workloads. Although we initially had the ambition of developing a tool which will give one analytical probability distributions for the various parameters mentioned in Section I so as to be able to generate synthetic workloads, we soon realized that this, while technically possible, is practically infeasible as discussed below and as also reported by Ganger [1]. ESSWA is thus a workload analyzer for diagnostic purposes. In other words, given a storage system workload representation in the form of an I/O trace file containing data for the workload parameters, ESSWA will do a thorough statistical analysis of the data.

ESSWA will also automatically suggest the best, but not necessarily good, probability density distribution for the particular parameter values given. The statistics and probability distribution models apply only to the particular workload for which they are produced. This is, as we discovered, because storage system workload characteristics are sensitive to the file system of the particular operating system, the architecture of the storage system and of course the particular application and other storage workload activity at the time of recording the trace, so that the results of a particular analysis is not widely applicable [2].

ESSWA also displays some parameters graphically using empiric cumulative functions and histograms. In summary, ES-SWA is a machine that takes I/O traces as input and produces statistics for workload parameters for diagnostic purposes as illustrated in Figure 1. In order to illustrate the utility of ESSWA, we analyzed storage system workloads represented by three sets of I/O traces, two of which are publicly available

Fig. 1. Context of the ESSWA Enterprize Storage System Workload Analyzer tool

from the Storage Performance Council (SPC)^{1} and the other from the Hewlett Packard I/O trace repository^{2}. Some of the results we obtained are presented and discussed in Section VI.

III. Motivation

A great deal of current research effort is being spent on the understanding and improving both the storage and time efficiency and the reliability of enterprize storage systems (ESSs). In general disk storage subsystems have not kept up the speed with server processor speeds. Processor performance has been increasing at a much higher rate than that of disk drives so that consequently, the I/O subsystem has become a bottleneck in many computer systems.

The situation is made worse with the proliferation of applications which involve large volume of data stored on disks. Such applications include data warehousing, image processing, digital video editing, transaction processing, decision support systems, scientific and engineering simulations, etc.

In the development and management of ESSs, workload analysis is important for mainly two reasons [2]:

– Understanding usage patterns. It is important for the architects to understand the usage patterns when designing and developing a new, or improving upon the design of an existing storage system [5]. Understanding the usage patterns will help in making certain decisions such as scheduling application runs or to suggest a reasonable architecture for a new storage system design.

1http://www.storageperformance.org/home. 2http://tesla.hpl.hp.com/public software.

– Modeling storage system workloads. Part of the work in the development of high performance storage system goes into the performance and correctness analysis of these systems using software tools such as RAIDframe [7] and RAIDsim [8]. For the evaluations, based on simulation or otherwise, to be reliable, one has to analyze, understand and represent the workload as best as possible. Ganger [1] found that the commonly used workload models e.g., the uniform distribution function for starting addresses and the exponential distribution function for inter-arrival time, are seldom representative and can produce dramatically incorrect results. For interarrival times, Hsu et al[2] agrees with Ganger that the exponential probability density function is not always the proper model. Hsu et al as did we, found the lognormal probability density function to be a better model for the inter-arrival times in the workloads they analyzed.

These are not the only reasons for analyzing storage system workloads. The analysis might also be performed to determine the relationship between any two given workloads. Before a decision is taken to pool storage resources to increase the throughput, one may want to establish whether the different workloads involved are correlated or not, and so on.

There are several detailed studies on file system workloads from a variety of environments including database and scientific systems, e.g., [3], [4], [15]. On the other hand, there are very few studies on storage system workloads [5]. Hsu et al [2] pointed out that part of the reason is that storage system workloads are influenced by the file system design and configuration. Therefore the results of any analysis are less widely applicable.

Our findings show that they are two categories of research concerning storage workload analysis.

– The first category involves analyzing storage workload traces with the aim of modeling the workload and discovering some usage patterns.

– The second category involves developing software tools to perform storage workload analysis given some workload traces.

Despite the fact that majority of storage workload analysis and characterization studies use custom built solutions for trace analysis, a number of trace analysis tools have been described in the literature [6]. These tools gather traces, filter, analyze the trace data and provide a facility for data visualization. One of the most comprehensive tools that we came across is called Rubicon [6].

Rubicon was developed by Veitch and Keeton of Hewlett Packard Laboratories for the characterization of I/O workloads. This tool provides a rich set of operations on I/O traces, and was designed to be easily extended through the addition of new analysis functions and reporting methods [6]. The developers of Rubicon identified a number of problems with other workload analysis tools. They noted that these tools need to meet the requirements which they come up with for a generic workload characterization tool. According to these requirements an analysis tool should be:

– a single program,

– configurable,

– extensible,

– able to multiple report formats In our opinion none of the tools reported upon in the literature meet all these requirements.

We therefore pursued the work described here because of the importance of analyzing storage system workloads and the need, in our opinion, for a better tool to do this.

The rest of this paper is organized as follows: The next section discusses related work; Section IV describes the statistical tools and techniques implemented in ESSWA for analyzing storage system workload; Section V describes the tool itself and Section VI presents some of the analysis results we obtained from analyzing three storage system workloads.

IV. Statistical Methodology

In this section, we discuss some of the statistical tools and techniques that ESSWA uses to analyze storage system workloads. The statistical approach we took is similar to that Walters used to analyze and model web traffic [11].

A. Visual Techniques

We used histograms and empirical cumulative distribution functions (ECDF) to visually explore the workload parameter data sets. Histograms are used to identify the shape, location and scale of the distribution of data sets and are useful to determine the presence of symmetry, peakedness, outliers and heavy-tails.^{3} An ECDF, for each potential value x in a given data set, is equal to the probability that observations are less than or equal to x.

B. Statistic measures

In this section we discuss the second way that helps in the understanding of the important features of a data set. This approach involves computing a few “key” numbers which summarize a given data set. The aim is to reduce a large batch of data to just a few numbers which can be grasped simultaneously [10].

1) Five number summary: The five number summary is based on the idea of ranking the quantitative items in a sorted data set. Suppose we have n items in the sorted data set (x_{1}, x_{2}, …, x_{n}). The first number is said to have rank 1, the second smallest rank 2, ..., the largest rank n. The number whose rank m = (n + 1)/2 is called the median and denoted by x_{m}. If n is odd, the median is the middle number. If n is even, then the median is the average of “two middle numbers” in the data set. The number whose rank is l = (⌈m⌉ + 1)/2 is called the lower quartile and the number whose rank is u = n − l + 1 is called the upper quartile. These 5 numbers (minimum, lower quartile, median, upper quartile, maximum) are called the five-number summary and usually written from

3A distribution F (t) is heavy-tailed if its complementary cumulative distribution F^{c}(t) = 1 − F (t) decays slower than exponentially. I.e., e^{γt}F^{c}(t) → ∞ for some γ

smallest to largest as (x_{1}, x_{l}, x_{m}, x_{u}, x_{n}), provide a useful summary of a data set [10].

2) Measures of location: A Measure of Location is a statistic that locates the “middle”, in some sense, of the data set [10]. For example, given a set of I/O request inter-arrival times, we should use the measure of location to answer the question: What is the typical inter-arrival time of I/O requests? The two most important measures of location are the median and the mean.

3) Measures of spread: A Measure of spread is a statistic that gives the extent of variability in the data set. Two measures of spread can be defined from the five-number summary. They are the range R and the inter-quartile range I. The range is unreliable as a measure of spread because it depends only on the smallest and the largest values in the data set, and thus is sensitive to the outlying values, unlike the inter-quartile range. More commonly the sample variance and the sample standard deviation indicate the variation or spread of the data.

4) Sample skewness: This is a measure of symmetry, or more precisely, the lack of symmetry. A distribution, or data set, is symmetric if it looks the same to the left and right of the center point. Sample skewness of a distribution is defined as [12]:

ς = \frac{n}{(n − 1)(n − 2)} ∑_{i=1}^{n}(\frac{x_{i} − x̄}{s})^{3}  (1)

where n > 2 is the number of non-missing values for a variable, x_{i} is the i^{th} value of the variable, x̄ is the sample mean, and s is the sample standard deviation. If ς > 0 we term the distribution to be positively skewed or vise versa [12].

5) Sample kurtosis: Sample kurtosis is a measure of whether the data are peaked or flat relative to a normal distribution. That is, data sets with high kurtosis tend to have a distinct peak near the mean, decline rather rapidly, and have heavy tails. Data sets with low kurtosis tend to have a flat top near the mean rather than a sharp peak.

Sample kurtosis of a distribution is defined as [13]:

κ = \frac{n(n + 1)}{(n − 1)(n − 2)(n − 2)} ∑_{i=1}^{n}(\frac{x_{i} − x̄}{s})^{4} − \frac{3(n − 1)^{2}}{(n − 2)(n − 2)}

(2)

where n > 3.

6) Tail Index: The tail index is a statistic that is used to determine how heavy tailed a distribution is. A heavy tailed distribution is a distribution for which the upper part or “tail” of the distribution declines according to a power rate rather than an exponential rate. Distributions commonly used to model network characteristics such as the exponential and normal distributions have tails which decline exponentially or faster. Heavy tailed distributions have tails that decline slower than these distributions which result in greater degree of variability in size observations. In heavy tailed distributions, the probability of larger observations occurring is relatively high. We say that a random variable χ has a heavy-tailed distribution with tail index α if [11]

P [χ > x] ∼ cx^{−α}, as x → ∞, 0 < α < 2,  (3)

where c > 0 is a constant, and where ∼ means the ratio of the two sides tends to 1 as x → ∞. This distribution has infinite variance, and if α ≤ 1 it has an infinite mean. Smaller values of α imply heavier tails.

7) Correlation Coefficient and Autocorrelation Function: The correlation coefficient is a statistic used to test for independence between any two given data sets. The formula for calculating the correlation coefficient φ from two random variables (x_{1}, y_{1}), (x_{2}, y_{2}), ..., (x_{n}, y_{n}), where the means of the x-values and the y-values are x̄ and ȳ and their standard deviations are s_{x} and s_{y}, respectively, is [12]:

φ = \frac{1}{n − 1} ∑_{i=1}^{n}(\frac{x_{i} − x̄}{s_{x}})(\frac{y_{i} − ȳ}{s_{y}})  (4)

where n is the size of the data set.

The autocorrelation of a random variable is simply the correlation of the process against a time-shifted version of itself. The magnitude of the shift is called the lag. The autocorrelation function is used to test for independence between time instances of a random variable and is defined as [13]:

ρ(m) = \frac{∑_{i=1}^{n−m}(x_{i} − x̄)(x_{i+m} − x̄)}{∑_{i=1}^{n}(x_{i} − x̄)^{2}}, m < n  (5)

where m is the lag and n is the size of the data set.

For many random variables the value ρ(1) is particularly significant. If a random variable is autocorrelated the autocorrelation is often the greatest at a lag of 1. For a data set that is not autocorrelated, |r(1)| < 2/\sqrt{n} at 95% confidence level.

8) Goodness-of-fit statistic: Part of what we did was to fit certain known cumulative distribution functions to the recorded data. A number of goodness-of-fit tests exist to determine how well such analytic distributions fit the data. These include the χ-square test, the Anderson Darling test and the λ^{2} Discrepancy measure.

Pederson and Johnson [16] defined the λ^{2} discrepancy statistic as:

λ̂^{2} = \frac{X^{2} − K − df}{n − 1}  (6)

where n is the sample size and df is defined as N − r − 1, where N is the number of bins in the histogram and r the number of model constants estimated from the data. Assuming that Υ = (Y_{1}, Y_{2}, …, Y_{n}) is a multinomial random variable with p = (p_{1}, p_{2}, …, p_{n}) denoting a probability vector for Υ then [11]

K = ∑_{i=1}^{n} \frac{(Y_{i} − Np_{i})}{Np_{i}}  (7)

and

X^{2} = ∑_{i=1}^{n} \frac{(Y_{i} − Np_{i})^{2}}{Np_{i}}  (8)

The λ^{2} discrepancy measure has a number of advantages over the other goodness-of-fit tests. It can be used when dealing with large data sets whereas other statistics e.g. the Anderson Darling and the χ^{2} statistics, cannot. Another advantage of the λ^{2} statistic is that it can be used to compare the goodness-of-fit tests performed on data sets with different sample sizes. This is not possible with the χ^{2} statistic and the Anderson Darling statistic. The λ^{2} statistic can be used to compare results from tests performed on data sets of different sizes because the sample size and number of bins are taken into account in the calculation of the statistic.

The λ^{2} statistic can take on any real value. Positive values close to zero indicate a better fit while large positive values indicate a lack of fit. Note that the conclusions drawn based on this statistic are not always correct, because this test is not infallible. Therefore further analysis of the data should be done to ascertain the match.

ESSWA, to accomplish this, is able to generate a data set of random values following the best fitting probability distribution function using attribute values, such as the mean value, estimated from the data set being analyzed and then draw the empirical cumulative distribution functions for the two data sets. This allows the user to see how well the probability function, said to be the best fit, matches the real data set.

ESSWA computes the λ^{2} discrepancy statistic for use in finding the probability density function which fits a given data set of inter-arrival times. The probability distribution functions it tests against are the

– normal,

– lognormal,

– exponential,

– gamma,

– beta,

– Weibull,

– Pareto, probability density functions. We only considered these 7 statistical mathematical families because they can model heavy tailed empirical distribution. Recent studies, such as [2], has shown that storage system traffic can be heavy tailed, bursty and, like web server and network traffic, appears to exhibit self-similar characteristics. It is also important to note that these probability density functions are usually used to approximate workload models in that together they represent a wide variety of possible shapes.

Walters [11] implemented a function in the R programming language [14] for calculating the λ^{2} discrepancy statistic in his study which involved finding mathematical models for web traffic parameters. The function uses the method of maximum likelihood estimation to obtain likelihood estimates for probability density function attributes. We incorporated this function in ESSWA.

V. ESSWA, the tool

Our objectives were to develop a storage system workload analyzer that does not only meet the requirements outlined in Section III upon which Rubicon is based, but which is also more user-friendly, and uses a proven and stable statistical environment. A tool that is better than all the tools we encountered in literature. We implemented the functions of ESSWA to perform various analysis tasks in the R-language and environment discussed next.

A. R-language and environment

R is a language and environment for statistical computing and graphics [14]. It is a GNU project and is similar to another language and environment called S, which was developed at Bell Laboratories by John Chambers and colleagues. It compiles and runs on a wide variety of UNIX platforms and similar systems (including FreeBSD and Linux), Windows and MacOS.

R provides a variety of statistical techniques such as linear and nonlinear modeling, classical statistical tests, time-series analysis, classification, clustering, and graphical techniques, and is highly extensible. It has facilities for data manipulation, calculation and graphical display and allows users to easily produce well-designed publication-quality plots, including mathematical symbols and formulae where needed. It is a fully planned and coherent system, rather than an incremental buildup of very specific and inflexible tools, as is frequently the case with other data analysis software. It is also designed around a true computer language and allows users to add functionality by defining new functions. For computationallyintensive tasks, C, C++ and Fortran code can be linked and called at run time. Furthermore, advanced users can write C code to manipulate R objects directly. R can be extended (easily) via packages. There are about eight packages supplied with the R distribution and many more are available through the CRAN family of Internet sites^{4} covering a very wide range of modern statistics. Because of the benefits that the Rlangauge offers, we decided to use it to implement the analysis tasks for ESSWA.

B. ESSWA Design

ESSWA is made up of a back-end statistical analysis engine and a GUI front-end implemented using Visual Basic .NET. A typical GUI screen is shown in Figure 2.

The statistical analysis engine is a collection of functions implemented in R to perform the various analyzes mentioned in the previous sections and called from the GUI to calculate various statistics for the workload parameter data sets. However, to visually display the data sets in form of histograms or cumulative distribution functions, the front-end calls R generic functions directly.

For the interface between R and Visual Basic .NET, we used the Distributed Component Object Model (DCOM) software. DCOM is a standard Windows mechanism used for communication between Windows applications on the same machine or different machines. One application is run as DCOM backend which offers services to the front-end calling application. The services are described in a Type Library and are (more or less) language-independent, making the implementation of the tool very extensible. That is, the calling application can be written in C, C++, Visual Basic, Perl, Python, etc. The

4http://cran.r-project.org/ at the time of writing Fig. 2. Typical ESSWA window; this one to compute cross correlation values

basic R distribution is not a DCOM back-end, so we used some currently available add-ons that interface directly with R or R programs and provide a DCOM back-end. The two packages we used are called DCOMServer and RDCOM and are described in [15].

C. Advantages of ESSWA

ESSWA has a number of advantages over other storage workload analyzers we know. It

– takes advantage of some of the statistical and graphical techniques of R language, which is a free, powerful and proven environment, and

– is driven from a GUI which makes it easy to use.

– Is simple in its design while meeting most of the requirements for a generic analysis tool (see Section III).

– is based on the client/server architecture. This means that the ESSWA front- and back-end can run on separate machines and that more than one front-end can use a single back-end.

– is able to analyze storage system workloads in various trace file formats.

VI. Results

This section discusses some of the results we obtained from the analysis of three different storage system workloads using ESSWA. For some of the workload parameter data sets we present key data statistics and visual displays.

The first storage system workload we analyzed is represented by a trace from SPC. The trace was collected from an Online Transaction Processing (OLTP) system. It contains records of 549,320 I/O requests. The second storage system workload we analyzed consists of 535,233 I/O requests also in the form of a trace from SPC. This trace was collected from a system running a web search engine. The third workload consists of 228,460 I/O requests in the form of a trace from the HP trace repository. The set of traces from which we got this trace was collected from an HP-UX time-sharing server attached to several disk arrays which was instrumented to record all I/O system calls.

We subsequently refer to these workloads as the OLTP, Web and HP workloads respectively.

A. OLTP Inter-arrival Time

The first storage system workload parameter we analyzed is the inter-arrival time. Table I gives the key statistics in microseconds for the OLTP inter-arrival time data set.

Statistic  Value
Sample Size  549320
Minimum  0
Lower Quartile  0
Median  0
Sample Mean  10530
Upper Quartile  13180
Maximum  4017000
Upper Outliers >  79080
Sample Variance  929506412.86
Sample Standard Deviation 30487.81
Coefficient of Variation  2.89
Coefficient of Skew  38.03
Coefficient of Kurtosis  2934.74
Tail index  0.5544

TABLE I

OLTP inter-arrival time statistics

From the table it is clear that the minimum value of the OLTP inter-arrival time data set is 0 microseconds. This implies that there are some I/O requests issued simultaneously i.e., I/O requests issued in parallel. The analysis of the degree of I/O parallelism is discussed separately in Section VI-D. From the table we can see that the median is also 0 microseconds. This means that at least 50% of the inter-arrival times have value zero implying a large number of simultaneous I/O requests as one might expect for a OLTP workload. The mean value is 10,530 microseconds which is much higher that the median. This is because a portion (25%) of inter-arrival values contains relatively large values between 13,180 and 4,017,000 microseconds, thereby increasing the mean.

The coefficient of skew for OLTP inter-arrival times is 38.03. This indicates that the distribution of the data set for inter-arrival times is not symmetric but positively skewed. The coefficient of kurtosis which is 2934.74 indicates that the distribution of inter-arrival times is heavy tailed. This is confirmed by the tail index which is 0.5544 ≫ 0. The fact that the distribution of inter-arrival times is heavy tailed means that the probability of having a relatively long period or idle time between I/O requests is quite high. The peakedness and unsymmetrical characteristics of the distribution of OLTP inter-arrival times can also be seen from a histogram. Figure 3 shows the histogram of OLTP inter-arrival times without outliers. Table II gives the 3 of the possible 7 probability density functions we consider to best fit the OLTP inter-arrival time data set. Among the 3 functions in the table, the first function is the best fit followed by the second and the third is the worst. The table also includes the estimated value(s)

Fig. 3. Histogram of OLTP workload inter-arrival times with outliers removed

for the attribute(s) of each of the three functions and the value of the corresponding λ^{2} discrepancy statistic used to determine how well the match is. Figure 4 contains a plot

Function  λ^{2}  Attributes
Weibull  0.730 γ = 0.2925, α = 5162.0971
Gamma  1.046 shape = 0.2077, rate = 0
Exponential 1.188 β = 18170.2932

TABLE II

The 3 distribution functions matching the OLTP inter-arrival times best

of these three distribution functions respectively on the same graph as the measured cumulative distribution function. The graph confirms that the Weibull probability function is the best fit and in this case (only) it seems reasonable to use this distribution to generate inter-arrival times for a synthetic OLTP-like workload.

B. Web Request Size

The next storage system workload parameter which we analyzed is the I/O request size. Table III presents the key statistics of the Web request sizes. The distribution of Web request sizes is multimodal i.e., there are a number of peaks as is evident from Figure 5. The histogram of this data set contains four peaks at values 8,192; 16,384; 24,576 and 32,768 bytes such that almost all the I/O requests had one of these sizes as shown in Figure 5 and Table IV. The reason for this is not difficult to understand. In operating systems such as UNIX, both read() and write() system calls typically make use of the concept of a Filesystem Block. A Filesystem Block is a unit of data that an operating system typically uses when reading from or writing data to physical devices. It is configurable and

Fig. 4. ECDF’s of OLTP workload inter-arrival times

Statistic  Value
Sample Size  535233
Minimum  512
Lower Quartile  8192
Median  8192
Sample Mean  15420
Upper Quartile  24580
Maximum  1138000
Upper Outliers >  106520
Sample Variance  103512492.07
Sample Standard Deviation 10174.11
Coefficient of Variation  0.66
Coefficient of Skew  5.85
Coefficient of Kurtosis  552.06
Tail index  1.1825

TABLE III

Web request size statistics

most operating systems use a setting of 8192 bytes. Disk reads and writes are typically not multiples of 8192 bytes, and disk space is therefore wasted when only a few bytes are written to a Filesystem Block of 8192 bytes. Therefore, most operating systems allow reads and writes of certain sizes smaller than 8192 bytes, such as 512, 1024, and so on, to be performed in order to conserve disk space. From the evidence in this section, we conclude that I/O request size depend almost entirely on the particulars of the operating system file management system, rather than the requirements of the application.

C. Web logical seek distance

In general I/O traces rarely contain a measure of the physical seek distance required for any access since this information is only available at the disk drive itself. We defined a “logical seek distance” to be the difference between any two consecutive start addresses for any single Logical Volume (LV). Whether this is representative of the physical seek distance is

Fig. 5. Histogram of Web I/O request sizes

Size  Count  Frequency (%)
8192  323209 60
16384 58136  11
24576 47743  9
32768 106119 20

TABLE IV

Frequency table of Web request sizes

arguable, since a single LV is almost certain to be distributed over several physical volumes. Still, we analyzed this parameter as giving some indication of the locality of reference and bearing the aforementioned in mind. Our definition also yields “negative” seek distances which only makes sense in the above mentioned context.

Table V gives the key statistics of the Web logical seek distances measured in blocks for a particular LV ( = 0). The coefficient of skew is zero meaning that the distribution of this data set is symmetric. The distribution of seek distances for all the Web logical volumes is also symmetric. The ratio of the number of positive seek distances to the number of negative seek distances is one. From Figure 6 we note that for each positive logical seek distance there is a corresponding negative logical seek distance of the same magnitude. Such values do not necessarily occur in close succession of the individual I/O requests and at the time of writing we have no explanation for this very interesting phenomenon. An explanation may well be found by determining how the search algorithm(s) employed by the application work(s). The histogram of the data set without outliers is shown in Figure 6.

D. OLTP Degree of Parallelism

Table VI and Table VII, respectively, show the key statistics and the frequency table of the degree of parallelism in the

Statistic  Value
Sample Size  180693
Minimum  -34930000
Lower Quartile  -3449000
Median  64
Sample Mean  311.3
Upper Quartile  3452000
Maximum  34940000
Lower Outliers <  -20711552
Upper Outliers >  20711680
Sample Variance  181047111999023
Sample Standard Deviation 13455374.84
Coefficient of Variation  43224.22
Coefficient of Skew  0
Coefficient of Kurtosis  1.16
Tail index  0.0010

TABLE V

Statistics of the Web logical seek distances for LV 0

Fig. 6. Histogram of Web logical seek distances

OLTP data set. The minimum number of I/O requests issued at the same time in this workload is 1. From Table VII we can see that 55% of the I/O requests occur without any other simultaneous I/O request.

The maximum degree of parallelism in the OLTP data set is 20. Figure 7 shows the distribution of the degree of data parallelism as a histogram. This figure and Table VII show that there are very few values in the parallelism degree data set between 9 and 20. Only 1% of values of parallelism degrees are equal or greater than 9.

E. OLTP, Web, HP operation type

ESSWA reports that the read/write ratios are 1.13, 5048.37 and 0.34 for the OLTP, Web and HP workloads, respectively. In the Web workload almost all the operations are reads (i.e., 99.98% of the total number of operations). This is understandable as a Web search application does not typically

Statistic  Value
Sample Size  273983
Minimum  1
Lower Quartile  1
Median  1
Sample Mean  2.00
Upper Quartile  2
Maximum  20
Upper Outliers >  7
Sample Variance  2.66
Sample Standard Deviation 1.63
Coefficient of Variation  0.81
Coefficient of Skew  2.67
Coefficient of Kurtosis  9.97
Tail index  0.0889

TABLE VI

OLTP parallelism degree statistics

Size frequency (%)
1  55
2  20
3  13
4  5
5  2
6  2
7  1
8  1
>=9 1

TABLE VII

Frequency table for OLTP parallelism degrees

write much data to secondary storage.

F. Auto- and cross-correlation

Parameters which are correlated (see Section IV) cannot be considered in isolation for whatever analysis and certainly not in arriving at an analytic distribution function. Understanding the behavior of the data in this regard is therefore important.

1) Auto-correlation: Table VIII contains the autocorrelation values of all parameters at lag 1, i.e., ρ(1) and the corresponding 95% confidence interval limits, for the OLTP, Web and HP workload parameters. As mentioned in Section IV, the 95% confidence interval limits are −2/\sqrt{n} and +2/\sqrt{n}, where n is the sample size. For a data set that is autocorrelated, |ρ(1)| > 2/\sqrt{n} at 95% confidence level. In all the three workloads, the autocorrelation values for all the parameters are outside the 95% confidence intervals.

Therefore we can say that these parameters are autocorrelated with 95% confidence level. The implication of this is obvious for both adjusting a workload on the basis of one or other parameter. It also implies that although the Weibull distribution provides a good analytic approximation to the inter arrival times in one case (the OLTP data) one needs to consider that parameter is highly correlated with itself.

2) Cross-correlation: We calculated the cross-correlation for only the Web and HP workload parameters. Table IX and Table X therefore show the coefficients of correlation between any two Web and HP workload parameters respectively. Unlike

Fig. 7. Histogram of OLTP parallelism degrees

Parameter  OLTP,  Web,  HP, 95% Confidence
ρ(1)  ρ(1)  ρ(1)  Interval Limits

OLTP:Web:HP

Logical 0.1263 0.0778 - (-0.0027, 0.0027):
Volume  (-0.0027, 0.0027)

Number

Inter-arrival  0.1598 -0.0168 0.1011 (-0.0027, 0.0027):
Times  (-0.0027, 0.0027):

(-0.0091, 0.0091)

Request Size  0.3576 0.0245 0.0730 (-0.0027, 0.0027)

(-0.0027, 0.0027): (-0.0091, 0.0091)

Operation  0.3470 0.3867 0.3664 (-0.0027, 0.0027):
Type  (-0.0027, 0.0027):

(-0.0091, 0.0091)

Logical Seek -0.4507 0.1741  - (-0.0027, 0.0027)
Distance  (-0.0027, 0.0027):
Parallelism 0.0870 - - (-0.0038, 0.0038)

Degree

TABLE VIII

Autocorrelation values for all three data sets

in the case of auto-correlation where one can compute confidence intervals which can be used to determine whether a given parameter is auto-correlated or not, we did not come across a similar notion with cross-correlation. Our conclusions on cross-correlation are based on the premise that the closer the absolute coefficient of correlation for two parameters is to 0 the more independent the two parameters are and vice versa [12]. Based on the foregoing and the values in the tables, we can conclude there are little correlations between the parameters for all these workloads. In the Web workload the correlation between the logical seek distances and the logical volume number is the strongest with 0.2 as the coefficient of correlation.

If the correlations between the workload parameters are so small, then one can in theory use the models for individual

Logical Inter- Request Operation Logical
Parameters Volume arrival Size Type Seek
Number Times  Distance
Logical * 0.02 0.01 0.02 0.20

Volume

Number

Inter- 0.02 * -0.10 0 0.01

arrival

Times

Request 0.01 -0.10 * -0.01 0.07

Size

Operation 0.02 0 -0.01 * 0.01

Type

Logical Seek 0.20 0.01 0.07 0.01 *

Distance

TABLE IX

Coefficients of correlation for Web workload parameters

workload parameters to produce synthetic workloads representative of these workloads.

Inter- Request Operation
Parameters arrival Size Type

Times

Inter- * -0.04 -0.04

arrival Times

Request -0.04 * 0.03

Size

Operation -0.04 0.03 *

Type

TABLE X

Coefficients of correlation for HP workload parameters

VII. Conclusion

As stressed before, the purpose of the work described here was not, in the first instance, to develop analytic workload models of the I/O request parameters, however useful that would be. Rather the intend was to develop a workload diagnostic tool in the first instance.

For the latter purpose we believe ESSWA to be more general, versatile and easy to use both for selecting the input parameters and reporting the statistics than any tool reported in the open literature. For example, from the results we obtained, we are able to tell the fraction of I/O requests serviced by each available logical volume; whether there is I/O parallelism or not; and the read/write ratio in a given workload. If the workload is unbalanced among the available logical volumes, the system administrator might be required to reconfigure the storage system to balance the load to improve performance. The fact that a particular workload exhibits I/O parallelism, as the case with one of the workloads that we analyzed, implies that it would be probably beneficial to implement the I/O rescheduling feature in the underlying storage system to improve performance.

The read/write ratio helps in deciding whether to optimize for both read and write operations or just for one of the two. In one of the workload that we analyzed, the results show that most of the operations are read operations. Therefore, optimizing the storage system handling this kind of a workload for read operations can improve performance. This can be done, for example, by converting part, if not all, of the write cache to read cache.

I/O traces are expensive to record and not many are available to the public for obvious reasons. While we have therefore not analyzed sufficiently many I/O traces to make statements which are generally applicable, the evidence presented here for the traces analyzed confirms that general analytic models of general or even specific I/O request behavior are fraud with difficulties, if not downright impossible. Considering the growing importance of I/O in the performance of computer systems, this is not good news and it would seem that any analytic model would have to be only for a specific application recorded on a specific system. This obviously does not mitigate against applying accurate statistic analysis using a tool which is generally applicable to diagnose specific workloads for the purpose of adjusting the performance of a storage system: ESSWA was written exactly for this purpose as shown here.

References

[1] G. R. Ganger, ”Generating representative synthetic workload: An unsolved problem,” In Int. CMG Conference, pp. 4-8, Nashville, TN, USA, 1995. Computer Measurement Group.

[2] W. Hsu et al, ”Characterization of I/O traffic in personal and server workloads,” IBM Systems Journal, vol 42, no. 2, 2003, pp. 347- 372.

[3] W. Hsu et al, ”Characterization of Production Database Workloads and TPC Benchmarks,” IBM Systems Journal, vol 40, no. 3, 2001, pp. 781-802.

[4] W. Hsu et al, ”I/O Reference Behaviour of Production Database Workloads and TPC Benchmarks-An analysis at the Logical Level,” ACM Transactions on Database Systems, vol 26, 2001, pp. 96-143.

[5] D. Roselli et al, ”A comparison of File System Workloads,” In Proceedings of USENIX Annual Technical Conference, San Diego, CA, 2000, USENIX Association, Berkeley, CA (2000), pp. 93-109.

[6] A. Veitch and K. Keeton, ”The Rubicon workload characterization tool,” SSP technical report HPL-SSP-2003-13, HP Laboratories, March 2003.

[7] W. Courtright II et al, ”RAIDframe: rapid prototyping for disk arrays,” In Proceedings of the 1996 Conference on Measurement and Modelling of Computer Systems (SIGMETRICS), vol 24, 1996, pp. 268-269.

[8] P. Chen et al, ”Maximizing performance in a striped disk array,” In Proceedings of ACM SIGARCH Conference, 1990, pages 322-331, ACM.

[9] C. Ruemmler et al, ”UNIX Disk Access Patterns,” In Proceedings of USENIX Winter Conference, San Diego, CA, 1993, USENIX Association, Berkeley, CA (1993), pp. 405-420.

[10] Les Underhill et al, ”Data Survey”, IntroSTAT, 5th ed., Juta and Co Ltd, pp. 1-44, 1994.

[11] L. O. Walters, ”A Web Browsing Workload Model For Simulation”. Dissertation submitted to the Department of Computer Science, Faculty of Science, University of Cape Town in fulfillment of the requirements for the degree of MSc, May 2004.

[12] F. Daly et al, ”Elements of Statistics”, Addison-Wesley Publishing Company, pp. 1-41, 1995.

[13] R. Kirk, ”Statistics: An Introduction”, Baylor University, 4th ed., 1999.

[14] W. N. Venables et al, ”An Introduction to R”, Notes on R: A programming Environment for Data Analysis and Graphics, Version 2.0.1 (2004-11-15).

[15] R development Core Team, ”Writing R Extensions”, Version 2.0.1 (2004-11-15).

[16] S. Pederson and L. Jones, ”Estimating Model Discrepancy,” Technometrics, vol 32, pp. 305-314, 1990.