アプリケーションから発行された要求が, の両キャッシュでミスヒットした場合, 両キャッシュには同一のデータが格納される. しかし, 最近アクセスされたデータへのアクセス要求は上で処理され, に届くことはない. 従ってでは最近アクセスされたデータは近い将来再度アクセスされる可能性が低いという通常と

Size: px

Start display at page:

Download "アプリケーションから発行された要求が, の両キャッシュでミスヒットした場合, 両キャッシュには同一のデータが格納される. しかし, 最近アクセスされたデータへのアクセス要求は上で処理され, に届くことはない. 従ってでは最近アクセスされたデータは近い将来再度アクセスされる可能性が低いという通常と"

しなつさわまつ
5 years ago
Views:

1 マルチメディア, 分散, 協調とモバイル (DICOMO214) シンポジウム平成 26 年 7 月二重キャッシュ環境における負の参照の時間的局所性を考慮したキャッシュ管理手法 1 杉本洋輝 1 山口実靖近年, クラウドコンピューティングの普及に伴い仮想化環境の重要性が高まっている. 仮想化環境下において, ( 下位キャッシュ ) へのアクセスは ( 上位キャッシュ ) を介して行われる. このような二重キャッシュ環境下において上位キャッシュの置換アルゴリズムに LRU が使用されている場合, 下位キャッシュにおいては一度アクセスされたデータが近い将来に再度アクセスされる可能性が低くなり, 通常とは逆向きの負の参照の時間的局所性が存在することが実で確認されている. また, 二重キャッシュ環境ではとに同一のデータを重複して格納している可能性が高い. このように, は負の参照の時間的局所性やとのデータの重複により有効に機能しない. 本研究では, 仮想化環境に適したキャッシュ置換手法を提案し, 評価によりその有効性を示す. A Cache Replacement Algorithm in Virtualized Environment with Two Caches HIROKI SUGIMOTO 1 SANEYASU YAMAGUCHI 1 1. はじめに近年, クラウドコンピューティングの普及に伴い仮想化環境の重要性が高まっている. 仮想化環境下において, ( 下位キャッシュ ) へのアクセスは ( 上位キャッシュ ) を介して行われる. このような二重キャッシュ環境下において, 上位キャッシュの置換アルゴリズムに LRU が使用されている場合, 下位キャッシュにおいては一度アクセスされたデータが近い将来に再度アクセスされる可能性が低くなり, 通常とは逆向きの負の参照の時間的局所性が存在することが実で確認されている [1]. また, 二重キャッシュ環境ではとに同一のデータを重複して格納している可能性が高い. は負の参照の時間的局所性やとのデータの重複により有効に機能しない. そのため, 負の参照の時間的局所性とデータの重複を考慮した置換手法が必要である. また, 近年普及が進んでいるクラウドコンピューティング環境では, 物理マシン上に複数の仮想マシンを稼働させ, 契約者に提供する. このような例では, 資源提供者側が自由に仮想マシンの資源を増減させることができず, 仮想マシンの数が少なく資源に余裕のある物理マシンではメモリ資源をホストが管理した状態のまま性能向上を図ることが重要となる. 本稿では, 二重のキャッシュで構成される仮想化環境に適したキャッシュ置換手法を提案し, 評価によりその有効性を示す. 2. 負の参照の時間的局所性アプリケーションが発行するデータアクセス要求には多くの場合偏りがあり,LRU などのメモリ管理技法の多くはこの参照の局所性の概念に基づいている. 多くの場合, 参照の時間的局所性を考慮したメモリ置換手法を用いることにより下層の低速記憶装置の記憶容量よりも小さいキャッシュでも十分な性能を発揮することができる. しかし, 仮想化環境のような二重キャッシュ環境では通常とは逆向きの負の参照の時間的局所性が存在する. へのアクセスは, 図 1 のようにゲストキャッシュを介して行われる. アクセス要求 H i t H i t アプリケーションゲストホスト 1 工学院大学大学院 1Department of information and Communications Engineering, Kogakuin University 物理 HDD 図 1 二重キャッシュ構造

