日本ソフトウェア科学会第 32 回大会 (2015 年度) 講演論文集

分散ハッシュテーブルを用いたストレージシステムの省電力化手法為我井 勝

長谷部 浩二加藤 和彦

本研究では，大規模分散ストレージシステムの省電力化手法を提案する．その基本的なアイディアは，ストレージシ
ステムを分散ハッシュテーブルにより管理し，予測される将来のアクセス頻度が類似したファイル群を同一のディスクに集約するというものである．これにより，一部のディスクにアクセスを集約させ，一定時間アクセスされないディスクを休止状態にすることで消費電力を削減する．ここでのアクセス頻度の予測は，ファイルがアップロードされてからの経過時間とアクセス回数によって行われる．これをもとに，分散ハッシュテーブルにおける ID の割り当てを，従来のハッシュ関数に加えてアップロード後の経過時間とアクセス回数により行う．以上により，アクセス頻度によるファイルの集約を，分散ハッシュテーブル上の ID 空間で自然に実現することができる．さらに，ファイルの保存場所が変化したとしても，クライアントは目的のファイルの ID をアップロード後の経過時間とアクセス回数から求めることでアクセスすることができる．本論文では，以上で述べた提案手法の詳細を説明するとともに，ディスクの使用効率を向上させる方法についても議論する．

とも言われている．そのため，近年ストレージシステ

1 はじめにムの省電力化の研究が盛んに行われている．

近年，クラウドコンピューティングの発展と普及に以上を背景に，本研究では，大規模な分散ストレー

伴い，インターネット経由のオンラインストレージ

ジシステムの省電力化手法を提案する．特に，ファイサービスが普及している．その例としては，Dropbox，

ルが逐次追加される状況に対応し，負荷を一部のディ

Google Drive，Amazon S3 等が挙げられる．こうし

スクに集約することを目的とする．その基本的なアイたサービスを提供するためには，データセンター規模

ディアは，将来のアクセス頻度が類似したファイル群

でサーバを稼働させる必要があり，そこでは大量の電を同一のディスクに保存することで負荷の集約を行

力が消費される．文献 [12] によると，米国で消費されい，一定時間アクセスされないディスクを休止状態にる電力のうち，データセンターが消費する電力の割合するというものである．特にここでは，ディスク間では約 1〜2%だと報告されている．そのため，データのファイルの移動により，負荷の集約を実現する．一センターの省電力化は，クラウドコンピューティング

般に，分散ストレージシステムでは，ファイルの保存の基盤システムを構築する上で重要な課題となってい場所をインデックスサーバによって管理する．しかしる．このようなデータセンターにおいて，電力消費のながら，本研究のようにファイルの移動が頻繁に起こ割合が比較的高いものとしてストレージシステムが挙るシステムでは，単一のインデックスサーバによってげられる．文献 [7] によると，その割合は 25-35% だ

管理を行うと，そこが性能のボトルネックや単一障害点となることが考えられる．そこで本研究では，ファPower-Saving in Storage Systems with Distributed
Hash Table.
Masaru Tamegai, Koji Hasebe, Kazuhiko Kato, 筑波
大学システム情報工学研究科コンピュータサイエンス専
攻, Dept. of Computer Science, Graduate school of
Systems and Information Engineering, University ofTsukuba.

イルの保存場所を分散ハッシュテーブルによって管理する．分散ハッシュテーブルとは，巨大なハッシュ
テーブルを用いて複数のノードでデータを管理する技術である．これにより，単一のインデックスサーバ
によるファイルの保存場所の管理を不要にすることができる．以上で述べたシステムにおいて負荷の集約をが高いときは，レプリカを配置したディスクを利用し実現するために，本研究では，分散ハッシュテーブル

て負荷分散を行う．PARAID では，RAID により構上のファイルの ID とファイルのアクセス頻度を同一築されたストレージシステムを対象とし，そこでの未視するという手法を提案する．先行研究 [8] で，ファ使用のスペースに着目した手法である．この手法でイルの将来のアクセス頻度は，過去のアクセス回数とは，データのレプリカを未使用のスペースに配置し，アップロード後の経過時間の２つと相関関係のあるこ

そのスペースを負荷の大きさにより段階的に省電力とが示されている．本提案手法でもこの関係を利用しモードにしていく．

