平成９年度　委託研究ソフトウェアの提案

(21) 並列アクティブデータベースにおけるI/O処理の高速化

研究代表者：	横田　治夫　助教授
	北陸先端科学技術大学院大学　情報科学研究科
	（現・東京工業大学大学院情報理工学研究科助教授）

［目次］

研究の背景
研究の目的
研究内容
研究体制／研究方法
想定されるソフトウェア成果

［研究の背景］

　現在、データベースの分野で、データベースの状態により、予め定められたルールに従って、データベース管理システムが能動的にデータベース処理を行なうアクティブデータベースシステムが注目を集めている。アクティブルールを利用することにより、自由度の高い高度な処理の実現が可能となることが、その大きな要因であると思われる。
　具体的には、従来からのデータベースのトリガー／アラータ機能に加え、完全性制約や参照制約などをデータベース内で自動的に保つ機構を持たすことができる。また、データの自動解析、データマイニング、マルチデータベース間のメディエータとして状態管理をするエージェントの実現、モーバイルデータベースにおける移動ホストの環境変化への適応などが研究されており、推論機能を使った大規模知識ベースの実現など知識処理分野への展開も期待される。このように、アクティブデータベースの利用範囲は非常に広いと言える。
　しかし、アクティブルール処理自体が重い処理であるため、実際に利用されるためには、並列処理による高速化が望まれている。ルール実行の並列化、ルールの条件照合の並列化、ルールの最適化処理の並列化などに加え、ベースとなる関係データベース自体の並列化も重要である。
　これまで我々は、アクティブデータベース処理を統合的に並列化することを目指して Parade と名付けたアクティブデータベースエンジンを KLIC を用いて実現してきた。昨年度までに、サーバが並列マシン上で動作するクライアント／サーバタイプの実験システムを試作してきた。これにより、KLIC の並列プログラムの記述能力や移植性を実証してきた。
　しかしながら、データベースとしての実用的な処理速度という面で、特に大きなデータをアクセスする際に、I/Oがボトルネックとなることが分かってきた。速度向上を目指して並列化しているため、実質的に処理速度を支配している I/O を高速化することが、何より重要である。これは、今後 I/O を含む処理に対する KLIC の潜在能力を示し、更に広く多くの分野に KLIC の機能をアピールすることにつながると確信する。

［研究の目的］

　我々が研究している KLIC による並列アクティブデータベースシステムのプロトタイプを、実用的な処理速度で動作させるため、KLIC のジェネリックオブジェクトを用いた低レベルの I/O 性能の向上と、並列ディスクアレー向けに B-Tree の改良を施すことにより、達成することを目指す。これは、KLIC の拡張性や記述能力の高さを実証するとともに、その応用の広さを示し、第五世代技術の普及と発展に貢献することにつながる。
　第五世代プロジェクトでの成果を、経営判断の意志決定支援等の応用分野において広く利用されるためには、実用的な処理速度を持つ、並列アクティブデータベースシステムを用意することが重要である。 KLICの論理変数によるプロセス間のメッセージ通信は、無共有並列計算機上でデータベース処理を実現する際に非常に適合性がよい。
　昨年までの委託研究では、アクティブデータベース処理をKLICのプロセス間のメッセージ通信を利用することにより実現し、汎用ワークステーションならびに超並列計算機nCUBE上で動作させ、その記述能力と移植性の高さを実証してきた。この研究を通して、データベース処理では非常に大きな鍵を握るI/O処理が、システムの性能の向上に大きく影を落していることが分かってきた。これは、KLIC標準のI/O が、性能を重視して設計されたものではないことと、一般のB-Treeが並列ディスクアレーに対応しておらず、データへのアクセスの際に木のルートノード付近にトラフィックが集中することに起因する。本研究では、KLICのジェネリックオブジェクトを用いて、ページ単位で I/Oを直接アクセスし、低レベルI/Oの高速化を目指すとともに、 B-Treeを並列ディスクアレー向けに改良したFat B-Treeにより、データへのアクセス速度の改善を、ワークステーションクラスタや超並列計算機nCUBE上での実験を通して明らかにする。特に、ジェネリックオブジェクトを利用した低レベルのI/O性能の向上は、アクティブデータベースの実用的な処理速度を目指す目的だけでなく、KLICの言語処理系レベルの拡張性をアピールすることにもつながる。

［研究内容］

　昨年度までの委託研究により開発した、並列アクティブデータベースParadeをベースに、1) ジェネリックオブジェクトによる低レベル I/O性能の改善、2) 並列ディスクアレー向きFat B-Treeによるデータアクセスの高速化、に分けてその内容の詳細を以下に示す。

