{'fraction_non_alphanumeric': 0.030070498402918217, 'fraction_numerical': 0.013003458768829499, 'mean_word_length': 4.396776825785394, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 5, 'https://': 0, 'lorem ipsum': 0, 'www.': 1, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Data Allocation in a Heterogeneous Disk Array - HDA with Multiple RAID Levels for Database Applications

We consider the allocation of Virtual Arrays (VAs) in a Heterogeneous Disk Array (HDA). Each VA holds groups of related objects and datasets such as files, relational tables, which has similar performance and availability characteristics. We evaluate single-pass data allocation methods for HDA using a synthetic stream of allocation requests, where each VA is characterized by its RAID level, disk loads and space requirements. The goal is to maximize the number of allocated VAs and maintain high disk bandwidth and capacity utilization, while balancing disk loads. Although only RAID1 (basic mirroring) and RAID5 (rotated parity arrays) are considered in the experimental study, we develop the analysis required to estimate disk loads for other RAID levels. Since VA loads vary significantly over time, the VA allocation is carried out at the peak load period, while ensuring that disk bandwidth is not exceeded at other high load periods. Experimental results with a synthetic stream of allocation requests show that allocation methods minimizing the maximum disk bandwidth and capacity utilization or their variance across all disks yield the maximum number of allocated VAs. HDA saves disk bandwidth, since a single RAID level accommodating the most stringent availability requirements for a small subset of objects would incur an unnecessarily high overhead for updating check blocks or data replicas for all objects. The number of allocated VAs can be increased by adopting the clustered RAID5 paradigm, which exploits the tradeoff between redundancy and bandwidth utilization. Since rebuild can be carried out at the level of individual VAs, prioritizing rebuild of VAs with higher access rates can improve overall performance.


INTRODUCTION
The Redundant Array of Independent Disks (RAID) paradigm [6] ensures high availability as a solution to the high cost of downtime due to disk failures, as quantified in Figure 1.3 in [8]. Replication and erasure coding are the two main methods to deal with disk failures and Latent Sector Errors (LSEs), which result in unreadable disk blocks [24]. RAID level 0 (RAID0) added to the original five level RAID classification implements striping but provides no redundancy [6]. Striping partitions large files into strips allocated in round-robin manner across the disks of the array with the intention of balancing disk loads.
RAID arrays were classified as k-Disk Failure Tolerant (kDFT) in [24]. Maximum Distance Separable (MDS) erasure coding requires k check disks, which is the minimum, to attain kDFT with RAID level (4 + k), k ≥ 1, so that the redundancy level with N disks is k/N [24]. This is much lower than 100k% redundancy ]of k + 1-way replication.
RAID5 which tolerates single disk failures was extended to RAID6 to prevent unsuccessful rebuilds, which eventually lead to data loss, mainly due to LSEs rather than rare disk failures [24]. RAID6 utilizes two check strips per stripe according to Reed-Solomon (RS) coding, or computationally less costly parity coding in the case of EVENODD and RDP [24]. The disk access cost, which is the main consideration in this study, is the same in all three cases. There are also 3DFTs which are MDS [24]. The Mean Time to Data Loss (MTTDL) [6], is a single measure used to quantify RAID resilience to failure, as determined by disk failure rate and the frequency of LSEs, but asymptotic reliability analysis [21] is used in Section 2.3.3. The failures of other components, such as the Disk Array Controllers (DACs) can be masked with internal redundancy such as duplexing, but also coding methods [26].
A RAID level accommodating the most stringent availability requirements for a small subset of datasets would incur an unnecessarily high overhead for updating check blocks or data replicas for all datasets, since as noted below disk bandwidths constitute a bottleneck. We propose Heterogeneous Disk Arrays (HDAs) with DACs that can emulate multiple RAID levels and disks which share data for these levels.
Computer installation rather than procuring multiple disk arrays with different RAID levels, which are inadequately utilized, could consolidate their data in HDAs, with adequate access bandwidth and capacity. Fewer boxes entail a lower purchasing cost, footprint, and power consumption. We are mainly concerned with database applications such as OnLine Transaction Processing (OLTP), which entails random disk accesses, and data mining which entails sequential accesses. This study is not concerned with multimedia applications, such as Video-on-Demand (VoD), with specialized data storage allocation methods and real-time data delivery requirements, where the performance metric is the number of data streams supported.
Virtual Arrays (VAs) with RAID levels best suited for the respective application, are the units of data allocation in HDA. A VA holds a collection of objects, datasets, such as files and relational tables, which has similar performance and availability characteristics. Figure 1 shows the sharing of disk space in an HDA with three RAID levels. In fact only RAID levels RAID1 and RAID5 are considered in this study, but we specify the for-mulas to estimate the load to allocate RAID0, RAID(4 + k) for k > 1, and clustered RAID arrays [24]. With a single failed disk in RAID5 the load on surviving disks is doubled, which may result in overload in an HDA environment. Clustered RAID sets the parity group size over which the parity is computed to a smaller value than the number of disks (G < N), which has the advantage of reduced load increase on surviving disks, i.e., α = (G − 1)/(N − 1)1 < 1.
We assume that data is stored on Hard Disk Drives (HDDs), which is the most popular storage medium for databases and file systems. While disk capacities and transfer rates are increasing rapidly, the disk access time constitutes a bottleneck, e.g., for ten milliseconds the access rate is limited to 100 I/Os per second (IOPs). The improvement in disk access time and hence disk bandwidth (accesses per second) is quite limited for randomly placed disk blocks, which is typical for OLTP. This is due to slow improvements in mechanical aspects of disk access mechanism [10]. The disk transfer rate for sequential data transfers is quite high due to high disk recording densities and increased RPMs (rotations per minute). DRAM and flash memories are more expensive per GB than disks, so that they are utilized as disk caches, rather than HDD replacements. Weaknesses associated with flash memories have led to a bleak outlook according to [7], but Storage Class Memories (SCMs) are expected to eventually replace HDDs due to their lower power consumption and footprint. Non-Volatile Storage (NVS) to hold dirty data is required to prevent data loss as in ordinary RAID arrays via Uninterruptible Power Supply (UPS) [10].
The purchase cost of storage hardware, which constitutes a significant fraction of the cost of computer installations, is exceeded by Total Cost of Ownership (TCO). There is a need for tools to optimize storage bandwidth and capacity utilization, while providing satisfactory performance. Several studies discussed in Section 5 have addressed the issue of optimal design of storage complexes. This study is more narrow in scope in that it is focused on improved storage utilization by data allocation. Figure 1: HDA with four disks and five VAs with different RAID levels: two RAID1 VAs with 2 disks each, two RAID5 VAs with 3 disks each, and a single disk referred to as RAID0, since it has no redundancy.
The allocation of VAs in a disk array requires their load requirements. This load can be obtained with various tools, such as IBM's Resource Measurement Facility (RMF), 1 and Systems 1 http://www-03.ibm.com/systems/z/os/zos/features/rmf/. Management Facility (SMF) allows a breakdown by workload, e.g., OLTP versus batch. 2 It is difficult to specify VA loads without access to such data, so that the alternate method of generating a synthetic stream of allocation requests for VAs is used in this study to compare the effectiveness of data allocation methods for HDA. Each VA allocation request has a given RAID level, size, and its load in periods of high activity is known, A VAs heavily loaded in one period may have a light load in another. We carry out VA allocations based on the load in the heaviest period, while keeping track of disk loads in other periods with heavy load to ensure that disk utilizations are not exceeded in any period.
The primary goal of the allocation study is to maximize the number of allocated VAs, with balancing disk bandwidth and capacity utilization serving as a secondary goal. The former will improve disk response times. VA parameters (load and size) are used to determine their width (W ), which is the number of Virtual Disks (VDs) required to materialize them. The declustering ratio (α) in clustered RAID5 [6,24] is varied in Section 4.5 to take advantage of the tradeoff between disk capacity and bandwidth utilization in degraded mode. This results in an increased number of allocations when the system is disk bandwidth bound.
Optimization methods such as those discussed in [15] cannot be applied directly in this case for three reasons: (1) this is not a straightforward 2-dimensional bin-packing problem, because allocation requests are malleable, e.g., clustered RAID5 provides a tradeoff between VA size and bandwidth or disk utilization requirements (in degraded mode). (2) allocation requests become available and are assigned one at a time and not in batches. The latter would allow optimization methods such as those discussed in [15].
The heuristic allocation method in this study formulates the allocation of VDs of a VA as vector-packing [9], which is equivalent to 2-dimensional bin-packing. Small rectangles representing VD bandwidth and space requirement are allocated into larger rectangles representing disk bandwidth and capacity. Obviously, the smaller the bandwidth and space requirement per VD, the larger the number of allocated VDs.
We consider single pass data allocation methods based on disk bandwidth and two new methods which take into account both bandwidth and capacity requirements. The latter methods are more robust than the former. A novel aspect of this study is that we take into account the load increase due to disk failures. When the number of allocations is constrained by disk bandwidth, rather than disk capacity, we study the effect of adopting the clustered RAID5 paradigm, since it offers a tradeoff between disk bandwidth and disk space requirements.
The paper is organized as follows. Section 2 is concerned with data allocation in HDA. Section 3 on VA allocation in HDA first discusses data allocation in general and then proceeds to discuss data allocation in normal and degraded modes. Section 4 reports experimental results using a synthetic stream of allocation requests. A sensitivity study of the parameters used in the allocation study is reported in Section 4.4. Abbreviations are listed preceding the references. Related work is discussed in the Appendix 5.

