P2P を利用した地球流体データアーカイブサーバ横断検索の試み
佐藤 麻美

1

(指導教員：渡辺 知恵美)

はじめにド上にあるデータは全て共通のグローバルスキーマで定義されていると想定している．
ノードが持つテーブルの各タップルについて，テーブル名，属性名，属性値をまとめてハッシュ化したものをキー，テーブル名，タップル番号，所持ノードのIP アドレスといったタップルの所在情報（もしくはタップルそのもの）を値としてその組を DHT に分散させることにより，DHT による選択演算を実現する．
また PIER の問合せ処理では，結合など関係代数演算に必要な各演算処理を定義している．

近年の地球観測と計算機の発展により大気や水質などの数値データは爆発的に増加している．それに伴い科学者達が個人で管理するデータも飛躍的に増加し，気軽に自分の計算機に蓄積されたデータを検索したり同様の研究をする科学者に観測データを公開したりしたいという要求が生まれて来た．
そこで我々は地球流体科学者を対象に，科学者個人が管理するデータのアーカイブサーバを容易に構築することの出来る Ruby on Rails ベースのパッケージ「Gfdnavi」を開発している [2], [3]．
本稿では Gfdnavi を用いて公開されるサーバ間の横断検索を P2P ネットワークを利用したリレーショナルデータベース（RDB）の絞込み検索で実現するための一検討とその手法について述べる．

2

4

PIER をベースに Gfdnavi に特化した横断検索手法について述べる．
今回は２点の限定条件を設けることとした．
1. 全てのノードに Gfdnavi がインストールされていることを前提とし，Gfdnavi で定義されているスキーマの一部をグローバルリレーショナルスキーマとして用いる．

P2P と分散ハッシュテーブル

我々は維持管理に膨大なコストが掛かる中央サーバを設置する方法ではなく，P2P ネットワークを用いて各 Gfdnavi サーバ同士が自立的にデータ管理・検索を行う横断的検索を実現する．P2P とは端末同士の繋がりを意識したオーバーレイネットワークのことである．
P2P ファイル共有ソフトウェアの検索ルーティング
方法は大きく二つ，非構造的検索のフラッディング，構造的検索の分散ハッシュテーブル（DHT）を用いた手法に分けられる．
DHT はハッシュ関数を通して算出したキーと値の組を格納したハッシュテーブルを，P2P ネットワークに参加したノードで分散して管理し効率的に検索を行う手法である．ノードが P2P ネットワークに参加すると一意な ID が付与され，ノードが公開するデータに対するハッシュテーブルエントリが生成される．エントリはデータを一意に同定する値のハッシュ値をキーとし，IP アドレス等のデータの所在を値とする 2 項組である．各ノードは自分の ID と同じもしくは近隣のキー値のハッシュテーブルを管理する．またネットワーク上に存在する幾つかの他ノードの所在情報 (スキップリスト) を管理する．検索時は，目的データのハッシュ値を算出し，所在を知っているノードの内探しているハッシュ値に最も近い値の ID を持つノードへ検索依頼を送る．フラッディングは連鎖的に検索依頼を広める手法で全データ検索などには負荷が掛かり過ぎるので向かない．そこで本研究では検索の効率性と負荷分散効果から DHT を用いる手法を採用した．

3

Gfdnavi における横断検索機能の検討

variables(int id，text name，text path)spatial_attributes(int id，int variable_id，float longitude_lb，float longitude_rt，float latitude_lb，float latitude_rt)
keyword_attributes(int id，int variable_id，text name，text value)
variables は多次元配列データセットに対するメ タ デ ー タ，spatial attributes は variables
がカバーする空間領域の最小外接矩形，keyword attributes は variables に 関 す る 空
間属性以外の属性であり，属性名 name と属性値value のペアで記述される．
なお，各スキーマの詳細やスキーマ間の関連については [2] を参照されたい．

2. Gfdnavi の空間検索インタフェースで発行される限定した問合せのみを対象とする．
空間インタフェースにて，空間領域，キーワード属性名，キーワード属性値が指定された場合に発行される問合せの内容は図 2(☆) に示す通りである．

P2P を利用したデータベース検索

