You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@helix.apache.org by ji...@apache.org on 2020/03/13 22:28:53 UTC
[helix] branch master updated: Remove possible score-tie between
two AssignableNodes (#889)
This is an automated email from the ASF dual-hosted git repository.
jiajunwang pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/helix.git
The following commit(s) were added to refs/heads/master by this push:
new c966784 Remove possible score-tie between two AssignableNodes (#889)
c966784 is described below
commit c9667847644f11abcf63d83e16a878ccb403257a
Author: Neal Sun <ne...@gmail.com>
AuthorDate: Fri Mar 13 15:28:42 2020 -0700
Remove possible score-tie between two AssignableNodes (#889)
This PR fixes a potential situation where two AssignableNodes will receive the same score; the fix makes the algorithm more deterministic.
Co-authored-by: Neal Sun <ne...@nesun-mn1.linkedin.biz>
---
.../constraints/ConstraintBasedAlgorithm.java | 12 +++--
.../constraints/TestConstraintBasedAlgorithm.java | 58 ++++++++++++++--------
.../waged/model/AbstractTestClusterModel.java | 5 +-
.../waged/model/ClusterModelTestHelper.java | 25 ++++++++++
4 files changed, 70 insertions(+), 30 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 dcadff6..2f6c9cd 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
@@ -63,8 +63,7 @@ class ConstraintBasedAlgorithm implements RebalanceAlgorithm {
}
@Override
- public OptimalAssignment calculate(ClusterModel clusterModel)
- throws HelixRebalanceException {
+ public OptimalAssignment calculate(ClusterModel clusterModel) throws HelixRebalanceException {
OptimalAssignment optimalAssignment = new OptimalAssignment();
List<AssignableNode> nodes = new ArrayList<>(clusterModel.getAssignableNodes().values());
Set<String> busyInstances =
@@ -122,9 +121,12 @@ class ConstraintBasedAlgorithm implements RebalanceAlgorithm {
if (scoreCompareResult == 0) {
// If the evaluation scores of 2 nodes are the same, the algorithm assigns the replica
// to the idle node first.
- int idleScore1 = busyInstances.contains(nodeEntry1.getKey().getInstanceName()) ? 0 : 1;
- int idleScore2 = busyInstances.contains(nodeEntry2.getKey().getInstanceName()) ? 0 : 1;
- return idleScore1 - idleScore2;
+ String instanceName1 = nodeEntry1.getKey().getInstanceName();
+ String instanceName2 = nodeEntry2.getKey().getInstanceName();
+ int idleScore1 = busyInstances.contains(instanceName1) ? 0 : 1;
+ int idleScore2 = busyInstances.contains(instanceName2) ? 0 : 1;
+ return idleScore1 != idleScore2 ? (idleScore1 - idleScore2)
+ : - instanceName1.compareTo(instanceName2);
} else {
return scoreCompareResult;
}
diff --git a/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/constraints/TestConstraintBasedAlgorithm.java b/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/constraints/TestConstraintBasedAlgorithm.java
index e0e2eb3..3954407 100644
--- a/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/constraints/TestConstraintBasedAlgorithm.java
+++ b/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/constraints/TestConstraintBasedAlgorithm.java
@@ -19,41 +19,34 @@ package org.apache.helix.controller.rebalancer.waged.constraints;
* under the License.
*/
-import static org.mockito.Matchers.any;
-import static org.mockito.Mockito.mock;
-import static org.mockito.Mockito.when;
-
import java.io.IOException;
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableMap;
import org.apache.helix.HelixRebalanceException;
import org.apache.helix.controller.rebalancer.waged.model.ClusterModel;
import org.apache.helix.controller.rebalancer.waged.model.ClusterModelTestHelper;
import org.apache.helix.controller.rebalancer.waged.model.OptimalAssignment;
import org.testng.Assert;
-import org.testng.annotations.BeforeMethod;
import org.testng.annotations.Test;
-import com.google.common.collect.ImmutableList;
-import com.google.common.collect.ImmutableMap;
+import static org.mockito.Matchers.any;
+import static org.mockito.Mockito.mock;
+import static org.mockito.Mockito.when;
-public class TestConstraintBasedAlgorithm {
- private ConstraintBasedAlgorithm _algorithm;
- @BeforeMethod
- public void beforeMethod() {
+public class TestConstraintBasedAlgorithm {
+ @Test(expectedExceptions = HelixRebalanceException.class)
+ public void testCalculateNoValidAssignment() throws IOException, HelixRebalanceException {
HardConstraint mockHardConstraint = mock(HardConstraint.class);
SoftConstraint mockSoftConstraint = mock(SoftConstraint.class);
when(mockHardConstraint.isAssignmentValid(any(), any(), any())).thenReturn(false);
when(mockSoftConstraint.getAssignmentNormalizedScore(any(), any(), any())).thenReturn(1.0);
-
- _algorithm = new ConstraintBasedAlgorithm(ImmutableList.of(mockHardConstraint),
- ImmutableMap.of(mockSoftConstraint, 1f));
- }
-
- @Test(expectedExceptions = HelixRebalanceException.class)
- public void testCalculateNoValidAssignment() throws IOException, HelixRebalanceException {
+ ConstraintBasedAlgorithm algorithm =
+ new ConstraintBasedAlgorithm(ImmutableList.of(mockHardConstraint),
+ ImmutableMap.of(mockSoftConstraint, 1f));
ClusterModel clusterModel = new ClusterModelTestHelper().getDefaultClusterModel();
- _algorithm.calculate(clusterModel);
+ algorithm.calculate(clusterModel);
}
@Test
@@ -62,11 +55,32 @@ public class TestConstraintBasedAlgorithm {
SoftConstraint mockSoftConstraint = mock(SoftConstraint.class);
when(mockHardConstraint.isAssignmentValid(any(), any(), any())).thenReturn(true);
when(mockSoftConstraint.getAssignmentNormalizedScore(any(), any(), any())).thenReturn(1.0);
- _algorithm = new ConstraintBasedAlgorithm(ImmutableList.of(mockHardConstraint),
- ImmutableMap.of(mockSoftConstraint, 1f));
+ ConstraintBasedAlgorithm algorithm =
+ new ConstraintBasedAlgorithm(ImmutableList.of(mockHardConstraint),
+ ImmutableMap.of(mockSoftConstraint, 1f));
ClusterModel clusterModel = new ClusterModelTestHelper().getDefaultClusterModel();
- OptimalAssignment optimalAssignment = _algorithm.calculate(clusterModel);
+ OptimalAssignment optimalAssignment = algorithm.calculate(clusterModel);
Assert.assertFalse(optimalAssignment.hasAnyFailure());
}
+
+ @Test
+ public void testCalculateScoreDeterminism() throws IOException, HelixRebalanceException {
+ HardConstraint mockHardConstraint = mock(HardConstraint.class);
+ SoftConstraint mockSoftConstraint = mock(SoftConstraint.class);
+ when(mockHardConstraint.isAssignmentValid(any(), any(), any())).thenReturn(true);
+ when(mockSoftConstraint.getAssignmentNormalizedScore(any(), any(), any())).thenReturn(1.0);
+ ConstraintBasedAlgorithm algorithm =
+ new ConstraintBasedAlgorithm(ImmutableList.of(mockHardConstraint),
+ ImmutableMap.of(mockSoftConstraint, 1f));
+ ClusterModel clusterModel = new ClusterModelTestHelper().getMultiNodeClusterModel();
+ OptimalAssignment optimalAssignment = algorithm.calculate(clusterModel);
+
+ optimalAssignment.getOptimalResourceAssignment().values().forEach(
+ resourceAssignment -> resourceAssignment.getMappedPartitions().forEach(partition -> {
+ Assert.assertEquals(resourceAssignment.getReplicaMap(partition).keySet().size(), 1);
+ Assert.assertTrue(resourceAssignment.getReplicaMap(partition)
+ .containsKey(ClusterModelTestHelper.TEST_INSTANCE_ID_1));
+ }));
+ }
}
diff --git a/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/model/AbstractTestClusterModel.java b/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/model/AbstractTestClusterModel.java
index 0fec67b..7f8281b 100644
--- a/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/model/AbstractTestClusterModel.java
+++ b/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/model/AbstractTestClusterModel.java
@@ -196,9 +196,8 @@ public abstract class AbstractTestClusterModel {
protected Set<AssignableNode> generateNodes(ResourceControllerDataProvider testCache) {
Set<AssignableNode> nodeSet = new HashSet<>();
- testCache.getInstanceConfigMap().values().stream()
- .forEach(config -> nodeSet.add(new AssignableNode(testCache.getClusterConfig(),
- testCache.getInstanceConfigMap().get(_testInstanceId), config.getInstanceName())));
+ testCache.getInstanceConfigMap().values().forEach(config -> nodeSet
+ .add(new AssignableNode(testCache.getClusterConfig(), config, config.getInstanceName())));
return nodeSet;
}
}
diff --git a/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/model/ClusterModelTestHelper.java b/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/model/ClusterModelTestHelper.java
index 131d92a..1c1687e 100644
--- a/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/model/ClusterModelTestHelper.java
+++ b/helix-core/src/test/java/org/apache/helix/controller/rebalancer/waged/model/ClusterModelTestHelper.java
@@ -21,11 +21,19 @@ package org.apache.helix.controller.rebalancer.waged.model;
import java.io.IOException;
import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
import java.util.Set;
import org.apache.helix.controller.dataproviders.ResourceControllerDataProvider;
+import org.apache.helix.model.InstanceConfig;
+
+import static org.mockito.Mockito.when;
+
public class ClusterModelTestHelper extends AbstractTestClusterModel {
+ public static final String TEST_INSTANCE_ID_1 = "TestInstanceId1";
+ public static final String TEST_INSTANCE_ID_2 = "TestInstanceId2";
public ClusterModel getDefaultClusterModel() throws IOException {
initialize();
@@ -37,4 +45,21 @@ public class ClusterModelTestHelper extends AbstractTestClusterModel {
new ClusterContext(assignableReplicas, assignableNodes, Collections.emptyMap(), Collections.emptyMap());
return new ClusterModel(context, assignableReplicas, assignableNodes);
}
+
+ public ClusterModel getMultiNodeClusterModel() throws IOException {
+ initialize();
+ ResourceControllerDataProvider testCache = setupClusterDataCache();
+ InstanceConfig testInstanceConfig1 = createMockInstanceConfig(TEST_INSTANCE_ID_1);
+ InstanceConfig testInstanceConfig2 = createMockInstanceConfig(TEST_INSTANCE_ID_2);
+ Map<String, InstanceConfig> instanceConfigMap = new HashMap<>();
+ instanceConfigMap.put(TEST_INSTANCE_ID_1, testInstanceConfig1);
+ instanceConfigMap.put(TEST_INSTANCE_ID_2, testInstanceConfig2);
+ when(testCache.getInstanceConfigMap()).thenReturn(instanceConfigMap);
+ Set<AssignableReplica> assignableReplicas = generateReplicas(testCache);
+ Set<AssignableNode> assignableNodes = generateNodes(testCache);
+
+ ClusterContext context =
+ new ClusterContext(assignableReplicas, assignableNodes, Collections.emptyMap(), Collections.emptyMap());
+ return new ClusterModel(context, assignableReplicas, assignableNodes);
+ }
}