研究の内容

昨年度までの委託研究により開発した、並列アクティブデータベースParadeをベース に、1) ジェネリックオブジェクトを用いたページ単位I/Oの実現による高速化、 2) 更新に対しても効率のよい並列ディレクトリ構成によるデータアクセスの高速化、 に分けてその内容を以下に示す。

1. ジェネリックオブジェクトを用いた低レベルI/Oの高速化
   KLIC標準のI/Oは、外部表現と内部表現を交換するためにparse/unparse機構を必要 とし、かつそのデータアクセスの単位は小さい。そのため、極めてソフトウェア オーバヘッドの大きいものとなっており、かつディスクI/Oの面から見ても、ス ループットを高くすることを困難なものとしている。

   しかしながら、一般的にデータベース処理では、ディスクI/Oが全体のボトルネッ クとなることが多く、このボトルネックを解決することが、データベース全体の処 理速度の向上に大きく貢献する。通常のデータベースでは、ディスクをページ単位 といった大きなデータ単位でアクセスしてディスクI/Oのスループットを高くする ことが行なわれている。これをKLICで行なうためには、KLICのデータ型を拡張する ためのジェネリックオブジェクトを用いるのが、最も簡単にかつ性能を上げること を可能にすると考えられる。なおかつ、ジェネリックオブジェクトの導入により、 プログラムの移植性を損なわないという利点も見逃せない。具体的には、新しい データ型としてページオブジェクトをジェネリックオブジェクトにより定義し、 ページ単位でディスクアクセスを行なえるようにし、ディスクI/Oのスループット の向上を図る(図1)。このページオブジェクトによるページ単位の ディスクアクセスは、B-treeなどのアクセスパス構造との親和性の向上にも貢献す る。また、このページオブジェクトに適切なメソッドを定義し、KLICの基本データ 構造に変換することなく直接データを扱えるようにする。これにより、 parse/unparseというソフトウェアのオーバヘッドを大きく削減できる。

   このページオブジェクトの導入は、無共有並列計算機におけるKLICのプロセス間の メッセージ通信のオーバヘッドの削減にも有効である。なぜならば、一般的に無共 有並列計算機は、メッセージのセットアップコストがメッセージバッファの獲得や ロックのため、通信のスループットに比較してかなり大きいが、一方で分散版KLIC はプロセッサ間通信の際に、通常1レベルずつの細かなメッセージが転送される。 このため、言語処理系レベルでの通信オーバヘッドが大きくなってしまうからであ る。分散版KLICでは、マルチレベルでのメッセージ通信もサポートしているが、こ れは、メッセージのencode/decodeというソフトウェアのオーバヘッドを伴う。し かしながら、前述のページオブジェクトを用いれば、大きなデータ単位でメッセー ジを送受信することが可能となり、メッセージのセットアップコストを相対的に小 さくでき、データのencode/decodeといったソフトウェアのオーバヘッドも削減す ることができる。これによりトータルなメッセージハンドリングオーバヘッドを大 きく改善することが期待できる。特に、専用計算機に比較してメッセージハンドリ ングオーバヘッドが大きいワークステーションクラスタでは、この改善は大きな意 味をなす[1]。

    

   
   図 1: ページオブジェクトによる I/O
    

   
   図 2: Fat-Btree 構造
   

2. 更新に対しても効率のよい並列ディレクトリ構成による高速化
   無共有並列データベースシステムの水平データ分割の有効な手法として、ハッシュ 分割と値域分割がある。ハッシュ分割は適切なハッシュ関数によりデータの分配の 偏りを小さくすることができるが、値域指定の検索やデータのクラスタ化には対応 できない。値域分割はこれらに対応できるが、静的な基準によりデータを分配する ためデータ配置の偏りが生じる。

   一方、効率の良いデータのアクセスパス構造の一つとして、B-tree構造が挙 げられ、B-tree のノード単位で値域分割の弱点であるデータ配置の偏りに 対処する並列B-treeが提案されている。しかし、これまでに提案された並列 B-treeは、更新時にディレクトリ構造の変更の同期がプロセッサ間で大きな オーバーヘッドとなってしまうという問題点を持っていた。

   この並列B-treeの問題点を解決するために、更新も考慮した並列データベース向け のディレクトリ構造である Fat-Btreeを提案している[2]。 Fat-Btreeは、並列計算機の内部ネットワーク構造の一つとして知られるFat-Tree と同様に、木の根の部分を太くした構造を持ち、太い部分はノードのコピーを持た せている。

   Fat-Btreeは値域分割されたページのディレクトリ構造として従来のB-treeを利用 し、各ディスクには均等に分配されたB-treeの葉ページと、そこから根までのパス を持つ部分木を格納する。このためFat-Btreeでは、多くの葉ページまでのパスに 共有される木の根付近のノードは、複数のコピーが存在することになり、根ノード は全てのディスクにコピーされる(図2)。しかしながら、木の 根付近のノードの更新頻度は葉ページに比較して少ないため、ディレクトリを全て のディスクにコピーする方式に比較して、更新時の処理は軽くなることが期待でき る。さらに、根から各葉ページへのアクセスパスは全てのディスクに存在するた め、葉まで木をたどる時の木の根付近のノードのアクセスの衝突を減少させること ができる。また、Fat-Btreeの各ページは、前述したページオブジェクト型を利用 することにより、ディスクI/Oのオーバヘッドを削減でき、データアクセスの高速 化につながる。