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

アクセス時間に基づいた次アクセス予想によるデバイスミックススト
レージシステムの制御手法

Title(English)
著者(和文)

新屋敷裕太, 飯澤健, 小沢 年弘, 荒堀 喜貴, 横田 治夫

Authors(English)

Yuta Shinyashiki, Ken Iizawa, Toshihiro Ozawa, Yoshitaka Arahori,Haruo Yokota

出典(和文)

第8回データ工学と情報マネジメントに関するフォーラム論文集, , ,D8-2

Citation(English), , ,発行日 / Pub. date

2016, 3

D8-2

Powered by T2R2 (Science Tokyo Research Repository)DEIM Forum 2016 D8-2

アクセス時間に基づいた次アクセス予想による
デバイスミックスストレージシステムの制御手法
新屋敷裕太†飯澤健††

小沢 年弘††

荒堀 喜貴†

横田 治夫†† 東京工業大学 〒 152–8550 東京都目黒区大岡山 2 丁目 12–1†† 株式会社 富士通研究所 〒 211–8588 神奈川県川崎市中原区上小田中 4–1–1
E-mail: †shinyashiki@de.cs.titech.ac.jp, ††{iizawa.ken,t.ozawa}@jp.fujitsu.com,†††{arahori,yokota}@cs.titech.ac.jp
あらまし

低コストで高性能なストレージシステム実現に向け，HDD と SSD のデバイスミックスにおける効率的制御が注目されている．デバイスミックス環境は様々な用途で使われることが想定される．公開されているアクセスト
レースを用いたアクセス間隔分析により，ワークロード毎やストレージ領域毎でアクセスパターンが異なることを検知した．デバイス間でデータの再配置を行う際のタイミングは性能に影響を及ぼす．そのため，アクセス時間間隔を考慮し，ワークロード毎や領域毎に適した制御が求められる．本研究では，領域ごとのアクセスの時間間隔を基に次のアクセスの予測を行うデバイスミックスの制御手法を提案する．アクセス予測に応じて，アクセス対象データのデバイス選択やデータ移動のタイミング制御を行い，その有用性を示す．
キーワード

デバイスミックス，ブロックトレース，データ再配置，アクセス予測

1. は じ め に現在，世の中のデータ量は爆発的な増加をしており，データの格納媒体として HDD（ハードディスクドライブ）が広く用いれられてきた．HDD は大容量化により，そのデータ量の増加に対応してきた．しかしながら，HDD 自体の性能は頭打ちとなっている．一方，メモリに半導体素子を用いている SSD（ソリッドステイトドライブ）が存在する．SSD は HDD のような
磁気ディスクと比較して，ヘッドがアクセス対象となるデータ
トラックまで動くシーク時間が存在せずランダムアクセスに優れ，物理的駆動箇所がないため衝撃にも強いという特徴がある．

図 1 デバイスミックスストレージシステムイメージ

また，プラッタの回転やヘッドのシーク動作など駆動箇所がな
いため省電力である．しかし，SSD は書き込みの処理の際にチップ内の絶縁膜が劣化する．そのため，動作を保証するため
書き込み回数の制限が設けられている．HDD と比べ，容量あたりの単価は高価である．ストレージシステムにおいて，すべての記憶媒体を HDD から SSD に取り換えることは性能向上のために望ましいが，その構築は非常にコストが高くなる．そのため，低コストでストレージシステムの性能を向上させるが必要であり，HDD と SSD を組み合わせたデバイスミックスス
トレージシステムが注目されている．

SSD などの半導体ストレージを HDD などの磁気ストレージのシステムへ組み込むデバイスミックスストレージシステムの手法として Cache 方式と Tiering 方式が存在する (図 1) [1]．

Cache 方式とは全てのデータを HDD に配置し，データのア

データのコピーは行わず，SSD と HDD 間でデータの移行を行う．データの移行はデータアクセスの統計情報を基にデバイスの特性を活かすよう，指定されたタイミングで行う．Cahce 方式では一度アクセスが発生したデータを SSD にキャッシュするため，二度目のアクセスから高速化が可能となる．しかし，データのアクセスがランダムなワークロードでは頻繁なキャッ
シュの入れ替え動作によって，性能の劣化や寿命の短縮が懸念される．また，Tiering 方式では，データのアクセス頻度が多い領域を指定されたタイミングで移行することにより高速化を図っている．しかし，データのアクセスする領域に変化があった場合，移行のタイミングによっては十分な効果が得られない
場合がある．よって，SSD と HDD のデバイスミックス環境において効率的な制御が求められている．