アプリケーションから発行された要求が, の両キャッシュでミスヒットした場合, 両キャッシュには同一のデータが格納される. しかし, 最近アクセスされたデータへのアクセス要求は上で処理され, に届くことはない. 従ってでは最近アクセスされたデータは近い将来再度アクセスされる可能性が低いという通常とは逆向きの負の参照の時間的局所性が存在する.

仮想化環境において, 実験に使用した計算機の仕様は表 1, 表 2 の通り,FFSB の設定は表 3 の通りである. なおモニタリングはゲストの仮想ブロックデバイス層 (xvd 層 ) にて行った. 3. 関連研究二重キャッシュ環境を考慮したキャッシュ置換手法や二重キャッシュ環境に適したキャッシュ置換手法として, 以下の手法がある. 3.1 2Q(two Queue) 2Q は Johnson らによって提案された 2 つのリストを用いるキャッシュ置換手法である [2].

2 アプリケーションから発行された要求が, の両キャッシュでミスヒットした場合, 両キャッシュには同一のデータが格納される. しかし, 最近アクセスされたデータへのアクセス要求は上で処理され, に届くことはない. 従ってでは最近アクセスされたデータは近い将来再度アクセスされる可能性が低いという通常とは逆向きの負の参照の時間的局所性が存在する. また, 負の参照の時間的局所性はベンチマークのデータサイズが十分に大きい時, 上位キャッシュのサイズが大きいほど影響が大きくなることが確認されている [1]. た ( キャッシュミスした ) 後のものであり, への参照の局所性を調査することができる. 図 2 の実験環境にてベンチマークソフトである FFSB (Flexible File System Benchmark) を実行した. 仮想化環境において, 実験に使用した計算機の仕様は表 1, 表 2 の通り,FFSB の設定は表 3 の通りである. なおモニタリングはゲストの仮想ブロックデバイス層 (xvd 層 ) にて行った. 3. 関連研究二重キャッシュ環境を考慮したキャッシュ置換手法や二重キャッシュ環境に適したキャッシュ置換手法として, 以下の手法がある Q(two Queue) 2Q は Johnson らによって提案された 2 つのリストを用いるキャッシュ置換手法である [2]. FIFO 列 A1in と LRU 列 Am を用いてデータを保管し, 初めてアクセスしたデータは A1in に格納し,2 回目以降は Am に格納する. 置換が必要になった際,A1in のサイズが拡張可能閾値よりも小さく拡張可能である場合は Am の中で最も長い時間使われていないデータを置換対象に選択する.A1in が拡張可能でないときは A1in の中で最も古いデータを破棄し, その識別子を A1out に保管する. 本手法は多重キャッシュ構造を考慮した手法ではないが, 後述の MQ などの多重キャッシュ用置換アルゴリズムの研究にて参照されている. 3.2 MQ(Multi Queue) MQ はネットワークストレージのキャッシュのような 2 次キャッシュのために提案されたアルゴリズムである [3]. 一度アクセスされたデータは近い将来に再度アクセスされることはなく, ある程度長い時間がたってからのみ再度アクセスされることを考慮し, データを履歴に長期間保管することでキャッシュヒット率向上を目指したアルゴリズムである.MQ は 2Q を参考にしており, 複数の LRU 列を維持してデータを管理する. 各データをどの列に格納するかはアクセス頻度によって決定され, 最下位の列で最も長い時間参照されていないデータをとする. 破棄したデータの ID とアクセス頻度が Qout 列に保管される. データが再びアクセスされときは,Qout に保管してあった情報にもとづき格納する LRU 列を決定する. LRU 列のデータには expire Time が設定されており, 参照がないままこの時間に達すると,1 つ下位の LRU 列に移動される.LRU 列内のデータが参照されると, 参照回数が更新され, 新しい参照回数にもとづき格納 LRU が再計算される 4. 二重キャッシュ環境における参照の時間的局所性の解析 4.1 二重キャッシュ環境における参照の局所性の解析仮想化環境おいて下位キャッシュ ( ) に対する参照の局所性の調査を行う. 図 2 の様な実験環境を構築し, 図 2 内の Monitoring の箇所を流れるアクセス要求を調査した. 図 2 内の Monitoring の箇所を流れるアクセス要求はゲストのキャッシュを経由し図 2 参照の局所性解析環境表 1 実計算機の仕様 Cent6.3(64bit) Kernel Linux HDD 3TB 16GB Cache 15.45GB 仮想化システム Xen 使用ファイルシステム ext2 表 2 仮想計算機の仕様 Cent6.3(64bit) Kernel Linux HDD 5GB 1GB,2GB Cache.87GB, GB 使用ファイルシステム ext2 表 3 FFSB の設定 Data Size 8GB File Size 1MB Num File 8192 OP Size 1MB 4.2 解析結果アクセス間隔とアクセス発生確率 ( 確率密度関数 ) の関係を図 5, 図 6 に示す. 再アクセス間隔とは, 一度データへのアクセスがされてから, もう一度同じデータへのアクセスが来るまでに他のデータへ何 GB アクセスしたかを表している. 上位キャッシュサイズを変えた 2 つの測定結果両方で負の参照の時間的局所性が確認できた. 図 3 には再アクセ

