Class GreedyMapper

source code

Haizea's default greedy mapper

Haizea uses a greedy algorithm to determine how VMs are mapped to physical resources at a specific point in time (determining that point in time, when using best-effort scheduling, is determined in the lease and VM scheduling classes).

The way the algorithm works is by, first, greedily ordering the physical nodes from "most desirable" to "least desirable". For example, a physical node with no leases scheduled on it in the future is preferable to one with leases (since this reduces the probability of having to preempt leases to obtain a mapping). This ordering, however, is done by the policy engine (see the GreedyPolicy class in the host_selection module) so, to be a truly greedy algorithm, this mapper must be used in conjunction with the "greedy" host selection policy).

Then, the algorithm traverses the list of nodes and tries to map as many lease nodes into each physical node before moving on to the next. If the list of physical nodes is exhausted without finding a mapping for all the lease nodes, then the algorithm tries to find a mapping by preempting other leases.

Before doing this, the mapper must first determine what leases could be preempted. This decision is delegated to the policy engine, which returns a list of leases ordered from "most preemptable" to "least preemptable". The mapper attempts a mapping assuming that the first lease is going to be preempted, then assuming the first and the second, etc.

If no mapping is found with preemption, then there is no mapping at the requested time.