クセスによって HDD から SSD へとデータのコピーをキャッシュする方式である．SSD へのデータのキャッシュは LRU な
どのキャッシュアルゴリズムによって制御されている．一方，Tiering 方式ではデータを SSD と HDD に分けて配置をする．

2. 関 連 研 究
ストレージ間のデータ配置の最適化を図ることを目的として

様々な研究が行われてきた．ファイルベースでデータの移行を純にキャッシュによってデータのコピーを配置することは領域行う研究として次のようなものがある．[2] ではファイル間の相を効率的に使用できない．これらの問題を回避するため本研究

関関係を発見し，HDD から SSD へのプリフェッチを行っておでは Tiering 方式を採用する．2. でのデバイスミックス環境にり，[3] では時間的に共起しやすいファイルを同一ディスクに配おける取り組みではデータのアクセス頻度に注目し，データ再置する手法を提案している．ブロックベースで移行を行う研究

配置における最適化や特定のワークロードにおいてアクセス

として，[4] [5] などの研究がある．これらはブロックの相関を検集中領域を予測する研究は多く行われている．しかしながら，出し，HDD からメモリへのプリフェッチを行う．データ移行

データの再配置の周期に注目して行われている解析は少ない．

のポリシーを動的に変更する研究として，[6] ではキャッシュのTiering 方式では予め決められた時間によって再配置を行うこ

ヒット率などに応じてキャッシングやプリフェッチに割り当てとが多く，次のデータ移行の時間に達するまでアクセスの高速るメモリの配分を変更している．[7] ではシステム全体の I/O レ

化を行えないという欠点がある．そのため，最適な時間間隔でイテンシを最小化するようにポリシーを変更している．また，の再配置が必要である．また，デバイスミックス環境は様々なストレージシステム上を流れるワークロードに注目した研究と用途で使われることが想定される．上記で述べたように特定のして，[8] では昼夜でワークロードの特性が大きく切り替わるよ

ワークロードに対して特徴を捉える研究は行われているが，全

うなシステムにおいて，特性が切り替わる前に次のワークローてのワークロードに対して最適な制御を行われているものは少ドを先読みし，あらかじめデータを SSD へと移行している．[9]ない．さらに Tiering 方式ではアクセスの統計情報を基に決めでは全 I/O の多くが連続した領域に集中し，分オーダーで継続られた領域（extent）単位でデバイス間のデータの移行を行う．

した後，別領域に I/O が移動していくようなワークロードを想Cache 方式のようなブロック単位でのデータ移行は，統計情報

定している．I/O 集中フィルタリングを行い，性能向上が期待を管理するコストを大きくしてしまうからである．そのため，できる領域を SSD へ移行することで SSD への I/O を集中さ

ワークロード毎やアクセスが発生する extent 単位でのアクセせている．

ス傾向を捉える必要がある．アクセスパターンを知ることによ

また，SSD はフラッシュメモリを使用しているものが一般的でり，最適な時間間隔でデータの再配置を行うことが可能である．

あるが，次世代の不揮発性のメモリとして PCM（相変化メモ

アクセス時間間隔を考慮したデータ配置を行い，その管理コス

リ）や ReRAM（抵抗変化形メモリ），NRAM（カーボンナノ

トを軽量化することにより従来の Tiering 方式の問題点を解決

チューブを使用したメモリ），MRAM（磁気抵抗メモリ）等ができると考える．本研究ではデバイスミックス環境の高寿命か注目され，ストレージへの需要も高まっている．これらの次世

つ高効率運用を目的として，データのアクセス時間間隔を考慮

代メモリはフラッシュメモリよりも I/O 性能に優れ，書き込したデータ配置の最適化の手法を提案する．本手法の有用性をみ回数の制限が緩和されているという利点と製品として開発段示すため，以降の分析と実験を行う．

階であるものも多く，価格が高いという欠点がある．次世代メ
モリはメインメモリとしての用途に関して，様々な研究が行わ

4. アクセス間隔分析

れている．[10] では，PCM と従来の DRAM を組み合わせたハ

上記で述べたように全てのワークロードに対して最適な制御

イブリッドメモリにおいて PCM への Write を緩和するページを行われているものは少ない．そのため，ワークロード毎やア置換アルゴリズムの提案を行い，メモリへの Write を予測す

クセスが発生する決められた領域（extent）単位でのアクセスる方法として 2 つの事象を観測している．1 つ目は時間の周期傾向を捉えるため必要がある．アクセスパターンを捉えるため，的なアクセスよりもアクセス頻度に応じた予測が優れているこ以下の分析を MicroSoft Research が一般に公開しているサーとであり，2 つ目は Read/Write を合わせたアクセス履歴より

