論文 / 著書情報
Article / Book Information
論題(和文)

仕様が異なるディスク混在ストレージの帯域・容量同時有効利用に向けた領域割当とデータ配置の評価

Title(English)

Evaluation of disk segmentation and data location policy for efficientuse of storage capacity and bandwidth on the heterogeneous systems

著者(和文)

片居木誠, 横田治夫

Authors(English)

Makoto KATAIGI, Haruo YOKOTA

掲載誌(和文)データ工学ワークショップ論文集

Citation(English)

Proceedings of Data Engineering Workshop

Vol, no, pages, ,発行日 / Pub. date2008, 3

URL

http://search.ieice.org/

権利情報 / Copyright

本著作物の著作権は電子情報通信学会に帰属します。
Copyright (c) 2008 Institute of Electronics, Information andCommunication Engineers.

Powered by T2R2 (Science Tokyo Research Repository)

DEWS2008 D1-1

仕様が異なるディスク混在ストレージの帯域・容量同時有効利用に向けた領域割当とデータ配置の評価
片居木

誠†

横田

治夫†,††† 東京工業大学 大学院 情報理工学研究科 計算工学専攻 〒 152-8552 東京都目黒区大岡山 2-12-1†† 東京工業大学 学術国際情報センター 〒 152-8552 東京都目黒区大岡山 2-12-1
E-mail: †mkataigi@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
あらまし近年，帯域や容量等の仕様の異なるディスクが混在するストレージシステム構築の要求が増している．しかし，このようなシステムでは，帯域及び容量が不均衡であるため，速度性能を引き出すことが難しい．本稿では，
データに対してプライマリ・バックアップ構造によって冗長性を付与しているシステムにおいて，そのプライマリ・
バックアップ間のアクセス頻度の違いに着目し，均一環境において負荷とデータ量を均衡化させるデータ配置法 AOD
法の混在環境への拡張を行う．AOD 法においてはバックアップはプライマリの隣接ディスクに配置しなければならないという配置関係が存在することから，混在環境において容量割り当てが不可能となる領域を減らし，容量利用率を均衡化させるようにデータを配置するため，隣接ディスクのプライマリ・バックアップ対領域の割り当ての調整を行う．同時に，プライマリ・バックアップ対領域内でのプライマリ・バックアップの役割変更により，混在環境において帯域利用率を均衡化させる．また，本手法をシミュレーションで実装し，同様の目的で用いられる BSR を用いた手法と比較し，BSR を用いた手法と同等の帯域利用率でかつより均衡化した容量利用率であるという結果を得た．
キーワード

ストレージ, 性能評価, データ構造

Evaluation of disk segmentation and data location policy for eﬃcient useof storage capacity and bandwidth on the heterogeneous systems
Makoto KATAIGI† and Haruo YOKOTA†,††† Department of Computer Science, Graduated School of Imformation Science and Engineering,Tokyo Institute of Technology, Ookayama 2-12-1, Meguro-ku, Tokyo, Japan†† Global Scientiﬁc Information & Compting Center, Tokyo Institude of Technology,
Ookayama 2-12-1, Meguro-ku, Tokyo, Japan
E-mail: †mkataigi@de.cs.titech.ac.jp, ††yokota@cs.titech.ac.jp
Abstract Recently, the requirement of building of heterogeneous storage systems, which are constructed by thedisks with various bandwidth and capacity is growing. However it is diﬃcult to eﬃciently use performance on thesesystems because of the imbalance of both bandwidth and capacity. On the other hand, the data location policy
AOD, which uses the diﬀerence of access frequency between primary data and backup data on replication systems,
can balance both access load and data size of each disks. Thus, we aim to extend the AOD method for heterogeneous
storage systems. Since the data location policy of AOD method has to put the backup data to the neighbor diskof disk which primary data locate in, we extend this method to reduce the area, which backup data cannot be put
on and balance the capacity utilization rate by adjusting the location of data. At the same time, we extend thismethod to balance the bandwidth utilization rate by changing the role of primary and backup. We also simulate
the system, and compare with BSR method, which is used for same aim. The result shows that the extended AOD
method is better than the BSR method in terms of the bandwidth utilization rate and capacity utilization rate.
Key words Storage system, Performance evaluation, Data structure—1—1. は じ め に

本稿ではこれらのデータ配置領域決定法によって決定した
データ配置領域を元に，各ディスクへの実際のデータ配置の決

近年のハードディスクの急速な広帯域・大容量化に伴い，様々定を行う．まず，最終的にどのようなデータの配置になれば各な帯域及び容量のディスクが混在するストレージシステム (混ディスクの帯域・容量を有効利用でき，それにより速度性能を引

在環境) 構築への要求が高まっている．Grochowski らの報告にき出せるのかについて考察したのち，そのデータ配置にするた

よると，1990 年から 2000 年において，ハードディスクの帯域めに従来の AOD 法におけるデータ再配置法であるディスク内は年率約 1.25 倍，容量は年率約 2 倍で向上しているという [1]．

データマイグレーション及びディスク間データマイグレーショ

そのためストレージシステムの，ディスク故障によるディスク

ンを混在環境において適用できるように変更を行う．また，本交換や，システム拡張のためのディスク追加において，この新手法をシミュレーションにより実装し，類似手法である BSR をしい広帯域・大容量ディスクを利用したいという要求がある．

利用した手法及び従来の AOD 法と比較しその性能を評価する．