て，分散ハッシュテーブルにおける ID をファイルの一方，アクセス頻度に着目した手法の例としては，

アップロード後の経過時間と過去のアクセス回数によMAID [4] や PDC [9] が挙げられる．MAID は，直前

り決定する．ただし，提案システムでは，クライアンにアクセスされたデータをキャッシュディスクに保存

トはファイルへのアクセス回数を保持しているものとし，常にキャッシュディスクを起動させておき，そのし，ファイルが異なるディスクに移動したとしても，他のデータを保存したディスクを省電力モードにする

クライアントは目的のファイルの ID をアップロード手法である．それに対し，PDC はデータをアクセス

後の経過時間と過去のアクセス回数から求めること

頻度順に保存することで，アクセスの少ないディスクでアクセスすることができる．以上のアイディアに基を省電力モードに移行する手法である．

づき，本提案手法ではクライアントの目的のファイル以上で挙げた手法は，比較的小規模なシステムを前へのアクセスを可能にしつつ，ファイルの将来のアク提としている．しかし近年，クラウドコンピューティ

セス頻度により負荷の集約を行う．

ングの普及に伴い，大規模なストレージシステムに

以下，第 2 章で関連研究について説明する．第 3

対する省電力化の研究も行われるようになった．そ章では，実際のファイル共有サービスのアクセスパ

こでの中心的課題は，以上の手法で用いられてきたターンを用いて将来のアクセス頻度予測を行うためアイディアの拡張性を高め，大規模なシステムに適に，Dailymotion と呼ばれるファイル共有サービスの用することである．こうした研究の例として，HDFS

アクセスパターンを分析した結果を述べる．第 4 章（Hadoop Distributed File System）を対象とした手では本研究が提案するシステムを説明する．最後に，

法 [6] がある．この手法は，ディスク群を hot zone と第 5 章でまとめと今後の課題を述べる．

cold zone に分類して省電力化を行うものである．また同様に，クラウド上の既存のストレージシステム

2 関連研究を対象にした手法 [5] がある．この手法では，レプリ

これまでに提案されてきたストレージシステムのカの配置を工夫することで省電力化を行っており，さ省電力化手法の多くは，低負荷時にファイルを一部のらに，省電力モードで一部のデータにアクセスでき

ディスクに集約させることで，他のディスクを省電力なくなる状況を考慮し，auxiliary nodes と呼ばれるモードに移行させ，消費電力を削減するというもので特別なノードを挿入することで，全てのデータへのある [3]．このような省電力化の手法には，大きく分

アクセスを可能にしている．その他にも，本研究の直けて冗長化したデータを用いて負荷分散するものと，接の先行研究である Okoshi らの [8] による格子状にアクセス頻度に着目して負荷の集約を行うものの２つ配置したディスクでアクセス頻度ごとにファイルを集がある．冗長化したデータを用いる例としては，DIV約する手法がある．Okoshi らの手法では，ファイル[10] や PARAID [14] が挙げられる．DIV では，オリに対する急激なアクセス頻度の変化に対応するため

ジナルデータが保存されたディスクとデータのレプリに，現在のアクセス頻度ではなく，将来のアクセス頻

カが保存された 2 種類のディスクを用意する．負荷度の予測値を用いてファイルの集約を行っている．たが低いときは，レプリカが保存されたディスクを省電だし，これらの手法では，ファイルが保存されている

力モードにすることで省電力化を行う．一方で，負荷場所の管理を単一のインデックスサーバによって行っている．単一のインデックスサーバによるファイルのス頻度を求める方法を 3. 2 節で説明する．

保存場所の管理は，そこが性能のボトルネックや単一
障害点となる可能性がある．

3. 1 Dailymotion のアクセス傾向の特徴

以上で述べた先行研究に対し，本研究では [8] と同

まず，動画ファイルの 1 時間あたりの平均のアク様にファイルが逐次的に増加する状況に対応し，アク

セス回数の推移を調べた．図 1 にその結果を示す．

バによる全ファイルの保存場所の管理が不要な手法を提案する．また， [8] では Flickr のアクセスパターン
のみを用いて将来のアクセス頻度予測を行っており，
他のサービスに対し将来のアクセス頻度予測が適用可能かどうかは不明である．そこで，本研究では，他のサービスに対してもアクセス頻度予測が適用可能であるか否かを調べるために Dailymotion と呼ばれるファイル共有サービスのアクセスパターンの分析を