バーワークロードのブロックトレースを用いて行った [13]．よも Write のみに注目した履歴を使用する方が予測に優れている

り詳しい分析の内容と考察については [13] を参照されたい．

ことである．デバイスミックスストレージシステムにおいても

4. 1 MSR Cambridge

SSD と HDD では使用の寿命が異なるため，SSD への Write

MSR Cambridge は MicroSoft Rearch サーバに関する I/Oを緩和することでシステム全体の寿命を伸ばすことが可能であの ブ ロック ト レ ー ス で あ る [12]．Usr home directories やると考えられる．

Project directories，Web/SQL server 等，様々な用途で使用

また，デバイスミックスストレージシステムは実際に製品化されたワークロードのトレースを一般に公開している．このブされ，運用されているものも存在する，EMC VNX シリーズ

ロックトレースのデータは 13 servers，36 volumes，179 disks

製品における FAST VP という機能 [11] では，1GB あたりのから約 1 週間分の I/O が採取されている．トレースのデータ

sub-LUN の粒度で I/O の統計情報を集計し，その情報を元には csv ファイルで公開されており，Timestamp，Hostname，

各階層へのデータの再配置を行っている．

DiskNumber，R/W Type，Starting oﬀset，Responsetime か3. 本研究の目的
1. で述べたように Cache 方式では頻繁なキャッシュの入れ替ら成る．

4. 2 同一 extent へのアクセス間隔分析
同一 extent へのアクセス間隔分析は，ワークロード毎のア

え動作による性能の劣化と寿命の短縮が問題となる．また，今クセス特徴を捉えるため行う．ストレージ領域を extent 毎に

後 SSD の大容量化により，使用可能な領域が増大した際，単区切り，extent 内に発生した I/O の Timestamp の差分を計算

図 3 usr 0
図 2 同一 extent へのアクセス間隔分析
ファイル名 Read 数

Write 数

Read size

Write Size

usr 0904,493

1,333,406 約 35.05GB 約 13.08GB

mds 0

143,973

1,067,061

約 3.26GB

約 7.37GB

wdev 0229,529

913,732

約 2.75GB

約 7.15GB

表 1 分析対象トレース

し，extent 毎の再アクセス間隔を集計する（図 2）．どの extent
へアクセスが発生しているかは I/O の Starting oﬀset がどの

extent 領域内に含まれているかによって判定する．時間間隔として，1ms 以下，1ms から 10ms 以下，10ms から 100ms 以下，

100ms から 1s 以下，1s から 60s 以下，60s から 10min 以下，

図 4 mds 0

10min から 20min 以下，20min から 1h 以下，1h から 2h 以下，
2h から 6h 以下，6h から 12h 以下，12h から 1day 以下，1dayから 2days のパターンに分けてアクセスカウントを採取している．この時間間隔の分け方は人間の感覚として分かりやすい時
間間隔に設定している．実際の製品におけるデータの再配置なども 3 時間毎，2 日毎など人の手によって設定されている場合が多い．ある extentA のアクセスに対し，次の extentA へのアクセスが 40min 後だったとすると，20min から 1h 以下のア
クセスをインクリメントする．ここでは User home directories（usr 0），Media server（mds 0），Test web server（wdev 0）のワークロードについて分析した結果を示す（図 3 から図 5）．
この時の extent のサイズは 1GB としている．縦軸が extent へ

図 5 wdev 0のアクセス回数，横軸がアクセス間隔である．それぞれのワー
クロードの詳細は表 1 である．
ワークロードごとに extent へのアクセス回数の偏りやアク

以下のアクセス間隔やそれより長いアクセス間隔のパターンも少なくはあるが検知することができた．

セスの時間間隔に違いがあることが分かる．usr 0（図 3）はア

4. 3 extent 毎のアクセスの持続性に関する分析

クセス間隔が 1ms 以下や 10ms から 100ms 以下が多くを占め

4. 2 からワークロード毎にアクセスパターンが異なることがる．また 1s から 60s の間隔のアクセスも比較的多く存在する．

分かった．この分析ではワークロード全体としての傾向を得る

mds 0（図 4）では usr 0 と比較して 10ms から 100ms 以下のことができたが，どの extent にアクセスがあったのかというアクセス間隔のパターンが一番多く，続いて 1ms から 10ms 以

情報はない．そのため，直接データ配置に活かすことが難しい．

下のアクセス間隔，1ms 以下のアクセス間隔が多くを占める

extent 毎の傾向のアクセスの傾向を知る必要があり，extent 毎