ス間隔.4GB 以下, 図 4 には再アクセス間隔.6GB 以下の再アクセスがほとんど発生していない. また, 上位キャッシュとなるゲストのメモリサイズを増やすことで再アクセスが発生しない間隔が長くなり, 負の参照の局所性が強くなることがわかる. 5. 二重キャッシュ環境におけるキャッシュヒット率の測定 5.1 測定方法本章において, 実のキャッシュのヒット率の測定を行う.

図 5 内の Monitoring (A) から (D) の箇所を流れるアクセス要求は順に, アプリケーションから発行され上位キャッシュに入ってくるアクセス要求, 上位キャッシュでキャッシュミスしホストに送られるアクセス要求, 上位キャッシュでキャッシュミスし下位キャッシュに送られてくるアクセス要求, 下位キャッシュでキャッシュミスし物理 HDD に送られるアクセス要求である.

3 ス間隔.4GB 以下, 図 4 には再アクセス間隔.6GB 以下の再アクセスがほとんど発生していない. また, 上位キャッシュとなるゲストのメモリサイズを増やすことで再アクセスが発生しない間隔が長くなり, 負の参照の局所性が強くなることがわかる. 5. 二重キャッシュ環境におけるキャッシュヒット率の測定 5.1 測定方法本章において, 実のキャッシュのヒット率の測定を行う. 上位キャッシュ ( ), 下位キャッシュ ( キャシュ ) の各キャッシュヒット率を求めるため, 図 5 の様な実験環境を構築した, 図 5 内は仮想化環境を示す. また, キャッシュヒット率を求めるため, 図 5 の Monitoring の箇所を流れるアクセス要求を調査した. 図 5 内の Monitoring (A) から (D) の箇所を流れるアクセス要求は順に, アプリケーションから発行され上位キャッシュに入ってくるアクセス要求, 上位キャッシュでキャッシュミスしホストに送られるアクセス要求, 上位キャッシュでキャッシュミスし下位キャッシュに送られてくるアクセス要求, 下位キャッシュでキャッシュミスし物理 HDD に送られるアクセス要求である. また, 各キャッシュミス率は, 各キャッシュに入る前のアクセス要求量 ( 図 5 の A や C) をキャッシュを経由した後のアクセス要求量 ( 図 5 の B や D) で割ることにより近似的に求めることができる. なお上位キャッシュのモニタリングはブロック層, 下位キャッシュのモニタリングは SCSI 層にて行なった. 図 7 の実験環境で FFSB を実行した. 実計算機および仮想計算機の仕様は表 4, 表 5 にしめす. 表 5 仮想計算機の仕様 Cent6.3(64bit) Kernel Linux 仮想 HDD 5GB 2GB~12GB 使用ファイルシステム ext2 図 3 上位キャッシュ 1GB 時の参照の局所性図 5 キャッシュヒット率測定環境図 4 上位キャッシュ 2GB 時の参照の局所性表 4 実計算機の仕様 Cent6.3(64bit) Kernel Linu HDD 3TB 16GB 仮想化システム Xen 使用ファイルシステム ext2