DATA ALLOCATION BACKGROUND
Section 2.1 provides the background for data allocation in HDA. Section 2.2 specifies the methods used for allocating VDs. In Section 2.3 we use a simplified analyses of HDA performance and reliability to justify its viability.

Balancing Disk Allocations
We model disks and allocation requests as vectors in two dimensions, where the x-axis is the disk access bandwidth or disk utilization and the y-axis is its capacity [9]. While very high capacity Serial ATA (SATA) disks with lower performance are available for archival storage, we consider higher performance, smaller capacity SCSI disks [4], which are more appropriate for OLTP and database applications.
We simplify the discussion by initially ignoring sequential accesses. A disk is then represented by the Disk Vector D = (X,C), where X denotes the maximum disk bandwidth for accessing small data blocks or equivalently disk utilization in the case of sequential accesses, and C the disk capacity, as shown in  The x-and y-axis represent the disk bandwidth in processing accesses to small randomly placed blocks and disk capacity utilizations.
Data allocation is modeled as vector addition. Taking into account disk space is straightforward. Disk bandwidth requirement is determined by assuming FCFS scheduling, average seek time, which is based on one third of the maximum seek distance for uniform disk accesses, and a mean latency equal to half a disk rotation time, plus the transfer time. This is a pessimistic assumption, since seek distances can be reduced using one of the following methods: (i) Placing frequently accessed VAs centrally, i.e., the organ pipe organization. (ii) Placing VAs accessed together on neighboring tracks, such as Automatic Locality Improving Storage (ALIS) [10]. (iii) Shortest Access Time First (SATF) disk scheduling significantly reduces disk positioning time with respect to FCFS under heavier disk loads [10].
The sum of all allocation vectors should not exceed the disk vector D = (X,C) in Figure 2. Full disk bandwidth and capacity utilization is attained when the end-point of allocation vectors reaches the end point of D. For heterogeneous disk drives D n = (X n ,C n ), 1 ≤ n ≤ N have different values for X n and C n [20]. This will lead to unbalanced disk utilizations and higher disk access times on slower disks, if the same stripe size is to be maintained across disks.
Disk allocation requests are at the level of VDs. The resource requirements of VA i 's VDs are specified as d i = (x i , c i ), where x i is the access rate (to small blocks) and c i is the disk space requirement per VD. With the initialization X r n = X n , C r n = C n , 1 ≤ n ≤ N, as additional VDs are allocated the residual disk bandwidth and capacity is updated as: X r n = X r n − x i and C r n = C r n − c i . A VD allocation at the n th disk is successful if X r n ≥ 0 and C r n ≥ 0, i.e., both constraints are satisfied.
Disk utilization is a more robust metric than disk bandwidth, since the disk may be involved in processing disk accesses with varying sizes, including sequential accesses. Let U x n and U c n denote the current utilization of the bandwidth and capacity of the n th disk in the array They are initialized as U X n = 0, U C n = 0, 1 ≤ n ≤ N and the allocations are taken into account as U x n = U x n + u x i and U c n = U c n + u c i , where u x i and u c i are the utilization of disk access bandwidth and capacity by VA i . Given that J n denotes the set of VD allocations at the n th disk, we should have: The workload is considered disk bandwidth/utilization or capacity bound depending on which limit is reached first.

