HOSHINO Takashi Kitsuregawa Lab. 2007/11/15

Presentation on theme: "HOSHINO Takashi Kitsuregawa Lab. 2007/11/15"— Presentation transcript:

1 HOSHINO Takashi Kitsuregawa Lab. 2007/11/15
再編成論文サーベイ2 HOSHINO Takashi Kitsuregawa Lab. 2007/11/15

2 内容 再編成に関連する論文overview 論文誌におけるNoveltyとEffectivenessの議論
[ hoshino] 再編成論文サーベイ2 内容 再編成に関連する論文overview 論文誌におけるNoveltyとEffectivenessの議論

3 Optimum Data Base Reorganization Points
[ hoshino] 再編成論文サーベイ2 Optimum Data Base Reorganization Points Ben Chneiderman (State University of New York) Communications of the ACM 1973

4 概要 再編成タイミングのanalyticalな評価 我々との比較 定期的に再編成する方式を数式として導出
[ hoshino] 再編成論文サーベイ2 概要 再編成タイミングのanalyticalな評価 定期的に再編成する方式を数式として導出 コスト密度(レコードあたりのサーチコスト)がある一定まで下がった場合に再編成する方式を数式として導出 上記の比較をして、概して後者の方がコストが低いので、構造劣化の進行速度が一定でないような場合には、後者を使うべきだとしている 我々との比較 サーチコストは抽象化されている。 Ex. オーバーフローレコードのサーチコストは2倍 容易に取れる統計値を判断に用いている # of records, # of overflows, rate of addition/deletion

5 Opportunities For Data Base Reorganization
[ hoshino] 再編成論文サーベイ2 Opportunities For Data Base Reorganization Ben Shneiderman (Indiana University) Sigmod Record 1974

6 概要 データベース再編成の実施機会について考察 我々との比較 構造で分類
[ hoshino] 再編成論文サーベイ2 概要 データベース再編成の実施機会について考察 構造で分類 Access path reorganization (treeの深さ) Block overflow reorganization (充填率) Linked reorganization (充填率) Indexed sequential access method reorganization (sequentiality) 何にせよappropriate performance statisticsを得ることが重要だが、measurableでないため難しい。Best sourceは実性能データ いつ再編成をすれば良いかsolutionを出していない 我々との比較 問題提起と構造分類のみ(まともな構造分類もできていない)

7 Reorganization Points for File Designs with Nonlinear Processing Costs
[ hoshino] 再編成論文サーベイ2 Reorganization Points for File Designs with Nonlinear Processing Costs K. Sundar Das, T. J. Teorey, S. B. Yao (The University of Michigan) VLDB1975

8 概要 成長するファイルに対して再編成タイミングを予測する方式について実験による評価 我々との比較
[ hoshino] 再編成論文サーベイ2 概要 成長するファイルに対して再編成タイミングを予測する方式について実験による評価 内部レコードにdelete flagが存在するファイルを想定 IOコスト: ファイルにアクセスするIO応答時間 (おそらくスキャン) 再編成された場合のIOコストとされない場合のIOコストの差は、過去に観測されたものと同じと見なす 再編成をするタイミングは、Cn>=C’n + Rn/nとなる最小のnth time period Cn: (1st periodの最初に再編成された場合の)n+1番目のperiodのにおけるIOコスト C’n: (nth periodの最後に再編成された場合の) n+1番目のperiodにおけるIOコス ト Rn: nth periodの最後に実施した再編成コスト n: 経過時間 何が実測値で、何が代用値なのかさっぱりわからない。。。 我々との比較 経験則による再編成タイミング予測

9 Optimal Reorganization of Distributed Space Disk Files
[ hoshino] 再編成論文サーベイ2 Optimal Reorganization of Distributed Space Disk Files K. Maruyama and S. E. Smith (IBM Thomas J. Watson Research Center) Communications of the ACM 19(11), 1976

10 [ hoshino] 再編成論文サーベイ2 概要 Analyticalなモデルで、deterioration costとreorganizationコストを記述し、ケーススタディで最適な再編成タイミングを導出 DSDF (Distributed Space Disk File)が対象 我々との比較 Analyticであるが故にワークロード記述が単純 Cylinder splitでdeterioration costが上がることが示されており、page splitと原理的には同じ

