Merge pull request #10998 from vespa-engine/bratseth/balanced-allocation

Pick hosts for nodes to reduce resource allocation skew

18 files changed, 322 insertions, 88 deletions

diff --git a/config-provisioning/abi-spec.json b/config-provisioning/abi-spec.json
index dc9dc80fddf..32fb870150e 100644
--- a/config-provisioning/abi-spec.json
+++ b/config-provisioning/abi-spec.json
@@ -587,7 +587,8 @@
     ],
     "methods": [
       "public static com.yahoo.config.provision.NodeResources$DiskSpeed[] values()",
-      "public static com.yahoo.config.provision.NodeResources$DiskSpeed valueOf(java.lang.String)"
+      "public static com.yahoo.config.provision.NodeResources$DiskSpeed valueOf(java.lang.String)",
+      "public static int compare(com.yahoo.config.provision.NodeResources$DiskSpeed, com.yahoo.config.provision.NodeResources$DiskSpeed)"
     ],
     "fields": [
       "public static final enum com.yahoo.config.provision.NodeResources$DiskSpeed fast",
diff --git a/config-provisioning/src/main/java/com/yahoo/config/provision/NodeResources.java b/config-provisioning/src/main/java/com/yahoo/config/provision/NodeResources.java
index 4469eef98cf..5687697aff9 100644
--- a/config-provisioning/src/main/java/com/yahoo/config/provision/NodeResources.java
+++ b/config-provisioning/src/main/java/com/yahoo/config/provision/NodeResources.java
@@ -11,9 +11,24 @@ import java.util.Objects;
 public class NodeResources {
 
     public enum DiskSpeed {
+
         fast, // SSD disk or similar speed is needed
         slow, // This is tuned to work with the speed of spinning disks
-        any // The performance of the cluster using this does not depend on disk speed
+        any; // The performance of the cluster using this does not depend on disk speed
+
+        /**
+         * Compares disk speeds by cost: Slower is cheaper, and therefore before.
+         * Any can be slow and therefore costs the same as slow.
+         */
+        public static int compare(DiskSpeed a, DiskSpeed b) {
+            if (a == any) a = slow;
+            if (b == any) b = slow;
+
+            if (a == slow && b == fast) return -1;
+            if (a == fast && b == slow) return 1;
+            return 0;
+        }
+
     }
 
     private final double vcpu;
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 2c2063a0d86..4eea36c342a 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
@@ -56,8 +56,8 @@ public class DockerHostCapacity {
     /**
      * Calculate the remaining capacity for the dockerHost.
      *
-     * @param dockerHost The host to find free capacity of.
-     * @return A default (empty) capacity if not a docker host, otherwise the free/unallocated/rest capacity
+     * @param dockerHost the host to find free capacity of.
+     * @return a default (empty) capacity if not a docker host, otherwise the free/unallocated/rest capacity
      */
     NodeResources freeCapacityOf(Node dockerHost, boolean excludeInactive) {
         // Only hosts have free capacity
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/GroupPreparer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/GroupPreparer.java
index 68b9466ac82..e260e069402 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/GroupPreparer.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/GroupPreparer.java
@@ -16,6 +16,7 @@ import com.yahoo.vespa.hosted.provision.LockedNodeList;
 import com.yahoo.vespa.hosted.provision.Node;
 import com.yahoo.vespa.hosted.provision.NodeRepository;
 
+import java.util.Collections;
 import java.util.List;
 import java.util.Optional;
 import java.util.stream.Collectors;
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 5183a2d188f..cc27b1b2196 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
@@ -89,9 +89,7 @@ public class NodePrioritizer {
                     .collect(Collectors.toSet());
     }
 
-    /**
-     * @return The list of nodes sorted by PrioritizableNode::compare
-     */
+    /** Returns the list of nodes sorted by PrioritizableNode::compare */
     List<PrioritizableNode> prioritize() {
         return nodes.values().stream().sorted().collect(Collectors.toList());
     }
@@ -102,7 +100,7 @@ public class NodePrioritizer {
      */
     void addSurplusNodes(List<Node> surplusNodes) {
         for (Node node : surplusNodes) {
-            PrioritizableNode nodePri = toNodePriority(node, true, false);
+            PrioritizableNode nodePri = toPrioritizable(node, true, false);
             if (!nodePri.violatesSpares || isAllocatingForReplacement) {
                 nodes.put(node, nodePri);
             }
@@ -112,7 +110,7 @@ public class NodePrioritizer {
     /**
      * Add a node on each docker host with enough capacity for the requested flavor
      *
-     * @param exclusively Whether the ready docker nodes should only be added on hosts that
+     * @param exclusively whether the ready docker nodes should only be added on hosts that
      *                    already have nodes allocated to this tenant
      */
     void addNewDockerNodes(boolean exclusively) {
@@ -164,7 +162,7 @@ public class NodePrioritizer {
                                                  host.hostname(),
                                                  resources(requestedNodes).withDiskSpeed(host.flavor().resources().diskSpeed()),
                                                  NodeType.tenant);
-            PrioritizableNode nodePri = toNodePriority(newNode, false, true);
+            PrioritizableNode nodePri = toPrioritizable(newNode, false, true);
             if ( ! nodePri.violatesSpares || isAllocatingForReplacement) {
                 log.log(LogLevel.DEBUG, "Adding new Docker node " + newNode);
                 nodes.put(newNode, nodePri);
@@ -172,9 +170,7 @@ public class NodePrioritizer {
         }
     }
 
-    /**
-     * Add existing nodes allocated to the application
-     */
+    /** Add existing nodes allocated to the application */
     void addApplicationNodes() {
         EnumSet<Node.State> legalStates = EnumSet.of(Node.State.active, Node.State.inactive, Node.State.reserved);
         allNodes.asList().stream()
@@ -182,18 +178,16 @@ public class NodePrioritizer {
                 .filter(node -> legalStates.contains(node.state()))
                 .filter(node -> node.allocation().isPresent())
                 .filter(node -> node.allocation().get().owner().equals(appId))
-                .map(node -> toNodePriority(node, false, false))
+                .map(node -> toPrioritizable(node, false, false))
                 .forEach(prioritizableNode -> nodes.put(prioritizableNode.node, prioritizableNode));
     }
 
-    /**
-     * Add nodes already provisioned, but not allocated to any application
-     */
+    /** Add nodes already provisioned, but not allocated to any application */
     void addReadyNodes() {
         allNodes.asList().stream()
                 .filter(node -> node.type().equals(requestedNodes.type()))
                 .filter(node -> node.state().equals(Node.State.ready))
-                .map(node -> toNodePriority(node, false, false))
+                .map(node -> toPrioritizable(node, false, false))
                 .filter(n -> !n.violatesSpares || isAllocatingForReplacement)
                 .forEach(prioritizableNode -> nodes.put(prioritizableNode.node, prioritizableNode));
     }
@@ -202,14 +196,13 @@ public class NodePrioritizer {
      * Convert a list of nodes to a list of node priorities. This includes finding, calculating
      * parameters to the priority sorting procedure.
      */
-    private PrioritizableNode toNodePriority(Node node, boolean isSurplusNode, boolean isNewNode) {
+    private PrioritizableNode toPrioritizable(Node node, boolean isSurplusNode, boolean isNewNode) {
         PrioritizableNode.Builder builder = new PrioritizableNode.Builder(node)
                 .withSurplusNode(isSurplusNode)
                 .withNewNode(isNewNode);
 
         allNodes.parentOf(node).ifPresent(parent -> {
             builder.withParent(parent).withFreeParentCapacity(capacity.freeCapacityOf(parent, false));
-
             if (spareHosts.contains(parent)) {
                 builder.withViolatesSpares(true);
             }
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 a47daa0e86e..d53e36b7501 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
@@ -4,7 +4,12 @@ package com.yahoo.vespa.hosted.provision.provisioning;
 import com.yahoo.config.provision.NodeResources;
 import com.yahoo.vespa.hosted.provision.Node;
 
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
 import java.util.Optional;
+import java.util.stream.Collectors;
 
 import static com.yahoo.vespa.hosted.provision.provisioning.NodePrioritizer.ALLOCATABLE_HOST_STATES;
 
@@ -15,11 +20,14 @@ import static com.yahoo.vespa.hosted.provision.provisioning.NodePrioritizer.ALLO
  */
 class PrioritizableNode implements Comparable<PrioritizableNode> {
 
+    private static final NodeResources zeroResources =
+            new NodeResources(0, 0, 0, 0, NodeResources.DiskSpeed.any);
+
     // TODO: Make immutable
     Node node;
 
-    /** The free capacity, including retired allocations */
-    final NodeResources freeParentCapacity;
+    /** The free capacity on the parent of this node, before adding this node to it */
+    private final NodeResources freeParentCapacity;
 
     /** The parent host (docker or hypervisor) */
     final Optional<Node> parent;
@@ -66,8 +74,8 @@ class PrioritizableNode implements Comparable<PrioritizableNode> {
         if (other.node.state() == Node.State.inactive && this.node.state() != Node.State.inactive) return 1;
 
         // Choose reserved nodes from a previous allocation attempt (the exist in node repo)
-        if (isInNodeRepoAndReserved(this) && !isInNodeRepoAndReserved(other)) return -1;
-        if (isInNodeRepoAndReserved(other) && !isInNodeRepoAndReserved(this)) return 1;
+        if (this.isInNodeRepoAndReserved() && ! other.isInNodeRepoAndReserved()) return -1;
+        if (other.isInNodeRepoAndReserved() && ! this.isInNodeRepoAndReserved()) return 1;
 
         // Choose ready nodes
         if (this.node.state() == Node.State.ready && other.node.state() != Node.State.ready) return -1;
@@ -81,9 +89,16 @@ class PrioritizableNode implements Comparable<PrioritizableNode> {
         int otherHostStatePri = other.parent.map(host -> ALLOCATABLE_HOST_STATES.indexOf(host.state())).orElse(-2);
         if (thisHostStatePri != otherHostStatePri) return otherHostStatePri - thisHostStatePri;
 
-        // Choose the node with parent node with the least capacity (TODO parameterize this as this is pretty much the core of the algorithm)
-        int freeCapacity = NodeResourceComparator.defaultOrder().compare(this.freeParentCapacity, other.freeParentCapacity);
-        if (freeCapacity != 0) return freeCapacity;
+        if (this.parent.isPresent() && other.parent.isPresent()) {
+            int diskCostDifference = NodeResources.DiskSpeed.compare(this.parent.get().flavor().resources().diskSpeed(),
+                                                                     other.parent.get().flavor().resources().diskSpeed());
+            if (diskCostDifference != 0)
+                return diskCostDifference;
+        }
+
+        int hostPriority = Double.compare(this.skewWithThis() - this.skewWithoutThis(),
+                                          other.skewWithThis() - other.skewWithoutThis());
+        if (hostPriority != 0) return hostPriority;
 
         // Choose cheapest node
         if (this.node.flavor().cost() < other.node.flavor().cost()) return -1;
@@ -93,14 +108,43 @@ class PrioritizableNode implements Comparable<PrioritizableNode> {
         return this.node.hostname().compareTo(other.node.hostname());
     }
 
-    private static boolean isInNodeRepoAndReserved(PrioritizableNode nodePri) {
-        if (nodePri.isNewNode) return false;
-        return nodePri.node.state().equals(Node.State.reserved);
+    /** Returns the allocation skew of the parent of this before adding this node to it */
+    double skewWithoutThis() { return skewWith(zeroResources); }
+
+    /** Returns the allocation skew of the parent of this after adding this node to it */
+    double skewWithThis() { return skewWith(node.flavor().resources()); }
+
+    private double skewWith(NodeResources resources) {
+        if (parent.isEmpty()) return 0;
+
+        NodeResources all = anySpeed(parent.get().flavor().resources());
+        NodeResources allocated = all.subtract(anySpeed(freeParentCapacity)).add(anySpeed(resources));
+
+        return new Mean(allocated.vcpu() / all.vcpu(),
+                        allocated.memoryGb() / all.memoryGb(),
+                        allocated.diskGb() / all.diskGb())
+                       .deviation();
+    }
+
+    /** We don't care about disk speed in calculations here */
+    private NodeResources anySpeed(NodeResources resources) {
+        return resources.withDiskSpeed(NodeResources.DiskSpeed.any);
+    }
+
+    private boolean isInNodeRepoAndReserved() {
+        if (isNewNode) return false;
+        return node.state().equals(Node.State.reserved);
+    }
+
+    @Override
+    public String toString() {
+        return node.id();
     }
 
     static class Builder {
+
         public final Node node;
-        private NodeResources freeParentCapacity = new NodeResources(0, 0, 0, 0);
+        private NodeResources freeParentCapacity;
         private Optional<Node> parent = Optional.empty();
         private boolean violatesSpares;
         private boolean isSurplusNode;
@@ -108,8 +152,10 @@ class PrioritizableNode implements Comparable<PrioritizableNode> {
 
         Builder(Node node) {
             this.node = node;
+            this.freeParentCapacity = node.flavor().resources();
         }
 
+        /** The free capacity of the parent, before adding this node to it */
         Builder withFreeParentCapacity(NodeResources freeParentCapacity) {
             this.freeParentCapacity = freeParentCapacity;
             return this;
@@ -140,4 +186,19 @@ class PrioritizableNode implements Comparable<PrioritizableNode> {
         }
     }
 
+    /** The mean and mean deviation (squared difference) of a bunch of numbers */
+    private static class Mean {
+
+        private final double mean;
+        private final double deviation;
+
+        private Mean(double ... numbers) {
+            mean = Arrays.stream(numbers).sum() / numbers.length;
+            deviation = Arrays.stream(numbers).map(n -> Math.pow(mean - n, 2)).sum() / numbers.length;
+        }
+
+        public double deviation() {  return deviation; }
+
+    }
+
 }
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicDockerAllocationTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicDockerAllocationTest.java
index cfcdc882a3c..4037bc52064 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicDockerAllocationTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/DynamicDockerAllocationTest.java
@@ -109,46 +109,81 @@ public class DynamicDockerAllocationTest {
         tester.makeReadyNodes(5, "host-small", NodeType.host, 32);
         deployZoneApp(tester);
         List<Node> dockerHosts = tester.nodeRepository().getNodes(NodeType.host, Node.State.active);
-        NodeResources flavor = new NodeResources(1, 4, 10, 0.3);
+        NodeResources resources = new NodeResources(1, 4, 10, 0.3);
 
         // Application 1
         ApplicationId application1 = makeApplicationId("t1", "a1");
         ClusterSpec clusterSpec1 = clusterSpec("myContent.t1.a1");
-        deployApp(application1, clusterSpec1, flavor, tester, 3);
+        deployApp(application1, clusterSpec1, resources, tester, 3);
 
         // Application 2
         ApplicationId application2 = makeApplicationId("t2", "a2");
         ClusterSpec clusterSpec2 = clusterSpec("myContent.t2.a2");
-        deployApp(application2, clusterSpec2, flavor, tester, 2);
+        deployApp(application2, clusterSpec2, resources, tester, 2);
 
         // Application 3
         ApplicationId application3 = makeApplicationId("t3", "a3");
         ClusterSpec clusterSpec3 = clusterSpec("myContent.t3.a3");
-        deployApp(application3, clusterSpec3, flavor, tester, 2);
+        deployApp(application3, clusterSpec3, resources, tester, 2);
 
         // App 2 and 3 should have been allocated to the same nodes - fail one of the parent hosts from there
-        String parent = tester.nodeRepository().getNodes(application2).stream().findAny().get().parentHostname().get();
+        String parent = "host-1.yahoo.com";
         tester.nodeRepository().failRecursively(parent, Agent.system, "Testing");
 
         // Redeploy all applications
-        deployApp(application1, clusterSpec1, flavor, tester, 3);
-        deployApp(application2, clusterSpec2, flavor, tester, 2);
-        deployApp(application3, clusterSpec3, flavor, tester, 2);
+        deployApp(application1, clusterSpec1, resources, tester, 3);
+        deployApp(application2, clusterSpec2, resources, tester, 2);
+        deployApp(application3, clusterSpec3, resources, tester, 2);
 
         Map<Integer, Integer> numberOfChildrenStat = new HashMap<>();
-        for (Node node : dockerHosts) {
-            int nofChildren = tester.nodeRepository().list().childrenOf(node).size();
+        for (Node host : dockerHosts) {
+            int nofChildren = tester.nodeRepository().list().childrenOf(host).size();
             if (!numberOfChildrenStat.containsKey(nofChildren)) {
                 numberOfChildrenStat.put(nofChildren, 0);
             }
             numberOfChildrenStat.put(nofChildren, numberOfChildrenStat.get(nofChildren) + 1);
         }
 
-        assertEquals(3, numberOfChildrenStat.get(3).intValue());
-        assertEquals(1, numberOfChildrenStat.get(0).intValue());
+        assertEquals(4, numberOfChildrenStat.get(2).intValue());
         assertEquals(1, numberOfChildrenStat.get(1).intValue());
     }
 
+    @Test
+    public void test_allocation_balancing() {
+        // Here we test balancing between cpu and memory and ignore disk
+
+        ProvisioningTester tester = new ProvisioningTester.Builder().zone(new Zone(Environment.prod, RegionName.from("us-east"))).flavorsConfig(flavorsConfig()).build();
+        tester.makeReadyNodes(3, "flt", NodeType.host, 8); // cpu: 30, mem: 30
+        tester.makeReadyNodes(3, "cpu", NodeType.host, 8); // cpu: 40, mem: 20
+        tester.makeReadyNodes(3, "mem", NodeType.host, 8); // cpu: 20, mem: 40
+        deployZoneApp(tester);
+        NodeResources fltResources = new NodeResources(6, 6, 1, 0.1);
+        NodeResources cpuResources = new NodeResources(8, 4, 1, 0.1);
+        NodeResources memResources = new NodeResources(4, 8, 1, 0.1);
+
+        // Cpu heavy application
+        ApplicationId application1 = makeApplicationId("t1", "a1");
+        deployApp(application1, clusterSpec("c"), cpuResources, tester, 2);
+        tester.assertAllocatedOn("Cpu nodes cause least skew increase", "cpu", application1);
+
+        // Mem heavy application
+        ApplicationId application2 = makeApplicationId("t2", "a2");
+        deployApp(application2, clusterSpec("c"), memResources, tester, 2);
+        tester.assertAllocatedOn("Mem nodes cause least skew increase", "mem", application2);
+
+        // Flat application
+        ApplicationId application3 = makeApplicationId("t3", "a3");
+        deployApp(application3, clusterSpec("c"), fltResources, tester, 2);
+        tester.assertAllocatedOn("Flat nodes cause least skew increase", "flt", application3);
+
+        // Mem heavy application which can't all be allocated on mem nodes
+        ApplicationId application4 = makeApplicationId("t4", "a4");
+        deployApp(application4, clusterSpec("c"), memResources, tester, 3);
+        assertEquals(2, tester.hostFlavorCount("mem", application4));
+        assertEquals(1, tester.hostFlavorCount("flt", application4));
+
+    }
+
     /**
      * Test redeployment of nodes that violates spare headroom - but without alternatives
      * <p>
@@ -410,8 +445,11 @@ public class DynamicDockerAllocationTest {
 
     private FlavorsConfig flavorsConfig() {
         FlavorConfigBuilder b = new FlavorConfigBuilder();
-        b.addFlavor("host-large", 6., 24., 80, 6, Flavor.Type.BARE_METAL);
-        b.addFlavor("host-small", 3., 12., 40, 3, Flavor.Type.BARE_METAL);
+        b.addFlavor("host-large", 6, 24, 80, 6, Flavor.Type.BARE_METAL);
+        b.addFlavor("host-small", 3, 12, 40, 3, Flavor.Type.BARE_METAL);
+        b.addFlavor("flt", 30, 30, 40, 3, Flavor.Type.BARE_METAL);
+        b.addFlavor("cpu", 40, 20, 40, 3, Flavor.Type.BARE_METAL);
+        b.addFlavor("mem", 20, 40, 40, 3, Flavor.Type.BARE_METAL);
         return b.build();
     }
 
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/PrioritizableNodeTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/PrioritizableNodeTest.java
index 1a373222bc5..725842db819 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/PrioritizableNodeTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/PrioritizableNodeTest.java
@@ -18,32 +18,132 @@ import java.util.Set;
 
 import static org.junit.Assert.assertEquals;
 
+/**
+ * @author bratseth
+ */
 public class PrioritizableNodeTest {
 
     @Test
     public void test_order() {
         List<PrioritizableNode> expected = List.of(
-                new PrioritizableNode(node("abc123", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.empty(), false, true, false),
-                new PrioritizableNode(node("abc123", Node.State.active), new NodeResources(2, 2, 2, 2), Optional.empty(), true, false, false),
-                new PrioritizableNode(node("abc123", Node.State.inactive), new NodeResources(2, 2, 2, 2), Optional.empty(), true, false, false),
-                new PrioritizableNode(node("abc123", Node.State.reserved), new NodeResources(2, 2, 2, 2), Optional.empty(), true, false, false),
-                new PrioritizableNode(node("abc123", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.of(node("host1", Node.State.active)), true, false, true),
-                new PrioritizableNode(node("abc123", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.of(node("host1", Node.State.ready)), true, false, true),
-                new PrioritizableNode(node("abc123", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.of(node("host1", Node.State.provisioned)), true, false, true),
-                new PrioritizableNode(node("abc123", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.of(node("host1", Node.State.failed)), true, false, true),
-                new PrioritizableNode(node("abc123", Node.State.ready), new NodeResources(1, 1, 1, 1), Optional.empty(), true, false, true),
-                new PrioritizableNode(node("abc123", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.empty(), true, false, true),
-                new PrioritizableNode(node("xyz789", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.empty(), true, false, true)
+                new PrioritizableNode(node("01", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.empty(), false, true, false),
+                new PrioritizableNode(node("02", Node.State.active), new NodeResources(2, 2, 2, 2), Optional.empty(), true, false, false),
+                new PrioritizableNode(node("03", Node.State.inactive), new NodeResources(2, 2, 2, 2), Optional.empty(), true, false, false),
+                new PrioritizableNode(node("04", Node.State.reserved), new NodeResources(2, 2, 2, 2), Optional.empty(), true, false, false),
+                new PrioritizableNode(node("05", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.of(node("host1", Node.State.active)), true, false, true),
+                new PrioritizableNode(node("06", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.of(node("host1", Node.State.ready)), true, false, true),
+                new PrioritizableNode(node("07", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.of(node("host1", Node.State.provisioned)), true, false, true),
+                new PrioritizableNode(node("08", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.of(node("host1", Node.State.failed)), true, false, true),
+                new PrioritizableNode(node("09", Node.State.ready), new NodeResources(1, 1, 1, 1), Optional.empty(), true, false, true),
+                new PrioritizableNode(node("10", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.empty(), true, false, true),
+                new PrioritizableNode(node("11", Node.State.ready), new NodeResources(2, 2, 2, 2), Optional.empty(), true, false, true)
         );
+        assertOrder(expected);
+    }
+
+    @Test
+    public void testOrderingByAllocationSkew1() {
+        List<PrioritizableNode> expected = List.of(
+                node("1", node(4, 4), host(20, 20), host(40, 40)),
+                node("2", node(4, 4), host(21, 20), host(40, 40)),
+                node("3", node(4, 4), host(22, 20), host(40, 40)),
+                node("4", node(4, 4), host(21, 22), host(40, 40)),
+                node("5", node(4, 4), host(21, 21), host(40, 80))
+        );
+        assertOrder(expected);
+    }
+
+    @Test
+    public void testOrderingByAllocationSkew2() {
+        // The same as testOrderingByAllocationSkew1, but deviating from mean (20) in the other direction.
+        // Since we don't choose the node with the lowest skew, but with the largest skew *reduction*
+        // this causes the opposite order.
+        List<PrioritizableNode> expected = List.of(
+                node("4", node(4, 4), host(19, 18), host(40, 40)),
+                node("3", node(4, 4), host(18, 20), host(40, 40)),
+                node("2", node(4, 4), host(19, 20), host(40, 40)),
+                node("1", node(4, 4), host(20, 20), host(40, 40)),
+                node("5", node(4, 4), host(19, 19), host(40, 80))
+        );
+        assertOrder(expected);
+    }
 
+    @Test
+    public void testOrderingByAllocationSkew3() {
+        // The same as testOrderingByAllocationSkew1, but allocating skewed towards cpu
+        List<PrioritizableNode> expected = List.of(
+                node("1", node(4, 2), host(20, 20), host(40, 40)),
+                node("2", node(4, 2), host(21, 20), host(40, 40)),
+                node("4", node(4, 2), host(21, 22), host(40, 40)),
+                node("3", node(4, 2), host(22, 20), host(40, 40)),
+                node("5", node(4, 2), host(21, 21), host(40, 80))
+        );
+        assertOrder(expected);
+    }
+
+    @Test
+    public void testOrderingByAllocationSkew4() {
+        // The same as testOrderingByAllocationSkew1, but allocating skewed towards memory
+        List<PrioritizableNode> expected = List.of(
+                node("5", node(2, 10), host(21, 21), host(40, 80)),
+                node("3", node(2, 10), host(22, 20), host(40, 40)),
+                node("2", node(2, 10), host(21, 20), host(40, 40)),
+                node("1", node(2, 10), host(20, 20), host(40, 40)),
+                node("4", node(2, 10), host(21, 22), host(40, 40))
+        );
+        assertOrder(expected);
+    }
+
+    @Test
+    public void testOrderingByAllocationSkew5() {
+        // node1 is skewed towards cpu (without this allocation), allocation is skewed towards memory, therefore
+        // node 1 is preferred (even though it is still most skewed)
+        List<PrioritizableNode> expected = List.of(
+                node("1", node(1, 5), host(21, 10), host(40, 40)),
+                node("2", node(1, 5), host(21, 20), host(40, 40)),
+                node("3", node(1, 5), host(20, 20), host(40, 40)),
+                node("4", node(1, 5), host(20, 22), host(40, 40))
+        );
+        assertOrder(expected);
+    }
+
+    private void assertOrder(List<PrioritizableNode> expected) {
         List<PrioritizableNode> copy = new ArrayList<>(expected);
         Collections.shuffle(copy);
         Collections.sort(copy);
         assertEquals(expected, copy);
     }
 
+    private static NodeResources node(double vcpu, double mem) {
+        return new NodeResources(vcpu, mem, 0, 0);
+    }
+
+    private static NodeResources host(double vcpu, double mem) {
+        return new NodeResources(vcpu, mem, 10, 10);
+    }
+
     private static Node node(String hostname, Node.State state) {
         return new Node(hostname, new IP.Config(Set.of("::1"), Set.of()), hostname, Optional.empty(), new Flavor(new NodeResources(2, 2, 2, 2)),
-                Status.initial(), state, Optional.empty(), History.empty(), NodeType.tenant, new Reports(), Optional.empty());
+                        Status.initial(), state, Optional.empty(), History.empty(), NodeType.tenant, new Reports(), Optional.empty());
+    }
+
+    private static PrioritizableNode node(String hostname,
+                                          NodeResources nodeResources,
+                                          NodeResources allocatedHostResources, // allocated before adding nodeResources
+                                          NodeResources totalHostResources) {
+        Node node = new Node(hostname, new IP.Config(Set.of("::1"), Set.of()), hostname, Optional.of(hostname + "parent"), new Flavor(nodeResources),
+                             Status.initial(), Node.State.ready, Optional.empty(), History.empty(), NodeType.tenant, new Reports(), Optional.empty());
+        Node parent = new Node(hostname + "parent", new IP.Config(Set.of("::1"), Set.of()), hostname, Optional.empty(), new Flavor(totalHostResources),
+                               Status.initial(), Node.State.ready, Optional.empty(), History.empty(), NodeType.host, new Reports(), Optional.empty());
+        return new PrioritizableNode(node, totalHostResources.subtract(allocatedHostResources), Optional.of(parent), false, false, true);
+    }
+
+    private void printSkew(List<PrioritizableNode> nodes) {
+        for (var node : nodes)
+            System.out.println("Skew of " + node.node.id() +
+                               ": diff: " + (node.skewWithThis()-node.skewWithoutThis()) +
+                               ", with: " + node.skewWithThis() +
+                               ", without: " + node.skewWithoutThis());
     }
+
 }
\ No newline at end of file
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 ef1ad1e76eb..6c5cc198c67 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
@@ -412,6 +412,31 @@ public class ProvisioningTester {
         assertEquals(expectedCount, actualNodesWithFlavor);
     }
 
+    public void assertAllocatedOn(String explanation, String hostFlavor, ApplicationId app) {
+        for (Node node : nodeRepository.getNodes(app)) {
+            Node parent = nodeRepository.getNode(node.parentHostname().get()).get();
+            assertEquals(node + ": " + explanation, hostFlavor, parent.flavor().name());
+        }
+    }
+
+    public void printFreeResources() {
+        for (Node host : nodeRepository().getNodes(NodeType.host)) {
+            NodeResources free = host.flavor().resources();
+            for (Node child : nodeRepository().getNodes(NodeType.tenant)) {
+                if (child.parentHostname().get().equals(host.hostname()))
+                    free = free.subtract(child.flavor().resources());
+            }
+            System.out.println(host.flavor().name() + " node. Free resources: " + free);
+        }
+    }
+
+    public int hostFlavorCount(String hostFlavor, ApplicationId app) {
+        return (int)nodeRepository().getNodes(app).stream()
+                                                  .map(n -> nodeRepository().getNode(n.parentHostname().get()).get())
+                                                  .filter(p -> p.flavor().name().equals(hostFlavor))
+                                                  .count();
+    }
+
     private Flavor getNodeFlavor(String hostname) {
         return nodeRepository.getNode(hostname).map(Node::flavor).orElseThrow(() -> new RuntimeException("No flavor for host " + hostname));
     }
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/RestApiTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/RestApiTest.java
index cad885104f3..59c3ef32dcb 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/RestApiTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/RestApiTest.java
@@ -165,23 +165,23 @@ public class RestApiTest {
                        "{\"message\":\"Removed host8.yahoo.com\"}");
 
         // or, PUT a node in failed ...
-        assertResponse(new Request("http://localhost:8080/nodes/v2/state/failed/test-node-pool-101-2",
+        assertResponse(new Request("http://localhost:8080/nodes/v2/state/failed/test-node-pool-102-2",
                                    new byte[0], Request.Method.PUT),
-                       "{\"message\":\"Moved test-node-pool-101-2 to failed\"}");
-        assertResponseContains(new Request("http://localhost:8080/nodes/v2/node/test-node-pool-101-2"),
+                       "{\"message\":\"Moved test-node-pool-102-2 to failed\"}");
+        assertResponseContains(new Request("http://localhost:8080/nodes/v2/node/test-node-pool-102-2"),
                                            "\"state\":\"failed\"");
         // ... and deallocate it such that it moves to dirty and is recycled
-        assertResponse(new Request("http://localhost:8080/nodes/v2/state/dirty/test-node-pool-101-2",
+        assertResponse(new Request("http://localhost:8080/nodes/v2/state/dirty/test-node-pool-102-2",
                                    new byte[0], Request.Method.PUT),
-                       "{\"message\":\"Moved test-node-pool-101-2 to dirty\"}");
+                       "{\"message\":\"Moved test-node-pool-102-2 to dirty\"}");
 
         // ... and set it back to ready as if this was from the node-admin with the temporary state rest api
-        assertResponse(new Request("http://localhost:8080/nodes/v2/state/ready/test-node-pool-101-2",
+        assertResponse(new Request("http://localhost:8080/nodes/v2/state/ready/test-node-pool-102-2",
                         new byte[0], Request.Method.PUT),
-                "{\"message\":\"Moved test-node-pool-101-2 to ready\"}");
+                "{\"message\":\"Moved test-node-pool-102-2 to ready\"}");
 
-        assertResponse(new Request("http://localhost:8080/nodes/v2/node/test-node-pool-101-2",  new byte[0], Request.Method.GET),
-                404, "{\"error-code\":\"NOT_FOUND\",\"message\":\"No node with hostname 'test-node-pool-101-2'\"}");
+        assertResponse(new Request("http://localhost:8080/nodes/v2/node/test-node-pool-102-2",  new byte[0], Request.Method.GET),
+                404, "{\"error-code\":\"NOT_FOUND\",\"message\":\"No node with hostname 'test-node-pool-102-2'\"}");
 
         // Put a host in failed and make sure it's children are also failed
         assertResponse(new Request("http://localhost:8080/nodes/v2/state/failed/dockerhost1.yahoo.com", new byte[0], Request.Method.PUT),
@@ -286,10 +286,10 @@ public class RestApiTest {
                        "{\"error-code\":\"BAD_REQUEST\",\"message\":\"Cannot assign [127.0.1.1] to tenant-node-foo.yahoo.com: [127.0.1.1] already assigned to host1.yahoo.com\"}");
 
         // Attempt to PATCH existing tenant node with already assigned IP
-        assertResponse(new Request("http://localhost:8080/nodes/v2/node/test-node-pool-101-2",
+        assertResponse(new Request("http://localhost:8080/nodes/v2/node/test-node-pool-102-2",
                                    "{\"ipAddresses\": [\"127.0.2.1\"]}",
                                    Request.Method.PATCH), 400,
-                       "{\"error-code\":\"BAD_REQUEST\",\"message\":\"Could not set field 'ipAddresses': Cannot assign [127.0.2.1] to test-node-pool-101-2: [127.0.2.1] already assigned to host2.yahoo.com\"}");
+                       "{\"error-code\":\"BAD_REQUEST\",\"message\":\"Could not set field 'ipAddresses': Cannot assign [127.0.2.1] to test-node-pool-102-2: [127.0.2.1] already assigned to host2.yahoo.com\"}");
 
         // Attempt to POST host node with already assigned IP
         assertResponse(new Request("http://localhost:8080/nodes/v2/node",
@@ -480,7 +480,7 @@ public class RestApiTest {
                        "{\"error-code\":\"BAD_REQUEST\",\"message\":\"Cannot add host8.yahoo.com: A node with this name already exists\"}");
 
         // Attempt to PATCH field not relevant for child node
-        assertResponse(new Request("http://localhost:8080/nodes/v2/node/test-node-pool-101-2",
+        assertResponse(new Request("http://localhost:8080/nodes/v2/node/test-node-pool-102-2",
                                    Utf8.toBytes("{\"modelName\": \"foo\"}"), Request.Method.PATCH),
                        400,
                        "{\"error-code\":\"BAD_REQUEST\",\"message\":\"Could not set field 'modelName': A child node cannot have model name set\"}");
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/acl-config-server.json b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/acl-config-server.json
index c8a8037aeb0..55891309856 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/acl-config-server.json
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/acl-config-server.json
@@ -217,9 +217,9 @@
       "trustedBy": "cfg1.yahoo.com"
     },
     {
-      "hostname": "test-node-pool-101-2",
+      "hostname": "test-node-pool-102-2",
       "type": "tenant",
-      "ipAddress": "::101:2",
+      "ipAddress": "::102:2",
       "trustedBy": "cfg1.yahoo.com"
     }
   ],
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/acl-tenant-node.json b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/acl-tenant-node.json
index 370dacd3c85..16cf5c36dcc 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/acl-tenant-node.json
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/acl-tenant-node.json
@@ -163,9 +163,9 @@
       "trustedBy": "foo.yahoo.com"
     },
     {
-      "hostname": "test-node-pool-101-2",
+      "hostname": "test-node-pool-102-2",
       "type": "tenant",
-      "ipAddress": "::101:2",
+      "ipAddress": "::102:2",
       "trustedBy": "foo.yahoo.com"
     }
   ],
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-hostremoval-impossible.json b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-hostremoval-impossible.json
index f3c73e61c91..f85e0dcc270 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-hostremoval-impossible.json
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-hostremoval-impossible.json
@@ -13,7 +13,7 @@
       "eligibleParents": 1
     },
     {
-      "tenant": "test-node-pool-101-2",
+      "tenant": "test-node-pool-102-2",
       "eligibleParents": 0
     }
   ]
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-hostremoval-possible.json b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-hostremoval-possible.json
index b896fd9d63a..9633ded1d5e 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-hostremoval-possible.json
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-hostremoval-possible.json
@@ -12,7 +12,7 @@
       "eligibleParents": 2
     },
     {
-      "tenant": "test-node-pool-101-2",
+      "tenant": "test-node-pool-102-2",
       "newParent": "dockerhost5.yahoo.com",
       "eligibleParents": 1
     }
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-zone.json b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-zone.json
index 68f89b1e20a..f65ee84b795 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-zone.json
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/capacity-zone.json
@@ -25,16 +25,16 @@
   },
   "details": {
     "hostsToRemove": [
-      "dockerhost2.yahoo.com",
+      "dockerhost3.yahoo.com",
       "dockerhost1.yahoo.com",
       "dockerhost4.yahoo.com",
-      "dockerhost3.yahoo.com"
+      "dockerhost5.yahoo.com"
     ],
     "removalPossible": false,
     "history": [
       {
-        "tenant": "test-node-pool-101-2",
-        "newParent": "dockerhost5.yahoo.com",
+        "tenant": "test-node-pool-102-2",
+        "newParent": "dockerhost2.yahoo.com",
         "eligibleParents": 1
       },
       {
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/docker-container1.json b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/docker-container1.json
index 3fd38118e91..16dcd9a3fbd 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/docker-container1.json
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/docker-container1.json
@@ -1,11 +1,11 @@
 {
-  "url": "http://localhost:8080/nodes/v2/node/test-node-pool-101-2",
-  "id": "test-node-pool-101-2",
+  "url": "http://localhost:8080/nodes/v2/node/test-node-pool-102-2",
+  "id": "test-node-pool-102-2",
   "state": "active",
   "type": "tenant",
-  "hostname": "test-node-pool-101-2",
-  "parentHostname": "dockerhost2.yahoo.com",
-  "openStackId": "fake-test-node-pool-101-2",
+  "hostname": "test-node-pool-102-2",
+  "parentHostname": "dockerhost3.yahoo.com",
+  "openStackId": "fake-test-node-pool-102-2",
   "flavor": "[vcpu: 1.0, memory: 4.0 Gb, disk 100.0 Gb, bandwidth: 1.0 Gbps]",
   "canonicalFlavor": "[vcpu: 1.0, memory: 4.0 Gb, disk 100.0 Gb, bandwidth: 1.0 Gbps]",
   "minDiskAvailableGb": 100.0,
@@ -49,7 +49,7 @@
     }
   ],
   "ipAddresses": [
-    "::101:2"
+    "::102:2"
   ],
   "additionalIpAddresses": []
 }
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/nodes-recursive.json b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/nodes-recursive.json
index 123344f4aac..cf3e3c1b457 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/nodes-recursive.json
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/nodes-recursive.json
@@ -8,8 +8,8 @@
     @include(node1.json),
     @include(docker-node4.json),
     @include(node6.json),
-    @include(docker-node5.json),
     @include(docker-container1.json),
+    @include(docker-node5.json),
     @include(docker-node2.json),
     @include(node13.json),
     @include(node2.json),
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/nodes.json b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/nodes.json
index a45e239c2b6..cdbd2cac9b9 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/nodes.json
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/restapi/v2/responses/nodes.json
@@ -25,10 +25,10 @@
       "url": "http://localhost:8080/nodes/v2/node/host6.yahoo.com"
     },
     {
-      "url": "http://localhost:8080/nodes/v2/node/dockerhost5.yahoo.com"
+      "url": "http://localhost:8080/nodes/v2/node/test-node-pool-102-2"
     },
     {
-      "url": "http://localhost:8080/nodes/v2/node/test-node-pool-101-2"
+      "url": "http://localhost:8080/nodes/v2/node/dockerhost5.yahoo.com"
     },
     {
       "url": "http://localhost:8080/nodes/v2/node/dockerhost2.yahoo.com"