(57)【要約】【課題】負荷分散を迅速に実行することを課題とする。【解決手段】振分装置は、コンシステントハッシュ空間が分割される領域ごとに、各領域を担当する各サーバを識別するサーバ識別子を対応付けた領域情報を記憶する。振分装置は、負荷が閾値以上である第１のサーバが検出された場合、領域情報にしたがって、第１のサーバが担当する担当領域を特定する。振分装置は、第１のサーバの担当領域に対応付けて第２のサーバのサーバ識別子を、領域情報に追加する。【選択図】図４
2017021722.tif 000002
【特許請求の範囲】
【請求項１】
コンシステントハッシュ空間が分割される領域ごとに、各領域を担当する各サーバを識別するサーバ識別子を対応付けた領域情報を記憶する領域記憶部と、
負荷が閾値以上である第１のサーバが検出された場合、前記領域情報にしたがって、前記第１のサーバが担当する担当領域を特定する特定部と、
前記第１のサーバの前記担当領域に対応付けて第２のサーバのサーバ識別子を、前記領域情報に追加する追加部と
を有することを特徴とする分散処理装置。
【請求項２】
前記領域記憶部は、前記サーバ識別子と、前記各サーバに割り当てられたノードを識別するノード識別子とを対応付けた、前記各サーバが担当する領域を特定する前記領域情報を記憶し、
前記追加部は、前記担当領域内に位置する前記ノードのノード識別子と、前記第２のサーバのサーバ識別子とを対応付けて、前記領域情報に追加することを特徴とする請求項１に記載の分散処理装置。
【請求項３】
前記領域ごとに、確立中のセッションを識別するセッション識別子と、該セッションを使用するノードのノード識別子とを対応付けて記憶するセッション記憶部をさらに有し、
前記追加部は、前記セッション記憶部を参照して、前記第１のサーバの担当領域内で確立中であるセッションのセッション識別子を特定し、特定したセッション識別子が含まれないように前記担当領域を分割する前記ノードのノード識別子と、前記第２のサーバのサーバ識別子とを対応付けて、前記領域情報に追加することを特徴とする請求項２に記載の分散処理装置。
【請求項４】
前記追加部は、前記確立中であるセッションのセッション識別子が含まれない領域が複数ある場合、最も広い領域に分割する前記ノードのノード識別子と、前記第２のサーバのサーバ識別子とを対応付けて、前記領域情報に追加することを特徴とする請求項３に記載の分散処理装置。
【請求項５】
前記第１のサーバの負荷が前記閾値未満になった場合、前記担当領域に対応付けられる第２のサーバのサーバ識別子を、前記領域情報から削除する削除部をさらに有することを特徴とする請求項１に記載の分散処理装置。
【請求項６】
コンピュータが、
負荷が閾値以上である第１のサーバが検出された場合、コンシステントハッシュ空間が分割される領域ごとに、各領域を担当する各サーバを識別するサーバ識別子を対応付けた領域情報にしたがって、第１のサーバが担当する担当領域を特定し、
前記第１のサーバの前記担当領域に対応付けて第２のサーバのサーバ識別子を、前記領域情報に追加する
処理を実行することを特徴とする分散処理方法。
【請求項７】
コンピュータに、
負荷が閾値以上である第１のサーバが検出された場合、コンシステントハッシュ空間が分割される領域ごとに、各領域を担当する各サーバを識別するサーバ識別子を対応付けた領域情報にしたがって、第１のサーバが担当する担当領域を特定し、
前記第１のサーバの前記担当領域に対応付けて第２のサーバのサーバ識別子を、前記領域情報に追加する
処理を実行させることを特徴とする分散処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散処理装置、分散処理方法および分散処理プログラムに関する。
【背景技術】
【０００２】
従来から、ネットワークの分散処理技術において、コンシステントハッシュ法などのハッシュ法を用いた信号の振り分け手法が知られている。コンシステントハッシュ法を用いた信号の振り分け手法では、各サーバに任意のID（以降、ノードIDと記載する場合がある）を事前に割り当てて、コンシステントハッシュ空間上にマッピングする。そして、コンシステントハッシュ空間上で、反時計回りに隣接するサーバのノードIDとの間の領域を各サーバの担当領域として定める。
【０００３】
振分サーバは、信号を受信した場合、信号から抽出したキーとハッシュ関数とを用いてハッシュ値を算出し、ハッシュ値をコンシステントハッシュ空間上にマップさせる。そして、振分サーバは、算出したハッシュ値を担当領域に持つサーバに、受信した信号を振り分ける。その後、振分サーバは、後続の信号にも同じキーを埋め込むことにより、同一セッションの信号を同じサーバに振り分ける。
【０００４】
また、コンシステントハッシュ空間上のサーバが削除された場合、削除対象のサーバが管理するデータは、削除対象のサーバから時計回りの位置に位置する隣接する特定サーバが担当する事になり、特定サーバの負荷が集中する。このような場合の対策として、コンシステントハッシュ法を用いる際に、サーバ１台につき複数の仮想的なID（以降、仮想ノードIDと記載する場合がある）を事前に割り当てて更に細かい領域分割を行うことにより、負荷集中の影響を局所化する手法が知られている。
【０００５】
近年では、振分サーバが各サーバの負荷状況を計算し、負荷が閾値を超えると検出されたサーバが、担当領域のデータを、負荷が閾値以下であるサーバの仮想ノードIDに移動させることで、負荷分散を実行する技術が知られている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特開２０１２−４８４２４号公報
【特許文献２】特開２０１２−２３８０８４号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかしながら、上記技術では、既に負荷が閾値を超えるサーバが、負荷の小さいサーバにデータを移動させる処理を実行するので、データの移動処理でさらに負荷がかかり、負荷分散が完了するまでに時間かかる。また、急激なトラフィック増加が発生する環境においては、データの移動処理が間に合わず、サーバが提供するサービスが停止するなどの影響が発生する場合もある。
【０００８】
１つの側面では、負荷分散を迅速に実行することができる分散処理装置、分散処理方法および分散処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
第１の案では、分散処理装置は、コンシステントハッシュ空間が分割される領域ごとに、各領域を担当する各サーバを識別するサーバ識別子を対応付けた領域情報を記憶する領域記憶部を有する。分散処理装置は、負荷が閾値以上である第１のサーバが検出された場合、前記領域情報にしたがって、前記第１のサーバが担当する担当領域を特定する特定部を有する。分散処理装置は、前記第１のサーバの前記担当領域に対応付けて第２のサーバのサーバ識別子を、前記領域情報に追加する追加部を有する。
【発明の効果】
【００１０】
一実施形態によれば、負荷分散を迅速に実行することができる。
【図面の簡単な説明】
【００１１】
【図１】図１は、実施例１にかかるシステムの全体構成例を示す図である。
【図２】図２は、実施例１にかかるシステムを構成する物理サーバの階層構造を説明する図である。
【図３】図３は、実施例１にかかるコンシステントハッシュ空間を説明する図である。
【図４】図４は、実施例１にかかるシステムの機能構成を示す機能ブロック図である。
【図５】図５は、仮想ノードＩＤテーブルに記憶される情報の例を示す図である。
【図６】図６は、サーバ管理テーブルに記憶される情報の例を示す図である。
【図７】図７は、救済管理テーブルに記憶される情報の例を示す図である。
【図８】図８は、領域算出用テーブルに記憶される情報の例を示す図である。
【図９】図９は、救済領域の具体例を説明する図である。
【図１０】図１０は、サーバ３の負荷集中と救済領域の特定例を示す図である。
【図１１】図１１は、サーバ３のエリア３−２の救済例を説明する図である。
【図１２】図１２は、サーバ３のエリア３−１の救済例を説明する図である。
【図１３】図１３は、サーバ３の救済時の振分例を説明する図である。
【図１４】図１４は、サーバ３のエリア３−１の救済解除例を説明する図である。
【図１５】図１５は、サーバ３のエリア３−２の部分的な救済解除例を説明する図である。
【図１６】図１６は、サーバ３のエリア３−２の全面解除例を説明する図である。
【図１７】図１７は、一連の処理の流れを示すシーケンス図である。
【図１８】図１８は、救済処理の流れを示すフローチャートである。
【図１９】図１９は、領域判定処理の流れを示すフローチャートである。
【図２０】図２０は、信号振分処理の流れを示すフローチャートである。
【図２１】図２１は、負荷解消時の救済解放処理の流れを示すフローチャートである。
【図２２】図２２は、呼解放時の救済解放処理の流れを示すフローチャートである。
【図２３】図２３は、解放領域判定処理の流れを示すフローチャートである。
【図２４】図２４は、ハードウェア構成例を示す図である。
【発明を実施するための形態】
【００１２】
以下に、本願の開示する分散処理装置、分散処理方法および分散処理プログラムの実施例を図面に基づいて詳細に説明する。なお、この実施例によりこの発明が限定されるものではない。
【実施例１】
【００１３】
［全体構成］
図１は、実施例１にかかるシステムの全体構成例を示す図である。図１に示すように、このシステムは、振分装置１０とサーバ１〜サーバ４を有する分散処理システムである。この分散処理システムは、仮想マシンで実現することができる。例えば、１台の物理サーバ上で実現することもでき、複数の物理マシン上で実現することもできる。
【００１４】
このシステムでは、一例として、ＳＩＰ（Session  Initiation  Protocol）などの呼信号の制御について説明する。具体的には、振分装置１０は、クライアント装置から呼信号を受信し、いずれかのサーバに振り分ける。振り分けられたサーバは、呼信号に対して各種処理を実行する。なお、各種処理としては、音声通信の確立や切断などが挙げられる。
【００１５】
ここで、仮想マシンを実行する物理サーバについて説明する。図２は、実施例１にかかるシステムを構成する物理サーバの階層構造を説明する図である。図２に示すように、物理サーバは、ハードウェア１１、ＯＳ１２、ＨＶ１３、ＶＭ（Virtual  Machine）１４を有する。ＯＳ１２、ＨＶ１３およびＶＭ１４は、物理サーバのハードウェア１１によって、実行されるソフトウェアである。
【００１６】
ハードウェア１１の構成については後述する。ＯＳ１２は、ハードウェア１１を制御するオペレーティングシステム（Operating  System）である。ＨＶ１３は、ＯＳ１２上で実行されるハイパーバイザのプログラムである。例えば、ＨＶ１３は、ハードウェア１１に含まれるメモリの領域を仮想的に割り当てた仮想メモリやハードウェア１１に含まれるプロセッサを仮想的に割り当てた仮想プロセッサなどを用いて、ＶＭ１４ａからＶＭ１４ｅを実行する。
【００１７】
ＶＭ１４ａからＶＭ１４ｅは、ＨＶ１３によって生成、管理される仮想マシン・プログラムである。図１の例では、これらのＶＭによって、振分装置１０およびサーバ１からサーバ４が実現される。なお、振分装置１０およびサーバ１からサーバ４は、物理サーバで実現することもできる。
【００１８】
図１に示したシステムは、コンシステントハッシュ法を用いた分散処理システムである。具体的には、このシステムは、各サーバに仮想サーバＩＤを割り当ててコンシステントハッシュ空間上にマップさせる。そして、コンシステントハッシュ空間上で、反時計回りに隣接するサーバの仮想ノードＩＤとの間の領域を各サーバの担当領域として定める。
【００１９】
ここで、８ビットのハッシュ空間を例にして説明する。図３は、実施例１にかかるコンシステントハッシュ空間を説明する図である。図３に示すように、サーバ１には仮想ノードＩＤ（ハッシュ値）として「０」と「１２８」が割与えられ、サーバ２には仮想ノードＩＤとして「６４」と「１９２」が割与えられ、サーバ３には仮想ノードＩＤとして「３２」と「２２４」が割与えられ、サーバ４には仮想ノードＩＤとして「９６」と「１６０」が割与えられる。なお、各サーバに割与えられる仮想ノードＩＤは、管理者等が設定してもよく、使用する既存のハッシュ関数などで指定することもできる。
【００２０】
そして、割与えた仮想ノードＩＤの若番の順で時計回りに配置し、仮想ノードＩＤで囲まれた領域を各サーバに担当領域として割り当てる。具体的には、図３に示すように、仮想ノードＩＤ＝０（サーバ１）、仮想ノードＩＤ＝３２（サーバ３）、仮想ノードＩＤ＝６４（サーバ２）、仮想ノードＩＤ＝９６（サーバ４）、仮想ノードＩＤ＝１２８（サーバ１）、仮想ノードＩＤ＝１６０（サーバ４）、仮想ノードＩＤ＝１９２（サーバ２）、仮想ノードＩＤ＝２２４（サーバ３）の順で円状に配置する。
【００２１】
この結果、仮想ノードＩＤが１から３２までの領域をサーバ３が担当し、仮想ノードＩＤが３３から６４までの領域をサーバ２が担当し、仮想ノードＩＤが６５から９６までの領域をサーバ４が担当し、仮想ノードＩＤが９７から１２８までの領域をサーバ１が担当する。同様に、仮想ノードＩＤが１２９から１６０までの領域をサーバ４が担当し、仮想ノードＩＤが１６１から１９２までの領域をサーバ２が担当し、仮想ノードＩＤが１９３から２２４までの領域をサーバ３が担当し、仮想ノードＩＤが２２５から２５６（０）までの領域をサーバ１が担当する。ここで、本実施例では、各領域を「エリア＋サーバ名＋登場順」で記載する。例えば、仮想ノードＩＤが１から３２までの静的な領域は、サーバ３が担当する領域の１番目であることから「エリア３−１」と記載し、仮想ノードＩＤが１９３から２２４までの領域は、サーバ３が担当する領域の２番目であることから「エリア３−２」と記載する。
【００２２】
そして、振分装置１０は、クライアント装置からＳＩＰ信号を受信すると、ＳＩＰ信号から識別子（以降、キーと記載する場合がある）を抽出し、識別子を所定のハッシュ関数に代入してハッシュ値を算出する。その後、振分装置１０は、算出したハッシュ値を図３のコンシステントハッシュ空間にマッピングし、マッピングした領域を担当するサーバに受信したＳＩＰ信号を送信する。例えば、振分装置１０は、ハッシュ値が２２０であった場合、エリア３−２にマッピングして、当該領域を担当するサーバ３にＳＩＰ信号を送信する。
【００２３】
上述したシステムにおいて、振分装置１０は、コンシステントハッシュ空間が分割される領域ごとに、各領域を担当する各サーバを識別するサーバ識別子を対応付けた領域情報を記憶する。そして、振分装置１０は、負荷が閾値以上である第１のサーバが検出された場合、領域情報にしたがって、第１のサーバが担当する担当領域を特定する。その後、振分装置１０は、第１のサーバの担当領域に対応付けて第２のサーバのサーバ識別子を、領域情報に追加する。
【００２４】
つまり、振分装置１０は、コンシステントハッシュ空間にサーバの仮想ノードＩＤを割当てる際に、負荷が閾値以上の被救済サーバの担当領域に救済サーバの仮想ノードＩＤを追加する。この結果、振分装置１０は、救済時にサーバ間のデータ移動を抑制し、迅速に負荷分散を実行することができる。
【００２５】
［機能構成］
次に、図４を用いて図１に示した各装置の機能構成ついて説明する。図４は、実施例１にかかるシステムの機能構成を示す機能ブロック図である。なお、サーバ１からサーバ４は、同様の機能を有するので、ここではサーバ１について説明する。
【００２６】
（サーバの機能構成）
図４に示すように、サーバ１は、リソース収集部１ａとセッション管理部１ｂを有する。なお、リソース収集部１ａやセッション管理部１ｂは、サーバ１に割当てられた仮想プロセッサによって実行されるプロセスなどの一例である。
【００２７】
リソース収集部１ａは、サーバ１のリソース状況を収集する処理部である。例えば、リソース収集部１ａは、サーバ１の仮想プロセッサの使用率、仮想メモリの使用率などを収集する。また、リソース収集部１ａは、定期的にリソースを収集して振分装置１０に送信することもでき、振分装置１０から要求を受信した場合にリソースを収集して送信することもできる。
【００２８】
セッション管理部１ｂは、サーバ１内で確立中のセッションを管理する処理部である。例えば、セッション管理部１ｂは、サーバ１に割当てられた仮想ノードＩＤの利用状況を監視し、呼接続が確立されている仮想ノードＩＤを管理する。そして、セッション管理部１ｂは、振分装置１０から要求を受付けた場合に、確立中のセッション情報、すなわち呼接続が実行されている仮想ノードＩＤ等を応答する。
【００２９】
（振分装置の機能構成）
図４に示すように、振分装置１０は、記憶部２０と制御部３０とを有するロードバランサの一例である。なお、記憶部２０は、仮想メモリなどの記憶装置の一例であり、制御部３０は、仮想プロセッサなどのプロセッサの一例である。
【００３０】
記憶部２０は、仮想ノードＩＤテーブル２１、サーバ管理テーブル２２、救済管理テーブル２３、領域算出用テーブル２４を有する。
【００３１】
仮想ノードＩＤテーブル２１は、各サーバが持つ仮想ノードＩＤをハッシュ値の昇順でソートして管理するテーブルである。図５は、仮想ノードＩＤテーブルに記憶される情報の例を示す図である。図５に示すように、仮想ノードＩＤテーブル２１は、「Ｋｅｙ、Ｖａｌｕｅ」を対応付けて記憶し、「Ｋｅｙ」には「仮想ノードＩＤ」が記憶され、「Ｖａｌｕｅ」には「仮想ノードＩＤ種別、担当サーバＩＤ、救済領域管理表」が記憶される。
【００３２】
ここで記憶される「仮想ノードＩＤ」は、各サーバに静的に割与えられたハッシュ値である。なお、図５では一例として「nodeId1」などと記載しているが、実際には、図３等で説明した仮想ノードＩＤの「１」や「２２４」や「２２０」などが格納される。
【００３３】
「仮想ノードＩＤ種別」は、Ｋｅｙに設定される仮想ノードＩＤの種別を特定する情報である。例えば、サーバをシステムに組み込んだ時に静的に割り当てられる仮想ノードＩＤ（以降、通常ノードＩＤと記載する場合がある）には「通常」が設定される。負荷が高いサーバを救済する救済サーバが救済領域を借りるために追加で割り当てる仮想ノードＩＤ（以降、救済ノードＩＤと記載する場合がある）には「救済」が設定される。救済ノードＩＤを割り当てる過程において、既存セッションのデータ移動を回避するために追加で割り当てた被救済サーバ自身の仮想ノードＩＤ（以降、自救済ノードＩＤと記載する場合がある）には「自救済」が設定される。なお、仮想ノードＩＤ種別が異なる同一ハッシュ値は重複を許容して保持される。
【００３４】
「担当サーバＩＤ」は、仮想ノードＩＤが割り当てられたサーバのＩＤである。なお、図５では一例として「サーバ１」などと記載しているが、実際には、図３等で説明したサーバＩＤの「１」から「４」のいずれかが格納される。「救済領域管理表」は、領域ごとに設けられた救済管理テーブル２３へのポインタである。
【００３５】
図５の例では、負荷が高い被救済サーバを救済するために、救済サーバであるサーバ４（サーバ４）の仮想ノードＩＤである「nodeId4」（仮想ノードＩＤ＝４）が追加されたことを示している。また、この仮想ノードＩＤの追加によって、エリア４−２がサーバ４の担当領域になったことを示している。
【００３６】
サーバ管理テーブル２２は、サーバ毎の通常ノードＩＤを管理するテーブルである。図６は、サーバ管理テーブルに記憶される情報の例を示す図である。図６に示すように、サーバ管理テーブル２２は、「Ｋｅｙ、Ｖａｌｕｅ」を対応付けて記憶し、「Ｋｅｙ」には「サーバＩＤ」が記憶され、「Ｖａｌｕｅ」には「仮想ノードＩＤリスト、救済サーバＩＤリスト、救済ノードＩＤリスト」が記憶される。
【００３７】
ここで記憶される「サーバＩＤ」は、各サーバに静的に割与えられた識別子である。なお、図６では「サーバ１」などと記載しているが、実際には、図３等で説明したサーバＩＤの「１」から「４」のいずれかが格納される。「仮想ノードＩＤリスト」は、各サーバに割当てられた仮想ノードＩＤの一覧である。なお、図６では一例として「nodeId1」などと記載しているが、実際には、図３等で説明した仮想ノードＩＤの「２２４」が格納される。
【００３８】
「救済サーバＩＤリスト」は、自装置が被救済サーバであり、どの装置によって救済されているかを示す情報であり、救済サーバのサーバＩＤが設定される。「救済ノードＩＤリスト」は、自装置が救済サーバであり、どの被救済サーバを救済しているかを示す情報であり、被救済サーバのサーバＩＤが設定される。
【００３９】
図６の例では、サーバ３に仮想ノードＩＤとして「１」（nodeId1）と「３」（nodeId3）が割り当てられており、サーバ４に救済されていることを示す。また、サーバ４に仮想ノードＩＤとして「７」（nodeId7）が割り当てられており、仮想ノードＩＤの「２」と「４」をサーバ３の担当領域に追加して、サーバ３を救済していることを示す。なお、救済処理が行われる場合は、被救済サーバとなるサーバには対応する救済サーバＩＤのリストが管理される。１台の被救済サーバに対し複数の救済サーバが救済する事も可能である。救済サーバとなるサーバでは、救済対象となる被救済サーバ毎に救済ノードＩＤのリストが管理される。1台の救済サーバが複数の被救済サーバを救済する事も可能である。
【００４０】
救済管理テーブル２３は、救済対象の領域ごとに管理するテーブルであり、救済期間中のみ管理されるデータで、救済領域における信号から抽出されたキーのハッシュ値を昇順のソートで管理するテーブルである。図７は、救済管理テーブルに記憶される情報の例を示す図である。図７は、サーバ４の担当領域であるエリア４−２を例示している。図７に示すように、救済管理テーブル２３は、「Ｖａｌｕｅ」として「セッションＩＤ」を記憶する。この「セッションＩＤ」には、呼接続が実行されている仮想ノードＩＤが設定される。なお、図７の例では、「sessionId1」などを記載されているが、実際には、図３等で説明した仮想ノードＩＤの「２２０」などが格納される。
【００４１】
図７の例では、エリア４−２には、「sessionId1」から「sessionId5」のセッションが存在することを示している。なお、仮想ノード（ハッシュ値）は重複する可能性が有るため、実際には例えばユニークに定義されるセッションＩＤ（sessionId1）等の付加情報と共に管理し、セッションをユニークに特定できるデータ構造とする。
【００４２】
領域算出用テーブル２４は、救済領域を算出するために特定サーバに負荷偏りが発生した時にだけ一時的に生成されるテーブルである。図８は、領域算出用テーブルに記憶される情報の例を示す図である。図８に示すように、領域算出用テーブル２４は、「領域候補領域ＩＤ、救済候補領域長」を対応付けて記憶する。
【００４３】
ここで記憶される「領域候補領域ＩＤ」は、救済対象となる仮想ノードＩＤを記憶し、「救済候補領域長」は、領域候補領域ＩＤによって特定される仮想ノードＩＤによって救済対象となる領域の長さ（大きさ）を示す情報である。図８は、サーバ４の担当領域であるエリア４−２を例示している。図８の例では、「regionId1」の長さが「length1」であり、「regionId2」の長さが「length2」であり、「regionId3」の長さが「length3」であることを示している。
【００４４】
制御部３０は、振分装置１０全体の処理を司る処理部であり、振分処理部３１、負荷監視部３２、救済制御部３３、救済解除部３４を有する。なお、振分処理部３１、負荷監視部３２、救済制御部３３、救済解除部３４は、仮想プロセッサに実行されるプロセスなどの一例である。
【００４５】
振分処理部３１は、クライアント装置から受信したＳＩＰ信号をいずれかのサーバに振り分ける処理部である。具体的には、振分処理部３１は、ＳＩＰ信号からキーを抽出し、キーを所定のハッシュ関数に代入して仮想ノードＩＤ（ハッシュ値）を算出する。その後、振分処理部３１は、算出した仮想ノードＩＤを図３のコンシステントハッシュ空間にマッピングし、マッピングした領域を担当するサーバに受信したＳＩＰ信号を送信する。また、振分処理部３１は、後続のＳＩＰ信号にも同じ仮想ノードＩＤを埋め込むことにより、同一セッションの信号を同じサーバに振り分ける。
【００４６】
負荷監視部３２は、コンシステントハッシュ空間を形成する各サーバの負荷を定期的に監視する処理部である。具体的には、負荷監視部３２は、サーバ１からサーバ４のそれぞれから、仮想プロセッサや仮想メモリなどの負荷情報を定期的に取得する。そして、負荷監視部３２は、閾値を超える負荷のサーバを検出すると、負荷分散を救済制御部３３に要求する。例えば、負荷監視部３２は、サーバ３のプロセッサ使用率が閾値である８５％を超えたことを検出すると、被救済候補としてサーバ３を特定する情報（例えば、サーバＩＤなど）を被救済候補に送信する。
【００４７】
救済制御部３３は、負荷が高いサーバ（被救済サーバ）の担当領域の一部を、負荷が小さいサーバ（救済サーバ）に割当てることで、負荷分散を実行する処理部である。具体的には、救済制御部３３は、負荷監視部３２から負荷が高いサーバが通知されると、（１）セッション情報の取得、（２）救済領域の特定、（３）救済領域の割当を実行する。
【００４８】
（１）セッション情報の取得
例えば、救済制御部３３は、サーバ３の負荷が高いことが検出されると、負荷監視部３２から各サーバの負荷情報を取得して、最も負荷が低いサーバを特定する。ここで、救済制御部３３は、サーバ３を被救済サーバ、サーバ４を救済サーバと決定する。そして、救済制御部３３は、被救済サーバ３から、サーバ３の各担当領域のセッション情報を取得する。そして、救済制御部３３は、取得した各領域のセッション情報を用いて、領域ごとに救済管理テーブル２３を生成する。
【００４９】
（２）救済領域の特定
続いて、救済制御部３３は、被救済サーバであるサーバ３の各担当領域について、既存のセッションを除くように領域を分割し、分割した各領域の長さを算出して、領域算出用テーブル２４を生成する。そして、救済制御部３３は、分割した各領域のうち、最も長い領域を救済対象領域と決定する。
【００５０】
ここで救済対象の領域を特定する具体例を説明する。図９は、救済領域の具体例を説明する図である。なお、救済領域長の閾値を１５とする。図９に示す領域は、仮想ノードＩＤが「１９３」から「２２４」までを担当するサーバ３のエリア３−２である。このエリア３−２では、既存セッションとして、仮想ノード（regionId）＝２１０、２２０、２２４の３つのセッションが存在している。
【００５１】
そして、救済制御部３３は、各セッションに分割される領域の長さを算出する。例えば、救済制御部３３は、仮想ノードＩＤ＝１９２から仮想ノードＩＤ＝２１０までの救済候補領域の長さを１８、仮想ノードＩＤ＝２１０から仮想ノードＩＤ＝２２０までの救済候補領域の長さを１０、仮想ノードＩＤ＝２２０から仮想ノードＩＤ＝２２４までの救済候補領域の長さ４と算出する。そして、救済制御部３３は、ここで算出した情報を用いて、救済管理テーブル２３を生成する。
【００５２】
その後、救済制御部３３は、各救済候補領域のうち、最も長くかつ閾値（１５）以上の領域として、仮想ノードＩＤ＝１９２から仮想ノードＩＤ＝２１０までの救済候補領域を、救済領域に決定する。
【００５３】
（３）救済領域の割当
続いて、救済制御部３３は、救済領域に対して、救済サーバのサーバＩＤを追加することで、救済領域に存在する各仮想ノードＩＤの担当を、救済サーバに割当てる。具体的には、救済制御部３３は、救済領域が先頭要素である場合、つまり担当領域の先頭の仮想ノードＩＤが救済領域に含まれる場合、救済領域の末尾にあるセッションの一つ前の仮想ノードＩＤに救済サーバのサーバＩＤを追加する。また、救済制御部３３は、救済領域の先頭要素に対応する仮想ノードＩＤに被救済サーバのサーバＩＤを追加する。
【００５４】
また、救済制御部３３は、救済領域が末尾要素である場合、つまり担当領域の最後の仮想ノードＩＤが救済領域に含まれる場合、救済領域の先頭にあるセッションの一つ後の仮想ノードＩＤと、救済領域の末尾要素である仮想ノードＩＤとに救済サーバのサーバＩＤを追加する。さらに、救済制御部３３は、救済領域の先頭にあるセッションに対応する仮想ノードＩＤに被救済サーバのサーバＩＤを追加する。
【００５５】
また、救済制御部３３は、救済領域が中間要素である場合、つまり既存セッションに囲まれた領域が救済領域である場合、救済領域の先頭にあるセッションに対応する仮想ノードＩＤに被救済サーバのサーバＩＤを追加し、救済領域の末尾にあるセッションの一つ前の仮想ノードＩＤに救済サーバのサーバＩＤを追加する。
【００５６】
図９の例で具体的に説明する。例えば、仮想ノードＩＤ＝１９２から仮想ノードＩＤ＝２１０までの救済候補領域が救済領域に決定されたとする。この場合、救済制御部３３は、救済領域が先頭要素であることから、対象領域の末尾にあるセッション（２１０）の一つ前の仮想ノードＩＤ（２０９）の位置に救済サーバのサーバＩＤ（４）を配置する。そして、救済制御部３３は、対象領域の先頭要素である仮想ノードＩＤ（１９２）の位置に被救済サーバのサーバＩＤ（３）を配置する。この結果、セッション（２１０）はサーバ３が担当したまま、仮想ノードＩＤ＝１９３から仮想ノードＩＤ＝２０９までをサーバ４が担当することとなる。
【００５７】
また、仮想ノードＩＤ＝２２０から仮想ノードＩＤ＝２２４までの救済候補領域が救済領域に決定されたとする。この場合、救済制御部３３は、救済領域が末尾要素であることから、対象領域の先頭にあるセッション（２２０）の一つ後の仮想ノードＩＤ（２２１）の位置に救済サーバのサーバＩＤ（４）を配置する。さらに、救済制御部３３は、救済領域の末尾要素である仮想ノードＩＤに救済サーバのサーバＩＤを追加するが、末尾要素の仮想ノードＩＤ（２２４）もセッションが存在することから、セッション（２２４）の一つ前の仮想ノードＩＤ（２２３）の位置に救済サーバのサーバＩＤ（４）を配置する。そして、救済制御部３３は、対象領域の先頭にあるセッション（２２０）に対応する仮想ノードＩＤの位置に被救済サーバのサーバＩＤ（３）を配置する。この結果、セッション（２２０）およびセッション（２２４）はサーバ３が担当したまま、仮想ノードＩＤ＝２２１から仮想ノードＩＤ＝２２３までをサーバ４が担当することとなる。
【００５８】
また、仮想ノードＩＤ＝２１０から仮想ノードＩＤ＝２２０までの救済候補領域が救済領域に決定されたとする。この場合、救済制御部３３は、救済領域が中間要素であることから、対象領域の先頭にあるセッション（２１０）に対応する仮想ノードの位置に被救済サーバのサーバＩＤ（３）を配置し、対象領域の末尾にあるセッション（２２０）の一つ前の仮想ノードＩＤ（２１９）の位置に救済サーバのサーバＩＤ（４）を配置する。この結果、セッション（２１０）およびセッション（２２０）はサーバ３が担当したまま、仮想ノードＩＤ＝２１１から仮想ノードＩＤ＝２１９までをサーバ４が担当することとなる。
【００５９】
救済解除部３４は、被救済サーバの負荷が閾値を下回った場合、または、セッションが解放された場合、救済領域を解放する処理部である。例えば、救済解除部３４は、被救済サーバであるサーバ３のプロセッサの使用率が閾値を下回った場合負荷分散するためにコンシステントハッシュ空間に配置した救済サーバや被救済サーバのサーバＩＤを削除して、元の状態に戻す。
【００６０】
また、救済解除部３４は、既存のセッションが解放されるたびに、救済領域を狭めることで、救済領域を徐々に解放することもできる。図９の例において、仮想ノードＩＤ＝１９２から仮想ノードＩＤ＝２１０までが救済領域に決定されたとする。つまり、仮想ノードＩＤ＝１９３から仮想ノードＩＤ＝２０９までをサーバ４が救済しているとする。
【００６１】
そして、救済している状態において、救済領域内の仮想ノードＩＤ＝２００と仮想ノードＩＤ＝２０５とに新たなセッションが発生する。この場合、これらのセッションは、サーバ４によって処理される。その後、セッション（仮想ノードＩＤ＝２０５）が解放されると、救済解除部３４は、対象領域の末尾にあるセッション（２１０）の一つ前の仮想ノードＩＤ（２０９）の位置に配置されたサーバＩＤ（４）を削除する。続いて、救済解除部３４は、残っているセッション（２００）に対応する仮想ノードＩＤの位置にサーバＩＤ（４）を配置する。この結果、仮想ノードＩＤ＝１９２から仮想ノードＩＤ＝２１０までの救済領域が、仮想ノードＩＤ＝１９２から仮想ノードＩＤ＝２００までに変更される。この結果、救済解除部３４は、セッションの解放に伴って、救済領域を順次解放することができる。
【００６２】
［具体例］
次に、図１０から図１６を用いて、救済領域の作成および解放や、テーブルの変化について具体的に説明する。ここでは、サーバ３が被救済サーバ、サーバ４が救済サーバとする。また、仮想ノードＩＤについても、仮想ノードＩＤ＝３を仮想ノードＩＤ（３）と記載する。また、救済の解放については、セッションの終了を例にして説明する。
【００６３】
（前提条件）
図１０は、サーバ３の負荷集中と救済領域の特定例を示す図である。図１０に示すコンシステントハッシュ空間は、図３で説明したコンシステントハッシュ空間と同様とする。仮想ノードＩＤテーブル２１には、仮想ノードＩＤと担当サーバＩＤとの対応付けが記憶される。なお、対応付けは、図３と同様なので省略するが、この対応付けは、コンシステントハッシュ空間の設定時に決定される静的な情報であることから、各仮想ノードＩＤの「仮想ノードＩＤ種別」には、「通常」が設定されている。また、初期値としては、救済領域管理表には何も設定されていない。
【００６４】
また、サーバ管理テーブル２２には、各サーバに対応付けられる通常ノードＩＤリストが記憶される。なお、この対応付けは、図３と同様なので省略する。また、まだ救済が始まっていない初期値の段階では、救済サーバＩＤリストにも救済ノードＩＤリストにも何も設定されていない。
【００６５】
（救済領域の特定）
このような状態からサーバ３の負荷が上昇したとする。すると、救済制御部３３は、各テーブルからサーバ３の担当領域としてエリア３−１とエリア３−２とを特定する。また、救済制御部３３は、サーバ３から確立中のセッションの情報として、仮想ノードＩＤ（５）、（３０）、（３２）、（２１０）、（２２０）、（２２４）を取得する。この結果、救済制御部３３は、エリア３−１の救済管理テーブル２３に仮想ノードＩＤ（５）、（３０）、（３２）を格納し、エリア３−２の救済管理テーブル２３に仮想ノードＩＤ（２１０）、（２２０）、（２２４）を格納する。
【００６６】
続いて、救済制御部３３は、エリア３−１について、仮想ノードＩＤ（０）、（５）、（３０）、（３２）の領域候補の長さを算出する。具体的には、救済制御部３３は、仮想ノードＩＤ（０）から（５）までの長さを５、仮想ノードＩＤ（５）から（３０）までの長さを２５、仮想ノードＩＤ（３０）から（３２）までの長さを２と算出し、これらを救済管理テーブル２３に格納する。そして、救済制御部３３は、閾値（１５）以上である仮想ノードＩＤ（５）から（３０）までの領域を救済対象に決定する。
【００６７】
同様に、救済制御部３３は、エリア３−２について、仮想ノードＩＤ（１９２）、（２１０）、（２２０）、（２２４）の領域候補の長さを算出する。具体的には、救済制御部３３は、仮想ノードＩＤ（１９２）から（２１０）までの長さを１８、仮想ノードＩＤ（２１０）から（２２０）までの長さを１０、仮想ノードＩＤ（２２０）から（２２４）までの長さを４と算出し、これらを救済管理テーブル２３に格納する。そして、救済制御部３３は、閾値（１５）以上である仮想ノードＩＤ（１９２）から（２１０）までの領域を救済対象に決定する。
【００６８】
（エリア３−２の救済）
次に、エリア３−２を救済して負荷を分散させる例を説明する。図１１は、サーバ３のエリア３−２の救済例を説明する図である。図１１の上図に示すように、救済制御部３３は、救済対象の仮想ノードＩＤ（１９２）から（２１０）までの領域が先頭要素であることを特定する。すると、救済制御部３３は、対象領域の末尾にあるセッション（２１０）の一つ前の仮想ノードＩＤ（２０９）の位置に救済サーバのサーバＩＤ（４）を配置する。また、救済制御部３３は、対象領域の先頭要素である仮想ノードＩＤ（１９２）の位置に被救済サーバのサーバＩＤ（３）を配置する。
【００６９】
つまり、図１１の下図に示すように、救済制御部３３は、仮想ノードＩＤテーブル２１に「仮想ノードＩＤ＝２０９、サーバ４」を対応付けて記憶する。また、救済制御部３３は、サーバ４が救済サーバであることから、仮想ノードＩＤ（２０９）に対応付けられる「仮想ノードＩＤ種別」に「救済」を設定する。また、救済制御部３３は、サーバ４の担当領域がすでに２つ存在し、エリア３−２の一部を救済することで担当領域が３つになることから、仮想ノードＩＤ（２０９）に対応付けられる「救済領域管理表」に「エリア４−３」を対応付ける。そして、救済制御部３３は、救済管理テーブル２３にエリア４−３のテーブルを生成する。
【００７０】
さらに、救済制御部３３は、仮想ノードＩＤテーブル２１に「仮想ノードＩＤ＝１９２、サーバ３」を対応付けて記憶する。また、救済制御部３３は、サーバ３が被救済サーバであることから、仮想ノードＩＤ（１９２）に対応付けられる「仮想ノードＩＤ種別」に「自救済」を設定する。
【００７１】
続いて、救済制御部３３は、サーバ３がサーバ４に救済されていることから、サーバ管理ＩＤテーブル２２のサーバ３の「救済サーバＩＤリスト」に「サーバ４」を追加する。さらに、サーバ４が仮想ノードＩＤ（２０９）を新たな管理対象としたことから、サーバ管理ＩＤテーブル２２のサーバ４の「救済ノードＩＤリスト」に「２０９」を追加する。このようにして、救済制御部３３は、エリア３−２において仮想ノードＩＤ（１９３）から（２０９）をサーバ４に割り振ることで、負荷分散を実現する。
【００７２】
（エリア３−１の救済）
次に、エリア３−１を救済して負荷を分散させる例を説明する。図１２は、サーバ３のエリア３−１の救済例を説明する図である。図１２の上図に示すように、救済制御部３３は、救済対象の仮想ノードＩＤ（５）から（３０）までの領域が中間要素であることを特定する。すると、救済制御部３３は、対象領域の先頭にあるセッション（５）に対応する仮想ノードの位置に被救済サーバのサーバＩＤ（３）を配置し、対象領域の末尾にあるセッション（３０）の一つ前の仮想ノードＩＤ（２９）の位置に救済サーバのサーバＩＤ（４）を配置する。
【００７３】
つまり、図１２の下図に示すように、救済制御部３３は、仮想ノードＩＤテーブル２１に「仮想ノードＩＤ＝２９、サーバ４」を対応付けて記憶する。また、救済制御部３３は、サーバ４が救済サーバであることから、仮想ノードＩＤ（２９）に対応付けられる「仮想ノードＩＤ種別」に「救済」を設定する。また、救済制御部３３は、サーバ４の担当領域がすでに３つ存在し、エリア３−１の一部を救済することで担当領域が４つになることから、仮想ノードＩＤ（２９）に対応付けられる「救済領域管理表」に「エリア４−４」を対応付ける。そして、救済制御部３３は、救済管理テーブル２３にエリア４−４のテーブルを生成する。
【００７４】
さらに、救済制御部３３は、仮想ノードＩＤテーブル２１に「仮想ノードＩＤ＝５、サーバ３」を対応付けて記憶する。また、救済制御部３３は、サーバ３が被救済サーバであることから、仮想ノードＩＤ（５）に対応付けられる「仮想ノードＩＤ種別」に「自救済」を設定する。
【００７５】
続いて、救済制御部３３は、サーバ３がサーバ４に救済されていることから、サーバ管理ＩＤテーブル２２のサーバ３の「救済サーバＩＤリスト」に「サーバ４」追加するが、すでに対応付けられているので、それを維持する。さらに、サーバ４が仮想ノードＩＤ（２９）を新たな管理対象としたことから、サーバ管理ＩＤテーブル２２のサーバ４の「救済ノードＩＤリスト」に「２９」を追加する。このようにして、救済制御部３３は、救済制御部３３は、エリア３−２において仮想ノードＩＤ（６）から（２９）をサーバ４に割り振ることで、負荷分散を実現する。
【００７６】
（エリア４−３のセッション）
次に、サーバ３を救済するサーバ４が救済するエリア４−３においてセッションが発生した場合の管理について説明する。図１３は、サーバ３の救済時の振分例を説明する図である。図１３に示すよぅに、振分装置１０の振分処理部３１は、受信したＳＩＰ信号から算出したハッシュ値が２００である場合、当該ＳＩＰ信号をサーバ４に割り振る。同様に、振分処理部３１は、受信したＳＩＰ信号から算出したハッシュ値が２０５である場合、当該ＳＩＰ信号をサーバ４に割り振る。
【００７７】
このとき、振分処理部３１または救済制御部３３は、ハッシュ値（２００）およびハッシュ値（２０５）がエリア４−３に該当することから、エリア４−３に対応する救済管理テーブル２３に、セッションＩＤとしてこれらを追加する。
【００７８】
なお、振分処理部３１は、受信したＳＩＰ信号から算出したハッシュ値が２１０や２２０である場合、当該ＳＩＰ信号をサーバ３に割り振る。このとき、振分処理部３１または救済制御部３３は、ハッシュ値（２１０）またはハッシュ値（２２０）がエリア３−２に該当することから、エリア３−２に対応する救済管理テーブル２３に、セッションＩＤとしてこれらを追加する。
【００７９】
（エリア４−４の解放）
次に、エリア３−１を救済するエリア４−４を解放する例について説明する。つまり、サーバ４によるエリア３−１の救済終了を説明する。図１４は、サーバ３のエリア３−１の救済解除例を説明する図である。
【００８０】
図１４に示すように、救済解除部３４は、救済時に存在したセッション（３０）が終了したことを検出すると、サーバ４のエリア４−４を参照して、他にセッションが存在しないことを検出する。ここで、救済解除部３４は、サーバ３のエリア３−１には既存セッション（５）が存在するが、このセッションは、エリア３−１に該当し、サーバ３が担当することから、エリア４−４の解放には影響しないと判定する。
【００８１】
そして、救済解除部３４は、エリア３−１に追加した各情報を削除する。具体的には、救済解除部３４は、仮想ノードＩＤテーブル２１から、救済ノードである「仮想ノードＩＤ（２９）、サーバ４」に対応するレコードを削除する。同様に仮想ノードＩＤテーブル２１から、自救済ノードである「仮想ノードＩＤ（５）、サーバ３」に対応するレコードを削除する。
【００８２】
さらに、救済解除部３４は、サーバ管理テーブル２２から、サーバ４に対応付けられる救済ノードＩＤリストから（２９）を削除する。このようにすることで、サーバ４に新たに割り当てられていたエリア４−４が削除され、元のエリア３−１の状態となる。なお、エリア４−４が削除されたため、救済解除部３４は、エリア４−４に対応する救済管理テーブル２３を削除する。こうして、救済解除部３４は、エリア４−４を解放する。
【００８３】
（エリア４−３の解放）
次に、エリア３−２を救済するエリア４−３を解放する例について説明する。つまり、サーバ４によるエリア３−２の救済終了を説明する。ここでは、一例として段階的に開放する例を説明する。図１５は、サーバ３のエリア３−２の部分的な救済解除例を説明する図である。ここでは、救済時に存在したセッション（２００）およびセッション（２１０）はすでに終了しているものとする。
【００８４】
図１５に示すように、救済解除部３４は、救済後に発生したセッション（２０５）が終了したことを検出すると、サーバ４のエリア４−３を参照して、救済後に発生したセッション（２００）については依然としてセッションが存在することを検出する。したがって、救済解除部３４は、エリア４−４に対応する救済管理テーブル２３からセッションＩＤ（２０５）のみを削除する。
【００８５】
つまり、サーバ４のエリア４−３が仮想ノードＩＤ（１９２）から仮想ノードＩＤ（２１０）までであったが、仮想ノードＩＤ（２１０）が終了して、仮想ノードＩＤ（２００）が依然として処理中である。このことから、救済解除部３４は、仮想ノードＩＤ（１９２）から仮想ノードＩＤ（２００）までを救済可能と判定する。なお、既存セッション（２００）を担当しているサーバがサーバ４であることから、仮想ノードＩＤ（２００）はサーバ４の担当のままである。
【００８６】
そして、救済解除部３４は、仮想ノードＩＤテーブル２１において「仮想ノードＩＤ種別＝救済、担当サーバＩＤリストサーバ４」と設定される仮想ノードＩＤ（２０９）を仮想ノードＩＤ（２００）に変更する。同様に、救済解除部３４は、サーバ管理テーブルにおいて、サーバ４に対応付けられる救済ノードＩＤリストを（２９、２００）から（２００）に変更する。このようにすることで、救済解除部３４は、サーバ４が担当するエリア４−３の領域を、仮想ノードＩＤ（１９２）から仮想ノードＩＤ（２１０）までの長さ１８から仮想ノードＩＤ（１９２）から仮想ノードＩＤ（２００）の長さ８に縮退させることができる。
【００８７】
その後、救済後に発生したセッション（２００）が終了した例について説明する。図１６は、サーバ３のエリア３−２の全面解除例を説明する図である。救済解除部３４は、救済後に発生して依然として残っていたセッション（２００）が終了したことを検出すると、サーバ４のエリア４−３を参照して、他にセッションが存在しないことを検出する。
【００８８】
そして、救済解除部３４は、エリア３−２に追加した各情報を削除する。具体的には、救済解除部３４は、仮想ノードＩＤテーブル２１から、救済ノードである「仮想ノードＩＤ（２００）、サーバ４」に対応するレコードを削除する。同様に仮想ノードＩＤテーブル２１から、自救済ノードである「仮想ノードＩＤ（１９２）、サーバ３」に対応するレコードを削除する。
【００８９】
さらに、救済解除部３４は、サーバ管理テーブル２２から、サーバ４に対応付けられる救済ノードＩＤリストから（２００）を削除する。このようにすることで、サーバ４に新たに割り当てられていたエリア４−３が削除され、元のエリア３−２の状態となる。なお、エリア４−３が削除されたため、救済解除部３４は、エリア４−３に対応する救済管理テーブル２３を削除する。こうして、救済解除部３４は、エリア４−３を解放する。
【００９０】
［処理の流れ］
次に、上述した各種処理の流れについて説明する。ここでは、全体的な流れ、救済処理、解放処理などについて説明する。
【００９１】
（一連の流れ）
図１７は、一連の処理の流れを示すシーケンス図である。図１７に示すように、振分装置１０は、サーバ１やサーバ２からリソース情報を取得し（Ｓ１０１からＳ１０３）、サーバ１の負荷上昇を検出する（Ｓ１０４）。
【００９２】
続いて、振分装置１０は、負荷が閾値を超えたサーバ１を被救済サーバに特定し、負荷が小さいサーバ２を救済サーバに特定する（Ｓ１０５）。そして、振分装置１０は、救済処理を実行して、負荷分散を実行する（Ｓ１０６）。
【００９３】
その後、振分装置１０は、クライアント装置からＳＩＰなどの信号を受信すると（Ｓ１０７とＳ１０８）、信号からキーを用いて算出したハッシュ値の担当が元々サーバ１であったが、現在はサーバ２によって救済されていることから、サーバ１への振分を抑制し、サーバ２へ振り分ける（Ｓ１０９からＳ１１１）。
【００９４】
その後、振分装置１０は、セッションが解放された場合やサーバ１の負荷が小さくなった場合、これらを契機にして救済解放処理を実行する（Ｓ１１２）。
【００９５】
救済解放後に、振分装置１０は、クライアント装置からＳＩＰなどの信号を受信すると（Ｓ１１３とＳ１１４）、信号からキーを用いてハッシュ値を算出し、該ハッシュ値を担当するサーバ１へ振り分ける（Ｓ１１５からＳ１１７）。
【００９６】
（救済処理の流れ）
図１８は、救済処理の流れを示すフローチャートである。図１８に示すように、振分装置１０の負荷監視部３２は、処理が開始されると（Ｓ２０１：Ｙｅｓ）、各サーバのリソース情報を取得する（Ｓ２０２）。
【００９７】
続いて、救済制御部３３は、リソース情報を用いて、負荷が閾値以上の被救済サーバを検出した場合（Ｓ２０３：Ｙｅｓ）、リソース情報を用いて、負荷が閾値未満の救済サーバが存在するか否かを判定する（Ｓ２０４）。ここで、救済制御部３３は、救済サーバが存在しない場合（Ｓ２０４：Ｎｏ）、救済不可能つまり負荷分散不可能と判定して、処理を終了する。
【００９８】
一方、救済制御部３３は、救済サーバが存在する場合（Ｓ２０４：Ｙｅｓ）、サーバ管理テーブル２２に対して、被救済サーバのサーバＯＩＤに対応する救済サーバＩＤリストに、特定した救済サーバのサーバＩＤを設定する（Ｓ２０５）。
【００９９】
続いて、救済制御部３３は、被救済サーバからセッション情報を取得する（Ｓ２０６）。また、救済制御部３３は、サーバ管理テーブル２２や仮想ノードＩＤテーブル２１などを用いて、被救済サーバの通常ノードＩＤを抽出する（Ｓ２０７）。
【０１００】
その後、救済制御部３３は、Ｓ２０８からＳ２２１まで、被救済サーバの担当領域についてループ処理を実行する（Ｓ２０８）。具体的には、救済制御部３３は、通常ノードＩＤをキーにして、仮想ノードＩＤテーブル２１から担当する仮想ノードＩＤの位置関係等を特定し、被救済サーバの担当領域を算出する（Ｓ２０９）。
【０１０１】
続いて、救済制御部３３は、各担当領域について領域算出用テーブル２４を生成する（Ｓ２１０）。例えば、救済制御部３３は、被救済サーバから取得したセッション情報の中から該当範囲内に存在するセッション情報を抽出し、これらを用いて領域算出用テーブル２４を生成する。
【０１０２】
そして、救済制御部３３は、被救済サーバが担当する各領域において救済候補領域を算出し（Ｓ２１１）、算出した各救済候補領域についてＳ２１２からＳ２２０までのループ処理を実行する（Ｓ２１２）。具体的には、救済制御部３３は、救済候補領域を１つ選択し、選択した救済候補領域の長さが閾値以上である場合（Ｓ２１３：Ｙｅｓ）、該救済候補領域に対応する救済管理テーブル２３を生成する（Ｓ２１４）。
【０１０３】
続いて、救済制御部３３は、該救済候補領域に対応する領域算出用テーブル２４等を参照して、該救済候補領域にセッションが存在するか否かを判定する（Ｓ２１５）。ここで、救済制御部３３は、セッションが存在しない場合（Ｓ２１５：Ｎｏ）、仮想ノードＩＤテーブル２１を更新する（Ｓ２１６とＳ２１７）。具体的には、救済制御部３３は、該当領域の末尾に対応する仮想ノードの１つ前の通常ノードＩＤを自救済ノードＩＤとして追加し、該当領域の末尾に対応する仮想ノードの通常ノードＩＤを救済ノードＩＤとして追加する。
【０１０４】
一方、救済制御部３３は、セッションが存在する場合（Ｓ２１５：Ｙｅｓ）、救済領域判定処理を実行する（Ｓ２１８）。そして、救済制御部３３は、Ｓ２１７またはＳ２１８が終了すると、サーバ管理テーブル２２に救済ノードＩＤを追加する（Ｓ２１９）。具体的には、救済制御部３３は、救済サーバのサーバＩＤに対応する救済ノードＩＤリストに、Ｓ２１７で仮想ノードＩＤテーブル２１に追加した救済ノードＩＤを追加する。
【０１０５】
そして、救済制御部３３は、各救済候補領域について上述したＳ２１２からＳ２１９を実行し（救済領域算出処理ループ）、被救済サーバの各担当領域について上述したＳ２０９からＳ２２０を実行する（担当領域検索処理ループ）。
【０１０６】
その後、救済制御部３３は、救済サーバに対して、救済領域における呼信号の解放契機の通知開始を要求し（Ｓ２２２）、救済を開始する（Ｓ２２３）。
【０１０７】
（領域判定処理の流れ）
図１９は、領域判定処理の流れを示すフローチャートである。この処理は、図１８のＳ２１８で実行される処理である。
【０１０８】
図１９に示すように、救済制御部３３は、救済候補の該当領域が先頭要素である場合（Ｓ３０１：Ｙｅｓ）、仮想ノードＩＤテーブル２１に対して、該当領域の末尾に対応する仮想ノードの１つ前の通常ノードＩＤを自救済ノードとして追加する（Ｓ３０２）。さらに、救済制御部３３は、仮想ノードＩＤテーブル２１に対して、救済領域の右端（末尾）のセッションＩＤから１だけ減算した値を救済ノードＩＤとして追加する（Ｓ３０３）。
【０１０９】
一方、救済制御部３３は、救済候補の該当領域が先頭要素ではなく（Ｓ３０１：Ｎｏ）、救済候補の該当領域が末尾要素である場合（Ｓ３０４：Ｙｅｓ）、Ｓ３０５とＳ３０６を実行する。具体的には、救済制御部３３は、仮想ノードＩＤテーブル２１に対して、救済領域の左端（先頭）のセッションＩＤを自救済ノードＩＤとして追加し、該当領域の末尾に対応する仮想ノードの通常ノードＩＤを救済ノードとして追加する。
【０１１０】
また、救済制御部３３は、救済候補の該当領域が先頭要素ではなく（Ｓ３０１：Ｎｏ）、救済候補の該当領域が末尾要素でもない場合（Ｓ３０４：Ｎｏ）、Ｓ３０７とＳ３０８を実行する。具体的には、救済制御部３３は、仮想ノードＩＤテーブル２１に対して、救済領域の左端（先頭）のセッションＩＤを自救済ノードＩＤとして追加し、救済領域の右端（末尾）のセッションＩＤから１だけ減算した値を救済ノードＩＤとして追加する。
【０１１１】
（振分処理の流れ）
図２０は、信号振分処理の流れを示すフローチャートである。図２０に示すように、振分処理部３１は、信号を受信すると（Ｓ４０１：Ｙｅｓ）、ハッシュ値を算出し（Ｓ４０２）、仮想ノードＩＤテーブル２１等を参照して、ハッシュ値に該当する仮想ノードＩＤを検索する（Ｓ４０３）。
【０１１２】
そして、振分処理部３１は、検索された仮想ノードＩＤが救済ノードＩＤであり（Ｓ４０４：Ｙｅｓ）、信号種別が後続信号である場合（Ｓ４０５：Ｙｅｓ）、該救済ノードＩＤに対応付けられる担当サーバである救済サーバへ、受信信号を振り分ける（Ｓ４０６）。
【０１１３】
一方、振分処理部３１は、検索された仮想ノードＩＤが救済ノードＩＤであり（Ｓ４０４：Ｙｅｓ）、信号種別が後続信号ではない場合（Ｓ４０５：Ｎｏ）、救済管理テーブル２３を更新し（Ｓ４０７）、その後Ｓ４０６が実行される。具体的には、振分処理部３１は、ハッシュ値を含む領域の救済管理テーブル２３に対して、ハッシュ値を追加し、ハッシュ値の昇順でソートする。
【０１１４】
また、振分処理部３１は、検索された仮想ノードＩＤが救済ノードＩＤではなく（Ｓ４０４：Ｎｏ）、検索された仮想ノードＩＤが通常ノードＩＤか否かを判定する（Ｓ４０８）。
【０１１５】
そして、振分処理部３１は、検索された仮想ノードＩＤが通常ノードＩＤである場合（Ｓ４０８：Ｙｅｓ）、通常ノードＩＤに対応付けられるサーバに、受信信号を振り分ける（Ｓ４０９）。一方、振分処理部３１は、検索された仮想ノードＩＤが通常ノードＩＤではない場合（Ｓ４０８：Ｎｏ）、つまり検索された仮想ノードＩＤが自救済ノードＩＤである場合、自救済ノードＩＤに対応付けられる被救済サーバに、受信信号を振り分ける（Ｓ４１０）。
【０１１６】
（負荷解消時の処理）
図２１は、負荷解消時の救済解放処理の流れを示すフローチャートである。図２１に示すように、救済解除部３４は、被救済サーバの負荷が閾値未満になったことを検出すると（Ｓ５０１：Ｙｅｓ）、サーバ管理テーブル２２から救済ノードＩＤを特定する（Ｓ５０２）。
【０１１７】
続いて、救済解除部３４は、救済ノードＩＤをキーにして仮想ノードＩＤテーブル２１から救済領域管理表を検索し（Ｓ５０３）、救済領域管理表をポインタにして該当する救済管理テーブル２３を参照し、救済領域内にセッションが存在するか否かを判定する（Ｓ５０４）。
【０１１８】
そして、救済解除部３４は、救済領域内にセッションが存在する場合（Ｓ５０４：Ｙｅｓ）、救済解放が不可能であると判定し、未処理の救済領域が存在するか否かを判定する（Ｓ５０５）。
【０１１９】
ここで、救済解除部３４は、未処理の救済領域が存在する場合（Ｓ５０５：Ｙｅｓ）、次の救済領域についてＳ５０３以降を繰り返す。一方、救済解除部３４は、未処理の救済領域が存在しない場合（Ｓ５０５：Ｎｏ）、処理を終了する。
【０１２０】
一方、救済解除部３４は、救済領域内にセッションが存在しない場合（Ｓ５０４：Ｎｏ）、仮想ノードＩＤテーブル２１を更新する（Ｓ５０６）。具体的には、救済解除部３４は、仮想ノードＩＤテーブル２１から、仮想ノードＩＤ種別が自救済であるレコードと救済であるレコードとを削除する。
【０１２１】
続いて、救済解除部３４は、サーバ管理テーブル２２を更新する（Ｓ５０７）。具体的には、救済解除部３４は、サーバ管理テーブル２２から、救済ノードＩＤリストに登録されている仮想ノードＩＤと救済ノードＩＤリストに登録されている仮想ノードＩＤとを削除する。
【０１２２】
その後、救済解除部３４は、解放したエリアに対応する救済管理テーブル２３を削除する（Ｓ５０８）。
【０１２３】
（呼解放時の処理）
図２２は、呼解放時の救済解放処理の流れを示すフローチャートである。図２２に示すように、救済解除部３４は、呼解放通知を受信すると（Ｓ６０１：Ｙｅｓ）、呼解放通知（解放呼）のキーからハッシュ値を算出する（Ｓ６０２）。なお、救済解除部３４は、解放呼にハッシュ値（仮想ノードＩＤ）が含まれている場合は、それを抽出する。
【０１２４】
続いて、救済解除部３４は、ハッシュ値をキーにして仮想ノードＩＤテーブル２１から救済ノードＩＤを検索し（Ｓ６０３）、検索した救済ノードＩＤの１つ前の仮想ノードＩＤ（自救済ノードＩＤ）を検索する（Ｓ６０４）。そして、救済解除部３４は、検索した救済ノードＩＤに対応付けられる救済領域管理表をポインタにして、救済管理テーブル２３を抽出する（Ｓ６０５）。
【０１２５】
そして、救済解除部３４は、抽出した救済管理テーブル２３を参照して、セッションの残りが１つである場合（Ｓ６０６：Ｙｅｓ）、仮想ノードＩＤテーブル２１から救済ノードＩＤを削除する（Ｓ６０７）。例えば、救済解除部３４は、仮想ノードＩＤテーブル２１から、仮想ノードＩＤ種別が救済であるレコードを削除する。
【０１２６】
続いて、救済解除部３４は、仮想ノードＩＤテーブル２１から、自救済ノードＩＤを削除する（Ｓ６０８）。例えば、救済解除部３４は、仮想ノードＩＤテーブル２１から、仮想ノードＩＤ種別が自救済であるレコードを削除する。
【０１２７】
続いて、救済解除部３４は、サーバ管理テーブル２２から救済ノードＩＤを削除する（Ｓ６０９）。具体的には、救済解除部３４は、サーバ管理テーブル２２から、救済ノードＩＤリストに登録されている仮想ノードＩＤと救済ノードＩＤリストに登録されている仮想ノードＩＤとを削除する。その後、救済解除部３４は、解放したエリアに対応する救済管理テーブル２３を削除する（Ｓ６１０）。
【０１２８】
その後、救済解除部３４は、未処理の救済ノードＩＤが存在する場合（Ｓ６１１：Ｙｅｓ）、Ｓ６０３以降を繰り返す。一方、救済解除部３４は、未処理の救済ノードＩＤが存在しない場合（Ｓ６１１：Ｎｏ）、救済サーバに対して、救済領域における呼解放契機の通知終了を要求する（Ｓ６１２）。
【０１２９】
また、Ｓ６０６において、救済解除部３４は、抽出した救済管理テーブル２３を参照して、セッションの残りが１つではない場合（Ｓ６０６：Ｎｏ）、解放領域判定処理を実行した後（Ｓ６１３）、Ｓ６１１を実行する。
【０１３０】
（解放領域判定処理）
図２３は、解放領域判定処理の流れを示すフローチャートである。この処理は、図２２のＳ６１３で実行される処理である。
【０１３１】
図２３に示すように、救済解除部３４は、解放候補の該当領域が先頭要素である場合（Ｓ７０１：Ｙｅｓ）、Ｓ７０２およびＳ７０３を実行する。すなわち、救済解除部３４は、仮想ノードＩＤテーブル２１において、自救済ノードＩＤの値を「該当ハッシュ値の１つ後の要素のハッシュ値から１だけ減算した値」に更新する。つまり、救済解除部３４は、図２３に示すように、救済領域を右方向に削り取る。そして、救済解除部３４は、該当領域に対応する救済管理テーブル２３から該当ハッシュ値を削除する。
【０１３２】
一方、救済解除部３４は、解放候補の該当領域が先頭要素ではなく（Ｓ７０１：Ｎｏ）、解放候補の該当領域が末尾要素である場合（Ｓ７０４：Ｙｅｓ）、Ｓ７０５およびＳ７０６を実行する。すなわち、救済解除部３４は、仮想ノードＩＤテーブル２１において、自救済ノードＩＤの値を「該当ハッュ値の１つ前の要素のハッシュ値」に更新する。つまり、救済解除部３４は、図２３に示すように、救済領域を左方向に削り取る。そして、救済解除部３４は、該当領域に対応する救済管理テーブル２３から該当ハッシュ値を削除する。
【０１３３】
また、救済解除部３４は、解放候補の該当領域が末尾要素でもない場合（Ｓ７０４：Ｎｏ）、記憶部２０に、救済管理テーブル（分割用）を新たに作成する（Ｓ７０７）。続いて、救済解除部３４は、救済領域管理表（既存用）における該当ハッシュ値より前の全要素のハッシュ値を救済管理テーブル（分割用）に複製する（Ｓ７０８）。
【０１３４】
続いて、救済解除部３４は、仮想ノードＩＤテーブル２１において「該当ハッシュ値の１つ前の要素のハッシュ値」を救済ノードＩＤとして追加する（Ｓ７０９）。さらに、救済解除部３４は、サーバ管理テーブル２２に救済ノードＩＤを追加する（Ｓ７１０）。その後、救済解除部３４は、仮想ノードＩＤテーブル２１において「該当ハッシュ値の１つ後の要素のハッシュ値から１だけ減算した値」を自救済ノードＩＤとして追加する（Ｓ７１１）。
【０１３５】
［効果］
このように、実施例１によれば、振分装置１０は、コンシステントハッシュ法を用いた信号振り分けが特定サーバに偏り負荷が集中しそうになった場合に、データの移動を伴わずに、負荷分散を実行することができる。つまり、振分装置１０は、負荷が上がったサーバに影響を与えずに、低負荷サーバが高負荷サーバの担当領域の一部を一時的に担当し救済する事で速やかに負荷分散を実現できる。具体的には、振分装置１０は、既存のセッションに対する再割り当てなどを抑制しつつ、救済領域の設定を実行することで、迅速な負荷分散を実現できる。
【０１３６】
さらに、振分装置１０は、上述した方式で負荷バランスを取りながらも、高負荷サーバの負荷が低減し定常負荷に戻った場合は、速やかに、かつデータの移動を伴わずに救済した領域を元に戻せる制御方式を確立する。この結果、救済した低負荷サーバの負荷が上昇してしまう可能性を低減することができる。
【０１３７】
このように、振分装置１０は、データの移動を伴わずに既存サーバ間で仮想ノードＩＤの動的再配置を実行することができる。つまり、振分装置１０は、信号振り分けが特定サーバに偏った場合、新たなサーバを追加することなく、かつ、データ移動も伴わないため特定サーバに更なる負荷をかける事もなく、速やかに負荷分散ができる。更に、振分装置１０は、被救済サーバの輻輳が解消された場合においても、データ移動を伴わずに速やかに初期状態に戻すことができる。
【実施例２】
【０１３８】
さて、これまで本発明の実施例について説明したが、本発明は上述した実施例以外にも、種々の異なる形態にて実施されてよいものである。
【０１３９】
［サーバＩＤ］
上記実施例では、仮想ノードＩＤを用いた場合を例にして説明したが、これに限定されるものではなく、サーバＩＤそのものを用いても同様に処理することができる。
【０１４０】
［物理マシン］
上記実施例では、仮想マシンで実現する例を説明したが、これに限定されるものではなく、システムを構成する各装置は物理マシンで実現することもできる。また、振分装置を物理マシンで実現し、各サーバを仮想マシンで実現するなど、物理マシンと仮想マシンとが混合されていてもよい。なお、物理マシンで実現する場合、図４に示した各処理部は、プロセッサが有する電子回路やプロセッサが実行するプロセスに該当する。
【０１４１】
［ハッシュ値の重複］
上記実施例において、救済領域を設定する際に、通常ノードＩＤと自救済ノードＩＤなどが同じハッシュ値となる場合がある。例えば、振分装置１０がクライアント装置から信号を受信し、信号から取得したキーのハッシュ値が救済領域以外を示した場合、該当サーバに振り分ける。また、振分装置１０は、救済領域を示した場合は救済サーバに振り分ける。この時、振分装置が、初期信号だった場合には、救済領域管理表にセッション情報を追加しておく。
【０１４２】
なお、振分装置１０は、振り分け先の領域を算出するに辺り、具体的には信号から取得したキーのハッシュ値を基に仮想ノードＩＤテーブル２１から該当する仮想ノードＩＤを検索する事になる。このとき、同一ハッシュ値の通常ノードＩＤと自救済ノードＩＤが存在した場合は、通常ノードＩＤが優先され、通常ノードＩＤと救済ノードＩＤが存在した場合には、救済ノードＩＤが優先して選択されるものとする。
【０１４３】
［システム］
また、図示した装置の各構成は、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、任意の単位で分散または統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１４４】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的におこなうこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１４５】
［ハードウェア］
図２４は、ハードウェア構成例を示す図である。図２４に示すように、物理サーバ１００は、通信インタフェース１０ａ、ＨＤＤ（Hard  Disk  Drive）１０ｂ、メモリ１０ｃ、プロセッサ１０ｄを有する。また、図２４に示した各部は、バス等で相互に接続される。
【０１４６】
通信インタフェース１０ａは、他の装置との通信を制御するインタフェースであり、例えばネットワークインタフェースカードである。ＨＤＤ１０ｂは、仮想マシンを動作させるプログラムや各種情報を記憶するテーブルなどを記憶する。
【０１４７】
プロセッサ１０ｄは、仮想マシン・プログラムをＨＤＤ１０ｂ等から読み出してメモリ１０ｃに展開することでＶＭを実行し、図４等に示した各処理部と同様の処理を実行するプロセスを動作させる。
【０１４８】
例えば、このプロセスは、振分装置１０が有する各処理部と同様の機能を実行する。具体的には、プロセッサ１０ｄは、振分処理部３１、負荷監視部３２、救済制御部３３、救済解除部３４と同様の処理を実行するプロセスを実行する。
【０１４９】
このように物理サーバ１００は、プログラムを読み出して実行することで分散処理方法を実行する情報処理装置として動作する。また、物理サーバ１００は、媒体読取装置によって記録媒体から上記プログラムを読み出し、読み出された上記プログラムを実行することで上記した実施例と同様の機能を実現することもできる。なお、この他の実施例でいうプログラムは、物理サーバ１００によって実行されることに限定されるものではない。例えば、他のコンピュータまたはサーバがプログラムを実行する場合や、これらが協働してプログラムを実行するような場合にも、本発明を同様に適用することができる。
【符号の説明】
【０１５０】
１０  振分装置
２０  記憶部
２１  仮想ノードＩＤテーブル
２２  サーバ管理テーブル
２３  救済管理テーブル
２４  領域算出用テーブル
３０  制御部
３１  振分処理部
３２  負荷監視部
３３  救済制御部
３４  救済解除部
【図１】
2017021722.tif 000003
【図２】
2017021722.tif 000004
【図３】
2017021722.tif 000005
【図４】
2017021722.tif 000006
【図５】
2017021722.tif 000007
【図６】
2017021722.tif 000008
【図７】
2017021722.tif 000009
【図８】
2017021722.tif 000010
【図９】
2017021722.tif 000011
【図１０】
2017021722.tif 000012
【図１１】
2017021722.tif 000013
【図１２】
2017021722.tif 000014
【図１３】
2017021722.tif 000015
【図１４】
2017021722.tif 000016
【図１５】
2017021722.tif 000017
【図１６】
2017021722.tif 000018
【図１７】
2017021722.tif 000019
【図１８】
2017021722.tif 000020
【図１９】
2017021722.tif 000021
【図２０】
2017021722.tif 000022
【図２１】
2017021722.tif 000023
【図２２】
2017021722.tif 000024
【図２３】
2017021722.tif 000025
【図２４】
2017021722.tif 000026