diff options
author | Jon Bratseth <bratseth@gmail.com> | 2020-06-17 16:25:30 +0200 |
---|---|---|
committer | Jon Bratseth <bratseth@gmail.com> | 2020-06-17 16:25:30 +0200 |
commit | b4c0044429359f984b7927ae04ffbe416ce6bc4a (patch) | |
tree | ff42ea880144e2234ece0990b15aee25dc550377 /node-repository | |
parent | 916e2e9c19025ba8002bb17025b3d975125e4bb7 (diff) |
Memoize
Diffstat (limited to 'node-repository')
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; |