DEIM Forum 2013 F10-4

大規模データベースにおけるアクセス局所性を利用した VM ライブマイグレーションスケジューリング手法の提案と評価
渉†石田横山 大作††

中野美由紀††

豊田 正史††

喜連川 優††† 東京大学大学院 情報理工学系研究科 〒 153–8505 東京都目黒区駒場 4-6-1†† 東京大学生産技術研究所 〒 153–8505 東京都目黒区駒場 4-6-1
E-mail: †{ishida,yokoyama,miyuki,toyoda,kitsure}@tkl.iis.u-tokyo.ac.jp
あらまし 本論文では大規模な OLTP を行うアプリケーションのエラスティシティを効率良く実現する手法を提案する。この手法ではアプリケーション性能のボトルネックとなりうるハイパバイザーとデータベースの負荷分散を協調して行う. 特にデータベースの負荷分散に関してはアプリケーションのアクセス分布とデータベースのキャッシュの類似度を考慮することによってデータベースのキャッシュミスによるアプリケーションの性能劣化を防ぎつつエラス
ティシティを実現する. 評価実験では実際にクラウドコンピューティング環境を模した実環境を構築し, TPC-C ベン
チマークを利用したアプリケーションを実行し, 提案手法によりアプリケーションの性能劣化を防ぎつつハイパバイ
ザーとデータベースの負荷分散が実行できることを確認した.
キーワード

クラウドコンピューティング, ライブマイグレーション, エラスティシティ

Wataru ISHIDA† , Daisaku YOKOYAMA†† , Miyuki NAKANO†† , Masashi TOYODA†† , andMasaru KITSUREGAWA††† Graduate School of Information Science and Technology, The University of Tokyo 4-6-1 Komaba, Meguro, Tokyo, 153–8505 Japan†† Institute of Industrial Science, The University of Tokyo 4-6-1 Komaba, Meguro, Tokyo, 153–8505 Japan
E-mail: †{ishida,yokoyama,miyuki,toyoda,kitsure}@tkl.iis.u-tokyo.ac.jp
Abstract In this paper, we are going to show controlling the elasticity of application servers and databases separetly can cause performance degradation of client applications. To solve this problem, we propose the schedulingmethod of live migration which utilizes VMs’ access locality. Then, we clear up the framework of the execution
environment of applications which use large scale database. Furthermore, we evaluate the proposed method with
OLTP in real environment.
Key words Cloud Computing, Live migration, Elasticity

1. は じ め にのミドルウェアとの連携が強く望まれている.
本論文では大規模な OLTP 処理を行うアプリケーションの

近年 Amazon EC2 [2], Rackspace [4], Microsoft Azure [3],エラスティシティを効率良く実現する手法を検討する. クラウ

Google Compute Engine [5] といった広く利用されているクラドコンピューティングでは Xen [6] や KVM [7] などの仮想化技

ウドコンピューティングサービスの大きな特色は計算資源を動術を利用して, エラスティシティの実現手法として VM ライブ

的に増減できるエラスティシティ(伸縮性) にある. e コマース

マイグレーション [1] が利用可能である. またデータベースに関やオンラインゲームなど, 利用者数やアクセスされるデータ量

しても Albatross [10], Zephyer [9] といったエラスティシティをの変動が大きく, 処理負荷が容易に予測できないウェブサービ

実現するための手法が提案されている. しかしより効率的にエスアプリケーションにおいてエラスティシティの重要性は高い.

ラスティシティを実現するためにはアプリケーションとデータ

一方, これらのアプリケーションでは OLTP(オンライントラン

ベースのエラスティシティを別々に考慮するのではなく協調さ

ザクション処理) が必要不可欠であり, クライアントアプリケー

せることが不可欠である. そこで, 本論文ではクライアントアプ

ションのエラスティシティを実現するにあたりデータベース等

リケーションのアクセス局所性を利用した負荷分散スケジュー

# of Users

Users

ことができる. 代表的な HV の実装として KVM [7] と Xen [6]がある.
アプリケーションサーバのエラスティシティを実現する方法
として VM ライブマイグレーションを紹介する. VM ライブ
マイグレーションとは HV 上で稼働している VM を停止させTimeることなく, 異なる HV 上に移す技術で Clark らによって提案された [1]. VM のメモリと CPU ステート, ハードウェアのス

VM

VM VM

VM

Hypervisor

Hypervisor

Hypervisor

OLTP

Database

Database

Database

テートを VM を止めずに段階的にマイグレート先の HV に転送することで行う. VM の動作中はメモリの書き換えが生じる
ため多くの場合メモリの再転送が必要となり, VM ライブマイグレーションにおいてはこのメモリ転送量の削減がマイグレー
ションのオーバーヘッドを減らす要となっている. VM ライブ
マイグレーションにおけるメモリの転送量の削減に関しては多Cloud Computing
Requirement for Rapid Elasticity

くの研究がなされており, 代表的なものに [11], [12], [13] がある.

VM のディスクイメージはマイグレーション元と先の両 HV が

図 1 対象とするクライアントアプリケーションの構成

