Merge lp:~allenap/maas/ntp-prefer-nearby-servers--bug-1675095 into lp:~maas-committers/maas/trunk

[Gavin Panella]

Calculated routes between nodes are now prioritised.

This is necessarily hand-wavy because it's nearly impossible to anticipate the cost exactly. Instead a cost is calculated based on a few expectations:

- Sending traffic within a single host is fastest.
- Sending traffic within the same subnet is next.
- Then, sending traffic within the same VLAN.
- Then, sending traffic within the same space.
- Then, sending traffic within the null space.

These costs are relative to one another only, and they do not convey relative _magnitudes_ of cost. They are useful for ordering only.

[Andres Rodriguez (andreserl)]

http://pastebin.ubuntu.com/24274775/

review: Needs Fixing

=== modified file 'src/maasserver/dbviews.py'
--- src/maasserver/dbviews.py	2017-03-07 16:26:47 +0000
+++ src/maasserver/dbviews.py	2017-03-29 15:49:17 +0000
@@ -36,6 +36,7 @@
     with closing(connection.cursor()) as cursor:
         cursor.execute(view_sql)
 
+
 # Note that the `Discovery` model object is backed by this view. Any
 # changes made to this view should be reflected there.
 maasserver_discovery = dedent("""\
@@ -102,17 +103,33 @@
 # should not be used without constraining, say, the sets of nodes, to find
 # addresses that are mutually routable between region controllers for example.
 maasserver_routable_pairs = dedent("""\
-    SELECT if_left.node_id AS left_node_id,
+    SELECT
+           -- "Left" node.
+           if_left.node_id AS left_node_id,
            if_left.id AS left_interface_id,
            subnet_left.id AS left_subnet_id,
            vlan_left.id AS left_vlan_id,
            sip_left.ip AS left_ip,
+
+           -- "Right" node.
            if_right.node_id AS right_node_id,
            if_right.id AS right_interface_id,
            subnet_right.id AS right_subnet_id,
            vlan_right.id AS right_vlan_id,
            sip_right.ip AS right_ip,
-           vlan_left.space_id AS space_id
+
+           -- Space that left and right have in commmon. Can be NULL.
+           vlan_left.space_id AS space_id,
+
+           -- Relative metric; lower is better.
+           CASE
+             WHEN if_left.node_id = if_right.node_id THEN 0
+             WHEN subnet_left.id = subnet_right.id THEN 1
+             WHEN vlan_left.id = vlan_right.id THEN 2
+             WHEN vlan_left.space_id IS NOT NULL THEN 3
+             ELSE 4  -- The NULL space.
+           END AS metric
+
       FROM maasserver_interface AS if_left
       JOIN maasserver_interface_ip_addresses AS ifia_left
         ON if_left.id = ifia_left.interface_id

=== modified file 'src/maasserver/ntp.py'
--- src/maasserver/ntp.py	2016-10-03 20:10:53 +0000
+++ src/maasserver/ntp.py	2017-03-29 15:49:17 +0000
@@ -124,8 +124,9 @@
         routable_addrs_map: AddressMap) -> Iterable[IPAddress]:
     """Choose one routable address per destination node.
 
-    The result is stable, preferring IPv6 over IPv4, and then the highest
-    address numberically. (In fact it relies on the ordering provided by
-    `netaddr.IPAddress`, which is basically that.)
+    The addresses are in preference order (see `find_addresses_between_nodes`
+    for information on how that's derived) so this simply chooses the first.
     """
-    return map(max, routable_addrs_map.values())
+    for addresses in routable_addrs_map.values():
+        assert len(addresses) >= 1
+        yield addresses[0]

=== modified file 'src/maasserver/routablepairs.py'
--- src/maasserver/routablepairs.py	2016-09-19 14:50:27 +0000
+++ src/maasserver/routablepairs.py	2017-03-29 15:49:17 +0000
@@ -24,6 +24,17 @@
     ``node-left`` and ``node-right`` are one of the nodes passed in and
     ``addr-left`` and ``addr-right`` are :class:`netaddr.IPAddress` instances
     corresponding to an active address on their respective nodes.