4 5.2 測定結果上位 ( ゲスト ) キャッシュ, 下位 ( ホスト ) キャッシュのキャッシュヒット率を図 8~ 図 11 に示す. ゲストメモリサイズとは,VM に与えたメモリのサイズであり, ゲストが使用できるメモリのサイズである. ゲストは, このうちの一部をカーネルやユーザプロセスに割り当て, 残りの全てをページキャッシュ ( ) に割り当てる. 図の横軸は FFSB のデータサイズを示し, 図の左軸はキャッシュヒット率を示し, また図の右軸は FFSB によって得られたスループットを示している. また, 両キャッシュヒット率とはまたはでヒットした確率を近似的に求めたものである. これは, 上位キャッシュに入ってくるアクセス要求量を, 物理 HDD に対して発行されるアクセス量を割ったものである. すべての図において, ヒット率が 1% のときにヒットが存在しないのは, すべてのアクセス要求がで処理されるために要求がこないためである. まず, ヒット率について考察する. ゲストに 12GB と 14GB 割り当てた実験に着目するとヒット率はほぼ % となっており, ホストに割り当てたメモリが有効に機能していないことがわかる. また, が大きいとき ( 図 9 から図 11 など ) は, データサイズの増加に対するヒット率の低下の速度が高いことがわかる. 仮にへの参照に局所性がなく, 全てのブロックに対して均等の確率で要求がくるとするとヒット率はをデータサイズで割ったものとなるはずである. データサイズの増加とともにホストヒット率はこの速度を超えて低下しており, 負の参照の時間的局所性により, ホストに割り当てたメモリが有効に機能しなかったため性能が劣化してしまったと考えられる. 次にスループットに着目して考察する. スループットはヒット率が 1% であるときが最も良く, 次にヒット率が 1% であるときが良い. ヒット率が 1% のときが, ヒット率が 1% の時に比べてスループットが低い理由として, でヒットした場合よりでヒットした場合のほうが, アクセス要求に対する応答速度が遅いことが挙げられる. 二重キャッシュ環境では, アクセス要求のあったデータをまず上位キャッシュ ( ) に存在するか確認し, 存在しない場合下位キャッシュ ( ) に該当データが存在するか確認する. そのため, に該当データが存在せず, ホストで該当データが存在した場合でもに該当データが存在するか確認するため, でヒットした場合に比べて CPU 処理が多くかかってしまい, アクセス要求に対する応答速度が遅くなり, スループットの低下の原因となっていると考えられるヒット率ヒット率 / データサイズ比両キャッシュヒット率 Throughput DataSize[GB] DataSize[GB] 図 6 ゲストメモリ 2GB キャッシュヒット率ヒット率ヒット率 / データサイズ比両キャッシュヒット率 Throughput 図 7 ゲストメモリ 4GB キャッシュヒット率ヒット率ヒット率 / データサイズ比両キャッシュヒット率 Throughput DataSize[GB] 図 8 ゲストメモリ 6GB キャッシュヒット率 3, 2,5 2, 1,5 1, 5 3, 2,5 2, 1,5 1, 5 3, 2,5 2, 1,5 1, 5 Throughput[MB/s] Throughput[MB/s] Throughput[MB/s]

