(57)【要約】【課題】分散処理システムにおける負荷分散をより効率的に実行可能な技術を提供すること。【解決手段】１つ以上の分散処理装置（ノード）によって構成される分散処理システムにおいて、あるノード（比較ノード）が担当する処理の一部を分担させる候補となるノード（候補ノード）について、候補ノードが担当している処理の全てを１つ以上のノード（代行ノード）を用いて代行させる代行ノード集合を作成し（ステップＳ１）、代行ノード集合が候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求め（ステップＳ２）、各代行ノードの代行後負荷予測値が所定の条件を満たす場合に（ステップＳ３でＹｅｓ）、候補ノードの処理を代行ノード集合に代行させて候補ノードを空きノードとするとともに、比較ノードが担当する処理の一部を、空きノードとなった候補ノードに分担させる負荷分散を実行する（ステップＳ４）。【選択図】      図４
2013149069.tif 000002
【特許請求の範囲】
【請求項１】
１つ以上の分散処理装置（ノード）によって構成される分散処理システムにおいて、
あるノード（比較ノード）が担当する処理の一部を分担させる候補となるノード（候補ノード）について、前記候補ノードが担当している処理の全てを１つ以上のノード（代行ノード）を用いて代行させる代行ノード集合を作成し、
前記代行ノード集合が前記候補ノードの処理を代行する場合の前記各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求め、
前記各代行ノードの代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行する、負荷分散方法。
【請求項２】
前記各代行ノードの代行後負荷予測値と、前記比較ノードの負荷分散前の負荷の値とが所定の関係にあることを前記所定の条件として、該所定の条件が満たされる場合に前記負荷分散を実行することを特徴とする請求項１に記載の負荷分散方法。
【請求項３】
概念的なリング状のキー空間であって、キーの値が時計回りに増加するとともに、キー間の距離が時計回り方向に定義されているキー空間において、前記分散処理システムを構成する各ノードがいずれかのキーをノードＩＤとして有しており、前記分散処理システムの処理対象となるデータが、該データから算出されるキーからの距離が最も近いノードＩＤを有するノード（該キーのサクセッサ）によって処理されるとき、
前記代行ノード集合として、前記キー空間において前記候補ノードに対して距離が近いノードから順にｎ個（ｎは１以上の整数）のノードによって構成される集合を作成することを特徴とする請求項１または請求項２に記載の負荷分散方法。
【請求項４】
前記代行ノード集合が１つの代行ノード（候補ノードのサクセッサ）によって構成され、
前記代行ノードの代行後負荷予測値および前記比較ノードの負荷分散前の負荷の値が前記所定の関係であるとき、
前記比較ノードが前記候補ノードのサクセッサならば、前記比較ノードおよび前記候補ノードの負荷が均等になるように、前記比較ノードおよび前記候補ノード間でデータの移動を行う負荷分散を実行し、
前記比較ノードが前記候補ノードのサクセッサではないならば、前記候補ノードが保持するデータの全てを前記代行ノードに移動させるとともに、前記比較ノードおよび前記候補ノードの負荷が均等になるように、前記比較ノードから前記候補ノードにデータの移動を行う負荷分散を実行することを特徴とする請求項３に記載の負荷分散方法。
【請求項５】
前記分散処理システムを構成する各ノードのうち、負荷の値が閾値以上であるノードを前記比較ノードとして、前記負荷分散を実行することを特徴とする請求項１から請求項４のいずれか１項に記載の負荷分散方法。
【請求項６】
１つ以上の分散処理装置（ノード）によって構成される分散処理システムであって、
他のノード（比較ノード）が担当する処理の一部を分担する候補となる候補ノードは、
自ノードが担当する処理の全てを１つ以上のノード（代行ノード）を用いて代行させる代行ノード集合を作成する代行ノード集合作成部と、
前記各代行ノードの負荷の値を受信する代行ノード負荷受信部と、
前記各代行ノードの負荷の値に基づいて、前記代行ノード集合が前記候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求める代行後負荷予測値算出部と、
前記代行後負荷予測値を前記比較ノードに送信する代行後負荷予測値送信部と、
前記比較ノードによって決定される負荷分散を実行する負荷分散実行部と、
を備え、
前記代行ノードは、
前記候補ノードに対して自ノードの負荷の値を送信する負荷送信部と、
前記比較ノードによって決定される負荷分散を実行する負荷分散実行部と、
を備え、
前記比較ノードは、
前記代行後負荷予測値を受信する代行後負荷予測値受信部と、
前記代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行することを決定する負荷分散決定部と、
決定された負荷分散を実行する負荷分散実行部と、
を備える分散処理システム。
【請求項７】
分散処理システムを構成する分散処理装置（ノード）であって、
自ノードが、他のノード（比較ノード）が担当する処理の一部を分担する候補となるノード（候補ノード）である場合に、自ノードが担当する処理の全てを１つ以上の他のノード（代行ノード）を用いて代行させる代行ノード集合を作成する代行ノード集合作成部と、
前記各代行ノードの負荷の値を受信する代行ノード負荷受信部と、
前記各代行ノードの負荷の値に基づいて、前記代行ノード集合が前記候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求める代行後負荷予測値算出部と、
前記代行後負荷予測値を前記比較ノードに送信する代行後負荷予測値送信部と、
前記比較ノードによって決定される負荷分散を実行する負荷分散実行部と、
を備えた分散処理装置。
【請求項８】
分散処理システムに含まれる分散処理装置（ノード）を構成するコンピュータ装置に、
自ノードが、他のノード（比較ノード）が担当する処理の一部を分担する候補となるノード（候補ノード）である場合に、自ノードが担当する処理の全てを１つ以上の他のノード（代行ノード）を用いて代行させる代行ノード集合を作成する代行ノード集合作成ステップと、
前記各代行ノードの負荷の値を受信する代行ノード負荷受信ステップと、
前記各代行ノードの負荷の値に基づいて、前記代行ノード集合が前記候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求める代行後負荷予測値算出ステップと、
前記代行後負荷予測値を前記比較ノードに送信する代行後負荷予測値送信ステップと、
前記比較ノードによって決定される負荷分散を実行する負荷分散実行ステップと、
を実行させるコンピュータ・プログラム。
【請求項９】
分散処理システムを構成する分散処理装置（ノード）であって、
自ノードが、担当する処理の一部を他の候補ノードに分担させる比較ノードである場合に、
前記候補ノードが担当する処理の全てを代行させる代行ノード集合を構成する各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を、前記候補ノードから受信する代行後負荷予測値受信部と、
前記代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行することを決定する負荷分散決定部と、
決定した負荷分散を実行する負荷分散実行部と、
を備えた分散処理装置。
【請求項１０】
分散処理システムに含まれる分散処理装置（ノード）を構成するコンピュータ装置に、
自ノードが、担当する処理の一部を他の候補ノードに分担させる比較ノードである場合に、前記候補ノードが担当する処理の全てを代行させる代行ノード集合を構成する各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を、前記候補ノードから受信する代行後負荷予測値受信ステップと、
前記代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行することを決定する負荷分散決定ステップと、
決定した負荷分散を実行する負荷分散実行ステップと、
を実行させるコンピュータ・プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、１つ以上の分散処理装置によって構成される分散処理システムにおける負荷分散方法、分散処理システム、分散処理装置、および、コンピュータ・プログラムに関する。
【背景技術】
【０００２】
大量のデータの処理や格納を、複数の分散処理装置（ノード）が分担する分散処理システムが知られている。このような分散処理システムにおいて、ある第１のノードの処理量が極端に増え、そのＣＰＵ（Central Processing Unit）使用率が100％に近づくなどの負荷が高い状態になることがある。この場合、このような分散処理システムは、第１のノードが実行中の処理の一部を、他の第２のノードにも分担させることにより、第１のノードの負荷を分散することができる。このように、分散処理システムでは、ノード間における負荷分散が重要な課題となる。このような負荷分散を行う技術の一例が、非特許文献１に記載されている。非特許文献１には、Ｃｈｏｒｄを採用した分散処理システムにおける負荷分散について、主に述べられている。Ｃｈｏｒｄとは、分散処理システムにおいて、データをその担当ノードに割り当てる技術として知られる分散ハッシュテーブル（Distributed Hash Table, DHT）の代表的なアルゴリズムである。Ｃｈｏｒｄでは、リング状のキー空間が定義されている。このキー空間において、キーの値は時計回りに増加していく。また、キーとは、ハッシュ関数の値である。参加ノードは、キー空間上のいずれかのキーをノードＩＤとして有している。また、キー空間では、あるキーから他のキーまでの距離として、時計回り方向の長さが定義されている。ここで、あるキーからの距離が最も近いノードを、そのキーのサクセッサという。また、あるキーからの距離が最も遠いノードを、そのキーのプレディセッサという。Ｃｈｏｒｄでは、あるデータは、そのデータから算出されるキーのサクセッサによって担当される。つまり、各ノードは、自ノードのプレディセッサのノードＩＤより大きく自ノードのノードＩＤまでのキーを担当範囲とする。このようなＣｈｏｒｄを採用した分散処理システムにおける負荷分散について、非特許文献１に記載された技術を以下に述べる。
【０００３】
各ノード（ノードａ）は、ランダムに選択した他のノード（ノードｘ）の負荷の値を取得し、ノードｘの負荷の値（l_x）とノードａの負荷の値（l_a）との関係がl_x≦ε×l_a（εは、０＜ε＜１の定数、例えば０．２５）であるとき、以下のｃａｓｅ１〜ｃａｓｅ３のいずれかの処理を行う。なお、ノードｘのサクセッサをノードｙとする。
＜ｃａｓｅ１：ノードａがノードｘのサクセッサである場合＞
ノードａおよびノードｘの負荷が均等になるように、ノードａが保持するデータの一部をノードｘに移動する。
＜ｃａｓｅ２：ノードａがノードｘのサクセッサではなく、ノードａの負荷の値が、ノードｙの負荷の値以下の場合＞
ノードｘおよびノードｙの負荷の値が均等になるように、ノードｙが保持するデータの一部をノードｘに移動する。
＜ｃａｓｅ３：ノードａがノードｘのサクセッサではなく、ノードａの負荷の値がノードｙの負荷の値より大きい場合＞
ノードｘが保持する全データをノードｙに移動する。すなわち、ノードｘが処理していた全てのデータをノードｙが担当することになる。ノードａは、ノードａおよびノードｘの負荷の値が均等になるように、ノードａが保持するデータの一部をノードｘに移動する。
【０００４】
ｃａｓｅ１〜ｃａｓｅ３について具体例で説明する。図１２に示すように、ノードａからノードhまでの８つのノードによって構成される分散処理システムを想定する。図１２において、各ノードは、リング上のキー空間９００上で図示の順に並ぶノードＩＤをそれぞれ有している。また、各ノードを示す図形の横に示した数値は、各ノードの負荷を表している。
【０００５】
＜ｃａｓｅ１＞
ノードａがノードｈの負荷の値（l_h）を取得したとする。ここで、l_h（１０％）≦ε×l_a（８０％）であり、ノードａはノードｈのサクセッサである。したがって、この場合は、ｃａｓｅ１に相当する。そこで、ノードａの負荷の値を減らすため、ノードａおよびノードhの負荷の値が均等になるように、ノードａは、保持するデータの一部をノードｈに移動する。この結果、ノードａおよびノードhの負荷の値は、それぞれ４５％となる。また、データ移動前に、ノードａおよびノードｈがそれぞれ担当するキー範囲が、[151, 190]および[100, 150]であったとする。なお、[k1, k2]は、k1以上k2以下のキー範囲を表す。ここで、キーが[151, 170]であるデータをノードａからノードｈに移動させたとすると、ノードａおよびノードｈが新たに担当するキー範囲は、[171, 190]および[100, 170]になる。
【０００６】
＜ｃａｓｅ２＞
ノードａがノードbの負荷の値（l_b）を取得したとする。ここで、l_b（１５％）≦ε×l_a（８０％）である。また、ノードａがノードｂのサクセッサではなく、ノードａの負荷の値（l_a＝８０％）が、ノードｂのサクセッサであるノードｃの負荷の値（l_c＝８５％）以下である。したがって、この場合は、ｃａｓｅ２に相当する。そこで、負荷の値が高いノードcの負荷を分散するため、ノードbおよびノードｃの負荷の値が均等になるように、ノードｃは、保持するデータの一部をノードbに移動する。この結果、ノードａの負荷の値は８０％(変更なし)、ノードbの負荷の値は５０％、ノードｃの負荷の値は５０％になる。また、データ移動前にノードbおよびノードｃがそれぞれ担当するキー範囲が[191, 250]、[251, 300]であったとする。ここで、キーが[251, 280]であるデータをノードｃからノードbに移動させたとすると、ノードｂおよびノードｃが新たに担当するキー範囲は、[191, 280]および[281, 300]になる。また、ノードａが担当するキーの範囲は変わらない。
【０００７】
＜ｃａｓｅ３＞
ノードａがノードdの負荷の値（l_d）を取得したとする。ここで、l_d（２０％）≦ε×l_a（８０％）である。また、ノードａがノードｄのサクセッサではなく、ノードａの負荷の値（l_a＝８０％）が、ノードｄのサクセッサであるノードｅの負荷の値（l_e＝３０％）より大きい。したがって、この場合は、ｃａｓｅ３に相当する。そこで、負荷の値が高いノードａの負荷を分散するため、ノードdは、保持するデータをノードeに移動して空きノードとなる。そして、ノードａは、ノードａの負荷の値が半分になるように、保持するデータをノードdに移動する。この結果ノードａの負荷の値は４０％、ノードdの負荷の値は４０％、ノードeの負荷の値は５０％になる。また、データ移動前にノードａ、ノードdおよびノードeのそれぞれが担当するキーの範囲が[151, 190]、[301, 380]および[381, 500]であったとする。ここで、キーが[170, 190]のデータをノードａからノードdに移動させたとすると、ノードａ、ノードdおよびノードeがそれぞれ新たに担当するキー範囲は[151, 169]、[170, 190]および[301, 500]になる。
【０００８】
このように、非特許文献1に記載された技術は、分散処理システムにおいて、負荷の値が高いノードの負荷を軽減することができる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】David R. Karger, Matthias Ruhl著,“Simple Efficient Load Balancing Algorithms for Peer-to-Peer Systems”，Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures (SPAA’04), 2004
【発明の概要】
【発明が解決しようとする課題】
【００１０】
分散処理システムにおいて、負荷の高い第１のノードの処理を他の第２のノードに分散させるには、第２のノードが何も処理を実行していない状態（以降、このような状態のノードを空きノードともいう）であるか、少量の処理しか実行しておらず負荷が低い状態であることが前提となる。そこで、非特許文献１に記載された技術は、ｃａｓｅ３において、第１のノードの負荷を分散するために、ランダムに第２のノードを選択し、第２のノードが現在実行中の処理のすべてを、この第２のノードのサクセッサである第３のノードに担当させる。これにより、非特許文献１に記載された技術は、第２のノードを空きノードとしている。
【００１１】
しかしながら、非特許文献１に記載された技術は、第３のノードの負荷がどのように変化するか考慮せずに第２のノードの処理を代行させるため、第３のノードの負荷が大きくなりすぎる場合がある。このため、負荷が大きくなりすぎた第３のノードの負荷をさらに分散させる必要が生じる場合もある。その結果、非特許文献１に記載された技術は、負荷分散の回数を増大させることもあり、負荷分散を効率よく実行することができない。
【００１２】
本発明は、上述の課題を解決するためになされたもので、分散処理システムにおける負荷分散をより効率的に実行可能な技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明の負荷分散方法は、１つ以上の分散処理装置（ノード）によって構成される分散処理システムにおいて、あるノード（比較ノード）が担当する処理の一部を分担させる候補となるノード（候補ノード）について、前記候補ノードが担当している処理の全てを１つ以上のノード（代行ノード）を用いて代行させる代行ノード集合を作成し、前記代行ノード集合が前記候補ノードの処理を代行する場合の前記各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求め、前記各代行ノードの代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行する。
【００１４】
また、本発明の分散処理システムは、１つ以上の分散処理装置（ノード）によって構成される分散処理システムであって、他のノード（比較ノード）が担当する処理の一部を分担する候補となる候補ノードは、自ノードが担当する処理の全てを１つ以上のノード（代行ノード）を用いて代行させる代行ノード集合を作成する代行ノード集合作成部と、前記各代行ノードの負荷の値を受信する代行ノード負荷受信部と、前記各代行ノードの負荷の値に基づいて、前記代行ノード集合が前記候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求める代行後負荷予測値算出部と、前記代行後負荷予測値を前記比較ノードに送信する代行後負荷予測値送信部と、前記比較ノードによって決定される負荷分散を実行する負荷分散実行部と、を備え、前記代行ノードは、前記候補ノードに対して自ノードの負荷の値を送信する負荷送信部と、前記比較ノードによって決定される負荷分散を実行する負荷分散実行部と、を備え、前記比較ノードは、前記代行後負荷予測値を受信する代行後負荷予測値受信部と、前記代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行することを決定する負荷分散決定部と、決定された負荷分散を実行する負荷分散実行部と、を備える。
【００１５】
また、本発明の分散処理装置は、分散処理システムを構成する分散処理装置（ノード）であって、自ノードが、他のノード（比較ノード）が担当する処理の一部を分担する候補となるノード（候補ノード）である場合に、自ノードが担当する処理の全てを１つ以上の他のノード（代行ノード）を用いて代行させる代行ノード集合を作成する代行ノード集合作成部と、前記各代行ノードの負荷の値を受信する代行ノード負荷受信部と、前記各代行ノードの負荷の値に基づいて、前記代行ノード集合が前記候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求める代行後負荷予測値算出部と、前記代行後負荷予測値を前記比較ノードに送信する代行後負荷予測値送信部と、前記比較ノードによって決定される負荷分散を実行する負荷分散実行部と、を備える。
【００１６】
また、本発明のコンピュータ・プログラムは、分散処理システムに含まれる分散処理装置（ノード）を構成するコンピュータ装置に、自ノードが、他のノード（比較ノード）が担当する処理の一部を分担する候補となるノード（候補ノード）である場合に、自ノードが担当する処理の全てを１つ以上の他のノード（代行ノード）を用いて代行させる代行ノード集合を作成する代行ノード集合作成ステップと、前記各代行ノードの負荷の値を受信する代行ノード負荷受信ステップと、前記各代行ノードの負荷の値に基づいて、前記代行ノード集合が前記候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求める代行後負荷予測値算出ステップと、前記代行後負荷予測値を前記比較ノードに送信する代行後負荷予測値送信ステップと、前記比較ノードによって決定される負荷分散を実行する負荷分散実行ステップと、を実行させる。
【００１７】
また、本発明の分散処理装置は、分散処理システムを構成する分散処理装置（ノード）であって、自ノードが、担当する処理の一部を他の候補ノードに分担させる比較ノードである場合に、前記候補ノードが担当する処理の全てを代行させる代行ノード集合を構成する各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を、前記候補ノードから受信する代行後負荷予測値受信部と、前記代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行することを決定する負荷分散決定部と、決定した負荷分散を実行する負荷分散実行部と、を備える。
【００１８】
また、本発明のコンピュータ・プログラムは、分散処理システムに含まれる分散処理装置（ノード）を構成するコンピュータ装置に、自ノードが、担当する処理の一部を他の候補ノードに分担させる比較ノードである場合に、前記候補ノードが担当する処理の全てを代行させる代行ノード集合を構成する各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を、前記候補ノードから受信する代行後負荷予測値受信ステップと、前記代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行することを決定する負荷分散決定ステップと、決定した負荷分散を実行する負荷分散実行ステップと、を実行させる。
【発明の効果】
【００１９】
本発明は、分散処理システムにおける負荷分散をより効率的に実行可能な技術を提供することができる。
【図面の簡単な説明】
【００２０】
【図１】本発明の第１の実施の形態としての分散処理システムの構成を示すブロック図である。
【図２】本発明の第１の実施の形態としての分散処理装置のハードウェア構成図である。
【図３】本発明の第１の実施の形態としての分散処理システムの機能ブロック図である。
【図４】本発明の第１の実施の形態としての分散処理システムの動作を説明するフローチャートである。
【図５】本発明の第２の実施の形態としての分散処理システムの構成を示すブロック図である。
【図６】本発明の第２の実施の形態としての分散処理システムの機能ブロック図である。
【図７】本発明の第２の実施の形態としての分散処理システムの負荷分散動作を説明するフローチャートである。
【図８】本発明の第３の実施の形態としての分散処理システムの構成を示すブロック図である。
【図９】本発明の第３の実施の形態としての分散処理システムの機能ブロック図である。
【図１０】本発明の第３の実施の形態における候補ノードの負荷分散動作を説明するフローチャートである。
【図１１】本発明の第３の実施の形態における比較ノードの負荷分散動作を説明するフローチャートである。
【図１２】Ｃｈｏｒｄを採用した分散処理システムの一例を示す図である。
【発明を実施するための形態】
【００２１】
以下、本発明の実施の形態について、図面を参照して詳細に説明する。
【００２２】
（第１の実施の形態）
本発明の第１の実施の形態としての分散処理システム１の構成を図１に示す。図１において、分散処理システム１は、１つ以上の分散処理装置（以下、ノードともいう）１０によって構成されている。これらの分散処理装置１０は、インターネット、ＬＡＮ（Local Area Network）、公衆回線網、無線通信網またはこれらの組合せ等によって構成されるネットワークを介して互いに通信可能に接続されている。なお、図１には、６つの分散処理装置１０を示しているが、本発明が対象とする分散処理システムを構成する分散処理装置の数を限定するものではない。
【００２３】
また、分散処理システム１の処理対象となるデータは、いずれかの分散処理装置１０によって処理される。ここで、データとは、格納対象となるコンテンツであってもよいし、格納されたコンテンツを要求するクエリであってもよい。各分散処理装置１０は、分散処理システム１において処理対象となるデータを受信すると、そのデータが自ノードで担当するものであれば、自ノードで処理を実行する。また、各分散処理装置１０は、受信したデータが自ノードで担当するものでなければ、そのデータの処理を担当する他の分散処理装置１０に該データを送信する。なお、各分散処理装置１０は、他の全ての分散処理装置１０と直接通信可能でなくてもよい。各分散処理装置１０は、受信したデータが自ノードで担当するものでなければ、そのデータの処理を担当する他の分散処理装置１０に最終的に到達するよう、自ノードから転送可能ないずれかの他の分散処理装置１０に該データを送信すればよい。このような分散処理システム１において、各ノードの負荷は、そのノードが受信しているデータ量により変動する。
【００２４】
また、図１に示した分散処理装置１０のうち、負荷分散により負荷を軽減させる対象となるノードを比較ノード１１０というものとする。また、分散処理装置１０のうち、比較ノード１１０の処理の一部を分担させる候補となるノードを候補ノード１２０というものとする。また、分散処理装置１０のうち、候補ノード１２０が比較ノード１１０の処理を分担する場合にそれまで候補ノード１２０が担当していた処理を代行するノードを代行ノード１３０というものとする。なお、分散処理システム１を構成する各分散処理装置１０は、いずれも、比較ノード１１０、候補ノード１２０および代行ノード１３０として動作しうるものとする。
【００２５】
次に、分散処理装置１０のハードウェア構成を図２に示す。図２において、分散処理装置１０は、ＣＰＵ（Central Processing Unit）１００１と、ＲＡＭ（Random Access Memory）１００２と、ＲＯＭ（Read Only Memory）１００３と、ハードディスク等の記憶装置１００４と、ネットワークインタフェース１００５とを備えたコンピュータ装置によって構成されている。
【００２６】
ＲＯＭ１００３および記憶装置１００４には、コンピュータ装置を本実施の形態の分散処理装置１０として機能させるためのコンピュータ・プログラムおよび各種データが記憶されている。
【００２７】
ＣＰＵ１００１は、ＲＯＭ１００３および記憶装置１００４に記憶されたコンピュータ・プログラムおよび各種データをＲＡＭ１００２に読み込んで実行する。
【００２８】
ネットワークインタフェース１００５は、ネットワークを介して他の分散処理装置１０との通信を行うモジュールである。
【００２９】
次に、分散処理システム１の機能ブロック構成を図３に示す。図３において、分散処理システム１は、代行ノード集合作成部１０１と、代行後負荷予測値算出部１０２と、代行後負荷予測値判断部１０３と、負荷分散実行部１０４とを備える。ここで、各機能ブロックは、それぞれ、いずれかの分散処理装置１０におけるネットワークインタフェース１００５と、ＲＯＭ１００３および記憶装置１００４に記憶されたコンピュータ・プログラムおよび各種データをＲＡＭ１００２に読み込んで実行するＣＰＵ１００１とによって構成される。また、分散処理システム１の各機能ブロックは、同一の分散処理装置１０によって構成されていてもよいし、少なくとも１つは異なる分散処理装置１０によって構成されていてもよい。また、各機能ブロックを構成する分散処理装置１０は、その動作上、他の機能ブロックとの通信が必要な場合であって、該他の機能ブロックが他の分散処理装置１０によって構成される場合は、適宜該他の分散処理装置１０との間で通信を行うものとする。
【００３０】
代行ノード集合作成部１０１は、ある候補ノード１２０について、候補ノード１２０が担当している処理の全てを１つ以上の代行ノード１３０を用いて代行させる代行ノード集合を作成する。ここで、代行ノード集合作成部１０１は、代行ノード１３０となりうるノードのうち１つ以上を代行ノード１３０としてランダムに選択することにより、代行ノード集合を作成してもよい。なお、代行ノード１３０となりうるノードとは、例えば、分散処理システム１を構成する分散処理装置１０のうち、比較ノード１１０および候補ノード１２０以外のノードであってもよい。
【００３１】
代行後負荷予測値算出部１０２は、代行ノード集合が候補ノード１２０の処理の全てを代行する場合の、各代行ノード１３０の代行後の負荷の予測値（代行後負荷予測値）を求める。
【００３２】
ここで、代行ノード集合が複数の代行ノード１３０から構成されていれば、代行後負荷予測値算出部１０２は、各代行ノード１３０の代行後負荷予測値として、候補ノード１２０の処理の全てのうち各代行ノード１３０に割り当てられる分の負荷の値と、各代行ノード１３０の負荷の値との合計値をそれぞれ算出する。例えば、代行後負荷予測値算出部１０２は、各代行ノード１３０の代行後負荷予測値が均等になるよう各代行ノード１３０に代行させる分の負荷の値を算出することにより、各代行ノード１３０の代行後負荷予測値を求めてもよい。
【００３３】
また、代行ノード集合が１つの代行ノード１３０から構成されていれば、代行後負荷予測値算出部１０２は、該代行ノード１３０の代行後負荷予測値として、候補ノード１２０の負荷の値と、該代行ノード１３０の負荷の値との合計値を求めればよい。
【００３４】
代行後負荷予測値判断部１０３は、各代行ノード１３０の代行後負荷予測値が所定の条件を満たすか否か判断する。ここで、所定の条件とは、例えば、各代行ノード１３０の代行後負荷予測値のうち最大値が閾値以下であることであってもよい。
【００３５】
負荷分散実行部１０４は、代行後負荷予測値が所定の条件を満たすと判断された場合に、比較ノード１１０の負荷を軽減する負荷分散を実行する。具体的には、負荷分散実行部１０４は、候補ノード１２０の処理を代行ノード１３０に代行させるため、候補ノード１２０が担当するデータを代行ノード１３０に移動させて候補ノード１２０を空きノードとする。そして、負荷分散実行部１０４は、比較ノード１１０が担当する処理の一部を、空きノードとなった候補ノード１２０に分担させるため、比較ノード１１０が担当するデータの一部を候補ノード１２０に移動させる。例えば、負荷分散実行部１０４は、比較ノード１１０および候補ノード１２０の負荷分散後の負荷の値が均等になるように、比較ノード１１０から候補ノード１２０へデータを移動させてもよい。
【００３６】
以上のように構成された分散処理システム１の動作について、図４を参照して説明する。
【００３７】
まず、代行ノード集合作成部１０１は、ある候補ノード１２０について、１つ以上の代行ノード１３０からなる代行ノード集合を作成する（ステップＳ１）。例えば、前述のように、代行ノード集合作成部１０１は、代行ノード１３０となりうるノードのうちランダムに選択したものからなる代行ノード集合を作成してもよい。
【００３８】
次に、代行後負荷予測値算出部１０２は、ステップＳ１で作成された代行ノード集合を構成する各代行ノード１３０について、候補ノード１２０の全ての処理を代行ノード集合で代行する場合の代行後負荷予測値を算出する（ステップＳ２）。例えば、前述のように、代行後負荷予測値算出部１０２は、各代行ノード１３０の代行後負荷予測値が均等になるように、代行後負荷予測値を求めてもよい。
【００３９】
次に、代行後負荷予測値判断部１０３は、ステップＳ２で算出された各代行ノード１３０の代行後負荷予測値が所定の条件を満たすか否かを判断する（ステップＳ３）。例えば、前述のように、代行後負荷予測値判断部１０３は、代行後負荷予測値の最大値が閾値以下であるか否かを判断してもよい。
【００４０】
ここで、代行後負荷予測値判断部１０３が所定の条件を満たすと判断された場合、負荷分散実行部１０４は、負荷分散を実行する。具体的には、前述のように、負荷分散実行部１０４は、候補ノード１２０の処理を代行ノード１３０に代行させて候補ノード１２０を空きノードとする。そして、負荷分散実行部１０４は、比較ノード１１０が担当する処理の一部を、空きノードとなった候補ノード１２０に分担させる。例えば、負荷分散実行部１０４は、比較ノード１１０および候補ノード１２０の負荷の値が均等になるよう、比較ノード１１０の処理の一部を候補ノード１２０に分担させてもよい。
【００４１】
以上で、分散処理システム１は動作を終了する。
【００４２】
なお、分散処理システム１は、分散処理システム１を構成する分散処理装置１０のいずれかを所定のタイミング毎に候補ノード１２０として、上述の動作を行ってもよい。また、分散処理システム１は、分散処理システム１を構成する分散処理装置１０のうち、負荷の値が閾値以上のもの比較ノード１１０として、上述の動作を行ってもよい。あるいは、分散処理システム１は、分散処理システム１を構成する分散処理装置１０のうちランダムに選択したものを比較ノード１１０として、上述の動作を行ってもよい。
【００４３】
次に、本発明の第１の実施の形態の効果について述べる。
【００４４】
本発明の第１の実施の形態としての分散処理システムは、負荷分散をより効率的に実行することができる。
【００４５】
その理由は、負荷を軽減する対象となる比較ノードの処理を分担する候補となる候補ノードについて、その処理を代行する代行ノード集合を作成し、代行ノード集合に候補ノードの処理を代行させる場合の各代行ノードの代行後負荷予測値を算出し、代行後負荷予測値が所定の条件を満たす場合に、候補ノードの処理を代行ノードに代行させて空きノードとするとともに空きノードとなった候補ノードに比較ノードの処理の一部を分担させる負荷分散を実行するからである。これにより、代行後負荷予測値が所定の条件を満たさない（例えば、代行後負荷予測値の最大値が閾値より大きい）場合、本実施の形態としての分散処理システムは、負荷分散を実行しない。したがって、代行ノードの負荷分散後の負荷の値が、さらなる負荷の軽減が必要なほど大きくなることがないからである。
【００４６】
（第２の実施の形態）
次に、本発明の第２の実施の形態について図面を参照して詳細に説明する。
【００４７】
本発明の第２の実施の形態としての分散処理システム２の構成を図５に示す。図５において、分散処理システム２は、１つ以上の分散処理装置２０によって構成されている。これらの分散処理装置２０は、図１を参照して説明した本発明の第１の実施の形態としての分散処理装置１０と同様に、ネットワークを介して互いに接続されている。なお、図５には、６つの分散処理装置２０を示しているが、本発明の分散処理システムを構成する分散処理装置の数を限定するものではない。
【００４８】
また、分散処理システム２は、本発明の第１の実施の形態としての分散処理システム１と同様に、処理対象となるデータを受信すると、そのデータを担当する分散処理装置２０にそのデータを送信することにより、該データを処理する。各分散処理装置２０は、自装置で受信したデータを、該データを担当する他の分散処理装置２０に転送するために、他のいくつかの分散処理装置２０のアドレスをルーティングテーブルとして保持する。このような分散処理システム２において、各ノードの負荷は、そのノードが受信しているデータ量により変動する。
【００４９】
また、図５に示した分散処理装置２０のうち、負荷分散により負荷を軽減させる対象となるノードを比較ノード２１０というものとする。また、分散処理装置２０のうち、比較ノード２１０の処理の一部を分担させる候補となるノードを候補ノード２２０というものとする。また、分散処理装置２０のうち、候補ノード２２０が比較ノード２１０の処理を分担する場合にそれまで候補ノード２２０が担当していた処理を代行するノードを代行ノード２３０というものとする。なお、各分散処理装置２０は、いずれも、比較ノード２１０、候補ノード２２０、および、代行ノード２３０として動作しうるものとする。
【００５０】
また、分散処理装置２０は、図２に示した本発明の第１の実施の形態としての分散処理装置１０と同様なハードウェア構成を備えるコンピュータ装置によって構成されている。
【００５１】
次に、分散処理システム２の機能ブロック構成を図６に示す。
【００５２】
図６において、比較ノード２１０は、代行後負荷予測値受信部２１１と、負荷分散決定部２１２と、負荷分散実行部２１５とを備える。また、候補ノード２２０は、代行ノード集合作成部２２１と、代行ノード負荷受信部２２２と、代行後負荷予測値算出部２２３と、代行後負荷予測値送信部２２４と、負荷分散実行部２２５とを備える。代行ノード２３０は、負荷送信部２３１と、負荷分散実行部２３５とを備える。ここで、代行後負荷予測値受信部２１１と、代行ノード負荷受信部２２２と、代行後負荷予測値送信部２２４と、負荷送信部２３１と、負荷分散実行部２１５、２２５、２３５とは、ネットワークインタフェース１００５と、ＲＯＭ１００３および記憶装置１００４に記憶されたコンピュータ・プログラムおよび各種データをＲＡＭ１００２に読み込んで実行するＣＰＵ１００１とによって構成される。また、負荷分散決定部２１２と、代行後負荷予測値算出部２２３とは、ＲＯＭ１００３および記憶装置１００４に記憶されたコンピュータ・プログラムおよび各種データをＲＡＭ１００２に読み込んで実行するＣＰＵ１００１によって構成される。なお、比較ノード２１０、候補ノード２２０、および、代行ノード２３０の各機能ブロックを構成するハードウェア構成は上述の構成に限定されない。
【００５３】
次に、候補ノード２２０の各機能ブロックについて説明する。
【００５４】
代行ノード集合作成部２２１は、自ノードが担当する処理の全てを１つ以上の代行ノード２３０を用いて代行させる代行ノード集合を作成する。例えば、代行ノード集合作成部２２１は、代行ノード２３０となりうる他の分散処理装置２０のうち、負荷の値が閾値以下のものを代行ノード２３０として代行ノード集合を作成してもよい。また、代行ノード集合作成部２２１は、そのような他の分散処理装置２０のうち、負荷の値が最も小さいものを代行ノード２３０として、１つの代行ノード２３０から構成される代行ノード集合を作成してもよい。なお、代行ノード２３０となりうる他の分散処理装置２０とは、その負荷の値を取得可能な他の分散処理装置２０であってもよい。
【００５５】
代行ノード負荷受信部２２２は、代行ノード集合作成部２２１によって作成された代行ノード集合を構成する各代行ノード２３０について、その代行ノード２３０の負荷の値を受信する。
【００５６】
代行後負荷予測値算出部２２３は、代行ノード負荷受信部２２２によって受信された各代行ノード２３０の負荷の値に基づいて、代行ノード集合に自ノードの処理を代行させた場合の各代行ノード２３０の代行後負荷予測値を求める。
【００５７】
例えば、代行後負荷予測値算出部２２３は、各代行ノード２３０の代行後負荷予測値として、各代行ノード２３０のその時点での負荷の値と、自ノードが担当する処理のうち各代行ノード２３０に割り当てる分の負荷の値との合計値をそれぞれ求めてもよい。
【００５８】
もし、代行ノード集合が１つの代行ノード２３０によって構成される場合、代行後負荷予測値算出部２２３は、代行後負荷予測値として、その代行ノード２３０のその時点での負荷の値と、自ノードが担当する処理の負荷の値との合計値を求めればよい。
【００５９】
また、代行ノード集合が複数の代行ノード２３０によって構成される場合、代行後負荷予測値算出部２２３は、各代行ノード２３０の代行後負荷予測値が均等になるような代行後負荷予測値を求めてもよい。
【００６０】
代行後負荷予測値送信部２２４は、代行後負荷予測値算出部２２３によって算出された各代行後負荷予測値を、比較ノード２１０に送信する。このとき、複数の代行ノード２３０についてそれぞれ代行後負荷予測値が算出されている場合、代行後負荷予測値送信部２２４は、各代行ノード２３０の代行後負荷予測値のうち最大値を、比較ノード２１０に送信してもよい。
【００６１】
また、例えば、代行後負荷予測値送信部２２４は、代行後負荷予測値の送信先の比較ノード２１０として、他の分散処理装置２０のうち、負荷の値が閾値以上であるノードを選択してもよい。また、例えば、代行後負荷予測値送信部２２４は、代行後負荷予測値の送信先の比較ノード２１０として、自ノードが保持するルーティングテーブルに含まれる他のノードのいずれかを選択してもよい。
【００６２】
負荷分散実行部２２５は、後述の比較ノード２１０の負荷分散実行部２１５によって決定される内容の負荷分散を実行する。具体的には、負荷分散実行部２２５は、自ノードが担当する処理を代行ノード２３０に代行させるため、自ノードが担当するデータを代行ノード２３０に送信する。また、負荷分散実行部２２５は、比較ノード２１０の処理の一部を分担するため、比較ノード２１０が担当するデータの一部を比較ノード２１０から受信する。
【００６３】
次に、代行ノード２３０の各機能ブロックについて説明する。
【００６４】
負荷送信部２３１は、候補ノード２２０に対して、自ノードの負荷の値を送信する。例えば、負荷送信部２３１は、候補ノード２２０からの要求に応じて、負荷の値を送信するようにしてもよい。
【００６５】
負荷分散実行部２３５は、後述の比較ノード２１０の負荷分散実行部２１５によって決定された内容の負荷分散を実行する。具体的には、負荷分散実行部２３５は、候補ノード２２０が担当する処理を代行するため、候補ノード２２０から、候補ノード２２０が担当していたデータを受信する。
【００６６】
次に、比較ノード２１０の各機能ブロックについて説明する。
【００６７】
代行後負荷予測値受信部２１１は、候補ノード２２０から、代行後負荷予測値を受信する。
【００６８】
負荷分散決定部２１２は、受信された代行後負荷予測値と、自ノードの負荷の値とが、所定の関係にあるか否かを判断する。具体的には、所定の関係とは、自ノードの負荷の値が、代行後負荷予測値以上であることであってもよい。
【００６９】
また、負荷分散決定部２１２は、受信された代行後負荷予測値と、自ノードの負荷の値とが所定の関係にある場合に、負荷分散の処理内容を決定する。この負荷分散の処理内容とは、候補ノード２２０の処理を代行ノード集合に代行させて候補ノード２２０を空きノードとするとともに、自ノードが担当する処理の一部を、空きノードとなった候補ノード２２０に分担させる処理である。そして、負荷分散決定部２１２は、決定した負荷分散の処理内容を、候補ノード２２０に通知する。
【００７０】
負荷分散実行部２１５は、負荷分散決定部２１２によって決定された負荷分散を実行する。具体的には、負荷分散実行部２１５は、自ノードの処理の一部を候補ノード２２０に分担させるため、自ノードが担当するデータの一部を候補ノード２２０に対して送信する。例えば、負荷分散実行部２１５は、自ノードの負荷の値と候補ノード２２０の負荷の値とが均等になるよう、自ノードが担当するデータの一部を候補ノード２２０に対して送信してもよい。
【００７１】
以上のように構成された分散処理システム２の負荷分散動作について、図７を参照して説明する。なお、図７において、左図は候補ノード２２０の動作を示し、右図は比較ノード２１０の動作を示し、左右を結ぶ破線の矢印はノード間のデータの流れを表すものとする。
【００７２】
ここでは、まず、候補ノード２２０の代行ノード集合作成部２２１は、代行ノード集合を作成する（ステップＳ１１）。
【００７３】
次に、代行ノード負荷受信部２２２は、ステップＳ１１で作成された代行ノード集合を構成する各代行ノード２３０の負荷の値を受信する（ステップＳ１２）。
【００７４】
次に、代行後負荷予測値算出部２２３は、ステップＳ１１で作成された代行ノード集合に自ノードが担当する処理を代行させた場合の、各代行ノード２３０の代行後負荷予測値を算出する（ステップＳ１３）。
【００７５】
次に、代行後負荷予測値送信部２２４は、ステップＳ１３で算出された代行後負荷予測値を、比較ノード２１０に送信する（ステップＳ１４）。例えば、前述のように、代行後負荷予測値送信部２２４は、ステップＳ１３で算出された代行後負荷予測値の最大値を比較ノード２１０に送信してもよい。また、このステップにおいて、代行後負荷予測値送信部２２４は、他の分散処理装置２０のうち負荷の値が閾値以下のものを、送信先の比較ノード２１０として選択してもよい。あるいは、代行後負荷予測値送信部２２４は、自ノードがルーティングテーブルに保持する他の分散処理装置２０のいずれかを、送信先の比較ノード２１０として選択してもよい。
【００７６】
次に、比較ノード２１０の代行後負荷予測値受信部２１１は、代行後負荷予測値を受信する（ステップＳ１５）。
【００７７】
次に、負荷分散決定部２１２は、ステップＳ１５で受信された代行後負荷予測値と、自ノートの負荷の値とが、所定の関係にあるか否かを判断する（ステップＳ１６）。例えば、前述のように、負荷分散決定部２１２は、自ノードの負荷の値が代行後負荷予測値以上であるか否かを判断してもよい。
【００７８】
ここで、代行後負荷予測値と、自ノートの負荷の値とが、所定の関係にあると判断した場合、負荷分散決定部２１２は、負荷分散の処理内容を決定する（ステップＳ１７）。具体的には、候補ノード２２０の処理を代行ノード２３０に代行させて候補ノード２２０を空きノードとするとともに、自ノードの処理の一部を候補ノード２２０に分担させることを決定する。そして、負荷分散決定部２１２は、負荷分散の処理内容を、候補ノード２２０に通知する。
【００７９】
次に、負荷分散実行部２１５は、決定された内容の負荷分散を実行する（ステップＳ１８）。具体的には、負荷分散実行部２１５は、自ノードが担当するデータの一部を、候補ノード２２０に送信する。
【００８０】
次に、候補ノード２２０の負荷分散実行部２２５は、負荷分散の内容が通知されると（ステップＳ１９でＹｅｓ）、その内容の負荷分散を実行する（ステップＳ２０）。具体的には、負荷分散実行部２２５は、自ノードが担当するデータを代行ノード集合に送信する。そして、負荷分散実行部２２５は、比較ノード２１０が担当するデータの一部を受信する。
【００８１】
以上で、分散処理システム２は、負荷分散動作を終了する。
【００８２】
なお、候補ノード２２０は、ステップＳ１４における代行後負荷予測値送信処理を、所定のタイミング毎に（例えば所定の時間間隔で）行ってもよい。あるいは、候補ノード２２０は、ステップＳ１２で受信した代行ノード２３０の負荷の値および自ノードの負荷の値のすくなくともいずれか一方が、それぞれに定められた閾値以下である場合に、ステップＳ１４の代行後負荷予測値送信処理を実行するようにしてもよい。あるいは、候補ノード２２０は、比較ノード２１０から要求されたタイミングで、ステップＳ１４の代行後負荷予測値送信処理を実行するようにしてもよい。
【００８３】
次に、本発明の第２の実施の形態の効果について述べる。
【００８４】
本発明の第２の実施の形態としての分散処理システムは、負荷分散をより効率的に実行することができる。
【００８５】
その理由は、分散処理システムを構成するノードのうち、負荷を軽減する対象となる比較ノードの処理を分担する候補となる候補ノードが、自ノードの処理の全てを代行ノード集合に代行させた場合の各代行ノードの代行後負荷予測値を算出して比較ノードに送信し、比較ノードは、自ノードの負荷の値および代行後負荷予測値が所定の関係にある場合に、候補ノードの処理を代行ノードに代行させて比較ノードの処理の一部を候補ノードに分担させる負荷分散を実行することを決定するからである。これにより、比較ノードの負荷の値および代行後負荷予測値が所定の関係にない（例えば、代行後負荷予測値が比較ノードの負荷の値より大きい）場合、分散処理システムは、負荷分散を実行しない。したがって、比較ノード、候補ノードおよび代行ノードのうち負荷分散後の負荷の値の最大値が、負荷分散前の負荷の値の最大値より大きくなることがない。その結果、本発明の第２の実施の形態としての分散処理システムは、１つのノードの負荷を軽減する負荷分散処理により他のノードの負荷の軽減が必要となるケースを生じることなく、負荷分散をより効率よく実行可能となる。
【００８６】
（第３の実施の形態）
次に、本発明の第３の実施の形態について図面を参照して詳細に説明する。
【００８７】
本実施の形態では、本発明を、非特許文献１に記載されたＣｈｏｒｄの技術に基づく分散処理システムに適用した例について説明する。本発明の第３の実施の形態としての分散処理システム３の構成を図８に示す。図８において、分散処理システム３は、１つ以上の分散処理装置３０を備えている。また、これらの分散処理装置３０は、図５を参照して説明した本発明の第２の実施の形態としての分散処理装置３０と同様に、ネットワークを介して互いに接続されている。なお、図８には、６つの分散処理装置３０を示しているが、本発明の分散処理システムを構成する分散処理装置の数を限定するものではない。
【００８８】
各分散処理装置３０は、キー空間上のいずれかのキーをノードＩＤとして有している。ここで、キー空間とは、キーの値が時計回りに増加する概念的なリング状のキー空間である。このキー空間では、キー間の距離が時計回り方向に定義されている。
【００８９】
また、分散処理システム３において、処理対象となるデータは、該データから算出されるキーからの距離が最も近いノードＩＤを有するノード（そのキーのサクセッサ）によって処理される。つまり、各分散処理装置３０は、自ノードのノードＩＤからの距離が最も遠いノードＩＤを有するノード（自ノードのプレディセッサ）のノードＩＤより大きく、自ノードのノードＩＤまでの範囲のキーに関連するデータの処理を担当する。ここで、データとは、格納対象となるコンテンツであってもよいし、格納されたコンテンツを要求するクエリであってもよい。
【００９０】
また、分散処理システム３は、いずれかの分散処理装置３０が外部から受信するデータを、他の分散処理装置３０に順次転送することにより、該データの処理を担当する分散処理装置３０に最終的に配送する。各分散処理装置３０は、データを他の分散処理装置３０に転送するために、他のいくつかの分散処理装置３０のアドレスをルーティングテーブルとして保持する。例えば、Ｃｈｏｒｄでは、各分散処理装置３０は、自ノードのノードＩＤであるキーからの距離が2i−1 (i=1,2,...,m)であるキーのサクセッサのアドレスを、ルーティングテーブルに保持する。
【００９１】
また、分散処理システム３を構成する分散処理装置３０のうち、負荷分散により負荷を軽減させる対象となるノードを比較ノード３１０というものとする。また、分散処理装置３０のうち、比較ノード３１０の処理の一部を分担させる候補となるノードを候補ノード３２０というものとする。また、分散処理装置３０のうち、候補ノード３２０が比較ノード３１０の処理を分担する場合にそれまで候補ノード３２０が担当していた処理を代行するノードを代行ノード３３０というものとする。なお、各分散処理装置３０は、いずれも、比較ノード３１０、候補ノード３２０、および、代行ノード３３０として動作しうるものとする。
【００９２】
次に、分散処理システム３の機能ブロック構成を図９に示す。
【００９３】
図９において、比較ノード３１０は、負荷情報受信部３１１と、負荷分散決定部３１２と、負荷分散実行部３１５とを備えている。また、候補ノード３２０は、代行ノード集合作成部３２１と、代行ノード負荷受信部３２２と、負荷情報作成部３２３と、負荷情報送信部３２４と、負荷分散実行部３２５とを備えている。また、代行ノード３３０は、負荷送信部３３１と、負荷分散実行部３３５とを備えている。なお、負荷情報受信部３１１は、本発明の代行後負荷予測値受信部の一実施形態を構成する。また、負荷情報作成部３２３は、本発明の代行後負荷予測値算出部の一実施形態を構成する。また、負荷情報送信部３２４は、本発明の代行後負荷予測値送信部の一実施形態を構成する。
【００９４】
次に、候補ノード３２０の各機能ブロックについて説明する。
【００９５】
代行ノード集合作成部３２１は、自ノード（候補ノード３２０）のサクセッサを代行ノード３３０として、１つの代行ノード３３０からなる代行ノード集合を作成する。
【００９６】
代行ノード負荷受信部３２２は、自ノードのサクセッサである代行ノード３３０の負荷の値を受信する。
【００９７】
負荷情報作成部３２３は、比較ノード３１０が自ノードのサクセッサである場合、自ノードの負荷の値を表す数値と、自ノードのノードＩＤとから構成される負荷情報を作成する。
【００９８】
また、負荷情報作成部３２３は、比較ノード３１０が自ノードのサクセッサでない場合、自ノードの負荷の値およびサクセッサの負荷の値の合計値（すなわち、サクセッサである代行ノード３３０の代行後負荷予測値）と、自ノードのノードＩＤとから構成される負荷情報を作成する。
【００９９】
負荷情報送信部３２４は、負荷情報作成部３２３によって作成された負荷情報を、比較ノード３１０に送信する。なお、負荷情報送信部３２４は、負荷情報の送信先である比較ノード３１０として、例えば、以下のような手法により他の分散処理装置３０を選択してもよい。
＜負荷情報送信先の選択手法（１）＞キー空間のキーをランダムに選択し、選択したキーを担当する他の分散処理装置３０を、負荷情報送信先の比較ノード３１０として選択。
＜負荷情報送信先の選択手法（２）＞候補ノード３２０が保持するルーティングテーブルに格納されているノードの中からランダムに選択。
＜負荷情報送信先の選択手法（３）＞候補ノード３２０が保持するルーティングテーブルに格納されているノードのうち、そのノードに他のノードから転送されるデータの単位時間当たりの量が閾値以上であるノードを選択。
＜負荷情報送信先の選択手法（４）＞候補ノード３２０において、データ転送先となる他のノードごとに送信キューが用意されているときに、送信キューに格納されているデータの量が閾値以上であるノードを選択。
【０１００】
負荷分散実行部３２５は、比較ノード３１０によって決定された内容の負荷分散を実行する。具体的な負荷分散の処理内容については、詳細を後述する。
【０１０１】
次に、代行ノード３３０の各機能ブロックについて説明する。
【０１０２】
負荷送信部３３１は、候補ノード３２０に対して、自ノードが担当している処理の負荷の値を送信する。例えば、負荷送信部３３１は、候補ノード３２０からの要求に応じて、負荷の値を送信するようにしてもよい。
【０１０３】
負荷分散実行部３３５は、後述の比較ノード３１０の負荷分散実行部３１５によって決定された内容の負荷分散を実行する。具体的な負荷分散の処理内容については、詳細を後述する。
【０１０４】
次に、比較ノード３１０の各機能ブロックについて述べる。
【０１０５】
負荷情報受信部３１１は、候補ノード３２０から負荷情報を受信する。負荷情報は、自ノードが候補ノード３２０のサクセッサである場合、候補ノード３２０の負荷の値および候補ノード３２０のノードＩＤからなる。また、負荷情報は、自ノードが候補ノード３２０のサクセッサでない場合、候補ノード３２０の負荷の値およびそのサクセッサの負荷の値の合計値（サクセッサの代行後負荷予測値）と、候補ノード３２０のノードＩＤとからなる。
【０１０６】
負荷分散決定部３１２は、受信された負荷情報に含まれる負荷の値と、自ノードの負荷の値とが所定の関係を満たす場合に、負荷分散の処理内容を決定する。ここで、所定の関係とは、次式（１）で表される関係であってもよい。
[比較ノード３１０の負荷の値]≧[受信した負荷情報に含まれる負荷の値]・・・（１）
具体的には、負荷分散決定部３１２は、そのような所定の関係を満たす場合であって、負荷情報の送信元である候補ノード３２０が自ノードのプレディセッサである場合、自ノード（比較ノード３１０）および候補ノード３２０間で負荷を均等にするようデータを移動する負荷分散処理を決定する。また、負荷分散決定部３１２は、そのような所定の関係を満たす場合であって、負荷情報の送信元である候補ノード３２０が自ノードのプレディセッサではない場合、候補ノード３２０の処理をサクセッサ（代行ノード３３０）に代行させるとともに自ノード（比較ノード３１０）の処理の一部を候補ノード３２０に分担させる負荷分散処理を決定する。このとき、負荷分散決定部３１２は、自ノードの負荷分散後の負荷の値と、候補ノード３２０の負荷分散後の負荷の値とが均等になるように、自ノードから候補ノード３２０に移動するデータを決定してもよい。また、負荷分散決定部３１２は、所定の関係が満たされない場合は、この候補ノード３２０と自ノード間で負荷分散を実行しないことを決定する。
【０１０７】
また、負荷分散決定部３１２は、負荷分散の実行を決定した場合は、その処理内容を、候補ノード３２０に通知する。
【０１０８】
負荷分散実行部３１５は、負荷分散決定部３１２によって決定された内容の負荷分散を実行する。
【０１０９】
以上のように構成された分散処理システム３の動作について、図１０および図１１を参照して詳細に説明する。なお、図１０は候補ノード３２０の動作を示し、図１１は比較ノード３１０の動作を示している。また、図１０および図１１における破線の矢印は、候補ノード３２０および比較ノード３１０間のデータの流れを示す。
【０１１０】
図１０では、まず、候補ノード３２０の代行ノード集合作成部３２１は、代行ノード集合を構成する代行ノード３３０として、自ノードのサクセッサを選択する（ステップＳ２１）。
【０１１１】
次に、代行ノード負荷受信部３２２は、サクセッサからその負荷の値を受信する（ステップＳ２２）。
【０１１２】
次に、負荷情報作成部３２３は、比較ノード３１０が自ノードのサクセッサであるか否かを判断する（ステップＳ２３）。なお、ここで、負荷情報作成部３２３は、負荷情報送信部３２４によって、例えば前述の負荷情報送信先の選択手法（１）〜（４）のいずれかを用いて選択された比較ノード３１０について、判断を行うようにすればよい。
【０１１３】
ここで、比較ノード３１０が自ノードのサクセッサである場合、負荷情報作成部３２３は、自ノードの負荷の値と、自ノードＩＤとからなる負荷情報を作成する（ステップＳ２４）。
【０１１４】
一方、比較ノード３１０が自ノードのサクセッサでない場合、負荷情報作成部３２３は、自ノードの負荷の値およびサクセッサの負荷の値の合計値（サクセッサの代行後負荷予測値）と、自ノードＩＤとからなる負荷情報を作成する（ステップＳ２５）。
【０１１５】
次に、負荷情報送信部３２４は、ステップＳ２４またはステップＳ２５で作成された負荷情報を比較ノード３１０に送信する（ステップＳ２６）。
【０１１６】
次に、負荷情報を受信した比較ノード３１０の動作を、図１１を参照して説明する。
【０１１７】
図１１では、まず、比較ノード３１０の負荷情報受信部３１１は、候補ノード３２０から負荷情報を受信する（ステップＳ２７）。
【０１１８】
次に、負荷分散決定部３１２は、受信された負荷情報に含まれる負荷の値と、自ノードの負荷の値とが所定の関係を満たすか否かを判断する（ステップＳ２８）。例えば、前述のように、所定の関係とは、自ノードの負荷の値が、受信された負荷情報に含まれる負荷の値以上であることであってもよい。
【０１１９】
ここで、所定の関係を満たすと判断した場合、負荷分散決定部３１２は、さらに、負荷情報の送信元である候補ノード３２０が、自ノード（比較ノード３１０）のプレディセッサであるか否かを判断する（ステップＳ２９）。
【０１２０】
ここで、候補ノード３２０が自ノードのプレディセッサである場合、負荷分散決定部３１２は、自ノードおよび候補ノード３２０間で負荷の値が均等になるよう、２つのノード間でデータを移動する負荷分散を決定する（ステップＳ３０）。そして、負荷分散の処理内容を候補ノード３２０に通知する。
【０１２１】
一方、候補ノード３２０が自ノードのプレディセッサでない場合、負荷分散決定部３１２は、候補ノード３２０の処理をそのサクセッサに代行させるとともに、自ノードおよび候補ノード３２０間で負荷の値が均等になるよう自ノードから候補ノード３２０へデータを移動する負荷分散を決定する（ステップＳ３１）。そして、負荷分散の処理内容を候補ノード３２０に通知する。
【０１２２】
また、ステップＳ２８において、所定の関係を満たさないと判断した場合、分散処理システム３は負荷分散を実行しない。
【０１２３】
次に、比較ノード３１０の負荷分散実行部３１５は、ステップＳ３０またはステップＳ３１で決定された負荷分散の内容にしたがって、候補ノード３２０との間でデータの送受信を行う（ステップＳ３２）。
【０１２４】
次に、図１０において、候補ノード３２０の負荷分散実行部３２５は、比較ノード３１０から負荷分散の処理内容を通知されると（ステップＳ３３でＹｅｓ）、通知された処理内容にしたがって負荷分散を実行する（ステップＳ３４）。具体的には、もし、比較ノード３１０が自ノードのサクセッサであれば、負荷分散実行部３２５は、比較ノード３１０および自ノード間で負荷分散後の負荷の値が均等になるようデータを送受信する。また、比較ノード３１０が自ノードのサクセッサでなければ、負荷分散実行部３２５は、自ノードの担当していたデータの全てをサクセッサに送信する。そして、負荷分散実行部３２５は、比較ノード３１０および自ノード間で負荷分散後の負荷の値が均等になるよう、比較ノード３１０からデータを受信する。
【０１２５】
以上で、分散処理システム３は動作を終了する。
【０１２６】
次に、分散処理システム３の負荷分散動作について、具体例を挙げて説明する。ここでは、図１２に示したようなノードａからノードhまでの８つの分散処理装置によって構成される分散処理システムに、本実施の形態としての分散処理システム３を適用した場合の負荷分散動作について説明する。なお、前述のように、図１２において、各ノードは、リング上のキー空間９００上で図示の順に並ぶノードＩＤをそれぞれ有している。また、各ノードを示す図形の横に示した数値は、各ノードの負荷の値を表している。
【０１２７】
まず、ノードｅを候補ノード３２０とし、ノードｅにより負荷情報の送信先の比較ノード３１０としてノードａが選択された場合の動作例について説明する。
【０１２８】
この場合、まず、ノードｅの代行ノード集合作成部３２１は、ノードｅのサクセッサであるノードｆを代行ノード３３０として選択する（ステップＳ２１）。
【０１２９】
そして、ノードｅの代行ノード負荷受信部３２２は、ノードｆから、ノードｆの負荷の値「２０％」を受信する（ステップＳ２２）。
【０１３０】
次に、ノードｅの負荷情報作成部３２３は、比較ノード３１０としてのノードａが自ノードのサクセッサではないので（ステップＳ２３でＮｏ）、ノードｆの負荷の値「２０％」および自ノードの負荷の値「３０％」の合計値である「５０％」（サクセッサの代行後負荷予測値）と、自ノードのノードＩＤとからなる負荷情報を作成する（ステップＳ２５）。
【０１３１】
次に、負荷情報送信部３２４は、作成された負荷情報を、比較ノード３１０としてのノードaに送信する（ステップＳ２６）。
【０１３２】
次に、負荷情報を受信したノードaでは、負荷分散決定部３１２は、自ノードの負荷の値「８０％」が、受信された負荷情報に含まれる負荷の値「５０％」以上であり（ステップＳ２８でＹｅｓ）、ノードｅがノードａのプレディセッサではない（ステップＳ２９でＮｏ）と判断する。そこで、ノードaの負荷分散決定部３１２は、ノードｅの処理をノードｆに代行させるとともにノードａの処理の一部をノードｅに分担させる負荷分散を決定する（ステップＳ３１）。そして、ノードａ、ノードｅおよびノードｆの各負荷分散実行部３１５、３２５および３３５は、決定された負荷分散を実行する。これにより、ノードａおよびノードｅの負荷分散後の負荷の値はそれぞれ４０％となる。また、ノードｆの負荷分散後の負荷の値は５０％となる。
【０１３３】
以上で、ノードｅを候補ノード３２０とし、ノードａを比較ノード３１０とした場合の動作の具体例の説明を終了する。
【０１３４】
次に、ノードｆを候補ノード３２０とし、ノードｆにより負荷情報の送信先の比較ノード３１０としてノードａが選択された場合の動作例について説明する。
【０１３５】
この場合、まず、ノードｆの代行ノード集合作成部３２１は、ノードｆのサクセッサであるノードｇを代行ノード３３０として選択する（ステップＳ２１）。
【０１３６】
そして、ノードｆの代行ノード負荷受信部３２２は、ノードｇから、ノードｇの負荷の値「７９％」を受信する（ステップＳ２２）。
【０１３７】
次に、ノードｆの負荷情報作成部３２３は、比較ノード３１０としてのノードａが自ノードのサクセッサではないので（ステップＳ２３でＮｏ）、ノードｇの負荷の値「７９％」および自ノードの負荷の値「２０％」の合計値である「９９％」（サクセッサの代行後負荷予測値）と、自ノードのノードＩＤとからなる負荷情報を作成する（ステップＳ２５）。
【０１３８】
次に、負荷情報送信部３２４は、作成された負荷情報を、比較ノード３１０としてのノードaに送信する（ステップＳ２６）。
【０１３９】
次に、負荷情報を受信したノードaでは、負荷分散決定部３１２は、自ノードの負荷の値「８０％」が、受信された負荷情報に含まれる負荷の値「９９％」以上ではないので（ステップＳ２８でＮｏ）、負荷分散を行わないと決定する。
【０１４０】
以上で、分散処理システム３の負荷分散動作の具体例の説明を終了する。
【０１４１】
次に、本発明の第３の実施の形態の効果について述べる。
【０１４２】
本発明の第３の実施の形態としての分散処理システムは、あるノードの負荷を軽減するための負荷分散処理に関連したノード群において、負荷分散前の負荷の値の最大値より、負荷分散後の負荷の値の最大値が大きくなることを防止することができる。
【０１４３】
その理由は、比較ノードの負荷分散決定部が、自ノードの負荷の値が、自ノードの処理を分担させる候補ノードの処理を代行させる代行ノードの代行後負荷予測値以上である（所定の関係である）場合に、負荷分散を実行することを決定するからである。
【０１４４】
ここで、比較ノードの負荷分散前の負荷の値をl_a、負荷分散後の負荷の値をl_a’とし、候補ノードの負荷分散前の負荷の値をl_x、負荷分散後の負荷の値をl_x’とし、代行ノードの負荷分散前の負荷の値をl_y、負荷分散後の負荷の値をl_y’とする。このとき、前述の所定の関係は、l_a≧l_x＋l_yと表される。また、代行後負荷予測値l_y’は、l_x＋l_yで算出される。
【０１４５】
もし、代行後負荷予測値l_y’（＝l_x+l_y）がl_aより大きいと（ステップＳ２８でＮｏ）、本実施の形態としての分散処理システムは、負荷分散を実行しない。したがって、max{l_a, l_x, l_y}＝max{l_a’, l_x’, l_y’}となる。ここで、max{}は、要素のうち最大値を表す。したがって、関連するノード群（比較ノード、候補ノードおよび代行ノード）において、負荷分散前の負荷の値の最大値より、負荷分散後の負荷の値が大きくなることはない。
【０１４６】
また、代行後負荷予測値l_y’（＝l_x+l_y）がl_a以下であると（ステップＳ２８でＹｅｓ）、max{l_a, l_x, l_y}はl_aである。この場合、本実施の形態としての分散処理システムは、負荷分散を実行することにより、
l_a’=l_a×0.5、
l_x’=l_a×0.5、
l_y’=l_x＋l_y
となる。このとき、max{l_a’, l_x’, l_y’}は、l_a×0.5またはl_x+l_yであるが、どちらの値も、l_a以下である。したがって、max{l_a, l_x, l_y}≧max{l_a’, l_x’, l_y’}となり、関連するノード群（比較ノード、候補ノードおよび代行ノード）において、負荷分散前の負荷の値の最大値より、負荷分散後の負荷の値が大きくなることはない。
【０１４７】
このように、本実施の形態としての分散処理システムにおいて、比較ノードの負荷の値が、代行ノードの代行後負荷予測値以上である場合に負荷分散を実行することにより、関連するノード群（比較ノード、候補ノードおよび代行ノード）において、負荷分散前の負荷の値の最大値より、負荷分散後の負荷の値が大きくなることはない。その結果、本実施の形態としての分散処理システムにおいて、負荷分散後にさらなる負荷分散が必要なケースを減らすことができ、負荷分散の処理回数を軽減できることになる。
【０１４８】
例えば、図１２において、ノードｆを候補ノード３２０とし、ノードａを比較ノード３１０としたとき、本実施の形態としての分散処理システムは、負荷分散を行わないことを説明した。ここで、図１２において、非特許文献１に記載の関連技術を適用した場合について考える。このとき、ノードａがノードｆの負荷の値（l_f）を取得したとする。ここで、l_f（２０％）≦ε×l_a（８０％）である。また、ノードａがノードｆのサクセッサではなく、ノードａの負荷の値（l_a＝８０％）が、ノードｆのサクセッサであるノードｇの負荷の値（l_c＝７９％）より大きい。したがって、この場合は、関連技術におけるｃａｓｅ３に相当する。そこで、ノードｆは、保持するデータをノードｇに移動して空きノードとなる。そして、ノードａは、ノードａの負荷の値が半分になるように、保持するデータをノードｆに移動する。この結果ノードａおよびノードｆの負荷の値はそれぞれ４０％となり、ノードｇの負荷の値は９９％となる。その結果、関連技術では、負荷の値が９９％となったノードｇの負荷を軽減するための負荷分散が、さらに実行されることになる。一方、本実施の形態としての分散処理システムは、ノードｆからノードａに負荷の値を送信した場合、前述のように負荷分散を実行せず、例えばノードｅからノードａに負荷の値を送信した場合に、負荷分散を実行することになる。したがって、このような具体例において、本実施の形態としての分散処理システムは、負荷分散の処理回数を軽減することになる。
【０１４９】
なお、本実施の形態において、候補ノードの代行ノード集合作成部は、候補ノードのサクセッサを代行ノードとして、１つの代行ノードからなる代行ノード集合を作成するものとして説明した。この他、候補ノードの代行ノード集合作成部は、候補ノードに対して時計回り方向の距離が近いノードから順にｎ個（ｎは１以上の整数）のノードを代行ノードとして、それらの代行ノードによって構成される代行ノード集合を作成してもよい。
【０１５０】
また、本実施の形態において、候補ノードが比較ノードに対して負荷情報を送信するタイミングとしては、以下が採用可能である。
＜負荷送信タイミング（１）＞所定のタイミング。例えば、一定時間毎や、あらかじめ定められたスケジュールにしたがったタイミング等。
＜負荷送信タイミング（２）＞候補ノードおよび代行ノードの少なくとも一方の負荷の値が、それぞれに定められた閾値以下となったタイミング。
＜負荷送信タイミング（３）＞候補ノードのルーティングテーブルにアドレスが格納されている他のノードのうち、単位時間当たりに転送されるデータの数または量が閾値以上となったノードがあるとき。
＜負荷送信タイミング（４）＞候補ノードにおいてデータ転送先のノード毎に送信キューが用意されている場合に、あるノード用の送信キューに格納されているデータ数または量が閾値以上になったとき。
【０１５１】
なお、候補ノードがこのようなタイミングを判断して比較ノードに対して代行後負荷予測値を送信してもよいし、比較ノードがこのようなタイミングを判断することにより候補ノードに代行後負荷予測値の送信を要求してもよい。
【０１５２】
また、本発明の第２および第３の実施の形態において、比較ノードの代行後負荷予測値受信部（または負荷情報受信部）は、複数の候補ノードから代行後負荷予測値を受信してもよい。この場合、比較ノードの負荷分散決定部は、最も値が小さい代行後負荷予測値の送信元の候補ノードおよびその代行ノードを用いた負荷分散を決定してもよい。
【０１５３】
また、本発明の第２および第３の実施の形態において、比較ノードの負荷分散決定部が、負荷分散を実行しないことを決定した場合、この候補ノードから受信した代行後負荷予測値を、他の比較ノードに転送してもよい。この場合、代行後負荷予測値を転送された他の比較ノードが同様に動作することにより、負荷分散を行うか否かを決定すればよい。これにより、各実施の形態としての分散処理システムは、ある候補ノードによって算出された代行後負荷予測値をもとに、負荷の値が高いいずれかのノードの負荷を軽減する負荷分散を実行できることになる。
【０１５４】
また、本発明の第２および第３の実施の形態において、候補ノードは、自ノードの負荷の値または代行ノードの負荷の値の少なくともいずれか一方が閾値以上であるときは、比較ノードに代行後負荷予測値を送信しないようにしてもよい。これにより、各実施の形態としての分散処理システムは、負荷分散を実行しないことを決定する可能性が高いにもかかわらず、代行後負荷予測値の送信処理および負荷分散を実行するか否かの決定処理を行うことがなく、より効率的に負荷分散を実行可能となる。
【０１５５】
また、上述した各実施の形態としての分散処理システムは、候補ノードおよび代行ノードを用いて負荷分散を行うことを決定した場合に、そのような負荷分散を実行する前に、次の処理をおこなってもよい。すなわち、この場合において、各実施の形態としての分散処理システムは、代行ノードの負荷の値が、代行ノードのサクセッサの負荷の値以上であれば、代行ノードの処理の一部を代行ノードのサクセッサに分担させる負荷分散をあらかじめ行うようにしてもよい。これにより、各実施の形態としての分散処理システムは、負荷分散による代行ノードの負荷の値の上昇をさらに軽減することができる。
【０１５６】
また、本発明の第２および第３の実施の形態において、候補ノードが、代行ノード集合を作成して代行後負荷予測値を算出し、比較ノードが、代行後負荷予測値が所定の条件を満たすか否かに基づいて負荷分散を実行するか否かを決定する例について説明した。これに限らず、本発明の分散処理システムにおいて、代行ノード集合の作成処理は、候補ノード以外のノードによって行われても構わない。また、本発明の分散処理システムにおいて、代行後負荷予測値の算出処理は、候補ノード以外のノードによって行われても構わない。また、本発明の分散処理システムにおいて、代行後負荷予測値が所定の条件を満たすか否かの判定処理は、比較ノード以外のノードによって行われても構わない。
【０１５７】
また、上述した本発明の各実施の形態において、各フローチャートを参照して説明した各ノードの動作を、本発明のコンピュータ・プログラムとしてコンピュータ装置の記憶装置（記憶媒体）に格納しておき、係るコンピュータ・プログラムを当該ＣＰＵが読み出して実行するようにしてもよい。そして、このような場合において、本発明は、係るコンピュータ・プログラムのコード或いは記憶媒体によって構成される。
【０１５８】
また、上述した各実施の形態は、適宜組み合わせて実施されることが可能である。
【０１５９】
また、本発明は、上述した各実施の形態に限定されず、様々な態様で実施されることが可能である。
【０１６０】
また、上述した各実施形態の一部又は全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
１つ以上の分散処理装置（ノード）によって構成される分散処理システムにおいて、
あるノード（比較ノード）が担当する処理の一部を分担させる候補となるノード（候補ノード）について、前記候補ノードが担当している処理の全てを１つ以上のノード（代行ノード）を用いて代行させる代行ノード集合を作成し、
前記代行ノード集合が前記候補ノードの処理を代行する場合の前記各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求め、
前記各代行ノードの代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行する、負荷分散方法。
（付記２）
前記各代行ノードの代行後負荷予測値と、前記比較ノードの負荷分散前の負荷の値とが所定の関係にあることを前記所定の条件として、該所定の条件が満たされる場合に前記負荷分散を実行することを特徴とする付記１に記載の負荷分散方法。
（付記３）
概念的なリング状のキー空間であって、キーの値が時計回りに増加するとともに、キー間の距離が時計回り方向に定義されているキー空間において、前記分散処理システムを構成する各ノードがいずれかのキーをノードＩＤとして有しており、前記分散処理システムの処理対象となるデータが、該データから算出されるキーからの距離が最も近いノードＩＤを有するノード（該キーのサクセッサ）によって処理されるとき、
前記代行ノード集合として、前記キー空間において前記候補ノードに対して距離が近いノードから順にｎ個（ｎは１以上の整数）のノードによって構成される集合を作成することを特徴とする付記１または付記２に記載の負荷分散方法。
（付記４）
前記代行ノード集合が１つの代行ノード（候補ノードのサクセッサ）によって構成され、
前記代行ノードの代行後負荷予測値および前記比較ノードの負荷分散前の負荷の値が前記所定の関係であるとき、
前記比較ノードが前記候補ノードのサクセッサならば、前記比較ノードおよび前記候補ノードの負荷が均等になるように、前記比較ノードおよび前記候補ノード間でデータの移動を行う負荷分散を実行し、
前記比較ノードが前記候補ノードのサクセッサではないならば、前記候補ノードが保持するデータの全てを前記代行ノードに移動させるとともに、前記比較ノードおよび前記候補ノードの負荷が均等になるように、前記比較ノードから前記候補ノードにデータの移動を行う負荷分散を実行することを特徴とする付記３に記載の負荷分散方法。
（付記５）
前記分散処理システムを構成する各ノードのうち、負荷の値が閾値以上であるノードを前記比較ノードとして、前記負荷分散を実行することを特徴とする付記１から付記４のいずれか１項に記載の負荷分散方法。
（付記６）
前記分散処理システムを構成する各ノードのうち、ランダムに選択されたノードを前記比較ノードとして、前記負荷分散を実行することを特徴とする付記１から付記４のいずれか１つに記載の負荷分散方法。
（付記７）
前記候補ノードにおいて他のノードに関する情報を保持するルーティングテーブルに含まれる他のノードのいずれかを前記比較ノードとして、前記負荷分散を実行することを特徴とする付記１から付記４のいずれか１つに記載の負荷分散方法。
（付記８）
前記候補ノードにおける前記ルーティングテーブルに含まれる他のノードのいずれかに対して、単位時間当たりに転送されるデータ量が閾値以上になったタイミングで、前記各代行ノードの代行後負荷予測値を求めることにより、該他のノードを前記比較ノードとして前記負荷分散を実行することを特徴とする付記７に記載の負荷分散方法。
（付記９）
前記候補ノードにおいてデータ転送先となる他のノードごとに送信キューが用意されている場合に、いずれかの他のノード用の送信キューに格納されているデータ量が閾値以上になったタイミングで、前記各代行ノードの代行後負荷予測値を求めることにより、該他のノードを前記比較ノードとして前記負荷分散を実行することを特徴とする付記１から付記４のいずれか１つに記載の負荷分散方法。
（付記１０）
前記各代行ノードの代行後負荷予測値を所定のタイミング毎に求めることにより、前記負荷分散を実行することを特徴とする付記１から付記７のいずれか１つに記載の負荷分散方法。
（付記１１）
前記候補ノードの負荷の値および前記代行ノードの負荷の値の少なくとも一方がそれぞれに定められた閾値以下となったタイミングで、前記各代行ノードの代行後負荷予測値を求めることにより、前記負荷分散を実行することを特徴とする付記１から付記７のいずれか１つに記載の負荷分散方法。
（付記１２）
複数の前記候補ノードについてそれぞれ前記代行ノード集合を作成し、作成した各代行ノード集合における前記代行後負荷予測値に基づいていずれかの候補ノードを選択し、選択した候補ノードおよびその代行ノード集合を用いて、前記比較ノードの前記負荷分散を実行することを特徴とする付記１から付記１１のいずれか１つに記載の負荷分散方法。
（付記１３）
前記代行後負荷予測値と、前記比較ノードの負荷分散前の負荷の値とが前記所定の関係にない場合に、他のノードを新たな比較ノードとして前記代行後負荷予測値が前記所定の関係を満たすか否かに基づいて、前記新たな比較ノードについて前記負荷分散を実行するか否かを決定することを特徴とする付記２から付記１２のいずれか１つに記載の負荷分散方法。
（付記１４）
前記各代行ノードの代行後負荷予測値として、前記候補ノードの処理の全てのうち前記各代行ノードに代行させる分の負荷の値と、前記各代行ノードの負荷の値との合計値をそれぞれ求めることを特徴とする付記１から付記１３のいずれか１つに記載の負荷分散方法。
（付記１５）
前記各代行ノードの代行後負荷予測値が均等になるよう前記各代行ノードに代行させる分の負荷の値を算出することにより、前記各代行ノードの代行後負荷予測値を求めることを特徴とする付記１４に記載の負荷分散方法。
（付記１６）
前記代行ノード集合が１つの代行ノードからなるとき、該代行ノードの代行後負荷予測値として、前記候補ノードの負荷の値と、前記代行ノードの負荷の値との合計値を求めることを特徴とする付記１４に記載の負荷分散方法。
（付記１７）
前記比較ノードの負荷分散前の負荷の値が、前記各代行ノードの代行後負荷予測値の最大値以上であることを前記所定の関係として、該所定の関係が満たされる場合に前記負荷分散を実行することを特徴とする付記２から付記１６のいずれか１つに記載の負荷分散方法。
（付記１８）
前記各代行ノードの代行後負荷予測値の最大値が閾値以下であることを前記所定の条件として、該所定の条件が満たされる場合に前記負荷分散を実行することを特徴とする付記１に記載の負荷分散方法。
（付記１９）
前記代行ノードとなりうるノードのうち、負荷の値が閾値以下のものを前記代行ノードとして前記代行ノード集合を作成することを特徴とする付記１または付記２に記載の負荷分散方法。
（付記２０）
前記代行ノードとなりうるノードのうち、負荷の値が最小のものを前記代行ノードとして前記代行ノード集合を作成することを特徴とする付記１９に記載の負荷分散方法。
（付記２１）
１つ以上の分散処理装置（ノード）によって構成される分散処理システムであって、
他のノード（比較ノード）が担当する処理の一部を分担する候補となる候補ノードは、
自ノードが担当する処理の全てを１つ以上のノード（代行ノード）を用いて代行させる代行ノード集合を作成する代行ノード集合作成部と、
前記各代行ノードの負荷の値を受信する代行ノード負荷受信部と、
前記各代行ノードの負荷の値に基づいて、前記代行ノード集合が前記候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求める代行後負荷予測値算出部と、
前記代行後負荷予測値を前記比較ノードに送信する代行後負荷予測値送信部と、
前記比較ノードによって決定される負荷分散を実行する負荷分散実行部と、
を備え、
前記代行ノードは、
前記候補ノードに対して自ノードの負荷の値を送信する負荷送信部と、
前記比較ノードによって決定される負荷分散を実行する負荷分散実行部と、
を備え、
前記比較ノードは、
前記代行後負荷予測値を受信する代行後負荷予測値受信部と、
前記代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行することを決定する負荷分散決定部と、
決定された負荷分散を実行する負荷分散実行部と、
を備える分散処理システム。
（付記２２）
分散処理システムを構成する分散処理装置（ノード）であって、
自ノードが、他のノード（比較ノード）が担当する処理の一部を分担する候補となるノード（候補ノード）である場合に、自ノードが担当する処理の全てを１つ以上の他のノード（代行ノード）を用いて代行させる代行ノード集合を作成する代行ノード集合作成部と、
前記各代行ノードの負荷の値を受信する代行ノード負荷受信部と、
前記各代行ノードの負荷の値に基づいて、前記代行ノード集合が前記候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求める代行後負荷予測値算出部と、
前記代行後負荷予測値を前記比較ノードに送信する代行後負荷予測値送信部と、
前記比較ノードによって決定される負荷分散を実行する負荷分散実行部と、
を備えた分散処理装置。
（付記２３）
分散処理システムを構成する分散処理装置（ノード）を用いて、
自ノードが、他のノード（比較ノード）が担当する処理の一部を分担する候補となるノード（候補ノード）である場合に、自ノードが担当する処理の全てを１つ以上の他のノード（代行ノード）を用いて代行させる代行ノード集合を作成し、
前記各代行ノードの負荷の値を受信し、
前記各代行ノードの負荷の値に基づいて、前記代行ノード集合が前記候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求め、
前記代行後負荷予測値を前記比較ノードに送信し、
前記比較ノードによって決定される負荷分散を実行する、負荷分散方法。
（付記２４）
分散処理システムに含まれる分散処理装置（ノード）を構成するコンピュータ装置に、
自ノードが、他のノード（比較ノード）が担当する処理の一部を分担する候補となるノード（候補ノード）である場合に、自ノードが担当する処理の全てを１つ以上の他のノード（代行ノード）を用いて代行させる代行ノード集合を作成する代行ノード集合作成ステップと、
前記各代行ノードの負荷の値を受信する代行ノード負荷受信ステップと、
前記各代行ノードの負荷の値に基づいて、前記代行ノード集合が前記候補ノードの処理を代行する場合の各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を求める代行後負荷予測値算出ステップと、
前記代行後負荷予測値を前記比較ノードに送信する代行後負荷予測値送信ステップと、
前記比較ノードによって決定される負荷分散を実行する負荷分散実行ステップと、
を実行させるコンピュータ・プログラム。
（付記２５）
分散処理システムを構成する分散処理装置（ノード）であって、
自ノードが、担当する処理の一部を他の候補ノードに分担させる比較ノードである場合に、
前記候補ノードが担当する処理の全てを代行させる代行ノード集合を構成する各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を、前記候補ノードから受信する代行後負荷予測値受信部と、
前記代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行することを決定する負荷分散決定部と、
決定した負荷分散を実行する負荷分散実行部と、
を備えた分散処理装置。
（付記２６）
分散処理システムを構成する分散処理装置（ノード）を用いて、
自ノードが、担当する処理の一部を他の候補ノードに分担させる比較ノードである場合に、
前記候補ノードが担当する処理の全てを代行させる代行ノード集合を構成する各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を、前記候補ノードから受信し、
前記代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行することを決定し、
決定した負荷分散を実行する、負荷分散方法。
（付記２７）
分散処理システムに含まれる分散処理装置（ノード）を構成するコンピュータ装置に、
自ノードが、担当する処理の一部を他の候補ノードに分担させる比較ノードである場合に、前記候補ノードが担当する処理の全てを代行させる代行ノード集合を構成する各代行ノードの代行後の負荷の予測値（代行後負荷予測値）を、前記候補ノードから受信する代行後負荷予測値受信ステップと、
前記代行後負荷予測値が所定の条件を満たす場合に、前記候補ノードの処理を前記代行ノード集合に代行させて前記候補ノードを空きノードとするとともに、前記比較ノードが担当する処理の一部を、空きノードとなった前記候補ノードに分担させる負荷分散を実行することを決定する負荷分散決定ステップと、
決定した負荷分散を実行する負荷分散実行ステップと、
を実行させるコンピュータ・プログラム。
【符号の説明】
【０１６１】
１、２、３    分散処理システム
１０１  代行ノード集合作成部
１０２  代行後負荷予測値算出部
１０３  代行後負荷予測値判断部
１０４  負荷分散実行部
１０、２０、３０    分散処理装置
１１０、２１０、３１０    比較ノード
１２０、２２０、３２０    候補ノード
１３０、２３０、３３０    代行ノード
２１１    代行後負荷予測値受信部
２１２、３１２    負荷分散決定部
２１５、３１５    負荷分散実行部
２２１、３２１    代行ノード集合作成部
２２２、３２２    代行ノード負荷受信部
２２３    代行後負荷予測値算出部
２２４    代行後負荷予測値送信部
２２５、３２５    負荷分散実行部
２３１、３３１    負荷送信部
２３５、３３５    負荷分散実行部
３１１  負荷情報受信部
３２３  負荷情報作成部
３２４  負荷情報送信部
１００１  ＣＰＵ
１００２  ＲＡＭ
１００３  ＲＯＭ
１００４  記憶装置
１００５  ネットワークインタフェース
【図１】
2013149069.tif 000003
【図２】
2013149069.tif 000004
【図３】
2013149069.tif 000005
【図４】
2013149069.tif 000006
【図５】
2013149069.tif 000007
【図６】
2013149069.tif 000008
【図７】
2013149069.tif 000009
【図８】
2013149069.tif 000010
【図９】
2013149069.tif 000011
【図１０】
2013149069.tif 000012
【図１１】
2013149069.tif 000013
【図１２】
2013149069.tif 000014