Memoize

3 files changed, 120 insertions, 3 deletions

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 2b4775cbeb1..1a15dce283a 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
@@ -7,6 +7,8 @@ import com.yahoo.config.provision.Deployer;
 import com.yahoo.config.provision.Deployment;
 import com.yahoo.config.provision.TransientException;
 import com.yahoo.jdisc.Metric;
+
+import java.util.Objects;
 import java.util.logging.Level;
 import com.yahoo.transaction.Mutex;
 import com.yahoo.vespa.hosted.provision.Node;
@@ -206,6 +208,22 @@ class MaintenanceDeployment implements Closeable {
         public boolean isEmpty() { return node == null; }
 
         @Override
+        public int hashCode() {
+            return Objects.hash(node, fromHost, toHost);
+        }
+
+        public boolean equals(Object o) {
+            if (o == this) return true;
+            if (o == null || o.getClass() != this.getClass()) return false;
+
+            Move other = (Move)o;
+            if ( ! Objects.equals(other.node, this.node)) return false;
+            if ( ! Objects.equals(other.fromHost, this.fromHost)) return false;
+            if ( ! Objects.equals(other.toHost, this.toHost)) return false;
+            return true;
+        }
+
+        @Override
         public String toString() {
             return "move " +
                    ( isEmpty() ? "none" : (node.hostname() + " from " + fromHost + " to " + toHost));
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 a67f0b55b14..8578e07f3b3 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
@@ -13,8 +13,11 @@ import com.yahoo.vespa.hosted.provision.provisioning.HostCapacity;
 
 import java.time.Duration;
 import java.util.ArrayList;
+import java.util.HashMap;
 import java.util.Iterator;
 import java.util.List;
+import java.util.Map;
+import java.util.Objects;
 import java.util.Optional;
 import java.util.Set;
 import java.util.logging.Level;
@@ -35,8 +38,7 @@ import java.util.stream.Collectors;
  */
 public class SpareCapacityMaintainer extends NodeRepositoryMaintainer {
 
-    private static final int maxMoves = 5;
-
+    private static final int maxIterations = 5; // Should take a couple of seconds
     private final Deployer deployer;
     private final Metric metric;
 
@@ -99,7 +101,7 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer {
         CapacitySolver capacitySolver = new CapacitySolver(hostCapacity);
         List<Move> shortestMitigation = null;
         for (Node spareHost : spareHosts) {
-            List<Move> mitigation = capacitySolver.makeRoomFor(node, spareHost, hosts, List.of(), maxMoves);
+            List<Move> mitigation = capacitySolver.makeRoomFor(node, spareHost, hosts, List.of(), maxIterations);
             if (mitigation == null) continue;
             if (shortestMitigation == null || shortestMitigation.size() > mitigation.size())
                 shortestMitigation = mitigation;
@@ -110,12 +112,16 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer {
 
     private static class CapacitySolver {
 
+        private int iterations = 0;
         private final HostCapacity hostCapacity;
 
         CapacitySolver(HostCapacity hostCapacity) {
             this.hostCapacity = hostCapacity;
         }
 
+        /** The map of subproblem solutions already found. */
+        private Map<SolutionKey, Solution> solutions = new HashMap<>();
+
         /**
          * 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.
@@ -128,6 +134,22 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer {
          *         or null if no sequence could be found
          */
         List<Move> makeRoomFor(Node node, Node host, List<Node> hosts, List<Move> movesMade, int movesLeft) {
+            SolutionKey solutionKey = new SolutionKey(node, host, movesMade);
+            Solution solution = solutions.get(solutionKey);
+            if (solution == null || (solution.isNone() && solution.movesLeft() < movesLeft)) {
+                List<Move> moves = findRoomFor(node, host, hosts, movesMade, movesLeft);
+                solution = new Solution(moves, movesLeft);
+                solutions.put(solutionKey, solution);
+            }
+            if (solution.isNone() || solution.moves().size() > movesLeft)
+                return null;
+            return solution.moves();
+        }
+
+        private List<Move> findRoomFor(Node node, Node host, List<Node> hosts, List<Move> movesMade, int movesLeft) {
+            iterations++;
+            if ((iterations % 1000) == 0)
+                System.out.println("  Iteration " + iterations);
             if ( ! host.resources().satisfies(node.resources())) return null;
             NodeResources freeCapacity = freeCapacityWith(movesMade, host);
             if (freeCapacity.satisfies(node.resources())) return List.of();
@@ -206,6 +228,58 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer {
 
     }
 
+    private static class SolutionKey {
+
+        private final Node node;
+        private final Node host;
+        private final List<Move> movesMade;
+
+        private final int hash;
+
+        public SolutionKey(Node node, Node host, List<Move> movesMade) {
+            this.node = node;
+            this.host = host;
+            this.movesMade = movesMade;
+
+            hash = Objects.hash(node, host, movesMade);
+        }
+
+        @Override
+        public int hashCode() { return hash; }
+
+        @Override
+        public boolean equals(Object o) {
+            if (o == this) return true;
+            if (o == null || o.getClass() != this.getClass()) return false;
+
+            SolutionKey other = (SolutionKey)o;
+            if ( ! other.node.equals(this.node)) return false;
+            if ( ! other.host.equals(this.host)) return false;
+            if ( ! other.movesMade.equals(this.movesMade)) return false;
+            return true;
+        }
+
+    }
+
+    private static class Solution {
+
+        /** The moves of this solution, or null if there is none */
+        private final List<Move> moves;
+
+        /** The number of moves considered when finding (or not finding) this solution */
+        private final int movesLeft;
+
+        public Solution(List<Move> moves, int movesLeft) {
+            this.moves = moves;
+            this.movesLeft = movesLeft;
+        }
+
+        public List<Move> moves() { return moves; }
+        public int movesLeft() { return movesLeft; }
+        public boolean isNone() { return moves == null; }
+
+    }
+
     private static class SubsetIterator implements Iterator<List<Node>> {
 
         private final List<Node> nodes;
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/SpareCapacityMaintainerTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/SpareCapacityMaintainerTest.java
index ae8d363934a..05d318dbd69 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/SpareCapacityMaintainerTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/SpareCapacityMaintainerTest.java
@@ -23,6 +23,7 @@ import com.yahoo.vespa.hosted.provision.provisioning.EmptyProvisionServiceProvid
 import com.yahoo.vespa.hosted.provision.provisioning.FlavorConfigBuilder;
 import com.yahoo.vespa.hosted.provision.testutils.MockDeployer;
 import com.yahoo.vespa.hosted.provision.testutils.MockNameResolver;
+import org.junit.Ignore;
 import org.junit.Test;
 
 import java.time.Duration;
@@ -198,6 +199,30 @@ public class SpareCapacityMaintainerTest {
         assertEquals(0, tester.metric.values.get("spareHostCapacity"));
     }
 
+    /** Microbenchmark */
+    @Test
+    @Ignore
+    public void testLargeNodeRepo() {
+        // Completely fill 200 hosts with 2000 nodes
+        int hosts = 200;
+        var tester = new SpareCapacityMaintainerTester();
+        tester.addHosts(hosts, new NodeResources(100, 1000, 10000, 10));
+        int hostOffset = 0;
+        for (int i = 0; i < 200; i++) {
+            int applicationSize = 10;
+            int resourceSize = 10;
+            tester.addNodes(i, applicationSize, new NodeResources(resourceSize, resourceSize * 10, resourceSize * 100, 0.1), hostOffset);
+            hostOffset = (hostOffset + applicationSize) % hosts;
+        }
+        long startTime = System.currentTimeMillis();
+        tester.maintainer.maintain();
+        long totalTime = System.currentTimeMillis() - startTime;
+        System.out.println("Complete in " + ( totalTime / 1000) + " seconds");
+        assertEquals(0, tester.deployer.redeployments);
+        assertEquals(0, tester.nodeRepository.list().retired().size());
+        assertEquals(0, tester.metric.values.get("spareHostCapacity"));
+    }
+
     private static class SpareCapacityMaintainerTester {
 
         NodeRepository nodeRepository;