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

ゲーム理論を用いた大規模分散ストレージシステムの省電力化手法
澤田 匠

長谷部 浩二加藤 和彦

本研究では，大規模分散ストレージシステムの省電力化手法を提案する．その基本的なアイディアは，システムの低負荷時に一部のディスクにファイルを移動させることによりアクセスを集約し，残りのディスクを省電力モードへと移行させるというものである．ディスク間での柔軟なファイルの移動を実現するために，本提案手法では，仮想ノードを用いた分散ハッシュテーブルによりファイルを管理する．さらに，システムの負荷の変動に応じ，消費電力に関して最適となる仮想ノードの移動を実現するために，ゲーム論的アプローチを採用する．すなわち，各仮想ノードをプレイヤーとみなし，システムの省電力化に貢献するほど高い利得が与えられるようにする．これにより，仮想ノードの利己的な移動によってシステム全体の望ましい状態が達成される．この手法の特徴は，各仮想ノードは局所的な情報をもとに移動先を決定するため，システム全体の情報収集や集中的な処理を行う必要がなく，したがって大規模なシステムにも対応することができる点にある．また本研究では，提案手法による省電力化の効果をシミュレーションにより確認する．

トレージシステムに適用する手法も考えられている．

1 はじめにこれらの多くは，人気に応じてデータを分類する，も近年，Amazon S3 や SkyDrive をはじめとするク

しくはあらかじめレプリカを分散して配置しておく

ラウドコンピューティングによるストレージサービスという考えにより省電力化を実現している．しかし，が広く普及している．こうした大規模なストレージシ

本研究で想定するようなストレージシステムでは時ステムを提供するデータセンターでは多くの電力が間経過とともに負荷は増減すると考えられ，データ消費されるため，今日，その省電力化は重要な課題との人気に基づいた手法ではこうした場合に対応しづなっている．

らい．また，書き込みが多く発生することからレプ

これまで提案されてきたストレージシステムの省リカを配置する方法では一貫性を保つためのコスト

電力化手法の多くは，高負荷時には負荷を分散しておが多くかかると思われる．本研究の重要な先行研究

き，一方で低負荷時には少数のディスクへと負荷を集である [1] では，データを移動させることで大規模分約することで残りのディスクを省電力モードに移行

散ストレージシステムに上記のアイディアを適用しさせるという共通のアイディアに基づいている．比較ている．この手法では，仮想ノードを用いた分散ハッ的初期の研究では中央コントローラにより制御されシュテーブル [2] を構築することで物理計算機（物理る小規模なシステムを対象として，人気のあるデーノード）間でのデータの移動を実現している．各仮想タの集約，冗長データの利用，ディスク間でのデータノードは負荷の変動に応じてあらかじめ決められたの移動といった様々な考えによってこのアイディアを物理ノードへと移動するよう設計されており，これに実現している．最近では，これらの考えを大規模なスより，中央コントローラーのないシステムにおいてもGame Theoretic Approach for Power Saving in Large
Scale Storage Systems.
Takumi Sawada, Koji Hasebe, Kazuhiko Kato, 筑波大学コンピュータサイエンス専攻, Department of Computer Science, University of Tsukuba.

省電力化が達成される．また，仮想ノードの移動先が決定されていることから，変更されたファイルのみを送信することで移動が完了するという優れた特徴を持っている．この手法では稼働ノード数を負荷の増減に応じて変動させることができ，また，データの一貫イルを少数のディスクに集めておくことで他のディス性を保つための処理も必要ない．しかし，このシスクを省電力モードへ移行させている．第二に，冗長テムが省電力化を達成するには仮想ノード間で負荷データを用いた手法が挙げられる．DIV [5] などがこ分散が達成されている必要があり，ファイルの人気がれに該当する．この手法では，データのレプリカを配変動する環境では効果的に動作しない可能性がある．

置しておくことで高負荷時には負荷の分散を達成し，また，物理ノードの数に制約が存在するため，負荷に低負荷時にはレプリカの配置されたディスクを省電力応じて柔軟にシステムを構成することが難しい．これモードへと移動させる．第三に，データの移動を用いらの欠点は，仮想ノードの移動先があらかじめ決定さた手法が挙げられる．PARAID [6] などがこれに該当れていることによると考えられる．

する．低負荷時には少数のディスクに全てのデータがそこで本研究では，各仮想ノードが負荷に応じた配格納されており，高負荷時にはデータの一部を移動さ置へと自律的に移動する手法を考える．これにより，せることで負荷を分散させるという考えにより，省電中央コントローラーが不要であるという利点を残し力化が図られている．これらの先行研究では，比較的つつ，先述のような欠点を回避することができる．仮小規模なシステムや，中央コントローラーによって管想ノードの自律的な移動を実現するために，本研究で理されるシステムを想定している．

