1. No category

低優先度処理を指定可能な
リアルタイム処理向け
I/Oスケジューラ
髙村成道，鵜川始陽，岩崎英哉
電気通信大学
2014年 3月 7日
リアルタイムサービスの普及
•  リアルタイム性を必要とするWebサービスの例
•  ソーシャルゲーム，チャット，SNS...
•  定期的なメンテナンスが必須
⇒ サービスを継続したままメンテナンスを行う
オンラインメンテナンス
2
オンラインメンテナンス
•  問題点
•  作業負荷によるサービス品質の低下
⇒ 本研究では I/O 負荷に着目
•  I/O 負荷を伴うオンラインメンテナンスの例
•  データベースサーバ上の巨大なログファイルの削除
3
オンラインメンテナンスの例 (1)
データベース
プロセス
メンテナンス
プロセス
巨大なログの削除
(緊急性がない作業)
4
オンラインメンテナンスの例 (2)
データベース
プロセス
データベース処理の
スループットが減少
メンテナンス
プロセス
メンテナンス処理により
本来優先すべき処理が
妨げられてしまう
5
I/O スケジューラ
•  I/O 要求を適切に並び替えるソフトウェア
•  Linux カーネルに組み込まれている
リアルタイム処理 I/O 優先度指定
CFQ
スケジューラ
Deadline
スケジューラ
☓
⇒リアルタイム処理向きであり，かつ，優先度指定可
能な I/O スケジューラは無い
6
目的・方針
目的
オンラインメンテナンスによるサービスの品質低下を防ぐ
方針
•  低優先度処理が指定可能なリアルタイム向けの
I/O スケジューラの実装
⇒ Deadline スケジューラを拡張
7
ファイル I/O の概略
ユーザ空間
プロセス
VFS
カーネル空間
汎用ブロック層
I/O スケジューラ層
ファイルシステム
ディスク
キャッシュ
デバイス
ドライバ
デバイス
ドライバ
物理
デバイス
物理
デバイス
8
I/O スケジューラの動作概要
汎用ブロック層
デバイスドライバ
処理する順に 要求を格納 要求の並び替え ディスパッチキュー
処理順序の制御は 物理
要求がサブキューに デバイス
ある場合に可能
サブキュー
I/O スケジューラ
9
Deadline スケジューラの動作
データベース処理の要求
1 1 2 3 2
メンテナンス処理の要求
サブキュー
ディスパッチ
キュー
1 1 2 3 2
時間
10
Deadline スケジューラの拡張
•  処理性能の維持
•  低優先度処理の追加
•  低優先度処理のスループット制限
•  I/O 帯域の有効活用
11
低優先度処理のスループット制限（1）
データベース
プロセス
メンテナンス
プロセス
低優先度処理の
スループットを抑え，
メインの処理に多くの
スループットを割り当てる12
低優先度処理のスループット制限（2）
•  通常（データベース処理）の要求はそのまま
処理する
•  低優先度要求は一定時間ごとに保留する
•  保留の処理はサブキューを用いる
13
低優先度処理のスループット制限（3）
データベース処理の要求
1 1 2 3 2
メンテナンス処理の要求
サブキュー
ディスパッチ
キュー
1 1
α
2 2
α
3
時間 14
I/O 帯域の有効活用（1）
データベース
プロセス
メンテナンス
プロセス
一定時間，メインの処理
が行われない場合，
低優先度処理の
スループット制限を解除
15
I/O 帯域の有効活用（2）
1 1 2 3 4 5
サブキュー
ディスパッチ
キュー
2
1 1
α
β
3 4 5
α
時間 16
I/O 帯域の有効活用（3）
6 2 7 8 9
サブキュー
ディスパッチ
キュー
7
5 6 2
8 9
α
β
時間 17
2つのモード
•  通常モード
•  低優先度処理のスループット制限をして処理する
•  バッチモード
•  低優先度処理のスループット制限をせずに処理する
18
タイマによるディスパッチ制御
•  カーネルタイマを利用
•  α 時間後に1つの低優先度要求をディスパッチ
•  β 時間後にバッチモードへ切り替え，すべての低
優先度要求をディスパッチ
19
実験環境
OS
CentOS release 6.5 (Final)
Linux カーネル 3.12.7
CPU
Intel Core i7-3770 @ 3.40GHz 4 コア
メモリ
8 GiB
物理デバイス 1 SSD 240GB
（Intel SSDSC2CT240A4）
物理デバイス 2 HDD 320 GB, 7200 rpm
（Hitachi HDP72503）
ベンチマーク
ツール
sysbench
20
評価: 低優先度処理の影響 (1)
実験内容
•  データベースサーバ（MySQL）を利用
•  低優先度処理がある場合は，ない場合と比
較して何%の性能が出るかを測定
•  通常の処理: データベース処理
•  低優先度処理: Sequential Read
•  α = 200ms, β = 500 ms
21
HDD
SSD
HDD
SSD
評価: 低優先度処理の影響
(2)
Normal I/O TPS / Low Prio I/O TPS [%]
1010
00
110
100
90
80
70
60
50
40
30
20
10
0
Deadline
Deadline
Our
OurScheduler
Scheduler
HDD
SSD
22
HDD
SSD
HDD
SSD
評価: 低優先度処理の影響
(2)
Normal I/O TPS / Low Prio I/O TPS [%]
1010
00
110
100
90
80
70
60
50
40
30
20
10
0
Deadline
Deadline
Our
OurScheduler
Scheduler
既存のDeadline スケジューラでは， 70 % 以上の性能が低下した
HDD
SSD
23
HDD
SSD
HDD
SSD
評価: 低優先度処理の影響
(2)
Normal I/O TPS / Low Prio I/O TPS [%]
1010
00
110
100
90
80
70
60
50
40
30
20
10
0
Deadline
Deadline
Our
OurScheduler
Scheduler
本機構では，1 % 未満の性能低
下に抑えることができた
HDD
SSD
24
評価: スループットの推移
実験内容
•  5GB のファイル読み込み
•  2つの処理に対して，1秒ごとにスループット
を測定し，変化を確認
•  通常の処理: Sequential Read
•  低優先度処理: Sequential Read
•  α = 200 ms, β = 5000 ms
25
Throughput ( Mbytes/sec )
評価: スループットの推移
250
200
150
100
低優先度処理が通常
の処理を妨げている
50
0
0
5
10
15
Deadline での通常処理と Deadline での低優先度処理
20
25
Time ( sec )
30
Deadline Normal I/O
35
40
45
26
Throughput ( Mbytes/sec )
評価: スループットの推移
250
本機構での通常の処理
200
通常の処理がすぐに完了し，
その後スループットを有効
活用している
150
100
本機構での低優先度処理
50
0
0
5
10
15
β
20
25
Time ( sec )
30
Deadline Normal I/O
35
40
45
27
評価: 拡張によるオーバーヘッド
実験内容
•  1 分間のファイルアクセスを実行
•  スループット (Mbytes/sec) を比較
110
Our Scheduler / Deadline [%]
100
90
80
70
60
50
通常のI/O要求を処理する上で，
既存のDeadline スケジューラと 本機構との性能差はほぼない
40
30
20
10
0
SeqRead RndRead SeqWrite RndWrite
28
関連研究（1）
•  汎用向けの高性能スケジューラ
•  CFQスケジューラの高性能化 [Lunde, 2009]
•  各種スケジューラの高性能化 [Seelam, 2005]
•  高速デバイス向けのスケジューラ
•  SSD 向けのスケジューラの実装 [Dunnら, 2009]
•  Fusion-io 向けのスケジューラの実装 [Robin, 2013]
⇒高速化が目的でありオンラインメンテナンスに
配慮したスケジューラを実現する研究ではない
29
関連研究（2）
•  cgroups [Linux 準拠 (v2.6.24 以降)]
•  スケジューラに依存することなく，スループットの
上限を指定可能
•  プロセスごとに設定が必要
⇒本研究では，I/O スケジューラを拡張した
30
まとめ
•  低優先度を指定可能なリアルタイム処理向け
の I/O スケジューラの設計・実装を行った
•  提案機構の評価を行い有効性を確認した
•  既存のものでは性能低下が70 % 以上であるのに
対し、本機構では 1% 未満に抑えることができた
31
32
α の設定値によるスループットの変化
Throughput ( Mbytes/sec )
120
100
80
60
40
20
0
10
50
100
150
200
Time ( sec )
250
300
33
ファイル I/O の概略
ユーザ空間
プロセス
VFS
カーネル空間
汎用ブロック層
I/O スケジューラ層
ファイルシステム
ディスク
キャッシュ
デバイス
ドライバ
デバイス
ドライバ
物理
デバイス
物理
デバイス 34
Deadline スケジューラの動作 (1)
セクタ番号順
並べ替えキュー
s: 98 s: 41 s: 23
t: 2 t: 5 t: 3
I/O 要求の
発行順
期限付きキュー
s: 41 s: 23 s: 98
t: 5 t: 3 t: 2
末尾
先頭
処理実行
s: セクタ番号 t: 発行要求時刻
35
拡張後のスケジューラの動作 (1)
並べ替えキュー
低優先度 要求の追加
s: 77
t: 7
s: 98 s: 64 s: 41 s: 23
t: 2 t: 6 t: 5 t: 3
期限付きキュー
s: 64 s: 41 s: 23 s: 98
t: 6 t: 5 t: 3 t: 2
処理実行
低優先度キュー
36
拡張後のスケジューラの動作 (2)
並べ替えキュー
s: 98 s: 64 s: 41 s: 23
t: 2 t: 6 t: 5 t: 3
期限付きキュー
s: 64 s: 41 s: 23 s: 98
t: 6 t: 5 t: 3 t: 2
処理実行
低優先度キュー
s: 77
t: 7
37
拡張後のスケジューラの動作 (3)
並べ替えキュー
s: 98 s: 64 s: 41
t: 2 t: 6 t: 5
期限付きキュー
s: 64 s: 41 s: 98
t: 6 t: 5 t: 2
処理実行
低優先度キュー
s: 77
t: 7
38
拡張後のスケジューラの動作 (4)
並べ替えキュー
期限付きキュー
処理実行
低優先度キュー
s: 77
t: 7
39
実装: カーネルタイマによる制御
1 1 2 3 4 5
dispatch()
dispatch()
dispatch()
dispatch()
Sub Q
set(β)
Dispatch Q
set(α)
2
1 1
mode(normal)
set(α)
α
β
3 4 5
mode(batch)
時間 40