Merge lp:~justin-fathomdb/nova/constraint-scheduler into lp:~hudson-openstack/nova/trunk

[justinsb]

Implementation of constraint-based scheduler.
Created a simple contraint solver and a scheduler that uses it; created constraints that mirrored the existing selection criteria; refactored DB access code to avoid duplication and support future constraints (Working towards 'proximity' allocation or 'specific zone' allocation)

[Soren Hansen (soren)]

I question the usefulness of best-match algorithms. I don't believe that the best match is really interesting at all. Finding best matches typically involves (and indeed that seems to be what happens in this implementation) looking at the entire set of candidates and ordering them according to some criteria. I don't believe this approach scales, and I don't believe it's necessary. It's not unlikely that the top XX% are all just fine candidates, so finding the very best offers no real advantage. Furthermore, the host that is the best match right now might be significantly worse two minutes from now.

[Sandy Walsh (sandy-walsh)]

Justin, nice work on a very interesting branch.

We're currently working on a similar approach in our Zones and Distributed Scheduler blueprints.

https://blueprints.launchpad.net/nova/+spec/multi-cluster-in-a-region
https://blueprints.launchpad.net/nova/+spec/bexar-distributed-scheduler

Ed Leafe (dabo) is working on a similar body of work to this, based on the current Rackspace/Slicehost implementation of Server Best Match.

Soren has a point that the search doesn't have to be exhaustive. We recently changed our approach from server-side to nearly fully db-side and saw massive performance improvements. Also, limiting the result set to XX% as Soren mentioned was possible once the problem was pushed off.

I think we need to review your branch in some depth before giving a pass/fail. I've sure there are things we can leverage to bring it in line with Distributed Scheduler.

Cheers! ... and stay tuned.

[justinsb (justin-fathomdb)]

Soren: It's true that an exhaustive search can be expensive, which is why I
didn't code an exhaustive search (other than in the unit tests) :-) There's
a framework for 'Criteria', which the 'Solver' tries to solve as best it
can. You can plug in whatever Solver technique you think best (which might
actually be exhaustive for small sets), but I believe the Solver I've got
here is likely to be reasonable in practice. The approach is that it
identifies the 'most selective criteria' and then steps through those
results in order to find one where all the other criteria are no-more
unhappy (mini-max). I'll document the magic better! I haven't coded
heuristic algorithms yet because - frankly - we're nowhere near the scales
where it becomes necessary and we have no way to take advantage of
heuristics when we're sourcing data from a relational DB, and because there
are difficult questions around behavior when the heuristics fail to find a
good solution or any solution at all.

Sandy: I think the work is non-overlapping with the distributed & multi
schedulers, but I'll check them out in more detail. My goal is to support
more constraints in the scheduler (in particular, co-placement of volumes
and servers), and I'm going to work on this constraint to help motivate this
patch.

I'm going to check out the other branches, and code up a co-placement
Criteria so this isn't just work in the abstract!

[justinsb (justin-fathomdb)]

I've got a branch up which makes use of the constraint scheduler:
lp:~justin-fathomdb/nova/schedule-compute-near-volume

It's now super-easy to add constraints, even conflicting constraints, and (hopefully) this will still yield reasonable decisions.

As the number of constraints grows, I don't believe that trying to satisfy the constraints manually will scale.

The dependent branch isn't yet ready for merge (I doubt it actually works); I need to write tests for it and that is at the end of a really long chain of merge requests!!

[Nachi Ueno (nati-ueno)]

As you pointed, I suppose your code needs more test code before merged.
In addtion unit tests for ConstraintLib fail.

======================================================================
ERROR: test_big (nova.tests.test_constraintlib.ConstraintLibTestCase)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/nati/workspace/constraint-scheduler/nova/tests/test_constraintlib.py", line 106, in test_big
    self._do_random_test(rnd, item_count, constraints_count)
  File "/home/nati/workspace/constraint-scheduler/nova/tests/test_constraintlib.py", line 122, in _do_random_test
    solver = constraint_lib.Solver(None, None)
TypeError: __init__() takes exactly 2 arguments (3 given)

======================================================================
ERROR: test_five_five__five (nova.tests.test_constraintlib.ConstraintLibTestCase)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "/home/nati/workspace/constraint-scheduler/nova/tests/test_constraintlib.py", line 97, in test_five_five__five
    self._do_random_test(rnd, 5, 5)
  File "/home/nati/workspace/constraint-scheduler/nova/tests/test_constraintlib.py", line 122, in _do_random_test
    solver = constraint_lib.Solver(None, None)
TypeError: __init__() takes exactly 2 arguments (3 given)

review: Needs Fixing

[justinsb (justin-fathomdb)]

