Merge lp:~justin-fathomdb/nova/schedule-compute-near-volume into lp:~hudson-openstack/nova/trunk

[justinsb]

The first new pluggable scheduler policy: support allocation of machines in a requested 'location'.

The 'location' is like eday's DNS-style zone names. Because that isn't implemented yet, we instead infer the location based on the reversed host DNS name (for now). Also, because we don't know how we're going to pass this information, we instead pass it in the only collection we've got: the metadata.

[Todd Willey (xtoddx)]

Probably shouldn't pass context as {} in the test case, as it will raise warnings if it actually gets used.

[Christopher MacGown (0x44)]

Should _build_topology, Topology, NamedTopology, and TopologyNode have docstrings?

[justinsb (justin-fathomdb)]

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

Unmerged revisions

734. By justinsb on 2011-03-08

Pep8ulous

733. By justinsb on 2011-03-08

Got tests passing; the problem was how to handle ties (i.e. when the weakest constraint had a draw)

732. By justinsb on 2011-03-08

Changed to using the more pythonic __str__ instead of the to_s hack

731. By justinsb on 2011-03-08

Merged in tests

730. By justinsb on 2011-03-08

Fix misnamed method service_get_all_by_topic_location

729. By justinsb on 2011-03-08

Fix superclass call

728. By justinsb on 2011-03-07

Plug in proximity based scheduler based on metadata

727. By justinsb on 2011-03-07

Merged with trunk

726. By justinsb on 2011-03-07

Initial implementation of proximity scheduler constraint

725. By justinsb on 2011-03-07

Added simple topology mapper

=== modified file 'nova/db/sqlalchemy/models.py'
--- nova/db/sqlalchemy/models.py	2011-03-03 19:13:15 +0000
+++ nova/db/sqlalchemy/models.py	2011-03-08 07:15:21 +0000
@@ -99,6 +99,9 @@
         local.update(joined)
         return local.iteritems()
 
+    def __repr__(self):
+        return "%s" % dict(self)
+
 
 class Service(BASE, NovaBase):
     """Represents a running service on a host."""

=== modified file 'nova/scheduler/constraint.py'
--- nova/scheduler/constraint.py	2011-03-08 07:15:20 +0000
+++ nova/scheduler/constraint.py	2011-03-08 07:15:21 +0000
@@ -23,6 +23,7 @@
 from nova import db
 from nova import flags
 from nova import log as logging
+from nova.scheduler import datastore
 from nova.scheduler import driver
 from nova.scheduler import constraint_lib
 
@@ -44,13 +45,20 @@
     def datastore(self):
         return self.scheduler().datastore()
 
+    def topology(self):
+        context = self.request_context()
+        return self.scheduler().topology(context)
+
     def selectivity(self):
         # We default to an intermediate value here
         return 0.75
 
-    def to_s(self):
+    def __str__(self):
         return self.__class__.__name__
 
+    def __repr__(self):
+        return self.__str__()
+
 
 class InstanceConstraintFavorLeastLoaded(SchedulerConstraint):
     def __init__(self):
@@ -71,7 +79,9 @@
         return self.db_results
 
     def score_item(self, candidate):
