SpareCapacityMaintainer sketch

19 files changed, 274 insertions, 96 deletions

diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/Node.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/Node.java
index a9861497ca3..b6237886dc7 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/Node.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/Node.java
@@ -128,6 +128,8 @@ public final class Node {
         return parentHostname.isPresent() && parentHostname.get().equals(hostname);
     }
 
+    public NodeResources resources() { return flavor.resources(); }
+
     /** Returns the flavor of this node */
     public Flavor flavor() { return flavor; }
 
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/NodeList.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/NodeList.java
index 1b2f73a2f5f..1cc2abef734 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/NodeList.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/NodeList.java
@@ -46,13 +46,21 @@ public class NodeList extends AbstractFilteringList<Node, NodeList> {
     }
 
     /** Returns the subset of nodes having exactly the given resources */
-    public NodeList resources(NodeResources resources) { return matching(node -> node.flavor().resources().equals(resources)); }
+    public NodeList resources(NodeResources resources) { return matching(node -> node.resources().equals(resources)); }
+
+    /** Returns the subset of nodes which satisfy the given resources */
+    public NodeList satisfies(NodeResources resources) { return matching(node -> node.resources().satisfies(resources)); }
 
     /** Returns the subset of nodes of the given flavor */
     public NodeList flavor(String flavor) {
         return matching(node -> node.flavor().name().equals(flavor));
     }
 