Fixed up the unit tests (I was working in a derived branch and tried to keep this one up to date - probably more trouble than it's worth with bazaar)

This branch has good test coverage; and the dependent one now does also.

[Nachi Ueno (nati-ueno)]

Thank you for your fix.
Would you add more test case for ConstraintDriverTestCase?

[justinsb (justin-fathomdb)]

It's easy to miss, but the ConstraintDriverTestCase derives from
_SchedulerBaseTestCase, so inherits basically the same code coverage as the
SimpleScheduler (although the SimpleScheduler supports some 'directed
placement' in a bit of a hacky way, which I don't support in the
ConstraintScheduler) But the ConstraintScheduler (which is never used
unless someone specifically requests it) behaves the same way as the
SimpleScheduler under the basic tests.

In addition, there are unit tests for the constraint solving library.

I believe that's reasonable test coverage. There can always be more tests,
but I think this is a reasonable start for something that is only
user-selectable. As we add use-cases, I'm sure we'll find issues and add
tests, both for bugs, and places where extra behaviour is needed. I did
find a bug when developing the derived directed-location branch, and I
back-ported that fix (which is how I broke the unit tests in the first
place!) That bug was when the min-scores were tied, it didn't fall-back to
consider the secondary criteria. The constraint solving library tests
didn't hit this because they were using randomized data, so were very
unlikely to get ties.

Is that OK?

[Nachi Ueno (nati-ueno)]

I'm sorry for late reply, because of earthquake in Japan.
As you said, it is hard to write sufficient test code.
However, is it possible to add Schedure test code which corresponds to constraint solving library tests? Test code can be used a document, so it shows how to use the Constraint Schedure.

> It's easy to miss, but the ConstraintDriverTestCase derives from
> _SchedulerBaseTestCase, so inherits basically the same code coverage as the
> SimpleScheduler (although the SimpleScheduler supports some 'directed
> placement' in a bit of a hacky way, which I don't support in the
> ConstraintScheduler) But the ConstraintScheduler (which is never used
> unless someone specifically requests it) behaves the same way as the
> SimpleScheduler under the basic tests.
>
> In addition, there are unit tests for the constraint solving library.
>
> I believe that's reasonable test coverage. There can always be more tests,
> but I think this is a reasonable start for something that is only
> user-selectable. As we add use-cases, I'm sure we'll find issues and add
> tests, both for bugs, and places where extra behaviour is needed. I did
> find a bug when developing the derived directed-location branch, and I
> back-ported that fix (which is how I broke the unit tests in the first
> place!) That bug was when the min-scores were tied, it didn't fall-back to
> consider the secondary criteria. The constraint solving library tests
> didn't hit this because they were using randomized data, so were very
> unlikely to get ties.
>
> Is that OK?

[justinsb (justin-fathomdb)]

Nachi: There are tests already for the constraint scheduler, but the only constraints implemented in this branch are ones that assign to the least-loaded machine. If you look in the derived branch, there are examples of more advanced constraints and better tests

In the derived branch, I add a constraint that favors putting a compute node as close as possible to a specified location, based on a topology:
https://code.launchpad.net/~justin-fathomdb/nova/schedule-compute-near-volume/+merge/52520

[justinsb (justin-fathomdb)]

Moving to WIP - we're going to discuss at Design Summit

Unmerged revisions

725. By justinsb on 2011-03-10

Back-ported fixes from derived branch

724. By justinsb on 2011-03-02

Added (derived) unit test for constraint scheduler

723. By justinsb on 2011-03-02

Fixed pep8, missing copyrights

722. By justinsb on 2011-03-02

Use datastore in simple scheduler for retrieval in non-forced case

721. By justinsb on 2011-03-02

Remove DB update code from schedulers; they deal with the datastore now

720. By justinsb on 2011-03-02

Refactoring data store so that we're not using DB objects
(Different constraints will likely need different queries, and the DB binding will be problematic)

719. By justinsb on 2011-03-02

Optimization for when we know we're not the worst constraint

718. By justinsb on 2011-03-02

Small cleanup of tests & pep8

717. By justinsb on 2011-03-02

Fix logical error, use a priority queue in the constraint solver

716. By justinsb on 2011-03-01

A few fixes (passes most simple scheduler tests)

=== added file 'nova/scheduler/constraint.py'
--- nova/scheduler/constraint.py	1970-01-01 00:00:00 +0000
+++ nova/scheduler/constraint.py	2011-03-10 20:18:18 +0000
@@ -0,0 +1,226 @@
+# vim: tabstop=4 shiftwidth=4 softtabstop=4
+
+# Copyright (c) 2011 Justin Santa Barbara
+#
+# All Rights Reserved.
+#
+#    Licensed under the Apache License, Version 2.0 (the "License"); you may
+#    not use this file except in compliance with the License. You may obtain
+#    a copy of the License at
+#
+#         http://www.apache.org/licenses/LICENSE-2.0
+#
+#    Unless required by applicable law or agreed to in writing, software
+#    distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+#    WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+#    License for the specific language governing permissions and limitations
+#    under the License.
+
+"""
+Constraint-Based Scheduler
+"""
+
+from nova import db
+from nova import flags
+from nova import log as logging
+from nova.scheduler import driver
+from nova.scheduler import constraint_lib
+
+
+LOG = logging.getLogger('nova.scheduler.constraint')
+FLAGS = flags.FLAGS
+
+
+class SchedulerConstraint(constraint_lib.Constraint):
+    def request(self):
+        return self.solver.context['request']
+
+    def request_context(self):
+        return self.solver.context['request_context']
+
+    def scheduler(self):
+        return self.solver.context['scheduler']
+
+    def datastore(self):
+        return self.scheduler().datastore()
+
+    def selectivity(self):
+        # We default to an intermediate value here
+        return 0.75
+
+    def __str__(self):
+        return self.__class__.__name__
+
+    def __repr__(self):
+        return self.__str__()
+
+
+class InstanceConstraintFavorLeastLoaded(SchedulerConstraint):
+    def __init__(self):
+        super(InstanceConstraintFavorLeastLoaded, self).__init__()
+        self.db_results = None
+
+    def _get_database_items(self):
+        if not self.db_results:
+            self.trace(_("get_instance_hosts_sorted"))
+            results = self.datastore().get_instance_hosts_sorted(
+                                                    self.request_context())
+
+            for result in results:
+                self.cache_item(result)
+
+            self.db_results = results
+
+        return self.db_results
+
+    def score_item(self, candidate):
+        score = candidate.utilization_score()
+        self.trace_score(candidate, score)
+        return score
+
+    def get_candidate_iterator(self):
+        """Returns an iterator over all items in best-to-least-good order"""
+        requested_vcpus = self.request()['vcpus']
+
+        for host in self._get_database_items():
+            if host.used + requested_vcpus <= host.capacity:
+                score = self.score_item(host)
+                yield constraint_lib.Candidate(host.id, score)
+            else:
+                self.trace(_("skip %s: capacity") % host)
+
+
+class VolumeConstraintFavorLeastGigabytes(SchedulerConstraint):
+    def __init__(self):
+        super(VolumeConstraintFavorLeastGigabytes, self).__init__()
+        self.db_results = None
+
+    def _get_database_items(self):
+        if not self.db_results:
+            self.trace(_("get_volume_hosts_sorted"))
+            results = self.datastore().get_volume_hosts_sorted(
+                                                    self.request_context())
+
+            for result in results:
+                self.cache_item(result)
+
+            self.db_results = results
+
+        return self.db_results
+
+    def score_item(self, candidate):
+        score = candidate.utilization_score()
+        self.trace_score(candidate, score)
+        return score
+
+    def get_candidate_iterator(self):
+        """Returns an iterator over all items in best-to-least-good order"""
+        requested_size = self.request()['size']
+
+        for host in self._get_database_items():
+            if host.used + requested_size <= host.capacity:
+                score = self.score_item(host)
+                yield constraint_lib.Candidate(host.id, score)
+            else:
+                self.trace(_("skip %s: capacity") % host)
+
+
+class NetworkConstraintFavorLeastNetworks(SchedulerConstraint):
+    def __init__(self):
+        super(NetworkConstraintFavorLeastNetworks, self).__init__()
+        self.db_results = None
+
+    def _get_database_items(self):
+        if not self.db_results:
+            self.trace(_("get_network_hosts_sorted"))
+            results = self.datastore().get_network_hosts_sorted(
+                                                    self.request_context())
+
+            for result in results:
+                self.cache_item(result)
+
+            self.db_results = results
+
+        return self.db_results
+
+    def score_item(self, candidate):
+        score = candidate.utilization_score()
+        self.trace_score(candidate, score)
+        return score
+
+    def get_candidate_iterator(self):
+        """Returns an iterator over all items in best-to-least-good order"""
+        requested_count = 1
+
+        for host in self._get_database_items():
+            if host.used_networks + requested_count <= host.capacity_networks:
+                score = self.score_item(host)
+                yield constraint_lib.Candidate(host.id, score)
+            else:
+                self.trace(_("skip %s: capacity") % host)
+
+
+class ConstraintScheduler(driver.Scheduler):
+    """Implements constraint-based scheduler"""
+    def __init__(self):
+        super(ConstraintScheduler, self).__init__()
+
+    def schedule(self, context, topic, *_args, **_kwargs):
+        raise NotImplementedError(_("Must implement a %s scheduler") % topic)
+
+    def schedule_run_instance(self, request_context, instance_id,
+                              *_args, **_kwargs):
+        """Picks a host that is up and has the fewest running instances."""
+        instance_ref = db.instance_get(request_context, instance_id)
+
+        solver = constraint_lib.Solver({'request_context': request_context,
+                                        'request': instance_ref,
+                                        'scheduler': self})
+        solver.add_constraint(InstanceConstraintFavorLeastLoaded())
+
+        for service in solver.get_solutions_iterator():
+            if self.service_is_up(service.model):
+                host = service.model['host']
+                self.datastore().record_instance_scheduled(request_context,
+                                                           instance_id,
+                                                           host)
+                return host
+
+        raise driver.NoValidHost(_("No suitable hosts found"))
+
+    def schedule_create_volume(self, request_context, volume_id,
+                               *_args, **_kwargs):
+        """Picks a host that is up and has the fewest volumes."""
+        volume_ref = db.volume_get(request_context, volume_id)
+
+        solver = constraint_lib.Solver({'request_context': request_context,
+                                        'request': volume_ref,
+                                        'scheduler': self})
+        solver.add_constraint(VolumeConstraintFavorLeastGigabytes())
+
+        for service in solver.get_solutions_iterator():
+            if self.service_is_up(service.model):
+                host = service.model['host']
+                self.datastore().record_volume_scheduled(request_context,
+                                                         volume_id,
+                                                         host)
+                return host
+
+        raise driver.NoValidHost(_("No suitable hosts found"))
+
+    def schedule_set_network_host(self, request_context, *_args, **_kwargs):
+        """Picks a host that is up and has the fewest networks."""
+
+        solver = constraint_lib.Solver({'request_context': request_context,
+                                        'request': {},
+                                        'scheduler': self})
+        solver.add_constraint(NetworkConstraintFavorLeastNetworks())
+
+        for service in solver.get_solutions_iterator():
+            if self.service_is_up(service.model):
+                host = service.model['host']
+                self.datastore().record_network_scheduled(request_context,
+                                                          host)
+                return host
+
+        raise driver.NoValidHost(_("No suitable hosts found"))
 
=== added file 'nova/scheduler/constraint_lib.py'
--- nova/scheduler/constraint_lib.py	1970-01-01 00:00:00 +0000
+++ nova/scheduler/constraint_lib.py	2011-03-10 20:18:18 +0000
@@ -0,0 +1,254 @@
+# vim: tabstop=4 shiftwidth=4 softtabstop=4
+
+# Copyright (c) 2011 Justin Santa Barbara
+# All Rights Reserved.
+#
+#    Licensed under the Apache License, Version 2.0 (the "License"); you may
+#    not use this file except in compliance with the License. You may obtain
+#    a copy of the License at
+#
+#         http://www.apache.org/licenses/LICENSE-2.0
+#
+#    Unless required by applicable law or agreed to in writing, software
+#    distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+#    WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+#    License for the specific language governing permissions and limitations
+#    under the License.
+
+"""
+Simple Constraint Solver Library
+"""
+
+import heapq
+
+from nova import flags
+from nova import log as logging
+
+
+LOG = logging.getLogger('nova.scheduler.constraint')
+FLAGS = flags.FLAGS
+
+
+class Candidate(object):
+    def __init__(self, id, score):
+        self.id = id
+        self.score = score
+
+    def __str__(self):
+        return "%s:%s" % (self.id, self.score)
+
+
+class Constraint(object):
+    def __init__(self):
+        self.solver = None
+
+    def __str__(self):
+        return "%s" % self.__class__.__name__
+
+    def score_item(self, candidate):
+        """Scores the 'goodness' of a candidate.
+
+        For acceptable values, the score must be > 0 and <= 1.
+        If score <= 0, then the decision is unacceptable"""
+        raise NotImplementedError("Must implement score_item")
+
+    def get_candidate_iterator(self):
+        """Returns an iterator over all items in best-to-least-good order"""
+        raise NotImplementedError("Must implement get_candidate_iterator")
+
+    def selectivity(self):
+        """Returns the selectivity of the constraint in (0,1]
+
+        A smaller value means the constraint is likely to match fewer results.
+        If the criteria only matches half the items, use 0.5.
+        If it only matches one in 10, use 0.1 etc"""
+        raise NotImplementedError("Must implement selectivity")
+
+    def can_beat_score(self, score):
+        """Checks if we know that we can match/beat the specified score.
+
+        This is an optimization; a typical implementation will check the items
+        in the context and check if at least one of them has a score that is
+        >= the passed score. If so, we're not going to be the worst criteria,
+        so we don't need to get the list of values. See the implementation of
+        the Solver for the details of why!
+        """
+        for item in self.solver.all_cached_items():
+            if self.score_item(item) > score:
+                return True
+        return False
+
+    def set_solver(self, solver):
+        if self.solver:
+            raise Exception("Tried to double-set solver")
+        self.solver = solver
+
+    def trace(self, message):
+        self.solver.trace(message)
+
+    def trace_score(self, candidate, score):
+        self.trace("%s scored %s => %s" % (self, candidate, score))
+
+    def cache_item(self, item):
+        item_id = item.id
+        self.solver.cache_item(item, item_id)
+
+
+def get_selectivity(constraint):
+    return constraint.selectivity()
+
+
+class ConstraintIteratorState(object):
+    """Holds the state of iteration over the candidates for a constraint"""
+    def __init__(self, constraint, query_values=True):
+        self.constraint = constraint
+
+        self.is_done = False
+        self.current = None
+
+        if query_values:
+            self.iterator = constraint.get_candidate_iterator()
+            self.advance()
+        else:
+            self.iterator = None
+
+    def advance(self):
+        next_item = next(self.iterator, None)
+        if next_item:
+            self.current = next_item
+        else:
+            self.current = None
+            self.is_done = True
+
+    def __str__(self):
+        return "%s %s" % (self.constraint, self.current)
+
+
+class Solver(object):
+    """Finds the minimax solution to the constraints
+
+    Formally, we're looking for max(min(score(candidate, constraint))
+    where max is over all candidates
+    and min is over all constraints.
+
+    NOTE(justinsb): Anyone know how to get TeX into here? :-)"""
+
+    def __init__(self, context):
+        self.cached_items = {}
+        self.context = context
+        self.constraints = []
+
+    def add_constraint(self, constraint):
+        self.constraints.append(constraint)
+        constraint.set_solver(self)
+
+    def lookup_item(self, item_id):
+        item = self.cached_items.get(item_id)
+        if not item:
+            # This shouldn't be possible
+            raise Exception(_("Item not in cache: %s") % item_id)
+            #            if self.lookup_function:
+            #            self.trace(_("lookup on %s") % (item_id))
+            #            item = self.lookup_function(item_id)
+            #            self.cache(item, item_id)
+            #            else:
+            #                raise Error()
+        return item
+
+    def cache_item(self, item, item_id):
+        self.cached_items[item_id] = item
+
+    def all_cached_items(self):
+        return self.cached_items.values()
+
+    def trace(self, message):
+        """Records diagnostic information on scheduling decisions.
+
+        Constraint scheduling is not exactly simple. We may in future want to
+        provide (admin) API calls that expose the scheduling reasoning
+        """
+        LOG.debug(message)
+
+    def get_solutions_iterator(self):
+        if not self.constraints:
+            raise Exception("No constraints provided")
+
+        queue = []
+
+        # We sort so that the most selective criteria is done first
+        # This then lets less selective criteria inspect the candidates that
+        #  the more selective candidates have chosen first.
+        # This is just a (potential) optimization
+        constraints = sorted(self.constraints, key=get_selectivity)
+
+        # Find the criteria which is the lowest scoring (worst)
+        # Observe that the worst doesn't actually change... the score must get
+        #  lower as we iterate through
+        worst = None
+        states = []
+        for constraint in constraints:
+            query_values = True
+
+            if worst and constraint.can_beat_score(worst.current.score):
+                # This is a sneaky optimization. If we know we're not going
+                #  to be the worst, we don't need to query (see code below)
+                # If we'd be querying a REST service or DB, this is important
+                self.trace(_("Won't query constraint - not the worst: %s") %
+                           (constraint))
+                query_values = False
+
+            state = ConstraintIteratorState(constraint,
+                                            query_values=query_values)
+            states.append(state)
+
+            if query_values:
+                if not worst or worst.current.score > state.current.score:
+                    worst = state
+
+        self.trace(_("Using lowest-scoring criteria: %s") %
+                   (worst.constraint))
+
+        while not worst.is_done:
+            self.trace(_("Candidate: %s") % (worst))
+
+            # Loop over other constraints to get the score for the candidate
+            # We break ties by choosing the candidate with the sum of scores
+            min_score = worst.current.score
+            tie_break_score = 0
+
+            item_id = worst.current.id
+            item = self.lookup_item(item_id)
+            for constraint_state in states:
+                score = constraint_state.constraint.score_item(item)
+                min_score = min(min_score, score)
+                tie_break_score += score
+
+            # Heapify is really nice and will look at tie_break_score
+            #  if min_score is the same
+            heapq.heappush(queue, (-min_score, -tie_break_score, item))
+
+            # Every future item will have a score <= worst.current.score
+            while True:
+                (head_score, tie_break_score, head_item) = queue[0]
+                head_score = -head_score
+                #tie_break_score = -tie_break_score
+                if head_score <= worst.current.score:
+                    break
+
+                heapq.heappop(queue)
+                self.trace(_("Yielding: %s") % (head_item))
+                yield head_item
+
+            # Advance the iterator
+            worst.advance()
+            if not worst.is_done:
+                self.trace(_("Advanced: %s") % (worst))
+
+        self.trace(_("Reached end of: %s") % (worst.constraint))
+
+        while queue:
+            (head_score, tie_break_score, head_item) = heapq.heappop(queue)
+            #head_score = -head_score
+            #tie_break_score = -tie_break_score
+            self.trace(_("Yielding: %s") % (head_item))
+            yield head_item
 
=== added file 'nova/scheduler/datastore.py'
--- nova/scheduler/datastore.py	1970-01-01 00:00:00 +0000
+++ nova/scheduler/datastore.py	2011-03-10 20:18:18 +0000
@@ -0,0 +1,148 @@
+# vim: tabstop=4 shiftwidth=4 softtabstop=4
+
+# Copyright (c) 2011 Justin Santa Barbara
+#
+# All Rights Reserved.
+#
+#    Licensed under the Apache License, Version 2.0 (the "License"); you may
+#    not use this file except in compliance with the License. You may obtain
+#    a copy of the License at
+#
+#         http://www.apache.org/licenses/LICENSE-2.0
+#
+#    Unless required by applicable law or agreed to in writing, software
+#    distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+#    WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+#    License for the specific language governing permissions and limitations
+#    under the License.
+
+"""
+DataStore for the scheduler.
+
+Currently backed by the DB.
+"""
+import datetime
+
+from nova import db
+from nova import flags
+from nova import log as logging
+
+
+LOG = logging.getLogger('nova.scheduler.datastore')
+FLAGS = flags.FLAGS
+
+
+class SchedulerAbstractHostModel(object):
+    def __init__(self, id, model, used, capacity):
+        self.id = id
+        self.model = model
+        self.used = used
+        self.capacity = capacity
+
+    def to_s(self):
+        return '%s %s/%s' % (self.id, self.used, self.capacity)
+
+    def utilization_score(self):
+        # The best machine is one that is unused
+        utilization = float(self.used) / float(self.capacity)
+        if utilization > 1:
+            utilization = 1
+        score = 1 - utilization
+        return score
+
+
+class SchedulerInstanceHostModel(SchedulerAbstractHostModel):
+    def __init__(self, id, model, used_cores, capacity_cores):
+        super(SchedulerInstanceHostModel, self).__init__(id, model,
+                                                         used_cores,
+                                                         capacity_cores)
+
+
+class SchedulerVolumeHostModel(SchedulerAbstractHostModel):
+    def __init__(self, id, model, used_gigabytes, capacity_gigabytes):
+        super(SchedulerVolumeHostModel, self).__init__(id, model,
+                                                       used_gigabytes,
+                                                       capacity_gigabytes)
+
+
+class SchedulerNetworkHostModel(SchedulerAbstractHostModel):
+    def __init__(self, id, model, used_networks, capacity_networks):
+        super(SchedulerNetworkHostModel, self).__init__(id, model,
+                                                        used_networks,
+                                                        capacity_networks)
+
+
+class SchedulerDataStore(object):
+    def get_instance_hosts_sorted(self, context):
+        results = []
+        db_results = db.service_get_all_compute_sorted(context)
+        for db_result in db_results:
+            (model, used_cores) = db_result
+            id = model['id']
+
+            # TODO(justinsb): We need a way to know the true capacity
+            capacity_cores = FLAGS.max_cores
+
+            item = SchedulerInstanceHostModel(id,
+                                              model,
+                                              used_cores,
+                                              capacity_cores)
+            results.append(item)
+        # NOTE(justinsb): This is only sorted by score because max is fixed
+        return results
+
+    def service_get_all_by_topic(self, context, topic):
+        return db.service_get_all_by_topic(context, topic)
+
+    def get_volume_hosts_sorted(self, context):
+        results = []
+        db_results = db.service_get_all_volume_sorted(context)
+        for db_result in db_results:
+            (model, used_gigabytes) = db_result
+            id = model['id']
+
+            # TODO(justinsb): We need a way to know the true capacity
+            capacity_gigabytes = FLAGS.max_gigabytes
+
+            item = SchedulerVolumeHostModel(id,
+                                            model,
+                                            used_gigabytes,
+                                            capacity_gigabytes)
+            results.append(item)
+        # NOTE(justinsb): This is only sorted by score because max is fixed
+        return results
+
+    def get_network_hosts_sorted(self, context):
+        results = []
+        db_results = db.service_get_all_network_sorted(context)
+        for db_result in db_results:
+            (model, used_networks) = db_result
+            id = model['id']
+
+            # TODO(justinsb): We need a way to know the true capacity
+            capacity_networks = FLAGS.max_networks
+
+            item = SchedulerNetworkHostModel(id,
+                                             model,
+                                             used_networks,
+                                             capacity_networks)
+            results.append(item)
+        # NOTE(justinsb): This is only sorted by score because max is fixed
+        return results
+
+    def record_instance_scheduled(self, context, instance_id, host):
+        now = datetime.datetime.utcnow()
+        db.instance_update(context,
+                           instance_id,
+                           {'host': host,
+                            'scheduled_at': now})
+
+    def record_volume_scheduled(self, context, volume_id, host):
+        now = datetime.datetime.utcnow()
+        db.volume_update(context,
+                         volume_id,
+                         {'host': host,
+                          'scheduled_at': now})
+
+    def record_network_scheduled(self, context, host):
+        pass
 
=== modified file 'nova/scheduler/driver.py'
--- nova/scheduler/driver.py	2011-01-18 19:01:16 +0000
+++ nova/scheduler/driver.py	2011-03-10 20:18:18 +0000
@@ -3,6 +3,7 @@
 # Copyright (c) 2010 Openstack, LLC.
 # Copyright 2010 United States Government as represented by the
 # Administrator of the National Aeronautics and Space Administration.
+# Copyright 2011 Justin Santa Barbara
 # All Rights Reserved.
 #
 #    Licensed under the Apache License, Version 2.0 (the "License"); you may
@@ -23,9 +24,10 @@
 
 import datetime
 
-from nova import db
 from nova import exception
 from nova import flags
+from nova.scheduler import datastore
+
 
 FLAGS = flags.FLAGS
 flags.DEFINE_integer('service_down_time', 60,
@@ -44,6 +46,9 @@
 
 class Scheduler(object):
     """The base class that all Scheduler clases should inherit from."""
+    def __init__(self):
+        super(Scheduler, self).__init__()
+        self._datastore = None
 
     @staticmethod
     def service_is_up(service):
@@ -55,8 +60,7 @@
 
     def hosts_up(self, context, topic):
         """Return the list of hosts that have a running service for topic."""
-
-        services = db.service_get_all_by_topic(context, topic)
+        services = self.datastore().service_get_all_by_topic(context, topic)
         return [service.host
                 for service in services
                 if self.service_is_up(service)]
@@ -64,3 +68,9 @@
     def schedule(self, context, topic, *_args, **_kwargs):
         """Must override at least this method for scheduler to work."""
         raise NotImplementedError(_("Must implement a fallback schedule"))
+
+    def datastore(self):
+        """Returns the associated SchedulerDataStore"""
+        if not self._datastore:
+            self._datastore = datastore.SchedulerDataStore()
+        return self._datastore
 
=== modified file 'nova/scheduler/simple.py'
--- nova/scheduler/simple.py	2011-01-27 22:14:10 +0000
+++ nova/scheduler/simple.py	2011-03-10 20:18:18 +0000
@@ -3,6 +3,7 @@
 # Copyright (c) 2010 Openstack, LLC.
 # Copyright 2010 United States Government as represented by the
 # Administrator of the National Aeronautics and Space Administration.
+# Copyright 2011 Justin Santa Barbara
 # All Rights Reserved.
 #
 #    Licensed under the Apache License, Version 2.0 (the "License"); you may
@@ -21,8 +22,6 @@
 Simple Scheduler
 """
 
-import datetime
-
 from nova import db
 from nova import flags
 from nova.scheduler import driver
@@ -52,25 +51,19 @@
             if not self.service_is_up(service):
                 raise driver.WillNotSchedule(_("Host %s is not alive") % host)
 
-            # TODO(vish): this probably belongs in the manager, if we
-            #             can generalize this somehow
-            now = datetime.datetime.utcnow()
-            db.instance_update(context, instance_id, {'host': host,
-                                                      'scheduled_at': now})
+            self.datastore().record_instance_scheduled(context,
+                                                       instance_id,
+                                                       host)
             return host
-        results = db.service_get_all_compute_sorted(context)
+        results = self.datastore().get_instance_hosts_sorted(context)
         for result in results:
-            (service, instance_cores) = result
-            if instance_cores + instance_ref['vcpus'] > FLAGS.max_cores:
+            service = result.model
+            if result.used + instance_ref['vcpus'] > result.capacity:
                 raise driver.NoValidHost(_("All hosts have too many cores"))
             if self.service_is_up(service):
-                # NOTE(vish): this probably belongs in the manager, if we
-                #             can generalize this somehow
-                now = datetime.datetime.utcnow()
-                db.instance_update(context,
-                                   instance_id,
-                                   {'host': service['host'],
-                                    'scheduled_at': now})
+                self.datastore().record_instance_scheduled(context,
+                                                           instance_id,
+                                                           service['host'])
                 return service['host']
         raise driver.NoValidHost(_("No hosts found"))
 
@@ -86,37 +79,33 @@
             if not self.service_is_up(service):
                 raise driver.WillNotSchedule(_("Host %s not available") % host)
 
-            # TODO(vish): this probably belongs in the manager, if we
-            #             can generalize this somehow
-            now = datetime.datetime.utcnow()
-            db.volume_update(context, volume_id, {'host': host,
-                                                  'scheduled_at': now})
+            self.datastore().record_volume_scheduled(context,
+                                                     volume_id,
+                                                     host)
             return host
-        results = db.service_get_all_volume_sorted(context)
+        results = self.datastore().get_volume_hosts_sorted(context)
         for result in results:
-            (service, volume_gigabytes) = result
-            if volume_gigabytes + volume_ref['size'] > FLAGS.max_gigabytes:
+            service = result.model
+            if result.used + volume_ref['size'] > result.capacity:
                 raise driver.NoValidHost(_("All hosts have too many "
                                            "gigabytes"))
             if self.service_is_up(service):
-                # NOTE(vish): this probably belongs in the manager, if we
-                #             can generalize this somehow
-                now = datetime.datetime.utcnow()
-                db.volume_update(context,
-                                 volume_id,
-                                 {'host': service['host'],
-                                  'scheduled_at': now})
+                self.datastore().record_volume_scheduled(context,
+                                                         volume_id,
+                                                         service['host'])
                 return service['host']
         raise driver.NoValidHost(_("No hosts found"))
 
     def schedule_set_network_host(self, context, *_args, **_kwargs):
         """Picks a host that is up and has the fewest networks."""
 
-        results = db.service_get_all_network_sorted(context)
+        results = self.datastore().get_network_hosts_sorted(context)
         for result in results:
-            (service, instance_count) = result
-            if instance_count >= FLAGS.max_networks:
+            service = result.model
+            if result.used + 1 > result.capacity:
                 raise driver.NoValidHost(_("All hosts have too many networks"))
             if self.service_is_up(service):
+                self.datastore().record_network_scheduled(context,
+                                                          service['host'])
                 return service['host']
         raise driver.NoValidHost(_("No hosts found"))
 
=== modified file 'nova/scheduler/zone.py'
--- nova/scheduler/zone.py	2011-01-11 22:27:36 +0000
+++ nova/scheduler/zone.py	2011-03-10 20:18:18 +0000
@@ -24,7 +24,6 @@
 import random
 
 from nova.scheduler import driver
-from nova import db
 
 
 class ZoneScheduler(driver.Scheduler):
@@ -38,7 +37,7 @@
         if zone is None:
             return self.hosts_up(context, topic)
 
-        services = db.service_get_all_by_topic(context, topic)
+        services = self.datastore().service_get_all_by_topic(context, topic)
         return [service.host
                 for service in services
                 if self.service_is_up(service)
 
=== added file 'nova/tests/test_constraintlib.py'
--- nova/tests/test_constraintlib.py	1970-01-01 00:00:00 +0000
+++ nova/tests/test_constraintlib.py	2011-03-10 20:18:18 +0000
@@ -0,0 +1,170 @@
+# vim: tabstop=4 shiftwidth=4 softtabstop=4
+
+# Copyright 2011 Justin Santa Barbara
+# All Rights Reserved.
+#
+#    Licensed under the Apache License, Version 2.0 (the "License"); you may
+#    not use this file except in compliance with the License. You may obtain
+#    a copy of the License at
+#
+#         http://www.apache.org/licenses/LICENSE-2.0
+#
+#    Unless required by applicable law or agreed to in writing, software
+#    distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
+#    WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
+#    License for the specific language governing permissions and limitations
+#    under the License.
+"""
+Tests For Constraint Library
+"""
+
+import random
+
+from nova import flags
+from nova import log as logging
+from nova import test
+from nova.scheduler import constraint_lib
+
+
+LOG = logging.getLogger('nova.tests.constraintlib')
+
+FLAGS = flags.FLAGS
+FLAGS.verbose = True
+
+
+def brute_compute_score(item, constraints):
+    min_score = None
+    for constraint in constraints:
+        score = constraint.score_item(item)
+        if min_score and min_score <= score:
+            continue
+        min_score = score
+
+    return min_score
+
+
+def brute_force(all_items, constraints):
+    max_min_score = None
+    max_min_item = None
+
+    for item in all_items:
+        min_score = brute_compute_score(item, constraints)
+
+        if max_min_score and max_min_score >= min_score:
+            continue
+
+        max_min_score = min_score
+        max_min_item = item
+
+    return (max_min_item, max_min_score)
+
+
+class ParameterBoundConstraint(constraint_lib.Constraint):
+    def __init__(self, all_items, key, selectivity_value):
+        super(ParameterBoundConstraint, self).__init__()
+        self.all_items = all_items
+        self.key = key
+        self.selectivity_value = selectivity_value
+
+    def to_s(self):
+        return "ParameterBoundConstraint:%s" % self.key
+
+    def score_item(self, candidate):
+        return candidate[self.key]
+
+    def get_candidate_iterator(self):
+        """Returns an iterator over all items in best-to-least-good order"""
+        all_items_ordered = sorted(self.all_items,
+                                   key=self.score_item,
+                                   reverse=True)
+        for item in all_items_ordered:
+            score = self.score_item(item)
+            item_id = item['id']
+            yield constraint_lib.Candidate(item_id, score)
+
+    def selectivity(self):
+        return self.selectivity_value
+
+
+class ConstraintLibTestCase(test.TestCase):
+    """Test case for constraint library"""
+
+    def test_five_five__five(self):
+        rnd = random.Random()
+        rnd.seed(555)
+
+        for _rep in range(5):
+            self._do_random_test(rnd, 5, 5)
+
+    def test_big(self):
+        rnd = random.Random()
+        rnd.seed(1234)
+
+        item_count = 1000
+        constraints_count = 100
+
+        self._do_random_test(rnd, item_count, constraints_count)
+
+    def _test_random_100(self):
+        """This is hidden because it's slow, but it's a nice torture test"""
+        rnd = random.Random()
+        rnd.seed(1234)
+
+        for _rep in range(100):
+            item_count = rnd.randint(100, 1000)
+            constraints_count = rnd.randint(5, 100)
+
+            self._do_random_test(rnd, item_count, constraints_count)
+
+    def _do_random_test(self, rnd, item_count, constraints_count):
+        all_items = []
+
+        context = {}
+        solver = constraint_lib.Solver(context)
+
+        for j in range(item_count):
+            item = {}
+            for i in range(constraints_count):
+                key = 'c%s' % i
+                item[key] = rnd.random()
+            item['id'] = j
+            all_items.append(item)
+            solver.cache_item(item, item['id'])
+
+        constraints = []
+        for i in range(constraints_count):
+            key = 'c%s' % i
+            selectivity_value = rnd.random()
+            constraint = ParameterBoundConstraint(all_items,
+                                                  key,
+                                                  selectivity_value)
+            solver.add_constraint(constraint)
+            constraints.append(constraint)
+
+        solved_item = None
+
+        previous_item = None
+        for item in solver.get_solutions_iterator():
+            if not solved_item:
+                solved_item = item
+            if previous_item:
+                previous_score = brute_compute_score(previous_item,
+                                                     constraints)
+                item_score = brute_compute_score(item, constraints)
+
+                if previous_score < item_score:
+                    LOG.warn("PREVIOUS: %s %s" % (previous_item,
+                                                  previous_score))
+                    LOG.warn("THIS: %s %s" % (item,
+                                                  item_score))
+                    self.assertFalse("Items not returned in order")
+
+            previous_item = item
+
+        (brute_item, brute_score) = brute_force(all_items, constraints)
+
+        self.assertEquals(brute_score,
+                          brute_compute_score(brute_item, constraints))
+        self.assertEquals(brute_score,
+                          brute_compute_score(solved_item, constraints))
+        self.assertEquals(brute_item, solved_item)
 
=== modified file 'nova/tests/test_scheduler.py'
--- nova/tests/test_scheduler.py	2011-03-07 01:25:01 +0000
+++ nova/tests/test_scheduler.py	2011-03-10 20:18:18 +0000
@@ -130,17 +130,20 @@
                                availability_zone='zone1')
 
 
-class SimpleDriverTestCase(test.TestCase):
-    """Test case for simple driver"""
+class _SchedulerBaseTestCase(test.TestCase):
+    """Base test case for scheduler drivers"""
+    def __init__(self, *args, **kwargs):
+        super(_SchedulerBaseTestCase, self).__init__(*args, **kwargs)
+
     def setUp(self):
-        super(SimpleDriverTestCase, self).setUp()
+        super(_SchedulerBaseTestCase, self).setUp()
         self.flags(connection_type='fake',
                    stub_network=True,
                    max_cores=4,
                    max_gigabytes=4,
                    network_manager='nova.network.manager.FlatManager',
                    volume_driver='nova.volume.driver.FakeISCSIDriver',
-                   scheduler_driver='nova.scheduler.simple.SimpleScheduler')
+                   scheduler_driver=self.scheduler_driver)
         self.scheduler = manager.SchedulerManager()
         self.manager = auth_manager.AuthManager()
         self.user = self.manager.create_user('fake', 'fake', 'fake')
@@ -210,47 +213,6 @@
         compute1.kill()
         compute2.kill()
 
-    def test_specific_host_gets_instance(self):
-        """Ensures if you set availability_zone it launches on that zone"""
-        compute1 = self.start_service('compute', host='host1')
-        compute2 = self.start_service('compute', host='host2')
-        instance_id1 = self._create_instance()
-        compute1.run_instance(self.context, instance_id1)
-        instance_id2 = self._create_instance(availability_zone='nova:host1')
-        host = self.scheduler.driver.schedule_run_instance(self.context,
-                                                           instance_id2)
-        self.assertEqual('host1', host)
-        compute1.terminate_instance(self.context, instance_id1)
-        db.instance_destroy(self.context, instance_id2)
-        compute1.kill()
-        compute2.kill()
-
-    def test_wont_sechedule_if_specified_host_is_down(self):
-        compute1 = self.start_service('compute', host='host1')
-        s1 = db.service_get_by_args(self.context, 'host1', 'nova-compute')
-        now = datetime.datetime.utcnow()
-        delta = datetime.timedelta(seconds=FLAGS.service_down_time * 2)
-        past = now - delta
-        db.service_update(self.context, s1['id'], {'updated_at': past})
-        instance_id2 = self._create_instance(availability_zone='nova:host1')
-        self.assertRaises(driver.WillNotSchedule,
-                          self.scheduler.driver.schedule_run_instance,
-                          self.context,
-                          instance_id2)
-        db.instance_destroy(self.context, instance_id2)
-        compute1.kill()
-
-    def test_will_schedule_on_disabled_host_if_specified(self):
-        compute1 = self.start_service('compute', host='host1')
-        s1 = db.service_get_by_args(self.context, 'host1', 'nova-compute')
-        db.service_update(self.context, s1['id'], {'disabled': True})
-        instance_id2 = self._create_instance(availability_zone='nova:host1')
-        host = self.scheduler.driver.schedule_run_instance(self.context,
-                                                           instance_id2)
-        self.assertEqual('host1', host)
-        db.instance_destroy(self.context, instance_id2)
-        compute1.kill()
-
     def test_too_many_cores(self):
         """Ensures we don't go over max cores"""
         compute1 = self.start_service('compute', host='host1')
@@ -316,3 +278,58 @@
             volume2.delete_volume(self.context, volume_id)
         volume1.kill()
         volume2.kill()
+
+
+class SimpleDriverTestCase(_SchedulerBaseTestCase):
+    """Test case for simple driver"""
+    def __init__(self, *args, **kwargs):
+        self.scheduler_driver = 'nova.scheduler.simple.SimpleScheduler'
+        super(SimpleDriverTestCase, self).__init__(*args, **kwargs)
+
+    def test_specific_host_gets_instance(self):
+        """Ensures if you set availability_zone it launches on that zone"""
+        compute1 = self.start_service('compute', host='host1')
+        compute2 = self.start_service('compute', host='host2')
+        instance_id1 = self._create_instance()
+        compute1.run_instance(self.context, instance_id1)
+        instance_id2 = self._create_instance(availability_zone='nova:host1')
+        host = self.scheduler.driver.schedule_run_instance(self.context,
+                                                           instance_id2)
+        self.assertEqual('host1', host)
+        compute1.terminate_instance(self.context, instance_id1)
+        db.instance_destroy(self.context, instance_id2)
+        compute1.kill()
+        compute2.kill()
+
+    def test_wont_sechedule_if_specified_host_is_down(self):
+        compute1 = self.start_service('compute', host='host1')
+        s1 = db.service_get_by_args(self.context, 'host1', 'nova-compute')
+        now = datetime.datetime.utcnow()
+        delta = datetime.timedelta(seconds=FLAGS.service_down_time * 2)
+        past = now - delta
+        db.service_update(self.context, s1['id'], {'updated_at': past})
+        instance_id2 = self._create_instance(availability_zone='nova:host1')
+        self.assertRaises(driver.WillNotSchedule,
+                          self.scheduler.driver.schedule_run_instance,
+                          self.context,
+                          instance_id2)
+        db.instance_destroy(self.context, instance_id2)
+        compute1.kill()
+
+    def test_will_schedule_on_disabled_host_if_specified(self):
+        compute1 = self.start_service('compute', host='host1')
+        s1 = db.service_get_by_args(self.context, 'host1', 'nova-compute')
+        db.service_update(self.context, s1['id'], {'disabled': True})
+        instance_id2 = self._create_instance(availability_zone='nova:host1')
+        host = self.scheduler.driver.schedule_run_instance(self.context,
+                                                           instance_id2)
+        self.assertEqual('host1', host)
+        db.instance_destroy(self.context, instance_id2)
+        compute1.kill()
+
+
+class ConstraintDriverTestCase(_SchedulerBaseTestCase):
+    """Test case for constraint driver"""
+    def __init__(self, *args, **kwargs):
+        self.scheduler_driver = 'nova.scheduler.constraint.ConstraintScheduler'
+        super(ConstraintDriverTestCase, self).__init__(*args, **kwargs)