Adds LeastCostScheduler which uses a series of cost functions and associated weights to determine which host to provision to.

Left for future work:

* Handle scheduling of many instances (currently assumes n=1)
* Handle scheduling of arbitrary resources (currently weigh_hosts only handles instances)
* Add more cost functions (currently just noop and fill-first)
* Simulator so we can determine sensible values for cost-function-weights

NOTE: This patch depends on Sandy's dist-scheduler-2a patch.

5 files changed, 383 insertions, 1 deletions

diff --git a/nova/tests/scheduler/__init__.py b/nova/tests/scheduler/__init__.py
new file mode 100644
index 000000000..e69de29bb
--- /dev/null
+++ b/nova/tests/scheduler/__init__.py
diff --git a/nova/tests/scheduler/test_host_filter.py b/nova/tests/scheduler/test_host_filter.py
new file mode 100644
index 000000000..07817cc5a
--- /dev/null
+++ b/nova/tests/scheduler/test_host_filter.py
@@ -0,0 +1,206 @@
+# Copyright 2011 OpenStack LLC.
+# 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 Scheduler Host Filters.
+"""
+
+import json
+
+from nova import exception
+from nova import flags
+from nova import test
+from nova.scheduler import host_filter
+
+FLAGS = flags.FLAGS
+
+
+class FakeZoneManager:
+    pass
+
+
+class HostFilterTestCase(test.TestCase):
+    """Test case for host filters."""
+
+    def _host_caps(self, multiplier):
+        # Returns host capabilities in the following way:
+        # host1 = memory:free 10 (100max)
+        #         disk:available 100 (1000max)
+        # hostN = memory:free 10 + 10N
+        #         disk:available 100 + 100N
+        # in other words: hostN has more resources than host0
+        # which means ... don't go above 10 hosts.
+        return {'host_name-description': 'XenServer %s' % multiplier,
+                'host_hostname': 'xs-%s' % multiplier,
+                'host_memory_total': 100,
+                'host_memory_overhead': 10,
+                'host_memory_free': 10 + multiplier * 10,
+                'host_memory_free-computed': 10 + multiplier * 10,
+                'host_other-config': {},
+                'host_ip_address': '192.168.1.%d' % (100 + multiplier),
+                'host_cpu_info': {},
+                'disk_available': 100 + multiplier * 100,
+                'disk_total': 1000,
+                'disk_used': 0,
+                'host_uuid': 'xxx-%d' % multiplier,
+                'host_name-label': 'xs-%s' % multiplier}
+
+    def setUp(self):
+        self.old_flag = FLAGS.default_host_filter
+        FLAGS.default_host_filter = \
+                            'nova.scheduler.host_filter.AllHostsFilter'
+        self.instance_type = dict(name='tiny',
+                memory_mb=50,
+                vcpus=10,
+                local_gb=500,
+                flavorid=1,
+                swap=500,
+                rxtx_quota=30000,
+                rxtx_cap=200)
+
+        self.zone_manager = FakeZoneManager()
+        states = {}
+        for x in xrange(10):
+            states['host%02d' % (x + 1)] = {'compute': self._host_caps(x)}
+        self.zone_manager.service_states = states
+
+    def tearDown(self):
+        FLAGS.default_host_filter = self.old_flag
+
+    def test_choose_filter(self):
+        # Test default filter ...
+        hf = host_filter.choose_host_filter()
+        self.assertEquals(hf._full_name(),
+                        'nova.scheduler.host_filter.AllHostsFilter')
+        # Test valid filter ...
+        hf = host_filter.choose_host_filter(
+                        'nova.scheduler.host_filter.InstanceTypeFilter')
+        self.assertEquals(hf._full_name(),
+                        'nova.scheduler.host_filter.InstanceTypeFilter')
+        # Test invalid filter ...
+        try:
+            host_filter.choose_host_filter('does not exist')
+            self.fail("Should not find host filter.")
+        except exception.SchedulerHostFilterNotFound:
+            pass
+
+    def test_all_host_filter(self):
+        hf = host_filter.AllHostsFilter()
+        cooked = hf.instance_type_to_filter(self.instance_type)
+        hosts = hf.filter_hosts(self.zone_manager, cooked)
+        self.assertEquals(10, len(hosts))
+        for host, capabilities in hosts:
+            self.assertTrue(host.startswith('host'))
+
+    def test_instance_type_filter(self):
+        hf = host_filter.InstanceTypeFilter()
+        # filter all hosts that can support 50 ram and 500 disk
+        name, cooked = hf.instance_type_to_filter(self.instance_type)
+        self.assertEquals('nova.scheduler.host_filter.InstanceTypeFilter',
+                          name)
+        hosts = hf.filter_hosts(self.zone_manager, cooked)
+        self.assertEquals(6, len(hosts))
+        just_hosts = [host for host, caps in hosts]
+        just_hosts.sort()
+        self.assertEquals('host05', just_hosts[0])
+        self.assertEquals('host10', just_hosts[5])
+
+    def test_json_filter(self):
+        hf = host_filter.JsonFilter()
+        # filter all hosts that can support 50 ram and 500 disk
+        name, cooked = hf.instance_type_to_filter(self.instance_type)
+        self.assertEquals('nova.scheduler.host_filter.JsonFilter', name)
+        hosts = hf.filter_hosts(self.zone_manager, cooked)
+        self.assertEquals(6, len(hosts))
+        just_hosts = [host for host, caps in hosts]
+        just_hosts.sort()
+        self.assertEquals('host05', just_hosts[0])
+        self.assertEquals('host10', just_hosts[5])
+
+        # Try some custom queries
+
+        raw = ['or',
+                   ['and',
+                       ['<', '$compute.host_memory_free', 30],
+                       ['<', '$compute.disk_available', 300]
+                   ],
+                   ['and',
+                       ['>', '$compute.host_memory_free', 70],
+                       ['>', '$compute.disk_available', 700]
+                   ]
+              ]
+        cooked = json.dumps(raw)
+        hosts = hf.filter_hosts(self.zone_manager, cooked)
+
+        self.assertEquals(5, len(hosts))
+        just_hosts = [host for host, caps in hosts]
+        just_hosts.sort()
+        for index, host in zip([1, 2, 8, 9, 10], just_hosts):
+            self.assertEquals('host%02d' % index, host)
+
+        raw = ['not',
+                  ['=', '$compute.host_memory_free', 30],
+              ]
+        cooked = json.dumps(raw)
+        hosts = hf.filter_hosts(self.zone_manager, cooked)
+
+        self.assertEquals(9, len(hosts))
+        just_hosts = [host for host, caps in hosts]
+        just_hosts.sort()
+        for index, host in zip([1, 2, 4, 5, 6, 7, 8, 9, 10], just_hosts):
+            self.assertEquals('host%02d' % index, host)
+
+        raw = ['in', '$compute.host_memory_free', 20, 40, 60, 80, 100]
+        cooked = json.dumps(raw)
+        hosts = hf.filter_hosts(self.zone_manager, cooked)
+
+        self.assertEquals(5, len(hosts))
+        just_hosts = [host for host, caps in hosts]
+        just_hosts.sort()
+        for index, host in zip([2, 4, 6, 8, 10], just_hosts):
+            self.assertEquals('host%02d' % index, host)
+
+        # Try some bogus input ...
+        raw = ['unknown command', ]
+        cooked = json.dumps(raw)
+        try:
+            hf.filter_hosts(self.zone_manager, cooked)
+            self.fail("Should give KeyError")
+        except KeyError, e:
+            pass
+
+        self.assertTrue(hf.filter_hosts(self.zone_manager, json.dumps([])))
+        self.assertTrue(hf.filter_hosts(self.zone_manager, json.dumps({})))
+        self.assertTrue(hf.filter_hosts(self.zone_manager, json.dumps(
+                ['not', True, False, True, False]
+            )))
+
+        try:
+            hf.filter_hosts(self.zone_manager, json.dumps(
+                'not', True, False, True, False
+            ))
+            self.fail("Should give KeyError")
+        except KeyError, e:
+            pass
+
+        self.assertFalse(hf.filter_hosts(self.zone_manager,
+                json.dumps(['=', '$foo', 100])))
+        self.assertFalse(hf.filter_hosts(self.zone_manager,
+                json.dumps(['=', '$.....', 100])))
+        self.assertFalse(hf.filter_hosts(self.zone_manager,
+                json.dumps(
+            ['>', ['and', ['or', ['not', ['<', ['>=', ['<=', ['in', ]]]]]]]])))
+
+        self.assertFalse(hf.filter_hosts(self.zone_manager,
+                json.dumps(['=', {}, ['>', '$missing....foo']])))
diff --git a/nova/tests/scheduler/test_least_cost_scheduler.py b/nova/tests/scheduler/test_least_cost_scheduler.py
new file mode 100644
index 000000000..506fa62fb
--- /dev/null
+++ b/nova/tests/scheduler/test_least_cost_scheduler.py
@@ -0,0 +1,144 @@
+# Copyright 2011 OpenStack LLC.
+# 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 Least Cost Scheduler
+"""
+
+from nova import flags
+from nova import test
+from nova.scheduler import least_cost
+from nova.tests.scheduler import test_zone_aware_scheduler
+
+MB = 1024 * 1024
+FLAGS = flags.FLAGS
+
+
+class FakeHost(object):
+    def __init__(self, host_id, free_ram, io):
+        self.id = host_id
+        self.free_ram = free_ram
+        self.io = io
+
+
+class WeightedSumTestCase(test.TestCase):
+    def test_empty_domain(self):
+        domain = []
+        weighted_fns = []
+        result = least_cost.weighted_sum(domain, weighted_fns)
+        expected = []
+        self.assertEqual(expected, result)
+
+    def test_basic_costing(self):
+        hosts = [
+            FakeHost(1, 512 * MB, 100),
+            FakeHost(2, 256 * MB, 400),
+            FakeHost(3, 512 * MB, 100)
+        ]
+
+        weighted_fns = [
+            (1, lambda h: h.free_ram),  # Fill-first, free_ram is a *cost*
+            (2, lambda h: h.io),  # Avoid high I/O
+        ]
+
+        costs = least_cost.weighted_sum(
+            domain=hosts, weighted_fns=weighted_fns)
+
+        # Each 256 MB unit of free-ram contributes 0.5 points by way of:
+        #   cost = weight * (score/max_score) = 1 * (256/512) = 0.5
+        # Each 100 iops of IO adds 0.5 points by way of:
+        #   cost = 2 * (100/400) = 2 * 0.25 = 0.5
+        expected = [1.5, 2.5, 1.5]
+        self.assertEqual(expected, costs)
+
+
+class LeastCostSchedulerTestCase(test.TestCase):
+    def setUp(self):
+        super(LeastCostSchedulerTestCase, self).setUp()
+
+        class FakeZoneManager:
+            pass
+
+        zone_manager = FakeZoneManager()
+
+        states = test_zone_aware_scheduler.fake_zone_manager_service_states(
+            num_hosts=10)
+        zone_manager.service_states = states
+
+        self.sched = least_cost.LeastCostScheduler()
+        self.sched.zone_manager = zone_manager
+
+    def tearDown(self):
+        super(LeastCostSchedulerTestCase, self).tearDown()
+
+    def assertWeights(self, expected, num, request_spec, hosts):
+        weighted = self.sched.weigh_hosts(num, request_spec, hosts)
+        self.assertDictListMatch(weighted, expected, approx_equal=True)
+
+    def test_no_hosts(self):
+        num = 1
+        request_spec = {}
+        hosts = []
+
+        expected = []
+        self.assertWeights(expected, num, request_spec, hosts)
+
+    def test_noop_cost_fn(self):
+        FLAGS.least_cost_scheduler_cost_functions = [
+            'nova.scheduler.least_cost.noop_cost_fn'
+        ]
+        FLAGS.noop_cost_fn_weight = 1
+
+        num = 1
+        request_spec = {}
+        hosts = self.sched.filter_hosts(num, request_spec)
+
+        expected = [dict(weight=1, hostname=hostname)
+                    for hostname, caps in hosts]
+        self.assertWeights(expected, num, request_spec, hosts)
+
+    def test_cost_fn_weights(self):
+        FLAGS.least_cost_scheduler_cost_functions = [
+            'nova.scheduler.least_cost.noop_cost_fn'
+        ]
+        FLAGS.noop_cost_fn_weight = 2
+
+        num = 1
+        request_spec = {}
+        hosts = self.sched.filter_hosts(num, request_spec)
+
+        expected = [dict(weight=2, hostname=hostname)
+                    for hostname, caps in hosts]
+        self.assertWeights(expected, num, request_spec, hosts)
+
+    def test_fill_first_cost_fn(self):
+        FLAGS.least_cost_scheduler_cost_functions = [
+            'nova.scheduler.least_cost.fill_first_cost_fn'
+        ]
+        FLAGS.fill_first_cost_fn_weight = 1
+
+        num = 1
+        request_spec = {}
+        hosts = self.sched.filter_hosts(num, request_spec)
+
+        expected = []
+        for idx, (hostname, caps) in enumerate(hosts):
+            # Costs are normalized so over 10 hosts, each host with increasing
+            # free ram will cost 1/N more. Since the lowest cost host has some
+            # free ram, we add in the 1/N for the base_cost
+            weight = 0.1 + (0.1 * idx)
+            weight_dict = dict(weight=weight, hostname=hostname)
+            expected.append(weight_dict)
+
+        self.assertWeights(expected, num, request_spec, hosts)
diff --git a/nova/tests/test_scheduler.py b/nova/tests/scheduler/test_scheduler.py
index 54b3f80fb..b0f0e882a 100644
--- a/nova/tests/test_scheduler.py
+++ b/nova/tests/scheduler/test_scheduler.py
@@ -61,7 +61,8 @@ class SchedulerTestCase(test.TestCase):
     """Test case for scheduler"""
     def setUp(self):
         super(SchedulerTestCase, self).setUp()