はゲーム理論を利用する．ゲーム理論とは，お互いの最近では，中央コントローラーによる管理の難しい行動が影響しあう環境において複数の利己的なプレ大規模なシステムを想定した手法も現れている．こイヤーがどのように行動するかを解析する分野であれらの手法において，基本的なアイディアとその実る．本提案手法では各仮想ノードをプレイヤーにあて

現方法は小規模なシステムを対象とした手法と共通はめ，その配置に応じて得点を与える．この得点を，している．例えば，Harnik らにより提案された手法

負荷に応じた適切な配置であるほど高い値となるよ[7] では，大規模分散ストレージシステムにおいてレう設計すれば，個々の仮想ノードが大きな得点を求めプリカを効率的に配置することで，少数のディスクて移動を行うことでシステムの状態が最適化されるへとアクセスを集約させている．また，GreenHDFSような構造を実現できる．

[11] ではサーバ群を 2 つに分け，それぞれ人気のある

本論文の構成は以下の通りである．2 章では関連研

データを片方に集めることでもう一方のサーバー群究を紹介する．3 章では本研究で想定するシステムのを省電力モードへと移行させている．本研究で注目

ゲーム理論を用いたモデル化を説明する．ゲーム理論

する Hasebe らによる手法 [1] では，物理ノード間でによるモデルに従い仮想ノードを移動させる際の具データを移動させることで少数のディスクへと負荷を体的な手順を 4 章にて示す．シミュレーションを行っ集約させている．ファイルの人気を用いた手法や冗長た結果を 5 章で示し，最後に結論と今後の課題を述

データを用いた手法に比べ，このようなデータの移動べる．

を用いた手法は現在あまり考えられておらず， [1] はその少ない例であると言える．

2 関連研究ストレージシステムの省電力化手法には様々なもの

3 ゲーム理論によるモデル化が提案されているこれらの多くは，高負荷時は負荷を3. 1 システムのモデル

分散しておき，低負荷時は少数のディスクへと負荷をはじめに，本研究で扱うシステムのモデルを示す．

集約させることで他のディスクを省電力モードへと物理ノードの集合 P = {p1 , p2 , ..., pn } が存在し，仮移行させるというアイディアに基づいている．このア想ノードの集合 V = {v1 , v2 , ..., vm } を保持している．

イディアの実現方法として，第一にファイルの人気にシステムに格納されるファイルは，仮想ノードを用着目した手法が挙げられる．MAID [3] や PDC [4] がいた分散ハッシュテーブルによって管理される．仮想

これに該当する．これらの手法では，人気のあるファノードがどの物理ノードによって保持されているか

は，関数 place : V → P によって定義される．物理3. 3 利得関数の設計

ノード p の許容できる最大の負荷を capload (p)，その本研究では次に示される目的関数 g を設計した．

容量を capvol (p) と定義し，仮想ノード v の負荷値をg(place) =load(v)，サイズを size(v) と定義する．これらの値はN∑∑(−c · over(p, i · tw )2

i=0 p∈P+load(p, i · tw )2全て整数で表される．物理ノード p は，サイズの合計が capvol (p) を超えるように仮想ノードを保持することはできず，また，負荷の合計 load(p) が capload (p))(1)

ここで，over(p, t) は次の式で表される．

over(p, t) = β · capload − load(p, t)(2)を超えるように仮想ノードを保持した場合オーバー

β は (0,1] の範囲をとる定数である．また，load(p, t)ロードとなってしまう．物理ノードは互いにメッセー

は t 秒後の物理ノード p における負荷を表す．すでにジのやり取りや仮想ノードの転送を行うことができload(p) が定義されているが，これは load(p, 0) と同る．この状況において，オーバーロードが発生せず，様の意味を持つ．式 2 は，現在の負荷が β · capload

稼働ノード数が最も少なくなるような関数 place を決定することが本研究で扱う問題である．
この問題は，仮想ノードをエージェント，物理ノーという閾値をどれだけ超過しているかを表す関数である．また，式 1 における c は次の式を満たす任意の定数である．

c > (N + 1)

ドを資源に見立てることで，資源配分問題として見る∑

capload (p)(3)

p∈Pことができる．文献 [8] や [9] では，ゲーム理論を用い

