Merge pull request #3201 from vespa-engine/smorgrav/headroom_allocation_fix

Allocation headroom fixes

8 files changed, 348 insertions, 75 deletions

diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/DockerHostCapacity.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/DockerHostCapacity.java
index 77d91c7bea7..78ea258107b 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/DockerHostCapacity.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/DockerHostCapacity.java
@@ -65,12 +65,12 @@ public class DockerHostCapacity {
      * Checks the node capacity and free ip addresses to see
      * if we could allocate a flavor on the docker host.
      */
-    boolean hasCapacity(Node dockerHost, Flavor flavor) {
-        return freeCapacityOf(dockerHost, false).hasCapacityFor(flavor) && freeIPs(dockerHost) > 0;
+    boolean hasCapacity(Node dockerHost, ResourceCapacity requestedCapacity) {
+        return freeCapacityOf(dockerHost, false).hasCapacityFor(requestedCapacity) && freeIPs(dockerHost) > 0;
     }
 
-    boolean hasCapacityWhenRetiredAndInactiveNodesAreGone(Node dockerHost, Flavor flavor) {
-        return freeCapacityOf(dockerHost, true).hasCapacityFor(flavor) && freeIPs(dockerHost) > 0;
+    boolean hasCapacityWhenRetiredAndInactiveNodesAreGone(Node dockerHost, ResourceCapacity requestedCapacity) {
+        return freeCapacityOf(dockerHost, true).hasCapacityFor(requestedCapacity) && freeIPs(dockerHost) > 0;
     }
 
     /**
@@ -105,7 +105,7 @@ public class DockerHostCapacity {
     public long getNofHostsAvailableFor(Flavor flavor) {
         return allNodes.asList().stream()
                 .filter(n -> n.type().equals(NodeType.host))
-                .filter(n -> hasCapacity(n, flavor))
+                .filter(n -> hasCapacity(n, ResourceCapacity.of(flavor)))
                 .count();
     }
 
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodePrioritizer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodePrioritizer.java
index 960d0b9d729..1ac86ad9f4b 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodePrioritizer.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodePrioritizer.java
@@ -30,7 +30,7 @@ import java.util.stream.Collectors;
  *
  * @author smorgrav
  */
-public class NodePrioritizer {
+class NodePrioritizer {
 
     private final Map<Node, PrioritizableNode> nodes = new HashMap<>();
     private final List<Node> allNodes;
@@ -39,10 +39,10 @@ public class NodePrioritizer {
     private final ApplicationId appId;
     private final ClusterSpec clusterSpec;
 
+    private final boolean isDocker;
     private final boolean isAllocatingForReplacement;
     private final Set<Node> spareHosts;
-    private final Map<Node, Boolean> headroomHosts;
-    private final boolean isDocker;
+    private final Map<Node, ResourceCapacity> headroomHosts;
 
     NodePrioritizer(List<Node> allNodes, ApplicationId appId, ClusterSpec clusterSpec, NodeSpec nodeSpec, NodeFlavors nodeFlavors, int spares) {
         this.allNodes = Collections.unmodifiableList(allNodes);
@@ -50,8 +50,8 @@ public class NodePrioritizer {
         this.clusterSpec = clusterSpec;
         this.appId = appId;
 
-        spareHosts = findSpareHosts(allNodes, spares);
-        headroomHosts = findHeadroomHosts(allNodes, spareHosts, nodeFlavors);
+        this.spareHosts = findSpareHosts(allNodes, spares);
+        this.headroomHosts = findHeadroomHosts(allNodes, spareHosts, nodeFlavors);
 
         this.capacity = new DockerHostCapacity(allNodes);
 
@@ -68,14 +68,14 @@ public class NodePrioritizer {
                 .filter(node -> node.allocation().get().membership().cluster().id().equals(clusterSpec.id()))
                 .count();
 
-        isAllocatingForReplacement = isReplacement(nofNodesInCluster, nofFailedNodes);
-        isDocker = isDocker();
+        this.isAllocatingForReplacement = isReplacement(nofNodesInCluster, nofFailedNodes);
+        this.isDocker = isDocker();
     }
 
     /**
      * From ipAddress - get hostname
      *
-     * @return hostname or null if not able to do the loopup
+     * @return hostname or null if not able to do the lookup
      */
     private static String lookupHostname(String ipAddress) {
         try {
@@ -104,14 +104,14 @@ public class NodePrioritizer {
     }
 
     /**
-     * Headroom are the nodes with the least but sufficient space for the requested headroom.
+     * Headroom hosts are the host with the least but sufficient capacity for the requested headroom.
      *
-     * If not enough headroom - the headroom violating hosts are the once that are closest to fulfull
+     * If not enough headroom - the headroom violating hosts are the once that are closest to fulfill
      * a headroom request.
      */
-    private static Map<Node, Boolean> findHeadroomHosts(List<Node> nodes, Set<Node> spareNodes, NodeFlavors flavors) {
+    private static Map<Node, ResourceCapacity> findHeadroomHosts(List<Node> nodes, Set<Node> spareNodes, NodeFlavors flavors) {
         DockerHostCapacity capacity = new DockerHostCapacity(nodes);
-        Map<Node, Boolean> headroomNodesToViolation = new HashMap<>();
+        Map<Node, ResourceCapacity> headroomHosts = new HashMap<>();
 
         List<Node> hostsSortedOnLeastCapacity = nodes.stream()
                 .filter(n -> !spareNodes.contains(n))
@@ -121,20 +121,25 @@ public class NodePrioritizer {
                 .sorted((a, b) -> capacity.compareWithoutInactive(b, a))
                 .collect(Collectors.toList());
 
+        // For all flavors with ideal headroom - find which hosts this headroom should be allocated to
         for (Flavor flavor : flavors.getFlavors().stream().filter(f -> f.getIdealHeadroom() > 0).collect(Collectors.toList())) {
             Set<Node> tempHeadroom = new HashSet<>();
             Set<Node> notEnoughCapacity = new HashSet<>();
+
+            ResourceCapacity headroomCapacity = ResourceCapacity.of(flavor);
+
+            // Select hosts that has available capacity for both headroom and for new allocations
             for (Node host : hostsSortedOnLeastCapacity) {
-                if (headroomNodesToViolation.containsKey(host)) continue;
-                if (capacity.hasCapacityWhenRetiredAndInactiveNodesAreGone(host, flavor)) {
-                    headroomNodesToViolation.put(host, false);
+                if (headroomHosts.containsKey(host)) continue;
+                if (capacity.hasCapacityWhenRetiredAndInactiveNodesAreGone(host, headroomCapacity)) {
+                    headroomHosts.put(host, headroomCapacity);
                     tempHeadroom.add(host);
                 } else {
                     notEnoughCapacity.add(host);
                 }
 
                 if (tempHeadroom.size() == flavor.getIdealHeadroom()) {
-                    continue;
+                    break;
                 }
             }
 
@@ -145,14 +150,13 @@ public class NodePrioritizer {
                         .limit(flavor.getIdealHeadroom() - tempHeadroom.size())
                         .collect(Collectors.toList());
 
-                for (Node nodeViolatingHeadrom : violations) {
-                    headroomNodesToViolation.put(nodeViolatingHeadrom, true);
+                for (Node hostViolatingHeadrom : violations) {
+                    headroomHosts.put(hostViolatingHeadrom, headroomCapacity);
                 }
-
             }
         }
 
-        return headroomNodesToViolation;
+        return headroomHosts;
     }
 
     /**
@@ -197,14 +201,14 @@ public class NodePrioritizer {
                     }
                 }
 
-                if (!conflictingCluster && capacity.hasCapacity(node, getFlavor())) {
+                if (!conflictingCluster && capacity.hasCapacity(node, ResourceCapacity.of(getFlavor(requestedNodes)))) {
                     Set<String> ipAddresses = DockerHostCapacity.findFreeIps(node, allNodes);
                     if (ipAddresses.isEmpty()) continue;
                     String ipAddress = ipAddresses.stream().findFirst().get();
                     String hostname = lookupHostname(ipAddress);
                     if (hostname == null) continue;
                     Node newNode = Node.createDockerNode("fake-" + hostname, Collections.singleton(ipAddress),
-                            Collections.emptySet(), hostname, Optional.of(node.hostname()), getFlavor(), NodeType.tenant);
+                            Collections.emptySet(), hostname, Optional.of(node.hostname()), getFlavor(requestedNodes), NodeType.tenant);
                     PrioritizableNode nodePri = toNodePriority(newNode, false, true);
                     if (!nodePri.violatesSpares || isAllocatingForReplacement) {
                         nodes.put(newNode, nodePri);
@@ -249,7 +253,7 @@ public class NodePrioritizer {
         pri.node = node;
         pri.isSurplusNode = isSurplusNode;
         pri.isNewNode = isNewNode;
-        pri.preferredOnFlavor = requestedNodes.specifiesNonStockFlavor() && node.flavor().equals(getFlavor());
+        pri.preferredOnFlavor = requestedNodes.specifiesNonStockFlavor() && node.flavor().equals(getFlavor(requestedNodes));
         pri.parent = findParentNode(node);
 
         if (pri.parent.isPresent()) {
@@ -260,14 +264,29 @@ public class NodePrioritizer {
                 pri.violatesSpares = true;
             }
 
-            if (headroomHosts.containsKey(parent)) {
-                pri.violatesHeadroom = headroomHosts.get(parent);
+            if (headroomHosts.containsKey(parent) && isPreferredNodeToBeReloacted(allNodes, node, parent)) {
+                ResourceCapacity neededCapacity = headroomHosts.get(parent);
+
+                // If the node is new then we need to check the headroom requirement after it has been added
+                if (isNewNode) {
+                    neededCapacity = ResourceCapacity.composite(neededCapacity, new ResourceCapacity(node));
+                }
+                pri.violatesHeadroom = !capacity.hasCapacity(parent, neededCapacity);
             }
         }
 
         return pri;
     }
 
+    static boolean isPreferredNodeToBeReloacted(List<Node> nodes, Node node, Node parent) {
+        NodeList list = new NodeList(nodes);
+        return list.childNodes(parent).asList().stream()
+                .sorted(NodePrioritizer::compareForRelocation)
+                .findFirst()
+                .filter(n -> n.equals(node))
+                .isPresent();
+    }
+
     private boolean isReplacement(long nofNodesInCluster, long nodeFailedNodes) {
         if (nodeFailedNodes == 0) return false;
 
@@ -280,7 +299,7 @@ public class NodePrioritizer {
         return (wantedCount > nofNodesInCluster - nodeFailedNodes);
     }
 
-    private Flavor getFlavor() {
+    private static Flavor getFlavor(NodeSpec requestedNodes) {
         if (requestedNodes instanceof NodeSpec.CountNodeSpec) {
             NodeSpec.CountNodeSpec countSpec = (NodeSpec.CountNodeSpec) requestedNodes;
             return countSpec.getFlavor();
@@ -289,7 +308,7 @@ public class NodePrioritizer {
     }
 
     private boolean isDocker() {
-        Flavor flavor = getFlavor();
+        Flavor flavor = getFlavor(requestedNodes);
         return (flavor != null) && flavor.getType().equals(Flavor.Type.DOCKER_CONTAINER);
     }
 
@@ -299,4 +318,27 @@ public class NodePrioritizer {
                 .filter(n -> n.hostname().equals(node.parentHostname().orElse(" NOT A NODE")))
                 .findAny();
     }
+
+    private static int compareForRelocation(Node a, Node b) {
+        // Choose smallest node
+        int capacity = ResourceCapacity.of(a).compare(ResourceCapacity.of(b));
+        if (capacity != 0) return capacity;
+
+        // Choose unallocated over allocated (this case is when we have ready docker nodes)
+        if (!a.allocation().isPresent() && b.allocation().isPresent()) return -1;
+        if (a.allocation().isPresent() && !b.allocation().isPresent()) return 1;
+
+        // Choose container over content nodes
+        if (a.allocation().isPresent() && a.allocation().isPresent()) {
+            if (a.allocation().get().membership().cluster().type().equals(ClusterSpec.Type.container) &&
+                    !b.allocation().get().membership().cluster().type().equals(ClusterSpec.Type.container))
+                return -1;
+            if (!a.allocation().get().membership().cluster().type().equals(ClusterSpec.Type.container) &&
+                    b.allocation().get().membership().cluster().type().equals(ClusterSpec.Type.container))
+                return 1;
+        }
+
+        // To get a stable algorithm - choose lexicographical from hostname
+        return a.hostname().compareTo(b.hostname());
+    }
 }
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/PrioritizableNode.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/PrioritizableNode.java
index 06acd646ea7..807fbfae1c9 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/PrioritizableNode.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/PrioritizableNode.java
@@ -23,7 +23,7 @@ class PrioritizableNode implements Comparable<PrioritizableNode> {
     /** True if the node is allocated to a host that should be dedicated as a spare */
     boolean violatesSpares;
 
-    /** True if the node is allocated on slots that should be dedicated to headroom */
+    /** True if the node is (or would be) allocated on slots that should be dedicated to headroom */
     boolean violatesHeadroom;
 
     /** True if this is a node that has been retired earlier in the allocation process */
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/ResourceCapacity.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/ResourceCapacity.java
index fdec29d5b97..8373cf9e17f 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/ResourceCapacity.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/ResourceCapacity.java
@@ -28,6 +28,18 @@ public class ResourceCapacity {
         disk = node.flavor().getMinDiskAvailableGb();
     }
 
+    static ResourceCapacity of(Flavor flavor) {
+        ResourceCapacity capacity = new ResourceCapacity();
+        capacity.memory = flavor.getMinMainMemoryAvailableGb();
+        capacity.cpu = flavor.getMinCpuCores();
+        capacity.disk = flavor.getMinDiskAvailableGb();
+        return capacity;
+    }
+
+    static ResourceCapacity of(Node node) {
+        return new ResourceCapacity(node);
+    }
+
     public double getMemory() {
         return memory;
     }
@@ -40,6 +52,15 @@ public class ResourceCapacity {
         return disk;
     }
 
+    static ResourceCapacity composite(ResourceCapacity a, ResourceCapacity b) {
+        ResourceCapacity composite = new ResourceCapacity();
+        composite.memory = a.memory + b.memory;
+        composite.cpu -= a.cpu + b.cpu;
+        composite.disk -=  a.disk + b.disk;
+
+        return composite;
+    }
+
     void subtract(Node node) {
         memory -= node.flavor().getMinMainMemoryAvailableGb();
         cpu -= node.flavor().getMinCpuCores();
@@ -54,14 +75,18 @@ public class ResourceCapacity {
         return result;
     }
 
+    boolean hasCapacityFor(ResourceCapacity capacity) {
+        return memory >= capacity.memory &&
+                cpu >= capacity.cpu &&
+                disk >= capacity.disk;
+    }
+
     boolean hasCapacityFor(Flavor flavor) {
-        return memory >= flavor.getMinMainMemoryAvailableGb() &&
-                cpu >= flavor.getMinCpuCores() &&
-                disk >= flavor.getMinDiskAvailableGb();
+        return hasCapacityFor(ResourceCapacity.of(flavor));
     }
 
     int freeCapacityInFlavorEquivalence(Flavor flavor) {
-        if (!hasCapacityFor(flavor)) return 0;
+        if (!hasCapacityFor(ResourceCapacity.of(flavor))) return 0;
 
         double memoryFactor = Math.floor(memory/flavor.getMinMainMemoryAvailableGb());
         double cpuFactor = Math.floor(cpu/flavor.getMinCpuCores());
@@ -85,11 +110,4 @@ public class ResourceCapacity {
         if (cpu < that.cpu) return -1;
         return 0;
     }
-
-    Flavor asFlavor() {
-        FlavorConfigBuilder b = new FlavorConfigBuilder();
-        b.addFlavor("spareflavor", cpu, memory, disk, Flavor.Type.DOCKER_CONTAINER).idealHeadroom(1);
-        return new Flavor(b.build().flavor(0));
-    }
-
 }
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DockerHostCapacityTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DockerHostCapacityTest.java
index 55e1ff8de9f..dce9f694647 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DockerHostCapacityTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DockerHostCapacityTest.java
@@ -72,20 +72,20 @@ public class DockerHostCapacityTest {
 
     @Test
     public void hasCapacity() {
-        assertTrue(capacity.hasCapacity(host1, flavorDocker));
-        assertTrue(capacity.hasCapacity(host1, flavorDocker2));
-        assertTrue(capacity.hasCapacity(host2, flavorDocker));
-        assertTrue(capacity.hasCapacity(host2, flavorDocker2));
-        assertFalse(capacity.hasCapacity(host3, flavorDocker));  // No ip available
-        assertFalse(capacity.hasCapacity(host3, flavorDocker2)); // No ip available
+        assertTrue(capacity.hasCapacity(host1, ResourceCapacity.of(flavorDocker)));
+        assertTrue(capacity.hasCapacity(host1, ResourceCapacity.of(flavorDocker2)));
+        assertTrue(capacity.hasCapacity(host2, ResourceCapacity.of(flavorDocker)));
+        assertTrue(capacity.hasCapacity(host2, ResourceCapacity.of(flavorDocker2)));
+        assertFalse(capacity.hasCapacity(host3, ResourceCapacity.of(flavorDocker)));  // No ip available
+        assertFalse(capacity.hasCapacity(host3, ResourceCapacity.of(flavorDocker2))); // No ip available
 
         // Add a new node to host1 to deplete the memory resource
         Node nodeF = Node.create("nodeF", Collections.singleton("::6"), Collections.emptySet(),
                 "nodeF", Optional.of("host1"), flavorDocker, NodeType.tenant);
         nodes.add(nodeF);
         capacity = new DockerHostCapacity(nodes);
-        assertFalse(capacity.hasCapacity(host1, flavorDocker));
-        assertFalse(capacity.hasCapacity(host1, flavorDocker2));
+        assertFalse(capacity.hasCapacity(host1, ResourceCapacity.of(flavorDocker)));
+        assertFalse(capacity.hasCapacity(host1, ResourceCapacity.of(flavorDocker2)));
     }
 
     @Test
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicDockerProvisioningTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicDockerProvisioningTest.java
index f2b5624d3b8..c26865d5690 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicDockerProvisioningTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicDockerProvisioningTest.java
@@ -48,18 +48,17 @@ public class DynamicDockerProvisioningTest {
 
     /**
      * Test relocation of nodes that violate headroom.
-     *
+     * <p>
      * Setup 4 docker hosts and allocate one container on each (from two different applications)
      * No spares - only headroom (4xd-2)
-     *
+     * <p>
      * One application is now violating headroom and need relocation
-     *
-     *  Initial allocation of app 1 and 2 --> final allocation (headroom marked as H):
-     *
+     * <p>
+     * Initial allocation of app 1 and 2 --> final allocation (headroom marked as H):
+     * <p>
      * | H  |  H  | H   | H   |        |    |    |    |    |
      * | H  |  H  | H1a | H1b |   -->  |    |    |    |    |
      * |    |     | 2a  | 2b  |        | 1a | 1b | 2a | 2b |
-     *
      */
     @Test
     public void relocate_nodes_from_headroom_hosts() {
@@ -97,18 +96,17 @@ public class DynamicDockerProvisioningTest {
 
     /**
      * Test relocation of nodes from spare hosts.
-     *
+     * <p>
      * Setup 4 docker hosts and allocate one container on each (from two different applications)
      * No headroom defined - only 2 spares.
-     *
+     * <p>
      * Check that it relocates containers away from the 2 spares
-     *
-     *  Initial allocation of app 1 and 2 --> final allocation:
-     *
+     * <p>
+     * Initial allocation of app 1 and 2 --> final allocation:
+     * <p>
      * |    |    |    |    |        |    |    |    |    |
      * |    |    |    |    |   -->  | 2a | 2b |    |    |
      * | 1a | 1b | 2a | 2b |        | 1a | 1b |    |    |
-     *
      */
     @Test
     public void relocate_nodes_from_spare_hosts() {
@@ -146,8 +144,136 @@ public class DynamicDockerProvisioningTest {
     }
 
     /**
-     * Test an allocation workflow:
+     * Test that new docker nodes that will result in headroom violations are
+     * correctly marked as this.
+     * <p>
+     * When redeploying app1 - should not do anything (as moving app1 to host 0 and 1 would violate headroom).
+     * Then redeploy app 2 - should cause a relocation.
+     * <p>
+     * | H  |  H  | H2a  | H2b  |         | H  |  H  |  H    |  H    |
+     * | H  |  H  | H1a  | H1b  |  -->    | H  |  H  |  H1a  |  H1b  |
+     * |    |     |  1a  |  1b  |         | 2a | 2b  |  1a   |  1b   |
+     */
+    @Test
+    public void new_docker_nodes_are_marked_as_headroom_violations() {
+        ProvisioningTester tester = new ProvisioningTester(new Zone(Environment.perf, RegionName.from("us-east")), flavorsConfig(true));
+        enableDynamicAllocation(tester);
+        tester.makeReadyNodes(4, "host", "host-small", NodeType.host, 32);
+        deployZoneApp(tester);
+        List<Node> dockerHosts = tester.nodeRepository().getNodes(NodeType.host, Node.State.active);
+        Flavor flavorD2 = tester.nodeRepository().getAvailableFlavors().getFlavorOrThrow("d-2");
+        Flavor flavorD1 = tester.nodeRepository().getAvailableFlavors().getFlavorOrThrow("d-1");
+
+        // Application 1
+        ApplicationId application1 = makeApplicationId("t1", "1");
+        ClusterSpec clusterSpec1 = ClusterSpec.request(ClusterSpec.Type.content, ClusterSpec.Id.from("myContent"), Version.fromString("6.100"));
+        String hostParent2 = dockerHosts.get(2).hostname();
+        String hostParent3 = dockerHosts.get(3).hostname();
+        addAndAssignNode(application1, "1a", hostParent2, flavorD2, 0, tester);
+        addAndAssignNode(application1, "1b", hostParent3, flavorD2, 1, tester);
+
+        // Application 2
+        ApplicationId application2 = makeApplicationId("t2", "2");
+        ClusterSpec clusterSpec2 = ClusterSpec.request(ClusterSpec.Type.content, ClusterSpec.Id.from("myContent"), Version.fromString("6.100"));
+        addAndAssignNode(application2, "2a", hostParent2, flavorD1, 0, tester);
+        addAndAssignNode(application2, "2b", hostParent3, flavorD1, 1, tester);
+
+        // Assert allocation placement - prior to re-deployment
+        assertApplicationHosts(tester.nodeRepository().getNodes(application1), hostParent2, hostParent3);
+        assertApplicationHosts(tester.nodeRepository().getNodes(application2), hostParent2, hostParent3);
+
+        // Redeploy application 1
+        deployapp(application1, clusterSpec1, flavorD2, tester, 2);
+
+        // Re-assert allocation placement
+        assertApplicationHosts(tester.nodeRepository().getNodes(application1), hostParent2, hostParent3);
+        assertApplicationHosts(tester.nodeRepository().getNodes(application2), hostParent2, hostParent3);
+
+        // Redeploy application 2
+        deployapp(application2, clusterSpec2, flavorD1, tester, 2);
+
+        // Now app2 should have re-located
+        assertApplicationHosts(tester.nodeRepository().getNodes(application1), hostParent2, hostParent3);
+        assertApplicationHosts(tester.nodeRepository().getNodes(application2), dockerHosts.get(0).hostname(), dockerHosts.get(1).hostname());
+    }
+
+    /**
+     * Test that we only relocate the smallest nodes from a host to free up headroom.
+     * <p>
+     * The reason we want to do this is that it is an cheap approximation for the optimal solution as we
+     * pick headroom to be on the hosts were we are closest to fulfill the headroom requirement.
      *
+     * Both applications could be moved here to free up headroom - but we want app2 (which is smallest) to be moved.
+     * <p>
+     * | H  |  H  | H2a  | H2b  |         | H  |  H  |  H    |  H    |
+     * | H  |  H  | H1a  | H1b  |  -->    | H  |  H  |  H    |  H    |
+     * |    |     |  1a  |  1b  |         | 2a | 2b  |  1a   |  1b   |
+     * |    |     |      |      |         |    |     |  1a   |  1b   |
+     */
+    @Test
+    public void only_preferred_container_is_moved_from_hosts_with_headroom_violations() {
+        ProvisioningTester tester = new ProvisioningTester(new Zone(Environment.perf, RegionName.from("us-east")), flavorsConfig(true));
+        enableDynamicAllocation(tester);
+        tester.makeReadyNodes(4, "host", "host-medium", NodeType.host, 32);
+        deployZoneApp(tester);
+        List<Node> dockerHosts = tester.nodeRepository().getNodes(NodeType.host, Node.State.active);
+        Flavor flavorD2 = tester.nodeRepository().getAvailableFlavors().getFlavorOrThrow("d-2");
+        Flavor flavorD1 = tester.nodeRepository().getAvailableFlavors().getFlavorOrThrow("d-1");
+
+        // Application 1
+        ApplicationId application1 = makeApplicationId("t1", "1");
+        ClusterSpec clusterSpec1 = ClusterSpec.request(ClusterSpec.Type.content, ClusterSpec.Id.from("myContent"), Version.fromString("6.100"));
+        String hostParent2 = dockerHosts.get(2).hostname();
+        String hostParent3 = dockerHosts.get(3).hostname();
+        addAndAssignNode(application1, "1a", hostParent2, flavorD2, 0, tester);
+        addAndAssignNode(application1, "1b", hostParent3, flavorD2, 1, tester);
+
+        // Application 2
+        ApplicationId application2 = makeApplicationId("t2", "2");
+        ClusterSpec clusterSpec2 = ClusterSpec.request(ClusterSpec.Type.content, ClusterSpec.Id.from("myContent"), Version.fromString("6.100"));
+        addAndAssignNode(application2, "2a", hostParent2, flavorD1, 0, tester);
+        addAndAssignNode(application2, "2b", hostParent3, flavorD1, 1, tester);
+
+        // Assert allocation placement - prior to re-deployment
+        assertApplicationHosts(tester.nodeRepository().getNodes(application1), hostParent2, hostParent3);
+        assertApplicationHosts(tester.nodeRepository().getNodes(application2), hostParent2, hostParent3);
+
+        // Redeploy application 1
+        deployapp(application1, clusterSpec1, flavorD2, tester, 2);
+
+        // Re-assert allocation placement
+        assertApplicationHosts(tester.nodeRepository().getNodes(application1), hostParent2, hostParent3);
+        assertApplicationHosts(tester.nodeRepository().getNodes(application2), hostParent2, hostParent3);
+
+        // Redeploy application 2
+        deployapp(application2, clusterSpec2, flavorD1, tester, 2);
+
+        // Now app2 should have re-located
+        assertApplicationHosts(tester.nodeRepository().getNodes(application1), hostParent2, hostParent3);
+        assertApplicationHosts(tester.nodeRepository().getNodes(application2), dockerHosts.get(0).hostname(), dockerHosts.get(1).hostname());
+    }
+
+    private void assertApplicationHosts(List<Node> nodes, String... parents) {
+        for (Node node : nodes) {
+            // Ignore retired and non-active nodes
+            if (!node.state().equals(Node.State.active) ||
+                    node.allocation().get().membership().retired()) {
+                continue;
+            }
+            boolean found = false;
+            for (String parent : parents) {
+                if (node.parentHostname().get().equals(parent)) {
+                    found = true;
+                    break;
+                }
+            }
+            Assert.assertTrue(found);
+        }
+    }
+
+    /**
+     * Test an allocation workflow:
+     * <p>
      * 5 Hosts of capacity 3 (2 spares)
      * - Allocate app with 3 nodes
      * - Allocate app with 2 nodes
@@ -195,23 +321,22 @@ public class DynamicDockerProvisioningTest {
             numberOfChildrenStat.put(nofChildren, numberOfChildrenStat.get(nofChildren) + 1);
         }
 
-        assertEquals(3l, (long)numberOfChildrenStat.get(3));
-        assertEquals(1l, (long)numberOfChildrenStat.get(0));
-        assertEquals(1l, (long)numberOfChildrenStat.get(1));
+        assertEquals(3l, (long) numberOfChildrenStat.get(3));
+        assertEquals(1l, (long) numberOfChildrenStat.get(0));
+        assertEquals(1l, (long) numberOfChildrenStat.get(1));
     }
 
     /**
      * Test redeployment of nodes that violates spare headroom - but without alternatives
-     *
+     * <p>
      * Setup 2 docker hosts and allocate one app with a container on each
      * No headroom defined - only 2 spares.
-     *
+     * <p>
      * Initial allocation of app 1 --> final allocation:
-     *
+     * <p>
      * |    |    |        |    |    |
      * |    |    |   -->  |    |    |
      * | 1a | 1b |        | 1a | 1b |
-     *
      */
     @Test
     public void do_not_relocate_nodes_from_spare_if_no_where_to_reloacte_them() {
@@ -341,15 +466,15 @@ public class DynamicDockerProvisioningTest {
     }
 
     private void deployapp(ApplicationId id, ClusterSpec spec, Flavor flavor, ProvisioningTester tester, int nodecount) {
-        List<HostSpec> hostSpec = tester.prepare(id, spec, nodecount,1, flavor.canonicalName());
+        List<HostSpec> hostSpec = tester.prepare(id, spec, nodecount, 1, flavor.canonicalName());
         tester.activate(id, new HashSet<>(hostSpec));
     }
 
     private Node addAndAssignNode(ApplicationId id, String hostname, String parentHostname, Flavor flavor, int index, ProvisioningTester tester) {
         Node node1a = Node.create("open1", Collections.singleton("127.0.0.100"), new HashSet<>(), hostname, Optional.of(parentHostname), flavor, NodeType.tenant);
         ClusterSpec clusterSpec = ClusterSpec.request(ClusterSpec.Type.content, ClusterSpec.Id.from("myContent"), Version.fromString("6.100")).changeGroup(Optional.of(ClusterSpec.Group.from(0)));
-        ClusterMembership clusterMembership1 = ClusterMembership.from(clusterSpec,index);
-        Node node1aAllocation = node1a.allocate(id,clusterMembership1, Instant.now());
+        ClusterMembership clusterMembership1 = ClusterMembership.from(clusterSpec, index);
+        Node node1aAllocation = node1a.allocate(id, clusterMembership1, Instant.now());
 
         tester.nodeRepository().addNodes(Collections.singletonList(node1aAllocation));
         NestedTransaction transaction = new NestedTransaction().add(new CuratorTransaction(tester.getCurator()));
@@ -372,6 +497,7 @@ public class DynamicDockerProvisioningTest {
         FlavorConfigBuilder b = new FlavorConfigBuilder();
         b.addFlavor("host-large", 6., 6., 6, Flavor.Type.BARE_METAL);
         b.addFlavor("host-small", 3., 3., 3, Flavor.Type.BARE_METAL);
+        b.addFlavor("host-medium", 4., 4., 4, Flavor.Type.BARE_METAL);
         b.addFlavor("d-1", 1, 1., 1, Flavor.Type.DOCKER_CONTAINER);
         b.addFlavor("d-2", 2, 2., 2, Flavor.Type.DOCKER_CONTAINER);
         if (includeHeadroom) {
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/NodePrioritizerTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/NodePrioritizerTest.java
new file mode 100644
index 00000000000..407101c7b8b
--- /dev/null
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/NodePrioritizerTest.java
@@ -0,0 +1,86 @@
+package com.yahoo.vespa.hosted.provision.provisioning;// Copyright 2017 Yahoo Holdings. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+
+import com.yahoo.component.Version;
+import com.yahoo.config.provision.ApplicationId;
+import com.yahoo.config.provision.ClusterMembership;
+import com.yahoo.config.provision.ClusterSpec;
+import com.yahoo.config.provision.Flavor;
+import com.yahoo.config.provision.NodeFlavors;
+import com.yahoo.config.provision.NodeType;
+import com.yahoo.config.provisioning.FlavorsConfig;
+import com.yahoo.vespa.hosted.provision.Node;
+import org.junit.Assert;
+import org.junit.Test;
+
+import java.time.Instant;
+import java.util.ArrayList;
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Optional;
+
+/**
+ * @author smorgrav
+ */
+public class NodePrioritizerTest {
+
+    private static NodeFlavors flavors = new NodeFlavors(flavorsConfig());
+
+    @Test
+    public void relocated_nodes_are_preferred() {
+        List<Node> nodes = new ArrayList<>();
+        Node parent = createParent("parent");
+        Node b = createNode(parent, "b", "d2");
+        nodes.add(b);
+
+        // Only one node - should be obvious what to prefer
+        Assert.assertTrue(NodePrioritizer.isPreferredNodeToBeReloacted(nodes, b, parent));
+
+        // Two equal nodes - choose lexically
+        Node a = createNode(parent, "a", "d2");
+        nodes.add(a);
+        Assert.assertTrue(NodePrioritizer.isPreferredNodeToBeReloacted(nodes, a, parent));
+        Assert.assertFalse(NodePrioritizer.isPreferredNodeToBeReloacted(nodes, b, parent));
+
+        // Smallest node should be preferred
+        Node c = createNode(parent, "c", "d1");
+        nodes.add(c);
+        Assert.assertTrue(NodePrioritizer.isPreferredNodeToBeReloacted(nodes, c, parent));
+
+        // Unallocated over allocated
+        ClusterSpec spec = ClusterSpec.from(ClusterSpec.Type.container, ClusterSpec.Id.from("mycluster"), ClusterSpec.Group.from(0), Version.fromString("6.142.22"));
+        c = c.allocate(ApplicationId.defaultId(), ClusterMembership.from(spec, 0), Instant.now());
+        nodes.remove(c);
+        nodes.add(c);
+        Node d = createNode(parent, "d", "d1");
+        nodes.add(d);
+        Assert.assertTrue(NodePrioritizer.isPreferredNodeToBeReloacted(nodes, d, parent));
+        Assert.assertFalse(NodePrioritizer.isPreferredNodeToBeReloacted(nodes, c, parent));
+
+        // Container over content
+        ClusterSpec spec2 = ClusterSpec.from(ClusterSpec.Type.content, ClusterSpec.Id.from("mycluster"), ClusterSpec.Group.from(0), Version.fromString("6.142.22"));
+        d = d.allocate(ApplicationId.defaultId(), ClusterMembership.from(spec, 0), Instant.now());
+        nodes.remove(d);
+        nodes.add(d);
+        Assert.assertTrue(NodePrioritizer.isPreferredNodeToBeReloacted(nodes, c, parent));
+        Assert.assertFalse(NodePrioritizer.isPreferredNodeToBeReloacted(nodes, d, parent));
+    }
+
+    private static Node createNode(Node parent, String hostname, String flavor) {
+        return Node.createDockerNode("openid", Collections.singleton("127.0.0.1"), new HashSet<>(), hostname, Optional.of(parent.hostname()),
+                flavors.getFlavorOrThrow(flavor), NodeType.tenant);
+    }
+
+    private static Node createParent(String hostname) {
+        return Node.create("openid", Collections.singleton("127.0.0.1"), new HashSet<>(), hostname, Optional.empty(),
+                flavors.getFlavorOrThrow("host-large"), NodeType.host);
+    }
+
+    private static FlavorsConfig flavorsConfig() {
+        FlavorConfigBuilder b = new FlavorConfigBuilder();
+        b.addFlavor("host-large", 6., 6., 6, Flavor.Type.BARE_METAL);
+        b.addFlavor("d1", 1, 1., 1, Flavor.Type.DOCKER_CONTAINER);
+        b.addFlavor("d2", 2, 2., 2, Flavor.Type.DOCKER_CONTAINER);
+        return b.build();
+    }
+}
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisioningTester.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisioningTester.java
index 6bd158e8311..1c82675dbab 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisioningTester.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisioningTester.java
@@ -132,6 +132,7 @@ public class ProvisioningTester implements AutoCloseable {
     public List<HostSpec> prepare(ApplicationId application, ClusterSpec cluster, int nodeCount, int groups, String flavor) {
         return prepare(application, cluster, Capacity.fromNodeCount(nodeCount, Optional.ofNullable(flavor)), groups);
     }
+
     public List<HostSpec> prepare(ApplicationId application, ClusterSpec cluster, Capacity capacity, int groups) {
         Set<String> reservedBefore = toHostNames(nodeRepository.getNodes(application, Node.State.reserved));
         Set<String> inactiveBefore = toHostNames(nodeRepository.getNodes(application, Node.State.inactive));