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

並列ストレージにおけるデータ再配置による長期的負荷均衡化と短期的応答性能の両立

Title(English)

Simultaneous Pursuit of Load Balancing by Data Migration and Qualityof Response Performance on Parallel Storage Systems

著者(和文)

小林大, 横田治夫

Authors(English)

Dai Kobayashi, Haruo Yokota

出典(和文)

情報処理学会論文誌：データベース, Vol. 49, No. SIG 7 (TOD 37), pp.
29-43

Citation(English)

IPSJ Transactions on Database (TOD), Vol. 49, No. SIG 7 (TOD 37),
pp. 29-43

発行日 / Pub. date2008, 3

権利情報 / Copyright

ここに掲載した著作物の利用に関する注意: 本著作物の著作権は（社）情報処理学会に帰属します。本著作物は著作権者である情報処理学会の許可のもとに掲載するものです。ご利用に当たっては「著作権法」ならびに「情報処理学会倫理綱領」に従うことをお願いいたします。
The copyright of this material is retained by the Information Processing
Society of Japan (IPSJ). This material is published on this web site withthe agreement of the author (s) and the IPSJ. Please be complied with
Copyright Law of Japan and the Code of Ethics of the IPSJ if any users
wish to reproduce, make derivative work, distribute or make available tothe public any part or whole thereof.

Powered by T2R2 (Science Tokyo Research Repository)

Vol. 49

No. SIG 7(TOD 37)

Mar. 2008

情報処理学会論文誌：データベース

並列ストレージにおけるデータ再配置による
長期的負荷均衡化と短期的応答性能の両立
小林

大†1,†2 横

田

治

夫†1

並列ストレージシステムにおける性能維持では，アクセス負荷の時間的変化に対するストレージ
ノード間のアクセス負荷均衡化を迅速に行うことが肝要である．しかし動的負荷均衡化をデータマイ
グレーションによるデータ再配置によって行う手法は，システム処理能力の一部を使用するため短期的に応答性能保証が困難となる．本論文では，データマイグレーションによる負荷均衡化と応答性能維持の両立を目指す．提案する手法では，他のノード中に格納される複製データを用いたデータ移動
経路選択およびアクセス回送を，各ノードの許容最大負荷を基準として制御する．これにより応答性
能要件を維持しつつ迅速にマイグレーションを行う処理能力を確保する．シミュレーションによる実験により，読み出しアクセス中心のワークロード下における提案手法の有効性を検証した．その結果，提案手法を用いることで，単純な人工的ワークロード下では 33%〜38%の負荷耐性向上，実利用を想定したワークロード下でもマイグレーションに起因する超過レスポンスの 93%削減を達成し，応答性能を維持しつつ迅速なマイグレーションが可能となることが示された．

Simultaneous Pursuit of Load Balancing by Data Migration
and Quality of Response Performance on Parallel Storage Systems
Dai Kobayashi†1,†2 and Haruo Yokota†1
Load balancing between storage nodes is important to keep performance of parallel storage
systems above required level. However, online load balancing with data migration causes
a temporary quality violation of system services. To solve the problem, we propose a method
using replicated data to keep the service quality even during the data migration. It forwards
overloaded accesses to the replica data, and selects an appropriate source node of the migration from its original or replica to moderate the load and to shorten the migration process.
We show its eﬃciency with simulation results.

ムを著しく増加させる4) ．そのため，ノード間での大1. は じ め にきなアクセス負荷偏りは負荷均衡化により除去すべき

爆発的に増大するデータを可用性，柔軟性，拡張性である．データマイグレーションは並列構成のデータといった技術項目を満たしつつ低い管理コストで格納

ベースやストレージシステムにおけるアクセス負荷均するストレージシステムの実現が求められている．こ衡化手法である．データマイグレーションでは，ネットのため，HDD に加え CPU やメモリ等を組み込んだ

ワーク結合されたストレージノード間で各データのア

高機能なストレージノードを LAN により多数結合しクセス負荷傾向を考慮しデータを移動することでデーたシステムである高機能並列ストレージシステムが注

タ配置を変化させる．これにより，一部ノードへのア

目されている1)–3) ．

クセス集中を回避し，システムに要請されるサービス

管理コスト増加の一因として負荷均衡化があげられ品質を維持することができる．高機能並列ストレージる．システムを構成する一部のストレージノードへのシステムではストレージノード上の計算資源を用いてアクセス集中はストレージノードのレスポンスタイ

ストレージシステムの自律管理を行うことが可能である．動的に採取される現在の負荷情報をもとにシステ
ムが自律的に行う動的データマイグレーションは，セ†1 東京工業大学
Tokyo Institute of Technology†2 日本学術振興会特別研究員 DC
Research fellow, Japan Society for the Promotion of
Science

ルフパフォーマンスチューニング手法として提案され効果を得ている5),6) ．
しかし，動的データマイグレーションによるアクセ
29

30

情報処理学会論文誌：データベース

Mar. 2008

ス負荷均衡化は，短期的にはノード性能を低下させる

大負荷以下の負荷で動作可能となることを目指す．なことが問題となる．データマイグレーションがディス

お，本論文においてはデータマイグレーション発生時

クアクセスやネットワーク転送等，ストレージノードの特殊な状況のみ複製の利用を考慮し，つねにアクセが通常のデータ提供サービスに用いる資源の一部を利スを複製へ回送する負荷均衡化手法を併用するアクセ用するためである．アクセス傾向の変化が激しい場合

ス回送常用システムへの拡張は今後の課題とする．

や，負荷の評価精度が低い場合，処理能力がすでに飽

本論文の後半では，並列ストレージシミュレーショ

和しているストレージノードからのデータ転送が求め

ンプログラムによる実験により，提案手法の有効性られる．その結果，ユーザにより要求される応答性能を確認する．実験では，Zipf 分布に基づく読み出しが満たされなくなる可能性がある．

リクエスト中心の人工的な負荷，および大規模 WEB

データマイグレーション中の応答性能維持に関するサーバから採取されたアクセス傾向に基づくワーク

既存研究として，速度制御がある7)–9) ．これらの既存ロードを用いる．それぞれにおいて応答性能，マイグ

研究はいずれも，主に階層構成のストレージシステ

レーション時間の観点から評価を行う．その結果，提ムにおける階層間のデータ移動を目的としている．上案手法を用いることで，単純な人工的ワークロード下記の既存研究はいずれも，階層構成におけるデータ移では 33%〜38%の負荷耐性向上，WEB ワークロード

動は使われていないデータに対する移動であり，デー下でもマイグレーションに起因する超過レスポンスのタマイグレーションの速度を遅らせてもシステムレス

93%削減を達成し，応答性能を維持しつつ迅速なマイグレーションが可能となることが示された．

ポンスタイムやスループットへの影響が小さいことを仮定し，マイグレーション速度を調節するアプローチ

本論文の構成を以下に示す．つづく 2 章では，デーをとっている．一方，階層構成におけるデータマイグ

タマイグレーション，応答性能保証，複製の利用に関レーションと異なり，負荷均衡化のためのデータマイする関連研究について論ずる．3 章において前提とす

グレーションは迅速な実行が必要とされる．データ移るシステムおよびデータマイグレーション戦略につい

動元，移動先がともにサービス提供中であり，かつ大て述べる．4 章では RM 手法で用いる 2 種の複製利用

きな負荷のアクセス下であることが多いためである．

法を紹介し，5 章において，提案する RM 手法を構成

速度調整による応答性能保証は負荷均衡化のためのマする複製制御アルゴリズムについて述べる．6 章におイグレーションでは難しい．

いて，本論文における実験環境の概要を述べる．7 章

こ の よ う な 問 題 を 解 決 す る た め ，本 論 文 で は ，

では人工的なワークロード，8 章では実利用を想定しReplica-assisted Migration（以下，RM 手法）を提たワークロードを用いて，提案手法の有効性をシミュ案する．RM 手法により，マイグレーション速度を減

レーションにより確認する．最後に 9 章でまとめと今少させることなく，マイグレーション中の応答性能維後の課題について述べる．

持を達成する．RM 手法では複製データを用いる．並列ストレージシステムでは，ノード故障によるデータ

2. 関 連 研 究喪失を防ぐため，他のノードのバックアップのため複アクセス負荷均衡化は主に無共有並列データベース