Allocation Methods Considered in this Study
Five bin-packing methods based on disk bandwidth utilization and two additional methods which also take into account disk capacities are considered for allocating VDs on N disks in this study. It is needless to say that VDs belonging to the same VA need to be allocated on different disks. It is assumed that VA allocations are carried out in a disk array with no failed disks. Allocation on consecutive disks simplifies addressing. Round-Robin Allocate VDs beyond the last stopping point, on consecutive disk drives with wrap-around modulo N. This method equalizes the allocated disk space provided RAID1/0 and RAID5 arrays adopt the same strip size, but does not balance bandwidth or capacity utilizations. Random: Allocate VDs on disk drives randomly, until an unsuccessful allocation is encountered. Further attempts rarely result in a significant number of additional VA allocations, so that this option is not pursued further in this study. This method does not ensure balanced capacity and bandwidth utilizations. Best-Fit: Select the disk with the minimum remaining bandwidth or the maximum disk utilization, which may satisfy this request. First-Fit: Disks are considered in increasing order of their indices, starting with the first disk. A VD is allocated on the first disk that can hold it. Worst-Fit: Allocate requests on disks with minimum bandwidth utilization, provided that both constraints are satisfied.
Given the bandwidth and capacity utilizations for the n th disk U x n and U c n given by Equations (1), two more sophisticated allocation methods minimize the following objective functions: Min-F1: Allocate VDs on disk drives, such that the maximum disk bandwidth utilization or capacity utilization at the disks is minimized. Note that without the latter constraint this is equivalent to Worst-Fit.
Min-F2: Minimize the weighted sum of the variances of disk access bandwidths and capacity utilizations.
Var(.) is the variance computed over all N disks and β ≥ 0 is an emphasis factor for disk capacity utilization.

Analytic Justification for HDA
Different RAID arrays can be implemented separately or by dedicating subsets of the disks to each RAID level, e.g., allocating n < N disks to RAID1 and N − n disks to RAID5 in a single disk array. This approach provides less flexibility than HDA, because the mixture and resource demands for different RAID levels are not known a priori, so that this may result in a situation when one array is underutilized and the other overutilized. There is potential for improving disk access time by sharing disk space, as demonstrated in Section 2.3.1. There is a small reduction in reliability, however, as shown in Section sec:reliability. Calculation of mean response in an HDA with a disk failure is illustrated in Section 2.3.2.
In evaluating HDA performance we postulate an M/M/1 queueing system [13] with Poisson arrivals and exponential service times. Given an arrival rate λ and mean disk service time x d , the mean disk response time is R = x d /(1 − ρ), where ρ = λx d is the disk utilization factor.

Improved Response Time Due to HDA
The arrival rate of read requests to RAID1 and RAID5 arrays is Λ R1 and Λ R5 , respectively. Two disk array configurations are considered with N = 8 disks: C 1 : Vertical Disk Partitioning: n = 2 disks are dedicated to RAID1 and N − n = 6 disks to RAID5. C 2 : Horizontal Disk Partitioning: RAID1 is allocated over N = 8 disks, occupying 2/N or 25% of the space on each disk. The remaining empty space on the N disks is more than adequate to hold the RAID5 array allocated on six disks in C 1 , since the wider RAID5 array allocates less space to parity. 3 The more important mean response time for RAID1 with C 1 is: For C 2 there are two components to disk utilization, since RAID1 and RAID5 disk arrays share disk space: R1 . For N = 8 C 2 will improve the RAID1 response time with respect to C 1 for Λ R1 > Λ R5 /3. 3 The RAID5 data (not parity) blocks are distributed over seven disks, utilizing 5/7 or 72% of disk capacity, which is less than 75% of available space. RAID1 response times in C 2 can be improved by processing its accesses at a higher priority than RAID5 accesses.  [13]. For C 1 with , a 4-fold improvement.

