(57)【要約】【課題】サーバの処理量及びメモリ使用量を考慮した負荷分散を行うこと。【解決手段】ドメイン分類部は、クライアントから受信するであろう処理の実行要求の処理内容を示すキー情報のハッシュ値を算出し、算出したハッシュ値に基づいて、処理の実行要求を所定の数のドメインに分類する。要求処理サーバ割当部は、ドメインのそれぞれを、実行要求の要求頻度が所定の閾値以下となる分割ドメインに分割し、各ドメインにおける分割ドメインを、複数の要求処理サーバのそれぞれに対する割当数が所定数以下となるように、割り当てる。要求処理サーバ決定部は、クライアントから処理の実行要求を受信した場合に、当該実行要求の処理内容を示すハッシュ値を算出して、算出したハッシュ値に基づいて、受信した実行要求が分類されたドメインを特定し、特定したドメインの分割ドメインが割り当てられた要求処理サーバを実行要求の転送先として決定する。【選択図】図２
2014096113.tif 000002
【特許請求の範囲】
【請求項１】
クライアント装置から受信した処理の実行要求を複数の要求処理サーバのうちのいずれかに転送する負荷分散装置であって、
前記クライアント装置から受信するであろう処理の実行要求の処理内容を示すキー情報のハッシュ値を算出し、算出したハッシュ値に基づいて、前記処理の実行要求を所定の数の管理単位に分類する分類部と、
前記管理単位のそれぞれを、前記実行要求の要求頻度が所定の閾値以下となる部分管理単位に分割し、各管理単位における部分管理単位を、前記複数の要求処理サーバのそれぞれに対する割当数が所定数以下となるように、割り当てる割当部と、
前記クライアント装置から処理の実行要求を受信した場合に、当該実行要求の処理内容を示すハッシュ値を算出して、算出したハッシュ値に基づいて、受信した実行要求が分類された管理単位を特定し、特定した管理単位の部分管理単位が割り当てられた要求処理サーバを前記実行要求の転送先として決定する決定部と、
を備えたことを特徴とする負荷分散装置。
【請求項２】
前記割当部は、前記要求処理サーバの処理性能を前記所定数で除算した値を前記所定の閾値として用いることを特徴とする請求項１に記載の負荷分散装置。
【請求項３】
前記割当部は、前記部分管理単位の総数を前記所定数で除算することで、前記部分管理単位を割り当てる要求処理サーバの台数を決定し、決定した台数の要求処理サーバに前記部分管理単位を割り当てることを特徴とする請求項１又は２に記載の負荷分散装置。
【請求項４】
前記割当部は、前記複数の要求処理サーバのうち、前記部分管理単位の割当数が最少であり、かつ、分割元の管理単位が割当予定の部分管理単位と同一となる部分管理単位の割当数が最少である要求処理サーバを前記割当予定の部分管理単位の割当先と決定することを特徴とする請求項１〜３のいずれか一つに記載の負荷分散装置。
【請求項５】
前記決定部は、同一の管理単位から分割された部分管理単位がそれぞれ異なる要求処理サーバに割り当てられていた場合に、前記要求処理サーバそれぞれに対して前記管理単位に属する実行要求の転送回数が略均等になるように前記実行要求を転送することを特徴とする請求項１〜４のいずれか一つに記載の負荷分散装置。
【請求項６】
前記管理単位ごとの前記実行要求の要求頻度を監視して、前記要求頻度を更新する更新部をさらに備え、
前記割当部は、前記更新部によって前記要求頻度が更新された場合に、前記管理単位を更新後の要求頻度が所定の閾値以下となる部分管理単位に再分割し、再分割後の部分管理単位の増減に応じて、前記複数の要求処理サーバへの割り当てを変更することを特徴とする請求項１〜５のいずれか一つに記載の負荷分散装置。
【請求項７】
前記割当部は、前記部分管理単位が増加した場合に、分割元の管理単位が同一となる部分管理単位の割当数が最少である要求処理サーバに増加分の部分管理単位を割り当てることを特徴とする請求項６に記載の負荷分散装置。
【請求項８】
前記割当部は、前記部分管理単位が減少した場合に、分割元の管理単位が同一となる部分管理単位の割当数が最多である要求処理サーバから減少分の部分管理単位の割り当てを解除することを特徴とする請求項６に記載の負荷分散装置。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、負荷分散装置に関する。
【背景技術】
【０００２】
従来、クライアントからの要求を処理するサーバシステムにおいて、要求量が多く、単一のサーバでは処理できない場合、クライアントとサーバシステムの間に負荷分散装置を設置し、負荷分散装置が要求を複数のサーバに振り分けることが広く行われている。ここで、負荷分散装置における負荷分散の方式として、いくつかの方式が知られている。例えば、ＤＮＳサーバの負荷分散などで広く利用されているラウンドロビン方式は、最も単純な負荷分散の方式であり、クライアントからの要求を各サーバに順番に振り分ける。ここで、ラウンドロビン方式では各サーバに均等な数の要求を割り振ることができるため、１要求あたりの処理負荷がおおよそ同じであれば、各サーバの処理負荷もおおむね均等になることが期待できる。
【０００３】
また、例えば、データ管理システムの一種であるキーバリューストア（Key-Value  Store）では、コンシステントハッシュ法（Consistent  Hashing）と呼ばれる負荷分散方式が使われることがある(例えば、非特許文献１)。コンシステントハッシュ法による負荷分散方式では、負荷分散装置が、要求に含まれるキー情報のハッシュ値を計算して、あらかじめ保持している、サーバとハッシュ値の範囲の対応関係に基づいて、要求をそのハッシュ値に対応するサーバに振り分ける。
【０００４】
コンシステントハッシュ法は、ハッシュ関数のランダム性から、各サーバにおおよそ均等な数のキー情報が割り当てられる方式であり、ラウンドロビン方式と異なり、要求に含まれるキー情報と要求の振り分け先のサーバの対応が固定される。そのため、各サーバが要求を処理するにあたって、要求に含まれるキー情報に対応するデータ(例えば、キーバリューストアにおけるバリュー)が必要な状況において、各サーバは全てのキー情報のデータを保持しておく必要が無く、自サーバに振り分けられるキー情報のデータだけを保持していればよい。
【０００５】
この特性は、全キー情報分のデータサイズが大きい場合に有用であり、例えば、サーバが高速に要求を処理するために、キー情報に対応するデータをメモリ上に保持しておく必要がある場合、各サーバが全てのキー情報のデータをメモリに保持する必要があるラウンドロビン方式はメモリ容量の制約から適用できない可能性があるが、そのような場合であってもコンシステントハッシュ法は適用可能である。
【０００６】
一方、コンシステントハッシュ法は、キー情報毎の要求頻度に大きな偏りがある場合に、サーバの処理負荷が均等にならないという課題がある。例えば、要求頻度が平均的なキー情報の要求頻度に比べて非常に高いキー情報があり、そのキー情報の要求頻度が単一のサーバの処理性能を越える場合は、コンシステントハッシュ法をそもそも適用できない。また、単一のサーバの処理性能は越えていない場合であっても、要求頻度の非常に高いキー情報を割り当てられたサーバとそうでないサーバの処理負荷に大きな偏りが生じ、システム全体としてサーバの処理性能を有効に活用できない。
【０００７】
このようなコンシステントハッシュ法におけるサーバの処理負荷の偏りを解決するために、仮想ノードと呼ばれる技術を拡張し、各サーバに割り当てるキー情報の数を調整することで、サーバの処理負荷の偏りを軽減する方式が提案されている(例えば、特許文献１)。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２０１２−４８４２４号公報
【非特許文献】
【０００９】
【非特許文献１】D. Karger, E. Lehman, T. Leighton, M. Levine, D. Lewin, and R. Panigrahy, "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web," in Proceedings of the 29th ACM Symposium on Theory of Computing (STOC'97), pp.654-663, May 1997.
【発明の概要】
【発明が解決しようとする課題】
【００１０】
しかしながら、上述した従来技術では、サーバの処理量及びメモリ使用量を考慮した負荷分散を行うことが困難であった。例えば、上述した従来技術では、各サーバに割り当てるキー情報の数がサーバ毎に異なってしまうと、処理負荷の偏りは軽減されたとしても、サーバが保持するデータサイズに偏りが生じてしまう。従って、上述した従来技術では、各サーバのメモリ使用量に偏りが生じてしまうこととなり、サーバの処理量及びメモリ使用量を考慮した負荷分散を行うことが困難であった。その結果、上述した従来技術では、システム全体としてメモリ使用量を有効に活用できない。
【００１１】
そこで、本願に係る技術は、上述した従来技術の問題に鑑みてなされたものであって、サーバの処理量及びメモリ使用量を考慮した負荷分散を行うことを可能とする負荷分散装置を提供することを目的とする。
【課題を解決するための手段】
【００１２】
上述した課題を解決し、目的を達成するため、本願の装置は、クライアント装置から受信した処理の実行要求を複数の要求処理サーバのうちのいずれかに転送する負荷分散装置であって、分類部と、割当部と、決定部とを備える。分類部は、前記クライアント装置から受信するであろう処理の実行要求の処理内容を示すキー情報のハッシュ値を算出し、算出したハッシュ値に基づいて、前記処理の実行要求を所定の数の管理単位に分類する。割当部は、前記管理単位のそれぞれを、前記実行要求の要求頻度が所定の閾値以下となる部分管理単位に分割し、各管理単位における部分管理単位を、前記複数の要求処理サーバのそれぞれに対する割当数が所定数以下となるように、割り当てる。決定部は、前記クライアント装置から処理の実行要求を受信した場合に、当該実行要求の処理内容を示すハッシュ値を算出して、算出したハッシュ値に基づいて、受信した実行要求が分類された管理単位を特定し、特定した管理単位の部分管理単位が割り当てられた要求処理サーバを前記実行要求の転送先として決定する。
【発明の効果】
【００１３】
本願の装置は、サーバの処理量及びメモリ使用量を考慮した負荷分散を行うことを可能にする。
【図面の簡単な説明】
【００１４】
【図１】図１は、第１の実施形態に係る情報処理システムの構成の一例を示す図である。
【図２】図２は、第１の実施形態に係る負荷分散装置の構成の一例を示す図である。
【図３】図３は、第１の実施形態に係るドメイン開始ハッシュ値テーブルによって記憶される情報の一例を示す図である。
【図４】図４は、第１の実施形態に係るドメイン要求頻度テーブルによって記憶される情報の一例を示す図である。
【図５】図５は、第１の実施形態に係る要求処理サーバ割当テーブルによって記憶された情報の一例を示す図である。
【図６】図６は、第１の実施形態に係る要求処理サーバ割当状態管理テーブルによって記憶される情報の一例を示す図である。
【図７】図７は、第１の実施形態に係る要求処理サーバ割当部によるドメインの分割処理の一例を説明するための図である。
【図８】図８は、第１の実施形態に係る要求処理サーバ割当部による割当処理の一例を説明するための図である。
【図９】図９は、第１の実施形態に係る情報処理システムにおける分割ドメインの割当処理の手順を説明するためのシーケンス図である。
【図１０】図１０は、第１の実施形態に係る負荷分散装置による要求処理サーバ割当処理の手順を説明するためのフローチャートである。
【図１１】図１１は、第１の実施形態に係る負荷分散装置による要求処理サーバ割当処理の手順を説明するためのフローチャートである。
【図１２】図１２は、第１の実施形態に係る情報処理システムにおけるサービス要求の応答処理の手順を説明するためのシーケンス図である。
【図１３】図１３は、第１の実施形態に係る負荷分散装置による要求処理サーバ決定処理の手順を説明するためのフローチャートである。
【図１４】図１４は、第１の実施形態に係る要求処理サーバによるサービス応答作成処理の手順を説明するためのフローチャートである。
【図１５】図１５は、第１の実施形態に係る情報処理システムにおいて、ドメイン分割数が増加した場合の割当変更処理の手順を説明するためのシーケンス図である。
【図１６】図１６は、第１の実施形態に係る負荷分散装置によるドメイン分割数が増加した場合の要求処理サーバ割当変更処理の手順を説明するためのフローチャートである。
【図１７】図１７は、第１の実施形態に係る情報処理システムにおいて、ドメイン分割数が減少した場合の割当変更処理の手順を説明するためのシーケンス図である。
【図１８】図１８は、第１の実施形態に係る負荷分散装置によるドメイン分割数が減少した場合の要求処理サーバ割当変更処理の手順を説明するためのフローチャートである。
【発明を実施するための形態】
【００１５】
以下に添付図面を参照して、本願に係る負荷分散装置の実施形態を詳細に説明する。なお、本願に係る負荷分散装置は、以下の実施形態により限定されるものではない。
【００１６】
［第１の実施形態］
［第１の実施形態に係る情報処理システムの構成］
以下では、まず、第１の実施形態に係る負荷分散装置を含む情報処理システムの全体の構成について説明した後、負荷分散装置の詳細な構成について説明する。図１は、第１の実施形態に係る情報処理システム１の構成の一例を示す図である。
【００１７】
図１に示すように、第１の実施形態に係る情報処理システム１は、クライアント１１〜１３と、負荷分散装置３０と、要求処理サーバ４１〜４５と、ストレージ装置５１とを有する。そして、クライアント１１〜１３と負荷分散装置３０とは、ＩＰネットワーク２１で接続され、負荷分散装置３０と要求処理サーバ４１〜４５とは、ＩＰネットワーク２２で接続され、要求処理サーバ４１〜４５とストレージ装置５１とは、ＩＰネットワーク２３で接続される。ＩＰネットワーク２１〜２３は、インターネットサービスを提供するプロバイダによってそれぞれ構成されたＩＰ（Internet Protocol）網である。
【００１８】
ここで、クライアント１１〜１３は、３台のみ図示されているが、実際にはさらに多数のクライアントがＩＰネットワーク２１に接続されている。また、要求処理サーバ４１〜４５は、５台のみ図示されているが、実際にはさらに多数の要求処理サーバがＩＰネットワーク２２及びＩＰネットワーク２３に接続されている。そして、複数のクライアント及び複数の要求処理サーバは、それぞれ同一の機能を有することから、以下の説明では、複数のクライアントをまとめてクライアント１０とし、複数の要求処理サーバをまとめて要求処理サーバ４０として説明する。
【００１９】
クライアント１０は、いずれかの要求処理サーバ４０に実行させる処理の実行に必要なキー情報（サービス指定値）を含むサービス要求を生成する。そして、クライアント１０は、生成したサービス要求を負荷分散装置３０に発行する。その後、クライアント１０は、負荷分散装置３０を介して、いずれかの要求処理サーバ４０による処理の実行結果を取得する。
【００２０】
要求処理サーバ４０は、高速にアクセス可能なメモリを有し、ストレージ装置５１に保持される全ての制御データのうち、負荷分散装置３０から送信される割当ドメイン情報通知に基づいて、自身に割り当てられたドメインのサービス要求の処理を実行するために必要な制御データ（属性値情報）をストレージ装置５１から取得して、メモリに記憶する。そして、要求処理サーバ４０は、負荷分散装置３０からサービス要求を受信した場合には、受信したサービス要求に含まれるキー情報と対応付けられた制御データをメモリ上で検索し、検索した制御データを応答として負荷分散装置３０に送信する。 なお、割当ドメイン情報通知については、後に詳述する。
【００２１】
ストレージ装置５１は、すべてのキー情報（サービス指定値）に対応する制御データ（属性値情報）をディスク上に保持しており、要求処理サーバ４０から送信された属性値情報要求に含まれるドメインに属する全てのキー情報とその属性値情報のペアをディスクから取得し、属性値情報応答として要求処理サーバ４０に送信する。また、ストレージ装置５１は、属性値情報要求に含まれるドメインから当該ドメインに属するキー情報を算出するため、負荷分散装置３０からドメイン開始ハッシュ値テーブルの内容が通知され、当該テーブルと同じ内容を保持する。なお、ドメイン開始ハッシュ値テーブルについては、後に詳述する。
【００２２】
負荷分散装置３０は、クライアントから送信されたサービス要求に含まれるキー情報（サービス指定値）に基づいて、当該サービス要求を処理させる要求処理サーバ４０を決定し、その要求処理サーバ４０にサービス要求を送信する。そして、負荷分散装置３０は、サービス要求に対応するサービス応答を要求処理サーバ４０から受信すると、当該サービス応答をクライアントに送信する。そして、負荷分散装置３０は、サービス要求量の増加に備えて、未使用の要求処理サーバ４０の情報をサーバプール情報として保持しており、サービス要求量が増加した場合には、サーバプール情報から未使用の要求処理サーバ４０の情報を取得し、当該要求処理サーバ４０に割当ドメイン情報通知を送信することで、サービス要求の処理を開始させることができる。逆に、サービス要求量が減少し、割当ドメインが無くなった要求処理サーバ４０はサーバプール情報に記録される。なお、図１においては、負荷分散装置３０は１台であるが、冗長化のために負荷分散装置３０を並列に複数設置することも可能であり、その場合に負荷分散装置３０の構成は変わらない。以下、図２を用いて、負荷分散装置３０の詳細について説明する。
【００２３】
図２は、第１の実施形態に係る負荷分散装置３０の構成の一例を示す図である。例えば、負荷分散装置３０は、図２に示すように、通信制御Ｉ／Ｆ部３１と、入力部３２と、表示部３３と、記憶部３４と、制御部３５とを有する。
【００２４】
通信制御Ｉ／Ｆ部３１は、クライアント１０と制御部３５との間でやり取りする各種情報に関する通信を制御する。また、通信制御Ｉ／Ｆ部３１は、要求処理サーバ４０と制御部３５との間でやり取りする各種情報に関する通信を制御する。例えば、通信制御Ｉ／Ｆ部３１は、サービス要求及びサービス応答の送受信を制御する。また、通信制御Ｉ／Ｆ部３１は、入力部３２及び表示部３３と、制御部３５との間での各種情報のやり取りを制御する。
【００２５】
入力部３２は、例えば、キーボードやマウスなどであり、ユーザによる種々の情報の入力処理を受付ける。一例を挙げると、入力部３２は、ドメインの分類に用いられる閾値の入力処理などを受付ける。なお、ドメインの分類に用いられる閾値については後述する。表示部３３は、例えば、ディスプレイなどであり、ユーザに対して処理結果を表示出力する。
【００２６】
記憶部３４は、図２に示すように、ドメイン開始ハッシュ値テーブル３４ａと、ドメイン要求頻度テーブル３４ｂと、要求処理サーバ割当テーブル３４ｃと、要求処理サーバ割当状態管理テーブル３４ｄとを備える。記憶部３４は、例えば、ハードディスク、光ディスクなどの記憶装置、または、ＲＡＭ（Random Access Memory）、フラッシュメモリ（Flash Memory）などの半導体メモリ素子であり、負荷分散装置３０によって実行される各種プログラムなどを記憶する。
【００２７】
ドメイン開始ハッシュ値テーブル３４ａは、クライアント１０から受信するサービス要求をキー情報に基づいて分類するための管理単位（ドメイン）の範囲を示す開始ハッシュ値を記憶する。具体的には、ドメイン開始ハッシュ値テーブル３４ａは、後述する制御部３５によってサービス要求のキー情報から算出されたハッシュ値に応じて分類されたドメインを識別するための情報を記憶する。図３は、第１の実施形態に係るドメイン開始ハッシュ値テーブル３４ａによって記憶される情報の一例を示す図である。
【００２８】
例えば、ドメイン開始ハッシュ値テーブル３４ａは、図３に示すように、開始ハッシュ値とドメインとを対応づけた情報を記憶する。ここで、図３における「開始ハッシュ値」とは、各ドメインの範囲の開始となるハッシュ値を意味する。また、図３に示す「ドメイン」とは、クライアントから受信するサービス要求をキー情報のハッシュ値で分類して管理するための管理単位を意味する。
【００２９】
一例を挙げると、ドメイン開始ハッシュ値テーブル３４ａは、図３に示すように、「開始ハッシュ値：００１３、ドメイン：ドメインＤ」、「開始ハッシュ値：１１５６、ドメイン：ドメインＡ」、「開始ハッシュ値：２６３２、ドメイン：ドメインＨ」などを記憶する。これらの情報は、例えば、ハッシュ値が「００１３」〜「１１５５」までのキー情報に対応するサービス要求が、「ドメインＤ」に属することを意味する。同様に、例えば、ハッシュ値が「１１５６」〜「２６３１」までのキー情報に対応するサービス要求が、「ドメインＡ」に属することを意味する。すなわち、ドメイン開始ハッシュ値テーブル３４ａは、ドメインごとのハッシュ値の範囲を記憶する。
【００３０】
図２に戻って、ドメイン要求頻度テーブル３４ｂは、ドメインごとのサービス要求の要求頻度と、要求頻度に応じたドメインの分割数を記憶する。図４は、第１の実施形態に係るドメイン要求頻度テーブル３４ｂによって記憶される情報の一例を示す図である。例えば、ドメイン要求頻度テーブル３４ｂは、図４に示すように、ドメインごとに、要求頻度（／秒）とドメイン分割数とを対応付けた情報を記憶する。
【００３１】
一例を挙げると、ドメイン要求頻度テーブル３４ｂは、図４に示すように、「ドメインＡ」に「要求頻度（／秒）：２８０」と「ドメイン分割数：１」とを対応付けた情報を記憶する。この情報は、「ドメインＡ」に属するサービス要求を１秒間に２８０回受信しており、ドメインの分割数が「１」であることを意味する。なお、ドメイン分割数の詳細については、後述する。同様に、ドメイン要求頻度テーブル３４ｂは、ドメインＢ〜ドメインＨまでの要求頻度及びドメイン分割数を記憶する。
【００３２】
図２に戻って、要求処理サーバ割当テーブル３４ｃは、各ドメインに属するサービス要求の転送先の要求処理サーバ４０の情報を記憶する。具体的には、要求処理サーバ割当テーブル３４ｃは、後述する制御部３５によってドメインごとに決定されたサービス要求を実行する要求処理サーバの数と転送先の情報を記憶する。図５は、第１の実施形態に係る要求処理サーバ割当テーブル３４ｃによって記憶された情報の一例を示す図である。
【００３３】
例えば、要求処理サーバ割当テーブル３４ｃは、図５に示すように、ドメインに要求処理サーバを対応付けた情報を記憶する。一例を挙げると、「ドメインＡ：サーバ４１」、「ドメインＢ：サーバ４２、サーバ４３、サーバ４４、サーバ４５」、「ドメインＣ：サーバ４６、サーバ４１」などの情報を記憶する。これらの情報は、例えば、「ドメインＡ」に属するサービス要求の転送先が「要求処理サーバ４１」であり、「ドメインＢ」に属するサービス要求の転送先が「要求処理サーバ４２」、「要求処理サーバ４３」、「要求処理サーバ４４」、「要求処理サーバ４５」のいずれかであり、「ドメインＣ」に属するサービス要求の転送先が「要求処理サーバ４６」又は「要求処理サーバ４１」であることを意味する。同様に、要求処理サーバ割当テーブル３４ｃは、すべてのドメインについて、サービス要求を転送する転送先の要求処理サーバ４０の情報を記憶する。
【００３４】
図２に戻って、要求処理サーバ割当状態管理テーブル３４ｄは、要求処理サーバ４０ごとに、転送先として割り当てられたドメインの情報を記憶する。図６は、第１の実施形態に係る要求処理サーバ割当状態管理テーブル３４ｄによって記憶される情報の一例を示す図である。例えば、要求処理サーバ割当状態管理テーブル３４ｄは、図６に示すように、要求処理サーバに割当ドメインを対応付けた情報を記憶する。
【００３５】
一例を挙げると、要求処理サーバ割当状態管理テーブル３４ｄは、図６に示すように、「サーバ４１：ドメインＡ、ドメインＣ、ドメインＦ」や、「サーバ４２：ドメインＢ、ドメインＤ、ドメインＧ」などの情報を記憶する。すなわち、これらの情報は、「要求処理サーバ４１」が「ドメインＡ」、「ドメインＣ」及び「ドメインＦ」に属するサービス要求の転送先であり、「要求処理サーバ４２」が「ドメインＢ」、「ドメインＤ」及び「ドメインＧ」に属するサービス要求の転送先であることを意味する。同様に、要求処理サーバ割当状態管理テーブル３４ｄは、その他の要求処理サーバについて転送先として割り当てられたドメインの情報を記憶する。
【００３６】
図２に戻って、制御部３５は、ドメイン分類部３５ａと、要求処理サーバ割当部３５ｂと、割当ドメイン情報通知部３５ｃと、要求処理サーバ決定部３５ｄと、要求頻度更新部３５ｅとを備える。制御部３５は、例えば、ＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路やＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路であり、負荷分散装置３０の全体制御を実行する。
【００３７】
ドメイン分類部３５ａは、実行要求の処理内容を示すキー情報（サービス指定値）のハッシュ値に応じて、クライアント１０から受信する処理の実行要求を所定の数の管理単位（ドメイン）に分類する。具体的には、ドメイン分類部３５ａは、サービス要求に含まれるキー情報のハッシュ値が取り得る値の範囲をあらかじめ定める数のドメインに分割して、ドメイン開始ハッシュ値テーブル３４ａに情報を格納する。
【００３８】
例えば、ドメイン分類部３５ａは、ドメイン数を「８」、ハッシュ値の範囲を「００００」〜「９９９９」として、ランダムなハッシュ値を各ドメインの開始ハッシュ値として算出する。そして、ドメイン分類部３５ａは、例えば、図３に示すような情報を、ドメイン開始ハッシュ値テーブル３４ａに格納する。
【００３９】
要求処理サーバ割当部３５ｂは、ドメインごとに、実行要求の要求頻度が所定の閾値以下となる分割ドメインに分割し、各ドメインにおける分割ドメインを、複数の要求処理サーバ４０に所定の割当数以下でそれぞれ割り当てる。具体的には、要求処理サーバ割当部３５ｂは、要求処理サーバの処理性能を所定の割当数で除算した値を所定の閾値として用いドメインを分割ドメインに分割する。図７は、第１の実施形態に係る要求処理サーバ割当部３５ｂによるドメインの分割処理の一例を説明するための図である。
【００４０】
ここで、図７においては、図３に示すように、ドメイン分類部３５ａによってサービス要求が８つのドメインに分類された場合の処理について示す。例えば、要求処理サーバ割当部３５ｂは、図７に示すように、各ドメインの要求頻度を取得し、取得した要求頻度に応じて、各ドメインを分割ドメインに分割する。ここで、要求処理サーバ割当部３５ｂは、キー情報（サービス指定値）ごとの要求頻度が判明している場合には、ドメイン開始ハッシュ値テーブル３４ａによって記憶される情報を参照して、各ドメインの要求頻度を算出する。
【００４１】
一方、キー情報（サービス指定値）ごとの要求頻度が判明していない場合には、要求処理サーバ割当部３５ｂは、クライアント１０から受信する全体のサービス要求量をドメイン数で除算した値を各ドメインの要求頻度の暫定値として設定する。かかる場合には、要求処理サーバ割当部３５ｂは、その後の処理に伴って判明する実際のドメインごとの要求頻度に応じて、暫定値を実測値に更新する。
【００４２】
要求処理サーバ割当部３５ｂは、上述したように、各ドメインの要求頻度を取得して、要求頻度に応じた分割ドメインに分割する。例えば、要求処理サーバ割当部３５ｂは、図７に示すように、要求処理サーバ４０の処理性能「９００（／秒）」を所定の割当数「３」で除算した値「３００」を所定の閾値とする。そして、要求処理サーバ割当部３５ｂは、各ドメインの要求頻度を所定の閾値「３００」で除算し、小数点以下の値を切り上げて整数としたものをドメイン分割数として決定する。
【００４３】
要求処理サーバ割当部３５ｂは、取得した各ドメインの要求頻度と、決定したドメイン分割数をドメイン要求頻度テーブル３４ｂに格納するとともに、図７の右側の図に示すように、各ドメインを対応するドメイン分割数で分割する。一例を挙げると、要求処理サーバ割当部３５ｂは、「ドメインＢ」の「要求頻度：１０５０」を所定の閾値「３００」で除算した値「３．５」の小数点以下を切り上げた「４」で「ドメインＢ」を「分割ドメインＢ１」、「分割ドメインＢ２」、「分割ドメインＢ３」、「分割ドメインＢ４」に分割する。同様に、要求処理サーバ割当部３５ｂは、各ドメインをドメイン分割数でドメインを分割ドメインに分割する。
【００４４】
さらに、要求処理サーバ割当部３５ｂは、分割ドメインの総数を所定の割当数で除算することで、分割ドメインを割り当てる要求処理サーバ４０の台数を決定し、決定した台数の要求処理サーバ４０に分割ドメインを割り当てる。ここで、要求処理サーバ割当部３５ｂは、複数の要求処理サーバ４０のうち、分割ドメインの割当数が最少であり、かつ、分割元のドメインが割当予定の分割ドメインと同一となる分割ドメインの割当数が最少である要求処理サーバ４０を割当予定の分割ドメインの割当先と決定する。
【００４５】
図８は、第１の実施形態に係る要求処理サーバ割当部３５ｂによる割当処理の一例を説明するための図である。ここで、図８においては、図７に示す分割処理の後の処理について示す。例えば、要求処理サーバ割当部３５ｂは、図８の左側の図に示すように、分割ドメイン「Ａ１」〜「Ｈ３」の個数「１８」を所定の割当数「３」で除算した値「６」を要求処理サーバ４０の台数とする。そして、要求処理サーバ割当部３５ｂは、要求処理サーバ４１〜４６の６台のサーバを割当対象のサーバとして決定して、各要求処理サーバに分割ドメインを割当てる。
【００４６】
このとき、要求処理サーバ割当部３５ｂは、上述した手法により分割ドメインを割り当てる。例えば、要求処理サーバ割当部３５ｂは、分割ドメインＡ１を要求処理サーバ４１に割り当てた後、分割ドメインＢ１〜Ｂ４を割り当てる場合、まず、分割ドメインの割当数が最少の要求処理サーバ４２〜４６を抽出する（要求処理サーバ４１は、分割ドメインＡ１が割り当てられているため、最少ではない）。そして、要求処理サーバ割当部３５ｂは、分割ドメインＢ１から順に要求処理サーバに割り当てる。ここで、要求処理サーバ割当部３５ｂは、分割ドメインの割当数が最少であり、かつ、分割元のドメインが割当予定の分割ドメインと同一となる分割ドメインの割当数が最少である要求処理サーバ４０を割当予定の分割ドメインの割当先と決定する。
【００４７】
すなわち、要求処理サーバ割当部３５ｂは、仮に図８の右側の図で要求処理サーバが４台（サーバ４１〜４４まで）であった場合には、分割ドメインＢ４を、分割元が同一である分割ドメインＢ１〜Ｂ３が割り当てられたサーバ４２〜４４ではなく、サーバ４１に割り当てるように制御する。同様に要求処理サーバ割当部３５ｂは、図８の右側の図に示すように、ドメインＣ〜Ｈにおける各分割ドメインを要求処理サーバ４１〜４６に順に割り当てる。そして、要求処理サーバ割当部３５ｂは、割当後の情報を、要求処理サーバ割当テーブル３４ｃ及び要求処理サーバ割当状態管理テーブル３４ｄにそれぞれ格納する。
【００４８】
第１の実施形態に係る負荷分散装置３０では、上述したように、キー情報（サービス指定値）のハッシュ値に基づいて、サービス要求を複数のドメインに分類することで、ハッシュ関数のランダム性から各ドメインのキー情報の数をおよそ均等にして、メモリ使用量をおよそ均等にすることができる。さらに、負荷分散装置３０は、各ドメインの要求頻度を、要求処理サーバ４０の処理性能の１／Ｎを閾値として分割し、各サーバにＮずつ割り当てることで、各要求処理サーバの処理量もおよそ均等にすることができる。
【００４９】
要求処理サーバ割当部３５ｂは、さらに、後述する要求頻度更新部３５ｅによって各ドメインの要求頻度が更新された場合に、ドメインを更新後の要求頻度が所定の閾値以下となる分割ドメインに再分割し、再分割後の分割ドメインの増減に応じて、複数の要求処理サーバへの割り当てを変更する。なお、この処理については、後に詳述する。
【００５０】
図２に戻って、割当ドメイン情報通知部３５ｃは、要求処理サーバ割当部３５ｂによって要求処理サーバ割当状態管理テーブル３４ｄが更新された場合に、分割ドメインの割当てが変更された要求処理サーバ４０に対して割当ドメイン情報通知を行う。例えば、割当ドメイン情報通知部３５ｃは、図６に示す要求処理サーバ割当状態管理テーブル３４ｄの情報を参照して、要求処理サーバ４１に、ドメインＡ、ドメインＣ及びドメインＦの分割ドメインが割り当てられたことを通知する。すなわち、割当ドメイン情報通知部３５ｃは、要求処理サーバ４１に対してドメインＡ、ドメインＣ及びドメインＦのサービス要求に対する応答を実行するように通知する。
【００５１】
要求処理サーバ決定部３５ｄは、クライアント１０から処理の実行要求を受信した場合に、当該実行要求の処理内容を示すハッシュ値を算出して、算出したハッシュ値に対応するドメインの分割ドメインが割り当てられた要求処理サーバ４０を実行要求の転送先として決定する。具体的には、要求処理サーバ決定部３５ｄは、同一のドメインから分割された分割ドメインがそれぞれ異なる要求処理サーバ４０に割り当てられていた場合に、要求処理サーバ４０それぞれに対してドメインに属する実行要求の転送回数が略均等になるようにサービス要求を転送する。
【００５２】
例えば、要求処理サーバ決定部３５ｄは、ドメインＢに属するサービス要求を複数受信した場合に、要求処理サーバ４２〜４５へのドメインＢに属するサービス要求の転送回数が均等になるように転送先を決定して、サービス要求を転送する。
【００５３】
要求頻度更新部３５ｅは、ドメインごとの実行要求の要求頻度を監視して、要求頻度を更新する。具体的には、要求頻度更新部３５ｅは、サービス要求がクライアント１０から送出される頻度をドメイン分類部３５ａが分類したドメインごとにカウントし、ドメイン要求頻度テーブルを定期的に更新する。また、要求頻度更新部３５ｅは、あらかじめ定める閾値を越える要求頻度の増減があった場合に、要求処理サーバ割当部３５ｂに対して要求処理サーバ４０の割当を変更するよう通知する。
【００５４】
例えば、要求頻度更新部３５ｅは、ドメイン要求頻度テーブル３４ｂに記憶されたドメインごとのドメイン分割数が増減した場合に、増減した分の分割ドメインの割当てを変更する。
【００５５】
すなわち、要求処理サーバ割当部３５ｂは、分割ドメインが増加した場合に、分割元のドメインが同一となる分割ドメインの割当数が最少である要求処理サーバ４０に増加分の分割ドメインを割り当てる。一方、要求処理サーバ割当部３５ｂは、分割ドメインが減少した場合に、分割元のドメインが同一となる分割ドメインの割当数が最多である要求処理サーバ４０から減少分の分割ドメインの割り当てを解除する。
【００５６】
［第１の実施形態に係る負荷分散装置による処理の手順］
次に、第１の実施形態に係る負荷分散装置３０による処理の手順について、図９〜１８を用いて説明する。なお、以下では、分割ドメインの割当処理、サービス要求の応答処理及び割当変更処理の各手順について、情報処理システム１におけるシーケンス図と、負荷分散装置３０におけるフローチャートとを用いて順に説明する。
【００５７】
まず、図９〜１１を用いて、分割ドメインの割当処理について説明する。図９は、第１の実施形態に係る情報処理システム１における分割ドメインの割当処理の手順を説明するためのシーケンス図である。図９に示すように、負荷分散装置３０においては、ドメイン分類部３５ａが、ドメイン初期化処理を実行して（ステップＳ１０１）、ドメイン開始ハッシュ値テーブル３４ａに各ドメインの開始ハッシュ値を格納する。
【００５８】
そして、ドメイン開始ハッシュ値テーブル３４ａを格納すると、負荷分散装置３０は、ストレージ装置５１に対してドメイン開始ハッシュ値を通知する（ステップＳ１０２）。ストレージ装置５１は、ドメイン開始ハッシュ値の通知を受信すると、内容を自身のメモリ上に記憶して、ドメイン開始ハッシュ値応答を負荷分散装置３０に送信する（ステップＳ１０３）。
【００５９】
続いて、負荷分散装置３０においては、要求処理サーバ割当部３５ｂが、要求頻度初期化処理を実行して（ステップＳ１０４）、各ドメインの要求頻度とドメイン分割数をドメイン要求頻度テーブル３４ｂに格納する。そして、要求処理サーバ割当部３５ｂは、要求処理サーバ割当初期化処理を実行して（ステップＳ１０５）、要求処理サーバ４０の台数を決定して、各要求処理サーバ４０に分割ドメインを割り当てる。
【００６０】
割当ドメイン情報通知部３５ｃは、要求処理サーバ割当部３５ｂによって各要求処理サーバ４０に分割ドメインが割り当てられると、要求処理サーバ割当状態管理テーブル３４ｄによって記憶された情報を参照して、各要求処理サーバ４０に割当ドメイン情報を通知する（ステップＳ１０６）。割当ドメイン情報が通知されると、要求処理サーバ４０は、ストレージ装置５１に対して割り当てられたドメインの属性値情報を取得するための属性値情報要求を送信する（ステップＳ１０７）。ストレージ装置５１は、各要求処理サーバ４０に対して、受信した属性値情報要求に対応する属性値情報応答を送信する（ステップ
Ｓ１０８）。
【００６１】
ストレージ装置５１から属性値情報応答を受信すると、要求処理サーバ４０は、負荷分散装置３０に対して、割当ドメイン情報の通知に対する応答である割当ドメイン情報応答を送信する（ステップＳ１０９）。
【００６２】
次に、図９のステップＳ１０５で示す要求処理サーバ割当初期化処理の詳細について説明する。図１０及び図１１は、第１の実施形態に係る負荷分散装置３０による要求処理サーバ割当処理の手順を説明するためのフローチャートである。ここで、図１１に示す処理は、図１０のステップＳ２０２の処理の詳細を示す。
【００６３】
図１０に示すように、負荷分散装置３０においては、ドメイン要求頻度テーブル３４ｂにドメインの要求頻度及びドメイン分割数を格納すると、要求処理サーバ割当部３５ｂは、全ドメインの分割ドメイン数の合計と、サーバ分割数（所定の割当数）とから必要な要求処理サーバ数を決定し、決定した数の要求処理サーバ４０をサーバプール情報から取得して、要求処理サーバ割当状態管理テーブル３４ｄに各要求処理サーバ４０のレコードを追加する（ステップＳ２０１）。
【００６４】
続いて、要求処理サーバ割当部３５ｂは、分割ドメインごとの要求処理サーバ割当初期化処理を実行する（ステップＳ２０２）。この処理は、全分割ドメインについて繰り返し実行される。かかる処理においては、図１１に示すように、要求処理サーバ割当部３５ｂが、要求処理サーバ割当状態管理テーブル３４ｄにおいて、割当ドメイン数が最少であり、かつ、当該ドメインの割当数が最少である要求処理サーバのうちの一つを割当予定の分割ドメインの要求処理サーバとして決定する（ステップＳ３０１）。
【００６５】
そして、要求処理サーバ割当部３５ｂは、要求処理サーバ割当テーブル３４ｃにおける当該分割ドメインの分割元のドメインのレコードに決定した要求処理サーバの情報を追加する（ステップＳ３０２）。さらに、要求処理サーバ割当部３５ｂは、要求処理サーバ割当状態管理テーブル３４ｄにおける決定した要求処理サーバのレコードに割当予定の分割ドメイン（分割元のドメイン）の情報を追加する（ステップＳ３０３）。要求処理サーバ割当部３５ｂは、全分割ドメインについて上述した処理を繰り返し実行する。
【００６６】
次に、図１２〜１４を用いて、サービス要求の応答処理について説明する。図１２は、第１の実施形態に係る情報処理システム１におけるサービス要求の応答処理の手順を説明するためのシーケンス図である。図１２に示すように、負荷分散装置３０においては、クライアント１０からサービス要求を受信すると（ステップＳ４０１）、要求処理サーバ決定部３５ｄが受信したサービス要求を転送する要求処理サーバを決定する（ステップＳ４０２）。なお、クライアント１０から受信するサービス要求には単一のサービス指定値（キー情報）が含まれる。
【００６７】
そして、要求処理サーバ決定部３５ｄが、サービス要求の転送先の要求処理サーバ４０を決定すると、負荷分散装置３０は、決定した要求処理サーバ４１にサービス要求を転送する（ステップＳ４０３）。サービス要求を受信した要求処理サーバ４１は、サービス応答作成処理を実行して（ステップＳ４０４）、サービス応答を送信する（ステップＳ４０５）。サービス応答を受信した負荷分散装置３０は、サービス要求を送信したクライアントに受信したサービス応答を転送する（ステップＳ４０６）。
【００６８】
続いて、図１２のステップＳ４０２で示す要求処理サーバ決定処理の詳細について説明する。図１３は、第１の実施形態に係る負荷分散装置３０による要求処理サーバ決定処理の手順を説明するためのフローチャートである。図１３に示すように、負荷分散装置３０は、クライアント１０からサービス要求を受信すると、要求処理サーバ決定部３５ｄは、サービス要求に含まれるサービス指定値のハッシュ値を算出して、算出したハッシュ値をキーとして、ドメイン開始ハッシュ値テーブル３４ａを検索して、サービス指定値のドメインを判定する（ステップＳ５０１）。
【００６９】
そして、要求処理サーバ決定部３５ｄは、決定したドメインをキーとして要求処理サーバ割当テーブル３４ｃを検索して、該当するドメイン（分割ドメイン）に属するサービス要求の転送先となっている要求処理サーバ４０の一覧を取得する（ステップＳ５０２）。さらに、要求処理サーバ決定部３５ｄは、要求処理サーバ一覧に含まれる要求処理サーバの中から、ランダムで１つを選択して、サービス要求を処理させる要求処理サーバとして決定する（ステップＳ５０３）。なお、上述した処理の例では、ランダムに要求処理サーバを選択する場合について説明したが、これはあくまでも一例であり、実施形態はこれに限定されるものではない。例えば、分割ドメインの割当状況を考慮し要求処理サーバを選択する場合であってもよい。
【００７０】
続いて、図１２のステップＳ４０４で示すサービス応答作成処理の詳細について説明する。図１４は、第１の実施形態に係る要求処理サーバ４１によるサービス応答作成処理の手順を説明するためのフローチャートである。図１４に示すように、要求処理サーバ４１は、負荷分散装置３０からサービス要求を受信すると、サービス要求に含まれるサービス指定値をキーとして、当該サービス指定値に対応する属性値をメモリ上で検索する（ステップＳ６０１）。
【００７１】
ここで、該当するレコードがある場合には（ステップＳ６０２肯定）、要求処理サーバ４１は、対応する属性値を含めたサービス応答を作成して（ステップＳ６０３）、作成したサービス応答を負荷分散装置３０に送信する。一方、該当するレコードがない場合には（ステップＳ６０２否定）、要求処理サーバ４１は、対応する属性値を含めずにサービス応答を作成して（ステップＳ６０４）、作成したサービス応答を負荷分散装置３０に送信する。なお、上述した例では、サービス応答作成処理を要求処理サーバ４１が実行する場合について説明したが、その他の要求処理サーバ４０も同様の処理を実行することができる。
【００７２】
次に、図１５〜１８を用いて、割当変更処理について説明する。図１５は、第１の実施形態に係る情報処理システム１において、ドメイン分割数が増加した場合の割当変更処理の手順を説明するためのシーケンス図である。図１５に示すように、負荷分散装置３０においては、要求頻度更新部３５ｅが、クライアント１０から送信されるサービス要求について、ドメインごとの要求をカウントして、定期的にドメイン要求頻度テーブル３４ｂを更新する処理である要求頻度監視・更新処理を実行する（ステップＳ７０１）。
【００７３】
要求頻度更新部３５ｅによってドメイン要求頻度テーブル３４ｂが更新されると、要求処理サーバ割当部３５ｂは、要求処理サーバ割当変更処理を実行して（ステップＳ７０２）、要求処理サーバとして新たに割り当てた要求処理サーバ４６に対して割当ドメイン情報追加通知を送信する（ステップＳ７０３）。割当ドメイン情報追加通知を受信した要求処理サーバ４６は、ストレージ装置５１に対して属性値情報要求を送信して（ステップＳ７０４）、属性値情報応答を受信する（ステップＳ７０５）。属性値情報応答を受信すると、要求処理サーバ４６は、割当ドメイン情報追加応答を負荷分散装置３０に送信する（ステップＳ７０６）。
【００７４】
続いて、図１５のステップＳ７０２で示す要求処理サーバ割当変更処理の詳細について説明する。図１６は、第１の実施形態に係る負荷分散装置３０によるドメイン分割数が増加した場合の要求処理サーバ割当変更処理の手順を説明するためのフローチャートである。図１６に示すように、ドメイン分割数が増加した場合、要求処理サーバ割当部３５ｂは、要求処理サーバ割当状態管理テーブル３４ｄにおいて、割当ドメイン数がサーバ分割数未満の要求処理サーバがあるか否かを判定する（ステップＳ８０１）。
【００７５】
ここで、割当ドメイン数がサーバ分割数未満の要求処理サーバがあると判定した場合には（ステップＳ８０１肯定）、要求処理サーバ割当部３５ｂは、さらに、割当ドメイン数がサーバ分割数未満の要求処理サーバの中で、割当ドメイン数が最少で、かつ割当予定の分割ドメインと分割元が同一であるドメインの割当数も最少の要求処理サーバがあるか否かを判定する（ステップＳ８０２）。
【００７６】
ここで、割当ドメイン数が最少で、かつ割当予定の分割ドメインと分割元が同一であるドメインの割当数も最少の要求処理サーバがあると判定した場合には（ステップＳ８０２肯定）、要求処理サーバ割当部３５ｂは、該当する要求処理サーバのうちのひとつを当該分割ドメインの要求処理サーバのひとつに決定する（ステップＳ８０３）。一方、割当ドメイン数が最少で、かつ割当予定の分割ドメインと分割元が同一であるドメインの割当数も最少の要求処理サーバがないと判定した場合には（ステップＳ８０２否定）、要求処理サーバ割当部３５ｂは、割当ドメインがサーバ分割数未満の要求処理サーバの中で、割当予定の分割ドメインと分割元が同一である分割ドメインの割当数が最少の要求処理サーバのうちのひとつを割当予定の分割ドメインの要求処理サーバの一つに決定する（ステップＳ８０４）。
【００７７】
一方、ステップＳ８０１において、割当ドメイン数がサーバ分割数未満の要求処理サーバがないと判定した場合には（ステップＳ８０１否定）、要求処理サーバ割当部３５ｂは、サーバプール情報から未使用の要求処理サーバ４０を一つ取得し、その要求処理サーバ４０を要求処理サーバ割当状態管理テーブル３４ｄに追加するとともに、割当予定の分割ドメインの要求処理サーバのひとつに決定する（ステップＳ８０５）。
【００７８】
そして、要求処理サーバ割当部３５ｂは、要求処理サーバ割当テーブル３４ｃにおける
当該ドメインのレコードに決定した要求処理サーバの情報を追加し（ステップＳ８０６）、さらに、要求処理サーバ割当状態管理テーブル３４ｄにおける決定した要求処理サーバのレコードに当該ドメインの情報を追加する（ステップＳ８０７）。要求処理サーバ割当部３５ｂは、ドメイン分割数の増加分だけ上記した処理を繰り返し実行する。
【００７９】
その後、割当ドメイン情報通知部３５ｃは、新たに割り当てた要求処理サーバに対して、割当ドメイン情報追加通知を送信し（ステップＳ８０８）、負荷分散装置３０は、要求処理サーバから割当ドメイン情報追加応答を受信して（ステップＳ８０９）、処理を終了する。
【００８０】
図１７は、第１の実施形態に係る情報処理システム１において、ドメイン分割数が減少した場合の割当変更処理の手順を説明するためのシーケンス図である。図１７に示すように、負荷分散装置３０においては、要求頻度更新部３５ｅが、クライアント１０から送信されるサービス要求について、ドメインごとの要求をカウントして、定期的にドメイン要求頻度テーブル３４ｂを更新する処理である要求頻度監視・更新処理を実行する（ステップＳ９０１）。
【００８１】
要求頻度更新部３５ｅによってドメイン要求頻度テーブル３４ｂが更新されると、要求処理サーバ割当部３５ｂは、要求処理サーバ割当変更処理を実行して（ステップＳ９０２）、要求処理サーバから削除する要求処理サーバ４６に対して割当ドメイン情報削除通知を送信する（ステップＳ９０３）。割当ドメイン情報削除通知を受信した要求処理サーバ４６は、割当ドメイン情報削除応答を負荷分散装置３０に送信する（ステップＳ９０４）。
【００８２】
続いて、図１７のステップＳ９０２で示す要求処理サーバ割当変更処理の詳細について説明する。図１８は、第１の実施形態に係る負荷分散装置によるドメイン分割数が減少した場合の要求処理サーバ割当変更処理の手順を説明するためのフローチャートである。図１８に示すように、ドメイン分割数が減少した場合、要求処理サーバ割当部３５ｂは、要求処理サーバ割当状態管理テーブル３４ｄにおいて、割当ドメイン数が最多で、かつ削除予定の分割ドメインと分割元が同一である分割ドメインの割当数も最多の要求処理サーバがあるか否かを判定する（ステップＳ１００１）。
【００８３】
ここで、割当ドメイン数が最多で、かつ削除予定の分割ドメインと分割元が同一である分割ドメインの割当数も最多の要求処理サーバがあると判定した場合には（ステップＳ１００１肯定）、要求処理サーバ割当部３５ｂは、該当する要求処理サーバのうちの一つを当該分割ドメインの割当を解除する要求処理サーバに決定する（ステップＳ１００２）。
【００８４】
一方、割当ドメイン数が最多で、かつ削除予定の分割ドメインと分割元が同一である分割ドメインの割当数も最多の要求処理サーバがないと判定した場合には（ステップＳ１００１否定）、要求処理サーバ割当部３５ｂは、削除予定の分割ドメインと分割元が同一である分割ドメインの割当数が最多の要求処理サーバのうちの一つを当該分割ドメインの割当を解除する要求処理サーバに決定する（ステップＳ１００３）。
【００８５】
そして、要求処理サーバ割当部３５ｂは、要求処理サーバ割当テーブル３４ｃにおける
当該ドメインのレコードから決定した要求処理サーバの情報を削除し（ステップＳ１００４）、さらに、要求処理サーバ割当状態管理テーブル３４ｄにおける決定した要求処理サーバのレコードから当該分割ドメインの情報を削除する（ステップＳ１００５）。要求処理サーバ割当部３５ｂは、ドメイン分割数の減少分だけ上記した処理を繰り返し実行する。
【００８６】
その後、割当ドメイン情報通知部３５ｃは、分割ドメインの割当を解除した要求処理サーバに対して、割当ドメイン情報変更通知を送信し（ステップＳ１００６）、負荷分散装置３０は、要求処理サーバから割当ドメイン情報変更通知応答を受信して（ステップＳ１００７）、処理を終了する。
【００８７】
［第１の実施形態の効果］
上述したように、第１の実施形態によれば、クライアント装置から受信した処理の実行要求を複数の要求処理サーバのうちのいずれかに転送する負荷分散装置３０において、ドメイン分類部３５ａは、クライアント１０から受信するであろう処理の実行要求の処理内容を示すキー情報のハッシュ値を算出し、算出したハッシュ値に基づいて、処理の実行要求を所定の数のドメインに分類する。要求処理サーバ割当部３５ｂは、ドメインのそれぞれを、実行要求の要求頻度が所定の閾値以下となる分割ドメインに分割し、各ドメインにおける分割ドメインを、複数の要求処理サーバ４０のそれぞれに対する割当数が所定数以下となるように、割り当てる。要求処理サーバ決定部３５ｄは、クライアント１０から処理の実行要求を受信した場合に、当該実行要求の処理内容を示すハッシュ値を算出して、算出したハッシュ値に基づいて、受信した実行要求が分類されたドメインを特定し、特定したドメインの分割ドメインが割り当てられた要求処理サーバ４０を実行要求の転送先として決定する。従って、第１の実施形態に係る負荷分散装置３０は、キー情報のハッシュ値に基づいて、サービス要求を複数のドメインに分類することで、各ドメインのキー情報の数をおよそ均等にしてメモリ使用量を略均等にするとともに、各ドメインの要求頻度に応じて分割ドメインに分割し、各サーバに略均等に割り当てることで、各要求処理サーバ４０の処理量もおよそ均等にすることができる。その結果、負荷分散装置３０は、サーバの処理量及びメモリ使用量を考慮した負荷分散を行うことを可能にする。
【００８８】
また、第１の実施形態によれば、要求処理サーバ割当部３５ｂは、要求処理サーバ４０の処理性能を所定数で除算した値を所定の閾値として用いる。従って、第１の実施形態に係る負荷分散装置３０は、要求処理サーバ４０への分割ドメインの最大割当数で処理性能を除算した値を分割の閾値とすることで、分割ドメインを最大数割り当てたとしても、割当後の処理量が要求処理サーバ４０の処理性能を超えることはなく、安定した負荷分散を実行させることを可能にする。
【００８９】
また、第１の実施形態によれば、要求処理サーバ割当部３５ｂは、分割ドメインの総数を所定数で除算することで、分割ドメインを割り当てる要求処理サーバ４０の台数を決定し、決定した台数の要求処理サーバ４０に分割ドメインを割り当てる。従って、第１の実施形態に係る負荷分散装置３０は、過不足のない最適な台数の要求処理サーバ４０を割当サーバとして決定することができ、サーバシステムを有効に利用することを可能にする。
【００９０】
また、第１の実施形態によれば、要求処理サーバ割当部３５ｂは、複数の要求処理サーバ４０のうち、分割ドメインの割当数が最少であり、かつ、分割元のドメインが割当予定の分割ドメインと同一となる分割ドメインの割当数が最少である要求処理サーバ４０を割当予定の分割ドメインの割当先と決定する。従って、第１の実施形態に係る負荷分散装置３０は、分割元が同一となる分割ドメインを同一の要求処理サーバ４０に割り当てることを抑止することができ、要求処理サーバ４０の処理量及びメモリ使用量をより均等にすることを可能にする。また、特定のドメインの処理が特定の要求処理サーバ４０のみで実行されることが少ないため、第１の実施形態に係る負荷分散装置３０は、要求処理サーバ４０のいずれかに故障が発生したなどの場合に、故障による影響が特定のドメインの偏ることを抑止することを可能にする。
【００９１】
例えば、各ドメインの処理量をＮ台のサーバに均等に分散していた場合（一つのドメインの各分割ドメインをＮ台のサーバに割り当てている場合）には、仮にそのうちの１台のサーバに故障が発生したとしても、そのドメインに与える影響は、１／Ｎで済むことになる。これは、処理の要求頻度が高く、複数の分割ドメインに分割されるドメインにより効果的である。
【００９２】
また、第１の実施形態によれば、要求処理サーバ決定部３５ｄは、同一のドメインから分割された分割ドメインがそれぞれ異なる要求処理サーバ４０に割り当てられていた場合に、要求処理サーバ４０それぞれに対してドメインに属する実行要求の転送回数が略均等になるように実行要求を転送する。従って、第１の実施形態に係る負荷分散装置３０は、特定の処理が特定の要求処理サーバ４０に集中することを抑止することを可能にする。
【００９３】
また、第１の実施形態によれば、要求頻度更新部３５ｅは、ドメインごとの実行要求の要求頻度を監視して、要求頻度を更新する。要求処理サーバ決定部３５ｄは、要求頻度更新部３５ｅによって要求頻度が更新された場合に、ドメインを更新後の要求頻度が所定の閾値以下となる分割ドメインに再分割し、再分割後の分割ドメインの増減に応じて、複数の要求処理サーバ４０への割り当てを変更する。従って、第１の実施形態に係る負荷分散装置３０は、経時的に変化するサービス要求の要求頻度に応じて、柔軟に負荷分散を実行することを可能にする。
【００９４】
また、第１の実施形態によれば、要求処理サーバ決定部３５ｄは、分割ドメインが増加した場合に、分割元のドメインが同一となる分割ドメインの割当数が最少である要求処理サーバに増加分の分割ドメインを割り当てる。従って、第１の実施形態に係る負荷分散装置３０は、分割ドメインの増加時においても、分割ドメインをバランスよく割り当てることを可能にする。
【００９５】
また、第１の実施形態によれば、要求処理サーバ決定部３５ｄは、分割ドメインが減少した場合に、分割元のドメインが同一となる分割ドメインの割当数が最多である要求処理サーバ４０から減少分の分割ドメインの割り当てを解除する。従って、第１の実施形態に係る負荷分散装置３０は、分割ドメインの減少時においても、分割ドメインの割当てをバランスよく解除することを可能にする。
【００９６】
［第２の実施形態］
これまで第１の実施形態を説明したが、本願に係る実施形態は、これら第１の実施形態に限定されるものではない。すなわち、これらの実施形態は、その他の様々な形態で実施されることが可能であり、種々の省略、置き換え、変更を行うことができる。
【００９７】
上述した第１の実施形態においては、分割元の同じ分割ドメインについて、既に割り当てた割当数が最少となる要求処理サーバ４０に割り当てるように制御する場合について説明した。しかしながら、実施形態はこれに限定されるものではなく、例えば、分割元の同じ分割ドメインが同一の要求処理サーバ４０に割り当てられないように制御する場合であってもよい。
【００９８】
かかる場合には、分割元のドメインが割当予定の分割ドメインと同一となる分割ドメインの既に割り当てた割当数が「０」のサーバが無ければ、サーバプール情報を参照して未使用の要求処理サーバ４０を割当対象のサーバとする。これにより、耐障害性を改善（≒１台以上のサーバが故障した場合のシステム全体としての安全性を向上）させることができる。なお、上述した分割ドメインの割当方法は、必要となる要求処理サーバ４０の数が増えることから、未使用の要求処理サーバ４０が多数ある場合に用いられることが望ましい。
【００９９】
また、例えば、各装置の分散・統合の具体的形態（例えば、図２の形態）は図示のものに限られず、その全部又は一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的又は物理的に分散・統合することができる。一例を挙げると、要求処理サーバ割当部３５ｂと要求頻度更新部３５ｅとを一つの処理部として統合してもよく、一方、要求処理サーバ割当部３５ｂを、分割ドメインを生成する分割ドメイン生成部と、分割ドメインを割り当てる割当部とに分散してもよい。
【０１００】
また、制御部３５を負荷分散装置３０の外部装置としてネットワーク経由で接続するようにしてもよく、或いは、記憶部３４に記憶される各テーブルを別の装置がそれぞれ有し、ネットワークに接続されて協働することで、上述した負荷分散装置３０の機能を実現するようにしてもよい。
【０１０１】
これらの実施例やその変形は、本願が開示する技術に含まれると同様に、特許請求の範囲に記載された発明とその均等の範囲に含まれるものである。
【符号の説明】
【０１０２】
１１、１２、１３  クライアント
２１、２２、２３  ＩＰネットワーク
３０  負荷分散装置
３４  記憶部
３５  制御部
３５ａ  ドメイン分類部
３５ｂ  要求処理サーバ割当部
３５ｃ  割当ドメイン情報通知部
３５ｄ  要求処理サーバ決定部
３５ｅ  要求頻度更新部
４１、４２，４３、４４、４５、４６  要求処理サーバ
５１  ストレージ装置
【図１】
2014096113.tif 000003
【図２】
2014096113.tif 000004
【図３】
2014096113.tif 000005
【図４】
2014096113.tif 000006
【図５】
2014096113.tif 000007
【図６】
2014096113.tif 000008
【図７】
2014096113.tif 000009
【図８】
2014096113.tif 000010
【図９】
2014096113.tif 000011
【図１０】
2014096113.tif 000012
【図１１】
2014096113.tif 000013
【図１２】
2014096113.tif 000014
【図１３】
2014096113.tif 000015
【図１４】
2014096113.tif 000016
【図１５】
2014096113.tif 000017
【図１６】
2014096113.tif 000018
【図１７】
2014096113.tif 000019
【図１８】
2014096113.tif 000020