5 6. 負の参照の時間的局所性を考慮したキャッシュ置換 6.1 負の参照の時間的局所性を考慮したキャッシュ置換上位キャッシュ, 下位キャッシュ両キャッシュでミスヒットした場合, 両キャッシュには HDD から読み込まれた同じデータが格納される. しかし, 最近参照されたデータへの要求は上位キャッシュで処理され下位キャッシュには届かない. これを考慮し, では最後に参照されてからの時間が最も短いデータをとする (MRU) 手法を提案する. また, 上位キャッシュから破棄されるデータを監視し, 破棄データを下位キャッシュに最後に参照されてからの時間を最長 ( 最も破棄されにくい状態 ) として格納する. 上位キャッシュから破棄されたデータを格納する理由は, 上位キャッシュから破棄されたデータは上位キャッシュに存在しないため, 両キャッシュでのデータの重複が起きないためである. アクセス要求がでヒットした場合の動作 ( 図 12) を説明する. アプリケーションからページ D へのアクセス要求が来たとする. ページ D はゲスト O S に存在するため, ゲストは下位層に要求を転送せすることなくアプリケーションにデータを返す. また, は置換アルゴリズムに LRU を用いているためヒットしたページ ( ページ D) をにおいて最も破棄されづらい状態 (LRU の先頭 ) とする. 次に, アクセス要求がでヒットした場合の動作 ( 図 13) を説明する. アプリケーションからページ G へのアクセス要求が来たとする. 提案手法では, は置換アルゴリズムを MRU としているため, ヒットしたページ ( ページ G) をホストキャッシュにおいて最も破棄されやすい状態とする. 次に, ゲストはにページ G のコピーを格納する. の最後尾データはゲストから破棄され, に最も破棄されづらい状態 ( 最後に参照されてからの時間が最長 ) で格納される. これに伴い, では, 最後に参照されてからの時間が最短のページ G が破棄される. また, でのページ G を破棄する. 次に, アクセス要求が両キャッシュでミスヒットした場合の動作 ( 図 14) を説明する. アプリケーションからページ K へのアクセス要求が来たとする. ページ K は, の両キャッシュに存在しないため, 物理 HDD からデータの読み込みが行われる. その時, 提案手法ではでのみページ K を格納し, にはページ K を格納しない. この時, でのページ E をに最も破棄されにくい状態で格納する. また, でのページ J を破棄する. 提案手法は以上の動作により両キャッシュのデータの重複を抑える事ができる. 6.3 負の参照の時間的局所性を考慮したキャッシュ置換の評価シミュレーションによりキャッシュヒット率を評価しゲストキャッシュホストキャッシュ (LRU) pagedへのアクセス要求 (MRU) paged pagea pageb pagec pagee 1 pageg pageh pagei pagej pageg pageh pagei pagej ゲストキャッシュホストキャッシュ (LRU) pagegへのアクセス要求 (MRU) pageg 1 図 12 ヒット時の動作 pagek pagea pageb pagec paged 2 pageh pagei pagej pageg 2 pageh pagei pagej 図 13 ヒット時の動作 pagek ゲストキャッシュホストキャッシュ (LRU) pagekへのアクセス要求 (MRU) pageg pagee pageg pageh pagei 図 14 両キャッシュミス時の動作た. シミュレーションではキャッシュおよびディスクは 4KB ブロックに管理されているものとした. 上位キャッシュの置換アルゴリズムには LRU を用い, 下位キャッシュの置換アルゴリズムを変えてシミュレーションを行った. データサイズは 1GB とし, アクセス分布は一様分布とした. 図 15~ 図 17 にシミュレーション結果を示す. まず, 各手法のヒット率を比較すると, すべての例において提案手法のヒット率が高く, 提案手法が有効であることがわかる. 次に, LRU のヒット率について述べる. シミュレーションの結果より LRU は今回使用したアルゴリズムの中で最もヒット率が低いことがわかる. また, 下位キャッシュのサイズが同じ場合でも上位キャッシュのサイズを増やすと下位キャッシュヒット率が低下する事がわかる. この理由は 2 つ考えられる. 一つは上位キャッシュのサイズを大きくしたことにより負の参照の時間的局所性の影響が 3 pagej 3