+    /** Returns the subset of nodes not in the given collection */
+    public NodeList except(Collection<Node> nodes) {
+        return matching(node -> ! nodes.contains(node));
+    }
+
     /** Returns the subset of nodes assigned to the given cluster type */
     public NodeList type(ClusterSpec.Type type) {
         return matching(node -> node.allocation().isPresent() && node.allocation().get().membership().cluster().type().equals(type));
@@ -109,6 +117,11 @@ public class NodeList extends AbstractFilteringList<Node, NodeList> {
         return matching(node -> nodeTypes.contains(node.type()));
     }
 
+    /** Returns the subset of nodes of the host type */
+    public NodeList hosts() {
+        return matching(node -> node.type() == NodeType.host);
+    }
+
     /** Returns the subset of nodes that are parents */
     public NodeList parents() {
         return matching(n -> n.parentHostname().isEmpty());
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocatableClusterResources.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocatableClusterResources.java
index e6cbddf96f2..267bfefa332 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocatableClusterResources.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/autoscale/AllocatableClusterResources.java
@@ -47,7 +47,7 @@ public class AllocatableClusterResources {
         this.nodes = nodes.size();
         this.groups = (int)nodes.stream().map(node -> node.allocation().get().membership().cluster().group()).distinct().count();
         this.realResources = averageRealResourcesOf(nodes, nodeRepository); // Average since we average metrics over nodes
-        this.advertisedResources = nodes.get(0).flavor().resources();
+        this.advertisedResources = nodes.get(0).resources();
         this.clusterType = nodes.get(0).allocation().get().membership().cluster().type();
         this.fulfilment = 1;
     }
@@ -125,11 +125,11 @@ public class AllocatableClusterResources {
         NodeResources sum = new NodeResources(0, 0, 0, 0);
         for (Node node : nodes)
             sum = sum.add(nodeRepository.resourcesCalculator().realResourcesOf(node, nodeRepository).justNumbers());
-        return nodes.get(0).flavor().resources().justNonNumbers()
-                                                .withVcpu(sum.vcpu() / nodes.size())
-                                                .withMemoryGb(sum.memoryGb() / nodes.size())
-                                                .withDiskGb(sum.diskGb() / nodes.size())
-                                                .withBandwidthGbps(sum.bandwidthGbps() / nodes.size());
+        return nodes.get(0).resources().justNonNumbers()
+                                       .withVcpu(sum.vcpu() / nodes.size())
+                                       .withMemoryGb(sum.memoryGb() / nodes.size())
+                                       .withDiskGb(sum.diskGb() / nodes.size())
+                                       .withBandwidthGbps(sum.bandwidthGbps() / nodes.size());
     }
 
     public static Optional<AllocatableClusterResources> from(ClusterResources wantedResources,
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/AutoscalingMaintainer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/AutoscalingMaintainer.java
index fa8e8375e23..c32b7854d4e 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/AutoscalingMaintainer.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/AutoscalingMaintainer.java
@@ -85,7 +85,7 @@ public class AutoscalingMaintainer extends NodeRepositoryMaintainer {
         int currentGroups = (int)clusterNodes.stream().map(node -> node.allocation().get().membership().cluster().group()).distinct().count();
         ClusterSpec.Type clusterType = clusterNodes.get(0).allocation().get().membership().cluster().type();
         log.info("Autoscaling " + application + " " + clusterType + " " + clusterId + ":" +
-                 "\nfrom " + toString(clusterNodes.size(), currentGroups, clusterNodes.get(0).flavor().resources()) +
+                 "\nfrom " + toString(clusterNodes.size(), currentGroups, clusterNodes.get(0).resources()) +
                  "\nto   " + toString(target.nodes(), target.groups(), target.nodeResources()));
     }
 
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/CapacityChecker.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/CapacityChecker.java
index 97253df900b..97810c0b329 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/CapacityChecker.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/CapacityChecker.java
@@ -136,7 +136,7 @@ public class CapacityChecker {
             int occupiedIps = 0;
             Set<String> ipPool = host.ipAddressPool().asSet();
             for (var child : nodeChildren.get(host)) {
-                hostResources = hostResources.subtract(child.flavor().resources().justNumbers());
+                hostResources = hostResources.subtract(child.resources().justNumbers());
                 occupiedIps += child.ipAddresses().stream().filter(ipPool::contains).count();
             }
             availableResources.put(host, new AllocationResources(hostResources, host.ipAddressPool().asSet().size() - occupiedIps));
@@ -250,7 +250,7 @@ public class CapacityChecker {
                 long eligibleParents =
                     hosts.stream().filter(h ->
                             !violatesParentHostPolicy(node, h, containedAllocations)
-                                && availableResources.get(h).satisfies(AllocationResources.from(node.flavor().resources()))).count();
+                                && availableResources.get(h).satisfies(AllocationResources.from(node.resources()))).count();
                 allocationHistory.addEntry(node, newParent.get(), eligibleParents + 1);
             }
         }
@@ -302,7 +302,7 @@ public class CapacityChecker {
             reason.violatesParentHostPolicy = violatesParentHostPolicy(node, host, containedAllocations);
 
             NodeResources l = availableHostResources.nodeResources;
-            NodeResources r = node.allocation().map(Allocation::requestedResources).orElse(node.flavor().resources());
+            NodeResources r = node.allocation().map(Allocation::requestedResources).orElse(node.resources());
 
             if (l.vcpu() < r.vcpu())
                 reason.insufficientVcpu = true;
@@ -391,7 +391,7 @@ public class CapacityChecker {
             if (node.allocation().isPresent())
                 return from(node.allocation().get().requestedResources());
             else
-                return from(node.flavor().resources());
+                return from(node.resources());
         }
 
         public static AllocationResources from(NodeResources nodeResources) {
@@ -514,7 +514,7 @@ public class CapacityChecker {
             public String toString() {
                 return String.format("%-20s %-65s -> %15s [%3d valid]",
                         tenant.hostname().replaceFirst("\\..+", ""),
-                        tenant.flavor().resources(),
+                        tenant.resources(),
                         newParent == null ? "x" : newParent.hostname().replaceFirst("\\..+", ""),
                         this.eligibleParents
                 );
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/MaintenanceDeployment.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/MaintenanceDeployment.java
index b006b2f964b..db331e88d64 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/MaintenanceDeployment.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/MaintenanceDeployment.java
@@ -131,14 +131,19 @@ class MaintenanceDeployment implements Closeable {
 
     public static class Move {
 
-        final Node node;
-        final Node toHost;
+        private final Node node;
+        private final Node fromHost, toHost;
 
-        Move(Node node, Node toHost) {
+        Move(Node node, Node fromHost, Node toHost) {
             this.node = node;
+            this.fromHost = fromHost;
             this.toHost = toHost;
         }
 
+        public Node node() { return node; }
+        public Node fromHost() { return fromHost; }
+        public Node toHost() { return toHost; }
+
         /**
          * Try to deploy to make this move.
          *
@@ -197,10 +202,10 @@ class MaintenanceDeployment implements Closeable {
         @Override
         public String toString() {
             return "move " +
-                   ( isEmpty() ? "none" : (node.hostname() + " to " + toHost));
+                   ( isEmpty() ? "none" : (node.hostname() + " from " + fromHost + " to " + toHost));
         }
 
-        public static Move empty() { return new Move(null, null); }
+        public static Move empty() { return new Move(null, null, null); }
 
     }
 
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRepositoryMaintenance.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRepositoryMaintenance.java
index caf845d36cb..c3f8afae4a4 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRepositoryMaintenance.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRepositoryMaintenance.java
@@ -88,7 +88,7 @@ public class NodeRepositoryMaintenance extends AbstractComponent {
                 new LoadBalancerExpirer(nodeRepository, defaults.loadBalancerExpirerInterval, lbService));
         dynamicProvisioningMaintainer = provisionServiceProvider.getHostProvisioner().map(hostProvisioner ->
                 new DynamicProvisioningMaintainer(nodeRepository, defaults.dynamicProvisionerInterval, hostProvisioner, flagSource));
-        spareCapacityMaintainer = new SpareCapacityMaintainer(deployer, nodeRepository, metric, clock, defaults.spareCapacityMaintenanceInterval);
+        spareCapacityMaintainer = new SpareCapacityMaintainer(deployer, nodeRepository, metric, defaults.spareCapacityMaintenanceInterval);
         osUpgradeActivator = new OsUpgradeActivator(nodeRepository, defaults.osUpgradeActivatorInterval);
         rebalancer = new Rebalancer(deployer, nodeRepository, metric, clock, defaults.rebalancerInterval);
         nodeMetricsDbMaintainer = new NodeMetricsDbMaintainer(nodeRepository, nodeMetrics, nodeMetricsDb, defaults.nodeMetricsCollectionInterval);
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/Rebalancer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/Rebalancer.java
index da3b9bd0e65..e10ac68fde0 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/Rebalancer.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/Rebalancer.java
@@ -6,16 +6,14 @@ import com.yahoo.config.provision.Deployer;
 import com.yahoo.config.provision.NodeResources;
 import com.yahoo.config.provision.NodeType;
 import com.yahoo.jdisc.Metric;
-import com.yahoo.transaction.Mutex;
 import com.yahoo.vespa.hosted.provision.Node;
 import com.yahoo.vespa.hosted.provision.NodeList;
 import com.yahoo.vespa.hosted.provision.NodeRepository;
 import com.yahoo.vespa.hosted.provision.node.Agent;
-import com.yahoo.vespa.hosted.provision.provisioning.DockerHostCapacity;
+import com.yahoo.vespa.hosted.provision.provisioning.HostCapacity;
 
 import java.time.Clock;
 import java.time.Duration;
-import java.util.Optional;
 
 /**
  * @author bratseth
@@ -53,7 +51,7 @@ public class Rebalancer extends NodeRepositoryMaintainer {
 
     /** We do this here rather than in MetricsReporter because it is expensive and frequent updates are unnecessary */
     private void updateSkewMetric(NodeList allNodes) {
-        DockerHostCapacity capacity = new DockerHostCapacity(allNodes, nodeRepository().resourcesCalculator());
+        HostCapacity capacity = new HostCapacity(allNodes, nodeRepository().resourcesCalculator());
         double totalSkew = 0;
         int hostCount = 0;
         for (Node host : allNodes.nodeType((NodeType.host)).state(Node.State.active)) {
@@ -75,7 +73,7 @@ public class Rebalancer extends NodeRepositoryMaintainer {
      * Returns Move.none if no moves can be made to reduce skew.
      */
     private Move findBestMove(NodeList allNodes) {
-        DockerHostCapacity capacity = new DockerHostCapacity(allNodes, nodeRepository().resourcesCalculator());
+        HostCapacity capacity = new HostCapacity(allNodes, nodeRepository().resourcesCalculator());
         Move bestMove = Move.empty();
         for (Node node : allNodes.nodeType(NodeType.tenant).state(Node.State.active)) {
             if (node.parentHostname().isEmpty()) continue;
@@ -84,29 +82,29 @@ public class Rebalancer extends NodeRepositoryMaintainer {
             if (deployedRecently(applicationId)) continue;
             for (Node toHost : allNodes.matching(nodeRepository()::canAllocateTenantNodeTo)) {
                 if (toHost.hostname().equals(node.parentHostname().get())) continue;
-                if ( ! capacity.freeCapacityOf(toHost).satisfies(node.flavor().resources())) continue;
+                if ( ! capacity.freeCapacityOf(toHost).satisfies(node.resources())) continue;
 
                 double skewReductionAtFromHost = skewReductionByRemoving(node, allNodes.parentOf(node).get(), capacity);
                 double skewReductionAtToHost = skewReductionByAdding(node, toHost, capacity);
                 double netSkewReduction = skewReductionAtFromHost + skewReductionAtToHost;
                 if (netSkewReduction > bestMove.netSkewReduction)
-                    bestMove = new Move(node, toHost, netSkewReduction);
+                    bestMove = new Move(node, nodeRepository().getNode(node.parentHostname().get()).get(), toHost, netSkewReduction);
             }
         }
         return bestMove;
     }
 
-    private double skewReductionByRemoving(Node node, Node fromHost, DockerHostCapacity capacity) {
+    private double skewReductionByRemoving(Node node, Node fromHost, HostCapacity capacity) {
         NodeResources freeHostCapacity = capacity.freeCapacityOf(fromHost);
         double skewBefore = Node.skew(fromHost.flavor().resources(), freeHostCapacity);
         double skewAfter = Node.skew(fromHost.flavor().resources(), freeHostCapacity.add(node.flavor().resources().justNumbers()));
         return skewBefore - skewAfter;
     }
 
-    private double skewReductionByAdding(Node node, Node toHost, DockerHostCapacity capacity) {
+    private double skewReductionByAdding(Node node, Node toHost, HostCapacity capacity) {
         NodeResources freeHostCapacity = capacity.freeCapacityOf(toHost);
         double skewBefore = Node.skew(toHost.flavor().resources(), freeHostCapacity);
-        double skewAfter = Node.skew(toHost.flavor().resources(), freeHostCapacity.subtract(node.flavor().resources().justNumbers()));
+        double skewAfter = Node.skew(toHost.flavor().resources(), freeHostCapacity.subtract(node.resources().justNumbers()));
         return skewBefore - skewAfter;
     }
 
@@ -122,20 +120,19 @@ public class Rebalancer extends NodeRepositoryMaintainer {
 
         final double netSkewReduction;
 
-        Move(Node node, Node toHost, double netSkewReduction) {
-            super(node, toHost);
+        Move(Node node, Node fromHost, Node toHost, double netSkewReduction) {
+            super(node, fromHost, toHost);
             this.netSkewReduction = netSkewReduction;
         }
 
         @Override
         public String toString() {
-            return "move " +
-                   ( node == null ? "none" :
-                                    (node.hostname() + " to " + toHost + " [skew reduction "  + netSkewReduction + "]"));
+            if (isEmpty()) return "move none";
+            return super.toString() + " [skew reduction "  + netSkewReduction + "]";
         }
 
         public static Move empty() {
-            return new Move(null, null, 0);
+            return new Move(null, null, null, 0);
         }
 
     }
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/SpareCapacityMaintainer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/SpareCapacityMaintainer.java
index c0e39b39e94..4179d6d3f83 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/SpareCapacityMaintainer.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/SpareCapacityMaintainer.java
@@ -2,15 +2,21 @@
 package com.yahoo.vespa.hosted.provision.maintenance;
 
 import com.yahoo.config.provision.Deployer;
+import com.yahoo.config.provision.NodeResources;
 import com.yahoo.jdisc.Metric;
 import com.yahoo.vespa.hosted.provision.Node;
 import com.yahoo.vespa.hosted.provision.NodeList;
 import com.yahoo.vespa.hosted.provision.NodeRepository;
+import com.yahoo.vespa.hosted.provision.maintenance.MaintenanceDeployment.Move;
+import com.yahoo.vespa.hosted.provision.node.Agent;
+import com.yahoo.vespa.hosted.provision.provisioning.HostCapacity;
 
-import java.time.Clock;
 import java.time.Duration;
+import java.util.ArrayList;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Optional;
+import java.util.Set;
 import java.util.logging.Level;
 import java.util.stream.Collectors;
 
@@ -29,19 +35,18 @@ import java.util.stream.Collectors;
  */
 public class SpareCapacityMaintainer extends NodeRepositoryMaintainer {
 
+    private static final int maxMoves = 5;
+
     private final Deployer deployer;
     private final Metric metric;
-    private final Clock clock;
 
     public SpareCapacityMaintainer(Deployer deployer,
                                    NodeRepository nodeRepository,
                                    Metric metric,
-                                   Clock clock,
                                    Duration interval) {
         super(nodeRepository, interval);
         this.deployer = deployer;
         this.metric = metric;
-        this.clock = clock;
     }
 
     @Override
@@ -60,46 +65,194 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer {
 
         Optional<CapacityChecker.HostFailurePath> failurePath = capacityChecker.worstCaseHostLossLeadingToFailure();
         if (failurePath.isPresent()) {
-            int worstCaseHostLoss = failurePath.get().hostsCausingFailure.size();
-            metric.set("spareHostCapacity", worstCaseHostLoss - 1, null);
-            if (worstCaseHostLoss == 1) { // Try to get back to needing 2 hosts to fail in the worst case
-                Optional<Move> moveCandidate = identifyMoveCandidate(failurePath.get());
-                if (moveCandidate.isPresent())
-                    move(moveCandidate.get());
+            int spareHostCapacity = failurePath.get().hostsCausingFailure.size() - 1;
+            if (spareHostCapacity == 0) {
+                Move move = findMitigatingMove(failurePath.get());
+                boolean success = move.execute(Agent.SpareCapacityMaintainer, deployer, metric, nodeRepository());
+                if (success) {
+                    // This may strictly be a (noble) lie: We succeeded in taking one step to mitigate,
+                    // but not necessarily *all* steps needed to justify adding 1 to spare capacity.
+                    // However, we alert on this being 0 and we don't want to do that as long as we're not stuck.
+                    spareHostCapacity++;
+                }
             }
+            metric.set("spareHostCapacity", spareHostCapacity, null);
         }
     }
 
-    private Optional<Move> identifyMoveCandidate(CapacityChecker.HostFailurePath failurePath) {
+    private Move findMitigatingMove(CapacityChecker.HostFailurePath failurePath) {
         Optional<Node> nodeWhichCantMove = failurePath.failureReason.tenant;
-        if (nodeWhichCantMove.isEmpty()) return Optional.empty();
-        return findMoveWhichMakesRoomFor(nodeWhichCantMove.get());
+        if (nodeWhichCantMove.isEmpty()) return Move.empty();
+        return moveTowardsSpareFor(nodeWhichCantMove.get());
     }
 
-    private Optional<Move> findMoveWhichMakesRoomFor(Node node) {
-        return Optional.empty();
+    private Move moveTowardsSpareFor(Node node) {
+        NodeList allNodes = nodeRepository().list();
+        // Allocation will assign the two most empty nodes as "spares", which will not be allocated on
+        // unless needed for node failing. Our goal here is to make room on these spares for the given node
+        HostCapacity hostCapacity = new HostCapacity(allNodes, nodeRepository().resourcesCalculator());
+        Set<Node> spareHosts = hostCapacity.findSpareHosts(allNodes.hosts().satisfies(node.resources()).asList(), 2);
+        List<Node> hosts = allNodes.hosts().except(spareHosts).asList();
+
+        CapacitySolver capacitySolver = new CapacitySolver(hostCapacity);
+        List<Move> shortestMitigation = null;
+        for (Node spareHost : spareHosts) {
+            List<Move> mitigation = capacitySolver.makeRoomFor(node, spareHost, hosts, List.of(), maxMoves);
+            if (mitigation == null) continue;
+            if (shortestMitigation == null || shortestMitigation.size() > mitigation.size())
+                shortestMitigation = mitigation;
+        }
+        if (shortestMitigation == null || shortestMitigation.isEmpty()) return Move.empty();
+        return shortestMitigation.get(0);
     }
 
-    private void move(Move move) {
+    private static class CapacitySolver {
+
+        private final HostCapacity hostCapacity;
+
+        CapacitySolver(HostCapacity hostCapacity) {
+            this.hostCapacity = hostCapacity;
+        }
+
+        /**
+         * Finds the shortest sequence of moves which makes room for the given node on the given host,
+         * assuming the given moves already made over the given hosts' current allocation.
+         *
+         * @param node the node to make room for
+         * @param host the target host to make room on
+         * @param hosts the hosts onto which we can move nodes
+         * @param movesMade the moves already made in this scenario
+         * @return the list of movesMade with the moves needed for this appended, in the order they should be performed,
+         *         or null if no sequence could be found
+         */
+        List<Move> makeRoomFor(Node node, Node host, List<Node> hosts, List<Move> movesMade, int movesLeft) {
+            if ( ! host.resources().satisfies(node.resources())) return null;
+            NodeResources freeCapacity = freeCapacityWith(movesMade, host);
+            if (freeCapacity.satisfies(node.resources())) return List.of();
+            if (movesLeft == 0) return null;
+
+            List<Move> shortest = null;
+            for (var i = Subsets(hostCapacity.allNodes().childrenOf(host), movesLeft); i.hasNext(); ) {
+                List<Node> childrenToMove = i.next();
+                if ( ! addResourcesOf(childrenToMove, freeCapacity).satisfies(node.resources())) continue;
+                List<Move> moves = move(childrenToMove, host, hosts, movesMade, movesLeft);
+                if (moves == null) continue;
+                if (shortest == null || moves.size() < shortest.size())
+                    shortest = moves;
+            }
+            if (shortest == null) return null;
+            List<Move> total = append(movesMade, shortest);
+            if (total.size() > movesLeft) return null;
+            return total;
+        }
+
+        private List<Move> move(List<Node> nodes, Node host, List<Node> hosts, List<Move> movesMade, int movesLeft) {
+            List<Move> moves = new ArrayList<>();
+            for (Node childToMove : nodes) {
+                List<Move> childMoves = move(childToMove, host, hosts, append(movesMade, moves), movesLeft - moves.size());
+                if (childMoves == null) return null;
+                moves.addAll(childMoves);
+                if (moves.size() > movesLeft) return null;
+            }
+            return moves;
+        }
+
+        private List<Move> move(Node node, Node host, List<Node> hosts, List<Move> movesMade, int movesLeft) {
+            List<Move> shortest = null;
+            for (Node target : hosts) {
+                List<Move> childMoves = makeRoomFor(node, target, hosts, movesMade, movesLeft - 1);
+                if (childMoves == null) continue;
+                if (shortest == null || shortest.size() > childMoves.size() + 1) {
+                    shortest = new ArrayList<>(childMoves);
+                    shortest.add(new Move(node, host, target));
+                }
+            }
+            return shortest;
+        }
+
+        private NodeResources addResourcesOf(List<Node> nodes, NodeResources resources) {
+            for (Node node : nodes)
+                resources = resources.add(node.resources());
+            return resources;
+        }
+
+        private Iterator<List<Node>> Subsets(NodeList nodes, int maxLength) {
+            return new SubsetIterator(nodes.asList(), maxLength);
+        }
+
+        private List<Move> append(List<Move> a, List<Move> b) {
+            List<Move> list = new ArrayList<>();
+            list.addAll(a);
+            list.addAll(b);
+            return list;
+        }
+
+        private NodeResources freeCapacityWith(List<Move> moves, Node host) {
+            NodeResources resources = hostCapacity.freeCapacityOf(host);
+            for (Move move : moves) {
+                if ( ! move.toHost().equals(host)) continue;
+                resources = resources.subtract(move.node().resources());
+            }
+            for (Move move : moves) {
+                if ( ! move.fromHost().equals(host)) continue;
+                resources = resources.add(move.fromHost().resources());
+            }
+            return resources;
+        }
 
     }
 
-    private static class Move {
+    private static class SubsetIterator implements Iterator<List<Node>> {
+
+        private final List<Node> nodes;
+        private final int maxLength;
+
+        // A number whose binary representation determines which items of list we'll include
+        private int i = 0; // first "previous" = 0 -> skip the empty set
+        private List<Node> next = null;
 
-        static final Move none = new Move(null, null);
+        public SubsetIterator(List<Node> nodes, int maxLength) {
+            this.nodes = new ArrayList<>(nodes.subList(0, Math.min(nodes.size(), 31)));
+            this.maxLength = maxLength;
+        }
+
+        @Override
+        public boolean hasNext() {
+            if (next != null) return true;
 
-        final Node node;
-        final Node toHost;
+            // find next
+            while (++i < 1<<nodes.size()) {
+                int ones = onesIn(i);
+                if (ones > maxLength) continue;
 
-        Move(Node node, Node toHost) {
-            this.node = node;
-            this.toHost = toHost;
+                next = new ArrayList<>(ones);
+                for (int position = 0; position < nodes.size(); position++) {
+                    if (hasOneAtPosition(position, i))
+                        next.add(nodes.get(position));
+                }
+                return true;
+            }
+            return false;
         }
 
         @Override
-        public String toString() {
-            return "move " +
-                   ( node == null ? "none" : (node.hostname() + " to " + toHost));
+        public List<Node> next() {
+            next = null;
+            if ( ! hasNext()) throw new IllegalStateException("No more elements");
+            return next;
+        }
+
+        private boolean hasOneAtPosition(int position, int number) {
+            return (number & (1 << position)) > 0;
+        }
+
+        private int onesIn(int number) {
+            int ones = 0;
+            for (int position = 0; Math.pow(2, position) <= number; position++) {
+                if (hasOneAtPosition(position, number))
+                    ones++;
+            }
+            return ones;
         }
 
     }
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/node/Agent.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/node/Agent.java
index 31b7181a58a..eba9e4a1ac9 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/node/Agent.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/node/Agent.java
@@ -21,6 +21,7 @@ public enum Agent {
     ProvisionedExpirer,
     ReservationExpirer,
     DynamicProvisioningMaintainer,
-    RetiringUpgrader;
+    RetiringUpgrader,
+    SpareCapacityMaintainer
 
 }
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/Activator.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/Activator.java
index ebe9327967e..7ad69d673e7 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/Activator.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/Activator.java
@@ -184,12 +184,12 @@ class Activator {
         for (Node node : nodes) {
             HostSpec hostSpec = getHost(node.hostname(), hosts);
             node = hostSpec.membership().get().retired() ? node.retire(nodeRepository.clock().instant()) : node.unretire();
-            if (! hostSpec.advertisedResources().equals(node.flavor().resources())) // A resized node
+            if (! hostSpec.advertisedResources().equals(node.resources())) // A resized node
                 node = node.with(new Flavor(hostSpec.advertisedResources()));
             Allocation allocation = node.allocation().get()
                                         .with(hostSpec.membership().get())
                                         .withRequestedResources(hostSpec.requestedResources()
-                                                                        .orElse(node.flavor().resources()));
+                                                                        .orElse(node.resources()));
             if (hostSpec.networkPorts().isPresent())
                 allocation = allocation.withNetworkPorts(hostSpec.networkPorts().get());
             node = node.with(allocation);
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/EmptyProvisionServiceProvider.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/EmptyProvisionServiceProvider.java
index e4b1e0fcbc0..004c74b5f70 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/EmptyProvisionServiceProvider.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/EmptyProvisionServiceProvider.java
@@ -34,7 +34,7 @@ public class EmptyProvisionServiceProvider implements ProvisionServiceProvider {
     private static class IdentityHostResourcesCalculator implements HostResourcesCalculator {
 
         @Override
-        public NodeResources realResourcesOf(Node node, NodeRepository repository) { return node.flavor().resources(); }
+        public NodeResources realResourcesOf(Node node, NodeRepository repository) { return node.resources(); }
 
         @Override
         public NodeResources advertisedResourcesOf(Flavor flavor) { return flavor.resources(); }
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/HostCapacity.java
index b508198db3a..4125345d492 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/HostCapacity.java
@@ -3,10 +3,14 @@ package com.yahoo.vespa.hosted.provision.provisioning;
 
 import com.yahoo.config.provision.NodeResources;
 import com.yahoo.config.provision.NodeType;
+import com.yahoo.vespa.hosted.provision.LockedNodeList;
 import com.yahoo.vespa.hosted.provision.Node;
 import com.yahoo.vespa.hosted.provision.NodeList;
 
+import java.util.List;
 import java.util.Objects;
+import java.util.Set;
+import java.util.stream.Collectors;
 
 /**
  * Capacity calculation for docker hosts.
@@ -16,17 +20,38 @@ import java.util.Objects;
  *
  * @author smorgrav
  */
-public class DockerHostCapacity {
+public class HostCapacity {
 
     private final NodeList allNodes;
     private final HostResourcesCalculator hostResourcesCalculator;
 
-    public DockerHostCapacity(NodeList allNodes, HostResourcesCalculator hostResourcesCalculator) {
+    public HostCapacity(NodeList allNodes, HostResourcesCalculator hostResourcesCalculator) {
         this.allNodes = Objects.requireNonNull(allNodes, "allNodes must be non-null");
         this.hostResourcesCalculator = Objects.requireNonNull(hostResourcesCalculator, "hostResourcesCalculator must be non-null");
     }
 
-    int compareWithoutInactive(Node hostA, Node hostB) {
+    public NodeList allNodes() { return allNodes; }
+
+    /**
+     * Spare hosts are the two hosts in the system with the most free capacity.
+     *
+     * We do not count retired or inactive nodes as used capacity (as they could have been
+     * moved to create space for the spare node in the first place).
+     *
+     * @param candidates the candidates to consider. This list may contain all kinds of nodes.
+     * @param count the max number of spare hosts to return
+     */
+    public Set<Node> findSpareHosts(List<Node> candidates, int count) {
+        return candidates.stream()
+                         .filter(node -> node.type() == NodeType.host)
+                         .filter(dockerHost -> dockerHost.state() == Node.State.active)
+                         .filter(dockerHost -> freeIPs(dockerHost) > 0)
+                         .sorted(this::compareWithoutInactive)
+                         .limit(count)
+                         .collect(Collectors.toSet());
+    }
+
+    private int compareWithoutInactive(Node hostA, Node hostB) {
         int result = compare(freeCapacityOf(hostB, true), freeCapacityOf(hostA, true));
         if (result != 0) return result;
 
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeAllocation.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeAllocation.java
index 47d1b30a8e7..df8a7e45917 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeAllocation.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeAllocation.java
@@ -148,7 +148,7 @@ class NodeAllocation {
                 }
                 node.node = offered.allocate(application,
                                              ClusterMembership.from(cluster, highestIndex.add(1)),
-                                             requestedNodes.resources().orElse(node.node.flavor().resources()),
+                                             requestedNodes.resources().orElse(node.node.resources()),
                                              nodeRepository.clock().instant());
                 accepted.add(acceptNode(node, false, false));
             }
@@ -242,7 +242,7 @@ class NodeAllocation {
         Node node = prioritizableNode.node;
 
         if (node.allocation().isPresent()) // Record the currently requested resources
-            node = node.with(node.allocation().get().withRequestedResources(requestedNodes.resources().orElse(node.flavor().resources())));
+            node = node.with(node.allocation().get().withRequestedResources(requestedNodes.resources().orElse(node.resources())));
 
         if (! wantToRetire) {
             accepted++;
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 5e297900767..8560dd424e7 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
@@ -13,7 +13,6 @@ import com.yahoo.vespa.hosted.provision.Node;
 import com.yahoo.vespa.hosted.provision.NodeList;
 import com.yahoo.vespa.hosted.provision.NodeRepository;
 import com.yahoo.vespa.hosted.provision.node.IP;
-import com.yahoo.vespa.hosted.provision.persistence.NameResolver;
 
 import java.util.EnumSet;
 import java.util.HashMap;
@@ -21,7 +20,6 @@ import java.util.List;
 import java.util.Map;
 import java.util.Optional;
 import java.util.Set;
-import java.util.function.Predicate;
 import java.util.logging.Logger;
 import java.util.stream.Collectors;
 
@@ -39,7 +37,7 @@ public class NodePrioritizer {
 
     private final Map<Node, PrioritizableNode> nodes = new HashMap<>();
     private final LockedNodeList allNodes;
-    private final DockerHostCapacity capacity;
+    private final HostCapacity capacity;
     private final NodeSpec requestedNodes;
     private final ApplicationId application;
     private final ClusterSpec clusterSpec;
@@ -55,11 +53,11 @@ public class NodePrioritizer {
     NodePrioritizer(LockedNodeList allNodes, ApplicationId application, ClusterSpec clusterSpec, NodeSpec nodeSpec,
                     int spares, int wantedGroups, boolean allocateFully, NodeRepository nodeRepository) {
         this.allNodes = allNodes;
-        this.capacity = new DockerHostCapacity(allNodes, nodeRepository.resourcesCalculator());
+        this.capacity = new HostCapacity(allNodes, nodeRepository.resourcesCalculator());
         this.requestedNodes = nodeSpec;
         this.clusterSpec = clusterSpec;
         this.application = application;
-        this.spareHosts = findSpareHosts(allNodes, capacity, spares);
+        this.spareHosts = capacity.findSpareHosts(allNodes.asList(), spares);
         this.allocateFully = allocateFully;
         this.nodeRepository = nodeRepository;
 
@@ -83,22 +81,6 @@ public class NodePrioritizer {
         this.isDocker = resources(requestedNodes) != null;
     }
 
-    /**
-     * Spare hosts are the two hosts in the system with the most free capacity.
-     *
-     * We do not count retired or inactive nodes as used capacity (as they could have been
-     * moved to create space for the spare node in the first place).
-     */
-    private static Set<Node> findSpareHosts(LockedNodeList nodes, DockerHostCapacity capacity, int spares) {
-        return nodes.asList().stream()
-                    .filter(node -> node.type() == NodeType.host)
-                    .filter(dockerHost -> dockerHost.state() == Node.State.active)
-                    .filter(dockerHost -> capacity.freeIPs(dockerHost) > 0)
-                    .sorted(capacity::compareWithoutInactive)
-                    .limit(spares)
-                    .collect(Collectors.toSet());
-    }
-
     /** Returns the list of nodes sorted by PrioritizableNode::compare */
     List<PrioritizableNode> prioritize() {
         return nodes.values().stream().sorted().collect(Collectors.toList());
@@ -207,7 +189,7 @@ public class NodePrioritizer {
 
             if (!isNewNode)
                 builder.resizable(! allocateFully
-                                  && requestedNodes.canResize(node.flavor().resources(), parentCapacity, isTopologyChange, currentClusterSize));
+                                  && requestedNodes.canResize(node.resources(), parentCapacity, isTopologyChange, currentClusterSize));
 
             if (spareHosts.contains(parent))
                 builder.violatesSpares(true);
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeSpec.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeSpec.java
index a8abdc3f38a..9971aae1714 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeSpec.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeSpec.java
@@ -139,7 +139,7 @@ public interface NodeSpec {
 
         @Override
         public boolean needsResize(Node node) {
-            return ! node.flavor().resources().compatibleWith(requestedNodeResources);
+            return ! node.resources().compatibleWith(requestedNodeResources);
         }
 
         @Override
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 3fc60c1192d..0c1b396c40c 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
@@ -126,7 +126,7 @@ class PrioritizableNode implements Comparable<PrioritizableNode> {
     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()); }
+    double skewWithThis() { return skewWith(node.resources()); }
 
     private double skewWith(NodeResources resources) {
         if (parent.isEmpty()) return 0;
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/restapi/ApplicationSerializer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/restapi/ApplicationSerializer.java
index aa81aae84fe..a4161a318ab 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/restapi/ApplicationSerializer.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/restapi/ApplicationSerializer.java
@@ -43,7 +43,7 @@ public class ApplicationSerializer {
         if (nodes.isEmpty()) return;
 
         int groups = (int)nodes.stream().map(node -> node.allocation().get().membership().cluster().group()).distinct().count();
-        ClusterResources currentResources = new ClusterResources(nodes.size(), groups, nodes.get(0).flavor().resources());
+        ClusterResources currentResources = new ClusterResources(nodes.size(), groups, nodes.get(0).resources());
 
         toSlime(cluster.minResources(), clusterObject.setObject("min"));
         toSlime(cluster.maxResources(), clusterObject.setObject("max"));
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/restapi/HostCapacityResponse.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/restapi/HostCapacityResponse.java
index 7e81a9cc002..e28b03d7517 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/restapi/HostCapacityResponse.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/restapi/HostCapacityResponse.java
@@ -129,7 +129,7 @@ public class HostCapacityResponse extends HttpResponse {
         );
         failurePath.failureReason.tenant.ifPresent(tenant -> {
             object.setString("failedTenant", tenant.hostname());
-            object.setString("failedTenantResources", tenant.flavor().resources().toString());
+            object.setString("failedTenantResources", tenant.resources().toString());
             tenant.allocation().ifPresent(allocation ->
                     object.setString("failedTenantAllocation", allocation.toString())
             );