アクセスできる仮想ディスクに保管することでマイグレーショ

Fig. 1 client application

ン後の VM のディスクアクセスを可能にするのが一般的であるが [14] のようにディスクイメージの転送も行うマイグレーショリング手法を提案し, 提案手法を実機により評価する.

ンも提案されている. VM ライブマイグレーションにより, ク

本論文の構成は以下のようになっている. 2. でアプリケー

ライアントの VM の HV への集約, 分散が可能になり VM がションサーバとデータベースサーバに関してエラスティシティ必要とする計算資源と HV が提供できる計算資源のバランスをを実現するための基本技術を説明する. 3. でアプリケーション

考慮し VM をライブマイグレーションにより再配置することでとデータベースを協調させた負荷分散を実現する際の課題を指エラスティックな計算資源をクライアントに提供することがで摘し, 4. でアクセス局所性を利用した負荷分散スケジューリン

きる.

グ手法を提案した後, 5. で実装方式について説明する. さらに

2. 2 DB のエラスティシティ

6. で提案手法の有用性を実機により評価し, 最後に 7. で結論をDB のエラスティシティの実現に利用可能な技術としては DB

述べる.

2. クライアントアプリケーションのエラスティ
シティ実現のための基本技術の負荷分散技術であるレプリケーションとテーブルパーティ
ショニングがある. レプリケーションは DB において更新クエ
リ, 参照クエリを共に受け付けるマスターノードと参照クエリのみを処理するスレーブノードを用意し, マスターノードの更図 1 に本論文が対象とするクライアントアプリケーションの新情報をスレーブノードに随時転送することによってスレーブ構成を示す. 対象とするアプリケーションは, 仮想化技術を利用からも最新の情報を取得可能にし参照クエリの負荷を分散させして VM(ヴァーチャルマシン) として HV(ハイパーバイザー)る手法である.

上に実装されるアプリケーションサーバ群と, データを管理す

テーブルパーティショニングは単一ノードで扱うにはデータ

る DB(データベース) サーバ群から構成される. 本節ではクラサイズが大きすぎるテーブルを DB システムの内部で複数のイアントアプリケーションのエラスティシティを実現するためテーブルに分割し複数ノードで管理することで負荷を分散するの技術としてアプリケーションサーバに関しては仮想化技術と手法である. レプリケーションと異なり更新クエリも複数台のVM ライブマイグレーション, データベースサーバに関してはノードに分散させることができる反面, 分割の仕方を工夫しな

レプリケーション, テーブルパーティショニングとマルチテナ

いと限定されたノードに負荷が集中してしまう可能性がある.

ントなデータベースで利用可能な Albatross [10] と Zephyer [9]を説明する.

2. 1 仮想化技術と VM ライブマイグレーション

マルチテナントな DB のエラスティシティに対しては DB テ
ナントのライブマイグレーション手法としては Sudipto らによる Zephyr [9] と Aaron らによる Albatross [10] が提案されてい仮想化技術は物理マシン上で稼働する HV がエミュレートしる. ここでマルチテナントな DB とはそれぞれ独立した契約ポ

た仮想的な物理環境上で VM を稼働させるもので, VM は自らリシーを持つ複数クライアントに物理インフラを共有させるマが仮想化されていることを意識せず, HV を物理マシンと認識

ルチテナントな DB のことである. Zephyr はマイグレーションし稼働する. クラウドプロバイダは仮想化技術を利用しクライ

元とマイグレーション先は DB のテーブルを含め何も共有してアントに提供する計算資源を VM として扱うことで, 物理的ないない状況 (Shared Nothing) を前提としており, ライブマイグ

設定などを必要とせず, クライアントに迅速に計算資源を提供

レーションの前後を通してトランザクション処理の中断を生じできる. またクライアントはクラウドプロバイダが持つ物理イ

させないためにライブマイグレーションが始まる時点で既に実ンフラを意識せずに自分専用の計算資源として VM を利用する行が始まっているトランザクションはそのままマイグレーショ

② live migrate VM1 and VM2ン元で行い, ライブマイグレーション中に新たに発生したトラ
ンザクション処理はマイグレーション先で行う. マイグレーショ① HV1 high-load
VM1 VM2 VM3 VM4ン中はトランザクションを完遂させるのに必要なデータ揃って

HV1

HV2

DB1

DB2

VM1 VM2 VM3 VM4VM1 VM2

HV1

HV2

DB1

DB2

いないため, そのようなデータはオンデマンドにマイグレーショ
ン元から読み込む手法を提案している. Albatross も Zephyr と同様マルチテナントな DB のライブマイグレーションであるが,Zephyr とは異なり各物理ノードがストレージを共有している③ DB1 high-load
VM3 VM4
HV1

HV2

DB1

DB2

④ Change DB path to DB2システムを前提としている. Albatross では VM ライブマイグ
レーションのメモリの転送と同様, トランザクションテーブル
をイテレーティブに転送することでライブマイグレーションのVM1 VM2⑤ Cache miss

図2

想定環境

前後を通してトランザクション処理の中断を避ける.

