論文 / 著書情報
Article / Book Information
Title

Consideration of disk segmentation and disk sequencingfor efficient useof disk resource on heterogeneous disk environment

AuthorMakoto Kataigi, Dai Kobayashi, Haruo Yokota

Journal/Book name

Proceedings of the Second IEEE International Conference on Digital
Information Management, Vol. , No. , pp. 577-579

Issue date2007, 10DOI

http://dx.doi.org/10.1109/ICDIM.2007.4444286

URL

http://www.ieee.org/index.html

Copyright(c)2007 IEEE. Personal use of this material is permitted. Permission
from IEEE must be obtained for all other users, including
reprinting/republishing this material for advertising or promotional
purposes, creating new collective works for resale or redistribution toservers or lists, or reuse of any copyrighted components of this work inother works.

Note

このファイルは著者（最終）版です。
This file is author (final) version.

Powered by T2R2 (Science Tokyo Research Repository)

Consideration of disk segmentation and disk sequencing
for efficient use of disk resource on heterogeneous disk environment
Makoto KataigiTokyo Institute of Technology
mkataigi@de.cs.titech.ac.jp

Dai Kobayashi
Tokyo Institute of Technology
Japan Society for
the Promotion of Science
daik@de.cs.titech.ac.jp

Abstract
Recently, it is needed to have high performance and use
capacity efficiently at the same time on the heterogeneous
disk environment. But it is difficult to do so because the performance and capacity of each disk are different. We think
to extend AOD method for this aim. This method uses thedifference of access load between primary data and backup
data and balance access load and data amount simultaneously on the homogeneous environment. In this paper,
we consider to maximize usable capacity by the position ofbackup and the disk sequencing. Furthermore, we arrange
the primary data in order to balance the performance basedon its Bandwidth to Space Ratio.

1 Introduction
Recently, the number of large storage systems constructed by many HDDs is increasing because of enlargement of data. Usually, these systems need to have a highperformance and reliability. So, these systems balance access load because average response time of HDD drops off
by load imbalance and data amount of each disk because therecovery methods become inefficient if it is imbalance.
However, the counter-operations are occurred when weuse both methods simultaneously. We proposed Adaptive
Overlapped Declustering (AOD) [7] to solve this problem.
This method leverages the difference of access pattern between primary data and backup data on the environment thatthe systems have backup data. We put primary data to balance access load and backup data on the neighbor (left andright) disks primary is data put on. We balance the dataamount by dividing the backup data to 2 parts on the left
and the right adjacent disks.
On the other hand, the HDDs which are componentsof storage systems have become higher performance andHaruo Yokota
Tokyo Institute of Technologyyokota@cs.titech.ac.jp

larger capacity [5]. But we use old model HDDs or HDDs
limited the performance and capacity at other old HDDs on
a method kind of AOD. So we cannot use the new disk’s
resource efficiently. This is because the existing methods
didn’t care of the heterogeneous disk environment; thesemethods are created for the homogeneous disk environment.
In this paper, we suggest the method that use AOD tobalance both performance and capacity simultaneously inheterogeneous disk environment. There is also a research
to use both performance and capacity efficiently on the environment which Bandwidth to Space Ratio (BSR) of eachdisk is balanced [3]. We adopt the BSR method to AOD for
efficient use of performance.
In this research, we aim to resolve the problem that performance and capacity cannot be used efficiently on the heterogeneous disk environment. There are many kinds of performance such as disk and network throughput, in this research we consider the performance as throughput bottlenecked. Firstly, we allocate backup area to solve capacity
difference. Secondly, we think about disk sequencing to use
capacity efficiently. Finally, we allocate primary area to settle performance difference. We think to segmentalize disk
area to some sub-area such as disk left, right, primary andbackup area. Positioning of real data is future work.
The rest of this paper is organized as follows. We consider the method to make the capacity utilization of the system higher in Section 2, and the method to make the performance utilization ratio of the system higher in Section 3.
Finally in Section 4, we introduce some related work.
The parameters used in this paper are shown in Table1.