1) ジェネリックオブジェクトによる低レベルI/Oの高速化: KLIC標準のI/Oは、外部表現と内部表現を交換するために parse/unparse機構を必要とし、かつそのデータアクセスの単位は小さい。そのため、極めてソフトウェアオーバヘッドの大きいものとなっており、かつディスクI/Oの面から見ても、スループットを高くすることを困難なものとしている。
　しかしながら、一般的にデータベース処理では、ディスクI/Oが全体のボトルネックとなることが多く、このボトルネックを解決することが、データベース全体の処理速度の向上に大きく貢献する。通常のデータベースでは、ディスクをページ単位といった大きなデータ単位でアクセスしてディスクI/Oのスループットを高くすることが行なわれている。これをKLICで行なうためには、KLICのデータ型を拡張するためのジェネリックオブジェクトを用いるのが、最も簡単にかつ性能を上げることを可能にすると考えられる。なおかつ、ジェネリックオブジェクトの導入により、プログラムの移植性を損なわないという利点も見逃せない。具体的には、新しいデータ型としてページオブジェクトをジェネリックオブジェクトにより定義し、ページ単位でディスクアクセスを行なえるようにし、ディスクI/Oのスループットの向上を図る。このページオブジェクトによるページ単位のディスクアクセスは、B-Treeなどのアクセスパス構造との親和性の向上にも貢献する。また、このページオブジェクトに適切なメソッドを定義し、KLIC の基本データ構造に変換することなく直接データを扱えるようにする。これにより、parse/unparseというソフトウェアのオーバヘッドを大きく削減できる。
　このページオブジェクトの導入は、無共有並列計算機におけるKLIC のプロセス間のメッセージ通信のオーバヘッドの削減にも有効である。なぜならば、一般的に無共有並列計算機は、メッセージのセットアップコストがメッセージバッファの獲得やロックのため、通信のスループットに比較してかなり大きいが、一方で分散版KLICはプロセッサ間通信の際に、通常1レベルずつの細かなメッセージが転送される。このため、言語処理系レベルでの通信オーバヘッドが大きくなってしまうからである。分散版KLICでは、マルチレベルでのメッセージ通信もサポートしているが、これは、メッセージのencode/decodeというソフトウェアのオーバヘッドを伴う。しかしながら、前述のページオブジェクトを用いれば、大きなデータ単位でメッセージを送受信することが可能となり、メッセージのセットアップコストを相対的に小さくでき、データのencode/decodeといったソフトウェアのオーバヘッドも削減することができる。これによりトータルなメッセージハンドリングオーバヘッドを大きく改善することが期待できる。特に、専用計算機に比較して、メッセージハンドリングオーバヘッドが大きいワークステーションクラスタでは、この改善は大きな意味をなす。
　このページオブジェクトを実現し、具体的なI/O性能やメッセージハンドリングオーバヘッドを、nCUBEやワークステーションクラスタ上で比較し、評価を行なう。
2) 並列ディスクアレー向きFat B-Treeによるデータアクセスの高速化: 　並列ディスクアレー上へのデータ配置の有効な手法として、ハッシュ分割と値域分割がある。ハッシュ分割は適切なハッシュ関数によりデータの分配の偏りを小さくすることができるが、値域指定の検索やデータのクラスタ化には対応できない。値域分割はこれらに対応できるが、静的な基準によりデータを分配するためデータ配置の偏りが生じる。
　一方、効率の良いデータのアクセスパス構造の1つとして、B-Tree が挙げられる。B-Treeは、範囲指定の検索やデータのクラスタ化に強いが、データの分割が困難である。また、その構造が木状であるため、データへのアクセス頻度が高い場合、木の根付近のノードでトラフィックが集中し、ボトルネックとなる。
　本研究では、B-Treeの問題点を解決するFat B-Treeを提案する。
Fat B-Treeは値域分割されたページのディレクトリ構造としてB-Tree を利用し、各ディスクには均等に分配されたB-Treeの葉ページの一部と、そこから根までのパス構造を持つ部分木を格納する。このため Fat B-Treeでは、多くの葉ページまでのパスに共有される木の根付近のノードは、複数のコピーが存在することになり、根ノードは全てのディスクにコピーされる。しかしながら、木の根付近のノードの更新頻度は葉ページに比較して少ないため、ディレクトリを全てのディスクにコピーする方式に比較して、更新時の処理は軽くなることが期待できる。さらに、根から各葉ページへのアクセスパス構造は全てのディスクに存在するため、木の根付近のノードのアクセスの衝突を減少させることができる。また、Fat B-Treeの各ページは、前述したページオブジェクト型を利用することにより、ディスクI/Oのオーバヘッドを削減でき、データアクセスの高速化に貢献する。
　この提案するFat B-Treeを、並列ディスクアレーをもつnCUBEに実現することにより、データのアクセスに対するレスポンスタイムやスループットを測定することにより、通常のB-Treeに対する利点を示す。

