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.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 @@
         .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 @@
           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,