2 The efficient use of capacity
In this section, we aim to use capacity efficiently bydisk area segmentation and disk sequencing. Especially,
we think to reduce the capacity of the area which backup
data cannot be put on both left disk and right disk (calledP P
L1 R1
B B

PB

Bad R3 L2

P P
R1BB
Good R3 L2PB

P Backup P
B area B

L2R2L3 Enable R3R1L3R2L1L2PB

R2PB

L 1 R1L2R2R1SameCapacity

PB

R3L3R3L3L3(Gn) L1R2P
B

Table 2. Disk Segmentation Algorithm
Input {Cn } the array of disk capacities
Output {Ln } the array of left area’s capacities
Step1. n = 2, Gk = 0 for all k
Step2. L1 (α) = α (0 ≤ α ≤ C1 )Step3. Ln (α) = Cn−1 − Gn−1 − Ln−1 (α)
Step4. If Ln (0) > Cn , then Gn−1 + = Ln (0) − Cn ,n = n − 1, go to Step3.
Step5. If n < N , then n = n + 1 go to Step3.
Step6. When N is odd, then α = 12 Ln (0)Step7. When N is even
Step7.1 If LN (0) = 0, then GN + = LN (0)Step7.2 α = 12 (C1 − G1 )L1

2.2 Disk sequencing

SameCapacity

Figure 1. The capacity relation
backup-enable area) (Fig 1). Firstly, we segmentalize disk
area to disk left area whose backup data is on the left disk
and right area whose backup data is on the right disk, andadjust the capacity of each left and right area for minimizing
the capacity of backup-enable area. Secondly, in Section 2.1
the disk sequence is settled, but it relates to the capacity ofbackup-enable area, so in Section 2.2 we consider about thedisk sequencing to minimize the capacity of backup-enablearea.

2.1 Disk segmentation
Firstly, we consider the way to minimize the capacity ofthe backup-enable area by the disk segmentation. There is arelation that the capacities between adjacent disks are equal
because the primary data and backup data have to be thesame capacity (Fig 1). Of course, the disk capacities relate
to the disk areas capacities. Therefore, we get the following
formulas (1).
Ln = Rn−1 ,capacity. We also take the border condition that the capacity of the last disk’s right area is same as that of the first
disk’s left area into account. The disk segmentation algorithm is shown as following Table 2.

BorderCalculate Initicondition capacities alize

Table 1. Parameters at Disk nCn
Capacity (Cn = Ln + Rn + Gn )Ln , Rn
Capacity of left and right area
Dn , Gn
Capacity can use and cannot use
BnBandwidthPn
Capacity of primary area
PLn , PRn Primary capacity put on left and right area
N : Disk number in this system
For simplify, we write disk n (> N ) as disk n mod N , anddisk n (≤ 0) as disk (n + αN ) mod N .

Cn = Ln + Rn + Gn

(1)

So we have to minimize the capacity of backup-enable area
to keep the condition satisfied.
To minimize the capacity of backup-enable area, we calculate the capacity of each area by the using formulas (1).
And we create a minimum backup-enable area on the disk
which have the area whose capacity is grater than the disk

The disk sequencing depends on the capacity of backupenable area because there is a relation between the capacities of both neighbor disks. So then we think about how toreduce the capacity of the backup-enable area by disk sequencing.
We can take the disk array whose disk capacity increases
at first, and then decrease as a proper sequencing. And wetake where we insert a new disk to satisfy the proper disk sequencing into account. The disk insertion algorithm shownas following Table3. Of course, we can still use this algorithm when extremely big capacity disk added.
Table 3. New Disk Insertion Algorithm
Input Dnew the capacity of new disk
{Dn } the array of disk capacity
Output position to insert new disk
Step1. From the disk which has minimum capacity,
search the positions which satisfy
Dl ≤ Dnew ≤ Dl+1(call L)
or Dm ≤ Dnew ≤ Dm+1 (call M).
Step2. calculate δc (N )for insertion at both L and M.
Step3. Insert new disk at the position|δc (N )| is small.

3 To have a high performance
In this section, we aim to have a high performance after adjusting of the capacity Ln and Rn . In order to havehigh performance, just considering about the primary area
is enough, because the required performance of backup data

in AOD is zero. So we adjust BSR for primary area (calledBSRp) to achieve as good performance as possible.
There is a relation of primary area’s capacities between
adjacent disks which is shown in the followings formulas(2).
PLn = Rn−1 − PRn−1 ,Pn = PLn + PRn(2)