RDB の P2P 検索を設計するに当たって，P2P ネットワークを利用した DB 検索の代表的研究である PeerDBと PIER[4] について分散環境での RDB 検索・共有の構造を調査した．
以下に本研究のベースとした PIER の概要を示す．
PIER は DHT を利用してネットワーク上のノードが持つデータベースを検索するシステムである．各ノー

我々が提案する RDB 検索手法の概要を以下に示す.
【Step1：DHT を用いた選択演算】
spatial attributes および keyword attributes に対する選択演算を DHT を用いて行い，検索条件に該当するタップルを所有するノード (以下該当ノードと呼ぶ)の URL を割り出す．そのために，あらかじめ各ノー

47

トや帯域の圧迫の問題がある．それらの問題を解消するため Gfdnavi の横断検索機能を P2P を利用して実現する一手法を提案した．
しかしこの提案手法にはいくつかの問題点があることが分かっている．
第一に Step1 にて該当ノードがほとんど絞り込めなかった場合，多くのノードに問合せを発行しなければならなくなる．
第二に DHT に登録するエントリ数が膨大になる恐れがある．これは空間情報の切り分け方や 1 つのデータが持つキーワード属性の多さが原因で起こると予測される．
そこでこれらの問題点を緩和する改良手法を現在検討し実装している．

1. ノード数が絞り込めないことに関する改良法
Gfdnavi では問合せ該当件数が多数の場合そこからさらに詳細な絞込を促すような検索インタラクションを設計しており [2]，空間属性に対する検索における該当データのグループ化表示，グループを細分化しての再表示を GoogleMap 上で行える機能を持っている．これを利用し，素朴法で Step1を行った時該当データ数が一定数以下でなければStep2 に進まず，データ数をインタラクティブに表示しながらユーザにさらなる絞込みを促し Step1の処理を繰り返して問合せ先を減らしていく．

図 1: 緯度経度の分割と座標の交換

2. エントリ数の多さに関する改良法
spatial attributes の空間情報の DHT への登録方
法を変える．1 つのノード内であるブロックをカバーしているデータが幾つあるかを求め，valueを”URL；その URL 内でブロックをカバーしているデータの個数” として，つまりブロックごとのデータ分布数の情報を登録する．この手法では 1つのノードが登録する空間情報のエントリ数の上限があらかじめ算出でき，予測の範囲内でエントリ数を調整できる．

図 2: 問合せ処理の流れの例
ドは keyword attributes 及び variables テーブルの各タップルに対し，key =hash(”テーブル名；属性名；属性値”)
value =”URL；variable id”の 規 則 に 従って DHT に エ ン ト リ を 登 録 す る ．
spatial attributes における問合せ条件文は範囲検索に対応するため，図 1 のように緯度経度の 2 次元空間を分割したブロックを作成し，緯度経度の範囲をブロック番号で表してハッシュテーブルに登録することとした．図 1 の例は，実際には空間検索で指定した 2点の座標が囲む範囲をブロック番号に変換し，ハッシュテーブルに登録する考え方を示している．
【Step2: 該当ノードへの問合せ】
Step1 で求められた該当ノードに対し問合せを発行し検索結果を収集する．
キーワードと空間範囲指定が行われた場合の Step1から Step2 までの一連の流れと問合せの詳細を示したものが図 2 である．

5

今後は実装したそれぞれの手法を比較検討し，実際の運用に耐え得るよう改良を加えて行きたい．

参考文献[1] 地 球 流 体 電 脳 倶 楽 部:
dennou.org/

http://www.gfd-[2] 柳平有美：“Gfdnavi:地球流体物理科学者のためのデータアーカイブサーバ構築支援ツールの開発”,
増永研・渡辺研中間発表会予稿.
[3] 渡辺知恵美： “地球惑星科学研究者のためのデスクトップサーチツールの開発に向けて”, 情報処理学会研究報告 2006-DBS-140(2), Vol.2006, No.78,
pp.429-436, 2006.
[4] R. Huebsch, J. Hellerstein, N. Lanham, B. T. Loo,S. Shenker, and I. Stoica : “Querying the Internetwith PIER”, In Proc. the 29th International Conference on Very Large Data Bases, pp. 321–332,
September 2003.

まとめと今後の課題

Gfdnavi で扱おうとしているデータは膨大であり，従来のクライアント-サーバ方式ではサーバを設けるコス48