第3章 Java Solver のスタートガイド: クラウドバランシングの例

サンプルを使用して、Java コードを使用した基本的な Red Hat Business Optimizer Solver の開発を紹介します。

クラウドコンピューターを複数台所有し、そのクラウドコンピューターで複数のプロセスを実行する必要があると仮定します。コンピューターに各プロセスを割り当てる必要があります。

以下のハード制約を満たす必要があります。

  • すべてのコンピューターで、プロセスの合計容量を処理するのに必要なハードウェア最小要件を満たす必要があります。

    • CPU 容量: コンピューターには、最低でも、そのコンピューターに割り当てられたプロセスで必要とされる合計の CPU 処理能力が必要です。
    • メモリー容量: コンピューターには、最低でも、そのコンピューターに割り当てられたプロセスで必要とされる合計のメモリーが必要です。
    • ネットワーク容量: コンピューターには、最低でも、そのコンピューターに割り当てられたプロセスで必要とされる合計のネットワーク帯域幅が必要です。

以下のソフト制約を最適化する必要があります。

  • 1 つまたは複数のプロセスが割り当てられたコンピューターにはそれぞれ、保守コストが発生します (コンピューターごとに固定)。

    • コスト: 合計保守コストを最小限に抑えます。

これは、ビンパッキング 問題にあたります。以下に、簡単なアルゴリズムを使用して、制約が 2 つ (CPU およびメモリー) あるコンピューター 2 台に、4 つのプロセスを割り当てるという簡単な例を紹介します。

cloudBalanceUseCase

ここで使用しているアルゴリズムは FFD (First Fit Decreasing) アルゴリズムです。このアルゴリズムでは、最初に大きいプロセスを割り当ててから、残りのスペースに小さいプロセスを割り当てていきます。図からも分かるように、これは黄色いプロセス D を割り当てる容量が残っていないため、最適ではありません。

Business Optimizer は、別の、より良いアルゴリズムを使用して、より適した解 (ソリューション) を見つけます。また、データ (プロセスやコンピューター) と制約 (ハードウェア要件などの制約) の両方を増やして評価します。

以下のまとめは、「マシンの再割当て (Google ROADEF 2012)」 で説明されている、より多くの制約を使用した高度な実装や、この例に該当します。

cloudOptimizationValueProposition

表3.1 クラウドのバランス問題の規模

問題の規模コンピュータープロセス探索空間

コンピューター 2 台、プロセス 6 件

2

6

64

コンピューター 3 台、プロセス 9 件

3

9

10^4

コンピューター 4 台、プロセス 12 件

4

12

10^7

コンピューター 100 台、プロセス 300 件

100

300

10^600

コンピューター 200 台、プロセス 600 件

200

600

10^1380

コンピューター 400 台、プロセス 1200 件

400

1200

10^3122

コンピューター 800 台、プロセス 2400 件

800

2400

10^6967

3.1. ドメインモデルの設計

ドメインモデル を使用すると、どのクラスがプランニングエンティティーで、どのプロパティーがプランニング変数かが分かります。また、制約の簡素化、パフォーマンスの向上、これからのニーズに対する柔軟性の向上もサポートします。

3.1.1. ドメインモデルの設計

ドメインモデルを作成するには、問題の入力データを表現するオブジェクトをすべて定義します。この例では、オブジェクトはプロセスとコンピューターです。

ドメインモデルの個別のオブジェクトは、ソリューションおよび入力データを含む、問題の完全なデータセットを表現する必要があります。以下の例では、このオブジェクトにコンピューターの一覧とプロセスの一覧を格納します。プロセスごとにコンピューターが 1 台割り当てられ、コンピューター間のプロセスの配分が解となります。

