(57)【特許請求の範囲】
【請求項１】
複数のサーバ装置に分散配置するデータの配置先を、前記データを管理する単位であるインスタンスごとに決定するデータ配置装置であって、
前記インスタンスの組合せのパターンを導出するパターン導出部と、
前記パターン導出部によって導出された前記パターンと前記サーバ装置との組合せごとに、前記パターンを選択した場合にユーザ側が受けるユーザ観点の利益および／またはシステム側が受けるシステム観点の利益の度合いを示す利益値を、当該利益値の増減に影響を及ぼす要素を変数に組み込んだ評価関数を演算することで算出する利益算出部と、
前記利益算出部によって算出された前記利益値のうちの最大の利益値に対応する前記パターンと前記サーバ装置との組合せを選択し、当該選択した前記パターンと前記サーバ装置との組合せに関する選択パターン情報を記憶装置に記憶させる選択記憶処理を、全ての前記サーバ装置に対して前記パターンが選定されるまで繰り返し行うパターン選択部と、
を備えることを特徴とするデータ配置装置。
【請求項２】
前記パターン導出部によって導出された前記パターンの中から二つのパターンを選択し、予め定められたパターン間の類似度を算出するための式を用いて二つのパターン間の類似度を算出し、前記類似度が所定の閾値よりも高い場合に、当該２つの前記パターンを、いずれか一つの前記パターンに統合する統合処理を所定回数実行するパターン統合部を、さらに備え、
前記利益算出部は、前記パターン統合部によって統合された後に残った前記パターンと前記サーバ装置との組合せごとに、前記利益を算出する、
ことを特徴とする請求項１記載のデータ配置装置。
【請求項３】
前記パターン導出部は、
前記インスタンスの組合せのパターンのうちの一部のパターンを導出し、
前記利益算出部によって算出された前記利益値の合計が所定の閾値に到達しない場合には、前記一部のパターンを導出し直す、
ことを特徴とする請求項１記載のデータ配置装置。
【請求項４】
前記評価関数には、少なくとも、前記インスタンスのデータ量、データ属性に対応する情報、現時点の配置からのデータ移動量、または前記パターン選択部によって前記パターンに選択された前記インスタンスの選択回数のうちのいずれか一つが前記変数として組み込まれる、
ことを特徴とする請求項１〜３のいずれか１項に記載のデータ配置装置。
【請求項５】
前記評価関数には、さらに、少なくとも、前記インスタンスへのアクセス量、または前記インスタンスのデータ増減量のうちのいずれか一つが前記変数として組み込まれる、
ことを特徴とする請求項４記載のデータ配置装置。
【請求項６】
記憶装置に記憶された選択パターン情報に基づいて、前記サーバ装置に対応する前記パターンにより特定される前記インスタンスを、対応する前記サーバ装置に配置するインスタンス配置部を、さらに備える、
ことを特徴とする請求項１〜５のいずれか１項に記載のデータ配置装置。
【請求項７】
複数のサーバ装置に分散配置するデータの配置先を、前記データを管理する単位であるインスタンスごとに決定するデータ配置方法であって、
前記インスタンスの組合せのパターンを導出するパターン導出ステップと、
前記パターン導出ステップにおいて導出された前記パターンと前記サーバ装置との組合せごとに、前記パターンを選択した場合にユーザ側が受けるユーザ観点の利益および／またはシステム側が受けるシステム観点の利益の度合いを示す利益値を、当該利益値の増減に影響を及ぼす要素を変数に組み込んだ評価関数を演算することで算出する利益算出ステップと、
前記利益算出ステップにおいて算出された前記利益値のうちの最大の利益値に対応する前記パターンと前記サーバ装置との組合せを選択し、当該選択した前記パターンと前記サーバ装置との組合せに関する選択パターン情報を記憶装置に記憶させる選択記憶処理を、全ての前記サーバ装置に対して前記パターンが選定されるまで繰り返し行うパターン選択ステップと、
を含むことを特徴とするデータ配置方法。
【請求項８】
請求項７に記載の各ステップをコンピュータに実行させるためのデータ配置プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ配置装置、データ配置方法およびデータ配置プログラムに関する。
【背景技術】
【０００２】
処理対象のデータを複数のサーバ装置に分散配置する分散データ処理システムでは、処理対象のデータをどのように配置するかが重要な課題の一つになっている。下記特許文献１には、記憶装置に格納されているデータ量に基づいてデータ配置を行う技術が開示されている。また、下記特許文献２には、計算機のリソース状況とアクセス分布とに基づいてデータ配置を行う技術が開示されている。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】特開２００５−５０３０３号公報
【特許文献２】特開平０６−２５９４７８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００４】
上記特許文献１ではデータ量のみを考慮してデータ配置を行っており、上記特許文献２ではリソース状況とアクセス分布のみを考慮してデータ配置を行っている。しかしながら、データの処理効率を向上させるためには、様々な要素を複合的に考慮する必要があるため、改善の余地がある。
【０００５】
本発明は、上述した課題を解決するためになされたものであり、様々な要素を複合的に考慮してデータ配置を行うことで、データ処理の効率を向上させることができるデータ配置装置、データ配置方法およびデータ配置プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００６】
本発明のデータ配置装置は、複数のサーバ装置に分散配置するデータの配置先を、前記データを管理する単位であるインスタンスごとに決定するデータ配置装置であって、前記インスタンスの組合せのパターンを導出するパターン導出部と、前記パターン導出部によって導出された前記パターンと前記サーバ装置との組合せごとに、前記パターンを選択した場合に得られる利益を算出する利益算出部と、前記利益算出部によって算出された前記利益のうちの最大の利益に対応する前記パターンを選択するパターン選択部と、を備える。
【０００７】
本発明のデータ配置方法は、複数のサーバ装置に分散配置するデータの配置先を、前記データを管理する単位であるインスタンスごとに決定するデータ配置方法であって、前記インスタンスの組合せのパターンを導出するパターン導出ステップと、前記パターン導出ステップにおいて導出された前記パターンと前記サーバ装置との組合せごとに、前記パターンを選択した場合に得られる利益を算出する利益算出ステップと、前記利益算出ステップにおいて算出された前記利益のうちの最大の利益に対応する前記パターンを選択するパターン選択ステップと、を含む。
【０００８】
本発明のデータ配置プログラムは、上記データ配置方法に含まれる各ステップをコンピュータに実行させる。
【発明の効果】
【０００９】
本発明によれば、様々な要素を複合的に考慮してデータ配置を行うことで、データ処理の効率を向上させることができる。
【図面の簡単な説明】
【００１０】
【図１】第１実施形態におけるデータ配置装置の構成を例示する図である。
【図２】パターン導出部によって導出されるパターンの概念を説明するための図である。
【図３】インスタンスが選択済みパターンに選択された回数を例示する図である。
【図４】利益表の一例を示す図である。
【図５】利益表の一例を示す図である。
【図６】利益表の一例を示す図である。
【図７】第１実施形態におけるデータ配置装置の動作を説明するためのフローチャートである。
【図８】第２実施形態におけるデータ配置装置の構成を例示する図である。
【図９】パターン統合部が２つのパターンを統合する際の概念を説明するための図である。
【図１０】第２実施形態におけるデータ配置装置の動作を説明するためのフローチャートである。
【図１１】パターン統合処理の手順を説明するためのフローチャートである。
【図１２】第３実施形態におけるデータ配置装置の構成を例示する図である。
【図１３】第３実施形態におけるデータ配置装置の動作を説明するためのフローチャートである。
【図１４】第４実施形態におけるデータ配置装置の構成を例示する図である。
【図１５】アクセス情報テーブルのデータ構成を例示する図である。
【図１６】増減情報テーブルのデータ構成を例示する図である。
【図１７】第４実施形態におけるデータ配置装置に特有の動作を説明するためのフローチャートである。
【発明を実施するための形態】
【００１１】
以下、添付図面を参照して、本発明に係るデータ配置装置、データ配置方法およびデータ配置プログラムの好適な実施形態について説明する。ここで、データ配置装置は、複数のサーバ装置に分散して配置されるデータの配置先をインスタンスごとに決定する。インスタンスは、データを管理する単位であり、一または複数のデータがインスタンスごとにまとめられる。
【００１２】
[第１実施形態]
まず、図１を参照して、第１実施形態におけるデータ配置装置の構成について説明する。図１に示すデータ配置装置１は、機能的には、例えば、パターン導出部１１と、利益算出部１２と、パターン選択部１３と、インスタンス配置部１４とを有する。データ配置装置１は、上記各部が参照・更新する情報を格納するインスタンス情報記憶部２１、サーバ情報記憶部２２、および選択済パターン情報記憶部２３を備える。
【００１３】
インスタンス情報記憶部２１は、インスタンスに関するインスタンス情報を格納する。インスタンス情報には、例えば、データ量や、データ属性、データスキーマ等のインスタンスに属するデータに関する情報が含まれる。
【００１４】
サーバ情報記憶部２２は、サーバ装置に関するサーバ情報を格納する。サーバ情報には、例えば、サーバ装置のリソース情報（ディスク量、メモリ量、ＣＰＵの処理能力等）や、現時点でサーバ装置に配置されているインスタンスを特定する情報等が含まれる。
【００１５】
ここで、データ配置装置１は、物理的には、例えば、ＣＰＵ（Central Processing Unit）と、記憶装置と、入出力インターフェースとを含んで構成される。記憶装置には、例えば、ＣＰＵで処理されるプログラムおよびデータを記憶するＲＯＭ（Read Only Memory）やＨＤＤ（Hard Disk Drive）、主として制御処理のための各種作業領域として使用されるＲＡＭ（Random Access Memory）等の要素が含まれる。これらの要素は、互いにバスを介して接続されている。ＣＰＵが、ＲＯＭに記憶されたプログラムを実行し、入出力インターフェースを介して受信されるメッセージや、ＲＡＭに展開されるデータを処理することで、データ配置装置１が有する各部の機能を実現することができる。
【００１６】
図１に示すパターン導出部１１は、データを配置するように指示するデータ配置指示を受信した場合に、インスタンス情報記憶部２１を参照し、インスタンスの組合せの全てのパターンを導出する。データ配置指示が送信されるタイミングとしては、例えば、データが追加されるときや、サーバ装置が追加されるとき、システム管理者により実行指示が入力されたとき等が該当する。
【００１７】
図２を参照して、パターン導出部１１によって導出されるパターンの概念について説明する。例えば、５つのインスタンスＩ１〜Ｉ５が存在する場合には、例えば、３つのインスタンスＩ１、Ｉ２、Ｉ３を含むパターン１、３つのインスタンスＩ１、Ｉ４、Ｉ５を含むパターン２、５つのインスタンスＩ１、Ｉ２、Ｉ３、Ｉ４、Ｉ５を含むパターン３、１つのインスタンスＩ３を含むパターン４等が導出される。
【００１８】
なお、導出するパターンは、インスタンスの組合せの全てのパターンであることには限定されない。全てのインスタンスがいずれかのパターンに含まれていれば、一部のパターンのみを導出することとしてもよい。例えば、３つのインスタンスを含むパターンのみを導出することとしてもよいし、１つのインスタンスだけを含むパターンを除外して導出することとしてもよい。
【００１９】
図１に示す利益算出部１２は、インスタンス情報記憶部２１、サーバ情報記憶部２２および選択済パターン情報記憶部２３を参照し、パターン導出部１１によって導出されたパターンと配置先候補のサーバ装置との組合せごとに、そのパターンを選択した場合に得られる利益を算出する。利益には、ユーザ側が利益を受けるユーザ観点の利益と、システム側が利益を受けるシステム観点の利益とが含まれる。ユーザ観点の利益としては、例えば、そのパターンをあるサーバ装置に配置することで、データへのアクセス速度が向上する等の利益が該当する。システム観点の利益としては、例えば、そのパターンをあるサーバ装置に配置するときのデータ移動に要するサーバ間の通信量を削減できる等の利益が該当する。このような利益の基準は、システム管理者が適宜設定することができる。
【００２０】
利益算出部１２は、各パターンに属するインスタンスのデータ量、データの属性、現時点の配置からのデータ移動量、インスタンスがパターンに選択された回数等の様々な要素を複合的に用いて、利益を算出する。利益は、上記各要素を用いて、例えば以下のように算出することができる。
【００２１】
データ量から利益を算出する場合には、例えば、各パターンのデータ量の平均が全体のデータ量の平均に近いほど利益が高くなるように、利益を算出する。これにより、各サーバ装置に配置されるインスタンスのデータ量が均等に近づくように導くことが可能となる。
【００２２】
データ属性から利益を算出する場合には、例えば、各パターンのデータの属性が、同じ属性に集中しているほど利益が高くなるように、利益を算出する。これにより、同じ属性のデータが同じサーバに配置されるように導くことが可能となる。
【００２３】
データ移動量から利益を算出する場合には、例えば、各パターンの配置が再配置前に存在するパターンの配置に近いほど利益が高くなるように、利益を算出する。これにより、データを再配置する際のデータの移動量が少なくなるように導くことが可能となる。
【００２４】
インスタンスの選択回数から利益を算出する場合には、例えば、既に選択されたパターンに含まれるインスタンスを多く含むほど利益が低くなるように、利益を算出する。これにより、インスタンス間での配置数の格差が縮まるように導くことが可能となる。
【００２５】
利益を算出する方法について、より具体的に説明する。例えば、各パターンのデータ量、データ移動量、インスタンスの選択回数に基づいて利益を算出する場合には、下記式（１）に示す評価関数を用いることができる。
【００２６】
ｗ１＊ｆ１（パターン、サーバ情報、インスタンス情報） ＋ ｗ２＊ｆ２（パターン、サーバ情報、インスタンス情報） ＋ ｗ３＊ｆ３（パターン、選択済パターン）  …  （１）
【００２７】
ここで、ｆ１はデータ量から利益を算出する関数であり、ｆ２はデータ移動量から利益を算出する関数であり、ｆ３はインスタンスの選択回数から利益を算出する関数である。また、ｗ１、ｗ２、ｗ３は、それぞれ重み係数である。重み係数ｗ１、ｗ２、ｗ３を調整することで、どの要素を重視するのかを調整することができる。また、関数ｆ１は、例えば下記式（２）のように表すことができる。
【００２８】
ｆ１ ＝ ｆ１_ｗ１＊｛１／（１＋｜全体のデータ量の平均 − パターンのデータ量の平均｜）｝ ＋ ｆ１_ｗ２＊（パターンのデータ量／サーバのリソース量）  …  （２）
【００２９】
上記式（２）の第一項は、パターンに含まれるデータ量の平均値が全体のデータ量の平均値にどの程度近いかを評価する項であり、第二項は、各サーバ装置のリソース（ディスク量やメモリ量）をどの程度有効活用できているかを評価する項である。上記式（２）は、パターンのデータ量の平均が全体のデータ量の平均に近く、かつ、サーバ装置のリソースがなるべく多く利用されているほど、利益が高くなるように設定されている。ただし、パターンのデータ量がサーバ装置のリソース量（ディスク量やメモリ量）を超過する場合には、そのパターンは物理的にサーバ装置に配置できないため、この場合には、そのパターンの利益を０にする。なお、上記式（２）のｆ１_ｗ１、ｆ１_ｗ２は、それぞれ重み係数である。
【００３０】
上記式（１）の関数ｆ２は、例えば下記式（３）のように表すことができる。
【００３１】
ｆ２ ＝ （現時点でサーバに配置されているインスタンスとパターンに含まれるインスタンスとの間で一致しているインスタンス数／現時点でサーバに配置されている総インスタンス数）  …  （３）
【００３２】
上記式（３）は、現時点でサーバ装置に配置されているインスタンスのパターンと、評価対象のパターンとがどの程度一致しているかを評価しており、現時点の配置に近いほど利益が高くなるように設定されている。具体的に、例えば、サーバ装置に現在配置されているインスタンスが３つのインスタンスＩ１、Ｉ２、Ｉ３であり、評価対象のパターンに含まれるインスタンスが２つのインスタンスＩ２、Ｉ４である場合には、「現時点でサーバに配置されているインスタンスとパターンに含まれるインスタンスとの間で一致しているインスタンス数」は、インスタンスＩ２のみの“１”となり、関数ｆ２は、“１／３”となる。
【００３３】
上記式（１）の関数ｆ３は、例えば下記式（４）のように表すことができる。
【００３４】
ｆ３ ＝ ｛（１＋パターンに含まれるインスタンスのうち選択済パターンにまだ含まれていないインスタンスの数）／（１＋パターンに含まれるインスタンスのうち選択済みパターンに含まれるインスタンスの累計）｝  …  （４）
【００３５】
上記式（４）は、これまでに選択されたパターンに含まれるインスタンスが評価対象のパターンにどの程度含まれているかを評価しており、評価対象のパターンに含まれるインスタンスがこれまでに選択されていないほど利益が高くなるように設定されている。
【００３６】
上記式（４）について図３を参照して説明する。図３に示す表Ｔ１は、選択済みパターンに選択された回数を、インスタンスごとに表すものである。表Ｔ１のインスタンスＩ１は、選択済みパターンに１回選択され、インスタンスＩ２は、まだ選択済みパターンに選択されておらず、インスタンスＩ３は、選択済みパターンに３回選択されていることを示す。
【００３７】
例えば、３つのインスタンスＩ１、Ｉ２、Ｉ３を含むパターンを、関数ｆ３で評価する場合には、「パターンに含まれるインスタンスのうち選択済パターンにまだ含まれていないインスタンスの数」は、インスタンスＩ２のみであるため“１”となる。また、「パターンに含まれるインスタンスのうち選択済みパターンに含まれるインスタンスの累計」は、インスタンスＩ１の“１”回と、インスタンスＩ３の“３”回とを合わせて“４”回となる。したがって、関数ｆ３は、“（１＋１）／（１＋４）＝２／５”となる。
【００３８】
このように、利益として設定したい要素を評価関数に組み込むことで、様々な要素を考慮した利益を計算することが可能となる。また、それぞれの要素の重み係数を調整することで、重視したい要素の比率を簡単に変更することができる。
【００３９】
なお、インスタンスを配置するサーバ装置の性能が個々に異なる場合や、データ移動量を考慮する場合には、それぞれのサーバ装置が現在どのようなインスタンスを配置しているのかを考慮する必要があるため、各パターンの利益を算出する場合には、サーバ装置ごとに利益を算出する必要がある。図４は、サーバ装置とパターンとの組み合わせごとに算出された利益を表示する利益表の一例である。
【００４０】
図１に示すパターン選択部１３は、利益算出部１２によって算出された利益のうちの最大の利益に対応するパターンを選択する。パターン選択部１３は、選択したパターンに関する選択パターン情報を、選択済パターン情報記憶部２３に記憶させる。なお、選択パターン情報には、選択されたパターンの利益に関する情報も含まれる。
【００４１】
図５および図６を参照して、パターン選択部１３がパターンを選択する際の手順について説明する。
【００４２】
最初に、パターン選択部１３は、図５に示す利益表Ｔ２の中から、最大の利益に対応するパターンとサーバとの組み合わせを選択する。利益表Ｔ２では、パターン２とサーバ１との組み合わせによる利益が“２０”で最大の利益となるため、パターン２とサーバ１との組み合わせが選択される。
【００４３】
続いて、パターン選択部１３は、パターン２とサーバ１との組み合わせに関する選択パターン情報を、選択済パターン情報記憶部２３に記憶させる。続いて、利益算出部１２は、各パターンの利益を再度算出し直す。これは、選択済パターン情報記憶部２３に新たなパターンが追加されたことにより、各パターンの利益が変動するためである。ただし、サーバ１には、既にパターン２が配置されるため、サーバ１に関しては利益を計算する必要はない。
【００４４】
続いて、利益算出部１２による利益の再算出によって、図６に示す利益表Ｔ３が生成されたとする。パターン選択部１３は、利益表Ｔ３の中から、最大の利益に対応するパターンとサーバとの組み合わせを選択する。利益表Ｔ３では、パターン１とサーバ２との組み合わせによる利益が“１０”で最大の利益となるため、パターン１とサーバ２との組み合わせが選択される。
【００４５】
続いて、パターン選択部１３は、パターン１とサーバ２との組み合わせに関する選択パターン情報を、選択済パターン情報記憶部２３に記憶させる。これ以降は、配置対象のサーバ装置がなくなるまで上記と同様の処理を繰り返し行う。
【００４６】
図１に示すインスタンス配置部１４は、選択済パターン情報記憶部２３に記憶されているパターン情報に従って、インスタンスを各サーバ装置に配置する。インスタンス配置部１４は、各サーバ装置に配置したインスタンスの配置に関する情報を、サーバ情報記憶部２２に記憶させる。
【００４７】
次に、図７を参照して、第１実施形態におけるデータ配置装置１の動作について説明する。
【００４８】
最初に、データ配置指示を受信する（ステップＳ１０１）と、パターン導出部１１は、インスタンス情報記憶部２１を参照し、インスタンスの組合せの全パターンを導出する（ステップＳ１０２）。
【００４９】
続いて、利益算出部１２は、インスタンス情報記憶部２１、サーバ情報記憶部２２および選択済パターン情報記憶部２３を参照し、パターン導出部１１によって導出されたパターンと配置先候補のサーバ装置との組合せごとに、そのパターンを選択した場合に得られる利益を算出する（ステップＳ１０３）。
【００５０】
続いて、パターン選択部１３は、利益算出部１２によって算出された利益のうちの最大の利益に対応するパターンを選択し（ステップＳ１０４）、選択したパターンに関する選択パターン情報を、選択済パターン情報記憶部２３に記憶させる。
【００５１】
続いて、パターン選択部１３は、全てのサーバ装置に対して配置するパターンが選択されたか否かを判定する（ステップＳ１０５）。この判定がＮＯである場合（ステップＳ１０５；ＮＯ）に、処理を上記ステップＳ１０３に移行する。
【００５２】
一方、上記ステップＳ１０５の判定で全てのサーバ装置に対して配置するパターンが選択されたと判定された場合（ステップＳ１０５；ＹＥＳ）に、パターン導出部１１は、選択済パターン情報記憶部２３を参照し、選択済パターン情報に全てのインスタンスが含まれているか否かを判定する（ステップＳ１０６）。この判定がＮＯである場合（ステップＳ１０６；ＮＯ）には、上記式（１）の評価関数の重み係数“ｗ３”の値を大きくし、評価関数における関数ｆ３の比率を大きくする（ステップＳ１０７）。そして、処理を上記ステップＳ１０２に移行する。これにより、まだ選択されていないインスタンスを含むパターンの利益を相対的に大きくすることが可能となる。
【００５３】
一方、上記ステップＳ１０６の判定で選択済パターン情報に全てのインスタンスが含まれていると判定された場合（ステップＳ１０６；ＹＥＳ）に、インスタンス配置部１４は、選択済パターン情報記憶部２３に記憶されているパターン情報に従って、インスタンスを各サーバ装置に配置する（ステップＳ１０８）。そして、サーバ情報記憶部２２に記憶されている現時点でサーバ装置に配置されているインスタンスを特定する情報を更新し、本動作を終了する。
【００５４】
上述したように、第１実施形態におけるデータ配置装置１によれば、配置可能なインスタンスのパターンを導出し、それぞれのパターンに対してデータ量やデータ移動量、インスタンスの選択回数等の様々な要素を複合的に考慮した利益を算出し、その利益が最大となるパターンを順次選択することで、データ量やデータ移動量等の様々な要素を複合的に考慮したデータ配置を、比較的簡単な評価関数を用いて行うことが可能となる。したがって、例えばシステムの運用中にデータ配置のポリシーを変更する場合には、配置ポリシーを変更するために要するコストを削減することが可能となる。
【００５５】
なお、上述したデータ配置装置１の動作において、ステップＳ１０６の判定で選択済パターン情報に全てのインスタンスが含まれていないと判定された場合に、ステップＳ１０７で上記式（１）の評価関数の重み係数“ｗ３”の値を大きくしてからステップＳ１０２に処理を移行しているが、これに限定されない。
【００５６】
例えば、ステップＳ１０６の判定で選択済パターン情報に全てのインスタンスが含まれていないと判定された場合に、上記式（１）の評価関数に、選択済パターン情報に含まれていないインスタンスを含むパターンの利益を高くするような補正項を付加してから、ステップＳ１０２に処理を移行することとしてもよい。これにより、まだ選択されていないインスタンスを含むパターンの利益を相対的に大きくすることが可能となる。
【００５７】
[第２実施形態]
本発明の第２実施形態について説明する。第２実施形態におけるデータ配置装置の構成を図８に示す。第２実施形態におけるデータ配置装置２が、上述した第１実施形態におけるデータ配置装置１と相違する点は、パターン統合部１５を新たに追加した点である。それ以外の構成については、第１実施形態におけるデータ配置装置１の各構成と同様であるため、各構成要素には同一の符合を付し、その説明は省略するとともに、以下においては、主に第１実施形態との相違点について説明する。
【００５８】
パターン統合部１５は、パターン導出部１１によって導出された２つのパターン間の類似度を算出する。類似度は、例えば下記式（５）を用いて算出することができる。
【００５９】
類似度 ＝ ２＊（２つのパターン間で共通するインスタンス数）／（２つのパターンに含まれるインスタンス数の合計）  …  （５）
【００６０】
パターン統合部１５は、算出した類似度が予め設定した閾値よりも高い場合に、類似度を算出したパターンの組に含まれる２つのパターンを、いずれか一つのパターンに統合する。上記閾値は、例えば、統合により削除したパターンがデータを配置する工程に与える影響度を考慮して適宜設定することができる。
【００６１】
利益算出部１２は、パターン統合部１５によって統合された後に残ったパターンと配置先候補のサーバ装置との組合せごとに、利益を算出することになる。
【００６２】
図９を参照して、パターン統合部１５が、３つのインスタンスＩ１、Ｉ２、Ｉ３を含むパターン１と、３つのインスタンスＩ１、Ｉ２、Ｉ４を含むパターン２とを統合する際の手順について説明する。
【００６３】
パターン統合部１５は、上記式（５）を用いて、パターン１とパターン２との間の類似度を算出する。この場合に、類似度は、“２＊２／（３＋３）＝２／３”となる。この類似度“２／３”が閾値以上であれば、いずれか一方のパターンに統合し、閾値未満であれば統合しない。
【００６４】
パターン統合部１５は、パターン１とパターン２とを統合する場合に、いずれか一方のパターンを削除する。削除するパターンは、パターン導出部１１により導出されたパターンに含まれる各インスタンスの数に基づいて、例えば以下のように決定することができる。
【００６５】
ここでの前提条件として、現時点において、インスタンスＩ１が導出されたパターンに全部で１０含まれ、インスタンスＩ２が導出されたパターンに全部で１０含まれ、インスタンスＩ３が導出されたパターンに全部で５含まれ、インスタンスＩ４が導出されたパターンに全部で１０含まれているとする。
【００６６】
パターン１を削除した場合には、インスタンスＩ１、Ｉ２、Ｉ３が１つずつ削除され、パターン２を削除した場合には、インスタンスＩ１、Ｉ２、Ｉ４が１つずつ削除されることになる。したがって、パターン１を削除した場合の影響度は、“（１／１０）＋（１／１０）＋（１／５）＝４／１０”となり、パターン２を削除した場合の影響度は、“（１／１０）＋（１／１０）＋（１／１０）＝３／１０”となる。
【００６７】
この結果、パターン１を削除した場合の影響度が、パターン２を削除した場合の影響度よりも大きいことが判明する。したがって、パターン統合部１５は、パターン２を削除することで、パターン１とパターン２との組をパターン１に統合する。
【００６８】
なお、パターンを削除することで、そのパターンに含まれるいずれかのインスタンスが、導出されたパターンの中に一つも含まれないことになる場合には、もう一方のパターンを削除することとする。これにより、パターンを統合していく過程で特定のインスタンスが導出されたパターンから無くなってしまうことを防止することができる。
【００６９】
また、影響度が等しい場合には、いずれか一方をランダムに選択して削除することができる。
【００７０】
次に、図１０を参照して、第２実施形態におけるデータ配置装置２の動作について説明する。上述した第１実施形態におけるデータ配置装置１の動作と異なるのは、図７に示すステップＳ１０２の処理とステップＳ１０３の処理との間に、パターン統合処理（ステップＳ２００）が追加される点である。なお、上述した第１実施形態におけるデータ配置装置１の動作と同様の処理には同一のステップ符号を付し、その説明は省略する。
【００７１】
図１０のステップＳ２００で行われるパターン統合処理について、図１１を参照して説明する。
【００７２】
最初に、パターン統合部１５は、上記ステップＳ１０２でパターン導出部１１によって導出されたパターンの中から２つのパターンを選択する（ステップＳ２０１）。
【００７３】
続いて、パターン統合部１５は、選択したパターン間の類似度を、例えば上記式（５）を用いて算出する（ステップＳ２０２）。
【００７４】
続いて、パターン統合部１５は、算出した類似度が閾値以上であるか否かを判定する（ステップＳ２０３）。この判定がＮＯである場合（ステップＳ２０３；ＮＯ）には、処理を上記ステップＳ２０１に移行する。
【００７５】
一方、上記ステップＳ２０３の判定で類似度が閾値以上であると判定された場合（ステップＳ２０３；ＹＥＳ）に、パターン統合部１５は、例えば各パターンを削除した場合の影響度を考慮して、いずれか一方のパターンを削除することで、２つのパターンを１つのパターンに統合する（ステップＳ２０４）。
【００７６】
続いて、パターン統合部１５は、上記ステップＳ２０４の統合が所定回数以上実行されたか否かを判定する（ステップＳ２０５）。この判定がＮＯである場合（ステップＳ２０５；ＮＯ）には、処理を上記ステップＳ２０１に移行する。
【００７７】
一方、上記ステップＳ２０５の判定で統合が所定回数以上実行されたと判定された場合（ステップＳ２０５；ＹＥＳ）には、パターン統合処理を終了し、図１０のステップＳ１０３に処理を移行する。
【００７８】
続いて、利益算出部１２は、インスタンス情報記憶部２１、サーバ情報記憶部２２および選択済パターン情報記憶部２３を参照し、パターン統合部１５によって統合された後に残ったパターンと配置先候補のサーバ装置との組合せごとに、そのパターンを選択した場合に得られる利益を算出する（ステップＳ１０３）。そして、ステップＳ１０４以降の処理を、第１実施形態と同様に実行する。
【００７９】
上述したように、第２実施形態におけるデータ配置装置２によれば、パターン統合部１５により統合された後のパターンを、利益算出の対象にすることができるため、利益算出対象を削減することができる。これにより、利益を算出するための計算工数等を削減することができ、第１実施形態に比べ、より高速にデータ配置を決定することができる。
【００８０】
[第３実施形態]
本発明の第３実施形態について説明する。第３実施形態におけるデータ配置装置の構成を図１２に示す。第３実施形態におけるデータ配置装置３が、上述した第１実施形態におけるデータ配置装置１と相違する点は、パターン導出部１１をパターン一部導出部１１ａに変更した点と、利益評価部１６を新たに追加した点である。それ以外の構成については、第１実施形態におけるデータ配置装置１の各構成と同様であるため、各構成要素には同一の符合を付し、その説明は省略するとともに、以下においては、主に第１実施形態との相違点について説明する。
【００８１】
パターン一部導出部１１ａは、インスタンスの組合せの全パターンを導出するのではなく、インスタンスの組合せのパターンのうちの一部のパターンのみを導出する点で、上述した第１実施形態におけるパターン導出部１１と相違する。これにより、利益算出部１２は、パターン一部導出部１１ａによって導出されたパターンと配置先候補のサーバ装置との組合せごとに、利益を算出することになる。
【００８２】
利益評価部１６は、全てのサーバ装置に対して配置するパターンが選択された後に、選択済パターン情報記憶部２３を参照し、選択済みパターンの利益の合計が、予め定めた所定の閾値に到達しているか否かを判定する。上記閾値は、利益の合計とデータ配置後の実際の利益とを比較する実験等を繰り返すことで、最適となる値を適宜設定することができる。
【００８３】
インスタンス配置部１４は、利益評価部１６により選択済みパターンの利益の合計が閾値に到達していると判定された場合に、選択済パターン情報に従ってインスタンスを各サーバ装置に配置する。
【００８４】
パターン一部導出部１１ａは、利益評価部１６により選択済みパターンの利益の合計が閾値に到達していないと判定された場合に、上記一部のパターンを導出し直す。パターン一部導出部１１ａは、パターンを導出し直すときには、前回までに導出したパターンを導出対象から除外する。
【００８５】
選択済パターン情報記憶部２３は、利益評価部１６により選択済みパターンの利益の合計が閾値に到達していないと判定された場合に、現時点で格納している選択済みパターン情報を他の記憶部に移動させ、選択済みパターン情報を他の記憶部に蓄積していく。これにより、選択済パターン情報記憶部２３から選択済みパターン情報を削除し、他の記憶部に選択済みパターン情報を蓄積することができる。なお、他の記憶部に蓄積する情報には、少なくとも選択済みパターン情報のうちの利益に関する情報が含まれていればよい。
【００８６】
次に、図１３を参照して、第３実施形態におけるデータ配置装置３の動作について説明する。上述した第１実施形態におけるデータ配置装置１の動作と異なるのは、図７に示すステップＳ１０２の処理に替えてステップＳ３０１の処理を行うことと、図７に示すステップＳ１０６の処理とステップＳ１０８の処理との間に、ステップＳ３０２の処理が追加されることである。なお、上述した第１実施形態におけるデータ配置装置１の動作と同様の処理には同一のステップ符号を付し、その説明は省略する。
【００８７】
最初に、データ配置指示を受信する（ステップＳ１０１）と、パターン一部導出部１１ａは、インスタンス情報記憶部２１を参照し、インスタンスの組合せのパターンのうちの一部のパターンのみを導出する（ステップＳ３０１）。
【００８８】
続いて、上述した第１実施形態の動作と同様にして、利益算出部１２は、パターン一部導出部１１ａによって導出されたパターンと配置先候補のサーバ装置との組合せごとに利益を算出し（ステップＳ１０３）、パターン選択部１３は、利益算出部１２により算出された利益、およびこれまでに算出されて他の記憶部に蓄積されている利益のうちの最大の利益に対応するパターンを選択し（ステップＳ１０４）、選択パターン情報を、選択済パターン情報記憶部２３に記憶させる。
【００８９】
続いて、上述した第１実施形態の動作と同様にして、パターン選択部１３により全てのサーバ装置に対して配置するパターンが選択されたと判定され（ステップＳ１０５；ＹＥＳ）、パターン導出部１１により選択済パターン情報に全てのインスタンスが含まれていると判定された場合（ステップＳ１０６；ＹＥＳ）に、利益評価部１６は、選択済パターン情報記憶部２３を参照し、選択済みパターンの利益の合計が閾値に到達しているか、または、全てのパターンを導出し終えたか否かを判定する（ステップＳ３０２）。この判定がＮＯである場合（ステップＳ３０２；ＮＯ）には、処理を上記ステップＳ３０１に移行する。
【００９０】
一方、上記ステップＳ３０２の判定がＹＥＳである場合（ステップＳ３０２；ＹＥＳ）に、インスタンス配置部１４は、上述した第１実施形態の動作と同様にして、インスタンスを各サーバ装置に配置する（ステップＳ１０８）。
【００９１】
なお、上記ステップＳ３０２の判定で利益の合計が閾値に到達している場合（ステップＳ３０２；ＹＥＳ）であっても、選択済みパターンの中に、サーバ装置に配置できないパターン（利益が０のパターン）が含まれている場合には、処理を上記ステップＳ３０１に移行することにする。これは、第３実施形態では、一部のパターンしか導出しないため、あるサーバ装置には、どのパターンも配置できない事態が発生することも想定されるためである。
【００９２】
また、閾値の設定によっては全てのパターンを導出し終えた後でも利益の合計が閾値に到達しない場合もあり得るが、その場合には最後に選択されたパターンを用いてインスタンスを配置すればよい。
【００９３】
上述したように、第３実施形態におけるデータ配置装置によれば、パターン一部導出部１１ａにより導出されたパターンを、利益算出の対象にすることができるため、利益算出対象を削減することができる。これにより、利益を算出するための計算工数等を削減することができ、第１実施形態に比べ、より高速にデータ配置を決定することができる。
【００９４】
[第４実施形態]
本発明の第４実施形態について説明する。第４実施形態におけるデータ配置装置の構成を図１４に示す。第４実施形態におけるデータ配置装置４が、上述した第１実施形態におけるデータ配置装置１と相違する点は、クエリ監視部１７およびクエリ解析部１８を新たに追加した点である。それ以外の構成については、第１実施形態におけるデータ配置装置１の各構成と同様であるため、各構成要素には同一の符合を付し、その説明は省略するとともに、以下においては、主に第１実施形態との相違点について説明する。
【００９５】
クエリ監視部１７は、各インスタンスに対して実行されるクエリを監視し、例えば、どのような種類のクエリが、どのインスタンスに対してどのような頻度で実行されたのかを示す情報を記録する。図１５および図１６を参照して、クエリ監視部１７により記録される情報の一例について説明する。
【００９６】
図１５に示すアクセス情報テーブルＴ４は、直近１時間の各インスタンスへのアクセス数に関する情報を格納する。図１６に示す増減情報テーブルＴ５は、直近１時間の各インスタンスへの挿入／削除クエリの数に関する情報を格納する。
【００９７】
図１４に示すクエリ解析部１８は、解析条件が成立した場合に、クエリ監視部１７により記録された情報に基づいて、各インスタンスへのアクセス量やデータの増減量を算出し、インスタンス情報記憶部２１に格納されるインスタンス情報に付加する。以下に、具体的に説明する。
【００９８】
クエリ解析部１８は、例えば、図１５に示すアクセス情報テーブルＴ４に基づいて、インスタンスＩ１のアクセス頻度値として、“１５／（１５＋２５＋５）＝１／３”を算出し、インスタンスＩ２のアクセス頻度値として、“２５／（１５＋２５＋５）＝５／９”を算出し、インスタンスＩ３のアクセス頻度値として、“５／（１５＋２５＋５）＝１／９”を算出する。クエリ解析部１８は、算出したアクセス頻度値を、インスタンス情報記憶部２１のインスタンス情報に付加する。
【００９９】
クエリ解析部１８は、例えば、図１６に示す増減情報テーブルＴ５の挿入／削除クエリ数情報と、インスタンス情報記憶部２１のインスタンス情報に含まれるデータスキーマ情報とに基づいて、各インスタンスのデータの増減数を算出する。クエリ解析部１８は、算出したデータの増減数を、インスタンス情報記憶部２１のインスタンス情報に付加する。
【０１００】
解析条件が成立したか否かの判断基準としては、例えば、所定時間ごとや、実行されたクエリの数が所定以上になったとき、システム管理者により任意のタイミングで指示が入力されたとき等を用いることができる。
【０１０１】
図１４に示す利益算出部１２は、クエリ解析部１８によりインスタンス情報に付加された情報を考慮した評価関数を用いて利益を算出する。評価関数の内容は、例えば、以下のように設定することができる。
【０１０２】
アクセス頻度値が高いインスタンスは、負荷が高くなるため、性能の高いサーバ装置に配置するほど利益が高くなるように評価関数の内容を設定する。また、データが増加傾向にあるインスタンスは、リソース量が多いサーバに配置するほど利益が高くなるように評価関数の内容を設定する。
【０１０３】
次に、図１７を参照して、第４実施形態におけるデータ配置装置４の動作について説明する。上述した第１実施形態におけるデータ配置装置１の動作と異なるのは、データを配置する処理の前段階処理として、クエリを監視／解析する処理が追加されることである。したがって、以下においては、第４実施形態に特有の処理である、クエリを監視／解析する処理について説明する。
【０１０４】
最初に、クエリ監視部１７は、アプリケーションにより発行されるクエリを監視し（ステップＳ４０１）、監視により得られた情報を記録する。
【０１０５】
続いて、解析条件が成立した場合（ステップＳ４０２；ＹＥＳ）に、クエリ解析部１８は、クエリ監視部１７により記録された情報に基づいて、クエリを解析し（ステップＳ４０３）、解析した結果得られた情報を、インスタンス情報記憶部２１のインスタンス情報に付加する。そして、処理を上記ステップＳ４０１に移行する。
【０１０６】
上述したように、第４実施形態におけるデータ配置装置４によれば、システムの稼動後に変動するアクセス量やデータの増減量を考慮してデータを配置することができるため、上述した第１実施形態に比べ、データ配置の精度をより向上させることができる。
【０１０７】
[変形例]
なお、上述した各実施形態は、単なる例示に過ぎず、各実施形態に明示していない種々の変形や技術の適用を排除するものではない。すなわち、本発明は、その趣旨を逸脱しない範囲で様々な形態に変形して実施することができる。
【０１０８】
例えば、上述した各実施形態の一部または全部は、以下の付記のようにも記載され得るが、本発明を以下に限定するものではない。
【０１０９】
（付記１）  複数のサーバ装置に分散配置するデータの配置先を、前記データを管理する単位であるインスタンスごとに決定するデータ配置装置であって、前記インスタンスの組合せのパターンを導出するパターン導出部と、前記パターン導出部によって導出された前記パターンと前記サーバ装置との組合せごとに、前記パターンを選択した場合に得られる利益を算出する利益算出部と、前記利益算出部によって算出された前記利益のうちの最大の利益に対応する前記パターンを選択するパターン選択部と、を備えることを特徴とするデータ配置装置。
【０１１０】
（付記２）  前記パターン導出部によって導出された前記パターン間の類似度を算出し、前記類似度が所定の閾値よりも高い関係にある前記パターンの組が存在する場合に、当該パターンの組に属する複数の前記パターンを、当該パターンの組に含まれるいずれか一つの前記パターンに統合するパターン統合部を、さらに備え、前記利益算出部は、前記パターン統合部によって統合された後に残った前記パターンと前記サーバ装置との組合せごとに、前記利益を算出する、ことを特徴とする付記１記載のデータ配置装置。
【０１１１】
（付記３）  前記パターン導出部は、前記インスタンスの組合せのパターンのうちの一部のパターンを導出し、前記利益算出部によって算出された前記利益の合計が所定の閾値に到達しない場合には、前記一部のパターンを導出し直す、ことを特徴とする付記１記載のデータ配置装置。
【０１１２】
（付記４）  前記利益算出部は、少なくとも、前記インスタンスのデータ量、データ属性、現時点の配置からのデータ移動量、または前記パターン選択部によって前記パターンに選択された前記インスタンスの選択回数のうちのいずれか一つを用いて、前記利益を算出する、ことを特徴とする付記１〜３のいずれかに記載のデータ配置装置。
【０１１３】
（付記５）  前記利益算出部は、さらに、少なくとも、前記インスタンスへのアクセス量、または前記インスタンスのデータ増減量のうちのいずれか一つを用いて、前記利益を算出する、ことを特徴とする付記４記載のデータ配置装置。
【０１１４】
（付記６）  前記パターン選択部により選択された前記パターンに従って、前記インスタンスを前記サーバ装置に配置するインスタンス配置部を、さらに備える、ことを特徴とする付記１〜５のいずれかに記載のデータ配置装置。
【０１１５】
（付記７）  複数のサーバ装置に分散配置するデータの配置先を、前記データを管理する単位であるインスタンスごとに決定するデータ配置方法であって、前記インスタンスの組合せのパターンを導出するパターン導出ステップと、前記パターン導出ステップにおいて導出された前記パターンと前記サーバ装置との組合せごとに、前記パターンを選択した場合に得られる利益を算出する利益算出ステップと、前記利益算出ステップにおいて算出された前記利益のうちの最大の利益に対応する前記パターンを選択するパターン選択ステップと、を含むことを特徴とするデータ配置方法。
【０１１６】
（付記８）  付記７に記載の各ステップをコンピュータに実行させるためのデータ配置プログラム。
【符号の説明】
【０１１７】
１、２、３、４…データ配置装置、１１…パターン導出部、１１ａ…パターン一部導出部、１２…利益算出部、１３…パターン選択部、１４…インスタンス配置部、１５…パターン統合部、１６…利益評価部、１７…クエリ監視部、１８…クエリ解析部、２１…インスタンス情報記憶部、２２…サーバ情報記憶部、２３…選択済パターン情報記憶部。
【図１】
0005733684.tif 000002
【図２】
0005733684.tif 000003
【図３】
0005733684.tif 000004
【図４】
0005733684.tif 000005
【図７】
0005733684.tif 000006
【図８】
0005733684.tif 000007
【図９】
0005733684.tif 000008
【図１０】
0005733684.tif 000009
【図１１】
0005733684.tif 000010
【図１２】
0005733684.tif 000011
【図１３】
0005733684.tif 000012
【図１４】
0005733684.tif 000013
【図１５】
0005733684.tif 000014
【図１６】
0005733684.tif 000015
【図１７】
0005733684.tif 000016
【図５】
0005733684.tif 000017
【図６】
0005733684.tif 000018