　以上で述べた2つの項目を、現状の並列アクティブデータベース Paradeに統合して、システムの性能の向上を目指す。

［研究体制／研究方法］

(1) 研究体制

	氏　名	所　属
研究代表者	横田　治夫	北陸先端大　助教授
研究協力者	宮崎　純	北陸先端大　助手
研究協力者	金政　泰彦	北陸先端大　修士課程２年

(2) 研究の方法

　ジェネリックオブジェクトを用いた低レベルI/Oの高速化には、宮崎が担当し、Fat B-Treeの実現には金政が担当する。それぞれの作業は並行して行ない、最終的な機能の統合および取りまとめは横田が担当する。

［想定されるソフトウェア成果］

(1)作成されるソフトウェア名称

KLICによる並列アクティブデータベース

(2)そのソフトウェアの機能／役割／特徴

　以下に、並列アクティブデータベースサーバとクライアントに分けて記述する。

: 1) 並列アクティブデータベースサーバ; 　クライアントからの関係代数レベルのコマンドを受け付け、主に nCUBE上において並列データベース処理を行なう。全てがKLICで記述されているため、ディスクドライブ名など機種や計算機環境依存部分のテーブルを書き換えるのみで、他の機種で動作させることができる。すなわち、LANに接続されたワークステーション上でもデータベースサーバとして利用することができる。並列マシンの上で動作させる場合、KLICにより関係データベース演算やデッドロック検出の並列アルゴリズムを記述してあるため、並列性を活かした高速実行が可能である。特に、処理コストの大きな結合演算は高い速度向上が望める。さらに、ジェネリックオブジェクトを用いた低レベルI/Oの高速化のほか、並列ディスクアレー向けのFat B-Treeにより、高速なデータアクセスが可能である。
　機能的には、アクティブルールをサポートしているため、一貫性制約などをルールで記述することにより、データベース処理の高機能化を図ることが可能である。アクティブデータベースの応用範囲は、演繹データベースと比較するとかなり広く、データの一貫性を強く維持しなければならないようなビジネス分野での利用が望める。さらに、複雑なルールの実行であっても、ネステッドトランザクションにより並列性を活かした高速実行が可能である。
　当然、サーバとして同時に複数のクライアントからの要求に対応する必要があり、二相ロックによる並行性の制御により、クライアント間のシリアライザビリティは保たれる。
　なお、クライアントは、関係代数コマンドを発行できるものであれば何でもよい。例えば演繹データベース用のクライアントを実現すれば、アクティブデータベースと演繹データベースとを組み合わせたシステムの実験等も可能となる。このように、並列マシンで動作させた場合の効果が大きく、拡張性も高いシステムである。; 2) クライアント; 　SQL、OQL、QBEライクな3種類のクライアントを用意する。SQLクライアントは、関係データベースの標準的なデータ操作記述言語(DML) である SQLをインタラクティブに受け付け、関係代数レベルのコマンドに変換する。OQLクライアントは、OODBのようなDMLをインタラクティブに受け付け、関係代数レベルのコマンドに変換する。QBEクライアントはJAVAで記述されており、GUIを利用したインタフェースとなっており、最終的には関係代数レベルのコマンドに変換する。LAN 環境下のワークステーション上で動作することを前提に、変換した関係代数コマンドを、Unixのソケットインタフェースを介して、前述した並列アクティブデータベースサーバに渡す。さらに、各クライアントは、サーバーから送られてくる実行結果の表示を行なう。
　特に、SQLクライアントにおけるSQL自身は、JISやISO等で規格化されており、それに準拠する形になっているため、ビジネス分野等の広い分野での利用性が高い。また、SQL、OQLクライアントは、全てが KLICで記述されているため機能拡張性に富み、言語仕様を拡張することも容易である。当然ながら、ソケットをサポートする機種ならば、 KLICがインストールされていれば機種に依存することなく、変更なしに動作させることができ、ポータビリティは非常に高い。
　QBEクライアントはJAVAで記述されており、それ自身のポータビリティは非常に高く、ワークステーションに限らずソケットをサポートするパソコンなど、多くの機種で動作させることが可能である。また、GUIを用いてインタラクティブにデータの操作を行なえるため、初心者でも違和感なく操作できる。

(3)ソフトウェアの構成／構造

1) 並列アクティブデータベースサーバ