Average number of accesses per hour

セス頻度の予測を行いつつ，単一のインデックスサー

1

0.1
0

行った．

3 Dailymotion における動画ファイルの分析

10

図1

200

400

600
800
Time (hour)

1000

1200

1400

Dailymotion における平均のアクセス回数の推移

本研究では，Flickr 以外のファイル共有サービスにおいても将来のアクセス頻度予測が可能か否かを調べ

１時間あたりの平均のアクセス回数はアップロード

るために，Dailymotion と呼ばれる動画共有サイト

されて１時間後は 6.8 回であるのに対し，1400 時間のファイルのアクセスパターンを取得した [1]．Daily-

後は 0.19 回まで減少している．また，1400 時間中，

motion には月間 1.28 億人の人々が訪れ，月に約 3 億400 時間までに全アクセス数の約 55%を占めている

人が動画を視聴している．また，1ヶ月の動画視聴回ことが分かった．これらの結果より，先行研究 [8] の数は 25 億回以上であり，1 日に 9 千以上もの動画が投Flickr のアクセスパターンと同様に，経過時間とアク稿されている [11]．本研究では，Dailymotion の動画

セス回数は負の相関関係が存在し，特にアクセスはファイルのアクセスパターンの収集を，Dailymotion

アップロード直後に多く行われることが分かった．

が提供している Web API [2] を用いて行った．この次に，図 2 にアクセス頻度の偏りを表す結果を示

API により，アップロード直後のランダムな 50,000

す．この図では各経過時間に対する累積のアクセス回

個の動画ファイルのアクセス回数を間 2014 年 12 月

数を動画ファイルのアクセス回数ごとに並び替えた

20 日から 2015 年 2 月 22 日まで 1 時間ごとに採取結果を表している．この図 2 より，アクセスは一部のした．

ファイルに集中していることが観察できた．また，図Okoshi らの先行研究 [8] では，実際のファイル共有
サービスのアクセスパターンを用いてファイルの将

1 の結果と同様に，アップロード直後にアクセスの回数が多いことも観察できた．

来のアクセス頻度予測を行っているが，Flickr のみの写真ファイルの分析しか行っていない．そこで，本研
究では，Dailymotion における動画ファイルの分析を

3. 2 Dailymotion におけるアクセスパターンを用いた将来のアクセス傾向予測

行うとにより，アクセス頻度予測が Flickr 以外の他

3. 1 節の結果より，Dailymotion のアクセスパターのサービスに対しても適応可能であることを示す．以ンにおいても先行研究 [8] の Flickr のアクセスパター

下，3. 1 節で Dailymotion のアクセスパターンを分ンと同様に，将来のアクセス頻度は，アップロードさ析した結果を説明し，この結果をもとに将来のアクセ

れてからの経過時間が短く，過去のアクセス回数が多1e+06
100000
10000

6000

1000

5000

100
10
10
200
400
600
800
1000
1200

Time (hour)

0

50000
45000
40000
35000
30000
25000
20000
15000
10000
5000

MoviesAccess (future)

Cumulative number of accesses

きるようにしたグラフを図 4 に示す． この図を用い

4000
3000
2000
1000
00

20000
200

15000

400
10000

600
800

Elapsed time (hour)

図2

5000

1000
1200 0Access (past)

Dailymotion におけるアクセス頻度の偏り

いファイルは高いことが考えられる．そのため，将来のアクセス頻度は，過去のアクセス回数とアップロー

図4

Dailymotion において累乗近似により平滑化した
将来のアクセス回数

ドされてからの経過時間の 2 つと相関関係のあることが考えられる．そこで，図 3 に Dailymotion におて，アップロードされてからの経過時間と累積のアク

ける動画の経過時間とそれまでの累積のアクセス回

セス回数の 2 変数を引数にとり，将来のアクセス頻数に対する 300 時間後のアクセス回数を表した図を

度を関数 f req : F × T → N として算出する．以上示す．ここでは，x 軸に経過時間を示し，y 軸にそれの分析により，先行研究 [8] で示されている将来のアまでの累積のアクセス回数を示し，z 軸に経過時間か