11 Optimal File Designs and Reorganization Points
[ hoshino] 再編成論文サーベイ2 Optimal File Designs and Reorganization Points D. S. Batory (University of Tronto) TODS 1982

12 概要 データ構造のデザインと再編成は同時に考えるべきだとして、再編成タイミングをanalyticalモデルから導出する方式を提案
[ hoshino] 再編成論文サーベイ2 概要 データ構造のデザインと再編成は同時に考えるべきだとして、再編成タイミングをanalyticalモデルから導出する方式を提案 Hash と indexed-sequential fileで評価 初期充填率と再編成タイミングには反比例の関係があると指摘 我々との比較 再編成タイミングは定期的

13 Optimum Reorganization Points for Arbitrary Database Costs
[ hoshino] 再編成論文サーベイ2 Optimum Reorganization Points for Arbitrary Database Costs Raul J. Ramirez, Frank W. Tompa, and J. Jan Munro (University of Waterloo) Acta Informatica 18, 1982

14 [ hoshino] 再編成論文サーベイ2 概要 グラフにおける最短経路問題に帰着して、Dynamic Programming法で再編成タイミングを導出する方法を提案(formalization) 構造劣化度(deterioration)やある時点における再編成コストは導出可能である前提を置いている。 計算コストは、データベースのlifetime Tを用いて、O(T**2)の計算時間, O(T)のメモリスペースが必要 これまでの研究はlinearな振る舞いしか扱えなかったが、提案手法はdeterioration costがnon-linearでも計算できると主 例として、logarithmeticなケースを上げていたが、いちいちsearchコストやreorgコストを導出する必要があった。 我々との比較 構造劣化度の導出方法について言及していない。 未来が予測できるという前提。Offlineアルゴリズムといっても良い?

15 A Reorganization Model Based on the Database Entropy Concept
[ hoshino] 再編成論文サーベイ2 A Reorganization Model Based on the Database Entropy Concept K. T. Fung (American Bell Inc.) The Computer Journal 27(1) 1984

16 [ hoshino] 再編成論文サーベイ2 概要 (よくわかっていない) 最大エントロピー法で、クエリセット(アクセスの確率分布)とデータベース状態セットの相互情報量を用いて再編成タイミングを決める方法を提案 データベース状態として、キャッシュヒット率を使用 時間が経つにつれてアクセス分布が変わっていくにつれ、相互情報量Cが変化し、閾値を越えたら再編成。 評価 再編成というよりは、ILM的な環境におけるmigrationを用いて評価 提案手法を用いたら、再編成頻度が減った。 我々との比較 どうやって閾値を設定するかがunknown。 構造劣化の本質をうまくエントロピーで表せたらいけるのかも。

17 Heuristic Reorganization of Clustered Files
[ hoshino] 再編成論文サーベイ2 Heuristic Reorganization of Clustered Files Pater Scheuermann, Young Chul Park (Northwestern University), Edward Omiecinski (Georgia Institute of Technology) Foundations of Data Organization and Algorithms 1989

18 概要 レコードとページの最適マッピングを見つけるのはNP-Hard?なので、heuristicsを用いた再編成アルゴリズムを提案
[ hoshino] 再編成論文サーベイ2 概要 レコードとページの最適マッピングを見つけるのはNP-Hard?なので、heuristicsを用いた再編成アルゴリズムを提案 再編成タイミングについての記述は(おそらく)なし

19 [ hoshino] 再編成論文サーベイ2 Performance Analysis of A Periodic Data Reorganization Algorithm for Concurrent Blink-Trees in Database Systems Ing-Ray Chen (National Cheng Kung University), Salah Hassan (Mtel Technologies) ACM Symposium on Applied Computing 1995

20 概要 Blink-treeに特化した、analytic modelによる最適再編成タイミングの導出 我々との比較
[ hoshino] 再編成論文サーベイ2 概要 Blink-treeに特化した、analytic modelによる最適再編成タイミングの導出 Insertとdeleteのrateは一緒、updateとreadのrateも一緒(サイズは変わらない) ワークロードは固定、一様分布 再編成といっているのは、delete flagの立ったレコードを回収する操作、garbage collection。 Degradation level dを定義しているが、性能との関係は間接的。 我々との比較 論理構造における構造劣化が対象 アクセスパタンが非現実的であり、この振る舞いからはずれるとどうなるか分からない 直接性能低下を表現するための構造劣化メトリクスがない