しかし，混在環境においてはこの帯域及び容量の不均一さの本稿の構成を示す．まず 2. 章で帯域と容量の異なるディスク

ため，システムの速度性能を引き出すことが難しいという問が混在するストレージシステムにおいて，帯域と容量を有効利

題点がある．これは，帯域が偏って使用されるため，帯域が足用するための試みとその問題点を示す．その後 3. 章で本手法のりないディスクにおいて速度性能低下を引き起こしたり，容量前提である AOD 法について述べる．続いて 4. 章で本稿の主張が偏って使用されるため，容量利用率の高いディスクにおいてである AOD 法を混在環境に対して適用するための拡張法を述

シーク性能が低下するなどがあるためである．そのため現状でべる．そして，5. 章において本手法を実装したシミュレーショ

は，ディスク交換において旧来の狭帯域・小容量のディスクを使

ンについて述べ，6. 章において BSR を用いた手法と比較した用したり，新しい広帯域・大容量ディスクを使用したとしても，実験結果及びその考察について述べる．最後に 7. 章において本その帯域や容量をシステム内の他のディスクに合わせて制限す

稿のまとめと今後の課題について述べる．

るなどしており，広帯域・大容量を有効に利用できていない．
一方，均一環境においては，各ディスクに対する負荷及び保2. 関 連 研 究

存データ量を均衡化させる手法として Adaptive Overlapped

様々な帯域と容量の混在するシステム構築のための，混在環

Declustering (AOD) 法 [2] がある．AOD 法は，冗長化のため境での帯域と容量の有効利用について，様々な角度から研究さのバックアップデータを保持しており，データへのアクセスはれている．たとえば，Striping や RAID5 環境において帯域とプライマリデータに対して行われるという環境で用いられる．

容量の同時有効利用を目指す研究や，データのアクセス頻度をそのプライマリデータとバックアップデータのアクセス傾向の利用したもの，容量や帯域が混在しているものを仮想的に均一違いに着目し，アクセス対象となるプライマリデータの配置でに見せる方法などがある．特に BSR を用いた手法は我々の提負荷の均衡化，アクセス対象とならないバックアップデータの案手法の対抗手法となるため，詳しく説明する．

配置でデータ量の均衡化を図る手法である．

AdaptRAID0 [5] では Striping 環境において，また Adap-

ここで，我々はこの AOD 法のプライマリデータで負荷を均tRAID5 [6] では RAID5 環境において，各ディスクに配置する

衡化し，バックアップデータでデータ量を均衡化させるというストライプユニットの数を各ディスクの容量に比例させること

点が，混在環境における各ディスクの帯域の差及び容量の差にによって，ディスクの容量利用率の向上を図っている．これら対処するために利用できるのではないかと考えた．具体的には，の手法では，どのディスクも帯域と容量の比率はほぼ一定であ各ディスクの負荷の比を各ディスクの帯域の比と一致させるよ

るとを仮定することにより，どちらか片方，この場合は容量をうに調整し，また各ディスク上のデータ量の比を各ディスクの均衡化させることによって帯域も均衡化するとしている．しか容量の比に一致させるように調整する．これにより各ディスク

し，1. で述べたとおり，混在環境では容量と帯域の比率は一定の帯域・容量がそれぞれ異なる環境でも，それぞれのディスクにはなっていない．また，Weight Striping [7] では，各ディスの帯域・容量を有効利用できるのではないかと考えた．

クにウェイトという値をヒューリスティックに定めて，その値

ここで，我々はまず AOD 法を混在環境へ拡張する上で，無に比例させるようにストライプユニットを配置することにより，駄な領域が出来てしまう問題を解決した．これにはデータ配置

ウェイトの値によって柔軟に帯域・容量のどちらを重視して均の条件を満たしながら帯域・容量の有効利用を可能にするため衡化させるか調整する手法である．しかし，どちらも同時に均のデータ配置領域の決定を行った [3]．これは，プライマリデー

衡化することはできない．どの手法も，データへのアクセス量

タとバックアップデータの配置に制約があるためであり，デー

はサイズに比例すると考えているため，混在環境での帯域と容タの配置によってはバックアップデータを配置できない領域が量の同時均衡化ができない．

出来てしまう可能性があるためである．そのため，バックアッ

この問題点を解決した手法として Resource Based Strip-

プデータを置けない領域を最小化しつつ，各ディスクのプライ

ing [8] がある．この手法では，データ毎のアクセス量の違いをマリ領域に対する帯域対容量比 (Bandwidth toSpace Ratio [4])利用し，各ディスクへのデータの割り当てを，アクセスの多いを均衡化させるデータ配置領域決定法を提案してきた．これは，データは帯域の多いディスクに多く配置し，アクセスの少ない

BSR が均衡化している環境においては，帯域及び容量の有効

データは帯域の少ないディスクに多く配置することにより，シ利用が可能であるという結果が出ているためである．

ステム全体として帯域及び容量の有効利用を図っている．しか

—2—







 


=> <




 

=> !
"$#%'&)(+*-,/.1032

 !
465879#%'&)(-*+,:.10;2   $ %&"(' )
  
 

 !#"    !&"(*)
 
  

 !&"(*(+
  
 

 ?
465879#%'&)(-*+,:.10;2

図 2 AOD のデータ配置
図 1 BSR の一致

そのため，本章ではまず AOD 法 [2] の概略について説明する．
し，この手法においてそれぞれのデータ配置を計算するために

AOD 法は値域分散におけるディスク間での負荷とデータ量