製データを保持する構成をとるものが多い．RM 手法の分野における主要な課題であった．Scheuermann

では，他のノードに配置された複製データを利用する

ら11) は，分割されたテーブルを格納するシステムにことで負荷集中ノードから一時的に処理能力を捻出す

おいて，各データ断片のアクセス負荷をもとにした動る．よって，ノードに負荷が集中した後でも，データ

的データマイグレーションによる負荷均衡化を達成しマイグレーションを行うことが可能となる．我々の先た．そして彼らは動的マイグレーションと性能保証の行研究10) では，複製データへのアクセス回送による両立が次の重要な課題であると述べていた5) ．また，応答性能維持効果について論じた．本論文の提案では，

Feeliﬂ らは並列 B-tree 索引構造の負荷分散をデータ

複製データを用いたマイグレーション経路選択，およマイグレーションにより解決している6) ．このとき彼

び複製へのアクセス回送制御を行い，処理能力を確保

らは速度制御による性能保証を導入している．これはする．提案する RM 手法では，この経路選択，アク

データ量が比較的少ない索引構造のマイグレーション

セス回送の 2 種類を，ストレージノードの許容最大性

として効果が得られている．データマイグレーション

能を基に制御する．RM 手法によって，負荷集中ノーと応答性能保証両立に対する速度制御によるアプロー

ド，マイグレーション対象ノード，そしてそれらの複チは階層構成ストレージシステムにおいて多く提案さ製保持ノードそれぞれが性能要件を維持可能な許容最れている．階層構成では上位層と下位層の間でデータ

Vol. 49

No. SIG 7(TOD 37)

並列ストレージにおける長期的負荷均衡化と短期的応答性能の両立

31を移動する必要がある．これまでに，現在のレスポン
スタイムを基にした適応的速度制御8) ，負荷変化の予想による速度制御7) ，ストレージノードの許容最大性
能見積り値を基にした速度制御9) 等が提案されている．
しかし，負荷均衡化のためのデータマイグレーション
では速度制御の効果が低い．これは本論文における実験で明らかにする．
自律データ管理と応答性能保証の問題は，ストレー
ジアレイにおける障害回復時においても問題となっている．ディスク障害にともなう突発的な負荷不均衡や，

図 1 アクセス回送と応答性能（データ配置による負荷均衡時の値を 1 とした相対応答性能）
Fig. 1 Access forwarding and response time (Normarizedbased on load balanced with suitable data placement).

データ冗長度回復のためのアクセスが応答性能を低下させるためである．Chained Declustering 12) は，前行うことを仮定する．データの更新はプライマリと同者の突発的な不均衡を複製データへのアクセス回送

時にすべての複製データにも同期的に行われる．以下により解決している．一方，Façade

13)は突発的な不では簡単な実験により，複製間ラウンドロビンによる均衡や冗長度回復と応答性能保証を，クライアントとアクセス回送常用，負荷が少ないノード上の複製へア

ストレージの間のフローコントロールにより解決してクセスを回送する適応的アクセス回送常用，アクセス回

いる．

送なし（データ配置は負荷均衡化），アクセス回送なし

複製データを障害回復だけでなくアクセスにも利用（データ配置は格納量均衡）の 4 種の平均応答性能を測する手法は，WAN における長いネットワークレイテ

定・比較する．図中ではそれぞれ，fwd(round-robin)，

ンシの隠蔽14)–16)，ビデオ配信サーバの負荷均衡化

17)等で長く利用されてきた．しかし，高機能並列スト

fwd(adaptive)，load-balanced，amount-balanced と表記する．

レージにおいては，単純なアクセス回送は各ストレー

6 章で述べるシステムでノード 4 台，後述の Zipf 分

ジノード上のキャッシュメモリ利用率を低下させると布，ポアソン到着で到着率 350 [req/sec]，傾向変化ないう問題がある18),19) ．一方データマイグレーション

しのワークロードを発生させた．また，キャッシュミ

によるアクセスはキャッシュヒット率が低いアクセスス時の性能ペナルティを大きくするため，SYNC 書きである．よって，キャッシュミスアクセスを優先的に込みを 25%，50%混ぜたアクセスでも実験を行った．

回送する手法19) により，マイグレーションによる負図 1 に，データ配置格納量均衡時の値を 1 とした

荷上昇は他ノードに回送できる．

3. 前提とするシステムおよびデータマイグ
レーション

相対応答性能を示す．図より，アクセス回送により著しく応答性能が改善される例がある反面，ラウンドロ
ビンや適応的回送においても応答性能が悪化する例も見られる．たとえば，Read 比率 0.75，Zipf 係数 0.6

3.1 シ ス テ ムの例では，ノード間アクセス量の標本分散が適応的

本論文では，Gigabit Ethernet 等の，高速な LAN

回送により 1/4 倍に改善されているにもかかわらず，

上に並列接続された高機能ストレージノードにより構キャッシュヒット率が 37%から 31%へ低下したため成されたシステムを想定する．データは，ファイル，

許容負荷量が低下し，応答性能が悪化している．

エクステント，ページ，ブロック等の粒度で分割を行

このため，本論文においてはデータマイグレーショ

い，各ストレージノードに分散格納する．分割されたン発生時の特殊な状況のみ複製の利用を考慮し，アク

データ断片と格納されるストレージノードの対応は，

セス回送常用への拡張は今後の課題とする．

メタデータサーバや分散ディレクトリを利用したスト3.2 データマイグレーション

レージ仮想化機構により利用者から隠蔽される．その時間的に変化するワークロード下でシステム全体のため，システムは運用中の動的データ再配置を低い管性能を維持するため，システムはデータ動的再配置

理コストで行うことが可能となる．また，各ノードは（データマイグレーション）による負荷均衡化を自律

アクセスのためのデータ断片（プライマリデータ）に的に行う．データマイグレーションは，各ノードごと

加え，他のある 1 つのノードに格納されたプライマリのアクセス負荷が要求性能を維持可能な量を超えない

データの複製データを障害復旧用に保持する．

データ配置を目標とする．本論文では集約評価型の負データの読み出しは基本的にプライマリデータから荷均衡化アルゴリズムを前提とする．すべてのノード

32

情報処理学会論文誌：データベース

Mar. 2008

は，自ノードに格納されるデータの現在の負荷を表す
負荷値を記録している．ここで負荷とはデータ提供のための資源利用量を示す度合いである．READ によるプライマリデータアクセス，WRITE によるプライ
マリ，バックアップ両データに対するアクセスの量で決まる．負荷値は負荷を定量的に表現する値である．
例として，最近一定時間のアクセス量の平均値や，最近一定回数のアクセスの到達時間間隔，あるいはそれらの値を各ノードの性能を表す値によって正規化した値が負荷値として利用される．
集約評価型の負荷均衡化では，システムはある定められたインターバル時間ごとに以下の作業を行う．まず全ノードは，ある 1 つのノード（以下では coordi-

図 2 RM 手法における 2 種類の複製利用法．(a) マイグレーション経路選択，(b) アクセス回送
Fig. 2 Relica usage in RM method. (a) Migration source
node selection, (b) access forwarding.

nator と呼ぶ）を選定する．そして coordinator に対し直接，あるいは段階的20) に自ノードの負荷値を送の応答性能維持を達成する RM 手法のアルゴリズム

信する．全ノードの負荷値を受け取った coordinatorを紹介する．

は，すべてのノード間で負荷値が均衡化するデータ配

マイグレーション経路選択では，移動対象データの置とそのためのデータ移動戦略を計算する．移動戦略

複製を保持するノードのうち最も負荷の低いノードをはマイグレーションタスクの集合とする．ここでマイデータ移動元ノードとして選択する．図 2 (a) にその

グレーションタスクは（移動元ノード，移動先ノード，様子を示す．データ p3 をノード n へ移動する．デー

移動負荷値）とする．そして各ノードに移動戦略を送タ移動元ノード j の負荷が複製保持ノード k よりも信する．

低ければ，ノード j のプライマリデータ（p3）を移動

coordinator では集約負荷値から移動する負荷値のみを決定し，具体的な移動データの特定は各ノードする．そうでなければ，ノード k 上に格納された p3の複製データ（rep3）を移動する．

内で行う．これは個々の格納データごとの負荷情報を

アクセス回送では，あるノードに格納されたデータ

