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

分散ストレージシステム上での複製を含むデータの分割配置とアクセ
ススケジューリング

Title(English)

Access Scheduling for Dynamic Allocatable Striping Data and Replicas
on a Distributed Storage System

著者(和文)

片居木誠, 小林大, 吉原朋宏, 小林隆志, 田口亮, 横田 治夫

Authors(English)

Makoto Kataigi, Dai KOBAYASHI, Tomohiro YOSHIHARA, Takashi
KOBAYASHI, Ryo Taguchi, Haruo YOKOTA

掲載誌(和文)DEWS2006 論文集

Citation(English)

Proc. of DEWS2006

Vol, no, pages

Vol. , No. , pp. 7C-o5

発行日 / Pub. date

2006, 3

URL

http://search.ieice.org/

権利情報 / Copyright

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

Powered by T2R2 (Science Tokyo Research Repository)

DEWS2006 7C-o5

分散ストレージシステム上での複製を含むデータの分割配置とアクセス
スケジューリング片居木 誠†

小林大††

吉原 朋宏††
横田小林 隆志†††

田口亮 ††††

治夫†††,††† 東京工業大学 工学部 情報工学科†† 東京工業大学 大学院情報理工学研究科 計算工学専攻††† 東京工業大学 学術国際情報センター, † † †† NHK 放送技術研究所
E-mail: {{mkataigi,daik,yoshihara}@de,tkobaya@,yokota@}cs.titech.ac.jp, taguchi.r-cs@nhk.or.jp
あらまし

我々はこれまで分散ストレージシステムにおける負荷分散，容量分散，耐故障，規模変更等を行う様々な

自律的な管理機能について研究を行ってきた．その際，これらの機能を実現する処理や戦略を単純化するため，アクセス単位となる対象の 1 つのオブジェクトが 1 つのストレージ装置に格納されることを前提にしていた．一方，近年，高精度のマルチメデ ィアストリームオブジェクトなどの増加により，ストレージシステムに対する安定した高速アクセスの要求が高まっている．この要求を満たすためには，複数の分散ストレージ装置にまたがるストライピングが必要となる．しかし，従来の RAID で用いられているストライピングはマルチメデ ィアストリームオブジェクトには適さない．本稿では，安定した高いスループットの分散ストレージシステムを実現するため，これまでの研究を拡張して，負荷を考慮した動的な配置を行うストライピング戦略に関して検討を行う．また，スループット改善のために，ストライピングされた複製に対するスケジューリング戦略に関しても検討を行う．さらに，我々が提案している自律デ ィスク上に実装し，実験によりそれらの効果を評価する．
キーワード

複製， 並列・分散 DB， ストレージシステム， ストライピング

Access Scheduling for Dynamic Allocatable Striping Data and Replicas on aDistributed Storage System†††††
Makoto KATAIGI , Dai KOBAYASHI , Tomohiro YOSHIHARA ,Takashi KOBAYASHI†††, Ryo TAGUCHI††††, and Haruo YOKOTA†††,††† Dept. of Computer Science, Faculity of Engineering, Tokyo Institute of Technology†† Dept. of Computer Science, Grad. School of Info. Sci. and Eng, Tokyo Institute of Technology††† Global Scientic Information & Computing Center, Tokyo Institute of Technology† † †† NHK Science & Technical Research Laboratories
E-mail: {{mkataigi,daik,yoshihara}@de,tkobaya@,yokota@}cs.titech.ac.jp, taguchi.r-cs@nhk.or.jp
Abstract

We have studied many functions to realize the distributed autonomous storage management, such as workload bal-ancing, data amount balancing, failure recovery and online reconstruction. To make processes and strategies in these functions
simple, we assumed that a target object was stored into a storage device. Recently, the demands for stable and high-speed
accesses to storage systems have risen according to the increase of high-denition multimedia stream objects. To satisfy therequirement, the object should be striped across multiple storage devices. However, the ordinary striping technique used in
RAIDs are not suitable for the multimedia stream objects. In this paper, we consider a workload-aware dynamic allocatablestriping strategy to provide stable and high-speed access to a distributed storage system by enhancing our previous research.
We also consider a scheduling strategy of using striped replicas to improve system throughput. We then evaluate these strategies using an experimental autonomous disk system we proposed.
Key words

Replica, Parallel Distributed DB, Storage System, Striping

1.

はじめに

トライピングに対する，負荷均衡化，容量均衡化，耐故障化，規模変更機能の実現と位置づけられる．

近年，コンピュータシステムで使用されるデータ量が増大ししかし，ストレージ装置間にまたがるストライピングを行う

続けている．このため，HDD に代表されるストレージ装置を多場合には，ストレージ装置単位で負荷や容量を計算するだけで数結合することで大容量でかつ信頼性の高いシステムを安価には不十分であり，プ ライマリ・バックアップによる耐故障化，構成する方法が取られることが多い．しかし，ストレージ装置

規模変更もこれまでの方法をそのまま適用することはできない．