手順

  1. ドメインモデルのクラス図を作成します。
  2. 正規化して複製データを削除します。
  3. クラスごとに サンプルインスタンス を記述します。サンプルインスタンスは、プランニングの目的に関連するエンティティープロパティーです。

    • Computer: 特定のハードウェアが搭載され、特定の保守コストが発生するコンピューターを表します。

      この例では、cpuPowermemorynetworkBandwidth、および costComputer クラスのサンプルインスタンスです。

    • Process: デマンドのあるプロセスを表します。このプロセスは、Planner によって Computer に割り当てられます。

      Process のサンプルインスタンスは requiredCpuPowerrequiredMemory、および requiredNetworkBandwidth です。

    • CloudBalance: コンピューター間のプロセスの配分を表します。CloudBalance には、特定のデータセットの Computer および Process がすべて含まれます。

      オブジェクトがすべてのデータセットおよび解を表す場合は、score を格納するサンプルインスタンスが必要です。Business Optimizer は異なる解のスコアを計算して、比較します。最高スコアの解が最適解となります。このため、CloudBalance のサンプルインスタンスは score になります。

  4. プランニング中にどの関係 (またはフィールド) が変化するか判断します。

    • Planning entity (プランニングエンティティー): 解決中に Business Optimizer が変更可能なクラス。この例では、別のコンピューターにプロセスを移動できるため Process クラスです。

      • Business Optimizer が変更できない入力データを表現するクラスは、問題ファクト として知られています。
    • Planning variable (プランニング変数): 解決時に変化するプランニングエンティティークラスのプロパティー。この例では、Process クラスの computer プロパティーがそれにあたります。
    • Planning solution (プランニングの解): 問題への解を表現するクラス。このクラスは、プランニングエンティティーをすべて含むデータセットを表す必要があります。この例では、CloudBalance クラスがそれにあたります。

以下の UML クラスの図では、Business Optimizer のコンセプトにすでにアノテーションが付けてあります。

cloudBalanceClassDiagram

examples/sources/src/main/java/org/optaplanner/examples/cloudbalancing/domain ディレクトリーに、この例のクラス定義が含まれています。

3.1.2. Computer クラス

Computer クラスは、データを保存する Java オブジェクトで、POJO (Plain Old Java Object) として知られています。通常、入力データを持つこの種のクラスが多くなります。

例3.1 CloudComputer.java

public class CloudComputer ... {

    private int cpuPower;
    private int memory;
    private int networkBandwidth;
    private int cost;

    ... // getters
}

3.1.3. Process クラス

Process クラスは、解決中に変更されるクラスです。

Business Optimizer に、computer プロパティーを変更できることを指示する必要があります。これには、クラスに @PlanningEntity のアノテーションを付けて、getComputer() ゲッターに @PlanningVariable のアノテーションを付けます。

当然ながら、Business Optimizer が解決中にプロパティーを変更できるように、この computer プロパティーにはセッターも必要です。

例3.2 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
    // ************************************************************************

    ...

}

Business Optimizer は、computer プロパティーに割り当てるのに、どの値を選択できるのかを把握しておく必要があります。これらの値は、プランニングの解の CloudBalance.getComputerList() メソッドから取得し、現在のデータセットに含まれる全コンピューターのリストを返します。

CloudProcess.getComputer() 上にある @PlanningVariablevalueRangeProviderRefs パラメーターは、CloudBalance.getComputerList() 上にある @ValueRangeProviderid に一致する必要があります。

注記

ゲッターの代わりにフィールドにアノテーションも使用できます。

3.1.4. CloudBalance クラス

CloudBalance クラスには、 @PlanningSolution アノテーション。

このクラスは、すべてのコンピューターおよびプロセスの一覧を保持します。プランニングの問題と、(初期化されている場合は) プランニングの解の両方を表します。

CloudBalance クラスには、以下の主要な属性が含まれます。

  • このクラスは、Business Optimizer が変更可能なプロセスコレクションを保持します。ゲッター getProcessList()@PlanningEntityCollectionProperty アノテーションを付けて、Business Optimizer が変更できるプロセスを Business Optimizer で取得できるようにします。解を保存するには、Business Optimizer は、変更したプロセス一覧で、クラスの新規インスタンスを初期化します。

    1. これには @PlanningScore のアノテーションがついた score プロパティーも含まれており、このプロパティーは、現在の状態の解の Score を指します。Business Optimizer は、解のインスタンス向けに Score を計算すると自動的にこのプロパティーを更新するため、このプロパティーにはセッターが必要です。
    2. 特に、Drools でスコアの計算をする場合、computerList のプロパティーは @ProblemFactCollectionProperty のアノテーションを付けて、Business Optimizer がコンピューターのリスト (問題ファクト) を取得し、デシジョンエンジンに公開できるようにする必要があります。

例3.3 CloudBalance.java

@PlanningSolution
public class CloudBalance ... {

    private List<CloudComputer> computerList;

    private List<CloudProcess> processList;

    private HardSoftScore score;

    @ValueRangeProvider(id = "computerRange")
    @ProblemFactCollectionProperty
    public List<CloudComputer> getComputerList() {
        return computerList;
    }

    @PlanningEntityCollectionProperty
    public List<CloudProcess> getProcessList() {
        return processList;
    }

    @PlanningScore
    public HardSoftScore getScore() {
        return score;
    }

    public void setScore(HardSoftScore score) {
        this.score = score;
    }

    ...
}