helix-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From jiajunw...@apache.org
Subject [helix] branch master updated: Remove possible score-tie between two AssignableNodes (#889)
Date Fri, 13 Mar 2020 22:28:53 GMT
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 <nealsun.0428@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 <nesun@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);
+  }
 }


Mime
View raw message