　サーバは、トランザクションマネージャ、ロックマネージャ、デッドロックマネージャ、コマンド実行マネージャ、ログマネージャ、ディスクアクセスマネージャ、ルールマネージャ、およびクライアントと対話するためのソケットインタフェースから構成される。
　トランザクションマネージャは、クライアントに対応してトランザクションIDを管理しながら、他のマネジャとのメッセージ通信を行い、ネステッドトランザクションの管理も行なう。ロックマネージャは、アクセスするデータに対する適切なロックを獲得し、これを管理する。デッドロックマネージャは、Wait-For Graphを利用して、トランザクション間のデッドロックを検出する。コマンド実行マネージャは関係代数レベルのコマンドの実行を行なう。ディスクアクセスマネージャは、並列ディスクアレー内に格納されたデータのアクセス、およびその維持を行なう。ログマネージャは実行ログの管理を行なう。ルールマネージャは、アクティブルールの管理を行なうとともに、ルールで指定されたデータベースイベントに反応して、適切なルールをトランザクションマネージャを介して実行する。
　以上は、昨年度までの委託研究により実現されている構成である。
今年度は、I/O周り、すなわちディスクアクセスマネージャの強化を行なう。新たにジェネリックオブジェクトを利用することにより、ページ単位で低オーバヘッドでディスクアクセスできるように改良を行なうとともに、並列計算機上でのメッセージ通信のオーバヘッドの削減も、同時に実現する。さらに、Fat B-Treeと名付ける並列ディスクアレー向けの、アクセス衝突の少ない、かつデータのクラスタ化が可能なアクセスパス構造を実現し、データのアクセスの高速化、維持の効率化を行なえるようにする。

2) クライアント

　SQL、OQL、QBEの3種類のクライアントとも、パーザおよび関係代数レベルコマンドジェネレータとソケットインタフェースから構成される。
　SQL、OQLクライアントは、ともに全てKLICで記述されており、インタラクティブに入力されたデータ操作言語の解釈、関係代数コマンドへの変換、およびソケットインタフェースを介してサーバとの対話を行なう。
　QBEクライアントは、JAVAで記述されており、GUIを通してインタラクティブに入力されたデータ操作言語の解釈、関係代数への変換、ソケットインタフェースを介してのサーバとの対話を行なう。
　ソケットインタフェースによるサーバとの対話は、基本的にキャラクタベースで行なわれる。

(4)参考とされたICOTフリーソフトウェアとの関連

KLIC(一部JAVA)で記述した内容を、全てIFSとして公開する。

(5)使用予定言語および動作環境／必要とされるソフトウェア・パッケージ／ポータビリティなど

: 使用予定言語：KLICおよびJAVA(オプショナル); 動作環境: Unixワークステーション及びnCUBEを始めとする並列マシン; ポータビリティ：並列ディスクアクセスなどの機種依存の部分を除けば、非常にポータビリティは高い。特に、クライアントについては、ソケットさえサポートしていれば特に機種を限定しない。
(6)ソフトウェアの予想サイズ（新規作成分の行数）: 2000行程度
(7)ソフトウェアの利用形態: 　これまで、汎用並列マシン上の関係データベース処理系としては、 Oracle 7等市販のものは存在しているが、フリーでポータビリティの高い、なおかつ簡単に実験に利用できるものはなかった。そのため、本システムのように移植が簡単で、機能的な拡張も容易である並列アクティブデータベースがフリーソフトとして公開されれば、かなり広範囲で利用されると考える。
　特に、QBEクライアントを除く全てがKLICで記述されているため、研究者や技術者が自ら拡張することも容易であり、これからの並列データベース関係の研究用、実験用のツールとして、利用してもらえることを望んでいる。また、クライアントとサーバ間で規定している関係代数レベルのコマンドは、クライアントを構成する上でも、各種の実験を試みることが可能な枠組みとなっており、単なるSQL、OQL、 QBEのインタフェースだけでなく、いろいろなシステムに組み込んで、利用して貰えるものと考えている。
　さらに、研究分野のみでなく、ビジネスなど広範囲の分野での利用も可能であると思われる。無論、完成度として不十分な部分があることは承知して頂かなければならないが、銀行のオンライン等シビアな環境でなく、企業内データのデータベース化等には、性能的に耐えるレベルにしたいと考えている。特にクライアントは、これまでビジネスでデータベースを利用してきた人々にとって、非常に馴染みやすいインタフェースとなるよう設計されており、逐次処理の実行時間に不満があるような場合には、積極的に利用してもらえるのではないかと考えている。また、本システムをベースとして、より完成度の高いシステムの開発を目指すところが出現してくれれば、より広範囲での利用が望めると思われる。
　アクティブルールの枠組みは、今後いろいろな発展が望めるが、さしあたって、一貫性保持や動的な動向調査(OLAP)等は、研究分野でもビジネス分野でも、実験的に利用されていくものと考えている。
(8)添付予定資料

ソースプログラム
内部仕様書
利用手引書

www-admin@icot.or.jp