数や記憶容量が増えることで，システムが複雑化し，データ管

複数のストレージ装置の負荷や容量が密接に関連して変化する

理が煩雑化するため，アクセス QoS の保証，容量割当て，デーことを想定した場合の，負荷均衡化，容量均衡化，耐故障化，

タ冗長性の管理等の管理コストの増大が問題となっている．

規模変更機能を一時に実現することは非常に難しい．

この問題に対し，各ストレージ装置毎に計算処理能力を持た

本稿ではまず，アクセス傾向が大きく変化しないという前提

せるストレージシステムにおいて，その計算処理能力をデータを置いた上で，ストライピングのために分割したデータを配置

管理に利用する試みが行われている [14]．我々も，ストレー

するプリミティブな配置手法の実機実験による性能評価を行う．

ジ装置毎に持つ計算処理能力を用いて負荷均衡化，容量均衡化，また，バックアップを耐故障化に用いるだけでなく，ストライ

耐故障，および柔軟な規模変更の機能を実現する研究を行ってピング時のスループット向上に利用する可能性を調べるために，きた [59]．

プライマリデータだけでなくバックアップデータからも読み出

これまで我々は，アクセス単位となるある 1 つのオブジェク

すよう，コネクション数に注目したプライマリ・バックアップ

トがいずれか 1 つのストレージ装置に格納されることを前提に，間の読み出し比率調整を行う手法を提案し，実機実験によってオブジェクトをストレージ装置間で移動させることで，負荷均評価する．

衡化，容量均衡化，プライマリ・バックアップによる耐故障化，規模変更機能の実現を試みてきた．1 つのオブジェクトの格納を 1 つのストレージ装置内に限ることで，負荷，容量の配分の

2.

関連研究

近年多くの スト ラ イピング 法が 研究されている．例えば ，計算や戦略を単純化することができ，耐故障処理や規模変更に

RAID0+1 や RAID1+0，擬似ランダムハッシュ関数を使ったスも柔軟性を持たせることができた．

トライピング [13]，スタガード ストライピング [14] などが提案

一方，近年の高精度のマルチメディアオブジェクトなどの増されている．

加で，ストレージ装置中のオブジェクトごとに高いスループッ

スト ラ イピ ン グ お よび ミ ラ ー リン グ を 使 う 方 法で あ る

トが求められるようになってきている．特に，オブジェクトのRAID0+1 や RAID1+0 は 高速な 読み 出し と ミラー リング に種類も多様になっているため，オブジェクト毎に異なるスルー

よる冗長化を両立した手法である．しかし，ともに RAID の問

プットが求められるようになってきている．しかし ，オブジェ

題点である分割されたデータの配置が固定であるという問題点

クトを 1 つのストレージ装置内だけで格納していては，そのスがある．そのため，オブジェクト毎に柔軟なスループットに対トレージ装置単体のスループット以上の性能を実現することは応させることができず，システム拡張時にも問題が生じる．

できない．

擬似ランダムハッシュ関数を用いたストライピングは，擬似ストレージ装置単体以上の高いスループットを実現するためランダムハッシュ関数を再計算することにより分割されたデーには，RAID 0， 3〜6 などのようなストライピングを行う必要

タの配置を自由に変更することが可能な手法である．しかし ，がある [1012]．しかし ，これまでの RAID に代表される分割

大量の分割されたデータの配置を同時に変更する際の擬似ランされたデータの配置が固定されるストライピングでは，大規模ダムハッシュ関数の再計算コストが非常に高く，オブジェクト

構成において，負荷均衡化，容量均衡化や柔軟な規模変更，さ毎の柔軟な管理ができないという問題点がある．

らにオブジェクト毎に異なるスループットに対応させるようなスタガード ストライピングは安定した高速読み出しを行うこ

柔軟な管理を行うことが容易ではい．また，RAID 3〜6 で用いとができ，オブジェクト毎に違うスループットが適用できるス

られるようなパリティ計算に基づく耐故障化では，データ回復

トライピング法である．しかし，分割されたデータの自由な配のために複数ストレージ装置にまたがるパリティ計算を行わな

置ができないため，耐故障処理や規模変更時に，全データの構

くてはならないため，故障発生時においても安定した転送レー成を変更しなければならないという問題がある．

トを保ちながらスト リーミングを行うという QoS を保証する
ことが困難である．
そこで，本研究では一部のストレージ装置が故障した場合も含めオブジェクト毎に柔軟に高いスループットで安定したデー

3.

前提となるシステム

3. 1

用語定義

本稿において用いる用語を以下に定義する．

タ供給を行うことを目的として，これまで行ってきたストレー

分散ストレージシステム

ジ装置単位のオブジェクトに対する負荷均衡化，容量均衡化，システム全体がネットワークでつながれており，各ストレージ

プライマリ・バックアップによる耐故障化，規模変更機能をスが別々に動作することが可能であるストレージシステム

トレージ装置間にまたがるストライピングに拡張する方法を考

アクセスえる．これは，分割されたデータの配置を動的に変更可能なス