3. クライアントアプリケーションのエラスティ
シティを実現する際の課題
本節ではアプリケーションサーバである VM, それをホストする HV, そして DB から構成される仮想化環境 (2) でクライア
ントアプリケーションのエラスティシティを実現するための課
題を考察する. 議論を簡単にするため VM 群は V M 1〜V M 4,

HV を HV 1, HV 2, DB を DB1, DB2 とする. DB1 と DB2はレプリケーションにより, どちらを参照しても同様の結果が得られるとする. はじめすべての VM 群は HV 1 上で稼働し,DB1 を参照している. ここで VM 群の負荷が上昇し, HV 1 が十分な計算資源を提供できなくなった場合を考える (図 2 À部).

VM 群のうち V M 1 と V M 2 を HV 2 にライブマイグレートすることで HV 1 の負荷分散をすることができる (図 2 Á部). 一
方負荷分散後, VM 群はより計算資源を得る, すなわち DB1 への負荷が増加する (図 2 Â部). ここで DB1 の計算資源が足りないと, アプリケーション全体としてはスループットが上がらない. そこで V M 1, V M 2 の接続する DB サーバを DB1 から DB2 に切り替えると, DB サーバの負荷も分散する (図 2 Ã部). しかし, V M 1, V M 2 の利用するデータが DB2 のキャッシュにない場合, キャッシュミスが発生し, DB1 へリクエスト
し続ける場合と比較し, クライアントアプリケーションの性能が劣化する (図 2 Ä部). ここでは HV が先にボトルネックとなる状況を想定したが, 実環境では HV と DB のどちらが先にボトルネックになるかは環境と負荷に依存し, 一方の負荷分散が他方の負荷増大を招く恐れがある.

3. 1 キャッシュミスによるアプリケーション性能劣化の検証
実際に VM ライブマイグレーションと DB の接続変更をエ
ラスティシティの実現のために実行した際, キャッシュが温まっていない DB に接続変更をしてしまうことでアプリケーションの性能が劣化することを確かめた. VM 内で稼働させるアプリ
ケーションとして TPC-C を一部改変したものを用いた (アプリケーションの詳細については後述する). VM の負荷変化はDB への接続数の変化によって実現する. 検証環境を図 3 に示す. まず HV 1, HV 2 上で合計 24 台の VM を稼働させ, 上述のアプリケーションを接続数 4 として稼働させる. はじめ全ての VM は DB1 を参照し, DB1 のキャッシュは温まっている.
全ての VM の接続数を 50 秒毎に 4 ずつ接続数が 16 になるまで上昇させ負荷を増大させていく (図 3 À部). 負荷上昇の後,

HV がボトルネックとなるため, 2 台の HV からそれぞれ 4 台,
合計 8 台の VM を HV 3 にマイグレートし HV の負荷分散を行う (図 3 Á部). マイグレーションの後 3 台の HV 上でそれぞれ 8 台の VM が稼働する状態となる. HV の負荷分散によってVM に与えられる計算資源が増加するため, VM の DB1 へのクエリ頻度が高まり今度は DB1 の負荷が上昇する. そこで 24
台の VM のうち半数の接続する DB を DB2 に変更し, DB の負荷分散を行う (図 3 Â部). このとき DB2 のキャッシュが温まっている場合と温まっていない場合の 2 通りで計測を行う.

DB2 のキャッシュが温まっている場合と温まっていない場
合での, 全 VM のアプリケーションの TPM(transaction perminites) と平均クエリ処理時間 (delay) の平均の時間変化の様子を図 4 に示す. 横軸は計測を開始してからの時間である. 0 から 200 秒までは VM の負荷を上昇させている様子, 200 秒から

270 秒までは VM のマイグレーションを行った後の様子, 270
秒から 320 秒までが DB の接続先変更を行った後の様子となっている. グラフから, キャッシュが温まっていない場合, DB2に接続変更をした後, キャッシュが温まっている場合に比べてTPM は約 40%減少し, 平均クエリ処理時間は約 3 倍増加する
ことがわかる. また 100 秒から 200 秒の間, 接続数は増加しているにも関わらず TPM が 50 秒から 100 秒の間よりも減少している. これは VM の負荷増大により HV がボトルネックとな
り VM に十分な計算資源を提供できていない事による.
以上より, アプリケーションのエラスティシティを実現する
ために VM ライブマイグレーションと DB の接続先変更を単純に利用しただけではアプリケーション性能を大幅に劣化させてしまうことがわかる. このため HV と DB を協調させること
でアプリケーションの性能を維持しつつ, エラスティシティを実現するフレームワークが必要である.

4. エラスティシティ実現のための負荷分散スケ
ジューリング手法
本論文ではアプリケーションの性能を維持しつつエラスティ
シティを実現するためのアプリケーションのアクセス局所性を考慮した実行時負荷分散フレームワークを提案する. 負荷分散
フレームワークを考えるに当たって, 負荷分散をトリガーする基準を決定しなければいけない. クライアントとクラウドサー
ビスのプロバイダとの間にはサービスレベル契約 (SLA) が結荷分散を行なってもアプリケーション性能が向上する保証がな
いため本手法の適用範囲外とし負荷分散を行わない.
①HV1負荷増大②ライブマイグレーション (計8台)
12台