-        return candidate.utilization_score()
+        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"""
@@ -85,6 +95,46 @@
                 self.trace(_("skip %s: capacity") % host)
 
 
+class InstanceConstraintPlaceNearLocation(SchedulerConstraint):
+    def __str__(self):
+        return "InstanceConstraintPlaceNearLocation:%s" % self.target_location
+
+    def __init__(self, target_location):
+        super(InstanceConstraintPlaceNearLocation, self).__init__()
+        self.target_location = target_location
+
+    def _score_service(self, service):
+        location = datastore.get_service_location(service)
+        distance = self.topology().distance(self.target_location, location)
+        score = 1 / float(1 + distance)  # Map to (0, 1]
+        LOG.debug("%s scores %s" % (location, score))
+        return score
+
+    def score_item(self, candidate):
+        score = self._score_service(candidate.model)
+        self.trace_score(candidate, score)
+        return score
+
+    def get_candidate_iterator(self):
+        """Returns an iterator over all items in best-to-least-good order"""
+        topo = self.topology()
+        for location in topo.find_by_distance_from(self.target_location):
+            services = self.datastore().service_get_all_by_topic_location(
+                                                    self.request_context(),
+                                                    'compute',
+                                                    location.key)
+            LOG.debug(_("Found services at %(location)s => %(services)s")
+                      % locals())
+            for service in services:
+                score = self._score_service(service)
+                LOG.debug("%s scores %s" % (service.host, score))
+                yield constraint_lib.Candidate(service.id, score)
+
+    def selectivity(self):
+        # TODO(justinsb): We need to systematize this a bit better...
+        return 0.1  # We expect to be very selective
+
+
 class VolumeConstraintFavorLeastGigabytes(SchedulerConstraint):
     def __init__(self):
         super(VolumeConstraintFavorLeastGigabytes, self).__init__()
@@ -169,6 +219,22 @@
                                         'scheduler': self})
         solver.add_constraint(InstanceConstraintFavorLeastLoaded())
 
+        # NOTE(justinsb): Once we reach a decision on where this metadata
+        #  should be, then use that location.  For now, use 'metadata'
+        if instance_ref.get('metadata'):
+            for item in instance_ref['metadata']:
+                key = item['key']
+                value = item['value']
+
+                if key == 'openstack:near':
+                    topo = self.topology(request_context)
+                    node = topo.get_node_by_key(value, create=True)
+                    constraint = InstanceConstraintPlaceNearLocation(node)
+                    solver.add_constraint(constraint)
+
+        LOG.debug("Metadata: %s" % instance_ref.get('metadata'))
+        LOG.debug("Constraints: %s" % solver.constraints)
+
         for service in solver.get_solutions_iterator():
             if self.service_is_up(service.model):
                 host = service.model['host']

=== modified file 'nova/scheduler/constraint_lib.py'
--- nova/scheduler/constraint_lib.py	2011-03-08 07:15:20 +0000
+++ nova/scheduler/constraint_lib.py	2011-03-08 07:15:21 +0000
@@ -34,7 +34,7 @@
         self.id = id
         self.score = score
 
-    def to_s(self):
+    def __str__(self):
         return "%s:%s" % (self.id, self.score)
 
 
@@ -42,8 +42,8 @@
     def __init__(self):
         self.solver = None
 
-    def to_s(self):
-        return "%s" % self
+    def __str__(self):
+        return "%s" % self.__class__.__name__
 
     def score_item(self, candidate):
         """Scores the 'goodness' of a candidate.
@@ -86,6 +86,9 @@
     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)
@@ -117,11 +120,8 @@
             self.current = None
             self.is_done = True
 
-    def to_s(self):
-        if self.current:
-            return "%s %s" % (self.constraint.to_s(), self.current.to_s())
-        else:
-            return "%s -" % (self.constraint.to_s())
+    def __str__(self):
+        return "%s %s" % (self.constraint, self.current)
 
 
 class Solver(object):
@@ -194,7 +194,7 @@
                 #  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.to_s()))
+                           (constraint))
                 query_values = False
 
             state = ConstraintIteratorState(constraint,
@@ -206,40 +206,49 @@
                     worst = state
 
         self.trace(_("Using lowest-scoring criteria: %s") %
-                   (worst.constraint.to_s()))
+                   (worst.constraint))
 
         while not worst.is_done:
-            self.trace(_("Candidate: %s") % (worst.to_s()))
-
-            # Query other constraints to get the score for the candidate
-            item_score = worst.current.score
+            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)
-                item_score = min(item_score, score)
+                min_score = min(min_score, score)
+                tie_break_score += score
 
-            heapq.heappush(queue, (-item_score, item))
+            # 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, head_item) = queue[0]
+                (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.to_s()))
+                self.trace(_("Yielding: %s") % (head_item))
                 yield head_item
 
             # Advance the iterator
             worst.advance()
             if not worst.is_done:
-                self.trace(_("Advanced: %s") % (worst.to_s()))
+                self.trace(_("Advanced: %s") % (worst))
 
-        self.trace(_("Reached end of: %s") % (worst.constraint.to_s()))
+        self.trace(_("Reached end of: %s") % (worst.constraint))
 
         while queue:
-            (head_score, head_item) = heapq.heappop(queue)
-            self.trace(_("Yielding: %s") % (head_item.to_s()))
+            (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

=== modified file 'nova/scheduler/datastore.py'
--- nova/scheduler/datastore.py	2011-03-08 07:15:20 +0000
+++ nova/scheduler/datastore.py	2011-03-08 07:15:21 +0000
@@ -32,6 +32,20 @@
 FLAGS = flags.FLAGS
 
 
+def get_service_location(service):
+    #TODO(justinsb): Implement configurable location
+    #TODO(justinsb): Move this to service class
+    location = None  # service.location
+
+    if not location:
+        # Fall back to using the DNS name / IP for "poor man's" topology
+        location = service.host
+        components = location.split('.')
+        components.reverse()
+        location = '.'.join(components)
+    return location
+
+
 class SchedulerAbstractHostModel(object):
     def __init__(self, id, model, used, capacity):
         self.id = id
@@ -39,9 +53,12 @@
         self.used = used
         self.capacity = capacity
 
-    def to_s(self):
+    def __str__(self):
         return '%s %s/%s' % (self.id, self.used, self.capacity)
 
+    def __repr__(self):
+        return "Host:%s" % self
+
     def utilization_score(self):
         # The best machine is one that is unused
         utilization = float(self.used) / float(self.capacity)
@@ -94,6 +111,17 @@
     def service_get_all_by_topic(self, context, topic):
         return db.service_get_all_by_topic(context, topic)
 
+    def service_get_all_by_topic_location(self, context, topic, location):
+        #TODO(justinsb): We need a call like this once we've agreed it
+        #return db.service_get_all_by_topic_location(context, topic, location)
+
+        services = []
+        for service in db.service_get_all_by_topic(context, topic):
+            if location == get_service_location(service):
+                services.append(service)
+
+        return services
+
     def get_volume_hosts_sorted(self, context):
         results = []
         db_results = db.service_get_all_volume_sorted(context)
@@ -146,3 +174,6 @@
 
     def record_network_scheduled(self, context, host):
         pass
+
+    def service_get_all(self, context):
+        return db.service_get_all(context)

=== modified file 'nova/scheduler/driver.py'
--- nova/scheduler/driver.py	2011-03-08 07:15:20 +0000
+++ nova/scheduler/driver.py	2011-03-08 07:15:21 +0000
@@ -26,9 +26,12 @@
 
 from nova import exception
 from nova import flags
+from nova import log as logging
 from nova.scheduler import datastore
-
-
+from nova.scheduler import topology
+
+
+LOG = logging.getLogger('nova.scheduler.driver')
 FLAGS = flags.FLAGS
 flags.DEFINE_integer('service_down_time', 60,
                      'maximum time since last checkin for up service')
@@ -49,6 +52,7 @@
     def __init__(self):
         super(Scheduler, self).__init__()
         self._datastore = None
+        self._topology = None
 
     @staticmethod
     def service_is_up(service):
@@ -74,3 +78,36 @@
         if not self._datastore:
             self._datastore = datastore.SchedulerDataStore()
         return self._datastore
+
+    def _build_topology(self, context):
+        #TODO(justinsb): Refresh?
+        topo = topology.NamedTopology()
+
+        nodes = {}
+
+        services = self.datastore().service_get_all(context)
+        for service in services:
+            #TODO(justinsb): Implement configurable location
+            location = None  # service.location
+
+            if not location:
+                # Fall back to using the DNS name / IP for topology
+                location = service.host
+                components = location.split('.')
+                components.reverse()
+                location = '.'.join(components)
+                LOG.debug("Rewrote %s to %s" % (service.host, location))
+
+            node = nodes.get(location)
+            if not node:
+                node = topology.TopologyNode(location)
+                topo.add(node)
+                nodes[location] = node
+
+        return topo
+
+    def topology(self, context):
+        """Returns the associated SchedulerDataStore"""
+        if not self._topology:
+            self._topology = self._build_topology(context)
+        return self._topology

=== added file 'nova/scheduler/topology.py'
--- nova/scheduler/topology.py	1970-01-01 00:00:00 +0000
+++ nova/scheduler/topology.py	2011-03-08 07:15:21 +0000
@@ -0,0 +1,121 @@
+# 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.
+
+"""
+Topology mapping to expose e.g. same machine, same rack, same room etc
+"""
+
+from nova import flags
+from nova import log as logging
+
+
+LOG = logging.getLogger('nova.scheduler.constraint')
+FLAGS = flags.FLAGS
+
+
+class TopologyNode(object):
+    def __str__(self):
+        return self.key
+
+    def __repr__(self):
+        return "TopologyNode:%s" % self.key
+
+    def __init__(self, key):
+        self.key = key
+
+
+class Topology(object):
+    def distance(self, a, b):
+        """Returns the distance from TopologyNode a to TopologyNode b"""
+        raise NotImplementedError()
+
+    def find_by_distance_from(self, a):
+        """Returns all the topology nodes ordered with the closest to a first.
+
+        This may (should?) return an iterator"""
+        raise NotImplementedError()
+
+
+class NamedTopology(Topology):
+    """A named toplogy uses DNS-like naming e.g. machine3.rack2.roomb.nyc.us
+
+    We assume that the distance between two items is:
+      (D - the length of the suffix path they share)
+    where D is the maximum distance.
+
+    Trick: We assume all names are reversed, so
+        machine3.rack2.roomb.us => us.roomb.rack2.machine3
+        Prefix matching is much more natural, in particular for databases
+
+    This is really eday's concept - all credit to him!
+    """
+    def __init__(self):
+        #TODO(justinsb): As we aim for scale, we should switch to a graph
+        self.nodes = []
+        self.nodes_by_key = {}
+        self.max_distance = 0
+
+    def add(self, node):
+        # Pre-compute the components
+        node.components = node.key.split('.')
+        self.nodes.append(node)
+        self.nodes_by_key[node.key] = node
+        self.max_distance = max(self.max_distance, len(node.components))
+
+    def distance(self, a, b):
+        # This is an inefficient implementation
+        if not isinstance(a, TopologyNode):
+            a = self.get_node_by_key(a)
+
+        if not isinstance(b, TopologyNode):
+            b = self.get_node_by_key(b)
+
+        if not a or not b:
+            return self.max_distance + 1
+
+        a_components = a.components
+        b_components = b.components
+
+        min_length = min(len(a_components), len(b_components))
+        d = 0
+        while True:
+            if d >= min_length:
+                break
+            if a_components[d] != b_components[d]:
+                break
+            d = d + 1
+
+        d = self.max_distance - d
+        return d
+
+    def find_by_distance_from(self, a):
+        # This is an inefficient implementation
+        proximities = [(node, self.distance(a, node))
+                       for node in self.nodes]
+
+        proximities.sort(key=lambda p: p[1])
+
+        ret = [p[0] for p in proximities]
+        return ret
+
+    def get_node_by_key(self, key, create=False):
+        node = self.nodes_by_key.get(key)
+        if create and not node:
+            node = TopologyNode(key)
+            self.add(node)
+        return node

=== modified file 'nova/tests/test_constraintlib.py'
--- nova/tests/test_constraintlib.py	2011-03-08 07:15:20 +0000
+++ nova/tests/test_constraintlib.py	2011-03-08 07:15:21 +0000
@@ -119,7 +119,8 @@
     def _do_random_test(self, rnd, item_count, constraints_count):
         all_items = []
 
-        solver = constraint_lib.Solver(None, None)
+        context = {}
+        solver = constraint_lib.Solver(context)
 
         for j in range(item_count):
             item = {}

=== modified file 'nova/tests/test_scheduler.py'
--- nova/tests/test_scheduler.py	2011-03-08 07:15:20 +0000
+++ nova/tests/test_scheduler.py	2011-03-08 07:15:21 +0000
@@ -30,6 +30,7 @@
 from nova import rpc
 from nova import utils
 from nova.auth import manager as auth_manager
+from nova.db.sqlalchemy import models
 from nova.scheduler import manager
 from nova.scheduler import driver
 
@@ -84,7 +85,7 @@
         self.flags(scheduler_driver='nova.scheduler.zone.ZoneScheduler')
 
     def _create_service_model(self, **kwargs):
-        service = db.sqlalchemy.models.Service()
+        service = models.Service()
         service.host = kwargs['host']
         service.disabled = False
         service.deleted = False
@@ -153,7 +154,7 @@
     def tearDown(self):
         self.manager.delete_user(self.user)
         self.manager.delete_project(self.project)
-        super(SimpleDriverTestCase, self).tearDown()
+        super(_SchedulerBaseTestCase, self).tearDown()
 
     def _create_instance(self, **kwargs):
         """Create a test instance"""
@@ -167,6 +168,12 @@
         inst['ami_launch_index'] = 0
         inst['vcpus'] = 1
         inst['availability_zone'] = kwargs.get('availability_zone', None)
+        if kwargs.get('metadata'):
+            metadata_list = []
+            for k, v in kwargs['metadata'].items():
+                metadata_list.append(models.InstanceMetadata(key=k, value=v))
+            inst['metadata'] = metadata_list
+
         return db.instance_create(self.context, inst)['id']
 
     def _create_volume(self):
@@ -335,3 +342,46 @@
     def __init__(self, *args, **kwargs):
         self.scheduler_driver = 'nova.scheduler.constraint.ConstraintScheduler'
         super(ConstraintDriverTestCase, self).__init__(*args, **kwargs)
+
+    def test_create_compute_in_location(self):
+        """Ensures that location requests behave as we expect"""
+
+        # Set up two cabinets each with two machines
+        for machine_number in [1, 2]:
+            for cabinet_number in [1, 2]:
+                host = ('machine%s.cab%s.openstack' %
+                        (cabinet_number, machine_number))
+                _service = self.start_service('compute', host=host)
+
+        # Should allocate onto requested machine
+        metadata = {'openstack:near': 'openstack.cab1.machine1'}
+        instance_id = self._create_instance(metadata=metadata)
+        host1 = self.scheduler.driver.schedule_run_instance(self.context,
+                                                            instance_id)
+        self.assertEqual('machine1.cab1.openstack', host1)
+
+        # Requested machine doesn't exist; should match onto cab1
+        #  and then choose the less-loaded machine2
+        metadata = {'openstack:near': 'openstack.cab1.machineX'}
+        instance_id = self._create_instance(metadata=metadata)
+        host2 = self.scheduler.driver.schedule_run_instance(self.context,
+                                                            instance_id)
+        self.assertEqual('machine2.cab1.openstack', host2)
+
+        # Will match cab2 but not a machine, neither machine should have any
+        #  load, so will go onto either machine in cab2
+        metadata = {'openstack:near': 'openstack.cab2.machineX'}
+        instance_id = self._create_instance(metadata=metadata)
+        host3 = self.scheduler.driver.schedule_run_instance(self.context,
+                                                            instance_id)
+        # Should allocate onto either machine in cab2
+        self.assertTrue(host3.endswith('.cab2.openstack'))
+
+        # Should be no-location match.
+        # Should go onto the only machine with no servers
+        metadata = {'openstack:near': 'openstack.cabX.machine1'}
+        instance_id = self._create_instance(metadata=metadata)
+        host4 = self.scheduler.driver.schedule_run_instance(self.context,
+                                                            instance_id)
+        self.assertTrue(host4.endswith('.cab2.openstack'))
+        self.assertNotEqual(host3, host4)  # It should be on the other server

=== added file 'nova/tests/test_topology.py'
--- nova/tests/test_topology.py	1970-01-01 00:00:00 +0000
+++ nova/tests/test_topology.py	2011-03-08 07:15:21 +0000
@@ -0,0 +1,89 @@
+# 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 Topology
+"""
+
+from nova import test
+from nova.scheduler import topology
+
+
+class NamedTopologyTestCase(test.TestCase):
+    """Test case for named topology"""
+    def _build_simple_topology(self):
+        t = topology.NamedTopology()
+        t.add(topology.TopologyNode('room1.rack1.machine1'))
+        t.add(topology.TopologyNode('room1.rack1.machine2'))
+        t.add(topology.TopologyNode('room1.rack2.machine1'))
+        t.add(topology.TopologyNode('room1.rack2.machine2'))
+        t.add(topology.TopologyNode('room2.rack1.machine1'))
+        t.add(topology.TopologyNode('room2.rack1.machine2'))
+        t.add(topology.TopologyNode('room2.rack2.machine1'))
+        t.add(topology.TopologyNode('room2.rack2.machine2'))
+        self.topology = t
+
+    def _distance(self, key1, key2):
+        node1 = self.topology.get_node_by_key(key1)
+        node2 = self.topology.get_node_by_key(key2)
+        return self.topology.distance(node1, node2)
+
+    def _keys_by_distance_from(self, key1):
+        node1 = self.topology.get_node_by_key(key1)
+        nodes = self.topology.find_by_distance_from(node1)
+        return [node.key for node in nodes]
+
+    def test_distances(self):
+        self._build_simple_topology()
+
+        self.assertEquals(0, self._distance('room1.rack1.machine1',
+                                            'room1.rack1.machine1'))
+
+        self.assertEquals(1, self._distance('room1.rack1.machine1',
+                                            'room1.rack1.machine2'))
+
+        self.assertEquals(2, self._distance('room1.rack1.machine1',
+                                            'room1.rack2.machine1'))
+
+        self.assertEquals(3, self._distance('room1.rack1.machine1',
+                                            'room2.rack1.machine1'))
+
+    def test_order_by_distance(self):
+        self._build_simple_topology()
+
+        keys = self._keys_by_distance_from('room1.rack1.machine1')
+        # We assume a stable sort...
+        self.assertEquals(keys, ['room1.rack1.machine1',
+                                 'room1.rack1.machine2',
+                                 'room1.rack2.machine1',
+                                 'room1.rack2.machine2',
+                                 'room2.rack1.machine1',
+                                 'room2.rack1.machine2',
+                                 'room2.rack2.machine1',
+                                 'room2.rack2.machine2',
+                                 ])
+
+        keys = self._keys_by_distance_from('room2.rack2.machine2')
+        # We assume a stable sort...
+        self.assertEquals(keys, ['room2.rack2.machine2',
+                                 'room2.rack2.machine1',
+                                 'room2.rack1.machine1',
+                                 'room2.rack1.machine2',
+                                 'room1.rack1.machine1',
+                                 'room1.rack1.machine2',
+                                 'room1.rack2.machine1',
+                                 'room1.rack2.machine2',
+                                 ])