6 大きくなり, 参照の時間的局所性を期待している LRU が効果的に機能しなかったためである. もう一つの理由は, 上位キャッシュのサイズが大きくなったことにより, 両キャッシュのデータの重複が増えたため, 上位キャッシュでミスヒットしたデータは下位キャッシュでもミスヒットする可能性が高くなり, ヒット率の低下に繋がったと考えられる. 次に, 下位キャッシュの置換アルゴリズムに提案手法を選択した場合のヒット率に着目して考察する.LRU のヒット率が上位キャッシュの増加とともに低下するのに対し, 提案手法のヒット率は上位キャッシュの増加ともに向上していることがわかる. 上位キャッシュの増加ともにヒット率が向上した理由として, 提案手法では負の参照の時間的局所性を考慮し, 最近参照のあったデータをとするためと考えられる. また, 提案手法では, データの重複が発生しないため, 下位キャッシュが効果を持たないデータを格納することがない. これもキャッシュヒット率が向上した理由考えられる. 次に, 下位キャッシュの置換アルゴリズムに MQ を選択した場合のヒット率に着目して考察する. 下位キャッシュの置換アルゴリズムに MQ を選択した場合は LRU と変わらない性能となり, 有効に機能していないことがわかった. MQ は参照回数に基づき格納する LRU 列を決定するが, 今回の測定ではすべてのデータが 1 つの LRU 列に入ってしまい実質的に LRU と同じ動作となり, 同等の性能となった. 今回の測定では,MQ の文献 [3] で推奨する (f は参照回数 ) に基づき格納 LRU 列を決定したが, これでは適切に動作しないことがわかり,MQ ではこの決定方法を調整しないと高い性能を示せないことがわかった. 1% 9% 8% 7% LRU 6% MQ FIFO 5% RAND 4% LFU MRU 3% FIX 提案手法 2% 1% % 下位キャッシュサイズ [GB] 図 16 シミュレーション結果, 上位キャッシュ 3GB 1% 9% 8% 7% LRU 6% MQ FIFO 5% RAND 4% LFU MRU 3% FIX 提案手法 2% 1% % 下位キャッシュサイズ [GB] 図 17 シミュレーション結果, 上位キャッシュ 4GB 1% 9% 8% 7% 6% 5% 4% 3% 2% LRU MQ FIFO RAND LFU MRU FIX 提案手法 7. おわりに本稿では, 仮想化環境下における負の参照の時間的局所性の紹介と負の参照の時間的局所性を考慮した置換手法の提案をし, 評価した. その結果, 提案手法は多くので採用されている置換アルゴリズムである LRU よりも高い性能を示すことがわかった. 今後は, 代表的なホストである Linux への実装を行っていく予定である. 1% % 下位キャッシュサイズ [GB] 図 15 シミュレーション結果, 上位キャッシュ 2GB 謝辞本研究は JSPS 科研費 24334, , の助成を受けたものである参考文献 [1] 竹内洸祐, 山口実靖, 複数サーバ接続ネットワークストレージ環境での参照の局所性の解析第 24 回コンピュータシステムシンポジウム (ComSys 212) [2]Theodore Johnson, Dennis Shasha, 2Q: A Low Overhead High Performance Buffer Management Replacement Algorithm, Proceedings of the 2th International Conference on Very Large Data Bases (1994) [3]Yuanyuan Zhou and James F. Philbin, Kai Li Second-Level Buffer Cache Management, IEEE Transactions on parallel and distributed systems, vol. 15, no. 7, JULY 24

56 OS OS OS OS 1 OS HDD OS 1 OS HDD HDD OS OS OSOS HDD 図 1 二重キャッシュ環境 3. 負の参照の時間的局所性 3.1 参照の局所性 Locality of Reference Temporal locality Spatial localit

56 OS OS OS OS 1 OS HDD OS 1 OS HDD HDD OS OS OSOS HDD 図 1 二重キャッシュ環境 3. 負の参照の時間的局所性 3.1 参照の局所性 Locality of Reference Temporal locality Spatial localit 116 26 4 1 2 2 1 3 An Analysis of Locality of Reference in Virtualized Environment Hiroki SUGIMOTO 1, Kousuke TAKEUCHI 2, Kouya HINAGAWA 2 and Saneyasu YAMAGUCHI 1 3 Abstract As cloud computing has spread