The Effect of Disk Failures on Response Time
We use the HDA configuration in Figure 3 to illustrate the increases in mean disk response times as a result of a single disk failure. All disk requests are reads with mean disk service time x d and an arrival rate to each VA is 2λ, so that the disk utilization per VD is ρ V D = λx d . The utilizations of the eight disks in normal mode are then ρ = 3ρ V D and the mean response times When disk 3 fails then the mean response time at VAs unaffected by this failure remains the same as before. We assume that read requests are routed uniformly to the two VDs of a VA even when the load of the two disks on which they reside are not balanced. Due to the unavailability of E 2 , the load on E 1 will be doubled and hence ρ 2 = 4ρ V D . This increased load affects the mean response time of VAs arrays (A 1 , A 2 ) and (L 1 , L 2 ). Due to the unavailability of B 1 and I 1 the load on B 2 and I 2 will be doubled, so that ρ 4 = 5ρ V D . This increase affects the mean response time for VA (F 1 , F 2 ).
The mean response times at the disk level are which is a small increase in mean disk response time. The mean response times for VAs in degraded mode are:

Asymptotic Reliability Analysis of HDA
We next utilize the asymptotic reliability analysis in [21] to compare the reliability of C 1 and C 2 configurations. The reliabil- In what follows we assume that the disks are highly reliable, so that r = 1 − ε with ε ≪ 1.
It follows that the C 1 configuration is more reliable than C 2 , since it tolerates two disk failures as long as long as they do not affect the same array: RAID1 or RAID5. This reliability analysis is extensible to more complicated cases.

HDA DATA ALLOCATION
This section is organized as follow. In Section 3.1 we specify the characteristics of the VA allocation requests. In Sections 3.2 and 3.3 we provide analytic expressions for system load per VA in normal and degraded modes. The former load estimates are used to obtain the widths of the VAs and the latter to estimate disk bandwidth requirements.

Virtual Allocation Requests
We are concerned with allocating VAs in an HDA with N identical disks. Requests to allocate VAs become available one at a time and are assigned consecutive index numbers. VA allocations are processed in strict First-Come, First-Served (FCFS) order, i.e., VA i+1 is allocated after VA i . Each VA is associated with a certain RAID level, which cannot be reassigned for higher efficiency. A VA allocation fails when not all of its VDs can be allocated due to bandwidth or capacity constraints. The goal is to maximize the number of allocations with balanced disk loads.
The VA load is determined by the arrival rate of disk requests and their mean service time. Disk I/O trace analysis generated by OLTP workloads has shown that disk accesses are to small randomly placed disk blocks. Database applications, such as query processing and data mining, require sequential accesses to large data files. In the following discussion VAs are specified as follows: • The RAID ℓevel of a VA. This is specified a priori as ℓ = 1 for RAID1 and ℓ = 5 for RAID5. • Ratio of RAID1 versus RAID5 arrays. A fraction f 1 of all allocation requests are for RAID1 and a fraction f 5 = 1 − f 1 are for RAID5. These fractions may follow the observed pattern or are based on classification as in [2,25]. We also use the notation RAID5:RAID1=3:1 implying f 5 = 0.75. • VA size. The size V i of VA i is generated according to a RAID level dependent distribution, but as if the data was to be allocated as a RAID0 array (with no redundancy). The effective sizes of VA i , denoted by V ′ i , as determined below, are utilized in the allocation process. The metadata required for HDA is specified in [20], but is not discussed in this study, since space requirements for metadata are considered to be negligible with respect to data size. Given the critical nature of metadata, multiple copies of it need to be stored on disk for the sake of higher reliability, but also cached for the sake of efficiency.
For RAID1 VAs the effective size is V ′ i = 2V i , since the disk space requirement is doubled. For RAID0/5/6/7 VAs which are kDFT arrays with k = 0/1/2/3, the effective size of the VAs is ). The VA width W i is determined based on the size of the VA and its load in normal mode (see Equation (9) in Section 3.2). V ′ i in clustered RAID is discussed in Section 4.5. The same strip size may be adopted in all allocations, which reduces external disk apace fragmentation, while increasing internal disk fragmentation.
• VA loads. Disk accesses to small randomly placed disk blocks incur a disk service time dominated by positioning time. Restricted to such accesses the disk load per VA can be specified by its bandwidth to access small blocks. Disk utilization is a more robust metric which is applicable to accesses to small blocks and large sequential accesses. A certain fraction of disk utilization may be reserved for sequential accesses.
The arrival rate of requests to VA i is Λ i = V i κ ℓ , where κ ℓ is the I/O intensity per GB for RAID level ℓ. The per GB rate for RAID1 is set to be higher than RAID5 (κ 1 > κ 5 ), since RAID1 arrays tend to be used for high performance OLTP applications. These parameters are also varied in the experimental study to emulate I/O-bound, balanced, and capacitybound workloads.
VA loads may vary significantly in different periods. The load in the heaviest period is specified explicitly, but the loads in different periods are taken into account in data allocation, so that they are not exceeded.
• Read:Write Ratio: The fraction of read and write requests to VA i is denoted by f r and f w = 1 − f r , respectively. Read (resp. write) requests to the disks are misses from a read cache (resp. destages from an NVS cache). We ignore the possibility of repeated updates of dirty blocks and the potential locality for destages, so in effect we postulate a worst case scenario.
Disk access time is determined by disk drive characteristics. An analytic method to compute the mean disk service time for random disk accesses with FCFS scheduling in zoned HDDs is reported in [22]. The Shortest Access Time First (SATF) disk scheduling policy currently implemented in most disk drives significantly improve disk access time [10] and results in a lower disk utilization. FCFS scheduling is considered in this study, since it provides the worst case disk utilization.
The average disk transfer rate is considered in this study, since the disk transfer rate varies across disk tracks due to Zoned Bit Recording (ZBR) [10], which maintains approximately the same linear recording density across tracks, so that the mean disk transfer rate is a weighted sum according to track capacities assuming that the track access rate is proportional to track size.
HDA introduces an additional layer in accessing data, since there is a mapping for virtual to physical disk addresses, which are specified by LUNs. This mapping is carried out using the metadata specified in [20], which is in addition to directories specifying the files (tables and indexes) in the case of a relational DBMS. The data is cached so that there is no additional delay.