We calculate the primary area’s capacity of each disk by using these formulas and if the that capacity is grater than thedisk capacity, we have to readjust the primary capacity fromthat disk to other disks while keeping the BSRp balanced.
The algorithm is shown in Table 4.
Table 4. Primary Determination Algorithm
Input {Rn } the array of the right area’s capacity{Bn } the array of the disk bandwidth
Output {Pn } the array of the primary capacity
Step1. n = 1m
Step2. Pm = 12 Dall ∗ BBallfor all m
Step3. we search the minimum δbsr (n, m) forminm ∈ [1..N ] and that is δbsr
, m = minmin
Step4. If δbsr ≥ 0, then go to Step8.
Step5. For m ∈ [n..min],Bm
min
Pm = Pm + |δbsr| ∗ minStep6.

k=n

Bk

For m ∈ [min + 1..n + N ],Bmmin
Pm = Pm − |δbsr| ∗ n+N

k=min+1

Step7.
Step8.
Step9.

Bk

go to Step3.
n=n+1
if n ≤ N , then go to Step2., otherwise end.

4 Related work
Recently, there are many researches focus on having highperformance and using capacity efficiently on the heterogeneous disk environment. For example, in [1, 2, 6] theyapplied extended striping or RAID to use on the heterogeneous disk environment. In these researches, they assumed
BSR of each disk is almost the same. But in our research,
we don’t need this.
In [8], they made BSR of virtual disks become equal bysumming up some disks. In [4], they used the differenceof access pattern. They put the high accessed data on thehigh performance disk and the low accessed data on the low
performance disk. But these methods can not be always
used.
In [3], they focus BSR and defined the data position toreduce the deviation between the BSR of disk and the BSRof data on it. The experiment’s results showed that higher
utilization ratio of both bandwidth and capacity took on theenvironment, which is constructed from disks that have thesame BSR. But, the result is not good on the environment
in which the disks don’t have the same BSR.

5 Summary and future work
In this paper, we thought the method to have high performance and use capacity efficiently on the heterogeneous
disk environment. We used AOD in this environment forthis aim. To use capacity efficiently, we segmented disks toleft and right areas, and we propose the method how to define the ratio of left and right. And we propose the disk
sequencing to minimize the capacity backup data cannot
be putted on. Finally we adjust the allocation of primaryarea to have high performance. Especially, we propose themethod to adjust primary BSR for high performance.
For future work, we are considering to estimate the utilization rate of capacity and performance on the realistic
disk pattern such as when new disks (usually it has larger
capacity than old one) are added. And we are also thinking
about the arrangement and the rearrangement methods ofreal data in such situation that we need to have where to put
or move data when the access pattern is changed or when
new disks are added.

Acknowledgments
This work is partially supported by the JST CREST,MEXT of Japanese Government via Grant-in-Aid for Scientific Research #19024028 and the MEXT 21st Century
COE Program.

References[1] T. Cortes and J. Labarta. A case for heterogeneous disk arrays. IEEE International Conference on Cluster Computing(Cluster’00), page 319, 2000.
[2] T. Cortes and J. Labarta. Extending heterogeneity to RAID
level 5. In Proceedings of the 2001 USENIX Technical Conference, pages 119–132, Boston, 2001. USENIX Association.
[3] A. Dan and D. Sitaram. An online video placement policy based on bandwidth to space ratio (bsr). SIGMOD Rec.,24(2):376–385, 1995.
[4] J.-W. Ding and Y.-M. Huang. Resource-based striping: An
efficient striping strategy for video servers using heterogeneous disk-subsystems. Multimedia Tools and Applications,19(1):29–51, 1 2003.
[5] E. Grochowski and R. F. Hoyt. Future trends in hard diskdrives. In IEEE TRANSACTIONS ON MAGNETICS, volume 32, MAY 1996.
[6] Y. Wang and D. H.-C. Du. Weighted striping in multimedia
servers. In International Conference on Multimedia Computing and Systems, pages 102–109, 1997.
[7] A. Watanabe and H. Yokota. Adaptive overlapped declustering: A highly available data-placement method balancing
access load and space utilization. pages 828–839. 21st International Conference on Data Engineering (ICDE’05), 2005.
[8] R. Zimmermann. Continuous media placement and scheduling in heterogeneous disk storage systems. PhD thesis, 1998.
Adviser-Shahram Ghandeharizadeh.