Merge pull request #2337 from yahoo/freva/auto-retire-allocated

Freva/auto retire allocated

7 files changed, 515 insertions, 55 deletions

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 e8672c2003d..013c1425ec0 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
@@ -13,6 +13,7 @@ import com.yahoo.jdisc.Metric;
 import com.yahoo.vespa.curator.Curator;
 import com.yahoo.vespa.hosted.provision.NodeRepository;
 import com.yahoo.vespa.hosted.provision.maintenance.retire.RetireIPv4OnlyNodes;
+import com.yahoo.vespa.hosted.provision.provisioning.FlavorClusters;
 import com.yahoo.vespa.orchestrator.Orchestrator;
 import com.yahoo.vespa.service.monitor.ServiceMonitor;
 
@@ -70,7 +71,9 @@ public class NodeRepositoryMaintenance extends AbstractComponent {
         dirtyExpirer = new DirtyExpirer(nodeRepository, clock, durationFromEnv("dirty_expiry").orElse(defaults.dirtyExpiry), jobControl);
         nodeRebooter = new NodeRebooter(nodeRepository, clock, durationFromEnv("reboot_interval").orElse(defaults.rebootInterval), jobControl);
         metricsReporter = new MetricsReporter(nodeRepository, metric, durationFromEnv("metrics_interval").orElse(defaults.metricsInterval), jobControl);
-        nodeRetirer = new NodeRetirer(nodeRepository, zone, durationFromEnv("retire_interval").orElse(defaults.nodeRetirerInterval), jobControl,
+
+        FlavorClusters flavorClusters = new FlavorClusters(zone.nodeFlavors().get().getFlavors());
+        nodeRetirer = new NodeRetirer(nodeRepository, zone, flavorClusters, durationFromEnv("retire_interval").orElse(defaults.nodeRetirerInterval), jobControl,
                 new RetireIPv4OnlyNodes(),
                 new Zone(SystemName.cd, Environment.dev, RegionName.from("cd-us-central-1")),
                 new Zone(SystemName.cd, Environment.prod, RegionName.from("cd-us-central-1")),
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirer.java
index f855eddf1cf..d662d3a5fef 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirer.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirer.java
@@ -1,15 +1,20 @@
 package com.yahoo.vespa.hosted.provision.maintenance;
 
+import com.yahoo.config.provision.ApplicationId;
 import com.yahoo.config.provision.Flavor;
+import com.yahoo.config.provision.NodeType;
 import com.yahoo.config.provision.Zone;
 import com.yahoo.transaction.Mutex;
 import com.yahoo.vespa.hosted.provision.Node;
 import com.yahoo.vespa.hosted.provision.NodeRepository;
 import com.yahoo.vespa.hosted.provision.maintenance.retire.RetirementPolicy;
 import com.yahoo.vespa.hosted.provision.node.Agent;
+import com.yahoo.vespa.hosted.provision.provisioning.FlavorClusters;
 
 import java.time.Duration;
 import java.util.Arrays;
+import java.util.Comparator;
+import java.util.Iterator;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
@@ -20,11 +25,14 @@ import java.util.stream.Collectors;
  * @author freva
  */
 public class NodeRetirer extends Maintainer {
+    private static final long MAX_SIMULTANEOUS_RETIRES_PER_APPLICATION = 1;
     private static final Logger log = Logger.getLogger(NodeRetirer.class.getName());
+
+    private final FlavorClusters flavorClusters;
     private final RetirementPolicy retirementPolicy;
 
-    public NodeRetirer(NodeRepository nodeRepository, Zone zone, Duration interval, JobControl jobControl,
-                       RetirementPolicy retirementPolicy, Zone... applies) {
+    public NodeRetirer(NodeRepository nodeRepository, Zone zone, FlavorClusters flavorClusters, Duration interval,
+                       JobControl jobControl, RetirementPolicy retirementPolicy, Zone... applies) {
         super(nodeRepository, interval, jobControl);
         if (! Arrays.asList(applies).contains(zone)) {
             String targetZones = Arrays.stream(applies).map(Zone::toString).collect(Collectors.joining(", "));
@@ -33,16 +41,23 @@ public class NodeRetirer extends Maintainer {
         }
 
         this.retirementPolicy = retirementPolicy;
+        this.flavorClusters = flavorClusters;
     }
 
     @Override
     protected void maintain() {
-        retireUnallocated();
+        if (retireUnallocated()) {
+            retireAllocated();
+        }
     }
 
+    /**
+     * Retires unallocated nodes by moving them directly to parked.
+     * Returns true iff all there are no unallocated nodes that match the retirement policy
+     */
     boolean retireUnallocated() {
         try (Mutex lock = nodeRepository().lockUnallocated()) {
-            List<Node> allNodes = nodeRepository().getNodes();
+            List<Node> allNodes = nodeRepository().getNodes(NodeType.tenant);
             Map<Flavor, Long> numSpareNodesByFlavor = getNumberSpareReadyNodesByFlavor(allNodes);
 
             long numFlavorsWithUnsuccessfullyRetiredNodes = allNodes.stream()
@@ -62,6 +77,76 @@ public class NodeRetirer extends Maintainer {
         }
     }
 
+    void retireAllocated() {
+        List<Node> allNodes = nodeRepository().getNodes(NodeType.tenant);
+        List<ApplicationId> activeApplications = getActiveApplicationIds(allNodes);
+        Map<Flavor, Long> numSpareNodesByFlavor = getNumberSpareReadyNodesByFlavor(allNodes);
+
+        for (ApplicationId applicationId : activeApplications) {
+            try (Mutex lock = nodeRepository().lock(applicationId)) {
+                // Get nodes for current application under lock
+                List<Node> applicationNodes = nodeRepository().getNodes(applicationId);
+                Set<Node> retireableNodes = getRetireableNodesForApplication(applicationNodes);
+                long numNodesAllowedToRetire = getNumberNodesAllowToRetireForApplication(applicationNodes, MAX_SIMULTANEOUS_RETIRES_PER_APPLICATION);
+
+                for (Iterator<Node> iterator = retireableNodes.iterator(); iterator.hasNext() && numNodesAllowedToRetire > 0; ) {
+                    Node retireableNode = iterator.next();
+
+                    Set<Flavor> possibleReplacementFlavors = flavorClusters.getFlavorClusterFor(retireableNode.flavor());
+                    Flavor flavorWithMinSpareNodes = getMinAmongstKeys(numSpareNodesByFlavor, possibleReplacementFlavors);
+                    long spareNodesForMinFlavor = numSpareNodesByFlavor.getOrDefault(flavorWithMinSpareNodes, 0L);
+                    if (spareNodesForMinFlavor > 0) {
+                        log.info("Setting node " + retireableNode + " to wantToRetire. Policy: " +
+                                retirementPolicy.getClass().getSimpleName());
+                        Node updatedNode = retireableNode.with(retireableNode.status().withWantToRetire(true));
+                        nodeRepository().write(updatedNode);
+                        numSpareNodesByFlavor.put(flavorWithMinSpareNodes, spareNodesForMinFlavor - 1);
+                        numNodesAllowedToRetire--;
+                    }
+                }
+            }
+        }
+    }
+
+    /**
+     * Returns a list of ApplicationIds sorted by number of active nodes the application has allocated to it
+     */
+    List<ApplicationId> getActiveApplicationIds(List<Node> nodes) {
+        return nodes.stream()
+                .filter(node -> node.state() == Node.State.active)
+                .collect(Collectors.groupingBy(
+                        node -> node.allocation().get().owner(),
+                        Collectors.counting()))
+                .entrySet().stream()
+                .sorted((c1, c2) -> c2.getValue().compareTo(c1.getValue()))
+                .map(Map.Entry::getKey)
+                .collect(Collectors.toList());
+    }
+
+    /**
+     * @param applicationNodes All the nodes allocated to an application
+     * @return Set of nodes that all should eventually be retired
+     */
+    Set<Node> getRetireableNodesForApplication(List<Node> applicationNodes) {
+        return applicationNodes.stream()
+                .filter(node -> node.state() == Node.State.active)
+                .filter(node -> !node.status().wantToRetire())
+                .filter(retirementPolicy::shouldRetire)
+                .collect(Collectors.toSet());
+    }
+
+    /**
+     * @param applicationNodes All the nodes allocated to an application
+     * @return number of nodes we can safely start retiring
+     */
+    long getNumberNodesAllowToRetireForApplication(List<Node> applicationNodes, long maxSimultaneousRetires) {
+        long numNodesInWantToRetire = applicationNodes.stream()
+                .filter(node -> node.status().wantToRetire())
+                .filter(node -> node.state() != Node.State.parked)
+                .count();
+        return Math.max(0, maxSimultaneousRetires - numNodesInWantToRetire);
+    }
+
     /**
      * @param nodesToPark Nodes that we want to park
      * @param limit Maximum number of nodes we want to park
@@ -100,4 +185,15 @@ public class NodeRetirer extends Maintainer {
         long numNodesToSpare = (long) Math.ceil(0.1 * numActiveNodes);
         return Math.max(0L, numReadyNodes - numNodesToSpare);
     }
+
+    /**
+     * Returns the key with the smallest value amongst keys
+     */
+    <K, V extends Comparable<V>> K getMinAmongstKeys(Map<K, V> map, Set<K> keys) {
+        return map.entrySet().stream()
+                .filter(entry -> keys.contains(entry.getKey()))
+                .min(Comparator.comparing(Map.Entry::getValue))
+                .map(Map.Entry::getKey)
+                .orElseThrow(() -> new RuntimeException("No min key found"));
+    }
 }
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorClusters.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorClusters.java
new file mode 100644
index 00000000000..d21c39581a4
--- /dev/null
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorClusters.java
@@ -0,0 +1,60 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.vespa.hosted.provision.provisioning;
+
+import com.yahoo.config.provision.Flavor;
+
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Optional;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+/**
+ * Keeps track of flavor clusters: disjoint set of flavors that are connected through 'replaces'.
+ * Given a node n, which has the flavor x, the flavor cluster of x is the set of flavors that
+ * n could get next time it is redeployed.
+ *
+ * @author freva
+ */
+public class FlavorClusters {
+    final Set<Set<Flavor>> flavorClusters;
+
+    public FlavorClusters(List<Flavor> flavors) {
+        // Make each flavor and its immediate replacements own cluster
+        Set<Set<Flavor>> prevClusters = flavors.stream()
+                .map(flavor -> {
+                    Set<Flavor> cluster = new HashSet<>(flavor.replaces());
+                    cluster.add(flavor);
+                    return cluster;
+                }).collect(Collectors.toSet());
+
+        // See if any clusters intersect, if so merge them. Repeat until all the clusters are disjoint.
+        while (true) {
+            Set<Set<Flavor>> newClusters = new HashSet<>();
+            for (Set<Flavor> oldCluster : prevClusters) {
+                Optional<Set<Flavor>> overlappingCluster = newClusters.stream()
+                        .filter(cluster -> !Collections.disjoint(cluster, oldCluster))
+                        .findFirst();
+
+                if (overlappingCluster.isPresent()) {
+                    overlappingCluster.get().addAll(oldCluster);
+                } else {
+                    newClusters.add(oldCluster);
+                }
+            }
+
+            if (prevClusters.size() == newClusters.size()) break;
+            prevClusters = newClusters;
+        }
+
+        flavorClusters = prevClusters;
+    }
+
+    public Set<Flavor> getFlavorClusterFor(Flavor flavor) {
+        return flavorClusters.stream()
+                .filter(cluster -> cluster.contains(flavor))
+                .findFirst()
+                .orElseThrow(() -> new RuntimeException("Could not find cluster for flavor " + flavor));
+    }
+}
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirerTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirerTest.java
index db6b0082459..f3a234588fd 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirerTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirerTest.java
@@ -1,6 +1,8 @@
 package com.yahoo.vespa.hosted.provision.maintenance;
 
+import com.yahoo.config.provision.ApplicationId;
 import com.yahoo.config.provision.Flavor;
+import com.yahoo.config.provision.NodeFlavors;
 import com.yahoo.config.provision.NodeType;
 import com.yahoo.vespa.hosted.provision.Node;
 import com.yahoo.vespa.hosted.provision.maintenance.retire.RetirementPolicy;
@@ -8,6 +10,8 @@ import com.yahoo.vespa.hosted.provision.node.Agent;
 import com.yahoo.vespa.hosted.provision.node.Allocation;
 import com.yahoo.vespa.hosted.provision.node.History;
 import com.yahoo.vespa.hosted.provision.node.Status;
+import com.yahoo.vespa.hosted.provision.provisioning.FlavorClusters;
+import com.yahoo.vespa.hosted.provision.provisioning.FlavorClustersTest;
 import org.junit.Before;
 import org.junit.Test;
 import org.junit.experimental.runners.Enclosed;
@@ -15,6 +19,7 @@ import org.junit.runner.RunWith;
 
 import java.time.Duration;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.List;
@@ -23,6 +28,8 @@ import java.util.Optional;
 import java.util.Set;
 import java.util.UUID;
 import java.util.stream.Collectors;
+import java.util.stream.IntStream;
+import java.util.stream.Stream;
 
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
@@ -38,12 +45,16 @@ import static org.mockito.Mockito.when;
 public class NodeRetirerTest {
 
     public static class FullNodeRepositoryTester {
+        private final RetirementPolicy policy = node -> node.ipAddresses().equals(Collections.singleton("::1"));
+        private NodeRetirerTester tester;
+        private NodeRetirer retirer;
 
         @Test
         public void testRetireUnallocatedNodes() {
-            NodeRetirerTester tester = new NodeRetirerTester(NodeRetirerTester.makeFlavors(5));
-            RetirementPolicy policy = node -> node.ipAddresses().equals(Collections.singleton("::1"));
-            NodeRetirer retirer = new NodeRetirer(tester.nodeRepository, NodeRetirerTester.zone, Duration.ofDays(1), new JobControl(tester.nodeRepository.database()), policy);
+            NodeFlavors nodeFlavors = FlavorClustersTest.makeFlavors(6);
+            FlavorClusters flavorClusters = new FlavorClusters(nodeFlavors.getFlavors());
+            tester = new NodeRetirerTester(nodeFlavors);
+            retirer = new NodeRetirer(tester.nodeRepository, NodeRetirerTester.zone, flavorClusters, Duration.ofDays(1), new JobControl(tester.nodeRepository.database()), policy);
 
             tester.createReadyNodesByFlavor(5, 3, 77, 47);
             tester.deployApp("vespa", "calendar", 0, 3);
@@ -51,20 +62,12 @@ public class NodeRetirerTest {
             tester.deployApp("sports", "results", 2, 7);
             tester.deployApp("search", "images", 3, 6);
 
-            Map<Flavor, Long> expected = tester.expectedCountsByFlavor(1, 3, 56, 40);
-            Map<Flavor, Long> actual = retirer.getNumberSpareReadyNodesByFlavor(tester.nodeRepository.getNodes());
-            assertEquals(expected, actual);
-
             // Not all nodes that we wanted to retire could be retired now (Not enough spare nodes)
+            assertSpareCountsByFlavor(1, 3, 56, 40);
             assertFalse(retirer.retireUnallocated());
-            Map<Flavor, Long> parkedCountsByFlavor = tester.nodeRepository.getNodes(Node.State.parked).stream()
-                    .collect(Collectors.groupingBy(Node::flavor, Collectors.counting()));
-            assertEquals(expected, parkedCountsByFlavor);
-
-            expected = tester.expectedCountsByFlavor(0, -1, 0, 0);
-            actual = retirer.getNumberSpareReadyNodesByFlavor(tester.nodeRepository.getNodes());
-            assertEquals(expected, actual);
+            assertParkedCountsByFlavor(1, 3, 56, 40);
 
+            assertSpareCountsByFlavor(0, -1, 0, 0);
             // Lets change parked nodes IP address and set it back to ready
             tester.nodeRepository.getNodes(Node.State.parked)
                     .forEach(node -> {
@@ -75,25 +78,179 @@ public class NodeRetirerTest {
                         tester.nodeRepository.setReady(node.hostname());
                     });
 
-            expected = tester.expectedCountsByFlavor(1, 3, 56, 40);
-            actual = retirer.getNumberSpareReadyNodesByFlavor(tester.nodeRepository.getNodes());
-            assertEquals(expected, actual);
-
             // The remaining nodes we wanted to retire has been retired
+            assertSpareCountsByFlavor(1, 3, 56, 40);
             assertTrue(retirer.retireUnallocated());
-            parkedCountsByFlavor = tester.nodeRepository.getNodes(Node.State.parked).stream()
+            assertParkedCountsByFlavor(1, -1, 2, 1);
+        }
+
+        /* Creates flavors where 'replaces' graph and node counts that looks like this:
+         *           Total nodes: 40  1
+         *                            |                     4   Total nodes: 7
+         *          Total nodes: 20   |                     |   search.images nodes: 4
+         *    vespa.notes nodes: 3    0                     |
+         * sports.results nodes: 6   / \                    5   Total nodes: 5
+         *                          /   \                       search.videos nodes: 2
+         *       Total nodes: 25   2     3  Total nodes: 14
+         */
+        @Test
+        public void testRetireAllocatedNodes() throws InterruptedException {
+            NodeFlavors nodeFlavors = FlavorClustersTest.makeFlavors(
+                    Collections.singletonList(1),   // 0 -> {1}
+                    Collections.emptyList(),        // 1 -> {}
+                    Collections.singletonList(0),   // 2 -> {0}
+                    Collections.singletonList(0),   // 3 -> {0}
+                    Collections.emptyList(),        // 4 -> {}
+                    Collections.singletonList(4));  // 5 -> {4}
+            FlavorClusters flavorClusters = new FlavorClusters(nodeFlavors.getFlavors());
+            tester = new NodeRetirerTester(nodeFlavors);
+
+            tester.createReadyNodesByFlavor(20, 40, 25, 14, 7, 5);
+            tester.deployApp("vespa", "calendar", 3, 7);
+            tester.deployApp("vespa", "notes", 0, 3);
+            tester.deployApp("sports", "results", 0, 6);
+            tester.deployApp("search", "images", 4, 4);
+            tester.deployApp("search", "videos", 5, 2);
+
+            JobControl jobControl = new JobControl(tester.nodeRepository.database());
+            retirer = new NodeRetirer(tester.nodeRepository, NodeRetirerTester.zone, flavorClusters, Duration.ofDays(1), jobControl, policy);
+            // Update IP addresses on ready nodes so that when they are deployed to, we wont retire them
+            tester.nodeRepository.getNodes(Node.State.ready)
+                    .forEach(node -> tester.nodeRepository.write(node.withIpAddresses(Collections.singleton("::2"))));
+
+            assertSpareCountsByFlavor(10, 40, 25, 6, 2, 2);
+
+
+            retireThenAssertSpareAndParkedCounts(new long[]{8, 40, 25, 5, 1, 1}, new long[]{1, 1, 1, 1, 1});
+
+            // At this point we only have 1 spare node for flavors 4 & 5, 5 also replaces 4, which means that we can
+            // only replace 1 of either flavor-4 or flavor-5.
+            // search.videos (5th app) wont be replaced because search.images will get the last spare node in
+            // flavor-4, flavor-5 cluster because it has more active nodes
+            retireThenAssertSpareAndParkedCounts(new long[]{6, 40, 25, 4, 0, 1}, new long[]{2, 2, 2, 2, 1});
+
+            // After redeploying search.images, it ended up on a flavor-4 node, so we still have a flavor-5 spare,
+            // but we still wont be able to retire any nodes for search.videos as min spare for its flavor cluster is 0
+            retireThenAssertSpareAndParkedCounts(new long[]{4, 40, 25, 3, 0, 1}, new long[]{3, 3, 3, 2, 1});
+
+            // All 3 of vespa.notes old nodes have been retired, so its parked count should stay the same
+            retireThenAssertSpareAndParkedCounts(new long[]{3, 40, 25, 2, 0, 1}, new long[]{4, 3, 4, 2, 1});
+
+            // Only vespa.calendar and sports.results remain, but their flavors (3 and 0 respectively) are in the same
+            // flavor cluster, because the min count for this cluster is 1, we can only retire one of them
+            retireThenAssertSpareAndParkedCounts(new long[]{2, 40, 25, 1, 0, 1}, new long[]{5, 3, 5, 2, 1});
+
+            // min flavor count for both flavor clusters is now 0, so no further change is expected
+            retireThenAssertSpareAndParkedCounts(new long[]{2, 40, 25, 0, 0, 1}, new long[]{6, 3, 5, 2, 1});
+            retireThenAssertSpareAndParkedCounts(new long[]{2, 40, 25, 0, 0, 1}, new long[]{6, 3, 5, 2, 1});
+        }
+
+        @Test
+        public void testGetActiveApplicationIds() {
+            NodeFlavors nodeFlavors = FlavorClustersTest.makeFlavors(1);
+            FlavorClusters flavorClusters = new FlavorClusters(nodeFlavors.getFlavors());
+            tester = new NodeRetirerTester(nodeFlavors);
+            retirer = new NodeRetirer(tester.nodeRepository, NodeRetirerTester.zone, flavorClusters, Duration.ofDays(1), new JobControl(tester.nodeRepository.database()), policy);
+
+            tester.createReadyNodesByFlavor(50);
+            ApplicationId a1 = tester.deployApp("vespa", "calendar", 0, 10);
+            ApplicationId a2 = tester.deployApp("vespa", "notes", 0, 12);
+            ApplicationId a3 = tester.deployApp("sports", "results", 0, 7);
+            ApplicationId a4 = tester.deployApp("search", "images", 0, 6);
+
+            List<ApplicationId> expectedOrder = Arrays.asList(a2, a1, a3, a4);
+            List<ApplicationId> actualOrder = retirer.getActiveApplicationIds(tester.nodeRepository.getNodes());
+            assertEquals(expectedOrder, actualOrder);
+        }
+
+        @Test
+        public void testGetRetireableNodesForApplication() {
+            NodeFlavors nodeFlavors = FlavorClustersTest.makeFlavors(1);
+            FlavorClusters flavorClusters = new FlavorClusters(nodeFlavors.getFlavors());
+            tester = new NodeRetirerTester(nodeFlavors);
+            retirer = new NodeRetirer(tester.nodeRepository, NodeRetirerTester.zone, flavorClusters, Duration.ofDays(1), new JobControl(tester.nodeRepository.database()), policy);
+
+            tester.createReadyNodesByFlavor(10);
+            tester.deployApp("vespa", "calendar", 0, 10);
+
+            List<Node> nodes = tester.nodeRepository.getNodes();
+            Set<String> actual = retirer.getRetireableNodesForApplication(nodes).stream().map(Node::hostname).collect(Collectors.toSet());
+            Set<String> expected = nodes.stream().map(Node::hostname).collect(Collectors.toSet());
+            assertEquals(expected, actual);
+
+            Node nodeWantToRetire = tester.nodeRepository.getNode("host3.test.yahoo.com").orElseThrow(RuntimeException::new);
+            tester.nodeRepository.write(nodeWantToRetire.with(nodeWantToRetire.status().withWantToRetire(true)));
+            Node nodeToFail = tester.nodeRepository.getNode("host5.test.yahoo.com").orElseThrow(RuntimeException::new);
+            tester.nodeRepository.fail(nodeToFail.hostname(), Agent.system, "Failed for unit testing");
+            Node nodeToUpdate = tester.nodeRepository.getNode("host8.test.yahoo.com").orElseThrow(RuntimeException::new);
+            tester.nodeRepository.write(nodeToUpdate.withIpAddresses(Collections.singleton("::2")));
+
+            nodes = tester.nodeRepository.getNodes();
+            Set<String> excluded = Stream.of(nodeWantToRetire, nodeToFail, nodeToUpdate).map(Node::hostname).collect(Collectors.toSet());
+            Set<String> actualAfterUpdates = retirer.getRetireableNodesForApplication(nodes).stream().map(Node::hostname).collect(Collectors.toSet());
+            Set<String> expectedAfterUpdates = nodes.stream().map(Node::hostname).filter(node -> !excluded.contains(node)).collect(Collectors.toSet());
+            assertEquals(expectedAfterUpdates, actualAfterUpdates);
+        }
+
+        @Test
+        public void testGetNumberNodesAllowToRetireForApplication() {
+            NodeFlavors nodeFlavors = FlavorClustersTest.makeFlavors(1);
+            FlavorClusters flavorClusters = new FlavorClusters(nodeFlavors.getFlavors());
+            tester = new NodeRetirerTester(nodeFlavors);
+            retirer = new NodeRetirer(tester.nodeRepository, NodeRetirerTester.zone, flavorClusters, Duration.ofDays(1), new JobControl(tester.nodeRepository.database()), policy);
+
+            tester.createReadyNodesByFlavor(10);
+            tester.deployApp("vespa", "calendar", 0, 10);
+
+            long actualAllActive = retirer.getNumberNodesAllowToRetireForApplication(tester.nodeRepository.getNodes(), 2);
+            assertEquals(2, actualAllActive);
+
+            // Lets put 3 random nodes in wantToRetire
+            List<Node> nodesToRetire = tester.nodeRepository.getNodes().stream().limit(3).collect(Collectors.toList());
+            nodesToRetire.forEach(node -> tester.nodeRepository.write(node.with(node.status().withWantToRetire(true))));
+            long actualOneWantToRetire = retirer.getNumberNodesAllowToRetireForApplication(tester.nodeRepository.getNodes(), 2);
+            assertEquals(0, actualOneWantToRetire);
+
+            // Now 2 of those finish retiring and go to parked
+            nodesToRetire.stream().limit(2).forEach(node ->
+                    tester.nodeRepository.park(node.hostname(), Agent.system, "Parked for unit testing"));
+            long actualOneRetired = retirer.getNumberNodesAllowToRetireForApplication(tester.nodeRepository.getNodes(), 2);
+            assertEquals(1, actualOneRetired);
+        }
+
+        private void assertSpareCountsByFlavor(long... nums) {
+            Map<Flavor, Long> expectedSpareCountsByFlavor = tester.expectedCountsByFlavor(nums);
+            Map<Flavor, Long> actualSpaceCountsByFlavor = retirer.getNumberSpareReadyNodesByFlavor(tester.nodeRepository.getNodes());
+            assertEquals(expectedSpareCountsByFlavor, actualSpaceCountsByFlavor);
+        }
+
+        private void assertParkedCountsByFlavor(long... nums) {
+            Map<Flavor, Long> expected = tester.expectedCountsByFlavor(nums);
+            Map<Flavor, Long> actual = tester.nodeRepository.getNodes(Node.State.parked).stream()
                     .collect(Collectors.groupingBy(Node::flavor, Collectors.counting()));
-            expected = tester.expectedCountsByFlavor(1, -1, 2, 1);
-            assertEquals(expected, parkedCountsByFlavor);
+            assertEquals(expected, actual);
         }
-    }
 
+        private void assertParkedCountsByApplication(long... nums) {
+            Map<ApplicationId, Long> expected = tester.expectedCountsByApplication(nums);
+            Map<ApplicationId, Long> actual = tester.nodeRepository.getNodes(Node.State.parked).stream()
+                    .collect(Collectors.groupingBy(node -> node.allocation().get().owner(), Collectors.counting()));
+            assertEquals(expected, actual);
+        }
+
+        private void retireThenAssertSpareAndParkedCounts(long[] spareCountsByFlavor, long[] parkedCountsByApp) {
+            retirer.retireAllocated();
+            tester.iterateMaintainers();
+            assertSpareCountsByFlavor(spareCountsByFlavor);
+            assertParkedCountsByApplication(parkedCountsByApp);
+        }
+    }
 
     /**
      * For testing methods that require minimal node repository and flavor setup
      */
     public static class HelperMethodsTester {
-        private final List<Flavor> flavors = NodeRetirerTester.makeFlavors(5).getFlavors();
+        private final List<Flavor> flavors = FlavorClustersTest.makeFlavors(5).getFlavors();
         private final List<Node> nodes = new ArrayList<>();
         private final NodeRetirer retirer = mock(NodeRetirer.class);
 
@@ -177,5 +334,22 @@ public class NodeRetirerTest {
             assertEquals(retirer.getNumSpareNodes(1, 2), 1L);
             assertEquals(retirer.getNumSpareNodes(43, 23), 18L);
         }
+
+        @Test
+        public void testGetMinAmongstKeys() {
+            when(retirer.getMinAmongstKeys(any(), any())).thenCallRealMethod();
+
+            Map<String, Integer> map = createMapWith(4, 10, 43, 23, 7, 53, 2, 12, 42, 10);
+            Set<String> keys = createKeySetWith(1, 3, 4, 5, 7, 9);
+            assertEquals("4", retirer.getMinAmongstKeys(map, keys)); // Smallest value is 7, which is index 4
+        }
+
+        private Map<String, Integer> createMapWith(int... values) {
+            return IntStream.range(0, values.length).boxed().collect(Collectors.toMap(String::valueOf, i -> values[i]));
+        }
+
+        private Set<String> createKeySetWith(int... keys) {
+            return Arrays.stream(keys).boxed().map(String::valueOf).collect(Collectors.toSet());
+        }
     }
 }
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirerTester.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirerTester.java
index 635e7ac7d10..c6412d7c28f 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirerTester.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/NodeRetirerTester.java
@@ -4,7 +4,6 @@ package com.yahoo.vespa.hosted.provision.maintenance;
 import com.yahoo.component.Version;
 import com.yahoo.config.provision.ApplicationId;
 import com.yahoo.config.provision.Capacity;
-import com.yahoo.config.provision.ClusterMembership;
 import com.yahoo.config.provision.ClusterSpec;
 import com.yahoo.config.provision.Environment;
 import com.yahoo.config.provision.Flavor;
@@ -21,19 +20,20 @@ import com.yahoo.vespa.curator.transaction.CuratorTransaction;
 import com.yahoo.vespa.hosted.provision.Node;
 import com.yahoo.vespa.hosted.provision.NodeRepository;
 import com.yahoo.vespa.hosted.provision.provisioning.NodeRepositoryProvisioner;
-import com.yahoo.vespa.hosted.provision.testutils.FlavorConfigBuilder;
 import com.yahoo.vespa.hosted.provision.testutils.MockDeployer;
 import com.yahoo.vespa.hosted.provision.testutils.MockNameResolver;
-import com.yahoo.vespa.hosted.provision.testutils.OrchestratorMock;
-import com.yahoo.vespa.hosted.provision.testutils.ServiceMonitorStub;
-import com.yahoo.vespa.orchestrator.Orchestrator;
 
+import java.time.Duration;
 import java.util.ArrayList;
 import java.util.Collections;
+import java.util.Comparator;
 import java.util.HashMap;
+import java.util.Iterator;
+import java.util.LinkedHashMap;
 import java.util.List;
 import java.util.Map;
 import java.util.Optional;
+import java.util.stream.Collectors;
 
 
 /**
@@ -45,12 +45,16 @@ public class NodeRetirerTester {
     // Components with state
     public final ManualClock clock;
     public final NodeRepository nodeRepository;
-    public ServiceMonitorStub serviceMonitor;
-    public MockDeployer deployer;
-    private final Orchestrator orchestrator;
     private final NodeRepositoryProvisioner provisioner;
     private final Curator curator;
     private final List<Flavor> flavors;
+
+    // Use LinkedHashMap to keep order in which applications were deployed
+    private final Map<ApplicationId, MockDeployer.ApplicationContext> apps = new LinkedHashMap<>();
+
+    private PeriodicApplicationMaintainer applicationMaintainer;
+    private RetiredExpirer retiredExpirer;
+    private InactiveExpirer inactiveExpirer;
     private int nextNodeId = 0;
 
     public NodeRetirerTester(NodeFlavors nodeFlavors) {
@@ -58,18 +62,7 @@ public class NodeRetirerTester {
         curator = new MockCurator();
         nodeRepository = new NodeRepository(nodeFlavors, curator, clock, zone, new MockNameResolver().mockAnyLookup());
         provisioner = new NodeRepositoryProvisioner(nodeRepository, nodeFlavors, zone);
-        orchestrator = new OrchestratorMock();
-        deployer = new MockDeployer(provisioner, Collections.emptyMap());
-        serviceMonitor = new ServiceMonitorStub(Collections.emptyMap(), nodeRepository);
-        flavors = nodeFlavors.getFlavors();
-    }
-
-    public void suspend(ApplicationId app) {
-        try {
-            orchestrator.suspend(app);
-        } catch (Exception e) {
-            throw new RuntimeException(e);
-        }
+        flavors = nodeFlavors.getFlavors().stream().sorted(Comparator.comparing(Flavor::name)).collect(Collectors.toList());
     }
 
     public void createReadyNodesByFlavor(int... nums) {
@@ -88,14 +81,36 @@ public class NodeRetirerTester {
         nodeRepository.setReady(nodes);
     }
 
-    public void deployApp(String tenantName, String applicationName, int flavorId, int numNodes) {
+    public ApplicationId deployApp(String tenantName, String applicationName, int flavorId, int numNodes) {
         Flavor flavor = flavors.get(flavorId);
 
         ApplicationId applicationId = ApplicationId.from(tenantName, applicationName, "default");
         ClusterSpec cluster = ClusterSpec.request(ClusterSpec.Type.container, ClusterSpec.Id.from("test"), Version.fromString("6.99"));
         Capacity capacity = Capacity.fromNodeCount(numNodes, flavor.name());
+        apps.put(applicationId, new MockDeployer.ApplicationContext(applicationId, cluster, capacity, 1));
 
         activate(applicationId, cluster, capacity);
+        return applicationId;
+    }
+
+    public void iterateMaintainers() {
+        if (applicationMaintainer == null) {
+            MockDeployer deployer = new MockDeployer(provisioner, apps);
+            JobControl jobControl = new JobControl(nodeRepository.database());
+            applicationMaintainer = new PeriodicApplicationMaintainerTest.TestablePeriodicApplicationMaintainer(
+                    deployer, nodeRepository, Duration.ofMinutes(10), Optional.empty());
+            retiredExpirer = new RetiredExpirer(nodeRepository, deployer, clock, Duration.ofMinutes(10), jobControl);
+            inactiveExpirer = new InactiveExpirer(nodeRepository, clock, Duration.ofMinutes(10), jobControl);
+
+        }
+
+        applicationMaintainer.maintain();
+
+        clock.advance(Duration.ofMinutes(11));
+        retiredExpirer.maintain();
+
+        clock.advance(Duration.ofMinutes(11));
+        inactiveExpirer.maintain();
     }
 
     private void activate(ApplicationId applicationId, ClusterSpec cluster, Capacity capacity) {
@@ -115,11 +130,14 @@ public class NodeRetirerTester {
         return countsByFlavor;
     }
 
-    public static NodeFlavors makeFlavors(int numFlavors) {
-        FlavorConfigBuilder flavorConfigBuilder = new FlavorConfigBuilder();
-        for (int i = 0; i < numFlavors; i++) {
-            flavorConfigBuilder.addFlavor("flavor-" + i, 1. /* cpu*/, 3. /* mem GB*/, 2. /*disk GB*/, Flavor.Type.BARE_METAL);
+    public Map<ApplicationId, Long> expectedCountsByApplication(long... nums) {
+        Map<ApplicationId, Long> countsByApplicationId = new HashMap<>();
+        Iterator<ApplicationId> iterator = apps.keySet().iterator();
+        for (int i = 0; iterator.hasNext(); i++) {
+            if (nums[i] < 0) continue;
+            ApplicationId applicationId = iterator.next();
+            countsByApplicationId.put(applicationId, nums[i]);
         }
-        return new NodeFlavors(flavorConfigBuilder.build());
+        return countsByApplicationId;
     }
 }
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/PeriodicApplicationMaintainerTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/PeriodicApplicationMaintainerTest.java
index cd4a34cf6ea..c1504ec188d 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/PeriodicApplicationMaintainerTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/maintenance/PeriodicApplicationMaintainerTest.java
@@ -204,7 +204,7 @@ public class PeriodicApplicationMaintainerTest {
 
     }
     
-    private static class TestablePeriodicApplicationMaintainer extends PeriodicApplicationMaintainer {
+    public static class TestablePeriodicApplicationMaintainer extends PeriodicApplicationMaintainer {
 
         private Optional<List<Node>> overriddenNodesNeedingMaintenance;
         
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorClustersTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorClustersTest.java
new file mode 100644
index 00000000000..c4bd452d25c
--- /dev/null
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorClustersTest.java
@@ -0,0 +1,109 @@
+// Copyright 2016 Yahoo Inc. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.vespa.hosted.provision.provisioning;
+
+import com.yahoo.config.provision.Flavor;
+import com.yahoo.config.provision.NodeFlavors;
+import com.yahoo.config.provisioning.FlavorsConfig;
+import com.yahoo.vespa.hosted.provision.testutils.FlavorConfigBuilder;
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+import java.util.stream.Collectors;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author freva
+ */
+@SuppressWarnings("unchecked")
+public class FlavorClustersTest {
+
+    @Test
+    public void testSingletonClusters() {
+        NodeFlavors nodeFlavors = makeFlavors(Collections.emptyList(), Collections.emptyList(), Collections.emptyList());
+        FlavorClusters clusters = new FlavorClusters(nodeFlavors.getFlavors());
+        Set<Set<Flavor>> expectedClusters = createExpectedClusters(nodeFlavors,
+                Collections.singletonList(0), Collections.singletonList(1), Collections.singletonList(2));
+        assertEquals(expectedClusters, clusters.flavorClusters);
+    }
+
+    @Test
+    public void testSingleClusterWithMultipleNodes() {
+        // 0 -> 1 -> 2
+        NodeFlavors nodeFlavors = makeFlavors(Collections.singletonList(1), Collections.singletonList(2), Collections.emptyList());
+        FlavorClusters clusters = new FlavorClusters(nodeFlavors.getFlavors());
+        Set<Set<Flavor>> expectedClusters = createExpectedClusters(nodeFlavors, Arrays.asList(0, 1, 2));
+        assertEquals(expectedClusters, clusters.flavorClusters);
+    }
+
+    @Test
+    public void testMultipleClustersWithMultipleNodes() {
+        /* Creates flavors where 'replaces' graph that looks like this:
+         *    5
+         *    |
+         *    |
+         *    3      4                    8
+         *     \   /                      |
+         *      \ /                       |
+         *       1           6            7
+         *      / \
+         *     /   \
+         *    0     2
+         */
+        NodeFlavors nodeFlavors = makeFlavors(
+                Collections.singletonList(1),   // 0 -> {1}
+                Arrays.asList(3, 4),        // 1 -> {3, 4}
+                Collections.singletonList(1),   // 2 -> {1}
+                Collections.singletonList(5),   // 3 -> {5}
+                Collections.emptyList(),        // 4 -> {}
+                Collections.emptyList(),        // 5 -> {}
+                Collections.emptyList(),        // 6 -> {}
+                Collections.singletonList(8),   // 7 -> {8}
+                Collections.emptyList());       // 8 -> {}
+
+        FlavorClusters clusters = new FlavorClusters(nodeFlavors.getFlavors());
+        Set<Set<Flavor>> expectedClusters = createExpectedClusters(nodeFlavors,
+                Arrays.asList(0, 1, 2, 3, 4, 5),
+                Collections.singletonList(6),
+                Arrays.asList(7, 8));
+        assertEquals(expectedClusters, clusters.flavorClusters);
+    }
+
+    private Set<Set<Flavor>> createExpectedClusters(NodeFlavors nodeFlavors, List<Integer>... clusters) {
+        return Arrays.stream(clusters).map(cluster ->
+                cluster.stream()
+                        .map(flavorId -> nodeFlavors.getFlavorOrThrow("flavor-" + flavorId))
+                        .collect(Collectors.toSet()))
+                .collect(Collectors.toSet());
+    }
+
+    public static NodeFlavors makeFlavors(int numFlavors) {
+        FlavorConfigBuilder flavorConfigBuilder = new FlavorConfigBuilder();
+        for (int i = 0; i < numFlavors; i++) {
+            flavorConfigBuilder.addFlavor("flavor-" + i, 1. /* cpu*/, 3. /* mem GB*/, 2. /*disk GB*/, Flavor.Type.BARE_METAL);
+        }
+        return new NodeFlavors(flavorConfigBuilder.build());
+    }
+
+    /**
+     * Takes in variable number of List of Integers:
+     *  For each list a flavor is created
+     *  For each element, n, in list, the new flavor replace n'th flavor
+     */
+    @SafeVarargs
+    public static NodeFlavors makeFlavors(List<Integer>... replaces) {
+        FlavorConfigBuilder flavorConfigBuilder = new FlavorConfigBuilder();
+        for (int i = 0; i < replaces.length; i++) {
+            FlavorsConfig.Flavor.Builder builder = flavorConfigBuilder
+                    .addFlavor("flavor-" + i, 1. /* cpu*/, 3. /* mem GB*/, 2. /*disk GB*/, Flavor.Type.BARE_METAL);
+
+            for (Integer replacesId : replaces[i]) {
+                flavorConfigBuilder.addReplaces("flavor-" + replacesId, builder);
+            }
+        }
+        return new NodeFlavors(flavorConfigBuilder.build());
+    }
+}