(57)【特許請求の範囲】
【請求項１】
複数のデータベースサーバ間のデータベースの作業負荷バランシングのための方法であって、
新しいサーバが利用できるとき、該新しいサーバへマイグレートするマスタ及びスレーブデータベースのセットを選択し、マイグレートするためのコストであるマイグレーションコストを最小としつつ、全てのサーバ間で作業負荷のバランスがとれるように選択されたデータベースをマイグレートし、
動作中に作業負荷の変動により作業負荷のアンバランスをリアルタイムに検出すると、作業負荷のバランスがとれるまで他のサーバへマイグレートするデータベースを一つずつ繰り返し選択する方法。
【請求項２】
所定のデータベース構成の良好度を評価するためのメトリックを適用する請求項１記載の方法。
【請求項３】
前記メトリックは、プロセッサ（ＣＰＵ）使用率及びメモリ使用量を含むシステムリソースである請求項２記載の方法。
【請求項４】
マイグレーションのためのマスタデータベース及びスレーブデータベースのセットを選択する工程は、（ａ）マイグレーション後の予想低減コスト、（ｂ）マイグレーション後の各サーバのマスタ対スレーブ比、及び（ｃ）各データベースのサイズに関連するマイグレーションコスト、を含むファクターを考慮する工程をさらに有する請求項１記載の方法。
【請求項５】
マイグレーション中に前記サーバ間で作業負荷のバランスがとれるようにマイグレーションの最適な順序を選択する工程を有する請求項１記載の方法。
【請求項６】
ホットスポットを解消するために、マイグレートする次のデータベース及び対応するターゲットデータベースサーバを繰り返し選択する工程を有する請求項１記載の方法。
【請求項７】
ホットスポットが解消するまでデータベースを一つずつ繰り返しマイグレートする請求項１記載の方法。
【請求項８】
ｃmem及びｃcpuを、メモリ及びＣＰＵの異なる単位をキャリブレートするためのパラメータとしたとき、
【数１】
0005914699.tif 000024
で決定される分散を含む所定のデータベース構成のためのメトリックを設定する工程を有する請求項１記載の方法。
【請求項９】
ｃmem及びｃcpuが
【数２】
0005914699.tif 000025
及び
【数３】
0005914699.tif 000026
に設定された請求項８記載の方法。
【請求項１０】
複数のデータベースサーバ間のデータベースの作業負荷バランシングのためのシステムであって、
プロセッサと、
前記プロセッサに、新しいサーバが利用できるとき、該新しいサーバへマイグレートするマスタ及びスレーブセットを選択させ、マイグレートするためのコストであるマイグレーションコストを最小としつつ、全てのサーバ間で作業負荷のバランスがとれるように選択されたデータベースをマイグレートさせるための指示を含む、前記プロセッサで実行可能なコードと、
前記プロセッサに、動作中に作業負荷の変動により作業負荷のアンバランスをリアルタイムに検出させ、作業負荷のバランスがとれるまで他のサーバへマイグレートするデータベースを一つずつ繰り返し選択させるための指示を含む、前記プロセッサで実行可能なコードと、
を有するシステム。
【請求項１１】
前記プロセッサに、所定のデータベース構成の良好度を評価するためのメトリックを利用させるためのコードを有する請求項１０記載のシステム。
【請求項１２】
前記メトリックは、プロセッサ（ＣＰＵ）使用率及びメモリ使用量を含むシステムリソースである請求項１１記載のシステム。
【請求項１３】
マイグレーションのためのマスタデータベース及びスレーブデータベースのセットを選択するためのコードは、
前記プロセッサに、（ａ）マイグレーション後の予想低減コスト、（ｂ）マイグレーション後の各サーバのマスタ対スレーブ比、及び（ｃ）各データベースのサイズに関連するマイグレーションコスト、を含むファクターを考慮させるためのコードをさらに有する請求項１０記載のシステム。
【請求項１４】
前記プロセッサに、マイグレーション中に前記サーバ間で作業負荷のバランスがとれるようにマイグレーションの最適な順序を選択させるためのコードを有する請求項１０記載のシステム。
【請求項１５】
ホットスポットを解消するために、前記プロセッサに、マイグレートする次のデータベース及び対応するターゲットデータベースサーバを繰り返し選択させるためのコードを有する請求項１０記載のシステム。
【請求項１６】
前記プロセッサに、ホットスポットが解消するまでデータベースを一つずつ繰り返しマイグレートさせるためのコードを有する請求項１０記載のシステム。
【請求項１７】
ｃmem及びｃcpuを、メモリ及びＣＰＵの異なる単位をキャリブレートするためのパラメータとしたとき、前記プロセッサに、
【数４】
0005914699.tif 000027
で決定される分散を含む所定のデータベース構成のためのメトリックを設定させるためのコードを有する請求項１０記載のシステム。
【請求項１８】
ｃmem及びｃcpuを
【数５】
0005914699.tif 000028
及び
【数６】
0005914699.tif 000029
に設定するためのコードを有する請求項１７記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
この出願は、２０１２年４月４日に出願された米国仮出願番号６１６２０１５１号を基礎とし、その開示の全てをここに取り込む。
【０００２】
本発明はデータベースの作業負荷バランシングに関する。
【背景技術】
【０００３】
企業では、様々な経済的及びビジネス上の理由により、データセンタを構築する目的でバックエンドコンピュータシステムの中央集約化が進んでいる。データセンタは、一般にコンピュータシステムを高集中度及び高密度で収容し、さらに顧客のニーズをサポートするデータベースを提供する。データセンタのオペレータは、サーバボックスを確保し、刻々と変化する作業負荷に備えてリソースを準備しなければならない。さらに、多様な作業負荷で同じ物理ボックス上のリソースを共有することや、作業負荷に対するプロビジョニングでは物理リソースの容量制約等の物理上の制約を考慮する必要がある。近年は、データセンタオペレータへ絶好の機会や課題を提示するデータ集約型コンピューティングのためのクラウドコンピューティングへ移行している。
【０００４】
データセンタオペレータが直面する一つのキーとなる課題は、顧客の作業負荷のためのデータセンタにおけるリソースのプロビジョニングである。例えば、新しいサーバが追加されると、既存の各サーバは、
・新しいサーバに共同設置されるマスタ・スレーブの組み合わせが無い、
・マスタ対スレーブ比が全サーバでほぼ同一である、
・メモリ容量及びＣＰＵ容量が全サーバで可能な限りバランスがとれている、
・データ量の移動が最小である、
となるように、該新しいサーバへマイグレートする（移行する）マスタ及びスレーブセットを提供する。
【０００５】
他の問題は、ホットスポットの解消である。所定のサーバ構成において、過負荷のサーバが在る場合（メモリホットスポット、ＣＰＵホットスポット、またはその両方であるとき、サーバは過負荷である）、各過負荷サーバから一つのマスタをマイグレートすることでサーバの過負荷状態が解消される。
【０００６】
連合データベース（Federated databases）は、個々のサーバ間のリレーションが手動で分割され、統一された方式でクライアントに公開されることで用いられてきた。しかしながら、そのような解決法では、マニュアルによる機器設定、特殊なマージング・ラッパー・アルゴリズム、動的な再バランシングがサポートされない問題を引き起こす。
【０００７】
他の解決法として、作業負荷に基づいてスレーブデータベースを追加または削除する方法がある。しかしながら、スレーブデータベース（複製）はリードクエリをサポートするだけであり、全てのライトクエリはマスタへ渡さなければならないため、そのような解決法は作業負荷に多くのライトクエリを含む場合に役に立たない。さらに、スレーブの追加には長い時間を要するため、この解決法は早い作業負荷の変動を扱うことができない。
【０００８】
その他のアプローチとして、作業負荷をマスタＤＢとそのスレーブとで異なるようにすることが考えられる。その場合、マスタとスレーブの役割、またはマスタとスレーブとを交換することで、作業負荷のバランスが保たれる。しかしながら、そのような方法は、マスタとスレーブの作業負荷が大きく異なり、ＤＢシステムがスワッピングをサポートしているときにのみ有効である。さらに他の方法として、（ａ）同じサーバにおける異なる仮想マシン間でリソースの割り当てを変更する、（ｂ）サーバを追加及び削除する、ことで負荷バランシングが達成される。しかしながら、そのような方法は、各ＤＢインスタンスが一つの仮想マシンでラップされ、各サーバが全てのＤＢを含んでいなければならないため（全ＤＢの全マスタ、または各ＤＢの１スレーブのいずれか一方）、該方法を適用できる範囲が制限される。
【発明の概要】
【０００９】
本発明の一態様は、複数のデータベースサーバ間のデータベースの作業負荷バランシングのための方法であって、新しいサーバが利用できるとき、該新しいサーバへマイグレートするマスタ及びスレーブデータベースのセットを選択し、マイグレーションコストを最小としつつ、全てのサーバ間で作業負荷のバランスがとれるように選択されたデータベースをマイグレートし、動作中に作業負荷の変動により作業負荷のアンバランスをリアルタイムに検出すると、作業負荷のバランスがとれるまで他のサーバへマイグレートするデータベースを一つずつ繰り返し選択する。
【００１０】
好ましい実施例の優れた点は以下の通りである。本システムでは、リアルタイムなデータベース・マイグレーションを用いることで、データベースの作業負荷バランシングを達成する。このような解決法は、レスポンスタイムが速く、手動による介入を最小限とし、目標関数として様々な特性（メモリ及びＣＰＵのフットプリント等）やメトリック（作業負荷分散、作業負荷変動のＬ１ノルム、サーバにおけるマスタ／スレーブ比等）を利用できる。本システムでは、データベースの作業負荷バランシングを達成することで、全データベース及び全サーバの総合的なシステムパフォーマンスが最適化される。高速な動作が達成される。本システムでは、メモリ常駐型データベースのライブマイグレーション技術を活用するため、動作が速くなり、作業負荷の変動への反応も早くなる。本システムでは、作業負荷のランニングコストが最小となる、費用効率が高いデータベースの配置を素早く見出せる。本システムは、動作中における作業負荷の総動作コスト（ＴＯＣ：Total Operating Cost）を最小化しつつ、個別の作業負荷に備えて準備するデータセンタオペレータを支援する。作業負荷バランシングは、マイグレーションによってリアルタイムに達成でき、多くのデータベースシステムに要求されるＡＣＩＤ特性（Atomicity（原子性、不可分性）、Consistency（一貫性）、Isolation（独立性）、Durability（永続性））が保証される。
【図面の簡単な説明】
【００１１】
【図１】サーバ間のデータベースマスタまたはスレーブのマイグレーションで達成される作業負荷バランシングの一例を示す図である。
【図２Ａ】Ｎ＝２における、容量バランスがとれた状態を意味する低分散を説明する図である。
【図２Ｂ】Ｎ＝３における、容量バランスがとれた状態を意味する低分散を説明する図である。
【図３】最適なテナントが存在しない様子を示す図である。
【図４】ホットスポット解消問題を示す図である。
【図５】複数のリソース、すなわちメモリ及びＣＰＵで与えられるメモリホットスポットを示す図である。
【図６】データベースバランシングを実行するコンピュータの一例を示す図である。
【発明を実施するための形態】
【００１２】
図１は、サーバ間のデータベースマスタまたはスレーブのマイグレーションで達成される作業負荷バランシングの一例を示す図である。
【００１３】
ＳＶ１−ＳＶ４は４台のサーバを示し、Ｍ１−Ｍ３は３台のデータベースマスタを示し、各データベースマスタが対応する２台のデータベーススレーブ（レプリカ）を備えている。したがって、Ｓ１１及びＳ１２はＭ１のスレーブである。第１に、新しいサーバが作業負荷の取り扱いを開始すると、本システムは、該新しいサーバへマイグレート（移行）するマスタ及びスレーブデータベースのセットを選択する。マイグレートさせる選択されたデータベースは、マイグレーションコストを最小にしつつ、全ての（新しいサーバを含む）サーバの作業負荷バランスが最もとれる結果をもたらす。新しいサーバは、マスタ対スレーブ比が既存のサーバのそれと同様になる（すなわち、新しいサーバはマイグレーション完了後には他の既存サーバと同様になる）。第２に、動作中、例えば任意のデータベースの作業負荷が変動することで、作業負荷のアンバランスがリアルタイムに検出されると、作業負荷のバランスをとるために、他のサーバへマイグレートするデータベースを一つずつ繰り返し選択する。
【００１４】
一実施例において、Ｍ台のデータベースはＮ台のサーバでホストされる。各データベースは、プライマリＤＢ（マスタ）と、他のサーバでホストされる、１つまたは複数のセカンダリＤＢ（スレーブ）とを有する構成である。すなわち、マスタＤＢは、自身のスレーブと同じサーバに配置されず、同じマスタに属する２台のスレーブは同じサーバに配置されない。
【００１５】
各データベースは、時々刻々と変化するＣＰＵ使用率及びメモリ使用量のようなシステムリソースのフットプリントを備えている。各サーバは、サーバが過負荷と考えられる状態を超える、最大リソース容量を備える。各リソースは、相加的であると見做される、すなわちサーバリソース使用量はサーバでホストされる全てのデータベースの各リソース使用量の合計となる。このような前提はＣＰＵ使用率及びメモリ使用量の分野で一般的に受け入れられる。本システムは、ＤＢのライブマイグレーション、例えばＮＥＣ  ＴＡＭ等のシステムが提供するリアルタイムマイグレーション機能、を実行することが好ましい。以下、各種の用語について詳述する。
【００１６】
・本システムはN台のサーバＳＶ１，…，ＳＶＮで構成される。
【００１７】
・サーバＳＶｉはＫｉ（ｔｉ１，…，ｔｉｋｉ）台のテナントを収容する（注：各サーバは異なる数のテナントを有していてもよい）。
【００１８】
・各テナントｔｉｋはマスタまたはスレーブのいずれか一方となる。マスタとなるテナントは、そのスレーブと同一のＴＡＭサーバに配置されない。
【００１９】
・各テナントｔｉｋは，メモリ使用量ｔｉｋ．ｍｅｍのフットプリント及びＣＰＵ使用率ｔｉｋ．ｃｐｕのフットプリントを備える。
【００２０】
・メモリ使用量及びＣＰＵ使用率はサーバＳＶｉにおいて相加的であり、総メモリ使用量は
【００２１】
【数１】
0005914699.tif 000002
【００２２】
であり、総ＣＰＵ使用率は
【００２３】
【数２】
0005914699.tif 000003
【００２４】
である。
【００２５】
・メモリユニット及びＣＰＵユニットは各サーバどうしで互換性がある（例えば、メモリユニットはギガバイトであり、ＣＰＵユニットはギガサイクル／秒である）。
【００２６】
・各サーバＳＶｉには、通常時は超えない値であるメモリ閾値ＳＶｉ．ｍｅｍＴｈ及びＣＰＵ閾値ＳＶｉ．ｃｐｕＴｈがある。本明細書では、メモリ閾値またはＣＰＵ閾値のいずれか一方を越えた場合、サーバがホットスポット（メモリホットスポットまたはＣＰＵホットスポット）になったと称す。
【００２７】
・各サーバＳＶｉには、メモリ容量ＳＶｉ．ｍｅｍＣａｐ（ＳＶｉがメモリホットスポットになる前の空きメモリ容量）及びＣＰＵ容量ＳＶｉ．ｃｐｕＣａｐがある。ＳＶｉ．ｍｅｍＣａｐ＜０またはＳＶｉ．ｃｐｕＣａｐ＜０の場合、サーバＳＶｉはホットスポットになる。
【００２８】
各サーバＳＶｉに関して、
・ＳＶｉ．ｍｅｍＣａｐ：サーバＳＶｉのメモリ容量。
【００２９】
・ＳＶｉ．ｃｐｕＣａｐ：サーバＳＶｉのＣＰＵ容量。
【００３０】
・ＳＶｉ．ｍｅｍＴｈ：越えるとＳＶｉがメモリホットスポットになる、サーバＳＶｉのメモリ閾値。
【００３１】
・ＳＶｉ．ｃｐｕＴｈ：越えるとＳＶｉがＣＰＵホットスポットになる、サーバＳＶｉのＣＰＵ閾値。
【００３２】
・ＳＶｉ．ｔｅｎａｎｔｓ：サーバＳＶｉに属するテナント｛ｔｉ１，…，ｔｉＫｉ｝である。
【００３３】
【数３】
0005914699.tif 000004
【００３４】
である各テナントｔｉｋに関して、
・ｔｉｋ．ｔｉｄ：ｔｉｋのテナントＩＤ。
【００３５】
・ｔｉｋ．ｉｓＭａｓｔｅｒ：ｔｉｋがマスタ（またはスレーブ）であることを示すブールフラグ。
【００３６】
・ｔｉｋ．ｍｅｍ：ｔｉｋのメモリ使用量。
【００３７】
・ｔｉｋ．ｃｐｕ：ｔｉｋのＣＰＵ使用率。
【００３８】
・ｔｉｋ．ｄａｔａＳｉｚｅ：ｔｉｋのデータサイズである。
【００３９】
Ｎ個の数値｛ｘ１，…，ｘＮ｝の平均値μｘ及び分散σｘ２は、以下のように定義される。
【００４０】
【数４】
0005914699.tif 000005
【００４１】
上記式において、小さい分散は各サーバのバランスがとれていることを意味する。｛ｘ１，…，ｘＮ｝を各サーバのリソース容量（メモリまたはＣＰＵ）とすると、｛ｘ１，…，ｘＮ｝が低分散であるとき、各サーバ間のバランスがとれている状態を意味する。すなわち、
【００４２】
【数５】
0005914699.tif 000006
【００４３】
が変化しない場合、ｘ１＝…＝ｘＮのときにσｘ２が最小となる。σｘ２は各サーバのリソース容量のバランスを評価するのに有益なメトリックとなる。
【００４４】
図２Ａは、Ｎ＝２における、容量バランスがとれた状態を意味する低分散を説明する図である。ｘ１＋ｘ２＝ｃとし、ｃ＝２μｘを定数としたとき、本システムでは単純にｘ１及びｘ２に値を再配分する。ｘ１＋ｘ２＝２μｘであるため、全ての｛ｘ１，ｘ２｝のペアは図に示された線上に配置される。図１には、σｘ２が同じ値となる等値線が示されている（それらは円状になる）。図示されるように、ｘ１=ｘ２＝μｘのとき、σｘ２が最小値０になり、それ以外は、｛ｘ１，ｘ２｝がよりアンバランスな高分散状態である。これは、Ｎ＞２のときも成立する。一例として、図２Ｂは、Ｎ＝３における、容量バランスがとれた状態を意味する低分散を説明する図である。
【００４５】
ＳＶｉがリソース（例えばメモリ）容量ｘｉのホットスポットサーバであり、ＳＶｊがリソース容量ｘｊの軽負荷サーバであり、本システムがリソース使用量ΔのテナントをＳＶｉからＳＶｊへマイグレートする場合、各サーバ間の容量の分散の低減は、
【００４６】
【数６】
0005914699.tif 000007
【００４７】
である。ここで、この分散低減をΔの関数として扱うと、
【００４８】
【数７】
0005914699.tif 000008
【００４９】
であり、マイグレートすべき最良のテナントはリソース使用量が
【００５０】
【数８】
0005914699.tif 000009
【００５１】
のテナントであり、マイグレーションの結果として、分散の変化は、
【００５２】
【数９】
0005914699.tif 000010
【００５３】
となる。
【００５４】
上記解決法は最大リソース容量を選択することである。テナントのリソース使用量は離散値であり、図３の最適なΔ＊へ到達しない例で示すように、最も近いテナントのリソース使用量はΔ１とΔ２であり、リソース使用量がΔ＊のテナントを見出せるとは限らない。図３は最適なテナントが存在しない場合の様子を示している。
【００５５】
次に、新しいサーバのマイグレーションプロセスについて説明する。新しいサーバの追加に伴って既存の各サーバは、
・新しいサーバに共同設置されたマスタ・スレーブが無いこと、
・全てのサーバでマスタ対スレーブ比がほぼ同じであること、
・全てのサーバでメモリ容量及びＣＰＵ容量のバランスができるだけとれていること、
・移動させるデータ量が最小であること、
となるように、該新しいサーバへマイグレートするマスタ及びスレーブセットを提供する。
【００５６】
新しいサーバへＤＢをマイグレートする一方法例１のための疑似コードは以下のようになる。
【００５７】
【表１】
0005914699.tif 000011
【００５８】
既存のＮ台のサーバ｛ＳＶ１，…，ＳＶＮ｝のリソース使用量をＸ＝｛ｘ１，…，ｘＮ｝としたとき、説明のために一つのリソースＸを抽出する。ここで、新しいサーバＳＶＮ＋１が本システムに組み込まれる。各既存サーバから新しいサーバに対するマスタ及びスレーブ提供後のＮ＋１台のサーバのリソース使用量をＹ＝｛ｙ１，…，ｙＮ，ｙＮ＋１｝とする。マイグレーション後のリソース使用量の平均値及び分散は、
【００５９】
【数１０】
0005914699.tif 000012
【００６０】
となる。ここで、テナント構成により
【００６１】
【数１１】
0005914699.tif 000013
【００６２】
とはならない。
【００６３】
方法１は何度も利用及び起動できる。問題は、ＳＶＮ＋１が当初は空き状態である点で異なることである。つまり、空き状態のＳＶＮ＋１がすばやく満たされることは、方法１のグリーディネイチャーが既存サーバの大きなテナントのマイグレートを促し、そのためにＳＶＮ＋１に大きなテナントのみ搭載される結果となり、同時に既存サーバ容量に大きなホールが残される（例えば、マイグレートさせた大きなテナントを有するサーバもあれば、マイグレートさせたテナントが無いサーバもある）。
【００６４】
上記の検討に基づき、方法２は新しいサーバの分散を考慮しない。すなわち、各繰り返し処理において、本方法は新しいサーバＳＶＮ＋１へマイグレートするテナントｔを検索し、既存のＮ台のサーバ（μＸに代わってμＹに関して）の分散低減を最大化する。
【００６５】
【数１２】
0005914699.tif 000014
【００６６】
【表２】
0005914699.tif 000015
【００６７】
上記のように、方法２は新しいサーバのマイグレーションに利用できる。方法２において、｛ＳＶ１，…，ＳＶＮ｝には｜Ｍ｜マスタ及び｜Ｓ｜スレーブがある。そして、本方法は新しいサーバＳＶＮ＋１へマイグレートする｜Ｍ｜／（Ｎ＋１）マスタ及び｜Ｓ｜／（Ｎ＋１）スレーブを選択する。方法２では、｜Ｍ｜／（Ｎ＋１）マスタを選択することをパラメータ
【００６８】
【数１３】
0005914699.tif 000016
【００６９】
と称し、｜Ｓ｜／（Ｎ＋１）スレーブを選択することをパラメータ
【００７０】
【数１４】
0005914699.tif 000017
【００７１】
と称す。Ｑは、分散低減により対象をソートする、優先度付きキューである。
【００７２】
方法２において、
・ライン２−５は、リソース使用量の平均値μｍｅｍ及びμＣＰＵ（新しいサーバＳＶＮ＋１を含む）を計算する。
・ライン６−９は、各サーバにおけるマイグレーションのための最良のテナント候補を抽出する。これらの候補は、他のサーバに相談することなく、各サーバでローカルに決定できる。
・ライン１１−１４は、Ｎ台のサーバから最良の候補をＳＶＮ＋１へ移動する。
・ライン１５−２４は、各サーバの最良のテナント候補を更新する。スレーブをマイグレートする場合、ＳＶＮ＋１へ新たに移動させるスレーブは、他のサーバでは最良の候補から除外されるため、再計算が必要となる。
【００７３】
次に、ホットスポットの解消問題について説明する。所定のデータベース構成で過負荷サーバ（ＳＶｉ．ｍｅｍＣａｐ＜０であるメモリホットスポット、またはＳＶｉ．ｃｐｕＣａｐ＜０であるＣＰＵホットスポット、あるいはその両方）がある場合、各過負荷サーバから一つのマスタをマイグレートすることでサーバの過負荷状態が解消される。このことは図１に示されている。
【００７４】
ところで、実際にはリソースＸは一つではなく、２つのリソース（ｍｅｍＣａｐ，ｃｐｕＣａｐ）がある。これは、（１）ホットスポットをどのように定義するか、（２）各サーバ間のバランスをどのように評価するかの２点に影響を与える。（１）について、新しいサーバＳＶｉが、ＳＶｉ．ｍｅｍＣａｐ＜０またはＳＶｉ．ｃｐｕＣａｐ＜０であると、ホットスポットとなる。このケースではホットスポットが解消されなければならない。このことは、複数のリソース、すなわちメモリとＣＰＵとで定められるメモリホットスポットを説明する図５に示されている。
【００７５】
（２）について、単純な解決法として、メモリ容量の分散とＣＰＵ容量の分散とを組み合わせる方法を用いることができる。
【００７６】
【数１５】
0005914699.tif 000018
【００７７】
ここで、ｃｍｅｍ及びｃｃｐｕは、メモリとＣＰＵの異なる単位（ＧＢ  ｖｓ．  Ｇ−ｃｙｃｌｅ−ｐｅｒ−ｓｅｃ）をキャリブレートするためのパラメータである。
【００７８】
また、ｃｍｅｍ及びｃｃｐｕは、メモリとＣＰＵのバランスのエンファシスを制御するために用いることができる。例えば、ＣＰＵ使用率はバースト性であり、メモリ使用量は比較的安定であるため、ＣＰＵ使用率のバランスはメモリ使用量のバランスよりも重要になる。特別なケースでは
【００７９】
【数１６】
0005914699.tif 000019
【００８０】
及び
【００８１】
【数１７】
0005914699.tif 000020
【００８２】
に設定される。
【００８３】
このように設定すると、本システムは、μｍｅｍＣａｐ及びμｃｐｕｃａｐの両方を１に正規化し、メモリとＣＰＵのバランスを等しい重要度で扱う。この考え方は方法３のライン７，８及び１１に反映されている。
【００８４】
各テナントは異なるデータサイズであるため、それらをマイグレートするためのコストも異なる。一つの解決法は、ｔのマイグレートによる分散低減とｔのマイグレートによるコストの比のような目的関数を見直すことである。例えば、ｔのマイグレーションコストがｔのデータサイズと比例するとき、新しいメトリックを
【００８５】
【数１８】
0005914699.tif 000021
【００８６】
とする。ここで、σ２（ｔ）はｔをマイグレートした場合の分散低減である。
【００８７】
マスタは、そのスレーブと同じサーバに配置できない。そのため、ホットスポットサーバのマスタは無作為に選んだサーバへマイグレートできない。このことはアルゴリズムでチェックされる。すなわち、本システムでは、マイグレーション候補であるテナントｔ用に、ｔのスレーブを搭載しないターゲットサーバのみを考慮する。
【００８８】
本システムは、既存のホットスポットを解消し、新しいホットスポットを発生させないテナント候補及びターゲットサーバを検討する。そのような解決法が無い場合、本アルゴリズムはヌル位置へ戻る。
【００８９】
本アルゴリズムに対する入力は｛ＳＶ１，…，ＳＶＮ｝である。これらのサーバで一つ以上のホットスポットがあれば、本アルゴリズムによる解決法は全てのホットスポットに対処すべきである。このことは、より困難な問題を引き起こす。本発明では、ホットスポットを一つずつ解消するローカルなグリーディ・ヒューリスティックを用いる方法を選択する。すなわち、（１）各サーバのホットスポットをそれぞれ該ホットスポットのみであると見做して対処する、（２）ホットスポットに対処する度に、本システムの構成を仮更新する、（３）そして、仮更新したシステム構成により次のホットスポットに対処する、（４）もし全てのホットスポットを解消する最終構成へ到達できない場合、アルゴリズムは失敗を宣言する。
【００９０】
このことは、（１）対処したホットスポットの順序を監視し、（２）各ホットスポットについて、次のホットスポットを解消しやすくする、あまりグリーディではないグリーディ法で解決策を見つけるため、ヒューリスティックであることに留意する。
【００９１】
図４は、データベース・マイグレーションを用いる、データベースサーバにおけるデータベースの作業負荷バランシングのプロセス例を示している（２０１）。本方法は、各サーバの作業負荷のバランスがとれるように、既存サーバのセットから新たに利用可能なサーバへデータベースのセットをマイグレートする工程（２０２）と、各サーバの作業負荷のバランスがとれるように、既存のデータベースサーバのデータベースをマイグレートする工程とを含む（２０９）。本プロセスでは、所定のデータベース構成の良好度を評価するメトリックを用いる（２０３）。また、本プロセスでは、新しいサーバへマイグレートするデータベースマスタ及びスレーブの配列を選択する（２０４）。２０５において、メトリックには、ＣＰＵ使用率やメモリ使用量等の様々なシステムリソースが考慮される。２０６において、該メトリックは、重み付け戦略及びベクトルノルム（ユークリッド・ノルムまたはＬ１ノルム）による統合された方法における異なるファクターを併せ持つ。
【００９２】
次に２０４を検討すると、本方法は、新たに利用できるサーバへマイグレートするマスタデータベース及びスレーブデータベースのセットを選択する工程を含む。２０７において、選択工程では、（ａ）マイグレーション後の予想低減コスト、（ｂ）マイグレーション後の各サーバのマスタ対スレーブ比、及び（ｃ）各データベースのサイズに関連するマイグレーションコスト、を含む各種ファクターを考慮する。２０８において、本方法は、マイグレーションプロセス中に本システムへ影響を与える負のパフォーマンスが最小となるように、最適なマイグレーションの順序を選択する。
【００９３】
本方法は、各サーバの作業負荷のバランスがとれるように、既存のデータベースサーバのデータベースをマイグレートする工程を含む（２０９）。メトリックは、所定のデータベース構成の良好度の評価に用いられる（２１０）。２１２において、メトリックにはＣＰＵ使用率やメモリ使用量のような様々なシステムリソースが考慮される。２１３において、メトリックは、重み付け戦略やベクトルノルム（ユークリッド・ノルムまたはＬ１ノルム）による統合された方法における異なるファクターを併せ持つ。
【００９４】
または、２１１において、本方法は、全てのホットスポットを解消するために、マイグレートする次のデータベースと対応するターゲットデータベースサーバとを繰り返し選択する工程を含む。２１４において、本方法では、マイグレートする次のデータベースと対応するターゲットサーバとを効率よく選択する。２１５において、本方法では、全てのホットスポットが解消されるまでデータベースを一つずつ繰り返しマイグレートする。
【００９５】
【表３】
0005914699.tif 000022
【００９６】
【表４】
0005914699.tif 000023
【００９７】
図６は、データベースバランシングを実行するコンピュータの一例を示している。本システムは、ハードウェア、ファームウェア、ソフトウェア、またはそれらの組み合わせによって実現される。好ましくは、本発明は、プロセッサ、データストレージシステム、揮発性及び不揮発性メモリおよび／またはストレージ素子、少なくとも１つの入力装置、並びに少なくとも１つの出力装置を備えるプログラム可能なコンピュータによりコンピュータプログラムを実行することで実現される。
【００９８】
次に、一例として、本システムをサポートするコンピュータについて、図６のブロック図を用いて説明する。本コンピュータは、好ましくは、ＣＰＵバスに接続された、プロセッサ、ランダムアクセスメモリ（ＲＡＭ）、プログラムメモリ（好ましくは、フラッシュＲＯＭのような書き換え可能なリードオンリーメモリ（ＲＯＭ））及びインプット／アウトプット（ＩＮＰＵＴ／ＯＵＴＰＵＴ：Ｉ／Ｏ）コントローラを備える。本コンピュータは、ＣＰＵバスによってハードディスクと接続されたハードドライブコントローラを備えていてもよい。ハードディスクは、本発明を実現するためのアプリケーションプログラムやデータを保存するために使用される。アプリケーションプログラムはＲＡＭやＲＯＭで保存されていてもよい。Ｉ／Ｏコントローラは、Ｉ／ＯバスによりＩ／Ｏインタフェースと接続される。Ｉ／Ｏインタフェースは、シリアルリンク、ローカルエリアネットワーク、無線リンク及びパラレルリンク等の通信リンクを通じて、アナログまたはデジタル形式でデータを送受信する。Ｉ／Ｏバスには、ディスプレイ、キーボード及びポインティングデバイス（マウス）が接続されていてもよい。また、Ｉ／Ｏインタフェース、ディスプレイ、キーボード及びポインティングデバイス用に、セパレートコネクション（セパレートバス）を使用してもよい。プログラム可能な処理システムは、事前にプログラムされていてもよく、他のソース（例えば、フロッピーディスク、ＣＤ−ＲＯＭ、あるいは他のコンピュータ）からプログラムをダウンロードすることでプログラム（または再プログラム）されてもよい。
【００９９】
コンピュータプログラムは、通常または特別な目的を持つプログラム可能なコンピュータで読み取ることができる、機械で読み取り可能なストレージメディアまたは装置（例えば、プログラムメモリまたは磁気ディスク）に格納される。コンピュータプログラムは、ストレージメディアまたは装置から本明細書に記載された手順を実行するコンピュータで読み出される、該コンピュータの設定及び制御動作のためのものである。本発明のシステムには、本明細書に記載した機能を実行する、特定の及び事前に定義された方法でコンピュータに動作させるように構成されたコンピュータプログラムを含む、コンピュータで読み取り可能なストレージメディアも考慮される。
【０１００】
上述した本システムは、特許法に適合し、当業者に新しい原理の適用に必要な情報を提供し、必要に応じて要求される専用のコンポーネントを構成するように、本明細書で詳細に説明されている。しかしながら、本発明は、他の設備や装置で実行することが可能であり、設備の細部及び手順の動作の両方で、発明の要旨を逸脱しない範囲で種々の変更でも達成できることを理解されたい。
【図１】
0005914699.tif 000030
【図２Ａ】
0005914699.tif 000031
【図２Ｂ】
0005914699.tif 000032
【図３】
0005914699.tif 000033
【図４】
0005914699.tif 000034
【図５】
0005914699.tif 000035
【図６】
0005914699.tif 000036