クセス頻度に関する相関関係が Dailymotion におい

ら 300 時間後までにアクセスされる回数を示していても観察することができた．そのため同様のファイル

る．しかし，このグラフからはデータを採取してい共有サービスの多くで，将来のアクセス頻度についない部分がグラフの谷として現れてしまう． そのたての相関関係の見られることが予想される．したがって，本研究で採取したようなファイルの経過時間と過去のアクセス回数，将来のアクセス回数のデータを用
いて，将来のアクセス頻度予測を行い，提案システム

30000

を適用することが有効だと思われる．

Access (future)

25000
20000

4 提案システム

15000
10000

この章では，本研究が提案するシステムについて説

5000
00

20000
200

15000

400
10000

600
800

節でシステムの構成を説明する．また，4. 3 節では，

5000

1000
1200 0

明する．4. 1 節で提案システムの概要を説明し，4. 2

Access (past)

Elapsed time (hour)

提案システムにおける分散ハッシュテーブルの ID の定義を説明し，4. 4 節では，クライアントの要求に対

図3

Dailymotion における将来のアクセス回数の算出

しシステムが行う処理を説明する．さらに，4. 5 節では，提案システムが ID を更新する方法について説明

め，次に先行研究 [8] と同様に，図 3 のグラフに対し，b

経過時間ごとに最小二乗法と累乗関数 z = ay により，a と b を決定し累乗近似を行い，データを採取していない部分をアクセス頻度予測に用いることがでし，4. 6 節では，ディスクの使用率を改善するための処理の説明をする．

図5

システムの構成

4. 1 システムの概要

ファイルをディスク間で移動させると使用率が低い

提案手法は，数千から数万台のディスクにより構成

ディスクが生じてしまう可能性がある．そこで，本提された大規模なストレージシステムを対象としてい案手法では，一定時間ごとに使用率が低いディスクのる．図 5 にシステム全体の構成図を示す．提案システ

ファイルを一部のディスクにまとめることでシステム

ムは，クライアントからファイルのアップロードを受全体としてディスクの使用率を高くする処理を行う．

け付ける k（定数）台の書き込み用ディスク群と，クライアントから読み込みのみ受け付ける読み込み用

4. 2 システムの構成

ディスク群，さらに空のディスクプールの 3 つのグ

提案システムにおいて，初期状態でシステムを構成

ループにより構成されている．なお，本研究の分散ス

しているディスクの集合を Dinit = {d1 , · · · , dk } とトレージシステムでは，分散ハッシュテーブルを用いし，これらのディスクを初期状態の書き込み用ディスてファイルを管理する．分散ハッシュテーブルとは，ク群とする．さらに，各ディスクを Chord におけるネットワーク上の複数のノードでファイルを分散してノードとし，Successor を関数 suc : D × T → D と定管理する技術である．これを用いることにより，クラ義し，Predecessor は pre : D × T → D と定義する．

イアントからのファイルへのアクセスを単一のイン

また，システムの稼働中に追加される空のディスク

デックスサーバ無しで可能にする．本研究の提案手法の集合を Dsup = {dk+1 , · · · } とする．すなわち，全では，分散ハッシュテーブルの代表的な 1 つであるてのディスクの集合は D = Dinit ∪ Dsup と表される．

Chord [13] を用いる．ただし，本提案手法では，分散

さらに，このシステムに格納されているファイルの集

ハッシュテーブルにおけるファイルの ID をアクセス

合を F として，F = {f1 , f2 , · · · } とする．システム

頻度に従い変化させる．本研究では先行研究 [8] で示における時刻は t = 0, 1, 2, · · · ∈ T として自然数で表された将来のアクセス頻度の性質を利用して，Chord

し，離散的に表すものとする．次に，ファイルが属すにおける ID を下位の部分は従来のハッシュ関数によるディスクを関数 place : F × T → D によって表す．

り一意の値を割り振り，上位の部分は過去のアクセス

つまり，時刻 t において，あるファイル fi がディス

回数とアップロード後の経過時間により変化させる．

ク dj に属するとき，place(fi , t) = dj とする．また，これにより，ID 空間上でアクセス頻度によるファイ関数 place はあるディスクに属するファイル群を表す

