(57)【要約】      （修正有）【課題】複数のジョブで共有される物理資源をプロビジョニングするためのシステムを提供する。【解決手段】動作中、システムは、ジョブに対する資源使用モデルを確立し、これらのジョブに関連付けられたサービス品質（ＱｏＳ）要件に基づいてジョブを格付けし、上位ＱｏＳ格付けを有しているジョブの第１の部分集合に関連付けられた任意の未使用の予約が他の残存ジョブのうち最上位のＱｏＳ格付けを有しているジョブの第２の部分集合の方を優先させて他の残存ジョブへ分布されるように所定の時間インターバルに対してジョブをプロビジョニングする。ジョブのプロビジョニングは、資源使用モデルとジョブに関連付けられた対応するＱｏＳ要件とに基づいて、ジョブに対して予約を行う。【選択図】図４
2013175178.tif 000002
【特許請求の範囲】
【請求項１】
複数のジョブによって共有される物理資源をプロビジョニングするためのコンピュータ実行可能な方法であって、
前記ジョブに対して資源使用モデルを確立するステップと、
前記ジョブに関連付けられたサービス品質（ＱｏＳ）要件に基づいて前記ジョブを格付けするステップと、
上位ＱｏＳ格付けを有しているジョブの第１の部分集合に関連付けられた任意の未使用の予約が、他の残存ジョブのうち最上位のＱｏＳ格付けを有しているジョブの第２の部分集合の方を優先させて前記他の残存ジョブへ分布されるように、所定の時間インターバルに対して前記ジョブをプロビジョニングするステップであって、前記ジョブのプロビジョニングが前記資源使用モデルと前記ジョブに関連付けられた対応するＱｏＳ要件に基づいて前記ジョブに対して予約を行うことを含む、ステップと、
を含む、方法。
【請求項２】
コンピュータで実行されると、複数のジョブによって共有された物理資源をプロビジョニングするための方法を前記コンピュータに実行させる命令を記憶しているコンピュータ読出可能記憶媒体であって、
前記方法が、
前記ジョブに対して資源使用モデルを確立するステップと、
前記ジョブに関連付けられたサービス品質（ＱｏＳ）要件に基づいて前記ジョブを格付けするステップと、
上位ＱｏＳ格付けを有しているジョブの第１の部分集合に関連付けられた任意の未使用の予約が、他の残存ジョブのうち最上位のＱｏＳ格付けを有しているジョブの第２の部分集合の方を優先させて、前記他の残存ジョブへ分布されるように、所定の時間インターバルに対して前記ジョブをプロビジョニングするステップであって、前記ジョブのプロビジョニングが前記資源使用モデルと前記ジョブに関連付けられた対応するＱｏＳ要件に基づいて前記ジョブに対して予約を行うことを含む、ステップと、
を含むことよりなる、コンピュータ読出可能記憶媒体。
【請求項３】
複数のジョブによって共有された物理資源をプロビジョニングするための計算システムであって、
前記ジョブに対して資源使用モデルを構築するように構成されている資源使用モデル構築子と、
前記ジョブに関連付けられたサービス品質（ＱｏＳ）要件に基づいて前記ジョブを格付けするように構成されている格付けメカニズムと、
上位ＱｏＳ格付けを有しているジョブの第１の部分集合に関連付けられた任意の未使用の予約が、他の残存ジョブのうち最上位のＱｏＳ格付けを有しているジョブの第２の部分集合の方を優先させて前記他の残存ジョブへ分布されるように、所定の時間インターバルに対して前記ジョブをプロビジョニングするように構成されているプロビジョニングメカニズムであって、前記ジョブのプロビジョニングが前記資源使用モデルと前記ジョブに関連付けられた対応するＱｏＳ要件に基づいて前記ジョブに対して予約を行うことを含むプロビジョニングメカニズムと、
を含む計算システム。
【請求項４】
前記ジョブをプロビジョニングしている間、前記プロビジョニングメカニズムが、
前記ジョブに関連付けられた対応するＱｏＳ格付けに基づいて前記ジョブへ異なる数の共有を割り当て、それぞれのジョブに割り当てられた前記共有の数が前記それぞれのジョブのＱｏＳ格付けに逆相関され、
ジョブの前記第１の部分集合に関連付けられた未使用の予約が前記他の残存ジョブに割り当てられた共有数に基づいて前記他の残存ジョブへ比例分布されることを前提に予約を割当てる、
ように構成されている、請求項３に記載のシステム。
【請求項５】
前記ジョブをプロビジョニングしている間、前記プロビジョニングメカニズムが、
ＱｏＳ格付けに基づいて降順に前記ジョブを仕分するように構成され、かつ、
最上位のＱｏＳ格付けを有しているジョブからスタートして、
次のインラインジョブを直前に形成されたサブグループに加算することによってサブグループを形成するステップと、
前記サブグループに対して資源使用モデルを確立するステップと、
前記サブグループに対する前記資源使用モデルと前記次のインラインジョブに関連付けられたＱｏＳ要件に基づいて前記サブグループによって必要とされる資源要求量を算定するステップと、
を反復するように構成されている、請求項３に記載のシステム。
【請求項６】
前記ジョブをプロビジョニングしている間、前記プロビジョニングメカニズムが前記資源要求量と前記直前に形成されたサブグループに対して行われた予約との間の差に基づいて前記次のインラインジョブに対して予約を行うように構成されている、請求項５に記載のシステム。
【請求項７】
前記ジョブをプロビジョニングしている間、
前記プロビジョニングメカニズムが、
同じＱｏＳ格付けを有している少なくとも２つのジョブに応答して、一つの層としての前記少なくとも２つのジョブを前記直前に形成されたサブグループに加算することによって階層状サブグループを形成し、
前記少なくとも２つのジョブの各々によって必要とされる資源に基づいて前記２つのジョブの各々に対して基準倍率を求めて、
前記基準倍率に基づいて、前記少なくとも２つのジョブの各々に対して予約を行うように構成されている、請求項５に記載のシステム。
【請求項８】
前記プロビジョニングメカニズムが、複数の所定の時間インターバルに対して前記ジョブをプロビジョニングするようにさらに構成されており、これには前記複数の所定の時間インターバルに対して１つ以上のジョブのグループによって必要とされる資源の最大量を算定することが含まれる、請求項３に記載に記載のシステム。
【請求項９】
ジョブの間で分離の度合を定義付ける分離パラメータを算定するように構成されている分離モジュールを更に含むことで、前記ジョブに対して予約を行っている間、前記プロビジョニングメカニズムが前記分離パラメータを適用するように構成され、完全な分離によって前記ジョブに対して個別予約が行われる、請求項３に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本明細書は、一般に、データセンタのオペレーションに関し、より詳細には、データセンタに対して長期資源プロビジョニングを提供するシステムに関する。
【背景技術】
【０００２】
近年の仮想化技術はデータセンタが共有された環境において様々なジョブを実行することを可能にした。いいかえれば、このような様々なジョブは、その全てを単一のマシンまたは複数のマシンのクラスタによって提供することができるメモリ、中央処理装置（ＣＰＵ）、および帯域幅などの同じ物理資源を共有することができる。データ・センタ・オペレーションの重要な考慮する点は、単一のマシンまたは複数のマシンのクラスタで複数のジョブ（または負荷）を統合することである。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
資源の有効なプロビジョニングは良好に統合することができるジョブのグループ、即ち、マシンまたは複数のマシンのクラスタで物理資源をより有効に活用することができるグループを検索することを含む。より良好な統合によって増加したデータセンタ容量を得ることができる。さらに、未使用のマシンの電源を切ることによって、データセンタはその省エネ効果を高めることもできる。
【課題を解決するための手段】
【０００４】
本発明の一実施形態は、複数のジョブによって共有された物理資源をプロビジョニングするためのシステムを提供する。動作中、このシステムはジョブに対する資源使用モデルを確立し、ジョブに関連付けられたサービス品質（ＱｏＳ）要件に基づいてジョブを格付けし、上位のＱｏＳ格付けを有しているジョブの第１の部分集合に関連付けられた任意の未使用予約が、他の残存ジョブのうち最上位のＱｏＳ格付けを有しているジョブの第２の部分集合の方を優先させて、他の残存ジョブへ分布されるように所定の時間インターバルに対してジョブをプロビジョニングする。ジョブのプロビジョニングは、資源使用モデルとジョブに関連付けられた対応するＱｏＳ要件に基づいてジョブに対して予約を行うことを含む。
【０００５】
この実施形態の一変形例において、ジョブのプロビジョニングは、ジョブに関連付けられた対応するＱｏＳ格付けに基づいてジョブへ異なる数の共有を割り当て、ジョブの第１の部分集合に関連付けられた未使用資源が、他の残存ジョブへ割り当てられた共有の数に基づいて他の残存ジョブに比例して分布されることを前提に、予約を割り当てることをさらに含む。それぞれのジョブに割り当てられた共有数はそれぞれのジョブのＱｏＳ格付けに互いに関連している。
【０００６】
本実施形態による一変形例において、ジョブのプロビジョニングは、ＱｏＳ格付けに基づいて降順でジョブを仕分けし、最上位のＱｏＳ格付けを有しているジョブからスタートして、次のインラインジョブを直前に形成されたサブグループに加算することによってサブグループを形成するステップと、サブグループに対して資源使用モデルを確立するステップと、サブグループに対する資源使用モデルと次のインラインジョブに関連付けられたＱｏＳ要件に基づいてサブグループによって必要とされる資源要求量を決定するステップと、を反復することを含む。
【０００７】
本実施形態の更なる変形例において、このシステムは、要求された資源の量と直前に形成されたサブグループに対して行われた予約量との差に基づいて次のインラインジョブに対して予約を行う。
【０００８】
更なる変形例において、同じＱｏＳ格付けを有している少なくとも２つのジョブに応答して、システムは、直前に形成されたサブグループに少なくとも２つのジョブをティアとして加算することによってティアードサブグループを形成し、少なくとも２つのジョブの各々によって要求される資源に基づいて少なくとも２つのジョブの各々に対する基準倍率を算定し、この基準倍率に基づいてこれら少なくとも２つのジョブの各々に対して予約を行う。
【０００９】
本実施形態の一変形例において、システムは、複数の所定の時間インターバルに対してジョブをプロビジョニングし、その際、複数の所定の時間インターバルに対して１つ以上のジョブから成るグループによって必要とされる資源の最大量を算定することを含む。
【００１０】
本実施形態の一変形例において、システムはジョブの間で分離の度合を定義する分離パラメータを受信する。ジョブのプロビジョニングは、ジョブに対して予約を行っている間、分離パラメータを適用することを含み、完全な分離によってジョブに対して個別予約が行われる。
【図面の簡単な説明】
【００１１】
【図１】ジョブに対する例示的な不足解析を示す図である。
【図２】本発明の一実施形態による、２つの互いに隣り合うプレフィックスグループ間で資源がどのようにカスケード（層化）するかを示す図である。
【図３】本発明の一実施形態による、資源プロビジョニングコントローラを示す図である。
【図４】本発明の一実施形態による、資源プロビジョニングの例示的なプロセスを示す流れ図である。
【図５】本発明の一実施形態による、データセンタ内の資源プロビジョニングのための例示的なコンピュータシステムを示す図である。
【発明を実施するための形態】
【００１２】
図面では、同じ要素には同じ参照番号が付される。
【００１３】
以下の記載は、当業者が本発明の実施形態を活用することを可能にするために提示され、特定のアプリケーションとその要件に関して提供されている。開示されている実施形態に対する様々な変更は当業者に容易に理解され、本明細書中に定義されている一般的な原理が本明細書の精神及び範囲を逸脱しない限りに於いて他の実施形態やアプリケーションに適用可能である。よって、本発明は図示されている実施形態に限定されないが、本明細書中に開示された原理および特性を逸脱しない最も広い範囲に一致する。
【００１４】
概要
本発明の実施形態は、データセンタへ長期資源プロビジョニングを提供するためのシステムを提供する。より詳細には、システムは、今後発生する時間インターバルの集合内のジョブの資源ニーズに基づいてジョブのグループに対して資源をプロビジョンする。ジョブに対する資源ニーズを満たすだけでなくサービス品質（ＱｏＳ）要件を満たすために、システムは、行われた累積予約が全てのジョブの資源ニーズを十分に満たすほど大きくなるまで、ＱｏＳ降順に基づいてジョブに対する個別予約を行う全体のプール割当てアルゴリズムを適用する。カスケードされたアルゴリズムはそれらのＱｏＳ格付けに基づいて未使用予約の再分布を他のジョブに対して計画するためにも使用される。
【００１５】
本明細書において、用語「物理資源」は、計算ジョブを完了するために必要とされる様々なタイプの物理的機器をさす。この用語は、処理能力、記憶領域、通信帯域幅、入／出力などを含み得る。さらに、特定の「物理資源」は、データセンタの単一マシン、マシンのクラスタ、またはすべてのマシンに言及することができる。また、用語「物理資源」と「物理マシン」は互いに互換性がある。
【００１６】
本明細書において、用語「ジョブ」は、共有された環境における計算可能なタスクをいう。より具体的には、ジョブは、仮想マシンインスタンスまたは仮想マシンインスタンスの集合であってよい。
【００１７】
単一インターバルプロビジョニング
データ・センタ・オペレーションにとって好ましいとされる資源プロビジョニングシステムはプロビジョニングを自動的にかつ頻繁に調整することができるはずだが、このようなシステムへの人間のオペレータによる厳密な管理がいまだに望ましいとされる。例えば、ジョブの資源ニーズを監視しかつ資源プロビジョニングを提案する監視ツールを有することが望ましい。次に、人間のオペレータはプロビジョニングを承認して実施する。自動システムは１５分ごとにプロビジョニングを調整するが、管理されたシステムははるかに少ない頻度でプロビジョニングを調整する（例えば、毎日、毎週、または毎月）。
【００１８】
単一時間インターバルにおける資源のプロビジョニングは短期プロビジョニングに非常に類似している。唯一の違いは、短期システムは、（次の１５分などの）直ぐ後に続く時間インターバルに対してジョブのグループの資源使用要件を予測するモデルを使用して、これらのジョブのＱｏＳ仕様に基づいて資源を割り当てて資源使用要件を満たす。一方、単一時間インターバルプロビジョニングは、すぐ後に続かない特定の時間インターバルに対する資源のプロビジョンを含む。短期プロビジョニングは、最近の資源消費量が近く発生する期間の資源ニーズの強力な予測子となるので、相対的に簡単に行うことができる。
【００１９】
この開示に於いて、ジョブに対するＱｏＳ仕様（またはＱｏＳレベル）はｐで表され、ｐは、ジョブがその資源ニーズで完全にプロビジョニングされない受容可能な確率である。すなわち、ＱｏＳレベルｐを有しているジョブは、測定されたインターバルの間、確率ｐを有する全ての要求された資源を受信するわけではない。ＱｏＳレベルｐはジョブ失敗の確率と混同されるべきではないことに注意されたい。最新のアプリケーションは、それらが要求された資源の１００％を有していない場合でも十分良好に実行できるほど良好に書かれている。例えば、重い負荷が掛かったアプリケーションはより低い解像度の画像を一時的に分配するか、またはバッチモードで実行されているアプリケーションはデッドラインまでの完了を確実とするために早くスタートする。しかしながら、しかしながら、資源の不足へのレジリエンス（回復力）はアプリケーションの固有の特性である。混同を避けるために、完全にプロビジョニングするための失敗を「不足」の状況と称する。ＱｏＳｐ（即ち、許容された「不足の確率」）の適切な設定値は、許容されたジョブの失敗の確率よりも大きいことに留意されたい。
【００２０】
この開示に於いて、時間インターバルτにおいてジョブｉによって必要とされる資源を表すためにわれわれはランダム変数Ｚτ（ｉ）を使用する。ＺはＣＰＵサイクル、メモリ、ハードディスク、またはＩ／Ｏなどの一次元資源あるいは多次元資源であってもよいことを留意されたい。単一の時間インターバルだけを考慮する場合、われわれはτ指数を一時的に省略することができる。
【００２１】
ジョブｉに対する資源ニーズは、ランダム変数Ｚ（ｉ）に対する観察された確率分布関数φ（ｉ）（ｚ）によってモデリングすることができる。対応する累積分布は以下のように表すことができる。
【数１】
2013175178.tif 000003
観察された分布と真の分布の差は十分なサンプルがあるので無視することができることに留意されたい。しかしながら、モデリングと統合アルゴリズムがジョブの集合に新たに適用される場合、それ以前の仮説を用いかつモデリングエラーのリスクを取り入れる際にはいくぶん注意が必要である。
【００２２】
（統計的パッキングアルゴリズムとも呼ばれこともある）全体のプールアルゴリズムは、累積予約
【数２】
2013175178.tif 000004
がジョブの全体プールが十分な資源を有するほどに大きくなるまで、
【数３】
2013175178.tif 000005
に基づいてジョブの個別の予約を行うことによってＱｏＳの降順（または増加するｐ）においてジョブを処理する。（ｋより大きい指数を有している）残存ジョブは予約を必要としない。いいかえれば、より上位のＱｏＳレベルを有しているジョブがそれらのＱｏＳ要件を満たす十分な資源によって個別にプロビジョニングされると、未使用の資源の頻繁な利用可能性はより下位のＱｏＳレベルを有するジョブの要件を満たすには十分である。
【００２３】
より形式的ないい方をすれば、全体のプール割当てアルゴリズムは、第１のｋ−１個のジョブに対する個別予約
【数４】
2013175178.tif 000006
＋ジョブｋにおける部分予約ｓ（ｋ）≦ｒ（ｋ）の部分合計が、ｋ番目のジョブのＱｏＳレベル（即ち、ｐ（ｋ））においてグループ総資源のニーズを満たすほど大きくなるように、最小の指数ｋを検索することによって効果的に作用する。即ち、自式となる。
【数５】
2013175178.tif 000007
【数６】
2013175178.tif 000008
の上付き（ｎ）はグループ全体への累積分布を意味することに留意されたい。等式（３）によれば、ジョブ１、２、．．．、ｋは予約ｒ（１），ｒ（２），．．．，ｒ（ｋ―１），ｓ（ｋ）を得ることができ、残存ジョブには予約は入らない。ジョブがＱｏＳ順序にあるため、残存ジョブのＱｏＳ要件は、更なる予約なしでも満たすことができることに留意されたい。ジョブｉに与えられる実際の予約は、遷移的指数ｋに対してジョブがスタンドしている場所に依存する。
【数７】
2013175178.tif 000009
等式（４）を以下のそのアルゴリズムバージョンを用いて表す方が便利である。
【数８】
2013175178.tif 000010
ここで、変数“ａｃｃｕｍ”は発生した予約全体である。等式（４）の正確度（およびそのアルゴリズムバージョン）は、等式（３）に基づくグループの資源ニーズを満たすことがｐ（ｋ）のＱｏＳレベルのすべての個別のジョブの資源ニーズを満たすという観察に準じており、この観察は、ｐ（ｊ）≧ｐ（ｋ）であるとき、指数ｊ＞ｋを有する任意のこれ以降発生するジョブに対して十分すぎるくらいである。
【００２４】
全体のプールアルゴリズムのアプリケーションは、個別のジョブ（等式（２））に対する資源ニーズのモデリングだけでなく、グループ全体（等式（３））に対する資源ニーズのモデリングも必要とする。これまで、我々は、ＱｏＳ順序でのジョブを介してシーケンシャルに進行し、ｋを下回る指数を有するジョブに対しては大きな保護予約をするが、ｋを上回る指数を有するジョブに対しては予約を行わない結果的に等式（４）に示した予約が得られる全体のプール割当てアルゴリズムについて説明してきた。この結果を少しだけ改変し、所謂、固定小数点計算を用いて全ての予約を一回計算することによって合計予約を削減することが可能である。大抵の場合、固定小数点計算の結果は、等式（４）の予約に類似するが、ｋを下回る指数を有するジョブに対する予約は少ないが、ｋを上回る指数を有するジョブに対しては少ない予約でも、ｋにおける遷移を緩和することができる。
【００２５】
ジョブｉごとに、われわれがジョブの資源ニーズ（ランダム変数Ｚ（ｉ））とジョブｉを除く全ての他のジョブの全体的資源ニーズ（ランダム変数Ｙ（−ｉ））とのジョイント（共同）分布（これは観察された確率分布関数：
【数９】
2013175178.tif 000011
と表示される）をモデリングすることができると仮定すると、不足確率は以下のように計算される。
【数１０】
2013175178.tif 000012
ここで、ｓ（ｉ）はジョブｉに対して行われた個別予約であり、ｓＴ＝ｓ（１）＋ｓ（２）＋．．．＋ｓ（ｎ）はグループ全体に対して行われた予約である。不足は、個別予約またはグループ予約のいずれも
【数１１】
2013175178.tif 000013
を満たすほど大きくない場合に発生する。
【００２６】
図１はジョブの例示的な不足解析を示す図である。ｘ軸は、ジョブｉの資源ニーズ（変数ｚ）であり、ｙ軸は全ての他のジョブの資源ニーズである（変数ｙ）。点線は、ジョブｉ（ｓ（ｉ））に対して行われた個別予約を意味し、破線は、グループ全体（ｓＴ）のために行われた予約を意味する。ジョブｉに対する資源ニーズがジョブｉに対して行われた個別予約を下回る場合（即ち、点線の左側）、このようなニーズはジョブｉの個別予約によって満たすことができる。ジョブｉに対する資源ニーズがその個別予約を上回る（即ち、点線の右側）が、グループに対する資源ニーズがグループ予約を下回る場合（即ち、破線の下）、ジョブｉに対する資源ニーズは他のジョブの未使用の予約によって満たすことができる。斜線部分（点線の左側でかつ破線の上）はいわゆる不足領域である。資源ニーズが不足領域内にあるときに不足が発生する。グループ予約が十分に大きくない場合、仮想マシンのスケジューラがどのように作用するかによっては、まだ全体的にプロビジョニングされるジョブもあることに留意されたい。ここで、「痛みが共有される」、即ち、グループ内のすべてのジョブがその全資源ニーズに不足があって僅かの不足であってもＱｏＳ要件達成のためには失敗事象としてカウントされるとわれわれは仮定する。これはＱｏＳ要件を満たすための従来のアプローチであり、即ち、これらの要件が個別又はグループ予約によって満たされない限り、われわれは要件が満たされたと仮定することはない。
【００２７】
不足確率を用いて、必要とされる個別予約ｓ（ｉ）を
【数１２】
2013175178.tif 000014
と
【数１３】
2013175178.tif 000015
の同時解として算定することができる。
【００２８】
等式（６）および（７）は、固定小数点計算を用いて解くことができる。合計予約ｓＴからスタートし、等式（６）に基づいてＱｏＳ要件を満たすために必要な個別予約ｓ（ｉ）を解き、これらの個別予約を用いて等式（７）に基づく新しい全体予約を定義する。観察された確率分布関数がヒストグラムとして与えられたとき、この固定小数点計算をシステマチックに進めることができる。即ち、最大可能値からスタートして、正確なｓＴを検索し、ｓＴを段階的に減らしていく。これによって、単調に増分する等式（６）の解において、ｓ（ｉ）が得られる。ｓ（ｉ）の和がｓＴを上回ると、この検索は終了し、これによって、ヒストグラムの量子化の精度範囲に対して固定小数点を識別する。アルゴリズムを終了するために、等式（７）に基づいてｓＴはｓ（ｉ）の和に設定され、これによって、ｓＴとｓ（ｉ）が共に必要以上であることを確実にする。
【００２９】
このアルゴリズムの正確度は等式（６）に準じている。固定小数点において、不足の確率はＱｏＳ仕様によって必要とされる確率ｐ（ｉ）である。ヒストグラムと段階的な検索を使用する場合、オーバーシュートが生じることもあることに留意されたい。しかしながら、ｓＴとｓ（ｉ）の両方が大きくなるにつれて、ｑ（ｉ）（ｓ（ｉ），ｓＴ）が単調減少するという事実によって、
【数１４】
2013175178.tif 000016
が得られ、これがジョブｉのＱｏＳ要件を満たすかまたはこれを超える。
【００３０】
プロビジョニングの唯一のコントロールが個別のジョブ予約をすることであると仮定した場合、全体のプール割当てアルゴリズムの固定小数点のばらつきをプロビジョニングの問題の最適なソリューションとして検討することができるが、未使用の予約を選択的に再分布するソリューションを含むプロビジョニングをコントロールするためであれば、他のツールを使用することもできる。
【００３１】
前述の全体のプール割当てアルゴリズムは、未使用の予約がプール内のすべてのジョブの間で均等に再分布されることを可能にする。しかしながら、上位ＱｏＳ格付けを有するジョブ（即ち、下位ｐを有するジョブ）を優先してこれらの未使用の予約を選択的に再分布する方が有利である。一実施形態において、未使用の予約を再分布する時に「共有」マシンが使用される。具体的には、各ジョブには多数の共有が割当てられ、未使用の予約は、資源を必要とする残存ジョブの共有に比例して分布される。従って、より上位のＱｏＳジョブにより多くの共有を割り当てることによって、これらのジョブがより多くの未使用予約を取得することができることを確実とする。例えば、ジョブがＱｏＳ降順に指数付けされる場合、システムは指数に基づいて共有を割当てることができる。ジョブｉは、Ｍｎ―ｉ個の共有を受信する。ここで、Ｍは大きい正の定数であり、ｎはプール内のジョブの数である。Ｍが大きくなればなるほど、再分布はより上位のＱｏＳジョブを優先する。限界Ｍ→∞において、すべてのジョブの資源ニーズが満たされるまで（または十分な資源がなくなるまで）、すべての未使用の資源は残存ジョブを介してＱｏＳ順に「カスケード」する。実際に、Ｍは５または１０などの有限値に設定される。これらの有限値において、未使用の資源の一部はより下位のＱｏＳジョブへ「リークする」。この全体のプール割当てアルゴリズムを用いれば、未使用資源を下位のＱｏＳジョブへ付与することも統合の役に立つことから、これらの資源も無駄にはならない。
【００３２】
他の実施形態において、共有をジョブや仮想マシンに割り当てる代わりに、システムは、ジョブのＱｏＳ格付けに応じてこれらのジョブに類似している未使用資源のカスケードを作成するためにグルーピングマシンを使用する。より具体的には、最上位のＱｏＳ格付けを有している２つのジョブ（または仮想マシン）が一緒にグルーピングされ、その後、グループの階層は、以下に示されるように、この階層が拡張されるにつれて下位のＱｏＳジョブを連続的に加算することによって構築される。
【数１５】
2013175178.tif 000017
個別のジョブ（または仮想マシン）には予約
【数１６】
2013175178.tif 000018
が付与され、総資源プール
【数１７】
2013175178.tif 000019
は個別予約の和よりも大きくなるように選択され、以下のように与えられる。
【数１８】
2013175178.tif 000020
【数１９】
2013175178.tif 000021
はいくつかの余分なパッディングによって設定され、複数の物理マシンを介してマシンの整数を四捨五入すべくビンパッキングを可能にすることに留意されたい。各グループには、そのプール内の総資源からサブツリー内に存在しない任意の予約を減算したものに等しいに大きな予約が付与される。
【数２０】
2013175178.tif 000022
ここで、
【数２１】
2013175178.tif 000023
は、そのサブツリー内のｖｍ１，ｖｍ２，．．．，ｖｍｉを含む階層内に形成されるグループに対する予約である。これらのグループ予約は全てのニーズが満たされるまで、それらのサブツリーにおける未使用の資源をキャプチャする。このように未使用の資源はグループ階層の左側を優先し、資源が下位のＱｏＳジョブの資源ニーズを満たす前により上位のＱｏＳジョブの資源ニーズを満たす。
【００３３】
一つの実用的な考慮は、ＱｏＳ仕様が少数の固定レベルに含まれる傾向があることである。これにより、全てのジョブが異なるＱｏＳレベルｐ（ｉ）を有することにはならない。ジョブを介して未使用の資源をシーケンシャルにカスケードするのではなく、むしろ、未使用の資源が同じＱｏＳレベルを有する全てのジョブに対して同時にカスケードすることができる。このカスケードは、等しいＱｏＳジョブに対する共有割当てを等しくすることによって、またはグルーピングメカニズムを使用する場合は階層内の同じレベルで等しいＱｏＳジョブをまとめて加算することによって、配列され得る。
【００３４】
単純化するために、我々は最初、異なるＱｏＳレベルのケースを考慮し、カスケーディング（即ち、Ｍ→∞、または各レベルにおいて加算された一つの新しい仮想マシンを有しているグループの階層）を厳密に命令した。カスケード過剰アルゴリズムは、最初に、最上位のＱｏＳジョブによってＱｏＳの降順（したがって、昇順ｐ（ｉ））でジョブを処理する。各ステップにおいて、実際の予約
【数２２】
2013175178.tif 000024
は累積予約がすべての先行ジョブによってグルーピングされるジョブｉの資源ニーズを満たすように選択される。ｉごとに、
【数２３】
2013175178.tif 000025
が、グループ内の最新ジョブのＱｏＳレベルにおいてプレフィックスグループ｛１、２、．．．、ｉ｝に必要とされる全体予約であるとすると、
【数２４】
2013175178.tif 000026
となり、ここで、Ψ（ｉ）はプレフィックスグループに対する累積分布関数（ＣＤＦ）である。ジョブｉに対する実際の予約
【数２５】
2013175178.tif 000027
は、プレフィックスグループ｛１、２、．．．、ｉ｝の全体要件を満たすために、ジョブｉに必要とされる（上位のＱｏＳジョブに対して既に行われている予約の和
【数２６】
2013175178.tif 000028
を上回る）更なる予約である。
【数２７】
2013175178.tif 000029
を計算するためのアルゴリズムは、以下のように記載できる。
【数２８】
2013175178.tif 000030
【００３５】
ＱｏＳの降順で残存ジョブを介して未使用資源をカスケードするために共有（またはグルーピング）マシンを用いることから得られる利点は、その予測資源より多く（例えば、そのＱｏＳニーズを満たすために必要である資源を上回る量）を必要とする下位ＱｏＳジョブは、これらの資源が上位のＱｏＳジョブを介してカスケードするまで、未使用資源を受信しないことに留意されたい。図２は、本発明の一実施形態による、２つの互いに隣り合うプレフィックスグループ間で資源がどのようにカスケードするかを示す図である。図２の上半分はプレフィックスグループ｛１、２、．．．、ｉ−１｝の確率密度関数（ＰＤＦ）を示し、図２の下半分は、次のプレフィックスグループ｛１、２、．．．、ｉ｝に対するＰＤＦを示している。ＱｏＳの降順の場合、不足確率ｐ（ｉ）がｉとともに増分し、これによって、分布に相対して左方向へのプレフィックスグループシフトに対して必要とされる予約につながることに注意されたい。図２から、更なる予約
【数２９】
2013175178.tif 000031
が殆ど必要とされないことが分かる。このカスケード過剰アルゴリズムの正確度は、
【数３０】
2013175178.tif 000032
を知ることによって、および等式（１２）によって、提供される。カスケード過剰アルゴリズムに基づいて行われた累積予約は、ＱｏＳレベルｐ（ｉ）におけるグループ｛１、２、．．．、ｉ｝の資源ニーズを満たすほど十分に大きく、ＱｏＳレベルｐ（ｉ）におけるグループの最後のメンバであるジョブｉに対する資源ニーズを必ず満たすことになる。
【００３６】
複数のジョブが同じＱｏＳ要件を有している場合、ティア（層）ベースのカスケード過剰アルゴリズムが実施される。より具体的には、未使用の予約は、同じティア（層）内のすべてのジョブ、または同じＱｏＳレベルを有するジョブを、同時にカスケードする。そうするためには、所与の層内のジョブへ等数の共有が付与される。したがって、これらのジョブに予約が与えられる場合、これらのジョブは余分の使用可能な資源の等しい部分を受信する。
【００３７】
層ベースのカスケードアルゴリズムはｍ個のＱｏＳ層を定義付け、これによって、各（ＱｏＳ順の）ジョブｉが層に割り当てられ、所与の層内の各ジョブは同じＱｏＳレベルを共有する。ジョブｉの層ｋは、グルーピングメカニズムによって、ｋ＝Ｇ（ｉ）として定義付けることができ、層ｋ内のジョブの数はｍｋとして表される。層がＱｏＳ降順で指数付けされると仮定すると、Ｇ（ｉ）≦ｋであるようにすべてのジョブｉを含むプレフィックスグループに必要とされる予約は、
【数３１】
2013175178.tif 000033
となり、ここで、Ψｇ（ｋ）はプレフィックスグループのＣＤＦであり、ｐｇ（ｋ）はＱｏＳの層ｋに関連付けられる不足確率である。
【００３８】
共有メカニズムは層内のジョブの間で各層において余分な資源を等しく割り当てるので、必要とされる残存予約
【数３２】
2013175178.tif 000034
は各ジョブの個別のプロビジョニング予約ｒ＊（ｉ）に比例的にヒューリスティックに割り当てることができる。一実施形態において、システムは、ジョブのスケーリングされた個別予約に基づいてジョブごとに実際の予約を行う。ジョブｉに対してスケーリングされる個別予約は、以下のように定義される。
【数３３】
2013175178.tif 000035
したがって、ジョブｉの実際の予約は次式で与えられる。
【数３４】
2013175178.tif 000036
【００３９】
等式（１４）によって定義された倍率の個別予約以外に、与えられたティアに対する全てのγ（ｉ）値に合計が１であれば、この比例倍率の他の定義も可能であることに留意されたい。個別のプロビジョニング予約に比例してティア予約を配分する、この特定のヒューリスティックは、個別の保護を提供するのみならず最新の移行決定を賢明にガイドするという利点がある。ティアベースのカスケード過剰アルゴリズムの正確度は、ｋごとに、
【数３５】
2013175178.tif 000037
であることを知ることによって提供される。これによって、
【数３６】
2013175178.tif 000038
となる。したがって、等式（１３）に基づいて、累積予約はＱｏＳレベルｐ（ｋ）において、ティアプレフィックスグループΨｇ（ｋ）のニーズを満たすほど大きい。
【００４０】
概して、モデリング努力と達成される統合の量との間にはトレードオフがある。シンプルな全体のプール割当てアルゴリズムは、個別ジョブ資源と総資源をモデリングする最もシンプルなモデリング要件を有している。全体のプール割当てアルゴリズムの固定小数点のばらつきは、より良好で、より統合された解を取得するが、ジョブごとにジョイント（共同）モデルを必要とする。カスケード過剰アルゴリズムは、根本的な仮想化スケジューラ（即ち、共有またはグルーピングのいずれか）により多くのプロビジョニングマシンを用いることによってより良好でより統合された解を得ることができるが、そのモデリングニーズはシンプルな全体のプール割当てよりもやや複雑であり、ｎ個の個別モデルではなく、ｎ個の「プレフィックスグループ」のモデルを必要とする。カスケード過剰アルゴリズムの拡張としてのティアベースのカスケード過剰アルゴリズムは、改良された統合解を取得するが、ｍ個のティアプレフィクスグループだけでなく、（γを計算するための）ｎ個の個別モデルを必要とする。
【００４１】
ジョブが独立している場合、さまざまなモデリング要件は重要ではなく、全ての上記のモデルは個別のジョブモデルの様々な畳み込みによって導き出すことができる。しかしながら、実際には、ジョブの資源ニーズは通常相関関係にあり、この相関関係を説明するモデリング（即ち、様々なグループ資源の要件をモデリングすること）は、統合問題をうまく解決する上で不可欠である。カスケード過剰アルゴリズムはまた、下位ＱｏＳジョブからの上位ＱｏＳジョブの分離の利点を提供する。
【００４２】
複数のインターバルプロビジョニング
データセンタの長期プロビジョニングは、複数の時間インターバルのためのプロビジョニングを含む。各時間インターバルの前にプロビジョニングを動的に変更するよりむしろ、複数の時間インターバルに対して効果を表す一つのプロビジョニングを予め設定することが好ましい（例えば、全日または全週）。このより安定したプロビジョニングに対する動機は、例えば、あまり頻繁に検討せずおよび／またはより長期のプロビジョニング勧告を手動で適用することによってデータセンタオペレータがデータセンタのオペレーションをより慎重に管理できるようにすることである。
【００４３】
複数のインターバルプロビジョニングへの挑戦は、複数のインターバルに対して同時に作用するプロビジョニングを計算することである。単純な戦略は、各時間インターバルτ
に対して予約ｒτ（ｉ）を計算するために上記した単一インターバルプロビジョニングアルゴリズムのいずれか一つを使用することであり、次に
【数３７】
2013175178.tif 000039
を設定することにより全てのこのような予約の最大値を用いることである。
【００４４】
これはジョブのいくつかの集合に有効であるが、ジョブの資源ニーズが相補関係にある場合、同じ時間インターバルでは全ての資源ニーズが予約の最大値を必要としない場合もあるという欠点があった。従って、この単一のインターバルプロビジョニングアルゴリズムは単一の時間インターバル内で資源を共有するために良い仕事をしたとしても、等式（１５）における最大の演算は時間インターバルの間で資源を共有するためにいい仕事をしない。従って、より優れたアプローチが必要になる。
【００４５】
様々な単一インターバルプロビジョニングアルゴリズムのなかでも、カスケード過剰アルゴリズムは、時間インターバルの間で資源の再配分するために大部分のコントロールを提供する。ここでは、カスケード過剰アルゴリズムを複数の時間インターバルに拡張することができる。各プレフィックスグループ｛１、２、．．．、ｉ｝ごとに、全ての時間インターバルに対するグループ（即ちｐ（ｉ））の最新のメンバのＱｏＳレベルにおけるグループの資源ニーズを満たすために必要とされる予約
【数３８】
2013175178.tif 000040
は、
【数３９】
2013175178.tif 000041
と
【数４０】
2013175178.tif 000042
を用いて計算することができる。
【００４６】
前述の共有やグルーピングマシンを使用し、過剰資源がＱｏＳ降順でジョブへカスケードすると仮定して、以下のアルゴリズムを用いて実際予約を計算することができる。
【数４１】
2013175178.tif 000043
【００４７】
このアルゴリズムは、等式（１５）において記述されている単純な最大値アルゴリズムとは異なる。実際の単一インターバル予約
【数４２】
2013175178.tif 000044
に最大値を適用するよりむしろ、このアルゴリズムは、等式（１７）に示すように、実際の予約を行う前に、この最大値を要求された予約へ適用する。この方法はプレフィックスグループ内の資源のより多くの共有を可能にする。
【００４８】
このアルゴリズムの正確度は、各プレフィックスグループ｛１、２、．．．、ｉ｝ごとに、
【数４３】
2013175178.tif 000045
としての十分な累積予約があることを通知することによって提供される。等式（１７）に基づいて、累積予約
【数４４】
2013175178.tif 000046
はすべての時間インターバルにおいて、グループの最後のメンバ、ジョブｉのＱｏＳレベルにおいてプレフィックスグループの資源ニーズを満たすほど大きい。従って、プレフィックスグループｉのプロビジョニングは、そのＱｏＳ要件を満たすことを確実にする。
【００４９】
ティアードされた（層になった）場合、等式（１６）および（１７）は以下のように書き換えることができる。
【数４５】
2013175178.tif 000047
【数４６】
2013175178.tif 000048
ここで、
【数４７】
2013175178.tif 000049
は、全ての時間インターバルに対するグループ（即ち、ｐｇ（ｉ））の最後のティアのＱｏＳレベルにおけるグループの資源ニーズを満たすために必要とされる予約である。
【００５０】
ジョブｉに対してスケーリングされた個別予約は、
【数４８】
2013175178.tif 000050
と
【数４９】
2013175178.tif 000051
に基づいて、全ての時間インターバルに対する小数の平均値として計算することができ、ここでＴは時点数である。
【００５１】
アルゴリズムは単一インターバルのティア（層）ベースのカスケード過剰アルゴリズムに類似している。
【数５０】
2013175178.tif 000052
【００５２】
ｋごとに、
【数５１】
2013175178.tif 000053
であるので、単一のインターバルシナリオの正確度を証明する論理は、この複数のインターバルティアベースのカスケード過剰アルゴリズムのためにも通じる。
【００５３】
ジョブモデル間の分離
仮想化の利点の一つは、仮想マシンが資源を共有できるようにすることである。また他の利点は、あまり頻繁に引用されないが、互いから仮想マシンを分離させることである。共有する資源が完成した分離が可能でないか又は望ましくないことをしばしば意味することから、これらの利点の両方を達成することは難しい。実際には、一つのジョブの不正な振舞いが、システム内の他のジョブに深刻な影響を与えない程度の分離を有することは望ましいといえる。
【００５４】
分離を改良するための簡単なステップは、ＶＭｗａｒｅ（登録商標）（ＶＭｗａｒｅ、Ｉｎｃ、Ｐａｌｏ  Ａｌｔｏ、Ｃａｌｉｆｏｒｎｉａ）などの仮想化システムにおいて提示された「最大値」の仕様を使用することである。例えば、ジョブｉのための個別予約が
【数５２】
2013175178.tif 000054
で表される予約を必要とする場合、
その後、最大値は、
【数５３】
2013175178.tif 000055
に基づいて設定することができる。
つまり、このケース２において、ある一定の係数によってそのＱｏＳ要件をアウトパフォームするために必要な量より多い資源を使用することは許されない。最大値を特定する別の簡単なアプローチは、ｒ＊（ｉ）に用いられた１．２などの、１より大きい基準倍率を使用することであるが、Φ（ｉ）の可用性は、等式（２３）を最大値設定に対するより基本的なアプローチにすることができる。等式（２３）で設定される最大値は、上記したセクションに説明した異なるグループの統合が最小値を設定するために使用されている場合でも設定可能であることに留意されたい（即ち、予約）。最大値を設定することが有用である一方、グループ統合アルゴリズムが使用されている場合、ジョブ分離のより効果的なコントロールを提供するための更なる技術も必要とされる。
【００５５】
ジョブが最初に仮想化されている場合、従来の戦略は、直前に用いられた物理資源に等しい仮想資源の量に対して予約を行うことである。これは互いからジョブを完全には分離しないが（まだに未使用の資源を共有し利益を得ようとするが）、少なくともそれらの直前の非仮想化された物理的実施と同じくらい良好に分離する。残念ながら、直前に用いられた物理資源に等しい仮想資源を単に予約するこの従来のアプローチは、仮想化の利点を最大限に実現していない。ジョブの資源ニーズが良好にモデル化され、ＱｏＳ要件が良好に指定されると、資源における相当な更なる保存やＱｏＳの改善が分離削減や資源共有を介して可能となる。これは前述のアルゴリズムのいずれかを介して達成することができる。
【００５６】
可変性の高い資源ニーズを有するジョブが上述の資源統合アルゴリズムにとって問題ではなく、それらの可変性が十分良好にモデリングされている限りにおいて分離させる必要がないことを強調することが重要である。ジョブが最初に仮想化された場合、高い分離を皮切りに、分離の度合いを管理して、その後、ジョブの資源ニーズがより良好にモデリングされるにつれて、分離を削減してより大きな統合を成し遂げることが重要である。
【００５７】
ここで、われわれはジョブの分離をコントロールするパラメータαを導入する。αの範囲は０〜１であり、０は完全分離を意味し、１はジョブ間での資源の完全共有を意味する。ジョブが異なるＱｏＳレベルを有している場合、等式（２２）は予約を個別に定義し、グループ（即ち、ｐ（ｉ））の最新メンバのＱｏＳレベルにおけるグループの資源ニーズを満たすためのプレフィックスグループ｛１、２、．．．、ｉ｝に対して必要とされる予約
【数５４】
2013175178.tif 000056
は、（等式（１６）‐（１７）に基づいて）次式で表される。
【数５５】
2013175178.tif 000057
【００５８】
ジョブがＱｏＳ降順で等式（２２）と（２４）を使用して仕分けられると仮定すると、われわれはその割当てを以下に基づいて設定することができる。
【数５６】
2013175178.tif 000058
【００５９】
見ての通り、一つの極値（α＝０）において、上記のアルゴリズムは等式（２２）で定義される個別のプロビジョニング
【数５７】
2013175178.tif 000059
に還元される。一方、他の極値（α＝１）において、上記のアルゴリズムは前のセクションで述べた複数のインターバルカスケード過剰アルゴリズムへ還元される。
【００６０】
ジョブが同じＱｏＳレベル（ティアベースの場合）を有するケースについては、最新のティアメンバのＱｏＳ要件を満たすことができるティア「プレフィックスグループ」に必要とされる予約は、（等式（１８）‐（１９）に基づいて）
【数５８】
2013175178.tif 000060
で表される。
【００６１】
同じαパラメータを用いて、以下に基づいて割当てを設定することができる。
【数５９】
2013175178.tif 000061
【００６２】
前出のアルゴリズムと同様に、このティアベースのアルゴリズムは、α＝０において個別プロビジョニングに還元され、α＝１において上記のセクションで述べた複数のインターバルの層ベースのカスケード過剰アルゴリズムへ還元される。
【００６３】
本発明の実施形態によれば、データセンタにおける長期の資源プロビジョニングのためのソリューションが提供される。具体的には、システムは、一週間あたり一日または複数日にわたって複数の時間周期などの複数の時間インターバルに対する更なる資源ニーズに対するモデルに対して複数のインターバルアルゴリズムを適用して、あまり頻繁ではないプロビジョニングの変更を可能にする。これによって、システムは人間のオペレータに資源のプロビジョニングを監督する機会を提供する。たとえば、人間のオペレータはジョブの資源使用を監視する監視ツールからの推薦を受け取り、その後、その推薦を手動的に適用することができる。システムがジョブの間で分離の程度を管理することが可能である。とりわけ、システムはほぼ完全な分離モードと非常に効率的なグループの統合を可能にする資源共有モードとの間を遷移することができる。例えば、ジョブが新たに導入され、それらの資源ニーズがあまり理解されない場合、システムは、ジョブがそれらのＱｏＳニーズを満たすことができる個別予約を受信する完全な分離モードで動作することができる。ジョブが良好にモデリングされ、資源の潜在的な共有が解析され実施された後、システムは、（全体のプール割当てアルゴリズムとその変形に基づいて）グループへの予約が行われて効率的なグループ統合を可能にする共有モードで動作することができる。
【００６４】
システムとモジュール
図３は、本発明の一実施形態による、資源のプロビジョニングコントローラを示す図である。図３において、資源プロビジョニングコントローラ３００は、ＱｏＳ識別子３０２と、資源使用モニタ３０４と、資源使用モデル構築子３０６、予約計算子３０８、過剰再分布モジュール３１０と、スケジューラ３１２と、ユーザインタフェース３１４と、を含む。
【００６５】
資源プロビジョニングコントローラ３００は、最高のパフォーマンスを達成するために、物理マシンまたはマシンのクラスタに位置付けされているジョブの資源のプロビジョニングをコントロールする。ＱｏＳ識別子３０２は各ジョブに関連付けられたＱｏＳ要件を識別する。一実施形態において、ＱｏＳ要件は不足確率によって表される。資源使用モニタ３０４はジョブごとに資源ニーズを監視し、このモニタはランダムであるか又はいくつかの時間的パターンを有することができる。資源使用モデル構築子３０６は、資源使用モニタ３０４から使用情報を受信し、これに応じて、ジョブごとに資源使用モデルを構築する。いくつかの実施形態において、資源使用モデル構築子３０６は、ジョブのプレフィックスグループのモデルを計算する。一実施形態において、資源使用モデルは一定量の資源を必要とするジョブのジョブまたはグループの確率を示している資源ニーズ分布関数を含む。更なる実施形態において、資源使用モデルはジョブまたはジョブのグループの資源ニーズの時間的分布を含む。例えば、ある特定のジョブが午前中に大量の資源を必要とする確率は高い。
【００６６】
構築された資源使用モデルとジョブごとのＱｏＳ要件に基づいて、予約計算子３０８はジョブごとに必要とされる予約を計算する。一実施形態において、全体のプール割当てアルゴリズムは必要とされる予約を計算するために使用される。より具体的には、予約計算子３０８は最初、ジョブをＱｏＳ降順で指数付けし、次に、最初のｋ−１個のジョブ＋ジョブｋに対する部分予約の部分和がｋ番目のジョブのＱｏＳレベルにおけるグループ総資源ニーズを満たすほどに大きくなるように最小の指数ｋを検索する。つまり、予約計算子３０８は、ジョブのＱｏＳ要件を満たすために必要とされる個別予約として第１のｋ−１個のジョブに対する予約と、ジョブのＱｏＳ要件を満たすために必要とされるその個別予約の分数としてｋ番目のジョブに対する予約と、残存する下位ＱｏＳジョブに対するゼロ予約と、を出力する。一実施形態において、予約計算子３０８は、全体のプール割当てアルゴリズムの固定小数点のばらつきを利用してこれらの予約を計算する。固定小数点のばらつきを実施するために、資源使用モデル構築子３０６は、ジョブと残存グループに対する資源ニーズを記述するジョブに対してジョイントモデルを構築する必要があることに留意されたい。
【００６７】
過剰再分布モジュール３１０は、未使用予約がジョブの間でどのように再分布されるかをコントロールする。一実施形態において、過剰再分布モジュール３１０はそれらのＱｏＳ要件に基づいてジョブに共有を割り当てる「共有」マシンを使用し、上位ＱｏＳジョブにより多くの共有が割り当てられる。このように、ＶＭｗａｒｅなどのシステムのオペレーションによって、共有数に比例して未使用予約を分布することによって残存ジョブを介して未使用予約をＱｏＳ順にカスケードさせる。一実施形態において、過剰再分布モジュール３１０は次に、各々がインラインの下位順序のＱｏＳジョブを直前に形成されたグループへ加算することによって形成される、グループの階層を構築する「グルーピング」マシンを使用する。新しく加算されたジョブに対して行われた予約は、現在のグループのＱｏＳ要件を満たすことができる（上位のＱｏＳジョブに対して既に行われている予約の和を上回る）ジョブに必要な更なる予約である。未使用予約が残存ジョブの間で均等に分布される場合には過剰再分布モジュール３１０は呼び出されないことに留意されたい。
【００６８】
一実施形態において、予約計算子３０８と過剰再分布モジュール３１０の出力はスケジューラ３１２へ送信され、スケジューラ３１２はジョブごとに実際の予約を行う。一実施形態において、出力は、人間のオペレータへの出力を提供する、ユーザインタフェース３１４へ送信される。人間のオペレータは、提示された資源プロビジョニングを検討し、このようなプロビジョニングを実行するかどうかを判定する。ユーザインタフェース３１４は、オペレータが分離モジュール３１６をコントロールすることを可能にする。より詳細には、オペレータは分離パラメータを設定することができる。分離パラメータを用いて、分離モジュール３１６は、ジョブ間の分離の程度を管理することができる。分離パラメータが０に設定されている場合、ジョブの全体分離が分離モジュール３１６で要求される。これによって、予約計算子３０８はジョブの個別のニーズに基づいてジョブに対する予約を計算する。分離パラメータが１に設定されている場合、分離モジュール３１６はジョブに資源を完全に共有させることができる。したがって、予約計算子３０８はグループとしてのジョブのニーズに基づいてジョブに対する予約を計算する。更なる実施形態において、人間のオペレータに代えて、分離モジュール３１６は、資源使用モニタ３０４からの入力に基づいて分離パラメータを算定する。システムがこれらのジョブの資源使用に関する知識が徐々に蓄積されていくにつれ、分離モジュール３１６は、分離パラメータを増加させる。
【００６９】
資源プロビジョニングコントローラ３００は、単一の時間インターバルまたは複数の時間インターバルに対する資源をプロビジョニングするために使用することができる。複数のインターバルプロビジョニングに使用する場合、資源使用モデル構築子３０６は、様々な時間インターバルに対する資源利用モデルを構築する必要があり、予約計算子３０８はすべての時間インターバルのＱｏＳ要件を満たすことができるジョブの予約を計算する。同様に、過剰な再分布モジュール３１０はまた、未使用の予約を再分布する際、複数のインターバルアルゴリズムを実施することも必要とする。複数のインターバルのためのプロビジョニング戦略は、ユーザインタフェース３１４によってオペレータに提示可能であり、オペレータはスケジューラ３１２へ複数の時間インターバルに対して提案されたプロビジョニングを同時に実行するように指示することができる。
【００７０】
図４は、本発明の一実施形態による、資源プロビジョニングの例示的なプロセスを示す流れ図である。動作中、システムはマシンのクラスタで実行されるジョブごとにＱｏＳ要件を識別し（動作４０２）、ジョブの資源使用履歴に基づいてジョブごとに資源使用モデルを構築する（動作４０４）。一実施形態において、確率密度関数（ＰＤＦ）などの資源の使用モデルは資源使用確率分布関数を含む。更なる実施形態において、資源使用確率分布関数は経時的に変化する。
【００７１】
次に、システムはジョブに対する資源予約を計算する（動作４０６）。所望される統合のレベル次第では、これらに限定されないが、単一の全体のプール割当てアルゴリズム、全体のプール割当てアルゴリズムの固定小数点のばらつき、およびティアベースのカスケード過剰アルゴリズムを含む、様々なアルゴリズムが資源予約を計算するために使用することができる。更なる実施形態に於いて、システムはジョブの間での分離の度合をコントロールするために分離パラメータを使用する。計算された資源予約が単一の時間インターバルまたは複数の時間インターバルに適用できることに留意されたい。複数のインターバルの場合、資源予約を計算する時にさまざまなアルゴリズムの複数のインターバルのばらつきがシステムによって実行される。
【００７２】
システムは必要に応じて計算された資源予約を人間のオペレータへ提供し（動作４０８）、オペレータからフィードバックを受信する（動作４１０）。オペレータのフィードバックに基づいて、システムは単一の時間インターバルまたは複数の時間インターバルに対して資源予約を実行する（動作４１２）。
【００７３】
図５は、本発明の一実施形態による、データセンタ内の資源プロビジョニングのための例示的なコンピュータシステムを示している。一実施形態において、コンピュータおよび通信システム５００は、プロセッサ５０２、メモリ５０４、および記憶装置５０６を含む。記憶装置５０６は、資源プロビジョニングアプリケーション５０８のみならずアプリケーション５１０と５１２などの他のアプリケーションも記憶している。動作中、資源プロビジョニングアプリケーション５０８は、記憶装置５０６からメモリ５０４へロードされ、その後、プロセッサ５０２によって実行される。プログラムを実行している間、プロセッサ５０２は、前述した機能を実行する。コンピュータおよび通信システム５００は、任意選択のディスプレイ５１４、キーボード５１６、およびポインティングデバイス５１８に連結される。
【００７４】
資源プロビジョニングの以上の考慮する点は、単一マシン、マシンのクラスタ、またはデータセンタを含む、データセンタ内の複数のレベルにおいて、適用することができることから、グループ統合は、資源利用を改良するためでなく、ＱｏＳ要件を満たすために使用することができることに留意されたい。
【図１】
2013175178.tif 000062
【図２】
2013175178.tif 000063
【図３】
2013175178.tif 000064
【図４】
2013175178.tif 000065
【図５】
2013175178.tif 000066