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/30 21:25:57 UTC
[GitHub] [helix] xyuanlu opened a new pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
xyuanlu opened a new pull request #1691:
URL: https://github.com/apache/helix/pull/1691
### Issues
- [X] My PR addresses the following Helix issues and references them in the PR description:
#1653 Gracefully handle very large partitions in WAGED
### Description
- [X] Here are some details about my PR, including screenshots of any UI changes:
Every time we chose the replica that has highest impact on the whole cluster when state priority is the same.
Total impact = SUM(weight * Resource_capacity) where weight = 1/(1-resource_util)
where weight of each capacity dimension = 1/(1-usagePct)
### Tests
- [X] The following tests are written for this issue:
TestConstraintBasedAlgorithm.testSortingByResourceCapacity()
This newly added test is failing on master, pass with this PR.
- The following is the result of the "mvn test" command on the appropriate module:
(If CI test fails due to known issue, please specify the issue and test PR locally. Then copy & paste the result of "mvn test" to here.)
### Documentation (Optional)
- In case of new functionality, my PR adds documentation in the following wiki page:
(Link the GitHub wiki you added)
### Commits
- My commits all reference appropriate Apache Helix GitHub issues in their subject lines. In addition, my commits follow the guidelines from "[How to write a good git commit message](http://chris.beams.io/posts/git-commit/)":
1. Subject is separated from body by a blank line
1. Subject is limited to 50 characters (not including Jira issue reference)
1. Subject does not end with a period
1. Subject uses the imperative mood ("add", not "adding")
1. Body wraps at 72 characters
1. Body explains "what" and "why", not "how"
### Code Quality
- My diff has been formatted using helix-style.xml
(helix-style-intellij.xml if IntelliJ IDE is used)
--
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
[GitHub] [helix] NealSun96 commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r604527621
##########
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)) {
Review comment:
`resourceKey` is not the best name, because Resource has a meaning in WAGED. Maybe `capacityKey` is better.
##########
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,
+ _replicaHashCodeMap, highestScore, score)) {
+ highestScore = score;
+ if (nextAssinableReplica != null) {
+ replicaForNextRound.add(nextAssinableReplica);
}
+ nextAssinableReplica = replica;
} else {
- // If the best possible assignment contains the assignment, prioritize the replica.
- return bestPossibleAssignment.containsKey(resourceName1) ? -1 : 1;
+ replicaForNextRound.add(replica);
}
- });
- return orderedAssignableReplicas;
+ }
+ return new MutablePair<>(nextAssinableReplica, replicaForNextRound);
Review comment:
Why does `replicaForNextRound` need to be computed and returned by `getNextAssignableReplica`? It looks like it has no purpose in `getNextAssignableReplica`, because the logic is to find the replica with the highest score.
Would it be more efficient to just remove the "best replica" from the `toBeAssignedReplicas` that's already computed in the outer scope?
##########
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 =
Review comment:
The Pair usage makes it very unclear what each number represents, especially when this map is passed into later functions. The references of `left` and `right` has no obvious meaning later on.
I suggest:
1. getting rid of the `total capacity`. As I commented later, seems like the calculation cancels out `total capacity` and it may not be needed at all;
2. creating helper functions in ClusterModel with meaningful names, and leave all calculations/updates in the helper functions;
3. using 2 maps with meaningful names.
##########
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) {
Optional<AssignableNode> maybeBestNode =
getNodeWithHighestPoints(replica, nodes, clusterModel.getContext(), busyInstances,
optimalAssignment);
// stop immediately if any replica cannot find best assignable node
- if (optimalAssignment.hasAnyFailure()) {
- String errorMessage = String
- .format("Unable to find any available candidate node for partition %s; Fail reasons: %s",
+ if (!maybeBestNode.isPresent() || optimalAssignment.hasAnyFailure()) {
+ String errorMessage = String.format(
+ "Unable to find any available candidate node for partition %s; Fail reasons: %s",
replica.getPartitionName(), optimalAssignment.getFailures());
+ System.out.println(String.format(
Review comment:
NIT: might want to remove this.
##########
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,
+ _replicaHashCodeMap, highestScore, score)) {
+ highestScore = score;
+ if (nextAssinableReplica != null) {
+ replicaForNextRound.add(nextAssinableReplica);
}
+ nextAssinableReplica = replica;
} else {
- // If the best possible assignment contains the assignment, prioritize the replica.
- return bestPossibleAssignment.containsKey(resourceName1) ? -1 : 1;
+ replicaForNextRound.add(replica);
}
- });
- return orderedAssignableReplicas;
+ }
+ return new MutablePair<>(nextAssinableReplica, replicaForNextRound);
+ }
+
+ // return true is replica1 is better
+ private boolean keepOriginalPreferredReplica(AssignableReplica replica1,
Review comment:
NIT: function naming should be closer to something like `compareReplicas`, because the logic is not about "keeping a replica" per se.
##########
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;
Review comment:
Question: why does it start with 0.01?
##########
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,
+ _replicaHashCodeMap, highestScore, score)) {
+ highestScore = score;
+ if (nextAssinableReplica != null) {
+ replicaForNextRound.add(nextAssinableReplica);
}
+ nextAssinableReplica = replica;
} else {
- // If the best possible assignment contains the assignment, prioritize the replica.
- return bestPossibleAssignment.containsKey(resourceName1) ? -1 : 1;
+ replicaForNextRound.add(replica);
}
- });
- return orderedAssignableReplicas;
+ }
+ return new MutablePair<>(nextAssinableReplica, replicaForNextRound);
+ }
+
+ // return true is replica1 is better
+ private boolean keepOriginalPreferredReplica(AssignableReplica replica1,
+ AssignableReplica replica2, ClusterModel clusterModel,
+ Map<String, Integer> replicaHashCodeMap, float replica1Score, float replica2Score) {
+ Map<String, ResourceAssignment> _bestPossibleAssignment =
+ clusterModel.getContext().getBestPossibleAssignment();
+ Map<String, ResourceAssignment> _baselineAssignment =
+ clusterModel.getContext().getBaselineAssignment();
+
+ String resourceName1 = replica1.getResourceName();
+ String resourceName2 = replica2.getResourceName();
+
+ // 1. Sort according if the assignment exists in the best possible and/or baseline assignment
+ if (_bestPossibleAssignment.containsKey(resourceName1) != _bestPossibleAssignment
+ .containsKey(resourceName2)) {
+ // If the best possible assignment contains only one replica's assignment,
+ // prioritize the replica.
+ return _bestPossibleAssignment.containsKey(resourceName1);
+ }
+
+ if (_baselineAssignment.containsKey(resourceName1) != _baselineAssignment
+ .containsKey(resourceName2)) {
+ // If the baseline assignment contains only one replica's assignment, prioritize the replica.
+ return _baselineAssignment.containsKey(resourceName1);
+ }
+
+ // 2. Sort according to the state priority. Or the greedy algorithm will unnecessarily shuffle
+ // the states between replicas.
+ int statePriority1 = replica1.getStatePriority();
+ int statePriority2 = replica2.getStatePriority();
+ if (statePriority1 != statePriority2) {
+ // Note we shall prioritize the replica with a higher state priority,
+ // the smaller priority number means higher priority.
+ return statePriority1 - statePriority2 < 0;
+ }
+
+ // 3. Sort according to the replica impact based on the weight.
+ // So the greedy algorithm will place the more impactful replicas first.
+ if (Math.abs(replica2Score - replica1Score) > 0.001f) {
+ return replica1Score > replica2Score;
+ }
+
+ // 4. Sort according to the resource/partition name.
+ // If none of the above conditions is making a difference, 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) < 0;
+ } else {
+ // In case of hash collision, return order according to the name.
+ return replica1.toString().compareTo(replica2.toString()) < 0;
+ }
Review comment:
NIT: I suppose you could also have pre-sorted the list of replicas with the other 3 conditions, store the sorted list outside, then just compare the scores during `getNextAssignableReplica`. It doesn't provide any performance boost but it looks cleaner IMO.
##########
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);
Review comment:
Is the 0.01 to avoid divide by 0? May be a good idea to comment that.
Also, this division cancels out the denominator if I'm not mistaken? This score can be simplified to "replica usage / remaining capacity in the cluster".
--
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
[GitHub] [helix] NealSun96 commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r612671942
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,135 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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;
- }
+ private Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ if (utilizationMap.containsKey(capacityKey)) {
+ Integer newUtil =
+ utilizationMap.get(capacityKey) + node.getRemainingCapacity().get(capacityKey);
+ // update util
+ utilizationMap.put(capacityKey, newUtil);
} else {
- // If the baseline assignment contains the assignment, prioritize the replica.
- return baselineAssignment.containsKey(resourceName1) ? -1 : 1;
+ Integer newUtil = node.getRemainingCapacity().get(capacityKey);
+ utilizationMap.put(capacityKey, newUtil);
}
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private int _score = 0;
+ private boolean _isInBestPossibleAssignment;
+ private boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
+ _replica = replica;
+ _isInBestPossibleAssignment = clusterModel.getContext().getBestPossibleAssignment()
+ .containsKey(replica.getResourceName());
+ _isInBaselineAssignment =
+ clusterModel.getContext().getBaselineAssignment().containsKey(replica.getResourceName());
+ _replicaHash = Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet());
+ }
+
+ public void reComputeScore(Map<String, Integer> overallClusterRemainingCapMap) {
+ int score = 0;
+ // score = SUM(weight * (resource_capacity/cluster_capacity) where weight = 1/(1-total_util%)
+ // it could be be simplified to "resource_capacity/cluster_remainingCapacity".
+ for (Map.Entry<String, Integer> resourceCapacity : _replica.getCapacity().entrySet()) {
+ score += resourceCapacity.getValue() * 100 / (
+ overallClusterRemainingCapMap.get(resourceCapacity.getKey())
+ + 0.01f /*avoid divide by 0*/);
Review comment:
My original comment is more focused on the fact that 0.01 is a magical number that could have an impact to the remaining capacities, since the remaining capacities aren't normalized and their units can vary. You're right that it's an integer so my extreme example wouldn't hold, but I hope my point has come across. :)
I firmly believe that using a magical number to avoid "divide by 0" is hacky no matter what value is chosen. I suggest throwing an exception when the remaining capacity is 0 and terminate the assignment right then and there. For code cleanness, you may want to consider using do while as suggested by @jiajunwang . I will also comment there to see if that solution makes sense.
--
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
[GitHub] [helix] NealSun96 commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r605276834
##########
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,
+ _replicaHashCodeMap, highestScore, score)) {
+ highestScore = score;
+ if (nextAssinableReplica != null) {
+ replicaForNextRound.add(nextAssinableReplica);
}
+ nextAssinableReplica = replica;
} else {
- // If the best possible assignment contains the assignment, prioritize the replica.
- return bestPossibleAssignment.containsKey(resourceName1) ? -1 : 1;
+ replicaForNextRound.add(replica);
}
- });
- return orderedAssignableReplicas;
+ }
+ return new MutablePair<>(nextAssinableReplica, replicaForNextRound);
+ }
+
+ // return true is replica1 is better
+ private boolean keepOriginalPreferredReplica(AssignableReplica replica1,
+ AssignableReplica replica2, ClusterModel clusterModel,
+ Map<String, Integer> replicaHashCodeMap, float replica1Score, float replica2Score) {
+ Map<String, ResourceAssignment> _bestPossibleAssignment =
+ clusterModel.getContext().getBestPossibleAssignment();
+ Map<String, ResourceAssignment> _baselineAssignment =
+ clusterModel.getContext().getBaselineAssignment();
+
+ String resourceName1 = replica1.getResourceName();
+ String resourceName2 = replica2.getResourceName();
+
+ // 1. Sort according if the assignment exists in the best possible and/or baseline assignment
+ if (_bestPossibleAssignment.containsKey(resourceName1) != _bestPossibleAssignment
+ .containsKey(resourceName2)) {
+ // If the best possible assignment contains only one replica's assignment,
+ // prioritize the replica.
+ return _bestPossibleAssignment.containsKey(resourceName1);
+ }
+
+ if (_baselineAssignment.containsKey(resourceName1) != _baselineAssignment
+ .containsKey(resourceName2)) {
+ // If the baseline assignment contains only one replica's assignment, prioritize the replica.
+ return _baselineAssignment.containsKey(resourceName1);
+ }
+
+ // 2. Sort according to the state priority. Or the greedy algorithm will unnecessarily shuffle
+ // the states between replicas.
+ int statePriority1 = replica1.getStatePriority();
+ int statePriority2 = replica2.getStatePriority();
+ if (statePriority1 != statePriority2) {
+ // Note we shall prioritize the replica with a higher state priority,
+ // the smaller priority number means higher priority.
+ return statePriority1 - statePriority2 < 0;
+ }
+
+ // 3. Sort according to the replica impact based on the weight.
+ // So the greedy algorithm will place the more impactful replicas first.
+ if (Math.abs(replica2Score - replica1Score) > 0.001f) {
+ return replica1Score > replica2Score;
+ }
+
+ // 4. Sort according to the resource/partition name.
+ // If none of the above conditions is making a difference, 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) < 0;
+ } else {
+ // In case of hash collision, return order according to the name.
+ return replica1.toString().compareTo(replica2.toString()) < 0;
+ }
Review comment:
As discussed with @xyuanlu , pre-sorting will have additional n(log n) complexity, since the usage here is only "find max", not sorting. Feel free to discard this comment.
--
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
[GitHub] [helix] NealSun96 commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r611948370
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,135 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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;
- }
+ private Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ if (utilizationMap.containsKey(capacityKey)) {
Review comment:
Consider shortening it to `utilizationMap.compute(capacityKey, (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey) : v + node.getRemainingCapacity().get(capacityKey))`?
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,135 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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;
- }
+ private Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ if (utilizationMap.containsKey(capacityKey)) {
+ Integer newUtil =
+ utilizationMap.get(capacityKey) + node.getRemainingCapacity().get(capacityKey);
+ // update util
+ utilizationMap.put(capacityKey, newUtil);
} else {
- // If the baseline assignment contains the assignment, prioritize the replica.
- return baselineAssignment.containsKey(resourceName1) ? -1 : 1;
+ Integer newUtil = node.getRemainingCapacity().get(capacityKey);
+ utilizationMap.put(capacityKey, newUtil);
}
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private int _score = 0;
+ private boolean _isInBestPossibleAssignment;
+ private boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
+ _replica = replica;
+ _isInBestPossibleAssignment = clusterModel.getContext().getBestPossibleAssignment()
+ .containsKey(replica.getResourceName());
+ _isInBaselineAssignment =
+ clusterModel.getContext().getBaselineAssignment().containsKey(replica.getResourceName());
+ _replicaHash = Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet());
+ }
+
+ public void reComputeScore(Map<String, Integer> overallClusterRemainingCapMap) {
+ int score = 0;
+ // score = SUM(weight * (resource_capacity/cluster_capacity) where weight = 1/(1-total_util%)
+ // it could be be simplified to "resource_capacity/cluster_remainingCapacity".
+ for (Map.Entry<String, Integer> resourceCapacity : _replica.getCapacity().entrySet()) {
+ score += resourceCapacity.getValue() * 100 / (
+ overallClusterRemainingCapMap.get(resourceCapacity.getKey())
+ + 0.01f /*avoid divide by 0*/);
Review comment:
Does 0.01 really make sense, in case when a certain capacity is measured in decimals, and 0.01 becomes a significant portion (total cluster capacity = 0.01 TB, as an extreme example, then adding 0.01 is a 100% increase to the remaining cap).
On the other hand, why are we handling the case for "remaining cap = 0"? When that happens, this assignment is already doomed, right? I don't think it's possible to place this replica any more.
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -68,23 +68,40 @@ 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)) {
+
+ // Compute overall utilization of the cluster. Capacity dimension -> total remaining capacity
+ Map<String, Integer> overallClusterRemainingCapacityMap =
+ computeOverallClusterRemainingCapacity(nodes);
+
+ // Create a wrapper for each AssignableReplica.
+ Set<AssignableReplicaWithScore> toBeAssignedReplicas =
+ clusterModel.getAssignableReplicaMap().values().stream()
+ .flatMap(replicas -> replicas.stream())
+ .map(replica -> new AssignableReplicaWithScore(replica, clusterModel))
+ .collect(Collectors.toSet());
+
+ AssignableReplicaWithScore replica =
+ getNextAssignableReplica(toBeAssignedReplicas, overallClusterRemainingCapacityMap);
+ while (replica != null) {
+ toBeAssignedReplicas.remove(replica);
+ AssignableReplica rawReplica = replica.getRawAssignableReplica();
Review comment:
(This is related to my comment on function naming for `AssignableReplicaWithScore`. )
`rawReplica` here is really just `replica`, and the `replica` before should be `replicaWithScore`, right? I believe that's more clear as the names reflect their classes, and `getRawAssignableReplica()` could just become `getAssignableReplica()`.
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,135 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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;
- }
+ private Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ if (utilizationMap.containsKey(capacityKey)) {
+ Integer newUtil =
+ utilizationMap.get(capacityKey) + node.getRemainingCapacity().get(capacityKey);
+ // update util
+ utilizationMap.put(capacityKey, newUtil);
} else {
- // If the baseline assignment contains the assignment, prioritize the replica.
- return baselineAssignment.containsKey(resourceName1) ? -1 : 1;
+ Integer newUtil = node.getRemainingCapacity().get(capacityKey);
+ utilizationMap.put(capacityKey, newUtil);
}
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
Review comment:
Two comments about function naming here:
1. We could just say "computeScore" instead of "reComputeScore". We're re-computing by calling the compute function again.
2. We could just say "getAssignableReplica" instead of "getRawAssignableReplica".
Happy to discuss.
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r606443515
##########
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)) {
Review comment:
Good point, Updated.
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r612016259
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -68,23 +68,40 @@ 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)) {
+
+ // Compute overall utilization of the cluster. Capacity dimension -> total remaining capacity
+ Map<String, Integer> overallClusterRemainingCapacityMap =
+ computeOverallClusterRemainingCapacity(nodes);
+
+ // Create a wrapper for each AssignableReplica.
+ Set<AssignableReplicaWithScore> toBeAssignedReplicas =
+ clusterModel.getAssignableReplicaMap().values().stream()
+ .flatMap(replicas -> replicas.stream())
+ .map(replica -> new AssignableReplicaWithScore(replica, clusterModel))
+ .collect(Collectors.toSet());
+
+ AssignableReplicaWithScore replica =
+ getNextAssignableReplica(toBeAssignedReplicas, overallClusterRemainingCapacityMap);
+ while (replica != null) {
+ toBeAssignedReplicas.remove(replica);
+ AssignableReplica rawReplica = replica.getRawAssignableReplica();
Review comment:
TFTR. Good suggestion. Will update.
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r612827236
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,135 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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;
- }
+ private Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ if (utilizationMap.containsKey(capacityKey)) {
+ Integer newUtil =
+ utilizationMap.get(capacityKey) + node.getRemainingCapacity().get(capacityKey);
+ // update util
+ utilizationMap.put(capacityKey, newUtil);
} else {
- // If the baseline assignment contains the assignment, prioritize the replica.
- return baselineAssignment.containsKey(resourceName1) ? -1 : 1;
+ Integer newUtil = node.getRemainingCapacity().get(capacityKey);
+ utilizationMap.put(capacityKey, newUtil);
}
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private int _score = 0;
+ private boolean _isInBestPossibleAssignment;
+ private boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
+ _replica = replica;
+ _isInBestPossibleAssignment = clusterModel.getContext().getBestPossibleAssignment()
+ .containsKey(replica.getResourceName());
+ _isInBaselineAssignment =
+ clusterModel.getContext().getBaselineAssignment().containsKey(replica.getResourceName());
+ _replicaHash = Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet());
+ }
+
+ public void reComputeScore(Map<String, Integer> overallClusterRemainingCapMap) {
+ int score = 0;
+ // score = SUM(weight * (resource_capacity/cluster_capacity) where weight = 1/(1-total_util%)
+ // it could be be simplified to "resource_capacity/cluster_remainingCapacity".
+ for (Map.Entry<String, Integer> resourceCapacity : _replica.getCapacity().entrySet()) {
+ score += resourceCapacity.getValue() * 100 / (
+ overallClusterRemainingCapMap.get(resourceCapacity.getKey())
+ + 0.01f /*avoid divide by 0*/);
Review comment:
We had an offline discussion with jiajunwang. Our final decision is:
1. function `computeScore` should add 0 to final score when replica's capacity on a dimension is 0.
2. function `computeScore` will return Integer.MAX_VALUE when cluster's remaining capacity is 0.
3. `computeScore` won't throw exception or do admission check (won't throw exception when cluster's remaining capacity is 0). Constrain check will fail this placement in the next step.
4. Also, to avoid overflow, the score is caped at 100 for each dimension.
--
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
[GitHub] [helix] NealSun96 commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r605277429
##########
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,
+ _replicaHashCodeMap, highestScore, score)) {
+ highestScore = score;
+ if (nextAssinableReplica != null) {
+ replicaForNextRound.add(nextAssinableReplica);
}
+ nextAssinableReplica = replica;
} else {
- // If the best possible assignment contains the assignment, prioritize the replica.
- return bestPossibleAssignment.containsKey(resourceName1) ? -1 : 1;
+ replicaForNextRound.add(replica);
}
- });
- return orderedAssignableReplicas;
+ }
+ return new MutablePair<>(nextAssinableReplica, replicaForNextRound);
Review comment:
As discussed, the concern is that removing the "best replica" from the list is O(n). Please consider using a set for the outer scope data structure since the list-typing serves no purpose.
--
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
[GitHub] [helix] NealSun96 commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r612672450
##########
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:
How about
```
do {
...
}
while (!toBeAssignedReplicas.isEmpty())
```
?
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r612781220
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,135 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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;
- }
+ private Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ if (utilizationMap.containsKey(capacityKey)) {
Review comment:
TFTR. Updated
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r616264869
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -68,23 +71,40 @@ 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)) {
+
+ // Compute overall utilization of the cluster. Capacity dimension -> total remaining capacity
+ Map<String, Integer> overallClusterRemainingCapacityMap =
+ computeOverallClusterRemainingCapacity(nodes);
+
+ // Create a wrapper for each AssignableReplica.
+ Set<AssignableReplicaWithScore> toBeAssignedReplicas =
+ clusterModel.getAssignableReplicaMap().values().stream()
+ .flatMap(replicas -> replicas.stream())
+ .map(replica -> new AssignableReplicaWithScore(replica, clusterModel))
+ .collect(Collectors.toSet());
+
+ while (!toBeAssignedReplicas.isEmpty()) {
+ AssignableReplicaWithScore replicaWithScore =
+ getNextAssignableReplica(toBeAssignedReplicas, overallClusterRemainingCapacityMap);
Review comment:
Moving the remove part to getNextAssignableReplica is more cleaner. However, based on our offline discussion, it is not easy to do remove the selected replica from linkedList/listArray with the same time complexity O(1). Will keep using set 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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r606479166
##########
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:
I am not sure... I think we still need to call `getNextAssignableReplica` twice when using do-while .
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r617771508
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -68,23 +69,39 @@ 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)) {
+
+ // Compute overall utilization of the cluster. Capacity dimension -> total remaining capacity
+ Map<String, Integer> overallClusterRemainingCapacityMap =
+ computeOverallClusterRemainingCapacity(nodes);
+
+ // Create a wrapper for each AssignableReplica.
+ Set<AssignableReplicaWithScore> toBeAssignedReplicas =
+ clusterModel.getAssignableReplicaMap().values().stream()
+ .flatMap(replicas -> replicas.stream())
+ .map(replica -> new AssignableReplicaWithScore(replica, clusterModel))
+ .collect(Collectors.toSet());
+
+ while (!toBeAssignedReplicas.isEmpty()) {
+ AssignableReplicaWithScore replicaWithScore =
+ getNextAssignableReplica(toBeAssignedReplicas, overallClusterRemainingCapacityMap);
Review comment:
Good suggestion. will update.
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r616893210
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,135 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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;
- }
+ private Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ if (utilizationMap.containsKey(capacityKey)) {
+ Integer newUtil =
+ utilizationMap.get(capacityKey) + node.getRemainingCapacity().get(capacityKey);
+ // update util
+ utilizationMap.put(capacityKey, newUtil);
} else {
- // If the baseline assignment contains the assignment, prioritize the replica.
- return baselineAssignment.containsKey(resourceName1) ? -1 : 1;
+ Integer newUtil = node.getRemainingCapacity().get(capacityKey);
+ utilizationMap.put(capacityKey, newUtil);
}
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
Review comment:
Updated.
--
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
[GitHub] [helix] jiajunwang commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
jiajunwang commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r616031829
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +172,136 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private float _score = 0;
+ private boolean _isInBestPossibleAssignment;
Review comment:
nit, final?
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +172,136 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private float _score = 0;
+ private boolean _isInBestPossibleAssignment;
+ private boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
+ _replica = replica;
+ _isInBestPossibleAssignment = clusterModel.getContext().getBestPossibleAssignment()
+ .containsKey(replica.getResourceName());
+ _isInBaselineAssignment =
+ clusterModel.getContext().getBaselineAssignment().containsKey(replica.getResourceName());
+ _replicaHash = Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet());
+ }
+
+ public void computeScore(Map<String, Integer> overallClusterRemainingCapMap) {
+ float score = 0;
+ // score = SUM(weight * (resource_capacity/cluster_capacity) where weight = 1/(1-total_util%)
+ // it could be be simplified to "resource_capacity/cluster_remainingCapacity".
+ for (Map.Entry<String, Integer> resourceCapacity : _replica.getCapacity().entrySet()) {
+ score = resourceCapacity.getValue() == 0 ? score
Review comment:
nit, IMO, checking resourceCapacity.getValue() == 0 and skip the loop makes the code cleaner. And it helps to avoid the unnecessary score value update if the compiler does not optimize it automatically.
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -68,23 +71,40 @@ 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)) {
+
+ // Compute overall utilization of the cluster. Capacity dimension -> total remaining capacity
+ Map<String, Integer> overallClusterRemainingCapacityMap =
+ computeOverallClusterRemainingCapacity(nodes);
+
+ // Create a wrapper for each AssignableReplica.
+ Set<AssignableReplicaWithScore> toBeAssignedReplicas =
+ clusterModel.getAssignableReplicaMap().values().stream()
+ .flatMap(replicas -> replicas.stream())
+ .map(replica -> new AssignableReplicaWithScore(replica, clusterModel))
+ .collect(Collectors.toSet());
+
+ while (!toBeAssignedReplicas.isEmpty()) {
+ AssignableReplicaWithScore replicaWithScore =
+ getNextAssignableReplica(toBeAssignedReplicas, overallClusterRemainingCapacityMap);
Review comment:
Can we remove the selected replica in the getNextAssignableReplica() method? Maybe call it pollNextAssignableReplica()? Then I guess we can just use a linked list or some other more efficient data structure to make the loop faster.
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +172,136 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private float _score = 0;
+ private boolean _isInBestPossibleAssignment;
+ private boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
Review comment:
Just extend AssignableReplica?
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -42,6 +42,9 @@
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
+import static java.lang.Float.compare;
Review comment:
nit, better directly call Float.compare in the code. Static import here is not quite desired.
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r612781049
##########
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:
Thanks for the offline discussion. Changed to use `toBeAssignedReplicas.isEmpty()` in while evaluate expression.
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r612051412
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,135 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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;
- }
+ private Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ if (utilizationMap.containsKey(capacityKey)) {
+ Integer newUtil =
+ utilizationMap.get(capacityKey) + node.getRemainingCapacity().get(capacityKey);
+ // update util
+ utilizationMap.put(capacityKey, newUtil);
} else {
- // If the baseline assignment contains the assignment, prioritize the replica.
- return baselineAssignment.containsKey(resourceName1) ? -1 : 1;
+ Integer newUtil = node.getRemainingCapacity().get(capacityKey);
+ utilizationMap.put(capacityKey, newUtil);
}
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private int _score = 0;
+ private boolean _isInBestPossibleAssignment;
+ private boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
+ _replica = replica;
+ _isInBestPossibleAssignment = clusterModel.getContext().getBestPossibleAssignment()
+ .containsKey(replica.getResourceName());
+ _isInBaselineAssignment =
+ clusterModel.getContext().getBaselineAssignment().containsKey(replica.getResourceName());
+ _replicaHash = Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet());
+ }
+
+ public void reComputeScore(Map<String, Integer> overallClusterRemainingCapMap) {
+ int score = 0;
+ // score = SUM(weight * (resource_capacity/cluster_capacity) where weight = 1/(1-total_util%)
+ // it could be be simplified to "resource_capacity/cluster_remainingCapacity".
+ for (Map.Entry<String, Integer> resourceCapacity : _replica.getCapacity().entrySet()) {
+ score += resourceCapacity.getValue() * 100 / (
+ overallClusterRemainingCapMap.get(resourceCapacity.getKey())
+ + 0.01f /*avoid divide by 0*/);
Review comment:
Thanks for the comment. I think it reveals a valid point -- should we continue the process when remaining capacity is 0? I think we could safe several compute cycle by checking hard constrain first and quit early. That might be more elegant comparing to this hacky way of avoiding divide by 0.
Regarding the example in your comment, I am not sure if this will happen since the remaining capacity is an Integer. I think adding 0.01 to 1 might not change the result a lot since we only care about the relative relationship between each replicas.
Considering the effort in development, I think maybe adding 0.01 here is the easiest way to avoid divide by 0.
All comments are welcome. :D
--
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
[GitHub] [helix] jiajunwang commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r616264140
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +172,136 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private float _score = 0;
+ private boolean _isInBestPossibleAssignment;
+ private boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
Review comment:
Please correct me if I am wrong. We already have a list of AssignableReplica objects in clusterModel. Why creating many duplicated objects? I think wrapper is a better choice here.
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -42,6 +42,9 @@
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
+import static java.lang.Float.compare;
Review comment:
TFTR. Updated.
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r617772792
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,139 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private float _score = 0;
+ private final boolean _isInBestPossibleAssignment;
+ private final boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
+ _replica = replica;
+ _isInBestPossibleAssignment = clusterModel.getContext().getBestPossibleAssignment()
+ .containsKey(replica.getResourceName());
+ _isInBaselineAssignment =
+ clusterModel.getContext().getBaselineAssignment().containsKey(replica.getResourceName());
+ _replicaHash = Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet());
+ }
+
+ public void computeScore(Map<String, Integer> overallClusterRemainingCapMap) {
+ float score = 0;
+ // score = SUM(weight * (resource_capacity/cluster_capacity) where weight = 1/(1-total_util%)
+ // it could be be simplified to "resource_capacity/cluster_remainingCapacity".
+ for (Map.Entry<String, Integer> resourceCapacity : _replica.getCapacity().entrySet()) {
+ if (resourceCapacity.getValue() == 0) {
Review comment:
JJ mentioned a good point here and I agree with that. "checking resourceCapacity.getValue() == 0 and skip the loop makes the code cleaner. And it helps to avoid the unnecessary score value update if the compiler does not optimize it automatically"
--
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
[GitHub] [helix] xyuanlu commented on pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on pull request #1691:
URL: https://github.com/apache/helix/pull/1691#issuecomment-820665685
> Question: a general question, seemed this sorting to be happened in every pipeline. Can we add some checks there? If no condition needed for such sorting, we skip it?
Thanks for the question.
In my understanding, we sort replicas for two reasons:
1. For every rebalance, the assignment of each replicas should be in the same sequence. This is already garnered in the original design.
2. We want to place replicas with larger impact first to solve the failure by placing very large partition after small partitions. We only know the placement will fail afterward. So it is hard to know is we need to sort beforehand.
Hope my explain is clear.
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r606443728
##########
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,
+ _replicaHashCodeMap, highestScore, score)) {
+ highestScore = score;
+ if (nextAssinableReplica != null) {
+ replicaForNextRound.add(nextAssinableReplica);
}
+ nextAssinableReplica = replica;
} else {
- // If the best possible assignment contains the assignment, prioritize the replica.
- return bestPossibleAssignment.containsKey(resourceName1) ? -1 : 1;
+ replicaForNextRound.add(replica);
}
- });
- return orderedAssignableReplicas;
+ }
+ return new MutablePair<>(nextAssinableReplica, replicaForNextRound);
Review comment:
Thanks for the review. I updated the PR based on our offline discussion.
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm storing logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r606443029
##########
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:
Thanks for the review. I updated the PR based on our offline discussion.
--
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
[GitHub] [helix] dasahcc commented on pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
dasahcc commented on pull request #1691:
URL: https://github.com/apache/helix/pull/1691#issuecomment-820651685
Question: a general question, seemed this sorting to be happened in every pipeline. Can we add some checks there? If no condition needed for such sorting, we skip it?
--
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
[GitHub] [helix] xyuanlu commented on pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on pull request #1691:
URL: https://github.com/apache/helix/pull/1691#issuecomment-826028259
This PR is ready to be merged. Approved by @NealSun96
Final commit message:
Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact.
--
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
[GitHub] [helix] jiajunwang merged pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
jiajunwang merged pull request #1691:
URL: https://github.com/apache/helix/pull/1691
--
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
[GitHub] [helix] NealSun96 commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r617808305
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,139 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private float _score = 0;
+ private final boolean _isInBestPossibleAssignment;
+ private final boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
+ _replica = replica;
+ _isInBestPossibleAssignment = clusterModel.getContext().getBestPossibleAssignment()
+ .containsKey(replica.getResourceName());
+ _isInBaselineAssignment =
+ clusterModel.getContext().getBaselineAssignment().containsKey(replica.getResourceName());
+ _replicaHash = Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet());
+ }
+
+ public void computeScore(Map<String, Integer> overallClusterRemainingCapMap) {
+ float score = 0;
+ // score = SUM(weight * (resource_capacity/cluster_capacity) where weight = 1/(1-total_util%)
+ // it could be be simplified to "resource_capacity/cluster_remainingCapacity".
+ for (Map.Entry<String, Integer> resourceCapacity : _replica.getCapacity().entrySet()) {
+ if (resourceCapacity.getValue() == 0) {
Review comment:
I think the next line's calculation encapsulates the mathematical logic completely (including when there's no resource_capacity), and doesn't need this extra check; imo this doesn't look as clean. But since there are 2 votes already, I'll oblige.
--
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
[GitHub] [helix] NealSun96 commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
NealSun96 commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r617762721
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -68,23 +69,39 @@ 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)) {
+
+ // Compute overall utilization of the cluster. Capacity dimension -> total remaining capacity
+ Map<String, Integer> overallClusterRemainingCapacityMap =
+ computeOverallClusterRemainingCapacity(nodes);
+
+ // Create a wrapper for each AssignableReplica.
+ Set<AssignableReplicaWithScore> toBeAssignedReplicas =
+ clusterModel.getAssignableReplicaMap().values().stream()
+ .flatMap(replicas -> replicas.stream())
+ .map(replica -> new AssignableReplicaWithScore(replica, clusterModel))
+ .collect(Collectors.toSet());
+
+ while (!toBeAssignedReplicas.isEmpty()) {
+ AssignableReplicaWithScore replicaWithScore =
+ getNextAssignableReplica(toBeAssignedReplicas, overallClusterRemainingCapacityMap);
Review comment:
Do you think it makes sense for `getNextAssignableReplica` to return an actual `AssignableReplica`, instead of an `AssignableReplicaWithScore`?
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,139 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private float _score = 0;
+ private final boolean _isInBestPossibleAssignment;
+ private final boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
+ _replica = replica;
+ _isInBestPossibleAssignment = clusterModel.getContext().getBestPossibleAssignment()
+ .containsKey(replica.getResourceName());
+ _isInBaselineAssignment =
+ clusterModel.getContext().getBaselineAssignment().containsKey(replica.getResourceName());
+ _replicaHash = Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet());
+ }
+
+ public void computeScore(Map<String, Integer> overallClusterRemainingCapMap) {
+ float score = 0;
+ // score = SUM(weight * (resource_capacity/cluster_capacity) where weight = 1/(1-total_util%)
+ // it could be be simplified to "resource_capacity/cluster_remainingCapacity".
+ for (Map.Entry<String, Integer> resourceCapacity : _replica.getCapacity().entrySet()) {
+ if (resourceCapacity.getValue() == 0) {
Review comment:
Is there a reason for a special case here? It looks like it will result in `score = score + 0` anyways.
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +169,139 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
Review comment:
NIT: can be shortened to one line `compute`
--
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
[GitHub] [helix] xyuanlu commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
xyuanlu commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r616892627
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +172,136 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private float _score = 0;
+ private boolean _isInBestPossibleAssignment;
Review comment:
Updated.
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +172,136 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private float _score = 0;
+ private boolean _isInBestPossibleAssignment;
+ private boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
+ _replica = replica;
+ _isInBestPossibleAssignment = clusterModel.getContext().getBestPossibleAssignment()
+ .containsKey(replica.getResourceName());
+ _isInBaselineAssignment =
+ clusterModel.getContext().getBaselineAssignment().containsKey(replica.getResourceName());
+ _replicaHash = Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet());
+ }
+
+ public void computeScore(Map<String, Integer> overallClusterRemainingCapMap) {
+ float score = 0;
+ // score = SUM(weight * (resource_capacity/cluster_capacity) where weight = 1/(1-total_util%)
+ // it could be be simplified to "resource_capacity/cluster_remainingCapacity".
+ for (Map.Entry<String, Integer> resourceCapacity : _replica.getCapacity().entrySet()) {
+ score = resourceCapacity.getValue() == 0 ? score
Review comment:
Updated.
--
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
[GitHub] [helix] jiajunwang commented on a change in pull request #1691: Improve the WAGED.ConstraintBasedAlgorithm sorting logic to prioritize replica with larger impact
Posted by GitBox <gi...@apache.org>.
jiajunwang commented on a change in pull request #1691:
URL: https://github.com/apache/helix/pull/1691#discussion_r619423198
##########
File path: helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java
##########
@@ -152,69 +172,136 @@ 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());
-
- Map<String, ResourceAssignment> bestPossibleAssignment =
- clusterModel.getContext().getBestPossibleAssignment();
- Map<String, ResourceAssignment> baselineAssignment =
- clusterModel.getContext().getBaselineAssignment();
-
- Map<String, Integer> replicaHashCodeMap = orderedAssignableReplicas.parallelStream().collect(
- Collectors.toMap(AssignableReplica::toString,
- replica -> Objects.hash(replica.toString(), clusterModel.getAssignableNodes().keySet()),
- (hash1, hash2) -> hash2));
-
- // 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 Map<String, Integer> computeOverallClusterRemainingCapacity(List<AssignableNode> nodes) {
+ Map<String, Integer> utilizationMap = new HashMap<>();
+ for (AssignableNode node : nodes) {
+ for (String capacityKey : node.getMaxCapacity().keySet()) {
+ utilizationMap.compute(capacityKey,
+ (k, v) -> v == null ? node.getRemainingCapacity().get(capacityKey)
+ : v + node.getRemainingCapacity().get(capacityKey));
+ }
+ }
+ return utilizationMap;
+ }
+
+ /**
+ * Update the overallClusterUtilMap with newly placed replica
+ */
+ private void updateOverallClusterRemainingCapacity(
+ Map<String, Integer> overallClusterRemainingCapacityMap, AssignableReplica replica) {
+ for (Map.Entry<String, Integer> resourceUsage : replica.getCapacity().entrySet()) {
+ Integer newRemainingCapacity =
+ overallClusterRemainingCapacityMap.get(resourceUsage.getKey()) - resourceUsage.getValue();
+ overallClusterRemainingCapacityMap.put(resourceUsage.getKey(), newRemainingCapacity);
+ }
+ }
+
+ private class AssignableReplicaWithScore implements Comparable<AssignableReplicaWithScore> {
+ private final AssignableReplica _replica;
+ private float _score = 0;
+ private boolean _isInBestPossibleAssignment;
+ private boolean _isInBaselineAssignment;
+ private final Integer _replicaHash;
+
+ AssignableReplicaWithScore(AssignableReplica replica, ClusterModel clusterModel) {
Review comment:
This is just another way to wrap the class. My intention is just help you to reduce some of the methods like, toString(), getAssignableReplica() - since it is already an assignableReplia.
--
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