(57)【要約】【課題】要求処理の負荷を分散し、且つ、記憶装置の容量を小さくすることを課題とする。【解決手段】データ管理装置２００は、ホットゾーンに振り分けられた識別子により識別されるデータの要求に対する応答処理を、全ての要求処理サーバ装置のうちのいずれかの要求処理サーバ装置に割り当て、ノーマルゾーンに振り分けられた識別子により識別されるデータの要求に対する応答処理を、複数の要求処理サーバ装置のうちのいずれかの要求処理サーバ装置に割り当て、コールドゾーンに振り分けられた識別子により識別されるデータの要求に対する応答処理を、一つのサーバ装置に割り当てる。また、ノーマルゾーンに属する識別子により識別されるデータの要求に対する応答処理が割り当てられる要求処理サーバ装置の延べ台数を、全要求処理サーバ装置の台数よりも大きな値とするように、ＲｆおよびＲｌを設定する。【選択図】        図１
2014164357.tif 000002
【特許請求の範囲】
【請求項１】
サーバ制御装置が実行するサーバ制御方法であって、
同一のデータをそれぞれ記憶する複数のサーバ装置に対してクライアント装置がデータを要求した際に、サーバ装置がクライアント装置から受信する識別子の受信頻度をそれぞれ取得する取得ステップと、
前記取得ステップによって取得された各識別子の受信頻度に応じて、各識別子の順位を決定する決定ステップと、
前記決定ステップによって決定された各識別子の順位に応じて、順位が第一閾値よりも高く受信頻度が高い識別子が属する第一のグループ、順位が前記第一閾値以下であって第二閾値よりも高く受信頻度が中程度の識別子が属する第二のグループ、または、順位が前記第二閾値以下であって受信頻度が低い識別子が属する第三のグループのいずれかに各識別子を振り分ける振分ステップと、
前記第一のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理を、全てのサーバ装置のうちのいずれかのサーバ装置に割り当て、前記第二のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理を、複数のサーバ装置のうちのいずれかのサーバ装置に割り当て、前記第三のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理を、一つのサーバ装置に割り当てる割当ステップと、
前記第二のグループに属する識別子により識別されるデータの要求に対する応答処理が割り当てられるサーバ装置の延べ台数を、全サーバ装置の台数よりも大きな値とするように、前記第一閾値および前記第二閾値を設定する設定ステップと、
を含んだことを特徴とするサーバ制御方法。
【請求項２】
前記設定ステップは、前記第二のグループに属する識別子により識別されるデータの要求に対する応答処理が割り当てられるサーバ装置の延べ台数を、全サーバ装置の台数よりも大きな値とするように前記第一閾値および前記第二閾値を設定しつつ、前記第一閾値および前記第二閾値をできるだけ小さい値に設定することを特徴とする請求項１に記載のサーバ制御方法。
【請求項３】
前記設定ステップは、前記順位をｒとし、ジップ定数をｐとし、Ｋを倍率とし、Ｎｓをサーバ数とした場合に、ｐ≠１のとき、（１−ｐ）ＫＮｓ／（１−Ｎｓ（ｐ−１／ｐ））で求められた値、または、ｐ＝１のとき、ｐＫＮｓ／ｌｏｇＮｓで求められた値を用いて、前記第二閾値を設定することを特徴とする請求項１または２に記載のサーバ制御方法。
【請求項４】
前記設定ステップは、前記順位をｒとし、ジップ定数をｐとし、Ｋを倍率とし、Ｎｓをサーバ数とし、Ｒｌを前記第二閾値とした場合に、前記第二閾値が、ｐ≠１のとき、Ｒｌ≧０且つＲｌ−ｐ［Ｒｌ−（１−ｐ）ＫＮｓ］＝１を満たし、ｐ＝１のとき、Ｒｌ＝ｅｘｐ（ＫＮｓ／Ｒｌ）を満たすことを特徴とする請求項１または２に記載のサーバ制御方法。
【請求項５】
前記設定ステップは、前記順位をｒとし、ジップ定数をｐとし、Ｋを倍率とし、Ｎｓをサーバ数とし、Ｒｌを前記第二閾値とした場合に、ｐ≠１のとき、｛Ｒｌ−ｐ［Ｒｌ−（１−ｐ）ＫＮｓ］｝１／（１−ｐ）で求められた値、または、ｐ＝１のとき、Ｒｌ＝ｅｘｐ（ＫＮｓ／Ｒｌ）で求められた値を用いて、前記第二閾値を設定することを特徴とする請求項３または４に記載のサーバ制御方法。
【請求項６】
同一のデータをそれぞれ記憶する複数のサーバ装置に対してクライアント装置がデータを要求した際に、サーバ装置がクライアント装置から受信する識別子の受信頻度をそれぞれ取得する取得部と、
前記取得部によって取得された各識別子の受信頻度に応じて、各識別子の順位を決定する決定部と、
前記決定部によって決定された各識別子の順位に応じて、順位が第一閾値よりも高く受信頻度が高い識別子が属する第一のグループ、順位が前記第一閾値以下であって第二閾値よりも高く受信頻度が中程度の識別子が属する第二のグループ、または、順位が前記第二閾値以下であって受信頻度が低い識別子が属する第三のグループのいずれかに各識別子を振り分ける振分部と、
前記第一のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理については、全てのサーバ装置のうちのいずれかのサーバ装置に割り当て、前記第二のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理については、前記全てのサーバ装置より少ない複数のサーバのうちのいずれかのサーバ装置に割り当て、前記第三のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理については、一つのサーバ装置に割り当てる割当部と、
前記第二のグループに属する識別子により識別されるデータの要求に対する応答処理が割り当てられるサーバ装置の延べ台数を、全サーバ装置の台数よりも大きな値とするように、前記第一閾値および前記第二閾値を設定する設定部と、
を備えたことを特徴とするサーバ制御装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、サーバ制御方法およびサーバ制御装置に関する。
【背景技術】
【０００２】
従来、インターネットやそれを利用するための端末技術の発展にともない、ネットワークを利用するユーザに対して、アプリケーション層やネットワーク層など様々な層（レイヤー）でサービスが提供されている。このようなサービスを提供する為に、ネットワークには、様々なサーバが設置されている。例えば、ＷＥＢサービスにおけるＷＷＷサーバや、ユーザ端末をネットワークに接続するサービスにおける認証サーバなどがある。このようなサーバは、ユーザから直接的、あるいは、間接的に送られてきた識別子に応じてサービスを提供する為の応答を返すことで、サービスを構成している。識別子の例としては、ＷＷＷサーバにおけるＵＲＩ（Uniform  Resource  Identifier）や、認証サーバにおけるユーザ識別子がある。なお、ＵＲＩは、例えば、非特許文献１にRFC3986として制定されている。
【０００３】
このような識別子に対して応答を返すサーバは、ユーザのネットワーク利用が爆発的に増加する中で、非常に高い性能を求められるようになってきており、これを解決する為に、多くのサーバを設置することで、複数のサーバ全体として高い性能を実現してきている。この複数のサーバを設置するという方法では、サーバの有効利用の観点から、識別子に対するサーバの処理に起因するサーバ負荷が、複数の異なるサーバ間で均一になるようにすることが求められる。このサーバ間の負荷の均一化は、負荷分散と呼ばれ、例えば、非特許文献２や非特許文献３に述べられているラウンドロビンや、非特許文献４に述べられているコンシステントハッシングなどの方法によって実現されている。
【０００４】
図４１は、ラウンドロビン法による、負荷分散を表している。まず、クライアント１０５０、１０６０、１０７０は、サーバ装置に対する処理要求をランドロビン用負荷分散転送装置１０４０に送信する。ランドロビン用負荷分散転送装置１０４０は、クライアントからの処理要求を、ランドロビン用負荷分散転送装置１０４０に登録されたサーバ装置の順番に従い、最初は、一番目に登録されているサーバ装置１０００に送信し、次の処理要求を二番目に登録されているサーバ装置１０１０に送信し、順次、登録された順序で、クライアントからの処理要求の送信先を変更する。全ての登録されたサーバ装置にクライアントからの処理要求を送信したら、また、一番目に登録されているサーバ装置１０００に送信する。このように、ラウンドロビン法では、任意の識別子を含む処理要求を、任意のサーバ装置が処理する必要があるため、全てのサーバ装置が全ての識別子を処理するための情報を保持しておく必要がある。以上の動作を繰り返すことで、クライアントからの処理要求を複数のサーバに送信することで、複数のサーバ装置全体で、負荷分散を実現しながら、クライアントからの大量の処理要求に対して応答することが可能となる。
【０００５】
図４２は、コンシステントハッシング法による、負荷分散を表している。まず、クライアント１１５０、１１６０、１１７０は、サーバ装置に対する処理要求をコンシステントハッシング用負荷分散転送装置１１４０に送信する。コンシステントハッシング用負荷分散転送装置１１４０は、クライアントからの処理要求を、受信したとき、最初に、その中に含まれる、前記サーバが応答を特定するための識別子を取り出す。次に、取り出した識別子に対し、MD5やSHA1などのハッシュ法を用いて識別子のハッシュ値を計算する。コンシステントハッシング用負荷分散転送装置１１４０には、ハッシュ値の範囲と対応するサーバ装置の対応表を管理しており、計算したハッシュ値に対応するサーバ装置を検索し、そのサーバ装置に対して、クライアントからの処理要求を送信する。図４３は、このサーバ装置の選択方法を示している。例えば、識別子として、www.aaa.co.jpが指定されたとき、www.aaa.co.jpのハッシュ値を計算し、ハッシュ値の範囲と対応するサーバ装置の対応表からサーバ装置１１１０を選択している。以上のように、識別子から計算されるハッシュ値をもとに、クライアントからの処理要求を送信するサーバ装置を振り分けることにより、複数のサーバ装置全体で、負荷分散を実現しながら、クライアントからの大量の処理要求に対して応答することが可能となる。
【０００６】
更に、近年、様々なサービスを開始するにあたり、最初は、小規模のユーザを対象としてサービス提供を開始し、ユーザ数が大規模化するに従い、柔軟にサービスを提供するためのサーバを構成することが求められてきている。これまで、小規模のユーザを対象としたサービスを、大規模化していくには、一つ一つのサーバ装置の性能を上げていく、スケールアップという手法が主流であった。しかし、スケールアップ手法は、装置を取り替えていく必要があり、柔軟な規模の変更が困難であった。これに対して、ユーザの規模に応じて、サーバ装置を追加していくことで、複数のサーバ装置全体としての性能を上げていく、スケールアウトという手法の必要性が大幅に増してきている。
【０００７】
上記のコンシステントハッシングは、スケールアウトを実現する手法であり、近年、盛んに利用が検討されてきている。図４４は、コンシステントハッシング法によるスケールアウトを示している。最初、図４４の左側で示している、ハッシュ値の範囲と対応するサーバ装置の対応表(変更前の表)を用いていたとする。このとき、ハッシュ値６個に対して、一つのサーバ装置が割り当てられ、サーバ装置としてＭ台で処理している。次に、クライアント数が増加したとき、図４４の右側で示している、ハッシュ値の範囲と対応するサーバ装置の対応表（変更後の表）を用いて、ハッシュ値３個に対して、一つのサーバ装置が割り当てられ、サーバ装置として２Ｍ台で処理することで、サーバ装置の台数増加により、既存サーバ装置を活かしながら、容易に負荷の増加に対応できる。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】T.  Berners-Lee、R.  Fielding、L.  Masinter  著、「Uniform  Resource  Identifier  (URI):Generic  Syntax」、RFC3986、http://www.ietf.org/rfc/rfc3986.txt、2005.
【非特許文献２】トニー  ブルーク著、鍋島  公章訳、横山  晴庸訳、上谷  一訳、「サーバ負荷分散技術」，オライリー・ジャパン発行，２００１．
【非特許文献３】A.  Kuurne、A.  P.  Miettinen  著、「Weighted  Round  Robin  Scheduling  Strategies  in  (E)GPRS  Radio  Interface」,  2004  IEEE  60th  Vehicular  Technology  Conference,  Vol5,  pp.  3155-3159,  2004.
【非特許文献４】David  Karger、Eric  Lehman、Tom  Leighton、Rina  Panigrahy、Matthew  Levine、Daniel  Lewin  著、「Consistent  hashing  and  random  trees:  distributed  caching  protocols  for  relieving  hot  spots  on  the  World  Wide  Web」、Proceedings  of  the  twenty-ninth  annual  ACM  symposium  on  Theory  of  computing,  pp.  654-663,  1997.
【非特許文献５】L.  Breslau、P.  Cao、L.  Fan、G.  Phillips、S.  Shenker、「Web  caching  and  Zipf-like  distributions:  evidence  and  implications」、Proceeding  IEEE  INFOCOM,  pp.  126-134,  1999.
【非特許文献６】I.ガットマン、S.S.ウィルクス著、石井恵一、堀素夫訳、「工科系のための統計概論」、培風館、1999年.
【発明の概要】
【発明が解決しようとする課題】
【０００９】
ところで、クライアントからサーバ装置に対して送信される処理要求に含まれる識別子が、どのような割合でサーバ装置に送信される全処理要求に含まれるか、即ち、各識別子の発生頻度は、一般的には、サーバ装置が用いられるアプリケーションによって異なってくる。一方で、例えば、非特許文献５に例示されているように、ＷＥＢサービスなど、識別子の発生頻度がジップ（Zipf）の法則に従い、且つ、広く用いられているアプリケーションであるような場合があり、このような識別子の発生頻度の分布に対しても、負荷分散、及び、スケールアウトを実現することは、実利用の観点から極めて重要である。
【００１０】
また、サーバ装置への処理要求が、ネットワーク利用の拡大により、増大していく中、サーバ装置による効率的な識別子に対する処理を実現することを目的として、サーバ装置が処理要求を行うために必要な識別子に関連したデータを、メモリ上に保持したり、SSD(Solid  State  Drive)と呼ばれるフラッシュメモリを用いた記憶装置に保持したりするなど高速な記憶装置を有効利用することが求められてきている。このような記憶装置のコストや性能の面から限られた記憶容量を有効に利用しながら、負荷分散、及び、スケールアウトを実現することが不可欠である。
【００１１】
ここで、まず、上記の説明で触れたジップの法則について説明する。各識別子の発生頻度を、発生頻度の大きいものから、小さいものの順序で並べ、発生頻度が何番目に大きいかを表す数字をランクと呼ぶものとする。例えば、最も発生頻度の大きい識別子のランクは、１となる。このとき、ジップの法則では、ランクの発生頻度ｆ（ｒ）が、下記（１）式になる。
【００１２】
【数１】
2014164357.tif 000003
【００１３】
ここで、ｐとａは、正の実数である。本明細書において、ｐをジップ定数と呼ぶこととする。図４５は、ジップの法則に従う発生頻度の分布の例である。識別子の発生頻度が、このジップの法則に従う場合の、特に顕著な特性として、以下の二つの特性がある。一つ目の特性としては、比較的少数の識別子の発生頻度が、全体の大きな部分を占めること（以下、特徴（１）という）である。また、二つ目の特性としては、発生頻度が非常に小さい識別子が大量に存在すること（以下、特徴（２）という）である。
【００１４】
以下に、上記の特徴を持った発生頻度を持つ識別子の処理要求の、負荷分散、及び、スケールアウトの実現に、ラウンドロビン法、及び、コンシステントハッシング法を用いた場合を考える。
【００１５】
ラウンドロビン法を用いた場合、任意の識別子を含む処理要求を、任意のサーバ装置が処理する必要があるため、全てのサーバ装置が全ての識別子を処理するための情報を保持しておく必要がある。よって、上記の、「発生頻度が非常に小さい識別子が大量に存在する。」という上記の特徴（２）により、発生頻度の非常に小さい識別子が大量に有り、この大量の識別子を処理するための情報を、全てのサーバ装置が保持しなければならないことになる。このことは、処理要求への応答に必要となる識別子に関連したデータの保持するために必用な記憶装置の容量が非常に大きいものとなり、効率的なサーバ装置の処理のために、メモリやＳＳＤを用いることを困難にしたり、サーバ装置のコストを大幅に増加させたりといった問題を発生させる。また、識別子の増加に対して、サーバ装置単体の記憶容量が上限となり、スケールアウトを実現することができないという問題も発生させる。
【００１６】
上述のラウンドロビン法を用いた場合の問題点として、（１）サーバ装置単体に必要とされる記憶装置の容量が大規模化することでサーバ装置のコストが高くなることと、（２）サーバ装置単体の記憶装置の容量がボトルネックとなりスケールアウトを実現できないことが挙げられる。
【００１７】
次に、コンシステントハッシング法を用いた場合、上記で説明したように、処理要求への応答に必用な識別子に関連したデータを複数のサーバ装置で分割して持つことで、負荷分散とスケールアウトの実現が可能である。一方で、ある識別子の処理要求は、単一のサーバ装置に送信されるため、その識別子を含む処理要求が、単一のサーバ装置の性能で、十分に処理できる程度でなければならない。しかし、上記の特徴（１)により、発生頻度の大きい識別子について、その発生頻度は、非常に大きな値となることから、単一のサーバ装置での処理が困難となる場合がある（例えば、図４５におけるランク１の処理に必用な性能が、単一のサーバ装置の性能を上回っている場合がある）。
【００１８】
また、仮に少数の識別子に対する処理で、単一のサーバ装置の大部分の性能が必要な場合についても、そのサーバ装置で処理できる識別子の数が大幅に小さくなり、処理要求への応答に必用な識別子に関連したデータを複数のサーバ装置で分割して持つことでスケールアウトを実現する際に、記憶容量の利用効率の低いサーバ装置が発生し、サーバ装置の効率が低下する。その結果として、サーバ装置全体のコストが増加するという問題が発生する。更に、コンシステントハッシング法を用いた場合、非常に発生頻度の高い識別子を割り当てられたサーバ装置の負荷が非常に高くなり、発生頻度の低い識別子のみを割り当てられたサーバ装置の負荷が小さくなることが発生し、全体として、サーバ装置の負荷分散が十分に行われず、結果として、必要なサーバ装置の台数が増加するという問題が発生する。
【００１９】
上述のコンシステントハッシング法を用いた場合の問題点として、（１）単一の識別子の発生頻度が、単一のサーバ装置で処理できる性能を超えている場合、コンシステントハッシング法が利用できないこと、（２）少数の識別子の発生頻度の割当によって、単一のサーバ装置で処理できる性能を超えている場合、十分な数の識別子に対する処理ができなくなり、サーバ装置の記憶容量の利用効率が低下すること、（３）発生頻度の高い識別子を割り当てられたサーバ装置と、発生頻度の小さい識別子のみを割り当てられたサーバ装置との間でサーバ装置の負荷の偏りが発生し必要なサーバ装置台数が増加することが挙げられる。
【００２０】
そこで、この発明は、上述した従来技術の課題を解決するためになされたものであり、要求処理の負荷を分散し、且つ、記憶装置の容量を小さくすることを目的とする。
【課題を解決するための手段】
【００２１】
上述した課題を解決し、目的を達成するため、サーバ制御方法は、サーバ制御装置が実行するサーバ制御方法であって、同一のデータをそれぞれ記憶する複数のサーバ装置に対してクライアント装置がデータを要求した際に、サーバ装置がクライアント装置から受信する識別子の受信頻度をそれぞれ取得する取得ステップと、前記取得ステップによって取得された各識別子の受信頻度に応じて、各識別子の順位を決定する決定ステップと、前記決定ステップによって決定された各識別子の順位に応じて、順位が第一閾値よりも高く受信頻度が高い識別子が属する第一のグループ、順位が前記第一閾値以下であって第二閾値よりも高く受信頻度が中程度の識別子が属する第二のグループ、または、順位が前記第二閾値以下であって受信頻度が低い識別子が属する第三のグループのいずれかに各識別子を振り分ける振分ステップと、前記第一のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理を、全てのサーバ装置のうちのいずれかのサーバ装置に割り当て、前記第二のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理を、複数のサーバのうちのいずれかのサーバ装置に割り当て、前記第三のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理を、一つのサーバ装置に割り当てる割当ステップと、前記第二のグループに属する識別子により識別されるデータの要求に対する応答処理が割り当てられるサーバ装置の延べ台数を、全サーバ装置の台数よりも大きな値とするように、前記第一閾値および前記第二閾値を設定する設定ステップと、を含んだことを特徴とする。
【００２２】
また、サーバ制御装置は、同一のデータをそれぞれ記憶する複数のサーバ装置に対してクライアント装置がデータを要求した際に、サーバ装置がクライアント装置から受信する識別子の受信頻度をそれぞれ取得する取得部と、前記取得部によって取得された各識別子の受信頻度に応じて、各識別子の順位を決定する決定部と、前記決定部によって決定された各識別子の順位に応じて、順位が第一閾値よりも高く受信頻度が高い識別子が属する第一のグループ、順位が前記第一閾値以下であって第二閾値よりも高く受信頻度が中程度の識別子が属する第二のグループ、または、順位が前記第二閾値以下であって受信頻度が低い識別子が属する第三のグループのいずれかに各識別子を振り分ける振分部と、前記第一のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理については、全てのサーバ装置のうちのいずれかのサーバ装置に割り当て、前記第二のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理については、前記全てのサーバ装置より少ない複数のサーバのうちのいずれかのサーバ装置に割り当て、前記第三のグループに振り分けられた識別子により識別されるデータの要求に対する応答処理については、一つのサーバ装置に割り当てる割当部と、前記第二のグループに属する識別子により識別されるデータの要求に対する応答処理が割り当てられるサーバ装置の延べ台数を、全サーバ装置の台数よりも大きな値とするように、前記第一閾値および前記第二閾値を設定する設定部と、を備えたことを特徴とする。
【発明の効果】
【００２３】
本願に開示するサーバ制御方法およびサーバ制御装置は、要求処理の負荷を分散し、且つ、記憶装置の容量を小さくすることが可能である。
【図面の簡単な説明】
【００２４】
【図１】図１は、第一の実施形態に係るシステムの構成の一例を示す図である。
【図２】図２は、第一の実施形態に係る要求処理サーバ装置の構成を説明するための図である。
【図３】図３は、要求処理サーバ装置側要求処理用データベースのデータ構造の一例を示す図である。
【図４】図４は、第一の実施形態に係るデータ管理装置の構成を説明するための図である。
【図５】図５は、データ管理装置側要求処理用データベースのデータ構造の一例を示す図である。
【図６】図６は、要求処理サーバ装置データベースのデータ構造の一例を示す図である。
【図７】図７は、ハッシュ値要求処理サーバ装置変換用データベースのデータ構造の一例を示す図である。
【図８】図８は、データ管理装置側分散度決定用データベースのデータ構造の一例を示す図である。
【図９】図９は、識別子のランクの領域の分割方法を説明する図である。
【図１０】図１０は、ホットゾーン・ノーマルゾーン・コールドゾーン決定の為の入力と出力を示す図である。
【図１１】図１１は、識別子の頻度の分布が完全にジップの法則に従う場合のジップ定数の決定方法を説明する図である。
【図１２】図１２は、識別子の頻度の分布が完全にジップの法則に従わない場合のジップ定数の決定方法を説明する図である。
【図１３】図１３は、識別子の頻度の分布が完全にジップの法則に従わない場合のジップ定数の決定方法を説明する図である。
【図１４】図１４は、Ｖｆ≧１且つｐ≧１のときのＲｌとＲｆの関係を示す図である。
【図１５】図１５は、Ｖｆ≧１且つ０＜ｐ＜１のときのＲｌとＲｆの関係を示す図である。
【図１６】図１６は、Ｖｆ＜１且つｐ≧１のときのＲｌとＲｆの関係を示す図である。
【図１７】図１７は、Ｖｆ＜１且つ０＜ｐ＜１のときのＲｌとＲｆの関係を示す図である。
【図１８】図１８は、第一の実施形態に係る負荷分散転送装置の構成を説明するための図である。
【図１９】図１９は、負荷分散転送装置側分散度決定用データベースのデータ構造の一例を示す図である。
【図２０】図２０は、処理用データ取得処理の処理手順を示すフローチャートである。
【図２１】図２１は、サービス応答処理の処理手順を示すフローチャートである。
【図２２】図２２は、頻度情報更新部の処理手順を示すフローチャートである。
【図２３】図２３は、頻度情報取得要求部の処理手順を示すフローチャートである。
【図２４】図２４は、処理用データ応答部の処理手順を示すフローチャートである。
【図２５】図２５は、識別子割当決定部の処理手順を示すフローチャートである。
【図２６】図２６は、頻度情報取得部の処理手順を示すフローチャートである。
【図２７】図２７は、分散度決定部の処理手順を示すフローチャートである。
【図２８】図２８は、ランク決定部の処理手順を示すフローチャートである。
【図２９】図２９は、サーバ装置データ送信部の処理手順を示すフローチャートである。
【図３０】図３０は、識別子割当通知部の処理手順を示すフローチャートである。
【図３１】図３１は、識別子割当受信部の処理手順を示すフローチャートである。
【図３２】図３２は、サーバ装置データ受信部の処理手順を示すフローチャートである。
【図３３】図３３は、要求振分部の処理手順を示すフローチャートである。
【図３４】図３４は、サーバ装置数の決定処理の処理手順を示すフローチャートである。
【図３５】図３５は、ホット・ノーマルゾーン境界とノーマル・コールドゾーン境界の決定処理の処理手順を示すフローチャートである。
【図３６】図３６は、Ｖｆ≧１且つｐ＝１のときのＲｌとＲｆの決定処理の処理手順を示すフローチャートである。
【図３７】図３７は、Ｖｆ≧１且つｐ≠１のときのＲｌとＲｆの決定処理の処理手順を示すフローチャートである。
【図３８】図３８は、Ｖｆ＜１且つｐ＝１のときのＲｌとＲｆの決定処理の処理手順を示すフローチャートである。
【図３９】図３９は、Ｖｆ＜１且つｐ≠１のときのＲｌとＲｆの決定処理の処理手順を示すフローチャートである。
【図４０】図４０は、サーバ制御プログラムを実行するコンピュータを示す図である。
【図４１】図４１は、ラウンドロビン法を用いた既存技術を説明する図である。
【図４２】図４２は、コンシステントハッシング法を用いた既存技術を説明する図である。
【図４３】図４３は、コンシステントハッシング法におけるサーバ選択方法を説明する図である。
【図４４】図４４は、コンシステントハッシング法によるスケールアウトの仕組みを説明する図である。
【図４５】図４５は、ジップの法則の発生頻度分布の例を示す図である。
【発明を実施するための形態】
【００２５】
以下に添付図面を参照して、この発明に係るサーバ制御方法およびサーバ制御装置の実施形態を詳細に説明する。なお、この実施形態によりこの発明が限定されるものではない。
【００２６】
［第一の実施形態］
以下の実施の形態では、第一の実施形態に係るシステムの構成、要求処理サーバ装置の構成、データ管理装置の構成、負荷分散転送装置の構成および各装置による処理の流れを順に説明し、最後に第一の実施形態による効果を説明する。
【００２７】
［システムの構成］
まず、第一の実施形態に係る負荷分散転送装置が適用されるシステムの構成の一例を説明する。図１は、第一の実施形態に係るシステムの構成の一例を示す図である。図１に示すように、第１の実施形態に係るシステムは、複数の要求処理サーバ装置１００Ａ〜１００Ｄ、データ管理装置２００、負荷分散転送装置３００、複数のクライアント４００Ａ〜４００Ｃを有する。なお、以下では、要求処理サーバ装置１００Ａ〜１００Ｄについて、特に区別することなく説明する場合には、要求処理サーバ装置１００と記載し、クライアント４００Ａ〜４００Ｃについて、特に区別することなく説明する場合には、クライアント４００と記載する。
【００２８】
要求処理サーバ装置１００Ａ〜１００Ｄは、各種データをそれぞれ記憶しており、クライアント４００Ａ〜４００Ｃから識別子を受け付けると、識別子で特定される応答を送信する。
【００２９】
データ管理装置２００は、各識別子の発生頻度に関する情報を取得し、識別子を要求処理サーバ装置１００に割り当てる。具体的には、データ管理装置２００は、要求処理サーバ装置１００が提供するサービスを決定する識別子を、識別子の発生頻度の高いものから小さいものの順序で並べ、識別子の領域を三つの領域に分割する。ここで、発生頻度の高い領域をホットゾーン、発生頻度の小さい領域をコールドゾーン、ホットゾーンとコールドゾーンに挟まれた領域をノーマルゾーンと呼ぶことにする。次に、ホットゾーン、ノーマルゾーン、コールドゾーンの領域毎に異なる負荷分散方法を採用する。ホットゾーンの領域に含まれる識別子の処理は、要求処理サーバ装置１００全体で負荷を分散する。コールドゾーンの領域に含まれる識別子に対しては、コンシステントハッシング法と同様に、識別子のハッシュ値によって決まる要求処理サーバ装置１００で処理を行うことで、要求処理サーバ装置１００間で担当する識別子を分割し、負荷を分散する。
【００３０】
また、データ管理装置２００は、ノーマルゾーンの領域に含まれる識別子に対しては、各識別子の発生頻度に応じた複数、且つ、全サーバ装置数未満の要求処理サーバ装置１００で負荷分散を行うとともに、要求処理サーバ装置１００間で担当する識別子を分割することで、負荷を分散する。ホットゾーンとノーマルゾーンにおける、各識別子の処理を行う複数の要求処理サーバ装置１００に対してはラウンドロビン法により負荷分散を行う。
【００３１】
負荷分散転送装置３００は、クライアント４００Ａ〜４００Ｃから受信した識別子を含む処理要求を要求処理サーバ装置１００Ａ〜１００Ｄに転送する。
【００３２】
まず、クライアント４００Ａ〜４００Ｃは、識別子を含む処理要求を負荷分散転送装置３００に送信する。次に、負荷分散転送装置３００は、要求処理サーバ装置１００Ａ〜１００Ｄから一つの要求処理サーバ装置１００を決定し、クライアント４００Ａ〜４００Ｃから受信した処理要求を、決定した要求処理サーバ装置１００に送信する。負荷分散転送装置３００、要求処理サーバ装置１００Ａ〜１００Ｄが、上記の動作に必要なデータは、データ管理装置２００において保持される。なお、負荷分散転送装置３００、要求処理サーバ装置１００Ａ〜１００Ｄおよびデータ管理装置２００は、物理的な筐体を表すものではなく、あるサーバの筐体に、負荷分散転送装置、要求処理サーバ装置、データ管理装置の機能の一つ、または、複数の組合せを搭載してもよい。また、図１では、負荷分散転送装置を一台として説明しているが、複数台としてもよい。
【００３３】
［要求処理サーバ装置の構成］
次に、図２を用いて、図１に示した要求処理サーバ装置１００の構成を説明する。図２は、第一の実施形態に係る要求処理サーバ装置１００の構成を説明するための図である。図２に示すように、要求処理サーバ装置１００は、通信制御Ｉ／Ｆ部１０１、制御部１０２、記憶部１０３を有する。通信制御Ｉ／Ｆ部１０１は、データ管理装置２００、および、負荷分散転送装置３００との通信を行う。
【００３４】
記憶部１０３は、図２に示すように、要求処理サーバ装置側要求処理用データベース１０８を有する。記憶部１０３は、例えば、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、又は、ハードディスク、光ディスク等の記憶装置などである。
【００３５】
要求処理サーバ装置側要求処理用データベース１０８は、例えば、図３に例示するように、クライアントから送信される「識別子」と、該当する識別子を含む要求処理の発生回数を表す値である「頻度」と、識別子を含む要求処理に対する応答を行うための「処理用データ」とが対応付けて記憶される。
【００３６】
図２に戻って、制御部１０２は、サービス応答部１０４と、頻度情報更新部１０５と、頻度情報取得要求処理部１０６と、処理用データ取得部１０７とを有する。ここで、制御部１０２は、ＣＰＵ（Central  Processing  Unit）やＭＰＵ（Micro  Processing  Unit）などの電子回路やＡＳＩＣ（Application  Specific  Integrated  Circuit）やＦＰＧＡ（Field  Programmable  Gate  Array）などの集積回路である。
【００３７】
サービス応答部１０４は、サービスの処理要求を受信した場合に、処理要求に含まれている識別子に対応する応答を作成して、応答を送信する。具体的には、サービス応答部１０４は、最初に、サービスの処理要求を受信すると、処理要求に含まれる識別子を取り出し、これを含むレコードを要求処理サーバ装置側要求処理用データベース１０８から検索する。ここで、サービス応答部１０４は、処理要求に含まれている識別子が要求処理サーバ装置側要求処理用データベース１０８に含まれているか、否かを検査する。本検査において、サービス応答部１０４は、識別子が要求処理サーバ装置側要求処理用データベースに含まれていた場合、検索したレコードから該当する識別子に対する処理用データを用いて処理要求に対する応答を作成する。
【００３８】
その後、サービス応答部１０４は、受信した処理要求に含まれる識別子に対する頻度情報を更新するために頻度情報更新部に依頼して頻度情報更新処理を実施し、最後に、応答を送信する。また、上記の検査において、サービス応答部１０４は、識別子が要求処理サーバ装置側要求処理用データベースに含まれていなかった場合、登録されていない識別子に対する応答を作成し、応答を送信する。
【００３９】
頻度情報更新部１０５は、要求処理サーバ装置側要求処理用データベース１０８における頻度情報の変更を行う。具体的には、頻度情報更新部１０５は、最初に、処理要求に含まれる識別子をもとにして、要求処理サーバ装置側要求処理用データベース１０８から該当するレコードを検索する。次に、頻度情報更新部１０５は、該当するレコードの頻度情報を読み込み後、頻度情報をインクリメントし、その後、該当するレコードの頻度情報の変更を行う。なお、前述したように、頻度の情報は、該当する識別子を含む要求処理の発生回数を表す値を格納している。
【００４０】
頻度情報取得要求処理部１０６は、データ管理装置２００から、頻度情報取得要求処理を受信すると、識別子と頻度情報の組を取得し、取得した識別子と頻度情報の組を返信する。具体的には、頻度情報取得要求処理部１０６は、最初に、データ管理装置から、頻度情報取得要求処理を受信すると、要求処理サーバ装置側要求処理用データベース１０８の、ｉ番目のレコードについて、ｉを１からＮｒまで変化させながら、全てのレコードに対して以下の処理を行う。
【００４１】
つまり、頻度情報取得要求処理部１０６は、ｉ番目のレコードについて、識別子と頻度情報の組を取得する。取得した頻度情報について、頻度情報を、頻度情報を取得している期間で割り、実際の単位時間当たりの発生回数に変換し、識別子とともにデータ管理装置に送信するために記憶する。そして、頻度情報取得要求処理部１０６は、全てのレコードに対して上記の処理を実施したのち、送信用に記憶した識別子と、識別子に対する単位時間当たりの発生回数の組を全て送信する。
【００４２】
処理用データ取得部１０７は、処理用データを送信する旨を、データ管理装置２００に要求し、要求処理サーバ装置用の処理用データを受信して識別子と処理用データの組を要求処理サーバ装置側要求処理用データベース１０８に格納する。
【００４３】
具体的には、処理用データ取得部１０７は、まず、処理用データを送信する旨を、データ管理装置２００に要求する。このとき、本要求に、要求を行う要求処理サーバ装置情報を含める。そして、この要求処理サーバ用の処理用データを送信する旨を受信したデータ管理装置２００は、処理用データを要求処理サーバ装置１００に対して応答する。続いて、処理用データ取得部１０７は、データ管理装置２００から送られてきた、該当要求処理サーバ装置用の処理用データを受信する。その後受信した識別子と処理用データの組を図３で示す要求処理サーバ装置側要求処理用データベース１０８に格納する。
【００４４】
［データ管理装置の構成］
次に、図４を用いて、図１に示したデータ管理装置２００の構成を説明する。図４は、第一の実施形態に係るデータ管理装置２００の構成を説明するための図である。図４に示すように、データ管理装置２００は、通信制御Ｉ／Ｆ部２０１、制御部２０２、記憶部２０３を有する。通信制御Ｉ／Ｆ部２０１は、要求処理サーバ装置１００との通信を行う。
【００４５】
データ管理装置２００は、まず、サーバ装置が提供するサービスを決定する識別子を、識別子の発生頻度の高いものから小さいものの順序で並べ、識別子の領域をノーマルゾーン、ホットゾーンとコールドゾーンの三つの領域に分割する。
【００４６】
次に、ホットゾーン、ノーマルゾーン、コールドゾーンの領域毎に異なる負荷分散方法を採用する。ホットゾーンの領域に含まれる識別子の処理は、サーバ装置全体で負荷を分散する。コールドゾーンの領域に含まれる識別子に対しては、コンシステントハッシング法と同様に、識別子のハッシュ値によって決まるサーバ装置で処理を行うことで、サーバ装置間で担当する識別子を分割し、負荷を分散する。ノーマルゾーンの領域に含まれる識別子に対しては、各識別子の発生頻度に応じた複数、且つ、全サーバ装置数未満のサーバ装置で負荷分散を行うとともに、サーバ装置間で担当する識別子を分割することで、負荷を分散する。ホットゾーンとノーマルゾーンにおける、各識別子の処理を行う複数のサーバ装置に対してはラウンドロビン法により負荷分散を行う。
【００４７】
ここで、ノーマルゾーンに含まれる識別子の中で最もランクの値が小さい、即ち、発生頻度が最も高いランクをＲｆで表し、コールドゾーンに含まれる識別子の中で最もランクの値が小さい、即ち、発生頻度が最も高いランクをＲｌで表すこととする。今、ランクＲｆの識別子の処理を担当するサーバ装置の台数を、Ｎｄｉｖ（ｒ）で表すと、ノーマルゾーンの識別子を処理するために必要なサーバ装置の延台数は、下記（２）式となり、全サーバ装置の数を、Ｎｓｅｒｖで表すと、Ｎｓｅｒｖに対する下記（２）式でもとめられる倍率が、十分に大きな倍率Ｋに近い値となるように、Ｒｆ、および、Ｒｌを決定する。即ち、下記（３）式となり、Ｋを十分に大きな値とする。また、上記条件を満たすＲｆとＲｌの組合せの中で、Ｒｆ、および、Ｒｌが出来るだけ小さな値となるＲｆとＲｌを選択する。
【００４８】
【数２】
2014164357.tif 000004
【００４９】
【数３】
2014164357.tif 000005
【００５０】
記憶部２０３は、図４に示すように、データ管理装置側要求処理用データベース２１１、要求処理サーバ装置データベース２１２、ハッシュ値要求処理サーバ装置変換用データベース２１３およびデータ管理装置側分散度決定用データベース２１４を有する。記憶部２０３は、例えば、ＲＡＭ（Random  Access  Memory）、フラッシュメモリ（Flash  Memory）等の半導体メモリ素子、又は、ハードディスク、光ディスク等の記憶装置などである。
【００５１】
データ管理装置側要求処理用データベース２１１は、例えば、図５に例示するように、「識別子」が登録されており、各識別子に対して、クライアント４００からの要求処理に必要な「処理用データ」、識別子に対する要求処理が発生する「頻度」、および、識別子を頻度の高いものから低いものの順序で並べたときの順番である「ランク」が管理されている。
【００５２】
要求処理サーバ装置データベース２１２は、例えば、図６に例示するように、登録されている要求処理サーバ装置１００の「番号」と、要求処理サーバ装置１００を識別する情報である「要求処理サーバ装置情報」とを記憶する。
【００５３】
ハッシュ値要求処理サーバ装置変換用データベース２１３は、例えば、図７に例示するように、識別子のハッシュ値の範囲である「担当領域」と、その範囲に含まれる識別子の処理を担当する要求処理サーバ装置１００を示す「要求処理サーバ装置情報」とを記憶する。
【００５４】
データ管理装置側分散度決定用データベース２１４は、例えば、図８に例示するように、「識別子のハッシュ値」と、その識別子のハッシュ値に対応する「識別子のリスト」と、その識別子を処理するときの「分散度」とを記憶する。ここで分散度とは、該当する識別子の処理を何台の要求処理サーバに分散するかを表す値であり、この値が０の場合は、全ての要求処理サーバに処理を分散することを意味する。
【００５５】
図４に戻って、制御部２０２は、処理用データ応答部２０４と、識別子割当決定部２０５と、頻度情報取得部２０６と、識別子割当通知部２０７と、分散度決定部２０８と、ランク決定部２０９と、サーバ装置データ送信部２１０とを有する。ここで、制御部２０２は、ＣＰＵやＭＰＵなどの電子回路やＡＳＩＣやＦＰＧＡなどの集積回路である。
【００５６】
具体的には、処理用データ応答部２０４は、受信した処理用データ要求の送信元に対して応答として送信する。具体的には、処理用データ応答部２０４は、まず、処理用データ要求を受信すると、ハッシュ値の下限Ｈｍｉｎと上限Ｈｍａｘの差をサーバ数Ｎｓで割った値Ｈｗｉｄｔｈを求め、これを各サーバが要求処理を担当するハッシュ値の幅とする。要求処理サーバ装置データベース２１２から、処理データ要求の送信元の要求処理サーバ装置１００を検索し、その要求処理サーバ装置１００の要求処理サーバ装置データベース２１２内に登録されている番号をｎｒとする。データ管理装置側要求処理用データベース２１１に登録されている全ての識別子に対して、以下の処理を行う。データ管理装置側要求処理用データベース２１１のｉ番目に登録されているレコードを検索し、ハッシュ値をｈ、ランクをｒ、分散度をｄとする。ハッシュ値ｈに対して、Ｈｍｉｎ＋（ｎｒ−１）Ｈｗｉｄｔｈ≦ｈ、且つ、ｈ＜Ｈｍｉｎ＋ｎｒＨｗｉｄｔｈを満たすかを検査する。
【００５７】
ここで検査の条件を満足しなかった場合は、１≦ｒ＜Ｒｆを満足するかを検査する。Ｈｍｉｎ＋（ｎｒ−１）Ｈｗｉｄｔｈ≦ｈ、且つ、ｈ＜Ｈｍｉｎ＋ｎｒＨｗｉｄｔｈを満たすか、および、１≦ｒ＜Ｒｆを満足するかの検査の条件を満足した場合は、データ管理装置側要求処理用データベースのｉ番目に登録されているレコードの識別子と処理用データの組を応答用として記憶する。そして、１≦ｒ＜Ｒｆを満足するかの検査の条件を満足しなかった場合は、Ｒｆ≦ｒ＜Ｒｌの条件を満足するかを検査する。この条件を満足した場合は、Ｈｍｉｎ＋（ｎｓ−１）Ｈｗｉｄｔｈ≦ｈ、且つ、ｈ＜Ｈｍｉｎ＋ｎｓＨｗｉｄｔｈとなるｎｓをもとめる。その後、ｎｓ≦ｎｒ＜ｎｓ＋ｄの条件を満足するかを検査し、満足する場合は、データ管理装置側要求処理用データベース２１１のｉ番目に登録されているレコードの識別子と処理用データの組を応答用として記憶する。
【００５８】
また、ｎｓ≦ｎｒ＜ｎｓ＋ｄの条件を満足するかの検査の条件を満足しない場合、および、Ｒｆ≦ｒ＜Ｒｌの条件を満足するかの検査において、条件を満足しなかった場合は、データ管理装置側要求処理用データベースのｉ番目に登録されているレコードに関して、応答用のデータとしては、何も記憶しない。以上を、１≦ｉ≦Ｎｒを満たす全てのｉについて実行する。最後に、全ての応答用に記憶した識別子と処理用データの組を、受信した処理用データ要求の送信元に対して応答として送信する。
【００５９】
識別子割当決定部２０５は、図９に示すように、決定された各識別子のランクに応じて、ランクがＲｆよりも高く発生頻度が高い識別子が属するホットゾーン、ランクがＲｆ以下であってＲｌよりも高く発生頻度が中程度の識別子が属するノーマルゾーン、または、ランクがＲｌ以下であって発生頻度が低い識別子が属するコールドゾーンのいずれかに各識別子を振り分ける。
【００６０】
また、識別子割当決定部２０５は、ホットゾーンに振り分けられた識別子により識別されるデータの要求に対する応答処理を、全ての要求処理サーバ装置１００のうちのいずれかの要求処理サーバ装置１００に割り当て、ノーマルゾーンに振り分けられた識別子により識別されるデータの要求に対する応答処理を、複数の要求処理サーバ装置１００のうちのいずれかの要求処理サーバ装置１００に割り当て、コールドゾーンに振り分けられた識別子により識別されるデータの要求に対する応答処理を、一つのサーバ装置に割り当てる。
【００６１】
また、識別子割当決定部２０５は、ノーマルゾーンに属する識別子により識別されるデータの要求に対する応答処理が割り当てられる要求処理サーバ装置１００の延べ台数を、全要求処理サーバ装置１００の台数よりも十分に大きな値とするように、ＲｆおよびＲｌを設定する。
【００６２】
具体的には、識別子割当決定部２０５は、まず、コールドゾーンの最も頻度の高いランクであるＲｌ、および、ノーマルゾーンの最も頻度の高いランクであるＲｆを決定する。この処理については、後述する。次に、ハッシュ値の下限Ｈｍｉｎと上限Ｈｍaｘの差をサーバ数Ｎｓで割った値Ｈｗｉｄｔｈを求め、これを各サーバが要求処理を担当するハッシュ値の幅とする。その後、要求処理サーバ装置データベースに登録されている、番号ｉが、１からＮｓである各サーバｉについてループを繰り返す。ループ内の各繰り返しでは、以下の処理を行う。サーバｉの担当するハッシュ値の下限をＨｍｉｎ＋（ｉ―１）Ｈｗｉｄｔｈとする。
【００６３】
その後、サーバｉの担当するハッシュ値の上限をＨｍｉｎ＋ｉＨｗｉｄｔｈとする。これらの結果サーバｉの担当するハッシュ値は、ここで計算した下限以上、且つ、上限未満を担当することになる。最後に、図６に例示した要求処理サーバ装置データベース２１２から、番号がｉである要求処理サーバ装置情報を検索し、検索した要求処理サーバ装置情報・ハッシュ値上限・下限の範囲を、図７に示すハッシュ値要求処理サーバ装置変換用データベースに登録する。ここで、ハッシュ値要求処理サーバ装置変換用データベース２１３は、識別子のハッシュ値の範囲である担当領域と、その範囲に含まれる識別子の処理を担当する、要求処理サーバ装置情報によって構成される。
【００６４】
上記の識別子割当決定部の処理の中で、説明したコールドゾーンの最も頻度の高いランクであるＲｌ、および、ノーマルゾーンの最も頻度の高いランクであるＲｆの決定は、以下のように行う。
【００６５】
図１０は、これらのＲｌ、Ｒｆの決定の流れを表す。まず、要求処理サーバ装置単体で処理可能な識別子の発生頻度ｆｉは、データ管理装置の外部から指定され入力される。次に、ジップ定数ｐ、及び、総識別子数Ｎｒを決定する。最後に、要求処理サーバ装置総数Ｎｓ、コールドゾーンの最も頻度の高いランクであるＲｌ、および、ノーマルゾーンの最も頻度の高いランクであるＲｆを決定する。
【００６６】
図１０で示した流れに従い、最終的な、コールドゾーンの最も頻度の高いランクであるＲｌ、および、ノーマルゾーンの最も頻度の高いランクであるＲｆの決定する処理を以下に説明するが、まず、ジップ定数ｐの決定について説明する。
【００６７】
まず、発生頻度ｆ（ｒ）は、上述した（１）式で表すことができる。（１）式の両辺の対数をとると、下記の（４）式になる。
【００６８】
【数４】
2014164357.tif 000006
【００６９】
よって、頻度、及び、ランクを対数としたグラフを描くことで、その傾きがジップ定数ｐを表すことになる。図１１は、ジップの法則に従う場合の頻度とランクを縦軸・横軸とも対数にしたグラフに描いた状態を表しており、この傾きによりジップ定数ｐを計算することができる。頻度とランクの関係が、完全には、ジップの法則に従わない場合でも、最小二乗法を用いて、分布に近い直線の傾きを求めることが可能であり、これによりジップ定数ｐを定めることができる。
【００７０】
また、このとき、グラフの切片ｌｏｇ  ａについては、図１２のように、実際の頻度とランクの関係を全てのランクにおいて、上回るように分布を定めても良い。また、図１３のように、一定の値（図中では、１０６）よりも頻度の大きい領域、即ち、１００〜１０６の領域のランクにおいて、実際の頻度とランクの関係を上回るように分布を定めても良い。更に、一定の値よりも頻度の大きい領域において、最小二乗法などを用いて分布に近い直線を求めても良い。
【００７１】
ジップ定数ｐを決定した後、総識別子数Ｎｒを決定する。総識別子数Ｎｒの決定については、図５で示したデータ管理装置側要求処理用データベース２１１に含まれる識別子を数え上げることで決定することができる。その後、要求処理サーバ装置総数Ｎｓの決定を行う。本処理については、図３４を用いて後述する。
【００７２】
次に、ｐ＝１かどうかの判定を行う。ｐ＝１の場合、まず、それぞれ、値ＶｌとＶｆを計算する。ここで、Ｖｌ、および、Ｖｆは、それぞれ、Ｒｌ、および、Ｒｆを決定するための基準となる値である。その後、Ｖｆ≧１の判定を行い、Ｖｆ≧１の場合、「Ｖｆ≧１且つｐ＝１のときのＲｌとＲｆの決定」（詳細は、図３６）を実行する。この判定で、Ｖｆ≧１が否定された場合、「Ｖｆ＜１且つｐ＝１のときのＲｌとＲｆの決定」（詳細は、図３８）を実行する。
【００７３】
上記の判定において、ｐ＝１が否定された場合、それぞれ、値ＶｌとＶｆを計算する。その後、Ｖｆ≧１の判定を行い、Ｖｆ≧１の場合、「Ｖｆ≧１且つｐ≠１のときのＶｌとＶｆの決定」（詳細は、図３７）を実行する。上記の判定で、Ｖｆ≧１が否定された場合、「Ｖｆ＜１且つｐ≠１のときのＲｌとＲｆの決定」（詳細は、図３９）を実行する。
【００７４】
上記で説明した、「要求処理サーバ装置総数Ｎｓの決定」、「Ｖｆ≧１且つｐ＝１のときのＲｌとＲｆの決定」、「Ｖｆ＜１且つｐ＝１のときのＲｌとＲｆの決定」、「Ｖｆ≧１且つｐ≠１のときのＲｌとＲｆの決定」、及び、「Ｖｆ＜１且つｐ≠１のときのＲｌとＲｆの決定」について、それぞれ説明する。
【００７５】
「要求処理サーバ装置総数Ｎｓの決定」について、ランク１からランクＮｒまでの発生頻度の総和をＳとして求める。そして、Ｓを要求処理サーバ装置単体で処理可能な識別子の発生頻度ｆｉで割ることで、必要な要求処理サーバ装置総数を求める。要求処理サーバ装置総数は、１以上の整数でなければならないため、ここで計算した値を下回らない最小の整数を求めＮｓとする。
【００７６】
次に、「Ｖｆ≧１且つｐ＝１のときのＲｌとＲｆの決定」について説明する。まず、Ｖｌについて、その値を超えない最大の整数を求めＲｌに代入する。次に、このＲｌを基にしたＶｆを求め、そのＶｆを下回らない最小の整数をＲｆに代入する。ＲｌとＲｆの値が、下記（５）式を満足しているかを判定し、満足している場合は、それらの値をＲｌとＲｆとして採用する。上記の判定で条件を満足していない場合は、Ｒｌを１だけ増加させ、上記したＲｌを基にしたＶｆを求め、そのＶｆを下回らない最小の整数をＲｆに代入する処理を、条件を満足するまで繰り返し実施する。
【００７７】
【数５】
2014164357.tif 000007
【００７８】
次に、「Ｖｆ＜１且つｐ＝１のときのＲｌとＲｆの決定」について説明する。まず、下記（６）式を満足するＶｌを求め、Ｖｌの値を超えない最大の整数を求めてＲｌに代入する。次に、このＲｌを基にしたＶｆを求め、そのＶｆを下回らない最小の整数をＲｆに代入する。Ｒｆの値が、Ｒｆ≧１を満足しているかを判定し、満足している場合は、それらの値をＲｌとＲｆとして採用する。上記の判定で条件を満足していない場合は、Ｒｌを１だけ増加させ、上記したＲｌを基にしたＶｆを求め、そのＶｆを下回らない最小の整数をＲｆに代入する処理を、条件を満足するまで繰り返し実施する。
【００７９】
【数６】
2014164357.tif 000008
【００８０】
次に、「Ｖｆ≧１且つｐ≠１のときのＲｌとＲｆの決定」について説明する。まず、決定したＶｌについて、その値を超えない最大の整数を求めＲｆに代入する。次に、このＲｌを基にしたＶｆを求め、そのＶｆを下回らない最小の整数をＲｆに代入する。ＲｌとＲｆの値が、上記（５）式を満足しているかを判定し、満足している場合は、それらの値をＲｌとＲｆとして採用する。上記の判定で条件を満足していない場合は、Ｒｌを１だけ増加させ、上記したＲｌを基にしたＶｆを求め、そのＶｆを下回らない最小の整数をＲｆに代入する処理を、条件を満足するまで繰り返し実施する。
【００８１】
次に、「Ｖｆ＜１且つｐ≠１のときのＲｌとＲｆの決定」について説明する。まず、Ｖｌ−ｐ［Ｖｌ−（１−ｐ）ＫＮｓ］＝１、且つ、Ｖｌ≧０を満足するＶｌを求め、Ｖｌの値を超えない最大の整数を求めてＲｌに代入する。次に、このＲｌを基にしたＶｆを求め、そのＶｆを下回らない最小の整数をＲｆに代入する。Ｒｆの値が、Ｒｆ≧１を満足しているかを判定し、満足している場合は、それらの値をＲｌとＲｆとして採用する。上記の判定で条件を満足していない場合は、Ｒｌを１だけ増加させ、上記したＲｌを基にしたＶｆを求め、そのＶｆを下回らない最小の整数をＲｆに代入する処理を、条件を満足するまで繰り返し実施する。
【００８２】
本発明では、ＲｌとＲｆがなるべく小さくなる組合せを選択するために、識別子の発生頻度の分布がジップの法則に近く、ランクｒの識別子の発生頻度が１／ｒｐに比例する場合に、Ｒｌとして、ｐ≠１のとき、（１−ｐ）ＫＮｓ／（１−Ｎｓ（ｐ−１／ｐ））、ｐ＝１のとき、ｐＫＮｓ／ｌｏｇＮｓの近傍の値を用いる。また、Ｒｌとして、ｐ≠１のとき、Ｒｌ≧０且つＲｌ−ｐ［Ｒｌ−（１−ｐ）ＫＮｓ］＝１を満たすＲｌの値、ｐ＝１のとき、Ｒｌ＝ｅｘｐ（ＫＮｓ／Ｒｌ）を満足するＲｌの値の近傍の値を用いる。また、Ｒｆとして、ｐ≠１のとき、｛Ｒｌ−ｐ［Ｒｌ−（１−ｐ）ＫＮｓ］｝１／（１−ｐ）、ｐ＝１のとき、Ｒｌｅｘｐ（−ＫＮｓ／Ｒｌ）の近傍の値を用いる。
【００８３】
ここで、上記したＲｌとＲｆの決定方法を採用する理由について説明する。ノーマルゾーンにおける各ランクの負荷を分散させるサーバ数を以下の（７）式で表される台数とする。
【００８４】
【数７】
2014164357.tif 000009
【００８５】
ノーマルゾーンにおける、負荷を分散させるサーバの延べ台数は、各ランクでの分散させるサーバ数の総和であり、下記（８）式のようになる。
【００８６】
【数８】
2014164357.tif 000010
【００８７】
今、あるランクｒの負荷を、上記（７）式で表される台数のサーバに分散した場合、ランクｒの負荷を分割した結果として、サーバ１台当りに割り当てられる負荷は、下記（９）式で表される。
【００８８】
【数９】
2014164357.tif 000011
【００８９】
上式の分母は、サーバ台数が整数であるため、値がランク毎に異なってくる。そこで、各サーバに多くのランクの負荷を割り当てることにより、統計的な多重化の効果により、サーバ毎の負荷のばらつきが減ることになる。
【００９０】
そこで、上記の（８）式の値をサーバ台数のＫ倍(Ｋは１以上の実数)として、Ｋを、ある程度の大きな値とすることで負荷の平均化を計るものとする。即ち下記（１０）式のようになる。
【００９１】
【数１０】
2014164357.tif 000012
【００９２】
このことにより、Ｒｆが下記（１１）式の条件を満たすとき、負荷を分散させるサーバの延べ台数はＫＮｓ以上を確保できる。
【００９３】
【数１１】
2014164357.tif 000013
【００９４】
各ランクのサーバ台数は、式（７）で表され、これはサーバ台数Ｎｓを超えることができないことから下記（１２）式の条件を満足する必要がある。よって下記（１３）式のようになる。
【００９５】
【数１２】
2014164357.tif 000014
【００９６】
【数１３】
2014164357.tif 000015
【００９７】
今、あるＲｆの値に対して、上式の条件を満たすには、Ｒｌｐがとることのできる値の最大値は、ＮｓＲｆｐであることから、ＮｓＲｆｐ≦Ｒｌｐになり、結果として、下記（１４）式を満たす必要がある。
【００９８】
【数１４】
2014164357.tif 000016
【００９９】
式（１１）と式（１４）の不等式の等号が成立する式について、ＲｆとＲｌを変数としたグラフを描くと、図１４（Ｖｆ≧１且つｐ≧１の場合）、図１５（Ｖｆ≧１且つ０＜ｐ＜１の場合）、図１６（Ｖｆ＜１且つｐ≧１の場合）、及び、図１７（Ｖｆ＜１且つ０＜ｐ＜１の場合）のようになる。ここで、式（１１）と式（１４）の不等式の等号が成立する式の交点となる、Ｒｌ、及び、Ｒｆを、それぞれ、Ｖｌ、及び、Ｖｆとする。Ｖｌは、下記（１５）式のようになる。
【０１００】
【数１５】
2014164357.tif 000017
【０１０１】
図１４のＶｆ≧１且つｐ≧１の場合、及び、図１５のＶｆ≧１且つ０＜ｐ＜１の場合、領域Ａでは、式（１１）と式（１４）の条件が満足される領域である。領域Ｂ、及び、領域Ｃでは、サーバ数としてＮｓを超えた台数が必要であり、領域Ｃ、及び、領域Ｄでは、式（１１）が満たされず、ノーマルゾーンにおける、負荷を分散させるサーバの延べ台数が十分ではない領域である。よって、領域Ａの中でＲｌとＲｆを求める必要がある。
【０１０２】
領域Ａの中で、ＲｌとＲｆによって、Ｎｓ台のサーバに必要なメモリの延べ使用量がどのように変化するかを考える。コールドゾーンでは、各ランクに割り当てられるサーバ台数は１台であり、各ランクを処理するために必要な情報は、１台のサーバにのみ保持されるため、必要な延べメモリ量は、ノーマルゾーンやホットゾーンと比較して最小である。また、ホットゾーンは、Ｎｓ台のサーバで処理されるため、各ランクを処理するために必要な情報は、Ｎｓ台のサーバに保持されるため、必要な延べメモリ量は最大である。以上から、ＲｌとＲｆを最小化することが、メモリの延べ使用量を最小化することにつながる。図１４と図１５において、ＲｌとＲｆを最小化できるのは、式（１１）と式（１４）の不等式の等号が成立する式の交点となり、この交点に近い領域Ａに含まれる格子点を、ＲｌとＲｆとする必要がある。
【０１０３】
次に、図１６のＶｆ＜１且つｐ≧１の場合、及び、図１７のＶｆ＜１且つ０＜ｐ＜１の場合、領域Ｅでは、式（１１）と式（１４）の条件とＲｆが１以上である条件が満足される領域である。領域Ｇ、及び、領域Ｈでは、サーバ数としてＮｓを超えた台数が必要であり、領域Ｈ、領域Ｉ、及び、領域Ｊでは、式（１１）が満たされず、ノーマルゾーンにおける、負荷を分散させるサーバの延べ台数が十分ではない領域である。更に、領域Ｆは、Ｒｆが１未満となり、定義に反する領域である。よって、領域Ｅの中でＲｌとＲｆを求める必要がある。領域Ｅの中で、図１４と図１５の場合と同じように、メモリの延べ使用量を最小化するため、ＲｌとＲｆを最小化できるのは、式（１１）の不等式の等号が成立する式とＲｆ＝１の交点となり、この交点に近い領域Ａに含まれる格子点を、ＲｌとＲｆとする必要がある。以上のような理由から、第一の実施形態のようなＲｌとＲｆの決定方法を採用することで、効率的なサーバ利用に繋げることができる。
【０１０４】
頻度情報取得部２０６は、同一のデータをそれぞれ記憶する複数の要求処理サーバ装置１００に対してクライアント４００がデータを要求した際に、要求処理サーバ装置がクライアント４００から受信する識別子の受信頻度をそれぞれ取得する。
【０１０５】
まず、頻度情報取得部２０６は、データ管理装置側要求処理用データベース２１１の全識別子の頻度情報を０に初期化し、要求処理サーバ装置データベース２１２に登録されている全サーバに対して、以下の処理を行う。各要求処理サーバ装置１００に対しては、まず、頻度情報取得要求を送信する。これに対して、送信先の要求処理サーバ装置１００から、その要求処理サーバ装置１００が要求処理を行った全識別子の頻度情報を、識別子と頻度の組のリストとして受信する。受信した全識別子と頻度の組に対して、識別子毎に、その頻度情報を、データ管理装置側要求処理用データベース２１１の該当する識別子の頻度カラムに加算する。以上により、データ管理装置側要求処理用データベース２１１で管理する全識別子について、要求処理サーバ装置１００全体に対して行われた要求処理の頻度を計算する。
【０１０６】
識別子割当通知部２０７は、ハッシュ値の担当領域と要求処理サーバ装置情報の組、および、識別子ハッシュ値と識別子リストと分散度の組を負荷分散転送装置３００に送信する。具体的には、識別子割当通知部２０７は、ハッシュ値要求処理サーバ装置変換用データベース２１３に含まれるハッシュ値の担当領域と要求処理サーバ装置情報の組を全て、負荷分散転送装置３００に対して送信する。次に、識別子割当通知部２０７は、データ管理装置側分散度決定用データベース２１４の識別子ハッシュ値と識別子リストと分散度の組を全て、負荷分散転送装置３００に送信する。
【０１０７】
分散度決定部２０８は、全てのサーバｉに対して、ループにより、データ管理装置側要求処理用データベースに登録されているＮｒ個の識別子に対して分散度を決定し、データ管理装置側分散度決定用データベースに登録する。ループでは、ｉを１からＮｒまで変化させながら、データ管理装置側要求処理用データベースのｉ番目のレコードに記録されている識別子Ｉのハッシュ値ｈを計算し、ランクをｒとする。このランクｒが、ｒ＜Ｒｆを満足するかを検査し、満足するときは、識別子Ｉの分散度を０とする。ここで、分散度が、０であるということは、該当する識別子の処理を全ての要求処理サーバ装置で負荷分散することを意味し、該当する識別子がホットゾーンに存在することを意味する。上記の検査で条件を満足しない場合は、Ｒｆ≦ｒ＜Ｒｌを満足するかを検査し、満足するときは、分散度を式（７）でもとめる。
【０１０８】
この式（７）で求められる値は、Ｒｌｐ／ｒｐの値を下回らない最小の整数を表す。上記の検査を満足しないとき、分散度を１とするため、ｄ＝１とする。その後、データ管理装置側分散度決定用データベースからハッシュ値ｈを検索する。そして、ハッシュ値ｈのレコードの存在有無を判定し、存在した場合は、検索した分散度ｄ＊を読み取り、データ管理装置側分散度決定用データベースから検索したハッシュ値ｈのレコードに対して、識別子Ｉが含まれていない場合は、識別子Ｉを追記し、分散度をｍaｘ（ｄ，ｄ＊）として登録する。ここで、ｍaｘ（ｄ，ｄ＊）は、ｄとｄ＊のうち、大きいほうの値を意味する。上記の判定においてレコードが存在しない場合は、データ管理装置側分散度決定用データベースに対して、新規のレコードとして、ハッシュ値ｈ、識別子Ｉ、分散度ｄを登録する。以上の処理を１≦ｒ≦Ｎｒに対して行う。
【０１０９】
ランク決定部２０９は、取得された各識別子の受信頻度に応じて、各識別子のランクを決定する。具体的には、ランク決定部２０９は、データ管理装置側要求処理用データベースの識別子と頻度の組を頻度の高いものから低いものの順序でソートする。ソートしたときの各識別子の順序をその識別子のランクとして、データ管理装置側要求処理用データベースに登録する。上記の処理をループの処理で全ての識別子に対して行う。
【０１１０】
サーバ装置データ送信部２１０は、要求処理サーバ装置データベース２１２に登録されている要求処理サーバ装置１００の番号と要求処理サーバ装置情報の全ての組のリストを送信する。
【０１１１】
［負荷分散転送装置の構成］
次に、図１８を用いて、図１に示した負荷分散転送装置３００の構成を説明する。図１８は、第一の実施形態に係る負荷分散転送装置３００の構成を説明するための図である。図１８に示すように、負荷分散転送装置３００は、通信制御Ｉ／Ｆ部３０１、制御部３０２、記憶部３０３を有する。通信制御Ｉ／Ｆ部３０１は、要求処理サーバ装置１００、データ管理装置２００、および、クライアント４００との通信を行う。
【０１１２】
記憶部３０３は、図１８に示すように、ハッシュ値要求処理サーバ装置変換用データベース３０７、負荷分散転送装置用分散度決定用データベース３０８、要求処理サーバ装置データベース３０９を有する。記憶部３０３は、例えば、ＲＡＭ、フラッシュメモリ等の半導体メモリ素子、又は、ハードディスク、光ディスク等の記憶装置などである。
【０１１３】
ハッシュ値要求処理サーバ装置変換用データベース３０７および要求処理サーバ装置データベース３０９は、上述したデータ管理装置２００のハッシュ値要求処理サーバ装置変換用データベース２１３および要求処理サーバ装置データベース２１２と同様の情報を記憶しているため、説明を省略する。
【０１１４】
負荷分散転送装置用分散度決定用データベース３０８は、図１９に例示するように、各識別子のハッシュ値を示す「識別子ハッシュ値」と、その識別子ハッシュ値を持つ「識別子リスト」と、識別子の「払出位置」と、識別子の「分散度」とを記憶する。
【０１１５】
図１８に戻って、制御部３０２は、要求振分処理部３０４と、識別子割当受信部３０５と、サーバ装置データ受信部３０６とを有する。ここで、制御部３０２は、ＣＰＵやＭＰＵなどの電子回路やＡＳＩＣやＦＰＧＡなどの集積回路である。
【０１１６】
識別子割当受信部３０５は、まず、データ管理装置２００から、識別子に対するハッシュ値の担当領域と要求処理サーバ装置情報の組のリストを受信する。受信した、識別子に対するハッシュ値の担当領域と要求処理サーバ装置情報の組のリストを、負荷分散転送装置３００が管理するハッシュ値要求処理サーバ装置変換用データベース３０７に登録する。次に、データ管理装置２００から、識別子に対するハッシュ値、そのハッシュ値の識別子のリスト、分散度の組のリストを受信し、受信した識別子に対するハッシュ値、識別子のリスト、分散度を、負荷分散転送装置用分散度決定要データベース３０８の識別子ハッシュ値、識別子リスト、分散度として登録し、払出位置は、１として登録する。
【０１１７】
サーバ装置データ受信部３０６は、データ管理装置２００から、要求処理サーバ装置の番号と要求処理サーバ装置情報の組のリストを受信する。その後、受信した、要求処理サーバ装置の番号と要求処理サーバ装置情報の組のリストを負荷分散転送装置が管理する要求処理サーバ装置データベース３０９に受信した番号の昇順で登録する。要求処理サーバ装置データベース３０９は、データ管理装置２００のもつ要求処理サーバ装置データベース２１２と同じ構造を持つ。
【０１１８】
要求振分処理部３０４は、処理要求を受信すると、処理要求に含まれる識別子Ｉを取り出し、そのハッシュ値ｈを計算する。その計算したハッシュ値ｈを用いて、ハッシュ値要求処理サーバ装置変換用データベースの中から、ｈを担当領域に含む、レコードを検索し、ｈを担当領域とする要求処理サーバ装置情報をＳとする。検索したＳを元に、要求処理サーバ装置データベースを検索し、該当する要求処理サーバ装置の番号をｖとし、負荷分散装置側分散度決定用データベースからハッシュ値ｈを検索する。その結果をもとに、ハッシュ値ｈのレコードが存在するかの検査を行い、レコードが存在した場合には、検索したレコードから分散度ｄと払出位置ｐを読み出す。このとき、ｄ＝０であれば、分散度をＮｓとし、ｄ＝Ｎｓとする。読み出したｐを用いて、要求処理サーバ装置データベースから番号がｖ＋ｐ−１のレコードを検索し、そのレコードの要求処理サーバ装置をＳとする。その後、分散度決定用データベースから検索したハッシュ値ｈのレコードの払出位置をｐ＋１（ｍｏｄ  ｄ）に変更し、要求処理サーバ装置Ｓに処理要求を転送する。ここで、ｐ＋１（ｍｏｄ  ｄ）は、ｐ＋１をｄで割ったときの余りを表す。上記の検査において、レコードが存在しない場合には、Ｓの値は変更せず、そのまま要求処理サーバ装置Ｓに処理要求を転送する。
【０１１９】
［要求処理サーバによる処理］
次に、図２０を用いて、第一の実施形態に係る要求処理サーバ装置１００による処理を説明する。図２０は、処理用データ取得処理の処理手順を示すフローチャートである。
【０１２０】
同図に示すように、処理用データ取得部１０７は、まず、処理用データを送信する旨を、データ管理装置２００に要求する（Ｓ２００）。このとき、本要求に、要求を行う要求処理サーバ装置情報を含める。そして、この処理用データ管理装置を受信したデータ管理装置２００は、処理用データを要求処理サーバ装置１００に対して応答する。続いて、処理用データ取得部１０７は、データ管理装置２００から送られてきた、該当要求処理サーバ装置用の処理用データを受信する（Ｓ２０１）。その後受信した識別子と処理用データの組を図３で示す要求処理サーバ装置側要求処理用データベース１０８に格納する（Ｓ２０２）。最後に、要求処理サーバ装置側要求処理用データベース１０８の全てのレコードの頻度を、０として初期化する（Ｓ２０３）。
【０１２１】
次に、図２１を用いて、第一の実施形態に係る要求処理サーバ装置１００による処理を説明する。図２１は、サービス応答処理の処理手順を示すフローチャートである。同図に示すように、サービス応答部１０４は、最初に、サービスの処理要求を受信すると（Ｓ２１０）、処理要求に含まれる識別子を取り出し、これを含むレコードを要求処理サーバ装置側要求処理用データベース１０８から検索する（Ｓ２１１）。ここで、サービス応答部１０４は、処理要求に含まれている識別子が要求処理サーバ装置側要求処理用データベース１０８に含まれているか、否かを検査する（Ｓ２１２）。
【０１２２】
本検査において、サービス応答部１０４は、識別子が要求処理サーバ装置側要求処理用データベースに含まれていた場合、検索したレコードから該当する識別子に対する処理用データを用いて処理要求に対する応答を作成する（Ｓ２１３）。その後、サービス応答部１０４は、受信した処理要求に含まれる識別子に対する頻度情報を更新するために頻度情報更新部に依頼して頻度情報更新処理を実施し（Ｓ２１４）、最後に、応答を送信する（Ｓ２１５）。また、Ｓ２１２の検査において、サービス応答部１０４は、識別子が要求処理サーバ装置側処理用データベースに含まれていなかった場合、登録されていない識別子に対する応答を作成し（Ｓ２１６）、応答を送信する（Ｓ２１５）。
【０１２３】
次に、図２２を用いて、第一の実施形態に係る要求処理サーバ装置１００による処理を説明する。図２２は、頻度情報更新部の処理手順を示すフローチャートである。同図に示すように、頻度情報更新部１０５は、最初に、処理要求に含まれる識別子をもとにして、要求処理サーバ装置側要求処理用データベース１０８から該当するレコードを検索する（Ｓ２２０）。次に、頻度情報更新部１０５は、該当するレコードの頻度情報を読み込み後、頻度情報をインクリメントし（Ｓ２２１）、その後、該当するレコードの頻度情報の変更を行う（Ｓ２２２）。なお、前述したように、頻度の情報は、該当する識別子を含む要求処理の発生回数を表す値を格納している。
【０１２４】
次に、図２３を用いて、第一の実施形態に係る要求処理サーバ装置１００による処理を説明する。図２３は、頻度情報取得要求部の処理手順を示すフローチャートである。同図に示すように、頻度情報取得要求処理部１０６は、最初に、データ管理装置から、頻度情報取得要求処理を受信する（Ｓ２３０）。要求処理サーバ装置側要求処理用データベースの、ｉ番目のレコードについて、ｉを１からＮｒまで変化させながら（Ｓ２３１、Ｓ２３５）、全てのレコードに対して以下の処理を行う。
【０１２５】
つまり、頻度情報取得要求処理部１０６は、ｉ番目のレコードについて、識別子と頻度情報の組を取得する（Ｓ２３２）。取得した頻度情報を、識別子とともにデータ管理装置２００に送信するために記憶する（Ｓ２３３）。全てのレコードに対してＳ２３２とＳ２３３の処理を実施したのち（Ｓ２３４の判定において、Ｎｏの場合）、送信用に記憶した識別子と、頻度情報の組を全て送信する（Ｓ２３６）。
【０１２６】
［データ管理装置による処理］
次に、図２４を用いて、第一の実施形態に係るデータ管理装置２００による処理を説明する。図２４は、処理用データ応答部の処理手順を示すフローチャートである。同図に示すように、処理用データ応答部２０４は、まず、処理用データ要求を受信すると（Ｓ２４０）、ハッシュ値の下限Ｈｍｉｎと上限Ｈｍａｘの差をサーバ数Ｎｓで割った値Ｈｗｉｄｔｈを求め、これを各サーバが要求処理を担当するハッシュ値の幅とする（Ｓ２４１）。要求処理サーバ装置データベース２１２から、処理データ要求の送信元の要求処理サーバ装置１００を検索し、その要求処理サーバ装置１００の要求処理サーバ装置データベース２１２内に登録されている番号をｎｒとする（Ｓ２４２）。データ管理装置側要求処理用データベース２１１に登録されている全ての識別子に対して、以下の処理を行う（Ｓ２４３、Ｓ２５３）。データ管理装置側要求処理用データベース２１１のｉ番目に登録されているレコードを検索し、ハッシュ値をｈ、ランクをｒ、分散度をｄとする（Ｓ２４４）。ハッシュ値ｈに対して、Ｈｍｉｎ＋（ｎｒ−１）Ｈｗｉｄｔｈ≦ｈ、且つ、ｈ＜Ｈｍｉｎ＋ｎｒＨｗｉｄｔｈを満たすかを検査する（Ｓ２４５）。
【０１２７】
ここで検査の条件を満足しなかった場合は、１≦ｒ＜Ｒｆを満足するかを検査する（Ｓ２４６）。Ｓ２４５、および、Ｓ２４６での検査の条件を満足した場合は、データ管理装置側要求処理用データベースのｉ番目に登録されているレコードの識別子と処理用データの組を応答用として記憶する（Ｓ２５０）。Ｓ２４６の検査の条件を満足しなかった場合は、Ｒｆ≦ｒ＜Ｒｌの条件を満足するかを検査する（Ｓ２４７）。この条件を満足した場合は、Ｈｍｉｎ＋（ｎｒ−１）Ｈｗｉｄｔｈ≦ｈ、且つ、ｈ＜Ｈｍｉｎ＋ｎｒＨｗｉｄｔｈとなるｎｓをもとめる（Ｓ２５１）。その後、Ｓ２５２で、ｎｓ≦ｎｒ＜ｎｓ＋ｄの条件を満足するかを検査し、満足する場合は、データ管理装置側要求処理用データベースのｉ番目に登録されているレコードの識別子と処理用データの組を応答用として記憶する（Ｓ２５０）。Ｓ２５２で検査の条件を満足しない場合、および、Ｓ２４７の検査において、条件を満足しなかった場合は、データ管理装置側要求処理用データベースのｉ番目に登録されているレコードに関して、応答用のデータとしては、何も記憶しない。以上を、１≦ｉ≦Ｎｒを満たす全てのｉについて実行する（Ｓ２４８）。最後に、全ての応答用に記憶した識別子と処理用データの組を、Ｓ２４０で受信した処理用データ要求の送信元に対して応答として送信する（Ｓ２４９）。
【０１２８】
次に、図２５を用いて、第一の実施形態に係るデータ管理装置２００による処理を説明する。図２５は、識別子割当決定部の処理手順を示すフローチャートである。同図に示すように、識別子割当決定部２０５は、まず、コールドゾーンの最も頻度の高いランクであるＲｌ、および、ノーマルゾーンの最も頻度の高いランクであるＲｆを決定する（Ｓ２６０）。このＳ２６０の処理については、後述する。次に、ハッシュ値の下限Ｈｍｉｎと上限Ｈｍaｘの差をサーバ数Ｎｓで割った値Ｈｗｉｄｔｈを求め、これを各サーバが要求処理を担当するハッシュ値の幅とする（Ｓ２６１）。ここで、サーバ数Ｎｓは、Ｓ２６０の処理の中で決定される。そして、番号ｉを１にする（Ｓ２６２）。その後、要求処理サーバ装置データベースに登録されている、番号ｉが、１からＮｓである各サーバｉについてＳ２６３からＳ２６８のループを繰り返す。ループ内の各繰り返しでは、以下の処理を行う。サーバｉの担当するハッシュ値の下限をＨｍｉｎ＋（ｉ−１）Ｈｗｉｄｔｈとする（Ｓ２６３）。
【０１２９】
その後、サーバｉの担当するハッシュ値の上限をＨｍｉｎ＋ｉＨｗｉｄｔｈとする（Ｓ２６４）。これらの結果サーバｉの担当するハッシュ値は、ここで計算した下限以上、且つ、上限未満を担当することになる。最後に図６に例示した要求処理サーバ装置データベース２１２から、番号がｉである要求処理サーバ装置情報を検索し（Ｓ２６５）、検索した要求処理サーバ装置情報・ハッシュ値上限・下限の範囲を、図７に示すハッシュ値要求処理サーバ装置変換用データベースに登録する（Ｓ２６６）。ここで、ハッシュ値要求処理サーバ装置変換用データベース２１３は、識別子のハッシュ値の範囲である担当領域と、その範囲に含まれる識別子の処理を担当する、要求処理サーバ装置情報によって構成される。
【０１３０】
その後、ｉ＜Ｎｓであるか否かを判定する（Ｓ２６７）。そして、ｉ＜Ｎｓである場合には、ｉに１を加算して（Ｓ２６８）、Ｓ２６３に戻り、ｉ＜Ｎｓで無い場合には、処理を終了する。
【０１３１】
次に、図２６を用いて、第一の実施形態に係るデータ管理装置２００による処理を説明する。図２６は、頻度情報取得部の処理手順を示すフローチャートである。同図に示すように、頻度情報取得部２０６は、まず、データ管理装置側要求処理用データベース２１１の全識別子の頻度情報を０に初期化し（Ｓ２７０）、番号ｉを１にし（Ｓ２７１）、Ｓ２７２からＳ２７６のループで表される処理により、要求処理サーバ装置データベース２１２に登録されている全サーバに対して、以下の処理を行う。各要求処理サーバ装置１００に対しては、まず、頻度情報取得要求を送信する（Ｓ２７２）。これに対して、送信先の要求処理サーバ装置１００から、その要求処理サーバ装置１００が要求処理を行った全識別子の頻度情報を、識別子と頻度の組のリストとして受信する（Ｓ２７３）。受信した全識別子と頻度の組に対して、識別子毎に、その頻度情報を、データ管理装置側要求処理用データベース２１１の該当する識別子の頻度カラムに加算する（Ｓ２７４）。以上により、データ管理装置側要求処理用データベース２１１で管理する全識別子について、要求処理サーバ装置１００全体に対して行われた要求処理の頻度を計算する。その後、ｉ＜Ｎｓであるか否かを判定する（Ｓ２７５）。そして、ｉ＜Ｎｓである場合には、ｉに１を加算して（Ｓ２７６）、Ｓ２７２に戻り、ｉ＜Ｎｓで無い場合には、処理を終了する。
【０１３２】
次に、図２７を用いて、第一の実施形態に係るデータ管理装置２００による処理を説明する。図２７は、分散度決定部の処理手順を示すフローチャートである。同図に示すように、分散度決定部２０８は、まず、番号ｉを１にし（Ｓ２８０）、全てのサーバｉに対して、Ｓ２８１からＳ２９４のループにより、データ管理装置側要求処理用データベースに登録されているＮｒ個の識別子に対して分散度を決定し、データ管理装置側分散度決定用データベースに登録する。ループでは、ｉを１からＮｒまで変化させながら、データ管理装置側要求処理用データベースのｉ番目のレコードに記録されている識別子Ｉのハッシュ値ｈを計算し（Ｓ２８１）、ランクをｒとする（Ｓ２８２）。このランクｒが、ｒ＜Ｒｆを満足するかを検査し（Ｓ２８３）、満足するときは、識別子Ｉの分散度ｄを０とする（Ｓ２９１）。ここで、分散度が、０であるということは、該当する識別子の処理を全ての要求処理サーバ装置で負荷分散することを意味し、該当する識別子がホットゾーンに存在することを意味する。Ｓ２８３の検査で条件を満足しない場合は、Ｒｆ≦ｒ＜Ｒｌを満足するかを検査し（Ｓ２８４）、満足するときは、分散度を式（７）でもとめる（Ｓ２９２）。この式（７）で求められる値は、Ｒｌｐ／ｒｐの値を下回らない最小の整数を表す。Ｓ２８４の検査を満足しないとき、分散度を１とするため、ｄ＝１とする（Ｓ２８５）。その後、及び、Ｓ２９１とＳ２９２の処理を行った後は、データ管理装置側分散度決定用データベースからハッシュ値ｈを検索する（Ｓ２８６）。そして、ハッシュ値ｈのレコードの存在有無を判定し（Ｓ２８７）、存在した場合は、検索した分散度ｄ＊を読み取り（Ｓ２９３）、データ管理装置側分散度決定用データベースから検索したハッシュ値ｈのレコードに対して、識別子Ｉが含まれていない場合は、識別子Ｉを追記し、分散度をｍaｘ（ｄ，ｄ＊）として登録する（Ｓ２９４）。ここで、ｍaｘ（ｄ，ｄ＊）は、ｄとｄ＊のうち、大きいほうの値を意味する。Ｓ２８７の判定においてレコードが存在しない場合は、データ管理装置側分散度決定用データベースに対して、新規のレコードとして、ハッシュ値ｈ、識別子Ｉ、分散度ｄを登録する（Ｓ２８８）。以上の処理を１≦ｒ≦Ｎｒに対して行う。つまり、ｉ＜Ｎｒであるか否かを判定する（Ｓ２８９）。そして、ｉ＜Ｎｒである場合には、ｉに１を加算して（Ｓ２９０）、Ｓ２８１に戻り、ｉ＜Ｎｒで無い場合には、処理を終了する。
【０１３３】
次に、図２８を用いて、第一の実施形態に係るデータ管理装置２００による処理を説明する。図２８は、ランク決定部の処理手順を示すフローチャートである。同図に示すように、ランク決定部２０９は、データ管理装置側要求処理用データベースの識別子と頻度の組を頻度の高いものから低いものの順序でソートする（Ｓ３００）。ソートしたときの各識別子の順序をその識別子のランクとして、データ管理装置側要求処理用データベースに登録する（Ｓ３０２）。これをＳ３０２からＳ３０４のループの処理で全ての識別子に対して行う。つまり、ｉ＜Ｎｒであるか否かを判定する（Ｓ３０３）。そして、ｉ＜Ｎｒである場合には、ｉに１を加算して（Ｓ３０４）、Ｓ３０２に戻り、ｉ＜Ｎｒで無い場合には、処理を終了する。
【０１３４】
次に、図２９を用いて、第一の実施形態に係るデータ管理装置２００による処理を説明する。図２９は、サーバ装置データ送信部の処理手順を示すフローチャートである。同図に示すように、サーバ装置データ送信部２１０は、要求処理サーバ装置データベース２１２に登録されている要求処理サーバ装置１００の番号と要求処理サーバ装置情報の全ての組のリストを送信する（Ｓ３０７）。
【０１３５】
次に、図３０を用いて、第一の実施形態に係るデータ管理装置２００による処理を説明する。図３０は、識別子割当通知部の処理手順を示すフローチャートである。同図に示すように、識別子割当通知部２０７は、ハッシュ値要求処理サーバ装置変換用データベースに含まれるハッシュ値の担当領域と要求処理サーバ装置情報の組を全て、負荷分散転送装置に対して送信する（Ｓ３１０）。識別子割当通知部２０７は、識別子割当通知処理を行うために、負荷分散転送装置への通信に必要な情報を保持している。次に、データ管理装置側分散度決定用データベースの識別子ハッシュ値と識別子リストと分散度の組を全て、負荷分散転送装置に送信する（Ｓ３１１）。
【０１３６】
［負荷分散転送装置による処理］
次に、図３１を用いて、第一の実施形態に係る負荷分散転送装置３００による処理を説明する。図３１は、識別子割当受信部の処理手順を示すフローチャートである。
【０１３７】
同図に示すように、識別子割当受信部３０５は、まず、データ管理装置２００から、識別子に対するハッシュ値の担当領域と要求処理サーバ装置情報の組のリストを受信する（Ｓ３２０）。受信した、識別子に対するハッシュ値の担当領域と要求処理サーバ装置情報の組のリストを、負荷分散転送装置３００が管理するハッシュ値要求処理サーバ装置変換用データベース３０７に登録する（Ｓ３２１）。次に、データ管理装置２００から、識別子に対するハッシュ値、そのハッシュ値の識別子のリスト、分散度の組のリストを受信し（Ｓ３２２）、受信した識別子に対するハッシュ値、識別子のリスト、分散度を、負荷分散転送装置用分散度決定要データベース３０８の識別子ハッシュ値、識別子リスト、分散度として登録し、払出位置は、１として登録する（Ｓ３２３）。
【０１３８】
次に、図３２を用いて、第一の実施形態に係る負荷分散転送装置３００による処理を説明する。図３２は、サーバ装置データ受信部の処理手順を示すフローチャートである。負荷分散転送装置３００のサーバ装置データ受信部３０６は、データ管理装置２００から、要求処理サーバ装置の番号と要求処理サーバ装置情報の組のリストを受信する（Ｓ３３０）。その後、受信した、要求処理サーバ装置の番号と要求処理サーバ装置情報の組のリストを負荷分散転送装置が管理する要求処理サーバ装置データベースに受信した番号の昇順で登録する（Ｓ３３１）。
【０１３９】
次に、図３３を用いて、第一の実施形態に係る負荷分散転送装置３００による処理を説明する。図３３は、要求振り分け部の処理手順を示すフローチャートである。要求振り分け部３０４は、処理要求を受信する（Ｓ３４０）と、要求処理に含まれる識別子Ｉを取り出し、そのハッシュ値ｈを計算する（Ｓ３４１）。その計算したハッシュ値ｈを用いて、ハッシュ値要求処理サーバ装置変換用データベースの中から、ｈを担当領域に含む、レコードを検索し、ｈを担当領域とする要求処理サーバ装置情報をＳとする（Ｓ３４２）。検索したＳを元に、要求処理サーバ装置データベースを検索し、該当する要求処理サーバ装置の番号をｖとし（Ｓ３４３）、負荷分散装置用分散度決定用データベースからハッシュ値ｈを検索する（Ｓ３４４）。
【０１４０】
その結果をもとに、ハッシュ値ｈのレコードが存在するかの検査を行い（Ｓ３４５）、レコードが存在した場合には、検索したレコードから分散度ｄと払出位置ｐを読み出す（Ｓ３４７）。このとき、ｄ＝０であれば、分散度をＮｓとし、ｄ＝Ｎｓとする。読み出したｐを用いて、要求処理サーバ装置データベースから番号がｖ＋ｐ−１のレコードを検索し、そのレコードの要求処理サーバ装置をＳとする（Ｓ３４８）。その後、負荷分散装置用分散度決定用データベースから検索したハッシュ値ｈのレコードの払出位置をｐ＋１（ｍｏｄ  ｄ）に変更し（Ｓ３４９）、要求処理サーバ装置Ｓに処理要求を転送する（Ｓ３４６）。ここで、ｐ＋１（ｍｏｄ  ｄ）は、ｐ＋１をｄで割ったときの余りを表す。Ｓ３４５の検査において、レコードが存在しない場合には、Ｓの値は変更せず、そのまま要求処理サーバ装置Ｓに処理要求を転送する。
【０１４１】
次に、図３４を用いて、第一の実施形態に係る負荷分散転送装置３００による処理を説明する。図３４は、サーバ装置数の決定処理の処理手順を示すフローチャートである。なお、ここでの処理は、後述する図３５のＳ５４２において実行される処理である。同図に示すように、Ｓ５３０、Ｓ５３１、Ｓ５３２、及び、Ｓ５３３により、ランク１からランクＮｒまでの発生頻度の総和をＳとして求める。そして、Ｓを要求処理サーバ装置単体で処理可能な識別子の発生頻度ｆｉで割ることで、必要な要求処理サーバ装置総数を求める。要求処理サーバ装置総数は、１以上の整数でなければならないため、ここで計算した値を下回らない最小の整数を求めＮｓとする（Ｓ５３４）。
【０１４２】
次に、図３５を用いて、ＲｌとＲｆの決定処理を説明する。図３５は、ホット・ノーマルゾーン境界とノーマル・コールドゾーン境界の決定処理の処理手順を示すフローチャートである。同図に示すように、まず、ジップ定数ｐの決定を行う（Ｓ５４０）。そして、ジップ定数ｐを決定した後、総識別子数Ｎｒを決定する（Ｓ５４１）。総識別子数Ｎｒの決定については、図５で示したデータ管理装置側要求処理用データベース２１１に含まれる識別子を数え上げることで決定することができる。Ｓ５４１の後、要求処理サーバ装置総数Ｎｓの決定（Ｓ５４２）を行う（図３４参照）。
【０１４３】
次にＳ５４３で、ｐ＝１かどうかの判定を行う。ｐ＝１の場合、まず、Ｓ５４４、Ｓ５４５で、それぞれ、値ＶｌとＶｆを計算する。ここで、Ｖｌ、および、Ｖｆは、それぞれ、Ｒｌ、および、Ｒｆを決定するための基準となる値である。その後、Ｖｆ≧１の判定（Ｓ５４６）を行い、Ｖｆ≧１の場合、Ｓ５４７で、「Ｖｆ≧１且つｐ＝１のときのＲｌとＲｆの決定」（詳細は、図３６）を実行する。Ｓ５４６の判定で、Ｖｆ≧１が否定された場合、Ｓ５４８で、「Ｖｆ＜１且つｐ＝１のときのＲｌとＲｆの決定」（詳細は、図３８）を実行する。
【０１４４】
Ｓ５４３の判定において、ｐ＝１が否定された場合、Ｓ５４９、Ｓ５５０で、それぞれ、値ＶｌとＶｆを計算する。その後、Ｖｆ≧１の判定（Ｓ５５１）を行い、Ｖｆ≧１の場合、Ｓ５５２で、「Ｖｆ≧１且つｐ≠１のときのＶｌとＶｆの決定」（詳細は、図３７）を実行する。Ｓ５５１の判定で、Ｖｆ≧１が否定された場合、Ｓ５５３で、「Ｖｆ＜１且つｐ≠１のときのＲｌとＲｆの決定」（詳細は、図３９）を実行する。
【０１４５】
次に、図３６を用いて、Ｖｆ≧１且つｐ＝１のときのＲｌとＲｆの決定処理を説明する。図３６は、Ｖｆ≧１且つｐ＝１のときのＲｌとＲｆの決定処理の処理手順を示すフローチャートである。同図に示すように、「Ｖｆ≧１且つｐ＝１のときのＲｌとＲｆの決定」について説明する。まず、Ｓ５４４で決定したＶｌについて、その値を超えない最大の整数を求めＲｌに代入する（Ｓ５６０）。次に、このＲｌを基にしたＶｆを求め（Ｓ５６１）、そのＶｆを下回らない最小の整数をＲｆに代入する（Ｓ５６２）。ＲｌとＲｆの値が、上記（５）式を満足しているかを判定し（Ｓ５６３）、満足している場合は、それらの値をＲｌとＲｆとして採用する。Ｓ５６３の判定で条件を満足していない場合は、Ｒｌを１だけ増加させ（Ｓ５６４）、上記のＳ５６１からＳ５６３の処理を実施する。
【０１４６】
次に、図３７を用いて、Ｖｆ≧１且つｐ≠１のときのＲｌとＲｆの決定処理を説明する。図３７は、Ｖｆ≧１且つｐ≠１のときのＲｌとＲｆの決定処理の処理手順を示すフローチャートである。同図に示すように、「Ｖｆ≧１且つｐ≠１のときのＲｌとＲｆの決定」について説明する。まず、Ｓ５４９で決定したＶｌについて、その値を超えない最大の整数を求めＲｌに代入する（Ｓ５７０）。次に、このＲｌを基にしたＶｆを求め（Ｓ５７１）、そのＶｆを下回らない最小の整数をＲｆに代入する（Ｓ５７２）。ＲｌとＲｆの値が、上記（５）式を満足しているかを判定し（Ｓ５７３）、満足している場合は、それらの値をＲｌとＲｆとして採用する。Ｓ５７３の判定で条件を満足していない場合は、Ｒｌを１だけ増加させ（Ｓ５７４）、上記のＳ５７１からＳ５７３の処理を実施する。
【０１４７】
次に、図３８を用いて、Ｖｆ＜１且つｐ＝１のときのＲｌとＲｆの決定処理について説明する。図３８は、Ｖｆ＜１且つｐ＝１のときのＲｌとＲｆの決定処理の処理手順を示すフローチャートである。同図に示すように、「Ｖｆ＜１且つｐ＝１のときのＲｌとＲｆの決定」について説明する。まず、上記（６）式を満足するＶｌを求め（Ｓ５８０）、Ｖｌの値を超えない最大の整数を求めてＲｌに代入する（Ｓ５８１）。次に、このＲｌを基にしたＶｆを求め（Ｓ５８２）、そのＶｆを下回らない最小の整数をＲｆに代入する（Ｓ５８３）。Ｒｆの値が、Ｒｆ≧１を満足しているかを判定し（Ｓ５８４）、満足している場合は、それらの値をＲｌとＲｆとして採用する。Ｓ５８４の判定で条件を満足していない場合は、Ｒｌを１だけ増加させ（Ｓ５８５）、上記のＳ５８２からＳ５８４の処理を実施する。
【０１４８】
次に、図３９を用いて、Ｖｆ＜１且つｐ≠１のときのＲｌとＲｆの決定処理について説明する。図３９は、Ｖｆ＜１且つｐ≠１のときのＲｌとＲｆの決定処理の処理手順を示すフローチャートである。まず、Ｖｌ−ｐ［Ｖｌ−（１−ｐ）ＫＮｓ］＝１、且つ、Ｖｌ≧０を満足するＶｌを求め（Ｓ５９０）、Ｖｌの値を超えない最大の整数を求めてＲｌに代入する（Ｓ５９１）。次に、このＲｌを基にしたＶｆを求め（Ｓ５９２）、そのＶｆを下回らない最小の整数をＲｆに代入する（Ｓ５９３）。Ｒｆの値が、Ｒｆ≧１を満足しているかを判定し（Ｓ５９４）、満足している場合は、それらの値をＲｌとＲｆとして採用する。Ｓ５９４の判定で条件を満足していない場合は、Ｒｌを１だけ増加させ（Ｓ５９５）、上記のＳ５９２からＳ５９４の処理を実施する。
【０１４９】
[第一の実施形態の効果]
上述してきたように、データ管理装置２００は、決定された各識別子のランクに応じて、ランクがＲｆよりも高く発生頻度が高い識別子が属するホットゾーン、ランクがＲｆ以下であってＲｌよりも高く発生頻度が中程度の識別子が属するノーマルゾーン、または、ランクがＲｌ以下であって発生頻度が低い識別子が属するコールドゾーンのいずれかに各識別子を振り分ける。そして、データ管理装置２００は、ホットゾーンに振り分けられた識別子により識別されるデータの要求に対する応答処理を、全ての要求処理サーバ装置１００のうちのいずれかの要求処理サーバ装置１００に割り当て、ノーマルゾーンに振り分けられた識別子により識別されるデータの要求に対する応答処理を、複数の要求処理サーバ装置１００のうちのいずれかの要求処理サーバ装置１００に割り当て、コールドゾーンに振り分けられた識別子により識別されるデータの要求に対する応答処理を、一つのサーバ装置に割り当てる。そして、データ管理装置２００は、ノーマルゾーンに属する識別子により識別されるデータの要求に対する応答処理が割り当てられる要求処理サーバ装置１００の延べ台数を、全要求処理サーバ装置１００の台数よりも十分に大きな値とするように、ＲｆおよびＲｌを設定する。このため、サーバ負荷を平準化することができる。また、要求処理の負荷を分散し、且つ、記憶装置の容量を小さくすることが可能である。
【０１５０】
上述してきたように、データ管理装置２００は、ノーマルゾーンに属する識別子により識別されるデータの要求に対する応答処理が割り当てられる要求処理サーバ装置１００の延べ台数を、全要求処理サーバ装置１００の台数よりも十分に大きな値とするようにＲｆおよびＲｌを設定しつつ、ＲｆおよびＲｌをできるだけ小さい値に設定する。このため、必要な記憶容量の最小化を図ることが可能である。
【０１５１】
また、ホットゾーンの識別子を処理するために必要な情報は、全サーバ装置で保持され、ノーマルゾーンの識別子を処理するために必要な情報は、その識別子の発生頻度に応じた台数のサーバ装置に保持される。一方で、コールドゾーンの識別子については、コンシステントハッシング法を用いた場合と同様に、１台のサーバ装置に保持される。よって、各サーバ装置が全ての識別子を処理するために必要な情報を保持しなくてもよいため、個々のサーバ装置の記憶装置の容量を大規模化しなくてもよい。
【０１５２】
また、第一の実施形態によれば、各サーバ装置の記憶装置の容量を大規模化する必要はなく、ノーマルゾーンおよびコールドゾーンの識別子を処理するための情報は、サーバ装置間で分担して保持させることが可能となり、サーバ装置を増加させることによって、識別子の増加に対応することが可能となり、結果としてスケールアウトが可能となる。
【０１５３】
単一の識別子の発生頻度が、非常に高いものについては、ホットゾーンとして、全サーバ装置で負荷分散されるか、ノーマルゾーンとして、発生頻度に応じて決まる台数のサーバ装置で負荷分散される。よって、単一のサーバ装置で処理できる性能を超えている場合においても、サーバ装置間の負荷分散が実現可能であり、装置台数を増やすことによって、性能および識別子増加に対応するスケールアウトが可能となる。
【０１５４】
ホットゾーンやノーマルゾーンの発生頻度の高い識別子を単一のサーバ装置で処理する必要がなくなり、複数のサーバ装置で負荷分散することにより、全てのサーバ装置が、多くの識別子を担当できるようになる。このことにより、サーバ装置の記憶容量の利用効率を平準化し、高く保つことが可能となる。また、ホットゾーンおよびノーマルゾーンに含まれるランクの識別子については、複数のサーバ装置で担当する。このとき、ホットゾーンおよびノーマルゾーンに含まれるランクの各識別子の処理を担当するサーバ装置の台数Ｎｄｉｖ（ｒ）の総和（上記の（２）式参照）の、Ｎservに対する倍率が、十分に大きな倍率Ｋに近い値となるようにすることで(即ち上記（３）式の値に近くする)、各サーバ装置に、Ｋ個程度の識別子の負荷を分担させることができる。各識別子の処理によって発生する負荷を分割した値に一定程度のばらつきがあっても、負荷を分割した値が、各装置に、十分に大きな数Ｋ個程度割り当てられることにより、各サーバ装置で担当する識別子の数のばらつきも小さくなり、サーバ装置の記憶容量の利用効率を平準化し、高く保つことが可能となる。また、ＲｆとＲｌがなるべく小さい値となる組合せを選択することにより、ホットゾーン、および、ノーマルゾーンの領域が小さくなることにより記憶装置の容量を小さくすることが可能となる。
【０１５５】
ホットゾーンおよびノーマルゾーンに含まれるランクの識別子については、複数のサーバ装置で担当する。このとき、ホットゾーンおよびノーマルゾーンに含まれるランクの各識別子の処理を担当するサーバ装置の台数Ｎｄｉｖ（ｒ）の総和（上記の（２）式参照）の、Ｎservに対する倍率が、十分に大きな倍率Ｋに近い値となるようにすることで(即ち上記（３）式の値に近くする)、各サーバ装置に、Ｋ個程度の識別子の負荷を分担させることができる。各識別子の処理によって発生する負荷を分割した値に一定程度のばらつきがあっても、負荷を分割した値が、各装置に、十分に大きな数Ｋ個程度割り当てられることにより、各サーバ装置で担当する負荷のばらつきも小さくなり、サーバ装置の負荷の偏りを小さくすることが可能であり、結果としてサーバ装置台数を削減できる。また、ＲｆとＲｌがなるべく小さい値となる組合せを選択することにより、ホットゾーン、および、ノーマルゾーンの領域が小さくなることにより記憶装置の容量を小さくすることが可能となる。
【０１５６】
［全サーバ装置の数］
上記の説明では、全サーバ装置の数Ｎｓを、図３４に示した処理によって決定したが、全サーバ装置の数Ｎｓは、本システムを管理する者がシステムに対して決定を行い、システムに与えても良い。この場合、第一の実施形態の図３５の処理において、Ｓ５４１の処理をスキップすることで実現できる。
【０１５７】
［ランクの決定］
また、決定した、Ｒｆ、および、Ｒｌに対して、ランクＲｍの識別子の発生頻度が、要求処理サーバ装置単体で処理可能な識別子の発生頻度ｆｉと比較して十分小さくなるように、ランクＲｍを定め、決定したＲｌが、Ｒｍよりも小さい場合、Ｒｌの値をＲｍの値で置き換え、Ｒｆの値を、（１／Ｎｓ１／ｐ）Ｒｍで置き換えてもよい。このＲｆ、および、Ｒｌの置き換えにより、Ｒｌの値が小さくなりすぎ、サーバ負荷に偏りを発生させることを防止することができる。
【０１５８】
また、決定した、Ｒｆ、および、Ｒｌに対して、ランクＲｍの識別子の発生頻度が、要求処理サーバ装置単体で処理可能な識別子の発生頻度と比較して十分小さくなるように、ランクＲｍを定め、決定したＲｌが、Ｒｍよりも小さい場合、Ｒｌの値をＲｍの値での値で置き換え、Ｒｆの値を、１で置き換えてもよい。このＲｆ、および、Ｒｌの置き換えにより、Ｒｌの値が小さくなりすぎ、サーバ負荷に偏りを発生させることを防止することができる。
【０１５９】
［システム構成等］
また、図示した各装置の各構成要素は機能概念的なものであり、必ずしも物理的に図示の如く構成されていることを要しない。すなわち、各装置の分散・統合の具体的形態は図示のものに限られず、その全部または一部を、各種の負荷や使用状況などに応じて、任意の単位で機能的または物理的に分散・統合して構成することができる。さらに、各装置にて行なわれる各処理機能は、その全部または任意の一部が、ＣＰＵおよび当該ＣＰＵにて解析実行されるプログラムにて実現され、あるいは、ワイヤードロジックによるハードウェアとして実現され得る。
【０１６０】
また、本実施例において説明した各処理のうち、自動的におこなわれるものとして説明した処理の全部または一部を手動的に行うこともでき、あるいは、手動的におこなわれるものとして説明した処理の全部または一部を公知の方法で自動的におこなうこともできる。この他、上記文書中や図面中で示した処理手順、制御手順、具体的名称、各種のデータやパラメータを含む情報については、特記する場合を除いて任意に変更することができる。
【０１６１】
［プログラム］
また、上記実施形態において説明したデータ管理装置２００が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。例えば、第一の実施形態に係るデータ管理装置２００が実行する処理をコンピュータが実行可能な言語で記述したサーバ制御プログラムを作成することもできる。この場合、コンピュータがサーバ制御プログラムを実行することにより、上記実施形態と同様の効果を得ることができる。さらに、かかるサーバ制御プログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されサーバ制御プログラムをコンピュータに読み込ませて実行することにより上記第一の実施形態と同様の処理を実現してもよい。以下に、図２に示したデータ管理装置２００と同様の機能を実現するサーバ制御プログラムを実行するコンピュータの一例を説明する。
【０１６２】
図４０は、サーバ制御プログラムを実行するコンピュータ１０００を示す図である。図４０に例示するように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有し、これらの各部はバス１０８０によって接続される。
【０１６３】
メモリ１０１０は、図４０に例示するように、ＲＯＭ（Read  Only  Memory）１０１１及びＲＡＭ１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、図４０に例示するように、ハードディスクドライブ１０３１に接続される。ディスクドライブインタフェース１０４０は、図４０に例示するように、ディスクドライブ１０４１に接続される。例えば磁気ディスクや光ディスク等の着脱可能な記憶媒体が、ディスクドライブ１０４１に挿入される。シリアルポートインタフェース１０５０は、図４０に例示するように、例えばマウス１０５１、キーボード１０５２に接続される。ビデオアダプタ１０６０は、図４０に例示するように、例えばディスプレイ１０６１に接続される。
【０１６４】
ここで、図４０に例示するように、ハードディスクドライブ１０３１は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３、プログラムデータ１０９４を記憶する。すなわち、上記のサーバ制御プログラムは、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、例えばハードディスクドライブ１０３１に記憶される。
【０１６５】
また、上記実施形態で説明した各種データは、プログラムデータとして、例えばメモリ１０１０やハードディスクドライブ１０３１に記憶される。そして、ＣＰＵ１０２０が、メモリ１０１０やハードディスクドライブ１０３１に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出し、各種処理手順を実行する。
【０１６６】
なお、サーバ制御プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０３１に記憶される場合に限られず、例えば着脱可能な記憶媒体に記憶され、ディスクドライブ等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、サーバ制御プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ネットワーク（ＬＡＮ（Local  Area  Network）、ＷＡＮ（Wide  Area  Network）等）を介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【０１６７】
１００、１００Ａ〜１００Ｄ  要求処理サーバ装置
１０１  通信制御Ｉ／Ｆ部
１０２  制御部
１０３  記憶部
２００  データ管理装置
２０１  通信制御Ｉ／Ｆ部
２０２  制御部
２０３  記憶部
３００  負荷分散転送装置
３０１  通信制御Ｉ／Ｆ部
３０２  制御部
３０３  記憶部
４００Ａ〜４００Ｃ  クライアント
【図１】
2014164357.tif 000018
【図２】
2014164357.tif 000019
【図３】
2014164357.tif 000020
【図４】
2014164357.tif 000021
【図５】
2014164357.tif 000022
【図６】
2014164357.tif 000023
【図７】
2014164357.tif 000024
【図８】
2014164357.tif 000025
【図９】
2014164357.tif 000026
【図１０】
2014164357.tif 000027
【図１１】
2014164357.tif 000028
【図１２】
2014164357.tif 000029
【図１３】
2014164357.tif 000030
【図１４】
2014164357.tif 000031
【図１５】
2014164357.tif 000032
【図１６】
2014164357.tif 000033
【図１７】
2014164357.tif 000034
【図１８】
2014164357.tif 000035
【図１９】
2014164357.tif 000036
【図２０】
2014164357.tif 000037
【図２１】
2014164357.tif 000038
【図２２】
2014164357.tif 000039
【図２３】
2014164357.tif 000040
【図２４】
2014164357.tif 000041
【図２５】
2014164357.tif 000042
【図２６】
2014164357.tif 000043
【図２７】
2014164357.tif 000044
【図２８】
2014164357.tif 000045
【図２９】
2014164357.tif 000046
【図３０】
2014164357.tif 000047
【図３１】
2014164357.tif 000048
【図３２】
2014164357.tif 000049
【図３３】
2014164357.tif 000050
【図３４】
2014164357.tif 000051
【図３５】
2014164357.tif 000052
【図３６】
2014164357.tif 000053
【図３７】
2014164357.tif 000054
【図３８】
2014164357.tif 000055
【図３９】
2014164357.tif 000056
【図４０】
2014164357.tif 000057
【図４１】
2014164357.tif 000058
【図４２】
2014164357.tif 000059
【図４３】
2014164357.tif 000060
【図４４】
2014164357.tif 000061
【図４５】
2014164357.tif 000062