Added FlavorSpareChecker

2 files changed, 335 insertions, 0 deletions

diff --git a/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorSpareChecker.java b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorSpareChecker.java
new file mode 100644
index 00000000000..b9556836fee
--- /dev/null
+++ b/node-repository/src/main/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorSpareChecker.java
@@ -0,0 +1,105 @@
+// 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.vespa.hosted.provision.Node;
+
+import java.util.Collections;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Definitions:
+ * - Wanted flavor: The flavor that is the node prefers, for example by specifying in services.xml
+ * - Node-repo flavor: The flavor that the node actually has (Either the wanted flavor or a flavor that transitively
+ *                     replaces the wanted flavor)
+ * - Replacee flavor: Flavor x is replacee of y iff x transitively replaces y
+ * - Immediate replacee flavor: Flavor x is an immediate replacee of flavor y iff x directly replaces y.
+ *
+ * @author freva
+ */
+public class FlavorSpareChecker {
+    private final SpareNodesPolicy spareNodesPolicy;
+    private final Map<Flavor, FlavorSpareCount> spareCountByFlavor;
+
+    public FlavorSpareChecker(SpareNodesPolicy spareNodesPolicy, Map<Flavor, FlavorSpareCount> spareCountByFlavor) {
+        this.spareNodesPolicy = spareNodesPolicy;
+        this.spareCountByFlavor = spareCountByFlavor;
+    }
+
+    public void updateReadyAndActiveCountsByFlavor(Map<Flavor, Map<Node.State, Long>> numberOfNodesByFlavorByState) {
+        spareCountByFlavor.forEach((flavor, flavorSpareCount) -> {
+            Map<Node.State, Long> numberOfNodesByState = numberOfNodesByFlavorByState.getOrDefault(flavor, Collections.emptyMap());
+            flavorSpareCount.updateReadyAndActiveCounts(
+                    numberOfNodesByState.getOrDefault(Node.State.ready, 0L),
+                    numberOfNodesByState.getOrDefault(Node.State.active, 0L));
+        });
+    }
+
+    public boolean canRetireAllocatedNodeWithFlavor(Flavor flavor) {
+        Set<FlavorSpareCount> possibleNewFlavors = findPossibleReplacementFlavorFor(spareCountByFlavor.get(flavor));
+        possibleNewFlavors.forEach(FlavorSpareCount::decrementNumberOfSpares);
+        return !possibleNewFlavors.isEmpty();
+    }
+
+    public boolean canRetireUnallocatedNodeWithFlavor(Flavor flavor) {
+        FlavorSpareCount flavorSpareCount = spareCountByFlavor.get(flavor);
+        if (flavorSpareCount.hasReady() && spareNodesPolicy.hasSpare(flavorSpareCount)) {
+            flavorSpareCount.decrementNumberOfSpares();
+            return true;
+        }
+
+        return false;
+    }
+
+
+    /**
+     * Returns a set of possible new flavors that can replace this flavor given current node allocation.
+     * If the set is empty, there are not enough spare nodes to safely retire this flavor.
+     *
+     * The algorithm is:
+     *  for all possible wanted flavor, check:
+     *      1: Sum of spare nodes of flavor f and all replacee flavors of f is > 0
+     *      2a: Number of ready nodes of flavor f is > 0
+     *      2b: Verify 1 & 2a for all immediate replacee of f, f_i, where sum of ready nodes of f_i and all
+     *          replacee flavors of f_i is > 0
+     * Only 2a OR 2b need to be satisfied.
+     */
+    private Set<FlavorSpareCount> findPossibleReplacementFlavorFor(FlavorSpareCount flavorSpareCount) {
+        Set<FlavorSpareCount> possibleNewFlavors = new HashSet<>();
+        for (FlavorSpareCount possibleWantedFlavor : flavorSpareCount.getPossibleWantedFlavors()) {
+            Set<FlavorSpareCount> newFlavors = verifyReplacementConditions(possibleWantedFlavor);
+            if (newFlavors.isEmpty()) return Collections.emptySet();
+            else possibleNewFlavors.addAll(newFlavors);
+        }
+
+        return possibleNewFlavors;
+    }
+
+    private Set<FlavorSpareCount> verifyReplacementConditions(FlavorSpareCount flavorSpareCount) {
+        Set<FlavorSpareCount> possibleNewFlavors = new HashSet<>();
+        // Breaks condition 1, end
+        if (! spareNodesPolicy.hasSpare(flavorSpareCount)) return Collections.emptySet();
+
+        // Condition 2a
+        if (flavorSpareCount.hasReady()) {
+            possibleNewFlavors.add(flavorSpareCount);
+
+            // Condition 2b
+        } else {
+            for (FlavorSpareCount possibleNewFlavor : flavorSpareCount.getImmediateReplacees()) {
+                if (possibleNewFlavor.getSumOfReadyAmongReplacees() == 0) continue;
+
+                Set<FlavorSpareCount> newFlavors = verifyReplacementConditions(possibleNewFlavor);
+                if (newFlavors.isEmpty()) return Collections.emptySet();
+                else possibleNewFlavors.addAll(newFlavors);
+            }
+        }
+        return possibleNewFlavors;
+    }
+
+    public interface SpareNodesPolicy {
+        boolean hasSpare(FlavorSpareCount flavorSpareCount);
+    }
+}
diff --git a/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorSpareCheckerTest.java b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorSpareCheckerTest.java
new file mode 100644
index 00000000000..8418d3e6d47
--- /dev/null
+++ b/node-repository/src/test/java/com/yahoo/vespa/hosted/provision/provisioning/FlavorSpareCheckerTest.java
@@ -0,0 +1,230 @@
+// 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 org.junit.Before;
+import org.junit.Test;
+
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.stream.Collectors;
+import java.util.stream.Stream;
+
+import static org.junit.Assert.assertFalse;
+import static org.junit.Assert.assertTrue;
+import static org.mockito.Mockito.doNothing;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.times;
+import static org.mockito.Mockito.verify;
+import static org.mockito.Mockito.when;
+
+/**
+ * @author freva
+ */
+public class FlavorSpareCheckerTest {
+    /* Creates flavors where 'replaces' graph that looks like this (largest flavor at the bottom), in
+     * parenthesis is the number of spare nodes for that flavor:
+     * (1) 5
+     *     |
+     *     |
+     * (2) 3      4 (5)           8 (3)
+     *      \   /  \              |
+     *       \ /    \             |
+     *    (2) 1      6 (0)        7 (0)
+     *       / \
+     *      /   \
+     * (3) 0     2 (1)
+     */
+    private static final List<Flavor> flavors = FlavorSpareCountTest.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.singletonList(4),   // 6 -> {4}
+            Collections.singletonList(8),   // 7 -> {8}
+            Collections.emptyList());        // 8 -> {}
+
+    private final Map<Flavor, FlavorSpareCount> flavorSpareCountByFlavor = flavors.stream()
+            .collect(Collectors.toMap(
+                    i -> i,
+                    i -> mock(FlavorSpareCount.class)));
+
+    private final FlavorSpareChecker.SpareNodesPolicy spareNodesPolicy = mock(FlavorSpareChecker.SpareNodesPolicy.class);
+    private FlavorSpareChecker flavorSpareChecker = new FlavorSpareChecker(spareNodesPolicy, flavorSpareCountByFlavor);
+
+
+    @Test
+    public void canRetireUnallocated_Successfully() {
+        Flavor flavorToRetire = flavors.get(0);
+        FlavorSpareCount flavorSpareCount = flavorSpareCountByFlavor.get(flavorToRetire);
+        when(flavorSpareCount.hasReady()).thenReturn(true);
+        when(spareNodesPolicy.hasSpare(flavorSpareCount)).thenReturn(true);
+
+        assertTrue(flavorSpareChecker.canRetireUnallocatedNodeWithFlavor(flavorToRetire));
+        verifyDecrement(0);
+    }
+
+    @Test
+    public void canRetireUnallocated_NoReadyForFlavor() {
+        Flavor flavorToRetire = flavors.get(0);
+        FlavorSpareCount flavorSpareCount = flavorSpareCountByFlavor.get(flavorToRetire);
+        when(spareNodesPolicy.hasSpare(flavorSpareCount)).thenReturn(true);
+
+        assertFalse(flavorSpareChecker.canRetireUnallocatedNodeWithFlavor(flavorToRetire));
+        verifyDecrement();
+    }
+
+    @Test
+    public void canRetireUnallocated_NoSpareForFlavor() {
+        Flavor flavorToRetire = flavors.get(0);
+        FlavorSpareCount flavorSpareCount = flavorSpareCountByFlavor.get(flavorToRetire);
+        when(flavorSpareCount.hasReady()).thenReturn(true);
+
+        assertFalse(flavorSpareChecker.canRetireUnallocatedNodeWithFlavor(flavorToRetire));
+        verifyDecrement();
+    }
+
+    @Test
+    public void canRetireAllocated_LeafFlavor_Successfully() {
+        Flavor flavorToRetire = flavors.get(0);
+
+        // If we want to retire flavor 0, then we must have enough spares & ready of flavor 0 and all
+        // other flavor that it replaces transitively
+        Stream.of(0, 1, 3, 4, 5)
+                .map(flavors::get)
+                .map(flavorSpareCountByFlavor::get)
+                .forEach(flavorSpareCount -> {
+                    when(flavorSpareCount.hasReady()).thenReturn(true);
+                    when(spareNodesPolicy.hasSpare(flavorSpareCount)).thenReturn(true);
+                });
+
+        assertTrue(flavorSpareChecker.canRetireAllocatedNodeWithFlavor(flavorToRetire));
+        verifyDecrement(0, 1, 3, 4, 5);
+    }
+
+    @Test
+    public void canRetireAllocated_LeafFlavor_NoSparesForPossibleWantedFlavor() {
+        Flavor flavorToRetire = flavors.get(0);
+
+        // Flavor 4 is transitively replaced by flavor 0, even though we have enough spares of flavor 0,
+        // we cannot retire it if there are not enough spares of flavor 4
+        Stream.of(0, 1, 3, 5)
+                .map(flavors::get)
+                .map(flavorSpareCountByFlavor::get)
+                .forEach(flavorSpareCount -> {
+                    when(flavorSpareCount.hasReady()).thenReturn(true);
+                    when(spareNodesPolicy.hasSpare(flavorSpareCount)).thenReturn(true);
+                });
+
+        assertFalse(flavorSpareChecker.canRetireAllocatedNodeWithFlavor(flavorToRetire));
+        verifyDecrement();
+    }
+
+    @Test
+    public void canRetireAllocated_CenterNode_Successfully() {
+        Flavor flavorToRetire = flavors.get(1);
+
+        Stream.of(1, 3, 4, 5)
+                .map(flavors::get)
+                .map(flavorSpareCountByFlavor::get)
+                .forEach(flavorSpareCount -> {
+                    when(flavorSpareCount.hasReady()).thenReturn(true);
+                    when(spareNodesPolicy.hasSpare(flavorSpareCount)).thenReturn(true);
+                });
+
+        assertTrue(flavorSpareChecker.canRetireAllocatedNodeWithFlavor(flavorToRetire));
+        verifyDecrement(1, 3, 4, 5);
+    }
+
+    @Test
+    public void canRetireAllocated_CenterNode_NoNodeRepoFlavorNodes_Successfully() {
+        Flavor flavorToRetire = flavors.get(1);
+
+        // If we want to retire a node with node-repo flavor 1, but there are no ready nodes of flavor-1,
+        // we must ensure there are spare nodes of flavors that replace flavor 1
+        Stream.of(0, 1, 2, 3, 4, 5)
+                .map(flavors::get)
+                .map(flavorSpareCountByFlavor::get)
+                .forEach(flavorSpareCount -> {
+                    when(flavorSpareCount.hasReady()).thenReturn(true);
+                    when(spareNodesPolicy.hasSpare(flavorSpareCount)).thenReturn(true);
+                });
+        when(flavorSpareCountByFlavor.get(flavorToRetire).hasReady()).thenReturn(false);
+        when(flavorSpareCountByFlavor.get(flavors.get(0)).getSumOfReadyAmongReplacees()).thenReturn(1L);
+        when(flavorSpareCountByFlavor.get(flavors.get(2)).getSumOfReadyAmongReplacees()).thenReturn(1L);
+
+        assertTrue(flavorSpareChecker.canRetireAllocatedNodeWithFlavor(flavorToRetire));
+        verifyDecrement(0, 2, 3, 4, 5);
+    }
+
+    @Test
+    public void canRetireAllocated_CenterNode_NoNodeRepoFlavorNodes_NoImmediateSpare() {
+        Flavor flavorToRetire = flavors.get(1);
+
+        // Same as above, but now one of the flavors that could replace flavor 1 (flavor 2) does not have enough spares
+        Stream.of(0, 1, 3, 4, 5)
+                .map(flavors::get)
+                .map(flavorSpareCountByFlavor::get)
+                .forEach(flavorSpareCount -> {
+                    when(flavorSpareCount.hasReady()).thenReturn(true);
+                    when(spareNodesPolicy.hasSpare(flavorSpareCount)).thenReturn(true);
+                });
+        when(flavorSpareCountByFlavor.get(flavorToRetire).hasReady()).thenReturn(false);
+        when(flavorSpareCountByFlavor.get(flavors.get(0)).getSumOfReadyAmongReplacees()).thenReturn(1L);
+        when(flavorSpareCountByFlavor.get(flavors.get(2)).getSumOfReadyAmongReplacees()).thenReturn(1L);
+
+        assertFalse(flavorSpareChecker.canRetireAllocatedNodeWithFlavor(flavorToRetire));
+        verifyDecrement();
+    }
+
+    @Test
+    public void canRetireAllocated_CenterNode_NoNodeRepoFlavorNodes_SkipEmptyImmediate() {
+        Flavor flavorToRetire = flavors.get(1);
+
+        // Flavor 2 still has no spares, but also the sum of ready nodes in its replaces tree is 0, so we should
+        // be able to continue
+        Stream.of(0, 1, 3, 4, 5)
+                .map(flavors::get)
+                .map(flavorSpareCountByFlavor::get)
+                .forEach(flavorSpareCount -> {
+                    when(flavorSpareCount.hasReady()).thenReturn(true);
+                    when(spareNodesPolicy.hasSpare(flavorSpareCount)).thenReturn(true);
+                });
+        when(flavorSpareCountByFlavor.get(flavorToRetire).hasReady()).thenReturn(false);
+        when(flavorSpareCountByFlavor.get(flavors.get(0)).getSumOfReadyAmongReplacees()).thenReturn(1L);
+        when(flavorSpareCountByFlavor.get(flavors.get(2)).getSumOfReadyAmongReplacees()).thenReturn(0L);
+
+        assertTrue(flavorSpareChecker.canRetireAllocatedNodeWithFlavor(flavorToRetire));
+        verifyDecrement(0, 3, 4, 5);
+    }
+
+    private void verifyDecrement(int... decrementFlavorIds) {
+        Set<Flavor> decrementedFlavors = Arrays.stream(decrementFlavorIds).boxed().map(flavors::get).collect(Collectors.toSet());
+        for (Flavor flavor : flavors) {
+            int times = decrementedFlavors.contains(flavor) ? 1 : 0;
+            verify(flavorSpareCountByFlavor.get(flavor), times(times)).decrementNumberOfSpares();
+        }
+    }
+
+    @Before
+    public void setup() {
+        Map<Flavor, FlavorSpareCount> flavorSpareCountGraph = FlavorSpareCount.constructFlavorSpareCountGraph(flavors);
+        flavorSpareCountByFlavor.forEach((flavor, flavorSpareCount) -> {
+            Set<FlavorSpareCount> possibleWantedFlavors = flavorSpareCountGraph.get(flavor).getPossibleWantedFlavors()
+                    .stream().map(FlavorSpareCount::getFlavor).map(flavorSpareCountByFlavor::get).collect(Collectors.toSet());
+            Set<FlavorSpareCount> immediateReplacees = flavorSpareCountGraph.get(flavor).getImmediateReplacees()
+                    .stream().map(FlavorSpareCount::getFlavor).map(flavorSpareCountByFlavor::get).collect(Collectors.toSet());
+
+            doNothing().when(flavorSpareCount).decrementNumberOfSpares();
+            when(flavorSpareCount.hasReady()).thenReturn(false);
+            when(flavorSpareCount.getPossibleWantedFlavors()).thenReturn(possibleWantedFlavors);
+            when(flavorSpareCount.getImmediateReplacees()).thenReturn(immediateReplacees);
+            when(spareNodesPolicy.hasSpare(flavorSpareCount)).thenReturn(false);
+        });
+    }
+}