オブジェクト指向データベースのアプリケーション形態の一つはLWSというモデルで特徴付けられる。LWSモデルに従うアプリケーションは、プログラム起動時に一定量のデータを二次記憶より読み込み(Load phase)、次に読み込み済みのデータを繰り返し参照しながら、計算あるいは更新を実行し(Work phase)、最後に計算・更新の結果を二次記憶に書き出す(Save phase)という動作をする。Work phaseでのデータ参照は繰り返し実施され、その実行時間が全実行時間の大半を占めることが多い。

　しかしながら、これまでに実装された研究用あるいは商用のオブジェクトデータベースシステムのほとんどは、永続性を付加するための機構を導入した結果生じる、Work phaseにおけるオーバヘッドを甘受している。これを鑑み、著者はWork phaseでの最適化を目的とした実装方式を提案した。一方、1991年に本研究とは独立に同じ目的を達成するために、ハードウェアに基づく方式がテキサス大学のWilsonらによって提案された。Object Design社が開発・販売する商用オブジェクト指向データベースObjectStoreにも同様の機構が採用されている。また1994年にはウィスコンシン大学のWhiteらによって同様の方式を用いた実装の性能が報告されている。本論文で提案する方式と、これらのハードウェアを用いた方式を比較した場合、いずれもWork phaseの実行の最適化を指向するものの、その基本的な戦略の違いにより異なる特性を示す。本論文は両方式の得失を明らかにするものである。

　一般に、オブジェクト指向データベースにおいてオブジェクト間の参照のために用いられる識別子には、プロセッサが直接扱えるアドレスのビット長よりも長いものが用いられる。これは、現在主流になっているプロセッサの4Gバイトという仮想アドレス空間が、データベース構築のためには十分な規模でないためである。データベースに格納されるオブジェクトには、そのような長い識別子を通して参照される大規模な空間中のアドレスが割り振られる。この空間は永続アドレス空間と呼ばれる。永続アドレス空間内のアドレスを割り付けられたオブジェクトは、二次記憶上に格納され、個々のオブジェクトは内部に埋め込まれた識別子(永続識別子)により互いに関連付けられる。

　多くの処理系では、オブジェクトが二次記憶から仮想記憶に転送される際にも、オブジェクト内に埋め込まれた永続識別子には全く変更が加えられない。永続識別子を含む参照は、仮想アドレスを保持する通常のポインタよりもより多くの記憶領域を必要とするし、一般には永続識別子を用いて直接オブジェクトをアクセスすることはできないので、

　・同一のオブジェクトを参照する識別子が多数存在する場合に、参照によって占められる物理記憶の量が増加する。

　・参照のコピーのために必要となる機械命令数が増加する。

　・参照の対象となるオブジェクトをアクセスするためには、永続参照が含む識別子を、対象アドレスに対して与えられた仮想アドレスに変換する必要があるため、この変換のための機械命令列を繰り返し実行する必要がある。

　といった、Work phaseにおける実行性能低下の原因が生じる。グラスゴー大学を中心に行なわれたPS-Algolの実装では、第三のオーバヘッドを抑えることを目的に、現在「ポインタ書き換え(Pointer Swizzling)」と呼ばれる実現技術が考案された。文献に述べられているPS-Algolの実装では永続識別子と通常のポインタのサイズが同一であったため、その他の問題点については触れられていない。

　ポインタ書き換えとは、「永続識別子を繰り返し仮想アドレスに変換することを避けるために、変換対象となった永続識別子を含む参照を、仮想アドレスで書き換えることである」¹。ポインタ書き換えの導入によって、永続識別子の変換回数は大幅に減少するものの、書き換え済みの参照を解決する前には、参照が書き換え済みであるか否かの検査(予約検査)が繰り返し必要となる。