coordinator ノードへ集約することはコストが高いためである．各ノードは，与えられた戦略に含まれる移へのアクセスの一部を，当該データの複製データを保動負荷値がある閾値を越えた場合，自ノードの個々の象ノードが負荷集中ノードとなった場合，このアクセ格納データに関する負荷値を走査し，与えられた移動

ス回送を用いマイグレーション対象ノード上にマイグ

負荷値を満たすデータセットを特定する．各ノードはレーション処理能力を確保することができる．アクセ

指定された移動先ノードに必要なデータを送信する．

ス回送は各ノード上のキャッシュヒット率の低下を招

ここで，データの移動は Silvering 8) と呼ばれる操く可能性がある．アクセス頻度の高い少数の同じデー

作により行われることを前提する．Silvering ではまタが複数のノード上のキャッシュに格納されるためでず移動するデータの複製を移動先ノードに作成する．

ある．そこで，我々が以前に提案した，キャッシュヒッ

次に複製作成開始時から終了時までの更新を複製に適

ト・ミスを観測しつつ回送対象アクセスリクエストを用する．最後に元のデータを削除する．これにより移選出する手法19) により，この低下を抑えることとす

動中データへの排他ロック取得期間を短く抑えることる．図 2 (b) では，ノード j 上のデータ p3 をノード nができる．よって，以下の議論ではデータマイグレー

へ移動する．ノード j の処理能力がデータマイグレー

持するノードに回送する．データマイグレーション対ションのための排他制御による応答性能への影響は考ションにより飽和するため，データ p4 へのアクセス

慮しないこととする．

をノード k 上にある複製データ rep4 へ回送している．

4. 複製データの併用

アクセス回送は次のように行う．あらかじめ，各ノー
ド i ごとにアクセス回送率 ri を算出する．回送率 ri

本章ではまず RM 手法で用いる複製の 2 つの利用は 0 ≤ ri ≤ 1 であり，そのノード上データに要求さ法である，マイグレーション経路選択とアクセス回送れる全アクセス量（アクセス数とアクセスサイズの積）制御についてそれぞれ説明を行う．続いて次章においのうち，複製側へ回送するアクセス量の割合を示す．

て，2 つの利用法を制御しデータマイグレーション中

ノード j が移動元の場合，移動元ノード j に対する

Vol. 49

No. SIG 7(TOD 37)

並列ストレージにおける長期的負荷均衡化と短期的応答性能の両立

33

アクセス要求を，与えられた回送率 rj の割合で，複製の存在するノード k へと回送するようにノード j 上のコントローラをセットする．つづいてマイグレーション戦略に基づきデータを移動する．その間のノード j
へのアクセス要求の一部はセットされた回送率 rj とアクセス回送判定手法19) に基づき複製ノード k へ回送される．データ移動完了後，複製への要求回送率 rj
を 0 にする．

5. Replica-assisted Migration
データマイグレーションによる応答性能の低下は，

図 3 アクセス回送率計算アルゴリズムの概要
Fig. 3 Concepts of algorithm for calcuration of accessforwarding ratio.

データマイグレーション処理を行うストレージノードのアクセス処理能力飽和により起こる．クライアント

負荷値を維持するためのアクセス回送率の計算を行う．

への応答性能を維持しつつマイグレーションへも処理

各データに対する性能要件は主にアクセスに対する能力を確保するため，マイグレーション経路の選択とレスポンスタイムで表される．ストレージノードのレ

アクセス回送率の計算が重要となる．ラウンドロビン

スポンスタイムは負荷の増加に対して巨視的には単調等の単純な戦略では，複製利用により負荷集中ノード

増加する4) ．よって，レスポンスタイムとしての性能の負荷が複製保持ノードに移譲されることで，複製保要件は各ノードの許容最大負荷値へ変換できる．許容

持ノードの許容最大負荷を超えてしまうためである．

最大負荷値は，ストレージノードのディスク，ネット

加えて，単純な負荷分散やスループット向上ではなく，ワーク等の性能緒元，用途における不変のアクセス傾

各ノードの性能要件保持を考慮する必要がある．

向（キャッシュヒット率，アクセスサイズ分布等）を本章では，5.2 節で述べる我々が以前から提案している自律ディスク

1)のデータ配置を前提に，マイグ

考慮のうえ，事前に各ノードの性能測定を行った結果を用いて算出する．

レーション経路選択とアクセス回送を制御する，RM

提案手法では 3 章で述べた，coordinator によるマ手法を提案する．移動元ノードの負荷が最大許容量にイグレーション戦略立案後，得られた戦略を利用して近い場合でも，複製データ保持ノードの処理能力を用次のことを行う．まずマイグレーション経路選択アルい，データマイグレーションによる負荷均衡化を行う

ゴリズムにより，複製保持ノードのうちより負荷の低ことが可能となる．さらにマイグレーション用処理能

いノードにマイグレーションタスクの移動元ノードを力の確保も重視するためマイグレーション速度低下が割り当てる．その結果として，各ノード i における割少ない．

当てマイグレーションタスク数 si（移動先ノードまたRM 手法では性能要件として与えられるレスポンス

は移動元ノードとなったタスクの個数）が得られる．

タイムを基に集約評価型のアルゴリズムにより coor-

マイグレーション経路選択アルゴリズムでは，まずす

dinator ノード上で，2 つの複製データ利用戦略を決定する．これは，負荷集中ノード，マイグレーション

べてのマイグレーションタスクからデータ移動先ノー

対象ノード，そしてそれらの複製保持ノードそれぞれ再計算する．そして戦略から得られるマイグレーショが性能要件を維持可能な許容最大負荷以下の負荷で動ンタスク 1 つごとに，そのデータ移動元ノードを最も作可能となる戦略を得るためである．実際の制御アル

負荷が低い複製ノードに割り当てる．

ドのリストを作成し，それをもとに各ノードの負荷をゴリズム構築・記述については，データ配置，複製配

つづいて提案手法のうち回送率計算アルゴリズムに置の制約による影響が大きい．そこで本章では，まずより，アクセス回送率を算出する．その結果として各RM 手法による複製制御の概要を説明する．つづいて
自律ディスクへの適用を考慮し，アルゴリズムを構築する．

率計算アルゴリズムでは，クライアントへのアクセス

ノード i におけるアクセス回送率 ri が得られる．回送への処理能力を確保しつつ，マイグレーション対象タ

5.1 概
要RM 手法では，まずマイグレーション経路の選択に

スクにより多くの処理能力を確保する．図 3 にアクセよりマイグレーションタスクの移動元をより負荷の低

中 M はマイグレーション経路選択アルゴリズムによりいノードに割り当てる．その後，各ノードの許容最大

データ移動元もしくはデータ移動先として割り当てらス回送率計算アルゴリズムの概要を示す．ここで，図34Mar. 2008

情報処理学会論文誌：データベース

で述べた RM 手法を実現するためのアルゴリズムを記述する．
以下では各ノード i の複製データはノード (i + 1)に保持されているとする．また明記のない場合ノード
図 4 Chained Declustering と値域分割データ配置を適用したス
トレージシステムの例
Fig. 4 Example of Chained Declustering and range
partitioning.

番号 i に対する加減算 i ± p は i ± p mod N とする．
ただし N は全ノード数である．ここで Li (t) は採集された時刻 t におけるノード i の格納データ（プライマリおよび他のノードの複製）に対するアクセス負荷れたタスク数を表す．マイグレーション対象ノード nの複製保持ノード j へタスクが割り当てられていない場合（図 3 (a)），ノード n へマイグレーション用処理

値とする．同様に Lprii (t) をプライマリデータのみに対するアクセス負荷値とする．Ti (t) と Tipri (t) は一時変数で，それぞれ Li (t)，Lpri
i (t) で初期化される．

能力を確保するため，ノード n のすべての読み出しアLMAXは事前に測定等から算出された，各ノード i のi

クセスを j へ回送する．ここでノード j の許容最大

許容最大負荷値とする．

負荷値を超えた場合，超過分に相当する j へのアクセ

マイグレーション経路選択アルゴリズム

スをさらにその複製保持ノード k へと回送する．ノーマイグレーションタスクのうちデータ移動元ノード

ド n，j ともに 1 つのマイグレーションタスクの対象を均等に割り当て，各ノード i における割当てマイグの場合（図 3 (b)），両ノードで空き負荷値（許容最大レーションタスク数 si を出力する．