は，システムに保存される全データ及びその各データへのアクを同時に均衡化することが困難であるという問題点を解決す

セス量が事前に分かっていないといけない．しかし，実際にはるための手法である．従来の値域分散を用いたインデックスにそのようなシステムは一般的ではない．

おいては，データの配置が値によって一意に決まってしまうた

また，Striping や RAID5 のようなデータを分割して配置す

め，各ディスクの負荷及びデータ量を同時に均衡化させることる環境だけではなくデータを分割しない環境でも，帯域及び容は非常に難しかった．AOD 法は，冗長化のためにバックアッ

量が混在する環境でその帯域と容量を有効利用する研究がおこプを保持しており，そのバックアップの配置として Chained

なわれている．例えば，Disk Merging [9] では複数のディスク

Declustering を採用している環境において用いられる．まず，をまとめて仮想的に一つのディスクとみなす，または逆に一つプライマリデータの配置で負荷の均衡化，さらにバックアップのディスクを分割して仮想的に複数のディスクにみなす方法でデータをプライマリデータの左右のディスクへ分散させ，そのある．また，そのそれぞれの仮想ディスクに割り当てる帯域及分散割合を調整することによりデータ量の均衡化を行う．またび容量を調整することにより，システム内での仮想ディスクの新しいデータの挿入やアクセス傾向の変化に対して，2 種類の帯域対容量比を一定にすることによって，システム全体での帯

データ再配置により動的に均衡化状態を維持する手法である．

域と容量の有効利用を行っている．しかし，元のディスクの組

なお，各ディスクに論理的な番号が付けてあり，また番号のみ合わせによっては必ずしも仮想ディスクの帯域対容量比を一一つ小さいディスクを左のディスク，番号の一つ大きいディスク

定にすることができるわけではない．

を右のディスクと呼ぶことにする．また，以降本稿では負荷と2. 1 BSR を利用した手法
BSR(Bandwidth to Space Ratio : 帯域対容量比) を基にしは各データを読み出すために使われているディスク帯域を表す．

3. 1 AOD 法におけるデータ配置

たデータ配置決定方法 [4] は，ディスク及びデータの BSR を

AOD 法では，プライマリデータとバックアップデータのア

利用し，各ディスクの BSR とそのディスク上のデータの BSR

クセス頻度の違いを利用する．アクセスされるプライマリデー

が一致するようにデータを配置する (図 1)．これによって，各タの配置によって負荷の均衡化，アクセスされないバックアッ

ディスクの帯域と容量を有効に利用している．

プデータをプライマリデータの左右に分散して配置し，その分さらに，新しいデータの挿入やアクセス傾向の変化に対しては，データの BSR がディスクの BSR より大きいディスク上の散割合を変更させることによってデータ量の均衡化を行い，各ディスクの負荷とデータ量を均衡化させる (図 2)．

データのレプリカを作成し，他のディスク例えばデータの BSR

また，新しいデータの挿入やアクセス傾向の変化が発生したがディスクの BSR より小さいディスクに配置し，各レプリカ

際に，負荷とデータ量の均衡化状態が崩れてしまう．これに対へのアクセス割合を調整することにより，再びディスクの BSR

してデータの動的再配置を用いることによって再均衡化を行う．

とデータの BSR を一致させている．また，レプリカ作成は，シ

ここでは 2 種類のデータ再配置法，負荷を均衡化するためのステム内の各ディスクの状況により動的に行われるため，あらディスク内データマイグレーションと容量を均衡化するためのかじめアクセス傾向を知っている必要はなく，またアクセス傾

ディスク間データマイグレーションを併用し，均衡化を行う．

向が変わった場合にも対応できる．

AOD 法でも BSR を用いた手法と同じく，システム内の各ディ[4] における実験の結果を見ると，各ディスクの BSR が同じ

スクの状況により，動的にデータの再配置が行われるため，あである環境においては良い帯域利用率・容量利用率が得られてらかじめアクセス傾向が分かっている必要はなく，またアクセいる．しかし，各ディスクの BSR が均衡化していない状況，帯ス傾向の変化にも対応できる．

域が最大 20% 違う環境においては結果が芳しくない．しかし

3. 2 ディスク内データマイグレーション

前章で述べたとおり，混在環境を構築する際にはシステム内でディスク内データマイグレーションは隣接ディスク間においのディスク間の帯域の違いは 20% よりはるかに大きくなるたて，プライマリデータとそのバックアップデータのお互いの役

め，この手法による帯域及び容量の有効利用は難しいと考える．

割を入れ替えることによって，負荷を移動させる方法である (図3. Adaptive Overlapped Declustering 法3)．このとき，データの役割を入れ替える操作だけでよいので，
実際のデータの移動を伴うことなく，ディスク間での負荷の移

我々はディスクの容量及び帯域が混在する環境で，容量及び動を行うことができる．AOD 法では，配置条件から，必ずプラ帯域を有効利用するために，AOD 法を拡張することを考える．

イマリデータとバックアップデータは隣接ディスクに保存され

—3—

 

  




 

  

12'23 +4526 7 

図 3 ディスク内データマイグレーション  

!#"%$"'&)(   

 



 


 



8 2'2'23 +4526  7 


 

 

*%
+'"%,%-.( 0/

92'23 +8 2'26 7 

図 5 ディスクの領域分割

4. AOD の混在環境への適用

及び容量を有効利用し，速度性能を引き出す方法を考える．ま図 4 ディスク間データマイグレーション

ず，3. で述べたとおり，AOD 法ではデータ配置において，バッ

