[Haizea] RFC: Adding pluggable policies in Haizea

[Borja Sotomayor]

Hi all,

Haizea TP1.3 was recently released, and this will be the last release
before TP2.0, which will involve a substantial redesign of Haizea's
scheduling code. The main new feature that will be added in TP2.0 will
be a policy module that allows users to plug in their own scheduling
policies. Since several people have expressed interest in this feature,
the purpose of this Request For Comments is to open up discussion on the 
new policy module in case users have requirements we haven't considered.

Below I provide my thoughts on what the policy module should provide.
Please feel free to reply to this thread with any thoughts, suggestions,
feature requests, etc. you may have. We will also be tracking progress
of this feature in the following ticket:

https://phoenixforge.cs.uchicago.edu/haizea/ticket/1


SUPPORTING PLUGGABLE POLICIES IN HAIZEA
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Haizea currently has three hard-coded policies that are relevant to how 
leases are scheduled:

P1 - Lease admission: Haizea accepts all lease requests, assuming enough 
resources are available. In other words, best-effort (BE) leases are 
never rejected (they're just placed on a queue), advance reservations 
(AR) and immediate leases (IM) are only rejected if there is contention 
with a previously requested AR or IM lease (there is no notion of 
rejecting an incoming lease based on who requested it, user quotas, 
number of leases already scheduled, etc.)

P2 - Node selection: When physical hosts have to be selected for a 
lease's VMs, a hardcoded selection algorithm is used (see 
VMScheduler.__choose_nodes in haizea.resourcemanager.scheduler).

P3 - Preemption: When deciding whether to preempt another lease and, 
given a choice, which one to preempt, Haizea simply assumes that BE 
leases are preemptable and cannot preempt other leases, while AR and IM 
leases are not preemptable and can preempt other leases. Furthermore, if 
preemption is unavoidable, Haizea will preempt the most recently 
submitted leases.

Modifying any of these policies would require making changes in Haizea's 
code, meaning that anyone who wants to try out a new policy would have 
to branch off his/her own version of Haizea (or we would need to include 
a massive switch/case statement with all the different policies, which 
still doesn't make it easy to experiment with arbitrary policies).

So, we propose adding a Policy Module to Haizea that allows developers 
to write their own policies and plug them into Haizea (without modifying 
Haizea's code). For example, let's say a developer wants to experiment 
with a new trivial policy for P1 that rejects any lease with an 
odd-numbered ID. That developer should be able to write something like this:

class MyPolicy(LeaseAdmissionPolicy)
	def admit(lease):
		if lease.id % 2 == 1:
			return False
		else:
			return True

And simply instruct Haizea (via the configuration file) that this policy 
should be used for lease admission. Even if Haizea is updated (and 
assuming no changes in the policy API), the developer can continue to 
use this policy (instead of having to dig through Haizea's code to find 
where to paste his lease admission code)

So, to be a bit more specific, the functionality provided by the policy 
module should be the following:

- A "pluggable policy" would be a Python class (like MyPolicy above) 
that extends from an Haizea class (like LeaseAdmissionPolicy above). 
Writing a new policy would involve writing a set of functions with 
well-specified arguments and return values (like "admit" above).

- A developer must be able to specify pluggable policies for P1, P2, and 
P3. I think that P2 and P3 may have to be merged somehow, since there 
can be a lot of feedback between them (e.g., you may choose certain 
physical nodes specifically to avoid preemption). We may also want to 
support policies for assigning priorities to best-effort leases.

- P1 policies would return whether a lease is admitted or not. P2 and P3 
policies would assign a score to physical hosts (higher score means it 
is more desirable to schedule a VM there) and leases (higher score means 
the lease is a better candidate for preemption).

- Specifying what policy to use should be as simple as adding the 
following to the config file:

[policies]
admission: mypackage.policies.MyAdmissionPolicy
host-select: mypackage.policies.MyHostSelectionPolicy
preemption: mypackage.policies.MyPreemptionPolicy

(the pluggable policies would have to be in PYTHONPATH)

As a refinement of the above, we can also provide a way to assign 
weights to policies so that developers can mix different policies. For 
example:

[policies]
admission: 0.8*MyAdmissionPolicy + 0.2*DefaultHaizeaAdmissionPolicy

In this case, and assuming that each policy returns a 1 or a 0, a 
threshold value would have to be defined too (e.g., only leases that 
score more that 0.7 will be admitted).

- A pluggable policy will have read-only access to all of Haizea's 
internal state (lease tables, slot table, queue, etc.) to aid in its 
decisions.


Please feel free to pitch in with thoughts, suggestions, feature 
requests, etc. I would also be interested in knowing if the above would 
meet the requirements of anyone who is interested in writing arbitrary 
policies for Haizea.

Cheers!
-- 
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::
Borja Sotomayor, University of Chicago
  Ph.D. Candidate, Department of Computer Science
  Ryerson 257-C, 1100 East 58th Street, Chicago, IL
  http://people.cs.uchicago.edu/~borja/
Haizea: http://haizea.cs.uchicago.edu/
·····························································
          "Dis maschine vill run und run!"
                -- Kurt Gödel (on the Turing Machine)
:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::