Open Stack

Hi all,

I've been making steady progress on the pieces of the delegation PoC that I volunteered for.  Here's the usual design doc for reference.

https://docs.google.com/document/d/1ksDilJYXV-5AXWON8PLMedDKr9NpS8VbT0jIy_MIEtI/edit#

My main tasks were to spearhead the creation of a skeleton for this work and to work on the conversion of Datalog to LP.
- The skeleton has already been merged; you can find it in congress/policy_engines/vm_placement.py.
- The quite rough implementation of converting Datalog to LP can be found in review.

This note aims to give some details of the Datalog-to-LP conversion code so that others working on the PoC have the context for working on their pieces.  Here are the relevant patches.

https://review.openstack.org/#/c/155537/
https://review.openstack.org/#/c/157612/
https://review.openstack.org/#/c/170311/

The toplevel routine for converting Datalog to LP is vm_placement.py:ComputePlacementEngine.policy_to_lp().  It returns two things: a formula to optimize and a list of constraints that must be satisfied.

For example, the test in congress/tests/policy_engines/test_vmplacement.py:TestPolicyToLp.test_policy_to_lp starts with the following policy.

warning(id) :-
    nova:host(id, zone, memory_capacity),
    legacy:special_zone(zone),
    ceilometer:mem_consumption(id, avg),
    mul(0.75, memory_capacity, three_quarters_mem),
    lt(avg, three_quarters_mem)

and the following data

nova:host(123, 1, 10)
nova:host(456, 1, 10)
nova:server(789, "alice", 123)
nova:server(101, "bob", 123)
legacy:special_zone(1)
ceilometer:mem_consumption(123, 15)
ceilometer:mem_consumption(456, 20)

The call to policy_to_lp() returns (1) the optimization criteria, which aims to minimize the numer of warnings and (2) the set of hard constraints that must be satisfied.  The code returns the following.  (The syntax needs to be changed so that the VM placement engine utilizes the LP solver interface that we decide on.  So the main thing to take away from what follows is just seeing that we can take Datalog as input and output what is conceptually an LP program.)

1. the optimization criteria: (u'warning', 456) + (u'warning', 123)

Here the term (u'warning, 456) is an LP variable that is defined to be true exactly when warning(456) is true in the policy.  And we're using + in the usual LP way, meaning that we want to minimize the sum of those variables.  (These are the Yi in the google doc.)

2. the hard constraints:

First we're defining the (u'warning, 456) LP decision variables to be true exactly when warning(456) is true in the policy: when the host's memory usage is less than 75% of its capacity.

(u'warning', 456) = (u'lt', u'memUsage[456]', 7.5)
(u'warning', 123) = (u'lt', u'memUsage[123]', 7.5)

In this case (u'lt', u'memUsage[456]', 7.5) is equivalent to memUsage[456] < 7.5, where memUsage[456] is an LP decision variable.  (Just noticed that I'm using 2 different syntaxes to represent LP decision variables, but that's not a huge deal since the syntax is just a placeholder anyway.)

Second we're codifying the relationship between memory usage for guests and memory usage for hosts and the assignment of guests to hosts.  These are the domain specific axioms we discussed.

('hMemUse', 456) = ('assign', 789, 456) * ('gMemUse', 789) + ('assign', 101, 456) * ('gMemUse', 101)
('hMemUse', 123) = ('assign', 789, 123) * ('gMemUse', 789) + ('assign', 101, 123) * ('gMemUse', 101)

Here ('assign', 789, 456) is the LP decision variable that says guest 789 is assigned host 456.
('gMemUse', 789) is the memory usage of guest 789.

(I'm sure we're missing some hard constraints, but I think we've got the hardest ones worked out.)

I'm on vacation all week and will be back at work next Tuesday.  I'll try to check email, but I won't be checking into any code/bugs in depth.  I just wanted to let everyone know what I've been up to so I'm not holding anyone up working on their piece of the PoC.

Tim?


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openstack.org/pipermail/openstack-dev/attachments/20150408/b8bd4c30/attachment.html>