21 [ hoshino] 再編成論文サーベイ2 On the Cost of Monitoring and Reorganization of Object Bases for Clustering Carsten A. Gerlhof, Alfons Kemper (Lehrstuhl fur Informatik), Guido Moerkotte (University Mannheim) SIGMOD Record 1996

22 概要 ODBMSにおいて、クラスタリングによる再編成手法を提案し、モニタリングのコストを評価 我々との比較 モニタリング
[ hoshino] 再編成論文サーベイ2 概要 ODBMSにおいて、クラスタリングによる再編成手法を提案し、モニタリングのコストを評価 モニタリング Reference counts, link counts オーバーヘッドは34%以上 クラスタリング手法の評価 評価軸に、# of repetitions を利用 我々との比較 シーケンスのことは意識していない 再編成タイミングについての議論はない

23 [ hoshino] 再編成論文サーベイ2 Probabilistic Model and Optimal Reorganization of B+-Tree with Physical Clustering June S. Park (University of Iowa) and V. Sridhar (Ohio University) TKDE 9(5), 1997

24 概要 VSAM KSDSの再編成タイミングを決定する方式を提案 我々との比較
[ hoshino] 再編成論文サーベイ2 概要 VSAM KSDSの再編成タイミングを決定する方式を提案 構造変化は Budket split と region split があるが、region splitが起きる前に再編成すべきとの結論 Region splitが起きる時間の推定手法を構築 我々との比較 データ構造specificな手法 再編成タイミングの決定ポリシは、経験則によるもの

25 [ hoshino] 再編成論文サーベイ2 Improving I/O Response Times Via Prefetching and Storage System Reorganization C. L. Chee, H. Lu, and H. Tang (National University of Singapore), C. V. Ramamoorthy (University of California, Berkeley) COMPSAC 1997

26 概要 再編成とプリフェッチでストレージ性能を上げる方式を提案 我々との比較 Statistics collector
[ hoshino] 再編成論文サーベイ2 概要 再編成とプリフェッチでストレージ性能を上げる方式を提案 Statistics collector 次に参照されやすいブロック 次の次に参照されやすいブロック リード回数 ライト回数 我々との比較 統計情報収集と再編成は定期的に行われる スケジュールについての議論はない

27 [ hoshino] 再編成論文サーベイ2 Performance and Stability Analysis of Multilevel Data Structures with Deferred Reorganization I.-R. Chen (Virginia Polytechnic Institute and State University), S. A. Banawan (University of Qatar) IEEE Transactions on Software Engineering 25(3), 1999

28 概要 最適な再編成タイミングの導出手法を提案
[ hoshino] 再編成論文サーベイ2 概要 最適な再編成タイミングの導出手法を提案 Performance Analysis of A Periodic Data Reorganization Algorithm for Concurrent Blink-Trees in Database Systems(1995)と基本的な考え方は同じ 以前のマルコフモデルを拡張 対象データ構造: two-level sorted array

29 Dynamic Reorganization of Object Databases
[ hoshino] 再編成論文サーベイ2 Dynamic Reorganization of Object Databases Vlad S. Wietrzyk, Mehmet A. Orgun (Macquarie University) IDEAS 1999

30 概要 ODBMSにおいて、インクリメンタル再編成手法を提案 再編成タイミングの話はとくになし クラスタリングの話
[ hoshino] 再編成論文サーベイ2 概要 ODBMSにおいて、インクリメンタル再編成手法を提案 クラスタリングの話 再編成タイミングの話はとくになし

31 Research issues in automatic database clustering
[ hoshino] 再編成論文サーベイ2 Research issues in automatic database clustering Sylvain Guinepain, Le Gruenwald (The University of Oklahoma) Sigmod Record 2005

