(57)【特許請求の範囲】
【請求項１】
クライアントにサービスを提供する処理装置と、コンシステント・ハッシュ法により前記クライアントから得られるメッセージを前記処理装置に振り分ける負荷分散装置と、が通信可能に接続されている分散システムにおいて、前記処理装置に対して、１または複数の識別子を割り当てることで、メッセージの呼処理を担当するための１または複数の担当範囲を、コンシステント・ハッシュ法のＩＤ空間に設定することができるように前記負荷分散装置を機能させる負荷分散プログラムであって、
前記負荷分散装置の記憶部が、
前記分散システムを構成する既存の処理装置に割り当てられた１または複数の識別子である既存識別子の値と、
前記既存識別子に対して設定されている担当範囲である１または複数の既存担当範囲のサイズと、
前記既存の処理装置が有する１または複数の前記既存担当範囲を合わせた合計既存担当範囲のサイズと、
前記既存の処理装置の処理性能を示す既存性能指標値と、を記憶しており、
前記負荷分散装置の制御部に、
前記分散システムに追加された新たな処理装置を検出する処理と、
前記新たな処理装置の処理性能を示す新規性能指標値を特定する処理と、
前記新たな処理装置に割り当てられる識別子である１または複数の新規識別子を、特定の既存の処理装置が有する既存担当範囲に配置するとき、すべての前記既存の処理装置の合計既存担当範囲のサイズの合計値に対する、前記特定の既存の処理装置の合計既存担当範囲のサイズの比と、前記新規性能指標値およびすべての既存性能指標値の合計値に対する、前記特定の既存の処理装置の既存性能指標値の比と、を等しく、または略等しくする処理と、を実行させる
ことを特徴とする負荷分散プログラム。
【請求項２】
前記負荷分散装置の制御部に、
前記既存性能指標値に対する前記合計既存担当範囲のサイズの割合を、前記既存の処理装置ごとに算出する処理と、
前記割合が相対的に大きな既存の処理装置の既存担当範囲に配置する新規識別子の個数を、前記割合が相対的に小さな既存の処理装置が有する既存担当範囲に配置する新規識別子の個数と同等またはそれよりも多くする処理と、を実行させる
ことを特徴とする請求項１に記載の負荷分散プログラム。
【請求項３】
前記負荷分散装置の制御部に、
前記新規識別子が配置される既存担当範囲を有する前記既存の処理装置において、少なくとも前記既存の処理装置が有する１または複数の既存担当範囲のうち、そのサイズが最大となる既存担当範囲に前記新規識別子を配置する処理を実行させる
ことを特徴とする請求項１または請求項２に記載の負荷分散プログラム。
【請求項４】
クライアントにサービスを提供する処理装置と、コンシステント・ハッシュ法により前記クライアントから得られるメッセージを前記処理装置に振り分ける負荷分散装置と、が通信可能に接続されている分散システムにおいて、前記処理装置に対して、１または複数の識別子を割り当てることで、メッセージの呼処理を担当するための１または複数の担当範囲を、コンシステント・ハッシュ法のＩＤ空間に設定することができる負荷分散装置であって、
前記負荷分散装置の記憶部が、
前記分散システムを構成する既存の処理装置に割り当てられた１または複数の識別子である既存識別子の値と、
前記既存識別子に対して設定されている担当範囲である１または複数の既存担当範囲のサイズと、
前記既存の処理装置が有する１または複数の前記既存担当範囲を合わせた合計既存担当範囲のサイズと、
前記既存の処理装置の処理性能を示す既存性能指標値と、を記憶しており、
前記負荷分散装置の制御部に、
前記分散システムに追加された新たな処理装置を検出する制御と、
前記新たな処理装置の処理性能を示す新規性能指標値を特定する制御と、
前記新たな処理装置に割り当てられる識別子である１または複数の新規識別子を、特定の既存の処理装置が有する既存担当範囲に配置するとき、すべての前記既存の処理装置の合計既存担当範囲のサイズの合計値に対する、前記特定の既存の処理装置の合計既存担当範囲のサイズの比と、前記新規性能指標値およびすべての既存性能指標値の合計値に対する、前記特定の既存の処理装置の既存性能指標値の比と、を等しく、または略等しくする制御と、を実行する
ことを特徴とする負荷分散装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、分散処理を行う分散システムにおける負荷分散の技術に関する。
【０００２】
分散システムは、複数の物理的な処理装置（サーバ）を含み、必要であればこれらの処理装置を仮想化することで、所定のセッション制御を実現する。また、分散システムは、一般的には、１または複数の負荷分散装置を含む。負荷分散装置は、端末（クライアント）からセッション接続要求などのメッセージを受信すると、所定の方法に従ってメッセージを処理装置に振り分ける。つまり、分散システムの各処理装置は、負荷を分担する。各処理装置は、振り分けられたメッセージを呼処理し、端末に対して所定のサービスを提供する。
【０００３】
前記所定の方法としては、例えば、コンシステント・ハッシュ法がある。なお、非特許文献１は、コンシステント・ハッシュ法について開示している。コンシステント・ハッシュ法は、処理装置を識別する処理装置識別子と、処理装置に振り分けるメッセージに含まれ、呼処理の対象となるデータの実体を識別するデータ識別子と、に基づいて、どの処理装置にどのメッセージを振り分けるかを決定する方法である。コンシステント・ハッシュ法は、例えば、分散データベースシステムにおいて利用されている。
【０００４】
具体的に、どのようにしてメッセージの振り分けが決定されるかを、図６を参照して説明する。図６は、コンシステント・ハッシュ法を説明するためのＩＤ（Identifier）空間の概念図である。処理装置識別子は、例えば、処理装置のＩＰ（Internet Protocol）アドレス、処理装置名などに、ハッシュ関数を作用させて得られた値である。負荷分散装置は、分散システムを構成する処理装置の処理装置識別子をＩＤ空間に配置する。図６において、処理装置識別子は、「●」で示されている。
【０００５】
ＩＤ空間は、図６に示すようにリング状で描写されるハッシュ空間である。処理装置識別子は、例えば、その値に基づいてＩＤ空間において時計回りに昇順に配置される。メッセージがある処理装置に振り分けられるとき、データ識別子は、その値に基づいてハッシュ空間に写像して配置される。データ識別子も、その値に基づいてＩＤ空間において時計回りに昇順に配置される。図６において、データ識別子は、「○」で示されている。
【０００６】
このとき、処理装置は、自身の処理装置識別子の直近の処理装置識別子の配置場所から自身の処理装置識別子の配置場所まで時計回りに辿る円弧上に配置されるデータ識別子を含むメッセージを呼処理する。ここで、「直近の処理装置識別子」とは、ＩＤ空間において、対象の処理装置識別子の値よりも小さな値を持つ処理装置識別子のうち最も大きな値を持つ処理装置識別子を意味する。しかし、対象の処理装置識別子の値がＩＤ空間において、最も小さな値を持つ場合には、直近の処理装置識別子は、ＩＤ空間において、最も大きな値を持つこととする。すると、直近の処理装置識別子の配置場所から対象の処理装置識別子の配置場所まで時計回りに辿る円弧が、対象の処理装置識別子で識別される処理装置がメッセージの呼処理を担当する範囲、すなわち「担当範囲」である。また、図６において、ＩＤ空間に配置される対象のデータ識別子と、そのデータ識別子を含むメッセージの呼処理を行う処理装置である「担当処理装置」との関係である担当関係は、矢印で示されている。
【０００７】
図６によれば、処理装置識別子Ａ、Ｂ、Ｃの値にＡの値＜Ｂの値＜Ｃの値という関係があるとすると、時計回りにＡ→Ｂ→Ｃの順番に処理装置識別子が配置される。また、データ識別子Ｘの値は、Ａの値＜Ｘの値＜Ｂの値という関係を満たすとすると、処理装置識別子Ａおよび処理装置識別子Ｂの間に配置される。よって、データ識別子Ｘを含むメッセージについては、処理装置識別子Ｂで識別される処理装置が呼処理を担当する。つまり、処理装置識別子Ｂで識別される処理装置は、データ識別子Ｘを含むメッセージの呼処理にとっての担当処理装置である。また、図６において、処理装置識別子Ａから処理装置識別子Ｂまでに辿る円弧が、処理装置識別子Ｂで識別される処理装置の担当範囲となる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】David Karger、外５名、“Consistent Hashing and Random Trees:Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web”、［online］、［平成２４年１月１２日検索］、インターネット〈URL：http://www.akamai.com/dl/technical_publications/ConsistenHashingandRandomTreesDistributedCachingprotocolsforrelievingHotSpotsontheworldwideweb.pdf〉
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ところで、コンシステント・ハッシュ法によれば、処理装置識別子の値およびデータ識別子の値は、例えば、ハッシュ関数を用いて無作為な値として設定される。すると、各処理装置の担当範囲、つまり各処理装置が呼処理するメッセージの処理量は、確率的に均一に近づく。よって、確率的に均一に近づく負荷分散が行われる。
【００１０】
ただ、負荷分散が均一になるか否かは、確率的に決まるため、均一にならない場合がある。コンシステント・ハッシュ法では、１つの処理装置に（１または）複数の処理装置識別子を割り当て、１つの処理装置を複数の仮想的な処理装置の集合として実現する手段がある。この手段は、負荷分散装置が実行する。ある処理装置が分担する負荷の量は、その処理装置の担当範囲の長さ（サイズ）に比例する。前記手段により、ある処理装置の担当範囲の長さは、仮想的な処理装置の担当範囲の合計値となる。（仮想的ではない）各処理装置に対するこの合計値の分布は、大数の法則により、仮想的な処理装置の数が多いほど平均値に近づく。よって、負荷分散を均一に近づけることができ、負荷分散性を向上することができる。
【００１１】
しかし、一般的に、分散システムを構成する処理装置の処理性能は、各処理装置間で異なる。よって、負荷分散を確率的に決める手法を用いると、処理性能の高い処理装置が僅かな負荷しか分担せず、遊休資源が発生したり、処理性能の低い処理装置が、処理しきれない程の膨大な負荷を分担したりする場合が生じる。このような場合、分散システム全体の負荷分散性の低下を招く。また、このような事態を解消するために、各処理装置間の処理性能の違いを考慮して各処理装置が分担する負荷の量を変化させたいという要求がある。
【００１２】
このような事情に鑑みて、本発明は、処理装置に複数の処理装置識別子を割り当てることができる負荷分散装置において、処理装置の処理性能の違いに応じて、分散システムにおける負荷分散を最適化することを目的とする。
【課題を解決するための手段】
【００１３】
前記課題を解決するため、請求項１に記載の発明は、クライアントにサービスを提供する処理装置と、コンシステント・ハッシュ法により前記クライアントから得られるメッセージを前記処理装置に振り分ける負荷分散装置と、が通信可能に接続されている分散システムにおいて、前記処理装置に対して、１または複数の識別子を割り当てることで、メッセージの呼処理を担当するための１または複数の担当範囲を、コンシステント・ハッシュ法のＩＤ空間に設定することができるように前記負荷分散装置を機能させる負荷分散プログラムであって、前記負荷分散装置の記憶部が、前記分散システムを構成する既存の処理装置に割り当てられた１または複数の識別子である既存識別子の値と、前記既存識別子に対して設定されている担当範囲である１または複数の既存担当範囲のサイズと、前記既存の処理装置が有する１または複数の前記既存担当範囲を合わせた合計既存担当範囲のサイズと、前記既存の処理装置の処理性能を示す既存性能指標値と、を記憶しており、前記負荷分散装置の制御部に、前記分散システムに追加された新たな処理装置を検出する処理と、前記新たな処理装置の処理性能を示す新規性能指標値を特定する処理と、前記新たな処理装置に割り当てられる識別子である１または複数の新規識別子を、特定の既存の処理装置が有する既存担当範囲に配置するとき、すべての前記既存の処理装置の合計既存担当範囲のサイズの合計値に対する、前記特定の既存の処理装置の合計既存担当範囲のサイズの比と、前記新規性能指標値およびすべての既存性能指標値の合計値に対する、前記特定の既存の処理装置の既存性能指標値の比と、を等しく、または略等しくする処理と、を実行させることを特徴とする。
【００１４】
請求項２に記載の発明は、請求項１に記載の発明において、前記負荷分散装置の制御部に、前記既存性能指標値に対する前記合計既存担当範囲のサイズの割合を、前記既存の処理装置ごとに算出する処理と、前記割合が相対的に大きな既存の処理装置の既存担当範囲に配置する新規識別子の個数を、前記割合が相対的に小さな既存の処理装置が有する既存担当範囲に配置する新規識別子の個数と同等またはそれよりも多くする処理と、を実行させることを特徴とする。
【００１５】
請求項３に記載の発明は、請求項１または請求項２に記載の発明において、前記負荷分散装置の制御部に、前記新規識別子が配置される既存担当範囲を有する前記既存の処理装置において、少なくとも前記既存の処理装置が有する１または複数の既存担当範囲のうち、そのサイズが最大となる既存担当範囲に前記新規識別子を配置する処理を実行させることを特徴とする。
【００１６】
請求項４に記載の発明は、クライアントにサービスを提供する処理装置と、コンシステント・ハッシュ法により前記クライアントから得られるメッセージを前記処理装置に振り分ける負荷分散装置と、が通信可能に接続されている分散システムにおいて、前記処理装置に対して、１または複数の識別子を割り当てることで、メッセージの呼処理を担当するための１または複数の担当範囲を、コンシステント・ハッシュ法のＩＤ空間に設定することができる負荷分散装置であって、前記負荷分散装置の記憶部が、前記分散システムを構成する既存の処理装置に割り当てられた１または複数の識別子である既存識別子の値と、前記既存識別子に対して設定されている担当範囲である１または複数の既存担当範囲のサイズと、前記既存の処理装置が有する１または複数の前記既存担当範囲を合わせた合計既存担当範囲のサイズと、前記既存の処理装置の処理性能を示す既存性能指標値と、を記憶しており、前記負荷分散装置の制御部に、前記分散システムに追加された新たな処理装置を検出する制御と、前記新たな処理装置の処理性能を示す新規性能指標値を特定する制御と、前記新たな処理装置に割り当てられる識別子である１または複数の新規識別子を、特定の既存の処理装置が有する既存担当範囲に配置するとき、すべての前記既存の処理装置の合計既存担当範囲のサイズの合計値に対する、前記特定の既存の処理装置の合計既存担当範囲のサイズの比と、前記新規性能指標値およびすべての既存性能指標値の合計値に対する、前記特定の既存の処理装置の既存性能指標値の比と、を等しく、または略等しくする制御と、を実行することを特徴とする。
【００１７】
請求項１、４に記載の発明によれば、分散システムを構成する既存の処理装置の処理性能が均一でない、つまり性能指標値が同一でない場合であっても、新たな処理装置を追加するときは、新たな処理装置を含む各処理装置のそれぞれの性能指標値の比に合致するといった調整を実現できるように、新たな処理装置の仮想識別子の値を決定する。これにより、既存の処理装置に対して負荷を均等に分散させたいという要求を満たしつつも、処理装置の処理性能の不均一性と負荷分散性とを両立する。その結果、処理装置の処理性能の違いに応じて、分散システムにおける負荷分散を最適化することができる。
【００１８】
請求項２に記載の発明によれば、相対的に大きな負荷を分担する既存の処理装置の担当範囲内に、新たな処理装置の仮想識別子をより多く配置し、そのような既存の処理装置が分担する負荷を優先的に小さくすることができる。よって、新たな処理装置を追加するときは、前記した、新たな処理装置を含む各処理装置のそれぞれの性能指標値の比に合致するような調整を、より高い精度で行うことができる。
【００１９】
請求項３に記載の発明によれば、既存の処理装置が有する１または複数の担当範囲のうち、新たな処理装置に譲るに相応しい担当範囲を特定することができる。よって、新たな処理装置を追加するときは、前記した、新たな処理装置を含む各処理装置のそれぞれの性能指標値の比に合致するような調整を、より高い精度で行うことができる。
【発明の効果】
【００２０】
本発明によれば、処理装置に複数の処理装置識別子を割り当てることができる負荷分散装置において、処理装置の処理性能の違いに応じて、分散システムにおける負荷分散を最適化することができる。
【図面の簡単な説明】
【００２１】
【図１】分散システムの構成図である。
【図２】負荷分散装置で使用されるソフトウェアの構成図である。
【図３Ａ】処理装置を増設したときの負荷分散装置における処理を示すフローチャートである。
【図３Ｂ】処理装置を増設したときの負荷分散装置における処理を示すフローチャートである。
【図４】分散システムの他の形態の構成図である。
【図５】分散システムのさらに他の形態の構成図である。
【図６】コンシステント・ハッシュ法を説明するためのＩＤ空間の概念図である。
【発明を実施するための形態】
【００２２】
≪構成≫
まず、本実施形態の構成について説明する。
図１は、分散システムの構成図である。この分散システムは、負荷分散装置１と、処理装置２と、クライアント３とを含む。この分散システムは、複数の処理装置２が協調してセッション制御を行い、クライアント３に所定のサービスを提供する。前記セッション制御は、例えば、呼制御であり、ＳＩＰ（Session Initiation Protocol）を使用して、インターネット電話などのサービスが提供される。
【００２３】
負荷分散装置１は、クライアント３から受信したメッセージを、例えばコンシステント・ハッシュ法によって、処理装置２に振り分ける。前記メッセージは、例えばＳＩＰ信号であり、セッション接続要求などを含む。
処理装置２は、負荷分散装置１から振り分けられたメッセージを呼処理し、クライアント３にサービスを提供する。処理装置２は、計算機やコンピュータなどの物理的な装置であってもよいし、仮想マシンなどの論理的な装置であってもよい。分散システムは、複数の処理装置２などのコンピュータ資源を仮想化して動作するクラスタシステムとすることができる。コンピュータ資源の仮想化には、例えば、VMware（登録商標）を用いることができる。
クライアント３は、メッセージを負荷分散装置１に送信し、処理装置２が提供するサービスを利用する。
【００２４】
負荷分散装置１と、処理装置２と、クライアント３とはいずれも、入力部、出力部、制御部および記憶部といったハードウェアを含むコンピュータである。入力部は、例えば、入力インタフェースから構成される。出力部は、例えば、出力インタフェースから構成される。制御部は、例えば、ＣＰＵ（Central Processing Unit）や専用回路から構成される。記憶部は、例えば、ＲＡＭ（Random Access Memory）、ＲＯＭ（Read Only Memory）、ＨＤＤ（Hard Disk Drive）、フラッシュメモリの記憶媒体から構成される。前記制御部がＣＰＵから構成される場合、その制御部を含むコンピュータによる情報処理は、ＣＰＵによるプログラム実行処理で実現する。また、そのコンピュータが含む記憶部は、ＣＰＵが指令し、そのコンピュータの機能を実現するためのプログラム（負荷分散プログラムを含む）を記憶する。これによりソフトウェアとハードウェアの協働が実現される。
【００２５】
本実施形態は、前記情報処理を実行させるプログラムによって実現することができ、そのプログラムをコンピュータによる読み取り可能な記録媒体（例：ＣＤ−ＲＯＭ）に記憶して提供することが可能である。また、そのプログラムを、インターネットのネットワークを通して提供することも可能である。
【００２６】
本実施形態の分散システムで使用されるソフトウェアについて説明する。
図２は、負荷分散装置で使用されるソフトウェアの構成図である。負荷分散装置１は、処理装置検出部１１と、性能指標値特定部１２と、識別子割当個数決定部１３と、識別子割当担当範囲選択部１４と、識別子割当部１５と、識別子管理テーブルＴ１と、負荷管理テーブルＴ２といった構成要素を備える。なお、負荷分散装置１が備える構成要素は他にも存在するが、その説明を省略する。
【００２７】
処理装置検出部１１は、分散システムに追加された、つまり増設された処理装置２を検出する。また、処理装置検出部１１は、分散システムから処理装置２が削除された、つまり減設されたことを検出する。例えば、分散システムを構成する処理装置２は、生存信号を負荷分散装置１に定期的に送信しており、負荷分散装置１は、その生存信号を所定期間以上受信しなかったときに、その処理装置２が削除されたとみなす。
【００２８】
なお、前記したとおり、コンシステント・ハッシュ法では、分散システムを構成する処理装置２には、複数の仮想的な処理装置の集合として実現するための、１または複数の処理装置識別子を割り当てることができる。そのような１または複数の処理装置識別子は、ＩＤ空間（図６参照）に配置することができる。本実施形態では、１つの処理装置２に割り当てる１または複数の処理装置識別子を「仮想識別子」と呼ぶことにする。仮想識別子は、複数の仮想的な処理装置のそれぞれを識別するための識別子である。仮想識別子の値は、例えば、処理装置２のＩＰアドレスや処理装置名などに、ハッシュ関数を作用させたハッシュ値である。分散システムを構成する既存の処理装置２および分散システムに追加された処理装置２に対して、１または複数の仮想識別子が割り当てられる。なお、本実施形態では、特に断らない限り、単に処理装置識別子と述べるときは、仮想識別子（特許請求の範囲の「識別子」に相当）を意味することとする。
【００２９】
一方、処理装置２は、他の処理装置２と区別して識別するための固有の（１つの）識別子を有している。本実施形態では、そのような固有の識別子を「親識別子」と呼ぶ。親識別子の値は、任意の値とすることができ、特に、ハッシュ値である必要は無い。説明の便宜上、本実施形態では、親識別子は、ＩＤ空間に配置されないとする。しかし、親識別子の値をハッシュ値とし、親識別子をＩＤ空間に配置するように設計することは可能である。処理装置２に割り当てられた仮想識別子は、その処理装置２が有している親識別子に属している。例えば、処理装置２を分散システムに追加するとき、その処理装置２に対して、１つの親識別子が割り当てられる。また、処理装置２に割り当てられた複数の仮想識別子の一つを親識別子と設計することも可能であるが、本実施形態では、このような設計は行わない。
【００３０】
性能指標値特定部１２は、分散システムを構成する処理装置２の性能指標値を特定する。よって、性能指標値特定部１２は、分散システムに追加された処理装置２の性能指標値を特定する。「性能指標値」とは、処理装置２の処理性能を示すパラメータである。処理装置２の処理性能の具体例としては、例えば、処理装置２のＣＰＵ周波数、処理装置２の記憶部の記憶容量、処理装置２がデータストアを使用してデータを記憶するリソース（例：ディスク）の記憶容量がある。処理装置２の処理性能をそのまま性能指標値としてもよい。また、総合的な処理性能を判断するために、ベンチマークプログラムを用いて、それらの処理性能の一部または全部から算出されるスコアを性能指標値としてもよい。
【００３１】
性能指標値が大きいほど、処理装置２の処理性能が大きいとする。性能指標値の大きな処理装置２は、分担する負荷量を多くしても、つまりＩＤ空間の担当範囲を長くしても、所望する処理速度を実現することができる。また、処理装置２が物理的な装置であっても、論理的な装置であっても、前記の性能指標値を適用することができる。
【００３２】
識別子割当個数決定部１３は、処理装置２に割り当てる仮想識別子の個数を決定する。よって、識別子割当個数決定部１３は、分散システムに追加された処理装置２に割り当てる仮想識別子の個数を決定する。その個数を決定する方法については、後記する。
【００３３】
識別子割当担当範囲選択部１４は、処理装置２に割り当てる仮想識別子を、既存の処理装置２の担当範囲のいずれに配置するかを選択する。つまり、処理装置２に割り当てる仮想識別子をＩＤ空間のどこに配置するか決定する。よって、識別子割当担当範囲選択部１４は、分散システムに追加された処理装置２に割り当てる仮想識別子を、既存の処理装置２の担当範囲のいずれに配置するかを選択すると、既存の処理装置２の担当範囲が、追加された処理装置２の担当範囲に切り替わる。その担当範囲を選択する方法については、後記する。
【００３４】
識別子割当部１５は、所定のハッシュ値が設定された１または複数の仮想識別子を、処理装置２に割り当てる。よって、識別子割当部１５は、所定のハッシュ値が設定された１または複数の仮想識別子を、分散システムに追加された処理装置２に割り当てる。これにより、追加された処理装置２の担当範囲、つまり負荷量が定まる。なお、追加された処理装置２の仮想識別子にどのようなハッシュ値を設定するか、つまり、その仮想識別子に対応する仮想的な処理装置の担当範囲の長さをどの程度にするか、ということについては、後記する。
【００３５】
識別子管理テーブルＴ１は、処理装置２に割り当てられた仮想識別子が、ＩＤ空間でどのように配置されているかを管理する。識別子管理テーブルＴ１は、「仮想識別子」と、「担当範囲サイズ」と、「親識別子」といったフィールドを含み、仮想識別子ごとにレコードが作成されている。
【００３６】
「仮想識別子」のフィールドには、１つの処理装置２に対して割り当てられた１または複数の仮想識別子（既存識別子）の値（ハッシュ値）が格納されている。
「担当範囲サイズ」のフィールドには、対応する仮想識別子で識別される仮想的な処理装置に設定された担当範囲（既存担当範囲）のサイズ、つまりＩＤ空間の円弧の長さが格納されている。なお、１または複数の仮想識別子で識別される仮想的な処理装置に設定された担当範囲を合わせた担当範囲を「合計既存担当範囲」と呼ぶ。
「親識別子」のフィールドには、対応する仮想識別子が属している親識別子の値が格納されている。
【００３７】
負荷管理テーブルＴ２は、処理装置２が分担する負荷を管理する。負荷管理テーブルＴ２は、「親識別子」と、「振り分け先アドレス」と、「性能指標値」と、「合計担当範囲サイズ」といったフィールドを含み、親識別子ごとにレコードが作成されている。
【００３８】
「親識別子」のフィールドには、分散システムを処理装置２に割り当てられた親識別子の値が格納されている。負荷管理テーブルＴ２の「親識別子」のフィールドは、識別子管理テーブルＴ１の「親識別子」のフィールドと同等である。
「振り分け先アドレス」のフィールドには、処理装置２のＩＰアドレスが格納されている。
「性能指標値」のフィールドには、処理装置２の性能指標値（既存性能指標値）が格納されている。
「合計担当範囲サイズ」のフィールドには、処理装置２に設定された担当範囲のサイズの合計値（合計既存担当範囲のサイズ）が格納されている。この合計値は、処理装置２に割り当てられた１または複数の仮想識別子に設定された担当範囲のサイズの合計値である。つまり、この合計値は、処理装置２に割り当てられた親識別子に属する仮想識別子で識別される仮想的な処理装置に設定された担当範囲のサイズ（識別子管理テーブルＴ１の「担当範囲サイズ」のフィールドの該当部分）の合計値である。
【００３９】
なお、処理装置２のソフトウェアの構成についての説明は省略するが、処理装置２は、以下に述べる処理を行うことができる。つまり、処理装置２の担当範囲が変更し、メッセージの呼処理を担当しないことになった場合、処理装置２は、そのメッセージの呼処理を新たに担当することになった別の処理装置２に対し、その呼処理に必要となるデータの実体を送信することができる。
【００４０】
≪処理≫
次に、本実施形態の処理について説明する。
図３（図３Ａおよび図３Ｂの総称）は、処理装置を増設したときの負荷分散装置における処理を示すフローチャートである。この処理の主体は、負荷分散装置１の制御部である。この処理は、ステップＳ０１から開始する。なお、負荷分散装置１は、分散システムを構成する処理装置（既存の処理装置）２の個数Ｎの値を、負荷分散装置１の記憶部に記憶している。
【００４１】
ステップＳ０１において、負荷分散装置１の制御部は、分散システムに追加された新たな処理装置２を検出する。ステップＳ０１の処理は、主に、処理装置検出部１１の機能に従う。ステップＳ０１の後、ステップＳ０２に進む。
【００４２】
ステップＳ０２において、負荷分散装置１の制御部は、性能指標値特定部１２により、新たな処理装置２の性能指標値Ｐ（新規性能指標値）を特定する。ステップＳ０２の処理は、主に、性能指標値特定部１２の機能に従う。ステップＳ０２の後、ステップＳ０３に進む。
【００４３】
ステップＳ０３において、負荷分散装置１の制御部は、新たな処理装置２に割り当てる仮想識別子（新規識別子）の個数Ｘを決定する。ステップＳ０３の処理は、主に、識別子割当個数決定部１３の機能に従う。ステップＳ０３の後、ステップＳ０４に進む。仮想識別子の個数Ｘは、下記の計算式から決定する。
Ｘ  ＝  Ｐ  ÷  ＰＢ  ×  ＸＢ
ただし、
ＰＢ：基準性能指標値
ＸＢ：仮想識別子の基準個数
【００４４】
基準性能指標値ＰＢとは、処理装置２の性能指標値のおよその目安値である。基準性能指標値ＰＢは、例えば、分散システムの管理者の裁量で決定し、負荷分散装置１の入力部から入力される。例えば、分散システムの管理者は、分散システムを構成する既存の処理装置２の性能指標値を取得し、その性能指標値の平均値を基準性能指標値とすることができる。なお、基準性能指標値の決定方法は、これに限定されない。
【００４５】
仮想識別子の基準個数ＸＢとは、処理装置２に割り当てる仮想識別子の個数のおよその目安値である。仮想識別子の基準個数ＸＢは、例えば、分散システムの管理者の裁量で決定し、負荷分散装置１の入力部から入力される。また、例えば、処理装置の性能指標値Ｐを基準性能指標値ＰＢとしたときに割り当てられる仮想識別子の個数Ｘを、仮想識別子の基準個数ＸＢとすることができる。
【００４６】
ところで、負荷分散装置１の記憶部の記憶領域を考慮すると、１つの処理装置２に複数の仮想識別子を割り当てるという手段による負荷分散の均一化、つまり負荷分散性の向上には、限界がある。つまり、処理装置２に複数の処理装置識別子を割り当てることで、負荷分散装置１が識別子管理テーブルＴ１を用いて管理する仮想識別子の量が増え、負荷分散装置１の記憶部の記憶領域を圧迫してしまう。よって、仮想識別子の基準個数ＸＢを大きくすると、負荷分散性は向上するが、負荷分散装置１の記憶部の記憶領域を圧迫してしまう。分散システムの管理者は、負荷分散性と、負荷分散装置１の記憶部の記憶領域とのトレードオフを考慮して仮想識別子の基準個数ＸＢを定めることが好ましい。
【００４７】
なお、ステップＳ０３の計算式により、小数点以下の端数は任意に取り扱って（例：四捨五入）、最終的には、仮想識別子の個数Ｘを１以上の整数として出力する。
【００４８】
ステップＳ０３の計算式により、単に、基準個数ＸＢ分の仮想識別子を割り当てられる場合と比較して、処理装置２の性能を考慮した最適な個数Ｘを求めることができる。よって、無駄に多くの仮想識別子を作ってしまい、負荷分散装置１の記憶部の記憶領域を圧迫してしまう、という事態を解消することができる。
【００４９】
ステップＳ０４において、負荷分散装置１の制御部は、負荷管理テーブルＴ２を参照して、分散システムを構成する既存の処理装置２についてそれぞれ、
合計担当範囲サイズ（合計既存担当範囲のサイズ）  ÷  性能指標値（既存性能指標値）
となる値（割合）を算出し、その算出結果の降順に負荷管理テーブルＴ２をソートする。ステップＳ０４の後、ステップＳ０５に進む。
ステップＳ０４により、性能指標値の割には大きすぎる担当範囲サイズを持っている既存の処理装置２を特定することができる。
【００５０】
ステップＳ０５において、負荷分散装置１の制御部は、新たな処理装置２について、
Ｘ  ｍｏｄ  Ｎ  ＝  ０
という関係式を満たすか否か判定する。ここで、「ｍｏｄ」は、モジュロ関数、つまり整数の除算における剰余を求める関数である。前記関係式を満たす場合（ステップＳ０５でＹｅｓ）、ステップＳ０６に進み、そうでなければ（ステップＳ０５でＮｏ）、ステップＳ０７に進む。
【００５１】
ステップＳ０６において、負荷分散装置１の制御部は、新たな処理装置２に割り当てることになるＸ個の仮想識別子に関して、既存の処理装置２それぞれの担当範囲内にＹ＝Ｘ÷Ｎ個の仮想識別子を配置することを決定する。ステップＳ０６の後、ステップＳ０８に進む。
【００５２】
ステップＳ０７において、負荷分散装置１の制御部は、新たな処理装置２に割り当てることになるＸ個の仮想識別子に関して、ステップＳ０４でソートした負荷管理テーブルＴ２の先頭からＸ  ｍｏｄ  Ｎ番目までのレコードに対応する既存の処理装置２それぞれの担当範囲内にＹ＝［Ｘ÷Ｎ］＋１個の仮想識別子を配置するとともに、（Ｘ  ｍｏｄ  Ｎ）＋１番目のレコードから最後尾のレコードに対応する残りの既存の処理装置２それぞれの担当範囲内にＹ＝［Ｘ÷Ｎ］個の仮想識別子を配置することを決定する。ここで、［Ｘ］とは、Ｘの床関数、つまりＸを超えない最大の整数を意味する。ステップＳ０７の後、ステップＳ０８に進む。
【００５３】
例えば、６つの処理装置２（Ｎ＝６）で構成される分散システムに、新たな処理装置２を追加し、新たな処理装置２の仮想識別子を１０個（Ｘ＝１０）割り当てる場合を考える。この場合、ステップＳ０４の処理によって、６つの既存の処理装置２のそれぞれについて、（合計担当範囲サイズ  ÷  性能指標値）となる値を計算し、その値の大きいものから順に並べる。１番目から４（＝１０ｍｏｄ６）番目の処理装置２に対しては、新たな処理装置２の仮想識別子を２個（＝［１０÷６］＋１）ずつ割り当てる。そして、残る２つ（＝６−１０ｍｏｄ６）の処理装置２に対しては、新たな処理装置２の仮想識別子を１個（＝［１０÷６］）ずつ割り当てる。このような割り当ては、性能指標値に対して余分に大きな担当範囲を抱えている処理装置２から優先的に、多くの仮想識別子を割り当てて、新たな処理装置２に担当範囲を移譲することを意味する。
【００５４】
ステップＳ０６の処理と、ステップＳ０７の処理とにより、既存の処理装置２の担当範囲のいずれに、新たな処理装置２の仮想識別子を何個配置するかを決定することができる。特に、ステップＳ０７の処理により、合計担当範囲サイズ÷性能指標値の値が大きな処理装置２、つまり、相対的に大きな負荷を分担する既存の処理装置２の担当範囲内に、新たな処理装置２の仮想識別子を１つ多く配置することになる。よって、そのような既存の処理装置２が分担する負荷を優先的に小さくすることができる。なお、相対的に大きな負荷を分担する既存の処理装置２の担当範囲内に、２つ以上多い新たな処理装置２の仮想識別子を配置することも可能である。
【００５５】
ステップＳ０８において、負荷分散装置１の制御部は、既存の処理装置２に対して用いられる自然数の変数ｉに１を代入する。ステップＳ０８の後、ステップＳ０９に進む。なお、説明の便宜上、ｉ番目の既存の処理装置２の担当範囲内に配置されることになる新たな処理装置２の仮想識別子の個数Ｙを、「Ｙｉ」と表記する。
【００５６】
ステップＳ０９において、負荷分散装置１の制御部は、識別子管理テーブルＴ１を参照して、ｉ番目の既存の処理装置２に割り当てられた仮想識別子に対応する担当範囲のうち、最も長い担当範囲からＹｉ番目に長い担当範囲までのＹｉ個の担当範囲を選択する。具体的には、識別子管理テーブルＴ１において、ｉ番目の既存の処理装置２の親識別子が同じである仮想識別子を特定する。次に、識別子管理テーブルＴ１において、特定した仮想識別子に対応する担当範囲の担当範囲サイズを取得し、担当範囲サイズの最も大きな仮想識別子、担当範囲サイズの２番目に大きな仮想識別子、・・・、担当範囲サイズのＹｉ番目に大きな仮想識別子、を抽出する。そして、抽出したＹｉ個の仮想識別子に対応する担当範囲を選択する。ステップＳ０９の処理（および、後記するステップＳ１０〜ステップＳ１５の処理）は、主に、識別子割当担当範囲選択部１４の機能に従う。ステップＳ０９の後、ステップＳ１０に進む。
【００５７】
ステップＳ０９により、ｉ番目の既存の処理装置２の担当範囲のうち、新たな処理装置２に譲るに相応しい担当範囲を特定することができる。また、ステップＳ０９によれば、少なくとも最も長い担当範囲に新たな処理装置２の仮想識別子が配置される、つまり、最も長い担当範囲の一部を新たな処理装置２に譲ることになる。
【００５８】
例えば、２０個の仮想識別子が割り当てられている既存の処理装置２が有する２０個の担当範囲に、追加された新たな処理装置２の２つの仮想識別子を配置することになった場合を考える。この場合、この既存の処理装置２は、２０個の担当範囲のうち、担当範囲サイズの最も大きな担当範囲と、担当範囲サイズの２番目に大きな担当範囲という２つの担当範囲を選択し、新たな処理装置２の２つの仮想識別子を選択した担当範囲のそれぞれに配置する。
【００５９】
ステップＳ１０において、負荷分散装置１の制御部は、負荷管理テーブルＴ２を参照して、ｉ番目の既存の処理装置２（特定の既存の処理装置）の合計担当範囲サイズＣｉの目標値ＣＡｉを決定する。ステップＳ１０の後、ステップＳ１１に進む。目標値ＣＡｉは、下記の計算式から決定する。
ＣＡｉ  ＝  ＣＴ  ×  Ｐｉ  ÷  ＰＴ
ただし、
ＣＴ：すべての既存の処理装置２の合計担当範囲サイズの合計値（負荷管理テーブルＴ２の「合計担当範囲サイズ」のフィールドに格納された値の和。図６のＩＤ空間を表現したリング１周分の長さに相当）
Ｐｉ：ｉ番目の既存の処理装置２の性能指標値
ＰＴ：新たな処理装置２の性能指標値と、すべての既存の処理装置２の性能指標値の合計値（負荷管理テーブルＴ２の「性能指標値」のフィールドに格納された値の和）との合計値
ステップＳ１０により、ｉ番目の既存の処理装置２の性能指標値に相応しい合計担当範囲サイズを決定することができる。
【００６０】
例えば、仮に、それぞれの性能指標値が、７，８，９，１０，１１となる５つの処理装置２で構成される分散システムに対し、性能指標値が１２となる新たな処理装置２を追加し、性能指標値９の処理装置２の担当範囲に、新たな処理装置２の仮想識別子を配置する場合を採り上げる。この場合、性能指標値９の処理装置２の担当範囲が、全体の担当範囲の９／（７＋８＋９＋１０＋１１＋１２）  ＝  ３／１９となるような目標値ＣＡｉを決定する。
【００６１】
ステップＳ１１において、負荷分散装置１の制御部は、負荷管理テーブルＴ２を参照して、ｉ番目の既存の処理装置２の余分担当範囲サイズＣＥｉを決定する。余分担当範囲サイズＣＥｉとは、ｉ番目の既存の処理装置２の担当範囲サイズの余分値である。例えば、この余分値は、ｉ番目の既存の処理装置２にとっては多すぎる負荷の量と解釈することができる。ステップＳ１１の後、ステップＳ１２に進む。余分担当範囲サイズＣＥｉは、下記の計算式から決定する。
ＣＥｉ  ＝  Ｃｉ  −  ＣＡｉ
ステップＳ１１により、ｉ番目の既存の処理装置２の合計担当範囲サイズＣｉと、その目標値ＣＡｉとのズレを定量的に評価することができる。
【００６２】
ステップＳ１２において、負荷分散装置１の制御部は、ｉ番目の既存の処理装置２について、
ＣＥｉ  ≦  ０
という関係式を満たすか否か判定する。前記関係式を満たす場合（ステップＳ１２でＹｅｓ）、ステップＳ１３に進み、そうでなければ（ステップＳ１２でＮｏ）、ステップＳ１４に進む。
【００６３】
ステップＳ１３において、負荷分散装置１の制御部は、ｉ番目の既存の処理装置２の担当範囲については、新たな処理装置２のＹｉ個の仮想識別子の配置を中断する。ｉ番目の既存の処理装置２の担当範囲については、余分な担当範囲サイズは存在せず、十分な負荷分散性が得られているからである。ステップＳ１３の後、ステップＳ１７に進む。なお、配置を中断した、新たな処理装置２のＹｉ個の仮想識別子は、削除してもよいし、他の既存の処理装置２の担当範囲に配置してもよい。図３のフローにおいては、削除することとする。
【００６４】
ステップＳ１４において、負荷分散装置１の制御部は、ｉ番目の既存の処理装置２に関する比率ＰＲｉを決定する。ステップＳ１４の後、ステップＳ１５に進む。比率ＰＲｉは、下記の計算式から決定する。
ＰＲｉ  ＝  ＣＥｉ  ÷  ＣＵｉ
ただし、
ＣＵｉ：ｉ番目の既存の処理装置２の担当範囲のうち、ステップＳ０９で選択したＹｉ個の担当範囲の担当範囲サイズの合計値
【００６５】
ステップＳ１５において、負荷分散装置１の制御部は、ｉ番目の既存の処理装置２の担当範囲のうち、ステップＳ０９で選択したＹｉ個の担当範囲のそれぞれに１つずつ配置することになる新たな処理装置２のＹｉ個の仮想識別子の値Ｖｋ（ｋ＝１、２、・・・、Ｙｉ）を決定する。ステップＳ１５の後、ステップＳ１６に進む。新たな処理装置２のＹｉ個の仮想識別子の値Ｖｋは、下記の計算式から決定する。
Ｖｋ  ＝  Ｗｋ  −  （１−ＰＲｉ）  ×  Ｄｉｋ
ただし、
Ｗｋ：ｉ番目の既存の処理装置２の担当範囲のうち、ステップＳ０９で選択したＹｉ個の担当範囲に対応する仮想識別子の値（ｋ＝１、２、・・・、Ｙｉ）
Ｄｉｋ：ステップＳ０９で選択したＹｉ個の担当範囲のうち、Ｙｉ番目の担当範囲の担当範囲サイズ
【００６６】
ステップＳ１４、ステップＳ１５によれば、新たな処理装置２のＹｉ番目の仮想識別子を、ｉ番目の既存の処理装置２のＹｉ番目の担当範囲内に配置すると、ｉ番目の既存の処理装置２のＹｉ番目の担当範囲を２分することになる。このとき、その２分された２つの担当範囲（一方の担当範囲は、新たな処理装置２の担当範囲となる）の担当範囲サイズの比は、ＰＲｉに等しい。
【００６７】
ステップＳ１６において、負荷分散装置１の制御部は、新たな処理装置２の追加に対して、識別子管理テーブルＴ１と、負荷管理テーブルＴ２とを更新する。ステップＳ１６の処理は、主に、識別子割当部１５の機能に従う。ステップＳ１６の後、ステップＳ１７に進む。
【００６８】
具体的には、識別子管理テーブルＴ１と、負荷管理テーブルＴ２において、新たな処理装置２のためのレコードを作成する。そして、負荷分散装置１は、周知の方法で決定され、新たな処理装置２に割り当てた親識別子を、識別子管理テーブルＴ１の「親識別子」のフィールド、負荷管理テーブルＴ２の「親識別子」のフィールドに追加する。また、周知の方法で決定され、新たな処理装置２に割り当てた振り分け先アドレスを、負荷管理テーブルＴ２の「振り分け先アドレス」のフィールドに追加する。また、ステップＳ０２で特定した新たな処理装置２の性能指標値Ｐを、負荷管理テーブルＴ２の「性能指標値」のフィールドに追加する。また、ステップ１５で決定した新たな処理装置２のＹｉ個の仮想識別子の値Ｖｋを、識別子管理テーブルＴ１の「仮想識別子」のフィールドに追加する。新たな処理装置２のＹｉ個の仮想識別子をＩＤ空間に配置することに伴い、新たな処理装置２および既存の処理装置２に関して、識別子管理テーブルＴ１の「担当範囲サイズ」のフィールドの値、負荷管理テーブルＴ２の「合計担当範囲サイズ」のフィールドの値は、適宜追加および変更される。
【００６９】
ステップＳ１７において、負荷分散装置１の制御部は、
ｉ  ≧  Ｎ
という関係式を満たすか否か判定する。前記関係式を満たす場合（ステップＳ１７でＹｅｓ）、図３の処理全体を終了する。新たな処理装置２に割り当てるＸ個すべての仮想識別子についてＩＤ空間の所定の位置に配置した（またはステップＳ１３により配置を中断した）からである。一方、前記関係式を満たさない場合（ステップＳ１７でＮｏ）、ステップＳ１８に進む。
【００７０】
ステップＳ１８において、負荷分散装置１の制御部は、既存の処理装置２に対して用いられる変数ｉをインクリメントする。ステップＳ１８の後、ステップＳ９に戻る。これにより、既存の他の処理装置２の担当範囲に配置することになる、新たな処理装置２の１または複数の仮想識別子の割り当てを実行する。
以上で、図３の処理の説明を終了する。
【００７１】
（分散システムの他の形態）
図１に示す分散システムの負荷分散装置１は、単一の負荷分散プログラムにより動作する単一の装置として説明した。しかし、コンシステント・ハッシュ法を実行する負荷分散装置１は、複数であってもよい。
【００７２】
図４は、分散システムの他の形態の構成図である。図１に示す分散システムとの相違点は、負荷分散装置１が複数存在し、各負荷分散装置１が同一の負荷分散プログラムを備えている点と、ロードバランサ４が存在する点である。各負荷分散装置１が備える負荷分散プログラムは、協調して動作することができる。
【００７３】
ロードバランサ４は、クライアント３から受信したメッセージを、例えばラウンドロビンによって、負荷分散装置１のそれぞれに振り分ける。負荷分散装置１は、ロードバランサ４から振り分けられたメッセージを、処理装置２に対して再度振り分ける。
【００７４】
各負荷分散装置１はそれぞれ、同一の識別子管理テーブルＴ１と、同一の負荷管理テーブルＴ２とを有している。１つの識別子管理テーブルＴ１または１つの同一の負荷管理テーブルＴ２が更新されれば、残りの識別子管理テーブルＴ１または残りの同一の負荷管理テーブルＴ２も同様に更新することができる。よって、ロードバランサ４からいずれの負荷分散装置１に振り分けられても、まったく同じ論理によってメッセージの振り分け先となる処理装置２を一意に決定することができる。識別子管理テーブルＴ１または同一の負荷管理テーブルＴ２の更新契機は、基本的には、処理装置２の追加（増設）と削除（減設）だけである。よって、すべての識別子管理テーブルＴ１およびすべての負荷管理テーブルＴ２の内容を同一にする必要があったとしても、処理装置２の追加と削除との頻度が十分に小さければ、識別子管理テーブルＴ１および負荷管理テーブルＴ２の更新処理に必要な処理量は、負荷分散処理（呼処理など）に比べて無視できるほど小さい。
【００７５】
図５は、分散システムのさらに他の形態の構成図である。図４に示す分散システムとの相違点は、負荷分散装置１と処理装置２と組み合わせて一体化した装置として構成されている点である。この場合、負荷分散装置１として機能させるプログラムと、処理装置２として機能させるプログラムとを統合し、前記した負荷分散プログラムとすることができる。前記一体化した装置に含まれる負荷分散装置１は、ロードバランサ４から振り分けられたメッセージを、その負荷分散装置１と一体化した処理装置２または、その他の処理装置２に振り分ける。各処理装置２は、振り分けられたメッセージを呼処理する。例えば、コンシステント・ハッシュ法を用いた一般的なデータストアは、この図５に示す構成をとる場合が多い。
【００７６】
図４または図５に示す分散システムの構成であっても、図１に示す分散システムと同等の効果を奏することができる。
【００７７】
≪まとめ≫
本実施形態によれば、処理装置に複数の処理装置識別子（つまり、仮想識別子）を割り当てることができる負荷分散装置において、処理装置の処理性能の違いに応じて、分散システムにおける負荷分散を最適化することができる。分散システムを構成する既存の処理装置２の処理性能が均一でない、つまり性能指標値が同一でない場合であっても、新たな処理装置２を追加するときは、新たな処理装置２を含む各処理装置２のそれぞれの性能指標値の比に合致するといった調整を実現できるように、新たな処理装置２の仮想識別子の値を決定するからである（主に、図３ＢのステップＳ１０の処理を参照）。これにより、既存の処理装置２に対して負荷を均等に分散させたいという要求を満たしつつも、処理装置２の処理性能の不均一性と負荷分散性とを両立する。
【００７８】
また、本実施形態によれば、相対的に大きな負荷を分担する既存の処理装置２の担当範囲内に、新たな処理装置２の仮想識別子をより多く配置し、そのような既存の処理装置２が分担する負荷を優先的に小さくすることができる（主に、図３ＡのステップＳ０７の処理を参照）。よって、新たな処理装置２を追加するときは、前記した調整を、より高い精度で行うことができる。
【００７９】
また、本実施形態によれば、既存の処理装置２が有する１または複数の担当範囲のうち、新たな処理装置２に譲るに相応しい担当範囲を特定することができる（主に、図３ＢのステップＳ０９の処理を参照）。よって、新たな処理装置２を追加するときは、前記した調整を、より高い精度で行うことができる。
【００８０】
≪その他≫
前記実施形態は、本発明を実施するために好適のものであるが、その実施形式はこれらに限定されるものでなく、本発明の要旨を変更しない範囲内において種々変形することが可能である。
【００８１】
例えば、本実施形態は、処理装置２がＨＴＴＰ（HyperText Transfer Protocol）サーバである場合、メッセージに含まれており、ＩＤ空間に配置されることになるデータ識別子は、メッセージが要求するＵＲＬ（Uniform Resource Locator）、クライアント３のＩＰアドレス、Ｃｏｏｋｉｅなど、といったさまざまな情報を用いることができる。
【００８２】
また、例えば、本実施形態では、ＩＤ空間に配置する仮想識別子を求めるために、処理装置２のＩＰアドレスを用いた。しかし、前記したＩＰアドレスの代わりに、例えばＭＡＣ（Media Access Control address）アドレスを用いてもよい。また、ＩＰアドレスやＭＡＣアドレスのように、分散システムのネットワーク上で処理装置２を特定できる機能を持つのであればどのような種類のアドレスを用いてもよい。
【００８３】
また、例えば、本実施形態では、分散システムに処理装置２を増設する場合について説明した。しかし、分散システムの処理装置２を減設する場合にも、本発明の考え方を応用することができる。つまり、分散システムの負荷分散性が、減設後の残りの処理装置２の性能指標値の不均一性を考慮して、減設すべき処理装置２を特定することができる。
【００８４】
また、例えば、本実施形態では、分散システムに処理装置２を１つ増設する場合について説明した。しかし、分散システムに処理装置２を２つ以上同時増設する場合についても、本発明の考え方を応用することができる。つまり、２つ以上同時増設する処理装置２のそれぞれに対して割り当てる１または複数の仮想識別子を、ＩＤ空間に一度にまとめて配置した場合に相当すると考えることができる。
【００８５】
また、本実施形態で説明した種々の技術を適宜組み合わせた技術を実現することもできる。
また、本実施形態で説明したソフトウェアをハードウェアとして実現することもでき、ハードウェアをソフトウェアとして実現することもできる。
【００８６】
その他、ハードウェア、ソフトウェア、テーブル、フローチャートなどの具体的な構成について、本発明の趣旨を逸脱しない範囲で適宜変更が可能である。
【符号の説明】
【００８７】
１          負荷分散装置
２          処理装置
３          クライアント
４          ロードバランサ
１１        処理装置検出部
１２        性能指標値特定部
１３        識別子割当個数決定部
１４        識別子割当担当範囲選択部
１５        識別子割当部
Ｔ１        識別子管理テーブル
Ｔ２        負荷管理テーブル
【図１】
0005690287.tif 000002
【図２】
0005690287.tif 000003
【図３Ａ】
0005690287.tif 000004
【図３Ｂ】
0005690287.tif 000005
【図４】
0005690287.tif 000006
【図５】
0005690287.tif 000007
【図６】
0005690287.tif 000008