...



12台

クラウドコンピューティングの特徴にもあるように, クラウ
ドコンピューティングにおいてクライアントの使用する計算リ

...



③DBの接続先変更 (計12台)

ソースはモニタリングされており, OLTP では各 VM 内の発行するクエリの発行レートとクエリの処理にかかった時間を

DB を通して取得することができるため, 本手法では予め設定

キャッシュミス

した SLA を遵守するための閾値 sla threshold を VM のアプ

リケーション性能が下回った場合に負荷分散をトリガーする.
図3

計測環境

負荷分散がトリガーされた場合, HV と DB のどちらがボトル
ネックとなっているかを判断する. HV と DB のどちらが VMの性能のボトルネックになっているかは HV と DB のリソース使用率が基準値 hv heavy threshold, db heavy threshold を上回っているか否かで判定する. リソース使用率は例えば CPU,
メモリ, ネットワークなどの利用率から算出することを想定しているが, アプリケーションによってボトルネックの原因となるリソースは異なるため, 具体的な算出方法は 4 章でアプリケー
ションの詳細とともに議論する. HV と DB のリソース使用率が基準値 hv heavy threshold, db heavy threshold を下回っているにもかかわらず, アプリケーション性能が sla thresholdを下回っている場合は 2 つ目の指針に基づき, 負荷分散を行わない.
ボトルネックが HV の場合は VM ライブマイグレーション

図4

キャッシュミスによる性能劣化の様子

を, DB の場合は VM の DB 接続先を変更する. 負荷分散スケ
ジューリングフレームワークのアルゴリズムをアルゴリズム 1

ばれることが一般的であるため, 負荷分散のトリガーは SLA がに示す.

遵守されるように行われる必要がある.
負荷分散アルゴリズムは次の 2 つの指針に基づいて設計する.

Algorithm 1 負荷分散スケジューリングフレームワーク（ 1 ） なるべく少ない HV と DB で全ての VM の SLA を//threshold for load balancing trigger守る

sla threshold（ 2 ） ボトルネックがはっきりしないときは SLA を守れな//threshold to judge HV is the bottleneck.

くても負荷分散を実行しない.

1 つ目の指針は VM のスケールインを想定したものである.

hv heavy threashold//threshold to judge DB is the bottleneck.
db heavy threshold

本論文では負荷分散によるスケールアウトのみを扱っているが,// array of virtual machine in the system vms

クラウドコンピューティングではスケールインも同時に考慮し

loop

なければいけない. VM のアプリケーション性能を最大化するには, システム内の全 HV 上の VM の台数が均一になるように

for all vm in vms do
if vm.perf ormance < sla threshold thenVM を HV 上に配置し, DB もキャッシュが温まっていることを

hv = get hv(vm)

前提にすれば, システム内の全 DB に接続する VM の台数が均

db = get db(vm)

一になるようにすればいい. しかしクラウドコンピューティン

if hv.load() > hv heavy threshold thenhv load distribution(vm)グにおいて, 金銭的なコストを抑えるため, SLA を満たせる範

end if

囲で利用するクラウドコンピューティングの計算資源を最小化

if db.load() > db heavy threshold then

することが望ましい. そのため負荷分散においてもなるべく少ない HV と DB で全ての VM の SLA を守るように設計する.

2 つ目の指針はライブマイグレーションと接続先変更の頻発を防ぐためである. ライブマイグレーションと接続先変更にもコストがあるため, 負荷分散することによってアプリケーショ

db load distribution(vm)end ifend ifend forend loop

ン性能が向上することが確かな場合以外は負荷分散を避けるべきである. 具体的には本提案手法が想定していないボトルネッ

4. 1 HV の負荷分散

クによりアプリケーション性能が SLA を守れていないとき負HV が ボ ト ル ネック と 判 定 さ れ た 場 合, VM の ラ イ ブ マ

全 DB に 対 し 現 在 の リ ソ ー ス 使 用 率 と マ イ グ レ ー ト す

イグレーションを検討する. マイグレーション先の決定ア
マ イ グ レ ー ション

る VM が 消 費 す る と 予 想 さ れ る リ ソ ー ス 使 用 率 を 足 し た

先 の 決 定 の た め ま ず 全 HV に 対 し 現 在 の リ ソ ー ス 使 用 率

値 ( estimated resource usage ) と VM のアクセス範囲とと マ イ グ レ ー ト す る VM が 消 費 す る と 予 想 さ れ る リ ソ ー

DB の キャッシュの 類 似 度 を 算 出 す る ( access similarity

ス 使 用 量 を 足 し た estimated resource usage を 算 出 す る.

).

hv heavy threashold を下回る estimated resource usage を

0 以 上 1 以 下 を 満 た す よ う に す る.

持つ HV の中で estimated resource usage が最大となるも算 出 方 法 に つ い て は 後 述 す る.