ワークロードとなる．wdev 0（図 5）では 1ms 以下と 1s からのアクセスの持続性に関する分析を行う．extent 毎の特徴を捉

60s 以下のアクセス間隔が大半を占めるワークロードとなる．

えることにより，Tiering に向いた移行対象の extent の発見がこれららのアクセス分析からストレージのアクセスパターンはできると考える．この分析で使用するワークロードは usr 0 を

ワークロード毎で異なることが分かる．また，60s から 10min用いる．1 週間のブロックトレースのうち，I/O 数が最も多い

図 6 I/O 数上位の extent に対するアクセスの持続性
図7

システム概要図

日の 3 時間を抽出し，その I/O 数上位の extent に対し，4. 2の分析における時間間隔がどの程度持続するかについて分析する（図 6）．この時の extent のサイズは 512MB としている．

I/O 数上位となる extent の番号は上位の番号から 6，0，5 である．縦の軸は，アクセス間隔を示しており，1ms 以下，1ms
から 10ms 以下，10ms から 100ms 以下，100ms から 1s 以下，

1s から 60s 以下のアクセス間隔が発生したことを示す．横軸はワークロードにおいて extent への初めて I/O が発生してからの時間の流れである．縦の値が 1ms 以下になっている時刻では前のアクセスから次のアクセスまでの時間間隔が 1ms 以下であったことを示している．図 6 が示すように，ワークロード
内の extent 毎でアクセスの持続性は異なる．最も I/O 数が多
い extent である extent6 ではワークロードの始まりは 100ms
から 1s 以下や 1s から 60s 以下の比較的長いアクセス間隔が少しの間継続し，1s 以下のアクセスパターンが連続する．その後は 1s から 60s 以下のアクセス間隔が多くを占める傾向がある．

extent0 では 1s 以下のアクセス間隔が継続した後，中盤に 1sから 60s 以下のアクセスが頻出し，再び短いアクセス間隔が継続する傾向がある．extent5 についても extent6 と extent0 とは違う傾向がある．このため，あるワークロード内のそれぞれの extent についてもアクセスパターンが異なることが分かる．

5. 1 システムの概要
提案システムは OS ドライバとして動作する．Linux Kernelが提供する device-mapper と呼ばれるフレームワークを利用
し実装を行った．device-mapper はブロック型デバイスドライ
バをサポートするライブラリ群であり，複数のブロック型の実デバイスを管理し，仮想デバイスの作成や管理に利用できる．
そのため，ユーザは仮想デバイスにアクセスすることで通常通りに使用することができる．HDD から SSD に移行した情報
はドライバ自身が Mapping Table を保持しており，ユーザからの I/O はこの Mapping Table を参照することにより，実デバイスへと振り分けられる．Write の I/O が移行中の extent
へ発行された場合は，I/O 待ちキューに追加する．キュー内のI/O は移行終了後、対象の extent へ I/O を発行される．実際のデータ移行は本システムが保持する次アクセス予想リストを基にデータの移行を決定する．また，次アクセス予想リストは同様に保持しているアクセス時間管理リストによって作成される．本システムの概要図を図 7 に示す．

5. 2 アクセス時間管理リスト
アクセス時間管理リスト（図 8）では，extent へアクセスが発生した時刻をリング状のリストで管理する．従来の Tiering
手法では時間単位でアクセス履歴を保持し，データ移行へと活

5. 次アクセス予想制御
4. の分析結果より，ワークロード毎にアクセス間隔の分布は異なり，extent 毎でもアクセスの持続性が異なることが分かった．そのため，ワークロード毎，extent 毎で適切なデータ移行の管理を行う必要がある．extent 毎のアクセスの持続性の分析で見られたアクセスパターンの変化をうまく捉えるためには個々の extent でアクセスの時間情報を管理することが望まし
い．Tiering 方式において，アクセス予測に用いる情報の集計・管理・解析にはコストがかかる．特に extent のアクセス間隔
分析のように 1s 以下のアクセス間隔が多く存在する場合，ア
クセス情報の解析に時間をかけると短いアクセス間隔の活用は難しい．本稿では，アクセス単位で extent 毎のアクセス時間
情報を管理するリストを用いて，アクセス情報の管理を軽量化し，アクセス時間間隔から次のアクセスを予想するデータ移行を提案する．

用していたが本システムではアクセス単位によりアクセス履
歴を発生時刻と共に保持する．一定回数のアクセス（Window