式 1 における総和の内部は，過剰な負荷を負うことることで資源配分問題を分散的に解く手法が解説さに対する負の評価と負荷の集約に対する正の評価をれており，本提案手法はこれを参考にしている．

加算したものとなっている．ここで係数 c を用いることで，負荷集約の面でどれだけ改善されてもオーバー

3. 2 ゲーム理論を用いた最適化手法

ロードが少しでも発生すれば全体の値は減少するよ

はじめに，システムのモデルを非協力ゲームとしてうな構造とする．さらに，この目的関数は N ステッ

モデル化する．非協力ゲームとは，複数のプレイヤープ先の未来までの評価を考えることにより，未来の状がそれぞれ自身の利得を高めるよう利己的に行動す況を見越した配置により高い値を与えるように設計る状況を考えたものである．ここでは，仮想ノードをされている．1 ステップの間隔は tw によって決定さプレイヤーとし，その行動を物理ノードの選択とすれる．この式を計算するには物理ノードの未来の負荷ることで非協力ゲームとしてモデル化する．このモを予測する必要があり，ここでは次の式によって予測

デルでは，各仮想ノードは自身の利得を高めるため，を行う．

利己的に物理ノードを選択することになる．ここで，load(p, t)

個々の仮想ノードの利己的な行動によってシステムが=load(p, 0)t(load(p, 0) − load(p, −tw ))tw(4)+最適化されるような構造を実現できれば，分散的に最適な配置を実現することができる．こうした構造を持この式による予測は，tw 秒前からの負荷の傾きが今つゲームはポテンシャルゲームと呼ばれ，その設計手後も継続されるという仮定に基づいている．正確な予法として Wonderful Life Utility (WLU) という手法

測方法であるとは言えないが，負荷の傾きが急激に変が存在する．WLU を用いて各仮想ノードに与える利動することのないワークロードにおいてはうまく機得を設計し，これを増加させるように振る舞わせるこ能すると思われる．とでシステムは最適化される．
ここで，WLU を用いて利得を設計するためにはシステムの状態を評価する目的関数を与える必要がある．次に，目的関数の設計と WLU により得られる利得関数について説明する．

以上に示した目的関数に WLU を適用することで利得関数を導出する．この結果，仮想ノード v の利得関数は次のように設計される．

uv (place) =N∑
i=0(−c · over2 (place(v), i · tw )+c · over′2 (place(v), i · tw )+load (place(v), i · tw )−load (place(v), i · tw )

22)

(5)′′

7. 自身のリクエストする移動が選択された場合，この手順を終了する．そうでなければ，相手側にキャンセルメッセージを送信してこのリクエストを取り消す．

over (p, t) や load (p, t) は仮想ノード v を除いた場

8. 受信リクエストに含まれる移動が選択された場

合の over(p, t)，load(p, t) の値を示す．この利得関数

合，その移動を開始してこの手順を終了する．こを各仮想ノードに与えることでポテンシャルゲームがのとき実行している移動が存在すれば，相手側に構築され，仮想ノードの自律的な移動による式 1 のキャンセルメッセージを送信することでこれを中最大化が実現される．

断してから選択された移動を開始する．

9. 現在実行中の移動が選択された場合，この手順4 仮想ノードの転送を終了する．

ここまで，仮想ノードに与える利得関数について解10. 自身の持つ仮想ノードの移動が選択された場

説した．仮想ノードがこの値を増加させるように移動合，相手側にリクエストを送信してこの手順を終することで，物理ノードのオーバーロードは回避さ了する．ただし，この移動先が自分自身，つまりれ，稼働ノード数は減少する．しかし，仮想ノードの移動しないことが最も良い場合についてはリク

移動は物理ノードの帯域を消費するため，全ての移動エストの送信を行わず，さらに現在実行中の移動を実行することは難しい．このことから，本提案手法を中断してからこの手順を終了する．

において各物理ノードは，単位時間当たりの利得の基本的には，各物理ノードはこの手順を一定の時間間増分が最大であるような移動を 1 つ選択し実行する．

隔で実行する．この時間を短く設定するほど負荷変動つまり，利得の増分を転送にかかる時間で割った値をに対して機敏に反応できると考えられる．さらに，あ計算し，これが最大である移動が選択されることになる仮想ノードの移動が終了したとき，キャンセルメッる．このような基準で選択するのは，目的関数値の素セージや拒否メッセージを受け取ったときにもこの手早い増加を実現するためである．ここで，各物理ノー順を実行する．これによって必要な移動を素早く完了