ル ゴ リ ズ ム を ア ル ゴ リ ズ ム 2 に 示 す.

access similarity も リ ソ ー ス 使 用 率 と 同 様 正 規 化 し類似度の具体的なestimated resource usageのをマイグレーション先とする. estimated resource usage

が db heavy threshold を 上 回 る DB と access similarity

が hv heavy threashold を下回る HV をマイグレーションが db similarity threshold を 下 回 る DB を 除 外 し て 残っ

先の候補とするのは, マイグレート先でも HV のリソース不た DB の 中 で α ∗ estimated resource usage + (1 − α) ∗足が生じることでアプリケーション性能が sla threashold

access similarity の値が最大となる DB を接続変更先とすを 下 回 り ラ イ ブ マ イ グ レ ー ション が 連 鎖 す る の を 防 ぐ

る. α を小さくするとリソース使用率よりも VM のアクセス範た め で あ る.

ま た hv heavy threashold を 下 回った 中 で囲と DB のキャッシュの類似度を重視して DB の接続変更先を

estimated resource usage が最大となる HV をマイグレー

決定する. α を大きくした場合は VM のアクセス範囲と DB のト先として選択するのは, 全 VM のアプリケーション性能を

キャッシュの類似度よりもリソース使用率を重視して DB の接

sla threashold 以上にするために稼働させる必要がある HV の続変更先を決定する. 接続変更先が見つかり, かつ接続変更の台数を最小化するためである.

コストが change db threshold が下回っている場合接続変更を

マイグレーション先が見つかり, かつマイグレーションのコ行う. 接続変更先が見つからなかった場合または接続変更のコ

ストが migration threshold が下回っている場合マイグレー

ストが高すぎる場合はシステム全体でアプリケーションの要求

ションを行う. マイグレート先が見つからなかった場合またはに応えられるだけの計算資源がないとして負荷分散を行わない.

マイグレーションのコストが高すぎる場合はシステム全体でア
プリケーションの要求に応えられるだけの計算資源がないとしAlgorithm 3 DB の負荷分散アルゴリズムて負荷分散を行わない.

//array of database in the system

Algorithm 2 HV の負荷分散アルゴリズム

dst candidates = []//array of hypervisor in the systemdbs
for all db in dbs do//estimate the db’s load when vm is migrated

hvs
dst candidates = []for all hv in hvs do//estimate the hv’s load when vm is migrated
estimated resource usage = hv.load() + vm.load()
if estimated resource usage < hv heavy threshold then
add hv to dst candidates

estimated resource usage = db.load() + vm.load()//calculate access similarity between vm’s access pattern anddb’s cache
access similarity = similarity(db, vm)
if estimated resource usage < hv heavy threshold andaccess similarity > db similarityt hreashold thenadd db to dst candidates

end ifend for//choose the hv whose load is highest in dst candidates.
//destination can be NULL if dst candidates is empty
destination = highest load(dst candidates)
if destination and migration cost < migration thresholdthenvm.live migrate(destination)else//give up hv load distribution
end ifend ifend for//choose the db whose score is highest in dst candidates.
//destination can be NULL if dst candidates is empty//score is calculated by//score=α ∗ estimated resource usage + (1 − α) ∗access similarity//destination can be NULL if dst candidates is empty
destination = highest score(dst candidates)
if destination and change db cost < change db thresholdthenvm.change db(destination)

4. 2 DB の負荷分散
DB がボトルネックと判定された場合, DB の接続変更を検討
する. DB の接続変更先の決定アルゴリズムをアルゴリズム 3 に示す. DB の接続変更先の決定はリソース使用率と VM のアクセス範囲と DB のキャッシュの類似度の２つの指標から決定される. どちらをどれだけ重視するかはパラメータ α (0 <= 1)=α<によって設定する.

else//give up db load distribution
end ifCollect infomation

5. 提案手法の実装

from VM, HV, DB

Controller

Triger live migration
Triger DB connection change

5. 1 OLTP を行うアプリケーションの実装

VM1 VM2VM3 VM4VM5 VM6

HV1

HV2

HV3

提案フレームワークの実装と評価のため VM 内で稼働させるアプリケーションとして TPC-C を一部改変したアプリケー
ションを実装し利用した. TPC-C は OLTP システムの評価を目的としたベンチマークであり, 商取引とサプライチェーン管理を模擬したアプリケーションとなっている. 注文, 支払, 注文
確認, 発送, 在庫確認の 5 種類のクエリを規定の割合に従いデー

リのうち, 注文, 支払, 発送はデータベースの更新を伴うクエリ,
注文確認, 在庫確認は参照のみを行うクエリであるが, TPC-C

HV4

HV5

VM128
HV6

HV7

HV8

OLTP
DB1

DB2

DB3

DB4

DB5

DB6

DB7

DB8

W = 128

W = 128

W = 128

W = 128

W = 128

W = 128

W = 128

W = 128

図 5 構築したクラウドコンピューティング環境

タベースに対して発行し, 注文クエリが 1 分間に何回処理でき
るか (TPMC) で OLTP システムの評価を行う. 5 種類のクエ

VM6

