データ検索システム及びデータ検索方法、ノード及びそのコンピュータプログラム
【課題】ノード間においてターゲットデータを管理するに際して、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現するデータ検索システム等を提供する。
【解決手段】各ノードは、自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを有し、前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、前記第２の識別子が含まれる経路情報を用いてメッセージを転送すべき他ノードを決定する転送手段とを備え、前記転送手段は前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する。
【解決手段】各ノードは、自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを有し、前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、前記第２の識別子が含まれる経路情報を用いてメッセージを転送すべき他ノードを決定する転送手段とを備え、前記転送手段は前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、管理対象のデータ（ターゲットデータ）を、Ｐ２Ｐを構成するノード間において管理するデータ検索技術に関する。
【背景技術】
【０００２】
Ｐ２Ｐ（Ｐｅｅｒ ｔｏ Ｐｅｅｒ、ピアツーピア）とは、特定のサーバによらず、ピア（ノード）と呼ばれる互いに対等な複数の通信装置によって構成される分散型のデータ検索システムによく用いられるアーキテクチャである。即ち、Ｐ２Ｐとは、通信方式、通信モデル、あるいは、通信技術の一分野を指す。このようなＰ２Ｐを、継続的あるいは一時的に、コンピュータネットワーク（通信ネットワーク）に接続した計算機群によって構成するに際して、各計算機のＣＰＵ（Central Processing Unit）は、ピア（ノード）と呼ばれるプロセス（処理、プログラム）を、１つあるいは複数実行する。Ｐ２Ｐを構成する分散型のデータ検索システムにおいて、各ノードは、管理対象である複数のデータを、個々のノード、或いは一部のノードに分配した状態で保持する。そして、これらのノードは、互いに対等に通信を行いながら、データの検索や新しいデータの登録といった管理対象のデータに対する処理を実現する。本願において、管理対象のデータとは、例えば動画や音楽などのコンテンツ情報や、データベースのインデックス情報、プログラム（ソフトウェア・プログラム・モジュール）を構成する情報などを指す（以下、これらのデータを「ターゲットデータ」と称する）。但し、係るターゲットデータは、それ以外の情報であっても構わない。
【０００３】
ところで、Ｐ２Ｐ技術の一類型として、上記のようなデータ検索システムに一般的に適用される技術として、分散ハッシュテーブル（Ｄｉｓｔｒｉｂｕｔｅｄ Ｈａｓｈ Ｔａｂｌｅ：ＤＨＴ）がある。
【０００４】
ＤＨＴにおいて、あるコンピュータネットワークに接続された計算機群の各ＣＰＵは、ノードに所定の方法で論理的な識別子（論理識別子、識別子、ＩＤ）を与える、そして、ＤＨＴでは、ノードを識別子空間にマップ（マッピング）することで、当該コンピュータネットワークの上に、論理的には別のネットワークが構築される。ＤＨＴにおいて個々のＣＰＵがノードに論理識別子を与える所定の方法は、実装の形態などによって様々である。但し、一般的なＤＨＴでは、ハッシュ関数の出力値であるハッシュ値を、論理識別子として使用する方法が知られている。この場合、物理的に存在するコンピュータネットワーク上に論理的なネットワークが構築されることにより、ＤＨＴのノードは、当該コンピュータネットワークよりも下位のコンピュータネットワークのトポロジを意識しない通信を行うことができる。すなわち、ＤＨＴにおける任意のノードは、ＩＰアドレスなどのコンピュータネットワーク上のアドレス（住所）を知らない他ノードとも通信を行うことができる。このように、あるコンピュータネットワーク上に構築される別のネットワークのことを、“オーバレイネットワーク”と呼ぶ。即ち、オーバレイネットワークとは、インターネットなどの物理的なトポロジとは独立したアプリケーションレベルのネットワークである。本願における以降の説明では、コンピュータネットワーク及び通信ネットワークを“ネットワーク”と略称する場合がある。一方、係るオーバレイネットワークを意味するときは、略称せずに“オーバレイネットワーク”と表現する。
【０００５】
図２は、本願に関連するオーバレイネットワークと、下位のコンピュータネットワークとの対応関係を模式的に例示する図である。図中の破線矢印は、コンピュータネットワークに接続された計算機（黒丸）と、オーバレイネットワークにおけるノード（白丸）との対応関係を表している。図２に示される通り、一つの計算機は、オーバレイネットワークでは複数のノードとして振舞う場合もある。また、コンピュータネットワークのトポロジと、オーバレイネットワークのトポロジとは、同一であるとは限らない。
【０００６】
ＤＨＴを用いた分散型のデータ検索システムにおいて、コンピュータネットワークに接続された計算機群の各ＣＰＵは、所定の方法でターゲットデータに論理識別子を与える。そして、各ＣＰＵは、論理識別子を与えたターゲットデータを、論理識別子に従って、ノードと同じ識別子空間へマップすることにより、当該ターゲットデータを、各ノードに分散配置する。ここで、ターゲットデータに対して論理識別子を与える方法としては、採用するＤＨＴのアルゴリズムや実装形態によって様々である。例えば、係る方法としては、ハッシュ関数の出力値であるハッシュ値を論理識別子として利用する方法を採用することができる。
【０００７】
図３は、非特許文献１に記載されているＣｈｏｒｄアルゴリズムを例に、識別子空間におけるノードと、ターゲットデータとの対応関係を例示する図である。図３において、二重破線の円環（Ｃｉｒｃｌｅ）は、Ｃｈｏｒｄにおける識別子（ＩＤ）空間を表している。図３に示す例において、識別子の全体の値域は、０以上１２８未満とする。ここで、５つの白丸は、ノードを表す。説明の便宜上、個々のノードには、ラベルａ〜ｅが付与されている。ここで、ラベルとは、各ＣＰＵがノードとして実行するプロセスが当該システムには複数存在する場合があるため、便宜上、それらを区別するために付与した記号（ノードの名称）である。図３では、ノードに付与される識別子によっても、ノードを区別することは可能である。尚、後述する実施形態に係る負荷分散によって、ノード（プロセス）は、実行中に、自ノードが持つ識別子の値を変更する可能性がある。そのため、プロセスを真に特定するためには、ラベルを用いることとする。
【０００８】
また、図３に示す円環において、各ノードの下部には、個々のノードのノード識別子（ノードＩＤ：ＮＩＤ）を表記する。本願において、ノード識別子は、識別子空間上の位置の名称を表しており、ノードが所持している情報である。白い四角形は、ターゲットデータを表す。各ターゲットデータの上部には、個々のターゲットデータのデータ識別子（データＩＤ：ＤＩＤ）を示す。図３によれば、ノードとターゲットデータとが同じ識別子空間上にマップされていることが判る。以降、便宜上、ノードに付与される識別子をノードＩＤ、データに付与される識別子をデータＩＤと呼ぶ。但しこれらの識別子は、何れも同じ識別子空間から得られる値であることに注意する。また、以下の説明において、ノードＩＤとデータＩＤどちらにも当てはまる説明については、単に“識別子”と表現する場合がある。
【０００９】
ところでＤＨＴでは、識別子に距離の概念が採用されている。ＤＨＴにおいて、係る距離の概念は、分散配置されたデータ（ターゲットデータ）の管理に関して非常に重要な役割を果たす。距離の定義は、アルゴリズムによって異なる。例えばＣｈｏｒｄにおける距離の定義によると、識別子Ｘからの距離が最も小さい（短い）識別子は、Ｘの次に値が大きな識別子である。一方、識別子Ｘからの距離が最も大きい（長い）識別子は、Ｘの次に値が小さな識別子である。つまり、識別子空間上において値が異なる二つの識別子ＸとＹとに注目した場合、ＸからＹまでの距離の大きさは、ＹからＸまでの距離の大きさと同値ではない。例えば図３において、ノードａにとって最も近いノード（すなわち、ノードａからの距離が最も小さいノード）は、ノードａの次に値が大きいノード識別子を持つノードｂである。これに対して、ノードｂにとって最も近いノードは、ノードｂの次に値が大きいノード識別子を持つノードｃである。
【００１０】
また、識別子空間は、図３に示す如く循環している。言い換えれば、図３に示す識別子空間は、前述した通り識別子の全体の値域を０以上１２８未満と仮定したため、当該識別子空間において最大の識別子値である１２７の次に大きい識別子値は０である。このため、ノードｅにとって最も近いノードは、ノードａとなる。Ｃｈｏｒｄでは、自ノードからの距離が最も近い他ノードは、そのノードのサクセッサと呼ぶ。一方、自ノードまでの距離が最も近い他ノードは、そのノードのプレデセッサと呼ぶ。従って、図３に示す例において、ノードｅのサクセッサはノードａである。ノードｅのプレデセッサはノードｄである。
【００１１】
尚、Ｃｈｏｒｄと同様に識別子空間がリング状で、同様の距離の定義を持つ異なるアルゴリズムとして、他にＫｏｏｒｄｅ（非特許文献４）と呼ばれるアルゴリズムも存在する。
【００１２】
上述したように、ノードは、所定の規則に基づき定められた識別子の、ある値域を情報として保持する。ここで、値域とは、ある値から他の値までの値の範囲である。そして、ノードは、この値域に属するデータＩＤを持つデータを、ターゲットデータとして管理する。以降、本願では、このような識別子空間上の値域を、“データ保持値域”と呼ぶ。また、ある識別子Ｘがあるノードのデータ保持値域に属するとき、そのノードを、識別子Ｘの“担当ノード”と呼ぶ。ＤＨＴにおいて、識別子Ｘの担当ノードは、識別子Ｘから最も近い識別子を持つノードである。よって、あるノードのデータ保持値域は、自ノードＩＤまでの距離が最も小さい他ノードのノードＩＤから、自ノードＩＤまでの範囲として算出される。例えば、距離の定義が非対称であるＣｈｏｒｄアルゴリズムでは、あるノードのデータ保持値域は、プレデセッサのノードＩＤより大きく、かつ、自ノードＩＤ以下である。
【００１３】
図４は、図３に例示したノードａ〜ｅの夫々のデータ保持値域と、それらノードが保持するデータとの関係を説明する図である。表１は、図３に例示した各ノードのデータ保持値域を表すテーブルである。
【００１４】
【表１】
【００１５】
本願において、データ保持値域は、数学的な表記によって表現される。例えば、表１に示すノードｃのデータ保持値域（２８、５６］は、識別子２８より大きく識別子５６以下であることを意味する。例として、表１におけるノードａ〜ｅが保持するターゲットデータの一覧を、図４（ａ）から図４（ｅ）にリストする。当該リストに示すように、各ノードは、ターゲットデータに与えられたデータＩＤと、ターゲットデータとを関連付けて保持していることとする。ノードのデータ保持値域が大きいほど、そのノードは、確率的に数多くのターゲットデータを保持する。そして、各ノードにおいて、もし、そのノードのターゲットデータに対する格納容量やネットワークの帯域幅に対して、管理すべきターゲットデータの件数やデータボリュームが大きいとき、そのノードの負荷は高いと言える。
【００１６】
複数のノードによって複数のターゲットデータを分散管理するためには、ノード間における通信は欠かせない。ＤＨＴを採用するノードは、任意の識別子を検索キーとし、その検索キーの担当ノードへメッセージを届ける通信を行う。ノード間において通信されるメッセージには、検索用のキー値と、宛先ノードへの何らかの処理命令（処理要求）とが記述されている。記述される処理命令としては、例えば、ターゲットデータの検索命令や登録命令などが挙げられる。ノードは、オーバレイネットワークに参加している他のすべてのノードの、ネットワーク上の住所（例えばＩＰアドレス）を知っているとは限らない。このため、ノードは、検索キーの担当ノードの住所を知らない場合もある。このような場合、各ノードは、それぞれが持つ経路表から適切なノードを選び、メッセージをノード間でリレー（中継、転送）することにより、当該メッセージを、担当（宛先）ノードに最終的に届ける（“経路表”については図５を参照して後述する）。そして本願では、メッセージが経由するノードの道筋を、“経路（Ｒｏｕｔｅ）”と称する。また、メッセージをノード間において転送する処理を、メッセージ転送（メッセージ転送処理）と称する。
【００１７】
経路表が保持する他ノードの情報（経路情報）は、ネットワークからメッセージを受け取ったノードが、そのメッセージを、次の適切な他ノードへ転送することが可能な情報であれば、どのような情報であっても構わない。
【００１８】
図５（ａ）から図５（ｅ）は、図３に例示した５つのノードａ〜ｅの経路表を例示する図である。これらの経路表には、経路情報として、各ノードの識別子空間上の値（たとえばノードＩＤ）と、ネットワーク上のアドレス（住所）とが登録されている。ここではＩＰアドレスとポート番号がネットワーク上のアドレスである。どのような基準で経路表に登録すべき他ノードを選ぶかは、実装態様やアルゴリズムによって異なる。図５（ａ）から図５（ｅ）に例示した各表は、Ｃｈｏｒｄアルゴリズムに則って作られている。
【００１９】
経路表の中から、次にメッセージを転送べきノードを選択する方法は、実装形態やアルゴリズムによって異なる。但し、基本的には、受け取った検索キーが表す識別子からの距離がより小さくなるような識別子を持つ他ノードへ、メッセージは転送される。例として、Ｃｈｏｒｄアルゴリズムにおけるメッセージ転送の動作を以下に説明する。
【００２０】
Ｃｈｏｒｄにおいて、各ノードは、自ノードのサクセッサがどのノードであるか、およびサクセッサの住所を必ず知っていることを前提とする。
【００２１】
メッセージ転送の最終的な目標は、検索キー（ノードＩＤあるいはデータＩＤ）を含むメッセージを、識別子Ｘの担当ノードに転送することである。ここで、担当ノードとは、識別子空間上において、識別子Ｘからの距離が最も小さいノードＩＤを持つノード、あるいは、自ノードのデータ保持値域に識別子Ｘが属しているノードである。
【００２２】
あるノードは、メッセージを受け取ると、メッセージに含まれる検索キーＸと、自ノードおよび経路表に登録された全てのノードのノードＩＤとを比較する。Ｘまでの距離が最も小さいノードＩＤを持つノードが、自ノードがメッセージを転送すべきノードである。もし、経路表に登録された、サクセッサを含む他のどのノードより、自ノードＩＤからＸまでの距離が小さいとき、自ノードは、自ノードＩＤとサクセッサのノードＩＤとの間に、Ｘが存在していることが判る。上述したサクセッサの定義によれば、自ノードとサクセッサとの間に他のノードは存在しない。そのため、自ノードは、Ｘからの距離が最も小さいノードＩＤを持つノードが自分のサクセッサであることが分かる。すなわち、サクセッサはＸの担当ノードである。自ノードは、直ちにサクセッサにメッセージを転送し、当該メッセージに対するメッセージ転送処理は完了する。
【００２３】
Ｃｈｏｒｄでは、上述した手順のように、検索キーＸを含むメッセージは、必ずＸの担当ノードをサクセッサとして持つノードにたどり着き、その次の転送で担当ノードにたどり着く。以降の説明において、Ｘの担当ノードをサクセッサとして持つノードは、Ｘのルートノード（Ｒｏｏｔ Ｎｏｄｅ）と呼ぶ。
【００２４】
図６に示す状態（ａ）から状態（ｅ）は、図３に例示する識別子空間におけるメッセージ転送の動作の流れを説明する図である。はじめに、図６の状態（ａ）に示すように、ノードｃは、オーバレイネットワークの外部から受信したメッセージにより、識別子３を持つターゲットデータの検索命令を取得したとする。このメッセージには、検索キーとして、探したいターゲットデータの識別子値（ここではデータＩＤ＝３）が含まれている。また、ここでは図６の状態（ａ）に例示するように、ノードｃがオーバレイネットワークの外部からメッセージを受信している。尚、ＤＨＴでは、一般に、任意のノードが外部からメッセージを受信可能である。
【００２５】
次に、図６の状態（ｂ）に示すように、ノードｃは、まず自ノードのデータ保持値域（２８、５６］に、当該識別子（データＩＤ＝３）が属さないことを確認する。その後、ノードｃは、自ノードおよび経路表（図５（ｃ））に登録されたノードの中から、データＩＤ＝３までの距離が最も小さいノードＩＤを持つノードｅを選ぶ。そしてノードｃは、ノードｅに対して、当該メッセージを転送する（図６の状態（ｂ）に示す動作＜１＞）。
【００２６】
ノードｅは、当該メッセージを受信するのに応じて、ノードｃと同様に、自ノードのデータ保持値域（６４、１２１］にデータＩＤ＝３が属するか否かを確認し、この例の場合は属さないと判断する。そこで、ノードｅは、自ノードおよび経路表（図５（ｅ））に登録されたノードの中から、データＩＤ＝３までの距離が最も小さいノードＩＤを持つノードａを選び、ノードａに対してメッセージを転送する（図６の状態（ｂ）に示す動作＜２＞）。
【００２７】
同様な手順により、ノードａもまた、自ノードのデータ保持値域（１２１、２］にデータＩＤ＝３が属さないのを確認した後、自ノードおよび経路表に登録されたノードの中から、データＩＤ＝３までの距離が最も小さいノードＩＤを持つノードａを選ぶ。この場合、ノードａは自ノードを選んだため、ノードａは、データＩＤ＝３のルートノードが自分であり、かつ、担当ノードが自分のサクセッサ（ノードｂ）であることを認識する。ノードａは、ノードｂに対して、ノードｃがデータＩＤ＝３のターゲットデータを探していることを、メッセージによって伝達する（図６に示す状態（ｃ））。メッセージを受け取ったノードｂは、ノードｃへデータＩＤ＝３のターゲットデータを送信する（図６に示す状態（ｄ））。そして、ターゲットデータを受け取ったノードｃは、当該検索命令の発行元に対して、当該ターゲットデータを送信する（図６に示す状態（ｅ））。
【００２８】
上述したノードは、必要に応じて、オーバレイネットワークへの参加（加入）、或いは離脱（脱退）を行う場合がある。あるいは、何らかの不具合により、係るノードは、短期的あるいは長期的に通信不可能な状態に陥ることがある。これにより、経路表に登録されたノードの識別子や住所などの経路情報は、時間の経過に伴い失効する可能性がある。例えば、図３におけるノードｅが、突然の不具合で通信不可能になったと仮定する。このとき、図６に示した一連の状態（ａ）から（ｅ）に例示した手順によってメッセージ転送を行おうとすると、ノードｃの経路表（図５（ｃ））からノードｅを選択し、ノードｅに対してメッセージを送信しても通信は失敗する。このとき、実装態様によっては、ノードcは、経路表の中から、検索キーまでの距離が次に近いノードｄを選択することによって再びメッセージの送信を試みるなどの処置を行う。しかしながら、通信の失敗による通信遅延はどうしても生じる。
【００２９】
このような問題を未然に防ぐため、ＤＨＴのアルゴリズムでは、各ノードが経路表のヘルスチェックを行う。ヘルスチェックは、経路表に登録されている他ノードに関する経路情報が正しいかどうかを、その他ノードと通信を試みることによって確認可能な機能である。更にヘルスチェックは、もし経路情報が間違っていた場合はその経路情報を経路表から削除する、ないしは、正しい経路情報に書き換える機能である。Ｃｈｏｒｄでは、ヘルスチェックは定期的に行われる。図３に例示する状況においてノードｅが通信不可能に陥った場合、あるタイミングにおけるチェックで、ノードａ、ｂ、ｃ、ｄは、ノードｅの経路情報が失効していることを検出する。その時点において、夫々のノードは、経路表からノードｅに関する情報を削除する。しかしながら、どのアルゴリズムにおいても、実際に経路情報が失効したタイミングからヘルスチェックにより経路表が正されるまでの時間は、経路表は失効した情報を含むことになる。ノードのオーバレイネットワークへの参加や離脱が頻繁な場合などは、経路表に失効した情報が含まれる確率が高くなるため、通信効率はより低下する。
【００３０】
先述したように、ＤＨＴでは、データ保持値域が広いほど、多くのターゲットデータを保持する確率が大きくなる。すなわち、管理するターゲットデータの量が増えるので、ノードの負荷が比較的大きくなる。あるノードに過大な負荷が集中すると、そのノードの処理効率は低下し、結果として、データ検索システム全体の処理効率が低下する。そのため、ＤＨＴでは、重要な要素技術として、様々な負荷分散技術が提案されている。
【００３１】
本願に関連する多くの負荷分散技術において、ＣＰＵは、負荷の高いノードや他のノードのデータ保持値域を変更する。そしてＣＰＵは、その値域から外れたデータＩＤに対応するターゲットデータを、新たな担当ノードへ移すことによって負荷の分散を実現する。係る多くの負荷分散技術は、このような技術的アプローチを採用する。ここで、データ保持値域を変更するアプローチを採用する負荷分散技術のイメージ図を、図７に示す。
【００３２】
図７は、負荷分散に際してデータ保持値域を変更するアプローチを取る関連技術を説明する図である。即ち、図７は識別子空間の一部を表わしており、ノードＸとノードＹとが空間上に隣りあって存在している。図７に示す例では、ノードＸのデータ保持値域に属するターゲットデータが多いので、ノードＸは負荷が大きい。そこで、係る負荷分散技術では、ノードＩＤを基に算出されるデータ保持値域を変更することで、一部のターゲットデータの担当ノードをノードＸからノードＹとし、これにより負荷の分散を図っている。ここで、上記のようなデータ保持値域を変更するアプローチを採る手法としては、インターバルシフト（非特許文献２）、仮想サーバ（非特許文献３）、仮想ノード（非特許文献２）と呼ばれるアルゴリズムなどが提案されている。
【００３３】
ここで、データ保持値域を変更することで負荷分散を行う動作を、図８（ａ）から図８（ｃ）、並びに表１を参照して具体的に説明する。
【００３４】
図８（ａ）から図８（ｃ）は、図３に示す識別子空間において、インターバルシフトを適用する動作を例示的に説明する図である。インターバルシフトは、負荷の高いノードが、自ノードのデータ保持値域を、データ保持値域が隣り合う他ノードとの間で調整することによって狭くする手法である。具体的には、自ノードのノードＩＤの値を変更することにより、自ノードのデータ保持値域を狭くする。ここでこの手法について概説する。
【００３５】
図３に示すノードｅにおいて、データ保持値域は、前述した表１に示したように（６４、１２１］である。係るデータ保持値域に対応して、ノードｅは、図８（ａ）に示すように、８個のデータ（即ち、ＤＩＤ＝６４、７０、８０、８２、１０３、１１０、１１５、１１９）を保持している。このため、ノードｅは、その他のノードに比べて負荷が高い。その一方で、ノードｅとデータ保持値域が隣り合うノードａ及びノードｄは、保持しているデータが夫々１個であるため、ノードｅと比較して負荷が小さい。このとき、ノードｅは、隣り合うノードａ及びノードｄと通信することにより、より負荷の軽いノードを、負荷の分散先として選択すべきである（ここではノードａを選択したとする）。ノードｅは、自ノードが管理するオブジェクトデータの一部を、ノードａに移譲（分散）できるように、自ノードのノードＩＤの値を変更する。ノードＩＤ値をどのように変更するかは、アルゴリズムや実装態様によって異なる。ここではノードｅは、保持するデータ数が以前の半分になるよう、自ノードの識別子を９３に設定する（図８（ｂ））。これにより、ノードｅのデータ保持値域は（６４、９３］、ノードａのデータ保持値域は（９３、２］となる。そこで、ノードｅは、自ノードに代わりノードａが新たに管理することになったターゲットデータ（ＩＤ１０３〜１１９）を、ノードａに送信する（図８（ｃ））。この一連の動作により、ノードｅは、管理するデータの数を減らした分だけ負荷が軽くなる。
【００３６】
しかしながら、先述した負荷分散の手法には、以下の問題がある。
【００３７】
第一に、ＤＨＴにおけるメッセージ転送は、経路表に登録された経路情報（ノードの住所やノードＩＤ）が全て正しい場合に限って、最適な、あるいは最短の経路を辿って宛先ノードへたどり着くことが実現できる。しかしながら、経路表から選んだメッセージの転送先ノードの経路情報が既に失効していた場合は、非効率な経路選択となる。例えば、次の転送先として選択したノードの経路情報のうち、住所（ＩＰアドレスやポート番号）が失効していた場合は、通信そのものが失敗する。或いは、住所は正しくともノードＩＤが負荷分散によるノードＩＤの変更などで失効していた場合は、選択したノードにメッセージが無事に届けられたとしても、最短経路が選択された可能性は低くなる。
【００３８】
例えば、図８（ｃ）に示す状態の直後に、オーバレイネットワークの外部から、データＩＤ＝１１９のターゲットデータを検索する要求を、ノードｃが新たに取得した場合を考える。そしてこの場合、何れのノードも経路表のヘルスチェックがまだ行われておらず、経路表は、図５（ａ）から図５（ｅ）に示す状態であると仮定する。
【００３９】
上記のような状況において、ノードｃは、まず、自ノードと経路表（図５（ｃ））とに登録された他ノードｄおよびｅの中から、データＩＤ＝１１９までの距離が最も小さいノードＩＤを持つノードｄを選択する。そしてノードｃは、ノードｄへ検索キー（データＩＤ＝１１９）を含むメッセージを転送する。
【００４０】
メッセージを受け取ったノードｄは、同様に、自ノードと経路表（図５（ｄ））とに登録された他ノードａおよびｅの中から、検索キーまでの距離が最も小さいノードＩＤを持つノードｄを選択する。この場合、選択したノードが自ノードであるため、ノードｄは、自ノードがデータＩＤ＝１１９のルートノードであると判断する。更にノードｄは、サクセッサであるノードｅが、データＩＤ＝１１９の担当ノードだと判断する。そしてノードｄは、ノードｅに対して、データＩＤ＝１１９に対応するターゲットデータを要求する。しかし実際は、図８（ａ）乃至図８（ｃ）を参照して上述した一連の負荷分散動作によって、このターゲットデータは、既にノードａが所持している。このため、ノードｅは、要求元であるノードｃに対して、当該ターゲットデータを送信することができない。このとき、実装態様によっては、ノードｅは検索失敗のメッセージを、ノードｃへ向けて送信し、メッセージの転送を終えるかもしれない。あるいは、ノードｅは、自ノードが持つ経路表（図５（ｅ））を用いてメッセージの転送処理をやり直すかもしれない。そしてこの場合、ノードｅの経路表が図５（ｅ）に示す状態のままであれば、ノードｅは、メッセージの検索キーが表すデータＩＤ＝１１９までの距離が最も近いノードはノードｄであると判断する。そしてノードｅは、データＩＤ＝１１９に対するターゲットデータの検索要求メッセージを、ノードｄへ改めて転送し直す。ノードｄは、もし経路表がまだ図５（ｄ）のままならば、先ほどと同様にノードｅを検索キー１１９の担当ノードだと誤認する。このように、必要なノードにおいてヘルスチェックが実行され、且つ必要な経路情報が更新されるまでの間、当該メッセージは、オーバレイネットワーク上のノード間をさまよい、メッセージ転送が非効率になる可能性がある。
【００４１】
このように、上述した関連技術に係る負荷分散手法には、各ノードのデータ保持値域を変更する過渡的な期間において、メッセージ転送の効率が一時的に悪化するという問題がある。これは、ＤＨＴにおいて、ノード識別子（ノードＩＤ）の値が、ターゲットデータをどの程度の数だけ保持するかを決める要素であると共に、ノード識別子の値が経路表にも含まれ、メッセージ転送に際して用いられることが原因である。
【先行技術文献】
【非特許文献】
【００４２】
【非特許文献１】Ｉｏｎ Ｓｔｏｉｃａ，Ｒｏｂｅｒｔ Ｍｏｒｒｉｓ，Ｄａｖｉｄ Ｋａｒｇｅｒ，Ｍ． Ｆｒａｎｓ Ｋａａｓｈｏｅｋ ａｎｄ Ｈａｒｉ Ｂａｌａｋｒｉｓｈｎａｎ，”Ｃｈｏｒｄ：Ａ Ｓｃａｌａｂｌｅ Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ Ｌｏｏｋｕｐ Ｓｅｒｖｉｃｅ ｆｏｒ Ｉｎｔｅｒｎｅｔ Ａｐｐｌｉｃａｔｉｏｎｓ，”２００１．
【非特許文献２】Ｋａｒｇｅｒ， Ｄａｖｉｄ Ｒ．， ａｎｄ Ｍａｔｔｈｉａｓ Ｒｕｈｌ，”Ｓｉｍｐｌｅ Ｅｆｆｉｃｉｅｎｔ Ｌｏａｄ−Ｂａｌａｎｃｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ Ｓｙｓｔｅｍｓ，”ＳＰＡＡ’０４．
【非特許文献３】Ａｎａｎｔｈ Ｒａｏ， Ｋａｒｔｈｉｋ Ｌａｋｓｈｍｉｎａｒａｙａｎａｎ， Ｓｏｎｅｓｈ Ｓｕｒａｎａ ａｎｄ Ｒｉｃｈａｒｄ Ｋａｒｐ，”Ｌｏａｄ Ｂａｌａｎｃｉｎｇ ｉｎ Ｓｔｒｕｃｔｕｒｅｄ Ｐ２Ｐ Ｓｙｓｔｅｍｓ，”ＩＰＴＰＳ’０３．
【非特許文献４】Ｋａａｓｈｏｅｋ， Ｆｒａｎｓ Ｍ．， ａｎｄ Ｄａｖｉｄ Ｋａｒｇｅｒ，”Ｋｏｏｒｄｅ： Ａ Ｓｉｍｐｌｅ ｄｅｇｒｅｅ−ｏｐｔｉｍａｌ ｄｉｓｔｒｉｂｕｔｅｄ ｈａｓｈ ｔａｂｌｅ，”２００３．
【発明の概要】
【発明が解決しようとする課題】
【００４３】
関連技術として上述したＤＨＴの効率化のための負荷分散技術においては、ターゲットデータを別ノードに移し替えるために、ノードの識別子（ＮＩＤ）を変更する。このため、係る負荷分散技術においては、複数のノードの経路表において一部の情報の失効が発生するのに応じて、それら経路表に登録されている経路情報の削除等の書き換えが行われる。そして、経路情報が書き換えられている過渡的な期間において、ノード間において転送されるメッセージは、場合（タイミング）によっては、書き換えが行われていない定常状態と比較して多くのノードを中継（迂回）される。このため、メッセージの転送に長い時間を要したり、或いは、通信が失敗するなどの問題が生じる。これは、経路情報の書き換えが行われている間にメッセージの転送が行われることに起因して、当該各ノードが接続されているネットワークの通信状態が不安定になることに起因する。
【００４４】
即ち、上記の問題は、ノード毎に唯一決定されている識別子（ノードＩＤ：ＮＩＤ）が、ノードが管理するターゲットデータの量に影響を与えると同時に、経路情報の一部としても含まれているため、メッセージ転送の実行に際して、次の中継ノードを決定するために重要な役割を果たすことに起因する。
【００４５】
更に、上述した問題は、ストレージの容量や帯域幅など、ターゲットデータを保持できる量に影響を与えるノード（ひいてはノードを実行するＣＰＵ（Central Processing Unit）や計算機）の性能がノードごとに異なるようなヘテロ（ヘテロジニアス）な環境において、以下に説明する更なる問題を派生する。
【００４６】
即ち、上記のようなヘテロな環境の場合、ノードが保持できるデータの数量（ボリューム）は、ノードによって異なる。そのような環境において、各ノードの負荷ができるだけ均一に分散するようにターゲットデータを分配していくと、データ保持値域は、ノード毎に異なってくる。そして、データ保持値域の大きさに偏りが生じると、識別子空間上のある近接した範囲において複数のノードが識別子を割り当てられ、ノード群が比較的密集する現象が生じる。このとき、密集しているノードは、密集していないノードに比べて、ターゲットデータの保持量が少なく、且つ他ノードの経路表に登録される確率が低い。すなわち、メッセージの中継ノードとして選ばれる確率が低い。一般に、メッセージの情報量は、ターゲットデータの情報量より小さい。このため、多くのターゲットデータを保持しきれないノードであっても、メッセージの中継であれば実行可能な場合がある。しかしながら、上述のとおり、負荷分散の結果、データ保持値域の大きさがノード間で大きく偏ると、メッセージの中継ノードとして選ばれる確率にノード間で差が生じ、これに応じてノードのリソースに無駄が生じる。
【００４７】
これは、関連技術として上述したＤＨＴ技術では、各ノードが保持するターゲットデータの数量に由来する負荷の観点から、個々のノードの経路表に対して、どの程度の数量の経路情報を登録するかを調整することが難しいためである。
【００４８】
本発明は、上述した課題を解決することを目的とする。即ち本発明は、ノード間においてターゲットデータを管理するに際して、上述した関連技術と比較して、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現するデータ検索システム等の提供を主な目的とする。
【課題を解決するための手段】
【００４９】
上記の目的を達成すべく、本発明に係るデータ検索システムは、以下の構成を備えることを特徴とする。
【００５０】
即ち、管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノードにおいて管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するデータ検索システムであって、
各ノードは、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する。
【００５１】
また、例えば前記各ノードの転送手段は、
前記メッセージを受信するのに応じて、自ノードが保持する前記経路情報を参照した結果に応じてノード間においてメッセージの転送を繰り返すことにより、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子を持つ特定ノードに対して、前記メッセージを転送すると良い。
【００５２】
また、上記の場合において、例えば前記複数のノードは、
自ノードが担当するストレージに関する情報を有しており、
前記特定ノードの転送手段は、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行するとよい。
【００５３】
また、上記同目的を達成する他の観点は、管理対象である複数のターゲットデータを、オーバレイネットワーク上において管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するノードであって、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信した際、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送することを特徴とする。
【００５４】
尚、同目的は、上記の各構成のデータ検索システムに対応するデータ検索方法によっても達成される。
【００５５】
また、同目的は、上記の各構成を有するノードを、コンピュータによって実現するコンピュータ・プログラム、及びそのコンピュータ・プログラムが格納されている、コンピュータ読み取り可能な記憶媒体によっても達成される。
【発明の効果】
【００５６】
本発明によれば、ノード間においてターゲットデータを管理するに際して、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現するデータ検索システム等の提供が実現する。
【図面の簡単な説明】
【００５７】
【図１】本発明の実施形態に係るデータ検索システムの構成を例示するブロック図である。
【図２】本願に関連するオーバレイネットワークと、下位のコンピュータネットワークとの対応関係を模式的に例示する図である。
【図３】非特許文献１に記載されているＣｈｏｒｄアルゴリズムを例に、識別子空間におけるノードと、ターゲットデータとの対応関係を例示する図である。
【図４】図３に例示したノードａ〜ｅの夫々のデータ保持値域と、それらノードが保持するデータとの関係を説明する図である。
【図５】図３に例示した５つのノードａ〜ｅの経路表を例示する図である。
【図６】図３に例示する識別子空間におけるメッセージ転送の動作の流れを説明する図である。
【図７】負荷分散に際してデータ保持値域を変更するアプローチを取る関連技術を説明する図である。
【図８】図３に示す識別子空間において、インターバルシフトを適用する動作を例示的に説明する図である。
【図９】本発明の第１及び第２の実施形態に係るデータ検索装置のハードウェア構成を例示的に説明する図である。
【図１０】本発明の第２の実施形態に係るデータ検索システムを、Ｃｈｏｒｄアルゴリズムに適用した動作例を説明する図である。
【図１１Ａ】図１０における各ノードの担当ストレージ表を示す図である。
【図１１Ｂ】図１０における各ノードの隣接ストレージ表を示す図である。
【図１２】本発明の第２の実施形態に係るデータ検索システムにおいて、高負荷な状態にあるノードｅから負荷分散を行うときの動作の流れを説明する図である。
【図１３Ａ】本発明の第２の実施形態に係るデータ検索システムにおいて、オーバレイネットワークに新たなノードが参加する動作を説明する図である。
【図１３Ｂ】本発明の第２の実施形態に係るデータ検索システムにおいて、オーバレイネットワークに新たなノードが参加する動作を説明する図である。
【図１３Ｃ】本発明の第２の実施形態に係るデータ検索システムにおいて、オーバレイネットワークに新たなノードが参加する動作を説明する図である。
【図１４】図１３Ａから図１３Ｃに示すオーバレイネットワークへの参加動作において各ノードが参照する担当ストレージ表を例示する図である。
【図１５】本発明の第２の実施形態に係るデータ検索装置が実行するターゲットデータの探索処理を示すフローチャートである。
【図１６】本発明の第２の実施形態に係るデータ検索装置が実行するオーバレイネットワークへの参加処理を示すフローチャートである。
【図１７】本発明の第２の実施形態に係るデータ検索装置が実行する担当ストレージ表の書き換え処理を示すフローチャートである。
【図１８】本発明の第２の実施形態に係るデータ検索装置が実行するネットワークからの離脱処理を示すフローチャートである。
【図１９】本発明の第２の実施形態に係るデータ検索装置が実行する負荷分散処理を示すフローチャートである。
【図２０】本発明の第２の実施形態に係るデータ検索装置が実行する経路識別子の変更処理を示すフローチャートである。
【図２１】本発明の第１の実施形態に係るデータ検索システムの構成を示すブロック図である。
【発明を実施するための形態】
【００５８】
次に、本発明の模範的な実施の形態について、図面を参照して詳細に説明する。
【００５９】
＜第１の実施形態＞
図２１は、本発明の第１の実施形態に係るデータ検索システムの構成を示すブロック図であり、以下に説明する各実施形態およびその変形例に共通する概念を表す。
【００６０】
図２１に示すデータ検索システムは、管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノード（図２１の例では３つのノードＡ、Ｂ、Ｃ）において管理する。そして、このデータ検索システムは、移動対象のターゲットデータの移動に先立って、その移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索する。
【００６１】
ノード（データ検索装置）１００は、保持部（ストレージ部）３００と、転送部（メッセージ転送部）４００とを備える。
【００６２】
第１の識別子（ストレージ識別子（ＳＩＤ））３０１は、自ノードが保持すべきターゲットデータの値域を求めるための情報である。第２の識別子（経路識別子（ＲＩＤ））４０１は、受信したメッセージを他ノードに転送する転送経路の決定に用いる情報である。第３の識別子（データＩＤ（ＤＩＤ））３０２は、ターゲットデータを識別する情報である。
【００６３】
保持部３００は、第３の識別子（データＩＤ（ＤＩＤ））３０２によって特定されるターゲットデータ３０３を保持（格納）する。各ノードが保持するターゲットデータ３０３は、第１の識別子３０１を基に決定した値域に属するデータである。
【００６４】
転送部４００は、第２の識別子４０１が含まれる経路情報（経路表）４０２を用いて、メッセージを転送すべき他ノードを決定する。その際、転送部４００は、第１の識別子３０１、第２の識別子４０１、第３の識別子３０２の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、経路情報４０２を参照する。その結果、転送部４００は、対応する他ノードが存在する場合には、当該他ノードに対して、自ノードが受信した当該メッセージを転送する。
【００６５】
本実施形態に係るデータ検索システムは、上記のように複数種類の識別子を用いて、ターゲットデータを管理している。このような本実施形態によれば、ノード間においてターゲットデータ３０３を管理するに際して、例えばあるノードにおける負荷を分散する必要が生じ、そのノードの第１の識別子３０１を変更したとしても、第１の識別子３０１とは独立している第２の識別子４０１は影響を受けない。即ち、本実施形態において、第２の識別子４０１が含まれる経路表の情報は失効することが無い。よって、本実施形態によれば、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現することができる。
【００６６】
＜第２の実施形態＞
次に、上述した第１の実施形態に係るデータ検索システムを基本とする模範的な第２の実施形態について説明する。以下の説明においては、本実施形態に係る特徴的な部分を中心に説明すると共に、上述した第１の実施形態と同様な構成についての重複する説明は省略する。
【００６７】
本実施形態に係る分散型のデータ検索システムは、コンピュータネットワークに接続された複数のノードによって構成される。このデータ検索システムは、あるノードから他ノードにターゲットデータを、ＤＨＴを用いて配置するシステムである。ここで、配置とは、ノード間におけるターゲットデータの移動、移譲、分配などを表す。このようなシステムでは、ノード間におけるターゲットデータの移動によるネットワーク上の通信トラフィックの発生を抑制する必要がある。本システムは、当該ターゲットデータの移動（配置）に先立って、対象となるノード間においてメッセージの転送（中継）を適宜行うことにより、移動対象のターゲットデータの異動先のノードを、メッセージを用いて探索する。このため、メッセージの情報量は、原則としてターゲットデータの情報量より少ないことが好ましい。
【００６８】
本実施形態において、各ノードは、ネットワークに接続された計算機のＣＰＵが実行するプロセス（ソフトウェアプログラム・モジュール）である。従って、本実施形態において、ネットワークに接続された複数のノードは、ハードウェア資源としての１台の計算機（ＣＰＵ）が、いわゆる仮想マシンとして実現する形態、ノード毎に計算機が割り当てられた形態、並びにそれらを適宜組み合わせた形態などが想定される。
【００６９】
また、本実施形態において、当該各ノードには、自ノードがターゲットデータを保持（格納）するための第１の識別子と、ノード間においてメッセージ転送を行うための第２の識別子とが与えられる。第１の識別子は、第１の実施形態における第１の識別子３０１に相当する。第２の識別子は、第１の実施形態における第２の識別子４０１に相当する。これら２種類の識別子は、同一の識別子空間から得られる値であり、同値である必要はない。本実施形態においても、以下の説明において、係る第１の識別子を“ストレージ識別子（ＳＩＤ）”、係る第２の識別子を“経路識別子（ＲＩＤ）”と称する。
【００７０】
ストレージ識別子（ＳＩＤ）は、各ノードのデータ保持値域を決める値である。本実施形態において、第１ノードが保持するターゲットデータを第２ノードに分散（配置）するに際して、当該第１ノードは、ストレージ識別子の値を変更する。即ち、当該第１ノードのＣＰＵは、自ノードのデータ保持値域を狭める等の処理を契機として、自ノード（第１ノード）に保持されているターゲットデータを、他ノード（第２ノード）に移譲する。これにより、例えば、多くのターゲットデータを処理しており負荷が高かった第１ノードから、比較的負荷が少なかった第２ノードへの負荷分散が実現する。
【００７１】
経路識別子（ＲＩＤ）は、例えば、ターゲットデータを、オーバレイネットワークにおいて検索すべく、メッセージの転送経路を決定するために用いる値である。本実施形態において、各ノードの経路表に保持される経路情報は、ネットワーク上の住所（ＩＰアドレスなど）と、経路識別子とを含む。本実施形態において上記負荷分散は、ストレージ識別子（ＳＩＤ）を用いて実行される。このため、本実施形態において経路識別子（ＲＩＤ）を用いて実行されるメッセージ転送は、上述した関連技術で説明した経路情報の失効などによる悪影響を受けない。
【００７２】
ノードは、メッセージの受信に応じて、検索キーとなる識別子（データＩＤ、ＳＩＤ、あるいはＲＩＤ）を取得する。そして、当該ノードは、自ノードの経路表の中で、当該検索キーまでの距離が最も小さい経路識別子を持つノード（特定ノード）に対して、当該メッセージを転送する。本実施形態において、メッセージには、検索用のキー値のほかに、ノードへの何らかの処理命令（処理要求）が記述されている。
【００７３】
メッセージに含まれる処理命令がターゲットデータの検索要求である場合、上記転送処理が繰り返されることにより、当該メッセージは、やがて、オーバレイネットワークに参加している全てのノードのうち、当該検索キー値までの距離が最も小さい経路識別子を持つノード（特定ノード）にたどり着く。上述したように、当該ノードの経路識別子と、ストレージ識別子とは同値である必要はない。このため、当該ノードは、当該検索キー値が表す識別子に対応する担当ノードであるとは限らない。しかしながら、当該ノードの経路識別子の近くにデータ保持値域が広がっているような他ノードは、当該検索キーによって求めている担当ノードである可能性は高い。そこで本実施形態において、各ノードは、自ノードの経路識別子からの距離が小さいストレージ識別子を持つ他ノードの経路情報も保持する。この経路情報には、少なくとも、当該他ノードのデータ保持値域と、当該他ノードのネットワーク上の住所（アドレス）とが含まれる。このような経路情報群を、以下の説明では、“担当ストレージ表”と称する（詳細は図１１Ａを参照して後述する）。
【００７４】
また、本実施形態では、自ノードの経路識別子から、受信した検索キーまでの距離が他のどのノードよりも十分近い場合、当該自ノードは、担当ストレージ表の中に、当該検索キーの担当ノードの経路情報を必ず持っていなければならない。ターゲットデータの検索要求を含むメッセージを、オーバレイネットワーク外部からあるノードが取得した際、当該メッセージは、経路表に基づき当該オーバレイネットワーク上のノード間において中継される。そして、当該メッセージは、そのメッセージに含まれる検索キーが表す識別子までの距離が最も小さい経路識別子を持つノード（特定ノード）にやがてたどり着く。
【００７５】
当該メッセージを受信したノードは、自ノードの持つ担当ストレージ表を参照することにより、その担当ストレージ表に登録された各ノードのデータ保持値域を参照する。そして当該ノードは、自ノードの担当ノードを探し出して、その担当ノードに対してターゲットデータの検索要求を発行する。
【００７６】
即ち、メッセージ転送がノード間において行われる過程において、当該メッセージが担当ノードにたどり着く最後のメッセージ転送動作を除いて、それ以外の中間ノードを転々とするメッセージ転送動作は、個々の経路表の中の経路識別子を参照することによって行われる。そして、当該メッセージが担当ノードにたどり着く最後のメッセージ転送動作においては、担当ストレージ表を参照することによって行われる。
【００７７】
図１は、本発明の実施形態に係るデータ検索システムの構成を例示するブロック図である。図１に示すデータ検索システムは、ネットワークに接続された複数のノード１、２、３によって構成されている。本実施形態において、個々のノード（データ検索装置１００）は、計算機のＣＰＵにより実行されるプロセス（ソフトウェアプログラム・モジュール）である（詳細は、図９を参照して後述する）。
上述したように、個々のノードは、１台の計算機において複数のノードが仮想マシンとして実行される環境、１台の計算機に１つのノードが割り当てられる環境、或いはそれらの組み合わせの何れであってもよい。
【００７８】
以下の説明では、図１に例示する３つのノードのち、データ検索装置１００としてのノード３を例にノードの構成について説明する。ノード３は、大別して、通信部１０、ストレージ部２０、初期化・終了部３０、そしてメッセージ転送部４０を備える。 ストレージ部２０は、第１の実施形態における保持部（ストレージ部）３００に相当する。そしてメッセージ転送部４０は、第１の実施形態における転送部（メッセージ転送部）４００に相当する。尚、本実施形態において、ノード１、２は、ノード３と同様な構成を備えており、ノード３との通信が可能である。
【００７９】
＜ノード（データ検索装置１００）の構成＞
ノード３（データ検索装置１００）を構成する各部の構成と動作について以下に説明する。
【００８０】
通信部１０は、通信機能１１を備えている。通信機能１１は、ノード３が有する他の機能から、メッセージや、そのメッセージの宛先となる他ノードのネットワーク２００上の住所（アドレス）を与えられる。そしてノード３は、取得したメッセージを、当該住所に対応する他ノードに送信する。また、ノード３は、自ノードが参加しているオーバレイネットワークとは異なる外部のノードや装置、或いは自ノードが所参加しているオーバレイネットワークの他ノードからメッセージを受信する。そしてノード３は、受信したメッセージの内容に応じて、自ノードの適切な部ないし機能に当該メッセージを割り振る。
【００８１】
初期化・終了部３０は、参加機能３１と離脱機能３２とを備える。参加機能３１は、図１に示すネットワーク２００の上位に位置する概念的なオーバレイネットワーク（図１には不図示）に自ノードが参加する際に、ストレージ部２０およびメッセージ転送部４０を初期化する。離脱機能３２は、係るオーバレイネットワークから自ノードが離脱する際に、以下の動作を実行する。
【００８２】
即ち、離脱機能３２は、当該オーバレイネットワークに参加している他の必要なノードに、自ノードの離脱を通知する。また、離脱機能３２は、ストレージ部２０が管理するターゲットデータを、適切な他ノードに移譲する。更に、離脱機能３２は、メッセージ転送部４０がそれまで行っていたメッセージ転送の処理を停止する。また、離脱機能３２は、自ノード外部からのメッセージの受信を停止する。
【００８３】
（ストレージ部２０）
ストレージ部２０は、データアクセス機能２２、ストレージ識別子（ＳＩＤ）決定機能２３、隣接ストレージ維持機能２１、ＳＩＤ情報格納部２６、データ格納部２５、そして隣接ストレージ表２４を備える。
【００８４】
はじめに、ストレージ部２０が上記各機能を実行するに際して読み書きする情報（隣接ストレージ表２４、データ格納部２５、ＳＩＤ情報格納部２６）について説明する。
【００８５】
ＳＩＤ情報格納部２６は、ストレージ識別子と、そのストレージ識別子を基に決定されるデータ保持値域とを格納する。後述するＣｈｏｒｄアルゴリズムを用いた実施例では、あるノードのデータ保持値域は、自ノードのストレージ識別子（ＳＩＤ）の次に小さい他ノードのストレージ識別子から、自ノードのストレージ識別子までを表す値の範囲である。
【００８６】
データ格納部２５は、ノード３（自ノード）が保持するターゲットデータを格納する。本実施形態において、各ノードは、自ノードのデータ保持値域に属するデータＩＤを持つターゲットデータの担当ノードとなり、そのターゲットデータを保持する。ここで、データＩＤは、第１の実施形態における第３の識別子３０２に相当する。また、ターゲットデータは、第１の実施形態におけるターゲットデータ３０３に相当する。
【００８７】
隣接ストレージ表（図１１Ｂ）は、ストレージ識別子の値が自ノードの次に大きい他ノードと、あるいはストレージ識別子の値が自ノードの次に小さい他ノードとに関して、ストレージ識別子とネットワーク上のアドレスとを格納する。以降、このような他ノードを、本実施形態では“隣接ストレージ”と称する。
【００８８】
次に、ストレージ部２０が上記各種情報を読み書きしながら実行するところの、隣接ストレージ維持機能２１、データアクセス機能２２、そしてＳＩＤ決定機能２３について説明する。
【００８９】
データアクセス機能２２は、データ格納部２５に対してターゲットデータの登録や検索、削除を行う機能である。
【００９０】
隣接ストレージ維持機能２１は、隣接ストレージ表（図１１B）を定期的にヘルスチェックし、その結果、失効した経路情報があれば、適宜削除や書き換えを行う。
【００９１】
ＳＩＤ決定機能２３は、自ノードのストレージ識別子（ＳＩＤ）を決定し、決定したストレージ識別子をＳＩＤ情報格納部２６に格納する。決定方法は、ＤＨＴのアルゴリズムや、負荷分散の手順によって異なる。
【００９２】
（メッセージ転送部４０）
メッセージ転送部４０は、ＲＩＤ決定機能４１、ストレージ探索機能４２、経路表維持機能４３、担当ストレージ表維持機能４４、ＲＩＤ情報格納部４５、経路表４６、そして担当ストレージ表４７を備える。
【００９３】
はじめに、メッセージ転送部４０が上記各機能を実行するに際して読み書きする情報（ＲＩＤ情報格納部４５、経路表４６、担当ストレージ表４７）について説明する。
【００９４】
ＲＩＤ情報格納部４５は、経路識別子（ＲＩＤ）と、その経路識別子を基に決定される識別子値域とが格納される。経路識別子の決定方法は、実装態様やアルゴリズムによってさまざま異なるが、上述した関連技術と同様な技術を採用することができる。たとえば、ノード識別子の決定方法として、本実施形態では、ハッシュ関数の出力値を経路識別子として用いるなどの手法を適用可能である。本実施形態における以下の説明では、このような経路識別子の値域を“ストレージ索引値域”と呼ぶ。あるノードのストレージ索引値域は、自ノードの経路識別子（ＲＩＤ）から、最も距離が近い経路識別子を持つ他ノードまでを表す値の範囲である。尚、本実施形態では、同一ノードが格納するストレージ識別子と経路識別子とは、同じ識別子空間に存在するも、同値であるとは限らない。
【００９５】
経路識別子（ＲＩＤ）は、検索キーとなる各種識別子（データＩＤ、ＳＩＤ、あるいはＲＩＤ）を自ノードが受信したとき、次にメッセージを転送する他ノードを選ぶときに使用される。そこで、本実施形態における経路表（４６）には、複数のノードの経路識別子と、ネットワーク上のアドレスとが格納される。本実施形態において、自ノードは、メッセージと共に受け取ったキーの識別子（データ識別子、ＳＩＤ、あるいはＲＩＤ）までの距離が最も近い経路識別子を持つ他ノードを、当該メッセージの次の転送先として当該経路表から選択する（詳細は図１３Ａ乃至図１３Ｃを参照して後述する）。
【００９６】
ノード３の担当ストレージ表（４７）は、ノード３のストレージ索引値域に少なくとも一部が重なるようなデータ保持値域を持つ他ノードの、データ保持値域とネットワーク上のアドレスとを格納する。このため、自ノードのストレージ索引値域に検索キーの値が属するということは、担当ストレージ表に登録された複数のノード群において、いずれか一つのノードのデータ保持値域に検索キーが属することを表す。すなわち、受信したメッセージに含まれる検索キーが自ノードのストレージ索引値域に属するとき、自ノードは、担当ストレージ表の中に、当該検索キーに対応する担当ノードへの経路情報を必ず持っている。
【００９７】
次に、メッセージ転送部４０が上記各種情報を読み書きしながら実行するところの、ＲＩＤ決定機能４１、ストレージ探索機能４２、経路表維持機能４３、そして担当ストレージ表維持機能４４について説明する。
【００９８】
ストレージ探索機能４２は、検索キーを受け取ると、経路表４６および担当ストレージ表４７から適切なノードを探索し、探索によって見つけたノードへ当該検索キーを転送する。
【００９９】
経路表維持機能４３は、経路表４６のヘルスチェックを行い、その結果、失効した情報が見つかれば適宜削除や書き換えを行う。
【０１００】
担当ストレージ表維持機能４４は、担当ストレージ表４７のヘルスチェックを行い、その結果、失効した情報が見つかれば適宜削除や書き換えを行う。
【０１０１】
ＲＩＤ決定機能４１は、自ノードの経路識別子（ＲＩＤ）を決定すると共に、決定した経路識別子をＲＩＤ情報格納部に格納する。経路識別子の決定方法は、ＤＨＴのアルゴリズムや、どのような方針で各ノードにメッセージ転送を実行するかに依る。
【０１０２】
図１０は、本発明の第２の実施形態に係るデータ検索システムを、Ｃｈｏｒｄアルゴリズムに適用した動作例を説明する図である。図１０に示す例は、同一の識別子空間に、５つのノードａ〜ｅが存在している状態を表している。即ち、円環ａには、各ノードに分散配置されているターゲットデータの識別子（データＩＤ：ＤＩＤ）と、各ノードのストレージ識別子（ＳＩＤ）の値とが例示されている。一方、円環ｂには、当該各ノードの経路識別子（ＲＩＤ）の値が示されている。円環ａと円環ｂとは、同一の識別子空間を表わす。但し、図示と理解の利便性を考慮して、本実施形態では、データＩＤ（ＤＩＤ）およびストレージ識別子（ＳＩＤ）の分布の様子と、経路識別子（ＲＩＤ）の分布の様子とを、図１０に示す如く２つの円環に分けて表している。
【０１０３】
表２は、本実施形態において図１０に示す各ノードのデータ保持値域を例示する。また、表３は、本実施形態において図１０に示す各ノードのストレージ索引値域を例示する。図１０において、夫々のノードのストレージ識別子（ＳＩＤ）と経路識別子（ＲＩＤ）は、たまたま同じ値である例を示している。但し、Ｃｈｏｒｄでは、「背景技術」欄において説明したように、距離の定義が非対称である。このため、ラベルを付した夫々のノードについて表２及び表３を参照すると、これらの表において、データ保持値域とストレージ索引値域とは一致していないことが判る。そして、図１に示す各ノード内のＲＩＤ情報格納部４５には、表２に示すデータ保持領域のうち、ラベル（ノード名）に対応した情報が格納される。また、図１に示す各ノード内のＳＩＤ情報格納部２６には、表３に示すストレージ索引値域のうち、ラベル（ノード名）に対応した情報が格納される。尚、説明の便宜上、表２及び表３には、各ノードの値域をテーブル状にまとめて表現したが、実際の値域は、対応するノードが個別に有する。
【０１０４】
【表２】
【０１０５】
【表３】
【０１０６】
図１１Ａは、図１０における各ノードの担当ストレージ表を示す図である。担当ストレージ表で保持する経路情報（ＲＩＤ）は、ノードのデータ保持値域と住所のみで必要十分である。但し、同図に示す例では、説明の便宜上から、更にノードのラベル及びストレージ識別子（ＳＩＤ）を含む。
【０１０７】
図１１Ｂは、図１０における各ノードの隣接ストレージ表を示す図である。図１０に示す例では、各ノードの経路識別子は、図３に示すノード識別子と同値である。このため、図１０に示す各ノードの経路表は、図５（ａ）乃至図５（ｅ）に示した内容と同じである。ただし、ここではストレージ識別子に注目しているので、図５（ａ）乃至図５（ｅ）に示す表中のＮＩＤを、本実施形態においてはＲＩＤと見なして説明する。また、各ノードのストレージ識別子（およびデータ保持値域）も、図３に示した例におけるノードの識別子（データ保持値域）と同じ値であり、且つデータの分布の様子も同じである。このため、各ノードがデータ格納部に格納するデータは、図４（ａ）乃至図４（ｅ）に示す場合と同じであることとする。
【０１０８】
次に、上述した各機能を備えるデータ検索システム（図１）において、各ノードが実行する具体的な動作について詳細に説明する。以下の説明では、本実施形態に係るデータ検索システムの主要な動作（処理）として、（１）ターゲットデータを探索する動作、（２）オーバレイネットワークに新たにノードが参加する動作、（３）ネットワークからノードが離脱する動作、（４）ノード間における負荷分散動作、そして（５）経路識別子の変更動作、について順に説明する。また、以下の説明では、説明の便宜上から、図１に示すノード３が自ノードであると想定して説明する。
【０１０９】
＜ターゲットデータの探索動作＞
まず、ターゲットデータの探索動作について、図１５に示すフローチャートを参照して説明する。
【０１１０】
図１５は、本発明の第２の実施形態に係るデータ検索装置が実行するターゲットデータの探索処理を示すフローチャートである。図１５に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１１１】
ノード３（自ノード）は、検索キー（データ識別子）を含むメッセージを外部装置などから受け取るのに応じて、その検索キーが自ノードのデータ保持値域に属するか否かを、ＳＩＤ情報格納部２６を参照することによって判断する（ステップＳ１０１）。この判断において自ノードのデータ保持値域に当該検索キーが属すると判断した場合（ステップＳ１０１にてＹＥＳ）、ノード３は、その検索キーの担当ノードである。そこでノード３は、当該検索キーを利用して、自ノードのデータ格納部２５を探索（探索）する。そして、ノード３は、当該検索キーと一致するデータＩＤを持つターゲットデータがデータ格納部２５に格納されていると判断した場合、そのターゲットデータを、当該メッセージの送信元へ送る（ステップＳ１０５）。
【０１１２】
一方、自ノードのデータ保持値域に当該検索キーが属さないと判断した場合（ステップＳ１０１にてＮＯ）、ノード３は、当該検索キーが自ノードのストレージ索引値域に属するか否かを、ＲＩＤ情報格納部４５を参照することによって判断する（ステップＳ１０２）。この判断において自ノードのストレージ索引値域に当該検索キーが属さないと判断した場合（ステップＳ１０２にてＮＯ）、ノード３は、経路表（図５，４６）を参照することにより、当該検索キーまでの距離が最も近い経路識別子（ＲＩＤ）を持つ他ノードを選択し、選択した他ノードに当該メッセージを転送する（ステップＳ１０３）。
【０１１３】
これに対して、当該検索キーがストレージ索引値域に属すると判断された場合（ステップＳ１０２にてＹＥＳ）、担当ストレージ表（図１１Ａ）に登録された何れかの他ノードが、当該検索キーの担当ノードである。この場合、ノード３は、データ保持値域に当該検索キーが属する他ノードを、担当ストレージ表（図１１Ａ）の中から選択し、選択した他ノードに対して当該メッセージを転送する（ステップＳ１０４）。
【０１１４】
ここで、上述したターゲットデータの探索動作の、より具体的な動作例を、図５及び図１０を参照して説明する。今、ノードｃに、ネットワークの外部から、データＩＤ＝３のターゲットデータの検索要求メッセージが送られてきたとする（図１０に示す動作＜１＞）。ノードｃは、自ノードのＳＩＤ情報格納部２６（表２）を参照することによって、自ノードのデータ保持値域（２８、５６］を判断する。この例の場合、ノードｃは、係る判断の結果、自ノードがデータＩＤ３の担当ノードではないと判断する。次にノードｃは、自ノードのＲＩＤ情報格納部４５を参照することによって、自ノードのストレージ索引値域（表３）を判断する。この例の場合、ノードｃは、データＩＤ＝３が自ノードのストレージ索引値域（５６、６４］に属していないと判断する。そしてこの例の場合、ノードｃは、経路表４６（図５（ｃ））の中から、データＩＤ（ＤＩＤ）＝３までの距離が最も近い経路識別子１２１を持つノードｅを選択し、選択したノードｅに対して、当該メッセージを転送する（図１０に示す動作＜２＞）。尚、この説明においてもストレージ識別子に注目しているので、上述したように、図５（ａ）乃至図５（ｅ）に示す表中のＮＩＤは、本実施形態においてはＲＩＤと見なした説明である。
【０１１５】
ノードｅも上述したノードｃと同様な動作を実行する。即ち、ノードｅは、識別子３が自ノードのデータ保持値域（６４、１２１］およびストレージ索引値域（１２１、２］に属していないことを、ＳＩＤ情報格納部２６及びＲＩＤ情報格納部４５を参照することによって確認する。そして、ノードｅは、経路表４６（図５（ｅ））の中から、識別子３までの距離が最も近い経路識別子２に対応するノードａを選択し、選択したノードａに対して、当該メッセージを転送する（図１０に示す動作＜３＞）。
【０１１６】
そして、ノードａも上述したノードｃ及びｅと同様な動作を実行する。即ち、ノードａは、データＩＤ３がデータ保持値域（１２１、２］には属しておらず、ストレージ保持値域（２、２８］には属していると判断する。そこでノードａは、自ノードの担当ストレージ表４７（図１１Ａ（ａ））を参照することにより、データ保持値域にデータＩＤ３が属するノードｂを選択する。そしてノードａは、ノードｃがデータＩＤ３のターゲットデータを探していることを、ノードｂへ伝える（図１０に示す動作＜４＞）。ノードｂは、データ格納部２５からデータＩＤ３に対応するターゲットデータを読み出し、読み出したターゲットデータをノードｃへ送信する（図１０に示す動作＜５＞）。
【０１１７】
＜オーバレイネットワークへの参加動作＞
次に、オーバレイネットワークへのノードの参加動作について、図１６のフローチャートを参照して詳細に説明する。
【０１１８】
図１６は、本発明の第２の実施形態に係るデータ検索装置が実行するオーバレイネットワークへの参加処理を示すフローチャートである。図１６に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１１９】
ノード３（自ノード）は、まず、図１を参照して上述したＳＩＤ決定機能２３およびＲＩＤ決定機能４１により、ストレージ識別子（ＳＩＤ）および経路識別子（ＲＩＤ）を決定する（ステップＳ２０１）。つぎに、ノード３は、決定した経路識別子を検索キーとし、その検索キーから、あるいは検索キーまでの距離が最も近い経路識別子を持つ他ノードＸを探索する。係る条件を満たすノードが複数ある場合は、すべて探索する。そしてノード３は、探索した条件に合致する全ての他ノードＸから、他ノードＸの経路情報（経路識別子とネットワーク上のアドレス）を受け取り、自ノードの経路表４６に、他ノードＸの経路情報を登録する（ステップＳ２０２）。ノード３は、登録した他ノードＸの経路識別子を基に自ノードのストレージ索引値域を算出すると共に、算出したストレージ索引値域を、ＲＩＤ情報格納部４５に格納する（ステップＳ２０３）。
【０１２０】
さらに、ノード３は、自ノードの経路表４６に登録された他ノードの担当ストレージ表から、自ノードの担当ストレージ表に保持すべき経路情報を取得する。また、ノード３は、自ノードのストレージ識別子を検索キーに用いて、検索キーから、あるいは検索キーまでの距離が最も近いストレージ識別子を持つ他ノード（隣接ストレージ）を探索する。そしてノード３と当該隣接ストレージとは、互いの経路情報を、互いの隣接ストレージ表（図１１Ｂ）に登録する（ステップＳ２０４）。ノード３は、これら取得した隣接ストレージのストレージ識別子を基に、自ノードのデータ保持値域を算出し、ＳＩＤ情報格納部２６に格納する。
【０１２１】
また、ネットワークに新たに参加したノード３は、自ノードの経路情報を、適切な他ノードの担当ストレージ表に登録するよう、適切な他ノードに対して登録命令を発行する（ステップＳ２０５）。ここで、ノード３を担当ストレージ表に登録するべき適切な他ノードとは、先述の通り、ノード３のデータ保持値域と少なくとも一部が重なり合うようなストレージ索引値域を持つノードである。この動作は、担当ストレージ表の書き換え動作（図１７）として詳しく後述する。
【０１２２】
最後に、ノード３は、隣接ストレージ表に登録された他ノードのデータ格納部から、保持すべきデータを取得する（ステップＳ２０６）。
【０１２３】
ここで、担当ストレージ表の書き換え動作について、図１７に示すフローチャートを参照して説明する。
【０１２４】
図１７は、本発明の第２の実施形態に係るデータ検索装置が実行する担当ストレージ表の書き換え処理を示すフローチャートである。図１７に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１２５】
ステップＳ３０１：まず、登録命令（メッセージ）を出したいノード３は、自ノードのデータ保持値域の下限値を検索キーとし、その検索キーまでの距離が最も近い経路識別子を持つ他ノードを探索する。係る他ノードは、すなわち、ストレージ索引値域に検索キーが属する他ノードである。これは、ノード３のデータ保持値域と、当該他ノードのストレージ索引値域とが、少なくとも一部において重なっていることを意味する。このため、当該他ノードは、自ノードの担当ストレージ表に、ノード３の経路情報を登録すべきである。係る他ノードを発見したノード３は、すぐさま係る他ノードと通信を行い、ノード３の経路情報（ここではデータ保持値域とネットワーク上のアドレス）を、登録メッセージと共に送信する。
【０１２６】
ステップＳ３０２：メッセージを受信した当該他ノードは、自ノードの担当ストレージ表に、ノード３の経路情報を登録する。
【０１２７】
ステップＳ３０３：さらに、係る他ノードは、メッセージに含まれているノード３のデータ保持値域の上限値が、当該他ノード自身のストレージ索引値域に属しているかどうか確認する。当該上限値が係る他ノードのストレージ索引値域に属している場合（ステップＳ３０３にてＹＥＳ）、担当ストレージ表の書き換え動作は、終了である。一方、当該上限値が係る他ノードのストレージ索引値域に属していない場合（ステップＳ３０３にてＮＯ）は、係る他ノードは、自ノードのストレージ索引値域の上限値を経路識別子とする別の他ノードに対して、登録命令（メッセージ）を転送する。尚、ステップＳ３０３は、自ノードが上記他ノードとして動作する場合を想定して同一のフローチャートに記載した。
【０１２８】
ここで、オーバレイネットワークに新たなノードｆが参加するときの具体的な動作の流れについて、図５、図１３Ａから図１３Ｃ、図１４、図１６、図１７、並びに表４、表５を参照して説明する。
【０１２９】
【表４】
【０１３０】
【表５】
【０１３１】
図１３Ａから図１３Ｃは、本発明の第２の実施形態に係るデータ検索システムにおいて、オーバレイネットワークに新たなノードが参加する動作を説明する図である。図１４は、図１３Ａから図１３Ｃに示すオーバレイネットワークへの参加動作において各ノードが参照する担当ストレージ表を例示する図である。
【０１３２】
ノードｆは、オーバレイネットワークに新たに参加を希望しているノードである。まず、ノードｆは、ＳＩＤ決定機能２３及びＲＩＤ決定機能４１により、自ノードのストレージ識別子を９３（ＳＩＤ＝９３）、経路識別子の値を１５（ＲＩＤ＝１５）と決定する（図１６のステップＳ２０１）。本実施形態に係るデータ検索システムにおける前提として、新たに参加するノードは、既にオーバレイネットワークに参加している各ノードのうち、任意のあるノードの住所（ＩＰアドレスなど）を認識している。以下に説明する具体例では、ノードｆは、ノードａの住所を知っていることとする。また、ここでは、自ノードが持つ経路識別子の次に大きい経路識別子を持つ他ノードを、自ノードのサクセッサとする。
【０１３３】
ノードｆは、まず、自ノードの経路表４６に、必要最低限の経路情報として、自ノードのサクセッサを登録する処理を行う（図１６のステップＳ２０２）。サクセッサを探すため、ノードｆは、自ノードの経路識別子の値１５を検索キーとし、その検索キーを用いて、当該値１５から最も距離が近い経路識別子を持つノードを探すよう、ノードａに命令を送信する（図１３Ａに示す動作＜１＞）。ノードａは、自ノードの経路表（図５（ａ））を参照することにより、経路識別子の値が１５から最も近い経路識別子を持つノードｂを選択する。ここで、ノードｂは、ノードａのサクセッサである。従って、ノードａは、ノードｂ以上には経路識別子の値１５から近い距離に存在するノードが他に存在しないことを認識する。
【０１３４】
そして、ノードａは、ノードｆがネットワークへの参加手続きを希望していることをノードｂに伝える（図１３Ａに示す動作＜２＞）。知らせを受けたノードｂは、ノードｆと通信し、ノードｂの経路情報（ここでは経路識別子とネットワーク上のアドレス）を送信する（図１３Ａに示す動作＜３＞）。ノードｆは、受け取った経路情報を経路表に登録する。また、ノードａは、上記の一連の処理から、ノードｆが自ノードの新たなサクセッサになったことを認識することができるので、ノードｆの経路情報を、自ノードの経路表に登録する。
【０１３５】
次に、ノードｆは、自ノードの担当ストレージ表に、適切な経路情報を登録する処理を行う（図１６のステップＳ２０３）。ノードｆのストレージ索引値域（表５）は、それまでノードａのストレージ索引値域であった値域の一部である。すなわち、ノードｆは、ノードａの担当ストレージ表に登録されている経路情報の適切な一部を、ノードｆが管理すべき経路情報として受け取れば十分である。そこで、ノードｆはノードａと通信を行い、ノードａの担当ストレージ表に登録されている経路情報の中から、ノードｆのストレージ索引値域と重なるようなデータ保持値域（表４）を持つノードの経路情報を、ノードａから受け取り、ノードｆの担当ストレージ表に登録する。
【０１３６】
さらに、ノードｆは、隣接ストレージ表２４に自ノードの隣接ストレージの経路情報（ここではストレージ識別子とネットワーク上のアドレス）を登録する処理を行う（図１６のステップＳ２０４）。隣接ストレージを探すため、ノードｆは、自ノードのストレージ識別子の値９３を検索キーに用いて、値９３からの距離が最も近いストレージ識別子を持つノード（すなわち隣接ストレージ）を探索するメッセージを、ノードａに送信する（図１３Ｂに示す動作＜４＞）。これまでと同様、メッセージを受け取ったノードａは、自ノードの経路表４６を用いてメッセージを真の宛先までリレーしていく。この例では、当該メッセージは、図１３Ｂに示す動作＜５＞及び動作＜６＞のように転送され、最後にノードｄへたどり着く。ノードｄは、自ノードの経路表に登録された他ノードおよび自ノード自身の経路識別子と、検索キー９３とを夫々比較して、自ノードの経路識別子から検索キー９３までの距離が、もっとも最短であることを認識する。ノードｄは、担当ストレージ表の中に、ノードｆの隣接ストレージとなるべき他ノードへの経路情報を保持していることになる。
【０１３７】
そこで、ノードｄは、自ノードの担当ストレージ表（図１３Ｄに示す（ｄ））を参照することにより、検索キー９３が属するようなストレージ索引値域を持つ他ノード（ここではノードｅ）を探す。そして、ノードｄは、ノードｅに対して、ノードｆが隣接ストレージを探していることをメッセージによって伝える（図１３Ｂに示す動作＜７＞）。このメッセージを受けたノードｅは、ノードｆと通信を行い、互いの経路情報（ここではストレージ識別子とネットワーク上のアドレス）を、互いの隣接ストレージ表に登録する（図１３Ｂに示す動作＜８＞）。
【０１３８】
また、ノードｆは、自ノードの経路情報を、適切な他ノードの担当ストレージ表に登録してもらう処理を行う（図１６のステップＳ２０５）。図１７のステップＳ３０１に従い、ノードｆは、表４を参照することにより、自ノードのデータ保持値域の下限値（データ保持値域に属する最小の値）６５を検索キーとし、検索キーまでの距離が最も近い経路識別子を持つ他ノードを探すため、経路表を用いて検索キーを含むメッセージを転送する。現在、ノードｆの経路表には唯一ノードｂが登録されているので、メッセージはノードｂへ転送される（図１３Ｂに示す動作＜９＞）。メッセージを受け取ったノードｂは、当該メッセージに含まれる検索キー値６５までの距離が最も近い経路識別子を持つ他ノードを、ノードｂ自身および経路表の中から選択する。まだいずれのノードにおいても経路表のヘルスチェックが行われていないと仮定すると、ノードｂは、図５（ｂ）に示す経路表からノードｄを選び、メッセージを転送する。ノードｄは、自ノード自身および経路表の中から、検索キー６５までの距離が最も近い経路識別子を持つノードｄを選択することで、自ノードが最も検索キー６５までの距離が近いと判断する。そして、ノードｄは、ノードｆと通信し、自ノードがノードｆの探しているノードであることを教える。
【０１３９】
ノードｆは、ノードｄへ、自ノードのデータ保持値域とともに、登録命令の書かれたメッセージを送信する。メッセージを受信したノードｄは、共に受け取ったノードｆのデータ保持値域とネットワーク上のアドレスを経路情報として、ノードｄの担当ストレージ表に登録する（図１７のステップＳ３０２）。
【０１４０】
さらに、図１７のステップＳ３０３に従い、ノードｄは、ノードｆのデータ保持値域の上限値９３が、ノードｄのストレージ索引値域に属しているか判定する。この判定は真であるため、図１７に従い、適切なノードの担当ストレージ表への登録（書き換え）処理は終了する。
【０１４１】
最後に、図１６のステップＳ２０６に従い、ノードｆは、自ノードの隣接ストレージであるノードｅから、自ノードが保持すべきターゲットデータ（ＩＤ＝６４〜８２）を受け取る。このような一連の動作を経て、ノードｆは、オーバレイネットワークに新たに参加することにより、図１３Ｃに示す状態が実現する。
【０１４２】
＜ネットワークからの離脱動作＞
次に、ノードがネットワークから離脱する動作について、図１８に示すフローチャートを参照して説明する。
【０１４３】
図１８は、本発明の第２の実施形態に係るデータ検索装置が実行するネットワークからの離脱処理を示すフローチャートである。図１８に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１４４】
離脱対象のノードは、まず保持しているターゲットデータを、隣接ストレージ表（図１１Ｂ）に登録されている隣接ストレージへ移譲する（ステップＳ４０１）。次に、離脱対象のノードは、自ノードのストレージ索引値域の下限値及び上限値を、ＳＩＤ情報格納部２６から参照し、その下限値あるいは上限値を経路識別子に持つ他ノードを探索する。そして、離脱対象のノードは、自ノードの担当ストレージ表（図１１Ａ）に登録されている経路情報を、探索によって求めた当該他ノードに移譲する（ステップＳ４０２）。そして、当該離脱対象のノードは、ネットワークから離脱する（ステップＳ４０３）。尚、離脱対象のノードの指定は、例えば、ノードへ離脱を命令できる権限のあるユーザが、当該ノードへ離脱の命令が書かれたメッセージを送信するなどによって行えば良い。
【０１４５】
＜負荷分散動作＞
次に、ネットワークに参加しているノード間において負荷を分散する負荷分散動作について、図１９に示すフローチャートを参照して説明する。
【０１４６】
図１９は、本発明の第２の実施形態に係るデータ検索装置が実行する負荷分散処理を示すフローチャートである。図１９に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１４７】
ノードは、何らかの手段により自ノードの負荷が高いと判断すると（ステップＳ５０１にてＮＯ）、図１を参照して上述したＳＩＤ決定機能２３により、新たなストレージ識別子およびデータ保持値域を決定する（ステップＳ５０２）。
【０１４８】
上記の決定によってストレージ識別子を変更したため、自ノードの隣接ストレージは、決定前と異なっている可能性がある。そこで当該ノードは、係る新たなストレージ識別子を用いて、隣接ストレージ表（図１１Ｂ）の経路情報（ここではストレージ識別子とネットワーク上のアドレス）のヘルスチェックを行う（ステップＳ５０３）。その結果、自ノードの新たなストレージ識別子に対して、現在登録されている他ノードがもはや隣接ストレージの条件を満たさないと判定した場合、当該自ノードは、当該他ノードを隣接ストレージ表から削除する（ステップＳ５０３）。
【０１４９】
さらに自ノードは、新たなストレージ識別子を検索キーとして含むメッセージを発行することで、検索キーと数値的に隣り合うストレージ識別子を持つ他ノードを新たな隣接ストレージとして探索し、探索結果を隣接ストレージ表に登録する。次に、当該自ノードは、負荷分散に応じてデータ保持値域が変わるので、必要な全ての他ノードに対して、担当ストレージ表の書き換えを行わせる必要がある。そこで、図１７に示す、担当ストレージ表の書き換え動作のフローチャートに従い、当該ノードは、新たなデータ保持値域に基づき、保持すべきデータは保持し、他ノードへ移譲すべきノードは移譲する（ステップＳ５０４）。
【０１５０】
更に当該ノードは、変更したデータ保持値域の下限値を検索キーとし、その検索キーまでの距離が最も近い経路識別子を持つ他ノードを探索する。当該ノードは、探索した他ノードへ、自ノードのデータ保持値域の情報と共に、担当ストレージ表（図１１Ａ）への登録命令を送信する（ステップＳ５０５）。
【０１５１】
ここで、上述した負荷分散動作について、より具体的に説明する。本実施形態において例示しているノードｅは、図４等を参照して上述したように、保持しているターゲットデータ数が他のノードに比べて多いので負荷が高い。そこで、以下の具体例では、インターバルシフトによる負荷分散について説明する。
【０１５２】
図１２は、本発明の第２の実施形態に係るデータ検索システムにおいて、高負荷な状態にあるノードｅから負荷分散を行うときの動作の流れを説明する図である。はじめに、ノードｅは、隣接ストレージ表（図１１Ｂに示す（ｅ））に登録された他ノード（隣接ストレージ）と通信を行い、ターゲットデータの譲渡先となるノード（ここではノードａとする）を、どの隣接ストレージにするか決める。ここで、隣接ストレージの決定方法としては、様々な方法が考えられる。例えば、ノード識別子を変更することで負荷分散を行う関連技術を採用すると共に、負荷の高いノードがターゲットデータの移譲先を決定する方法を採用することができる。
【０１５３】
ノードｅは、ノードａにターゲットデータを譲渡すべく、ストレージ識別子（ＳＩＤ）の値を９３に、データ保持値域を（６４、９３］に、それぞれ変更する（図１２に示す円環ａ）。次に、ノードｅは、ノードａへ、ストレージ識別子を９３に変更したことを伝える。これに応じてノードａは、自ノードのデータ保持値域を、当初の（１２１、２］（表２）から、（９３、２］に広げる変更を行う。これによりノードａは、当初はノードｅが保持していたデータ識別子１０３〜１１９のターゲットデータ（図４（ｅ））を、ノードｅから受け取る。
【０１５４】
ノードｅおよびノードａは、夫々のデータ保持値域を変更したため、適切な他ノードに対して、担当ストレージ表の書き換えを依頼する必要がある。そこで、ノードｅは、図１７に示すフローチャートに従い、担当ストレージ表の書き換え処理を実行する。即ち、ノードｅは、新たなデータ保持値域（６４、９３］の下限（最小値）６５を検索キーとし、値６５をストレージ索引値域に含むようなノードを探索する。そしてノードｅは、探索により求めた他ノードに対して、自ノードのデータ保持値域の情報と共に、担当ストレージ表の書き換え命令をメッセージとして送信する。
【０１５５】
経路表（図５）を用いて当該キーまでの距離が最も近づくようにメッセージ転送を行えば、メッセージは、図１２に示す動作＜１＞のように、ノードｄに転送される。ノードｄは、検索キー値６５が自ノードのストレージ索引値域（６４、１２１］に含まれている（表３）。このためノードｄは、自ノードの担当ストレージ表（図１１Ａ）の中の、ノードｅの経路情報を書き換える。
【０１５６】
上述した具体例におけるノードｅの変更後のデータ保持値域（６４、９３］の上限９３は、ノードｄの変更後のストレージ索引値域（６４、１２１］に属している。このため、ノードｄは、メッセージをそれ以上他ノードに転送する必要がない。
【０１５７】
一方、ノードａもまた、変更が生じた自ノードのデータ保持値域(９３、２]の下限（最小値）９４を検索キーに用いて、値９４をストレージ索引値域に含むノードを探し、自ノードのデータ保持値域の情報と共に、担当ストレージ表の書き換え命令をメッセージとして送信する。
【０１５８】
経路表（図５）を用いて当該検索キーまでの距離が最も近づくようにメッセージ転送を行えば、メッセージは、図１２に示す動作＜２＞及び動作＜３＞のように転送され、ノードｄに辿り着く。ノードｄは、自ノードの担当ストレージ表のノードａの情報を書き換える。さらに、ノードａのデータ保持値域の上限値２は、ノードｄのストレージ索引値域（６４、１２１］に属していない（表３）。このためノードｄは、メッセージを、ストレージ索引値域の上限の担当ノード（すなわち、Ｃｈｏｒｄでは自ノードのサクセッサ）であるノードｅに転送する（図１２に示す動作＜４＞）。ノードｅは、メッセージに従い、自ノードの担当ストレージ表を書き換える。ノードａのデータ保持値域の上限値２は、ノードｅのストレージ索引値域（１２１、２］に属しているので、ノードｅはメッセージを転送する必要がない。
【０１５９】
＜経路識別子の変更動作＞
ところで、経路表（４６）に登録された経路情報の数を減らしたい、或いはノード間でできるだけ経路表の大きさを均一にしたい、などの目的で、経路識別子を変更したい場合がある。本実施形態における経路識別子の変更は、図２０に示すフローチャートのように動作する。
【０１６０】
図２０は、本発明の第２の実施形態に係るデータ検索装置が実行する経路識別子の変更処理を示すフローチャートである。図２０に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１６１】
ステップＳ６０１：まず、経路識別子を変更したいノードは、自ノードの経路識別子の値を変更する。
【０１６２】
ステップＳ６０２：次に、変更した経路識別子を検索キーに用いて、当該ノードは、当該変更後の経路識別子から（まで）の距離が最も近い経路識別子を持つ他ノードを探索する。そして、当該ノードは、探索によって見つけた他ノードに応じて、経路表に必要な情報を登録する。
【０１６３】
ステップＳ６０３：さらに、当該自ノードは、経路表に登録された他ノードから、ストレージ索引値域を算出する。自ノードは、新たに算出されたストレージ索引値域と重なりあうデータ保持値域を持つ他ノードを、担当ストレージ表に登録する必要がある。担当ストレージ表に登録すべき経路情報は、自ノードの経路識別子と数値的に隣り合う他ノード（すなわち、先ほど経路表に登録した他ノード）が保持しているため、当該他ノードから係る経路情報を取得する。
【０１６４】
＜ハードウェア構成＞
次に、第１及び第２の実施形態において上述したデータ検索装置（ノード）が実行されるハードウェア環境について、図９を参照して説明する。上述したように、各実施形態において説明したデータ検索装置（ノード）は、サーバなどのコンピュータによって実行されるプロセスとして捉えることができる。係るデータ検索装置の機能は、ソフトウェアプログラムを、コンピュータのＣＰＵが実行することによって実現される。そして、上述した各実施形態において図面に示した各機能は、ソフトウェアプログラムの機能単位（ソフトウェアモジュール）と捉えることができる。この場合のハードウェア環境の一例を、図９を参照して説明する。
【０１６５】
図９は、本発明の第１及び第２の実施形態に係るデータ検索装置のハードウェア構成を例示的に説明する図である。図９に示したハードウェアは、ＣＰＵ１０１、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）１０２、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１０３、ハードディスク（記憶装置）１０４、通信インタフェース１０５を備え、これらの構成がバス１０６を介して接続された一般的なコンピュータである。通信インタフェース（Ｉ／Ｆ）１０５は、図１に示した通信部１０に対応しており、ネットワーク２００を介して、自装置（自ノード）と外部装置（他ノードなど）との通信を実現する。ここで、ハードディスク１０４は、上述した図１に示す隣接ストレージ表２４、データ格納部２５、ＳＩＤ情報格納部２６、ＲＩＤ情報格納部４５、経路表４６、及び担当ストレージ表４７を実現する記憶装置として機能する。
【０１６６】
そして、上述した各実施形態を例に説明したデータ検索装置１００（ノード）は、図９に示したハードウェアに対して、その説明において参照したブロック構成図（図１、図２１）或いはフローチャート（図１５乃至図２０）の機能を実現可能なコンピュータプログラムを供給した後、そのコンピュータプログラムを、当該ハードウェアのＣＰＵ１０１に読み出して実行することによって達成される。また、当該装置内に供給されたコンピュータプログラムは、読み書き可能なメモリ（１０３）またはハードディスク装置（１０４）等の記憶デバイスに格納すれば良い。
【０１６７】
尚、上記の例では、説明の便宜上から、１台のコンピュータが１つのノード（データ検索装置）を実現する構成を説明したがこの構成には限られない。即ち、上述した各実施形態を例に説明したデータ検索装置１００（ノード）は、１台のコンピュータが複数の仮想マシンを実現する構成を実行環境として、当該１台のコンピュータが複数のノード（プロセス）を実現する構成であってもよい（尚、仮想マシンを利用する場合については後述する実施例にて詳述する）。但し、データ検索装置１００は、専用のハードウェアによって実現してもよい。
【０１６８】
また、前記の場合において、当該ハードウェア内へのコンピュータプログラムの供給方法は、ＣＤ−ＲＯＭ等の各種記録媒体を介して当該装置内にインストールする方法や、インターネット等の通信回線を介して外部よりダウンロードする方法等のように、現在では一般的な手順を採用することができる。そして、このような場合において、本発明は、係るコンピュータプログラムのコード或いは記憶媒体によって構成される。
【０１６９】
＜実施形態の効果＞
以上説明した第１及び第２の実施形態に係るデータ検索装置（ノード）及びそれらが複数接続されたデータ検索システムによれば、ノード間においてターゲットデータを管理するに際して、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現することができる。
【０１７０】
即ち、本実施形態では、例えばあるノードにおける負荷を分散する必要が生じ、そのノードのストレージ識別子（ＳＩＤ）を変更したとしても、経路表の情報が失効することが無いので、安定したメッセージ転送が実現する。
【０１７１】
また、本実施形態によれば、経路識別子（ＲＩＤ）を変更することも可能である。即ち、メッセージの中継ノードに選ばれる確率にノード間において大きな差があり、これに応じてノードのリソースに無駄が生じている場合がある。このような場合、本実施形態によれば、各ノードの経路識別子を、識別子空間上において可能な限り分散するように割り当て直すことにより、当該確率を、ノード間で均一にすることができる。これに対して、「発明の背景」欄で説明した関連技術では、各ノードが一つの識別子のみを用いてターゲットデータの保持とメッセージ転送とを実行するため、負荷の観点から困難であった。換言すれば、ノード間において、メッセージ転送を全く行わないノードは、リソースを持て余してしまうので、そのようなノードは無くすることが求められる。この要求に対して、関連技術では、ヘテロな環境であればあるほど、負荷を分散すると、データ保持値域の広さがノード間でバラついてしまい、結果として、識別子空間上で複数のノードが極端に近い場所に密集する状況が生じる。この場合、密集したノード群には、確率的に、メッセージがほとんど転送されることはない。このような問題を解消する観点からは、メッセージ転送の際に参照する識別子は、ノード間において均等に離散していることが望ましい。この関係は、上述した関連技術においては、ヘテロな環境において負荷分散とトレードオフの関係であった。これに対して、本実施形態によれば、２種類の識別子（ＲＩＤ，ＲＩＤ）を用いて、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現する訳である。
【実施例】
【０１７２】
上述した実施形態では、負荷分散の１つのアプローチとして、インターバルシフトを用いた。しかしながら、上述した実施形態を例に説明した本発明は、識別子の値を変更することで負荷の分散を図る各種のアプローチに有効である。このため、本発明に係るデータ検索システムは、仮想サーバ、仮想ノード等と呼ばれる仮想マシン（仮想マシン環境）にも適用可能である。
【０１７３】
ここで、仮想マシン環境に本発明を適用した場合について説明する。この場合、既にオーバレイネットワークに参加しているノードのうち、リソースに余裕のあるノードを実現しているＣＰＵは、負荷を分散すべく、新たなプロセスを実行することによって別ノードを作り、当該別ノードをオーバレイネットワークに参加させる。但し、仮想マシンでは、一般に、１つのＣＰＵが複数のノードを実現するため、メッセージがノード間を中継される際に、実際は同じ計算機（物理マシン）の中で何度も中継されるという問題がある。このような問題が生じる仮想マシン環境に対して、本発明に係るデータ検索システムを適用する場合、ストレージ索引値域が限りなく小さくなるように経路識別子を決定すれば、同じメッセージが何度も同一ノードに転送されてくることを阻止することができるので、上記の問題が解消できるという利点がある。
【０１７４】
さらに、上述した実施形態では、Ｃｈｏｒｄアルゴリズムを例に説明した。しかしながら本発明は、Ｃｈｏｒｄアルゴリズムだけでなく、Ｃｈｏｒｄと同様に識別子空間がリング型であるＫｏｏｒｄｅアルゴリズムにも適用可能である。ここで、Ｋｏｏｒｄｅアルゴリズムは、仮想的なｄｅ Ｂｕｒｕｉｊｎグラフ上のノード（イマジナリノード）を、目的キーに対応するノードに近づけるようシミュレートしながら、オーバレイネットワーク上で自ノードのデータ保持値域にイマジナリノードが含まれるよう、経路を辿っていくアルゴリズムである。本発明は、係るイマジナリノードを経路識別子として用いることで、Ｋｏｏｒｄｅアルゴリズムにも適用可能である。
【産業上の利用可能性】
【０１７５】
本発明は、ネットワークに接続した計算機群に対して、各ＣＰＵがプロセスとして動かすノードへデータを分散して管理する分散型のデータ検索システムに適用可能である。ここで想定するネットワークは、例えば、インターネットなどの広域なものから、データセンタ内部の比較的閉じたネットワークなどが挙げられる。分散配置された情報のメタデータ（例えばどのデータベースにその情報があるなどの位置情報）を、上述した実施形態及びその実施例にて説明した如く管理すれば、分散型のインデックスとして適用することができる。また、広域でのコンテンツ配信システムにも適用できる。コンテンツ配信システムとしては、映画やテレビ映像、ビデオの配信などが想定される。
【０１７６】
尚、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１７７】
（付記１）
管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノードにおいて管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するデータ検索システムであって、
各ノードは、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子（ストレージ識別子（ＳＩＤ））と、
メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子（経路識別子（ＲＩＤ））とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子（データＩＤ（ＤＩＤ））によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報（経路表）を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするデータ検索システム。
【０１７８】
（付記２）
前記各ノードの転送手段は、
前記メッセージを受信するのに応じて、自ノードが保持する前記経路情報を参照した結果に応じてノード間においてメッセージの転送を繰り返すことにより、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子（経路識別子）を持つ特定ノードに対して、前記メッセージを転送する
ことを特徴とする付記１記載のデータ検索システム。
【０１７９】
（付記３）
前記複数のノードは、
自ノードが担当するストレージに関する情報（担当ストレージ表）を有しており、
前記特定ノードの転送手段は、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする付記２記載のデータ検索システム。
【０１８０】
（付記４）
前記ストレージに関する情報は、
自ノードの前記第２の識別子（経路識別子）から、最も距離が近い前記第２の識別子を持つ他ノードまでを表す値の範囲（ストレージ索引値域）に、少なくとも一部が重なるようなターゲットデータの保持値域を持つ他ノードに関して、ターゲットデータの保持値域と、前記複数のノードが接続された通信ネットワーク上のアドレスとを含む
ことを特徴とする付記３記載のデータ検索システム。
【０１８１】
（付記５）
前記複数のノードのうち、第１ノードが保持するターゲットデータを第２ノードに配置するに際して、該第１ノードの転送手段は、前記第２の識別子の変更に応じて、前記経路情報に登録すべき情報を変更することの契機とする
ことを特徴とする付記１乃至付記４の何れかに記載のデータ検索システム。
【０１８２】
（付記６）
前記複数のノードのうち、第１ノードが保持するターゲットデータを第２ノードに分散するに際して、該第１ノードの転送手段は、前記第１の識別子と、その第１ノードによるターゲットデータの保持値域とを新たな値に更新することの契機とする
ことを特徴とする付記１乃至付記４の何れかに記載のデータ検索システム。
【０１８３】
（付記７）
管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノードにおいて管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するデータ検索方法であって、
各ノードに、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子（ストレージ識別子（ＳＩＤ））と、
メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子（経路識別子（ＲＩＤ））と
を保持させ、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子（データＩＤ（ＤＩＤ））によって特定されるターゲットデータを保持させ、
前記第２の識別子が含まれる経路情報（経路表）を用いて、メッセージを転送すべき他ノードを決定するに際して、前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするデータ検索方法。
【０１８４】
（付記８）
前記各ノードがメッセージを転送する過程において、
前記メッセージを受信するのに応じて、自ノードが保持する前記経路情報を参照した結果に応じてノード間においてメッセージの転送を繰り返すことにより、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子（経路識別子）を持つ特定ノードに対して、前記メッセージを転送する
ことを特徴とする付記７記載のデータ検索方法。
【０１８５】
（付記９）
前記複数のノードに、
自ノードが担当するストレージに関する情報（担当ストレージ表）を保持させ、
前記特定ノードは、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする付記８記載のデータ検索方法。
【０１８６】
（付記１０）
管理対象である複数のターゲットデータを、オーバレイネットワーク上において管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するノードであって、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子（ストレージ識別子（ＳＩＤ））と、
メッセージを受信した際、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子（経路識別子（ＲＩＤ））とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子（データＩＤ（ＤＩＤ））によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報（経路表）を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするノード。
【０１８７】
（付記１１）
自ノードが担当するストレージに関する情報（担当ストレージ表）を有しており、
自ノードが、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子（経路識別子）を持つ特定ノードである場合に、前記転送手段は、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする付記１０記載のノード。
【０１８８】
（付記１２）
管理対象である複数のターゲットデータを、オーバレイネットワーク上において管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するノードとして、コンピュータを動作させるコンピュータプログラムであって、そのコンピュータプログラムにより、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子（ストレージ識別子（ＳＩＤ））と、
メッセージを受信した際、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子（経路識別子（ＲＩＤ））とを保持する機能と、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子（データＩＤ（ＤＩＤ））によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報（経路表）を用いて、メッセージを転送すべき他ノードを決定する転送機能とを実現すると共に、
前記転送機能により、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするコンピュータプログラム。
【符号の説明】
【０１８９】
１０ 通信部
１１ 通信機能
２０ ストレージ部
２１ 隣接ストレージ維持機能
２２ データアクセス機能
２３ ストレージ識別子（ＳＩＤ）決定機能
２４ 隣接ストレージ表
２５ データ格納部
２６ ＳＩＤ情報格納部
３０ 初期化・終了部
３１ 参加機能
３２ 離脱機能
４０ メッセージ転送部
４１ ＲＩＤ決定機能
４２ ストレージ探索機能
４３ 経路表維持機能
４４ 担当ストレージ表維持機能
４５ ＲＩＤ情報格納部
４６ 経路表
４７ 担当ストレージ表
１００ ノード（データ検索装置）
２００ ネットワーク
３００ 保持部（ストレージ部）
３０１ 第１の識別子（ストレージ識別子（ＳＩＤ））
３０２ 第３の識別子（データＩＤ（ＤＩＤ））
３０３ ターゲットデータ
４００ 転送部（メッセージ転送部）
４０１ 第２の識別子（経路識別子（ＲＩＤ））
４０２ 経路情報（経路表）
【技術分野】
【０００１】
本発明は、管理対象のデータ（ターゲットデータ）を、Ｐ２Ｐを構成するノード間において管理するデータ検索技術に関する。
【背景技術】
【０００２】
Ｐ２Ｐ（Ｐｅｅｒ ｔｏ Ｐｅｅｒ、ピアツーピア）とは、特定のサーバによらず、ピア（ノード）と呼ばれる互いに対等な複数の通信装置によって構成される分散型のデータ検索システムによく用いられるアーキテクチャである。即ち、Ｐ２Ｐとは、通信方式、通信モデル、あるいは、通信技術の一分野を指す。このようなＰ２Ｐを、継続的あるいは一時的に、コンピュータネットワーク（通信ネットワーク）に接続した計算機群によって構成するに際して、各計算機のＣＰＵ（Central Processing Unit）は、ピア（ノード）と呼ばれるプロセス（処理、プログラム）を、１つあるいは複数実行する。Ｐ２Ｐを構成する分散型のデータ検索システムにおいて、各ノードは、管理対象である複数のデータを、個々のノード、或いは一部のノードに分配した状態で保持する。そして、これらのノードは、互いに対等に通信を行いながら、データの検索や新しいデータの登録といった管理対象のデータに対する処理を実現する。本願において、管理対象のデータとは、例えば動画や音楽などのコンテンツ情報や、データベースのインデックス情報、プログラム（ソフトウェア・プログラム・モジュール）を構成する情報などを指す（以下、これらのデータを「ターゲットデータ」と称する）。但し、係るターゲットデータは、それ以外の情報であっても構わない。
【０００３】
ところで、Ｐ２Ｐ技術の一類型として、上記のようなデータ検索システムに一般的に適用される技術として、分散ハッシュテーブル（Ｄｉｓｔｒｉｂｕｔｅｄ Ｈａｓｈ Ｔａｂｌｅ：ＤＨＴ）がある。
【０００４】
ＤＨＴにおいて、あるコンピュータネットワークに接続された計算機群の各ＣＰＵは、ノードに所定の方法で論理的な識別子（論理識別子、識別子、ＩＤ）を与える、そして、ＤＨＴでは、ノードを識別子空間にマップ（マッピング）することで、当該コンピュータネットワークの上に、論理的には別のネットワークが構築される。ＤＨＴにおいて個々のＣＰＵがノードに論理識別子を与える所定の方法は、実装の形態などによって様々である。但し、一般的なＤＨＴでは、ハッシュ関数の出力値であるハッシュ値を、論理識別子として使用する方法が知られている。この場合、物理的に存在するコンピュータネットワーク上に論理的なネットワークが構築されることにより、ＤＨＴのノードは、当該コンピュータネットワークよりも下位のコンピュータネットワークのトポロジを意識しない通信を行うことができる。すなわち、ＤＨＴにおける任意のノードは、ＩＰアドレスなどのコンピュータネットワーク上のアドレス（住所）を知らない他ノードとも通信を行うことができる。このように、あるコンピュータネットワーク上に構築される別のネットワークのことを、“オーバレイネットワーク”と呼ぶ。即ち、オーバレイネットワークとは、インターネットなどの物理的なトポロジとは独立したアプリケーションレベルのネットワークである。本願における以降の説明では、コンピュータネットワーク及び通信ネットワークを“ネットワーク”と略称する場合がある。一方、係るオーバレイネットワークを意味するときは、略称せずに“オーバレイネットワーク”と表現する。
【０００５】
図２は、本願に関連するオーバレイネットワークと、下位のコンピュータネットワークとの対応関係を模式的に例示する図である。図中の破線矢印は、コンピュータネットワークに接続された計算機（黒丸）と、オーバレイネットワークにおけるノード（白丸）との対応関係を表している。図２に示される通り、一つの計算機は、オーバレイネットワークでは複数のノードとして振舞う場合もある。また、コンピュータネットワークのトポロジと、オーバレイネットワークのトポロジとは、同一であるとは限らない。
【０００６】
ＤＨＴを用いた分散型のデータ検索システムにおいて、コンピュータネットワークに接続された計算機群の各ＣＰＵは、所定の方法でターゲットデータに論理識別子を与える。そして、各ＣＰＵは、論理識別子を与えたターゲットデータを、論理識別子に従って、ノードと同じ識別子空間へマップすることにより、当該ターゲットデータを、各ノードに分散配置する。ここで、ターゲットデータに対して論理識別子を与える方法としては、採用するＤＨＴのアルゴリズムや実装形態によって様々である。例えば、係る方法としては、ハッシュ関数の出力値であるハッシュ値を論理識別子として利用する方法を採用することができる。
【０００７】
図３は、非特許文献１に記載されているＣｈｏｒｄアルゴリズムを例に、識別子空間におけるノードと、ターゲットデータとの対応関係を例示する図である。図３において、二重破線の円環（Ｃｉｒｃｌｅ）は、Ｃｈｏｒｄにおける識別子（ＩＤ）空間を表している。図３に示す例において、識別子の全体の値域は、０以上１２８未満とする。ここで、５つの白丸は、ノードを表す。説明の便宜上、個々のノードには、ラベルａ〜ｅが付与されている。ここで、ラベルとは、各ＣＰＵがノードとして実行するプロセスが当該システムには複数存在する場合があるため、便宜上、それらを区別するために付与した記号（ノードの名称）である。図３では、ノードに付与される識別子によっても、ノードを区別することは可能である。尚、後述する実施形態に係る負荷分散によって、ノード（プロセス）は、実行中に、自ノードが持つ識別子の値を変更する可能性がある。そのため、プロセスを真に特定するためには、ラベルを用いることとする。
【０００８】
また、図３に示す円環において、各ノードの下部には、個々のノードのノード識別子（ノードＩＤ：ＮＩＤ）を表記する。本願において、ノード識別子は、識別子空間上の位置の名称を表しており、ノードが所持している情報である。白い四角形は、ターゲットデータを表す。各ターゲットデータの上部には、個々のターゲットデータのデータ識別子（データＩＤ：ＤＩＤ）を示す。図３によれば、ノードとターゲットデータとが同じ識別子空間上にマップされていることが判る。以降、便宜上、ノードに付与される識別子をノードＩＤ、データに付与される識別子をデータＩＤと呼ぶ。但しこれらの識別子は、何れも同じ識別子空間から得られる値であることに注意する。また、以下の説明において、ノードＩＤとデータＩＤどちらにも当てはまる説明については、単に“識別子”と表現する場合がある。
【０００９】
ところでＤＨＴでは、識別子に距離の概念が採用されている。ＤＨＴにおいて、係る距離の概念は、分散配置されたデータ（ターゲットデータ）の管理に関して非常に重要な役割を果たす。距離の定義は、アルゴリズムによって異なる。例えばＣｈｏｒｄにおける距離の定義によると、識別子Ｘからの距離が最も小さい（短い）識別子は、Ｘの次に値が大きな識別子である。一方、識別子Ｘからの距離が最も大きい（長い）識別子は、Ｘの次に値が小さな識別子である。つまり、識別子空間上において値が異なる二つの識別子ＸとＹとに注目した場合、ＸからＹまでの距離の大きさは、ＹからＸまでの距離の大きさと同値ではない。例えば図３において、ノードａにとって最も近いノード（すなわち、ノードａからの距離が最も小さいノード）は、ノードａの次に値が大きいノード識別子を持つノードｂである。これに対して、ノードｂにとって最も近いノードは、ノードｂの次に値が大きいノード識別子を持つノードｃである。
【００１０】
また、識別子空間は、図３に示す如く循環している。言い換えれば、図３に示す識別子空間は、前述した通り識別子の全体の値域を０以上１２８未満と仮定したため、当該識別子空間において最大の識別子値である１２７の次に大きい識別子値は０である。このため、ノードｅにとって最も近いノードは、ノードａとなる。Ｃｈｏｒｄでは、自ノードからの距離が最も近い他ノードは、そのノードのサクセッサと呼ぶ。一方、自ノードまでの距離が最も近い他ノードは、そのノードのプレデセッサと呼ぶ。従って、図３に示す例において、ノードｅのサクセッサはノードａである。ノードｅのプレデセッサはノードｄである。
【００１１】
尚、Ｃｈｏｒｄと同様に識別子空間がリング状で、同様の距離の定義を持つ異なるアルゴリズムとして、他にＫｏｏｒｄｅ（非特許文献４）と呼ばれるアルゴリズムも存在する。
【００１２】
上述したように、ノードは、所定の規則に基づき定められた識別子の、ある値域を情報として保持する。ここで、値域とは、ある値から他の値までの値の範囲である。そして、ノードは、この値域に属するデータＩＤを持つデータを、ターゲットデータとして管理する。以降、本願では、このような識別子空間上の値域を、“データ保持値域”と呼ぶ。また、ある識別子Ｘがあるノードのデータ保持値域に属するとき、そのノードを、識別子Ｘの“担当ノード”と呼ぶ。ＤＨＴにおいて、識別子Ｘの担当ノードは、識別子Ｘから最も近い識別子を持つノードである。よって、あるノードのデータ保持値域は、自ノードＩＤまでの距離が最も小さい他ノードのノードＩＤから、自ノードＩＤまでの範囲として算出される。例えば、距離の定義が非対称であるＣｈｏｒｄアルゴリズムでは、あるノードのデータ保持値域は、プレデセッサのノードＩＤより大きく、かつ、自ノードＩＤ以下である。
【００１３】
図４は、図３に例示したノードａ〜ｅの夫々のデータ保持値域と、それらノードが保持するデータとの関係を説明する図である。表１は、図３に例示した各ノードのデータ保持値域を表すテーブルである。
【００１４】
【表１】
【００１５】
本願において、データ保持値域は、数学的な表記によって表現される。例えば、表１に示すノードｃのデータ保持値域（２８、５６］は、識別子２８より大きく識別子５６以下であることを意味する。例として、表１におけるノードａ〜ｅが保持するターゲットデータの一覧を、図４（ａ）から図４（ｅ）にリストする。当該リストに示すように、各ノードは、ターゲットデータに与えられたデータＩＤと、ターゲットデータとを関連付けて保持していることとする。ノードのデータ保持値域が大きいほど、そのノードは、確率的に数多くのターゲットデータを保持する。そして、各ノードにおいて、もし、そのノードのターゲットデータに対する格納容量やネットワークの帯域幅に対して、管理すべきターゲットデータの件数やデータボリュームが大きいとき、そのノードの負荷は高いと言える。
【００１６】
複数のノードによって複数のターゲットデータを分散管理するためには、ノード間における通信は欠かせない。ＤＨＴを採用するノードは、任意の識別子を検索キーとし、その検索キーの担当ノードへメッセージを届ける通信を行う。ノード間において通信されるメッセージには、検索用のキー値と、宛先ノードへの何らかの処理命令（処理要求）とが記述されている。記述される処理命令としては、例えば、ターゲットデータの検索命令や登録命令などが挙げられる。ノードは、オーバレイネットワークに参加している他のすべてのノードの、ネットワーク上の住所（例えばＩＰアドレス）を知っているとは限らない。このため、ノードは、検索キーの担当ノードの住所を知らない場合もある。このような場合、各ノードは、それぞれが持つ経路表から適切なノードを選び、メッセージをノード間でリレー（中継、転送）することにより、当該メッセージを、担当（宛先）ノードに最終的に届ける（“経路表”については図５を参照して後述する）。そして本願では、メッセージが経由するノードの道筋を、“経路（Ｒｏｕｔｅ）”と称する。また、メッセージをノード間において転送する処理を、メッセージ転送（メッセージ転送処理）と称する。
【００１７】
経路表が保持する他ノードの情報（経路情報）は、ネットワークからメッセージを受け取ったノードが、そのメッセージを、次の適切な他ノードへ転送することが可能な情報であれば、どのような情報であっても構わない。
【００１８】
図５（ａ）から図５（ｅ）は、図３に例示した５つのノードａ〜ｅの経路表を例示する図である。これらの経路表には、経路情報として、各ノードの識別子空間上の値（たとえばノードＩＤ）と、ネットワーク上のアドレス（住所）とが登録されている。ここではＩＰアドレスとポート番号がネットワーク上のアドレスである。どのような基準で経路表に登録すべき他ノードを選ぶかは、実装態様やアルゴリズムによって異なる。図５（ａ）から図５（ｅ）に例示した各表は、Ｃｈｏｒｄアルゴリズムに則って作られている。
【００１９】
経路表の中から、次にメッセージを転送べきノードを選択する方法は、実装形態やアルゴリズムによって異なる。但し、基本的には、受け取った検索キーが表す識別子からの距離がより小さくなるような識別子を持つ他ノードへ、メッセージは転送される。例として、Ｃｈｏｒｄアルゴリズムにおけるメッセージ転送の動作を以下に説明する。
【００２０】
Ｃｈｏｒｄにおいて、各ノードは、自ノードのサクセッサがどのノードであるか、およびサクセッサの住所を必ず知っていることを前提とする。
【００２１】
メッセージ転送の最終的な目標は、検索キー（ノードＩＤあるいはデータＩＤ）を含むメッセージを、識別子Ｘの担当ノードに転送することである。ここで、担当ノードとは、識別子空間上において、識別子Ｘからの距離が最も小さいノードＩＤを持つノード、あるいは、自ノードのデータ保持値域に識別子Ｘが属しているノードである。
【００２２】
あるノードは、メッセージを受け取ると、メッセージに含まれる検索キーＸと、自ノードおよび経路表に登録された全てのノードのノードＩＤとを比較する。Ｘまでの距離が最も小さいノードＩＤを持つノードが、自ノードがメッセージを転送すべきノードである。もし、経路表に登録された、サクセッサを含む他のどのノードより、自ノードＩＤからＸまでの距離が小さいとき、自ノードは、自ノードＩＤとサクセッサのノードＩＤとの間に、Ｘが存在していることが判る。上述したサクセッサの定義によれば、自ノードとサクセッサとの間に他のノードは存在しない。そのため、自ノードは、Ｘからの距離が最も小さいノードＩＤを持つノードが自分のサクセッサであることが分かる。すなわち、サクセッサはＸの担当ノードである。自ノードは、直ちにサクセッサにメッセージを転送し、当該メッセージに対するメッセージ転送処理は完了する。
【００２３】
Ｃｈｏｒｄでは、上述した手順のように、検索キーＸを含むメッセージは、必ずＸの担当ノードをサクセッサとして持つノードにたどり着き、その次の転送で担当ノードにたどり着く。以降の説明において、Ｘの担当ノードをサクセッサとして持つノードは、Ｘのルートノード（Ｒｏｏｔ Ｎｏｄｅ）と呼ぶ。
【００２４】
図６に示す状態（ａ）から状態（ｅ）は、図３に例示する識別子空間におけるメッセージ転送の動作の流れを説明する図である。はじめに、図６の状態（ａ）に示すように、ノードｃは、オーバレイネットワークの外部から受信したメッセージにより、識別子３を持つターゲットデータの検索命令を取得したとする。このメッセージには、検索キーとして、探したいターゲットデータの識別子値（ここではデータＩＤ＝３）が含まれている。また、ここでは図６の状態（ａ）に例示するように、ノードｃがオーバレイネットワークの外部からメッセージを受信している。尚、ＤＨＴでは、一般に、任意のノードが外部からメッセージを受信可能である。
【００２５】
次に、図６の状態（ｂ）に示すように、ノードｃは、まず自ノードのデータ保持値域（２８、５６］に、当該識別子（データＩＤ＝３）が属さないことを確認する。その後、ノードｃは、自ノードおよび経路表（図５（ｃ））に登録されたノードの中から、データＩＤ＝３までの距離が最も小さいノードＩＤを持つノードｅを選ぶ。そしてノードｃは、ノードｅに対して、当該メッセージを転送する（図６の状態（ｂ）に示す動作＜１＞）。
【００２６】
ノードｅは、当該メッセージを受信するのに応じて、ノードｃと同様に、自ノードのデータ保持値域（６４、１２１］にデータＩＤ＝３が属するか否かを確認し、この例の場合は属さないと判断する。そこで、ノードｅは、自ノードおよび経路表（図５（ｅ））に登録されたノードの中から、データＩＤ＝３までの距離が最も小さいノードＩＤを持つノードａを選び、ノードａに対してメッセージを転送する（図６の状態（ｂ）に示す動作＜２＞）。
【００２７】
同様な手順により、ノードａもまた、自ノードのデータ保持値域（１２１、２］にデータＩＤ＝３が属さないのを確認した後、自ノードおよび経路表に登録されたノードの中から、データＩＤ＝３までの距離が最も小さいノードＩＤを持つノードａを選ぶ。この場合、ノードａは自ノードを選んだため、ノードａは、データＩＤ＝３のルートノードが自分であり、かつ、担当ノードが自分のサクセッサ（ノードｂ）であることを認識する。ノードａは、ノードｂに対して、ノードｃがデータＩＤ＝３のターゲットデータを探していることを、メッセージによって伝達する（図６に示す状態（ｃ））。メッセージを受け取ったノードｂは、ノードｃへデータＩＤ＝３のターゲットデータを送信する（図６に示す状態（ｄ））。そして、ターゲットデータを受け取ったノードｃは、当該検索命令の発行元に対して、当該ターゲットデータを送信する（図６に示す状態（ｅ））。
【００２８】
上述したノードは、必要に応じて、オーバレイネットワークへの参加（加入）、或いは離脱（脱退）を行う場合がある。あるいは、何らかの不具合により、係るノードは、短期的あるいは長期的に通信不可能な状態に陥ることがある。これにより、経路表に登録されたノードの識別子や住所などの経路情報は、時間の経過に伴い失効する可能性がある。例えば、図３におけるノードｅが、突然の不具合で通信不可能になったと仮定する。このとき、図６に示した一連の状態（ａ）から（ｅ）に例示した手順によってメッセージ転送を行おうとすると、ノードｃの経路表（図５（ｃ））からノードｅを選択し、ノードｅに対してメッセージを送信しても通信は失敗する。このとき、実装態様によっては、ノードcは、経路表の中から、検索キーまでの距離が次に近いノードｄを選択することによって再びメッセージの送信を試みるなどの処置を行う。しかしながら、通信の失敗による通信遅延はどうしても生じる。
【００２９】
このような問題を未然に防ぐため、ＤＨＴのアルゴリズムでは、各ノードが経路表のヘルスチェックを行う。ヘルスチェックは、経路表に登録されている他ノードに関する経路情報が正しいかどうかを、その他ノードと通信を試みることによって確認可能な機能である。更にヘルスチェックは、もし経路情報が間違っていた場合はその経路情報を経路表から削除する、ないしは、正しい経路情報に書き換える機能である。Ｃｈｏｒｄでは、ヘルスチェックは定期的に行われる。図３に例示する状況においてノードｅが通信不可能に陥った場合、あるタイミングにおけるチェックで、ノードａ、ｂ、ｃ、ｄは、ノードｅの経路情報が失効していることを検出する。その時点において、夫々のノードは、経路表からノードｅに関する情報を削除する。しかしながら、どのアルゴリズムにおいても、実際に経路情報が失効したタイミングからヘルスチェックにより経路表が正されるまでの時間は、経路表は失効した情報を含むことになる。ノードのオーバレイネットワークへの参加や離脱が頻繁な場合などは、経路表に失効した情報が含まれる確率が高くなるため、通信効率はより低下する。
【００３０】
先述したように、ＤＨＴでは、データ保持値域が広いほど、多くのターゲットデータを保持する確率が大きくなる。すなわち、管理するターゲットデータの量が増えるので、ノードの負荷が比較的大きくなる。あるノードに過大な負荷が集中すると、そのノードの処理効率は低下し、結果として、データ検索システム全体の処理効率が低下する。そのため、ＤＨＴでは、重要な要素技術として、様々な負荷分散技術が提案されている。
【００３１】
本願に関連する多くの負荷分散技術において、ＣＰＵは、負荷の高いノードや他のノードのデータ保持値域を変更する。そしてＣＰＵは、その値域から外れたデータＩＤに対応するターゲットデータを、新たな担当ノードへ移すことによって負荷の分散を実現する。係る多くの負荷分散技術は、このような技術的アプローチを採用する。ここで、データ保持値域を変更するアプローチを採用する負荷分散技術のイメージ図を、図７に示す。
【００３２】
図７は、負荷分散に際してデータ保持値域を変更するアプローチを取る関連技術を説明する図である。即ち、図７は識別子空間の一部を表わしており、ノードＸとノードＹとが空間上に隣りあって存在している。図７に示す例では、ノードＸのデータ保持値域に属するターゲットデータが多いので、ノードＸは負荷が大きい。そこで、係る負荷分散技術では、ノードＩＤを基に算出されるデータ保持値域を変更することで、一部のターゲットデータの担当ノードをノードＸからノードＹとし、これにより負荷の分散を図っている。ここで、上記のようなデータ保持値域を変更するアプローチを採る手法としては、インターバルシフト（非特許文献２）、仮想サーバ（非特許文献３）、仮想ノード（非特許文献２）と呼ばれるアルゴリズムなどが提案されている。
【００３３】
ここで、データ保持値域を変更することで負荷分散を行う動作を、図８（ａ）から図８（ｃ）、並びに表１を参照して具体的に説明する。
【００３４】
図８（ａ）から図８（ｃ）は、図３に示す識別子空間において、インターバルシフトを適用する動作を例示的に説明する図である。インターバルシフトは、負荷の高いノードが、自ノードのデータ保持値域を、データ保持値域が隣り合う他ノードとの間で調整することによって狭くする手法である。具体的には、自ノードのノードＩＤの値を変更することにより、自ノードのデータ保持値域を狭くする。ここでこの手法について概説する。
【００３５】
図３に示すノードｅにおいて、データ保持値域は、前述した表１に示したように（６４、１２１］である。係るデータ保持値域に対応して、ノードｅは、図８（ａ）に示すように、８個のデータ（即ち、ＤＩＤ＝６４、７０、８０、８２、１０３、１１０、１１５、１１９）を保持している。このため、ノードｅは、その他のノードに比べて負荷が高い。その一方で、ノードｅとデータ保持値域が隣り合うノードａ及びノードｄは、保持しているデータが夫々１個であるため、ノードｅと比較して負荷が小さい。このとき、ノードｅは、隣り合うノードａ及びノードｄと通信することにより、より負荷の軽いノードを、負荷の分散先として選択すべきである（ここではノードａを選択したとする）。ノードｅは、自ノードが管理するオブジェクトデータの一部を、ノードａに移譲（分散）できるように、自ノードのノードＩＤの値を変更する。ノードＩＤ値をどのように変更するかは、アルゴリズムや実装態様によって異なる。ここではノードｅは、保持するデータ数が以前の半分になるよう、自ノードの識別子を９３に設定する（図８（ｂ））。これにより、ノードｅのデータ保持値域は（６４、９３］、ノードａのデータ保持値域は（９３、２］となる。そこで、ノードｅは、自ノードに代わりノードａが新たに管理することになったターゲットデータ（ＩＤ１０３〜１１９）を、ノードａに送信する（図８（ｃ））。この一連の動作により、ノードｅは、管理するデータの数を減らした分だけ負荷が軽くなる。
【００３６】
しかしながら、先述した負荷分散の手法には、以下の問題がある。
【００３７】
第一に、ＤＨＴにおけるメッセージ転送は、経路表に登録された経路情報（ノードの住所やノードＩＤ）が全て正しい場合に限って、最適な、あるいは最短の経路を辿って宛先ノードへたどり着くことが実現できる。しかしながら、経路表から選んだメッセージの転送先ノードの経路情報が既に失効していた場合は、非効率な経路選択となる。例えば、次の転送先として選択したノードの経路情報のうち、住所（ＩＰアドレスやポート番号）が失効していた場合は、通信そのものが失敗する。或いは、住所は正しくともノードＩＤが負荷分散によるノードＩＤの変更などで失効していた場合は、選択したノードにメッセージが無事に届けられたとしても、最短経路が選択された可能性は低くなる。
【００３８】
例えば、図８（ｃ）に示す状態の直後に、オーバレイネットワークの外部から、データＩＤ＝１１９のターゲットデータを検索する要求を、ノードｃが新たに取得した場合を考える。そしてこの場合、何れのノードも経路表のヘルスチェックがまだ行われておらず、経路表は、図５（ａ）から図５（ｅ）に示す状態であると仮定する。
【００３９】
上記のような状況において、ノードｃは、まず、自ノードと経路表（図５（ｃ））とに登録された他ノードｄおよびｅの中から、データＩＤ＝１１９までの距離が最も小さいノードＩＤを持つノードｄを選択する。そしてノードｃは、ノードｄへ検索キー（データＩＤ＝１１９）を含むメッセージを転送する。
【００４０】
メッセージを受け取ったノードｄは、同様に、自ノードと経路表（図５（ｄ））とに登録された他ノードａおよびｅの中から、検索キーまでの距離が最も小さいノードＩＤを持つノードｄを選択する。この場合、選択したノードが自ノードであるため、ノードｄは、自ノードがデータＩＤ＝１１９のルートノードであると判断する。更にノードｄは、サクセッサであるノードｅが、データＩＤ＝１１９の担当ノードだと判断する。そしてノードｄは、ノードｅに対して、データＩＤ＝１１９に対応するターゲットデータを要求する。しかし実際は、図８（ａ）乃至図８（ｃ）を参照して上述した一連の負荷分散動作によって、このターゲットデータは、既にノードａが所持している。このため、ノードｅは、要求元であるノードｃに対して、当該ターゲットデータを送信することができない。このとき、実装態様によっては、ノードｅは検索失敗のメッセージを、ノードｃへ向けて送信し、メッセージの転送を終えるかもしれない。あるいは、ノードｅは、自ノードが持つ経路表（図５（ｅ））を用いてメッセージの転送処理をやり直すかもしれない。そしてこの場合、ノードｅの経路表が図５（ｅ）に示す状態のままであれば、ノードｅは、メッセージの検索キーが表すデータＩＤ＝１１９までの距離が最も近いノードはノードｄであると判断する。そしてノードｅは、データＩＤ＝１１９に対するターゲットデータの検索要求メッセージを、ノードｄへ改めて転送し直す。ノードｄは、もし経路表がまだ図５（ｄ）のままならば、先ほどと同様にノードｅを検索キー１１９の担当ノードだと誤認する。このように、必要なノードにおいてヘルスチェックが実行され、且つ必要な経路情報が更新されるまでの間、当該メッセージは、オーバレイネットワーク上のノード間をさまよい、メッセージ転送が非効率になる可能性がある。
【００４１】
このように、上述した関連技術に係る負荷分散手法には、各ノードのデータ保持値域を変更する過渡的な期間において、メッセージ転送の効率が一時的に悪化するという問題がある。これは、ＤＨＴにおいて、ノード識別子（ノードＩＤ）の値が、ターゲットデータをどの程度の数だけ保持するかを決める要素であると共に、ノード識別子の値が経路表にも含まれ、メッセージ転送に際して用いられることが原因である。
【先行技術文献】
【非特許文献】
【００４２】
【非特許文献１】Ｉｏｎ Ｓｔｏｉｃａ，Ｒｏｂｅｒｔ Ｍｏｒｒｉｓ，Ｄａｖｉｄ Ｋａｒｇｅｒ，Ｍ． Ｆｒａｎｓ Ｋａａｓｈｏｅｋ ａｎｄ Ｈａｒｉ Ｂａｌａｋｒｉｓｈｎａｎ，”Ｃｈｏｒｄ：Ａ Ｓｃａｌａｂｌｅ Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ Ｌｏｏｋｕｐ Ｓｅｒｖｉｃｅ ｆｏｒ Ｉｎｔｅｒｎｅｔ Ａｐｐｌｉｃａｔｉｏｎｓ，”２００１．
【非特許文献２】Ｋａｒｇｅｒ， Ｄａｖｉｄ Ｒ．， ａｎｄ Ｍａｔｔｈｉａｓ Ｒｕｈｌ，”Ｓｉｍｐｌｅ Ｅｆｆｉｃｉｅｎｔ Ｌｏａｄ−Ｂａｌａｎｃｉｎｇ Ａｌｇｏｒｉｔｈｍｓ ｆｏｒ Ｐｅｅｒ−ｔｏ−Ｐｅｅｒ Ｓｙｓｔｅｍｓ，”ＳＰＡＡ’０４．
【非特許文献３】Ａｎａｎｔｈ Ｒａｏ， Ｋａｒｔｈｉｋ Ｌａｋｓｈｍｉｎａｒａｙａｎａｎ， Ｓｏｎｅｓｈ Ｓｕｒａｎａ ａｎｄ Ｒｉｃｈａｒｄ Ｋａｒｐ，”Ｌｏａｄ Ｂａｌａｎｃｉｎｇ ｉｎ Ｓｔｒｕｃｔｕｒｅｄ Ｐ２Ｐ Ｓｙｓｔｅｍｓ，”ＩＰＴＰＳ’０３．
【非特許文献４】Ｋａａｓｈｏｅｋ， Ｆｒａｎｓ Ｍ．， ａｎｄ Ｄａｖｉｄ Ｋａｒｇｅｒ，”Ｋｏｏｒｄｅ： Ａ Ｓｉｍｐｌｅ ｄｅｇｒｅｅ−ｏｐｔｉｍａｌ ｄｉｓｔｒｉｂｕｔｅｄ ｈａｓｈ ｔａｂｌｅ，”２００３．
【発明の概要】
【発明が解決しようとする課題】
【００４３】
関連技術として上述したＤＨＴの効率化のための負荷分散技術においては、ターゲットデータを別ノードに移し替えるために、ノードの識別子（ＮＩＤ）を変更する。このため、係る負荷分散技術においては、複数のノードの経路表において一部の情報の失効が発生するのに応じて、それら経路表に登録されている経路情報の削除等の書き換えが行われる。そして、経路情報が書き換えられている過渡的な期間において、ノード間において転送されるメッセージは、場合（タイミング）によっては、書き換えが行われていない定常状態と比較して多くのノードを中継（迂回）される。このため、メッセージの転送に長い時間を要したり、或いは、通信が失敗するなどの問題が生じる。これは、経路情報の書き換えが行われている間にメッセージの転送が行われることに起因して、当該各ノードが接続されているネットワークの通信状態が不安定になることに起因する。
【００４４】
即ち、上記の問題は、ノード毎に唯一決定されている識別子（ノードＩＤ：ＮＩＤ）が、ノードが管理するターゲットデータの量に影響を与えると同時に、経路情報の一部としても含まれているため、メッセージ転送の実行に際して、次の中継ノードを決定するために重要な役割を果たすことに起因する。
【００４５】
更に、上述した問題は、ストレージの容量や帯域幅など、ターゲットデータを保持できる量に影響を与えるノード（ひいてはノードを実行するＣＰＵ（Central Processing Unit）や計算機）の性能がノードごとに異なるようなヘテロ（ヘテロジニアス）な環境において、以下に説明する更なる問題を派生する。
【００４６】
即ち、上記のようなヘテロな環境の場合、ノードが保持できるデータの数量（ボリューム）は、ノードによって異なる。そのような環境において、各ノードの負荷ができるだけ均一に分散するようにターゲットデータを分配していくと、データ保持値域は、ノード毎に異なってくる。そして、データ保持値域の大きさに偏りが生じると、識別子空間上のある近接した範囲において複数のノードが識別子を割り当てられ、ノード群が比較的密集する現象が生じる。このとき、密集しているノードは、密集していないノードに比べて、ターゲットデータの保持量が少なく、且つ他ノードの経路表に登録される確率が低い。すなわち、メッセージの中継ノードとして選ばれる確率が低い。一般に、メッセージの情報量は、ターゲットデータの情報量より小さい。このため、多くのターゲットデータを保持しきれないノードであっても、メッセージの中継であれば実行可能な場合がある。しかしながら、上述のとおり、負荷分散の結果、データ保持値域の大きさがノード間で大きく偏ると、メッセージの中継ノードとして選ばれる確率にノード間で差が生じ、これに応じてノードのリソースに無駄が生じる。
【００４７】
これは、関連技術として上述したＤＨＴ技術では、各ノードが保持するターゲットデータの数量に由来する負荷の観点から、個々のノードの経路表に対して、どの程度の数量の経路情報を登録するかを調整することが難しいためである。
【００４８】
本発明は、上述した課題を解決することを目的とする。即ち本発明は、ノード間においてターゲットデータを管理するに際して、上述した関連技術と比較して、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現するデータ検索システム等の提供を主な目的とする。
【課題を解決するための手段】
【００４９】
上記の目的を達成すべく、本発明に係るデータ検索システムは、以下の構成を備えることを特徴とする。
【００５０】
即ち、管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノードにおいて管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するデータ検索システムであって、
各ノードは、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する。
【００５１】
また、例えば前記各ノードの転送手段は、
前記メッセージを受信するのに応じて、自ノードが保持する前記経路情報を参照した結果に応じてノード間においてメッセージの転送を繰り返すことにより、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子を持つ特定ノードに対して、前記メッセージを転送すると良い。
【００５２】
また、上記の場合において、例えば前記複数のノードは、
自ノードが担当するストレージに関する情報を有しており、
前記特定ノードの転送手段は、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行するとよい。
【００５３】
また、上記同目的を達成する他の観点は、管理対象である複数のターゲットデータを、オーバレイネットワーク上において管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するノードであって、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信した際、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送することを特徴とする。
【００５４】
尚、同目的は、上記の各構成のデータ検索システムに対応するデータ検索方法によっても達成される。
【００５５】
また、同目的は、上記の各構成を有するノードを、コンピュータによって実現するコンピュータ・プログラム、及びそのコンピュータ・プログラムが格納されている、コンピュータ読み取り可能な記憶媒体によっても達成される。
【発明の効果】
【００５６】
本発明によれば、ノード間においてターゲットデータを管理するに際して、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現するデータ検索システム等の提供が実現する。
【図面の簡単な説明】
【００５７】
【図１】本発明の実施形態に係るデータ検索システムの構成を例示するブロック図である。
【図２】本願に関連するオーバレイネットワークと、下位のコンピュータネットワークとの対応関係を模式的に例示する図である。
【図３】非特許文献１に記載されているＣｈｏｒｄアルゴリズムを例に、識別子空間におけるノードと、ターゲットデータとの対応関係を例示する図である。
【図４】図３に例示したノードａ〜ｅの夫々のデータ保持値域と、それらノードが保持するデータとの関係を説明する図である。
【図５】図３に例示した５つのノードａ〜ｅの経路表を例示する図である。
【図６】図３に例示する識別子空間におけるメッセージ転送の動作の流れを説明する図である。
【図７】負荷分散に際してデータ保持値域を変更するアプローチを取る関連技術を説明する図である。
【図８】図３に示す識別子空間において、インターバルシフトを適用する動作を例示的に説明する図である。
【図９】本発明の第１及び第２の実施形態に係るデータ検索装置のハードウェア構成を例示的に説明する図である。
【図１０】本発明の第２の実施形態に係るデータ検索システムを、Ｃｈｏｒｄアルゴリズムに適用した動作例を説明する図である。
【図１１Ａ】図１０における各ノードの担当ストレージ表を示す図である。
【図１１Ｂ】図１０における各ノードの隣接ストレージ表を示す図である。
【図１２】本発明の第２の実施形態に係るデータ検索システムにおいて、高負荷な状態にあるノードｅから負荷分散を行うときの動作の流れを説明する図である。
【図１３Ａ】本発明の第２の実施形態に係るデータ検索システムにおいて、オーバレイネットワークに新たなノードが参加する動作を説明する図である。
【図１３Ｂ】本発明の第２の実施形態に係るデータ検索システムにおいて、オーバレイネットワークに新たなノードが参加する動作を説明する図である。
【図１３Ｃ】本発明の第２の実施形態に係るデータ検索システムにおいて、オーバレイネットワークに新たなノードが参加する動作を説明する図である。
【図１４】図１３Ａから図１３Ｃに示すオーバレイネットワークへの参加動作において各ノードが参照する担当ストレージ表を例示する図である。
【図１５】本発明の第２の実施形態に係るデータ検索装置が実行するターゲットデータの探索処理を示すフローチャートである。
【図１６】本発明の第２の実施形態に係るデータ検索装置が実行するオーバレイネットワークへの参加処理を示すフローチャートである。
【図１７】本発明の第２の実施形態に係るデータ検索装置が実行する担当ストレージ表の書き換え処理を示すフローチャートである。
【図１８】本発明の第２の実施形態に係るデータ検索装置が実行するネットワークからの離脱処理を示すフローチャートである。
【図１９】本発明の第２の実施形態に係るデータ検索装置が実行する負荷分散処理を示すフローチャートである。
【図２０】本発明の第２の実施形態に係るデータ検索装置が実行する経路識別子の変更処理を示すフローチャートである。
【図２１】本発明の第１の実施形態に係るデータ検索システムの構成を示すブロック図である。
【発明を実施するための形態】
【００５８】
次に、本発明の模範的な実施の形態について、図面を参照して詳細に説明する。
【００５９】
＜第１の実施形態＞
図２１は、本発明の第１の実施形態に係るデータ検索システムの構成を示すブロック図であり、以下に説明する各実施形態およびその変形例に共通する概念を表す。
【００６０】
図２１に示すデータ検索システムは、管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノード（図２１の例では３つのノードＡ、Ｂ、Ｃ）において管理する。そして、このデータ検索システムは、移動対象のターゲットデータの移動に先立って、その移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索する。
【００６１】
ノード（データ検索装置）１００は、保持部（ストレージ部）３００と、転送部（メッセージ転送部）４００とを備える。
【００６２】
第１の識別子（ストレージ識別子（ＳＩＤ））３０１は、自ノードが保持すべきターゲットデータの値域を求めるための情報である。第２の識別子（経路識別子（ＲＩＤ））４０１は、受信したメッセージを他ノードに転送する転送経路の決定に用いる情報である。第３の識別子（データＩＤ（ＤＩＤ））３０２は、ターゲットデータを識別する情報である。
【００６３】
保持部３００は、第３の識別子（データＩＤ（ＤＩＤ））３０２によって特定されるターゲットデータ３０３を保持（格納）する。各ノードが保持するターゲットデータ３０３は、第１の識別子３０１を基に決定した値域に属するデータである。
【００６４】
転送部４００は、第２の識別子４０１が含まれる経路情報（経路表）４０２を用いて、メッセージを転送すべき他ノードを決定する。その際、転送部４００は、第１の識別子３０１、第２の識別子４０１、第３の識別子３０２の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、経路情報４０２を参照する。その結果、転送部４００は、対応する他ノードが存在する場合には、当該他ノードに対して、自ノードが受信した当該メッセージを転送する。
【００６５】
本実施形態に係るデータ検索システムは、上記のように複数種類の識別子を用いて、ターゲットデータを管理している。このような本実施形態によれば、ノード間においてターゲットデータ３０３を管理するに際して、例えばあるノードにおける負荷を分散する必要が生じ、そのノードの第１の識別子３０１を変更したとしても、第１の識別子３０１とは独立している第２の識別子４０１は影響を受けない。即ち、本実施形態において、第２の識別子４０１が含まれる経路表の情報は失効することが無い。よって、本実施形態によれば、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現することができる。
【００６６】
＜第２の実施形態＞
次に、上述した第１の実施形態に係るデータ検索システムを基本とする模範的な第２の実施形態について説明する。以下の説明においては、本実施形態に係る特徴的な部分を中心に説明すると共に、上述した第１の実施形態と同様な構成についての重複する説明は省略する。
【００６７】
本実施形態に係る分散型のデータ検索システムは、コンピュータネットワークに接続された複数のノードによって構成される。このデータ検索システムは、あるノードから他ノードにターゲットデータを、ＤＨＴを用いて配置するシステムである。ここで、配置とは、ノード間におけるターゲットデータの移動、移譲、分配などを表す。このようなシステムでは、ノード間におけるターゲットデータの移動によるネットワーク上の通信トラフィックの発生を抑制する必要がある。本システムは、当該ターゲットデータの移動（配置）に先立って、対象となるノード間においてメッセージの転送（中継）を適宜行うことにより、移動対象のターゲットデータの異動先のノードを、メッセージを用いて探索する。このため、メッセージの情報量は、原則としてターゲットデータの情報量より少ないことが好ましい。
【００６８】
本実施形態において、各ノードは、ネットワークに接続された計算機のＣＰＵが実行するプロセス（ソフトウェアプログラム・モジュール）である。従って、本実施形態において、ネットワークに接続された複数のノードは、ハードウェア資源としての１台の計算機（ＣＰＵ）が、いわゆる仮想マシンとして実現する形態、ノード毎に計算機が割り当てられた形態、並びにそれらを適宜組み合わせた形態などが想定される。
【００６９】
また、本実施形態において、当該各ノードには、自ノードがターゲットデータを保持（格納）するための第１の識別子と、ノード間においてメッセージ転送を行うための第２の識別子とが与えられる。第１の識別子は、第１の実施形態における第１の識別子３０１に相当する。第２の識別子は、第１の実施形態における第２の識別子４０１に相当する。これら２種類の識別子は、同一の識別子空間から得られる値であり、同値である必要はない。本実施形態においても、以下の説明において、係る第１の識別子を“ストレージ識別子（ＳＩＤ）”、係る第２の識別子を“経路識別子（ＲＩＤ）”と称する。
【００７０】
ストレージ識別子（ＳＩＤ）は、各ノードのデータ保持値域を決める値である。本実施形態において、第１ノードが保持するターゲットデータを第２ノードに分散（配置）するに際して、当該第１ノードは、ストレージ識別子の値を変更する。即ち、当該第１ノードのＣＰＵは、自ノードのデータ保持値域を狭める等の処理を契機として、自ノード（第１ノード）に保持されているターゲットデータを、他ノード（第２ノード）に移譲する。これにより、例えば、多くのターゲットデータを処理しており負荷が高かった第１ノードから、比較的負荷が少なかった第２ノードへの負荷分散が実現する。
【００７１】
経路識別子（ＲＩＤ）は、例えば、ターゲットデータを、オーバレイネットワークにおいて検索すべく、メッセージの転送経路を決定するために用いる値である。本実施形態において、各ノードの経路表に保持される経路情報は、ネットワーク上の住所（ＩＰアドレスなど）と、経路識別子とを含む。本実施形態において上記負荷分散は、ストレージ識別子（ＳＩＤ）を用いて実行される。このため、本実施形態において経路識別子（ＲＩＤ）を用いて実行されるメッセージ転送は、上述した関連技術で説明した経路情報の失効などによる悪影響を受けない。
【００７２】
ノードは、メッセージの受信に応じて、検索キーとなる識別子（データＩＤ、ＳＩＤ、あるいはＲＩＤ）を取得する。そして、当該ノードは、自ノードの経路表の中で、当該検索キーまでの距離が最も小さい経路識別子を持つノード（特定ノード）に対して、当該メッセージを転送する。本実施形態において、メッセージには、検索用のキー値のほかに、ノードへの何らかの処理命令（処理要求）が記述されている。
【００７３】
メッセージに含まれる処理命令がターゲットデータの検索要求である場合、上記転送処理が繰り返されることにより、当該メッセージは、やがて、オーバレイネットワークに参加している全てのノードのうち、当該検索キー値までの距離が最も小さい経路識別子を持つノード（特定ノード）にたどり着く。上述したように、当該ノードの経路識別子と、ストレージ識別子とは同値である必要はない。このため、当該ノードは、当該検索キー値が表す識別子に対応する担当ノードであるとは限らない。しかしながら、当該ノードの経路識別子の近くにデータ保持値域が広がっているような他ノードは、当該検索キーによって求めている担当ノードである可能性は高い。そこで本実施形態において、各ノードは、自ノードの経路識別子からの距離が小さいストレージ識別子を持つ他ノードの経路情報も保持する。この経路情報には、少なくとも、当該他ノードのデータ保持値域と、当該他ノードのネットワーク上の住所（アドレス）とが含まれる。このような経路情報群を、以下の説明では、“担当ストレージ表”と称する（詳細は図１１Ａを参照して後述する）。
【００７４】
また、本実施形態では、自ノードの経路識別子から、受信した検索キーまでの距離が他のどのノードよりも十分近い場合、当該自ノードは、担当ストレージ表の中に、当該検索キーの担当ノードの経路情報を必ず持っていなければならない。ターゲットデータの検索要求を含むメッセージを、オーバレイネットワーク外部からあるノードが取得した際、当該メッセージは、経路表に基づき当該オーバレイネットワーク上のノード間において中継される。そして、当該メッセージは、そのメッセージに含まれる検索キーが表す識別子までの距離が最も小さい経路識別子を持つノード（特定ノード）にやがてたどり着く。
【００７５】
当該メッセージを受信したノードは、自ノードの持つ担当ストレージ表を参照することにより、その担当ストレージ表に登録された各ノードのデータ保持値域を参照する。そして当該ノードは、自ノードの担当ノードを探し出して、その担当ノードに対してターゲットデータの検索要求を発行する。
【００７６】
即ち、メッセージ転送がノード間において行われる過程において、当該メッセージが担当ノードにたどり着く最後のメッセージ転送動作を除いて、それ以外の中間ノードを転々とするメッセージ転送動作は、個々の経路表の中の経路識別子を参照することによって行われる。そして、当該メッセージが担当ノードにたどり着く最後のメッセージ転送動作においては、担当ストレージ表を参照することによって行われる。
【００７７】
図１は、本発明の実施形態に係るデータ検索システムの構成を例示するブロック図である。図１に示すデータ検索システムは、ネットワークに接続された複数のノード１、２、３によって構成されている。本実施形態において、個々のノード（データ検索装置１００）は、計算機のＣＰＵにより実行されるプロセス（ソフトウェアプログラム・モジュール）である（詳細は、図９を参照して後述する）。
上述したように、個々のノードは、１台の計算機において複数のノードが仮想マシンとして実行される環境、１台の計算機に１つのノードが割り当てられる環境、或いはそれらの組み合わせの何れであってもよい。
【００７８】
以下の説明では、図１に例示する３つのノードのち、データ検索装置１００としてのノード３を例にノードの構成について説明する。ノード３は、大別して、通信部１０、ストレージ部２０、初期化・終了部３０、そしてメッセージ転送部４０を備える。 ストレージ部２０は、第１の実施形態における保持部（ストレージ部）３００に相当する。そしてメッセージ転送部４０は、第１の実施形態における転送部（メッセージ転送部）４００に相当する。尚、本実施形態において、ノード１、２は、ノード３と同様な構成を備えており、ノード３との通信が可能である。
【００７９】
＜ノード（データ検索装置１００）の構成＞
ノード３（データ検索装置１００）を構成する各部の構成と動作について以下に説明する。
【００８０】
通信部１０は、通信機能１１を備えている。通信機能１１は、ノード３が有する他の機能から、メッセージや、そのメッセージの宛先となる他ノードのネットワーク２００上の住所（アドレス）を与えられる。そしてノード３は、取得したメッセージを、当該住所に対応する他ノードに送信する。また、ノード３は、自ノードが参加しているオーバレイネットワークとは異なる外部のノードや装置、或いは自ノードが所参加しているオーバレイネットワークの他ノードからメッセージを受信する。そしてノード３は、受信したメッセージの内容に応じて、自ノードの適切な部ないし機能に当該メッセージを割り振る。
【００８１】
初期化・終了部３０は、参加機能３１と離脱機能３２とを備える。参加機能３１は、図１に示すネットワーク２００の上位に位置する概念的なオーバレイネットワーク（図１には不図示）に自ノードが参加する際に、ストレージ部２０およびメッセージ転送部４０を初期化する。離脱機能３２は、係るオーバレイネットワークから自ノードが離脱する際に、以下の動作を実行する。
【００８２】
即ち、離脱機能３２は、当該オーバレイネットワークに参加している他の必要なノードに、自ノードの離脱を通知する。また、離脱機能３２は、ストレージ部２０が管理するターゲットデータを、適切な他ノードに移譲する。更に、離脱機能３２は、メッセージ転送部４０がそれまで行っていたメッセージ転送の処理を停止する。また、離脱機能３２は、自ノード外部からのメッセージの受信を停止する。
【００８３】
（ストレージ部２０）
ストレージ部２０は、データアクセス機能２２、ストレージ識別子（ＳＩＤ）決定機能２３、隣接ストレージ維持機能２１、ＳＩＤ情報格納部２６、データ格納部２５、そして隣接ストレージ表２４を備える。
【００８４】
はじめに、ストレージ部２０が上記各機能を実行するに際して読み書きする情報（隣接ストレージ表２４、データ格納部２５、ＳＩＤ情報格納部２６）について説明する。
【００８５】
ＳＩＤ情報格納部２６は、ストレージ識別子と、そのストレージ識別子を基に決定されるデータ保持値域とを格納する。後述するＣｈｏｒｄアルゴリズムを用いた実施例では、あるノードのデータ保持値域は、自ノードのストレージ識別子（ＳＩＤ）の次に小さい他ノードのストレージ識別子から、自ノードのストレージ識別子までを表す値の範囲である。
【００８６】
データ格納部２５は、ノード３（自ノード）が保持するターゲットデータを格納する。本実施形態において、各ノードは、自ノードのデータ保持値域に属するデータＩＤを持つターゲットデータの担当ノードとなり、そのターゲットデータを保持する。ここで、データＩＤは、第１の実施形態における第３の識別子３０２に相当する。また、ターゲットデータは、第１の実施形態におけるターゲットデータ３０３に相当する。
【００８７】
隣接ストレージ表（図１１Ｂ）は、ストレージ識別子の値が自ノードの次に大きい他ノードと、あるいはストレージ識別子の値が自ノードの次に小さい他ノードとに関して、ストレージ識別子とネットワーク上のアドレスとを格納する。以降、このような他ノードを、本実施形態では“隣接ストレージ”と称する。
【００８８】
次に、ストレージ部２０が上記各種情報を読み書きしながら実行するところの、隣接ストレージ維持機能２１、データアクセス機能２２、そしてＳＩＤ決定機能２３について説明する。
【００８９】
データアクセス機能２２は、データ格納部２５に対してターゲットデータの登録や検索、削除を行う機能である。
【００９０】
隣接ストレージ維持機能２１は、隣接ストレージ表（図１１B）を定期的にヘルスチェックし、その結果、失効した経路情報があれば、適宜削除や書き換えを行う。
【００９１】
ＳＩＤ決定機能２３は、自ノードのストレージ識別子（ＳＩＤ）を決定し、決定したストレージ識別子をＳＩＤ情報格納部２６に格納する。決定方法は、ＤＨＴのアルゴリズムや、負荷分散の手順によって異なる。
【００９２】
（メッセージ転送部４０）
メッセージ転送部４０は、ＲＩＤ決定機能４１、ストレージ探索機能４２、経路表維持機能４３、担当ストレージ表維持機能４４、ＲＩＤ情報格納部４５、経路表４６、そして担当ストレージ表４７を備える。
【００９３】
はじめに、メッセージ転送部４０が上記各機能を実行するに際して読み書きする情報（ＲＩＤ情報格納部４５、経路表４６、担当ストレージ表４７）について説明する。
【００９４】
ＲＩＤ情報格納部４５は、経路識別子（ＲＩＤ）と、その経路識別子を基に決定される識別子値域とが格納される。経路識別子の決定方法は、実装態様やアルゴリズムによってさまざま異なるが、上述した関連技術と同様な技術を採用することができる。たとえば、ノード識別子の決定方法として、本実施形態では、ハッシュ関数の出力値を経路識別子として用いるなどの手法を適用可能である。本実施形態における以下の説明では、このような経路識別子の値域を“ストレージ索引値域”と呼ぶ。あるノードのストレージ索引値域は、自ノードの経路識別子（ＲＩＤ）から、最も距離が近い経路識別子を持つ他ノードまでを表す値の範囲である。尚、本実施形態では、同一ノードが格納するストレージ識別子と経路識別子とは、同じ識別子空間に存在するも、同値であるとは限らない。
【００９５】
経路識別子（ＲＩＤ）は、検索キーとなる各種識別子（データＩＤ、ＳＩＤ、あるいはＲＩＤ）を自ノードが受信したとき、次にメッセージを転送する他ノードを選ぶときに使用される。そこで、本実施形態における経路表（４６）には、複数のノードの経路識別子と、ネットワーク上のアドレスとが格納される。本実施形態において、自ノードは、メッセージと共に受け取ったキーの識別子（データ識別子、ＳＩＤ、あるいはＲＩＤ）までの距離が最も近い経路識別子を持つ他ノードを、当該メッセージの次の転送先として当該経路表から選択する（詳細は図１３Ａ乃至図１３Ｃを参照して後述する）。
【００９６】
ノード３の担当ストレージ表（４７）は、ノード３のストレージ索引値域に少なくとも一部が重なるようなデータ保持値域を持つ他ノードの、データ保持値域とネットワーク上のアドレスとを格納する。このため、自ノードのストレージ索引値域に検索キーの値が属するということは、担当ストレージ表に登録された複数のノード群において、いずれか一つのノードのデータ保持値域に検索キーが属することを表す。すなわち、受信したメッセージに含まれる検索キーが自ノードのストレージ索引値域に属するとき、自ノードは、担当ストレージ表の中に、当該検索キーに対応する担当ノードへの経路情報を必ず持っている。
【００９７】
次に、メッセージ転送部４０が上記各種情報を読み書きしながら実行するところの、ＲＩＤ決定機能４１、ストレージ探索機能４２、経路表維持機能４３、そして担当ストレージ表維持機能４４について説明する。
【００９８】
ストレージ探索機能４２は、検索キーを受け取ると、経路表４６および担当ストレージ表４７から適切なノードを探索し、探索によって見つけたノードへ当該検索キーを転送する。
【００９９】
経路表維持機能４３は、経路表４６のヘルスチェックを行い、その結果、失効した情報が見つかれば適宜削除や書き換えを行う。
【０１００】
担当ストレージ表維持機能４４は、担当ストレージ表４７のヘルスチェックを行い、その結果、失効した情報が見つかれば適宜削除や書き換えを行う。
【０１０１】
ＲＩＤ決定機能４１は、自ノードの経路識別子（ＲＩＤ）を決定すると共に、決定した経路識別子をＲＩＤ情報格納部に格納する。経路識別子の決定方法は、ＤＨＴのアルゴリズムや、どのような方針で各ノードにメッセージ転送を実行するかに依る。
【０１０２】
図１０は、本発明の第２の実施形態に係るデータ検索システムを、Ｃｈｏｒｄアルゴリズムに適用した動作例を説明する図である。図１０に示す例は、同一の識別子空間に、５つのノードａ〜ｅが存在している状態を表している。即ち、円環ａには、各ノードに分散配置されているターゲットデータの識別子（データＩＤ：ＤＩＤ）と、各ノードのストレージ識別子（ＳＩＤ）の値とが例示されている。一方、円環ｂには、当該各ノードの経路識別子（ＲＩＤ）の値が示されている。円環ａと円環ｂとは、同一の識別子空間を表わす。但し、図示と理解の利便性を考慮して、本実施形態では、データＩＤ（ＤＩＤ）およびストレージ識別子（ＳＩＤ）の分布の様子と、経路識別子（ＲＩＤ）の分布の様子とを、図１０に示す如く２つの円環に分けて表している。
【０１０３】
表２は、本実施形態において図１０に示す各ノードのデータ保持値域を例示する。また、表３は、本実施形態において図１０に示す各ノードのストレージ索引値域を例示する。図１０において、夫々のノードのストレージ識別子（ＳＩＤ）と経路識別子（ＲＩＤ）は、たまたま同じ値である例を示している。但し、Ｃｈｏｒｄでは、「背景技術」欄において説明したように、距離の定義が非対称である。このため、ラベルを付した夫々のノードについて表２及び表３を参照すると、これらの表において、データ保持値域とストレージ索引値域とは一致していないことが判る。そして、図１に示す各ノード内のＲＩＤ情報格納部４５には、表２に示すデータ保持領域のうち、ラベル（ノード名）に対応した情報が格納される。また、図１に示す各ノード内のＳＩＤ情報格納部２６には、表３に示すストレージ索引値域のうち、ラベル（ノード名）に対応した情報が格納される。尚、説明の便宜上、表２及び表３には、各ノードの値域をテーブル状にまとめて表現したが、実際の値域は、対応するノードが個別に有する。
【０１０４】
【表２】
【０１０５】
【表３】
【０１０６】
図１１Ａは、図１０における各ノードの担当ストレージ表を示す図である。担当ストレージ表で保持する経路情報（ＲＩＤ）は、ノードのデータ保持値域と住所のみで必要十分である。但し、同図に示す例では、説明の便宜上から、更にノードのラベル及びストレージ識別子（ＳＩＤ）を含む。
【０１０７】
図１１Ｂは、図１０における各ノードの隣接ストレージ表を示す図である。図１０に示す例では、各ノードの経路識別子は、図３に示すノード識別子と同値である。このため、図１０に示す各ノードの経路表は、図５（ａ）乃至図５（ｅ）に示した内容と同じである。ただし、ここではストレージ識別子に注目しているので、図５（ａ）乃至図５（ｅ）に示す表中のＮＩＤを、本実施形態においてはＲＩＤと見なして説明する。また、各ノードのストレージ識別子（およびデータ保持値域）も、図３に示した例におけるノードの識別子（データ保持値域）と同じ値であり、且つデータの分布の様子も同じである。このため、各ノードがデータ格納部に格納するデータは、図４（ａ）乃至図４（ｅ）に示す場合と同じであることとする。
【０１０８】
次に、上述した各機能を備えるデータ検索システム（図１）において、各ノードが実行する具体的な動作について詳細に説明する。以下の説明では、本実施形態に係るデータ検索システムの主要な動作（処理）として、（１）ターゲットデータを探索する動作、（２）オーバレイネットワークに新たにノードが参加する動作、（３）ネットワークからノードが離脱する動作、（４）ノード間における負荷分散動作、そして（５）経路識別子の変更動作、について順に説明する。また、以下の説明では、説明の便宜上から、図１に示すノード３が自ノードであると想定して説明する。
【０１０９】
＜ターゲットデータの探索動作＞
まず、ターゲットデータの探索動作について、図１５に示すフローチャートを参照して説明する。
【０１１０】
図１５は、本発明の第２の実施形態に係るデータ検索装置が実行するターゲットデータの探索処理を示すフローチャートである。図１５に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１１１】
ノード３（自ノード）は、検索キー（データ識別子）を含むメッセージを外部装置などから受け取るのに応じて、その検索キーが自ノードのデータ保持値域に属するか否かを、ＳＩＤ情報格納部２６を参照することによって判断する（ステップＳ１０１）。この判断において自ノードのデータ保持値域に当該検索キーが属すると判断した場合（ステップＳ１０１にてＹＥＳ）、ノード３は、その検索キーの担当ノードである。そこでノード３は、当該検索キーを利用して、自ノードのデータ格納部２５を探索（探索）する。そして、ノード３は、当該検索キーと一致するデータＩＤを持つターゲットデータがデータ格納部２５に格納されていると判断した場合、そのターゲットデータを、当該メッセージの送信元へ送る（ステップＳ１０５）。
【０１１２】
一方、自ノードのデータ保持値域に当該検索キーが属さないと判断した場合（ステップＳ１０１にてＮＯ）、ノード３は、当該検索キーが自ノードのストレージ索引値域に属するか否かを、ＲＩＤ情報格納部４５を参照することによって判断する（ステップＳ１０２）。この判断において自ノードのストレージ索引値域に当該検索キーが属さないと判断した場合（ステップＳ１０２にてＮＯ）、ノード３は、経路表（図５，４６）を参照することにより、当該検索キーまでの距離が最も近い経路識別子（ＲＩＤ）を持つ他ノードを選択し、選択した他ノードに当該メッセージを転送する（ステップＳ１０３）。
【０１１３】
これに対して、当該検索キーがストレージ索引値域に属すると判断された場合（ステップＳ１０２にてＹＥＳ）、担当ストレージ表（図１１Ａ）に登録された何れかの他ノードが、当該検索キーの担当ノードである。この場合、ノード３は、データ保持値域に当該検索キーが属する他ノードを、担当ストレージ表（図１１Ａ）の中から選択し、選択した他ノードに対して当該メッセージを転送する（ステップＳ１０４）。
【０１１４】
ここで、上述したターゲットデータの探索動作の、より具体的な動作例を、図５及び図１０を参照して説明する。今、ノードｃに、ネットワークの外部から、データＩＤ＝３のターゲットデータの検索要求メッセージが送られてきたとする（図１０に示す動作＜１＞）。ノードｃは、自ノードのＳＩＤ情報格納部２６（表２）を参照することによって、自ノードのデータ保持値域（２８、５６］を判断する。この例の場合、ノードｃは、係る判断の結果、自ノードがデータＩＤ３の担当ノードではないと判断する。次にノードｃは、自ノードのＲＩＤ情報格納部４５を参照することによって、自ノードのストレージ索引値域（表３）を判断する。この例の場合、ノードｃは、データＩＤ＝３が自ノードのストレージ索引値域（５６、６４］に属していないと判断する。そしてこの例の場合、ノードｃは、経路表４６（図５（ｃ））の中から、データＩＤ（ＤＩＤ）＝３までの距離が最も近い経路識別子１２１を持つノードｅを選択し、選択したノードｅに対して、当該メッセージを転送する（図１０に示す動作＜２＞）。尚、この説明においてもストレージ識別子に注目しているので、上述したように、図５（ａ）乃至図５（ｅ）に示す表中のＮＩＤは、本実施形態においてはＲＩＤと見なした説明である。
【０１１５】
ノードｅも上述したノードｃと同様な動作を実行する。即ち、ノードｅは、識別子３が自ノードのデータ保持値域（６４、１２１］およびストレージ索引値域（１２１、２］に属していないことを、ＳＩＤ情報格納部２６及びＲＩＤ情報格納部４５を参照することによって確認する。そして、ノードｅは、経路表４６（図５（ｅ））の中から、識別子３までの距離が最も近い経路識別子２に対応するノードａを選択し、選択したノードａに対して、当該メッセージを転送する（図１０に示す動作＜３＞）。
【０１１６】
そして、ノードａも上述したノードｃ及びｅと同様な動作を実行する。即ち、ノードａは、データＩＤ３がデータ保持値域（１２１、２］には属しておらず、ストレージ保持値域（２、２８］には属していると判断する。そこでノードａは、自ノードの担当ストレージ表４７（図１１Ａ（ａ））を参照することにより、データ保持値域にデータＩＤ３が属するノードｂを選択する。そしてノードａは、ノードｃがデータＩＤ３のターゲットデータを探していることを、ノードｂへ伝える（図１０に示す動作＜４＞）。ノードｂは、データ格納部２５からデータＩＤ３に対応するターゲットデータを読み出し、読み出したターゲットデータをノードｃへ送信する（図１０に示す動作＜５＞）。
【０１１７】
＜オーバレイネットワークへの参加動作＞
次に、オーバレイネットワークへのノードの参加動作について、図１６のフローチャートを参照して詳細に説明する。
【０１１８】
図１６は、本発明の第２の実施形態に係るデータ検索装置が実行するオーバレイネットワークへの参加処理を示すフローチャートである。図１６に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１１９】
ノード３（自ノード）は、まず、図１を参照して上述したＳＩＤ決定機能２３およびＲＩＤ決定機能４１により、ストレージ識別子（ＳＩＤ）および経路識別子（ＲＩＤ）を決定する（ステップＳ２０１）。つぎに、ノード３は、決定した経路識別子を検索キーとし、その検索キーから、あるいは検索キーまでの距離が最も近い経路識別子を持つ他ノードＸを探索する。係る条件を満たすノードが複数ある場合は、すべて探索する。そしてノード３は、探索した条件に合致する全ての他ノードＸから、他ノードＸの経路情報（経路識別子とネットワーク上のアドレス）を受け取り、自ノードの経路表４６に、他ノードＸの経路情報を登録する（ステップＳ２０２）。ノード３は、登録した他ノードＸの経路識別子を基に自ノードのストレージ索引値域を算出すると共に、算出したストレージ索引値域を、ＲＩＤ情報格納部４５に格納する（ステップＳ２０３）。
【０１２０】
さらに、ノード３は、自ノードの経路表４６に登録された他ノードの担当ストレージ表から、自ノードの担当ストレージ表に保持すべき経路情報を取得する。また、ノード３は、自ノードのストレージ識別子を検索キーに用いて、検索キーから、あるいは検索キーまでの距離が最も近いストレージ識別子を持つ他ノード（隣接ストレージ）を探索する。そしてノード３と当該隣接ストレージとは、互いの経路情報を、互いの隣接ストレージ表（図１１Ｂ）に登録する（ステップＳ２０４）。ノード３は、これら取得した隣接ストレージのストレージ識別子を基に、自ノードのデータ保持値域を算出し、ＳＩＤ情報格納部２６に格納する。
【０１２１】
また、ネットワークに新たに参加したノード３は、自ノードの経路情報を、適切な他ノードの担当ストレージ表に登録するよう、適切な他ノードに対して登録命令を発行する（ステップＳ２０５）。ここで、ノード３を担当ストレージ表に登録するべき適切な他ノードとは、先述の通り、ノード３のデータ保持値域と少なくとも一部が重なり合うようなストレージ索引値域を持つノードである。この動作は、担当ストレージ表の書き換え動作（図１７）として詳しく後述する。
【０１２２】
最後に、ノード３は、隣接ストレージ表に登録された他ノードのデータ格納部から、保持すべきデータを取得する（ステップＳ２０６）。
【０１２３】
ここで、担当ストレージ表の書き換え動作について、図１７に示すフローチャートを参照して説明する。
【０１２４】
図１７は、本発明の第２の実施形態に係るデータ検索装置が実行する担当ストレージ表の書き換え処理を示すフローチャートである。図１７に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１２５】
ステップＳ３０１：まず、登録命令（メッセージ）を出したいノード３は、自ノードのデータ保持値域の下限値を検索キーとし、その検索キーまでの距離が最も近い経路識別子を持つ他ノードを探索する。係る他ノードは、すなわち、ストレージ索引値域に検索キーが属する他ノードである。これは、ノード３のデータ保持値域と、当該他ノードのストレージ索引値域とが、少なくとも一部において重なっていることを意味する。このため、当該他ノードは、自ノードの担当ストレージ表に、ノード３の経路情報を登録すべきである。係る他ノードを発見したノード３は、すぐさま係る他ノードと通信を行い、ノード３の経路情報（ここではデータ保持値域とネットワーク上のアドレス）を、登録メッセージと共に送信する。
【０１２６】
ステップＳ３０２：メッセージを受信した当該他ノードは、自ノードの担当ストレージ表に、ノード３の経路情報を登録する。
【０１２７】
ステップＳ３０３：さらに、係る他ノードは、メッセージに含まれているノード３のデータ保持値域の上限値が、当該他ノード自身のストレージ索引値域に属しているかどうか確認する。当該上限値が係る他ノードのストレージ索引値域に属している場合（ステップＳ３０３にてＹＥＳ）、担当ストレージ表の書き換え動作は、終了である。一方、当該上限値が係る他ノードのストレージ索引値域に属していない場合（ステップＳ３０３にてＮＯ）は、係る他ノードは、自ノードのストレージ索引値域の上限値を経路識別子とする別の他ノードに対して、登録命令（メッセージ）を転送する。尚、ステップＳ３０３は、自ノードが上記他ノードとして動作する場合を想定して同一のフローチャートに記載した。
【０１２８】
ここで、オーバレイネットワークに新たなノードｆが参加するときの具体的な動作の流れについて、図５、図１３Ａから図１３Ｃ、図１４、図１６、図１７、並びに表４、表５を参照して説明する。
【０１２９】
【表４】
【０１３０】
【表５】
【０１３１】
図１３Ａから図１３Ｃは、本発明の第２の実施形態に係るデータ検索システムにおいて、オーバレイネットワークに新たなノードが参加する動作を説明する図である。図１４は、図１３Ａから図１３Ｃに示すオーバレイネットワークへの参加動作において各ノードが参照する担当ストレージ表を例示する図である。
【０１３２】
ノードｆは、オーバレイネットワークに新たに参加を希望しているノードである。まず、ノードｆは、ＳＩＤ決定機能２３及びＲＩＤ決定機能４１により、自ノードのストレージ識別子を９３（ＳＩＤ＝９３）、経路識別子の値を１５（ＲＩＤ＝１５）と決定する（図１６のステップＳ２０１）。本実施形態に係るデータ検索システムにおける前提として、新たに参加するノードは、既にオーバレイネットワークに参加している各ノードのうち、任意のあるノードの住所（ＩＰアドレスなど）を認識している。以下に説明する具体例では、ノードｆは、ノードａの住所を知っていることとする。また、ここでは、自ノードが持つ経路識別子の次に大きい経路識別子を持つ他ノードを、自ノードのサクセッサとする。
【０１３３】
ノードｆは、まず、自ノードの経路表４６に、必要最低限の経路情報として、自ノードのサクセッサを登録する処理を行う（図１６のステップＳ２０２）。サクセッサを探すため、ノードｆは、自ノードの経路識別子の値１５を検索キーとし、その検索キーを用いて、当該値１５から最も距離が近い経路識別子を持つノードを探すよう、ノードａに命令を送信する（図１３Ａに示す動作＜１＞）。ノードａは、自ノードの経路表（図５（ａ））を参照することにより、経路識別子の値が１５から最も近い経路識別子を持つノードｂを選択する。ここで、ノードｂは、ノードａのサクセッサである。従って、ノードａは、ノードｂ以上には経路識別子の値１５から近い距離に存在するノードが他に存在しないことを認識する。
【０１３４】
そして、ノードａは、ノードｆがネットワークへの参加手続きを希望していることをノードｂに伝える（図１３Ａに示す動作＜２＞）。知らせを受けたノードｂは、ノードｆと通信し、ノードｂの経路情報（ここでは経路識別子とネットワーク上のアドレス）を送信する（図１３Ａに示す動作＜３＞）。ノードｆは、受け取った経路情報を経路表に登録する。また、ノードａは、上記の一連の処理から、ノードｆが自ノードの新たなサクセッサになったことを認識することができるので、ノードｆの経路情報を、自ノードの経路表に登録する。
【０１３５】
次に、ノードｆは、自ノードの担当ストレージ表に、適切な経路情報を登録する処理を行う（図１６のステップＳ２０３）。ノードｆのストレージ索引値域（表５）は、それまでノードａのストレージ索引値域であった値域の一部である。すなわち、ノードｆは、ノードａの担当ストレージ表に登録されている経路情報の適切な一部を、ノードｆが管理すべき経路情報として受け取れば十分である。そこで、ノードｆはノードａと通信を行い、ノードａの担当ストレージ表に登録されている経路情報の中から、ノードｆのストレージ索引値域と重なるようなデータ保持値域（表４）を持つノードの経路情報を、ノードａから受け取り、ノードｆの担当ストレージ表に登録する。
【０１３６】
さらに、ノードｆは、隣接ストレージ表２４に自ノードの隣接ストレージの経路情報（ここではストレージ識別子とネットワーク上のアドレス）を登録する処理を行う（図１６のステップＳ２０４）。隣接ストレージを探すため、ノードｆは、自ノードのストレージ識別子の値９３を検索キーに用いて、値９３からの距離が最も近いストレージ識別子を持つノード（すなわち隣接ストレージ）を探索するメッセージを、ノードａに送信する（図１３Ｂに示す動作＜４＞）。これまでと同様、メッセージを受け取ったノードａは、自ノードの経路表４６を用いてメッセージを真の宛先までリレーしていく。この例では、当該メッセージは、図１３Ｂに示す動作＜５＞及び動作＜６＞のように転送され、最後にノードｄへたどり着く。ノードｄは、自ノードの経路表に登録された他ノードおよび自ノード自身の経路識別子と、検索キー９３とを夫々比較して、自ノードの経路識別子から検索キー９３までの距離が、もっとも最短であることを認識する。ノードｄは、担当ストレージ表の中に、ノードｆの隣接ストレージとなるべき他ノードへの経路情報を保持していることになる。
【０１３７】
そこで、ノードｄは、自ノードの担当ストレージ表（図１３Ｄに示す（ｄ））を参照することにより、検索キー９３が属するようなストレージ索引値域を持つ他ノード（ここではノードｅ）を探す。そして、ノードｄは、ノードｅに対して、ノードｆが隣接ストレージを探していることをメッセージによって伝える（図１３Ｂに示す動作＜７＞）。このメッセージを受けたノードｅは、ノードｆと通信を行い、互いの経路情報（ここではストレージ識別子とネットワーク上のアドレス）を、互いの隣接ストレージ表に登録する（図１３Ｂに示す動作＜８＞）。
【０１３８】
また、ノードｆは、自ノードの経路情報を、適切な他ノードの担当ストレージ表に登録してもらう処理を行う（図１６のステップＳ２０５）。図１７のステップＳ３０１に従い、ノードｆは、表４を参照することにより、自ノードのデータ保持値域の下限値（データ保持値域に属する最小の値）６５を検索キーとし、検索キーまでの距離が最も近い経路識別子を持つ他ノードを探すため、経路表を用いて検索キーを含むメッセージを転送する。現在、ノードｆの経路表には唯一ノードｂが登録されているので、メッセージはノードｂへ転送される（図１３Ｂに示す動作＜９＞）。メッセージを受け取ったノードｂは、当該メッセージに含まれる検索キー値６５までの距離が最も近い経路識別子を持つ他ノードを、ノードｂ自身および経路表の中から選択する。まだいずれのノードにおいても経路表のヘルスチェックが行われていないと仮定すると、ノードｂは、図５（ｂ）に示す経路表からノードｄを選び、メッセージを転送する。ノードｄは、自ノード自身および経路表の中から、検索キー６５までの距離が最も近い経路識別子を持つノードｄを選択することで、自ノードが最も検索キー６５までの距離が近いと判断する。そして、ノードｄは、ノードｆと通信し、自ノードがノードｆの探しているノードであることを教える。
【０１３９】
ノードｆは、ノードｄへ、自ノードのデータ保持値域とともに、登録命令の書かれたメッセージを送信する。メッセージを受信したノードｄは、共に受け取ったノードｆのデータ保持値域とネットワーク上のアドレスを経路情報として、ノードｄの担当ストレージ表に登録する（図１７のステップＳ３０２）。
【０１４０】
さらに、図１７のステップＳ３０３に従い、ノードｄは、ノードｆのデータ保持値域の上限値９３が、ノードｄのストレージ索引値域に属しているか判定する。この判定は真であるため、図１７に従い、適切なノードの担当ストレージ表への登録（書き換え）処理は終了する。
【０１４１】
最後に、図１６のステップＳ２０６に従い、ノードｆは、自ノードの隣接ストレージであるノードｅから、自ノードが保持すべきターゲットデータ（ＩＤ＝６４〜８２）を受け取る。このような一連の動作を経て、ノードｆは、オーバレイネットワークに新たに参加することにより、図１３Ｃに示す状態が実現する。
【０１４２】
＜ネットワークからの離脱動作＞
次に、ノードがネットワークから離脱する動作について、図１８に示すフローチャートを参照して説明する。
【０１４３】
図１８は、本発明の第２の実施形態に係るデータ検索装置が実行するネットワークからの離脱処理を示すフローチャートである。図１８に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１４４】
離脱対象のノードは、まず保持しているターゲットデータを、隣接ストレージ表（図１１Ｂ）に登録されている隣接ストレージへ移譲する（ステップＳ４０１）。次に、離脱対象のノードは、自ノードのストレージ索引値域の下限値及び上限値を、ＳＩＤ情報格納部２６から参照し、その下限値あるいは上限値を経路識別子に持つ他ノードを探索する。そして、離脱対象のノードは、自ノードの担当ストレージ表（図１１Ａ）に登録されている経路情報を、探索によって求めた当該他ノードに移譲する（ステップＳ４０２）。そして、当該離脱対象のノードは、ネットワークから離脱する（ステップＳ４０３）。尚、離脱対象のノードの指定は、例えば、ノードへ離脱を命令できる権限のあるユーザが、当該ノードへ離脱の命令が書かれたメッセージを送信するなどによって行えば良い。
【０１４５】
＜負荷分散動作＞
次に、ネットワークに参加しているノード間において負荷を分散する負荷分散動作について、図１９に示すフローチャートを参照して説明する。
【０１４６】
図１９は、本発明の第２の実施形態に係るデータ検索装置が実行する負荷分散処理を示すフローチャートである。図１９に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１４７】
ノードは、何らかの手段により自ノードの負荷が高いと判断すると（ステップＳ５０１にてＮＯ）、図１を参照して上述したＳＩＤ決定機能２３により、新たなストレージ識別子およびデータ保持値域を決定する（ステップＳ５０２）。
【０１４８】
上記の決定によってストレージ識別子を変更したため、自ノードの隣接ストレージは、決定前と異なっている可能性がある。そこで当該ノードは、係る新たなストレージ識別子を用いて、隣接ストレージ表（図１１Ｂ）の経路情報（ここではストレージ識別子とネットワーク上のアドレス）のヘルスチェックを行う（ステップＳ５０３）。その結果、自ノードの新たなストレージ識別子に対して、現在登録されている他ノードがもはや隣接ストレージの条件を満たさないと判定した場合、当該自ノードは、当該他ノードを隣接ストレージ表から削除する（ステップＳ５０３）。
【０１４９】
さらに自ノードは、新たなストレージ識別子を検索キーとして含むメッセージを発行することで、検索キーと数値的に隣り合うストレージ識別子を持つ他ノードを新たな隣接ストレージとして探索し、探索結果を隣接ストレージ表に登録する。次に、当該自ノードは、負荷分散に応じてデータ保持値域が変わるので、必要な全ての他ノードに対して、担当ストレージ表の書き換えを行わせる必要がある。そこで、図１７に示す、担当ストレージ表の書き換え動作のフローチャートに従い、当該ノードは、新たなデータ保持値域に基づき、保持すべきデータは保持し、他ノードへ移譲すべきノードは移譲する（ステップＳ５０４）。
【０１５０】
更に当該ノードは、変更したデータ保持値域の下限値を検索キーとし、その検索キーまでの距離が最も近い経路識別子を持つ他ノードを探索する。当該ノードは、探索した他ノードへ、自ノードのデータ保持値域の情報と共に、担当ストレージ表（図１１Ａ）への登録命令を送信する（ステップＳ５０５）。
【０１５１】
ここで、上述した負荷分散動作について、より具体的に説明する。本実施形態において例示しているノードｅは、図４等を参照して上述したように、保持しているターゲットデータ数が他のノードに比べて多いので負荷が高い。そこで、以下の具体例では、インターバルシフトによる負荷分散について説明する。
【０１５２】
図１２は、本発明の第２の実施形態に係るデータ検索システムにおいて、高負荷な状態にあるノードｅから負荷分散を行うときの動作の流れを説明する図である。はじめに、ノードｅは、隣接ストレージ表（図１１Ｂに示す（ｅ））に登録された他ノード（隣接ストレージ）と通信を行い、ターゲットデータの譲渡先となるノード（ここではノードａとする）を、どの隣接ストレージにするか決める。ここで、隣接ストレージの決定方法としては、様々な方法が考えられる。例えば、ノード識別子を変更することで負荷分散を行う関連技術を採用すると共に、負荷の高いノードがターゲットデータの移譲先を決定する方法を採用することができる。
【０１５３】
ノードｅは、ノードａにターゲットデータを譲渡すべく、ストレージ識別子（ＳＩＤ）の値を９３に、データ保持値域を（６４、９３］に、それぞれ変更する（図１２に示す円環ａ）。次に、ノードｅは、ノードａへ、ストレージ識別子を９３に変更したことを伝える。これに応じてノードａは、自ノードのデータ保持値域を、当初の（１２１、２］（表２）から、（９３、２］に広げる変更を行う。これによりノードａは、当初はノードｅが保持していたデータ識別子１０３〜１１９のターゲットデータ（図４（ｅ））を、ノードｅから受け取る。
【０１５４】
ノードｅおよびノードａは、夫々のデータ保持値域を変更したため、適切な他ノードに対して、担当ストレージ表の書き換えを依頼する必要がある。そこで、ノードｅは、図１７に示すフローチャートに従い、担当ストレージ表の書き換え処理を実行する。即ち、ノードｅは、新たなデータ保持値域（６４、９３］の下限（最小値）６５を検索キーとし、値６５をストレージ索引値域に含むようなノードを探索する。そしてノードｅは、探索により求めた他ノードに対して、自ノードのデータ保持値域の情報と共に、担当ストレージ表の書き換え命令をメッセージとして送信する。
【０１５５】
経路表（図５）を用いて当該キーまでの距離が最も近づくようにメッセージ転送を行えば、メッセージは、図１２に示す動作＜１＞のように、ノードｄに転送される。ノードｄは、検索キー値６５が自ノードのストレージ索引値域（６４、１２１］に含まれている（表３）。このためノードｄは、自ノードの担当ストレージ表（図１１Ａ）の中の、ノードｅの経路情報を書き換える。
【０１５６】
上述した具体例におけるノードｅの変更後のデータ保持値域（６４、９３］の上限９３は、ノードｄの変更後のストレージ索引値域（６４、１２１］に属している。このため、ノードｄは、メッセージをそれ以上他ノードに転送する必要がない。
【０１５７】
一方、ノードａもまた、変更が生じた自ノードのデータ保持値域(９３、２]の下限（最小値）９４を検索キーに用いて、値９４をストレージ索引値域に含むノードを探し、自ノードのデータ保持値域の情報と共に、担当ストレージ表の書き換え命令をメッセージとして送信する。
【０１５８】
経路表（図５）を用いて当該検索キーまでの距離が最も近づくようにメッセージ転送を行えば、メッセージは、図１２に示す動作＜２＞及び動作＜３＞のように転送され、ノードｄに辿り着く。ノードｄは、自ノードの担当ストレージ表のノードａの情報を書き換える。さらに、ノードａのデータ保持値域の上限値２は、ノードｄのストレージ索引値域（６４、１２１］に属していない（表３）。このためノードｄは、メッセージを、ストレージ索引値域の上限の担当ノード（すなわち、Ｃｈｏｒｄでは自ノードのサクセッサ）であるノードｅに転送する（図１２に示す動作＜４＞）。ノードｅは、メッセージに従い、自ノードの担当ストレージ表を書き換える。ノードａのデータ保持値域の上限値２は、ノードｅのストレージ索引値域（１２１、２］に属しているので、ノードｅはメッセージを転送する必要がない。
【０１５９】
＜経路識別子の変更動作＞
ところで、経路表（４６）に登録された経路情報の数を減らしたい、或いはノード間でできるだけ経路表の大きさを均一にしたい、などの目的で、経路識別子を変更したい場合がある。本実施形態における経路識別子の変更は、図２０に示すフローチャートのように動作する。
【０１６０】
図２０は、本発明の第２の実施形態に係るデータ検索装置が実行する経路識別子の変更処理を示すフローチャートである。図２０に示す各ステップは、データ検索装置１００（ノード３）のＣＰＵがソフトウェア・プログラムを実行することによって実現する処理機能である（詳細は、図９を参照して後述する）。
【０１６１】
ステップＳ６０１：まず、経路識別子を変更したいノードは、自ノードの経路識別子の値を変更する。
【０１６２】
ステップＳ６０２：次に、変更した経路識別子を検索キーに用いて、当該ノードは、当該変更後の経路識別子から（まで）の距離が最も近い経路識別子を持つ他ノードを探索する。そして、当該ノードは、探索によって見つけた他ノードに応じて、経路表に必要な情報を登録する。
【０１６３】
ステップＳ６０３：さらに、当該自ノードは、経路表に登録された他ノードから、ストレージ索引値域を算出する。自ノードは、新たに算出されたストレージ索引値域と重なりあうデータ保持値域を持つ他ノードを、担当ストレージ表に登録する必要がある。担当ストレージ表に登録すべき経路情報は、自ノードの経路識別子と数値的に隣り合う他ノード（すなわち、先ほど経路表に登録した他ノード）が保持しているため、当該他ノードから係る経路情報を取得する。
【０１６４】
＜ハードウェア構成＞
次に、第１及び第２の実施形態において上述したデータ検索装置（ノード）が実行されるハードウェア環境について、図９を参照して説明する。上述したように、各実施形態において説明したデータ検索装置（ノード）は、サーバなどのコンピュータによって実行されるプロセスとして捉えることができる。係るデータ検索装置の機能は、ソフトウェアプログラムを、コンピュータのＣＰＵが実行することによって実現される。そして、上述した各実施形態において図面に示した各機能は、ソフトウェアプログラムの機能単位（ソフトウェアモジュール）と捉えることができる。この場合のハードウェア環境の一例を、図９を参照して説明する。
【０１６５】
図９は、本発明の第１及び第２の実施形態に係るデータ検索装置のハードウェア構成を例示的に説明する図である。図９に示したハードウェアは、ＣＰＵ１０１、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）１０２、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１０３、ハードディスク（記憶装置）１０４、通信インタフェース１０５を備え、これらの構成がバス１０６を介して接続された一般的なコンピュータである。通信インタフェース（Ｉ／Ｆ）１０５は、図１に示した通信部１０に対応しており、ネットワーク２００を介して、自装置（自ノード）と外部装置（他ノードなど）との通信を実現する。ここで、ハードディスク１０４は、上述した図１に示す隣接ストレージ表２４、データ格納部２５、ＳＩＤ情報格納部２６、ＲＩＤ情報格納部４５、経路表４６、及び担当ストレージ表４７を実現する記憶装置として機能する。
【０１６６】
そして、上述した各実施形態を例に説明したデータ検索装置１００（ノード）は、図９に示したハードウェアに対して、その説明において参照したブロック構成図（図１、図２１）或いはフローチャート（図１５乃至図２０）の機能を実現可能なコンピュータプログラムを供給した後、そのコンピュータプログラムを、当該ハードウェアのＣＰＵ１０１に読み出して実行することによって達成される。また、当該装置内に供給されたコンピュータプログラムは、読み書き可能なメモリ（１０３）またはハードディスク装置（１０４）等の記憶デバイスに格納すれば良い。
【０１６７】
尚、上記の例では、説明の便宜上から、１台のコンピュータが１つのノード（データ検索装置）を実現する構成を説明したがこの構成には限られない。即ち、上述した各実施形態を例に説明したデータ検索装置１００（ノード）は、１台のコンピュータが複数の仮想マシンを実現する構成を実行環境として、当該１台のコンピュータが複数のノード（プロセス）を実現する構成であってもよい（尚、仮想マシンを利用する場合については後述する実施例にて詳述する）。但し、データ検索装置１００は、専用のハードウェアによって実現してもよい。
【０１６８】
また、前記の場合において、当該ハードウェア内へのコンピュータプログラムの供給方法は、ＣＤ−ＲＯＭ等の各種記録媒体を介して当該装置内にインストールする方法や、インターネット等の通信回線を介して外部よりダウンロードする方法等のように、現在では一般的な手順を採用することができる。そして、このような場合において、本発明は、係るコンピュータプログラムのコード或いは記憶媒体によって構成される。
【０１６９】
＜実施形態の効果＞
以上説明した第１及び第２の実施形態に係るデータ検索装置（ノード）及びそれらが複数接続されたデータ検索システムによれば、ノード間においてターゲットデータを管理するに際して、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現することができる。
【０１７０】
即ち、本実施形態では、例えばあるノードにおける負荷を分散する必要が生じ、そのノードのストレージ識別子（ＳＩＤ）を変更したとしても、経路表の情報が失効することが無いので、安定したメッセージ転送が実現する。
【０１７１】
また、本実施形態によれば、経路識別子（ＲＩＤ）を変更することも可能である。即ち、メッセージの中継ノードに選ばれる確率にノード間において大きな差があり、これに応じてノードのリソースに無駄が生じている場合がある。このような場合、本実施形態によれば、各ノードの経路識別子を、識別子空間上において可能な限り分散するように割り当て直すことにより、当該確率を、ノード間で均一にすることができる。これに対して、「発明の背景」欄で説明した関連技術では、各ノードが一つの識別子のみを用いてターゲットデータの保持とメッセージ転送とを実行するため、負荷の観点から困難であった。換言すれば、ノード間において、メッセージ転送を全く行わないノードは、リソースを持て余してしまうので、そのようなノードは無くすることが求められる。この要求に対して、関連技術では、ヘテロな環境であればあるほど、負荷を分散すると、データ保持値域の広さがノード間でバラついてしまい、結果として、識別子空間上で複数のノードが極端に近い場所に密集する状況が生じる。この場合、密集したノード群には、確率的に、メッセージがほとんど転送されることはない。このような問題を解消する観点からは、メッセージ転送の際に参照する識別子は、ノード間において均等に離散していることが望ましい。この関係は、上述した関連技術においては、ヘテロな環境において負荷分散とトレードオフの関係であった。これに対して、本実施形態によれば、２種類の識別子（ＲＩＤ，ＲＩＤ）を用いて、個々のターゲットデータの柔軟な配置と、安定したメッセージ転送とを実現する訳である。
【実施例】
【０１７２】
上述した実施形態では、負荷分散の１つのアプローチとして、インターバルシフトを用いた。しかしながら、上述した実施形態を例に説明した本発明は、識別子の値を変更することで負荷の分散を図る各種のアプローチに有効である。このため、本発明に係るデータ検索システムは、仮想サーバ、仮想ノード等と呼ばれる仮想マシン（仮想マシン環境）にも適用可能である。
【０１７３】
ここで、仮想マシン環境に本発明を適用した場合について説明する。この場合、既にオーバレイネットワークに参加しているノードのうち、リソースに余裕のあるノードを実現しているＣＰＵは、負荷を分散すべく、新たなプロセスを実行することによって別ノードを作り、当該別ノードをオーバレイネットワークに参加させる。但し、仮想マシンでは、一般に、１つのＣＰＵが複数のノードを実現するため、メッセージがノード間を中継される際に、実際は同じ計算機（物理マシン）の中で何度も中継されるという問題がある。このような問題が生じる仮想マシン環境に対して、本発明に係るデータ検索システムを適用する場合、ストレージ索引値域が限りなく小さくなるように経路識別子を決定すれば、同じメッセージが何度も同一ノードに転送されてくることを阻止することができるので、上記の問題が解消できるという利点がある。
【０１７４】
さらに、上述した実施形態では、Ｃｈｏｒｄアルゴリズムを例に説明した。しかしながら本発明は、Ｃｈｏｒｄアルゴリズムだけでなく、Ｃｈｏｒｄと同様に識別子空間がリング型であるＫｏｏｒｄｅアルゴリズムにも適用可能である。ここで、Ｋｏｏｒｄｅアルゴリズムは、仮想的なｄｅ Ｂｕｒｕｉｊｎグラフ上のノード（イマジナリノード）を、目的キーに対応するノードに近づけるようシミュレートしながら、オーバレイネットワーク上で自ノードのデータ保持値域にイマジナリノードが含まれるよう、経路を辿っていくアルゴリズムである。本発明は、係るイマジナリノードを経路識別子として用いることで、Ｋｏｏｒｄｅアルゴリズムにも適用可能である。
【産業上の利用可能性】
【０１７５】
本発明は、ネットワークに接続した計算機群に対して、各ＣＰＵがプロセスとして動かすノードへデータを分散して管理する分散型のデータ検索システムに適用可能である。ここで想定するネットワークは、例えば、インターネットなどの広域なものから、データセンタ内部の比較的閉じたネットワークなどが挙げられる。分散配置された情報のメタデータ（例えばどのデータベースにその情報があるなどの位置情報）を、上述した実施形態及びその実施例にて説明した如く管理すれば、分散型のインデックスとして適用することができる。また、広域でのコンテンツ配信システムにも適用できる。コンテンツ配信システムとしては、映画やテレビ映像、ビデオの配信などが想定される。
【０１７６】
尚、上記の実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
【０１７７】
（付記１）
管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノードにおいて管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するデータ検索システムであって、
各ノードは、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子（ストレージ識別子（ＳＩＤ））と、
メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子（経路識別子（ＲＩＤ））とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子（データＩＤ（ＤＩＤ））によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報（経路表）を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするデータ検索システム。
【０１７８】
（付記２）
前記各ノードの転送手段は、
前記メッセージを受信するのに応じて、自ノードが保持する前記経路情報を参照した結果に応じてノード間においてメッセージの転送を繰り返すことにより、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子（経路識別子）を持つ特定ノードに対して、前記メッセージを転送する
ことを特徴とする付記１記載のデータ検索システム。
【０１７９】
（付記３）
前記複数のノードは、
自ノードが担当するストレージに関する情報（担当ストレージ表）を有しており、
前記特定ノードの転送手段は、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする付記２記載のデータ検索システム。
【０１８０】
（付記４）
前記ストレージに関する情報は、
自ノードの前記第２の識別子（経路識別子）から、最も距離が近い前記第２の識別子を持つ他ノードまでを表す値の範囲（ストレージ索引値域）に、少なくとも一部が重なるようなターゲットデータの保持値域を持つ他ノードに関して、ターゲットデータの保持値域と、前記複数のノードが接続された通信ネットワーク上のアドレスとを含む
ことを特徴とする付記３記載のデータ検索システム。
【０１８１】
（付記５）
前記複数のノードのうち、第１ノードが保持するターゲットデータを第２ノードに配置するに際して、該第１ノードの転送手段は、前記第２の識別子の変更に応じて、前記経路情報に登録すべき情報を変更することの契機とする
ことを特徴とする付記１乃至付記４の何れかに記載のデータ検索システム。
【０１８２】
（付記６）
前記複数のノードのうち、第１ノードが保持するターゲットデータを第２ノードに分散するに際して、該第１ノードの転送手段は、前記第１の識別子と、その第１ノードによるターゲットデータの保持値域とを新たな値に更新することの契機とする
ことを特徴とする付記１乃至付記４の何れかに記載のデータ検索システム。
【０１８３】
（付記７）
管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノードにおいて管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するデータ検索方法であって、
各ノードに、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子（ストレージ識別子（ＳＩＤ））と、
メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子（経路識別子（ＲＩＤ））と
を保持させ、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子（データＩＤ（ＤＩＤ））によって特定されるターゲットデータを保持させ、
前記第２の識別子が含まれる経路情報（経路表）を用いて、メッセージを転送すべき他ノードを決定するに際して、前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするデータ検索方法。
【０１８４】
（付記８）
前記各ノードがメッセージを転送する過程において、
前記メッセージを受信するのに応じて、自ノードが保持する前記経路情報を参照した結果に応じてノード間においてメッセージの転送を繰り返すことにより、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子（経路識別子）を持つ特定ノードに対して、前記メッセージを転送する
ことを特徴とする付記７記載のデータ検索方法。
【０１８５】
（付記９）
前記複数のノードに、
自ノードが担当するストレージに関する情報（担当ストレージ表）を保持させ、
前記特定ノードは、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする付記８記載のデータ検索方法。
【０１８６】
（付記１０）
管理対象である複数のターゲットデータを、オーバレイネットワーク上において管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するノードであって、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子（ストレージ識別子（ＳＩＤ））と、
メッセージを受信した際、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子（経路識別子（ＲＩＤ））とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子（データＩＤ（ＤＩＤ））によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報（経路表）を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするノード。
【０１８７】
（付記１１）
自ノードが担当するストレージに関する情報（担当ストレージ表）を有しており、
自ノードが、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子（経路識別子）を持つ特定ノードである場合に、前記転送手段は、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする付記１０記載のノード。
【０１８８】
（付記１２）
管理対象である複数のターゲットデータを、オーバレイネットワーク上において管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するノードとして、コンピュータを動作させるコンピュータプログラムであって、そのコンピュータプログラムにより、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子（ストレージ識別子（ＳＩＤ））と、
メッセージを受信した際、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子（経路識別子（ＲＩＤ））とを保持する機能と、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子（データＩＤ（ＤＩＤ））によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報（経路表）を用いて、メッセージを転送すべき他ノードを決定する転送機能とを実現すると共に、
前記転送機能により、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするコンピュータプログラム。
【符号の説明】
【０１８９】
１０ 通信部
１１ 通信機能
２０ ストレージ部
２１ 隣接ストレージ維持機能
２２ データアクセス機能
２３ ストレージ識別子（ＳＩＤ）決定機能
２４ 隣接ストレージ表
２５ データ格納部
２６ ＳＩＤ情報格納部
３０ 初期化・終了部
３１ 参加機能
３２ 離脱機能
４０ メッセージ転送部
４１ ＲＩＤ決定機能
４２ ストレージ探索機能
４３ 経路表維持機能
４４ 担当ストレージ表維持機能
４５ ＲＩＤ情報格納部
４６ 経路表
４７ 担当ストレージ表
１００ ノード（データ検索装置）
２００ ネットワーク
３００ 保持部（ストレージ部）
３０１ 第１の識別子（ストレージ識別子（ＳＩＤ））
３０２ 第３の識別子（データＩＤ（ＤＩＤ））
３０３ ターゲットデータ
４００ 転送部（メッセージ転送部）
４０１ 第２の識別子（経路識別子（ＲＩＤ））
４０２ 経路情報（経路表）
【特許請求の範囲】
【請求項１】
管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノードにおいて管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するデータ検索システムであって、
各ノードは、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするデータ検索システム。
【請求項２】
前記各ノードの転送手段は、
前記メッセージを受信するのに応じて、自ノードが保持する前記経路情報を参照した結果に応じてノード間においてメッセージの転送を繰り返すことにより、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子を持つ特定ノードに対して、前記メッセージを転送する
ことを特徴とする請求項１記載のデータ検索システム。
【請求項３】
前記複数のノードは、
自ノードが担当するストレージに関する情報を有しており、
前記特定ノードの転送手段は、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする請求項２記載のデータ検索システム。
【請求項４】
前記ストレージに関する情報は、
自ノードの前記第２の識別子から、最も距離が近い前記第２の識別子を持つ他ノードまでを表す値の範囲に、少なくとも一部が重なるようなターゲットデータの保持値域を持つ他ノードに関して、ターゲットデータの保持値域と、前記複数のノードが接続された通信ネットワーク上のアドレスとを含む
ことを特徴とする請求項３記載のデータ検索システム。
【請求項５】
管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノードにおいて管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するデータ検索方法であって、
各ノードに、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子と
を保持させ、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持させ、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定するに際して、前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするデータ検索方法。
【請求項６】
前記各ノードがメッセージを転送する過程において、
前記メッセージを受信するのに応じて、自ノードが保持する前記経路情報を参照した結果に応じてノード間においてメッセージの転送を繰り返すことにより、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子を持つ特定ノードに対して、前記メッセージを転送する
ことを特徴とする請求項５記載のデータ検索方法。
【請求項７】
前記複数のノードに、
自ノードが担当するストレージに関する情報を保持させ、
前記特定ノードは、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする請求項６記載のデータ検索方法。
【請求項８】
管理対象である複数のターゲットデータを、オーバレイネットワーク上において管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するノードであって、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信した際、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするノード。
【請求項９】
自ノードが担当するストレージに関する情報を有しており、
自ノードが、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子を持つ特定ノードである場合に、前記転送手段は、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする請求項９記載のノード。
【請求項１０】
管理対象である複数のターゲットデータを、オーバレイネットワーク上において管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するノードとして、コンピュータを動作させるコンピュータプログラムであって、そのコンピュータプログラムにより、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信した際、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを保持する機能と、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定する転送機能とを実現すると共に、
前記転送機能により、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするコンピュータプログラム。
【請求項１】
管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノードにおいて管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するデータ検索システムであって、
各ノードは、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするデータ検索システム。
【請求項２】
前記各ノードの転送手段は、
前記メッセージを受信するのに応じて、自ノードが保持する前記経路情報を参照した結果に応じてノード間においてメッセージの転送を繰り返すことにより、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子を持つ特定ノードに対して、前記メッセージを転送する
ことを特徴とする請求項１記載のデータ検索システム。
【請求項３】
前記複数のノードは、
自ノードが担当するストレージに関する情報を有しており、
前記特定ノードの転送手段は、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする請求項２記載のデータ検索システム。
【請求項４】
前記ストレージに関する情報は、
自ノードの前記第２の識別子から、最も距離が近い前記第２の識別子を持つ他ノードまでを表す値の範囲に、少なくとも一部が重なるようなターゲットデータの保持値域を持つ他ノードに関して、ターゲットデータの保持値域と、前記複数のノードが接続された通信ネットワーク上のアドレスとを含む
ことを特徴とする請求項３記載のデータ検索システム。
【請求項５】
管理対象である複数のターゲットデータを、オーバレイネットワーク上に配置された複数のノードにおいて管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するデータ検索方法であって、
各ノードに、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信したノードが、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子と
を保持させ、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持させ、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定するに際して、前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするデータ検索方法。
【請求項６】
前記各ノードがメッセージを転送する過程において、
前記メッセージを受信するのに応じて、自ノードが保持する前記経路情報を参照した結果に応じてノード間においてメッセージの転送を繰り返すことにより、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子を持つ特定ノードに対して、前記メッセージを転送する
ことを特徴とする請求項５記載のデータ検索方法。
【請求項７】
前記複数のノードに、
自ノードが担当するストレージに関する情報を保持させ、
前記特定ノードは、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする請求項６記載のデータ検索方法。
【請求項８】
管理対象である複数のターゲットデータを、オーバレイネットワーク上において管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するノードであって、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信した際、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを有しており、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定する転送手段とを備え、
前記転送手段は、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするノード。
【請求項９】
自ノードが担当するストレージに関する情報を有しており、
自ノードが、前記検索キーが表す識別子までの距離が最も小さい前記第２の識別子を持つ特定ノードである場合に、前記転送手段は、
自ノードの前記ストレージに関する情報を参照することにより、自ノードが担当する担当ノードを探し出し、その担当ノードに対してターゲットデータの検索要求を発行する
ことを特徴とする請求項９記載のノード。
【請求項１０】
管理対象である複数のターゲットデータを、オーバレイネットワーク上において管理すると共に、移動対象のターゲットデータの移動に先立って、該移動対象のターゲットデータの異動先のノードを、メッセージを用いて検索するノードとして、コンピュータを動作させるコンピュータプログラムであって、そのコンピュータプログラムにより、
自ノードが保持すべきターゲットデータの値域を求めるための第１の識別子と、
メッセージを受信した際、そのメッセージを他ノードに転送する転送経路の決定に用いる第２の識別子とを保持する機能と、
前記第１の識別子を基に決定した値域に属するところの、第３の識別子によって特定されるターゲットデータを保持する保持手段と、
前記第２の識別子が含まれる経路情報を用いて、メッセージを転送すべき他ノードを決定する転送機能とを実現すると共に、
前記転送機能により、
前記第１乃至第３の少なくとも何れかの識別子を自ノードに受信するのに応じて、その識別子を検索キーとして、前記経路情報を参照した結果、対応する他ノードが存在する場合には該他ノードにメッセージを転送する
ことを特徴とするコンピュータプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１２】
【図１３Ａ】
【図１３Ｂ】
【図１３Ｃ】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２１】
【公開番号】特開２０１２−４３３３０（Ｐ２０１２−４３３３０Ａ）
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願番号】特願２０１０−１８５９６８（Ｐ２０１０−１８５９６８）
【出願日】平成２２年８月２３日（２０１０．８．２３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成２１年度 独立行政法人新エネルギー・産業 技術総合開発機構「グリーンネットワーク・システム技術研究開発プロジェクト（グリーンＩＴプロジェクト）／エネルギー利用最適化データセンタ基盤技術の研究開発／サーバの最適構成とクラウド・コンピューティング環境における進化するアーキテクチャー開発／クラウド・コンピューティング技術」委託研究、産業技術力強化法第１９条適用を受ける特許出願）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
【公開日】平成２４年３月１日（２０１２．３．１）
【国際特許分類】
【出願日】平成２２年８月２３日（２０１０．８．２３）
【国等の委託研究の成果に係る記載事項】（出願人による申告）国等の委託研究の成果に係る特許出願（平成２１年度 独立行政法人新エネルギー・産業 技術総合開発機構「グリーンネットワーク・システム技術研究開発プロジェクト（グリーンＩＴプロジェクト）／エネルギー利用最適化データセンタ基盤技術の研究開発／サーバの最適構成とクラウド・コンピューティング環境における進化するアーキテクチャー開発／クラウド・コンピューティング技術」委託研究、産業技術力強化法第１９条適用を受ける特許出願）
【出願人】（０００００４２３７）日本電気株式会社 (19,353)
【Ｆターム（参考）】
[ Back to top ]