ルの集約を行うことができる．なお，クライアントがためにも用いる．すなわち，place : D × T → 2F でファイルにアクセスする場合は，ファイルのハッシュもあり，place(dj , t) = {f | place(f, t) = dj } となる．

値と過去のアクセス回数，アップロード後の経過時間

ただし，文脈より明らかな場合は place(fi , t) = dj を

により ID を求めることで常にアクセスできる．また，

単に fi ∈ dj と表す．さらに，１つのファイルのサイズを関数 size : F → N で表し，ディスクに格納され変化する．すなわち，ri + c = ri+1 となる．以下の本ているファイルの容量の合計を関数 vol : D × T → N

論文では，時刻 t において直前に更新された時刻を riで表す．したがって，以下のように表される．

Dと表すものとする．関数 IDtime
では，ディスクが書∑

vol(dj , t) =size(f ).

f ∈place(dj ,t)

こ れ に 対 し ，ディス ク の ファイ ル の 許容 量 を 関 数

capvol : D → N で表す．
4. 3 分散ハッシュテーブルにおける ID の定義（1）ディスクの ID の定義
分散ハッシュテーブルによって管理されるディスクの ID を関数 IDD : D × T → IDS により表し，ID空間は集合 IDS で表されるものとする．関数 ID D
は以下のように定義する．
D
D
IDD (d, t) = IDtime(d, t) : IDunique(d, t).

ここでは，x と y が整数で y の桁数が Y のとき，

x : y は x · 10Y + y を 表 す も の と す る ．ID はき込み用ディスク群にある場合は常に 2Mtime − 1 であり，ディスクが読み込み用ディスク群に移動したとき (2Mtime − 1) − (ri − timeadd (d)) に変化する．この式における関数 timeadd : D → T は，ディスクが書
き込み用ディスク群から読み込み用ディスク群に挿入された時刻を表している．そのため，t < timeadd (d)のときは，時刻 t においてディスク d が書き込み用
ディスク群に存在することを表し，t ≥ timeadd (d) のときは読み込み用ディスク群に存在することを表す．
D
次 に ，関 数 IDuniqueに つ い て 説 明 す る ．関 数
DIDuniqueを次の式で定義する．
Munique−1w index(d, t) · 2k (if t < timeadd (d))
DIDunique(d, t) =hashD (d) (if t ≥ time (d)).
add

関数 w index : D × T → N は時刻 t において，ディM = Mtime + Munique ビット で 表 さ れ ，ID のD
スク d の IDuniqueの書き込み用ディスク群におけるう ち 上 位 Mtime ビット が ディス ク の 場 合 は 関 数

順序を表す関数であり，0 < w index(d, t) ≤ k となD
IDtime: D × T → N により表される．それに対し，下位 Munique ビットがディスクの場合は関数D
IDunique: D × T → N により表される．なお，ID 空

る．関数 hashD : D → N はディスクに対し，ディスクの IP アドレス等から一意に決まる値をハッシュ関
数により割り当てることを表している．

間のうち 2Mtime −1 : 0 から 2Mtime −1 : 2Munique −1までが書き込む用ディスク群が管理される範囲であ（2）ファイルの ID の定義

り，0 : 0 から 2Mtime − 2 : 2Munique − 1 までが読み

次に，分散ハッシュテーブルによって管理される込み用ディスク群が管理される範囲とする．次に，関ファイルの ID を表す関数 ID F : F × T → IDS に

D
D
数 IDD を構成する関数 IDtimeと IDuniqueについついて説明する．関数 ID F を以下の式で定義する．

Dてそれぞれ説明する．まず，関数 IDtime
を次の式で

定義する．

D
IDtime(d, t) =F
IDF (f, t) = IDtime(f, t) : hashF (f ).


2Mtime − 1 (if t < timeadd (d))

(2Mtime − 1) − (ri − timeadd (d))
 (if t ≥ timeadd (d)).

F
まず，ID のうち上位 Mtime ビットを表す関数 IDtime:

F × T → N について説明する．ファイルが保存されているディスクが書き込み用ディスク群に存在するとFき，IDtime
は 2Mtime − 1 となる．それに対し読み込