負荷値とノード負荷値の差）が均等になるように回送

Step 1 すべての si を 0 で初期化する．
Step 2 ノード i がマイグレーション戦略において
データ移動先ノードであった場合，インクリ負荷値を決定する．ノード間で異なる数のマイグレー
ションタスクが割り当てられていた場合（図 3 (c)），
空き負荷値の比とタスク数の比が一致するよう回送負荷値を決定する．以上を各ノードに対して行い，現在負荷値に対する回送負荷値の割合を回送率 ri とする．

メントする（si = si + 1）．
Step 3 si > 0 であるすべてのノード i について次のことを行う．

5.2 自律ディスク
我々はこれまで可用性やスケーラビリティに優れた– 該当マイグレーションタスクの 2 つのデータ移動元候補ノードのうち，空き負

高機能並列ストレージシステムとして自律ディスクを− Tki (t)）が大きい方を選
荷値（LMAXki

提案している．自律ディスクでは，Primary-Backupの One-copy21)

複製により障害復旧用バックアップ用

複製データを管理する．このバックアップ用複製デー
タを，Chained Declustering 12) 複製配置戦略に基づきすべてのストレージノード間で鎖状に保持しあうことで信頼性を高めている．
また，データ配置管理に分散 B+ -tree による分散仮+想化機構を有する．各ノードは B -tree 索引構造のある値域の部分木を保持し，データ位置検索に利用する．
そのため格納されるデータ断片についても，一意に定ぶ．ノード ki とする．

– ノード ki の割当てタスク数を 1 増やす：(ski ← ski + 1)．
– ノード ki の負荷値を増やす：（Tki (t) に(LMAX−Tki (t))×(1/{ski (ski +1)}) を
ki
加える）．

Step 4 si を出力する．
本アルゴリズムの計算量は O(N ) となる．
アクセス回送率計算アルゴリズム

められた識別子を与え，対応する索引構造と同じノーマイグレーション経路選択アルゴリズムで得られた
si をもとに，クライアントへのアクセスへの処理能力ドへ格納する，値域分割を採用している．このようなを確保しつつ，マイグレーション対象タスクにより多値域分割と複製配置戦略に対する制約から，あるノー

くの処理能力を確保するため，各ノード i におけるアド n からのマイグレーションは，n に与えられた値域

クセス回送率 ri を出力する．

において最大のデータ識別子を持つデータをデータ識
別子値正方向（n + 1），もしくは最小識別子のデータ

Step 1 （変数初期化）ノード i から i + 1 への回送負荷値 fi を 0 で初期化する．アルゴリズム内を同負方向（n − 1）へ移動する 2 方向のマイグレー

で使用する一時変数 Ti (t) と Tipri (t) を，そションのみとなる（図 4）．

5.3 アルゴリズム
本節では，自律ディスクのデータ配置制約上で 5.1 節

れぞれ Li (t)，Lpri
i (t) で初期化する．

Step 2 ノード番号降順に si を走査し，sj > 0 な
る j を見つけるたびに次の処理をする．変数Vol. 49

No. SIG 7(TOD 37)

並列ストレージにおける長期的負荷均衡化と短期的応答性能の両立

p ← j + 1 とする．
(2a) もし sp > 0 なら（図 3 (b)，(c) のパターン），回送により j と p の空き負35

6. 実 験 概 要
本章以降では，本論文で提案した RM 手法の有効性

荷値比を sj : sp とする：

を検証するために行ったシミュレーションによる実験– fj =

1{(LMAX− Tp (t))sj
max 0, sj +spp

結果を示す．まず本章で，実験設定の概要を説明する．

− (LMAX− Tjpri (t))sp }j

待ち行列ベースの並列ストレージシミュレーションプ
ログラムを構築し，その上で実験を行う．シミュレー– Tp (t) に fj を加える．
– Tjpri (t) から fj を引く．
Step 2 へ戻る．

ション内のシステムに対し時間的に変化するワーク(2b) もし sp = 0 なら（図 3 (a) のパターン），(2b) と (2c) でノード j のアク各手法の応答性能を観測することで，提案手法とそのセス負荷を，マイグレーション非対象

本実験ではまず人工的なワークロードを用いて，異ノード j + 1, j + 2, . . . , p にすべて回なるパラメータ下での挙動を観察し，性能維持効果と送する．その後，途中のノードが溢れ

マイグレーション速度減少率について検証する．実験たら，(2d) と (2e) で回送し過ぎた負では，Zipf 分布に従うアクセス分布とポワソン到着に荷を戻す：

従うアクセス到着率を持つワークロードを発生させマ

pri– fp−1 と Tp (t) に Tp−1(t) を加える．
pri– Tp−1 (t) から Tp−1(t) を引く．

(2c)pri– Tp−1(t) ← 0.
もし Tp (t) > LMAX
かつ s(p+1) = 0pなら（図 3 (a) の j → k のパターン），ロードを発生させ，ある時点でデータマイグレーションによる負荷均衡化処理を発生させた．そのうえで，
他の手法の応答性能保持能力を比較する．

イグレーションの挙動と応答性能の変化を観測する．
2 つ目の実験として，実利用を想定したワークロード下での挙動を観察することで手法の現実システムへの適用可能性を考察する．ここでは，大規模な WEB
サーバから採取されたアクセスログを基にしたワーク
ロードを用いる．

p ← p + 1 とする．Step 2b へ戻る．
(2d) ノード p の許容最大性能を超えている，

6.1 システム構成
待ち行列を利用したイベント駆動型のストレージシ

もしくは回送設定量がノード p のアク

ミュレーションプログラムを構築し，実験に用いた．シ

セス量を超えているなら，余剰分 δp を

ミュレーションはイベントタイマ，イベント，モジュー

ノード (p−1) に戻す作業：もし p > jル，ジョブで構成される．イベントタイマにより起動さかつ，(sp+1 > 0 または Lprip (t) < fp

れたイベントがジョブをモジュールに投入することでまたは Tp (t) > LMAX
) なら，p

シミュレーション時間が進む，イベント駆動型をとる．

––

δp を max(fp − Lprip (t), Tp (t) −LMAX) とする．
ppri
Tp−1(t) と Tp−1 (t) に δp を加
える．

(2e)

– fp と Tp (t) から δp を引く．
もし p > j なら，p ← p − 1 とし，Step 2c へ戻る．

シミュレーションのモジュール構成を図 5 に示す．
シミュレーション内におけるディスクアクセス時間は，

HGST Deskstar T7K250 22) を基にした表 1 に示す
パラメータと前回アクセス時のヘッド位置から計算する．各ストレージノードのネットワークは 800 Mbps

Step 3 (fi /Lprii (t)) を回送率 ri として出力する．
ただし，本アルゴリズムは許容最大負荷値を超える
負荷値を持つノードが回送対象に含まれる場合うまく機能しない．その場合，各ノードの負荷値を均衡化するようなアルゴリズムに切り替える必要がある．本アルゴリズムの計算量は最悪の場合 O(N 2 ) となる．

Step 2b 以下が O(1) となれば O(N ) となる．これは負荷分布に依存する．

図 5 ストレージシミュレーションのモジュール構成
Fig. 5 Module structure of a system on the simulation.

36

Mar. 2008

情報処理学会論文誌：データベース
表 1 シミュレーション構成設定
Table 1 Conﬁguration of storage simulation.

ただし，ディスクの許容最大負荷量を 1 とした．

simulation parametervalue

ディスク回転速度 (RPM)
ディスクサーフェイス数
シリンダあたりのセクタ数
ゾーン数
シークタイム（最長，最短）(msec)
ヘッドスイッチ時間 (msec)

7,200
4
2,520 to 5,184
29
14.7, 0.8
1.4

バッファサイズ (KB)

8,196
4
64
800

ディスクノード数
ノードキャッシュサイズ (MB)ネットワーク速度 (Mbps)

また，WEB ワークロードにおける実験では，ワー
クロード特性からよりキャッシュヒット率が高くネッ
トワークがボトルネックとなった．よって，アクセス
サイズによらず上記下側の式を用いた．