Size）分の時刻を各 extent 毎が記憶している．一定回数のアクセス間隔を集計し，平均値または最頻値を算出する．算出した
値と最新のアクセスが発生した時刻から次のアクセスが発生する時刻を予想する．リングリストのポインタを進めて打刻する
ことにより，古いアクセス間隔は破棄され，新しいアクセス間
隔がアクセス毎に逐次更新されていく．新たなアクセスが発生した場合，アクセス時間管理リストは以下のような動作を行う．
（ 1 ） アクセス時刻を取得（ 2 ） リングリストのポインタが指し示す時刻（Window

Size 内の最も古いアクセス）と 2 番目に古いアクセスの発生時
刻のアクセス間隔を集計値より減算（ 3 ） 最新のアクセス時刻をリングリストに記録し，1 つ前のアクセス時刻とのアクセス間隔を集計値へ加算される．その際に，リスト挿入用に extent 番号と次にアクセスが発生する予想時刻を保持したエントリーを作成する．リス
トは時間順に並んでおり，新しく作成したエントリーのアクセ
ス時間が時間順に並ぶよう挿入する．挿入する時以下の 3 通りの場合が考えられ，それぞれの場合の処理を示す．
（ 1 ） リストに同一の extent が存在する場合
リスト上の同一 extent エントリーを削除し，時間順に挿入する．この場合，リストのサイズは変わらないので移行に影響はない．
（ 2 ） リストに同一 extent が存在せず，挿入箇所がリストの末尾の場合挿入された新たなエントリーを削除する．最もアクセス時間
図 8 アクセス時間管理リスト

が遅いエントリーのため，SSD に移行する必要がなく，移行は行われない．
（ 3 ） リストに同一 extent が存在せず，挿入箇所が末尾以外の場合末尾のエントリーの extent を HDD へ戻し，新たに挿入されたエントリーの extent を SSD へと移行させる．この時，extentの移行が発生する．
上記のリスト操作により，リスト上のエントリーの extent
は SSD へ移行され，リストから漏れたエントリーの extent はHDD へと移行される．また，リストに存在していながら以降アクセスがなかった extent に対しては予想時間が更新されず，リストに残り続けてしまう問題点がある．その問題を回避すべく，現時刻とリスト内の最も早い予想時間を比較し，現時刻
が予想時間を超えていた場合，リストから削除し，extent を
図 9 次アクセス予想リスト

HDD へ移行する処理を行っている．リストで管理するアクセス予想時間はアクセス時間管理リストにおける平均値または最（ 4 ） アクセス間隔の平均値または最頻値の更新

頻値によって導出される．

（ 5 ） 次アクセス予想時刻の更新

また，次アクセス時間予想リストはアクセス毎に更新が発生すこのようなリスト操作をアクセス毎に行うことにより，アクる．リストの更新によるデバイス間の extent 移行が頻繁に発セス間隔をそれ以前のアクセスパターンから更新し，アクセス

生すると，I/O 待ちが多くなり性能へ影響を及ぼす．そのため，履歴の解析時間の短縮を行うことが可能である．

以下の二つの機能により，性能を劣化させるような extent の移

長期アクセス検知フラグを用意しており，長期的なアクセス間

行を抑制する．

隔を検知していた場合，フラグを立て予め長期アクセス用に割•り当てておいた領域へプリフェッチを行う．

extent の移行が次のアクセス予想時間に間に合わない場合，

5. 3 アクセス予想リスト
アクセス予想リスト（図 9）では，アクセス時間管理リスト
によって算出した次アクセス予想時刻をリスト上で管理する．
このリストを利用して，SSD から HDD または HDD から SSD

Time restraint

extent 移行を行わない．
•

Queue-length based restraint

I/O 待ちキューの長さによって，システムの負荷を判断し，負荷が大きい場合，extent 移行を行わない．

のデータの移行を行う．アクセス予想リストは次アクセス時間

4. 2 で述べたように比較的長いアクセス間隔が発生する ex-

予想リストと長期的再アクセス時間予想リストの 2 本のリスト

tent も存在する．こうした extent で長いアクセス間隔時間がを持つ．これらのリスト上に存在する extent が SSD に存在す

記録された場合，平均値によるアクセス予想では次時間アクセることとなる．2 本のリストの長さの合計は使用可能な SSD のス予想リストに反映されにくいという欠点がある．そのため，

extent 分のサイズである．

次の長期的再アクセス時間予想リストを用いて別の移行を行う

5. 3. 1 次アクセス時間予想リスト

ことで，次時間アクセス予想リストでは漏れてしまう extent へ

次アクセス時間予想リストはアクセス時間管理リストの次アのアクセスを捉えることができる．

クセス予想時刻に基づいて更新される．アクセス時間管理リス
トにより，次アクセス予想時刻は各 extent のアクセス毎に更新

