This is an automated email from the ASF dual-hosted git repository. jiajunwang pushed a commit to branch wagedRebalancer in repository https://gitbox.apache.org/repos/asf/helix.git
commit 04f7e049f58da34728154a8fca706a10d6109735 Author: Jiajun Wang <[email protected]> AuthorDate: Mon Oct 28 12:41:31 2019 -0700 Adjust the replica rebalance calculating ordering to avoid static order. (#535) * Adjust the replica rebalance calculating ordering to avoid static order. The problem of a static order is that the same set of replicas will always be the ones that are moved or state transited during the rebalance. This randomize won't change the algorithm's performance. But it will help the Helix to eliminate very unstable partitions. --- .../constraints/ConstraintBasedAlgorithm.java | 22 +++++++++++++++++----- 1 file changed, 17 insertions(+), 5 deletions(-) diff --git a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java index 3f2f845..65737f7 100644 --- a/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java +++ b/helix-core/src/main/java/org/apache/helix/controller/rebalancer/waged/constraints/ConstraintBasedAlgorithm.java @@ -24,6 +24,7 @@ import java.util.Comparator; import java.util.HashMap; import java.util.List; import java.util.Map; +import java.util.Objects; import java.util.Optional; import java.util.Set; import java.util.function.Function; @@ -134,7 +135,6 @@ class ConstraintBasedAlgorithm implements RebalanceAlgorithm { .collect(Collectors.toList()); } - // TODO investigate better ways to sort replicas. One option is sorting based on the creation time. private List<AssignableReplica> getOrderedAssignableReplica(ClusterModel clusterModel) { Map<String, Set<AssignableReplica>> replicasByResource = clusterModel.getAssignableReplicaMap(); List<AssignableReplica> orderedAssignableReplicas = @@ -162,11 +162,23 @@ class ConstraintBasedAlgorithm implements RebalanceAlgorithm { int statePriority1 = replica1.getStatePriority(); int statePriority2 = replica2.getStatePriority(); if (statePriority1 == statePriority2) { - // If state prioritizes are the same, compare the names. - if (resourceName1.equals(resourceName2)) { - return replica1.getPartitionName().compareTo(replica2.getPartitionName()); + // 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. + Long replicaHash1 = (long) Objects + .hash(replica1.toString(), clusterModel.getAssignableNodes().keySet()); + Long replicaHash2 = (long) Objects + .hash(replica2.toString(), clusterModel.getAssignableNodes().keySet()); + if (!replicaHash1.equals(replicaHash2)) { + return replicaHash1.compareTo(replicaHash2); } else { - return resourceName1.compareTo(resourceName2); + // 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,