6.2.3 適応的速度制御手法
提案手法に対する比較対象として，適応的速度制御手法である Aqueduct 8) を実装した．Aqueduct は階層型ストレージにおいてデータマイグレーションと応答性能保証の両立を達成する適応的速度制御手法である．Aqueduct では各ノードのレスポンスタイムをで処理可能な FIFO で表現した．ディスクへのアクセ

常時監視し，許容応答性能を超えた場合にマイグレー

スは buﬀer size 単位に分割して行う．キャッシュの追ション速度を動的に減少させることで応答性能維持をい出しアルゴリズムは LRU とした．

達成する．

6.2 手法の実装

Aqueduct では，時間間隔 W ごとに時間ウインド

本実験では提案手法である RM 手法を用いたマイグ

ウ（(k − 1)W ，kW ）における各ノード i の平均レス

レーション（RM），適応的な速度制御を用いたマイグ

ポンスタイム Li (k) を取得する．そして応答性能破綻，および応答性能維持制御
レーション（speed adjust）

指標 Emin (k) を求める：

を行わない通常のマイグレーション（normal）の 3 つを比較する．また，8 章では参考値として，ディスクやEmin (k)= min{P × LCi − Li (k) | 0 ≤ i < N }(2)

ネットワーク処理等をともなわず一瞬でデータ配置を変

ここで，LCi は求める応答性能であり，P はマージ更した，アクセスのないマイグレーション Zero access

ンを表す制御基準係数である．Emin (k) を用いて，次migration（za-mig）の結果を用いる．RM 手法およの時間ウインドウ（kW ，(k + 1)W ）におけるマイグ

び比較対象とする適応的速度制御手法について述べる．

レーション速度比 Rm (k) を更新する：

6.2.1 マイグレーション戦略立案

Rm (k) = Rm (k − 1) + K × Emin (k)負荷均衡化のためのデータマイグレーション戦略については 3 章に示した戦略を実装した．負荷値につ(3)

ここで K は安定化係数である．
以上により得られた Rm (k) を用いて，マイグレー

いては，各データごとに過去 600 秒間のアクセス時間

ション速度を遅延させる．速度遅延はデータ断片 j のとサイズを保持する．サイズは 6.2.2 項において記す

転送ごとに，max(0, W/Rm (k) − Tj ) で表される時間

式 (1) により負荷量に変換する．そして，計測期間でインターバルを挟むことにより実現する．ここで Tj は割った単位時間あたりの負荷量を負荷値とし戦略立案

データ断片 j の転送時間である．
本実験では，W = 2 秒，P = 0.9 を用いた．K にに用いる．

6.2.2 ノード性能
提案手法のアルゴリズムで必要とする，シミュレー

ついては，次章では K = 0.1，1，5，10 の 4 種類を算出す
ション内のディスク 1 台の許容負荷値 LMAXi

い K = 5，10 を用いた．Rm (k) の最小値を 0.1 とるため，予備実験を行った．ディスク 1 台に対し，異し，20 秒以上のインターバルが入らないようにしていなるサイズごとの読み出しリクエストを発生させ応答

る．マイグレーション単位となるデータ断片として，性能を測定した．今回目標とするレスポンスタイムを

1 ファイルを用いた．8 章では性能要件を 1 ブロックあたりとしたため，転送ごとのインターバル時間を，

低負荷時のレスポンスタイムの 10 倍と設定した．そこで，低負荷時の 10 倍を超えるレスポンスタイムを示す平均到着率を用いて，本実験に用いる設定のディスクに対するデータサイズ a [KByte] からアクセス負荷量 l(a) を得る次の式を導出した：

l(a) =

 a×3.4

5.5+ 10
3
a/(96 × 106 )109(a ≤ 800 KB)(a > 800 KB)を用いた．その結果，8 章では速度制御の影響が大き



WB



j
max 0, Rm (k)− Tj とした．ただし Bj はファイル jの構成ブロック数である．

7. 人工的ワークロードによる実験
実験ではまず人工的なワークロード下での挙動を観

(1)

察する．

Vol. 49

No. SIG 7(TOD 37)

並列ストレージにおける長期的負荷均衡化と短期的応答性能の両立

37

表 2 人工的ワークロード実験緒元
Table 2 Speciﬁcation of experiments with synthetic
workload.

workload parametervalue

時間 (hour)read:write
格納ファイルサイズ (GB)2
10:0
100 × 2
(Primary & Backup)
100,000(1 MB each)

格納ファイル数
アクセス分布

Zipf

f = 

1/ks
N

1/ns

Zipf 係数 s
アクセス到着分布
experiment conﬁguration

1.5, 1.2
ポワソン到着
value

アクセス傾向変化時点 (sec)
負荷均衡化開始時点 (sec)
許容最大応答時間 (msec)

600
900
200

図 6 目標レスポンスタイム超過アクセス数の割合（s = 1.5）
Fig. 6 Ratio of violating accesses (s = 1.5).

7.1 環
境
表 2 にワークロード緒元を示す．
実験では，Zipf 分布に従うアクセス分布とポワソン
到着に従うアクセス到着率を持つアクセスをシャッフル関数を用いて格納ファイルに分散する．Zipf 分布は
一部のファイルに多くのアクセスが集中するモデルである．表中の式 f は，N 個のファイルのうち k 番目に多くアクセスされるファイルへのアクセス割合を示し，パラメータ s の値が大きいほど偏りが大きい．そして実験開始 600 秒後にシャッフル関数の乱数種を変化さ

図 7 目標レスポンスタイム超過アクセス数の割合（s = 1.2）
Fig. 7 Ratio of violating accesses (s = 1.2).

せ，アクセス傾向を変化させる．実験開始 900 秒後にマイグレーションによる負荷均衡化を実行する．そのの全体に占める割合を表す．各点は，異なる 3 つの後実験終了までの応答性能およびマイグレーション速

シャッフル関数を用いたアクセス分布における実験結度の変化を観察する．以上の実験を，アクセス偏りの果の平均値である．図 6 より，提案手法により超過度合いを表す Zipf 係数 s が 1.5 の場合と 1.2 の場合

アクセス数が大きく抑えられているのが分かる．仮にについて，アクセス分布を決定するシャッフル関数の5%の超過アクセス数を許容できると仮定した場合，提乱数種およびポワソン到着のアクセス到着率 [req/sec]

案手法の導入によりこのアクセス偏り度合いのもとでを変化させる．そのうえで，各マイグレーション性能システムの負荷耐性が 38%上昇したといえる．一方，保持手法使用時のアクセス応答時間を測定する．
今回の実験における必要性能としては 1 リクエスト

適応的速度制御ではいずれの K に対しても到着率がた．6.2.2 項で述べたように，この値は低負荷時の平120 [req/sec] から 140 [req/sec] を超えた近辺でシス
テム性能が維持できなくなっている．さらに，速度制御の度合い K の値が大きくなるほど性能が劣る．こ均レスポンスタイムのおよそ 10 倍の値を目安とし設の理由については次のマイグレーション時間に関する定した．

評価とともに考察する．

7.2 実験結果 1：応答性能保証
まず，図 6 に大きな偏りのワークロード（Zipf 係
数 s=1.5）での各実験における，目標レスポンスタイ

係数 s = 1.2 とした実験の結果を示す．図 7 は超過
アクセス数の割合である．超過アクセス数の割合が急

ム超過アクセス数（以下，超過アクセス数）を示す．

激に上昇する点におけるアクセス到着率を見ると，どグラフでは横軸にワークロード負荷の大きさであるの手法も図 6 より 30%から 40%程度大きい．よって，アクセス到着率を表し，縦軸に実験におけるレスポン

どの手法もより大きな負荷に対応できていることが分

スタイムが目標値である 0.2 秒を超えたリクエスト数

かる．しかしながら，手法間の差異に関する傾向は変あたりの目標レスポンスタイムを 0.2 秒以下と設定しつづいて，アクセス偏りの度合いがより低い Zipf

38

情報処理学会論文誌：データベース

図 8 1 回目のマイグレーションに要した時間（s = 1.5）
Fig. 8 Duration of ﬁrst data migration in eachexperiments (s = 1.5).

Mar. 2008

図 9 平均レスポンスタイムの時間推移（緩やかな変化の場合）．ア
クセス傾向変化後，各ディスクの負荷がそれまでの（2.2 倍，
1.5 倍，0.5 倍，0 倍）となった場合．負荷集中ノードではアクセス到着率 < アクセス処理率
Fig. 9 Transitional average respons time when workloadchange was mild. Load on each node are increased(2.2, 1.5, 0.5, 0) times. Access arrival rate aresmaller than service rate.

