You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@helix.apache.org by GitBox <gi...@apache.org> on 2021/03/31 17:51:39 UTC

[GitHub] [helix] jiajunwang commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact

jiajunwang commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r605090940



##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +179,147 @@ private double getAssignmentNormalizedScore(AssignableNode node, AssignableRepli
         .collect(Collectors.toList());
   }
 
-  private List<AssignableReplica> getOrderedAssignableReplica(ClusterModel clusterModel) {
-    Map<String, Set<AssignableReplica>> replicasByResource = clusterModel.getAssignableReplicaMap();
-    List<AssignableReplica> orderedAssignableReplicas =
-        replicasByResource.values().stream().flatMap(replicas -> replicas.stream())
-            .collect(Collectors.toList());
+  private Map<String, MutablePair<Integer, Integer>> computeOverallClusterUtil(
+      List<AssignableNode> nodes) {
+    Map<String, MutablePair<Integer, Integer>> utilizationMap = new HashMap<>();
+    for (AssignableNode node : nodes) {
+      for (String resourceKey : node.getMaxCapacity().keySet()) {
 
-    Map<String, ResourceAssignment> bestPossibleAssignment =
-        clusterModel.getContext().getBestPossibleAssignment();
-    Map<String, ResourceAssignment> baselineAssignment =
-        clusterModel.getContext().getBaselineAssignment();
+        if (utilizationMap.containsKey(resourceKey)) {
+          Integer newUtil = utilizationMap.get(resourceKey).getLeft() + node.getRemainingCapacity()

Review comment:
       getRemainingCapacity() gives you idle capacity, it seems not what you want. Please double-check.

##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -68,23 +71,47 @@ public OptimalAssignment calculate(ClusterModel clusterModel) throws HelixRebala
     List<AssignableNode> nodes = new ArrayList<>(clusterModel.getAssignableNodes().values());
     Set<String> busyInstances =
         getBusyInstances(clusterModel.getContext().getBestPossibleAssignment().values());
-    // Sort the replicas so the input is stable for the greedy algorithm.
-    // For the other algorithm implementation, this sorting could be unnecessary.
-    for (AssignableReplica replica : getOrderedAssignableReplica(clusterModel)) {
+    List<AssignableReplica> toBeAssignedReplicas = clusterModel.getAssignableReplicaMap().values().stream()
+        .flatMap(replicas -> replicas.stream()).collect(Collectors.toList());
+    // Compute overall utilization of the cluster. Capacity dimension -> <total usage, total capacity>
+    Map<String, MutablePair<Integer, Integer>> overallClusterUtilMap =
+        computeOverallClusterUtil(nodes);
+    Map<String, Integer> replicaHashCodeMap = toBeAssignedReplicas.parallelStream().collect(Collectors

Review comment:
       Please add some comments here since the logic has been moved away from where it is used. Might be hard to understand.

##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +179,147 @@ private double getAssignmentNormalizedScore(AssignableNode node, AssignableRepli
         .collect(Collectors.toList());
   }
 
-  private List<AssignableReplica> getOrderedAssignableReplica(ClusterModel clusterModel) {
-    Map<String, Set<AssignableReplica>> replicasByResource = clusterModel.getAssignableReplicaMap();
-    List<AssignableReplica> orderedAssignableReplicas =
-        replicasByResource.values().stream().flatMap(replicas -> replicas.stream())
-            .collect(Collectors.toList());
+  private Map<String, MutablePair<Integer, Integer>> computeOverallClusterUtil(
+      List<AssignableNode> nodes) {
+    Map<String, MutablePair<Integer, Integer>> utilizationMap = new HashMap<>();
+    for (AssignableNode node : nodes) {
+      for (String resourceKey : node.getMaxCapacity().keySet()) {
 
-    Map<String, ResourceAssignment> bestPossibleAssignment =
-        clusterModel.getContext().getBestPossibleAssignment();
-    Map<String, ResourceAssignment> baselineAssignment =
-        clusterModel.getContext().getBaselineAssignment();
+        if (utilizationMap.containsKey(resourceKey)) {
+          Integer newUtil = utilizationMap.get(resourceKey).getLeft() + node.getRemainingCapacity()
+              .get(resourceKey);
+          Integer newCapacity =
+              utilizationMap.get(resourceKey).getLeft() + node.getMaxCapacity().get(resourceKey);
+          // update util
+          utilizationMap.get(resourceKey).setLeft(newUtil);
+          // update capacity
+          utilizationMap.get(resourceKey).setRight(newCapacity);
+        } else {
+          Integer newUtil = node.getRemainingCapacity().get(resourceKey);
+          Integer newCapacity = node.getMaxCapacity().get(resourceKey);
+          utilizationMap.put(resourceKey, new MutablePair<>(newUtil, newCapacity));
+        }
+      }
+    }
+    return utilizationMap;
+  }
 
-    Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
-        Collectors.toMap(AssignableReplica::toString,
-            replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
-            (hash1, hash2) -> hash2));
+  /**
+   * Update the overallClusterUtilMap with newly placed replica
+   */
+  private void updateOverallClusterUtil(
+      Map<String, MutablePair<Integer, Integer>> overallClusterUtilMap, AssignableReplica replica) {
+    for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+      Integer newUtil =
+          overallClusterUtilMap.get(resourceUsage.getKey()).getLeft() - resourceUsage.getValue();
+      overallClusterUtilMap.get(resourceUsage.getKey()).setLeft(newUtil);
+    }
+  }
 
-    // 1. Sort according if the assignment exists in the best possible and/or baseline assignment
-    // 2. Sort according to the state priority. Note that prioritizing the top state is required.
-    // Or the greedy algorithm will unnecessarily shuffle the states between replicas.
-    // 3. Sort according to the resource/partition name.
-    orderedAssignableReplicas.sort((replica1, replica2) -> {
-      String resourceName1 = replica1.getResourceName();
-      String resourceName2 = replica2.getResourceName();
-      if (bestPossibleAssignment.containsKey(resourceName1) == bestPossibleAssignment
-          .containsKey(resourceName2)) {
-        if (baselineAssignment.containsKey(resourceName1) == baselineAssignment
-            .containsKey(resourceName2)) {
-          // If both assignment states have/not have the resource assignment the same,
-          // compare for additional dimensions.
-          int statePriority1 = replica1.getStatePriority();
-          int statePriority2 = replica2.getStatePriority();
-          if (statePriority1 == statePriority2) {
-            // If state priorities are the same, try to randomize the replicas order. Otherwise,
-            // the same replicas might always be moved in each rebalancing. This is because their
-            // placement calculating will always happen at the critical moment while the cluster is
-            // almost close to the expected utilization.
-            //
-            // Note that to ensure the algorithm is deterministic with the same inputs, do not use
-            // Random functions here. Use hashcode based on the cluster topology information to get
-            // a controlled randomized order is good enough.
-            Integer replicaHash1 = replicaHashCodeMap.get(replica1.toString());
-            Integer replicaHash2 = replicaHashCodeMap.get(replica2.toString());
-            if (!replicaHash1.equals(replicaHash2)) {
-              return replicaHash1.compareTo(replicaHash2);
-            } else {
-              // In case of hash collision, return order according to the name.
-              return replica1.toString().compareTo(replica2.toString());
-            }
-          } else {
-            // Note we shall prioritize the replica with a higher state priority,
-            // the smaller priority number means higher priority.
-            return statePriority1 - statePriority2;
-          }
-        } else {
-          // If the baseline assignment contains the assignment, prioritize the replica.
-          return baselineAssignment.containsKey(resourceName1) ? -1 : 1;
+  private Pair<AssignableReplica, List<AssignableReplica>> getNextAssignableReplica(
+      List<AssignableReplica> allReplica,
+      Map<String, MutablePair<Integer, Integer>> overallClusterUtilMap, ClusterModel clusterModel,
+      Map<String, Integer> _replicaHashCodeMap) {
+    List<AssignableReplica> replicaForNextRound = new ArrayList<>();
+    float highestScore = -1;
+    AssignableReplica nextAssinableReplica = null;
+    Map<String, Float> weightMap = new HashMap<>();
+    // compute weight for each capacity dimension
+    for (Map.Entry<String, MutablePair<Integer, Integer>> resourceUsage : overallClusterUtilMap
+        .entrySet()) {
+      float freePercentage =
+          (float) (resourceUsage.getValue().right - resourceUsage.getValue().left) / resourceUsage

Review comment:
       For protecting any possible future errors (for example, we allow overprovisioning in the future), please bound the subtraction result it should be 0 at least, I guess. Or if the later calculation can handle a negative percentage number, then it would be fine here.

##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +179,147 @@ private double getAssignmentNormalizedScore(AssignableNode node, AssignableRepli
         .collect(Collectors.toList());
   }
 
-  private List<AssignableReplica> getOrderedAssignableReplica(ClusterModel clusterModel) {
-    Map<String, Set<AssignableReplica>> replicasByResource = clusterModel.getAssignableReplicaMap();
-    List<AssignableReplica> orderedAssignableReplicas =
-        replicasByResource.values().stream().flatMap(replicas -> replicas.stream())
-            .collect(Collectors.toList());
+  private Map<String, MutablePair<Integer, Integer>> computeOverallClusterUtil(
+      List<AssignableNode> nodes) {
+    Map<String, MutablePair<Integer, Integer>> utilizationMap = new HashMap<>();
+    for (AssignableNode node : nodes) {
+      for (String resourceKey : node.getMaxCapacity().keySet()) {
 
-    Map<String, ResourceAssignment> bestPossibleAssignment =
-        clusterModel.getContext().getBestPossibleAssignment();
-    Map<String, ResourceAssignment> baselineAssignment =
-        clusterModel.getContext().getBaselineAssignment();
+        if (utilizationMap.containsKey(resourceKey)) {
+          Integer newUtil = utilizationMap.get(resourceKey).getLeft() + node.getRemainingCapacity()
+              .get(resourceKey);
+          Integer newCapacity =
+              utilizationMap.get(resourceKey).getLeft() + node.getMaxCapacity().get(resourceKey);
+          // update util
+          utilizationMap.get(resourceKey).setLeft(newUtil);
+          // update capacity
+          utilizationMap.get(resourceKey).setRight(newCapacity);
+        } else {
+          Integer newUtil = node.getRemainingCapacity().get(resourceKey);
+          Integer newCapacity = node.getMaxCapacity().get(resourceKey);
+          utilizationMap.put(resourceKey, new MutablePair<>(newUtil, newCapacity));
+        }
+      }
+    }
+    return utilizationMap;
+  }
 
-    Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
-        Collectors.toMap(AssignableReplica::toString,
-            replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
-            (hash1, hash2) -> hash2));
+  /**
+   * Update the overallClusterUtilMap with newly placed replica
+   */
+  private void updateOverallClusterUtil(
+      Map<String, MutablePair<Integer, Integer>> overallClusterUtilMap, AssignableReplica replica) {
+    for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+      Integer newUtil =
+          overallClusterUtilMap.get(resourceUsage.getKey()).getLeft() - resourceUsage.getValue();
+      overallClusterUtilMap.get(resourceUsage.getKey()).setLeft(newUtil);
+    }
+  }
 
-    // 1. Sort according if the assignment exists in the best possible and/or baseline assignment
-    // 2. Sort according to the state priority. Note that prioritizing the top state is required.
-    // Or the greedy algorithm will unnecessarily shuffle the states between replicas.
-    // 3. Sort according to the resource/partition name.
-    orderedAssignableReplicas.sort((replica1, replica2) -> {
-      String resourceName1 = replica1.getResourceName();
-      String resourceName2 = replica2.getResourceName();
-      if (bestPossibleAssignment.containsKey(resourceName1) == bestPossibleAssignment
-          .containsKey(resourceName2)) {
-        if (baselineAssignment.containsKey(resourceName1) == baselineAssignment
-            .containsKey(resourceName2)) {
-          // If both assignment states have/not have the resource assignment the same,
-          // compare for additional dimensions.
-          int statePriority1 = replica1.getStatePriority();
-          int statePriority2 = replica2.getStatePriority();
-          if (statePriority1 == statePriority2) {
-            // If state priorities are the same, try to randomize the replicas order. Otherwise,
-            // the same replicas might always be moved in each rebalancing. This is because their
-            // placement calculating will always happen at the critical moment while the cluster is
-            // almost close to the expected utilization.
-            //
-            // Note that to ensure the algorithm is deterministic with the same inputs, do not use
-            // Random functions here. Use hashcode based on the cluster topology information to get
-            // a controlled randomized order is good enough.
-            Integer replicaHash1 = replicaHashCodeMap.get(replica1.toString());
-            Integer replicaHash2 = replicaHashCodeMap.get(replica2.toString());
-            if (!replicaHash1.equals(replicaHash2)) {
-              return replicaHash1.compareTo(replicaHash2);
-            } else {
-              // In case of hash collision, return order according to the name.
-              return replica1.toString().compareTo(replica2.toString());
-            }
-          } else {
-            // Note we shall prioritize the replica with a higher state priority,
-            // the smaller priority number means higher priority.
-            return statePriority1 - statePriority2;
-          }
-        } else {
-          // If the baseline assignment contains the assignment, prioritize the replica.
-          return baselineAssignment.containsKey(resourceName1) ? -1 : 1;
+  private Pair<AssignableReplica, List<AssignableReplica>> getNextAssignableReplica(
+      List<AssignableReplica> allReplica,
+      Map<String, MutablePair<Integer, Integer>> overallClusterUtilMap, ClusterModel clusterModel,
+      Map<String, Integer> _replicaHashCodeMap) {
+    List<AssignableReplica> replicaForNextRound = new ArrayList<>();
+    float highestScore = -1;
+    AssignableReplica nextAssinableReplica = null;
+    Map<String, Float> weightMap = new HashMap<>();
+    // compute weight for each capacity dimension

Review comment:
       Should be a separate method. And in this way, you can just pass the weight map to this select replica method.

##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +179,147 @@ private double getAssignmentNormalizedScore(AssignableNode node, AssignableRepli
         .collect(Collectors.toList());
   }
 
-  private List<AssignableReplica> getOrderedAssignableReplica(ClusterModel clusterModel) {
-    Map<String, Set<AssignableReplica>> replicasByResource = clusterModel.getAssignableReplicaMap();
-    List<AssignableReplica> orderedAssignableReplicas =
-        replicasByResource.values().stream().flatMap(replicas -> replicas.stream())
-            .collect(Collectors.toList());
+  private Map<String, MutablePair<Integer, Integer>> computeOverallClusterUtil(
+      List<AssignableNode> nodes) {
+    Map<String, MutablePair<Integer, Integer>> utilizationMap = new HashMap<>();
+    for (AssignableNode node : nodes) {
+      for (String resourceKey : node.getMaxCapacity().keySet()) {
 
-    Map<String, ResourceAssignment> bestPossibleAssignment =
-        clusterModel.getContext().getBestPossibleAssignment();
-    Map<String, ResourceAssignment> baselineAssignment =
-        clusterModel.getContext().getBaselineAssignment();
+        if (utilizationMap.containsKey(resourceKey)) {
+          Integer newUtil = utilizationMap.get(resourceKey).getLeft() + node.getRemainingCapacity()
+              .get(resourceKey);
+          Integer newCapacity =
+              utilizationMap.get(resourceKey).getLeft() + node.getMaxCapacity().get(resourceKey);
+          // update util
+          utilizationMap.get(resourceKey).setLeft(newUtil);
+          // update capacity
+          utilizationMap.get(resourceKey).setRight(newCapacity);
+        } else {
+          Integer newUtil = node.getRemainingCapacity().get(resourceKey);
+          Integer newCapacity = node.getMaxCapacity().get(resourceKey);
+          utilizationMap.put(resourceKey, new MutablePair<>(newUtil, newCapacity));
+        }
+      }
+    }
+    return utilizationMap;
+  }
 
-    Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
-        Collectors.toMap(AssignableReplica::toString,
-            replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
-            (hash1, hash2) -> hash2));
+  /**
+   * Update the overallClusterUtilMap with newly placed replica
+   */
+  private void updateOverallClusterUtil(
+      Map<String, MutablePair<Integer, Integer>> overallClusterUtilMap, AssignableReplica replica) {
+    for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+      Integer newUtil =
+          overallClusterUtilMap.get(resourceUsage.getKey()).getLeft() - resourceUsage.getValue();
+      overallClusterUtilMap.get(resourceUsage.getKey()).setLeft(newUtil);
+    }
+  }
 
-    // 1. Sort according if the assignment exists in the best possible and/or baseline assignment
-    // 2. Sort according to the state priority. Note that prioritizing the top state is required.
-    // Or the greedy algorithm will unnecessarily shuffle the states between replicas.
-    // 3. Sort according to the resource/partition name.
-    orderedAssignableReplicas.sort((replica1, replica2) -> {
-      String resourceName1 = replica1.getResourceName();
-      String resourceName2 = replica2.getResourceName();
-      if (bestPossibleAssignment.containsKey(resourceName1) == bestPossibleAssignment
-          .containsKey(resourceName2)) {
-        if (baselineAssignment.containsKey(resourceName1) == baselineAssignment
-            .containsKey(resourceName2)) {
-          // If both assignment states have/not have the resource assignment the same,
-          // compare for additional dimensions.
-          int statePriority1 = replica1.getStatePriority();
-          int statePriority2 = replica2.getStatePriority();
-          if (statePriority1 == statePriority2) {
-            // If state priorities are the same, try to randomize the replicas order. Otherwise,
-            // the same replicas might always be moved in each rebalancing. This is because their
-            // placement calculating will always happen at the critical moment while the cluster is
-            // almost close to the expected utilization.
-            //
-            // Note that to ensure the algorithm is deterministic with the same inputs, do not use
-            // Random functions here. Use hashcode based on the cluster topology information to get
-            // a controlled randomized order is good enough.
-            Integer replicaHash1 = replicaHashCodeMap.get(replica1.toString());
-            Integer replicaHash2 = replicaHashCodeMap.get(replica2.toString());
-            if (!replicaHash1.equals(replicaHash2)) {
-              return replicaHash1.compareTo(replicaHash2);
-            } else {
-              // In case of hash collision, return order according to the name.
-              return replica1.toString().compareTo(replica2.toString());
-            }
-          } else {
-            // Note we shall prioritize the replica with a higher state priority,
-            // the smaller priority number means higher priority.
-            return statePriority1 - statePriority2;
-          }
-        } else {
-          // If the baseline assignment contains the assignment, prioritize the replica.
-          return baselineAssignment.containsKey(resourceName1) ? -1 : 1;
+  private Pair<AssignableReplica, List<AssignableReplica>> getNextAssignableReplica(
+      List<AssignableReplica> allReplica,
+      Map<String, MutablePair<Integer, Integer>> overallClusterUtilMap, ClusterModel clusterModel,
+      Map<String, Integer> _replicaHashCodeMap) {
+    List<AssignableReplica> replicaForNextRound = new ArrayList<>();
+    float highestScore = -1;
+    AssignableReplica nextAssinableReplica = null;
+    Map<String, Float> weightMap = new HashMap<>();
+    // compute weight for each capacity dimension
+    for (Map.Entry<String, MutablePair<Integer, Integer>> resourceUsage : overallClusterUtilMap
+        .entrySet()) {
+      float freePercentage =
+          (float) (resourceUsage.getValue().right - resourceUsage.getValue().left) / resourceUsage
+              .getValue().right;
+      weightMap.put(resourceUsage.getKey(), freePercentage);
+    }
+    // Compare every replica with current candidate, update candidate if needed
+    for (AssignableReplica replica : allReplica) {
+      // score = SUM(weight * Resource_capacity) where weight = 1/(1-resource_util)
+      float score = 0.01f;
+      for (Map.Entry<String, Integer> resourceCapacity : replica.getCapacity().entrySet()) {
+        // use int to store % * 100
+        int replicaUsageInClusterPoolPct =
+            (resourceCapacity.getValue() * 100) / overallClusterUtilMap
+                .get(resourceCapacity.getKey()).right;
+        score += replicaUsageInClusterPoolPct / (weightMap.get(resourceCapacity.getKey()) + 0.01);
+      }
+      if (nextAssinableReplica == null) {
+        nextAssinableReplica = replica;
+        highestScore = score;
+      } else if (!keepOriginalPreferredReplica(nextAssinableReplica, replica, clusterModel,

Review comment:
       I prefer to keep the sorting algorithm simple. Can we do the following steps,
   1. Calculate the score, and set it to replica (with some wrapper class)
   2. Compare the replicas to find the "maximum" using the customized compare method (which has been put into keepOriginalPreferredReplica in this PR).

##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -68,23 +71,47 @@ public OptimalAssignment calculate(ClusterModel clusterModel) throws HelixRebala
     List<AssignableNode> nodes = new ArrayList<>(clusterModel.getAssignableNodes().values());
     Set<String> busyInstances =
         getBusyInstances(clusterModel.getContext().getBestPossibleAssignment().values());
-    // Sort the replicas so the input is stable for the greedy algorithm.
-    // For the other algorithm implementation, this sorting could be unnecessary.
-    for (AssignableReplica replica : getOrderedAssignableReplica(clusterModel)) {
+    List<AssignableReplica> toBeAssignedReplicas = clusterModel.getAssignableReplicaMap().values().stream()
+        .flatMap(replicas -> replicas.stream()).collect(Collectors.toList());
+    // Compute overall utilization of the cluster. Capacity dimension -> <total usage, total capacity>
+    Map<String, MutablePair<Integer, Integer>> overallClusterUtilMap =
+        computeOverallClusterUtil(nodes);
+    Map<String, Integer> replicaHashCodeMap = toBeAssignedReplicas.parallelStream().collect(Collectors
+        .toMap(AssignableReplica::toString,
+            replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
+            (hash1, hash2) -> hash2));
+    Pair<AssignableReplica, List<AssignableReplica>> replicaRes =
+        getNextAssignableReplica(toBeAssignedReplicas, overallClusterUtilMap, clusterModel,
+            replicaHashCodeMap);
+    AssignableReplica replica = replicaRes.getLeft();
+    toBeAssignedReplicas = replicaRes.getRight();
+
+    while (replica != null) {

Review comment:
       Could do-while fit better here?




-- 
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.

For queries about this service, please contact Infrastructure at:
users@infra.apache.org



---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@helix.apache.org
For additional commands, e-mail: reviews-help@helix.apache.org