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

Proposed by justinsb on 2011-03-02
Status: Work in progress
Proposed branch: lp:~justin-fathomdb/nova/constraint-scheduler
Merge into: lp:~hudson-openstack/nova/trunk
Diff against target: 1136 lines (+898/-85)
8 files modified
nova/scheduler/constraint.py (+226/-0)
nova/scheduler/constraint_lib.py (+254/-0)
nova/scheduler/datastore.py (+148/-0)
nova/scheduler/driver.py (+13/-3)
nova/scheduler/simple.py (+24/-35)
nova/scheduler/zone.py (+1/-2)
nova/tests/test_constraintlib.py (+170/-0)
nova/tests/test_scheduler.py (+62/-45)
To merge this branch: bzr merge lp:~justin-fathomdb/nova/constraint-scheduler
Reviewer Review Type Date Requested Status
Nachi Ueno (community) Needs Fixing on 2011-03-10
Nova Core security contacts 2011-03-02 Pending
Review via email: mp+51857@code.launchpad.net

Description of the change

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)

To post a comment you must log in.
Soren Hansen (soren) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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) wrote :

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

justinsb (justin-fathomdb) wrote :

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) wrote :

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) wrote :

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) wrote :

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)

Preview Diff

[H/L] Next/Prev Comment, [J/K] Next/Prev File, [N/P] Next/Prev Hunk
1=== added file 'nova/scheduler/constraint.py'
2--- nova/scheduler/constraint.py 1970-01-01 00:00:00 +0000
3+++ nova/scheduler/constraint.py 2011-03-10 20:18:18 +0000
4@@ -0,0 +1,226 @@
5+# vim: tabstop=4 shiftwidth=4 softtabstop=4
6+
7+# Copyright (c) 2011 Justin Santa Barbara
8+#
9+# All Rights Reserved.
10+#
11+# Licensed under the Apache License, Version 2.0 (the "License"); you may
12+# not use this file except in compliance with the License. You may obtain
13+# a copy of the License at
14+#
15+# http://www.apache.org/licenses/LICENSE-2.0
16+#
17+# Unless required by applicable law or agreed to in writing, software
18+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
19+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
20+# License for the specific language governing permissions and limitations
21+# under the License.
22+
23+"""
24+Constraint-Based Scheduler
25+"""
26+
27+from nova import db
28+from nova import flags
29+from nova import log as logging
30+from nova.scheduler import driver
31+from nova.scheduler import constraint_lib
32+
33+
34+LOG = logging.getLogger('nova.scheduler.constraint')
35+FLAGS = flags.FLAGS
36+
37+
38+class SchedulerConstraint(constraint_lib.Constraint):
39+ def request(self):
40+ return self.solver.context['request']
41+
42+ def request_context(self):
43+ return self.solver.context['request_context']
44+
45+ def scheduler(self):
46+ return self.solver.context['scheduler']
47+
48+ def datastore(self):
49+ return self.scheduler().datastore()
50+
51+ def selectivity(self):
52+ # We default to an intermediate value here
53+ return 0.75
54+
55+ def __str__(self):
56+ return self.__class__.__name__
57+
58+ def __repr__(self):
59+ return self.__str__()
60+
61+
62+class InstanceConstraintFavorLeastLoaded(SchedulerConstraint):
63+ def __init__(self):
64+ super(InstanceConstraintFavorLeastLoaded, self).__init__()
65+ self.db_results = None
66+
67+ def _get_database_items(self):
68+ if not self.db_results:
69+ self.trace(_("get_instance_hosts_sorted"))
70+ results = self.datastore().get_instance_hosts_sorted(
71+ self.request_context())
72+
73+ for result in results:
74+ self.cache_item(result)
75+
76+ self.db_results = results
77+
78+ return self.db_results
79+
80+ def score_item(self, candidate):
81+ score = candidate.utilization_score()
82+ self.trace_score(candidate, score)
83+ return score
84+
85+ def get_candidate_iterator(self):
86+ """Returns an iterator over all items in best-to-least-good order"""
87+ requested_vcpus = self.request()['vcpus']
88+
89+ for host in self._get_database_items():
90+ if host.used + requested_vcpus <= host.capacity:
91+ score = self.score_item(host)
92+ yield constraint_lib.Candidate(host.id, score)
93+ else:
94+ self.trace(_("skip %s: capacity") % host)
95+
96+
97+class VolumeConstraintFavorLeastGigabytes(SchedulerConstraint):
98+ def __init__(self):
99+ super(VolumeConstraintFavorLeastGigabytes, self).__init__()
100+ self.db_results = None
101+
102+ def _get_database_items(self):
103+ if not self.db_results:
104+ self.trace(_("get_volume_hosts_sorted"))
105+ results = self.datastore().get_volume_hosts_sorted(
106+ self.request_context())
107+
108+ for result in results:
109+ self.cache_item(result)
110+
111+ self.db_results = results
112+
113+ return self.db_results
114+
115+ def score_item(self, candidate):
116+ score = candidate.utilization_score()
117+ self.trace_score(candidate, score)
118+ return score
119+
120+ def get_candidate_iterator(self):
121+ """Returns an iterator over all items in best-to-least-good order"""
122+ requested_size = self.request()['size']
123+
124+ for host in self._get_database_items():
125+ if host.used + requested_size <= host.capacity:
126+ score = self.score_item(host)
127+ yield constraint_lib.Candidate(host.id, score)
128+ else:
129+ self.trace(_("skip %s: capacity") % host)
130+
131+
132+class NetworkConstraintFavorLeastNetworks(SchedulerConstraint):
133+ def __init__(self):
134+ super(NetworkConstraintFavorLeastNetworks, self).__init__()
135+ self.db_results = None
136+
137+ def _get_database_items(self):
138+ if not self.db_results:
139+ self.trace(_("get_network_hosts_sorted"))
140+ results = self.datastore().get_network_hosts_sorted(
141+ self.request_context())
142+
143+ for result in results:
144+ self.cache_item(result)
145+
146+ self.db_results = results
147+
148+ return self.db_results
149+
150+ def score_item(self, candidate):
151+ score = candidate.utilization_score()
152+ self.trace_score(candidate, score)
153+ return score
154+
155+ def get_candidate_iterator(self):
156+ """Returns an iterator over all items in best-to-least-good order"""
157+ requested_count = 1
158+
159+ for host in self._get_database_items():
160+ if host.used_networks + requested_count <= host.capacity_networks:
161+ score = self.score_item(host)
162+ yield constraint_lib.Candidate(host.id, score)
163+ else:
164+ self.trace(_("skip %s: capacity") % host)
165+
166+
167+class ConstraintScheduler(driver.Scheduler):
168+ """Implements constraint-based scheduler"""
169+ def __init__(self):
170+ super(ConstraintScheduler, self).__init__()
171+
172+ def schedule(self, context, topic, *_args, **_kwargs):
173+ raise NotImplementedError(_("Must implement a %s scheduler") % topic)
174+
175+ def schedule_run_instance(self, request_context, instance_id,
176+ *_args, **_kwargs):
177+ """Picks a host that is up and has the fewest running instances."""
178+ instance_ref = db.instance_get(request_context, instance_id)
179+
180+ solver = constraint_lib.Solver({'request_context': request_context,
181+ 'request': instance_ref,
182+ 'scheduler': self})
183+ solver.add_constraint(InstanceConstraintFavorLeastLoaded())
184+
185+ for service in solver.get_solutions_iterator():
186+ if self.service_is_up(service.model):
187+ host = service.model['host']
188+ self.datastore().record_instance_scheduled(request_context,
189+ instance_id,
190+ host)
191+ return host
192+
193+ raise driver.NoValidHost(_("No suitable hosts found"))
194+
195+ def schedule_create_volume(self, request_context, volume_id,
196+ *_args, **_kwargs):
197+ """Picks a host that is up and has the fewest volumes."""
198+ volume_ref = db.volume_get(request_context, volume_id)
199+
200+ solver = constraint_lib.Solver({'request_context': request_context,
201+ 'request': volume_ref,
202+ 'scheduler': self})
203+ solver.add_constraint(VolumeConstraintFavorLeastGigabytes())
204+
205+ for service in solver.get_solutions_iterator():
206+ if self.service_is_up(service.model):
207+ host = service.model['host']
208+ self.datastore().record_volume_scheduled(request_context,
209+ volume_id,
210+ host)
211+ return host
212+
213+ raise driver.NoValidHost(_("No suitable hosts found"))
214+
215+ def schedule_set_network_host(self, request_context, *_args, **_kwargs):
216+ """Picks a host that is up and has the fewest networks."""
217+
218+ solver = constraint_lib.Solver({'request_context': request_context,
219+ 'request': {},
220+ 'scheduler': self})
221+ solver.add_constraint(NetworkConstraintFavorLeastNetworks())
222+
223+ for service in solver.get_solutions_iterator():
224+ if self.service_is_up(service.model):
225+ host = service.model['host']
226+ self.datastore().record_network_scheduled(request_context,
227+ host)
228+ return host
229+
230+ raise driver.NoValidHost(_("No suitable hosts found"))
231
232=== added file 'nova/scheduler/constraint_lib.py'
233--- nova/scheduler/constraint_lib.py 1970-01-01 00:00:00 +0000
234+++ nova/scheduler/constraint_lib.py 2011-03-10 20:18:18 +0000
235@@ -0,0 +1,254 @@
236+# vim: tabstop=4 shiftwidth=4 softtabstop=4
237+
238+# Copyright (c) 2011 Justin Santa Barbara
239+# All Rights Reserved.
240+#
241+# Licensed under the Apache License, Version 2.0 (the "License"); you may
242+# not use this file except in compliance with the License. You may obtain
243+# a copy of the License at
244+#
245+# http://www.apache.org/licenses/LICENSE-2.0
246+#
247+# Unless required by applicable law or agreed to in writing, software
248+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
249+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
250+# License for the specific language governing permissions and limitations
251+# under the License.
252+
253+"""
254+Simple Constraint Solver Library
255+"""
256+
257+import heapq
258+
259+from nova import flags
260+from nova import log as logging
261+
262+
263+LOG = logging.getLogger('nova.scheduler.constraint')
264+FLAGS = flags.FLAGS
265+
266+
267+class Candidate(object):
268+ def __init__(self, id, score):
269+ self.id = id
270+ self.score = score
271+
272+ def __str__(self):
273+ return "%s:%s" % (self.id, self.score)
274+
275+
276+class Constraint(object):
277+ def __init__(self):
278+ self.solver = None
279+
280+ def __str__(self):
281+ return "%s" % self.__class__.__name__
282+
283+ def score_item(self, candidate):
284+ """Scores the 'goodness' of a candidate.
285+
286+ For acceptable values, the score must be > 0 and <= 1.
287+ If score <= 0, then the decision is unacceptable"""
288+ raise NotImplementedError("Must implement score_item")
289+
290+ def get_candidate_iterator(self):
291+ """Returns an iterator over all items in best-to-least-good order"""
292+ raise NotImplementedError("Must implement get_candidate_iterator")
293+
294+ def selectivity(self):
295+ """Returns the selectivity of the constraint in (0,1]
296+
297+ A smaller value means the constraint is likely to match fewer results.
298+ If the criteria only matches half the items, use 0.5.
299+ If it only matches one in 10, use 0.1 etc"""
300+ raise NotImplementedError("Must implement selectivity")
301+
302+ def can_beat_score(self, score):
303+ """Checks if we know that we can match/beat the specified score.
304+
305+ This is an optimization; a typical implementation will check the items
306+ in the context and check if at least one of them has a score that is
307+ >= the passed score. If so, we're not going to be the worst criteria,
308+ so we don't need to get the list of values. See the implementation of
309+ the Solver for the details of why!
310+ """
311+ for item in self.solver.all_cached_items():
312+ if self.score_item(item) > score:
313+ return True
314+ return False
315+
316+ def set_solver(self, solver):
317+ if self.solver:
318+ raise Exception("Tried to double-set solver")
319+ self.solver = solver
320+
321+ def trace(self, message):
322+ self.solver.trace(message)
323+
324+ def trace_score(self, candidate, score):
325+ self.trace("%s scored %s => %s" % (self, candidate, score))
326+
327+ def cache_item(self, item):
328+ item_id = item.id
329+ self.solver.cache_item(item, item_id)
330+
331+
332+def get_selectivity(constraint):
333+ return constraint.selectivity()
334+
335+
336+class ConstraintIteratorState(object):
337+ """Holds the state of iteration over the candidates for a constraint"""
338+ def __init__(self, constraint, query_values=True):
339+ self.constraint = constraint
340+
341+ self.is_done = False
342+ self.current = None
343+
344+ if query_values:
345+ self.iterator = constraint.get_candidate_iterator()
346+ self.advance()
347+ else:
348+ self.iterator = None
349+
350+ def advance(self):
351+ next_item = next(self.iterator, None)
352+ if next_item:
353+ self.current = next_item
354+ else:
355+ self.current = None
356+ self.is_done = True
357+
358+ def __str__(self):
359+ return "%s %s" % (self.constraint, self.current)
360+
361+
362+class Solver(object):
363+ """Finds the minimax solution to the constraints
364+
365+ Formally, we're looking for max(min(score(candidate, constraint))
366+ where max is over all candidates
367+ and min is over all constraints.
368+
369+ NOTE(justinsb): Anyone know how to get TeX into here? :-)"""
370+
371+ def __init__(self, context):
372+ self.cached_items = {}
373+ self.context = context
374+ self.constraints = []
375+
376+ def add_constraint(self, constraint):
377+ self.constraints.append(constraint)
378+ constraint.set_solver(self)
379+
380+ def lookup_item(self, item_id):
381+ item = self.cached_items.get(item_id)
382+ if not item:
383+ # This shouldn't be possible
384+ raise Exception(_("Item not in cache: %s") % item_id)
385+ # if self.lookup_function:
386+ # self.trace(_("lookup on %s") % (item_id))
387+ # item = self.lookup_function(item_id)
388+ # self.cache(item, item_id)
389+ # else:
390+ # raise Error()
391+ return item
392+
393+ def cache_item(self, item, item_id):
394+ self.cached_items[item_id] = item
395+
396+ def all_cached_items(self):
397+ return self.cached_items.values()
398+
399+ def trace(self, message):
400+ """Records diagnostic information on scheduling decisions.
401+
402+ Constraint scheduling is not exactly simple. We may in future want to
403+ provide (admin) API calls that expose the scheduling reasoning
404+ """
405+ LOG.debug(message)
406+
407+ def get_solutions_iterator(self):
408+ if not self.constraints:
409+ raise Exception("No constraints provided")
410+
411+ queue = []
412+
413+ # We sort so that the most selective criteria is done first
414+ # This then lets less selective criteria inspect the candidates that
415+ # the more selective candidates have chosen first.
416+ # This is just a (potential) optimization
417+ constraints = sorted(self.constraints, key=get_selectivity)
418+
419+ # Find the criteria which is the lowest scoring (worst)
420+ # Observe that the worst doesn't actually change... the score must get
421+ # lower as we iterate through
422+ worst = None
423+ states = []
424+ for constraint in constraints:
425+ query_values = True
426+
427+ if worst and constraint.can_beat_score(worst.current.score):
428+ # This is a sneaky optimization. If we know we're not going
429+ # to be the worst, we don't need to query (see code below)
430+ # If we'd be querying a REST service or DB, this is important
431+ self.trace(_("Won't query constraint - not the worst: %s") %
432+ (constraint))
433+ query_values = False
434+
435+ state = ConstraintIteratorState(constraint,
436+ query_values=query_values)
437+ states.append(state)
438+
439+ if query_values:
440+ if not worst or worst.current.score > state.current.score:
441+ worst = state
442+
443+ self.trace(_("Using lowest-scoring criteria: %s") %
444+ (worst.constraint))
445+
446+ while not worst.is_done:
447+ self.trace(_("Candidate: %s") % (worst))
448+
449+ # Loop over other constraints to get the score for the candidate
450+ # We break ties by choosing the candidate with the sum of scores
451+ min_score = worst.current.score
452+ tie_break_score = 0
453+
454+ item_id = worst.current.id
455+ item = self.lookup_item(item_id)
456+ for constraint_state in states:
457+ score = constraint_state.constraint.score_item(item)
458+ min_score = min(min_score, score)
459+ tie_break_score += score
460+
461+ # Heapify is really nice and will look at tie_break_score
462+ # if min_score is the same
463+ heapq.heappush(queue, (-min_score, -tie_break_score, item))
464+
465+ # Every future item will have a score <= worst.current.score
466+ while True:
467+ (head_score, tie_break_score, head_item) = queue[0]
468+ head_score = -head_score
469+ #tie_break_score = -tie_break_score
470+ if head_score <= worst.current.score:
471+ break
472+
473+ heapq.heappop(queue)
474+ self.trace(_("Yielding: %s") % (head_item))
475+ yield head_item
476+
477+ # Advance the iterator
478+ worst.advance()
479+ if not worst.is_done:
480+ self.trace(_("Advanced: %s") % (worst))
481+
482+ self.trace(_("Reached end of: %s") % (worst.constraint))
483+
484+ while queue:
485+ (head_score, tie_break_score, head_item) = heapq.heappop(queue)
486+ #head_score = -head_score
487+ #tie_break_score = -tie_break_score
488+ self.trace(_("Yielding: %s") % (head_item))
489+ yield head_item
490
491=== added file 'nova/scheduler/datastore.py'
492--- nova/scheduler/datastore.py 1970-01-01 00:00:00 +0000
493+++ nova/scheduler/datastore.py 2011-03-10 20:18:18 +0000
494@@ -0,0 +1,148 @@
495+# vim: tabstop=4 shiftwidth=4 softtabstop=4
496+
497+# Copyright (c) 2011 Justin Santa Barbara
498+#
499+# All Rights Reserved.
500+#
501+# Licensed under the Apache License, Version 2.0 (the "License"); you may
502+# not use this file except in compliance with the License. You may obtain
503+# a copy of the License at
504+#
505+# http://www.apache.org/licenses/LICENSE-2.0
506+#
507+# Unless required by applicable law or agreed to in writing, software
508+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
509+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
510+# License for the specific language governing permissions and limitations
511+# under the License.
512+
513+"""
514+DataStore for the scheduler.
515+
516+Currently backed by the DB.
517+"""
518+import datetime
519+
520+from nova import db
521+from nova import flags
522+from nova import log as logging
523+
524+
525+LOG = logging.getLogger('nova.scheduler.datastore')
526+FLAGS = flags.FLAGS
527+
528+
529+class SchedulerAbstractHostModel(object):
530+ def __init__(self, id, model, used, capacity):
531+ self.id = id
532+ self.model = model
533+ self.used = used
534+ self.capacity = capacity
535+
536+ def to_s(self):
537+ return '%s %s/%s' % (self.id, self.used, self.capacity)
538+
539+ def utilization_score(self):
540+ # The best machine is one that is unused
541+ utilization = float(self.used) / float(self.capacity)
542+ if utilization > 1:
543+ utilization = 1
544+ score = 1 - utilization
545+ return score
546+
547+
548+class SchedulerInstanceHostModel(SchedulerAbstractHostModel):
549+ def __init__(self, id, model, used_cores, capacity_cores):
550+ super(SchedulerInstanceHostModel, self).__init__(id, model,
551+ used_cores,
552+ capacity_cores)
553+
554+
555+class SchedulerVolumeHostModel(SchedulerAbstractHostModel):
556+ def __init__(self, id, model, used_gigabytes, capacity_gigabytes):
557+ super(SchedulerVolumeHostModel, self).__init__(id, model,
558+ used_gigabytes,
559+ capacity_gigabytes)
560+
561+
562+class SchedulerNetworkHostModel(SchedulerAbstractHostModel):
563+ def __init__(self, id, model, used_networks, capacity_networks):
564+ super(SchedulerNetworkHostModel, self).__init__(id, model,
565+ used_networks,
566+ capacity_networks)
567+
568+
569+class SchedulerDataStore(object):
570+ def get_instance_hosts_sorted(self, context):
571+ results = []
572+ db_results = db.service_get_all_compute_sorted(context)
573+ for db_result in db_results:
574+ (model, used_cores) = db_result
575+ id = model['id']
576+
577+ # TODO(justinsb): We need a way to know the true capacity
578+ capacity_cores = FLAGS.max_cores
579+
580+ item = SchedulerInstanceHostModel(id,
581+ model,
582+ used_cores,
583+ capacity_cores)
584+ results.append(item)
585+ # NOTE(justinsb): This is only sorted by score because max is fixed
586+ return results
587+
588+ def service_get_all_by_topic(self, context, topic):
589+ return db.service_get_all_by_topic(context, topic)
590+
591+ def get_volume_hosts_sorted(self, context):
592+ results = []
593+ db_results = db.service_get_all_volume_sorted(context)
594+ for db_result in db_results:
595+ (model, used_gigabytes) = db_result
596+ id = model['id']
597+
598+ # TODO(justinsb): We need a way to know the true capacity
599+ capacity_gigabytes = FLAGS.max_gigabytes
600+
601+ item = SchedulerVolumeHostModel(id,
602+ model,
603+ used_gigabytes,
604+ capacity_gigabytes)
605+ results.append(item)
606+ # NOTE(justinsb): This is only sorted by score because max is fixed
607+ return results
608+
609+ def get_network_hosts_sorted(self, context):
610+ results = []
611+ db_results = db.service_get_all_network_sorted(context)
612+ for db_result in db_results:
613+ (model, used_networks) = db_result
614+ id = model['id']
615+
616+ # TODO(justinsb): We need a way to know the true capacity
617+ capacity_networks = FLAGS.max_networks
618+
619+ item = SchedulerNetworkHostModel(id,
620+ model,
621+ used_networks,
622+ capacity_networks)
623+ results.append(item)
624+ # NOTE(justinsb): This is only sorted by score because max is fixed
625+ return results
626+
627+ def record_instance_scheduled(self, context, instance_id, host):
628+ now = datetime.datetime.utcnow()
629+ db.instance_update(context,
630+ instance_id,
631+ {'host': host,
632+ 'scheduled_at': now})
633+
634+ def record_volume_scheduled(self, context, volume_id, host):
635+ now = datetime.datetime.utcnow()
636+ db.volume_update(context,
637+ volume_id,
638+ {'host': host,
639+ 'scheduled_at': now})
640+
641+ def record_network_scheduled(self, context, host):
642+ pass
643
644=== modified file 'nova/scheduler/driver.py'
645--- nova/scheduler/driver.py 2011-01-18 19:01:16 +0000
646+++ nova/scheduler/driver.py 2011-03-10 20:18:18 +0000
647@@ -3,6 +3,7 @@
648 # Copyright (c) 2010 Openstack, LLC.
649 # Copyright 2010 United States Government as represented by the
650 # Administrator of the National Aeronautics and Space Administration.
651+# Copyright 2011 Justin Santa Barbara
652 # All Rights Reserved.
653 #
654 # Licensed under the Apache License, Version 2.0 (the "License"); you may
655@@ -23,9 +24,10 @@
656
657 import datetime
658
659-from nova import db
660 from nova import exception
661 from nova import flags
662+from nova.scheduler import datastore
663+
664
665 FLAGS = flags.FLAGS
666 flags.DEFINE_integer('service_down_time', 60,
667@@ -44,6 +46,9 @@
668
669 class Scheduler(object):
670 """The base class that all Scheduler clases should inherit from."""
671+ def __init__(self):
672+ super(Scheduler, self).__init__()
673+ self._datastore = None
674
675 @staticmethod
676 def service_is_up(service):
677@@ -55,8 +60,7 @@
678
679 def hosts_up(self, context, topic):
680 """Return the list of hosts that have a running service for topic."""
681-
682- services = db.service_get_all_by_topic(context, topic)
683+ services = self.datastore().service_get_all_by_topic(context, topic)
684 return [service.host
685 for service in services
686 if self.service_is_up(service)]
687@@ -64,3 +68,9 @@
688 def schedule(self, context, topic, *_args, **_kwargs):
689 """Must override at least this method for scheduler to work."""
690 raise NotImplementedError(_("Must implement a fallback schedule"))
691+
692+ def datastore(self):
693+ """Returns the associated SchedulerDataStore"""
694+ if not self._datastore:
695+ self._datastore = datastore.SchedulerDataStore()
696+ return self._datastore
697
698=== modified file 'nova/scheduler/simple.py'
699--- nova/scheduler/simple.py 2011-01-27 22:14:10 +0000
700+++ nova/scheduler/simple.py 2011-03-10 20:18:18 +0000
701@@ -3,6 +3,7 @@
702 # Copyright (c) 2010 Openstack, LLC.
703 # Copyright 2010 United States Government as represented by the
704 # Administrator of the National Aeronautics and Space Administration.
705+# Copyright 2011 Justin Santa Barbara
706 # All Rights Reserved.
707 #
708 # Licensed under the Apache License, Version 2.0 (the "License"); you may
709@@ -21,8 +22,6 @@
710 Simple Scheduler
711 """
712
713-import datetime
714-
715 from nova import db
716 from nova import flags
717 from nova.scheduler import driver
718@@ -52,25 +51,19 @@
719 if not self.service_is_up(service):
720 raise driver.WillNotSchedule(_("Host %s is not alive") % host)
721
722- # TODO(vish): this probably belongs in the manager, if we
723- # can generalize this somehow
724- now = datetime.datetime.utcnow()
725- db.instance_update(context, instance_id, {'host': host,
726- 'scheduled_at': now})
727+ self.datastore().record_instance_scheduled(context,
728+ instance_id,
729+ host)
730 return host
731- results = db.service_get_all_compute_sorted(context)
732+ results = self.datastore().get_instance_hosts_sorted(context)
733 for result in results:
734- (service, instance_cores) = result
735- if instance_cores + instance_ref['vcpus'] > FLAGS.max_cores:
736+ service = result.model
737+ if result.used + instance_ref['vcpus'] > result.capacity:
738 raise driver.NoValidHost(_("All hosts have too many cores"))
739 if self.service_is_up(service):
740- # NOTE(vish): this probably belongs in the manager, if we
741- # can generalize this somehow
742- now = datetime.datetime.utcnow()
743- db.instance_update(context,
744- instance_id,
745- {'host': service['host'],
746- 'scheduled_at': now})
747+ self.datastore().record_instance_scheduled(context,
748+ instance_id,
749+ service['host'])
750 return service['host']
751 raise driver.NoValidHost(_("No hosts found"))
752
753@@ -86,37 +79,33 @@
754 if not self.service_is_up(service):
755 raise driver.WillNotSchedule(_("Host %s not available") % host)
756
757- # TODO(vish): this probably belongs in the manager, if we
758- # can generalize this somehow
759- now = datetime.datetime.utcnow()
760- db.volume_update(context, volume_id, {'host': host,
761- 'scheduled_at': now})
762+ self.datastore().record_volume_scheduled(context,
763+ volume_id,
764+ host)
765 return host
766- results = db.service_get_all_volume_sorted(context)
767+ results = self.datastore().get_volume_hosts_sorted(context)
768 for result in results:
769- (service, volume_gigabytes) = result
770- if volume_gigabytes + volume_ref['size'] > FLAGS.max_gigabytes:
771+ service = result.model
772+ if result.used + volume_ref['size'] > result.capacity:
773 raise driver.NoValidHost(_("All hosts have too many "
774 "gigabytes"))
775 if self.service_is_up(service):
776- # NOTE(vish): this probably belongs in the manager, if we
777- # can generalize this somehow
778- now = datetime.datetime.utcnow()
779- db.volume_update(context,
780- volume_id,
781- {'host': service['host'],
782- 'scheduled_at': now})
783+ self.datastore().record_volume_scheduled(context,
784+ volume_id,
785+ service['host'])
786 return service['host']
787 raise driver.NoValidHost(_("No hosts found"))
788
789 def schedule_set_network_host(self, context, *_args, **_kwargs):
790 """Picks a host that is up and has the fewest networks."""
791
792- results = db.service_get_all_network_sorted(context)
793+ results = self.datastore().get_network_hosts_sorted(context)
794 for result in results:
795- (service, instance_count) = result
796- if instance_count >= FLAGS.max_networks:
797+ service = result.model
798+ if result.used + 1 > result.capacity:
799 raise driver.NoValidHost(_("All hosts have too many networks"))
800 if self.service_is_up(service):
801+ self.datastore().record_network_scheduled(context,
802+ service['host'])
803 return service['host']
804 raise driver.NoValidHost(_("No hosts found"))
805
806=== modified file 'nova/scheduler/zone.py'
807--- nova/scheduler/zone.py 2011-01-11 22:27:36 +0000
808+++ nova/scheduler/zone.py 2011-03-10 20:18:18 +0000
809@@ -24,7 +24,6 @@
810 import random
811
812 from nova.scheduler import driver
813-from nova import db
814
815
816 class ZoneScheduler(driver.Scheduler):
817@@ -38,7 +37,7 @@
818 if zone is None:
819 return self.hosts_up(context, topic)
820
821- services = db.service_get_all_by_topic(context, topic)
822+ services = self.datastore().service_get_all_by_topic(context, topic)
823 return [service.host
824 for service in services
825 if self.service_is_up(service)
826
827=== added file 'nova/tests/test_constraintlib.py'
828--- nova/tests/test_constraintlib.py 1970-01-01 00:00:00 +0000
829+++ nova/tests/test_constraintlib.py 2011-03-10 20:18:18 +0000
830@@ -0,0 +1,170 @@
831+# vim: tabstop=4 shiftwidth=4 softtabstop=4
832+
833+# Copyright 2011 Justin Santa Barbara
834+# All Rights Reserved.
835+#
836+# Licensed under the Apache License, Version 2.0 (the "License"); you may
837+# not use this file except in compliance with the License. You may obtain
838+# a copy of the License at
839+#
840+# http://www.apache.org/licenses/LICENSE-2.0
841+#
842+# Unless required by applicable law or agreed to in writing, software
843+# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
844+# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
845+# License for the specific language governing permissions and limitations
846+# under the License.
847+"""
848+Tests For Constraint Library
849+"""
850+
851+import random
852+
853+from nova import flags
854+from nova import log as logging
855+from nova import test
856+from nova.scheduler import constraint_lib
857+
858+
859+LOG = logging.getLogger('nova.tests.constraintlib')
860+
861+FLAGS = flags.FLAGS
862+FLAGS.verbose = True
863+
864+
865+def brute_compute_score(item, constraints):
866+ min_score = None
867+ for constraint in constraints:
868+ score = constraint.score_item(item)
869+ if min_score and min_score <= score:
870+ continue
871+ min_score = score
872+
873+ return min_score
874+
875+
876+def brute_force(all_items, constraints):
877+ max_min_score = None
878+ max_min_item = None
879+
880+ for item in all_items:
881+ min_score = brute_compute_score(item, constraints)
882+
883+ if max_min_score and max_min_score >= min_score:
884+ continue
885+
886+ max_min_score = min_score
887+ max_min_item = item
888+
889+ return (max_min_item, max_min_score)
890+
891+
892+class ParameterBoundConstraint(constraint_lib.Constraint):
893+ def __init__(self, all_items, key, selectivity_value):
894+ super(ParameterBoundConstraint, self).__init__()
895+ self.all_items = all_items
896+ self.key = key
897+ self.selectivity_value = selectivity_value
898+
899+ def to_s(self):
900+ return "ParameterBoundConstraint:%s" % self.key
901+
902+ def score_item(self, candidate):
903+ return candidate[self.key]
904+
905+ def get_candidate_iterator(self):
906+ """Returns an iterator over all items in best-to-least-good order"""
907+ all_items_ordered = sorted(self.all_items,
908+ key=self.score_item,
909+ reverse=True)
910+ for item in all_items_ordered:
911+ score = self.score_item(item)
912+ item_id = item['id']
913+ yield constraint_lib.Candidate(item_id, score)
914+
915+ def selectivity(self):
916+ return self.selectivity_value
917+
918+
919+class ConstraintLibTestCase(test.TestCase):
920+ """Test case for constraint library"""
921+
922+ def test_five_five__five(self):
923+ rnd = random.Random()
924+ rnd.seed(555)
925+
926+ for _rep in range(5):
927+ self._do_random_test(rnd, 5, 5)
928+
929+ def test_big(self):
930+ rnd = random.Random()
931+ rnd.seed(1234)
932+
933+ item_count = 1000
934+ constraints_count = 100
935+
936+ self._do_random_test(rnd, item_count, constraints_count)
937+
938+ def _test_random_100(self):
939+ """This is hidden because it's slow, but it's a nice torture test"""
940+ rnd = random.Random()
941+ rnd.seed(1234)
942+
943+ for _rep in range(100):
944+ item_count = rnd.randint(100, 1000)
945+ constraints_count = rnd.randint(5, 100)
946+
947+ self._do_random_test(rnd, item_count, constraints_count)
948+
949+ def _do_random_test(self, rnd, item_count, constraints_count):
950+ all_items = []
951+
952+ context = {}
953+ solver = constraint_lib.Solver(context)
954+
955+ for j in range(item_count):
956+ item = {}
957+ for i in range(constraints_count):
958+ key = 'c%s' % i
959+ item[key] = rnd.random()
960+ item['id'] = j
961+ all_items.append(item)
962+ solver.cache_item(item, item['id'])
963+
964+ constraints = []
965+ for i in range(constraints_count):
966+ key = 'c%s' % i
967+ selectivity_value = rnd.random()
968+ constraint = ParameterBoundConstraint(all_items,
969+ key,
970+ selectivity_value)
971+ solver.add_constraint(constraint)
972+ constraints.append(constraint)
973+
974+ solved_item = None
975+
976+ previous_item = None
977+ for item in solver.get_solutions_iterator():
978+ if not solved_item:
979+ solved_item = item
980+ if previous_item:
981+ previous_score = brute_compute_score(previous_item,
982+ constraints)
983+ item_score = brute_compute_score(item, constraints)
984+
985+ if previous_score < item_score:
986+ LOG.warn("PREVIOUS: %s %s" % (previous_item,
987+ previous_score))
988+ LOG.warn("THIS: %s %s" % (item,
989+ item_score))
990+ self.assertFalse("Items not returned in order")
991+
992+ previous_item = item
993+
994+ (brute_item, brute_score) = brute_force(all_items, constraints)
995+
996+ self.assertEquals(brute_score,
997+ brute_compute_score(brute_item, constraints))
998+ self.assertEquals(brute_score,
999+ brute_compute_score(solved_item, constraints))
1000+ self.assertEquals(brute_item, solved_item)
1001
1002=== modified file 'nova/tests/test_scheduler.py'
1003--- nova/tests/test_scheduler.py 2011-03-07 01:25:01 +0000
1004+++ nova/tests/test_scheduler.py 2011-03-10 20:18:18 +0000
1005@@ -130,17 +130,20 @@
1006 availability_zone='zone1')
1007
1008
1009-class SimpleDriverTestCase(test.TestCase):
1010- """Test case for simple driver"""
1011+class _SchedulerBaseTestCase(test.TestCase):
1012+ """Base test case for scheduler drivers"""
1013+ def __init__(self, *args, **kwargs):
1014+ super(_SchedulerBaseTestCase, self).__init__(*args, **kwargs)
1015+
1016 def setUp(self):
1017- super(SimpleDriverTestCase, self).setUp()
1018+ super(_SchedulerBaseTestCase, self).setUp()
1019 self.flags(connection_type='fake',
1020 stub_network=True,
1021 max_cores=4,
1022 max_gigabytes=4,
1023 network_manager='nova.network.manager.FlatManager',
1024 volume_driver='nova.volume.driver.FakeISCSIDriver',
1025- scheduler_driver='nova.scheduler.simple.SimpleScheduler')
1026+ scheduler_driver=self.scheduler_driver)
1027 self.scheduler = manager.SchedulerManager()
1028 self.manager = auth_manager.AuthManager()
1029 self.user = self.manager.create_user('fake', 'fake', 'fake')
1030@@ -210,47 +213,6 @@
1031 compute1.kill()
1032 compute2.kill()
1033
1034- def test_specific_host_gets_instance(self):
1035- """Ensures if you set availability_zone it launches on that zone"""
1036- compute1 = self.start_service('compute', host='host1')
1037- compute2 = self.start_service('compute', host='host2')
1038- instance_id1 = self._create_instance()
1039- compute1.run_instance(self.context, instance_id1)
1040- instance_id2 = self._create_instance(availability_zone='nova:host1')
1041- host = self.scheduler.driver.schedule_run_instance(self.context,
1042- instance_id2)
1043- self.assertEqual('host1', host)
1044- compute1.terminate_instance(self.context, instance_id1)
1045- db.instance_destroy(self.context, instance_id2)
1046- compute1.kill()
1047- compute2.kill()
1048-
1049- def test_wont_sechedule_if_specified_host_is_down(self):
1050- compute1 = self.start_service('compute', host='host1')
1051- s1 = db.service_get_by_args(self.context, 'host1', 'nova-compute')
1052- now = datetime.datetime.utcnow()
1053- delta = datetime.timedelta(seconds=FLAGS.service_down_time * 2)
1054- past = now - delta
1055- db.service_update(self.context, s1['id'], {'updated_at': past})
1056- instance_id2 = self._create_instance(availability_zone='nova:host1')
1057- self.assertRaises(driver.WillNotSchedule,
1058- self.scheduler.driver.schedule_run_instance,
1059- self.context,
1060- instance_id2)
1061- db.instance_destroy(self.context, instance_id2)
1062- compute1.kill()
1063-
1064- def test_will_schedule_on_disabled_host_if_specified(self):
1065- compute1 = self.start_service('compute', host='host1')
1066- s1 = db.service_get_by_args(self.context, 'host1', 'nova-compute')
1067- db.service_update(self.context, s1['id'], {'disabled': True})
1068- instance_id2 = self._create_instance(availability_zone='nova:host1')
1069- host = self.scheduler.driver.schedule_run_instance(self.context,
1070- instance_id2)
1071- self.assertEqual('host1', host)
1072- db.instance_destroy(self.context, instance_id2)
1073- compute1.kill()
1074-
1075 def test_too_many_cores(self):
1076 """Ensures we don't go over max cores"""
1077 compute1 = self.start_service('compute', host='host1')
1078@@ -316,3 +278,58 @@
1079 volume2.delete_volume(self.context, volume_id)
1080 volume1.kill()
1081 volume2.kill()
1082+
1083+
1084+class SimpleDriverTestCase(_SchedulerBaseTestCase):
1085+ """Test case for simple driver"""
1086+ def __init__(self, *args, **kwargs):
1087+ self.scheduler_driver = 'nova.scheduler.simple.SimpleScheduler'
1088+ super(SimpleDriverTestCase, self).__init__(*args, **kwargs)
1089+
1090+ def test_specific_host_gets_instance(self):
1091+ """Ensures if you set availability_zone it launches on that zone"""
1092+ compute1 = self.start_service('compute', host='host1')
1093+ compute2 = self.start_service('compute', host='host2')
1094+ instance_id1 = self._create_instance()
1095+ compute1.run_instance(self.context, instance_id1)
1096+ instance_id2 = self._create_instance(availability_zone='nova:host1')
1097+ host = self.scheduler.driver.schedule_run_instance(self.context,
1098+ instance_id2)
1099+ self.assertEqual('host1', host)
1100+ compute1.terminate_instance(self.context, instance_id1)
1101+ db.instance_destroy(self.context, instance_id2)
1102+ compute1.kill()
1103+ compute2.kill()
1104+
1105+ def test_wont_sechedule_if_specified_host_is_down(self):
1106+ compute1 = self.start_service('compute', host='host1')
1107+ s1 = db.service_get_by_args(self.context, 'host1', 'nova-compute')
1108+ now = datetime.datetime.utcnow()
1109+ delta = datetime.timedelta(seconds=FLAGS.service_down_time * 2)
1110+ past = now - delta
1111+ db.service_update(self.context, s1['id'], {'updated_at': past})
1112+ instance_id2 = self._create_instance(availability_zone='nova:host1')
1113+ self.assertRaises(driver.WillNotSchedule,
1114+ self.scheduler.driver.schedule_run_instance,
1115+ self.context,
1116+ instance_id2)
1117+ db.instance_destroy(self.context, instance_id2)
1118+ compute1.kill()
1119+
1120+ def test_will_schedule_on_disabled_host_if_specified(self):
1121+ compute1 = self.start_service('compute', host='host1')
1122+ s1 = db.service_get_by_args(self.context, 'host1', 'nova-compute')
1123+ db.service_update(self.context, s1['id'], {'disabled': True})
1124+ instance_id2 = self._create_instance(availability_zone='nova:host1')
1125+ host = self.scheduler.driver.schedule_run_instance(self.context,
1126+ instance_id2)
1127+ self.assertEqual('host1', host)
1128+ db.instance_destroy(self.context, instance_id2)
1129+ compute1.kill()
1130+
1131+
1132+class ConstraintDriverTestCase(_SchedulerBaseTestCase):
1133+ """Test case for constraint driver"""
1134+ def __init__(self, *args, **kwargs):
1135+ self.scheduler_driver = 'nova.scheduler.constraint.ConstraintScheduler'
1136+ super(ConstraintDriverTestCase, self).__init__(*args, **kwargs)