本章では AOD 法を混在環境に拡張することによって，帯域クアップデータをプライマリデータの隣接ディスクに配置しなているため，このような役割変更が行える．なお，実際のデーければならないという条件が存在する．AOD 法を混在環境に

タ移動を伴わないため，データ量の移動は起こらない．

適用するためには，この配置の条件を満たさなくてはならな

システム全体としては，隣接するディスク n 及び n + 1 において，ディスク n 上の各データ Data i の負荷 (A(i)) の合計

い．しかし，無計画にデータを配置してしまうと，バックアッ
プデータが配置できない領域ができてしまう．

とディスク n + 1 上の各データ Data j の負荷の合計の差の絶

そのために，配置条件を満たしつつ利用可能容量が最大とな

対値 δband を最小化するようにデータの役割変更を行う．順に

り，プライマリ領域の BSR が均衡化するようなディスクの領域

操作対象となるディスクをずらしていくことにより，漸近的に分割を行う．その後，各ディスクの容量利用率及び帯域利用率

システム全体で負荷を均衡化していく手法である．なお，ディが均衡化するようにデータの配置を行う．また，データ追加や

スク n 上の全データ集合を Data in(n) と定義する．負荷の差

アクセス傾向の変化に対して，データ再配置によって，各ディ

δband は以下のとおりである．

スクの帯域利用率および容量利用率を再均衡化させる．

¯¯
δband (n) = ¯¯XXA(i) −i∈Data in(n)¯¯
A(j)¯¯ (1)j∈Data in(n+1)

4. 1 ディスクの領域分割
我々は [3] において，データ配置条件を満たしつつ，帯域及び容量を有効利用するため，利用可能容量を最大化し，各ディス

3. 3 ディスク間データマイグレーション

クのプライマリ領域の BSR を均衡化させるディスク領域分割

ディスク間データマイグレーションはバックアップデータを手法を提案してきた．この手法は，まず利用可能領域を最大化

プライマリデータに対して反対側の隣接ディスクに移動させるするため，左右どちらのディスクにもバックアップを配置できことにより，データ量を移動させる方法である (図 4)．AOD 法

なくなる領域を最小化させるように，各ディスクのバックアッ

ではバックアップデータはプライマリデータの左右のどちらか

プを左右に振り分けて配置する領域の決定を行った (図 5 中ののディスクに配置すればよく，反対の隣接ディスクへ移動する

縦棒，以降この領域をそれぞれディスク内の左の領域および右ことができる．この方法ではプライマリデータは動かないため，の領域と呼ぶ)．その後，各ディスクの帯域を有効利用するたデータアクセスへの影響は少なく，負荷の移動は起らない．

め，各ディスクにおけるプライマリデータを配置する領域の大システム全体としては，隣接ディスク n 及び n + 1 におい

きさを各ディスクのプライマリ領域の BSR が均衡化するようて，ディスク n 上の各データ Data i のデータ量 (S(i)) の合計に調整した (図 5 中の横棒，以降この領域をそれぞれプライマとディスク n + 1 上の各データ Data j のデータ量の合計の差

リ領域およびバックアップ領域と呼ぶ)．

の絶対値 δcap を最小化するようにデータ移動を行う．順に操

ディスク領域を分割したのち，どのようにデータを配置する

作化象となるディスクをずらしていくことにより，漸近的にシと良いのか考察する．さらに，その配置にするためのデータ再ステム全体でデータ量を均衡化していく手法である．データ量

配置戦略を考察する．また，各ディスクのデータ領域をそれぞの差 δcap は以下のとおりである．

れ左右の領域及びプライマリ・バックアップ領域へと分割した¯¯
δcap (n) = ¯¯Xi∈Data in(n−1)S(i) −X¯¯
S(j)¯¯ (2)j∈Data in(n+1)

上記のディスク内データマイグレーションとディスク間デー

ことによるデータ配置戦略への影響や均衡化への効果を測定す
るため，それぞれ領域を分割する再配置戦略 (AOD-W) と領域を分割しない再配置戦略 (AOD-S) を提案する．まず，混在環境においては，何を均衡化すべきか考察する．

タマイグレーションを合わせることによって，AOD 法ではディ

4. 2 混在環境におけるデータ配置

スク毎の負荷の均衡化，及びデータ量の均衡化を行っている．

混在環境において，その速度性能を引き出すためには，帯域—4— "!"$#!%'&)(*%#,+# -%'# .0/%

利用率及び容量利用率の均衡化が必要ある．まず，データを読み出す場合，そのデータにとって必要な分だけの帯域を占有し，また必要な帯域が確保できない場合は読み出しが行えず，速度性能低下につながる．そのため，速度性能を引き出すためには，

FHG?I J
2 G?K?L 8J

ディスク上の容量使用率が大きく影響する．そのため，各ディ
スクのシーク性能を落とさないためには，容量利用率を均衡化

FHG?I J
2 GDK?L J:<; =?>A@'BC

帯域に対して負荷を偏らせない，つまり帯域利用率を均衡化する必要があるためである．また，ディスクのシーク性能はそのFHG?I J
2 G?K?L J '12
34657

FHG?I J
2 GDKML J

FHG?I J
2 GDK?L J

 











:<; =D>A@  

 


:<; =?>A@'E

 

 
9 12
 '34657

9 12
 34657

FHG?I J
2 G?K?L J'12
 34657

'12
834657 12
34657させることが必要である．
図 6 帯域利用率の偏り