ドは自身の保持する仮想ノードの移動のみを考えるすることができる．のではなく，他の物理ノードからリクエストされていこの手順を用いた場合，何度も同じ物理ノードへとる移動も含めて最良の移動を選択する．また，現在リクエストを送信してその度に拒否されるという状実行している移動よりも良い移動が存在する場合は，態に陥る可能性がある．これは，送信先がリクエスト現在の移動を中断してこの移動を実行する．次に，物された移動よりも良い移動を実行している場合に発理ノードが実行する具体的な手順を実行する．

生し，この移動が終了するまでリクエストが採用され

1. 空のリストを用意し，受信したリクエストに含まれる移動情報をこれに追加する．

2. 自身が保持する仮想ノードについて考えられる全ての移動情報をリストに追加する．

3. 現在行っている移動が存在すれば，この情報をリストに追加する．

る可能性は無い．無駄なリクエストの送信による時間の浪費を避けるため，ある移動を選択するかどうかを送信先が現在行っている移動を考慮して判断する．自身がリクエストしようとする移動と送信先が現在行っている移動を比較し，後者のほうが良い場合はリクエストを送信しても採用される見込みがないためこう4. 自身が送信し，まだ返信のないリクエストが存した移動は除いて考える．自身のリクエストする移在すればこの移動情報をリストに追加する．

動のほうが良い場合でも拒否される可能性はあるが，5. リストの中から最も良い移動を 1 つ選択する．

その後送信先の物理ノードはより優れた移動を実行し6. 受信リクエストの中で選択されなかったものにているはずであるから，拒否されるのは 1 度のみと対して拒否メッセージを返信する．

なる．この方法によって無駄なリクエストの送信を防ぎ，効率よく仮想ノードを移動させることができる．に示す．図 1 は経過時間に対して稼働ノード数が変動

前述のような，移動させる仮想ノードの効率的な選する様子を示したものである．稼働ノード数は負荷の択に加え，本提案手法では移動のコスト自体の削減も変動に応じて増減しており，低負荷時には稼働ノード考える．具体的には，仮想ノードが移動する際にデー数の減少による省電力化が達成されている．本シミュ

タを移動元に残しておき，再び同じ物理ノードに戻る

レーションの設定における最大の負荷は物理ノードときには差分情報の転送のみで済むようにするという800 台分のキャパシティと等しいことから，ここでは方法により転送データ量を削減する．書き込みの少な

常に 800 台の物理ノードを稼働させた場合に対していワークロードにおいて移動のコストは大幅に減少

どれだけ稼働時間が削減されているかを省電力化の指すると思われる．この方法は仮想ノードが過去のデー標として考える．図 1 に示される 3 日目からの 7 日

タの残る物理ノードを選択しなければ効果はないが，間のデータについてこの値を求めたところ，16.6%の本提案手法では利得を素早く上昇させられるような稼働時間が削減されているという結果となった．こ移動が優先して選択されるため，こうした転送コスト

こでは負荷の最小値と最大値に 4 倍の差がある設定の少ない移動は優先して選択されると予想される．の下でシミュレーションを行い省電力効果を確かめたが，負荷変動の幅が小さい場合では省電力効果も小さ5 シミュレーションくなると考えられる．

本研究では，提案手法がうまく動作することをシ

図 2 はリクエストに対する平均遅延時間と最大遅ミュレーションによって確かめる．このシミュレー

延時間を示している．平均遅延時間については最大ションで用いる具体的なパラメータについて説明すで 500ms 程度となるがその他のほとんどの部分はる．システムは 1000 台の物理ノードにより構成され，150ms 以内に収まっており，低い値に抑えられてい10000 個の仮想ノードが保持される．各物理ノードると言える．一方で最大遅延時間を見ると，負荷が最は，アクセス速度が 55MB/sec，容量が 500GB であ大となる時刻付近で非常に大きい値となっており，一るようなディスクをそれぞれ持つ．このシステムに，部の物理ノードでは大きな遅延時間が発生しているサイズが 500KB のファイルが 2 億個格納されていることが分かる．この値は最大で 50 秒以上となってお状況を考える．各ファイルに対するリクエストの数り，実際の運用ではこうした場合一部のリクエストをは，Zipf 分布に従う．このシステムに対し発生する破棄する事になると思われる．このように一部の物理リクエストの数は 1 日の周期で線形に変動し，午前ノードが過負荷状態となってしまうのは，過大な負荷0 時に最小，正午に最大となる．午前 0 時では 1 秒の保持を避けるために実行した移動が他の移動によっあたり 22000 回，正午では 1 秒あたり 88000 回のリて中断されてしまい，他の物理ノードを対象として再クエストが発生する．この設定の下で良好な省電力び移動をやり直すことになるためである．