5. 3. 2 長期的再アクセス時間予想リスト
長期的再アクセス時間予想リストは 5. 2 で述べた長期アクセ
ス検知フラグが検出された際に更新される．次アクセス時間予CPUXeon X5460 3.16GHz

MEMORY

48GB

OS

Linux 2.6.32（x86 64）

SSD

SAS 3.0 MLC 400GB

HDD

SATA 3.0 7200rpm 1TB
表2

ファイル名 Read 数

実験環境

Write 数

Read size

Write Size

usr 039,537

10,138

約 1.12GB

約 0.12GB

mds 0

6,169

7.993

約 25.54MB 約 77.41MB

wdev 035,732

135,482

約 0.43GB

表3

約 1.09GB

実験データ

図 10 Window Size を変更した SSD ヒット率

想リストと同様，extent 番号と再アクセスが発生する予想時刻

図 10 で示したグラフが usr 0，mds 0，wdev 0 で Widow Sizeと保持したエントリーを作成し，リストへと挿入する．リストを変更し，実行した結果である．

に挿入された場合，SSD へのプリフェッチを行う．長期的なア

usr 0 では Window Size を変更しても，Total のヒット率に

クセス時間は 4. 2 の分析で検知できた 60s から 10min 以下の大きな差はない．しかしながら 100 の場合，Write のヒット率

時間間隔を用いたい．

5. 4 特徴が低下が見られる．SSD は Write 操作によって性能の劣化や寿命の短縮が懸念されるため，Write のアクセスパターンによる本システムではアクセスの履歴管理を全てリスト操作のみ影響も見られたのではないかと考える．mds 0 では 50 の場合により行っている．一定アクセス数内におけるアクセス情報のにヒット率が最も良い．その際，Read のヒット率も向上して逐次更新により，前までのアクセスパターンを考慮しながら次いるため，SSD に移行される extent として適切なものが次アのアクセス予想を行うことを可能とした．そのため，従来の一クセス時間予想リストで管理されていると考えられる．wdev 0

定時間内での集計・解析・予想と比較し，解析時間を短縮及びでは Window Size を大きくするごとにヒット率が向上していデータを配置する適切なデバイス選択が可能となったのではな

る．Total のヒット率に伴い，Read のヒット率も向上している

いかと考える．また，アクセス毎に管理情報を更新することにため， mds 0 と同様に適切な extent が移行されている．

より，柔軟なアクセスのパターンの変化も捉えることが出来る

6. 2. 1 Window Size の選択についてようになると考える．Tiering 方式の問題点であった再配置のWindow Size を大きくする場合，アクセスの時間履歴をより周期によって，十分な効果が得られない点をアクセスパターン

多く保存することになる．このため，アクセスの少ない extentの変化を即座に捉えることで改善できると考える．

は次アクセス予想リストに反映されにくくなり，高頻度でアク

6. 実

験

セスのある extent が優先的にリストへ反映できる利点がある．
しかしながら，ワークロード内でアクセスパターンが変化した

提案システムの有用性を示すため，デバイスミックス環境に時，Window Size 分のアクセス履歴が埋まるまでは過去のアクおける SSD のヒット率と平均応答時間についての実験を Time

セス間隔が反映され，アクセスパターンの捉えにくくなる欠点

restraint で移行を抑制した提案手法，Queue-length restraintも存在する．3 つのワークロードによって Window Size を変で移行を抑制した提案手法，Cache 方式である FlashCache と更した際のヒット率の変化は異なることが分かった．そのため，

従来 Tiering 手法に対して行う．FlashCache [14] は，Facebook

ワークロードによってこれらの利点反映されやすい Windowが開発した SSD を HDD のキャッシュとして利用可能なデバイ

Size とある Window Size からは欠点が反映されやすくなる場

スドライバである．device-mapper のフレームワークを用いて合がある．ワークロード毎によって，適切な Window Size の実装されている．また従来 Tiering 方式では extent に発生し決定が必要であると考える．

た I/O 数をカウントし，一定時間毎に I/O 数上位の extent を

6. 3 従来手法との比較

HDD から SSD へ移行する．実験環境は表 2 に示す．

比較対象である FlashCache は Block Size を 4KB，従来

6. 1 実験データ

Tiering の I/O 集計を行う一定の時間は 10 分間と設定してい本実験では表 3 に示すトレースファイルを対象とし，I/O トる．また，従来 Tiering と提案手法共に移行を行う extent のサ

レースのリプレイを各方式に行った．表 3 は表 1 で示した 1 週

