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.


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 
- The quite rough implementation of converting Datalog to LP can be found in 

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.


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 
 starts with the following policy.

warning(id) :-
    nova:host(id, zone, memory_capacity),
    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)
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.


OpenStack Development Mailing List (not for usage questions)
Unsubscribe: openstack-dev-requ...@lists.openstack.org?subject:unsubscribe

Reply via email to