Merge pull request #16657 from vespa-engine/jonmv/mind-the-gaps

Jonmv/mind the gaps

6 files changed, 152 insertions, 35 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 543e452c810..0a22cc1cc58 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
@@ -20,6 +20,7 @@ import com.yahoo.vespa.hosted.provision.provisioning.HostProvisioner.HostSharing
 
 import java.util.List;
 import java.util.Optional;
+import java.util.function.Supplier;
 import java.util.stream.Collectors;
 
 /**
@@ -51,15 +52,15 @@ public class GroupPreparer {
      * @param requestedNodes     a specification of the requested nodes
      * @param surplusActiveNodes currently active nodes which are available to be assigned to this group.
      *                           This method will remove from this list if it finds it needs additional nodes
-     * @param highestIndex       the current highest node index among all active nodes in this cluster.
-     *                           This method will increase this number when it allocates new nodes to the cluster.
+     * @param indices            the next available node indices for this cluster.
+     *                           This method will consume these when it allocates new nodes to the cluster.
      * @return the list of nodes this cluster group will have allocated if activated
      */
     // Note: This operation may make persisted changes to the set of reserved and inactive nodes,
     // but it may not change the set of active nodes, as the active nodes must stay in sync with the
     // active config model which is changed on activate
     public List<Node> prepare(ApplicationId application, ClusterSpec cluster, NodeSpec requestedNodes,
-                              List<Node> surplusActiveNodes, MutableInteger highestIndex, int wantedGroups) {
+                              List<Node> surplusActiveNodes, NodeIndices indices, int wantedGroups) {
 
         String allocateOsRequirement = allocateOsRequirementFlag
                 .with(FetchVector.Dimension.APPLICATION_ID, application.serializedForm())
@@ -68,16 +69,16 @@ public class GroupPreparer {
         // Try preparing in memory without global unallocated lock. Most of the time there should be no changes and we
         // can return nodes previously allocated.
         {
-            MutableInteger probePrepareHighestIndex = new MutableInteger(highestIndex.get());
             NodeAllocation probeAllocation = prepareAllocation(application, cluster, requestedNodes, surplusActiveNodes,
-                                                               probePrepareHighestIndex, wantedGroups, PROBE_LOCK,
+                                                               indices::probeNext, wantedGroups, PROBE_LOCK,
                                                                allocateOsRequirement);
             if (probeAllocation.fulfilledAndNoChanges()) {
                 List<Node> acceptedNodes = probeAllocation.finalNodes();
                 surplusActiveNodes.removeAll(acceptedNodes);
-                highestIndex.set(probePrepareHighestIndex.get());
+                indices.commitProbe();
                 return acceptedNodes;
             }
+            indices.resetProbe();
         }
 
         // There were some changes, so re-do the allocation with locks
@@ -85,7 +86,7 @@ public class GroupPreparer {
              Mutex allocationLock = nodeRepository.nodes().lockUnallocated()) {
 
             NodeAllocation allocation = prepareAllocation(application, cluster, requestedNodes, surplusActiveNodes,
-                                                          highestIndex, wantedGroups, allocationLock,
+                                                          indices::next, wantedGroups, allocationLock,
                                                           allocateOsRequirement);
 
             if (nodeRepository.zone().getCloud().dynamicProvisioning()) {
@@ -133,11 +134,11 @@ public class GroupPreparer {
     }
 
     private NodeAllocation prepareAllocation(ApplicationId application, ClusterSpec cluster, NodeSpec requestedNodes,
-                                             List<Node> surplusActiveNodes, MutableInteger highestIndex, int wantedGroups,
+                                             List<Node> surplusActiveNodes, Supplier<Integer> nextIndex, int wantedGroups,
                                              Mutex allocationLock, String allocateOsRequirement) {
         LockedNodeList allNodes = nodeRepository.nodes().list(allocationLock);
         NodeAllocation allocation = new NodeAllocation(allNodes, application, cluster, requestedNodes,
-                highestIndex, nodeRepository);
+                nextIndex, nodeRepository);
         NodePrioritizer prioritizer = new NodePrioritizer(
                 allNodes, application, cluster, requestedNodes, wantedGroups,
                 nodeRepository.zone().getCloud().dynamicProvisioning(), nodeRepository.nameResolver(),
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeAllocation.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeAllocation.java
index d5d221cba7c..6f323955ac7 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeAllocation.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeAllocation.java
@@ -25,6 +25,7 @@ import java.util.Map;
 import java.util.Optional;
 import java.util.Set;
 import java.util.function.Predicate;
+import java.util.function.Supplier;
 import java.util.stream.Collectors;
 
 /**
@@ -71,18 +72,18 @@ class NodeAllocation {
     private final Set<Integer> indexes = new HashSet<>();
 
     /** The next membership index to assign to a new node */
-    private final MutableInteger highestIndex;
+    private final Supplier<Integer> nextIndex;
 
     private final NodeRepository nodeRepository;
     private final NodeResourceLimits nodeResourceLimits;
 
     NodeAllocation(NodeList allNodes, ApplicationId application, ClusterSpec cluster, NodeSpec requestedNodes,
-                   MutableInteger highestIndex, NodeRepository nodeRepository) {
+                   Supplier<Integer> nextIndex, NodeRepository nodeRepository) {
         this.allNodes = allNodes;
         this.application = application;
         this.cluster = cluster;
         this.requestedNodes = requestedNodes;
-        this.highestIndex = highestIndex;
+        this.nextIndex = nextIndex;
         this.nodeRepository = nodeRepository;
         nodeResourceLimits = new NodeResourceLimits(nodeRepository);
     }
@@ -135,7 +136,7 @@ class NodeAllocation {
                     continue;
                 }
                 candidate = candidate.allocate(application,
-                                               ClusterMembership.from(cluster, highestIndex.add(1)),
+                                               ClusterMembership.from(cluster, nextIndex.get()),
                                                requestedNodes.resources().orElse(candidate.resources()),
                                                nodeRepository.clock().instant());
                 if (candidate.isValid())
@@ -257,7 +258,6 @@ class NodeAllocation {
         }
         candidate = candidate.withNode(node);
         indexes.add(node.allocation().get().membership().index());
-        highestIndex.set(Math.max(highestIndex.get(), node.allocation().get().membership().index()));
         nodes.put(node.hostname(), candidate);
         return node;
     }
@@ -284,7 +284,7 @@ class NodeAllocation {
         return requestedNodes.fulfilledBy(accepted);
     }
 
-    /** Returns true this allocation was already fulfilled and resulted in no new changes */
+    /** Returns true if this allocation was already fulfilled and resulted in no new changes */
     public boolean fulfilledAndNoChanges() {
         return fulfilled() && reservableNodes().isEmpty() && newNodes().isEmpty();
     }
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeIndices.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeIndices.java
new file mode 100644
index 00000000000..da4ae2a119e
--- /dev/null
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/NodeIndices.java
@@ -0,0 +1,56 @@
+// Copyright Verizon Media. 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.ClusterSpec;
+import com.yahoo.vespa.hosted.provision.NodeList;
+
+import java.util.List;
+
+import static java.util.Comparator.naturalOrder;
+
+/**
+ * Tracks indices of a node cluster, and proposes the index of the next allocation.
+ *
+ * @author jonmv
+ */
+class NodeIndices {
+
+    private final List<Integer> used;
+
+    private int last;
+    private int probe;
+
+    /** Pass the list of current indices in the cluster, and whether to fill gaps or not. */
+    NodeIndices(List<Integer> used, boolean compact) {
+        this.used = List.copyOf(used);
+        this.last = compact ? -1 : used.stream().max(naturalOrder()).orElse(-1);
+        this.probe = last;
+    }
+
+    /** Returns the next available index and commits to using it. Throws if a probe is ongoing. */
+    int next() {
+        if (probe != last)
+            throw new IllegalStateException("Must commit ongoing probe before calling 'next'");
+
+        probeNext();
+        commitProbe();
+        return last;
+    }
+
+    /** Returns the next available index, without committing to using it. Yields increasing indices when called multiple times. */
+    int probeNext() {
+        while (used.contains(++probe));
+        return probe;
+    }
+
+    /** Commits to using all indices returned by an ongoing probe. */
+    void commitProbe() {
+        last = probe;
+    }
+
+    /** Resets any probed state to what's currently committed. */
+    void resetProbe() {
+        probe = last;
+    }
+
+}
diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/Preparer.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/Preparer.java
index 87b3742efb4..2eee3c3f01c 100644
--- a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/Preparer.java
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/Preparer.java
@@ -8,6 +8,7 @@ import com.yahoo.config.provision.OutOfCapacityException;
 import com.yahoo.lang.MutableInteger;
 import com.yahoo.vespa.flags.FlagSource;
 import com.yahoo.vespa.hosted.provision.Node;
+import com.yahoo.vespa.hosted.provision.NodeList;
 import com.yahoo.vespa.hosted.provision.NodeRepository;
 import com.yahoo.vespa.hosted.provision.node.Agent;
 
@@ -60,13 +61,17 @@ class Preparer {
     private List<Node> prepareNodes(ApplicationId application, ClusterSpec cluster, NodeSpec requestedNodes, int wantedGroups) {
         List<Node> surplusNodes = findNodesInRemovableGroups(application, cluster, wantedGroups);
 
-        MutableInteger highestIndex = new MutableInteger(findHighestIndex(application, cluster));
+        List<Integer> usedIndices = nodeRepository.nodes().list()
+                                                  .owner(application)
+                                                  .cluster(cluster.id())
+                                                  .mapToList(node -> node.allocation().get().membership().index());
+        NodeIndices indices = new NodeIndices(usedIndices, ! cluster.type().isContent());
         List<Node> acceptedNodes = new ArrayList<>();
         for (int groupIndex = 0; groupIndex < wantedGroups; groupIndex++) {
             ClusterSpec clusterGroup = cluster.with(Optional.of(ClusterSpec.Group.from(groupIndex)));
             List<Node> accepted = groupPreparer.prepare(application, clusterGroup,
                                                         requestedNodes.fraction(wantedGroups), surplusNodes,
-                                                        highestIndex, wantedGroups);
+                                                        indices, wantedGroups);
             replace(acceptedNodes, accepted);
         }
         moveToActiveGroup(surplusNodes, wantedGroups, cluster.group());
@@ -120,21 +125,4 @@ class Preparer {
         return list;
     }
 
-    /**
-     * Returns the highest index number of all active and failed nodes in this cluster, or -1 if there are no nodes.
-     * We include failed nodes to avoid reusing the index of the failed node in the case where the failed node is the
-     * node with the highest index.
-     */
-    private int findHighestIndex(ApplicationId application, ClusterSpec cluster) {
-        int highestIndex = -1;
-        for (Node node : nodeRepository.nodes().list(Node.State.allocatedStates().toArray(new Node.State[0])).owner(application)) {
-            ClusterSpec nodeCluster = node.allocation().get().membership().cluster();
-            if ( ! nodeCluster.id().equals(cluster.id())) continue;
-            if ( ! nodeCluster.type().equals(cluster.type())) continue;
-
-            highestIndex = Math.max(node.allocation().get().membership().index(), highestIndex);
-        }
-        return highestIndex;
-    }
-
 }
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/InfraDeployerImplTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/InfraDeployerImplTest.java
index f4d8bbfcb21..6f50cbf9803 100644
--- a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/InfraDeployerImplTest.java
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/InfraDeployerImplTest.java
@@ -150,7 +150,7 @@ public class InfraDeployerImplTest {
         Node node = tester.addHost("id-" + id, "node-" + id, "default", nodeType);
         Optional<Node> nodeWithAllocation = wantedVespaVersion.map(version -> {
             ClusterSpec clusterSpec = application.getClusterSpecWithVersion(version).with(Optional.of(ClusterSpec.Group.from(0)));
-            ClusterMembership membership = ClusterMembership.from(clusterSpec, 1);
+            ClusterMembership membership = ClusterMembership.from(clusterSpec, 0);
             Allocation allocation = new Allocation(application.getApplicationId(), membership, node.resources(), Generation.initial(), false);
             return node.with(allocation);
         });
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/NodeIncidesTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/NodeIncidesTest.java
new file mode 100644
index 00000000000..eee9c2ffc01
--- /dev/null
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/NodeIncidesTest.java
@@ -0,0 +1,72 @@
+// Copyright Verizon Media. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
+package com.yahoo.vespa.hosted.provision.provisioning;
+
+import org.junit.Test;
+
+import java.util.List;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * @author jonmv
+ */
+public class NodeIncidesTest {
+
+    @Test
+    public void testNonCompactIndices() {
+        NodeIndices indices = new NodeIndices(List.of(1, 3, 4), false);
+        assertEquals(5, indices.probeNext());
+        assertEquals(6, indices.probeNext());
+
+        indices.resetProbe();
+        assertEquals(5, indices.probeNext());
+        assertEquals(6, indices.probeNext());
+
+        indices.commitProbe();
+        assertEquals(7, indices.probeNext());
+        assertEquals(8, indices.probeNext());
+
+        indices.resetProbe();
+        assertEquals(7, indices.next());
+        assertEquals(8, indices.next());
+
+        assertEquals(9, indices.probeNext());
+        try {
+            indices.next();
+        }
+        catch (IllegalStateException e) {
+            assertEquals("Must commit ongoing probe before calling 'next'", e.getMessage());
+        }
+    }
+
+
+    @Test
+    public void testCompactIndices() {
+        NodeIndices indices = new NodeIndices(List.of(1, 3, 4), true);
+        assertEquals(0, indices.probeNext());
+        assertEquals(2, indices.probeNext());
+        assertEquals(5, indices.probeNext());
+        assertEquals(6, indices.probeNext());
+
+        indices.resetProbe();
+        assertEquals(0, indices.probeNext());
+        assertEquals(2, indices.probeNext());
+
+        indices.commitProbe();
+        assertEquals(5, indices.probeNext());
+        assertEquals(6, indices.probeNext());
+
+        indices.resetProbe();
+        assertEquals(5, indices.next());
+        assertEquals(6, indices.next());
+
+        assertEquals(7, indices.probeNext());
+        try {
+            indices.next();
+        }
+        catch (IllegalStateException e) {
+            assertEquals("Must commit ongoing probe before calling 'next'", e.getMessage());
+        }
+    }
+
+}