　前述のハードウェアに基づく方式は、フォールト時書き換えと呼ばれる。この方式では、オブジェクトが物理記憶にコピーされる段階で、オブジェクト内の参照を仮想アドレスで書き換える。ただし、書き換えた参照のターゲットの読み込みは行なわず、必要になるまで読み込みを遅延させる。そのため参照のターゲットをアクセスする際には、ターゲットが読み込み済みであるか否かを検査する必要がある。この検査(存在検査〉はメモリ管理ユニットの機能を利用して実行される。つまりポインタを書き換えた時に、ターゲットに割り付けた仮想アドレス空間をアクセス保護するようオペレーティングシステムに要求が出される。その結果、保護された領域へのアクセスが生じた際には、メモリ管理ユニットから例外が生成されるので、これを捕捉して例外ハンドラ内でオブジェクトの内容を読み込む。このような機構の採用により、予約検査と存在検査のいずれのための機械命令列も必要とされない。フォールト時書き換えの概念図を図1に示す。

　一方、提案方式(発見時書き換え)ではポインタがヒープ領域から読み出された段階で予約検査が実行される。その結果、プログラムよるコピーや参照解決の対象となるポインタには必ず有効な仮想アドレスが含まれることが保証される。一般に、ヒープ領域からの読み出しはポインタを使用した参照に比べ頻度が低いので、PS-Algolで用いられた方式(参照時書き換え)よりも予約検査の回数を減ずることができる。予約検査のための機械命令列をコンパイラによって自動的に生成すれば、利用者は永続オブジェクトへのポインタを通常のポインタと全く同様に扱える。予約検査によって、書き換え済みでない参照が発見されると、ランタイムライブラリ(RTL)が呼び出される。RTLはターゲットに対して仮想アドレスを割り当て、発見された参照をその仮想アドレスで書き換える。このときオブジェクトの読み込みも行なわれる。

　¹必ずしも仮想アドレスである必要はなく、永続空間とは独立の、プロセス固有のアドレスであればよい。

　発見時まで書き換えが遅延されることは、読み込み時にはオブジェクト内の参照を仮想アドレスに変更できない場合があることを意味する。そこで、通常のポインタと同一サイズの領域に永続識別子をエンコードするために、代理OIDと名付けた機構を導入している。すなわち、仮想アドレスの割り当てが済んでいないオブジェクトへの参照は、通常使用可能ではない特殊な仮想アドレス値(lambda)で書き換えられる。それだけでは、書き換えられた参照がもともと含んでいた永続識別子の値が失われてしまうので、書き換えを行なった参照が置かれたアドレスと永続識別子の対応表が管理される。Lambdaが発見された際には、それが置かれたアドレスを鍵としてテーブルを検索することで、対応する永続識別子の値を知ることができる。図2中にAddr2Oid Tableとして示されているのがこのテーブルである。この図は、オブジェクトRとBが読み込み済みである時にポインタP2内のlambdaが発見され、その結果としてオブジェクトAが読み込まれる際の処理を図示したものである。このようにして、フォール時に参照のサイズを縮めることで前述の第2のオーバヘッドが避けられている²。

図表Figure 1:Persistent pages reserved in virtual memory (by Singhal et al.) / Figure 2:Pointer swizzling in P3L

　発見時書き換え方式の評価を行なうために、P3Lと名付けた処理系の実装を行なった。予約検査のための命令を発行するコンパイラ、永続アドレスと仮想アドレスの間の変換を行なうためのRTL、オブジェクトを格納するためのStorage Managerなどの基本構成要素が必要であった。コンパイラはGnu C Compilerを基にコード生成部に変更を加え、RTL,Storage ManagerはC++で新たに記述した。

　P3Lの評価には、Sun Micro SystemsのCattelらによって提案されたエンジニアリング応用向けのベンチマークであるOO1ベンチマークを用いた。データベースは、数十バイト程度の部品が互いに参照しあう部品のネットワークからなり、それぞれのパーツからは別の部品へ3つのリンクが出ている。このリンクは9割の確率で、1パーセント以内の近さの部品に接続される。「近さ」は各部品に与えられた部品番号によって定義される。OO1Benchmarkによって規定される3つの操作のうちのTraversalの一例である「Small database(2万パーツ)に対するhot traversal」の結果を図3に示す。Traversalテストは、「部品の中からランダムに一個を選択し、そこからリンクを7段に渡って辿り、訪れた3280個の部品のそれぞれに関して、x,y座標と部品タイプを引数として空の関数を呼び出す」というものである。Hotは、上記Traversalを複数の出発点に対して繰り返したのち、同一の出発点に基づいて再び同じTraversalを繰り返した場合の結果を意味している。図3に結果を示すベンチマークでは十分な主記憶が確保されているので、hot traversalでは一切I/Oは発生しない。図中randomと示されているのは、パーツ間の接続に上述の9割-1%ルールを導入しないでデータベースを構築した場合、shuffleはこのルールを導入するものの、部品番号と部品の物理的配置の関係をランダムにした場合である。図4に示すのは、データベースの規模が主記憶の量に比較して大きく、hot traversal時にもbacking storeへのアクセスが生じる時の結果である。

図表Figure 3:OO1 Benchmark Hot Traversal (Small Databases) / Figure 4:OO1 Benchmark Hot Traversal (Large Shuffled Database)

　得られた結果は2つの点で注目に値するものである。一つは、ソフトウェアに基づいた実装が、ハードウェア方式を用いたTexas Persistent Storeと比較して遜色ない性能を示していることである。ソフトウェアとハードウェアによる方式の性能比較を行なった論文が近年いくつか発表されているが、hot traversalの性能では、ソフトウェア方式は数倍以上遅いとされている。もう一つは、random,shuffleデータベースに対しては、P3LがHot traversalの開始直後には、Texas Persistent Storeを上回る性能を示している、つまり,ソフトウェアによる実装がハードウェアに基づく実装よりも高速となりうる可能性を示していることである。このような結果が得られた原因は、提案方式がページ内でのオブジェクトの詰め込みを可能としているために生じるTLB,Cacheへの影響だと思われる。backing storeへのアクセスが生じる場合には、その差はさらに顕著となっている。これは、上記の効果に加え、仮想記憶の割り当てがハードウェア方式に比べ遅延して行なわれるという、提案方式の特性による。

　²未解決のLambdaが少なければ、第1の問題も回避される

　本論文は、「Strategies for Persistent Object Faulting:An Implementation in a Persistent C++ System P3L(永続オブジェクトのフォールティング方式:永続C++システムP3Lにおける実装)」と題し、英語で記述され7章から成り、永続記憶構築のための新しいオブジェクトフォールティング機構に関し論じたものである。コンピュータ設計支援システムや地理情報システムなどの先進的アプリケーション構築のためのツールとしてオブジェクト指向データベースシステムが現在注目されているが、オブジェクトフォールティングはその実現のための基幹技術と考えられている。本論文では、発見時書き換えと呼ばれるポインタ書き換えに基づく新しいオブジェクトフォールティング方式を提案するとともに、当該方式を採用したP3Lなる永続C++システムを実装し、その性能を既存の方式の中で最速とされているMMUを利用した方式と比較することにより、提案方式の優位性を明らかにしている。

　第1章「Introduction」では、研究の背景、永続C++システムP3Lの概要、本論文の構成について述べている。

　第2章「Design Issues in Building Persistent Object Systems」では、オブジェクト指向データベースに代表される永続オブジェクトシステムを作成するために必要となる構成要素を列挙するとともに、その実装技術について概説している。その中で、第3章での議論の対象となる「オブジェクトフォールティング」および「ポインタ書き換え(pointer swizzling)」について解説し、各々を永続オブジェクトに対するアクセスを検出、あるいは予期して、オブジェクトの読み込みを行なうこと、オブジェクト識別子から仮想アドレスへの変換の繰り返しを避けることなどを目的として、仮想記憶中の参照を変換結果で書き換えることと定義するとともに、既存の永続オブジェクトシステムを概観し、その特徴をまとめている。

　第3章「Object Faulting and Pointer Swizzling Strategies」では、「アドレスの予約」と「内容の転送」という概念を新たに提唱し、それに基づいて、既存のオブジェクトフォールティング方式を分類、概観することにより、その位置付けを明確にするとともに「発見時書き換え」と名付けられた新しいポインタ書き換え方式を提案している。提案方式では「内容の転送」の実行時には、オブジェクト内に含まれる参照のうち、参照対象の存在しないものはlambdaという特殊な形式のポインタに書き換えられる(部分書き換え)。そして実行中にlambdaが発見された際に、参照対象の読み込みを行ない、参照の仮想アドレスへの完全な書き換えを行なう。この方式はフォールト時に書き換えを行なう方式(フォールト時書き換え)と、参照のデレファレンスが行なわれた段階で書き換えを行なう方式(参照時書き換え)の中間に位置するとしている。さらにP3Lにおける提案方式の動作を実例をあげて説明している。

　第4章「P3L Compiler Implementation」では、発見時書き換えに必要となる予約検査の為の機械命令列を自動的に生成するコンパイラについて記述している。P3Lは、Gnu C Compilerを基にしており、構文木生成部、ならびにRTLと呼ばれる中間コード生成部に加えられた変更が示されている。さらに、オブジェクト内の参照の部分書き換えや予約検査を実行する際に必要となる補助関数とメタデータの生成方式に関して議論している。

　第5章「Runtime Library and Storage Managers」では、ランタイムライブラリに関して、例外処理システム、永続オブジェクト識別子と仮想アドレス間のアドレス変換のために維持管理されるデータ構造、ルートオブジェクト管理、型情報の管理などを取り上げている。一方Storage Managerに関しては、ランタイムライブラリとウィスコンシン大学で開発されたExodusを始めとするStorage Managerとの間の共通インターフェイス、および、Storage Managerの実装方式について述べている。

　第6章「Performance Evaluation」では、フォールト時書き換え方式を採用したTexas Persistent Storeと呼ばれる処理系との比較を中心に、デザインアプリケーションの特性に基づいて永続オブジェクトシステムの評価を行なうために広く利用されているOO1ベンチマークを用いて、提案方式の得失を評価している。その結果から、ソフトウェアによる実装を前提とした本提案方式が、MMUを利用するTexas Persistent Storeと比べ遜色のない性能を示すこと、永続記憶の規模が大きくなり、内部のクラスタリングが良好でない場合には、その性能を上回ることを明らかにしている。さらに、実際のレイトレーシングプログラムを用いて、永続性の付加によって生じるオーバヘッドを計測し、それがわずかなものであることも確認している。

　第7章「Conclusions」では、上記の成果をまとめるとともに、提案方式の改良および、Garbage Collection,分散処理などへの適用について考察している。

　以上、これを要するに、本論文は発見時にポインタの書き換えを行なう新しいオブジェクトフォールティングの方式を提案し、「アドレス予約」と「内容の転送」という2つの概念に基づいて既存の方式に対する位置付けを明確化するとともに、この発見時書き換え方式をP3Lなる永続C++処理系において実装し、さらに性能評価を行なうことにより、ソフトウェアに基づく本提案方式が、MMUの利用を前提とする従来の方式と比較して遜色のない性能を発揮するばかりでなく、データベース内でのクラスタリングが良好でない場合にはそれを凌駕する性能を示すことを明らかにしたものであって、情報工学上貢献するところが少なくない。

　よって本論文は博士(工学)の学位請求論文として合格と認められる。