わらず，RM 手法を導入することで，システムが要求性能を維持可能なワークロードの最大値が大きく増加している．しかし，この増加率は 240 [req/sec] から

320 [req/sec] と 33%程度であり，s = 1.5 時よりも低い向上率を示した．偏り度合いが低いアクセス負荷では，負荷集中ノード上のアクセス負荷が低くかつ他のノードの負荷が相対的に高いためである．そのためマ
イグレーションによる性能低下が少なく，アクセス回送率を高く設定できない提案手法の効果が低下したためである．

7.3 実験結果 2：マイグレーション時間
s = 1.5 の実験において，実験開始 900 秒後に発生する 1 回目のマイグレーションがデータ転送に要した時間を図 8 に示す．横軸はアクセス到着率を，縦軸にマイグレーションに要した時間を表す．ただし計測値
は 60 秒単位である．なお，各実験では同じ量のデータ

図 10 平均レスポンスタイムの時間推移（急激な変化の場合）．ア
クセス傾向変化後，各ディスクの負荷がそれまでの（2.7 倍，
1.1 倍，0.2 倍，0 倍）となった場合．負荷集中ノードではアクセス到着率 > アクセス処理率となり平均 5 アクセス/秒
が当該ノードのキューに溜まっていく
Fig. 10 Transitional average respons time when workloadchange was rapid and extensive. Load on eachnode are increased (2.7, 1.1, 0.2, 0) times. Access arrival rate became larger than service rate,
so that ﬁve accesses per second are enqueued thequeue in the node.

がマイグレーションされている．図より，適応速度制
御では K = 1，5，10 の場合 120 [req/sec]，K = 0.1

7.4 実験結果 3：応答性能の推移の場合 140 [req/sec] を超えたところでマイグレーショ

実際の実験中の応答性能の推移を観察する．ここでンが機能しなくなることが分かる．これは，超過アクは特徴的な 2 つの実験について，各手法の応答性能のセスが発生した場合にマイグレーション速度を下げる

変化をみる．グラフ中の応答性能はすべて 1 分間の平処理が働き，マイグレーション処理が止まってしまう

均である．

ためである．速度制御の度合い K の値が大きくなるほ

まず，図 9 に変化が緩やかな場合の応答性能の変化

ど早く速度を下げる．超過アクセスはマイグレーショ

をみる．s = 1.5，アクセス到着率 140 [req/sec] であンだけでなくアクセス偏りによっても引き起こされてる．図より，まず t = 600 においてアクセス傾向の変いるが，アクセス偏りを是正するはずのマイグレー

化により応答性能が若干悪化しているのが分かる．そションを適応的速度制御が止めてしまう．その結果，

して，t = 900 において，RM を除く 2 手法が大きく

アクセス偏りが是正されず超過アクセス数が増加して応答性能を悪化させているのが分かる．これはマイグ

いる．

レーション開始時点である．このように，アクセス傾

図 8 の傾向が図 6 の傾向と酷似していることから向の変化が緩やかであれば，RM 手法により応答性能

もデータ移動速度と応答性能維持の正の相関が見て取を維持しつつマイグレーションを行うことができる．

れる．RM 手法では応答性能維持だけでなく，マイグ

また，図 10 はより大きな変化が起きた場合である．
t = 1.5，アクセス到着率は 140 [req/sec] と同じであレーション時間の削減も同様に達成している．

Vol. 49

No. SIG 7(TOD 37)

並列ストレージにおける長期的負荷均衡化と短期的応答性能の両立

るが，シャッフル関数に用いた値が異なる．t = 600 のアクセス傾向変化ののち，負荷集中ノードのアクセス
到着率がアクセス処理率を上回り，未処理リクエストがキューに溜まり始める．その結果応答性能の悪化が進む．normal では t = 900 から，データマイグレー
ションとクライアントアクセスが資源を取り合いなが

表 3 WEB サーバワークロード構成緒元
Table 3 Speciﬁcation of experiments with real server
workload.

workload parametertime span# of requests
read:write
total ﬁle size

らゆっくりデータ再配置が進行し，応答性能が回復している．一方 RM 手法では，複製保持ノードの処理

39# of total ﬁlesvalue
3 hours
約 20,000,000
10:0
430 MB × h × 2(Primary & Backup)
21,000

能力を使い，応答性能が速やかに回復しているのが分かる．適応的速度制御では，t = 900 時点の応答性能が性能要件を著しく超過しているため，応答性能が要件値を下回るまでマイグレーションを遅延させる．しかし，マイグレーションが行われないことで負荷集中
ノード上のキュー長は伸び続け，応答性能は悪化し続ける．本実験におけるワークロードはポアソン到着に従っており，平均到着率は時間を通して一定としている．よって，負荷偏りが除去されない限りはキュー中のリクエスト数は減少せず，よって，応答性能は改善
せずマイグレーションも行われない．平均到着率が時間とともに変化し，負荷集中ノードにおいてもアクセス到着率が処理率を下回る状態であれば，状況は変化する．そのようなワークロード下での振舞いについては 8 章で紹介する．

図 11 使用したワークロードの傾向．ファイル数を基準にファイル群を 4 分割し，それぞれに対する 1 分ごとの平均単位時間
あたりアクセス要求量（avg）と，5 分ごとの最大単位時間
あたりアクセス要求量（max）の時間変化を示した
Fig. 11 Average quantity of requests per a minute as avg
and max quantity of requests per 5 minutes as max
as a Trend of used workload.

このように，緩やかな変化，急な変化であっても，RM 手法ではシステムを応答性能を維持しつつ迅速に
マイグレーションを行うことが可能となる．

8. WEB サーバワークロードによる実験
本章では，より実際のシステムへ適用した場合に近いワークロードを用いることで，提案手法の性能保持手法の適用可能性を検証する．

的なワークロードを，ファイルサイズおよびアクセス
リクエストサイズを h 倍した複数の設定により実験を行った．これは WEB アクセスログから得られるア
クセス分布，アクセスサイズの相対分布，およびそれら分布の変化速度を維持しつつ，異なる複数のワークロードを実現するためである．
本実験で用いた部分の傾向変化を図 11 に示す．こ

実際のシステムでは前章の実験のような大きなアクの図は，格納ファイルをファイル数が 4 等分となるよセス傾向変化に加え，短期的で突発的なアクセス傾向

う f1〜f4 のグループに分けたとき，それぞれのグルーの変化も含まれる．またアクセスサイズも多様化する

プに属するファイルへのアクセス要求量の時間変化をため，各ノードの振舞いも複雑化する．よって前章の表したものである．それぞれ平均と最大を示した．図

実験に比べアクセス負荷値の見積り精度，ノードごと

中の 4 本の avg 曲線より，このワークロードでは t がの許容最大負荷値精度が低下する．このような条件を5000 から 6000 の間で f2，f3 に大きなアクセス量・比

含む，現実に近いワークロードによる実験より，提案の変化があり，また t = 8000 以降においても f2，f3

手法の性能維持能力への影響を考察する．

間の比に緩やかな変化があることが分かる．また，同

8.1 環境
シミュレーションで用いるシステム負荷は，FIFA
WorldCup98 Oﬃcial WEB サイトから採取されたアことから，f2，f4 に属するファイル中に突発的にアク

クセスログ23) から抽出した．実験ではこのうち 3 時
間分のワークロードを切り出して基本的なワークロー

図の max 曲線において f2，f4 が高い値を示している
セスされるファイルが含まれることが分かる．とくに

t = 10000 での f4-max に注目されたい．
本実験では 60 秒ごとにノード負荷を評価し，ノードとした．詳細を表 3 に示す．ワークロード傾向の

ド間平均負荷が最大許容負荷の 20%以上で，かつある

詳細については文献 24) を参考にされたい．この基本ノードの負荷が平均負荷を 5%以上上回っていたとき

40

情報処理学会論文誌：データベース

Mar. 2008