32 概要 データベースクラスタリング技術の問題点を整理
[ hoshino] 再編成論文サーベイ2 概要 データベースクラスタリング技術の問題点を整理 What to cluster?, how to cluster?, static or dynamic?, when to trigger the process?, what statistics to collect?, how to detect bad clustering?, how to re-cluster? 参考文献を分類しながら、まだ解決されていない課題を提示 IOコストを減らすための技術:indexing, buffering, clustering, parallelismの中でのclusteringという位置付け 著者らの手法AutoClust[Pasquier1999, Durand2002]のメリットも主張 Record clustering と attribute clustering両方を考慮 クエリログを使って分析するためオンライン性能に影響しない 分析手法はグラフ理論を用いたクラスタリング ポリシベースのautomatic re-clustering (query response time) 我々との違い データベース構造における論理的なデータ配置論 ディスクの物理特性までは言及していない 最も低レベルの指標はIO数 アクセスの統計情報から分析 Transaction内での相関性、ページアクセス数、etc.

33 An On-Line Reorganization Framework for SAN File Systems
[ hoshino] 再編成論文サーベイ2 An On-Line Reorganization Framework for SAN File Systems Shahram Ghandeharizadeh, Shan Gao (University of Southern California), Chris Gahagan, Russ Krauss (BMC Software Inc.) ADBIS 2006

34 概要 SANスイッチのところで、フラグメント単位のマイグレーションをコスト対効果を考えて行う手法を提案 我々との比較
[ hoshino] 再編成論文サーベイ2 概要 SANスイッチのところで、フラグメント単位のマイグレーションをコスト対効果を考えて行う手法を提案 MonitorPredictMigrateのステップをタイムスライス毎に実行 Monitorにおいては、request size, heart, loadなどをフラグメント毎に、ディスク毎に記録 コスト: フラグメントを移動するための時間 効果: 前タイムスライスにおいて、測定されたフラグメントの応答時間と、仮に移動先(候補)に配置されて場合の推定値の差 相関の高いフラグメントは別ディスクに配置 我々との比較 Monitorだけでなく全部やっている アクセス頻度が高いものと速いディスクに移動するという思想

35 Tuning File System Block Addressing for Performance
[ hoshino] 再編成論文サーベイ2 Tuning File System Block Addressing for Performance Harrison Caudill, Ada Gavrilovska (Georgia Tech) ACM SE2006

36 概要 LFSを、断片化が少なくなるような構造にする方式を提案 Flash memoryを用いて、Ext2と比較 我々との比較
[ hoshino] 再編成論文サーベイ2 概要 LFSを、断片化が少なくなるような構造にする方式を提案 ファイルへのinternal pointerを連続ページ内に配置 Extentサイズをファイルサイズに応じて増大(buddy system) Flash memoryを用いて、Ext2と比較 テスト: シーケンシャルアクセス、カーネルコンパイル 128MB空間でのテスト 小さすぎる サイズ大のファイルには効くが、サイズ小のサイズには効果がない 我々との比較 再編成の話ではなく、断片化しにくいデータ構造を用いるアプローチ

37 [ hoshino] 再編成論文サーベイ2

38 我々の Novelty と Effectiveness
[ hoshino] 再編成論文サーベイ2 我々の Novelty と Effectiveness 従来の構造劣化同定 & 再編成スケジュール 情報取得 アクセスパタン: アクセス頻度 Analytical modelの場合は、一様分布のアクセス 構造劣化の評価 間接的 (cost) 再編成タイミング 定期的に行うことを前提 我々 論理シーケンシャルアクセスを捉える オンラインで、低オーバーヘッド 細粒度、直接的(response time) 人間まかせだが、可視化

39 主張ポイント 論理シーケンシャルアクセスに注目 オンライン、低オーバーヘッドで細粒度の監視 ストレージ性能特性を考慮した構造劣化モデル
[ hoshino] 再編成論文サーベイ2 主張ポイント 論理シーケンシャルアクセスに注目 ディスクを用いたストレージで構造劣化の影響が甚大 オンライン、低オーバーヘッドで細粒度の監視 これまでと比べ、オーバーヘッド vs 情報取得量が高い(?) ストレージ性能特性を考慮した構造劣化モデル 従来はせいぜいIO数、シーケンシャル＆ランダムアクセスコストまで