+
+    The results are sorted, lowest metric first, meaning that earlier
+    addresses are likely to have a lower overall communications cost, lower
+    latency, and so on. The order of preference is:
+
+    - Same node
+    - Same subnet
+    - Same VLAN
+    - Same space
+
+    An explicitly defined space is preferred to the default / null space.
     """
     nodes_left = {node.id: node for node in nodes_left}
     nodes_right = {node.id: node for node in nodes_right}
@@ -48,6 +59,7 @@
       FROM maasserver_routable_pairs
      WHERE left_node_id IN (%s)
        AND right_node_id IN (%s)
+     ORDER BY metric ASC
 """)
 
 

=== modified file 'src/maasserver/tests/test_dbviews.py'
--- src/maasserver/tests/test_dbviews.py	2017-01-28 00:51:47 +0000
+++ src/maasserver/tests/test_dbviews.py	2017-03-29 15:49:17 +0000
@@ -10,6 +10,7 @@
     _ALL_VIEWS,
     register_all_views,
 )
+from maasserver.models.subnet import Subnet
 from maasserver.testing.factory import factory
 from maasserver.testing.testcase import MAASServerTestCase
 from testtools.matchers import HasLength
@@ -39,29 +40,97 @@
             cursor.execute("SELECT * from maasserver_routable_pairs")
             self.assertThat(cursor.fetchall(), HasLength(0))
 
-    def make_node_with_address(self, space, cidr):
+    def make_node_with_address(self, cidr, space=None, vlan=None):
         node = factory.make_Node()
         iface = factory.make_Interface(node=node)
-        subnet = factory.make_Subnet(space=space, cidr=cidr)
+        try:
+            subnet = Subnet.objects.get(cidr=cidr, vlan__space=space)
+        except Subnet.DoesNotExist:
+            subnet = factory.make_Subnet(cidr=cidr, space=space, vlan=vlan)
         sip = factory.make_StaticIPAddress(interface=iface, subnet=subnet)
         return node, iface, subnet, sip
 
+    def test__contains_routes_between_nodes_on_same_subnet(self):
+        network = factory.make_ip4_or_6_network()
+        node1, if1, sn1, sip1 = self.make_node_with_address(network)
+        node2, if2, sn2, sip2 = self.make_node_with_address(network)
+
+        # Routes between all addresses are found, even back to themselves.
+        left = node1.id, if1.id, sn1.id, sn1.vlan.id, sip1.ip
+        right = node2.id, if2.id, sn2.id, sn2.vlan.id, sip2.ip
+        row = lambda ent1, ent2, metric: (*ent1, *ent2, None, metric)
+        expected = [
+            row(left, left, 0),
+            row(left, right, 1),  # Same space, hence metric of 3.
+            row(right, right, 0),
+            row(right, left, 1),  # Same space, hence metric of 3.
+        ]
+
+        with connection.cursor() as cursor:
+            cursor.execute("SELECT * from maasserver_routable_pairs")
+            self.assertItemsEqual(expected, cursor.fetchall())
+
+    def test__contains_routes_between_nodes_on_same_vlan(self):
+        vlan = factory.make_VLAN()
+        network1 = factory.make_ip4_or_6_network()
+        network2 = factory.make_ip4_or_6_network(version=network1.version)
+        node1, if1, sn1, sip1 = self.make_node_with_address(
+            network1, vlan=vlan)
+        node2, if2, sn2, sip2 = self.make_node_with_address(
+            network2, vlan=vlan)
+
+        # Routes between all addresses are found, even back to themselves.
+        left = node1.id, if1.id, sn1.id, sn1.vlan.id, sip1.ip
+        right = node2.id, if2.id, sn2.id, sn2.vlan.id, sip2.ip
+        row = lambda ent1, ent2, metric: (*ent1, *ent2, None, metric)
+        expected = [
+            row(left, left, 0),
+            row(left, right, 2),  # Same VLAN, hence metric of 2.
+            row(right, right, 0),
+            row(right, left, 2),  # Same VLAN, hence metric of 2.
+        ]
+
+        with connection.cursor() as cursor:
+            cursor.execute("SELECT * from maasserver_routable_pairs")
+            self.assertItemsEqual(expected, cursor.fetchall())
+
     def test__contains_routes_between_nodes_on_same_space(self):
         space = factory.make_Space()
         network1 = factory.make_ip4_or_6_network()
         network2 = factory.make_ip4_or_6_network(version=network1.version)