み用ディスク群に存在するときは以下の式となる．
提案システムでは，読み込み用ディスク群におけるディスクとファイルの ID は一定時間 c（定数）ごとに変化し，r1 < · · · < ri ≤ t < ri+1 とし，ri のときに
IDf req (f, tri−1 ) − c






 (if group(IDf req (f, tri−1 )F= group(IDf req (f, tri ))IDtime (f, t) =





IDf req (f, tri )(otherwise).
本研究の提案手法では，読み込み用ディスク群において，ファイルの ID が変化したとき，アクセス頻度が同様なディスク間でのファイルの移動を無くすために，

ID 空間を n 段階のグループに分割し，同一グループ
内でファイルが他のディスクへ移動しないようにファイルの ID を定義した．そのため，n 段階のグループの集合を G = {g1 , . . . gn } とし，それぞれのグループにおける ID の範囲の上限を関数 area : G → 2IDSで表し，以下のように定義する．

2Mtime −22Mtime −2area(gi ) = {x|(i−1)·< x ≤ i·}.
nnF
それに対し，IDtime(f, t) で用いられる関数 group :IDS → G は，関数 area を使って定義する部分関数
であり，ID を引数にとりその ID が所属するグループを返すものとする．さらに，関数 IDf req : F ×T → N
は読み込み用ディスク群に存在するディスクに保存さFれているファイルの IDtime
を求めるときや更新するときに用いる関数であり，関数 IDf req の式は以下の通りである．

IDf req (f, t) = (24. 4 クライアントの要求とシステムの処理
この節では，提案システムにおけるクライアント
によるファイルのアップロード方法とクライアントがファイルへのアクセス方法を説明する．
（1）クライアントがファイルをアップロードする方法
まず，提案システムにおけるクライアントのファイ
ルのアップロード方法を説明する．まず，クライアント
は，ファイルに関数 hashF により ID の下位 Munique
ビットを割り当てる．それに対し，上位 Mtime ビッ
トの値は 2Mtime − 1 とする．以上の ID に従い対応
する書き込み用ディスク群のディスクにアップロード
する．
（2）クライアントがファイルにアクセスする方法
次に，提案システムにおいて，クライアントが目的のファイルにアクセスする方法を説明する．クライア
ントが時刻 t において，目的のファイル f にアクセスするものとし，f をアップロードした際に hashF (f )の値を保持しており，f に対してアクセスするのは 1
人のクライアントのみであるため，f のアクセス回数とアップロードしてからの経過時間の情報も保持している．なお，f に対し複数のクライアントからアクセスする場合は，ID を問い合わせるノードをシステ
ムの中に設置し，ここにファイルのアクセス回数を記

Mtime− 1) − (t − timeup (f ))録し，クライアントはここからアクセス回数とアップ+ a · f req(f, t).

ロード後の経過時間を求める．ただし，クライアントa は 0 < a の定数であり，関数 timeup : F → T でファイルがディスクにクライアントからアップロードされた時刻を表している．また，関数 f req : F × T → N
は時刻 t におけるファイル f のアクセス頻度を表す関数である．関数 f req では，先行研究 [8] におけるFlickr のアクセスパターンを用いた将来のアクセス頻度予測や，本研究で分析した Dailymotion のアク
セスパターンを用いた将来のアクセス頻度予測を用いる．最後にファイルの関数 hashF について説明する．ファイルの ID の下位 Munique ビットは関数

hashF : F → N により，ファイルの属性情報等から一意に決まる値を割り当てるものとする．

にとって，f が書き込み用ディスク群に存在している
場合，いつ f が読み込み用ディスク群に移動するか分からない．そのため，f が読み込み用ディスク群に保存されているかどうか不明な場合と明確な場合でアクセスする方法が異なるため，それぞれ説明する．

• Case 1： クライアントにとって f が書き込み用
ディスク群か読み込み用ディスク群に保存されているかどうか不明なとき
F
1. IDtime(f, t) = 2Mtime − 1 とし，書き込

み用ディスク群に保存されているものとしてアクセスする．

2. 書き込み用ディスク群に保存されている場
合はそのままアクセスする．それに対し，書き込み用ディスク群には保存されていない場

F
IDf req (f, ri ) を調べる．この値が IDtime(f, ri−1 ) の合は，目的のファイルは読み込み用ディスク値と比較して同じグループであれば，f req(f, ri ) の群に保存されていることを記録し，読み込み

F
値を考慮せず更新する．すなわち，IDtime(f, ri−1 )用ディスク群に保存されていることが明確なから c だけ小さくする．異なるグループであれば，場合の手続きを行う．

IDf req (f, ri ) の値に更新し，その値に従いディスク• Case 2： クライアントにとって f が読み込み用間の移動が必要な場合は対応するディスクに移動すディスク群に保存されていることが明確なときる．これらの操作により，アクセス頻度が類似した

1. f が現在所属する ID のグループに加わった

ファイルが集約され，それに伴い，アクセスが少ない

時刻 t′ を求める．具体的には IDf req (f, ri )，ディスクを省電力モードに移行させる．

IDf req (f, ri−1 )，· · · を順に求めていき，fが初めて異なるグループとなるときの１つ′前の時刻が t となる．

4. 6 ディスクの使用効率を改善するための処理
読み込み用ディスク群では，ディスク間でファイル′

2. 1. で求めた t を用いて，ID の上位 Mtimeが移動した結果，使用率の低いディスクが生じるこ

ビットの値を以下の式の値として，f にアクとがある．そこで，使用率が一定量以下のディスクのセスする．

ファイルを定期的に集約し，ディスクの台数を出来る(2Mtime −1)−(ri −timeup (f ))+a·f req(f, t′ ).

限り小さくする処理を行う．具体的には，グループご

ただし，読み込み用ディスク群において，4. 6 節で説使用率が一定量以下のディスクを列挙し，それらの明するファイルを一部のディスクにまとめる作業によ中で ID が高いディスクにファイルを集約する．ただり，f が ID に対応するディスクに保存されていない

し，移動したファイルの ID を担当し，本来そのファ場合がある．その場合，そのディスクが所持する移動

イルが保存されるディスクに，移動したファイルと移先リストを参照し，クライアントは実際に保存されて動先のディスクの組を記録し，クライアントからのアいるディスクにホップする．

クセスも可能にする．

とに全てのディスクの使用率を調べ，グループの中で逆に，読み込み用ディスク群において，ディスク間

4. 5 ディスクとファイルの ID の更新方法のファイルの移動により，データの許容量を超えてし

この節では，アクセス頻度が類似したファイルをまうディスクが生じることも起こりうる．その場合同一のディスクに集約するためのディスクとファイルは，許容量を超えてしまったディスクが担当する IDの ID の更新方法を説明する．まず，時刻 t において，空間を半分に分割するように ID を設定した新たな書き込み用ディスク群のディスク d が，所持するファディスクを挿入し，許容量を超えたディスクに保存さイルのデータ量が許容量を超えたとき， すなわち，れたファイルを新たなディスクに移動し，負荷分散を

vol(d, t) ≥ capvol (d) となったとき，d を書き込み用行う．具体的には，時刻 t のとき，読み込み用ディスディスク群から読み込み用ディスク群に移動する．そク群のディスク di において，ファイルの移動により，の際に，d の ID は関数 ID

D

に従い変更され，d に保Fvol(di , t) ≥ capvol (di )に従い変更する．一となるとき，空のディスクプールから新しいディスク

方，読み込み用ディスク群の全てのディスクは一定の追加を行うことで，負荷分散を行う．そこで，追加D
時間 c ごとに IDtimeを更新する．さらに，ディスク

するディスクを dj とする．di と pre(di , t) におけるDの IDtimeを更新する際にディスクが所持する各ファ関数 IDD の値を用いて，dj の ID D の値を以下のよF
イルの IDtimeも更新する．更新する方法は，ファイうに設定する．

存されたファイルの ID も ID

ル f の時刻 ri において，ID を更新するとしたとき，

IDD (dj , t) =IDD (pre(di , t), t)+

IDD (di , t) − IDD (pre(di , t), t).
2

この ID をもとに Chord の join のアルゴリズムを用いて，ディスク dj を追加することで，di のファイルを分散させる．

5 まとめと今後の課題
本研究では，分散ハッシュテーブルを用いた大規模ストレージシステムにおける省電力化手法を提案した．先行研究では，ファイルの保存場所の管理を単一のインデックスサーバにより行っていたが，本研究では，分散ハッシュテーブルによりファイルを管理する手法を提案した．これにより，本提案手法は先行研究と比較して拡張性が高い手法であると言える．さらに，先行研究では Flickr のアクセスパターンのみを用いてファイルの将来のアクセス頻度予測を行っていたので，他のサービスに対する有用性が不明であった．本研究では，Dailymotion におけるアクセスパ
ターンの分析も行い，その結果，Flickr と同様の相関関係が観察された．このことは，本提案手法が多くのファイル共有サービスに対して有用であることを示唆している．
今後は，引き続き Dailymotion の動画ファイルのアクセス回数のトレースを行い，長い時間のアクセスパターンの分析を行う予定である．また，シミュレー
ションにより，提案手法の省電力性や応答性，ファイルの移動回数，さらにディスクの使用率を調べ評価する予定である．また，シミュレーション以外にも提案
システムを実装し，より現実的な設定のもとでの提案
手法の有用性を示す予定である．

参 考 文 献[ 1 ] Dailymotion about. http://www.dailymotion.
com/jp/about.
[ 2 ] Dailymotion API. https://api.dailymotion.
com/videos.
[ 3 ] T. Bostoen, S. Mullender, and Y. Berbers.

Power-reduction techniques for data-center storage
systems. ACM Comput. Surv., Vol. 45, No. 3, pp.
33:1–33:38, July 2013.
[ 4 ] D. Colarelli and D. Grunwald. Massive arrays ofidle disks for storage archives. In Proceedings of the2002 ACM/IEEE Conference on Supercomputing,
SC ’02, pp. 1–11, Los Alamitos, CA, USA, 2002.
IEEE Computer Society Press.
[ 5 ] D. Harnik, D. Naor, and I. Segall. Low powermode in cloud storage systems.
Parallel andDistributed Processing Symposium, International,Vol. 0, pp. 1–8, 2009.
[ 6 ] R. T. Kaushik and M. Bhandarkar. Greenhdfs:
Towards an energy-conserving, storage-eﬃcient, hybrid hadoop compute cluster. In Proceedings ofthe 2010 International Conference on Power Aware
Computing and Systems, HotPower’10, pp. 1–9,
Berkeley, CA, USA, 2010. USENIX Association.
[ 7 ] J. Kim and D. Rotem. Energy proportionality
for disk storage using replication. In Proceedingsof the 14th International Conference on Extending
Database Technology, EDBT/ICDT ’11, pp. 81–92,
New York, NY, USA, 2011. ACM.
[ 8 ] J. Okoshi, K. Hasebe, and K. Kato. Powersaving in storage systems for internet hosting services with data access prediction. IGCC 2013, pp.
1–10, 2013.
[ 9 ] E. Pinheiro and R. Bianchini. Energy conservation techniques for disk array-based servers. In
Proceedings of the 18th Annual International Conference on Supercomputing, ICS ’04, pp. 68–78, New
York, NY, USA, 2004. ACM.
[10] E. Pinheiro, R. Bianchini, and C. Dubnicki.
Exploiting redundancy to conserve energy in storage systems. SIGMETRICS Perform. Eval. Rev.,
Vol. 34, No. 1, pp. 15–26, June 2006.
[11] J. Richard. French video site takes on youtube
with local oﬀering, November 16 2006. http://www.
thetimes.co.uk/tto/news/world/article1982385.
ece.
[12] P. Sehgal, V. Tarasov, and E. Zadok. Optimizing
energy and performance for server-class file system
workloads. Trans. Storage, Vol. 6, No. 3, pp. 10:1–
10:31, September 2010.
[13] I. Stoica, R. Morris, D. Karger, M. F. Kaashoek,
and H. Balakrishnan. Chord: A scalable peer-topeer lookup service for internet applications. In
Proceedings of the 2001 Conference on Applications, Technologies, Architectures, and Protocols
for Computer Communications, SIGCOMM ’01,
pp. 149–160, New York, NY, USA, 2001. ACM.
[14] C. Weddle, M. Oldham, J. Qian, A. A. Wang,
P. Reiher, and G. Kuenning. Paraid: A gear-shifting
power-aware raid. Trans. Storage, Vol. 3, No. 3, October 2007.