(57)【特許請求の範囲】
【請求項１】
通信サービスを利用する複数のクライアントマシンからの情報がネットワークを介して振り分けられる複数のノードを有する分散システムにおいて用いられるリバランス装置であって、
前記複数のノードの負荷量に基づいて、当該複数のノード間の負荷量の偏りを抑制するリバランスが必要であるか否かを判定するリバランス処理手段と、
前記リバランス処理手段により、リバランスが必要であると判定された場合において、前記リバランス後の前記複数のノードの予測負荷状態に基づいて、前記リバランスをキャンセルするか否かを判定するキャンセル処理手段とを備え、
前記キャンセル処理手段は、
前記リバランス処理手段によりリバランスが必要であると判定された第１の時点において、当該第１の時点における前記複数のノードの負荷量の平均値からの差分をノード毎に算出し、前記第１の時点から、前記リバランス処理手段によるリバランス設計にかかる時間が経過した第２の時点において、ノード毎に、当該第２の時点におけるノードの負荷量から前記差分を引くことにより、前記予測負荷状態を算出する
ことを特徴とするリバランス装置。
【請求項２】
前記予測負荷状態が、ノード数の増減を要する負荷状態であるか、又は、前記予測負荷状態が、許容範囲外の負荷量を持つ所定数のノードが存在する負荷状態である場合に、前記キャンセル処理手段は、前記リバランスをキャンセルすると判定する
ことを特徴とする請求項１に記載のリバランス装置。
【請求項３】
通信サービスを利用する複数のクライアントマシンからの情報がネットワークを介して振り分けられる複数のノードを有する分散システムにおいて用いられるリバランス装置が実行するリバランス方法であって、
前記複数のノードの負荷量に基づいて、当該複数のノード間の負荷量の偏りを抑制するリバランスが必要であるか否かを判定するリバランス判定ステップと、
前記リバランス判定ステップにより、リバランスが必要であると判定された場合において、前記リバランス後の前記複数のノードの予測負荷状態に基づいて、前記リバランスをキャンセルするか否かを判定するキャンセル判定ステップとを備え、
前記キャンセル判定ステップにおいて、前記リバランス装置は、
前記リバランス判定ステップによりリバランスが必要であると判定された第１の時点において、当該第１の時点における前記複数のノードの負荷量の平均値からの差分をノード毎に算出し、前記第１の時点から、リバランス設計にかかる時間が経過した第２の時点において、ノード毎に、当該第２の時点におけるノードの負荷量から前記差分を引くことにより、前記予測負荷状態を算出する
ことを特徴とするリバランス方法。
【請求項４】
前記キャンセル判定ステップにおいて、前記リバランス装置は、前記予測負荷状態が、ノード数の増減を要する負荷状態であるか、又は、前記予測負荷状態が、許容範囲外の負荷量を持つ所定数のノードが存在する負荷状態である場合に、前記リバランス装置は、前記リバランスをキャンセルすると判定する
ことを特徴とする請求項３に記載のリバランス方法。
【請求項５】
コンピュータを、請求項１又は２に記載のリバランス装置における各手段として機能させるためのプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散システムにおいて、複数のノード間での負荷の偏りを是正する技術に関連するものである。
【背景技術】
【０００２】
近年、クラウドコンピューティングの隆盛に伴い、多量なデータの処理や保持を効率的に行うことが求められている。そこで、複数のサーバを協調動作させることにより効率的な処理を実現する分散処理技術が発展している。分散処理を行う際には、クラスタを構成して分散システムを構築する各サーバ（以降、ノードともいう）が担当するデータを決定する必要がある。この際、分散システム全体でのデータの処理能力を高めるためには、各ノードが担当するデータ数は平均化されていることが望ましい。
【０００３】
ところで、代表的なデータの管理手法には、各データのｋｅｙ（キー）をハッシュ関数にかけた値（以降、ｈａｓｈ（ｋｅｙ）：ハッシュキーともいう）を、ノード数Ｎで割った余り、即ちｈａｓｈ（ｋｅｙ）ｍｏｄ  Ｎを番号として持つノードが、データを管理する手法がある。但し、その際、ノードに事前に０からＮ−１まで番号を割り当てている。このような管理手法を用いた場合、ノードを追加又は離脱すると、Ｎの値が変化し、多くのデータでは担当するノードが変更になるため、担当ノードの再配置が必要になる。
【０００４】
そこで、ノードの追加・離脱に伴い担当するノードが変更になるデータ数を約1/Nに抑える方法として、コンシステント・ハッシュ[Consistent Hashing]（非特許文献１）を用いたデータ管理手法があり、Amazon Dynamo等で用いられている（非特許文献２）。コンシステント・ハッシュ法を用いたデータ管理手法では、例えば図１５に符号５で示す円形状のＩＤ空間において、ノードＡ，Ｂ，Ｃ，Ｄ，Ｅと、○及び●印で示す負荷が異なる負荷データとの双方にＩＤ(identification)を割り当てる。データのＩＤからＩＤ空間５を時計回りに辿り、最初に突き当たったノードが当該データの担当ノードになる。ノードＡ〜Ｅに対するＩＤの与え方の例としては、ＩＰ(Internet Protocol)アドレスをハッシュ関数にかけた値｛これを、ｈａｓｈ（ＩＰアドレス）ともいう｝が挙げられる。
【０００５】
クラスタ構成の分散システムでは、例えば各ノードの性能が等しい場合には、各ノードＡ〜Ｅが担当するデータ量は等しい、即ち、コンシステント・ハッシュ法のＩＤ空間５における、ノード間の距離（以降、ノードの担当領域ともいう）が等しいことが望ましい。
【０００６】
この点を解決するため、各ノードＡ〜Ｅに仮想的に複数のＩＤを持たせる手法が用いられている（非特許文献３）。各ノードＡ〜Ｅが複数の仮想ＩＤを持つことで、仮想ＩＤ毎の担当領域は異なっていても、大数の法則に従い、ノードＡ〜Ｅの担当領域は平均化される。このようなコンシステント・ハッシュ法や仮想ＩＤ等の従来技術により、ノード間で担当するデータ数を均一化し、負荷を分散させることが可能となる。
【０００７】
しかしながら、各ノードＡ〜Ｅの内の特定ノードにて、アクセス頻度の多いデータや、処理時間の長いデータ（高負荷データ)が偏って発生するため、各ノードＡ〜Ｅが担当するデータ数自体は均等であっても、ノード間で負荷の偏りが発生する。
【０００８】
このようなコンシステント・ハッシュ法の分散システムにおける負荷増大に対する対策としては、分散システムに、例えば図１５に示す新たなノードＦを増設して分散システムをスケールアウトさせ、高負荷となったノード（高負荷ノード）、例えば高負荷ノードＣが担当するデータ数を縮小させて負荷を低減する手法がとられている。
【０００９】
また、ノードのコンシステント・ハッシュ上での空間配置変更（これを、リバランスという）を行い適切に負荷が分散されていれば、増設を行うことなく現行のノード台数で対処可能なケースもある。非特許文献４には、スケールアウト／リバランスで対処すべき状況を識別し、更に、リバランスで対処すべき状況においては、コンシステント・ハッシュ空間（ＩＤ空間５）上の隣接ノード間（例えばＥであれば、２つの矢印で示す隣のＡ又はＤ）でリバランスを実行して、ノード間の負荷の偏りを是正する手法が提案されている。また、リバランスについて、非特許文献４以外にも、種々の技術が検討されている。
【先行技術文献】
【非特許文献】
【００１０】
【非特許文献１】David Karger(著), "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web"
【非特許文献２】Giuseppe DeCandia (著), "Dynamo: Amazon's Highly Available Key-value Store"
【非特許文献３】入江道生他，"コンシステント・ハッシュ法におけるデータの複製を意識した負荷分散手法"，信学技報，IEICE Technical Report，IN2010-77（2010-10）
【非特許文献４】鶴田泰他，「分散サーバシステムにおけるノード負荷分散最適化方式」，電子情報通信学会総合大会講演論文集，Mar．2014，B-7-84
【発明の概要】
【発明が解決しようとする課題】
【００１１】
既存のリバランス方法は時間経過を考慮していないため、リバランス設計のための計算に係る時間によっては、実負荷が適正値であるにも関わらず、リバランスが実行されてしまうという課題がある。
【００１２】
例えば、図１６（ａ）に示すＩＤ空間において、ノードＢの負荷（図１６のＢとＢ´の担当領域の負荷）と、ノードＥの負荷（図１６のＥとＥ´の担当領域の負荷）が許容範囲外にある。従って、リバランスを行うことが決定される。
【００１３】
そして、図１６（ａ）に示す状態から、リバランス設計のための計算に係る時間（Δｔ）が経過した後（リバランスをする前）、図１６（ｂ）に示す状態になったとする。図１６（ｂ）に示す状態は、負荷の高かったノードＥ（Ｅ´）における負荷が減少し、負荷の低かったノードＢにおける負荷が増加したことを示している。これにより、負荷のアンバランスは許容範囲に収まっている。
【００１４】
しかし、従来技術では、図１６（ａ）の時点でリバランスを行うことを決定したら、図１６（ｂ）に示す状態になるか否かに関わらずに、リバランスを実行する。従って、例えば、図１６（ｂ）に示す状態からリバランスを実行したために、アンバランスが生じ、再度リバランスを実行しなければならない、といったことが生じ得る。
【００１５】
本発明は上記の点に鑑みてなされたものであり、分散システムにおける複数のノード間での負荷の偏りを是正するリバランスを実施する技術において、時間の経過に伴う負荷状態に基づき、リバランスの実行可否を決定することを可能とする技術を提供することを目的とする。
【課題を解決するための手段】
【００１６】
本発明の実施の形態によれば、通信サービスを利用する複数のクライアントマシンからの情報がネットワークを介して振り分けられる複数のノードを有する分散システムにおいて用いられるリバランス装置であって、
前記複数のノードの負荷量に基づいて、当該複数のノード間の負荷量の偏りを抑制するリバランスが必要であるか否かを判定するリバランス処理手段と、
前記リバランス処理手段により、リバランスが必要であると判定された場合において、前記リバランス後の前記複数のノードの予測負荷状態に基づいて、前記リバランスをキャンセルするか否かを判定するキャンセル処理手段とを備え、
前記キャンセル処理手段は、
前記リバランス処理手段によりリバランスが必要であると判定された第１の時点において、当該第１の時点における前記複数のノードの負荷量の平均値からの差分をノード毎に算出し、前記第１の時点から、前記リバランス処理手段によるリバランス設計にかかる時間が経過した第２の時点において、ノード毎に、当該第２の時点におけるノードの負荷量から前記差分を引くことにより、前記予測負荷状態を算出する
ことを特徴とするリバランス装置が提供される。
【００１７】
また、本発明の実施の形態によれば、通信サービスを利用する複数のクライアントマシンからの情報がネットワークを介して振り分けられる複数のノードを有する分散システムにおいて用いられるリバランス装置が実行するリバランス方法であって、
前記複数のノードの負荷量に基づいて、当該複数のノード間の負荷量の偏りを抑制するリバランスが必要であるか否かを判定するリバランス判定ステップと、
前記リバランス判定ステップにより、リバランスが必要であると判定された場合において、前記リバランス後の前記複数のノードの予測負荷状態に基づいて、前記リバランスをキャンセルするか否かを判定するキャンセル判定ステップとを備え、
前記キャンセル判定ステップにおいて、前記リバランス装置は、
前記リバランス判定ステップによりリバランスが必要であると判定された第１の時点において、当該第１の時点における前記複数のノードの負荷量の平均値からの差分をノード毎に算出し、前記第１の時点から、リバランス設計にかかる時間が経過した第２の時点において、ノード毎に、当該第２の時点におけるノードの負荷量から前記差分を引くことにより、前記予測負荷状態を算出する
ことを特徴とするリバランス方法が提供される。
【発明の効果】
【００１８】
本発明の実施の形態によれば、分散システムにおける複数のノード間での負荷の偏りを是正するリバランスを実施する技術において、時間の経過に伴う負荷状態に基づき、リバランスの実行可否を決定することを可能とする技術が提供される。
【図面の簡単な説明】
【００１９】
【図１】本発明の第１実施形態に係る分散システムの構成を示すブロック図である。
【図２】本実施形態の分散システムにおけるノードの構成を示し、（ａ）は制御部の構成を示すブロック図、（ｂ）は記憶部の情報を示すブロック図である。
【図３】複数のノードＡ〜Ｅで分割されたハッシュ空間を示す図である。
【図４】（ａ）ノード識別子管理表の一例を示す図、（ｂ）振分ＩＤ表の一例を示す図である。
【図５】（ａ）ノード負荷計測データ（ノード単位）の一例を示す図、（ｂ）ノード負荷計測データ（仮想ノード単位）の一例を示す図、（ｃ）ノード負荷計測データ（データ単位）の一例を示す図である。
【図６】分散システム負荷集計データの一例を示す図である。
【図７】（ａ）リバランス前の振分ＩＤ表の一例を示す図、（ｂ）リバランス後の振分ＩＤ表の一例を示す図、（ｃ）リバランス後の振分ＩＤ表の他例を示す図である。
【図８】（ａ）リバランス前の振分ＩＤ表の一例を示す図、（ｂ）リバランス後の振分ＩＤ表の一例を示す図である。
【図９】リバランシングキャンセル機能部の動作を説明するための図である。
【図１０】リバランシングキャンセル機能部の動作を説明するための図である。
【図１１】リバランシングキャンセル機能部の動作の効果を説明するための図である。
【図１２】本実施形態の分散システムの各ノードのリバランスを実行する際の動作を説明するためのフローチャートである。
【図１３】本実施形態の分散システムの各ノードのリバランスを実行する際の動作を説明するためのフローチャートである。
【図１４】リバランシングキャンセル機能部の動作を説明するためのフローチャートである。
【図１５】従来技術を説明するためのハッシュ空間を示す図である。
【図１６】課題を説明するための図である。
【発明を実施するための形態】
【００２０】
以下、図面を参照して本発明の実施の形態（本実施の形態）を説明する。なお、以下で説明する実施の形態は一例に過ぎず、本発明が適用される実施の形態は、以下の実施の形態に限られるわけではない。
【００２１】
例えば、以下で説明する例では、クラスタを構成するノード自身が、リバランス必要性判定、リバランス設計、リバランスのキャンセル判定を行うこととしているが、リバランス必要性判定、リバランス設計・実行、リバランスのキャンセル判定を、クラスタを構成するノード以外の装置が実行してもよい。この場合、当該装置が各ノードの負荷情報を収集し、リバランス必要性判定、リバランス設計、リバランスのキャンセル判定、振分ＩＤ表の配付等を行う。
【００２２】
なお、リバランス処理・リバランシングキャンセル判定処理を行う主体が、ノード自身の場合、ノード以外の装置の場合のいずれの場合も、当該主体をリバランス装置と称することができる。
【００２３】
また、以下で説明するリバランスの方法は一例である。本発明に係るリバランシングキャンセル判定方法は、以下で説明するリバランスの方法に限らず、他のリバランスの方法（例：非特許文献４）にも適用可能である。
【００２４】
ただし、以下で説明するリバランスの方法は、非特許文献４のように隣接ノード間での空間配置変更に限定されず、効率的に負荷の偏りを是正できる優れたリバランスの方法である。
【００２５】
（システムの全体構成、ノードの構成）
図１は、本実施の形態に係る分散システムの構成例を示すブロック図である。
【００２６】
図１に示す分散システム１０は、コンシステント・ハッシュ法を用いた複数のノード１５を利用し、データ管理を行うシステムである。当該分散システム１０では、分散システム１０を構成するノード１５間で負荷の偏りが生じた際に、現行ノード１５の負荷の偏り状況を踏まえて、効率的にリバランスを行い負荷の偏りを是正する。ただし、リバランスが必要であると判断した場合、所定時間経過後の負荷状態に基づき、リバランスを実行するか否か（キャンセルするか否か）を判定し、キャンセルしない場合にリバランスを実行する。
【００２７】
分散システム１０は、複数のクライアントマシン（単に、クライアントともいう）１１にインターネット等のネットワーク１２を介して接続されたロードバランサ１３と、クラスタ１４を構成する複数のノード１５とを備えて構成されている。
【００２８】
各ノード１５は、コンピュータ等の物理装置や仮想マシン等の論理装置、言い換えれば、物理的又は仮想的なサーバ等である。クライアント１１からのメッセージが、ロードバランサ１３によって各ノード１５に振り分けられる。この振り分けは、単純なラウンドロビン法等により行われる。
【００２９】
ノード１５は、制御部１８及び記憶部１９を備えて構成されている。但し、制御部１８及び記憶部１９は、ソフトウェア（プログラム）が上記装置（コンピュータ）によって実行されることにより実現されている。当該プログラムは、ネットワークを介して配信してもよいし、メモリ等の記憶媒体に記憶して配付してもよい。なお、制御部１８及び記憶部１９は、それぞれハードウェア（例：処理ロジックを組み込んだ集積回路）によって構成してもよい。
【００３０】
図２（ａ）に示すように、制御部１８は、ノード識別子管理部１８ａと、振分部１８ｂと、信号処理部１８ｃと、ノード負荷計測部１８ｄと、分散システム負荷リバランス部（単に、リバランス部ともいう）１８ｅと、リバランシングキャンセル機能部１８ｆとを備える。
【００３１】
図２（ｂ）に示すように、記憶部１９は、ノード識別子管理表１９ａと、振分ＩＤ表１９ｂと、データ１９ｃと、ノード負荷計測データ１９ｄと、分散システム負荷集計データ１９ｅと、呼制御状態フラグ１９ｆと、ノード毎負荷差分表・ノード毎予測負荷比較表１９ｇと、前回測定データ１９ｈとを記憶する。なお、ノード識別子管理表１９ａを管理表１９ａともいい、分散システム負荷集計データ１９ｅを集計データ１９ｅ、呼制御状態フラグ１９ｆをフラグ１９ｆともいう。
【００３２】
振分部１８ｂは、クライアント１１からのメッセージ（情報）を、例えばコンシステント・ハッシュ法等に基づき、メッセージを担当するノード１５に振り分ける。
【００３３】
信号処理部１８ｃは、クライアント１１からのメッセージに応じて、所定の信号処理を行い、クライアント１１にサービスを提供する。つまり、メッセージを担当するノード１５では、信号処理部１８ｃにて所定の信号処理を行ってクライアント１１にサービスを提供する。この振分部１８ｂ及び信号処理部１８ｃの処理動作については後述で更に詳細に説明する。
【００３４】
但し、分散システム１０においては、ロードバランサ１３が存在せず、クライアント１１から任意のノード１５（振分部１８ｂ）にメッセージを送信することも可能である。また、振分部１８ｂと信号処理部１８ｃは、図２のように同じノード１５上に同時に存在させてもよいし、別ノード１５上に存在させてもよい。
【００３５】
制御部１８において、ノード識別子管理部１８ａ（あるいはリバランス部１８ｅ）は、分散システム１０上のノード情報をノード識別子管理表１９ａに蓄積することにより、各ノード１５が担当するＩＤ空間を管理する。このＩＤ空間は、コンシステント・ハッシュ法ではコンシステント・ハッシュ上の空間（ハッシュ空間）である。
【００３６】
このハッシュ空間を、例えば図３に示すように、複数のノードＡ〜Ｅで分割し、各ノードＡ〜Ｅの担当領域を決めて管理する。この際、ノードＡが担当するハッシュ空間は、ノードＥから時計回りにノードＡまでの領域であり、このハッシュ空間に存在するデータを担当ノードＡが保持（もしくは処理）する。他のノードＢ〜Ｅも同様である。なお、ハッシュ空間（担当領域）のサイズが大きい程に、多くのデータを保持（処理）できるようになっている。
【００３７】
図２（ａ）に戻って、振分部１８ｂは、振分ＩＤ表１９ｂに基づき、メッセージ等のデータの振分先の決定に関する処理を行う。
【００３８】
信号処理部１８ｃは、ノード１５における信号処理を行う。この信号処理時のアクセス対象となるデータ１９ｃが記憶部１９に記憶される。
【００３９】
ノード負荷計測部１８ｄは、自ノード１５の負荷を計測し、この計測結果を記憶部１９にノード負荷計測データ１９ｄとして記録すると共に、必要に応じて定められる特権ノード１５（図３に示す例えばノードＢ）に送付する。
【００４０】
分散システム負荷リバランス部１８ｅは、分散システム１０全体のノード負荷に基づいて、負荷の平均値及び標準偏差等の算出を行い、これらの算出結果である分散システム負荷集計データ１９ｅを記憶部１９に記憶する。更に、リバランス部１８ｅは、その記憶された集計データ１９ｅに基づくリバランスの必要性判定、並びにリバランス設計を行って、リバランシングキャンセル機能部１８ｆにより、リバランスのキャンセルをしないと判定された場合に、リバランスを実行する。リバランシングキャンセル機能部１８ｆについては後述する。
【００４１】
また、記憶部１９に記憶される呼制御状態フラグ１９ｆは、新規呼を制御する状態か否かを判別するための情報である。
【００４２】
（振分部１８ｂ及び信号処理部１８ｃにおける処理について）
ここで、前述した図２に示すノード１５の振分部１８ｂ及び信号処理部１８ｃによるメッセージの振分処理及び信号処理について更に詳細に説明する。
【００４３】
振分部１８ｂは、クライアント１１から発呼されるメッセージ内の情報をもとに、信号処理を担当するノード１５を特定し、当該ノード１５にメッセージの振り分けを行う。メッセージは、新規呼（例えば、ＳＩＰ(Session Initiation Protocol)においてはＩｎｉｔｉａｌ−ＩＮＶＩＴＥ等）と後続呼（ＳＩＰにおいてはＢＹＥ等）に分けられる。
【００４４】
新規呼か後続呼かの識別は、呼のメッセージに後述の振分キーが埋め込まれているか否かで判定できる。例えば、ＳＩＰにおいては、Ｔｏ／ＦｒｏｍヘッダのＴａｇ等で判定できる。
【００４５】
振分キーは、"データ識別子（ＳＩＰにおいてはｃａｌｌ−ｉｄ）＋ハッシュ値"で構成されている。ハッシュ値は、データ識別子からハッシュ関数をかけて導出された値である。
【００４６】
一方、上述した新規呼か後続呼かの識別の判定の結果、後続呼の場合、振分部１８ｂにて、振分ＩＤ表１９ｂ上のノード１５毎の担当領域である振分ＩＤ空間{図４（ｂ）に示し後述する}と、振分キー内のハッシュ値とを比較して担当するノード１５を特定する。更に、担当するノード１５のアドレスを、後述の図４（ａ）に示すノード識別子管理表１９ａから特定し、この特定されたノード１５に転送する。
【００４７】
一方、上述した判定の結果、新規呼の場合、振分キーが存在しないため、メッセージからＣａｌｌ−ｉｄ（データ識別子）を抽出し、これをハッシュ関数に導入してハッシュ値を導出する。更に、振分部１８ｂにて、振分ＩＤ表１９ｂ上のノード１５毎の担当領域である振分ＩＤ空間{図４（ｂ）に示し後述する}と、導出したハッシュ値とを比較して担当するノード１５を特定する。更に、担当するノード１５のアドレスを、後述の図４（ａ）に示すノード識別子管理表１９ａから特定し、この特定されたノード１５に転送する。
【００４８】
新規呼を信号処理部１８ｃで受信した場合も、メッセージからＣａｌｌ−ｉｄ（データ識別子）を抽出し、これをハッシュ関数に導入してハッシュ値を導出して、振分キーを生成する。また、信号処理部１８ｃによる信号処理後に、クライアント１１（ＳＩＰにおいてはＵＡＣやＵＡＳ等）に送付するメッセージに振分キーを埋め込んで（ＳＩＰにおいてはＴｏ／ＦｒｏｍヘッダのＴａｇ）送付する。
【００４９】
以降、クライアント１１からの後続呼には本振分キーを埋め込みの上、メッセージを送付し、振分部１８ｂにて本振分キーのハッシュ値を基に振り分けが行われることで、当該呼が処理されたノード１５に後続呼が届くことが可能となる。
【００５０】
（ノード識別子管理部１８ａについて）
次に、上述したノード識別子管理部１８ａについて、より詳細に説明する。
【００５１】
ノード識別子管理部１８ａは、分散システム１０へのノード１５の追加や離脱が発生した際に、分散システム１０を構成するノード１５の識別子情報（ノード識別子）を更新し、これを、図４（ａ）に示すノード識別子管理表１９ａとして管理する。図４（ａ）の例においては、ノード識別子（又はノードＩＤ）（例えば、「Ｎｏｄｅ１」）に、アドレス（例えば、「１０．４５．０．１」）が対応付けられている。そのノード識別子は、特権ノードのノード識別子管理部１８ａで付与され、全ノード１５へと配信される。
【００５２】
コンシステント・ハッシュ法においては、ノード識別子に、図４（ｂ）に示す仮想ノード識別子（又は仮想ノードＩＤ）が従属している。この仮想ノードＩＤは、振分ＩＤ空間の任意のＩＤ（ハッシュ値による）である。例えば図４（ａ）に示すノード識別子「Ｎｏｄｅ１」には、図４（ｂ）の振分ＩＤ表１９ｂに示す少なくとも１つ以上の仮想ノードＩＤ「Ｎｏｄｅ１−１」，「Ｎｏｄｅ１−２」が従属している。言い換えれば、ノード１５に１つ以上の仮想ノードが従属している。但し、これは基本構成であって、ノード１５に仮想ノードが従属しない場合もある。
【００５３】
このように、前述のノード識別子管理表１９ａの更新と合わせて、ノード１５が担当する振分ＩＤ空間の担当領域を更新し、これを振分ＩＤ表１９ｂとして管理する。振分ＩＤ表１９ｂには、例えば、仮想ノードＩＤ「Ｎｏｄｅ１−１」に、担当する振分ＩＤ空間の担当領域として「０〜１９９（Ｄ＝２００）」のデータサイズが対応付けられ、仮想ノードＩＤ「Ｎｏｄｅ１−２」に、担当する振分ＩＤ空間の担当領域として「６００〜９９９（Ｄ＝４００）」のデータサイズが対応付けられている。即ち、Ｄ＝２００は、担当領域のデータサイズが２００であることを示す。他のＤ＝４００等も同じである。
【００５４】
（ノード負荷計測部１８ｄの処理について）
次に、上述したノード負荷計測部１８ｄにより計測される負荷の情報収集と、この収集された負荷の特権ノードへの送付について説明する。
【００５５】
ノード負荷計測部１８ｄは、所定の周期で当該ノード１５の負荷を計測し、これをノード負荷計測データ１９ｄとして記憶部１９に記録して蓄積する。また、ノード負荷計測部１８ｄは、所定の周期で特権ノード（例えば図３に示すノードＢ）に蓄積したノード負荷計測データ１９ｄを送付する。
【００５６】
また、特権ノードは、各ノード１５から収集した全ノードの負荷データを、全ノード１５へ配信する。各ノード１５は、この負荷データをノード負荷計測データ１９ｄとして記憶部１９に記録することができる。
【００５７】
上述したノード負荷計測部１８ｄにおいて所定周期で計測されるノード１５の負荷として、ＣＰＵ(Central Processing Unit)使用率、メモリ使用率、アクセス頻度等の、ノード１５にて取得可能なあらゆるパラメータを使用することができる。また、どの数値がボトルネックとなるか、更に、どの程度の値であればリバランスすべき閾値となるかは、分散システムのシステム特性に応じて異なり、複数のパラメータの組み合わせにより判断するケースもある。従って、特定のパラメータ種別に限定せず利用可能とする。
【００５８】
また、ノード負荷計測部１８ｄによる負荷の計測単位は、図５の（ａ）ノードＩＤによるノード単位、（ｂ）仮想ノードＩＤによる仮想ノードＩＤ単位、（ｃ）データ単位の内、どの単位で計測しても構わない。また、図５（ｂ）の仮想ノード単位で負荷を計測する場合、それを集計して（ａ）のノード単位を算出可能であり、（ｃ）のデータ単位で負荷を計測する場合、それを集計して（ｂ）の仮想ノード単位や（ａ）のノード単位の負荷を算出可能である。なお、図５においては、ノード負荷計測部１８ｄにより計測される負荷は、アクセス頻度（アクセス回数）を例に示してある。
【００５９】
このような図５（ａ）〜（ｃ）の表は、２つのノード１５で構成される分散システム１０におけるものであり、次のような構成となっている。
【００６０】
図５（ａ）に示す１つのノード１５（例えばノードＩＤ＝Ｎｏｄｅ１）において、図５（ｂ）に示す２つの仮想ノードＩＤ（Ｎｏｄｅ１_１，Ｎｏｄｅ１_２）による２つの仮想ノードを保持する。更に、図５（ｃ）に示す１つの仮想ノードＩＤ（例えばＮｏｄｅ１_１）による仮想ノード当り２つのデータ（ｄａｔａ１，ｄａｔａ２）を保有する場合を想定してある。他のノードも同様である。
【００６１】
この場合に、負荷の計測単位を図５（ｂ）に示すように仮想ノード単位とし、収集する負荷としてのアクセス頻度（回数）を、１０秒周期（１０：１５：００→１０：１５：１０→１０：１５：２０）で収集して、蓄積するケースを想定してある。
【００６２】
（分散システム負荷リバランス部１８ｅによるリバランスの判定処理について）
次に、上述した分散システム負荷リバランス部１８ｅによるノード１５の負荷の偏り算出及びリバランス必要性判断の処理について説明する。以下で説明する分散システム負荷リバランス部１８ｅにおけるリバランス必要性判断、リバランス設計、実行（振分ＩＤ表配付）の処理は、どのノード１５が行ってもよいが、ここでは、特権ノードが行うことを想定している。
【００６３】
リバランス部１８ｅは、所定の周期で各ノード１５から収集したノードの負荷データ（ノード負荷計測データ１９ｄ）に基づき、分散システム１０全体のノード１５の負荷の平均値及び標準偏差、偏差並びに偏差／標準偏差（偏差を標準偏差で除した値）の算出を行う。更に、リバランス部１８ｅは、それらの算出結果を、図６に一例を示すように集計データ１９ｅとして記録し、この記録した集計データ１９ｅに基づき、後述の３つの条件（１）〜（３）の何れか１つを満たす場合、ノード１５間の負荷の偏りを是正するリバランスが必要であると判定する。何れも満たさない場合はリバランスが不要であると判定する。
【００６４】
図６に示す集計データ１９ｅには、収集時の時刻、ノードＩＤ（ノード識別子）、平均値（アクセス頻度）、標準偏差、実測値（アクセス頻度）、偏差（平均値からの差分）、及び偏差／標準偏差が記録される。なお、平均値及び実測値は、アクセス頻度の平均値及び実測値である。
【００６５】
条件（１）、リバランス部１８ｅは、集計データ１９ｅに基づき、いずれかのノード１５の負荷が、当該ノード１５が許容する負荷の上限値（予め定められた上限値）を超えていないか否かをチェックし、上限値を超えるノードが存在する場合に、リバランスが必要であると判定する。
【００６６】
条件（２）、リバランス部１８ｅは、集計データ１９ｅに基づき、ノード１５全体の負荷の標準偏差が所定の閾値（第１閾値）以下であるか否かを確認し、閾値を超えている場合に、リバランスが必要であると判定する。
【００６７】
条件（３）、リバランス部１８ｅは、集計データ１９ｅに基づき、ノード１５毎の負荷の偏差／標準偏差が所定の閾値（第２閾値）以下であるか否かを確認し、閾値を超えているノード１５がある場合に、リバランスが必要であると判定する。
【００６８】
但し、図６に示す集計データ１９ｅにおいては、負荷の計測単位を図５（ａ）に示すノード単位（仮想ノード単位の場合もある）とし、負荷の平均値及び実測値をアクセス頻度とする。更に、平均値や標準偏差を算出する際の時間間隔を２０秒間（例えば、１０：１４：４０〜１０：１５：００）とする。図６の例は、１０：１５：００の時刻における上記算出値等である。また、各ノード１５が許容する負荷の上限値をアクセス頻度の実測値についての上限値として、これを「９０」｛条件（１）｝とし、標準偏差の閾値を「１５」｛条件（２）｝、偏差／標準偏差の閾値（乖離閾値ともいう）を「１．２」｛条件（３）｝とした際の例である。なお、平均値や標準偏差を算出する際の時間間隔は、リバランスの必要性を判定する時間間隔であってもよい。
【００６９】
この例では、条件（１）、（２）は満たさない。しかし、図６ではノード識別子の「Ｎｏｄｅ１」、「Ｎｏｄｅ３」、「Ｎｏｄｅ４」の偏差／標準偏差が「１．５」であり、閾値「１．２」を超えており、条件（３）を満たしているため、リバランスが必要であると判定される。ただし、後述するリバランシングキャンセル機能部１８ｆにより、リバランスをキャンセルすると判定された場合には、このタイミングでのリバランスは実行されない。
【００７０】
（分散システム負荷リバランス部１８ｅによるリバランスの設計、及び実行処理について）
ここで、リバランシングキャンセル機能部１８ｆによりリバランスがキャンセルされない場合における、リバランス部１８ｅが実行するリバランスの設計、及び実行処理について説明する。
【００７１】
リバランスは、負荷の高いノード１５の担当領域（担当のＩＤ空間）中の移譲領域（後述）を、負荷の低いノード１５へ移譲することで負荷の偏りを是正する。この時、負荷の乖離を是正するために、担当領域の必要な移譲領域のサイズを推定の上、その移譲領域のみを移譲する。但し、移譲領域は、担当領域の全てであったり、担当領域の１００％未満の割合の領域であったりする。
【００７２】
本実施の形態において、この移譲の方法は、次の（Ｔ１）〜（Ｔ４）のようになる。
【００７３】
（Ｔ１）全てのノード１５の中で最も負荷の高いノード１５の担当領域中の移譲領域を、最も低いノード１５に対して移譲していくものとする。
【００７４】
（Ｔ２）移譲領域の移譲は次の場合に終了するものとする。即ち、上記の条件（１）〜（３）の何れかを満たす要因となった偏差の全てが存在しなくなった場合（Ｔ２−１）、若しくは、その偏差の一部（予め指定の偏差解消割合を満たす偏差）を解消する移譲領域の移譲が決定した場合（Ｔ２−２）、若しくは、移譲領域の移譲を許容可能な移譲先ノード１５が存在しなくなった場合（Ｔ２−３）に終了するものとする。
【００７５】
（Ｔ３）移譲領域の移譲単位は、ノード単位や仮想ノード単位でも構わないし、仮想ノード単位でなく、仮想ノードの担当領域の半分を割譲する単位や、１つのハッシュ値によるデータのみの移譲単位でも構わない。
【００７６】
（Ｔ４）リバランス部１８ｅがリバランスを行う際に事前に実行するリバランス設計は、負荷の計測単位を上述したノード単位、仮想ノード単位及びデータ単位の内、どの単位で実行していたかで、可能なリバランス設計の粒度が、次に記載するように変わる。
【００７７】
即ち、ノード単位の負荷計測の場合、後述のリバランス粒度が粗い場合のみの方式となる。
【００７８】
仮想ノード単位の負荷計測の場合、後述のリバランス粒度が粗い場合及びリバランス粒度が中間（粗いと細かいとの中間）の場合の方式が可能となる。
【００７９】
データ単位の負荷計測の場合、後述のリバランス粒度が粗い場合、中間の場合及び細かい場合の３つ全ての方式が採用可能となる。
【００８０】
まず、リバランス粒度が粗い場合について説明する。
【００８１】
ノード１５全体における負荷の総量を、ノード１５全ての仮想ノードＩＤ数で割った仮想ノード当たりの平均負荷量「Ｌｖ＿ａｖｅ」を算出する。次に、ノード１５間において最も負荷の高いノード１５に着目し、このノード１５について解消すべき負荷量の偏差（この偏差の符号は＋であることから、プラス偏差ともいう）「Ｌｔａｒｇｅｔ」を算出する。この偏差は、例えば、当該ノード１５について、図６で示されているプラスの偏差（実測値の平均値との差分）である。
【００８２】
次に、「Ｌｔａｒｇｅｔ」を「Ｌｖ＿ａｖｅ」で割った値を、解消すべき負荷量を解消するために必要な仮想ノードＩＤ数「Ｖｔａｒｇｅｔ＿ｎｕｍ」と考える。
【００８３】
この最も負荷の高いノード１５の仮想ノードの中から無作為に「Ｖｔａｒｇｅｔ＿ｎｕｍ」の仮想ノードＩＤを抽出する。この時、「Ｖｔａｒｇｅｔ＿ｎｕｍ」に小数が含まれる場合は、上記（Ｔ３）にその概要を記載したように、所定の仮想ノードＩＤの仮想ノードの担当領域を例えば小数に基づき割譲してもよい。これは、例えば「１．５」の場合、仮想ノード１つの担当領域の割譲と、仮想ノード２つ目の担当領域を半分にして割譲することである。更に、小数部分を切り捨てや切り上げ、又は四捨五入する等して整数個の仮想ノードＩＤを抽出してもよい。
【００８４】
上述したように、無作為に抽出された仮想ノードＩＤ「Ｖｔａｒｇｅｔ＿ｎｕｍ」の仮想ノードの担当領域中の移譲領域を移譲する際に、全てのノード１５の中で、最も負荷の低いノード１５から順に移譲していく。この際、移譲によって移譲先のノード１５の負荷が高まりすぎないように、許容可能な担当領域の移譲サイズを求める必要がある。
【００８５】
具体的には、移譲先のノード１５は、負荷量の偏差（この偏差の符号は−であることから、マイナス偏差ともいう）までは受け入れ許容可能である。このため、負荷量のマイナス偏差を平均負荷量「Ｌｖ＿ａｖｅ」で割った値である負荷量解消に必要な仮想ノードＩＤ数「Ｖｇｅｔ＿ｎｕｍ１」が、許容可能な仮想ノードＩＤ数となる。
【００８６】
ここで、移譲先のノード１５の担当領域が許容量を越える場合は、次に負荷の低いノード１５について、同様の手順で許容可能な仮想ノードＩＤ数「Ｖｇｅｔ＿ｎｕｍ２」を求めていき、Ｖｔａｒｇｅｔ＿ｎｕｍ＜Ｖｇｅｔ＿ｎｕｍ１＋Ｖｇｅｔ＿ｎｕｍ２＋…となって、全ての必要な担当領域中の移譲領域の移譲が完了すれば終了となる。
【００８７】
以降同様の処理を、次に負荷の高いノードに対しても実行し、全ての負荷乖離の解消が必要なノード１５において、負荷の乖離を是正する担当領域中の移譲領域の移譲が完了するか、若しくは、移譲領域の移譲が可能なノードが存在しなくなるまで実行する。
【００８８】
次に、リバランス粒度が中間の場合について説明する。
【００８９】
基本的に上述したリバランス粒度が粗い場合と同じであるため、粗い場合との差分のみを説明する。
【００９０】
上述したように、移譲元のノード１５の仮想ノードの中から無作為に仮想ノードを抽出するのではなく、解消すべき負荷量のプラス偏差を発生させている仮想ノードを選択的に抽出し、この抽出した仮想ノードの担当領域中の移譲領域を移譲するものとする。この場合、仮想ノード単位で負荷量を計測しているため、計測負荷は粒度が粗い場合よりも高くなるが、負荷の乖離を是正するための移譲領域の移譲を、より正確に行うことが可能となる。
【００９１】
次に、リバランス粒度が細かい場合について説明する。
【００９２】
基本的に上述したリバランス粒度が粗い場合と同じであるため、粗い場合との差分のみを説明する。
【００９３】
上述したように、移譲元のノード１５の仮想ノードの中から無作為に仮想ノードを抽出するのではなく、解消すべき負荷量のプラス偏差を発生させているデータのハッシュ値を選択的に抽出し、そのハッシュ値のみを移譲するものとする。この場合、データ単位で負荷量を計測しているため、計測負荷はリバランス粒度が中間の場合よりも高くなるが、負荷の乖離を是正するための移譲領域の移譲を、より正確に行うことが可能となる。また、移譲の単位も最小化することができる。
【００９４】
リバランス部１８ｅは、リバランスが必要であると判定した場合に、負荷の偏りを是正するリバランス設計を、上述した手順で実行し、振分ＩＤ表１９ｂに反映させる。ただし、振分ＩＤ表１９ｂの全ノード１５への送付については、リバランスがキャンセルされない場合に実行する。
【００９５】
例えば、図７（ａ）に示すように、リバランス前の振分ＩＤ表１９ｂは、仮想ノードＩＤ「Ｎｏｄｅ１−１」に、担当する振分ＩＤ空間の担当領域として「０〜１９９（Ｄ＝２００）」のデータサイズが対応付けられ、「Ｎｏｄｅ２−１」に「２００〜３９９（Ｄ＝２００）」、「Ｎｏｄｅ３−１」に「４００〜５９９（Ｄ＝２００）」、「Ｎｏｄｅ１−２」に「６００〜９９９（Ｄ＝４００）」のデータサイズが対応付けられているとする。
【００９６】
ここで、例えば図７（ａ）に示す「Ｎｏｄｅ１−２」の仮想ノードの担当領域「６００〜９９９（Ｄ＝４００）」を全て、他の仮想ノードＩＤ「Ｎｏｄｅ３＿２」の仮想ノードへ移譲するものとする。この場合、図７（ｂ）に示すように、仮想ノードＩＤ「Ｎｏｄｅ３＿２」の仮想ノードの担当領域が「６００〜９９９（Ｄ＝４００）」のサイズとなる。
【００９７】
また、図７（ａ）に示す「Ｎｏｄｅ１−２」の仮想ノードの担当領域「６００〜９９９（Ｄ＝４００）」の半分を、他の仮想ノードＩＤ「Ｎｏｄｅ３＿２」の仮想ノードへ移譲するものとする。この場合、図７（ｃ）に示すように、仮想ノードＩＤ「Ｎｏｄｅ１＿２」の仮想ノードの担当領域が「６００〜７９９（Ｄ＝２００）」のサイズとなり、仮想ノードＩＤ「Ｎｏｄｅ３＿２」の仮想ノードの担当領域が「８００〜９９９（Ｄ＝２００）」のサイズとなる。
【００９８】
＜リバランス設計の他の例＞
リバランス部１８ｅが以下で説明する処理によりリバランス設計を行うようにしてもよい。
【００９９】
ここでは、分散システム１０の各ノード１５のリソースの総量（負荷の総量）が、使用リソース量（使用負荷量）に対して十分であるにも関わらず、使用リソース量に偏りが生じているとする。この際に、リバランス部１８ｅが、上述した処理のように担当領域中の移譲領域を移譲する対象ノードや、該当ノード１５の適切な移譲サイズを指定することなく、各ノード１５が持つ仮想ノード数を、ノード１５毎の現状の負荷の状況に応じて、ノード１５毎に必要な負荷量とする仮想ノード数に再設定するリバランスを行うようにする。
【０１００】
この際、リバランス部１８ｅは、各ノード１５の仮想ノード数を、負荷の状況に合わせて下式（１）により算出し、この算出された各ノード１５の仮想ノード数に基づきリバランスする。
【０１０１】
このリバランスにおいては、算出された仮想ノード数に基づき、各仮想ノードの振分ＩＤ空間の先頭から仮想ノードＩＤと振分ＩＤ空間の再マッピングを行う。再マッピングは、担当領域の総延長（総サイズ）を算出した仮想ノード数で除し、１仮想ノード当たりの振分ＩＤ空間サイズを求め、振分ＩＤ空間の先頭から新たな振分ＩＤ空間サイズ毎に、仮想ノードＩＤ毎の仮想ノード数を再設定していく。
【０１０２】
リバランス後の仮想ノード数＝現状の仮想ノード数×(全ノードの負荷の平均値／該当ノードの負荷の実測値)  …（式１）
但し、式（１）中の「該当ノードの負荷の実測値」は、現状の仮想ノードを有するノードの負荷の実測値である。また、式（１）はリバランス部１８ｅの図示せぬ記憶部に保持されるものとする。
【０１０３】
以下、ここでのリバランス処理について具体的に説明する。
【０１０４】
リバランス部１８ｅは、まず、各ノード１５が持つ仮想ノード数を再設定する。この再設定の処理を図８（ａ）及び（ｂ）を参照して説明する。但し、図８（ａ）及び（ｂ）に示す仮想ノードＩＤ「Ｎｏｄｅ１−１」，「Ｎｏｄｅ１−２」は、ノードＩＤ「Ｎｏｄｅ１」のノード１に従属する仮想ノード１−１，１−２に対応するものとする。他の仮想ノードＩＤにおいても同様であり、例えば、仮想ノードＩＤ「Ｎｏｄｅ５−１」，「Ｎｏｄｅ５−２」，「Ｎｏｄｅ５−３」は、ノードＩＤ「Ｎｏｄｅ５」のノード５に従属する仮想ノード５−１，５−２，５−３に対応するものとする。
【０１０５】
図８（ａ）に示す振分ＩＤ表１９ｂには、仮想ノードＩＤ「Ｎｏｄｅ１−１」に、担当する振分ＩＤ空間の担当領域として「０〜１９９（Ｄ＝２００）」のデータサイズが対応付けられ、「Ｎｏｄｅ１−２」に、「２００〜３９９（Ｄ＝２００）」のデータサイズが対応付けられている。他の仮想ノードＩＤにおいても図示する通りである。
【０１０６】
更に、各ノード１〜５の仮想ノード数は、ノード１の仮想ノード数が２個、ノード２の仮想ノード数が１個、ノード３の仮想ノード数が１個、ノード４の仮想ノード数が２個、ノード５の仮想ノード数が２個である。
【０１０７】
このような条件において、リバランス部１８ｅは、ノード１〜５が持つ仮想ノード数を現状の負荷の状況に応じて、必要な負荷量に再設定する。以降、この再設定の処理について説明する。
【０１０８】
まず、リバランス部１８ｅは、各ノード１〜５の仮想ノード数を変更する。例えば、各ノード１〜５の現状の仮想ノード数は、図８（ａ）に示すように、ノード１が２個、ノード２が１個、ノード３が１個、ノード４が２個、ノード５が２個の合計８個である。これを、各ノード１〜５の負荷の現状に応じて、図８（ｂ）に示すように、ノード１が１個、ノード２が２個、ノード３が２個、ノード４が２個、ノード５が３個の合計１０個に変更する。
【０１０９】
この仮想ノード数の変更を行う場合に上記式（１）を用いる。仮想ノード数の変更は、例えば図８（ａ）に示す各ノード１〜５の個数「２個、１個、１個、２個、２個」＝８個を、図８（ｂ）に示す各ノード１〜５の個数「１個、２個、２個、２個、３個」＝１０個に変更することである。
【０１１０】
図８（ａ）の現状では、全ノード１〜５のハッシュ空間サイズ（担当領域のサイズ）は「０〜１５９９」の１６００であり、仮想ノード数は８個なので、仮想ノード当たりの担当領域のサイズは、１６００÷８＝２００である。このＤ＝２００の担当領域のサイズの内、該当ノード１の負荷の実測値は、例えば「８０」や「１５０」のようになる。このような全ノード１〜５の実測値から、全ノード１〜５の負荷の平均値が求められるので、その平均値及び実測値を上記式（１）に代入する。
【０１１１】
例えば、仮想ノードＩＤ＝「Ｎｏｄｅ１−１」の振分ＩＤ空間の担当領域（サイズＤ＝２００）では負荷の実測値が「１４０」、「Ｎｏｄｅ１−２」では負荷の実測値が「１６０」であるとすると、ノード１の負荷の実測値は「３００」である。この際、全ノード１〜５の負荷の平均値が「１５０」とする。この場合、ノード１のリバランス後の仮想ノード数は、２×（１５０／３００）＝１となる。同様に、他のノード２〜５においてもリバランス後の仮想ノード数を求め、各ノード１〜５の仮想ノード数を、その求められた仮想ノード数に変更する。但し、式（１）に当て嵌めた計算結果が、１．６等の小数点を伴う場合、切り上げ、切り捨て、四捨五入とすることを予め決めておく。
【０１１２】
次に、リバランス部１８ｅは、仮想ノード当たりのハッシュ空間サイズを変更する。図８（ａ）に示す現状では、上述したように、仮想ノード当たりのハッシュ空間サイズＤは、１６００÷８＝２００である。
【０１１３】
これを、上述した変更後の仮想ノード数＝１０個を用いると、仮想ノード当たりのハッシュ空間サイズは、１６００÷１０＝１６０となる。このハッシュ空間サイズを用いて、図８（ｂ）に示すように、１個当たりの仮想ノードのハッシュ空間サイズＤを「１６０」とする。
【０１１４】
次に、リバランス部１８ｅは、その変更後のハッシュ空間サイズＤ＝「１６０」の仮想ノードを、前述で変更した後の各ノード１〜５の仮想ノード数だけ割り振って行く。即ち、ノード１では変更後の仮想ノードが１個なので、図８（ｂ）に示すように、ノード１において、変更後のハッシュ空間サイズＤ＝「１６０」の仮想ノード｛仮想ノードＩＤ「Ｎｏｄｅ１−１」｝が１個割り振られる。
【０１１５】
同様に、ノード２では変更後の仮想ノードが２個なので、サイズＤ＝「１６０」の仮想ノード｛仮想ノードＩＤ「Ｎｏｄｅ２−１，Ｎｏｄｅ２−２」｝が２個割り振られる。以降、同様に図示するように、ノード３〜５まで変更後の仮想ノード２個〜３個が割り振られる。
【０１１６】
上記のようなリバランス設計の結果、図８（ｂ）に示すようなリバランス後の振分ＩＤ表が得られ、キャンセルがない場合に、これが各ノード１５に配付される。各ノード１５は、当該振分ＩＤ表に従って、振り分け処理を実行する。
【０１１７】
（リバランシングキャンセル機能部１８ｆの処理について）
以下、リバランシングキャンセル機能部１８ｆの処理について説明する。リバランシングキャンセル機能部１８ｆの処理についてもどのノード１５で行ってもよいが、ここでは、前述したように、リバランス設計、及びリバランス後の振分ＩＤ表の配付を行う特権ノードが行うことを想定している。
【０１１８】
リバランシングキャンセル機能部１８ｆは、リバランス部１８ｅにより、リバランスが必要であると判定された場合に、まず、ノード負荷計測部１８ｄにより得られた全ノード１５の負荷データに基づき、ノード毎負荷差分表１９ｇを作成し、記憶部１９に記憶する。
【０１１９】
図９の左側に、ノード毎負荷差分表１９ｇの例を示す。図９の例に示すように、ノード毎負荷差分表１９ｇは、ノード１５毎の実測負荷と、平均値（全ノードの合計負荷÷ノード数、ここでは７０）からの差分（偏差）からなる。なお、本例では、ノード単位の計算例を示しているが、ここでのノードは、「仮想ノード」であってもよい。
【０１２０】
そして、ノード負荷計測部１８ｄは、ノード毎負荷差分表１９ｇを作成した時刻（＝リバランスが必要であると判定された時刻であり、これをｔとおく）における各ノードの負荷データ（差分のみでもよい）を、前回測定データ１９ｈとして、記憶部１９に格納する。前回測定データ１９ｈが既に格納されている場合、既に格納されている「前回測定データ１９ｈ」は削除され、今回の「前回測定データ１９ｈ」が格納される。
【０１２１】
次に、リバランシングキャンセル機能部１８ｆは、ｔからリバランス設計にかかる時間（Δｔ）の後（つまり、時刻ｔ＋Δｔの時点）に、現時点のノード負荷計測データ１９ｄ（各ノード１５の負荷の実測データ）を取得し、当該現時点のノード負荷計測データ１９ｄと、前回測定データ１９ｈとから、ノード毎予測負荷比較表１９ｇ（キャンセル判定に係る表という意味でノード毎負荷差分表と同じ１９ｇを付している）を作成する。なお、Δｔは、予め定めた時間であってもよいし、リバランス部１８ｅが計算に係るノード数等からΔｔを推定し、リバランス部１８ｅがリバランシングキャンセル機能部１８ｆに対してΔｔを通知することとしてもよい。なお、ノード負荷計測データ１９ｄの更新時間間隔は、Δｔよりも短い。
【０１２２】
図９の右側に、ノード毎予測負荷比較表１９ｇの例を示す。当該ノード毎予測負荷比較表１９ｇに示されるように、ノード毎予測負荷比較表１９ｇは、現時点（ｔ+Δｔ）でのノード毎の負荷と、ｔの時刻での差分（"前差"と呼ぶ）と、予測負荷とを有する。予測負荷は、リバランスを実行したと仮定した場合における、各ノードの負荷である。リバランスにより、差分が解消されることが想定されるから、ここでの予測負荷は、「現時点での負荷‐前差」で求めている。例えば、図９の例で、ノードＡにおける現時点（ｔ＋Δｔ）での負荷は１２５であり、前差が＋６８であるから、予測負荷は１２５−６８＝５７となっている。
【０１２３】
そして、リバランシングキャンセル機能部１８ｆは、以下の判定基準（１）、（２）のうちのいずれかが満たされるか否かを判定し、いずれかが満たされる場合に、ｔのタイミングで必要であると判定されたリバランスをキャンセルする。いずれも満たされない場合は、リバランスを実行することを決定する。
【０１２４】
判定基準（１）：ノード数に増減がある。
【０１２５】
判定基準（２）：負荷予測値が、許容範囲外になるノードが存在する。
【０１２６】
上記判定基準（１）のノード数の増減については、例えば、リバランシングキャンセル機能部１８ｆが、リバランス部１８ｅからリバランス設計結果（振分ＩＤ表）を取得することで判定できる。ここで、ノード数が増加する場合とは、例えば、負荷の増大が大きく、現状のノード数では不足し、ノードを追加することが必要になる場合等である。また、ノード数が減少する場合とは、例えば、負荷の減少が大きく、現状のノード数では大きすぎ、非効率であるため、ノードを削減する場合等である。
【０１２７】
また、判定基準（２）について、許容範囲は予め定めておく値である。図９の例では、許容範囲を平均値から±２０％としている。そして、図９の例では、ノードＧが許容範囲外となるため、リバランスをキャンセルすると判定される。
【０１２８】
一方、図１０に示す例では、全ノードについて、許容範囲内であるため、リバランスを実行すると判定される。
【０１２９】
また、判定基準（２）に関して、許容範囲外となるノードの個数が予め定めた閾値を超えた場合に、判定基準（２）を満たす、こととしてもよい。一例として、判定基準（２）を「許容範囲外のノードの個数＞全ノード数の20%」とし、これを満たした場合にキャンセルする。この場合、図９、１０の例では、予測値が３個以上許容範囲外の場合にキャンセルする。
【０１３０】
ここで、リバランスをキャンセルするとは、例えば、リバランシングキャンセル機能部１８ｆがリバランス部１８ｅに対し、リバランス設計で得られた新たな振分ＩＤ表を、各ノード１５に配付せずに破棄することを指示することである。また、リバランスを実行することを決定した場合、リバランシングキャンセル機能部１８ｆは、リバランス部１８ｅに対し、リバランス設計で得られた新たな振分ＩＤ表を、各ノード１５に配付することを指示する。
【０１３１】
図１１を参照して、リバランシングキャンセル機能部１８ｆの処理の効果を説明する。図１１は、例えば、あるノードについての負荷の推移を示したものである。時刻ｔにおいてリバランスが必要であると判定される。その後、当該ノードの負荷が低下し、ｔ＋Δｔの時点では、許容範囲（リバランスを行う必要のない範囲）に入っている。しかし、従来技術では、このような負荷の時間変化を考慮しないため、リバランスを行ってしまい、負荷が許容範囲外となり、再度リバランスが実行される。
【０１３２】
一方、リバランシングキャンセル機能部１８ｆの判定機能により、ｔ＋Δｔの時点でリバランスをキャンセルすると判定するので、無駄なリバランスを実行することなく、許容範囲の負荷を保つことができる。
【０１３３】
（動作例）
次に、本実施の形態に係る分散システム１０において、ノード１５間の負荷の偏りを是正するリバランスの必要性の判定、及び、キャンセル判定等を実行する際の動作例を、図１２〜図１４のフローチャートを参照して説明する。本動作例は、例えば図３に示すハッシュ空間を前提とする。また、以下の動作例は、最初に説明したリバランス設計方法に対応する。
【０１３４】
まず、図１２に示すステップＳ１において、所定のノード（例：図３のノードＢ）の分散システム負荷リバランス部１８ｅは、所定の周期で各ノードＡ〜Ｅから収集したノード負荷計測データ１９ｄに基づき、各ノードＡ〜Ｅの負荷の平均値及び標準偏差、偏差並びに偏差／標準偏差の算出を行う。
【０１３５】
次に、ステップＳ２において、リバランス部１８ｅは、上記ステップＳ１での算出結果を集計データ１９ｅ（例：図６）として記憶部１９に記録する。
【０１３６】
ステップＳ３において、リバランス部１８ｅは、上記ステップＳ２で記録したデータ１９ｅに基づき、上述した３つの条件（１）〜（３）の何れか１つを満たすか否かを判定する。この結果、満たさなければ（Ｎｏ）、リバランスの処理を終了する。
【０１３７】
一方、その判定の結果、何れか１つを満たす場合、ステップＳ３において、リバランシングキャンセル機能部１８ｆが、リバランシングキャンセル判定を実施する。
【０１３８】
リバランシングキャンセル判定については図１４を参照する。リバランシングキャンセル機能部１８ｆは、リバランスが必要であると判定された時点（ｔ）におけるノード毎負荷差分表１９ｇを作成し、その後、ｔ＋Δｔの時点で、当該ノード毎負荷差分表１９ｇと、その時点のノード負荷計測データ１９ｄとに基づいて、ノード毎予測負荷比較表１９ｇを作成する（ステップＳ４１）。そして、ステップＳ４２において、リバランシングキャンセル機能部１８ｆは、前述した判定基準（１）、判定基準（２）のうちのいずれかを満たすかどうかを判定し、満たす場合はリバランスをキャンセルし（ステップＳ４３）、満たさない場合はキャンセルしない（ステップＳ４４）。
【０１３９】
図１２に戻り、リバランスをキャンセルする場合は、ステップＳ１に戻り、次のタイミングで、上記と同様に、リバランス実施の必要性を判定する。
【０１４０】
リバランスをキャンセルしない場合、ステップＳ５において、各ノードＡ〜Ｅの負荷量を検知し、例えば、高負荷ノードＡの担当領域中の移譲領域を他ノードＢ，Ｃに移譲することで負荷の偏りを是正する、といった判断を行う。
【０１４１】
ステップＳ６において、リバランス部１８ｅは、移譲元ノードの担当領域中の移譲領域のサイズ（＝負荷量）を求め、ステップＳ７において、移譲先ノードの担当領域の許容可能なサイズを求める。
【０１４２】
次に、図１３に示すステップＳ８において、リバランス部１８ｅは、移譲元ノードの移譲対象の担当領域を移譲可能な移譲先ノードが有るか否かを判定する。この判定は、移譲先ノードの担当領域の許容可能なサイズが、移譲元ノードの担当領域中の移譲領域を移譲可能であるか否かを検知して行う。この結果、移譲可能な移譲先ノーが無ければ（Ｎｏ）、リバランスの処理を終了する。
【０１４３】
一方、移譲可能な移譲先ノードが有れば（Ｙｅｓ）、ステップＳ９において、リバランス部１８ｅは、移譲元ノードの担当領域中の移譲領域を、移譲先ノードへ移譲する。
【０１４４】
この後、図１３に示すステップＳ１０において、リバランス部１８ｅは、移譲元ノードの担当領域中の移譲領域の残りが有るか否かを判定する。この結果、残りが無ければ（Ｎｏ）、言い換えれば、移譲対象の担当領域が全て移譲完遂されていれば、リバランスの処理を終了する。
【０１４５】
一方、上記ステップＳ１０の判定で残りが有れば（Ｙｅｓ）、ステップＳ１１において、リバランス部１８ｅは、移譲元ノードの残りの移譲領域が移譲可能な、移譲先ノードが有るか否かを判定する。この結果、移譲先ノードが無ければ（Ｎｏ）、リバランスの処理を終了する。
【０１４６】
上記ステップＳ１１の判定の結果、残りの移譲領域が移譲可能な移譲先ノードが有れば（Ｙｅｓ）、ステップＳ１２において、リバランス部１８ｅは、移譲元ノードの残りの移譲領域を、上記ステップＳ１０で存在が認められた移譲先ノードへ移譲する。
【０１４７】
この後、上記ステップＳ１０に戻って、リバランス部１８ｅは、処理が終了するまでステップＳ１０〜Ｓ１２を繰り返す。また、前述したように、ステップＳ６以降の処理は、移譲元ノード毎に繰り返される。
【０１４８】
上記の処理により、リバランス後の振分ＩＤ表１９ｂが作成され、各ノードに配付されることで、リバランシング後の振り分け処理が実行され、負荷の偏りが解消される。
【０１４９】
（実施の形態のまとめ）
以上、説明したように、本実施の形態により、通信サービスを利用する複数のクライアントマシンからの情報がネットワークを介して振り分けられる複数のノードを有する分散システムにおいて用いられるリバランス装置であって、前記複数のノードの負荷量に基づいて、当該複数のノード間の負荷量の偏りを抑制するリバランスが必要であるか否かを判定するリバランス処理手段と、前記リバランス処理手段により、リバランスが必要であると判定された場合において、前記リバランス後の前記複数のノードの予測負荷状態に基づいて、前記リバランスをキャンセルするか否かを判定するキャンセル処理手段とを備えるリバランス装置が提供される。当該リバランス装置は、前記複数のノードにおけるいずれかのノードであってもよいし、前記複数のノード以外の装置であってもよい。
【０１５０】
前記キャンセル処理手段は、例えば、前記リバランス処理手段によりリバランスが必要であると判定された第１の時点から、前記リバランス処理手段によるリバランス設計にかかる時間が経過した第２の時点における前記複数のノードの負荷量と、前記第１の時点における前記複数のノードの負荷量とに基づいて、前記予測負荷状態を算出する。
【０１５１】
また、例えば、前記予測負荷状態が、ノード数の増減を要する負荷状態であるか、又は、前記予測負荷状態が、許容範囲外の負荷量を持つ所定数のノードが存在する負荷状態である場合に、前記キャンセル処理手段は、前記リバランスをキャンセルすると判定する。
【０１５２】
また、前記キャンセル処理手段は、例えば、前記第１の時点において、当該第１の時点における前記複数のノードの負荷量の平均値からの差分をノード毎に算出し、前記第２の時点において、ノード毎に、当該第２の時点におけるノードの負荷量から前記差分を引くことにより、前記予測負荷状態を算出する。
【０１５３】
なお、分散システム負荷リバランス部１８ｅは、リバランス処理手段の例である。リバランシングキャンセル機能部１８ｆは、キャンセル処理手段の例である。
【０１５４】
本実施の形態に係る技術によれば、分散システムにおいて、時間経過の観点を含めてリバランスの実行が適切であるかを高速で判断し、実行すべきでない状況を特定することができる。よって、無駄なリバランスの実行を抑制できる。
【０１５５】
（第１項）
通信サービスを利用する複数のクライアントマシンからの情報がネットワークを介して振り分けられる複数のノードを有する分散システムにおいて用いられるリバランス装置であって、
前記複数のノードの負荷量に基づいて、当該複数のノード間の負荷量の偏りを抑制するリバランスが必要であるか否かを判定するリバランス処理手段と、
前記リバランス処理手段により、リバランスが必要であると判定された場合において、前記リバランス後の前記複数のノードの予測負荷状態に基づいて、前記リバランスをキャンセルするか否かを判定するキャンセル処理手段と
を備えることを特徴とするリバランス装置。
（第２項）
前記キャンセル処理手段は、
前記リバランス処理手段によりリバランスが必要であると判定された第１の時点から、前記リバランス処理手段によるリバランス設計にかかる時間が経過した第２の時点における前記複数のノードの負荷量と、前記第１の時点における前記複数のノードの負荷量とに基づいて、前記予測負荷状態を算出する
ことを特徴とする第１項に記載のリバランス装置。
（第３項）
前記予測負荷状態が、ノード数の増減を要する負荷状態であるか、又は、前記予測負荷状態が、許容範囲外の負荷量を持つ所定数のノードが存在する負荷状態である場合に、前記キャンセル処理手段は、前記リバランスをキャンセルすると判定する
ことを特徴とする第１項又は第２項に記載のリバランス装置。
（第４項）
前記キャンセル処理手段は、
前記第１の時点において、当該第１の時点における前記複数のノードの負荷量の平均値からの差分をノード毎に算出し、前記第２の時点において、ノード毎に、当該第２の時点におけるノードの負荷量から前記差分を引くことにより、前記予測負荷状態を算出する
ことを特徴とする第２項に記載のリバランス装置。
（第５項）
通信サービスを利用する複数のクライアントマシンからの情報がネットワークを介して振り分けられる複数のノードを有する分散システムにおいて用いられるリバランス装置が実行するリバランス方法であって、
前記複数のノードの負荷量に基づいて、当該複数のノード間の負荷量の偏りを抑制するリバランスが必要であるか否かを判定するリバランス判定ステップと、
前記リバランス判定ステップにより、リバランスが必要であると判定された場合において、前記リバランス後の前記複数のノードの予測負荷状態に基づいて、前記リバランスをキャンセルするか否かを判定するキャンセル判定ステップと
を備えることを特徴とするリバランス方法。
（第６項）
前記キャンセル判定ステップにおいて、前記リバランス装置は、
前記リバランス判定ステップによりリバランスが必要であると判定された第１の時点から、リバランス設計にかかる時間が経過した第２の時点における前記複数のノードの負荷量と、前記第１の時点における前記複数のノードの負荷量とに基づいて、前記予測負荷状態を算出する
ことを特徴とする第５項に記載のリバランス方法。
（第７項）
前記キャンセル判定ステップにおいて、前記予測負荷状態が、ノード数の増減を要する負荷状態であるか、又は、前記予測負荷状態が、許容範囲外の負荷量を持つ所定数のノードが存在する負荷状態である場合に、前記リバランス装置は、前記リバランスをキャンセルすると判定する
ことを特徴とする第５項又は第６項に記載のリバランス方法。
（第８項）
コンピュータを、第１項ないし第４項のうちいずれか１項に記載のリバランス装置における各手段として機能させるためのプログラム。
以上、本発明の実施例について詳述したが、本発明は斯かる特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形・変更が可能である。
【符号の説明】
【０１５６】
１０  分散システム
１１  クライアントマシン
１２  ネットワーク
１３  ロードバランサ
１４  クラスタ
１５  ノード
１８  制御部
１８ａ  ノード識別子管理部
１８ｂ  振分部
１８ｃ  信号処理部
１８ｄ  ノード負荷計測部
１８ｅ  分散システム負荷リバランス部
１８ｆ  リバランシングキャンセル機能部
１９  記憶部
１９ａ  ノード識別子管理表
１９ｂ  振分ＩＤ表
１９ｃ  データ
１９ｄ  ノード負荷計測データ
１９ｅ  分散システム負荷集計データ
１９ｆ  呼制御状態フラグ
１９ｇ  ノード毎負荷差分表、ノード毎予測負荷比較表
１９ｈ  前回測定データ
【図１】
0006433926.tif 000002
【図２】
0006433926.tif 000003
【図３】
0006433926.tif 000004
【図４】
0006433926.tif 000005
【図５】
0006433926.tif 000006
【図６】
0006433926.tif 000007
【図７】
0006433926.tif 000008
【図８】
0006433926.tif 000009
【図９】
0006433926.tif 000010
【図１０】
0006433926.tif 000011
【図１１】
0006433926.tif 000012
【図１２】
0006433926.tif 000013
【図１３】
0006433926.tif 000014
【図１４】
0006433926.tif 000015
【図１５】
0006433926.tif 000016
【図１６】
0006433926.tif 000017