Estimating VA Widths Based on Load in Normal Mode
Logical read and write requests are processed as Single Read (SR) and Single Write (SW) accesses. The mean service times for SR, SW, and also Read-Modify-Write (RMW) disk accesses are denoted by x SR , x SW , and x RMW , respectively, These are derived in Section 4.2.
The load across the W i VDs of RAID0 is the arrival rate of requests to the array multiplied by the mean disk service time, which is a weighted sum of the two request types (ρ ′ i ). Divided by the number of VDs (W i ) yields the HDD utilization per VD: The width of RAID1/0 VAs is set to W i = 2 in this study, since VA sizes for such arrays are selected to be relatively small. The per VD utilization is the sum of the loads for read and write requests. The read load per VD is also given based on the assumption that read requests are distributed evenly over the two disks.
The cost equations for (k + 1)-way replication are simple extensions of RAID1 costs.
Method C The DAC after receiving d di f f from the data disk computes p di f f , q di f f , and r di f f , which are then sent to appropriate check disks for RAID5/6/7 disk arrays. The difference with Method B is that only an XOR capability is required at the disks, but the disk access time remains the same.

Method D: Disk Architecture for Composite Operations
(DACO) reduce the cost of processing RMW accesses via a specialized read/write head [14], where the write head is placed at a short distance following the read head on a single disk actuator [10] allowing sufficient delay for a just read data block to be XORed with the difference block, before it is overwritten. DACO result in a great improvement in processing RMW requests, since x RMW ≈ x SW , but is not considered further because of difficulties associated with its implementation.
Method A is less susceptible to lost updates, termed write holes, than Method B and C, since the DAC logs its operations to recover from failures, such as power loss. Methods B and C incur the same disk load. Method A substitutes the disk rotation time associated with Methods B and C with an SW request (seek and latency). By issuing of SW requests after SR requests are completed and if there are no intervening disk accesses then an extra seek is not required at check disks, but almost a full disk rotation is incurred, so that the first three methods incur approximately the same cost: The VA width to implement RAID0/5/6/7 arrays is determined by the maximum disk utilization allowed per VD on each disk (ρ max ) and a maximum capacity constraint per VD (v max ), which is expressed as a fraction of all disk capacities. W i is the maximum of these widths, less than N: Limiting the per VD bandwidth utilization to a small fraction of disk bandwidth spreads the load across multiple disks. This also reduces the possibility of disk overload when VA loads are underestimated. Allocating a RAID5 VA across all N disks maximizes parallelism for read accesses and minimizes the space dedicated to check blocks, but has the disadvantage that if a single disk fails then the read load at N − 1 disks is doubled. While for W < N the per VD load increase is higher than the case W = N, fewer disk drives are affected by a disk failure. HDA is effectively a clustered RAID since the VA widths W < N. VA widths are reported in conjunction with allocation studies of clustered RAID in Section 4.5.
Sequential accesses can be handled similarly to accesses to small blocks with the difference that the seek time for sequential requests is negligible compared to transfer time. Latency is reduced due to Zero Latency Read (ZLR) capability, i.e., the reading of a sector can start at any any sector inside the block [10]. The preemptive resume policy is applied to large sequential accesses to ensure an acceptable response time for small accesses. Preemptions incur extra positioning time so preemptions should be allowed at a sufficiently high granularity for efficiency reasons. For the sake of brevity we omit the effect of sequential accesses on disk utilization, which can be handled by estimating the service time for accesses to variable size blocks. The analysis can be extended to accesses spanning strips over several disks. Large sequential updates can be processed efficiently as full-stripe writes, if all the strips in a stripe are updated. Otherwise if the majority of the strips in a stripe are updated, the ReConstruct Write (RCW) method is more appropriate [24].

Load in Degraded Mode
We carry out VA allocations in a manner that HDA disk bandwidths are not exceeded in degraded mode when a single disk fails. One method is to first carry out the allocations in normal mode, but then consider the effect of failures of the disks allocated to a VA one by one, to ensure that no disk affected by the failure is overloaded. Carrying out allocations by this method is costly because of the required backtracking. Assume I VAs are allocated on N disks and the failure of a disk results in overload. Then i allocated VAs should be removed till there is no overload with I − i allocated VAs. A larger I − i can be attainable by moving data around.
The following alternate method was used in this study. We allocate VAs in degraded mode to start with, as if there is a single disk failure. Only single disk failures are considered for kDFT VAs even when k > 1, since concurrent disk failures are rare, a disk failure is dealt with by rebuilt before an additional disk fails, and the additional check blocks are intended to deal with media failures due to LSEs, rather than disk failures [24]. LSEs can be dealt with an intradisk redundancy scheme, which applies the RAID paradigm at the level of disk segments [24].
An HDA with a single disk failure is not expected to operate in degraded mode for lengthy periods of time, since the rebuild can be carried at the level of individual VAs and the rebuild process for highly active VAs can be prioritized to improve overall performance. Rebuild failures can be associated with individual VAs.
The read load on the surviving disk in RAID1 is doubled when one of the two disks fails, while the write load remains the same. Both disks for VA i are allocated with increased loads. We use RAID1/F1 to specify RAID1 arrays with a single failure.
Alternative RAID1 data organizations where the data on each disk is distributed over multiple disks resulting in a more balanced load is described in [23]. Disk utilizations for read and write requests in clustered RAID5 with a single failure (RAID5/F1) and a parity group size G ≤ W are given below following the discussion in [19]. The parity group size is the number of strips, which is protected by a single parity strip in RAID5. Using W = W i to simplify the notation, the arrival rate per disk in VA i is As far as sequential accesses are concerned, in the case of reads a missing strip can be reconstructed if all surviving strips in the stripe or parity group are read. In the case of writes, the writing of the parity strip on a broken disk can be bypassed.

