第2章 クイックスタート
2.1. クラウドのバランスのチュートリアル
2.1.1. 問題の詳細
クラウドコンピューターを複数台所有し、そのクラウドコンピューターで複数のプロセスを実行する必要があると仮定します。以下の 4 つの制約がある中で、コンピューターに各プロセスを割り当てます。
以下のハード制約を満たす必要があります。
すべてのコンピューターで、プロセスの合計容量を処理するのに必要なハードウェア最小要件を満たす必要があります。
- コンピューターには、最低でも、そのコンピューターに割り当てられたプロセスで必要とされる合計の CPU 処理能力が必要です。
- コンピューターには、最低でも、そのコンピューターに割り当てられたプロセスで必要とされる合計のメモリーが必要です。
- コンピューターには、最低でも、そのコンピューターに割り当てられたプロセスで必要とされる合計のネットワーク帯域幅が必要です。
以下のソフト制約を最適化する必要があります。
1 つまたは複数のプロセスが割り当てられたコンピューターにはそれぞれ、保守コストが発生します (コンピューターごとに固定)。
- 合計保守コストを最小限に抑えます。
これは、ビンパッキング 問題にあたります。以下に、簡単なアルゴリズムを使用して、制約が 2 つ (CPU およびメモリー) があるコンピューター 2 台に、4 つのプロセスを割り当てるという簡単な例を紹介します。
ここで使用しているアルゴリズムは FFD (First Fit Decreasing) アルゴリズムです。このアルゴリズムでは、最初に大きいプロセスを割り当ててから、残りのスペースに小さいプロセスを割り当てていきます。図からも分かるように、黄色いプロセス「D」を割り当てる容量が残っていないため、最適ではありません。
Planner は、より適切な、別のアルゴリズムを使用して、より適した解 (ソリューション) を見つけます。また、データ (プロセス、コンピューター) と制約 (ハードウェア要件やその他の制約) の両方を増やして評価します。では、以下のシナリオで Planner をどのように使用できるかをご覧ください。
2.1.2. 問題の規模
問題の規模 | コンピューター | プロセス | 探索空間 |
---|---|---|---|
コンピューター 2 台、プロセス 6 件 |
2 |
6 |
64 |
コンピューター 3 台、プロセス 9 件 |
3 |
9 |
104 |
コンピューター 4 台、プロセス 12 件 |
4 |
12 |
107 |
コンピューター 100 台、プロセス 300 件 |
100 |
300 |
10600 |
コンピューター 200 台、プロセス 600 件 |
200 |
600 |
101380 |
コンピューター 400 台、プロセス 1200 件 |
400 |
1200 |
103122 |
コンピューター 800 台、プロセス 2400 件 |
800 |
2400 |
106967 |
2.1.3. ドメインモデルの設計
ドメインモデルから始めましょう。
-
Computer
: 特定のハードウェア (CPU 処理能力、RAM メモリー、ネットワーク帯域幅) が搭載され、特定の保守コストが発生するコンピューターを表します。 -
Process
: デマンドのあるプロセスを表します。このプロセスは、Planner によってComputer
に割り当てられます。 -
CloudBalance
: 問題を表します。CloudBalance には、特定のデータセットに関するComputer
およびProcess
がすべて含まれます。
上の UML クラスの図では、Planner のコンセプトにすでにアノテーションが付けてあります。
-
PlanningEntity (プランニングエンティティー): 計画時に変化するクラス。この例では、
Process
クラスがそれにあたります。 -
PlanningVariable (プランニング変数): 計画時に変化するプランニングエンティティークラスのプロパティー。この例では、
Process
クラスのcomputer
プロパティーがそれにあたります。 -
PlanningSolution (ソリューション): プランニングエンティティーをすべて含むデータセットを表現するクラス。この例では、
CloudBalance
クラスがそれにあたります。
2.1.4. メインメソッド
では、実際に試してみましょう。任意の IDE にサンプルを ダウンロードして、設定します。org.optaplanner.examples.cloudbalancing.app.CloudBalancingHelloWorld
を実行します。デフォルトでは、120 秒間実行するように設定されています。これにより、以下のコードが実行します。
例2.1 CloudBalancingHelloWorld.java
public class CloudBalancingHelloWorld { public static void main(String[] args) { // Build the Solver SolverFactory<CloudBalance> solverFactory = SolverFactory.createFromXmlResource( "org/optaplanner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml"); Solver<CloudBalance> solver = solverFactory.buildSolver(); // Load a problem with 400 computers and 1200 processes CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200); // Solve the problem CloudBalance solvedCloudBalance = solver.solve(unsolvedCloudBalance); // Display the result System.out.println("\nSolved cloudBalance with 400 computers and 1200 processes:\n" + toDisplayString(solvedCloudBalance)); } ... }
このコードサンプルにより、以下が行われます。
Solver の設定をもとに
Solver
を構築します (ここでは、クラスパスの XML ファイル を使用します)。SolverFactory<CloudBalance> solverFactory = SolverFactory.createFromXmlResource( "org/optaplanner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml"); Solver solver<CloudBalance> = solverFactory.buildSolver();
問題を読み込みます。
CloudBalancingGenerator
が無作為に問題を生成します。これを、たとえばデータベースから実際の問題を読み込むクラスに置き換えてください。CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200);
問題を解決します。
CloudBalance solvedCloudBalance = solver.solve(unsolvedCloudBalance);
結果を表示します。
System.out.println("\nSolved cloudBalance with 400 computers and 1200 processes:\n" + toDisplayString(solvedCloudBalance));
Solver
の構築部分だけが唯一複雑になります。これについては、次のセクションで詳しく説明します。
2.1.5. Solver の設定
Solver の設定を見てみましょう。
例2.2 cloudBalancingSolverConfig.xml
<?xml version="1.0" encoding="UTF-8"?> <solver> <!-- Domain model configuration --> <scanAnnotatedClasses/> <!-- Score configuration --> <scoreDirectorFactory> <scoreDefinitionType>HARD_SOFT</scoreDefinitionType> <easyScoreCalculatorClass>org.optaplanner.examples.cloudbalancing.solver.score.CloudBalancingEasyScoreCalculator</easyScoreCalculatorClass> <!--<scoreDrl>org/optaplanner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>--> </scoreDirectorFactory> <!-- Optimization algorithms configuration --> <termination> <secondsSpentLimit>30</secondsSpentLimit> </termination> </solver>
Solver の設定は、3 つの部分で構成されます。
ドメインモデルの設定: Planner が変更できるものは何ですか? Planner にドメインクラスを指定する必要があります。ここでは、(
@PlanningEntity
または@PlanningSolution
アノテーションに対して) クラスパス内の全クラスを自動的にスキャンします。<scanAnnotatedClasses/>
スコアの設定: Planner はプランニング変数をどのように最適化すればよいでしょうか? また、目的は何でしょうか? ここでは、ハード制約とソフト制約を使用するため、
HardSoftScore
を使用します。ただし、Planner に、ビジネス要件に合ったスコアの計算方法を指定する必要があります。後ほど、スコアの計算方法を 2 種類 (単純な Java 実装の使用、または Drools DRL の使用) 紹介します。<scoreDirectorFactory> <scoreDefinitionType>HARD_SOFT</scoreDefinitionType> <easyScoreCalculatorClass>org.optaplanner.examples.cloudbalancing.solver.score.CloudBalancingEasyScoreCalculator</easyScoreCalculatorClass> <!--<scoreDrl>org/optaplanner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>--> </scoreDirectorFactory>
最適化のアルゴリズム設定: Planner はどのように最適化しますか? この例では、(最適化アルゴリズムが明示的に設定されていないので) 30 秒間、デフォルトの 最適化アルゴリズム を使用します。
<termination> <secondsSpentLimit>30</secondsSpentLimit> </termination>
Planner は、数秒 (リアルタイム計画 では 15 ミリ秒未満になる場合も) でも良い結果は得られますが、時間が長くなればなるほど、結果は良くなります。高度なユースケースでは、ハードな時間制限以外に、終了の条件 を使用することが適しています。
デフォルトのアルゴリズムでも、人的作業による計画や、多くの社内の実装よりもはるかに優れていますが、さらに良くするためには、ベンチマーカー を使用して 高度な調整 (Power tweak) を行います。
では、ドメインモデルクラスとスコア設定について検証しましょう。
2.1.6. ドメインモデルの実装
2.1.6.1. Computer クラス
Computer
クラスは POJO (Plain Old Java Object) で、一般的には、この種類のクラスがよく使用されます。
例2.3 CloudComputer.java
public class CloudComputer ... { private int cpuPower; private int memory; private int networkBandwidth; private int cost; ... // getters }
2.1.6.2. Process クラス
Process
クラスは、特に重要です。このクラスが computer
フィールドを変更できることを Planner に指定する必要があるため、このクラスに @PlanningEntity
、getComputer()
ゲッターに @PlanningVariable
アノテーションを付けます。
例2.4 CloudProcess.java
@PlanningEntity(...) public class CloudProcess ... { private int requiredCpuPower; private int requiredMemory; private int requiredNetworkBandwidth; private CloudComputer computer; ... // getters @PlanningVariable(valueRangeProviderRefs = {"computerRange"}) public CloudComputer getComputer() { return computer; } public void setComputer(CloudComputer computer) { computer = computer; } // ************************************************************************ // Complex methods // ************************************************************************ ... }
Planner が computer
フィールドに選択できる値は、Solution
実装の CloudBalance.getComputerList()
メソッドから取得します。このメソッドは、現在のデータセット内のコンピューター一覧を返します。valueRangeProviderRefs
プロパティーを使用して、この情報を Planner に渡します。
ゲッターアノテーションの代わりに、フィールドアノテーション を使用することもできます。
2.1.6.3. CloudBalance クラス
CloudBalance
クラスは、Solution
インターフェースを実装します。これは、コンピューターおよびプロセスの一覧を保持します。変更可能なプロセスのコレクションを取得する方法を Planner に指定する必要があるため、getProcessList
のゲッターに @PlanningEntityCollectionProperty
アノテーションを付ける必要があります。
CloudBalance
クラスには、score
プロパティーも含まれます。このプロパティーは、対象 Solution
インスタンスにおけるそのときの スコア
を表します。
例2.5 CloudBalance.java
@PlanningSolution public class CloudBalance ... implements Solution<HardSoftScore> { private List<CloudComputer> computerList; private List<CloudProcess> processList; private HardSoftScore score; @ValueRangeProvider(id = "computerRange") public List<CloudComputer> getComputerList() { return computerList; } @PlanningEntityCollectionProperty public List<CloudProcess> getProcessList() { return processList; } ... public HardSoftScore getScore() { return score; } public void setScore(HardSoftScore score) { this.score = score; } // ************************************************************************ // Complex methods // ************************************************************************ public Collection<? extends Object> getProblemFacts() { List<Object> facts = new ArrayList<Object>(); facts.addAll(computerList); // Do not add the planning entity's (processList) because that will be done automatically return facts; } ... }
getProblemFacts()
メソッドは、スコア計算に Drools を使用した場合に必要になります。他のスコア計算タイプには必要ありません。
2.1.7. スコアの設定
Planner は、スコア
が最も高いソリューション
を探します。この例では、HardSoftScore
を使用し、Planner がハード制約に違反していない (またはハードウェア要件を満たす) ソリューションと、ソフト制約に違反する数が少ない (メンテナンスコストが低い) ソリューションを探します。
また、Planner には、ドメイン固有のスコア制約についても指定する必要があります。このようなスコア関数の実装には複数の方法があります。
- Easy Java
- Java インクリメント演算子
- Drools
2 つの異なる実装について見ていきます。
2.1.7.1. Easy Java のスコア設定
スコア関数の定義方法の 1 つに、プレーン Java での EasyScoreCalculator
インターフェース実装があります。
<scoreDirectorFactory> <scoreDefinitionType>HARD_SOFT</scoreDefinitionType> <easyScoreCalculatorClass>org.optaplanner.examples.cloudbalancing.solver.score.CloudBalancingEasyScoreCalculator</easyScoreCalculatorClass> </scoreDirectorFactory>
calculateScore(Solution)
メソッドを実装すれば HardSoftScore
インスタンスを返します。
例2.6 CloudBalancingEasyScoreCalculator.java
public class CloudBalancingEasyScoreCalculator implements EasyScoreCalculator<CloudBalance> { /** * A very simple implementation. The double loop can easily be removed by using Maps as shown in * {@link CloudBalancingMapBasedEasyScoreCalculator#calculateScore(CloudBalance)}. */ public HardSoftScore calculateScore(CloudBalance cloudBalance) { int hardScore = 0; int softScore = 0; for (CloudComputer computer : cloudBalance.getComputerList()) { int cpuPowerUsage = 0; int memoryUsage = 0; int networkBandwidthUsage = 0; boolean used = false; // Calculate usage for (CloudProcess process : cloudBalance.getProcessList()) { if (computer.equals(process.getComputer())) { cpuPowerUsage += process.getRequiredCpuPower(); memoryUsage += process.getRequiredMemory(); networkBandwidthUsage += process.getRequiredNetworkBandwidth(); used = true; } } // Hard constraints int cpuPowerAvailable = computer.getCpuPower() - cpuPowerUsage; if (cpuPowerAvailable < 0) { hardScore += cpuPowerAvailable; } int memoryAvailable = computer.getMemory() - memoryUsage; if (memoryAvailable < 0) { hardScore += memoryAvailable; } int networkBandwidthAvailable = computer.getNetworkBandwidth() - networkBandwidthUsage; if (networkBandwidthAvailable < 0) { hardScore += networkBandwidthAvailable; } // Soft constraints if (used) { softScore -= computer.getCost(); } } return HardSoftScore.valueOf(hardScore, softScore); } }
Maps
を使用して最適化し、processList
を 1 回だけ反復した場合でも、インクリメンタルスコアの計算 が行われないため、処理が遅くなります。これを修正するには、Java インクリメント演算子のスコア関数、または Drools のスコア関数のいずれかを使用します。では、Drools スコア関数について見ていきます。
2.1.7.2. Drools スコア関数
クラスパスに scoreDrl
リソースを追加すれば、Drools ルールエンジンをスコア関数として使用できます。
<scoreDirectorFactory> <scoreDefinitionType>HARD_SOFT</scoreDefinitionType> <scoreDrl>org/optaplanner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl> </scoreDirectorFactory>
まず、すべてのコンピューターに、すべてのプロセスに対応するのに十分な CPU、メモリー、ネットワーク帯域幅があることを確認します。これをハード制約とします。
例2.7 cloudBalancingScoreRules.drl - ハード制約
... import org.optaplanner.examples.cloudbalancing.domain.CloudBalance; import org.optaplanner.examples.cloudbalancing.domain.CloudComputer; import org.optaplanner.examples.cloudbalancing.domain.CloudProcess; global HardSoftScoreHolder scoreHolder; // ############################################################################ // Hard constraints // ############################################################################ rule "requiredCpuPowerTotal" when $computer : CloudComputer($cpuPower : cpuPower) $requiredCpuPowerTotal : Number(intValue > $cpuPower) from accumulate( CloudProcess( computer == $computer, $requiredCpuPower : requiredCpuPower), sum($requiredCpuPower) ) then scoreHolder.addHardConstraintMatch(kcontext, $cpuPower - $requiredCpuPowerTotal.intValue()); end rule "requiredMemoryTotal" ... end rule "requiredNetworkBandwidthTotal" ... end
次に、これらの制約を満たした場合に、メンテナンスコストを最小限に抑えられるように、ソフト制約としてその条件を追加します。
例2.8 cloudBalancingScoreRules.drl - ソフト制約
// ############################################################################ // Soft constraints // ############################################################################ rule "computerCost" when $computer : CloudComputer($cost : cost) exists CloudProcess(computer == $computer) then scoreHolder.addSoftConstraintMatch(kcontext, - $cost); end
スコアの計算に Drools ルールエンジンを使用する場合は、デシジョンテーブル (エクセルまたは Web ベース) や KIE Workbench など、他の Drools 技術と統合することができます。
2.1.8. このチュートリアルの応用
上記のようなシンプルな例が設定できたら、さらに掘り下げてみてください。ドメインモデルを改良して、以下のような制約を追加してみてください。
-
すべての
プロセス
がサービス
に属する。コンピューターはクラッシュする可能性があるため、同じサービスを実行するプロセスは、別のコンピューターに割り当てる必要がある。 -
すべての
コンピューター
がビル
に設置されている。ビルが火災にあう可能性があるので、同じサービスのプロセスは、別のビルに設置されているコンピューターに割り当てる必要がある。