性能を得るためには残されたデータを利用した転送コストの減少が必要不可欠であることが事前のシミュ6 結論と今後の課題

レーションで確認されている．このため，ここでは初

本研究では大規模分散ストレージシステムの省電力めの 2 日間にダミーの負荷を与えることであらかじ化手法を提案した．この基本的なアイディアは，ゲー

めデータの一部を各物理ノードに配置しておき，そム理論を用いることで仮想ノードを自律的に移動され以降のデータを収集する．ここで，ダミーの負荷せ，少数の物理ノードに集約させるというものであとは実際に応答を返す必要のないリクエストである．

る．この手法の利点として，中央コントローラーを用提案手法におけるパラメータは，N = 2，tw = 900，いる必要がないことや，柔軟なシステム構成が可能

β = 0.9 と設定されている．また，各物理ノードは前であることが挙げられる．シミュレーションによって述の手順を 1 分ごとに実行する．

提案手法の省電力化効果を確かめたところ，16.6%の上記の条件でシミュレーションを実行した結果を次稼働時間が削減されるという結果となった．しかし，遅延時間は改善されると予想される．
1000900

参 考 文 献700
600500400300200100023

図1456経過時間[day]789稼働ノード数の変化

60060000

平均遅延時間[ms]平均遅延時間最大遅延時間
50050000

40040000

300

30000

20020000

100

10000

0023456789経過時間[day]
図2

遅延時間

一部のリクエストに対する応答に大きな遅延が発生するという問題も残されている．今後の課題として，さらなる稼働ノード数の減少や遅延時間の改善を目的とした利得関数の改善，転送手順の改善が考えられる．また，β などの各パラメータの適切な設定方法を考える必要がある．これらの値をワークロードに対して適切に設定できれば更なる省電力化効果が得られ，[ 1 ] K. Hasebe, T. Niwa, A. Sugiki, and K. Kato.
Power-Saving in Large-Scale Storage Systems with
Data Migration. In Proceedings of the 2010 IEEE
Second International Conference on Cloud Computing Technology and Science, CLOUDCOM’10,pages 266-273, Washington, DC, USA, 2010. IEEE
Computer Society.
[ 2 ] F. Araujo, and L. Rodrigues. Survey on Distributed Hash Tables. Ph.D. dissertation, Universityof Lisbon, Lisbon, Portugal, 2006.
[ 3 ] D. Colarelli, and D. Grunwald. Massive arraysof idle disks for storage archives. In Proceedings ofthe 2002 ACM/IEEE conference on Supercomputing, Supercomputing’02, pages 1-11, Los Alamitos,CA, USA, 2002. IEEE Computer Society Press.
[ 4 ] E. Pinheiro, and R. Bianchini. Energy conservation techniques for disk array-based servers. In Proceedings of the 18th annual international conferenceon Supercomputing, ICS’04, pages 68-78, New York,NY, USA, 2004. ACM.
[ 5 ] E. Pinheiro, R. Bianchini, and C. Dubnicki. Exploiting Redundancy to Conserve Energy in Storage Systems. SIGMETRICS Perform. Eval. Rev. 34,1526. 2006.
[ 6 ] C. Weddle, M. Oldham, J. Qian, An-I A. Wang,P. Reiher, and G. Kuenning. PARAID: A GearShifting Power-Aware RAID. In Proceedings of the5th USENIX conference on File and Storage Technologies, FAST’07, pages 30-30, Berkeley, CA, USA,2007. USENIX Association.
[ 7 ] D. Harnik, D. Naor, and I. Segall. Low
power mode in cloud storage systems. Parallel andDistributed Processing Symposium, International,pages 1-8, 2009.
[ 8 ] R. Gopalakrishnan, J. R. Marden, and A. Wierman. An architectural view of game theoretic control. ACM SIGMETRICS Performance Evaluation
Review, vol.38, no.3, pp.31-36, Dec. 2010.
[ 9 ] J. R. Marden, and A. Wierman. Distributed welfare games. Operations Reserch, Vol.61, pp. 155168, 2013.
[10] D. Monderer, and L. Shapley. Potential games.
Games and Economic Behavior 14, 124-143, 1996.
[11] R. T. Kaushik, M. Bhandarkar. GreenHDFS:
Towards An Energy-Conserving, Storage-Efcient,Hybrid Hadoop Compute Cluster. In Proceedingsof the 2010 international conference on Power aware
computing and systems. HotPower 10.

最大遅延時間[ms]稼動ノード数800