データベース更新差分を用いた範囲検索のIOコスト推定東京大学星野

[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
データベース更新差分を用いた
範囲検索のIOコスト推定
東京大学
星野喬、合田和生、喜連川優
2005年7月13日
1
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
背景と目的
 データベースの大容量化、多様化
 データベース常時運用ニーズの増大
データベース管理コスト低減が必要
 データベース再編成は不可欠な管理業務
– 再編成タイミングの判断は困難
– 高度な知識と経験を持つ管理者が必要
 目的: データベース再編成の自立化
– シンプルなデータベース再編成判断基準
– 充分な精度で構造劣化を判断
– オンライン業務に影響を与えることなく判断、実行
2
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
概要
 背景と目的
 データベース構造劣化と再編成
 クラスタ表における範囲検索のIOコスト推定
 更新差分を用いたリアルタイム推定手法
 評価
 まとめ
3
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
データベースの構造劣化と再編成
 構造劣化
– データベース更新によって引き起こされるデータ配置の乱れ
– データ配置の乱れは性能劣化の原因
 再編成
– 構造劣化を改善するための、データ再配置処理
クエリ
セット
Clean(構造劣化小)
更新操作...
再編成
クエリ
セット
性能劣化！
Dirty(構造劣化大)
4
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
データベース再編成を
いつすべきか？
 再編成をしないでそのまま運用を続けた場合、性能
要求を下回ると予測されるとき
性能
T1:再編成開始期限
T2:性能要求を下回る時刻
T2-T1:再編成に要する期間
性能要求
T1
T2
再編成期限
=性能要求を下回る時刻
- 再編成実行期間
時間
再編成タイミング判断には性能予測が必要
5
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
性能予測手法
 性能予測手法候補
– 実際の性能を測定
 構造劣化以外の原因との切り分けが困難
– データベース状態から性能を予測
 クエリ性能=CPUコスト+IOコスト
 構造劣化はIOコスト増大に直接影響
 対象
– MySQLクラスタ表の範囲検索
– データIOがボトルネックとなるアプリケーション
IOコスト推定による性能予測
6
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
概要
 背景と目的
 データベース構造劣化と再編成
 クラスタ表における範囲検索のIOコスト推定
– [星野ほか2004,2005]
 更新差分を用いたリアルタイム推定手法
 評価
 まとめ
7
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
MySQLにおける
クラスタ表のB+Tree構造
DBMS層での
論理構造
Branch pages
Leaf pages
Root page
b1
b2
0
1
1 b1
9
ストレージ層での
物理構造
b3
2
3
4
範囲検索は葉ページを
順序iで走査
•行は葉ページのみに存在
0 b0
8
4
論理(鍵)順ページ番号 i
0, 1, 2, 3, 4
b0
2
0
10
b2
3
4
11
12
1
b3
5
2
6
7
3
物理順ページ番号:
LBNi(=LBA/pagesize)
2, 4~5, 7~8
ページアクセスのIOコストが増加性能劣化
8
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
ハードディスクにおける
IO性能特性
トラック
セクタ
 ハードディスク内部におけるIOコストCaccess
Caccess  Cheadseek  Crotation  Ctransfer
ハードディスクプラッタ
– Cheadseek ヘッドが目的のトラックにシークするのにかかる時間
– Crotation ヘッドが目的のセクタに到達するのにかかる回転待ち時間
– Ctransfer メディアアクセス及びホストにデータを転送する時間
 ハードディスクのIOアクセス列をページ列 S  { pi : i  0,1,}
で表すとき、piのIOコストCiはハードディスク上の論理アドレ
ス、LBNi、LBNi-1で推定可能
– 正確な推定には、LBNi とハードディスクジオメトリとの対応情報、
ハードディスク個体性能情報、キャッシュ機構の情報が必要
– 簡単のため論理シーク距離⊿LBNi (= LBNi - LBNi-1 )を用いて
推定 C [sec]  f (LBN [page])
i
i
9
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
⊿LBN vs IOコスト
Rotation コスト変化
レスポンスタイム [ms]
ハードディスク上のランダムリード実験
Head seek コスト変化
⊿LBN [page]
10
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
レスポンスタイム [ms]
Rotationコスト平滑化による
IOコストの線形近似
Rotation cost を ½ と仮定し、
⊿LBN100毎にresponse time の平均値を取りプロット
⊿LBN [page]
11
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
レスポンスタイム [ms]
⊿LBN vs IOコスト (拡大図)
⊿LBNに対しRotationコストは
周期性を持つ
キャッシュヒット
プリフェッチヒット(sequential領域)
⊿LBN [page]
12
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
MySQLクラスタ表における
範囲検索IOコスト推定
 B+Treeにおける葉ページの対象範囲ページ群を、
Sの部分ページ列 R  { pi : i  i0 , i1 , iN 1} としてIOコ
ストCRを計算
i N 1
CR [sec]  i i Ci
0
 考慮したハードディスク特性
– ⊿LBNに対するHeadseekコスト
– ⊿LBNが1付近のシーケンシャルプリフェッチキャッシュ
ヒット
– |⊿LBN|<128のときのRotationコスト
– 2つ前までのIOアクセスを考慮したキャッシュヒット
13
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
概要
 背景と目的
 データベース構造劣化と再編成
 クラスタ表における範囲検索のIOコスト推定
 更新差分を用いたリアルタイム推定手法
 評価
 まとめ
14
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
IOコスト推定時のオーバーヘッド
 これまで提案した範囲検索IOコスト推定手法
– コスト推定の度に表(空間)全体を読み込み、分析する必
要あり
オーバーヘッド大
 データベース更新差分によるインクリメンタルな手法
– コスト推定のために表空間を読み込む必要がない
– MySQLのクラスタ表に対しては、B+Treeのページ分割、
結合時のみメモリ上にある更新情報を取得すればよい
オーバーヘッド小
リアルタイム推定が可能に
15
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
データベース更新差分を用いた
リアルタイムIOコスト推定
例ページ分割
i-2
i-1
i
i+1
i
i+1
i+2
 Ci old
 Ci n ew
 Ci new 1
任意のデータベース更新に対して、
C
new
R
C
old
R

C
deleted i old
i old

C
i new
inserted i new
16
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
データベース更新差分抽出器と
リアルタイムIOコスト推定器
アプリケーション
DBMS
システム状態モニタ
クエリ
表空間モニタ
自立再編成器
クエリプロセッサ
データベースエンジン
B+Tree更新差分抽出器
通常IO
ハードディスク
フィード
バック
B+Tree
分割/結合
更新差分
再編成実行
保持している推定IOコストを
更新差分を元にアップデート
リアルタイム
IOコスト推定器
構造劣化同定器
再編成スケジューラ
再編成実行器
17
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
概要
 背景と目的
 データベース構造劣化と再編成
 クラスタ表における範囲検索のIOコスト推定
 更新差分を用いたリアルタイム推定手法
 評価
 まとめ
18
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
評価
 データベース更新差分抽出器をMySQLに実装
 TPC-Hベンチマークを用いて実験
– 範囲検索のリアルタイムIOコスト推定が、従来手法と同
じ精度を持つことを確認
– データベース更新におけるデータベース更新差分抽出器
のオーバーヘッドを測定
19
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
実験環境
Xeon3.2GHz x2
Memory 2GB
HBA Emulex LP8000 (PCI-X 133MHz)
Linux 2.4.21
1Gbit FCスイッチ
 DBMS: MySQL 4.1
– 更新差分抽出器あり
– 更新差分抽出器なし
 素のMySQL
 ストレージ: Cheetah FC
Disk 18GB
(ST318203FC)
– disk cache 1MB
 3 segment
– Average rotation
latency 5.4ms
– Max throughput 28MB/s
– Max track size 230KB
ディスクアレイ(JBOD)
20
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
実験内容
 アプリケーション: TPC-Hベンチマーク
– 初期設定
 SF=0.1 (初期ロード時に220MB程度表空間を使用)
 クラスタ表を使用
– データ初期ロード
 10回初期ロードを行い、オーバーヘッドを算出
– 更新: TPC-H の RF1 と RF2 を用いて更新
 Orders表とLineitem表にデータが挿入、削除される
 1回でデータベースの1%を更新
 データ量、主鍵分布はほとんど変化しない
 全実験における更新時間から、オーバーヘッドを算出
– クエリ: Orders表とLineitem表の全表検索
 更新複数回ごとに実行
 実測値を測定、従来手法による推定IOコスト、更新差分を用いた
推定IOコストを算出
21
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
Orders表の全表検索性能
22
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
Lineitem表の全表検索性能
23
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
データベース更新差分抽出器
のオーバーヘッド
24
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
考察
 推定精度
– Orders表: 誤差17%以下
 データ量が少なく、他のオーバーヘッドが大きい
(1.3秒程度のクエリ実行時間)
– Lineitem表: 誤差6%以下
– クエリ実行時間はCPUコストも含む(推定IOコストは含まず)
– 従来手法と同じ推定精度
 推定されるIOコストは論理的にまったく同じ
 オーバーヘッド
– データ更新時:1.0%
– データロード時:0.2%
 B+Treeにおけるページ分割よりも、ページ結合の方がコストが少ないた
め
 更新されるデータ量に対して、ページ分割及び結合の頻度が多い更新
パタンであるため、これ以上オーバーヘッドが大きくなる可能性は小
25
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
概要
 背景と目的
 データベース構造劣化と再編成
 クラスタ表における範囲検索のIOコスト推定
 更新差分を用いたリアルタイム推定手法
 評価
 まとめ
26
[DBWS2005] データベース更新差分を用いた範囲検索のIOコスト推定
まとめ
 結論
– クラスタ表における範囲検索の低オーバーヘッドIOコスト推定手法を
提案
– 提案手法をMySQLに実装
– 評価では、オーバヘッド1%未満で17%以下の誤差でIOコストを推
定可能であることを示した
 今後の課題
– 高度ストレージへの対応 (RAID)
– 他のクエリへの対応 (Join等)
– 表空間リアルタイム分析ツールの実現
 充填率やキャッシュヒット率などと統合し、再編成による回復量の推定
27

Download Report