しかし，AOD 法ではデータの配置は値域分散で決定される
ため，初期配置のままでは均衡化が行えない．そのため，デー
タマイグレーションを利用することによって，この帯域利用率のディスクが混在する環境において，容量を有効利用するため及び容量利用率が均衡化した状況を作り出す．以下ではそのには，各ディスクの容量利用率を均衡化させる必要がある．

データマイグレーションを各ディスクの帯域利用率・容量利用

まず，ディスクを左右の領域に分割しない場合の手法 (AOD-

率を均衡化させられるように拡張する方法を示す．

W) を考える．この場合，ディスク間マイグレーションの移動

4. 3 ディスク内データマイグレーションの拡張決定のためのデータ量の差の絶対値 δcap を，以下の式 (5) のよ

従来のディスク内データマイグレーションでは，各ディスク

うに，データ量だけではなく，ディスク毎の容量 (C(n)) も用への負荷を均衡化していた．しかし，様々な帯域のディスクがいて容量利用率 (= データ量/容量) とした手法を提案する．

混在する環境においては，単純に負荷を均衡化するだけでは帯域の有効利用はできない．そのためには，各ディスクの帯域利P¯P¯S(j) ¯¯ i∈Data in(n−1) S(i)j∈Data in(n+1)¯¯(5)δcap w (n) ≡ ¯−¯C(n − 1)C(n + 1)

用率の均衡化が必要である．
まず，プライマリ・バックアップ領域に分割しない手法 (AOD-

また，ディスクを左右の領域に分割した手法 (AOD-S) につ

W) を考える．この場合，ディスク内マイグレーションの移動いても考える．この場合，各領域毎の容量利用率を考えること決定のための負荷の差の絶対値 δband を，以下の式 (3) のようによって，システム全体での容量使用率を考えなくてはならなに，負荷だけではなく，各ディスク毎の帯域 (B(n)) も用いてい．よって，ディスク n の左の領域 Ln 及び右の領域 Rn に割

帯域利用率 (= 負荷/帯域) とした手法を提案する．

り当てられた容量 C(Ln ), C(Rn ) を用いて，ディスク間データ

P¯P¯A(j) ¯¯ i∈Data in(n) A(i)j∈Data in(n+1)¯¯(3)δband w (n) ≡ ¯−¯B(n)B(n + 1)

マイグレーションの容量の差の絶対値 δcap を，以下の式 (6) をまた，プライマリ・バックアップ領域に分割した手法 (AOD-S)のように変更した手法を提案する．

P¯P¯
S(j) ¯¯ i∈Data in(Ln ) S(i)j∈Data in(Rn)¯¯(6)δcap s (n) ≡ ¯−¯C(Ln )
C(Rn )

についても考える．この場合，各領域毎の帯域利用率を均衡化することによって，システム全体での帯域利用率の均衡化を考えなくてはならない．しかし，ディスクのデータ配置領域決定

これによって，各ディスクの容量利用率の差が小さくなることになり，システム全体での容量の有効利用が行える．

時には各領域への帯域は決めておらず，その代りに各領域へ配

4. 5 帯 域 変 更

置されるプライマリデータ量が決められている．このプライマ

しかし，これだけでは問題がある．実際，図 6 のように，リデータ量は，各領域で使用して欲しい帯域の割合に応じて決全領域の容量利用率がすべて 0.5 で同じになっており，かつめられた値である．そのため，各領域について，このプライマ

Diskn − 1 の右の領域と Disk n の左の領域の帯域利用率がそれ

リ領域の大きさに応じた帯域を割り当てればよいことになる．

ぞれ 0.7 で等しく，また，Disk n の右の領域と Disk n + 1 の

よってディスク n の左の領域 Ln 及び右の領域 Rn に割り当て

左の領域の帯域利用率がそれぞれ 0.3 で等しくなっているようられた帯域 B(Ln ), B(Rn ) を用いて，ディスク内データマイグ

な場合がある．この場合，各領域で容量利用率及び帯域利用率

レーションの負荷の差の絶対値 δband を，以下の式 (4) をのよ

は均衡化しているため，ディスク内データマイグレーション・

うに変更した手法を提案する．

ディスク間データマイグレーションともに行われない．しかし，ディスク n の左右の領域の帯域利用率はそれぞれ 0.7, 0.3P¯P¯A(j) ¯¯ i∈Data in(Rn ) A(i)j∈Data in(Ln+1 )¯(4) と偏っている．これはディスク内の左右の領域間の帯域利用率
δband s (n) ≡ ¯¯−¯B(Rn )
B(Ln+1 )を均衡化する方法がないためである．そのため，この領域間でこれによって，各ディスクの帯域利用率の差が小さくなるこの帯域偏りを解消する方法が必要である．

とにより，システム全体での帯域の有効利用が行える．

しかし，ディスク内の左右の領域間でのデータ移動を行うこ

4. 4 ディスク間データマイグレーションの拡張とはできない．そのため，この領域間で帯域利用率を均衡化さ従来のディスク間データマイグレーションでは，各ディスクせるためには，各領域に割り当てられた帯域自身を変更する必に保存されるデータ量を均衡化していた．しかし，様々な容量要がある．そのため，ここではディスク内の左と右の領域に割—5—

表 1 パラメータ設定

り当てられた帯域を再割り当てし，左右の領域の帯域利用率を均衡化させ，左右のディスクとの間の領域を再び不均一にし，Storage Number

10

Client Number

300

Initial Storage Capacity

30GB

Capacity Growth Rate

