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

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

筧捷彦PM（早稲田大学理工学術院基幹理工学部情報理工学科教授）

2．採択者氏名

チーフクリエータ
千々和大輝（自由ヶ丘高等学校）
コクリエータ
なし

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

株式会社オープンテクノロジーズ

4．採択金額

3,000,000円

5．テーマ名

従来のシステムと比べて柔軟性の高いkey-value storeの開発

6．関連Webサイト

なし

7．申請テーマ概要

近年、クラウドコンピューティングにおける基盤技術として、key-value storeが注目されている。このシステムはRDBと比べて大規模なクラスタ内での使用を前提としており、ノード数の増加に対応して自動的にスケールアウトするものがほとんどである。さらに、高速に動作する必要があるのでRDBほど処理が多様でない点も特徴的である。

提案者も今年の六月に、P2P構造化オーバーレイネットワークの一つであるSkip Graphを利用した簡易的な分散key-value storeを並列プログラミング言語Erlangで実装している。このシステムの特徴は、大規模クラスタ内で効率的な範囲検索を行うことができるという点である。これはSkip GraphがChordなどのDHTとは異なり、ピアがkeyによってソートされているという性質を利用して実現している。

しかし一般的なkey-value storeは単一keyのgetとput、deleteのような既に実装されている機能しか行うことができず、とても柔軟性があるとは言い難い。そこで本プロジェクトでは、以前作ったシステムをC++で書き直して十分に高速化し、柔軟性向上のため以下の2つの新しい機能を備えた分散key-value storeを開発する。

valueによる範囲検索
自律的な分散エージェントによる拡張機構

さらに、Skip GraphはDHTに劣らない検索効率でありながら範囲検索も行うことができるというとても優秀なアルゴリズムであるが、素直に実装すると物理ノード間のデータ分布が偏ってしまうという欠点が存在する。しかし、これはデータのput時にDHTを利用してノードを選択することにより解消できると考えた。よって本プロジェクトでは並行してデータ分散基盤としてのDHTの実装も行う。

成果物はオープンソースソフトウェアとしての公開を予定している。ライセンスは特に考えていないのでとりあえずBSD Licenseとするつもりであるが、今後さらに緩いライセンスに変更する可能性もある。

8．採択理由

クリエータは、高校1年生（15歳）。提案は、Webキャッシュの手法として注目されている、key-value storeの機構を、分散ハッシュテーブルの上でskip graphによって実現しようというもの。具体的には、隣接のピアの情報を保持しておき、分散エージェントとして別プロトコルで通信を行うことで拡張性をもたせるというものである。すでに、Erlangを用いてネットワーク上で実験的なシステムを動かしてみた経験をもつ。現在、それを C++で書き直しているところだという。

この年齢でここまでのアイディアをもち、さらに手が動かせるというのはすばらしい。プログラミングは中学2年のときに始めたというが、驚くべき勉強ぶりである。提案内容の実現にとどまらず、この未踏ユースの期間にその能力を一気に開花させて、より高いレベルの成果を残してくれることを期待している。