Prefer to retire the highest index nodes

3 files changed, 83 insertions, 24 deletions

diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/GroupPreparer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/GroupPreparer.java
index 0f5549e1110..e1af3340f80 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/GroupPreparer.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/GroupPreparer.java
@@ -14,6 +14,7 @@ import com.yahoo.vespa.hosted.provision.node.Flavor;
 import java.time.Clock;
 import java.util.ArrayList;
 import java.util.Collection;
+import java.util.Comparator;
 import java.util.HashSet;
 import java.util.LinkedHashSet;
 import java.util.List;
@@ -62,7 +63,7 @@ class GroupPreparer {
             nodeList.offer(nodeRepository.getNodes(application, Node.State.active), !canChangeGroup);
             if (nodeList.satisfied()) return nodeList.finalNodes(surplusActiveNodes);
 
-            // Use active nodes that will otherwise be retired
+            // Use active nodes from other groups that will otherwise be retired
             List<Node> accepted = nodeList.offer(surplusActiveNodes, canChangeGroup);
             surplusActiveNodes.removeAll(accepted);
             if (nodeList.satisfied()) return nodeList.finalNodes(surplusActiveNodes);
@@ -76,10 +77,10 @@ class GroupPreparer {
             nodeList.update(nodeRepository.reserve(accepted));
             if (nodeList.satisfied()) return nodeList.finalNodes(surplusActiveNodes);
 
-            // Use new, ready nodes. Need to lock ready pool to ensure that nodes are not grabbed by others.
+            // Use new, ready nodes. Lock ready pool to ensure that nodes are not grabbed by others.
             try (Mutex readyLock = nodeRepository.lockUnallocated()) {
                 List<Node> readyNodes = nodeRepository.getNodes(Node.Type.tenant, Node.State.ready);
-                accepted = nodeList.offer(optimize(readyNodes), !canChangeGroup);
+                accepted = nodeList.offer(stripeOverHosts(readyNodes), !canChangeGroup);
                 nodeList.update(nodeRepository.reserve(accepted));
             }
             if (nodeList.satisfied()) return nodeList.finalNodes(surplusActiveNodes);
@@ -99,33 +100,32 @@ class GroupPreparer {
         }
     }
 
-    // optimize based on parent hosts
-    static List<Node> optimize(List<Node> input) {
-        int cnt = input.size();
-        List<Node> output = new ArrayList<Node>(cnt);
+    /** Return the input nodes in an order striped over their parent hosts */
+    static List<Node> stripeOverHosts(List<Node> input) {
+        List<Node> output = new ArrayList<>(input.size());
 
-        // first deal with VMs.
-        long vms = input.stream()
+        // first deal with nodes having a parent host
+        long nodesHavingParent = input.stream()
             .filter(n -> n.parentHostname().isPresent())
             .collect(Collectors.counting());
-        if (vms > 0) {
-            // Make a map where each parenthost maps to a list of VMs:
+        if (nodesHavingParent > 0) {
+            // Make a map where each parent host maps to its list of child nodes
             Map<String, List<Node>> byParentHosts = input.stream()
                 .filter(n -> n.parentHostname().isPresent())
                 .collect(Collectors.groupingBy(n -> n.parentHostname().get()));
 
-            // sort keys, those parent hosts with the most (remaining) ready VMs first
+            // sort keys, those parent hosts with the most (remaining) ready nodes first
             List<String> sortedParentHosts = byParentHosts
                 .keySet().stream()
                 .sorted((k1, k2) -> byParentHosts.get(k2).size() - byParentHosts.get(k1).size())
                 .collect(Collectors.toList());
-            while (vms > 0) {
-                // take one VM from each parent host, round-robin.
+            while (nodesHavingParent > 0) {
+                // take one node from each parent host, round-robin.
                 for (String k : sortedParentHosts) {
                     List<Node> leftFromHost = byParentHosts.get(k);
                     if (! leftFromHost.isEmpty()) {
                         output.add(leftFromHost.remove(0));
-                        --vms;
+                        --nodesHavingParent;
                     }
                 }
             }
@@ -225,7 +225,7 @@ class GroupPreparer {
         private boolean offeredNodeHasParentHostnameAlreadyAccepted(Collection<Node> accepted, Node offered) {
             for (Node acceptedNode : accepted) {
                 if (acceptedNode.parentHostname().isPresent() && offered.parentHostname().isPresent() &&
-                        acceptedNode.parentHostname().get().equals(offered.parentHostname().get())) {
+                    acceptedNode.parentHostname().get().equals(offered.parentHostname().get())) {
                     return true;
                 }
             }
@@ -312,6 +312,7 @@ class GroupPreparer {
          * Prefer to retire nodes of the wrong flavor.
          * Make as few changes to the retired set as possible.
          *
+         * @param surplusNodes this will add nodes not any longer needed by this group to this list
          * @return the final list of nodes
          */
         public List<Node> finalNodes(List<Node> surplusNodes) {
@@ -319,17 +320,17 @@ class GroupPreparer {
             long surplus = nodes.size() - requestedNodes - currentRetired;
 
             List<Node> changedNodes = new ArrayList<>();
-            if (surplus > 0) { // retire until surplus is 0
-                for (Node node : nodes) {
+            if (surplus > 0) { // retire until surplus is 0, prefer to retire higher indexes to minimize redistribution
+                for (Node node : byDecreasingIndex(nodes)) {
                     if ( ! node.allocation().get().membership().retired() && node.state().equals(Node.State.active)) {
                         changedNodes.add(node.retireByApplication(clock.instant()));
-                        surplusNodes.add(node); // will be used in another group or retired
+                        surplusNodes.add(node); // offer this node to other groups
                         if (--surplus == 0) break;
                     }
                 }
             }
             else if (surplus < 0) { // unretire until surplus is 0
-                for (Node node : nodes) {
+                for (Node node : byIncreasingIndex(nodes)) {
                     if ( node.allocation().get().membership().retired() && hasCompatibleFlavor(node)) {
                         changedNodes.add(node.unretire());
                         if (++surplus == 0) break;
@@ -340,6 +341,18 @@ class GroupPreparer {
             return new ArrayList<>(nodes);
         }
 
+        private List<Node> byDecreasingIndex(Set<Node> nodes) {
+            return nodes.stream().sorted(nodeIndexComparator().reversed()).collect(Collectors.toList());
+        }
+
+        private List<Node> byIncreasingIndex(Set<Node> nodes) {
+            return nodes.stream().sorted(nodeIndexComparator()).collect(Collectors.toList());
+        }
+        
+        private Comparator<Node> nodeIndexComparator() {
+            return Comparator.comparing((Node n) -> n.allocation().get().membership().index());
+        }
+
     }
 
 }
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisionTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisionTest.java
index 0d6a2cd6b9e..2c80ece4aab 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisionTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/ProvisionTest.java
@@ -4,6 +4,7 @@ package com.yahoo.vespa.hosted.provision.provisioning;
 import com.yahoo.cloud.config.ConfigserverConfig;
 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.HostFilter;
@@ -425,12 +426,39 @@ public class ProvisionTest {
         }
     }
 
+    @Test
+    public void highest_node_indexes_are_retired_first() {
+        ProvisioningTester tester = new ProvisioningTester(new Zone(Environment.prod, RegionName.from("us-east")));
+
+        ApplicationId application1 = tester.makeApplicationId();
+
+        tester.makeReadyNodes(10, "default");
+
+        // deploy
+        SystemState state1 = prepare(application1, 2, 2, 3, 3, "default", tester);
+        tester.activate(application1, state1.allHosts);
+
+        // decrease cluster sizes
+        SystemState state2 = prepare(application1, 1, 1, 1, 1, "default", tester);
+        tester.activate(application1, state2.allHosts);
+
+        // group0
+        assertFalse(state2.hostByMembership("test", 0, 0).membership().get().retired());
+        assertTrue( state2.hostByMembership("test", 0, 1).membership().get().retired());
+        assertTrue( state2.hostByMembership("test", 0, 2).membership().get().retired());
+
+        // group1
+        assertFalse(state2.hostByMembership("test", 1, 0).membership().get().retired());
+        assertTrue( state2.hostByMembership("test", 1, 1).membership().get().retired());
+        assertTrue( state2.hostByMembership("test", 1, 2).membership().get().retired());
+    }
+
     private SystemState prepare(ApplicationId application, int container0Size, int container1Size, int group0Size, int group1Size, String flavor, ProvisioningTester tester) {
         // "deploy prepare" with a two container clusters and a storage cluster having of two groups
         ClusterSpec containerCluster0 = ClusterSpec.from(ClusterSpec.Type.container, ClusterSpec.Id.from("container0"), Optional.empty());
         ClusterSpec containerCluster1 = ClusterSpec.from(ClusterSpec.Type.container, ClusterSpec.Id.from("container1"), Optional.empty());
-        ClusterSpec contentGroup0 = ClusterSpec.from(ClusterSpec.Type.content, ClusterSpec.Id.from("test"), Optional.of(ClusterSpec.Group.from("g0")));
-        ClusterSpec contentGroup1 = ClusterSpec.from(ClusterSpec.Type.content, ClusterSpec.Id.from("test"), Optional.of(ClusterSpec.Group.from("g1")));
+        ClusterSpec contentGroup0 = ClusterSpec.from(ClusterSpec.Type.content, ClusterSpec.Id.from("test"), Optional.of(ClusterSpec.Group.from("0")));
+        ClusterSpec contentGroup1 = ClusterSpec.from(ClusterSpec.Type.content, ClusterSpec.Id.from("test"), Optional.of(ClusterSpec.Group.from("1")));
 
         Set<HostSpec> container0 = new HashSet<>(tester.prepare(application, containerCluster0, container0Size, 1, flavor));
         Set<HostSpec> container1 = new HashSet<>(tester.prepare(application, containerCluster1, container1Size, 1, flavor));
@@ -484,6 +512,24 @@ public class ProvisionTest {
             this.group1 = group1;
             this.group2 = group2;
         }
+        
+        /** Returns a host by cluster name and index, or null if there is no host with the given values in this */
+        public HostSpec hostByMembership(String clusterId, int group, int index) {
+            for (HostSpec host : allHosts) {
+                if ( ! host.membership().isPresent()) continue;
+                ClusterMembership membership = host.membership().get();
+                if (membership.cluster().id().value().equals(clusterId) &&
+                    groupMatches(membership.cluster().group(), group) &&
+                    membership.index() == index)
+                    return host;
+            }
+            return null;
+        }
+        
+        private boolean groupMatches(Optional<ClusterSpec.Group> clusterGroup, int group) {
+            if ( ! clusterGroup.isPresent()) return group==0;
+            return Integer.parseInt(clusterGroup.get().value()) == group;
+        }
 
         public Set<String> hostNames() {
             return allHosts.stream().map(HostSpec::hostname).collect(Collectors.toSet());
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/VirtualNodeProvisioningTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/VirtualNodeProvisioningTest.java
index db4c2941970..35d844dbb73 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/VirtualNodeProvisioningTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/VirtualNodeProvisioningTest.java
@@ -45,7 +45,7 @@ public class VirtualNodeProvisioningTest {
 
     @Test
     public void optimize_sorts_by_more_vms() {
-        List<Node> readyList = new ArrayList<Node>();
+        List<Node> readyList = new ArrayList<>();
         readyList.addAll(tester.makeReadyNodes(2, flavor));
         readyList.addAll(tester.makeReadyVirtualNodes(2, flavor, "parentHost1"));
         readyList.addAll(tester.makeReadyNodes(2, flavor));
@@ -54,7 +54,7 @@ public class VirtualNodeProvisioningTest {
         readyList.addAll(tester.makeReadyVirtualNodes(1, flavor, "parentHost4"));
         readyList.addAll(tester.makeReadyNodes(3, flavor));
         assertEquals(15, readyList.size());
-        List<Node> optimized = GroupPreparer.optimize(readyList);
+        List<Node> optimized = GroupPreparer.stripeOverHosts(readyList);
         assertEquals(15, optimized.size());
         assertEquals("parentHost2", optimized.get(0).parentHostname().get());
         assertEquals("parentHost4", optimized.get(3).parentHostname().get());