JBoss.orgCommunity Documentation
Assign each process to a computer.
Hard constraints:
Every computer should be able to handle the sum of each of the minimal hardware requirements (CPR, RAM, network bandwidth) of all its processes.
Soft constraints:
Each computer that has one or more processes assigned, has a fixed maintenance cost. Minimize the total cost.
This is a form of bin packing. Here's a simplified example where we assign 4 processes to 2 computers:
The domain model is pretty simple:
Computer
: represents a computer with a capacity and cost.
Process
: represents a process with a demand. Needs to be assigned to a
Computer
.
CloudBalance
: represents a problem. Contains every Computer
and
Process
.
Download and configure the examples in your favorite IDE.
Run org.drools.planner.examples.cloudbalancing.app.CloudBalancingHelloWorld
. By default, it is
configured to run for 120 seconds.
Example 2.1. CloudBalancingHelloWorld.java
public class CloudBalancingHelloWorld {
public static void main(String[] args) {
// Build the Solver
SolverFactory solverFactory = new XmlSolverFactory(
"/org/drools/planner/examples/cloudbalancing/solver/cloudBalancingSolverConfig.xml");
Solver solver = solverFactory.buildSolver();
// Load a problem with 400 computer and 1200 processes
CloudBalance unsolvedCloudBalance = new CloudBalancingGenerator().createCloudBalance(400, 1200);
// Solve the problem
solver.setPlanningProblem(unsolvedCloudBalance);
solver.solve();
CloudBalance solvedCloudBalance = (CloudBalance) solver.getBestSolution();
// Display the result
System.out.println("\nSolved cloudBalance with 400 computers and 1200 processes:\n"
+ toDisplayString(solvedCloudBalance));
}
...
}
This code above basically does this:
Build the Solver
.
Load the problem. CloudBalancingGenerator
generates a random problem: you'll replace
this with a class that loads a real problem, for example from a database.
Solve the problem.
Display the result.
The only non-obvious part is building the Solver
. Let's examine that.
Take a look at the solver configuration:
Example 2.2. cloudBalancingSolverConfig.xml
<?xml version="1.0" encoding="UTF-8"?>
<solver>
<!--<environmentMode>DEBUG</environmentMode>-->
<!-- Domain model configuration -->
<solutionClass>org.drools.planner.examples.cloudbalancing.domain.CloudBalance</solutionClass>
<planningEntityClass>org.drools.planner.examples.cloudbalancing.domain.CloudProcess</planningEntityClass>
<!-- Score configuration -->
<scoreDirectorFactory>
<scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>
<simpleScoreCalculatorClass>org.drools.planner.examples.cloudbalancing.solver.score.CloudBalancingSimpleScoreCalculator</simpleScoreCalculatorClass>
<!--<scoreDrl>/org/drools/planner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>-->
</scoreDirectorFactory>
<!-- Optimization algorithms configuration -->
<termination>
<maximumSecondsSpend>120</maximumSecondsSpend>
</termination>
<constructionHeuristic>
<constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
<constructionHeuristicPickEarlyType>FIRST_LAST_STEP_SCORE_EQUAL_OR_IMPROVING</constructionHeuristicPickEarlyType>
</constructionHeuristic>
<localSearch>
<selector>
<selector>
<moveFactoryClass>org.drools.planner.core.move.generic.GenericChangeMoveFactory</moveFactoryClass>
</selector>
<selector>
<moveFactoryClass>org.drools.planner.core.move.generic.GenericSwapMoveFactory</moveFactoryClass>
</selector>
</selector>
<acceptor>
<planningEntityTabuSize>7</planningEntityTabuSize>
</acceptor>
<forager>
<minimalAcceptedSelection>1000</minimalAcceptedSelection>
</forager>
</localSearch>
</solver>
This consists out of 3 parts:
Domain model configuration: What can Planner change?
Score configuration: What should Planner optimize?
Optimization algorithms configuration: How should Planner optimize it? Don't worry about this for now: this is a good default configuration that works on most planning problems.
Let's examine the domain model and the score configuration.
The class Computer
is a POJO (Plain Old Java Object), nothing special. Usually, you'll
have more of these kind of classes.
Example 2.3. CloudComputer.java
public class CloudComputer ... {
private int cpuPower;
private int memory;
private int networkBandwidth;
private int cost;
... // getters
}
The class Process
is a little bit special. We need to tell Planner that it can change the
field computer
, so we annotate the class with @PlanningEntity
and the getter
getComputer
with @PlanningVariable
:
Example 2.4. CloudProcess.java
@PlanningEntity(...)
public class CloudProcess ... {
private int requiredCpuPower;
private int requiredMemory;
private int requiredNetworkBandwidth;
private CloudComputer computer;
... // getters
@PlanningVariable(...)
@ValueRange(type = ValueRangeType.FROM_SOLUTION_PROPERTY, solutionProperty = "computerList")
public CloudComputer getComputer() {
return computer;
}
public void setComputer(CloudComputer computer) {
computer = computer;
}
// ************************************************************************
// Complex methods
// ************************************************************************
public CloudProcess clone() {
CloudProcess clone = new CloudProcess();
clone.id = id;
clone.requiredCpuPower = requiredCpuPower;
clone.requiredMemory = requiredMemory;
clone.requiredNetworkBandwidth = requiredNetworkBandwidth;
clone.computer = computer;
return clone;
}
...
}
The values that Planner can chose from for the field computer
, are retrieved from a
method on the Solution
implementation:
CloudBalance.getComputerList()
.
The class CloudBalance
implements the Solution
interface. It holds a
list of all computers and processes. It has a property score
which is the
Score
of that Solution
instance in it's current state:
Example 2.5. CloudBalance.java
public class CloudBalance ... implements Solution<HardAndSoftScore> {
private List<CloudComputer> computerList;
private List<CloudProcess> processList;
private HardAndSoftScore score;
public List<CloudComputer> getComputerList() {
return computerList;
}
@PlanningEntityCollectionProperty
public List<CloudProcess> getProcessList() {
return processList;
}
...
public HardAndSoftScore getScore() {
return score;
}
public void setScore(HardAndSoftScore 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;
}
/**
* Clone will only deep copy the {@link #processList}.
*/
public CloudBalance cloneSolution() {
CloudBalance clone = new CloudBalance();
clone.id = id;
clone.computerList = computerList;
List<CloudProcess> clonedProcessList = new ArrayList<CloudProcess>(
processList.size());
for (CloudProcess process : processList) {
CloudProcess clonedProcess = process.clone();
clonedProcessList.add(clonedProcess);
}
clone.processList = clonedProcessList;
clone.score = score;
return clone;
}
...
}
The method getProblemFacts()
is only needed for score calculation with Drools. It's not
needed with the other score calculation types.
The method clone()
is required. Planner uses it to make a clone of the best
Solution
in encounters during searching.
Planner will search for the Solution
with the highest Score
. We're
using a HardAndSoftScore
, which means Planner will look for the solution with no hard
constraints broken (hardware requirements) and as little as possible soft constraints broken (maintenance
cost).
There are several ways to implement the score function:
Simple Java
Incremental Java
Drools
Let's look at 2 of those:
One way to define a score function is to implement the interface SimpleScoreCalculator
in plain Java.
<scoreDirectorFactory>
<scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>
<simpleScoreCalculatorClass>org.drools.planner.examples.cloudbalancing.solver.score.CloudBalancingSimpleScoreCalculator</simpleScoreCalculatorClass>
</scoreDirectorFactory>
Just implement the method calculateScore(Solution)
to return a
DefaultHardAndSoftScore
instance.
Example 2.6. CloudBalance.java
public class CloudBalancingSimpleScoreCalculator implements SimpleScoreCalculator<CloudBalance> {
public Score calculateScore(CloudBalance cloudBalance) {
Map<CloudComputer, Integer> cpuPowerUsageMap = new HashMap<>();
...
for (CloudComputer computer : cloudBalance.getComputerList()) {
cpuPowerUsageMap.put(computer, 0);
...
}
Set<CloudComputer> usedComputerSet = new HashSet<>();
visitProcessList(cpuPowerUsageMap, ...,
usedComputerSet, cloudBalance.getProcessList());
int hardScore = sumHardScore(cpuPowerUsageMap, ...);
int softScore = sumSoftScore(usedComputerSet);
return DefaultHardAndSoftScore.valueOf(hardScore, softScore);
}
private void visitProcessList(Map<CloudComputer, Integer> cpuPowerUsageMap, ...
Set<CloudComputer> usedComputerSet, List<CloudProcess> processList) {
// We loop through the processList only once for performance
for (CloudProcess process : processList) {
CloudComputer computer = process.getComputer();
if (computer != null) {
int cpuPowerUsage = cpuPowerUsageMap.get(computer) + process.getRequiredCpuPower();
cpuPowerUsageMap.put(computer, cpuPowerUsage);
...
usedComputerSet.add(computer);
}
}
}
private int sumHardScore(Map<CloudComputer, Integer> cpuPowerUsageMap, ...) {
int hardScore = 0;
for (Map.Entry<CloudComputer, Integer> usageEntry : cpuPowerUsageMap.entrySet()) {
CloudComputer computer = usageEntry.getKey();
int cpuPowerAvailable = computer.getCpuPower() - usageEntry.getValue();
if (cpuPowerAvailable < 0) {
hardScore += cpuPowerAvailable;
}
}
...
return hardScore;
}
private int sumSoftScore(Set<CloudComputer> usedComputerSet) {
int softScore = 0;
for (CloudComputer usedComputer : usedComputerSet) {
softScore -= usedComputer.getCost();
}
return softScore;
}
}
Despite that the code above is optimized with Map
s to only go through the
processList
once, it is still slow because it doesn't do
incremental score calculation. To fix that, either use an incremental Java score function or a Drools score
function.
To use Drools as a score function, simply add a scoreDrl
resource in the
classpath:
<scoreDirectorFactory>
<scoreDefinitionType>HARD_AND_SOFT</scoreDefinitionType>
<scoreDrl>/org/drools/planner/examples/cloudbalancing/solver/cloudBalancingScoreRules.drl</scoreDrl>
</scoreDirectorFactory>
First, we want to make sure that all computers have enough CPU, RAM and network bandwidth to support all their processes, so we make those hard constraints:
Example 2.7. cloudBalancingScoreRules.drl - hard constraints
... import org.drools.planner.examples.cloudbalancing.domain.CloudBalance; import org.drools.planner.examples.cloudbalancing.domain.CloudComputer; import org.drools.planner.examples.cloudbalancing.domain.CloudProcess; global HardAndSoftScoreHolder scoreHolder; // ############################################################################ // Hard constraints // ############################################################################ rule "requiredCpuPowerTotal" when $computer : CloudComputer($cpuPower : cpuPower) $requiredCpuPowerTotal : Number(intValue > $cpuPower) from accumulate( CloudProcess( computer == $computer, $requiredCpuPower : requiredCpuPower), sum($requiredCpuPower) ) then insertLogical(new IntConstraintOccurrence("requiredCpuPowerTotal", ConstraintType.NEGATIVE_HARD, $requiredCpuPowerTotal.intValue() - $cpuPower, $computer)); end rule "requiredMemoryTotal" ... end rule "requiredNetworkBandwidthTotal" ... end // ############################################################################ // Calculate hard score // ############################################################################ // Accumulate hard constraints rule "hardConstraintsBroken" salience -1 // Do the other rules first (optional, for performance) when $hardTotal : Number() from accumulate( IntConstraintOccurrence(constraintType == ConstraintType.NEGATIVE_HARD, $weight : weight), sum($weight) ) then scoreHolder.setHardConstraintsBroken($hardTotal.intValue()); end
Next, if those constraints are met, we want to minimize the maintenance cost, so we add that as a soft constraint:
Example 2.8. cloudBalancingScoreRules.drl - soft constraints
// ############################################################################ // Soft constraints // ############################################################################ rule "computerCost" when $computer : CloudComputer($cost : cost) exists CloudProcess(computer == $computer) then insertLogical(new IntConstraintOccurrence("computerCost", ConstraintType.NEGATIVE_SOFT, $cost, $computer)); end // ############################################################################ // Calculate soft score // ############################################################################ // Accumulate soft constraints rule "softConstraintsBroken" salience -1 // Do the other rules first (optional, for performance) when $softTotal : Number() from accumulate( IntConstraintOccurrence(constraintType == ConstraintType.NEGATIVE_SOFT, $weight : weight), sum($weight) ) then scoreHolder.setSoftConstraintsBroken($softTotal.intValue()); end
Now that this simple example works, you can go further. Try this:
Each Process
belongs to a Service
. A computer can crash, so
processes running the same service should be assigned to different Computers.
Each Computer
is located in a Building
. A building can burn down,
so processes of the same services should be assigned to computers in different buildings.