イズは 256MB である．提案手法の Window Size は usr 0 が間分の I/O トレースの内，I/O 数の最も多い日付の 1 時間を抽

50，mds 0 が 50，wdev 0 が 100 である．図 11 から図 16 が出したトレースデータである．リプレイには btreplay（トレー実行結果である．使用する SSD の領域は 2GB 分であり，そのスのリプレイツール）[15] を利用した．

内 512MB 分を長期的アクセス用に割り当てている．長期的な6. 2 Window Size による効果
まず提案手法における Window Size を決定するため，Win-dow Size を 20，50，100 と変化させた場合のヒット率を示す．

アクセス時間間隔は 5 分と設定した．

6. 3. 1 FlashCache との比較
提案手法と FlashCache では SSD ヒット率において、usr 0

図 11 SSD ヒット率 (usr 0)

図 13 SSD ヒット率 (mds 0)

図 12 平均応答時間 (usr 0)

図 14 平均応答時間 (mds 0)

では約 5 倍から約 5.4 倍，mds 0 では約 1.7 倍から 2.9 倍，提案手法が優れていおり，wdev 0 では FlashCache が約 1.2 倍優れている結果となった．また，平均応答時間は usr 0 のワークロー
ドにおいて，Time restraint 付与の提案手法が優れていることが分かった．ワークロードによって，提案手法と FlashCacheとでヒット率が大幅に変わってしまう．そのため，Cache 方式に適したワークロードと Tiering 方式に適したワークロードがそれぞれある．Tiering 方式に Cache 方式を組み合わせることにより，それぞれに方式に適したワークロードにも柔軟に対応することが可能であると考える．

6. 3. 2 従来 Tiering との比較

図 15 SSD ヒット率 (wdev 0)

提案手法と従来 Tiering では SSD ヒット率において，usr 0
では約 15.1 倍から約 16.3 倍，mds では約 1.1 倍から約 1.8
倍，wdev 0 では約 4.1 倍から約 4.6 倍の向上が見られた．平
均応答時間は，usr 0 と wdev 0 のワークロードにおいて Time

restraint 付与の提案手法が優れており，mds 0 のワークロードにおいて Queue-length based restraint 付与の提案手法と同等であることが分かった．時間毎のアクセスを集計し，ソートす
る従来 Tiering と比べて，アクセス毎に時間情報を更新する提案手法では移行のため解析のコストが低いため有用であると考手法の提案を行った．同一 extent へのアクセス時間間隔の分
析から各ワークロードについてアクセスパターンが異なることが分かった．extent のアクセスの持続性の分析により，同一のワークロード内においても extent 毎にアクセスパターンは異なり，時間の流れで変化することが分かった．アクセス履歴を管理する幅である Window Size を変更したヒット率の実験においては，ワークロード毎の適切な Windows Size を決定する必要があると分かった．提案手法と FlashCache との実験において，ワークロードによってヒット率と平均応答時間に大幅なえられる．

差があることが分かった．そのため，Cache 方式に適したワー

7. 考

察

MSR のブロックトレースを用いて，アクセス間隔・持続性の分析を行い，アクセスの時間間隔を用いたデータ配置の制御

クロードと Tiering 方式に適したワークロードがあると考えられ，Tiering 方式に対し Cache 方式を組み合わせることによって，それぞれに適したワークロードへの対応も可能であると考ロードによる適切な方式の選択や Window Size の決定が必要であるという結果からこれらを効率的に導き出す必要性がある考えられる．また，本研究では HDD と SSD を用いたが，次世代メモリの研究も進んでおり，次世代メモリストレージを利用した最適な制御手法についても検討が必要である．

文

図 16

平均応答時間 (wdev 0)

えられる．また同等の性能である場合，単純にデータのコピーを配置する FlashCache と比較すると領域利用率の面から見ると提案手法は有用であると考えられる．従来 Tiering との比較
では mds 0 以外の 2 つのワークロードについてヒット率と平均応答時間において優位性を示せた．統計情報を基にした移行
より時間間隔情報を基にした移行の有用性を示せた．アクセス
本研究の分析と実験から従来 Tiering と比較してアクセス単位の時間情報管理が有用であると考えられ，Cache 方式との比較
ではワークロードによって方式を複合し対応させることができると考えられる．
また，実際のシステムではいくつかのワークロードが複合して実行されることがある．複合ワークロードの場合であっても，本手法ではアクセスパターンを即座に捉えることができるため，有用に働くのではないかと考える．

