ディスク空き領域を用いるレプリケーション手法における 複製数の増加

DEWS2008 D1-2
ディスク空き領域を用いるレプリケーション手法における
複製数の増加による性能向上
窪田 将希†
山口 実靖†
淺谷 耕一†
†工学院大学工学部 〒163-8677 東京都新宿区西新宿 1- 24-2
E-mail: †[email protected],[email protected],[email protected]
あらまし 近年，情報処理システムが処理する情報量は飛躍的に増加している．この増大した情報を高速に処理
するために，ストレージシステムには非常に高い性能が要求されるようになっている．しかし，主たる情報蓄積装
置である HDD はその機械的構造からランダムアクセス時における高速なデータ処理の実現が容易ではない．これ
に対して HDD の容量は著しい速度で増加をしており，多くの情報処理システムが使用されていない記憶領域を大
量に有している．この状況を考慮し，同一の HDD の空き領域内にデータの複製を配置しランダムアクセス性能を
向上させる研究が行われている．本研究では複製の数を増加させることにより，更なる性能向上を実現する手法を
提案する．そして，性能評価結果を紹介し提案手法の有効性を示す．
キーワード ストレージ，複製技術
Performance Improvement of Free Disk Space Replication
by Increasing Number of Replications
Masaki KUBOTA†
Saneyasu YAMAGUCHI†
and
Koichi ASATANI†
†Kogakuin University 1-24-2 Nishi-Shinjyuku, Shinjyuku-ku, Tokyo, 163-8677 Japan
E-mail: †[email protected],[email protected] ,[email protected]
Abstract Recent computer systems process huge amount of data. Storage systems are required to provide very high
performance. However, performance of storage device is not enough to process these huge data, especially in the case of
random access. On the other hand, storage capacity is rapidly increasing. Thus computer systems have many unused space.
Free Space Filesystem creates file replicas in unused storage space in order to improve storage performance. In this paper, we
discuss relation between number of replicas and performance, and propose performance improving method by increasing
number of replicas.
Keyword
1.
Strage,Data Replication，
はじめに
使用されていない記憶領域を大量に有している．これ
近年，情報処理システムで処理する情報量が飛躍的
の 状 況 を 考 慮 し ， 同 一 の HDD の 空 き 領 域 内 に デ ー タ
に増加している．この増大した情報を高速に処理する
の複製を配置しランダムアクセス性能を向上させる研
ために，ストレージシステムには非常に高い性能が要
究 が 行 わ れ て い る [1]．本 研 究 で は 複 製 の 数 を 増 加 さ せ
求されるようになった．しかし，主たる情報蓄積装置
ることによりこれを発展させ，更なる性能向上を実現
で あ る HDD は そ の 機 械 的 構 造 か ら 情 報 へ の ラ ン ダ ム
すること目的とする
なアクセスの性能が高くなく，高速なデータ処理の実
現は容易ではない．デバイス性能は数年で 2 倍程度の
低い成長だが，これに対してストレージの容量は年率
2. デ ィ ス ク ア ク セ ス 時 間 と フ ァ イ ル シ ス テ ム
デ ィ ス ク ア ク セ ス 時 間 は ，ヘ ッ ド が デ ィ ス ク の 目 的 ト
50%増 加 す る 急 速 な 成 長 を し て お り ， ス ト レ ー ジ の 大
ラ ッ ク へ の 移 動 す る 時 間 (シ ー ク 時 間 )， ヘ ッ ド が 移 動
容量化はデバイス性能向上を上回る速度で達成されて
完了後にディスクが目的のセクタへ回転するまでの時
い る ．そ の た め ，企 業 の 計 算 機 の デ ィ ス ク 使 用 率 は 50%
間 (回 転 待 ち 時 間 )， デ ー タ 転 送 時 間 の ３ つ に よ り 構 成
程 度 で あ る こ と が 多 く [1]，多 く の 情 報 処 理 シ ス テ ム が
されている．ランダムアクセスの場合ディスクアクセ
ス時間の大部分をシーク時間，回転待ち時間が占めて
い る ．デ ィ ス ク の 異 な る ア ド レ ス に ア ク セ ス し た 場 合 ，
3. FreeSpaceFileSystem(FS2)
FS2 は ，フ ァ イ ル シ ス テ ム の Ext2 を 改 変 し た も の で
移 動 時 間 (シ ー ク 時 間 +回 転 待 ち 時 間 )が 発 生 す る ．移 動
あり，ディスクの大容量化により生じた空きブロック
距 離 と 移 動 時 間 の 関 係 の 調 査 結 果 を 図 1，2 に 示 す ．図
の増加に着目し，空きブロックにファイルのレプリカ
2 は図 1 を拡大したものである．図 1 より移動距離が
を配置し，ランダムアクセス性能を向上させるもので
増加すると移動時間が増加していることが分かる．こ
あ る [1]．具 体 的 に は ア ク セ ス パ タ ー ン の 観 察 に 基 づ き
れは，移動距離が増加したことによりシーク時間が増
連続アクセスするファイルのレプリカを近隣に配置し，
加したことが原因である．また図 2 より移動距離があ
HDD の ヘ ッ ド の 移 動 量 を 減 少 さ せ る こ と に よ る ア ク
る一定まで増加すると移動時間が減少していることが
セス性能を向上させる．図 3 に動作例を示す．
分かる．この周期はディスクの回転待ち時間の周期で
ある．
こ の 例 で は フ ァ イ ル 0,1,2 の 順 に ア ク セ ス が 行 わ れ
る．ファイル 1 が他のファイルと離れた場所に配置さ
れ て い る た め に ，シ ー ク 距 離 が 増 加 し て い る ．そ こ で ，
フ ァ イ ル 1 の レ プ リ カ を フ ァ イ ル 0，2 の 近 隣 に 配 置 す
12
ることによりシーク時間の短縮が可能となる．それに
よりアクセス性能を向上させている．本手法では，レ
8
プ リ カ の 数 は 最 大 で 1 個 (オ リ ジ ナ ル と レ プ リ カ の 合
6
計 で 2 個 )ま で と し て い る ．
4
2
0
0
50000
図 1
100000
移動距離[KB]
150000
200000
シーク距離とアクセス速度の関係
12
10
移動時間[msec]
移動時間[msec]
10
図 3
8
FS2 に お け る 動 作 例
6
4
4. 複 数 の 空 き 領 域 複 製
2
0
0
500
移動距離[KB]
1000
FS2 に お い て ，空 き 領 域 へ の フ ァ イ ル の レ プ リ カ の 作
成および配置は 1 個のみで行われている．そこで，本
研究では空き領域へのファイルレプリカ数を増加させ
図 2
シーク距離とアクセス速度の関係
ることにより，更なるディスクアクセス性能向上を実
現させる手法について考察する．
ファイルを作成，配置する際にファイルシステムは
ア ク セ ス パ タ ー ン を 想 定 せ ず に 配 置 を 行 う ．そ の た め ，
4.1
HDD ア ク セ ス パ タ ー ン の 調 査
連続してアクセスされるファイルが離れて配置される
ア プ リ ケ ー シ ョ ン の HDD ア ク セ ス パ タ ー ン の 調 査
ことがあり，その場合にはシーク時間が増加し，ディ
として，アプリケーションを起動する際に発生する読
スクアクセス性能が低下する．この問題は，連続して
み 込 み HDD ア ド レ ス と フ ァ イ ル 名 の 取 得 を 行 っ た ．
アクセスされやすいファイルを近隣に配置することに
ア プ リ ケ ー シ ョ ン に は Firefox と OpenOffice Calc を 用
よって改善することが可能である．
いた．実験環境を表 1 に示す．また，各アプリケーシ
次章にて，ヘッドのシーク時間の短縮によるファイ
ョンのアクセスパターンの測定結果を図４，図 5 に示
ルアクセス性能向上を目的としたレプリケーション手
す ．図 ４ よ り ，Firefox 起 動 時 に は 主 に デ ィ ス ク ア ド レ
法 で あ る Free Space FileSystem を 紹 介 す る ．
ス 50GB 近 辺 ，80GB 付 近 に ア ク セ ス さ れ ，様 々 な ア ク
セ ス が 見 ら れ た ． OpenOffice Calc は 主 に 50GB 付 近 ，
4.2
性能測定
100GB 付 近 に 集 中 し て ア ク セ ス さ れ た ． 50GB 付 近 に
本節では複数の複製が作成された場合のストレー
は /usr/lib/openoffice.org2.0/ 以 下 の フ ァ イ ル が あ り ，
ジアクセスをシミュレートし，複数複製手法における
100GB 付 近 に は /root/.openoffice.org2.0/ 以 下 の フ ァ イ
複製の数と性能の関係を調査する．
ルがある．
ま ず ，Firefox 起 動 時 の ス ト レ ー ジ ア ク セ ス 時 間 に つ
いて調査を行う．図 4 のアクセスパターンを元に，複
表 1
実験環境
製を用いない従来手法，単一の複製を用いる手法，複
数の複製を用いる手法，全ブロックを連続して空き領
OS
FedoraCore6
CPU
Intel(R) Pentium 4 CPU 2.80GHz
域に複製する手法で得られる性能を測定した．
単 一 の 複 製 を 用 い る 手 法 で は ，100GB 付 近 の ブ ロ ッ
ク の レ プ リ カ を 60GB 付 近 の 空 き 領 域 に 配 置 を し た 場
File System
ext3
Kernel
Linux 2.6.18.8
HDD
合 を 想 定 し ，ス ト レ ー ジ ア ク セ ス 性 能 の 測 定 を 行 っ た ．
100GB 付 近 の ブ ロ ッ ク に 保 存 さ れ て い る フ ァ イ ル は
/usr/lib/firefox-1.5.0.12/で Firefox の フ ァ イ ル で あ る ．
単一複製配置したアクセスパターンを図 6 に示す．本
WDC WD1200JB-75CRA0
例ではアクセスされるアドレスの中心からもっとも遠
Rotational
Speed
Capacity
7200rpm
いブロック群のみを複製の対象とした．
複数の複製を用いる手法では，上記単一複製に加え
120GB
30GB 付 近 の フ ァ イ ル の 複 製 も 配 置 し た 場 合 を 想 定 し
120
性 能 を 測 定 し た ． 30GB 付 近 の ブ ロ ッ ク に 保 存 さ れ て
↓ /usr/lib/firefox-1.5.0.12/
い る フ ァ イ ル は ， /etc/fonts/conf.d/75-blacklist-
100
fedora.conf や /bin/bash な ど の 多 数 の ア プ リ ケ ー シ ョ ン
Disk Address[GB]
↓ /root/mozilla/firefox/
により使用されるファイルであり，複製数が 1 個に限
80
定 さ れ て い る 状 況 に お い て は こ れ の 複 製 を Firefox の
近隣に配置することはできない．本例でも同様に，ア
60
↑ /usr/lib/firefox-1.5.0.12/
クセスされる中心アドレスから最も遠いブロック群の
みを複製の対象とした．
40
↑ /usr/lib/firefox-1.5.0.12/
↑ /bin/bash
20
全ブロック複製手法は，アクセスされる全ブロック
↑ /etc/etc/fonts/conf.d/
を 100GB 付 近 の 連 続 し た 空 き 領 域 に 複 製 し た 理 想 的
な状況における性能である．複数複製配置，全ブロッ
0
0
1
2
3
4
5
6
Time[sec]
Disk Access [GB]
図 4
100
90
80
70
60
50
40
30
20
10
0
ク複製を行った際のアクセスパターンを図 7 に示す．
アクセス性能は，上記手法によりアクセスされるア
ド レ ス に 対 し て I/O 要 求 を 発 行 し ， 全 ア ク セ ス に 要 し
Firefox に お け る ア ク セ ス パ タ ー ン
た時間を測定した．本測定はアプリケーションが行う
CPU 処 理 の 時 間 を 除 い た HDD ア ク セ ス 時 間 の み の 測
/root/openoffice2.0
定である．測定結果を表 2 に示す．
次 に ，OpenOffice Calc 起 動 時 の ス ト レ ー ジ ア ク セ ス
/root/.beagle/ToIndex/
に関する調査を行う．同様に図 5 におけるアクセスパ
タ ー ン を 元 に 複 製 を 行 う ．単 一 複 製 手 法 で は 100GB 付
/usr/lib/openoffice2.0
/bin/bash
近 の ブ ロ ッ ク を 50GB 付 近 に 複 製 し た 場 合 を 想 定 し 測
定 し た ．100GB 付 近 の ブ ロ ッ ク に 保 存 さ れ た フ ァ イ ル
/etc/etc/fonts/conf.d/
は /root/openoffice2.0 な ど の Openoffice の フ ァ イ ル で あ
る ． 複 製 複 数 手 法 で は 30GB 付 近 の ブ ロ ッ ク も 50GB
0
2
4
6
Time [sec]
図 5
OpenOffice Calc に お け る
アクセスパターン
8
付近に複製した場合を想定し，全ブロック複製手法で
は ア ク セ ス 対 象 の 全 ブ ロ ッ ク の 複 製 を 100GB 付 近 の
連続空き領域に連続して配置した場合を想定している．
測定結果を表 3 に示す．
表 3
120
OpenOffice Calc に お け る
ディスクアクセス性能
Disk address[GB]
100
アクセス時 間 [msec]
80
複 製 なし
7074.9
40
単一複製
6170.46
20
複数複製
6007.2
全 ブロック複 製
1386.4
60
0
0
1
図 6
2
3
Time[sec]
4
5
6
7. お わ り に
Firefox の 単 一 複 製 手 法 に お け る
本稿では，ストレージアクセス性能向上を目的とし
アクセスパターン
た空き領域へのファイル複製手法を，複数数の増加に
よりさらに改善する手法を提案した．そして，アプリ
ケーション起動時のストレージアクセスパターンを取
120
得 し ， 複 製 数 が 増 加 さ れ た 場 合 に 行 わ れ る I/O 処 理 を
Disk Address[GB]
100
シミュレートし本手法のとして有効性の検証を行った．
測定結果より，性能が向上されることを確認した．
80
今後は，提案手法のファイルシステムへの実装やそ
60
れを用いた性能の測定，別のアプリケーションを用い
40
ての検証，レプリカの管理法，さらなる性能向上手法
複数複製手法
全ブロック複製
20
についての考察を行う予定である．
0
0
図 7
1
2
3
Time[sec]
4
5
6
複数複製手法及び全ブロック複製手法
におけるアクセスパターン
表 2,3 よ り ， 複 製 を 用 い る こ と に よ り ス ト レ ー ジ ア
クセス性能を向上させることが可能であることがわか
り，複製数を増加させることにより更なる改善が可能
であることが確認された．アプリケーションがアクセ
スする全ブロックを連続領域に複製する手法は，大量
の空き領域と多くの複製時間が必要となると考えられ
るが，大幅な性能改善が期待でき使用頻度の高いアプ
リケーションに関しては有効な手法になると考えられ
る．
表 2
Firefox に お け る デ ィ ス ク ア ク セ ス 性 能
アクセス時 間 [msec]
複 製 なし
4042.2
単一複製
3997.7
複数複製
3678.8
全 ブロック複 製
495.5
文
献
[1] Hai Huang, Wanda Hung, Kang G.Shin,“FS2:
Dynamic Data Replication in Free Disk Space for
Improving
Disk
Performance
and
Energy
Consumption,” SOSP 2005 pp. 263-276
[2] John Douceur and William Bolosky, A Large-cale
Studyof File-System Contents, ACM SIGMETRICS
Performance Review, 59–70, 1999.
[3] C. Lumb and J. Schindler and G. Ganger and D. Nagle
and
E. Riedel, Towards Higher Disk Head
Utilization: Extracting Free Bandwidth from Busy
Disk Drives, Proceedings of the Symposium on
Operating Systems Design and Implementation, 2000
[4] Linux Filesystem Performance Comparison for
OLTP,http://oracle.com/technology/tech/linux/pdf/Li
nux-FSPerformance[5] M. K. McKusick et al., A Fast File System for UNIX,
ACM Transactions on Computing Systems (TOCS),
2(3), 1984.
[6] M. K. McKusick et al., A Fast File System for UNIX,
ACM Transactions on Computing Systems (TOCS),
2(3), 1984.
[7] Douglas Orr and Jay Lepreau and J. Bonn and
R.Mecklenburg, Fast and Flexible Shared Libraries,
USENIX Summer, 237–252, 1993
[8] Sedat Akyurek and Kenneth Salem, Adaptive
BlockRearrangement, Computer Systems, 13(2):
89–121, 1995.
[9] P. J. Denning, Effects of Scheduling on File Memory
Operations,
AFIPS
Spring
Joint
Computer
Conference,9–21, 1967.