ALLOCATION EXPERIMENTS
This section is organized as follows. Section 4.1 describes the experimental method used to evaluate the data allocation methods considered in this study. Section 4.2 describes the assumptions made in the experimental study. Section 4.3 summarizes the results of the experimental study to compare the allocation methods. Sensitivity of results with respect to parameter settings to determine the width of VAs and the parameter β for the Min-F1 and Min-F2 method are evaluated in Section 4.4. We then assess the effect of clustered RAID5 on the number of allocations in Section 4.5.

Description of the Experiment
Experiments to study the efficiency of VA allocations in HDA is reported in this section. The attributes of VA allocation requests are generated one at a time using pseudo-random numbers sampling from prespecified distributions. Requests are processed in strict FCFS order by different VA allocation policies. We are interested in identifying the policy that maximizes the number of allocated VAs. The runs are repeated multiple times and the average over these runs is reported. The same sequence of pseudorandom numbers is used to generate the same sequence of requests for different allocation policies. This variance reduction technique is used for increased simulation efficiency. 4 In addition to the number HDA disks and their characteristics, the input parameters for the experiment are: (i) The fraction of RAID1 versus RAID5 allocation requests in the input stream. (ii) The size and bandwidth requirements for VAs, where the latter are sampled from different distributions for RAID1 and RAID5. (iii) The fraction of read and write requests. The requests are to small randomly placed disk blocks, so that the disk service time is determined by positioning time.
The experiment to estimate the efficiency of VA allocation methods can be specified as follows.
1. Initialization: I R1 = I R5 = 0 and the VA index i = 1. 2. Determine the RAID level ℓ for VA i according to the fraction of RAID1 (ℓ = 1) versus RAID5 (ℓ = 5) VAs, generate a uniformly distributed random number u ∈ (0, 1). If u ≤ f 1 then VA i is a RAID1 and otherwise it is a RAID5. 3. Generate the size of VA i , which is denoted by V i , based on the size distribution for RAID level ℓ. 4. Compute the access rate to VA i : Λ i = κ ℓ V i , where κ ℓ depends on ℓ and workload category: bandwidth-bound, capacity-bound, or balanced. The load due to sequential accesses is expected to be proportional to V i , and remains the same in normal and degraded mode. 5. For RAID5 allocation requests determine the VA load according to Section 3.2. Use thresholds for maximum disk bandwidth (ρ max ) and capacity (v max ) using Equation (9). Set W i = 2 for RAID1 VAs. 6. Calculate VA loads in degraded mode using the expressions in Section 3.3. 7. Determine if all VDs of VA i can be allocated successfully satisfying disk space and bandwidth constraints, the latter in degraded mode. 5 Ensure that the load in no other high load period is exceeded. If so set I R1&R5 = I R1 + I R5 and stop. 8. Set I Rℓ = I Rℓ + 1 based on the RAID level ℓ of the allocated VA i . Increment the disk bandwidth and capacity utilization or decrement the residual bandwidth and capacity for all allocation periods being considered, set i = i + 1, and return to Step 2.
This experiment can be repeated for normal mode operation using the disk utilizations in Section 3.2 for comparison purposes. Allocation methods are ranked by the number of allocated VAs, which is specified as I R1&R5 = I R1 + I R5 , where I R1 and I R5 are counters for allocated RAID1 and RAID5 VAs.
VA loads may vary significantly over time, so that we have VAs sharing disk space, which reach their peak load in different periods. In this case the algorithm should be carried out using the load in the peak period, but ensuring that the disk load in no other high load period is exceeded.

Assumptions and Parameter Settings
We use the following parameter settings to run experiments. An HDA with N = 12 IBM model 18ES drives is considered. The characteristics of these disk drives, which are extracted from the web site for the Parallel Data Laboratory (PDL) 6 are summarized in Table 1. The relative efficiency of data allocation methods is expected to hold due to the low rate of improvement in disk access times [10]. The size of the nonredundant data stored in each VA is assumed to be exponentially distributed with a mean V 1 = 256 MB for RAID1 and V 5 = 768 MB for RAID5 VAs. The RAID sizes obtained by sampling are rounded up to multiples of 256 KB, which can be placed in strips of this size. As noted earlier space requirements for metadata are ignored in this study.
We set v max = 1/50 of the capacity of all disks and ρ max = 1/20 the bandwidth of each disk. We set β = 1 based on the sensitivity analysis in Section 4.4 for the Min-F1 and Min-F2 allocation methods. The access rate for RAID1 VAs is set to be ten times higher than the rate for RAID5 VAs, i.e., κ 1 = 10κ 5 . While RAID1 arrays are three times smaller on the average, the rate of accesses to RAID1 arrays is set to be 3.3 times higher than RAID5 on the average. We consider three VA workloads with different access rates for RAID5 VAs in normal mode. Bandwidth-Bound: κ 5 = 8.5, Balanced: κ 5 = 3.3, Capacity-Bound: κ 5 = 2.1 accesses/second per GB.
Parameters used in the experimental study are summarized in Table 2