200%/year

Initial Storage Bandwidth

160M b/s

Bandwidth Growth Rate

125%/year

タを作成した．まず，シミュレーションで対象とするシステム

Total Data Size

50% of Total Capacity Sizeである，マルチメディアデータサーバの構成及びデータに対す

Data Size

1〜5GB (uniform distribution)

るアクセス傾向ついて紹介する．本手法においては，システム

Data Required Bandwidth 30〜40M b/s (uniform distribution)

再びディスク内マイグレーションを促すことにより，全ディス
クにおける各領域の帯域利用率を均衡化させる．

5. シミュレーション実装
提案手法の有用性を確認するために，提案手法のシミュレー

内での帯域利用率および容量利用率を均衡化させることにより速度性能を引き出すことを考えるため，本シミュレーションでRequest Number

100000

Zipf Parameter

0.271

は特にディスクの帯域及び容量部分についてシミュレートした．
また，マルチメディアサーバに対して，想定されるアクセスを中心であり，書き込みリクエストは非常に少ない．本実験にお与えた時の性能を測定する．特に，帯域に対する性能として，いては，読み出しリクエストのみを行い，その性能を測定する．

システム全体でのリクエスト待機時間，容量に対する性能としまた，本システムは動画配信のためにだけ用いられるため，クて，システム内の各ディスクの容量利用率の分散を測定した．

ライアント以外からのアクセスはないとする．マルチメディア

5. 1 前提となるシステム

サーバのような環境では，アクセスはすべてのデータに対して

本シミュレーションで対象とするマルチメディアデータサー

均一になされるのではなく，アクセス頻度の高いデータとアク

バとは，クライアントの要求に応じて動画データを返すような

セス頻度の低いデータが出てくる．なおそのアクセス傾向はストレージシステムのことである．このようなシステムに使わ

Zipf 分布で近似される [10]．

れるストレージシステムは，大量かつサイズの大きい動画デー
タを保存する必要があり，また動画データは増えていく一方であるため，巨大化する傾向がある．

6. 実

験

本実験の目的は拡張した AOD 法のデータ配置による帯域利

マルチメディアサーバのデータは，すべてのデータが一律に用率及び容量利用率均衡化の効果を測定することにある．そのアクセスされるということはなく，アクセス頻度の高いデータため，本実験ではデータ再配置が終わった後の均衡化状態の性とアクセス頻度の低いデータが混在するため，データ間のアク能について注目する．なお，本実験において使用したパラメー

セス頻度が違ってくる．また，動画データでは，動画を途切れ

タは表 1 に示すとおりである．以下に実験手順を示す．s

ることなく見るためには，常に一定以上のデータ転送速度が要（ 1 ） 10 台のストレージによりシステムを構築する

求される．そのため，このようなシステムではいかに一定以上（ 2 ） システムにデータを挿入する，このとき挿入するデーのデータ転送速度で送信できるかが重要になってくる．

タの総サイズをプライマリデータ及びバックアップデータ合わ

5. 2 シミュレーション環境

せてシステムの総容量の 50% となるようにする，なお 2 回目

まず，帯域に対する性能として，システム全体のリクエスト以降は古いデータを削除したのち再挿入する

待機時間を測定する．これは，各クライアントはそれぞれこの（ 3 ） クライアントから合計 100, 000 回アクセスを行う，シ

ディスクに対してコネクションを張り，動画データの読み出し

ステムはこの間にデータへのアクセス傾向を取得するに必要な帯域を占有することによりデータを読み出す．しかし，（ 4 ） 各手法によりデータの再配置を行う

必要な帯域を占有できなかった場合は，その読み出しリクエス（ 5 ） 再度クライアントから合計 100, 000 回アクセスを行

トは待機させられる．これは，占有できないまま帯域を使用し

い，性能測定を行う，なお 4 回繰り返し測定しその平均を取るてしまうとほかのクライアントの読み出しにも影響を与えてし（ 6 ） ディスクを 1 台取り換える，このとき取りのぞかれるまうためである．次に，容量に対する性能として，それぞれのディスクはランダムに選ばれる

ディスクの容量利用率を測定する．これは，それぞれ違う容量（ 7 ） (2)〜(6) を 20 回繰り返すを持つ複数のディスクにおいて，シーク性能を引き出すために，

ストレージとしては，現在のモデル (1000GB, 500M b/s) [11]各ディスクにおいて使用されている容量の割合を一定に保つ必を基準に，帯域向上率 1.25 倍/年，容量向上率 2 倍/年 として，

要があるからである．

5 年前 (30GB, 160M b/s) に使用を開始したとして計算を行っまた，ネットワークについては，各クライアントから全スト

た．このストレージを 10 台用いて，故障したら故障した時点

レージにそれぞれ接続されており，ユーザは任意のストレージの最新のディスクに入れ替えるとし，入れ替えを行った合計のデータを取得できるとする．またストレージ間もそれぞれお台数をシステムの混在具合のパラメータとした (以降これを混

互いにネットワークでつながれており，任意のストレージ同士在度と呼ぶ)．また，データについてはサイズを 1〜5GB ，及でデータを転送できるものとする．前提システムのようなマルび要求帯域を地上デジタル放送によるデータ配信をモデルとチメディアサーバにおけるアクセスは，読み出しリクエストがして 30〜40M b/s とし，これを現在の基準として，5 年前 (30

—6—

0.12

AOD-W
18 AOD-S
BSR
16
AOD
14

AOD-W
AOD-S
0.1
BSR
AOD

Variance of Capacity Utilization Rate

Total Waiting Time (Step)

20

12
10
8
6
4
2
0

0.08
0.06
0.04
0.02
0

10

12

図7

14
16
Replaced Storage Number

18

20

混在度に対するリクエスト待時間

0

5
10
15
Replaced Storage Number
図820

混在度に対する容量利用率の分散〜150M B, 9.8〜13M b/s) からディスクと同様にサイズが年率かる．また，AOD を拡張した 2 手法と BSR を用いた手法を2 倍，要求帯域が年率 1.25 倍でそれぞれ増加しているとする．