表1

計算機環境

Table 1 Conputational Environment
HV(*8 台)CPU Intel Xeon E5530 2. 4Ghz
memory 24GBの規定値では更新を行うクエリが全体の約 95%を占めている.

OS Debian 6. 0. 4 Squeeze

提案フレームワークにおいてデータベースの負荷分散はレプリ

kernel Linux 2. 6. 32

ケーションによって行う. レプリケーションは参照クエリの負qemu qemu-kvm-1. 0. 1

荷分散を行うもので, 更新クエリはマスターノードで処理されnetwork Intel 82599EB 10Gbit

た後, 全てのスレーブノードにログが転送され再実行されるたCPU 2 virtual CPU

VM

め, 負荷分散されない. そのため TPC-C を規定値通り実行しmemory 1GBた場合, データベースのレプリケーションによる負荷分散の効

OS Ubuntu 11. 04

果を期待できない. そこでデータベースのレプリケーションがkernel Linux 3. 0. 0
blk driver virtio-blk

効果を持つアプリケーションを模擬するため TPC-C の 5 種類

network virtio-netのクエリのうち参照クエリのみを実行するアプリケーションとした.

TPC-C ではデータベースに warehouse テーブルを W 個分

DB(*8 台)CPU Intel Xeon E5530 2. 4Ghz
memory 24GBOS Debian 6. 0. 5 Squeeze

構築し, クライアントは発行するクエリ毎にランダムに W 個のkernel Linux 2. 6. 32

中から warehouse を選び, その warehouse テーブルに対してクエリを発行する. そのため複数の TPC-C クライアントを実行

DB MySQL 5.5
network Intel 82599EB 10Gbit

した場合, 各クライアントのアクセス範囲は全ての warehouseに対して均一なものとなる. 本論文では各クライアントは同一のアプリケーションを実行するが, アクセス範囲は異なり局所性を持つクラウドコンピューティング環境を対象としているため, クライアントに与えるパラメータとしてクエリを発行する

warehouse を W 個の warehouse の中から指定できるようにすることでクライアントによるアクセス範囲の違いを実現した.
クライアントはパラメータとして与えられた warehouse からランダムに選んだ warehouse に対してクエリを発行する.
負荷変化に関しては TPC-C クライアントにパラメータとして与えられる connection を変化させることで実現する.

connection は TPC-C クライアントが DB に対して張る接続数で, TPC-C クライアント内で connection 個のスレッドを立て, その全てで DB に対してクエリを発行する. 実装したアプ
リケーションでは connection と接続先の DB を動的に外部から変更できるようにした.

5. 2 計 測 環 境
上述のアプリケーションを稼働させるシステムとして, クラ
ウドコンピューティング環境を模擬した実環境を構築した (図5). システム内に HV と DB はそれぞれ 8 台存在し, VM のディスクイメージは 128 台分用意した. VM のディスクイメー
ジの保管場所として glusterfs を用いて 8 台のファイルサーバ

で分散ファイルシステムを構築し, 各 HV はそれをマウントすることで任意の HV 上に任意の VM を起動できる環境を構築
した. またコントローラを介して全ての VM の起動, 停止の一元管理を可能にすると伴に, ライブマイグレーションも行うことができるようにした. さらに VM 内で稼働させるアプリケー
ションの起動, 停止, アプリケーション性能の監視, 接続数の変更, 接続 DB の変更もコントローラを介して実行できる. このコントローラ上に提案フレームワークを実装し, VM 群の負荷上昇に合わせて自動的に HV と DB の負荷分散を実行するようにする. 計算機環境を表 1 に示す. HV, DB はスイッチを介して 10Gbit イーサネットで接続されている.

5. 3 各閾値の決定
負 荷 分 散 を 検 討 す る ア プ リ ケ ー ション 性 能 の 閾 値

sla threshold は平均クエリ処理時間 500ms とした. 構築した環境で HV がボトルネックとなる状況と DB がボトルネックとなる状況のもとで事前評価を行い実装したアプリケーション性能のボトルネックは HV と DB の CPU 使用率から判定できることが確かめられた. よって提案アルゴリズムにおいて HV と DBの負荷状況は CPU 使用率で判定する. HV がボトルネックとなる状況での計測結果で平均クエリ処理時間が 500ms を上回る

データ点のうち HV の CPU 使用率が最小のものは 88.6%, DB

cache increment は 1/17 とした. また DB キャッシュと VM ア

がボトルネックとなる状況での計測結果で平均クエリ処理時間がクセス範囲の類似度は VM アクセス範囲に含まれる warehouse

500ms を上回るデータ点のうち DB の CPU 使用率が最小のもの DB キャッシュでのカバー率とし, 次の式で計算する.

のは 80.1%であったため, リソース使用率は 0 以上 1 以下となる
よう hv heavy threshold = 0.88, db heavy threshold = 0.80

V = warehouses which a VM accessesとした. また estimated resource usage の算出は計測環境内
で VM1 台のみを稼働させた時の結果を利用する. 例えばリソース使用率 0.5 の HV に接続数 4 の VM をマイグレートするとき, VM1 台での計測の接続数 4 のときの HV の CPU 使用

