diff options
author | Jon Bratseth <bratseth@gmail.com> | 2020-06-17 17:02:30 +0200 |
---|---|---|
committer | Jon Bratseth <bratseth@gmail.com> | 2020-06-17 17:02:30 +0200 |
commit | d589e157fce08e509011ba3ede109c7d71b327d6 (patch) | |
tree | b5cca09ea95efb8b32053b1acdaa0e65415a3cc4 /node-repository | |
parent | b4c0044429359f984b7927ae04ffbe416ce6bc4a (diff) |
Limit by iterations instead of depth
Diffstat (limited to 'node-repository')
2 files changed, 68 insertions, 54 deletions
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 8578e07f3b3..7fb6f929cb7 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 @@ -38,7 +38,7 @@ import java.util.stream.Collectors; */ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer { - private static final int maxIterations = 5; // Should take a couple of seconds + private final int maxIterations; private final Deployer deployer; private final Metric metric; @@ -46,9 +46,20 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer { NodeRepository nodeRepository, Metric metric, Duration interval) { + this(deployer, nodeRepository, metric, interval, + 1_000_000 // Should take a couple of seconds + ); + } + + public SpareCapacityMaintainer(Deployer deployer, + NodeRepository nodeRepository, + Metric metric, + Duration interval, + int maxIterations) { super(nodeRepository, interval); this.deployer = deployer; this.metric = metric; + this.maxIterations = maxIterations; } @Override @@ -98,10 +109,10 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer { 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); + CapacitySolver capacitySolver = new CapacitySolver(hostCapacity, maxIterations); List<Move> shortestMitigation = null; for (Node spareHost : spareHosts) { - List<Move> mitigation = capacitySolver.makeRoomFor(node, spareHost, hosts, List.of(), maxIterations); + List<Move> mitigation = capacitySolver.makeRoomFor(node, spareHost, hosts, List.of(), List.of()); if (mitigation == null) continue; if (shortestMitigation == null || shortestMitigation.size() > mitigation.size()) shortestMitigation = mitigation; @@ -112,15 +123,18 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer { private static class CapacitySolver { - private int iterations = 0; private final HostCapacity hostCapacity; + private final int maxIterations; - CapacitySolver(HostCapacity hostCapacity) { + private int iterations = 0; + + CapacitySolver(HostCapacity hostCapacity, int maxIterations) { this.hostCapacity = hostCapacity; + this.maxIterations = maxIterations; } - /** The map of subproblem solutions already found. */ - private Map<SolutionKey, Solution> solutions = new HashMap<>(); + /** The map of subproblem solutions already found. The value is null when there is no solution. */ + private Map<SolutionKey, List<Move>> solutions = new HashMap<>(); /** * Finds the shortest sequence of moves which makes room for the given node on the given host, @@ -129,37 +143,38 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer { * @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 movesConsidered the moves already being considered to add as part of this scenario + * (after any moves made by this) * @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) { - 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); + List<Move> makeRoomFor(Node node, Node host, List<Node> hosts, List<Move> movesConsidered, List<Move> movesMade) { + SolutionKey solutionKey = new SolutionKey(node, host, movesConsidered, movesMade); + List<Move> solution = solutions.get(solutionKey); + if (solution == null) { + solution = findRoomFor(node, host, hosts, movesConsidered, movesMade); solutions.put(solutionKey, solution); } - if (solution.isNone() || solution.moves().size() > movesLeft) - return null; - return solution.moves(); + return solution; } - private List<Move> findRoomFor(Node node, Node host, List<Node> hosts, List<Move> movesMade, int movesLeft) { - iterations++; + private List<Move> findRoomFor(Node node, Node host, List<Node> hosts, + List<Move> movesConsidered, List<Move> movesMade) { + if (iterations++ > maxIterations) + return null; + 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(); - if (movesLeft == 0) return null; List<Move> shortest = null; - for (var i = subsets(hostCapacity.allNodes().childrenOf(host), movesLeft); i.hasNext(); ) { + for (var i = subsets(hostCapacity.allNodes().childrenOf(host), 5); i.hasNext(); ) { List<Node> childrenToMove = i.next(); if ( ! addResourcesOf(childrenToMove, freeCapacity).satisfies(node.resources())) continue; - List<Move> moves = move(childrenToMove, host, hosts, movesMade, movesLeft); + List<Move> moves = move(childrenToMove, host, hosts, movesConsidered, movesMade); if (moves == null) continue; if (shortest == null || moves.size() < shortest.size()) @@ -167,43 +182,48 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer { } 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) { + private List<Move> move(List<Node> nodes, Node host, List<Node> hosts, List<Move> movesConsidered, List<Move> movesMade) { List<Move> moves = new ArrayList<>(); for (Node childToMove : nodes) { - List<Move> childMoves = move(childToMove, host, hosts, append(movesMade, moves), movesLeft - moves.size()); + List<Move> childMoves = move(childToMove, host, hosts, movesConsidered, append(movesMade, moves)); 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) { + private List<Move> move(Node node, Node host, List<Node> hosts, List<Move> movesConsidered, List<Move> movesMade) { + if (contains(node, movesConsidered)) return null; + if (contains(node, movesMade)) return null; List<Move> shortest = null; for (Node target : hosts) { if (target.equals(host)) continue; - List<Move> childMoves = makeRoomFor(node, target, hosts, movesMade, movesLeft - 1); + Move move = new Move(node, host, target); + List<Move> childMoves = makeRoomFor(node, target, hosts, append(movesConsidered, move), movesMade); if (childMoves == null) continue; if (shortest == null || shortest.size() > childMoves.size() + 1) { shortest = new ArrayList<>(childMoves); - shortest.add(new Move(node, host, target)); + shortest.add(move); } } return shortest; } + private boolean contains(Node node, List<Move> moves) { + return moves.stream().anyMatch(move -> move.node().equals(node)); + } + 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 Iterator<List<Node>> subsets(NodeList nodes, int maxSize) { + return new SubsetIterator(nodes.asList(), maxSize); } private List<Move> append(List<Move> a, List<Move> b) { @@ -213,6 +233,12 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer { return list; } + private List<Move> append(List<Move> moves, Move move) { + List<Move> list = new ArrayList<>(moves); + list.add(move); + return list; + } + private NodeResources freeCapacityWith(List<Move> moves, Node host) { NodeResources resources = hostCapacity.freeCapacityOf(host); for (Move move : moves) { @@ -232,16 +258,18 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer { private final Node node; private final Node host; + private final List<Move> movesConsidered; private final List<Move> movesMade; private final int hash; - public SolutionKey(Node node, Node host, List<Move> movesMade) { + public SolutionKey(Node node, Node host, List<Move> movesConsidered, List<Move> movesMade) { this.node = node; this.host = host; + this.movesConsidered = movesConsidered; this.movesMade = movesMade; - hash = Objects.hash(node, host, movesMade); + hash = Objects.hash(node, host, movesConsidered, movesMade); } @Override @@ -255,31 +283,13 @@ public class SpareCapacityMaintainer extends NodeRepositoryMaintainer { SolutionKey other = (SolutionKey)o; if ( ! other.node.equals(this.node)) return false; if ( ! other.host.equals(this.host)) return false; + if ( ! other.movesConsidered.equals(this.movesConsidered)) 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 05d318dbd69..8c945ad4aaa 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 @@ -173,9 +173,9 @@ public class SpareCapacityMaintainerTest { } @Test - public void testTooManyMovesAreNeeded() { + public void testTooManyIterationsAreNeeded() { // 6 nodes must move to the next host, which is more than the max limit - var tester = new SpareCapacityMaintainerTester(); + var tester = new SpareCapacityMaintainerTester(5); tester.addHosts(2, new NodeResources(10, 100, 1000, 1)); tester.addHosts(1, new NodeResources(9, 90, 900, 0.9)); @@ -233,6 +233,10 @@ public class SpareCapacityMaintainerTest { private int nodeIndex = 0; private SpareCapacityMaintainerTester() { + this(1000_000); + } + + private SpareCapacityMaintainerTester(int maxIterations) { NodeFlavors flavors = new NodeFlavors(new FlavorConfigBuilder().build()); nodeRepository = new NodeRepository(flavors, new EmptyProvisionServiceProvider().getHostResourcesCalculator(), @@ -242,7 +246,7 @@ public class SpareCapacityMaintainerTest { new MockNameResolver().mockAnyLookup(), DockerImage.fromString("docker-registry.domain.tld:8080/dist/vespa"), true, false); deployer = new MockDeployer(nodeRepository); - maintainer = new SpareCapacityMaintainer(deployer, nodeRepository, metric, Duration.ofMinutes(1)); + maintainer = new SpareCapacityMaintainer(deployer, nodeRepository, metric, Duration.ofMinutes(1), maxIterations); } private void addHosts(int count, NodeResources resources) { |