nova-solver-scheduler/solver_scheduler.rst

Solver Scheduler

The Solver Scheduler provides an extensible mechanism for making smarter, complex constraints optimization based resource scheduling in Nova. This driver supports pluggable Solvers, that can leverage existing complex constraint solving frameworks, available in open source such as PULP, CVXOPT, Google OR-TOOLS, etc. This Scheduler is currently supported to work with Compute Nodes in Nova.

The Nova compute resource placement can be described as a problem of placing a set of VMs on a set of physical hosts, where each VM has a set of resource requirements that have to be satisfied by a host with available resource capacity. In addition to the constraints, we optimize the solution for some cost metrics, so that the net cost of placing all VMs to certain hosts is minimized.

A pluggable Solver used by the Solver Scheduler driver models the Nova compute placement request as a constraint optimization problem using a set of constraints derived from the placement request specification and a net cost value to optimize. A Solver implementation should model the constraints and costs and feed it to a constraint problem specification, which is eventually solved by using any external solvers such as the COIN-OR CLP, CBC, GLPK, and so on.

The Nova compute resource placement optimization problem when subject to a set of linear constraints, can be formulated and solved as a linear programming problem. A linear programming (LP) problem involves maximizing or minimizing a linear function subject to linear constraints.

Solvers

All Solver implementations will be in the module (nova_solverscheduler.scheduler.solvers). A solver implementation should be a subclass of solvers.BaseHostSolver and they implement the host_solve method. This method returns a list of host-instance tuples after solving the constraints optimization problem.

A Reference Solver Implementation

HostsPulpSolver <nova_solverscheduler.scheduler.solvers.hosts_pulp_solver.HostsPulpSolver> is a reference solver implementation that models the Nova scheduling problem as a linear programming (LP) problem using the PULP modeling framework. This example implementation is a working solver that includes the required disk and memory as constraints, and uses the free ram as a cost metric to maximize (for spreading hosts), or minimize (for stacking) for the LP problem.

An example LP problem formulation is provided below to describe how this example solver models the problem in LP.

Consider there are 2 hosts Host_1 and Host_2, with available resources described as a tuple (usable_disk_mb, usable_memory_mb, free_ram_mb):

• `Host_1`: (2048, 2048, 2048)
• `Host_2`: (4096, 1536, 1536)

There are two VM requests with the following disk and memory requirements:

• `VM_1`: (1024, 512)
• `VM_2`: (1024, 512)

To formulate this problem as a LP problem, we use the variables: X11, X12, X21, X22. Here, a variable Xij takes the value 1 if VM_i is placed on Host_j, 0 otherwise.

If the problem objective is to minimize the cost metric of free_ram_mb, the mathematical LP formulation of this example is as follows:

Minimize (2048*X11 + 2048*X21 + 1536*X12 + 1536*X22)

 subject to constraints:

 X11*1024 + X21*1024 <= 2048 (disk maximum supply for Host_1)
 X11*512  + X21*512  <= 2048 (memory maximum supply for Host_1)
 X12*1024 + X22*1024 <= 4096 (disk maximum supply for Host_2)
 X12*512  + X22*512  <= 1536 (memory maximum supply for Host_2)
 X11*1024 + X12*1024 >= 1024 (disk minimum demand for VM_1)
 X11*512  + X12*512  >= 512  (memory minimum demand for VM_1)
 X21*1024 + X22*1024 >= 1024 (disk minimum demand for VM_2)
 X21*512  + X22*512  >= 512  (memory minimum demand for VM_2)
 X11      + X12      == 1    (VM_1 can run in only 1 Host)
 X21      + X22      == 1    (VM_2 can run in only 1 Host)

X11 = 0, X12 = 1, X21 = 0, and X22 = 1 happens to be the optimal solution, implying, both VM_1 and VM_2 will be hosted in Host_2.

HostsPulpSolver <nova_solverscheduler.scheduler.solvers.hosts_pulp_solver.HostsPulpSolver> models such LP problems using the PULP LP modeler written in Python. This problem is solved for an optimal solution using an external solver supported by PULP such as CLP, CBC, GLPK, etc. By default, PULP uses the CBC solver, which is packaged with the coinor.pulp distribution.

Additional Solver implementations are planned in the roadmap, that support pluggable constraints and costs.

Configuration

To use Solver Scheduler, the nova.conf should contain the following settings under the [solver_scheduler] namespace:

The Solver Scheduler driver to use (required):

scheduler_driver=nova_solverscheduler.scheduler.solver_scheduler.ConstraintSolverScheduler

The Solver implementation to use:

scheduler_host_solver=nova_solverscheduler.scheduler.solvers.hosts_pulp_solver.HostsPulpSolver

When using the default provided Solver implementation HostsPulpSolver <nova_solverscheduler.scheduler.solvers.hosts_pulp_solver.HostsPulpSolver>, the following default values of these settings can be modified:

These are under the [DEFAULT] namespace, as they are also being used by the Filter Scheduler as well.

The ram weight multiplier. A negative value indicates stacking as opposed to spreading:

ram_weight_multiplier=1.0

Virtual disk to physical disk allocation ratio:

disk_allocation_ratio=1.0

Virtual ram to physical ram allocation ratio:

ram_allocation_ratio=1.5