C = warehouses in DB cacheV∩Csimilarity =|V|

率 0.12 より, estimated resource usage = 0.5 + 0.12 = 0.62

本論文では db similarity threshold = 0.5 とし VM のアクとなる. DB の接続変更先の決定に VM のアクセス範囲と DBセスする warehouse の半分以上がキャッシュミスを起こすこと

キャッシュの類似度のどちらを優先するかを示す指標である αが予測される場合, DB の接続先変更を中止するようにした.

はどちらも同等に評価する 0.5 と設定した.

5. 4 DB キャッシュと VM アクセス範囲の類似度と DBの接続先変更を行う際の閾値の決定
提案フレームワークでは DB キャッシュの情報は DB から取得することを想定しているが, 本論文では実装を簡便に済ませ

Algorithm 4 DB キャッシュのシミュレーション//array of database in the systemdbs
loop
for all db in dbs do

るためアクセス単位を warehouse として VM のアクセス範囲

vms = select vms connected to dbの情報と接続先 DB の情報よりコントローラが DB キャッシュ

for all vm in vms doの状態を実行時にシミュレートする.
シミュレーションのアルゴリズムをアルゴリズム 4 に示す. まず各 DB についてキャッシュの状態を更新する. DB に接続する

VM を取得し, 接続する VM がアクセスする warehouse を取得

warehouses = get warehouses accessed by vm
for all w in warehouses do
if db cache doesn’t include w thendb.cache[w] = 0
else

する. DB のキャッシュ情報はコントローラ内で warehouse のif db.cache[w] < 1.0 then

ID をキーとするハッシュとして実装され 0 から 1 の値をとる.

if db.diskread < disk access threshold then0 は VM からアクセスされる可能性があるが, DB キャッシュdb.cache[w] = 1.0にそのデータが存在しない可能性が高いことを示し, 1 は DB

else
db.cache[w]+ = cache increment/length(warehouses)

キャッシュにデータ存在する可能性が高いことを示す. 取得した

end ifwarehouse, w がキーとして存在しない場合, キーを w, 値は 0としてキャッシュ情報を更新する. w がキーとして存在する場合,

w に対応する値が 1 未満の場合に限りキャッシュ情報の更新をする. 1 以上の場合は w のデータはキャッシュ上に存在すると判断しさらなる更新は行わない. キャッシュ情報の更新のため, まずDB のディスクアクセススループットを調べる. スループットが予め定めた disk access threshold を下回っている場合, キャッ

end ifend ifend forend forend forsleep 1 second
end loop

シュ上にデータがあるためにディスクが発生していないと判断し, 値に 1 とし更新する. スループットが disk access threshold
を上回る場合は, 予め定めた cache increment を VM がアクセスする warehouse の総数で割り, キーに対応する値に足す.

6. 大規模環境における実負荷を想定した提案手法の評価

VM がアクセスする warehouse の総数で割るのは, アクセスす大規模環境において実負荷を想定した負荷変動をアプリケー

る warehouse の数が増えると w に対するクエリ発行量が相対ションに加えた場合, 提案フレームワークがアプリケーション

的に減少するためキャッシュにデータがのるまでに時間がかか

性能の劣化を防ぎつつエラスティシティを実現できるか評価しると予想されるためである.

た. 計測状況を図 6 に示す. VM は 4 台の HV 上に 32 台ずつ,

disk access threshold と cache increment を決定するため,合計 128 台稼働させ, 全ての VM 内でアプリケーションを実行

キャッシュをクリアした状態で事前計測を行った. その結果,した. はじめ全ての VM は DB1 に接続するようにした. VM

アクセスする warehouse 数に比例してアプリケーション性能のアクセス分布は 8 通りのアクセスパターン (a, b, c, d, e, f,が収束するまでの時間が長くなることがわかり, 収束時には

g, h) を用意し, VM1 16 は a, VM17 32 は b...VM113 128 は h

ディスク読み込み帯域は 1.0MB/sec 以下となり, warehouse1と VM16 台をグループとしてアクセスパターンを割り当てた.

つに対応するデータがキャッシュにのるまでに 17 秒かかるこ

それぞれのアクセスパターンは 8 つ warehouse を含み, それぞとがわかった. そのため disk access threshold は 1.0MB/sec,

れ共通部分はない. 各 DB は図 6 の DB cache 部に示したアクAccess pattern:[c] [d]VM33~VM64 VM65~VM96 VM97~VM128

HV1

HV2

[e] [f]HV3[g] [h]HV4Application load
HV load balancing

HV5

HV6

16

Connection[a][b]
VM1~VM32

Choose a vm to

add connection
randomly
HV8 every seconds

HV7

1

DB load balancing

0

600

Time

散のためには HV と DB の両者を協調させた負荷分散手法が必要となる. そこで HV と DB を協調させたアプリケーションのアクセス局所性を考慮した実行時負荷分散手法を設計した.

DB2

DB3

DB4

DB5

DB6

DB7

DB8