を変更する，アクセスのないマイグレーション Zeroaccess migration（za-mig）の結果を併記した．za-mig
はシミュレーションプログラム上で動作しているスト
レージシステムにおいて，ある瞬間にデータ配置情報（どのディスクのどのセクタが該当データを格納しているかという情報）をシミュレーション時間を進ませずに書き換えることで実現した．za-mig の結果により，データマイグレーション処理に起因するアクセスによらない超過レスポンス数のおおよその値が確認できる．ただし，マイグレーション処理のアクセスを除去することにより，負荷評価タイミング，データ配置
変更タイミングが変化する等の理由により，アクセスのあるマイグレーションよりも低い性能を示す可能性があることに注意されたい．za-mig は参考値であり，
図 12

目標レスポンスタイム超過アクセス数の割合と za-mig との差（WEB ワークロード）．(a) 超過アクセス数絶対値と zamig の平均応答時間，(b) normal，RM における za-migとの超過アクセス数差，(c) speed adjust（K = 5，10）における za-mig との超過アクセス数差
Fig. 12 Ratio of violating accesses (WEB server workload).
(a) Absolute ratio, (b) diﬀerence from za-mig (RM,
normal), (c) diﬀrence from za-mig (speed adjust).

za-mig との差はデータマイグレーション処理のアクセスに起因する超過レスポンス数ではない．図 12 (a)に za-mig における超過レスポンス数と za-mig における平均レイテンシを併記した．また図 12 (b)，(c)には，za-mig の平均レイテンシが性能要件を超える

h = 44 までの各手法における超過レスポンス数割合の za-mig との差を示した．

に，ノード間負荷を平準化する戦略でマイグレーションが行われることとした．

図 12 (a) より，h ≤ 30 までは，いずれの手法も同様の応答性能を保持していることが分かる．これは実験開始後 1,500 秒後から適応制御を行うこととした．

h ≤ 30 ではノード性能を超えるようなワークロード
集中が散発的であり，各性能維持手法の発動回数が低本実験では実験開始時の負荷均衡状態を，データマイ

いためである．

なお，適応的速度制御については，この実験に限り

グレーション機能を流用して実現している．しかし適

図 12 (b) より，normal では za-mig よりも最大で

応的速度制御を初期状態より有効にし続けると，極度3%程度，全体に占める超過リクエストの割合が増加しに偏った状態である初期状態から通常状態に遷移するている．一方提案する RM 手法では za-mig と同等以ために必要なマイグレーション処理を，適応的速度制下の超過リクエスト数割合を維持している．図 12 (b)

御が止め続けてしまうためである．なお，本実験にお中のそれぞれの正の値の合計を比較すると，RM はける応答性能等の合算値は，実験開始後 3,600 秒後か

normal のおよそ 7%であり，データマイグレーション

らの値を用いた．初期状態へのデータマイグレーショに起因する超過リクエスト数を大きく削減しているこンによる影響を排除するためである．

とが分かる．

本実験における目標レスポンスタイムは，1 ブロック

図 12 (c) より，speed adjust では h = 36 や h = 43

あたり 1 秒と設定した．低負荷時のレスポンスタイム

では大きく超過アクセス数を増加させてしまっているのおよそ 10 倍の値を目安とし設定している（6.2.2 項

ことが分かる．これは負荷均衡化に対して重要なタ参照）．

イミングでのマイグレーションを止めてしまったため

8.2 実験結果 1：応答性能保証である．図 13 に h = 35 における応答性能とイン

図 12 (a) にアクセスサイズ倍率 h ごとの目標レス

ターバルの関係を示す．図 11 で示したとおりアクセ

ポンスタイム超過アクセス数の割合を示す．本論文にス量が増加し応答性能が悪化する．h = 35 ではマイおける着目点はデータマイグレーション処理による超グレーション発動時点が遅く，t = 5500 で性能要件

過レスポンス増加への対処である．しかし図 12 (a) 中値を超えたため適応的にインターバルを増加させる．

の値は，ワークロードの突発的変化等に起因するそれ

インターバルの増加が負荷不均衡を助長するため，応以外の超過レスポンスも含まれる．そこで，ディスク

答性能は悪化し続ける．本実験では h の値ごとにマやネットワーク処理等をともなわず一瞬でデータ配置

イグレーション発動時点が異なる．上記のようなマイVol. 49

No. SIG 7(TOD 37)

並列ストレージにおける長期的負荷均衡化と短期的応答性能の両立

41

ションが実行されたタイミングを表す．
この実験では t = 5100，8100，9600 付近で大きなデータマイグレーションが発生している．なお，
この実験における 3 手法の平均スループットは毎秒

228 MByte で同等であり，いずれの手法もスループッ
図 13 h = 35，K = 10 における平均応答時間とマイグレーショ
ン間インターバル時間の時間推移．
Fig. 13 Transitional average response time and interval
between migration (h = 35, K = 10).

トへの影響はない．
まず t = 5100 付近に注目する．図 14 (b) より，どの手法でも za-mig と比較して応答時間が上昇しているが，RM 手法が 0.1 [sec] と最も小さいことが分かる．
適応的速度制御では，マイグレーションを遅延させた
結果，t = 8000 付近までマイグレーションが継続し，

t = 6000 付近で応答性能の悪化を引き起こしている．
t = 8100 付近では，RM 手法以外では za-mig と比較して応答性能を悪化させている一方，RM 手法では複製ノードを用いて応答時間が削減されている．
なお，t = 10000 付近の急激な応答時間上昇は，図 11の f4-max より，アクセス負荷の突発的な変化に起因するもので，本論文の対象範囲外の挙動であることに注意されたい．また，RM や speed-adjust の手法がマイグレーションを行っていない（速度制御や複製利用を行っていない）にもかかわらず，za-mig が相対的に悪くなっている．これは，この直前までのアクセス傾向に za-mig でのデータ配置がよりよく合致していたため，突発的で過去の傾向から逸脱したアクセスに
図 14

h = 40 における各手法の時間推移．(a) 絶対的平均応答時
間の時間推移，(b) za-mig との平均応答時間差の時間推移と各手法のマイグレーション実行タイミング
Fig. 14 Transitional average response time (WEB server
workload). (a) response time (absolute), (b) diﬀerence of response time from za-mig and migration
execution timing.

よる応答時間の上昇が顕著だったためと考えられる．
このように，za-mig はマイグレーション処理に起因するアクセスを除去してあるが，必ずしも理想的性能を示すものではない．
このように，データマイグレーションによる一時的な応答性能悪化は通常の運用で起こりうることである．
提案する RM 手法を用いることで，データマイグレー

グレーション中の負荷不均衡が 1 度でも起きた場合，ションに起因する応答性能悪化を大幅に削減すること

適応的速度制御がマイグレーション機能をずっと停止が可能となることが示された．

させ続けてしまう．しかし，人工的ワークロードによる実験と異なり，h = 39，h = 40 では speed-adjust

9. ま と め

でも超過アクセス数を削減できている．これは，人工高機能並列ストレージシステムでは，負荷均衡化の的ワークロードと異なり WEB ワークロードはアクセためのデータマイグレーションに起因する一時的な応

ス量が時間とともに変化するためである．マイグレー

答性能低下が存在する．本論文ではデータマイグレー

ションを遅延させることで，ワークロードの小さくな

ション時においても要求される応答性能を達成するたるタイミングのノード資源を効率良く利用できているめの手法 Replica-assisted Migration（RM 手法）を場合もある．

提案した．本手法では，マイグレーション経路選択と8.3 実験結果 2：応答性能の時間変化

アクセス回送の 2 手法に複製を利用する．提案する

マイグレーション発生時の応答性能の変化を観測

RM 手法では 2 手法を，ストレージノードの最大許容する．図 14 (a) は h = 40 における，それぞれの手負荷情報をもとに，負荷集中ノード，マイグレーショ法使用下の応答性能変化の推移を表している．また，ン対象ノード，そしてそれらの複製保持ノードそれぞ

図 14 (b) は za-mig との差を，図 14 (c) はマイグレー

れが性能要件を維持可能な許容最大負荷以下の負荷で42

情報処理学会論文誌：データベース