Comparison of Allocation Methods
The number of allocated RAID1 and RAID5 VAs is the key performance metric in evaluating data allocation methods. The number of allocated VAs in the two categories follows the fractions of requests in the input stream, since the allocations are carried out in FCFS order. Tables 3, 4, and 5 are based on 100%, 75%, and 50% read requests in normal mode, while Tables 6, 7, and 8 are based on the same fractions of read requests in degraded mode. The three cases: bandwidth-bound, balanced, and capacity-bound workloads are considered. The same pseudo-random sequence was used in experiments to generate the same synthetic sequence of allocation requests for a fair comparison.
The allocation experiments were repeated one hundred times, so as to obtain the average number of allocated VAs over these iterations. Increasing the number of iterations yielded indistinguishable results, so lengthier experiments are not reported here.
The key metric in the comparison is the number of times an allocation method performed best, i.e., allocated the most VAs. It follows from the tables that there were many ties, with more than one method providing the best allocation. The following conclusions can be drawn from the tables.
1. The number of VAs allocated in normal mode is almost double the number of those in degraded mode for r = 1. This is because the load on surviving disks in degraded mode is approximately double the load in normal mode (for both RAID1 and RAID5 arrays).
2. Min-F1 and Min-F2 are consistently the best methods in terms of the number of allocations in all configurations, although Min-F1 outperforms Min-F2. Both disk bandwidth and capacity need to be considered for robust resource allocation.
3. Worst-Fit and Best-Fit methods provide good allocations for bandwidth-bound workloads in normal and degraded modes. The number of allocations is lower than Min-F1 and Min-F2, however.
4. First-Fit, Random, and Round-Robin are the worst among all allocation methods considered, since they do not optimize bandwidth or capacity allocation.    Table 5: Comparison of the allocation methods with RAID5:RAID1=3:1, and r = 0.5 in normal mode. Table 9, provides the comparison of average bandwidth and capacity utilization for all disks and number of RAID1 and RAID5 VAs allocated with RAID5:RAID1=3:1, r = 1 in degraded mode for Min-F1, Min-F2, and the less efficient Round-Robin allocation methods, for bandwidth-bound workload.
The following observations can be made: Min-F1 and Min-F2 attain high disk bandwidth utilization for bandwidth-bound and balanced workloads, while disk capacity utilizations are low for bandwidth-bound workloads, since the bandwidth bound is reached first. For capacity-bound allocations Min-F1 and Min-F2 minimize the variation of disk utilizations and this results in an increase in the number of VA allocations. Poor allocation methods have high standard deviations for disk bandwidth and capacity utilization.

Sensitivity Analysis
In Section 4.4.1 we study the sensitivity of the number of allocations to β, which is used in conjunction with Min-F1 and Min-F2 allocation methods. In Section 4.4.2 we study the sensitivity of allocation results with respect to the granularity of allocations: ρ max and v max .

Sensitivity to β in Min-F1 and Min-F2
The parameter β emphasizes capacity versus bandwidth utilization for Min-F1 and Min-F2 allocation methods. Higher values of β assign more weight to disk capacity utilization, so that more balanced disk capacity utilizations are achieved.
The following parameters are used in experiments: N = 12 disks, RAID5:RAID1=3:1, the fraction of read requests is r = 1. The VA sizes are exponentially distributed with V 1 = 256 MB     for RAID1 and V 5 = 768 MB for RAID5. The access rates for RAID1 are ten times the access rates of RAID5: (κ 1 = 10κ 5 ). v max is set to 1/50 th of the capacity of all disks and ρ max is set to 1/20 of the bandwidth of a single disk. We consider bandwidthbound, balanced, and capacity-bound workloads.
The following conclusions can be drawn from Table 10. For balanced and capacity-bound workloads the number of VAs allocated increases more than 10% when β is increased from zero to one, but there is little improvement for β > 1. The effect on the bandwidth-bound workload is also less significant. Note that a large value for β would result in the effect of bandwidth utilizations being ignored. We have used β = 1.0 in the experimental results reported in this study.

The Effect of ρ max and v max on Allocations
The parameters ρ max and v max determine the maximum bandwidth (or equivalently maximum disk bandwidth utilization) and the maximum capacity allocated per VD on a disk drive, respectively. ρ max is the more critical parameter, since it restricts the bandwidth utilization of a VA on a disk. Because VA loads are estimates, restricting the load per VD reduces the possibility of a disk becoming overloaded when the VA load was underestimated in the allocation phase. The smaller the values of these two parameters, the more VDs are required for the allocation and vice-versa.
The following parameters are used in the experiment: N = 12, RAID5:RAID1=1:0, i.e., only RAID5 requests, and r = 1, since the load increase in degraded mode is highest for read requests. The VA sizes are exponentially distributed with V 1 = 256 MB for RAID1 and V 2 = 768 MB for RAID5. The allocation method Min-F1 is used in this experiment, because it is one of the two best methods as shown in Section 2 with β set to one. We consider the bandwidth-bound, balanced, and capacity-bound workloads.
The following conclusions can be drawn from Table 11. ρ max affects the number of VDs for both balanced and bandwidthbound workloads, but has no effect on capacity-bound workloads, since the width is determined by v max rather than ρ max . If we consider ρ max = 1/20 and a capacity-bound system, the increase in the number of allocations can be explained by the fact that for v max = 1/25, 1/50, and 1/100 the mean disk capac-   ity utilization was determined to be 96.5%, 98.5%, and 99.2%, respectively, while the standard deviation of capacity utilization was quite small in all cases. The improvement in allocation efficiency is due to the reduction in the sizes of allocation requests. Incidentally, the average RAID5 width was determined to be 4.7, 5.6, 7.3 for ρ max = 1/10, ρ max = 1/20, ρ max = 1/40, respectively.