提案手法では, HV と DB の負荷分散を協調して行い, DB の

[b]

[c]

[d]

[e]

[f]

[g]

[h]

負荷分散の際にアプリケーションのアクセス分布と DB キャッ

W = 128

W = 128

W = 128

W = 128

W = 128

W = 128

W = 128

DB1
DB cache :[ a,b,c,d,e,f,g,h ]W = 128

に関する研究は多くなされている. しかしより効率的な負荷分

図 6 大規模環境における実負荷を想定した計測環境

シュの類似度を考慮することでキャッシュミスによるアプリケー
ションの性能劣化を防ぎつつ負荷分散を行う. 評価実験により提案する手法によってアプリケーションの性能劣化を防ぎつつ負荷分散が行えるか検証を行った. その結果, 性能目標を維持しつつ HV と DB の負荷分散が実行できることが確認された. さらに大規模環境を想定した 128 台の VM が稼働する環境下でVM の負荷を上昇させたときの提案手法の有効性も確認された.
最後に今後の課題をまとめる. 本論文では実装を簡便に済ますため DB のキャッシュ情報を DB から直接得るのではなく, 負荷分散を行うコントローラが VM のアクセス範囲を利用し, 推定するよう実装したがより正確な DB キャッシュの情報を取得するため DB から直接キャッシュ情報を得るようにしたい. またエラスティシティの実現方法として負荷分散にのみ着目したが, アプリケーションの負荷が減少した場合は HV と DB の負荷を集約することでクラウド環境のリソース利用率を下げられ
図7

提案フレームワークによるアプリケーション性能の時間変化ると考えられる. アプリケーションの増減に対して適切に計算資源を割り当てる手法についても今後検討して行きたい.

セスパターンに含まれる warehouse のデータがキャッシュに存在するように温めた. 負荷の上昇は毎秒 128 台の VM の中からランダムに 1 台選び接続数を 1 増やすようにした. また比較対象としてアプリケーションのアクセス分布と DB キャッシュの類似性を考慮せず, DB のリソース利用率のみを指標として DBの接続変更先を決定した場合での計測も行った.
計測の結果を図 7 に示す. 横軸は計測を開始してから時間で上から全 VM の平均 TPM と平均クエリ処理時間を表す. グラフより提案手法においてはアプリケーションのアクセス分布とDB キャッシュの類似性を考慮して負荷分散を行うことで大規模環境においても平均クエリ処理時間を 500ms 以下に抑えられていることがわかる. また TPM に関してもリソース使用率のみを指標として負荷分散をした場合に比べて最大 1.8 倍とな
り, 性能劣化を抑えてエラスティシティを実現できていることが確認できた.

7. ま と め
本論文ではクラウドコンピューティングにおいてデータイン
テンシブなアプリケーションのエラスティシティを実現するために, アプリケーションのアクセス局所性を考慮した実行時負荷分散手法を提案した. データインテンシブなアプリケーショ
ンでは利用者数の変動, アクセスされるデータ量の変動が大き
く, 処理負荷が容易に予測できないため, 負荷の上昇に合わせて実行時に負荷分散を行うことが重要である. クラウドコン
ピューティングにおいて HV と DB の両者がアプリケーション
性能のボトルネックになる可能性があり, それぞれの負荷分散

文

献[1] C. Clark, K. Fraser, Steven Hand, et al. Live Migration of
Virtual Machines NSDI, 2005.
[2] Amazon Elastic Compute Cloud(Amazon EC2).
http://aws.amazon.com/ec2/.
[3] Microsoft azure. http://www.microsoft.com/azure[4] rackspace http://www.rackspace.com/[5] Google Compute Engine.
https://cloud.google.com/products/compute-engine[6] xen http://xen.org/[7] KVM http://www.linux-kvm.org/page/Main Page
[8] TPC-C http://www.tpc.org/tpcc/[9] Aaron J.Elmore, Sudipto Das, Divyakant Agrawal, Amr
El Abbadi Zephyr: Live Migration in Shared Nothing
Databases for Elastic Cloud Platforms SIGMOD, 2011.
[10] Sudipto Das, Shoji Nishimura, Divyakant Agrawal, Amr El
Abbadi Albatross: Lightweight Elasticity in Shared Storage
Databases for the Cloud using Live Data Migration VLDB,
2011.
[11] Jie Zheng, T.S.Eugene Ng and Kunwadee Sripanidkulchai.
￥em Workload-Aware Live Storage Migration for Clouds.
VEE, March 2011.
[12] Samer Al-Kiswany, Dinesh Subhraveti, Prasenjit Sarkar andMatei Ripeanu. ￥em VMFlock: Virtual Machine CoMigration for the Cloud HPDC, June 2011.
[13] Umesh Deshpande, Xiaoshuang Wang and Kartik Gopalan.
￥em Live Gang Migration of Virtual Machines HPDC, June
2011.
[14] T. Hirofuchi, H. Ogawa, H. Nakada, et al. ￥em A Live
Storage Migration Mechanism over WAN for Relocatable
Virtual Machine Services on Clouds CCGrid, 2009.