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