Clustered RAID5
Clustered RAID5 is a method to attain a reduction in disk load increase when operating in degraded mode. It can be used to attain more allocations for bandwidth-bound workloads when a sufficient disk capacity is available. Given the width of VAs W ≤ N and parity group size G ≤ W , we study the effect of the declustering ratio: α = (G − 1)/(W − 1) on the number of allocated VAs with the clustered RAID5 organization. This experiment could have been carried out with read and write requests, since disk loads for RAID5 with and without clustering are given in [19], but this discussion is simplified by postulating only read accesses, since the increase in disk loads in degraded mode is highest in this case and can be simply expressed as 1 + α. Note that a clustered RAID5 with G = 2 corresponds to RAID1 and one disk access is required to reconstruct a block on the failed disk.
For a disk drive with capacity C with a workload consisting of accesses to randomly placed small data blocks, the Capacity/Bandwidth Ratio (CBR) is given as: γ d = Cx SR . where [x SR ] −1 is the maximum disk bandwidth for SR requests. Bandwidth/Space Ratio (BSR), which is the inverse of CBR, has been defined in the context of storage systems for multimedia applications. The capacity of IBM 18ES disk drives considered in this study is C = 9.17 GB and their maximum bandwidth is 1000/x SR ≈ 87 accesses per second, so that γ d = 9.17/87 = 0.105 (GB/second). This corresponds to the slope of the diagonal in Figure 2. It is desirable for γ c (α) for RAID5 to be close to the disk CBR: γ c (α) ≈ γ d , such that successive allocation vectors follow the diagonal in Figure 2.
The RAID5 access rate per GB with a bandwidth-bound workload is κ 5 = 8.5 accesses per second. The capacity bandwidth ratio for a workload for clustered RAID5 is given in Table 12.       1. If the disk bandwidth is the bottleneck resource then more allocations can be made with smaller values of α, since the bandwidth requirement per VA is lower in degraded mode.
2. As α decreases the system reverts from bandwidth to capacity bound. This is because as G = α(N − 1)+ 1 gets smaller, the disk capacity overhead 1/G gets larger. The number of allocations increases, until the disk capacity becomes the bottleneck resource.
3. If disk capacity is the bottleneck resource then more allocations can be made with larger values of α, because the capacity overhead per VA is lowest for G = N.
Finally, we use the general configuration for all experiments and a bandwidth-bound workload with the Min-F1 method and β = 1. For each allocated VA α is set such that VAs CBR γ c is close to γ d . Once the value of α is determined, the new width will be calculated accordingly. It can be concluded from Table 15 that clustered RAID5 arrays increase the number of VA allocations significantly when all requests are reads (r = 1), but clustering has less effect for higher fractions of write requests.

CONCLUSIONS
We have described HDA, argued about its advantages, and used a synthetic workload to experimentally compare several singlepass data allocation methods for HDA. The allocation efficiency is determined primarily by the number of allocated VAs, disk bandwidth and capacity utilizations, and by the balancedness of allocations.
While only RAID1 and RAID5 are considered in the experimental study, we have provided the methodology for calculating the load for other RAID levels. These analytic results can be used in further studies of HDA.
The two allocation methods: Min-F1 and Min-F2, which take into account both disk access bandwidth and capacity, outperform methods such as Worst-Fit and Best-Fit, which only take into account disk bandwidth. Methods in the latter category outperform methods such as Round-Robin and Random, which do not take into account either disk bandwidth or capacity.
Experimental results that the better data allocation methods result in disks with fully utilized bandwidth, capacity, or both bandwidth and capacity for bandwidth-bound, capacity-bound, and balanced workloads, respectively. More complex data allocation methods would be required to deal with larger allocation requests with respect to disk bandwidth and capacity.
We have investigated the sensitivity of allocations to β, emphasizing disk space utilization, and ρ max and v max , which limit the bandwidth and capacity utilization per VD. The sensitivity to β will be less important if the increase in disk capacities exceeds dataset sizes. Experimental results show that a smaller ρ max results in an increased number of VA allocations for bandwidthbound VAs, which is consistent with the fact that smaller allocations yield a higher bin-packing efficiency.
Clustered RAID5 is a means of decreasing the increased load on surviving disks when disk failures occur. An experimental approach was used to quantify the increase in number of allocations and the optimal value for the declustering ratio (α).
Intermixed bandwidth-and capacity-bound requests can benefit from an adaptive allocation method, which monitors the end point of allocations over time with respect to the disk vector in Figure 2 and applies declustering to bandwidth-bound and data compression to capacity-bound allocation requests.
Methods to reallocate VAs whose load was incorrectly estimated or varied significantly over time are required for system maintenance. The disk cooling algorithm proposed in [17], which balances disk loads by reallocating datasets according to their "heat", i.e., access rate, is relevant to this discussion. Similar capabilities have been developed for storage migration for VMware's virtual machines (vMotion).
Overload control, especially in degraded mode, can be applied to throttle access to VAs for less critical applications to ensure satisfactory performance for more critical ones. There is the more general issue of attaining Quality of Service (QoS) for different applications sharing disk space [5].
An alternate formulation as a bin-packing problem is to start with a fixed number of VAs to be allocated, with the goal to minimize the number of utilized HDAs. Processing allocations in decreasing order of their load will yield improved results.
Rebuild processing is a systematic reconstruction of a failed disk, which is accomplished by reading the contents of surviving disks to reconstruct missing data. Rebuild processing can be carried out using: (1) a spare disk, in the case of HDA an additional VD need be allocated; (2) spare areas as in distributed sparing [18], but this approach does not make sense in the context of HDA, since it would require larger VA sizes; (3) overwriting check strips in the case of restriping, so that a RAID5 would be converted to a RAID0 and a RAID6 to RAID5 [26]; (4) parity sparing by combining same-sized RAID5 arrays [24]. Methods (2) and (3) have the advantage of balancing disk loads and not requiring extra space allocation Simple instances of HDA performance analysis are given in Section 2.3. Performance evaluation of HDA via analysis, simulation, or measurements and benchmarking of a prototype remain an area of further investigation. Benchmarks developed by the Transaction Processing Council (TPC) 8 can be used to determine the viability of HDA by developing a credible prototype. Analytic methods for performance evaluation methods for RAID5 [22] and RAID1 [23] can be extended to HDA operating in normal, degraded, and rebuild modes.