読み込みあるいは書き込みリクエストを送り，それに対してシ

複数のストレ ージ装置で構成され ，クライアントがストレージシステムに対して単一のステムがファイルの保存場所を返し，その保存場所に対してク57698;:=<

ライアントがファイルの送信または受信を行う一連の動作をいう．アクセスが行われているとき，その対象となるファイルが置いてあるストレージのアクセス数が 1 であると定義する．
フラグメント$

固定長に分割されたデータ，このデータがスト






ライピングの最小単位になる．
サブオブジェクト

同じ ストレージ上に配置された元が同じオブジェクトであるフラグ メントの集合
3. 2

自律ディスク 1324' + & ')(*',+ .%
( 


"!



( 0/ '  '

# 
#



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

図 1 任意配置の構成

我々は負荷均衡化，容量均衡化，耐故障，柔軟な規模変更など の機能を持つ分散ストレ ージシステムとして自律ディス
ク [5, 15] の研究を行ってきた．自律ディスクとは高機能な分散ストレージシステムの 1 つである．自律デ ィスクにおいては，各オブジェクトは値域分割により配置ストレージが決定される．
また，それぞれのストレージがシステム内のいかなるデータへのアクセス要求にも対応するために，各ストレージが分散索引
構造 [16, 17] を持っている．このようなシステムで，負荷均衡化，容量均衡化，耐故障，柔軟な規模変更を以下の手順で自律的に行う．
負荷均衡化 システム内の値域が隣のストレージとの負荷を比較し，負荷の多いストレージから少ないストレージへデータを移動させることにより，システム内の各ストレージの負荷を均衡化させる．
容量均衡化 システム内の値域が隣のストレージとの容量を比較し，容量の多いストレージから少ないストレージへデータを移動させることにより，システム内の各ストレージの容量を均衡化させる．
耐故障

スタガード 割り当て [18] によるバックアップを持ち，故障発生時に以下の手順で障害復旧を行う．
（ 1 ） 故障し たストレ ージ上のプ ライマリデ ータに対するバックアップデータをプライマリデータにする．
（ 2 ） (1) のプライマリデータと故障したストレージ上のバッ
クアップデータに対するプライマリデータのバックアップを作
成する．
（ 3 ） 負荷分散および容量分散を行う．
柔軟な規模変更 新しいストレージが追加されたとき，システ
ム中の全ストレージに対し，新しいストレージが追加されたという情報を送信し，負荷分散および容量分散を行う．
自律ディスクは以上の機能をクライアントに対して透過的に行うシステムである．
4.

サブオブジェクト 配置法

る．また，ストライピングにおいてスループットはオブジェク
トの分割数によって決定される．そのため，要求スループットの違うオブジェクトを柔軟に管理するためにはオブジェクトごとに分割数を柔軟に変更できる必要がある．
そのため，本稿では自律ディスクに対して負荷均衡化，容量均衡化，耐故障，柔軟な規模変更を実現可能で，要求スルー
プットの異なるオブジェクトを柔軟に管理がすることが可能であるストライピング法を適用する．
4. 1

任意配置の構成法

まず最初に要求スループットに応じて分割数を決定する．その後，分割数に応じてフラグ メントを配置するストレージを選択する．選択したストレージ上にラウンド ロビン形式でフラグメントを配置する (図 1)．ここで同じオブジェクトの同じ スト
レージ上のフラグ メントをサブオブジェクトとする．そして，
そのサブオブジェクトを配置するストレージの情報を管理するために索引構造中に新しいデータを作成する (この索引構造中のデータを分割情報データと呼ぶ)．
このように配置することにより，サブオブジェクトを配置する場所が限定されていないため障害復旧や規模拡張を問題なく行うことができる．また，オブジェクトの移動を行う際も，移動場所の計算はサブオブジェクトごとに行えばよいため計算コ
ストはフラグ メント単位で管理する場合に比べ少ない．さらに，サブオブジェクト数を調整することによりオブジェクトごとに違うスループットを提供することも可能である．
4. 2

サブオブジェクト の配置

4. 1 のような配置の場合，読み出し速度は最も遅いストレー

ジによって決定されるため，少数のストレージにアクセスが集中する場合，全体として読み出し速度が低下するという問題が生じる [19]．よって，サブオブジェクトを無計画に配置させた
場合，アクセスが多いオブジェクトのサブオブジェクトが同じ
ストレージに配置され，一部のストレージの読み出し速度が遅くなる．そのため，少数のストレージにアクセスを集中させな

フラグ メント同士の位置関係が固定であるストライピング法
では，一部のフラグ メントの配置を変更する際に，他のフラグ
メントの配置も変更する必要がある．そのため，障害復旧や規模拡張を行うときに問題が生じる．フラグ メント同士の位置関係が固定でないストライピング法でも，フラグ メント単位で配置を決める配置法では，負荷均衡化や容量均衡化処理を行う時にフラグ メントの移動先をフラグ メントごとに計算しなければならない．そのため，計算コストが高くなるという問題が生じいためのサブオブジェクトの配置法が不可欠である．またサブ
オブジェクトの配置は一度決定してしまうと，移動するためには非常にコストがかかる．そのため，配置をする瞬間だけでな
くそれ以降のアクセスも考慮に入れたサブオブジェクト配置法が必要である．
これらの理由により，我々は長期的スパンにおけるアクセス分散を目指し，過去のストレージ上のデータへのアクセス状況  

によって配置場所を決定するアルゴ リズムを用いる．なお，長期的なスパンでのデータへのアクセス傾向の変化はないと仮定! "$#&%

している．長期的に見てデータへのアクセスが多いストレージはある瞬間においてもそのストレージ上のデータへのアクセス       

が行われている可能性が高い．また，将来的にもストレージへのアクセスが多い可能性が高い．よって，過去にデータへのア

クセスの多いストレージにデータを配置すると，そのストレー')(+*-,

ジへのアクセス数が増える．そのため，過去のデータへの読み
書き量の多いストレージにサブオブジェクトを配置することは避けるべきである．

図 2 アクセス数に応じた読み出し量以上のことにより，次のような並列ストレージシステムにおいて少数のストレージにアクセスが集中しないようなサブオブ

なお以下ではバックアップは常に最新であることを仮定する．
読み出し 時間の最小化

ジェクト配置場所決定アルゴ リズムを用いる．分割情報データ

5. 1を配置したストレージがアルゴ リズム中で用いるサブオブジェ

バックアップは必ずプライマリと別のストレージ上に存在す

クト配置可能ストレージのアクセス数情報 (アクセス数リスト )る．そのため，プライマリだけでなくバックアップも読み出しを取得し ，サブオブジェクト配置決定法によってサブオブジェに利用することによって，読み出し時間を減少させることが可

クトの配置場所と各サブオブジェクトに含まれるフラグ メント

能である．しかし，プライマリオブジェクトの置いてあるストの決定を行う．

レージとバックアップオブジェクトの置いてあるストレージのサブオブジェクト 配置決定法
input:

サブオブジェクト数：n

フラグ メント数：k
サブオブジェクト配置可能ストレージ台数： M(> n)
各ストレージのアクセス数リスト： AD[M]output:フ ラ グ メン ト 配 置 スト レ ー ジ ID リ スト：

f ragment s[k]Step1:

AD[M] 中のアクセス数が少ないほうから n 台

選び，そのストレージのリスト S ubob ject s[n] を作成．
Step2:i ∈ [0, k] に対して j = i mod n，f ragment s[i] = S ubob ject s[ j] とする．
Step3:

f ragment s[k] を out put して終了

アクセス数が異なるとき，プライマリオブジェクトとバックアップオブジェクトの読み出し速度は異なる．このとき，読み出し時間を最小化するためには図 2 のように，プライマリ・バック
アップ間で読み出し割合を変える必要がある．
まず読み出し時間を最小化する読み出し割合を求める．

•

プライマリストレージの読み出し速度 v p•

バックアップストレージの読み出し速度 vb•

プライマリオブジェクト読み出し割合 α•

オブジェクトのサイズ S•

プライマリ読み出し時間 T P•

バックアップ読み出し時間 T b

このときプライマリ・バックアップのそれぞれの読み出し量と読み出し時間の関係は，

上記のように，過去のアクセスが多いストレージへのサブオブ

プライマリ ： αS = T p · v p

ジェクトの配置を避け，アクセスの少ないストレージへ配置さバックアップ ： (1 − α)S = T b · vb

せる．このアルゴ リズムは，すでにアクセスが多いストレージのアクセスを増やさず，アクセスの少ないストレージのアクセ
スを増やすため，システム全体でディスク間のアクセス数を均等化し，長期的なスパンでのストレージ間でのアクセスの分散を行うことが可能である．
5.

複製アクセススケジューリング

また，4. のサブオブジェクト配置アルゴ リズムに加え，バッ
クアップを読み出しに利用することによって読み出し速度を向上させることが可能である．しかし，ストレージ装置の読み出
し 速度はそれぞれのストレ ージへのアクセス数により変わる
ため，プライマリデータの存在するストレージとバックアップ
データの存在するストレージの読み出し 速度は同じではない．
そのため，読み出しを行う瞬間に速度が違う場合に，読み出し時間を最小化するためにプライマリとバックアップの読み出し量をコネクション数に応じて変更する方法を提案する．

(1)
(2)

となる．このとき読み出し 時間 T = max{T p , T b } が最小になるのは，プライマリとバックアップの読み出し時間が等しいとき，
つまり

α=

vp
v p + vbのときである．よって，v p と vb を取得することができれば読み出し時間を最小化できる．
5. 2

コネクション数の比による読み出し 量決定

読み出し速度に大きな影響を与える要因として，同時読み出
し数が考えられる．そのため，読み出し速度と同時読み出し数の関係を調べるため補助実験を行った．その結果が図 3 である．
図 3 より分かるとおり，同時読み出し数と読み出し速度には一定の関係がある．実際図 3 の結果はv =kaccess number(3)であり，同時読み出し数と読み出し速度が反比例することを示

*

5. 4



5. 2 または 5. 3 を用いて読み出し時間を最小にするプライマ

アルゴ リズム中ではサブオブジェクト配置ストレージの情報が

!

"


リ・バックアップ読み出し量決定法を提案する．なお，以下の


')(
&
$%#



必要なため，分割情報データが配置されているストレージが以!


読み出し 量決定法



下のアルゴ リズムを行うとする．


プライマリ・バックアップ読み出し 量決定法














input

プライマリストレージのコネクション数 ： L p

バックアップストレージのコネクション数 ： Lb

図 3 補助実験：同時読み出し数とアクセス速度

サブオブジェクト中のフラグ メント数 ： k
している．なお k は係数である．また， access number = 1 としたとき v = k となるため，k はそのストレージの読み出しの最大速度である．さらに同時読み出し数はそのときのデ ィスクへのコネクション数に等しい．よって，この関係式を用いて最プライマリストレージのコネクション数 L p•

バックアップストレージのコネクション数 Lb

バックアップ読み出し速度 vb = k/Lb

(4)
(5)

式 (5. 1) に式 (4) と式 (5) を適用させることにより係数 k ，つまバックアップ読み出し率 Rb =L p + Lb
Lp
L p + Lb

プライマリサブオブジェクトの読み出しフラグ

バックアップサブオブジェクトの読み出しフラグ メン

り最高速度によらずによらず，
Lb

フラグ メント 読み出し ストレ ージ ID リスト：

メント数 S p = F(L p , Lb )となる．このとき，読み出し 時間を最小化する読み出し 量は，プライマリ読み出し率 R p =読み出し量計算関数 ： F(L p , Lb )outputStep1:とする．このときの読み出し速度はそれぞれ，
プライマリ読み出し速度 v p = k/L p

バックアップストレージ ID ： Ib

List[k]

適な読み出し量を計算することができる．

•

プライマリストレージ ID ： I p

(6)

(7)

ト数 S b = F(L p , Lb ) を計算する．
Step2:

pos = 0

Step3:i ∈ [ pos, pos + S p ] について List[i] = I p とする．

Step4:pos= pos + S p こ こで pos > k と なったらStep7 へStep5:i ∈ [ pos, pos + S b ] について List[i] = Ib とする．

Step6:

pos = pos + S b ここで pos > k となったら Step7

へ， pos <= k ならば Step3 へ
Step7:

List を out put して終了

プライマリ・バックアップ読み出し量決定法により，その瞬となる．よって，速度がコネクション数に反比例する場合，最間のコネクション数が多い読み出しの遅いストレージからの読高速度によらず式 (6) と式 (7) から読み出し 時間を最小にする

み出しを少なくし，コネクション数が少なく読み出しの速いス

読み出し割合が求められる．

トレージからの読み出しを多くすることによって，全体での読

5. 3

過去の読み出し 実績による読み出し 量決定

み出し時間を最小化することができる．

式 (3) は特定環境に依存したものであり，実際の式は環境によって変わってくる．そのため，より一般的な速度予測法が必要である．
通常，同じ ストレ ージで同じ コネクション数であれば スト

6.

実

験

6. 1

実験環境

PC クラスタ上に実装して実験を行った．実験システムの構

レージ故障以外で速度が変化することはない．そのため，以前

成は表 1 に示す PC をクライアントとなるストレージとして 4に読み出しが行われた際のコネクション数とそのときの読み出台，分散ストレージとなるストレージとして 8 台用い，それぞし速度を履歴として取得しておくことによって将来の読み出し

れがお互いにネットワークで接続されている．

速度予測にも使用できる．

実験方法は，以下の通りである．まず各クライアントがそれ

よって過去の履歴からコネクション数と読み出し速度のテー

ぞれファイル読み出しまたは書き込みを行った．このとき，最ブルを作成し，新しいアクセスがあった瞬間のコネクション数

初に初期構成作成のために計 100 回ファイル送信を行い，アクをそのテーブルに照らし合わせることによって読み出し速度のセス数データ取得のために計 200 回ファイル受信を行った後，予測ができる．

ファイル送信確率 0.02 で計 2000 回ランダムにファイル送受信

読み出し 開始時 コネクション数・速度テーブルからを行った．

そのときのコネクション数に対応する速度を取得する

ファイル送信に用いられる格納ファイルはクライアント上に読み出し 終了時 そのときのコネクションと読み出し保存されているファイルからランダムに選ばれる．ファイル受の平均速度をコネクション数・速度テーブルに書き込む

信時の受信ファイル決定は，アクセス量に偏りを持たせるため，

表1

ストレージノード 性能緒元

表 3 サブオブジェクト配置決定法の効果

Number of Client nodes

4 nodes

AverageStandard

Number of Disk nodes

8 nodesThroughput (MB/s)

DeviationCPU

AMD Athlon XP-M 1800+ (1.53GHz)

ストライピングを用いない

6.96

4.10

MEM

PC2100 DDR SDRAM 1GB

ランダムに配置

16.01

5.38

Network

1000BASE-T

アクセスの履歴による配置決定法

17.12

6.35

HDD

TOSHIBA MK3019GAX(30GB，5400rpm，2.5inch)

ライピングを用いた 2 手法を比較すると，ストライピングを用OSLinux 2.4.20

Local File Systemreiser FS

いることによってスループットが 2 倍以上に向上している．まJava VM

Sun J2SE 1.5.0 03

た，図 4 から分かるとおり，常に 2 倍以上のスループットを達成している．これは従来のストライピングを行わない方法では

表 2 実験パラメタ
100 回

初期読み出し200 回合計送受信回数

2000 回

送信率 α

0.02

ピーク数 k1

Zipf 母数 θ

0.9

Fragment サイズ

8kB

定した手法を比較すると，アクセスの履歴を用いた手法のほう

Subobject 数

3がスループットが上昇している．この理由としては，ランダム

レージしか用いられなかったが，ストライピングを行うことにより同時に最大 8 台のストレージが用いられるようになったためである．
また，表 3 および図 4 から分かるとおり，サブオブジェクトをランダムに配置した手法とアクセスの履歴を用いて配置を決

576 8 98 :3;=<>;=?A@
BDC ?FEG6IH
JLKFKFMONNAP ; N 8Q6I:SR


 
4

4 台のクライアントの読み出しに対して同時に最大 4 台のスト

初期書き込み



132
0
)
+
&*

り，そのストレージの読み出し性能が減少し，さらにそのストレージにアクセスされることが多いため，結果として平均の読
み出し性能が遅くなる．それに対して，アクセス履歴を用いた



-/. ,

に配置した場合はある一部のストレージへのアクセスが多くな



手法ではストレージ間のアクセス数が均等化されるため，スト

レージの読み出し速度の減少量が平均化され，またシステム全


)

%&

体のストレージから均等に読み出しが行われるため，平均の読'(

み出し性能が遅くならないためである．


しかし ，表 3 の標準偏差から分かるとおり読み出し 速度の








 

  !"#$

ばらつきは増大している．これは，アクセス履歴を用いた手法ではオブジェクト毎のスループットが，高スループットと低スループットに二極化されてしまうためである．そのため，ス

図 4 配置によるスループットの変化

ループットの安定化と更なる高速化のためには，スループット
が二極化されてしまった原因を特定し，低スループットとなる

2k 個の Zipf 分布を合成し 生成した，ピーク数が k 個のアクセ

スパターンを用いた．Zipf 分布の偏りはパラメタ θ によって決まる．今回行った実験のパラメタは表 2 の通りである．
6. 2

配置法の効果まずサブオブジェクト配置決定法の効果を検証する．実験内
容は以下の通りである．
（ 1 ） ストライピングを用いない（ 2 ） ランダムに配置する（ 3 ） アクセスの履歴による配置決定法を用いて配置する
上記の 3 通りの配置法を用いてランダムにリクエストを複数
クライアントから送信する．その際の各クライアントによるオ
ブジェクト読み出しの平均スループットの時間変化を測定した．
その結果は表 3 および図 4 の通りである．なお図 4 は全クライ
アント合わせて 100 回ごとの平均のスループットの推移を表したグラフである．
6. 2. 1

考読み出しを減らす必要がある．
6. 3

プライマリ・バックアップスケジューリングの効果

プライマリ・バックアップスケジューリングの効果を確かめるための実験を行う．実験には，以下の 2 種類のプライマリバックアップ読み出し法を使用し，フラグ メントの配置法はサ
ブオブジェクト配置決定法を用いる．
（ 1 ） 全てプライマリから読み出す（ 2 ） プライマリ・バックアップの読み出し割合 1:1（ 3 ） コネクション数の比による読み出し量決定法（ 4 ） 過去の処理実績による読み出し量決定法
なお，この実験も配置法の実験と同様にリクエストの送信を行い，各クライアントによるオブジェクト読み出しの平均ス
ループットの時間変化を測定した．その結果は表 4 および図 5の通りである．なお図 5 も配置法の実験と同様に全クライアン
ト合わせて 100 回ごとの平均のスループットの推移を表したグ

察

まず，表 3 より，ストライピングを用いなかった場合とストラフである．

 
0

-/.
,
)+* (



%
'  

"&
%
#$



!"

+






図5



 
    )' (> 1@??0-A/B8DCE1@? FG6&3 H0-JI > K :&?MLJ'B(        B' (,.-0/2143 576289- ,.-2:0; ,.:<8=(ON &  ! " $# ! % "スケジューリングによるスループットの変化

AverageStandard

Throughput (MB/s)

Deviation

全てプライマリ

17.12

6.35

読み出し割合 1:1

21.87

8.02

コネクション数の比

21.86

7.57

過去の処理実績

18.61

7.43

考

   ! " $# ! % " 

表 4 フラグ メント読み出し量決定アルゴ リズムの効果

6. 3. 1')(*132426587:9<;=7?>
587@96;=7?>BA4C8=ED F GEH  A 
IKJMLEN DPOQ9RJMLTSUG ;WVN 7
IKJMLEN DPOQ9RJMLTXY9<Z[J\O]JM7^>



 (ON
図 6 読み出し量再計算

察

表 4 のように，バックアップからの読み出しを行うことによってスループットが向上した．これはバックアップへもアク
セスすることにより，システム全体として各クライアントへのアクセス数が均等化されたためである．
また，図 5 および表 4 から分かるとおり，読み出し割合をプ
ライマリ・バックアップ間で常に 1:1 にした方法と，コネクショ
ン数の比を用いて決定した方法を比較すると，平均スループッ
トは同じである．これはコネクション数の比を用いて予測する方法を用いたとき，読み出し途中でのコネクション数の変化が生じたり，システムプロセスなどが動作し読み出し性能へ影響を与えたりするが，これらの読み出し性能への影響が考慮できていないためである．しかし，偏りはコネクション数の比を用いたほうが小さくなって読み出し速度が安定している．これはコネクション数の比を用いたことにより，高スループットの読
み出し も減ったが，低スループットの読み出しも減ったため，平均値付近のスループットが多くなったためであり，速度が安定したことが分かる．
しかし ，過去の処理実績を用いた方法では，他のバックアップを読み出しに用いた 2 手法に比べてスループットが向上していない．これは今回の実験では履歴として過去全てのアクセスを用いたため，時間が経つにつれ過去の履歴が多くなり，現在の性能が反映しにくくなるためである．しかし，図 5 から分かるとおり，リクエスト回数 200 回程度から減少が始まっている．
そのため，履歴の保持期間の設定をすることによって，古い履歴を破棄し現在の性能を反映しやすくすることによってスルー
プット減少を抑えられると考えられる．
7.

議

論

プライマリとバックアップの存在するストレージの片方だけコネクション 数が 変化し た場合，コネクション 数の変化が 起
こったストレージの読み出し速度が変化するため，式 (5. 1) による最適な読み出し割合が変わってしまう．そのため，コネク
ション数が変化した場合にも読み出し時間を最小化するためには，コネクション数が変わった瞬間にプライマリ・バックアップのフラグ メントの読み出し割合を再計算する必要がある．
例えば図 6 において，初めのプライマリストレージとバック
アップストレージへのコネクションの数がそれぞれ 2 である場
合 (I)，それぞれのストレージの読み出し割合は 1/2 (1 : 1) とな
る．ここで，バックアップストレージのコネクションの数が増
え 3 になったとする (II)．この時，式 (5. 1) による最適な読み出
し割合はプライマリ 3/5 ，バックアップ 2/5 (3 : 2) となる．そのため，1/2 (1 : 1) のままでは最適ではないため，読み出し割合を最適な値に直すことで読み出し時間を短くすることができる (III)．
以上のこと次のように読み出し率の再計算を行うことによって読み出し時間を最小にすることができる．
（ 1 ） 一定時間ごとにコネクション数の変化がないかシステ
ムに問い合わせを行う．
（ 2 ） コネクション数の変化があったときだけ，プライマリ・
バックアップ読み出し量を再計算する．
以上のように，定期的に読み出し 率の再計算を行うことによって，読み出しを開始した後にコネクション数の変化があった場合でも，読み出し率を最適化でき，読み出し時間を短くすることができる．
8.

まとめと今後の課題

本研究では，自律デ ィスク上でストライピングを行うために分割したデータを配置するプ リミティブな配置手法を提案し ，[7]実機実験による性能評価を行った．また，バックアップを耐故障化に用いるだけでなく，ストライピング時のスループット向No. 9, pp. 831840, Sep. 2002.
[8]

上に利用する可能性を調べるために，プライマリのアクセス負Akitsugu Watanabe and Haruo Yokota. Adaptive lapped declustering: A highly available data-placement method balancing access loadand space utilization. In ICDE, pp. 828839. IEEE Computer Soci-

荷が高い場合はバックアップデータから読み出すよう，アクセス数に注目したプライマリ・バックアップ間の読み出し比率調渡邊明嗣 , 横田治夫. 分散ディレクトリ探索コストを考慮した並列
データアクセス偏り制御. 電子情報通信学会論文誌, Vol. J85-D-I,

ety, 2005.
[9]

Mana Nakano, Dai Kobayashi, Akitsugu Watanabe, Toshihiro Uehara, Ryo Taguchi, and Haruo Yokota. The versioning system balanc-

整を行う手法を提案し，実機実験によって評価した．

ing data amount and access frequency on distributed storage system.

今後の課題についてはまず，異なるパラメタでの環境に対する各アルゴ リズムの挙動について実験評価を行う必要があるこ

In ICDE Workshops, p. 1264, 2005.
[10]

Per-Åke Larson, editors, SIGMOD Conference, pp. 109116. ACM

変化する場合を考慮していない．データへの読み書きリクエス
トの傾向が変化する場合に，ストレージ間のアクセスを均等化

Press, 1988.
[11]

Peter M. Chen, Edward L. Lee, Garth A. Gibson, Randy H. Katz,
and David A. Patterson. Raid: High-performance, reliable secondary

するにはデータマイグレーションが適する．よって本稿で提案した手法とデータマイグレーションを両方用いた場合のコスト

David A. Patterson, Garth A. Gibson, and Randy H. Katz. A casefor redundant arrays of inexpensive disks (raid). In Haran Boral andとである．また今回はデータへの読み書きリクエストの傾向がstorage. ACM Comput. Surv., Vol. 26, No. 2, pp. 145185, 1994.
[12]

Kenneth Salem and Hector Garcia-Molina.

Disk striping.

In Pro-ceedings of the Second International Conference on Data Engineer-と性能の評価なども必要であると考える．

ing, pp. 336342, Washington, DC, USA, 1986. IEEE Computer So-

また，現実的なシステムではストレージノード 内部で並行動作しているシステムプロセス等があるため，これらのディスク

ciety.
[13]

I/O 性能への影響調査と，それを考慮したスケジューリング手Andre Brinkmann, Kay Salzwedel, and Christian Scheideler.

Effi-

cient, distributed data placement strategies for storage area networks.
In ACM Symposium on Parallel Algorithms and Architectures, pp.

法の改善を行うことが必要である．

119128, 2000.

また，近年のストレージノード 上には大容量の半導体記憶に[14]

Steven Berson, Shahram Ghandeharizadeh, Richard Muntz, and Xiangyu Ju. Staggered striping in multimedia information systems. In

よるキャッシュ機構が期待できるため，高速化のためにそれら

SIGMOD '94: Proceedings of the 1994 ACM SIGMOD internationalのデ ィスクキャッシュも考慮したスケジューリングを行うこと

conference on Management of data, pp. 7990, New York, NY, USA,を検討している．

1994. ACM Press.

これらをふまえ，動的配置が可能なストライピングにおける[15]

伊藤大輔 , 風戸広史 , 横田治夫. 負荷分散機構と組み合わせた自律ディスクのクラスタ再構築. 信学技報，FTS2001-20, pp. 119126.
電子情報通信学会, Jul. 2001.

[16]

Haruo Yokota, Yasuhiko Kanemasa, and Jun Miyazaki.

負荷均衡化，容量均衡化，耐故障化，規模変更機能の実現を目
指す．

Fat-btree:

An update-conscious parallel directory structure. In Proc. of the 15th

謝辞Int'l Conf. on Data Engineering, pp. 448457, 1999.
[17]

CREST，情報ストレージ研究推進機構 (SRC)，文部科学省科学pp. 4552. Information Processing Society of Japan, Jul. 2001.
[18]

研究費補助金特定領域研究 (16016232) および東京工業大学 21
世紀 COE プログラム「 大規模知識資源の体系化と活用基盤構
築」の助成により行なわれた．
文
[1]

献

Gregory R. Ganger, John D. Strunk, and Andrew J. Klosterman. Self* storage: Brick-based storage with automated administration. Technical Report CMU-CS-03-178, Carnegie Mellon University, Aug
2003.

[2]

Svend Frølund, Arif Merchant, Yasushi Saito, Susan Spence, and Alistair Veitch.

FAB: enterprise storage systems on a shoestring.

In

HOTOS 2003, Kauai, HI, May 2003.
[3]

John MacCormick, Nick Murphy, Marc Najork, Chandramohan A.
Thekkath, and Lidong Zhou. Boxwood: Abstractions as the foundation for storage infrastructure. In OSDI, pp. 105120, 2004.

[4]

武理一郎, 野口康生, 土屋芳浩, 荻原一隆, 田村雅寿, 丸山哲太
郎. オーガニックストレージシステム. 信学技報 CPSY2004-57
pp.55-60, 電子情報通信学会, 2004.

[5]

Haruo Yokota.
tions.

Autonomous disks for advanced database applica-

In Proc. of International Symposium on Database Applica-

tions in Non-Traditional Environments (DANTE'99), pp. 441448,
Nov. 1999.
[6]

D. Ito and H. Yokota. Automatic reconguration of an autonomous
disk cluster. In Proc. of 2001 Pacic Rim International Symposiumon Dependable Computing (PRDC 2001), pp. 169172. IEEE, Dec.
2001.

Hiroshi Kazato and Haruo Yokota. Implementation of a fat-btree inan autonomous-disk cluster. In IPSJ Technical Report, DBS-125-71,

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

J. Gray and A. Reuter. Transaction Proceeding: Concepts and Techniques. Morgan Kaufmann, San Francisco, 1992.

[19]

H. Simitci. Storage Network Performance Analysis. Wiley Technology Publishing, 2003.