動作可能となることを目指し複製制御を行う．そのため極端な負荷集中後においても性能要件を維持しつつ迅速なデータマイグレーションを実現する．
人工的なワークロードを用いた実験により RM 手法と適応的速度制御手法を比較した．その結果，読み出しアクセス中心のワークロード下においては，これまでのシステムでは対応できなかった高負荷・高負荷偏り
環境下においても高い性能維持能力を確認できた．また，現実に近いワークロードとして大規模 WEB サー
バのアクセスログを用いた実験から，提案手法の現実のシステムへの実現可能性も示された．
今後の課題として，更新要求の取扱いは重要である．
提案手法のうち，経路選択による効果はデータ挿入・
更新要求混在時でも得られるが，アクセス回送は難し
い．より柔軟なデータ配置制御，WAL やライトバッ
クキャッシュによる書き込み負荷の軽減を組み合わせることで，このような問題に対処することを検討している．またストレージノード性能の見積りの簡素化・自動化は重要な要素である．今回の実験では，予備実
験の結果等からノード性能の上限を算出した．これらの値をより高い精度で推定可能な手法を考案することで提案手法の効果はさらに高まると考える．加えて，この性能見積り手法を改良することで本提案手法の異機種混在環境へ拡張することも検討している．
突発的なアクセス負荷上昇への対処や，アクセス回送常用化と本提案手法の併用については本論文の対象外としたが，重要な課題と考えられる．また，より詳
細な手法評価として標準的なベンチマークツール等，より一般的な環境への有用性評価は重要である．以上の課題を達成したうえで，堅牢でディペンダブルな並列ストレージシステムの構築に関する検討を進めていきたい．
謝辞 本研究の一部は，独立行政法人科学技術振興
機構戦略的創造研究推進事業 CREST，独立行政法人
日本学術振興会科学研究費補助金特別研究員奨励費，情報ストレージ研究推進機構（SRC），文部科学省科学研究費補助金特定領域研究（18049026，19024028）
および東京工業大学 21 世紀 COE プログラム「大規模知識資源の体系化と活用基盤構築」の助成により行
われた．

参

考 文

献

1) Yokota, H.: Autonomous Disks for Advanced Database Applications, Proc. International Symposium on Database Applications in
Non-Traditional Environments (DANTE’99 ),Mar. 2008

pp.441–448 (1999).
2) Frølund, S., Merchant, A., Saito, Y., Spence,
S. and Veitch, A.: FAB: enterprise storage systems on a shoestring, HOTOS 2003, Kauai, HI(2003).
3) Ganger, G.R., Strunk, J.D. and Klosterman,
A.J.: Self-* Storage: Brick-based Storage with
Automated Administration, Technical Report
CMU-CS-03-178, Carnegie Mellon University(2003).
4) Simitci, H.: Storage Network Performance
Analysis, Wiley Technology Publishing (2003).
5) Weikum, G., Mönkeberg, A., Hasse, C. andZabback, P.: Self-tuning Database Technology
and Information Services: from Wishful Thinking to Viable Engineering., VLDB, pp.20–31(2002).
6) Feeliﬂ, H., Kitsuregawa, M. and Ooi, B.: A
Fast Convergence Technique for Online Heatbalancing of Btree Indexed Database over
Shared-nothing Parallel Systems, 11th Int’l
Conf. on Database and Expert Systems Applications, pp.846–858 (2000).
7) Dasgupta, K., Ghosal, S., Jain, R., Sharma,
U. and Verma, A.: QoSMig: Adaptive RateControlled Migration of Bulk Data in Storage Systems, the 21st International Conferenceon Data Engineering (ICDE2005 ), pp.816–827(2005).
8) Lu, C., Alvarez, G.A. and Wilkes, J.:
Aqueduct: online data migration with performance guarantees, Conference on File andStorage Technologies (FAST’02 ), Monterey,
CA, pp.219–230 (2002).
9) Zhang, J., Sarkar, P. and Sivasubramaniam,
A.: Achieving completion time guarantees
in an opportunistic data migration scheme,
SIGMETRICS Perform. Eval. Rev., Vol.33,
No.4, pp.11–16 (2006).
10) 小林 大，渡邊明嗣，山口宗慶，田口 亮，上原年博，横田治夫：複製データを併用した効率的なデータマイグレーションの検討，日本データベー
ス学会 Letters，Vol.3, No.2, pp.65–68 (2004).
11) Scheuermann, P., Weikum, G. and Zabback,P.: Data Partitioning and Load Balancing in
Parallel Disk Systems., VLDB J., Vol.7, No.1,
pp.48–66 (1998).
12) Hsiao, H.-I. and DeWitt, D.J.: Chained
Declustering: A New Availability Strategy for
Multiprocessor Database Machines, Proc. 6th
International Conference on Data Engineering, Los Angeles, CA, IEEE Computer Society,pp.456–465 (1990).
13) Lumb, C.R., Merchant, A. and Alvarez, G.A.:

Vol. 49

No. SIG 7(TOD 37)

並列ストレージにおける長期的負荷均衡化と短期的応答性能の両立

Façade: Virtual Storage Devices with Performance Guarantees, 2nd USENIX Conference
on File and Storage Technologies (FAST’03 ),pp.131–144 (2003).
14) Kistler, J.J. and Satyanarayanan, M.: Disconnected operation in the Coda File System, ACM Trans. Comput. Syst., Vol.10, No.1,
pp.3–25 (1992).
15) Saito, Y. and Levy, H.M.: Optimistic Replication for Internet Data Services, Distributed
Computing, 14th International Conference(DISC ), Toledo, Spain, pp.297–314 (2000).
16) 原 隆浩，春本 要，塚本昌彦，西尾章治郎，
奥井 順：広帯域ネットワーク上のデータベース
移動に基づく動的複製配置法，電子情報通信学会論文誌，Vol.J-82-D-I, No.8, pp.1049–1058 (1999).
17) Wolf, J.L., Yu, P.S. and Shachnai, H.:
Disk Load Balancing for Video-On-Demand
Systems, Multimedia Systems, Vol.5, No.6,
pp.358–370 (1997).
18) Lumb, C.R., Golding, R. and Ganger,
G.R.: DSPTF: Decentralized Request Distribution in Brickbased Storage Systems, Proc.
ASPLOS’04, Boston, MA (2004).
19) 小林 大，渡邊明嗣，田口 亮，上原年博，横田治夫：データ移動コストとキャッシュを考慮した
複製へのアクセス分散制御，日本データベース学会 Letters，Vol.4, No.1, pp.125–128 (2005).
20) 渡邊明嗣，横田治夫：分散ディレクトリ探索コ
ストを考慮した並列データアクセス偏り制御，電子情報通信学会和文論文誌 DI，Vol.85-DI, No.9,
pp.877–886 (2002).
21) Bernstein, P.A. and Goodman, N.: An Algorithm for Concurrency Control and Recovery in Replicated Distributed Databases, ACM
Trans. Database Syst., Vol.9, No.4, pp.596–615(1984).
22) Hitachi Global Storage Technologies: Deskstar
T7K250 Hard Disk Drive Specification, ver. 1.7
edition (2006). http://www.hitachigst.com
23) Lawrence Berkeley National Laboratory: The
Internet Traﬃc Archive. http://ita.ee.lbl.gov/

4324) Arlitt, M. and Jin, T.: Workload Characterization of the 1998 World Cup Web Site, Technical Report HPL-1999-35R1, Hewlett-Packart
Laboratories (1999).
(平成 19 年 9 月 20 日受付)
(平成 20 年 1 月 13 日採録)
（担当編集委員

片山 紀生）
小林大2003 年東京工業大学工学部情報工学科卒業．2005 年東京工業大学
大学院情報理工学研究科計算工学専
攻修士課程修了．現在，同専攻博士後期課程在学中．2006 年より日本学術振興会特別研究員 DC．並列ストレージシステム，
データ工学等の研究に従事．日本データベース学会学生会員．
横田 治夫（正会員）

1980 年東京工業大学工学部電子物理工学科卒業．1982 年東京工業大学大学院理工学研究科情報工学専
攻修士課程修了．同年富士通（株）．
同年 6 月（財）新世代コンピュータ
技術開発機構研究所（ICOT）．1986 年（株）富士通研究所．1992 年北陸先端科学技術大学院大学情報科学研究科助教授．1998 年東京工業大学大学院情報理工学研究科助教授．2001 年東京工業大学学術国際情報センター教授．工学博士．主として分散インデキシン
グ，データ工学向けアーキテクチャ，高機能ストレー
ジシステム，ディペンダブルシステム等に関する研究に従事．電子情報通信学会フェロー．日本データベース学会理事．人工知能学会，IEEE，ACM 各会員．