-        self.flags(scheduler_driver='nova.tests.test_scheduler.TestDriver')
+        driver = 'nova.tests.scheduler.test_scheduler.TestDriver'
+        self.flags(scheduler_driver=driver)
 
     def _create_compute_service(self):
         """Create compute-manager(ComputeNode and Service record)."""
diff --git a/nova/tests/test_zone_aware_scheduler.py b/nova/tests/scheduler/test_zone_aware_scheduler.py
index 72b74be20..561fdea94 100644
--- a/nova/tests/test_zone_aware_scheduler.py
+++ b/nova/tests/scheduler/test_zone_aware_scheduler.py
@@ -22,6 +22,37 @@ from nova.scheduler import zone_aware_scheduler
 from nova.scheduler import zone_manager
 
 
+def _host_caps(multiplier):
+    # Returns host capabilities in the following way:
+    # host1 = memory:free 10 (100max)
+    #         disk:available 100 (1000max)
+    # hostN = memory:free 10 + 10N
+    #         disk:available 100 + 100N
+    # in other words: hostN has more resources than host0
+    # which means ... don't go above 10 hosts.
+    return {'host_name-description': 'XenServer %s' % multiplier,
+            'host_hostname': 'xs-%s' % multiplier,
+            'host_memory_total': 100,
+            'host_memory_overhead': 10,
+            'host_memory_free': 10 + multiplier * 10,
+            'host_memory_free-computed': 10 + multiplier * 10,
+            'host_other-config': {},
+            'host_ip_address': '192.168.1.%d' % (100 + multiplier),
+            'host_cpu_info': {},
+            'disk_available': 100 + multiplier * 100,
+            'disk_total': 1000,
+            'disk_used': 0,
+            'host_uuid': 'xxx-%d' % multiplier,
+            'host_name-label': 'xs-%s' % multiplier}
+
+
+def fake_zone_manager_service_states(num_hosts):
+    states = {}
+    for x in xrange(num_hosts):
+        states['host%02d' % (x + 1)] = {'compute': _host_caps(x)}
+    return states
+
+
 class FakeZoneAwareScheduler(zone_aware_scheduler.ZoneAwareScheduler):
     def filter_hosts(self, num, specs):
         # NOTE(sirp): this is returning [(hostname, services)]