未踏IT人材発掘・育成事業（ユース）：2008年度下期採択プロジェクト概要（郷原PJ）

1．担当プロジェクトマネージャー

• 竹内　郁雄（東京大学大学院　情報理工学系研究科　創造情報学専攻　教授）

2．採択者氏名

• チーフクリエータ：郷原 浩之(東京大学工学部システム創成学科数理社会デザインコース)
  コクリエータ：なし

3．未踏ユースプロジェクト管理組織

• 株式会社創夢

4．採択金額

• 3,000,000円

5．テーマ名

• オープンかつポータブルなデータベースガーベジコレクション

6．関連Webサイト

• なし

7．申請テーマ概要

本提案ではJavaで標準的なオブジェクトリレーショナルマッピング（以下,ORM）であるHibernate上でポータブルなデータベースガベージコレクション（DBGC）を実現する．
近年,メモリデータ構造をデータベースに保存するべくORMと呼ばれるデータベースマッピングツールが普及し始め,DB内部のリンク構造は複雑になる一方である．
しかしデータ構造の管理に目を向けた場合,共有循環構造の削除は到達可能性予測が困難であるため課題となっている. 削除を示すフラグを用いてデータを消さずに取り置く選択肢では,データが小さくことはないため,長期運用を前提とした情報システムでは不必要に高性能なデータベースを導入せざるを得なかった．また,データ流出等のリスクを開発ベンダーが取らなければならず,セキュリティー上にも問題を生じていた．
メモリ上ではグラフ削除の最も有効な方法はGCと実証されつつある.したがって分散DB等,今後さらに複雑なリンク構造をもつDBシステムが登場することを考えればアクセスの遅いDB上でも高速に動作するように設計されたDBGCは必須となる.
DBGCによって本来のサービスを長時間停止させてはいけない.本システムではユーザープログラムとの並列処理時に性能が良いDijkstraのOn-the-flyリアルタイムGCアルゴリズムを用いることでこの問題を回避する.GCでは計算時間のほとんどがマーキングに費やされる.DBの能力を最大限まで引き出せるよう,メモリ上ではなくSQLを用いた集合演算によるマーキングアルゴリズムを提案する.またテーブル間参照グラフマトリックスの解析からマーキングパスを枝と環に分解することでSQL自体の発行回数を最小化する.
開発物はApache Licenseを適用して公開し、必要十分なドキュメントを整備し、広い普及を狙う．

8．採択理由

竹内は10年前、記号処理言語の並行ガーベジコレクション (GC) のプログラムを書いていた。GCは1959年にマッカーシーらのLispの開発で初めて出てきた概念であるが、その後50年近くも火が消えずに (ボーボーと燃えているわけではないが) 研究が続けられている基幹技術である。なぜこんなに長く研究が続いているかというと、GCを行なうべきシステムやそこに含まれる性能パラメータが本当に多様で、万能GCというものが存在しないからである。また、GCが必要な言語も増えてきた。
さて、この提案を聞いてまず驚いたのが、世の中の巨大データベースの中身の大半がゴミということだ。ゴミを保存しておくために巨大の計算機資源が必要だし、ゴミからの情報漏洩もあるという。人海戦術でなにかやろうにも、巨大なうえに間違うとゴミでないものも消してしまうことがあるらしい。じゃあ、GCというわけだが、教科書で習うようなGCでは通用しないことは明らかだ。郷原君の挑戦はそこにある。内容の不透明な、商用データベースGCはすでにあるようだが、郷原君はApacheライセンスで公開するという。
これは実に芯のあるシステムプログラミング分野の提案である。とはいえ、この問題は聞くほどやさしくはない。データベースを止めないで並列的にGCをするという技術アイデアは大丈夫そうだが、実際に一般のデータベースに適用するとなると、データベース運用者の注意深い取扱いが必要になる。このプロジェクトの最終的な成否はそこをどこまでやさしく安全にできるにかかっている。郷原君の若さのもつ力に賭けよう。