比較すると，交換台数 10 台以降は AOD 法を拡張した手法のまた，それぞれ一様分布とした．また，アクセス傾向として方が容量利用率は均衡化されているという結果となっている．

は，[10] で述べられている，パラメータ 0.271 の Zipf 分布とし

これは，BSR を用いた手法では，レプリカを作ることによってた．また，クライアント数を 300 台としている．

帯域の有効利用を図るため，帯域利用率の偏りが大きくなって以上の環境において，帯域及び容量を分割しない方法で AOD

きた時点で大量にレプリカを作成したためである．それに対し

法を拡張した手法 (AOD-W) と帯域及び容量を分割した方法でて，AOD 法を拡張した手法では，データの移動のみを行い帯AOD 法を拡張した手法 (AOD-S) と BSR を用いた手法 (BSR)

域利用率を均衡化しているため，容量利用率は最初から最後ま及び AOD 法を拡張せずにそのまま適用した手法の 4 手法につでほぼ変わらない．

いてリクエスト待機時間及び平均容量利用率を測定した．なお，

次に AOD を拡張した 2 手法について比較する．両手法の結

BSR を用いた手法では，バックアップを持つことを前提として果を見てみると，分割を行った手法の方が容量利用率の偏りがいないため，AOD 法と同じ条件にするために，最低 1 つレプ

大きくなっている．しかし，必ずしもすべての点において大きリカを持つこととした．また，各手法 3 回の平均値を取得した．

いわけではなく，同程度の値を示している点と，大きくなって

6. 1 帯 域 比 較

いる点が存在することがわかる．これは分割を行った手法を用

リクエスト待機時間の結果は図 7 のようになった．グラフかいた場合，ディスクの組み合わせによっては，非常に容量の小らわかるとおり，混在度が高い状態では，AOD 法を拡張したさな領域ができてしまい，その領域が壁となり容量分散が進ま

2 手法の待機時間は少なくとも BSR を用いた手法及び従来のない状況になるためである．たとえば図 9 における Disk n − 1

AOD 法の待機時間を下回ることはなく，帯域利用率が均衡化の右の領域及びディスク n の左の領域がそれぞれ 4GB 及びできているという結果になった．これは AOD 法を拡張した手

6GB となり，他の領域 (240GB や 390GB) に比べて非常に小法では，各ディスクの「帯域利用率」を均衡化しており，全ディ

さい容量になっている．容量の小さい領域においては，領域へ

スクの帯域利用率が均衡化し，一部ディスクへのリクエスト集のデータ配置や領域からのデータ移動を行った場合，容量利用中がなかったが，BSR を用いた手法ではディスクとデータの率が急激に変わってしまう．結果，容量の小さい領域において

BSR のかい離度のみ見ているため，また従来の AOD 法各ディ

データを配置したり，逆にデータを移動させることができなくスクのデータ量のみを見ているため，必ずしも帯域利用率が均なってしまう．結局，小さな領域の左右で，データを移動でき衡化せず，一部ディスクにリクエストが集中したためである．

なくなってしまうため，容量の小さな領域の隣接ディスクにお次に AOD を拡張した 2 手法について比較する．両手法の結いて容量利用率の均衡化がうまくできなくなってしまう．その果を見てみると，混在度によってその優劣は変わっており，ど

結果，確実に分散させられる分割しない手法 (AOD-W) の方がちらかの方が優れているとはいえない．これは，負荷について平均するとよくなるためである．

は必ずしもディスク内の左右の領域で均衡化している必要はな

6. 3 実験考察のまとめ

く，左右の領域では偏っていても，ディスク全体として偏って以上により，AOD 法を拡張した手法では BSR を用いた手法

いなければ，十分帯域の有効利用が可能であるからである．

及び従来の AOD 法に比べて，ほぼ同程度帯域利用率が均衡化

6. 2 容 量 比 較しており，容量利用率は大きく均衡化している．よって，速度

容量利用率の分散の結果は図 8 のようになった．AOD を拡性能について帯域利用率の均衡化による効果及び容量利用率の張した 2 手法と従来の AOD を比較すると，その容量利用率の均衡化によるシーク性能の双方を考慮すれば，AOD 法を拡張

分散は小さくなっており，容量利用率が均衡化されたことがわ

した手法は BSR を用いた手法及び従来の AOD 法に比べ向上—7—

,.-0/1/2436587:9;0<>=@? A BDCE? FG<8-:9? 27  !#"%$&(' !)"*$
 

近くになった場合にも本アルゴリズムは正常に動くか，またシ 
 
  !#"*$+'

ステム規模がさらに大きくなった場合に現実的時間で均衡化処       

図 9 ディスク間データマイグレーションのボトルネック

