(57)【特許請求の範囲】
【請求項１】
相互に通信可能に接続される複数のＤＢサーバと、前記複数のＤＢサーバそれぞれと通信可能に接続される仮想サーバ配置装置とを備えるデータ負荷分散配置システムであって、
前記ＤＢサーバは、
（１）クライアントからの検索対象となるデータ、およびそのデータそれぞれに対応付けられるデータキー、（２）前記ＤＢサーバ自身のサーバ性能、並びに、（３）前記データそれぞれの保存先の前記ＤＢサーバを示すサーバ担当データ情報が保存される記憶部と、
前記データキーおよび前記サーバ性能を、前記仮想サーバ配置装置に送信するデータ管理部と、
前記仮想サーバ配置装置から、新たな前記サーバ担当データ情報を受信し、前記保存していたサーバ担当データ情報と比較することにより、自身の前記ＤＢサーバの前記記憶部に保存していないデータおよびそのデータの保存先となる他のＤＢサーバを抽出し、前記抽出した他のＤＢサーバにデータ交換要求を送信することにより、前記自身が保存していないデータを取得し、前記保存していたサーバ担当データ情報を前記新たなサーバ担当データ情報に更新するデータ交換部と、を備え、
前記仮想サーバ配置装置は、
前記データ負荷分散配置システム全体に求められる処理性能と、前記ＤＢサーバそれぞれに設定する負荷の閾値を示す負荷閾値定数が保存される記憶部と、
前記ＤＢサーバそれぞれから取得した、前記サーバ性能と、前記負荷閾値定数とを用いて、前記ＤＢサーバそれぞれの負荷の閾値であるサーバ閾値を計算し、前記データ負荷分散配置システム全体に求められる処理性能と、前記ＤＢサーバそれぞれから取得した前記データキーの数の合計であるシステム全体のデータ数とに基づき、前記データへのアクセス回数が均等であると仮定して、前記ＤＢサーバそれぞれの負荷を計算し、前記ＤＢサーバごとに、前記負荷と前記サーバ閾値との差の絶対値を計算し、前記負荷が前記サーバ閾値以下のサーバＳ−の集合と、前記負荷が前記サーバ閾値を超えるサーバＳ＋の集合とを生成するサーバ負荷計算部と、
前記ＤＢサーバおよび前記データそれぞれについて、所定のハッシュ関数を用いてハッシュ値を算出することにより、ハッシュ空間上に、前記データの保存を担当する前記ＤＢサーバの担当領域を設定し、前記サーバＳ＋の集合うち、前記負荷と前記サーバ閾値との差の絶対値が大きいＤＢサーバから順に、前記ハッシュ空間上の前記サーバＳ＋の担当領域において、担当できるデータ数が自身のＤＢサーバのサーバ閾値を超える超過分に対して、前記サーバＳ−の集合のうち、前記絶対値が大きいＤＢサーバから順に仮想サーバを配置し、前記超過分のデータの前記ハッシュ空間上での担当領域を前記仮想サーバに変更し、前記変更したハッシュ空間上での担当領域に基づき、前記ＤＢサーバそれぞれが担当するデータの保存先を示す前記新たなサーバ担当データ情報を生成し、前記生成した新たなサーバ担当データ情報を、前記ＤＢサーバそれぞれに送信する配置処理部と、を備えること、
を特徴とするデータ負荷分散配置システム。
【請求項２】
前記ＤＢサーバは、
自身が保存する前記データの増減と、前記クライアントからの前記データに対するアクセス数とを監視し、前記データそれぞれへの前記アクセス数を示すアクセス回数情報を生成するアクセス監視部を、さらに備え、
前記データ管理部は、所定間隔ごとに、前記記憶部に保存されている前記データの前記データキーと、前記アクセス回数情報とを、前記仮想サーバ配置装置に送信し、
前記仮想サーバ配置装置は、
仮想サーバ再配置計算部を、さらに備えており、
前記サーバ負荷計算部は、前記所定間隔ごとに前記ＤＢサーバそれぞれから取得した前記アクセス回数情報に含まれる、前記データキーの数であるデータ数と、前記データへのアクセス数とを用いて、前記所定間隔ごとの前記ＤＢサーバそれぞれの前記負荷を計算することにより、前記サーバＳ−の集合と、前記サーバＳ＋の集合とを生成し、
前記仮想サーバ再配置計算部は、前記サーバＳ−の集合のうち、前記ハッシュ空間上に前記仮想サーバが配置されている前記ＤＢサーバについて、前記絶対値が大きいＤＢサーバから順に、前記仮想サーバの担当領域を前記変更前に担当していた前記ＤＢサーバの担当領域に戻したときに、当該ＤＢサーバの負荷が当該ＤＢサーバのサーバ閾値を超えない場合に、前記仮想サーバの担当領域を前記ハッシュ空間上から取り除き、前記ＤＢサーバそれぞれの前記負荷を再計算し、前記ＤＢサーバごとに、前記負荷と前記サーバ閾値との差の絶対値を計算し直すことにより、前記サーバＳ−の集合と、前記サーバＳ＋の集合とを再度生成して、前記配置処理部に引き渡すこと、
を特徴とする請求項１に記載のデータ負荷分散配置システム。
【請求項３】
相互に通信可能に接続される複数のＤＢサーバと、前記複数のＤＢサーバそれぞれと通信可能に接続される仮想サーバ配置装置とを備えるデータ負荷分散配置システムのデータ負荷分散配置方法であって、
前記ＤＢサーバは、
（１）クライアントからの検索対象となるデータ、およびそのデータそれぞれに対応付けられるデータキー、（２）前記ＤＢサーバ自身のサーバ性能、並びに、（３）前記データそれぞれの保存先の前記ＤＢサーバを示すサーバ担当データ情報が保存されている記憶部を備えており、
前記データキーおよび前記サーバ性能を、前記仮想サーバ配置装置に送信するステップを実行し、
前記仮想サーバ配置装置は、
前記データ負荷分散配置システム全体に求められる処理性能と、前記ＤＢサーバそれぞれに設定する負荷の閾値を示す負荷閾値定数が保存されている記憶部を備えており、
前記ＤＢサーバそれぞれから取得した、前記サーバ性能と、前記負荷閾値定数とを用いて、前記ＤＢサーバそれぞれの負荷の閾値であるサーバ閾値を計算し、前記データ負荷分散配置システム全体に求められる処理性能と、前記ＤＢサーバそれぞれから取得した前記データキーの数の合計であるシステム全体のデータ数とに基づき、前記データへのアクセス回数が均等であると仮定して、前記ＤＢサーバそれぞれの負荷を計算し、前記ＤＢサーバごとに、前記負荷と前記サーバ閾値との差の絶対値を計算し、前記負荷が前記サーバ閾値以下のサーバＳ−の集合と、前記負荷が前記サーバ閾値を超えるサーバＳ＋の集合とを生成するステップと、
前記ＤＢサーバおよび前記データそれぞれについて、所定のハッシュ関数を用いてハッシュ値を算出することにより、ハッシュ空間上に、前記データの保存を担当する前記ＤＢサーバの担当領域を設定し、前記サーバＳ＋の集合うち、前記負荷と前記サーバ閾値との差の絶対値が大きいＤＢサーバから順に、前記ハッシュ空間上の前記サーバＳ＋の担当領域において、担当できるデータ数が自身のＤＢサーバのサーバ閾値を超える超過分に対して、前記サーバＳ−の集合のうち、前記絶対値が大きいＤＢサーバから順に仮想サーバを配置し、前記超過分のデータの前記ハッシュ空間上での担当領域を前記仮想サーバに変更し、前記変更したハッシュ空間上での担当領域に基づき、前記ＤＢサーバそれぞれが担当するデータの保存先を示す新たなサーバ担当データ情報を生成し、前記生成した新たなサーバ担当データ情報を、前記ＤＢサーバそれぞれに送信するステップと、を実行し、
前記ＤＢサーバは、
前記仮想サーバ配置装置から、前記新たなサーバ担当データ情報を受信し、前記保存していたサーバ担当データ情報と比較することにより、自身の前記ＤＢサーバの前記記憶部に保存していないデータおよびそのデータの保存先となる他のＤＢサーバを抽出し、前記抽出した他のＤＢサーバにデータ交換要求を送信することにより、前記自身が保存していないデータを取得し、前記保存していたサーバ担当データ情報を前記新たなサーバ担当データ情報に更新するステップを実行すること、
を特徴とするデータ負荷分散配置方法。
【請求項４】
前記ＤＢサーバは、
自身が保存する前記データの増減と、前記クライアントからの前記データに対するアクセス数とを監視し、前記データそれぞれへの前記アクセス数を示すアクセス回数情報を生成するステップと、
所定間隔ごとに、前記記憶部に保存されている前記データの前記データキーと、前記アクセス回数情報とを、前記仮想サーバ配置装置に送信するステップとを、さらに実行し、
前記仮想サーバ配置装置は、
前記所定間隔ごとに前記ＤＢサーバそれぞれから取得した前記アクセス回数情報に含まれる、前記データキーの数であるデータ数と、前記データへのアクセス数とを用いて、前記所定間隔ごとの前記ＤＢサーバそれぞれの前記負荷を計算することにより、前記サーバＳ−の集合と、前記サーバＳ＋の集合とを生成するステップと、
前記サーバＳ−の集合のうち、前記ハッシュ空間上に前記仮想サーバが配置されている前記ＤＢサーバについて、前記絶対値が大きいＤＢサーバから順に、前記仮想サーバの担当領域を前記変更前に担当していた前記ＤＢサーバの担当領域に戻したときに、当該ＤＢサーバの負荷が当該ＤＢサーバのサーバ閾値を超えない場合に、前記仮想サーバの担当領域を前記ハッシュ空間上から取り除き、前記ＤＢサーバそれぞれの前記負荷を再計算し、前記ＤＢサーバごとに、前記負荷と前記サーバ閾値との差の絶対値を計算し直すことにより、前記サーバＳ−の集合と、前記サーバＳ＋の集合とを再度生成するステップとを、実行すること、
を特徴とする請求項３に記載のデータ負荷分散配置方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、大量のデータを分散して格納する分散データベースの技術分野において、データを格納する各サーバ間の負荷分散性を維持するための仮想サーバを用いたデータ負荷分散配置システムおよびデータ負荷分散配置方法に関する。
【背景技術】
【０００２】
データを複数のサーバ間に分散して格納する技術として、データとサーバとをハッシュ関数にかけてリング状のハッシュ空間に配置し、ハッシュ空間上のデータとサーバの位置関係から、各サーバが担当すべきデータを決定するコンシステントハッシュ法がある（非特許文献１参照）。図１９（ａ）に示すように、リング状のハッシュ空間にデータとサーバとが配置され、あるサーバ（例えば、「Ｓ１」）が配置された位置から、その１つ前に配置されたサーバ「Ｓ５」の配置位置の前までの領域（担当領域）に配置されたデータを、時計回りに、そのサーバ「Ｓ１」が格納する。このコンシステントハッシュ法によるデータの分散格納方法では、サーバ数の増減に対して格納先のサーバが変更となるデータが限られるため、拡張性に富むという特徴がある。
【０００３】
しかし、このコンシステントハッシュ法を用いたデータ配置方法では、ハッシュ空間におけるサーバとデータのハッシュ値の配置が一様にならず、各サーバの担当するデータ数に偏りが生じやすい。この問題を解決するため、一つのサーバから複数のハッシュ値を算出することにより、ハッシュ空間上に仮想サーバを配置する手法がある（非特許文献２参照）。例えば、図１９（ｂ）に示すように、ハッシュ空間上にサーバ「Ｓ３」の仮想サーバ「ＶＳ３」を、例えば、サーバ「Ｓ１」の担当領域にハッシュ値に基づき配置する。そして、この仮想サーバ「ＶＳ３」を設けることで、サーバ「Ｓ１」の担当領域の一部のデータを、仮想サーバ「ＶＳ３」の基のサーバ「Ｓ３」に格納させることで、サーバ「Ｓ１」の負荷を減らし、負荷分散性を向上させる。
この仮想サーバを用いた方法によれば、各サーバの仮想サーバをハッシュ空間上に増やすことで、担当領域を細かく分割し各サーバが格納するデータ数を、より均一にすることができる。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】D.Karger,E.Lehman, T.Leighton, R.Panigraphy, M.Levine, and D.Lewin, “Consistent hashing and random trees,” Proc. Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp.654-663, Elpaso, Texas, 1997
【非特許文献２】Rajesh Swaminathan,“Web Caching with Consistet Hashing,”University of Waterloo, pp.11-13, San Francisco, CA, 2009, ［online］、［平成23年4月22日検索］、インターネット＜http://rajesh.rapidtech.ca/publications/work_reports/report5.pdf＞
【発明の概要】
【発明が解決しようとする課題】
【０００５】
しかしながら、従来のコンシステントハッシュ法による仮想サーバの配置方法では、サーバにハッシュ関数を繰り返し適用するなどして複数のハッシュ値を算出し、仮想サーバをハッシュ空間に配置する。従って、適用するハッシュ関数に応じて負荷分散効果が異なると同時に、分散効果を高めるためには大量の仮想サーバをハッシュ空間上に配置する必要がある。その結果、仮想サーバ保持のための記述量が増加し、クライアントからデータの問い合わせを受けた際に、そのデータを格納している担当サーバの検索に要する時間が増加してしまう。
【０００６】
また、従来の仮想サーバを用いた負荷分散方法では、各サーバに設ける仮想サーバ数は同一に設定されることが多く、各サーバの性能を考慮したものではない。さらに、システム稼動後、時間経過に伴う担当データ数の増減や各データへの実アクセス数に応じて変動するサーバの実負荷の変化に対応できず、負荷分散効果を継続して維持するには問題があった。
【０００７】
このような背景に鑑みて本発明がなされたのであり、本発明は、仮想サーバの配置数を抑えた上で、サーバ間の負荷分散を実現し、システム全体としてスループットを向上させることができる、仮想サーバを用いたデータ負荷分散配置システムおよびデータ負荷分散配置方法を提供することを課題とする。
【課題を解決するための手段】
【０００８】
前記した課題を解決するため、請求項１に記載の発明は、相互に通信可能に接続される複数のＤＢサーバと、前記複数のＤＢサーバそれぞれと通信可能に接続される仮想サーバ配置装置とを備えるデータ負荷分散配置システムであって、前記ＤＢサーバが、（１）クライアントからの検索対象となるデータ、およびそのデータそれぞれに対応付けられるデータキー、（２）前記ＤＢサーバ自身のサーバ性能、並びに、（３）前記データそれぞれの保存先の前記ＤＢサーバを示すサーバ担当データ情報が保存される記憶部と、前記データキーおよび前記サーバ性能を、前記仮想サーバ配置装置に送信するデータ管理部と、前記仮想サーバ配置装置から、新たな前記サーバ担当データ情報を受信し、前記保存していたサーバ担当データ情報と比較することにより、自身の前記ＤＢサーバの前記記憶部に保存していないデータおよびそのデータの保存先となる他のＤＢサーバを抽出し、前記抽出した他のＤＢサーバにデータ交換要求を送信することにより、前記自身が保存していないデータを取得し、前記保存していたサーバ担当データ情報を前記新たなサーバ担当データ情報に更新するデータ交換部と、を備え、前記仮想サーバ配置装置が、前記データ負荷分散配置システム全体に求められる処理性能と、前記ＤＢサーバそれぞれに設定する負荷の閾値を示す負荷閾値定数が保存される記憶部と、前記ＤＢサーバそれぞれから取得した、前記サーバ性能と、前記負荷閾値定数とを用いて、前記ＤＢサーバそれぞれの負荷の閾値であるサーバ閾値を計算し、前記データ負荷分散配置システム全体に求められる処理性能と、前記ＤＢサーバそれぞれから取得した前記データキーの数の合計であるシステム全体のデータ数とに基づき、前記データへのアクセス回数が均等であると仮定して、前記ＤＢサーバそれぞれの負荷を計算し、前記ＤＢサーバごとに、前記負荷と前記サーバ閾値との差の絶対値を計算し、前記負荷が前記サーバ閾値以下のサーバＳ−の集合と、前記負荷が前記サーバ閾値を超えるサーバＳ＋の集合とを生成するサーバ負荷計算部と、前記ＤＢサーバおよび前記データそれぞれについて、所定のハッシュ関数を用いてハッシュ値を算出することにより、ハッシュ空間上に、前記データの保存を担当する前記ＤＢサーバの担当領域を設定し、前記サーバＳ＋の集合うち、前記負荷と前記サーバ閾値との差の絶対値が大きいＤＢサーバから順に、前記ハッシュ空間上の前記サーバＳ＋の担当領域において、担当できるデータ数が自身のＤＢサーバのサーバ閾値を超える超過分に対して、前記サーバＳ−の集合のうち、前記絶対値が大きいＤＢサーバから順に仮想サーバを配置し、前記超過分のデータの前記ハッシュ空間上での担当領域を前記仮想サーバに変更し、前記変更したハッシュ空間上での担当領域に基づき、前記ＤＢサーバそれぞれが担当するデータの保存先を示す前記新たなサーバ担当データ情報を生成し、前記生成した新たなサーバ担当データ情報を、前記ＤＢサーバそれぞれに送信する配置処理部と、を備えることを特徴とするデータ負荷分散配置システムとした。
【０００９】
また、請求項３に記載の発明は、相互に通信可能に接続される複数のＤＢサーバと、前記複数のＤＢサーバそれぞれと通信可能に接続される仮想サーバ配置装置とを備えるデータ負荷分散配置システムのデータ負荷分散配置方法であって、前記ＤＢサーバが、（１）クライアントからの検索対象となるデータ、およびそのデータそれぞれに対応付けられるデータキー、（２）前記ＤＢサーバ自身のサーバ性能、並びに、（３）前記データそれぞれの保存先の前記ＤＢサーバを示すサーバ担当データ情報が保存されている記憶部を備えており、前記データキーおよび前記サーバ性能を、前記仮想サーバ配置装置に送信するステップを実行し、前記仮想サーバ配置装置が、前記データ負荷分散配置システム全体に求められる処理性能と、前記ＤＢサーバそれぞれに設定する負荷の閾値を示す負荷閾値定数が保存されている記憶部を備えており、前記ＤＢサーバそれぞれから取得した、前記サーバ性能と、前記負荷閾値定数とを用いて、前記ＤＢサーバそれぞれの負荷の閾値であるサーバ閾値を計算し、前記データ負荷分散配置システム全体に求められる処理性能と、前記ＤＢサーバそれぞれから取得した前記データキーの数の合計であるシステム全体のデータ数とに基づき、前記データへのアクセス回数が均等であると仮定して、前記ＤＢサーバそれぞれの負荷を計算し、前記ＤＢサーバごとに、前記負荷と前記サーバ閾値との差の絶対値を計算し、前記負荷が前記サーバ閾値以下のサーバＳ−の集合と、前記負荷が前記サーバ閾値を超えるサーバＳ＋の集合とを生成するステップと、前記ＤＢサーバおよび前記データそれぞれについて、所定のハッシュ関数を用いてハッシュ値を算出することにより、ハッシュ空間上に、前記データの保存を担当する前記ＤＢサーバの担当領域を設定し、前記サーバＳ＋の集合うち、前記負荷と前記サーバ閾値との差の絶対値が大きいＤＢサーバから順に、前記ハッシュ空間上の前記サーバＳ＋の担当領域において、担当できるデータ数が自身のＤＢサーバのサーバ閾値を超える超過分に対して、前記サーバＳ−の集合のうち、前記絶対値が大きいＤＢサーバから順に仮想サーバを配置し、前記超過分のデータの前記ハッシュ空間上での担当領域を前記仮想サーバに変更し、前記変更したハッシュ空間上での担当領域に基づき、前記ＤＢサーバそれぞれが担当するデータの保存先を示す新たなサーバ担当データ情報を生成し、前記生成した新たなサーバ担当データ情報を、前記ＤＢサーバそれぞれに送信するステップと、を実行し、前記ＤＢサーバが、前記仮想サーバ配置装置から、前記新たなサーバ担当データ情報を受信し、前記保存していたサーバ担当データ情報と比較することにより、自身の前記ＤＢサーバの前記記憶部に保存していないデータおよびそのデータの保存先となる他のＤＢサーバを抽出し、前記抽出した他のＤＢサーバにデータ交換要求を送信することにより、前記自身が保存していないデータを取得し、前記保存していたサーバ担当データ情報を前記新たなサーバ担当データ情報に更新するステップを実行することを特徴とするデータ負荷分散配置方法とした。
【００１０】
このようにすることで、本実施形態に係るデータ負荷分散配置システムおよびデータ負荷分散配置方法によれば、各ＤＢ（DataBase）サーバのサーバ性能を考慮した上でサーバ閾値を計算し、ハッシュ空間上で、負荷がサーバ閾値を超えるサーバＳ＋のＤＢサーバの負荷の超過分の領域を、負荷がサーバ閾値以下のサーバＳ−のＤＢサーバが、仮想サーバを設けることにより、その領域のデータを、サーバＳ−のＤＢサーバが担当する。よって、ＤＢサーバ間の負荷分散を実現し、さらに、各サーバの担当領域に配置する仮想サーバの数が同一に設定される従来技術に比べ、仮想サーバの数を減らすことができる。また、仮想サーバを大量に配置する必要がなくなるため、仮想サーバ保持のための記述量の増加を抑え、クライアントからデータの問い合わせを受けた際に、そのデータを格納している担当サーバの検索に要する時間の増加を抑えることができる。よって、システム全体としてのスループットを向上させることができる。
【００１１】
請求項２に記載の発明は、前記ＤＢサーバが、自身が保存する前記データの増減と、前記クライアントからの前記データに対するアクセス数とを監視し、前記データそれぞれへの前記アクセス数を示すアクセス回数情報を生成するアクセス監視部を、さらに備え、前記データ管理部が、所定間隔ごとに、前記記憶部に保存されている前記データの前記データキーと、前記アクセス回数情報とを、前記仮想サーバ配置装置に送信し、前記仮想サーバ配置装置が、仮想サーバ再配置計算部を、さらに備えており、前記サーバ負荷計算部が、前記所定間隔ごとに前記ＤＢサーバそれぞれから取得した前記アクセス回数情報に含まれる、前記データキーの数であるデータ数と、前記データへのアクセス数とを用いて、前記所定間隔ごとの前記ＤＢサーバそれぞれの前記負荷を計算することにより、前記サーバＳ−の集合と、前記サーバＳ＋の集合とを生成し、前記仮想サーバ再配置計算部が、前記サーバＳ−の集合のうち、前記ハッシュ空間上に前記仮想サーバが配置されている前記ＤＢサーバについて、前記絶対値が大きいＤＢサーバから順に、前記仮想サーバの担当領域を前記変更前に担当していた前記ＤＢサーバの担当領域に戻したときに、当該ＤＢサーバの負荷が当該ＤＢサーバのサーバ閾値を超えない場合に、前記仮想サーバの担当領域を前記ハッシュ空間上から取り除き、前記ＤＢサーバそれぞれの前記負荷を再計算し、前記ＤＢサーバごとに、前記負荷と前記サーバ閾値との差の絶対値を計算し直すことにより、前記サーバＳ−の集合と、前記サーバＳ＋の集合とを再度生成して、前記配置処理部に引き渡すこと、を特徴とする請求項１に記載のデータ負荷分散配置システムとした。
【００１２】
また、請求項４に記載の発明は、前記ＤＢサーバが、自身が保存する前記データの増減と、前記クライアントからの前記データに対するアクセス数とを監視し、前記データそれぞれへの前記アクセス数を示すアクセス回数情報を生成するステップと、所定間隔ごとに、前記記憶部に保存されている前記データの前記データキーと、前記アクセス回数情報とを、前記仮想サーバ配置装置に送信するステップとを、さらに実行し、前記仮想サーバ配置装置が、前記所定間隔ごとに前記ＤＢサーバそれぞれから取得した前記アクセス回数情報に含まれる、前記データキーの数であるデータ数と、前記データへのアクセス数とを用いて、前記所定間隔ごとの前記ＤＢサーバそれぞれの前記負荷を計算することにより、前記サーバＳ−の集合と、前記サーバＳ＋の集合とを生成するステップと、前記サーバＳ−の集合のうち、前記ハッシュ空間上に前記仮想サーバが配置されている前記ＤＢサーバについて、前記絶対値が大きいＤＢサーバから順に、前記仮想サーバの担当領域を前記変更前に担当していた前記ＤＢサーバの担当領域に戻したときに、当該ＤＢサーバの負荷が当該ＤＢサーバのサーバ閾値を超えない場合に、前記仮想サーバの担当領域を前記ハッシュ空間上から取り除き、前記ＤＢサーバそれぞれの前記負荷を再計算し、前記ＤＢサーバごとに、前記負荷と前記サーバ閾値との差の絶対値を計算し直すことにより、前記サーバＳ−の集合と、前記サーバＳ＋の集合とを再度生成するステップとを、実行すること、を特徴とする請求項３に記載のデータ負荷分散配置方法とした。
【００１３】
このようにすることで、本実施形態に係るデータ負荷分散配置システムおよびデータ負荷分散配置方法によれば、所定間隔ごとに、負荷がサーバ閾値以下のサーバＳ−に含まれることになったＤＢサーバのハッシュ空間上での担当領域に、仮想サーバが配置されている場合に、その仮想サーバの担当領域を、元のＤＢサーバの担当領域に戻すことができる。そして、負荷とサーバ閾値との差の絶対値を計算し直すことにより、負荷がサーバ閾値以下のサーバＳ−の集合と、負荷がサーバ閾値を超えるサーバＳ＋の集合とを生成して、再度、ハッシュ空間上での仮想サーバの配置を計算する。これにより、各ＤＢサーバの負荷を均一化させるとともに、ハッシュ空間上に配置する仮想サーバの数を減らすことができる。
【発明の効果】
【００１４】
本発明によれば、仮想サーバの配置数を抑えた上で、サーバ間の負荷分散を実現し、システム全体としてスループットを向上させる、仮想サーバを用いたデータ負荷分散配置システムおよびデータ負荷分散配置方法を提供することができる。
【図面の簡単な説明】
【００１５】
【図１】本実施形態に係るデータ負荷分散配置システムの構成例を示すブロック図である。
【図２】本実施形態に係る仮想サーバ配置装置による、ハッシュ空間上での仮想サーバの初期配置の概要を説明するための図である。
【図３】本実施形態に係る仮想サーバ配置装置による、ハッシュ空間上での仮想サーバの初期配置の概要を説明するための図である。
【図４】本実施形態に係る仮想サーバ配置装置による、ハッシュ空間上での仮想サーバの初期配置の概要を説明するための図である。
【図５】本実施形態に係る仮想サーバ配置装置による、ハッシュ空間上での仮想サーバの初期配置の概要を説明するための図である。
【図６】本実施形態に係るサーバ担当データ情報のデータ構成の一例を示す図である。
【図７】本実施形態に係るアクセス回数情報のデータ構成の一例を示す図である。
【図８】本実施形態に係るデータ負荷分散配置処理（仮想サーバの初期配置）の全体の処理の流れを示すシーケンス図である。
【図９】本実施形態に係る仮想サーバ配置装置の仮想サーバ配置処理の流れを示すフローチャートである。
【図１０】本実施形態に係る仮想サーバ配置装置の仮想サーバ配置処理の流れを示すフローチャートである。
【図１１】本実施形態に係るデータ負荷分散配置処理（仮想サーバの再配置）の全体の処理の流れを示すシーケンス図である。
【図１２】本実施形態に係る仮想サーバ配置装置による仮想サーバ再配置計算の概要を説明するための図である。
【図１３】本実施形態に係る仮想サーバ配置装置による仮想サーバ再配置計算の概要を説明するための図である。
【図１４】本実施形態に係る仮想サーバ配置装置による仮想サーバ再配置計算の概要を説明するための図である。
【図１５】本実施形態に係る仮想サーバ配置装置による仮想サーバ再配置計算の概要を説明するための図である。
【図１６】本実施形態に係る仮想サーバ配置装置による仮想サーバ再配置計算の概要を説明するための図である。
【図１７】本実施形態に係る仮想サーバ配置装置による仮想サーバ再配置計算の概要を説明するための図である。
【図１８】本実施形態に係る仮想サーバ配置装置の仮想サーバ再配置計算の処理の流れを示すフローチャートである。
【図１９】従来技術におけるコンシステントハッシュ法による仮想サーバの配置方法を説明するための図である。
【発明を実施するための形態】
【００１６】
次に、本発明を実施するための形態（以下、「実施形態」という）について、適宜図面を参照しながら詳細に説明する。
【００１７】
本実施形態に係る仮想サーバを用いたデータ負荷分散配置システム１およびデータ負荷分散配置方法では、（１）各ＤＢサーバ２０のサーバ性能を考慮した仮想サーバの初期配置によるデータ負荷分散配置処理と、（２）システム稼動後の時間経過に伴うデータ数やデータへのアクセス回数の増減に対応した動的な仮想サーバの再配置と、を実現する。まず、本実施形態に係るデータ負荷分散配置システム１の概要について説明する。
【００１８】
図１は、本実施形態に係るデータ負荷分散配置システム１の構成を示すブロック図である。
図１に示すように、本実施形態に係るデータ負荷分散配置システム１は、各データを保存する複数のＤＢサーバ２０と、ハッシュ空間上での仮想サーバの配置による各データの保存先となるＤＢサーバ２０の決定や、そのデータの保存先の変更等を管理する仮想サーバ配置装置１０とが、通信可能に接続されて構成される。この仮想サーバ配置装置１０と各ＤＢサーバ２０それぞれとが通信可能に接続されるとともに、各ＤＢサーバ２０同士も、通信可能に接続される。
【００１９】
また、仮想サーバ配置装置１０は、管理者サーバ５と通信可能に接続されており、仮想サーバをハッシュ空間上に配置するために必要となる、設定情報（後記参照）を管理者サーバ５から受信する。そして、仮想サーバ配置装置１０は、仮想サーバの配置処理の結果、ＤＢサーバ２０が不足する場合には、リソース不足通知を管理者サーバ５へ送信する。
【００２０】
ＤＢサーバ２０は、クライアント６とも通信可能に接続されている。ＤＢサーバ２０は、クライアント６からのデータ要求を受け付けると、そのデータを保存するＤＢサーバ２０を、後記する記憶部２４内のサーバ担当データ情報１００（図６参照）を参照して検索し、その検索結果を担当サーバ通知として、クライアント６に送信する。そして、クライアント６は、その担当サーバ通知に示されるデータの保存先のＤＢサーバ２０に対して、データ取得要求を送信し、そのデータを取得する。
【００２１】
次に、本実施形態に係るデータ負荷分散配置システム１の仮想サーバの初期配置の概要について説明する。その後に、データ負荷分散配置システム１の具体的な構成と、データ負荷分散配置方法の具体的な処理の流れについて説明する。
【００２２】
（仮想サーバの初期配置の概要）
まず、本実施形態に係るデータ負荷分散配置システム１が仮想サーバの初期配置を行う際の前提となる条件および処理の概要について説明する。
【００２３】
本実施形態に係るデータ負荷分散配置システム１では、初期状態として、Ｎ台のＤＢサーバ（物理サーバ）２０にＨ個のデータが保存されているものとする。この場合に、初期状態でのシステム性能要件は、以下の（Ａ）（Ｂ）ようになる。
【００２４】
（Ａ）各サーバＳｍにかかる負荷Ｗｍは、そのサーバ性能Ｔｍ以下である。
【００２５】
【数１】
0005540269.tif 000002
【００２６】
（Ｂ）各サーバＳｍにかかる負荷Ｗｍの合計が、システム全体に求める処理性能Ｒ以下である。
【００２７】
【数２】
0005540269.tif 000003
【００２８】
この（Ａ）および（Ｂ）のシステム性能条件を満たす限り、クライアント６は、正常なアクセス応答時間内でシステム内のデータへのアクセスが可能である。
【００２９】
本実施形態に係る仮想サーバの初期配置では、システム全体に対して１秒当たりのシステム最大性能であるＲ回のアクセスがあり、各データへのアクセス回数は均等であるとして、１つのデータ当たりＲ／Ｈ回のアクセスがあると仮定する。
【００３０】
そして、システム性能条件（Ａ）および（Ｂ）を満たしながら、さらに次のシステム性能条件（Ｃ）を満たすように、仮想サーバを配置する。
【００３１】
（Ｃ）各サーバＳｍにかかる負荷Ｗｍは、そのサーバ閾値αｍ以下である。
【００３２】
【数３】
0005540269.tif 000004
【００３３】
なお、このサーバ閾値αｍは、以下の（式１）により計算される。
【００３４】
【数４】
0005540269.tif 000005
【００３５】
ここで、ｃは、負荷閾値定数であり、例えば、サーバ性能Ｔｍの７割をサーバ閾値αｍとして設定する場合には、システムの管理者等により「0.7」が、負荷閾値定数ｃとして設定される。
また、負荷Ｗｍは、以下の（式２）により計算される。
【００３６】
【数５】
0005540269.tif 000006
【００３７】
ここで、Ｄｍは、サーバＳｍに保存されるデータ数であり、αＳｍ(i)は、サーバＳｍが保存するデータｄＳｍ(i)へのアクセス回数である。
【００３８】
本実施形態に係る仮想サーバ配置装置１０は、ハッシュ空間における各サーバＳｍ（ＤＢサーバ２０）の担当領域に、仮想サーバを配置し、サーバＳｍ（物理サーバ）の担当領域の一部を仮想サーバに担当させる。これにより、そのサーバＳｍ（物理サーバ）の担当データ（ＤＢサーバ２０が保存するデータ）の一部を、仮想サーバの基となる他の物理サーバ（ＤＢサーバ２０）に変更すること、つまり、他のＤＢサーバ２０にそのデータを移して保存させることが可能となる。そして、仮想サーバ配置装置１０は、この仮想サーバを用いて、ハッシュ空間における負荷の大きい物理サーバ（ＤＢサーバ２０）の担当領域内に、負荷の小さい物理サーバ（ＤＢサーバ２０）の仮想サーバを割り当てることで、システム全体の負荷分散を行う。なお、本実施形態において、ＤＢサーバ２０をハッシュ空間に配置した場合に、ＤＢサーバ２０を、仮想サーバに対応させる意味において物理サーバということがある。
【００３９】
仮想サーバ配置装置１０は、各ＤＢサーバ２０からサーバ性能Ｔｍを取得し、管理者サーバ５から負荷閾値定数ｃを取得するなどして、（式１）を用いて、サーバ閾値αｍを計算する。そして、仮想サーバ配置装置１０は、負荷Ｗｍがかかっている物理サーバＳｍに対し、Ｏｍを以下のように定義する。
【００４０】
【数６】
0005540269.tif 000007
【００４１】
ここで、Ｏｍは、物理サーバＳｍの負荷Ｗｍとサーバ閾値αｍとの差の絶対値である。
【００４２】
そして、仮想サーバ配置装置１０は、物理サーバの集合Ｓを、以下のようにＳ−，Ｓ＋の２つの集合に分割する。
【００４３】
ここで、負荷がサーバ閾値以下の物理サーバの集合を、Ｓ−とする。そして、Ｓ−に含まれる物理サーバＳｍをＯｍの大きい順に並べたものを以下のように記述する。
【００４４】
【数７】
0005540269.tif 000008
【００４５】
一方、負荷がサーバ閾値を超える物理サーバの集合を、Ｓ＋とする。そして、Ｓ＋に含まれる物理サーバＳｍをＯｍの大きい順に並べたものを以下のように記述する。
【００４６】
【数８】
0005540269.tif 000009
【００４７】
また、負荷がサーバ閾値以下のサーバＳ−の絶対値Ｏ−kj、負荷がサーバ閾値を超えるサーバＳ＋の絶対値Ｏ＋liを、以下のように定義する。
【００４８】
【数９】
0005540269.tif 000010
【００４９】
次に、仮想サーバ配置装置１０による、ハッシュ空間上での仮想サーバの初期配置の概要について説明する。図２〜図５は、本実施形態に係る仮想サーバ配置装置１０による、ハッシュ空間上での仮想サーバの初期配置の概要を説明するための図である。
【００５０】
ここでは、図２（ｂ）に示すように、仮想サーバ配置装置１０により、負荷がサーバ閾値以下のサーバＳ−が、Ｓ３，Ｓ４，Ｓ５のように、負荷とサーバ閾値との差の絶対値Ｏ−の大きい順に並べられ、負荷がサーバ閾値を超えるサーバＳ＋が、Ｓ１，Ｓ２のように、負荷とサーバ閾値との差の絶対値Ｏ＋の大きい順に並べられているものとする。そして、この各サーバＳ１〜Ｓ５とその担当データとが、仮想サーバ配置装置１０により、図２（ａ）に示すように、ハッシュ空間上に配置されるとする。
【００５１】
図２（ａ）に示すような状態から、仮想サーバ配置装置１０は、負荷とサーバ閾値との差の絶対値が大きい順に、負荷がサーバ閾値を超えるサーバＳ＋の負荷の超過分の領域に、負荷がサーバ閾値以下のサーバＳ−の仮想サーバを配置することで、負荷がサーバ閾値を超えるサーバＳ＋の負荷の超過分のデータの担当を、負荷がサーバ閾値以下のサーバＳ−に変更する。
【００５２】
具体的には、図３に示すように、まず、負荷がサーバ閾値を超えるサーバＳ＋のうち、絶対値Ｏ＋が一番大きいＳ１のサーバの負荷の超過分の領域に、負荷がサーバ閾値以下のサーバＳ−のうち、絶対値Ｏ−が一番大きいサーバＳ３の仮想サーバＶＳ３を配置し、その領域のデータをサーバＳ３が担当する。
【００５３】
次に、図４に示すように、サーバＳ１の残りの負荷の超過分の領域に、負荷がサーバ閾値以下の次のサーバであるサーバＳ４の仮想サーバＶＳ４を配置し、その領域のデータをサーバＳ４が担当する。これによって、サーバＳ１の負荷の超過分が解消される。続いて、負荷がサーバ閾値を超える次のサーバであるサーバＳ２の負荷の超過分の領域に、負荷がサーバ閾値以下のサーバＳ４の残りの余剰分を、仮想サーバＶＳ４として配置し、その領域のデータをサーバＳ４が担当する。
【００５４】
続いて、図５に示すように、サーバＳ２の残りの負荷の超過分の領域に、負荷がサーバ閾値以下の次のサーバであるサーバＳ５の仮想サーバＶＳ５を配置し、その領域のデータをサーバＳ５が担当する。これによって、サーバＳ２の負荷の超過分が解消される。なお、仮想サーバ配置装置１０は、この仮想サーバの配置処理の結果、負荷がサーバ閾値以下のサーバＳ−が不足する場合には、リソース不足通知を管理者サーバ５へ送信する。
【００５５】
本実施形態に係る仮想サーバ配置装置１０は、このように、ハッシュ空間上で、負荷がサーバ閾値を超えるサーバＳ＋の負荷の超過分の領域を、負荷がサーバ閾値以下のサーバＳ−が、仮想サーバを設けることにより、その領域のデータを、負荷がサーバ閾値以下のサーバＳ−のサーバが担当する。よって、サーバ間の負荷分散を実現し、仮想サーバの数を減らすことができる。
【００５６】
（データ負荷分散配置システムの構成）
次に、本実施形態に係るデータ負荷分散配置システム１を構成するＤＢサーバ２０および仮想サーバ配置装置１０の構成例について詳細に説明する。
【００５７】
＜ＤＢサーバの構成＞
まず、本実施形態に係るＤＢサーバ２０の構成例について、図１を参照して説明する。
ＤＢサーバ２０は、データを自身が備える記憶手段（後記する記憶部２４）に保存しておき、クライアント６からのデータ取得要求に応じて、その要求のあったデータをクライアント６へ送信する。また、ＤＢサーバ２０は、仮想サーバ配置装置１０から、各データの保存先となるＤＢサーバ２０を示すサーバ担当データ情報１００（詳細は後記する図６参照）を受信すると、そのサーバ担当データ情報１００を参照して、自身が担当すべきデータを記憶する他のＤＢサーバ２０から、そのデータを取得し保存する処理を行う。
このＤＢサーバ２０は、図１に示すように、処理部２１と、通信部２２と、メモリ部２３と、記憶部２４とを備える。
【００５８】
通信部２２は、クライアント６、自身以外の他のＤＢサーバ２０および仮想サーバ配置装置１０との間の通信を司る、通信インタフェースにより構成される。
【００５９】
処理部２１は、ＤＢサーバ２０全体の制御を司り、情報受信部２１１と、データ管理部２１２と、アクセス監視部２１４と、データ交換部２１５と、情報送信部２１６とを含んで構成される。なお、この処理部２１は、例えば、ＤＢサーバ２０の記憶部２４に格納されたプログラムをＣＰＵ（Central Processing Unit）が、メモリ部２３であるＲＡＭ（Random Access Memory）に展開し実行することで実現される。
【００６０】
情報受信部２１１は、通信部２２を介して、クライアント６からのデータ要求や、仮想サーバ配置装置１０からのサーバ担当データ情報１００（図６参照）、他のＤＢサーバ２０から送信されたデータ等を取得する。
【００６１】
データ管理部２１２は、記憶部２４に記憶されたデータの管理全般を司る。具体的には、データ管理部２１２は、クライアント６からのデータ要求を、情報受信部２１１を介して受け付けると、記憶部２４内のサーバ担当データ情報１００を参照し、そのデータを記憶するＤＢサーバ２０を検索する。そして、その検索結果を、担当サーバ通知として、情報送信部２１６を介して、クライアント６に送信する。
【００６２】
図６は、本実施形態に係るサーバ担当データ情報１００のデータ構成の一例を示す図である。
図６に示すように、サーバ担当データ情報１００は、各ＤＢサーバ（サーバＳｍ）２０ごとに、そのサーバＳｍが保存する担当データが記憶される。例えば、サーバＳ１は、「ｄ１〜ｄ３，ｄ６」のデータを保存することを示している。なお、この担当データには、各データのデータキーが「ｄ１」「ｄ２」…、等として記憶される。なお、このサーバ担当データ情報１００には、仮想サーバ配置装置１０による仮想サーバの初期配置の処理の初期値として、現時点においてＤＢサーバ２０ごとに保存される各データの情報が記憶されているものとする。
【００６３】
また、データ管理部２１２は、図１に示すように、ハッシュ値計算部２１３を備えている。そして、データ管理部２１２は、通信部２２や、不図示の入力部を介して、新たなデータを取得すると、そのデータのデータキーに対して、ハッシュ値計算部２１３が、所定のハッシュ関数によりハッシュ値を計算する。データ管理部２１２は、そのデータのデータキーと、そのハッシュ値と、そのデータ（データ値）とを対応付けて、記憶部２４内の後記するデータ格納部２００に記憶する。
【００６４】
そして、データ管理部２１２は、クライアント６から自身が保存するデータに対するデータ取得要求を受け付けると、そのデータ取得要求に付されたデータキーについて、ハッシュ値計算部２１３がハッシュ値を計算する。次に、データ管理部２１２は、そのデータキーのハッシュ値を用いて、データ格納部２００に記憶されたデータ（データ値）を検索し、検索したデータを、情報送信部２１６を介して、クライアント６へ送信する。
【００６５】
また、データ管理部２１２は、仮想サーバ配置装置１０による仮想サーバの初期配置の処理に際して、記憶部２４内のデータ格納部２００を参照し、自身が保存するすべてのデータのデータキーと、予め記憶部２４等に保存されている自身のサーバ性能Ｔｍとを、自身のＤＢサーバ２０に固有な番号と共に、情報送信部２１６を介して仮想サーバ配置装置１０に送信する。なお、自身のＤＢサーバ２０に固有な番号とは、例えば、そのＤＢサーバ２０のＩＰアドレス等であるが、これに限定されず、他のＤＢサーバ２０等と識別可能な番号であればよい。
【００６６】
また、データ管理部２１２は、システム稼働後、所定間隔Ｚごとに、自身がその時点で保存するすべてのデータのデータキーと、アクセス監視部２１４が生成したアクセス回数情報３００（後記する図７参照）とを、自身のＤＢサーバ２０に固有な番号と共に、情報送信部２１６を介して仮想サーバ配置装置１０に送信する。
さらに、データ管理部２１２は、仮想サーバ配置装置１０から、新たなサーバ担当データ情報１００を取得すると、記憶部２４内のサーバ担当データ情報１００を更新する処理を行う。
【００６７】
アクセス監視部２１４は、データ管理部２１２を監視し、クライアント６からのデータ取得要求を受け付けるごとに、データ格納部２００に記憶された各データへのアクセス回数をカウントし、その結果を、アクセス回数情報３００として記憶する。
【００６８】
図７は、本実施形態に係るアクセス回数情報３００のデータ構成の一例を示す図である。
図７に示すように、アクセス回数情報３００には、各ＤＢサーバ２０自身が記憶するデータごとに、クライアント６からアクセスが何回あったかを示す情報であり、各データのデータキーと、そのデータのアクセス回数が記憶される。なお、このアクセス回数情報３００は、データ管理部２１２により、仮想サーバ配置装置１０へ所定間隔Ｚごとに送信される。
【００６９】
データ交換部２１５は、データ管理部２１２が仮想サーバ配置装置１０から新たなサーバ担当データ情報１００を受信したことを契機として、その新たなサーバ担当データ情報１００と記憶部２４に保存していたサーバ担当データ情報１００と比較することにより、自身が保存していないデータおよびそのデータの保存先となる他のＤＢサーバ２０を抽出する。そして、データ交換部２１５は、その抽出した自身が担当すべきデータを記憶している他のＤＢサーバ２０に対して、データ交換要求を送信することにより、そのデータの送信を依頼し、担当すべきデータを取得する。続いて、データ交換部２１５は、記憶部２４に保存していたサーバ担当データ情報１００を、データ管理部２１２を介して、受信した新たなサーバ担当データ情報１００に更新させる。
【００７０】
情報送信部２１６は、通信部２２を介して、クライアント６への担当サーバ通知や、仮想サーバ配置装置１０への自身が保存するデータに関する情報、他のＤＢサーバ２０へのデータ交換要求等を送信する。
【００７１】
次に、記憶部２４は、ハードディスクやフラッシュメモリ等の記憶装置からなり、サーバ担当データ情報１００、データ格納部２００、アクセス回数情報３００を記憶している。
【００７２】
メモリ部２３は、ＲＡＭ等の一次記憶装置からなり、処理部２１によるデータ処理に必要な情報を一次的に記憶している。
【００７３】
＜仮想サーバ配置装置の構成＞
次に、本実施形態に係る仮想サーバ配置装置１０の構成について、図１を参照して説明する。
仮想サーバ配置装置１０は、データを複数のＤＢサーバ２０に分散して保存させるために、データ（データキー）とＤＢサーバ（固有の番号）２０とをハッシュ関数にかけてリング状のハッシュ空間に配置する。そして、仮想サーバ配置装置１０は、各ＤＢサーバ２０のサーバ性能Ｔｍや、時間経過に伴うサーバ負荷の変動を考慮した上で、仮想サーバをハッシュ空間上に配置する。仮想サーバ配置装置１０は、仮想サーバの配置により決定した各ＤＢサーバ２０が保存すべきデータの情報（サーバ担当データ情報１００）を、各ＤＢサーバ２０それぞれに送信する。
【００７４】
この仮想サーバ配置装置１０は、図１に示すように、制御部１１と、通信部１２と、メモリ部１３と、記憶部１４とを備える。
【００７５】
通信部１２は、各ＤＢサーバ２０および管理者サーバ５との間の通信を司る、通信インタフェースにより構成される。
【００７６】
制御部１１は、仮想サーバ配置装置１０全体の制御を司り、情報受信部１１１と、サーバ負荷計算部１１２と、配置処理部１１３と、仮想サーバ再配置計算部１１５と、情報送信部１１６とを含んで構成される。なお、この制御部１１は、例えば、仮想サーバ配置装置１０の記憶部１４に格納されたプログラムをＣＰＵが、メモリ部１３であるＲＡＭに展開し実行することで実現される。
【００７７】
情報受信部１１１は、通信部１２を介して、ＤＢサーバ２０それぞれから、各ＤＢサーバ２０に記憶されたデータ等に関する情報を受信したり、管理者サーバ５から、仮想サーバの配置に必要となる設定情報等を取得する。
【００７８】
サーバ負荷計算部１１２は、各ＤＢサーバ２０のサーバ閾値αｍおよび負荷Ｗｍを計算する。
具体的には、サーバ負荷計算部１１２は、仮想サーバの初期配置の処理において、管理者サーバ５等から、システム全体に求める処理性能Ｒおよび負荷閾値定数ｃを取得し、ＤＢサーバ２０から各ＤＢサーバ２０のサーバ性能Ｔｍおよびデータキーを取得する。そして、サーバ負荷計算部１１２は、各ＤＢサーバ２０のサーバ性能Ｔｍと負荷閾値定数ｃにより、（式１）を用いて、各ＤＢサーバ２０のサーバ閾値αｍを計算する。また、サーバ負荷計算部１１２は、各ＤＢサーバ２０から取得したデータキーの数を合計し、システム全体のデータ数Ｈを計算する。そして、各データへのアクセス回数が均等であると仮定し、１つのデータへのアクセス回数をＲ／Ｈ回として、（式２）を用いて、各ＤＢサーバ２０の負荷Ｗｍを計算する。
【００７９】
そして、サーバ負荷計算部１１２は、計算したＤＢサーバ２０ごとの負荷Ｗｍとサーバ閾値αｍとを比較し、負荷がサーバ閾値以下のサーバＳ−の集合と、負荷がサーバ閾値を超えるサーバＳ＋の集合とを生成して、その集合ごとに、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順にサーバを整列する処理を行う。
【００８０】
また、サーバ負荷計算部１１２は、仮想サーバの再配置の処理において、所定間隔Ｚごとに各ＤＢサーバ２０が記憶するデータのデータキーと、そのデータに対するアクセス回数を記録したアクセス回数情報３００を、各ＤＢサーバ２０から取得する。そして、（式２）を用いて、各ＤＢサーバ２０の負荷Ｗｍを計算する。
また、サーバ負荷計算部１１２は、計算した所定間隔Ｚ経過後のＤＢサーバ２０ごとの負荷Ｗｍとサーバ閾値αｍとを比較し、負荷がサーバ閾値以下のサーバＳ−の集合と、負荷がサーバ閾値を超えるサーバＳ＋の集合とを生成して、その集合ごとに、所定間隔Ｚ経過時点における、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順にサーバを整列する処理を行う。
【００８１】
次に、配置処理部１１３は、ハッシュ値計算部１１４を備えており、コンシステントハッシュ法（時計回り方式）を用いて、各ＤＢサーバ（固有の番号）２０およびデータ（データキー）のハッシュ値を計算し、ハッシュ空間上に各ＤＢサーバ２０およびデータを配置する。
そして、配置処理部１１３は、負荷がサーバ閾値を超えるサーバＳ＋のうち、絶対値Ｏ＋が大きいＤＢサーバ２０から順に、ハッシュ空間上の担当領域の超過分に対して、負荷がサーバ閾値以下のサーバＳ−のうち、絶対値Ｏ−が大きいＤＢサーバ２０から順に仮想サーバを配置することで、負荷がサーバ閾値を超えるサーバＳ＋の超過分を解消する処理（仮想サーバ配置処理）を行う。なお、この仮想サーバ配置処理の詳細については、図９および図１０を用いて説明する。  
【００８２】
配置処理部１１３は、負荷がサーバ閾値を超えるサーバＳ＋のすべての超過分について、仮想サーバを配置することにより決定した、各ＤＢサーバ２０が担当するデータについての新たなサーバ担当データ情報１００を生成する。そして、配置処理部１１３は、情報送信部１１６を介して、各ＤＢサーバ２０それぞれに、新たなサーバ担当データ情報１００を送信する。
【００８３】
また、配置処理部１１３は、仮想サーバを配置しても、負荷がサーバ閾値を超えるサーバＳ＋の超過分を解消できない場合には、情報送信部１１６を介して、管理者サーバ５に、ＤＢサーバ２０のリソースが足りないことを示すリソース不足通知を送信する。
【００８４】
次に、仮想サーバ再配置計算部１１５は、仮想サーバの再配置の処理において、サーバ負荷計算部１１２が、所定間隔Ｚ経過時点における、負荷がサーバ閾値以下のサーバＳ−と、負荷がサーバ閾値を超えるサーバＳ＋とについて、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順にサーバを整列する処理が行ったことを契機として、所定間隔Ｚ経過時点において、負荷がサーバ閾値以下のサーバＳ−に、ハッシュ空間上で仮想サーバが配置されていた場合に、その仮想サーバを取り除く処理（仮想サーバ再配置計算）を行う。つまり、元々そのＤＢサーバ２０自身が担当すべきハッシュ空間の担当領域を、そのＤＢサーバ２０の負荷Ｗｍがサーバ閾値αｍより大きいため、他のＤＢサーバ２０が仮想サーバを配置することにより、データの保存先を変更してもらっていたものを、時間の経過により、サーバの負荷が変化し、負荷に余裕が生じたため、仮想サーバが担当していたデータ分を、元々のＤＢサーバ２０の担当領域に戻す処理を行う。なお、この仮想サーバ再配置計算の詳細は、後記する図１２〜図１８を参照して説明する。
【００８５】
情報送信部１１６は、通信部１２を介して、各ＤＢサーバ２０それぞれに、配置処理部１１３が生成したサーバ担当データ情報１００を送信する。また、情報送信部１１６は、管理者サーバ５に対し、リソース不足通知を送信する。
【００８６】
次に、記憶部１４は、ハードディスクやフラッシュメモリ等の記憶装置からなり、配置処理部１１３が生成したサーバ担当データ情報１００を記憶している。
【００８７】
メモリ部１３は、ＲＡＭ等の一次記憶装置からなり、制御部１１によるデータ処理に必要な情報を一次的に記憶している。
【００８８】
次に、本実施形態に係るデータ負荷分散配置システム１が行う、（１）各ＤＢサーバ２０のサーバ性能を考慮した仮想サーバの初期配置によるデータ負荷分散配置処理と、（２）システム稼動後の時間経過に伴うデータ数やデータアクセス回数の増減に対応した動的な仮想サーバの再配置と、について具体的に説明する。
【００８９】
（データ負荷分散配置処理―仮想サーバの初期配置）
まず、図８を参照して、データ負荷分散配置システム１が行う、仮想サーバの初期配置における全体の処理の流れについて説明する。図８は、本実施形態に係るデータ負荷分散配置処理（仮想サーバの初期配置）の全体の処理の流れを示すシーケンス図である。
【００９０】
まず、管理者サーバ５から、仮想サーバ配置装置１０が、システム全体に求める処理性能Ｒと、各サーバのサーバ閾値を決定するための負荷閾値定数ｃとを、設定情報として取得する（ステップＳ１１）。なお、この処理は、予め、仮想サーバ配置装置１０の記憶部１４に、設定情報として記憶するようにしてもよい。
【００９１】
次に、各ＤＢサーバ２０は、自身が保存しているデータのデータキー、および自サーバのサーバ性能Ｔｍを、自身に固有な番号とともに、仮想サーバ配置装置１０に送信する（ステップＳ１２）。
【００９２】
続いて、仮想サーバ配置装置１０のサーバ負荷計算部１１２は、サーバ負荷計算処理を行う（ステップＳ１３）。
具体的には、サーバ負荷計算部１１２は、管理者サーバ５から受信した設定情報に含まれる負荷閾値定数ｃと、各ＤＢサーバ２０から受信したサーバ性能Ｔｍとに基づき、（式１）を用いて、各サーバのサーバ閾値αｍを計算する。そして、サーバ負荷計算部１１２は、管理者サーバ５から受信したシステム全体に求める処理性能Ｒと、各サーバから受信したデータキーの数の合計から得られるデータ数Ｈとに基づき、（式２）を用いて、ＤＢサーバ２０ごとの負荷Ｗｍを計算する。なお、この仮想サーバの初期配置では、システム全体に対して１秒当たりシステム最大性能であるＲ回のアクセスがあり、各データへのアクセス回数は均等であるＲ／Ｈ回と想定する。
そして、サーバ負荷計算部１１２は、計算したＤＢサーバ２０ごとの負荷Ｗｍとサーバ閾値αｍとを比較し、負荷がサーバ閾値以下のサーバＳ−の集合と、負荷がサーバ閾値を超えるサーバＳ＋の集合とを生成して、その集合ごとに、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順にサーバを整列する処理を行う。
【００９３】
そして、仮想サーバ配置装置１０の配置処理部１１３が、ハッシュ空間上での仮想サーバの配置処理（「仮想サーバ配置処理」）を行うことにより、サーバ担当データ情報１００を生成する（ステップＳ１４）。ここで、配置処理部１１３は、この仮想サーバ配置処理において、リソース不足と判定した場合には、サーバ担当データ情報１００を生成せずに、そのリソース不足通知を、管理者サーバ５に送信し（ステップＳ１５）、物理サーバ（ＤＢサーバ２０）の追加を促して（ステップＳ１６）、処理を終える。
【００９４】
一方、仮想サーバ配置装置１０が、サーバ担当データ情報１００を生成した場合には、そのサーバ担当データ情報１００を、各ＤＢサーバ２０それぞれに送信する（ステップＳ１７）。
【００９５】
そして、各ＤＢサーバ２０同士で担当データの交換処理を行う（ステップＳ１８）。具体的には、各ＤＢサーバ２０のデータ交換部２１５は、仮想サーバ配置装置１０から受信した新たなサーバ担当データ情報１００と、記憶部２４に保存していたサーバ担当データ情報１００とを比較し、自身のＤＢサーバ２０が、追加して記憶すべきデータを、そのデータを保存するＤＢサーバ２０に問い合わせる。そして、問い合わせを受けたＤＢサーバ２０は、そのデータを問い合わせ元のＤＢサーバ２０に送信し、その送信確認後に自身のサーバからそのデータを削除する処理を行う。また、データ交換部２１５は、記憶部２４に保存していたサーバ担当データ情報１００を、データ管理部２１２を介して、受信した新たなサーバ担当データ情報１００に更新させる。
【００９６】
＜仮想サーバ配置処理＞
次に、図９および図１０を参照して、仮想サーバ配置装置１０（配置処理部１１３）による仮想サーバ配置処理（図８のステップＳ１４）について詳細に説明する。図９および図１０は、本実施形態に係る仮想サーバ配置装置１０の配置処理部１１３による仮想サーバ配置処理の流れを示すフローチャートである（適宜図１参照）。
【００９７】
なお、この配置処理部１１３による仮想サーバ配置処理は、図８のステップＳ１３において、仮想サーバ配置装置１０のサーバ負荷計算部１１２により、各ＤＢサーバ２０の負荷Ｗｍが計算され、負荷がサーバ閾値以下のサーバＳ−と、負荷がサーバ閾値を超えるサーバＳ＋とについて、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順に、サーバがすでに整列されているものとして説明する。
そして、配置処理部１１３は、図２〜図５において説明したように、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順に、負荷がサーバ閾値を超えるサーバＳ＋の負荷の超過分の領域に、負荷がサーバ閾値以下のサーバＳ−の仮想サーバを配置することで、負荷がサーバ閾値を超えるサーバＳ＋の負荷の超過分の担当データを、負荷がサーバ閾値以下のサーバＳ−に変更する処理を行う。以下、具体的に説明する。
【００９８】
まず、配置処理部１１３は、負荷がサーバ閾値を超えるサーバＳ＋、負荷がサーバ閾値以下のサーバＳ−それぞれについて、初期値として、絶対値（Ｏ＋li,Ｏ−kj）が大きい順に１番目のサーバを選択し（「ｉ←１」「ｊ←１」）、初期値のFlagとして「True」を設定する（ステップＳ１０１）。なお、ここで、「ｉ」は、（式５）で示したように、０＜ｉ≦ｑを満たし、「ｊ」は、（式４）で示したように、０＜ｊ≦ｐを満たす値である。また、このFlagは、以後のステップＳ１１３，Ｓ１１７，Ｓ１１９（図１０参照）で設定されるものであり、負荷がサーバ閾値を超えるサーバＳ＋の負荷の超過分を解消するために、負荷がサーバ閾値以下のサーバＳ−が仮想サーバの割当てを行った場合に、さらに、まだ仮想サーバを割り当てる負荷の余裕分があるか否かを示すFlagである。そして、次に割り当てる負荷の余裕分がない場合に「True」、次に割り当てる負荷の余裕分がある場合に「false」のFlagが設定される。
【００９９】
次に、配置処理部１１３は、負荷がサーバ閾値を超えるサーバＳ＋liのうち、まだ処理していないサーバがあるか否かを判定する（ｉ＜ｑ＋１）（ステップＳ１０２）。ここで、まだ処理していない、負荷がサーバ閾値を超えるサーバＳ＋liがない、つまり、すべての負荷がサーバ閾値を超えるサーバＳ＋liの処理を終えている場合には（ステップＳ１０２→Ｎｏ）、処理を終了する。一方、まだ、処理していない、負荷がサーバ閾値を超えるサーバＳ＋liがある場合には（ステップＳ１０２→Ｙｅｓ）、次のステップＳ１０３へ進む。
【０１００】
ステップＳ１０３において、配置処理部１１３は、負荷がサーバ閾値を超えるサーバＳ＋liが、どのくらいサーバ閾値を超えているかの絶対値（Ｏ＋li：超過分）を計算する（Ｏ＋li ← Wli−αli）。
【０１０１】
次に、配置処理部１１３は、その負荷がサーバ閾値を超えるサーバＳ＋liが、そのサーバのサーバ閾値αli以下でそのサーバが担当可能な最大個数のデータのハッシュ空間上での値ｘを計算する（ステップＳ１０４）。このｘは、負荷がサーバ閾値を超えるサーバＳ＋liの担当領域内のデータのハッシュ値をその負荷がサーバ閾値を超えるサーバＳ＋liのハッシュ値に近い順に並べたときに、負荷がサーバ閾値αｍ以下で最大となるｈ番目のデータのハッシュ値となる（x ← max{ x ;Σ h=1,…,x bli (h)≦  αli }）。ここで、bli (h)は、サーバＳ＋liの担当領域のうちのデータのハッシュ値をサーバＳ＋liのハッシュ値に近い順に並べたときに、ｈ番目のデータにかかる負荷を示す。なお、この処理は、後記するステップＳ１０９において、仮想サーバの配置位置を決定する際に利用される。
【０１０２】
続いて、配置処理部１１３は、負荷がサーバ閾値以下のサーバＳ−kjがあるか否かを判定する（ｊ＜ｐ＋１）（ステップＳ１０５）。ここで、負荷がサーバ閾値以下のサーバＳ−kjがない場合には（ステップＳ１０５→Ｎｏ）、ステップＳ１２２（図１０参照）に進み、管理者サーバ５に、物理サーバ（ＤＢサーバ２０）の追加依頼を送信し、処理を終える。一方、負荷がサーバ閾値以下のサーバＳ−kjがある場合には（ステップＳ１０５→Ｙｅｓ）、次のステップＳ１０６へ進む。
【０１０３】
ステップＳ１０６において、配置処理部１１３は、Flagが「true」か否かを判定する。つまり、直前の負荷解消のために割り当てた、負荷がサーバ閾値以下のサーバＳ−kjの負荷の余裕分が使えるか否かを判定する。具体的には、負荷を解消するために、自身の負荷の余裕分をすべて使って仮想サーバの割り当てを行ったか（Flag=true）、仮想サーバの割り当てを行ってもなお負荷の余裕分が残っているか（Flag=false）を判定する。なお、負荷がサーバ閾値を超えるサーバＳ＋liの絶対値Ｏ＋liの大きい順で１番目のサーバ（ｉ＝１）については、ステップＳ１０１で初期値のFlagとして「True」が設定されている。
【０１０４】
ここで、Flag=trueの場合は（ステップＳ１０６→Ｙｅｓ）、次のステップＳ１０７において、配置処理部１１３が、負荷がサーバ閾値以下のサーバＳ−kjの負荷の絶対値を計算し（Ｏ−kj← αkj−Wkj）、ステップＳ１０９へ進む。一方、Flag=falseの場合は（ステップＳ１０６→Ｎｏ）、次のステップＳ１０８において、直前に負荷を割り当てた、負荷がサーバ閾値以下のサーバＳ−kjの負荷の余裕分「Rest」を取得し（Ｏ−kj← Rest）、ステップＳ１０９へ進む。なお、この負荷の余裕分「Rest」は、後記するステップＳ１１６（図１０参照）において、計算されるものである。
【０１０５】
そして、配置処理部１１３は、ステップＳ１０９において、サーバＳ＋liの担当領域のｘ＋１の位置に、サーバＳ−kjの仮想サーバを割り当てる。この仮想サーバの配置位置は、ステップＳ１０４において計算した、負荷がサーバ閾値を超えるサーバが、サーバ閾値以下でそのサーバが担当可能な最大個数のデータのハッシュ空間上での値ｘの次のハッシュ値であるｘ＋１に設定される。
【０１０６】
図１０に進み、ステップＳ１１０において、配置処理部１１３は、ステップＳ１０９（図９参照）で決定した配置位置に、仮想サーバを配置した場合に、負荷がサーバ閾値を超えるサーバＳ＋liの負荷が解消されるか否かを判定する。具体的には、配置処理部１１３は、負荷がサーバ閾値を超えるサーバＳ＋liの負荷の絶対値（Ｏ＋li：超過分）と、仮想サーバを設定する負荷がサーバ閾値以下のサーバＳ−kjの負荷の絶対値（Ｏ−kj：余裕分）とを比較し、負荷がサーバ閾値を超えるサーバＳ＋liの負荷の絶対値Ｏ＋liの方が大きいか否かを判定する（Ｏ＋li＞ Ｏ−kj）。
【０１０７】
ここで、負荷がサーバ閾値を超えるサーバＳ＋liの負荷の絶対値Ｏ＋liの方が大きい場合（ステップＳ１１０→Ｙｅｓ）、つまり、仮想サーバを割り当てても、まだ、負荷がサーバ閾値を超えている場合（超過分が残っている場合）には、次のステップＳ１１１へ進む。
【０１０８】
ステップＳ１１１において、配置処理部１１３は、ステップＳ１０９（図９参照）で設定した、ハッシュ空間上の仮想サーバの配置位置から、その仮想サーバの担当可能な最大個数のデータのハッシュ空間上での値ｘを計算する（x ← max{ x ;Σ h=1,…,x bli (h)≦  αli }）。なお、このハッシュ空間上での値ｘは、絶対値Ｏ−kjの大きさ順が次の負荷がサーバ閾値以下のサーバＳ−kjの仮想サーバを、ハッシュ空間上に割り当てる際（再び、ステップＳ１０９の処理を行う際）に、その仮想サーバの配置位置を決定するときに利用される。
【０１０９】
次に、配置処理部１１３は、仮想サーバを割り当てた後の負荷がサーバ閾値を超えるサーバＳ＋liについて、サーバ閾値を超える負荷の絶対値Ｏ＋liを計算する（Ｏ＋li ← Ｏ＋li−Ｏ−kj）（ステップＳ１１２）。
【０１１０】
そして、配置処理部１１３は、負荷解消のために、負荷がサーバ閾値以下のサーバＳ−kjの余裕部のすべてを割り当てたことを示す、Flagを「true」に設定する（ステップＳ１１３）。
【０１１１】
続いて、配置処理部１１３は、サーバ負荷計算部１１２が計算し整列した後の、負荷がサーバ閾値以下のサーバＳ−kjのうち、次に絶対値Ｏ−kjが大きいサーバを選択し（ｊ←ｊ＋１）（ステップＳ１１４）、ステップＳ１０５（図９参照）へ戻る。
【０１１２】
一方、ステップＳ１１０において、配置処理部１１３は、負荷がサーバ閾値を超えるサーバＳ＋liの負荷の絶対値（Ｏ＋li：超過分）と、仮想サーバを設定する負荷がサーバ閾値以下のサーバＳ−kjの負荷の絶対値（Ｏ−kj：余裕分）とを比較し、負荷がサーバ閾値を超えるサーバＳ＋liの負荷の絶対値Ｏ＋liの方が大きい場合でないとき（ステップＳ１１０→Ｎｏ）、つまり、負荷がサーバ閾値以下のサーバＳ−kjの負荷の余裕の絶対値Ｏ−kjが、負荷がサーバ閾値を超えるサーバＳ＋liの負荷の絶対値Ｏ＋liと同じか、それを超える場合には、ステップＳ１１５へ進む。
【０１１３】
そして、ステップＳ１１５において、配置処理部１１３は、負荷がサーバ閾値以下のサーバＳ−kjの負荷の絶対値（Ｏ−kj：余裕分）が、負荷がサーバ閾値を超えるサーバＳ＋の負荷の絶対値（Ｏ＋li：超過分）を超えるか否かを判定する（Ｏ＋li ＜ Ｏ−kj）。そして、負荷がサーバ閾値以下のサーバＳ−の負荷の絶対値（Ｏ−kj：余裕分）が、負荷がサーバ閾値を超えるサーバＳ＋liの負荷の絶対値（Ｏ＋li：超過分）を超える場合には（ステップＳ１１５→Ｙｅｓ）、つまり、仮想サーバの割当てによって、負荷がサーバ閾値を超えるサーバＳ＋liの超過分が解消され、さらに、仮想サーバを割り当てたサーバＳ−kjにまだ余裕分が残っている場合には、次のステップＳ１１６へ進む。
【０１１４】
次に、配置処理部１１３は、仮想サーバを割り当てた負荷がサーバ閾値以下のサーバＳ−kjの負荷の余裕分（Rest）を計算する（Rest ← Ｏ−kj − Ｏ＋li）（ステップＳ１１６）。そして、配置処理部１１３は、その負荷の余裕分（Rest）を記憶する。
【０１１５】
次に、配置処理部１１３は、負荷解消のために、負荷がサーバ閾値以下のサーバＳ−kjに、まだ余裕分があること（次に割り当てる負荷の余裕分があること）を示す、Flagを「false」に設定する（ステップＳ１１７）。
【０１１６】
そして、配置処理部１１３は、サーバ負荷計算部１１２が計算し整列した後の、負荷がサーバ閾値を超えるサーバＳ＋liのうち、次に絶対値Ｏ＋liの大きいサーバを選択し（ｉ←ｉ＋１）（ステップＳ１１８）、次のステップＳ１２１へ進む。
【０１１７】
一方、ステップＳ１１５において、配置処理部１１３は、負荷がサーバ閾値以下のサーバＳ−kjの負荷の絶対値（Ｏ−kj：余裕分）が、負荷がサーバ閾値を超えるサーバＳ＋liの負荷の絶対値（Ｏ＋li：超過分）と同じ場合は（ステップＳ１１５→Ｎｏ）、次のステップＳ１１９へ進む。そして、配置処理部１１３は、負荷解消のために、負荷がサーバ閾値以下のサーバＳ−kjの余裕分のすべてを割り当てたことを示す、Flagを「true」に設定する（ステップＳ１１９）。
【０１１８】
続いて、配置処理部１１３は、サーバ負荷計算部１１２が計算し整列した後の、負荷がサーバ閾値を超えるサーバＳ＋li、負荷がサーバ閾値以下のサーバＳ−kjのうち、次に絶対値（Ｏ＋li,Ｏ−kj）の大きいサーバをそれぞれ選択し（ｉ←ｉ＋１，ｊ←ｊ＋１）（ステップＳ１２０）、次のステップＳ１２１へ進む。
【０１１９】
そして、ステップＳ１１８およびステップＳ１２０の次に、ステップＳ１２１において、配置処理部１１３は、まだ余裕分の残っている、負荷がサーバ閾値以下のサーバＳ−kjがあるか否かを判定する（ｊ＝ｐ＋１）。そして、まだ余裕分が残っている、負荷がサーバ閾値以下のサーバＳ−kjがある場合には（ステップＳ１２１→Ｙｅｓ）、ステップＳ１０２（図９参照）へ戻り処理を続ける。一方、配置処理部１１３は、負荷がサーバ閾値以下のサーバＳ−kjで、余裕分が残っているサーバがない場合には（ステップＳ１２１→Ｎｏ）、ステップＳ１２２へ進み、管理者サーバ５に、物理サーバ（ＤＢサーバ２０）の追加依頼を送信し、処理を終える。
なお、配置処理部１１３は、ハッシュ空間上での仮想サーバの割当てを完了することにより、新たなサーバ担当データ情報１００を生成し、各ＤＢサーバ２０それぞれに送信する。
【０１２０】
このようにすることで、本実施形態に係るデータ負荷分散配置システム１およびデータ負荷分散配置方法による仮想サーバの初期配置によって、負荷分散を実現し、さらに、各サーバの担当領域に配置する仮想サーバの数が同一に設定される従来技術に比べ、仮想サーバの数を減らすことができる。また、仮想サーバを大量に配置する必要がなくなるため、仮想サーバ保持のための記述量の増加を抑え、クライアントからデータの問い合わせを受けた際に、そのデータを格納している担当サーバの検索に要する時間の増加を抑えることができる。よって、システム全体としてのスループットを向上させることができる。
【０１２１】
（データ負荷分散配置処理―仮想サーバの再配置）
次に、図１１を参照して、データ負荷分散配置システム１が行う、所定間隔Ｚごとの仮想サーバの再配置処理の全体の処理の流れについて説明する。図１１は、本実施形態に係るデータ負荷分散配置処理（仮想サーバの再配置）の全体の処理の流れを示すシーケンス図である。なお、図８に示した仮想サーバの初期配置の全体の流れと同一の処理については、図１１においても、同一の名称と符号を付し、説明を省略する。
【０１２２】
まず、管理者サーバ５から、仮想サーバ配置装置１０が、システム全体に求める処理性能Ｒと、各サーバの負荷のサーバ閾値を決定するための負荷閾値定数ｃとを、設定情報として取得する（ステップＳ１１）。なお、この処理は、所定間隔Ｚごとに行われてもよいが、システム全体に求める処理性能Ｒおよび負荷閾値定数ｃに変更がなければ、このステップＳ１１を行わないようにしてもよい。また、予め、仮想サーバ配置装置１０の記憶部１４に、設定情報（Ｒ，ｃ）を記憶させておき利用するようにしてもよい。
【０１２３】
そして、各ＤＢサーバ２０それぞれは、所定間隔Ｚごとに、自身のＤＢサーバ２０に保存しているデータのデータキーおよびそのデータへのアクセス回数の情報であるアクセス回数情報３００（図７参照）を、自身に固有な番号とともに、仮想サーバ配置装置１０へ送信する（ステップＳ２１）。
【０１２４】
次に、仮想サーバ配置装置１０のサーバ負荷計算部１１２は、サーバ負荷計算処理を行う（ステップＳ２２）。
具体的は、サーバ負荷計算部１１２は、図８の仮想サーバの初期配置におけるステップＳ１２で受信している、各ＤＢサーバ２０のサーバ性能Ｔｍと、自身の記憶部１４に記憶する負荷閾値定数ｃまたはステップＳ１１で取得した負荷閾値定数ｃに基づき、（式１）を用いて、各サーバのサーバ閾値αｍを設定する。また、サーバ負荷計算部１１２は、ステップＳ２１で各ＤＢサーバ２０から受信した、データキーおよびアクセス回数を含むアクセス回数情報３００（図７参照）に基づき、各ＤＢサーバの負荷Ｗｍを計算する。そして、サーバ負荷計算部１１２は、計算したＤＢサーバ２０ごとの負荷Ｗｍとサーバ閾値αｍとを比較し、負荷がサーバ閾値以下のサーバＳ−の集合と、負荷がサーバ閾値を超えるサーバＳ＋の集合とを生成して、その集合ごとに、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順にサーバを整列する処理を行う。
【０１２５】
続いて、仮想サーバ配置装置１０の仮想サーバ再配置計算部１１５は、負荷がサーバ閾値以下となったＤＢサーバ２０について、仮想サーバを取り除く処理（仮想サーバ再配置計算）を行う（ステップＳ２３）。そして、仮想サーバ再配置計算部１１５は、仮想サーバを取り除いた後の各サーバの負荷に基づき、負荷がサーバ閾値以下のサーバＳ−と、負荷がサーバ閾値を超えるサーバＳ＋とについて、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順にサーバを整列する。そして、その情報を、配置処理部１１３に引き渡す。なお、この仮想サーバ再配置計算は、後記する図１２〜図１８において詳細に説明する。
【０１２６】
そして、仮想サーバ配置装置１０の配置処理部１１３は、仮想サーバ再配置計算部１１５が計算し整列させた各サーバの負荷に関する情報に基づき、再度、仮想サーバ配置処理（図９および図１０参照）を実行する（ステップＳ１４）。そして、以下は、図８のステップＳ１５〜Ｓ１８と同様の処理を行って、各ＤＢサーバ２０同士が担当データの交換処理を行う。
【０１２７】
＜仮想サーバ再配置計算＞
次に、図１２〜図１７を参照して、図１１のステップＳ２３における、仮想サーバ配置装置１０（仮想サーバ再配置計算部１１５）による仮想サーバ再配置計算の概要を説明する。そして、図１８を用いて、仮想サーバ再配置計算部１１５による仮想サーバ再配置計算の流れを、さらに詳細にフローチャートを用いて説明する（適宜図１参照）。
【０１２８】
なお、この仮想サーバ再配置計算部１１５による仮想サーバ再配置計算は、例えば、図１１のステップＳ２２において、サーバ負荷計算部１１２が、所定間隔Ｚごとに各ＤＢサーバ２０の負荷Ｗｍを算出し、負荷がサーバ閾値以下のサーバＳ−と、負荷がサーバ閾値を超えるサーバＳ＋とについて、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順にサーバを整列させたことを契機として実行される。
【０１２９】
図１２〜図１７は、本実施形態に係る仮想サーバ配置装置１０（仮想サーバ再配置計算部１１５）による仮想サーバ再配置計算の概要を説明するための図である。
ここでは、仮想サーバ配置装置１０による仮想サーバの初期配置により、図５（ａ）に示すようにハッシュ空間上で仮想サーバが配置され（図１２（ａ）参照）、システム稼働後の所定間隔Ｚ後に、各サーバＳｍの負荷Ｗｍとサーバ閾値αｍとの差の絶対値が、図１２（ｂ）のようになったものとして説明する。例えば、サーバＳ１は、初期配置では、仮想サーバ（ＶＳ３，ＶＳ４）が配置されることにより、負荷がサーバ閾値を超えない設定で、処理を開始したが、時間の経過とともに、図１２（ｂ）に示すように、負荷がサーバ閾値以下のサーバＳ−となっている。つまりサーバＳ１の負荷が減少している。
【０１３０】
仮想サーバ再配置計算部１１５は、負荷がサーバ閾値以下のサーバＳ−のうち、ハッシュ空間上で仮想サーバが配置されているものを取り除く処理を行う。なお、その際、仮想サーバ再配置計算部１１５は、仮想サーバを取り除くと、その負荷Ｗｍがサーバ閾値αｍを超えてしまう場合には、負荷がサーバ閾値以下のサーバＳ−のその仮想サーバを取り除く処理を行わないものとする。
【０１３１】
まず、仮想サーバ再配置計算部１１５は、図１２に示す状態から、負荷がサーバ閾値以下のサーバＳ−のうち、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順で、かつ、ハッシュ空間上で仮想サーバが配置されているサーバを選択する。ここでは、Ｓ１のサーバを選択する。そして、ハッシュ空間上のサーバＳ１に近い順に、１番目に配置された仮想サーバＶＳ３を取り除く（図１３（ａ）参照）。この状態での各サーバＳｍの負荷Ｗｍとサーバ閾値αｍとの差の絶対値を図１３（ｂ）に示す。サーバＳ１は、仮想サーバＶＳ３が担当していたデータの分だけ、負荷の余裕分が減っている。これに対し、サーバＳ３は、仮想サーバＶＳ３の担当していたデータ分だけ、負荷の余裕分が増えている。
【０１３２】
次に、仮想サーバ再配置計算部１１５は、ハッシュ空間上のサーバＳ１に近い順に、２番目に配置された仮想サーバＶＳ４を取り除く（図１４（ａ）参照）。この状態での各サーバＳｍの負荷Ｗｍとサーバ閾値αｍとの差の絶対値を図１４（ｂ）に示す。サーバＳ１は、仮想サーバＶＳ４が担当していたデータ分だけ、負荷の余裕分が減っている。これに対し、サーバＳ４は、仮想サーバＶＳ４の担当していたデータ分だけ、負荷の超過分が減っている。
【０１３３】
これで、サーバＳ１の仮想サーバをすべて取り除いたので、図１２（ｂ）において、負荷がサーバ閾値以下のサーバＳ−で、仮想サーバが配置されている次のサーバであるサーバＳ２を選択する。なお、サーバＳ３は、仮想サーバが配置されていないので、選択せずに、サーバＳ２を選択する。そして、ハッシュ空間上のサーバＳ２に近い順に、１番目に配置された仮想サーバＶＳ４を取り除く（図１５（ａ）参照）。この状態での各サーバＳｍの負荷Ｗｍとサーバ閾値αｍとの差の絶対値を図１５（ｂ）に示す。サーバＳ２は、仮想サーバＶＳ４が担当していたデータ分だけ、負荷の余裕分が減っている。これに対し、サーバＳ４は、仮想サーバＶＳ４が担当していたデータ分だけ、負荷の超過分が減っている。
【０１３４】
次に、仮想サーバ再配置計算部１１５は、ハッシュ空間上のサーバＳ２に近い順に、２番目に配置された仮想サーバＶＳ５を取り除く処理を行おうとするが、仮想サーバＶＳ５の担当データ分の負荷が、サーバＳ２の余裕分より大きいため、仮想サーバＶＳ５を取り除くと、サーバＳ２の負荷がサーバ閾値を超えてしまうため、取り除く処理を行わない（図１６参照）。
【０１３５】
そして、仮想サーバ再配置計算部１１５は、負荷がサーバ閾値以下のサーバＳ−のすべてのサーバの処理を終えると、仮想サーバを取り除いても負荷がサーバ閾値を超えない範囲で、その仮想サーバを取り除いた状態の各サーバＳｍの負荷Ｗｍとサーバ閾値αｍとの差の絶対値を示す図１６（ｂ）のようになる。仮想サーバ再配置計算部１１５は、負荷がサーバ閾値以下のサーバＳ−と、負荷がサーバ閾値を超えるサーバＳ＋とについて、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順に整列し直し（図１７参照）、仮想サーバ再配置計算を終え、その情報を配置処理部１１３に渡す。そして、配置処理部１１３が、図１１のステップＳ１４の仮想サーバ配置処理（図９および図１０参照）を続ける。
【０１３６】
次に、図１８を用いて、仮想サーバ再配置計算部１１５による仮想サーバ再配置計算の流れを、さらに詳細にフローチャートを用いて説明する（適宜図１参照）。
【０１３７】
まず、仮想サーバ再配置計算部１１５は、初期値として、負荷がサーバ閾値以下のサーバＳ−kjについて、絶対値Ｏ−kjが大きい順に１番目のサーバを選択し（ｊ←１）、その選択した負荷がサーバ閾値以下のサーバＳ−kjに、ハッシュ空間上で近い順で一番目の仮想サーバを初期値として選択する（ｌ←１）（ステップＳ２０１）。
【０１３８】
次に、仮想サーバ再配置計算部１１５は、まだ処理していない、負荷がサーバ閾値以下のサーバＳ−kjがあるか否かを判定する（ｊ＜ｐ＋１）（ステップＳ２０２）。ここで、まだ処理していない、負荷がサーバ閾値以下のサーバＳ−kjがない、つまり、すべての負荷がサーバ閾値以下のサーバＳ−kjの処理を終えている場合には（ステップＳ２０２→Ｎｏ）、ステップＳ２１０へ進む。一方、まだ処理していない、負荷がサーバ閾値以下のサーバＳ−kjがある場合には（ステップＳ２０２→Ｙｅｓ）、次のステップＳ２０３へ進む。
【０１３９】
ステップＳ２０３において、仮想サーバ再配置計算部１１５は、負荷がサーバ閾値以下のサーバＳ−kjのハッシュ空間上での担当領域に、仮想サーバが配置されているか否かを判定する（ｙkj ＞ ０）。ここでｙkjは、負荷がサーバ閾値以下のサーバＳ−kjに配置された仮想サーバ数を示す。そして、負荷がサーバ閾値以下のサーバＳ−kjに仮想サーバが配置されていない場合には（ステップＳ２０３→Ｎｏ）、ステップＳ２０９へ進む。一方、仮想サーバが配置されている場合には（ステップＳ２０３→Ｙｅｓ）、次のステップＳ２０４へ進む。
【０１４０】
続いて、仮想サーバ再配置計算部１１５は、負荷がサーバ閾値以下のサーバＳ−kjの負荷の絶対値（Ｏ−kj：余裕分）が０を超えているか否かを判定する（Ｏ−kj ＞０）（ステップＳ２０４）。つまり、負荷がサーバ閾値以下のサーバＳ−kjが、仮想サーバを取り除いた後でも、まだ、その余裕分が残っているか否かを判定する。なお、このステップＳ２０４を最初に実行する際は、ステップＳ２０２で、負荷がサーバ閾値以下のサーバが１つでも存在すれば、当然に、余裕分が残っていることになる。ここで、負荷がサーバ閾値以下のサーバＳ−kjの負荷の絶対値（Ｏ−kj：余裕分）が０以下、つまり余裕分が残っていない場合は（ステップＳ２０４→Ｎｏ）、ステップＳ２０９へ進む。一方、負荷がサーバ閾値以下のサーバＳ−kjの負荷の絶対値（Ｏ−kj：余裕分）が０より大きい、つまり余裕分が残っている場合には（ステップＳ２０４→Ｙｅｓ）、次のステップＳ２０５へ進む。
【０１４１】
次に、仮想サーバ再配置計算部１１５は、負荷がサーバ閾値以下のサーバＳ−kjの担当領域に、まだ未処理の仮想サーバが配置されているか否かを判定する（ｌ＜ｙkj＋１）（ステップＳ２０５）。つまり、取り除くことができる可能性のある仮想サーバが残っているか否かを判定する。ここで、未処理の仮想サーバがハッシュ空間上に配置されていない場合には（ステップＳ２０５→Ｎｏ）、ステップＳ２０９へ進む。一方、未処理の仮想サーバがそのサーバのハッシュ空間上の担当領域に残っている場合には（ステップＳ２０５→Ｙｅｓ）、次のステップＳ２０６へ進む。
【０１４２】
ステップＳ２０６において、仮想サーバ再配置計算部１１５は、仮想サーバの担当する負荷（Ｚkj(l)）が、負荷がサーバ閾値以下のサーバＳ−kjの負荷の余裕分の絶対値（Ｏ−kj：余裕分）より小さいか否かを判定する（Ｚkj(l) ＜ Ｏ−kj）。つまり、仮想サーバを取り除いても、その仮想サーバの基のサーバの負荷が、サーバ閾値を超えないか否かを判定する。ここで、仮想サーバの担当する負荷（Ｚkj(l)）が、負荷がサーバ閾値以下のサーバＳ−kjの負荷の絶対値（Ｏ−kj：余裕分）以上の場合は（ステップＳ２０６→Ｎｏ）、ステップＳ２０９へ進む。一方、仮想サーバの担当する負荷（Ｚkj(l)）が、負荷がサーバ閾値以下のサーバＳ−kjの負荷の絶対値（Ｏ−kj：余裕分）より小さい場合には（ステップＳ２０６→Ｙｅｓ）、次のステップＳ２０７へ進む。
【０１４３】
ステップＳ２０７において、仮想サーバ再配置計算部１１５は、仮想サーバをハッシュ空間上から取り除く。そして、仮想サーバ再配置計算部１１５は、その領域を担当する元のサーバに負荷を戻す処理を行う。具体的には、仮想サーバ（ｖk(l)）を取り除いた場合の負荷を以下の式により計算する。
【０１４４】
【数１０】
0005540269.tif 000011
【０１４５】
ここで、Wvkj(l)は、仮想サーバを取り除いた元のサーバの負荷を示す。
【０１４６】
そして、仮想サーバ再配置計算部１１５は、負荷がサーバ閾値以下のサーバＳ−kjの担当領域の、次の仮想サーバを選択し（ｌ←ｌ＋１）（ステップＳ２０８）、ステップＳ２０４へ戻り、処理を続ける。
【０１４７】
一方、ステップＳ２０３→Ｎｏ、ステップＳ２０４→Ｎｏ、ステップＳ２０５→Ｎｏ、ステップＳ２０６→Ｎｏの場合には、ステップＳ２０９において、仮想サーバ再配置計算部１１５は、サーバ負荷計算部１１２が計算し整列した後の、負荷がサーバ閾値以下のサーバＳ−kjのうち、次に絶対値が大きいサーバを選択し（ｊ←ｊ＋１）、ステップＳ２０２へ戻る。
【０１４８】
そして、仮想サーバ再配置計算部１１５は、ステップＳ２０２において、負荷がサーバ閾値以下のサーバＳ−kjすべての処理を終えている場合には（ステップＳ２０２→Ｎｏ）、ステップＳ２０７において再計算された各サーバの負荷Ｗｍに基づき、負荷がサーバ閾値以下のサーバＳ−と、負荷がサーバ閾値を超えるサーバＳ＋とについて、負荷Ｗｍとサーバ閾値αｍとの差の絶対値が大きい順に整列する（ステップＳ２１０）。そして、その情報を、配置処理部１１３に渡す。配置処理部１１３では、図９および図１０で示した仮想サーバ配置処理を実行する。
【０１４９】
このようにすることで、本実施形態に係るデータ負荷分散配置システム１およびデータ負荷分散配置方法による仮想サーバの再配置によれば、所定間隔ごとの担当データ数の増減や各データへの実アクセス数に応じた、各ＤＢサーバ２０の負荷を計算する。そして、負荷がサーバ閾値以下のサーバＳ−に含まれることになったＤＢサーバ２０のハッシュ空間上での担当領域に、仮想サーバが配置されている場合に、その仮想サーバの担当領域を、元のＤＢサーバの担当領域に戻すことができる。そして、負荷Ｗｍとサーバ閾値αｍとの差の絶対値を計算し直すことにより、負荷がサーバ閾値以下のサーバＳ−の集合と、負荷がサーバ閾値を超えるサーバＳ＋の集合とを生成して、再度、ハッシュ空間上での仮想サーバの配置を計算する。これにより、各ＤＢサーバ２０の負荷を均一化させるとともに、ハッシュ空間上に配置する仮想サーバの数を減らすことができる。
【０１５０】
なお、本実施形態において仮想サーバ配置装置１０は、コンシステントハッシュ法の領域分割方式として、時計回り方式を用いて、ハッシュ空間上に仮想サーバを配置するものとして説明した。しかし、本発明はこれに限定されず、反時計回り方式や、各データがリング上で最も隣接するサーバにデータを格納する最近値方式等を用いることもできる。
【符号の説明】
【０１５１】
１      データ負荷分散配置システム
５      管理者サーバ
６      クライアント
１０    仮想サーバ配置装置
１１    制御部
１２，２２  通信部
１３，２３  メモリ部
１４，２４  記憶部
２０    ＤＢサーバ
２１    処理部
１００  サーバ担当データ情報
１１１，２１１  情報受信部
１１２  サーバ負荷計算部
１１３  配置処理部
１１４，２１３  ハッシュ値計算部
１１５  仮想サーバ再配置計算部
１１６，２１６  情報送信部
２００  データ格納部
２１２  データ管理部
２１４  アクセス監視部
２１５  データ交換部
３００  アクセス回数情報
【図１】
0005540269.tif 000012
【図２】
0005540269.tif 000013
【図３】
0005540269.tif 000014
【図４】
0005540269.tif 000015
【図５】
0005540269.tif 000016
【図６】
0005540269.tif 000017
【図７】
0005540269.tif 000018
【図８】
0005540269.tif 000019
【図９】
0005540269.tif 000020
【図１０】
0005540269.tif 000021
【図１１】
0005540269.tif 000022
【図１２】
0005540269.tif 000023
【図１３】
0005540269.tif 000024
【図１４】
0005540269.tif 000025
【図１５】
0005540269.tif 000026
【図１６】
0005540269.tif 000027
【図１７】
0005540269.tif 000028
【図１８】
0005540269.tif 000029
【図１９】
0005540269.tif 000030