8. まとめと今後の課題
本研究ではデバイスミックス環境における高寿命かつ高効率なデータ移行の制御手法として，アクセス単位で extent 毎のア
クセス時間情報をリストで管理し，アクセス時間間隔から次のアクセスを予想するデータ移行を提案した．本手法では Cache
方式における頻繁なキャッシュの入れ替え動作に性能の劣化やデバイスの寿命短縮の問題を回避するため Tiering 方式を採用した．従来の Tiering 方式において，データ再配置のタイミングが性能に影響を及ぼすため，アクセス時間間隔を考慮した
データ配置により高効率化を図った．また，アクセス単位のリ
スト更新により，アクセス情報管理の軽量化も行った．本手法の有用性を示すため SSD のヒット率と平均応答時間に関する実験を行った．Window Size を変更した実験においてはワーク
ロードによって適切な Window Size の決定が必要であることが分かった．3 つのワークロードに対し，提案手法と Cache 方式，従来の Tiering 方式の比較を行った結果，Cache 方式とはワークロードによって優位性が異なること，従来の Tiering 方式に対しては優位性があることが分かった．
また，SSD の特徴の観点から Write のヒット率は低下させる
ことが望ましい．そのため，アクセス情報を Read の I/O のみに限って記録するなど Write の SSD へのアクセスを避ける手法についても検討したい．また，今回の実験で得られたワーク

献[1] 林 真一，薦田 憲久，“階層ストレージにおけるボリューム階層化方式と SSD キャッシュ方式の評価，” 電学論Ｃ（電子・情報・システム部門），vol.134，No.3，pp.459-465，2014．
[2] T.M. Kroeger, D.D.E. Long, “Design and implementation ofa predictive file prefetching algorithm,” Proceedings of the2001 USENIX Annual Technical Conference，pp.105-118，
Jun, 2001.
[3] M. Iritani，H. Yokota, “Eﬀects on Performance and Energy
Reduction by File Relocation based on File-access Correlations,” Proceedings of the 1st Workshop on Enegy DataManagement, pp.79-86, Mar, 2012[4] Z. Li, Z. Chen, S.M. Srinivasan, and Y. Zhou, “C-Miner:
Mining Block Correlations in Storage System,” Proceedings of the 3rd USENIX Symposium on File and Storage
Technologies, pp.173-186, Mar, 2004
[5] X. Ding, S. Jiang, F. Chen, K. Davis, and X. Zhang,“DiskSeen:exploiting disk layout and access history to enhance I/O prefetch,” Proceedings of the 2007 USENIX Annual Technical Conference, pp.17-22, Jun, 2007
[6] R.H. Patterson, G.A.Gibson, E. Ginting, D. Stodolsky, and
J. Zelenlka, “Informed prefetching and caching,” Proceedings of the 15th ACM symposium on Operating systems
principles, pp.79-95, Dec,1995[7] D. Vengerov, “A reinforcement learning framework for online data migration in hierarchical storage systems,” The
Journal of Supercomputing Vol.43, Issue 1, pp.1-19, Jan,2008
[8] G. Zhang, L. Chiu, C. Dickey, L. Liu, P. Muench, and S.
Seshadri, “Automated lookahead data migration in SSDenabled multi-tiered storage systems,” Proceeding of the2010 IEEE 26th Symposium on Mass Storage Systems andTechnologies，pp.1-6，May, 2010[9] 大江 和一，岩田 聡，本田 岳夫，河場 基行，“On-The-Fly - Automated Storage Tiering（OTF-AST）の提案”，情処学シス
テムソフトウェアとオペレーティング・システム研究会，pp.1-10，
Feb，2014[10] S. Lee, H. Bahn, S.H. Noh, “CLOCK-DWF: A WriteHistory-Aware Page Replacement Algorithm for Hybrid
PCM and DRAM Memory Architectures,” IEEE Transactions on Computers, vol.63, no.9, pp.2187-2200, Sept, 2014[11] EMC White Paper, EMC VNX FAST VP A Detailed Review, 2013[12] D. Narayanan, A. Donnelly, and A. Rowstron, “Write OﬀLoading:Practical Power Management for Enterprise
Storage,” ACM Transactions on Storage, vol.4 Issue 3,
no.10, Nov, 2008[13] 新屋敷 裕太，飯澤 健，小沢 年弘，荒堀 喜貴，横田治夫， “階層ストレージシステムに向けたワークロードのブロックアクセス分
析に関する考察，” 信学技報，vol .115，no.177, DE2015-12，
pp.1-6，Aug，2015.
[14] M. Srinivasan, https://github.com/facebook/flashcache[15] A.D. Brunelle, “btrecord and btreplay User Guide ,”http://www.cse.unsw.edu.au/ aaronc/iosched/doc/btreplay.html