理が終わるのかなどについても検証を行う必要がある．また，本手法を実際の運用環境に適用し，実機でもシミュレーションの通りに動くかどうか検証を行う必要がある．特に実際のスト
レージの挙動，キャッシュ等の影響や，ストレージ以外の部分，
例えばメタデータサーバやキャッシュサーバ等の影響や，ネッ
トワーク構成による違い等の検証が必要である．

謝辞すると考えられる．

AOD 法を拡張した 2 手法では，分割しない方が若干良いと

本研究の一部は， 科学技術振興機構戦略的創造研究推進事業

いう結果になった．これは，分割した手法ではその分割の仕方

CREST，文部科学省科学研究費補助金特定領域研究 (19024028)

によっては逆に戦略上の壁となってしまうためである．今後分

および東京工業大学 21 世紀 COE プログラム「大規模知識資割した手法をよくするためには，データ移動を考慮して，一時源の体系化と活用基盤構築」の助成により行なわれた．

的に領域を超える量になったとしてもデータ移動ができるようにするなどの改良が必要である．

7. まとめと今後の課題
本稿では，ハードディスクドライブの帯域及び容量の向上に伴う，様々な帯域や容量のディスクが混在するストレージシス
テム構築の要求を満たすため，ディスク混在環境においても速度性能を引き出すため，その帯域利用率と容量利用率を同時に均衡化することを目指した．そのために均一環境において負荷及びデータ量を均衡化する手法である AOD 法の拡張を行った．
本稿では [3] で提案したディスク領域分割手法を基にデータ配置の決定を行った．まず，プライマリデータの配置で帯域利用率を均衡化，バックアップデータの配置で容量利用率を均衡化することを考えた．このために，ディスク内データマイグレー
ション，及びディスク間データマイグレーションの拡張を行った．また，シミュレーションにより実験し，BSR を用いた手法
及び従来の AOD 法と比較することにより，AOD 法を拡張した手法の有用性を確認した．特に，データ配置領域を分割しない手法による帯域利用率及び容量利用率の均衡化を確認し，総合的な速度性能を最も引き出せると考えられることを示した．
今後の課題としては，まず，より詳細な調査が必要である．
本稿におけるシミュレーションでは容量利用率のみを測定したが，より詳細には容量利用率によるシーク性能への影響をシ
ミュレーションに含める必要がある．次に，データ移動時に容量の小さい領域が壁となってしまうという問題点について考慮
して改良する必要がある．このとき，データ移動時に一時的に領域の容量を超えたとしても，最終的にその領域の大きさ以内に収まるならば移動できるようにすることなどにより解決できると考える．さらに，本手法によるデータ配置が，最適なデー
タ配置と比較して，どの程度の最適性を達成しているか検証を行う必要がある．加えて，マイグレーションそのもののコストの評価や，マイグレーション実行時の性能評価についても行う必要がある．今回は特に Read アクセスが大半と仮定して評価

文

献[1] E. Grochowski and R. D. Halem. Technological impact ofmagnetic hard disk drives on storage systems. IBM Systems
Journal, Vol. 42, No. 2, pp. 338–346, 2003.
[2] Akitsugu Watanabe and Haruo Yokota. Adaptive overlapped declustering: A highly available data-placement
method balancing access load and space utilization. pp.
828–839. 21st International Conference on Data Engineering (ICDE’05), 2005.
[3] Makoto Kataigi, Dai Kobayashi, and Haruo Yokota. Consideration of disk segmentation and disk sequencingfor eﬃcientuse of disk resource on heterogeneous disk environment. In
Proceedings of the Second IEEE International Conference
on Digital Information Management, Vol. 107, pp. 577–579,
2007.
[4] Asit Dan and Dinkar Sitaram. An online video placement
policy based on bandwidth to space ratio (BSR). SIGMOD
Rec., Vol. 24, No. 2, pp. 376–385, 1995.
[5] T. Cortes and J. Labarta. A case for heterogeneous diskarrays. IEEE International Conference on Cluster Computing (Cluster’00), Vol. 00, pp. 319–325, 2000.
[6] T. Cortes and J. Labarta. Extending heterogeneity to RAID
level 5. In Proceedings of the 2001 USENIX Technical Conference, pp. 119–132, Boston, 2001. USENIX Association.
[7] Yuewei Wang and David Hung-Chang Du. Weighted striping in multimedia servers. In International Conference on
Multimedia Computing and Systems, pp. 102–109, 1997.
[8] Jen-Wen Ding and Yueh-Min Huang. Resource-based striping: An eﬃcient striping strategy for video servers using
heterogeneous disk-subsystems. Multimedia Tools and Applications, Vol. 19, No. 1, pp. 29–51, 2003.
[9] Roger Zimmermann and Shahram Ghandeharizadeh. Continuous display using heterogeneous disk-subsystems. In
MULTIMEDIA ’97: Proceedings of the ﬁfth ACM international conference on Multimedia, pp. 227–238, New York,NY, USA, 1997. ACM.
[10] A. Dan, D. Sitaram, and P. Shahabuddin. Scheduling policies for an on-demand video server with batching. In MULTIMEDIA ’94: Proceedings of the second ACM international conference on Multimedia, pp. 15–23, New York, NY,
USA, 1994. ACM.
[11] Hitachi Ultrastar A7K1000 Datasheet.
http://www.hitachigst.com/tech/techlib.nsf/techdocs/
DF2EF568E18716F5862572C20067A757/$ﬁle/Ultrastar A7K1000 ﬁnal DS.pdf.

を行ったが，Write アクセスが多い場合の評価も必要である．
また，実験についても，さらに様々な状況，特に容量が飽和—8—