(57)【要約】  分散システム（１）は、データ群を分散して管理する複数のノード装置（１００）を備える分散システムであって、複数のノード装置（１００）は、分散システム（１）の論理識別子空間を示すリング上で一意に割り当てられた論理識別子をそれぞれ有し、ノード装置（１００）は、ＩＤ領域に対応するデータの属性値の値域のデータ（１０４）と、その値域端点（１０６）を格納するデータ格納部（１０２）と、自ノードと近隣ノードのＩＤ領域の幅あたりの負荷密度を比較し、負荷密度を均一にする負荷移動量を算出する密度比較部（１１２）と、負荷移動量に基づいて負荷分散処理を行う負荷平滑化部（１１４）と、データ（１０４）を近隣ノードとの間で移動し、値域端点（１０６）を更新するデータ移動部（１１６）と、を備える。
2013190743.tif 000002
【特許請求の範囲】
【請求項１】
データ群を分散して管理する複数のノードを備える分散システムであって、
複数の前記ノードは、前記分散システムの論理識別子空間を示すリング上で一意に割り当てられた論理識別子をそれぞれ有し、
複数の前記ノードは、前記データ群のデータを部分的に記憶する記憶装置をそれぞれ備え、
前記ノードは、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に格納するデータ格納手段と、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノードの近隣のノードから前記負荷密度を取得し、前記自ノードの前記負荷密度と前記近隣のノードの前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出する密度比較手段と、
前記密度比較手段が算出した前記負荷移動量に基づいて、前記近隣のノードと移動するデータを決定し、負荷分散処理を行う負荷分散手段と、
前記負荷分散処理で決定した移動する前記データを、前記近隣のノードとの間で移動するとともに、前記値域端点を更新するデータ移動手段と、を備える分散システム。
【請求項２】
請求項１に記載の分散システムにおいて、
前記ノードの前記負荷分散手段は、前記負荷分散処理を行う機能の有効化または無効化を制御する分散システム。
【請求項３】
請求項２に記載の分散システムにおいて、
前記分散システム内にて、追加または削除対象となる対象ノードと、前記対象ノードの追加または削除の指示とを受け付ける受付手段をさらに備え、
前記受付手段が前記指示を受け付けたとき、前記対象ノードの近隣のノードの前記負荷分散手段が、前記負荷分散処理を行う機能を一時的に無効化する分散システム。
【請求項４】
請求項２または請求項３に記載の分散システムにおいて、
前記ノードの前記負荷分散手段は、前記負荷分散処理を行う機能の有効化または無効化を前記属性値毎に制御する分散システム。
【請求項５】
請求項４に記載の分散システムにおいて、
前記データ移動手段は、前記負荷分散処理で決定した移動する前記データを前記属性値毎に移動し、
前記負荷分散手段は、移動が完了した前記属性値の前記負荷分散処理を行う機能を有効化する分散システム。
【請求項６】
請求項１乃至５いずれかに記載の分散システムにおいて、
前記ノードの前記負荷は、前記ノードの前記記憶装置に記憶される前記データのデータ量または前記ノードの前記記憶装置に記憶された前記データへのアクセス頻度である分散システム。
【請求項７】
請求項１乃至６いずれかに記載の分散システムにおいて、
前記ノードの前記密度比較手段は、前記負荷移動量を下記の式（１）により算出し、
算出された前記負荷移動量が正の値を取るときは、自ノードから前記自ノードの近隣のノードに移動すべき負荷移動量を示し、算出された前記負荷移動量が負の値を取るときは、前記自ノードへ前記近隣のノードから移動すべき負荷移動量を示す分散システム。
（Ｖｓ＋Ｖｍ）Ｒｍ／（Ｒｓ＋Ｒｍ）−Ｖｍ    ・・・式（１）
ここで、ＶｓおよびＲｓは前記自ノードの負荷および前記ＩＤ領域の幅、ＶｍおよびＲｍは前記自ノードの近隣のノードの負荷および前記ＩＤ領域の幅である。
【請求項８】
複数のノード装置がデータ群を分散して管理する分散システムを構成し、前記分散システムに対し参加または離脱可能なノード装置であって、
前記分散システムの論理識別子空間を示すリング上で、他の前記ノード装置と識別可能に一意に割り当てられた論理識別子を有し、
前記データ群のデータを部分的に記憶する記憶装置と、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に格納するデータ格納手段と、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノード装置の近隣のノード装置から前記負荷密度を取得し、前記自ノード装置の前記負荷密度と前記近隣のノード装置の前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出する密度比較手段と、
前記密度比較手段が算出した前記負荷移動量に基づいて、前記近隣のノード装置と移動するデータを決定し、負荷分散処理を行う負荷分散手段と、
前記負荷分散処理で決定した移動する前記データを、前記近隣のノード装置との間で移動するとともに、前記値域端点を更新するデータ移動手段と、を備えるノード装置。
【請求項９】
複数のノード装置がデータ群を分散して管理する分散システムを実現する負荷分散方法であって、
複数の前記ノード装置は、
前記分散システムを構成し、前記分散システムに対し参加または離脱可能であり、
前記データ群のデータを部分的に記憶する記憶装置をそれぞれ備え、
前記ノード装置が、
前記分散システムの論理識別子空間を示すリング上で、他の前記ノード装置と識別可能に論理識別子を一意に割り当て、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に記憶し、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノードの近隣のノードから前記負荷密度を取得し、前記自ノードの前記負荷密度と前記近隣のノードの前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出し、
算出した前記負荷移動量に基づいて、前記近隣のノードと移動するデータを決定し、負荷分散処理を行い、
前記負荷分散処理を行うとき、前記記憶装置に格納されている前記データを前記近隣のノードとの間で移動するとともに、前記値域端点を更新する負荷分散方法。
【請求項１０】
複数のノード装置がデータ群を分散して管理する分散システムを構成し、前記分散システムに対し参加または離脱可能なノード装置を実現するコンピュータが実行するプログラムであって、
前記コンピュータは、前記分散システムの論理識別子空間を示すリング上で、他の前記ノード装置と識別可能に一意に割り当てられた論理識別子を有するとともに、前記データ群のデータを部分的に記憶する記憶装置を備え、
前記コンピュータに、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に記憶する手順、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノードの近隣のノードから前記負荷密度を取得し、前記自ノードの前記負荷密度と前記近隣のノードの前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出する手順、
算出した前記負荷移動量に基づいて、前記近隣のノードと移動するデータを決定し、負荷分散処理を行う手順、
前記負荷分散処理を行うとき、前記記憶装置に格納されている前記データを前記近隣のノードとの間で移動するとともに、前記値域端点を更新する手順をさらに実行させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散システム、負荷分散方法、ノード装置、およびプログラムに関し、特に、複数のノード装置に分散してデータを管理する分散システム、負荷分散方法、ノード装置、およびプログラムに関する。
【背景技術】
【０００２】
分散データシステムにおける負荷分散技術が、非特許文献１に記載されている。この負荷分散技術は、構造化Ｐ２Ｐ（Peer to Peer）において範囲検索を実現するように、各ノードがレンジパーティショニングされたノード間で、各ノードが管理する範囲を動的に変更することで負荷分散を図る技術である。【０００３】
構造化Ｐ２Ｐとは、あるノードが別のノードの通信アドレスを認識する（言い換えれば、「リンクする」）際に、ある規則をもってノード間でリンクするＰ２Ｐであり、大きくＤＨＴ（Distributed Hash Table：分散ハッシュテーブル）とＳｋｉｐＧｒａｐｈ型に分類される。
ＤＨＴは有限のＩＤ（IDentifier）空間を持ち、そのＩＤ空間での距離に応じてノード間でリンクを持つ。これに対してＳｋｉｐＧｒａｐｈ型は、ＩＤの順序に応じてリンクを持つ。すなわち、ＩＤに応じてノードが並びつつ、１つ隣、２つ隣、４つ隣と、距離ではなく順序に応じてリンクを持つ。【０００４】
たとえば、１、３、９、１１、１４、というＩＤがあった場合、ＤＨＴでは、ＩＤが１であるノードは、たとえば、距離が２の指数離れたノード（１＋１、１＋２、１＋４、１＋８、・・・）とリンクするので、ノード３とノード９とリンクする。ＳｋｉｐＧｒａｐｈでは、確率的に２の指数だけ隣のノードとリンクする。この例では、ノード１は１つ隣のノード３、２つ隣のノード９、４つ隣のノード１４とリンクする。【０００５】
非特許文献１には、ＳｋｉｐＧｒａｐｈ型を想定しており、ＩＤが隣接するノード間で担当するデータの範囲を変更し、負荷分散を図ることが記載されている。その際、隣接するノードの保持するデータ量が均一になるように、データを移動する。この操作をＮＢＲＡＤＪＵＳＴと呼ぶ。また、ＲＥＯＲＤＥＲという操作は、ノードのＩＤを隣接しないノードに変更する。非特許文献１には、このＮＢＲＡＤＪＵＳＴという操作と、ＲＥＯＲＤＥＲという操作とを、どのタイミングで制御するかについて記載されている。【０００６】
非特許文献１をＤＨＴに適用すると、負荷を均一化するように各ノードのＩＤを変更することになる。これは、ＩＤの距離に応じてリンクを決定するＤＨＴにおいては、リンク構成に影響を与えるため、Ｐ２Ｐルーティングのホップ数や次数（リンク数）に悪い影響を与えることが述べられている。【０００７】
上記の例において、ノード１１とノード１４の範囲にデータが多い場合について考える。この場合、ノード９およびノード１１のＩＤを変更して、それぞれノード１０およびノード１２となったとする。ＳｋｉｐＧｒａｐｈではノードのＩＤの順序が変わらないので、リンク関係に変更は生じない。しかし、距離に基づいてリンクするＤＨＴでは、リンク関係に変更が生じる。【０００８】
また、別の分散データシステムにおける負荷分散技術が、非特許文献２に記載されている。この技術はＤＨＴを想定し、負荷分散を目的として、隣接ノード間でＩＤを変更する。すなわち、隣接ノード間でデータ量が均一になるようにＩＤを変更する。あるノードの負荷が高くなった場合、隣接ノード間でＩＤを変更することでデータの負荷の差をなくすため、隣接ノードに負荷が移動する。そして、さらにその隣接ノードへと負荷が伝搬するため、熱伝搬のようにして、全体で負荷を平準化するようになる。
【先行技術文献】
【非特許文献】
【０００９】
【非特許文献１】Ganesan, P.、外２名、"Online balancing of range-partitioned data with applications to peer-to-peer systems"、Proceedings of the 30th international conference on Very large data bases Conference、２００４年、Volume 30、p. 444−455、［平成24年5月1日検索］、インターネット〈URL：http://www.vldb.org/conf/2004/RS11P3.PDF〉
【非特許文献２】Rieche, S.、外２名、"A thermal-dissipation-based approach for balancing data load in distributed hash tables"、 Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks (LCN'04)、２００４年、p.15−23
【発明の概要】
【発明が解決しようとする課題】
【００１０】
上述した分散データシステムにおいては、負荷を均一化するように各ノードのＩＤを変更するため、また、ＩＤの距離に応じてリンクを決定するＤＨＴにおいては、リンク構成に影響を与えるため、ノード間で負荷分散を行う際に、ルーティング性能の劣化や、各ノードのリンク数の分布の偏りなどが生じるという問題点があった。【００１１】
本発明の目的は、上述した課題であるノード間で負荷分散を行う際に、ルーティング性能の劣化や、各ノードのリンク数の分布の偏りなどが生じるという問題点を解決する分散システム、負荷分散方法、ノード装置、およびプログラムを提供することにある。
【課題を解決するための手段】
【００１２】
本発明の分散システムは、
データ群を分散して管理する複数のノードを備える分散システムであって、
複数の前記ノードは、前記分散システムの論理識別子空間を示すリング上で一意に割り当てられた論理識別子をそれぞれ有し、
複数の前記ノードは、前記データ群のデータを部分的に記憶する記憶装置をそれぞれ備え、
前記ノードは、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に格納するデータ格納手段と、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノードの近隣のノードから前記負荷密度を取得し、前記自ノードの前記負荷密度と前記近隣のノードの前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出する密度比較手段と、
前記密度比較手段が算出した前記負荷移動量に基づいて、前記近隣のノードと移動するデータを決定し、負荷分散処理を行う負荷分散手段と、
前記負荷分散処理で決定した移動する前記データを、前記近隣のノードとの間で移動するとともに、前記値域端点を更新するデータ移動手段と、を備える。【００１３】
本発明のノード装置は、
複数のノード装置がデータ群を分散して管理する分散システムを構成し、前記分散システムに対し参加または離脱可能なノード装置であって、
前記分散システムの論理識別子空間を示すリング上で、他の前記ノード装置と識別可能に一意に割り当てられた論理識別子を有し、
前記データ群のデータを部分的に記憶する記憶装置と、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に格納するデータ格納手段と、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノード装置の近隣のノード装置から前記負荷密度を取得し、前記自ノード装置の前記負荷密度と前記近隣のノード装置の前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出する密度比較手段と、
前記密度比較手段が算出した前記負荷移動量に基づいて、前記近隣のノード装置と移動するデータを決定し、負荷分散処理を行う負荷分散手段と、
前記負荷分散処理で決定した移動する前記データを、前記近隣のノード装置との間で移動するとともに、前記値域端点を更新するデータ移動手段と、を備える。【００１４】
本発明の負荷分散方法は、
複数のノード装置がデータ群を分散して管理する分散システムを実現する負荷分散方法であって、
複数の前記ノード装置は、
前記分散システムを構成し、前記分散システムに対し参加または離脱可能であり、
前記データ群のデータを部分的に記憶する記憶装置をそれぞれ備え、
前記ノード装置が、
前記分散システムの論理識別子空間を示すリング上で、他の前記ノード装置と識別可能に論理識別子を一意に割り当て、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に記憶し、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノードの近隣のノードから前記負荷密度を取得し、前記自ノードの前記負荷密度と前記近隣のノードの前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出し、
算出した前記負荷移動量に基づいて、前記近隣のノードと移動するデータを決定し、負荷分散処理を行い、
前記負荷分散処理を行うとき、前記記憶装置に格納されている前記データを前記近隣のノードとの間で移動するとともに、前記値域端点を更新する。【００１５】
本発明のコンピュータプログラムは、
複数のノード装置がデータ群を分散して管理する分散システムを構成し、前記分散システムに対し参加または離脱可能なノード装置を実現するコンピュータが実行するプログラムであって、
前記コンピュータは、前記分散システムの論理識別子空間を示すリング上で、他の前記ノード装置と識別可能に一意に割り当てられた論理識別子を有するとともに、前記データ群のデータを部分的に記憶する記憶装置を備え、
前記コンピュータに、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に記憶する手順、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノードの近隣のノードから前記負荷密度を取得し、前記自ノードの前記負荷密度と前記近隣のノードの前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出する手順、
算出した前記負荷移動量に基づいて、前記近隣のノードと移動するデータを決定し、負荷分散処理を行う手順、
前記負荷分散処理を行うとき、前記記憶装置に格納されている前記データを前記近隣のノードとの間で移動するとともに、前記値域端点を更新する手順をさらに実行させるためのものである。【００１６】
なお、以上の構成要素の任意の組合せ、本発明の表現を方法、装置、システム、記録媒体、コンピュータプログラムなどの間で変換したものもまた、本発明の態様として有効である。【００１７】
また、本発明の各種の構成要素は、必ずしも個々に独立した存在である必要はなく、複数の構成要素が一個の部材として形成されていること、一つの構成要素が複数の部材で形成されていること、ある構成要素が他の構成要素の一部であること、ある構成要素の一部と他の構成要素の一部とが重複していること、等でもよい。【００１８】
また、本発明の方法およびコンピュータプログラムには複数の手順を順番に記載してあるが、その記載の順番は複数の手順を実行する順番を限定するものではない。このため、本発明の方法およびコンピュータプログラムを実施するときには、その複数の手順の順番は内容的に支障のない範囲で変更することができる。【００１９】
さらに、本発明の方法およびコンピュータプログラムの複数の手順は個々に相違するタイミングで実行されることに限定されない。このため、ある手順の実行中に他の手順が発生すること、ある手順の実行タイミングと他の手順の実行タイミングとの一部ないし全部が重複していること、等でもよい。
【発明の効果】
【００２０】
本発明によれば、ノードの追加または削除時のシステムへの影響を抑える分散システム、負荷分散方法、ノード装置、およびプログラムが提供される。
【図面の簡単な説明】
【００２１】
上述した目的、およびその他の目的、特徴および利点は、以下に述べる好適な実施の形態、およびそれに付随する以下の図面によってさらに明らかになる。【００２２】
【図１】本発明の実施の形態に係る分散システムの構成を示す機能ブロック図である。
【図２】本発明の実施の形態に係る分散システムのＩＤ空間の一例を示す図である。
【図３】本発明の実施の形態に係る分散システムの構成例を概念的に示す図である。
【図４】本発明の実施の形態に係る分散システムの動作の一例を示すフローチャートである。
【図５】本発明の実施の形態に係る分散システムの構成を示す機能ブロック図である。
【図６】本発明の実施の形態に係る分散システムのノード装置の密度比較部における負荷差分算出処理の手順の一例を示すフローチャートである。
【図７】本発明の実施の形態に係る分散システムのノード装置の負荷平滑化部の負荷分散処理の手順の一例を示すフローチャートである。
【図８】本発明の実施の形態に係る分散システムの構成を示す機能ブロック図である。
【図９】本発明の実施の形態に係る分散システムの動作の一例を示すフローチャートである。
【図１０】本発明の実施の形態に係る分散システムのノード間の負荷分散処理機能の制御を説明するための図である。
【図１１】本発明の実施の形態に係る分散システムの動作の一例を示すフローチャートである。
【図１２】本発明の実施の形態に係る分散システムの構成を示す機能ブロック図である。
【図１３】本発明の実施の形態に係る分散システムのノードの参加または離脱時の動作の一例を示すフローチャートである。
【図１４】本発明の実施の形態に係る分散システムにおけるノードの動作を説明するための図である。
【図１５】本発明の実施の形態に係る分散システムにおいて、ノードの参加または離脱要求を受け付けた時の処理の手順の一例を示すフローチャートである。
【図１６】本発明の実施の形態に係る分散システムにおいて、ノードの参加または離脱終了通知を受け付けた時の処理の手順の一例を示すフローチャートである。
【図１７】本発明の分散システムの実施例において、ノードの参加または離脱が行われる前の各ノードの負荷の状態を概念的に示す図である。
【図１８】本発明の分散システムの実施例１において、ノードの参加または離脱が行われた後の各ノードの負荷の状態を概念的に示す図である。
【図１９】本発明の分散システムの実施例２において、ノードの参加または離脱が行われた後の各ノードの負荷の状態を概念的に示す図である。
【発明を実施するための形態】
【００２３】
以下、本発明の実施の形態について、図面を用いて説明する。尚、すべての図面において、同様な構成要素には同様の符号を付し、適宜説明を省略する。
【００２４】
（第１の実施の形態）
図１は、本発明の実施の形態に係る分散システム１の構成を示す機能ブロック図である。
本発明の実施の形態に係る分散システム１は、データ群を分散して管理する複数のノード（ノード装置１００）を備え、複数のノード装置１００は、論理識別子空間を示すリング上で一意に割り当てられた論理識別子をそれぞれ有する。
複数のノード装置１００は、データ群のデータ１０４を部分的に記憶する記憶装置（データ格納部１０２）をそれぞれ備える。ノード装置１００は、リング上の論理識別子で区切られるＩＤ領域にデータ群に含まれるデータの属性値の範囲を示す値域を対応付け、論理識別子のＩＤ領域に対応する値域のデータ１０４を記憶装置（データ格納部１０２）に格納するとともに、記憶装置（データ格納部１０２）に格納されるデータ１０４の値域を示す値域端点１０６を記憶装置（データ格納部１０２）に格納し、記憶装置（データ格納部１０２）に格納されたデータ１０４の負荷を、ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、リング上で自ノードの近隣のノードから負荷密度を取得し、自ノードの負荷密度と近隣のノードの負荷密度とを比較し、負荷密度を均一にするための負荷移動量を算出する密度比較算出部（密度比較部１１２）と、密度比較部１１２が算出した負荷移動量に基づいて、近隣のノードと移動するデータを決定し、負荷分散処理を行う負荷分散部（負荷平滑化部１１４）と、負荷分散処理で決定した移動するデータを、近隣のノードとの間で移動するとともに、値域端点１０６を更新するデータ移動部１１６と、を備える。
【００２５】
ここで、ノード（ノード装置１００）とは、論理ノードであり、たとえば、タスク、プロセス、インスタンス等のようなソフトウェア要素であり、本実施形態に係るノード装置のようなコンピュータにより実現される。一つのコンピュータに複数のノードを含んでもよい。また、コンピュータがプロセッサコアを複数有する場合、複数のプロセッサコアに跨って、一つのノードが存在してもよい。図１のノード装置１００は、この論理ノードを示している。以下、ノード装置１００は、「ノード」または「論理ノード」とも呼ぶ。
【００２６】
本発明は、ＤＨＴのように有限な論理識別子空間を持つ分散データシステムを想定する。
ノードの論理識別子とは、リング構造を有する有限の識別子空間内で複数の論理ノードに一意にそれぞれ割り当てられる複数の識別子の中の、論理ノードに割り当てられた識別子である。すなわち、各論理ノードには、ユニークな識別子（以降、ノードＩＤまたはＩＤとも表記する）がそれぞれ割り当てられる。リング構造を有する有限の識別子空間とは、その空間内で最大の識別子の次に最小の識別子が続くように定義された識別子空間を意味する。すなわち、リングとは、ある有限の整数空間で表現される論理識別子（ＩＤ）が、その整数空間の最小値から最大値へと順に並び、最大値の次に最小値が来る循環を持つ論理識別子空間を示す。
【００２７】
論理ノードは、識別子空間（以下、「ＩＤ空間」とも呼ぶ）内におけるノード識別子と他の識別子との間の関係に応じて他の論理ノード（上記リンク先論理ノード）との間にリンクを確立する。リンク確立とは、論理ノードが当該リンク先論理ノードと通信可能となることを意味し、たとえば、相互にＩＰ（Internet Protocol）アドレスを持ち合うことで実現される。なお、本実施形態は、当該リンクの実現手法を制限しない。
【００２８】
このように、本実施形態では、データを分散管理する複数の論理ノードにおいて、ノードＩＤに基づくトポロジが構築される。
【００２９】
一方、各論理ノードは、上述のデータ格納部１０２のように、格納する部分データ１０４に対応する値域情報をそれぞれ管理する。そして、属性毎の値域境界は、ＩＤ空間内において隣接する論理ノード間に位置する。すなわち、ノードのＩＤ空間のリング構造に対応して、各論理ノードが担当する属性毎の値域が決定される。これにより、ＩＤ空間と同様に、属性毎の属性値空間は、循環順序（リング構造）を持つものとして管理され得る。これは、ＩＤ空間のリンクトポロジ上に、属性値空間の値域情報ビューを重畳させて管理する構成であるとも言える。この構成により、値域変更に対して、ＩＤ空間のリンクトポロジは変更することなく、それに重畳されている値域情報ビューのみの変更で対応することができる。
【００３０】
なお、データ格納部１０２に格納される値域境界値は、論理ノードが格納する部分データの値域の起点であってもよいし、その値域の終点であってもよいし、その値域の始点と終点との組み合わせであってもよい。また、値域格納部には、論理ノードの値域境界値のみならず、論理ノードの隣接ノードが格納する部分データの値域境界値が格納されるようにしてもよい。本実施形態では、ノードが格納するデータ１０４の値域の終点を保持するものとし、これを値域端点１０６と呼ぶ。
【００３１】
図２は、本発明の実施の形態に係る分散システム１のＩＤ空間の一例を示す図である。
図２では、ｎビット長のＩＤ空間（ここでは、１０ビット）で示されるリング上に一意に割り当てられた論理識別子（以下、「論理ＩＤ」とも呼ぶ）７０、１２９、２５０、４１３、５５１、６４０、６９８、８０３、および９８０をそれぞれ有する９個のノードを含む分散システム１の例を示す。
【００３２】
図２に示すように、ＩＤ空間はリング構造を持つ。以降、このリング構造はＩＤリングとも表記される。このＩＤリング上では、各ノードにとって、自ノードのＩＤより大きくかつ最も近いＩＤを持つノードは、Successorノードと呼び、自ノードのＩＤより小さくかつ最も近いＩＤを持つノードは、Predecessorノードと呼ぶものとする。そして、ＩＤリングでは、ＩＤ空間内で最大値のノードＩＤを持つノード（図２では、ＩＤ９８０のノード）が、ＩＤ空間内で最小値のノードＩＤを持つノード（図２では、ＩＤ７０のノード）をSuccessorノードとし、ＩＤ空間内で最小値のノードＩＤを持つノード（図２では、ＩＤ７０のノード）が、ＩＤ空間内で最大値のノードＩＤを持つノード（図２では、ＩＤ９８０のノード）をPredecessorノードとする。
【００３３】
なお、このようなＩＤリング上のリンク関係は、ノードＩＤの値により即座に特定可能であるため、対応テーブルに格納されなくてもよいし、上述のようなＩＤ空間上で隣接しないノード間の関係と共にリンクテーブルに格納されてもよい。
【００３４】
また、各ノードは、データ群のデータを部分的に格納する。各ノードが担当するデータは、データの属性値の値域で範囲が定められている。たとえば、論理ＩＤ１２９のノードは、データの属性値が、（１８，３２］の範囲のデータを保持する。ここで、"（"はその値を含まず、"］"はその値を含むことを示すものとする。図２では、論理ＩＤ１２９のノードは、（１８，３２］の範囲のデータを３５個保持しているものとする。
本実施形態の分散システム１は、各ノードが担当するデータの属性値の範囲を、値域の終点、すなわち、値域端点で管理することができる。
【００３５】
なお、本発明は、主に、分散データベースにおける範囲検索を効率的に扱うことのできるレンジパーティショニングを想定しているが、データを格納するのではなく、連続的クエリ（Continuous Query）やSubscribe条件を格納するデータストリームシステムにも適用可能である。また、データ量を均一化するだけでなく、単位時間当たりのデータ処理量を均一化させ、ある範囲のデータを処理する、アプリケーションサーバ、負荷分散装置にも適用可能である。
【００３６】
図３は、本実施形態における分散システム１の構成例を概念的に示す図である。本実施形態における分散システム１は、複数のデータサーバ１０等を有する。データサーバ１０は相互にネットワーク９によって通信可能に接続される。データサーバ１０は、本実施形態におけるノード装置１００に対応する。データサーバ１０は、アプリケーションや他の端末からの要求に応じて、データサーバ１０に格納されるデータにアクセスし、所望のデータを取得する。
【００３７】
データサーバ１０は、いわゆるコンピュータであり、たとえば、バス５で相互に接続される、ＣＰＵ（Central Processing Unit）２、メモリ３、および入出力インタフェース（Ｉ／Ｆ）４等を有する。メモリ３は、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ハードディスク、または可搬型記憶媒体等である。入出力Ｉ／Ｆ４は、ネットワーク９を介して他のデータサーバ１０、データ操作クライアント５０、他の端末（不図示）、または記憶装置等と通信を行う通信装置７等と接続される。入出力Ｉ／Ｆ４は、表示装置や入力装置等のようなユーザインタフェース装置と接続されてもよい。なお、本実施形態は、データサーバ１０のハードウェア構成を限定しない。以下の各図において、本発明の本質に関わらない部分の構成については省略してあり、図示されていない。
【００３８】
また、データサーバ１０は、コンピュータのハードウェアとソフトウェアの任意の組合せによって実現される。そして、その実現方法、装置にはいろいろな変形例があることは、当業者には理解されるところである。以下説明する各図は、ハードウェア単位の構成ではなく、機能単位のブロックを示している。また、データサーバ１０は、仮想サーバなどにより構成されてもよい。
また、データサーバ１０のＣＰＵ２が、ＲＯＭやハードディスク等に記憶されるプログラムをＲＡＭに読み出して実行することにより、ノード装置１００の図１の各ユニットの各機能を実現することができる。
【００３９】
本発明の実施の形態に係るノード装置１００は、コンピュータプログラムに対応する各種の処理動作をＣＰＵ２が実行することにより、前述のような各種ユニットが各種機能として実現される。
【００４０】
本発明の実施の形態に係るコンピュータプログラムは、ノード装置１００を実現させるためのコンピュータが実行するプログラムであって、コンピュータに、リング上の論理識別子で区切られるＩＤ領域にデータ群に含まれるデータの属性値の範囲を示す値域を対応付け、論理識別子のＩＤ領域に対応する値域のデータ１０４をデータ格納部１０２に格納するとともに、データ格納部１０２に格納されるデータ１０４の値域を示す値域端点１０６をデータ格納部１０２に記憶する手順、データ格納部１０２に格納されたデータ１０４の負荷を、ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、リング上で自ノードの近隣のノードから負荷密度を取得し、自ノードの負荷密度と近隣のノードの負荷密度とを比較し、負荷密度を均一にするための負荷移動量を算出する手順、算出した負荷移動量に基づいて、近隣のノードと移動するデータを決定し、負荷分散処理を行う手順、負荷分散処理を行うとき、データ格納部１０２に格納されているデータ１０４を近隣のノードとの間で移動するとともに、値域端点１０６を更新する手順、を実行させるように記述されている。
【００４１】
本実施形態のコンピュータプログラムは、コンピュータで読み取り可能な記録媒体に記録されてもよい。記録媒体は特に限定されず、様々な形態のものが考えられる。また、プログラムは、記録媒体からコンピュータのメモリにロードされてもよいし、ネットワークを通じてコンピュータにダウンロードされ、メモリにロードされてもよい。
【００４２】
本発明の実施の形態に係る分散システム１は、図１に示すように、複数のノード装置１００を含み、各ノード装置１００は、互いにネットワーク９を介して接続される。
【００４３】
ノード装置１００は、データ格納部１０２と、ＩＤ格納部１０８と、密度比較部１１２と、負荷平滑化部１１４と、データ移動部１１６と、インタフェース部（図中、「Ｉ／Ｆ」と示す）１１８と、を備える。
【００４４】
データ格納部１０２およびＩＤ格納部１０８は、たとえば、図３のデータサーバ１０のメモリ３で実現することができる。インタフェース部１１８は、たとえば、図３のデータサーバ１０の入出力Ｉ／Ｆ４および通信装置７により実現することができる。
【００４５】
データ格納部１０２は、本発明の分散システム１が管理するデータの一部を格納する。好適には、各ノード装置１００が担当する範囲を表す値域メタデータ（値域端点１０６）も別途格納される。
そして、値域端点１０６に基づいて、この範囲に含まれない値へのアクセスは失敗することが望ましい。その理由は、データ移動に伴いこのノードが担当する範囲が変更されたことを他のノードが認識しないまま、このノードのデータにアクセスすることがあるからである。エラーを返されたノードは、他のノードに値域を問い合わせる等の処理を行い、正しいノードにアクセスし直す等の処理を行うことができる。
【００４６】
ＩＤ格納部１０８は、ノード装置１００の論理ＩＤを格納する。上述したように、論理ＩＤは、分散システム１で一意な、あるビット長の値である。本実施形態において、データ格納部１０２およびＩＤ格納部１０８は、図３のデータサーバ１０のメモリ３で構成することができる。
【００４７】
密度比較部１１２は、データ格納部１０２に格納されたデータの負荷を、ＩＤ領域の幅（ＩＤ幅とも呼ぶ）あたりの負荷密度に換算して求めるとともに、リング上で自ノードの近隣のノードから負荷密度をインタフェース部１１８を介して取得し、自ノードの負荷密度と近隣のノードの負荷密度とを比較し、負荷密度を均一にするための負荷移動量を算出する。本実施形態では、近隣のノードとは、Successorノードとすることができる。さらに、密度比較部１１２は、他のノードから負荷密度の問い合わせを受け付けた場合、インタフェース部１１８を介して問い合わせ元に自ノードの負荷密度を返信する機能も有する。
【００４８】
すなわち、密度比較部１１２は、自ノードとＩＤが隣接する他ノードとの間の、ＩＤ密度の比較を行い、その密度が均一になるために必要な負荷移動量の算出を行う。ＩＤ密度とは、ＩＤ幅あたりの負荷であり、ＩＤ幅とは、各ノードにとって、Predecessorノードから自ノードへの距離に相当する。ただし、この距離は、ＩＤ空間のリングに沿った差である。ＩＤ空間サイズを２ｎとすると、ノードｍのＩＤ幅は、ＩＤｍ−ＩＤｐｍｏｄ２ｎで算出される。たとえば、ＩＤが３であり、Predecessorが２５０であり、ＩＤ空間が２５６であった場合は、３−２５０ｍｏｄ２５６＝９となる。
【００４９】
ここで、負荷は、データ量でもよく、単位時間当たりのデータへのアクセス数、すなわち、アクセス頻度でもよい。また、データ量は、データ数、データのバイト数、ブロック数、またはタプル数でもよい。
【００５０】
負荷平滑化部１１４は、自ノードと隣接するノードの負荷移動量を、密度比較部１１２に問い合わせて取得する。また、この差分をデータ移動部１１６に与えて、データの移動を指示する。ただし、算出された負荷移動量の全てをデータ移動部１１６に指示するのではなく、その一定割合（たとえば、０．５をかけた値）、あるいは一定期間前の過去からの移動量の総和や、過去に算出された移動量の差分などを、実際に移動指示する量に反映させてもよい。また、この移動量を制御する処理は、負荷平滑化部１１４ではなく、データ移動部１１６で行ってもよい。
【００５１】
データ移動部１１６は、自ノードとＩＤが隣接する他ノードとの間で、そのデータ格納部１０２に格納されるデータを移動させ、そのデータ移動量に応じた値域メタデータ（値域端点１０６）の変更を行う。負荷分散により他のノードにデータを移動する際には、ある範囲、たとえば、移動先のノードが担当する側の自ノードが担当する範囲の端からのある範囲のデータを移動先のノードに移動する。
また、データに対するアクセスが行われている場合には、一度に全てのデータを移動させず、サービス品質を著しく低下させないように、一部のデータのみを移動させながら、徐々に移動を行うものとする。
【００５２】
インタフェース部１１８は、ネットワーク９を介して他のノード装置１００との通信を行う。上述したように、図３の入出力Ｉ／Ｆ４および通信装置７により構成される。
【００５３】
上述のような構成において、本実施の形態の分散システム１における負荷分散方法を以下に説明する。図４は、本実施形態の分散システム１の動作の一例を示すフローチャートである。
【００５４】
本実施形態の負荷分散方法は、複数のノード装置１００がデータ群を分散して管理する分散システム１を実現する負荷分散方法である。複数のノード装置１００は、分散システム１を構成し、分散システム１に対し参加または離脱可能であり、データ群のデータを部分的に記憶する記憶装置（データ格納部１０２）をそれぞれ備える。本実施形態の負荷分散方法は、ノード装置１００が、分散システム１の論理識別子空間を示すリング上で、他のノード装置１００と識別可能に論理識別子を一意に割り当て（ステップＳ１０１）、リング上の論理識別子で区切られるＩＤ領域にデータ群に含まれるデータの属性値の範囲を示す値域を対応付け、論理識別子のＩＤ領域に対応する値域のデータ１０４をデータ格納部１０２に格納するとともに、データ格納部１０２に格納されるデータ１０４の値域を示す値域端点１０６をデータ格納部１０２に記憶し（ステップＳ１０３）、データ格納部１０２に格納されたデータ１０４の負荷を、ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに（ステップＳ１０５）、リング上で自ノードの近隣のノードから負荷密度を取得し（ステップＳ１０７）、自ノードの負荷密度と近隣のノードの負荷密度とを比較し、負荷密度を均一にするための負荷移動量を算出し（ステップＳ１０９）、算出した負荷移動量に基づいて、近隣のノードと移動するデータを決定し、負荷分散処理を行い（ステップＳ１１１）、負荷分散処理を行うとき、近隣のノードとの間で移動するとともに（ステップＳ１１３）、値域端点を更新する（ステップＳ１１５）。
【００５５】
詳細には、分散システム１において、まず、各ノード装置１００には、論理ＩＤが割り当てられる（ステップＳ１０１）。割り当てられた論理ＩＤは、ＩＤ格納部１０８に格納される。
そして、各ノード装置１００が、リング上の論理ＩＤで区切られるＩＤ領域にデータ群に含まれるデータの属性値の範囲を示す値域を対応付け、論理ＩＤのＩＤ領域に対応する値域のデータ１０４をデータ格納部１０２に格納する（ステップＳ１０３）。さらに、各ノード装置１００が、データ格納部１０２に格納されるデータ１０４の値域を示す値域端点１０６をデータ格納部１０２に記憶する（ステップＳ１０３）。
【００５６】
そして、密度比較部１１２が、データ格納部１０２に格納されたデータ１０４の負荷を、ＩＤ領域の幅あたりの負荷密度に換算する（ステップＳ１０５）。さらに、密度比較部１１２が、リング上で自ノードの近隣のノードから負荷密度を取得する（ステップＳ１０７）。
【００５７】
ここで、近隣のノードとは、上述したように、Successorノードとすることができる。また、本実施形態では、自ノードとリング上で論理ＩＤが、論理ＩＤ空間で一つだけ隣のSuccessorノードとの間の負荷密度を比較する構成としているが、これに限定されない。自ノードとリング上で論理ＩＤが隣のSuccessorノードからさらに論理ＩＤが連続する複数のノードも含むノード群との間で負荷密度を比較してもよい。
【００５８】
そして、密度比較部１１２が、自ノードの負荷密度と近隣のノード（Successorノード）の負荷密度とを比較し、負荷密度を均一にするための負荷移動量を算出する（ステップＳ１０９）。密度比較部１１２が、算出した負荷移動量に基づいて、近隣のノード（Successorノード）と移動するデータを決定し、負荷平滑化部１１４に受け渡す。そして、負荷平滑化部１１４が、負荷移動量に基づき、負荷分散処理を行う（ステップＳ１１１）。
【００５９】
負荷平滑化部１１４が、負荷分散処理を行うとき、データ移動部１１６が、データ格納部１０２に格納されているデータ１０４を近隣のノード（Successorノード）との間でインタフェース部１１８を介して移動する（ステップＳ１１３）。そして、データ移動部１１６が、データ格納部１０２の値域端点１０６を更新する（ステップＳ１１５）。
【００６０】
以上説明したように、本発明の実施の形態の分散システム１によれば、ノード間で負荷分散を行う際に、ルーティング性能の劣化や、各ノードのリンク数の分布の偏りなどが生じるという問題点を解決することができる。その理由は、ノード間で負荷分散を行う際、ＩＤ幅あたりの負荷密度が均一になるように各ノードが担当するデータの値域を決定してデータの移動を行い、格納データの属性毎に値域端点のみを変更し、ノードの論理ＩＤを変更しないからである。そして、ノードの論理ＩＤの変更に伴って起こる可能性のある、データ検索、データ登録といったデータベースシステム、アプリケーションシステムの応答時間の劣化も回避できる。
【００６１】
（第２の実施の形態）
図５は、本発明の実施の形態に係る分散システムの構成を示す機能ブロック図である。
本実施形態の分散システム１は、上記実施形態とは、負荷分散処理を行う機能の有効化または無効化制御できる点で相違する。また、本実施形態では、密度比較部の負荷移動量の算出方法について具体例を用いて説明する。
本実施形態の分散システム１において、ノード装置２００は、図１の上記実施形態のノード装置１００の同様なデータ格納部１０２と、ＩＤ格納部１０８と、データ移動部１１６と、インタフェース部１１８と、を備えるとともに、さらに、密度比較部２１２と、負荷平滑化部２１４と、を備える。
【００６２】
本発明の実施の形態に係る分散システム１において、ノード装置２００の負荷分散部（負荷平滑化部２１４）は、負荷分散処理を行う機能の有効化または無効化を制御する。たとえば、分散システム１のノード数に変化があったときに、負荷分散処理を行う機能を一時的に無効化する。
【００６３】
本実施形態のノード装置２００において、密度比較部２１２は、Successorノードと自ノードとPredecessorノードのＩＤを元に、Successorノードおよび自ノードのＩＤ幅を求め、これをＲｓとＲｍとする。そして、密度比較部２１２は、Successorノードと自ノードの負荷量を取得し、これをＶｓとＶｍとする。これらを用いて、密度比較部２１２は、以下の式（１）で自ノードとSuccessorノードとの間の負荷移動量を算出する。
（Ｖｓ＋Ｖｍ）Ｒｍ／（Ｒｓ＋Ｒｖ）−Ｖｍ      ・・・  式（１）
この負荷移動量は、負の値を取る時、Successorから自ノードへの負荷移動量を表し、正の値を取る時、自ノードからSuccessorへの負荷移動量を表す。
【００６４】
また、内部では、この負荷分散処理の機能を有効にするか、無効にするかの状態が、たとえば、フラグ等に保持される。負荷平滑化部２１４では、たとえば、フラグの状態がＯＮである限り、負荷分散処理を実行し、フラグの状態がＯＦＦになると、動作しなくなる。
【００６５】
このように構成された本実施形態の分散システム１の動作について、以下説明する。
図６は、本実施形態の分散システム１のノード装置２００の密度比較部２１２における負荷差分（移動量）算出処理Ｓ２００の手順の一例を示すフローチャートである。図７は、本実施形態の分散システム１のノード装置２００の負荷平滑化部２１４の負荷分散処理Ｓ２１０の手順の一例を示すフローチャートである。以下、図５乃至図７を用いて説明する。
【００６６】
まず、図６に示すように、負荷差分（移動量）算出処理Ｓ２００において、密度比較部２１２が、Successorノードと自ノードとPredecessorノードのＩＤを元に、Successorノードおよび自ノードのＩＤ幅を求め、これをＲｓとＲｍとする（ステップＳ２０１）。そして、密度比較部２１２が、Successorノードと自ノードの負荷量を取得し、これをＶｓとＶｍとする（ステップＳ２０３）。これらを用いて、密度比較部２１２が、上記の式（１）を用いて自ノードとSuccessorノードとの間の負荷移動量を算出し、これを差分（負荷移動量）として返す（ステップＳ２０５）。
【００６７】
次に、図６の上記負荷差分算出処理Ｓ２００で、密度比較部２１２が算出した負荷移動量に基づいて、図７に示す負荷平滑化部２１４における負荷分散処理Ｓ２１０に進む。本実施形態では、上述したように、負荷平滑化部２１４は、負荷分散処理を行う機能を有効化するか、無効化するか制御することができる。図７の負荷分散処理Ｓ２１０は、この負荷分散処理を行う機能が有効（ＯＮ）である場合に（ステップＳ２１１のＹＥＳ）、ステップＳ２１３〜ステップＳ２１９の処理を行い、負荷分散処理を行う機能が無効（ＯＦＦ）である場合には（ステップＳ２１１のＮＯ）、処理を終了し、負荷分散処理を行わないようにする。
【００６８】
なお、負荷平滑化部２１４において、初期状態は、負荷分散処理を行う機能は有効（ＯＮ）である。
また、たとえば、負荷分散処理を行うことで、分散システム１への影響が想定される場合等に負荷分散処理機能を無効（ＯＦＦ）にすることが考えられる。負荷分散処理機能を無効にすべき条件を予め設定し、条件を満たす場合、負荷分散処理機能を無効にしてもよい。負荷分散処理機能を無効にする条件等については、後述する実施形態で詳細に説明する。
【００６９】
そして、負荷分散処理を行う機能が有効（ＯＮ）である場合（ステップＳ２１１のＹＥＳ）、密度比較部２１２に問い合わせ、密度比較部２１２が算出した隣接ノードとの負荷の差分（移動量）を取得する（ステップＳ２１３）。得られた差分の絶対値が一定値以上であれば（ステップＳ２１５のＹＥＳ）、負荷平滑化部２１４が、この差分を反映させるようにデータ移動部１１６にデータ移動の指示を与える（ステップＳ２１７）。得られた差分の絶対値が一定値未満であれば（ステップＳ２１５のＮＯ）、負荷平滑化部２１４は、何もせず（ステップＳ２１７はバイパス）、一定時間待ち（ステップＳ２１９）、ステップＳ２１１に戻る。
【００７０】
以上説明したように、本発明の実施の形態の分散システム１によれば、上記実施形態と同様な効果を奏するとともに、さらに、ノード毎に負荷分散処理機能を有効化または無効化できるので、負荷分散処理による分散システム１への影響が想定される場合には、負荷分散処理機能を無効にするなどの対策を取ることができ、分散システム１の安定性を確保し、信頼性を維持することができる。
【００７１】
（第３の実施の形態）
本実施形態の分散システム１は、上記実施の形態とは、分散システム１へのノードの追加または削除の指示を受け付け、ノードのＩＤ幅あたりの負荷密度に急激な変化が生じた場合に、一時的に負荷分散処理を行う機能を無効化する点で相違する。
【００７２】
図８は、本発明の実施の形態に係る分散システム１の構成を示す機能ブロック図である。
本実施形態のノード装置３００は、図５の上記実施形態のノード装置２００と同様なデータ格納部１０２と、ＩＤ格納部１０８と、密度比較部２１２と、データ移動部１１６と、インタフェース部１１８とを有するとともに、さらに、受付部３０２と、負荷平滑化部３１４と、を備える。
なお、本実施形態のノード装置３００は、図１の上記実施形態のノード装置１００の構成に、受付部３０２を設けた構成とすることもできる。
【００７３】
本発明の実施の形態に係る分散システム１において、分散システム１内にて、追加または削除対象となる対象ノードと、対象ノードの追加または削除の指示とを受け付ける受付部３０２をさらに備える。受付部３０２が指示を受け付けたとき、対象ノードの近隣のノードの負荷分散部（負荷平滑化部３１４）が、負荷分散処理を行う機能を一時的に無効化する。
【００７４】
受付部３０２は、図２のデータサーバ１０の入出力Ｉ／Ｆ４に接続される入力装置などからユーザの操作指示を受け付けてもよいし、あるいは、データ操作クライアント５０から指示を受け付けてもよい。あるいは、受付部３０２の代わりに、隣接ノードを監視する監視部（不図示）を備え、隣接ノードの参加または離脱を検知する構成としてもよい。
【００７５】
負荷平滑化部３１４において、好適には、負荷分散処理を行う機能は、属性値毎にＯＦＦ（無効化）あるいはＯＮ（有効化）させることができることが望ましい。その理由は、新たに参加したノードあるいは、離脱するノードが、Successorノードとの間でデータ移動を行う際には、全ての属性値について同時に移動させることは、システムのレスポンスタイムなどへの影響が大きく、一部の属性毎に、データを移動させることが、望まれるからである。データ移動が完了した属性から、負荷分散処理の機能をＯＮに（有効化）することが望ましい。
【００７６】
このように構成された本発明の実施の形態に係る分散システム１の動作について、以下説明する。図９は、本実施形態の分散システム１のノード変更指示を受け付けたときの動作の一例を示すフローチャートである。図９に示すように、受付部３０２が、新たなノードを追加する指示、または既存のノードを除去する指示と、追加または除去する対象となるノードを受け付けたとき（ステップＳ３０１のＹＥＳ）、ステップＳ３０３に進む。対象ノードの近隣のノードにおいて、負荷平滑化部３１４が、一時的に負荷分散処理を行う機能を無効化する（ステップＳ３０３）。
【００７７】
すなわち、図１０に示すように、たとえば、新たにノードｍが追加された場合、またはノードｍを除去する場合、ノードｍの近隣のノードｐ（Predecessorノード）との間の負荷分散処理機能（ｆ１）と、近隣のノードｓ（Successorノード）とそのノードｓの隣接ノードｓ′との間の負荷分散処理機能（ｆ２）とを一時的に無効化する。
【００７８】
ノードｍが追加される場合、ノードｍの負荷は初め０であり、ノードｓとの間で負荷の差が一時的に大きくなる。ノードｍでは、負荷分散処理機能（ｆ０）は有効のままとし、密度比較部２１２が上記実施形態の図６の負荷差分処理Ｓ２００を行い、負荷移動量を求める。そして、負荷平滑化部３１４が、上記実施形態の図７の負荷分散処理Ｓ２１０を行い、データ移動部１１６がインタフェース部１１８を介して、ノードｓからデータを受信し、データ格納部１０２に格納するとともに、値域端点１０６を更新する。
【００７９】
このとき、ノードｐの負荷分散処理機能（ｆ１）と、ノードｓの隣接ノードｓ′の負荷分散処理機能（ｆ２）は、ともに一時的に無効化されている。そして、ノードｍとノードｓの間で負荷分散処理が完了し、負荷が均一になった後に、ノードｐとノードｓ′における負荷分散処理機能を有効化する。なお、本実施形態において、ノードｍの追加または削除時に、ノードｐとその隣接ノードｐ′との間の負荷分散処理機能（ｆ３）、ならびに、ノードｓ′とその隣接ノードｓ"との間の負荷分散処理機能（ｆ４）は、ともに有効のままとしてよい。
【００８０】
図１１は、負荷平滑化部３１４が、属性値毎に負荷分散処理機能の有効化または無効化を制御する場合の手順の一例を示すフローチャートである。
データ移動部１１６が、負荷平滑化部３１４からの指示に基づいて、インタフェース部１１８を介して近隣のノードとデータを属性値毎に移動する（ステップＳ３１１）。そして、属性値のデータ移動が完了する度に（ステップＳ３１３のＹＥＳ）、移動が完了した属性値の負荷分散処理機能を有効化する（ステップＳ３１５）。具体的には、ノードｐとノードｓまたはノードｓ′に、属性値の負荷分散処理機能を有効化する指示を通知する。
【００８１】
そして、全ての属性値についてデータの移動が完了するまで（ステップＳ３１７のＮＯ）、属性値毎のデータ移動を繰り返す（ステップＳ３１１〜ステップＳ３１５）。全てのデータの移動が完了したとき（ステップＳ３１７のＹＥＳ）、本処理を終了する。
【００８２】
以上説明したように、本発明の実施の形態の分散システム１によれば、上記実施形態と同様な効果を奏するとともに、さらに、分散システム１のノード構成に変化があった時、ノード間でのデータ移動量を適切に制御することができる。
【００８３】
たとえば、分散システム１では、ノード間で負荷分散処理とデータ移動を行う場合、ノードへの問い合わせ等に対する応答時間に影響を与えないように、移動すべきデータを一度に移動するのではなく、少量ずつ徐々に移動する。分散システム１にノードを追加または削除した場合、その対象となるノードと関連するノードとの間で、負荷密度が急激に増加または減少する。これは、ノードが追加または削除されたとき、ＩＤ幅は、時間的に突発的に変化するのに対し、データ量については上述したように徐々に連続的に変化するためである。そのため、負荷密度が急激に変化したノードの周辺のノードに、その変化の影響が及ぶこととなり、本来負荷分散が必要ないはずのノード間でもデータの移動が波及してしまう。
【００８４】
本発明では、このようなノードを追加または削除した場合に、急激な密度変化を生じたノードにおいて負荷分散処理が一段落するまでの間、すなわち、隣接ノードとの間でのデータ移動が完了するまでの間、周辺の他のノードにおける負荷分散処理機能を無効にすることで、分散システム１全体にデータ移動を波及させる影響を低減することができる。
【００８５】
このように、本発明では、ノードの追加または削除があった場合にも、移動中のデータにアクセスすることに伴って起こる可能性のある、データ検索やデータ登録といったデータベースシステム、アプリケーションシステムの応答時間の劣化も回避できる。
【００８６】
（第４の実施の形態）
本実施形態の分散システム１は、上記実施の形態とは、ノードがシステムに参加するとき、またはシステムから離脱するときに、自らが隣接ノードを特定し、隣接ノードに参加または離脱を表明し、隣接ノードの負荷分散機能を制御させる点で相違する。
【００８７】
本実施形態のノード装置４００は、図１２に示すように、図５のノード装置３００と同様な、データ格納部１０２と、ＩＤ格納部１０８と、密度比較部２１２と、負荷平滑化部３１４と、データ移動部１１６と、インタフェース部１１８と、を備えるとともに、さらに、ノード参加離脱特定部４０２と、ノード参加離脱要求部４０４と、ノード参加離脱要求受付部４０６と、を備える。
【００８８】
なお、本実施形態のノード装置４００は、図１の上記実施形態のノード装置１００、または図３のノード装置２００の構成に、ノード参加離脱特定部４０２と、ノード参加離脱要求部４０４と、ノード参加離脱要求受付部４０６と、を含めた構成でもよい。
【００８９】
各ノード装置４００は、自らが分散システム１に新たに参加、または離脱する対象ノードとなるとき、リング上で対象ノードの前後に隣接するSuccessorノードとPredecessorノードを特定するノード参加離脱特定部４０２と、特定したSuccessorノードとPredecessorノードに参加または離脱要求を送信するノード参加離脱要求部４０４と、をさらに備える。
【００９０】
さらに、各ノード装置４００は、対象ノードから参加または離脱要求を受信するノード参加離脱要求受付部４０６を備える。ノード装置４００のノード参加離脱要求部４０４が対象ノードから参加または離脱要求を受け付けたとき、ノード装置４００の負荷分散部（負荷平滑化部３１４）が、負荷分散処理を一時的に停止する、すなわち、負荷分散処理機能を一時的に無効にする。
【００９１】
ノード参加離脱特定部４０２は、自らが分散システム１に新たに参加、または離脱する対象ノードとなるとき、リング上で対象ノードの前後に隣接するSuccessorノードとPredecessorノードを特定する。
ノード参加離脱要求部４０４は、分散システム１に新たに参加するノード、あるいはシステムから離脱するノードが、ＩＤが隣接するノードに対して、その一連の処理の開始あるいは一連の処理の終了を通知する機能を持つ。
【００９２】
ノード参加離脱要求受付部４０６は、自ノードと隣接ノードとの間に新たなノードが参加する際、あるいは隣接ノードが離脱する際に、そのノードからの参加または離脱要求、あるいは参加または離脱終了の通知を受付け、システムとして問題がないような設定を施す機能を持つ。その際、本実施の形態では、負荷分散機能をＯＮにする、あるいはＯＦＦにすることも行う。
【００９３】
このように構成された本実施形態の分散システム１の動作について、以下説明する。
図１３は、本発明の実施の形態に係る分散システム１の動作の一例を示すフローチャートである。
以下、図１２および図１３を用いて説明する。
【００９４】
本ノード参加離脱処理Ｓ４００は、自ノードが分散システム１に参加または離脱する場合に開始する。
まず、ノード参加離脱特定部４０２が、SuccessorおよびPredecessorを特定する（ステップＳ４０１）。そして、ノード参加離脱特定部４０２が、特定したSuccessorノードおよびPredecessorノードに対し、インタフェース部１１８を介して参加または離脱要求を送信する（ステップＳ４０３）。
【００９５】
そして、送信した要求が「参加」である場合には（ステップＳ４０５の「参加」）、負荷平滑化部３１４が負荷分散処理を開始する（ステップＳ４０７）。このステップＳ４０７の処理は、図７で説明した負荷分散処理Ｓ２１０である。そして、Successorと自ノードとの負荷の密度が均一になるまで（ステップＳ４０９のＮＯ）、負荷分散処理Ｓ２１０を続け、図１３のステップＳ４１１で、一定時間待っている間、データ移動部１１６によりSuccessorノードに自ノードのデータを移動させる。
【００９６】
均一になったと判断された場合（ステップＳ４０９のＹＥＳ）、ノード参加離脱要求部４０４が、SuccessorノードおよびPredecessorノードに参加終了の通知をする（ステップＳ４３１）。
【００９７】
また、上記要求が「離脱」である場合には（ステップＳ４０５の「離脱」）、ノード参加離脱特定部４０２が、負荷平滑化部３１４の負荷分散処理機能を無効化（ＯＦＦ）する（ステップＳ４２１）。そして、データ移動部１１６が、自ノードからSuccessorノードへのデータ移動をインタフェース部１１８を介して行う（ステップＳ４２３）。このとき、上述したように、データは隣接ノードに徐々に送信するので、すべてのデータ移動が終了するまで（ステップＳ４２５のＮＯ）、ステップＳ４２３に戻り、データ移動を繰り返す。
【００９８】
すべてのデータ移動が終了したとき（ステップＳ４２５のＹＥＳ）、データ移動部１１６が、SuccessorノードおよびPredecessorノード離脱終了の通知をする（ステップＳ４３１）。
【００９９】
図１４は、参加表明したノードｍと、ノードｍのSuccessorノードにあたるノードsにおいて、それぞれ有効になっている構成要素のみを示す機能ブロック図である。図１５は、本実施形態の分散システム１において、参加または離脱を表明したノードｍからの参加または離脱要求をノードｓが受け付けたときの処理Ｓ４４０の手順の一例を示すフローチャートである。図１６は、本実施形態の分散システム１において、参加または離脱を表明したノードｍからの参加または離脱終了通知をノードｓが受け付けたときの処理Ｓ４５０の手順の一例を示すフローチャートである。
【０１００】
図１５に示すように、ノード参加離脱要求受付処理Ｓ４４０において、ノードｓのノード参加離脱要求受付部４０６が、ノード参加または離脱要求をノードｍからインタフェース部１１８を介して受け付けると（ステップＳ４４１のＹＥＳ）、本処理が開始する。そして、ノードｓのノード参加離脱要求受付部４０６が、負荷平滑化部３１４における負荷分散処理機能を無効化（ＯＦＦ）する（ステップＳ４４３）。そして、ノードｓのノード参加離脱要求受付部４０６が、参加または離脱処理を行い（ステップＳ４４５）、本処理を終了する。
【０１０１】
ステップＳ４４５の処理は、分散システム１においてノードが参加または離脱する際に必要な各種処理であり、たとえば、論理ＩＤの追加または削除に伴うリングの再構築処理等である。
【０１０２】
さらに、図１６に示すように、ノード参加離脱終了受付処理Ｓ４５０において、ノードｓのノード参加離脱要求受付部４０６が、ノードｍから参加または離脱処理の終了通知を受け付けると（ステップＳ４５１のＹＥＳ）、本処理が開始する。そして、ノードｓのノード参加離脱要求受付部４０６が、負荷平滑化部３１４における負荷分散処理機能を有効化（ＯＮ）し、負荷分散処理を開始する（ステップＳ４５３）。この負荷分散処理は、図７の負荷分散処理Ｓ２１０である。そして、ノードｓのノード参加離脱要求受付部４０６が、参加または離脱処理を行い（ステップＳ４５５）、本処理を終了する。
【０１０３】
ステップＳ４５５の処理は、分散システム１において、ノードが参加または離脱した後に必要な各種処理であり、たとえば、再構築したリングが正しいか確認する処理等である。
【０１０４】
このようにして、本実施形態の分散システム１では、分散システム１に参加または離脱するノードｍは、隣接ノードを特定するとともに、隣接ノードに参加または離脱を通知し、隣接ノードの分散処理機能を一時的に無効化し、ノードｍにおけるノードｓとの負荷分散処理が終了したら、隣接ノードに通知し、負荷分散処理機能を有効に戻す。
【０１０５】
以上説明したように、本発明の実施の形態の分散システム１によれば、上記実施形態と同様な効果を奏するとともに、さらに、各ノードは、分散システム１に参加または離脱を表明して、自律的に参加または離脱処理を行うことができ、負荷分散処理機能を適切に制御することで、分散システム１への影響を最小限に抑えることができる。
【０１０６】
以上、図面を参照して本発明の実施形態について述べたが、これらは本発明の例示であり、上記以外の様々な構成を採用することもできる。
【実施例】
【０１０７】
（実施例１）
以下、図１７および図１８を用いて、本発明の分散システム１の実施例１として、図５の上記実施形態の構成において、ノードを追加した場合の動作について説明する。
図１７および図１８は、ノードのＩＤが２０、３０、５２、６０、６６であるノードを表している。図１７は、ノードが追加される前の状態を示す図であり、図１８は、ノードが追加された後の状態を示す図である。図１７の状態において、それぞれのＩＤ幅は、ＩＤが３０であるノードから順に、１０、２２、８、６となる。また、各ノードはある値域のデータを管理しており、データ量がノード３０であるノードから順に、５、１１、４、３であったとする。【０１０８】
図１７では、既に、隣接ノード間でＩＤ幅あたりのデータ量を均一化するように、負荷分散処理が施された後であり、それぞれのデータ密度は、５／１０＝０．５、１１／２２＝０．５、４／８＝０．５、３／６＝０．５（不図示）となっている。【０１０９】
図１７の状態から、新たにＩＤが４２であるノードが追加され、図１８のような状態になったとする。
ノードが追加されると、図１８に示すように、ＩＤ幅は、ＩＤが３０であるノードから順に、１０，１２，１０，８，６となる。データ量については、参加した当初はデータの移動が完了していないため、５，０，１１，４，３（不図示）となる。そのためデータ密度（ＩＤ幅あたりのデータ量）は、５／１０＝０．５、０／１２＝０、１１／１０＝１．１、４／８＝０．５、３／６＝０．５（不図示）となる。【０１１０】
ここで、ノードを受け入れたＩＤが５２であるノードは、データ密度が急激に増加するため、その隣接ノードであるＩＤが６０であるノードとの間で、データ密度を均一化するようにデータ移動量が密度比較部２１２により算出される。
（４＋１１）×１０／（８＋１０）＝２．７      ・・・式（２）
式（２）より、２．７のデータ量をＩＤが６０であるノードに移動させる。これにより、ＩＤが５２であるノードと、６０であるノードの密度は、それぞれ８．３／１０＝０．８３、６．７／８＝０．８３となった。【０１１１】
一方、新たに加わったＩＤが４２であるノードと、そのPredecessorであるＩＤが３０であるノードとの間でも、同様の処理がなされる。
（０＋５）×１０／（１２＋１０）−５＝２．７      ・・・式（３）
式（３）より、２．７のデータ量をＩＤが３０であるノードから、ＩＤが４２であるノードにデータ移動させる。これにより、それぞれのノードのデータ密度は、２．３／１０＝０．２３、２．７／１２＝０．２３となった。【０１１２】
続いて、ノードＩＤが４２であるノードと、ノードＩＤが５２であるノードの間、ノードＩＤが６０であるノードと６６であるノードの間などでも同様の処理が行われ、ＩＤ密度が均一化するように、動作する。
その結果、各ノードのデータ密度は、ＩＤが３０のノードから順に、０．３８、０．３８、０．５８、０．５８となった。その後、さらに負荷分散処理を繰り返すことで、各ノードの負荷が均一化になる。【０１１３】
（実施例２）
次に、図１７および図１９を用いて、本発明の分散システム１の実施例２として、図１２の上記実施形態の構成において、ノードを追加した場合の動作について説明する。図１９は、ノードが追加された後の状態を示す図である。
上記実施例１と同様に、ＩＤが４２であるノードが分散システム１に参加したとする。ＩＤが４２であるノードにおいて、ノード参加離脱特定部４０２が、ＩＤが５２であるSuccessorノードと、ＩＤが３０であるPredecessorノードを特定し、SuccessorノードとPredecessorノードに対して、参加要求を送信することで、SuccessorノードとPredecessorノードの負荷分散処理機能をＯＦＦ（無効化）させる。【０１１４】
この時に、各ノードで動作している機能は、図１４に示すとおりとなる。新たに参加するノードｍでは、負荷平滑化部３１４が動作しており、このSuccessorノードであるノードｓでは、負荷平滑化部３１４が動作していない。
そのため、図１９に示すように、ＩＤが４２であるノードｍは、ＩＤが５２であるノードｓとのデータ密度が等しくなるまで、データを受け取る。具体的には、式（４）に相当するデータ量が移動した。
（１１＋０）×１２／（１０＋１２）＝６      ・・・式（４）【０１１５】
この移動が完了すると、ＩＤが４２であるノード、およびＩＤが５２であるノードの密度は、それぞれ０．５となる。この間、SuccessorノードおよびPredecessorノードは負荷分散処理を行っていない。
新規に参加したＩＤが４２であるノードが、ＩＤが５２であるノードとの密度に差がないと判定すると、SuccessorであるＩＤが５２であるノード、およびPredecessorであるＩＤが３０であるノードに対して、参加終了の通知を行い、SuccessorノードとPredecessorノードの負荷分散処理機能をＯＮ（有効化）させる。【０１１６】
このように、参加または離脱するノードの隣接ノードにおいて、一時的に負荷分散処理機能をＯＦＦ（無効化）にすることで、参加あるいは離脱するノードとそのSuccessorのノードとの間だけに、データ移動を限定することができる。この間、他のノードとの不要なデータ移動は発生せず、目的の状態である密度が均一化される状態に到達することができた。図１８の場合に比較しても、早期に負荷密度が均一化されたことがわかる。【０１１７】
これは、ＩＤ幅の変化が、ノード参加離脱という離散的なイベントに伴う、時間的に突発的な変化であるのに対して、データ量の変化が時間的に連続的な変化となるからである。これは、データを急激に移動すると、サービス品質を低下させる可能性があるため、サービス品質に対する影響を少なくするために、データ移動を徐々に行うからである。そして、密度は、データ量／ＩＤ幅で算出するため、ノードの参加または離脱時に、急激に変化してしまう。この間、負荷分散処理機能が動作していると、本来は波及する必要のないノードにも、その急激な変化が伝わってしまうため、本来は不要なデータ移動が発生してしまい、最終的に密度が均一の状態に到達するまで処理が必要以上に繰り返されることになる。【０１１８】
換言すると、負荷分散機能は、２つの外部変化に対して適応的に動作しているが、それらをノードが判別できないことにこのような動作は起因している。２つの変化とは、データの分布の変化と、ノード数の変化である。データの分布の変化は、アプリケーションの動作次第で、常に起こり得るものであり、負荷分散を行うには、この変化に適応的に値域を変更することが望まれる。しかしながら、ノード数を変化させると、データ量ではなくＩＤ幅あたりのデータ密度が急激に増加する。そして、ノードは、このノード数の変化に伴う変化と、データ分布の変化との判別がつかないため、問題が生じる。
したがって、本発明では、ノード数の変化をノードが判別できる構成を備え、負荷分散処理機能の制御を行う構成を有することで、この問題を解決している。なお、ノード数Ｎのシステムでデータ量を各ノードにつき１／Ｎとして均一化して負荷分散を行う場合には、ノード数Ｎが変化すると全てのノードに対して影響が及ぶので、この対処法は有効ではない。本発明のように、ＩＤ幅あたりのデータ量で負荷分散を行う場合に有効である。【０１１９】
最後に、データ量ではなく、ＩＤ幅あたりのデータ密度を均一化することによって、何故負荷分散が図れるかについて補足する。ここで述べるノードは、一つのサーバの上で動作する複数のノードであってもよく、その複数のノードは、ランダムにＩＤ幅の広いノードや狭いノードからなっている時、サーバあたりのデータ量は、ほぼ均一化することができる。これは、一般に仮想ノード、あるいは仮想サーバと呼ばれる。【０１２０】
以上、実施形態および実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１２１】
上記の実施形態の一部または全部は、以下の付記のようにも記載されうるが、以下には限られない。
（付記１）
データ群を分散して管理する複数のノードを備える分散システムであって、
複数の前記ノードは、前記分散システムの論理識別子空間を示すリング上で一意に割り当てられた論理識別子をそれぞれ有し、
複数の前記ノードは、前記データ群のデータを部分的に記憶する記憶装置をそれぞれ備え、
前記ノードは、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に格納するデータ格納手段と、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノードの近隣のノードから前記負荷密度を取得し、前記自ノードの前記負荷密度と前記近隣のノードの前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出する密度比較手段と、
前記密度比較手段が算出した前記負荷移動量に基づいて、前記近隣のノードと移動するデータを決定し、負荷分散処理を行う負荷分散手段と、
前記負荷分散処理で決定した移動する前記データを、前記近隣のノードとの間で移動するとともに、前記値域端点を更新するデータ移動手段と、を備える分散システム。
（付記２）
付記１に記載の分散システムにおいて、
前記ノードの前記負荷分散手段は、前記負荷分散処理を行う機能の有効化または無効化を制御する分散システム。
（付記３）
付記２に記載の分散システムにおいて、
前記分散システム内にて、追加または削除対象となる対象ノードと、前記対象ノードの追加または削除の指示とを受け付ける受付手段をさらに備え、
前記受付手段が前記指示を受け付けたとき、前記対象ノードの近隣のノードの前記負荷分散手段は、前記負荷分散処理を行う機能を一時的に無効化する分散システム。
（付記４）
付記２または付記３に記載の分散システムにおいて、
前記ノードの前記負荷分散手段は、前記負荷分散処理を行う機能の有効化または無効化を前記属性値毎に制御する分散システム。
（付記５）
付記４に記載の分散システムにおいて、
前記データ移動手段は、前記負荷分散処理で決定した移動する前記データを前記属性値毎に移動し、
前記負荷分散手段は、移動が完了した前記属性値の前記負荷分散処理を行う機能を有効化する分散システム。
（付記６）
付記１乃至５いずれかに記載の分散システムにおいて、
前記ノードの前記負荷は、前記ノードの前記記憶装置に記憶される前記データのデータ量または前記ノードの前記記憶装置に記憶された前記データへのアクセス頻度である分散システム。
（付記７）
付記１乃至６いずれかに記載の分散システムにおいて、
前記ノードの前記密度比較手段は、前記負荷移動量を下記の式（１）により算出し、
算出された前記負荷移動量が正の値を取るときは、自ノードから前記自ノードの近隣のノードに移動すべき負荷移動量を示し、算出された前記負荷移動量が負の値を取るときは、前記自ノードへ前記近隣のノードから移動すべき負荷移動量を示す分散システム。
（Ｖｓ＋Ｖｍ）Ｒｍ／（Ｒｓ＋Ｒｍ）−Ｖｍ    ・・・式（１）
ここで、ＶｓおよびＲｓは前記自ノードの負荷および前記ＩＤ領域の幅、ＶｍおよびＲｍは前記自ノードの近隣のノードの負荷および前記ＩＤ領域の幅である。
（付記８）
付記２乃至付記７いずれかに記載の分散システムにおいて、
前記ノードは、
自らが前記分散システムに新たに参加する参加対象ノードとなるとき、前記リング上で前記参加対象ノードの前後に隣接するSuccessorノードとPredecessorノードを特定する参加特定手段と、
特定した前記Successorノードと前記Predecessorノードに参加要求を送信する参加要求手段と、をさらに備える分散システム。
（付記９）
付記８に記載の分散システムにおいて、
前記ノードは、
前記参加対象ノードから前記参加要求を受信する参加要求受付手段を備え、
前記ノードの前記参加要求受付手段が前記参加対象ノードから前記参加要求を受け付けたとき、前記ノードの前記負荷分散手段が、前記負荷分散処理を一時的に停止する分散システム。
（付記１０）
付記２乃至付記９いずれかに記載の分散システムにおいて、
前記ノードは、
自らが前記分散システムから離脱する離脱対象ノードとなるとき、前記リング上で前記離脱参加対象ノードの前後に隣接するSuccessorノードとPredecessorノードを特定する離脱特定手段と、
特定した前記Successorノードと前記Predecessorノードに離脱要求を送信する離脱要求手段と、を備える分散システム。
（付記１１）
付記１０に記載の分散システムにおいて、
前記ノードは、
前記離脱対象ノードから前記離脱要求を受信する離脱要求受付手段を備え、
前記ノードの前記離脱要求受付手段が前記離脱対象ノードから前記離脱要求を受け付けたとき、前記ノードの前記負荷分散手段が、前記負荷分散処理を一時的に停止する分散システム。【０１２２】
（付記１２）
複数のノード装置がデータ群を分散して管理する分散システムを構成し、前記分散システムに対し参加または離脱可能なノード装置であって、
前記分散システムの論理識別子空間を示すリング上で、他の前記ノード装置と識別可能に一意に割り当てられた論理識別子を有し、
前記データ群のデータを部分的に記憶する記憶装置と、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に格納するデータ格納手段と、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノード装置の近隣のノード装置から前記負荷密度を取得し、前記自ノード装置の前記負荷密度と前記近隣のノード装置の前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出する密度比較手段と、
前記密度比較手段が算出した前記負荷移動量に基づいて、前記近隣のノード装置と移動するデータを決定し、負荷分散処理を行う負荷分散手段と、
前記負荷分散処理で決定した移動する前記データを、前記近隣のノード装置との間で移動するとともに、前記値域端点を更新するデータ移動手段と、を備えるノード装置。
（付記１３）
付記１２に記載のノード装置において、
前記負荷分散手段は、前記負荷分散処理を行う機能の有効化または無効化を制御するノード装置。
（付記１４）
付記１３に記載の分散システムにおいて、
前記分散システム内にて、追加または削除対象となる対象ノードと、前記対象ノードの追加または削除の指示とを受け付ける受付手段をさらに備え、
前記受付手段が前記指示を受け付けたとき、前記対象ノードの近隣のノードの前記負荷分散手段は、前記負荷分散処理を行う機能を一時的に無効化するノード装置。
（付記１５）
付記１４に記載のノード装置において、
前記負荷分散手段は、前記負荷分散処理を行う機能の有効化または無効化を前記属性値毎に制御するノード装置。
（付記１６）
付記１５に記載のノード装置において、
前記データ移動手段は、前記負荷分散処理で決定した移動する前記データを前記属性値毎に移動し、
前記負荷分散手段は、移動が完了した前記属性値の前記負荷分散処理を行う機能を有効化するノード装置。
（付記１７）
付記１２乃至付記１６いずれかに記載のノード装置において、
前記負荷は、前記記憶装置に記憶される前記データのデータ量または前記記憶装置に記憶された前記データへのアクセス頻度であるノード装置。
（付記１８）
付記１２乃至付記１７いずれかに記載のノード装置において、
前記密度比較手段は、前記負荷移動量を下記の式（１）により算出し、
算出された前記負荷移動量が正の値を取るときは、自ノードから前記自ノードの近隣のノードに移動すべき負荷移動量を示し、算出された前記負荷移動量が負の値を取るときは、前記自ノードへ前記近隣のノードから移動すべき負荷移動量を示すノード装置。
（Ｖｓ＋Ｖｍ）Ｒｍ／（Ｒｓ＋Ｒｍ）−Ｖｍ    ・・・式（１）
ここで、ＶｓおよびＲｓは前記自ノードの負荷および前記ＩＤ領域の幅、ＶｍおよびＲｍは前記自ノードの近隣のノードの負荷および前記ＩＤ領域の幅である。
（付記１９）
付記１３乃至付記１８いずれかに記載のノード装置において、
自らが前記分散システムに新たに参加する参加対象ノードとなるとき、前記リング上で前記参加対象ノードの前後に隣接するSuccessorノードとPredecessorノードを特定する参加特定手段と、
特定した前記Successorノードと前記Predecessorノードに参加要求を送信する参加要求手段と、をさらに備えるノード装置。
（付記２０）
付記１９に記載のノード装置において、
前記参加対象ノードから前記参加要求を受信する参加要求受付手段を備え、
前記参加要求受付手段が前記参加対象ノードから前記参加要求を受け付けたとき、前記負荷分散手段が、前記負荷分散処理を一時的に停止するノード装置。
（付記２１）
付記１３乃至付記２０いずれかに記載のノード装置において、
自らが前記リングから離脱する離脱対象ノードとなるとき、前記リング上で前記離脱参加対象ノードの前後に隣接するSuccessorノードとPredecessorノードを特定する離脱特定手段と、
特定した前記Successorノードと前記Predecessorノードに離脱要求を送信する離脱要求手段と、を備えるノード装置。
（付記２２）
付記２１に記載のノード装置において、
前記離脱対象ノードから前記離脱要求を受信する離脱要求受付手段を備え、
前記離脱要求受付手段が前記離脱対象ノードから前記離脱要求を受け付けたとき、前記負荷分散手段が、前記負荷分散処理を一時的に停止するノード装置。【０１２３】
（付記２３）
複数のノード装置がデータ群を分散して管理する分散システムを実現する負荷分散方法であって、
複数の前記ノード装置は、
前記分散システムを構成し、前記分散システムに対し参加または離脱可能であり、
前記データ群のデータを部分的に記憶する記憶装置をそれぞれ備え、
前記ノード装置が、
前記分散システムの論理識別子空間を示すリング上で、他の前記ノード装置と識別可能に論理識別子を一意に割り当て、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に記憶し、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノードの近隣のノードから前記負荷密度を取得し、前記自ノードの前記負荷密度と前記近隣のノードの前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出し、
算出した前記負荷移動量に基づいて、前記近隣のノードと移動するデータを決定し、負荷分散処理を行い、
前記負荷分散処理で決定した移動する前記データを、前記近隣のノードとの間で移動するとともに、前記値域端点を更新する負荷分散方法。
（付記２４）
付記２３に記載の負荷分散方法において、
前記ノードは、前記負荷分散処理を行う機能の有効化または無効化を制御する負荷分散方法。
（付記２５）
付記２４に記載の負荷分散方法において、
前記ノード装置が、
前記分散システム内にて、追加または削除対象となる対象ノードと、前記対象ノードの追加または削除の指示とを受け付け、
前記指示を受け付けたとき、前記対象ノード、および前記対象ノードの近隣のノードは、前記負荷分散処理を行う機能を一時的に無効化する負荷分散方法。
（付記２６）
付記２４または付記２５に記載の負荷分散方法において、
前記ノードは、前記負荷分散処理を行う機能の有効化または無効化を前記属性値毎に制御する負荷分散方法。
（付記２７）
付記２６に記載の負荷分散方法において、
前記負荷分散処理で決定した移動する前記データを前記属性値毎に移動し、
前記データの移動が完了した前記属性値の前記負荷分散処理を行う機能を有効化する負荷分散方法。
（付記２８）
付記２３乃至付記２７いずれかに記載の負荷分散方法において、
前記ノードの前記負荷は、前記ノードの前記記憶装置に記憶される前記データのデータ量または前記ノードの前記記憶装置に記憶された前記データへのアクセス頻度である負荷分散方法。
（付記２９）
付記２３乃至付記２８いずれかに記載の負荷分散方法において、
前記ノードが、前記負荷移動量を下記の式（１）により算出し、
算出された前記負荷移動量が正の値を取るときは、自ノードから前記自ノードの近隣のノードに移動すべき負荷移動量を示し、算出された前記負荷移動量が負の値を取るときは、前記自ノードへ前記近隣のノードから移動すべき負荷移動量を示す負荷分散方法。
（Ｖｓ＋Ｖｍ）Ｒｍ／（Ｒｓ＋Ｒｍ）−Ｖｍ    ・・・式（１）
ここで、ＶｓおよびＲｓは前記自ノードの負荷および前記ＩＤ領域の幅、ＶｍおよびＲｍは前記自ノードの近隣のノードの負荷および前記ＩＤ領域の幅である。
（付記３０）
付記２４乃至付記２９いずれかに記載の負荷分散方法において、
前記ノードが、
自らが前記分散システムに新たに参加する参加対象ノードとなるとき、前記リング上で前記参加対象ノードの前後に隣接するSuccessorノードとPredecessorノードを特定し、
特定した前記Successorノードと前記Predecessorノードに参加要求を送信する負荷分散方法。
（付記３１）
付記３０に記載の負荷分散方法において、
前記ノードが、
前記参加対象ノードから前記参加要求を受信し、
前記参加対象ノードから前記参加要求を受け付けたとき、前記負荷分散処理を一時的に停止する負荷分散方法。
（付記３２）
付記２４乃至付記３１いずれかに記載の負荷分散方法において、
前記ノードが、
自らが前記分散システムから離脱する離脱対象ノードとなるとき、前記リング上で前記離脱参加対象ノードの前後に隣接するSuccessorノードとPredecessorノードを特定し、
特定した前記Successorノードと前記Predecessorノードに離脱要求を送信する負荷分散方法。
（付記３３）
付記３２に記載の負荷分散方法において、
前記ノードが、
前記離脱対象ノードから前記離脱要求を受信し、
前記離脱対象ノードから前記離脱要求を受け付けたとき、前記負荷分散処理を一時的に停止する負荷分散方法。【０１２４】
（付記３４）
複数のノード装置がデータ群を分散して管理する分散システムを構成し、前記分散システムに対し参加または離脱可能なノード装置を実現するコンピュータが実行するプログラムであって、
前記コンピュータは、前記分散システムの論理識別子空間を示すリング上で、他の前記ノード装置と識別可能に一意に割り当てられた論理識別子を有するとともに、前記データ群のデータを部分的に記憶する記憶装置を備え、
前記コンピュータに、
前記リング上の前記論理識別子で区切られるＩＤ領域に前記データ群に含まれるデータの属性値の範囲を示す値域を対応付け、前記論理識別子の前記ＩＤ領域に対応する前記値域のデータを前記記憶装置に格納するとともに、前記記憶装置に格納されるデータの前記値域を示す値域端点を前記記憶装置に記憶する手順、
前記記憶装置に格納された前記データの負荷を、前記ＩＤ領域の幅あたりの負荷密度に換算して求めるとともに、前記リング上で自ノードの近隣のノードから前記負荷密度を取得し、前記自ノードの前記負荷密度と前記近隣のノードの前記負荷密度とを比較し、前記負荷密度を均一にするための負荷移動量を算出する手順、
算出した前記負荷移動量に基づいて、前記近隣のノードと移動するデータを決定し、負荷分散処理を行う手順、
前記負荷分散処理を行うとき、前記記憶装置に格納されている前記データを前記近隣のノードとの間で移動するとともに、前記値域端点を更新する手順をさらに実行させるためのプログラム。
（付記３５）
付記３４に記載のプログラムにおいて、
前記負荷分散処理を行う機能の有効化または無効化を制御する手順をコンピュータにさらに実行させるためのプログラム。
（付記３６）
付記３５に記載のプログラムにおいて、
前記分散システム内にて、追加または削除対象となる対象ノードと、前記対象ノードの追加または削除の指示とを受け付ける手順、
前記指示を受け付けたとき、前記対象ノード、および前記対象ノードの近隣のノードに対し、前記負荷分散処理を行う機能を一時的に無効化する指示を行う手順をコンピュータにさらに実行させるためのプログラム。
（付記３７）
付記３５または付記３６に記載のプログラムにおいて、
前記負荷分散処理を行う機能の有効化または無効化を前記属性値毎に制御する手順をコンピュータにさらに実行させるためのプログラム。
（付記３８）
付記３７に記載のプログラムにおいて、
前記負荷分散処理で決定した移動する前記データを前記属性値毎に移動する手順、
移動が完了した前記属性値の前記負荷分散処理を行う機能を有効化する手順をコンピュータにさらに実行させるためのプログラム。
（付記３９）
付記３４乃至付記３８いずれかに記載のプログラムにおいて、
前記ノードの前記負荷は、前記ノードの前記記憶装置に記憶される前記データのデータ量または前記ノードの前記記憶装置に記憶された前記データへのアクセス頻度であるプログラム。
（付記４０）
付記３４乃至付記３９いずれかに記載のプログラムにおいて、
前記負荷移動量を下記の式（１）により算出する手順、
算出された前記負荷移動量が正の値を取るときは、自ノードから前記自ノードの近隣のノードに移動すべき負荷移動量を示し、算出された前記負荷移動量が負の値を取るときは、前記自ノードへ前記近隣のノードから移動すべき負荷移動量を示す手順をコンピュータにさらに実行させるためのプログラム。
（Ｖｓ＋Ｖｍ）Ｒｍ／（Ｒｓ＋Ｒｍ）−Ｖｍ    ・・・式（１）
ここで、ＶｓおよびＲｓは前記自ノードの負荷および前記ＩＤ領域の幅、ＶｍおよびＲｍは前記自ノードの近隣のノードの負荷および前記ＩＤ領域の幅である。
（付記４１）
付記３５乃至付記４０いずれかに記載のプログラムにおいて、
自らが前記分散システムに新たに参加する参加対象ノードとなるとき、前記リング上で前記参加対象ノードの前後に隣接するSuccessorノードとPredecessorノードを特定する手順、
特定した前記Successorノードと前記Predecessorノードに参加要求を送信する手順をコンピュータにさらに実行させるためのプログラム。
（付記４２）
付記４１に記載のプログラムにおいて、
前記参加対象ノードから前記参加要求を受信する手順、
前記参加対象ノードから前記参加要求を受け付けたとき、前記負荷分散処理を一時的に停止する手順をコンピュータにさらに実行させるためのプログラム。
（付記４３）
付記３５乃至付記４２いずれかに記載のプログラムにおいて、
自らが前記分散システムから離脱する離脱対象ノードとなるとき、前記リング上で前記離脱参加対象ノードの前後に隣接するSuccessorノードとPredecessorノードを特定する手順、
特定した前記Successorノードと前記Predecessorノードに離脱要求を送信する手順をコンピュータにさらに実行させるためのプログラム。
（付記４４）
付記４３に記載のプログラムにおいて、
前記離脱対象ノードから前記離脱要求を受信する手順、
前記離脱対象ノードから前記離脱要求を受け付けたとき、前記負荷分散処理を一時的に停止する手順をコンピュータにさらに実行させるためのプログラム。【０１２５】
この出願は、２０１２年６月１８日に出願された日本出願特願２０１２−１３６５７３号を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【図１】
2013190743.tif 000003
【図２】
2013190743.tif 000004
【図３】
2013190743.tif 000005
【図４】
2013190743.tif 000006
【図５】
2013190743.tif 000007
【図６】
2013190743.tif 000008
【図７】
2013190743.tif 000009
【図８】
2013190743.tif 000010
【図９】
2013190743.tif 000011
【図１０】
2013190743.tif 000012
【図１１】
2013190743.tif 000013
【図１２】
2013190743.tif 000014
【図１３】
2013190743.tif 000015
【図１４】
2013190743.tif 000016
【図１５】
2013190743.tif 000017
【図１６】
2013190743.tif 000018
【図１７】
2013190743.tif 000019
【図１８】
2013190743.tif 000020
【図１９】
2013190743.tif 000021
【国際調査報告】
2013190743.tif 000022
2013190743.tif 000023
2013190743.tif 000024
2013190743.tif 000025