(57)【要約】【課題】サーバ増減に伴う負荷増大を抑制し、サーバ間の負荷の偏りがない負荷分散システムを提供する。【解決手段】スロット群生成装置は、複数のサーバ間で負荷分散を行う負荷分散システムにおいて、システムを最大構成とした場合の最大スロット列を生成する。そして、スロット群生成装置は、この最大スロット列をベースに、負荷分散システムからサーバを減設した場合のスロット列を生成する。このときスロット群生成装置は、まず最大スロット列をコピーして連結した延長スロット列を生成する。そして、スロット群生成装置は、この延長スロット列の中から減設対象のサーバの登場部分を別サーバに置換したスロット列を生成する。ここでの置換は、減設対象外のサーバの基本順列それぞれの登場回数ができるだけ同じになるような置換とする。そして、スロット群生成装置は、置換後のスロット列を用いてスロット群を生成する。【選択図】図１４
2015184744.tif 000002
【特許請求の範囲】
【請求項１】
複数のサーバ間で負荷分散を行う負荷分散システムにおいて、受信パケットの振り分けに用いるスロット群を生成するスロット群生成装置であって、
前記負荷分散システムを構成するサーバ数を最大とした場合の最大のサーバ群それぞれについて、所定数のサーバの順列組合せの登場回数が同じとなるようサーバを配列したスロット列を生成する最大スロット列生成部と、
前記生成されたスロット列を１以上複製して連結させた延長スロット列を生成する延長スロット列生成部と、
前記負荷分散システムに要求されるサーバの数が、前記最大のサーバ群のサーバの数よりも少ないとき、前記生成した延長スロット列における、前記最大のサーバ群からの減設対象となるサーバの登場部分それぞれを、前記減設対象外のサーバの基本順列それぞれの登場回数ができるだけ同じになるように前記減設対象外のサーバに置換したスロット列を生成するサーバ置換部と、
所定のハッシュ空間を、前記生成されたスロット列の長さのスロットに分割し、前記分割したスロットそれぞれに、前記スロット列に示される順で前記サーバを割り当てたスロット群を生成するスロット割り当て部とを備えることを特徴とするスロット群生成装置。
【請求項２】
前記スロット群生成装置は、さらに、
前記延長スロット列および前記サーバ置換部による置換の過程で生成されたスロット列を保管する保管部を備え、
前記スロット割り当て部は、
前記負荷分散システムに要求されるサーバの数に対応するスロット列が前記保管部にあるとき、前記保管部から前記負荷分散システムに要求されるサーバの数に対応するスロット列を取得し、前記スロット群を生成することを特徴とする請求項１に記載のスロット群生成装置。
【請求項３】
前記サーバ置換部は、
前記負荷分散システムに要求されるサーバの数に対応するスロット列が前記保管部になく、かつ、前記負荷分散システムに要求されるサーバの数が、前記最大のサーバ群のサーバの数よりも少ないとき、前記保管部から現在の前記負荷分散システムのサーバ群に対応するスロット列を取得し、前記取得したスロット列における、現在の前記負荷分散システムのサーバ群からの減設対象となるサーバの登場部分それぞれを、前記減設対象外のサーバの基本順列それぞれの登場回数ができるだけ同じになるように前記減設対象外のサーバに置換したスロット列を生成することを特徴とする請求項２に記載のスロット群生成装置。
【請求項４】
前記最大スロット列生成部は、
前記負荷分散システムを構成するサーバ数を最大とした場合の最大のサーバ群の中から、所定数のサーバの順列組合せである基本順列を生成するスロット順列組み合わせ生成部と、
前記生成した基本順列をノードとして接続した順列接続グラフを生成する接続グラフ生成部と、
前記生成した順列接続グラフから、各ノードの通過回数が全ノード間で同じになる順列閉路を抽出する順列閉路抽出部と、
前記抽出した順列閉路を構成するノードそれぞれの先頭のサーバを閉路の順に並べて前記最大のサーバ群のスロット列を生成するスロット列生成部とを備えることを特徴とする請求項１〜３のいずれか１項に記載のスロット群生成装置。
【請求項５】
前記所定数は、前記負荷分散システムにおいて想定する故障サーバの台数に１を加算した値であることを特徴とする請求項１〜４のいずれか１項に記載のスロット群生成装置。
【請求項６】
前記スロット群生成装置は、
前記スロット列生成部がスロット列の対象外としたサーバを、前記スロット列に組み込むとき、前記スロット列に示されるサーバについて、前記所定数から１を減じた数のサーバの順列組合せである拡張基礎順列を生成する拡張基礎順列生成部と、
前記スロット列の対象外としたサーバを、前記拡張基礎順列で挟んだ順列を生成し、前記生成した順列で、前記スロット列における当該拡張基礎順列の箇所を置換したスロット列を生成する拡張スロット列生成部とをさらに備えることを特徴とする請求項１〜５のいずれか１項に記載のスロット群生成装置。
【請求項７】
複数のサーバ間で負荷分散を行う負荷分散システムにおいて、受信パケットの振り分けに用いるスロット群を生成するスロット群生成装置が、
前記負荷分散システムを構成するサーバ数を最大とした場合の最大のサーバ群それぞれについて、所定数のサーバの順列組合せの登場回数が同じとなるようサーバを配列したスロット列を生成するステップと、
前記生成されたスロット列を１以上複製して連結させた延長スロット列を生成するステップと、
前記負荷分散システムに要求されるサーバの数が、前記最大のサーバ群のサーバの数よりも少ないとき、前記生成した延長スロット列における、前記最大のサーバ群からの減設対象となるサーバの登場部分それぞれを、前記減設対象外のサーバの基本順列それぞれの登場回数ができるだけ同じになるように前記減設対象外のサーバに置換したスロット列を生成するステップと、
所定のハッシュ空間を、前記生成されたスロット列の長さのスロットに分割し、前記分割したスロットそれぞれに、前記スロット列に示される順で前記サーバを割り当てたスロット群を生成するステップとを実行することを特徴とするスロット群生成方法。
【請求項８】
複数のサーバ間で負荷分散を行う負荷分散システムにおいて、受信パケットの振り分けに用いるスロット群を生成するスロット群生成装置と、前記生成されたスロット群を用いて、前記受信パケットの振り分けを行う振分装置とを備える負荷分散システムであって、
前記スロット群生成装置は、
前記負荷分散システムを構成するサーバ数を最大とした場合の最大のサーバ群それぞれについて、所定数のサーバの順列組合せの登場回数が同じとなるようサーバを配列したスロット列を生成する最大スロット列生成部と、
前記生成されたスロット列を１以上複製して連結させた延長スロット列を生成する延長スロット列生成部と、
前記負荷分散システムに要求されるサーバの数が、前記最大のサーバ群のサーバの数よりも少ないとき、前記生成した延長スロット列における、前記最大のサーバ群からの減設対象となるサーバの登場部分それぞれを、前記減設対象外のサーバの基本順列それぞれの登場回数ができるだけ同じになるように前記減設対象外のサーバに置換したスロット列を生成するサーバ置換部と、
所定のハッシュ空間を、前記生成されたスロット列の長さのスロットに分割し、前記分割したスロットそれぞれに、前記スロット列に示される順で前記サーバを割り当てたスロット群を生成するスロット割り当て部とを備えることを特徴とする負荷分散システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スロット群生成装置、スロット群生成方法、および、負荷分散システムに関する。
【背景技術】
【０００２】
ネットワーク越しにサービス要求を受け付けるシステムでは、膨大なサービス要求にも応答し、かつサービス要求量に応じて割り当てるハードウェア量を柔軟に変更する必要があるため、複数のサーバやＤＢ（データベース）サーバを並列動作させる分散システムでの実現が主流となっている。
【０００３】
分散システムの実現には、サービス要求やＤＢ操作を適切にいずれかのサーバへ振り分け、サーバ負荷や保管データ量をサーバ間で均一化する負荷分散装置が必要となる。多くのＷｅｂサービスにおいては個々のサービス要求は独立に処理することが可能なため、サービス要求を順番にまたはランダムになど、サービス要求やＤＢ操作の内容と無関係に振り分ける負荷分散装置が用いられている。しかし、ＳＩＰ（Session  Initiation  Protocol）アプリケーションや分散ハッシュテーブルをはじめとする、複数のサービス要求間で同じ情報を共有する必要があるステートフルなＷｅｂサービスにおいては、それら関係があるサービス要求やＤＢ操作を同一サーバに振り分ける負荷分散装置を実現する必要がある。また、分散ハッシュテーブル等においては、サーバの増減に伴って負荷分散装置からの振り分け先が変化すると保管データの移動等が必要となるが、この移動はネットワーク帯域や記憶領域へ大きな負荷を発生させることから、振り分け先の変化は極力低減することが求められる。
【０００４】
この必要性に関して、非特許文献１では、キーのハッシュ値に応じてデータの格納サーバを決定するコンシステント・ハッシュ法を負荷分散装置に応用し、サービス要求内に同一のキーがある限り同じサーバに振り分ける手法、特にハッシュ値と振り分け先サーバの対応付けを定義するスロット群のスロット数を抑制しながら負荷を均一に分散する手法が記されている。
【０００５】
また、非特許文献２にはスロット数を増加させることで、コンシステント・ハッシュ法の負荷の偏りを低減させる手法が記されている。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】入江道生他、“コンシステント・ハッシュ法におけるデータの複製を意識した負荷分散手法”、社団法人電子情報通信学会、信学技報IN2010-77、2010年10月
【非特許文献２】I.Stoica他、“Chord:  A  Scalable  Peer-to-peer  Lookup  Service  for  Internet  Applications”、Proc.  ACM  SIGCOMM  2001、Aug.  2001.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
非特許文献１の手法では、スロット群の数やサーバ増減に伴う負荷増大を抑制できる一方で負荷の均一化は完全ではなく、サーバ間で大きな負荷の偏りが生じる可能性がある。また、非特許文献２の手法でも、サーバ増減に伴う負荷増大を抑制しつつ、スロット数の増加によって負荷の偏りが低減することは示されているが、どの程度のスロット数で所望の均一化が図れるかは定かではない。
【０００８】
実際にシステムを構築する場合、負荷の均一化が十分になされず、かつどのサーバの負荷が高くなるかも分からない状況では、サーバ等のハードウェアの調達時に十分な性能を持った機器を選定せざるを得ない。その結果、システム構築のための調達コストを押し上げる結果となってしまう。したがって、システム構築において、システム内のサーバ間の負荷の均一化は非常に重要な課題である。
【０００９】
そこで、本発明は、サーバ増減に伴う負荷増大を抑制しつつ、サーバ間の負荷の偏りがない負荷分散システムを提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本発明は、複数のサーバ間で負荷分散を行う負荷分散システムにおいて、受信パケットの振り分けに用いるスロット群を生成するスロット群生成装置であって、前記負荷分散システムを構成するサーバ数を最大とした場合の最大のサーバ群それぞれについて、所定数のサーバの順列組合せの登場回数が同じとなるようサーバを配列したスロット列を生成する最大スロット列生成部と、前記生成されたスロット列を１以上複製して連結させた延長スロット列を生成する延長スロット列生成部と、前記負荷分散システムに要求されるサーバの数が、前記最大のサーバ群のサーバの数よりも少ないとき、前記生成した延長スロット列における、前記最大のサーバ群からの減設対象となるサーバの登場部分それぞれを、前記減設対象外のサーバの基本順列それぞれの登場回数ができるだけ同じになるように前記減設対象外のサーバに置換したスロット列を生成するサーバ置換部と、所定のハッシュ空間を、前記生成されたスロット列の長さのスロットに分割し、前記分割したスロットそれぞれに、前記スロット列に示される順で前記サーバを割り当てたスロット群を生成するスロット割り当て部とを備えることを特徴とする。
【発明の効果】
【００１１】
本発明によれば、サーバ増減に伴う負荷増大を抑制しつつ、サーバ間の負荷の偏りがない負荷分散システムを提供することができる。
【図面の簡単な説明】
【００１２】
【図１】図１は、各実施形態の負荷分散システムを示す構成図である。
【図２】図２は、スロット群生成部を示す構成図である。
【図３】図３は、スロット群生成部を示す構成図である。
【図４】図４は、第１の実施形態のスロット群生成部の処理手順を示すフローチャートである。
【図５】図５は、図４の基本スロット列生成処理を示すフローチャートである。
【図６】図６は、基本順列の生成例を示す図である。
【図７】図７は、基本順列接続グラフの生成例を示す図である。
【図８】図８は、基本順列閉路の生成例を示す図である。
【図９】図９は、スロット列の生成例を示す図である。
【図１０】図１０は、ハッシュ空間にサーバＡ〜Ｂの担当区分を割り当てたスロット群の生成例を示す図である。
【図１１】図１１は、スロット群生成部の処理手順を示すフローチャートである。
【図１２】図１２は、スロット群生成部の処理手順を示すフローチャートである。
【図１３】図１３は、延長スロット列の生成例を示す図である。
【図１４】図１４は、サーバ数が３、４、５の場合のスロット列の一例を示す図である。
【図１５】図１５は、ハッシュ空間にサーバＡ〜Ｅの担当区分を割り当てたスロット群の生成例を示す図である。
【図１６】図１６は、第２の実施形態の最大スロット列生成部の処理手順を示すフローチャートである。
【図１７】図１７は、拡張情報の生成例を示す図である。
【図１８】図１８は、図１６のスロット列拡張処理を示すフローチャートである。
【図１９】図１９は、拡張基礎順列の生成例を示す図である。
【図２０】図２０は、拡張後のスロット列の生成例を示す図である。
【図２１】図２１は、拡張情報の更新例を示す図である。
【図２２】図２２は、負荷分散システムの他の構成例を示す図である。
【図２３】図２３は、負荷分散プログラムを実行するコンピュータを示す図である。
【発明を実施するための形態】
【００１３】
以下、本発明の実施形態について、第１の実施形態および第２の実施形態に分けて説明する。なお、各実施形態により本発明が限定されるものではない。
【００１４】
（第１の実施形態）
各実施形態の負荷分散システム（システム）は、図１に示すように、クライアント１００と、負荷分散装置２００と、サーバ３００とがネットワーク（図示省略）で接続されて構成される。
【００１５】
負荷分散装置２００は、クライアント１００からのサービス要求パケットを受信するパケット受信部２１０と、受信したパケットから所定のキーを抽出し、そのハッシュ値とスロット群との比較からパケットの転送先のサーバ３００を決定する振分部２２０と、振分部２２０の決定に基づきパケットの転送を実施するパケット転送部２３０と、負荷の均一化を実現するスロット群を生成するスロット群管理部２４０と、スロット群管理部２４０を多くの負荷分散装置で流用できるようにサーバ名称等の抽象化を制御するスロット群汎用化部２５０とを備える。
【００１６】
振分部２２０は、パケット受信部２１０が受信したパケットから、コンシステント・ハッシュ法でキーとする情報を抽出するキー抽出部２２１と、抽出したキーからハッシュ値を生成し、スロット群汎用化部２５０から取得されるスロット群の中からそのハッシュ値に対応するスロットを検索し、そのスロットに割り当てられたサーバをパケットの転送先として決定するパケット送信先決定部２２２とを備える。
【００１７】
スロット群管理部２４０は、システムの最大構成とした場合のサーバ３００のリスト（最大のサーバ群のリスト）や、稼働させたいサーバ３００のリスト（要求されるサーバ３００のリスト）、サーバ３００が何台故障した場合まで負荷を均一化するかを示す耐障害度等の各種パラメータを受信し、これらのパラメータに基づき、各種スロット群の生成、保管等を行う。このスロット群管理部２４０はと、スロット群生成部２４１と、スロット保管部２４２と、最大スロット列生成部２４３を備える。
【００１８】
スロット群生成部２４１は、サーバ群抽象化部２５１から出力されたパラメータに基づきスロット群の生成を行う。具体的には、スロット群生成部２４１は、サーバ群抽象化部２５１からパラメータとして、分散処理システムを構成するサーバリスト（例えば、Ａ、Ｂ、Ｃ、Ｄ、Ｅ）、基本順列長（例えば、２）、最大のサーバ群のリスト（例えば、Ａ、Ｂ、Ｃ、Ｄ、Ｅ）、現在必要なサーバ数（例えば、４）等の情報の入力を受け付けると、最大スロット列生成部２４３に最大のサーバ群（例えば、Ａ、Ｂ、Ｃ、Ｄ、Ｅ）と、基本順列長（例えば、２）とを送信する。そして、スロット群生成部２４１は、最大スロット列生成部２４３より計算結果として最大サーバ数でのスロット群を生成するために必要な、スロットの割り当て順序を規定するスロット列を受け取る。そして、スロット群生成部２４１は、受け取ったスロット列に基づきスロット群を生成する。ここで、スロット群生成部２４１は、最大サーバ数や運用中のサーバ数と、要望されたサーバ数とを比較し、要望されたサーバ数が、最大サーバ数や運用中のサーバ数よりも少ないとき、つまり、負荷分散システム内のサーバ数の減設が必要なとき、現在運用中のサーバ群に関するスロット列から、減設の対象のサーバ３００を減設したスロット列（減設スロット列）を生成する。そして、その減設スロット列をもとにスロット群を生成し、スロット保管部２４２へ出力する。このスロット群生成部２４１の詳細は後記する。
【００１９】
最大スロット列生成部２４３は、最大構成のサーバ群（例えば、Ａ、Ｂ、Ｃ、Ｄ、Ｅ）と、基本順列長（例えば、２）とに基づき、この最大のサーバ群のスロット列を生成する。この最大スロット列生成部２４３の詳細についても後記する。
【００２０】
スロット保管部２４２は、スロット群生成部２４１から出力されたスロット群やスロット列を保持する。具体的には、スロット保管部２４２は、最大構成のサーバ群から、稼働させるサーバ３００までサーバ３００の数を減少させる場合にその過程で生成されるスロット列やスロット群を保管する。
【００２１】
スロット群汎用化部２５０は、システム保守者４００等から事前に設定された、負荷分散システムのサーバリストをもとに、各サーバ３００に汎用的なサーバ名を割り当て、スロット群管理部２４０へスロット群の生成を要求するサーバ群抽象化部２５１と、スロット群管理部２４０が生成したスロット群において、各スロットに割り当てられたサーバ名称を汎用的な名称からシステム固有の名称に変換するサーバ群個別化部２５２と、サーバリストの汎用化に係る対応表を保持するサーバリスト保持テーブル２５３とで構成される。また、図１の負荷分散装置２００は、図１に例示する台数に限定されず、サーバ３００の集合に対し、任意の台数としてもよい。
【００２２】
以下の説明では、負荷分散装置２００の適用サービスが、分散ハッシュテーブルを用いたサービスである場合を例に説明するが、適用サービスはこれに限られるものではない。
【００２３】
クライアント１００は、例えば、ＤＢクライアントであり、ＰＵＴやＧＥＴ等のＤＢ操作に係る要求パケットを送出する装置である。
【００２４】
この場合、負荷分散装置２００とサーバ３００の集合は一体のシステムとしてデータベースであるように振る舞い、クライアント１００からのＤＢ操作パケットは専ら負荷分散装置２００が受信・振り分けし、ＤＢ操作そのものはサーバ３００が実施する。これにより、クライアント１００はサーバ３００の増設等を意識することなく、負荷分散装置２００と対向すればよい。ただし、キーが同一のデータに関する更新や参照処理は同一のサーバ３００が一貫して実施する必要があるため、負荷分散装置２００の振り分けロジックは、同一キーのデータを同一サーバ３００に振り分けるものである必要がある。この点について、負荷分散装置２００は以下で説明するコンシステント・ハッシュ法を用いる。
【００２５】
コンシステント・ハッシュ法において、クライアント１００からのＤＢ操作パケットを受信した負荷分散装置２００のパケット受信部２１０は、受信したＤＢ操作パケットを振分部２２０のキー抽出部２２１に受け渡す。キー抽出部２２１では、操作対象データを識別するため、ＤＢ操作パケットからキーを抽出し、パケット送信先決定部２２２に送る。キーを受信したパケット送信先決定部２２２では、キーのハッシュ値を生成し、スロット群汎用化部２５０から取得した、各サーバ３００が担当するハッシュ値の範囲を記したスロット群にキーのハッシュ値を照らし合わせることで、受信パケットの転送先とするサーバ３００を決定する。このように振り分け先を決定することで、操作対象データのキーが同一である限りにおいて同一のサーバ３００にパケットを転送することができる。
【００２６】
パケットの転送先の決定の後は、パケット転送部２３０がその情報をもとにパケットの送信先ＩＰアドレス等を書き換え、該当するサーバ３００へパケットを転送する。
【００２７】
負荷分散装置２００が上記の処理によってパケットを振り分けた場合に、サーバ３００間での負荷の均一化をはかるためには、各サーバ３００が担当するハッシュ値の範囲が均一化されたスロット群を生成する必要がある。以下では、いくつかのサーバ３００が故障した場合を含め、各サーバ３００が担当するハッシュ値の範囲が均一化されたスロット群を生成する方法について説明する。
【００２８】
今回の例では、負荷分散システムを構成するサーバ３００が最大５台（最大サーバ数が５台）であり、それぞれサーバ名称が、DBserver1、DBserver2、DBserver3、DBserver4、DBserver5であるものとする。例えば、運用開始当初はDBserver1、DBserver2、DBserver3、DBserver4の４台のサーバ３００で運用されるが、その後、DBserver1、DBserver2、DBserver3の３台に減設されたり、５台に増設されたりする等、負荷分散システムにおいて運用（稼働）されるサーバ数は、最大サーバ数以下で増減が発生することを想定している。また、負荷分散システムにおけるサーバ３００の故障時の対応については、サーバ３００のうちランダムに１台が故障した場合であっても残るサーバ３００で負荷を均一化する。
【００２９】
スロット群汎用化部２５０は、スロット群管理部２４０が個別のサーバ名DBserver1等を意識することなくスロット群を生成することができるよう、名称の変換を担う。
【００３０】
具体的には、サーバリスト保持テーブル２５３には、システム保守者４００が事前にDBserver1等システム固有のサーバ名称と、ＡやＢといったスロット群管理部２４０が用いるサーバ名称の対応付け、例えば、DBserver1:Ａ、DBserver2:Ｂ、DBserver3:Ｃ、DBserver4:Ｄ、DBserver5:Ｅを保持させる。この状況でサーバ群抽象化部２５１がシステム保守者４００から、最大サーバ数を５台とする中で１台故障まで耐性のあるスロット群を生成するよう要求を受けた場合、サーバ群抽象化部２５１では、サーバリスト保持テーブル２５３の情報をもとに最大でＡ、Ｂ、Ｃ、Ｄ、Ｅに関するスロット群が必要となることとともに、現在はＡ、Ｂ、Ｃ、Ｄに関するスロット群が必要であると、スロット群管理部２４０のスロット群生成部２４１に要求する。この際には、例えば、「故障耐性を求められる台数（想定する故障サーバの台数）＋１」、すなわちここでは「１＋１＝２」を、スロット群生成に係るパラメータとして送信する（以下、本パラメータを基本順列長と呼ぶ）。なお、この「１」を加える処理については、必ずしもサーバ群抽象化部２５１で行う必要はなく、スロット群生成部２４１で行ってもよい。
【００３１】
今回の場合、例えば、サーバ群抽象化部２５１から、パラメータとして、サーバリスト「Ａ、Ｂ、Ｃ、Ｄ、Ｅ」、基本順列長「２」、最大でＡ、Ｂ、Ｃ、Ｄ、Ｅに関するスロット群が必要となり、現在はＡ、Ｂ、Ｃ、Ｄに関するスロット群が必要であるという情報がスロット群生成部２４１に送信されると、スロット群管理部２４０からは、例えば、後述するようなＡ、Ｂ等で構成されたスロット群が返送される。つまり、環状のハッシュ空間に対し、各サーバの担当範囲を割り当てたスロット群が返送される。そして、サーバ群個別化部２５２が、返送されたスロット群に対し、サーバリスト保持テーブル２５３の情報をもとに、Ａ、Ｂ等の汎用的な名称からDBserver1等の個別の名称に変換することで、DBserver1等の個別の名称に対応したスロット群が生成される。以降、サーバ台数が増減する際にも、スロット群汎用化部２５０は同様に動作する。
【００３２】
なお、このスロット群は、負荷分散システムのいずれかのサーバ３００が故障したとき、この故障サーバの処理を引き継ぐサーバ３００を選択するときにも用いられる。例えば、振分部２２０が受信パケットの振り分け先としてDBserver1を選択した後、このDBserver1が故障したとき、処理の引き継ぎ先のサーバ３００として、当該スロット群において故障サーバ（DBserver1（Ａ））の右隣り（時計回りの向きで隣り）に配置されるサーバ（例えば、DBserver5（Ｅ））を選択する。
【００３３】
（スロット群生成部）
次に、図２を用いて、スロット群生成部２４１を詳細に説明する。スロット群生成部２４１は、パラメータ受信部２４１１と、最大スロット列生成依頼部２４１２と、判定部２４１３と、スロット列延長部２４１４と、処理対象集合抽出部２４１５と、スロット列保管処理部２４１６と、サーバ選定部２４１７と、サーバ置換部２４１８と、スロット割り当て部２４１９とを備える。
【００３４】
パラメータ受信部２４１１は、サーバ群抽象化部２５１からスロット群生成に関するパラメータを受信する。例えば、パラメータ受信部２４１１は、サーバ群抽象化部２５１からパラメータとして、分散処理システムを構成するサーバリスト（例えば、Ａ、Ｂ、Ｃ、Ｄ、Ｅ）、基本順列長（例えば、２）、最大のサーバ群のリスト（例えば、Ａ、Ｂ、Ｃ、Ｄ、Ｅ）、現在必要なサーバ数（例えば、４）等の情報を受信する。
【００３５】
最大スロット列生成依頼部２４１２は、最大スロット列生成部２４３に対しこの最大のサーバ群のスロット列（最大スロット列）の生成の依頼を行う。具体的には、最大スロット列生成依頼部２４１２は、スロット群生成に関するパラメータに示される、最大のサーバ群のリスト（例えば、Ａ、Ｂ、Ｃ、Ｄ、Ｅ）と、基本順列長（例えば、２）とを最大スロット列生成部２４３へ送信し、そして、最大スロット列生成部２４３から計算結果として最大スロット列を受け取る。受け取った最大スロット列はスロット列延長部２４１４へ出力する。
【００３６】
判定部２４１３は、負荷分散システムにサーバ増減設が必要か否か、また必要な場合、増設が必要か、減設が必要かを判定する。具体的には、判定部２４１３は、まず、スロット群生成に関するパラメータに示される、現在必要なサーバ数（システム保守者４００等から要求されたサーバの数）および負荷分散システムの最大サーバ数を参照して、現在必要なサーバ数が、最大サーバ数よりも少なければ減設が必要と判定し、最大サーバ数と同じであれば減設は必要ないと判定する。また、判定部２４１３は、負荷分散システムの運用開始後、要求されたサーバ数と、現在運用中のサーバ数とを比較し、要求されたサーバ数が現在運用中のサーバ数よりも少ないときは減設が必要と判定し、要求されたサーバ数が現在運用中のサーバ数よりも多いときは増設が必要と判定する。
【００３７】
スロット列延長部２４１４は、最大スロット列を１回以上繰り返した延長スロット列（後記する図１３参照）を生成する。
【００３８】
スロット列保管処理部２４１６は、スロット列延長部２４１４により生成された延長スロット列やサーバ置換部２４１８により生成されたスロット列をスロット保管部２４２へ出力する。
【００３９】
処理対象集合抽出部２４１５は、最大のサーバ群と現在必要なサーバ群との差分のサーバ群を減設対象となるサーバ群として抽出する。
【００４０】
サーバ選定部２４１７は、減設対象となるサーバ群からサーバ置換部２４１８による置換処理の対象のサーバ３００を選定する。
【００４１】
サーバ置換部２４１８は、スロット列延長部２４１４により生成された延長スロット列またはスロット保管部２４２に保管されるスロット列において、サーバ選定部２４１７により選択されたサーバ３００が登場する箇所を、別のサーバ３００に置き換える（置換処理を行う）。例えば、判定部２４１３により、負荷分散システムの最大のサーバ群からサーバ減設が必要と判定された場合、サーバ置換部２４１８は、延長スロット列における置換処理の対象のサーバ３００の登場部分を、当該延長スロット列に登場する他のサーバ３００に置換する。このサーバ置換部２４１８の詳細は具体例を交えながら後記する。
【００４２】
スロット割り当て部２４１９は、スロット列をもとにスロット群を生成する。例えば、スロット割り当て部２４１９は、サーバ置換部２４１８により生成されたスロット列またスロット列延長部２４１４により生成された延長スロット列をもとに、受信パケットの振り分けに用いるハッシュ空間を、当該スロット列の長さのスロットに分割する。そして、スロット割り当て部２４１９は、この分割したスロットそれぞれに、スロット列に示される順でサーバ３００を割り当てたスロット群を生成する（図１５参照）。生成したスロット群は、スロット保管部２４２へ出力する。なお、システム保守者４００等により要求されたサーバ数に対応するスロット列が、スロット保管部２４２に既に保管されている場合、スロット割り当て部２４１９は、スロット保管部２４２に保管されるスロット列を用いてスロット群を生成する。
【００４３】
（最大スロット列生成部）
最大スロット列生成部２４３を詳細に説明する。最大スロット列生成部２４３は、図３に示すように、スロット列順列組合せ生成部２４３１と、接続グラフ生成部２４４と、順列閉路抽出部２４５と、スロット列生成部２４６とを備える。拡張基礎順列生成部２４８と、拡張スロット列生成部２４９とは、最大スロット列生成部２４３が装備する場合と装備しない場合とがあり、装備する場合については第２の実施形態で述べる。なお、各部の処理の詳細は、具体例を交えながら後記する。
【００４４】
スロット列順列組合せ生成部２４３１は、負荷分散システムの最大のサーバ群から、（想定する故障サーバの台数＋１）の台数のサーバの順列組合せを生成する。
【００４５】
接続グラフ生成部２４４は、スロット列順列組合せ生成部２４３１により生成された順列組合せ同士をノードとして接続した順列接続グラフを生成する。
【００４６】
順列閉路抽出部２４５は、接続グラフ生成部２４４により生成された順列接続グラフから、各ノードを同じ回数通る順列閉路を抽出する。
【００４７】
スロット列生成部２４６は、順列閉路抽出部２４５により抽出された順列閉路を構成するノードそれぞれの先頭のサーバを閉路の順に並べてスロット列（基本スロット列）を生成する。
【００４８】
（処理手順）
次に、負荷分散装置２００のスロット群管理部２４０の処理手順について説明する。
【００４９】
（最大スロット列生成部の処理手順）
まず、スロット群管理部２４０の最大スロット列生成部２４３の処理手順を説明する。最大スロット列生成部２４３は、図４に示すように、スロット群生成の対象となるサーバを示したサーバリストを取得し（Ｓ１０）、サーバリストに示されるサーバの基本スロット列を生成する（Ｓ２０）。
【００５０】
例えば、最大のサーバ群がＡ、Ｂ、Ｃであり、最大スロット列生成部２４３が基本スロット列生成処理により、ＡＢＣＢＡＣというスロット列を生成した場合を考える。この場合、スロット群生成部２４１は、このＡＢＣＢＡＣというスロット列に基づきスロット群を生成する。例えば、スロット群生成部２４１は、後記する図１０に示すように、ハッシュ空間を６等分（スロット列の長さで等分）し、スロット列と同じ順番でスロットにサーバを割り当てる。つまり、スロット群生成部２４１は、Ａ→Ｂ→Ｃ→Ｂ→Ａ→Ｃ（→Ａに戻る）というスロット群を生成する。このように、スロット群生成部２４１が最大のサーバ群の各サーバの登場回数が同じで、かつ各サーバの次に他のサーバが登場する回数が均一になるようなスロット群を生成し、振分部２２０が当該スロット群により受信パケットの振り分けを行うことで、各サーバ間で負荷を均一化し、かつ、故障時の負荷についても均一化することができる。
【００５１】
図４の基本スロット列生成処理（Ｓ２０）は、図５に示す手順により行われる。まず、最大スロット列生成部２４３のスロット列順列組合せ生成部２４３１は、図４のＳ１０で取得されたサーバリストに基づき基本順列を生成する（Ｓ２１）。具体的には、スロット列順列組合せ生成部２４３１は、サーバリストに示されるサーバ群について、（想定する故障サーバの台数＋１）、すなわち基本順列長の台数のサーバの順列組合せをすべて抽出する。
【００５２】
例えば、想定する故障サーバの台数を「１」とし、サーバリストにＡ、Ｂ、Ｃが記載されていた場合を考える。この場合、スロット列生成部２４３は、図６に示すように、３つのサーバについて「２（基本順列長）」の長さの全順列を列挙すると、ＡＢ、ＡＣ、ＢＣ、ＢＡ、ＣＡ、ＣＢとなる。つまり、例えば、Ａが故障したときはＢが処理を引き継ぐ、Ａが故障したときにはＣが引き継ぐ、Ｂが故障したときはＣが処理を引き継ぐ、…というように、故障サーバとその故障サーバの処理を引き継ぐサーバとの順列組合せをすべて列挙する。なお、このようにして列挙した順列を基本順列とする。サーバが３台の場合の基本順列の数は３Ｐ２、つまり６個となる。
【００５３】
図５の説明に戻る。Ｓ２１の後、接続グラフ生成部２４４は、基本順列接続グラフを生成する（Ｓ２２）。具体的には、接続グラフ生成部２４４は、Ｓ２１で抽出した順列組合せ（基本順列）同士をノードとして接続した基本順列接続グラフを生成する。
【００５４】
例えば、図７に示すように、基本順列がＡＢ、ＡＣ、ＢＣ、ＢＡ、ＣＡ、ＣＢである場合、接続グラフ生成部２４４は、各基本順列について、後ろ２−１＝１の長さの部分順列で始まる基本順列と接続する。つまり、接続グラフ生成部２４４は、各基本順列をラベルに持つノードを生成し、各基本順列についてはじめの１サーバを除く部分順列を抽出する。例えば、ＡＢ、ＡＣ、ＢＣ、ＢＡ、ＣＡ、ＣＢという基本順列をラベルに持つノードを生成し、ＡＢについてはＢという部分順列を抽出し、ＡＣについてはＣという部分順列を抽出する。このような処理をすべての基本順列に対し行う。そして、接続グラフ生成部２４４は、その抽出した部分順列から始まる基本順列を抽出する。例えば、Ｂという部分順列から始まる基本順列としてＢＣ、ＢＡを抽出し、Ｃという部分順列から始まる基本順列としてＣＡ、ＣＢを抽出する（図７の「基本順列接続グラフのリンク」参照）。このように、接続グラフ生成部２４４は、基本順列の最後尾と同じサーバを先頭に持つ基本順列をグラフのリンク先として抽出する。そして、接続グラフ生成部２４４は、各基本順列を示すノードを、前記した処理により抽出したリンク先のノードと有向リンクにより接続し、図７の右側に示すような基本順列接続グラフを生成する。
【００５５】
図５の説明に戻る。Ｓ２２の後、順列閉路抽出部２４５は、Ｓ２２で生成された基本順列接続グラフから、各ノードを同じ回数通る基本順列閉路を抽出する（Ｓ２３）。
【００５６】
例えば、順列閉路抽出部２４５は、図８に示すような基本順列接続グラフから、各ノードを同回数通る閉路を抽出し、図８の右側に示す基本順列閉路を得る。このような閉路が生成されれば、最大スロット列生成部２４３が、この閉路に沿ってスロット列上のサーバの順番を決定することで、各基本順列が同回数出現するスロット列を生成することができる。当該閉路の抽出方法は問わないが、少なくとも当該グラフはオイラー閉路を持つ条件を満たしているため、Fleuryのアルゴリズムを用いることでオイラー閉路を抽出することが可能である。
【００５７】
なお、図８に例示した基本順列接続グラフは、各ノードが入次数、出次数ともに２次の有向グラフとなっているため、抽出されたオイラー閉路は各ノードを丁度２回ずつ通る閉路となる。以降の説明では基本順列閉路として図８に示す「ＡＢ→ＢＣ→ＣＢ→ＢＡ→ＡＣ→ＣＡ→ＡＣ→ＣＢ→ＢＣ→ＣＡ→ＡＢ→ＢＡ（ＡＢに戻る）」を用いるものとする。
【００５８】
図５の説明に戻る。Ｓ２３の後、スロット列生成部２４６は、Ｓ２３で抽出された基本順列閉路を構成するノードそれぞれの先頭のサーバを閉路の順に並べてスロット列を生成する（Ｓ２４）。例えば、スロット列生成部２４６は、図９に示すように基本順列閉路をＡＢ→ＢＣ→ＣＢ→ＢＡ→ＡＣ→ＣＡ→ＡＣ→ＣＢ→ＢＣ→ＣＡ→ＡＢ→ＢＡの順に走査し、それぞれのラベルのはじめのサーバを閉路に沿って並べ、スロット列としてＡＢＣＢＡＣＡＣＢＣＡＢを生成する。
【００５９】
その後、スロット群生成部２４１は、例えば、図５のＳ２４で生成されたスロット列の長さでハッシュ空間を等分（空間を１２等分）し、スロット列（ＡＢＣＢＡＣＡＣＢＣＡＢ）と同じ順で各スロットにサーバを割り当てたスロット群を生成する。つまり、スロット群生成部２４１は、Ａ→Ｂ→Ｃ→Ｂ→Ａ→Ｃ→Ａ→Ｃ→Ｂ→Ｃ→Ａ→Ｂ（→Ａに戻る）というスロット群を生成する。
【００６０】
このようにして生成されたスロット群には、前記した基本順列が全て同じ回数含まれる。したがって、振分部２２０が、受信パケットの振り分けにこのようなスロット群を用いることで、負荷分散システム内のサーバ３００の故障時を含め、各サーバ間の負荷を均一化させることができる。すなわち、前記したスロット群には、サーバ３００もサーバ３００の順列も同じ数だけ登場するため、平常時の割り当てスロット数が均一となる。さらに、例えばスロットの割り当てとしてＡ→Ｂの順で割り当てている部分があった場合、Ａが故障時にはコンシステント・ハッシュ法に従うと、次のＢが割り当てを受ける形となる。その結果、全ての基本順列の登場回数が同じであった場合、各サーバ３００の次に他のサーバ３００が登場する回数が均一となり、故障時も負荷を均一化させることができる。
【００６１】
なお、上記では、説明を簡単にするため、負荷分散システムの最大サーバ数がＡ、Ｂ、Ｃの３台である場合のスロット列の生成手順を示したが、最大サーバ数がＡ、Ｂ、Ｃ、Ｄ、Ｅの５台である場合のスロット列も同様の手順により生成される。例えば、最大サーバ数がＡ、Ｂ、Ｃ、Ｄ、Ｅの５台である場合、最大スロット列生成部２４３はオイラー閉路から生成すると「ＡＢＣＤＥＡＢＤＡＤＣＤＢＤＢＥＤＢＣＡＣＢＡＥＢＤＥＣＤＡＢＥＡＣＤＣＢＥＢＣＥＢＡＣＥＡＤＥＢＥＣＥＣＢＣＢＤＣＡＢＡＤＡＣＡＥＡＥＤＥＤＣＥＤＡＥＣＡＤＢ」、オイラー閉路ではなく各ノードを２回ずつ通る閉路を用いる場合は「ＡＥＡＤＥＤＡＥＡＢＥＢＤＥＤＢＥＢＣＥＣＤＣＥＣＢＤＢＡＤＡＣＤＣＡＣＢＣＡＢ」というスロット列を生成する。そして、最大スロット列生成部２４３は、生成したスロット列を、スロット群生成部２４１へ出力する。なお、以降の説明では最大スロット列としては後者の「ＡＥＡＤＥＤＡＥＡＢＥＢＤＥＤＢＥＢＣＥＣＤＣＥＣＢＤＢＡＤＡＣＤＣＡＣＢＣＡＢ」を用いる。
【００６２】
（スロット群生成部の処理手順）
図１１を用いて、スロット群生成部２４１の処理手順を説明する。スロット群生成部２４１のパラメータ受信部２４１１は、サーバ群抽象化部２５１からスロット群生成に関するパラメータを受信すると（Ｓ１）、最大スロット列生成依頼部２４１２は、最大スロット列生成部２４３に対し最大スロット列の生成依頼を行う（Ｓ２）。その後、最大スロット列生成部２４３から、最大スロット列を受信すると（Ｓ３）、判定部２４１３は、Ｓ１で受信したパラメータに示される、最大のサーバ群の数（最大サーバ数）と現在必要なサーバ数とを比較し、サーバ３００の減設が必要か否かを判定する（Ｓ４）。ここで判定部２４１３において、サーバ３００の減設が必要と判定した場合（Ｓ４でＹｅｓ）、スロット群生成部２４１は、減設スロット群の生成を行う（Ｓ５）。つまり、スロット群生成部２４１は、減設スロット列を生成し、この生成した減設スロット列をもとにスロット群（減設スロット群）を生成する。一方、判定部２４１３がサーバ３００の減設は必要ないと判定した場合（Ｓ４でＮｏ）、スロット群生成部２４１は、Ｓ３で受信した最大スロット列をもとにスロット群を生成する（Ｓ６）。
【００６３】
図１１の減設スロット群生成処理（Ｓ５）は、図１２に示す手順により行われる。まず、スロット列延長部２４１４は、最大スロット列生成部２４３から得られた最大スロット列について、１回以上繰り返した延長スロット列を生成する（Ｓ８０：スロット列延長）。例えば、スロット列延長部２４１４は、図１３に示すように３回繰り返した延長スロット列を生成する。この繰り返しの回数については１でもよいが、基本的には大きくするほど、負荷分散システムのサーバ３００間での負荷の偏りを抑制することができる。
【００６４】
次に、処理対象集合抽出部２４１５は、図１２のＳ８０で生成された延長スロット列に現れるサーバ集合と、スロット群を生成するよう求められているサーバ群との差分を減設対象のサーバ３００として抽出する（Ｓ９０：減設対象集合抽出）。例えば、処理対象集合抽出部２４１５は、例えば、最大のサーバ群（Ａ、Ｂ、Ｃ、Ｄ、Ｅ）の中から、減設対象集合として｛Ｅ｝を抽出する。Ｓ９０の後、サーバ選定部２４１７は、減設対象集合が空集合になるまで１サーバずつ選択する。
【００６５】
すなわち、減設対象集合に減設対象があれば（Ｓ１００でＹｅｓ）、まずスロット列保管処理部２４１６は、その段階での延長スロット列をスロット保管部２４２に保管する（Ｓ１１０：スロット列保管）。ここで延長スロット列を保管するのは、サーバ３００を減設して負荷分散システムの運用を開始した後、サーバ３００を増設する場合に、この増設したサーバ３００を含めたスロット群の生成を行うときに用いるためである。一方、Ｓ１００で減設対象集合に減設対象がなければ（Ｓ１００でＮｏ）、スロット群生成部２４１は現在のスロット列をもとにスロット群を生成する（Ｓ１５０）。そして、生成したスロット群を、スロット保管部２４２に出力する。
【００６６】
Ｓ１１０の後、サーバ選定部２４１７は、減設対象集合｛Ｅ｝から１つ、例えば降順等の条件で置換処理の対象のサーバ３００を選定する（Ｓ１２０：処理対象サーバ選定）。例えば、サーバ選定部２４１７は、減設対象集合｛Ｅ｝からＥを選定する。
【００６７】
Ｓ１２０の後、サーバ置換部２４１８は、延長スロット列における置換処理の対象のサーバ３００（例えば、Ｅ）を他のサーバ３００に置換する（Ｓ１３０：処理対象サーバ置換）。具体的には、サーバ置換部２４１８は延長スロット列中、Ｓ１２０で選定したサーバ３００（例えば、Ｅ）が登場する箇所を、負荷分散システムを構成する他のサーバ３００（例えば、Ａ、Ｂ、Ｃ、Ｄのいずれか）に置換する。このとき、サーバ置換部２４１８は、サーバ置換後の延長スロット列に登場するサーバ３００（Ａ、Ｂ、Ｃ、Ｄ）の基本順列（例えば、ＡＢ、ＣＤ等）それぞれの登場回数ができるだけ同じになるように置換する。このＳ１３０の処理の詳細は具体例を交えながら後記する。
【００６８】
Ｓ１３０の後、サーバ置換部２４１８は減設対象集合の更新を行い（Ｓ１４０）、Ｓ１００へ戻る。そして、Ｓ１００で減設対象集合に減設対象がなければ（Ｓ１００でＮｏ）、スロット群生成部２４１は現在のスロット列をもとにスロット群を生成する（Ｓ１５０）。すなわち、スロット群生成部２４１は、生成されたスロット列の長さでハッシュ空間を分割し、それをスロット列に沿って各サーバ３００に割り当てることでスロット群を生成する。例えば、生成されたスロット列の長さが「２０」であった場合、図１５に例示するようにハッシュ空間を２０に分割し、生成されたスロット列に沿って各サーバ３００に割り当てることでスロット群を生成する。
【００６９】
なお、このスロット群においてサーバ３００それぞれの登場回数が各サーバ３００間で同じであるほど各サーバ３００が正常動作している場合の負荷が均一化される。また、このスロット群において各基本順列の登場回数が各基本順列間で同じであるほど、基本順列長−１台まで故障した場合の稼働サーバ間での負荷が均一化される。
【００７０】
（処理対象サーバ置換処理）
前記した図１２のＳ１３０における処理対象サーバ置換処理を詳細に説明する。例えば、図１３に示すような延長スロット列においてＡ〜ＥのうちＥを置換処理の対象として選定した場合を考える。この場合、延長スロット列中にＥは２４回登場しているが、サーバ置換部２４１８は、その登場している箇所についてＥ以外のいずれかのサーバ（Ａ、Ｂ、Ｃ、Ｄのいずれか）に置換する。このときサーバ置換部２４１８は、基本順列（例えば、ＡＢ、ＣＤ等）それぞれの登場回数ができるだけ同じになるように置換する。
【００７１】
例えば、サーバ置換部２４１８は、延長スロット列においてＥが登場している箇所それぞれについてＡ、Ｂ、Ｃ、Ｄそれぞれに置換してみて、置換後に全ての基本順列（ＡＢ、ＢＡ、ＢＣ、ＣＢ、ＣＤ、ＤＣ、ＤＡ、ＡＤ、ＡＣ、ＣＡ、ＢＤ、ＤＢ）の登場回数の分散値が最少となる置換を探索する。
【００７２】
その結果、例えば、図１４に示すように、サーバ数５の延長スロット列から、同図に示すサーバ数４のスロット列が生成される。このサーバ数４のスロット列では、全ての基本順列（ＡＢ、ＢＡ、ＢＣ、ＣＢ、ＣＤ、ＤＣ、ＤＡ、ＡＤ、ＡＣ、ＣＡ、ＢＤ、ＤＢ）が等しく１０回ずつ登場している。
【００７３】
したがって、このスロット列に沿ってスロット割り当て部２４１９がスロット群を生成すれば、負荷分散システム内でＡ、Ｂ、Ｃ、Ｄの４サーバが正常に動作しているときも、その任意の１台が故障したときもサーバ間の負荷を均一化するようなスロット群を生成することができる。また、サーバ置換部２４１８は、延長スロット列から減設対象のサーバ３００の登場する箇所を別のサーバ３００に置き換えたスロット列（減設スロット列）を生成する。したがって、このスロット列に沿ってスロット割り当て部２４１９がスロット群を生成すれば、サーバ３００の減設があった場合でも、減設前のスロット群と比較して、減設対象のサーバ３００のハッシュ空間の割当担当範囲のみ変更されたスロット群を生成することができる。例えば、負荷分散システムを構成するサーバ数が４（Ａ、Ｂ、Ｃ、Ｄ）と５（Ａ、Ｂ、Ｃ、Ｄ、Ｅ）との間で変動したときも、減設対象のサーバ３００（例えば、Ｅ）に割り当てられていたハッシュ空間の割当担当範囲のみ変更されたスロット群を生成することができる。したがって、負荷分散システムを構成するサーバ数に増減があったときでも、上記の処理により生成されたスロット群を用いて、振分部２２０がパケットの振り分けを行うことで、サーバ間での保管データの移動等による影響を必要最小限にすることができる。
【００７４】
なお、この後、システム保守者４００等から、負荷分散システムを構成するサーバ３００の変更に関する要求があった場合は、当該要求を受信したスロット群生成部２４１は運用中のサーバ数と、要求されたサーバ数とを比較し、サーバ３００の減設または増設が必要か否かを判定する。
【００７５】
例えば、現在運用中のサーバ数が４（Ａ、Ｂ、Ｃ、Ｄ）であり、要求されるサーバ数が３（Ａ、Ｂ、Ｃ）である場合、当該要求を受信したスロット群生成部２４１は、サーバ３００（例えば、Ｄ）の減設が必要であると判定する。そして、スロット群生成部２４１は、図１２に示したフローの中でスロット列延長処理（Ｓ８０）を実行せず、Ｓ９０以降の処理を実行することで、スロット保管部２４２に保管されるサーバ数４の場合のスロット列から、減設対象のサーバ３００（例えば、Ｄ）を減設したスロット列を生成する。例えば、スロット群生成部２４１は、図１４に示すサーバ数３の場合のスロット列を生成する。そして、スロット群生成部２４１は、減設対象のサーバ３００（例えば、Ｄ）を減設したスロット列を生成する。
【００７６】
また、例えば、現在運用中のサーバ数が３であり、要求されるサーバ数が４または５である場合、つまり、現在運用中のサーバ数よりも、要求されるサーバ数の方が大きく、かつ最大サーバ数より小さい場合には、当該要求を受信したスロット群生成部２４１は、サーバ３００の増設が必要であると判定する。そして、スロット群生成部２４１はスロット保管部２４２にサーバ数４または５の場合のスロット列（例えば、図１４のサーバ数４のスロット列またはサーバ数５のスロット列）を取り出し、取り出したスロット列をもとに、スロット群を生成する。
【００７７】
このようにすることで、例えば、負荷分散システムのサーバ数を３（例えば、Ａ、Ｂ、Ｃ）から、４（例えば、Ａ、Ｂ、Ｃ、Ｄ）に増加させる場合でも、スロット群生成部２４１は、増設対象のサーバ３００（例えば、Ｄ）以外のサーバ３００（例えば、Ａ、Ｂ，Ｃ）に割り当てられるハッシュ空間の担当範囲をできるだけ変えないようなスロット群を生成することができる。その結果、負荷分散システムにおいてサーバ３００を増設する場合でも、最大サーバ数以下であれば、スロット群生成部２４１は、サーバ間で負荷を均一化しつつ、サーバ間で保管データの移動等による影響を必要最小限にするようなスロット群を生成することができる。
【００７８】
（第２の実施形態）
次に、本発明の第２の実施形態を説明する。第２の実施形態は、最大スロット列生成部２４３ａが、最大スロット数のスロット列（最大スロット列）を生成するとき、サーバリストの一部のサーバのスロット列を生成し（基本スロット列生成）、そのスロット列をサーバリストの残りのサーバ分まで拡張する（スロット列拡張を行う）ことを特徴とする。このように最大スロット列生成部２４３ａが基本スロット列生成とスロット列拡張とを組み合わせてスロット列を生成することで、サーバリストに示されるサーバの台数が多い場合でも、全サーバのスロット列の生成にかかる計算量とスロット長を低減することができる。
【００７９】
なお、以下、最大スロット列生成部２４３ａは、まずサーバリストのサーバのうち、（基本順列長＋１）台のサーバのスロット列を生成し、その後、このスロット列を残りのサーバ分まで拡張する場合を例に説明する。前記した第１の実施形態と同じ構成は、同じ符号を付して説明を省略する。
【００８０】
この最大スロット列生成部２４３ａは、図３に示すように、破線で示す拡張基礎順列生成部２４８と、拡張スロット列生成部２４９とをさらに備える。
【００８１】
まず、最大スロット列生成部２４３ａは、スロット順列組合せ生成部２４３、接続グラフ生成部２４４、順列閉路抽出部２４５、および、スロット列生成部２４６により、サーバリストに示されるサーバ（例えば、Ａ〜Ｅ）のうち、（基本順列長＋１）台のサーバ、例えば、Ａ、Ｂ、Ｃの３台のサーバのスロット列を生成する。
【００８２】
拡張基礎順列生成部２４８は、スロット順列組合せ生成部２４３により生成された基本順列に示されるサーバ（例えば、Ａ、Ｂ、Ｃ）から、（基本順列長−１）台のサーバの順列組合せである拡張基礎順列をすべて抽出する。例えば、拡張基礎順列生成部２４８は、拡張基礎順列として、Ａ、Ｂ、Ｃを抽出する。
【００８３】
拡張スロット列生成部２４９は、サーバリストに示されるサーバ（例えば、Ａ〜Ｅ）のうち、スロット列生成部２４６がスロット列（基本スロット列）の対象としなかったサーバを１つ選択する。
【００８４】
例えば、拡張スロット列生成部２４９は、Ｄ、Ｅのいずれかを選択する、そして、拡張スロット列生成部２４９は、スロット列生成部２４６により生成されたスロット列（例えば、ＡＢＣＢＡＣ）から、拡張基礎順列に示されるサーバ（例えば、Ａ、Ｂ、Ｃ）を１つずつ抽出し、それぞれ拡張対象サーバ（例えば、Ｄ）を拡張基礎順列（例えば、Ａ、Ｂ、Ｃ）で挟んだ順列で置換する。これにより、基本スロット列に、拡張対象サーバが挿入された新たなスロット列が生成される。つまり、基本スロット列が拡張対象サーバの分まで拡張される。その後、拡張スロット列生成部２４９は、上記と同様の処理により、拡張サーバ（例えば、Ｄ）が挿入されたスロット列に、さらに拡張対象サーバ（例えば、Ｅ）を挿入する。これにより、サーバリストに示される全サーバ（Ａ、Ｂ、Ｃ、Ｄ、Ｅ）のスロット列が生成される。
【００８５】
この拡張基礎順列生成部２４８と、拡張スロット列生成部２４９の詳細は、具体例を用いて後記する。
【００８６】
次に、第２の実施形態の最大スロット列生成部２４３ａにおけるスロット群生成の処理手順について説明する。
【００８７】
図１６に示すように、最大スロット列生成部２４３ａは、サーバリストおよび基本順列長を示した基礎情報を取得し（Ｓ４０）、この基礎情報をもとに基本スロット列生成用のサーバリストを抽出する（Ｓ５０）。そして、最大スロット列生成部２４３ａは、Ｓ５０で抽出されたサーバリストをもとに、図４のＳ２０と同様の手順により基本スロット列生成を行う（Ｓ２０）。そして、最大スロット列生成部２４３ａは、拡張情報を生成する（Ｓ６０）。この拡張情報は、スロット列を拡張するために用いられる情報であり、基本スロット列生成用のサーバリスト（拡張前サーバリスト）と、Ｓ２０で生成した基本スロット列（拡張前のスロット列）と、基本順列長と、サーバリストのうち基本スロット列の対象外としたサーバのリスト（拡張サーバリスト）とを示した情報である。
【００８８】
例えば、図１７に示すように、基礎情報に示されるサーバリストが「Ａ、Ｂ、Ｃ、Ｄ、Ｅ」であり、基本順列長が「２」である場合、最大スロット列生成部２４３ａは、基本順列長＋１＝３台のサーバを任意に抽出し、基本スロット列生成のためのサーバリスト（例えば、Ａ、Ｂ、Ｃ）を抽出する。なお、ここで抽出対象外のサーバ（例えば、Ｄ、Ｅ）は拡張サーバリストにのせる。その後、最大スロット列生成部２４３ａは基本スロット列生成処理（図４のＳ２０と同様の処理）によってスロット列を生成する。このスロット列を基本スロット列とする。そして、最大スロット列生成部２４３ａは、拡張前サーバリスト（基本スロット列生成用のサーバリスト）が「Ａ、Ｂ、Ｃ」であり、拡張前のスロット列（基本スロット列）が「ＡＢＣＢＡＣＡＣＢＣＡＢ」であり、基本順列長が「２」であり、拡張サーバリストが「Ｄ、Ｅ」であることを示した拡張情報を生成する。
【００８９】
図１６の説明に戻る。Ｓ６０の後、最大スロット列生成部２４３ａは、Ｓ６０で生成された拡張情報をもとにスロット列拡張処理を実行する（Ｓ７０）。
【００９０】
ここで、図１８を用いて、図１６のＳ７０のスロット列拡張処理を説明する。拡張基礎順列生成部２４８は、Ｓ６０で生成された拡張情報を取得すると（Ｓ７１）、拡張対象サーバを抽出し（Ｓ７２）、拡張基礎順列を生成する（Ｓ７３）。
【００９１】
例えば、拡張基礎順列生成部２４８は、図１７に示す拡張情報の拡張サーバリスト「Ｄ、Ｅ」から、Ｄを抽出する。そして、拡張基礎順列生成部２４８は、図１９に示すように、拡張前サーバリストは「Ａ、Ｂ、Ｃ」、基本順列長は「２」という情報から、Ａ、Ｂ、Ｃの３つのサーバについて、基本順列長２−１＝１の長さの全順列を生成する。ここで抽出する順列を拡張基礎順列と呼ぶ。例えば、拡張基礎順列生成部２４８は、拡張基礎順列として「Ａ、Ｂ、Ｃ」を生成する。ここで抽出する拡張基礎順列の個数はサーバがＡ、Ｂ、Ｃの３台の場合、３Ｐ１＝３個となる。
【００９２】
図１８の説明に戻る。Ｓ７３の後、拡張スロット列生成部２４９は、Ｓ７３で生成された拡張基礎順列をスロット列へ挿入する（Ｓ７４）。
【００９３】
例えば、拡張スロット列生成部２４９は、Ｓ７３で生成された拡張基礎順列（例えば、Ａ、Ｂ、Ｃ）について、拡張前のスロット列（例えば、ＡＢＣＢＡＣＡＣＢＣＡＢ）から２つずつ、その位置を検索していく。いくつずつ検索していくかについては、当該スロット列の基本順列閉路（図８参照）において各ノードを通過した回数に等しく、拡張前のスロット列長を基本順列の数で除することで求められる。例えば、前記した例でいうと拡張前のスロット列（ＡＢＣＢＡＣＡＣＢＣＡＢ）の長さは「１２」で、基本順列の数は「３Ｐ２＝６」なので、「１２÷６＝２」となる。
【００９４】
そして、拡張スロット列生成部２４９は、拡張前のスロット列から検索した拡張基礎順列のそれぞれについて、その拡張基礎順列で拡張対象サーバを挟んだ順列で置換していく。例えば、拡張対象サーバが「Ｄ」である場合を考える。この場合、図２０に示すように、拡張スロット列生成部２４９は、拡張基礎順列「Ａ」については、拡張前のスロット列で「Ａ」となっている箇所２つについて、「ＡＤＡ」で置換する。また、同様に、拡張前のスロット列で「Ｂ」となっている箇所２つについて、「ＢＤＢ」で置換する。さらに、拡張前のスロット列で「Ｃ」となっている箇所２つについて、「ＣＤＣ」で置換する。その結果、拡張後のスロット列として「ＡＤＡＢＤＢＣＤＣＢＤＢＡＤＡＣＤＣＡＣＢＣＡＢ」が得られる。
【００９５】
このように、拡張スロット列生成部２４９は、拡張前のスロット列から、拡張基礎順列を各２抽出し、それぞれ拡張対象サーバを当該拡張基礎順列で挟んだ順列で置換する。なお、前記した例では、拡張基礎順列の長さが「１」である場合について説明したが、長さが「２」である場合、例えば、拡張基礎順列が「ＡＢ」である場合、拡張対象サーバが「Ｄ」なら、拡張前のスロット列で「ＡＢ」となっている箇所について「ＡＢＤＡＢ」に置換する。
【００９６】
図１８の説明に戻る。このようにして拡張基礎順列をスロット列に挿入した（Ｓ７４）後、拡張スロット列生成部２４９は、処理済みの拡張対象サーバを拡張前サーバリストに加える等して拡張情報を更新する（Ｓ７５）。例えば、拡張スロット列生成部２４９は、拡張前のスロット列「ＡＢＣＢＡＣＡＣＢＣＡＢ」に、サーバ「Ｄ」を挿入した後、図２１の左側の拡張情報を、右側の拡張情報へ更新する。
【００９７】
図１８の説明に戻る。Ｓ７６で拡張対象サーバが残存していれば（Ｓ７６でＹｅｓ）、最大スロット列生成部２４３ａは、更新した拡張情報を用いて、再度Ｓ７１以降の処理を実行する。一方、拡張対象サーバが残存していなければ（Ｓ７６でＮｏ）、スロット列拡張処理を終了する。
【００９８】
なお、拡張スロット列生成部２４９は、図２０に示す処理により、拡張対象サーバ「Ｄ」をスロット列へ挿入した後、上記と同様の処理により拡張対象サーバ「Ｅ」をスロット列へ挿入する。つまり、拡張スロット列生成部２４９は、「ＡＤＡＢＤＢＣＤＣＢＤＢＡＤＡＣＤＣＡＣＢＣＡＢ」というスロット列を生成した後、このスロット列の「Ａ、Ｂ、Ｃ、Ｄ」が登場する箇所を２つずつ抽出し、それぞれについて、拡張対象サーバ「Ｅ」を挟んだ順列で置換していく。その結果、拡張スロット列生成部２４９は、「ＡＥＡＤＥＤＡＥＡＢＥＢＤＥＤＢＥＢＣＥＣＤＣＥＣＢＤＢＡＤＡＣＤＣＡＣＢＣＡＢ」というスロット列を生成する。
【００９９】
以上の処理によってサーバリストに示される全てのサーバ（Ａ、Ｂ、Ｃ、Ｄ、Ｅ）が組み込まれたスロット列が完成すると、スロット群生成部２４１はこれをもとにスロット群を生成する。
【０１００】
例えば、最大スロット列生成部２４３ａは、ハッシュ値の空間を、スロット列「ＡＥＡＤＥＤＡＥＡＢＥＢＤＥＤＢＥＢＣＥＣＤＣＥＣＢＤＢＡＤＡＣＤＣＡＣＢＣＡＢ」の長さ４０に分割したスロットを生成すると、スロット群生成部２４１はこのスロットに、スロット列「ＡＥＡＤＥＤＡＥＡＢＥＢＤＥＤＢＥＢＣＥＣＤＣＥＣＢＤＢＡＤＡＣＤＣＡＣＢＣＡＢ」に登場する順番で担当サーバを割り当てる。
【０１０１】
以上の処理によって、サーバリストに示される全てのサーバが含まれ、かつ、それらの間で担当範囲が均一なスロット群が生成されたため、当該スロット群を用いた負荷分散システムでは、負荷をサーバ間で均一に分散することが可能となる。
【０１０２】
また、最大スロット列生成部２４３ａが、スロット列の生成を（基本順列長＋１）台までとし、（基本順列長＋１）台を超えた分のサーバについてはスロット列拡張処理によりスロット列に挿入することで、サーバリストに示される全サーバについてのスロット列を生成する際の計算量とスロット長を低減できる。
【０１０３】
（その他の実施形態）
なお、図１のスロット群管理部２４０は、負荷分散装置２００の中に１つであるように例示しているが、図２２のように負荷分散装置２００から切り出し、スロット群提供装置５００のような構成にしてもよく、またこの場合、１つのスロット群提供装置５００が複数の負荷分散装置２００の処理を行うことも可能である。
【０１０４】
（プログラム）
また、上記実施形態に係る負荷分散装置２００が実行する処理をコンピュータが実行可能な言語で記述したプログラムを作成することもできる。この場合、コンピュータがプログラムを実行することにより、上記実施形態と同様の効果を得ることができる。さらに、かかるプログラムをコンピュータ読み取り可能な記録媒体に記録して、この記録媒体に記録されたプログラムをコンピュータに読み込ませて実行することにより上記実施形態と同様の処理を実現してもよい。以下に、負荷分散装置２００と同様の部を実現する負荷分散プログラムを実行するコンピュータの一例を説明する。
【０１０５】
図２３は、負荷分散プログラムを実行するコンピュータを示す図である。図２３に示すように、コンピュータ１０００は、例えば、メモリ１０１０と、ＣＰＵ１０２０と、ハードディスクドライブインタフェース１０３０と、ディスクドライブインタフェース１０４０と、シリアルポートインタフェース１０５０と、ビデオアダプタ１０６０と、ネットワークインタフェース１０７０とを有する。これらの各部は、バス１０８０によって接続される。
【０１０６】
メモリ１０１０は、ＲＯＭ（Read  Only  Memory）１０１１およびＲＡＭ（Random  Access  Memory）１０１２を含む。ＲＯＭ１０１１は、例えば、ＢＩＯＳ（Basic  Input  Output  System）等のブートプログラムを記憶する。ハードディスクドライブインタフェース１０３０は、ハードディスクドライブ１０９０に接続される。ディスクドライブインタフェース１０４０は、ディスクドライブ１１００に接続される。ディスクドライブ１１００には、例えば、磁気ディスクや光ディスク等の着脱可能な記憶媒体が挿入される。シリアルポートインタフェース１０５０には、例えば、マウス１１１０およびキーボード１１２０が接続される。ビデオアダプタ１０６０には、例えば、ディスプレイ１１３０が接続される。
【０１０７】
ここで、図２３に示すように、ハードディスクドライブ１０９０は、例えば、ＯＳ１０９１、アプリケーションプログラム１０９２、プログラムモジュール１０９３およびプログラムデータ１０９４を記憶する。上記実施形態で説明した各テーブルは、例えばハードディスクドライブ１０９０やメモリ１０１０に記憶される。
【０１０８】
また、負荷分散プログラムは、例えば、コンピュータ１０００によって実行される指令が記述されたプログラムモジュールとして、ハードディスクドライブ１０９０に記憶される。具体的には、上記実施形態で説明した負荷分散装置２００が実行する各処理が記述されたプログラムモジュールが、ハードディスクドライブ１０９０に記憶される。
【０１０９】
また、負荷分散プログラムによる情報処理に用いられるデータは、プログラムデータとして、例えば、ハードディスクドライブ１０９０に記憶される。そして、ＣＰＵ１０２０が、ハードディスクドライブ１０９０に記憶されたプログラムモジュール１０９３やプログラムデータ１０９４を必要に応じてＲＡＭ１０１２に読み出して、上述した各手順を実行する。
【０１１０】
なお、負荷分散プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ハードディスクドライブ１０９０に記憶される場合に限られず、例えば、着脱可能な記憶媒体に記憶されて、ディスクドライブ１１００等を介してＣＰＵ１０２０によって読み出されてもよい。あるいは、負荷分散プログラムに係るプログラムモジュール１０９３やプログラムデータ１０９４は、ＬＡＮ（Local  Area  Network）やＷＡＮ（Wide  Area  Network）等のネットワークを介して接続された他のコンピュータに記憶され、ネットワークインタフェース１０７０を介してＣＰＵ１０２０によって読み出されてもよい。
【符号の説明】
【０１１１】
１００  クライアント
２００  負荷分散装置
２１０  パケット受信部
２２０  振分部
２２１  キー抽出部
２２２  パケット送信先決定部
２３０  パケット転送部
２４０  スロット群管理部
２４１  スロット群生成部
２４２  スロット保管部
２４３、２４３ａ  最大スロット列生成部
２４４  接続グラフ生成部
２４５  順列閉路抽出部
２４６  スロット列生成部
２４８  拡張基礎順列生成部
２４９  拡張スロット列生成部
２５０  スロット群汎用化部
２５１  サーバ群抽象化部
２５２  サーバ群個別化部
２５３  サーバリスト保持テーブル
３００  サーバ
２４１１  パラメータ受信部
２４１２  最大スロット列生成依頼部
２４１３  判定部
２４１４  スロット列延長部
２４１５  処理対象集合抽出部
２４１６  スロット列保管処理部
２４１７  サーバ選定部
２４１８  サーバ置換部
２４１９  スロット割り当て部
２４３１  スロット列順列組合せ生成部
【図１】
2015184744.tif 000003
【図２】
2015184744.tif 000004
【図３】
2015184744.tif 000005
【図４】
2015184744.tif 000006
【図５】
2015184744.tif 000007
【図６】
2015184744.tif 000008
【図７】
2015184744.tif 000009
【図８】
2015184744.tif 000010
【図９】
2015184744.tif 000011
【図１０】
2015184744.tif 000012
【図１１】
2015184744.tif 000013
【図１２】
2015184744.tif 000014
【図１３】
2015184744.tif 000015
【図１４】
2015184744.tif 000016
【図１５】
2015184744.tif 000017
【図１６】
2015184744.tif 000018
【図１７】
2015184744.tif 000019
【図１８】
2015184744.tif 000020
【図１９】
2015184744.tif 000021
【図２０】
2015184744.tif 000022
【図２１】
2015184744.tif 000023
【図２２】
2015184744.tif 000024
【図２３】
2015184744.tif 000025