-        node1, if1, sn1, sip1 = self.make_node_with_address(space, network1)
-        node2, if2, sn2, sip2 = self.make_node_with_address(space, network2)
-
-        # Routes between all addresses are found, even back to themselves.
-        left = node1.id, if1.id, sn1.id, sn1.vlan.id, sip1.ip
-        right = node2.id, if2.id, sn2.id, sn2.vlan.id, sip2.ip
-        row = lambda ent1, ent2: ent1 + ent2 + (space.id, )
-        expected = [
-            row(left, left),
-            row(left, right),
-            row(right, right),
-            row(right, left),
+        node1, if1, sn1, sip1 = self.make_node_with_address(network1, space)
+        node2, if2, sn2, sip2 = self.make_node_with_address(network2, space)
+
+        # Routes between all addresses are found, even back to themselves.
+        left = node1.id, if1.id, sn1.id, sn1.vlan.id, sip1.ip
+        right = node2.id, if2.id, sn2.id, sn2.vlan.id, sip2.ip
+        row = lambda ent1, ent2, metric: (*ent1, *ent2, space.id, metric)
+        expected = [
+            row(left, left, 0),
+            row(left, right, 3),  # Same space, hence metric of 3.
+            row(right, right, 0),
+            row(right, left, 3),  # Same space, hence metric of 3.
+        ]
+
+        with connection.cursor() as cursor:
+            cursor.execute("SELECT * from maasserver_routable_pairs")
+            self.assertItemsEqual(expected, cursor.fetchall())
+
+    def test__contains_routes_between_nodes_via_null_space(self):
+        network1 = factory.make_ip4_or_6_network()
+        network2 = factory.make_ip4_or_6_network(version=network1.version)
+        node1, if1, sn1, sip1 = self.make_node_with_address(network1)
+        node2, if2, sn2, sip2 = self.make_node_with_address(network2)
+
+        # Routes between all addresses are found, even back to themselves.
+        left = node1.id, if1.id, sn1.id, sn1.vlan.id, sip1.ip
+        right = node2.id, if2.id, sn2.id, sn2.vlan.id, sip2.ip
+        row = lambda ent1, ent2, metric: (*ent1, *ent2, None, metric)
+        expected = [
+            row(left, left, 0),
+            row(left, right, 4),  # The NULL space, hence metric of 4.
+            row(right, right, 0),
+            row(right, left, 4),  # The NULL space, hence metric of 4.
         ]
 
         with connection.cursor() as cursor:
@@ -73,8 +142,8 @@
         space2 = factory.make_Space()
         network1 = factory.make_ip4_or_6_network()
         network2 = factory.make_ip4_or_6_network(version=network1.version)
-        node1, if1, sn1, sip1 = self.make_node_with_address(space1, network1)
-        node2, if2, sn2, sip2 = self.make_node_with_address(space2, network2)
+        node1, if1, sn1, sip1 = self.make_node_with_address(network1, space1)
+        node2, if2, sn2, sip2 = self.make_node_with_address(network2, space2)
 
         # Only routes from left to left and right to right are found: right is
         # not routable from left, and left is not routable from right because
@@ -82,8 +151,8 @@
         left = node1.id, if1.id, sn1.id, sn1.vlan.id, sip1.ip
         right = node2.id, if2.id, sn2.id, sn2.vlan.id, sip2.ip
         expected = [
-            left + left + (space1.id,),
-            right + right + (space2.id,),
+            (*left, *left, space1.id, 0),
+            (*right, *right, space2.id, 0),
         ]
 
         with connection.cursor() as cursor:
@@ -95,8 +164,8 @@
         network1 = factory.make_ip4_or_6_network()
         network2 = factory.make_ip4_or_6_network(
             version=(4 if network1.version == 6 else 6))
-        node1, if1, sn1, sip1 = self.make_node_with_address(space, network1)
-        node2, if2, sn2, sip2 = self.make_node_with_address(space, network2)
+        node1, if1, sn1, sip1 = self.make_node_with_address(network1, space)
+        node2, if2, sn2, sip2 = self.make_node_with_address(network2, space)
 
         # Only routes from left to left and right to right are found: right is
         # not routable from left, and left is not routable from right because
@@ -104,8 +173,8 @@
         left = node1.id, if1.id, sn1.id, sn1.vlan.id, sip1.ip
         right = node2.id, if2.id, sn2.id, sn2.vlan.id, sip2.ip
         expected = [
-            left + left + (space.id,),
-            right + right + (space.id,),
+            (*left, *left, space.id, 0),
+            (*right, *right, space.id, 0),
         ]
 
         with connection.cursor() as cursor:

=== modified file 'src/maasserver/tests/test_ntp.py'
--- src/maasserver/tests/test_ntp.py	2017-01-28 00:51:47 +0000
+++ src/maasserver/tests/test_ntp.py	2017-03-29 15:49:17 +0000
@@ -5,8 +5,6 @@
 
 __all__ = []
 
-from operator import methodcaller
-
 from maasserver.models.config import Config
 from maasserver.ntp import (
     get_peers_for,
@@ -14,10 +12,12 @@
 )
 from maasserver.testing.factory import factory
 from maasserver.testing.testcase import MAASServerTestCase
-from netaddr import IPAddress
+from netaddr import (
+    IPAddress,
+    IPSet,
+)
 from testtools.matchers import (
     AfterPreprocessing,
-    AllMatch,
     ContainsAll,
     Equals,
     HasLength,
@@ -231,7 +231,7 @@
 
     For racks, machines, and devices, a selection process takes place to
     determine which of several candidate addresses per server to choose. This
-    result is stable, i.e. it will choose the same address each time.
+    result is semi-stable, i.e. it will always prefer "closer" addresses.
     """
 
     scenarios = (
@@ -253,23 +253,31 @@
         super(TestGetServersFor_Selection, self).setUp()
         Config.objects.set_config("ntp_external_only", False)
 
-    def test_prefers_ipv6_to_ipv4_peers_then_highest_numerically(self):
+    def test_prefers_closest_addresses(self):
         subnet4 = factory.make_Subnet(version=4)
-        subnet6a = factory.make_Subnet(version=6)
-        subnet6b = factory.make_Subnet(version=6)
-        # Ensure that addresses in subnet6a < those in subnet6b.
-        subnet6a, subnet6b = sorted(
-            {subnet6a, subnet6b}, key=methodcaller("get_ipnetwork"))
-        # Create a node and server with an address in each subnet.
-        node, server = self.make_node(), self.make_server()
-        subnets = {subnet4, subnet6a, subnet6b}
-        populate_node_with_addresses(node, subnets)
-        populate_node_with_addresses(server, subnets)
+        subnet6 = factory.make_Subnet(version=6)
+        # Separate subnets but sharing the VLAN, hence routable.
+        subnet4v = factory.make_Subnet(version=4, vlan=subnet4.vlan)
+        subnet6v = factory.make_Subnet(version=6, vlan=subnet6.vlan)
+
+        # Create a node with an address in the first two subnets...
+        node = self.make_node()
+        populate_node_with_addresses(node, {subnet4, subnet6})
+        # ... and a server with an address in every subnet.
+        server = self.make_server()
+        populate_node_with_addresses(
+            server, {subnet4, subnet6, subnet4v, subnet6v})
+
+        # The NTP server addresses chosen will be those that are "closest" to
+        # the node, and same-subnet wins in this over same-VLAN. No additional
+        # preference is made between IPv4 or IPv6, hence we allow for either.
+        preferred_subnets = subnet4, subnet6
+        preferred_networks = IPSet(
+            subnet.get_ipnetwork() for subnet in preferred_subnets)
 
         servers = get_servers_for(node)
         self.assertThat(servers, Not(HasLength(0)))
-        self.assertThat(servers, AllMatch(IsIPv6Address))
-        self.assertThat(subnet6b.get_ipnetwork(), ContainsAll(servers))
+        self.assertThat(preferred_networks, ContainsAll(servers))
 
 
 class TestGetPeersFor_Region_RegionRack(MAASServerTestCase):
@@ -296,23 +304,37 @@
             get_peers_for(node2),
             IsSetOfServers({node1_address.ip}))
 
-    def test_prefers_ipv6_to_ipv4_peers_then_highest_numerically(self):
+    def test_prefers_closest_addresses(self):
         subnet4 = factory.make_Subnet(version=4)
-        subnet6a = factory.make_Subnet(version=6)
-        subnet6b = factory.make_Subnet(version=6)
-        # Ensure that addresses in subnet6a < those in subnet6b.
-        subnet6a, subnet6b = sorted(
-            {subnet6a, subnet6b}, key=methodcaller("get_ipnetwork"))
-        # Create some peers, each with an address in each subnet.
-        nodes = self.make_node(), self.make_node()
-        subnets = {subnet4, subnet6a, subnet6b}
-        for node in nodes:
-            populate_node_with_addresses(node, subnets)
-        for node in nodes:
+        subnet6 = factory.make_Subnet(version=6)
+        # Separate subnets but sharing the VLAN, hence routable.
+        subnet4v1 = factory.make_Subnet(version=4, vlan=subnet4.vlan)
+        subnet6v1 = factory.make_Subnet(version=6, vlan=subnet6.vlan)
+        subnet4v2 = factory.make_Subnet(version=4, vlan=subnet4.vlan)
+        subnet6v2 = factory.make_Subnet(version=6, vlan=subnet6.vlan)
+
+        # Create a node with an address in the first two subnets and the first
+        # two same-VLAN subnets.
+        node1 = self.make_node()
+        populate_node_with_addresses(
+            node1, {subnet4, subnet6, subnet4v1, subnet6v1})
+        # Create a node with an address in the first two subnets and the
+        # second two same-VLAN subnets.
+        node2 = self.make_node()
+        populate_node_with_addresses(
+            node2, {subnet4, subnet6, subnet4v2, subnet6v2})
+
+        # The NTP server addresses chosen will be those that are "closest" to
+        # the node, and same-subnet wins in this over same-VLAN. No additional
+        # preference is made between IPv4 or IPv6, hence we allow for either.
+        preferred_subnets = subnet4, subnet6
+        preferred_networks = IPSet(
+            subnet.get_ipnetwork() for subnet in preferred_subnets)
+
+        for node in (node1, node2):
             peers = get_peers_for(node)
             self.assertThat(peers, Not(HasLength(0)))
-            self.assertThat(peers, AllMatch(IsIPv6Address))
-            self.assertThat(subnet6b.get_ipnetwork(), ContainsAll(peers))
+            self.assertThat(preferred_networks, ContainsAll(peers))
 
 
 class TestGetPeersFor_Other(MAASServerTestCase):

=== modified file 'src/maasserver/tests/test_routablepairs.py'
--- src/maasserver/tests/test_routablepairs.py	2017-01-28 00:51:47 +0000
+++ src/maasserver/tests/test_routablepairs.py	2017-03-29 15:49:17 +0000
@@ -5,13 +5,21 @@
 
 __all__ = []
 
-from itertools import product
+from itertools import (
+    product,
+    takewhile,
+)
+import random
 
 from maasserver.models.node import Node
 from maasserver.routablepairs import find_addresses_between_nodes
 from maasserver.testing.factory import factory
 from maasserver.testing.testcase import MAASServerTestCase
 from testtools import ExpectedException
+from testtools.matchers import (
+    AfterPreprocessing,
+    Equals,
+)
 
 
 class TestFindAddressesBetweenNodes(MAASServerTestCase):
@@ -102,3 +110,124 @@
         # No routable addresses are found.
         self.assertItemsEqual(
             expected, find_addresses_between_nodes([node1], [node2]))
+
+    def gen_disjoint_networks(self):
+        """Generate disjoint networks.
+
+        Can be IPv4 or IPv6, but once generation has begun they'll all be the
+        same family.
+        """
+        make_network = random.choice([
+            factory.make_ipv4_network,
+            factory.make_ipv6_network]
+        )
+        networks = []
+        while True:
+            network = make_network(disjoint_from=networks)
+            networks.append(network)
+            yield network
+
+    def test__yields_routes_with_lowest_metrics_first(self):
+        space = factory.make_Space()
+        # Ensure networks are disjoint but of the same family.
+        networks = self.gen_disjoint_networks()
+
+        # Create the node for the "left" that has two IP addresses, one in the
+        # null space, one in a non-null space.
+        origin = factory.make_Node(hostname="origin")
+        origin_iface = factory.make_Interface(
+            node=origin, disconnected=True)
+        origin_subnet = factory.make_Subnet(
+            space=space, cidr=next(networks))
+        origin_subnet_null_space = factory.make_Subnet(
+            space=None, cidr=next(networks))
+        origin_sip = factory.make_StaticIPAddress(
+            interface=origin_iface, subnet=origin_subnet)
+        origin_sip_null_space = factory.make_StaticIPAddress(
+            interface=origin_iface, subnet=origin_subnet_null_space)
+
+        # Same subnet, different node.
+        node_same_subnet = factory.make_Node(hostname="same-subnet")
+        sip_same_subnet = factory.make_StaticIPAddress(
+            interface=factory.make_Interface(
+                node=node_same_subnet, disconnected=True),
+            subnet=origin_subnet)
+
+        # Same VLAN, different subnet, different node.
+        node_same_vlan = factory.make_Node(hostname="same-vlan")
+        sip_same_vlan = factory.make_StaticIPAddress(
+            interface=factory.make_Interface(
+                node=node_same_vlan, disconnected=True),
+            subnet=factory.make_Subnet(
+                space=space, vlan=origin_subnet.vlan,
+                cidr=next(networks)))
+
+        # Same space, different VLAN, subnet, and node.
+        node_same_space = factory.make_Node(hostname="same-space")
+        sip_same_space = factory.make_StaticIPAddress(
+            interface=factory.make_Interface(
+                node=node_same_space, disconnected=True),
+            subnet=factory.make_Subnet(
+                space=space, cidr=next(networks)))
+
+        # Null space, different VLAN, subnet, and node.
+        node_null_space = factory.make_Node(hostname="null-space")
+        sip_null_space = factory.make_StaticIPAddress(
+            interface=factory.make_Interface(
+                node=node_null_space, disconnected=True),
+            subnet=factory.make_Subnet(
+                space=None, cidr=next(networks)))
+
+        # We'll search for routes between `lefts` and `rights`.
+        lefts = [
+            origin,
+        ]
+        rights = [
+            node_same_subnet,
+            node_same_vlan,
+            node_same_space,
+            node_null_space,
+        ]
+
+        # This is in order, lowest "metric" first.
+        expected = [
+            (origin, origin_sip.get_ipaddress(),
+             node_same_subnet, sip_same_subnet.get_ipaddress()),
+            (origin, origin_sip.get_ipaddress(),
+             node_same_vlan, sip_same_vlan.get_ipaddress()),
+            (origin, origin_sip.get_ipaddress(),
+             node_same_space, sip_same_space.get_ipaddress()),
+            (origin, origin_sip_null_space.get_ipaddress(),
+             node_null_space, sip_null_space.get_ipaddress()),
+        ]
+        self.assertThat(
+            find_addresses_between_nodes(lefts, rights),
+            AfterPreprocessing(list, Equals(expected)))
+
+        # Same node, same space, different VLAN and subnet. We did not add
+        # this earlier because its existence allows for a large number of
+        # additional routes between the origin and the other nodes, which
+        # would have obscured the test.
+        origin_sip_2 = factory.make_StaticIPAddress(
+            interface=factory.make_Interface(
+                node=origin, disconnected=True),
+            subnet=factory.make_Subnet(
+                space=space, cidr=next(networks)))
+
+        # Now the first addresses returned are between those addresses we
+        # created on the same node, in no particular order.
+        origin_ips = origin_sip.get_ipaddress(), origin_sip_2.get_ipaddress()
+        expected_mutual = {
+            (origin, ip1, origin, ip2)
+            for ip1, ip2 in product(origin_ips, origin_ips)
+        }
+        # There's a mutual route for the null-space IP address too.
+        expected_mutual.add(
+            (origin, origin_sip_null_space.get_ipaddress(),
+             origin, origin_sip_null_space.get_ipaddress()))
+        observed_mutual = takewhile(
+            (lambda route: route[0] == route[2]),  # Route is mutual.
+            find_addresses_between_nodes(lefts, [origin, *rights]),
+        )
+        self.assertItemsEqual(
+            expected_mutual, observed_mutual)